Inference-Time Search

Ask about this topic

Overview

Inference-time search studies how models can use additional computation at deployment to explore alternatives and improve their answers or decisions. Common approaches include best-of-N sampling, beam search and Monte Carlo tree search, guided by verifiers or reward models, with adaptive budgets, pruning, and memory used to focus effort. These methods are applied to mathematical reasoning, code and theorem proving, tool-using agents, planning, and scientific design, where stronger selection can matter as much as generating more candidates. A central tension is that search helps only when its guidance is informative: noisy scores can favor flawed paths, while broader exploration and verification cost time and compute.

Latest papers

CardsList

105 papers14 papers in the last four weeks, up 8% on the four weeks before. 0.1% of all new papers.

Apr 7, 2026

PRISM-MCTS: Learning from Reasoning Trajectories with Metacognitive Reflection

PRISM-MCTS: Learning from Reasoning Trajectories with Metacognitive Reflection Siyuan Cheng, Bozhong Tian, Yanchao Hao, Zheng Wei Published: 06 Apr 2026, Last Modified: 06 Apr 2026 ACL 2026 Findings Conference, Area Chairs, Reviewers, Publication Chairs, Authors Revisions BibTeX CC BY 4.0 Keywords: Efficient/Low-Resource Methods for NLP, Generation, Question Answering Abstract: The emergence of reasoning models, exemplified by OpenAI o1, signifies a transition from intuitive to deliberative cognition, effectively reorienting the scaling laws from pre-training paradigms toward test-time computation. While Monte Carlo Tree Search (MCTS) has shown promise in this domain, existing approaches typically treat each rollout as an isolated trajectory. This lack of information sharing leads to severe inefficiency and substantial computational redundancy, as the search process fails to leverage insights from prior explorations. To address these limitations, we propose PRISM-MCTS, a novel reasoning framework that draws inspiration from human parallel thinking and reflective processes. PRISM-MCTS integrates a Process Reward Model (PRM) with a dynamic shared memory, capturing both "Heuristics" and "Fallacies". By reinforcing successful strategies and pruning error-prone branches, PRISM-MCTS effectively achieves refinement. Furthermore, we develop a data-efficient training strategy for the PRM, achieving high-fidelity evaluation under a few-shot regime. Empirical evaluations across diverse reasoning benchmarks substantiate the efficacy of PRISM-MCTS. Notably, it halves the trajectory requirements on GPQA while surpassing MCTS-RAG and Search-o1, demonstrating that it scales inference by reasoning judiciously rather than exhaustively.

Siyuan Cheng, Bozhong Tian, YanChao Hao +1

Tencent PCG

Inference-Time SearchEfficient Language Model ReasoningMonte Carlo Tree SearchMetacognition in Language ModelsProcess Reward Models
AskPDF
Mar 30, 2026

Entropic Claim Resolution: Uncertainty-Driven Evidence Selection for RAG

Current Retrieval-Augmented Generation (RAG) systems predominantly rely on relevance-based dense retrieval, sequentially fetching documents to maximize semantic similarity with the query. However, in knowledge-intensive and real-world scenarios characterized by conflicting evidence or fundamental query ambiguity, relevance alone is insufficient for resolving epistemic uncertainty. We introduce Entropic Claim Resolution (ECR), a novel inference-time algorithm that reframes RAG reasoning as entropy minimization over competing semantic answer hypotheses. Unlike action-driven agentic frameworks (e.g., ReAct) or fixed-pipeline RAG architectures, ECR sequentially selects atomic evidence claims by maximizing Expected Entropy Reduction (EER), a decision-theoretic criterion for the value of information. The process dynamically terminates when the system reaches a mathematically defined state of epistemic sufficiency (H <= epsilon, subject to epistemic coherence). We integrate ECR into a production-grade multi-strategy retrieval pipeline (CSGR++) and analyze its theoretical properties. Our framework provides a rigorous foundation for uncertainty-aware evidence selection, shifting the paradigm from retrieving what is most relevant to retrieving what is most discriminative.

