mlsanityData to 14 Oct 2026

Test-time Verification via Optimal Transport: Coverage, ROC, & Sub-optimality

arXiv 2510.18982 ↗First posted 21 Oct 2025cs.AIcited by 4

On the map: LLM reasoning → Test-time compute and efficient thinking

Abstract (arXiv)

While test-time scaling with verification has shown promise in improving the performance of large language models (LLMs), the role of the verifier and its imperfections remain underexplored. The effect of verification manifests through interactions of three quantities: (i) the generator's coverage, (ii) the verifier's region of convergence (ROC), and (iii) the sampling algorithm's sub-optimality. Though recent studies capture subsets of these factors, a unified framework quantifying the geometry of their interplay is missing. We frame verifiable test-time scaling as a transport problem. This characterizes the interaction of coverage, ROC, and sub-optimality, and uncovers that the sub-optimality--coverage curve exhibits three regimes. A transport regime -- where sub-optimality increases with coverage, a policy improvement regime -- where sub-optimality may decrease with coverage, depending on the verifier's ROC, and a saturation regime -- where sub-optimality plateaus, unaffected by coverage. We further propose and analyze two classes of sampling algorithms -- sequential and batched, and examine how their computational complexities shape these trade-offs. Empirical results with Qwen, Llama, and Gemma models corroborate our theoretical findings.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning. Builds on 23 of its 37 references that are in the map. First posted on arXiv 21 Oct 2025.

Builds on

23 of 37 references.

Closest ancestors · 9

Same direction, newest first

  1. 2025ROC-n-reroll: How verifier imperfection affects test-time scaling16 Jul
  2. 2025Sample Complexity and Representation Ability of Test-time Scaling Paradigms5 Jun
  3. 2025Sampling-Efficient Test-Time Scaling: Self-Estimating the Best-of-N Sampling in Early Decoding3 Mar
  4. 2025Efficient Test-Time Scaling via Self-Calibration25 Feb
  5. 2025Scaling Test-Time Compute Without Verification or RL is Suboptimal17 Feb
  6. 2025s1: Simple test-time scaling31 Jan
  7. 2025Reward-Guided Speculative Decoding for Efficient LLM Reasoning31 Jan
  8. 2024Stream of Search (SoS): Learning to Search in Language1 Apr
  9. 2024Theoretical guarantees on the best-of-n alignment policy3 Jan

Other references · 14

  1. 2021Training Verifiers to Solve Math Word Problemscited by 10,109
  2. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learningcited by 6,330
  3. 2025Kimi k1.5: Scaling Reinforcement Learning with LLMscited by 1,210
  4. 2023Accelerating Large Language Model Decoding with Speculative Samplingcited by 1,006
  5. 2024Large Language Monkeys: Scaling Inference Compute with Repeated Samplingcited by 991
  6. 2023Distilling Step-by-Step! Outperforming Larger Language Models with Less Training Data and Smaller Model Sizescited by 737
  7. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisonscited by 247
  8. 2025RewardBench 2: Advancing Reward Model Evaluationcited by 150
  9. 2024Best Practices and Lessons Learned on Synthetic Datacited by 106
  10. 2025Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignmentcited by 97
  11. 2025How Do Large Language Monkeys Get Their Power (Laws)?cited by 43
  12. 2024Information Theoretic Guarantees For Policy Alignment In Large Language Modelscited by 23
2 more
  1. 2025Best-of-N through the Smoothing Lens: KL Divergence and Regret Analysiscited by 17
  2. 2024Learning to Better Search with Language Models via Guided Reinforced Self-Trainingcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 3.

4 papers.

  1. 2025How to Correctly Report LLM-as-a-Judge Evaluationscited by 30
  2. 2026PAC-CF: Calibrating Irreversible Frontier Pruning in LLM-Guided Searchcited by 0
  3. 2026ExpBoN: Exponential-Noise Best-of-n for Efficient Test-Time LLM Alignmentcited by 0
  4. 2026Tail Competition Explains Scaling in Best-of-N Sampling for Verifiable Problemscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Can 1B LLM Surpass 405B LLM? Rethinking Compute-Optimal Test-Time Scaling
  2. 2025Trust but Verify! A Survey on Verification Design for Test-time Scaling
  3. 2025Test-time Scaling of LLMs: A Survey from A Subproblem Structure Perspective
  4. 2025Optimal Aggregation of LLM and PRM Signals for Efficient Test-Time Scaling
  5. 2026Test-Time Scaling in the Wild: Why Exploitation, Not Exploration, Is the Bottleneck
  6. 2025T1: Tool-integrated Verification for Test-time Compute Scaling in Small Language Models
  7. 2026Sample Count Is Not Enough: Candidate-Generation Strategy Shapes the Energy and Performance of LLM Test-Time Scaling
  8. 2025Every Rollout Counts: Optimal Resource Allocation for Efficient Test-Time Scaling