Rank-Based Credit for LLM Search Operators

Many recent systems that use a large language model (LLM) to evolve programs, formulas, or heuristics share one structure. At each step a small bandit, an online algorithm that learns which of several options pays off, picks an editing "operator": refine the constants, mutate the structure, recombine two parents, or start over. The LLM carries out the chosen edit and the result is scored. These bandits are fed raw fitness improvements or binary success flags. Classical evolutionary computation found twenty years ago that this kind of credit is fragile. Averaging raw gains starves operators that rarely help but help a lot, and the bandit's choices change if the fitness is rescaled. LLM-driven search makes both problems worse. Most edits fail or are syntactically invalid, a few produce large jumps, and fitness scales differ by orders of magnitude across tasks.

We propose to carry rank-based, extreme-value credit assignment into LLM operator selection and to add one ingredient the classical work never needed: the cost of each operator. The claim fits in two sentences. When an operator's payoff is heavy-tailed and its cost varies, the bandit should reward it for how often it produces a top-ranked outcome per unit of budget, not for its average raw gain. Doing so should make LLM search both more sample-efficient and unaffected by arbitrary choices of fitness scale.

Where this sits

The credit-assignment ideas come from three classical papers, which supply the method. Adaptive operator selection with dynamic multi-armed bandits couples an upper-confidence-bound selector with a change-point test that resets an operator's statistics when its payoff shifts. That test's thresholds need tuning. Extreme Value Based Adaptive Operator Selection credits each operator with its maximum gain in a sliding window, which protects rare large improvers. Toward comparison-based adaptive operator selection replaces raw gains with ranks (Sum of Ranks and an area-under-curve score). This makes selection invariant to monotone transforms of the fitness and needs less retuning. All three were tested on OneMax and synthetic scenarios, where every operator costs the same and never fails.

The LLM systems motivate the proposal, because they show the gap. Deliberate Evolution picks among Refine, Mutate, Crossover and Regenerate using recent success rates. REFLEX runs a stationary UCB1 over mutation, crossover and skill retrieval. TIDE schedules prompt-level variation with UCB and tunes constants with a separate operator that makes no LLM calls. That design already hints that operators differ sharply in cost. None of these systems uses rank or extreme-value credit, and none charges an operator for what it consumes.

The obvious combination of the two directions would be a two-level bandit: an outer bandit over strategies and an inner bandit over operators. It is partly done already. TIDE nests an operator scheduler inside a structural island model, and RF-Agent uses tree-search bandit logic over candidates. A skeptic would also say that a flat bandit over strategy–operator pairs would do as well. We therefore leave the hierarchy alone and target the signal that every such bandit consumes. If the credit is wrong, adding levels only multiplies the error.

Core Claim

Consider a window of the last $W$ evaluated edits from all operators. Each outcome is ranked by fitness improvement, and invalid or crashing outputs share the worst rank. For operator $k$, let $q_k$ be the fraction of its recent outcomes that land in the top $\rho$ fraction of the window. Let $c_k$ be its running mean cost in LLM tokens or wall-clock time. The credit is

$$ r_k = \frac{q_k}{c_k / \bar{c}}, $$

where $\bar{c}$ is the mean cost across operators. This credit enters a standard UCB rule in place of the mean raw gain. The top-quantile rate is the extreme-value idea recast in ranks. Using ranks makes $r_k$ invariant to any monotone transform of fitness. The sliding window handles drift across search phases without change-point thresholds. The cost normalization lets a cheap constant-tuning operator win when it is productive per token even though its individual gains are small.

The prediction is specific. Scalar-credit bandits should change their operator frequencies, and their final results, when the bandit's reward is computed from NMSE rather than log-NMSE. Rank-credit bandits should not. The gap should be largest on tasks with the heaviest-tailed improvement distributions.

Research Program

The first stage is diagnostic. We instrument Deliberate Evolution on LLM-SRBench and a TIDE-style loop on TSP50 and Knapsack, and log every operator call with its improvement, validity, and token cost. For each operator we measure the fraction of invalid outputs, the tail heaviness of the positive improvements (the share of total gain contributed by the top 5% of edits), and how operator payoff drifts over the run. If improvements turn out to be light-tailed and operator costs roughly equal, the extreme-value and cost terms lose their motivation. We would report that as a finding and narrow the method to plain rank credit.

The second stage replaces each host system's operator credit with $r_k$ and changes nothing else: same prompts, same operators, same LLM. We sweep $W$ and $\rho$ on a held-out subset of problems and then freeze them for all reported runs. This tests the claim from the comparison-based work that rank credit needs little retuning.

