Introduction
The "holy grail" of Programming by Example (PBE) is inductive program synthesis: the ability to generate a general-purpose program from scratch using only a small set of input/output pairs. While significant progress has been made in loop-free code synthesis (e.g., bit-twiddling) and domain-specific languages (e.g., Excel's Flash Fill), synthesizing general programs with loops remains a formidable challenge.
The primary obstacle is the deceptive nature of the search space. In complex algorithmic tasks, standard search methods like hillclimbing often converge on "special-case" solutions—hacks that work for specific training inputs but fail to generalize. This paper introduces MAKESPEARE, a system designed to navigate these deceptive landscapes by identifying and utilizing "stepping stone" programs.
The MAKESPEARE Method: Delayed Acceptance
MAKESPEARE utilizes a novel search strategy called Delayed Acceptance Hillclimbing. Unlike traditional hillclimbing, which greedily accepts any modification that improves the current score, MAKESPEARE operates in distinct periods of $I$ steps to filter out deceptive local optima.
- Exploration: The system performs a random walk, accepting moves that are at least as good as the best program found in the previous period.
- Delayed Commitment: A new "best" program is not officially promoted until the end of the current period.
- The Filter: This delay forces the search to ignore small, jittery gains—such as hardcoding specific cases—and wait for structural changes that provide a significant, robust boost in correctness. This allows the search to find "stepping stones": partially correct programs that serve as foundations for the final algorithm.
Experimental Setup and Benchmarks
MAKESPEARE was evaluated across two low-level, assembly-like languages: a simplified x86-64 subset and TIS-100 (an assembly language from a popular programming puzzle game). The evaluation suite spanned several tiers of difficulty, ranging from basic array manipulations to highly algorithmic challenge problems.
Beyond the standard benchmarks shown above, the authors included "Challenge Problems" previously unsolved by pure inductive synthesis, such as Integer Sqrt, Merge, Collatz Numbers, and Fast Sort.
Key Insights: Bypassing Deception
The core advantage of Delayed Acceptance is its ability to bypass deceptive trajectories. In program synthesis, a "greedy" win often involves adding an if statement for a specific input. Delayed acceptance discourages this by requiring a leap in performance that such hacks rarely provide.
As seen in the figure above, MAKESPEARE's trajectory for the Collatz problem (b) reveals the discovery of a program that performs a simplified version of the required math, serving as a robust foundation. In contrast, basic hillclimbing (c) merely accumulates random correct points without developing a cohesive algorithmic strategy. This "stepping stone" effect is critical for generalization; the authors found that if the search identified the smallest possible program, it generalized perfectly 100% of the time across all 18 benchmarks.
Key Results and Emergent Algorithms
- Collatz Numbers: MAKESPEARE achieved the first reported success on this benchmark using pure inductive synthesis, with a 60% success rate in high-resource runs.
- Emergent Sorting: When tasked with sorting, MAKESPEARE independently "invented" Comb Sort (a variant of Shell Sort). It discovered that using a shrinking "gap" for comparisons was the most efficient way to handle large arrays within the given time bounds, generalizing to 100,000 elements despite being trained on only 20.
- TIS-100 Record: The system synthesized a 9-instruction solution for a TIS-100 puzzle, setting a new record on the community leaderboard.
Conclusion and Future Work
While MAKESPEARE demonstrates a breakthrough in synthesizing looping programs, it remains computationally intensive, with some challenge problems requiring billions of evaluations over several days. Future work will explore using machine learning to "warm start" the search or guide instruction selection, potentially reducing the stochasticity and computational cost for the most difficult algorithmic tasks.
Summary updated