기술 요약: 고정된 예산 하에서 롤아웃의 정보성 극대화

1. 문제 정의

이 논문은 희소 말단 보상 (예: $R \in \{-1, +1\}$) 환경에서 도구 증강 대규모 언어 모델 (LLM) 을 위한 강화 학습 (RL) 의 구조적 병목 현상을 다룹니다. 핵심 문제는 **고정된 예산 하에서의 롤아웃 정보성 (Rollout Informativeness under a Fixed Budget, RIFB)**입니다.

표준 그룹 상대적 정책 최적화 (GRPO) 에서 이득 (advantage) 신호는 $B$개의 롤아웃으로 구성된 그룹 내 보상의 표준 편차로 정규화됩니다. 주어진 프롬프트에 대한 $B$개의 독립적인 롤아웃이 모두 동일한 결과 (모두 성공 또는 모두 실패) 를 산출할 경우, 표준 편차는 0 이 되어 이득이 0 으로 붕괴합니다. 결과적으로 해당 롤아웃에 사용된 계산 자원이 무의미해지며, 정책에는 그라디언트 질량이 주입되지 않습니다.

저자들은 이를 독립 샘플링에 대한 불가능성 결과로 공식화합니다:

• 정리 1: 예산 무관 독립 샘플러의 경우, 붕괴 (분산 0) 확률은 $p^B + (1-p)^B$입니다. 여기서 $p$는 프롬프트당 성공 확률입니다.
• 함의: $p \to 0$ 또는 $p \to 1$ (어려운 프롬프트) 일 때, 비붕괴 확률은 예산 ($B \cdot \min(p, 1-p)$) 에 대해 최대 선형적으로만 증가합니다. 따라서 단순히 롤아웃 예산 $B$를 늘리는 것만으로는 어려운 프롬프트에서 영구 그라디언트 영역을 탈출할 수 없습니다. 붕괴율은 예산 크기와 무관하게 0 에서 일정하게 떨어져 유지됩니다.

2. 방법론: INFOTREE

독립 샘플링의 한계를 극복하기 위해 저자들은 INFOTREE를 제안합니다. 이는 훈련 시 트리 탐색 프레임워크로, 얼마나 샘플링할지보다 어떤 상태를 확장할지 최적화합니다.

2.1 서브모듈러 공식화

핵심 통찰은 트리 정보성을 극대화하기 위해 확장할 중간 상태를 선택하는 문제가 단조 서브모듈러 최대화 (monotone submodular maximization) 문제로 귀결될 수 있다는 점입니다. 목적 함수 $F$는 세 가지 항으로 구성됩니다:

1. 커버리지 (Coverage): 리프 노드의 백업된 값 $\bar{Q}(s)$를 추적합니다.
2. 새로움 (Novelty): 방문 횟수에 기반한 탐색 항 (전통적인 UCB 항) 을 추적합니다.
3. 대비 (Contrast): 토큰 수준의 엔트로피에서 유도된 형제 노드 간 결과의 다양성을 추적합니다.

저자들은 $F$가 단조롭고 서브모듈러임을 증명합니다. 이를 통해 이론적 $(1 - 1/e)$ 근사 보장을 가진 탐욕적 선택기를 사용하여 최적 확장 일정을 도출할 수 있습니다.

2.2 UUCB 선택기

서브모듈러 문제에 대한 탐욕적 해법은 불확실성 인식 상한 신뢰 구간 (Uncertainty-aware Upper Confidence Bound, UUCB) 점수를 도출합니다. 이는 임의의 휴리스틱이 아니라 목적 함수의 폐쇄형 한계 이득입니다:
$$\text{UUCB}(v) = \bar{Q}(v) + c\sqrt{\frac{\ln N(p_a(v))}{N(v)+1}} + \lambda_H \tilde{H}(v) - \lambda_C \tilde{C}(v) - \lambda_D \tilde{d}(v)$$

• $\bar{Q}(v)$: 커버리지 이득.
• 두 번째 항: 새로움 이득 (표준 UCB 탐색).
• $\lambda_H \tilde{H}(v)$: 대비 이득. 깊이가 계층화된 토큰 수준 엔트로피를 나타내며 (깊이 간 비교 가능하도록 정규화됨).
• 페널티: $\lambda_C$와 $\lambda_D$는 각각 도구 호출 비용과 확장 깊이를 페널티화하여 예산 제약을 준수합니다.

2.3 시스템 구성 요소

INFOTREE 는 UUCB 선택기를 두 가지 추가 메커니즘과 통합하여 실용적 약점을 해결합니다:

