Atlas
kb://library/test-time-compute-reasoningstable2026-06-16

Test-time compute & reasoning (o1 / R1) — paying for thinking at inference

libraryeducationreasoningtest-time-computeo1r1grporlchain-of-thoughtself-consistencyprmverifierscaling-lawsm13

Test-time compute & reasoning (o1 / R1) — paying for thinking at inference

For NAO + anyone trying to understand why "reasoning models" suddenly got good at math and code in 2024–2025. The one-sentence version: instead of only making models bigger (train-time compute), we let them think longer (test-time compute) — generate a long internal chain of thought, sometimes branch and verify it — and accuracy keeps climbing. This article goes intuition-first, then gives the real mechanics: the self-consistency equation, the GRPO objective that trained DeepSeek-R1, the test-time scaling curves, and the verifier / process-reward machinery. It is honest about what is published (R1) versus inferred (o1, which is closed). Sourced from OpenAI's o1 post, the DeepSeek-R1 paper (and its Nature version), DeepSeekMath/GRPO, Snell et al. on compute-optimal scaling, the s1 budget-forcing paper, the self-consistency paper, and OpenAI's Let's Verify Step by Step (PRM800K).

This is the reasoning companion to [[deepseek-architecture]] (which covers the model DeepSeek built) and [[fusion-and-llm-councils]] (which is "many models at once" — a spatial sibling to this article's temporal "one model thinking longer"). Related: [[rlhf-and-alignment]], [[mixture-of-agents]], [[scaling-laws]], [[model-routing]].

What it is (intuition first)

Two ways to make a language model give a better answer:

  1. Spend more at training time. Bigger model, more data, more GPU-hours. This is the classic [[scaling-laws]] story (Kaplan, Chinchilla). It is expensive, slow, and fixed once you ship — every query, easy or hard, runs the same forward pass.
  2. Spend more at *test* time. Keep the same weights, but let the model do more work per question: write out its reasoning step by step, try several approaches, check itself, then answer. Hard questions get more compute; easy ones get less.

A toy human analogy: a person who has studied more (bigger model) answers a math olympiad problem better — but anyone answers it better if you let them scribble on scratch paper for ten minutes instead of demanding an instant reply. Test-time compute is the scratch paper.

The headline empirical fact, reported by OpenAI for o1 (Sep 2024): accuracy on the AIME math competition rises smoothly with the log of how much test-time compute the model is allowed to use — a clean, almost straight line on a log-x plot. The same post shows a second line: accuracy also rises with the log of train-time RL compute. Two knobs, two log-linear curves (OpenAI, *Learning to reason with LLMs*).

A "reasoning model" (o1, o3, DeepSeek-R1, Gemini-thinking, Qwen-QwQ) is just an ordinary autoregressive transformer that has been trained to use that scratch paper well — to produce long chains of thought that actually help, including self-correction ("wait, that's wrong, let me reconsider"). The architecture is unchanged; the behaviour is post-trained in.

Why it matters

  • It moved the frontier on hard, verifiable tasks. GPT-4o solved ~12–13% of AIME 2024; o1 jumped to ~74% pass@1 (and ~83–93% with more samples), and DeepSeek-R1 reports 79.8% pass@1 on AIME 2024, 97.3% on MATH-500, and a Codeforces Elo of 2029 (96.3rd percentile of human competitors) (DeepSeek-R1 paper; *Nature* 2025). These are competition-math / competitive-programming levels that pure scale was struggling to reach.
  • It changes the economics. Test-time compute is pay-per-query. You can dial it per request: cheap "low effort" answers for trivia, expensive "high effort" answers for a proof. Snell et al. show that on problems a small model can sometimes solve, spending test-time compute can beat a 14× larger model under matched FLOPs (arXiv:2408.03314). Inference compute can substitute for parameters.
  • It re-opened RL for LLMs as a *capability* engine, not just an alignment tool. [[rlhf-and-alignment]] used RL to make models polite; o1/R1 use RL to make them smart at reasoning, rewarding correct final answers on verifiable problems.
  • It reframed scaling. "Scaling laws" used to mean parameters and tokens. Now there is a third axis — inference compute — and a research program on how to spend it optimally per prompt.

How it works (the real mechanics)

There are three layers, and people conflate them. Keep them separate:

  1. Eliciting reasoning (prompting / decoding): chain-of-thought, self-consistency. No training.
  2. Searching / verifying at test time: best-of-N, beam search, MCTS, guided by a verifier or reward model.
  3. Training the model to reason (RL): o1-style and R1-style. This is what makes a single forward pass produce a good long CoT, so you need less of layers 1–2.

1. Chain-of-thought + self-consistency (the free lunch)

Chain-of-thought (CoT) is just: prompt the model to "think step by step" before answering. The tokens of reasoning act as a serial scratchpad — the transformer can only do a bounded amount of computation per token, so writing more tokens literally buys more compute and more intermediate state.

Self-consistency (Wang et al., 2022) turns one CoT into many. Sample k independent reasoning chains at temperature > 0, then take the majority vote on the final answer. The framing: the reasoning chain r is a latent variable, and you want the most probable answer after marginalising it out:

answer* = argmax_a  Σ_i  1[ answer(chain_i) == a ]      # majority vote
        ≈ argmax_a  P(a | question)                     # marginalising over reasoning paths r

Intuition: a hard problem has many valid routes to the one right answer but many different wrong answers, so correct answers concentrate while errors scatter. This alone gave +17.9% on GSM8K, +11.0% on SVAMP, +12.2% on AQuA over greedy CoT (arXiv:2203.11171). Self-consistency is the simplest test-time-compute method — pure sampling, no extra training, no verifier. It is also the temporal cousin of [[fusion-and-llm-councils]] / [[mixture-of-agents]] (which vote across different models rather than across samples of one model).

2. Verifiers, ORMs, and Process Reward Models (PRMs)

Majority vote is a weak aggregator. A verifier scores candidate solutions so you can pick the best one (best-of-N) or steer a search. Two flavours (OpenAI o1 primer):

  • Outcome Reward Model (ORM): scores only the final answer — "is this right?" Cheap to label (you just need the gold answer), but gives no credit for partial work and can reward a right answer reached by a lucky wrong path.
  • Process Reward Model (PRM): scores each reasoning step — "is this step valid?" OpenAI's Let's Verify Step by Step (PRM800K, ~800k human step-level labels) showed PRMs beat ORMs at selecting correct MATH solutions, and that step-level supervision is more reliable and more interpretable (arXiv:2305.20050). A PRM lets you do guided search — beam search or lookahead where you prune branches whose intermediate steps look bad, instead of waiting for the end.

Snell et al. tie this together with compute-optimal scaling: the best way to spend a fixed test-time budget depends on the problem's difficulty. On easy problems, sequential revision (let the model rewrite its own answer) wins; on hard problems, parallel search against a PRM wins. Adaptively choosing the strategy per prompt beat a naïve best-of-N baseline by >4× in compute efficiency (arXiv:2408.03314).

3. Training a model to reason — the RL recipe (o1-style, R1 published)

The big leap of o1/R1 is folding the reasoning into the weights: instead of needing N samples + a verifier at inference, train the model so that a single long CoT is usually right. The recipe is RL with a verifiable reward.

OpenAI's o1 is closed; we know only that it "is trained with RL to ... think productively using its chain of thought" and that both train-time RL and test-time thinking scale log-linearly (OpenAI). The exact algorithm, whether an explicit PRM/search is used at inference, and the reward shaping are not disclosed — treat o1 internals as informed speculation.

DeepSeek-R1 is fully published, so use it as the canonical worked example (arXiv:2501.12948). The RL algorithm is GRPO (Group-Relative Policy Optimization), from DeepSeekMath (arXiv:2402.03300). GRPO is PPO with the value network deleted — instead of a learned critic baseline, it samples a group of G answers for the same prompt and uses the group's own mean as the baseline. For prompt q, sample {o_1..o_G} from the old policy, score each with reward r_i, and compute a whitened group-relative advantage:

A_i = ( r_i − mean(r_1..r_G) ) / std(r_1..r_G)

Then optimise a clipped PPO-style surrogate with a KL leash to a reference policy:

J_GRPO = E_q, {o_i} [  (1/G) Σ_i  min( ρ_i · A_i ,  clip(ρ_i, 1−ε, 1+ε) · A_i ) ]  −  β · KL(π_θ ‖ π_ref)

   where ρ_i = π_θ(o_i | q) / π_θ_old(o_i | q)        # importance ratio

Why this matters: no critic network = roughly half the memory/compute of PPO, and the group baseline is a clean, low-variance signal for tasks where you can verify correctness. (See [[deepseek-architecture]] for GRPO in its full V2/V3/R1 context.)

The reward is rule-based, not a neural model — and that choice is the crux:

  • Accuracy reward: for math, does the boxed final answer match the gold solution? For code, does it pass the unit tests / compile? A hard, ungameable signal.
  • Format reward: did the model wrap its reasoning in <think>...</think> and put the answer where expected?

DeepSeek deliberately avoided a neural PRM/ORM for the main R1-Zero run, citing reward hacking (the policy learns to fool a learned reward model) and the cost/instability of training and maintaining a PRM at scale. Rule-based rewards can't be hacked the way a neural critic can.

R1-Zero — the striking result: starting from the base DeepSeek-V3 model with pure RL and no supervised reasoning data at all, reasoning behaviour emerged on its own — longer and longer chains of thought, self-verification, backtracking. The paper's "aha moment" is a transcript where the model literally writes "Wait, wait. Wait. That's an aha moment I can flag here. Let's reevaluate this step-by-step..." — re-deriving a result mid-solution. Nobody trained that phrasing in; the RL reward for being correct incentivised self-correction as an instrumental strategy.

Full R1 adds a multi-stage pipeline because R1-Zero, while smart, had poor readability and language-mixing: a small cold-start SFT on curated CoT data → reasoning-oriented RL (GRPO) → rejection-sampling new SFT data from the RL model → a final RL pass covering all task types. The cold start is purely about polish and generality, not about teaching reasoning — the reasoning comes from RL.

Distillation: the R1 reasoning traces were used to SFT smaller dense models (Qwen/Llama 1.5B–70B). These distilled models inherit much of the reasoning far more cheaply than running RL on a small model from scratch — strong evidence that the capability, once discovered by a large model, transfers as data.

4. The cheap-and-cheerful version: budget forcing (s1)

You don't need a billion-dollar RL run to get some test-time scaling. The s1 paper finetunes Qwen2.5-32B on just 1,000 curated reasoning traces (s1K), then controls thinking length with budget forcing: to make the model think less, force-insert the end-of-thinking token; to make it think more, suppress that token and append the word "Wait", which reliably makes the model second-guess and extend its reasoning. Appending "Wait" a few times pushed AIME24 from ~50% to ~57% — a literal demonstration of the test-time scaling curve from a one-line decoding hack (arXiv:2501.19393).

Key ideas & tradeoffs

  • Train-time vs test-time is a *substitution*, not a free win. Snell et al.: test-time compute beats a 14× bigger model only when the base model already has non-trivial success on the problem. On problems the base model never gets, no amount of thinking helps — you still need a stronger model. Thinking amplifies latent ability; it doesn't create it from nothing.
  • Verifiability is the gating constraint. o1/R1 shine on math, code, and logic because correctness is checkable (gold answer, unit tests), giving a clean RL reward and a clean test-time verifier. On open-ended tasks (essays, strategy, taste) there's no oracle — gains are smaller and harder to measure.
  • Sequential (revise) vs parallel (sample+vote/search). Self-consistency and best-of-N are parallel — embarrassingly simple, but votes saturate. A trained reasoner does sequential compute inside one chain (backtracking), which is more sample-efficient but needs the RL training to be good at it.
  • PRM vs ORM vs rule-based reward. PRMs are most informative but expensive to label and hackable; rule-based outcome rewards are ungameable but only exist for verifiable domains; DeepSeek bet on rule-based and won, which is itself a finding.
  • Latency and cost. Reasoning models can emit thousands of hidden thinking tokens before answering. Great accuracy, but slow and expensive — hence "effort" / "thinking budget" dials and the need for [[model-routing]] to send only the hard queries to the expensive thinker.

Honest caveats & open questions

  • o1's internals are not public. Everything specific about o1's algorithm, whether it runs explicit search or a PRM at inference, and its reward design is inference, not fact. R1 is the load-bearing published evidence that the recipe works; do not state o1 mechanics as established.
  • "Reasoning" is a loaded word. The chains of thought are useful serial computation, and self-correction emerges — but whether this is reasoning in a human sense, or sophisticated pattern completion that looks like reasoning, is genuinely open. The CoT is also not guaranteed faithful: the written steps may not be the true cause of the answer.
  • Underthinking / overthinking. Follow-up work (e.g. "Thoughts are all over the place") finds o1-like models sometimes thrash — switching strategies prematurely, or padding with empty "thinking" that doesn't add accuracy. More tokens ≠ monotonically better; budget forcing also saturates and can degrade.
  • Test-time scaling can be partly illusory. 2025 critiques (e.g. arXiv:2502.12215, arXiv:2507.14419) argue some reported test-time scaling is fragile — sensitive to the verifier, the benchmark, and sample budget — and doesn't always reflect a true internal scaling capability. Read scaling curves skeptically and FLOPs-matched.
  • Benchmark contamination & saturation. AIME/MATH numbers are headline-grabbing but small test sets, prone to contamination and high variance; pass@1 vs pass@k vs cons@k report very different stories. Always check which metric.
  • Reward hacking still lurks. Rule-based rewards dodge neural-RM hacking but invite their own exploits (e.g. shortcutting to the answer format without real reasoning), and language-mixing/readability collapse in R1-Zero is a symptom of optimising a narrow reward.

How it connects to OpenAlice

  • Sibling articles. This is the temporal counterpart to [[fusion-and-llm-councils]] / [[mixture-of-agents]]: a council spends compute spatially (many models, one shot); a reasoner spends it temporally (one model, many steps). Self-consistency is the bridge — it's "council of samples from one model." And [[deepseek-architecture]] is the deep dive on the model (MLA/MoE/FP8) whose R1 variant is this article's canonical RL example; GRPO is documented in both — here for reasoning, there for architecture.
  • Model routing. Reasoning models are expensive per query, so the honest production pattern is to route: cheap model for easy turns, the thinker only when a turn is hard or verifiable. That is exactly the [[model-routing]] problem, and OpenAlice's per-chat mode axes (Companion vs Worker, where Worker = "for actual work like a diploma") are a coarse version of "decide how much compute this conversation deserves."
  • Verifiable-task RL as a path to autonomous coding. OpenAlice's stated AGI direction includes autonomous repo→PR coding measured on SWE-bench. The o1/R1 lesson — RL against a rule-based, verifiable reward (tests pass / compiles) teaches genuine capability — is directly the template: a passing test suite is a ready-made, ungameable accuracy reward for an agentic coding loop.
  • Council + verifier hybrids. OpenAlice's M11 fusion/council work and an R1-style verifier could compose: sample multiple chains and score them with a process/outcome check, which is the compute-optimal recipe Snell et al. describe. Worth prototyping in the lab/bench rig before any prod wiring.

Sources