acceptodds
Under review as a conference paper at ICLR 2027

Steady-State Queue-Length Tail Analysis of LLM Serving Systems

Abstract

The growing adoption of large language model (LLM) inference places increasing pressure on service providers. Although some serving systems can use coarse estimates to prevent unbounded request queue growth caused by overload, the lack of accurate estimates of LLM serving capacity may result in persistently long queues even in steady state, substantially degrading inference service quality. To address this issue, we combine batching mechanisms specific to LLM inference with classical queueing analysis and develop a framework for predicting arbitrary-time steady-state queue-length tail probabilities under different batching strategies. The framework accounts for random request lengths and service times associated with different batching strategies to estimate the probability that the number of requests awaiting service exceeds a specified threshold. It also enables comparisons across arrival rates, batch sizes, and service configurations. Validation experiments on a real server show that, as the system approaches full utilization, the proposed mathematical model accurately estimates queue-length tail probabilities across different arrival rates.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM inference, LLM serving optimization, queueing theory, queue-length tail analysis

Reviews

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

This paper proposes a framework for predicting the tail probability of steady-state queue lengths under different batching strategies. The framework takes into account the randomness of request sizes and service times and supports the comparison of performance under different arrival rates, batch sizes, and service configurations. Experiments on real servers show that, under near-full load conditions, the model can accurately estimate the tail probability of queue lengths at various arrival rates.

Critical strengths
  1. From modeling reasoning time and deriving from queuing probability theory to long-term experiments on real servers, the accuracy and effectiveness of the model are verified layer by layer.

  2. Focus on testing high-load scenarios that approach the system capacity limit, making the validation of the model's accuracy more convincing.

Critical weaknesses
  1. This paper studies fixed batching and dynamic elastic batching, but does not cover the more complex continuous batching behavior in modern serving systems.

  2. This paper's system model is a single LLM inference node. Actual deployments typically have multiple GPUs. How can it be extended to multiple GPUs?

Questions for authors
  1. This paper's linear service time model diminishes the impact of input length and prefill length. Therefore, in scenarios with long contexts or high prefill overhead, such as RAG, can this model still accurately predict service time?
2 comments
AuthorsOpenReview ↗

Response on Multi-GPU Settings and Long-Context Applicability

We thank the reviewer for recognizing our validation approach, from modeling to measurements, and our focus on high-load scenarios. We respond below to the questions about extending the model to multi-GPU settings and its applicability to long contexts.

  1. Multi-GPU Settings

We have added multi-GPU validation in Section 5.2.2, “Reliability under GPU Scaling,” on pages 9–10 of the manuscript. Using vLLM, we deploy the same LLM with two-way and four-way tensor parallelism and compare empirical and theoretical results under fixed and dynamic elastic batching at a load of ρ = 0.90.

The experimental results show that our theoretical tail probabilities remain very close to the empirical tail probabilities. This further demonstrates that our mathematical formulas can accommodate the additional communication and synchronization overhead in multi-GPU environments without introducing extra parameters: only the existing parameters of the service-time model H need to be refitted, followed by recomputation of the arrival rate and stationary distribution.

  1. Long Inputs and Prefill-Intensive RAG

We agree that the effect of input length cannot generally be ignored. For long-context or prefill-dominated RAG workloads, our mathematical model may need an additional input-token-length parameter to estimate the non-negligible additional time incurred during prefill.

In this paper, we restrict input lengths to 10–200 tokens and omit the prefill-stage timing parameter because our primary focus is short question-answering scenarios. We believe that users in long question-answering scenarios are less sensitive to waiting time and can tolerate some queueing delay, whereas users in short question-answering scenarios expect rapid responses and do not want service to be affected by excessive queueing. Since inputs in short question-answering scenarios are not excessively long, we omit the contribution of the input token count to prefill processing time.

Thanks for your timely and detailed response. It partially solves my concerns. I am still concerned about continuous batching in modern serving systems.I keep my score. Thank you for your time and effort.

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

This paper estimates the probability that an LLM serving queue exceeds a given length in steady state. It combines existing batch-runtime models with a Markov chain at batch completions, then derives the queue distribution at an arbitrary time. The analysis covers fixed and dynamic elastic batching under Poisson arrivals and uniformly distributed output lengths. Experiments with Qwen3.5-9B-INT4 on an RTX 4090 show fairly close agreement with measured distributions at 90--97% utilization, with larger discrepancies for rare queue-length exceedances.

