Quota-Based Aging for Prediction-Guided Scheduling in LLM Serving

Quota-Based Aging for Prediction-Guided Scheduling in LLM Serving Hanzhi Zhang, Anxuan Che, Hang Qi, Qiyue Li, Jingjin Wu

arXiv:2610.17795v1 [cs.DC] 13 Oct 2026

Guangdong Prov./Zhuhai Key Lab of IRADS, Beijing Normal-Hong Kong Baptist University, Guangdong, P. R. China Email: t330005063@mail.bnbu.edu.cn; t330018003@mail.bnbu.edu.cn; t330202706@mail.bnbu.edu.cn; t330005026@mail.bnbu.edu.cn; jj.wu@ieee.org Abstract—Large language model (LLM) serving systems use token-level continuous batching to improve resource utilization, but heterogeneous response lengths complicate request scheduling. Prediction-guided short-first scheduling reduces average latency but can severely delay long requests, while unrestricted aging may over-promote delayed long requests under congestion. We propose Quota-Based Aging (QBA), a lightweight policy that combines predicted short-first admission with quota-bounded, debt-enforced promotion of aged predicted-long requests. We also use a reduced M/G/𝑛 queueing surrogate, calibrated from simulator traces, to explain first-order mean-latency trends. QBA is evaluated using a serving-aware event-driven simulator that models decode-priority batching, chunked prefill, token-budget constraints, and KV-cache-safe admission. We compare QBA with FCFS, predicted short-first, and aggressive aging under asymmetric prediction errors on synthetic and production-derived workloads. The evaluation considers queueing delay, throughput, utilization, and class-conditional tail performance. Results show that QBA provides a controllable middle ground between aggressive short-first prioritization and unrestricted aging, substantially reducing long-request tail latency while retaining much of the mean-latency benefit of prediction-guided scheduling. Index Terms—large language model serving, request scheduling, Quality of Service, aging mechanism, queueing theory

I. Introduction Large Language Models (LLMs) support interactive services such as dialogue, coding, and content generation [1], [2]. Once deployed as online services, they must process dynamically arriving requests under stringent latency requirements. Modern serving engines improve resource utilization through tokenlevel continuous batching [3], [4]. However, this execution model couples scheduling to heterogeneous prompt and response lengths, competing prefill and decode stages, a finite token budget, and KV-cache capacity. Scheduling therefore becomes a core performance-control mechanism: it affects not only average responsiveness, but also whether particular request classes experience extreme delay. Accordingly, we use Quality of Service (QoS) here to refer to the joint control of mean latency and class-conditional tail latency. Length prediction provides a natural signal for exploiting request heterogeneity. Prioritizing requests predicted to be short can reduce mean delay, consistent with classical shortjob-oriented scheduling [5], [6], while recent LLM serving work has explored latency- and efficiency-oriented execution mechanisms [7], [8]. However, predicted short-first (PSF) admission can repeatedly defer predicted-long requests and inflate

their tail latency, especially under congestion. Generic aging can mitigate starvation [9], but unrestricted promotion may place too many delayed long requests ahead of short ones and erase the mean-delay benefit that motivated predictionguided scheduling. Accordingly, we ask the following research question: How can an LLM serving scheduler use coarse binary response-length predictions to retain the meandelay benefit of short-first admission while controlling long-request tail inflation, without aging-based promotions overwhelming the short-first path under token-level serving constraints? To answer this question, we propose Quota-Based Aging (QBA), a QoS-aware bounded-aging scheduler for predictionguided LLM serving. QBA prioritizes predicted-short requests while allowing delayed predicted-long requests to become eligible for promotion through a quantile-based waiting threshold. Rather than promoting every aged predicted-long request, QBA earns one promotion opportunity after every 𝑘 successful short admissions. This opportunity is recorded as promotion debt and is cleared only when an aged predicted-long request is actually admitted. By separating aging eligibility from promotion frequency, QBA provides bounded but enforceable protection for delayed long requests, with 𝑘 serving as an interpretable control over the mean–tail latency trade-off. To characterize this trade-off, we further pair QBA with a reduced M/G/𝑛 queueing abstraction and a realistic eventdriven simulator. The analytical model intentionally collapses implementation details into effective service and parallelism parameters, making the main delay trends interpretable. The simulator then restores practical serving mechanisms, including chunk continuation, KV-cache-safe admission, and token-loaddependent batch service, so that the analytical observations can be checked under realistic dynamics. We additionally test the same scheduling mechanisms, without re-tuning, on production LLM inference traces to examine whether the observed trade-off transfers beyond the synthetic setting. The main contributions are: • We propose QBA, a practical QoS-aware bounded-aging policy designed for prediction-guided LLM serving. To the best of our knowledge, it is a novel policy targeting the coupled serving features above. QBA separates aging eligibility from actual admission: delayed long requests become eligible through a quantile-based waiting threshold, while promotion is bounded by a quota cycle and enforced

through promotion debt. • We develop a tractable M/G/𝑛 abstraction that explains how load, service variability, and bounded promotion affect mean delay under token-level continuous batching. By collapsing token-level execution into effective service moments and effective parallelism, the model gives a compact view of why short-first scheduling lowers mean delay, why aggressive aging can over-correct, and why QBA provides a more controlled operating point. • We validate the analytical trends using realistic eventdriven simulation, showing consistent favorable meandelay/tail-latency trade-off for QBA. The simulator restores serving details absent from the reduced model, including decode-priority batching, continuation handling, KVcache-safe admission, token-budget constraints, and tokenload-dependent batch service. • We further validate QBA on 100 non-overlapping windows of a production Microsoft Azure LLM inference trace [10]. Despite bursty non-Poisson arrivals and a promptresponse composition substantially different from the synthetic workload, the results confirm that QBA remains a stable intermediate operating point without any workloadspecific re-tuning. The implementation and frozen experimental artifacts are publicly available at [11]. 1

