SGLang: Efficient Execution of Structured Language Model Programs — L2 #

1. TL;DR #

A co-designed frontend DSL + serving runtime for multi-call LLM programs. The runtime keeps finished KV caches in a radix tree with LRU eviction and schedules requests longest-shared-prefix-first (provably DFS-optimal), and compresses constrained-decoding FSMs so single-path token runs decode in one forward pass. Up to $6.4\times$ throughput vs vLLM/Guidance/LMQL.

2. Q1 / Q2 / Q3 #

Q1 — 痛点 (pain point) #

Modern LLM usage is programmatic: agents, tree/skeleton-of-thought, few-shot, JSON extraction, RAG, and multi-turn chat all issue multiple dependent generation calls ("LM Programs"). Two problems follow. (1) Programming these is tedious — string manipulation, brittle output parsing, manual parallelism. (2) Executing them is inefficient: state-of-the-art engines (vLLM, TGI, TRT-LLM) run "without direct knowledge of the workload," so they recompute the KV cache for each request even when calls share large prefixes (system prompts, few-shot examples, forked branches, chat history), and they decode constrained output one token at a time even when the format admits only one next token for many steps.

Q2 — 方法 (method) #

Two coupled parts (Fig. 1):

• Frontend DSL embedded in Python with generation primitives (gen, select, extend/+=) and parallelism primitives (fork, join), plus image/video. An interpreter runs each prompt as an async stream in a background thread (intra-program parallelism); a compiler can trace it to a dataflow graph.
• SGLang Runtime (SRT) with three optimizations: RadixAttention (retain KV cache in a radix tree with LRU eviction + cache-aware, longest-shared-prefix-first scheduling), compressed FSM (merge singular-transition edges so multi-token constant runs decode in one forward pass), and API speculative execution (over-generate past a stop token on black-box APIs to satisfy later gen calls, saving repeated input-token billing).

核心技术壁垒: treating the KV cache as a tree-structured LRU cache whose eviction interacts correctly with the running batch via per-node reference counters, and proving that a cheap greedy schedule (longest-shared-prefix-first) equals the offline-optimal DFS traversal (Theorem 3.1). The hard part is not the radix tree data structure — it is making eviction, continuous batching, and cache-aware scheduling coexist without cache thrashing while sharing one memory pool between cached and live tokens.

Q3 — 结果 (results) #

Up to $6.4\times$ throughput and $3.7\times$ latency reduction on Llama-7B; up to $6\times$ on multi-modal LLaVA; cache-aware scheduling reaches 96% of the theoretical-optimal hit rate on average (hit rate 50–99% across workloads); RadixAttention overhead is <0.3% even with zero reuse; compressed FSM gives $1.6\times$ on JSON decoding. Production: one month in Chatbot Arena gave 52.4% (LLaVA-Next-34B) / 74.1% (Vicuna-33B) cache hit and $1.7\times$ lower first-token latency.

3. 架构 / 方法图 #

Paper's Figure 1 (caption: "System architecture: An interpreter executes language primitives with optimized runtime."). This pins the system scope: it is a serving framework (not training), covering both prefill and decode. The frontend interpreter owns the program-level control flow and parallelism; the runtime (SRT) owns KV memory, scheduling, and kernel dispatch. The two halves can run independently but are co-designed — e.g. the frontend sends "prefix hints" for fork so the runtime inserts the shared prefix into the tree before the branches.

Paper's Figure 2 (caption: "The implementation of a multi-dimensional essay judge in SGLang utilizes the branch-solve-merge prompting technique. Primitives provided by SGLang are shown in red."). This is the concrete "LM Program" the runtime optimizes: fork creates three parallel branches sharing a common prefix (a RadixAttention reuse opportunity), and the final JSON regex argument triggers compressed-FSM decoding. The equivalent OpenAI-API program is $2.1\times$ longer.

The request lifecycle and the scheduler/memory-manager separation demanded by a serving framework:

The scheduler is FCFS replaced by longest-shared-prefix-first (a greedy priority order). The memory manager is a radix tree whose allocation unit is one token per page (non-contiguous paged layout); cached tokens and running requests share one pool, so a large waiting batch can evict all cached tokens to grow batch size. Distribution: tensor parallelism needs no extra sync (each GPU shards its own KV, tree ops are identical); data parallelism uses a router meta-tree (§A.4).

4. 作者证明 #

The load-bearing formal result is Theorem 3.1: longest-shared-prefix-first scheduling achieves the optimal cache hit rate, and equals a DFS traversal of the batch's radix tree, given cache size $\geq$ max request length.

