betaFeedback

WorksComputer Science

On the Fundamental Limits of Prefill-Based Decoding Length Prediction

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σ=αμ+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.

Introduction

Large language model (LLM) inference consists of two distinct phases: a compute-bound prefill phase that processes the input prompt in parallel, and a memory-bound decode phase that generates output tokens autoregressively [3, 12]. Because the decode phase dominates end-to-end latency and energy consumption [Zhong et al., 2024], knowing how many tokens will be decoded before decoding begins is invaluable for batch scheduling, PD disaggregation, and resource provisioning [8, 7, 13].

Motivated by this need, a growing body of work proposes to predict decoding length from prefill-phase information. Early approaches train external proxy models on surface features [7]. More recent methods reuse the target LLM’s own internal activations: Shahout et al. [ [8] schedule requests with intermediate-layer embeddings; Piotrowski et al. [ [6] build a graph convolutional regressor over layer-wise hidden states; and the concurrent EGTP framework [11] introduces Entropy-Guided Token Pooling (EGTP) over on-the-fly hidden states, achieving state-of-the-art results on the newly released ForeLen benchmark.

The fairness problem. Despite these advances, we observe that published numbers are difficult to compare. A predictor may achieve MAE ≈80\approx80 on ForeLen’s long-sequence split with Qwen2.5-7B, yet the same architecture degrades to MAE >150> 150 on ShareGPT with Qwen3-32B, or to MAE >260> 260 on RL-sampled data. The root cause is that the inherent randomness of autoregressive generation—not predictor design—is the dominant error source. When a query has high decode-length variance, no prefill-side predictor can forecast a single deterministic length with high accuracy, because the length itself is a random variable.

Our contributions. We make three contributions.

  1. A theory of where the error comes from. We model decoding as a stopping time with a non-constant hazard and show that the decode length is asymptotically normal, with an explicit Berry–Esseen error term (§ 3). The same analysis yields the affine variance law σ=αμ+b\sigma= \alpha\mu+ b and identifies the fitted slope as the coefficient of variation of the number of response segments. From the normal law we then derive bounds that hold for every prefill-side predictor, including sharpened MAE and pass-rate bounds and an exact decomposition of the excess risk into a system and a model term.

  1. Empirical validation, including where the law fails. On 300 ShareGPT prompts with 200 decodes each, we test the normal approximation against the quantities that the bounds actually use: the per-prompt MAE matches the Gaussian value σ2/π\sigma\sqrt{2/\pi} to within 1.9%, and the central mass matches to within two percentage points (§ 4).

The residual departures from normality (median skewness +0.27, excess kurtosis +0.35) are those predicted by the sampling-noise correction of our analysis. We also confirm that σ\sigma follows the affine law in μ\mu, with coefficients (α,b)(\alpha, b) that vary markedly across models and posttraining recipes (Table 1).

Modelα\alphaμ\mubb
Qwen3-4B-no-thinking0.2029814.255.56
Qwen3-4B-Instruct0.10681443.2831.25
DeepSeek-R1-distilled-thinking0.1156676.00147.60
Llama3-8B0.2042555.23−1.39-1.39
Qwen3-32B0.1486907.9227.36
Qwen3-30B-A3B-Instruct0.16821479.7812.18

Table 1. Per-model σ\sigma–μ\mu law on ShareGPT (300 prompts ×\times 200 decodes). Lower α\alpha and bb indicate more stable generation. By Corollary A.3, α=CV⁡(M)\alpha= \operatorname{CV}(M) and b=κ1/(2α)b = \kappa_1/(2\alpha).

  1. Architecture-agnostic evaluation. We benchmark a wide range of predictor designs—MLP regression on concatenated hidden states, EGTP-style entropy pooling, FiLM conditioning, soft-label classification, and MoE routing—under fixed model, data, and sampling settings. All methods converge to similar performance close to the theoretical bound (§ 5).

Finally, we argue that existing benchmarks such as ForeLen conflate predictor quality with task hardness, and we recommend a controlled evaluation protocol that reports relative-error metrics alongside absolute ones (§ 6).

Preliminaries and Related Work

Problem formulation. Let a prompt xx be tokenized into x1:Lx_{1:L}, and let h1:L(l)\mathbf{h}_{1:L}^{(l)} denote the hidden states of layer ll, for l∈[Lmodel]l \in[L_{\mathrm{model}}], computed during prefill. Let YY be the number of new tokens decoded before the model emits an end-of-sequence (EOS) token, and let y^=f(x,{h1:L(l)}l)\hat{y}=f\left(x,\{\mathbf{h}_{1:L}^{(l)}\}_{l}\right) be an estimate of YY that uses prefill-observable information only.

Metrics. Following prior work [11], we report the mean absolute error (MAE =1N∑i∣y^i−Yi∣= \frac{1}{N}\sum_i |\hat{y}_i-Y_i|) and the pass-rate accuracy at tolerance τ\tau,

acc⁡@τ:=Pr⁡(∣y^−Y∣<τ),(1)\operatorname{acc}@\tau:= \Pr\left(|\hat{y}-Y|<\tau\right), \tag*{(1)}

that is, the fraction of test prompts whose prediction error is below τ\tau tokens. We report acc⁡@100\operatorname{acc}@100, acc⁡@200\operatorname{acc}@200, acc⁡@500\operatorname{acc}@500, and x(p90)x(p90), the smallest τ\tau for which acc⁡@τ≥90%\operatorname{acc}@\tau\ge90\%.

Feature extraction. Most embedding-based methods pool the layer-wise hidden states into a fixed-dimensional vector. Common strategies are mean pooling over layers and tokens, taking the last token of the last layer, or concatenating all layers [8, 11]. Consistent with prior observations on sentence embeddings [2, 4], we find that concatenating all layers gives the richest representation for this task.

EGTP and ForeLen. Xie et al. [ [11] propose Entropy-Guided Token Pooling (EGTP), which computes a per-token entropy HiH_i from the next-token distribution and uses softmax⁡(H)\operatorname{softmax}(H) as attention weights to pool hidden states. They introduce ForeLen, a benchmark with three splits (long sequences, chain-of-thought reasoning, and RL sampling), and report MAE reductions of up to 29.16% over baselines. EGTP is an appealing feature-engineering technique, but ForeLen evaluates different methods on different model–dataset combinations, so the reported gains cannot be separated from differences in task difficulty.

Other predictors. Piotrowski et al. [ [6] treat layer-wise hidden states as a graph and apply a GCN regressor. Zheng et al. [ [13] predict the length with a lightweight side network inserted at inference time. Qiu et al. [ [7] train a separate proxy model on the prompt text alone. Our work differs from all of these in targeting the fundamental limits that they share.

Iterative and online prediction. All of the above methods make a single prediction before decoding begins. A complementary line of work updates the estimate as partial output becomes available. Choi et al. [ [1] propose ELIS, which feeds the prompt plus the already-generated tokens into a BGE-based predictor at fixed intervals (e.g. every 50 tokens) and shows that MAE decreases monotonically as more context is revealed. Wu et al. [ [10] take a different route: instead of predicting the length, they estimate the remaining time adaptively with a skip-join MLFQ scheduler that re-prioritizes jobs at every iteration. Neither approach contradicts our prefill-side bounds: they operate on a richer information set (xx and y<ty_{<t}) and therefore face a smaller effective σ\sigma. We discuss their implications in § 6.4.

Theoretical Analysis of Prediction Error

This section isolates the part of the prediction error that no predictor can remove. We first describe decoding as a stopped stochastic process and record exact hazard identities (§ 3.1). We then give a mechanistic model of how a response acquires its length, from which normality of the decode length follows as a theorem rather than as an assumption (§ 3.2). Finally we translate that law into bounds valid for every prefill-side predictor (§ 3.3) and identify what controls the per-prompt standard deviation (§ 3.5). To keep the exposition short, all proofs and derivations are deferred to Appendix § 8: the main text states each result, gives a one-line proof idea where useful, and points to the full argument.

Decoding Length as a Stopping Time

Fix a prompt xx, a target model, and a sampling configuration. Decoding draws y1,y2,…y_1,y_2,\ldots from the model’s next-token distribution and stops at

Y=min⁡{t≥1:yt∈S},(2)Y = \min\{t \ge1 : y_t \in\mathcal{S}\}, \tag*{(2)}

where S\mathcal{S} is the set of stop tokens (EOS together with any configured stop strings). Hence YY is a stopping time of the sampling process, and its randomness is exactly the randomness of the sampled continuation. Its law is governed by the stopping probability (discrete hazard) and the survival function

pt=Pr⁡(Y=t∣Y≥t,x),St=Pr⁡(Y≥t∣x)=∏s=1t−1(1−ps),(3)p_t = \Pr(Y=t \mid Y\ge t,x), \qquad S_t = \Pr(Y\ge t \mid x) = \prod_{s=1}^{t-1}(1-p_s), \tag*{(3)}

with S1=1S_1=1 and Pr⁡(Y=t∣x)=Stpt\Pr(Y=t\mid x)=S_tp_t. The hazard is itself random, because the sampled context decides how likely the model is to stop at step tt.

Appendix § 8.§ 1 records the exact moment identities implied by (3) and shows that a constant hazard would make YY geometric, with σ/μ→1\sigma/\mu\to1 and hence an irreducible relative MAE of about 74%; the measured σ/μ≈0.15\sigma/\mu\approx0.15 (§ 4) rules that model out. Moreover, since the indicators 1{Y≥t}1\{Y\ge t\} that sum to YY are nested rather than independent, normality cannot be inherited from a central limit theorem over tokens: it has to come from a coarser level, which is the subject of § 3.2.

A Renewal Model and a Central Limit Theorem

A long response is not one uninterrupted decision: it is a concatenation of segments—sentences, list items, clauses, or reasoning steps—each completed before the model decides whether to continue.

Assumption 3.1 (Segment (renewal) structure). Conditionally on xx, the response splits into MM segments of lengths L1,…,LML_1,\ldots,L_M such that (i) given MM and xx, the LiL_i are i.i.d. with mean mm, variance vv, and finite third absolute central moment ρ\rho; (ii) MM is a stopping count of the segment-level continuation process, independent of the LiL_i, with E[M]=n\mathbb{E}[M]=n and Var⁡(M)=c2n2+c1n\operatorname{Var}(M)=c^2n^2+c_1n for constants c,c1≥0c,c_1\ge0. Then Y=∑i=1MLiY=\sum_{i=1}^{M}L_i.*

Theorem 3.2 (Normality of the decode length). Under Assumption 3.1, let μ=mn\mu=mn, σ2=vn+m2Var⁡(M)\sigma^2=vn+m^2\operatorname{Var}(M), and ρM=E∣M−n∣3/Var⁡(M)3/2\rho_M=\mathbb{E}|M-n|^3/\operatorname{Var}(M)^{3/2}. Suppose moreover that MM satisfies a Berry–Esseen bound at rate n−1/2n^{-1/2}, i.e.

sup⁡u∈R∣Pr⁡(M−nVar⁡(M)≤u)−Φ(u)∣≤CMρMn−1/2.\sup_{u\in\mathbb{R}}\left|\Pr\left(\frac{M-n}{\sqrt{\operatorname{Var}(M)}}\le u\right)-\Phi(u)\right|\le C_M\rho_Mn^{-1/2}.

Then there is a constant CC such that

sup⁡u∈R∣Pr⁡(Y−μσ≤u∣x)−Φ(u)∣≤Cn(ρM+vmc),(4)\sup_{u\in\mathbb{R}}\left|\Pr\left(\frac{Y-\mu}{\sigma}\le u\mid x\right)-\Phi(u)\right|\le\frac{C}{\sqrt{n}}\left(\rho_M+\frac{\sqrt{v}}{mc}\right), \tag*{(4)}

and hence (Y−μ)/σ⇒N(0,1)(Y-\mu)/\sigma\Rightarrow N(0,1) as n→∞n\to\infty.

Assumption 3.1 is the only statistical assumption of the paper, and it is deliberately coarse: it constrains a segment count rather than token-level behaviour. Appendix § 8.§ 2 proves the theorem, discusses the regimes c=0c = 0 (renewal count) and c>0c > 0 (proportionally fluctuating segment count), and derives the consequences used below: the affine variance law σ=αμ+b\sigma= \alpha\mu+ b with α=CV⁡(M)\alpha= \operatorname{CV}(M) (Corollary A.3); the aggregation index σ/μ≥c\sigma/\mu\ge c, with k:=(μ/σ)2k := (\mu/\sigma)^2 effective stopping opportunities (Corollary A.4); and the Gaussian–geometric shape of the residual skew (Remark A.5). The stopping ramp of Figure 2 and the measurements of § 4 check the assumption and its consequences empirically.

The stopping process of the prompt

Figure 2. The stopping process of the prompt in Figure 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 tt, i.e. the stopping probability increases with length. (b) Bin-wise stopping probability (bin width 5% of μ\mu): the hazard ramps from ≈0\approx0 to ≈1\approx1 over roughly 350 steps, which is the aggregation that Theorem 3.2 requires and Remark A.2 rules out.

Lower Bounds on Prediction Error

Theorem 3.2 justifies the working model

Y∣x∼N(μ(x),σ2(x)),(5)Y \mid x \sim\mathcal{N}\left(\mu(x),\sigma^2(x)\right), \tag*{(5)}

up to the correction quantified in (4). We now derive what this law implies for any predictor y^=f(x)\hat{y} = f(x) that sees prefill-phase information only, and is therefore independent of the decoding noise given xx.

Proposition 3.3 (Irreducible MAE). For Y∼N(μ,σ2)Y \sim\mathcal{N}(\mu,\sigma^2),

inf⁡y^∈RE∣Y−y^∣=E∣Y−μ∣=σ2π≈0.7979 σ,(6)\inf_{\hat{y}\in\mathbb{R}} \mathbb{E}\lvert Y-\hat{y}\rvert= \mathbb{E}\lvert Y-\mu\rvert= \sigma\sqrt{\frac{2}{\pi}} \approx0.7979\,\sigma, \tag*{(6)}

and the infimum is attained uniquely at y^=μ\hat{y} = \mu.

Proposition 3.4 (Maximal pass-rate accuracy). For every tolerance τ>0\tau> 0 and every y^∈R\hat{y} \in\mathbb{R},

acc⁡@τ=Pr⁡(∣Y−y^∣<τ)≤2Φ(τσ)−1,(7)\operatorname{acc}@\tau= \Pr(\lvert Y-\hat{y}\rvert< \tau) \le2\Phi\left(\frac{\tau}{\sigma}\right)-1, \tag*{(7)}

where Φ\Phi is the standard normal CDF.

Proposition 3.3 follows by differentiating y^↦E∣Y−y^∣\hat{y} \mapsto\mathbb{E}\lvert Y-\hat{y}\rvert and Proposition 3.4 from a layer-cake (rearrangement) argument over intervals of length 2τ2\tau; both extrema are attained uniquely at y^=μ\hat{y} = \mu, so the statements concern the best possible predictor rather than the mean predictor (Appendix § 8.§ 3).

Propositions 3.3 and 3.4 state that, once σ(x)\sigma(x) is fixed, no prefill-side predictor can do better: the bounds hold equally for MLPs, graph regressors, entropy-weighted pooling, and mixtures of experts. Concretely, acc⁡@100≥90%\operatorname{acc}@100 \ge90\% for a single prompt requires σ≤100/Φ−1(0.95)=61\sigma\le100/\Phi^{-1}(0.95) = 61 tokens and acc⁡@200≥90%\operatorname{acc}@200 \ge90\% requires σ≤122\sigma\le122 tokens; above these thresholds high accuracy is impossible, whatever the capacity or the amount of training data.

A test set aggregates prompts with different σ\sigma. Because σ↦2Φ(τ/σ)−1\sigma\mapsto2\Phi(\tau/\sigma)-1 is strongly nonlinear, averaging the per-prompt bounds and inserting σˉ\bar{\sigma} differs materially—57.9% versus 46.2% for the test set of § 5.3; we therefore always report the average of the per-prompt bounds (the curvature of the map is computed in Appendix § 8.§ 3).

Proposition 3.5 (Excess risk). For any predictor y^=f(x)\hat{y}=f(x),

E[(Y−y^)2]=E[σ2(x)]⏟system error+E[(μ(x)−y^)2]⏟model error,(8)\mathbb{E}\left[(Y-\hat{y})^2\right]=\underbrace{\mathbb{E}\left[\sigma^2(x)\right]}_{\text{system error}}+\underbrace{\mathbb{E}\left[(\mu(x)-\hat{y})^2\right]}_{\text{model error}}, \tag*{(8)}
E[∣Y−y^∣]≤E[σ(x)2/π]+E[∣μ(x)−y^∣].(9)\mathbb{E}\left[|Y-\hat{y}|\right]\leq\mathbb{E}\left[\sigma(x)\sqrt{2/\pi}\right]+\mathbb{E}\left[|\mu(x)-\hat{y}|\right]. \tag*{(9)}

(8) is the law of total variance and (9) the triangle inequality applied prompt-wise (Appendix § 8.§ 3). Thus the gap between a predictor and the bound is at most its distance to the oracle mean μ(x)\mu(x), and since training labels are single decodes rather than the means μ(x)\mu(x), the regression target carries noise of variance σ2(x)\sigma^2(x), which slows learning at finite NN—the residual gap observed in § 5.3.

Corollary 3.6 (Relative-error metrics are the right currency). Under the affine law (18), for long responses (μ≫b/α\mu\gg b/\alpha),

MAEmin⁡μ⟶α2π≈0.798α,acc@100max⁡⟶2Φ(100αμ)−1.(10)\frac{\mathrm{MAE}_{\min}}{\mu}\longrightarrow\alpha\sqrt{\frac{2}{\pi}}\approx0.798\alpha,\qquad\mathrm{acc@100}_{\max}\longrightarrow2\Phi\left(\frac{100}{\alpha\mu}\right)-1. \tag*{(10)}

Absolute MAE therefore grows without bound with the length scale of the data, whereas the relative error tends to a stable, architecture-independent constant fixed by the generation process—the formal justification for the reporting protocol of § 6.1.

Estimating σ\sigma from Finitely Many Decodes

In practice σ\sigma is unobserved: we see only KK decodes per prompt. With Y1,…,YK∼N(μ,σ2)Y_1,\ldots,Y_K\sim N(\mu,\sigma^2) i.i.d. the sample variance satisfies (K−1)S2/σ2∼χK−12(K-1)S^2/\sigma^2\sim\chi^2_{K-1}, so requiring SS to estimate σ\sigma within 10% at 95% confidence amounts to the two simultaneous inequalities

χK−1,0.0252≥0.81(K−1)andχK−1,0.9752≤1.21(K−1),(11)\chi^2_{K-1,0.025}\geq0.81(K-1)\quad\text{and}\quad\chi^2_{K-1,0.975}\leq1.21(K-1), \tag*{(11)}

which first hold at K=193K=193 (Appendix § 8.§ 5); we use K=200K=200 decodes per prompt. All bounds reported below should therefore be read as accurate to about ±10%\pm10\% in σ\sigma, hence ±10%\pm10\% in the bound itself.

What Controls σ\sigma?

Empirically, σ\sigma is strongly correlated with the mean length μ\mu. Across six models evaluated on ShareGPT prompts, the relation is well described by the affine model derived in Appendix § 8.§ 2 (Corollary A.3):

σ=αμ+b.(12)\sigma=\alpha\mu+b. \tag*{(12)}

Table 1 reports (α,b)(\alpha, b) for each model. The spread is large: Qwen3-4B-Instruct is comparatively stable (α=0.1068)(\alpha= 0.1068), whereas Qwen3-4B-no-thinking is not (α=0.2029)(\alpha= 0.2029). DeepSeek-R1-distilled-thinking combines a low slope (α=0.1156)(\alpha= 0.1156) with an unusually large intercept (b=147.6)(b = 147.6), reflecting the exploratory randomness intrinsic to chain-of-thought generation even when the final answer is short. Since α≈CV⁡(M)\alpha\approx\operatorname{CV}(M), the fitted slopes say that a long answer to a ShareGPT prompt is worth roughly 1/α2≈251/\alpha^2 \approx25–9090 effectively independent stopping opportunities.

Empirical Validation

Is the Decode Length Normal?

We sample 300 prompts from ShareGPT and decode each K=200K = 200 times with Qwen3-32B, using the model’s recommended sampling configuration (temperature 0.6, top-kk 20, top-pp 0.95) so that the length law reflects deployment. Two of the 300 prompts are deterministic (all 200 decodes return the same 8-token answer); there σ=0\sigma= 0 and every statement below holds trivially. The remaining 298 prompts yield 200 lengths each.

A single pp-value is a poor summary at K=200K = 200, since tests reject minuscule deviations once the sample is large. We therefore report three complementary diagnostics: how often normality is rejected, the size and direction of the deviations (standardized skewness and excess kurtosis), and—most importantly—how accurately the Gaussian law reproduces the quantities that the bounds actually use.

Rejection rates. Shapiro–Wilk does not reject normality at α=0.05\alpha= 0.05 for 79 of the 298 prompts (26.5%), while Kolmogorov–Smirnov does not reject for 226 (75.8%). The gap reflects how sensitive Shapiro–Wilk is to tiny deviations at K=200K = 200.

Effect sizes. The deviations are small and systematic rather than arbitrary: the median standardized skewness is +0.27+0.27 (70.8% of prompts are right-skewed) and the median excess kurtosis is +0.35; 58% of prompts have ∣skew⁡∣<0.5|\operatorname{skew}| < 0.5 and 69% have ∣kurt⁡∣<1|\operatorname{kurt}| < 1. Pooling all 59,600 standardized lengths (Y−μ^)/σ^(Y-\hat{\mu})/\hat{\sigma} gives skewness 0.34, excess kurtosis 1.48, and a Kolmogorov–Smirnov distance of 0.019 from N(0,1)\mathcal{N}(0,1). This is precisely the correction predicted by Remark A.5: a Gaussian bulk plus a small right-skewed sampling component. Solving (32) for the observed medians gives r=0.60r=0.60 (from the skewness) and r=0.57r=0.57 (from the kurtosis), i.e. a mutually consistent decomposition with about a quarter of the variance in sampling noise.

Accuracy where it matters. The per-prompt mean absolute deviation in units of σ\sigma is E∣Y−μ∣/σ=0.783\mathbb{E}|Y-\mu|/\sigma=0.783 (median over prompts), against the Gaussian prediction 2/π=0.798\sqrt{2/\pi}=0.798: the bound of Proposition 3.3 is accurate to 1.9% and slightly conservative. Likewise, the empirical probability mass within τ/σ∈{0.625,1,1.28,1.645}\tau/\sigma\in\{0.625,1,1.28,1.645\} exceeds the Gaussian value by 1.1, 1.7, 2.0 and 1.1 percentage points, respectively, so the bound of Proposition 3.4 errs on the safe side at the tolerances of interest. The normal model is thus not a convenient fiction: it is accurate to a few percent exactly where the bounds rely on it. The most visible exception is a genuine outlier prompt (CV 0.61, skewness 9.1), a runaway generation that no prefill-side predictor can anticipate; more generally the distribution of σ\sigma is right-tailed (10% of prompts have σ>300\sigma>300), which is why we report both the mean σ\sigma (162.3) and the median (133.9) whenever ceilings are quoted.

Figure 1(a) shows the Q–Q plot of a representative long prompt and Figure 1(b) the pooled standardized law. Figure 2 displays the same prompt’s survival curve on a log scale, which is markedly not the straight line implied by a constant hazard, together with the stopping ramp that the CLT argument of § 3.2 relies on.

Normality of decode length

Figure 1. Normality of decode length (Qwen3-32B, ShareGPT). (a) Q–Q plot for a representative prompt (μ=1946\mu= 1946, σ=217\sigma= 217, K=200K = 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)\mathcal{N}(0,1): a slightly peaked, slightly right-skewed Gaussian, as predicted by Remark A.5.

Correlation

Figure 3 plots per-prompt (μ,σ)(\mu,\sigma) pairs. The positive correlation is evident (Spearman ρ=0.78\rho=0.78): longer expected outputs carry larger variance, as Corollary A.3 predicts. Outliers above the trend line are open-ended questions (e.g. “do you have reference text book. . . ”), while outliers below are tightly constrained instructions (e.g. code refactoring with prescribed variable names).

Per-prompt mean versus standard deviation on ShareGPT

Figure 3. Per-prompt mean μ\mu versus standard deviation σ\sigma on ShareGPT (Qwen3-32B, 300 prompts ×\times 200 decodes). The linear trend σ=αμ+b\sigma= \alpha\mu+ b of Corollary A.3 is visible, with outliers reflecting prompt-specific constraints.

MAE versus

We train a simple 3-layer MLP on concatenated prefill hidden states and evaluate its per-prompt MAE on the same 300 ShareGPT prompts. Figure 4 plots the test MAE against σ\sigma. The fitted slope is 0.774, close to the theoretical slope 2/π≈0.798\sqrt{2/\pi}\approx0.798 of Proposition 3.3. In other words, the predictor is not the bottleneck: its error is the stochastic floor plus a small offset.

Per-prompt test MAE versus per-prompt standard deviation

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

Predictor Architectures and Results

Experimental Setup

Primary evaluation (ShareGPT self-test). Our main experiments use ShareGPT as both training and test source. Prompts with IDs 0–18000 (≈18K prompts) form the training and validation set, and prompts 18000–18300 (exactly 300) form the test set. All experiments fix the target model to Qwen3-32B (no-thinking mode) with its recommended sampling parameters (temperature 0.6, top-kk 20, top-pp 0.95), so that generation matches deployment conditions. Prefill hidden states are exported once per prompt, and decode metadata is produced with the same model configuration. When evaluating other models (Llama3-8B, Qwen3-4B, DeepSeek-R1-distilled), we likewise adopt each model’s own default sampling configuration.

Why only 300 test prompts? Testing our framework requires an accurate per-prompt estimate of σ\sigma. As shown in § 3.4, estimating σ\sigma to within 10% at 95% confidence requires K≥193K \ge193 repeated decodes, and we use K=200K = 200; with 200 decodes per test prompt, the test set must stay small for the evaluation to be affordable. The training set, in contrast, uses single-shot decode labels, which suffice for fitting a predictor.

Cross-dataset generalization. Beyond the ShareGPT self-test we ran cross-dataset experiments (Appendix § 11). For example, training on LMSYS-200K and testing on ShareGPT 18000–18300 yields MAE 182.40, and training on LeetCode and testing on HumanEval yields MAE 29.28 with acc@100 =

96.28%. Predictor performance is thus highly sensitive to domain alignment between training and test, while the σ\sigma-driven ceiling remains the dominant constraint in every setting.

Data generation caveat. For resource reasons, prefill hidden states and length labels were produced by a PD-disaggregated pipeline: features were computed on prefill nodes and labels on separate decode workers. Batching, and hence low-level numerical behaviour, was not strictly controlled across the two stages; we return to this limitation in § 6.

Architectures Evaluated

We evaluate the following predictor designs, all of which see prefill hidden states only:

  • MLP-Concat: concatenate the last-token hidden vector of all layers (∼100k\sim100\mathrm{k} dims) and regress through a 3-layer MLP (hidden width 128). This is our simplest baseline.

  • MLP-Mean: mean-pool hidden states across layers and tokens, then MLP regression.

  • EGTP-style: compute a per-token entropy from the next-token logits, softmax-normalize it into attention weights, and weighted-pool the hidden states [11]; MLP regression on the pooled vector.

  • FiLM: treat the prefill token count as a conditioning signal and use a FiLM generator [5] to modulate the hidden representation before regression.

  • Soft-Label: discretize lengths into 50 or 100 bins, train a classification head with Gaussian-smoothed targets, and map the expected bin back to a continuous length.

  • MoE-Hard: train 4 expert regressors on length-based splits, with a hard gate classifier [9] selecting one expert.

  • MoE-Soft: the same experts, with a soft gate that averages their predictions.

  • MoE-E2E: end-to-end joint training of gate and experts with an auxiliary routing loss.

Results

Table 2 reports MAE and pass-rate metrics. Several findings stand out.

MethodMAE ↓Acc@100 ↑Acc@200 ↑Acc@500 ↑x(p90) ↓
MLP-Mean181.2145.07%68.91%93.51%402.78
MLP-Concat169.3148.91%71.11%94.35%391.09
MLP-Concat + LayerNorm168.1348.63%71.65%94.45%392.13
EGTP-style466.7914.58%25.35%61.86%891.48
FiLM192.6938.30%–––
Soft-Label (50 bins)183.2445.05%–––
Soft-Label (100 bins)180.1546.10%69.83%93.42%413.24
MoE-Hard177.9146.54%69.77%93.35%418.52
MoE-Soft170.7047.86%71.00%94.19%393.70
MoE-E2E171.3947.33%71.01%94.30%–
Theoretical bound129.557.9%79.7%96.5%–

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. 1N∑iσi2π\frac{1}{N}\sum_i \sigma_i\sqrt{\frac{2}{\pi}} and 1N∑i[2Φ(τ/σi)−1]\frac{1}{N}\sum_i[2\Phi(\tau/\sigma_i)-1]; no prefill-side predictor can exceed it.

Finding 1: simple is competitive. MLP-Concat matches or beats FiLM, Soft-Label, and all MoE variants; the gap to the best MoE variant (MoE-Soft, MAE 170.70) is below 1% relative. Notably, EGTP-style entropy-guided pooling [11] degrades to MAE 466.79 on this split, far behind even the simplest MLP-Mean baseline, which suggests that entropy-weighted aggregation can inject noise when the token-level entropy distribution does not align with the length-predictive signal.

Finding 2: the ceiling is tight and the residual gap is model error. The mean per-prompt σ\sigma is 162.3 (median 133.9; the σ\sigma distribution is right-tailed, with 10% of prompts above σ=300\sigma= 300), so the Gaussian floor is 129.5 tokens. Our best predictor achieves 168.1, an excess of 38.6 tokens. By Proposition 3.5 this excess is an upper bound on the model error E∣μ(x)−y^∣\mathbb{E}|\mu(x)-\hat{y}|, i.e. at most 30% of the system error E[σ(x)]2/π\mathbb{E}[\sigma(x)]\sqrt{2/\pi}. Two effects account for it: training labels are single decodes and therefore carry noise of variance σ2(x)\sigma^2(x) (Proposition 3.5), and the test prompts are not perfectly aligned with the training distribution. Neither is architectural, which is consistent with architectures that differ by orders of magnitude in complexity landing within a few percent of each other.

Finding 3: 90% Acc@100 is unattainable, and the shortfall is quantifiable. The per-prompt-averaged Gaussian ceiling is 57.9% at τ=100\tau= 100 (79.7% at τ=200\tau= 200, 96.5% at τ=500\tau= 500). Measured Acc@100 tops out at 48.9%, i.e. 8.9 points (or 15% relatively) below the ceiling, and measured Acc@500 reaches 94.5% against a ceiling of 96.5%. Reporting accuracy relative to the ceiling is therefore far more informative than the bare percentage (§ 6.1). Inserting the mean σˉ=162.3\bar{\sigma} = 162.3 into (7) instead of averaging per-prompt bounds would give 46.2% and understate the ceiling by 12 points, which is why we always average the per-prompt bounds.

The same arithmetic explains the other models. Llama3-8B (σˉ=112\bar{\sigma} = 112) and Qwen3-30B-A3B (σˉ=261\bar{\sigma} = 261) face much easier and much harder tasks respectively; Table 3 tabulates the resulting ceiling once, as a function of σ\sigma, so that any predictor can be placed against it without re-deriving the bound.

σ\sigma (tokens)60100150200250300400
Acc@100 ceiling90.4%68.3%49.5%38.3%31.1%26.1%19.7%
Acc@200 ceiling99.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Φ(τ/σ)−12\Phi(\tau/\sigma)-1 (Proposition 3.4) as a function of the per-prompt standard deviation. A 90% Acc@100 ceiling requires σ≤61\sigma\le61 tokens.

Discussion

Toward Fairer Benchmarks

The ForeLen benchmark [11] evaluates different methods on different model–dataset combinations (e.g. Qwen2.5-7B on long sequences, Llama3.2-3B on RL sampling). Because each combination has its own σ\sigma, the reported MAE differences confound predictor quality with task hardness. We recommend that future benchmarks

  1. fix the target LLM, the dataset, and the sampling parameters when comparing predictors;

  1. report the per-prompt σ\sigma (or at least its average and median over the test set), so that absolute MAE values can be read against the bound of Propositions 3.3 and 3.4;

  1. adopt relative-error metrics (MAE/μ\mu, or pass rates expressed as a fraction of the ceiling 2Φ(τ/σ)−12\Phi(\tau/\sigma)-1) alongside absolute MAE, since Corollary

lary 3.6 shows that only the former is stable under changes of the length scale.

Runtime Compute Inconsistency

Our prefill features and decode labels were produced by separate pipeline stages on different workers, without strict control of batch size, CUDA kernel versions, or deterministic mode. The hidden states used as features and those that produced the labels may therefore differ at the floating-point level. We believe this effect is small relative to the σ\sigma-driven system error, but it remains uncontrolled. Future work should generate features and labels in the same forward pass, or at least fix all runtime determinism flags.

PD-Disaggregated Generation

To obtain labels at scale we used a PD-disaggregated serving setup [Zhong et al., 2024] in which prefill nodes export hidden states and KV caches while decode nodes generate completions. The separation introduces two potential biases: numerical differences between prefill and decode workers (as above), and possibly different batching strategies on the two sides. Since our training labels are single decodes rather than means of 200 decodes, label noise is amplified further. These are practical constraints of large-scale data collection; they should be acknowledged and, ideally, controlled in future studies.

Iterative Prediction as Uncertainty Reduction

Our analysis assumes that the predictor sees prefill-phase information only. This is the hardest regime, because Var⁡(Y∣x)\operatorname{Var}(Y \mid x) is then as large as it can be. Once decoding begins, every generated token yty_t carries information about the remaining length, and the posterior variance can only shrink: Var⁡(Y∣x,y<t)≤Var⁡(Y∣x)\operatorname{Var}(Y \mid x,y_{<t}) \le\operatorname{Var}(Y \mid x), strictly so for most prompts. Choi et al. [ [1] exploit this by re-running a BGE-based predictor at fixed intervals during decoding and report that MAE decreases monotonically as more tokens are observed.

Theoretically, iterative prediction is the most effective way to reduce uncertainty without changing the generation process. Prefill-side feature engineering can only shrink the model error of Proposition 3.5, whereas iterative prediction shrinks the system error by reducing the conditional variance of the target. In the limit where the predictor is invoked after every token, the remaining length collapses to a near-deterministic countdown and the MAE bound tends to zero.

The price is runtime cost: each prediction requires an encoder forward pass, adding latency and memory pressure to the serving system. For scheduling applications that consume prefill-side estimates to batch requests, this overhead is often acceptable only for coarse-grained updates (e.g. every 50–100 tokens). We therefore view prefill-only bounds and iterative refinement as complementary: the former set the baseline achievable without decode-side overhead, the latter quantify the uncertainty reduction available to systems that are willing to pay for it.

Conclusion

We have shown that decoding-length prediction from prefill hidden states is fundamentally constrained by the stochasticity of autoregressive generation. Treating decoding as a stopping time and modelling the growth of a response as a renewal process yields per-prompt normality with an explicit error term, the affine variance law σ=αμ+b\sigma= \alpha\mu+ b, and lower bounds on MAE and pass-rate accuracy that no prefill-side predictor can beat. Empirically these bounds are tight: a simple MLP already lands within 30% of the noise floor, while more elaborate designs (EGTP, FiLM, Soft-Label, MoE) yield marginal or negative returns. The implication is that effort should shift from ever more complex predictors toward (i) controlling the variance of the generation process itself—through lower-temperature sampling, constrained decoding, or prompt design—and (ii) benchmarking protocols that fix the model, data, and sampling parameters and report relative errors against the ceiling.

Code availability. All code for data generation, model training, and evaluation, together with the prefill feature extraction utilities described above, is available at https://github.com/ShwStone/DecodingPredict.

Detailed Derivations

Hazard Identities and the Geometric Baseline

Lemma A.1 (Hazard identities). For any hazard sequence {pt}t≥1\{p_t\}_{t\geq1} with survival function St=∏s=1t−1(1−ps)S_t = \prod_{s=1}^{t-1}(1-p_s) as in (3),

E[Y]=∑t≥1St,E[Y2]=∑t≥1(2t−1)St,\mathbb{E}[Y] = \sum_{t\geq1} S_t,\qquad\mathbb{E}[Y^2] = \sum_{t\geq1}(2t-1)S_t,
Var⁡(Y)=∑t≥1(2t−1)St−(∑t≥1St)2.(13)\operatorname{Var}(Y) = \sum_{t\geq1}(2t-1)S_t-\left(\sum_{t\geq1}S_t\right)^2. \tag*{(13)}

Proof. For an integer-valued Y≥1Y\geq1 the layer-cake identities read Y=∑t≥11{Y≥t}Y=\sum_{t\geq1}1\{Y\geq t\} and, using ∑t=1n(2t−1)=n2\sum_{t=1}^{n}(2t-1)=n^2,

Y2=∑t≥1(2t−1)1{Y≥t}.(14)Y^2=\sum_{t\geq1}(2t-1)1\{Y\geq t\}. \tag*{(14)}

Taking expectations and using E[1{Y≥t}]=Pr⁡(Y≥t)=St\mathbb{E}[1\{Y\geq t\}]=\Pr(Y\geq t)=S_t gives (13). □\square

Remark A.2 (A constant hazard gives an exponential law, not a normal one). If pt≡pp_t\equiv p then Y∼Geom⁡(p)Y\sim\operatorname{Geom}(p) and the coefficient of variation is 1−p→1\sqrt{1-p}\to1, so the irreducible relative error is E∣Y−μ∣/μ→2/e≈0.74\mathbb{E}|Y-\mu|/\mu\to2/e\approx0.74 regardless of the output length. Since the indicators 1{Y≥t}1\{Y\geq t\} that sum to YY are nested rather than independent, a first-passage time does not inherit the CLT of a sum: normality requires many nearly independent contributions, which enter at a coarser level than the token.

Justification. For pt≡pp_t\equiv p we have St=(1−p)t−1S_t=(1-p)^{t-1}, so (13) gives E[Y]=1/p\mathbb{E}[Y]=1/p and Var⁡(Y)=(1−p)/p2\operatorname{Var}(Y)=(1-p)/p^2. For small pp the rescaled variable pYpY converges to a unit-rate exponential, whence

E∣Y−EY∣EY⟶E∣E−1∣=2e≈0.736,E∼Exp⁡(1),(15)\frac{\mathbb{E}|Y-\mathbb{E}Y|}{\mathbb{E}Y}\longrightarrow\mathbb{E}|E-1|=\frac{2}{e}\approx0.736,\qquad E\sim\operatorname{Exp}(1), \tag*{(15)}

where the constant follows from ∫01(1−x)e−x dx+∫1∞(x−1)e−x dx=2e−1\int_0^1(1-x)e^{-x}\,dx+\int_1^\infty(x-1)e^{-x}\,dx=2e^{-1}. An O(1)O(1) relative error is thus unavoidable under a constant hazard, no matter how much is known about xx, which is why the measured σ/μ≈0.15\sigma/\mu\approx0.15 excludes that model. □\square

Proof of Theorem 3.2 and Its Consequences

Wald identities. Write Y=∑i=1MLiY=\sum_{i=1}^{M}L_i with MM independent of the i.i.d. segments. Then E[Y]=mE[M]=mn\mathbb{E}[Y]=m\mathbb{E}[M]=mn, and by the law of total variance and Wald’s identity E[Var⁡(Y∣M)]=vE[M]\mathbb{E}[\operatorname{Var}(Y\mid M)]=v\mathbb{E}[M], so

Var⁡(Y)=vn+m2Var⁡(M)=vn+m2(c2n2+c1n)=κ2μ2+κ1μ,(16)\operatorname{Var}(Y)=vn+m^2\operatorname{Var}(M)=vn+m^2(c_2n^2+c_1n)=\kappa_2\mu^2+\kappa_1\mu, \tag*{(16)}
Equation not extracted

with κ2=c2\kappa_2 = c^2 and κ1=v/m+mc1\kappa_1 = v/m + m c_1. Taking square roots and expanding,

σ=κ2μ2+κ1μ=αμ1+κ1κ2μ=αμ+κ12α+O(μ−1),(17)\sigma= \sqrt{\kappa_2\mu^2 + \kappa_1\mu} = \alpha\mu\sqrt{1+\frac{\kappa_1}{\kappa_2\mu}} = \alpha\mu+ \frac{\kappa_1}{2\alpha} + O(\mu^{-1}), \tag*{(17)}

This is the affine variance law:

Corollary A.3 (Affine variance law). Under Assumption 3.1, with κ2=c2\kappa_2 = c^2 and κ1=v/m+mc1\kappa_1 = v/m + m c_1,

σ2=κ2μ2+κ1μ,henceσ=αμ+b+O(μ−1),(18)\sigma^2 = \kappa_2\mu^2 + \kappa_1\mu, \qquad\text{hence} \qquad\sigma= \alpha\mu+ b + O(\mu^{-1}), \tag*{(18)}

where α=κ2=c\alpha= \sqrt{\kappa_2} = c and b=κ1/(2α)b = \kappa_1/(2\alpha). The slope is therefore the coefficient of variation of the segment count and the intercept collects per-segment noise discounted by 1/(2α)1/(2\alpha)—properties of the generation process rather than of the predictor.

Corollary A.4 (Aggregation index). Under Assumption 3.1,

σμ=c2+v/m2+c1n≥c,(19)\frac{\sigma}{\mu} = \sqrt{c^2 + \frac{v/m^2 + c_1}{n}} \ge c, \tag*{(19)}

with equality as n→∞n \to\infty whenever c>0c > 0. Hence k:=(μ/σ)2k := (\mu/\sigma)^2 measures how many effectively independent stopping opportunities a prompt offers: models with a single deciding moment have k=O(1)k = O(1), aggregated models have k≫1k \gg1. For the prompts of § 4 the median of σ/μ\sigma/\mu is 0.145, i.e. k≈47k \approx47.

The two regimes. The variance form Var⁡(M)=c2n2+c1n\operatorname{Var}(M) = c^2n^2 + c_1n of Assumption 3.1 covers both cases of interest. With c=0c = 0 the segment count behaves like a renewal count, Var⁡(M)∝n\operatorname{Var}(M) \propto n, and the sampling and content terms of the decomposition below are of the same order. With c>0c > 0 the number of segments fluctuates proportionally across decodes of the same prompt—the regime implied by a fluctuating content path—and c=CV⁡(M∣x)c = \operatorname{CV}(M \mid x), which is the regime of the measurements in § 4.

The two-scale decomposition. With A=∑i<M(Li−m)A = \sum_{i<M}(L_i - m) and B=m(M−n)B = m(M-n) we have Y−μ=A+BY-\mu= A+B exactly, with E[A]=E[B]=0\mathbb{E}[A] = \mathbb{E}[B] = 0, Var⁡(A)=vn\operatorname{Var}(A) = vn and Var⁡(B)=m2Var⁡(M)\operatorname{Var}(B) = m^2\operatorname{Var}(M), so σ2=Var⁡(A)+Var⁡(B)\sigma^2 = \operatorname{Var}(A) + \operatorname{Var}(B). Although AA and BB are not independent (both depend on MM), they are conditionally independent given MM, so by the tower property

φ(Y−μ)/σ(t)=E[eitB/σφA/σ(t∣M)].(20)\varphi_{(Y-\mu)/\sigma}(t) = \mathbb{E}\left[e^{itB/\sigma}\varphi_{A/\sigma}(t \mid M)\right]. \tag*{(20)}

Given M=kM = k, the variable AA is a sum of kk centred i.i.d. terms, so a second-order expansion (or the Berry–Esseen bound for sums of length kk) gives

∣φA/σ(t∣M=k)−1∣≤t22Var⁡(A∣M=k)σ2+O(ρ∣t∣3k3/2m3σ3)=O(t2n),(21)\left|\varphi_{A/\sigma}(t \mid M=k)-1\right| \le\frac{t^2}{2}\frac{\operatorname{Var}(A \mid M=k)}{\sigma^2} + O\left(\frac{\rho|t|^3 k^{3/2}}{m^3\sigma^3}\right) = O\left(\frac{t^2}{n}\right), \tag*{(21)}

uniformly for k=O(n)k = O(n), because Var⁡(A∣M=k)=vk\operatorname{Var}(A \mid M = k) = vk and σ2≥m2c2n2\sigma^2 \ge m^2c^2n^2. Since ∣eitB/σ∣=1\lvert e^{itB/\sigma}\rvert= 1,

∣φ(Y−μ)/σ(t)−φB/σ(t)∣≤E[∣φA/σ(t∣M)−1∣]=O(t2n),(22)\left\lvert\varphi_{(Y-\mu)/\sigma}(t) - \varphi_{B/\sigma}(t) \right\rvert\le\mathbb{E}\left[\left\lvert\varphi_{A/\sigma}(t \mid M)-1\right\rvert\right] = O\left(\frac{t^2}{n}\right), \tag*{(22)}

i.e. the sampling term perturbs the characteristic function only at order 1/n1/n. For the content term, the assumed Berry–Esseen bound for MM gives, with σB=mVar⁡(M)\sigma_B = m\sqrt{\operatorname{Var}(M)},

∣φB/σ(t)−e−t2/2∣≤∣φB/σB(t)−e−t2/2∣+t22∣1−σB2σ2∣≤C(ρM∣t∣3n+∣t∣2n),(23)\left\lvert\varphi_{B/\sigma}(t)-e^{-t^2/2}\right\rvert\le\left\lvert\varphi_{B/\sigma_B}(t)-e^{-t^2/2}\right\rvert+ \frac{t^2}{2}\left\lvert1-\frac{\sigma_B^2}{\sigma^2}\right\rvert\le C\left(\rho_M\frac{\lvert t\rvert^3}{\sqrt{n}}+\frac{\lvert t\rvert^2}{n}\right), \tag*{(23)}

where 1−σB2/σ2=vn/σ2=O(n−1)1-\sigma_B^2/\sigma^2 = vn/\sigma^2 = O(n^{-1}). Combining the three displays, for every fixed tt,

∣φ(Y−μ)/σ(t)−e−t2/2∣≤C′(ρM∣t∣3n+∣t∣2n)⟶0,(24)\left\lvert\varphi_{(Y-\mu)/\sigma}(t)-e^{-t^2/2}\right\rvert\le C'\left(\rho_M\frac{\lvert t\rvert^3}{\sqrt{n}}+\frac{\lvert t\rvert^2}{n}\right)\longrightarrow0, \tag*{(24)}

and Lévy’s continuity theorem gives (Y−μ)/σ⇒N(0,1)(Y-\mu)/\sigma\Rightarrow N(0,1). Esseen’s smoothing lemma upgrades pointwise characteristic-function convergence to the uniform CDF bound (4). □

What the theorem does and does not assume. The argument does not derive normality from scratch. It reduces normality of a token-level stopping time to normality of a segment count MM—a much coarser object, with only tens of effective units—and it prices the reduction: the token-level (sampling) contribution enters the variance only at relative order vn/σ2=O(n−1)vn/\sigma^2 = O(n^{-1}), so its shape is irrelevant to leading order. In the renewal regime (c=0c=0, Var⁡(M)∝n\operatorname{Var}(M) \propto n) the two terms are of the same order and Anscombe’s theorem for randomly stopped sums plays the role of the content CLT; the conclusion is unchanged whenever M/n→1M/n \to1 in probability. The empirical checks of §4 test the outcome rather than the assumption: the affine law (16), the ratio E∣Y−μ∣/σ\mathbb{E}\lvert Y-\mu\rvert/\sigma, and the skewness/kurtosis pair all match the model’s predictions.

Proofs and Auxiliary Computations for Section 3.3

Proof of Proposition 3.3. Let Z∼N(0,1)Z \sim N(0,1) and c=(y^−μ)/σc=(\hat{y}-\mu)/\sigma, so that E∣Y−y^∣=σψ(c)\mathbb{E}\lvert Y-\hat{y}\rvert=\sigma\psi(c) with ψ(c)=E∣Z−c∣\psi(c)=\mathbb{E}\lvert Z-c\rvert. Differentiating under the expectation,

ψ′(c)=E[−sgn⁡(Z−c)]=Pr⁡(Z<c)−Pr⁡(Z>c)=2Φ(c)−1,(25)\psi'(c)=\mathbb{E}\left[-\operatorname{sgn}(Z-c)\right]=\Pr(Z<c)-\Pr(Z>c)=2\Phi(c)-1, \tag*{(25)}

which is negative for c<0c<0, zero at c=0c=0, and positive for c>0c>0; hence c=0c=0 is the unique minimizer. The value follows from u=z2/2u=z^2/2:

E∣Z∣=2∫0∞ze−z2/22π dz=2∫0∞e−u2π du=2π.(26)\mathbb{E}\lvert Z\rvert=2\int_0^\infty z\frac{e^{-z^2/2}}{\sqrt{2\pi}}\,\mathrm{d}z=2\int_0^\infty\frac{e^{-u}}{\sqrt{2\pi}}\,\mathrm{d}u=\sqrt{\frac{2}{\pi}}. \tag*{(26)}

For Y∼N(μ,σ2)Y\sim\mathcal{N}(\mu,\sigma^2) this gives MAE⁡min⁡=σ2/π≈0.7979σ\operatorname{MAE}_{\min}=\sigma\sqrt{2/\pi}\approx0.7979\sigma. □

Proof of Proposition 3.4. The density f(y)=σ−1φ((y−μ)/σ)f(y) = \sigma^{-1}\varphi((y-\mu)/\sigma) is symmetric about μ\mu and non-increasing in ∣y−μ∣|y-\mu|, so its superlevel sets As={y:f(y)≥s}A_s = \{y : f(y) \ge s\} are intervals centred at μ\mu with lengths ℓ(s)\ell(s). By the layer-cake representation and the fact that the intersection of two intervals of lengths 2τ2\tau and ℓ(s)\ell(s) has length at most min⁡{2τ,ℓ(s)}\min\{2\tau,\ell(s)\},

Pr⁡(Y∈I)=∫0∞∣I∩As∣ ds≤∫0∞min⁡{2τ,ℓ(s)} ds=Pr⁡(∣μ−Y∣<τ)(27)\Pr(Y \in I) = \int_0^\infty|I \cap A_s|\,\mathrm{d}s \le\int_0^\infty\min\{2\tau,\ell(s)\}\,\mathrm{d}s = \Pr(|\mu-Y| < \tau) \tag*{(27)}

for every interval II of length 2τ2\tau; the equality case is I=[μ−τ,μ+τ]I = [\mu-\tau,\mu+\tau], i.e. y^=μ\hat{y} = \mu. Taking I=[y^−τ,y^+τ]I = [\hat{y}-\tau,\hat{y}+\tau] gives (7). □

Proof of Proposition 3.5. For a predictor y^=f(x)\hat{y} = f(x) that is independent of the decoding noise given xx, the tower property gives

E[(Y−y^)2]=E[E[(Y−μ(x))2∣x]]+E[(μ(x)−y^)2]=E[σ2(x)]+E[(μ(x)−y^)2],(28)\begin{aligned} \mathbb{E}[(Y-\hat{y})^2] &= \mathbb{E}\left[\mathbb{E}\left[(Y-\mu(x))^2 \mid x\right]\right] + \mathbb{E}[(\mu(x)-\hat{y})^2] \\ &= \mathbb{E}[\sigma^2(x)] + \mathbb{E}[(\mu(x)-\hat{y})^2], \tag*{(28)} \end{aligned}

which is (8) and identifies the two terms as the irreducible (system) and the reducible (model) error. For the absolute loss, the triangle inequality together with Proposition 3.3 applied prompt-wise, E[∣Y−y^∣∣x]≥σ(x)2/π\mathbb{E}[|Y-\hat{y}| \mid x] \ge\sigma(x)\sqrt{2/\pi}, gives

E[∣Y−y^∣]≤E[σ(x)2/π]+E[∣μ(x)−y^∣],(29)\mathbb{E}[|Y-\hat{y}|] \le\mathbb{E}[\sigma(x)\sqrt{2/\pi}] + \mathbb{E}[|\mu(x)-\hat{y}|], \tag*{(29)}

i.e. (9): the excess over the bound is at most the L1L_1 distance from the predictor to the oracle mean. □

Proof of Corollary 3.6. Under (18), σ/μ=α1+κ1/(κ2μ)→α\sigma/\mu= \alpha\sqrt{1+\kappa_1/(\kappa_2\mu)} \to\alpha, so Proposition 3.3 gives MAEmin⁡/μ→α2/π\mathrm{MAE}_{\min}/\mu\to\alpha\sqrt{2/\pi} and Proposition 3.4 gives acc⁡@τmax⁡=2Φ(τ/σ)−1→2Φ(τ/(αμ))−1\operatorname{acc}@\tau_{\max} = 2\Phi(\tau/\sigma)-1 \to2\Phi(\tau/(\alpha\mu))-1. The bound therefore depends on μ\mu only through the ratio τ/μ\tau/\mu, which is what makes relative-error metrics scale-free. □

Test-set aggregation. For g(σ)=2Φ(τ/σ)−1g(\sigma) = 2\Phi(\tau/\sigma)-1,

g′(σ)=−2τφ(τ/σ)σ2,g′′(σ)=2τφ(τ/σ)σ3(2−τ2σ2),(30)g'(\sigma) = -\frac{2\tau\varphi(\tau/\sigma)}{\sigma^2}, \qquad g''(\sigma) = \frac{2\tau\varphi(\tau/\sigma)}{\sigma^3}\left(2-\frac{\tau^2}{\sigma^2}\right), \tag*{(30)}

so gg is decreasing everywhere, convex for σ>τ/2\sigma> \tau/\sqrt{2} and concave below. Prompts with σ≪τ\sigma\ll\tau saturate gg near 1, so a test-set average is dominated by the convex region and typically exceeds g(σˉ)g(\bar{\sigma}): for the test set of §5.3 the per-prompt average is 57.9% against 46.2% for g(σˉ)g(\bar{\sigma}). This is why all ceilings in this paper average the per-prompt bounds.

The Shape of the Deviations

Remark A.5 (Variance budget and the shape of the deviations). Write the two terms of the decomposition

Y−μ=∑i=1M(Li−m)+m(M−n)(31)Y-\mu=\sum_{i=1}^{M}(L_i-m)+m(M-n) \tag*{(31)}

as AA and BB, and let r=σsamp/σcontr=\sigma_{\mathrm{samp}}/\sigma_{\mathrm{cont}}. If the path-wise hazard is locally flat around the crossing point, AA behaves like a centred geometric variable, so the standardized law is a Gaussian–geometric convolution whose cumulants give

skew⁡(Y)=2r3(1+r2)3/2,kurt⁡(Y)=6r4(1+r2)2(32)\operatorname{skew}(Y)=\frac{2r^3}{(1+r^2)^{3/2}},\qquad\operatorname{kurt}(Y)=\frac{6r^4}{(1+r^2)^2} \tag*{(32)}

with kurt the excess kurtosis; r→0r\to0 recovers the Gaussian. The empirical medians (skewness 0.270.27, excess kurtosis 0.350.35; § 4) invert to r=0.60r=0.60 and r=0.57r=0.57—mutually consistent, and implying that at the segment counts realized here (n≈45n\approx45, far from the asymptotic regime of Theorem 3.2) about a quarter of the per-prompt variance is sampling noise. In this precise sense the decode length “is” Gaussian: the location and scale of the bound are Gaussian, and the residual right skew is a small, quantifiable correction rather than a modelling failure.

Derivation. Let X=N+r(E−1)X=N+r(E-1) with N∼N(0,1)N\sim\mathcal{N}(0,1), E∼Exp⁡(1)E\sim\operatorname{Exp}(1) independent, and r≥0r\ge0. Cumulants are additive, and the exponential law has κ3=2\kappa_3=2, κ4=6\kappa_4=6, so

Var⁡(X)=1+r2,κ3(X)=2r3,κ4(X)=6r4(33)\operatorname{Var}(X)=1+r^2,\qquad\kappa_3(X)=2r^3,\qquad\kappa_4(X)=6r^4 \tag*{(33)}

whence

skew⁡(X)=2r3(1+r2)3/2,kurt⁡(X)=6r4(1+r2)2(34)\operatorname{skew}(X)=\frac{2r^3}{(1+r^2)^{3/2}},\qquad\operatorname{kurt}(X)=\frac{6r^4}{(1+r^2)^2} \tag*{(34)}

which is (32). The map r↦skew⁡(X)r\mapsto\operatorname{skew}(X) is strictly increasing, so rr can be inverted from an observed skewness (or, redundantly, from an observed excess kurtosis); the ratio r2/(1+r2)r^2/(1+r^2) is the share of the variance carried by the geometric component. For the empirical medians of § 4 (skew =0.27=0.27, kurt =0.35=0.35) the two inversions give r=0.60r=0.60 and r=0.57r=0.57, i.e. a sampling-noise share of 24–26%. Theorem 3.2 makes the sampling component vanish only in the limit n→∞n\to\infty; at the segment counts realized here (n≈45n\approx45) its share is small but not negligible, which is precisely why the residual skew is measurable.

χ2\chi^2 Confidence Bound for σ\sigma

Given KK i.i.d. observations Y1,…,YK∼N(μ,σ2)Y_1,\ldots,Y_K \sim N(\mu,\sigma^2) with sample variance S2=1K−1∑i(Yi−Yˉ)2S^2 = \frac{1}{K-1}\sum_i(Y_i-\bar{Y})^2,

(K−1)S2σ2∼χK−12.(35)\frac{(K-1)S^2}{\sigma^2} \sim\chi^2_{K-1}. \tag*{(35)}

We want SS to estimate σ\sigma within 10% relative error at confidence 0.95, i.e. Pr⁡(0.9σ≤S≤1.1σ)≥0.95\Pr(0.9\sigma\le S \le1.1\sigma) \ge0.95, which is equivalent to

Pr⁡(0.81(K−1)≤χK−12≤1.21(K−1))≥0.95.(36)\Pr\left(0.81(K-1) \le\chi^2_{K-1} \le1.21(K-1)\right) \ge0.95. \tag*{(36)}

Let χK−1,α2\chi^2_{K-1,\alpha} denote the α\alpha-quantile of the chi-squared distribution with K−1K-1 degrees of freedom. Using the two central quantiles 0.025 and 0.975,

χK−1,0.0252≥0.81(K−1)andχK−1,0.9752≤1.21(K−1).(37)\chi^2_{K-1,0.025} \ge0.81(K-1) \quad\text{and} \quad\chi^2_{K-1,0.975} \le1.21(K-1). \tag*{(37)}

Both inequalities hold simultaneously for the first time at K=193K=193: there χ192,0.0252=155.52≥0.81⋅192=155.52\chi^2_{192,0.025}=155.52 \ge0.81\cdot192=155.52 and χ192,0.9752=232.27≤1.21⋅192=232.32\chi^2_{192,0.975}=232.27 \le1.21\cdot192=232.32, whereas at K=192K=192 the corresponding values are 154.62<154.71154.62<154.71 and 231.16>231.11231.16>231.11. We round up to K=200K=200 decodes per prompt. This requirement is the reason our test set is limited to 300 prompts: 200 decodes per prompt make an exhaustive evaluation of a larger test set prohibitively expensive.

Training Details

All predictors are implemented in PyTorch and trained with Adam. Unless noted otherwise:

  • learning rate 10−310^{-3} with cosine decay;

  • batch size 32;

  • up to 100 epochs, with early stopping on validation MAE (patience 10);

  • inputs are prefill hidden states exported with attn_implementation="eager";

  • loss: Smooth-L1 (Huber) for regression, and a cross-entropy plus MSE mixture for soft labels.

MLP-Concat. Concatenate the last-token hidden vectors of all layers. For Qwen3-32B (64 layers, hidden size 5120) the input dimension is 327,680, and the backbone applies 327680→128→128→1327680 \to128 \to128 \to1 linear maps with ReLU activations in between.

EGTP-style. Compute the entropy HiH_i of the next-token distribution at each prefill position, normalise to weights wi=softmax⁡(H)iw_i = \operatorname{softmax}(H)_i, weight-pool the hidden states per layer, and mean-pool across layers. An MLP regressor is fitted on the resulting 5120-dimensional vector.

FiLM. Condition on the prefill token count LL through a small MLP that produces a scale γ\gamma and a shift β\beta, applied element-wise to the mean-pooled hidden state before the regression head.

Soft-Label. Discretize target lengths into 100 equal-width bins and smooth the target with a Gaussian kernel of σbin=2\sigma_{\mathrm{bin}} = 2 bins. The loss is L=λLCE+(1−λ)LMSE\mathcal{L} = \lambda\mathcal{L}_{\mathrm{CE}} + (1-\lambda)\mathcal{L}_{\mathrm{MSE}} with λ=0.5\lambda= 0.5.

MoE variants. Four experts cover four length intervals with 20% overlap, namely [0,375)[0, 375), [375,750)[375, 750), [750,1149)[750, 1149) and [1149,∞)[1149, \infty). Each expert is a 2-layer MLP, and the gate is a 2-layer network with softmax output. MoE-E2E adds an auxiliary routing loss derived from the expert prediction intervals.

Full Benchmark Results

Table 4 reports mean and standard deviation over 10 independent training runs.

MethodMAEAcc@100Acc@200Acc@500
MLP-Concat169.3±4.2169.3 \pm4.248.9±1.1%48.9 \pm1.1\%71.1±0.9%71.1 \pm0.9\%94.4±0.3%94.4 \pm0.3\%
EGTP-style466.8±1.1466.8 \pm1.114.6±1.0%14.6 \pm1.0\%25.4±3.0%25.4 \pm3.0\%61.9±3.3%61.9 \pm3.3\%
MoE-Soft170.7±6.3170.7 \pm6.347.9±1.5%47.9 \pm1.5\%71.0±1.2%71.0 \pm1.2\%94.2±0.5%94.2 \pm0.5\%

Table 4. Mean ±\pm std over 10 runs (Qwen3-32B, ShareGPT).

Cross-Dataset Generalization

Table 5 summarizes experiments that train on one dataset and test on another (all with Qwen3-32B unless noted otherwise). Absolute MAE is strongly influenced by the alignment between the training and test domains, while the σ\sigma-driven ceiling stays the dominant constraint.

When the domains are closely aligned (LeetCode →\to HumanEval, both code generation), the predictor achieves low MAE and high accuracy. When they differ substantially (LMSYS →\to ShareGPT), MAE drifts toward the ceiling implied by the test-set σ\sigma. The pattern reinforces the central claim: once the predictor is adequately trained, the residual error is dominated by the inherent stochasticity of generation rather than by architectural limitations.

Train →\to TestMAEAcc@100Acc@200Acc@500x(p90)
LMSYS-200K →\to ShareGPT-100K172.6047.22%70.89%94.13%393.05
LMSYS-200K →\to ShareGPT-18k-18.3k182.4043.75%68.44%92.43%435.48
LMSYS-200K →\to GSM8K44.3392.96%99.04%99.88%86.23
ShareGPT-100K →\to ShareGPT-10K132.7057.76%80.16%96.68%299.96
LeetCode →\to HumanEval29.2896.28%100.00%100.00%76.17

Table 5. Cross-dataset generalization (train →\to test).

MoE Meta-Gate Definitions

For completeness we record the confidence-aware meta gate used in the MoE experiments. Let K=4K = 4 experts, where expert ii outputs a mean prediction μi(x)\mu_i(x) and a risk estimate ri(x)r_i(x):

μi(x)=Wi,μhi(x)+bi,μ,(38)\mu_i(x) = W_{i,\mu} h_i(x) + b_{i,\mu}, \tag*{(38)}
ri(x)=Softplus⁡(Wi,r2ReLU⁡(Wi,r1hi(x)+bi,r1)+bi,r2).(39)r_i(x) = \operatorname{Softplus}\left(W_{i,r2} \operatorname{ReLU}\left(W_{i,r1} h_i(x) + b_{i,r1}\right) + b_{i,r2}\right). \tag*{(39)}

The risk head is trained to predict the expert’s absolute error ei(x,Y)=∣μi(x)−Y∣e_i(x,Y) = \lvert\mu_i(x) - Y\rvert with a Smooth-L1 loss.

The meta gate concatenates the feature xx, the expert predictions μ(x)\mu(x), the risks r(x)r(x), and the interval distances d(x)d(x), where di(x)=max⁡(ai−μi,0)+max⁡(μi−bi,0)d_i(x) = \max(a_i - \mu_i, 0) + \max(\mu_i - b_i, 0) for the expert interval [ai,bi][a_i,b_i]. It outputs a prior π(x)=softmax⁡(g(z(x)))\pi(x) = \operatorname{softmax}(g(z(x))) and scores

si(x)=log⁡(πi(x)+ϵ)−αri(x)−βdi(x),(40)s_i(x) = \log\left(\pi_i(x) + \epsilon\right) - \alpha r_i(x) - \beta d_i(x), \tag*{(40)}

with routing weights wi(x)=exp⁡(si(x)/T)/∑jexp⁡(sj(x)/T)w_i(x) = \exp(s_i(x)/T) \mathbin{/} \sum_j \exp(s_j(x)/T) and final prediction y^(x)=∑iwi(x)μi(x)\hat{y}(x) = \sum_i w_i(x)\mu_i(x).

The total training loss is L=Lreg+λklLkl+λbalLbal\mathcal{L} = \mathcal{L}_{\mathrm{reg}} + \lambda_{\mathrm{kl}}\mathcal{L}_{\mathrm{kl}} + \lambda_{\mathrm{bal}}\mathcal{L}_{\mathrm{bal}}, where Lreg\mathcal{L}_{\mathrm{reg}} is Smooth-L1 on y^\hat{y}, Lkl\mathcal{L}_{\mathrm{kl}} is the KL divergence from the oracle soft routing targets qi∝exp⁡(−∣μi−Y∣)q_i \propto\exp(-\lvert\mu_i - Y\rvert), and Lbal\mathcal{L}_{\mathrm{bal}} penalises unbalanced expert usage.

References

  1. [1]Seungbeom Choi, Jeonghoe Goo, Eun joo Jeon, Mingyu Yang, and Minsung Jang. ELIS: Efficient LLM iterative scheduling system with response length predictor. arXiv preprint arXiv:2505.09142, 2025.arxiv.org/abs/2505.09142
  2. [2]Ting Jiang, Shaohan Huang, Zhongzhi Luan, Deqing Wang, and Fuzhen Zhuang. Scaling sentence embeddings with large language models. arXiv preprint arXiv:2307.16645, 2023.arxiv.org/abs/2307.16645
  3. [3]Woosuk Kwon, Zhuohan Li, Zhang Siyuan, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with PagedAttention. In Proceedings of the 29th ACM Symposium on Operating Systems Principles, pages 611–626, 2023.arxiv.org/abs/2309.06180
  4. [4]Yibin Lei, Di Wu, Tianyi Zhou, Tao Shen, Yu Cao, Chongyang Tao, and Andrew Yates. Meta-task prompting elicits embeddings from large language models. arXiv preprint arXiv:2402.18458, 2024.arxiv.org/abs/2402.18458
  5. [5]Ethan Perez, Florian Strub, Harm de Vries, Vincent Dumoulin, and Aaron Courville. FiLM: Visual reasoning with a general conditioning layer. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.arxiv.org/abs/1709.07871
  6. [6]Grzegorz Piotrowski, Mateusz Bystrónski, Mikolaj Holysz, Jakub Binkowski, Grzegorz Chodak, and Tomasz Kajdanowicz. Graph-based approach to predicting remaining output length in large language models. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics: Student Research Workshop, 2025.
  7. [7]Haoran Qiu, Weichao Mao, Archit Patke, Shengkun Cui, Saurabh Jha, Chen Wang, Hubertus Franke, Zbigniew T Kalbarczyk, Tamer Basar, and Ravishankar K Iyer. Efficient interactive LLM serving with proxy model-based sequence length prediction. arXiv preprint arXiv:2404.08509, 2024.arxiv.org/abs/2404.08509
  8. [8]Rana Shahout, Eran Malach, Chunwei Liu, Weifan Jiang, Minlan Yu, and Michael Mitzenmacher. Don’t stop me now: Embedding based scheduling for LLMs. arXiv preprint arXiv:2410.01035, 2024.arxiv.org/abs/2410.01035
  9. [9]Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoc Le, Geoffrey Hinton, and Jeff Dean. Outrageously large neural networks: The sparsely-gated mixture-of-experts layer. arXiv preprint arXiv:1701.06538, 2017.arxiv.org/abs/1701.06538
  10. [10]Bingyang Wu, Yinmin Zhong, Zili Zhang, Gang Huang, Xuanzhe Liu, and Xin Jin. Fast distributed inference serving for large language models. In Proc. USENIX Symp. on Networked Systems Design and Implementation (NSDI), 2026.
  11. [11]Huanvi Xie, Yubin Chen, Liangyu Wang, Lijie Hu, and Di Wang. Predicting LLM output length via entropy-guided representations. arXiv preprint arXiv:2602.11812, 2026.arxiv.org/abs/2602.11812
  12. [12]Gyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim, and Byung-Gon Chun. Orca: A distributed serving system for transformer-based generative models. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22), pages 521–538, 2022.
  13. [13]Zangwei Zheng, Xiaozhe Ren, Fuzhao Xue, Yang Luo, Xin Jiang, and Yang You. Response length perception and sequence scheduling: An LLM-empowered LLM inference pipeline. Advances in Neural Information Processing Systems, 36:65517–65530, 2023.arxiv.org/abs/2305.13144

Paper details

vlnc:W_nr4t2njv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents