Top-Down Synthesis for Library Learning
summary
Paper introduces corpus-guided top-down synthesis that builds abstractions by expanding holes and using branch-and-bound pruning with quick upper bounds; utility is roughly size×matches so search balances specificity vs. coverage. Implementation called Stitch (Rust core, pip-installable Python bindings) synthesizes libraries 1,000–10,000× faster and uses ~100× less memory than DreamCoder, yields comparable-or-better compressivity, scales to hundreds of complex programs, and finds near-optimal abstractions with early stopping.
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:20Basic program synthesis Given a library of primitives (DSL), the synthesizer assembles the primitives into a program that meets a spec
- 1:01Prior Work: DreamCoder Algorithm
- 3:43DreamCoder: Results (Prior Work)
- 4:24Related Work
- 5:10Abstraction Learning in DreamCoder
- 6:06Outline of this talk
- 7:39Top-down Search
- 10:52Upper bound
- 12:31More pruning!
- 13:58Performance vs. DreamCoder
- 14:55Scaling to More Complex Datasets
- 15:30Anytime algorithm
- 16:17Utility vs. DreamCoder
- 16:53Python Library (Rust Backend)
- 17:42Conclusion
- 19:20What is a good abstraction?
related talks
16mDigging for Fold: Synthesis-Aided API Discovery for Haskell
17mAccelerating Syntax-Guided Program Synthesis by Optimizing Domain-Specific Languages
28mScooPy: Enhancing Program Synthesis with Nested Example Specifications
13mProgramming with a Read-Eval-Synth Loop
20mTerm Search in Rust
20mAutomating the Design Recipe
20mEquivalence by Canonicalization for Synthesis-Backed Refactoring
14mLooPy: Interactive Program Synthesis with Control Structures