Algorithmic Phase Transitions in Language Models: A Mechanistic Case Study of Arithmetic
Alan Sun, Ethan Sun, Warren Shepard · 2024
Read Algorithmic Phase Transitions in Language Models: A Mechanistic Case Study of Arithmetic by Alan Sun, Ethan Sun, Warren Shepard (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-07386.txt.
Introduction
Alan Sun, Ethan Sun, and Warren Shepard wrote this 2024 arXiv paper on why language models are brilliant at some reasoning tasks and hopeless at near-identical ones. Their lens is algorithmic stability: whether the model keeps using the same problem-solving strategy when the task changes only slightly. They probed a small open model, Gemma-2-2b, on multi-digit addition.
Mechanistic analysis showed the model runs substantially different internal computations for four-digit versus eight-digit addition. It does not abstract addition into one procedure with a length dial; it keeps separate machinery for separate sizes. The authors argue this instability helps explain spotty zero-shot reasoning: a model can look competent until a trivial respecification swaps the algorithm it actually runs. The case study is a warning against judging reasoning by a handful of benchmarks at one difficulty setting.
Catalog record
| CREATOR | Alan Sun, Ethan Sun, Warren Shepard |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 23 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-07386
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Algorithmic Phase Transitions in Language Models: A Mechanistic Case Study of Arithmetic Alan Sun, Ethan Sun, Warren Shepard Abstract Zero-shot capabilities of large language models make them powerful tools for solving a range of tasks without explicit training. It remains unclear, however, how these models achieve such performance, or why they can zero-shot some tasks but not others. In this paper, we shed some light on this phenomenon by defining and investigating algorithmic stability in language models —changes in problem-solving strategy employed by the model as a result of changes in task specification. We focus on a task where algorithmic stability is needed for generalization: two-operand arithmetic. Surprisingly, we find that Gemma-2-2b employs substantially different computational models on closely related subtasks, i.e. four-digit versus eight-digit addition. Our findings suggest that algorithmic instability may be a contributing factor to language models’ poor zero-shot performance across certain logical reasoning tasks, as they struggle to abstract different problem-solving strategies and smoothly transition between them 1 1 1 Codebase for our experiments can be found at https://github.com/alansun17904/mech-arith . 1 Introduction Language models have demonstrated remarkable capabilities across many benchmarks. In particular, their zero-shot performance—solving a task or generating outputs for which they have not been explicitly trained on—makes them powerful tools. However, it remains unclear how this behavior emerges from training against the language modeling objective [ Wei et al. 2022a , Schaeffer et al. 2023 ] . Further, it has been shown that zero-shot performance varies highly between different tasks [ Wei et al. 2022b ] . In this paper, we shed light on this phenomenon by exploring the robustness of a models’ problem solving strategy with respect to changes in its given task. For example, given two-operand addition problems, we would expect a strong learner to add four-digit numbers the same way it adds eight-digit numbers. We coin the term algorithmic stability to describe this desirable property (see Def. 1 ). Surprisingly, we find that even for a small language model like Gemma-2-2b [ Team et al. 2024 ] , substantially different computational models are implemented on closely related subtasks. Our findings suggest that algorithmic instability may be a contributing factor to language models’ poor zero (few)-shot performance across certain logical reasoning tasks, as they struggle to abstract different problem-solving strategies and smoothly transition between them. We call these aforementioned changes in problem solving strategies under the same task algorithmic phase transitions (see Def. 2 ). These phases are identified using mechanistic interpretability. Mechanistic interpretability causally attributes [ Vig et al. 2020 , Nanda et al. 2022 , Olsson et al. 2022 , Chughtai et al. 2023 ] and localizes behavior to individual model components. The goal is to identify a minimal computational subcircuit that completely characterizes the model’s decision making process on a specific task [ Wang et al. 2022 ] . We identify subcircuits across a host of arithmetic subtasks, and then compare them both quantitatively and qualitatively. Seminal works, such as [ Nanda et al. 2022 , Zhong et al. 2023 ] , have shown that Transformers [ Vaswani et al. 2017 ] implement different algorithms in tandem to solve the same task. Additionally, the interactions between these parallel algorithms are highly sensitive to training and architectural hyperparameters. Similarly, Merullo et al. 2023 presented a case study of circuits within the same model being reused to perform two distinct tasks. Our work builds off of these results. We explore Gemma-2-2b ’s algorithmic stability on two-operand arithmetic. Although arithmetic is a relatively elementary task, it represents a complex task for language models, especially when the operands have many digits [ Hendrycks et al. 2021 , Hanna et al. 2023 , Mao et al. 2023 , Qiu et al. 2024 ] . The task encompasses sufficiently rich algorithms, since there are many possible implementations that span a host of problem-solving strategies, such as look-up table, divide-and-conquer, or dynamic programming. The methods described in our paper, however, can also be applied more broadly to other applications. We first identify a collection of algorithms implemented by the model to solve arithmetic. Then, we isolate sufficient conditions in terms of task perturbations that cause the model to transition between these algorithms. Moreover, we show that these phase transitions are induced by changes in subtask complexity. For example, as the number of digits in each operand increases, we present preliminary evidence that shows Gemma-2-2b undergoes periods of algorithmic stability and experiences sharp phase transitions. Our paper stands in contrast to many existing works that seek to elucidate the mechanism for arithmetic [ Stolfo et al. 2023b , Stolfo et al. 2023a , Qiu et al. 2024 ] , as we focus solely on the transitions between mechanisms rather than the mechanisms themselves. In sum, our contributions are threefold. Firstly, we introduce the notions of algorithmic stability and algorithmic phase transitions . Secondly, we present evidence that for two-operand arithmetic, Gemma-2-2b undergoes sharp algorithmic phase transitions. This may provide a sufficient explanation for their lack of generalization across arithmetic tasks. Lastly, we devise novel methods and techniques to quantify these changes in contrast to many of the existing qualitative techniques of mechanistic interpretability. 2 Defining Algorithmic Stability and Phase Transitions Herein, we first define the notions of algorithmic stability (see Def. 1 ) and algorithmic phase transitions (see Def. 2 ). Next, we present methods to empirically identify phase transitions. Lastly, we apply these methods to two-operand arithmetic and demonstrate how these transitions can be used to explain model performance. Definition 1 (Algorithmic Stability) . Let T be a collection of tasks. Let m be a model and denote \alg(m,t) for t\in T the minimal subcircuit of m that explains t [ Wang et al. 2022 ] . Then, we say that m is \varepsilon -algorithmically stable, for some \varepsilon>0 , across T with respect to some metric \rho if \sup_{t,t^{\prime}\in T}\rho(\alg(m,t^{\prime}),\alg(m,t))\leq\varepsilon. (2.1) Informally, if a model implements significantly different subcircuits across tasks in T , we say that the model is algorithmically unstable over T . We also say that m is algorthmically unstable if Eq. 2.1 does not hold. So far, we have framed algorithmic stability as a desirable property. But, depending on the composition of T , stability may be a hindrance to generalizability. For example, if T contains t_{1} , the set of all addition problems, and t_{2} , the set of all division problems. It would be necessary for performance to solve both of these tasks with different minimal circuits. In this paper, we focus on the case where algorithmic stability is desirable. Specifically, we define T to be the set of all two-operand addition problems. Each t\in T is a class of m -digit by n -digit addition problem, for all m,n\in\{1,2,\ldots,8\} . Therefore, |T|=64 . \rho and \alg(m,\cdot) is defined through activation patching, which we describe in later subsections. If a model is algorithmically unstable on a set of tasks T , then we seek to identify algorithmic phase transitions between these tasks. That is, sufficient conditions in task specification that induce changes in subcircuitry. This notion is formally defined in Def. 2 . Definition 2 (Algorithmic Phase Transition) . Let m be a model and suppose that for