Elamur Research⌕
☰
home / papers / 2024 / Arithmetic Without Algorithms: Language Models Solve Math With a Bag of Heuristics

Arithmetic Without Algorithms: Language Models Solve Math With a Bag of Heuristics

Paper · 2024 · Yaniv Nikankin, Anja Reusch, Aaron Mueller et al.

Summary

This paper asks whether LLMs solve arithmetic by running a general procedure or by recalling memorized examples. The authors reverse-engineer pre-trained models without arithmetic fine-tuning. Their test set is two-operand prompts covering +, −, ×, ÷, where every operand and result is a single token. Activation patching isolates a circuit that does almost all of the work: a handful of attention heads carry information about the operands and the operator over to the last token position, and mid- and late-layer MLPs then raise the logit of the answer. Analysis at the neuron level shows that a small subset of MLP neurons each encode a simple rule. Each rule fires on a particular input pattern, such as an operand in a numeric range or a result with a certain remainder, and boosts the matching output tokens. The authors sort these neurons into heuristic types and find that an unordered combination of them accounts for most correct answers. This "bag of heuristics" also dominates early in training. The answer to the original question is therefore neither of the two options, which helps explain why LLM arithmetic generalizes poorly.

Key points

  • Models studied: Llama3-8B (main focus), Llama3-70B, Pythia-6.9B and GPT-J. In Llama3-8B, every number from 0 to 1000 is a single token.
  • Data: for each operator, 100 prompts for circuit discovery and another 100 for evaluation, without in-context examples. Only prompts the model answers correctly are kept.
  • Across the four operators, the discovered circuit reaches an average faithfulness of 0.96 under mean ablation.
  • Heuristic types include:
    • operand or result ranges (e.g., results in [150, 180]);
    • modular rules (e.g., result ≡ 0 mod 8);
    • digit patterns;
    • identical operands.
  • Code is released at github.com/technion-cs-nlp/llm-arithmetic-heuristics.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Technion – Israel Institute of TechnologyHaifa · Israel54 works · 7,237 citations🎓Northeastern UniversityBoston · United States68 works · 7,316 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 works

🧭 Topics 1Research subjects and languages the work is about.Language models & pretraining · 3,894 works

Cite

Cite as Yaniv Nikankin, Anja Reusch, Aaron Mueller and Yonatan Belinkov. 2024. Arithmetic Without Algorithms: Language Models Solve Math With a Bag of Heuristics. arXiv:2410.21272.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2410.21272 · arXiv 2410.21272

@misc{nikankin2024arithmetic,
  title = {{Arithmetic Without Algorithms: Language Models Solve Math With a Bag of Heuristics}},
  author = {Yaniv Nikankin, Anja Reusch, Aaron Mueller and Yonatan Belinkov},
  year = {2024},
  doi = {10.48550/arxiv.2410.21272},
  eprint = {2410.21272},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2410.21272}
}

References

