On the Fundamental Limits of Prefill-Based Decoding Length Prediction

Haowen Shi; Xuzhe Yan; Fahao Chen; Peng Li

cs.AIOct 29, 2026

On the Fundamental Limits of Prefill-Based Decoding Length Prediction

Authors: Haowen Shi, Xuzhe Yan, Fahao Chen, Peng Li

Organizations: Xi’an Jiaotong University, Xi’an, China · Shandong University, Jinan, China

Abstract

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	$\alpha$	$\mu$	$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

\sigma

–

\mu

law on ShareGPT (300 prompts

\times

200 decodes). Lower

\alpha

and

b

indicate more stable generation. By Corollary A.3 ,

\alpha=\mathrm{CV}(M)

and

b=\kappa_{1}/(2\alpha)

Figure 1: Normality of decode length (Qwen3-32B, ShareGPT). (a) Q–Q plot for a representative prompt ( $\mu=1946$ , $\sigma=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 $\mathcal{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 $\mu$ ): the hazard ramps from $\approx 0$ to $\approx 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 $\mu$ versus standard deviation $\sigma$ on ShareGPT (Qwen3-32B, 300 prompts $\times$ 200 decodes). The linear trend $\sigma=\alpha\mu+b$ of Corollary A.3 is visible, with outliers reflecting prompt-specific constraints.

Figure 4: Per-prompt test MAE versus per-prompt $\sigma$ (Qwen3-32B, ShareGPT). The linear fit (blue) closely tracks the theoretical lower bound (red, $\mathrm{MAE}_{\min}=\sigma\sqrt{2/\pi}$ ).

Method	MAE $\downarrow$	Acc@100 $\uparrow$	Acc@200 $\uparrow$	Acc@500 $\uparrow$	x(p90) $\downarrow$
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.

\frac{1}{N}\sum_{i}\sigma_{i}\sqrt{2/\pi}

and

\frac{1}{N}\sum_{i}[2\Phi(\tau/\sigma_{i})-1]

; no prefill-side predictor can exceed it.

$\sigma$ (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@

\tau

ceiling

2\Phi(\tau/\sigma)-1

(Proposition 3.4 ) as a function of the per-prompt standard deviation. A

90\%

Acc@100 ceiling requires

\sigma\leq 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\pm 4.2$	$48.9\pm 1.1\%$	$71.1\pm 0.9\%$	$94.4\pm 0.3\%$
EGTP-style	$466.8\pm 1.1$	$14.6\pm 1.0\%$	$25.4\pm 3.0\%$	$61.9\pm 3.3\%$
MoE-Soft	$170.7\pm 6.3$	$47.9\pm 1.5\%$	$71.0\pm 1.2\%$	$94.2\pm 0.5\%$

Appendix

Table 4: Mean

\pm

std over 10 runs (Qwen3-32B, ShareGPT).

Train $\to$ Test	MAE	Acc@100	Acc@200	Acc@500	x(p90)
LMSYS-200K $\to$ ShareGPT-100K	172.60	47.22%	70.89%	94.13%	393.05
LMSYS-200K $\to$ ShareGPT-18k-18.3k	182.40	43.75%	68.44%	92.43%	435.48
LMSYS-200K $\to$ GSM8K	44.33	92.96%	99.04%	99.88%	86.23
ShareGPT-100K $\to$ ShareGPT-10K	132.70	57.76%	80.16%	96.68%	299.96
LeetCode $\to$ HumanEval	29.28	96.28%	100.00%	100.00%	76.17

Appendix

Table 5: Cross-dataset generalization (train

\to

test).

LLM Inference Scheduling

Large language model inference scheduling allocates requests, batches, compute, and KV-cache memory to balance latency, throughput, and service-level objectives.

See all 166 papers

Autoregressive Decoding as a Martingale: Characterizing the Stochastic Dynamics of LLM Generation
Oct 12, 2026Xiahui Zhu, Zhenyi Qi, Wanwei Liu +4Autoregressive Decoding Autoregressive Language Modeling
College of Computer, National University of Defense Technology, Changsha, Hunan, China
Decode-Latency Feedback Prefill: A Model-Free Controller and Its Generalization Limits
Sep 29, 2026Gaurav Agarwal, Ashish Garg, Isha SinghalLLM Serving LLM Inference
OUTLETS: Output-Length Prediction from Speculative Decoding Backbones
Sep 1, 2026Weihuang Wen, Yingying Liu, Yichuan Liu +5LLM Serving LLM Inference Scheduling
The Chinese University of Hong Kong, Shenzhen · The University of Hong Kong · Huawei Technologies Co., Ltd.

Oct 12, 2026J/K move · Enter open · S save

Autoregressive Decoding as a Martingale: Characterizing the Stochastic Dynamics of LLM Generation

Xiahui Zhu, Zhenyi Qi, Wanwei Liu, Haoang Chi+3

College of Computer, National University of Defense Technology, Changsha, Hunan, China

Autoregressive Decoding Autoregressive Language Modeling LLM Uncertainty Estimation

Open paper AskPDF arXiv

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

\sum_t\left(1-p(y_t\mid y_{<t})\right)

, 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.

Abstract

LLM Inference Scheduling

Explore similar work

Autoregressive Decoding as a Martingale: Characterizing the Stochastic Dynamics of LLM Generation

Decode-Latency Feedback Prefill: A Model-Free Controller and Its Generalization Limits

OUTLETS: Output-Length Prediction from Speculative Decoding Backbones