Davide Di Gioia

Retrieval-Augmented GenerationEvidence SelectionInference-Time SearchEpistemic UncertaintyValue of Information
AskPDF
Mar 30, 2026

CoT2-Meta: Budgeted Metacognitive Control for Test-Time Reasoning

Recent test-time reasoning methods improve performance by generating more candidate chains or searching over larger reasoning trees, but they typically lack explicit control over when to expand, what to prune, how to repair, and when to abstain. We introduce CoT2-Meta, a training-free metacognitive reasoning framework that combines object-level chain-of-thought generation with meta-level control over partial reasoning trajectories. The framework integrates four components: strategy-conditioned thought generation, tree-structured search, an online process oracle for step-level reasoning evaluation, and a meta-controller that allocates computation through expansion, pruning, repair, stopping, and fallback decisions. Under matched inference budgets, CoT2-Meta consistently outperforms strong single-path, sampling-based, and search-based baselines, including ReST-MCTS. On the default backbone, it achieves 92.8 EM on MATH, 90.4 accuracy on GPQA, 98.65 EM on GSM8K, 75.8 accuracy on BBEH, 85.6 accuracy on MMMU-Pro, and 48.8 accuracy on HLE, with gains over the strongest non-CoT2-Meta baseline of +3.6, +5.2, +1.15, +2.0, +4.3, and +4.3 points, respectively. Beyond these core results, the framework remains effective across a broader 15-benchmark suite spanning knowledge and QA, multi-hop reasoning, coding, and out-of-distribution evaluation. Additional analyses show better compute scaling, improved calibration, stronger selective prediction, targeted repair behavior, and consistent gains across backbone families. These results suggest that explicit metacognitive control is a practical design principle for reliable and compute-efficient test-time reasoning systems.

Siyuan Ma, Bo Gao, Zikai Xiao +6

Nanyang Technological University · Carnegie Mellon University · Zhejiang University +5

Efficient Language Model ReasoningMetacognition in Language ModelsInference-Time SearchInference-Time Compute Allocation
AskPDF
Mar 26, 2026

A Priori Sampling of Transition States with Guided Diffusion

Transition states, the first-order saddle points on the potential energy surfaces, govern the kinetics and mechanisms of chemical reactions and conformational changes. Locating them is challenging because transition pathways are topologically complex and can proceed via an ensemble of diverse routes. Existing methods address these challenges by introducing heuristic assumptions about the pathway or reaction coordinates, which limits their applicability when a good initial guess is unavailable or when the guess precludes alternative, potentially relevant pathways. We propose to bypass such heuristic limitations by introducing ASTRA, A Priori Sampling of TRAnsition States with Guided Diffusion, which reframes the transition state search as an inference-time scaling problem for generative models. ASTRA trains a score-based diffusion model on configurations from known metastable states. Then, ASTRA guides inference toward the isodensity surface separating the basins of metastable states via a principled composition of conditional scores. A Score-Aligned Ascent (SAA) process then approximates a reaction coordinate from the difference between conditioned scores and combines it with physical forces to drive convergence onto first-order transition states. Validated on benchmarks ranging from 2D potentials to biomolecular conformational changes and a chemical reaction, ASTRA locates transition states with high precision and discovers multiple reaction pathways, enabling mechanistic studies of complex molecular systems.

Hyukjun Lim, Soojung Yang, Lucas Pinède +3

Department of Materials Science and Engineering, Seoul National University, 1 Gwanak-ro, Gwanak-gu, Seoul, 08826, Republic of Korea. · Computational and Systems Biology, MIT, 77 Massachusetts Avenue, Cambridge, 02139, Massachusetts, USA. · Chimie ParisTech, PSL University, 11 rue Pierre et Marie Curie, Paris, 75005, France. +2

