Self-Improving Language Models with Bidirectional Evolutionary Search | Summary

Contents

Summary
1 Introduction
2 Preliminaries
3 BES: Bidirectional Evolutionary Search
4 Theoretical Motivations
- 4.1 Theoretical Motivation for Evolution Operators
- 4.2 Theoretical Motivation for Bidirectional Search
5 Experiments
6 Related Work
7 Conclusion
Appendix
Brief Thoughts

This article explains the key points of Self-Improving Language Models with Bidirectional Evolutionary Search.

2026-05-27 (arXiv), Preprint
Xu, Guowei, Qi, Zhenting, Su, Huangyuan, Ye, Weirui, Lakkaraju, Himabindu, Kakade, Sham M., Du, Yilun.
Harvard University, MIT
Paper
Github
Project Page

Summary

Self-Improving Language Models with Bidirectional Evolutionary Search introduces BES, a sampling framework for post-training and inference. It combines forward trajectory expansion and recombination with backward decomposition into verifiable sub-goals, addressing rare-solution discovery and sparse terminal feedback.
BES improves logical-reasoning post-training and raises MuSiQue accuracy from 4.0% to 7.0% for Llama-3.2-3B-Instruct and from 6.6% to 10.4% for Llama-3.1-8B-Instruct. On three GPT-5 program-search benchmarks, it achieves the highest mean objective values among the evaluated open-source frameworks, although its best Heilbronn result ties OpenEvolve and GEPA at the reported precision.
The theory motivates recombination through increased trajectory surprise and backward verification through sub-goal collection sample complexity. It does not establish that atypical candidates are better solutions or that complementary evidence can always be recombined successfully. Evaluation is limited by task-specific verification heuristics, small post-training models, unmatched generation-call budgets in logical reasoning, and three inference runs per benchmark.

1 Introduction

The paper studies sampling near the boundary of model capability, where correct trajectories may be too rare for ordinary rollouts to supply useful training data or reliable inference answers. Best-of-N sampling and tree search construct candidates primarily through sequential expansion, while binary or coarse terminal rewards provide little guidance before a complete solution is found.

BES separates candidate construction from progress assessment: forward evolution combines fragments across trajectories, while backward search exposes intermediate goals.
Figure 1 illustrates the intended distinction between ordinary expansion and recombination-guided exploration. Its reachable regions are conceptual, not measured solution-space coverage.
Code and trained models are provided at https://github.com/Embodied-Minds-Lab/BES.

Conceptual comparison of sequential tree expansion with forward evolution and backward goal decomposition in BES.

2 Preliminaries

A task consists of a problem description x and a verifier V(x, y) ∈ [0, 1]. The objective is to maximize verifier score over valid terminal responses under the task specification and resource budget, using a policy πθ to construct candidates.

Best-of-N draws independent trajectories from the same policy and returns the highest-scoring one; it can miss solutions assigned very little probability.
Tree search concentrates computation on promising prefixes through beam search, best-first search, or Monte Carlo Tree Search, but constructs each terminal response through a single sequence of extensions.

3 BES: Bidirectional Evolutionary Search

BES maintains a pool of partial trajectories and alternates forward candidate generation with backward goal refinement. New candidates receive recursive sub-goal scores, and refining the goal tree triggers re-scoring of existing candidates so that subsequent selection uses the updated feedback.

The general algorithm performs backward decomposition after several forward steps; the experimental implementations adapt this schedule to the task.
Evolution permits candidates to have multiple contributing parents rather than requiring one uninterrupted rollout lineage.

3.1 Forward Search: Expanding the Reachable Solution Space

Forward search uses expansion plus four evolution operators: combination concatenates distinct suffixes beyond a common prefix, deletion removes an interior step, translocation replaces one step with a donor step, and crossover joins a prefix to another trajectory’s tail. Expansion samples K uniformly from {1, …, Kmax} and appends up to K policy-generated steps.

