Abstract. Inference-time search is the family of methods that spends extra compute after a prompt arrives to generate, score, revise, and select among multiple possible outputs rather than accepting a single sampled continuation. The central claim is that test-time compute is most valuable when the task has a reliable selection signal—execution tests, formal checkers, process reward models, environment feedback, or strong judges—and much less reliable when the scoring function is weak, underspecified, or easy to exploit. This article covers best-of-N sampling, beam search, verifier-guided reranking, tree search, MCTS, language-agent tree search, Graph of Thoughts, and the emerging relationship between explicit search and reasoning models that internalize some search into hidden reasoning tokens.

Coverage note: verified through May 18, 2026.

Inference-Time Search: Algorithms for Test-Time Compute

1. Core definition

Inference-Time Search is a subset of Test-Time Compute Scaling: it allocates additional compute at inference time to improve output quality. The canonical pattern is:

Generate one or more candidate answers, partial thoughts, plans, tool actions, or program patches.
Score candidates using a verifier, reward model, language-model judge, execution result, environment feedback, heuristic, or human-provided objective.
Select or expand the best candidates under a budget.
Return the final candidate, aggregate answer, or action trajectory.

A compact abstraction is:

y*=arg⁡max⁡y∈CB(x)S(x,y)y^* = \arg\max_{y \in C_B(x)} S(x, y)y*=argy∈CB(x)maxS(x,y) where xxx is the input, CB(x)C_B(x)CB(x) is the set of candidates discovered under budget BBB, and SSS is a scoring function. This equation hides the hard parts: how candidates are generated, whether the score is reliable, whether partial states can be evaluated, and whether the search procedure spends compute on the right branches.

This family includes simple Best-of-N Sampling, Self-Consistency Decoding, Beam Search, Tree of Thoughts, Monte Carlo Tree Search, Language Agent Tree Search, Graph of Thoughts, verifier-guided decoding, and agentic tool-use loops. It does not include all inference-time optimization. For example, speculative decoding and KV-cache engineering reduce latency; they do not, by themselves, search over semantic alternatives for a better answer.

The useful mental model is: inference-time search converts generation from “draw once from the model” into “search a candidate space with a noisy proposal distribution and a possibly noisy evaluator.”

2. Why inference-time search works at all

Modern language models are not deterministic theorem provers. They are conditional generative models that place probability mass over many plausible completions. For hard tasks, a single completion may fail even when the model can sometimes produce a correct solution under different sampling, prompting, or intermediate reasoning. Inference-time search tries to exploit that latent capability.

The simplest case is a task with independent candidate success probability ppp and a perfect verifier. If we sample NNN independent candidates, the probability that at least one is correct is:

1−(1−p)N1 - (1-p)^N1−(1−p)N This is why repeated sampling can be surprisingly effective on code, math, and formal proof tasks: the model may already know how to solve some instances, but not reliably on the first try. The crucial caveat is “perfect verifier.” If the system cannot identify the correct candidate, pass@N may improve while selected pass@1 does not.

This distinction appears repeatedly in the empirical literature. Cobbe et al.’s verifier work on grade-school math framed the test-time procedure as generating many candidate solutions and choosing the one ranked highest by a learned verifier; they found that verification scaled more effectively with data than simply fine-tuning the generator in their setting. arXiv AlphaCode similarly relied on large-scale sampling followed by filtering, clustering, and reranking, achieving an average ranking in the top 54.3% of participants in simulated Codeforces contests. arXiv “Large Language Monkeys” later emphasized the same separation: coverage can scale dramatically with repeated sampling, but converting coverage into final accuracy depends on automatic verifiers, tests, reward models, or other selection mechanisms. arXiv

The reason this matters for practitioners is that sampling more is not the same as solving more. More samples buy opportunity. Scoring buys selection. Search policy buys efficient allocation.

3. The unifying framework

Most inference-time search methods differ along five axes.

3.1 Candidate unit

The candidate can be:

Candidate unit	Examples	Typical use
Full answer	best-of-N, reranking	Short answers, summaries, code solutions
Final answer after hidden reasoning	self-consistency	Math, QA, multiple-choice reasoning
Token prefix	beam search	Translation-like sequence generation, constrained decoding
Natural-language “thought”	Tree of Thoughts	Puzzle solving, decomposition, planning
Tool action or environment state	ReAct, LATS, agent search	Web navigation, embodied tasks, APIs
Program patch or proof step	verifier-guided search	Code repair, theorem proving
Graph node / intermediate artifact	Graph of Thoughts	Long synthesis, sorting, aggregation, transformation

The candidate unit determines the branching factor and the quality of partial scoring. Token-level search is fine-grained but often optimizes likelihood rather than usefulness. Thought-level and action-level search are coarser and more semantically meaningful, but require stronger evaluators.

3.2 Proposal distribution

The generator proposes candidate continuations. It may be:

the same language model used for final answers;
a smaller “policy” model;
a fine-tuned generator;
a tool-augmented agent;
a model conditioned on previous critiques or environment feedback.

