Source-linked AI summary
What Makes an LLM a Good Optimizer? A Trajectory Analysis of LLM-Guided Evolutionary Search
Xinhao Zhang, Xi Chen, François Portet, Maxime Peyrard
TL;DR
LLM-guided evolutionary systems can differ substantially in optimization despite similar zero-shot capability, but the mechanisms behind these differences remain unclear. This study analyzes trajectories across tasks and models, finding that strong optimizers act as local refiners and that novelty helps only within localized, promising search regions.
Problem
Different LLMs produce markedly different optimization trajectories and final performance even under controlled evolutionary settings, and zero-shot capability only partly explains these differences.
Method
The study analyzes the geometry and trajectories of LLM-guided evolutionary search across multiple models and tasks, including route and prompt optimization.
Results
Strong LLM optimizers progressively localize search around high-performing regions and make frequent incremental improvements, whereas higher novelty is not systematically associated with better outcomes.
Takeaways & Limitations
Effective LLM optimization depends on controlling refinement behavior through model selection and system-level choices such as prompting and decoding, rather than maximizing base-model capability alone.
Takeaways & Limitations
The experiments use a fixed evolutionary protocol, operationalize novelty primarily as nearest-neighbor distance, and do not fully isolate local refinement in the perturbation intervention.
Abstract
from arXiv · showhide
Recent work has demonstrated the promise of orchestrating large language models (LLMs) within evolutionary and agentic optimization systems. However, the mechanisms driving these optimization gains remain poorly understood. In this work, we present a large-scale study of LLM-guided evolutionary search, collecting optimization trajectories for 15 LLMs across 8 tasks. Although zero-shot problem-solving ability correlates with final optimization outcomes, it explains only part of the variance: models with similar initial capability often induce dramatically different search trajectories and outcomes. By analyzing these trajectories, we find that strong LLM optimizers behave as local refiners, producing frequent incremental improvements while progressively localizing the search in semantic space. Conversely, weaker optimizers exhibit large semantic drift, with sporadic breakthroughs followed by stagnation. Notably, various measures of solution novelty do not predict final performance; novelty is beneficial only when the search remains sufficiently localized around high-performing regions of the solution space. Our results highlight the importance of trajectory analysis for understanding and improving LLM-based optimization systems and provide actionable insights for their design and training.
1 Introduction
The paper asks why LLMs with similar initial capability produce different optimization outcomes and studies their trajectories to identify the underlying search behaviors.
- LLMs are increasingly used as black-box search operators that iteratively propose candidates, receive feedback, and refine solutions.
- 15 LLMs were studied across 4 task families and 8 tasks, yielding 72K analyzed candidate solutions.
- Zero-shot performance correlates with final optimization outcomes but explains only part of the variance, as similarly capable models can follow distinct trajectories.
- Successful trajectories feature frequent, sustained incremental breakthroughs rather than simply high novelty.
- Strong optimizers progressively localize search around high-performing semantic regions, whereas weak optimizers diffuse and drift.
- The study characterizes effective LLM optimizers as local refiners and suggests training and controlling search operators for refinement and error correction.
2 Related Work
Prior work integrates LLMs into evolutionary and iterative optimization, while this paper shifts attention from end outcomes toward the search behaviors and trajectories that produce them.
- LLMs are increasingly integrated into evolutionary computation to generate candidate solutions and heuristics within optimization frameworks.
- Trajectory analyses and behaviour-space studies connect effective optimization with sustained improvement and increased exploitation.
- Recent benchmarks evaluate LLMs as search operators in iterative or evolutionary loops guided by external feedback.
- Outcome-centric evaluation does not fully distinguish base-model capability from operator effectiveness, motivating specialized search-operator training.
3 Methodology
The methodology evaluates LLM-guided evolutionary search across diverse task families using a shared iterative framework, task-specific genomes and fitness functions, and semantic trajectory measures.
- Framework: LLMs act as semantic variation operators in an iterative evolutionary loop that generates candidates to optimize task-specific fitness.
- Framework: Each task begins with a fixed, shared population of valid genomes and fitness values, followed by evaluation, elite selection, LLM-guided mutation, deduplication, and top-N retention.
- Tasks: The evaluation spans combinatorial, linguistic, symbolic, and algorithmic optimization domains.
- Tasks & Genome Representations: TSP genomes are city permutations scored by inverse total distance, while prompt genomes are textual instructions evaluated with ROUGE-L or SARI on held-out validation data.
- Tasks & Genome Representations: Equation discovery uses candidate symbolic expressions scored by normalized prediction error, and heuristic design evolves priority functions for online bin packing.
- Trajectory Measures: Novelty is measured as minimum task-specific semantic distance from previous solutions, with distances tailored to TSP, prompts, equations, and heuristics.
- Experimental Setup: The study evaluates 15 LLMs for 30 generations per model–task pair, with 10 offspring per generation and two repetitions using the same initial population.
4 Results and Analysis
Across controlled evolutionary searches, zero-shot capability predicts final performance but leaves substantial model-to-model variation unexplained. Strong optimizers act as local refiners that sustain incremental improvements in localized semantic regions, whereas novelty alone is uninformative and weaker refinement degrades outcomes.
- Optimization Gap: Under identical conditions, LLMs produce different long-horizon outcomes, and strong first-generation performance does not reliably predict final gains.Deepseek-V3 performs best initially but does not achieve the largest gains over time.
- Base Model Capability: Zero-shot performance is strongly correlated with post-optimization performance but is insufficient to explain long-horizon success.Models with nearly identical zero-shot performance can diverge substantially after evolution.
- Novelty vs. Breakthrough Dynamics: Novelty-based measures have near-zero, non-significant coefficients and negligible explanatory power for final optimization performance.Increasing diversity alone does not improve optimization outcomes.
- Novelty vs. Breakthrough Dynamics: Breakthrough rate has the largest positive coefficient and explains around two times more variance than zero-shot capability.Combining breakthrough rate with zero-shot performance increases explanatory power further, while the zero-shot coefficient decreases.
- Trajectory Geometry: Strong optimizers progressively localize search and produce sustained best-so-far improvements, while weaker optimizers drift semantically and stagnate.Gemini-1.5-Pro localizes into a smaller semantic region, whereas Mistral-7B-Instruct drifts across distant regions.
- Operator-Level Validation: Performance depends on reliable incremental refinement rather than large semantic changes, and injecting weaker refiners reduces refinement rates and performance.Larger edits reduce refinement reliability; increasing weak-refiner offspring sharply and monotonically degrades performance on TSP60 and bin packing.
5 Discussion and Conclusion
LLM-guided evolution changes the exploration–exploitation balance through structured, semantically meaningful mutations, making refinement behavior more important than base capability alone. Strong operators localize search around promising regions, while novelty helps only under localized search conditions.
- Zero-shot performance correlates with final optimization outcomes but explains only part of the variance across LLM-guided searches.
- LLM-generated mutations are structured and semantically meaningful rather than fully random, biasing evolutionary search toward exploitation.
- Higher novelty is not systematically associated with better outcomes and can signal ineffective operators that drift without refining promising solutions.
- Strong LLM operators progressively localize trajectories around high-performing regions while producing frequent, incremental improvements.
- Refinement behavior emerges from the full agentic system, including the model, prompting strategy, and decoding configuration, rather than from the base model alone.
- System design can prioritize refinement behavior through model selection, prompting, decoding, and training focused on local refinement and error correction.
- The geometric trajectory-analysis framework can also be repurposed for other iterative search and agentic behaviors.
Limitations
The study’s conclusions are bounded by its fixed evolutionary protocol, narrow novelty operationalization, and difficulty isolating refinement in model-mixing interventions.
- The fixed evolutionary protocol leaves selection pressure, offspring size, and alternative sampling strategies as possible influences on cross-model differences.
- Novelty is primarily measured by nearest-neighbor distance, so robustness to KNN, average-distance, and other diversity indices remains unassessed.
- Model-mixing interventions may alter reasoning patterns or exploration tendencies, making performance differences difficult to attribute solely to local refinement.
A Complete Experimental Result
AI tools assisted with writing, editing, and code development while the authors retained responsibility for the paper’s content, ideas, and decisions.
- AI tools were used to assist in writing, editing, and code development.
- The authors provided all content, ideas, and decisions.
- AI use was limited to improving clarity, readability, and efficiency.
C Task-Specific Experimental Details
The experimental details specify task-specific evolutionary settings, genome validity and fitness rules, novelty measures, prompts, and reporting conventions across the evaluated task families.
- Prompts: Evolution prompts provide parent solutions and scores, ask the LLM to generate improved offspring, and use task-specific templates across the task families.
- Evolutionary Protocol: The common evolutionary loop initializes valid genomes with fitness, samples parents proportionally to fitness, generates offspring conditioned on parents, deduplicates them, and retains the top-N pool.
- TSP: TSP evolution uses 40 initial genomes, three sampled parents, ten offspring per generation, a pool capacity of 40, and 30 generations.
- TSP: TSP experiments use permutation genomes for 30 or 60 cities, with invalid or unparsable outputs receiving zero fitness and being excluded from parent sampling.
- TSP: TSP fitness is the negative tour length, while novelty uses canonized edge-set distance that ignores tour rotation and starting city.
- Prompt Optimization: Prompt-optimization experiments treat nonempty natural-language strings as valid genomes and evaluate them with ROUGE-L for SAMSum or SARI for ASSET.
- Reporting: Reported cells average normalized fitness across two subtasks and two seeds, with shading based on improvement relative to each task’s initial-population best.
C.4.1 Zero-shot Evaluation Details
The study evaluates each model–task pair under six decoding temperatures, using two runs per temperature.
- Six temperature settings were sampled for every model–task pair, with two runs at each setting.
C.4.2 Task-agnostic Novelty Computation
The paper computes task-agnostic novelty from semantic distances to prior candidates and projects task-specific distances into two-dimensional trajectory landscapes. Large datasets use sampled MDS fits with k-NN interpolation for out-of-sample points.
- Novelty is the minimum semantic distance to prior candidates within the same problem instance, normalized across generations.
- Task-specific novelty distances are projected into two-dimensional embeddings to visualize optimization trajectories across four task families.
- Datasets exceeding 4,000 genomes use stratified sampling to fit a base MDS representation, followed by out-of-sample placement.
- Out-of-sample points use k = 8 nearest neighbors with inverse-distance weights wi = 1/(di + 10^-8)^p, where p = 2.0.
- The interpolation is vectorized in blocks of 4,000 points and is intended to preserve high-dimensional neighborhood structure.
D.1 Temperature-Sensitivity Experiment
The temperature-sensitivity experiment tests whether the relationship between local refinement and optimization success depends on decoding stochasticity. Across the tested range, the paper reports that this relationship remains robust.
- Eight temperatures from T = 0.0 to T = 1.3 were tested on TSP and Oscillator using Mistral-7B and Mistral-24B.
- Local refinement remained a key driver of optimization success across substantial decoding-temperature variation.
- The refinement–performance relationship remained consistently positive across temperature settings.
- On TSP, the refinement–fitness correlations were particularly strong while performance itself varied with temperature.
E Statistical Model Specifications
The paper uses OLS and mixed-effects models to test whether novelty, breakthrough frequency, and trajectory geometry explain optimization outcomes. Breakthrough frequency is strongly predictive of final performance, while novelty alone has weak explanatory power and temporal prediction remains noisy.
- OLS Regressions: Breakthrough rate measures the fraction of generations achieving a best-so-far improvement.
- OLS Regressions: OLS models predict normalized best final fitness from zero-shot capability, novelty measures, breakthrough rate, and task fixed effects.
- OLS Regressions: Novelty metrics have weak explanatory power, whereas breakthrough-rate metrics strongly predict final evolutionary performance.
- Mixed-Effects Regression Models: Generation-level GLMMs model breakthrough probability using concurrent predictors or current-generation predictors of next-generation breakthroughs.
- Mixed-Effects Regression Models: The lagged model has residual variance 0.662 versus 0.780 for the concurrent model, indicating some temporal structure but substantial noise.
- Mixed-Effects Regression Models: The novelty–spatial-entropy interaction is the strongest signal across concurrent and lagged timescales.