The third stage is an invariance stress test. We keep the fitness shown to the LLM in prompts fixed, and change only the signal given to the bandit, applying log, square, and exponential transforms. This isolates the bandit's own sensitivity.

Baselines

The naive reference is uniform random choice among the host system's operators. It uses the same LLM, the same per-problem sample budget (400 samples on LLM-SRBench, the budget Deliberate Evolution reports), and the same seeds. In LLM search it may be surprisingly strong, because the LLM's sampling already adds diversity.

The strongest existing method is Deliberate Evolution's own success-rate bandit, run with its released operators and diagnostic tools. The file reports that it cuts average NMSE on LSR-Transform by 55% with Llama-3.1-8B and 37% with Qwen3-4B relative to standard baselines, using 400 samples instead of 1,000 (Deliberate Evolution). On combinatorial heuristics the reference is TIDE's UCB scheduler, which reports a TSP50 optimality gap of 4.76% against EoH's 12.11% and a Knapsack gap of 0.02% (TIDE). We rerun both hosts ourselves rather than comparing against published numbers, so that the LLM and budget are identical. Beating Deliberate Evolution means a lower median NMSE than its own bandit at 400 samples across the 240 problems, significant under a paired test over problems. Matching its accuracy at fewer samples also counts. Beating TIDE means a lower mean TSP50 gap at equal input tokens.

A second strong competitor is a scalar bandit whose rewards are z-scored within the same sliding window. This is the cheap fix a reviewer would propose, and it captures much of what ranks do. We also run D-MAB with Page-Hinkley resets, tuned on the same held-out subset, to separate "handles drift" from "uses ranks." Three ablations isolate the ingredients: rank credit with mean rather than top-quantile aggregation, the top-quantile rule on raw gains, and full rank credit with the cost term removed.

Why not just…?

Why not just pick operators uniformly at random? Uniform selection is a real threat in this setting. Evidence against it comes mostly from settings without LLMs. Balans found an operator mix no uniform policy could imitate: Local Branching was used only 0.6% of the time on H-MIPLIB while the primal gap fell by more than 75%. Grey-box fuzzing work shows the same pattern for mutators (Adaptive Grey-Box Fuzz-Testing with Thompson Sampling). Whether this holds when the LLM itself diversifies proposals is an empirical question. The uniform baseline in every experiment settles it. If uniform matches all bandits, the correct conclusion is that operator selection is not the bottleneck in these systems, and we would report exactly that.

Why not just normalize the raw rewards? Z-scoring within a window removes scale differences, but it does not make selection invariant to nonlinear monotone transforms. It also still averages away rare large gains. The invariance stress test and the z-score baseline test this directly. If z-scoring matches rank credit on accuracy and invariance, the contribution shrinks to the extreme-value and cost terms, and the ablations show whether those carry the gains.

Why not just ask the LLM which operator to use? KernelBand ran this ablation: it replaced its bandit with the LLM's own strategy choice, and performance fell sharply. REFLEX reports that mixing diagnosis and editing in one LLM call entangled the two tasks. We include an LLM-chooses-operator arm on LLM-SRBench at equal token budget, charging the selection call to the budget, to check whether this holds for symbolic regression.

Why not just build a two-level strategy/operator bandit? Hierarchy adds arms and delays feedback, yet both levels would still consume the same miscalibrated scalar credit. TIDE already shows that a nested design works with naive credit. Our experiments hold the hierarchy fixed in the host systems, so any gain can be attributed to credit alone.

Proposed Experiments

The main experiment runs Deliberate Evolution on all 240 LLM-SRBench problems with Llama-3.1-8B and Qwen3-4B at 400 samples and five seeds. Every credit rule from the Baselines section is tested. We report median and mean NMSE, exact-recovery rate, invalid-output rate, and tokens consumed.

The second experiment runs a TIDE-style loop on TSP50, Knapsack, CVRP, and bin packing, and reports optimality gap at matched input tokens. The cost term matters most here, because the constant-tuning operator makes no LLM calls.

The third is a sanity replication on 10,000-bit OneMax under log, exponential, and square transforms, following Toward comparison-based adaptive operator selection. It confirms that our implementation reproduces known invariance before we apply it to LLMs. The file gives no generation counts for OneMax, so we only check that the qualitative ordering is reproduced.

The decisive checks are three. First, on the transformed-reward runs, the change in operator frequencies and in final NMSE must be near zero for rank credit and clearly nonzero for scalar and z-scored credit. Second, across problems, the advantage over Deliberate Evolution's bandit should correlate positively with the tail heaviness measured in the diagnostic stage; a flat relationship would falsify the mechanism even if average gains appear. Third, the uniform baseline must lose to rank credit by a margin larger than seed variance. If it does not, we report the negative result.