Tunneling Through the Hill: Multi-Way Intersection for Version-Space Algebras in(…)
summary
Claims a new multi-way intersection algorithm that directly intersects many small VSAs to avoid huge intermediate structures, plus a bottom-up intersection procedure that prunes empty nodes. Integrates into a general VSA synthesizer and the string solver Blaze, evaluates 994 PBE tasks across four datasets, and reports up to 105 more tasks solved and a 7.36× speedup. Uses adaptive grouping to limit multi-way fan-in and provides theoretical guarantees for associative/commutative operators.
AI-written summary · about
chapters (13)
- 0:00VSA-based program synthesis
- 1:29How VSA synthesis works
- 2:54Inefficiency of iterative VSA intersection
- 3:58Optimizations for VSA intersection
- 5:01Top-down vs bottom-up intersection
- 6:55Advantages of bottom-up intersection
- 7:15Multi-way intersection with grouping
- 8:44Heuristic to avoid hill peak
- 9:27Theoretical properties of algorithm
- 10:09Evaluation on circuit dataset
- 11:33Integration with VSA solvers
- 11:54Summary of approach
- 12:16Q&A: VSA and grammars
related talks
21mVerMCTS: Synthesizing Multi-Step Programs using a Verifier, a Large Language Model,(…)
01h 04mInvited Talk: Finding Good Programs by Avoiding Bad Ones
29mSynthesis of dependable and self-driving communication networks
01h 03mImproved Assistance for Interactive Proof
15mUnconference: Explainable Vector Search
41m"Do What I Mean": The History of AI and Program Synthesis
15mToward Neural-Network-Guided Program Synthesis and Verification
18mGraphScape: A Model for Automated Reasoning about Visualization Similarity and Sequencing