acceptodds
Under review as a conference paper at ICLR 2027

Flow-Controlled Scheduling for LLM Inference with Provable Stability Guarantees

Abstract

Large language models (LLMs) have been widely adopted due to their great performance across a wide range of applications. ChatGPT and Gemini now serve hundreds of millions of active users and handle billions of user requests per day, which puts optimizing LLM inference into the spotlight. A key challenge in LLM inference is that decode lengths are unknown. The memory usage for each request grows with generated tokens, which may lead to overflow and cause system instability. To address this concern, we propose a simple flow-control framework that controls the rate at which prompts join the active set. For known output lengths, we prove that, for every arrival rate that is strictly inside the stability region, there exists a periodic policy that can be stable. We derive a necessary condition that any stable system must satisfy and establish sufficient conditions under which our algorithm can provably achieve stability. Experiments show that, compared to commonly used strategies in practice, our approach achieves higher request throughput and lower average latency.

Primary area:
optimization
Keywords:
LLM inference

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_w6bAOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper use results in queuing theory to optimize the admisson policy of inference engine. They provide a solid formulation for known output length of request. They derive an integer optimization formulation for selecting the budgets for a periodic flow-controlled policy. For unknown output length of request, they propose an easy-to-implement periodic flow-controlled scheduling algorithm with LIFO eviction. The numerical simulation results show the effectiveness of the method.

Critical strengths

1.The target question for optimizing LLM serving engines is good. 2.The theoretical results are elegant and offer novel structural insights. 3.The scheduling policy is simple, interpretable, and straightforward to implement.

Critical weaknesses

1.The theory is solid, but how can this theory be translated into practical scheduling benefits under specific workloads? 2.Except for evaluation section, there is no picture.

Questions for authors

1.How can your theory direct me in real system deployment? Could you present some experiments of real vllm (not simulation by Vidur)? 2.Why only short query (input/output length < 500)? Long querys need more KV cache which seems to be more useful to demonstrate effectiveness of your method.

1 comment

Thank you for reviewing our paper and for the helpful comments.

1. Deployment and real GPU experiments

Thank you very much for the positive assessment of the theory. To test the performance of our algorithm in practice, we evaluated our policy on Mistral-7B-Instruct-v0.3 using an RTX 4090 and 4 GiB of KV cache and compared it against vLLM and Sarathi-Serve. We selected the budgets and tested each configuration three times on ten request flows. Each request flow consists of a sequence of different requests. The arrival rate was set to be 48 requests/s. Results are as follows:

MethodAverage latency (s)95% latency (s)Request throughput (requests/s)
vLLM22.8343.7919.20
Sarathi-Serve20.7140.0619.92
Ours, [0,0,0,4][0,0,0,4]19.1337.9721.07
Ours, [0,0,0,5][0,0,0,5]18.7940.5820.99
Ours, [0,0,0,6][0,0,0,6]19.0342.2320.71

Across the three budgets, our method reduces average latency by 16.2%–17.7% compared with vLLM and 7.7%–9.3% compared with Sarathi-Serve. To check repeatability, we ran 15 repetitions on two request flows. Across these two flows, the mean latency remained 14.4%-17.1% lower than vLLM and 8.9%-10.3% lower than Sarathi.

2. Figures

Thank you for highlighting the question on pictures. We will add more illustrations to the main text to make the algorithm and theoretical results easier to follow. We will also add a figure of the real GPU results.

3. Longer requests

Thank you for pointing out this question. Following your suggestions, we considered all requests such that the input and output length at most 4,096 tokens and set the arrival rate as 10 requests/s over a time period of T=1000T=1000 seconds. Because the average workload increased, we set the budget b=0.6b=0.6 (i.e., at each slot, we admit one request with probability 0.6 and no request otherwise). We report the mean and 95% latency:

PolicyMean latency (s)95% latency (s)Requests/s
Ours, b=0.6b=0.61,017.52,284.63.138
vLLM1,247.42,362.92.879
Sarathi1,081.62,052.73.174

Our mean latency is 18.4% and 5.9% lower than vLLM and Sarathi, respectively. However, Sarathi achieves lower 95% latency. The results suggest that our advantages over the benchmarks may not become more pronounced. This is because longer requests make evictions more expensive. Since our policy restarts evicted requests without storing the prefill and decoded tokens, these costs may offset the effectiveness of our method. By contrast, Sarathi uses chunked prefill to reduce interference with ongoing decoding, which can make it less sensitive to longer prompts.

