💬 NLP

Process Reward Informed Tree Rollout for Effective Multi-Turn RL

이 논문은 유망한 중간 상태로부터 선택적으로 분기하고 공유된 접두사를 재사용함으로써 LLM 에이전트를 위한 다회차 강화 학습을 최적화하는 프로세스-보상 가이드 적응형 트리 롤아웃 프레임워크인 PATR을 소개하며, 이를 통해 전통적인 균등 궤적 샘플링 방식과 비교하여 SWE-Bench 및 FrozenLake와 같은 벤치마크에서 성능을 크게 향상시킨다.

원저자: Xintong Li, Sha Li, Yuwei Zhang, Changlong Yu, Rongmei Lin, Hongye Jin, Shuyi Guan, Xin Liu, Linwei Li, Qingyu Yin, Jingbo Shang

게시일 2026-07-20

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Xintong Li, Sha Li, Yuwei Zhang, Changlong Yu, Rongmei Lin, Hongye Jin, Shuyi Guan, Xin Liu, Linwei Li, Qingyu Yin, Jingbo Shang

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 로봇에게 미스터리를 해결하는 법을 가르치고 있다고 상상해 보세요. 인공지능의 세계에서는 이를 **강화 학습(Reinforcement Learning, RL)**이라고 부릅니다. 이것은 강아지를 훈련시키는 것과 비슷합니다. 로봇이 어떤 과제를 수행하고, 만약 제대로 해내면 간식(보상)을 받고, 실수하면 아무것도 받지 못하는 식이죠. 시간이 흐르면서 로봇은 어떤 행동이 간식을 가져다주는지를 배우게 됩니다. 하지만 여기서 까다로운 점이 있습니다. 때때로 로봇은 간식을 맛보기 전까지 아주 길고 구불구불한 경로를 거쳐 수많은 단계를 거쳐야 할 수도 있다는 것입니다. 만약 로봇이 무작정 무작위로 움직인다면, 올바른 길을 배우기도 전에 제자리를 맴돌거나 구덩이에 빠지며 시간을 허비하게 될 수도 있습니다. 이는 컴퓨터나 웹사이트 같은 도구와 상호작용하는 AI 프로그램인 '에이전트(agent)'들에게 특히 어려운 문제입니다. 왜냐하면 문제를 해결하기 위해 하나하나 연속적인 결정을 내려야 하기 때문입니다. 과학자들이 던지는 핵심 질문은 이것입니다. 어떻게 하면 이 에이전트들이 막다른 길에서 시간을 낭비하지 않고 올바른 경로를 탐색하도록 가르칠 수 있을까요?

여기서 PATR이라는 새로운 아이디어가 등장합니다. UC 샌디에이고, 아마존, MIT의 연구진은 현재 AI 에이전트를 훈련하는 방식이 마치 산탄총을 쏘는 방식처럼 다소 무차별적이라는 점에 주목했습니다. 기존 방식은 AI에게 매번 처음부터 다시 시작하며 똑같은 과제를 반복하라고 지시합니다. 만약 AI가 초반에 루프에 빠지거나 잘못된 움직임을 보인다면, 설령 앞선 몇 단계가 꽤 괜찮았더라도 그 시도는 통째로 버려집니다. 이는 마치 피자의 빵 부분이 탔다는 이유만으로 나머지 치즈와 소스가 완벽함에도 불구하고 피자 전체를 버리는 것과 같습니다.