Critical strengths
  1. The paper asks a useful question: even when a system is stable, how often does its waiting queue become too long? Estimating this probability could help with capacity planning. Section 4 also makes the distinction between observations at batch completions and observations at an arbitrary time clear.

  2. I appreciate the long measurement periods in Section 5: 24-72 hours after warm-up, including runs close to saturation. Figures 1 and 2 provide a useful check that the predictions agree with server measurements under the assumed workload.

Critical weaknesses
  1. My main concern is how much the validation tells us beyond the assumed model. Section 5 uses Poisson arrivals and independent uniform lengths, just as the analysis does, on one model and GPU. There is no test of bursty arrivals or a different length distribution. This leaves the usefulness of the estimates outside this controlled setting unclear.

  2. The batching model also limits the scope. In Section 4.3, completed requests can leave early, but the next batch forms only after the current batch finishes. It is unclear how the analysis extends to admitting new requests during decoding. Since the motivation concerns contemporary serving systems, this restriction needs a clearer discussion, including how it was enforced in the vLLM experiment.

Questions for authors
  1. Which parts of the derivation require uniform output lengths, and which would still hold with an empirical length distribution? Are any existing results available outside the Poisson/uniform setting?

  2. In the vLLM experiment, were new requests prevented from joining until the current batch finished? Please clarify how the implementation matches the batch-completion model in Section 4.3.

4 comments
AuthorsOpenReview ↗

Response on Distributional Applicability and Experimental Scheduling Consistency

We thank the reviewer for recognizing the value of predicting request backlogs, distinguishing between observation epochs, and conducting long-duration measurements. We respond below to the questions about distributional applicability and consistency between the experimental scheduling and theoretical model.

  1. Dependence on the Length Distribution Assumption

Equations (3) and (12) directly depend on the uniform length assumption. They compute the probability distribution of the maximum length within a batch and the joint distribution of the total and maximum lengths, respectively. If an empirical length distribution is used while request lengths remain independent and identically distributed, these probabilities can be recomputed from observed frequencies. The computational approach in Equations (4) and (14) and the structure of the final tail-probability expressions in Equations (11) and (17) remain applicable, although the probabilities must be solved for again.

Our use of Poisson arrivals and independent, uniformly distributed lengths follows similar settings in recent studies. “QoServe: Breaking the Silos of LLM Inference Serving,” published at ASPLOS 2026, uses Poisson arrivals to model request arrivals. “A Queueing-Theoretic Framework for Stability Analysis of LLM Inference with KV Cache Memory Constraints,” published at ICML 2026, uses uniformly sampled input and output lengths in controlled experiments. We acknowledge that the paper does not include experiments with bursty arrivals or alternative length distributions beyond the Poisson-arrival and uniform-length assumptions.

  1. Alignment Between the vLLM Implementation and the Theoretical Model

In our vLLM experiments, we introduce an external request queue and use an external queue controller to prevent new requests from joining before the current batch finishes. For elastic batching, for example, the external controller submits up to B waiting requests to vLLM only after the entire current logical batch has completed; no new waiting requests are submitted during its execution. This external gating mechanism ensures that the experiments match the batch-completion-based model in Section 4.3.

Thanks for your clarafication, I think the external queue controller part resolves my questions about how the vLLM exp matches the batch-level model. Now I also understand that uniform output length are not essential to the framework, provided lengths remain iid. The additional multi-GPU exp are useful.

My main concerns are the lack of validation with non-uniform output lengths and the fact that continuous batching remains out of the analysis. Are any results using non-uniform or empirical output-length distribution avialable? For now I'll keep my scoring.

Thank you for clarifying your remaining concerns. In response to your question about nonuniform or empirical output-length distributions, we have added two experiments to the revised manuscript. The new Section 5.2.3, “Reliability under Nonuniform Output Lengths,” and Figure 4 present the results. Both experiments were conducted on a single GPU at a load of rho=0.90.

For fixed batching, we selected 41,089 ChatGPT responses from BurstGPT with output lengths between 10 and 200 tokens. We constructed an empirical output-length distribution from the relative frequency of each length and sampled from it independently with replacement. For dynamic elastic batching, we used a discrete truncated Pareto distribution with shape parameter 1.5 to model long-tailed output lengths over the same token range. In both experiments, we retained the original formulas, recalibrated only the service-time model, and recomputed the theoretical queue-length tail probabilities. We then compared the predictions with six hours of measurements.

