LLM Evolutionary Search Strategies Should be Compared by Tokens

Tal Oved; Roi Pony; Oshri Naparstek; Udi Barzelay

cs.NEOct 13, 2026

LLM Evolutionary Search Strategies Should be Compared by Tokens

Authors: Tal Oved, Roi Pony, Oshri Naparstek, Udi Barzelay

Organizations: IBM Research

Abstract

LLM evolutionary search is currently evaluated by counting proposals (candidate programs). We demonstrate this metric hides the true cost of search, and redo the comparison using tokens. By replaying 600 logged runs across 5 tasks and 3 methods, we show that proposal costs vary wildly from 16k to 39k tokens. In equal-proposal comparisons, this silently grants some methods up to 1.9x the compute of others, and gives evolution roughly 6x the budget of independent sampling. When we match token budgets, giving sampling six times more attempts, and remove scorer exploits, the evolutionary advantage largely vanishes. Evolution beats independent sampling by 5% or less on 12 of 15 task-method pairs, retaining a 23 to 28% margin on only 3, all on one task. A replication with Claude Haiku 4.5 reproduces this split, though a third backbone shows its size depends on the model too. The performance margin justifying these systems is often an accounting artifact. Reporting tokens, not proposals and not model calls, fixes this and costs nothing, as the logs already hold them.

Figures & tables

Method	tokens/prop.	calls/prop.	reasoning
OpenEvolve	22,985	1.29	8%
EvoX	26,992	1.82	9%
AdaEvolve	33,907	1.52	14%
one sample	4,064–6,050	1.0	24–47%

Table 1: Cost of one proposal, averaged over tasks, against the cost of one independent sample. Reasoning tokens are a share of the total. The sample column is a range because it varies by task.

Figure 1: Tokens per proposal, by method and task, with the independent sample cost as the dashed line. Equal-proposal comparisons yield equal compute only if these bars match, which they do not: the same method varies by up to

2.4\times

across tasks, and within a task the methods differ by up to

1.9\times

. The distance to the dashed line (

4.6\times

7.2\times

) is why a sampling baseline run at equal proposals is given far less compute than the compared methods.

Task	Method	prop.	tok.	cut
		evolve / sampling
Heilbronn	EvoX	1.33	1.28	13%
Heilbronn	OpenEv.	1.31	1.27	10%
Heilbronn	AdaEv.	1.32	1.23	27%
Cloudcast	AdaEv.	1.06	1.05	27%
Cloudcast	EvoX	1.05	1.05	7%

Table 2: Evolution divided by independent sampling at equal proposals (prop.) and at equal tokens (tok.), the latter at the largest budget the sampling pool supports. The italic entry has an interval spanning parity. The cut column is how much advantage above parity disappears between them,

(\text{prop.}-\text{tok.})/(\text{prop.}-1)

; it exceeds

100\%

when the advantage does not merely shrink.

\dagger

audited by re-execution: each seed is credited only with its best program placing all transactions, and three seeds whose entire upper archive is the exploit are dropped.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 2: Best score against tokens spent. Solid lines are evolutionary search, one per method, each at its own best number of seeds for that budget. Cloudcast is shown with its coverage gate applied to both sides, and with the two cells whose ceiling misreported its transfer price capped at their best valid program. The dashed line is independent sampling, which at the same budget gets five to seven times more attempts, depending on the task. The transaction scheduling curves are shown after the audit: each seed is capped at the best program that places all 300 transactions and the three exploit seeds are dropped, so that panel tops out near 4,400 rather than 21,277. The range stops where the sampling pool stops, so nothing is extrapolated.

Task	Strategy	gpt-5-mini	Haiku	calls
		tokens / proposal
Circle	OpenEv.	22,813	13,544	1.14
Circle	EvoX	23,920	23,177	1.61
Circle	AdaEv.	37,573	36,444	1.38
Heilbronn	OpenEv.	17,990	19,645	1.84
Heilbronn	EvoX	22,265	19,275	1.62

Appendix

Table 3: Cost of one proposal on both backbones, averaged over the 40 seeds of each cell. The calls column is model calls per proposal on Haiku.

Task	Strategy	prop.	tok.	cut
		evolve / sampling
Heilbronn	AdaEv.	1.34	1.26	25%
Heilbronn	EvoX	1.31	1.25	19%
Heilbronn	OpenEv.	1.26	1.17	35%
Circle	EvoX	1.07	1.07	1%
Circle	AdaEv.	1.07	1.06	2%

Appendix

Table 4: Haiku 4.5 evolution divided by Haiku independent sampling: equal proposals (prop.) against equal tokens (tok.), the latter at the largest budget each pool supports, 37.2M and 24.6M tokens. All six Haiku cells are 40 seeds by 200 iterations. The split is the same one the main text finds on gpt-5-mini, Heilbronn rewarding search and circle packing barely doing so, which is why we claim it as a property of the task and not of the model.

Figure 3: Tokens for one proposal on Haiku 4.5, by strategy and task, with the cost of one independent Haiku sample as the dashed line. All six cells are complete at 40 seeds by 200 iterations.

Task	Method	gemini	gpt-5-mini	ratio	calls	reasoning
		tokens per proposal
PRISM	OpenEv.	16,849	16,252	1.04	1.17	43%
PRISM	EvoX	23,524	15,611	1.51	1.48	42%
PRISM	AdaEv.	65,437	26,713	2.45	2.23	35%
Cloudcast	OpenEv.	23,600	24,937	0.95	1.27	35%
Cloudcast	EvoX	57,573	35,879	1.60	3.83	62%

Appendix

Table 5: Cost of one proposal on gemini-2.5-flash , beside the same nine cells on gpt-5-mini . Calls and reasoning are the gemini figures.

