
3.2 Learning and Scaling Reasoning 3.2.1 From Search Experience to Learning


A car needs repair. What should its owner order?
Case: choose a machine part, rather than gas or a street crossing.
Generate a rationale connecting the repair to the required part. Keep the rationale if its answer matches the label.
Fine-tune on accepted rationale–answer pairs; repeat. A failed question can be retried with the correct answer as a hint.
Adapted from the paper’s CQA example. The answer check does not certify every rationale step.
| GPT-J · CQA dev | Accuracy |
|---|---|
| Few-shot CoT | 36.6% |
| Answer-only fine-tuning | 60.0% |
| STaR + rationalization | 72.5% |
+12.5 pp over answer-only fine-tuning on this task.
Table 1 · GPT-J 6B · labeled training answers; few-shot rationale seeds. Not inference-only prompting.
Expert Iteration trains on search decisions; STaR trains on accepted rationales. Both change the policy’s parameters.






R1-Zero: Learning from Verifiable Rewards




Teaching example: solve 2x+1=2. Extract the answer before assigning credit.
| Candidate | Check against x=\frac12 | Recorded result |
|---|---|---|
| Answer: 0.5 | 2\times0.5+1=2 | Correct value |
| Answer: 1.5 | 2\times1.5+1=4\ne2 | Wrong value |
| 0.5; missing required tags | Value and format checked separately | Correct value; format failure |
Benefit: same credit for 0.5 and \frac12; no credit for 1.5.
Task: solve 2x+1=2. Reference: x=\frac12.
<think>...</think><answer>1/2</answer>
| Candidate | Answer | Tags valid? | r_{\mathrm{acc}} | r_{\mathrm{fmt}} | r_{\mathrm{demo}} |
|---|---|---|---|---|---|
| A | \frac12 | Yes | 1 | 1 | 1 |
| B | \frac32 | Yes | 0 | 1 | 0 |
| C | 0.5 | Yes | 1 | 1 | 1 |
| D | \frac12 | No think tags | 1 | 0 | 0 |
Classroom gate: r_{\mathrm{demo}}=r_{\mathrm{acc}}\,r_{\mathrm{fmt}}\;\longrightarrow\;[1,0,1,0].
Constructed candidates and a teaching-only scoring rule. This is not a claim about R1-Zero’s exact aggregation weights or parser. Correct final answers do not certify every reasoning step.
Task: return \lvert a-b\rvert for two integers.
def distance(a, b):
return a - bThe program runs normally.
Swapping the inputs reveals the bug.
Repair: return abs(a - b)
| Input | Expected | Actual |
|---|---|---|
| (5, 2) | 3 | 3 ✓ |
| (2, 5) | 3 | −3 ✗ |
| (2, 2) | 0 | 0 ✓ |
Classroom reward: all selected tests pass → 1; wrong output, runtime error or timeout → 0. Here: 0; after repair: 1.
Illustrative binary rule, not a published R1 implementation. Keep failure statuses separate; a test-system outage should be retried or excluded, not treated as evidence of incorrect code.









Apple case: a first answer says 27. Spend the next tokens rechecking 23-20+6=9.
| Illustrative allocation | Generation-token cap | Information use |
|---|---|---|
| Many shorter paths | 8\times512=4{,}096 | Explore alternatives, then select |
| One longer path | 1\times4{,}096=4{,}096 | Continue from earlier tokens |
| Combined allocation | 4\times1{,}024=4{,}096 | Combine breadth and continuation |
s1-32B / AIME24: 50.0% → 56.7% with budget forcing (Table 1). Same trained checkpoint; extra inference computation.
Apple repair and token allocations are illustrations. s1 supplies the measured result; longer thinking can also loop.








3.2 Learning and Scaling Reasoning 3.2.4 Reasoning Efficiency










