# Compositional Generalization via Neural-Symbolic Stack Machines

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

## Key facts

- Cited by 80 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Aug 2020.

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

- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [The Devil is in the Detail: Simple Tricks Improve Systematic Generalization of Transformers](https://mlsanity.com/paper/2108.12284/) (2021)
- [Teaching Algorithmic Reasoning via In-context Learning](https://mlsanity.com/paper/2211.09066/) (2022)
- [An Empirical Survey of Data Augmentation for Limited Data Learning in NLP](https://mlsanity.com/paper/2106.07499/) (2021)
- [Compositional Semantic Parsing with Large Language Models](https://mlsanity.com/paper/2209.15003/) (2022)
- [Large Language Models can Learn Rules](https://mlsanity.com/paper/2310.07064/) (2023)
- [The Neural Data Router: Adaptive Control Flow in Transformers Improves Systematic Generalization](https://mlsanity.com/paper/2110.07732/) (2021)
- [Unlocking Compositional Generalization in Pre-trained Models Using Intermediate Representations](https://mlsanity.com/paper/2104.07478/) (2021)
- [Neuro-Symbolic Artificial Intelligence: Current Trends](https://mlsanity.com/paper/2105.05330/) (2021)
- [How Do In-Context Examples Affect Compositional Generalization?](https://mlsanity.com/paper/2305.04835/) (2023)
- [Evaluating the Impact of Model Scale for Compositional Generalization in Semantic Parsing](https://mlsanity.com/paper/2205.12253/) (2022)
- [Improving Compositional Generalization with Latent Structure and Data Augmentation](https://mlsanity.com/paper/2112.07610/) (2021)
- [Is Neuro-Symbolic AI Meeting its Promise in Natural Language Processing? A Structured Review](https://mlsanity.com/paper/2202.12205/) (2022)
- [SeqZero: Few-shot Compositional Semantic Parsing with Sequential Prompts and Zero-shot Models](https://mlsanity.com/paper/2205.07381/) (2022)
- [Learning Iterative Reasoning through Energy Diffusion](https://mlsanity.com/paper/2406.11179/) (2024)
- [Towards Data-and Knowledge-Driven Artificial Intelligence: A Survey on Neuro-Symbolic Computing](https://mlsanity.com/paper/2210.15889/) (2022)
- [On Compositional Generalization of Neural Machine Translation](https://mlsanity.com/paper/2105.14802/) (2021)
- [Skills-in-Context Prompting: Unlocking Compositionality in Large Language Models](https://mlsanity.com/paper/2308.00304/) (2023)
- [Learning Algebraic Recombination for Compositional Generalization](https://mlsanity.com/paper/2107.06516/) (2021)
- [Sequence-to-Sequence Learning with Latent Neural Grammars](https://mlsanity.com/paper/2109.01135/) (2021)
- [Pointer Value Retrieval: A new benchmark for understanding the limits of neural network generalization](https://mlsanity.com/paper/2107.12580/) (2021)
- [Unobserved Local Structures Make Compositional Generalization Hard](https://mlsanity.com/paper/2201.05899/) (2022)
- [Learning Algebraic Representation for Systematic Generalization in Abstract Reasoning](https://mlsanity.com/paper/2111.12990/) (2021)
- [How to Reuse and Compose Knowledge for a Lifetime of Tasks: A Survey on Continual Learning and Functional Composition](https://mlsanity.com/paper/2207.07730/) (2022)
- [Neural-Logic Human-Object Interaction Detection](https://mlsanity.com/paper/2311.09817/) (2023)
- [ProTo: Program-Guided Transformer for Program-Guided Tasks](https://mlsanity.com/paper/2110.00804/) (2021)
- [Revisiting the Compositional Generalization Abilities of Neural Sequence Models](https://mlsanity.com/paper/2203.07402/) (2022)
- [General Intelligence Requires Rethinking Exploration](https://mlsanity.com/paper/2211.07819/) (2022)
- [ReaSCAN: Compositional Reasoning in Language Grounding](https://mlsanity.com/paper/2109.08994/) (2021)
- [Annealed Training for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2207.11542/) (2022)

## Abstract (arXiv)

Despite achieving tremendous success, existing deep learning models have exposed limitations in compositional generalization, the capability to learn compositional rules and apply them to unseen cases in a systematic manner. To tackle this issue, we propose the Neural-Symbolic Stack Machine (NeSS). It contains a neural network to generate traces, which are then executed by a symbolic stack machine enhanced with sequence manipulation operations. NeSS combines the expressive power of neural sequence models with the recursion supported by the symbolic stack machine. Without training supervision on execution traces, NeSS achieves 100% generalization performance in four domains: the SCAN benchmark of language-driven navigation tasks, the task of few-shot learning of compositional instructions, the compositional machine translation benchmark, and context-free grammar parsing tasks.