mlsanityData to 14 Oct 2026

ALTA: Compiler-Based Analysis of Transformers

arXiv 2410.18077 ↗First posted 23 Oct 2024cs.LG cs.AI cs.CLcited by 7

Not on the map. Why?

Abstract (arXiv)

We propose a new programming language called ALTA and a compiler that can map ALTA programs to Transformer weights. ALTA is inspired by RASP, a language proposed by Weiss et al. (2021), and Tracr (Lindner et al., 2023), a compiler from RASP programs to Transformer weights. ALTA complements and extends this prior work, offering the ability to express loops and to compile programs to Universal Transformers, among other advantages. ALTA allows us to constructively show how Transformers can represent length-invariant algorithms for computing parity and addition, as well as a solution to the SCAN benchmark of compositional generalization tasks, without requiring intermediate scratchpad decoding steps. We also propose tools to analyze cases where the expressibility of an algorithm is established, but end-to-end training on a given training set fails to induce behavior consistent with the desired algorithm. To this end, we explore training from ALTA execution traces as a more fine-grained supervision signal. This enables additional experiments and theoretical analyses relating the learnability of various algorithms to data availability and modeling decisions, such as positional encodings. We make the ALTA framework -- language specification, symbolic interpreter, and weight compiler -- available to the community to enable further applications and insights.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Builds on 61 of its 77 references that are in the map. First posted on arXiv 23 Oct 2024.

Builds on

61 of 77 references.

References · 61

  1. 2017Attention Is All You Needcited by 60,361
  2. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  3. 2019Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformercited by 14,599
  4. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,459
  5. 2016Gaussian Error Linear Units (GELUs)cited by 3,502
  6. 2021Efficiently Modeling Long Sequences with Structured State Spacescited by 2,465
  7. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 2,022
  8. 2018SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processingcited by 1,989
  9. 2022Least-to-Most Prompting Enables Complex Reasoning in Large Language Modelscited by 1,407
  10. 2018Self-Attention with Relative Position Representationscited by 1,120
  11. 2018Adafactor: Adaptive Learning Rates with Sublinear Memory Costcited by 905
  12. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 886
38 more
  1. 2023Progress measures for grokking via mechanistic interpretabilitycited by 839
  2. 2018Universal Transformerscited by 647
  3. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 503
  4. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 406
  5. 2023The Impact of Positional Encoding on Length Generalization in Transformerscited by 327
  6. 2023On the Planning Abilities of Large Language Models : A Critical Investigationcited by 312
  7. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 294
  8. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
  9. 2019Measuring Compositional Generalization: A Comprehensive Method on Realistic Datacited by 284
  10. 2023Reasoning or Reciting? Exploring the Capabilities and Limitations of Language Models Through Counterfactual Taskscited by 246
  11. 2023Looped Transformers as Programmable Computerscited by 237
  12. 2022Towards Understanding Grokking: An Effective Theory of Representation Learningcited by 230
  13. 2022Neural Networks and the Chomsky Hierarchycited by 217
  14. 2022Exploring Length Generalization in Large Language Modelscited by 206
  15. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 199
  16. 2024Let's Think Dot by Dot: Hidden Computation in Transformer Language Modelscited by 191
  17. 2021Thinking Like Transformerscited by 184
  18. 2023Looped Transformers are Better at Learning Learning Algorithmscited by 149
  19. 2020Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?cited by 147
  20. 2021Investigating the Limitations of Transformers with Simple Arithmetic Taskscited by 139
  21. 2023Teaching Arithmetic to Small Transformerscited by 123
  22. 2021The Devil is in the Detail: Simple Tricks Improve Systematic Generalization of Transformerscited by 117
  23. 2023Randomized Positional Encodings Boost Length Generalization of Transformerscited by 117
  24. 2022Overcoming a Theoretical Limitation of Self-Attentioncited by 113
  25. 2022Teaching Algorithmic Reasoning via In-context Learningcited by 112
  26. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  27. 2023Tracr: Compiled Transformers as a Laboratory for Interpretabilitycited by 104
  28. 2020Compositional Generalization in Semantic Parsing: Pre-training vs. Specialized Architecturescited by 95
  29. 2023Phenomenal Yet Puzzling: Testing Inductive Reasoning Capabilities of Language Models with Hypothesis Refinementcited by 89
  30. 2024In-Context Language Learning: Architectures and Algorithmscited by 89
  31. 2024Transformers Can Achieve Length Generalization But Not Robustlycited by 86
  32. 2020Compositional Generalization via Neural-Symbolic Stack Machinescited by 80
  33. 2020Span-based Semantic Parsing for Compositional Generalizationcited by 77
  34. 2023Generalization on the Unseen, Logic Reasoning and Degree Curriculumcited by 73
  35. 2021Making Transformers Solve Compositional Taskscited by 72
  36. 2022Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functionscited by 70
  37. 2023Tighter Bounds on the Expressivity of Transformer Encoderscited by 66
  38. 2023Positional Description Matters for Transformers Arithmeticcited by 56

50 most cited of 61 All 61 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

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

7 papers.

  1. 2025Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformerscited by 6
  2. 2025Gradient-Based Program Repair: Fixing Bugs in Continuous Program Spacescited by 4
  3. 2025Tracr-Injection: Distilling Algorithms into Pre-trained Language Modelscited by 1
  4. 2025On the Existence of Universal Simulators of Attentioncited by 1
  5. 2026The New Compiler Stack: A Survey on the Synergy of LLMs and Compilerscited by 0
  6. 2026Loom: A Scalable Analytical Neural Computer Architecturecited by 0
  7. 2026Universal Transformers for Circuit Computations: Perfect Length Generalization in Tiny Transformerscited by 0