Every time a user sends their fifth message in a conversation, your LLM server recomputes the attention keys and values for the previous four turns from scratch. Think of it like a chef who, every time a new dish order arrives at a table, goes back to the pantry and re-chops, re-blanches, and re-seasons all the vegetables from earlier courses - even though those components are sitting right there on the pass, ready to use. At a few requests per second, this waste is invisible. At 50,000 concurrent multi-turn sessions, it’s the dominant cost and latency driver in your entire inference stack.

The KV cache is the intermediate activations generated during the transformer’s attention computation - the projected key and value tensors for each token at each layer. On a Llama-3 70B model running on 4xA100 GPUs, a 4,096-token context consumes roughly 4 GB of GPU HBM just for the KV cache. If you have a 20-turn conversation where each turn adds 200 tokens, by turn 20 you’re running a full 4,000-token prefill on every new message - recomputing activations for 19 turns of history that haven’t changed. This is exactly where naive serving engines bleed throughput and latency simultaneously.

The core tension is between memory and compute. GPU HBM is the scarce resource: you need it for model weights, for the KV cache of in-flight tokens, and for the batch of new requests. Storing more conversation history in the KV cache saves prefill FLOPS but steals memory from other requests. Evicting cached history saves memory but forces expensive recomputation. At scale, with 50,000 concurrent sessions each at different turn depths, you need a system that manages KV cache blocks as a shared, addressable pool - not as per-request scratch space that gets discarded after every response.

We need to solve for three things simultaneously: prefix cache lookup that identifies already-computed token sequences, distributed block management that tracks physical GPU memory across replicas, and sticky routing that delivers requests to replicas already holding the relevant cache blocks.

Requirements and Constraints

Functional Requirements

• Cache KV activations for any prefix of a token sequence and serve them on the next matching request
• Support multi-turn conversation sessions where each turn extends the previous turn’s context
• Share cached KV blocks across model replicas when memory pressure is low on a neighbor
• Evict least-recently-used blocks under memory pressure without corrupting in-flight requests
• Invalidate cached blocks when the model version changes or context window policy changes
• Support system prompt caching: system prompts that are identical across thousands of sessions should be computed once and shared globally

Non-Functional Requirements

• TTFT: p50 under 80ms, p99 under 200ms for cache-hit requests (vs 800ms cold for a 4K context)
• Throughput: 50,000 concurrent sessions, 2,000 new turns/second across the cluster
• Cache hit rate: greater than 70% prefix hit rate across all turns in steady state
• Memory efficiency: KV cache layer uses no more than 30% of available HBM per GPU; weights + active batches get the rest
• Cost per million tokens: target below $1.20 fully-loaded (vs $4.80 fully cold)
• Block transfer latency: cross-replica KV block migration completes in under 5ms over NVLink or InfiniBand
• Quality: caching must be bit-exact - reusing a cached block must produce numerically identical output to recomputing it

Constraints

• Model: Llama-3 70B in BF16, tensor-parallel across 4xA100 80GB per replica
• KV block size: fixed at 16 tokens per block (matching PagedAttention’s default)
• Context window: 8,192 tokens maximum; sessions exceeding this trigger sliding window eviction
• Out of scope: cross-session semantic caching (fuzzy prefix match); that’s a different system

High-Level Architecture

The system has six major components layered between the API gateway and the GPU inference workers.

Conversation Router is the entry point. It receives turn N for session S, computes the prefix hash for the conversation history up to turn N-1, and queries the Cache Index to find which replica (if any) holds the matching KV blocks. It then routes the request to the warm replica using sticky consistent hashing - or to any available replica if no warm replica exists.

Cache Index is a distributed in-memory data structure (backed by Redis Cluster) that maps prefix token hashes to the replica ID and physical block addresses holding those blocks. It’s the system’s directory: it knows where every cached prefix lives without holding the cache data itself.

KV Block Manager runs as a sidecar process on each inference replica. It owns the physical HBM allocation for KV blocks, maintains a local radix tree for fast prefix lookup, tracks reference counts so in-flight requests hold blocks open, and evicts LRU blocks when headroom drops below threshold.

Prefill Worker is the GPU process that runs the transformer forward pass to compute KV activations for uncached tokens. It writes new blocks directly to the KV Block Manager. When a request has a partial cache hit (first 3,000 tokens cached, last 500 not), the Prefill Worker computes only the uncached suffix.

Block Transfer Agent handles cross-replica block migration. When the router has no warm local replica for a high-value prefix (system prompts, very-long conversations), the Block Transfer Agent fetches blocks from the source replica over NVLink or InfiniBand and loads them into the destination GPU’s HBM before the prefill starts.

Eviction Oracle is a background service that runs a cost-benefit model: it weighs the probability that a cached block will be used again (based on session activity, turn depth, and historical hit rate) against the HBM cost of holding it. It signals the KV Block Manager when to preemptively evict, before memory pressure forces panic eviction of the wrong blocks.

