Prefix-Cache-Aware Routing and Cache Locality

Many generation workloads have a fixed head. A system instruction, a set of tool definitions, a retrieved document, or a conversation transcript that is replayed on every turn: all of these are tokens that the model processes identically for every request in a group. Prefill over that head is pure repetition. Computing it once and reusing the resulting keys and values removes work that grows linearly with the head’s length, which for a system prompt of a few thousand tokens is the dominant part of time-to-first-token.

Reuse is only possible if the request reaches the replica that holds the cache. Cache lives in accelerator memory attached to a specific process, and the block table that names it is per-sequence. A router that spreads requests uniformly across replicas guarantees that each replica must recompute the shared head, and the work saved by caching is multiplied by the number of replicas rather than divided by it.

The unit of reuse is a prefix, not a document

Causal attention makes the cache valid for any prefix of a sequence, and only for a prefix. Position i’s key and value depend on tokens 0..i, so a block of cache computed from tokens 0..255 is reusable by any request whose first 256 tokens are identical. A block computed from tokens 256..511 is reusable only if the first 256 tokens also match. The match is therefore a longest-common-prefix computation over token ids, not a set-membership test over chunks.

This constrains what can be cached usefully. Retrieved context inserted in the middle of a prompt is not a prefix for requests that differ before it, so a retrieval-augmented workload gains reuse only if the layout puts stable material first and variable material last. The ordering decision has real consequences: instructions, then tools, then documents, then the user turn. Any interleaving that varies early destroys the reuse of everything after it.

Block granularity applies on top of the token-prefix rule. If cache is stored in blocks of 16 tokens, a prefix match that ends mid-block cannot reuse the partial block without copying it. Reuse therefore rounds down to a block boundary, and a prompt whose stable head is 1,010 tokens with 16-token blocks reuses 1,008 tokens.

How the lookup works

A replica that supports prefix caching maintains an index from a hash of a block’s token ids, together with its parent block’s hash, to the physical block. Hashing each block’s tokens in isolation is insufficient: two different prefixes can contain the same 16 tokens, and reusing the block would produce attention over the wrong history. Chaining the parent hash into the child’s key makes each entry name a unique prefix path.

def block_keys(tokens, block_size, base=0):
    keys = []
    parent = base
    for i in range(0, len(tokens), block_size):
        chunk = tokens[i:i + block_size]
        if len(chunk) < block_size:
            break  # partial tail blocks are not indexed
        # chaining the parent hash makes each key name a unique prefix path
        parent = hashlib.blake2b(
            parent.to_bytes(8, "little") + b"".join(t.to_bytes(4, "little") for t in chunk),
            digest_size=8,
        ).digest()
        keys.append(parent)
    return keys

An incoming request computes its chain of keys, walks the index, and stops at the first miss. The matched blocks are attached to the new sequence’s table with reference counts incremented, and prefill begins at the first unmatched position. Nothing is copied; the indirection described in Paged KV Cache does the work.

The eviction side needs care. Indexed blocks are shared, so they cannot be freed on a least-recently-used basis while a live sequence references them. A common arrangement keeps a separate pool for cached-but-unreferenced blocks and evicts from that pool, leaving blocks that any active sequence names untouched. Eviction from the shared pool must also remove the index entry, or a later lookup returns a block that has been reassigned.

Routing on affinity against routing on load

A prefix-aware router scores each replica by the length of the prefix it can serve from cache, and sends the request where that length is greatest. A load-aware router scores by outstanding work and sends the request where that is smallest. The two objectives conflict, and the conflict is not marginal.

Consider two replicas. Replica A holds the 4,000-token shared system prompt and has 30 sequences in flight. Replica B holds nothing and has 5 sequences. Sending to A costs prefill over the variable tail only, perhaps 200 tokens, but adds to a busy queue. Sending to B costs prefill over 4,200 tokens and adds to an idle queue. The comparison reduces to whether the saved prefill exceeds the added queueing delay. For a head of several thousand tokens the saving is large: prefill over 4,000 positions is tens of milliseconds of exclusive accelerator work, while the marginal decode cost of one more sequence in a batch of 30 is a fraction of a decode step. Affinity wins in that regime. For a head of 200 tokens the saving is small, and load should win.

Practical routers implement this as a weighted score: affinity measured in saved tokens, load measured in outstanding tokens, with a coefficient that sets how many outstanding tokens one cached token is worth. The coefficient is a tuning constant with no universal value, and stating it as a fixed number in a configuration file hides a policy decision about latency versus throughput.

A second design avoids the conflict by partitioning rather than by scoring. Each replica owns a subset of cacheable prefixes, and requests are hashed to the owner. Load imbalance then comes from the popularity distribution of prefixes rather than from arrival order, and a hot prefix concentrates on one replica. Replicating the hottest prefixes across several replicas is the usual mitigation, which trades cache memory for balance.

Costs that the saving conceals

Cache memory is finite and shared with the sequences currently generating. A replica that dedicates a large fraction of its blocks to idle-but-indexed prefixes has fewer blocks for live work, so the effective batch size falls and throughput with it. The trade is direct: a cached head of 8,000 tokens at 128 KiB per token is 1 GiB, which on a 40 GiB cache is 2.5 percent per distinct head, and a replica holding twenty distinct heads loses half its capacity.

Invalidation is the second cost. Cache entries are keyed by token ids only, so a change to the model’s weights invalidates all of them, and a change to the tokenizer changes the ids and invalidates them just as thoroughly. Rolling out a new model version therefore starts with a cold cache on every replica, which is why warm-up traffic exists in Autoscaling Signals for Token Servers.

The third cost is the security boundary. A block is reusable by any request with a matching token prefix, which means a request can observe whether a prefix is cached by measuring its own time-to-first-token. That timing channel leaks the existence of prompts, and the standard mitigations are per-tenant cache namespaces and disabling cross-request reuse for untrusted traffic. Sharing cache across tenants is a performance decision that must be made deliberately, not a default.

Where locality stops mattering

Prefix reuse pays when the shared head is long relative to the variable part and when the same head recurs often. Workloads with unique prompts per request gain nothing and pay the memory cost of an index that never hits. Workloads with a short system prompt gain little and pay the routing complexity.

Between those extremes, the decisive quantity is the ratio of saved prefill to the queueing delay the affinity decision adds. That ratio depends on model size, head length, and arrival rate, and it changes as the fleet scales: with many replicas, the probability that a request’s prefix is cached anywhere falls, so affinity routing becomes a matter of steering requests to the few replicas that hold popular heads, which is closer to content-based partitioning than to load balancing. The scheduler-level consequences of concentrating traffic that way are covered in Deadline-Aware Batching and Tenant Fairness.