# Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets

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

## Key facts

- Cited by 76 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Mar 2015.

## Built on by (most cited first, 30 of 76)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [CodeRL: Mastering Code Generation through Pretrained Models and Deep Reinforcement Learning](https://mlsanity.com/paper/2207.01780/) (2022)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Recurrent Memory Transformer](https://mlsanity.com/paper/2207.06881/) (2022)
- [Scalable Adaptive Computation for Iterative Generation](https://mlsanity.com/paper/2212.11972/) (2022)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [Dynamic Cheatsheet: Test-Time Learning with Adaptive Memory](https://mlsanity.com/paper/2504.07952/) (2025)
- [Birth of a Transformer: A Memory Viewpoint](https://mlsanity.com/paper/2306.00802/) (2023)
- [Investigating the Limitations of Transformers with Simple Arithmetic Tasks](https://mlsanity.com/paper/2102.13019/) (2021)
- [Scaling Transformer to 1M tokens and beyond with RMT](https://mlsanity.com/paper/2304.11062/) (2023)
- [Understanding Transformer Reasoning Capabilities via Graph Algorithms](https://mlsanity.com/paper/2405.18512/) (2024)
- [Length Generalization in Arithmetic Transformers](https://mlsanity.com/paper/2306.15400/) (2023)
- [Personalized Federated Learning through Local Memorization](https://mlsanity.com/paper/2111.09360/) (2021)
- [Attention, please! A survey of Neural Attention Models in Deep Learning](https://mlsanity.com/paper/2103.16775/) (2021)
- [ABC: Attention with Bounded-memory Control](https://mlsanity.com/paper/2110.02488/) (2021)
- [Fine-tuning Image Transformers using Learnable Memory](https://mlsanity.com/paper/2203.15243/) (2022)
- [Learning Universal Predictors](https://mlsanity.com/paper/2401.14953/) (2024)
- [Artificial Intelligence in Drug Discovery: Applications and Techniques](https://mlsanity.com/paper/2106.05386/) (2021)
- [Minimum Description Length Recurrent Neural Networks](https://mlsanity.com/paper/2111.00600/) (2021)
- [Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensions](https://mlsanity.com/paper/2310.16076/) (2023)
- [Deep Reinforcement Learning for Inverse Inorganic Materials Design](https://mlsanity.com/paper/2210.11931/) (2022)
- [Pushdown Layers: Encoding Recursive Structure in Transformer Language Models](https://mlsanity.com/paper/2310.19089/) (2023)
- [Stack Attention: Improving the Ability of Transformers to Model Hierarchical Patterns](https://mlsanity.com/paper/2310.01749/) (2023)
- [Learning Hierarchical Structures with Differentiable Nondeterministic Stacks](https://mlsanity.com/paper/2109.01982/) (2021)
- [GALOIS: Boosting Deep Reinforcement Learning via Generalizable Logic Synthesis](https://mlsanity.com/paper/2205.13728/) (2022)
- [Memory Mosaics](https://mlsanity.com/paper/2405.06394/) (2024)
- [Memory-Based Meta-Learning on Non-Stationary Distributions](https://mlsanity.com/paper/2302.03067/) (2023)
- [On the Expressiveness and Length Generalization of Selective State-Space Models on Regular Languages](https://mlsanity.com/paper/2412.19350/) (2024)
- [UnweaveNet: Unweaving Activity Stories](https://mlsanity.com/paper/2112.10194/) (2021)

## Abstract (arXiv)

Despite the recent achievements in machine learning, we are still very far from achieving real artificial intelligence. In this paper, we discuss the limitations of standard deep learning approaches and show that some of these limitations can be overcome by learning how to grow the complexity of a model in a structured way. Specifically, we study the simplest sequence prediction problems that are beyond the scope of what is learnable with standard recurrent networks, algorithmically generated sequences which can only be learned by models which have the capacity to count and to memorize sequences. We show that some basic algorithms can be learned from sequential data using a recurrent network associated with a trainable memory.