Staleness as Selection Pressure in Asynchronous LLM Program Search

Large language models can write useful heuristics for problems like bin packing and the traveling salesman problem when they sit inside an evolutionary loop. The model proposes edits to programs, an evaluator scores them, and the best programs seed the next round. These loops have two problems that pull against each other. They are expensive: a full search can take up to 10 days on a V100 or cost over $200 in API fees (Understanding the Importance of Evolutionary Search in Automated Heuristic Design with Large Language Models). They also collapse early: greedy loops fall into a "greedy trap" and keep producing small variants of one algorithm. The usual fixes for collapse, such as larger populations, islands, and code-dissimilarity scoring, add evaluations or synchronization steps. That makes the cost problem worse.

This proposal tests one observation. When many workers share a population without waiting for each other at generation boundaries, each worker picks parents from a slightly out-of-date view of that population. That staleness means a newly found best program does not immediately take over every worker's choice of parent. It works like a built-in delay on greedy takeover and costs no extra evaluations. We propose to make staleness an explicit, controlled parameter of an asynchronous shared population, and to measure whether it reduces premature convergence while also removing the idle time that generation barriers impose.

Core Claim

In asynchronous LLM-driven program search, the age of the population snapshot a worker reads when choosing a parent controls how strongly the search favors the current best. Bounded staleness should therefore give two benefits together:

  1. Higher worker utilization, because nobody waits for a generation to finish.
  2. Diversity comparable to explicit diversity mechanisms, at equal numbers of LLM queries.

The claim is falsifiable in a specific way. If a synchronous loop with a softer parent-selection rule, tuned to the same parent-selection entropy, matches staleness on final quality, then staleness is only a disguised temperature knob. The contribution would then reduce to "asynchrony is free; tune temperature separately." We treat that outcome as a real possibility, not a strawman.

The intuition for why staleness might differ from temperature is timing. Softer selection spreads parent choices evenly at every step. Staleness instead blinds all workers to a new best for a window of about $\tau$ steps, where $\tau$ is the maximum snapshot age. In that window, work continues on the other lineages already in progress. This resembles island models with migration delay, and it requires no partitioning.

Relation to Prior Work

Three pieces of prior work motivate the proposal.

Understanding the Importance of Evolutionary Search in Automated Heuristic Design with Large Language Models built the llm-eps benchmark and showed two things. A (1+1) single-parent greedy loop stagnates relative to population methods like EoH. Uncoordinated sampling is worse than both. Its methods run in synchronous generations, and it leaves cost reduction open.

Multi-Objective Evolution of Heuristic Using Large Language Model (MEoH) keeps diversity by combining Pareto dominance with abstract-syntax-tree dissimilarity. It remains generational. Its diversity measure is static code structure, which can be fooled by rewrites that behave identically.

EffiLearner refines one program with line-level profiler feedback. Nearly all of its gains arrive in the first two iterations, so a single refinement trajectory saturates quickly.

Two further papers constrain and supply the method.

Lock-Free Optimization for Non-Convex Problems analyzes asynchronous gradient descent in shared memory. It models the gap between a thread reading shared state and writing its update, and it proves convergence only to stationary points. We borrow its framing of the read-write gap. We differ in treating staleness as a deliberate exploration parameter in a discrete program space, not as noise to be bounded away. Its NUMA result, where 4 threads ran slower than 1 on connect-4, is a warning that shared-memory asynchrony does not automatically pay off.

The BW-Tree keeps a mapping table from logical IDs to chains of immutable delta records, installed by compare-and-swap (an atomic instruction that updates a memory word only if it still holds an expected value). We reuse that structure for the population. Each lineage is a logical ID. Each refinement is an immutable delta record carrying the program edit, its score, and a version stamp. As a result, "the population as of $\tau$ versions ago" is a cheap read of the chain history rather than a copy.

iRe2f is a parallel in a different domain. It applies small delta updates to a parser's representations instead of re-encoding everything, which keeps throughput near the base parser while improving accuracy. We borrow the lesson that refinement should cost in proportion to the edit.

We state one point plainly. At LLM timescales, where one query takes seconds, lock-freedom is not a throughput necessity; a mutex around the population would rarely be contended. The lock-free, versioned design matters here because it makes controlled-age snapshot reads cheap and consistent without anyone copying the population. It is not the source of any speedup we claim.

Research Program

We will build an asynchronous search engine in which $W$ workers repeatedly do four things:

  1. Read a population snapshot of chosen age.
  2. Select parents.
  3. Ask an LLM for a mutation or a refinement.
  4. Evaluate the result and append it as a delta record.

Selection happens against snapshot $P_{t-\tau}$, where $t$ is the current global version and $\tau$ is drawn from a controlled distribution with maximum $\tau_{\max}$. Setting $\tau_{\max}=0$ gives fully fresh reads. The other settings fix $\tau_{\max}$ in units of completed evaluations, or let it drift naturally with asynchrony.

A simple takeover model gives the expected effect. Suppose each read of a fresh snapshot picks the incumbent best with probability $p$. Then the expected number of new children of a newly found best within its first $k$ evaluations is roughly $p\cdot\max(0,k-\tau)$. Staleness therefore shifts takeover by $\tau$ rather than flattening it. We will check this delay directly by logging the lineage of every evaluation.

