mlsanityData to 13 Oct 2026

Quantifying artificial intelligence through algorithmic generalization

arXiv 2411.05943 ↗First posted 8 Nov 2024cs.AI cs.CL cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

The rapid development of artificial intelligence (AI) systems has created an urgent need for their scientific quantification. While their fluency across a variety of domains is impressive, AI systems fall short on tests requiring algorithmic reasoning -- a glaring limitation given the necessity for interpretable and reliable technology. Despite a surge of reasoning benchmarks emerging from the academic community, no theoretical framework exists to quantify algorithmic reasoning in AI systems. Here, we adopt a framework from computational complexity theory to quantify algorithmic generalization using algebraic expressions: algebraic circuit complexity. Algebraic circuit complexity theory -- the study of algebraic expressions as circuit models -- is a natural framework to study the complexity of algorithmic computation. Algebraic circuit complexity enables the study of generalization by defining benchmarks in terms of the computational requirements to solve a problem. Moreover, algebraic circuits are generic mathematical objects; an arbitrarily large number of samples can be generated for a specified circuit, making it an ideal experimental sandbox for the data-hungry models that are used today. In this Perspective, we adopt tools from algebraic circuit complexity, apply them to formalize a science of algorithmic generalization, and address key challenges for its successful application to AI science.

Key facts. Cited by 5 papers in the map (data through 13 Oct 2026). Builds on 61 of its 98 references that are in the map. First posted on arXiv 8 Nov 2024.

Builds on

61 of 98 references.

References · 61

  1. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,376
  2. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 9,091
  3. 2020Measuring Massive Multitask Language Understandingcited by 7,876
  4. 2023Sparks of Artificial General Intelligence: Early experiments with GPT-4cited by 2,586
  5. 2022Emergent Abilities of Large Language Modelscited by 2,499
  6. 2019BoolQ: Exploring the Surprising Difficulty of Natural Yes/No Questionscited by 2,163
  7. 2016CLEVR: A Diagnostic Dataset for Compositional Language and Elementary Visual Reasoningcited by 1,450
  8. 2022Least-to-Most Prompting Enables Complex Reasoning in Large Language Modelscited by 1,404
  9. 2022In-context Learning and Induction Headscited by 940
  10. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 878
  11. 2023Are Emergent Abilities of Large Language Models a Mirage?cited by 520
  12. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 498
38 more
  1. 2019Analysing Mathematical Reasoning Abilities of Neural Modelscited by 333
  2. 2023The Impact of Positional Encoding on Length Generalization in Transformerscited by 322
  3. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 293
  4. 2019Measuring Compositional Generalization: A Comprehensive Method on Realistic Datacited by 283
  5. 2019Compositionality decomposed: how do neural networks generalise?cited by 264
  6. 2020COGS: A Compositional Generalization Challenge Based on Semantic Interpretationcited by 261
  7. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 258
  8. 2023Reasoning or Reciting? Exploring the Capabilities and Limitations of Language Models Through Counterfactual Taskscited by 244
  9. 2022Emergent Analogical Reasoning in Large Language Modelscited by 239
  10. 2022Neural Networks and the Chomsky Hierarchycited by 216
  11. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 198
  12. 2023Embers of Autoregression: Understanding Large Language Models Through the Problem They are Trained to Solvecited by 175
  13. 2021Investigating the Limitations of Transformers with Simple Arithmetic Taskscited by 138
  14. 2023Teaching Arithmetic to Small Transformerscited by 122
  15. 2023What Formal Languages Can Transformers Express? A Surveycited by 121
  16. 2021The Devil is in the Detail: Simple Tricks Improve Systematic Generalization of Transformerscited by 117
  17. 2023Randomized Positional Encodings Boost Length Generalization of Transformerscited by 116
  18. 2023The mechanistic basis of data dependence and abrupt learning in an in-context classification taskcited by 115
  19. 2022Teaching Algorithmic Reasoning via In-context Learningcited by 111
  20. 2020A Benchmark for Systematic Generalization in Grounded Language Understandingcited by 108
  21. 2022State-of-the-art generalisation research in NLP: A taxonomy and reviewcited by 98
  22. 2024Transformers Can Achieve Length Generalization But Not Robustlycited by 85
  23. 2019Measuring Compositionality in Representation Learningcited by 84
  24. 2024Transformers Can Do Arithmetic with the Right Embeddingscited by 77
  25. 2021Making Transformers Solve Compositional Taskscited by 72
  26. 2024Alice in Wonderland: Simple Tasks Showing Complete Reasoning Breakdown in State-Of-the-Art Large Language Modelscited by 68
  27. 2023Length Generalization in Arithmetic Transformerscited by 65
  28. 2023Positional Description Matters for Transformers Arithmeticcited by 56
  29. 2023Comparing Humans, GPT-4, and GPT-4V On Abstraction and Reasoning Taskscited by 55
  30. 2022Transformers generalize differently from information stored in context vs in weightscited by 49
  31. 2023Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languagescited by 48
  32. 2023Learning Transformer Programscited by 40
  33. 2024H-ARC: A Robust Estimate of Human Performance on the Abstraction and Reasoning Corpus Benchmarkcited by 33
  34. 2021An Analytical Theory of Curriculum Learning in Teacher-Student Networkscited by 27
  35. 2022Uncontrolled Lexical Exposure Leads to Overestimation of Compositional Generalization in Pretrained Modelscited by 26
  36. 2022Compositional generalization through abstract representations in human and artificial neural networkscited by 22
  37. 2024When does compositional structure yield compositional generalization? A kernel theorycited by 19
  38. 2021Exploring Generalization Ability of Pretrained Language Models on Arithmetic and Logical Reasoningcited by 17

50 most cited of 61 All 61 (JSON)

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2025: 2; 2026: 3.

5 papers.

  1. 2025RelP: Faithful and Efficient Circuit Discovery in Language Models via Relevance Patchingcited by 10
  2. 2026Robust Reasoning Benchmarkcited by 3
  3. 2025Experience Scaling: Post-Deployment Evolution For Large Language Modelscited by 0
  4. 2026Universal Transformers for Circuit Computations: Perfect Length Generalization in Tiny Transformerscited by 0
  5. 2026When does a scaling result justify a different allocation? A critical review of resource-allocation evidence for AI systemscited by 0