Reasoning Models and Test-Time Compute

Reasoning models are large language models augmented with deliberate, extended inference-time computation—commonly manifested as explicit "chain-of-thought" traces, search trees, or iterative self-refinement loops—that allow the model to trade additional compute at test time for substantially higher answer quality. This paradigm matters because it decouples the cost of thinking from the cost of training, enabling smaller models to match or exceed larger ones on hard reasoning tasks by spending more tokens. The counterintuitive fact: a 7B-parameter model given a generous test-time compute budget can outperform a 70B model given none, meaning raw parameter count is no longer the sole axis of capability.

The core insight

The central insight is that intelligence can be amortized differently: instead of baking all reasoning into weights through expensive pretraining, you can allow a model to "think out loud" at inference time—generating intermediate steps, checking its own work, and backtracking when wrong—converting wall-clock time (or token budget) directly into accuracy. The "aha moment" is recognizing that language model generation is itself a sequential decision process, and that any technique from planning and search (beam search, MCTS, best-of-N sampling) can be applied to token sequences, not just game states. This transforms inference from a one-shot read of compressed knowledge into an active, iterative problem-solving process.

Common trapCommon Misconception

The most common mistake is assuming that longer chains of thought are always better, and therefore simply prompting a model to "think step by step" with no structural guidance is equivalent to true test-time compute scaling. In reality, unguided verbosity produces what researchers call "overthinking"—the model generates plausible-sounding intermediate text that is semantically decorative rather than computationally useful, and accuracy can decrease past an optimal token budget. The correct mental model is that test-time compute only helps when the additional computation is verifiable or steerable: either a process reward model (PRM) scores intermediate steps, a verifier checks final answers, or search is explicitly constrained—otherwise more tokens just amplify confident errors.

How It Works

The Probability Framework

A standard autoregressive LM defines a distribution over completions. At training time we maximize log-likelihood; at test time we typically take the greedy or nucleus-sampled continuation. Reasoning models intervene in this generation process to search for higher-probability correct completions rather than just high-probability completions.

Best-of-N Sampling (the simplest baseline) Given a model $\pi_\theta$ , draw $N$ independent completions and score them with a reward model $r_\phi$ :

\quad \hat{y} = \arg\max_{y^{(i)},\, i \in [N]}\; r_\phi\!\left(x,\, y^{(i)}\right), \quad y^{(i)} \sim \pi_\theta(\cdot \mid x)

Explanation: We sample N candidate answers independently and return whichever the reward model rates highest—a pure exploitation of test-time compute that requires no change to the base model. Here $x$ is the prompt, $y^{(i)}$ is the $i$ -th sampled response, $r_\phi$ is a separately trained outcome reward model (ORM), and $\hat{y}$ is the selected answer. The accuracy of Best-of-N scales roughly as $1-(1-p_1)^N$ where $p_1$ is single-sample accuracy, giving logarithmic returns.

Compute-Optimal Allocation Let $C_{\text{train}}$ be training FLOPs and $C_{\text{test}}(N, L)$ be test-time FLOPs for $N$ samples each of length $L$ tokens. For a fixed total budget $B$ , the optimal split solves:

\quad \max_{\,C_{\text{train}},\, C_{\text{test}}}\; \mathcal{A}(C_{\text{train}},\, C_{\text{test}}) \quad \text{subject to}\quad C_{\text{train}} + C_{\text{test}} \leq B

Explanation: This framing shows that training and test-time compute are substitutable resources, and the optimal balance depends on the task difficulty distribution—harder tasks favor more test-time compute per query.

Process Reward Models (PRMs) A PRM assigns a scalar to every reasoning step $s_t$ in a chain $s_1, s_2, \ldots, s_T$ :

\quad r_{\text{PRM}}(x, s_{1:T}) = \prod_{t=1}^{T} P_\phi(s_t \text{ is correct} \mid x,\, s_{1:t-1})

Explanation: By taking the product of per-step correctness probabilities, the PRM scores the entire reasoning chain and identifies the earliest incorrect step, enabling targeted search rather than discarding full rollouts.

Monte Carlo Tree Search over Token Sequences MCTS adapts naturally: the state is the current partial reasoning trace, actions are token-level or sentence-level extensions, and the value function is the PRM score. The UCB selection criterion at node $v$ with parent $u$ is:

\quad \text{UCB}(v) = Q(v) + c \cdot \sqrt{\frac{\ln N(u)}{N(v)}}

Explanation: The first term exploits high-value reasoning paths found so far, while the second term explores rarely-visited branches—balancing breadth and depth of the reasoning tree. Here $Q(v)$ is the empirical mean PRM score of completions through node $v$ , $N(u)$ and $N(v)$ are visit counts for parent and child respectively, and $c$ is an exploration constant typically tuned in $[0.5, 2.0]$ .

Outcome-Conditioned Reinforcement Learning (the DeepSeek-R1 / o1-style approach) Reasoning models trained with RL maximize expected verified reward:

\quad \mathcal{L}_{\text{GRPO}}(\theta) = \mathbb{E}_{q \sim \mathcal{D},\, \{o_i\}_{i=1}^{G} \sim \pi_{\theta_{\text{old}}}(\cdot|q)} \left[ \frac{1}{G}\sum_{i=1}^{G} \min\!\left( \rho_i \hat{A}_i,\; \text{clip}(\rho_i, 1\pm\epsilon)\hat{A}_i \right) - \beta\, D_{\text{KL}}(\pi_\theta \| \pi_{\text{ref}}) \right]