For ease of reference, the table below lists the metrics corresponding to Figure 4.

Figure 4 metric                 (a) Fixed       (b) Dynamic elastic
------------------------------  --------------  -------------------
Output-length distribution      Empirical       Heavy-tailed
Total variation distance        0.0217          0.0530
Max. absolute tail error        0.0115          0.0528
Mean absolute tail error        0.0026          0.0130
Mean error for tails >= 1%      0.0060          0.0355
Predicted mean queue length     6.11            16.26
Measured mean queue length      6.08            19.33

For fixed batching under the empirical distribution, the predicted and measured tail probabilities agreed closely, with a mean absolute error of 0.26 percentage points. For dynamic elastic batching under the heavy-tailed distribution, the predictions also differed only slightly from the measurements, with a mean absolute error of 1.30 percentage points.

Dear Reviewers,

As the discussion deadline approaches, we would appreciate your feedback on our rebuttal and revised manuscript, including the additional experiments and clarifications addressing your comments.

If our responses and new evidence have resolved your concerns, we would be grateful if you could consider updating your assessment and score accordingly. If any concerns remain, please let us know so that we can address them while the discussion is still open.

Thank you for your time and consideration.

Best regards, The Authors

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

This paper addresses the lack of accurate queue backlog prediction for LLM serving systems, which can lead to persistently long queues even in steady state and degrade service quality. The authors combine LLM-specific batched inference time models with classical queueing theory to develop an analytical framework for computing steady-state queue-length tail probabilities at arbitrary time points under two representative batching strategies. The model is validated on a real server and the experimental results show that the model accurately estimates tail probabilities in high-probability regions across different load levels, with only modest calibration overhead.

Critical strengths
  • Rigorous and generalizable theoretical framework. The paper properly adapts classical embedded Markov chain and regenerative process analysis to the unique characteristics of LLM batching. It derives tractable tail probability expressions for two representative batching paradigms, providing a quantitative foundation for assessing queue backlog risk that was missing in prior LLM serving research. The methodology is extensible and can serve as a baseline for further queueing analysis of LLM systems.
  • Practically relevant empirical validation. The authors validate the model on real GPU hardware with a realistic model deployment, and evaluate not only prediction accuracy but also calibration overhead. According to the paper, only tens of seconds of profiling are sufficient to achieve high-accuracy tail prediction, which is particularly valuable for engineering practice, as it means the framework can be adopted in production with very low deployment cost.
Critical weaknesses
  • Limited workload assumptions. The model assumes homogeneous Poisson arrivals and uniformly distributed output lengths, which differ significantly from real-world LLM traffic patterns—production workloads typically exhibit bursty, non-stationary arrivals and heavy-tailed output lengths. The paper does not evaluate the model’s robustness to these distribution mismatches, which may limit its direct applicability in industrial settings.
  • Narrow system scenario coverage. The work only studies a single-node, single-queue FCFS system, and does not account for common features of production LLM serving such as distributed inference, multi-priority scheduling, KV cache prefix sharing, or request preemption. This restricts the direct applicability of the results to more complex, real-world serving architectures.
Questions for authors
  • The dynamic elastic batching model in the paper adopts batch-level scheduling: no new requests are admitted during batch execution, and only completed requests leave the batch. In contrast, vLLM implements iteration-level continuous batching, where new requests can be inserted at each decoding step. Have the authors considered extending the model to continuous batching? What are the main mathematical barriers to such an extension?

  • The paper assumes uniformly distributed output lengths. How would the model and its accuracy change if output lengths follow a heavy-tailed distribution, which is more typical of real LLM workloads? Does the overall derivation framework remain applicable?

  • Experiments are conducted on a single GPU with a 9B-parameter model. Do the authors plan to validate the model on larger distributed serving setups? Would the framework require significant modifications to apply to multi-GPU or multi-node inference systems?

1 comment
AuthorsOpenReview ↗

Response on the Scope of Model Applicability

We thank the reviewer for recognizing the value of our theoretical framework and validation on real hardware. The questions about continuous batching, workload assumptions, and multi-GPU extensions concern the scope of our results. We respond to each below.

  1. Continuous Batching

We have considered extending batch-level scheduling to iteration-level continuous batching, but this extension presents the following main mathematical challenges.

