# Top-Down Synthesis for Library Learning

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

## Key facts

- Cited by 58 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 64 references that are in the map.
- First posted on arXiv 29 Nov 2022.

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

- [A Survey of Machine Learning for Big Code and Naturalness](https://mlsanity.com/paper/1709.06182/) (2017)
- [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)
- [Synthesizing Programs for Images using Reinforced Adversarial Learning](https://mlsanity.com/paper/1804.01118/) (2018)
- [Leveraging Language to Learn Program Abstractions and Search Heuristics](https://mlsanity.com/paper/2106.11053/) (2021)
- [Program Synthesis and Semantic Parsing with Learned Code Idioms](https://mlsanity.com/paper/1906.10816/) (2019)
- [Learning Differentiable Programs with Admissible Neural Heuristics](https://mlsanity.com/paper/2007.12101/) (2020)
- [Beyond imitation: Zero-shot task transfer on robots by learning concepts as cognitive programs](https://mlsanity.com/paper/1812.02788/) (2018)
- [Program Synthesis from Polymorphic Refinement Types](https://mlsanity.com/paper/1510.08419/) (2015)
- [Mining Idioms from Source Code](https://mlsanity.com/paper/1404.0417/) (2014)
- [Learning Programmatic Idioms for Scalable Semantic Parsing](https://mlsanity.com/paper/1904.09086/) (2019)
- [Representing Partial Programs with Blended Abstract Semantics](https://mlsanity.com/paper/2012.12964/) (2020)
- [Multi-modal Synthesis of Regular Expressions](https://mlsanity.com/paper/1908.03316/) (2019)
- [Playgol: learning programs through play](https://mlsanity.com/paper/1904.08993/) (2019)
- [Identifying concept libraries from language about object structure](https://mlsanity.com/paper/2205.05666/) (2022)
- [On Repair with Probabilistic Attribute Grammars](https://mlsanity.com/paper/1707.04148/) (2017)

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

- [Agent Workflow Memory](https://mlsanity.com/paper/2409.07429/) (2024)
- [Self-Taught Optimizer (STOP): Recursively Self-Improving Code Generation](https://mlsanity.com/paper/2310.02304/) (2023)
- [WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environment](https://mlsanity.com/paper/2402.12275/) (2024)
- [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)
- [Clover: Closed-Loop Verifiable Code Generation](https://mlsanity.com/paper/2310.17807/) (2023)
- [Parsel: Algorithmic Reasoning with Language Models by Composing Decompositions](https://mlsanity.com/paper/2212.10561/) (2022)
- [What Are Tools Anyway? A Survey from the Language Model Perspective](https://mlsanity.com/paper/2403.15452/) (2024)
- [Combining Induction and Transduction for Abstract Reasoning](https://mlsanity.com/paper/2411.02272/) (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)
- [ShapeCoder: Discovering Abstractions for Visual Programs from Unstructured Primitives](https://mlsanity.com/paper/2305.05661/) (2023)
- [VerMCTS: Synthesizing Multi-Step Programs using a Verifier, a Large Language Model, and Tree Search](https://mlsanity.com/paper/2402.08147/) (2024)
- [Improving Unsupervised Visual Program Inference with Code Rewriting Families](https://mlsanity.com/paper/2309.14972/) (2023)
- [ARC-GEN: A Mimetic Procedural Benchmark Generator for the Abstraction and Reasoning Corpus](https://mlsanity.com/paper/2511.00162/) (2025)
- [REFACTOR: Learning to Extract Theorems from Proofs](https://mlsanity.com/paper/2402.17032/) (2024)
- [Anti-unification and Generalization: A Survey](https://mlsanity.com/paper/2302.00277/) (2023)
- [Self-Evolving Agents with Anytime-Valid Certificates](https://mlsanity.com/paper/2607.00871/) (2026)
- [Learning of Generalizable and Interpretable Knowledge in Grid-Based Reinforcement Learning Environments](https://mlsanity.com/paper/2309.03651/) (2023)
- [Searching for Programmatic Policies in Semantic Spaces](https://mlsanity.com/paper/2405.05431/) (2024)
- [Finding structure in logographic writing with library learning](https://mlsanity.com/paper/2405.06906/) (2024)
- [Scalable and Cost-Efficient de Novo Template-Based Molecular Generation](https://mlsanity.com/paper/2506.19865/) (2025)
- [DreamProver: Evolving Transferable Lemma Libraries via a Wake-Sleep Theorem-Proving Agent](https://mlsanity.com/paper/2604.26311/) (2026)
- [Action abstractions for amortized sampling](https://mlsanity.com/paper/2410.15184/) (2024)
- [Refactoring Codebases through Library Design](https://mlsanity.com/paper/2506.11058/) (2025)
- [Artificial Intelligence and the Structure of Mathematics](https://mlsanity.com/paper/2604.06107/) (2026)
- [Skill-as-Pseudocode: Refactoring Skill Libraries to Pseudocode for LLM Agents](https://mlsanity.com/paper/2605.27955/) (2026)
- [Bayesian Program Learning by Decompiling Amortized Knowledge](https://mlsanity.com/paper/2306.07856/) (2023)
- [AbstractBeam: Enhancing Bottom-Up Program Synthesis using Library Learning](https://mlsanity.com/paper/2405.17514/) (2024)

## Abstract (arXiv)

This paper introduces corpus-guided top-down synthesis as a mechanism for synthesizing library functions that capture common functionality from a corpus of programs in a domain specific language (DSL). The algorithm builds abstractions directly from initial DSL primitives, using syntactic pattern matching of intermediate abstractions to intelligently prune the search space and guide the algorithm towards abstractions that maximally capture shared structures in the corpus. We present an implementation of the approach in a tool called Stitch and evaluate it against the state-of-the-art deductive library learning algorithm from DreamCoder. Our evaluation shows that Stitch is 3-4 orders of magnitude faster and uses 2 orders of magnitude less memory while maintaining comparable or better library quality (as measured by compressivity). We also demonstrate Stitch's scalability on corpora containing hundreds of complex programs that are intractable with prior deductive approaches and show empirically that it is robust to terminating the search procedure early -- further allowing it to scale to challenging datasets by means of early stopping.