The KV Block Manager

The KV Block Manager’s job is to turn the GPU’s HBM into a managed pool of fixed-size blocks that can be shared, referenced, and evicted independently.

Think of it like a library’s physical book stacks with a checkout system. Each “book” is a 16-token KV block. The catalog (radix tree) tells you where each sequence lives. A block can be checked out by multiple readers simultaneously (reference-counted), but nobody can evict a book while a patron is actively reading it.

The radix tree (also called a prefix tree or trie over token sequences) is the core data structure. Each node represents a contiguous block of 16 tokens. A path from the root to a leaf represents the full prefix of a conversation. Lookup is O(prefix_length / block_size) - for a 2,048-token history that’s 128 node traversals, each a hash lookup.

# KV block manager: radix tree prefix lookup and block allocation
import hashlib
from dataclasses import dataclass, field
from typing import Optional
import threading

BLOCK_SIZE = 16  # tokens per KV block

@dataclass
class KVBlock:
    block_id: int
    token_hash: str           # SHA-256 of the 16 token IDs this block covers
    ref_count: int = 0
    last_used_ns: int = 0
    recompute_cost_ms: float = 0.0  # estimated GPU time to recompute this block
    gpu_ptr: int = 0          # physical HBM pointer

@dataclass
class RadixNode:
    token_hash: str
    block: Optional[KVBlock] = None
    children: dict = field(default_factory=dict)  # token_hash -> RadixNode

class KVBlockManager:
    def __init__(self, total_blocks: int):
        self.total_blocks = total_blocks
        self.free_blocks: list[int] = list(range(total_blocks))
        self.blocks: dict[int, KVBlock] = {}
        self.root = RadixNode(token_hash="root")
        self.lock = threading.RLock()

    def _hash_tokens(self, token_ids: list[int]) -> str:
        return hashlib.sha256(
            bytes(t.to_bytes(4, 'little') for t in token_ids)
        ).hexdigest()[:16]

    def lookup_prefix(self, token_ids: list[int]) -> tuple[int, list[KVBlock]]:
        """Returns (matched_token_count, list_of_matched_blocks)."""
        with self.lock:
            matched_blocks = []
            node = self.root
            offset = 0
            while offset + BLOCK_SIZE <= len(token_ids):
                chunk = token_ids[offset:offset + BLOCK_SIZE]
                h = self._hash_tokens(chunk)
                if h not in node.children:
                    break
                child = node.children[h]
                if child.block is None:
                    break
                child.block.ref_count += 1
                matched_blocks.append(child.block)
                node = child
                offset += BLOCK_SIZE
            return offset, matched_blocks

    def insert_block(self, token_ids: list[int], offset: int, block_id: int,
                     gpu_ptr: int, recompute_cost_ms: float) -> KVBlock:
        """Register a newly computed KV block in the radix tree."""
        with self.lock:
            chunk = token_ids[offset:offset + BLOCK_SIZE]
            h = self._hash_tokens(chunk)
            block = KVBlock(
                block_id=block_id,
                token_hash=h,
                ref_count=1,
                gpu_ptr=gpu_ptr,
                recompute_cost_ms=recompute_cost_ms,
            )
            node = self._navigate_to(token_ids, offset)
            node.children[h] = RadixNode(token_hash=h, block=block)
            self.blocks[block_id] = block
            return block

    def release_block(self, block: KVBlock):
        with self.lock:
            block.ref_count -= 1

    def evict_candidates(self, n: int) -> list[KVBlock]:
        """Return n lowest-value unreferenced blocks for eviction.
        Value = recompute_cost_ms / (time_since_last_use_s + 1).
        Evict low-value blocks first."""
        with self.lock:
            candidates = [
                b for b in self.blocks.values() if b.ref_count == 0
            ]
            candidates.sort(key=lambda b: b.recompute_cost_ms / 1.0)
            return candidates[:n]

    def _navigate_to(self, token_ids: list[int], target_offset: int) -> RadixNode:
        node = self.root
        offset = 0
        while offset < target_offset:
            chunk = token_ids[offset:offset + BLOCK_SIZE]
            h = self._hash_tokens(chunk)
            if h not in node.children:
                node.children[h] = RadixNode(token_hash=h)
            node = node.children[h]
            offset += BLOCK_SIZE
        return node

The Conversation Router

The router’s job is to make one decision per request: which replica owns the warmest cache for this conversation, and is the transfer cost to a colder replica worth avoiding?

The naive approach - round-robin load balancing - sends each turn to a random replica. Cache hit rate approaches zero even when the cluster has plenty of cached blocks. This is the single most common mistake in multi-turn deployments.

The correct approach is consistent hashing keyed on the session’s prefix hash. The session prefix hash is a rolling hash of the complete token sequence for the conversation up to the current turn. All turns that share a common prefix route to the same replica, which is exactly where the cached blocks live.

