How Much Is the Search and How Much Is the Bias? Hand-Designed Generators in Non-Learning Program Synthesis

We ask how much of the success of a program-synthesis search without machine learning is attributable to the search procedure itself and how much to hand-designed generators. Using the seven integer problems of the PSB2 benchmark, we find that nearly all measured success comes from the generators. Our system performs beam search over syntax trees in a small imperative language, selecting candidate programs according to the exact number of training cases solved. With six generator components designed after examining failures on these same problems, the system solves 595 of 700 runs (100 independent seeds per problem, with a 900-second budget and 2,000 unseen test cases per run), compared with 113 runs when these components are disabled. Leave-one-component-out experiments show that five of the six components are critical to their respective problems, while one is redundant for Paired Digits. A control that retains the generators but removes selection feedback shows no measurable advantage for beam search over random sampling on these problems: random search solves 187 of 210 runs, compared with 183 for beam search. Thus, directly sampling from the generators is sufficient for the observed results, and selection provides no measurable benefit under this experimental setup. The generators do not extend the system's reach: across 17 additional problems, we detect no effect from them. On a held-out set frozen before implementation—PSB2 Square Digits, Bowling, Camel Case, and PSB1 Median, evaluated with 30 seeds—the components also make no measurable difference, although all four problems are at either the floor or ceiling of performance. Median provides a contrasting case in which search matters: without applicable generator components, random search solves none of 30 runs, whereas beam search solves all 30. These results show that, on the benchmark problems where the components were developed, hand-designed generators account for most of the system's success, while the contribution of search depends on the problem.