Research map / Probabilistic and scientific modeling / Molecules and proteins
Bayesian Program Learning by Decompiling Amortized Knowledge
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes dream decompiling, which uses DreamCoder's learned recognition model to choose which functions to chunk into the library, so the same amortized knowledge reduces both search breadth and depth.
Problem
Library learning in DreamCoder-style program synthesis chooses chunks only from compression of discovered solutions, ignoring how the learned recognition (search) model will use them, so breadth and depth search knowledge are not coupled.
Approach
Use the recognition model's amortized probabilities to rank and select functions for chunking, via two variants: DreamDecompiler-Avg (expected generation probability) and DreamDecompiler-PC (probabilistic chunking based on a caching-benefit measure based on log-probability ratios), replacing compression-based selection.
Key results
- DDC-PC outperforms DreamCoder by 13.25% average test task performance in list processing at peak difference and by over 17% in the remaining domains (excluding text editing).
- Welch's t-test shows statistical significance of improved mid-cycle performance (cycle 3: t=2.57, p=0.016; cycle 4: t=2.1, p=0.045).
- Functions chunked early by dream decompiling variants are eventually used to solve more test tasks across domains.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use probabilistic dream decompiling to select library chunks instead of DreamCoder's compression-based selection | DreamCoder · List processing | average test task performance: 13.25% | Helped |
| Use probabilistic dream decompiling to select library chunks instead of DreamCoder's compression-based selection | DreamCoder · Block towers | average test task performance: over 17% | Helped |
| Use probabilistic dream decompiling to select library chunks instead of DreamCoder's compression-based selection | DreamCoder · Symbolic regression | average test task performance: over 17% | Helped |
| Use probabilistic dream decompiling to select library chunks instead of DreamCoder's compression-based selection | DreamCoder · LOGO graphics | average test task performance: over 17% | Helped |
| Use dream decompiling for chunk selection | DreamCoder · Text editing | test task performance | No clear effect |
| Use probabilistic chunk selection (DDC-PC) rather than average-probability ranking (DDC-Avg) | DreamCoder · Deterministic program domains | test performance | Helped |
| Use dream decompiling to select early chunks | DreamCoder · All evaluated domains | percentage of test tasks eventually solved using early chunked functions | Helped |
Surprising findings
- Text editing showed comparable performance across all systems, so dream decompiling gave no gain there.
- Dream decompiling variants reached similar training task solve counts as DreamCoder, yet generalized better to held-out tasks.
Limitations
- Chunking uses a simple fixed top-k rule (k=1 or 2), without a principled way to choose the number of functions to chunk.
- Candidate generation still relies on compression-based DreamCoder candidates; functions absent from existing solutions are not generated.
- Payoff symmetry assumed in the decision threshold of 0.5; the approximation of caching benefit is heuristic.
Experimental setup
Datasets: list processing tasks SyGuS text editing tasks block tower tasks symbolic regression functions LOGO graphics tasks regex tasks
Benchmarks: list processing text editing block towers symbolic regression LOGO graphics regexes
Metrics: percentage of test tasks solved average search time percentage of test tasks solved by top chunked functions
Baselines: DreamCoder
Builds on: DreamCoder wake-sleep algorithm Stitch babble
Closest papers by meaning
- From Perception to Programs: Regularize, Overparameterize, and Amortize (ICML 2023 · similarity 0.88)
- Leveraging Language to Learn Program Abstractions and Search Heuristics (ICML 2021 · similarity 0.88)
- CrossBeam: Learning to Search in Bottom-Up Program Synthesis (ICLR 2022 · similarity 0.87)
- HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis (NeurIPS 2024 · similarity 0.84)
- Solver-Aware Decompositions for Programming-by-Example: When Dividing Requires Knowing how to Conquer (NeurIPS 2026 · similarity 0.84)
- Large Language Models to Enhance Bayesian Optimization (ICLR 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.