DreamCoder: bootstrapping inductive program synthesis with wake-sleep library learning

By Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sablé-Meyer, Lucas Morales, Luke B. Hewitt, Luc Cary, Armando Solar-Lezama, Josh Tenenbaum. 2021

278 citations recorded by the source corpus.

We present a system for inductive program synthesis called DreamCoder, which inputs a corpus of synthesis problems each specified by one or a few examples, and automatically derives a library of program components and a neural search policy that can be used to efficiently solve other similar synthesis problems. The library and search policy bootstrap each other iteratively through a variant of "wake-sleep" approximate Bayesian learning. A new refactoring algorithm based on E-graph matching identifies common sub-components across synthesized programs, building a progressively deepening library of abstractions capturing the structure of the input domain. We evaluate on eight domains including classic program synthesis areas and AI tasks such as planning, inverse graphics, and equation discovery. We show that jointly learning the library and neural search policy leads to solving more problems, and solving them more quickly.

Subfields: Artificial Intelligence, Information Systems, Software, Prompting & Reasoning, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

In Software

In Prompting & Reasoning

In Reinforcement Learning

Citations in the corpus

Large Language Models Are Human-Level Prompt Engineers (2022, methodology): “Modern program synthesis admits a wide variety of specifications, including input-output examples (Ellis et al., 2021; Wong et al., 2021) and natural language (Jain et al.”
Cognitive Architectures for Language Agents (2023, methodology): “• Updating grounding (e.g., code-based skills; Liang et al., 2023a; Ellis et al., 2021; Wang et al., 2023a).”
DreamCoder: growing generalizable, interpretable knowledge with wake–sleep Bayesian program learning (2020, methodology): “Having previously presented the mechanics of the DreamCoder algorithm in an earlier paper [2], we focus here on giving a conceptual overview of the system and on its broader implications for cognitively informed AI.”
Demystifying GPT Self-Repair for Code Generation (2023, background): “Our work is also different in that we assume access to the full collection of input-output examples, as is typically done in inductive synthesis [6, 10, 12, 16, 30].”
Parsel: A Unified Natural Language Framework for Algorithmic Reasoning (2022, unknown): “This idea is embodied in DreamCoder (Ellis et al., 2021; Bowers et al., 2022).”
Neurosymbolic Program Synthesis (unknown): “Top: syntax trees of two programs sharing common structure, highlighted in orange, from which D REAM C ODER [8] can extract a reused fragment (bottom).”
Leveraging Language to Learn Program Abstractions and Search Heuristics (2021, methodology): “We initialize synthesizers with functional programming primitives (map, fold, cons, car, cdr, length, index) and character constants (following the simpler text editing domain in the baseline paper (Ellis et al., 2021)).”
Planning with Large Language Models for Code Generation (2023, methodology): “Different learning methods including learning from examples (Ellis et al., 2021) and neural-symbolic methods (Nye et al.”