Semantic Mutation via LLMs: A Hybrid Approach to Evolutionary Program Synthesis
TL;DR
This work proposes a hybrid framework that integrates Large Language Models into GP in two complementary roles: as a semantic mutation operator that proposes non-local program rewrites during evolution, and as a post-evolution repair that iteratively refines single failed programs after search terminates.
Abstract
Program synthesis over combinatorial Domain-Specific Language (DSL) spaces is challenging because the search space is vast and small program edits rarely produce meaningful semantic changes. Genetic Programming (GP) offers an interpretable framework for this kind of task, but its mutation operators make purely structural changes without understanding task semantics, causing it to frequently stall in local optima. To mitigate this, we propose a hybrid framework that integrates Large Language Models (LLMs) into GP in two complementary roles: as a semantic mutation operator that proposes non-local program rewrites during evolution, and as a post-evolution repair that iteratively refines single failed programs after search terminates. All LLM outputs are treated as untrusted and filtered through grammar constraints and typed parsing before entering the population. Evaluated on the Abstraction and Reasoning Corpus (ARC-AGI-1), our framework solves 85 out of 400 tasks, raising pixel accuracy from 54% to 74%.