# Strong Generalization and Efficiency in Neural Programs

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jul 2020.

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

- [Scaling up Test-Time Compute with Latent Reasoning: A Recurrent Depth Approach](https://mlsanity.com/paper/2502.05171/) (2025)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [Neural Algorithmic Reasoning](https://mlsanity.com/paper/2105.02761/) (2021)
- [Neural Production Systems: Learning Rule-Governed Visual Dynamics](https://mlsanity.com/paper/2103.01937/) (2021)
- [Learning to Synthesize Programs as Interpretable and Generalizable Policies](https://mlsanity.com/paper/2108.13643/) (2021)
- [Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks](https://mlsanity.com/paper/2211.00692/) (2022)
- [Neural Set Function Extensions: Learning with Discrete Functions in High Dimensions](https://mlsanity.com/paper/2208.04055/) (2022)
- [PUZZLES: A Benchmark for Neural Algorithmic Reasoning](https://mlsanity.com/paper/2407.00401/) (2024)
- [Recursive Algorithmic Reasoning](https://mlsanity.com/paper/2307.00337/) (2023)
- [Infusing Lattice Symmetry Priors in Attention Mechanisms for Sample-Efficient Abstract Geometric Reasoning](https://mlsanity.com/paper/2306.03175/) (2023)
- [Open-Book Neural Algorithmic Reasoning](https://mlsanity.com/paper/2501.00072/) (2024)

## Abstract (arXiv)

We study the problem of learning efficient algorithms that strongly generalize in the framework of neural program induction. By carefully designing the input / output interfaces of the neural model and through imitation, we are able to learn models that produce correct results for arbitrary input sizes, achieving strong generalization. Moreover, by using reinforcement learning, we optimize for program efficiency metrics, and discover new algorithms that surpass the teacher used in imitation. With this, our approach can learn to outperform custom-written solutions for a variety of problems, as we tested it on sorting, searching in ordered lists and the NP-complete 0/1 knapsack problem, which sets a notable milestone in the field of Neural Program Induction. As highlights, our learned model can perform sorting perfectly on any input data size we tested on, with O(n log n) complexity, whilst outperforming hand-coded algorithms, including quick sort, in number of operations even for list sizes far beyond those seen during training.