기술 요약: 대조적 동적 분기 샘플링을 통한 멀티 턴 검색 에이전트 학습

1. 문제 정의

에이전트 강화 학습(RL)은 거대 언어 모델(LLM)이 복잡한 멀티 턴 계획 및 도구 사용을 수행할 수 있도록 가능하게 했습니다. 그러나 이러한 에이전트를 장기적 호라이즌(long-horizon) 설정에서 학습시키는 것은 **희소한 궤적 수준의 결과 보상(sparse, trajectory-level outcome rewards)**으로 인해 여전히 어려운 과제로 남아 있습니다. 표준 RL 설정에서는 최종 정답 여부를 나타내는 단일 보상 신호가 전체 궤적에 할당됩니다. 이는 **신용 할당 모호성(credit assignment ambiguity)**을 초래하여, 초기 단계의 올바른 결정이 후기 단계의 오류로 인해 저평가되거나, 학습 신호의 분산이 높아지는 문제를 일으킵니다.

이를 완화하려는 기존의 시도들(예: Tree-GRPO와 같은 트리 기반 롤아웃)은 종종 높은 분산과 계산 비효효율성 문제를 겪습니다. 이들은 중간 상태로부터 깊은 몬테카를로 추정을 수행해야 하는데, 이는 노이즈가 많고 계산 비용이 많이 들 수 있습니다. 또한, 경험적 분석에 따르면 검색 에이전트에서 특정한 실패 패턴이 발견됩니다. 즉, 롤아웃 전반의 초기 상호작용은 서로 유사한 경우가 많지만, 성능의 차이는 주로 궤적의 꼬리(tail) 부분에서의 결정(예: 불충분한 탐색 또는 최종 합성 단계에서의 환각 현상)으로 인해 발생합니다. 전체 롤아웃을 균등하게 감독하는 것은 이러한 관찰 결과를 활용하지 못합니다.

2. 방법론: BranPO

저자들은 밀도 높은 보상 없이도 스텝 단위의 대조적 감독을 제공하도록 설계된 가치 없는(value-free) 방법인 **BranPO(Branching Relative Policy Optimization)**를 제안합니다. 핵심 통찰은 가장 정보가 풍부한 학습 신호는 시작점부터 다시 샘플링하는 것이 아니라, 궤적의 꼬리 근처에서 대안적인 결정들을 대조함으로써 발생한다는 것입니다.

핵심 메커니즘

BranPO는 궤적의 꼬리 부분을 재귀적으로 절단하고 대안적인 연속(continuations)을 재샘플링하여 공유된 접두사(prefix) 위에 **대조적 접미사(contrastive suffixes)**를 구축함으로써 작동합니다.

1. 초기 롤아웃 및 절단(Initial Rollout & Truncation): 주어진 궤적 그룹이 주어지면, 이 방법은 공유 접두사 $B$(검색 이력)를 얻기 위해 선택된 턴 $k$에서 궤적을 절단합니다.
2. 분기(Branching): 접두사에 의해 정의된 상태로부터 여러 개의 분기 연속체(suffixes) $C$를 샘플링합니다.
3. 대조적 필터링(Contrastive Filtering): 원래의 궤적과 결과가 다른 분기들만 유지합니다(예: 원래 궤적이 틀렸다면 올바른 연속체를 찾고, 원래 맞았다면 틀린 연속체를 찾음). 이는 의미 있는 대조 신호를 보장합니다.
4. 이득 분해(Advantage Decomposition):
   • 접두사 이득(Prefix Advantage): 공유 접두사에 대한 보상은 분기된 연속체들의 **평균 리턴(mean return)**으로 계산됩니다. 이는 꼬리 부분의 확률적 변동성을 평균화함으로써 초기 단계의 그래디언트를 안정화하며, 효과적으로 GRPO의 저분산 변형 역할을 합니다.
   • 접미사 이득(Suffix Advantage): 분기된 접미사들에 대해서는 모든 분기 그룹과 상대적인 이득을 계산합니다. 이는 DPO와 유사한 대조적 업데이트를 유도하여, 동일한 접두사를 조건으로 성공적인 연속체와 실패한 연속체 사이의 우도 격차(likelihood gap)를 최대화합니다.

주요 구성 요소

• 난이도 인지 분기 샘플링(Difficulty-Aware Branch Sampling, DBS): 효율성을 높이기 위해, 그룹 수준의 정확도에서 추론된 작업 난이도에 따라 분기 예산을 적응적으로 할당합니다.
  • 쉬운 작업/정답 궤적: 단순 분기(마지막 스텝을 절단).
  • 어려운 작업/오답 궤적: 재귀적 분기(여러 스텝을 뒤로 가서 절단)를 통해 다양한 대조적 접미사를 탐색합니다.
