Sequential Monte Carlo Program Synthesis with Refinement Proposals
summary
Extends program synthesis search to include probabilistic programs and evaluates exact marginal likelihood using the PL change named pluck via lazy knowledge compilation; builds an SMC algorithm that performs coarse-to-fine refinements by repeatedly replacing random primitives in particles with more deterministic code; compares against subtree-resampling MCMC and an edit-distance smoothed likelihood baseline and reports about 6× faster wall-clock convergence on list-manipulation benchmarks while increasing solved-task counts per inference steps.
AI-written summary · about
chapters (10)
- 0:00Program synthesis basics
- 2:13Bayesian program synthesis
- 3:39MCMC limitations
- 5:03Extending hypothesis space
- 7:32Acceptance probability challenges
- 8:16Pluck language for inference
- 8:59Empirical results
- 9:42Synthesis breakthroughs
- 11:05Refinement-based SMC algorithm
- 12:31Q&A
related talks
22mStochastic Lazy Knowledge Compilation for Inference in Discrete Probabilistic Programs
11mEffective Sequential Monte Carlo for Language Model Probabilistic Programs
20mProbabilistic Programming with Stochastic Probabilities
31mProbabilistic Programming: The What, Why and How
17mModeling Black-Box Components with Probabilistic Synthesis
19mIncremental Computation for Efficient Programmable Inference in Probabilistic Programs
29mMotivating Probabilistic Programming
32mMonte Carlo Sampling Approach to Solving Stochastic Multistage Programs