Graph Program Synthesis: Adaptive Execution and Evolution for Long-Horizon Multi-Agent Systems

Large language model-based multi-agent systems increasingly address long-horizon tasks, yet most deploy workflows that remain fixed after construction. This rigidity amplifies cascading failures, redundant information flow, and inefficient resource use as tasks or environments change. We introduce Graph Program Synthesis (GPS), a program-centric framework that represents task solving as an evolving executable graph. GPS couples two capabilities: Program Graph Representation, which unifies computation units, dependencies, local state, tools, and model bindings, and Reinforcement Learning-based Adaptive Program Evolution, which formulates execution and semantic rewrites as a constrained sequential decision process. Transient executors perform bounded computation and commit validated artifacts, while a deterministic compiler activates candidate graphs only after structural, interface, state-transition, and budget checks. Across nine benchmarks spanning reasoning, code generation, multi-hop question answering, and tool use, GPS improves average task performance by 2.34 percentage points, reduces matched-performance cost by 34.8%, and raises final success under controlled runtime failures by 13.53 percentage points. These findings support a shift from static communication topologies toward adaptive executable programs for long-horizon multi-agent computation.