Single-parent selection uses a Boltzmann distribution over backward scores, with λ = 0.1 added to nodes that have not yet produced children.
Two-parent selection uses joint sub-goal coverage rather than simply selecting the two individually highest-scoring candidates, favoring complementary parents.
Selection temperature decreases linearly over the budget. Direct edits need not improve quality or preserve coherence; executable-program experiments instead implement the operators through LLM prompts.

Expansion, combination, deletion, translocation, and crossover on step-sequence trajectories.

3.2 Backward Search: Better Verification through Goal Decomposition

Backward search recursively decomposes the root task into finer goals, each equipped with a local verifier. A leaf that no current candidate fully satisfies is selected for further decomposition, and all forward candidates are then evaluated against the refined tree.

For an internal goal, Eq. (5) blends its verifier score with the average recursive child score using α; leaves use their local verifier directly, and fully satisfied goals short-circuit to 1.
Eq. (6) scores parent pairs by replacing each local verifier output with the maximum across the two parents, measuring their combined coverage.
Verifier implementations can be rule-based checks, executable tests, embedding similarity, or LLM judgments. Their fidelity determines whether dense feedback reflects genuine progress.

The MuSiQue case study asks, “What is the record label of the artist who originally recorded Back to Bedlam?” Backward search separates artist identification from label identification, while translocation combines reasoning from two unsuccessful branches to produce the dataset’s correct answer, Custard Records.

The illustrated partial candidate receives score 0.3, whereas the successful recombination receives 1.0.
This trace illustrates cross-trajectory reuse, not its aggregate success rate or proof that continued expansion could never solve the example.

MuSiQue search trace combining artist and record-label evidence through translocation and backward sub-goal verification.

3.3 Using BES for Post-Training and Inference

For post-training, BES replaces the sample-generation stage and supplies selected trajectories to an existing training algorithm. For inference, it searches within a fixed budget and returns the terminal candidate with the highest original verifier score.

The experiments place BES on top of MaxRL for logical reasoning, GRPO for multi-hop reasoning, and ShinkaEvolve for executable-program search.
BES is a search and sampling component, not a standalone parameter-update rule.

4 Theoretical Motivations

The theoretical motivations address two questions: whether recombination reaches trajectories unlikely under ordinary policy sampling, and whether intermediate verification reduces the samples needed to collect useful partial evidence. The analyses use idealized trajectory distributions and sub-goal events rather than directly modeling the complete experimental system.

4.1 Theoretical Motivation for Evolution Operators

Theorem 4.4 assumes bounded per-step surprise, summably decaying influence on future conditional entropy, and block total correlation at least γT. The analysis shows concentration of policy-rollout surprise around trajectory entropy HT and an increase of at least γT in expected native surprise when blocks are independently recombined from their marginals.

The typical set is Aϵ^(T) = {y : |−log P(y) − HT| ≤ ϵT}, with size at most exp(HT + ϵT). For ϵ < γ, the stated probability bound gives positive mass outside this set if the finite-surprise bound also holds for recombined candidates.
Appendix C derives the surprise increase as total correlation plus DKL(Q∥P). If recombination produces candidates outside P’s support, their native surprise is infinite and the proof’s upper bound LT is not justified.
Increased surprise does not imply higher verifier score. Concentration for Y ∼ P also does not establish confinement for every adaptively selected tree-search output.

4.2 Theoretical Motivation for Bidirectional Search

Theorem 4.5 compares terminal success with collecting evidence for m leaf sub-goals. With independent sub-goal satisfaction probabilities pi and independently sampled candidates, terminal-only search needs Ω(1/∏i pi) candidates for constant success probability, whereas collecting at least one satisfying candidate for every sub-goal needs O(pmin⁻¹ log(m/δ)) candidates for probability at least 1 − δ.

When pi = p, the stated ratio is Ω(p⁻(m−1)/log(m/δ)), exponential in the number of sub-goals for fixed p < 1.
The backward bound concerns coverage across the candidate pool. Producing a complete solution additionally requires compatible partial trajectories and successful recombination, which the bound does not quantify.
Real multi-hop goals can be dependent; the experimental verifier checks them sequentially rather than assuming independent satisfaction.