Diffusion Model GuidanceDiffusion SamplingInference-Time Search
AskPDF
Mar 20, 2026

FormalEvolve: Neuro-Symbolic Evolutionary Search for Diverse Autoformalization

Autoformalization aims to produce formal statements that compile and faithfully preserve the intended meaning of informal mathematics. Yet standard single-output evaluation collapses this many-to-many structure into a single prediction. For downstream proving, this granularity is too coarse: a formal statement is not merely a faithful translation endpoint, but also a prover-facing interface whose structure can alter proof search under a fixed budget. We therefore recast autoformalization as budgeted test-time search: FormalEvolve maintains a compilation-feasible archive for reuse and returns a deduplicated, semantically accepted repertoire for evaluation and downstream proving. It expands the archive with LLM-driven mutation, crossover, bounded patch repair, and symbolic abstract syntax tree (AST) rewrites for structural diversity. Under a generator-call budget of T=100 with a fixed LLM semantic judge, FormalEvolve reaches SH@100 of 58.0% on CombiBench and 84.9% on ProofNet, improving over all no-archive controls while reducing the cross-problem concentration of semantic successes. Under a fixed B=64 prover budget, these repertoires improve theorem-complete proving over the matched no-archive control. Additional stronger-base statement-generation experiments show that archive-search gains persist with stronger seed and repair models.

Haijian Lu, Wei Wang, Jing Liu

School of Artificial Intelligence, Xidian University, Xi’an, China · Beijing Institute for General Artificial Intelligence, Beijing, China

AutoformalizationInference-Time SearchEvolutionary Optimization
AskPDF
Mar 16, 2026

More Test-Time Compute Can Hurt: Overestimation Bias in LLM Beam Search

Wider beam search should improve LLM reasoning, but when should you stop widening? Prior work on beam width selection has focused on inference efficiency \citep{qin2025dsbd, freitag2017beam}, without analyzing whether wider search can hurt output quality. We present an analysis, grounded in Extreme Value Theory, that answers this question. Beam selection over noisy scorer outputs introduces a systematic overestimation bias that grows with the candidate pool size, and we derive a maximum useful beam width k^\hat{k} beyond which search degrades performance. This critical width depends on the signal-to-noise ratio of the scorer: k^\hat{k} grows exponentially with (Δ/σ)2(Δ/σ)^2, where Δ>0Δ> 0 is the quality advantage of correct paths over incorrect ones and σσ is the scorer noise. We validate this theory by comparing perplexity-guided and PRM-guided beam search across three 7B-parameter models and ten domains on MR-BEN (5,975 questions). Perplexity scoring, with its high noise, yields k^=1\hat{k} = 1: search provides no benefit at any width tested. PRM scoring, with lower noise, yields k^≥4\hat{k} \geq 4, with gains of up to 8.9 percentage points. The same model, the same algorithm, but different scorers place k^\hat{k} at opposite ends of the beam width range. Our analysis identifies the scorer's signal-to-noise ratio as the key quantity governing beam width selection, and we propose diagnostic indicators for choosing the beam width in practice.

Gal Dalal, Assaf Hallak, Gal Chechik +1

NVIDIA Research · Bar-Ilan University · University of Groningen

Inference-Time Search
AskPDF
Mar 12, 2026

CreativeBench: Benchmarking and Enhancing Machine Creativity via Self-Evolving Challenges

The saturation of high-quality pre-training data has shifted research focus toward evolutionary systems capable of continuously generating novel artifacts, leading to the success of AlphaEvolve. However, the progress of such systems is hindered by the lack of rigorous, quantitative evaluation. To tackle this challenge, we introduce CreativeBench, a benchmark for evaluating machine creativity in code generation, grounded in a classical cognitive framework. Comprising two subsets -- CreativeBench-Combo and CreativeBench-Explore -- the benchmark targets combinatorial and exploratory creativity through an automated pipeline utilizing reverse engineering and self-play. By leveraging executable code, CreativeBench objectively distinguishes creativity from hallucination via a unified metric defined as the product of quality and novelty. Our analysis of state-of-the-art models reveals distinct behaviors: (1) scaling significantly improves combinatorial creativity but yields diminishing returns for exploration; (2) larger models exhibit ``convergence-by-scaling,'' becoming more correct but less divergent; and (3) reasoning capabilities primarily benefit constrained exploration rather than combination. Finally, we propose EvoRePE, a plug-and-play inference-time steering strategy that internalizes evolutionary search patterns to consistently enhance machine creativity.

