Forking Paths in Neural Text Generation
Authors: Eric J Bigelow
Ari Holtzman
Hidenori Tanaka
Tomer Ullman
Venue: ICLR 2025 Poster (2025)
Keywords: Large Language Models
Uncertainty Estimation
Interpretability
Primary area: interpretability and explainable AI

Abstract: Estimating uncertainty in Large Language Models (LLMs) is important for properly evaluating LLMs, and ensuring safety for users. However, prior approaches to uncertainty estimation focus on the final answer in generated text, ignoring intermediate steps that might dramatically impact the outcome. We hypothesize that there exist key forking tokens, such that re-sampling the system at those specific tokens, but not others, leads to very different outcomes. To test this empirically, we develop a novel approach to representing uncertainty dynamics across individual tokens of text generation, and applying statistical models to test our hypothesis. Our approach is highly flexible: it can be applied to any dataset and any LLM, without fine tuning or accessing model weights. We use our method to analyze LLM responses on 7 different tasks across 4 domains,  spanning a wide range of typical use cases. We find many examples of forking tokens, including surprising ones such as a space character instead of a colon, suggesting that LLMs are often just a single token away from saying something very different.

Published as a conference paper at ICLR 2025
FORKING PATHS IN NEURAL TEXT GENERATION
Eric Bigelow 122.3 1, Ari Holtzman", Hidenori Tanaka and Tomer Ullman 1.2
'Harvard University, Department of Psychology "Harvard University, Center for Brain Science 'NTT Research, Physics & Informatics Lab UUniversity of Chicago, Department of Computer Science
ABSTRACT
Estimating uncertainty in Large Language Models (LLMs) is important for properly evaluating LLMs, and ensuring safety for users. However, prior approaches to uncertainty estimation focus on the final answer in generated text, ignoring inter- mediate steps that might dramatically impact the outcome. We hypothesize that there exist key forking tokens, such that re-sampling the system at those specific tokens, but not others, leads to very different outcomes. To test this empirically, we develop a novel approach to representing uncertainty dynamics across individual tokens of text generation, and applying statistical models to test our hypothesis. Our approach is highly flexible: it can be applied to any dataset and any LLM, without fine tuning accessing model weights. We use method to analyze LLM responses on 7 different tasks across 4 domains, spanning a wide range of typical use cases. We find many examples of forking tokens, including surprising ones such as punctuation marks, suggesting that LLMs are often just a single token away from saying something very different.
INTRODUCTION
Large Language Models (LLMs) demonstrate impressive yet opaque capabilities that emerge during next-word prediction (Brown et al., 2020; Kaplan et al., 2020; Bubeck et al., 2023), and a good deal of current research is devoted to understanding and interpreting LLM behavior (Chang al., 2024; Anwar et al., 2024; Bricken et al., 2023; Holtzman et al., 2023; Akyürek et al., 2022). LLMs are often treated black boxes due to the sheer complexity of their internal workings, and because many state-of-thed the models are only accessible at the level of inputs and outputs. One way to assess any dynamic system is to consider what possible things could have done, but didn't. 't. In text generation, we can liken text sequence to path the system took through the semantic space of all possible paths, and ask: what other paths could the system have taken? Are there key points where re-sampling the system at that specific point, but not others, would lead to very different paths?
Work on uncertainty estimation in LLMS tackles the related problem of assessing how likely an LLM is to respond with different final answers, e.g. the probability of responding "A" or "B" to multiple choice question (Kadavath et al., 2022; Tian et al., 2023; Guo et al., 2017; Ye et al., 2024). Previous approaches to black-box uncertainty estimation have yielded important insights by analyzing data such as the logit probabilities of the final tokens in an LLM's s output, or the fraction text responses that end in the correct answer (Geng et al., 2024; Xiong al., 2024). However, in our analogy, these approaches consider only the final destination, and not the paths leading to them.
A major limitation of prior work uncertainty estimation is that the last few tokens of an LLM's output are largely determined by previous tokens. For example, a single wrong step when solving a multi-step reasoning problem (e.g. "The current year is 202/ ") can cascade into wrong final answer (e.g. The current British head of state is Queen Elizabeth.") "), or other undesired responses (Zhang et al., 2023). Uncertainty over intermediate tokens or reasoning steps will not be reflected in the final tokens of the LLM's response, since these tokens will be nearly deterministic (100%
Correspondence to: ebigel harvard. Equul contribution

---

Published as a conference paper at ICLR 2025
Question:
Who is the current British head of state? Let's think step by step.
past years
Elizabeth
Answer:
Rirst, we know that the current is 2026 We also know that Queen Elizabeth was
King Charles III
Base Path
Initial Prompt
Alternate
Keir
Starmer
Outcome
Figure 1: Forking paths in text generation: can single token alter the outcome? At each step of noxt text generation, an LLM has some probability of sampling variety of possible next tokens. This raises the question: are there specific forking tokens, where choosing a certain token over other probable alternatives results in a distinct outcome? To test this hypothesis, we estimate uncertainty in text generation by systematically re re-sampling alternate completions at each token in a single base path, such as a greedily decoded sequence, to identify if there are forking tokens where two paths diverge into different outcomes. We find forking tokens where expected content words (2021/2024 in this example) lead a different final answers (Queen Elizabeth or King Charles), but we also find forking tokens in unexpected places (e.g. that/who).
confidence) given the rest of the text preceding them. A similar assumption is made in process-level supervision (Lightman et al., 2023), which gives an LLM feedback for the correctness of each step of its solutions, in addition to its final answer (i.e. outcome-leve supervision). Perhaps, then, we might gleam valuable insights by analyzing uncertainty paths and not just outcomes.
Our approach is to study uncertainty dynamics, or how an LLM's likelihood of producing different responses changes as each new token is generated (Fig. 1). Specifically, we propose the Forking Tokens Hypothesis: that in LLM text generation, there will be individual forking tokens which, if generated, lead to dramatic differences in subsequent text (Fig. 1). Uncertainty dynamics and forking tokens are unseen by prior approaches to 'static' uncertainty estimation such as taking the logits of the final answer token, or sampang many full responses. This inspires a new 'dynamical' way of thinking about uncertainty in text generation, where study the influence that individual tokens have on the eventual outcome. We develop methodology called Forking Paths Analysis (Sec. 2) in order to shed light uncertainty dynamics and to empirically test for forking tokens. We find dramatic uncertainty dynamics in GPT-3.5 in many tasks commonly used for evaluation, including single tokens that cause the model to suddenly flip from low confidence to high confidence in final answer. This supports the Forking Tokens Hypothesis, and suggests that uncertainty dynamics in GPT-3.5 are considerably more chaotic than high confidence final answers might suggest.
Put briefly, our primary contributions are:
1. A novel hypothesis regarding the existence of fookking tokens' that greatly impact the outcome of text generation. We propose the Forking Tokens Hypothesis, that there exist individual tokens which, if sampled during decoding instead of an alternative token, lead to dramatic differences in subsequent text generation (Fig. 1).
2. A novel approach representing uncertainty at each token next-word prediction. Our method aggregates text samples into time series and conditional distributions, revealing uncertainty dynamics invisible to prior work (Sec. 2.1, 2.2). We use change point detection models and survival analysis to empirically test our hypothesis and efficiently scale across hundreds of individual analyses (Sec. 2.3, 2.4).
3. Our analysis shows striking text generation dynamics, including change points in many sequences and unexpected forking tokens such as space characters We examined text generation dynamics in GPT-3.5 using 7 different LLM evaluation tasks (Sec. 4). Our results support the Forking Tokens Hypothesis.
2 FORKING PATHS ANALYSIS
In text generation, exchanging a single token may drastically alter subsequent text. This is clearly true in reasoning. For example, if we ask "Who is the current British head of state? ?", the intermediate
2

---

Published as a conference paper at ICLR 2025
LLM Sampling Pipeline
Sample Base Path Alternate Tokens
Sample Alternate Path Completions
Extract Outcome Representations
Weighted Outcome Distribution
The current King of Britain and the U.K. ... King Charles The monarch of Britain is the head of Queen Elizabeth
also who the First, we know that the current year 2024, We also know that Queen the answer King Charles III
Keir Starmor
Base Path Context
Alternate Token
Sampled Completions
Outcome Representation
x,
PEX
x
Figure 2: (Top) Systematically sampling alternate paths text generation. Our data collection proceeds in three stages, First, decode base path text completion x² from LLM given some prompt and record the most probable alternate tokens w each step t. Next, we re-sample
(e) completions Stt by appending ø²z, the original prompt, along with each alternate token Finally, we extract outcome vector representations R(.) for each sample. our experiments, for R we different LLM to extract the final answer from path. (Bottom) Probability-
outcome distributions We aggregate outcome representations R(.) into outcome distributions o and ot, by weighting each outcome with next-token probabilities for the forking token p(2; w xx2x) and for the sampled path completion p(r>
x=2 Le
w). Also see Eq. 1.
reasoning step "The current year is (2021/2024) can lead to different final answers. This could also occur in open-ended text generation, when single token distinguishes topies. For example "Billy woke up in hotel and "Billy woke up in a spaceship... " leads to very different stories. LLMs generate text one token time, and sampling word such as "hotel" instead of "spaceship" could steer autoregressive text generation towards one path over another. Many possible tokens could cause forking if exchanged, e.g. we manually set the token in the previous example "coconus". However, we aim study the forking tokens that are most likely to be sampled during text generation.
We expect text generation to be relatively stable, in that most tokens an LLM is likely to sample would only change surface features and would not affect the outcome or overall meaning. However, LLMs also show significant biases in producing certain words and phrases over others (McCoy et al., 2023), and adapting their semantic priors on the fly (Wei et al., 2023), We also might expect, then, to find unexpected forking tokens with LLMs, for example if "Billy woke up a ... leads to story about summer vacation and "Billy woke up in the ... leads to science fiction story. This could occur if an LLM were considering two different outcomes to a story (e.g. summer vacation or a sci-fi story), but these outcomes were biased towards specific words phrases such as "Billy woke and "Billy awoke. If we find unexpected forking tokens such as this, it might suggest that L.LMs are not planning their final responses before generating text, and instead they are effectively deciding what the outcome will be as each new token is sampled.
We predict that in text generation with LLMs, there will be individual tokens where text generation 'forks' into multiple distinct outputs. More formally, we propose the Forking Tokens Hypothesis: that a single token being exchanged for a probable alternate token can significantly impact the outcome of subsequent text generation in L.MMs. To test this, we develop method that includes a multi-stage sampling pipeline (Section 2.1), aggregating text samples into outcome distributions (2.2), and applying statistical models to test our hypothesis (2.3,2.4)
2.1 LANGUAGE MODEL SAMPLING PIPELINE
For our analysis, we collect a large number of output texts from an LLM for each individual question prompt using 3-stage sampling pipeline (Fig. 2, Top). We begin by decoding single base path
3

