기술 요약: GraphPO - 추론 모델을 위한 그래프 기반 정책 최적화

1. 문제 정의

검증 가능한 보상(Verifiable Rewards)을 활용한 강화 학습(RLVR)은 대규모 추론 모델(LRM)을 향상시키기 위한 표준 패러다임이 되었습니다. 그러나 현재의 RLVR 방법론은 두 가지 주요 한계점에 직면해 있습니다:

1. 중복된 탐색(Redundant Exploration): 응답을 독립적으로 샘플링하면 서로 다른 궤적들이 유사한 중간 추론 단계를 포함하는 경우가 빈번합니다. 이는 계산 낭비를 초래하고 탐색의 다양성을 제한합니다.
2. 희소한 보상 신호(Sparse Reward Signals): RLVR은 일반적으로 이진 최종 답변 보상에 의존합니다. 이러한 희소성은 최종 답변에 기여하는 특정 중간 추론 단계에 크레딧(credit)을 할당하는 것을 어렵게 만듭니다.

TreeRL, PROS와 같은 트리 기반 방법들은 분기점에서의 미세한 신호 제공과 접두사(prefix) 공유를 통해 중복 문제를 일부 해결하지만, 여전히 갈라진 브랜치들을 독립적인 경로로 취급합니다. 결과적으로 서로 다른 브랜치가 의미론적으로 유사한 중간 상태에 도달하더라도 정보를 공유할 수 없으며, 이는 반복적인 탐색과 어드밴티지(advantage) 추정의 높은 분산을 초과하게 만듭니다.

2. 방법론: GraphPO

저자들은 추론 롤아웃(rollout)을 체인이나 트리가 아닌 **유향 비순환 그래프(Directed Acyclic Graph, DAG)**로 모델링하는 새로운 RL 프레임워크인 GraphPO를 제안합니다.

2.1 그래프 구축 및 병합

• 구조: GraphPO에서 추론 단계는 **에지(edge)**로 표현되며, 중간 의미 상태(프롬프트로부터 시작되는 추론 경로로부터 요약된 상태)는 **노드(node)**로 표현됩니다.
• 동등 클래스(Equivalence Classes): 이 프레임워크는 노드 임베딩(코사인 유사도 활용)을 사용하여 서로 다른 경로 간의 의미론적으로 유사한 상태를 탐지함으로써 그래프를 점진적으로 구축합니다. 유사도가 임계값 $\kappa$를 초과하면 노드들은 동등 클래스로 병합됩니다.
• 예산 재할당(Budget Reallocation): 경로가 기존의 동등 클래스에 도달하면, 추가 확장은 중복될 가능성이 높다고 판단합니다. GraphPO는 해당 경로의 다음 레이어 예산을 절반으로 줄이고(최소 한 개의 지속은 유지), 절약된 계산량을 새로운 프런티어 상태로 재할당하여 더 넓은 탐색을 장려합니다.

2.2 그래프 보상 (결과로부터의 프로세스 감독)

GraphPO는 주석이 달린 프로세스 라벨 없이도 희소한 결과 보상을 조밀한 단계별 보상으로 변환합니다:

• 상태 점수 산정(State Scoring): 각 노드는 그로부터 도달 가능한 검증된 답변을 기반으로 점수가 부여됩니다. 노드가 동등 클래스에 속하는 경우, 해당 노드의 점수는 가중치 $w$를 적용하여 해당 클래스의 다른 노드들의 점수와 풀링(pooling)됩니다.
• 단계 보상(Step Rewards): 특정 에지(단계)에 대한 보상은 목적지 노드와 출발 노드 사이의 상태 점수 차이로 계산되며, 양 끝점 사이의 유사도에 의해 할인됩니다. 이를 통해 조기에 종료된 브랜치도 정답에 성공적으로 도달한 동일 클래스의 파트너로부터 크레딧을 받을 수 있습니다.

2.3 이중 그룹 그래프 어드밴티지 (Dual-Group Graph Advantage)

추론 효율성과 크레딧 할당을 모두 개선하기 위해, GraphPO는 이중 그룹 어드밴티지 추정을 도입합니다:

1. 정확성 그룹 ($A_{cor}$): 동일한 의미 상태에서 나가는 단계들을 비교합니다. 이는 동일한 상태에서 나가는 다른 단계들과의 특정 단계의 어드밴티지를 계산하여 미세한 크레딧 할당을 제공합니다.
2. 효율성 그룹 ($A_{eff}$): 병합된 상태에 도달하는 유입 경로들을 비교합니다. 이는 유용한 의미 상태에 도달하는 더 짧은 경로(더 적은 토큰/단계)를 보상하여, 정책이 더 효율적인 추론 궤적을 찾도록 유도합니다.