Zi-Han Wang, Lam Nguyen, Zhengyang Zhao +4

Southern University of Science and Technology · Tsinghua University · Xi’an Jiaotong University +3

Computational CreativityCreativity AssessmentCode Generation BenchmarksCode GenerationSynthetic Benchmark GenerationInference-Time Search
AskPDF
Mar 11, 2026

How to make the most of your masked language model for protein engineering

A plethora of protein language models have been released in recent years. Yet comparatively little work has addressed how to best sample from them to optimize desired biological properties. We fill this gap by proposing a flexible, effective sampling method for masked language models (MLMs), and by systematically evaluating models and methods both in silico and in vitro on actual antibody therapeutics campaigns. Firstly, we propose sampling with stochastic beam search, exploiting the fact that MLMs are remarkably efficient at evaluating the pseudo-perplexity of the entire 1-edit neighborhood of a sequence. Reframing generation in terms of entire-sequence evaluation enables flexible guidance with multiple optimization objectives. Secondly, we report results from our extensive in vitro head-to-head evaluation for the antibody engineering setting. This reveals that the choice of sampling method can have a substantial impact, motivating future research into this under-explored area.

Calvin McCarter, Nick Bhattacharya, Sebastian W. Ober +1

BigHat Biosciences

Protein Language ModelsInference-Time SearchProtein DesignMasked Language Modeling
AskPDF
Mar 6, 2026

Efficient K-generalizable Learned Search

Learned top-K search improves the accuracy-latency trade-off of graph-based vector search, but existing methods target a fixed K. Serving real-world workloads with various K values thus incurs preprocessing cost proportional to the number of distinct Ks. We present OMEGA, which supports efficient arbitrary K learned search with the preprocessing cost of one top-1 model. It achieves so by reducing learned top-K search to repeated masked learned top-1 search with refinement, using carefully crafted trajectory features that generalize across Ks. OMEGA further employs rank-wise confidence allocation to tame error accumulation during refinements and applies a statistical forecast method to reduce model invocation overhead without compromising recall. Across nine dataset-scale configurations, OMEGA meets the 0.95 recall target and reduces mean latency by up to 65% (average: 23%; median: 20%) compared with learned search methods (including LAET, DARTH, MultiK-DARTH, ANNiE, and Ada-ef) at their lowest-preprocessing configurations. On production traces, it reduces total CPU time by up to 28% versus traditional HNSW search.

Yifan Peng, Jiafei Fan, Xingda Wei +7

Shanghai Jiao Tong University · Boston University · Alibaba Group

Inference-Time SearchGraph-Based RetrievalApproximate Nearest Neighbor Search
AskPDF
Feb 28, 2026

LiTS: A Modular Framework for LLM Tree Search

LiTS is a modular Python framework for LLM reasoning via tree search. It decomposes tree search into three reusable components (Policy, Transition, and RewardModel) that plug into algorithms like MCTS and BFS. A decorator-based registry enables domain experts to extend to new domains by registering components, and algorithmic researchers to implement custom search algorithms. We demonstrate composability on MATH500 (language reasoning), Crosswords (environment planning), and MapEval (tool use), showing that components and algorithms are orthogonal: components are reusable across algorithms within each task type, and algorithms work across all components and domains. We also report a mode-collapse finding: in infinite action spaces, LLM policy diversity (not reward quality) is the bottleneck for effective tree search. A demonstration video is available at https://youtu.be/nRGX43YrR3I. The package is released under the Apache 2.0 license at https://github.com/xinzhel/lits-llm, including installation instructions and runnable examples that enable users to reproduce the demonstrated workflows.