---

Published as a conference paper at ICLR 2025
response x" to a given prompt. This sample includes, for each token 2; in sequence, the logit probabilities p(zz = w|r<() for the top K tokens w at index t. Next, for each index t and each alternate token with sufficiently high probability p(z, w x)xe),
re-sample batch of samples {r-2) (8) by prompting the LLM with the original input text appended to the base path response क5 up time t, with the last token being 24 w. In the third step, we extract an outcome representation for each sample R( Ft w, x >( Described in the following section, R is semantic vector representation such as one-hot encoding of the final answer.
These stages rely on token logit probabilities from the evaluated LLM, which are available in black- box LLM APIs such as OpenAl and TogetherAl and can also inferred for APIs without this feature (Morris et al., 2023). In experiments, the third stage R. uses second LLM, which may be the same or different from the main LLM being evaluated, and does not require logit probabilities. We prompt this model to extract the final answer from x²", and convert its response into categorical value, such as "A" or "B".
2.2 REPRESENTING TEXT GENERATION OUTCOMES
We construct outcome distributions for individual token indexes and for token values or,w- We define an outcome distribution o as the expected value of a semantic vector representation R, which varies depending on the task and takes as input both the question prompt and model-generated response. In the case of multiple-choice task, a one-hot encoding of the final answer in the response string (e.g. 'A', 'B', 'C', or 'D"). For open-ended tasks without final answers, R can be any arbitrary semantic vector embedding.
(x,)
(5) E2 [R(eee Zt = =w, [111
(1)
Σ plab2 a'eer Wi w) R(x221 3t. w; (.
or(x*) -Ew |
(2)
Σ p(ze w x22)))
(6) Σ p( 122 w) R(E2t1 Iz- w, xz21)
Outcome Distr. Next-Word Prediction
Sample Probability
Outcome Representation
In our experiments, o, and Or,an are histograms over categorical outcome representations Rt weighted by the sample probability p(Z></<<<) I p(zr(Z1r)). ). In the case of ot, outcome represen- tations are also weighted by the forking token probability p(z, = w|x<)). All such weighting probabilities are derived from next-token prediction probabilities ((22/)11111)...... For brevity, refer to T1--1 as Tet and It+1:7 as Vz4. Our approach is Bayesian, in that we weight samples according to graph of conditional probabilities and we interpret output certainty the degree of an LLM's belief. This stands in contrast to frequentist calibration methods, which interpret certainty as the fraction of problems which are answered correctly (Guo al., 2017; Kadavath et al., 2022; Geng et al., 2024), or and ot.w have the advantages of being easy to visualize, and suitable for statistical analysis. O can be represented as multivariate time series (Figs. 4, 5), and ot.w can be plotted with parallel sets diagrams (Fig. 7). These visualizations reveal uncertainty dynamics across tokens, showing how the outcome distribution can dramatically change over the course of text generation.
Next, in the following sections we describe methods for analyzing outcome distributions and or to test for forking tokens. We define a forking token x; as token index or value x; = w which, if exchanged, leads to very different outcome (or 'path', ". In the case of ot, forking token index t corresponds to an abrupt change in the time series ot, i.e. where 0%4 & 02z- To identify these changes, we use Bayesian change point detection models, class of statistical models that empirically test whether there are abrupt changes in time series, and so to identify the times t when those changes occur. For or,w, forking token value x; occurs when the outcome distribution for an alternate token w deviates from the distribution for the base path token w² by at least e. To identify forking tokens in or we use discrete-time survival analysis where hazard (i.e. non-survival) occurs when a0 & ot,w-] for some token wc
4

---

Published as a conference paper at ICLR 2025
Uncertainty Dynamics Time Series
0x(x*)
y;= y;=do,, 0,)
current
year
2024
Text generation index
Text generation index
Outcome Distribution by Token
Multivariate Time Series
Semantic Drift Transformation
Change Point Detection (CPD) Model
Bayesian CPD Posterior Inference
P.
8.= (t.(t)
p( = (
p(m| y)
Text generation index
Text generation index
change points m
Figure 3: Uncertainty dynamics time series (Top) The outcome distribution o is equivalent to multivariate time series, where each possible outcome (e.g. King Charles or Queen Elizabeth) can be plotted as separate line. To simplify our modeling, we convert o, into a univariate time series using a semantic drift transformation y/- Bayesian Change Point Detection model. (Bottom, Left) We use Bayesian Change Point Detection (CPD) model to identify sudden shifts in y/- This model fits ye by splitting it into segments at times T, and fitting separate linear models with parameters B,, 6; to each segment (Bottom, Right) Our CPD model uses Monte Carlo sampling to infer posterior distributions that help interpret analysis results: p(T t y), or how likely it is that a change happened at time t, and p(m] y), or how many change points, if any, occurred in the time series.
2.3 BAYESIAN CHANGE POINT DETECTION
We now present a method for automatically identifying tokens where o, changes suddenly, and for statistically testing the hypothesis that such tokens exist. In simple terms, our goal is to test for whether there are indexes such that the outcome distribution changes substantially before and after t, i.c. Ose & Ocr-- Change Point Detection (CPD) is area of statistics that models time series data with abrupt changes to the line's intercept and/or slope. CPD models jointly infer what time t change occurs at, as well as trend parameters 3 for time segments before and after the change. We suppose that there may be multiple forking tokens, or change points, in the outcome distribution o<(x=) for single sequence x². This leads to use multiple CPD models, which assume there may be multiple change points. However, inference with multiple CPD models can be exponentially more expensive than with single CPD (Fearnhead, 2006). One solution to this complexity using Bayesian models for efficient approximate inference. Since multiple CPD with multivariate time series (as in ox) a relatively young area of research (Cabrieto et al., 2017) with limited available tooling, we convert 0g into univariate time series y/ using semantic drift metric (Fig. 3, Top), as in Kulkarni et al. (2015). Each time point in the univariate time series yt = d(oo: 0;) is the distance between the initial outcome distribution and outcome distributions for subsequent time steps or. given an arbitrary distance metric d. In our experiments, we use L2 distance for d.
More specifically, a CPD model decomposes a time series y into a set of m segments. Each segment i e (0... [0...m) } is fit by a regression model with intercept (i.c. abrupt change) d, and slope 3,, applicd to time steps é between T/-1 and TP. In Bayesian CPD model, p(T t'y) describes how likely it is that a change point t occurred at each time t in time series data y. and p(mly) describes belief in the number of change points m in series. The beginning and end of sequence treated as fixed change points (i.e. TO = 0 and Tm = ') which are excluded from analysis of p(T = m) and p(m y). We test for statistically significant change points by comparing the hypothesis that there is no change point (m = 0) with the hypothesis that there is at least one (m 2 1) (Aminikhanghahi & Cook, 2017). In Bayesian CPD, this entails model comparison between a model with no change points and a model with at least one change point. We take Bayes factor p(m 2 11y) / p(m = 0ly) greater than 9 as supporting the hypothesis that there is at least change point (Kass & Raftery, 1995) We use an extremely efficient open- implementation of Bayesian CPD which utilizes
"9 is typical threshold for Bayes factor significance testing, analogous to .05 in frequentist statisties
5

---

Published as a conference paper at ICLR 2025
Other
Question:
Hix Namntr
What American actress born June 19, 1972, was the The La-Lass?
Nu Sere
Popty Manegemery
Answer:
Outcome
Let's think step by step.
need identify American actness on June 19, 1972. A quick Google search reveals that the question Sara.
Change Point Prob. pir-iin 10
qusdicn
Sami
Next, need
Next, we nead find out Mia Sara was in the film Another Google search indeed star in the 2003 remake of The In-l law, alongside Michnel Douglas Albert Brooks.
Change Point at (-34
Therefore, the answer the question is Min Somi
40
80
Token Index
Figure The outcome distribution can collapse after single step in chain-of-thought reasoning. (Left, Top) The outcome distribution or and (Left, Bottom) change point probabilities p(r tly) for a single question from HotpotQA and a greedily decoded base path x". (Right) Tokens x", highlighted according to p(r = flyy, where yellow indicates low probability of change point, red indicates high probability; the initial prompt is shown above x' with no coloring. We see striking uncertainty dynamics in oμズ the outcome distribution remains stable with the top single answer being Robin Tunney (the correct answer) until the forking token i = 34, when the distribution suddenly collapses Mía Sara (a hallucinated wrong answer).
Monte Carlo Gibbs sampling infer posterior distributions p(m y) p(T fly) given sequence y (Zhao, 2019). Further details of CPD model are provided App. B.
2.4 SURVIVAL ANALYSIS
We perform survival analysis estimate how likely it is that text generation would be greatly impacted if a token in a base path x; = w" were instead sampled as w. This deseribes cases where an alternate token w leads an LLM down very different path from x², as in Fig (Right). This forking may not appear as stable change in or or(x)) (Sec 2.3) since w was not actually sampled and therefore does not impact (>²(x"). We define the survival function S(t) the probability that the base path "survives" sampling alternate tokens that would change the outcome distribution:
S(t) =
II 8'mm
Ew Jou, & Ou,
(3)
= =1
II #=1 w
Σ
plar = = w w| [dd(or, w-) c]
S(t) is discrete time survival function -1 -1:---1--- h(t') where h(t) the probability that a failure (or hazard fi) occurs at time t. In our case, a failure is when an alternate token causes the outcome distribution to shift significantly from the greedy, i.e. or,w o Or,w", which we estimate by testing whether the distance between outcome distributions d(or, ot,w=) ) is greater than some threshold 6. an arbitrary distance metric and we use L2 distance as our experiments. For each i, we compute the hazard rate h((t) as the sum of token logit probabilities p(2, w wlkkk,) for all forking tokens w (i.e. tokens where (Or, wr o1,w=) > 6).
-
EXPERIMENTS
We analyzed 7 unique tasks, across 4 different categories representative of typical LLM use and evaluation: Symbolic Reasoning, Mathematical Reasoning, Complex Question Answering, and Story Generation. These categories demonstrate the broad utility of our approach for various applications of text generation. The first three categories typically benefit from Chain-of-Thought (CoT) reasoning, where an LLM explicitly lists each step of its reasoning before giving final answer (Kojima et al., 2022: Wei et al., 2022). This is appealing for our analysis since output text in CoT is more complex than simple one- word answer, and so we may expect to see uncertainty dynamics in reasoning text. The category of Story Generation demonstrates the applicability of methods to open-ended L.I.M

---

Published as a conference paper at ICLR 2025
Outcome Distribution 9; (x")
Hell se mer sikked ancoum sctuece Spaen wettie
sdla You chaddiaall alrucce dradpic Stutte
NMLL -22
the Spar
boraa meee calasde Adt' cidy diick cansuing bo Boure au Mighiie lnve boun in des per dule drecnns vor OWY.
CSMAB 50
Dulcame
by cabiidde bemoue Add's wesiiy abuta
offer urancyy
5528
hhiddhereeee Aall meully dicste lefeer snw dester Et.
Text Generation Index C
Generated Highlighted
Figure 5: Further examples of forking tokens Two examples of outcome distributions (x(x*) with forking tokens: a physies question from MMLU (Top; Correct Answer: B) and mathematical reasoning question from GSM8k (Bottom; Answer: 21). In MMLU-12, we see similar pattern to Fig. 4, where remains stable for most of the base path, before suddenly collapsing when the answer token is first specified "a 9.8 m/s "2" GSM8k-59 we see multiple forking tokens, both occurring unexpected places. E.g. for the second change point, 0st changes depending on whether the token ( or 'by' sampled. We also note that, similar to Fig. 4, at I = 0 the most probable outcome is the correct answer (2/) but this answer disappears from Os way through.
cases, such creative writing, where there is no ground truth 'correct' answer. We have two tasks for each of the three CoT categories: one multiple choice dataset with limited set of answers, and one dataset with free-text response answers. F.g. for Symbolic Reasoning, CoinFlip has two options for the answer ("Yes" or "No"), whereas Lastletterr Letee has no such constraint.
We zero-shot CoT prompt in Kojima al. (2022) for the first 6 tasks. CoinFlip (Wei et al., 2022) is a very simple symbolic reasoning task with two responses: Yes or No. LastLetter (Wei et al., 2022) is more complex symbolic reasoning task, prompting models to take the last letter of each of four names (e.g. 'Forrest Juanito Allan Candice' ') and concatenate them ('tone") '). AQuA (Ling al.. 2017) and GSM8k (Cobbe et al., 2021) test mathematical reasoning with relatively simple math word problems. AQuA is 4-option multiple choice format, whereas GSM8k is open ended. MMLU (Hendryeks al., 2020) complex question answering dataset of multiple choice questions spanning many domains and is used to test LM HotpotQA (Yang et al., 2018) is a complex question answering dataset of multi-hop reasoning questions which cannot be answered by single memorized fact, but instead require chaining facts together. For our story generation task, we use the StoryCloze (Mostafazadeh et al., 2017) dataset, which was originally used for story understanding, and consists of short stories each with valid ending sentence as well as an invalid ending. We modify StoryCloze for open-ended story generation, by prompting model generate short story given only the first sentence of scenario, with the constraint that the story must end with one of two provided endings.
across wide range of subjects.
For our Forking Paths Analysis, we sample the < 10 most probable alternate tokens x; such that the probability of each token w is at least 5%. When sampling batches at each token index and alternate token, we collect S 30 text samples. For (1), we collect N 300 full text responses from the starting index t = 0 and aggregating outcome responses R into histogram. For (2) we append a final answer prompt to x=:
and query the evaluated LLM, taking the logit probability of the first response token. (3) appends another prompt to the result of (2): Percent confulence in final answer: _".
Therefore, the answer
We evaluated OpenAl's GPT-3.5 completion model 1opp::3.--trroo-isstuctt--tooo For cost efficiency, we used Google's Gemini Flash (gemini-1.5- 1--ffash-000: $$0075 per IM tokens) to extract final answer outcome representations Rt. We used slightly different prompts for R for each task, for example with MMLU we requested the answer choice A/B/C/D if it's provided. Additionally, used simple answer cleansing functions written in Python (as in Kojima et al. (2022)) extract minimal categorical answers from the R model's 's responses. See App. prompts and further details. Our Forking Paths Analysis pipeline (Fig. 2) is very costly in terms of the number of tokens required
$$2 per 1M tokens).
7

---

Published as a conference paper at ICLR 2025
Muttile Choice Tasks
Free Respence Tasks
025
Contip
0.20
0.20
(ert oper
of Examptee with
StwryCoene 20riiee
Change Paite
0.15
0.15
0.85
0.5
0.0 02
0.1
0.5
1.0
0.00
0.3
0.2
0.1 0.5 0.2 1.0
Mormakeed Token Index:
Figure 6: Change points occur closer to the beginning of sequences for some tasks, and near the middle of sequenees for others Each point represents the fraction of question-answer examples in task where our change point model predicts one or more change points approximately at 4, i.e. where p(T = tly) is above a threshold of .7. In three tasks (AQuA, MMLU, and LastLetter) we find a large number of change points close to the end of responses, which may suggest patterns similar to MMLU-12 in Fig. 5.
for inference (~1 million tokens per x², or $22 USD for GPT-3.5). For this reason we analyzed subset of 30 data points for each task, ~5500 in total. We randomly sampled question-answer pairs for all datasets. For GSM8k and MMLU, we used tiny Binyhenhhsarss (Polo al., 2024), which are a subset of 100 examples where LLM performance on this subset is highly correlated with performance on the full dataset. For HotporQA and AQuA we excluded questions and answers with string length outside the .9] quantile range, and for HotpotQA we sampled 18 data points for each difficulty level (easy, medium, hard).
4 RESULTS
4.1 CHANGE POINT DETECTION
In Fig. we observe striking uncertainty dynamics in or for HotpotQA (question 8076). The outcome distribution remains stable with the top single answer being Robin Tunney (the correct answer) until the forking token = 34, when the distribution suddenly collapses to Mia Sara (a wrong answer). This is precisely when the LLM answers the first question in its chain-of-thought:: "First, we need to identify the American actress born on June 19, 1972... ... is Mia Sara.". In reality, Mia Sara is an actress born on June 19 of different year, 1967. Apparently the LLM was uncertain until it hallucinated falsehood in its first reasoning step, and then it suddenly became certain that Mia Sara was the answer. We also see another hallucinated falsehood in the second reasoning step (Mia was not in this film), except by this point the LLM has already decided what its final answer will be.
In MMLU-12 we see similar pattern (Fig. 5, Top), where or remains stable in relative uncertainty for a long period, before suddenly collapsing when the answer token is first specified "a = 9.8 m/s" 2". Note that the equation in the prior sentence "a 6.67... ... evalluaess to a different answer B) 8.9 m/s 2. Examining token logits we see that 9 had 54% probability of being generated and 8 had 29%. With GSM8K-59 we observe more complex uncertainty dynamics (Fig. 5, Bottom) with multiple change points. These forking tokens occur at unexpected, seemingly innocuous tokens: both are open parenthesis tokens which provide extra information not required for the final answer (i.e. non-essential clauses such as '(kWh)') For the second forking token, ... weekly consumption ( ... the top answer in O>. is "$3,528' the token sampled is ( ', but changes to '$504' if the token sampled is 'by'. We also note that, similar to Fig. 4, at 0 the top probability answer is the correct answer (21") but this answer disappears from og part-way through x². Finally, in most cases where model detects no change points, we observe time series where the LLM remains confident in single outcome, with no notable uncertainty dynamics throughout text generation. Visualizations for all examples x² and analyses in dataset are available through interactive dashboard online." Additional analyses are provided in App. E.
We find additional patterns when aggregating CPD model inference results across tasks (Fig. 6, Tab. 1). Different tasks have different numbers of change points m, as well as different patterns in common change times r. We find more change points in some tasks, such as GSM8k and LastLetter. than others, with the fewest change points in CoinFlip. In order to compare change point times 7,
Interactive dashhoard:
stramm1 appp
8

---

Published as a conference paper at ICLR 2025
HotpotQA 8076
Surwaal nake sta Hazrd Preb. hd
0.4
GSMBK- 59
tee de
0.3
HotporGA- 8076
MMLU -12
X-i
F.W
0.2
0.0
1.0
0.8
0.-
04
ANA
0.2
0.2
0.4
Token Index
$+1,W
Figure 7: Text generation has a low probability of surviving decoding without a major distribu- tion shift (Top Left) The hazard function h(t) is the probability that or,w will change significantly if a different token w is sampled, and (Bottom Left) S(t) measures the cumulative survival rate after many hazards. We see that in most cases, hazards slowly accumulate as S(t) gradually decreases, but a few key tokens in GSM8k-59 and HotpotQA-8076 have large hazards corresponding to sharp drops in (t). We also see that the final survival rates S(T) for all three examples are below 30%. (Right) or,w visualized as parallel sets plots. We show distributions for two subsequent tokens 0r=34, and 0rm35,ars where different colors indicate different final answers. this example, = 34 and L = 35 a step in reasoning solution which eventually is used in the final answer (also Fig. 4). For t = 34, we see that the next token being Robin instead of Mia will lead to completely different outcome distributions 034 'Mia' and 034,w== 1=obbin"
we first normalize token index / to the range [0, 1]. Then, for each bucket across I, we compute the fraction of question-answer examples or (x*) with change point probability p(r = (|y) above some threshold. Under this analysis (Fig. 6, Left), tasks. In three tasks (AQuA, MMLU, and LastLetter) we find a large number of change points close to the end of responses, which may suggest patterns similar MMLU-12 (Fig. 5, Top). In LastLetter we find the most change points early in sequences, and HotpotQA, GSM8k, and AQuA we find the majority of change points in the middle of sequences. These points may correspond to individual CoT reasoning steps, similar to the change point in HotporQA-8072 (Fig. 4).
find change points at different times for different
4.2 SURVIVAL ANALYSIS
Our survival analysis shows low survival rates for many sequences x", even with large distance threshold .6 (Fig. 7), using L2 as the distance metric To give an intuition for = with d = Ly: change from ot, = [.5, 55 or = [.85, .15] will have distance of < .5. The hazard probability h(t) for the sequence with e = .6, with sharper spikes (and corresponding drops in than others. This shows that even though tokens w, which radically change the outcome distribution, have a relatively low probability, these chances can accumulate over the course of generating sequence. Aggregating results across all experimental data x (Fig. 7, Right), we find that majority of examples in our data have low survival rates the end of the sequence (S(T)- .2) for all .9. This suggests that text generation may have a low probability of surviving decoding without major distribution shift, which would imply that single sample LLM uncertainty estimates may be highly unstable.
survival rate S({) at some tokens
when forking
5 DISCUSSION
Text generation with LLMs can be viewed as a branching tree of possible paths, where each word choice determines what text will follow, akin to Borges' Garden of Forking Paths and other choose- your-own-advvntuure stories (Borges, 1941; Bottou & Schölkopf, 2023; janus, 2021). Many of these paths will follow similar trajectories and end in similar places, but some of them will hit forks which bifurcate into multiple distinct meanings. Our results support the Forking Tokens Hypothesis by empirically demonstrating forking tokens in a sfate-of-the art LLM applied to various real world benchmarks, suggesting that L.MSs often just single token away from producing

---

Published as a conference paper at ICLR 2025
Domain
Task
m 2 1 Changes
Mean S(T)
Symbolic Reasoning
CoinFlip
0%
.20
LastLetter
63%
.30
Mathematical Reasoning
AQuA
30%
.33
GSM8k
27%
.18
Complex Question Answering
MMLU
43%
.13
HotpotQA
32%
.26
Story Generation
StoryCloze"
7%
.27
Table Summary of results across all tasks We used tasks spanning domains commonly used for LLM evaluation. For each task, we list results for both our Change Point Detection model and our Survival Analysis. For change points, we list the fraction of question/answer pairs each dataset for which our model predicts at least change point with 90% confidence (i.e. the 11 quantile of p(mlly)) We then list the average survival rate at the end of each sequence S(T), using a threshold e = .6. We find lower survival rates in GSM8K and MMLU.
a very different answer. Forking Paths Analysis reveals dynamics unseen by prior approaches to uncertainty estimation, for example patterns where uncertainty is stable until forking token is reached, at which point the outcome distribution collapses into certainty in a single answer. Our results show how static estimates of uncertainty can be misleading, e-g. estimating - 1000% confidence at the last token and -40% confidence at the first token of the same sequence (Fig.4) 4).
Forking tokens might also have important implications for LLM evaluation and safety. If LLM behavior can change suddenly when even one token is sampled differently, this could impact user safety, e.g. if an LLM suddenly shifts to the wrong distribution such as producing hallucinations or harmful language (Anil et al., 2024). Static safety evaluations may prove brittle when, in real world user interactions, users might uccidentally or intentionally guide LLMs down dangerous paths. Static evaluations might be misleading measures of performance and alignment if LLMs have capabilities that emerge and then disappear over single context window, or capabilities that remain dormant until a single token (or 'path') triggers them (Cleo Nardo, 2023; Li et al., 2024).
We see a number of promising avenues for future work. The most immediate directions would be further Forking Paths Analyses with different LLMs, including open-source, and new tasks. Our experiments use second LLM as a one-hot feature extractor R(-), but more open-ended tasks could be analyzed using R as a semantic vector embedding. A limitation of our approach is that it is very costly in the number of tokens sampled. More efficient sampling (Banga & Balsa-Canto, 2008) might be able to reduce the number of tokens needed, and it might even be possible to avoid sampling altogether if hidden activations can be used to predict forking. We also hope to further explore applications of Forking Paths Analysis, for example to improve process-level RL feedback (Lightman et al., 2023) or to guide branching in inference-time tree search (Yao et al., 2024). By studying the mechanisms of forking tokens, we might be able to better understand how LLMs represent uncertainty, or to steer models more effectively by patching activations at forking tokens (Fei et al., 2024).
The Forking Tokens Hypothesis raises number of important questions, including: why do forking tokens occur in LLM text generation? One way to answer this question is with theories of In-Context Learning as Bayesian model selection (Xie al., 2021). If this is the case, then we might expect sharp transitions in overall behavior when new data changes which latent model (i.e. 'capability' or 'concept') is the maximum a posteriori (Bigelow et al., 2024). Studying forking tokens may provide valuable insights into how model selection surfaces in LLMs operating in real-world domains. Another perspective on forking tokens is to consider whether humans might have similar phenomena. We might expect forking in human language comprehension, e.g. when you read the sentence "Billy woke up in following words. In language production, however, a person who accidentally says the word "hole" instead of "hotel" is unlikely to then change their story to match "hole". An L.LM, on the other hand, might do just that. One interpretation might be that people typically holding intents and plan responses to some degree before they speak, whereas LLMs truly decide what to say next on the fly. This may be a fundamental property of next-word prediction models, unless the model has hidden state such as a hidden chain-of of of-tth (OpenAI, 2024). Forking in human speech may be more common during certain kinds of creative dialog, e.g. when a person makes up a fictional story one sentence at time, or when people think 'out loud' or 'step-by-step" (Lombrozo, 2024).
the next word being either hotel or hole should change your expectations of the
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY STATEMENT
All code and data used for this project is available at htttps://github.coo www.:///eeillll.loooo.......o.oe rathis
ACKNOWLEDGMENTS
E.B. supported by research internship with NTT Research, Inc. Compute resources used in this work were funded by grant from the Hodgson Innovation Fund at Harvard's Department of Psychology. We would also like to thank Yang Xiang, Yingqiao Wang, and Ekdeep Singh Lubana for helpful conversations.

---

Published as a conference paper at ICLR 2025
REFERENCES
Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou. What learning algo- rithm in-context learning? investigations with linear models. arXiv preprint arXiv:22 156661 2022.
S. Aminikhanghahi and D. J. Cook. Detecting correlation changes in multivariate time series: A comparison of four non-parametric change point detection methods. Knowledge and information systems, 51(2):339-33) 00099-6662200000 2017.
Cem Anil, Esin Durmus, Mrinank Sharma, Joe Benton, Sandipan Kundu, Joshua Batson, Nina Rimsky, Meg Tong, Jesse Mu, Daniel Ford, et al. Many-shot jailbreaking. Anthropic, April, 2024.
Usman Anwar, Abulhair Saparov, Javier Rando, Daniel Paleka, Miles Turpin, Peter Hase, Ekdeep Singh Lubana, Erik Jenner, Stephen Casper, Oliver Sourbut, et al. Foundational challenges in assuring alignment and safety of large language models. arXiv preprint arXiv:2404. 099322. 2024.
Julio Banga and Eva Balsa-Canto. Parameter estimation and optimal experimental design. Essays in biochemistry, 45:195-210 210, 2008
Eric Bigelow, Ekdeep Singh Lubana, Robert P Dick, Hidenori Tanaka, and Tomer Ullman. In- context learning dynamics with random binary sequences. International Conference on Learning Representations (ICLR), 2024.
Jorge Luis Borges. The garden of forking paths. pactettediictions 119, 1941.
Léon Bottou and Bernhardt Schölkopf. Borges and a.i. arXiv preprint arXiv:2310.0142 2023.
Trenton Bricken, Adly Templeton, Joshua Batson, Brian Chen, Adam Jermyn, Tom Conerly, Nick Turner, Cem Anil, Carson Denison, Amanda Askell, Robert Lasenby, Yifan Wu, Shauna Kravec, Nicholas Schiefer, Tim Maxwell, Nicholas Joseph, Zac Hatfield-Dodds, Alex Tamkin, Karina Nguyen, Brayden McLean, Josiah Burke, Tristan Hume, Shan Carter, Tom Henighan, and Christopher Olah. Towards monosemanticity: Decomposing language models with dictionary learning. Transformer Circuits Thread, 2023. http://transforneeccrcuttts ptt.:rrriitsttttt00mmommmmmmmam features/index.htme
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 13:1877-1901, 2020.
Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint arXiv:23033. 12712, 2023.
Jedelyn Cabrieto, Francis Tuerlinckx, Peter Kuppens, Mariel Grassmann, and Eva Ceulemans. Detecting correlation changes in multivariate time series: comparison of four non- non-parametric change point detection methods. Behavior research methods, 49:988-1005, 2017.
Yupeng Chang, Xu Wang, Jindong Wang. Yuan Wu, Linyi Yang, Kaijie Zhu, Hao Chen, Xiaoyuan Yi, Cunxiang Wang, Yidong Wang, et al. A survey on evaluation of large language models. ACM Transactions on Intelligent Systems and Technology, 15(3):1-45, 2024.
Cleo Nardo. The waluigi effect, 2023. URL http::ttt///omm / http://wwwwwwwwwsgg...ommm www.://sgooooo//oooeoo.ooeoeeeee
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reñchiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2/ 10. 14168, 2021.
Paul Fearheead. Exact and efficient bayesian inference for multiple changepoint problems. Statistics and computing, 16:203-213, 2006.
12

---

Published as a conference paper at ICLR 2025
Yu Fei, Yasaman Razeghi, and Sameer Singh. Nudging: Inference-tine time alignment via model collaboration. arXiv preprint arXiv:2410.09330, 2024.
Kanishk Gandhi, Denise Lee, Gabriel Grand, Muxin Liu, Winson Cheng, Archit Sharma, and Noah D Goodman. Stream of search (sos): Learning to search in language. arXiv preprint arXiv:2404.03663,, 2024.
Jiahui Geng, Fengyu Cai, Yuxia Wang. Heinz Koeppl, Preslav Nakov, and Iryna Gurevych. A survey of confidence estimation and calibration in large language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics:
Human Language Technologies (Volume I: Long Papers), pp. 6577-6595, 2024.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International conference on machine learning, pp. 1321-1330. PMLR, 2017.
Seungju Han, Beomsu Kim, and Buru Chang. Measuring and improving semantic diversity of dialogue generation. (arXiv:2210.05725), October 2022. URL ht.p:://axat hww.voor//aaoo /abs/ 2210. 05725. arXiv:2210.05725 [cs].
Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. arXiv preprint arXiv:2009. 00t.:20009.0300, 2020.
Ari Holtzman, Peter West, and Luke Zettlemoyer. Generative models complex systems science: How can we make sense of large language model behavior? arXiv preprint arXiv:2308.001 2023.
Michael Y Hu, Angelica Chen, Naomi Saphra, and Kyunghyun Cho. Latent state models of training dynamics. arXiv preprint arXiv:2308. 09543, 2023.
janus. Loom: interface to the multiverse, 2021. URL
Saurav Kadavath, Tom Conerly, Amanda Askell, Tom Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, 7ac Hatfield-Dodds, Nova DasSarma, Eli Tran-Johnson, et al. Language models (mostly) know what they know, arXiv preprint arXiv:2207.0522 2022.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint wwXivv2001.083660 2020.
Robert E Kass and Adrian E Raftery. Bayes factors. Journal of the american statistical association, 90(430):773-73) 1995.
Robert Kirk, Ishita Mediratta, Christoforos Nalmpantis, Jelena Luketina, Eric Hambro, Edward Grefenstette, and Roberta Raileanu. Understanding the effects rlhf on Ilm generalisation and diversity. 10.004552, October 2023. URL http: http///aww....g/bba/aa/a arXiv:2310.06455 [cs].
06452.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35: 22199-22213, 2022.
Vivek Kulkarni, Rami AI-Rfou, Bryan Perozzi, and Steven Skiena. Statistically significant detection of linguistic change. Proceedings of the 24th international conference on world wide web, pp- 625-635, 2015.
Yuxi Li, Yi Liu, Gelei Deng, Ying Zhang, Wenjia Song, Ling Shi, Kailong Wang, Yuekang Li, Yang Liu, and Haoyu Wang. Glitch tokens in large language models: categorization taxonomy and effective detection. Proceedings of the ACM on Software Engineering, 1(FSB):2055-209,, 2024.
Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. arXiv preprint arXiv:2305.200 20050, 2023.
13

---

Published as a conference paper at ICLR 2025
Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom. Program induction by rationale genera- tion: Learning to solve and explain algebraic word problems. arXiv preprint arXiv:1705.04144 2017.
Tania Lombrozo. Learning by thinking in natural and artificial minds. Trends in Cognitive Sciences, 2024.
The Minh Luong, Vittorio Perduca, and Gregory Nuel. Hidden markov model applications in change-point analysis. arXiv preprint arXiv: 22... 2012.
Thomas McCoy, Shunyu Yao, Dan Friedman. Matthew Hardy, and Thomas Griffiths. Embers of autoregression: Understanding large language models through the problem they are trained to solve. arXiv preprint arXiv:2309. 13638, 2023.
John X. Morris, Wenting Zhao, Justin T. Chiu, Vitaly Shmatikov, and Alexander M. Rush. Language model inversion, 2023.
Nasrin Mostafazadeh, Michael Roth, Annie Louis, Nathanael Chambers, and James F Allen. Lsdsem 2017 shared task: The story cloze test. In 2nd Workshop on Linking Models of Lexical, Sentential and Discourse-level Semantics, pp. 46-51. Association for Computational Linguistics, 2017.
OpenAl. Learning to reason with 1lss, 2024. URL https: http://pppaaaiiccaaa.a com ndex/ learning-to- cewoo-rrasoo--oe wwwhh-lmsss...
Felipe Maia Polo, Lucas Weber, Leshem Choshen, Yuekai Sun, Gongjun Xu, and Mikhail Yurochkin. tinybenchmarks: evaluating Ilms with fewer examples. arXiv preprint arXiv:2402.14999, 2024.
Anthony Sicilia, Hyunwoo Kim, Khyathi Raghavi Chandu, Malihe Alikhani, and Jack Hessel. Deal, or no deal (or who knows)? forecasting uncertainty in conversations using large language models. arXiv preprint arXhv:2402.03288. 2024.
Guy Tevet and Jonathan Berant. Evaluating the evaluation of diversity in natural language gener- ation. D.iXXiv2004.0299000 January 2021. URL SxXi::2004.02990 [es].
org abs 20000 02990.
Katherine Tian, Eric Mitchell, Allan Zhou, Archit Sharma, Rafael Rafailov, Huaxiu Yao, Chelsea Finn, and Christopher D Manning. Just ask for calibration: Strategies for eliciting calibrated confidence scores from language models fine-tuned with human feedback. arXiv preprint arXiv:2305. 14975, 2023.
Miles Turpin, Julian Michael, Ethan Perez, and Samuel Bowman. Language models don't 't always say what they think: unfaithful explanations in chain-of-thought prompting. Advances in Neural Information Processing Systems, 36, 2024.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837, 2022.
Jerry Wei, Jason Wei, Yi Tay, Dustin Tran, Albert Webson, Yifeng Lu, Xinyun Chen, Hanxiao Liu, Huang, Denny Zhou, et al. Larger language models do in-context learning differently, arXiv preprint 200.::::333003446. 2023.
Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma. An explanation of in-context learning implicit bayesian inference. arXiv preprint arXiv:2111.02080 2021.
Miao Xiong, Zhiyuan Hu, Xinyang Lu, Yifei Li, Jie Fu, Junxian He, and Bryan Hooi. Can llms express their uncertainty? empirical evaluation of confidence elicitation in 1lms. International Conference on Learning Representations (ICLR), 2024.
Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio. William W Cohen, Ruslan Salakhutdinov, and Christopher D Manning. Hotpotqa: A dataset for diverse, explainable multi-hop question answering. arXiv preprint arXiv: h 1809. 099000 2018.
14

---

Published as a conference paper at ICLR 2025
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36, 2024.
Fanghua Ye, Mingming Yang. Jianhui Pang, Longyue Wang, Derek F Wong, Emine Yilmaz, Shum- ing Shi, and Zhaopeng Tu. Benchmarking Ilms via uncertainty quantification. arXiv preprint arXiv:2401 12794, 2024.
Muru Zhang. Ofrr Press, William Merrill, Alisa Liu, and Noah A Smith. How language model hallucinations can snowball. arXiv preprint arXiv:2305. 13534, 2023.
Kaiguang Zhao. Detecting change-point, trend, and seasonality in satellite time series data to track abrupt changes and nonlinear dynamics, a bayesian ensemble algorithm. Remote Sensing of Environment, 2019.
15

---

Published as a conference paper at ICLR 2025
Appendices
A RELATED WORK
Uncertainty estimation and calibration in LLMs Previous approaches to uncertainty estimation with LLMs have provided valuable insights (Geng et al., 2024: Xiong et al., 2024; Kadavath et al., 2022; Tian et al., 2023; Guo et al., 2017; Ye et al., 2024). However, prior re-sampling based uncertainty estimation does not effectively capture the space of forking paths, for example paths that very likely to branch off of the highest probability (i.c. greedily decoded) branch. Final token probabilities or text- basdd uncertainty estimates (c.g. "70% ") likely do not capture the full picture. It may be possible to develop approaches effectively sample the space of possible paths that are simpler and/or cheaper than Forking Paths Analysis. Lastly, find parallel which strives to estimate people's 's belief uncertainty over the course of a conversation (Sicilia et al., 2024).
work in the area of conversation forecasting,
Semantic diversity in text generation Semantic diversity (Tevet & Berant, 2021; Han et al., 2022: Kirk et al., 2023) measures the degree to which a language model generates meaningfully distinct responses to the same input. We believe semantic diversity may be key cause of forking tokens, in that semantic diversity demands some degree of uncertainty in text generation. For example, diversity in CoT reasoning requires producing multiple distinct proofs.
Chain of thought and similar reasoning techniques Chain-of-Thougee (CoT) reasoning (Kojima et al., 2022: Wei et al., 2022) and related techniques prompt an autoregressive language model to reason across the intermediate tokens it generates. One challenge in CoT reasoning backtracking (Gandhi et al., 2024), where LLMs struggle 'undo' missed step. The Forking Tokens Hypothesis describes this phenomenon more broadly, where single token can trigger distribution shift such as one reasoning path over another. On the other hand, LLMs are not always faithful to their chains of reasoning in the token stream (Turpin et al., 2024). Forking Paths Analysis may be able to shed further light on these cases.
16

---

Published as a conference paper at ICLR 2025
B CHANGE POINT DETECTION MODEL DETAILS
We use an extremely efficient implementation of Bayesian multiple CPD, the Bayesian Estimator for Abrupt changes in Seasonality and Trends (BEAST). BEAST is described Zhao (2019) and available as an R package at https: /aps://crrt //crannn -- projocett org/ prg/web/ web htt//pckageesse sarees//beattte /tteast////////e/e.eee index. html. BEAST is implemented in C/C++, and we found times faster than comparable packages for multiple CPD, most of which also did not support inference of p(mly))
be between 1 10 thousand
We use BEAST to infer the posterior probability of a change point at each time p(r Al)) well as posterior of the number of change points in a time series p(mly) To estimate these posteriors, BEAST iteratively draws Monte Carlo samples j for each of the following variables, in order: the number of change points m ~ p(m())lp0i- y). change times T ~ p(r(0 (((0)))(111)1)))) 2), segment parameters př, ó ~ (36), (6)(7(5), _b--1),))) yy) and noise parameter a ~ ((00))130) (136),888 ,60), ,00, y).
We show plate notation for the structure of the BEAST CPD model in Fig. 8.
Bi, S
π
m
y/
Timestep
Segment o...
Figure 8: Plate diagram for change point model y univariate time series, m is an integer number of change points, т; E {1... b1 is the time index when a change point occurs, 0 includes model parameters such as abrupt change magnitude and polynomial trend model coefficients for segment ò = fa, (Vn-1o7)) (note: there are m + segments given m change points), is controls the variance of yt ~ N Normal(j, o). т (m) is a hyper-prior over number of change points m, and a is hyper-prior for noise
As described in Sec. 2.3, a CPD model decomposes a time series into set of m segments, and each [0... m is fit by a regression model with intercept (i.e. abrupt change) 6, and slope 8, applied to time steps between Ti-1 and Tj. In our case, we assume linear models for each segment Yt = 3, t + 6, E fr.-1..... T J, to match our assumption and qualitative observation that o, there are stable regimes of uncertainty which continue for many tokens, until o, abruptly changes to a new distribution. We also observe 'drift' in some cases, where 0r slowly changes from one distribution to another, which in model corresponds to different values of B. To our knowledge, our work is the first apply CPD to analyze neural network learning dynamics, either in-context (as in case) in-weights. (Hu al., 2023) uses Hidden Markov Models to analyze in-weights learning dynamics, which achieves a similar purpose as CPD* but with less interpretable parameters. We exciting direction for future work being further understand which statistical modeling assumptions are most appropriate for describing uncertainty dynamics in text generation.
segment E {0...
One challenge we found with using BEAST for CPD high false positive rate in cases where or has fewer changes. these cases, the drift ye has a low magnitude overall, and so very small changes in yt can show up as false positive change points when BEAST re-normalizes yr- To address this, we manually tuned noise hyper-parameter
and slightly perturb with Gaussian noise of variance .03.
In our CPD and survival analysis models, we used L2 distance. We also tested with L1 distance and K-L divergence, but found that results with d = L2 most reliably corresponded to qualitative judgments of change points in og and or
HMMSs be used for change point detection, in Luong et al.. (2012)
17

---

Published as a conference paper at ICLR 2025
C COMPARING UNCERTAINTY ESTIMATION METHODS
C.I STATIC UNCERTAINTY ESTIMATES
We now compare out outcome distribution representation or three static uncertainty estimation baselines, inspired by work such as Xiong et al. (2024). (1) We estimate the outcome distribution by re-sampling N 300 completions from the first token 0 and on. (2) We take the base path r,, append a brief string to the end Therefore, the answer is: and we take the logit probabilities for the next token as the answer certainty estimate, (3) Given the model's output (greedily decoded tokens) in (2), we then prompt the model for its confidence by appending an additional prompt For (3), we take the numeric confidence estimate and assign that confidence to the greedy token output in (2), and all other confidence to generic 'Other' outcome.
Percent confidence in final unswer:
We see in Figs. 9, 10 that in these cases with complex uncertainty dynamics and change points, the static confidence estimate (1) is significantly different from (2) and (3). This easily explained by looking ON, since the outcome distribution the beginning of the sequence Oy matches the first baseline (1), and the outcome at the end of the sequence or approximately matches (2) and (3). We also find that confidence estimates (2) and (3) assign very high certainty final answer, despite there being substantial fluctuations in uncertainty over the course of text generation.
outcome Disarib. de
Mewwrr
Miche le Honaghan
Pappy Montgemery
Robin Tunney
hmannple Rt
Uncertainty Coolidence
Last Bite Freb.
Figure 9: Comparing static uncertainty baselines to Forking Paths analysis (HotpotQA-8076:
Fig. 4) The uncertainty dynamics we observe in or (Left) are invisible to static uncertainty estimate baselines (1) (3) (Right). We also observe that baseline (1) is different from (2) and (3), with the top answer in (1) being Robin Tunney (the correct answer), whereas (2) and (3) assign near- 100% certainty to Mia Sara.
Outcome Distrib..
Other
0.0
21.0
3528.0
Racemple (e
Last Bik Prub.
Confidence
Uncartainty Beselimns
Comparing static uncertainty baselines Forking Paths analysis (GSM8K-59; Fig. 5) We see similar patterns here as in Fig. 9, with uncertainty dynamics in or (Left) that are hidden behind static uncertainty estimates (Right). In this case. (1) assigns the majority of certainty the correct answer 2/, where as (2) and (3) are near- 100% certainty in different answer 3,528.
Figure 10:
C.2 TOKEN LOGIT PROBABILITIES
simple question one might ask about forking tokens, is whether these can simply be explained as low-probability tokens which were unlikely, and when sampled caused the model to go off course.
18

---

Published as a conference paper at ICLR 2025
For this reason correlation between the change point probability at given token p(7 t y) and the token logit probability p(z; = w²) for the greedy token w". As shown in Fig. 11, we
find minimal correlation between (log) change point probability and (log) token probability. The
slight correlation we find is positive, contrary to the question above, and we note that many of the
highext-probability forking tokens also have high logit probabilities.
StoryCloze, 2Colice
HotpotQA
Change Point Prob.
-2
GSMBK
log p(r=t]]
-4
AQUA
LastLetter
MMLU
CoinFlip
-8
-10-
-12
0:0 10
-2
Token Logit Probability
Figure 11: Correlation between change point probability and token logit probability We find that token logit probability p(æ; w*) is not strongly predictive of the probability that token is labeled change point by our model p(r y). In fact we find a slight positive correlation, and that the highest probability change points also have high token logit probabilities.
C.3 COMPARING CPD AND SURVIVAL ANALYSIS
Another simple question is how our two analysis methods, change point detection (Sec 2.3) and survival analysis (Sec 2.4), compare to one another. our methods make similar predictions about which sequences have forking tokens, they might be redundant. In Sec. 2.4 we explain why survival analysis of Ot,w may provide different results from change point detection. We test this by running correlation between the estimated number of change points predicted by out change point model (i.e. the II quantile of p(m y)) and the final survival rate ((T) of a sequence. As shown in Fig. 12, find 0 correlation between which samples have low survival rates with which samples have more change points. This suggests that our two methods are identifying different forking tokens in the outcome distributions or and or, Though o, and our change point detection models given emphasis in the present work, further analysis of or may also be a promising direction for future work.
Est, Number of Change Points
StoryCloze 2Choice
HotpotQA
GSM8k
AQuA
LastLetter
2-
MMLU
CoinFlip
1-
0
1.0
0.6
0.4
0.2
0.0
Final Survival Rate S(T) with & =
Figure 12: Correlation between change point model and survival analysis. We find no correlation between the number of change points estimated by our CPD model (the .I quantile of p(m y)) and the final survival rate STT of a sequence. Each point represents single prompt and and
base path x².
19

---

Published as a conference paper at ICLR 2025
D IMPROVING COMPUTATIONAL EFFICIENCY
As mentioned in Sec. 3, the main limitation Forking Paths Analysis that it very costly in terms of number of tokens sampled. The approach we used has the token complexity: (( |a*| 1=(*)) * |x0 = w| |0*| S). where [z is the imput prompt, |x*| | is the length of the base path, [x(*) is the length of output completions, (at w| is the number of alternate tokens at an index t, and S is the number of completions sampled for each these.
For our experiments, we used S = 30 and sampled on the order of millions of tokens for each input and base path. However, one question we asked was whether smaller number of samples might serve nearly as well to identify forking tokens. As shown in Fig. 13, we find that with 10-20 samples, the number of change points our CPD model predicts is very similar to when we use 30. In other words, our experiments could be run half the cost and with similar results.
Est. Num. Changes with 30 samples
63
71
10
61
77
Changes samples
Figure 13:
Correlation between number of change points estimated with our full dataset (S=30) and estimated with smaller sample sizes $ = N For each panel, we sub-sampled N completion texts for each token and w, where < 30. Given this smaller dataset and estimated outcome distribution oz, predict the number of change points (.1 quantile of p(m y)). In red, plot Spearman's p correlation coefficient.
Additionally, we see a number of avenues for future work to improve the efficiency of Forking Paths Analysis. By using prompt caching with open-source models the token sample complexity may be reduced to O([x=) + [x(+))) * [z, w| |x=1 5) (i.e. samples will not scale by Tin). Next, it may possible use statistical models determine optimal tokens and to draw samples for. This is very similar to the problem of Optimal Experiment Design (Banga & Balsa- Balsa-Canto, 2008), which uses statistical models to determine which data should be collected most efficiently test hypothesis. More ambitiously, with open-source models we may be able to use hidden activations to predict forking tokens. Specifically, we can test whether hidden activations can predict token model predictions p(T t y). p(m y) (for our CPD model), and S(T) (for our survival analysis). If this possible, it may be possible to avoid the costly token sampling altogether, simply by analyzing model activations.
20

---

Published as a conference paper at ICLR 2025
E ADDITIONAL ANALYSES
Visualizations for all examples x" in our dataset and their respective analyses are available online through an interactive dashboard: https: /tpp:///orkkig paths streamlit.
Below, we include a subset of examples, and show or, p(r = 1ly), and highlighted text for each example x². Refer Fig. 4 for how interpret figures. Examples are hand-selected demonstrate interesting uncertainty dynamics, including change points. However, we also found many other interesting examples not shown here.
21

---

Published as a conference paper at ICLR 2025
COINFLIP
In the CoinFlip task (Fig. 15), most outcome distributions are static over the course of text generation. This task is particularly easy for GPT-3.5, and from or we conclude that, from the beginning of text generation, the LLM "decides" for certain what its final response will be.
Distribution
Quation:
up Dolann flips over dlac mut Eip
heads up?
flips the by Iniially
over manss
Change Point Prob. pic Pic-Ei>/ 1y)
Destio Eipoed
zotn lorger Nanatiaa
Index
Figure 14: CoinFlip-1033
Other
Question:
A con is heads up. Aaticia flys con over Clertta does not flip over. the oois still heads up?
Outcome
Atswer:
Let's thisk step by step. Initaily the cota heads Anlista fliss the con over, which means she turas the con over that the other side tacing This moane that the coi now tails up. Howerver Cleotha doos nor flip the ooin even, so the oein eomorns pocitio ss Aslishs ra-rail Therefone, the exen is longet beads
sime
Change Point Prob. 21--111)
tall
10
40
50
70
60
Token Index
Figure 15: CoinFlip-15426
22

---

Published as a conference paper at ICLR 2025
LASTLETTER
In the LastLetter task (Figs. 16, 17), we observe more change points than any other tasks. Many of these follow a very consistent pattern: the outcome distribution (z(x)) remains uncertain until the final answer tokens, at which point it collapses single outcome.
Distribution
Other
Quation:
Take conetiennt
Atswer:
gives by sap, separate
spint)
Marocia spatiiipptnn wonk/e "iaaaaipuee"
Change Polnt Prob.
Manso Marocia "raNNes,,
usig [word 1oo
pic Pic-Ei1/) 1y)
give elassent
worti//grtttttestt "woDDapprr wot
"wathollly
letter thejon)
Figure 16: LastLetter- 103 Correct answer: aota
Other
Cary
Question:
Take the let letter of each weod in "Soe Cassandia Cody Call" and concalcnate them.
Outcome
Atswer:
Let' dhikk step by Wil. First we neod spiit the given stilig into individual words We can use spint) methed this, which retm amy workiagl Nest, we need accnse lest interia each wond We can do this by using the charkl)) mothod and posting in indes of the bet litter which will be the longth of the wood minus 1:83. We can then concaterate these lettes logetierr using the operatoriak Finalyy we print our the concatenated string winltend' the codetaia" wel Given stringewsr se "Sue Casardat Cody Call" Spin the string mno individua! wondsimer words ser splin "yontad Innallie cmpptt aring sions the tec-sonneeeooo latioiinnoe nouil *Mramal each wond (var Dt word woodel to Get later the wortn var bell wordd charrrrrrrr Lenuhe Tian Concatcnate it result string scvall foll chle/ee
change Point Prob. pir 21
through
50
130
150
200
250
Token Index C
Figure 17: LastLetter-221 Correct answer: eayi
23

---

Published as a conference paper at ICLR 2025
AQUA
We find the complex uncertainty dynamics in the Mathematical Reasoning domains, AQuA (Figs. 18, 19) and GSM8k (Figs. 20, 21).
For the AQuA examples shown here, observe multiple changes, including changes relatively unexpected tokens. In these examples, we also observe sharp changes which occur over the course of few tokens instead of single token, e.g. the second change in AQuA-62 and the first change in AQuA-160.
Quasiion:
H.C.F LCM. oumbers and dividd
numter
Outccome Distribution
Choieca:
B] 100
125
240
F) nore thos
Amswer
Let's thisk sap by iiFins we know that the H.C L.C.MMM sumbers 50 and 100 respestivly. This meas that the
numbes lave common fattr of and thik product 100. 'sSo.
can wille two aunter 50x and Sty, whese x and are the other fictors 'nbest we gives that the fixt number (501)
change Point Prob. pir- -i
divided and fir quitian is 50. This messs Ball liTherefioe, the fist number is 50,2)
saNow, we fidd the
socond number Moniing iee L.C.M(100))
the fiot munber
(190), vio the second cumber 100 100/100 -. V.Baar wast, tis doesmn male sense becouse second number should multipl of 50 (sice his commion Sacoo 50 with the fist number). 'a8o Bill need miltiply by 59.10 get multiple 50. withorrtin,, the secord mimber x 50 inlleanee the corret answor A3
be
50
120
150
200
Token Index
Figure 18: AQuA-62 Correct answer: A
Question:
leading squad day Monday through Thurstay comperiion Saturday: average nead Friday day over foo Monday thoough Friday?
they
Distribution
Other
Choices:
by cup aqued practioos
Monday thoouh They practics swotagg
Change Point Prob. R1-1i1 11
honnsia3. sirads
Monday theouh Theeaky, thy praztiss
the LeTherefore
Friday
days Monday deough Fridaol.
75
100
12s
150
17s
Token Indiax
Figure 19: AQuA-160 Correct answer: C
24

---

Published as a conference paper at ICLR 2025
GSM8K
For GSM8K (Figs. 20, 21), similarly find complex uncertainty dynamies over text generation.
For the AQuA examples shown here, we observe multiple changes, including changes at relatively unexpected tokens. In these examples, also observe sharp changes which over the course of a few tokens instead of single token, e.g. the second change in AQuA-62 and the first change in AQuA-160.
Distribution
122
45.0
70.0
93.3
poats yiars posts
many pasts menry paos iltogehee??
goats cup by cup
goats
Change Point Prob. -ir 10)
wiwhidh
sold
laft numba lell
Tharefor,
actally negativo posts
nimba
135
Token Index
Figure 20: GSM8k-1
Correct answer: 70
Distribution
27.3
Question:
Chase and Rivkr can ride their bikes thrico a day for dayst but two other days, they ride twiez the tima they on days Hlww mony times they ride their bikes week?
Arower:
Let's thisk step by sap Walfins, we know that Chass and Rider can rike thair bikce throse day for days. This moree that for days. they rile their bikee time a day So, the ustil number tmae they rike their bikce in those 5 daspe is 3 1115 limee IntnN we know that on two other days, they ride tsice the timo ficy do on usaal days This moze that on these two dass, they ride thex brkcs 3 6 tineelll day. So, the total number of limes diey ride their bikes on these two days is
change Point Prob. pir-ci
unesiiii shiTheeffiee the sotal mumber of tiness they side their bikes in week is 15 12 27 times. So, Chese and Riãer ride dairr bluce 27 times sweck.
20
20
60
100
170
160
360
Token Index
Figure 21: GSM8k-78 Correct answer: 54
25

