# Compositional Program Generation for Few-Shot Systematic Generalization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 25 references that are in the map.
- First posted on arXiv 28 Sep 2023.

## Builds on (most cited first, 15 of 15)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Neural Module Networks](https://mlsanity.com/paper/1511.02799/) (2015)
- [Measuring Compositional Generalization: A Comprehensive Method on Realistic Data](https://mlsanity.com/paper/1912.09713/) (2019)
- [Compositionality decomposed: how do neural networks generalise?](https://mlsanity.com/paper/1908.08351/) (2019)
- [COGS: A Compositional Generalization Challenge Based on Semantic Interpretation](https://mlsanity.com/paper/2010.05465/) (2020)
- [Routing Networks: Adaptive Selection of Non-linear Functions for Multi-Task Learning](https://mlsanity.com/paper/1711.01239/) (2017)
- [The Devil is in the Detail: Simple Tricks Improve Systematic Generalization of Transformers](https://mlsanity.com/paper/2108.12284/) (2021)
- [Span-based Semantic Parsing for Compositional Generalization](https://mlsanity.com/paper/2009.06040/) (2020)
- [Learning Compositional Rules via Neural Program Synthesis](https://mlsanity.com/paper/2003.05562/) (2020)
- [Compositional Generalization by Learning Analytical Expressions](https://mlsanity.com/paper/2006.10627/) (2020)
- [Rearranging the Familiar: Testing Compositional Generalization in Recurrent Networks](https://mlsanity.com/paper/1807.07545/) (2018)
- [Routing Networks and the Challenges of Modular and Compositional Computation](https://mlsanity.com/paper/1904.12774/) (2019)
- [Learning Algebraic Recombination for Compositional Generalization](https://mlsanity.com/paper/2107.06516/) (2021)

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

- [Neuro-Symbolic AI in 2024: A Systematic Review](https://mlsanity.com/paper/2501.05435/) (2025)
- [A Survey on Compositional Learning of AI Models: Theoretical and Experimental Practices](https://mlsanity.com/paper/2406.08787/) (2024)
- [Exploring Compositional Generalization (in COGS/ReCOGS_pos) by Transformers using Restricted Access Sequence Processing (RASP)](https://mlsanity.com/paper/2504.15349/) (2025)
- [A Neuroscience-Inspired Dual-Process Model of Compositional Generalization](https://mlsanity.com/paper/2507.18868/) (2025)

## Abstract (arXiv)

Compositional generalization is a key ability of humans that enables us to learn new concepts from only a handful examples. Neural machine learning models, including the now ubiquitous Transformers, struggle to generalize in this way, and typically require thousands of examples of a concept during training in order to generalize meaningfully. This difference in ability between humans and artificial neural architectures, motivates this study on a neuro-symbolic architecture called the Compositional Program Generator (CPG). CPG has three key features: textitmodularity, textitcomposition, and textitabstraction, in the form of grammar rules, that enable it to generalize both systematically to new concepts in a few-shot manner, as well as productively by length on various sequence-to-sequence language tasks. For each input, CPG uses a grammar of the input language and a parser to generate a parse in which each grammar rule is assigned its own unique semantic module, a probabilistic copy or substitution program. Instances with the same parse are always processed with the same composed modules, while those with different parses may be processed with different modules. CPG learns parameters for the modules and is able to learn the semantics for new rules and types incrementally, without forgetting or retraining on rules it's already seen. It achieves perfect generalization on both the SCAN and COGS benchmarks using just 14 examples for SCAN and 22 examples for COGS -- state-of-the-art accuracy with a 1000x improvement in sample efficiency.