Workload

2

3

Binary Predictor

Scheduling Policies Aging-based Policies

Baselines

AA Poisson arrivals

predicted short

prompt/response heterogeneity

6

Metrics

FCFS

PSF

aggressive promotion

5

Evaluation

4

quota k + promotion debt

---

LLM Serving Engine

High-fidelity simulator

mean waiting tail latency fairness-efficiency trade-off

Reduced M/G/n analysis

Sym

Meaning

Sym

Meaning

𝜆, 𝜌 𝑃, 𝐷, 𝑆 𝑌𝑖 , 𝑌ˆ𝑖 𝜖𝑆𝐿/𝐿𝑆 𝑘

arrival rate / load prompt / decode / eff. svc. true/predicted class misclassif. rates QBA quota

𝑛 𝜏0.85 𝜋𝑆/𝐿 𝛾 𝜙𝑋 (𝜌)

effective parallelism short/long cutoff class priors aging quantile level promoted long frac.

A. LLM Serving Model We consider a single-engine LLM serving system with tokenlevel continuous batching [3], [4]. For analytical tractability, we first consider that requests arrive according to a Poisson process with rate 𝜆, a standard open-system abstraction in queueing models [6]. Request 𝑖 is represented by R 𝑖 = (𝑃𝑖 , 𝐷 𝑖 , 𝑌ˆ𝑖 ), where 𝑃𝑖 is the prompt length, 𝐷 𝑖 is the response length, and 𝑌ˆ𝑖 ∈ {𝑆, 𝐿} is a predicted short/long label. 1) Two-stage Execution: Each request evolves through a prefill stage followed by a decode stage. Prefill processes prompt tokens and builds the KV cache, while decode generates response tokens iteratively until completion [10]. Let 𝑃𝑖rem (𝑡) and 𝐷 rem 𝑖 (𝑡) denote the remaining prefill and decode workloads. A request departs when 𝑃𝑖rem (𝑡) = 0 and 𝐷 rem 𝑖 (𝑡) = 0. 2) Decode-Priority Token Batching: At batch boundary ℓ, the scheduler forms a batch under token budget 𝐵, following the batching abstraction used in modern inference-serving systems [3], [12]. Let Dℓ𝜋 and Pℓ𝜋 denote the decode and prefill requests selected by policy 𝜋. The batch must satisfy ∑︁ ∑︁ 𝑞𝑖 + 𝑢 𝑗 ≤ 𝐵, 𝑖 ∈ Dℓ𝜋

𝑗 ∈ Pℓ𝜋

QBA (Proposed)

bounded promotion

predicted long

TABLE I: Key notation.

token-level batching prefill/decode KV-safe admission

Fig. 1: Workflow of prediction-guided LLM request scheduling, including workload generation, binary response-length prediction, scheduling, token-level continuous batching, evaluation, and latency metrics. The synthetic workload follows Poisson arrivals, while the production trace (Section IV-E) retains its original bursty arrival structure.

II. System Model As summarized in Fig. 1, this section defines the LLM serving system, the reduced queueing abstraction, and the prediction labels used by the scheduler.

where 𝑞 𝑖 is the decode block allocated to request 𝑖 and 𝑢 𝑗 is the prefill chunk allocated to request 𝑗. Active decode requests are always served first, and prefill requests are admitted using the residual token budget. 3) Chunk Continuation and KV-Safe Admission: In our simulator, if a prefill request cannot be fully inserted into the current batch, it is chunked and its unfinished remainder is returned to the queue as a continuation request. Continuation requests always have the highest admission priority among prefill candidates. Let 𝑀ℓ be the live KV-cache usage at batch boundary ℓ. Admission is checked against the safe threshold 𝑀safe = 𝜂𝑀max , where 𝑀max is the hard KV capacity, and 𝜂 ∈ (0, 1) is a safety factor, reflecting the central role of KVcache memory in LLM serving [4]. A candidate prefill request is admitted only if the projected KV usage remains below 𝑀safe . 4) Batch Service Time: Let 𝑏 ℓ be the total token load of batch ℓ. Its service time is modeled as 𝑇ℓ = 𝑐 0 + 𝑎 max(0, 𝑏 ℓ − 𝑏 0 ), where 𝑐 0 is a fixed launch overhead, 𝑎 is the marginal per-token coefficient, and 𝑏 0 is a knee point obtained from profiling. The event-driven simulator preserves these serving mechanics, including decode-priority batching, continuation handling, KV-safe admission, and token-load-dependent batch service times. Thus, all scheduling policies compared in this paper operate under the same token budget, KV-cache constraint, and batch-service model.

B. Reduced M/G/𝑛 Abstraction To obtain a compact analytical model that helps to interpret the key results, we collapse the two-stage execution of each request into a single effective service time, following standard queueing practice in which complex service mechanisms are represented by effective service-time distributions [6]: 𝑆𝑖 = 𝑠0 + 𝛼𝑃𝑖 + 𝛽𝐷 𝑖 ,

(1)

