SynGuar: guaranteeing generalization in programming by example

Bo Wang, Teodora Baluta, Aashish Kolluri, Prateek Saxena

TL;DR

SynGuar is the first framework for Programming by Example (PBE) that provides formal guarantees on how well a synthesized program will generalize to unseen data. By leveraging PAC (Probably Approximately Correct) learning theory, it dynamically calculates exactly how many input-output examples are needed to ensure the final program is "close" to the target behavior with high probability.

What Problem Does This Paper Address?

In Programming by Example (PBE), a user provides a few input-output pairs (e.g., "John Doe" $\rightarrow$ "J.D."), and a synthesizer generates a program that matches them. The "holy grail" is generalization: the program should work correctly on all future inputs, not just the ones the user provided.

The challenge is that most current synthesizers are "greedy"—they stop as soon as they find any program that fits the 2–4 examples provided. This often leads to overfitting, where the synthesizer picks a program that is syntactically simple but logically incorrect for the broader task. Until now, there has been no principled way to determine how many examples are "enough" to guarantee that a synthesizer won't overfit.

Methods

The authors introduce SynGuar, a meta-framework that can be wrapped around existing PBE engines. Its core innovation is the use of Sample Complexity from PAC learning theory.

  1. Dynamic Hypothesis Space Tracking: SynGuar doesn't just look for one program; it tracks the size of the "consistent hypothesis space"—the set of all possible programs in the language that still match the seen examples.
  2. The PAC Bound: It uses a classical theorem (Blumer et al.) which states that the number of samples $m$ needed to bound error $\epsilon$ with confidence $1-\delta$ is proportional to the natural log of the hypothesis space size ($m > \frac{1}{\epsilon}(\ln |H| + \ln \frac{1}{\delta})$).
  3. Two-Phase Synthesis:
    • Sampling Phase: SynGuar asks for examples to shrink the hypothesis space as much as possible.
  4. Validation Phase: Once the space is small enough, it calculates a final "safety" number of examples to reach the theoretical guarantee.
  5. Retrofitting: The authors demonstrate how to implement this in two major synthesis architectures: PROSE (which uses Version Space Algebra to represent sets of programs) and STUN (which uses bottom-up search and unification).

Datasets

The authors evaluated SynGuar on two primary benchmarks:

  • PROSE-benchmark: 16 manually designed string-transformation tasks (like date formatting or name abbreviation) similar to those used in Microsoft Excel's FlashFill.
  • SyGuS-STUN: 59 tasks derived from the SyGuS 2019 competition (PBE-Strings track), which is the standard industry benchmark for program synthesis.

Key Insights and Ideas

  • The "Aha" Moment on Shrinkage: The authors found that the program space shrinks drastically with the first few examples. For one task, the space dropped from $10^{42}$ possible programs to just 18 programs after only 12 examples. This explains why PBE works at all, but also why the "last mile" of generalization requires more samples.
  • Complexity Costs Samples: The number of examples required is not fixed; it depends on the complexity of the target program. If you need a program with many if-then-else branches, SynGuar correctly identifies that you need significantly more examples to be sure you haven't picked a "fake" solution.
  • Provable vs. Ad-hoc: While "vanilla" synthesizers often fail or overfit when given only 4 examples, SynGuar's requirement of ~200–400 examples (for string tasks) provides a rigorous mathematical floor for reliability.

Key Results

  • Accuracy Boost: SynGuar-PROSE achieved 93.95% accuracy across all runs, compared to the vanilla version which frequently overfitted and failed when using a small, fixed number of examples.
  • Sample Efficiency: To guarantee a generalization error below 5% with 98% confidence, SynGuar required an average of 197 examples for PROSE tasks and 357 examples for STUN tasks.
  • Overfitting Confirmation: The study confirmed that existing synthesizers using only 2–4 examples (a common practice) produced the correct program in only 0/16 cases for the PROSE benchmark and 36/59 for SyGuS. SynGuar improved these to 14/16 and 53/59, respectively.

Limitations and Future Work

  • The Oracle Burden: SynGuar requires hundreds of examples to provide its guarantees. While a "black-box fuzzer" can generate these for some tasks, it might be too demanding for a human user to provide that many examples manually.
  • DSL Constraints: The current implementation is optimized for string manipulation. Computing the size of the hypothesis space ($|H|$) for more complex, recursive, or infinite Domain Specific Languages (DSLs) remains a significant technical challenge.
  • Distribution Assumptions: The PAC guarantees assume that examples are drawn from the same distribution (i.i.d.) that the program will face in the wild. If the "training" examples are biased, the guarantees may not hold.

The authors suggest that future work could involve "active learning," where the synthesizer doesn't just ask for any example, but specifically asks for examples that shrink the hypothesis space the fastest.

Summary updated

Abstract

Programming by Example (PBE) is a program synthesis paradigm in which the synthesizer creates a program that matches a set of given examples. In many applications of such synthesis (e.g., program repair or reverse engineering), we are to reconstruct a program that is close to a specific target program, not merely to produce some program that satisfies the seen examples. In such settings, we wish that the synthesized program generalizes well, i.e., has as few errors as possible on the unobserved examples capturing the target function behavior. In this paper, we propose the first framework (called SynGuar) for PBE synthesizers that guarantees to achieve low generalization error with high probability. Our main contribution is a procedure to dynamically calculate how many additional examples suffice to theoretically guarantee generalization. We show how our techniques can be used in 2 well-known synthesis approaches: PROSE and STUN (synthesis through unification), for common string-manipulation program benchmarks. We find that often a few hundred examples suffice to provably bound generalization error below $5\%$ with high ($\geq 98\%$) probability on these benchmarks. Further, we confirm this empirically: SynGuar significantly improves the accuracy of existing synthesizers in generating the right target programs. But with fewer examples chosen arbitrarily, the same baseline synthesizers (without SynGuar) overfit and lose accuracy.
BibTeX
@inproceedings{wang2021synguar,
  author = {Bo Wang and Teodora Baluta and Aashish Kolluri and Prateek Saxena},
  title = {{SynGuar: guaranteeing generalization in programming by example}},
  booktitle = {ESEC/SIGSOFT FSE},
  year = {2021},
  url = {https://openreview.net/forum?id=M-zHTa44fW},
}

Loading related content...

Figure