Language-model systems that write algorithms now improve programs by repeated trial. They propose a heuristic for vehicle routing or scheduling, run it, read the result, and propose a better one. The strongest of these systems keep candidates in a tree of program versions rather than a flat pool. Their bottleneck is evaluation: every candidate is run on the full, expensive problem set. The usual remedy from hyperparameter tuning is multi-fidelity optimization, which means scoring candidates first on a cheap stand-in, such as a few small instances, and spending full compute only on survivors. For programs this remedy is risky. A heuristic that wins on 50-city problems can lose on 1,000-city clustered ones, so a cheap test may discard exactly the structural ideas the search most needs.
Our claim is that a cheap test is reliable for some candidates and not others, and that the program tree tells us which. A child that only tweaks a constant or a local rule in its parent probably scales the same way as the parent. Comparing the two head to head on the same small instances should then predict which one wins at full scale. A child that rewrites the algorithm's overall structure has no such guarantee. We propose a scheduler that measures, while the search runs, how often small-instance comparisons agree with full-scale ones for each kind of edit in each region of the tree. It then sets each candidate's evaluation depth from that measured reliability. Cheap tests settle most small edits, and structural rewrites are protected from early pruning until enough compute has been spent to judge them.
Where the gap is
Three program-search systems already organize LLM code generation hierarchically, and all three evaluate every candidate at full fidelity. A2DEPT evolves complete programs in a tree using micro-tuning edits, macro-mutations, and semantic crossover. Its authors name verification cost as the main open problem and suggest "cheap proxies" as future work. MTHS searches over high-level metaheuristic concepts and then over task-specific code. TIDE separates code structure, evolved by the LLM, from numeric constants, tuned by a gradient-free optimizer. We reuse their tree and edit operators as the search engine and change only how evaluation compute is allocated.
Multi-fidelity methods supply the scheduling machinery but assume a different kind of candidate. HbBoPs runs Hyperband-style successive halving over prompts, using the number of validation examples as the fidelity, but only over a fixed pool of 250 candidates. MERGE³ scores merged models on small subsets chosen with item response theory, a method for picking the most informative test items. Neither faces a pool that grows by edits, where each new candidate has a known, already-evaluated parent.
Two papers constrain the design rather than motivate it. EoH-S shows that heuristics specialize by instance type, small and uniform versus large and clustered. That is direct evidence that small-instance scores can reverse rankings for program candidates. The roughly 0.85 rank correlation reported for 10% data subsets in LoRA tuning therefore cannot be assumed to carry over. HPOBench found that the advantage of multi-fidelity methods depends on budget and that full-fidelity methods catch up when budgets are large. We will therefore report results across budgets rather than at one convenient budget.
Core Claim
Consider a candidate program $c$ with parent $p$, produced by an edit of class $k$ (micro, macro, or crossover) inside a branch $b$ of the tree. Here $b$ is the subtree rooted at the most recent macro-structural ancestor. The paired low-fidelity delta $\Delta_z(c,p)$ is the score difference between child and parent on the same instances at fidelity $z$. We claim that the sign of this delta predicts the full-fidelity sign far more reliably than the child's absolute low-fidelity score predicts its full-fidelity rank. We further claim that this reliability depends strongly on $k$ and varies across branches.
The scheduler maintains a reliability estimate
$$\rho_{k,b}(z) = \Pr\big[\operatorname{sign}\Delta_z(c,p) = \operatorname{sign}\Delta_{z_{\max}}(c,p)\big],$$
which is the probability that the cheap comparison at fidelity $z$ agrees with the full comparison at $z_{\max}$. Each $\rho_{k,b}(z)$ is a beta-binomial estimate updated from every candidate that has been run at both fidelities. Its prior is shrunk toward the edit-class estimate $\rho_k(z)$, which in turn is shrunk toward a global estimate. This nesting is how the hierarchical search space enters the method. The tree supplies a hierarchy of proxy reliabilities, so a young branch borrows statistical strength from its edit class until it has its own data.
A candidate is evaluated at the cheapest fidelity $z$ whose reliability clears a target $\tau$. It is pruned if its paired delta is clearly negative at that fidelity, and otherwise promoted. Low-reliability edits, which in practice we expect to be macro-mutations, therefore go straight to an intermediate fidelity before any prune decision. Even then, a fixed small fraction of pruned candidates is promoted at random. These random promotions keep the reliability estimates honest and serve as an audit of how often pruning was wrong.
Before any of this, a crash-and-feasibility screen runs every candidate on one tiny instance. It catches the "partial migration" failures reported for A2DEPT, where a structural refactor updates one function but breaks the functions that depend on it.
Research Program
The work has three stages.
The first is a measurement study, and it can kill the idea. We run an A2DEPT-style tree search at full fidelity on CVRP and flexible job-shop scheduling from FrontierCO and on TSPLib-style TSP. We log a few thousand candidates with their parents and edit classes, and evaluate each one at four instance-size fidelities. From these logs we compute rank and sign-agreement statistics for absolute scores and for paired deltas, broken down by edit class and branch. The core claim predicts three things. Paired deltas should beat absolute scores. Micro-edits should show much higher agreement than macro-mutations. Agreement should vary across branches by more than sampling noise.
The second stage builds the scheduler on top of a reimplemented program tree. The file lists no public A2DEPT code, so we reimplement it from the paper's description of its operators, simulated annealing, and Boltzmann sampling.
The third stage is a head-to-head comparison at matched compute. All methods run under the same wall-clock evaluation budget, the same LLM, and the same token cap. Every final program is scored on held-out full-size test instances that no method saw during search.
Baselines
The naive reference is the full-fidelity tree itself, which is A2DEPT as published. The file reports that A2DEPT reduced mean normalized optimality gap by 9.8% relative to ReEvo and MCTS-AHD on standard FrontierCO problems and reached a 0.00% gap on CEVRPTW. We found no reported result on Lacuna for A2DEPT's evaluation cost or wall-clock time, so our reimplementation must first reproduce its gaps roughly before any cost comparison means anything. We run it at 1×, 2×, and 4× our method's budget, so that "more compute at full fidelity" is tested explicitly, as the HPOBench finding requires.
The strongest competitor is plain successive halving over the same tree. Each generation's new children are scored on small instances, the top third is promoted to triple the fidelity, and the process repeats, as in Hyperband-style schedules like HbBoPs. It is strong because it captures most of the obvious savings with no learned reliability at all. Its bracket settings get the same tuning budget as our threshold $\tau$.
As a cross-system reference, we include TIDE on TSP50, where it reports a 4.76% gap against 12.11% for EoH. We rerun TIDE under our budget rather than quoting its gap as directly comparable.
Three ablations isolate the key ingredients. The first scores children by absolute low-fidelity score instead of paired deltas. The second uses one global reliability estimate instead of per-edit-class and per-branch estimates. The third freezes the reliability estimates after warm-up instead of updating them online.
Beating the field means two things. At equal budget, our method must reach a lower held-out gap than successive halving on at least three of four problem families. It must also have a lower audited false-prune rate, meaning fewer pruned candidates that would have ranked in the top ten at full fidelity. If our method only matches successive halving, the reliability machinery is not worth its complexity, and we will say so.
Why not just…?
Why not just run successive halving on instance size? This is the real threat, and it is the main baseline. Our expectation that it falls short rests on the EoH-S evidence that instance type changes which heuristic wins. If that is right, schedules that ignore edit type will systematically cut structural rewrites at low fidelity. The stage-one measurement settles the question directly. If macro and micro edits show similar small-to-large agreement, successive halving is sufficient and our conditioning adds nothing.
Why not just screen for crashes on a tiny instance and evaluate the survivors fully? Much of the waste in free-form program search may come from non-executable code, and that waste is exactly what A2DEPT's self-healing loop addresses. We include this screen-only variant as a baseline. If it captures most of the savings, the case for graded fidelity is weak. The comparison separates savings from catching broken programs and savings from ranking working ones.
Why not just pick a small, maximally informative instance set, as MERGE³ does? A fixed informative subset, chosen with item response theory, is cheap and principled. However, it is chosen once, while the programs it must discriminate keep changing as the tree grows. We test an IRT-selected fixed subset as an alternative fidelity. If it matches our method, the right conclusion is that choosing which instances to run matters more than deciding how many to run per candidate.
Why not just learn a surrogate over program syntax trees, like AttnBO? AttnBO predicts performance over branching configuration spaces with a Transformer feeding a Gaussian process, and it needed roughly half the observations of independent per-branch models. Free-form code has no fixed schema of the kind AttnBO assumes, and TIDE warns that surface-level code similarity misleads. Paired evaluation sidesteps both problems, because it predicts nothing about code it has not run. A syntax-tree surrogate would be a complementary later step, not a replacement.
Proposed Experiments
The benchmarks are FrontierCO's CVRP, CFLP, and FJSP, plus the highly constrained CEVRPTW, which tests whether feasibility-heavy problems reverse rankings more often. We add TSP and CVRP on the TSPLib and CVRPLib families used by MTHS, TIDE, and ReEvo. The fidelity axis is instance size, plus instance count at each size.
We report three things for every method. The first is held-out normalized optimality gap as a function of evaluation CPU-seconds, at three budgets. The second is LLM tokens consumed. The third is the audited false-prune rate.
The decisive checks are three. In stage one, paired micro-edit deltas must show markedly higher sign agreement than macro-mutation deltas; if they do not, we drop edit-type conditioning. At matched budget, the method must beat successive halving on held-out gap with a lower false-prune rate. Finally, the advantage must persist at the 4× budget. If it vanishes there, we confirm HPOBench's caution, and the contribution narrows to the low-budget regime.
A secondary check concerns depth. The compute saved goes into deeper trees, which tests whether deeper search pushes past the 3-to-5-round plateau that Yan et al. report for refinement loops driven by feedback.
References
- $A_2$DEPT: Large Language Model–Driven Automated Algorithm Design via Evolutionary Program Trees
- Hierarchical Representations for Cross-task Automated Heuristic Design using LLMs
- TIDE: Tuning-Integrated Dynamic Evolution for LLM-Based Automated Heuristic Design
- Hyperband-based Bayesian Optimization for Black-box Prompt Selection
- MERGE$^3$: Efficient Evolutionary Merging on Consumer-grade GPUs
- EoH-S: Evolution of Heuristic Set Using LLMs for Automated Heuristic Design
- A Language-Guided Bayesian Optimization for Efficient LoRA Hyperparameter Search
- HPOBench: A Collection of Reproducible Multi-Fidelity Benchmark Problems for HPO
- Modeling All Response Surfaces in One for Conditional Search Spaces
- CodeTransOcean: A Comprehensive Multilingual Benchmark for Code Translation