SGLang: How Program Structure Sped Up LLM Inference

Continuing the theme of vLLM and PagedAttention, which I covered earlier, I decided to continue with the paper "SGLang: Efficient Execution of Structured Language Model Programs". vLLM asked how to place the KV cache more efficiently in memory. SGLang takes the next step: how can a system avoid recomputing exact prefixes already processed during earlier model calls?

The team from Stanford, UC Berkeley, Shanghai Jiao Tong, and Texas A&M looked not at a single request but at an entire LLM program: multiple model calls, branching, parallel generations, shared context, and structured output. The central idea of the work, published at NeurIPS 2024, is that when the engine can see this structure, it can optimize the whole workload.

The basic engineering ideas are these:

1️⃣ Reuse — RadixAttention A KV cache depends on the exact sequence of preceding tokens. SGLang keeps references to cached states in a radix tree—a compressed prefix tree—and finds the longest previously computed prefix. The GPU computes only the remaining suffix. The effect is less repeated prefill work, fewer duplicates in memory, lower time to first token, and higher throughput. This works best with long shared system prompts, few-shot examples, repeated RAG context, and reasoning branches.

2️⃣ Scheduling around expensive state Saving a cache is not enough: it has to be used before eviction. The scheduler therefore favors requests with longer matches, while an LRU policy removes long-unused leaves that are not referenced by active requests. The effect is more cache hits and more useful batches. CPU bookkeeping is small, but there is a fairness risk: a request without a useful match can wait longer.

3️⃣ Using determinism If a JSON grammar permits only one continuation along some segment, a compressed finite-state machine merges that segment and processes it in one pass instead of several steps. For closed APIs, the authors also proposed generating text ahead of a stop marker: if that tail matches the program's next operation, it can be reused. It is an interesting idea, but RadixAttention became the system's foundation.

In the authors' experiments on their workloads, SGLang delivered up to 6.4x higher throughput than the contemporary Guidance, vLLM, and LMQL baselines. This headline maximum combines several optimizations rather than measuring RadixAttention alone. The cache benefit falls when prefixes rarely repeat or long answer generation dominates the runtime.

What remains today? SGLang now presents itself less as a language for LLM programs and more as a complete serving framework. RadixAttention is still at its core, with the hierarchical HiCache extending KV storage from GPU to RAM and external storage. Around it, the project has grown continuous batching, paged attention, speculative decoding, prefill-decode disaggregation, distributed inference, quantization, and an OpenAI-compatible API. The broader idea of constrained structured output remains, but the original compressed-FSM jump-forward path was removed in 2025 to simplify maintenance. JSON Schema, regex, and EBNF constraints now run through dedicated grammar backends — XGrammar by default, plus Outlines and llguidance.

Overall, for me this paper continues the vLLM story. Performance often grows not from faster computation but from choosing the right systems abstraction. vLLM organized KV-cache placement and the sharing of common blocks. SGLang automated the discovery and reuse of arbitrary exact prefixes across calls, then tied that reuse to scheduling. The optimization target was not the model, but the work around it.

#AI #Research #Software #Architecture #Engineering #DistributedSystems #Performance #SystemDesign