On the Fundamental Limits of Prefill-Based Decoding Length Prediction

1 Introduction

• Decoding-length estimates can inform batch scheduling, PD disaggregation, and resource provisioning because decode dominates end-to-end latency and energy consumption.Prefill processes prompts in parallel, while decode generates tokens autoregressively and is memory-bound.Source: §1 · p. 2
• Reported MAE changes sharply across evaluation settings, which the authors attribute to autoregressive randomness rather than predictor design.The same architecture has MAE ≈80 on ForeLen’s long-sequence split, >150 on ShareGPT, and >260 on RL-sampled data.Source: §1 · p. 2
• A stopping-time model with non-constant hazard yields asymptotic normality, an affine variance law σ = αµ + b, and bounds for every prefill-side predictor.The fitted slope α is the coefficient of variation of the number of response segments; the bounds decompose excess risk into system and model terms.Source: §1 · p. 2
• Per-prompt MAE matches the Gaussian value σ√(2/π) within 1.9%, and central mass matches within two percentage points.The measured residual departures—median skewness +0.27 and excess kurtosis +0.35—are those predicted by the sampling-noise correction.Source: §1 · pp. 2–3
• Under fixed model, data, and sampling settings, MLP, EGTP, FiLM, soft-label, and MoE predictors converge to similar performance near the theoretical bound.The authors argue that existing benchmarks conflate predictor quality with task hardness and recommend controlled evaluation with relative-error metrics alongside absolute ones.Source: §1 · p. 3

Problem formulation

• The target Y is the number of new tokens generated before an end-of-sequence token, and the estimate uses only prefill-observable information.The input prompt is tokenized as x1:L, with layer-wise hidden states computed during prefill.Source: §2 · p. 3

Metrics

• Following prior work [Xie et al., 2026], the evaluation reports MAE, accuracy within token tolerances, and x(p90), the smallest tolerance reaching 90% accuracy.Reported accuracy thresholds include acc@100, acc@200, and acc@500.Source: §2 · p. 3

Feature extraction

• Concatenating layer-wise hidden states gives the richest representation for this task among the pooling strategies described.Common alternatives include mean pooling across layers and tokens or using the last token of the last layer.Source: §2 · p. 3

EGTP and ForeLen

• EGTP uses next-token entropy to weight token hidden states, but ForeLen’s different model–dataset combinations prevent separating its reported gains from task difficulty.ForeLen includes long-sequence, chain-of-thought, and RL-sampling splits; EGTP reports MAE reductions of up to 29.16% over baselines.Source: §2 · p. 4

Other predictors and online prediction

• Other approaches use graph regressors, inference-time side networks, or prompt-text proxy models, while online methods gain access to generated tokens or adapt scheduling over time.The paper distinguishes these online methods from prefill-only bounds because they use a richer information set.Source: §2 · p. 4

3.1 Decoding Length as a Stopping Time

• Decoding length is a stopping time whose law depends on a context-dependent stopping hazard; a constant hazard would imply a geometric length distribution inconsistent with measured σ/µ ≈0.15.A token-level central limit argument is unavailable because the indicators contributing to length are nested, motivating a coarser segment-level model.Source: §3.1 · p. 5

3.2 A Renewal Model and a Central Limit Theorem

• Under the segment-renewal assumption, decode length is asymptotically normal with an explicit Berry–Esseen error term.Conditioned on prompt and segment count, segment lengths are i.i.d. with finite third absolute central moment; the segment count follows a specified stopping-count model.Source: §3.2 · p. 5
• The segment model yields σ = αµ + b, with α = CV(M), and links residual skew to a Gaussian–geometric shape.The paper identifies the stopping ramp and measurements as empirical checks of the assumption and its consequences.Source: §3.2 · p. 6

3.3 Lower Bounds on Prediction Error

• For fixed σ(x), no prefill-side predictor beats the bounds; achieving acc@100 ≥90% requires σ ≤61 tokens, while acc@200 ≥90% requires σ ≤122 tokens.The gap between a predictor and the bound is at most its distance from the oracle mean; single-decode training labels carry variance σ²(x).Source: §3.3 · pp. 6–7
• Averaging per-prompt pass-rate bounds gives 57.9% rather than 46.2% for the §5.3 test set when applying the bound to average σ.The difference arises because the pass-rate bound is strongly nonlinear in σ.Source: §3.3 · pp. 6–7
• For long responses, absolute MAE grows with the data length scale, whereas relative error tends toward an architecture-independent constant fixed by the generation process.This supports reporting relative-error metrics alongside absolute ones.Source: §3.3 · p. 7

3.4 Estimating σ from Finitely Many Decodes

• With K = 200 decodes per prompt, the estimated σ and resulting bounds should be read as accurate to about ±10%.The stated sample-size threshold is K = 193 decodes to estimate σ within 10% at 95% confidence.Source: §3.4 · p. 7

3.5 What Controls σ?