Reviewer_2b8nOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper controls when requests enter the active set of an LLM server through periodic activation budgets. Under its KV-memory model and known output lengths, it proves that such budgets can stabilize every load in the interior of the stability region achievable by general causal policies. It also provides methods for selecting the budgets. For unknown lengths, the paper studies LIFO eviction with a finite-horizon overflow bound and a separate conservative reservation policy with a stability guarantee. Synthetic and Vidur simulations report improvements in average latency and throughput.

Critical strengths
  1. Theorem 3.3 is the strongest part of the paper. A simple periodic policy can cover the interior of the stability region of general causal policies under the stated model. The argument that a successful execution can be rearranged into continuous decoding without increasing memory use is particularly interesting.

  2. Section 4 gives concrete ways to choose the budgets, including an integer program and a simpler evenly spaced schedule. This makes the main result more useful. The experiments also report both average and tail latency and acknowledge that Sarathi-Serve has better P95 latency in the trace-driven comparison.

Critical weaknesses
  1. For unknown lengths, the guarantee depends on how the budgets are chosen. Appendix E proves stability with worst-case length reservations, but Theorem 5.1 only bounds the first overflow over a fixed horizon for the less conservative policy. It does not establish stability after repeated evictions and restarts. The practical trade-off between these two choices is not clear from the experiments.

  2. The theoretical model assumes zero prefill time and one decoded token per active request per slot. Section 6.2 partly addresses this with Vidur, which uses operator profiling and predictive timing models. Still, the proposed scheduler is not tested in a real serving engine. A deployment check would be useful, particularly against Sarathi-Serve, whose design explicitly accounts for prefill/decode interference.

Questions for authors
  1. Does the constant budget b=1b=1 in Section 6.2 satisfy the worst-case reservation condition, the finite-horizon risk constraint, or neither? What eviction frequency and recomputation cost were observed?

  2. How are prefill and the recomputation of evicted requests charged in the Vidur experiment? Are any measurements from a real inference engine available to check the simulated gains?

2 comments

Thank you for the careful review and the thoughtful comments.

1. Performance and guarantees with unknown output lengths

The budget b=1b=1 was selected through grid search. It does not satisfy the worst-case reservation condition and the finite-horizon risk constraint. To assess the cost of conservative budget choices, we compared different budgets in the synthetic setting. We compared a benchmark with guarantee on the overflow event. For a time horizon of 1000 slots, we selected the budget b=10b=10, with an upper bound of 1.64×10−51.64\times10^{-5} on the probability of the first overflow event. We also compared with a benchmark with worst-case guarantees, with b=6b=6. All requests were drained before calculating performance. We ran the experiments on three random seeds and report the results, as follows.

BudgetAverage latency (slots)95% latency (slots)Eviction countDiscarded output tokens
b=6b=6550.951,005.0000
b=10b=10147.63244.0000
b=12b=1263.5097.33418.7145.7

Here, eviction count records the number of eviction events, and discarded output tokens are tokens already generated and then lost on eviction. We find that, although smaller budgets achieve no evictions, the latency is longer. Budget 12 achieves lower average and 95% latency while discarding 0.030% of the useful output tokens. We will investigate the stability under repeated evictions in future work.

In the original Vidur experiment at T=1000T=1000 seconds, eviction events occurred at 1.98 and 1.99 events/s for arrival rates 10 and 50 requests/s, respectively. In the experiments with 10 requests/s arrival rate, restarts required 2.67% extra decode tokens and 58.2% extra prefill tokens.

2. Simulation settings and real serving systems

In our Vidur simulation, existing active requests generate one token per iteration, while newly activated requests complete prefill and generate their first token. Vidur estimates each iteration’s duration from its batch composition. Evicted requests return to the waiting queue and restart from their original prompts, repeating both prefill and decoding.

Regarding your comments on the real serving engine, we evaluated our policy on Mistral-7B-Instruct-v0.3 using an RTX 4090 and 4 GiB of KV cache and compared it against vLLM and Sarathi-Serve. We selected the budgets and tested each configuration three times on ten request flows. Each request flow consists of a sequence of different requests. The arrival rate was set to be 48 requests/s. The results are shown as follows.

MethodAverage latency (s)95% latency (s)Request throughput (requests/s)
vLLM22.8343.7919.20
Sarathi-Serve20.7140.0619.92
Ours, [0,0,0,4][0,0,0,4]19.1337.9721.07
Ours, [0,0,0,5][0,0,0,5]18.7940.5820.99
Ours, [0,0,0,6][0,0,0,6]19.0342.2320.71

