Predicting how many tokens a large language model (LLM) will decode, using only prefill-phase hidden states, is a key primitive for inference scheduling. We show that current benchmarks conflate predictor quality with task hardness: when the target model, dataset, or sampling configuration changes, reported accuracy collapses even though the predictor is unchanged. We trace this instability to an overlooked error source---the inherent stochasticity of autoregressive decoding---and derive bounds that every prefill-side method must obey. Our analysis treats decoding as a stopped stochastic process. The per-step stopping probability of a response is not constant but ramps up over hundreds of steps, so the decode length inherits a central limit theorem from the many local decisions that determine where a response ends; this yields per-prompt normality with an explicit error term, together with an affine variance law σ=αμ+b whose slope is the coefficient of variation of the number of response segments. Empirically, the normal law reproduces the per-prompt MAE and the central mass of the decode-length distribution to within a few percent, and the residual departures from normality (mild right skew, slight excess kurtosis) are the ones predicted by the sampling-noise correction. Under fixed model, data, and sampling conditions, a broad design space of predictors (MLP, EGTP, FiLM, soft-label, and Mixture-of-Experts variants) converges to similar performance close to the bound, confirming that system error dominates model error. We argue for a benchmarking protocol that fixes the model, data, and sampling parameters and that reports relative-error metrics alongside absolute ones. Code and analysis tools are available at https://github.com/ShwStone/DecodingPredict.
Figures & tables
Model
α
μ
b
Qwen3-4B-no-thinking
0.2029
814.25
5.56
Qwen3-4B-Instruct
0.1068
1443.28
31.25
DeepSeek-R1-distilled-thinking
0.1156
676.00
147.60
Llama3-8B
0.2042
555.23
−1.39
Qwen3-32B
0.1486
907.92
27.36
Qwen3-30B-A3B-Instruct
0.1682
1479.78
12.18
Table 1: Per-model σ – μ law on ShareGPT (300 prompts × 200 decodes). Lower α and b indicate more stable generation. By Corollary A.3 , α=CV(M) and b=κ1/(2α) .
Figure 1: Normality of decode length (Qwen3-32B, ShareGPT). (a) Q–Q plot for a representative prompt ( μ=1946 , σ=217 , K=200 ); the deviations are confined to the extreme tails. (b) Pooled standardized lengths of all 298 non-degenerate prompts ( 59,600 decodes) against N(0,1) : a slightly peaked, slightly right-skewed Gaussian, as predicted by Remark A.5 .
Figure 2: The stopping process of the prompt in Fig. 1 (a). (a) Empirical survival function on a log scale; a constant hazard would produce the dashed straight line, whereas the observed curve steepens with t , i.e. the stopping probability increases with length. (b) Bin-wise stopping probability (bin width 5% of μ ): the hazard ramps from ≈0 to ≈1 over roughly 350 steps, which is the aggregation that Theorem 3.2 requires and Remark A.2 rules out.
Figure 3: Per-prompt mean μ versus standard deviation σ on ShareGPT (Qwen3-32B, 300 prompts × 200 decodes). The linear trend σ=αμ+b of Corollary A.3 is visible, with outliers reflecting prompt-specific constraints.
Figure 4: Per-prompt test MAE versus per-prompt σ (Qwen3-32B, ShareGPT). The linear fit (blue) closely tracks the theoretical lower bound (red, MAEmin=σ2/π ).
Method
MAE ↓
Acc@100 ↑
Acc@200 ↑
Acc@500 ↑
x(p90) ↓
MLP-Mean
181.21
45.07%
68.91%
93.51%
402.78
MLP-Concat
169.31
48.91%
71.11%
94.35%
391.09
MLP-Concat + LayerNorm
168.13
48.63%
71.65%
94.45%
392.13
EGTP-style
466.79
14.58%
25.35%
61.86%
891.48
FiLM
192.69
38.30%
–
–
–
Soft-Label (50 bins)
183.24
45.05%
–
–
–
Table 2: Benchmark comparison under fixed model (Qwen3-32B), dataset (ShareGPT 18000–18300), and sampling settings. All methods use prefill hidden states only. The Gaussian bound is the ceiling of Propositions 3.3 and 3.4 , averaged over the 300 test prompts, i.e. N1∑iσi2/π and N1∑i[2Φ(τ/σi)−1] ; no prefill-side predictor can exceed it.
σ (tokens)
60
100
150
200
250
300
400
Acc@100 ceiling
90.4%
68.3%
49.5%
38.3%
31.1%
26.1%
19.7%
Acc@200 ceiling
99.9%
95.4%
81.8%
68.3%
57.6%
49.5%
38.3%
Acc@500 ceiling
>99.9 %
>99.9 %
99.9%
98.8%
95.4%
90.4%
78.9%
Table 3: Gaussian Acc@ τ ceiling 2Φ(τ/σ)−1 (Proposition 3.4 ) as a function of the per-prompt standard deviation. A 90% Acc@100 ceiling requires σ≤61 tokens.
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Method
MAE
Acc@100
Acc@200
Acc@500
MLP-Concat
169.3±4.2
48.9±1.1%
71.1±0.9%
94.4±0.3%
EGTP-style
466.8±1.1
14.6±1.0%
25.4±3.0%
61.9±3.3%
MoE-Soft
170.7±6.3
47.9±1.5%
71.0±1.2%
94.2±0.5%
Appendix
Table 4: Mean ± std over 10 runs (Qwen3-32B, ShareGPT).
Large language model inference scheduling allocates requests, batches, compute, and KV-cache memory to balance latency, throughput, and service-level objectives.
Large language models (LLMs) have achieved remarkable success across a wide range of language tasks. At their core, autoregressive LLMs are conditional probability models that learn to approximate the next-token distribution given the preceding context. Despite this probabilistic nature, the stochastic dynamics of autoregressive decoding have rarely been investigated from a rigorous probabilistic perspective. In this work, we define the per-step prediction error as the difference between the sampled token indicator and the model's conditional predictive distribution, and prove that the cumulative error process is a martingale with respect to the decoding filtration, implying that its conditional first-order moment is identically zero. Beyond this first-order property, we derive a closed-form expression for the second-order behavior of the martingale sequence: its predictable quadratic variation reduces to ∑t(1−p(yt∣y<t)), computable from realized token probabilities alone. This identity establishes a direct theoretical connection between sequence fluctuations and predictive uncertainty during autoregressive decoding. White-box experiments on Llama-3.x and Qwen2.5 families (1B to 72B parameters) verify that the empirically measured second-order moments closely match the theoretical predictions derived from our martingale analysis. These results provide a probabilistic framework for analyzing autoregressive LLM decoding, reveal intrinsic probabilistic fingerprints of different language models, and establish a rigorous mathematical foundation for LLM-generated text detection and uncertainty quantification.
Xiahui Zhu, Zhenyi Qi, Wanwei Liu +4
College of Computer, National University of Defense Technology, Changsha, Hunan, China
Concurrent autoregressive inference creates a fundamental interference problem: prefilling a newly arrived long prompt can delay tokens for requests that are already decoding. Fixed prefill chunks reduce this interference, but the best chunk size depends on the model, hardware, load, and latency objective. We introduce Decode-Latency Feedback Prefill (DLFP), a model-free controller that changes only prefill work that overlaps active decodes. After a guarded scheduling cycle, DLFP uses the observed interval as proportional feedback to resize the next prefill chunk; isolated prefills remain unrestricted. We implement DLFP in vLLM and evaluate it with open-loop Poisson arrivals, exact token accounting, raw request traces, and NVIDIA telemetry. On Qwen3-0.6B in BF16 on one A100 80 GB GPU, three paired 100-request trials reduce P99 inter-token latency by 24.8%, 30.1%, and 28.2% (mean 27.7%, paired 95% confidence interval 21.0% to 34.3%) with exact output agreement, no failures, and unchanged SLO compliance. The benefit is not free: mean P99 time to first token increases 34.8% while remaining inside the declared SLO. Crucially, the mechanism does not generalize to Qwen3-8B, Qwen3-32B, or a two-GPU tensor-parallel configuration. We trace the failure to an asynchronous scheduler-call interval that is only a proxy for completed GPU iteration time. This negative result defines the boundary of the contribution and motivates a completion-timed controller for concurrent CPU and on-device inference. We do not claim mobile-device performance; the present work is a reproducible proof-of-concept and generalization study.
The heavy-tailed distribution of output lengths in Large Language Model (LLM) serving poses major challenges for resource provisioning and cluster scheduling. Although output-length prediction can mitigate these issues, existing approaches have key drawbacks: external proxy models add substantial latency and often have limited fidelity, whereas internal state-based methods are efficient but rely on shallow probes of current model states. We identify a structural connection between speculative decoding (SD) and length prediction: latent representations produced by the draft decoder in advanced frameworks (e.g., EAGLE-3) encode signals that are predictive of generation length. Building on this insight, we introduce OUTLETS (Output-Length Prediction from Speculative Decoding Backbones), which repurposes the speculative backbone as a trajectory-aware length predictor. When its draft representations are already computed for speculative decoding, OUTLETS adds only a lightweight regression head and achieves lower MAE than the evaluated methods. Under saturated disaggregated serving, OUTLETS predictions enable standard scheduling policies to prioritize shorter requests and distribute requests more evenly across decoding instances, reducing short-request P99 latency by 34.8%.
Weihuang Wen, Yingying Liu, Yichuan Liu +5
The Chinese University of Hong Kong, Shenzhen · The University of Hong Kong · Huawei Technologies Co., Ltd.