EvoDuet: Bilevel Co-Evolution of Web Searching and Task Solving for Scientific Discovery
Young-Jun Lee, Jinheon Baek, Soyeong Jeong, Minki Kang, Seungyeon Jwa, Jonghyun Choi, Seungho Han, Dongyeop Kang
cs.CL
2026-10-01
EvoDuet co-evolves web queries with candidate solutions in a bi-level loop; Gemini-3.8-Flash NDG goes from 61.3% to 82.3%, and 8 of 21 tasks see new best scores.
Evolutionary search scaffolds such as FunSearch, AlphaEvolve, and OpenEvolve run a tight loop: the LLM proposes a candidate program, a deterministic evaluator scores it, and high scorers seed the next round. Everything the loop knows comes from the run's own history plus the LLM's parametric knowledge, so the search is closed. When progress depends on knowledge neither source holds, say the API of a newer library version, the loop stalls.
A preliminary experiment quantifies this. Across 31 optimization tasks, hand-curated oracle documents supplied at every iteration lift OpenEvolve's average NDG by 10.3% with Qwen3.5-9B and 4.0% with GPT-5.6-Luna. The gain does not arrive automatically: on Sums/Diffs, oracle documents do nothing at one candidate per iteration and only help at eight (+14.9% NDG). Handing the model a web search tool fails differently; over 100 iterations on Denoising it retrieves the same pages again and again (88.1% repeated URLs) and stops improving after iteration 50. Useful external knowledge requires queries that evolve with the solution.
EvoDuet frames discovery as bi-level optimization: an outer loop evolves solutions, an inner loop evolves search queries, and model parameters stay frozen.
The load-bearing choice is the surrogate. Whether a query helps is observable only after generating and evaluating a candidate, which is too expensive to repeat per query inside the inner loop. Predicted scores stand in, and they track reality: Spearman ρ = 0.86 against evaluated scores across 4,324 retrievals.
On 21 tasks with one candidate per iteration:
| Model | NDG change (N=1) |
| GPT-5.6-Luna | 74.1% -> 78.0% |
| Gemini-3.8-Flash | 61.3% -> 82.3% |
| Qwen3.5-9B | -14.4% |
Scaling candidates from 1 to 16 raises NDG monotonically for both frontier models (GPT-5.6-Luna 89.6% to 95.7%, Gemini-3.8-Flash 84.5% to 89.6% on eight tasks). The best runs beat previously reported best scores on eight tasks and match three more, including Swap Reduction on Q20 (15,186 to 14,835 SWAPs) and Rosetta; the eleven runs average $45.56 each. On Denoising, EvoDuet reaches 100.27% NDG for $38.45, 6.9x cheaper than SimpleTES at an estimated $265.39.
Ablations isolate the parts. The knowledge-gap gate reaches 84.5% NDG on Denoising against 60.6% for the stagnation heuristic EvoX uses. Against other wirings of search, bi-level scores 84.5% on Denoising where an in-loop search tool gets 43.2%, and 0.7846 on Burgers against DeepEvolve's published 0.6666. Packed onto Top-K and EvoX, it adds +46.7/+63.6 and +55.1/+37.8 NDG on Sums/Diffs and Denoising. Mechanistically, iterations that retrieve at least one document predicted to beat the parent improve on it 67.1% of the time versus 52.1% with no documents, and the most common use of retrieved material is method transfer, seen in 55 of 82 analyzed runs.
For anyone building automated discovery agents, this turns “when to search and what to ask” into something the search itself optimizes. It ships as an outer loop that leaves model parameters untouched and stacks onto OpenEvolve, Top-K, and EvoX, with code on GitHub. Where it pays off is equally clear: tasks with baseline NDG between 20% and 40% see a median +17.5% gain, while baselines above 80% see a median of zero. It is an incremental but well-executed addition to the scaffold family: one clear mechanism, consistent numbers.
The paper is candid that Qwen3.5-9B loses 14.4% NDG at N=1: sampled revisions show 26% either ignore the retrieved method (6%) or implement it incorrectly (20%), so co-evolution demands a model that can apply evidence as well as find it. Predicted gains mislead often enough that 29 of 82 runs contain revisions inspired by retrieved ideas that made things worse; the evaluator stays the final arbiter. Gains shrink as the baseline strengthens (Pearson r = -0.41).
Two things stand out on a close read. The main experiments cover 21 tasks while the preliminary analysis used 31, and the main text does not explain the selection. And 6 of 82 runs reuse public constructions more or less directly; the appendices document attribution, but as such systems proliferate, how much of a “discovery” is a retrieved answer becomes the question to ask.