# Conversation router: consistent hashing with prefix-aware placement
import hashlib
from bisect import bisect_left, insort

class PrefixAwareRouter:
    def __init__(self, replicas: list[str], virtual_nodes: int = 150):
        self.ring: list[tuple[int, str]] = []
        self.replicas = set(replicas)
        for replica in replicas:
            for i in range(virtual_nodes):
                key = int(hashlib.md5(f"{replica}:{i}".encode()).hexdigest(), 16)
                insort(self.ring, (key, replica))

    def route(self, prefix_hash: str, cache_index: 'CacheIndex') -> str:
        """Route to warm replica if hit rate delta justifies it, else consistent hash."""
        warm_replica = cache_index.find_warm_replica(prefix_hash)
        if warm_replica:
            warm_hit_rate = cache_index.hit_rate(warm_replica, prefix_hash)
            consistent_replica = self._consistent_hash(prefix_hash)
            if consistent_replica == warm_replica or warm_hit_rate > 0.6:
                return warm_replica
        return self._consistent_hash(prefix_hash)

    def _consistent_hash(self, key: str) -> str:
        h = int(hashlib.md5(key.encode()).hexdigest(), 16)
        pos = bisect_left(self.ring, (h, ""))
        if pos >= len(self.ring):
            pos = 0
        return self.ring[pos][1]

    def add_replica(self, replica: str, virtual_nodes: int = 150):
        self.replicas.add(replica)
        for i in range(virtual_nodes):
            key = int(hashlib.md5(f"{replica}:{i}".encode()).hexdigest(), 16)
            insort(self.ring, (key, replica))

    def remove_replica(self, replica: str, virtual_nodes: int = 150):
        self.replicas.discard(replica)
        for i in range(virtual_nodes):
            key = int(hashlib.md5(f"{replica}:{i}".encode()).hexdigest(), 16)
            idx = bisect_left(self.ring, (key, replica))
            if idx < len(self.ring) and self.ring[idx] == (key, replica):
                del self.ring[idx]

The Block Transfer Agent

When a conversation’s KV blocks are on replica A but the router has decided to send the next turn to replica B (because A is overloaded), the Block Transfer Agent migrates the blocks over NVLink or InfiniBand rather than forcing a full recompute on B.

Transfer over NVLink at 600 GB/s means moving a 100-block (1,600-token) cache takes about 0.8ms for a Llama-3 70B model in BF16 (100 blocks * 16 tokens * 80 layers * 8 KV heads * 128 dim * 2 bytes * 2 K/V = ~3.3 GB… actually let me do this more carefully).

For Llama-3 70B with GQA: 80 transformer layers, 8 KV heads per layer, head dim 128. KV cache per token per layer = 2 * 8 * 128 * 2 bytes (BF16) = 4,096 bytes. For 100 blocks of 16 tokens: 100 * 16 * 80 * 4,096 bytes = 524 MB. Over 600 GB/s NVLink: ~0.87ms. Under our 5ms SLA.

Over InfiniBand (200 Gb/s = 25 GB/s), the same transfer takes 21ms - over SLA. This means cross-node KV transfer is only viable within a single NVLink domain (8 GPUs on one A100 server). Cross-node transfers should trigger recompute, not migration.

# Block Transfer Agent: async KV block migration over NVLink
import asyncio
import torch
from typing import Optional

class BlockTransferAgent:
    def __init__(self, local_replica_id: str, nvlink_peers: list[str]):
        """nvlink_peers: replicas reachable via NVLink (same node)."""
        self.local_id = local_replica_id
        self.nvlink_peers = set(nvlink_peers)
        self.transfer_budget_bytes_per_s = 600 * 1024**3  # 600 GB/s NVLink

    async def fetch_blocks(
        self,
        source_replica: str,
        block_ids: list[int],
        destination_gpu_ptrs: list[int],
        timeout_ms: float = 5.0,
    ) -> bool:
        """Fetch KV blocks from source replica into local GPU memory.
        Returns True on success, False on timeout (caller should recompute)."""
        if source_replica not in self.nvlink_peers:
            # Cross-node: too slow, skip transfer
            return False

        estimated_bytes = len(block_ids) * self._bytes_per_block()
        estimated_ms = (estimated_bytes / self.transfer_budget_bytes_per_s) * 1000
        if estimated_ms > timeout_ms:
            return False

        try:
            await asyncio.wait_for(
                self._do_nvlink_transfer(source_replica, block_ids, destination_gpu_ptrs),
                timeout=timeout_ms / 1000,
            )
            return True
        except asyncio.TimeoutError:
            return False

    async def _do_nvlink_transfer(self, source: str, block_ids: list[int],
                                   dst_ptrs: list[int]):
        # In production: use NCCL P2P or cuMemcpy across GPU device IDs
        # Here we show the PyTorch equivalent for the same-node case
        for block_id, dst_ptr in zip(block_ids, dst_ptrs):
            src_tensor = self._get_remote_block_tensor(source, block_id)
            dst_tensor = torch.frombuffer(
                (ctypes.c_uint8 * src_tensor.nbytes).from_address(dst_ptr),
                dtype=torch.bfloat16,
            )
            dst_tensor.copy_(src_tensor, non_blocking=True)
        torch.cuda.synchronize()

    def _bytes_per_block(self) -> int:
        # Llama-3 70B, GQA: 80 layers, 8 KV heads, 128 head_dim, BF16, 16 tokens
        return 16 * 80 * 8 * 128 * 2 * 2  # 2 for K and V

    def _get_remote_block_tensor(self, replica_id: str, block_id: int) -> torch.Tensor:
        # In production: IPC handle shared via shared memory or gRPC
        raise NotImplementedError("replaced by NCCL IPC in production")

