정답 하나만 보상하면
긴 추론은 너무 늦게 배운다

수십 단계가 맞아도 마지막 한 단계가 틀리면 0점이다

LLM reasoning RL의 흔한 형태는 완전한 trajectory 끝에서 정답 여부를 판정하고 그 결과를 전체 token에 broadcast한다. 검증이 단순하다는 장점이 있지만, 길이가 늘수록 성공 trajectory가 희귀해져 exploration과 학습이 느려진다. 최악의 경우 학습 중 성공 샘플이 하나도 나오지 않아 gradient signal 자체가 사라진다.

논문의 Figure 1은 이 문제를 직관적으로 보여준다. 시뮬레이션에서는 sparse outcome reward가 한 번의 성공을 관측하기 위해 1,200만 개가 넘는 sample을 요구하는 장면을 제시한다. 반면 중간 point를 단순히 보상하는 process-style 접근은 더 빠르지만, 잘못된 hint 자체를 따라가도록 bias될 수 있다.

논리적으로 맞는 중간문장이 곧 task success를 뜻하지 않는다

기존 process reward는 각 reasoning segment의 논리적 correctness를 사람이나 LLM judge로 채점한다. 그러나 step-wise correctness가 실제 goal-reaching probability와 일치한다는 보장은 없다. 그래서 부분점수는 dense signal을 주면서도 최종 outcome objective와 다른 방향으로 policy를 끌고 갈 수 있다.

PPM은 correctness 정의를 직접 학습하는 reward/value model 대신, reference solution이 암시하는 “도달해야 할 reasoning state”를 reward anchor로 사용한다. privileged information은 policy 입력이 아니라 reward construction에만 사용되므로 fully on-policy learning을 유지한다.

Trajectory를 Markovian reasoning graph 위의 경로로 본다

PPM은 한 reasoning trajectory를 goal-reaching MDP의 경로로 해석한다. intermediate lemma나 하위문제의 해 같은 결과를 reasoning point라 부르고, 현재 state를 지금까지 도달한 reasoning point의 집합으로 표현한다.

여기서 \(\phi\)는 reference trajectory가 가진 reasoning point 중 현재 state가 몇 개를 포함하는지 세는 progress measure이다. segment \(t\)가 만드는 dense reward는 prefix progress의 증가량이다.

Figure 2의 Omni-MATH 예시는 이 값을 token 축에서 단조 증가하는 staircase로 보여준다. 성공 trajectory는 0에서 1까지 점진적으로 올라가고, reference progress에서 벗어난 trajectory는 중간에서 plateau를 만든다.

“중간점 많이 방문”이 “정답 도달”보다 더 큰 보상이 되는 오류를 막는다

단순히 방문한 point 수만 보상하면, 많은 intermediate point를 방문했지만 goal에 실패한 trajectory가 shortcut으로 goal에 성공한 trajectory보다 높은 reward를 받을 수 있다. PPM은 reasoning point 사이 prerequisite 관계를 reasoning graph로 만들고, downstream point에 도달하면 그것이 의존하는 upstream point도 사실상 달성한 것으로 처리한다.

이 shortcutting 규칙 때문에 goal에 도달하면 모든 prerequisite point가 reached로 간주된다. Proposition 4.1은 goal에 거의 확실하게 도달할 수 있는 policy가 존재한다는 가정 아래 PPM reward와 sparse outcome reward의 optimal-policy 집합이 같음을 보인다.

논문은 이를 potential shaping과 연결하지만 중요한 차이를 둔다. unsuccessful terminal state에도 terminal potential을 남기기 때문에 실패 trajectory가 만든 실제 진척을 버리지 않는다.

Reasoning point의 입자도를 조절하면 imitation과 sparse RL 사이를 연속적으로 움직인다

PPM의 설계 자유도는 “얼마나 강하게 reference를 따라갈 것인가”를 reasoning-point granularity로 조절하는 데 있다.

세 gradient estimator의 신호 대 잡음비

reasoning graph의 point 수를 \(n\), 각 point의 조건부 도달확률을 \(p\)라고 할 때 논문의 informal theorem은 다음 scaling을 제시한다.

직관은 분명하다. sparse reward에서는 모든 prerequisite를 통과해 goal까지 간 희귀한 event에 gradient가 묶인다. segment-level PPM은 각 reasoning point의 local progress와 더 직접적으로 gradient를 연결한다.

Multi-Countdown처럼 point 도달이 독립적인 경우 segment PPM의 SNR은 최선의 경우 \(\Theta(\sqrt n)\)까지 올라간다. Matrix Manipulation처럼 모든 step이 순차 의존하더라도 turn-level SNR은 \(\Theta(1)\)로 유지된다.

Y₁ ≪ Y₂ ≪ Y₃

부록은 sparse outcome gradient \(Y_1\), trajectory-level PPM \(Y_2\), segment-level PPM \(Y_3\)를 분리해 variance를 분석한다. 일반적 하한과 regularity 조건을 나누며, 핵심 결론은 segment-level credit assignment가 trajectory-level partial credit보다도 SNR 면에서 유리하다는 것이다.

Dandelion graph는 낮은 확률의 stem을 통과한 뒤 많은 leaf가 한꺼번에 reachable해지는 병적 상관구조로 worst-case를 구성한다. Hydrangea graph는 여러 depth에 correlation을 분산하며 \(\Theta(1/\log n)\) 형태의 하한 예를 만든다. 이 부록은 “PPM이 무조건 horizon과 함께 좋아진다”는 단순 주장이 아니라 reasoning graph의 reachability correlation이 실제 SNR을 결정한다는 조건을 분명히 한다.

