Leveraging Language to Learn Program Abstractions and Search Heuristics

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

Introduction

LAPS (Language for Abstraction and Program Search) is a framework that uses natural language annotations to bootstrap program synthesis. By jointly learning a library of code abstractions and a neural search heuristic, LAPS achieves significantly better performance and faster learning across domains like graphics and string editing—even when no language is provided at test time.

The Challenge of Program Synthesis

Inductive program synthesis—the ability for a machine to write code based on examples of desired behavior—is a "holy grail" of AI. However, it faces two massive hurdles:

  1. The Search Space: There are infinitely many ways to combine code primitives, making it nearly impossible to find a solution for complex tasks without guidance.
  2. The Library Problem: To solve hard problems, a system needs a "library" of high-level, reusable functions. Learning these abstractions from scratch is computationally brutal, often requiring thousands of CPU hours.

While humans use language to name concepts (e.g., "draw a hexagon") and decompose problems into parts, most synthesis models treat language as an afterthought or a simple label. This paper asks: can we use the structure of natural language to guide the discovery of both code abstractions and the search strategies used to find them?

The LAPS Framework

LAPS builds upon DreamCoder, a state-of-the-art "wake-sleep" Bayesian learning algorithm. In the standard DreamCoder setup, the model alternates between searching for programs (wake) and refactoring its library to better compress those programs (sleep).

LAPS vs DreamCoder framework

LAPS extends this baseline by introducing a joint generative model of programs and language. Key technical components include:

  • Language-Conditioned Search: Instead of searching based only on input/output examples, LAPS trains a neural model to predict programs using both the examples and natural language descriptions.
  • Compositional Translation: The model uses a "translation" layer (based on IBM Model 4) to map specific words in a description to specific code primitives in the library. This ensures that if a user says "hexagon," the model looks for a code snippet that actually draws a hexagon.
  • Mutual Exclusivity Prior: Borrowing a concept from developmental psychology, the authors implement a prior where "new" words are assumed to refer to "new" or less-used code components. This helps the model learn in "distant supervision" settings where it lacks ground-truth programs for every task.

Evaluation Domains

The authors evaluated LAPS on three diverse domains, using both synthetic (template-based) and human-sourced (Mechanical Turk) language:

  1. String Editing: Transforming text strings (e.g., "cools" $\rightarrow$ "gcools") based on regex-like rules.
  2. Compositional Graphics: A challenging LOGO-style turtle graphics environment where the model must draw complex shapes like "a seven-pointed snowflake."
  3. Structured Scene Reasoning: A modified version of the CLEVR dataset, requiring the model to answer questions or "imagine" scene changes (e.g., "what if the red things turned blue?").

Key Findings and Results

  • Language as a Scaffold, Not Just a Hint: The most striking insight is that language helps the model learn a better library. By forcing code abstractions to correspond to linguistic tokens, the model avoids "overfitting" its library to specific training tasks and instead discovers more generalizable functions.
  • Generalization to "Silent" Testing: Even if language descriptions are removed at test time, the LAPS-trained model outperforms the baseline. The library it built during the "language-guided" training phase is structurally superior.
  • Massive Performance Gains: In the graphics domain, LAPS solved ~98% of held-out tasks, compared to only ~50% for the baseline DreamCoder.
  • Efficiency and Search Effectiveness: LAPS reaches high performance levels in significantly fewer iterations than the baseline, effectively "compressing" the thousands of CPU hours usually required for library learning. During training, it consistently finds solutions to more diverse and difficult tasks, providing a richer "data diet" for the library-learning phase.
  • Robustness to Noise: The system is surprisingly robust to the variability of human language. It doesn't need a rigid grammar; it just needs to find consistent statistical correspondences between words and code fragments.

Limitations and Future Directions

While LAPS is a major step forward, some limitations remain. The model currently requires language annotations during the training phase. While these can be synthetic, the best results come from having some human-in-the-loop descriptions. Additionally, the authors used a relatively classic statistical translation model (IBM Model 4). Future work could integrate more powerful, pre-trained Transformers (like GPT-4 or specialized code models) to handle even more complex linguistic nuances. Ultimately, LAPS also serves as a compelling computational model to study how humans learn concepts through the interplay of language and symbolic reasoning.

Summary updated

Abstract

Inductive program synthesis, or inferring programs from examples of desired behavior, offers a general paradigm for building interpretable, robust, andgeneralizable machine learning systems. Effect...
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