Inductive Program Synthesis Guided by Observational Program Similarity

on YouTube ↗18m

" summary

Introduces SyMetric, a tool that replaces observational equivalence with a domain-specific observational similarity metric to cluster programs into bounded-radius version spaces and then applies repair via distance-guided rewrites (hill-climbing over rewrite rules) to turn “close but wrong” representatives into exact solutions. Implements bottom-up enumeration with clustering, ranking, extraction, and incremental repair. Evaluated on inverse CSG (25 random + 22 handwritten benchmarks), regex inference, and a tower-building task; outperforms domain‑agnostic equivalence-based syntheses and matches or nears domain-specific baselines. metric program synthesis

AI-written summary · about

" chapters (12)

1. 0:00Inductive program synthesis intro
2. 1:05Bottom-up synthesis recap
3. 2:51Limitations of equivalence
4. 3:53Extending to observational similarity
5. 5:39Algorithm overview
6. 7:25Parameterizing algorithm
7. 8:27Inverse CSG results
8. 9:31Results in regular expression domain
9. 10:35Tower building results
10. 11:17Ablation study
11. 12:18Conclusion and future work
12. 13:20Q&A