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

arXiv: https://arxiv.org/abs/2510.18982 · HTML: https://mlsanity.com/paper/2510.18982/

## 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.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 23 of 23)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [s1: Simple test-time scaling](https://mlsanity.com/paper/2501.19393/) (2025)
- [Kimi k1.5: Scaling Reinforcement Learning with LLMs](https://mlsanity.com/paper/2501.12599/) (2025)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [Distilling Step-by-Step! Outperforming Larger Language Models with Less Training Data and Smaller Model Sizes](https://mlsanity.com/paper/2305.02301/) (2023)
- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [RewardBench 2: Advancing Reward Model Evaluation](https://mlsanity.com/paper/2506.01937/) (2025)
- [Stream of Search (SoS): Learning to Search in Language](https://mlsanity.com/paper/2404.03683/) (2024)
- [Theoretical guarantees on the best-of-n alignment policy](https://mlsanity.com/paper/2401.01879/) (2024)
- [Best Practices and Lessons Learned on Synthetic Data](https://mlsanity.com/paper/2404.07503/) (2024)
- [Reward-Guided Speculative Decoding for Efficient LLM Reasoning](https://mlsanity.com/paper/2501.19324/) (2025)
- [Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment](https://mlsanity.com/paper/2503.21878/) (2025)
- [Scaling Test-Time Compute Without Verification or RL is Suboptimal](https://mlsanity.com/paper/2502.12118/) (2025)
- [Efficient Test-Time Scaling via Self-Calibration](https://mlsanity.com/paper/2503.00031/) (2025)
- [Sampling-Efficient Test-Time Scaling: Self-Estimating the Best-of-N Sampling in Early Decoding](https://mlsanity.com/paper/2503.01422/) (2025)
- [How Do Large Language Monkeys Get Their Power (Laws)?](https://mlsanity.com/paper/2502.17578/) (2025)
- [Information Theoretic Guarantees For Policy Alignment In Large Language Models](https://mlsanity.com/paper/2406.05883/) (2024)
- [Best-of-N through the Smoothing Lens: KL Divergence and Regret Analysis](https://mlsanity.com/paper/2507.05913/) (2025)
- [Sample Complexity and Representation Ability of Test-time Scaling Paradigms](https://mlsanity.com/paper/2506.05295/) (2025)
- [ROC-n-reroll: How verifier imperfection affects test-time scaling](https://mlsanity.com/paper/2507.12399/) (2025)
- [Learning to Better Search with Language Models via Guided Reinforced Self-Training](https://mlsanity.com/paper/2410.02992/) (2024)

## Built on by (most cited first, 4 of 4)

- [How to Correctly Report LLM-as-a-Judge Evaluations](https://mlsanity.com/paper/2511.21140/) (2025)
- [PAC-CF: Calibrating Irreversible Frontier Pruning in LLM-Guided Search](https://mlsanity.com/paper/2604.14345/) (2026)
- [ExpBoN: Exponential-Noise Best-of-n for Efficient Test-Time LLM Alignment](https://mlsanity.com/paper/2609.21899/) (2026)
- [Tail Competition Explains Scaling in Best-of-N Sampling for Verifiable Problems](https://mlsanity.com/paper/2610.19362/) (2026)

## 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.