Test-Time Scaling in the Wild: Why Exploitation, Not Exploration, Is the Bottleneck

• URL: http://arxiv.org/abs/2608.18931v1
• Date: Wed, 19 Aug 2026 13:59:53 GMT
• Title: Test-Time Scaling in the Wild: Why Exploitation, Not Exploration, Is the Bottleneck
• Abstract summary: Test-time scaling (TTS) improves language model outputs by spending additional inference compute.<n>We conduct the first compute-normalised comparison of five TTS families across five generation benchmarks.
• Score: 1.4991111518581999
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Test-time scaling (TTS) improves language model outputs by spending additional inference compute - generating multiple candidates, searching over partial sequences, or iteratively refining drafts. These techniques yield large gains on mathematics and code, but have been developed and stress-tested almost exclusively on tasks where verification is straightforward. We conduct the first compute-normalised comparison of five TTS families across five open-ended generation benchmarks spanning medicine, law, finance, general chat, and creative writing - grounded in a unified framework that decomposes the effectiveness of each method's token budget into exploration and exploitation. The answer depends on which side of that decomposition you examine. Scaling exploration works: the best candidate in the pool improves steadily with compute across all settings. What breaks is exploitation - the step that converts a rich candidate pool into a final output. With state-of-the-art generators, reward models correlate at only $ρ_v \approx 0.12$ with true quality, rendering selection near-random regardless of budget. Tree search amplifies this failure through diversity collapse. Refinement helps on one of five benchmarks; its apparent gains elsewhere are confounded. Only synthesis across candidates (Fusion) consistently improves over single-sample baselines, yet still recovers only ~40% of available quality. The candidate pool is not the bottleneck - choosing from it is.

Related papers

• Refining Over Resampling: Test-Time Self-Correction for LLM Reasoning [3.8191765711200065]
  We propose a verifier-free breadth--depth refinement framework that uses test-time compute to both explore and improve candidate solutions.<n>Our method consistently improves over greedy decoding, majority voting, verifier-based best-of-$N$, beam search, and look decoding across multiple open-weight models.
  arXiv  Detail & Related papers  (2026-08-06T06:38:37Z)
• REVES: REvision and VErification--Augmented Training for Test-Time Scaling [53.197756110943395]
  We propose a two-stage iterative framework that alternates between online data/prompt augmentation and policy optimization.<n>We observe gains of +6.5 points over the RL baseline and +4.0 points over standard multi-turn training.
  arXiv  Detail & Related papers  (2026-06-17T10:37:23Z)
• $S^3$: Stratified Scaling Search for Test-Time in Diffusion Language Models [10.157422365382933]
  Test-time scaling investigates whether a fixed diffusion language model (DLM) can generate better outputs when given more inference compute.<n>We propose $S3$ (Stratified Scaling Search), a verifier-guided search method that improves generation by reallocating compute during the denoising process.<n>Experiments with LLaDA-8B-Instruct on MATH-500, GSM8K, ARC-Challenge, and TruthfulQA demonstrate that $S3$ consistently improves performance across benchmarks.
  arXiv  Detail & Related papers  (2026-04-07T00:51:06Z)
• 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)
• Pushing Test-Time Scaling Limits of Deep Search with Asymmetric Verification [40.75612723453356]
  In certain contexts (e.g., solving Sudoku puzzles), verifying responses can be substantially easier than generating them.<n>We study both sequential and parallel TTS of deep search agents, motivated by the intuition that verification in this setting is often much easier than generation.<n>We conduct experiments with flagship open-source models and extend them to their Heavy'' variants through TTS.
  arXiv  Detail & Related papers  (2025-10-07T17:09:23Z)
• Online Learning of Optimal Sequential Testing Policies [7.8024154978341365]
  We study an online learning problem that seeks optimal testing policies for a stream of subjects.<n>Although conducting every candidate test for a subject provides more information, it is often preferable to select only a subset.<n>We prove that the minimax regret must scale at least as $Omega(Tfrac23)$, in contrast to the $Theta(sqrtT)$ rate in episodic MDPs.
  arXiv  Detail & Related papers  (2025-09-03T20:44:32Z)
• Efficient Algorithms for Logistic Contextual Slate Bandits with Bandit Feedback [0.8287206589886881]
  We study the Logistic Contextual Slate Bandit problem.<n>A single binary reward, determined by a logistic model, is observed for the chosen slate.<n>We propose two algorithms, Slate-GLM-OFU and Slate-GLM-TS, that accomplish this goal.
  arXiv  Detail & Related papers  (2025-06-16T07:19:02Z)
• $\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)
• From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
  We analyze the forgetting, i.e., loss on previously seen tasks, after $k$ iterations.<n>We develop novel last-iterate upper bounds in the realizable least squares setup.<n>We prove for the first time that randomization alone, with no task repetition, can prevent catastrophic in sufficiently long task sequences.
  arXiv  Detail & Related papers  (2025-04-06T18:39:45Z)
• Sample, Don't Search: Rethinking Test-Time Alignment for Language Models [55.2480439325792]
  We introduce QAlign, a new test-time alignment approach.<n>As we scale test-time compute, QAlign converges to sampling from the optimal aligned distribution for each individual prompt.<n>By adopting recent advances in Markov chain Monte Carlo for text generation, our method enables better-aligned outputs without modifying the underlying model or even requiring logit access.
  arXiv  Detail & Related papers  (2025-04-04T00:41:40Z)
• Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls [83.89771461061903]
  Recent advancements in tree search algorithms guided by verifiers have significantly enhanced the reasoning capabilities of large language models (LLMs)<n>Recent advancements in tree search algorithms guided by verifiers have significantly enhanced the reasoning capabilities of large language models (LLMs)<n>We identify two key challenges contributing to this inefficiency: $textitover-exploration$ due to redundant states with semantically equivalent content, and $textitunder-exploration$ caused by high variance in verifier scoring.<n>We propose FETCH, a flexible, plug-and-play system compatible with various tree search algorithms.
  arXiv  Detail & Related papers  (2025-02-16T16:12:01Z)
• Planning In Natural Language Improves LLM Search For Code Generation [5.370466208990696]
  We propose PlanSearch, a novel search algorithm for solving problems in natural language. PlanSearch shows strong results across HumanEval+, MBPP+, and LiveCodeBench. We show that, across all models, search algorithms, and benchmarks analyzed, we can accurately predict performance gains due to search.
  arXiv  Detail & Related papers  (2024-09-05T17:44:49Z)
• Truncation Sampling as Language Model Desmoothing [115.28983143361681]
  Long samples of text from neural language models can be of poor quality. Truncation sampling algorithms set some words' probabilities to zero at each step. We introduce $eta$-sampling, which truncates words below an entropy-dependent probability threshold.
  arXiv  Detail & Related papers  (2022-10-27T05:52:35Z)

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.