Across the three budgets, our method reduces average latency by 16.2%–17.7% compared with vLLM and 7.7%–9.3% compared with Sarathi-Serve. The tail latency is also competitive. To check repeatability, we increased the repetitions to 15 times on two request flows. Across these two flows and the three budgets, mean latency remained 14.4%-17.1% lower than vLLM and 8.9%-10.3% lower than Sarathi, which implies that the performance of our algorithm is competitive in real serving systems.

Thsnk you for clarifying with additional results. The rebuttal addressed my empirical concerns, but the gap between the theoretical guarantees and the practically tuned policy remains. Thus, I will keep my weak accept rating

Reviewer_6RGpOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies admission control for LLM inference under a hard KV-memory constraint. For known output lengths, it characterizes the stability-region closure through periodic activation budgets. For unknown lengths, it derives a finite-horizon first-overflow bound and calibrated budget constraints, complemented by synthetic and Vidur-based simulations.

Critical strengths

The main theoretical contribution is substantive: the reduction from general schedules with pauses or restarts to continuous-decoding, empty-to-empty blocks explains why periodic admission can approximate achievable rates. The strict-slack construction then yields a policy that works across arrival laws satisfying the stated assumptions. The budget formulation and evenly spaced construction make the characterization more actionable. The evaluation also reports a real tradeoff: improved average latency and throughput alongside worse tail latency than Sarathi in the reported settings. The periodic-policy characterization offers sufficient theoretical value despite limited guarantees for the practical unknown-length setting. The simulation-accounting questions should be clarified.

Critical weaknesses

The practical scope of the guarantees remains narrower than the serving motivation. The stability characterization assumes known lengths and zero-time prefill. For unknown lengths, Theorem 5.1 bounds the first overflow over a fixed horizon; Proposition F.3 establishes nominal-system stability and agreement before overflow, rather than unrestricted stability of the actual eviction/restart process. This is a limitation of applicability, not a demonstrated error in the stated results.

The simulation protocol needs a clearer connection to those guarantees. Section 6.2 uses a constant budget of one request per variable-duration iteration without specifying a corresponding risk certificate. Appendix G reports mean latency of 3,835 seconds at T = 1,000 seconds, making the distinction between arrival horizon, draining, and observation horizon essential to interpreting both latency and throughput.

Questions for authors
  1. Clarification: Was the serving-simulation budget risk-certified or selected heuristically, and how do variable-duration iterations correspond to theoretical slots? This would establish which guarantees apply to the reported serving experiment.
  2. Clarification: At the reported horizons, are arrivals stopped and queues drained, how are unfinished or restarted requests included in latency, and what interval defines throughput? This would resolve the interpretation of the 3,835-second mean latency at T = 1,000 seconds.
1 comment

We thank you for the careful review and for the insightful feedback.

1. Practical scope of the guarantees

We appreciate your recognition of our main theoretical contribution that periodic admission can approximate achievable rates for known output lengths. For unknown output lengths, we establish stability under a conservative choice of budgets. We also bound the probability of the first overflow over a finite horizon. Stability under repeated evictions is an important direction for future work. The practical value of our approach is demonstrated by our synthetic experiments and Vidur simulations, which show lower average latency than the benchmarks when output lengths are unknown.

2. Budget selection and slots

In our experiments, we selected b=1b=1 through grid search. This budget is not certified by the worst-case reservation and finite-horizon risk conditions. In the Vidur simulation, one slot corresponds to one iteration of the batch: for each existing active request, it generates one output token; for newly activated requests, it completes the prefill stage and generates the first output token. Vidur is then able to estimate each iteration's duration from its batch composition. The budget applies to each iteration, despite the fact that the duration might be different. Moreover, the request arrivals and performance metrics are measured in seconds.

3. Arrival horizon and performance metrics

In our numerical experiments, we assume that requests arrive during the time horizon [0,T][0,T], after which the simulation continues until every request finishes. Each request's latency runs is the lap between its first arrival to its final completion time. Regarding the definitions of throughputs, we consider two different types: request throughput and workload throughput. Let NN be the number of requests arrived (their input and output lengths are lil_i and oio_i, respectively) and DD the time of the last completion. Then the two throughputs are defined as follows:

\text{Workload throughput}=\frac{\sum_{i=1}^N[l_i o_i+o_i(o_i+1)/2]}{D}.$$ In the experiment, the arrival rates we considered exceed the server's capacity, so substantial waiting continues beyond the arrival window. This explains the mean latency of 3835 seconds at $T=1000$ seconds.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.