ReDS: Reactive DSL Synthesis with Large Language Models for Programming by Example

Genetic programming (GP) is common method to search for programs, but its hypothesis space is defined by the underlying domain-specific language (DSL). Large language models (LLMs) can generate programs directly but are largely ineffective at PBE from input-output examples alone. We introduce ReDS (Reactive DSL Synthesis), a hybrid system that combines genetic programming (GP) with a large language model (LLM) to expand the DSL during search. When evolution stagnates, an LLM proposes new primitives in order to modify the hypothesis space during search, and builds a library of reusable primitives at the same time. On three programming-by-example benchmarks, ReDS reaches 61.2% on Lists, 73.0% on 1D-ARC, and 38.3% on PBEBench cascade-2, outperforming GP-only search (40.1%, 25.6%, and 1.7%), token-matched LLM baselines on 1D-ARC and PBEBench, and DreamCoder on 1D-ARC (46.7%). Ablations show that primitive expansion, rather than LLM program injection, is the dominant mechanism, suggesting that many PBE failures are representation failures that reactive DSL expansion can fix.