Thought-Level Beam Search for Reasoning

• URL: http://arxiv.org/abs/2608.08020v2
• Date: Tue, 11 Aug 2026 04:35:54 GMT
• Title: Thought-Level Beam Search for Reasoning
• Abstract summary: Test-time compute scaling is a primary driver of performance in large reasoning models.<n>We formalize test-time reasoning as a constrained compute allocation problem over partial trajectories.<n>We introduce Gambit, an inference algorithm that executes emphthought-level beam search
• Score: 39.76902449987798
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Test-time compute scaling is a primary driver of performance in large reasoning models (LRMs), but extreme inefficiency bounds current approaches, shifting the critical question from \emph{how much} compute to spend, to \emph{where} to allocate it. We formalize test-time reasoning as a constrained compute allocation problem over partial trajectories. Under a fixed hardware budget, existing paradigms fail to actively allocate the compute to the most promising partial progress: traditional parallel sampling treats traces independently and induces severe memory bottlenecks, while subtractive pruning starves hardware and fails to actively and sufficiently shift the output distribution. To overcome this dichotomy, we introduce Gambit, an inference algorithm that executes \emph{thought-level beam search}. By periodically pruning unpromising trajectories and immediately branching from high-quality prefixes, Gambit dynamically concentrates compute onto the most promising reasoning traces via a light-weight scorer probing hidden states while maintaining continuous high hardware utilization. Extensive evaluations across multiple models and benchmarks demonstrate that Gambit strictly dominates existing baselines. Under identical hardware constraints, our method yields up to a +6.7\% absolute accuracy gain on HMMT-24 and +3.3\% on AIME-25 over pruning baselines, delivers $>2\times$ higher throughput on trace completion, and reduces total token consumption by up to 68.5\% relative to standard parallel sampling.

Related papers

• Beyond FLOPs: Benchmarking Real Inference Acceleration of LLM Pruning under a GEMM-Centric Taxonomy [13.790557800221057]
  Pruning has emerged as a dominant paradigm for accelerating large language model (LLM) inference.<n>We introduce a GEMM-centric taxonomy that reorganizes existing pruning methods according to the logical textbfM, textbfN, and textbfK dimensions of general matrix multiplication.
  arXiv  Detail & Related papers  (2026-06-08T06:26:18Z)
• Thinking in Scales: Accelerating Gigapixel Pathology Image Analysis via Adaptive Continuous Reasoning [52.41928980786654]
  We propose PathCTM to enable token-efficient scale-space continuous reasoning for gigapixel whole slide images.<n>PathCTM formulates diagnostic inference as a dynamic sequential information pursuit.<n>It reduces the number of required image patches by 95.95% and shortens inference time by approximately 95.62%, while maintaining AUC without degradation.
  arXiv  Detail & Related papers  (2026-05-19T07:46:44Z)
• Test-Time Scaling with Diffusion Language Models via Reward-Guided Stitching [66.39914384073145]
  We propose a self-consistency framework that turns cheap diffusion-sampled reasoning into a reusable pool of step-level candidates.<n>We find that step-level recombination is most beneficial on harder problems.<n>Our training-free framework improves average accuracy by up to 2 across six math and coding tasks.
  arXiv  Detail & Related papers  (2026-02-26T11:08:39Z)
• DASH: Deterministic Attention Scheduling for High-throughput Reproducible LLM Training [22.898073682504023]
  In widely used attention implementations such as FlashAttention-3, the deterministic backward pass can incur up to a 37.9% throughput reduction.<n>We formulate the backward pass of deterministic attention as a scheduling problem on a Directed Acyclic Graph (DAG)<n>We present DASH (Deterministic Attention Scheduling for High-Throughput), which encapsulates two complementary scheduling strategies.
  arXiv  Detail & Related papers  (2026-01-29T15:10:13Z)
• Hidden States as Early Signals: Step-level Trace Evaluation and Pruning for Efficient Test-Time Scaling [19.080366193748127]
  Large Language Models (LLMs) can enhance reasoning capabilities through test-time scaling by generating multiple traces.<n>The combination of lengthy reasoning traces with multiple sampling introduces substantial computation and high end-to-end latency.<n>We propose STEP: Step-level Trace Evaluation and Pruning, a novel pruning framework that evaluates reasoning steps using hidden states.
  arXiv  Detail & Related papers  (2026-01-14T02:54:55Z)
• DeepPrune: Parallel Scaling without Inter-trace Redundancy [53.62015294143274]
  Over 80% of parallel reasoning traces yield identical final answers, representing substantial wasted computation.<n>We propose DeepPrune, a novel framework that enables efficient parallel scaling through dynamic pruning.<n>Our work establishes a new standard for efficient parallel reasoning, making high-performance reasoning more efficient.
  arXiv  Detail & Related papers  (2025-10-09T17:24:54Z)
• $\texttt{SPECS}$: Faster Test-Time Scaling through Speculative Drafts [55.231201692232894]
  $textttSPECS$ is a latency-aware test-time scaling method inspired by speculative decoding.<n>Our results show that $textttSPECS$matches or surpasses beam search accuracy while reducing latency by up to $sim$19.1%.
  arXiv  Detail & Related papers  (2025-06-15T05:50:05Z)
• Fractured Chain-of-Thought Reasoning [61.647243580650446]
  We introduce Fractured Sampling, a unified inference-time strategy that interpolates between full CoT and solution-only sampling.<n>We show that Fractured Sampling consistently achieves superior accuracy-cost trade-offs, yielding steep log-linear scaling gains in Pass@k versus token budget.
  arXiv  Detail & Related papers  (2025-05-19T11:30:41Z)
• Quantization Meets Reasoning: Exploring and Mitigating Degradation of Low-Bit LLMs in Mathematical Reasoning [39.56908863102256]
  Low-bit post-training quantization impairs mathematical reasoning up to 69.81% in harder settings.<n>We address two deployment-critical questions with process-level precision.<n>In our settings, as few as 332 curated examples and 3--5 minutes of compute on a single GPU recover 4-bit weight math reasoning toward the full-precision baseline.
  arXiv  Detail & Related papers  (2025-05-16T12:11:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.