Can One Token Make All the Difference? Forking Paths in Autoregressive Text Generation

Authors: eric  bigelow
ari  holtzman
hidenori  tanaka
tomer  ullman
Venue: EMNLP_2024_Workshop_BlackBoxNLP
Published: 2024-08-20 03:34:24

Abstract: Analyzing uncertainty is essential for properly evaluating and safely using Large Language Models (LLMs). When an LLM generates some text, we might ask what alternate text could it have produced during the decoding process? Would an LLM generate a very different response if even just one token was sampled differently? We present a novel approach to understanding uncertainty in autoregressive text generation through a black-box methodology we call Forking Paths Analysis. Our method involves a multi-stage LLM sampling architecture, followed by the aggregation of samples into a multivariate time series representing the outcome distribution, and concludes with the application of change point detection to pinpoint tokens where the distribution shifts suddenly. We apply Forking Paths Analysis to questions from 7 datasets commonly used to evaluate LLMs. Our analysis reveals striking uncertainty dynamics over the course of text generation, including dramatic change points where one token can make all the difference.

Main paper: 
 : 
 Background Large Language Models (LLMs) are often treated as black boxes with mysterious capabilities that emerge during next-word prediction, and a good deal of current research is devoted to interpreting and understanding LLM text generation behavior. One way to assess a black box system is to consider what possible things it could have done, but didn't. In text generation, we can liken the a text sequence to a path the system took through semantic space, and ask: what other paths could the system have taken? Are there key forking points where re-sampling the system at that specific token, but not others, would lead to very different paths? We propose a novel methodology for answering these questions with what we call Forking Paths Analysis (Borges, 1941) .The most common method for estimating uncertainty in LLMs is to sample a single text output, and inspect logit probabilities for the final answer token (e.g. p("Yes") or p("No") given 'So, the answer is _") (Kadavath et al., 2022; Hu and Levy, 2023) . A less common approach is to sample a batch of output texts using stochastic decoding, and compute a histogram over final answers (Wang et al., 2023; Xiong et al., 2023) . However, the first method does not explain how an LLM can generate two distinct solution attempts for a problem. The uncertainty will not be reflected in the last token of each output, since that token will be deterministic given the proof preceding it. The second method explains uncertainty in the final answer, but ignores the rest of the text preceding the answer. For many LLM uses, such as proving a theorem, the steps leading to the final answer can be as important as the answer itself. By contrast, our Forking Paths Analysis considers both individual token sequences as well as final outcome distributions. This method offers a detailed view into the uncertainty dynamics underlying each step of text generation, and enables us to test the hypothesis that individual tokens are pivotal in that re-sampling at specific points can send text generation in a very different direction. Our Forking Paths Analysis does not require access to an LLM's internal activations, and relies only on logit probabilities available in some black-box LLM APIs (also see Morris et al. (2023) ). Our primary contributions: (a) a novel method, Forking Paths Analysis, for understanding uncertainty in text generation by representing it as multivariate time series aggregated over many samples, and by (b) applying change point detection models to statistically test the hypothesis that there are sharp change points in text generation; (c) we use Forking Paths Analysis to demonstrate striking dynamics in text generation, including significant change points where a single token dramatically affects subsequent text. Methods Conditional re-sampling (Fig. 1 , Part 1) proceeds in three stages: (1) sample a base text sequence x * and collect token logit probabilities p(x t = w|x * <t ) for the top-k tokens w at each index t, (2) for each index t and each alternate token w where p(x t = w|x * <t ) > ϵ is greater than some threshold ϵ, draw S samples of alternative text completions xEQUATIONfor all completions concatenated with their input text, extract an outcome representation R(x * <t , x t = w, x>t ), where R may be a one-hot embedding for the final answer extracted using another LLM, or R may be a semantic embedding vector.We define outcome distributions o t for individual token indexes t as weighted vector representations:EQUATION>t ) In the tasks shown here, R(x) is a one-hot encoding of the answer in x (e.g. 'A', 'B', 'C', 'D'), extracted using a secondary LLM with a prompt template. In future work, we will explore openended text generation tasks where R(x) is instead a dense vector embedding of x.We use o t to test the hypothesis that there are specific change points t where text generation shifts suddenly. First, we convert o t into a univariate time series for tractable multiple Change Point Detection (CPD) (Fearnhead, 2006) using a semantic drift metric (Kulkarni et al., 2015) . Each point in the shift series y t = d(o 0 , o t ) is the distance between the initial outcome distribution o 0 and subsequent time steps o t , given a distance metric d. We then run Bayesian CPD (Zhao et al., 2019) Experiments We present preliminary results for experiments on gpt-3.5-turbo-instruct-0914 using 7 datasets used for evaluating LLMs across a wide range of domains: Symbolic Reasoning (Wei et al., 2022) , Math. Reasoning (Ling et al., 2017; Cobbe et al., 2021) , Complex Question Answering (Hendrycks et al., 2020; Yang et al., 2018) , and Story Generation (Mostafazadeh et al., 2017) 1 . For the first 6 tasks, we add a zero-shot CoT prompt (Kojima et al., 2022) . x * is greedily decoded. We show results for 5 -15 prompts for each of 7 tasks (S=30, ϵ=.05), and soon will have results for 100 prompts each. Note each question in our dataset aggregates over millions of sampled tokens. In many o t , we observe dramatic non-linear uncertainty dynamics over the course of text generation. In time series such as AQuA-60927, we see a pattern where the LLM is equally uncertain across answers until one token is generated. In others such as HotpotQA-79442 and LastLetter-342, we see patterns where one stable regime of certainty maintains for dozens or hundreds of tokens, before shifting to another stable regime, and then a third or fourth regime (see App. B). These dynamics may suggest in-context model selection (Bigelow et al., 2024) . In many time series, particularly in CoinFlip and StoryCloze, we see minimal uncertainty with no obvious change points. We find more change points in some tasks than others (Table 1 ).The rich token-level uncertainty dynamics we see in our Forking Paths Analysis show us how black-box LLMs can 'fork' during text generation and transition suddenly from one pattern to something quite different. At the edge of this transition, even a single token can make all the difference. across alternate tokens w.To compute outcome representations, we aggregate samples into distributions -weighted vector representations -over token indexes (o t ) and alternate tokens (o t,w ):EQUATION>t )Outcome Distr.After de-duplicating samples, we weight by (a) the average next-token probability for sampled completions, normalized by number of tokens T in sample xEQUATIONt+1:t ′ ) 1/Tas well as (b) single next-token probability for alternate tokens p(x t = w|x * <t ) (Fig. 3 ). Note that o t is the main subject of this work, but we also use o t,w for an alternate Forking Tokens Analysis approach in App. C.Below, we show a Forking Paths Analysis (FPA) for one example each of all 7 of our datasets. The first 5 examples are hand picked to show change points. However, these 5 examples are taken from a relatively small sample (5-15 questions per task) which includes other change point FPA results not shown here.Examples for the first 5 datasets -GSM8k (Fig. 4 ), AQuA (Fig. 5 ), LastLetter (Fig. 6 ), MMLU (Fig. 7 ), and HotpotQA (Fig. 8 For the AQuA and LastLetter examples, we see a pattern of stable uncertainty for a long period, followed by a sudden collapse into high certainty. Note that for LastLetter, the high probability on Other is the amount of probability mass unassigned across tokens with less than ϵ next-word probability. In the case of AQuA-60927, this collapse to B (green; also the correct answer) occurs when a key token in the final answer is sampled -the first digit of $4,500. In the case of LastLetter-342, the second mode collapse occurs when sampling tokens in the final answer nlyhth. However, the first change in LastLetter-342 follows a different pattern, instead moving from a moderately high certainty regime to very low certainty. This change occurs when two seemingly innocuous return symbols . . . Elisabeth".split() \n ``\n \n Next, we need . . . are generated. The distribution suddenly shifts from ∼ 50% confidence in olah (the correct answer) to low certainty across answers (blue area in Fig. 6 ).We see additional change points and sudden transitions between stable regimes in the examples for GSM8k, MMLU, and HotpotQA. In GSM8k-97 (Fig. 4 ) we see the correct answer 70 (brown) hold 20 -30% of the overall probability mass for a few dozen tokens, before suddenly disappearing after 2x = 40 is sampled, being replaced by the answer 54 (purple). Eventually \n \n Now, we can is sampled and this answer disappears as the LLM collapses into full certainty of 46 (red). The change point at 2x = 40 might be expected since this token is key in articulating a certain chain of reasoning.However, the token at \n \n Now, we can is more surprising.In MMLU and HotpotQA examples, we see regimes of stable outcome distributions that suddenly collapse to high certainty in a single answer. For MMLU-32, this occurs at a perhaps surprising time, after the word scenario is generated in as of 2020. In scenario 2, the main character. In HotpotQA-79442 we see a striking pattern where the correct answer Peter Noone is at first the dominant response (red area). First it seems to gradually drift towards the alternate response, Eddie Vedder (orange), but then at two points it sharply jumps. The first of these tokens is surprising, in a relatively inert seeming down, whereas the second change point is a token in the final answer: Both musicians have had successful careers in the music industry, but which one also became an actor?\n \n The answer is Eddie Vedder.Finally CoinFlip-61 and StoryCloze-274 show example time series with no significant forking points. Time series such as these help us benchmark our Change Points Detection model, since we expect there to be no change points in these series One common theme of our observed change points is that some are at times we might expect, key meaningful words which distinguish between chains of reasoning or themes in text generation. Other change points are at times we might not expect, seemingly innocuous words such as Now or minor tokens such as punctuation and escape characters \n \n. Tokens such as this may relate to distinctions between surface and content forms (Holtzman et al., 2021) , vaguely analogous to syntax (surface form) and semantics (content) in natural language. Following this intuition, $4,500 or 2x = 40 may be examples of 'content' token that clearly distinguishes between multiple underlying content forms, whereas . . . Elisabeth".split() \n `\n \n Next, we need . . . and \n \n Now, we can are examples where a 'surface' token is distinguishing between latent content forms. First, we need to find the total number of students who passed the test. We know that 340 third graders and 40 fourth graders passed, so that's a total of 340 + 40 = 380 students.\n\nNext, we need to find the pass rate for the fifth graders. We are told that their pass rate was twice the fourth graders' pass rate, so we can set up the equation 2x = 40, where x represents the fourth graders' pass rate. Solving for x, we get x = 20. This means that the fifth graders' pass rate was 20%.\n\nNow, we can find the total number of fifth graders who passed by multiplying the total number of fifth graders (400) by the pass rate (20%). This gives us 400 x 0.20 = 80 fifth graders who passed. \n\nFinally, we can find the overall pass rate by adding the number of students who passed from each grade (380 + 80 = 460) and dividing by the total number of students (500 + 100 + 400 = 1000). This gives us an overall pass rate of 460/1000 = 46%.\n\nTherefore, the overall pass rate for Herbert Hoover Elementary School's annual standardized test is 46%.(c) Change point detection probabilities p(τ = t). Red is high probability, yellow is low.First, we need to find the total number of students who passed the test. We know that 340 third graders and 40 fourth graders passed, so that's a total of 340 + 40 = 380 students.\n\nNext, we need to find the pass rate for the fifth graders. We are told that their pass rate was twice the fourth graders' pass rate, so we can set up the equation 2x = 40, where x represents the fourth graders' pass rate. Solving for x, we get x = 20. This means that the fifth graders' pass rate was 20%.\n\nNow, we can find the total number of fifth graders who passed by multiplying the total number of fifth graders (400) by the pass rate (20%). This gives us 400 x 0.20 = 80 fifth graders who passed. \n\nFinally, we can find the overall pass rate by adding the number of students who passed from each grade (380 + 80 = 460) and dividing by the total number of students (500 + 100 + 400 = 1000). This gives us an overall pass rate of 460/1000 = 46%.\n\nTherefore, the overall pass rate for Herbert Hoover Elementary School's annual standardized test is 46%.(d) Token logit probabilities. Red is low probability, yellow is high. (b) Prompt: AQuA question 60927 \nFirst, we need to find the rate of filling for each inlet. \nWith both inlets open, the tank is filled in 36 minutes. This means that in 1 minute, both inlets together fill 1/36 of the tank. \nOn the other hand, the first inlet alone fills the tank in 2 hours, which is 120 minutes. This means that in 1 minute, the first inlet fills 1/120 of the tank. \nNow, we know that the second inlet admits 50 cubic meters of water more than the first inlet in every minute. This means that in 1 minute, the second inlet fills 1/120 + 50 = 1/120 + 1/2 = 61/120 of the tank. \nSince we know that both inlets together fill 1/36 of the tank in 1 minute, and the second inlet fills 61/120 of the tank in 1 minute, we can set up the following equation: \n1/36 + 61/120 = 1/x \nWhere x is the capacity of the tank. \nSolving for x, we get x = 4,500. \nTherefore, the capacity of the tank is 4,500 cubic meters. \nThe correct answer is B) 4,500.(c) Change point detection probabilities p(τ = t). Red is high probability, yellow is low.\nFirst, we need to find the rate of filling for each inlet. \nWith both inlets open, the tank is filled in 36 minutes. This means that in 1 minute, both inlets together fill 1/36 of the tank. \nOn the other hand, the first inlet alone fills the tank in 2 hours, which is 120 minutes. This means that in 1 minute, the first inlet fills 1/120 of the tank. \nNow, we know that the second inlet admits 50 cubic meters of water more than the first inlet in every minute. This means that in 1 minute, the second inlet fills 1/120 + 50 = 1/120 + 1/2 = 61/120 of the tank. \nSince we know that both inlets together fill 1/36 of the tank in 1 minute, and the second inlet fills 61/120 of the tank in 1 minute, we can set up the following equation: \n1/36 + 61/120 = 1/x \nWhere x is the capacity of the tank. \nSolving for x, we get x = 4,500. \nTherefore, the capacity of the tank is 4,500 cubic meters. \nThe correct answer is B) 4,500.(d) Token logit probabilities. Red is low probability, yellow is high. First, we need to separate the words in the given string. We can do this by using the split() method, which will create a list of words.\n\n```\nwords = "Lino Mariel Aditya Elisabeth".split()\n```\n\nNext, we need to access the last letter of each word. We can do this by using the index -1, which will give us the last element of the list.\n\n```\nlast_letters = [word[-1] for word in words] \n```\n\nNow, we have a list of the last letters of each word. We can use the join() method to concatenate them into a single string.\n\n```\nconcatenated = "".join(last_letters)\n```\n\nFinally, we can print the result. \n\n```\nprint(concatenated)\n```\n\nThe output will be: \n\n```\nnlyhth\n```\n\nSo, the final code will be:\n\n```\nwords = "Lino Mariel Aditya Elisabeth".split()\nlast_letters = [word[-1] for word in words] \nconcatenated = "".join(last_letters)\nprint(concatenated)\n``( c) Change point detection probabilities p(τ = t). Red is high probability, yellow is low.First, we need to separate the words in the given string. We can do this by using the split() method, which will create a list of words.\n\n```\nwords = "Lino Mariel Aditya Elisabeth".split()\n```\n\nNext, we need to access the last letter of each word. We can do this by using the index -1, which will give us the last element of the list.\n\n```\nlast_letters = [word[-1] for word in words] \n```\n\nNow, we have a list of the last letters of each word. We can use the join() method to concatenate them into a single string.\n\n```\nconcatenated = "".join(last_letters)\n```\n\nFinally, we can print the result. \n\n```\nprint(concatenated)\n```\n\nThe output will be: \n\n```\nnlyhth\n```\n\nSo, the final code will be:\n\n```\nwords = "Lino Mariel Aditya Elisabeth".split()\nlast_letters = [word[-1] for word in words] \nconcatenated = "".join(last_letters)\nprint(concatenated)\n``( d) Token logit probabilities. Red is low probability, yellow is high. In scenario 1, the main character is cheating on their wife by giving flowers to their girlfriend. This is considered morally wrong according to ordinary moral standards in the US as of 2020. In scenario 2, the main character is plagiarizing by copying and pasting sources from the internet without proper citation. This is also considered morally wrong according to ordinary moral standards in the US as of 2020. Therefore, the correct answer is A) Wrong, Wrong.(c) Change point detection probabilities p(τ = t). Red is high probability, yellow is low.In scenario 1, the main character is cheating on their wife by giving flowers to their girlfriend. This is considered morally wrong according to ordinary moral standards in the US as of 2020. In scenario 2, the main character is plagiarizing by copying and pasting sources from the internet without proper citation. This is also considered morally wrong according to ordinary moral standards in the US as of 2020. Therefore, the correct answer is A) Wrong, Wrong.(d) Token logit probabilities. Red is low probability, yellow is high. First, let's look at the two options: Eddie Vedder and Peter Noone. Eddie Vedder is best known as the lead vocalist and guitarist of the rock band Pearl Jam. Peter Noone is best known as the lead singer of the 1960s pop group Herman's Hermits. Both musicians have had successful careers in the music industry, but which one also became an actor?\n\nThe answer is Eddie Vedder. While Peter Noone has made occasional appearances in TV shows and films, Eddie Vedder has had a more prominent acting career. He has appeared in several films, including "Singles" and "Into the Wild," and has also provided voice work for animated films such as "Coraline" and "The Simpsons Movie." He has also made guest appearances on TV shows like "Twin Peaks" and "Portlandia."\n\nIn addition to his acting career, Eddie Vedder has also composed music for films and has won a Golden Globe for his song "Guaranteed" from the film "Into the Wild." So while both musicians have dabbled in acting, Eddie Vedder is the one who has had a more successful and prominent career in the field.(c) Change point detection probabilities p(τ = t). Red is high probability, yellow is low.First, let's look at the two options: Eddie Vedder and Peter Noone. Eddie Vedder is best known as the lead vocalist and guitarist of the rock band Pearl Jam. Peter Noone is best as lead singer of the 1960s pop group Herman's Hermits. Both musicians have had successful careers in the music industry, but which one also became an actor?\n\nThe answer is Eddie Vedder. While Peter Noone has made occasional appearances in TV shows and films, Eddie Vedder has had a more prominent acting career. He has appeared in several films, including "Singles" and "Into the Wild," and has also provided voice work for animated films such as "Coraline" and "The Simpsons Movie." He has also made guest appearances on TV shows like "Twin Peaks" and "Portlandia."\n\nIn addition to his acting career, Eddie Vedder has also composed music for films and has won a Golden Globe for his song "Guaranteed" from the film "Into the Wild." So while both musicians have dabbled in acting, Eddie Vedder is the one who has had a more successful and prominent career in the field.(d) Token logit probabilities. Red is low probability, yellow is high. Initially, the coin is heads up. When Mateah flips the coin over, it will now be tails up. Then, when Hallsten flips the coin over, it will be heads up again. So, the coin is still heads up after both Mateah and Hallsten have flipped it over.(c) Change point detection probabilities p(τ = t). Red is high probability, yellow is low.Initially, the coin is heads up. When Mateah flips the coin over, it will now be tails up. Then, when Hallsten flips the coin over, it will be heads up again. So, the coin is still heads up after both Mateah and Hallsten have flipped it over.(d) Token logit probabilities. Red is low probability, yellow is high. She would often daydream about swimming in the crystal clear water and hosting pool parties with her friends. However, her parents always said they couldn't afford it. One day, Kelsi's parents surprised her with a brand new pool in their backyard. Kelsi was overjoyed and spent every day swimming and playing in her new pool. She even invited her friends over for a pool party, and they all had a blast. Kelsi loved her new pool.(c) Change point detection probabilities p(τ = t). Red is high probability, yellow is low.She would often daydream about swimming in the crystal clear water and hosting pool parties with her friends. However, her parents always said they couldn't afford it. One day, Kelsi's parents surprised her with a brand new pool in their backyard. Kelsi was overjoyed and spent every day swimming and playing in her new pool. She even invited her friends over for a pool party, and they all had a blast. Kelsi loved her new pool.(d) Token logit probabilities. Red is low probability, yellow is high. Our Forking Tokens Analysis (FTA) considers o t,w rather than o t , as in our Forking Paths Analysis (FPA). Fig. 11 offers a visual intuition for o t,w and how individual tokens w can fork, in addition to token indexes t as in FPA.For this, we consider whether, for a given token index t, alternate tokens w being sampled cause the outcome distribution o t,w to deviate from the greedy outcome distribution o t,w * by at least some threshold ε. Following this, we define the forking survival function S(t) as the probability that, across t, text generation 'survives' forking from o t,w * to a very different outcome distribution o t,w :S(t) = 1 - t t ′ =1 E w o t ′ ,w ̸ ≈ o t ′ ,w * = 1 - t t ′ =1 w p(x t ′ = w|x * <t ′ ) 1 d(o t ′ ,w , o t ′ ,w * ) > εThis is loosely analogous to our semantic drift transformation y t = d(o 0 , o t ) in FPA, where o 0 was the base distribution and o t was the alternative when computing y t . In FTA, instead we have o t,w * as the base and o t,w as the alternative.In Fig. 12 we see that survival rate for this sequence goes to 0 over even very high thresholds -Note that a distance of ε = .7 for L 1 distance d is very high since vectors o t,w * and o t+1,w ) are normalized to sum to 1. We alter StoryCloze to instead request short stories beginning with 1 specified sentence and ending with 1of 2 equally plausible final sentences. 
 
 Appendix: