PaperlayerView exact revision on arXiv

Source-linked AI summary

SGLang: Efficient Execution of Structured Language Model Programs

Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E. Gonzalez, Clark Barrett, Ying Sheng

arXiv:2312.07104v2cs.AIcs.PL

TL;DR

Complex LM programs combine multiple calls, control flow, and structured I/O, but existing systems are difficult to program and inefficient to execute. SGLang addresses this with a Python-embedded frontend and optimized runtime, achieving up to 6.4× higher throughput across diverse workloads and systems.

  • Problem

    Existing systems make LM programs difficult to develop and execute efficiently because they require cumbersome orchestration and miss workload-specific reuse opportunities.

  • Method

    SGLang combines a frontend language with primitives for generation and parallelism and a runtime using RadixAttention and compressed finite state machines.

  • Results

    Up to 6.4× higher throughput was achieved across diverse workloads, models, and hardware setups compared with existing programming and inference systems.

  • Takeaways & Limitations

    SGLang provides a framework for efficient programming and execution of structured language model programs and advanced prompting workflows.

  • Takeaways & Limitations

    Future work includes addressing starvation in cache-aware scheduling and extending memory-hierarchy support, fuzzy matching, output modalities, primitives, and compiler optimizations.

Abstract

from arXiv · show

Large language models (LLMs) are increasingly used for complex tasks that require multiple generation calls, advanced prompting techniques, control flow, and structured inputs/outputs. However, efficient systems are lacking for programming and executing these applications. We introduce SGLang, a system for efficient execution of complex language model programs. SGLang consists of a frontend language and a runtime. The frontend simplifies programming with primitives for generation and parallelism control. The runtime accelerates execution with novel optimizations like RadixAttention for KV cache reuse and compressed finite state machines for faster structured output decoding. Experiments show that SGLang achieves up to 6.4x higher throughput compared to state-of-the-art inference systems on various large language and multi-modal models on tasks including agent control, logical reasoning, few-shot learning benchmarks, JSON decoding, retrieval-augmented generation pipelines, and multi-turn chat. The code is publicly available at https://github.com/sgl-project/sglang

1 Introduction

LM programs use multiple LLM calls, control flow, and structured inputs and outputs, but existing systems make them difficult to program and inefficient to execute. SGLang combines a programming frontend with a runtime that exploits these workloads for faster execution.

  • Motivation: LM programs coordinate multiple LLM calls with control flow and structured inputs and outputs for complex tasks.These properties support completing complex tasks, improving quality, composing programs, and integrating them into software systems.
  • Challenges: Programming LM programs is difficult because nondeterministic models require string manipulation, prompt tuning, output parsing, multimodal handling, and parallelism mechanisms.The resulting complexity reduces the readability of even simple programs.
  • Challenges: Executing LM programs is inefficient because current inference engines lack effective reuse of KV caches across calls sharing common prefixes.This causes unnecessary computation and wasted memory during typical batch executions.
  • SGLang: SGLang combines a frontend language with a backend runtime to simplify programming and accelerate execution of LM programs.The two components can work together or function independently.
  • SGLang: RadixAttention maintains an LRU KV-cache mapping in a radix tree, enabling automatic reuse across multiple generation calls.The cache-aware runtime matches, inserts, and evicts cached prefixes efficiently.
  • Results: 6.4× higher throughput was achieved across workloads, models, and hardware setups compared with Guidance, vLLM, and LMQL.Evaluated applications included agent control, reasoning, few-shot learning, JSON decoding, retrieval-augmented generation, chat, and multimodality.

2 Programming Model

SGLang is a Python-embedded programming model for composing generation, structured output, prompt-state, and parallelism operations. Its interpreter and optional graph execution simplify multi-call workflows while supporting runtime optimization.

  • Programming Model: SGLang simplifies multi-call workflows with flexible, composable primitives for string manipulation, API calling, constraints, and parallelism.The programming model is embedded in Python and works with native Python syntax and libraries.
  • Running Example: An essay-judging example uses image and essay inputs, conditional selection, parallel forks, generation, merging, grading, and regex-constrained JSON output.The equivalent OpenAI API-like implementation requires 2.1× as many lines because it manually handles string manipulation and parallelism.
  • Language Primitives: SGLang provides gen, select, extend, fork, join, image, and video primitives for generation, prompt-state control, parallelism, and multimodal inputs.The gen primitive can constrain output with a regular expression, including a JSON schema.
  • Execution Modes: Interpreter execution treats prompts as asynchronous streams, allowing non-blocking primitives to run while Python code continues.SGLang can also compile programs into computational graphs for execution with more optimizations.
  • Comparison: SGLang is a low-level programming system like LMQL and Guidance, distinguished by a co-designed runtime focused on execution efficiency.High-level systems such as DSPy can be compiled to SGLang, which can serve as a backend for better runtime efficiency.
  • Runtime Optimizations: Runtime optimization opportunities include KV-cache reuse, fast constrained decoding, and API speculative execution.These opportunities target inefficiencies arising in multi-call language model programs.

