LearnPython

SGLang and RadixAttention for Prefix-Heavy Workloads

SGLang treats the KV cache as a reusable resource and stores it in a radix tree. vLLM schedules requests first-come, first-served (FCFS). SGLang's cache-aware scheduler prioritizes requests with longer shared prefixes, which works like a depth-first radix traversal and keeps hot branches resident in HBM. On Llama 3.1 8B with ShareGPT-like 1K prompts, SGLang hits ~16,200 tok/s to vLLM's ~12,500, a ~29% edge. On prefix-heavy RAG workloads the advantage reaches 6.4x. On voice-cloning-shaped workloads, cache hit rate cleared 86%. It is deployed on 400,000+ GPUs in 2026 across xAI, LinkedIn, Cursor, Oracle, GCP, Azure, and AWS. The gotcha: the 6.4x number evaporates when prefix ordering is inconsistent, and ordering is the lever you control.

TIME: ~75 minutesPREREQUISITES: Phase 17 · 04 (vLLM Serving Internals), Phase 14 (Agentic RAG)

Learning Objectives

Diagram RadixAttention: how prefixes are stored in a radix tree and how KV blocks are shared across sequences rooted at the same branch.
Explain cache-aware scheduling and why FCFS is wrong for prefix-heavy traffic.
Compute expected speedup for a workload given prefix-cache hit rate and prompt length distribution.
Name the prompt-ordering discipline that makes the 6.4x number real vs a lost upside.

The Problem

Classic serving treats each request's prompt as opaque. Say 5,000 RAG requests all start with the same 2,000-token system prompt and the same retrieval preamble. vLLM without prefix caching prefills that 2,000-token prefix 5,000 times, and the GPU repeats the same work on every request.

Prompts in agentic and RAG workloads tend to share long prefixes. System prompt, tool schemas, few-shot examples, retrieval headers, conversation history: all of it repeats across requests. If you stored the KV cache for that prefix once and reused it, you would skip the prefill.

RadixAttention does this. Tokens are indexed in a radix tree, and each node owns the KV blocks for the token sequence on its path from the root. A new request walks the tree, and any node whose tokens match reuses that node's KV blocks. Prefill cost scales with the new suffix instead of the full prompt.

The hard part is scheduling. Suppose two requests share a 2,000-token prefix and a third shares only 200 tokens of it. You want to serve the two long-prefix requests together so the long prefix stays in HBM. FCFS does the opposite: it serves whoever arrived first, and it can evict the hot branch before the next long-prefix request shows up.

Warm-up0/4

1. In an agentic RAG request, which prompt components usually stay identical from one request to the next?Warm-up

One request split into parts: a prompt made of system prompt, tool schemas, retrieved passages and user question; a response of sampled output tokens and logprobs; and metadata of request ID and arrival timestamp. A question mark asks which part stays identical across requests. — Schematic; no part is marked as repeating.

2. By default, in what order does a vLLM-style continuous-batching scheduler admit waiting requests?Warm-up

Four requests that arrived at times t1 through t4, feeding into a scheduler box, with a question mark asking which request is admitted next by default. — Schematic; no admission order is shown.

3. During prefill, what does a transformer store for each prompt token so that decoding does not recompute earlier tokens?Warm-up

A token flowing through three attention layers, each layer marked 'stores: ?', with a note that earlier tokens are not recomputed at decode time. — Schematic transformer stack; no specific stored quantity is named.

4. A cache stores entries under an exact key. Two requests ask for the same content, but one builds its key with the parts in a different order. What does the cache do?Warm-up

Two requests with identical content but keys in a different order, (a,b,c) and (b,a,c), both feeding into one cache lookup box, with a question mark for what happens to the second request. — Schematic; outcome left open.

Check: The Problem0/6

1. What is RadixAttention?Define

Two requests, A and B, each drawn as token blocks: a shared leading block common to both followed by each request's own distinct tail. A question mark asks what the named system does with the shared part. — Illustrative token blocks, not to scale.

