mlsanityData to 14 Oct 2026

Top-Down Synthesis for Library Learning

arXiv 2211.16605 ↗First posted 29 Nov 2022cs.PL cs.AIcited by 58

Not on the map. Why?

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.

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

16 of 64 references.

References · 16

  1. 2017A Survey of Machine Learning for Big Code and Naturalnesscited by 221
  2. 2020DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learningcited by 161
  3. 2016DeepCoder: Learning to Write Programscited by 149
  4. 2018Synthesizing Programs for Images using Reinforced Adversarial Learningcited by 72
  5. 2021Leveraging Language to Learn Program Abstractions and Search Heuristicscited by 45
  6. 2019Program Synthesis and Semantic Parsing with Learned Code Idiomscited by 34
  7. 2020Learning Differentiable Programs with Admissible Neural Heuristicscited by 32
  8. 2018Beyond imitation: Zero-shot task transfer on robots by learning concepts as cognitive programscited by 21
  9. 2015Program Synthesis from Polymorphic Refinement Typescited by 20
  10. 2014Mining Idioms from Source Codecited by 19
  11. 2019Learning Programmatic Idioms for Scalable Semantic Parsingcited by 17
  12. 2020Representing Partial Programs with Blended Abstract Semanticscited by 14
4 more
  1. 2019Multi-modal Synthesis of Regular Expressionscited by 13
  2. 2019Playgol: learning programs through playcited by 8
  3. 2022Identifying concept libraries from language about object structurecited by 8
  4. 2017On Repair with Probabilistic Attribute Grammarscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 12; 2024: 19; 2025: 9; 2026: 17.

58 papers.

Sort:

By area:

  1. 2024Agent Workflow Memorycited by 383
  2. 2023Self-Taught Optimizer (STOP): Recursively Self-Improving Code Generationcited by 148
  3. 2024WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environmentcited by 107
  4. 2024Symbolic Regression with a Learned Concept Librarycited by 83
  5. 2024TroVE: Inducing Verifiable and Efficient Toolboxes for Solving Programmatic Taskscited by 75
  6. 2023Clover: Closed-Loop Verifiable Code Generationcited by 67
  7. 2022Parsel: Algorithmic Reasoning with Language Models by Composing Decompositionscited by 64
  8. 2024What Are Tools Anyway? A Survey from the Language Model Perspectivecited by 54
  9. 2024Combining Induction and Transduction for Abstract Reasoningcited by 53
  10. 2023LILO: Learning Interpretable Libraries by Compressing and Documenting Codecited by 49
  11. 2023Learning adaptive planning representations with natural language guidancecited by 36
  12. 2024ReGAL: Refactoring Programs to Discover Generalizable Abstractionscited by 36
38 more
  1. 2023ShapeCoder: Discovering Abstractions for Visual Programs from Unstructured Primitivescited by 23
  2. 2024VerMCTS: Synthesizing Multi-Step Programs using a Verifier, a Large Language Model, and Tree Searchcited by 14
  3. 2023Improving Unsupervised Visual Program Inference with Code Rewriting Familiescited by 10
  4. 2025ARC-GEN: A Mimetic Procedural Benchmark Generator for the Abstraction and Reasoning Corpuscited by 10
  5. 2024REFACTOR: Learning to Extract Theorems from Proofscited by 9
  6. 2023Anti-unification and Generalization: A Surveycited by 7
  7. 2026Self-Evolving Agents with Anytime-Valid Certificatescited by 6
  8. 2023Learning of Generalizable and Interpretable Knowledge in Grid-Based Reinforcement Learning Environmentscited by 5
  9. 2024Searching for Programmatic Policies in Semantic Spacescited by 5
  10. 2024Finding structure in logographic writing with library learningcited by 5
  11. 2025Scalable and Cost-Efficient de Novo Template-Based Molecular Generationcited by 5
  12. 2026DreamProver: Evolving Transferable Lemma Libraries via a Wake-Sleep Theorem-Proving Agentcited by 5
  13. 2024Action abstractions for amortized samplingcited by 4
  14. 2025Refactoring Codebases through Library Designcited by 4
  15. 2026Artificial Intelligence and the Structure of Mathematicscited by 4
  16. 2026Skill-as-Pseudocode: Refactoring Skill Libraries to Pseudocode for LLM Agentscited by 4
  17. 2023Bayesian Program Learning by Decompiling Amortized Knowledgecited by 2
  18. 2024AbstractBeam: Enhancing Bottom-Up Program Synthesis using Library Learningcited by 2
  19. 2024Algorithmic Language Models with Neurally Compiled Librariescited by 2
  20. 2025A Compute-Matched Re-Evaluation of TroVE on MATHcited by 2
  21. 2025Agent-centric learning: from external reward maximization to internal knowledge curationcited by 2
  22. 2025Learning Interestingness in Automated Mathematical Theory Formationcited by 2
  23. 2026ReaComp: Compiling LLM Reasoning into Symbolic Solvers for Efficient Program Synthesiscited by 2
  24. 2026A Compositional Framework for Open-ended Intelligencecited by 2
  25. 2023Learning logic programs by discovering higher-order abstractionscited by 1
  26. 2023Function-constrained Program Synthesiscited by 1
  27. 2024MeMo: Meaningful, Modular Controllers via Noise Injectioncited by 1
  28. 2024Unveiling the Decision-Making Process in Reinforcement Learning with Genetic Programmingcited by 1
  29. 2024Scalable Knowledge Refactoring using Constrained Optimisationcited by 1
  30. 2024PACE: Procedural Abstractions for Communicating Efficientlycited by 1
  31. 2025Analogy making as amortised model constructioncited by 1
  32. 2026Online library learning in human visual puzzle solvingcited by 1
  33. 2026Path-dependent program induction under resource constraints explains human sequence learningcited by 1
  34. 2026Beyond Fixed Representations: The Vocabulary and Verifier Gaps in Open-Ended AIcited by 1
  35. 2026SkillComposer: Learning Reusable Skills for Natural-Language Robot Programmingcited by 1
  36. 2023Symbolic Synthesis of Neural Networkscited by 0
  37. 2024MathDSL: A Domain-Specific Language for Concise Mathematical Solutions Via Program Synthesiscited by 0
  38. 2025Bayesian Inverse Physics for Neuro-Symbolic Robot Learningcited by 0

50 most cited of 58 All 58 (JSON)