Toward Probabilistic Coarse-to-Fine Program Synthesis

on YouTube ↗12m

" summary

Synthesizes programs by starting with coarse probabilistic programs that use randomness as placeholders, then iteratively refines high-entropy expressions into low-entropy ones until a deterministic program or a probabilistic conditional model emerges. Implements a simply-typed lambda calculus with Y combinator and domain primitives and evaluates likelihoods via mutually recursive constrain and forward algorithms that enumerate weak-head normal forms. Works on infinite generators, constrains lists in ~3–4 ms, and yields roughly 10^2–10^4 fewer sample rollouts on benchmarks using likelihood pruning and guided search.

AI-written summary · about

" chapters (8)

1. 0:00Probabilistic program synthesis intro
2. 1:23Top-down synthesis limits
3. 2:48Pruning search inefficiencies
4. 3:08Probabilistic programs with randomness
5. 4:34Likelihood-guided efficient synthesis
6. 6:00Likelihoods with constrain and forward
7. 9:39Performance gains in likelihoods
8. 11:24Future directions and challenges