PaperlayerView exact revision on arXiv

Source-linked AI summary

Self-Improving Language Models with Bidirectional Evolutionary Search

Guowei Xu, Zhenting Qi, Huangyuan Su, Weirui Ye, Himabindu Lakkaraju, Sham M. Kakade, Yilun Du

arXiv:2605.28814v1cs.CL

TL;DR

Existing LLM search methods use sparse verification and autoregressive expansion, limiting feedback and exploration beyond the model’s distribution. BES combines forward evolutionary candidate search with backward decomposition into verifiable subgoals, achieving consistent post-training gains and outperforming open-source frameworks on three inference benchmarks.

  • Problem

    Existing search methods provide sparse verification feedback and primarily autoregressively expand candidates within the model’s distribution.

  • Method

    BES couples forward search with four trajectory evolution operators and backward recursive decomposition into verifiable subgoals.

  • Results

    BES delivers consistent post-training gains and outperforms existing open-source frameworks in average and best-case performance across three open problem-solving benchmarks.

  • Takeaways & Limitations

    BES provides a search framework that broadens candidate exploration and supplies denser intermediate feedback for self-improvement and inference.

  • Takeaways & Limitations

    The theoretical justification relies on bounded per-step surprise, decaying step dependence, and linear block total correlation assumptions.

Abstract

from arXiv · show

Search has been proposed as an effective method for self-improving language models and agentic systems, both for post-training sample generation and for inference. However, widely used methods such as best-of-N sampling and tree search face two fundamental limitations: they are guided by sparse verification signals, and they construct candidates primarily through autoregressive expansion, restricting exploration to regions with substantial model probability mass. To address these, we propose Bidirectional Evolutionary Search (BES), a search framework that couples forward candidate evolution with backward goal decomposition. In the forward search, BES augments standard expansion with evolution operators that recombine partial trajectories to generate candidates that are difficult to obtain from a single model rollout. In the backward search, BES recursively decomposes the original task into checkable subgoals, producing dense intermediate feedback that guides forward search. We provide theoretical motivation showing that candidates generated by expansion-only search are confined to a narrow entropy shell while evolutionary operators can escape it, and that backward search can exponentially reduce the number of required samples to find a correct answer. Experiments show that on challenging post-training tasks where mainstream post-training algorithms fail to improve, BES enables consistent gains, and on three open problem solving benchmarks at inference time, BES outperforms existing open-source frameworks in both average and best-case performance. Code and trained models are available at https://github.com/Embodied-Minds-Lab/BES.

1 Introduction

Best-of-N sampling and tree search are widely used for LLM and agentic-system sampling but suffer from sparse verification and limited exploration beyond the model distribution. BES addresses these limitations through bidirectional subgoal decomposition and evolutionary recombination, enabling gains in challenging post-training settings.

  • Current sampling methods: Best-of-N sampling and tree search dominate post-training, self-improvement, and inference for LLMs and agentic systems.Best-of-N is widely used in post-training and serves as an inference baseline, while tree search supports harder problems.
  • Limitations: Both methods provide sparse verification signals and generate candidates mainly by autoregressive extension, limiting exploration beyond the model’s distribution.Common verifiers often provide binary or coarse-grained feedback, while autoregressive construction confines candidates to a restricted region of the solution space.
  • Bidirectional Evolutionary Search: BES combines forward candidate evolution with backward search that recursively discovers finer-grained, verifiable sub-goals.The forward search seeks better candidate solutions, while the backward search supplies denser intermediate feedback.
  • Bidirectional Evolutionary Search: Evolution operators recombine parts of different trajectories to generate candidates beyond those obtained through single autoregressive rollouts.This mechanism is presented as a way to escape the narrow entropy shell associated with expansion-only search.
  • Evaluation: BES is evaluated in post-training and inference across LLM and agent settings, including challenging logical and multi-hop reasoning tasks.The paper reports that mainstream methods such as GRPO, MaxRL, and Tree-GRPO struggle to find sufficient high-quality training samples in these post-training settings.

