SGLang: Executing Structured Language Model Programs
How a seven-primitive language and a radix-tree KV cache runtime bought up to 6.4× throughput
Slide contents
1. SGLang: Executing Structured Language Model Programs
How a seven-primitive language and a radix-tree KV cache runtime bought up to 6.4× throughput
2. SGLang grew from repeated computation
Zheng, Sheng and colleagues: programs know more than servers
3. Programs over chats, runtime over strings
Problem → language → runtime → result
4. Pages store, the tree reuses
vLLM shares a prefix declared in advance; SGLang finds and keeps any shared prefix itself
5. From chat to LM program
Many dependent calls, control flow, structured inputs and outputs
6. Hard to write, wasteful to run
Two problems and one answer: a frontend language plus a co-designed runtime
7. Seven primitives inside Python
extend, gen, select, fork, join, image, video; Python supplies the rest
8. The interpreter as an async stream
Primitives go to a background stream like CUDA kernel launches; reading a result waits
9. Four patterns of shared prefixes
Few-shot, self-consistency, multi-turn chat, tree-of-thought
10. The cache is a tree
A radix tree holds every request's KV cache; edges are token sequences
11. Insert, match, split, evict
How the tree lives under traffic: two chats, few-shot and self-consistency
12. The cache never fights the batch
A reference counter protects running requests; zero-count leaves get evicted
13. Longest shared prefix first
Sorting the queue by matched prefix equals a depth-first walk of the tree
14. Frontend hints and many GPUs
fork sends the shared prefix first; tensor parallel needs no sync; a router keeps a meta-tree
15. Constraints in characters, the model in tokens
A regex becomes a finite state machine that masks invalid tokens at every step
16. The compressed automaton jumps forward
A chain of singular transitions collapses into one edge decoded in a single pass
17. Speculation for closed APIs
One call instead of two: the model runs past the stop, the interpreter matches the remainder
18. Compare programs, not tokens
Maximum throughput and single-program latency come from different experiments
19. Up to 6.4× throughput
Llama-2-7B on A10G versus Guidance, vLLM and LMQL; latency down by up to 3.7×
20. Every piece pays, the tree is free
Cache hits grow the batch and cut latency; the tree costs 0.3 %
21. Large models, images, Chatbot Arena
Tensor parallel keeps the trend; multi-modal up to 6×; in production up to 74 % hits
22. Where the recipe falls short
Starvation under greedy scheduling, a single memory tier, distorted probabilities of the compressed automaton
23. What to take from the paper
Program structure is a resource; the cache is a tree; constraints compress
24. SGLang expanded to large MoE serving
DeepSeek: separate prefill and decode, expert parallelism
25. HiCache moved caching beyond the GPU
The paper’s future direction became hierarchical storage
26. Prefix reuse became a shared concern
Different data structures serve the same need