A search algorithm cannot recover candidates that the proposal distribution never explores. Strong search over a weak or mode-collapsed generator can still fail. Conversely, a high-diversity generator with a strong verifier can make even crude search effective.

3.3 Scoring function

The scorer can be exact, approximate, or learned.

Scorer type	Reliability	Example
Exact checker	High	Unit tests, theorem checker, SAT solver
Environment reward	Medium to high	WebShop score, game reward, simulator feedback
Outcome verifier	Medium	“Is final answer correct?” classifier
Process reward model	Medium, sometimes stronger	Step-level math verifier
Language-model judge	Variable	Pairwise critique, rubric score
Human preference model	Variable	RLHF reward model
Model likelihood	Poor proxy for open-ended quality	Beam search log probability

The literature is blunt about this: the evaluator is often the bottleneck. OpenAI’s early RLHF summarization work trained reward models from human comparisons and then optimized against those reward models; the authors and accompanying engineering descriptions explicitly treated reward models as proxies for human preference, not ground truth. arXiv Gao et al.’s reward-model overoptimization work studied the failure mode where optimizing a proxy too aggressively damages the true objective, including in best-of-N and reinforcement-learning settings. arXiv

3.4 Search topology

The topology describes how alternatives are organized.

Flat set: generate NNN complete outputs; choose one.
Sequence frontier: maintain top token prefixes, as in beam search.
Tree: expand partial thoughts, plans, or actions.
Monte Carlo tree: use rollouts and value estimates to balance exploration and exploitation.
Graph: merge, transform, or aggregate intermediate artifacts in a non-tree structure.
Agent trajectory space: search over tool calls and observations.

The deeper the topology, the more opportunities for strategic planning—and the more ways to waste compute on bad branches.

3.5 Budget allocation

Budget can be uniform or adaptive. Uniform best-of-N spends the same amount on every prompt. Adaptive test-time compute tries to allocate more effort to prompts where extra compute is likely to help. Snell et al. analyzed test-time compute with search against process-based reward models and adaptive strategies, arguing that the value of extra compute depends strongly on prompt difficulty; their compute-optimal strategies improved efficiency over naive best-of-N in the studied settings. OpenReview A 2026 adaptive allocation paper formalized the problem as maximizing accuracy subject to an average compute constraint and reported relative accuracy gains on math benchmarks under matched budgets. arXiv

This points to a practical rule: do not spend equal search on easy, medium, and impossible prompts. Easy prompts waste extra compute; impossible prompts often waste it too. The best return usually comes from the middle band where the model has a nontrivial chance of success and the selector can recognize progress.

4. Algorithm family

4.1 Best-of-N sampling and reranking

Best-of-N Sampling is the simplest inference-time search algorithm:

Sample NNN complete answers.
Score each answer.
Return the highest-scoring answer.

It is also called rejection sampling, reranking, or verifier selection depending on the literature. Early language-model preference-learning work by Ziegler et al. used reward models trained from human comparisons and noted that optimizing learned preferences can produce strong results but can also exploit labeler heuristics. arXiv Stiennon et al.’s summarization-from-feedback work used a learned reward model to predict human-preferred summaries and then optimized against that reward model. arXiv WebGPT combined browser-assisted answer generation with human feedback and used reward-model-based rejection sampling in its training and evaluation pipeline. OpenAI

Best-of-N is attractive because it is easy to implement and parallelize. It is strongest when:

candidates are cheap to generate;
the task has a reliable scorer;
diversity is high enough that different samples explore different solution modes;
latency can be hidden with parallel generation.

Its main weakness is linear cost. If each answer costs TTT tokens, best-of-NNN costs roughly N⋅TN \cdot TN⋅T generation tokens plus scoring. At fixed wall-clock, it only stays fast if the NNN samples are generated in parallel. At fixed dollar or energy cost, it must beat either a larger model or a smaller number of higher-quality deliberative samples.

A second weakness is reward hacking. If the scorer is a learned proxy, the best of many samples may be the candidate that exploits the scorer rather than the candidate a human would prefer. That failure mode becomes worse as NNN grows because the search becomes more powerful against the proxy. arXiv

4.2 Self-consistency decoding

Self-Consistency Decoding samples multiple reasoning paths and aggregates their final answers, often by majority vote or answer marginalization. Wang et al. proposed replacing greedy chain-of-thought decoding with sampling diverse reasoning paths and marginalizing over answers; they reported gains on GSM8K, SVAMP, AQuA, StrategyQA, and ARC-Challenge. arXiv

Self-consistency differs from best-of-N in the selection rule. Best-of-N asks, “Which candidate has the highest score?” Self-consistency asks, “Which answer is most supported by independent reasoning paths?” This makes it useful when there is no high-quality verifier but final answers can be canonicalized.

It works well when:

many reasoning traces converge on the same correct answer;
wrong traces are diverse rather than correlated;
the final answer can be normalized;
the task is short enough for many samples.

It fails when wrong answers are systematically correlated. If the model has a common misconception, self-consistency can amplify it. It also struggles with long-form tasks where “majority answer” is ill-defined.

4.3 Beam search

