SGLang: Efficient Execution of Structured Language Model Programs
Authors: 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
Venue: NeurIPS 2024 poster (2024)
Keywords: large language models; inference optimizations; KV cache; programming systems
Primary area: infrastructure
TL;DR: We introduce a system to simplify the programming and accelerate the execution of complex structured language model programs.

Abstract: 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.4\times$ 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.

SGLang: Efficient Execution of Structured Language Model Programs
Lianmin Zheng?*
Liangsheng Yin
Zhiqiang Xie
Chuyue Sun'
Jeff Huang" Joseph E. Gonzalez²
Cody Hao Yus
Shiyi Cao
Christos Kozyrakis'
lon Stoica²
Clark Barrett
Ying Sheng
Stanford University
2 UC Berkeley
3 Shanghai Jiao Tong University
Texas A&M University
5 Independent Researcher
Abstract
Large language models (LLMs) 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, system for efficient execution of complex language model programs. SGLang consists of frontend language and 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-a inference systems on various large language and multi-modal models on tasks including agent control, logical reasoning, few-shot learning benchmarks, JSON decoding, retrieval-augnee augmente generation pipelines, and multi-turn chat. The code publicly available https: :/gs tigtthu..c.. com/ wwttlppoooessssllleeee
Introduction
Recent increases in the capabilities of LLMs have broadened their utility, enabling them tackle wider range of general tasks and act as autonomous agents [35, 6, 36, 52, 46]. In such applications, LLMs engage multi-round planning, reasoning, and interaction with external environments. This is accomplished through tool usage [41, 38], multiple input modalities [47, 2]. and a wide range of prompting techniques [30], like few-shot learning [5], self-consistency [53]. skeleton-of-thought [33], and ofee-of-thought [56]. All of these new use cases require multiple, often dependent, LLM generation calls, showing trend of using multi-call structures to complete complex tasks [57, 21].
The emergence of these patterns signifies a shift in our interaction with LLMs, moving from simple chatting more sophisticated form of programmatic usage of LLMs, which means using program to schedule and control the generation processes of LLMs. We refer to these programs as "Language Model Programs" (LM Programs) [4, 20]. The advanced prompting techniques and agentic workflow mentioned above fall within the scope of LM programs. There are two common properties of LM programs: (1) LM programs typically contain multiple LLM calls interspersed with control flow, This is needed to complete complex tasks and improve overall quality. (2) LM programs receive structured inputs and produce structured outputs. This is needed enable the composition of LM programs and to integrate LM programs into existing software systems.
"Equal contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

SGLang Client (Frontend)
SGlang Runtime (Backend)
Interpreter
Optimizations: RadixAttention (Sec. 3), Compressed finite state machines (Sec. 4), API speculative execution (Sec. 5]
Language primitives (Sec. 2)
Figure I:
System architecture: An interpreter executes language primitives with optimized runtime.
Despite the widespread use of LM programs, current systems for expressing and executing them remain inefficient. We identify two primary challenges associated with the efficient use of LM pro- grams: First, programming LM programs is tedious and difficult due to the non-deterministic nature of L.Mss. Developing an LM program often requires extensive string manipulation, experimental tuning of prompts, brittle output parsing, handling multiple input modalities, and implementing parallelism mechanisms. This complexity significantly reduces the readability of even simple programs (Sec. 2).
Secondly and importantly, executing LM programs is inefficient due to redundant computation and memory usage. State-of-the-ar inference engines (c.g., vLLM [23], TGI [16], and TensorRT- LLM [34]), have been optimized to reduce latency and improve throughput without direct knowledge of the workload. This makes these systems general and robust but also results in significant ineffi- ciencies for any given workload. A prominent example is the reuse of the Jey-Value (KV) cache (Sec. 3). The KV cache consists of reusable intermediate tensors that are essential for generative inference. During typical batch executions of LM programs, numerous opportunities exist to reuse the KV cache across multiple different L.MM calls that share a common prefix. However, current systems lack effective mechanisms to facilitate this reuse, resulting in unnecessary computations and wasted memory. Another example is constrained decoding for structured outputs (e.g., JSON mode), where the output of LLMs is restricted to follow specific grammatical rules defined by regular expression (Sec. 4). Under these constraints, multiple tokens can often be decoded once. However, existing systems only decode one token at a time, leading to suboptimal decoding speeds.
To address these challenges. we present SGLang, a Structured Generation Language for LLMs. The core idea is to systematically exploit the multi-call structure in LM programs for efficient execution. As shown in Fig. 1, it has two parts: a front-end language and back-end runtime. The front-end simplifies the programming of LM programs, and the runtime accelerates their execution. The two parts can work together for better performance but can also function independently.
We introduce SGLang as a domain-specifee language embedded in Python. It provides primitives for generation (e.g., extend, gen, select) and parallelism control (e.g., fork, join). SGLang is compatible with Python's control flow and libraries, so users can develop advanced prompting workflows easily with native Python syntax. We provide an interpreter and a compiler for SGLang. The interpreter manages the prompt state as a stream and submits primitive operations to the stream for asynchronous execution, ensuring proper control over synchronization and intra- parra-prorram parallelism. Additionally, SGLang program can be traced and compiled for more optimizations.
On the runtime side, we propose several novel optimizations accelerate the execution of SGLang programs. The first technique, RadixAttention, enables the automatic reuse of the KV cache across multiple generation calls. In existing inference engines, the KV cache of request is discarded after processing is completed, preventing the KV cache from being reused across multiple calls and significantly slowing down the execution. Instead, our system maintains an LRU cache of the KV cache for all requests within a radix tree. This approach manages the KV cache as a traditional cache and uses a radix tree for efficient matching, insertion, and eviction. allows the runtime handle various reuse patterns with a cache-awane aware scheduling policy efficiently. The second technique is compressed finite state machine, which enables faster constrained decoding for structured outputs. Existing systems follow the constraints only for the next token by masking probabilities of disallowed tokens, making them able to decode only one token at a time. Instead, our system analyzes the constraints and builds compressed finite-state machine to represent the constraint. This approach compresses a multi-token path into a single-step path whenever possible, allowing the decoding of multiple tokens at once to achieve faster decoding speed. Lastly, SGLang also supports API-only models like OpenAl's GPT-4, and we introduce the third technique, API speculative execution, to optimize multi-call programs for APl-only models.
Using SGLang, we implemented various LLM applications, including agent control, logical reasoning. few-shot learning benchmarks, JSON decoding, retrieval- augmented generation pipelines, multi- turn chat, and multi-modality processing. We tested the performance on models including Ilama- 7B/70B [49], Mistral-8x7B [17], L.LVVA-v1.5-7 (image) [28], and -L.VA--ee----4 (video) [62] on NVIDIA A00G and A 100 GPUs. Experimental results show that SGLang achieves up to 6.4x higher throughput across a wide range of workloads, models, and hardware setups, compared to existing programming and inference systems, including Guidance [13], vLLM [23], and LMQL [4].
2

---

