cs.CLSep 30, 2026
SaveEvoDuet: Bilevel Co-Evolution of Web Searching and Task Solving for Scientific Discovery
Organizations: University of Minnesota · KAIST · Seoul National University · Hanyang University
Abstract
Evolutionary search with large language models (LLMs) can stall when progress requires external knowledge the model lacks. Supplying relevant documents helps, but simply adding web search tool can keep returning the same pages as solutions change. We introduce EvoDuet, a bi-level optimization method that co-evolves solutions and search queries with fixed model parameters. At each iteration, a retrieval gate lets the LLM assess its knowledge gap and choose to retrieve new documents, reuse stored ones, or proceed without them. An inner loop refines queries and ranks documents by the solution scores they are predicted to yield; an outer loop generates candidates in parallel from these documents and records the evaluated outcomes for later searches. Across 21 optimization tasks with one candidate per iteration, EvoDuet raises OpenEvolve's normalized discovery gain from 74.1% to 78.0% with GPT-5.6-Luna and from 61.3% to 82.3% with Gemini-3.8-Flash, whereas Qwen3.5-9B does not benefit. Our best runs surpass the previously reported best scores on eight tasks, including Swap Reduction on Q20 and Rosetta, and match them on three more. EvoDuet also improves with other scaffolds (e.g., Top-K, EvoX) on Sums/Diffs and Denoising, demonstrating its applicability across evolutionary search scaffolds.
Figures & tables
Figure 1: Packing loops of multiple optimization scaffolds
Figure 2: EvoDuet co-evolves solutions and web queries. The inner loop evolves queries; the outer loop uses retrieved documents to revise and evaluate solutions. The Swap Reduction example illustrates method transfer (the most common of the six behaviors analyzed in Section 5.1 ): the model applies retrieved routing principles to prioritize gates closer to execution (iteration 5) and penalize reversing the last SWAP (iteration 66). At iteration 64, the gate reuses stored documents without a new web search. The best router found in this run uses 14,835 Q20 SWAPs, 2.31% fewer than the released SimpleTES program ( WILL Team, 2026 ) (15,186) under the same evaluator.
Figure 3: OpenEvolve with and without oracle documents on 31 optimization tasks using Qwen3.5-9B and GPT-5.6-Luna. (a) Average NDG across tasks. (b) Per-task NDG versus baseline NDG, with bin medians pooled across models. Shading marks baseline NDG below 5% or at least 80%; hollow markers denote simple tasks. The dashed line shows the gain needed to reach 100% NDG. (c) Per-task NDG in descending order. Legends count tasks with NDG increases (improved) or decreases (degraded) of more than 1%; shading indicates changes within .
Figure 4: Effects of parallel generation and query evolution with GPT-5.6-Luna. (a) NDG of OpenEvolve on Sums/Diffs (mathematics) with and without oracle documents, using or candidates per iteration. (b) Cumulative number of search queries. (c) Number of distinct URLs returned. (d) Held-out NDG of the best program for each method.
Figure 5: Overview of EvoDuet . The outer loop evolves solutions, while the inner loop evolves web search queries using predicted solution scores. A knowledge-gap-based retrieval gate links the two loops by deciding whether to retrieve new documents ( ), reuse stored documents ( ), or proceed without documents ( ).
Figure 6: Discovery performance of OpenEvolve with and without EvoDuet . Results cover 21 paired tasks with or candidates per iteration. For each model, method, task, and , we report the best NDG across four runs. (a) Mean best NDG across tasks and the gain from adding EvoDuet ( NDG). (b) Mean NDG within each task group. (c) Task-level NDG versus OpenEvolve’s NDG; black bars and labels show the median gain within each NDG range.
Figure 7: Scaling effect of .
Figure 8: Program improvement with web documents and patterns of document use. Results cover 8,200 iterations from 82 GPT-5.6-Luna runs across 21 tasks. (a) Predicted versus evaluated candidate scores, scaled to using each task’s 2nd and 98th percentiles. (b) Rates at which the selected candidate improves on its parent (left axis) or sets a new best score within the run (right axis), grouped by gate decision. Arrows compare iterations with iterations that retain at least one promising document. (c) Percentage of runs exhibiting each behavior. Each run is counted at most once per category and may appear in multiple categories.
Table 1: Additional analyses of EvoDuet . For (b)-(e), we use GPT-5.6-Luna.
Appendix figures & tables23 assets
Supplementary material from the paper’s appendix.
Appendix
Algorithm 1 EvoDuet : overall procedure.
Figure 9: Three ways to couple web search with solution evolution. Top: search runs within generation (joint-level), precedes generation (sequential), or co-evolves with solutions (bi-level). Blue denotes search, violet solution evolution, and amber the knowledge-gap gate; the dashed overlap marks the coupling between the two loops. Bottom: search timing, query guidance, and memory for reuse across iterations. Checkmarks highlight EvoDuet ’s design choices.
Table 2: Joint-level versus bi-level retrieval (NDG, %).
| Domain | Tasks | # |
|---|---|---|
| Simple Scientific Optimization | Pressure Vessel, SINDy, Batch Reactor, LABS-27, LJ-13, Chwirut2, Perovskites, SRSD, GuacaMol, Summit | 10 |
| Quantum compilation | Swap Reduction | 1 |
| Astrodynamics | Cassini, Galileo, Mariner 10, Rosetta, Voyager 2 | 5 |
| Scientific algorithms | Denoising | 1 |
| AI foundations | Domain Mixture, U Shape, LR & BSZ, Parallel | 4 |
| Algorithm engineering | AHC039, AHC058 | 2 |
Table 3: Task coverage.
Table 6: Inner-loop budget ablations with GPT-5.6-Luna.
Table 7: Quantum compilation and astrodynamics.
Table 8: Scientific algorithms and AI foundations.
Table 9: Mathematics.
Table 10: Algorithm engineering.
Figure 10: Japanese phrases in search queries. (a) Share of parseable queries containing Japanese phrases, including repeated outputs. (b) Share of querying runs with at least one such query. Purple and hatched blue bars denote and . Accented names such as Erdős are excluded.
Figure 11: Top-20 web sources by task domain. Hosts are ranked by the share of retrieval iterations. Each host counts once per iteration; hosts can co-occur. All panels use a common 0–100% scale and report retrieval counts.
Figure 12: Top-20 web sources by task domain (continued). Exposure rates pool all available runs within each domain, using the same counting rule and scale.
Figure 13: Aggregated search dynamics by task group and model. Curves show retrieval (blue), reuse (purple), and missing gate responses (gray) in ten-iteration bins. Each panel pools all available runs. Percentages use all scheduled slots, including no-op and malformed decisions. All panels share the same axes.
Figure 14: GPT-5.6-Luna’s lookup provenance by task group. Arrows point from each lookup (purple, bottom) back to the document’s first recorded retrieval (blue, top), pooling all available runs. Both endpoints use ten-iteration bins; vertical arrows represent reuse within the same bin. Width encodes the within-panel share of resolved document ID–iteration pairs on a common square-root scale; is their total. All 10,887 resolved pairs are shown; 63 unresolved pairs are excluded.
Figure 15: Source age at reuse by task group and model. Bars aggregate resolved document requests from available GPT-5.6-Luna and Gemini-3.8-Flash checkpoints. Age is the reuse iteration minus the first retrieval iteration; counts document ID–iteration pairs. We exclude 63 unresolved Luna pairs. Qwen lacks saved checkpoint provenance and is omitted from this figure.
Figure 16: Program revision outcomes with retrieved documents. (a) Evaluation failure rates with and without documents at ; both conditions use EvoDuet . (b) Outcomes of 19,866 document iterations, with counts above the bars. All rates include unsuccessful generations in the denominator. The policy selects among eight candidates at document steps. Comparisons are observational because the gate selects document exposure.
| Task | Supplied evidence | Observed revision | Outcome |
|---|---|---|---|
| Sums/Diffs | A construction using the Chinese Remainder Theorem. | Adds random local search without implementing the supplied modular construction. | |
| Circle Packing (26) | Joint optimization of centers and radii using SLSQP. | Adopts SLSQP but mixes grouped and interleaved parameter layouts; a returned circle extends outside the square. | Invalid |
| Denoising | The Anscombe transform and its inverse. | Omits the factor of two in the forward transform, while the inverse still divides by two before squaring. |
Table 11: Examples of unsuccessful document use by Qwen at . Supplied documents, parent and child code, and evaluator records are inspected together. Scores are recorded search scores ( ). These cases illustrate mechanisms rather than their population frequencies.
| Behavior | Run | Main finding | Sec. |
|---|---|---|---|
| Method transfer | Swap Reduction | Retrieved depth weighting remains in later best programs despite repeated search misses. | I.1 |
| Cross-domain transfer | Erdős min. overlap | A radar codeword seeds later improvements in a number-theory task. | I.2 |
| Live documentation lookup | Voyager 2 | The added API keywords repeat defaults already given in the prompt. | I.3 |
| Target-informed reconstruction | CP ( =26) | A generated solver exceeds the value named in the first query. | I.4 |
| Public artifact reuse | Erdős, second run | A program that downloads a published witness improves the run’s best. | I.5 |
| Evidence-inspired over-reach | Galileo | A promising retrieval precedes a worse child; the run’s best is preserved. | I.6 |
Table 12: Seven worked behavior cases. Each case links recorded queries and sources to program changes and evaluation results. The cases illustrate the flags in Appendix E.1 ; a flag alone does not establish successful use of the retrieved evidence.
Figure 17: Routed quantum circuits on Q20. (a) The alu-v0_27 input circuit. (b, c) Outputs of the released SimpleTES program and EvoDuet ’s best program under matched replay settings. Colored bands highlight inserted SWAPs: two for SimpleTES and one for EvoDuet . All gates are shown; only idle wires are omitted. Labels and denote logical qubits and physical sites, respectively.
Figure 18: Rosetta and Voyager 2. (a, b) Encounters and dates of the SimpleTES construction and of the best program of EvoDuet ; diamonds are deep-space maneuvers labelled with their in km/s. (c) Total split into maneuvers and launch or arrival. On Rosetta, EvoDuet adds the Mars flyby of the actual mission; on Voyager 2, both follow the same tour and EvoDuet moves the arrival onto the end of the window. Planet images: NASA (public domain).
Figure 19: Denoised gene expression. (a) Noisy PBMC input, (b, c) outputs of the released SimpleTES program and EvoDuet ’s best program, and (d) held-out counts. Columns show all 1,087 cells; rows show 24 genes selected for their variability in the input. Gene selection and ordering use only the input, with the same order and color scale across panels. Values are log-normalized per cell. Held-out counts are independent observations and still contain noise.
Figure 20: Parallel Scaling and Domain Mixture. (a) Observed loss on the grid of parameter count and parallel streams for the two Parallel datasets (darker cells indicate lower loss within each dataset); the dashed row ( ) is held out, and a star marks the law that predicts that cell more closely ( EvoDuet in 7 of 12). (b) Predicted against actual held-out loss on Domain Mixture. (c) Held-out on a log scale. Both margins are small.
Figure 21: Mathematical objects. (a) The Erdős step function of EvoDuet , which is the published witness the run located and polished, against the SimpleTES construction. (b) The two order-29 matrices, which reach the same determinant. (c) The two sum–difference sets; EvoDuet scores 1.144999, exceeding the released post-training SimpleTES set (1.144887).
More in this topic
Large Language Model-Guided Optimization
Large Language Model-Guided Optimization uses language models to propose, steer, and refine solutions to hard search and design problems.
See all 587 papers