1. What is it?#
An LLM serving system whose distinguishing contributions are RadixAttention (a radix-tree prefix cache) and a frontend language for structured LLM programs.
vLLM's thesis: memory management is the bottleneck → PagedAttention
SGLang's thesis: LLM programs have structure (shared prefixes, branching,
constrained output) → exploit itBoth are right. The systems have converged substantially — vLLM has prefix caching, SGLang has paged memory — but their origins explain their strengths.
2. RadixAttention — the core idea#
Instead of a flat hash table mapping block-hash → block (vLLM’s approach), maintain a radix tree of token sequences.
root
│
"You are a helpful assistant."
╱ ╲
"Answer in JSON." "Be concise."
╱ ╲ │
"What is X?" "What is Y?" "Summarize:"Each node holds the KV blocks for its token span. A new request walks the tree from the root, matching as far as it can, and reuses everything along the path.
Why a tree beats a hash table#
1. BRANCHING STRUCTURE IS EXPLICIT
Agent workflows, tree search, and multi-sample generation naturally
produce branches from a common prefix. The tree represents this directly.
2. LRU EVICTION RESPECTS THE HIERARCHY
Evicting a leaf is safe. Evicting an interior node would orphan its
children — the tree makes this constraint explicit and easy to enforce.
A flat hash table can evict a middle block and silently break the chain.
3. LONGEST-PREFIX MATCH IS THE NATURAL OPERATION
Tree traversal IS longest-prefix matching. No separate logic.
4. THE SCHEDULER CAN SEE SHARING
Requests sharing a tree node can be scheduled together to maximize
cache locality — "cache-aware scheduling."That last point is SGLang’s scheduling contribution: order the waiting queue to group requests that share prefixes, so the shared KV stays hot and batches form around common prefixes.
3. Simple analogy#
A filing system organized by folder hierarchy versus by document hash.
Hash table: every document has an ID; you look up by ID. Fine for exact retrieval, but you can’t see that documents A and B are both in the “Q3 Reports” folder, and deleting a folder that documents still reference is a hazard you must guard separately.
Radix tree: the hierarchy is the structure. Shared context is a shared parent. Deleting is safe by construction (leaves first). And you can see, at a glance, which documents share context — which lets you process them together.
4. Tiny example — the frontend language#
SGLang’s second contribution is a DSL for LLM programs:
import sglang as sgl
@sgl.function
def multi_turn_qa(s, document, questions):
s += sgl.system("You are a document analyst.")
s += sgl.user(f"Document:\n{document}") # ← long, shared prefix
s += sgl.assistant("I've read the document.")
for i, q in enumerate(questions):
# fork: each question branches from the SAME cached prefix
forks = s.fork(1)
forks[0] += sgl.user(q)
forks[0] += sgl.assistant(sgl.gen(f"answer_{i}", max_tokens=200))
@sgl.function
def structured_extract(s, text):
s += sgl.user(f"Extract entities from: {text}")
s += sgl.assistant(
"{" +
'"name": "' + sgl.gen("name", stop='"') + '", ' +
'"role": "' + sgl.gen("role", stop='"') + '"}'
)
What the runtime does with this:
- The document prefix is prefilled once and shared by every question via the radix tree.
forkcreates tree branches with copy-on-write KV sharing.- The interleaved literal text in
structured_extractis not generated — it’s appended directly, so the model only generates the variable parts. This is both faster and guarantees valid structure.
That third point is a genuinely different capability: constrained generation by construction rather than by masking.
5. Architecture#
┌────────────────────────────────────────────────────────┐
│ FRONTEND (optional) │
│ Python DSL: gen, fork, select, system/user/assistant │
│ compiles to a program graph │
└────────────────────┬───────────────────────────────────┘
│ (or plain OpenAI-compatible HTTP)
┌────────────────────▼───────────────────────────────────┐
│ ROUTER (multi-replica) │
│ prefix-aware routing: send requests with shared │
│ prefixes to the replica that has them cached │
└────────────────────┬───────────────────────────────────┘
┌────────────────────▼───────────────────────────────────┐
│ SCHEDULER │
│ cache-aware ordering (group by shared prefix) │
│ continuous batching, chunked prefill │
└────────────────────┬───────────────────────────────────┘
┌────────────────────▼───────────────────────────────────┐
│ RADIX TREE + PAGED KV │
│ tree nodes → block ranges, refcounts, LRU on leaves │
└────────────────────┬───────────────────────────────────┘
┌────────────────────▼───────────────────────────────────┐
│ RUNTIME │
│ FlashInfer attention kernels, CUDA graphs, TP/EP │
│ constrained decoding (compressed FSM / xgrammar) │
└────────────────────────────────────────────────────────┘The prefix-aware router is notable: SGLang ships one, whereas with vLLM you typically build it yourself (Section VIII.06).
6. Where SGLang wins#
WORKLOAD WHY
Agentic loops long shared prefix (tools + scratchpad),
many short generations
Multi-sample generation (n>1) all samples share the prompt tree
Tree search / self-consistency branching is native
Structured output at scale compressed FSM constrained decoding is fast
Few-shot classification huge shared prefix, tiny generation
Document QA with many questions one document, many branches
Multi-turn chat at high volume deep prefix reuse across turnsReported speedups on these workloads range from 2x to 6x over baseline systems — almost entirely from cache reuse, not from faster kernels.
Where it wins less: single-turn, unique-prompt workloads with no sharing. There, it performs comparably to vLLM.
7. Constrained decoding#
SGLang’s approach to structured output is worth understanding because it’s meaningfully faster than the naive one:
NAIVE: at each step, run the grammar/regex automaton to compute the set of
allowed tokens, build a mask over the 128k vocabulary, apply it.
Cost: 0.5-5 ms per token. Can dominate ITL.
COMPRESSED FSM: precompute, per FSM state, the allowed-token bitmask.
Cache masks by state. At generation time it's a lookup.
Additionally: when the FSM has only ONE valid continuation for
several tokens (e.g. the literal `{"name": "` ), emit them all at
once WITHOUT running the model — "jump-forward decoding."
Cost: ~0.02 ms per token, and fewer model steps.Jump-forward decoding is the clever part: in a JSON schema, much of the output is literal structure the model doesn’t need to generate. Skipping it saves both time and the risk of the model getting it wrong.
8. Production implications#
- Evaluate SGLang if your workload has heavy prefix sharing. Agentic, few-shot, multi-sample, and document-QA workloads are its home ground.
- Use its router for multi-replica prefix affinity — it solves a problem you’d otherwise build yourself.
- Consider the frontend DSL for agent workloads. It’s not required (the HTTP API is OpenAI-compatible), but the fork/share semantics are hard to express otherwise.
- Structured output is a genuine strength. If you generate a lot of JSON, measure the ITL difference against a naive constrained-decoding implementation.
- Feature and model support track vLLM closely but not identically; check your model.
9. Common mistakes#
Expecting a win on unique-prompt workloads. The gains come from sharing.
Not using the router and then getting poor cache hit rates across replicas.
Assuming prefix caching is free capacity. Cached blocks occupy the same pool as active requests; a large cache reduces concurrency.
Ignoring constrained-decoding overhead in other systems and then attributing the difference to something else.
10. Hands-on exercise#
A. Measure the sharing win. Build a workload with a 2,000-token shared prefix and 100 different short questions. Run it on vLLM (with prefix caching) and SGLang. Compare TTFT and throughput. Is there a difference, and where does it come from?
B. Fork semantics. Use the SGLang frontend to generate 8 samples from one prompt with
fork. Measure memory and time versus 8 independent requests.
C. Constrained decoding. Generate 1,000 JSON objects with a schema, using (i) SGLang’s constrained decoding and (ii) a naive masking implementation. Compare ITL. Measure how many tokens jump-forward decoding skipped.
D. Router evaluation. Run 4 replicas with SGLang’s router and with round-robin. Measure aggregate prefix cache hit rate and p95 TTFT.
E. Read the radix tree. Read SGLang’s radix_cache.py. Find: insertion, longest-prefix
match, and the LRU eviction that respects the tree structure.
11. Interview questions#
- What is RadixAttention and how does it differ from a flat prefix hash table?
- Give three advantages of a tree structure for prefix caching.
- What is cache-aware scheduling?
- What is jump-forward decoding and why is it faster than masking?
- Which workloads favor SGLang, and why?
- What does SGLang’s router do that a standard load balancer doesn’t?
- When would SGLang and vLLM perform similarly?
12. Further reading#
- [ESTABLISHED] Zheng et al., “SGLang: Efficient Execution of Structured Language Model Programs” (2023/2024)
- [REFERENCE] SGLang documentation and source (
python/sglang/srt/mem_cache/radix_cache.py) - [REFERENCE] xgrammar / compressed FSM constrained decoding
- Next: 13 — TGI, Triton, ONNX Runtime