05 — RadixAttention & SGLang (YOUR PAPER)¶

Paper: Zheng, Yin, Xie, Huang, Sun, Li, Lin, Cao, Sheng, Chen, Wu, Liu, Sinha, Gonzalez, Stoica — “SGLang: Efficient Execution of Structured Language Model Programs” (NeurIPS 2024). arXiv: <phone_number_or_numberic_id_or_random_id_32>. LMSYS blog: https://www.lmsys.org/blog/2024-01-17-sglang. Repo: https://github.com/sgl-project/sglang.

Why this file is different from the others¶

Every other paper in this phase is a nice mechanism. This one is leverage against your specific day job.

You work on agentic harnesses and long-running automation services at Zoho. Your production traffic pattern is:

Long system prompt repeated on every turn (tools schema, few-shot examples, agent policy) — typically 2000-8000 tokens
Growing conversation history re-sent on every turn (multi-turn tool calling)
Retry loops on tool errors that re-send nearly-identical context
Fan-out patterns where the same context is used for multiple sub-queries

RadixAttention is the paper that reads exactly your traffic and says: “you don’t need to recompute or re-store 90% of that.” It is the highest- ROI thing in this entire phase for your specific position. If you land one win at Zoho from this roadmap, it will be from this paper.

The problem¶

Orca + PagedAttention got us: iteration-level scheduling with paged KV. But both still treat each request as independent. If 100 concurrent requests share a 2000-token system prompt, that prefix’s KV is either:

Recomputed 100 times (prefill compute wasted 99×), or
Stored 100 times (KV memory wasted 99×), or
Some accidental partial sharing if two happened to land on the same paged blocks by luck.

vLLM added prefix caching later (also via hash-chained blocks in the KV cache manager). SGLang was designed around it from day one, and chose a data structure that’s a natural fit: a radix tree keyed by token sequences.

RadixAttention: the mechanism¶

A radix tree (aka compact trie) stores strings by shared prefixes. Nodes have multiple characters per edge to collapse chains. SGLang uses a radix tree keyed by token IDs, where each node stores a range of tokens on its edge and the KV blocks corresponding to those tokens.

                    [root]
                      │
              "You are a helpful
              assistant. Tools: ..."
              (KV blocks 0..127)
                      │
                ┌─────┴─────┐
              (2 children diverge here)
                │           │
         "User: search   "User: what
         weather in"     time is"
         (KV 128..135)   (KV 136..142)
           │             │
         ...           ...

On every new request:

Tokenize the prompt.
Walk the radix tree matching tokens; return the deepest node whose full prefix matches the prompt.
The KV blocks along that path are already computed. Reuse them directly — no recomputation, no additional storage.
Compute prefill only for the unmatched tail of the prompt.
Insert the new tokens as a new branch (or extend the matched leaf).

Eviction: LRU on nodes. When KV memory pressure forces eviction, free the leaf-most, least-recently-used branch’s blocks. The tree structure guarantees you never evict a prefix while a suffix is still referenced.

That’s the whole idea. Elegant, and it exactly matches the tree-shape of how conversations branch.

Why the tree specifically¶

Alternatives exist:

Hash chain of blocks (what vLLM’s V1 prefix cache does): each block is keyed by hash(prev_block_hash, block_tokens). Lookup is O(1) per block; the “tree” is implicit in the hash chain. This works well and is simpler to implement.
Radix tree (SGLang): explicit tree, O(prompt_len / branching_factor) lookup, cheap traversal, and — crucially — fast batch prefix matching when many concurrent requests want to look up shared prefixes.

The fast batch matching matters at high concurrency on agentic workloads. When 100 requests arrive per second and 80% of them share a system prompt, the radix tree amortizes lookup cost across the batch.

The SGLang paper reports up to 6.4× throughput vs vLLM on prefix-heavy workloads that matched the design assumption. On unique prompts the two are within 5%. Note: vLLM’s V1 prefix cache has closed most of this gap since; on standard chat benchmarks in 2026 SGLang leads by ~20-40% on prefix-heavy traffic and matches on unique-prompt traffic.

The Zoho playbook (do this at work in Week 1 of Phase 4)¶

This is not a suggestion. This is the highest-ROI move in the roadmap.

Step 1 — Measure your prefix-hit potential (1 day)¶

Sample a day of your production agent traffic. For each request, compute:

prompt_len — tokens in the prompt
shared_prefix_len — longest token prefix shared with any other request in the same session (or across sessions if you can attribute)

Compute the ratio: sum(shared_prefix_len) / sum(prompt_len) across the daily corpus. This is your prefix cache hit rate ceiling.