2 Preliminaries

The paper formulates reasoning as maximizing a verifier score over valid terminal responses, a goal relevant to both self-improvement training and inference. Because this optimization is intractable on hard problems, practical methods approximate it by searching candidate trajectories.

  • Problem formulation: A reasoning problem is T = (x, V), where x is a problem description and V(x, y) ∈ [0, 1] scores how well trajectory y solves x.
  • Optimization objective: The objective is to produce a valid terminal response y that maximizes the verifier score under the task specification and resource budget.
  • Optimization objective: Finding the optimal response matters during training, where strong candidates support post-training and iterative self-improvement, and during inference, where it is the desired output.
  • Search motivation: The maximization is intractable on hard problems because the policy may assign extremely small probability mass to correct trajectories, motivating candidate search.
  • Best-of-N sampling: Best-of-N sampling draws N independent trajectories from the policy and returns the candidate with the highest verifier score, without requiring structural problem knowledge.
  • Tree search: Tree search decomposes trajectories into sequential steps and expands promising partial trajectories using heuristic values, concentrating computation on selected prefixes.

3 BES: Bidirectional Evolutionary Search

BES alternates forward candidate evolution with backward goal decomposition: it recombines partial trajectories while scoring them against fine-grained sub-goals. This coupling generates diverse candidates and provides dense feedback for selecting promising search nodes.

  • 3 BES: Bidirectional Evolutionary Search: BES alternates forward search for better candidates with backward decomposition into fine-grained sub-goals that evaluate each forward node.The forward process seeks improved candidates, while backward search supplies interpretable intermediate scores.
  • Forward search: The search maintains partial trajectories as nodes and applies expansion or evolution operators to produce scored child nodes added to the candidate set P.Expansion samples new steps from πθ, whereas evolution edits or recombines existing trajectories.
  • Forward search: Evolution restructures trajectories through combination, deletion, translocation, and crossover, enabling candidates that single-rollout expansion is unlikely to reach.Combination joins suffixes beyond a shared prefix; deletion removes an interior step; translocation replaces a step; crossover swaps a trajectory tail.
  • Search control: Node selection uses backward scores, while pair selection favors complementary candidates covering different parts of the goal tree; temperature annealing shifts behavior from exploration to exploitation.Unexplored nodes receive a λ = 0.1 bonus, and the temperature decreases linearly from τ0 to τend < τ0.
  • Backward search: Backward search builds a rooted goal tree whose verifiers score how well each candidate addresses each sub-goal, producing dense feedback before complete solutions exist.A candidate’s overall score recursively combines parent- and child-goal contributions, with fully satisfied goals short-circuited to 1.

4 Theoretical Motivations

The theory shows that expansion-only search remains confined to a narrow entropy shell, whereas evolution operators can escape it. It further shows that backward sub-goal signals make the enlarged candidate space exponentially more searchable than terminal-only search.

  • Shell confinement and escape: Under Assumptions 4.1–4.3, expansion-only trajectories are confined to a typical entropy shell, while evolution operators can escape it.The assumptions impose bounded per-step surprise, decaying step dependence, and block total correlation growing linearly with horizon T.
  • Shell confinement and escape: Expansion-only trajectories leave the typical set with probability at most exp(−Ω(T)), whose size is at most exp(H_T + ϵT).Evolution operators break inter-block dependence and increase expected surprise beyond H_T, pushing candidates outside the shell.
  • Exponential advantage from backward sub-goal signals: Backward search decomposes the task into m leaf sub-goals and supplies intermediate signals for checking them individually.Terminal success requires all leaf sub-goals, while backward-guided search collects evidence for each sub-goal.
  • Exponential advantage from backward sub-goal signals: Terminal-only search requires Ω(1/∏_{i=1}^m p_i) candidates for constant success probability, whereas backward-guided search needs O(…) candidates to collect all sub-goal evidence.The backward-guided bound depends on p_min = min_i p_i and a target failure probability δ.
  • Exponential advantage from backward sub-goal signals: When p_i = p, the terminal-to-bidirectional sample ratio is Ω(…), which is exponential in the number of sub-goals m.This establishes an exponential advantage for backward-guided bidirectional search under symmetric sub-goal probabilities.