A second knob governs refinement depth. Each lineage's delta chain carries the score gain of each refinement. When a lineage's last $r$ deltas each gain less than a threshold, the lineage is "consolidated": it stops receiving refinements, and workers are steered toward mutation from other lineages. EffiLearner's saturation after 2 to 3 iterations sets the prior range for $r$. This knob addresses the refinement-cost direction. It spends evaluations where the diminishing-returns curve is still steep, and it is crossed factorially with staleness.

We will measure diversity behaviorally, not only through syntax trees. Each program gets a fingerprint consisting of its decision vector on a fixed set of probe instances. Diversity is the number of distinct fingerprint clusters and the entropy over them. This targets the known weakness of the dissimilarity measure in MEoH.

Baselines

Fresh-read asynchronous engine ($\tau_{\max}=0$). This is the naive reference and isolates staleness. It is the same engine, with the same workers and the same query budget, but every read sees the latest population. Its purpose is to show whether asynchrony alone, without staleness, helps or hurts.

Synchronous generational EoH, as run in llm-eps. This is the strongest documented method on the shared benchmark. The file reports a TSP gap of 0.12% for EoH with Claude 3 Opus, 3.87% for (1+1)-EPS, and 9.64% for standalone sampling (Understanding the Importance of Evolutionary Search in Automated Heuristic Design with Large Language Models). On the admissible set problem, it reports 7.5% for (1+1)-EPS with GPT-3.5. We will rerun EoH ourselves with the same LLM, the same total query budget, the same evaluator instances, and the same worker count, parallelized within each generation. We then compare against our own rerun rather than the published figure, since models and budgets will differ. Beating it means reaching an equal or lower gap at equal queries while using less wall-clock time. Matching its gap at lower wall-clock also counts as a contribution. Losing on gap at equal queries means the staleness claim fails.

MEoH-style dominance-dissimilarity selection and a FunSearch-style island model. These are the explicit diversity mechanisms that staleness claims to substitute for. Both run inside our asynchronous engine with fresh reads, so that only the diversity mechanism differs. We will tune them with the same hyperparameter-search budget given to $\tau_{\max}$. For MEoH on bin packing, the file reports heuristics "up to 10 times faster" than single-objective EoH at competitive accuracy, but gives no hypervolume numbers. We therefore report our own measurements.

Temperature-matched synchronous selection. This baseline is the key ablation. We tune the softmax temperature of synchronous parent selection so that its parent-selection entropy matches that measured under staleness, and we compare final gaps. It is also listed under the next section because it is the main threat to the claim.

Why not just…?

Why not just lower the selection temperature in a synchronous loop? This is the most serious alternative. If staleness only softens selection, a one-line change to a synchronous loop reproduces it. The temperature-matched ablation settles the question. If staleness and matched temperature give indistinguishable gaps and diversity curves, we will report that the diversity benefit is not specific to staleness. The remaining result would then be that asynchronous execution removes barrier idle time without harming search quality. That finding would be smaller but still useful given the 10-day costs.

Why not just use a mutex-protected queue instead of a lock-free versioned store? At current LLM query latencies this would probably perform the same, and we will run it to confirm. What the versioned delta store adds is cheap, exact control over snapshot age. With a mutex, controlling age requires copying or logging the population. If the mutex version with copy-on-read matches ours in both throughput and outcome, we will say so. The lock-free design then remains a convenience that matters only when evaluators are cheap and local.

Why not just run independent restarts in parallel? The llm-eps results already show that uncoordinated sampling is far worse than coordinated search: 9.64% versus 0.12% on TSP. We include restarts at equal total queries as a sanity floor. Restarts are also the $\tau\to\infty$ limit of our knob, so they anchor one end of the staleness curve.

Why not just add Lévy-style random jumps? In program space, random perturbations mostly break programs. The structured alternative, dissimilarity selection, is already a baseline. We therefore test the random-jump idea only as an LLM prompt that asks for a "radically different algorithm" at a fixed rate. This controls for the possibility that any periodic exploration pulse, not staleness specifically, drives the gains.

Proposed Experiments

We will run on the three llm-eps tasks (admissible set, online bin packing, and TSP), with bin packing tested on Weibull instances from 5,000 to 100,000 items following MEoH's protocol. Refinement-depth experiments run on EffiBench. The primary metric is the optimality gap at fixed LLM-query budgets of 500, 2,000, and 5,000. Secondary metrics are:

  1. Wall-clock time to a target gap.
  2. Fraction of worker time spent idle.
  3. Behavioral diversity over time.
  4. Measured takeover delay of each new best.

For EffiBench we report execution time, memory, and pass@1. EffiLearner reports StarCoder2-15B runtime dropping from 0.93s to 0.12s; that single-trajectory refinement is our reference, at matched total refinement calls.

The decisive checks are these:

  1. Staleness at its best $\tau_{\max}$ must beat fresh-read asynchrony on gap at equal queries across at least two of the three tasks, with five or more seeds.
  2. It must reach within noise of tuned dissimilarity selection and islands on gap and diversity, while adding zero extra evaluations.
  3. It must beat temperature-matched synchronous selection. If it fails this check, the claim narrows as described above.
  4. Measured takeover delay should grow roughly linearly with $\tau_{\max}$, as the simple model predicts. If gains appear without that delay, the explanation is wrong even if the numbers look good.
  5. The depth-cap knob should reduce total refinement calls at unchanged final quality on EffiBench. If it does not, the refinement-cost component is dropped.

We will also report one run with a small local model as the evaluator-plus-generator, where queries are fast. This is the regime where the lock-free store's contention behavior, and the NUMA effect seen by Zhao et al., could actually matter.