paper
active
2026
paper:doi-10-48550-arxiv-2608-19611

Forking 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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)

Frameworks (1)

Datasets (3)

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.

+13 more

Similar preprints — Semantic Scholar