Self-Improving Language Models with Bidirectional Evolutionary Search

BES는 forward 후보의 진화와 backward 목표 분해를 결합해 expansion-only의 한계를 벗어나 더 적은 샘플로 더 나은 해를 찾고, post-training과 inference에서 성능을 향상시킨다.

확률 정책의 샘플링은 일반적으로 확률 질서의 얇은 엔트로피 셸에 머무르는 경향이 있다. Expansion-only은 이 셸 밖으로 벗어나지 못하고 다양한 해를 찾기 어렵다. Evolution operators는 서로 다른 두 후보의 부분을 재조합해 새로운 후보를 만들고, Backward Goal Tree는 하위 목표를 정의해 dense 피드백을 제공한다. 이로써 더 넓은 탐색 공간을 탐색하고, 최종적으로 더 나은 해를 발견한다.

BES는 forward search와 backward search를 교대로 실행하는 이중 루프 구조다. Forward search는 Expansion과 Evolution의 다섯 가지 연산으로 후보를 확장하고, Backward scoring이 각 후보를 평가하는 신호를 제공한다. Backward search는 groot 목표에서 시작해 leaf 서브-goal로 점진적으로 분해하는_goal 트리를 구성하고, 각 노드의 점수 Vg(x, n)을 재계산한다. 단일-부모 연산(expansion, deletion)은 Boltzmann 선택으로 부모를 샘플링하고, 이항 연산(two-parent: combination, translocation, crossover)은 Ct에서 두 부모를 샘플링해 공통 프리픽스 길이에 따라 suffix를 결합한다. 연산의 온도 τt는 초기값에서 끝값으로 선형적으로 감소시키며 탐색을 점진적으로 수렴시킨다. Backward score는 s(n,g) = α·Vg(x, n) + (1 − α)·(ch(g))의 점수의 평균으로 구성되며 leaf sub-goal이 모두 해결되면 s(n, g) = Vg(x, n)으로 정의한다. G를 주기적으로 업데이트하고, K forward steps마다 backward decomposition을 통해 서브-골 트리를 확장한다. Post-training에서는 각 문제에 대해 담을 터미널 후보를 8개로 구성하도록 설정하고, inference에서는 최종 후보를 선택한다. Theorem 4.4와 Theorem 4.5는 Shell confinement 및 Backward sub-goal의 지수적 이점을 보장한다.

Knights-and-Knaves(K&K)에서 BES는 학습 도중 validation accuracy를 지속적으로 향상시키며 GRPO/MaxRL 대비 우수한 성능 개선을 보인다. MuSiQue(다중-홉 추론)에서 3B-모델(Llama-3.2-3B-Instruct)에서 BES의 정확도는 7.0으로 최상이며, 8B 모델(Llama-3.1-8B-Instruct)에서도 BES가 10.4로 가장 높은 정확도를 보였다(각각 +3.0, +3.8 포인트). Circle Packing(Square)에서 Avg 2.623, Best 2.632로 Open Source framework 중 우수했고, Circle Packing(Rect) 2.3492.360, Heilbronn(Convex) 0.0260.027를 달성했다. 비용 측면에서는 Post-Training 시 BES의 walltime가 Tree-GRPO 대비 약 29% 증가(309s vs 240s)했고, API 비용 측면에서도 ShinkaEvolve 대비 증가가 관찰되었으며, 전반적으로 향상된 성능 품질을 보여준다.

BES 아키텍처는 forward search와 backward search가 서로를 보완하는 구조다. Forward search는 Expansion과 Evolution의 다섯 가지 연산을 통해 partial trajectories를 확장하고, Backward scoring이 dense 신호를 통해 후보를 선별한다. Backward search는 groot에서 시작해 leaf sub-goal로 확장하는 goal tree를 구성하고, 각 leaf에 Vg(x, n)을 계산한다. Single-parent 연산(expansion, deletion)은 Ct에서 Boltzmann 선택으로 부모를 선택하고, 새 스텝을 샘플링한다. Two-parent 연산(combination, translocation, crossover)은 두 부모를 선택해 공유 프리픽스 길이에 따른 suffix를 재조합한다. s(n, g)와 s(na, nb, g)의 정의는 Eq. (5)와 Eq. (6)에 기반한다. G를 업데이트하는 backward decomposition은 unsolved leaf 서브-goal을 선택해 인간-유도 백워드 계획으로 확장한다. 이론적 근거로 Shell confinement(Expansion)과 Shell escape(Evolution) 및 Exponential advantage from backward sub-goal signals가 제시된다.