# Leveraging Language to Learn Program Abstractions and Search Heuristics

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

## Key facts

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

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

- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [CLEVR: A Diagnostic Dataset for Compositional Language and Elementary Visual Reasoning](https://mlsanity.com/paper/1612.06890/) (2016)
- [The Neuro-Symbolic Concept Learner: Interpreting Scenes, Words, and Sentences From Natural Supervision](https://mlsanity.com/paper/1904.12584/) (2019)
- [Neural-Symbolic VQA: Disentangling Reasoning from Vision and Language Understanding](https://mlsanity.com/paper/1810.02338/) (2018)
- [DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning](https://mlsanity.com/paper/2006.08381/) (2020)
- [A Survey of Reinforcement Learning Informed by Natural Language](https://mlsanity.com/paper/1906.03926/) (2019)
- [DeepCoder: Learning to Write Programs](https://mlsanity.com/paper/1611.01989/) (2016)
- [Inferring and Executing Programs for Visual Reasoning](https://mlsanity.com/paper/1705.03633/) (2017)
- [RobustFill: Neural Program Learning under Noisy I/O](https://mlsanity.com/paper/1703.07469/) (2017)
- [Data Recombination for Neural Semantic Parsing](https://mlsanity.com/paper/1606.03622/) (2016)
- [Building machines that adapt and compute like brains](https://mlsanity.com/paper/1711.04203/) (2017)
- [Tree-to-tree Neural Networks for Program Translation](https://mlsanity.com/paper/1802.03691/) (2018)
- [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)
- [Compound Probabilistic Context-Free Grammars for Grammar Induction](https://mlsanity.com/paper/1906.10225/) (2019)
- [Learning with Latent Language](https://mlsanity.com/paper/1711.00482/) (2017)
- [Learning to Infer Graphics Programs from Hand-Drawn Images](https://mlsanity.com/paper/1707.09627/) (2017)
- [Synthesizing Programs for Images using Reinforced Adversarial Learning](https://mlsanity.com/paper/1804.01118/) (2018)
- [Learning Neural Templates for Text Generation](https://mlsanity.com/paper/1808.10122/) (2018)
- [Human few-shot learning of compositional instructions](https://mlsanity.com/paper/1901.04587/) (2019)
- [Learning to Infer Program Sketches](https://mlsanity.com/paper/1902.06349/) (2019)
- [Program Synthesis using Natural Language](https://mlsanity.com/paper/1509.00413/) (2015)
- [ALICE: Active Learning with Contrastive Natural Language Explanations](https://mlsanity.com/paper/2009.10259/) (2020)
- [Program Synthesis and Semantic Parsing with Learned Code Idioms](https://mlsanity.com/paper/1906.10816/) (2019)
- [Few-Shot Bayesian Imitation Learning with Logical Program Policies](https://mlsanity.com/paper/1904.06317/) (2019)
- [PixL2R: Guiding Reinforcement Learning Using Natural Language by Mapping Pixels to Rewards](https://mlsanity.com/paper/2007.15543/) (2020)
- [Shaping Visual Representations with Language for Few-shot Classification](https://mlsanity.com/paper/1911.02683/) (2019)
- [Neural Program Synthesis with Priority Queue Training](https://mlsanity.com/paper/1801.03526/) (2018)
- [Learning abstract structure for drawing by efficient motor program induction](https://mlsanity.com/paper/2008.03519/) (2020)

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

- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [Skill Induction and Planning with Latent Language](https://mlsanity.com/paper/2110.01517/) (2021)
- [Symbolic Regression with a Learned Concept Library](https://mlsanity.com/paper/2409.09359/) (2024)
- [TroVE: Inducing Verifiable and Efficient Toolboxes for Solving Programmatic Tasks](https://mlsanity.com/paper/2401.12869/) (2024)
- [Learning to Synthesize Programs as Interpretable and Generalizable Policies](https://mlsanity.com/paper/2108.13643/) (2021)
- [Top-Down Synthesis for Library Learning](https://mlsanity.com/paper/2211.16605/) (2022)
- [Structured, flexible, and robust: benchmarking and improving large language models towards more human-like behavior in out-of-distribution reasoning tasks](https://mlsanity.com/paper/2205.05718/) (2022)
- [What Are Tools Anyway? A Survey from the Language Model Perspective](https://mlsanity.com/paper/2403.15452/) (2024)
- [LILO: Learning Interpretable Libraries by Compressing and Documenting Code](https://mlsanity.com/paper/2310.19791/) (2023)
- [Learning adaptive planning representations with natural language guidance](https://mlsanity.com/paper/2312.08566/) (2023)
- [ReGAL: Refactoring Programs to Discover Generalizable Abstractions](https://mlsanity.com/paper/2401.16467/) (2024)
- [Program Transfer for Answering Complex Questions over Knowledge Bases](https://mlsanity.com/paper/2110.05743/) (2021)
- [Is Programming by Example solved by LLMs?](https://mlsanity.com/paper/2406.08316/) (2024)
- [How to talk so AI will learn: Instructions, descriptions, and autonomy](https://mlsanity.com/paper/2206.07870/) (2022)
- [Human-like Few-Shot Learning via Bayesian Reasoning over Natural Language](https://mlsanity.com/paper/2306.02797/) (2023)
- [Using Natural Language and Program Abstractions to Instill Human Inductive Biases in Machines](https://mlsanity.com/paper/2205.11558/) (2022)
- [Language and Culture Internalisation for Human-Like Autotelic AI](https://mlsanity.com/paper/2206.01134/) (2022)
- [ANPL: Towards Natural Programming with Interactive Decomposition](https://mlsanity.com/paper/2305.18498/) (2023)
- [Loose LIPS Sink Ships: Asking Questions in Battleship with Language-Informed Program Sampling](https://mlsanity.com/paper/2402.19471/) (2024)
- [Identifying concept libraries from language about object structure](https://mlsanity.com/paper/2205.05666/) (2022)
- [Neurosymbolic Programming for Science](https://mlsanity.com/paper/2210.05050/) (2022)
- [Using Program Synthesis and Inductive Logic Programming to solve Bongard Problems](https://mlsanity.com/paper/2110.09947/) (2021)
- [LEMMA: Bootstrapping High-Level Mathematical Reasoning with Learned Symbolic Abstractions](https://mlsanity.com/paper/2211.08671/) (2022)
- [Generating Language Corrections for Teaching Physical Control Tasks](https://mlsanity.com/paper/2306.07012/) (2023)
- [Policy Learning with a Language Bottleneck](https://mlsanity.com/paper/2405.04118/) (2024)
- [TurtleBench: A Visual Programming Benchmark in Turtle Geometry](https://mlsanity.com/paper/2411.00264/) (2024)
- [Refactoring Codebases through Library Design](https://mlsanity.com/paper/2506.11058/) (2025)
- [Skill-as-Pseudocode: Refactoring Skill Libraries to Pseudocode for LLM Agents](https://mlsanity.com/paper/2605.27955/) (2026)
- [lilGym: Natural Language Visual Reasoning with Reinforcement Learning](https://mlsanity.com/paper/2211.01994/) (2022)
- [SemSup: Semantic Supervision for Simple and Scalable Zero-shot Generalization](https://mlsanity.com/paper/2202.13100/) (2022)

## Abstract (arXiv)

Inductive program synthesis, or inferring programs from examples of desired behavior, offers a general paradigm for building interpretable, robust, and generalizable machine learning systems. Effective program synthesis depends on two key ingredients: a strong library of functions from which to build programs, and an efficient search strategy for finding programs that solve a given task. We introduce LAPS (Language for Abstraction and Program Search), a technique for using natural language annotations to guide joint learning of libraries and neurally-guided search models for synthesis. When integrated into a state-of-the-art library learning system (DreamCoder), LAPS produces higher-quality libraries and improves search efficiency and generalization on three domains -- string editing, image composition, and abstract reasoning about scenes -- even when no natural language hints are available at test time.