Data Model

The Cache Index needs to be fast (sub-millisecond lookups), durable enough to survive replica restarts, and consistent enough that two replicas never claim ownership of the same block set.

-- Cache index: prefix ownership registry in PostgreSQL (used for durable metadata)
-- Hot path uses Redis for sub-ms lookups; Postgres is the source of truth

CREATE TABLE kv_prefix_registry (
    prefix_hash       VARCHAR(16)  NOT NULL,   -- first 16 chars of SHA-256 of token seq
    replica_id        VARCHAR(64)  NOT NULL,
    block_start_idx   INTEGER      NOT NULL,   -- logical block index in conversation
    block_count       INTEGER      NOT NULL,
    token_count       INTEGER      NOT NULL,
    model_version     VARCHAR(32)  NOT NULL,   -- prefix invalid if model changes
    created_at        TIMESTAMPTZ  NOT NULL DEFAULT NOW(),
    last_hit_at       TIMESTAMPTZ,
    hit_count         BIGINT       NOT NULL DEFAULT 0,
    recompute_cost_ms FLOAT        NOT NULL DEFAULT 0,
    PRIMARY KEY (prefix_hash, replica_id),
    CONSTRAINT fk_replica FOREIGN KEY (replica_id) REFERENCES replicas(replica_id)
);

CREATE INDEX idx_prefix_hash ON kv_prefix_registry (prefix_hash);
CREATE INDEX idx_replica_last_hit ON kv_prefix_registry (replica_id, last_hit_at DESC);

CREATE TABLE kv_blocks (
    block_id          BIGSERIAL    PRIMARY KEY,
    prefix_hash       VARCHAR(16)  NOT NULL,
    block_seq_idx     INTEGER      NOT NULL,   -- position in the prefix (0, 1, 2, ...)
    token_hash        VARCHAR(16)  NOT NULL,   -- hash of the 16 tokens in this block
    replica_id        VARCHAR(64)  NOT NULL,
    gpu_ptr           BIGINT,                  -- physical HBM address (null if evicted)
    evicted_at        TIMESTAMPTZ,
    UNIQUE (prefix_hash, block_seq_idx, replica_id)
);

-- Session context: tracks rolling prefix hash for each active conversation
CREATE TABLE session_state (
    session_id        UUID         PRIMARY KEY,
    current_prefix_hash VARCHAR(16) NOT NULL,
    turn_count        INTEGER      NOT NULL DEFAULT 0,
    token_count       INTEGER      NOT NULL DEFAULT 0,
    assigned_replica  VARCHAR(64),
    context_tokens    INTEGER[]    NOT NULL,  -- full token sequence (up to 8192)
    last_active_at    TIMESTAMPTZ  NOT NULL DEFAULT NOW(),
    model_version     VARCHAR(32)  NOT NULL
);

CREATE INDEX idx_session_replica ON session_state (assigned_replica);
CREATE INDEX idx_session_active ON session_state (last_active_at DESC);

For the hot path, the Redis data model mirrors the critical lookup path:

# Redis hot-path schema

# Prefix -> warm replica mapping (TTL = 300s)
HSET prefix:{prefix_hash} replica_id {replica_id} block_count {n} hit_count {k}
EXPIRE prefix:{prefix_hash} 300

# Replica load and capacity (updated every 1s by health heartbeat)
HSET replica:{replica_id} free_blocks {n} total_blocks {m} active_sessions {k}

# Session sticky assignment (TTL = 1800s, refreshed on each turn)
SET session:sticky:{session_id} {replica_id} EX 1800

Key Algorithms and Protocols

Rolling Prefix Hash

The prefix hash for a conversation must be computed incrementally - you cannot re-hash the full token sequence on every turn. The rolling hash appends each new turn’s token IDs to a running SHA-256 state.

# Rolling prefix hash: incremental SHA-256 state across turns
import hashlib
import struct