5 Experiments

The evaluation covers logical reasoning with an LLM, multi-hop retrieval reasoning with an agent, and executable-program search for three geometric optimization problems. Post-training experiments target settings where baseline algorithms show limited improvement or degrade, while inference experiments compare objective values under a shared GPT-5 API-spend cap.

5.1 Bidirectional Evolutionary Search for Post-Training

5.1.1 Logical Reasoning uses Knights-and-Knaves with Gemma-3-1B-it. All methods start from 3 epochs of SFT on 1,000 problems, followed by 4 epochs of post-training on 5,000 problems; the validation set contains 1,287 problems spanning 2–10 people.

BES supplies samples to MaxRL and is compared with GRPO and MaxRL using independent rollouts. Figure 3 shows the largest validation improvement for BES; GRPO ends near its initial performance, while MaxRL improves modestly.
Each BES search permits 200 policy calls and targets eight unique terminal trajectories, padding missing slots with ordinary rollouts. Baselines draw eight independent trajectories, so this comparison does not isolate search structure at equal generation-call cost.
Because Gemma-3-1B-it cannot reliably construct open-ended decompositions, backward search uses a predefined verification-strategy tree and asks the model to schedule its traversal.

EMA-smoothed Knights-and-Knaves validation performance for GRPO, MaxRL, and BES.

Model, optimization, generation, and search hyperparameters for Knights-and-Knaves.

5.1.2 Multi-Hop Reasoning uses the answerable 3–4-hop MuSiQue training subset and the full official validation set. Llama-3.2-3B-Instruct and Llama-3.1-8B-Instruct are post-trained for 2 epochs with an offline Wikipedia retriever; the paper reports that additional epochs lead to training collapse.

For the 3B model, base, GRPO, Tree-GRPO, and BES accuracy are 4.0%, 2.1%, 3.9%, and 7.0%, respectively. For the 8B model, they are 6.6%, 5.6%, 7.4%, and 10.4%.
BES finish ratios are 0.97 and 0.94, compared with 0.64 and 0.71 for Tree-GRPO. BES also records 2.31 and 2.11 valid searches and 3.29 and 3.05 valid actions.
The authors attribute GRPO degradation to search-skipping reward hacking. The reported search counts are consistent with this interpretation but do not independently establish the causal mechanism.

MuSiQue post-training accuracy, valid searches, valid actions, and finish ratios for 3B and 8B Llama backbones.

Training, generation, retrieval, and BES search hyperparameters for MuSiQue.

5.2 Bidirectional Evolutionary Search for Inference

Inference experiments add BES to ShinkaEvolve’s archive of executable Python programs, using gpt-5 with reasoning_effort = high. Each run is capped at $50 of API spend, and means, standard deviations, and best values are reported across 3 runs per benchmark; baseline results are imported from SkyDiscover under the stated matching configuration.

Appendix D specifies n = 26 square circle packing with the sum of radii as the objective, rather than a shared maximum radius. Heilbronn uses n = 13 points; Appendix G describes minimizing over triangle areas with convex-hull-area normalization, which differs from the unit-square description in Appendix D.
The rectangle specification is also inconsistent: Appendix D describes a fixed-aspect container, whereas Appendix G describes n = 21 circles in a perimeter-4 rectangle with aspect ratio optimized.
Backward refinement is triggered after 5 generations without an objective improvement of at least 10⁻². Raw-objective buckets at precision 10⁻² determine ranking across buckets, with backward scores used within a bucket; this does not preserve ordering between all distinct raw scores in the same bucket.

GPT-5 program-evolution, archive, operator, and backward-tree settings for open problem solving.

BES reports mean ± standard deviation and best values of 2.623 ± .014 and 2.632 for square packing, 2.349 ± .012 and 2.360 for rectangle packing, and 0.026 ± .001 and 0.027 for Heilbronn. These are the highest means among the evaluated open-source frameworks in Table 2, with lower reported standard deviations than every listed open-source baseline.