DeepCoder: preserve input order in code.
AlphaProof: finish a Lean proof that can be checked.
Return the first even value: on [8, 2], sorting returns 2; scanning in order returns 8.
Measured benefit: LiveCodeBench 53.0% → 60.6% Pass@1 at a 64K cap.
DeepSeek-R1-Distill-Qwen-14B → DeepCoder-14B-Preview. Task above is illustrative; benchmark window: Aug 2024–Feb 2025.
Task: return the first even value in the original input order; otherwise None.
for x in sorted(xs): changes the order.
| Input | Required | Wrong candidate |
|---|---|---|
| [8, 2] | 8 | 2 ✗ |
| [] | None | None ✓ |
| [1, 3] | None | None ✓ |
| [1, 4, 2] | 4 | 2 ✗ |
Sorted candidate: 2 / 4 pass → reward 0.
def first_even(xs):
for x in xs:
if x % 2 == 0:
return x
return None
No sorting: 4 / 4 pass → reward 1.
All selected tests must pass for reward 1.
GRPO+ compares rewards to update the model.
Classroom illustration. Passing these tests is finite evidence.
From one repaired function to a coding benchmark: does the trained policy solve more new tasks?
| Max tokens | Starting model | DeepCoder | Change (pp) |
|---|---|---|---|
| 16K | 50.2 | 45.6 | −4.6 |
| 32K | 53.0 | 57.9 | +4.9 |
| 64K | 53.0 | 60.6 | +7.6 |
Training comparison: +4.9 points at 32K; +7.6 at 64K.
Inference comparison: DeepCoder gains 2.7 points from 32K to 64K.
LiveCodeBench Pass@1 (%), paper’s evaluation window. Matching token caps does not equal matching actual compute. Gains belong to the complete training recipe.
From b=a\cdot k and c=b\cdot l, prove a divides c: verified search produces learning data.
Case: construct a witness m with c=a\cdot m. Which candidate works: k+l or k\cdot l?
Teaching proof. System result: three IMO 2024 problems solved; manual formalization, multi-day computation.
Divisibility: b=a\cdot k and c=b\cdot l. Find m such that c=a\cdot m.
| Notation | Meaning |
|---|---|
a b c k l : Nat |
Natural numbers. |
hk : b = a * k |
A proof of this equality. |
∃ m, c = a * m |
A witness m and its equality proof. |
hk and hl are chosen proof names.
a b c k l : Nat
hk : b = a * k
hl : c = b * l
⊢ ∃ m, c = a * mAbove ⊢: available facts.
After ⊢: the goal still to prove.
A state display, not a standalone program.
⟨k * l, ?_⟩ supplies m=k\cdot l and leaves an equality to prove.
example (a b c : Nat)
(hab : ∃ k, b = a * k)
(hbc : ∃ l, c = b * l) :
∃ m, c = a * m := by
rcases hab with ⟨k, hk⟩
rcases hbc with ⟨l, hl⟩
refine ⟨k * l, ?_⟩
rw [hl, hk, Nat.mul_assoc]S_0\to S_1\to S_2: extract k and l.
S_2\to S_3: propose m=k\cdot l.
New goal: c = a * (k * l).
S_3 → complete:
c=b\cdot l=(a\cdot k)\cdot l=a\cdot(k\cdot l).
Lean 4 core. Checked classroom proof.
Same state S_2: \mathrm{hk}:b=a\cdot k, \mathrm{hl}:c=b\cdot l; goal ∃ m, c = a * m.
| Model-generated candidate | Lean feedback | Search consequence |
|---|---|---|
exact hk |
Type mismatch: an equality is not the required existential proof. |
Invalid action. Discard this candidate. |
refine ⟨k + l, ?_⟩ |
Valid move. New goal:c = a * (k + l) |
Rewriting leavesa*(k*l) = a*(k+l). |
refine ⟨k * l, ?_⟩ |
Valid move. New goal:c = a * (k * l) |
rw [hl, hk,Nat.mul_assoc] closes it. |
Another verified candidate:exact ⟨k * l, by rw [hl, hk, Nat.mul_assoc]⟩
Constructed candidates, each starting from S_2. A valid move can leave an unprovable goal.
Search finds a checked proof. Its state–tactic pairs train the next proof network.
| State | Target tactic | Return |
|---|---|---|
| S_0 | rcases hab with ⟨k, hk⟩ |
−4 |
| S_1 | rcases hbc with ⟨l, hl⟩ |
−3 |
| S_2 | refine ⟨k * l, ?_⟩ |
−2 |
| S_3 | rw [hl, hk, Nat.mul_assoc] |
−1 |
−1 per submitted tactic. Values refer to this verified path; the one-action alternative at S_2 has return −1.
Policy: token cross-entropy on the target tactic.
Value: predict the observed remaining-step return.
At the token prefix refine ⟨k:
target * has logit gradient p(\mathtt{*})-1;
alternative + has gradient p(\mathtt{+}).
Verified: the proof of the formal statement. Learned: tactic generation and proof difficulty.
Failed proof attempts are filtered from updates. The checker itself stays fixed.

AlphaProof: 3 problems. With AlphaGeometry 2: 4 / 6 · 28 / 42, silver-medal level.
Manual formalization; some solutions took days. Proofs are relative to the formal statements.
| Learning loop | R1-Zero | DeepCoder | AlphaProof |
|---|---|---|---|
| Generates | Reasoning + answer | Programs | Proof tactics |
| Checks | Answer correctness / test outcomes |
Selected tests | Lean: valid steps and complete proof |
| Signal | Accuracy + format | All pass: 1 Otherwise: 0 |
Verified proofs −1 per tactic |
| Update | GRPO | GRPO+ | Policy cross-entropy + value learning |
Independent verification provides the learning signal.
So far: verifiable feedback for code and mathematics.
| Verifier | What it checks | What must already be specified |
|---|---|---|
| Code tests | Outputs on selected inputs | Expected behavior and test coverage |
| Math answer checker | Agreement with an answer criterion | The correct answer and equivalence rules |
| Proof assistant | A proof of a formal statement | The statement and its assumptions |
Natural-language reasoning adds a missing interface:
Which facts, relations and constraints does the text express?
Next: formalize the text and delegate deduction to a symbolic solver.
Later: model uncertain facts and rules with exceptions.