---

Published as a conference paper at ICLR 2025
HOTPOTQA
We find dramatic uncertainty dynamies with change points in the HotpotQA examples shown in Figs, 4, 22. However, in HotpotQA we also observe a cases where different nearly identical outcomes are expressed with different words, as Fig 23. While we tried to control for semantic variation by using powerful LLM for R(-), gemini-1.5-flasse -00, we see this as a general challenge with properly evaluating LLM performance on open-ended benchmarks. Curiously, some of these cases such Fig 23 we nonetheless observe stable and interesting uncertainty dynamies across outcomes that are only superficially distinct.
Outcome Distribution
Question:
Which famous muscciin became actor, Fiddie Vodder or Peter
Noose?
Answer
Let's think sop by sop Pirs, lets look the two options kddee Vookter and Peier Noons VedMer best knooon
vozalis priseio
hand Peart
Naore is
known
Both musicias singar
1960 pep group Hemonr's Hemmis surzcedal uanana the music inliatry
Change Paint Prob.
which one also become in noter'ansthe rnewer ieElltte Vedder
RC7 11--119 30
films, Veaker load more promizers actng carcer epparad several
Peier Noone has made pocsiceal apporaacce
shows
including "Singiea" "int the
also prosidal voice
Simporrs Music" unimated
"Curaline"
apocarancss on shows
"Poellasiis.
addition acting cares, Eddie
composed and won Goldon Cius:: sony "Currtieal from film
100 Token Index
whilk
lane dabbial
Figure 22: HotpotQA--9442 Correct answer: Peter Noone
Outcome Distribution
Other
Natallo y La Fonquetina
Noti
Natalia Lafouradd
The smit who relooord the album "Al Desporte" is sometimes known se whe??
Quention:
Latourcade
Latourcade
Answer: Let's dhik step by
1. The first step is to find out who relonea the albur "Al Despetar"
A quick scarch on the mmment nosrale thet the album was nokowed by the Mestian ainar-anpartee Natalia Ealourcale
2 Now, we seed to find our if Nanaia Lafourade has any other nancs oe aliaees that she is kavwn by. Anothes search on the intreet shoos that whe somizimcs refemal to sn "Nati lafoercede" or simply "Naadia".
Change Point Prob. pir-tii))
3. However, fiere idial mention ol are other mane also duat known by in relation the alburs 'Ai Despenaa"
& Therefore the anover to the cuestion is that Natala Ladourcade sometimes known os "Nan Latourcade" "Naalia" but there no specifia name oe alias tha das knowa by in relation the abuun 'Al Despenta""
50
75
100
175
Token Index
Figure 23: HotpotQA--0010- Correct answer: La Negra
26

