GraphPO: 추론 모델을 위한 그래프 기반 정책 최적화 (Graph-based Policy Optimization)

검증 가능한 보상(Verifiable Rewards, RLVR)을 활용한 강화학습 (Reinforcement Learning)은 대규모 추론 모델의 능력을 향상시키기 위한 표준 패러다임이 되었습니다. RLVR은 일반적으로 응답을 독립적으로 샘플링하고 최종 답변으로부터 정책 (Policy)을 최적화합니다. 이 패러다임에는 두 가지 한계가 있습니다. 첫째, 독립적인 응답들은 종종 유사한 중간 추론 단계를 포함하고 있어, 중복된 탐색과 계산 낭비를 초래합니다. 둘째, 희소한 최종 답변 보상 (Sparse final-answer rewards)은 유용한 단계를 식별하기 어렵게 만듭니다. 트리 기반 (Tree-based) 방식은 접두사 (Prefix)를 공유하고 동일한 접두사로부터 파생된 분기 (Branch)들을 비교함으로써 미세한 신호를 제공하여 이 문제를 부분적으로 해결합니다. 그러나 트리 분기들은 여전히 독립적으로 확장됩니다. 서로 다른 분기들이 유사한 추론 상태 (Reasoning states)에 도달하더라도, 정보를 공유할 수 없어 유사한 탐색을 반복하게 됩니다. 더욱이, 트리 기반 방식은 이러한 분산 현상을 무시하고 별개의 분기 내에서만 국소적 비교를 수행하므로, 이점 추정 (Advantage estimation)의 분산을 높일 수 있습니다. 이러한 과제를 해결하기 위해, 우리는 추론 단계를 엣지 (Edge)로, 추론 경로로부터 요약된 의미적 상태 (Semantic states)를 노드 (Node)로 하여 롤아웃 (Rollouts)을 유향 비순환 그래프 (Directed Acyclic Graph, DAG)로 표현하는 새로운 RL 프레임워크인 GraphPO (Graph-based Policy Optimization)를 제안합니다. GraphPO는 의미적으로 동일한 추론 경로들을 동치 클래스 (Equivalence classes)로 병합하여, 이들이 접미사 (Suffix)를 공유할 수 있게 하고 중복된 확장 대신 다양한 탐색으로 예산을 재할당합니다. 또한, 들어오는 엣지 (Incoming edges)에는 효율성 이점 (Efficiency advantages)을, 나가는 엣지 (Outgoing edges)에는 정확성 이점 (Correctness advantages)을 할당함으로써, 결과로부터 과정 감독 (Process supervision)을 도출하는 동시에 추론 효율성을 향상시킵니다. 이론적으로 GraphPO는 이점 추정 분산을 줄이고 추론 효율성을 높임을 보여줍니다. 추론 및 에이전트 검색 (Agentic search) 벤치마크 전반에 걸쳐 세 가지 LLM을 대상으로 한 실험 결과, GraphPO는 동일한 토큰 예산 또는 응답 예산 조건에서 체인 기반 (Chain-based) 및 트리 기반 (Tree-based) 베이스라인 모델들을 일관되게 능가함을 보여줍니다.