Prompt Caching & RadixAttention

Prompt caching reuses the KV computed for identical prompt prefixes, skipping repeated prefill computation. Typical reusable prefixes: system prompts, few-shot exemplars, early turns of multi-turn conversations, and shared instruction blocks across tenants — often 50-90% of a request's tokens, needlessly recomputed every time. RadixAttention (SGLang's core): organizes the KV blocks of all live requests into a radix tree where each node is a shared token prefix (root = empty; a path from root to node is a token sequence). A new request walks the tree with longest-prefix matching; matched nodes reuse their KV directly, and only the unmatched suffix is prefilled (compute ∝ unmatched tokens). The tree splits/merges dynamically as requests start and end: shared prefixes stay shared, divergent branches split. Effects: with a cache hit, TTFT drops 80%+ (if 90% of tokens hit and prefill dominates TTFT, TTFT ≈ 1/10 of the original); multi-turn chats only compute the incremental turns; shared system prompts slash per-request cost across tenants. Eviction: tree nodes carry reference counts and last-access timestamps; when memory is tight, least-recently-used branches are evicted (like OS page replacement), and a later hit requires recomputing prefill. vs vLLM's automatic prefix caching: vLLM hashes fixed-size token blocks (n-gram block hashing) — simple and effective; RadixAttention reuses arbitrary-length longest common prefixes precisely, with finer granularity and bigger wins for long shared prefixes.

conversational services with long system prompts, agentic multi-turn tool calls (each turn resends the full context), RAG with shared instruction templates, multi-tenant SaaS; interview favorites: "why does TTFT drop 80%+", "how the radix tree matches prefixes", "eviction policies".

prefill is compute-bound, and repeated prefill of long prompts wastes GPU compute and inflates TTFT; prefix KV reuse zeroes out the repeated work — at 80-90% hit rates the prefill compute demand drops by an order of magnitude and TTFT by 80%+, sharply reducing per-token cost in multi-turn/multi-tenant settings. It is one of the most direct cost levers of the long-context era.

Radix-tree prefix reuse: how a new request does longest-prefix matching; how hit prefixes vs unmatched suffixes are handled; how the tree splits/merges as requests end.

Why TTFT drops 80%+: prefill compute is proportional to unmatched tokens; convert hit rate and prefill share into numbers (prefill is 90% of TTFT, 90% hits → TTFT down ~81%).

Eviction policies: how LRU / reference counting work on the radix tree (branch-wise eviction); the cost of evicting hot prefixes on hit rate and TTFT.

Which workloads gain most: system prompts, multi-turn, multi-tenant sharing; estimate hit rate and token savings, and how caching composes with continuous batching and PD disaggregation.

vLLM prefix caching vs SGLang RadixAttention: block-hash matching vs radix-tree longest-prefix matching; hit granularity, implementation complexity, and the gap on long shared prefixes.