Self-Improving Language Models with Bidirectional Evolutionary Search

Motivation

• Known: 기존에는 LLM 및 agentic system의 post-training sample generation과 inference-time test-time scaling을 위해 best-of-N sampling과 tree search(beam search, Monte Carlo Tree Search 등)가 널리 사용되어 왔으며, GRPO, Tree-GRPO와 같은 post-training 알고리즘과 Tree of Thoughts 같은 inference-time 방법에 적용되어 왔다.
• Gap: 기존 방법들은 (1) 성긴(sparse) verification signal에 의존하고, (2) autoregressive expansion을 통해서만 후보를 생성하기 때문에 model의 probability mass가 큰 영역에만 탐색이 국한되어 hard problem에서 정답이 존재하는 low-probability region에 도달하기 어렵다는 두 가지 근본적 한계를 가진다.
• Why: frontier 수준의 어려운 문제일수록 naive sampling은 정답을 찾기 위해 지나치게 많은 샘플을 필요로 하거나 아예 실패하므로, post-training의 self-improvement와 inference-time test-time scaling 모두에서 효율적인 sampling/search 방법을 찾는 것이 LLM과 agentic system의 능력 향상에 핵심적으로 중요하다.
• Approach: forward search에는 생물학적 유성생식의 chromosomal recombination에서 영감을 받은 evolution operator(combination, translocation, deletion, crossover)를 도입해 단일 rollout으로는 얻기 힘든 후보를 생성하고, backward search로는 원래 task를 재귀적으로 checkable subgoal로 분해해 forward search에 dense한 중간 피드백을 제공한다.

Achievement

Figure 3. EMA-smoothed validation accuracy on logical reasoning.

1. 이론적 정당화: expansion-only search로 생성된 후보들이 narrow entropy shell에 국한됨을 증명하고, evolution operator가 이 shell을 벗어날 수 있음과 backward search가 정답을 찾기 위해 필요한 샘플 수를 exponential하게 줄일 수 있음을 이론적으로 보였다.
2. post-training 성능 향상: GRPO, MaxRL, Tree-GRPO 등 주류 post-training 알고리즘이 개선에 실패하는 어려운 logical reasoning 및 multi-hop reasoning task에서 BES가 일관되게 유효한 training sample을 발견해 base model 성능을 향상시켰다.
3. inference-time 성능 향상: 세 가지 open problem solving benchmark에서 BES가 OpenEvolve, GEPA, ShinkaEvolve 등 기존 open-source framework 대비 평균 성능과 best-case 성능 모두에서 우수함을 보였다.

How

Figure 2. Forward search operators. (a) Expansion: the policy generates new steps (yellow). (b) Combination: two traject

• Task를 T = (x, V)로 정의하고, policy π_θ(·|x)가 생성한 trajectory y에 대해 verifier V(x,y)가 점수를 부여하는 설정에서 y* = arg max_{y∈Y_term(x)} V(x,y)를 찾는 문제로 정식화
• forward search: 기존 expansion 연산에 더해 combination(공통 prefix를 공유하는 두 trajectory의 distinct suffix를 concatenate), deletion(내부 step 제거), translocation(한 path의 step을 다른 path의 step으로 대체), crossover(한 path를 splice point에서 잘라 다른 path의 tail로 교체)의 4가지 evolution operator 도입
• backward search: 원래 task를 재귀적으로 checkable subgoal로 분해해 partial trajectory에 대한 dense한 verification 점수 제공, 이를 forward search 안내에 활용
• forward search와 backward search를 alternating하며 결합하여 bidirectional evolutionary search 수행
• 이론 분석: expansion-only 후보가 narrow entropy shell에 confine됨을 증명(Theorem 4.4a), backward search로 필요한 sample 수가 exponential하게 감소함을 증명
• 실험: post-training에서는 challenging logical/multi-hop reasoning task에 GRPO, MaxRL, Tree-GRPO와 비교, inference에서는 세 개의 open problem solving benchmark에서 OpenEvolve, GEPA, ShinkaEvolve와 비교, 추가로 ablation study, case study, wall-time 및 API cost 분석 수행

Originality

• 생물학적 유성생식의 chromosomal recombination 개념을 LLM/agent trajectory search에 도입해 combination, translocation, deletion, crossover라는 4가지 evolution operator를 정식화한 점이 독창적이다.
• forward evolutionary search와 backward goal decomposition을 하나의 alternating framework로 결합해 sparse verification과 제한된 탐색 범위라는 두 문제를 동시에 해결하려는 bidirectional 접근이 새롭다.
• expansion-only search가 narrow entropy shell에 갇힌다는 것을 이론적으로 증명하고 evolution operator의 shell 탈출 가능성 및 backward search의 sample efficiency에 대한 exponential reduction을 이론적으로 뒷받침한 점이 기존 empirical 위주 search 연구와 차별화된다.

Limitation & Further Study

• backward search를 통한 subgoal decomposition의 정확성이 LLM 자체의 decomposition 능력에 의존할 가능성이 있어, decomposition이 부정확한 도메인에서는 dense feedback의 신뢰성이 저하될 수 있다.
• evolution operator(특히 crossover, translocation)가 서로 다른 trajectory를 결합할 때 semantic coherence를 해칠 위험이 있으며, 이에 대한 상세한 실패 사례 분석이 본문 발췌만으로는 충분히 드러나지 않는다.
• 논문에서 제시한 wall-time 및 API cost 분석이 실제로 BES의 계산 비용이 tree search나 best-of-N 대비 얼마나 증가하는지에 대한 정량적 trade-off를 충분히 다루었는지 추가 검증이 필요하다.
• 후속 연구로는 다양한 도메인(코드 생성, 과학적 발견 등)으로의 일반화 가능성 검증과, evolution operator의 자동 선택/가중치 조정 메커니즘 개발이 유의미할 것이다.

Evaluation

총평: 생물학적 진화 개념을 search 알고리즘에 창의적으로 접목하고 이를 이론적으로 뒷받침하는 동시에 post-training과 inference 양쪽에서 실질적 성능 향상을 보인 완성도 높은 연구이나, evolution operator의 안정성과 backward decomposition의 신뢰성에 대한 추가 검증이 필요하다.