2.4 정책 최적화

정책은 이중 그룹 어드밴티지($A_{dual} = A_{cor} + \lambda_{eff} A_{eff}$)를 결합한 PPO 스타일의 목적 함수를 사용하여 최적화됩니다. 이 목적 함수는 참조 정책(reference policy)에 대한 KL-다이버전스 제약을 유지하면서 기대 수익을 최대화합니다.

3. 주요 기여

• 그래프 기반 롤아웃 프레임워크: GraphPO는 추론 롤아웃을 DAG로 표현하여 접미사(suffix) 공유와 예산 재할당을 가능하게 하는 최초의 RL 프레임워크입니다.
• 이중 그룹 어드밴티지 추정: 나가는 단계들을 비교하여 추론 정확성을 최적화하고, 유입 경로를 비교하여 추론 효율성을 동시에 최적화하는 방법을 제안하여 어드밴티지 추정의 분산을 줄였습니다.
• 주석 없는 프로세스 감독: 그래프 구조와 동등 클래스를 활용하여 희소한 결과 보상으로부터 조밀한 단계별 감독을 도출함으로써, 비용이 많이 드는 프로세스 보상 모델(PRM) 주석의 필요성을 제거했습니다.

4. 실험 결과

Qwen2.5-7B-Math, Qwen3-8B-Base, Deepseek-R1-Distill-Qwen-7B의 세 가지 LLM을 대상으로 수학적 추론 벤치마크(AIME24/25, MATH500, GPQA, LiveCodeBench) 및 에이전틱 검색 작업에서 실험을 수행했습니다.

• 성능: GraphPO는 동일한 토큰 및 응답 예산 하에서 모든 모델과 데이터셋에 대해 체인 기반(GRPO, DAPO) 및 트리 기반(TreeRL, SPO, PROS, TreePO) 베이스라인보다 일관되게 우수한 성능을 보였습니다. 예를 들어, Qwen2.5-7B-Math 모델에서 GraphPO는 평균 정확도 **40.9%**를 달성하여 가장 우수한 트리 기반 베이스라인(PROS, 37.7%)을 넘어섰습니다.
• 탐색 효율성: GraphPO는 더 높은 탐색 효율성을 보여주었습니다. 즉, 더 많은 비율의 계산량이 중복된 확장 대신 유용한 추론 진행에 할당되었습니다. 또한 트리 기반 방법들이 특정 추론 패턴으로 빠르게 붕괴되는 것과 달리, 더 높은 엔트로피를 유지했습니다.
• 응답 길이: GraphPO는 동등한 상태를 병합하고 짧은 경로에 보상을 줌으로써 트리 기반 방법보다 짧은 응답을 생성하여 추론 효율성을 개선했습니다.
• 에이전틱 작업: 이 방법은 심층 검색 및 에이전틱 작업(General AI Assistant, WebWalker, BrowseComp, XBench)에서 우수한 성능을 보여, 순차적 의사 결정 과정에 대한 적용 가능성을 입증했습니다.
• PRM과의 비교: GraphPO는 추가적인 주석 데이터 없이도 PRM 기반 방법(ReasonFlux-PRM)보다 뛰어난 성능을 보였습니다.

5. 의의 및 주장

본 논문은 GraphPO가 결과 보상만으로 **자기 발생적 프로세스 감독(self-emergent process supervision)**을 얻을 수 있는 실질적인 메커니즘을 제공한다고 주장합니다. 롤아웃을 그래프로 모델링함으로써, 서로 다른 경로에 의해 도달된 동등한 상태를 표현할 수 없는 트리의 구조적 한계를 해결합니다.

저자들은 GraphPO가 다음과 같은 효과를 가진다고 단언합니다:

1. 분산 감소: 동등한 상태를 병합하고 다운스트림 증거를 풀링함으로써 어드밴티지 추정의 분산을 낮춥니다.
2. 효율성 향식: 중복된 확장으로부터 계산 예산을 재할당하여 다양한 탐색과 더 짧은 추론 경로를 향하도록 합니다.
3. 활용도 개선: 조기에 종료된 브랜치가 성공적인 동등 파트너로부터 크레딧을 받을 수 있도록 하여 롤아웃 예산의 활용도를 높이고 정책 업데이트를 안정화합니다.

이 연구는 그래프 구조의 롤아웃이 검증 가능한 보상 설정 하에서 대규모 언어 모델의 추론 능력을 확장하기 위한 강력한 대안이 될 수 있음을 시사합니다.