dimensions ["Clarity", "Originality", "Evidence"]
@function
def multi_ puatti_imensionall jinensiional_uddees, path, essay):
systen(" an essay about image.")
(ser(imageppath)) "Essay:" essay) +- assistant ("Sure!!"
Handle chat template and multi-modal inputs
# Return directly 1f it is not related
Select an option with the highest probability
s +* user("Is the essay related to the image?")
5 += assistan((sllcct("eelaees s("related"]
choices=["yes yes", "no" "no"I))
Fetch result; Use Python control flow
"no": return
# Judge multiple dimensions in parallel
forks s..ork (.foor((ee((dimensllon)))
Runtime optimization: KV Cache Reuse (Sec. 3)
for f, dim in zip(farks, dimensions):
f += user("Evaluate based on the following dimension:"
dim + End your judgment with the word "END"")
assistant("" (")udgeet"" *ge("" jeddmnuu,"" "EOD="END"))
Multiple generation calls run parallel
# Merge the judgments
judgnent "\n" jfudgef[""udgeett"] for f in forks)
Fetch generation results
# Generate a summary and grade. Return in the JSON format.
s +* user("Provide the judgment, summary, and a letter grade")
5 + asjistant(judgnent + "In sumnary," gen("sumnary", stop=".")
Runtime optimization: API speculative execution (Sec.
"The grade of it is" gen ("nn""rde"")
schema = r'M("sumaay"": "[Wwid's]+>.", "grade": "[ABCO][+-]P"Q]
+= user("Return in the JSON format.")
Runtime optimization: fast constrained decoding (Sec.
+- assistant ("outtttt, regex-schema)
state m print(state("outppa pitienssionl_judgeennn....
Run an SGLang program
Figure 2: The implementation a multi-dimensional essay judge SGLang utilizes the branch-solve-merge prompting technique [40]. Primitives provided by SGL are shown in red.
2 Programming Model
This section introduces the SGLang programming model with running example, describes its language primitives and execution modes, and outlines runtime optimization opportunities. This programming model can simplify tedious operations in multi-call workflows (e.g., string manipulation, API calling, constraint specification, parallelism) by providing flexible and composable primitives.
A rumning example. The language is a domain-speciffe language embedded in Python. Fig. 2 shows a program that evaluates an essay about an image using the branch-solve-mergg prompting method [40]. takes three arguments: path, and essay. manages
The function multi ti dimensional__ the prompt state, path the image file path, and essay is the essay text. New strings and SGLang primitives can be appended to the state s for execution using the += operator. First, the function adds the image and essay to the prompt. then checks if the essay is related to the image using select, storing the result in ["related"]] If related, the prompt is forked into three copies for parallel evaluation from different dimensions, using gen to store results in f ["juugment"" "]. Next, merges the judgments, generates summary, and assigns letter grade. Finally, it returns the results in JSON format, following a schema defined by a regular expression constraint regex. SGLang equivalent program using OpenAI API-like interface would
greatly simplifies this program, take 2.1x as many lines of code due to manual string manipulation and parallelism control.
Language primitives. SGLang provides primitives for controlling prompt state, generation, and parallelism. They can be used together with Python syntax and libraries. Here are the primitives: "gen" calls a model to generate and stores the results in a variable with the name specified in its first argument. supports "regex" argument to constrain the output to follow a grammar defined by a regular expression (e.g., a JSON schema). "select" calls model to choose the highest probability option from a list. The operator "+=" or "extend" appends a string to the prompt. The operator "[ "[variable_naar [amme_name"" fetches the results of generation. "fork" creates parallel forks of the prompt state. "join" " rejoins the prompt state. "image" and "video" take in image and video inputs.
Execution modes. The simplest way to execute an SGLang program is through an interpreter, where prompt treated as an asynchronous stream. Primitives like extend. gen, and select are submitted to the stream for asynchronous execution. These non-blocking calls allow Python code to continue running without waiting for the generation to finish. This is similar to launching CUDA kernels asynchronously. Each prompt is managed by stream executor in a background thread, enabling intra-program parallelism. Fetching generation results will block until they are ready, ensuring correct synchronization. Alternatively, SGLang programs can be compiled as computational graphs and
3

---

Table 1:
Comparison among LMQL, Guidance. and SGLang,
System
Syntax
Language Primitives
Runtime Backends
LMQL
Custom
extend. gen, select
HF Transformers, llama.cpp, OpenAl
Guidance
Python
extend, gen, select, image
HF Transformers, lpp. OpenAl
SGLang
Python
extend. gen, select, image, video. fork. join SGLang Runtime (SRT), OpenAl
executed with a graph executor, allowing for more optimizations. This paper uses interpreter mode by default and discusses compiler mode results in Appendix D. SGLang supports open-weight models with its own SGLang Runtime (SRT), as well as API models such as OpenAl and Anthropic models.
Comparison. Programming systems for LLMs can be classified as high-level (e.g., LangChain, DSPy) and low-level (c.g.. LMQL, Guidance, SGLang). High-level systems provide predefined or auto-generated prompts, such DSPy's prompt optimizer. Low-level systems typically do not alter prompts but allow direct manipulation of prompts and primitives. SGLang is a low-level system similar LMQL and Guidance. Table compares their features. SGLang focuses more on runtime efficiency and comes with its own co-designed runtime, allowing for novel optimizations introduced later. High-level languages (e.g., DSPy) can be compiled to low-level languages (e.g., SGLang). We demonstrate the integration of SGLang as backend in DSPy for better runtime efficiency in Sec. 6.
Runtime optimizations. Fig. 2 shows three runtime optimization opportunities: KV cache reuse, fast constrained decoding, API speculative execution. We will discuss them in the following sections.
3 Efficient KV Cache Reuse with RadixAttention
SGLang programs can chain multiple generation calls and create parallel copies with the "fork" primitive. Additionally, different program instances often share some common parts (e.g., system prompts). These scenarios create many shared prompt prefixes during execution, leading to numerous opportunities for reusing the KV cache. During LLM inference, the KV cache stores intermediate tensors from the forward pass, reused for decoding future tokens. They are named after key-value pairs in the self-attention mechanism [51]. KV cache computation depends only on prefix tokens. Therefore, requests with the same prompt prefix can reuse the KV cache, reducing redundant computation and memory usage. More background and some examples are provided in Appendix A.
Given the KV cache reuse opportumity, a key challenge in optimizing SGLang programs is reusing the KV cache across multiple calls and instances. While some systems explore certain KV cache reuse cases [23, 58, 18, 12], they often need manual configurations and cannot handle all reuse patterns (e.g., dynamic tree structures). Consequently, most state-of-the-an inference systems recompute the KV cache for each request. We will discuss their limitations and our differences in Sec. 7.
This section introduces
a novel technique for automatic and systematic KV cache reuse during runtime. Unlike existing systems that discard the KV cache after a generation request finishes, our system retains the cache for prompts and generation results in a radix tree, enabling efficient prefix search, reuse, insertion, and eviction. We implement an LRU eviction policy and cache-aware scheduling policy to enhance the cache hit rate. RadixAttention is compatible with techniques like continuous batching [60]. paged attention [23], and tensor parallelism [44]. In addition, it introduces only negligible memory and time overhead when there is no cache hit.
RadixA Atention. A radix tree is a data structure that serves as space-efficient alternative to a classical trie (prefix tree). Unlike typical trees, the edges of radix tree can be labeled not just with single elements but also with sequences of elements of varying lengths, significantly enhancing efficiency. In our system, we utilize a radix tree to manage mapping between sequences of tokens, and their corresponding KV cache tensors. These KV cache tensors are stored a non-contiguous, paged layout, where the size of each page is equivalent to one token. Because GPU memory is quickly filled by the KV cahce, we introduce a simple LRU eviction policy that evicts the least recently used Icaf first. By evicting leaves first, enable the re-use of their common ancestors until those ancestors become leaves and are also evicted.
In the continuous batching setting, we cannot evict nodes used by the currently running batch. Therefore, each node maintains a reference counter indicating how many running requests are using it. A node is evictable if its reference counter is zero. Note that we do not preallocate a fixed-size memory pool as a cache. Instead, we let the cached tokens and the currently running requests share the same memory pool. Therefore, the system dynamically allocates memory for cache and running requests. When enough waiting requests run, the system will evict all cached tokens favor of a larger batch size. Fig. 3 shows how the radix tree is maintained for several incoming requests. The

---

(2)
You helpful assetant.
User: helpful assistant.
You are helpful assistant
helpful assistant.
User: itelll
Accistant: Hi!
Assesaat:: Hi!
Usen Hello! Assistant: Hill
User: What can you do? Assiscant: cann...
User: Hellel
User: What can you do? Assiicant: can...
Assistanc: Hit
User: Solve this problem....
Assistant: Sure!...
Usen Salve this question... Assistant; Sure!...
User: Write a Assiscant: Sure!
evicted
Quastion 1o..
Question to
are helpful assistant.
Answer 1:
You are helpful ausistant.
Answer 1:..
Quesstonn 2i
Qurestion 2:
Answer 2
Answer 2
User: Hello!
User: What can you do? Assistant:
Question
User: Hello! Assetant: Hil
Usen What can you do? Assisant::
Question
Assistant: Hit
Writee Assistant: Surel...
User: Writs story... Surel
What
When
How
Answer
[8]
(9)
Question
Guestion 31 on
You are a helpful assistant,
Answer 1:
You are helpful aosistant.
Answer 1:
Question
Question 2:
Answer
Answer Question
Hallo!
Hill
evicted
Question
Hello!
What Answer 3:
Solve question..
Assistant: Surel
evicted
User:
How about..?
Assetant:
This
We
To scllve....
Figure 3: Examples of RadixAttention operations with an LRU eviction policy, illustrated across nine time points. The figure demonstrates the dynamic evolution of the radix tree in response to various requests. These requests include two chat sessions, batch of few-shot learning inquiries, and self-consistency sampling. Each tree edge carries a label denoting a substring or a sequence of tokens. The nodes are color-coded to reflect different states: green for newly added nodes, blue for cached nodes accessed during the time point, and red for nodes that have been evicted. In step (1), the radix tree is initially empty. In step (2), the server processes an incoming user message "Hello" and responds with the L.M output "Hi". The system prompt "You are a helpful assistant", the user message "Hello!", and the LLM reply "Hi!" are consolidated into the tree new node. In step (3), a new prompt arrives and the server finds the prefix of the prompt (i.e., the first turn of the conversation) in the radix tree and reuses its KV cache. The new turn is appended tree as new node. In step (4), new chat session begins. The node "b" from (3) is split into two nodes to allow the two chat sessions to share the system prompt. In step (5), the second chat session continues. However, due to the memory limit, node "c" from (4) must be evicted. The new turn is appended after node "d" in (4). In step (6), the server receives a few-shot learning query, processes and inserts it into the tree. The root node is split because the new query does not share any prefix with existing nodes. In step (7), the server receives batch of additional few-shot learning queries. These queries share the same set of few-shot examples, step (8), the server receives a new message from the first chat session. evicts all nodes from the second chat session (node "g" and "h") as they are least recently used. In step (9), the server receives a request to sample more answers for the questions in node "j" from (8), likely for self-consistency prompting. To make space for these requests, evict node "I", "k", and "I" in (8).
single edge linked to
the
we split node 'e' from (6) to enable sharing. In
frontend interpreter sends full prompts to the runtime, and the runtime performs prefix matching and reuse. The tree structure is stored on the CPU with negligible maintenance overhead. During the execution of the fork primitive, the frontend sends the prefix first as a hint, ensuring the prefix is correctly inserted into the tree. It then sends the remaining prompts. This "Frontend Hint" simplifies co-design.
runtime scheduling and matching, exemplifying the benefits of Frontend-runtioo
Cache-aware seheduling. We define the cache hit rate as many requests the waiting queue, the order in which they are executed can significantly impact the cache hit rate. For example, if the request scheduler frequently switches between different, unrelated requests, can lead to cache thrashing and a low hit rate. We design a cache-aware scheduling algorithm to increase the cache hit rate. In the batch-processing setting we sort the
number of cached prompi tokens
When there are
number prompi tokens
5

---

FSM state
Token
LLM decode
"summayy'
(a) Normal FSM for regex "'unmary"::
(b) Compressed FSM for regex
"summaay":
Summary
LLM
LLM
[c] Decoding process with normal FSM
(d) Decoding process with compressed FSM
Figure 4: The decoding process of normal and compressed FSMs (the underscore means space).
requests by matched prefix length and prioritize requests with longer matched prefixes instead of using a first-come, first-served schedule. Alg. (Appendix) shows the pseudo-code for cache-aware scheduling with contiguous batching. The algorithm uses sangess-saared-prffi--f-f latency-sensitive settings we may still be able to tolerate limited batch re-ordering to improve cache reuse. Additionally, we prove the following theorem for optimal scheduling in the offline case." Theorem 3.1. For batch of requests, we can achieve an optimal cache hit rate by visiting the radix tree of the requests in the depth-first search order, with a cache size Z the maximum request length. depth-first search order.
order. In more
The longest-shares shared- shared-preftx--eeeeeee prefix-first order is equivalent
The proof is in Sec. A.3 (Appendix). In the online case, the DFS order will be disrupted, but our schedule still approximates the DFS behavior on the augmented part of the full radix tree, as described in Sec. A.3. While greedy cache-aware scheduling can achieve high throughput, it can lead starvation. We leave its integration with other fair scheduling methods [42] as future work.
Distributed Cases. RadixAttentiin can be extended to multiple GPUs. For tensor parallelism, each GPU maintains sharded KV cache. There is need for additional synchronization because the tree operations are the same. Data parallelism with multiple workers is discussed in Sec. A.4 (Appendix).
Efficient Constrained Decoding with Compressed Finite State Machine
In LM programs, users often want to constrain the model's output to follow specific formats, such as JSON schemas. This can improve controllability and robustness, and make the output easier to parse. SGLang offers a regex argument to enforce such constraints using regular expressions, which are expressive enough for many practical scenarios. Existing systems support this by converting a regular expression into finite state machine (FSM) [54]. During decoding, they maintain the current expressior
FSM state, retrieve allowed tokens from the next states, and set the probability of invalid tokens to zero, decoding token by token. This token-by-token approach, however, is inefficient when there opportunities to decode multiple tokens at once. For example, the constant sequence {" ("summary": : in Fig. 2 spans multiple tokens in the normal decoding process shown in Fig. 4 (c), requiring multiple decoding stages, even though there is only one valid next token when decoding it. Therefore, the whole sequence can be decoded in single step (i.e., forward pass). However, existing systems can only decode one token at a time because the lack of integration between the FSM and the model runner in existing systems prevents multi-token processing, resulting in slow decoding.
SGLang overcomes this limitation by creating a fast constrained decoding runtime with a compressed FSM. This runtime analyzes the FSM and compresses adjacent tnnuula-transittonn edges in the FSM into single edges as demonstrated in Fig. 4 (b), allowing it to recognize when multiple tokens can be decoded together. In Fig. 4 (d), multiple tokens the compressed transition edge be decoded in one forward pass, which greatly accelerates the decoding process. It is also general and applicable to all regular expressions. More details on the background and implementation are in Appendix B.
5 Efficient Endpoint Calling with API Speculative Execution
The previous sections introduced optimizations for open- geinhw models, which require modifications to the model inference process. Additionally, SGLang works with APl-access-only models, such as OpenAl's GPT-4. However, for these models, we can only call a black-box API endpoint.
This section introduces a new optimization for black-box API models that accelerates execution and reduces the API cost of multi-call SGLang programs using speculative execution. For ex- ample, program may ask the model to generate a description of a character with multi-call
"n practice. the computation is not the same as what is described in the proof of Theorem 3.1 because the unpredictable number of output tokens can cause the recomputation of the KV cache.

---

SGLang
VLLM
Guidance
LMQL
1.0
Thoughhut
L
0.2
0.0
Multi-Tum DSPy Decoding Chatfshort) Chatllong) Pipeline Figure 5: Normalized throughput on Llama-7B models. Higher is better.
Generative
Skeleton
Judge HellaSwag
JSON
Agents
Agents
Thought of Thought
"job:" gen (" ("job", (cop="\n")) Naively, the two gen primitives correspond to two API calls, meaning that the user needs to pay for the input token fee on the context twice. SGLang, we can enable speculative execution on the first call and let it continue the generation of few more tokens by ignoring the stop condition. The interpreter keeps the additional generation outputs and matches and reuses them with later primitives. In certain cases, with careful prompt engineering, the model can correctly match the template with high accuracy, saving us the latency and input costs of one API call.
pattern: context "name:" "
gen (enamee"", stop="\n")
6 Evaluation
We evaluate the performance of SGLang across diverse LLM workloads. Subsequently, conduct ablation studies and case studies to demonstrate the effectiveness of specific components. SGLang implemented in PyTorch [37] with custom CUDA kernels from FlashInfer [59] and Triton [48].
6.1
Setup
Models. We test dense Llama-2 models [49], sparse mixture of experts Mixtral models [17], multi- modal LLaVA image [27] and video models [62], and API model OpenAl's GPT-3.5. For open- weight models, the number of parameters ranges from 7 billion 70 billion, and
float16 precision.
Hardware. We run most experiments on AWS EC2 G5 instances, which are equipped with NVIDIA A10G GPUs (24GB). We run 7B models on a single A10G GPU and larger models on multiple A A10G GPUs with tensor parallelism [44]. We run some additional experiments on A100G (80GB) GPUs.
Baselines. We compare SGLang against both high-level programming systems with their respective languages and default runtimes, as well as low-level inference engines with standard OpenAI-like Completion APIs. Unless otherwise stated, we do not turn on optimizations that will change the computation results so that systems compute the same results. The baselines include:
Guidance 13], a language for controlling L.Ms. We use Guidance 1..1.8 with llama.cpp backend. vLLLM [23], high-throughput inference engine. We vLLM v0.2.5 and its default API server?. LMQL [4], a query language. We use LMQL v0.7.3 with Hugging Face Transformers backend.
Workloads. We test the following: 5-shot MMLU [14] and 20-shot HellaSwag [61] benchmarks. decode one token for MMLU and use primitive select to select the answer with the highest probability for HellaSwag. For the ReAct agent [57] and generative agents [36],
extract the
traces from the original papers and replay them. We use the of-thuhtth [56] for the GSM-8K problems and Skeleton-of-thougee [33] for tip generation. We use LLM judges with the branch-solve- merge [40] technique; JSON decoding with schema specified by a regular expression; Multi-turn chat with 4 turns, where the input of each turn is randomly sampled between 256-512 tokens. Multi- turn chat (short) means short output (4-8 tokens) and multi-turn chat (long) means long output (256-512 tokens); DSPy retrieval-and augmented generation (RAG) pipeline [20] in its official example.
Metrics. We report two performance metrics: throughput and latency. For throughput, we run sufficiently large batch of program instances compute the maximum throughput, comparing the number of program instances executed per second (programs per second, p/s). For latency, we execute single program at time without batching and report the average latency for multiple instances.
End-to Eind-t-EEnd Performance
Results on open-weight models. The latency and throughput results are shown in Fig. and Fig. 6. SGLang improves throughput by up to 6.4 and reduces latency by up to 3.7x. These improvements
Attention has been partially integrated optional experimental feature into the latest version of VLLM; therefore, we used earlier version for comparison.
7

---

SGLang
VLLM
Guidance
LMQL
Normaiizeel
1.0
Latency
0.8
0.0
Skeleton
Judge HellaSwag
JSON
Multi-Tum Multi-Tum
Agents
Agents
Thought
Thought
Decoding Chattshort) Chatllong) Ripeline
Figure 6: Normalized latency on Llama-7B models. Lower better.
SGLang
VILM
Throughout
(Nommlized)
1.0
0.8
0.2
0.0
Skeleton Judge HellaSwag
JSON
Multi-Tum
Agents
Agents
Thought of Thought
Decoding Chatrshort) Chatllong) Pipeline
Figure 7: Normalized throughput on Mixtral-8x7B models with tensor parallelism. Higher is better.
result from KV cache reuse, the exploitation of parallelism within single program, and faster constrained decoding. Next, explain the reasons for the speedup in each benchmark.
MMLU, SGLang can reuse the KV cache of the 5-shot examples with Radix Attention RadixAt- tention benefits both throughput and latency. RadixAttention reduces total memory usage by sharing the KV cache, allowing for a larger batch size to improve maximum throughput. RadixAttention also reduces the computation of prefill, thus decreasing the first token latency. On HellaSwag, SGLang reuses the KV cache both few-shot examples and the common question prefix for multiple choices, resulting in two-level sharing. For the ReAct and generative agents, SGLang reuses the KV cache of the agent template and previous calls. On Tree-of- of-htughtthuht and Skeleton-of-thenn offthouggh, SGLang parallelizes the generation calls within single program and reuses the KV cache as much as possible. On JSON decoding, SGLang accelerates decoding by decoding multiple tokens at once with compressed finite state machine. In multi-turn chat, SGLang reuses the KV cache of the chat history. The speedup is more noticeable for short outputs because KV cache reuse mostly helps reduce the prefix time. For long outputs, because there is not much sharing between different chat sessions and the decoding time dominates, there is almost no speedup. In the DSPy RAG pipeline, SGLang reuses the KV cache of the common context example. On these benchmarks, the cache hit rate ranges from 50% to 99%. Fig. 13 (Appendix) lists the achieved and optimal cache hit rates for all of them, showing that our cache-aware scheduling approaches 96% of the optimal hit rate on average.
We exclude LMQL and Guidance from some of the last five benchmarks due to slow performance and missing functionalities. LMQL's issues stem from slow token-level processing and an unoptimized backend, while Guidance lacks batching and parallelism support.
Results larger models with tensor parallelism. We larger models, Mixtral-8xx -x78 and Llama- 7OB, with tensor parallelism on the same set of benchmarks and report the results in Fig. 7 and Fig. 12 (Appendix). The speedup on larger models shows trend similar to that observed smaller models, indicating that our optimization generalizes well to larger models. We omit Guidance and LMQL here because they lack efficient implementations of tensor parallelism.
Results on multi-modal models. SGLang has native support for moltil models with the image and video primitives. The optimizations in this paper are compatible with multi-modal models. For Attenton,n,,nn, we compute the hash of the input images and use as the key in radix tree, allowing us to reuse the KV cache of the image tokens from the same image. We run LLaVA-v1.5-7B (image) on Ilava-bench-in sennch-ii-thhwwiin and LLaVA-NeXT-34D (video) on ActivityNet. Because these models are not well supported by other bascline systems, original implementation in Hugging Face Transformers as the baseline. As shown in Table 2, SGLang provides throughput up 6x higher on these benchmarks. In bava-bench-innthe-... multiple questions about the same image, and SGLang runtime reuses the KV cache in this case.
the model authors'
there are
Production deployment. SGLang has been deployed in Chatbot Arena [8] to serve open weight models. Due to low traffic for some models, only one SGLang worker serves each. After one month, we observed 52.4% RadixAttention cache hit rate for LLaVA-Next-S41 [28] and 74.1% 1% for Vieuna-33B [7]. Cache hits come from common system messages, frequently reused example images, and multi-turn chat histories. This reduces first-token latency by average of 1.7x for Vicuna-33B.

---

Table 2: Throughput comparison on multi-modal LLaVA image and video models.
Model
LLaVA-v1.5-7B (image)
LLaVA-NeXT-340 (video)
Author's 's original implementation
0.18 image/s
0.02 framels
SGLaang
1.15 image/s
0.10 frame/s
Cache
Handom Schedule No frontand Paralletom
frontand Optimization
Size
Latency
Stracture
Throughpit (takens/ s]
First Token Labency (5)
FCFS Schedal
1.2k
400
Through
1.00
1.0k
-20
(Nomalized
0.75
300
0.50
-10
0.25
20
0.4K
0.00
20
8o 100
20 60 80 100
LLM Judge
Tree of Thought (c)
MMLU
Multi-Tum
Cache Hit Rate (%6
Cache Hit Rate (%6 (b)
Chat(short)
(a)
Figure 8: (a)(b) Cache hit rate ablation study. (c) RadixAttention ablation study.
Results on API models. We test a prompt that extracts three fields from a Wikipedia page using
OpenAl's GPT-3.5 model. By using few-shot prompting, the accuracy of API speculative execution is high, and it reduces the cost of input tokens by about threefold due to the extraction of three fields.
6.3 Ablation Study
Cache hit rate vs. latency/throughput. Fig. 8(a)(b) shows the relationship between cache hit rate and performance metrics (first token latency, total latency. batch size, and throughput) on the tree-of-thought benchmark. The figure is obtained by partially disabling matched tokens at runtime. It shows that a higher cache hit rate leads to larger batch size, higher throughput, and lower latency.
Effectiveness of RadixAttention. We test the effectiveness of RadixAttention and its components on several representative benchmarks. As shown in Fig. 8(c), "No Cache" means not using any cache, "No Tree-Structure" means using simple table-based cache instead of a tree-structured cache, policy instead of our cache-aware scheduling,
"FCFS Schedule" means using a sat--com--iisssseeeee "Random Schedule" means using random order to schedule requests, "No Frontend Parallelism" means disabling parallelism in the interpreter, "No Frontend Hint" means disabling sending the fork hints from the interpreters, and "Full optimizations" means we turn on all optimizations. The experimental results show that each of these components is required to achieve the best performance. Disabling parallelism and hints from the frontend interpreter also results in suboptimal runtime performance, highlighting the importance of co-designing the frontend language and runtime.
We test the overhead of RadixAttention KV cache reuse opportunities. The benchmark measures throughput on the ShareGPT dataset. takes 74.3 seconds to run 100 requests; however, the time used for managing the Radix Attention data structures is only 0.2 seconds, which is a negligible overhead of less than 0.3%. This because the complexity of tree operations is linear and small. Thus, we can turn on RadixAttention by default.
Overhead of
benchmark without any
Effectiveness the compressed finite state machine. We test the effectiveness the compressed finite state machine and its components on the JSON decoding benchmark. Experimental results show that the compressed finite state machine increases the throughput by 1.6x because it can decode multiple tokens at once. In addition, need to preprocess the state machine and reuse it for a batch of requests. Otherwise, redoing the preprocessing for each request makes the throughput 2.4x lower.
7 Related Work
Various works have explored the reuse of the KV cache, and many of them are concurrent with our work. Uniquely, our RadixAttention first proposes treating the KV cache as brse-base LRU cache. is the first solution that supports multi-level sharing, cache-aware scheduling, frontend-runtime co-scheduling, and distributed cases. vLLM [23] and Mounked/Attettion [58] explore some simple reuse cases (e.g., system prompt sharing) but do not cover multi-level rre-structured sharing or LRU caching. PromptCache [12] proposes the modular reuse of the KV cache beyond the prefix but can impact accuracy by up to 43% drop. HydraGen [18], FlashInfer [59], and ChunkedAAttention [58] focus on CUDA kernel optimizations and do not include the concept of an LRU cache. InferCept [1] and L.LM-QLL [29] study KV cache reuse for specific applications such as interleaving with external
API calls and relational databases, but they do not have radix tree or cache-awar aware scheduling.

---

Several LLM programming and agent frameworks exist, such as Guidance [13]. LMQL [4], DSPy [20]. LangChain [24], AutoGen [55], and LLM Compiler [21]. Guidance and LMQL are most similar to Lan, and we compare them in Sec. 2. Our innovation lies in novel runtime optimizations for accelerating the proposed programming model. SGLaang is compatible with other frameworks and can accelerate them (e.g., the DSPy example in our evaluation). Additionally, SGLang is compatible with many other common inference optimizations [60, 39, 3, 23, 59, 10, 26, 15, 19, 32, 31, 11].
8 Future Directions and Conclusion
Future directions. Despite the progress made with SGI.ang, several limitations remain that reveal promising directions for future research. These include extending SGLang to support additional output modalities, adapting RadixAttention to operate across multiple levels of the memory hierarchy (e.g., DRAM, Disk) [43], enabling fuzzy semantic matching within Aadixtttention, providing higher- level primitives atop SGLang, fixing starvation in cache-aware scheduling [42], and enhancing the SGLang compiler to perform advanced static optimizations such as scheduling and memory planning.
Conclusion. We introduce SGLang, a framework for efficient programming and executing structured language model programs. SGLang significantly improves the throughput and latency of complex LM programs through novel optimizations like Radix Attention, compressed finite state machines, and language interpreter. It is valuable tool for developing advanced prompting techniques and agent workflows. The source code is publicly available.
Acknowledgement
This project is supported by the Stanford Center for Automated Reasoning and gifts from Astronomer, Google, IBM, Intel, Lacework, Microsoft, Mohamed Bin Zayed University of Artificial Intelligence. Nexla, Samsung SDS, Uber, and VMware. Lianmin Zheng is supported by Meta Ph.D. Fellowship. We thank Yuanhan Zhang and Bo Li for the LLaVA-NeXT (video) support.
References
[1] Reyna Abhyankar, Zijian He, Vikranth Srivatsa, Hao Zhang, and Yiying Zhang. Infercept: Efficient intercept support for augmented large language model inference. In Forty-first Interna- tional Conference on Machine Learning, Vienna, Austria, July 2024.
[2] Jean-Baptiste Alayrac, Jeff Donahue, Pauline Luc, Antoine Miech, Iain Barr, Yana Hasson, Karel Lenc, Arthur Mensch, Katherine Millican, Malcolm Reynolds, et al. Flamingo: a visual language model for few-shot learning. Advances in Neural Information Processing Systems, 35:23716-23753 2022.
[3] Reza Yazdani Aminabadi, Samyam Rajbhandari. Ammar Ahmad Awan, Cheng Li. Du Li, Elton Zheng, Olatunji Ruwase, Shaden Smith, Minjia Zhang, Jeff Rasley, et al. Deepspeed- inference: enabling efficient inference of transformer models at unprecedented scale. In SC22: International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1-15. IEEE, 2022.
[4] Luca Kellnr, Mare Fischer, and Martin Vechev. Prompting is programming: A query language for large language models. Proceedings of the ACM on Programming Languages, 1(PLD)):19461166) 2023.
[5] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 1877-1919 2020.
[6] Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint arXiv:2303.1 12712, 2023.
[7] Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph F. Gonzalez, lon Stoica, and Eric P. Xing. Vieuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality, March 2023.
10

---

[8] Wei-Lin Chiang, Lianmin Zheng, Ying Sheng, Anastasios Nikolas Angelopoulos, Tianle Li, Dacheng Li, Hao Zhang, Banghua Zhu, Michael Jordan, Joseph Gonzalez, al. Chatbot arena: An open platform for evaluating Imms by human preference. arXiv preprint arXiv:2403.04132 2024.
[9] Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311 2022.
[10] Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness. Advances Neural Information Processing Systems, 35:16444-16359 2022.
[1]] Suyu Ge, Yunan Zhang, Liyuan Liu, Minjia Zhang, Jiawei Han, and Jianfeng Gao. Model tells you what to discard: Adaptive kv cache compression for llms. In The Twelfth International Conference Learning Representations, 2023.
[12] In Gim, Guojun Chen, Seung-seob Lee, Nikhil Sarda, Anurag Khandelwal, and Lin Zhong. Prompt cache: Modular attention reuse for low-latency inference. arXiv preprint arXiv:2311.04934 2023.
[13] Guidance AI. A guidance language for controlling large language models. https://github. com/ hom//giddance-all aeieeaiiggggiii ai/guidance. Accessed: 2023-11.
[14] Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. In International Conference on Learning Representations, 2020.
[15] Coleman Hooper, Sehoon Kim, Hiva Mohammadzadeh, Michael W Mahoney, Yakun Sophia Shao, Kurt Keutzer, and Amir Gholami. Kvquant: Towards 10 million context length Ilm inference with kv cache quantization. arXiv preprint arXiv:2401.18073 2024.
[16] Hugging Face. Text generation inference. https://githiee com/huggingface/ text seattgeneratioo--oe inferenceeeeeeee.e Accessed: 2023-11.
[17] Albert Q Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, 2024.
et al. Mixtral of experts. arXiv preprint arXiv:2401.0400
[18] Jordan Juravsky, Bradley Brown, Ryan Ehrlich, Daniel Y Fu, Christopher Ré, and Azalia Mirhoseini. Hydragen: tightthroughhut Ilm inference with shared prefixes. arXiv preprint 24Xiv:2402.05099 2024.
[19] Hao Kang, Qingru Zhang, Souvik Kundu, Geonhwa Jeong, Zaoxing Liu, Tushar Krishna, and Tuo Zhao. Gear: An efficient kv cache compression recipefor near-lossless generative inference of Ilm. arXiv preprint arXiv:2403.05522 055527, 2024.
[20] Omar Khattab, Arnav Singhvi, Paridhi Maheshwari, Zhiyuan Zhang, Keshav Santhanam, Sri Vardhamanan, Saiful Haq, Ashutosh Sharma, Thomas T. Joshi, Hanna Moazam, Heather Miller, Matei Zaharia, and Christopher Potts. Dspy: Compiling declarative language model calls into seff-improving pipelines. arXiv preprint arXii:2310.037114, 2023.
[21] Sehoon Kim, Suhong Moon, Ryan Tabrizi, Nicholas Lee, Michael Mahoney, Kurt Keutzer, and Amir Gholami. An llm compiler for parallel function calling. arXiv preprint arXiv:2312.045/1, 2023.
[22] Michael Kuchnik, Virginia Smith, and George Amvrosiadis. Validating large language models with relm. Proceedings of Machine Learning and Systems, 5, 2023.
[23] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Principles, pages 61 1-166, 2023.
11

---

[24] LangChain AI. Langchain. 2023-11.
Accessed:
[25] Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Bccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. Competition-leve code generation with alphacode. Science, 37866224;1092-10997, 2022.
[26] Ji Lin, Jiaming Tang, Haotian Tang, Shang Yang, Xingyu Dang, and Song Han. Awq: Activation-aware weight quantization for Ilm compression and acceleration. arXiv preprint arXiv:2306.00978 2023.
[27] Haotian Liu, Chumyuan Li, Yuheng Li, and Yong Jae Lee. Improved baselines with visual instruction tuning. arXiv preprint arXiv:2310.03744, 2023.
[28] Haotian Liu, Chunyuan Li, Yuheng Li, Bo Li, Yuanhan Zhang, Sheng Shen, and Yong Jae Lee. Llava-next: Improved reasoning, ocr, and world knowledge, January 2024.
[29] Shu Liu, Asim Biswal, Audrey Cheng, Xiangxi Mo, Shiyi Cao, Joseph E Gonzalez, Ion Stoica, and Matei Zaharia. Optimizing Ilm queries in relational workloads. arXiv preprint arXiv:2403.05821, 2024.
[30] Xiaoxia Liu, Jingyi Wang, Jun Sun, Xiaohan Yuan, Guoliang Dong, Peng Di, Wenhai Wang, and Dongxia Wang. Prompting frameworks for large language models: A survey, arXiv preprint arXiv:2311.12785 2023.
[31] Zichang Liu, Aditya Desai, Fangshuo Liao, Weitao Wang, Victor Xie, Zhaozhuo Xu, Anastasios Kyrillidis, and Anshumali Shrivastava. Scissorhands: Exploiting the persistence of impor- tance hypothesis for IIm kv cache compression at test time. Advances in Neural Information Processing Systems, 36, 2024.
[32] Zirui Liu, Jiayi Yuan, Hongye Jin, Shaochen Zhong, Zhaozhuo Xu, Vladimir Braverman, Beidi Chen, and Xia Hu. Kivi: A tuning-fre- free asymmetric 2bit quantization for kv cache. arXiv preprint arXiv22402.02750 2024.
[33] Xuefei Ning, Zinan Lin, Zixuan Zhou, Zifu Wang, Huazhong Yang. and Yu Wang. Skeleton- of-thought: Prompting LLMs for efficient parallel generation. In The Twelfth International Conference on Learning Representations, 2024.
[34] NVIDIA. Tensont--lm. https: httpr//nttttgggtttttt.o///////// htgpth/..co//VVDDA//TTootT----- Accessed: 2023-
11.
[35] OpenAl. Gpt-4 technical report, 2023.
[36] Joon Sung Park, Joseph C. O' Brien, Carrie J. Cai, Meredith Ringel Morris, Percy Liang, and Michael S. Bernstein. Generative agents: Interactive simulacra of human behavior. In In the 36th Annual ACM Symposium on User Interface Software and Technology (UIST '23), UIST '33, New York, NY, USA, 2023. Association for Computing Machinery.
[37] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killcen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-peeformance deep learning library. Advances in neural information processing systems, 32, 2019.
[38] Shishir G. Patil, Tianjun Zhang, Xin Wang, and Joseph E. Gonzalez. Gorilla: Large language model connected with massive apis. arXiv preprint arXiv:2305.75334 2023.
[39] Reiner Pope, Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury. Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean. Efficiently scaling transformer inference. Proceedings of Machine Learning and Systems, 5, 2023.
[40] Swarnadeep Saha, Omer Levy, Asli Celikyilmaz, Mohit Bansal, Jason Weston, and Xian Li. Branch-solve-merge improves large language model evaluation and generation. arXiv preprint arX1v:2310.15123, 2023.
12

---

[41] Timo Schick, Jane Dwivedi- Yu, Roberto Dessi, Roberta Raileanu, Maria Lomeli, Luke Zettle- moyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves to use tools. arXiv preprini arXiv: 2023.
[42] Ying Sheng. Shiyi Cao, Dacheng Li, Banghua Zhu, Zhuohan Li, Danyang Zhuo, Joseph E Gonza- lez, and Ion Stoica. Fairness serving large language models. arXiv preprint arXiv:2401.066 .00588, 2023.
[43] Ying Sheng, Lianmin Zheng, Binhang Yuan, Zhuohan Li, Max Ryabinin, Beidi Chen, Percy Liang, Christopher Ré, lon Stoica, and Ce Zhang. Flexgen: high tagh-throughput generative inference of large language models with single gpu. In International Conference on Machine Learning, pages 31094-314 116. PMLR, 2023.
[44] Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro. Megatron-Im: Training multi-billion parameter language models using model parallelism. arXiv preprint arXiv:1909.008 08053, 2019.
[45] Vikranth Srivatsa, Zijian He, Reyna Abhyankar, Dongming Li, and Yiying Zhang, Preble: Elficient distributed prompt scheduling for I1m serving. 2024.
[46] Theodore Sumers, Shunyu Yao, Karthik Narasimhan, and Thomas Griffiths. Cognitive architec- tures for language agents. Transactions on Machine Learning Research, 2023.
[47] Gemini Team, Rohan Anil, Sebastian Borgeaud, Yonghui Wu, Jean-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, et al. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:23122 1805, 2023.
[48] Philippe Tillet, Hsiang- -ssun Kung, and David Cox. Triton: an intermediate language and compiler for tiled neural network computations. In Proceedings of the 3rd ACM SIGPLAN International Workshop Machine Learning and Programming Languages, pages 10-19, 2019.
[49] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprini arXiv:2307.099 09288, 2023.
[50] Vivien Tran-Thien. Fast, high-fidelity IIm decoding with regex constraints, 2024.
[51] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances neural information processing systems, 30, 2017.
[52] Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Voyager: An open-ended embodied agent with large language models. arXiv preprini arXiv: Arxiv-2305.1629) 2023.
[53] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe V Le, Ed H Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, 2022.
[54] Brandon T Willard and Rémi Louf. Efficient guided generation for large language models. arXiv e-prints, pages arXiv-2307 2023.
[55] Qingyun Wu, Gagan Bansal, Jieyu Zhang, Yiran Wu, Shaokun Zhang, Erkang Zhu, Beibin Li, Li Jiang, Xiaoyun Zhang, and Chi Wang. Autogen: Enabling next-gen 11m applications via multi-agent conversation framework. arXiv preprint 1rxXi::308.08155 2023.
[56] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. arXiv preprint arXiv:2305. 10601, 2023.
[57] Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. The Eleventh International Conference on Learning Representations, 2022.
13

---

[58] Lu Ye, Ze Tao, Yong Huang, and Yang Li. Chunkattention: Efficient self-attention with prefix-aware kv cache and two-phase partition. arXiv preprint arXiv:2402.15220, 2024.
[59] Zihao Ye, Lequn Chen, Ruihang Lai, Yilong Zhao, Size Zheng, Junru Shao, Bohan Hou, Hongyi Jin, Yifei Zuo, Liangsheng Yin, Tianqi Chen, and Luis Ceze. Accelerating self-attentions for Ilm serving with flashinfer, February 2024.
[60] Gyeong-In Yu, Joo Seong Jeong, Geon- Kim, Soojeong Kim, and Byung-Gon Chun. Orca: A distributed serving system for { generative models. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22), pages 521-538, 2022.
[61] Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. Hellaswag: Can machine really finish your sentence? In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 4890, 2019.
[62] Yuanhan Zhang, Bo Li, haotian Liu, Yong jae Lee, Liangke Gui, Di Fu, Jiashi Feng. Ziwei Liu, and Chunyuan Li. Llava-next: strong zero-shot video understanding model, April 2024.
14

---

Pronge
Towdeet surple
Atrwer
hompt
Towefes sumple
Dasties
Anywer
Few-shot learring
brech
Beech
Scuch valay
Neahh11
Searc Howe
L.E
L.I
homp
Duertin
Anser
Corerstion
Teark Hooe
1.21
Freahh 1:11
Self-conssterry
Gontiee
Rueck?
Chat Halery
Searcs vistary
Imanc 22
Fuech22
Hiterry
Hioors
Granch 2.11
2214
Mutti turn chat
(d) Tree- of thought
Figure 9: KV cache sharing examples. Blue boxes represent shareable prompt parts, green boxes indicate non-shareable parts and yellow boxes mark non-shareable model outputs. Shareable elements include few-shot learning examples, questions in self-consistency [53], chat history in multi-turn chat, and search history in tree-of-thought [56].
A
Additional Details on RadixAttention
A.1 Background on the KV Cache
Most LLMs in use today, such as GPT-3 [5], PaLM [9], and LLaMA [49], are based on the autore- gressive Transformer architecture [51]. These models predict the probability of the next token in sequence based on the preceding tokens. During inference, the model first processes sequence of input tokens through forward pass (this process is called "prefill"). It then sequentially decodes output tokens, with each token depending on prior tokens (this process is called "decoding") ") We refer the process of taking a sequence of input tokens and generating sequence of output tokens call. Throughout this process, each token generates some intermediate tensors, which are used for decoding further tokens. These intermediate tensors, known the "KV Cache," are named for the key-value pairs in the self-attention mechanism. An important observation when discussing optimizations this paper is that the computation of KV cache only depends on all previous tokens, so different sequences with the same prefix can reuse the KV cache of the prefix tokens and avoid redundant computation.
as
Often in LLM programs, multiple text segments and generation calls are appended to single prompt. Caching the computed KV cache for previous tokens across multiple chained calls can reduce redundant computation. This optimization, however, is neither free nor trivial, as it requires additional storage and more complex memory management. In addition, it is common in LLM programs to generate multiple outputs from a single prompt or to fork new prompt from the current state [25]. Basic prefix sharing has been investigated in vLLM [23]. More advanced sharing patterns like irregular tree-structured sharing can also be employed. Fig. shows four typical patterns of K cache sharing across multiple calls; none of the existing systems can automatically handle all of them. On the contrary, our Radix Attention in Sec. 3 can handle all of them automatically at runtime.
A.2 Pseudocode for Cache-Aware Scheduling
Alg. shows the pseudocode of cache-award aware scheduling for RadixAttention with continuous batching.
A.3 Proof of the Theorem 3.1
Theorem 3.1. For batch of requests, we can achieve an optimal cache hit rate by visiting the radix tree of the requests in the depth-first search order, with cache size 2 the maximum request length. The sharsss---rrdde-------e-
order is equivalent a depth-first search order.
Proof. First, we show that the depth-first search (DFS) order achieves an optimal cache hit rate. Let R denote the set of requests in the batch, and T denote the radix tree built from R. For each edge of T. the KV cache associated with e needs to computed least once. Let |el denote the size of the KV cache associated with Let C denote the computational complexity of the KV cache for R.
15

---

Algorithm Cache-Aware Scheduling for RadixAttention with Continuous Batching.
Input:
The radix tree T. the memory pool P. the current running batch B, the waiting queue Q. Output: Finished requests and updated system state.
I/ Get all requests from the waiting queue
requests + Qeget all requests()
I/ Search for the prefix matching for all waiting requests for req E requests do
req.prefiz_nodde i_dee, fex.prefix len <- gaanech_peeixxreg.nnntttooo end for
// Sort the requests according to the matched prefix lenghts
requesls.sort)
I/ Select requests for the next batch
available _izze +- 7. eevictable__szee( Paavalable_size()
current size 0
new hee__atchhhtee +
for req E requests do
req.size() + current_sicc size < available_size then
new hew._baachhappeed(fee..
delta +- T.nnreaaee ref_counter(reegpge fragg/preeffeaaeee
currenl_size + current_size + della end end for
geemove_requests/e _btcc)
Insert requests into the current running batch B. merrge(new batch)
Allocate new memory and do eviction if necessary needed _iieddssseeeeee + B. needde _ineded_size()
success, bu fer +- Palloc(nceded__i size) if not success then T.evict(needed__e _sizze)
success, bus f'rr +- Palloc(needed__siz) end
B. run(buuffer
Process finished requests
finished - B. faa_jjiiideequusseeee
for req E Fimished_requeste do
T. T.decrease ref reweree_eueeee www.ooonrrrrg.preeeefee node) T.inser((req) end for return fimished_requesl
We obtain the lower bound
C2
Σ le].
eEedges(T)
Consider we visit the radix tree T' in DFS order. For each edge of T' the first time we compute the KV cache associated with e, we will then compute the whole subtree e. During the computation of the subtree of the edge will be continuously hit, finishing the computation for the subtree rooted at e, the edge e will not be visited again. Notice that, with cache size the maximum request length, which equals the longest path in the radix tree T. edge e will not be evicted during the computation its subtree, since the common prefix including e of the subtree will be continuously hit. Therefore, the KV cache associated with each edge e will be computed only once. Thus, we achieve the lower bound
additional computation will happen. After
C=
Σ le].
(T)dges(T)
16

---

The cache hit rate, defined as
Erer number of cached prefill tokens in r Erer number of prefill tokens in r
equals Σrer r number prefill tokens reaches its upper bound, delivering optimality.
Next, we show that the longest-shared-preee prefix-first order is equivalent to DFS order by induction.
(Base) In the beginning, since there is nothing cached, random request that corresponds to a node x in 7 will be processed. All requests that correspond to the nodes {UI,.., Fn on the path from the root to x do not need recomputation. The computation complexity for requests corresponding to the nodes {ei,..., Un, } is aligned with a valid DFS. The path from the root to is cached.
(Induction) Assume we just visited a node in T, and the visited nodes align with a DFS order. Let P' denote the path from the root to y. Then each node that has not been visited has the lowest common ancestor with the visited nodes on P. Since nodes on P are cached, a node that has not been visited with the lowest common ancestor on P will have the longest shared prefix. The longest-shared seeedd-rff--fffieee first order will select 2, which is a valid DFS order. The path from the root to will be cached because is the most recent.
In the online case, the DFS order will be disrupted, but the longest shared prefix schedule still approximates the DFS behavior on the augmented part of the implied radix tree. We show this by considering the step of adding a new batch of requests.
Let T denote the part of the radix tree that has been visited so far, and T" denote the whole new radix tree after adding the new batch of requests. Let C' denote the set of cached nodes in T. Let longest(C") C*) denote the node in C that has the longest path from the root and has a subtree in T that has not been fully visited.
The longest shared prefix schedule will then process the subtree in T' rooted at longest(C) in a DFS order. During this process, eviction could occur, and the remaining cached nodes from C' become ((2) S C. A DFS will then occur for the subtree in T" rooted at longest(C(!)).
Similarly, we will have C(2),... C(K),, until ((R) contains only one Icaf node in C*(k) that has its subtree in I not fully visited. At this point, we have reached valid DFS state. The remaining part of will be visited in DFS order as described the proof of Theorem 3.1.
A.4 Data-Parallel Distributed RadixAttention
To adapt the RadixAttention for distributed settings with multiple replica workers (i.e., data par- allelism). we developed mechanism wherein each worker maintains its own sub-tree, while the router oversees meta-tree. This meta-tree acts as a trie that tracks all sub-trees and their associated devices. Upon the arrival of new batch of requests at the router, prefix matching executed on the meta-tree. We implement various policies based on each request's affiitt-mmasuree measured by the length of the shared prefix with specific workers and other requests in the same group to make efficient dispatch decisions that minimize redundant computations. Each time new requests are processed, both the router and workers independently update their respective trees. Should an eviction occur at worker node, it commits this eviction to a queue, which the router then processes to update the meta-tree during periods of low activity. We benchmarked this distributed configuration using four workers and the MMLU dataset, observing that achieves linear scaling and an optimal cache hit rate with minimal overhead from this weakly consistent distributed cache design. There exists a trade-off between maximizing data locality and parallel processing efficiency. Exploring advanced scheduling policies to optimize this trade-off is designated as an area for future research. In addition, concurrent work from Preble [45] studies data-parallel scheduling based on an early version of SGLang.
B Additional Details on Compressed Finite State Machine
This section discusses the background and implementation details of the compressed finite state machine for faster constrained decoding. We aim for LLMs to follow regular expression (regex),
17

---

which offers greater expressiveness and can be used to represent common formats such as JSON schemas. To achieve this, we convert the regex into a Finite State Machine (FSM) guide the generation process during decoding [54]. An FSM is essentially graph with nodes (states) and edges (transitions with strings/characters). Starting from an initial state, each transition appends the string on the edge to move to the next state, using set of final states to conclude the process. This mechanism guides an LLM's decoding, filtering out invalid tokens based on the FSM's current state transitions, as illustrated in Fig. 10. The decoding might involve multiple transitions in the FSM until reaching a final state.
[e-9]
"nare": "Tiidiee
mesasttie [0-9]=,
[0-9]
"house": "(ryfffindar(sycheeca sagpppeeet//aeeecaaaa//aaoarrrrr
Regular Expression
Finite State Machine
Please fill in the following information about Harry Potten.
Decode FSW
Please fill in the following information about Harry Potter.
Decode
FSM
"nane": "Harry",
age /
"name"; "Harry", "age":
Age X
hou x
fif x
Decoding Status
Decoding Status
allowed next token
x not allowed next token
Constrained Decoding With Logits Mask
Figure 10: Example of how regex is converted into FSM and how FSM guides the decoding process.
The challenge of constrained decoding arises from the fact that constraints are often expressed in natural language formats, i.e., regex is depicted by characters/strings, while LLMs are designed to interpret and process these tokens. This creates complex scenario since the mapping between strings and tokens is intricate and lacks one-to-one correspondence [22].
This section is derived from earlier blog post'. Readers also encouraged read the blog post for additional background and easier understanding.
B.1 Implementation Details of Compressed Finite State Machine
To simplify the construction of Compressed FSM, we build the original FSM on characters/strings instead of on tokens. We formally define the concepts of singular transition edge and compressed edge follows:
Singular transition edge: edge singular transition edge if its source node has only one successor node, and 2) there is only one acceptable character/string on it.
Compressed edge: An edge compressed by several consecutively adjacent edges (Eg, ....... ex) ,,
if and only if ci...., Gj are singular transition edges. The text of the compressed edge is the concatenation of the texts Eg. eg,...,e..
Starting from an FSM based on characters, we recursively merge singular transition edges into their preceding ones until further compression is unfeasible, resulting in Compressed FSM. This approach speeds up the decoding process, as demonstrated by SGLang's 's runtime efficiency with the Compressed FSM, shown
Fig. 11.
B.2 Handling Tokenization Artifacts with Retokenization
When a new token is generated, we get the token's string and search the outgoing edges of the current state find the that starts with the just decoded string, and then move forward. However, when the transition edge is a well-compressed one and contains a very long string, we may anticipate the next rounds' decoded strings well. This is where the acceleration happens and we call this process Jump Forward. However, we still need to convert the string into tokens for the next decoding phases and it is not straightforward due the LLM's specific pretraining and tokenization method;
http://mmayyrrrrr/l////2//-2--22 http://///00000000occoceeeeeeeee compressed-fen.
18

---

Please FI11 in the folloxing
Pllesse FiLL following
intermation about Harry Potser.
Har
PoLter
"age"
Thouse":
ryfFinder",
</S>
Tage's 4iyyfFindon
Jurp-Forward Decode With Compressed FSM
Please Fill in the folloxing about Hanry Better.
name
Please fill in the to following Inforr action about Horry Potton
Profil
Ind
Bacoda
Normal Decode With
Generated JSONs
Figure 1I: Comparison decoding using Compressed FSM versus normal FSM: The left subfigure depicts the decoding process per forward pass, while the right subfigure explains the origins of various result components.
direct partitioning might alter the intended meaning [50]. For example, the compressed text in Fig. 2's regex is ("summary": ". which can only be tokenized as {", summary, ": and according to the tokenizer instead of partition them randomly such {", summa, ry, and ": ". To address this issue, we use the original tokenizer to retokenize all the previous text as well as the text of the compressed edge, ensuring alignment with the original input format of LLMs. And it only brings minor retokenization overhead.
B.3 Future Extension: Addressing Distorted Probability
The challenge caused by the gap between strings and tokens also brings the problem of skewed proba- bility distribution [50]. For example, in Fig. 2, the regex [[ACD]] [+-]?" suggests grades from A+ to D-, but if replaced with broader terms like Excellent Above Average Fair BBllow Average, the runtime may inaccurately map an to Above Average due to the term Above Average is on a compressed transition, misrepresenting the grade hierarchy. This occurs because the L.LM doesn't 't recognize the specific range of choices, leading to inappropriate token sequences. Computing accurate probabilities for each choice requires summing the probabilities of all token sequences that result in each choice, which complicates decoding and adds overhead. One workaround is to include the choices the regex directly the prefill prompt, guiding the LLM to be aware of its choices and output the decision in proper token sequences. However, this approach doesn't I solve the underlying issue of distorted probabilities, highlighting the need for further research improve the compressed FSM's 's accuracy.
C Additional Experimental Setups and Results
Additional experimental setups. Fig. and Fig. are obtained by running Llama-7B on a single A10G (24GB) GPU. Fig. 7 are obtained by rumning Mixtral-8x7B on A10G (24GB) GPUs with tensor parallelism. Fig. 8(c) is obtained by running Llama-7B on a single A10G (24GB) GPU. Fig. 12 obtained by running Llama-70B obtained by running LLaVA--1.557 1.5-7BB on a single AOOG (24GB) GPU and running LLaVA-Next-344 on a single A100G (80GB) GPU. Each bar the benchmark figures takes several minutes to an hour to run.
4 A A100G (80GB) GPUs with tensor parallelism. Table 2
Additional experimental results. Fig. 13 shows the achieved and optimal cache hit rates the benchmarks listed in Fig. 5. Fig. 12 shows the throughput on Llama-2-70B with tensor parallelism.
D Compiler Mode
Besides the interpreter mode used the main body of the paper, another way run SGI Lan programs to compile them computational graphs and execute them with a graph executor. This opens up
19

---

SGLang
0.5
MMLU
RoÁct Agents
Generative Agents
Tree of Thought of Thought
Skeleton
LLM Judge HellaSwag
JSON
Multi-Turn Multi-Tum DSPy RAG
Decoding Chat(short) Chatilong) Pipeline
Figure 12: Normalized throughput on Llama-2-70B models with tensor parallelism. Higher better.
Achieved cache hit rate with SGLang
Optimal cache hate
80.0
60.0
Cache
20.0
MMLU
ReAct
Generative
Tree of Skeleton LLM Judge HellaSwag Decoding Chattshart) Chatllang) Pipeline
ISON MultiTTrn Multi-Turn DSPy RAG
Agents
Agents
Thought of Thought
Figure 13: Achieved cache hit rate and optimal cache hit rate on various benchmarks.
opportunities for more compilation optimizations, as we can rewrite the graph and perform more static planning.
D.1 Design and Implementation
We designed intermediate representation (IR) for SGLang, which represents SGLang program structures and operations as a computational graph. This graph includes nodes for primitive operators and edges for dependencies. See Fig. 14b for the graph corresponding the program in Fig. 14a. In the program, each call to a decorated function or fork creates a new prompt state or a stream.
There are several types of nodes. Each operand of the operators += and in SGLang program represented by an IR node. These include ConstantText, Argument, Gen, Select, Variable, Fork, GetForkIten and Join. There are two types of dependencies: intra-stream dependency, where operations submitted into a stream using + must be executed after all preceding operations in that stream, and inter-stream dependency, which occurs when stream needs to fetch variable values from another stream, necessitating synchronization. Operations like fork manipulate multiple streams and thus introduce inter-stream dependencies.
To generate the graph, we use tracing to run the program with abstract arguments and construct the graph dynamically. This method is limited to programs without data-dependent control flow, limitation we plan to address in future work. Once constructed, the graph can be executed through graph executor, eliminating the need to reinterpret the original Python program. This results in benefits like graph rewriting optimizations, reduced runtime overhead, and program serialization. For execution, stream executors are launched for each data stream, dispatching IR nodes to the streams in topological order.
D.2
Case Study of Compiler Optimization: Code Movement for Improving Prefix Sharing
We explore a compilation optimization for SGLang IR: code movement for improving prefix sharing. We anticipate that more classical compiler techniques can also be applied, such as auto-tuning and instruction selection.
This optimization aims to improve prefix sharing by reordering nodes in the graph to increase the length of the constant prefix. does strictly preserve the original computation, classifying it as an aggressive optimization. For instance, changing the prompt from "Here is a question + [question]. math expert and solve the given question." " to "Please act math expert and solve the given question. Here is a question + [question]." results in longer shareable prefix. This optimization interesting because traditional program analysis cannot achieve due to the presence of natural language instructions in SGLang. Instead, we prompt GPT-4 to reorder graph nodes. We write prompt with several examples to teach GPT-4 the concepts of SGLaang IR, and we find that GPT-4 can successfully apply this optimization for some simple SGLang programs.
Please
20

---

Condorifiin ("Here arc
Argument (toprd
Consarntion: Coee)
Constommioat (')
Stream 2
expand(s, tip):
Ben 1* 11
Constantiod "Pleaae expand "1
"Flease expand the following tip into "detafled parograph: tip "In"
Consoantiion: Ve
Varable (tpp17
gen( "en("paragroph")
Constomrieat ('2
Condanttien Ve')
efunction
Fan Mo
Gerij paesraphh
def iigsss topic):
concise tips topic "nln"
Constantion: (e
Stream 3
ConstantTeat (Th 1:
ConstontTeat Pleane expand .?)
Generate skeleton two short tips
5 -- "1." cen("tip_11 1", stop=["\n", 7: (.1) "An" 5 "2." 2=n stop=("Va", """"" *in, ") "L""
Variable (arraguph")
Variable [tpp_")
Constantren (e
ConstantTen Ve')
i Expand the tips into detailed paragraphs in parallel detailed tipt "=pano(tipps("tipp_"") detailed_tip2 Expmmi(tipss""tip22
Constunthatt (Tpp
Goni"paraprap""1
Varable ('porggoph")
genenate suerary
"Táp 1: detailed "paragrpaarpp""" "M""
] "In"
Constantied Vel
"Tip 2:
5 "In sumrary" gen( ("Sumary"")
Constanthot I" summary' )
state tip cegeestioo.runttpttt.. "staying healthy") prinz(state. toxt())
Gen (onmmmm-sssmmar
(b) computational graph for the program in Fig. 14a. The three streams correspond to three func- tion calls.
(a) The SGI Lang program for paraliel tip suggestion with skeleton-of-thouge prompting.
Figure 14: An SGLang program and its corresponding dataflow graph.
We evaluate the effectiveness of this optimization. We collect 20 prompt templates from the internet and implement them in SGLang. We utilize of these templates as few-shot training examples and the remaining 15 as test cases. Our evaluation shows that, for 12 out of the 15 templates, GPT-4 successfully reorders the graph nodes without altering the semantics, as confirmed by manual inspection of the modified prompts. On average, this optimization results in 60-token increase in the shareable prefix length, showcasing GPT-4's effectiveness. Failures in creating optimized prompt order come from incorrect understanding of the semantic meaning behind the graph nodes. It is too aggressive and puts all constants upfront even when such ordering changes the original semantics. This case study aims explore the of GPT-4 for compiler optimizations, More work is needed to make these kinds of optimizations reliable in the future.
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims in the abstract and introductions are empirically verified by the experimental section (Sec. 6).
Guidelines:
The answer NA means that the abstract and introduction not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. It is fine include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations and future directions address them are discussed in Sec. 8.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or a speech-to-ters system might not be used reliably provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The proof of the theorem is in Sec. A.3.
22

---

Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they uppear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented
by formal proofs provided in appendix or supplemental material. Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: The experimental setups are described in Sec. and Appendix C. The code is available.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reprodueible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., e. large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case closed-source models, it may be that access to the model limited some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
23

---

Justification:
The code is available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
public/ public/guides/ gewidee/CoeeSubbeee Sondeeuummissoonii
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //nips.. ccccccppllc htc/pulic//aec htt//guide/////oeee /wt////oouuiiiaec commissiinn pasionPolicyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only a subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experimental setups are described in Sec. and Appendix C. The code available.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core of the paper to level of detail
that is necessary to appreciate the results and make sense of them. The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We measure the throughput and latency by running a sufficiently large number of requests and reporting the average. These results are highly deterministic, so we do not include error bars in the figures to maintain clarity. The improvements are statistically significant.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar the standard deviation or the standard error of the mean.
24

---

It is OK to report 1-sigma enror bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetrie distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If ertor bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: The experimental setups described in Sec. 6 and Appendix C. We use common NVIDIA GPUs to conduct experiments. The code available.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
The research respects NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special considera- tion due laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
The techniques introduced this paper make the use of large language models easier and more efficient. They do not have additional direct societal impact beyond the existing societal impact of large language models. However, because they accelerate the execution of LLMs, they may amplify the existing societal impact of these models, whether positive or negative.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
25

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, there direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology being used intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper does not release new datasets models, this is not applicable.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. We recognize that providing effective safeguards is challenging, and many papers do not require this, we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: This paper uses open-weight models and public datasets for experiments. The usage respects all the original licenses.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the pack- age should be provided. For popular datasets, paperswithcode. thcode. com hom/dattset has
curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out the asset's creators.
26

---

13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We release the source code under the Apache 2.0 license.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
27


Reviews:
[{"review_id": "XtIxy6yTNs", "reviewer": "Reviewer_QRuS", "summary": "This paper introduces SGLang, a comprehensive framework designed to enhance frontend LLM-based prompting/programming and to accelerate the runtime inference of LLM programs. In the frontend component, SGLang employs a meticulously structured primitive to streamline LLM prompting and support parallel execution. For the runtime component, the framework incorporates radix attention to optimize KV-cache reuse, implements LRU eviction of nodes in radix tree, and proposes more effective decoding with compressed finite state machine. This runtime significantly improves LLM inference efficiency. Experimental evaluations conducted on diverse LLM models across multiple downstream decoding tasks demonstrate the superior performance of SGLang.", "questions": "This paper presents a comprehensive framework for the formulation of LLM prompting/programming and the acceleration of inference processes. The introduced method is both impressive and elegant, demonstrating extensive evaluations on both open-sourced and close-sourced LLMs that appear highly promising. This paper constitutes a substantial and significant contribution to the LLM serving community. I have some particular questions of the design inspirations and the detailed insights presented in the implementation.\n- For the frontend component, the selection of primitives such as [gen], [fork], and [select] for building language programs is intriguing. I am interested in the inspiration of selecting these operations, like they are considered atomic and any language program can be represented through combinations of these primitives? \n- The framework's implementation of an LRU eviction policy for managing nodes within the radix tree, which maps tokens to KV-cache tensors, is notable. However, I am wondering about the performance of alternative eviction policies, such as LFU.\n- Regarding the inference of close-sourced LLM endpoints, such as GPT-4, the paper mentions that it facilitates inference through speculative decoding. However, I have the question that how this can be implemented in detail, like it is based on streaming and setting stop points during generation or else?", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Great writing and presentation. \n- Its proposed framework of formulating LLM-based prompting/programming in the frontend， and redesigning KV-cache as radix attention in the backend is neat and elegant. It is a significant contribution to LLM serving.\n- The evaluation is extensive and solid. The results compared with powerful inference acceleration are very promising.", "weaknesses": "N/A", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your valuable feedback. We will incorporate the clarifications and address the issues in the next draft. Here is our response to your questions:\n\n> For the frontend component, the selection of primitives such as [gen], [fork], and [select] for building language programs is intriguing. I am interested in the inspiration of selecting these operations, like they are considered atomic and any language program can be represented through combinations of these primitives?\n\nWe select these primitive operations by summarizing the typical usage of LLMs. We summarize the usage patterns in the [OpenAI prompt engineering guide](https://platform.openai.com/docs/guides/prompt-engineering), the [Anthropic prompt engineering guide](https://docs.anthropic.com/en/docs/build-with-claude/prompt-engineering/overview), and more than ten papers on prompt design.\n\nIt cannot be guaranteed that any language program can be represented by combining these primitives. However, SGLang can be easily extended to support new primitives. In addition, there are low-level APIs in SGLang that can access the probabilities of every token, which can theoretically do almost anything. These APIs are not introduced in this paper, but they can be useful when existing primitives are insufficient.\n\n> The framework's implementation of an LRU eviction policy for managing nodes within the radix tree, which maps tokens to KV-cache tensors, is notable. However, I am wondering about the performance of alternative eviction policies, such as LFU.\n\nThe effectiveness of an eviction policy highly depends on the workload. We can easily support the LFU eviction policy as well. We compare LRU and LFU on our benchmarks: MMLU, Tree-of-Thought, and multi-turn chat. We find that LRU performs slightly better because our workload exhibits better temporal locality. We will add more experiments in the next version.\n\n> Regarding the inference of close-sourced LLM endpoints, such as GPT-4, the paper mentions that it facilitates inference through speculative decoding. However, I have the question that how this can be implemented in detail, like it is based on streaming and setting stop points during generation or else?\n\nIt is implemented by getting the output chunk by chunk. It is not exactly streaming. For example, we set a parameter `num_api_spec_tokens`, which defines the number of speculative tokens. If this number is 64, we always request 64 tokens from the API endpoint and cache them. Then we match on these 64 tokens. If the speculation is correct, all 64 tokens will be used.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2jNb1iBo6J", "reviewer": "Reviewer_P67b", "summary": "The authors introduce and evaluate SGLang, a LLM language and implementation that can perform inference or use an external API. They claim significant performance improvements mostly though cache redesign.", "questions": "My questions were asked above.", "limitations": "The system above may have a significant impact on the community, hopefully  positive.\n\n\n\nThe authors do focus on speeding existing LLMs, only.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "I liked the Python-embedded language. It seems relatively straightforward to use. The results look also pretty good for the cache, less so for the reg exps. The authors also claim good results in interfacing with Chat-gpt3.", "weaknesses": "The authors provide a  nice example of their language, but very informal. Is the language just what you mention here.?\n\nRadix trees are a good solution for data that tend to have the same prefix. This is common in web-data, such as URIs, but may not be so worthwhile in other types of data. It would be helpful to see how much this technique across the different benchmarks.\n\nHow do you select the least recently used cache entry?\n\nI wonder whether your scheduling strategy may lead to starvation.\n\nSection 4 is mostly a pointer  to App B,\n\nI missed a description of the absolute times. One thing is to speedup 1 ms. and another 1000 days, Also, I imagine this will take as much GPU memory as it can take, it would be nice to evaluate the cost of  memory usage,\n\nFinally you mention speeding for paralleillsim. One other important consideration is cost. YOu seem to do that, but I could  not find that clearly in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your valuable feedback. We will incorporate the clarifications and address the issues in the next draft. Here is our response to your questions:\n\n\n> The authors provide a nice example of their language, but very informal. Is the language just what you mention here.?\n\nWe introduced the language informally, covering 90% of its features. While we refer to it as a \"language,\" it's similar to how NumPy and PyTorch are considered \"array/tensor computation languages embedded in Python.\" If needed, we can provide a more formal description.\n\nThe language is designed to be intuitive and extensible, allowing you to easily add new primitives. Our submitted code includes more APIs and usage examples. Many researchers have adopted this language and used it to develop various workflows.\n\n> Radix trees are a good solution for data that tend to have the same prefix. This is common in web-data, such as URIs, but may not be so worthwhile in other types of data. It would be helpful to see how much this technique across the different benchmarks.\n\nWe tested 12 different workloads in this paper. The prefix cache hit rates for these workloads are shown in Figure 12 in Appendix C (L274 in the original paper). The cache hit rates range from 50% to 99%, indicating that the shared prefix is very common.\n\nAdditionally, SGLang has been deployed in Chatbot Arena for real-world online serving. We observed a cache hit rate of more than 50% (see L295 in the original paper). This is because, in a multi-turn chat, the chat history serves as an accumulative prefix. Every new turn triggers a cache hit. (see also Figure 8)\n\n> How do you select the least recently used cache entry?\n\nWe keep a timestamp on every tree node. The timestamp is updated every time that node is accessed. During eviction, we sort the leaf nodes based on this timestamp.\n\n> I wonder whether your scheduling strategy may lead to starvation.\n\nThe scheduling strategy can lead to starvation. In L188 of the original paper, we mentioned this limitation. This limitation can be addressed by integrating simple lottery scheduling or more advanced fair scheduling [42].\n\n> I missed a description of the absolute times. One thing is to speedup 1 ms. and another 1000 days.\n\nEach benchmark in this paper typically takes several minutes to half an hour. This is because we mostly pick small datasets for faster experiments. The speedup will be 100% transferable to larger datasets. We will include a table showing the absolute time in the next version.\n\nThe relative speedup is more relevant. For example, OpenAI runs the ChatGPT service, which can cost $700k per day (https://www.semianalysis.com/p/the-inference-cost-of-search-disruption). A small relative gain will translate to a huge absolute gain.\n\n> Finally you mention speeding for paralleillsim. One other important consideration is cost.\n\nYes, using more GPUs can achieve lower latency at a higher cost. We mention parallelism to show that our technique is fully compatible with all parallelism strategies (data parallelism and tensor parallelism). Users can choose which parallelism to use based on their cost and latency requirements. Sometimes, adding more parallelism can be even more cost-efficient because it resolves some bottlenecks in the system (e.g., more GPU memory -> larger batch size -> more reuse).\n\n--- \n\nPlease let us know if the answer addresses the weakness. We would greatly appreciate it if you could raise your score if you find the answers helpful.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UFkaq3YyX6", "reviewer": "Reviewer_PeTj", "summary": "The paper introduces SGLang, a system designed for efficient execution of complex language model (LM) programs. SGLang consists of a frontend language that simplifies programming with generation and parallelism primitives, and a runtime that boosts execution speed through several optimizations. The paper describes two main contributions: RadixAttention for Key-Value cache reuse, and a compressed finite state machine for constrained decoding. It also describes a method for API speculative execution. The evaluation demonstrates that SGLang achieves significantly higher throughput and lower latency on various tasks when using open-weights models.", "questions": "Have you tried any other examples for the public API evaluation, or is it only the wikipedia extraction example? In general, what class of LM program is well-suited for those optimisations? \n\nMinor comments and suggestions for improvements:\n*  line 48: is there a missing “at” in “multiple tokens can often be decoded (at) once”?", "limitations": "I thought the limitations were well and clearly addressed and I liked the wide range of suggestions for future work.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "* Quality: The evaluation is thorough, with experiments conducted on a diverse set of LLM workloads, including agent control, logical reasoning, few-shot learning benchmarks, JSON decoding, retrieval-augmented generation pipelines, and multi-turn chat. The results show substantial improvements in throughput and latency for open-weights models. I would also like to commend the authors for clear and transparent description of the challenges and limitations of the work. \n* Clarity: The paper is very well written, providing a clear overview of the problem, detailed explanations of the contributions, and comprehensive descriptions of the evaluation methodology. I like the figures, which I thought are helpful in understanding the overall system and the contributions of the paper. \n* Significance: In my opinion, this work is highly relevant to current developments in programming with large language models. The tools and techniques introduced in SGLang are likely to be valuable for practitioners working on complex LM applications. \n* Originality: I am not familiar well enough with the related work to be able to evaluate the originality of the paper.", "weaknesses": "If I have one weakness to mention, it would be that the contribution and evaluation related to API models seem relatively minor compared to the other contributions. Providing more details on optimizing API calls to public API models and including more examples in the evaluation would strengthen this aspect of the paper (in addition to being valuable to practicioners).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your valuable feedback. We will incorporate the clarifications and address the issues in the next draft. Here is our response to your questions:\n\n> Providing more details on optimizing API calls to public API models and including more examples in the evaluation would strengthen this aspect of the paper.\n\nWe will add a detailed example in the main body if space allows, and in the appendix otherwise.\n\n> Have you tried any other examples for the public API evaluation, or is it only the wikipedia extraction example? In general, what class of LM program is well-suited for those optimisations?\n\nWe also tested some DSPy retrieval-augmented generation pipelines. This optimization is inspired by these real-world workloads. In general, an LM program with few-shot examples that asks for multiple fields in the output will be well-suited for these optimizations. The few-shot examples can hint at the format, thereby increasing the success rate of speculative execution. Asking for multiple output fields is also necessary to make this optimization effective because it can automatically merge them into a single call.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jSF87UOiyS", "reviewer": "Reviewer_U8WY", "summary": "This paper introduces SGLang, a programming language for large language models (LLMs) that enables users to write programs specifying prompts in natural language and control flow with Python and execute them to call LLMs as needed. ​ SGLang provides a set of language constructs and functions that allow users to express complex tasks especially parallelizing multiple LLM calls. ​ The paper presents various optimizations and techniques for improving the efficiency and performance of LLMs, such as reusing  KV cache across multiple LLM calls and compressed finite state machines to decode multiple tokens simultaneously during constrained decoding. ​ Experimental results demonstrate the effectiveness of these techniques in improving the throughput of various LLMs on various tasks. ​", "questions": "1. How does the model handle model failures especially with token limitations and timeouts with API models? Does the approach give control to users to specify how they would want to handle these failures? \n\n2. The experiment report on the effectiveness of the compressed finite state machine is not very clear. Can you explain why compressing the state machine can lead to lower throughputs in some cases and under what circumstances this occurs?", "limitations": "Limitations are addressed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is well written. I thoroughly enjoyed reading the paper. The authors have done extensive exploration of the system space. Every alternative of the system that a reader could have think of, they have tried to answer it. For example, the authors present both an interpreter version and  a compiler version to execute SGLang programs; they consider multiple modes of accessing the models such as batch mode and sequential mode. In-addition to implementing cache reuse, they also explored cache-aware scheduling algorithm to further take advantage of the cache. They even handle multiple models sizes including those requiring distribution across multiple GPUs.\n\nThe experiments are also very extensive and try to assess the value of each component individually and together and show a clear empirical advantage of this system over other existing system. \n\nOverall, the paper is interesting and well thought-out, showcasing significant contributions to the field.", "weaknesses": "While the paper covers many interesting aspects, some parts did not receive as much attention. For example, optimizing for API-based model calls is not thoroughly explained or explored, but that is also not the main goal of the paper. Hopefully, future papers will handle and explore them more thoroughly. \n\nMinor: consider using phrases like \"improves throughput by x times to y times\" instead of  phrases like \"improves throughput up to 6.4x\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your valuable feedback. We will incorporate the clarifications and address the issues in the next draft. Here is our response to your questions:\n\n>  For example, optimizing for API-based model calls is not thoroughly explained or explored, but that is also not the main goal of the paper.\n\nWe will add a detailed example in the main body if space allows, and in the appendix otherwise.\n\n> How does the model handle model failures especially with token limitations and timeouts with API models? Does the approach give control to users to specify how they would want to handle these failures?\n\nYes, SGLang has error handling APIs as well. They are not introduced in the paper due to space limitations. Basically, the state will record any errors it encounters. After an SGLang program finishes or terminates due to errors, the user can fetch all error details. Depending on the error type, users can write their code to handle or retry them.\n\n> Can you explain why compressing the state machine can lead to lower throughputs in some cases and under what circumstances this occurs?\n\nSorry for the confusion. Line 325 reads: \"Otherwise, redoing the preprocessing for each request makes the throughput 2.4× lower.\" This means that without our cached preprocessing optimizations, redoing the preprocessing every time will be much slower. Please note the word \"Otherwise\" at the beginning. This emphasizes that our optimization is very effective. We will improve the wording in the next version.\n\n--- \n\nPlease let us know if the answer addresses the weakness. We would greatly appreciate it if you could raise your score if you find the answers helpful.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MjYHXfNNqz", "reviewer": "Reviewer_N1WL", "summary": "This paper proposes SGLang, a system with  frontend programming interface and run-time optimization for efficient execution of LLM-based applications. For frontend programming interface, SGLang provides primitives for generation and parallelism control. For run-time optimization, SGLang has three key optimizations. The first is to maintain a LRU cache of the KV cache for all generation requests within a radix tree to enable the automatic reuse of KV cache across requests. The second is to build a compressed finite-state machine (FSM) to represent the constraint of the request with structured outputs. Through analyzing the  FSM, SGLang is able to decode multiple tokens of the given structured template at a time. The last is to reduce the number of endpoint API call with a speculative decoding mechanism on the first API call. Experimental results show that SGLang achieves up to 6.4× higher throughput compared to state-of-the-art inference system.", "questions": "See above.", "limitations": "N.A.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "1. This paper focuses on solving a critical problem: efficient inference of LLM-based applications.\n2. Instead of designing a new algorithm for efficient execution of LLM-basd application, this paper optimize from the prompt aspects, which is convenient to be applied and causes no harm for the accuracy.\n3. The author built a comprehensive system, containing both frontend programming interface and run-time optimizations and covering different optimization strategies.\n4. Experimental results shows that SGLang achieves a significant higher throughput compared to state-of-the-art inference system.", "weaknesses": "1. **No modular sensitivity study:** SGLang incorporates optimizations from various perspectives. These strategies are independent and can be applied individually or in combination. However, their effectiveness may vary depending on the context. Therefore, I recommend to include a sensitivity analysis in experiments to evaluate the specific benefits of each optimization strategy in enhancing inference efficiency.\n    \n2. **Limited real-world applicability:** The practical applicability of FSM and API speculative decoding is questionable in real-world scenarios. These optimizations appear to enhance efficiency primarily in specific instances, such as when processing JSON outputs with predefined structures or when executing multiple API calls within a single sentence.\n    \n3. **Add more baselines for RadixAttention evaluation:** In related works, the author noted that many existing studies have devised their own approaches for reusing key-value (KV) caches, emphasizing the distinctive nature of the designed RadixAttention. To further demonstrate the effectiveness of RadixAttention, it is recommended to include additional baselines such as PromptCache and API Serve in the evaluation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your valuable feedback. We will incorporate the clarifications and address the issues in the next draft. Here is our response to your questions:\n  \n\n> Weaknesses 1: No modular sensitivity study.\n\nSection 6.3, \"Ablation Study,\" in the original paper did what you asked for. In line 306, we conducted the sensitivity study of our first technique, RadixAttention. In line 321, we demonstrated the effectiveness of our second technique, the compressed finite state machine. In line 298 (section 6.2), we showed the effectiveness of our third technique, API speculative execution.\n\nAll techniques proposed in this paper include standalone sensitivity analyses. We will highlight these results more in the next version.\n\n> Weaknesses 2: The practical applicability of FSM and API speculative decoding is questionable in real-world scenarios.\n\nBoth optimizations originate from the real workloads we observed in production.\n\nThe compressed FSM for constrained decoding is a very general technique that can accelerate almost all constrained decoding workloads. OpenAI just released [a new feature on structured decoding](https://openai.com/index/introducing-structured-outputs-in-the-api/) this week, as this is one of the most desired features by the developers.  We tested the first two official examples and found that the compressed FSM can achieve a 1.3x to 1.6x speedup.\n\nThe API speculative decoding originates from some workloads from DSPy, a retrieval-argument-generation workflow. It typically uses few-shot examples to enforce a format and requires a single call to generate multiple fields. API speculative decoding can greatly reduce the cost of this.\n\n\n> Weakness 3: Add more baselines for RadixAttention evaluation\n\nThanks for the suggestion. We compared SGLang with the open-source code of PromptCache.\n\nIn terms of the idea, PromptCache focuses more on the modular reuse of the KV cache to reduce time-to-first-token latency. SGLang, on the other hand, is about the tree-structured automatic KV cache reuse. They did something similar, but SGLang provides a more general, automatic, and lossless solution.\n\nAlthough their original focuses are slightly different, we can still run the two systems on the same workload and compare their performance. We used their default recommended API to run the same workload, with both systems' caches turned on. Here are the results:\n\n| Framework                        | Time-to-first-token (ms, lower is better) | Decoding throughput (tokens/s, higher is better) |\n|----------------------------------|------------------------------------------|--------------------------------------------------|\n| PromptCache (batch size = 1) | 180.2                                     | 9.2                                              |\n| SGLang (batch size = 1)      | 21.3                                      | 80.4                                             |\n| SGLang (batch size = 64)     | 729.3                                     | 1302.8                                           |\n\nWe found that SGLang provides two major advantages:\n1. SGLang has much better system optimizations. With a batch size of 1, the time-to-first-token latency of SGLang is 8.5x better than PromptCache. This is because SGLang uses highly optimized kernel implementation and has a much better runtime implementation. The decoding speed of SGLang is also about 8.7x faster.\n2. SGLang supports continuous batching and can greatly improve the decoding throughput with a larger batch size.\n\n---\n  \n  \nPlease let us know if the answer addresses the weakness. We would greatly appreciate it if you could raise your score if you find the answers helpful.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Companies around the world are currently racing to apply LLMs to various problems and tasks.  Applying an LLM to a complex task typically involves interleaving requests/prompts to the LLM with code that processes results, and then issues new prompts.  In many cases, (e.g. tool use), the LLM must produce structured outputs (e.g. API calls).  

SGLang is a library/domain-specific language that simplifies many of the common issues that arise when using an LLM in this way.  It can issue queries sequentially or in parallel, re-use KV-caches (to avoid pre-fill costs), and place structural constraints on the output of the LLM.  Most importantly, the authors have implemented the library using a number of LLM back-ends, including both open-source LLMs, and commercial LLMs that are only available through an API.  

The reviewers unanimously recommend "accept" for this paper, and I concur.  As LLMs are incorporated into various products moving forward, libraries such as this one will become increasingly important.   SGLang may not be the final word on "how to we make LLMs easy to use for complex problems", but it seems like a valuable addition to the discussion.  The contribution of this paper is both timely and widely-applicable.  

I personally would have liked to see more discussion around the design space for SGLang.  What are the pain points for writing LLM-programs in general, and what problems are _not_ solved by SGLang?  For example, the authors use a finite-state-machine for constrained decoding, but the purpose mainly seems to be efficiency.  For tool use, one might like to apply stronger constraints, e.g. to ensure that the output is syntactically correct (which requires more than an FSM), and possibly even type-checks.
Decision: Accept (poster)