where 𝑠0 is a fixed overhead and 𝛼, 𝛽 > 0 are effective prefill/decode coefficients. Hereafter, 𝑃, 𝐷, and 𝑆 denote generic prompt-length, response-length, and effective-servicetime random variables drawn from the same distribution as 𝑃𝑖 , 𝐷 𝑖 , and 𝑆𝑖 . For discrete implementation, l𝐷 m l𝑃 m 𝑖 𝑖 + 𝜏𝑑 , (2) 𝑆 𝑖 ≍ 𝑠0 + 𝜏𝑝 𝐶𝑝 𝑞 where 𝐶 𝑝 is the prefill chunk size, 𝑞 is the decode block size, and 𝜏𝑝 and 𝜏𝑑 are the effective service times of one prefill chunk and one decode block, respectively. 1) Effective Parallelism: Although the actual engine is not a classical multi-server queue, we approximate it as an M/G/𝑛 system with effective parallelism 𝑛 = ⌊min(𝐵/𝑞, 𝑛safe )⌋, where 𝐵/𝑞 is the decode concurrency implied by the token budget and 𝑛safe is the maximum safe concurrency under KV constraints [6]. Let 𝜇 = 1/E[𝑆] and 𝜌 = 𝜆E[𝑆]/𝑛. The reduced system is stable when 𝜌 < 1. 2) Moment Characterization: From (1), the first two moments are E[𝑆] = 𝑠0 + 𝛼E[𝑃] + 𝛽E[𝐷],
E[𝑆 ] = 𝑠02 + 2𝑠0 𝛼E[𝑃] + 𝛽E[𝐷] 2 2 2 2

(3)

2

+ 𝛼 E[𝑃 ] + 𝛽 E[𝐷 ] + 2𝛼𝛽E[𝑃𝐷].

(4)

Let 𝐶𝑠2 = Var(𝑆)/E[𝑆] 2 . When arrivals are Poisson, 𝐶𝑎2 = 1. This abstraction collapses prefill, decode, batching, and KV admission into a single effective service time together with a static effective parallelism. It preserves first-order mean-delay trends but cannot resolve token-level dynamics such as decodepriority preemption, chunk continuation, or the time-varying batch composition. We therefore use (1)–(2) only to explain mean-level trends, while tail latencies and token-level metrics are evaluated in the simulator. C. Label Construction and Prediction Assumption To make the short/long partition well-defined, we consider that each request has an underlying response-length random variable 𝐷 𝑖 drawn from a stationary workload distribution. Rather than assuming that the predictor directly outputs an arbitrary binary label, we define the true short/long class through a workloadlevel cutoff. Let 𝜏0.85 be a fixed threshold chosen from the estimated response-length distribution, for example as a quantile corresponding to a desired short/long split. The true class of request 𝑖 is defined as ( 𝑆, 𝐷 𝑖 ≤ 𝜏0.85 𝑌𝑖 = , (5) 𝐿, 𝐷 𝑖 > 𝜏0.85

1) Binary Predictor: We assume a lightweight binary predictor that estimates the thresholded class 𝑌𝑖 rather than the exact response length. Accordingly, the scheduler observes only the predicted label 𝑌ˆ𝑖 ∈ {𝑆, 𝐿}, where 𝑆 and 𝐿 denote predictedshort and predicted-long requests. 2) Prediction Errors: The class priors are 𝜋 𝑆 = Pr(𝑌𝑖 = 𝑆) and 𝜋 𝐿 = 1−𝜋 𝑆 = Pr(𝑌𝑖 = 𝐿). We characterize prediction errors by the two misclassification rates 𝜖 𝐿𝑆 = Pr(𝑌ˆ = 𝑆 | 𝑌 = 𝐿) and 𝜖 𝑆𝐿 = Pr(𝑌ˆ = 𝐿 | 𝑌 = 𝑆), which correspond to long-to-short and short-to-long errors, respectively. Under this assumption, the predicted-class arrival rates satisfy   𝜆 𝑆 = 𝜆 (1 − 𝜖 𝑆𝐿 )𝜋 𝑆 + 𝜖 𝐿𝑆 𝜋 𝐿 , (6)   𝜆 𝐿 = 𝜆 𝜖 𝑆𝐿 𝜋 𝑆 + (1 − 𝜖 𝐿𝑆 )𝜋 𝐿 . (7) III. Scheduling Policies and Analytical Approximation This section describes the scheduling policies evaluated in the paper and their reduced analytical approximations. At each scheduling decision, active decode requests retain priority because they correspond to already-started generations. The policies below therefore mainly determine the admission order among queued prefill candidates after decode traffic and continuation requests have been handled. A. Baseline and Prediction-Guided Policies 1) FCFS Baseline: First-come-first-served (FCFS) admits queued prefill requests in arrival order, subject to the tokenbudget and KV-cache constraints defined in the system model. Let 𝑊𝑞 denote queueing delay before service and 𝑇 denote end-to-end response time. For this baseline, we use the Allen– Cunneen approximation for a multi-server queue with general service-time variability [6]: E[𝑊𝑞FCFS ] ≈

𝐶𝑎2 + 𝐶𝑠2 𝑃wait · , 2 𝑛𝜇 − 𝜆

(8)