class RollingPrefixHasher:
    """Maintains a rolling hash that extends cheaply with each new turn."""
    def __init__(self):
        self._state = hashlib.sha256()
        self._turn_snapshots: list[str] = []  # hash at end of each turn

    def extend(self, token_ids: list[int]) -> str:
        """Add a new turn's tokens. Returns the new prefix hash."""
        for tid in token_ids:
            self._state.update(struct.pack('<I', tid))
        h = self._state.copy().hexdigest()[:16]
        self._turn_snapshots.append(h)
        return h

    def hash_at_turn(self, turn_idx: int) -> str:
        """Return the prefix hash at the end of turn turn_idx."""
        return self._turn_snapshots[turn_idx]

    def reset(self):
        self._state = hashlib.sha256()
        self._turn_snapshots = []

Eviction Policy: Cost-Aware LRU

Standard LRU evicts the block that was accessed least recently. This is wrong for KV caches because a 200-token block and a 4,000-token block have the same size but vastly different recompute costs. We need cost-aware eviction: prioritize keeping blocks whose recompute cost is high relative to how long they’ve been idle.

# Cost-aware eviction: combines LRU with recompute cost weight
import time
from heapq import heappush, heappop

class CostAwareLRU:
    def __init__(self, capacity_blocks: int):
        self.capacity = capacity_blocks
        self.cache: dict[str, KVBlock] = {}
        self.heap: list[tuple[float, str]] = []  # (priority, token_hash)

    def _eviction_priority(self, block: KVBlock) -> float:
        """Lower = evict sooner. Score = recompute_cost_ms / idle_seconds."""
        idle_s = (time.time_ns() - block.last_used_ns) / 1e9 + 1e-6
        return block.recompute_cost_ms / idle_s

    def touch(self, block: KVBlock):
        block.last_used_ns = time.time_ns()
        priority = self._eviction_priority(block)
        heappush(self.heap, (priority, block.token_hash))

    def evict_one(self) -> Optional[KVBlock]:
        while self.heap:
            priority, token_hash = heappop(self.heap)
            if token_hash not in self.cache:
                continue
            block = self.cache[token_hash]
            if block.ref_count > 0:
                # Block in use: reinsert with updated priority
                heappush(self.heap, (self._eviction_priority(block), token_hash))
                continue
            del self.cache[token_hash]
            return block
        return None

Partial Prefix Hit Handling

A request with a 3,000-token history might have the first 2,560 tokens cached (160 blocks) and the last 440 tokens uncached (28 blocks uncached). The prefill worker must run the forward pass only on the 440 uncached tokens, but it needs the 160 cached KV blocks in HBM to attend over during this partial prefill.

# Partial prefix hit: schedule prefill only for uncached suffix
@dataclass
class PrefillJob:
    session_id: str
    full_token_ids: list[int]
    cached_block_count: int          # blocks already in HBM
    cached_kv_blocks: list[KVBlock]  # references (keeps ref_count > 0)
    uncached_token_ids: list[int]    # only these need forward pass

async def schedule_prefill(
    session_id: str,
    full_token_ids: list[int],
    block_manager: KVBlockManager,
) -> PrefillJob:
    matched_count, matched_blocks = block_manager.lookup_prefix(full_token_ids)

    uncached_start = matched_count
    uncached_tokens = full_token_ids[uncached_start:]

    return PrefillJob(
        session_id=session_id,
        full_token_ids=full_token_ids,
        cached_block_count=len(matched_blocks),
        cached_kv_blocks=matched_blocks,
        uncached_token_ids=uncached_tokens,
    )

Scaling and Performance

The system scales horizontally for compute but not for cache. Each GPU replica holds a fixed amount of HBM. When you add replicas, you add compute capacity but you also fragment the cache - a conversation that was warm on replica 1 is cold on replica 5. Sticky routing partially solves this, but as the replica pool grows, the fraction of conversations that can stay on their assigned replica shrinks due to replica load imbalance.

Capacity estimation:

Llama-3 70B in BF16, 4xA100 80GB per replica (320 GB total HBM):
- Model weights (tensor-parallel): 70B * 2 bytes = 140 GB -> 35 GB per GPU
- Remaining HBM per GPU: 80 - 35 = 45 GB
- KV cache per token: 80 layers * 8 KV heads * 128 dim * 2 bytes * 2 (K+V) = 327,680 bytes (~320 KB)
  Wait - this is per token. Let's be precise:
  each layer: 2 (K+V) * 8 heads * 128 dim * 2 bytes (BF16) = 4,096 bytes/token/layer
  80 layers: 4,096 * 80 = 327,680 bytes per token = 320 KB per token
- KV cache per 8,192-token context: 8,192 * 320 KB = 2.56 GB per GPU (tensor-parallel shares heads)
  With GQA: 8 KV heads replicated across 4 GPUs -> 2 KV heads per GPU
  Revised: 2 heads * 128 dim * 2 bytes * 2 * 80 layers * 8192 tokens = 640 MB per GPU