3 Efficient KV Cache Reuse with RadixAttention

RadixAttention systematically reuses KV caches across shared prompt prefixes by storing them in a radix tree and managing them with cache-aware policies. Its scheduling strategy can achieve optimal offline cache hit rates, while online greedy scheduling may cause starvation.

  • Reuse opportunities: Shared prompt prefixes arise across chained calls, forked program instances, and common prompts, creating opportunities for KV-cache reuse.KV-cache computation depends only on prefix tokens, so cached intermediate tensors can support future decoding.
  • RadixAttention: RadixAttention retains prompt and generation-result KV caches in a radix tree, enabling automatic prefix search, reuse, insertion, and eviction.It uses LRU eviction and cache-aware scheduling, while remaining compatible with continuous batching, paged attention, and tensor parallelism.
  • Cache management: The radix tree maps token sequences to paged KV-cache tensors, and LRU eviction removes the least recently used leaf while preserving reusable common ancestors.In continuous batching, reference counters prevent eviction of nodes used by running requests.
  • Cache-aware scheduling: Cache-aware scheduling prioritizes requests with longer matched prefixes, reducing cache thrashing compared with frequently switching among unrelated requests.The batch scheduler uses longest-shared-prefix-first ordering.
  • Scheduling guarantees: A depth-first traversal achieves an optimal cache hit rate when cache size is at least the maximum request length, and longest-shared-prefix-first is equivalent to depth-first order.The online schedule approximates this behavior on the augmented radix tree, but greedy scheduling can cause starvation.
  • Distributed execution: RadixAttention extends to tensor-parallel multi-GPU execution because each GPU maintains a sharded KV cache without additional synchronization for tree operations.The cache and running requests share dynamically allocated memory, and cached tokens may be evicted when larger batches require capacity.

4 Efficient Constrained Decoding with Compressed Finite State Machine

SGLang accelerates constrained decoding by compressing finite-state-machine paths with adjacent singular transitions. Multiple tokens on a compressed edge can then be decoded in one forward pass.

  • Motivation: Regex-constrained decoding improves output controllability and robustness while making structured outputs easier to parse.SGLang exposes this capability through a regex argument.
  • Compressed FSM: SGLang converts regular-expression constraints into a compressed FSM that combines adjacent singular-transition edges into single edges.The compressed representation identifies sequences that can be decoded together.
  • Decoding acceleration: Multiple tokens on a compressed transition edge can be decoded in one forward pass, greatly accelerating constrained decoding.The runtime applies this optimization to regular expressions generally.

5 Efficient Endpoint Calling with API Speculative Execution

SGLang uses speculative execution to accelerate multi-call programs that access black-box model APIs. It continues an earlier generation beyond its stop condition, then matches and reuses those tokens in later primitives, potentially saving one API call’s latency and input cost.

  • API setting: SGLang supports API-access-only models but can modify execution only through black-box API endpoints.This setting motivates a separate optimization for multi-call programs.
  • Speculative execution: Speculative execution continues the first generation beyond its stop condition, stores the extra output, and matches it against later generation primitives.The optimization targets multi-call programs that repeatedly generate related structured content.
  • Practical caveat: In practice, unpredictable output-token counts can cause KV-cache recomputation, limiting the cache-reuse computation described by the scheduling proof.This caveat concerns the practical execution of the theoretical analysis.
  • Benefits: When prompt engineering yields accurate template matches, speculative execution can save the latency and input costs of one API call.The two naive generation primitives would otherwise resend the context and incur two API calls.

6 Evaluation