2. What does FCFS scheduling do, and what does that do to prefix reuse?Define

Three queued requests labelled by arrival order, first to arrive sharing little and the second and third sharing a long prefix. Two question marks ask the FCFS admission order and the effect on the long-shared-prefix branch. — Schematic; no admission order or effect is drawn.

3. Why does a request that matches a cached prefix cost less prefill work?Explain

A request's tokens split into a larger matched region, already in the tree, and a smaller new region, with a question mark asking why this costs less to prefill. — Proportions are illustrative, not measured.

4. Why is FCFS a poor fit for prefix-heavy traffic?Explain

Three queued requests: A and B each sharing a 2,000-token prefix, and C sharing only 200 tokens of it. A question mark asks why FCFS is a poor fit here. — Snapshot only; no serving order is shown.

5. 5,000 RAG requests share the same 2,000-token system prompt, and prefix caching is off. How many prefix tokens does the GPU prefill in total across them?Apply

One request with a 2,000-token system prompt, multiplied by 5,000 requests, with a note that each one prefills the full prefix, and a question mark for the total. — Numbers from The Problem's worked scenario.

6. Two queued requests share a 2,000-token prefix and a third shares only 50 tokens of it. Under load, the 2,000-token branch keeps being evicted to admit the third. Which ingredient is missing?Analyze

Numbers from The Problem's scenario.

The Concept

The radix tree as a KV index

A radix tree (compact trie) stores token sequences. Each node owns a token range and the KV blocks computed for that range. Children extend the sequence one or more tokens.

root
 |- "You are a helpful assistant..."  (2,000 tokens, 125 KV blocks)
      |- "Context: <doc A>..."        (500 tokens, 32 blocks)
           |- "Question: Alice..."    (80 tokens, 5 blocks)
           |- "Question: Bob..."      (95 tokens, 6 blocks)
      |- "Context: <doc B>..."        (520 tokens, 33 blocks)

A new request comes in with system prompt + "Context: " + "Question: Carol". The scheduler walks: system prefix matches (125 blocks reused), doc-A branch matches (32 blocks reused), then allocates fresh blocks only for "Question: Carol" (4 blocks). Prefill cost: 4 blocks of new tokens. Without the tree: 161 blocks. ~40x savings on prefill.

Cache-aware scheduling

Radix-tree reuse buys nothing if the cache churns. Two policies keep it from churning:

Depth-first dispatch. When picking the next request from the queue, prefer requests rooted at the same branch as the current running set. This keeps the hot branch pinned.
LRU at branch level, not block level. Evict whole branches (starting from shortest-used leaves) rather than individual blocks, so cache shape matches radix shape.

FCFS violates both. Picture a request sharing 2,000 tokens stuck behind one sharing 50. The 2,000-token branch can get evicted to admit the 50-token one.

Benchmark numbers worth remembering

Llama 3.1 8B, H100, ShareGPT 1K prompts: SGLang ~16,200 tok/s vs vLLM ~12,500 (~29% edge).
Prefix-heavy RAG (same system + same doc, varying question): up to 6.4x on SGLang.
Voice cloning workloads: 86.4% prefix-cache hit rate.
Production hit rates across SGLang customers: 50-99% depending on prompt discipline.
Deployed on 400,000+ GPUs in 2026.

The ordering gotcha

The 6.4x number relies on consistent prompt-template ordering. If your client constructs prompts as [system, tools, context, history, question] in some requests and [system, context, tools, history, question] in others, the tree cannot find the shared prefix. A human sees one shared prefix. The radix tree sees two distinct sequences.

Your prompt template is a cache key, and the order is yours to set. Put everything immutable (system, tools, schemas) first, retrieval context next, and the user question last. Keep dynamic content out of the prefix.

One reported case: moving dynamic content out of the cacheable prefix took a deployment from 7% to 74% cache hit rate in a single change.

Where RadixAttention wins and loses