The strongest competing square mean is GEPA’s 2.613 ± .022; the strongest competing rectangle mean is ShinkaEvolve’s 2.335 ± .026.
BES strictly improves the open-source best values for both packing tasks, but its Heilbronn best value of 0.027 ties OpenEvolve and GEPA at the reported precision.
All BES best values remain below the listed human and AlphaEvolve references. AlphaEvolve uses substantially more compute, so its reference row is not a budget-matched comparison.

GPT-5 program-search objective values, including three-run means, standard deviations, best values, and higher-compute reference results.

5.3 Ablation Study

The Knights-and-Knaves ablation removes either MaxRL answer reweighting or the evolution operators from the full method. Figure 4 shows lower final performance for both reduced variants than for full BES, supporting contributions from answer reweighting and trajectory evolution in this setup.

The reported ablation does not separately remove backward decomposition or isolate combination, deletion, translocation, and crossover individually.
It therefore does not establish that every search component is independently necessary.

Knights-and-Knaves ablations of answer reweighting and evolution operators.

5.4 Cost Analysis

For Llama-3.2-3B-Instruct MuSiQue post-training, median wall-clock time per step is 64 s for GRPO, 240 s for Tree-GRPO, and 309 s for BES. BES adds less than 30% over Tree-GRPO while increasing accuracy from 3.9% to 7.0%.

GRPO’s lower runtime accompanies only 0.84 valid searches and 2.1% accuracy, whereas BES performs 2.31 valid searches. The runtime comparison therefore includes agents exhibiting different amounts of retrieval behavior.
The measurements are per-step medians, not a complete accuracy-versus-total-compute scaling study.

Table 4 reports API costs of $18.6, $14.0, and $13.7 for BES, compared with $13.0, $11.9, and $11.5 for ShinkaEvolve on square packing, rectangle packing, and Heilbronn, respectively. BES obtains higher mean objective values in all three comparisons but uses more reported API spend.

The caption labels these as average API cost per generation, while Appendix D separately sets a $50 cap per run; the paper does not explain how these reporting units relate.
These results show a quality–cost trade-off rather than equal realized expenditure.

Open-problem objective values and reported average API cost per generation for ShinkaEvolve and BES.

The related-work discussion connects BES to self-training and output refinement, search-generated post-training data, inference-time reasoning search, evolutionary program search, and classical heuristic and genetic search. BES combines complementary-parent recombination with an explicitly refined tree of verifiable goals.

STaR, Self-Refine, Reflexion, and Voyager exemplify improvement through filtered outputs, revisions, reflections, or accumulated skills.
Tree-GRPO, TreeRL, ReST-MCTS*, and related methods motivate search-generated training data; AlphaEvolve and ShinkaEvolve provide the closest program-evolution context.
Classical connections include heuristic guidance in A* and bidirectional search, pruning in branch-and-bound, and population-based optimization in genetic search and differential evolution.

7 Conclusion

The paper concludes that forward evolution and backward verification improve search-generated samples for post-training and inference. The experiments support gains on the evaluated objective-reward tasks, while the theory gives conditional explanations for broader exploration and more efficient collection of partial evidence.

Appendix

