


3.1 Reasoning Processes and Search 3.1.1 Explicit Reasoning and Decomposition

A cafeteria starts with 23 apples, uses 20 for lunch, then buys 6 more. How many remain?
Standard-prompting output in the paper:
“The answer is 27.”
Which operation went wrong?
Example from Wei et al., Figure 1; not a new model run.
GSM8K · standard few-shot prompting
| Model | Accuracy |
|---|---|
| PaLM 540B | 17.9% |
The prompt supplies question–answer examples, but no intermediate reasoning.
Wei et al., Table 2. Historical benchmark setting.
What if the examples showed how to reach the answer?
Example question: Roger has 5 tennis balls and buys 2 cans with 3 balls each. How many balls does he have?
Answer: 11.
Question → final answer
Two cans add 2\times3=6 balls.
Roger now has 5+6=11 balls.
Answer: 11.
Question → reasoning steps → answer
Apply the pattern to the apples: 23-20=3;\quad3+6=9, replacing the paper’s direct answer 27.
Few-shot CoT: change the demonstrations, keep the model weights fixed. Adapted from Wei et al., Figure 1.











A missing dependency or wrong sub-answer can propagate. No interpreter is required.
Language model: map the story to variables, operations and executable Python.
Interpreter: run the generated program and return its computed answer.
baked = 200
sold = 93 + 39
returned = 6
answer = baked - sold + returned # 74
“Returned” means +6 here. An interpreter also executes the wrong translation (-6) faithfully.
Write Python. Store the result in ans.
# Example: 5 balls + 2 cans, 3 per can.
balls = 5
new_balls = 2 * 3
ans = balls + new_balls
# New question: 23 apples; use 20
# for lunch, then buy 6. How many remain?
# Python:
Few-shot: question–program examples, then a new question with its program left blank.
Zero-shot: instruction + new question, without the worked examples.
apples = 23
remaining = apples - 20
ans = remaining + 6
Python executes the code: ans = 9.
Illustrative prompt and continuation; one demonstration shown.

3.1 Reasoning Processes and Search 3.1.2 Test-Time Scaling I: Search and Feedback


How many candidate paths or branches should we explore?
How long should we continue a path, and how many times should we revise it?
Which candidates should we keep, and when should we stop?



























Apple case: 23-20+6. A first answer says 27; the correct answer is 9.
| Control | What changes in this case | What it buys |
|---|---|---|
| Candidate breadth | Sample answers: 27, 9, 9 | Expose alternatives |
| Sequential work | Recheck 23-20=3; then +6 | Repair the arithmetic |
| Selection & stopping | Vote for 9; or execute the expression | Return a checked answer |
Learning: checked experience → update \theta → freeze \theta^{\prime} → use the same controls again.
Constructed paths, not a benchmark. A majority can still be wrong. Count all generation and checking costs.

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.




3.3 Logic and Uncertainty 3.3.1 Natural Language to Logic: Formalization and Solving
Paper example, Figure 2: order three vehicles by age.
A tractor, a convertible and a minivan have distinct age ranks.
The tractor ranks second-newest.
The minivan is newer than the convertible.
Question: Which vehicle is oldest?
Core idea: the LLM specifies variables and constraints.
A symbolic solver searches for assignments satisfying them.

The LLM uses in-context examples to generate task-specific symbols and constraints.
The CSP solver (python-constraint) returns
c=1,\quad t=2,\quad m=3.
Map rank 1 back to the answer:
the convertible is oldest.
| Step | Information passed to the next component |
|---|---|
| Execute | Send the generated formalization to its solver |
| On execution error | Return the faulty form, the error message and repair demonstrations to the LLM |
| Revise and retry | Generate a revised formalization and run the solver again |
| Stop | No execution error, or the revision limit is reached |
Paper example of an error class: an FOL variable has no binding quantifier.
Self-refinement repairs generated text at inference time.
Successful execution still requires a separate check of semantic fidelity.
GPT-4 accuracy (%) · original Table 2 · no self-refinement
| Dataset | CoT | Logic-LM | Δ pp |
|---|---|---|---|
| PrOntoQA | 98.79 | 83.20 | −15.59 |
| ProofWriter | 68.11 | 79.66 | +11.55 |
| FOLIO | 70.58 | 78.92 | +8.34 |
| LogicalDeduction | 75.25 | 87.63 | +12.38 |
| AR-LSAT | 35.06 | 43.04 | +7.98 |
Separate refinement analysis (Table 3): GPT-4 FOLIO executable rate 79.9% → 85.8%; accuracy among executable cases 80.4% → 79.9%. These are different metrics.
Every rectangle has four sides.
Anything with four sides is a shape.
Query: Must every rectangle be a shape?
LLM role: translate both premises and the query into first-order logic.
Query:
Prover9 result: True.
The premises entail the query.
CoT asks the LLM to produce the deduction.
LINC assigns semantic parsing to the LLM and deduction to Prover9.

