Verification, Search & Speculation: PRMs, MCTS, and Medusa

In complex multi-step reasoning tasks:

• Outcome Reward Model (ORM): Evaluates r(x, y_(final)).
• Hazard: False positives (correct final answer reached via false arithmetic steps) and severe credit assignment sparsity (no guidance on which step failed).
• Process Reward Model (PRM): Evaluates step-level transitions r_(step)(x, s₁, ṡ, s_t):

r_(PRM)(y) = ∏_(t=1)^T P(Step t is valid | x, s_(<t))

Key Advantages of PRMs:

1. Precise Error Localization: Identifies the exact token or sentence where logic derailed.
2. Early Pruning in Tree Search: Cuts off unpromising reasoning branches at step 2 rather than generating 500 wasted tokens.
3. Alignment with Formal Proofs: Perfectly matches formal verification systems (Lean, Isabelle).

A student attempts a 3-step proof:

• Step 1 (Valid premises): PRM score p₁ = 0.98
• Step 2 (Flawed algebraic leap): PRM score p₂ = 0.12
• Step 3 (Lucky final answer): PRM score p₃ = 0.95

Comparison of Evaluation Methods:

• ORM Verdict: Final answer is correct arrow Reward = 1.0 (False Positive Pass).
• PRM Verdict:

Score = 0.98 × 0.12 × 0.95 = 0.1117 (Correctly Flagged as Defective)

The search harness halts generation immediately after Step 2, triggering backtracking and saving 66\% of downstream generation compute.

Foundation of modern reasoning models (OpenAI PRM800K, Qwen-Math, DeepSeek-R1).

Lightman et al. (OpenAI, 2023) published 'Let's Verify Step by Step', demonstrating that PRMs decisively outperform ORMs in mathematical reasoning.

• Lightman et al. (2023) — Let's Verify Step by Step ↗
• Uesato et al. (2022) — Solving math word problems with process- and outcome-based feedback ↗

ORMs score the destination, PRMs score the journey: verify step by step, never reward a lucky lie.

MCTS operates across four cyclic phases:

1. Selection: Traverse tree from root using PUCT action selection until reaching an unexpanded node.
2. Expansion: Sample K candidate next steps from policy π_θ(s_(t+1) | s_t).
3. Evaluation: Score the node using a Process Reward Model (PRM) or rollout policy.
4. Backpropagation: Update visit counts N(s, a) and mean value estimates Q(s, a) back up to the root.

The PUCT Action Selection Formula:

a^* = argmax_a [ Q(s, a) + U(s, a) ]

U(s, a) = c_(puct) · P(s, a) · (√(∑_(b) N(s, b))) / (1 + N(s, a))

Where Q(s, a) is the exploitation term (mean PRM score), P(s, a) is the prior policy probability, and the denominator shrinks the exploration bonus as an action is visited more frequently.

Let exploration constant c_(puct) = 2.0. Total parent visits N_(total) = 16 arrow √(N_(total)) = 4.0.

Consider two next-step reasoning thoughts:

• Thought A (Heavily Explored):
• Mean score: Q = 0.85, Prior probability: P = 0.60, Visits: N = 7.
• Exploration term: U = 2.0 × 0.60 × (4.0) / (1 + 7) = 1.20 × (4.0) / (8) = 0.60.
• PUCT Score: 0.85 + 0.60 = 1.45.
• Thought B (Rarely Explored Diamond in the Rough):
• Mean score: Q = 0.70, Prior probability: P = 0.40, Visits: N = 1.
• Exploration term: U = 2.0 × 0.40 × (4.0) / (1 + 1) = 0.80 × (4.0) / (2) = 1.60.
• PUCT Score: 0.70 + 1.60 = 2.30.

Verdict: The algorithm selects Thought B (2.30 > 1.45), choosing to explore the high-potential alternative path!

Core planning engine in AlphaGo, AlphaZero, OpenAI o1-style reasoning harnesses, and theorem-proving systems.

RocAlphaGo and AlphaZero (Silver et al., DeepMind 2016–2018) popularized PUCT, later adapted to language models by Yao et al. (Tree of Thoughts, 2023).

• Silver et al. (2017) — Mastering the game of Go without human knowledge ↗
• Yao et al. (2023) — Tree of Thoughts: Deliberate Problem Solving with Large Language Models ↗

Q exploits the known, U explores the new: balance prior odds with visit count to let the best thought through.

In standard single-shot generation, the model must map prompt x directly to final answer y:

P(y | x) = Softmax(W h_(L)(x))

Because a transformer has a constant depth L, the maximum computation allocated to derive y is strictly O(L) FLOPs.

Chain-of-Thought Compute Expansion:

By generating intermediate reasoning tokens z₁, z₂, ṡ, z_K:

P(y | x, z₁, ṡ, z_K) = ∏_(k=1)^K P(zₖ | x, z_(<k)) · P(y | x, z)

