DreamCoder's Wake-Sleep Library Learning - Kevin Ellis

Kevin Ellis, Assistant Professor at Cornell University, discusses his influential paper “DreamCoder,” which presents a system that jointly learns reusable program abstractions and a neural search strategy through an iterative wake-sleep process.

The work emerged from early efforts in library learning and a broader question about how humans accumulate concepts over time. Ellis reflects on the challenge of searching vast program spaces and how inspiration from cognitive processes, particularly dreaming and replay, led to a system that incrementally builds knowledge by reusing prior solutions.

In This Episode -

• Program synthesis beyond formal specifications

• Natural language as executable programs

• Library learning for compositional reuse

• Wake-sleep cycles for program learning

• Neural-guided search over program space

• E-graph refactoring for abstraction discovery

• Emergence of map and fold primitives

• Probabilistic programs for uncertainty

• World models beyond frame prediction

• Program synthesis benchmarks

References -

• ARC-AGI-3: https://arcprize.org/arc-agi/3

• ExoPredicator: https://arxiv.org/abs/2509.26255

• AutumnBench: https://www.basis.ai/blog/autumn-platform-2025/

About the Paper -

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

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

PLDI 2021 (ACM SIGPLAN Conference on Programming Language Design and Implementation)

DreamCoder is a program synthesis system that learns both a library of reusable program components and a neural search policy by iteratively solving tasks and compressing solutions into abstractions. It alternates between solving problems (wake phase) and improving its internal representations via abstraction and dreaming phases, enabling more efficient search and generalization across domains.

https://dl.acm.org/doi/10.1145/3453483.3454080

About the Guest -

Kevin Ellis is an Assistant Professor at Cornell University working on program synthesis, neurosymbolic AI, and computational models of cognition. His research focuses on learning structured representations such as programs that capture compositional knowledge about the world.

https://www.cs.cornell.edu/~ellisk/

Credits -

• Host & Music: Bryan Landers, Technical Staff, Ndea

• Editor: Alejandro Ramirez

• https://x.com/ndea

• https://x.com/bryanlanders

• https://ndea.com