5 Experiments

BES improves post-training and inference performance across logical reasoning, multi-hop reasoning, and open problem-solving benchmarks. Ablations and cost analyses further show that its evolution operators contribute to gains while adding limited overhead.

  • Logical Reasoning: BES steadily improves Knights-and-Knaves validation accuracy, whereas GRPO and MaxRL show little to no training improvement.The experiment uses Gemma-3-1B-it, 1K SFT examples, 4 post-training epochs, and a 1.3K validation set.
  • Multi-Hop Reasoning: BES gains +3.0% on 3B and +3.8% on 8B MuSiQue models, outperforming GRPO and Tree-GRPO, which fail to improve consistently.GRPO degrades from the base model, while Tree-GRPO improves only the 8B model by +0.8%.
  • Open Problem Solving: BES outperforms OpenEvolve, GEPA, and ShinkaEvolve on every open problem-solving benchmark and has much lower variance across runs.The comparison uses GPT-5 with matched backbone, compute budget, and configuration for the open-source baselines.
  • Ablation Study: Both removing answer reweighting and removing evolution operators underperform full BES on Knights-and-Knaves, while still outperforming the compared baseline.The ablation tests MaxRL’s answer reweighting and BES’s evolution operators separately.
  • Cost Analysis: BES incurs less than 30% additional overhead versus Tree-GRPO while achieving significantly better performance across all reported multi-hop metrics.GRPO’s lower wall-clock time is misleading because reward hacking causes the model to skip search actions and guess directly.
  • Cost Analysis: BES achieves consistently higher average objective values than ShinkaEvolve across all three open problem-solving benchmarks at modest additional API cost.The inference cost comparison reports average API cost per generation.

6 Related Work

Prior work studies self-improvement through trajectory refinement, self-generated feedback, and search-based training or inference for language models and agents. BES instead frames self-improvement as structured search, drawing on principles from classical search.

  • Self-Improvement for LLM and Agent: Self-improvement methods use model-generated outputs to evolve language models and agents through rationale filtering, output revision, reflections, or reusable skills.STaR filters correct rationales for fine-tuning, Self-Refine revises outputs using self-generated feedback, Reflexion verbalizes environmental feedback, and Voyager accumulates skills through continual exploration.
  • Self-Improvement for LLM and Agent: These approaches typically refine individual trajectories or rely on models to judge their own outputs, whereas BES treats self-improvement as structured search for high-quality solutions.BES is described as systematically discovering solutions that facilitate model self-improvement.
  • Search in LLM and Agent: Search-based methods support both training and inference, including tree-structured exploration, reinforcement-learning integration, and higher-quality training-data generation.Examples include Tree-GRPO, TreeRL, ReST-MCTS*, MCTS-DPO, and rStar-Math.
  • Classical Search Methods: Classical search contributes principles such as heuristic guidance, frontier expansion, search-space reduction, and pruning subtrees certified as suboptimal.The passage identifies A*, bidirectional search, and branch-and-bound as relevant classical precedents.

7 Conclusion … C.1.2 Shell Confinement of Expansion