First, the waiting queue length is no longer a sufficient Markov state. Even when the waiting queue length and the number of active requests are identical, different amounts of remaining work can lead to different completion and admission probabilities. The state must therefore also describe request progress, substantially increasing the dimensionality of the state space.

Second, the current derivation of occupation times over cycles relies on closed batch boundaries, with no new requests admitted during batch execution. Under continuous batching, new requests enter service before existing requests finish. The sojourn-time and occupation-probability analysis must therefore be reformulated to obtain queue-length probabilities at arbitrary times.

An expanded state representation is a possible research direction. However, this extension requires new mathematical modeling and derivations. Developing a computationally tractable model for continuous batching and validating its assumptions therefore remains a separate problem that is not resolved in this paper.

  1. Workload Assumptions

Our use of Poisson arrivals and independent, uniformly distributed lengths follows similar settings in recent studies. “QoServe: Breaking the Silos of LLM Inference Serving,” published at ASPLOS 2026, uses Poisson arrivals to model request arrivals. “A Queueing-Theoretic Framework for Stability Analysis of LLM Inference with KV Cache Memory Constraints,” published at ICML 2026, uses uniformly sampled input and output lengths in controlled experiments.

If output lengths instead follow a heavy-tailed distribution, our overall derivation framework remains applicable, but the batch service-time distribution and queue-length probabilities must be recomputed using the new length distribution.

  1. Multi-GPU and Multi-Node Settings

We have added multi-GPU validation in Section 5.2.2, “Reliability under GPU Scaling,” on pages 9–10 of the manuscript. Using vLLM, we deploy the same LLM with two-way and four-way tensor parallelism and compare empirical and theoretical results under fixed and dynamic elastic batching at a load of ρ = 0.90.

The experimental results show that our theoretical tail probabilities remain very close to the empirical tail probabilities. This further demonstrates that our mathematical formulas can accommodate the additional communication and synchronization overhead in multi-GPU environments without introducing extra parameters: only the existing parameters of the service-time model H need to be refitted, followed by recomputation of the arrival rate and stationary distribution.

We regret that limitations in our experimental hardware prevent us from validating the model in a multi-node environment consisting of multiple servers.

Comments on the paper

1 comment

We thank all reviewers for their feedback. We have added two experimental subsections to the revised manuscript to address two questions the reviewers raised about the scope of our validation: Do the theoretical predictions remain accurate when multiple GPUs jointly process a batch? Does the analysis remain applicable when request output lengths are not uniformly distributed?

Summary Outline

Core contribution. Given a queue-length threshold x, our framework estimates the probability that more than x requests are waiting for service at an arbitrary time in steady state. Rather than characterizing the system solely by its average throughput or stability condition, the framework links batch inference time to the risk of request backlog under both fixed and dynamic elastic batching.

Original submission. The original manuscript derived queue-length tail probability formulas for both batching strategies and validated them on a single GPU using independent, uniformly distributed output lengths. It also measured the overhead of calibrating the service-time model.

Revisions in response to the reviews. The new Section 5.2.2 and Figure 3 extend the experiments to tensor-parallel deployments on two and four GPUs. The new Section 5.2.3 and Figure 4 evaluate prediction accuracy under nonuniform output lengths using empirical and truncated Pareto distributions.

We have added the following subsections to the manuscript:

Section 5.2.2 — Reliability under GPU Scaling (Figure 3). We deployed the same model on two and four RTX 4090 GPUs using tensor parallelism and tested both batching strategies at a load of rho=0.90. We accounted for multi-GPU execution overhead solely by recalibrating the service-time model, without introducing separate parameters for inter-GPU communication or synchronization. Across all four configurations, the predicted and measured queue-length tail probabilities were generally close.

Section 5.2.3 — Reliability under Nonuniform Output Lengths (Figure 4). We conducted the experiments on a single GPU at a load of rho=0.90. For fixed batching, we selected 41,089 BurstGPT responses with output lengths between 10 and 200 tokens and independently resampled their lengths to construct an empirical distribution. For dynamic elastic batching, we used a discrete truncated Pareto distribution to model heavy-tailed output lengths over the same range. We recalibrated the service-time model and compared the theoretical predictions with the measurements. The mean absolute errors in the predicted queue-length tail probabilities were 0.26 percentage points for fixed batching and 1.30 percentage points for dynamic elastic batching. Figure 4 also shows close agreement between the theoretical predictions and the measurements.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.