Wins:

RAG (same retrieval preamble, varying question).
Agents (same tool schemas, varying query).
Chat with long system prompt.
Voice / vision workloads with repeated preambles.

Loses (returns to vLLM-level throughput):

Single-shot generation with unique prompts (code completion, open-ended chat without system prompt).
Dynamic prompts where every request interleaves unique content into the prefix.

Why this is a scheduler problem, not just a kernel problem

You can implement KV reuse as a kernel trick. SGLang's insight is that reuse only pays when the scheduler keeps the hot branch resident. A naive "reuse if available" policy can churn the cache under mixed load. The radix-tree-indexed scheduler is what turns the kernel trick into the ~29% edge.

Interplay with vLLM

The two systems overlap more than they compete. In 2026 vLLM added prefix caching (--enable-prefix-caching) and a cache-aware router (vLLM Router in Rust). The gap narrowed but is still there: SGLang's whole stack is radix-first, while vLLM added it on. For workloads dominated by prefix reuse, SGLang remains the default. For general-purpose serving without strong prefix patterns, vLLM is equal or better.

Check: The Concept0/19

1. In the radix tree described in The Concept section, what does each node own?Define

One node of a radix tree, with an edge up to its parent and two edges down to child nodes. A question mark asks what this node owns. — Generic node position; contents are the question.

2. What is a cache-aware scheduler?Define

A resident branch box above three waiting requests, none marked as related to it, with a question mark asking the selection rule for which runs next. — Schematic; no selection shown.

3. What eviction granularity does the cache-aware scheduler use to match radix shape?Define

A small tree of a root, three branches and four leaves, with a question mark asking the eviction unit and which one gets picked. — Schematic; no eviction is shown.

4. What does prefix-cache hit rate measure?Define

A prompt's tokens split into two unlabelled, equal-looking regions, with a question mark asking which fraction of which tokens the term hit rate refers to. — Illustrative split; no lengths are given.

5. In this context, what is prompt template ordering?Define

Four prompt components, retrieved context, user question, tool schemas and system prompt, chained in that arbitrary order, with a question mark asking what this order is called. — One arbitrary ordering, for illustration only.

6. What is system prompt pinning?Define

The system prompt node at the root of the tree with a small pin marker above it, and a question mark asking what system prompt pinning means. — Schematic; the pin's effect is the question.

7. In the tree diagram, why can the Alice and Bob questions both reuse the doc A node's KV blocks?Explain

A tree: root to system prompt to doc A, which splits into Alice and Bob, and separately to doc B. A question mark asks why Alice and Bob both reuse doc A's blocks. — Matches the Concept section's tree diagram, without block counts.

8. Why does depth-first dispatch keep the hot branch resident?Explain

A running branch X above three waiting requests, two on branch X and one on branch Y, with a question asking which is picked next and why that keeps branch X resident. — Schematic; no pick is shown.

9. Why does the lesson say KV reuse is a scheduler problem and not only a kernel problem?Explain

A kernel box that reuses KV blocks when available, under a note that load sometimes shares a prefix and sometimes does not, with a question about whether this alone is enough. — Schematic; the missing piece is the question.

10. When tools and context swap places between requests, a human sees one shared prefix but the radix tree sees two sequences. Why?Explain

Two requests, A as SYSTEM, TOOLS, CONTEXT, Q and B as SYSTEM, CONTEXT, TOOLS, Q, stacked with no highlighting, and a question about what the radix tree sees. — Same four components, tools and context swapped in B.

11. Why did moving dynamic content out of the prefix lift one deployment's hit rate from 7% to 74%?Explain

A bar chart of hit rate before and after one change, 7% and 74%, with a question mark asking what changed. — Figures reported in The ordering gotcha.

12. Why does the lesson say vLLM's added prefix caching narrowed the gap with SGLang but did not close it?Explain

SGLang and vLLM with prefix caching side by side, joined by a curve labelled gap narrowed, not closed, and a question mark asking why a gap remains. — Schematic; no cause is drawn.