where 𝑃wait is the Erlang-C delay probability of the corresponding M/M/𝑛 system. Hence, E[𝑇 FCFS ] ≈ E[𝑆] + E[𝑊𝑞FCFS ]. We model prediction-guided scheduling as a non-preemptive two-class priority discipline on top of the reduced M/G/𝑛 abstraction. 2) Predicted Classes: Requests are partitioned into predicted-short and predicted-long classes. Let 𝜆 𝑆 = 𝜆 Pr(𝑌ˆ = 𝑆) and 𝜆 𝐿 = 𝜆 Pr(𝑌ˆ = 𝐿), with 𝜆 𝑆 + 𝜆 𝐿 = 𝜆. Define the classconditional moments 𝑚 𝑟(𝑐) = E[𝑆𝑟 | 𝑌ˆ = 𝑐] for 𝑐 ∈ {𝑆, 𝐿} and 𝑟 = 1, 2, and the corresponding loads 𝜌 𝑐 = 𝜆 𝑐 𝑚 1(𝑐) /𝑛. 3) PSF Mean Waiting Approximation: Predicted short-first (PSF) prioritizes predicted-short requests over predicted-long requests, while preserving arrival order within each predicted class, motivated by the classical mean-delay advantage of shortjob-oriented service disciplines [5]. Exact closed forms for non-preemptive priority M/G/𝑛 queues do not yield a compact expression. We therefore use a compact priority correction that preserves the FCFS congestion term while capturing the shortfirst effect [6]. Let Ω𝑛 = (1 − 𝜌)E[𝑊𝑞FCFS ]. Then the queueing

delays of the two predicted classes are approximated by Ω𝑛 , 1 − 𝜌𝑆 Ω𝑛 E[𝑊𝑞( 𝐿) ] ≈ . (1 − 𝜌 𝑆 ) (1 − 𝜌) E[𝑊𝑞(𝑆) ] ≈

(9)

denominator counts all predicted-long jobs. These fractions are obtained at several load points and interpolated over 𝜌 to form load-dependent surrogates. The corresponding effective high-priority arrival rates are

(10)

The overall mean queueing delay under predicted short-first scheduling is 𝜆𝑆 𝜆𝐿 E[𝑊𝑞PSF ] ≈ E[𝑊𝑞(𝑆) ] + E[𝑊𝑞( 𝐿) ], (11) 𝜆 𝜆 and therefore E[𝑇 PSF ] ≈ E[𝑆] + E[𝑊𝑞PSF ]. 4) Quantile-Based Aging: To mitigate starvation of delayed predicted-long requests, the simulator uses a quantile-based aging threshold rather than a moment-based threshold, consistent with recent attention to queue-aware and scheduling-aware LLM serving [13]. Let 𝑊ref denote the empirical waiting-time sample used by the aging module. The threshold is 𝜃 𝐴 = 𝑄 𝛾 (𝑊ref ), where 𝑄 𝛾 (·) is the empirical 𝛾-quantile and 𝛾 ∈ (0, 1] is a tunable parameter. A predicted-long request becomes aged once its waiting time exceeds 𝜃 𝐴. The reference sample may be taken either from the current waiting queue or from the started-request history; in our experiments we use the history-based variant. 5) Aggressive Aging (AA): Aggressive Aging (AA) promotes all currently aged predicted-long requests ahead of ordinary predicted-short requests. This mechanism serves as a natural fairness-oriented1 extension of short-first scheduling: it mitigates starvation of delayed long requests, but can overcorrect under heavy congestion because aged long requests may repeatedly occupy the short-first admission path. This limitation motivates the bounded design of QBA. 6) Quota-Based Aging (QBA): QBA combines a per-𝑘short-admissions quota with a promotion-debt state to bound aged predicted-long promotions. A short-admission counter advances only when a short prefill fully completes (not on chunk continuations); once it reaches 𝑘, one promotion debt is earned and cannot be displaced by further short admissions, but debt is cleared (and the counter reset to 0) only when the oldest eligible aged-long request is actually admitted; while debt is pending the counter stays at 𝑘, serializing promotions to at most one per quota cycle. B. Mean-Level Surrogate and Simulator Alignment 1) Mean-Level Surrogate for AA and QBA: In the analytical model, both AA and QBA are represented through effective promoted fractions estimated from simulator traces, yielding a reduced empirical closure rather than an exact priorityqueue solution [6]. For AA, let 𝜙 𝐴 (𝜌) denote the empirical fraction of predicted-long jobs whose waiting time exceeds the aging threshold at service start. For QBA, let 𝜙𝑄 (𝜌; 𝑘) = 𝑁promoted-long /𝑁predicted-long , where the numerator counts successfully promoted predicted-long jobs under the quota rule and the 1 In this paper, fairness means tail-latency fairness, the protection of delayed long requests from starvation-induced tail inflation under short-first admission, rather than a Jain-index-style per-class balance or a direct short-versus-long latency gap. Accordingly, an efficiency–fairness trade-off denotes the tension between reducing mean delay and controlling long-request tail latency.

𝜆 𝑆( 𝐴) = 𝜆 𝑆 + 𝜙 𝐴 (𝜌)𝜆 𝐿 ,

(12)

𝜆 𝑆(𝑄) = 𝜆 𝑆 + 𝜙𝑄 (𝜌; 𝑘)𝜆 𝐿 .

(13)

The promoted high-priority class then has mixed moments 𝑚˜ 𝑟(𝑆,𝑋) =

𝜆 𝑆 𝑚 𝑟(𝑆) + 𝜙 𝑋 (𝜌)𝜆 𝐿 𝑚 𝑟(𝐿) , 𝜆 𝑆 + 𝜙 𝑋 (𝜌)𝜆 𝐿

𝑋 ∈ { 𝐴, 𝑄}, 𝑟 = 1, 2.

