Meta-Harness Adaptation for Evolving Fast Graph Algorithms

AlphaEvolve combines large language models, evolutionary search, and automated evaluation to improve programs, demonstrating successes in algorithm discovery and computational optimization. Recent work has shown that the prompts and search policies governing such systems can themselves be adapted. We investigate this direction as meta-harness adaptation, asking: Which forms of adaptation help AlphaEvolve-style code evolution improve implementations of the most fundamental algorithmic tasks? We study and compare four strategies for adapting the instructions that guide LLM-based code evolution: meta-coaching, bandit-based instruction selection, prompt evolution, and prompt tournaments. We evaluate them on three foundational textbook problems: maximum flow, single-source shortest paths with negative edge weights, and maximum-cardinality matching in general graphs. In most experiments, each problem class admits a meta-controller that clearly improves the best observed performance over non-adaptive code evolution. On the prepared benchmark suites, the best evolved programs achieve geometric-mean runtime speedups of $9.75\times$ over the official Hochbaum pseudoflow implementation for maximum flow, $4.26\times$ over the official Goldberg--Radzik implementation for shortest paths, and $1.16\times$ over our adapted implementation of the revised Gabow algorithm for matching. These results suggest that adapting search instructions can improve the performance of programs produced by LLM-based evolution.