1. Compute Scaling: Total compute expands from O(L) to O(K · L) FLOPs!
2. Shannon Entropy Decay:

Let entropy H(Y) = -∑ P(y) ln P(y).

Without scratchpad: H(Y | X) ≫ 0 (high uncertainty, hallucinations).

With step-by-step grounding: H(Y | X, z₁, ṡ, z_K) → 0. Each token acts as an entropy sink, collapsing uncertainty before the final conclusion is drawn.

A complex logic question has 4 possible answers with uniform initial uncertainty:

• Direct Prediction (K=0):
• Probabilities: [0.30, 0.25, 0.25, 0.20].
• Shannon Entropy:

H₀ = -(0.30 ln 0.30 + 2 × 0.25 ln 0.25 + 0.20 ln 0.20) = 0.361 + 0.693 + 0.322 = 1.376 nats

• Model has high entropy and guesses incorrectly.
• After 3 Steps of CoT (K=30 tokens):
• Step 1 eliminates options 3 & 4 arrow H₁ = 0.693 nats.
• Step 2 verifies condition A arrow H₂ = 0.280 nats.
• Step 3 completes deduction: probabilities become [0.98, 0.01, 0.005, 0.005].

H₃ = -(0.98 ln 0.98 + 0.01 ln 0.01 + 2 × 0.005 ln 0.005) = 0.0198 + 0.0461 + 0.0530 = 0.119 nats

Entropy decayed by 91.4\%, guaranteeing an accurate final token.

Standard prompting and alignment paradigm across all frontier reasoning systems (o1, R1, Claude 3.5 Sonnet).

Wei et al. (Google Research, 2022) published 'Chain-of-Thought Prompting Elicits Reasoning in Large Language Models'.

• Wei et al. (2022) — Chain-of-Thought Prompting Elicits Reasoning in Large Language Models ↗
• Kojima et al. (2022) — Large Language Models are Zero-Shot Reasoners ↗

Tokens are thinking time: write down the steps, collapse the entropy, reach the truth.

Autoregressive decoding is memory-bandwidth bound: each token requires loading all model weights from High Bandwidth Memory (HBM) into GPU SRAM.

The Speculative Protocol:

1. Draft Phase: A small model (e.g. 124M) drafts K tokens sequentially: (x̃₁, ṡ, x̃_K).
2. Parallel Verification: The large target model (e.g. 70B) processes all K tokens in a single forward pass, extracting true probabilities P(x) for all positions.
3. Rejection Sampling Criterion:

For each token i ∈ [1, K], accept with probability:

αᵢ = min( 1, (P(xᵢ)) / (Q(xᵢ)) )

Where P(x) is the target model probability and Q(x) is the draft model probability.

1. Correction on Rejection: If token j is rejected, sample from the adjusted difference distribution:

P'(x) = norm( max(0, P(x) - Q(x)) )

This recovery step guarantees that the final generated text matches the target model's exact probability distribution as if speculative decoding never occurred!

A small draft model proposes token 'quantum' with draft probability Q = 0.40.

The large target model evaluates 'quantum' in its parallel forward pass:

• Case 1 (Target Strongly Agrees): P = 0.60.
• Acceptance probability: α = min(1, (0.60) / (0.40)) = min(1, 1.5) = 1.0 (100\% accept).
• Case 2 (Target Skeptical): P = 0.20.
• Acceptance probability: α = min(1, (0.20) / (0.40)) = 0.50 (50\% accept).
• Average Tokens Per Step: With acceptance rate α = 0.80 and K=4, the system generates an average of (1 - α^(K+1)) / (1 - α) = (1 - 0.80⁵) / (1 - 0.80) = 3.36 tokens per large-model forward pass, delivering a 2.5× to 3.0× end-to-end speedup.

Standard acceleration engine in production inference servers (vLLM, Hugging Face TGI, TensorRT-LLM).

Leviathan et al. (Google Research, 2023) and Chen et al. (DeepMind, 2023) independently published speculative decoding.

• Leviathan et al. (2023) — Fast Inference from Large Language Models via Speculative Decoding ↗
• Chen et al. (2023) — Accelerating Large Language Model Decoding with Speculative Sampling ↗

Draft fast with the small, verify once with the tall: accept with p over q, exact math guaranteed.

Speculative decoding requires hosting two distinct models in VRAM, complicating load balancing.

The Medusa Architecture (Cai et al., 2024):

1. Medusa Heads: Attach K lightweight MLP heads to the frozen base model's final hidden state h_t:

ŷ_(t+k) = MedusaHeadₖ(h_t) for k ∈ [1, K]

Each head predicts tokens at offset t+k non-autoregressively.

