# Communicating Natural Programs to Humans and Machines

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 95 references that are in the map.
- First posted on arXiv 15 Jun 2021.

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

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Vision-and-Language Navigation: Interpreting visually-grounded navigation instructions in real environments](https://mlsanity.com/paper/1711.07280/) (2017)
- [MultiWOZ -- A Large-Scale Multi-Domain Wizard-of-Oz Dataset for Task-Oriented Dialogue Modelling](https://mlsanity.com/paper/1810.00278/) (2018)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [A Network-based End-to-End Trainable Task-oriented Dialogue System](https://mlsanity.com/paper/1604.04562/) (2016)
- [SPoC: Search-based Pseudocode to Code](https://mlsanity.com/paper/1906.04908/) (2019)
- [Constrained Language Models Yield Few-Shot Semantic Parsers](https://mlsanity.com/paper/2104.08768/) (2021)
- [DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning](https://mlsanity.com/paper/2006.08381/) (2020)
- [DeepCoder: Learning to Write Programs](https://mlsanity.com/paper/1611.01989/) (2016)
- [RobustFill: Neural Program Learning under Noisy I/O](https://mlsanity.com/paper/1703.07469/) (2017)
- [Task-Oriented Dialogue as Dataflow Synthesis](https://mlsanity.com/paper/2009.11423/) (2020)
- [Data Recombination for Neural Semantic Parsing](https://mlsanity.com/paper/1606.03622/) (2016)
- [Write, Execute, Assess: Program Synthesis with a REPL](https://mlsanity.com/paper/1906.04604/) (2019)
- [Neuro-Symbolic Program Synthesis](https://mlsanity.com/paper/1611.01855/) (2016)
- [Learning with Latent Language](https://mlsanity.com/paper/1711.00482/) (2017)
- [Executing Instructions in Situated Collaborative Interactions](https://mlsanity.com/paper/1910.03655/) (2019)
- [Learning to Infer Program Sketches](https://mlsanity.com/paper/1902.06349/) (2019)
- [Learning Language Games through Interaction](https://mlsanity.com/paper/1606.02447/) (2016)
- [Program Synthesis using Natural Language](https://mlsanity.com/paper/1509.00413/) (2015)
- [From Language to Programs: Bridging Reinforcement Learning and Maximum Marginal Likelihood](https://mlsanity.com/paper/1704.07926/) (2017)
- [Language Models as Few-Shot Learner for Task-Oriented Dialogue Systems](https://mlsanity.com/paper/2008.06239/) (2020)
- [Learning Rewards from Linguistic Feedback](https://mlsanity.com/paper/2009.14715/) (2020)
- [Simpler Context-Dependent Logical Forms via Model Projections](https://mlsanity.com/paper/1606.05378/) (2016)
- [Improving Policies via Search in Cooperative Partially Observable Games](https://mlsanity.com/paper/1912.02318/) (2019)
- [Fast and flexible: Human program induction in abstract reasoning tasks](https://mlsanity.com/paper/2103.05823/) (2021)
- [Neural Program Synthesis with Priority Queue Training](https://mlsanity.com/paper/1801.03526/) (2018)
- [Neural Program Meta-Induction](https://mlsanity.com/paper/1710.04157/) (2017)

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

- [Hypothesis Search: Inductive Reasoning with Language Models](https://mlsanity.com/paper/2309.05660/) (2023)
- [The ConceptARC Benchmark: Evaluating Understanding and Generalization in the ARC Domain](https://mlsanity.com/paper/2305.07141/) (2023)
- [The Surprising Effectiveness of Test-Time Training for Few-Shot Learning](https://mlsanity.com/paper/2411.07279/) (2024)
- [Phenomenal Yet Puzzling: Testing Inductive Reasoning Capabilities of Language Models with Hypothesis Refinement](https://mlsanity.com/paper/2310.08559/) (2023)
- [LLMs and the Abstraction and Reasoning Corpus: Successes, Failures, and the Importance of Object-based Representations](https://mlsanity.com/paper/2305.18354/) (2023)
- [Parsel: Algorithmic Reasoning with Language Models by Composing Decompositions](https://mlsanity.com/paper/2212.10561/) (2022)
- [Grammar Prompting for Domain-Specific Language Generation with Large Language Models](https://mlsanity.com/paper/2305.19234/) (2023)
- [Large Language Models Are Not Strong Abstract Reasoners](https://mlsanity.com/paper/2305.19555/) (2023)
- [A Review of Emerging Research Directions in Abstract Visual Reasoning](https://mlsanity.com/paper/2202.10284/) (2022)
- [H-ARC: A Robust Estimate of Human Performance on the Abstraction and Reasoning Corpus Benchmark](https://mlsanity.com/paper/2409.01374/) (2024)
- [Graphs, Constraints, and Search for the Abstraction and Reasoning Corpus](https://mlsanity.com/paper/2210.09880/) (2022)
- [Abstract Visual Reasoning Enabled by Language](https://mlsanity.com/paper/2303.04091/) (2023)
- [Evaluating statistical language models as pragmatic reasoners](https://mlsanity.com/paper/2305.01020/) (2023)
- [ANPL: Towards Natural Programming with Interactive Decomposition](https://mlsanity.com/paper/2305.18498/) (2023)
- [Unraveling the ARC Puzzle: Mimicking Human Solutions with Object-Centric Decision Transformer](https://mlsanity.com/paper/2306.08204/) (2023)
- [Toward Trustworthy Neural Program Synthesis](https://mlsanity.com/paper/2210.00848/) (2022)
- [Large Language Model (LLM) as a System of Multiple Expert Agents: An Approach to solve the Abstraction and Reasoning Corpus (ARC) Challenge](https://mlsanity.com/paper/2310.05146/) (2023)
- [The Stochastic Parrot on LLM's Shoulder: A Summative Assessment of Physical Concept Understanding](https://mlsanity.com/paper/2502.08946/) (2025)
- [ARC-GEN: A Mimetic Procedural Benchmark Generator for the Abstraction and Reasoning Corpus](https://mlsanity.com/paper/2511.00162/) (2025)
- [A Neurodiversity-Inspired Solver for the Abstraction & Reasoning Corpus (ARC) Using Visual Imagery and Program Synthesis](https://mlsanity.com/paper/2302.09425/) (2023)
- [ConceptSearch: Towards Efficient Program Search Using LLMs for Abstraction and Reasoning Corpus (ARC)](https://mlsanity.com/paper/2412.07322/) (2024)
- [Tackling the Abstraction and Reasoning Corpus (ARC) with Object-centric Models and the MDL Principle](https://mlsanity.com/paper/2311.00545/) (2023)
- [ARCLE: The Abstraction and Reasoning Corpus Learning Environment for Reinforcement Learning](https://mlsanity.com/paper/2407.20806/) (2024)
- [DiffVL: Scaling Up Soft Body Manipulation using Vision-Language Driven Differentiable Physics](https://mlsanity.com/paper/2312.06408/) (2023)
- [Adapting Like Humans: A Metacognitive Agent with Test-time Reasoning](https://mlsanity.com/paper/2511.23262/) (2025)
- [Infusing Lattice Symmetry Priors in Attention Mechanisms for Sample-Efficient Abstract Geometric Reasoning](https://mlsanity.com/paper/2306.03175/) (2023)
- [Program Synthesis using Inductive Logic Programming for the Abstraction and Reasoning Corpus](https://mlsanity.com/paper/2405.06399/) (2024)
- [SemSup: Semantic Supervision for Simple and Scalable Zero-shot Generalization](https://mlsanity.com/paper/2202.13100/) (2022)
- [Cognitive maps are generative programs](https://mlsanity.com/paper/2504.20628/) (2025)
- [GIFARC: Synthetic Dataset for Leveraging Human-Intuitive Analogies to Elevate AI Reasoning](https://mlsanity.com/paper/2505.20672/) (2025)

## Abstract (arXiv)

The Abstraction and Reasoning Corpus (ARC) is a set of procedural tasks that tests an agent's ability to flexibly solve novel problems. While most ARC tasks are easy for humans, they are challenging for state-of-the-art AI. What makes building intelligent systems that can generalize to novel situations such as ARC difficult? We posit that the answer might be found by studying the difference of language: While humans readily generate and interpret instructions in a general language, computer systems are shackled to a narrow domain-specific language that they can precisely execute. We present LARC, the textitLanguage-complete ARC: a collection of natural language descriptions by a group of human participants who instruct each other on how to solve ARC tasks using language alone, which contains successful instructions for 88% of the ARC tasks. We analyze the collected instructions as `natural programs', finding that while they resemble computer programs, they are distinct in two ways: First, they contain a wide range of primitives; Second, they frequently leverage communicative strategies beyond directly executable codes. We demonstrate that these two distinctions prevent current program synthesis techniques from leveraging LARC to its full potential, and give concrete suggestions on how to build the next-generation program synthesizers.