40 references, 9 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Antonis Antoniades, Xinyi Wang, Yanai Elazar, Alfonso Amayuelas, Alon Albalak, Kexun Zhang, and William Yang Wang. Generalization vs. memorization: Tracing language models’ capabilities back to pretraining data. In ICML 2024 Workshop on Foundation Models in the Wild, 2024. URL https://openreview.net… ↗
  2. Rachit Bansal, Danish Pruthi, and Yonatan Belinkov. Measures of information reflect memorization patterns. In Advances in Neural Information Processing Systems, 2022. find
  3. Yonatan Belinkov. Probing classifiers: Promises, shortcomings, and advances. Computational Linguistics, 48(1):207–219, 2022.
  4. Stella Biderman, Hailey Schoelkopf, Quentin Gregory Anthony, Herbie Bradley, Kyle O’Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, et al. Pythia: A suite for analyzing large language models across training and scaling. In International Conference on M… find
  5. Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tramer, and Chiyuan Zhang. Quantifying memorization across neural language models. In The Eleventh International Conference on Learning Representations, 2023. find
  6. Verna Dankers and Ivan Titov. Generalisation first, memorisation second? Memorisation localisation for natural language classification tasks. In The 62nd Annual Meeting of the Association for Computational Linguistics, pp. 14348–14366. Association for Computational Linguistics, 2024. find
  7. Guy Dar, Mor Geva, Ankit Gupta, and Jonathan Berant. Analyzing transformers in embedding space. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 16124–16170, 2023.
  8. Xiaoman Delores Ding, Zifan Carl Guo, Eric J Michaud, Ziming Liu, and Max Tegmark. Survival of the fittest representation: A case study with modular addition. In ICML 2024 Workshop on Mechanistic Interpretability, 2024. URL https://openreview.net/forum?id= 2WfiYQlZDa. ↗
  9. Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The Llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024.
  10. Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova DasSarma, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds, Danny Hernandez, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Ja… find
  11. Atticus Geiger, Hanson Lu, Thomas Icard, and Christopher Potts. Causal abstractions of neural networks. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 9574–9586. Curran Associates, Inc., 2021. UR… find
  12. Mor Geva, Roei Schuster, Jonathan Berant, and Omer Levy. Transformer feed-forward layers are key-value memories. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 5484–5495, 2021. find
  13. Rhys Gould, Euan Ong, George Ogden, and Arthur Conmy. Successor heads: Recurring, interpretable attention heads in the wild. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=kvcbV8KQsi. ↗
  14. Michael Hanna, Ollie Liu, and Alexandre Variengien. How does gpt-2 compute greater-than?: Interpreting mathematical abilities in a pre-trained language model. Advances in Neural Information Processing Systems, 36, 2024a.
  15. Michael Hanna, Sandro Pezzelle, and Yonatan Belinkov. Have faith in faithfulness: Going beyond circuit overlap when finding model mechanisms. arXiv preprint arXiv:2403.17806, 2024b. find
  16. Tom Henighan, Shan Carter, Tristan Hume, Nelson Elhage, Robert Lasenby, Stanislav Fort, Nicholas Schiefer, and Christopher Olah. Superposition, memorization, and double descent. Transformer Circuits Thread, 6:24, 2023. find
  17. Yifan Hou, Jiaoda Li, Yu Fei, Alessandro Stolfo, Wangchunshu Zhou, Guangtao Zeng, Antoine Bosselut, and Mrinmaya Sachan. Towards a mechanistic interpretation of multi-step reasoning capabilities of language models. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Proces… find
  18. Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), San Diega, CA, USA, 2015.
  19. Kenneth Li, Aspen K Hopkins, David Bau, Fernanda Viégas, Hanspeter Pfister, and Martin Wattenberg. Emergent world representations: Exploring a sequence model trained on a synthetic task. In The Eleventh International Conference on Learning Representations, 2022. find
  20. Hanxiao Liu, Zihang Dai, David So, and Quoc V Le. Pay attention to MLPs. Advances in neural information processing systems, 34:9204–9215, 2021. find
  21. Davide Maltoni and Matteo Ferrara. Arithmetic with language models: From memorization to computation. arXiv preprint arXiv:2308.01154, 2023. find
  22. Callum McDougall, Arthur Conmy, Cody Rushing, Thomas McGrath, and Neel Nanda. Copy suppression: Comprehensively understanding an attention head. arXiv preprint arXiv:2310.04625, 2023. find
  23. Neel Nanda. Attribution patching: Activation patching at industrial scale, 2022. URL https://www.neelnanda.io/mechanistic-interpretability/ attribution-patching. ↗
  24. Neel Nanda and Joseph Bloom. TransformerLens. TransformerLensOrg/TransformerLens, 2022. https://github.com/ ↗
  25. Neel Nanda, Lawrence Chan, Tom Lieberum, Jess Smith, and Jacob Steinhardt. Progress measures for grokking via mechanistic interpretability. In The Eleventh International Conference on Learning Representations, 2023. nostalgebraist. Interpreting GPT: The logit lens, 2020. URL https://www.lesswrong.co… ↗
  26. Judea Pearl. Direct and indirect effects. Direct and Indirect Effects, 2001. URL https://ftp.cs.ucla.edu/pub/stat_ser/R273-U.pdf. ↗
  27. Nikhil Prakash, Tamar Rott Shaham, Tal Haklay, Yonatan Belinkov, and David Bau. Fine-tuning enhances existing mechanisms: A case study on entity tracking. In The Twelfth International Conference on Learning Representations, 2024. find
  28. Alessandro Stolfo, Yonatan Belinkov, and Mrinmaya Sachan. A mechanistic interpretation of arithmetic reasoning in language models using causal mediation analysis. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 7035–7052, 2023. find
  29. Nishant Subramani, Nivedita Suresh, and Matthew E Peters. Extracting latent steering vectors from pretrained language models. In Findings of the Association for Computational Linguistics: ACL 2022, pp. 566–581, 2022.
  30. Aaquib Syed, Can Rager, and Arthur Conmy. Attribution patching outperforms automated circuit discovery. In NeurIPS Workshop on Attributing Model Behavior at Scale, 2023. URL https://openreview.net/forum?id=tiLbFR4bJW. ↗
  31. Michael Tänzer, Sebastian Ruder, and Marek Rei. Memorisation versus generalisation in pre-trained language models. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 7564–7578, 2022. find
  32. Alexander Matt Turner, Lisa Thiergart, Gavin Leech, David Udell, Juan J Vazquez, Ulisse Mini, and Monte MacDiarmid. Activation addition: Steering language models without optimization. arXiv preprint arXiv:2308.10248, 2023.
  33. Vikrant Varma, Rohin Shah, Zachary Kenton, János Kramár, and Ramana Kumar. Explaining grokking through circuit efficiency. arXiv e-prints, pp. arXiv–2309, 2023. find
  34. Jesse Vig, Sebastian Gehrmann, Yonatan Belinkov, Sharon Qian, Daniel Nevo, Yaron Singer, and Stuart Shieber. Investigating gender bias in language models using causal mediation analysis. Advances in neural information processing systems, 33:12388–12401, 2020. find
  35. Ben Wang and Aran Komatsuzaki. GPT-J-6B: A 6 Billion Parameter Autoregressive Language Model. https://github.com/kingoflolz/mesh-transformer-jax, May 2021. ↗
  36. Kevin Ro Wang, Alexandre Variengien, Arthur Conmy, Buck Shlegeris, and Jacob Steinhardt. Interpretability in the wild: A circuit for indirect object identification in GPT-2 small. In The Eleventh International Conference on Learning Representations, 2022. find
  37. Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107– 115, 2021. find
  38. Wei Zhang, Chaoqun Wan, Yonggang Zhang, Yiu ming Cheung, Xinmei Tian, Xu Shen, and Jieping Ye. Interpreting and improving large language models in arithmetic calculation. In Forty-first International Conference on Machine Learning, 2024. URL https://openreview.net/ forum?id=CfOtiepP8s. ↗
  39. Ziqian Zhong, Ziming Liu, Max Tegmark, and Jacob Andreas. The clock and the pizza: Two stories in mechanistic explanation of neural networks. Advances in Neural Information Processing Systems, 36, 2024. find
  40. Tianyi Zhou, Deqing Fu, Vatsal Sharan, and Robin Jia. Pre-trained large language models use Fourier features to compute addition. arXiv preprint arXiv:2406.03445, 2024. *Figure 11: Llama3-8B arithmetic circuit faithfulness as function of number of circuit heads.* find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/nikankin-2024-arithmetic-algorithms-language-models-solve/