acceptodds
Under review as a conference paper at ICLR 2027

Self-Improving Language Models with Bidirectional Evolutionary Search

Abstract

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 sub-goals, producing dense intermediate feedback that guides forward search. We provide motivation illustrating that candidates generated by expansion-only search may be confined to a narrow entropy shell, while evolution operators may escape it. Experiments show that on challenging post-training tasks where mainstream post-training algorithms fail to improve, BES enables consistent gains. At inference time, BES outperforms existing open-source frameworks on three open problem solving benchmarks in both average and best-case performance, and outperforms majority voting and Monte Carlo Tree Search on mathematical reasoning and competitive programming benchmarks.

Primary area:
foundation or frontier models, including LLMs
Keywords:
evolutionary search, bidirectional search, post-training

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_C7MDOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Bidirectional Evolutionary Search (BES), a search framework for improving the quality of LLM-generated solutions during both post-training and inference. BES combines forward search with several evolutionary operators, including combination, deletion, translocation, and crossover, to generate new candidates from existing trajectories. It also introduces backward search that recursively decomposes a task into verifiable sub-goals, providing more fine-grained feedback to guide candidate selection.

The authors evaluate BES across multi-hop reasoning, logical reasoning, mathematical reasoning, competitive programming, and open problem solving. The experiments show improvements over several sampling and search baselines, particularly on challenging tasks where conventional post-training methods struggle to discover successful trajectories.

Critical strengths
  1. Reasonable empirical improvements across multiple settings. The paper evaluates BES in both post-training and inference-time search, covering a reasonably broad range of tasks. The reported improvements over several existing search baselines suggest that combining evolutionary operators with goal decomposition can be practically useful.

  2. A unified framework for candidate generation and verification. BES provides a relatively systematic way to combine candidate evolution with fine-grained verification. Although the individual components are not entirely new, integrating them into a single framework for both training-time sampling and inference-time search is a useful engineering contribution.

Critical weaknesses
  1. Limited methodological novelty. My main concern is that BES appears to be largely an integration of existing ideas rather than a fundamentally new search algorithm. Evolutionary operators such as crossover, recombination, and mutation have been extensively explored in evolutionary computation and more recent LLM-based evolutionary search frameworks. Similarly, goal decomposition and intermediate verification are well-established ideas in planning and reasoning. While combining these components is reasonable, I find the proposed method conceptually rather incremental. The paper does not sufficiently establish what new algorithmic insight BES provides beyond this combination.

  2. Insufficient evidence for the significance and generality of the proposed approach. Although the experiments report improvements, I am not fully convinced that they establish a sufficiently substantial advancement over existing search methods. For example, the improvements on AIME and LiveCodeBench are relatively modest in several settings, while BES introduces additional search and verification complexity. Furthermore, the ablation study mainly examines the removal of the two major components on a single logical reasoning benchmark, making it difficult to understand the individual contributions of the evolutionary operators and the conditions under which each component is genuinely beneficial. I would also like to see stronger evidence that the proposed framework provides a consistent advantage in terms of solution quality versus computational cost.

Questions for authors

Please see Weaknesses

Reviewer_LxEsOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Bidirectional Evolutionary Search (BES), which combines standard evolutionary methods for candidate generation with decomposition of candidates, allowing for verifiable subgoals and denser reward estimation. The authors test this method on 3 reasoning post training tasks against other post training methods such as GRPO. Then the authors test this method against other inference time scaling methods on optimization and reasoning tasks, demonstrating improvement over majority of N and Monte Carlo Tree Search.

Overall the contribution seems novel although defense of it's improvement over alternatives appears weak.

Critical strengths

The paper appears to use a novel combo: generation of candidate solutions along with decomposition of said solutions as to provide both exploration and fine grain reward of candidates. From a cursory check through the literature this appears not to have been done with LLM's yet. The idea is intuitive and makes sense as a novel method for LLM solution generation.

Critical weaknesses

The paper seems limited in scope in comparisons to RL for post training. It appears to focus on MuSiQu, Bamboogle, and knights and knaves for comparison with GRPO. I think it could be greatly strengthened by testing more reasoning tasks such as gsm8k, math500, or sudoku for that comparison, or go back and test GRPO/variants on the inference tests it has with cicle packing, aime, and livecodebench. Looking at the training curves as well there appears to be substantial variance esp in figures 3 and 4. I am not sure one can conclude BES is significantly better than GRPO especially when the task set is so limited.

Questions for authors

Why were MuSiQue and Bamboogle chosen for post training comparison over more standard reasoning tasks like gsm8k, math500, countdown, or sudoku?

Reviewer_tx6UOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Bidirectional Evolutionary Search (BES), a framework for improving LLM reasoning through two complementary mechanisms: (1) forward search, which generates candidates through evolutionary operations such as combination, deletion, translocation, and crossover, and (2) backward search, which decomposes problems into verifiable sub-goals to provide more informative feedback. BES is applied to both post-training and inference-time search. Experiments on reasoning, mathematical optimization, and programming benchmarks demonstrate improvements over several existing search methods.

Critical strengths

The paper addresses two important limitations of LLM search: limited exploration beyond the model's existing distribution and sparse verification signals. The experimental evaluation is relatively comprehensive, covering both post-training and inference-time settings, multiple model backbones, and ablation studies.

Critical weaknesses
  1. (Major weakness) The methodological novelty is somewhat limited. BES combines evolutionary search operators with hierarchical goal decomposition, both of which are established ideas. While their integration is potentially useful, the paper does not clearly establish why this particular combination constitutes a fundamentally new search method. In particular, the experiments do not compare BES against existing search algorithms augmented with the same sub-goal verification mechanism.

  2. (Major weakness) The theoretical motivation does not adequately explain why evolutionary search improves solution quality. The entropy-shell analysis shows that recombination can generate trajectories unlikely under the original model. However, generating low-probability trajectories does not necessarily produce better solutions. Moreover, the analysis considers idealized recombination of independent trajectory segments rather than the actual LLM-based evolutionary operators. Thus, the connection between the theoretical motivation and the empirical improvements remains unclear.

  3. (Major weakness) The effectiveness of BES depends heavily on the quality of the backward-search verifier. The method assumes that problems can be decomposed into meaningful and verifiable sub-goals. However, this is not necessarily feasible for general reasoning tasks. Even in the MuSiQue experiments, the embedding-based verifier achieves only 0.78 precision and 0.74 recall (Appendix J). The paper provides limited evidence that BES remains effective under inaccurate sub-goal decomposition or noisy verification.

Questions for authors

Can the authors compare BES with existing search algorithms equipped with the same sub-goal decomposition and verification mechanisms? This would help isolate the methodological contribution of bidirectional evolutionary search. How robust is BES when the backward-search decomposition is inaccurate or the sub-goal verifiers provide noisy feedback? Can the authors demonstrate that escaping the original model's probability distribution actually increases the likelihood of finding correct solutions, rather than simply producing more diverse candidates?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.