- Available for KV cache (30% HBM budget): 0.30 * 45 GB = 13.5 GB per GPU
- Max concurrent full-context sessions per GPU: 13.5 GB / 640 MB = ~21 sessions
- Per replica (4 GPUs): ~84 sessions at full 8K context
- 50,000 concurrent sessions at average 2K context (640 MB * 2048/8192 = 160 MB):
  Per GPU: 13.5 GB / 160 MB = 84 sessions
  Per replica: 336 sessions
  Replicas needed: 50,000 / 336 = ~149 replicas (596 A100 GPUs)

With 70% cache hit rate (only 30% sessions need full prefill on each turn):
- Effective throughput gain: 3.3x on prefill-dominated workloads
- Net replicas needed with caching: ~45 replicas (180 A100 GPUs)
- Cost reduction: 69% fewer GPUs needed

Horizontal scaling works by adding replicas and rebalancing consistent hashing. When a new replica joins, the consistent hash ring shifts a fraction of sessions to the new node. Those sessions take one cold turn (full recompute) before the cache warms up. This is acceptable - it’s not a cache stampede because only the fraction of sessions remapped to the new node experience the cold turn.

The bottleneck is not GPU compute but HBM fragmentation at high replica counts. With 200 replicas, a single session’s prefix blocks are spread thinly - sticky routing concentrates load on a few “hot” replicas while others sit cold. The Eviction Oracle monitors this and signals cross-replica block migration to rebalance.

Cost and Token Economics

KV cache sharing changes the economics of multi-turn inference fundamentally because prefill is compute-bound and decode is memory-bandwidth-bound. Eliminating redundant prefill directly reduces GPU-hours.

Configuration	TTFT p50	Cost per 1M input tokens	Notes
No caching, round-robin	820ms	$4.80	All prefill, every turn
Prefix cache, sticky routing	78ms	$1.45	70% hit rate
Prefix cache + system prompt pin	62ms	$1.18	System prompt never recomputed
Semantic cache (fuzzy match)	55ms	$0.94	Separate vector similarity layer

The biggest single optimization is system prompt pinning. If your system prompt is 2,000 tokens and you serve 10,000 sessions per hour, naive serving spends 20 million token-prefill operations per hour just on the system prompt. At $0.002/1K input tokens that’s $40/hour in system prompt alone. Pin the system prompt - compute it once per model version, keep it permanently in HBM, and zero that cost.

The second optimization is turn-level caching with sliding window. When a conversation exceeds the context window (8,192 tokens), a naive implementation evicts all blocks and restarts prefill from the beginning. A better approach keeps the most recent 4,096 tokens in HBM and evicts the oldest 4,096 - the cache hit on the recent half saves 50% of prefill cost even past the context window limit.

Quality, Evaluation, and Guardrails

AI caching is uniquely dangerous because incorrect cache hits are silent - the model returns a response, but it’s the response to a different conversation’s context. The quality gate is bit-exact correctness: the output of a cache-assisted request must be numerically identical to the output of a fully recomputed request.

# Cache correctness validator: run in shadow mode during rollout
import torch
import numpy as np

async def shadow_validate_cache_hit(
    session_id: str,
    full_token_ids: list[int],
    cached_response_logits: torch.Tensor,
    prefill_worker: 'PrefillWorker',
    tolerance: float = 1e-5,
) -> bool:
    """During shadow validation: recompute from scratch and compare logits."""
    fresh_logits = await prefill_worker.full_prefill(full_token_ids)
    max_diff = (cached_response_logits - fresh_logits).abs().max().item()
    if max_diff > tolerance:
        # Log and alert - this indicates a cache corruption or hash collision
        import logging
        logging.error(
            "Cache correctness violation for session %s: max_logit_diff=%.6f",
            session_id, max_diff
        )
        return False
    return True

Offline eval: run the full test suite of multi-turn dialogues through the caching layer and compare outputs token-by-token against a reference (no-cache) run. A correctness rate below 99.999% means a hash collision or memory alignment bug.

Online signals: track “regeneration rate” per session - if users click regenerate more than 2% of the time on cached responses vs 1.5% on cold responses, there’s a quality regression in cache hit selection.

Guardrails on the cache path:

• Block hash collisions: SHA-256 first 16 chars gives 1 in 18 quintillion collision probability - acceptable. Use full 32 chars for the database record, short form for Redis.
• Model version mismatch: every cached block stores the model version it was computed with. Block is invalid if served to a different model version.
• Context window overflow: never serve a cached block for a prefix longer than max_model_len - max_new_tokens. Blocks computed near the context limit may have degraded attention quality.
• Token ID stability: the tokenizer must be frozen. A tokenizer update invalidates the entire cache.

Failure Modes and Recovery