독립 subproblem과 완전 순차 subproblem의 양 극단

Multi-Countdown은 \(n\)개의 Countdown 문제를 각각 풀어야 최종 outcome reward를 받는다. Matrix Manipulation은 회전·반사·element-wise 연산을 순서대로 적용해야 하므로 앞 단계 실패가 뒤 단계에 전파된다.

Qwen3-1.7B를 Multi-Countdown에, Qwen3-4B-Instruct를 Matrix Manipulation에 사용하고 각 turn당 512 token budget을 준다. GRPO를 공통 base method로 두고 sparse outcome, trajectory-level PPM, turn-level PPM을 비교한다.

Figure 4에서 horizon이 증가할수록 sparse outcome과 PPM의 훈련 격차가 급격히 벌어진다. Figure 8의 sequential Matrix Manipulation에서도 PPM이 horizon 증가에 따라 더 유리해지지만, 이득 증가율은 독립형 Multi-Countdown보다 느리다. 이는 이론의 graph-correlation 관점과 일치한다.

더 긴 training budget이 항상 더 좋은 것은 아니다

논문의 흥미로운 결과 중 하나는 4K로 학습한 PPM이 16K 평가에서 pass@8 0.148을 기록해 8K로 학습한 PPM의 0.125보다 높다는 점이다. 연구진은 8K training에서 output length가 줄고 policy가 답을 성급히 추측하는 greedy collapse가 생겼다고 해석한다.

PPM도 medium-length regime의 greedy collapse를 자동 해결하지는 않는다. 논문은 dataset마다 larger test-time budget 성능을 최대화하는 compute-optimal training sequence length가 존재할 가능성을 제기한다.

Sample → chunk → judge → Δprogress → token advantage → policy update

trajectory에 하나의 advantage만 주는 표준 GRPO와 달리 PPM은 segment의 상대 기여도에 따라 token advantage를 다르게 줄 수 있다. PPO나 GRPO 같은 off-the-shelf policy-gradient에 plug-and-play modification으로 구현한다.

외부 LLM 세 역할: point 생성, graph 생성, progress 판정

PPM은 policy 외 LLM을 세 곳에 쓴다. reference solution에서 rubric-like reasoning point를 만들고, 어떤 point가 다른 point를 obsolete하는지 dependency graph를 만들며, sampled prefix가 각 point를 달성했는지 판정한다.

GSM-Infinite 32개 held-out prompt에서 reasoning-point recall은 여러 judge/generator 모델이 대체로 높게 나타난다. n=24에서도 Qwen3-4B-Instruct 0.9712, Qwen3-32B 0.9591, Gemini-2.5-Flash-Lite 0.9551, Gemini-3-Flash-Preview 0.9654가 보고된다. 다만 reasoning graph 품질은 horizon 증가와 함께 저하될 수 있다고 논문은 지적한다.

POPE-hard의 oracle prefix를 0/25/50/75/100% 제공하는 calibration에서 \(\phi\)는 모델 종류에 관계없이 대략 선형으로 증가한다. 표준 rubric prompt보다 PPM용 criterion prompt의 Monte-Carlo-return rank correlation이 0.856 vs 0.768로 높았다.

Rubric는 정답 풀이를 강화하지 않고 reference에 충실해야 한다

부록 D의 reasoning-point generation prompt는 reference solution에 없는 더 강한 lemma·rigor·case를 추가하지 말라고 명시한다. 각 rubric item은 하나의 concrete yes/no requirement여야 하고, 마지막 item은 최종 결론이어야 한다.

Reasoning Graph Prompt는 later item이 earlier step의 수학적 내용을 실질적으로 subsume할 때만 makes_obsolete 관계를 만든다. 최종 answer 하나가 구체적 derivation 전체를 자동 obsolete해서는 안 된다. PPM judge는 rubric item을 서로 독립적으로 판정하고, problem/rubric 문장 자체가 아니라 sampled rollout 안의 evidence만 사용하도록 설계된다.

대조군 process reward prompt는 각 부분의 correctness를 순차적으로 검사하고 첫 오류가 나오면 이후 분석을 중단한다. POPE prompt는 reference prefix를 silent guidance로 제공한다. 이 prompt 차이는 PPM이 “local correctness”보다 “goal progress state를 이미 달성했는가”를 묻는다는 철학을 구현한다.

현재 증거의 범위는 1.7B–4B급 Qwen과 수학·synthetic reasoning 중심이다

논문 스스로 scale limitation을 인정한다. 더 큰 model, 더 큰 dataset, reference trajectory의 generalization/scalability 검증이 필요하다. 특히 extended multi-turn interaction이나 agentic coding처럼 test-time token budget이 training budget보다 몇 자릿수 더 길 수 있는 과제는 아직 실험하지 않았다.

또한 open-ended task에서 reasoning point와 progress judge는 외부 LLM에 의존한다. point가 부정확하거나 graph dependency가 잘못되면 reward 자체가 흔들린다. n 증가에 따라 reasoning graph quality가 떨어질 수 있다는 관찰도 있다.

“PPM이 장기 agent 문제를 해결했다”라고 해석하기에는 아직 이르다. 실제 tool-use agent에서는 reasoning point가 텍스트 lemma가 아니라 API state, file change, test pass, environment observation처럼 외부 상태와 연결될 수 있으며, 이 경우 state equivalence와 shortcutting의 의미를 다시 정의해야 한다.

다음 질문은 ‘무엇을 reasoning point로 만들 것인가’이다