Beam Search maintains the top BBB token prefixes according to model likelihood, expanding them step by step and pruning lower-scoring prefixes. It is a classic search algorithm for sequence generation and was historically central in machine translation and related tasks. Modern generation libraries still expose beam search, sampling, beam sampling, and related decoding strategies. Hugging Face

Beam search is not usually a good general-purpose reasoning search algorithm. Its score is typically log probability under the model, not task utility. Holtzman et al.’s “neural text degeneration” work argued that maximizing likelihood in open-ended generation can produce bland or repetitive text and that human text often does not lie on the high-probability ridge selected by maximization-based decoding. OpenReview

Beam search is still useful when the objective aligns with sequence probability or when constraints dominate:

translation-like generation;
speech recognition;
constrained formatting;
grammar-constrained decoding;
short structured outputs.

For reasoning, token-level beam search often prunes unusual but correct paths early. Thought-level beam search, where each beam item is a multi-token reasoning step or plan, is closer to Tree of Thoughts than to classical token beam search.

4.4 Verifier-guided search

Verifier-Guided Decoding uses an external or learned verifier to score candidates. The verifier may evaluate complete answers or intermediate reasoning steps.

Cobbe et al.’s math-verifier work is a canonical outcome-verifier example: generate many solutions and select with a trained verifier. arXiv OpenAI’s “Let’s Verify Step by Step” later compared outcome supervision with process supervision and reported that a process-supervised reward model solved a representative MATH subset more effectively in their setup; the work also released PRM800K, a dataset of step-level labels. arXiv

The difference matters. An outcome verifier sees the final answer or whole solution. A process reward model scores intermediate steps. Process scoring can guide search earlier, pruning bad branches before full rollouts. But it is expensive to label and can encode local preferences that do not guarantee global correctness.

Verifier-guided search is strongest when:

correctness is objective;
partial progress can be recognized;
wrong candidates are numerous but detectable;
the verifier is harder to fool than the generator.

It is weakest when:

the verifier is trained on shallow artifacts;
the task is subjective;
the search distribution drifts away from verifier training data;
the verifier rewards persuasive but false explanations.

4.5 Tree of Thoughts

Tree of Thoughts generalizes chain-of-thought prompting by searching over coherent intermediate reasoning units called “thoughts.” Instead of producing one linear chain, the model proposes multiple partial thoughts, evaluates them, and uses BFS, DFS, or similar search to explore promising branches. Yao et al. introduced Tree of Thoughts as a framework for deliberate problem solving and reported a large improvement on Game of 24 compared with chain-of-thought prompting in their experiments. arXiv

The algorithmic template is:

Decompose the task into thought steps.
Generate kkk candidate thoughts from the current state.
Score each partial state.
Keep or expand promising states.
Continue until a solution is found or budget is exhausted.

Tree of Thoughts is useful when the task has meaningful intermediate states. Puzzles, planning, symbolic manipulation, and multi-step decomposition fit this pattern better than open-ended prose. Its weakness is evaluator quality: if the model’s self-evaluation is poor, the tree search can confidently prune the right branch.

Tree search also has a budget problem. If branching factor is bbb and depth is ddd, exhaustive search is O(bd)O(b^d)O(bd). Practical ToT systems rely on aggressive pruning, shallow search, domain heuristics, or learned value functions.

4.6 Monte Carlo Tree Search and LLM hybrids

Monte Carlo Tree Search uses repeated simulations to estimate the value of actions in a tree. In classic MCTS, selection balances exploitation of high-value branches with exploration of uncertain branches; expansion adds new nodes; simulation estimates outcomes; backpropagation updates value estimates. AlphaGo made MCTS famous in neural systems by combining policy networks, value networks, and lookahead search. Nature

LLM-MCTS hybrids replace game moves with thoughts, tool actions, proof steps, or program edits. The language model proposes actions; a verifier, environment, or value model evaluates them; MCTS allocates rollouts.

Reasoning via Planning, or RAP, framed an LLM as both a reasoning policy and a world model, using MCTS to explore reasoning paths and reporting improvements on plan generation, math reasoning, and logical inference tasks. arXiv LATS integrated Monte Carlo tree search with language-model value estimates, self-reflection, and environment feedback across programming, interactive QA, web navigation, and math tasks. arXiv MCTS-DPO used tree search to collect preference data and then updated a model with direct preference optimization, reporting gains on GSM8K, MATH, and ARC-Challenge relative to its supervised fine-tuned baseline. arXiv

MCTS is attractive because it handles delayed rewards better than flat reranking. A bad-looking intermediate step may lead to a good outcome; a good-looking local step may dead-end. MCTS can, in principle, learn from rollouts rather than trusting immediate scores.

Its weaknesses are substantial:

rollouts are expensive;
value estimates are noisy;
language states are hard to canonicalize;
branching factors are large;
many tasks lack fast simulators;
backpropagated scores can be misleading if terminal rewards are sparse or hacked.

MCTS fits best when there is an environment or checker that makes rollouts meaningful: games, tool-use tasks, program execution, theorem proving, constrained planning, and some math settings.