13. A new request reuses its cached system prefix and its document branch, so only 4 fresh blocks need prefill. Without the tree the same prompt would cost 161 blocks. Roughly how much prefill work does reuse save?Apply

Two bars, 161 blocks without the tree and 4 blocks with the tree, with a question mark asking roughly how much less work that is. — Figures from the Concept section's worked example.

14. A RAG service builds prompts as [system, tools, context, question] on one code path and [system, context, tools, question] on another. Its hit rate sits near 8%. What is the best first fix?Analyze

Two code paths building the same four components, system, tools, context and question, in different orders, with a question mark asking the best first fix for an 8% hit rate. — Setup from the stem; no fix is shown.

15. A service reports an 8% prefix-cache hit rate. Every prompt starts with a line holding the current timestamp, followed by the same system prompt and tools. What is the most likely cause?Analyze

Three equally styled segments, timestamp, system prompt and tools, with a hit rate of 8% and a question mark asking the most likely cause. — No segment is marked as the cause.

16. A team moves code completion to SGLang. Every prompt is a unique snippet with no system prompt, and throughput matches vLLM. What explains the result?Analyze

Three distinct code snippets with no shared system prompt, above two equal bars labelled SGLang and vLLM, and a question asking why the throughputs are equal. — Equal bars are illustrative; both read 100.

17. You are building an agent service. Each request has a system prompt, tool schemas, retrieved documents and the user question. Which template order maximizes prefix reuse?Design

Four prompt components, system prompt, tool schemas, retrieved docs and user question, placed with no implied order, and a question mark asking which order maximizes reuse. — Components placed arbitrarily; order is the question.

18. You serve mixed traffic under tight HBM. Many requests share a long prefix and others share little. Which design best keeps the long prefix resident?Design

Two request groups, many sharing one long prefix and others sharing little, under a tight HBM budget, with a question mark asking which design keeps the long prefix resident. — Schematic; no design is shown.

19. Before adopting SGLang for a new product, which measurement best predicts whether a large prefix-reuse win is available to you?Design

Schematic; no candidate measurement is listed.

Use It

code/main.py implements a toy radix-tree KV cache and a scheduler with two policies, FCFS and cache-aware. It runs the same RAG workload through both and prints prefix-cache hit rate, then runs a scrambled-ordering workload to show the hit rate collapse. It reports hit rate and saved tokens only, not throughput.

Check: Use It0/6

1. In the toy cache, token_count gives TOOLS 300 tokens and BLOCK_TOKENS is 16. How many blocks does inserting the TOOLS node allocate?Apply

The real ceiling-division line from RadixCache.insert, with TOOLS at 300 tokens and BLOCK_TOKENS at 16, and a question mark for the blocks allocated. — Code quoted from main.py; values from the stem.

2. The toy cache holds the paths SYSTEM, SYSTEM+TOOLS, SYSTEM+TOOLS+DOC_0 and a question node under DOC_0 (SYSTEM is 2,000 tokens, TOOLS 300, DOC 500). A request arrives as [SYSTEM, TOOLS, DOC_1, Q_9]. How many tokens does walk() report as reused?Apply

A list of four cached paths all starting SYSTEM, TOOLS, DOC_0, next to a new request SYSTEM, TOOLS, DOC_1, Q_9, with a question mark for how many tokens walk() reuses. — Exact path keys from a real run of the toy RadixCache.

3. The toy cache holds the path [SYSTEM, TOOLS, DOC_0, Q_1]. A new request arrives as [TOOLS, SYSTEM, DOC_0, Q_2]. How many tokens does walk() report as reused?Apply

One cached path, SYSTEM, TOOLS, DOC_0, Q_1, next to a new request TOOLS, SYSTEM, DOC_0, Q_2 with the first two segments swapped, and a question mark for tokens reused. — Exact path key from a real run of the toy RadixCache.