---

Published as a conference paper at ICLR 2025
MMLU
Sequences in the MMLU have the second most change points (Figs 24, 25, 26), with LastLetter having the most.
Oitirr
comaor
meats people
Outcome
This for
change Point Prob. 2tr=civ9
urag toghe culy yous paie and
bockly duig apocloull
DC Tia we caery sade are spal cobik aouale villd vnliferrer thing tuke
50
100
150
200
250
300
Token Index
Figure 24: MMLU-3 Correct answer: B
Queetion
national sosccistion teought fideral againet
charpal the city with vielaing scveni frikzi connox During tria, the aserciatn'ss atturny
city sttuecy ss
Outcome Distribution
Obier
witeess aluency socttal allemcy-diant privilage objectel mation communccated
was inteneed contidereal ieeee miseet by the objections the city attorny be resaledd
fodena priviless
pivileae
folend povilege the privlegge law focum suze
detemnined by
folknal privilage the privilege fimm stais. whichever the count determines more aduiit eridence.
Chinge Point Prob. bir-tly)
Let's by stpp
deternine
spolles
appyy case being specitic
applics anorray-eteen privtlege
powor
fedendl hivillietoti cocnect privilege attomey resolved federal pervilage specifically
otjections
00
Token Index
Figure 25: MMLU-58 Correct answer: A
27

