3.2 Learning and Scaling Reasoning 3.2.1 From Search Experience to Learning



原 PPT 独立图片资源

3.2 Learning and Scaling Reasoning 3.2.1 From Search Experience to Learning

原 PPT 独立图片资源

Search Experience and Parameter Learning


原 PPT 独立图片资源
Search Experience and Parameter Learning
By perform exploration in the decoding phase:
stepwise reasoning paths are identified;
the accuracy of answers are greatly improved.
Why LLM cannot directly generate the reasoning paths?
Learning from Verifiable Feedback

Search Can Teach a Policy

A car needs repair. What should its owner order?

Turn a checked answer into training

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.

Does the next model improve?

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.

o1: Reasoning Model Overview


原 PPT 独立图片资源
o1: Reasoning Model Overview

o1: Reported Results


原 PPT 独立图片资源
o1: Reported Results
Image Source: https://www.vellum.ai/blog/analysis-openai-o1-vs-gpt-4o
原 PPT 独立图片资源
原 PPT 独立图片资源

o1: What Was Publicly Known


原 PPT 独立图片资源
o1: What Was Publicly Known
We don’t know;
Old Road Map?
Labeling amount of Supervised Thinking Data;
Supervise Finetune the Model
Apply the RLHF to improve the performance.

3.2 Learning and Scaling Reasoning 3.2.2 R1-Zero: Learning from Verifiable Rewards

R1-Zero: Learning from Verifiable Rewards


原 PPT 独立图片资源

R1-Zero: Learning from Verifiable Rewards

No supervised data needed!
Training directly on the pretrained model using RL.
https://medium.com/@lmpo/deepseek-r1-affordable-efficient-and-state-of-the-art-ai-reasoning-f293b0bd8d65
DeepSeek-R1: Affordable, Efficient, and State-of-the-Art AI Reasoning | by  LM Po | Jan, 2025 | Medium

R1-Zero: Response Structure


原 PPT 独立图片资源
R1-Zero: Response Structure
Directly prompting the pretrained model to generate the think procedure.
原 PPT 独立图片资源

R1-Zero: Accuracy and Format Rewards


原 PPT 独立图片资源
R1-Zero: Accuracy and Format Rewards
Rule based reward system:
Accuracy Rewards: Whether the response is correct. Math: rule based verification; LeetCode, complier feedback.
Format Rewards: enforces the model put thinking process between <think> and </think>;
No neural reward model:
Reward hacking;

R1-Zero: From Response to Verifiable Reward

Teaching example: solve 2x+1=2. Extract the answer before assigning credit.

r1 reward pipelineA generated response is parsed, compared with a reference or executed on tests, and assigned reward components. These become a learning signal; no gradient through the rule checker is required. Generate
Response o for task q
ExtractAnswer / code / tagsCheckReference or testsRecordReward + status
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.

R1-Zero: Math and Format Rewards

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.

R1-Zero: Code Execution Rewards

Task: return \lvert a-b\rvert for two integers.

Runs, but violates the task

def distance(a, b):
    return a - b

The program runs normally.
Swapping the inputs reveals the bug.

Repair: return abs(a - b)

Tests supply concrete evidence

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.

R1-Zero: GRPO


原 PPT 独立图片资源
R1-Zero: GRPO
GRPO(Group Relative Policy Optimization):
No critic model
Estimate the baseline from group scores.
原 PPT 独立图片资源
原 PPT 独立图片资源
10.48550/arXiv.2501.12948

R1-Zero: Response Length during Training


原 PPT 独立图片资源
R1-Zero: Response Length during Training
10.48550/arXiv.2501.12948
原 PPT 独立图片资源

R1-Zero: A Self-Checking Trace


原 PPT 独立图片资源
R1-Zero: A Self-Checking Trace
10.48550/arXiv.2501.12948
原 PPT 独立图片资源

R1-Zero: Evaluation Results


原 PPT 独立图片资源
R1-Zero: Evaluation Results
10.48550/arXiv.2501.12948
原 PPT 独立图片资源

3.2 Learning and Scaling Reasoning 3.2.3 Test-Time Scaling II: Length Control

Test-Time Compute: Length and Stopping

Apple case: a first answer says 27. Spend the next tokens rechecking 23-20+6=9.

compute revisitAt fixed model weights, a controller spends a question budget on generation, continuation and evaluation. Feedback returns to the controller; only stopping produces the final answer. This loop contains no parameter update.
Question x
Budget B
Allocate computationBranch · continue · stop
Generate with \theta
Weights stay fixed
Evaluate / selectVote · score · testfeedback or selected state → continue / stop → answer
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.

Budget Forcing: Controlling Reasoning Length


原 PPT 独立图片资源
Budget Forcing: Controlling Reasoning Length
Specifying the length of thinking in prompts: No precise control.
Forcing a maximum and/or minimum number of thinking tokens
Forcing a Maximum Token Count: Appending the end-of-thinking token delimiter early during the thinking phase. “Final Answer:” can also be appended to provide its current best answer.
Forcing a Minimum Token Count: Suppressing the generation of the end-of-thinking token delimiter. Optionally, strings such as “Wait” can be appended to the model‘s current reasoning trace, encouraging the model to reflect on its current generation.

Budget Forcing: A Worked Example


