On the Fundamental Limits of Prefill-Based Decoding Length Prediction

What it claims

Haowen Shi, Xuzhe Yan, Fahao Chen and Peng Li (Xi'an Jiaotong and Shandong universities, October 2026) argue that published decode-length predictors cannot be compared. The cause is the randomness of sampling itself. The same predictor architecture reaches MAE ≈ 80 on ForeLen's long-sequence split with Qwen2.5-7B, but exceeds 150 on ShareGPT with Qwen3-32B and 260 on RL-sampled data. No prefill-only predictor can beat MAE = σ·√(2/π) ≈ 0.798σ per prompt, or acc@τ = 2Φ(τ/σ) − 1, where σ is that prompt's decode-length standard deviation. The authors say ForeLen, which reports EGTP gains of up to 29.16%, evaluates methods on different model and dataset pairs, so those gains cannot be separated from task difficulty.

How it works

Decode length is a stopping time over the sampled continuation. A constant per-token stop probability would make length geometric, with σ/µ → 1 and an irreducible relative MAE of about 74%. The measured σ/µ ≈ 0.15 rules this out. Instead, a response is modelled as M segments (sentences, list items, reasoning steps) of i.i.d. length. This one assumption gives asymptotic normality with a Berry–Esseen error term, and the affine law σ = αµ + b, where α is the coefficient of variation of M. Mean squared error splits exactly into system error, E[σ²(x)], and model error, E[(µ(x) − ŷ)²]. Training labels are single decodes rather than µ(x), so the regression target itself carries noise of variance σ².

The bounds give usable thresholds. For acc@100 ≥ 90% on a prompt, σ must be at most 61 tokens. For acc@200 ≥ 90%, σ must be at most 122. For long outputs, the minimum relative MAE tends to 0.798α, a constant set by the model and its sampling, not by the predictor.

Evidence

The test set is 300 ShareGPT prompts, each decoded 200 times with Qwen3-32B (temperature 0.6, top-k 20, top-p 0.95). Two prompts were deterministic. On the other 298:

• The per-prompt E|Y − µ|/σ has a median of 0.783, against the Gaussian 0.798, a 1.9% gap.
• The central mass exceeds the Gaussian by 1.1 to 2.0 points, so the bounds err on the safe side.
• Shapiro–Wilk fails to reject normality for 26.5% of prompts and Kolmogorov–Smirnov for 75.8%. The median skew is +0.27 and the median excess kurtosis +0.35.
• Mean σ is 162.3 and median σ is 133.9. 10% of prompts have σ > 300, and one runaway prompt has CV 0.61.
• The µ–σ Spearman correlation is 0.78.

The fitted α varies widely by model: Qwen3-4B-Instruct 0.1068, DeepSeek-R1-distilled-thinking 0.1156 (with b = 147.6), Qwen3-32B 0.1486, Qwen3-30B-A3B-Instruct 0.1682, Qwen3-4B-no-thinking 0.2029, Llama3-8B 0.2042. MLP, EGTP, FiLM, soft-label and MoE predictors are reported to converge near the bound. On the §5.3 test set, the average of per-prompt acc bounds is 57.9%. Plugging in the mean σ gives 46.2% instead, so per-prompt averaging matters.

How to use it

Code and analysis tools are at https://github.com/ShwStone/DecodingPredict. To estimate σ within 10% at 95% confidence, K = 193 decodes per prompt are needed; the paper uses 200, so its bounds carry about ±10% uncertainty. Before tuning a predictor, measure σ on your own model, data and sampling settings. Report relative MAE next to absolute MAE, and average per-prompt bounds rather than using a mean σ.

Limits

The fetched text stops in §4.2, so the per-architecture predictor numbers from §5 are not shown here. The normality checks use a single model (Qwen3-32B) on ShareGPT only. The bounds apply only to single-shot prefill prediction. Iterative methods such as ELIS, and schedulers that re-prioritize as tokens arrive, see more information and face a smaller σ. Runaway generations, like the outlier prompt above, fall outside what any prefill predictor can anticipate.