저자들은 이 에이전트들을 훈련하기 위한 더 똑똑한 방법인 **PATR(Process-Scorer Guided Adaptive Tree Rollout)**을 제안합니다. PATR은 매번 처음부터 다시 시작하는 대신, 가능성의 '트리(tree)'를 구축합니다. AI를 갈림길에 선 등산객이라고 상상해 보세요. 열 명의 등산객을 완전히 무작위로 서로 다른 경로로 보내는 대신, PATR은 가장 유망한 길로 먼저 보냅니다. 만약 그 길을 가는 등산객들이 아름다운 경치(즉, '좋은' 중간 단계)를 발견한다면, 시스템은 그 경로의 다른 가지들을 탐색하기 위해 더 많은 등산객을 그 길로 보냅니다. 반대로 어떤 길이 절벽으로 이어지는 것처럼 보인다면(즉, '나쁜' 단계), 시스템은 에너지를 아끼기 위해 일찍 그 길로 가는 사람들을 멈추게 합니다. 결정적으로, 시스템은 절벽에서 떨어진 등산객들의 기록도 남겨둡니다. 무엇을 하지 말아야 하는지를 아는 것이 무엇을 해야 하는지를 아는 것만큼 중요하기 때문입니다.

이 논문은 이 '트리' 방식이 훨씬 더 효율적이라고 제안합니다. 몇 단계마다 진행 상황을 살피는 스마트한 판사 역할을 하는 '스코어러(scorer, 채점자)'를 사용함으로써, 시스템은 어떤 경로를 확장하고 어떤 경로를 쳐낼지 결정할 수 있습니다. 연구진은 이 방법을 두 가지 매우 다른 도전 과제에 테스트했습니다. 하나는 에이전트가 구멍에 빠지지 않고 얼음판을 통과해야 하는 FrozenLake라는 단순한 그리드 월드 게임이고, 다른 하나는 에이전트가 소프트웨어의 버그를 수정해야 하는 훨씬 더 어려운 실제 코딩 작업인 SWE-Bench입니다.

결과는 유망했습니다. 코딩 작업에서 PATR은 표준 방식에 비해 성공률을 최대 5.0 포인트 향상시켰습니다. 단순한 게임에서는 성공률을 9.3 포인트 높였습니다. 저자들은 이 방법이 단순히 AI를 더 똑똑하게 만들 뿐만 아니라, 더 빠르게 만들고 반복적인 루프에 빠질 가능성도 줄여준다는 것을 발견했습니다. 그들은 이것이 모든 것을 즉각 해결하는 마법의 탄환은 아니지만, '프로세스 스코어러(process scorer)'를 통해 탐색을 유도하는 것이 AI 에이전트가 시간을 낭비하지 않고 길고 복잡한 과제를 해결하는 법을 가르치는 강력한 방법임을 시사한다고 강조합니다. 핵심적인 교훈은 우리의 '탐험가'들을 어디로 보낼지 선택적으로 결정함으로써, 더 적은 노력으로 더 많은 것을 배울 수 있다는 것입니다.

기술 요약: 효과적인 멀티턴 RL을 위한 프로세스 보상 기반 트리 롤아웃 (PATR)

문제 정의

강화 학습(RL)은 GRPO(Group Relative Policy Optimization) 및 RLOO와 같은 방법론을 통해 대규모 언어 모델(LLM) 에이전트를 훈련하는 표준적인 접근 방식으로 자리 잡았습니다. 그러나 이러한 인기 있는 방법들은 어드밴티지 추정(advantage estimation)을 위해 여러 개의 **독립적으로 샘플링된 완전한 궤적(complete trajectories)**에 의존합니다.

장기적 호흡의 에이전트 작업(long-horizon agentic tasks)에서, 이러한 균등한 롤아웃 전략은 두 가지 결정적인 비효율성을 초래합니다:

예산 낭비: 계산 자원이 중간 품질과 관계없이 균등하게 할당되어, 유익하지 않은 "막다른 길(dead-end)" 시도(예: 반복적인 도구 사용 루프)에 자원이 낭비됩니다.
탐색 부족: 유망한 중간 상태(intermediate states)에 대해 예산이 동적으로 재배정되지 않기 때문에 충분한 탐색이 이루어지지 않습니다.

기존의 트리 기반 방법들은 이를 해결하려고 시도하지만 종종 한계가 있습니다. 일부는 높은 엔트로피 단계나 불확실성 추정에 따라 분기(branch)를 생성하지만, 이는 작업 목표를 향한 진전(progress)을 직접 측정하지 못합니다. 또한, 일부는 턴당 탐색을 적용하여 현재 정책으로부터 롤아웃 분포를 편향시키거나 유익한 부정적 사례(negative examples)를 버리는 문제를 가집니다.