GPT-4 / ProofWriter:
CoT 72.2% → LINC 98.3% (+26.1 pp)
GPT-4 / FOLIO:
CoT 75.3% → LINC 72.5% (−2.8 pp)
FOLIO: 182 retained validation examples; ProofWriter: 360 balanced OWA examples. FOLIO difference is not significant (paper: p=0.58). Different subsets and voting protocols prevent direct comparison with Logic-LM’s table.
| Question | Support supplied by these methods | Remaining requirement |
|---|---|---|
| What does the text mean? | Explicit formulas expose variables, conditions and scope | Check the translation against the source |
| Does the conclusion follow? | A solver checks the formal problem | Valid syntax, consistent premises and sufficient resources |
| Are the premises reliable? | The derivation is conditional on the supplied premises | Evidence about the underlying facts |
Logic-LM and LINC address formalization and deduction.
Noisy observations and rules with exceptions require an uncertainty model.

3.3 Logic and Uncertainty 3.3.2 Uncertain Evidence and Soft Rules



















Markov Random Fields












0
|
0
|
3
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
3
|

0
|
0
|
3/8
|
0
|
1
|
1/8
|
1
|
0
|
1/8
|
1
|
1
|
3/8
|









Markov Logic Networks













“张宁的父亲是李明。” Which Li Ming does the name refer to?
| Candidate | Born | Local belief |
|---|---|---|
| Li Ming A | 1965 | 0.40 |
| Li Ming B | 1998 | 0.60 |
The name and local context favor B.
Zhang Ning is already linked:
born in 1995.
The relation extractor assigns
0.90 to the father relation.
A father should be older than his child.
Conflict: B was born after the child.
Joint inference can revise the link or reject the extracted relation.
Teaching construction inspired by DeepDive-style relational inference; people, dates and numbers are illustrative.
X=1: link to A; X=0: link to B
R=1: the father relation is correct
| Grounding | Fixed age evidence | Simplified formula |
|---|---|---|
| e=A (1965) | \operatorname{Older}(A,\mathrm{child})=\mathrm{true} | R\land X\Rightarrow\mathrm{true}: always true |
| e=B (1998) | \operatorname{Older}(B,\mathrm{child})=\mathrm{false} | R\land\neg X\Rightarrow\mathrm{false}: R\Rightarrow X |
Weight 3: R\Rightarrow X. Penalize accepting the relation while linking to B.
Rejecting the relation leaves either candidate possible.
Teaching model: exactly one of A/B; child identity and birth years are fixed observations.
Use local beliefs to define unary potentials; add one relational factor.
| Evidence / preference | Formula | Weight |
|---|---|---|
| Local P(A)=0.40 | X | \theta_X=\ln\dfrac{0.4}{0.6}\approx-0.405 |
| Local P(R=1)=0.90 | R | \theta_R=\ln\dfrac{0.9}{0.1}\approx2.197 |
| Age consistency | \neg R\lor X | w=3 |
An isolated unary formula gives odds \exp(\theta)=\frac{p}{1-p}.
Once coupled, local inputs and posterior probabilities differ.
E denotes the fixed input evidence. All weights are specified for this demonstration; no learning is performed here.
Equivalent scoring: multiply local potentials, then penalize a violation.
| Link | Relation | Rule | Unnormalized mass m | Posterior |
|---|---|---|---|---|
| B · X=0 | reject · R=0 | satisfied | 0.6\times0.1=0.0600 | 12.32% |
| B · X=0 | accept · R=1 | violated | 0.6\times0.9\times e^{-3}\approx0.0269 | 5.52% |
| A · X=1 | reject · R=0 | satisfied | 0.4\times0.1=0.0400 | 8.22% |
| A · X=1 | accept · R=1 | satisfied | 0.4\times0.9=0.3600 | 73.94% |
Only “B + accept” violates the rule; its mass is multiplied by e^{-3}\approx0.0498.
Exact enumeration of the specified two-variable MLN; displayed probabilities are rounded to two decimal places.
(X^{*},R^{*})=\underset{x,r}{\arg\max}\;P(x,r\mid E)
A + accept the relation
73.94% probability of this world
Commit to both the link and the relation.
P(A\mid E)=\sum_r P(X=1,r\mid E)
8.2155\%+73.9394\%
82.15% total probability of A
Sum over accepting and rejecting the relation.
Relational consistency changes the linking belief.
Remaining uncertainty: P(B\mid E)=17.85\%.
MAP gives a complete assignment; a marginal preserves uncertainty about the other variable.
Sum over both relation states using unrounded probabilities; all numbers come from the specified teaching model.
Keep local P(A)=0.40; vary the rule or the relation evidence.
| Setting | Local P(R=1) | Rule w | Posterior P(A) | Joint MAP |
|---|---|---|---|---|
| No relation coupling | 0.90 | 0 | 40.00% | B + accept |
| Strong relation evidence | 0.90 | 3 | 82.15% | A + accept |
| Weak relation evidence | 0.10 | 3 | 42.42% | B + reject |
Strong relation evidence makes
A + accept more plausible.
Weak relation evidence allows
B + reject to remain most plausible.
MLN combines evidence; it does not force one repair.
We held weights fixed for inference. Learning those weights is a separate step.
Exact inference under three specified settings; finite soft weights allow violations, while hard constraints exclude them.

