acceptodds
Under review as a conference paper at ICLR 2027

A Queueing-Theoretic Framework for Prefill-Decode Disaggregated LLM Inference

Abstract

The rapid growth of large language models (LLMs) has made efficient large-scale inference a critical systems challenge. However, existing LLM serving research has primarily focused on engineering optimization, while queueing-theoretic guidance for resource provisioning under prefill–decode (P–D) disaggregation remains limited. In this paper, we develop a tandem-queue framework for P–D disaggregated inference. In particular, the interplay of autoregressive generation, evolving KV-cache requirements, continuous batching, and associated constraints in Decode gives rise to a distinctive dynamic multi-server queue in LLM inference.We formulate an exact, high-dimensional Markov representation of the proposed queueing model and further develop tractable analytical methods for its stationary population distributions.For the Prefill queue, we employ structured Markov analysis and transform-domain methods; for the Decode queue, we use saddlepoint approximation, large-deviation theory, and Halfin–Whitt quality-and-efficiency-driven (QED) analysis to classify and characterize regimes dominated by different resource bottlenecks. We find that both the onset of queueing and the transition to resource redundancy exhibit sharp changes, and that when multiple resources simultaneously become bottlenecks, necessary resource slack and the resulting underutilization are critical to system stability.These findings provide analytical tools for system deployment, enabling operators and schedulers to coordinate resource allocation across Prefill and Decode and to provision concurrency and KV-cache capacity jointly. Such guidance helps avoid underutilizing bottleneck resources or overprovisioning nonbinding resources. Extensive simulations validate the theoretical predictions.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
Queueing Theory, LLM Inference,KV Cache,Resource allocation

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_5TgvOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies PD-disaggregation LLM serving from queueing theory perspective. It can be seen as some extension to the Nie et al (ICML 2026), trying to extend from PD mixing LLM serving to PD-disaggregated LLM serving. It models this serving process as a tandem queue, where prefill is the first stage and decode is the second stage. The prefill is modeled as linear, and the decode is described carefully: the model contains continuous batching, concurrency limit, KV cache size limit, etc. The major contribution of this paper is to provide theoretical guarantees on given some P,D servers, what is the waiting time, resource redundancy, etc. Finally, the authors run a numerical simulation to verify the theory.

Critical strengths

I like the decode-step modeling. It differentiates the concurrency limit and the KV size limit. It also contains the linear increasing KV usage pattern. Therefore, I think the model is really trying to provide some insights specific on LLM serving, not something can be replaced by general cloud computing.

Critical weaknesses

However, there are two big weaknesses from my mind:

  1. the model and theoretical insights still have huge gap to real LLM serving. I have two comments on the model: (i) the author models the prefill process as linear to the prompt length. However, based on my understanding and my engineering experience, the prefill process is usually quadratic due to attention computation. (ii) the authors completely ignore the communication cost between prefill and decode, which is a big cost from my own experience. Then, on theory, I think there are many rigorous theorems, but I wonder what are the insights behind the theory. For example, I read the cited Nie. et al ICML 2026 paper, I think the authors try to extends Nie et al's PD mixing to PD disaggregation. However, in Nie. et al 2026, they provide exact theorems on stable condition and service rate, then engineers can compute service rate according to the math formula, and decide the provisioning plan (how many GPUs are required for a given workload distribution). In this paper, although there are many theorems, from my own understanding on math, I cannot get the most important decision: what is the P/D ratio on provisioning. The theorems on how congested the prefill/decode given a provisioning plan is not that insightful since one can easily observe from the realization.

  2. the numerical experiments do not have any hardware configuration, and therefore, I guess it is some model-based simulation. If yes, I think this completely cannot provide any insight. If the authors do not have GPU resources access, at least they should use Vidur simulator (which can run on your own CPU). A model-based simulation just verifies the theory on your specific model, but what if the model has huge gap with real? (I believe there are huge gaps between the model and real) Therefore, I strongly encourage the authors to run some experiments on either real GPUs or Vidur, and then, the theory can show its value. Specifically, for provisioning and queueing, once the formula can be verified on real GPU provisioning (e.g. Nie et al 2026 used 8*A100 to verify their theory), formulas can bring strong value and impact.

Questions for authors
  1. What is the experiment's setting? It is model-based, or Vidur simulator, or real experiments?
  2. Given on all of these theorems, for practitioners, if I care about how much P&D instances are needed given a workload distribution, how to derive this term?
8 comments
AuthorsOpenReview ↗

Response(1/8)

We thank the reviewer for recognizing the direction of our work and for raising these valuable questions. We acknowledge that your concerns have highlighted opportunities to further improve our work. Over the past period, we have carefully revisited and refined the manuscript in response to your comments. We hope that the following clarifications and additional results will address your concerns.We will add the remaining content soon.


1.Part of W1: prefill process Modeling

We agree with your observation that "due to the computation involved in the attention mechanism, the prefill process typically involves quadratic computational complexity." We would like to clarify two points:

  1. Our analytical method for the prefill stage employs transform-domain analysis of a structured Markov model and does not rely on the assumption of linear service time. It is generally applicable to arbitrary known service-time distributions.

  2. In this paper, we model the prefill service time as a linear function of the input length, which is supported by both theoretical analysis and empirical evidence under certain configurations.

SARA [1] derives the computational complexity of the prefill stage for Transformers employing GQA as follows:

\left[ L^2+ \left(2(1+g)N_{\mathrm{mod}} +2N_{\mathrm{hid}}+1\right)L \right],$$ where $L$ denotes the input length, $N_{\mathrm{mod}}$ is the hidden dimension, $N_{\mathrm{hid}}$ is the FFN intermediate dimension, and $N_{\mathrm{layer}}$ is the number of Transformer layers. Here, $g=N_{\mathrm{KV}}/N_{\mathrm{head}}$. When the model dimensions are sufficiently large relative to the input length, the linear terms dominate the overall computational cost, and the contribution of the quadratic attention term is relatively limited. For example, SARA reports that, under the NVIDIA A100 and LLaMA 3.1 8B configuration ($N_{\mathrm{layer}}=32$, $N_{\mathrm{mod}}=4096$, $N_{\mathrm{hid}}=14336$, and $g=0.25$), the quadratic term accounts for only approximately 2.56% of the total computation when $L=1024$: $$\frac{N_{\mathrm{layer}}N_{\mathrm{mod}}L^2} {N_{\mathrm{mul}}(L)} \approx 2.56\\%.$$ Preble [2] conducts GPU profiling of Mistral-7B on an NVIDIA A6000 and explicitly observes that linear layers dominate prefill latency, with the overall prefill time increasing approximately linearly with prompt length. Experiments in Sarathi-Serve [3] on NVIDIA A100 further demonstrate that, within the evaluated range where linear operators dominate, they contribute more than 80% of the prefill execution time, even when accounting for the quadratic complexity of attention. Moreover, once the system enters the compute-bound regime, the execution time grows approximately linearly with the number of tokens. In addition, following your suggestion, we conducted further experiments using the Vidur simulator. Specifically, under the configuration of 4 $\times$ NVIDIA A100 (TP=4) and LLaMA-3-8B, we fitted the prefill service times across different input lengths using a linear model (Figure K.1 in revised Appendix K.1). We have added a statement regarding this modeling in the revised version (Appendix K.1). [1] Shicong Liu, Xianghao Yu, Zhen Gao, and Jun Zhang. SARA: SLO-Aware Resource Allocation for Disaggregated Agentic LLM Services. arXiv preprint arXiv:2609.26763, 2026. [2] Vikranth Srivatsa, Zijian He, Reyna Abhyankar, Dongming Li, and Yiying Zhang. Preble: Efficient Distributed Prompt Scheduling for LLM Serving. In International Conference on Learning Representations (ICLR), 2025. [3] Amey Agrawal, Nitin Kedia, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav Gulavani, Alexey Tumanov, and Ramachandran Ramjee. Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI), pp. 117–134, 2024.
AuthorsOpenReview ↗

Response(2/8)

2.Part of W1: the communication cost between prefill and decode

Thank you for highlighting the impact of the communication cost between prefill and decode omitted from our original model. We first (a) clarify the rationale for this modeling choice and then (b) extend the analysis following your suggestion. We hope that these clarifications and additional results will strengthen your confidence in our work.

(a) Rationale for the original model. As stated in Section 3, the original model targets high-bandwidth deployments in which communication is not a primary bottleneck. This abstraction is supported by prior systems work. DistServe [1] explicitly treats cross-node KV-cache transfer overhead as negligible in its high-bandwidth placement analysis. Its experiments further show that, for OPT-175B on ShareGPT, KV-cache transfer accounts for less than 0.1% of aggregate request latency. Splitwise [2] similarly reports that its optimized transfer overhead is approximately 0.8% of end-to-end latency in the coding-trace experiment. Accordingly, our original model focuses on high-bandwidth settings to concentrate on the more complex inference mechanisms of the prefill and decode stages.

(b)Explicit modeling of KV-cache transfer. Following your suggestion, we agree that explicitly incorporating a KV-cache transfer queue is important under limited bandwidth. We have therefore added modeling and analysis of the transfer stage, together with experimental validation, as detailed below.

KV-cache transfer. Requests completing prefill enter a nonpreemptive FCFS single-server transfer queue. For a fixed model, KV volume is proportional to prompt length χ\chi. We model transfer time as an affine function with a fixed overhead, rounded to base slots:

\qquad a_{\mathrm T}>0,\quad c_{\mathrm T}\ge0.$$ Here $\delta$ is the base-slot duration, and $S$ denotes the prefill service requirement in slots. The transfer population $K_{\mathrm T}$ includes waiting and in-service requests. With $\lambda=\mathbb E[A_t]/\delta$, we assume $\lambda\delta\mathbb E[S]<1$ and $\lambda\delta\mathbb E[S_{\mathrm T}]<1$ under the paper's infinite-buffer, no-blocking assumptions. **Transfer analysis.** We retain the temporal dependence of prefill departures and the dependence between each request's two service requirements through $\chi$. Immediately after a nonempty external arrival batch, let $x$ be the residual time to its last scheduled prefill completion and $z$ the corresponding transfer-completion lag. Elapsing time $g$ and appending a request with joint physical service times $(p,t)=(\delta S,\delta S_{\mathrm T})$ give $$\mathcal D_g(x,z)=((x-g)^+,(x+z-g)^+-(x-g)^+),$$ $$\mathcal J_{p,t}(x,z)=(x+p,(z-p)^++t).$$ These maps follow directly from FCFS completion-time recursions. Under the paper's i.i.d. external batch-arrival model, composing them and averaging over batch sizes, inter-batch gaps and joint service marks defines a two-dimensional transition kernel $\mathcal P_{\mathrm{PT}}$. We compute the stationary law from $\nu_{\mathrm T}=\nu_{\mathrm T}\mathcal P_{\mathrm{PT}}$. Weighting batches by their request counts and selecting a request uniformly within each chosen batch yields the typical-request Palm law. Let $d_i^{\mathrm P}$ and $d_i^{\mathrm T}$ denote completion times of the tagged request ($i=0$) and its successors. The occupation identity $$C_k=\Pr\{K_{\mathrm T}\ge k\} =\lambda\mathbb E^\star\!\left[ \left(\min\{d_k^{\mathrm P},d_0^{\mathrm T}\} -d_{k-1}^{\mathrm P}\right)^+ \right],\qquad k\ge1,$$ gives the stationary time-sampled population, where $\mathbb E^\star$ is expectation under that Palm law. The PMF follows as $\pi_0^{\mathrm T}=1-C_1$ and $\pi_k^{\mathrm T}=C_k-C_{k+1}$ for $k\ge1$. Numerical evaluation uses the stationary equation and occupation rewards. **Interface to decode.** Let $A_n^{\mathrm D}$ count transfer completions in a fixed analysis slot of duration $\Delta_{\mathrm D}$, which need not coincide with a dynamic decode iteration. Departure-window rewards determine $$q_a^{\mathrm D}=\Pr\{A_n^{\mathrm D}=a\},\qquad G_{\mathrm D}(z)=\sum_{a\ge0}q_a^{\mathrm D}z^a,\qquad \lambda_{\mathrm D}=\lambda\Delta_{\mathrm D}.$$ This marginal replaces the original prefill-departure input law in the decode stage. We have incorporated these additions into Sections 3 and 4.2 and Appendix C of the revised manuscript, including detailed derivations and proofs, and updated the experimental validation in Section 7. [1] Zhong et al. *DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving*. OSDI 2024. [2] Patel et al. *Splitwise: Efficient Generative LLM Inference Using Phase Splitting*. ISCA 2024.
AuthorsOpenReview ↗

Response(3/8)

3.W2&Q1-(1)

Thank you for pointing out the limitations of our numerical experiments. We acknowledge that the experiments in the original manuscript were based on model-driven Monte Carlo simulations, which were intended to verify the correctness and accuracy of our derivations and approximation methods. We also agree that, as you suggested, our formulas could offer significant value and impact if validated through more realistic experiments. Consequently, we have conducted further, more realistic experiments using the Vidur simulator and have refined our model and theory based on these results to better reflect real-world conditions.


(1) Dynamic batch processing time. In the original version, following Nie et al., we approximated the duration of each batch iteration as a constant. Nie et al. primarily study system stability and service capacity. Our paper further investigates detailed stationary queue-length distributions and their tail behavior. Particularly under heavy load, the spare service capacity available to drain accumulated requests is small, so even slight deviations in processing time can be amplified through queueing accumulation, leading to substantial errors in distribution predictions. Therefore, a timing approximation that adequately captures long-run service capacity may not be sufficient to ensure accurate queue-length distribution predictions. Our Vidur experiments also indicate that this modeling assumption requires further refinement under the configurations and workloads considered.

Accordingly, we extend the duration of a single decode batch iteration to a linear function of the active batch size NN:

TD(N)=cD+aDN.T_D(N)=c_D+a_DN.

This model is directly supported by existing studies. Zhang et al. [1] explicitly model the duration of a single decode iteration using a linear relationship and provide execution-time measurements for Qwen3-4B on NVIDIA H200 and RTX PRO 6000 GPUs. Yang et al. [2] also observe, through experiments on an NVIDIA A100, that the time required to generate a single token increases approximately linearly with batch size. We additionally use Vidur to validate the suitability of this approximation under our experimental configuration (We have provided detailed justification in Appendix K.2).

Based on this refined modeling assumption, we have extended all analyses of the decode stage in the original paper and validated them experimentally. In model-based simulations, the extended theory largely maintains the predictive accuracy of the original approach, while achieving clear improvements in the Vidur-based experiments. The key ideas are as follows.We retain the original fixed-time-window framework and decomposition into resource-dominated regimes, incorporating the effects of dynamic batch processing times into the service description within each fixed window.Under specific parameter settings, the extended theory naturally reduces to the original constant-duration model.

We have incorporated these theoretical extensions into Sections 5.2 (Memory-Dominated Decode) and 5.3 (Concurrency-Dominated Decode), with detailed derivations and proofs in Appendix D (joint reference distribution and concurrency threshold), Appendix E (memory-dominated full distribution), Appendix F (large-deviation tails for both regimes), and Appendix G (concurrency-dominated QED approximation).

① Large-deviation analysis: update the equivalent work requirements while retaining the original tail-exponent framework. Normalizing the service budget in each fixed window to one, the equivalent per-request work requirements in the memory-dominated and concurrency-dominated regimes become

