Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning

A promising approach for improving reasoning in large language models is to use process reward models (PRMs). PRMs provide feedback at each step of a multi-step reasoning trace, potentially improving credit assignment over outcome reward models (ORMs) that only provide feedback at the final step. However, collecting dense, per-step human labels is not scalable, and training PRMs from automatically-labeled data has thus far led to limited gains. To improve a base policy by running search against a PRM or using it as dense rewards for reinforcement learning (RL), we ask:"How should we design process rewards?". Our key insight is that, to be effective, the process reward for a step should measure progress: a change in the likelihood of producing a correct response in the future, before and after taking the step, corresponding to the notion of step-level advantages in RL. Crucially, this progress should be measured under a prover policy distinct from the base policy. We theoretically characterize the set of good provers and our results show that optimizing process rewards from such provers improves exploration during test-time search and online RL. In fact, our characterization shows that weak prover policies can substantially improve a stronger base policy, which we also observe empirically. We validate our claims by training process advantage verifiers (PAVs) to predict progress under such provers, and show that compared to ORMs, test-time search against PAVs is $>8\%$ more accurate, and $1.5-5\times$ more compute-efficient. Online RL with dense rewards from PAVs enables one of the first results with $5-6\times$ gain in sample efficiency, and $>6\%$ gain in accuracy, over ORMs.

한 줄 요약

PAV(Progress Advantage Verifier)를 사용한 프로세스 보상 최적화가 테스트 타임 검색과 온라인 RL에서 정확도와 계산 효율성을 동시에 향상시킨다.

핵심 기여도

PAV는 프로버 정책 하에서의 단계별 진척(advantage)을 예측하여, 테스트 타임 검색에서 ORM 대비 8% 이상 정확도 향상과 1.5–5× 계산 효율 향상을 달성.
온라인 RL에서 PAV 기반의 밀집 보상이 ORM 대비 5–6× 샘플 효율 향상과 6% 이상 정확도 향상을 기록.
약한 프로버 정책조차도 강한 베이스 정책을 개선할 수 있음을 이론적 및 실험적으로 입증.
Pass@N 성능이 ORM 대비 5–8× 개선되어, 테스트 타임 리랭커의 상한선을 높임.

핵심 아이디어

기존의 ORMs는 단계별 피드백 없이 최종 결과에만 기반하여 학습 효율성이 낮고, PRMs는 자동 라벨링 데이터로 학습 시 제한적인 성능 향상만 보였다. 본 연구는 단계별 보상이 **진척**(progress)을 측정해야 한다는 통찰을 제시한다. 이는 단계 전후의 올바른 최종 답변 생성 확률의 변화량, 즉 RL에서의 **단계별 advantage**와 동일한 개념이다. 특히, 이 진척은 베이스 정책과 **다른 프로버 정책**(prover policy) 하에서 측정되어야 효과적이다. 이론적으로, 프로버 정책은 베이스 정책의 단계와 비교하면서도 전체적인 방향성을 유지하는 **보완적**(complementary) 정책이어야 한다. 예를 들어, Best-of-K 정책 중 K가 1보다 크지만 너무 크지 않은 경우, 베이스 정책을 개선하는 능력이 높았다. 이는 직관에 반하는 결과로, 약한 프로버도 강한 베이스 정책을 개선할 수 있음을 보여준다.

기술적 접근법

**PAV**(Process Advantage Verifier)는 프로버 정책 하에서의 단계별 advantage를 예측하는 밀집 보상 모델.
PAV 학습 데이터는 프로버 정책으로부터 **seed trace**와 **partial rollout**을 샘플링하여, 각 prefix에서의 Q-value를 추정.
학습 시 seed trace와 partial rollout의 비율을 조절하여 데이터 품질을 최적화.
프로버 정책은 베이스 정책과 다른, 단계별 advantage가 베이스 정책의 단계와 비교 가능하면서도 전체 성능과 일치하는 정책이어야 함.
RL에서 PAV 기반의 밀집 보상은 **Q^π + αA^μ** 형태로 사용, 샘플 효율성과 정확도를 동시에 향상.

주요 결과

**Gemma2 모델**(2B, 9B, 27B)에서 PAV 기반 테스트 타임 검색이 ORM 대비 **8% 이상 정확도 향상**과 **1.5–5× 계산 효율 향상**.
온라인 RL에서 PAV 기반 보상이 ORM 대비 **5–6× 샘플 효율 향상**과 **6% 이상 정확도 향상**.
Pass@N 성능이 ORM 대비 **5–8× 개선**되어, 테스트 타임 리랭커의 상한선을 높임.
학습된 PAV는 샘플링 예산이 제한된 상황에서도 **복잡한 문제 해결**을 가능하게 함.

의의 및 한계

PAV는 단계별 advantage를 기반으로 한 프로세스 보상 설계를 통해, 테스트 타임 검색과 온라인 RL 모두에서 샘플 및 계산 효율성을 동시에 향상시킨다. 특히, 약한 프로버 정책이 강한 베이스 정책을 개선할 수 있다는 사실은 기존의 프로세스 보상 설계에 대한 한계를 극복하는 중요한 통찰이다. 그러나, 프로버 정책을 자동으로 설계하는 방법은 명시되지 않았으며, PAV 학습 시 발생하는 fitting error는 성능 상한을 제한할 수 있다. 또한, 프로버 정책과 베이스 정책을 동시에 최적화하는 두 플레이어 게임 형태의 접근은 여전히 개방된 문제이다.

실용적 활용

PAV는 수학 추론, 코드 생성, 복잡한 추론 과제 등에서 테스트 타임 검색과 온라인 RL을 동시에 최적화할 수 있는 모델로 활용 가능하다. 특히, 샘플링 예산이 제한된 산업 현장에서 계산 효율성과 정확도를 동시에 요구하는 상황에 적합하다.