# Transformer-Based Models Are Not Yet Perfect At Learning to Emulate Structural Recursion

arXiv: https://arxiv.org/abs/2401.12947 · HTML: https://mlsanity.com/paper/2401.12947/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 53 of its 91 references that are in the map.
- First posted on arXiv 23 Jan 2024.

## Builds on (most cited first, 30 of 53)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Transformer Feed-Forward Layers Are Key-Value Memories](https://mlsanity.com/paper/2012.14913/) (2020)
- [LaMDA: Language Models for Dialog Applications](https://mlsanity.com/paper/2201.08239/) (2022)
- [Interpretability in the Wild: a Circuit for Indirect Object Identification in GPT-2 small](https://mlsanity.com/paper/2211.00593/) (2022)
- [WizardLM: Empowering large pre-trained language models to follow complex instructions](https://mlsanity.com/paper/2304.12244/) (2023)
- [CodeT5: Identifier-aware Unified Pre-trained Encoder-Decoder Models for Code Understanding and Generation](https://mlsanity.com/paper/2109.00859/) (2021)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [CodeGen: An Open Large Language Model for Code with Multi-Turn Program Synthesis](https://mlsanity.com/paper/2203.13474/) (2022)
- [Probing Classifiers: Promises, Shortcomings, and Advances](https://mlsanity.com/paper/2102.12452/) (2021)
- [Progress measures for grokking via mechanistic interpretability](https://mlsanity.com/paper/2301.05217/) (2023)
- [CodeXGLUE: A Machine Learning Benchmark Dataset for Code Understanding and Generation](https://mlsanity.com/paper/2102.04664/) (2021)
- [ByT5: Towards a token-free future with pre-trained byte-to-byte models](https://mlsanity.com/paper/2105.13626/) (2021)
- [InCoder: A Generative Model for Code Infilling and Synthesis](https://mlsanity.com/paper/2204.05999/) (2022)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Generative Language Modeling for Automated Theorem Proving](https://mlsanity.com/paper/2009.03393/) (2020)
- [Unified Pre-training for Program Understanding and Generation](https://mlsanity.com/paper/2103.06333/) (2021)
- [A Systematic Evaluation of Large Language Models of Code](https://mlsanity.com/paper/2202.13169/) (2022)
- [CodeT5+: Open Code Large Language Models for Code Understanding and Generation](https://mlsanity.com/paper/2305.07922/) (2023)
- [CodeGeeX: A Pre-Trained Model for Code Generation with Multilingual Benchmarking on HumanEval-X](https://mlsanity.com/paper/2303.17568/) (2023)
- [CRUXEval: A Benchmark for Code Reasoning, Understanding and Execution](https://mlsanity.com/paper/2401.03065/) (2024)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Analyzing the Structure of Attention in a Transformer Language Model](https://mlsanity.com/paper/1906.04284/) (2019)
- [Automatically Correcting Large Language Models: Surveying the landscape of diverse self-correction strategies](https://mlsanity.com/paper/2308.03188/) (2023)
- [IntelliCode Compose: Code Generation Using Transformer](https://mlsanity.com/paper/2005.08025/) (2020)
- [Is Self-Repair a Silver Bullet for Code Generation?](https://mlsanity.com/paper/2306.09896/) (2023)

## Built on by (most cited first, 14 of 14)

- [A Mechanistic Analysis of a Transformer Trained on a Symbolic Multi-Step Reasoning Task](https://mlsanity.com/paper/2402.11917/) (2024)
- [Towards a Theoretical Understanding of the 'Reversal Curse' via Training Dynamics](https://mlsanity.com/paper/2405.04669/) (2024)
- [EquiBench: Benchmarking Large Language Models' Reasoning about Program Semantics via Equivalence Checking](https://mlsanity.com/paper/2502.12466/) (2025)
- [Can Transformers Do Enumerative Geometry?](https://mlsanity.com/paper/2408.14915/) (2024)
- [An explainable transformer circuit for compositional generalization](https://mlsanity.com/paper/2502.15801/) (2025)
- [A Tool for In-depth Analysis of Code Execution Reasoning of Large Language Models](https://mlsanity.com/paper/2501.18482/) (2025)
- [Code Simulation as a Proxy for High-order Tasks in Large Language Models](https://mlsanity.com/paper/2502.03568/) (2025)
- [Understanding and Enhancing the Planning Capability of Language Models via Multi-Token Prediction](https://mlsanity.com/paper/2509.23186/) (2025)
- [Optimizing Multi-Hop Document Retrieval Through Intermediate Representations](https://mlsanity.com/paper/2503.04796/) (2025)
- [Fodor and Pylyshyn's Legacy: Still No Human-like Systematic Compositionality in Neural Networks](https://mlsanity.com/paper/2506.01820/) (2025)
- [Emergent Stack Representations in Modeling Counter Languages Using Transformers](https://mlsanity.com/paper/2502.01432/) (2025)
- [Sigma: The Key for Vision-Language-Action Models toward Telepathic Alignment](https://mlsanity.com/paper/2512.00783/) (2025)
- [Training Transformers as a Universal Computer](https://mlsanity.com/paper/2604.25166/) (2026)
- [Unveiling the Visual Counting Bottleneck in Vision-Language Models](https://mlsanity.com/paper/2605.30170/) (2026)

## Abstract (arXiv)

This paper investigates the ability of transformer-based models to learn structural recursion from examples. Recursion is a universal concept in both natural and formal languages. Structural recursion is central to the programming language and formal mathematics tasks where symbolic tools currently excel beyond neural models, such as inferring semantic relations between datatypes and emulating program behavior. We introduce a general framework that nicely connects the abstract concepts of structural recursion in the programming language domain to concrete sequence modeling problems and learned models' behavior. The framework includes a representation that captures the general textitsyntax of structural recursion, coupled with two different frameworks for understanding their textitsemantics -- one that is more natural from a programming languages perspective and one that helps bridge that perspective with a mechanistic understanding of the underlying transformer architecture. With our framework as a powerful conceptual tool, we identify different issues under various set-ups. The models trained to emulate recursive computations cannot fully capture the recursion yet instead fit short-cut algorithms and thus cannot solve certain edge cases that are under-represented in the training distribution. In addition, it is difficult for state-of-the-art large language models (LLMs) to mine recursive rules from in-context demonstrations. Meanwhile, these LLMs fail in interesting ways when emulating reduction (step-wise computation) of the recursive function.