Task	Method	prop.	tok.	cut
		evolve / sampling
Cloudcast	AdaEv.	1.61	1.59	3%
Cloudcast	OpenEv.	1.58	1.55	5%
Cloudcast	EvoX	1.53	1.53	0%
Txn	EvoX	1.25	1.25	0%
Txn	AdaEv.	1.27	1.25	6%

Appendix

Table 6: Gemini evolution divided by gemini independent sampling, built as Table 2 and audited the same way.

Figure 4: Tokens for one proposal on gemini-2.5-flash , by method and task, with one independent sample as the dashed line. The companion to Figure 1 .

Figure 5: Best score against tokens spent on gemini-2.5-flash , one panel per systems task, with the same gates and audits as Figure 2 .

Task	Method	tok.	95% CI
Heilbronn	EvoX	1.28	1.24–1.36
Heilbronn	OpenEv.	1.27	1.17–1.34
Heilbronn	AdaEv.	1.23	1.19–1.30
Cloudcast	AdaEv.	1.05	1.04–1.19
Cloudcast	EvoX	1.05	1.03–1.18
Circle	EvoX	1.04	1.04–1.04

Appendix

Table 7: Equal-token ratios from Table 2 with their

95\%

intervals. PRISM’s lower bounds are

1.0009

and round to

1.00

. Only Cloudcast with OpenEvolve spans parity.

		evolve / sampling
Task	Method	prop.	calls	tok.
Heilbronn	EvoX	1.33	1.33	1.28
Heilbronn	OpenEv.	1.31	1.31	1.27
Heilbronn	AdaEv.	1.32	1.29	1.23
Cloudcast	AdaEv.	1.06	1.06	1.05
Cloudcast	EvoX	1.05	1.05	1.05

Appendix

Table 8: The same fifteen pairs at three budget definitions. Transaction scheduling and Cloudcast are audited as in Table 2 . Switching from proposals to calls changes almost nothing; switching to tokens is what moves the comparison and what matters.

Figure 6: Tokens for one model call, by method and task, with the cost of one independent sampling call as the dashed line. If a call were a unit of compute this would be flat.

Task	Accepted despite	Degenerate	Effect
Txn	3 of 300 placed	3/120	$5.06\!\rightarrow\!1.02$
Cloudcast	no partitions sent	2/113	$<0.1\%$
Cloudcast	price misreported	2/113	$1.08\!\rightarrow\!1.05$
PRISM	2% of requests served	22/120	gated out
Circle	nothing	0/120	control
Heilbronn	nothing	0/120	control

Appendix

Table 9: What each scorer accepts, how often it happens, and what removing it costs. The Degenerate column counts seeds whose own best program fails a direct coverage check, out of the seeds we re-executed; both Cloudcast rows rest on the same 113, because seven of its winners cannot be re-run at all. Circle packing and Heilbronn accept nothing because their evaluators validate the output themselves, the latter rejecting any result that does not place every point inside the triangle. The Effect column is the change to Table 2 : transaction scheduling loses its headline, Cloudcast is unaffected by the two that send no partitions because neither ever led, but one of the two that misreport their price was a cell ceiling, and PRISM’s gate excludes its own before they are scored.

LLMs for Evolutionary Optimization

See all 28 papers

Evolution or Illusion? Rethinking Evaluation in LLM Evolutionary Search
Sep 17, 2026Tal Oved, Roi Pony, Oshri Naparstek +1Evolutionary Optimization Large Language Model-Guided Optimization
IBM Research
Compute Allocation in Evolutionary Search: From Depth-Breadth to Multi-Armed Bandits
May 28, 2026Sixue Xing, Haoyu He, Kerui Wu +4Multi-Armed Bandits Evolutionary Optimization
University of Notre Dame · 2Northeastern University · University of Massachusetts Amherst +4
Relay, Don't Route: Adaptive Population Handoff for Cost-Efficient LLM-Driven Evolution
Aug 6, 2026Sichun Luo, Yi Huang, Guanzhi Deng +6Multi-Fidelity Optimization Evolutionary Optimization
1The University of Hong Kong · 2JIUTIAN Research, China Mobile · 3City University of Hong Kong +1

Sep 17, 2026J/K move · Enter open · S save

Evolution or Illusion? Rethinking Evaluation in LLM Evolutionary Search

Tal Oved, Roi Pony, Oshri Naparstek, Udi Barzelay

IBM Research

Evolutionary Optimization Large Language Model-Guided Optimization

Open paper AskPDF arXiv

LLM-driven evolutionary search finds programs by launching seeds and iterating each one. Papers report a single budget setting, usually one seed run for a fixed number of iterations, and rank methods from that one point. We show this is not enough. We evaluate three evolutionary search strategies on five optimization tasks, commonly used by papers in the genre to report results. We run the analysis over a full grid of seeds and iterations. Our findings suggest that the best way to split a fixed budget between more seeds (width) and more iterations (depth) changes with the strategy, the task, and the total budget. Furthermore, we observe that the ranking of strategies also changes with the budget. On one task the strategy that looks worst at one seed is best at forty seeds. On another the best number of iterations is well below the value common in practice, so extra depth wastes budget that more seeds would turn into score. We provide a measurement protocol that reports the seeds-by-iterations frontier and practical guidance for using it.

Abstract

LLMs for Evolutionary Optimization

Explore similar work

Evolution or Illusion? Rethinking Evaluation in LLM Evolutionary Search

Compute Allocation in Evolutionary Search: From Depth-Breadth to Multi-Armed Bandits

Relay, Don't Route: Adaptive Population Handoff for Cost-Efficient LLM-Driven Evolution