Abstract
Program synthesis via Programming-by-Example (PBE) often faces a "search space explosion" when provided with overly broad grammars. This paper introduces GRT, a machine-learning-based preprocessor that prunes unnecessary grammar elements to accelerate synthesis. By predicting the criticality and potential time savings of grammar terminals, GRT reduces synthesis time by approximately 48% on standard benchmarks without sacrificing solution quality.
Introduction
Program synthesis aims to automatically generate code from input-output pairs. In the Syntax-Guided Synthesis (SyGuS) framework, users provide a grammar—a set of allowed functions and terminals. However, a fundamental tension exists: a grammar that is too restrictive may not contain the solution, while an overly expansive grammar leads to a "search space explosion," making it computationally infeasible for solvers to find a solution in real-time. This paper asks: Can we use data-driven methods to automatically shrink the grammar for a specific problem without losing the solution?
Methodology: The GRT Workflow
GRT acts as a modular preprocessor for existing SyGuS solvers like CVC4. Its primary goal is to produce a reduced grammar ($G^*$) that is likely to contain the solution while being much smaller than the original grammar ($G$).
The system operates in four distinct stages:
- Criticality Prediction: Using a Feedforward Neural Network (MLP) with an embedding layer, GRT analyzes input-output examples to predict which grammar terminals are essential for the solution.
- Time Savings Estimation: GRT estimates the computational cost of including specific terminals. It prioritizes removing terminals that are both unnecessary and expensive for the solver to process.
- Grammar Filtering: These metrics are combined via a voting mechanism. If multiple input-output examples are provided, each "votes" on the necessary functions to form the final reduced grammar.
- Fallback Strategy: To maintain completeness, if the solver cannot find a solution within a predicted timeframe using $G^*$, it automatically reverts to the original grammar $G$.
Experimental Evaluation
The authors evaluated GRT using the 2019 SyGuS Competition PBE Strings track, consisting of 64 benchmarks. The system was trained on a massive synthetic dataset of over 124,000 points, supplemented by human-generated constraints to reflect real-world usage patterns.
Key Results
- Significant Speedup: GRT+CVC4 reduced total synthesis time by 47.65% compared to the standalone CVC4 solver (the 2019 competition winner).
- Solving the "Unsolvable": The pipeline successfully solved a benchmark that previously timed out (3600s limit) for CVC4 alone.
- Efficiency and Low Overhead: For simpler benchmarks where CVC4 is already fast, the ML preprocessing added negligible overhead. In 32 out of 64 benchmarks, GRT+CVC4 clearly outperformed the standalone solver.
- Improved Solution Quality: By removing "distracting" complex functions, the solver often found shorter, more elegant solutions. The total node count across all synthesized programs dropped from 806 (CVC4) to 789 (GRT+CVC4).
Discussion and Future Work
GRT demonstrates that machine learning can effectively serve as a "scout" for symbolic solvers, cleaning the search space rather than attempting to solve the logic directly. This hybrid approach leverages the strengths of both statistical prediction and formal verification.
Current limitations include domain specificity; the current model is optimized for string manipulations. Future work aims to extend this to other domains like BitVectors and to implement more sophisticated neural architectures that can model the inter-constraint logic between multiple input-output pairs more effectively.
Summary updated