• 중복 스텝 마스킹(Redundant Step Masking, RSM): 검색 에이전트는 종종 중복된 행동(예: 충분한 증거를 찾은 후에도 계속 검색함)을 보입니다. RSM은 상호작용 길이가 정답의 그룹 평균보다 긴 궤적을 식별합니다. 이 방법은 마지막 전 단계(penultimate step)에서 분기하며, 만약 더 짧은 정답 연속체가 발견된다면 원래 궤적의 중복된 스텝들에 대한 이득을 그래디언트 계산 중에 마스킹(0으로 설정)합니다. 이는 불필요한 도구 사용의 강화를 방지합니다.

3. 주요 기여

1. 실패 패턴 식별: 본 논문은 장기 호라이즌 에이전트 검색에서 오류가 주로 궤적의 후기 단계에서의 발산하는 결정으로부터 발생하며, 초기 단계는 대체로 유효하다는 점을 경험적으로 확인했습니다.
2. BranPO 프레임워크: 접두사에 대해서는 안정적인 그래디언트를 제공하는 GRPO를, 접미사에 대해서는 효율적인 DPO 스타일의 대조 학습을 결합한 새로운 가치 없는(value-free) RL 방법을 제안합니다. 이는 궤적 수준의 RL과 선호도 기반 최적화를 이론적으로 통합합니다.
3. 효율성 메커니즘: 계산 자원을 적응적으로 할당하고 불필요하거나 중복된 행동을 억제하기 위해 난이도 인지 분기 샘플링(DBS)과 중복 스텝 마스킹(RSM)을 도입했습니다.
4. 경험적 검증: 멀티 홉 QA 태스크에서 GRPO, Tree-GRPO, GiGPO와 같은 강력한 베이스라인보다 뛰어난 성능을 보이며 BranPO의 우수성을 입증했습니다.

4. 실험 결과

저자들은 단일 홉(Natural Questions, TriviaQA, PopQA) 및 멀티 홉 데이터셋(HotpotQA, 2WikiMultihopQA, MuSiQue, Bamboogle)을 포함한 7개의 질의응답 벤치마크와 실제 웹 검색 태스크(GAIA)에서 BranPO를 평가했습니다.

• 성능: BranPO는 멀티 홉 데이터셋에서 일관되게 베이스라인을 능가하며, F1 점수와 LLM-as-a-Judge 지표 모두에서 상당한 이득을 달ей했습니다. 예를 들어, Qwen2.5-7B-Instruct 모델의 경우, BranPO는 멀티 홉 태스크에서 GRPO의 54.0 대비 평균 55.7의 F1을 달성했습니다.
• 확장성: 이 방법은 훈련 중 상호작용 호라이즌을 4에서 8 턴으로, 평가 중에는 16 턴으로 확장할 때 견고함을 보여주었습니다. BranPO는 정확도를 확보하면서도 중복 단계를 억제하기 위해 GRPO보다 더 빠르게 검색 사용을 늘리도록 학습되었습니다.
• 일반화: GAIA 벤치마크(실제 웹 검색)에서 BranPO는 GRPO보다 우수한 성능을 보이며 강력한 일반화 능력을 입증했습니다.
• 효율성: 추가적인 분기 롤아웃 오버헤드에도 불구하고, BranPO는 감소된 분산과 타겟팅된 감독 덕분에 최적화에 필요한 유효 훈련 샘플 수가 적었기 때문에 실제 훈련 시간(wall-clock time)은 GRPO와 유사하게 유지되었습니다.
• 절제 연구(Ablation): 난이도 인지 분기 샘플링이나 중복 스텝 마스킹 중 하나라도 제거하면 일관된 성능 저하가 나타나, 두 구성 요소의 필요성을 확인했습니다.

5. 의의 및 주장

본 논문은 BranPO가 궤적 수준의 보상에만 의존하는 것보다 에이전트 RL을 위한 훨씬 더 효율적인 훈련 패러다임을 제공한다고 주장합니다. 궤적의 꼬리를 구체적으로 겨냥한 스텝 단위의 대조적 감독을 구축함으로써, BranPO는 신용 할당 모호성을 효과적으로 완화합니다.

저자들은 다음과 같은 점을 강조합니다:

• 접두사 평균화를 통해 초기 단계의 그래디언트 업데이트 분산을 줄임으로써 훈련을 안정화합니다.
• 오류가 발생할 가능성이 가장 높은 궤적 꼬리 근처의 고불확실성 결정에 계산 자원을 집중함으로써 샘플 효율성을 개선합니다.
• 중복 스텝 마스킹을 통해 불필요한 지속에 대한 편향을 방지합니다.

결론적으로, 이 논문은 BranPO가 훈련 효율성과 최적화 품질을 개선하지만, 환각이나 잘못된 사실 정보와 같은 검색 기반 추론의 근본적인 한계를 제거하지는 못하며, 적절한 평가 안전장치가 여전히 필요함을 밝히고 있습니다. 이 연구는 장기 호리즌 태스크에서 가장 효과적인 학습 신호는 전체 궤적에 대한 균등한 감독이 아니라, 실패 지점 근처의 대안적인 결과들을 대조하는 데서 발견된다는 점을 강조합니다.