Leveraging Language to Learn Program Abstractions and Search Heuristics

Catherine Wong, Kevin Ellis, Joshua B. Tenenbaum, Jacob Andreas

Abstract

Inductive program synthesis offers a paradigm for building interpretable and generalizable machine learning systems. However, effective synthesis requires a strong library of functions and an efficient search strategy. We introduce LAPS (Language for Abstraction and Program Search), a technique that uses natural language annotations to guide the joint learning of libraries and neurally-guided search models. Integrated into the DreamCoder framework, LAPS produces higher-quality libraries and improves search efficiency across string editing, graphics, and scene reasoning domains, even when language is unavailable at test time.

Introduction

Inductive program synthesis—automatically generating code from input/output examples—is a long-standing goal in AI. While it promises interpretable models, the infinite search space of programs makes it computationally expensive. Modern approaches like DreamCoder attempt to mitigate this by iteratively learning a library of domain-specific abstractions and a neural search heuristic. However, learning these from scratch often results in brittle abstractions that fail to generalize. This work proposes that natural language can serve as a crucial scaffold to organize these abstractions and guide the search process.

The LAPS Framework

LAPS extends the DreamCoder architecture by incorporating a joint generative model of programs and natural language. Instead of a prior over programs alone, LAPS learns a joint prior $P(\rho, l)$ relating a program $\rho$ to a language description $l$.

Comparison of the standard DreamCoder algorithm (top) and the proposed LAPS framework (bottom), highlighting how language guides search and abstraction.

The framework introduces three key language-guided components:

  1. Language-Guided Search: The neural search model is conditioned on both I/O examples and language descriptions during training, allowing it to learn compositional patterns (e.g., mapping "hexagon" to a specific loop).
  2. Language-Guided Abstraction: When discovering new library functions, LAPS biases the search toward code fragments that correspond clearly to language tokens. This "naming" bias ensures that abstractions represent meaningful, generalizable concepts.
  3. Mutual Exclusivity Prior: Inspired by developmental psychology, this bias assumes that new words likely refer to previously unsolved program components, helping the model learn in distant supervision settings.

Experimental Evaluation

LAPS was evaluated across three domains using both synthetic and human-collected language annotations:

  • String Editing: Regex-style transformations.
  • Compositional Graphics: LOGO-style turtle graphics for drawing complex shapes.
  • Structured Scene Reasoning: Reasoning about and manipulating 3D scenes, extending the CLEVR benchmark.
Examples of structured scene reasoning tasks where the system must count or identify objects based on visual scenes.

Results and Discussion

LAPS consistently outperformed baseline models. In the graphics domain, LAPS solved 91.0% of test tasks compared to DreamCoder's 41.4%. In scene reasoning, it achieved 95.6% accuracy versus 67.8% for the non-language baseline.

Crucially, the benefits of LAPS persist even when language hints are removed at test time. This indicates that the language-guided training process helps the system build a fundamentally more robust and generalizable library of abstractions. By forcing code to align with language, the system avoids overfitting to arbitrary repeating patterns and instead discovers functions that represent human-interpretable concepts like "polygon" or "row."

Conclusion

LAPS demonstrates that natural language is a powerful tool for guiding the discovery of program abstractions. By treating language and code as jointly generated, the system learns more efficient search heuristics and higher-quality libraries. Future work will explore integrating more sophisticated neural translation models and scaling these techniques to even more complex, hierarchical program spaces.

Summary updated

Abstract

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.
BibTeX
@inproceedings{wong2021leveraging,
  author = {Catherine Wong and Kevin Ellis and Joshua B. Tenenbaum and Jacob Andreas},
  title = {{Leveraging Language to Learn Program Abstractions and Search Heuristics}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=o6FDGtjIthQ},
}
Figure