Prefix caching and reuse-aware scheduling
Share KV state safely and quantify cache value
Before you begin
Follow a linked prerequisite when you cannot explain it from memory. Background skills without links are stated as abilities rather than hidden terminology.
- Paged KV
- Hashing and cache keys
- Prompt processing
Forty percent of requests to the 7-billion-parameter service begin with the same 12,000-token system and tool description. Without reuse, every request runs prompt processing over those 12,000 positions and writes an identical set of key-value entries. Server logs show repeated prefill-token counts and similar prompt-processing milliseconds. A prefix cache can retain the completed blocks once and let later matching requests reference them.
Instrument cache lookup with the token-prefix hash, matched-token count, retained physical blocks, model version, adapter identifier, tenant, and saved prefill milliseconds. The lookup evidence distinguishes a request hit from useful work saved: matching 10 tokens is less valuable than matching 12,000. Memory counters also show the cost because retained prefix blocks occupy space that active sequences could otherwise use.
Many requests begin with identical tokens: a system prompt, tool schema, document, or conversation history. Prompt processing computes identical keys and values for that prefix. A prefix cache stores the blocks so later requests can start from the resulting state instead of repeating work. Prefix caching is memoization over token sequences and model configuration.
SGLang's RadixAttention represents cached token prefixes in a radix tree and uses that structure for automatic reuse and cache-aware scheduling. Other engines use block hashes or related structures. The implementation differs, but the correctness requirement is the same: a cache hit must represent exactly the model state that a fresh prefill would have produced.
Tokens alone are not a sufficient identity when model weights, adapters, position handling, cache dtype, attention configuration, or prompt serialization differ. Reused blocks also consume memory that could admit active requests. A hit has positive value only when saved prefill work exceeds lookup, retention, eviction, and opportunity costs.
Define cache identity and match length
Construct cache identity from the exact token sequence and every factor that changes the resulting KV state. At minimum, evaluate model and weight version, adapter, positional semantics, attention masks or sliding-window rules, cache dtype, and tenant isolation. The tokenizer, chat template, tool schema, and multimodal preprocessing determine the token or embedding sequence before lookup; version those inputs whenever the cache key is built from a higher-level prompt rather than final token IDs.
A request may match only an initial prefix. The engine reuses complete valid blocks and computes the remaining prompt suffix. When cache entries align with KV blocks, shared blocks can use reference counts and later tokens can be appended to private blocks. A match that ends inside a partially shared block needs a defined ownership rule.
Hashes make lookup efficient but cannot permit collision-based incorrect reuse. Verify token and configuration identity or use a collision-resistant scheme with an explicit threat model. Cache invalidation on model or adapter rollout must occur before requests can mix states from different versions.
Calculate value per retained byte
Measure hit value in saved prefill tokens and time, not request count alone. A frequently reused 32-token prefix may save little work. A 12,000-token tool and policy prefix can save a large prefill on each hit. Saved time also depends on the batch and hardware that would have processed the missed prefill.
Retained prefix blocks have an opportunity cost. The same blocks could hold active decode state or admit another request. Under light load, retaining a broad cache can be inexpensive. Near the memory limit, inactive prefix entries can cause admission delay or preemption. Report cached bytes, active KV bytes, hit tokens, saved prefill time, and evictions together.
Eviction policies can combine recency, frequency, size, regeneration cost, and tenant quota. A value-per-byte estimate is often more informative than LRU alone, but future reuse is uncertain. Replay real arrivals to determine whether a more complex policy improves goodput after its scheduler cost.
Combine reuse with scheduling and isolation
A reuse-aware scheduler can prioritize a request whose prefix is already resident, which converts a cache hit into immediate saved work and may prevent eviction. The scheduler can also group related branches or multi-turn calls so shared state remains hot. Delaying an older miss to serve a newer hit improves efficiency but changes fairness.
RadixAttention uses the prefix tree for reuse and cache-aware scheduling of structured programs. The benefit is workload-dependent. Independent chat prompts with little shared structure will not obtain the same hit rate as multi-turn, few-shot, or tree-search workloads. Preserve a policy for cache misses and for request classes that cannot share.
Cross-tenant sharing can leak information through state access or timing even when content is never returned directly. Use isolation domains and permissions in both lookup and eviction. Security policy can require separate caches or disable sharing across users, adapters, or model variants. The sharing restriction belongs in capacity and benchmark results.
Worked example: Valuing a cached system prompt
A 12,000-token system and tool prefix appears in 40% of requests. Its KV state occupies 1.5 GiB per physical copy under the serving mesh.
- Measure prefill time and energy for 12,000 tokens. Multiply by hit frequency to estimate compute saved per minute.
- Compare the 1.5 GiB retention with how many additional active-request tokens that memory could hold. At peak load, the opportunity cost may be high.
- Use one shared page chain with reference counts rather than duplicate cache per request. Include adapter and model-version identity in the key.
- Replay arrival patterns and memory pressure. Measure TTFT, goodput, eviction churn, and whether cache reservation causes admission stalls.
Conclusion: The 12,000-token prefix has large reuse value, but its 1.5 GiB footprint competes with active-request KV. Replay determines whether retained shared blocks save more prefill time and admissions than they displace. Report saved tokens and goodput, not hit percentage alone.
Common errors
- Keying only on decoded text. Tokenization, model state, adapters, positions, and numerical format affect cache validity.
- Maximizing hit rate. A high-rate short prefix can save less work than a lower-rate expensive prefix.
- Ignoring isolation. Cross-tenant reuse can violate privacy or side-channel requirements even when technically possible.
Reference summary
Prefix caching stores KV blocks for repeated token prefixes and reuses the longest valid match. A radix tree or block-hash structure can index those prefixes and guide reuse-aware scheduling. Reused state must be identical to the state a fresh prefill would produce.
The cache identity includes token IDs and every model or execution factor that changes KV, including weight version, adapter, position behavior, and cache format. Retained prefixes compete with active requests for memory, so evaluate saved prefill time per retained byte and enforce tenant isolation.
cache value ≈ hit probability × saved prefill work − lookup/retention/eviction cost- Measure hit rate weighted by saved tokens, not requests alone.
- Use reference-counted immutable shared blocks and copy-on-write branches.
- Evict by expected future value, recency, size, or tenant policy.
- Prevent cross-tenant information leakage through isolation and key design.
- Schedule reuse near enough in time that retention does not crowd out active decode cache.
Knowledge check
Why is hashing prompt token IDs alone insufficient for a safe prefix-cache key?
Show the answer guide
- Token IDs identify prompt content, but they do not identify every condition that determines the cached K and V tensors. The same IDs can produce different cache values under a different model revision, adapter, attention or rotary-position configuration, cache dtype, or multimodal preprocessing path.
- A safe key must include the model and weights identity, tokenizer and preprocessing identity where relevant, adapter or tenant-specific state, positional context, numerical and cache-layout version, and any prompt-affecting execution option.
- The key also needs an unambiguous prefix boundary and a collision-safe hash or content verification. Otherwise one prompt can incorrectly reuse blocks belonging to another logical input.
- Access control and lifecycle are part of safety: shared cache entries must not leak tenant data, outlive revoked model state, or bypass copy-on-write when a branch extends the prefix.
Design and attack a prefix-cache key
Implement a small prefix-cache simulator for token sequence [101, 42, 77, 9] under two model revisions, two LoRA adapters, two tenant scopes, and positions beginning at 0 or 128. Begin with a token-ID-only key, demonstrate incorrect hits, then replace it with a versioned semantic key and collision verification. Extend one shared prefix using copy-on-write.
Evidence to keep: Submit the simulator code, a table of all declared cases with expected hit or miss behavior, tests that expose at least three unsafe token-only hits, tests for tenant isolation and copy-on-write, and the final serialized key schema. Explain which execution fact makes each rejected reuse unsafe.
Long uncached prompts still need prefill. Chunking controls how their large work units coexist with ongoing decode and finite admission budgets.
Sources and further reading
The lesson explanations synthesize primary papers and official references. Follow the originals for proofs, exact APIs, architecture details, and version-sensitive behavior.
- Orca: Iteration-Level Scheduling↗
- PagedAttention / vLLM↗
- SGLang↗
- NVIDIA Nsight Systems User Guide↗
Official reference for capturing and reading CPU, CUDA API, GPU workload, and communication timelines.