A Pseudo Code and B Formal Definitions of Evolution Operators specify pool updates, Boltzmann parent selection, recursive scoring, and periodic decomposition of a randomly selected unsolved leaf. The general algorithm returns a fully verified terminal candidate when found, otherwise the best terminal candidate at budget exhaustion; post-training implementations additionally collect trajectory groups.
C Theoretical Motivations expands C.1 Theoretical Motivation for Evolution Operators through C.1.1 Discussion of Assumptions, C.1.2 Shell Confinement of Expansion, and C.1.3 Shell Escape via Evolution. It uses martingale concentration for rollout surprise and KL identities for independently spliced blocks; C.2 Theoretical Motivation for Bidirectional Search applies a union bound to missing sub-goal evidence.
D Detailed Experimental Setup begins with D.1 Logical Reasoning, which uses 2 H200 trainer GPUs and an auxiliary decomposition server. Paragraph-level operators have probabilities 0.70 for expansion, 0.10 for combination, 0.05 for deletion, and 0.075 each for translocation and crossover; temperature decreases from 2.0 to 1.0, decomposition scheduling occurs every 10 steps, and α = 0.3. Table 5 lists AdamW with learning_rate = 1×10⁻⁶, train_batch_size = 32, group_size = 8, and search_budget = 200 policy calls/problem; strategy leaves use syntactic reasoning-marker checks rather than logical proof verification.
D.2 Multi-Hop Reasoning uses 2 H200 trainer GPUs, an E5 + FAISS retriever over the 2018 Wikipedia dump, and a Llama-3.1-8B-Instruct decomposition server. Operators edit complete reasoning/search/information triples, using the same probability mixture as logical reasoning, temperature 1.5 to 0.3, α = 0.7, and 50 policy calls/problem with K-parallel = 4. A sub-question is covered when a search query reaches cosine similarity at least 0.6 in all-MiniLM-L6-v2 space, conditional on earlier sub-goals being covered; this measures query alignment rather than factual completion.
D.3 Open Problem Solving runs on a single CPU node with API-based LLM access. Table 7 specifies num_generations = 100, archive_size = 40, num_islands = 1, at most 2 concurrent evaluation and proposal jobs, maximum goal-tree depth 2, and recursive_blend_α = 0.3. Generated leaf verifiers are Python expressions returning partial-progress scores, and objective-bucket interpolation prevents backward feedback from moving a program above a higher raw-objective bucket.
E Case Study presents the Back to Bedlam search trace discussed in the main review: two unsuccessful branches contribute complementary reasoning, and translocation yields Custard Records. The example illustrates nonzero intermediate feedback and cross-trajectory reuse but supplies no aggregate success-rate evidence.
F Prompts for Open Problem Solving Tasks includes F.1 Backward Search: Goal Tree Decomposition and F.2 Forward Evolution Operations, with Combination, Deletion, Crossover, and Translocation prompts. The square decomposition prompt targets sum_of_radii > 2.636 and requests reference properties shared by elites plus aspirational structural properties, each with a single-expression verify_code. Combination adds compatible mechanisms, crossover combines implementations, translocation imports one mechanism, and program-level deletion requests a substantial strategy rewrite after removing limiting components rather than the formal operator’s single interior-step deletion.
G Identified Programs for Open Problem Solving Tasks summarizes the best discovered implementations. G.1 Circle Packing (Square) combines radii projection, active-set LP, simulated annealing, and SLSQP; G.2 Circle Packing (Rectangle) uses deterministic multi-start layouts followed by fixed-aspect and free-aspect SLSQP stages. G.3 Heilbronn (Convex) uses a C3-symmetric 13-point construction with 8 parameters and Coordinate Pattern Search, evaluating all 286 triangles and normalizing by convex-hull area.
H Potential Limitations and Broader Impacts acknowledges dependence on objective rewards, weak-model decomposition limitations, and post-training experiments restricted to models up to 8B parameters. The authors suggest potential reasoning and interpretability benefits while noting that stronger search could improve capabilities usable for harmful tasks; the paper does not measure environmental savings or downstream misuse.

Brief Thoughts

BES makes complementary partial progress operational: pair selection rewards coverage across parents, and the MuSiQue results show gains in answer accuracy and completed agent behavior. Verifier validity remains a central limitation. Syntactic reasoning markers and semantically aligned queries can guide exploration without certifying that a sub-problem was solved correctly.

The theory is motivation rather than a general guarantee for BES: a finite vocabulary does not imply the appendix’s claimed bound L = log |V| on every token’s surprise, and recombination can create incompatible or zero-probability block combinations unless additional support conditions hold. The rollout concentration result also does not directly cover adaptive prefix selection. Equal-call logical-reasoning comparisons, direct backward-search ablations, and more inference runs would help distinguish the proposed mechanisms from additional sampling and run variability.