4.7 Language-agent tree search

Language Agent Tree Search extends tree search into interactive environments. The state includes not just text but observations, tool outputs, browser pages, API responses, or environment transitions. ReAct introduced a prompting pattern that interleaves reasoning traces with actions and observations, improving performance on knowledge-intensive QA and interactive decision-making benchmarks in its reported experiments. arXiv Reflexion added verbal feedback and memory, allowing agents to learn from previous attempts without updating model weights. arXiv LATS combined these agentic ideas with MCTS-style search over action trajectories. arXiv

Agentic search is different from static answer search because the model can gather information. On factual tasks, this is often more important than “thinking harder.” A model that searches the web, calls a database, runs code, or inspects logs may outperform a model that merely samples more internal reasoning.

This class is strongest when:

actions produce reliable observations;
the environment can be reset or simulated;
failure is detectable;
exploration has bounded cost;
the final task rewards interaction, not just text generation.

It is weakest when tool calls are slow, irreversible, unsafe, or when observations are noisy and the agent lacks a reliable state representation.

4.8 Graph of Thoughts

Graph of Thoughts generalizes tree-structured reasoning into arbitrary graphs. Instead of forcing intermediate thoughts into a single chain or tree, GoT represents generated information as vertices and dependencies as edges. Thoughts can be combined, transformed, refined, compared, or aggregated. The GoT paper positioned this as a way to express richer reasoning topologies than chain-of-thought or Tree of Thoughts and reported quality and cost improvements on selected tasks such as sorting. arXiv

The graph view is natural for tasks where intermediate artifacts are reusable:

document synthesis;
multi-source comparison;
sorting or ranking;
iterative refinement;
decomposed analysis;
map-reduce style summarization;
hypothesis generation and consolidation.

Graph search is more general than tree search, but that generality is also the problem. Once arbitrary graph operations are allowed, the algorithm designer must decide which transformations are legal, when nodes should merge, how to detect redundancy, and how to score graph-level progress. GoT is promising as a design language, but its empirical base is thinner than best-of-N, self-consistency, or verifier-guided sampling.

4.9 Multi-agent debate and ensemble search

Multi-agent debate is not always described as search, but it often functions as inference-time search over arguments. Multiple model instances propose answers, critique each other, and converge on a final response. The original debate-style work reported improvements on math, strategic reasoning, and factual validity using multiple agents and rounds. arXiv

Debate is useful when critique is easier than generation and when independent agents make different errors. It is less useful when all agents share the same blind spot, when the judge is weak, or when persuasive rhetoric substitutes for correctness.

In practice, debate is best treated as one scoring-and-refinement strategy inside the broader inference-time search toolbox, not as a separate paradigm.

5. Algorithm comparison

Method	Search topology	Scorer	Cost shape	Parallelism	Best fit	Main failure mode
Single-shot sampling	None	None	1×1 \times1×	N/A	Easy tasks, low latency	No recovery from first error
Best-of-N	Flat set	Verifier, reward model, judge, heuristic	NNN full generations + scoring	High	Code, math, summarization with strong judge	Reward hacking; linear cost
Self-consistency	Flat set with answer aggregation	Agreement among sampled answers	NNN reasoning traces	High	Math, QA, canonical answers	Correlated wrong answers
Beam search	Prefix tree	Model likelihood	B⋅TB \cdot TB⋅T token expansions	Medium	Constrained sequence generation	High-probability but low-utility outputs
Verifier-guided reranking	Flat or staged	Outcome verifier	NNN candidates + verifier	High	Math, code, formal tasks	Verifier overfit or proxy exploitation
PRM-guided search	Tree	Step-level reward model	Branching search + step scoring	Medium	Long math/proof reasoning	Local scores may mislead globally
Tree of Thoughts	Thought tree	Self-eval, heuristic, verifier	O(bd)O(b^d)O(bd) worst case	Medium	Puzzles, planning, decomposable tasks	Bad pruning; evaluator weakness
MCTS hybrid	Tree with rollouts	Value model, environment, verifier	Rollouts × depth	Medium	Games, tools, code, theorem proving	Expensive rollouts; sparse reward
LATS / agent tree search	Environment trajectory tree	Environment feedback + model value	Tool calls × rollouts	Low to medium	Web, APIs, embodied/task agents	Slow, state explosion, irreversible actions
Graph of Thoughts	Arbitrary graph	Node/graph evaluator	Variable	Medium	Synthesis, aggregation, transformations	Underspecified graph operations
Debate / ensemble critique	Argument graph	Judge or consensus	Agents × rounds	Medium	Critique-heavy tasks	Persuasion over truth

The most important practical distinction is not the name of the algorithm. It is whether the system has a good enough scorer. With a strong scorer, even crude best-of-N can work. With a weak scorer, elaborate tree search can become an expensive way to select confidently wrong answers.

6. Evidence: when search beats single-shot

6.1 Verifiable domains are the strongest case

