Self-Improving Language Models with Bidirectional Evolutionary Search

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.

📋 한 줄 요약

**[Self-Improving LLM / Search]** BES가 forward evolutionary expansion + backward goal decomposition으로 best-of-N·tree search 한계 극복 — entropy shell 탈출·dense intermediate feedback, post-training·inference 모두에서 mainstream 대비 일관 향상.

🎯 핵심 기여도

Search가 self-improving language model·agentic system에 효과적이라 제안되어 왔지만(post-training sample generation과 inference 모두), 널리 쓰이는 best-of-N·tree search가 두 근본 한계 가짐을 진단 — (1) sparse verification signal에 의해 guided, (2) candidate를 주로 autoregressive expansion으로 구성해 substantial model probability mass 영역에 exploration 제한.
Bidirectional Evolutionary Search(BES) 제안 — forward candidate evolution + backward goal decomposition을 결합한 search 프레임워크.
Forward search: 표준 expansion에 partial trajectory를 recombine하는 evolution operator를 추가, single model rollout으로 얻기 어려운 candidate 생성.
Backward search: 원 task를 checkable subgoal로 recursively 분해, dense intermediate feedback을 만들어 forward search 가이드. 이론적 동기 — expansion-only search candidate가 narrow entropy shell에 confined되는 반면 evolutionary operator는 이를 escape 가능; backward search가 correct answer 발견에 필요한 sample 수를 exponentially 줄임.

💡 핵심 아이디어

LLM·agent의 search 한계는 expansion 중심·sparse signal에서 비롯되며, forward에 evolutionary recombination·backward에 goal decomposition을 결합하면 narrow entropy shell을 escape하고 exponentially 적은 sample로 정답에 도달 가능하다 — post-training과 inference 양쪽에서 일관 향상.

🔬 기술적 접근법

**방법론**: BES — Bidirectional Evolutionary Search.
**핵심 기법**: (1) Forward search에 evolution operator로 partial trajectory recombination 추가, (2) Backward search로 task를 checkable subgoal로 recursive 분해, (3) Dense intermediate feedback이 forward search 가이드, (4) 이론 — expansion-only candidate가 entropy shell에 confined·evolutionary는 escape; backward가 sample 수 지수 감소, (5) Post-training sample generation·inference 양 환경 적용.

📊 주요 결과

어려운 post-training task(mainstream post-training algorithm이 향상 실패하는)에서 BES가 consistent gain.
Inference 시점 3 open problem solving benchmark에서 average·best-case 모두 기존 open-source framework 능가.
Code·trained model: github.com/Embodied-Minds-Lab/BES.

💭 의의 및 한계

**의의**: LLM self-improvement search의 두 limitation 동시 해소, 이론적 동기(entropy shell·sample complexity)로 뒷받침, post-training·inference 통합 framework. **한계**: Evolutionary operator·goal decomposer 설계의 task 의존성, backward decomposition의 verifiable subgoal 가용성, 매우 긴 horizon task의 결과는 추가 검증.

🚀 실용적 활용

LLM의 post-training reasoning 향상.
Inference-time 어려운 문제 해결.
Agentic system의 search 일반 효율 개선.