• 적응형 예산 할당기 (Adaptive Budget Allocator, ABA): 오프라인에서 훈련된 경량 MLP 로, 균일한 결과 트리 (붕괴 가능성 높음) 를 가진 프롬프트가 단일 고온 (high-temperature) 롤아웃으로 '구조'될 수 있는지 예측합니다. 예측된 구조 확률이 임계값을 초과하면 추가 롤아웃이 트리거됩니다. 이를 통해 혼합 결과 비율을 약 58% 에서 약 76% 로 높였으며, 예산 오버헤드는 5% 미만입니다.
• 추측적 확장 (Speculative Expansion): 월클럭 지연을 줄이기 위해 작업자들은 잠재적으로 구식 (stale) 인 Q-값을 사용하여 UUCB 점수를 평가합니다 (경계된 구식성). 버전 태그에 기반한 조정 단계가 확장을 수락하거나 롤백합니다. 이로 인해 오버헤드가 14.3% 에서 4.8% 로 감소했습니다.
• 계층적 이득 (Hierarchical Advantage): 루트에서 리프까지의 경로에 따른 형제 대비에서 유래한 그라디언트 신호로, 그룹 정규화 GRPO 이득을 보완하는 대안적 크레딧 할당 메커니즘을 제공합니다.

3. 주요 기여

1. 이론적 공식화: 논문은 RIFB 를 정의하고, 예산 크기와 무관하게 독립 샘플링이 어려운 프롬프트에서 지속적인 붕괴를 겪음을 증명합니다.
2. 서브모듈러 환원: 고정된 예산 하의 트리 구축이 서브모듈러 최대화 문제임을 규명하여, 탐욕적 UUCB 선택기에 대한 이론적 $(1-1/e)$ 보장을 제공합니다.
3. 해석적 유도: UUCB 의 엔트로피 보너스가 경험적 트릭이 아니라 서브모듈러 목적 함수 (대비 항) 의 해석적 결과임을 보여줍니다.
4. 시스템 설계: ABA 와 추측적 확장을 도입하여 정보성과 계산 효율성 사이의 균형을 맞추는 실용적 프레임워크를 구축했습니다.
5. 직교성: 저자들은 선택 메커니즘이 궤적 재가중 (예: CW-GRPO) 과 롤아웃 재사용 (예: Tree-GRPO 접두사 공유) 과는 직교하는 축에서 작동함을 보여주어, 구성적 이득을 가능하게 합니다.

4. 실험 결과

이 방법은 수학적 추론, 웹 검색, 도구 풍부한 코딩/OS 에이전트 분야의 9 개 벤치마크에서 평가되었습니다.

• 성능: INFOTREE 는 평탄한 GRPO, DeepSearch, Tree-GRPO, AT2PO, CW-GRPO, RC-GRPO 보다 일관되게 우수한 성능을 발휘했습니다.
  • AIME 2025에서 INFOTREE 는 Mean@32 기준 30.2를 달성했습니다 (평탄한 GRPO 는 27.7, Tree-GRPO 는 29.1).
  • GAIA에서는 **56.0%**의 정확도를 달성했습니다 (평탄한 GRPO 는 44.8%).
• 구성 가능성: INFOTREE 와 Tree-GRPO 접두사 공유 또는 CW-GRPO 기여 가중치를 결합하면 추가적인 이득이 발생하여, 접근 방식의 직교성을 확인했습니다.
• 강건성: UUCB 계수 ($\lambda_H, \lambda_C, \lambda_D$) 에 대한 $5 \times 5 \times 5$ 하이퍼파라미터 그리드 실험 결과, 공간의 75% 이상이 최적값으로부터 2.1 점 이내에 위치하여, 이 방법이 하이퍼파라미터 튜닝에 취약하지 않음을 나타냈습니다.
• 효율성: 트리 탐색에도 불구하고, 추측적 확장을 통해 월클럭 오버헤드는 4.8% 로 감소했습니다. "목표 도달 단계수 (Mean@32 가 28 에 도달하는 데 필요한 단계)"는 평탄한 GRPO 의 248 에서 INFOTREE 의 138 로 감소하여, 월클럭 시간 기준 1.57 배 개선되었습니다.
• 그라디언트 정보성: 제곱 그라디언트 노름의 직접 측정은 INFOTREE 가 평탄한 GRPO 보다 3.9 배 높은 RIFB 를 생성함을 보여줍니다.

5. 의미 및 주장

이 논문은 롤아웃 전략의 설계를 공학적 선호에서 공식적으로 근거를 둔 최적화 문제로 재위치한다고 주장합니다.

• 휴리스틱에서 이론으로: 엔트로피 보너스를 경험적 트릭에서 서브모듈러 목적 함수의 필수 구성 요소로 변환하여, 그 포함에 대한 이론적 정당성을 제공합니다.
• 붕괴 해결: 서브모듈러 선택과 적응형 예산 할당을 통해 명시적으로 '영구 그라디언트' 영역을 타겟팅함으로써, INFOTREE 는 어려운 프롬프트에서 현재 GRPO 기반 에이전트의 근본적 한계를 해결합니다.
• 상호 보완성: 결과는 트리 구축을 통한 롤아웃 정보성 극대화가 독립 샘플의 재가중 또는 다양화에 초점을 맞춘 기존 방법들과 구별되며 상호 보완적인 축임을 시사합니다.

저자들은 트리 구축 에피소드 내 고정된 정책이라는 가정과 검증 가능한 보상이 없는 개방형 작업에 대한 결과의 예비적 성격 등 한계를 지적합니다. 그러나 이 프레임워크는 희소 보상 하에서 도구 증강 에이전트를 훈련하기 위한 견고한 솔루션으로 제시됩니다.