Deciphering the Factors Influencing the Efficacy of Chain-of-Thought: Probability, Memorization, and Noisy Reasoning (2024)

Abstract: Chain-of-Thought (CoT) prompting has been shown to enhance the multi-step reasoning capabilities of Large Language Models (LLMs). However, debates persist about whether LLMs exhibit *abstract generalization* or rely on *shallow heuristics* when given CoT prompts. To understand the factors influencing CoT reasoning we provide a detailed case study of the symbolic reasoning task of decoding shift ciphers, where letters are shifted forward some number of steps in the alphabet. We analyze the pattern of results produced by three LLMs—GPT-4, Claude 3, and Llama 3.1—performing this task using CoT prompting. By focusing on a single relatively simple task, we are able to identify three factors that systematically affect CoT performance: the probability of the task’s expected output (probability), what the model has implicitly learned during pre-training (memorization), and the number of intermediate operations involved in reasoning (noisy reasoning). We show that these factors can drastically influence task accuracy across all three LLMs; e.g., when tested with GPT-4, varying the output’s probability of occurrence shifts accuracy from 26% to 70%. Overall, we conclude that CoT prompting performance reflects both memorization and a probabilistic version of genuine reasoning.

## introduction reasoning, one of the key aspects of human intelligence, is the process of thinking about something logically and systematically using evidence and past experiences to make a decision @xcite @xcite . the impressive performance of large language models (llms) across a wide range of tasks has spurred extensive research into their reasoning capabilities @xcite . it remains unclear whether the behavior of these systems is based on true reasoning or on shallow heuristics. some results provide evidence that llms are able to reason @xcite @xcite , while others show that they still struggle on tasks that humans can easily solve via reasoning @xcite @xcite @xcite . the chain-of-thought (cot; @xcite ) prompting strategy has played a significant role in this debate. cot involves prompting an llm to generate a sequence of intermediate reasoning steps before producing the final answer, given some in-context exemplar(s) of how to break the task into steps. cot and its several variants @xcite @xcite have been shown to substantially improve performance over standard prompting. recent works have tried to identify which aspects of the demonstration contribute to cot's enhanced performance @xcite @xcite , typically relying on assessing performance across a wide range of tasks. in this work, we take a different approach: we present an extensive case study on a single task that allows us to disentangle reasoning from memorization. the task we selected is solving shift ciphers, a simple type of code in which each letter is shifted forward a certain number of positions in the alphabet (figure 1 , panel 1). we choose this task because it allows us to independently manipulate several factors that could be relevant for characterizing how llms solve reasoning tasks when prompted with cot: difficulty, frequency, and answer probability. our results suggest that cot performance reflects three factors: probability, memorization, and noisy reasoning. first, the accuracy of cot is affected by the probability of the correct output, with more probable outputs resulting in a stronger effect of cot. second, performance is higher when mem- shift cipher task number domain standard prompting chain-of-thought: probabilistic and memorization-influenced noisy reasoning example: cat fdw gpt-4 predicted signature of noisy two-way reasoning ~input/output: text messagen ~prompt: only description a b x y z c a b c d e f encoding decoding rot-3 ~input/output: number sequencen ~prompt: description + math formula + demonstration ~input/output: text messagen ~prompt: description + demonstration higher accuracy for frequently seen shifts (particularly 13) predicted signature of memorization effects overall decoding performance across different probability bins higher accuracy for high prob higher accuracy on smaller shifts predicted signature of probabilistic effects (3) however, gpt-4 scores nearly perfectly on an isomorphic task based on numbers rather than letters. (4) with cot prompting, gpt-4 adopts probabilistic and memorization-influenced noisy reasoning. that is, its performance (right) combines the trends we have hypothesized for each of the three factors on the left. orization is possible, as indicated by the frequency of encountering different shift cipher variants during pre-training. the effects of probability and memorization show that cot performance is not fully systematic abstract reasoning. nonetheless, cot performance is not solely driven by superficial heuristics: it also shows some hallmarks of true reasoning-albeit a noisy version of true reasoning, in which the error rate increases along with task difficulty (where we quantify task difficulty by the number of implicit reasoning steps involved). in addition, we find evidence that the effect of cot fundamentally depends on generating sequences of words that increase the probability of the correct answer when conditioned upon; as long as this is the case, cot can thus succeed even when the demonstrations in the prompt are invalid. in the ongoing debate about whether llms reason or memorize @xcite @xcite @xcite , our results thus support a reasonable middle-ground: llm behavior displays aspects of both memorization and reasoning, and also reflects the probabilistic origins of these models. ## related work in-context learning in language models. it has been argued that llms can learn a task purely from demonstrations given in their context without any additional training @xcite , a phenomenon known as in-context learning (icl). there have been many investigations into how icl operates. theoretical frameworks have modeled the pretraining data as a mixture of hidden markov models @xcite and have argued that icl is the result of implicit bayesian inference @xcite , an argument supported with evidence from synthetic data and tasks @xcite . the emergence of icl has been attributed to factors including data distributional properties @xcite , pretraining term frequencies @xcite , and the creation of task vectors @xcite . however, the extent to which icl is true learning is unclear @xcite . for example, @xcite shows that icl relies on in-context label information but cannot fully overcome preferences acquired during pre-training, which is evidence against the view that icl is true learning. ## approach one challenge of evaluating the role of memorization and reasoning in the performance of llms is that these models are typically evaluated on a wide range of complex reasoning tasks, whose variety and complexity can obscure the factors that drive performance. by contrast, we propose to tease apart the factors behind the efficacy of cot prompting by focusing on a single relatively simple task: deciphering text encoded with a shift cipher. encoding a message with a shift cipher involves replacing every letter with another letter that is some fixed number of positions (called shif t_level) forward in the alphabet; decoding is the reverse (shifting backward) as shown in figure 1 . these are also known as rotation ciphers since they rotate the alphabet forward some number of steps, and they are given the name rot-k where k corresponds to shif t_level. for example, given the test word "fdw" and that rot-3 encryption has been used (shif @xmath0, decoding involves shifting every letter 3 steps backwardi.e., @xmath1, @xmath2, and @xmath3. in our experiments, we give an llm a single word encoded with a shift cipher and ask it to decode this text to recover the original word. ## disentangling the factors influencing cot performance we consider four types of reasoning processes that llms might be adopting. (a) symbolic reasoning is the use of discrete, deterministic inference rules. shift ciphers can be perfectly decoded with a simple symbolic algorithm, so a system using fully systematic reasoning should attain 100% accuracy. a hallmark of memorization would be much higher accuracy at 13 than other shift levels. (d) probabilistic reasoning frames a task as choosing the output that is most probable given the input. such reasoning would be influenced by the prior probability of the output: a probabilistic reasoner should show accuracy that increases as the prior probability of the correct answer increases. figure 4 illustrates the hypothetical performance trends that would be observed in a system adopting each reasoning approach. these approaches are not mutually exclusive; e.g., a reasoner could be influenced by both probability and memorization. indeed, as discussed below, we find that llms' performance when prompted with cot displays hallmarks of several different types of reasoning; see figure 1 , panel 4 for gpt-4 and figure 11 in the appendix for claude 3 and llama 3.1. first, accuracy generally decreases as the shift level increases, a hallmark of noisy reasoning. llms' performance is, in particular, indicative of a two-way version of noisy reasoning in which it can decode a message by shifting letters forward or backward (e.g., instead of decoding a shift of 25 by shifting back 25 letters, it could instead shift forward 1 letter, as doing so requires fewer steps); this two-way nature shows up in the way that accuracy increases as the shift level changes from 20 to 25. second, evidence of probabilistic reasoning can be seen in the fact that accuracy is substantially higher for high prob (the highest-probability bin, bin 1) than low prob (the lowest-probability bin, bin 5). high prob / low prob refer to the prob-ability of the words that are the correct answers when our examples are decoded, where probability is quantified using gpt-2 as described in section 3.2. the "high prob" cases are common words such as {'mariner', 'shrines', 'paywall', . . . }, while the "low prob" cases are nonsense letter sequences such as {'xcbrouw', 'jsxrouw', 'levjspx', . . . }. finally, although a shift level of 13 requires the most reasoning steps of any shift level (assuming decoding can be done forward or backward), there is a spike in accuracy at a shift level of 13. as discussed above, this spike is a hallmark of memorization since 13 is the most common shift level in natural corpora. for the upcoming detailed analysis experiments, we use gpt-4 as the main reference model, since claude 3 and llama 3.1 exhibited similar trends as gpt-4 on the evaluations presented so far. * ## conclusion we have used the case study of shift ciphers to disentangle the factors that influence cot reasoning, with a focus on characterizing what type of reasoning is used in models prompted with cot. we found that cot performance is statistically significantly influenced by the probability of occurrence of the expected task output, the frequency of the task in corpora, and the number of reasoning steps that must be (implicitly) performed. these results suggest that cot reasoning can be characterized as probabilistic, memorization-influenced noisy reasoning, meaning that llm behavior displays traits of both memorization and generalization.