Prefix Caching and Request Routing

Two mechanisms operating at different layers of the serving stack often get lumped together under "prefix-aware." Local prefix caching decides whether a single engine instance can reuse KV blocks already in its memory pool. Distributed cache-aware routing decides which replica or shared cache tier should receive an incoming request. Neither layer replaces the other: a router cannot manufacture a cache hit that the destination engine rejects on compatibility checks, and an engine cannot reuse blocks sitting on another replica without cross-node transfer or shared storage.

This tutorial separates those two layers, works through a five-turn conversation reuse calculation, simulates the trade-off between cache affinity and replica load skew, and builds cache-compatibility and multi-tenant isolation checks.

Layer A: Local Automatic Prefix Caching

Exact Prefix Reuse

Under causal attention, a token's K/V state depends on the exact preceding token sequence and positions that produced it. Two prompts that look identical after rendering can still tokenize differently, and changing a chat template, model revision, adapter (such as a LoRA), positional parameters, KV dtype or layout, or multimodal input can make blocks incompatible.

vLLM's automatic prefix caching chains block hashes over the block's token IDs, the parent block's hash, and extra keys such as LoRA IDs, multimodal input hashes, and cache salts, then reuses matching full blocks (vLLM Automatic Prefix Caching). vLLM V1 turned automatic prefix caching on by default, whereas the legacy V0 engine left it off (vLLM V1 alpha release). Current releases document the switch as --enable-prefix-caching / --disable-prefix-caching (vLLM engine arguments); because defaults and flag spellings have changed across releases, pin the engine version and set the flag explicitly in production configs.

RadixAttention

SGLang's RadixAttention retains KV state in a radix tree, matches the longest shared token prefix across requests, and evicts the least recently used leaves first. SGLang's reported up-to-6.4× throughput gain is a whole-system result on structured language-model-program workloads, combining RadixAttention with compressed finite-state-machine decoding and frontend parallelism, not a multiplier for RadixAttention in isolation (Zheng et al., NeurIPS 2024).

What Local Caching Can and Cannot Improve

A prefix hit skips prefill compute on the matched prefix tokens. Once the engine processes the unmatched suffix and enters autoregressive decode, local prefix caching does not speed up per-step generation of new output tokens directly, though cutting prefill load can reduce iteration interference and queue wait. Workloads with long shared prompts and comparatively short outputs therefore gain the most.

Worked Example: Five-Turn Conversation

Consider a five-turn travel-copilot session whose prompt grows as follows:

Assume each turn's rendered token sequence strictly extends the prior prompt plus assistant reply without chat-template edits, block eviction, or incompatible state changes, allowing the engine to reuse KV state from prior assistant tokens as well. Counting every prior prompt and assistant token gives the idealized upper bound:

fresh prefill by turn = [400, 200, 200, 250, 200]
total fresh tokens    = 1,250

reused prefix by turn = [0, 500, 800, 1,150, 1,500]
total reused tokens   = 3,950

total input tokens    = 400 + 700 + 1,000 + 1,400 + 1,700
                      = 5,200

reuse fraction        = 3,950 / 5,200
                      = 75.96%

Treat 3,950 as an idealized upper bound under the extension assumption, not a measured hit count. In a paged engine with 16-token full-block matching, where the final sampled token of each turn has no KV state yet, reusable full-block tokens per turn drop to [0, 496, 784, 1136, 1488], totaling 3,904 of 5,200 tokens (75.08%), while fresh prefill becomes [400, 204, 216, 264, 212] (1,296 tokens). Whether a replica actually gets those hits still depends on block retention, exact token matching, and routing placement.

Layer B: Distributed Cache-Aware Placement

Across multiple replicas, a request router needs a view of both prefix locality and replica load. That view may be:

• approximate, inferred at the router from recent routing history or character- or token-level prefix trees;

• event-driven, updated from engine KV-cache events that report block storage and eviction; or

• shared-tier, backed by a distributed KV store that several workers can access.