(14) Here 𝜙 𝑋 (𝜌) denotes 𝜙 𝐴 (𝜌) for 𝑋 = 𝐴 and 𝜙𝑄 (𝜌; 𝑘) for 𝑋 = 𝑄. Substituting these mixed moments into the PSF approximation yields reduced mean-level surrogates for the aggressive-aging variant AA and the bounded policy QBA. For this closure, 𝜆 𝐿(𝑋) = 𝜆 − 𝜆 𝑆(𝑋) , 𝜌 𝑆(𝑋) = 𝜆 𝑆(𝑋) 𝑚˜ 1(𝑆,𝑋) /𝑛, and E[𝑊𝑞(𝑆,𝑋) ] and E[𝑊𝑞(𝐿,𝑋) ] are obtained by applying the same priority-correction form as in (11) with the mixed promoted class. Thus, 𝜙 𝑋 (𝜌) controls the effective high-priority population: larger promoted fractions improve delayed-long access but also increase congestion in the short-first path. E[𝑊𝑞𝑋 ] ≈

𝜆 𝑆(𝑋)

E[𝑊𝑞(𝑆,𝑋) ] +

𝜆 𝐿(𝑋) E[𝑊𝑞(𝐿,𝑋) ], 𝜆

𝑋 ∈ { 𝐴, 𝑄}. (15) The reduced closures in (15) and the simulator share the same workload family and prediction setup; the analytical layer collapses engine details for mean-level interpretation, while the simulator preserves token-level dynamics for tail-latency, TTFT, and fairness-efficiency evaluation. 𝜆

IV. Experiments A. Experimental Setup 1) Synthetic Workload Generation: We evaluate all policies on a synthetic request stream designed to mimic heterogeneous LLM serving workloads [14]. Requests arrive according to a Poisson process with arrival rate 𝜆. For each request, the prompt length is sampled from a mixture distribution: with probability 0.7 it is drawn from N (100, 302 ), and with probability 0.3 it is drawn from a Pareto distribution with shape 1.4 and scale 40, reflecting the heavy-tailed prompt-length behavior observed in production LLM workloads [14]. Both prompt and response lengths are capped at 4096 tokens. Conditioned on the prompt length 𝑃𝑖 , the response length 𝐷 𝑖 is generated from a lognormal model
𝐷 𝑖 ∼ LogNormal 𝛽0 + 𝛽1 log(1 + 𝑃𝑖 ), 𝜎 2 , with 𝛽0 = 3, 𝛽1 = 0.75, and 𝜎 = 0.3. 2) Prediction Labels: We construct short/long labels using the empirical 0.85-quantile of the generated response-length distribution. Unless otherwise stated, the predicted label matches the thresholded ground-truth label exactly. This noiseless setting isolates the scheduling mechanism; asymmetric prediction errors are evaluated separately below.

 



  



YKIUTJY

YKIUTJY



,),9 69, '' 7('

  









(a) Formula Mean waiting time 𝐸 [𝑊𝑞 ]



         

,),9 69, '' 7('

 

YKIUTJY



,),9 69, '' 7('

  











(b) Simulation Mean waiting time





 















(c) Simulation P99 waiting time

Fig. 2: Mean and tail waiting-time comparison of FCFS, PSF, AA, and QBA under the reduced analytical model and the high-fidelity simulator.

3) Serving-System Configuration: The serving engine uses a token budget of 𝐵 = 128 per iteration and a decode block size of 𝑞 = 8 tokens. The KV-cache capacity is set to 8192 tokens, and admission is guarded by a safety threshold equal to 0.7 of the total KV budget. Batch service time follows the profiled piecewise-linear model with parameters 𝑐 0 = 0.003, 𝑎 = 2 × 10−5 , and knee point 𝑏 0 = 64; concurrency correction and timing jitter are disabled in the main experiments. For the aging-based schedulers, the aging module uses a historybased reference sample with quantile parameter 𝛾 = 0.80. QBA additionally uses quota 𝑘 = 5. These values are used as the default configuration unless the corresponding parameter is explicitly varied in a sensitivity experiment. 4) Policy Comparison Protocol: We compare four schedulers defined in Section III: FCFS, PSF, AA, and QBA. All policies operate under the same token budget, KV-cache constraint, prediction labels, and batch-service model. For the main load-sweep experiment, we vary the arrival rate over 𝜆 ∈ {26, 27, 28, . . . , 40} and report the mean waiting time together with the 99th percentile waiting time. Each simulated operating point is repeated over 100 random seeds. We report seed-averaged results, and shaded bands indicate the corresponding confidence intervals. 5) Analytical Protocol: The reduced analytical model is calibrated from an FCFS trace at the calibration load 𝜆 = 30. This calibration yields the effective service moments and the effective parallelism parameter used in the M/G/𝑛 approximation. The calibration point is chosen in the congested regime so that the effective service moments reflect a non-trivial queue, and it differs from the 𝜆 = 32 reference load used for the main comparisons. For AA and QBA, the effective promoted fractions are not assumed a priori; instead, they are estimated from simulator traces at 𝜆 ∈ {25, 27, 29, 31, 33} and interpolated as load-dependent surrogate functions in the reduced model. The objective of the analytical comparison is not exact numerical matching with the simulator, but a reduced mean-level characterization of the scheduling trends. 6) Prediction-Error Protocol: To evaluate sensitivity to imperfect length prediction, we consider two asymmetric label

