Arithmetic Without Algorithms: Language Models Solve Math With a Bag of Heuristics — part 1/5
Cleaned-text code points [0, 14979). Bibliography omitted here; source.md includes it.
# Arithmetic Without Algorithms: Language Models Solve Math with a Bag of Heuristics
###### Abstract
Do large language models (LLMs) solve reasoning tasks by learning robust generalizable algorithms, or do they memorize training data? To investigate this question, we use arithmetic reasoning as a representative task. Using causal analysis, we identify a subset of the model (a circuit) that explains most of the model’s behavior for basic arithmetic logic and examine its functionality. By zooming in on the level of individual circuit neurons, we discover a sparse set of important neurons that implement simple heuristics. Each heuristic identifies a numerical input pattern and outputs corresponding answers. We hypothesize that the combination of these heuristic neurons is the mechanism used to produce correct arithmetic answers. To test this, we categorize each neuron into several heuristic types—such as neurons that activate when an operand falls within a certain range—and find that the unordered combination of these heuristic types is the mechanism that explains most of the model’s accuracy on arithmetic prompts. Finally, we demonstrate that this mechanism appears as the main source of arithmetic accuracy early in training. Overall, our experimental results across several LLMs show that LLMs perform arithmetic using neither robust algorithms nor memorization; rather, they rely on a “ bag of heuristics ’’. 1 1 1 Code at https://github.com/technion-cs-nlp/llm-arithmetic-heuristics
## 1 Introduction
Do large language models (LLMs) implement robust reusable algorithms to solve tasks, or are they merely memorizing aspects of the training distribution? This distinction is crucial ( Tänzer et al., 2022 ; Henighan et al., 2023 ) : while memorization might suffice for limited problem sets, true algorithmic comprehension allows for generalization and efficient scaling to new problems.
Arithmetic reasoning provides a lens for this investigation, as it can be solved using various methods: learning known algorithms, developing novel approaches, or by memorizing vast quantities of input-output pairs. Thus, we ask the following: Do LLMs implement robust algorithms to correctly complete arithmetic prompts, similar to children learning vertical addition to add two numbers, or do LLMs merely memorize the arithmetic prompts that appear in their vast training data?
Previous studies have made progress in identifying arithmetic mechanisms in LLMs. Stolfo et al. (2023) and Zhang et al. (2024) have identified a subset of model components ( a circuit ) responsible for arithmetic calculations in several LLMs and characterized the information flow between them. Zhou et al. (2024) suggested that pre-trained LLMs use features in Fourier space to accurately answer addition prompts. However, Stolfo et al. (2023) and Zhang et al. (2024) stopped short of elucidating the mechanism implemented by the circuit they identified—a required feat to understand the trade-off between generalization and memorization in this task. Zhou et al. (2024) studied addition prompts in models that were fine-tuned on arithmetic data. Their findings regarding Fourier features are significant, but we claim these represent only a part of a more complex mechanism. Our work aims to bridge these gaps: we investigate how the arithmetic circuit works qualitatively—and specifically, whether it implements a mathematical algorithm or memorizes arithmetic training data.
To do so, we reverse-engineer the arithmetic mechanism applied by LLMs. We use causal analysis to examine their arithmetic circuits, focusing on individual neurons within the circuit responsible for generating the correct answer. Our analysis reveals that a sparse subset of neurons is sufficient for accurate responses, with each neuron implementing a distinct heuristic . Each heuristic fires for a specific pattern in input operands or in their combination, and some increase the logits of relevant result tokens accordingly. For instance, one heuristic ( Figure 1 b) increases logits of tokens between 150 150 and 180 180 for subtraction prompts whose answer falls within this range. By examining these neurons, we classify each into one or more heuristic types. For example, the mentioned neuron ( Figure 1 b) falls within the type of result-range heuristics, which promote continuous value ranges. We discover that successful prompt completion relies on a combination of several unrelated heuristic types, forming a “bag of heuristics” approach. This finding suggests that LLMs may not be employing a single, cohesive algorithm for arithmetic reasoning, nor are they memorizing all possible inputs and outputs; rather, they deploy a collection of simpler rules and patterns.
We investigate if the bag of heuristics emerges as the primary arithmetic mechanism from the onset of training, or whether it overrides an earlier mechanism. To do that, we analyze how the heuristics evolve over the course of training. We show arithmetic heuristics appear throughout the model training, gradually converging towards the heuristics observed in the final checkpoint. Furthermore, we provide evidence that the bag of heuristics mechanism explains most of the model’s behavior even in early stages, indicating it is the main mechanism used for solving arithmetic prompts.
We contribute by providing a high-resolution understanding of the mechanism that LLMs use to answer arithmetic prompts. We (i) show pre-trained LLMs implement a “bag of heuristics” approach, (ii) investigate when and why this mechanism fails to generalize, and (iii) discover how it emerges across training. This allows us to better understand the source of current capabilities and limitations of LLMs in arithmetic reasoning—a finding that could apply to additional reasoning tasks.
## 2 Arithmetic circuit discovery
In transformer-based LLMs, a circuit ( Elhage et al., 2021 ) refers to a minimal subset of interconnected model components (multi-layer perceptrons (MLP) or attention heads) that perform the computations required for a specific task. We locate, and later analyze, the circuit responsible for arithmetic calculations.
### 2.1 Circuit discovery and evaluation
##### Models and Data
We analyze four LLMs: Llama3-8B/70B ( Dubey et al., 2024 ) , Pythia-6.9B ( Biderman et al., 2023 ) , and GPT-J ( Wang & Komatsuzaki, 2021 ) . For each, we locate and analyze the circuit responsible for arithmetic calculations. We focus on Llama3-8B in the main paper and report similar results for the additional models in Appendix I . We use pre-trained models without fine-tuning them on arithmetic prompts, as our goal is to uncover the mechanisms induced by typical language model training. Each model tokenizes positive numbers as a single token, up to some limit; e.g., in Llama3-8B, numbers in [ 0 , 1000 ] [0,1000] are tokenized to a single token. To locate the arithmetic circuit, we use two-operand arithmetic prompts with Arabic numerals and the four basic operators ( + , − , × , ÷ +,-,\times,\div ), such that each prompt has four tokens: o p 1 op1 , the operator, o p 2 op2 , and the “ = = ” sign. We sample a list of 100 100 prompts per operator for circuit discovery, and an identical amount for evaluation. Each prompt is chosen so that both its operands and result will be tokenized to a single token; e.g., in Llama3-8B, the operands and result must be between 0 0 and 1,000 1,000 . Unlike previous studies ( Stolfo et al., 2023 ) , we do not use in-context prompting, to ensure the circuit does not include any component not directly linked to arithmetic calculations. To reduce noise and ensure the circuits only contain components responsible for correct arithmetic completions, we only use prompts that are correctly completed by the model, similar to previous studies ( Wang et al., 2022 ; Prakash et al., 2024 ) . Throughout the paper, the prompt “ 226 − 68 = 226-68= ” is used as a running example.
##### Method
To locate the circuit components, we conduct a series of activation patching experiments ( Vig et al., 2020 ) that allow us to assess the importance of each MLP and attention head at each sequence position. Each experiment involves sampling a prompt p p with result r r from the dataset (for example, “ 226 − 68 = 226-68= ”), and sampling a random counterfactual prompt p ′ p^{\prime} that leads to a different result r ′ r^{\prime} (for example, “ 21 + 17 = 21+17= ”). After pre-computing the activations of the model for the counterfactual prompt p ′ p^{\prime} , we introduce the prompt p p to the model. We intervene on ( “patch” ) the computation, which means we replace the activation of a single MLP layer or attention head with its pre-computed activation for p ′ p^{\prime} . Following Stolfo et al. (2023) , we observe how this intervention affects the probabilities of both answer tokens, r r and r ′ r^{\prime} , by measuring the following: E ( r , r ′ ) = 1 2 [ ℙ ∗ ( r ′ ) − ℙ ( r ′ ) ℙ ( r ′ ) + ℙ ( r ) − ℙ ∗ ( r ) ℙ ∗ ( r ) ] \operatorname{E(r,r^{\prime})}=\frac{1}{2}\left[\frac{\mathbb{P}^{*}(r^{\prime})-\mathbb{P}(r^{\prime})}{\mathbb{P}(r^{\prime})}+\frac{\mathbb{P}\left(r\right)-\mathbb{P}^{*}\left(r\right)}{\mathbb{P}^{*}\left(r\right)}\right] (1) where ℙ \mathbb{P} and ℙ ∗ \mathbb{P^{*}} are the pre- and post-intervention probability distributions, respectively. The two summands in Equation 1 increase if patching raises the probability of r ′ r^{\prime} or decreases the probability of r r , respectively. High effect for an intervention on a component indicates its high importance in prompt calculation. The effect is averaged across prompts and measured separately per component.
##### Results
The patching results, shown in Figure 2(a) , reveal that the MLP layers affect the output probabilities more than the attention heads. The first MLP affects the representation at the operator and operand positions (see Section B.1 ), while middle- and late-layer MLPs exhibit a strong effect at the final position, likely reflecting their role in predicting the answer token in that position (further discussed in Section 2.2 ). Figure 2(a) also shows that very few attention heads are important to the circuit. Each such attention head copies information from a single position (either an operand or operator position) to the final position (see Section B.2 ). Figure 2(b) summarizes the information flow within the circuit, consistent in structure with prior work ( Stolfo et al., 2023 ) .
To evaluate the circuit 𝐜 \mathbf{c} , we measure its faithfulness ( Wang et al., 2022 ) , the proportion of the full model’s behavior on arithmetic prompts that can be explained solely by the circuit. To measure faithfulness, we first pre-compute mean activations for each model component (in each position) across all arithmetic prompts. We then intervene on the evaluation prompts by replacing non-circuit component activations with their means. To quantify performance, we measure NL ( 𝐜 ) \operatorname{NL}(\mathbf{c}) , the logit of the correct answer token normalized by the maximal logit, as a proxy for accuracy, when mean-ablating all components not in the circuit 𝐜 \mathbf{c} . The circuit’s faithfulness is calculated as: F ( 𝐜 ) = NL ( 𝐜 ) − NL ( ∅ ) NL ( 𝐌 ) − NL ( ∅ ) \operatorname{F}(\mathbf{c})=\frac{\operatorname{NL}(\mathbf{c})-\operatorname{NL}(\emptyset)}{\operatorname{NL}(\mathbf{M})-\operatorname{NL}(\emptyset)} (2) where 𝐌 \mathbf{M} is the entire model and NL ( 𝐌 ) \operatorname{NL}(\mathbf{M}) is the normalized correct-answer logit when no component is ablated (always 1.0 for correctly completed prompts). NL ( ∅ ) \operatorname{NL}(\emptyset) is the normalized correct answer logit when all components are mean-ablated. This formula normalizes faithfulness to a [ 0.0 , 1.0 ] [0.0,1.0] range.
The circuit achieves a high faithfulness of 0.96 on average across the four arithmetic operators; i.e., the circuit accounts for 96% of the entire model’s performance. We can therefore conclude that the components identified in this section comprise the arithmetic circuit, and explain most of the model’s accuracy for arithmetic prompts. See Appendix A for results across various circuit sizes, and a discussion of Pareto-optimality with respect to faithfulness and size.
### 2.2 Identifying answer-promoting components
To understand the mechanism implemented by the circuit to promote the correct answer, we first search for the specific circuit components that increase the probability of the correct answer. For this, we employ linear probing ( Belinkov, 2022 ) . For each layer l l and sequence position p p , we train a linear classifier f l , p : ℝ d → ℝ 1000 f_{l,p}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{1000} (where d d is the dimension of each layer’s output representation) using a training set of correctly completed arithmetic prompts. We pass these prompts through the model and calculate the output representation h l , p ∈ ℝ d h^{l,p}\in\mathbb{R}^{d} at layer l l and position p p for each prompt. The classifier f l , p f_{l,p} receives h l , p h^{l,p} as input, and outputs a probability distribution over the 1,000 1,000 possible arithmetic answers. The classifier f l , p f_{l,p} is evaluated on a separate test set of correctly completed prompts, showing to what extent the correct answer can be extracted from the output representation at layer l l and position p p .
We find that the answer can only be extracted with high accuracy from the final position ( Figure 3 ), after the token representation is processed by the later layers of the model, starting from layer l = 16 l=16 . Given that the arithmetic circuit contains only MLPs in these layers ( Figure 2 ), this suggests that these MLPs in layers [ 16 , 32 ] [16,32] are the components that write the correct answer into the representation at the last position. The following section zooms into these middle- and late-layer MLPs, and presents evidence for the role they play in generating the correct answer— specifically, in how they promote the correct answer token through a combination of many independent arithmetic heuristics.
## 3 MLP neurons implement arithmetic heuristics
### 3.1 Decomposing circuit MLPs to individual neurons
Having shown that the model generates the arithmetic answer in middle- and late-layer MLPs at the final position p = 4 p=4 , we zoom in on these MLPs and their calculations at this position to investigate the implemented mechanism. The MLP at layer l l can be described by the following equation: 𝐡 o u t l = MLP i n ( 𝐡 i n l ) ⋅ 𝐖 o u t l = 𝐡 p o s t l ⋅ 𝐖 o u t l = ∑ n = 0 d m l p 𝐡 p o s t l , n 𝐯 o u t l , n \mathbf{h}_{out}^{l}=\operatorname{MLP}_{in}\left(\mathbf{h}_{in}^{l}\right)\cdot\mathbf{W}_{out}^{l}=\mathbf{h}_{post}^{l}\cdot\mathbf{W}_{out}^{l}=\sum_{n=0}^{d_{mlp}}{\mathbf{h}_{post}^{l,n}\mathbf{v}_{out}^{l,n}} (3)