4. In the toy, a prompt is SYSTEM (2,000 tokens) + TOOLS (300) + DOC (500) + question (60), and the walk reuses the first 2,300 tokens. What is that request's prefix-cache hit rate?Apply

A segment bar of SYSTEM 2,000, TOOLS 300, DOC 500 and question 60 tokens, with a line marking that walk reuses the first 2,300 tokens, and a question mark for the hit rate. — Segment sizes and the reused count are both given in the stem.

5. In the toy `main.py`, what happens when the prefix order of [SYSTEM, TOOLS, DOC] is scrambled?Apply

Two equal bars at 69.1% for FCFS and CACHE_AWARE on the fixed-order RAG workload, with a question about what happens to each once the prefix order is scrambled. — Captured from a real run of main.py's workload_rag().

6. In the toy run on the fixed-order RAG workload, FCFS and cache-aware both reach 69.1% hit rate. Which conclusion does that support?Analyze

Two equal bars at 69.1% for FCFS and CACHE_AWARE on the RAG workload, with a question mark asking which conclusion this supports. — Captured from a real run of main.py's workload_rag().

Ship It

This lesson produces outputs/skill-radix-scheduler-advisor.md. Given a workload description (prompt-template shape, retrieval pattern, number of concurrent tenants), it produces a prompt-ordering prescription and a go/no-go for SGLang adoption.

Author's Note

I'd run main.py and read its output skeptically. It simulates hit rate only, so it can't confirm the throughput, 6.4x or GPU-count figures above, and I'd treat those as reported numbers. On the RAG workload, FCFS and cache-aware both land at 69.1% hit rate. In this toy the scheduler makes no difference there, so the scheduling argument in the Concept section is something the code doesn't show. The scrambled workload is where it does move: FCFS drops to 8.4% and cache-aware recovers to 26.5%, still far below 69.1%.

The KEY FINDING text at the bottom of main.py agrees with those numbers: about 69% on RAG with either scheduler, and a collapse when the prefix is scrambled. Exercise 1 asks you to check that yourself.

My bet is that ordering matters more than scheduling, and the toy agrees with me. Shuffling [SYSTEM, TOOLS, DOC] costs far more hit rate than any scheduler wins back. Treat the toy's constants (a 160-block budget, 16-token blocks) as pedagogical, since they are sized so eviction bites. They show the shape of the effect, not what your deployment will see.

Exercises

Run code/main.py. Compare FCFS and cache-aware on the same workload, and check the KEY FINDING line against the hit rates it prints. The toy reports hit rate only, so where would a delta show up in a real server: prefill savings, decode savings, or queue delay?
Modify the workload so prompts randomly permute [system, tools, context]. Re-run. What happens to hit rate? Why?
Compute the HBM cost of keeping a 2,000-token system prompt resident as one radix branch on Llama 3.1 8B. Compare to the cost of a 16-sequence batch without prefix reuse.
Read the SGLang RadixAttention paper. Explain in three sentences why tree-shaped LRU eviction beats block-shaped LRU under prefix-heavy load.
A customer reports only 8% cache hit rate. Name three likely causes and the diagnostic you would run for each.

Key Terms

Term	What people say	What it actually means
RadixAttention	"the SGLang thing"	KV cache indexed as a radix tree so shared prefixes reuse blocks
Radix tree	"compact trie"	Tree where each node owns a token range and its KV blocks
Cache-aware scheduler	"hot-branch-first"	Scheduler that prefers requests sharing the resident branch
Prefix-cache hit rate	"how much of your prompt was free"	Fraction of prompt tokens served from reused KV blocks
FCFS	"first-come first-served"	Default scheduling that breaks prefix locality
Branch-level LRU	"evict the leaf"	Eviction policy matched to radix shape
Prompt template ordering	"the cache key"	The prompt's component order determines what the tree can share
System prompt pinning	"resident prefix"	Keep the immutable system portion pinned to avoid eviction thrash