Probabilistic Soft Logic

Let a = v(A), b = v(B) ∈ [0, 1]. The last column uses a = 0.8, b = 0.6.
| Operation | Truth value | Logical meaning | Ex. |
|---|---|---|---|
| ⊥ Falsity | 0 | Always false. | 0 |
| ⊤ Truth | 1 | Always true. | 1 |
| ¬A Negation | 1 − a | “Not A”: the complement of A’s truth degree. | 0.2 |
| A ⇒ B Implication | min(1, 1 − a + b) | “If A, then B”: fully true when a ≤ b. | 0.8 |
| A ∨ B Weak OR | max(a, b) | “A or B”: take the larger truth degree. | 0.8 |
| A ∧ B Weak AND | min(a, b) | “A and B”: take the smaller truth degree. | 0.6 |
| A ⇔ B Equivalence | 1 − |a − b| | Both implications hold; fully true when a = b. | 0.8 |
| A ⊕ B Strong OR | min(1, a + b) | “A or B”: add truth degrees, capped at 1. | 1 |
| A ⊙ B Strong AND | max(0, a + b − 1) | “A and B”: subtract both shortfalls from 1, floor at 0. | 0.4 |
| A ⊖ B Difference | max(0, a − b) | A ⊙ ¬B: how much A exceeds B; violation of A ⇒ B. | 0.2 |
PSL rule AND/OR use the strong operations ⊙/⊕, usually written ∧/∨ in PSL.
The weak min/max rows are included for comparison; ⊕ here does not mean XOR.

1. Rule truth: A ⇒ B is ¬A ⊕ B, using Łukasiewicz strong OR.
t = v(A ⇒ B) = min(1, (1 − a) + b)
2. Violation is the shortfall from full truth: d = 1 − t.
d = 1 − min(1, 1 − a + b) = max(0, a − b)
a ≤ b: fully satisfied, d = 0.
Example: a = 0.6, b = 0.8 → d = 0.
a > b: penalize the gap, d = a − b.
Example: a = 0.8, b = 0.6 → d = 0.2.
3. Multiple premises: for A ⊙ B ⇒ C, let c = v(C).
L = max(0, a + b − 1), d = max(0, L − c) = max(0, a + b − c − 1)
4. Weighted loss and MAP: φi(x) = di(x)p, minimize Σi wiφi(x).
x ∈ [0, 1]n; observed values fixed. Nonnegative wi, p ∈ {1, 2}, affine hinges
and a convex feasible set give convex MAP inference. Soft truth is not P(B | A).