• Across six models on ShareGPT, σ is well described by the affine law, while fitted α and b vary markedly across models and posttraining recipes.Qwen3-4B-Instruct has α = 0.1068, Qwen3-4B-no-thinking has α = 0.2029, and DeepSeek-R1-distilled-thinking has α = 0.1156 and b = 147.6; lower α and b indicate more stable generation.Source: §3.5 · pp. 7–8, Table 1 · p. 8

4.1 Is the Decode Length Normal?

• 79 of 298 prompts pass Shapiro–Wilk and 226 pass Kolmogorov–Smirnov at α = 0.05; the tests differ in sensitivity to small deviations at K = 200.The evaluation uses 300 ShareGPT prompts, each decoded 200 times with Qwen3-32B; two prompts are deterministic.Source: §4.1 · p. 8
• Pooled lengths are slightly peaked and right-skewed, with median skewness +0.27 and excess kurtosis +0.35, matching the predicted sampling-noise correction.The representative prompt’s Q–Q deviations are confined to the extreme tails.Source: §4.1 · p. 9, Figure 1 · p. 10
• 0.783 median per-prompt normalized MAE versus the Gaussian prediction of 0.798 yields a 1.9% gap; central-mass bounds are conservative at tested tolerances.Empirical mass within the tested tolerances exceeds the Gaussian value by 1.1–2.0 percentage points.Source: §4.1 · p. 9

4.2 µ–σ Correlation

• Expected output length and variance correlate positively (Spearman ρ = 0.78), while an MLP’s test-MAE slope of 0.774 is close to the theoretical 0.798.Open-ended questions tend to lie above the length–variance trend, while tightly constrained instructions tend to lie below it.Source: §4.2 · p. 9, §4.3 · p. 9

5.1 Experimental Setup

• The self-test fixes Qwen3-32B, ShareGPT, and sampling settings; 200 decodes for each of 300 test prompts keep per-prompt σ estimates affordable.Prefill features and decode labels came from separate workers, and batching across stages was not strictly controlled.Source: §5.1 · pp. 10–11

5.2 Architectures Evaluated

• Figures 2–4 show a roughly 350-step stopping-hazard ramp, an affine σ–µ trend, and a per-prompt MAE fit that closely tracks the Gaussian lower bound.Source: Figure 2 · p. 11, Figure 3 · p. 12, Figure 4 · p. 12

5.1 Experimental Setup

• Predictor performance is sensitive to training–test domain alignment, while the σ-driven ceiling remains the dominant constraint across settings.Source: §5.1 · p. 11

5.2 Architectures Evaluated

• The evaluated designs include entropy pooling, FiLM conditioning, soft-label classification, and hard-, soft-, and end-to-end MoE variants.All methods use prefill hidden states only.Source: §5.2 · pp. 11–12

5.3 Results

• MLP-Concat matches or beats FiLM, Soft-Label, and all MoE variants; its gap to MoE-Soft (MAE 170.70) is below 1% relative, while EGTP-style pooling reaches MAE 466.79.The comparison uses a fixed Qwen3-32B, ShareGPT, and sampling setup.Source: Table 2 · p. 13, §5.3 · p. 13
• The mean per-prompt σ is 162.3 and the Gaussian floor is 129.5 tokens; the best predictor reaches 168.1, an excess of 38.6 tokens, at most 30% of system error.Single-decode label noise and imperfect test–training distribution alignment account for the residual gap, rather than architecture.Source: §5.3 · pp. 13–14
• The per-prompt-averaged Gaussian ceiling is 57.9% at τ = 100, versus measured Acc@100 of 48.9%; inserting mean σ instead gives 46.2%.The ceiling is averaged across prompts because averaging σ first understates it.Source: §5.3 · p. 14
• Mean σ values of 112 for Llama3-8B and 261 for Qwen3-30B-A3B correspond to easier and harder tasks, respectively; Table 3 tabulates ceilings by σ.Source: §5.3 · p. 14, Table 3 · p. 14

6.1 Toward Fairer Benchmarks

• Different model–dataset combinations have different σ, so cross-combination MAE comparisons confound predictor quality with task difficulty.The recommended protocol fixes the target LLM, dataset, and sampling parameters, reports per-prompt σ or its test-set average and median, and adds relative-error metrics alongside absolute MAE.Source: §6.1 · pp. 14–15

6.2 Runtime Compute Inconsistency

• Separate workers and uncontrolled batch sizes, CUDA kernels, or deterministic settings may make prefill features and decode labels differ at floating-point precision.The authors believe this effect is small relative to σ-driven system error, but it remains uncontrolled; they suggest generating features and labels in one forward pass or fixing runtime determinism flags.Source: §6.2 · p. 15

6.3 PD-Disaggregated Generation

• PD-disaggregated collection separates prefill feature export from decode generation, while single-decode labels amplify label noise compared with means of 200 decodes.The authors identify numerical differences between workers and potentially different batching strategies as practical data-collection constraints to control in future studies.Source: §6.3 · p. 15

6.4 Iterative Prediction as Uncertainty Reduction

• Iterative prediction reduces system error by conditioning on generated tokens, but each update adds encoder latency and memory pressure, making coarse-grained updates a practical compromise.The authors describe prefill-only bounds as a baseline without decode-side overhead and iterative refinement as a way to quantify uncertainty reduction when systems accept that cost.Source: §6.4 · pp. 15–16