errors. We define the short-to-long error rate as 𝜖 𝑆𝐿 = Pr(𝑌ˆ = long | 𝑌 = short), and the long-to-short error rate as 𝜖 𝐿𝑆 = Pr(𝑌ˆ = short | 𝑌 = long), where 𝑌 and 𝑌ˆ denote the ground-truth and predicted request classes, respectively. The two error directions are evaluated independently: we sweep one error rate over {0, 0.05, 0.10, . . . , 0.40} while fixing the other to zero. For each error level, the same scheduling policies and serving-system configuration are used as in the main comparison. Each operating point is repeated over 100 paired random seeds. In addition to overall mean waiting time, we report the 99th percentile waiting time separately for the true-short and true-long request classes. These class-conditional metrics are used to reveal latency redistribution that may be obscured by aggregate averages, particularly when prediction errors affect the two request classes asymmetrically. B. Performance Comparison Fig. 2 compares FCFS, PSF, AA, and QBA using both the reduced analytical model and the high-fidelity simulator. We first examine the mean-level trends predicted by the analytical model in Fig. 2(a). The reduced model yields a consistent first-order ordering: all prediction-guided policies improve over FCFS in mean waiting time, PSF achieves the lowest mean delay, and both AA and QBA remain between PSF and FCFS over the evaluated load range. Moreover, QBA remains very close to AA in the analytical curves, and is slightly lower over most of the evaluated range, indicating that quota-based bounded aging preserves most of the benefit of aging while avoiding overly aggressive promotion of delayed long requests. The simulator in Fig. 2(b) reveals a more realistic trade-off. PSF consistently minimizes the mean waiting time, confirming the efficiency advantage of short-first scheduling. However, the aggressive aging policy AA over-corrects under congestion and eventually exceeds FCFS in mean delay. In contrast, QBA substantially mitigates this degradation: across the tested loads, its

