DreamCoder grows its own library of code by compressing solved programs into reusable routines, so later search runs over a richer vocabulary than it started with.
lane: substrate · arXiv:2006.08381 (DreamCoder) — PLDI 2021, Ellis, Wong, Nye, Sablé-Meyer, Morales, Hewitt, Cary, Solar-Lezama, Tenenbaum (MIT); ancestor: Lake, Salakhutdinov, Tenenbaum, "Human-level concept learning through probabilistic program induction," Science 350(6266):1332-1338, 2015, DOI 10.1126/science.aab3050; descendant: LILO — arXiv:2310.19791, Grand, Wong, Bowers, Olausson, Liu, Tenenbaum, Andreas, ICLR 2024
Gives. Solved programs are refactored into new primitives; the next search runs over a shorter vocabulary.
Needs. Crisp, verifiable tasks and a hand-picked primitive set.
Breaks. Toy domains; LILO beat it by putting an LLM in the loop.
DreamCoder bets that search should learn its own vocabulary, not just a policy over a fixed one. DreamCoder refactors every solved task each cycle and compresses shared sub-patterns into new library primitives, so its DSL grows new functions over time. A neural recognition model then learns to predict which primitives are likely useful for a new task. This is the orthogonal piece against every LLM-code-search system on this hub. An LLM's library is an implicit, frozen prior over pretrained tokens. DreamCoder's library is explicit, inspectable Lisp-like code that grows during the run and is specific to the problem domain it has seen.
The loop has three phases per cycle (arXiv:2006.08381, full text via arxiv.org/html/2006.08381): 1. Wake: DreamCoder enumerates candidate programs for each training task in decreasing order of probability under the current neural recognition model, and keeps a beam of k=5 solved programs per task. 2. Abstraction sleep: DreamCoder takes the programs solved during wake, refactors them using version spaces and equivalence graphs with a bounded evaluation-step depth of 3 to expose reused sub-expressions, and adds the sub-expressions that most compress the corpus as new named library routines. This step is the symbolic library learning that grows the DSL. 3. Dreaming sleep: DreamCoder retrains the neural recognition model on a 50/50 mix of replayed real solutions and fantasies, programs sampled from the current library and interpreted to produce synthetic task-solution pairs, via a MAP objective. This lets the network learn to guide search even over new library primitives it has never seen solve a real task.
JUDGE is task-specific unit-test-style correctness: the program, when run, must match the input/output or image/behavior the task specifies. KEPT is the compressed library itself, plus one solution program per solved task, both carried into the next wake phase.
Nothing here is a continuous fit against a numeric residual in the SciPy/BFGS sense used elsewhere on this hub. Gradient ascent on a MAP objective over sampled program traces during dreaming sleep trains only the neural recognition model's weights. Program structure itself is entirely discrete: enumerative search chooses it during wake, and version-space compression chooses it during abstraction sleep. Both decide which primitives exist and which one solves a given task. The signal crossing between the discrete library and the continuous recognition network is not a scalar score or residual vector. It is the stream of solved and fantasied programs themselves.
DreamCoder targets domains with crisp, verifiable symbolic specifications: functional list operations, text editing, LOGO turtle graphics, physical laws as symbolic identities. In these domains a program is either right or wrong, and reuse across tasks is high. The paper states directly that search cost without the learned library is intractable: the sort-list solution would require over 10^72 years of brute-force search absent the learned library (arXiv:2006.08381, full text). Even with learning, building the origami and Lisp-primitive library took roughly a year of total CPU time. Typical per-domain training runs about a day on 20 to 100 CPUs, and the authors gave enumeration baselines a 24-hour-per-task budget for comparison. The authors state directly that the approach presumes hand-supplied starting primitives, such as functional basics, control flow, or Lisp primitives, rather than a blank slate. They also state that handling pervasive noise and messier real-world data, as opposed to crisp symbolic tasks, remains unaddressed.
Per-domain results from the full text (arxiv.org/html/2006.08381):
LILO (arXiv:2310.19791, ICLR 2024) is the direct descendant that swaps enumerative wake-search for an LLM synthesizer while keeping Stitch-based compression. On offline solve-rate-gain-over-initial-library experiments, DreamCoder's final library improved over its initial library by +19.6 percentage points (REGEX), +62.46 (CLEVR), +29.73 (LOGO); LILO's gains exceeded DreamCoder's in every domain tested, at +42.27 (REGEX), +63.43 (CLEVR), +43.24 (LOGO). These numbers come from a WebSearch synthesis of the arXiv HTML; the table itself was not independently re-opened this session. LILO's own cost estimate: one round of LLM synthesis costs roughly the same compute budget as 48 CPU-hours of DreamCoder's enumerative search.
1. LILO beats DreamCoder head-to-head: LILO's authors frame DreamCoder's enumerative wake phase as the bottleneck worth replacing with an LLM. LILO beat DreamCoder in every one of three re-run domains, REGEX, CLEVR, and LOGO — the clearest evidence that LLM-guided search outperforms DreamCoder's original search inside the same wake-sleep skeleton. 2. Search cost is combinatorial without the library: the paper's own 10^72-year figure for unaided brute-force search on list-sort is the sharpest stated limitation. The whole design exists because naive enumeration does not scale. 3. DSL and primitive dependence: DreamCoder starts from a hand-chosen primitive set per domain and does not learn primitives from nothing. The authors frame this as a deliberate scope choice. 4. Toy-domain scope: list processing, text editing, LOGO graphics, towers, and closed-form physics are domains chosen because they admit exact verification. The authors flag extending the approach to noisy real-world data as unaddressed future work. 5. LLM search is differently expensive, not simply cheaper: LILO's own estimate puts 48 CPU-hours of DreamCoder search at roughly one LLM synthesis round. This reframes the trade as a substitution between compute types, not a clean win.
No source found claims that LLM codegen has made DreamCoder wholly obsolete. The strongest statement found, LILO's own framing, calls LLM-based and enumerative-compression search "not mutually exclusive" — a case for hybridization rather than replacement.
DreamCoder frames itself as Bayesian program induction, building on Bayesian multitask program learning (Dechter et al., Lake et al., Liang et al.). It shares that lineage with Lake, Salakhutdinov, and Tenenbaum's 2015 Bayesian Program Learning, BPL. BPL represented handwritten-character concepts as short stochastic programs over strokes, parts, and subparts, and reached human-level one-shot classification on a 1,623-character, 50-writing-system dataset, beating contemporary deep-learning baselines, Science 350(6266):1332-1338. That result came via WebSearch; the primary PDF at cims.nyu.edu returned 403 and was not opened directly. BPL supplied the framing: represent concepts as programs, then fit a Bayesian posterior. DreamCoder's addition is learning the DSL and library itself, rather than treating the program space as fixed, plus a neural recognition model for amortized search guidance. LILO, 2024, is the direct successor. It keeps Stitch-style compression but replaces wake-phase enumerative search with LLM-guided synthesis. It also adds an AutoDoc step that names and documents each learned abstraction in natural language.
Verified: WebFetch on arxiv.org/abs/2006.08381 (abstract only) and arxiv.org/html/2006.08381 (full text, mechanism/results/limits sections); WebFetch on arxiv.org/abs/2310.19791 (abstract only, full text blocked from direct extraction, numbers recovered via WebSearch synthesis of the same arXiv HTML); WebSearch for Lake et al. 2015 bibliographic/method facts (cims.nyu.edu and cbmm.mit.edu PDFs returned 403/blocked, not opened directly); WebSearch for LILO numeric tables and DreamCoder critique/cost discussion. · code: https://github.com/ellisk42/ec (DreamCoder, named in multiple secondary sources, not independently opened this session); https://github.com/gabegrand/lilo (LILO)