Self-Improving Language Models with Bidirectional Evolutionary Search

Problem
This paper addresses the limitations of existing search methods for self-improving language models and agentic systems, specifically post-training sample generation and inference. The authors highlight that conventional techniques, such as best-of-N sampling and tree search, are hindered by sparse verification signals and primarily rely on autoregressive expansion, which restricts exploration to areas with high model probability mass. This work is presented as a preprint and has not yet undergone peer review.

Method
The authors introduce Bidirectional Evolutionary Search (BES), a novel search framework that integrates forward candidate evolution with backward goal decomposition. In the forward search phase, BES enhances standard expansion by employing evolutionary operators that recombine partial trajectories, allowing for the generation of candidates that are not easily obtainable through a single model rollout. The backward search phase involves recursively breaking down the original task into checkable subgoals, which yields dense intermediate feedback to inform the forward search. The theoretical foundation of BES posits that candidates produced by traditional expansion-only methods are limited to a narrow entropy shell, while evolutionary operators can navigate beyond this constraint. Additionally, the backward search is shown to exponentially decrease the sample size needed to identify correct answers.

Results
BES demonstrates significant performance improvements on challenging post-training tasks where traditional algorithms typically fail. Specifically, the framework outperforms existing open-source methods on three open problem-solving benchmarks, achieving superior average and best-case performance metrics. While exact numerical results are not disclosed in the abstract, the authors assert that BES consistently yields gains over baseline methods, indicating a robust enhancement in model capabilities.

Limitations
The authors acknowledge that the proposed method may require substantial computational resources due to the dual search processes involved. They do not explicitly discuss the scalability of BES in terms of larger model architectures or its performance across diverse language tasks. Additionally, the reliance on evolutionary operators may introduce complexity in tuning and implementation, which could be a barrier for practical deployment.

Why it matters
The introduction of BES has significant implications for the development of more effective self-improving language models and agentic systems. By overcoming the limitations of existing search methods, BES could facilitate more robust exploration of the solution space, leading to improved performance in various NLP tasks. This work opens avenues for future research into hybrid search strategies that combine evolutionary techniques with traditional sampling methods, potentially enhancing the adaptability and efficiency of language models in real-world applications.

Authors: Guowei Xu, Zhenting Qi, Huangyuan Su, Weirui Ye, Himabindu Lakkaraju, Sham M. Kakade, Yilun Du
Source: arXiv cs.CL
URL: https://arxiv.org/abs/2605.28814v1
arXiv ID: 2605.28814