Tunneling Through the Hill - Multi-Way Intersection for Version-Space Algebras in Program Synthesis

Explore a 14-minute conference presentation from OOPSLA 2025 that introduces a novel multi-way intersection approach for optimizing Version Space Algebras (VSA) in program synthesis. Learn how researchers from Peking University address the critical inefficiency problem in VSA-based synthesizers when processing multiple input-output examples, where traditional iterative intersection methods create exponentially growing intermediate VSAs that become computational bottlenecks. Discover the key insight that while intermediate VSAs can become enormous during processing, the final result typically remains small since only a few programs satisfy all examples, and understand how this observation led to developing a direct multi-way intersection algorithm that bypasses the construction of huge intermediate structures. Examine the technical details of the new intersection algorithm designed to avoid unnecessary VSA nodes and see how this approach was successfully integrated into two state-of-the-art VSA-based synthesizers: a general VSA synthesizer and Blaze, a specialized string domain synthesizer. Review comprehensive evaluation results across 4 datasets containing 994 synthesis tasks that demonstrate significant performance improvements, including solving up to 105 additional tasks and achieving speedups of up to 7.36 times compared to existing methods.