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. Programs over chats, runtime over strings
Problem → language → runtime → result
3. From chat to LM program
Many dependent calls, control flow, structured inputs and outputs
4. Hard to write, wasteful to run
Two problems and one answer: a frontend language plus a co-designed runtime
5. Seven primitives inside Python
extend, gen, select, fork, join, image, video; Python supplies the rest
6. The interpreter as an async stream
Primitives go to a background stream like CUDA kernel launches; reading a result waits
7. Four patterns of shared prefixes
Few-shot, self-consistency, multi-turn chat, tree-of-thought
8. The cache is a tree
A radix tree holds every request's KV cache; edges are token sequences
9. Insert, match, split, evict
How the tree lives under traffic: two chats, few-shot and self-consistency
10. The cache never fights the batch
A reference counter protects running requests; zero-count leaves get evicted
11. Longest shared prefix first
Sorting the queue by matched prefix equals a depth-first walk of the tree
12. Frontend hints and many GPUs
fork sends the shared prefix first; tensor parallel needs no sync; a router keeps a meta-tree
13. Constraints in characters, the model in tokens
A regex becomes a finite state machine that masks invalid tokens at every step
14. The compressed automaton jumps forward
A chain of singular transitions collapses into one edge decoded in a single pass
15. Speculation for closed APIs
One call instead of two: the model runs past the stop, the interpreter matches the remainder
16. Up to 6.4× throughput
Llama-2-7B on A10G versus Guidance, vLLM and LMQL; latency down by up to 3.7×
17. Every piece pays, the tree is free
Cache hits grow the batch and cut latency; the tree costs 0.3 %
18. Large models, images, Chatbot Arena
Tensor parallel keeps the trend; multi-modal up to 6×; in production up to 74 % hits
19. Where the recipe falls short
Starvation under greedy scheduling, a single memory tier, distorted probabilities of the compressed automaton
20. What to take from the paper
Program structure is a resource; the cache is a tree; constraints compress