---

Published as a conference paper at ICLR 2025
Distribution
Fiistt length
nerre
Al 1im
Change Pointt Prob. -3 19)
cuscki
lia vuy satal paociegs
ck poocrape
Tie lansa wnth color Al 55% Do Sue 505L
Taken
sati, sids accuati poogl Por Thenther
Figure 26: MMLU-72 Correct answer:
STORYCLOZE
For StoryCloze, in some cases we observe change points, such as in Fig. 27, However, we also observe many cases (such Fig. 28) of different pattern, where o, gradually drifts from one distribution to another. This pattern significantly more prevalent StoryCloze than the other tasks we evaluated, which is also noteworthy since this is the only open-ended task which has no ground truth answer.
Outcone Distributtion
Quation
Wrlte story with the follwing conotmints:
1. The say mus euzth five seniences lona.
2 The say mus stat with the sentence: "Teny loves swins but
never leanted how to dive."
3. The mus end with one of fullowing two semenzoe
"Tery hups ingrvv."
"Tery las given swimiing.."
4. The las senience aust elacily one of these sentences, act repiniiiggg
Change Point Froi. vir=tlyi
Answer:
Teny loves to exem but never faamd how to dive. He world waich his Sizrd anacedally dive into the pool while avilvaddly junged One day, minds cosiinedd his to ty diving and belly Sopped, causing evesyos to luugh Enhooraee rssedd,d Tenr deciced to give swimming altogette BB realised that diving was for him and he contont with jis swimning Torry has given swimming
20
35
Token Index
Figure 27: Story Cloze-1199
28