Ray Serve's PrefixCacheAffinityRouter (currently an alpha API) tracks a character-level prefix tree of prompts routed to each replica and guards against hotspots via imbalanced_threshold: with a finite value, the router falls back to Power-of-Two-Choices load balancing whenever the gap between the longest and shortest replica queues exceeds that threshold, while the documented default (infinity) never triggers that fallback (Ray prefix-aware routing). Research schedulers such as Preble and DualMap target this tension between cache affinity and load balance: pinning a popular prefix to one replica builds queues, while blind load balancing forfeits prefix reuse (Srivatsa et al., ICLR 2025; Yuan et al., ICLR 2026).

Separate Universal-Prefix Warm-Up from Steady State

Suppose 50 requests all share the same 200-token system prompt across five replicas with ample KV memory. Round-robin sends the first five requests to distinct replicas, warming each replica once, and the remaining 45 requests all hit locally. Concentrating all 50 requests on a single replica warms the prefix once and yields 49 hits instead of 45: a warm-up saving of only 4 × 200 = 800 prefill tokens before block rounding, bought by leaving four replicas idle and turning one replica into a hotspot. Once all five replicas are warm, round-robin hits on every later request without skew, and saved tokens alone do not establish a latency or capacity benefit.

Testing whether cache-aware routing helps in steady state therefore requires multiple skewed prefixes, constrained per-replica cache capacity, multi-turn session growth, or eviction churn rather than a single tiny system prompt that fits everywhere.

Freeze a Skewed Routing Trace

Model three replicas, each able to retain at most two distinct prefix families under LRU eviction. Prefix lengths are:

Request arrival sequence (20 requests):

A A B A C A B D A A C B A D A B C A B A

Compare three routing policies:

• round-robin, cycling through replicas 0, 1, 2;

• affinity-only, always picking a replica holding the prefix (breaking ties toward fewer cumulative assignments, and taking the least-assigned replica on a miss); and

• hybrid, picking a cache-holding replica only when its cumulative assignment count before routing is at most max_skew = 1 above the least-assigned replica, and falling back to the least-assigned replica otherwise.

Three simplifications matter. Cache capacity is counted in prefix entries rather than bytes. Cumulative assignments stand in for instantaneous queue depth, with no model of concurrent GPU service time. Finally, the assignments[index] <= least + max_skew check runs before the increment, so it is not a strict skew bound: right after an assignment, skew can reach max_skew + 1 (on this trace, hybrid's skew reaches 2 mid-run and ends at 1).

Worked Routing Result

Running the simulator produces:

Affinity-only reaches the maximum possible reuse on this trace (13,800 tokens: every request except the first of each prefix hits), at the price of sending all ten A requests, half the traffic, to replica 0 ([10, 5, 5]). Hybrid captures 2,000 more reused prefix tokens than round-robin while matching round-robin's [7, 7, 6] load distribution. These are simulator outputs; turning saved prefill tokens into TTFT or goodput claims requires pairing the router with a real queue and service-time benchmark.

Compatibility and Isolation Key

A sound prefix-cache key binds every input that can alter KV tensor values or access permissions. At minimum, evaluate:

(model_revision,
 tokenizer_and_chat_template_revision,
 adapter_or_LoRA_id,
 attention_and_position_configuration,
 KV_dtype_and_layout,
 multimodal_input_identity,
 tenant_or_trust_group_salt,
 token_prefix)

Sharing unsalted prefix hashes across tenants opens a timing side channel: an attacker can probe candidate prefixes and infer from a short TTFT whether another tenant recently submitted the same text. Passing a per-tenant cache_salt mixes an isolation secret into the first block hash so only requests carrying the identical salt can match cached blocks (vLLM security). Have an authenticated gateway inject high-entropy secret salts per user or trust group rather than trusting caller-supplied headers or predictable tenant IDs. Within that threat model, salting isolates prefix-hash lookups; it does not help once a salt leaks, and it does not close every other timing side channel.

Multimodal serving adds a second cache-identity boundary. vLLM's security guide notes that a caller-supplied media uuid replaces raw media-byte hashing as the cache identity in the processor, encoder, and prefix caches, so a colliding UUID can make the server reuse output derived from another caller's media (vLLM multimodal media UUID security, checked 2026-11-02). Authenticated gateways should assign unpredictable, trust-group-scoped media identifiers, reject untrusted caller UUID overrides, and test colliding UUIDs with distinct media payloads. The same guide states that options such as cache_salt reduce specific cross-tenant risks but are not an isolation boundary, so deploy isolated instances when tenant boundaries forbid shared caches. The text-only script below exercises prefix-key salting, not multimodal caches.

Build the Reuse and Routing Simulator

Save as simulate_prefix_routing.py and run python simulate_prefix_routing.py > prefix-routing-report.json. The isolation assertions test deterministic cache-key membership, not network-level timing:

import json
import secrets
from collections import OrderedDict

turn_inputs = [400, 700, 1000, 1400, 1700]
prior_outputs = [0, 100, 100, 150, 100]
reused = [0]
fresh = [turn_inputs[0]]
for index in range(1, len(turn_inputs)):
    reusable = turn_inputs[index - 1] + prior_outputs[index]
    reused.append(reusable)
    fresh.append(turn_inputs[index] - reusable)

block_size = 16
block_reused = [0] + [((turn_inputs[i-1] + prior_outputs[i] - 1) // block_size) * block_size
                      for i in range(1, len(turn_inputs))]
if any(r > n for r, n in zip(reused, turn_inputs)):
    raise ValueError("not an extending conversation")

prefix_lengths = {"A": 1000, "B": 800, "C": 600, "D": 400}
requests = list("AABACABDAACBADABCABA")

def simulate(policy, max_skew=1, cache_capacity=2):
    if cache_capacity < 1 or max_skew < 0:
        raise ValueError("invalid policy configuration")
    caches = [OrderedDict() for _ in range(3)]
    assignments = [0, 0, 0]
    reused_tokens = 0
    evictions = 0
    round_robin = 0

    for prefix in requests:
        hits = [index for index, cache in enumerate(caches) if prefix in cache]
        if policy == "round_robin":
            target = round_robin % len(caches)
            round_robin += 1
        elif policy == "affinity_only":
            target = min(hits, key=lambda index: assignments[index]) if hits else assignments.index(min(assignments))
        elif policy == "hybrid":
            least = min(assignments)
            eligible = [index for index in hits if assignments[index] <= least + max_skew]
            target = min(eligible, key=lambda index: assignments[index]) if eligible else assignments.index(least)
        else:
            raise ValueError(policy)

        cache = caches[target]
        if prefix in cache:
            reused_tokens += prefix_lengths[prefix]
            cache.move_to_end(prefix)
        else:
            cache[prefix] = True
            if len(cache) > cache_capacity:
                cache.popitem(last=False)
                evictions += 1
        assignments[target] += 1

    return {
        "reused_prefix_tokens": reused_tokens,
        "evictions": evictions,
        "assignments": assignments,
        "max_assignment_skew": max(assignments) - min(assignments),
    }

# Trusted runtime selects secrets; callers cannot supply another tenant's salt.
salts = {"tenant-a": secrets.token_hex(32), "tenant-b": secrets.token_hex(32)}
def key(tenant, prefix, model="model-v1", adapter="adapter-v1", salted=True):
    return (model, adapter, salts[tenant] if salted else "", prefix)
unsalted_cache = {key("tenant-a", "A", salted=False)}
salted_cache = {key("tenant-a", "A")}
tenant_b_probe_unsalted = key("tenant-b", "A", salted=False) in unsalted_cache
tenant_b_probe_salted = key("tenant-b", "A") in salted_cache
assert key("tenant-a", "A") in salted_cache
assert key("tenant-a", "A", model="model-v2") not in salted_cache
assert key("tenant-a", "A", adapter="adapter-v2") not in salted_cache

artifact = {
    "conversation": {
        "input_tokens": turn_inputs,
        "full_block_reused_by_turn": block_reused,
        "full_block_reused_total": sum(block_reused),
        "full_block_fresh_total": sum(turn_inputs) - sum(block_reused),
        "reused_tokens_by_turn": reused,
        "fresh_tokens_by_turn": fresh,
        "total_reused_tokens": sum(reused),
        "total_input_tokens": sum(turn_inputs),
        "reuse_fraction": sum(reused) / sum(turn_inputs),
    },
    "routing": {
        "round_robin": simulate("round_robin"),
        "affinity_only": simulate("affinity_only"),
        "hybrid": simulate("hybrid"),
    },
    "isolation": {
        "cross_tenant_hit_without_salt": tenant_b_probe_unsalted,
        "cross_tenant_hit_with_distinct_salts": tenant_b_probe_salted,
    },
}
print(json.dumps(artifact, indent=2))

Expected checks:

total_reused_tokens = 3950
total_input_tokens = 5200
reuse_fraction ≈ 0.7596
round_robin reused = 10000, skew = 1
affinity_only reused = 13800, skew = 5
hybrid reused = 12000, skew = 1
cross_tenant_hit_without_salt = true
cross_tenant_hit_with_distinct_salts = false

Deliberately Broken Cases

Universal-Prefix Benchmark

Benchmarking a router with a single shared system prompt, abundant KV memory, and light load mostly measures cold-start priming. It can show a finite warm-up advantage, but once every replica holds those blocks, hit rates converge, so the test cannot establish a steady-state routing advantage or an SLO improvement, and says nothing about eviction churn or hotspot control.

Affinity at Any Cost

Our affinity-only run sends 10 of 20 requests to replica 0. Under concurrent traffic, queueing behind an overloaded hot replica can erase the prefill time saved by a cache hit, even while the hit rate looks excellent. A production routing score should weigh saved prefill tokens against live prefill/decode queue depth, KV memory pressure, and TTFT SLO headroom.

Unsalted Multi-Tenant Cache

Leaving salted=False across tenants yields cross_tenant_hit_without_salt = true; in a real engine, that shared key would let one caller detect through a fast TTFT whether a guessed prefix is already cached. Distinct gateway-managed salts flip the cross-tenant probe to false.

Stale or Incompatible Index

A router's prefix view can lag behind local LRU evictions or miss differences in model revision, adapter, tokenizer, or KV dtype and layout, so routing hints are only best-effort optimization signals; the destination engine must still validate full block compatibility before reusing KV state.

Hands-On Exercise

1. Run the baseline simulator and inspect prefix-routing-report.json.

2. Shrink each replica's cache_capacity from 2 prefix families to 1.

3. Sweep max_skew across 0, 1, and 2.

4. Add a hot prefix E of length 1,200 tokens and append an eight-request burst of E to the arrival trace.

5. For each policy, report reused prefix tokens, assignment skew, eviction count, and a simple queue-penalty estimate.

6. Verify the model and adapter invalidation assertions in simulate_prefix_routing.py, then document how a production engine must additionally bind chat-template/tokenizer revision, position/mask config, KV layout, and multimodal media identity; those backend checks are outside this text-only simulator.

7. Add two authenticated trust groups with distinct gateway-assigned salts, verify intra-group hits and cross-group misses in the key model, and outline a separate end-to-end test for gateway header stripping and timing probes.

Measurable Exit Criteria

The tutorial passes when:

• local engine prefix lookup and distributed cache-aware routing are analyzed separately;

• the five-turn calculation distinguishes the 3,950-token idealized bound from the 3,904-token full-block count under 16-token blocks and unmaterialized final-token KV;

• previously generated assistant tokens are included in the reusable prefix of subsequent turns;

• the universal-prefix analysis separates the 800-token warm-up difference from steady-state behavior and latency claims;

• the baseline routing simulation reproduces 10,000, 13,800, and 12,000 reused tokens;

• hybrid routing achieves max_assignment_skew = 1 on the baseline trace;

• the cache-identity specification covers model, tokenizer/template, adapter, position/mask config, KV layout, multimodal media identity, and tenant salt, noting that the supplied script tests only the model, adapter, prefix, and tenant-salt fields while the rest require backend validation;

• the unsalted multi-tenant check demonstrates cross-tenant key collision (true); and

• distinct salts prevent cross-tenant key hits (false).

Retrieval Practice

1. How does local prefix caching differ from distributed cache-aware routing?

2. Why does turn 2 of the five-turn conversation reuse roughly 500 tokens instead of only the 400-token turn-1 prompt?

3. Why does round-robin match affinity routing in steady state when every request shares one small system prompt?

4. What trade-off does the hybrid routing rule make compared with affinity-only routing?

5. Why can a request routed for a predicted prefix hit still suffer a cache miss at the engine?

6. What threat does per-tenant cache salting address, and what remains outside its scope?

Answer Key

1. Local prefix caching hashes, validates, and reuses KV blocks inside a single engine's memory pool; distributed cache-aware routing selects which replica or cache domain receives an incoming request.

2. When turn 2 strictly extends turn 1, the 400 prompt tokens and the 100 generated assistant tokens from turn 1 form the prefix that turn 2 extends. With 16-token full blocks and no KV yet for the final sampled token, 496 of those 500 tokens are reusable.

3. After the first request per replica warms that 200-token prefix on all five replicas, every replica retains it locally and serves subsequent requests as cache hits without concentrating load.

4. Hybrid routing gives up some prefix hits whenever a cache-warm replica's assignment lead exceeds max_skew, to keep hot prefixes from overloading one replica.

5. Local LRU eviction may have dropped the blocks before the request arrived, the router's approximate prefix tree may disagree with exact tokenization, or compatibility metadata (such as adapter or template version) may differ.

6. With gateway-enforced, high-entropy salts per trust group, salting prevents one tenant from matching another tenant's cached prefix blocks and probing them via TTFT within this threat model. Leaked or predictable salts, shared multimodal UUID overrides, and other timing channels require separate controls.

What This Post Does Not Cover

I-03 combines prefix locality with network topology when scheduling across disaggregated prefill and decode pools. I-07 integrates cache hit rates, queueing, and tail-latency SLOs into a full production benchmark. Provider prompt caching in commercial APIs, including its pricing and retention behavior, is a separate product contract outside engine internals.

Source Notes

• Zheng, L., Yin, L., Xie, Z., et al. "SGLang: Efficient Execution of Structured Language Model Programs." NeurIPS, 2024. Primary source for RadixAttention and whole-system LM-program evaluations. arxiv.org/abs/2312.07104

• vLLM Project. "Automatic Prefix Caching." Current documentation, accessed 2026-11-02. First-party block-hash chaining, compatibility rules, and V1 prefix-caching design. docs.vllm.ai

• Srivatsa, V., He, Z., Abhyankar, R., et al. "Preble: Efficient Distributed Prompt Scheduling for LLM Serving." ICLR, 2025. Primary source for distributed prompt scheduling balancing prefix reuse against replica load. arxiv.org/abs/2407.00023

• Yuan, Y., Zuo, P., Wang, B., et al. "DualMap: Enabling Both Cache Affinity and Load Balancing for Distributed LLM Serving." ICLR, 2026. Primary source for dual-hash SLO-aware routing balancing cache affinity and hotspot load. arxiv.org/abs/2602.06502

• Ray Serve. "Prefix-Aware Routing." Current alpha documentation, accessed 2026-11-02. First-party PrefixCacheAffinityRouter behavior and imbalanced_threshold semantics. docs.ray.io

• vLLM Project. "Security: Prefix Cache Timing Side-Channel Mitigation." Current documentation, accessed 2026-11-02. First-party cache_salt and multi-tenant isolation guidance. docs.vllm.ai