BES combines forward evolutionary search with backward decomposition and verification to address sparse feedback and confined candidate generation. Its algorithms and theory formalize this bidirectional procedure and show that expansion-only rollouts concentrate within a narrow typical shell.

  • 7 Conclusion: BES couples forward candidate evolution with backward recursive decomposition into verifiable sub-goals, addressing sparse verification signals and confined candidate generation.Forward search uses expansion and four evolution operators, while backward search supplies dense intermediate feedback.
  • A Pseudo Code: The main loop alternates forward search and backward scoring, refining the goal tree every Kdec steps and recomputing pool scores afterward.The procedure continues under a policy-call budget and returns the highest-scoring terminal candidate verified by V.
  • A Pseudo Code: Expansion and deletion select one parent by Boltzmann selection, whereas combination, translocation, and crossover select two parents maximizing joint sub-goal coverage.The five operators are sampled from a fixed distribution during each forward step.
  • A Pseudo Code: Backward scoring assigns 1 to fully satisfied sub-goals and otherwise blends local verifier output with the average score of child sub-goals.Backward decomposition selects an unsolved leaf and prompts the policy to create finer children with local verifiers.
  • C.1 Theoretical Motivation for Evolution Operators: Evolution recombines blocks from different trajectories, making the number of reachable candidates grow as a Cartesian product of per-block libraries rather than a single lineage.This provides the theoretical motivation for using evolution operators alongside autoregressive expansion.
  • C.1.1 Discussion of Assumptions: The analysis assumes bounded per-step surprise, decaying step dependence, and linear block total correlation, conditions argued to fit finite-action policies and coherent sequential reasoning.For finite vocabulary LLMs, bounded surprise gives L = log |V|; linear total correlation follows when each block contributes at least constant mutual information.
  • C.1.2 Shell Confinement of Expansion: With high probability, policy-rollout information content is close to expected entropy, yielding a finite-sample analogue of the asymptotic equipartition property.The result follows by combining concentration bounds for the martingale terms under the stated assumptions and variance condition.
  • C.1.2 Shell Confinement of Expansion: Almost all rollouts occupy a set of size ≈exp(HT), so expansion-only search, regardless of prefix selection, can explore only within this shell.This formalizes the claimed confinement of expansion-only candidate generation.

C.1.3 Shell Escape via Evolution

Evolution operators escape the entropy shell by recombining trajectory segments, with the expected surprise gap governed by dependence among blocks. The theorem contrasts this with expansion-only search, which remains confined to a typical set, while a positive fraction of evolution candidates escape.

  • Crossover evolution: Crossover candidates have expected surprise at least the prefix–suffix mutual information above the policy entropy.The gap is strictly positive whenever the suffix distribution depends on the prefix.
  • Block evolution: k-way block evolution has an expected-surprise gap at least the blocks’ total correlation.The gap additionally includes DKL(Q∥P), where Q is the product of the policy’s block marginals.
  • Shell confinement and escape: Expansion-only trajectories remain in a typical set with probability at least 1 − exp(−Ω(T)), whose size is at most exp(HT + ϵT).The theorem describes this as shell confinement under the stated assumptions.
  • Shell confinement and escape: Evolution candidates have expected log-probability strictly beyond the shell boundary, confirming that a positive fraction escape the shell.The proof derives the expectation lower bound HT + γT from total correlation and DKL(Q∥P).

C.2 Theoretical Motivation for Bidirectional Search

The theoretical motivation shows that backward sub-goal signals provide an exponential sampling advantage over terminal-only search. By collecting evidence for individual subgoals and recombining partial trajectories, bidirectional search replaces a multiplicative hitting problem with sub-goal collection.

  • Exponential advantage from backward sub-goal signals: The resulting ratio N_term/N_bidir is exponential in the number of subgoals m.The theorem contrasts terminal-only sampling with backward-guided bidirectional search.
  • Backward verification and recombination: Backward verification succeeds when the candidate pool contains evidence for every subgoal, after which evolution recombines the corresponding partial trajectories.The pool must contain at least one candidate satisfying each subgoal condition C_i(n) = 1, with probability at least 1 − δ.
  • Backward verification and recombination: Terminal-only search depends on the joint success probability Q_i p_i, whereas bidirectional search exploits the larger local probabilities p_i.This changes the problem from finding a complete solution in one shot to collecting evidence for individual subgoals.
  • Exponential advantage from backward sub-goal signals: Bidirectional search requires only O(p^-1 log(m/δ)) candidates in the symmetric case, versus Ω(p^-m) for terminal-only search.Here p_i = p, m is the number of subgoals, and δ controls the failure probability.

