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 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 on ForeLen’s long-sequence split with Qwen2.5-7B, yet the same architecture degrades to MAE on ShareGPT with Qwen3-32B, or to MAE 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.
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 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.
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 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 follows the affine law in , with coefficients that vary markedly across models and posttraining recipes (Table 1).
| Model | |||
| 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 | |
| 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 indicate more stable generation. By Corollary A.3, and .
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 be tokenized into , and let denote the hidden states of layer , for , computed during prefill. Let be the number of new tokens decoded before the model emits an end-of-sequence (EOS) token, and let be an estimate of that uses prefill-observable information only.
Metrics. Following prior work [11], we report the mean absolute error (MAE ) and the pass-rate accuracy at tolerance ,
that is, the fraction of test prompts whose prediction error is below tokens. We report , , , and , the smallest for which .
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 from the next-token distribution and uses 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 ( and ) and therefore face a smaller effective . 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 , a target model, and a sampling configuration. Decoding draws from the model’s next-token distribution and stops at
where is the set of stop tokens (EOS together with any configured stop strings). Hence 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
with and . The hazard is itself random, because the sampled context decides how likely the model is to stop at step .
Appendix § 8.§ 1 records the exact moment identities implied by (3) and shows that a constant hazard would make geometric, with and hence an irreducible relative MAE of about 74%; the measured (§ 4) rules that model out. Moreover, since the indicators that sum to 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 , the response splits into segments of lengths such that (i) given and , the are i.i.d. with mean , variance , and finite third absolute central moment ; (ii) is a stopping count of the segment-level continuation process, independent of the , with and for constants . Then .*
Theorem 3.2 (Normality of the decode length). Under Assumption 3.1, let , , and . Suppose moreover that satisfies a Berry–Esseen bound at rate , i.e.
Then there is a constant such that
and hence as .
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 (renewal count) and (proportionally fluctuating segment count), and derives the consequences used below: the affine variance law with (Corollary A.3); the aggregation index , with 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.

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 , i.e. the stopping probability increases with length. (b) Bin-wise stopping probability (bin width 5% of ): the hazard ramps from to 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
up to the correction quantified in (4). We now derive what this law implies for any predictor that sees prefill-phase information only, and is therefore independent of the decoding noise given .
Proposition 3.3 (Irreducible MAE). For ,
and the infimum is attained uniquely at .
Proposition 3.4 (Maximal pass-rate accuracy). For every tolerance and every ,
where is the standard normal CDF.
Proposition 3.3 follows by differentiating and Proposition 3.4 from a layer-cake (rearrangement) argument over intervals of length ; both extrema are attained uniquely at , 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 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, for a single prompt requires tokens and requires tokens; above these thresholds high accuracy is impossible, whatever the capacity or the amount of training data.
A test set aggregates prompts with different . Because is strongly nonlinear, averaging the per-prompt bounds and inserting 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 ,
(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 , and since training labels are single decodes rather than the means , the regression target carries noise of variance , which slows learning at finite —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 (),
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 from Finitely Many Decodes
In practice is unobserved: we see only decodes per prompt. With i.i.d. the sample variance satisfies , so requiring to estimate within 10% at 95% confidence amounts to the two simultaneous inequalities
which first hold at (Appendix § 8.§ 5); we use decodes per prompt. All bounds reported below should therefore be read as accurate to about in , hence in the bound itself.
What Controls ?
Empirically, is strongly correlated with the mean length . Across six models evaluated on ShareGPT prompts, the relation is well described by the affine model derived in Appendix § 8.§ 2 (Corollary A.3):
Table 1 reports for each model. The spread is large: Qwen3-4B-Instruct is comparatively stable , whereas Qwen3-4B-no-thinking is not . DeepSeek-R1-distilled-thinking combines a low slope with an unusually large intercept , reflecting the exploratory randomness intrinsic to chain-of-thought generation even when the final answer is short. Since , the fitted slopes say that a long answer to a ShareGPT prompt is worth roughly – effectively independent stopping opportunities.
Empirical Validation
Is the Decode Length Normal?
We sample 300 prompts from ShareGPT and decode each times with Qwen3-32B, using the model’s recommended sampling configuration (temperature 0.6, top- 20, top- 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 and every statement below holds trivially. The remaining 298 prompts yield 200 lengths each.
A single -value is a poor summary at , 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 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 .
Effect sizes. The deviations are small and systematic rather than arbitrary: the median standardized skewness is (70.8% of prompts are right-skewed) and the median excess kurtosis is +0.35; 58% of prompts have and 69% have . Pooling all 59,600 standardized lengths gives skewness 0.34, excess kurtosis 1.48, and a Kolmogorov–Smirnov distance of 0.019 from . 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 (from the skewness) and (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 is (median over prompts), against the Gaussian prediction : the bound of Proposition 3.3 is accurate to 1.9% and slightly conservative. Likewise, the empirical probability mass within 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 is right-tailed (10% of prompts have ), which is why we report both the mean (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.

Figure 1. Normality of decode length (Qwen3-32B, ShareGPT). (a) Q–Q plot for a representative prompt (, , ); the deviations are confined to the extreme tails. (b) Pooled standardized lengths of all 298 non-degenerate prompts (59,600 decodes) against : a slightly peaked, slightly right-skewed Gaussian, as predicted by Remark A.5.
Correlation
Figure 3 plots per-prompt pairs. The positive correlation is evident (Spearman ): 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).

Figure 3. Per-prompt mean versus standard deviation on ShareGPT (Qwen3-32B, 300 prompts 200 decodes). The linear trend 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 . The fitted slope is 0.774, close to the theoretical slope of Proposition 3.3. In other words, the predictor is not the bottleneck: its error is the stochastic floor plus a small offset.

Figure 4. Per-prompt test MAE versus per-prompt (Qwen3-32B, ShareGPT). The linear fit (blue) closely tracks the theoretical lower bound (red, ).
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- 20, top- 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 . As shown in § 3.4, estimating to within 10% at 95% confidence requires repeated decodes, and we use ; 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 -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 ( 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.
| 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% | – | – | – |
| Soft-Label (100 bins) | 180.15 | 46.10% | 69.83% | 93.42% | 413.24 |
| MoE-Hard | 177.91 | 46.54% | 69.77% | 93.35% | 418.52 |
| MoE-Soft | 170.70 | 47.86% | 71.00% | 94.19% | 393.70 |
| MoE-E2E | 171.39 | 47.33% | 71.01% | 94.30% | – |
| Theoretical bound | 129.5 | 57.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. and ; 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 is 162.3 (median 133.9; the distribution is right-tailed, with 10% of prompts above ), 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 , i.e. at most 30% of the system error . Two effects account for it: training labels are single decodes and therefore carry noise of variance (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 (79.7% at , 96.5% at ). 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 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 () and Qwen3-30B-A3B () face much easier and much harder tasks respectively; Table 3 tabulates the resulting ceiling once, as a function of , so that any predictor can be placed against it without re-deriving the bound.
| (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 (Proposition 3.4) as a function of the per-prompt standard deviation. A 90% Acc@100 ceiling requires 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 , the reported MAE differences confound predictor quality with task hardness. We recommend that future benchmarks
fix the target LLM, the dataset, and the sampling parameters when comparing predictors;
report the per-prompt (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;
adopt relative-error metrics (MAE/, or pass rates expressed as a fraction of the ceiling ) 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 -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 is then as large as it can be. Once decoding begins, every generated token carries information about the remaining length, and the posterior variance can only shrink: , 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 , 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
Proof. For an integer-valued the layer-cake identities read and, using ,
Taking expectations and using gives (13).
Remark A.2 (A constant hazard gives an exponential law, not a normal one). If then and the coefficient of variation is , so the irreducible relative error is regardless of the output length. Since the indicators that sum to 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 we have , so (13) gives and . For small the rescaled variable converges to a unit-rate exponential, whence
where the constant follows from . An relative error is thus unavoidable under a constant hazard, no matter how much is known about , which is why the measured excludes that model.
Proof of Theorem 3.2 and Its Consequences
Wald identities. Write with independent of the i.i.d. segments. Then , and by the law of total variance and Wald’s identity , so
with and . Taking square roots and expanding,
This is the affine variance law:
Corollary A.3 (Affine variance law). Under Assumption 3.1, with and ,
where and . The slope is therefore the coefficient of variation of the segment count and the intercept collects per-segment noise discounted by —properties of the generation process rather than of the predictor.
Corollary A.4 (Aggregation index). Under Assumption 3.1,
with equality as whenever . Hence measures how many effectively independent stopping opportunities a prompt offers: models with a single deciding moment have , aggregated models have . For the prompts of § 4 the median of is 0.145, i.e. .
The two regimes. The variance form of Assumption 3.1 covers both cases of interest. With the segment count behaves like a renewal count, , and the sampling and content terms of the decomposition below are of the same order. With the number of segments fluctuates proportionally across decodes of the same prompt—the regime implied by a fluctuating content path—and , which is the regime of the measurements in § 4.
The two-scale decomposition. With and we have exactly, with , and , so . Although and are not independent (both depend on ), they are conditionally independent given , so by the tower property
Given , the variable is a sum of centred i.i.d. terms, so a second-order expansion (or the Berry–Esseen bound for sums of length ) gives
uniformly for , because and . Since ,
i.e. the sampling term perturbs the characteristic function only at order . For the content term, the assumed Berry–Esseen bound for gives, with ,
where . Combining the three displays, for every fixed ,
and Lévy’s continuity theorem gives . 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 —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 , so its shape is irrelevant to leading order. In the renewal regime (, ) 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 in probability. The empirical checks of §4 test the outcome rather than the assumption: the affine law (16), the ratio , 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 and , so that with . Differentiating under the expectation,
which is negative for , zero at , and positive for ; hence is the unique minimizer. The value follows from :
For this gives . □
Proof of Proposition 3.4. The density is symmetric about and non-increasing in , so its superlevel sets are intervals centred at with lengths . By the layer-cake representation and the fact that the intersection of two intervals of lengths and has length at most ,
for every interval of length ; the equality case is , i.e. . Taking gives (7). □
Proof of Proposition 3.5. For a predictor that is independent of the decoding noise given , the tower property gives
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, , gives
i.e. (9): the excess over the bound is at most the distance from the predictor to the oracle mean. □
Proof of Corollary 3.6. Under (18), , so Proposition 3.3 gives and Proposition 3.4 gives . The bound therefore depends on only through the ratio , which is what makes relative-error metrics scale-free. □
Test-set aggregation. For ,
so is decreasing everywhere, convex for and concave below. Prompts with saturate near 1, so a test-set average is dominated by the convex region and typically exceeds : for the test set of §5.3 the per-prompt average is 57.9% against 46.2% for . 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
as and , and let . If the path-wise hazard is locally flat around the crossing point, behaves like a centred geometric variable, so the standardized law is a Gaussian–geometric convolution whose cumulants give
with kurt the excess kurtosis; recovers the Gaussian. The empirical medians (skewness , excess kurtosis ; § 4) invert to and —mutually consistent, and implying that at the segment counts realized here (, 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 with , independent, and . Cumulants are additive, and the exponential law has , , so
whence
which is (32). The map is strictly increasing, so can be inverted from an observed skewness (or, redundantly, from an observed excess kurtosis); the ratio is the share of the variance carried by the geometric component. For the empirical medians of § 4 (skew , kurt ) the two inversions give and , i.e. a sampling-noise share of 24–26%. Theorem 3.2 makes the sampling component vanish only in the limit ; at the segment counts realized here () its share is small but not negligible, which is precisely why the residual skew is measurable.
Confidence Bound for
Given i.i.d. observations with sample variance ,
We want to estimate within 10% relative error at confidence 0.95, i.e. , which is equivalent to
Let denote the -quantile of the chi-squared distribution with degrees of freedom. Using the two central quantiles 0.025 and 0.975,
Both inequalities hold simultaneously for the first time at : there and , whereas at the corresponding values are and . We round up to 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 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 linear maps with ReLU activations in between.
EGTP-style. Compute the entropy of the next-token distribution at each prefill position, normalise to weights , 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 through a small MLP that produces a scale and a shift , 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 bins. The loss is with .
MoE variants. Four experts cover four length intervals with 20% overlap, namely , , and . 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.
| Method | MAE | Acc@100 | Acc@200 | Acc@500 |
| MLP-Concat | ||||
| EGTP-style | ||||
| MoE-Soft |
Table 4. Mean 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 -driven ceiling stays the dominant constraint.
When the domains are closely aligned (LeetCode HumanEval, both code generation), the predictor achieves low MAE and high accuracy. When they differ substantially (LMSYS ShareGPT), MAE drifts toward the ceiling implied by the test-set . 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 Test | MAE | Acc@100 | Acc@200 | Acc@500 | x(p90) |
| LMSYS-200K ShareGPT-100K | 172.60 | 47.22% | 70.89% | 94.13% | 393.05 |
| LMSYS-200K ShareGPT-18k-18.3k | 182.40 | 43.75% | 68.44% | 92.43% | 435.48 |
| LMSYS-200K GSM8K | 44.33 | 92.96% | 99.04% | 99.88% | 86.23 |
| ShareGPT-100K ShareGPT-10K | 132.70 | 57.76% | 80.16% | 96.68% | 299.96 |
| LeetCode HumanEval | 29.28 | 96.28% | 100.00% | 100.00% | 76.17 |
Table 5. Cross-dataset generalization (train test).
MoE Meta-Gate Definitions
For completeness we record the confidence-aware meta gate used in the MoE experiments. Let experts, where expert outputs a mean prediction and a risk estimate :
The risk head is trained to predict the expert’s absolute error with a Smooth-L1 loss.
The meta gate concatenates the feature , the expert predictions , the risks , and the interval distances , where for the expert interval . It outputs a prior and scores
with routing weights and final prediction .
The total training loss is , where is Smooth-L1 on , is the KL divergence from the oracle soft routing targets , and penalises unbalanced expert usage.
References
- [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]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]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]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]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]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]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]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]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]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]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]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]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