Xinzhe Li, Yaguang Tao

RMIT University

Inference-Time SearchTree SearchMonte Carlo Tree Search
AskPDF
Feb 19, 2026

Sonar-TS: Search-Then-Verify Natural Language Querying for Time Series Databases

Natural Language Querying for Time Series Databases (NLQ4TSDB) aims to assist non-expert users retrieve meaningful events, intervals, and summaries from massive temporal records. However, existing Text-to-SQL methods are not designed for continuous morphological intents such as shapes or anomalies, while time series models struggle to handle ultra-long histories. To address these challenges, we propose Sonar-TS, a neuro-symbolic framework that tackles NLQ4TSDB via a Search-Then-Verify pipeline. Analogous to active sonar, it utilizes a feature index to ping candidate windows via SQL, followed by generated Python programs to lock on and verify candidates against raw signals. To enable effective evaluation, we introduce NLQTSBench, the first large-scale benchmark designed for NLQ over TSDB-scale histories. Our experiments highlight the unique challenges within this domain and demonstrate that Sonar-TS effectively navigates complex temporal queries where traditional methods fail. This work presents the first systematic study of NLQ4TSDB, offering a general framework and evaluation standard to facilitate future research.

Zhao Tan, Yiji Zhao, Shiyu Wang +5

Jiangxi University of Finance and Economics · Griffith University · Yunnan University +2

Time Series QATemporal IRInference-Time Search
AskPDF
Feb 1, 2026

What If We Allocate Test-Time Compute Adaptively?

Test-time compute scaling allocates inference computation uniformly, uses fixed sampling strategies, and applies verification only for reranking. In contrast, we propose a verifier-guided adaptive framework treating reasoning as iterative trajectory generation and selection. For each problem, the agent runs multiple inference iterations. In each iteration, it optionally produces a high-level plan, selects a set of reasoning tools and a compute strategy together with an exploration parameter, and then generates a candidate reasoning trajectory. A process reward model (PRM) serves as a unified control signal: within each iteration, step-level PRM scores are aggregated to guide pruning and expansion during generation, and across iterations, aggregated trajectory rewards are used to select the final response. Across datasets, our dynamic, PRM-guided approach consistently outperforms direct test-time scaling, yielding large gains on MATH-500 and several-fold improvements on harder benchmarks such as AIME24 and AMO-Bench. We characterize efficiency using theoretical FLOPs and a compute intensity metric penalizing wasted generation and tool overhead, demonstrating that verification-guided allocation concentrates computation on high-utility reasoning paths.

Ahsan Bilal, Ahmed Mohsin, Muhammad Umer +4

University of Oklahoma, OK, USA · Stanford University, CA, USA · Universitat Pompeu Fabra, Barcelona, Spain +2

Inference-Time SearchTest-Time ScalingInference-Time Compute AllocationInference-Time Guidance
AskPDF
Jan 22, 2026

Inference-Time Diversity in RL-Trained Lean Theorem Provers: A Diagnostic Study

RL-trained Lean theorem provers mode-collapse at inference time: on miniF2F-test with DeepSeek-Prover-V1.5-RL, doubling the i.i.d.\ sampling budget from k=32k{=}32 to k=64k{=}64 produces zero additional solved theorems (42/244 in both cases). A fixed schedule of 15 tactic skeletons breaks this plateau and recovers a +45+45% relative improvement at k=16k{=}16 (mean Δ=+12.3±4.2Δ= +12.3 \pm 4.2 theorems across n=3n{=}3 seeds, sign preserved in every seed). A controlled diversity ablation rules out the prompt-diversity confound: tactic skeletons help, paraphrases match the baseline, and irrelevant Lean comments actively degrade. A leave-one-out formalization-difficulty stratification reveals a structural-content gradient across the three perturbations. The phenomenon is RL-specific: V1.5-Base proves zero theorems regardless of intervention, identifying RL as the stage that creates the proof capability which subsequently collapses; extending to two additional 7B Lean provers, RL-trained DeepSeek-Prover-V2-7B contributes +3+3 frontier solves no i.i.d. baseline can reach despite a flat aggregate, while SFT-trained Goedel-Prover does not ( −10.0-10.0 ±4.4\pm 4.4 theorems, n=3n{=}3, sign preserved every seed). Inference-time structural diversity is a cheap, complementary axis for RL-trained provers, orthogonal to scaling model size or training compute.