---

Published as a conference paper at ICLR 2025
Distribution
Qustion
with conotniins:
awy exaetly five seneencss
sayy
on sentence: "Holly swvy ger
sunta
following two
gase money componatioon
sentencee cuacity sensences, Bot rephinssigg
Change Pointt Prob. 03 11)
nituctenly agroed
her Helly yellial gat
10
2
Taken Index
Figure 28: StoryCloze-1482
AGGREGATED ANALYSIS FOR NUM. CHANGE POINTS
Multiple Choice Tasks
Free Response Tasks
Easy Tasks
et of with
0.
SteryChte 2Chokee
0.6
0.6
0.6
0.
0.2
0.2
Extimated Change Points
Figure 29: Estimated number of change points m aggregated over each task We estimate the number of change points each task by taking the .1 quantile of p(mly) (rounded to the nearest integer) for each prompt and base path x=". We then compute the fraction of all examples in task with each estimated number of change points.
In Fig 29, we show aggregate results for each task, estimating the number of change points. Intuitively, this serves as aggregating the posterior p(mly) over all data points y in a single task. These results are computed by taking single point estimate for the number of change points which in Fig 29 the quantile
Bayes factor of between p(m 2 m' (y)/ (m < m my), where m' is the estimate for m, similar hypothesis testing method described in Sec. 2.3.
p(mlly). Note that the II quantile is equivalent
29

---

Published as a conference paper at ICLR 2025
F ANALYSES WITH VARYING THRESHOLDS
In Fig. 30, we show results for Figs. 6, 29 with varying threshold parameters. In the case of the change point time (Left plots), the threshold used convert p(T = f|m) into a binary indicator for whether the change point probability is above some threshold. For the number of change points (Right plts), the threshold we vary is the quantile of p(mlyy used to compute single point estimate for the number of change noints in secnence. y. ComPhi
Lasti etter
Cointiip
Lastl etter
0.50
0.5
0.25
0.00
0.00
GSM6k
AQUA
GSKSK
0.4
% of tramples with 1s change Point at
Examptes Change Points
0.2
0.0
0.0
MXLU
HotpotQA
2.4
MIALU
0.50
HotpotQ4
0.2
0.25
0.0
0.0-
0.00
StoryChaee,Choic
pte Threshold
StaryGiore_ 2Choice
Quantile
0.3
0.1
2.5
0.7
0.5
0.9
0.7
8.0
0.99
0.0 1.0
09
3
Normalized Taken Index
Estimated Change Points m
Figure 30: Task-level estimates of CPD model results, varying threshold levels Here we show the results of Figs. 6, 29 while varying the thresholds we use for each. (Left) Varying the change point probability threshold for p(T = t/m), and (Right) varying the quantile used to estimate m
30

---

Published as a conference paper at ICLR 2025
G EXPERIMENT DETAILS
This sections lists the specific prompts used for completions, prompts for collecting outcome rep- resentations R(-), and finally answer cleansing functions used to parse outcomes into minimal answers.
COMPLETION PROMPTS
Below prompts used for sampling the base path xt well completions x/ Vt, used to for Forking Paths Analysis.
Standard CoT Prompt (LastLetter, GSM8k, HotpotQA)
Question: (question]
Answer: Let's think step by step.
Multiple Choice CoT Prompt (AQuA [5 choice], MMLU [4 choice]
Question:
(question)
Choices:
A) (A)
B) [B]
C) [C]
D) (D)
(E)
Answer: Let's think step by step.
StoryCloze 2-Choice Prompt
Question:
Write story with the following constraints:
The story must be exactly five sentences long.
2. The story must start with the sentence: "I first sentence
The story must end with one of the following two sentences:
"[
last sentence }
-"I "f last sentence }
4. The last sentence must be exactly one of these sentences, not rephrasing.
Answer: first sentence
OUTCOME REPRESENTATION PROMPTS
The following prompts used for extracting outcome representations R(-) from second LLM. In our case, for cost efficiency the second LLM uses the ChatCompletions API format (messages dictionaries) instead of Completions (single text string).
31