\qquad S_B=\frac{1}{\Delta_D}\left(\frac{c_D}{c}+a_D\right)\omega.$$ The original large-deviation arguments based on reflected random walks and inverse renewal-counting processes therefore remain applicable; the service-demand distribution changes. Under the stated reference-system and tail-regularity assumptions, the two tail exponents satisfy $$\gamma_M=\log\mathbb E\exp\\!\left[ \frac{\Lambda_D(\gamma_M)}{\Delta_D} \left(\frac{c_DW}{M}+a_D\omega\right) \right],$$ $$\gamma_B=\log\mathbb E\exp\\!\left[ \frac{\Lambda_D(\gamma_B)}{\Delta_D} \left(\frac{c_D}{c}+a_D\right)\omega \right].$$ [1] Zhang et al. Threshold-Based Exclusive Batching for LLM Inference. ICML 2026. [2] Yang et al. A Queueing Theoretic Perspective on Low-Latency LLM Inference with Variable Token Length. WiOpt 2024.
Reviewer_UfcXOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper develops a discrete-time tandem-queue framework for prefill–decode disaggregated LLM inference. Prefill is modeled as a compute-limited single-server queue, and transform-domain analysis yields its stationary population distribution. Decode is modeled as a dynamic multi-server queue with coupled concurrency and KV-cache constraints, where request memory footprints grow during decoding. To make the coupled system tractable, the authors introduce probabilistic resource decoupling: a memory-dominated regime is analyzed via an infinite-server reference, saddlepoint approximation, and large-deviation analysis, while a concurrency-dominated regime is analyzed via Halfin–Whitt/QED theory. The framework provides decode population and tail approximations, concurrency- and memory-redundancy thresholds for provisioning, and a necessary joint-slack result showing that separate resource stability does not guarantee joint stability. Simulations across arrival processes, workloads, and resource configurations support the theoretical predictions, including population distributions, tail decay, and threshold accuracy.

Critical strengths
  1. Resource decoupling for coupled memory/concurrency constraints. The separation into memory-dominated and concurrency-dominated regimes, with thresholds B_θ(M) and M_θ(c), is a consequential modeling contribution because it makes a difficult two-resource queue tractable and yields concrete provisioning guidance.

  2. Distributional and tail analysis beyond mean/stability. The stationary population laws, large-deviation tail characterization, and necessary joint-slack result provide information that mean-load or stability analysis alone cannot capture, especially for latency-sensitive provisioning and joint KV/concurrency dimensioning.

Critical weaknesses
  1. Decode KV-memory accounting is underspecified for waiting requests. The decode feasibility condition only constrains the active batch, but requests that have completed prefill and are waiting for decode admission may also occupy KV memory. This assumption is material because it determines whether the queueing model and the provisioning thresholds correspond to practical P-D serving.

  2. The Table 1 threshold validation is not fully conclusive. Predicted thresholds are consistently lower than the Monte Carlo thresholds, and the paper does not report empirical exceedance probabilities at the predicted thresholds to directly verify the specified θ-tolerance. This matters because it leaves open whether the approximation is systematically optimistic in the reported validation.

Questions for authors
  1. The memory-feasibility condition Rj<=M accounts only for the KV caches of active decode requests. Where are the KV caches of requests that have completed prefill but are waiting for decode stored? Under what assumptions can their memory usage be excluded from this constraint?

  2. Does the framework assume that prefix caching is disabled? If enabled, how would cache hits affect the prefill service time model? If requests share prefix KV blocks on the decode side, would the additive memory model and the resulting provisioning thresholds need to change?

  3. Table 1 reports small relative threshold errors, but all predicted thresholds are lower than the corresponding Monte Carlo reference thresholds. What empirical exceedance probabilities are achieved at these predicted thresholds, and do they satisfy the specified theta tolerances?

5 comments
AuthorsOpenReview ↗

Response(1/3)

We appreciate the reviewers' recognition of the strengths of our article and the valuable questions they raised. We acknowledge that refining these questions significantly improves the quality of our article and inspires our future work. Below, we will address each of your concerns. We will add the remaining content soon.


1.W1&Q1

Thank you for pointing out that the storage location and memory accounting of requests waiting for decode admission were not sufficiently specified in the original manuscript. We agree that this distinction is important for interpreting the memory-feasibility constraint. We clarify that M represents the effective GPU HBM KV-cache budget, rather than the total storage capacity of the decode instance.

Specifically, we consider a host-backed staging architecture. After prefill completion and KV-cache transfer, requests awaiting decode admission retain their KV caches in the CPU host memory of the decode node, which is separate from the GPU HBM pool. Upon admission, their KV caches are loaded into GPU HBM and incorporated into subsequent continuous batches. Accordingly, Rj≤MR_j\le M accounts only for the GPU KV-cache occupied by active decode requests.

This storage organization is supported by existing system designs. Mooncake (Qin et al., FAST 2025) transfers KV caches to the CPU memory of the decode node and subsequently loads them into GPU memory before continuous batching. Furthermore, the SGLang design proposal, explicitly proposes staging transferred KV caches in pinned host memory and deferring GPU KV allocation until requests approach decode execution. These designs motivate our separation of waiting-cache storage from the active decode GPU memory pool.

We assume that the decode-side host-memory staging capacity is sufficiently provisioned and does not introduce a bottleneck. We further assume that local host-to-device KV loading can be sufficiently overlapped with inference execution, such that it does not constitute an independent bottleneck. We have emphasized this point in the revised manuscript (Section 3, System Model)

