Gauss: Program Synthesis by Reasoning Over Graphs
summary
Gauss synthesizes table-transformation programs (Pandas and R) from partial outputs plus user intent graphs that record cell/row/column relations (example: selecting four cells and pasting their mean). It builds a graph abstraction of candidate programs and uses a novel conflict graph reasoning to prune infeasible skeletons and learn from failed enumerations. Evaluation shows average search-space reductions of 56×, 73×, 664× and speedups of 7×, 26×, 7× versus three state-of-the-art tools.
AI-written summary · about
chapters (14)
- 0:00Gauss: Program Synthesis by Reasoning over Graphs
- 0:35Input-Output Examples as the Synthesis Specification
- 1:23Input-Output Examples are Problematic for Table Transformations
- 2:27Gauss Uses a Dedicated UI to Capture Interaction
- 3:42Gauss Accepts Partial Outputs
- 4:17The Graph-Based Synthesis Specification
- 6:06Recapping the Motivating Example...
- 6:24Gauss Uses Two-Tiered Enumerative Search
- 7:18Eliminate Infeasible Skeletons using Unit Queries
- 8:27Enumerate Progs and Learn from Failures
- 10:29Return Programs Satisfying the Spec
- 10:42Main Research Questions - 1
- 12:39Main Research Questions - 2
- 13:21Can User Intent Graphs Reduce the Size of Output Specifications?
related talks
38mProgram Synthesis: A Dream Realized?
47mBig Ideas in Program Synthesis
25mInductive Synthesis of Structurally Recursive Functional Programs from Non-recur...
17mAlgebro-geometric Algorithms for Template-Based Synthesis of Polynomial Program...
01h 10mNeurosymbolic Program Synthesis: Bridging Perception and Reasoning in Real-World(…)
15mPL4XGL: A Programming Language Approach to Explainable Graph Learning
28mAutomated transpilation of imperative to functional code using neural-guided program synthe
16mJust-in-Time Learning for Bottom-Up Enumerative Synthesis