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$.
The framework introduces three key language-guided components:
- 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).
- 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.
- 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.
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