SGLang: Efficient Execution of Structured Language Model Programs

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:

Weaknesses 1: No modular sensitivity study.

Section 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.

All techniques proposed in this paper include standalone sensitivity analyses. We will highlight these results more in the next version.

Weaknesses 2: The practical applicability of FSM and API speculative decoding is questionable in real-world scenarios.

Both optimizations originate from the real workloads we observed in production.

The 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 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.

The 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.

Weakness 3: Add more baselines for RadixAttention evaluation

Thanks for the suggestion. We compared SGLang with the open-source code of PromptCache.

In 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.

Although 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:

We found that SGLang provides two major advantages:

1. 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.
2. SGLang supports continuous batching and can greatly improve the decoding throughput with a larger batch size.

Please 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.

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:

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.

We will add a detailed example in the main body if space allows, and in the appendix otherwise.

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?

Yes, 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.

Can you explain why compressing the state machine can lead to lower throughputs in some cases and under what circumstances this occurs?

Sorry 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.

Please 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.

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:

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.

We will add a detailed example in the main body if space allows, and in the appendix otherwise.

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?

We 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.

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:

The authors provide a nice example of their language, but very informal. Is the language just what you mention here.?

We 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.

The 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.

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.

We 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.

Additionally, 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)

How do you select the least recently used cache entry?

We 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.

I wonder whether your scheduling strategy may lead to starvation.

The 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].

I missed a description of the absolute times. One thing is to speedup 1 ms. and another 1000 days.

Each 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.

The 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.

Finally you mention speeding for paralleillsim. One other important consideration is cost.

Yes, 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).

Please 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.

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:

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?

We select these primitive operations by summarizing the typical usage of LLMs. We summarize the usage patterns in the OpenAI prompt engineering guide, the Anthropic prompt engineering guide, and more than ten papers on prompt design.

It 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.

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.

The 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.

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?

It 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.