---

Published as a conference paper at ICLR 2025
Yes/No Outcome Prompt (CoinFlip)
[(
'role': 'user', 'content'; < full_qa_text >
b
'role': 'user', 'content': 'Wat is the final choice (Yes or No) in the
Answer in the previous message?'
b
'role': 'system', ccontent: 'Respond with single- word Yes or No if possible.'
11
Generic QA Outcome Prompt (LastLetter, HotPotQA)
[[
'role': 'user', 'content': full_qa_text
b
'role': 'user', 'content'; 'What is the final answer to the Question given in the Answer in the previous message? Be brief.'
b 'role': 'system',
'content: 'Respond with only the final answer, if possible. Be brief in your response, not include unnecessary text.'
H]
Multiple Choice Outcome Prompt (AQuA, MMLU)
[[
'role': 'user', 'content': full_qa_text
b,
'role': 'user',
'content': 'What is the final choice (A, B, C, or D) at the end of the Answer the previous message?'
b, 'role': 'system', cconeent 'Respond with single-word word multiple choice answer if possible: A, B, C or D.
}]
* Note: AQuA prompts instead specify A.B.C.D,E
32

---

Published as a conference paper at ICLR 2025
Numeric Outcome Prompt (GSM8K)
[[
'role': 'user', 'content'; < full_qa_text >
b 'role': 'user',
'content': 'Waat is the final answer given in the Answer in the previous message?'
b 'role': 'system',
'content: 'Respond only with a number if possible. Do not include units such as "$".'
}]
Story Ending Outcome Prompt StoryCloze")
rroe'' 'user', [[
'content': full_ga_text.
b
'role': 'user', 'content': 'Which of the following two sentences matches the ending of this story?'
f'Anl. " last sentence "
f'In2. < last sentence 2 >
b 'role' 'system', 'content': 'Respond with single word, either 1 or 2.
11
ANSWER CLEANSING FUNCTIONS
Here list the 'answer cleansing" functions that used parse final answers from the extracted outcome representations R(-). Even with the structured outcome prompts listed in the prior section, the L.MS used for R(-) have tendency occasionally respond verbosely even when instructed otherwise. For this reason, we design simple functions to extract, e.g. numeric values from GSM8k responses are parsed that equal values are represented equivalently (e.g. R(x1) = "I.0" and R(x2) = ")"). This method is adopted from Kojima et al. (2022) (Appendix A.6), and the numeric and multiple choice answer cleansing functions we used modified versions of their functions.
Also note that we label all outcomes which cannot be parsed, or which are outside top 6 most probable in 0z, as the value 'Other'.
Standard Answer Cleansing Function
def base_ans_ ans fn _an__fnnss_ (s):
(s. ('plit('answea)) is ()[]] rellacee (!s', ")) if 'answer is in else s) s.strip() if (sn <= 1:
return
if s[-1] == 1.:: s s[:-1]
return
33

---

Published as a conference paper at ICLR 2025
Multiple Choice Answer Cleansing Functions
def abed fn (s, other_tok- *xthkr)) s = s.strip() return if in ('A', 'B', 'C', 'D") else other_tok
def abcde_fme fn (s, "ahher_tk==*Othae
= s.strip()
return s if s in ('A', 'B', 'C', 'D', 'B') else other_tck
Numeric Answer Cleansing Function
import re
def numeric_fn (s)
pred
pred
"")
pred [s for in re. findall (r1-? Mld+ pred)
if le (pred) 0:
return str (float (pred[01))
return
Answer Cleansing Function for LastLetter Task
def last_letter_ans fn (s)
s s. s.lower() ()
s = s.pell (!",, !!
s s.relaace ("!" !1)
= s. a.replace
11)
if 'answer is' in s:
s.split ('answer is') [1] if 'message is' in s:
s.split ('message is [1]
8. replace 11
return 8 loer () .stripp) ()
34


Reviews:
[{"review_id": "BQ7mS3EweO", "reviewer": "Reviewer_5J1y", "summary": "This paper poses an intriguing question: are there time steps $t$ that, if altered, would significantly impact the sequence completion $x_{>t}$? The authors find that such points, referred to as \"forking tokens\" in their work, do indeed exist. Additionally, they propose a method to automatically detect these forking tokens using a change point detection (CPD) model. More specifically, they derive a time series $y_t = \\text{Dist}(o_0, o_t)$, where $o_0$ and $o_t$ represent the expected answer distributions when tokens are changed at time steps 0 and $t$, respectively. They then train two models, $p(\\tau = t | y)$ and $p(m \\geq 1 | y)$, to predict the likelihood of a forking token occurring at time $t$ and the number of forking tokens, respectively. The authors demonstrate several interesting cases of their method across extensive datasets.", "questions": "It is also interesting to note that most forking tokens detected are entities. However, certain entities that may be important to humans, such as \"June 19, 1972\" in Figure 4 (lines 276–277), were not detected by the algorithm. Is there an explanation for this?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "1. The research question in this work is compelling because forking tokens are important for understanding model behaviors and steering model generation.  \n2. The approach of detecting forking tokens with CPD models is also innovative.", "weaknesses": "The core contribution of this paper is already intriguing, so the following weakness is likely minor.\n\nThe method section is somewhat difficult to follow. In Section 2.2, I struggled due to insufficient explanation of the connection between the definition of $o_t$ and the subsequent detection method at the beginning of Sec. 2.2. While the high-level concept in lines 247–259 is more understandable, some details remain unclear. For instance, defining $\\tau_{i-1}$ and $\\tau_i$ as the start and end of segment $i$ made it difficult to interpret $\\tau$ in $p(\\tau = t | y)$. It may affect the reproduce of their method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jh1HAFKtDo", "reviewer": "Reviewer_rCUA", "summary": "This paper proposes the Forking Tokens Hypothesis, that there exist some tokens the prefix such that changing them will lead to dramatic differences in the suffix. They use this hypothesis to study uncertainty estimation in the model's output sequences. Technical-wise, they use Bayesian change point detection and survival analysis to identify the location and number of forking tokens.", "questions": "see the weakness section.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The paper formulate a interesting and (I think) novel hypothesis about forking tokens, that there are a few sparse but critical tokens that will determine the trajectory of the generation, and uncertainty estimation should depend on these critical tokens. \n2. The estimation method (finding the critical forking token) seems statistically motivated and sound.", "weaknesses": "1. I think the method section is written in a very unclear way. For example, the Bayesian formulation in line 258 can be better described. The Gibbs sampling step is also very unclear. There seem to be lots of details missing. A related question: why use linear regression for the CPD? The math in the survival analysis part makes sense, but still lacks all the execution details: what is d? and what are the pros and cons of these two approaches? \n2. I agree that the forking theory is interesting, but I think the motivation of the paper is to use it for better uncertainty estimation. but no experiment directly ties these two parts together. It would be great to add an experiment about using the forking tokens to recalibrate the model, and yield higher calibration score. Otherwise, I don't quite buy the connection between forking theory and uncertainty estimation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XLfJdIb9lv", "reviewer": "Reviewer_5yCK", "summary": "This article innovatively proposes to analyze the uncertainty of language model generation by analyzing the intermediate steps of LLM decoding. Around the defined forking tokens hypothesis, the authors have built a pipeline and designed CPD to study the uncertainty behavior of language models in different inference tasks. The experimental results demonstrate some very interesting conclusions and provide a comprehensive discussion on the impact of this method on future work.", "questions": "No question", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The assumption in this article is quite important, and the pipeline constructed to validate the assumption and the evaluation metrics are very interesting\n* The experimental analysis in this article is detailed and comprehensive.\n* The assumption in this article is very interesting and significant.", "weaknesses": "The evaluation of the uncertainty of language models designed in this article requires sampling a large number of generated results for different tokens and conducting evaluation analysis. Therefore, the cost of evaluating a single sample is also enormous, which may affect the scalability of this work. However, this does not negate the innovativeness of this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)