Failure	Detection	Impact	Recovery
KV Block Manager OOM on replica	free_blocks == 0 alert from health heartbeat	New requests on that replica forced to full recompute; no data loss	Trigger aggressive eviction of low-value blocks; temporarily redirect sticky sessions to neighbor replicas
Redis Cache Index unavailable	Health check failure + request latency spike	Router cannot find warm replicas; all requests go cold	Fall back to consistent hashing on session_id without cache lookup; 0% cache hit but service continues
Hash collision (SHA-256 truncated)	Shadow validation detects logit divergence > 1e-5	One corrupted response per ~18 quintillion requests	Extend prefix hash to full 64 chars; purge affected block from radix tree
Replica restart / GPU fault	Health heartbeat timeout	Cache on that replica lost; sticky sessions re-routed cold for one turn	Reroute sessions to a warm neighbor if NVLink transfer is under 5ms; else accept one cold turn and rebuild
Model version rollout cache invalidation	Model version field mismatch in block lookup	Stale blocks could produce wrong outputs if not invalidated	On model version change: broadcast cache invalidation event to all KV Block Managers; they purge all blocks atomically before accepting new traffic
Context window exceeded mid-session	token_count > max_model_len - buffer check at router	Without handling, truncation silently drops early turns from context	Activate sliding window: evict oldest N blocks, adjust prefix hash to reflect new context start

Comparison of Approaches

Approach	TTFT (p50)	Cache Hit Rate	GPU Memory Overhead	Failure Mode	Best Fit
No caching, round-robin	820ms	0%	None	N/A - baseline	Single-turn or stateless requests
Per-replica radix cache, sticky routing	78ms	65-75%	30% HBM per replica	Session imbalance under replica churn	Multi-turn chatbots, standard production
Distributed shared KV store (CPU RAM)	180ms	80-85%	Minimal HBM; large CPU RAM	Transfer latency; PCIe bottleneck at scale	Cost-sensitive, latency-tolerant workloads
Cross-replica NVLink block migration	68ms	78-82%	30% HBM + transfer buffer	Only works within NVLink domain (8 GPUs)	High-density single-node deployments
Semantic cache (fuzzy prefix match)	55ms	85-90%	+ 5% for embedding index	False hits on semantically similar but different prompts	Q&A systems with templated prompts

The right default for a production multi-turn chatbot is per-replica radix cache with sticky routing. It requires no cross-replica infrastructure, adds minimal operational complexity, and delivers 65-75% cache hit rate which eliminates the majority of prefill cost. Move to NVLink block migration only when you have very long conversations (8K+ context) and can guarantee sessions land on the same 8-GPU node.

Distributed shared KV on CPU RAM sounds attractive because it gives you a single large cache pool, but PCIe bandwidth (64 GB/s) is the killer - loading 524 MB of KV blocks from CPU to GPU over PCIe takes 8ms, blowing your TTFT SLA. This is why NVLink (600 GB/s) is a prerequisite for any cross-device KV sharing.

Key Takeaways

• Sticky routing is the prerequisite for any prefix caching to work - without it, cache hit rate is near zero regardless of how much HBM you dedicate to the cache.
• KV blocks must be fixed-size (16 tokens is standard) to enable efficient memory management; variable-size blocks create fragmentation that ruins HBM utilization.
• Hash on token IDs, not text - tokenization is not deterministic across context variations and the KV activations are a function of token IDs, not the original string.
• System prompt pinning is the single highest-leverage optimization - one config change that eliminates billions of redundant prefill tokens per day.
• NVLink boundary is the hard limit for live KV block migration; cross-node migration is only viable for batch/async workloads where latency SLA is relaxed.
• Model and tokenizer version must both be stored in every cached block - a tokenizer patch without cache invalidation produces silently wrong multi-turn responses.
• Cost-aware eviction outperforms standard LRU because KV blocks have wildly different recompute costs; evicting a 4,000-token block to free space for a 16-token block is a terrible trade.
• Partial prefix hits are the common case, not full hits - your prefill worker must handle “cache hit on first 80% of context” gracefully without recomputing the already-cached prefix.

The counter-intuitive lesson in this design is that adding memory does not directly improve cache hit rate. Hit rate is dominated by routing policy. A cluster with 50% less HBM but perfect sticky routing will outperform a cluster with double the HBM and random routing. The cache is only as useful as your ability to route requests to where the cache lives.

Frequently Asked Questions

Q: Why not use a single large shared memory pool (like Redis) for KV blocks instead of per-replica HBM?

A: Because the bottleneck for KV block access is bandwidth, not storage. GPU HBM bandwidth is 2 TB/s. PCIe (CPU-GPU) is 64 GB/s. Loading a 500 MB KV context from CPU RAM takes 8ms over PCIe - that’s your entire TTFT budget before the model even runs a single forward pass. Redis is only viable if you accept much higher TTFT SLAs (200ms+) or use it as a warm-up store that gets pre-loaded into GPU HBM before the request arrives.

Q: Why not just use a larger context window to avoid KV cache management entirely?

A: Larger context windows make the problem worse, not better. A 128K-token context window requires 40 GB of GPU HBM per active session on Llama-3 70B - one session fills half an A100. KV cache management exists precisely because context windows are growing faster than GPU memory. The engineering problem only becomes more severe as context length increases.