原 PPT 独立图片资源
Budget Forcing: A Worked Example
https://arxiv.org/pdf/2501.19393
原 PPT 独立图片资源

Budget Forcing: Compute and Performance


原 PPT 独立图片资源
Budget Forcing: Compute and Performance
原 PPT 独立图片资源
https://arxiv.org/pdf/2501.19393

Compute Scaling: A Schematic


原 PPT 独立图片资源
Compute Scaling: A Schematic
原 PPT 独立图片资源
https://zhuanlan.zhihu.com/p/22658624635?utm_source=chatgpt.com

3.2 Learning and Scaling Reasoning 3.2.4 Reasoning Efficiency



原 PPT 独立图片资源

3.2 Learning and Scaling Reasoning 3.2.4 Reasoning Efficiency

原 PPT 独立图片资源

Overthinking: Redundant Computation


原 PPT 独立图片资源
Overthinking: Redundant Computation
https://arxiv.org/pdf/2503.21614
原 PPT 独立图片资源
原 PPT 独立图片资源

Overthinking: Length and Performance


原 PPT 独立图片资源
Overthinking: Length and Performance
https://arxiv.org/pdf/2503.21614
原 PPT 独立图片资源

Allocating Inference Compute


原 PPT 独立图片资源
Allocating Inference Compute
https://arxiv.org/pdf/2503.21614
原 PPT 独立图片资源

Coconut: Reasoning in Latent Space


原 PPT 独立图片资源
Coconut: Reasoning in Latent Space
原 PPT 独立图片资源
https://arxiv.org/pdf/2412.06769

3.2 Learning and Scaling Reasoning 3.2.5 Code and Proof: Learning from Verification

DeepCoder: preserve input order in code.

AlphaProof: finish a Lean proof that can be checked.

DeepCoder: The Training Loop

Return the first even value: on [8, 2], sorting returns 2; scanning in order returns 8.

deepcoder trainingCoding tasks provide prompts to a policy and tests to a separate sandbox. Candidate programs are executed, outcome rewards feed a GRPO+ update, and the updated policy produces the next group. Training tasksProblem + testsChecked dataCoder policySample a groupof candidate programsCode sandboxExecute selected testsCompare outputsOutcome rewardAll pass: 1Otherwise: 0promptcodelogstests go to the runnerGRPO+ updateGroup-relative learningrewardsupdated parameters

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.

DeepCoder: Execution Feedback and Learning

Task: return the first even value in the original input order; otherwise None.

Wrong: sort before scanning

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.

Correct: scan in input order

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.

DeepCoder: Compare Matching Token Caps

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.

AlphaProof: The Learning and Search System

From b=a\cdot k and c=b\cdot l, prove a divides c: verified search produces learning data.

alphaproof trainingInformal mathematics is auto-formalized into a Lean problem curriculum. A proof network guides search in Lean; search experience trains the policy and value, improving subsequent search. Auto-formalizationInformal mathematics→ Lean statementsLean task poolFormal problemsfor trainingProver + searchPolicy / value network↔ Lean environmentSearch experienceChecked proofs+ search outcomesTrain policy & valueAlphaZero-style learninglearning targetsupdated network

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.

Lean: Proof Names and the Goal State

Divisibility: b=a\cdot k and c=b\cdot l. Find m such that c=a\cdot m.

Names and types

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.

State S_2: witnesses unpacked

a b c k l : Nat
hk : b = a * k
hl : c = b * l
⊢ ∃ m, c = a * m

Above ⊢: 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.

AlphaProof: Inside the Proof Search

alphaproof searchA Lean state contains hypotheses and goals. The policy suggests tactics, value-guided tree search chooses a branch, and Lean checks each move. Valid moves create new goals, invalid moves are rejected, and a complete proof is checked. Proof stateHypotheses + goalsNetwork + searchPropose / rank tacticsLean checksApply a valid tacticNew state / proofSubgoals or finishedvalidinvalid → another tacticremaining goals → continue

A complete Lean 4 proof

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]

Follow the construction

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.

AlphaProof: Candidates and Lean Feedback

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 leaves
a*(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.

AlphaProof: From Verified Proofs to Learning

Search finds a checked proof. Its state–tactic pairs train the next proof network.

Training targets from this path

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.

Why better candidates become likelier

Policy: token cross-entropy on the target tactic.
Value: predict the observed remaining-step return.

\mathcal L_{\mathrm{policy}}=-\sum_j\log\pi_\theta(a_j\mid s,a_{<j})
\theta\leftarrow\theta-\eta\nabla_\theta\!\left(\mathcal L_{\mathrm{policy}}+\lambda\mathcal L_{\mathrm{value}}\right)

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: Learning Gains and IMO Results

Original AlphaProof Figure 3: training outcomes, held-out solving rates and proof-finding efficiency
miniF2F-valid · fixed 4,000 simulations≈65% → 96.7%
Formal IMO · fixed ≈30% solve rate3,497 → 308 simulations · ≈11.35× fewer
IMO 2024

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 from Verifiable Feedback

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.

What Code and Math Verifiers Check

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.

Further Reading: Reasoning Models



原 PPT 独立图片资源
Further Reading: Reasoning Models
原 PPT 独立图片资源

Reference Paper: DeepSeek-R1


原 PPT 独立图片资源
Reference Paper: DeepSeek-R1
Deepseek-AI, et, al. DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning, 2025