탐색(Search)은 사후 학습(post-training) 샘플 생성과 추론(inference) 모두에서 언어 모델(language models) 및 에이전트 시스템(agentic systems)을 자기 개선하기 위한 효과적인 방법으로 제안되어 왔습니다. 그러나 best-of-N 샘플링(sampling) 및 트리 탐색(tree search)과 같이 널리 사용되는 방법들은 두 가지 근본적인 한계에 직면해 있습니다. 즉, 이들은 희소한 검증 신호(sparse verification signals)에 의해 유도되며, 주로 자기회귀적 확장(autoregressive expansion)을 통해 후보를 구성함으로써 탐색 범위를 모델 확률 질량(probability mass)이 상당한 영역으로 제한한다는 점입니다. 이를 해결하기 위해, 우리는 전방향 후보 진화(forward candidate evolution)와 후방향 목표 분해(backward goal decomposition)를 결합한 탐색 프레임워크인 양방향 진화 탐색(Bidirectional Evolutionary Search, BES)을 제안합니다. 전방향 탐색(forward search)에서 BES는 표준적인 확장(expansion)에 부분적인 궤적(trajectories)을 재결합하여 단일 모델 롤아웃(rollout)으로는 얻기 어려운 후보를 생성하는 진화 연산자(evolution operators)를 추가합니다. 후방향 탐색(backward search)에서 BES는 원래의 과업을 검증 가능한 하위 목표(subgoals)로 재귀적으로 분해하여, 전방향 탐색을 가이드하는 조밀한 중간 피드백(intermediate feedback)을 생성합니다. 우리는 확장 전용 탐색(expansion-only search)에 의해 생성된 후보들이 좁은 엔트로피 쉘(entropy shell)에 갇혀 있는 반면, 진화 연산자는 이를 벗어날 수 있다는 이론적 동기를 제공하며, 후방향 탐색이 정답을 찾기 위해 필요한 샘플 수를 기하급수적으로 줄일 수 있음을 보여줍니다. 실험 결과, 주류 사후 학습 알고리즘이 개선에 실패하는 까다로운 사후 학습 과업에서 BES는 일관된 이득을 보여주었으며, 추론 시점의 세 가지 오픈 문제 해결 벤치마크에서 BES는 평균 및 최선 성능 모두에서 기존 오픈 소스 프레임워크를 능가함을 입증했습니다. 코드와 학습된 모델은 https://github.com/Embodied-Minds-Lab/BES 에서 확인할 수 있습니다.