방법론: PATR

저자들은 **프로세스 스코어 가이드 적응형 트리 롤아웃(Process-Scorer Guided Adaptive Tree Rollout, PATR)**을 제안합니다. 이 프레임워크는 효과적인 탐색을 궤적 트리 내에서 어디에서 분기할지를 결정하는 문제로 재정의합니다. PATR은 독립적인 전체 궤적을 처음부터 샘플링하는 대신, 부분 궤적(partial trajectories)의 트리를 구축합니다.

핵심 메커니즘

각 훈련 인스턴스에 대해, PATR은 $B_0$ 개의 활성 브랜치(active branches)를 초기화합니다. 프로세스는 반복적으로 진행되며, 활성 브랜치를 $K$ 번의 상호작용 단계만큼 전진시킵니다. 이 간격마다, **태스크 적응형 프로세스 스코어러( $S_\phi$ )**가 부분 궤적을 평가하고 이를 세 가지 경로 중 하나로 라우팅합니다:

확장(Expansion): 높은 점수를 받은 브랜치는 동일한 중간 상태로부터 $M$ 개의 자식 연속(child continuations)을 생성하도록 선택됩니다. 이를 통해 공유된 접두사(prefix)를 재사용하면서 유망한 상태에 추가 샘플을 할당할 수 있습니다.
생존(Survival): 중간 점수를 받은 브랜치는 활성 상태를 유지하며, 다시 평가받기 위해 또 다른 $K$ 단계 동안 전진합니다.
가지치기(Pruning): 중앙값보다 현저히 낮은 점수(마진 $\alpha$ 미만)를 보이거나 퇴행적 행동(예: 동일한 동작을 $\Theta$ 번 반복)을 보이는 브랜치는 조기에 종료됩니다. 결정적으로, 이렇게 가지치기 된 브리지들은 버려지는 대신 롤아웃 그룹에 유지되어, 정책 최적화를 위한 부정적 사례(negative examples) 역할을 수행합니다.

프로세스 스코어러 인스턴스화

이 프레임워크는 특정 스코어링 메커니즘에 구애받지 않으며, 세 가지 인스턴스화를 지원합니다:

휴리스틱 스코어러(Heuristic Scorer): 제어된 환경을 위해 관찰 가능한 진전 신호(예: 목표까지의 거리, 누적 보상)를 사용합니다.
사전 학습된 PRM 스코어러(Pretrained PRM Scorer): 프로세스 보상 모델(Process Reward Model)을 활용하여 단계별 점수를 생성하고, 이를 브랜치 점수로 집계합니다.
LLM-as-Judge 스코어러: 작업별 프롬프트(예: 진단, 편집, 검증 단계)를 기반으로 부분 궤적을 평가하는 LLM을 사용하며, 견고성을 위해 경량 휴리스틱과 결적으로 결합합니다.

정책 최적화

PATR은 표준 GRPO와 호환성을 유지합니다. 프로세스 점수는 오직 롤아웃 할당(어떤 브랜치를 확장할지 결정)을 위해서만 사용됩니다. 정책 최적화 목적 함수는 변경되지 않으며, 결과적으로 생성된 트리 기반 그룹에 대해 계산된 최종 **태스크 결과 보상( $r_{out}$ )**에만 의존합니다. 이는 비균등 샘플링에 의해 도입된 편향이 학습 목적을 변경하지 않고, 오직 데이터 효율성만을 개선하도록 보장합니다.

주요 기여

PATR 프레임워크: 유망한 부분 궤적에 예산을 적응적으로 할당하고 유망하지 않은 것은 조기에 종료하는 비용 효율적인 롤아웃 생성 프레임워크를 제공합니다.
GRPO 호환성: 이 방법은 롤아웃 구축에만 프로세스 피드백을 사용하며, 정책 목적 함수와 결과 보상은 그대로 유지하여 표준 GRPO의 이론적 보장을 보존합니다.
경험적 검증: 제어된 내비게이션(FrozenLake)과 도전적인 장기 호흡 코딩 작업(SWE-Bench) 모두에서 검증되어, 독립적 롤아웃 베이스라인 대비 일관된 성능 향상을 입증했습니다.