The best evidence for inference-time search comes from domains where candidate quality can be checked. Code is the cleanest example: unit tests, compilers, type checkers, linters, and execution traces provide external feedback. AlphaCode’s pipeline used massive sampling, then filtered, clustered, and reranked programs before submitting a small set of candidates. arXiv Large Language Monkeys reported that repeated sampling over code and proof tasks can produce strong coverage scaling, and that automatic verifiers are crucial for translating that coverage into selected performance. arXiv

Math is the next strongest case, but only when answer checking or verification is reliable. Self-consistency can work for problems with canonical final answers. Outcome verifiers and process reward models can improve selection and guide search, as shown in the GSM8K verifier work and later process-supervision work on MATH. arXiv

Formal proof and theorem proving fit the same pattern in principle: proof checkers provide exact feedback. The bottleneck is search space size, not ambiguity of correctness.

6.2 Weakly scored open-ended tasks are fragile

Open-ended writing, strategy, philosophical argument, and broad synthesis are harder. A reward model or LLM judge may rank candidates, but the score is an approximation of human preference or truth. The more aggressively the system searches, the more pressure it applies to that approximation.

This is the Goodhart problem for inference-time search. Best-of-N can improve summaries or answers when the reward model is aligned with human judgment, but it can also surface candidates that exploit the reward model’s blind spots. Gao et al. explicitly studied reward-model overoptimization in best-of-N and reinforcement-learning regimes. arXiv

Beam search illustrates a different scoring mismatch. It optimizes model likelihood. For open-ended text, high likelihood is not the same as quality, novelty, correctness, or usefulness. Holtzman et al.’s degeneration work is the standard warning that likelihood maximization can produce repetitive or bland generations. OpenReview

6.3 Fixed cost vs fixed wall-clock

Search can beat single-shot under a fixed quality budget while losing under a fixed latency budget. These are different questions.

At fixed dollar or token cost, the relevant comparison is: would we rather use a larger model once, a smaller model many times, a reasoning model with more internal tokens, or a search procedure with a verifier? Snell et al. studied this kind of tradeoff and found that compute-optimal test-time strategies depend on prompt difficulty and can outperform naive best-of-N in the studied settings. OpenReview Inference-scaling-law work similarly frames the problem as a tradeoff between model size and additional generated tokens under different inference strategies. OpenReview

At fixed wall-clock, parallelism dominates. Best-of-N is embarrassingly parallel: NNN candidates can be generated simultaneously if hardware is available. Tree search and MCTS are less parallel because later expansions depend on earlier evaluations, though frontier expansion and rollout batches can still be parallelized. AlphaCode is an extreme example of using large-scale parallel compute to fit many generations into a contest-like setting. arXiv

Most papers do not fully normalize for real production wall-clock, queueing, hardware saturation, cache effects, and scoring latency. Claims that a search method is “better” should therefore be read as benchmark- and budget-specific unless the comparison explicitly fixes tokens, FLOPs, dollars, and latency.

6.4 Task difficulty is decisive

The emerging scaling picture is not “more test-time compute always helps.” It is more conditional:

Easy prompts often need no search.
Medium prompts are where search has the highest marginal value.
Extremely hard prompts may not benefit if the model almost never samples a correct path or the verifier cannot identify it.

Snell et al. made this prompt-difficulty dependence central to their analysis. OpenReview A later large-scale study of test-time scaling strategies reported that no single strategy dominates across all models, tasks, difficulties, and budgets. arXiv

Knowledge-intensive tasks are a particularly important caveat. A 2025 study of reasoning models on knowledge-intensive benchmarks found that increasing test-time compute did not consistently improve accuracy and could increase hallucinations, even though “thinking” models could still outperform non-thinking baselines in some comparisons. arXiv The practical interpretation is simple: if the missing ingredient is external information, search over internal reasoning is the wrong tool. Use retrieval, tools, databases, or citations.

7. Relationship to reasoning models

Reasoning Models change the role of explicit inference-time search but do not eliminate it.

OpenAI described o1-style models as trained with reinforcement learning to spend more time reasoning before answering, with performance improving as more train-time RL and more test-time thinking are applied. OpenAI Current OpenAI API documentation describes reasoning models as using hidden reasoning tokens, exposes reasoning-effort controls, and notes that these internal tokens are billed as output tokens and occupy context even though they are not directly visible to the developer. OpenAI Developers

This is an internalized form of test-time compute. Instead of an external loop sampling candidates and scoring them, the model spends hidden tokens to plan, check, revise, or decompose before producing visible output. The exact internal algorithm is not public; it is not safe to assume that hidden reasoning tokens implement literal beam search, MCTS, or Tree of Thoughts. The defensible claim is weaker and more useful: reasoning models learn policies that use extra inference-time computation to improve outputs.

This creates several design choices.

7.1 Internal reasoning vs external search

Dimension	Internal reasoning tokens	Explicit inference-time search
Control	Coarse knobs such as reasoning effort	Direct control over samples, scorer, topology, budget
Visibility	Often hidden or summarized	Candidate traces can be logged and audited
Parallelism	Mostly sequential within one model call	Many candidates can be generated in parallel
Scoring	Learned internal criteria	External verifiers, tests, judges, tools
Integration	Simple API call	More engineering complexity
Best use	General reasoning, low-friction improvement	Verifiable tasks, high-stakes selection, tool workflows

