paper:doi-10-48550-arxiv-2608-19611Forking Fast: Efficiently Estimating Uncertainty Dynamics in Text Generation
TL;DR
Resampling noise in reasoning-chain uncertainty dynamics is almost exactly multinomial, so most of the cost of Forking Paths Analysis re-measures structure that neighboring tokens already contain. On tinyMMLU (n=100) with Llama-3-8B-Instruct and DeepSeek-R1-Distill-Llama-8B, 1.77B tokens of S=200 reference data show log-TVD falling with log S at slopes of −0.4903 (development set), −0.4757 (Llama) and −0.4838 (DeepSeek), against the −1/2 expected under i.i.d. multinomial sampling. Measured replicate TVD sits within 0.98–1.01 of the exact multinomial null. The paper's estimator, a three-stage smoother, exploits this: PELT change-point detection with an exact multinomial cost segments the base path at forking points, Gaussian-kernel-weighted Dirichlet pooling smooths within segments, and cross-validation tunes the penalty and bandwidth. Smoothing S=5 data multiplies effective sample size by 5.0× at 4-token spacing for Llama (22.1× at 1-token spacing) and 4.9× for DeepSeek sentence resampling, falling to about 1× at S=100. Combined with coarser resampling, it cuts total budget to 1/8 with small error increase, roughly 1% of reference cost in the Figure 1 example. Gains shrink at large forks: at a 0.20 threshold smoothing is marginally worse than raw data. The implication is that resampling-based analysis of reasoning should be treated as a statistical estimation problem with a known noise model, not a brute-force sampling problem, and that sampling budgets can be allocated accordingly.
What to take away
- 1. Replicate TVD between disjoint sample halves falls with slope −0.4903 on log-log axes through S=200 on the two development questions, closely matching the −1/2 slope expected under multinomial sampling.
- 2. Full-dataset slopes are −0.4757 for Llama (every token) and −0.4838 for DeepSeek (every sentence), and measured-to-null TVD ratios range from 0.98 to 1.01, so noise is essentially pure multinomial rather than model sensitivity to individual tokens.
- 3. For Llama at 4-token spacing, smoothing yields effective sample multipliers of 5.0× at S=5, 3.3× at S=30 and 1.0× at S=100, so the benefit is concentrated in the low-sample regime.
- 4. At 1-token spacing the Llama multiplier rises to 22.1× at S=5 and 7.3× at S=30, and DeepSeek sentence-level resampling gives 4.9×, 3.1× and 1.1× at S=5, 30 and 100.
- 5. The smoother is a three-stage pipeline of PELT change-point segmentation with an exact multinomial cost, Gaussian-kernel Dirichlet pooling within segments, and cross-validation of cost, penalty and bandwidth, where S=20 is split into 5 folds of S=4 and tuned on S=16 to predict the held-out fold, which another researcher can replicate directly.
- 6. Without smoothing, wider strides give better accuracy at equal token budget, but smoothed estimates trace one Pareto frontier in which varying S and varying spacing N trade off about equally, and combining them cuts budget by 1/8 with only a small error increase.
- 7. Near forking points (±10 tokens) at S=30, raw-data TVD rises from 0.0669 to 0.0936 to 0.1587 as spacing goes from 4 to 8 to 16 tokens and saturates near 0.16 at 32–64 tokens, meaning the fork is missed.
- 8. Ablating segmentation retains 93–96% of the pooled gain but adds +0.0113 TVD for Llama at fork threshold 0.15, while swapping the PELT cost from multinomial to L2 changes TVD by at most 0.0010 and keeps 97–100% of the gain.
- 9. The smoothing advantage disappears at large forks: it holds at threshold 0.10, degrades at 0.15 (n=35 questions), and reverses slightly at 0.20 (n=21), and the 90% credible intervals cover only 0.48–0.64 of the truth, so only point estimates are recommended.
- 10. The authors report that the ruptures library silently replaces any custom cost not inheriting BaseCost with CostL2, producing very different segment counts, and they raise as an open question whether adaptive choice of sampling positions, as in optimal experiment design, could replace post-hoc smoothing.
Peer brief — for seminar discussion
The work asks whether the high cost of resampling-based analysis of reasoning chains, Forking Paths Analysis (FPA), is better treated as a modeling problem. Using tinyMMLU (n=100), Llama-3-8B-Instruct resampled at every token and DeepSeek-R1-Distill-Llama-8B resampled at every sentence, it builds a 1.77B-token S=200 reference dataset (nearly two billion tokens in total with other runs) and tests whether the noise in outcome distributions o_t is simply multinomial sampling noise. The load-bearing finding is that it is. Replicate TVD scales with slope near −1/2 on log-log axes (−0.4903 on the development questions, −0.4757 for Llama, −0.4838 for DeepSeek), and measured TVD is within 0.98–1.01 of an exact i.i.d. multinomial null. Uncertainty curves are therefore flat or slowly drifting between sparse forking points, and a large budget mostly re-measures what neighboring positions contain. The proposed smoother combines PELT change-point detection with an exact multinomial cost, Gaussian-kernel Dirichlet pooling within segments, and cross-validated hyperparameters. It gives effective-sample multipliers of 5.0× at S=5 falling to 1.0× at S=100 for Llama at 4-token spacing, and up to 22.1× at 1-token spacing. Excess TVD above the noise floor falls from 0.0265 at S=5 to 0.0056 at S=100. Combined with coarser spacing, total budget drops to 1/8. An alternative the authors could have used is a parametric hierarchical Bayesian or Gaussian-process smoother, or simply adaptive sampling that places samples near suspected forks, which they flag as future work. The implication is that resampling analyses of reasoning, of the kind used in thought-anchor work, can be run at roughly an order of magnitude lower cost, and that noise in these curves should not be read as model sensitivity to individual tokens. What is contestable: the scope is narrow. Two 8B models, five-class multiple-choice outcomes, and short rollouts (at most 400 tokens for Llama, 1536 for DeepSeek). The model and hyperparameter procedure were developed on two questions from one model, so the multinomial claim and efficiency gains may not transfer to open-ended outcomes or larger models. The strongest pushback is that the method's value is weakest exactly where analysts care most. At large forks (threshold 0.20, n=21) smoothing is marginally worse than raw data, spacing of 16 tokens or more misses forks, and the 90% credible intervals cover only 0.48–0.64, so uncertainty about the estimates is not calibrated. The reference is itself a noisy S=200 estimate, which the paper partly handles with leave-replicate-out references. The discussion's claim of roughly 15× gains is also hard to reconcile with the reported 3.3–5× multipliers at moderate S, and its in-context-learning speculation is untested.
Methods (7)
- Cross-validation hyperparameter tuningTunes PELT cost, penalty and kernel bandwidth by splitting S into folds.
- Forking Paths Analysis (FPA)Resampling method for measuring uncertainty dynamics along a base path.
- Kernel-weighted Dirichlet poolingGaussian-kernel pooling of counts within segments parameterizing a Dirichlet.
- PELT change point detectionUsed to segment base path at forking points with exact multinomial cost.
- Raw Data estimatorEmpirical frequencies with linear interpolation baseline.
- Segment+Pool estimatorAblation variant with flat per-segment Dirichlet pooling.
- Total variation distance (TVD)Accuracy metric versus S=200 reference.
Frameworks (1)
- Three-stage smoothing statistical model (Full Model)Change point segmentation, kernel Dirichlet pooling, CV tuning.
Datasets (3)
- DeepSeek-R1-Distill-Llama-8BDistilled 8B Llama-based reasoning model studied as primary experimental subject
- S=200 reference FPA dataset (1.77B tokens)High-sample reference dataset collected.
- tinyMMLU100-question benchmark used.
Findings (26)
- Removing segmentation retains 93–96% of pooled improvement but raises fork-region TVD (+0.0113 Llama thr 0.15; +0.0091 DeepSeek thr 0.10).
Ablation.
- Smoothing advantage in fork regions holds at threshold 0.10, degrades at 0.15 (n=35), and is marginally worse than raw at 0.20 (n=21).
Limitation.
- With hundreds of resamples, uncertainty dynamics become smooth except at sharp forking points; noise is largely sampling artifact.
Main result 1.
- At S=30 fork-region TVD rises from 0.0669 to 0.0936 to 0.1587 as spacing goes N=4 to 8 to 16 tokens, saturating near 0.16.
Forks missed with coarse spacing.
- Fixing PELT to L2 cost raises pooled TVD by ≤0.0010, indistinguishable from Full Model, retaining 97–100% of improvement.
Ablation.
- Replacing cross-validated hyperparameters with fixed values increases TVD by 0.0126 for Llama at threshold 0.15.
Ablation.
- With smoothed data, denser sampling reliably gives more accurate o_t estimates, including in forking regions.
Smoothed behavior.
- Log-log slope of −0.4903 of pooled replicate TVD vs S through S=200 on two development questions, near −1/2.
Noise scaling.
- ruptures silently replaces custom cost not inheriting BaseCost with CostL2, significantly affecting results.
Bug discovered.
- At S=200 variation across runs (TVD 0.0451) nearly equals sampling variation within a run (TVD 0.0442).
Supports multinomial model.
Claims (7)
- The heavy cost of resampling steps in reasoning is a modeling problem: noise is exactly multinomial and curves are smooth with sparse forks, so large budgets mostly re-measure existing structure.
Central interpretation.
- Pooling within segments and breaking at change points yields ~15× efficiency gains within segments and ~4× without losing fork accuracy.
Discussion.
- Noise in uncertainty dynamics is largely an artifact of sampling rather than LLM sensitivity to each token or step.
Abstract claim.
- Wider stride improves raw accuracy at fixed budget because averaging over a window reduces variance.
Explanation of raw behavior.
- A mechanistic theory of in-context learning could explain these learning dynamics.
Future direction.
- Segmentation is needed to preserve forks; kernel pooling alone blurs them.
Ablation interpretation.
- The choice of PELT detection cost has little end-to-end effect.
Ablation.
Hypotheses (2)
Questions (3)
- When do sharp changes in the outcome distribution correspond to decision points in the reasoning path, and when do they correspond to sampling noise?
Motivates model.
- Whether the results generalize to longer horizons, open-ended outcomes, or larger models remains to be tested.
Limitation.
- What is the right statistical model for explaining uncertainty dynamics in text generation?
Central scientific question.
Original abstract (expand)
LLM reasoning is stochastic, and so understanding a model requires grappling with the distribution of reasoning chains that it might produce for a given question, i.e., its uncertainty. Resampling-based analyses characterize this distribution, revealing which steps of a rollout determine how the model arrives at its answer. However, a major limitation of these approaches is that resampling text sequences at every token or sentence in a reasoning chain is very costly. Our work strives to make resampling analysis more computationally efficient, while also shedding light on an important scientific question: what is the right statistical model for explaining uncertainty dynamics in text generation? We show that when resampling many reasoning chains, uncertainty dynamics converge to stable patterns, and noise is largely an artifact of sampling rather than an LLM's sensitivity to each individual token or reasoning step. We develop a statistical model for smoothing noisy low-sample rollout data to better approximate high-sample data, allowing us to significantly cut sampling costs.
Related work— refs + corpus + external arXiv
Cited / in-corpus / arXiv badges show which signals surfaced each row. Multi-source rows weighted higher.
- Reasoning Theater: Disentangling Model Beliefs from Chain-of-Thoughtcitedin corpus2026≈ 79%
- ≈ 81%
- Enhancing reasoning accuracy in large language models during inference timeManish Jain Vinay Sharma2026≈ 81%
- Hint Tuning: Less Data Makes Better ReasonersMinghao Li, Xiaoqian Ma, Xiusheng Huang, Zhuo Chen, Bowen Qin, Liujie Zhang, Shuo Shang, Weihang Chen Siqi Fan2026≈ 81%
- Reliable Chain-of-Thought via Prefix ConsistencyYuki Ichihara, Mohammad Atif Quamar, Junpei Komiyama Naoto Iwase2026≈ 81%
- ≈ 81%
- Reasoning Resides in Layers: Restoring Temporal Reasoning in Video-Language Models with Layer-Selective MergingHaonan Wang, Jian Kang, Kenji Kawaguchi, Jiaying Wu Zihang Fu2026≈ 80%
- Cheap Bootstrap for Fast Uncertainty Quantification of Stochastic Gradient DescentZitong Wang Henry Lam2026≈ 80%
- ≈ 80%
- ≈ 80%
- From Where Words Come: Efficient Regularization of Code Tokenizers Through Source AttributionPavel Chizhov and Egor Bogomolov and Ivan P. Yamshchikov2026≈ 80%
- Test-time Scaling over Perception: Resolving the Grounding Paradox in Thinking with ImagesYiming Chen, Nan He, Jiahui Chen, Chaoyang Li, Houde Qian, Lifeng Sun Zheng Jiang2026≈ 80%
- Large Language Models Decide Early and Explain LaterZhixue Zhao, Bhuvanesh Verma, Radhika Mamidi, Mounika Marreddy, Alexander Mehler Ayan Datta2026≈ 80%
- ≈ 80%
- On the Role of Reasoning Patterns in the Generalization Discrepancy of Long Chain-of-Thought Supervised Fine-TuningXiangyu Xi, Zhengyu Chen, Wei Wang, Gangwei Jiang, Ranran Shen, Linqi Song, Ying Wei, Defu Lian Zhaoyi Li2026≈ 80%
- Measuring and curing reasoning rigidity: from decorative chain-of-thought to genuine faithfulnessPavan Chakraborty Abhinaba Basu2026≈ 80%
- Affinity Is Not Enough: Recovering the Free Energy Principle in Mixture-of-ExpertsMan Yung Wong (Russell)2026≈ 79%
- ≈ 79%
- ≈ 79%
- STU-PID: Steering Token Usage via PID Controller for Efficient Large Language Model ReasoningAryasomayajula Ram Bharadwaj2026≈ 79%
- ≈ 79%
- Measuring Faithfulness in Chain-of-Thought Reasoningin corpus2023≈ 79%
- Covariance-based Sequence Poolingin corpus2026≈ 78%
- Open Problems in Mechanistic Interpretabilityin corpus2025≈ 78%
- ≈ 78%
- ≈ 78%
- ≈ 78%
- Monitoring and Discovering Reward Hacking with Internal Representations during LLM Evaluationsin corpus2026≈ 78%
- Why Larger Models Learn More: Effects of Capacity, Interference, and Rare-Task Retentionin corpus2026≈ 78%
- ≈ 78%
+13 more