실험 결과

저자들은 다양한 모델 규모(Qwen2.5-0.5B, 3B, Qwen3-4B)를 사용하여 FrozenLake와 SWE-Bench Verified에서 PATR을 평가했습니다.

FrozenLake: PATR은 모든 모델 규모에서 가장 높은 성공률을 달 achieved 했습니다.
- Qwen2.5-0.5B의 경우, PATR은 성공률을 GRPO의 **66.5%**에서 **75.8%**로(+9.3 포인트) 개선했습니다.
- 또한 평균 응답 길이를 더 짧게 생성하였는데, 이는 단순한 탐색 확장이 아닌 효율성 측면의 이득을 나타냅니다.
SWE-Bench: PATR 변체들은 해결률(resolved rates) 측면에서 모든 베이스라인(GRPO, DAPO, ARPO, Tree-Random)을 능가했습니다.
- PATR-PRM은 **27.2%**의 해결률을 달성하여 GRPO(22.2%)보다 +5.0 포인트 높았습니다.
- PATR-Judge 역시 모든 베이스라인(26.0%)을 앞질러, 다양한 스코어러 유형에 대한 프레임워크의 유연성을 입증했습니다.
- PATR 변체들은 DAPO 및 ARPO와 같은 베이스라인에 비해 평균 턴 수를 적게 사용하면서 더 많은 태스크 인스턴스를 완료했습니다.

훈련 역학(Training Dynamics)

훈련 곡선 분석 결과, PATR은 특히 작은 모델에서 훈련 초기 단계에 더 높은 성공률에 도달하는 것으로 나타났습니다. 이는 프로세스 가이드 분기가 이미 진전을 보이는 부분 궤적에 탐색을 집중함으로써 샘핑 효율성을 높인다는 것을 시사합니다. 또한, 가지치기 된 궤적을 롤아웃 그룹에 유지하는 것("Keep All")이 버리는 것보다 우수하다는 것이 밝혀졌는데, 이는 이들이 어드밴티지 추정을 위한 가치 있는 부정적 사례를 제공하기 때문입니다.

의의 및 주장

본 논문은 프로세스 가이드 트리 롤아웃이 확장 가능한 멀티턴 RL을 위한 효과적인 전략임을 주장합니다. 궤적을 트리 형태로 구성하고 태스크 적응형 프로세스 피드백을 사용하여 어디에서 분기할지 결정함으로써, PATR은 장기 호흡 작업에서의 균등 샘플링의 비효율성을 해결합니다.

저자들은 이 접근 방식이 실용적인 절충안을 제공한다고 강조합니다. 즉, 데이터 효율성을 높이기 위해 롤아웃 할당에 통제된 국소적 편향을 도입하면서도, 정책 최적화 목적 자체는 훼손하지 않는다는 것입니다. 결과는 품질 인식 확장(quality-aware expansion)과 함께 트리 구조 탐색을 결합하는 것이 추가적인 탐색을 신뢰할 수 있는 태스크 진전으로 전환하는 데 매우 중요하다는 점을 보여주며, 이는 SWE-Bench와 같은 복잡한 실제 코딩 에이전트 시나리오에서도 유효합니다.

한계점

저자들은 PATR가 프로세스 스코어러의 품질에 의존한다는 점을 인정하며, 부정확한 점수는 최적스럽지 못한 브랜치 확장이나 가지치기로 이어질 수 있습니다. 또한, 현재 평가는 FrozenLake와 SWE-Bench에 국한되어 있으며, 웹 내비게이션 및 임바디드 인터랙션(embodied interaction)과 같은 더 넓은 도메인에서 이 접근 방식을 검증하기 위한 추가 연구가 필요합니다.