Reasoning models reduce the need for explicit search on many everyday tasks. A single high-effort call may outperform elaborate prompting around a weaker model. But explicit search remains valuable when the external system has a scorer that the model does not have internally: unit tests, theorem checkers, database queries, simulators, human review, or domain-specific constraints.

7.2 Reasoning models can be nodes inside search

A reasoning model can also be used as the generator, evaluator, or both. For example:

best-of-N over high-effort reasoning traces;
self-consistency over reasoning-model outputs;
verifier-guided selection among reasoning-model candidates;
tool-using agent search where each node calls a reasoning model;
adaptive compute policies that choose reasoning effort per prompt.

This can be expensive, but it is conceptually clean. Reasoning tokens are one form of test-time compute; explicit search is another. A production system can mix them.

7.3 Distillation pressure

Successful search traces can be distilled into future models. This has happened repeatedly in machine learning: expensive inference procedures generate data, then a model is trained to imitate the improved behavior. MCTS-DPO is one example in the LLM setting, using MCTS-generated preferences to improve a model with preference optimization. arXiv

This creates a moving boundary. Today’s explicit search may become tomorrow’s learned reasoning policy. But as tasks become harder or more tool-dependent, external search reappears at the new frontier.

8. Choosing an algorithm by task class

8.1 Code generation and repair

Use best-of-N + execution feedback as the default. Generate diverse candidates, run tests, rank by pass/fail, then use secondary criteria such as simplicity, coverage, style, or static analysis. If tests are incomplete, add mutation tests, hidden tests, or model-based review; otherwise search may overfit visible tests.

For difficult bugs, use iterative repair: generate a patch, run tests, feed back failures, branch on alternative diagnoses, and keep a search tree of attempts. MCTS or LATS-style search becomes useful when actions have delayed effects and when execution feedback is available after each patch.

Recommended pattern:

Generate NNN candidate patches.
Execute tests and static checks.
Cluster equivalent patches.
Repair failing but promising candidates.
Select the simplest passing candidate.
Use a model or human review for underspecified behavior.

8.2 Math reasoning

For short math problems with canonical answers, start with self-consistency or best-of-N with answer checking. For harder multi-step problems, use verifier-guided search or process reward models when available. Tree of Thoughts can help when the problem decomposes into meaningful intermediate states, but it needs a scoring function stronger than naive self-evaluation.

Recommended pattern:

easy-to-medium problems: sample multiple chains, normalize final answers, majority vote;
medium-to-hard problems: use outcome verifier or PRM reranking;
long derivations: combine step-level scoring with tree search;
contest-style problems: use tool support where allowed, such as symbolic algebra or numeric checking.

Do not assume that longer reasoning is always better. Longer traces can introduce errors, rationalizations, or hallucinated lemmas.

8.3 Formal proof and symbolic tasks

Use search with exact checkers. The checker is the source of truth; the model is the proposal distribution. Best-of-N may work for short proofs or tactics. Tree search and MCTS become more relevant when partial proof states can be evaluated and expanded.

The main engineering problem is not scoring; it is candidate generation and state-space explosion.

8.4 Factual question answering

Use retrieval and tool calls before internal search. If the task is knowledge-intensive, extra reasoning tokens or more samples may simply produce more fluent hallucinations. The 2025 knowledge-intensive test-time scaling study is a useful warning: more compute did not consistently improve accuracy and could increase hallucinations in the evaluated settings. arXiv

Recommended pattern:

Retrieve relevant sources.
Generate candidate answers grounded in those sources.
Use citation coverage and contradiction checks.
Optionally rerank or debate candidates.
Return the answer with provenance.

For factual QA, Retrieval-Augmented Generation is often more important than Test-Time Compute Scaling.

8.5 Long-form writing and synthesis

Avoid token-level beam search. Use decomposition, critique, and graph-like workflows.

A strong long-form synthesis pipeline looks more like Graph of Thoughts than best-of-N:

Decompose the topic into claims.
Retrieve or generate evidence per claim.
Build intermediate summaries.
Cross-check contradictions.
Merge sections.
Run critique passes against a rubric.
Select or revise the final draft.

Graph methods are appealing here because intermediate artifacts are reusable. A section summary can support multiple later arguments; a contradiction node can trigger revisions across the document.

The scorer is usually not exact, so keep the search conservative. Use rubrics and citations, not just “which draft sounds best?”

8.6 Tool-using agents

Use ReAct-style loops for simple tasks and LATS/MCTS-style search for tasks where early actions can lead to long-term consequences. If the environment can be reset, simulated, or cheaply queried, tree search is viable. If actions are irreversible or costly, search must be constrained by safety checks.

Recommended pattern:

keep a structured state;
log observations separately from model thoughts;
branch only on meaningful alternatives;
use environment feedback whenever possible;
cap tool calls;
prefer exact validation over model self-judgment.

8.7 Open-ended judgment tasks