1. Tree Attention Candidate Expansion: The top candidates from each head are Cartesian-product combined into a tree of candidates (e.g., 64 top paths).
2. Tree Masked Verification: All candidates are evaluated in a single forward pass using custom attention masks that allow each branch to attend only to its ancestors:

M_(i, j) = 0 & if candidate j is an ancestor of candidate i \ -∞ & otherwise

The longest matching path is accepted, and weights update seamlessly.

A model with 3 Medusa heads proposes top candidates:

• Head 1 (offset +1): Top 2 candidates: `['is', 'was']`
• Head 2 (offset +2): Top 2 candidates: `['a', 'the']`
• Head 3 (offset +3): Top 1 candidate: `['great']`
• Candidate Tree Size: 2 × 2 × 1 = 4 candidate paths:

1. `['is', 'a', 'great']`
2. `['is', 'the', 'great']`
3. `['was', 'a', 'great']`
4. `['was', 'the', 'great']`

All 4 branches are verified in a single forward pass using tree attention. The model accepts path 1 (`'is a great'`), producing 3 accepted tokens in 1 forward pass!

Integrated into high-throughput enterprise serving engines (vLLM, TensorRT-LLM, SGLang).

Tianle Cai et al. (Together AI & Princeton, 2024) introduced Medusa, eliminating auxiliary draft models.

• Cai et al. (2024) — Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads ↗

Multiple heads on one body, tree attention in one pass: Medusa accelerates decoding without a second model.

A mathematical reasoning verification tree diagram in square 1:1 format on warm cream parchment (#fcf0db) with an 8px border.

Top section: Title in navy serif: "Outcome vs. Process Reward Models (ORMs vs. PRMs)". Subtitle: "Lightman et al. (OpenAI 2023): Granular step-level credit assignment for multi-step reasoning."

Middle section: A multi-step math solution trajectory:

Step 1: "2x + 6 = 14" ⟶ (Correct \checkmark)

Step 2: "2x = 8" ⟶ (Correct \checkmark)

Step 3: "x = 5" ⟶ (Arithmetic Error! ×)

Contrast two verifiers:

• Outcome Reward Model (ORM): Evaluates only the final answer (x = 5 → Fail). Provides zero feedback on where the reasoning broke down! Prone to rewarding wrong paths that stumble upon the right answer.
• Process Reward Model (PRM): Evaluates every single intermediate step independently:

Step 1: 0.99 \checkmark

Step 2: 0.98 \checkmark

Step 3: 0.02 × (Pinpoints exact error!).

Bottom section: Test-time compute: "PRMs power Best-of-N sampling and Monte Carlo Tree Search (MCTS), enabling models like OpenAI o1 to verify complex proofs."

Clear step-by-step verification markers, sharp error highlight, balanced square layout.

Every transformation preserves structural invariants while mapping coordinate spaces. When operating in high dimensions, numerical precision and computational efficiency require adhering strictly to canonical mathematical laws.

Formal derivation and peer-reviewed analysis:

Radford et al. (2019), Language Models are Unsupervised Multitask Learners, OpenAI ↗

"Process vs. Outcome Reward Models (PRMs vs. ORMs): Invariance, symmetry, and structure govern mathematical truth across continuous and discrete domains."

An inference acceleration pipeline diagram in square 1:1 format on dark slate (#0f172a) with clean timing lanes.

Top section: Title in white sans-serif: "Speculative Decoding: Draft Fast, Verify in Parallel". Subtitle in muted cyan: "Leviathan et al. (2023): Accelerating large models using a small draft model with zero distribution shift."

Middle section: Dual-lane execution timeline:

Lane 1 (Draft Model - Small 1B SLM, Ultra-Fast):

Autoregressively generates K = 4 speculative tokens sequentially in 10ms:

[Token 1, Token 2, Token 3, Token 4].

Lane 2 (Target Model - Large 70B LLM, High-Latency):

Takes all K = 4 draft tokens at once in a SINGLE parallel forward pass (evaluating all 4 positions in 25ms):

• Token 1: Accepted \checkmark
• Token 2: Accepted \checkmark
• Token 3: Rejected × (Target model samples corrected replacement Token 3*).

Result: Generated 3 verified tokens from the 70B model in the latency of a single forward pass!

Bottom section: Exact mathematical guarantee: "Modified rejection sampling guarantees that the output distribution is mathematically identical to sampling directly from the 70B model."

Crisp timing bars, clear accept/reject markers, high contrast dark theme.

Every transformation preserves structural invariants while mapping coordinate spaces. When operating in high dimensions, numerical precision and computational efficiency require adhering strictly to canonical mathematical laws.

Formal derivation and peer-reviewed analysis:

Radford et al. (2019), Language Models are Unsupervised Multitask Learners, OpenAI ↗

"Speculative Decoding: Drafting Fast, Verifying Parallel: Invariance, symmetry, and structure govern mathematical truth across continuous and discrete domains."