7 Conclusion

• A simple MLP lands within 30% of the noise floor, while EGTP, FiLM, Soft-Label, and MoE designs yield marginal or negative returns.The conclusion recommends shifting effort toward controlling generation variance and toward benchmarks that fix model, data, and sampling parameters and report relative errors against the ceiling.Source: §7 · p. 16
• The paper treats decoding as a stopped stochastic process and derives per-prompt normality, an affine variance law, and prefill-side MAE and pass-rate bounds.The conclusion says these bounds are tight empirically and that stochasticity fundamentally constrains prefill-hidden-state prediction.Source: §7 · p. 16

A.1 Hazard Identities and the Geometric Baseline

• Under a constant hazard, decode length is geometric and its irreducible relative MAE approaches 2/e ≈ 0.74, unlike the measured σ/µ ≈ 0.15.Because token-survival indicators are nested rather than independent, token-level stopping does not inherit a central limit theorem over tokens.Source: §A.1 · p. 19

A.2 Proof of Theorem 3.2 and Its Consequences

• The variance decomposition separates within-segment sampling noise from variation in the number of segments, yielding the affine variance law σ = αµ + b.The slope α is the coefficient of variation of the segment count; the intercept collects per-segment noise discounted by 1/(2α).Source: §A.2 · pp. 19–20
• The aggregation index k := (µ/σ)^2 measures effective stopping opportunities; for the prompts analyzed, median σ/µ = 0.145 corresponds to k ≈ 47.The affine slope is tied to the coefficient of variation of the segment count, linking variability in segment count to the scale of decode-length uncertainty.Source: §A.2 · p. 20
• Conditioned on the segment count, the content contribution is a sum of centered i.i.d. segment lengths; the proof combines its normal approximation with the segment-count bound.The sampling term perturbs the characteristic function at order 1/n, and the resulting convergence yields a uniform CDF error bound.Source: §A.2 · pp. 20–21
• The argument reduces token-level stopping-time normality to a segment-count normality assumption, rather than deriving that assumption from scratch.The analysis covers renewal behavior when c = 0 and proportionally fluctuating segment counts when c > 0; its conclusion also holds when M/n → 1 in probability.Source: §A.2 · pp. 20–21

A.3 Proofs and Auxiliary Computations for Section 3.3

• The normal-model absolute-error bound is minimized by predicting the mean, while the pass-rate ceiling depends on length scale through τ/µ.The appendix also notes that averaging per-prompt ceilings matters: in the cited test set, the per-prompt average is 57.9% versus 46.2% when evaluated at the mean σ.Source: §A.3 · pp. 21–22

A.4 The Shape of the Deviations

• The observed median skewness 0.27 and excess kurtosis 0.35 imply a sampling-noise share of about 24–26% of per-prompt variance.The correction assumes a locally flat path-wise hazard near the crossing point; at segment counts around 45, the sampling contribution is small but still measurable.Source: §A.4 · p. 23

A.5 χ2 Confidence Bound for σ

• The confidence calculation requires 193 decodes for a 10% relative-error estimate of σ at 95% confidence, so the study rounds up to 200 per prompt.That cost limits the test set to 300 prompts because exhaustive evaluation on a larger set would be prohibitively expensive.Source: §A.5 · p. 24

• Unless otherwise noted, predictors were implemented in PyTorch and trained with Adam.Source: B Training Details · p. 24
• Training ran for up to 100 epochs, with early stopping on validation MAE after a patience of 10.Source: B Training Details · p. 24
• Inputs were eager-exported prefill hidden states; regression used Smooth-L1, while soft labels used a cross-entropy and MSE mixture.Source: B Training Details · p. 24
• MLP-Concat joins the last-token hidden vectors across layers; for Qwen3-32B, its 327,680-dimensional input feeds 327680 →128 →128 →1 linear maps with ReLU activations.Source: B Training Details · p. 24
• EGTP-style pooling weights prefill hidden states by next-token entropy; FiLM conditions on token count, soft labels smooth 100 bins, and MoE variants route among four overlapping length experts.Source: B Training Details · p. 25

• The reported statistics are computed over 10 independent training runs.Source: C Full Benchmark Results · p. 25
• Table 4 reports mean and standard deviation for the benchmark results.Source: Table 4 · p. 25
• The table covers Qwen3-32B on ShareGPT.Source: Table 4 · p. 25

D Cross-Dataset Generalization

• When training and test domains align closely, MAE is low and accuracy high; substantial mismatch moves MAE toward the test-set σ ceiling.The reported pattern is consistent with residual error being dominated by generation stochasticity once predictors are adequately trained.Source: D Cross-Dataset Generalization · p. 25, Table 5 · p. 26

E MoE Meta-Gate Definitions

• The MoE meta-gate combines features, expert predictions, risk estimates, and interval distances; risk heads learn absolute error, with routing-KL and expert-balance losses.Source: E MoE Meta-Gate Definitions · p. 26