For subjective tasks—strategy memos, philosophical arguments, product decisions—use small-NNN generation plus rubric-based critique. Do not mistake search for objectivity. The output can improve through diversity and critique, but there is no exact target unless the human supplies one.

A practical approach is:

Generate 3–5 diverse candidates.
Score them against an explicit rubric.
Ask the model to identify tradeoffs, not just rank.
Merge the best parts.
Preserve uncertainty where evidence is thin.

Large best-of-N with a weak judge is risky because it rewards judge exploitation and rhetorical polish.

9. Cost and quality tradeoffs

Inference-time search has four costs:

Generation cost: tokens or model calls used to create candidates.
Scoring cost: verifier calls, model-judge calls, tests, tool calls, or human review.
Coordination cost: orchestration, state tracking, caching, deduplication.
Latency cost: sequential dependencies and wall-clock delay.

The quality gain must exceed all four.

A useful decision rule is:

Use search if P(better candidate exists)×P(selector finds it)×V(improvement)>C(search)\text{Use search if } P(\text{better candidate exists}) \times P(\text{selector finds it}) \times V(\text{improvement}) > C(\text{search})Use search if P(better candidate exists)×P(selector finds it)×V(improvement)>C(search) This makes the hidden assumptions explicit. Search is not justified merely because better candidates might exist. The system must also find them and recognize them.

9.1 Diversity is not optional

Best-of-N only helps if candidates differ in meaningful ways. If temperature is too low, candidates collapse. If temperature is too high, candidates become noisy. Diversity can come from sampling temperature, nucleus sampling, prompt perturbation, different models, different tools, or different decomposition strategies.

9.2 Selection quality dominates at large N

As NNN grows, the candidate pool contains more good candidates and more adversarial-looking bad candidates. With an imperfect scorer, the probability of selecting a scorer-exploiting candidate can rise. This is why reward-model overoptimization is central to the economics of search. arXiv

9.3 Adaptive budgets usually beat uniform budgets

Uniform NNN is easy but wasteful. A better system estimates uncertainty or difficulty and allocates compute accordingly. Snell et al.’s analysis and later adaptive allocation work both point in this direction: the best compute policy depends on instance difficulty and budget. OpenReview

Common adaptive signals include:

disagreement among samples;
verifier confidence;
entropy of final answers;
failed tests;
retrieval uncertainty;
model self-reported uncertainty, used cautiously;
task class;
user-specified stakes.

10. Failure modes

10.1 Reward hacking

If the scorer is a proxy, search optimizes the proxy. Best-of-N is especially vulnerable because it explicitly selects the highest-scoring candidate from a growing pool. The more candidates you sample, the more likely you are to find a candidate that exploits the scorer’s blind spots. arXiv

Mitigations:

use exact verifiers when possible;
use multiple independent scorers;
calibrate against human or ground-truth evaluations;
regularize against distributional drift;
inspect high-scoring failures;
cap NNN when the reward model is weak.

10.2 Correlated errors

Self-consistency assumes wrong answers are less correlated than correct answers. This is not always true. Models often share systematic misconceptions across samples. Majority vote can amplify a popular falsehood.

Mitigations:

diversify prompts or models;
use retrieval or tools;
score reasoning steps;
check final answers externally;
use adversarial critique.

10.3 Search myopia

Greedy pruning can discard the correct branch early. Token-level beam search is especially prone to this because low-probability early tokens can be necessary for a correct solution. Thought-level search reduces but does not eliminate the problem.

Mitigations:

keep diversity in the frontier;
use stochastic expansion;
delay pruning until enough evidence accumulates;
use rollouts rather than only local scores.

10.4 State explosion

Tree and graph methods can grow exponentially. Without aggressive pruning, caching, and canonicalization, they become impractical.

Mitigations:

bound branching factor and depth;
merge equivalent states;
use domain-specific heuristics;
allocate budget adaptively;
stop when marginal value declines.

10.5 Hallucinated evaluation

LLM-as-judge systems can hallucinate criteria, miss errors, or reward fluent nonsense. This is particularly dangerous when the same base model generates and judges candidates.

Mitigations:

separate generator and judge models;
ground judges in rubrics and evidence;
use external tools;
evaluate judges against labeled data;
require citations for factual claims.

11. The open question: does explicit search survive stronger reasoning models?

The open question is not whether reasoning models reduce the need for explicit search. They already do for many tasks. The harder question is whether explicit search remains a durable systems pattern as models become better at internal deliberation.

There are strong arguments on both sides.

11.1 Why explicit search may become less common

First, internal reasoning is simpler for users and developers. A single model call with a reasoning-effort parameter is easier than orchestrating candidates, verifiers, and search trees. OpenAI’s current reasoning-model documentation exposes exactly this kind of interface: developers can control reasoning effort while hidden reasoning tokens handle internal deliberation. OpenAI Developers

Second, search traces can be distilled. If best-of-N, Tree of Thoughts, or MCTS repeatedly finds better outputs, training can absorb some of that behavior into the model. The history of machine learning favors amortization: expensive inference procedures often become training data for faster policies.

