Grammar Filtering for Syntax-Guided Synthesis

Kairo Morton, William T. Hallahan, Elven Shum, Ruzica Piskac, Mark Santolucito

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 GRT workflow combines criticality and time-savings predictions to produce a filtered grammar.

The system operates in four distinct stages:

  1. 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.
  2. 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.
  3. 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.
  4. 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.

Comparison of synthesis time between standalone CVC4 and the GRT+CVC4 pipeline across benchmarks.

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

Abstract

Programming-by-example (PBE) is a synthesis paradigm that allows users to generate functions by simply providing input-output examples. While a promising interaction paradigm, synthesis is still too slow for realtime interaction and more widespread adoption. Existing approaches to PBE synthesis have used automated reasoning tools, such as SMT solvers, as well as works applying machine learning techniques. At its core, the automated reasoning approach relies on highly domain specific knowledge of programming languages. On the other hand, the machine learning approaches utilize the fact that when working with program code, it is possible to generate arbitrarily large training datasets. In this work, we propose a system for using machine learning in tandem with automated reasoning techniques to solve Syntax Guided Synthesis (SyGuS) style PBE problems. By preprocessing SyGuS PBE problems with a neural network, we can use a data driven approach to reduce the size of the search space, then allow automated reasoning-based solvers to more quickly find a solution analytically. Our system is able to run atop existing SyGuS PBE synthesis tools, decreasing the runtime of the winner of the 2019 SyGuS Competition for the PBE Strings track by 47.65% to outperform all of the competing tools.
BibTeX
@inproceedings{morton2020grammar,
  author = {Kairo Morton and William T. Hallahan and Elven Shum and Ruzica Piskac and Mark Santolucito},
  title = {{Grammar Filtering for Syntax-Guided Synthesis}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i02.5522},
}
Figure