D Detailed Experimental Setup … D.3 Open Problem Solving

The experiments evaluate BES across logical reasoning, multi-hop reasoning, and open problem solving using task-specific data, search procedures, verification mechanisms, and compute budgets. Across settings, BES combines forward candidate evolution with backward decomposition or intermediate verification.

  • D.1 Logical Reasoning: The K&K setup uses 1,000 SFT problems, 5,000 post-training problems, and 1,287 validation problems spanning npeople ∈{2, . . . , 10}.Stage 1 uses 3-epoch supervised fine-tuning; Stage 2 runs BES search per training batch with a fixed GRPO group size of 8.
  • D.1 Logical Reasoning: For K&K puzzles, backward search expands role-identification goals into per-person sub-goals and elementary verification strategies, while an LLM schedules traversal of the template tree.The backward decomposer chooses per-person verification order initially and activates strategies every D = 10 search steps.
  • D.2 Multi-Hop Reasoning: MuSiQue experiments use the answerable 3-to-4-hop solvable training split and the full official validation set, with the training data held fixed across methods.Training lasts two epochs, and BES, GRPO, and Tree-GRPO use the same per-problem budget of 8 trajectories; extra epochs cause overfitting and training collapse.
  • D.2 Multi-Hop Reasoning: In multi-hop reasoning, trajectories interleave thinking, retrieval, and information actions, while backward search decomposes each question into an ordered chain of atomic sub-questions.Each search call retrieves the top 3 passages, and sub-goals are checked sequentially only after preceding sub-goals are satisfied.
  • D.3 Open Problem Solving: Open problem solving evaluates Circle Packing (Square), Circle Packing (Rect), and Heilbronn (Convex, n = 13), reporting mean and best objective values across 3 runs.The tasks optimize circle-radius sums or minimum convex-polygon area under the stated geometric constraints.
  • D.3 Open Problem Solving: BES extends ShinkaEvolve with four LLM-driven program-level evolution operators and a backward goal tree supplying dense intermediate scores.The operators rewrite two parent programs jointly because direct concatenation is not meaningful for executable programs.
  • D.3 Open Problem Solving: The open-problem backward tree grows adaptively after 5 generations without raw-objective improvement at margin ∆=10^-2, adding 2–4 child sub-goals for an unsatisfied leaf.Leaf verifiers return continuous partial-progress scores in [0, 1], while bucket interpolation ensures raw-objective improvements dominate backward signals.

E Case Study · F Prompts for Open Problem Solving Tasks

The case study shows BES solving a multi-hop question by combining backward subgoal verification with forward translocation, while the appendix specifies benchmark prompts for decomposition and evolutionary program search. These prompts enforce dense verification and distinct mutation strategies, including combination, deletion, crossover, and targeted translocation.

  • E Case Study: BES decomposes the question into two sub-goals: identify the artist who recorded Back to Bedlam, then identify that artist’s record label.The correct answer is Custard Records, and the artist is James Blunt.
  • E Case Study: Two initial expansion branches produce wrong answers, whereas translocation combines reasoning from both branches to produce the correct answer.The left branch concludes Atlantic Records; the right identifies Custard Records and Atlantic Records but does not resolve the final answer.
  • E Case Study: The backward-search verifier assigns partial credit, including a score of 0.3 to the branch that identifies relevant Custard Records information without answering correctly.This dense intermediate feedback guides parent selection even when final answers are wrong.
  • F Prompts for Open Problem Solving Tasks: The appendix defines one benchmark-specific decomposition prompt and four evolution-operation prompts—DIFF, DIFF_ABLATE, FULL, and CROSS—for open-problem search.Prompts use Python str.format-style placeholders such as {code_content}, {performance_metrics}, and {previous_attempts}.
  • F.1 Backward Search: Goal Tree Decomposition: Decomposition verification should return a dense score in [0,1], preferably using min(1.0, <actual> / <target>) rather than a Boolean.The prompt requires a single Python expression evaluated with Python’s eval().
  • F.2.1 Combination: The combination prompt identifies compatible tricks from multiple inspiration programs and stitches them into the current program while preserving its skeleton.Conflicting or redundant tricks are dropped, and the description must explain each retained trick’s source and composition rationale.
  • F.2 Evolution Operation Prompts: Deletion, crossover, and translocation prompts respectively demand a fundamentally new strategy, a complete program combining two implementations, or one targeted trick transplanted into the current skeleton.All three preserve required interfaces where specified, while translocation explicitly avoids broad rewriting.

