SGLang: Efficient Execution of Structured Language Model Programs

Many real applications do not send one prompt and get one answer. An agent loops through reasoning and tool calls, each time resending a growing history. A few-shot classifier sends the same examples with every question. Self-consistency samples many answers to one prompt. A tree-of-thought program branches. A JSON extractor forces the model to produce a fixed structure with a few variable fields. The authors call these "language model programs", and they share two properties: many calls with overlapping prompts, and structured outputs.

SGLang, from a Stanford and Berkeley team (Lianmin Zheng, Ying Sheng, Ion Stoica, Joseph Gonzalez and others), is a serving runtime plus a small Python-embedded language for writing such programs. Its main runtime idea is RadixAttention. Instead of throwing away a request's KV cache when it finishes, SGLang keeps it in a radix tree keyed by token sequences. A new request walks the tree, reuses the longest cached prefix, and computes only the rest. When memory fills, the least recently used leaves are evicted. A cache-aware scheduler orders waiting requests to maximize prefix sharing, which avoids thrashing the cache.

The second idea is a compressed finite-state machine for constrained decoding. When output must match a regular expression, such as a JSON schema, standard engines mask disallowed tokens and decode one token at a time, even through stretches where only one continuation is possible, like {"summary": ". SGLang merges those forced stretches so they are processed in a single forward pass. For API-only models, an "API speculative execution" trick lets one call generate past a stop condition to satisfy a later call too, saving input-token costs.

Across agents, tree-of-thought, few-shot benchmarks, JSON decoding, retrieval pipelines and multi-turn chat, SGLang reached up to 6.4× the throughput of vLLM, Guidance and LMQL. On Chatbot Arena, where it served open models for a month, 74.1% of Vicuna-33B's prompt tokens came from cache, cutting time to first token by 1.7×.

Enterprise deployments are mostly language model programs: agents, retrieval pipelines with fixed instructions, extraction to schemas, few-shot classifiers. This paper shows how much cost hides in recomputing the same prefixes, and how to stop paying it.

Prompt order decides cache reuse. Reuse only works on identical prefixes. Put stable content first, such as system instructions, tool definitions and few-shot examples, and variable content (the user's question, retrieved documents) after. A timestamp or user name at the top of a prompt can silently defeat caching for everything below it.

Agents benefit most. Each agent step resends the full history; with prefix caching, each step pays only for the new tokens. That changes both latency and the GPU count needed for an agent workload.

Structured output can be faster, not just safer. Constrained decoding is often treated as a cost; with compressed state machines, the fixed parts of a schema are almost free. If a customer needs JSON, use the engine's structured-output support rather than parsing free text and retrying.

Hit rate is a metric to track. In production, cache hit rate directly affects throughput and first-token latency. Monitor it, and investigate drops after prompt changes.

The ideas are now everywhere. Automatic prefix caching and fast constrained decoding exist in vLLM and other engines too; the paper's baseline was an older vLLM without them. Choose an engine by measuring on the customer's workload, not by this paper's numbers alone.