[1]Ruoyu Qin, Zheming Li, Weiran He, Jialei Cui, Feng Ren, Mingxing Zhang, Yongwei Wu, Weimin Zheng, and Xinran Xu. Mooncake: Trading More Storage for Less Computation—A KVCache-centric Architecture for Serving LLM Chatbot. In Proceedings of the 23rd USENIX Conference on File and Storage Technologies (FAST), pp. 155–170, 2025.

[2] SGLang Contributors. Host-Backed Deferred Device KV Allocation for PD Disaggregation. SGLang GitHub RFC, Issue #27622, June 2026.https://github.com/sgl-project/sglang/issues/27622

AuthorsOpenReview ↗

Response(2/3)

2. W2&Q3

Thank you for pointing out that "the Table 1 threshold validation is not fully conclusive". We apologize that, partly due to space constraints, Table 1 and the accompanying discussion did not clearly convey the motivation and significance of this analysis. We will clarify this presentation.

We introduce resource-redundancy thresholds in order to distinguish regimes in which system performance is predominantly constrained by KV-cache memory or by concurrency. Request-length bounds alone yield conservative sufficient conditions. Let χ\chi and ω\omega denote prompt and output lengths. An active request occupies at most χmax⁡+ωmax⁡−1\chi_{\max}+\omega_{\max}-1 KV units. For a fixed MM, the system is therefore purely concurrency-constrained when

B≤Blo=⌊Mχmax⁡+ωmax⁡−1⌋.B\le B_{\mathrm{lo}}=\left\lfloor\frac{M}{\chi_{\max}+\omega_{\max}-1}\right\rfloor.

Conversely, each request occupies at least χmin⁡\chi_{\min} KV units, so the system is purely memory-constrained when

B≥Bhi=⌊Mχmin⁡⌋.B\ge B_{\mathrm{hi}}=\left\lfloor\frac{M}{\chi_{\min}}\right\rfloor.

We call [Blo,Bhi][B_{\mathrm{lo}},B_{\mathrm{hi}}] the resource-constraint transition interval. For example, this interval is [833,7488][833,7488] under the configuration in Table 1.

As discussed in Section 6, fixing one resource reveals a very sharp transition of the other from a bottleneck to a redundant resource (Figure 3 in revised Section 7.3). That means a much narrower window can probabilistically separate regimes dominated by a single resource. This also highlights the practical relevance of analyzing single-resource-constrained systems, conceptually resembling the notion of a "typical set" in information theory.

The conservative interval is too broad to offer useful practical provisioning guidance. Our goal is therefore to exploit information about arrivals and decode dynamics to substantially tighten it. Specifically, using the relationship between BB and its exceedance probability provided by Theorem 2, we develop Algorithm 1 (revised Appendix I). We select a tail-probability level ϵ\epsilon in advance and use monotone two-sided bisection, starting from the coarse interval boundaries, to locate the sharp transition window.

The additional evaluation uses the prespecified sensitivity level ϵ=10−9\epsilon=10^{-9}, with target window coverage 1−2ϵ1-2\epsilon. We report empirical coverage, its absolute deviation from the target in percentage points (pp), and the width compression relative to the coarse interval:

Arrival typePredicted windowEmpirical coverage (%)Coverage error (pp)Window compression (%)
Deterministic(1678, 1825]98.01021.989897.79
Poisson(1512, 1888]99.94050.059594.35
Discrete uniform(1360, 1926]99.99890.001191.50

Across all three arrival distributions, the width reduction is at least 91.50%. Empirical coverage exceeds 99.9% under Poisson and discrete uniform arrivals and 98% under deterministic arrivals. The observed errors allow practically meaningful conservative windows.

We therefore wish to clarify that our original presentation did not sufficiently explain the intended purpose of this analysis. For our analytical and practical objectives, predicting the sharp transition window and identifying high-probability single-resource-dominated regimes is more informative than distinguishing whether the exceedance probability at a particular BB within that window is 10% or 20%. Our experiments further show a marked improvement in prediction performance as arrival randomness increases, with both stochastic settings achieving over 99.9% coverage. In practice, exactly deterministic arrivals are rare; daily activity patterns and other factors often introduce substantial variability. The deterministic "worst case" is therefore included for theoretical rigor, rather than as a representative practical workload.

We have updated the relevant discussion and experimental results in the revised manuscript (Sections 6 and 7.3, and Appendix I). Thank you for this question, which helps us communicate the motivation and significance of our work more clearly.

AuthorsOpenReview ↗

Response(3/3)

3.Q2

We thank the reviewer for raising this question. Prefix caching is an important optimization in LLM serving because it can save computation during prefill and allow requests to share KV blocks during decode.

First, our current result provides a conservative performance baseline or lower bound , corresponding to the extreme case where such optimizations are not employed (i.e., a zero cache-hit rate).Under ideal conditions,prefix caching can reduce both prefill service requirements and decode-side KV-cache memory consumption. From a stochastic-ordering perspective, the system with prefix caching exhibits no greater resource demand than its no-caching counterpart.

More generally, our framework is built upon probabilistic models of service requirements and resource occupancy, rather than the specific contents of individual requests. It is therefore extensible to scenarios with prefix caching.In particular, compared with request arrivals, the prefix-cache contents evolve relatively slowly.And for specific application scenarios, users' interests and frequently accessed prefixes often exhibit temporal locality rather than changing drastically with every request. Therefore, over a local window containing multiple request arrivals, the prefix-cache state can be approximately regarded as fixed.Under this assumption, enabling prefix caching induces new probability distributions for effective request lengths and KV-cache memory occupancy, conditioned on the current prefix-cache state.

For prefill, the effective service-time distribution is determined by the distribution of effective prompt lengths, conditioned on the current prefix-cache state, rather than the original prompt-length distribution. This updated service-time distribution can be incorporated into our existing prefill analysis, which accommodates general service-time distributions.For decode, the per-request KV-cache memory requirement can similarly be characterized by a probability distribution conditioned on the current prefix-cache state. The resulting memory-occupancy model can then be incorporated into our existing decode analysis using appropriate probabilistic tools.Although the specific probability distributions and analytical expressions may change, the overall queueing-theoretic framework remains applicable.

We acknowledge that prefix caching is a promising expansion and our current analysis assumes that prefix caching is disabled.Our current work contributes by characterizing the fundamental and critical P-D inference process, which provides a theoretical basis for subsequent studies to progressively relax assumptions and simulate more advanced service optimization mechanisms. We have identified it as a direction for future work and expanded that discussion.Given the time and space available, we will outline the modeling approach in the paper and leave its empirical characterization to future work. We appreciate the reviewer’s constructive and thoughtful question.

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

This paper develops a discrete-time tandem-queue framework for prefill–decode disaggregated LLM inference, incorporating autoregressive generation, evolving KV-cache occupancy, and concurrency limits. It derives the stationary prefill population distribution and develops approximate decode population and tail analyses under different resource bottlenecks. These results inform resource-redundancy thresholds and coordinated provisioning of concurrency and KV-cache capacity. Synthetic simulations evaluate the distributional approximations and resource thresholds.

Critical strengths
  1. The framework captures the interaction between growing KV-cache occupancy and concurrency constraints, providing a useful perspective on resource bottlenecks in disaggregated LLM serving. This helps explain why concurrency and memory should be provisioned jointly.

  2. The exact prefill analysis within the stated model and the tractable decode approximations provide information beyond average load. Extensive simulations, including the coupled prefill–decode process, show encouraging agreement for mean populations and the bulk of the stationary distributions.

Critical weaknesses
  1. The resource thresholds are insufficiently calibrated to the target probability. Table 1 reports small relative errors in threshold values, but these can conceal substantial probability errors. For deterministic arrivals, the predicted threshold at θ = 0.01 is 1807, below the Monte Carlo threshold of 1815 at θ = 0.10. Under the stated threshold definition, this implies an empirical exceedance probability above 10% at the predicted 1% threshold. This weakens confidence in using the estimates to provision resources at a specified tolerance.

  2. Theorem 5 lacks a complete mathematical justification. The stated proof provides qualitative intuition and refers to a numerical illustration, without an explicit workload construction and capacity analysis establishing the strict inequality. Since this result supports the claim that additional joint resource slack can be necessary, a rigorous supporting argument is needed.

Questions for authors
  1. Threshold calibration: What empirical exceedance probabilities are achieved at the predicted thresholds in Table 1, particularly for θ = 0.01? Could you reconcile these probabilities with the intended redundancy tolerance?

  2. Theoretical justification: Could you provide a constructive proof of Theorem 5, including an explicit bounded workload and capacity bounds establishing the strict gap between joint and individual resource capacities?

4 comments
AuthorsOpenReview ↗

Response(1/2)

We appreciate the reviewers' recognition of the strengths of our article and for raising valuable questions. We acknowledge that addressing these two issues would significantly improve the quality of our article, and we will respond to your concerns below.


1. W1&Q1

Thank you for pointing out that "the resource thresholds are insufficiently calibrated to the target probability". We apologize that, partly due to space constraints, Table 1 and the accompanying discussion did not clearly convey the motivation and significance of this analysis. We will clarify this presentation.

We introduce resource-redundancy thresholds in order to distinguish regimes in which system performance is predominantly constrained by KV-cache memory or by concurrency. Request-length bounds alone yield conservative sufficient conditions. Let χ\chi and ω\omega denote prompt and output lengths. An active request occupies at most χmax⁡+ωmax⁡−1\chi_{\max}+\omega_{\max}-1 KV units. For a fixed MM, the system is therefore purely concurrency-constrained when

B≤Blo=⌊Mχmax⁡+ωmax⁡−1⌋.B\le B_{\mathrm{lo}}=\left\lfloor\frac{M}{\chi_{\max}+\omega_{\max}-1}\right\rfloor.

Conversely, each request occupies at least χmin⁡\chi_{\min} KV units, so the system is purely memory-constrained when

B≥Bhi=⌊Mχmin⁡⌋.B\ge B_{\mathrm{hi}}=\left\lfloor\frac{M}{\chi_{\min}}\right\rfloor.

We call [Blo,Bhi][B_{\mathrm{lo}},B_{\mathrm{hi}}] the resource-constraint transition interval. For example, this interval is [833,7488][833,7488] under the configuration in Table 1.

As discussed in Section 6, fixing one resource reveals a very sharp transition of the other from a bottleneck to a redundant resource (Figure 3 in revised Section 7.3). That means a much narrower window can probabilistically separate regimes dominated by a single resource. This also highlights the practical relevance of analyzing single-resource-constrained systems, conceptually resembling the notion of a "typical set" in information theory.