Third, learned reasoning policies may use compute more efficiently than hand-designed search. A model trained end-to-end to deliberate may learn when to branch, when to backtrack, and when to stop without exposing those operations.

11.2 Why explicit search likely persists

The opposing argument is stronger for high-stakes and tool-rich settings.

External search can use information and validators that are not inside the model. A reasoning model cannot internally know whether a code patch passes a project’s test suite; it must run the tests. It cannot internally know the latest database state; it must query the database. It cannot internally prove a theorem in a formal system without interacting with the checker.

Explicit search also provides parallelism. Internal reasoning tokens are mostly sequential within a call. Best-of-N can use many workers simultaneously. For latency-sensitive but high-value tasks, parallel external search can be economically attractive.

Explicit search is also more auditable. Developers can log candidates, scores, tool calls, failed branches, and verifier outputs. Hidden reasoning tokens may be summarized, but they are not the same as a structured search trace.

Finally, every improvement in model capability raises the ceiling of what search can explore. A stronger generator makes better candidates. A stronger verifier makes selection more reliable. A stronger reasoning model can be the policy inside MCTS or LATS. The relationship is not replacement only; it is also composition.

11.3 Current evidence is not enough to settle the question

The empirical literature is benchmark-heavy. It shows real gains for test-time search in math, code, planning, and selected agent tasks. It also shows fragility in knowledge-intensive and weakly scored settings. But it does not yet establish a universal compute-optimal frontier across frontier models, private reasoning systems, production latency constraints, and real user tasks.

The honest answer is: explicit inference-time search remains valuable whenever external selection is better than internal intuition, and its relative value will fluctuate as reasoning models, verifiers, tools, and deployment economics improve.

12. Practical design checklist

A production inference-time search system should answer these questions before adding complexity:

Question	Why it matters
What is the candidate unit?	Full answers are cheap; partial states enable deeper search but need scoring.
What creates diversity?	Search without diversity degenerates into repeated near-duplicates.
What is the scorer?	The scorer determines whether search selects better outputs or optimized failures.
Is the scorer validated?	A reward model that looks plausible may fail under search pressure.
Can the task be externally checked?	Exact checks justify larger search budgets.
Is the budget fixed by tokens, dollars, or latency?	Different algorithms win under different constraints.
Can samples run in parallel?	Parallel best-of-N changes wall-clock economics.
Should compute be adaptive?	Uniform budgets waste effort on easy and impossible prompts.
What is the fallback?	If search fails, the system should know whether to abstain, ask for help, or return the best candidate.
What failures are logged?	Search systems improve when high-scoring failures are inspected.

13. Source map

Descriptive reference label	Role in this article
Cobbe et al., “Training Verifiers to Solve Math Word Problems”	Canonical verifier-guided best-of-N for math; generate many candidates and select with a learned verifier. arXiv
Wang et al., “Self-Consistency Improves Chain of Thought Reasoning”	Canonical self-consistency paper; sample multiple reasoning paths and marginalize final answers. arXiv
Yao et al., “Tree of Thoughts”	Introduces thought-level tree search for language-model reasoning. arXiv
Besta et al., “Graph of Thoughts”	Generalizes chains and trees into graph-structured reasoning operations. arXiv
Zhou et al., “Language Agent Tree Search”	Combines MCTS, language agents, self-reflection, and environment feedback. arXiv
Hao et al., “Reasoning via Planning”	Uses MCTS with language models as reasoning policies/world models. arXiv
Xie et al., “Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learning”	Uses MCTS-generated preference data with DPO to improve reasoning models. arXiv
Snell et al., “Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters”	Analyzes compute-optimal test-time search and prompt-difficulty dependence. OpenReview
Brown et al., “Large Language Monkeys”	Studies repeated sampling at scale and the importance of verifiers for converting coverage into performance. arXiv
OpenAI, “Learning to Reason with LLMs” and reasoning-model API documentation	Primary sources for reasoning models, hidden reasoning tokens, and test-time thinking controls. OpenAI
Gao et al., “Scaling Laws for Reward Model Overoptimization”	Analyzes Goodhart-style failures in reward-model optimization, including best-of-N. arXiv
Holtzman et al., “The Curious Case of Neural Text Degeneration”	Standard caution against likelihood-maximizing decoding for open-ended generation. OpenReview

Companion entries

Core theory: Test-Time Compute Scaling, Search as Amortized Inference, Verifier-Guided Decoding, Reward Models, Process Reward Models, Reasoning Tokens, Goodhart’s Law in AI Systems

Algorithms: Best-of-N Sampling, Self-Consistency Decoding, Beam Search, Tree of Thoughts, Graph of Thoughts, Monte Carlo Tree Search, Language Agent Tree Search, Multi-Agent Debate

Practice: Code Generation with Execution Feedback, Adaptive Compute Allocation, Tool-Using Agents, Retrieval-Augmented Generation, LLM-as-Judge Evaluation, Unit Tests as Verifiers

Counterarguments and limits: Reward Hacking, Neural Text Degeneration, Knowledge-Intensive Reasoning Limits, Correlated Reasoning Errors, Internalized Search in Reasoning Models