Self-Improving Language Models with Bidirectional Evolutionary Search

왜 중요한가

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

핵심 기여

Shell confinement and escape

Expansion-only 검색은 엔트로피 셸에 갇히는 경향이 있으며, evolution operators는 이 셸에서 벗어나 저확률 영역으로 탐색을 확장할 수 있다.

Backward sub-goal decomposition

Backward search가 문제를 세분된 하위 목표의 트리로 분해해 각 노드를 평가하고, 그에 따른 dense 피드백으로 forward 후보를 효과적으로 가이드한다.

Four evolution operators

Combination, Deletion, Translocation, Crossover의 네 가지 연산이 서로 다른 부분의 강점을 재조합해 새로운 후보를 만든다.

Post-training 및 inference에서의 성능 개선

BES가 고품질 샘플을 더 많이 발견하게 하여 post-training의 성능 향상 및 open-problem 추론 벤치마크에서의 안정적 해를 보인다.

핵심 아이디어 이해하기

확률 정책의 샘플링은 일반적으로 확률 질서의 얇은 엔트로피 셸에 머무르는 경향이 있다. 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.349~~2.360, Heilbronn(Convex) 0.026~~0.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가 제시된다.

실무 활용

BES는 샘플 품질과 탐색 효율성의 상호 보완적 개선을 목표로 하는 일반 프레임워크로, post-training과 inference 모두에서 효과적으로 작동한다.

post-training에서 고품질 샘플로 학습 효과를 강화
inference에서 오픈 프로블럼 문제를 안정적으로 해결
다양한 도메인 문제의 추론 및 코드 작성 보조에서 샘플 다양성 증가

코드 공개 여부: 공개

코드 저장소 보기

키워드

Bidirectional Evolutionary Search (BES)entropy shellbackward goal decompositionforward candidate evolutionevolutionary operators (combination, deletion, translocation, crossover)post-training samplinginference open problems

용어 해설

엔트로피 셸(Entropy Shell): — 확률 모델이 생성하는 후보군이 확률 분포의 특정 얇은 영역(typical set) 안에 머무르는 현상을 뜻하며, expansion-only 탐색은 이 셸 밖으로 벗어나기 어렵다.
Backward 목표 트리(Backward Goal Tree): — 문제를 더 작은 검증 가능한 하위 목표들로 쪼개어 계층적 서브-goal을 구성하는 트리 구조를 뜻한다.
진화 연산자(Evolutionary Operators): — 두 후보를 결합, 제거, 전이, 교차 등의 편집 연산으로 재구성하여 후보 공간을 확장하는 기법을 뜻한다.
Combination: — 두 경로의 공유 프리픽스 이후 접미부를 연결해 새로운 후보를 만드는 연산이다.

Self-Improving Language Models with Bidirectional Evolutionary Search

왜 중요한가

핵심 기여

핵심 아이디어 이해하기

방법론

주요 결과

기술 상세

실무 활용

키워드

용어 해설

관련 토론

댓글

관련 기사

장기 LLM agent를 위한 저메모리 ES Fine-tuning

왜 중요한가

핵심 기여

핵심 아이디어 이해하기

방법론

주요 결과

기술 상세

실무 활용

키워드

관련 토론

댓글

관련 기사

장기 LLM agent를 위한 저메모리 ES Fine-tuning