7(' ,),9 69, ''



 



Q





(a) Simulation Mean waiting time vs quota k



   

 

'' 7(' ,),9 69,



 

7(' ,),9 69, ''



YKIUTJY

YKIUTJY



YKIUTJY







Q





(b) Simulation P99 waiting time vs quota k















(c) Simulation P99 waiting time vs 𝛾

Fig. 3: Sensitivity of QBA to the quota parameter 𝑘 and the aging-quantile-level parameter 𝛾 at the reference load. Solid curves show seed-averaged simulation results over 100 random seeds, and shaded bands indicate confidence intervals. Dashed horizontal lines provide baseline references for context.

mean waiting time remains below FCFS and significantly below AA, while preserving a substantial fraction of the efficiency advantage of PSF. This result supports the main motivation of QBA: bounded and enforceable promotion preserves mean-delay performance more reliably than unconstrained aging. The tail behavior is shown in Fig. 2(c). As expected, PSF exhibits the most severe tail inflation, especially at high load, confirming that pure short-first prioritization amplifies starvation risk for delayed long requests. Both aging-based policies substantially reduce this extreme-tail growth relative to PSF. However, the seed-averaged results show a more nuanced ordering than in the single-run case. At low load, FCFS and QBA are very close in the tail, and both remain well below PSF. Under moderate and high load, FCFS becomes the strongest tail baseline, AA attains a lower P99 than QBA, and QBA still remains far below PSF. Accordingly, the main advantage of QBA is a more favorable mean–tail trade-off than aggressive aging when average delay is also an important objective. Overall, Fig. 2 still validates the basic scheduling picture studied in this paper: PSF is the most efficient but least fair baseline, AA represents an aggressive fairness-oriented correction that sacrifices mean delay, and QBA serves as a practical middle ground that recovers much of the mean-delay advantage of prediction-guided scheduling while avoiding the extreme tail inflation of pure short-first prioritization.

indicates that reducing the frequency of long-request promotion gradually restores more of the efficiency advantage of short-first scheduling. In contrast, Fig. 3(b) reveals a non-monotonic tail trend: the P99 waiting time is minimized at a moderate value around 𝑘 = 4, and then increases as 𝑘 becomes larger. This implies that the quota parameter does not merely interpolate linearly between fairness and efficiency. Instead, it creates a useful operating region: small 𝑘 behaves more like aggressive aging, large 𝑘 drifts toward PSF, and an intermediate 𝑘 yields the best tail control within the QBA family while retaining a substantial mean-delay gain. In particular, the lowest P99 within the QBA family is attained around 𝑘 = 4, although FCFS still remains the lowest-tail baseline at the same reference load. The third panel, Fig. 3(c), shows that 𝛾 functions mainly as a secondary trigger-strength parameter. For QBA, the P99 waiting time remains relatively flat over a broad interval from approximately 𝛾 = 0.5 to 𝛾 = 0.95, and deteriorates sharply only when 𝛾 approaches 1.0. By contrast, AA is more sensitive to 𝛾: its P99 improves steadily as 𝛾 increases toward 0.95, but also collapses at 𝛾 = 1.0 when aging becomes effectively disabled. Therefore, the role of 𝛾 is different from that of 𝑘. The quota parameter primarily determines the policy’s position on the efficiency-fairness spectrum, whereas 𝛾 mostly fine-tunes the aggressiveness of aging around that operating point. In this sense, QBA is not the lowest-tail policy under 𝛾 tuning, but it is the more robust one across a wide range of threshold settings.

C. Sensitivity Analysis of QBA Hyperparameters We next study the sensitivity of QBA to its two main hyperparameters: the quota parameter 𝑘 and the aging-quantilelevel parameter 𝛾. All results in Fig. 3 are obtained at the reference load 𝜆 = 32. For the quota sweep, we vary 𝑘 from 2 to 14 with step size 2 while fixing 𝛾 = 0.8. For the aging sweep, we vary 𝛾 from 0.5 to 1.0 with step size 0.05 while fixing 𝑘 = 5. The first two panels of Fig. 3 show that the quota parameter 𝑘 acts as the primary control knob of QBA. As shown in Fig. 3(a), the mean waiting time is nearly flat for very small 𝑘 and then decreases markedly once 𝑘 reaches a moderate range. This

D. Sensitivity to Asymmetric Prediction Errors Figure 4 first demonstrates the results of short-to-long errors, where genuinely short requests are incorrectly assigned to the predicted-long class. For PSF, increasing 𝜖 𝑆𝐿 progressively removes short requests from the high-priority class, raising the overall mean waiting time. More importantly, even a small error rate sharply increases the true-short tail: at 𝜖 𝑆𝐿 = 0.05, the P99 waiting time of true-short requests increases from approximately 1.24 s to 7.03 s. This demonstrates that aggregate mean latency alone does not capture the impact of prediction errors on the requests that lose their intended priority.

     





E92





        

(a) Overall mean waiting time

69, '' 7(' ,),9





YKIUTJY

YKIUTJY



69, '' 7(' ,),9

YKIUTJY





E92





69, '' 7(' ,),9

  

(b) True-short P99 waiting time





E92





(c) True-long P99 waiting time

Fig. 4: Sensitivity to short-to-long prediction errors (𝜖 𝐿𝑆 = 0, 𝜆 = 32). Panels: mean, true-short P99, true-long P99. Same 100-seed convention as Fig. 3.





 

 

  



69, '' 7(' ,),9

YKIUTJY

YKIUTJY



69, '' 7(' ,),9

YKIUTJY







E29



(a) Overall mean waiting time









E29



(b) True-short P99 waiting time



       

69, '' 7(' ,),9





E29





(c) True-long P99 waiting time

Fig. 5: Sensitivity to long-to-short prediction errors (𝜖 𝑆𝐿 = 0, 𝜆 = 32). Panels: mean, true-short P99, true-long P99. Same 100-seed convention as Fig. 3.

QBA exhibits a different response to short-to-long errors. Its mean waiting time initially decreases, reaching approximately 1.13 s at 𝜖 𝑆𝐿 = 0.10, but this apparent improvement is accompanied by substantial degradation in both class-conditional tails. Over the same range, the true-short P99 increases from 3.44 s to 7.59 s and the true-long P99 increases from 7.64 s to 9.45 s. Hence, the mean-delay reduction is not increased robustness, but a redistribution across true classes. This behavior is consistent with contamination of the predicted-long class: short requests that are misclassified as long enter the same population from which aging-based promotions are selected, potentially diluting the protection intended for genuinely long requests. As 𝜖 𝑆𝐿 becomes large, PSF and QBA gradually converge because the predicted classes themselves carry progressively less useful length information. Figure 5 shows a qualitatively different failure mode under long-to-short errors. PSF remains highly efficient in terms of the aggregate mean: increasing 𝜖 𝐿𝑆 from 0 to 0.4 changes its mean waiting time only from approximately 0.83 s to 0.91 s. Its trueshort P99 also increases only moderately. These aggregate and short-class metrics, however, conceal a substantial deterioration in the long-request tail. The true-long P99 of PSF rises from approximately 11.10 s

under perfect prediction to 17.29 s at 𝜖 𝐿𝑆 = 0.4, an increase of about 56%. Under QBA, increasing 𝜖 𝐿𝑆 redistributes latency between the two true classes: the true-long P99 falls from 7.64 s to 5.27 s, while the true-short P99 rises from 3.44 s to 5.23 s as misclassified long requests enter the predicted-short path. At 𝜖 𝐿𝑆 = 0.4, QBA still cuts the true-long P99 by about 70% versus PSF, bounding the long-tail amplification that pure PSF suffers. This tail protection is not free. QBA’s overall mean waiting time increases from approximately 1.42 s to 1.92 s as 𝜖 𝐿𝑆 increases to 0.4, leaving only a marginal mean-latency advantage over FCFS at high error rates. Its true-short P99 also increases from 3.44 s to 5.23 s. Therefore, QBA should not be interpreted as prediction-error invariant: long-to-short errors primarily erode its efficiency advantage while shifting latency toward the true-long class, rather than leaving its tail protection stable. AA shows a similarly stable tail response at high 𝜖 𝐿𝑆 , indicating that aging-based fairness mechanisms in general are less susceptible than pure PSF to long-tail amplification in this error direction. QBA’s distinguishing role is therefore its quotacontrolled intervention under accurate or moderately accurate prediction, rather than uniform dominance over unrestricted aging. Taken together, Figs. 4 and 5 show that prediction errors

TABLE II: Production-trace-driven evaluation over 100 nonoverlapping Microsoft Azure LLM inference windows. Reported P99s are per-window medians; mean wait is pooled across all requests. Policy FCFS PSF AA QBA

Mean Wait (s) 0.179 0.123 0.178 0.146

P99 Wait (s) 0.771 1.376 0.949 0.951

Short P99 (s) 0.771 0.285 0.970 0.565

Long P99 (s) 0.766 2.097 0.491 1.446

TTFT P99 (s) 0.804 1.428 0.975 0.998

cannot be characterized by a single accuracy value. Their impact depends both on the direction of misclassification and on the scheduling mechanism. Short-to-long errors degrade class separation and can interfere with QBA’s targeting of delayed predicted-long requests, whereas long-to-short errors progressively transfer priority toward true-long requests and erode the short-first efficiency advantage. For pure PSF, the latter error direction is particularly harmful to true-long tail latency despite only a small change in the aggregate mean. QBA therefore does not eliminate prediction sensitivity; instead, it changes the failure mode of prediction-guided short-first scheduling and, in both error directions, avoids the severe longtail amplification exhibited by pure PSF. E. Production-Trace Validation We next test whether the same efficiency–fairness trade-off extends from synthetic workloads to a 100-window Microsoft Azure LLM trace [10] with no change to the engine or scheduler. Each window preserves original request ordering and relative inter-arrival structure, with the timeline normalized to 𝜆 = 32; prompt and response lengths are uniformly scaled by a factor of 0.44 to match synthetic demand. All serving-system and scheduling parameters are kept unchanged. The resulting traces remain strongly non-Poisson, with a mean inter-arrival squared coefficient of variation of approximately 2.9. Table II shows that the production traces preserve the efficiency–fairness tension observed in the controlled experiments. PSF reduces mean waiting time by 31% relative to FCFS, but increases true-long P99 from 0.77 s to 2.10 s. QBA reduces this long-tail value to 1.45 s while retaining a 18% mean-delay improvement over FCFS. Across all 100 trace windows, PSF, QBA, and AA consistently form the same ordering in mean delay, whereas the ordering is reversed for true-long P99. Thus, without workload-specific retuning, QBA remains a stable intermediate operating point between short-first efficiency and aggressive aging-based tail protection. Throughput is essentially identical across all four policies (≈ 2.47 × 104 tokens/s), batch utilization within 0.89–0.91, with zero OOM events across all windows. V. Conclusion QBA is a bounded-aging scheduler for token-level continuous batching in LLM serving, regulating aged-long promotions through a per-𝑘-short-admissions quota with enforceable promotion debt. Validated on FCFS/PSF/AA over synthetic and 100-window Azure traces, QBA retains roughly 59% of PSF’s mean-delay gain while substantially reducing tail inflation, with

no aged predicted-long request indefinitely postponable under bounded 𝑘. Acknowledgment This work was partly supported by the Guangdong Provincial Key Laboratory IRADS, BNBU (Project code 2022B1212010006), and the Guangdong Higher Education Upgrading Plan (2021–2025) UIC R0400001-22 and R040002422. References [1] T. B. Brown, et al., “Language models are few-shot learners,” in Proc. Adv. Neural Inf. Process. Syst. (NeurIPS), vol. 33, 2020, pp. 1877–1901. [2] OpenAI, “GPT-4 technical report,” arXiv preprint arXiv:2303.08774, 2023. [3] X. Zhang, et al., “Edge intelligence optimization for large language model inference with batching and quantization,” in Proc. IEEE Wireless Commun. Netw. Conf. (WCNC), 2024, pp. 1–6. [4] W. Kwon, et al., “Efficient memory management for large language model serving with PagedAttention,” in Proc. 29th ACM Symp. Operating Syst. Principles (SOSP). ACM, 2023, pp. 611–626. [5] L. E. Schrage and L. W. Miller, “The queue M/G/1 with the shortest remaining processing time discipline,” Oper. Res., vol. 14, no. 4, pp. 670– 684, 1966. [6] M. Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge, UK: Cambridge Univ. Press, 2013. [7] B. Wu, et al., “FastServe: Fast distributed inference serving for large language models,” arXiv preprint arXiv:2305.05920, 2023. [8] Y. Sheng, et al., “FlexGen: High-throughput generative inference of large language models with a single GPU,” in Proc. 40th Int. Conf. Mach. Learn. (ICML), vol. 202, 2023, pp. 31 094–31 116. [9] A. Silberschatz, P. B. Galvin, and G. Gagne, Operating System Concepts, 10th ed. Hoboken, NJ, USA: Wiley, 2018. [10] P. Patel, et al., “Splitwise: Efficient generative LLM inference using phase splitting,” in Proc. ACM/IEEE 51st Annu. Int. Symp. Comput. Archit. (ISCA), 2024, pp. 118–132. [11] H. Zhang. (2026) qba-llm-serving: Quota-Based Aging for PredictionGuided Scheduling in LLM serving. Accessed: Aug. 16, 2026. [Online]. Available: https://github.com/Julianjiuxi/qba-llm-serving [12] Z. Liu, Q. Lan, and K. Huang, “Resource allocation for multiuser edge inference with batching and early exiting,” IEEE J. Sel. Areas Commun., vol. 41, no. 4, pp. 1186–1200, Apr. 2023. [13] P. Jiang, et al., “SLoB: Suboptimal load balancing scheduling in local heterogeneous GPU clusters for large language model inference,” IEEE Trans. Comput. Soc. Syst., vol. 11, no. 6, pp. 7941–7951, Dec. 2024. [14] Y. Xiang, et al., “ServeGen: Workload characterization and generation of large language model serving in production,” arXiv preprint arXiv:2505.09999, 2025.

Related documents

• Denoising Surface: Modeling and Predicting Inference Cost for Diffusion LLM Serving#1155434
• Quota-Based Aging for Prediction-Guided Scheduling in LLM Serving#1343003
• Deadline-Aware Adaptive Prefill Chunking for Efficient Large Language Model Serving#985295
• MAPS: Memory-Aware Predictive Scheduling Framework for Large Language Model Serving#1109381
• Fast Recovery for LLM Serving via Decoupled Device Memory Lifetime in Dynamo#1061091