Q: How do you handle cache hit rate evaluation in production - you can’t compare every cached response to a fresh recompute?

A: You don’t compare outputs in steady state - you validate bit-exactness in shadow mode during rollout (10% of traffic, for 24 hours) and then rely on proxy metrics: TTFT distribution, user regeneration rate, and block hash collision rate. A sudden spike in p99 TTFT (cache misses) or regeneration rate indicates a quality regression in cache selection logic.

Q: What’s the right KV block size - why 16 tokens?

A: 16 tokens is the vLLM default and a reasonable balance: small enough that two conversations sharing a system prompt but diverging early don’t waste many cache blocks on the diverged portion; large enough that the overhead of block metadata and hash lookups doesn’t dominate at short context lengths. Experiments with 8-token blocks show diminishing returns on hit rate while doubling radix tree depth. 32-token blocks miss sharing opportunities on short common prefixes. 16 is the empirical sweet spot.

Q: Can KV caching help with cost on API-based LLMs like GPT-4 or Claude, or is this only for self-hosted?

A: Both Anthropic and OpenAI offer prompt caching at the API level (Anthropic charges 10% of input token price for cache hits; OpenAI charges 50%). These are essentially managed versions of this same prefix caching mechanism. Self-hosted lets you tune block size, eviction policy, and routing to your exact workload; API caching gives you the benefit without the operational complexity but with less control over cache granularity.

Q: How do you handle a model update that invalidates the entire cache - do all sessions go cold simultaneously?

A: Yes, unless you run the new model version as a shadow deployment and warm its cache before cutover. The standard pattern is: deploy the new model version alongside the old one for 30-60 minutes, route 10% of traffic to the new version to warm its KV cache, then cut over. The cache on the new version will have hit rates around 40-50% at cutover rather than 0%, dramatically reducing the TTFT spike that users experience during model updates.

Interview Questions

Q: Design the routing layer for a multi-turn LLM chat system serving 100,000 concurrent sessions across 50 model replicas. How do you maximize KV cache hit rate while keeping per-replica load balanced?

Expected depth: Discuss consistent hashing on session prefix hash vs. session ID; why prefix hash enables sharing between sessions with common prefixes (e.g., same system prompt); load imbalance between hot sessions (long conversations) and cold sessions; rebalancing via session migration; the tradeoff between cache hit rate (favors sticky routing) and load balance (favors work stealing); quantify the expected hit rate improvement from sticky vs. random routing.

Q: Walk through the memory math for KV cache on a Llama-3 70B model. How many concurrent 8K-token sessions can a single 4xA100 80GB replica serve?

Expected depth: Walk through: model weights in BF16 = 140 GB distributed across 4 GPUs = 35 GB/GPU; remaining HBM = 45 GB/GPU; KV cache per token per GPU with GQA (8 KV heads, 80 layers, 128 dim, BF16) = 2 heads/GPU * 128 * 2 * 80 * 2 bytes = 81,920 bytes/token; full 8K context per GPU = 640 MB; available KV HBM = 13.5 GB/GPU; max full-context sessions/GPU = ~21; discuss why GQA dramatically reduces KV cache size vs MHA.

Q: You see that KV cache hit rate has dropped from 72% to 31% after adding 10 new replicas to the cluster. What are the likely causes and how do you debug?

Expected depth: Consistent hash ring rebalancing remapped sessions to new replicas (expected); sticky routing may not be correctly keying on prefix hash (bug); new replicas started cold and haven’t warmed yet (transient); session affinity TTL in Redis expired during rollout (config); discuss how to distinguish between these by examining per-replica hit rate histograms, routing decision logs, and cache miss reason codes.

Q: How does partial prefix caching work when a conversation’s context changes because the model’s context window fills up and old tokens get truncated?

Expected depth: When sliding window truncation happens, the prefix hash changes (different starting token); blocks for the evicted early turns become orphaned; the new prefix (starting at token 4096) has no cached blocks even if the recent turns were cached; discuss strategies: always keep the most recent N blocks cached regardless of prefix alignment; use an anchor point (e.g., always align block boundaries to turn boundaries) so truncation only invalidates full turns rather than partial blocks; discuss why turn-aligned block boundaries outperform fixed-16-token boundaries for conversation truncation.

Q: What are the correctness risks of KV caching, and how do you prove that a cache-assisted forward pass produces bit-identical outputs to a fresh computation?

Expected depth: Hash collision risk (quantify: SHA-256 truncated to 16 hex chars = 64 bits, probability 1/2^64 per lookup); numerical precision: BF16 KV blocks stored and loaded are bit-identical by construction (no floating point operations on the cache path); context window boundary effects: attention scores near the end of a cached block may differ if the attention mask changes (discuss causal mask consistency); temperature and sampling: cache correctness is only about logits/hidden states, not sampled tokens (sampling is always fresh); shadow validation methodology for production rollout.