Explanation: Group Relative Policy Optimization (GRPO) samples G rollouts per question, computes advantages relative to group mean reward, clips probability ratios to prevent large policy updates, and penalizes KL divergence from a reference policy to maintain coherence—this is how DeepSeek-R1 trains its extended thinking traces. Here $\rho_i = \pi_\theta(o_i|q)/\pi_{\theta_\text{old}}(o_i|q)$ is the importance weight, $\hat{A}_i$ is the normalized group advantage, $\epsilon \approx 0.2$ is the clipping threshold, $\beta$ controls KL penalty strength, and $\pi_\text{ref}$ is the frozen reference model (typically the SFT checkpoint). ```python import torch import torch.nn.functional as F def grpo_loss( log_probs_new: torch.Tensor, # (G,) per-rollout log probs under new policy log_probs_old: torch.Tensor, # (G,) per-rollout log probs under old policy rewards: torch.Tensor, # (G,) scalar rewards (0 or 1 for math) log_probs_ref: torch.Tensor, # (G,) log probs under reference policy eps: float = 0.2, beta: float = 0.01, ) -> torch.Tensor:

# Normalize rewards to get advantages advantages = (rewards - rewards.mean()) / (rewards.std() + 1e-8)

# Importance ratios ratio = torch.exp(log_probs_new - log_probs_old)

# PPO-clip objective clipped = torch.clamp(ratio, 1 - eps, 1 + eps) policy_loss = -torch.mean(torch.min(ratio advantages, clipped advantages))

# KL penalty: KL(new || ref) ≈ log(new/ref) kl_penalty = torch.mean(log_probs_new - log_probs_ref) return policy_loss + beta * kl_penalty ```

researcher · Noam Shazeer | b. 1978 | Co-inventor of Mixture-of-Experts and key transformer components

Shazeer was a Google Brain researcher whose 2017 paper Attention Is All You Need (as a co-author) established the transformer architecture that underlies all modern reasoning models. His work on sparsely-gated mixture-of-experts demonstrated that conditional computation—activating different model subsets per input—is an early form of adaptive test-time routing, directly ancestral to reasoning model ideas. He later co-founded Character.AI after leaving Google, and his 2017 multi-query attention paper (reducing KV cache size) is a key enabler of long-context reasoning traces that would otherwise be memory-prohibitive.

researcher · Richard Sutton | b. 1949 | Foundational RL theory and the "Bitter Lesson"

Sutton is a professor at the University of Alberta and a Turing Award-adjacent figure who essentially wrote the textbook on reinforcement learning (Reinforcement Learning: An Introduction, with Barto). His 2019 essay "The Bitter Lesson" argued prophetically that methods leveraging search and learning—rather than human knowledge—always win in the long run, precisely describing the test-time compute paradigm a half-decade before it became mainstream. He developed temporal difference learning and policy gradient methods that form the mathematical substrate of GRPO and PPO used to train models like o1.

Figure

Test-Time Compute Scaling: Search Strategies

Figure

Compute Scaling: Training vs Test-Time

Intuition

The Mental Model

Imagine you're sitting an extremely hard mathematics exam under two different regimes. In the first regime, you're a savant who has memorized every theorem and simply writes the answer immediately—no scratch work, no checking. In the second, you're a careful analyst who has scratch paper and works through the problem step by step, pauses to verify each algebra manipulation, and crosses out wrong approaches before they compound into a wrong answer. The savant (large model, no test-time compute) is faster but brittle: one flawed memory and the answer is wrong with no recovery. The careful analyst (smaller model with test-time budget) is slower but robust—each intermediate step is checkable. Now imagine the analyst can clone themselves $N$ times, each pursuing a different approach in parallel, with a trusted judge evaluating which approach is most promising at each branch. That's MCTS over reasoning traces. The key insight is that knowing you're wrong partway through is the superpower—it requires a process reward model, which is what makes test-time compute genuinely powerful rather than just expensive. Think of Best-of-N as "brainstorming then picking the best draft," beam search as "writing with a planner who scores each sentence before you commit," and RL-trained reasoning models (o1, R1) as "having done so much deliberate practice that your internal draft-and-check loop is now compressed into how you write the first draft."

Historical Development

Origins · 1 minhow this was discovered

History

2016: AlphaGo (Silver et al., DeepMind) demonstrates that MCTS + neural value functions can exceed human performance in Go—an existence proof that search over discrete action spaces, guided by learned value estimates, dramatically outperforms pure policy networks. This is the conceptual template for reasoning models.

2017: The transformer architecture (Attention Is All You Need, Vaswani et al.) makes autoregressive language modeling tractable at scale, establishing token sequences as the medium over which test-time search would later be conducted.

2022 (May): Yao et al. introduce Least-to-Most Prompting and contemporaneously, Chain-of-Thought prompting (Wei et al., 2022) shows that simply prompting GPT-3 to generate intermediate steps dramatically improves multi-step math and reasoning—the first large-scale demonstration of test-time token budget → accuracy.

2022 (Nov–Dec): Self-Consistency (Wang et al.) demonstrates Best-of-N with majority voting as the verifier, achieving new SOTA on math benchmarks purely by sampling multiple CoT traces. The paper explicitly frames this as "marginalizing over reasoning paths."

2023: Tree of Thoughts (Yao et