SGLang is evaluated across diverse models, workloads, and hardware using throughput and latency metrics. Its gains arise from KV-cache reuse, frontend parallelism, and faster constrained decoding, while ablations examine cache, scheduling, co-design, and FSM components.

  • Experimental setup: SGLang is evaluated on dense, sparse mixture-of-experts, multimodal, and API models across diverse workloads.The evaluation includes Llama, Mixtral, LLaVA, and GPT-3.5 systems.
  • Experimental setup: Throughput is measured as program instances per second at maximum batch throughput, while latency is measured without batching.The reported latency is averaged across multiple single-program executions.
  • End-to-end performance: Up to 6.4× higher throughput and 3.7× lower latency are reported for SGLang on open-weight models.The comparison uses the systems and inference engines described in the evaluation setup.
  • End-to-end performance: The reported speedups result from KV-cache reuse, parallelism within a program, and faster constrained decoding.Examples include cache reuse for few-shot prompts and chat histories, parallel generation for tree- and skeleton-of-thought, and compressed-FSM JSON decoding.
  • Model and workload coverage: The optimization trend extends to Mixtral-8x7B and Llama-70B with tensor parallelism, while SGLang also supports image and video models.For multimodal inputs, image-token hashes enable reuse of cached image representations.
  • Ablation studies: Higher cache hit rates are associated with larger batch sizes, higher throughput, and lower latency.The study varies matched tokens at runtime on a tree-of-thought benchmark.
  • Ablation studies: Each tested optimization component contributes to best performance, and removing frontend parallelism or hints produces suboptimal runtime performance.The ablation compares no cache, no tree structure, alternative scheduling, and disabled frontend optimizations.
  • Ablation studies: RadixAttention management takes 0.2 seconds of a 74.3-second ShareGPT run, an overhead below 0.3%.The benchmark contains 100 requests without KV-cache reuse opportunities.

7 Related Work

SGLang is positioned among LLM programming and agent frameworks, with its distinguishing contribution centered on runtime optimizations and a co-designed execution system.

  • KV-cache reuse: RadixAttention uniquely treats the KV cache as a tree-based LRU cache supporting multi-level sharing, cache-aware scheduling, frontend-runtime co-scheduling, and distributed cases.The cited comparison distinguishes it from simpler reuse mechanisms and application-specific systems.
  • LLM programming frameworks: SGLang is compared with frameworks including Guidance, LMQL, DSPy, LangChain, AutoGen, and LLM Compiler.Guidance and LMQL are identified as the most similar systems.
  • System contribution: SGLang’s innovation lies in runtime optimizations, and its co-designed runtime can also accelerate compatible frameworks such as DSPy.The system is described as compatible with other frameworks.

8 Future Directions and Conclusion

SGLang improves execution of structured language model programs through runtime optimizations and supports future work on broader modalities, memory hierarchies, scheduling, and compilation.

  • 8 Future Directions and Conclusion: Future work includes supporting additional output modalities and extending RadixAttention across memory levels such as DRAM and disk.The authors also identify fuzzy semantic matching within RadixAttention as an open direction.
  • 8 Future Directions and Conclusion: The authors identify cache-aware scheduling starvation and advanced compiler optimizations for scheduling and memory planning as remaining challenges.These directions target improved execution planning and resource management.
  • 8 Future Directions and Conclusion: SGLang improves throughput and latency for complex language model programs through RadixAttention, compressed finite state machines, and a language interpreter.The framework supports advanced prompting techniques and agent workflows.
  • 8 Future Directions and Conclusion: SGLang is presented as a framework for efficient programming and execution of structured language model programs, with source code publicly available.The conclusion emphasizes its use for advanced prompting and agent workflows.

A.3 Proof of the Theorem 3.1

Theorem 3.1 establishes that depth-first traversal of the request radix tree achieves optimal cache-hit behavior under a sufficiently large cache, while longest-shared-prefix scheduling is equivalent to DFS.

  • A.3 Proof of the Theorem 3.1: A cache size at least equal to the maximum request length lets depth-first traversal achieve the optimal cache hit rate for a request batch.The proof argues that each radix-tree edge's KV cache is computed only once.
  • A.3 Proof of the Theorem 3.1: The longest-shared-prefix-first schedule is equivalent to a depth-first search order in the offline setting.This ordering prioritizes requests with longer matched prefixes.
  • A.3 Proof of the Theorem 3.1: The cache-aware scheduler matches waiting requests to radix-tree prefixes, sorts them by matched-prefix length, and selects requests subject to available memory.It merges selected requests into the running batch and performs allocation and eviction when needed.
  • A.3 Proof of the Theorem 3.1: In online operation, new batches can disrupt DFS, but longest-shared-prefix scheduling approximates DFS on the augmented radix tree.The schedule recursively processes subtrees rooted at the deepest cached nodes with unvisited descendants.
  • A.3 Proof of the Theorem 3.1: For distributed data-parallel execution, each worker maintains a subtree while a router maintains a meta-tree for prefix matching and device affinity.Requests are prioritized using the length of their matched prefixes.
  • A.3 Proof of the Theorem 3.1: Constrained decoding converts regular expressions into finite state machines whose transitions guide token generation.The string-to-token mismatch makes constrained decoding challenging because strings and tokens lack a one-to-one correspondence.

