Research map / Large language models / Reasoning and chain of thought

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

ICLR 2026 · Large language models › Reasoning and chain of thought · approach: Test-time compute scaling · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Frames verifier-based test-time sampling as an optimal transport problem under a chi-square coverage constraint, deriving exact sub-optimality and compute for accept-if-correct, sequential/batched rejection sampling, maximal coupling, and best-of-N with imperfect verifiers, validated on Qwen3 models.

Problem

Test-time verification with imperfect verifiers: how far sampling-based verification can approximate the verifier-induced optimal policy, given the generator's coverage and the verifier's accuracy (ROC / Youden's index).

Approach

Casts test-time verification as a transport plan from the reference distribution to the chi-square-constrained optimal policy; the Hamming optimal transport cost plus Youden's index yields a three-regime (transport, policy improvement, saturation) sub-optimality-coverage geometry, and proposes SRS and SMC sequential algorithms plus batched BRS that satisfy the coverage constraint.

Key results

• Sub-optimality of SRS and SMC follows three regimes (O(sqrt(beta)) growth, policy-improvement decrease scaled by Youden's index, then plateau) on Qwen3 models.
• SRS and SMC have identical expected number of proposals, E[tau] = (1 ∧ m_beta(s_ver))/s_ver, improving on AiC by factor m_beta(s_ver).
• AiC violates the coverage constraint for beta < 1/s_ver but matches SRS/SMC in the saturation regime.

Surprising findings

• SMC underperforms SRS when the assumed s is below the true value and outperforms it when above, showing SMC is sensitive to verifier-accuracy misspecification.
• When s = 1, SRS, SMC and AiC all reduce to AiC.

Limitations

• Theory assumes the reference mass s_ver is available to the algorithm, while in practice it is tuned as a hyperparameter.
• Analysis uses ratio-based (chi-square) coverage; difference-based coverage is unexplored.
• Restricted to verifiable binary rewards rather than general reward models.

Experimental setup

Metrics: sub-optimality expected number of proposals

Baselines: accept-if-correct (AiC) best-of-N (BoN) sequential rejection sampling (SRS) sequential maximal coupling (SMC)

Builds on: best-of-N sampling rejection sampling maximal coupling chi-square coverage constraint

Closest papers by meaning

• ROC-n-reroll: How verifier imperfection affects test-time scaling (ICLR 2026 · similarity 0.90)
• Scaling Test-Time Compute Without Verification or RL is Suboptimal (ICML 2025 · similarity 0.89)
• Optimal Aggregation of LLM and PRM Signals for Efficient Test-Time Scaling (ICLR 2026 · similarity 0.89)
• T1: Tool-integrated Verification for Test-time Compute Scaling in Small Language Models (ICLR 2026 · similarity 0.88)
• Test-Time Scaling in the Wild: Why Exploitation, Not Exploration, Is the Bottleneck (NeurIPS 2026 · similarity 0.88)
• On the Limits of Test-Time Compute: Sequential Reward Filtering for Better Inference (ICML 2026 · similarity 0.88)