Zachary Burton

Massachusetts Institute of Technology, Cambridge, MA, USA.

Inference-Time SearchRL for Language Model ReasoningLean Theorem ProvingLarge Language Model-Guided Theorem Proving
AskPDF
Nov 10, 2025

Scalable Decision Making for Games of Imperfect Information

Real-world decision-making generally involves hidden information, that is, information that is unknown to one agent but possessed by another. Unfortunately, the presence of large amounts of hidden information renders established reinforcement learning and search approaches ineffective. Even with multimillion-dollar industrial research efforts, top-human-level play at Stratego---a board wargame with hidden information on a massive scale---has remained beyond the reach of artificial intelligence (AI). Here we introduce Ataraxos, an AI for Stratego based on general techniques that we developed for both self-play reinforcement learning and test-time search under hidden information. Ataraxos defeated the most decorated human Stratego player of all time by a large margin---achieving, to our knowledge, the first superhuman result in the game's history---while consuming orders of magnitude less compute and data than previous efforts. Using the same techniques, we built a superhuman AI for Barrage Stratego and state-of-the-art AIs for Hanabi and dou dizhu, all with low cost and high sample efficiency. The success of this approach across adversarial, cooperative and team games establishes a design pattern for reinforcement learning and search that is effective under large amounts of hidden information, a longstanding desideratum of the field of strategic decision-making.

Samuel Sokota, Eugene Vinitsky, Hengyuan Hu +3

Carnegie Mellon University · NYU Tandon School of Engineering · Stanford University +1

Game-Playing AgentsInference-Time SearchSelf-Play RLImperfect-Information GamesRL for Game AI
AskPDF
Oct 28, 2025

MASPRM: Multi-Agent System Process Reward Model

Inference-time search over multi-agent systems (MAS) wastes compute when it cannot identify which agent's intermediate message advanced progress. We present the Multi-Agent System Process Reward Model (MASPRM), which scores routed transcripts (ordered sequences of messages between agents) and acts as an inference controller for step-level beam search (SBS) and Monte Carlo Tree Search (MCTS). MASPRM is trained from multi-agent MCTS rollouts labeled only with terminal outcome rewards, without human step-level annotations. We evaluate on GSM8K, MATH, MMLU, and LogiQA. Under matched scorer size and comparable MCTS budget, MASPRM exceeds a size-matched ORM by +2.0+2.0 to +3.0+3.0 points at 1.5B and +4.1+4.1 to +14.5+14.5 at 7B across all four benchmarks, with additional scorer-scaling gains over policy likelihood at 7B (avg +13.4+13.4 under MCTS). MASPRM also improves ranking quality, reducing Hit@1 to Hit@5 gaps by up to 10.310.3 points, with the largest gains under stepwise search that uses intermediate decisions. Code: https://github.com/milad1378yz/MASPRM

Milad Yazdani, Mahdi Mostajabdaveh, Zirui Zhou +1

Department of Electrical and Computer Engineering, University of British Columbia, Vancouver, BC V6T1Z4, Canada · Huawei Technologies Canada, Burnaby, BC V5C6S7, Canada

Multi-Agent LLM SystemsInference-Time SearchProcess Reward ModelsMulti-Agent Reasoning
AskPDF