B.1 Implementation Details of Compressed Finite State Machine

Compressed finite state machines accelerate constrained decoding by merging deterministic character transitions and using long transitions to anticipate future output strings.

  • B.1 Implementation Details of Compressed Finite State Machine: A singular transition edge has one successor and one acceptable character or string, while a compressed edge concatenates consecutive singular transitions.These definitions are used to simplify the finite state machine before decoding.
  • B.1 Implementation Details of Compressed Finite State Machine: The construction recursively merges singular transition edges into preceding edges until no further compression is possible.The resulting Compressed FSM speeds decoding.
  • B.1 Implementation Details of Compressed Finite State Machine: When a decoded token matches an outgoing edge, the decoder advances the FSM; long compressed edges can anticipate subsequent decoded strings through Jump Forward.The anticipated string must still be converted into tokens for subsequent decoding.
  • B.1 Implementation Details of Compressed Finite State Machine: Retokenizing prior text and compressed-edge text preserves alignment with the original tokenizer and input format.Directly partitioning compressed text can change the intended meaning.
  • B.1 Implementation Details of Compressed Finite State Machine: Compressed transitions can distort choice probabilities because string-level paths may correspond to multiple token sequences.Accurate probabilities require summing the probabilities of all token sequences for each choice, adding decoding overhead.

C Additional Experimental Setups and Results

The additional results report experimental configurations, cache-hit comparisons, tensor-parallel throughput, and compiler-mode opportunities for more static optimization.

  • C Additional Experimental Setups and Results: The experiments use Llama, Mixtral, and LLaVA models across A10G and A100G GPUs, including single-GPU and tensor-parallel settings.The setups cover Llama-7B, Mixtral-8x7B, Llama-70B, LLaVA-v1.5-7B, and LLaVA-Next-34B.
  • C Additional Experimental Setups and Results: Figure 13 compares achieved and optimal cache hit rates on the benchmarks listed in Figure 5.The comparison evaluates cache reuse against the corresponding optimum.
  • C Additional Experimental Setups and Results: Figure 12 reports throughput for Llama-2-70B with tensor parallelism, with normalized throughput where higher is better.The figure compares normalized throughput across the evaluated systems or configurations.
  • C Additional Experimental Setups and Results: Compiler mode represents SGLang programs as computational graphs that can be rewritten for more static planning and compilation optimization.This provides an alternative to the interpreter mode used in the main body.

D.1 Design and Implementation

SGLang represents program structures as computational graphs and executes them through graph-based machinery, enabling optimization of prompt sharing. A case study reorders graph nodes to lengthen constant prefixes, with GPT-4 successfully preserving semantics for most tested templates.

  • Intermediate representation: SGLang’s intermediate representation models program operators as graph nodes and dependencies as graph edges.The graph includes primitive operators and captures both intra-stream and inter-stream dependencies.
  • Graph construction and execution: Tracing executes programs with abstract arguments to construct graphs dynamically, but currently excludes data-dependent control flow.The resulting graph can be executed directly, supporting graph rewriting, lower runtime overhead, and serialization.
  • Code movement for prefix sharing: Code movement reorders graph nodes to increase the length of the constant prefix and improve prefix sharing.This aggressive optimization may alter the original computation and uses GPT-4 because traditional program analysis cannot handle SGLang’s natural-language instructions.
  • Evaluation: 12 out of 15 templates were successfully reordered by GPT-4 without semantic changes, as confirmed by manual inspection.The evaluation used 5 templates as few-shot examples and 15 as test cases from a collection of 20 internet-sourced templates.
Loading 2312.07104v2…