The conservative interval is too broad to offer useful practical provisioning guidance. Our goal is therefore to exploit information about arrivals and decode dynamics to substantially tighten it. Specifically, using the relationship between BB and its exceedance probability provided by Theorem 2, we develop Algorithm 1 (revised Appendix I). We select a tail-probability level ϵ\epsilon in advance and use monotone two-sided bisection, starting from the coarse interval boundaries, to locate the sharp transition window.

The additional evaluation uses the prespecified sensitivity level ϵ=10−9\epsilon=10^{-9}, with target window coverage 1−2ϵ1-2\epsilon. We report empirical coverage, its absolute deviation from the target in percentage points (pp), and the width compression relative to the coarse interval:

Arrival typePredicted windowEmpirical coverage (%)Coverage error (pp)Window compression (%)
Deterministic(1678, 1825]98.01021.989897.79
Poisson(1512, 1888]99.94050.059594.35
Discrete uniform(1360, 1926]99.99890.001191.50

Across all three arrival distributions, the width reduction is at least 91.50%. Empirical coverage exceeds 99.9% under Poisson and discrete uniform arrivals and 98% under deterministic arrivals. The observed errors allow practically meaningful conservative windows.

We therefore wish to clarify that our original presentation did not sufficiently explain the intended purpose of this analysis. For our analytical and practical objectives, predicting the sharp transition window and identifying high-probability single-resource-dominated regimes is more informative than distinguishing whether the exceedance probability at a particular BB within that window is 10% or 20%. Our experiments further show a marked improvement in prediction performance as arrival randomness increases, with both stochastic settings achieving over 99.9% coverage. In practice, exactly deterministic arrivals are rare; daily activity patterns and other factors often introduce substantial variability. The deterministic "worst case" is therefore included for theoretical rigor, rather than as a representative practical workload.

We have updated the relevant discussion and experimental results in the revised manuscript (Sections 6 and 7.3, and Appendix I). Thank you for this question, which helps us communicate the motivation and significance of our work more clearly.

AuthorsOpenReview ↗

Response(2/2)

2.W2&Q2

Thank you for pointing out that Theorem 5 lacks a complete mathematical justification. We agree that more rigorous evidence can make our work more impactful. We have revised the theorem (Section 6) and added a complete constructive proof (Appendix H).

Our motivation is to examine the natural bottleneck intuition that μM,B=min⁡μM,μB\mu_{M,B}=\min\\{\mu_M,\mu_B\\}. This suggests that the ideal resource configuration would balance the two capacities without wasting either resource, i.e., μM,B=μM=μB\mu_{M,B}=\mu_M=\mu_B. However, under χmax⁡≥2χmin⁡\chi_{\max}\ge2\chi_{\min}, we prove that this ideal cannot be attained. We have explained the properties of μM,B\mu_{M,B} and proved them in Theorem 5.

Following other reviewers' suggestions, we now use dynamic, batch-size-dependent decode batch service times, with the original constant-duration model as a special case. Below we present the revised theorem and core proof under this model; these revisions and the full proof are included in Section 6 and Appendix H.

Revised Theorem 5. Assume χmax⁡≥2χmin⁡\chi_{\max}\ge2\chi_{\min}. Every finite feasible configuration M≥χmax⁡M\ge\chi_{\max}, B∈N+B\in\mathbb N_+ admits a strictly effective finite expansion of at least one resource:

\lor (\exists B'\in\mathbb N_+,\\ B' > B:\mu_{M,B'} > \mu_{M,B}).$$ In particular, if the two single-resource reference rates coincide, then $$\mu_{M,B} < \mu_M=\mu_B.$$ Thus, even when the reference rates are matched, the joint system cannot fully attain their common rate. **Proof outline.** Use saturated FCFS service from an empty state, with bounded i.i.d. marks, memory tests only at admission and uninterrupted service. Measure rates in physical time under $T(N)=c_{\mathrm D}+a_{\mathrm D}N$, with $c_{\mathrm D} > 0$ and $a_{\mathrm D}\ge0$. Define $$n_M=\lfloor M/\chi_{\min}\rfloor,\qquad h_\omega=\gcd(\operatorname{supp}\omega),\qquad T_B=B\chi_{\max}+(B-1)(\omega_{\max}-h_\omega).$$ **1. Rate identity.** The bound $N\le\min\\{B,n_M\\}$ gives a finite-state chain of active marks, ages and the inspected head prompt. In each reachable closed class with invariant law $\pi$, work conservation and the ergodic theorem give $$\mu_\pi=f(\mathbb E_\pi[N]),\qquad f(n)=\frac{n}{\mathbb E[\omega](c_{\mathrm D}+a_{\mathrm D}n)}.$$ Here $f'(n) > 0$ and $\mu_B=f(B)$. The empty-start rate averages classwise rates by entry probabilities. **2. Memory expansion.** Admissions and completions occur on the $h_\omega$ iteration lattice. With $n < B$ survivors, refilling to $B$ requires at most $$n(\chi_{\max}+\omega_{\max}-h_\omega) +(B-n)\chi_{\max}\le T_B.$$ Thus $M\ge T_B$ maintains $N=B$ and gives $\mu_{M,B}=f(B)$. If $M < T_B$, suppose a closed class maintained $N=B$. At the cap, the next head is not inspected, so replacement marks are fresh i.i.d. samples. Thus the positions form independent marked renewal chains. Normalized lifetimes have gcd one, so the finite product chain is irreducible and aperiodic. If $\omega_{\max} > h_\omega$, a positive-probability configuration lets one request complete while the other $B-1$ have prompt length $\chi_{\max}$ and age $\omega_{\max}-h_\omega$. A replacement with prompt $\chi_{\max}$ requires $T_B > M$, contradicting closure. If $\omega_{\max}=h_\omega$, simultaneous completions followed by $B$ maximal prompts give the same contradiction. Hence each closed class assigns positive probability to $N < B$, so $$\mu_{M,B} < f(B)=\mu_{T_B,B}.$$ Thus $M'=T_B$ gives a strict gain. **3. Concurrency expansion.** For $M\ge T_B$ and any cap $K > B$, refilling ensures $N\ge B$. Suppose a closed class maintained $N=B$. Although an inspected head may have a biased prompt, its unrevealed output length retains its original law because $\chi\perp\omega$. The residual-length chains thus reach simultaneous completion with positive probability. There, prescribe output length $\omega_{\max}$ for the first $B$ requests and prompt length $\chi_{\min}$ for the following $B+1$. Its conditional probability is $$\Pr\\{\omega=\omega_{\max}\\}^{B} \Pr\\{\chi=\chi_{\min}\\}^{B+1} > 0,$$ without restricting the inspected head's prompt. Either more than $B$ requests enter immediately, or exactly $B$ enter and finish together $\omega_{\max}$ rounds later. Without completions, increasing KV occupancy prevents intermediate admission. The following $B+1$ requests then fit since $$(B+1)\chi_{\min} \le B\chi_{\max} \le T_B \le M.$$ Thus no closed class can remain at $N=B$. Every class has $\mathbb E_\pi[N] > B$, yielding $\mu_{M,K} > f(B)=\mu_{M,B}$. Choose $K=B+1$. Finally, $\mu_M=\mu_{M,n_M}$ since $n_M$ is nonbinding. If $M\ge T_B$, then $n_M\ge B+1$, and Step 3 gives $\mu_M > \mu_B$. Matched reference rates therefore require $M < T_B$, where Step 2 implies $\mu_{M,B} < \mu_M=\mu_B$.

Thank you for adding the constructive argument for Theorem 5. The two cases now make clear which resource can be expanded to obtain a strict throughput gain. I also appreciate the additional Vidur experiments.

My remaining question concerns the interpretation of the provisioning threshold. For deterministic arrivals, the original Table 1 gives a predicted threshold of 1807 for a 1% target, while the Monte Carlo threshold for a 10% target is already 1815. The new result that 98.0102% of observations fall in (1678, 1825] helps locate the transition, but it leaves open the practical question: if an operator provisions at 1807, how often is that threshold exceeded?

Could you report the empirical exceedance frequency at 1807 from the existing simulation, with an uncertainty estimate if available? If the intended use is to locate the transition window, it would also help to make that scope explicit wherever the paper discusses provisioning at a specified tolerance.

Thank you for your follow-up and for raising this important concern. We further address your question by reporting the empirical exceedance frequencies together with approximate 95% Monte Carlo confidence intervals.

Following your suggestion, we evaluate the predicted and empirical exceedance probabilities at a fixed concurrency cap of 1807 under all three arrival distributions. We also compare the predicted concurrency thresholds with their Monte Carlo counterparts at a target exceedance probability of 1%. As shown below, the discrepancy between the theoretical probabilities and empirical frequencies decreases substantially as the arrival process becomes more stochastic. Under discrete uniform arrivals, the difference is approximately 2.17%. Furthermore, when considering the relative error Err=BMC−B^BMC\mathrm{Err} = \frac{B^{\text{MC}} - {\hat{B}}}{B^{\text{MC}}}, all three errors are around 1%.

Arrival distributionBBTheoretical probabilityEmpirical frequency (approximate 95% CI)
Deterministic18071.00%14.00% [13.74%, 14.26%]
Poisson180722.21%28.40% [28.15%, 28.66%]
Discrete uniform180730.41%32.58% [32.12%, 33.05%]
Arrival distributionTheoretical probabilityB^\hat{B}BMCB^{\mathrm{MC}}Err.
Deterministic1.00%180718311.311%
Poisson1.00%183218601.505%
Discrete uniform1.00%184818650.912%

Above phenomenon is consistent with our findings regarding the sharp transition window. Even relatively small changes in concurrency can lead to substantial changes in exceedance probability. This further demonstrates the significance of identifying the sharp transition region: only a narrow interval is needed to probabilistically characterize the region in which a particular resource is unlikely to become a bottleneck. As shown by the results in Section 7.3 of the revised manuscript, our theory provides a relatively accurate characterization of this interval. In practical deployments, operators can use the predicted transition window to guide resource provisioning and avoid leaving scarce resources underutilized.

For the interior of the transition window, our theoretical analysis is also useful. The experimental results show that the predictive accuracy of our approximation improves noticeably as the randomness of request arrivals increases. In practical scenarios, request arrivals are generally stochastic rather than perfectly deterministic.Moreover, precise estimates can be obtained through computationally intensive simulations or Monte Carlo methods, and our theoretical framework effectively narrows down the transition region, substantially reducing the range over which such expensive computations are needed and the overall computational cost.

Thank you again for this valuable question.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.