Anytime Program Synthesis for the BEN ARC Solver

Abstract

Program synthesis for the Abstraction and Reasoning Corpus (ARC) remains challenging due to large search spaces, limited computational budgets, and the propagation of early synthesis decisions throughout the solver pipeline. This paper investigates whether internal solver metrics can guide retriggerable transformation search within the BEN Divide, Align, and Conquer (DA&C) architecture.To address this question, we introduce an anytime transformation-refinement mechanism that resumes synthesis from previously explored search frontiers, along with a threshold-based retriggering strategy driven by transformation overfitting and solver-state metrics. The proposed approach was implemented in a Julia-based reimplementation of BEN using the Herb.jl program synthesis framework and evaluated on the ARC benchmark.The experimental results show that retriggerable synthesis substantially changes the distribution of search effort across correspondences, enabling deeper exploration of highly ranked alignments while preserving exploration of lower-ranked alternatives. Compared to the baseline solver, the proposed method explores significantly fewer candidate transformations. It produces a different set of solved tasks, demonstrating that it redirects synthesis toward different regions of the search space. However, these changes do not translate into a large improvement in overall ARC solve rate, with both approaches achieving comparable aggregate performance.These findings suggest that transformation synthesis is not the primary bottleneck in the current BEN architecture. Instead, overall performance appears to be constrained by earlier stages of the pipeline, including segmentation, correspondence generation, and the expressiveness of the transformation language. While retriggerable anytime synthesis does not increase aggregate benchmark runtime performance, it provides a structured mechanism for adaptive search control. It lays the foundation for future work on stateful, dynamically allocated program synthesis.