Language Model-Driven Program Synthesis with Program Trace Optimization on the Abstraction and Reasoning Corpus

Program TraceProgram TraceOptimization (PTOPTO) is a framework that provides automatic representation design for arbitrary problem structures by neatly separating problem specification from search algorithm application. Problems in PTOPTOare specified through two components: a generator that creates candidate solutions, and a fitness function that evaluates them. This framework enables any search algorithm to be applied to any problem through a universal trace representation. A key strength of PTOPTOis its ability to work with unrestricted programs as generators. While PTOPTOhas traditionally been used with simple random solution generators, we explore its application to more sophisticated generators based on language models. Using the Abstraction and ReasoningReasoningCorpus (ARC) as our case study, we show how PTOPTOcan effectively search the space of programs generated by language models trained on domain-specific languages. This demonstrates how PTOPTO’s trace-based framework can guide the search through the space of programs, while harnessing the learned patterns and structure captured by the language model. Our work exemplifies how PTOPTOcan seamlessly extend beyond conventional evolutionary computation boundaries by incorporating advanced generative methods without requiring modification.