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 (≥ 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.
Introduction
In Programming by Example (PBE), a user provides a few input-output pairs (e.g., "John Doe" → "J.D."), and a synthesizer generates a program that matches them. The ultimate goal is generalization: the program should work correctly on all future inputs, not just the ones provided. However, most current synthesizers are "greedy," stopping as soon as they find any program that fits the initial 2–4 examples. This often leads to overfitting, where the synthesizer selects a program that is syntactically simple but logically incorrect for the broader task. SynGuar is the first framework for PBE that provides formal guarantees on how well a synthesized program will generalize to unseen data by leveraging PAC (Probably Approximately Correct) learning theory.
Methods
SynGuar is a meta-framework that can be wrapped around existing PBE engines like PROSE or STUN. Its core innovation is the use of sample complexity to dynamically calculate exactly how many input-output examples are needed to ensure the final program is "close" to the target behavior with high probability.
The framework follows a two-phase synthesis approach:
- Sampling Phase: SynGuar tracks the size of the "consistent hypothesis space"—the set of all possible programs in the language that still match the seen examples—and queries the user for examples to shrink this space.
- Validation Phase: Once the space is sufficiently small, it uses a PAC bound (proportional to the natural log of the hypothesis space size) to calculate the final number of examples required to reach the theoretical guarantee.
Key Insights and Results
A critical observation in this research is the dramatic rate at which the program space shrinks with the first few examples. As shown in the table below, 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 rigorous sampling.
Empirical Performance
The authors evaluated SynGuar on string-transformation tasks from the PROSE-benchmark and the SyGuS 2019 competition. Key findings include:
- Accuracy Boost: SynGuar-PROSE achieved 93.95% accuracy. It improved correct program generation from 0/16 to 14/16 on the PROSE benchmark and from 36/59 to 53/59 on SyGuS compared to vanilla synthesizers.
- 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.
- Complexity Scaling: The number of examples required is not fixed; it correctly scales with the complexity of the target program (e.g., those with many conditional branches).
Limitations and Future Work
While SynGuar provides a mathematical floor for reliability, it introduces an "oracle burden," requiring hundreds of examples that may be difficult for a human to provide manually. Future work could involve active learning to specifically ask for examples that shrink the hypothesis space the fastest. Additionally, computing the size of the hypothesis space for more complex, recursive, or infinite Domain Specific Languages (DSLs) remains a significant technical challenge. Finally, the PAC guarantees assume that training examples are drawn from the same distribution that the program will face in deployment.
Summary updated