Notation table

Cache hit rate (the scheduler's objective):

$$\text{cache hit rate} = \frac{\text{number of cached prompt tokens}}{\text{number of prompt tokens}}$$

Physical meaning: the fraction of prompt-token KV computations skipped. Higher hit rate → less prefill compute + less memory → larger batch → higher throughput and lower first-token latency.

Lower bound on compute — every distinct edge must be computed at least once (shared prefixes counted once, not per request):

$$C \geq \sum_{e \in \text{edges}(T)} |e|$$

Equality under DFS — a DFS with a big-enough cache computes each edge exactly once, hitting the bound:

$$C = \sum_{e \in \text{edges}(T)} |e|$$

The batch-level hit rate equals $1 - C / (\sum_{r\in R}\text{prefill tokens})$, so minimizing $C$ maximizes hit rate — hence DFS is optimal.

6 minimum checks

1. Why sum over edges (not requests): each unique prefix edge's KV is a shared physical quantity computed once; summing over requests would double-count shared prefixes. The sum-over-edges is exactly the irreducible work.
2. Why the $\geq$ becomes $=$: only when the cache is large enough that a common prefix is not evicted while its subtree is being processed (cache $\geq$ max request length = longest root-to-leaf path). Otherwise a prefix gets recomputed and $C$ exceeds the bound.
3. Monotonicity / boundary: the optimum is at the DFS ordering boundary, not an interior tradeoff — any deviation from DFS (e.g. switching subtrees mid-traversal) risks evicting an in-use prefix, strictly increasing $C$. The cache-size condition is the boundary that breaks the guarantee if violated.
4. Longest-shared-prefix-first ≡ DFS (induction): base — first request cached its whole root-to-node path, a valid DFS start; induction — an unvisited node whose lowest common ancestor with visited nodes is deepest on the cached path has the longest shared prefix, and selecting it is a valid DFS extension.
5. Online degradation is bounded: when a new batch arrives DFS is disrupted, but the schedule reduces to DFS on the augmented subtree rooted at the deepest still-cached node ($\text{longest}(C)$), recursing through $C^{(1)},\dots,C^{(k)}$ until a single leaf remains — approximating DFS on the "augmented part."
6. First-order mapping (verify reported numbers, not fit): plugging real workloads into the objective, cache-aware scheduling reaches 96% of optimal on average (Fig. 13), hit rate spans 50–99%, and production hit rates are 52.4% / 74.1% — consistent with the theorem's claim that a cheap greedy order nearly matches the DFS optimum rather than needing an expensive search.

Footnote caveat (honest): actual computation differs from the proof because the unpredictable number of output tokens can force KV recomputation, and greedy scheduling can cause starvation (left unsolved). This is a formal offline-optimality proof plus an online approximation argument — genuine, not merely empirical.

5. 实验与数据 #

Scheduling & resource management (the framework-specific asks):

• Granularity: request-level batching with token-page KV allocation; scheduling reorders whole requests by matched-prefix length.
• Preemption / admission: no explicit preemption; under memory pressure the tree evicts LRU leaves first (freeing ancestors only once they become leaves), and a large waiting batch may evict all cached tokens to grow batch size. No fairness guarantee — greedy order can starve.
• Memory: allocation unit = 1 token/page, non-contiguous; eviction = LRU on a radix tree with per-node reference counters so in-batch nodes are never evicted; swap to CPU/disk is only future work.



Paper's Figure 3 (caption abridged: "Examples of RadixAttention operations with an LRU eviction policy … green for newly added, blue for cached-accessed, red for evicted."). This is the mechanism's core: node splitting (step 4) lets two chat sessions share a system prompt; leaf eviction (steps 5, 8, 9) reclaims memory in LRU order; step 7 shows few-shot examples shared across a batch. It demonstrates the four sharing patterns a table-based cache cannot express.



Paper's Figure 5. The load-bearing throughput result: up to $6.4\times$ over baselines across MMLU, HellaSwag, ReAct, ToT/SoT, JSON, multi-turn chat, and RAG. Note the regime where it barely wins — long-output multi-turn chat, where decoding dominates and prefixes barely overlap.



Paper's Figure 6. Up to $3.7\times$ latency reduction; RadixAttention cuts first-token latency by skipping prefill of cached prefixes — the effect is largest for short-output, high-sharing workloads.



Paper's Figure 8. (a,b) confirm the causal chain: higher hit rate → larger batch → higher throughput + lower latency. (c) shows each component is load-bearing — removing tree structure, cache-aware scheduling (→FCFS/random), frontend parallelism, or the fork hint each degrades performance, evidencing the frontend↔runtime co-design.

Workload characterization — where it wins / loses:

Workload regime	SGLang	Baseline (vLLM/Guidance/LMQL)	Why
few-shot / shared-prefix, high concurrency	up to $6.4\times$, hit rate 50–99%	recompute per request	RadixAttention reuses prefix KV, larger batch
JSON / constrained decode	$1.6\times$	1 token / forward pass	compressed FSM decodes multi-token runs at once
multi-turn chat, short output	strong speedup	—	prefix (history) reuse dominates cost
multi-turn chat, long output	"almost no speedup"	—	decode-bound, little cross-session sharing
zero-reuse (ShareGPT)	<0.3% overhead	baseline	tree ops are linear + tiny, safe to leave on

Metric definitions (honest reading): throughput = programs/second at max batch; latency = average of single unbatched programs. Baselines: vLLM v0.2.5 (an earlier version — RadixAttention was later partially upstreamed to vLLM), Guidance v0.1.8 (llama.cpp, no batching/parallelism), LMQL v0.7.3 (HF Transformers, slow token-level). Guidance/LMQL are excluded from several benchmarks for lacking batching / TP — a fairness caveat: those baselines are weak on the harder workloads.



Paper's Table 2. 0.18→1.15 image/s and 0.02→0.10 frame/s (≈$6\times$), driven by hashing input images as radix keys so identical images reuse image-token KV.

6. 论证链 #

#	Step	Support
1	LM Programs make multiple dependent calls that share prefixes and need constrained output.	§1 taxonomy; Fig. 2 branch-solve-merge example
2	Existing engines recompute shared-prefix KV and decode constrained output token-by-token.	§1, §3 (workload-agnostic engines)
3	Retaining KV in a radix tree with LRU eviction enables automatic multi-pattern prefix reuse.	§3 RadixAttention; Fig. 3 nine-step trace
4	Scheduling requests longest-shared-prefix-first maximizes the hit rate and equals offline-optimal DFS.	Theorem 3.1; proof §A.3
5	Compressing singular-transition FSM edges lets constant token runs decode in one forward pass.	§4; Fig. 4(b,d)
6	Together these yield up to $6.4\times$ throughput / $3.7\times$ latency, at <0.3% overhead, 96% of optimal hit rate.	Figs. 5,6,8; §6.3

7. 实现 cross-reference #

The runtime radix cache is public in the SGLang repo (evolved past the paper but the paper's primitives are directly visible):

• Longest-shared-prefix matching (the scheduler's ranking key): match_prefix in sglang/python/sglang/srt/mem_cache/radix_cache.py:355.
• Insertion of finished-request KV back into the tree: insert at sglang/python/sglang/srt/mem_cache/radix_cache.py:415.
• LRU leaf-first eviction (the paper's "evict least recently used leaf first"): evict at sglang/python/sglang/srt/mem_cache/radix_cache.py:563, which skips any node with lock_ref > 0 (see the eviction guard at radix_cache.py:789).
• The reference-counter mechanism that keeps in-batch nodes un-evictable — the single hardest correctness detail (§ core 技术壁垒): inc_lock_ref / dec_lock_ref at radix_cache.py:592 and radix_cache.py:607; the running batch increments on schedule and decrements on finish. This is exactly Alg. 1's increase_ref_counter / decrease_ref_counter.

核心技术壁垒 (dedicated note): the replication difficulty is not the radix tree — it is the invariant that cached tokens and live tokens share one memory pool while eviction must never touch a node any running request depends on. Implemented as lock_ref on every node: eviction (radix_cache.py:789) treats lock_ref > 0 as pinned, and node-splitting propagates lock_ref to the new child (radix_cache.py:681) so a split prefix stays pinned. Get this wrong and you either corrupt in-flight attention or deadlock the pool.

关键实现细节 (easy-to-miss tricks):

1. Frontend prefix hint on fork: the interpreter sends the shared prefix first as a hint so the runtime inserts it into the tree before the branches arrive — without it, concurrent branches race and the shared prefix may be computed multiple times (ablation "No Frontend Hint" degrades performance).
2. Retokenization after a compressed-edge jump-forward: after decoding a long constant run in one pass, the emitted characters must be re-tokenized with the original tokenizer (not naively split), because string→token mapping is not one-to-one (e.g. {"summary": " must tokenize as the model expects); skipping this silently corrupts the KV/token stream.