Agentic workloads typically land 60-90%. The multi-turn tool-calling traces will be at the high end. Anything above 40% is a fat win.

Step 2 — Run the A/B (2 days)¶

Stand up two engines on identical hardware:

vLLM with --enable-prefix-caching and prefix-cache-aware routing at the load balancer (route requests with a shared session ID to the same replica).
The current production engine (whatever it is).

Replay a captured trace through both. Compare TTFT p50/p95/p99 and end-to-end tokens/sec/GPU.

Expected: TTFT p95 drops 30-70%, throughput up 2-4× on the cache-hot subset. If you see less than 20% improvement, either your traffic isn’t as prefix-heavy as you thought, or the routing isn’t actually landing sessions on the same replica.

Step 3 — Ship the write-up (1 day)¶

Internal doc: “Prefix-cache-aware routing for the agent platform: measured 74% cache hit rate on production traffic, resulting in 38% lower p95 TTFT and 2.3× throughput per H100.”

That document is your credibility. It funds every other phase of this roadmap on company time. Write it.

Step 4 — The scaling story¶

Once prefix caching is landed at single-node, the next win is prefix-cache-aware routing at the LB: don’t just hope sessions land on the same replica, deterministically route them there by hashing on session ID or the first K tokens of the prompt. This is a Phase 7 topic in depth, but you’ll have laid the groundwork in Phase 4.

The SGLang source code map (verified paths mid-2026)¶

Path	Read for
`python/sglang/srt/managers/scheduler.py`	The engine loop and iteration-level scheduler. Analog of vLLM’s scheduler.py.
`python/sglang/srt/mem_cache/radix_cache.py`	The paper’s mechanism. `RadixCache` class, `match_prefix(params: MatchPrefixParams) -> MatchResult`, insert, evict. Read this file completely.
`python/sglang/srt/mem_cache/memory_pool.py`	The physical KV block pool. Analog of vLLM’s kv_cache_manager.
`python/sglang/srt/model_executor/`	Forward-pass orchestration.
`python/sglang/srt/constrained/`	XGrammar/Outlines integration for structured decoding.
`python/sglang/lang/`	The frontend DSL (SGLang-the-language, distinct from SGLang-the-runtime). Skim; runtime is what you care about for inference engineering.

File 11 (11_sglang_source_map.md) expands this with reading questions per file.

SGLang’s other wins beyond RadixAttention¶

While you’re there, note the other design choices that make it strong:

Structured output first-class. XGrammar is deeply integrated; JSON schema constraint compilation is a normal feature not an add-on. Directly matches agentic tool-calling needs.
DSL for prompt programs. The sgl.gen, sgl.select, sgl.fork primitives let you express agent flows in Python and the runtime optimizes across them (shares prefixes automatically, does parallel decoding of independent branches). For your work this is worth prototyping.
Fast constrained decoding via speculative masking. The paper shows how structured output overhead can be amortized across the radix cache too — the FSM state can be cached per prefix.

SGLang vs vLLM in 2026: choose which¶

Situation	Choose
Agentic / multi-turn / high prefix overlap	SGLang (still the leader on this profile)
Structured output / JSON tool calling heavy	SGLang (XGrammar-native)
Broadest hardware (AMD, TPU, Intel)	vLLM
Broadest model support (bleeding-edge model on day 1)	vLLM
Best production ecosystem (K8s operators, docs)	vLLM
Best speculative decoding for EAGLE-2/3	vLLM (SGLang’s is experimental)
Best community for a first OSS PR	Either; vLLM has larger surface area

For a Zoho on-prem agent product? Both. SGLang for the agent tier, vLLM for the utility-model tier. You’ll be the person who can defend the architecture in review.

Reading exercise¶

Open radix_cache.py. Draw the RadixCache class on paper: TreeNode, match_prefix, insert, evict.
Simulate on paper: 3 requests with prompts “A B C D E”, “A B C F G”, “A B H I”. Show the tree after each insertion. Show the eviction choice when memory pressure requires freeing one leaf.
Now the killer question: what happens if two requests arrive simultaneously and both try to insert paths that share a new prefix not yet in the tree? Trace the locking (or lack thereof) in the code and identify whether SGLang does redundant compute in that case.

Question 3 is a plausible “good first issue” hunt.

The intuition to internalize¶

KV is a tree, not a slab, not a table. Agentic conversations branch; your KV cache should branch too. SGLang saw this first and made a data structure that matches the shape of the workload. When you build your mini-engine (file 09), the radix cache is the single most intellectually satisfying subsystem to implement, and the one you’ll understand deepest because your day job is the workload it was designed for.

RadixAttention is the paper you own after this phase. Cite it in Zoho design docs. Present it in an internal tech talk. Make it your thing.