PPM 프레임워크, 긴 Horizon LLM 추론에서 sparse reward의 비효율성 해결

PPM의 핵심 아이디어와 작동 원리

**Progressive Point Matching(PPM)**은 긴 Horizon LLM 작업에서 sparse outcome reward의 비효율성을 해결하기 위해 제안된 asymptotically unbiased partial credit 할당 프레임워크다. 기존 sparse reward는 긴 Horizon에서 signal-to-noise ratio가 지수적으로 감소하여 정책 gradient 성능을 저하시킨다. 또한 기존 partial credit 방법들은 surrogate objective 하의 최적 정책이 outcome reward 하에서 최적이지 않을 수 있는 asymptotic bias를 발생시킨다.

PPM은 추론 과정을 Markovian state space를 통한 경로 탐색으로 모델링한다. Reasoning points는 reference trajectory에서 추출한 intermediate results이며, 상태는 방문한 reasoning points의 set으로 정의된다. 핵심은 Shortcutting mechanism이다. 특정 point에 의존하는 모든 point가 도달되면 해당 point도 도달한 것으로 간주하여, reference trajectory와 다른 전략으로 성공한 trajectory도 full credit을 획득할 수 있게 한다. 이를 통해 outcome reward 하에서 최적 정책을 보장한다.

성능 향상과 실험 결과

실험 결과, subproblem이 독립적일 때 PPM의 학습 속도 향상은 subtask 수(n)에 대해 지수적으로(exponentially) 증가한다. 특히 base policy가 outcome reward를 거의 항상 0으로 받는 극도로 어려운 math dataset에서, GRPO는 24시간 내 training batch 하나를 채울 궤적 샘플링이 불가능했지만 PPM은 차선 방법(POPE)보다 유의미하게 우월한 성능을 보였다.

놀라운 발견은 Length 4K 학습이 Length 8K 학습과 동등하거나 더 좋은 성능을 낸다는 점이다. 8K 학습 시 policy가 정답을 탐욕적으로 추측하며 reasoning을 일찍 종료하는 output length collapse가 발생하기 때문이다. 반면 4K 학습은 token budget 제한으로 partial progress 최적화를 유도하여 특정 태스크 레짐에서 유리하다.

한계 및 향후 방향

PPM은 unbiased하며 goal을 향한 partial progress에 비례하는 reward 할당을 목표로 한다. 일반 reasoning task에는 clean partition이 없으므로 off-the-shelf LLM으로 reasoning points를 생성해야 하며, 상당한 iteration이 필요하다. 향후에는 multiple reference trajectories 적용 시 graph 확장에 따른 cost 및 variance 증가 문제를 해결해야 한다. PPM은 imitation learning의 근사치로 해석 가능하며, non-verifiable environments에도 적용 가능할 것으로 예상된다.