G Identified Programs for Open Problem Solving Tasks … G.3 Heilbronn (Convex)

This appendix summarizes the best BES-discovered programs for three open-problem benchmarks: square and rectangle circle packing, and Heilbronn convex-hull instances. The programs combine structured initialization, feasibility handling, and specialized optimization procedures tailored to each task.

  • G Identified Programs for Open Problem Solving Tasks: The appendix reports the structure of the best program discovered by BES for each open-problem benchmark.The identified programs cover circle packing in a square, circle packing in a rectangle, and Heilbronn convex-hull optimization.
  • G.1 Circle Packing (Square): The n=26 square-packing program is a hybrid global optimiser that jointly optimizes circle centres and radii.It alternates K-nearest-neighbour radii projection, active-set LP cutting planes, and two-tier simulated search.
  • G.1 Circle Packing (Square): Square-packing search starts from deterministic seeds including hexagonal rows, edge rings, corner-weighted arrangements, and spokes-plus-concentric-pentagon interiors.Seeds receive controlled anisotropic jitter and short feasibility probing.
  • G.2 Circle Packing (Rectangle): The n=21 rectangle-packing program uses deterministic multi-start construction with dense aspect-ratio and jitter-scale enumeration followed by feasibility clamping.Candidate layouts come from heterogeneous hex-like row patterns.
  • G.2 Circle Packing (Rectangle): Rectangle-packing candidates are ranked by sum of radii with minimal pairwise slack as the tie-breaker, and only the top-K seeds advance to optimization.Each surviving seed undergoes a two-stage refinement.
  • G.3 Heilbronn (Convex): The n=13 Heilbronn program uses a C3-symmetric parameterisation with one centre and four concentric 3-orbits, yielding 13 points and 8 free parameters.The four radii use a softplus-ordered map, while four phases are reduced modulo 2π/3.
  • G.3 Heilbronn (Convex): Heilbronn optimization applies Coordinate Pattern Search with K-guided weighted co-participation, where the top-K smallest triangles guide ring selection.Hull area is normalized using Andrew’s monotone chain and the shoelace formula across 286 triangles.

H Potential Limitations and Broader Impacts

BES has limitations involving reward-signal availability, backward decomposition quality, and the scale of post-training models evaluated. It may strengthen reasoning while reducing reliance on larger models and improving interpretability through verifiable sub-goals.

  • Potential Limitations: BES requires an objective reward signal and has not been tested on subjective tasks such as academic writing.Such signals are difficult to obtain for subjective evaluation tasks.
  • Potential Limitations: Backward search depends on the policy decomposing problems into meaningful sub-goals, a capability limited in very weak models.The limitation affects the decomposition component that guides search with intermediate structure.
  • Potential Limitations: Post-training experiments use relatively small models, with sizes up to 8B parameters, because of resource constraints.The reported model scale limits how broadly the post-training findings can be generalized.
  • Broader Impacts: BES may improve reasoning performance, reduce the need for larger models and associated costs, and make search more transparent through verifiable sub-goals.The broader impacts described include potential computational and environmental cost reductions and improved interpretability.
Loading 2605.28814v1…