Checking a language model's step-by-step reasoning one step at a time catches flawed logic, but it is slow. Pipelines that formalize each step and hand it to a logic solver, or that re-judge every sub-step, multiply inference cost by the length of the trace. There is also a less obvious waste. Most steps in a long reasoning trace do not actually influence the final answer; they are written after the model has effectively decided. Verifying such a step tells you almost nothing about whether the answer is right. This proposal treats "which steps should I spend my verification budget on?" as an optimization problem. The guiding principle is to protect against the worst case over competing guesses about which steps truly carry the answer, and to accept a small, provably bounded overrun of the budget in exchange for a guarantee.
The core idea fits in two sentences. First, cheap probes produce several disagreeing hypotheses about which steps carry the answer. Second, we choose the set of steps to verify that maximizes the minimum error-detection rate across those hypotheses, using a classic algorithm from robust sensor placement that guarantees optimal worst-case coverage if allowed a logarithmically larger budget. The bet is that guarding against the worst-case hypothesis beats trusting any single importance score, because post-hoc rationalization is exactly what makes single scores unreliable.
Why the gap is real
Three findings motivate the problem. Can Aha Moments Be Fake? measures how much each step causally matters by perturbing it and checking whether the answer changes. On AIME with Qwen-2.5, the mean score was 0.03, and only 2.3% of steps were critical. The same paper shows that "Wait, let me re-check" passages often have no effect on the output. Computing this score requires many repeated forward passes, so it cannot serve as a test-time filter. Thought Anchors finds that planning and uncertainty-management sentences carry more causal weight than arithmetic steps. It identifies them through resampling and through attention heads that point back to those sentences. On the Hardness of Faithful Chain-of-Thought Reasoning introduces an early-answering curve, which tracks how the answer probability changes as steps are revealed. It also reports that stronger models bypass their own reasoning more often. Taken together, these papers say that importance is sparse and model-dependent, and that any one cheap signal of importance can be fooled.
The closest existing systems share a limitation. OPV compresses long traces into a linear solution path and then searches for the first error. Its authors note that this summarization sometimes prunes nuance and wrongly flags valid answers. VeriCoT formalizes every step for the Z3 logic solver, at the cost of several sequential calls per step. Self-Reflective Test-Time RL condenses trajectories into skeletons for an LLM judge and pays about 28% more latency per training step than majority voting. In all three, the decision about what to verify is a fixed heuristic, either "everything" or "whatever survives summarization." None of them comes with a stated guarantee about what that decision risks missing.
Core Claim
Let $S$ be the steps of a trace, and let each step $s$ cost $c(s)$ to verify, where cost is measured in verifier calls or seconds. Let $h_1,\dots,h_m$ be hypotheses about where an error that would change the answer could lie. Each hypothesis comes from a different cheap probe. Each one defines a distribution over steps, and a verification set $A$ has detection value $F_i(A)$: the probability mass of error locations under $h_i$ that $A$ would catch. A verified step catches errors at itself and, with a lower probability, errors upstream of it that it depends on, following a step-dependency graph. Detection functions of this kind are coverage functions and are therefore submodular, meaning each added step contributes less once others are already covered. The problem we solve is
$$\max_{A \subseteq S,\ \sum_{s\in A} c(s) \le B}\ \min_{i} F_i(A),$$
where $B$ is the latency budget.
Two facts from Selecting Observations against Adversarial Objectives make this concrete. Under a strict budget, no polynomial-time algorithm can approximate this max-min. However, their SATURATE algorithm guarantees worst-case value at least the strict-budget optimum when it is allowed a budget of $\alpha B$ with $\alpha = 1 + \ln(\max_s \sum_i F_i(\{s\}))$. SATURATE works by binary-searching a target value $c$, capping each $F_i$ at $c$, and greedily covering the average of the capped functions. The slack is logarithmic because it inherits greedy set cover's approximation factor.
We claim this formulation is new for reasoning verification. We also claim, and will test, that the max-min choice beats both full verification and single-score ranking on the frontier of detection quality against latency.
Research Program
The build has three parts.
The first part is the hypothesis generators. Each must cost at most one or two forward passes. They are:
- the attention-based anchor signal from Thought Anchors;
- the early-answering probability jump between consecutive step prefixes, from Tanneru et al.;
- token-overlap and entropy measures of anchoring to the answer, adapted from Measuring and Mitigating Post-Hoc Rationalization;
- the OPV solution path itself, used as one hypothesis rather than as a hard filter;
- a uniform prior.
All probe costs are charged against $B$.
The second part is the dependency graph. We build it from the attention-masking method of Thought Anchors. This graph determines how far detection propagates from a verified step.
The third part is the selector. It is SATURATE extended to cost-weighted greedy partial cover, because a Z3 check and an LLM-judge check cost different amounts.
The selected steps are then passed to an unchanged downstream verifier. On math traces this is OPV's first-error verifier; on logic tasks it is VeriCoT's solver pipeline. Any gain can therefore be attributed to the choice of steps and not to a better checker.
On the analysis side, we will report how large $\alpha$ actually is on real traces. The theoretical bound depends on the largest single-step summed coverage, which is at most $m$ when each $F_i$ is a normalized probability. We will also test whether the strict budget ($\alpha = 1$) loses anything in practice. Krause et al. report that the strict budget often works heuristically, which leaves open whether the slack matters at all.
Baselines
The naive reference points sit at the two ends of the budget range. At the low end is outcome-only checking: no intermediate steps are verified, and a trace is accepted if its final answer passes an answer-level check. At the high end is exhaustive verification of every step with the same downstream verifier, which defines the detection ceiling and the latency we are trying to avoid. Every method is evaluated on the same traces with the same verifier model. The only thing that varies is which steps reach the verifier, plotted against a common cost axis that includes probe cost.
The strongest existing method is OPV as published. On OPV-Bench, a 2,200-sample benchmark that labels the first erroneous step in long math reasoning traces, OPV reports an F1 of 83.1, compared with 76.3 for Qwen3-Max-Preview, according to OPV. We run OPV's released verifier at its native cost. We then run our selector with the same verifier at budgets from 10% to 100% of OPV's cost. Beating OPV means one of two things: matching 83.1 F1 at a clearly lower measured cost, or exceeding it at equal cost. On ProofWriter, the reference is VeriCoT's reported 94.1% verification precision from VeriCoT. Beating it means equal precision with fewer solver and LLM calls per trace, since the paper reports no per-trace call count for us to cite.
The ablation that isolates the key ingredient is the sum version. It runs the same probes and the same cost-weighted greedy algorithm, but maximizes the average $\frac{1}{m}\sum_i F_i(A)$ and not the minimum. This is equivalent to ranking steps by a combined importance score and taking the top ones until the budget is spent. A second ablation uses each single probe alone. A third uses an oracle selector that ranks steps by the full causal score of Zhao et al.. The oracle is computed offline and gives an upper bound on what importance-aware selection could achieve. Tuning budgets, consisting of the probe hyperparameters and the binary-search tolerance, are matched across all variants on a held-out validation split.
Why not just…?
Why not just rank steps by one cheap importance score and verify the top few? This is the most serious threat, and the sum and single-probe ablations exist to test it directly. Our reason for doubt is that rationalized traces are built to look important in the wrong places. Fake self-corrections attract attention without affecting the answer, according to Zhao et al.. Stronger models also bypass their own steps, which weakens signals that track answer probability, according to Tanneru et al.. The two methods should differ most on traces where the probes disagree. We will therefore stratify results by how much the probes disagree. If top-k ranking matches max-min even when the probes disagree strongly, the worst-case formulation adds nothing. In that case we would reframe the contribution around probe design and treat the bicriteria result as a negative finding.
Why not just use OPV's summarization and skip step selection? Summarization is itself an implicit step-selection rule, and it has no guarantee attached. The OPV authors report false rejections caused by pruned nuance OPV. We include the OPV path as one hypothesis, so our selector can only drop it when other hypotheses cover the same error mass. The experiment that settles the question is to compare false-rejection rates on OPV-Bench traces where the summary omits the labeled first-error step.
Why not just vote over many samples? Majority voting avoids verification latency, but Self-Reflective Test-Time RL shows that on AIME the correct answer is often in the minority. In that paper, eight reflectively verified samples beat sixty-four voted ones. Voting is therefore a cost-matched baseline for final accuracy on AIME, not a competitor for detecting errors in individual steps.
Why not just ask a single LLM judge whether the reasoning is sound? A judge reading the whole trace is subject to the same anchoring and fake-correction effects documented above, and VeriCoT reports that such judges miss ungrounded premises. We run a whole-trace judge at matched cost as a further point on the frontier.
Proposed Experiments
The primary experiment plots F1 against measured cost on OPV-Bench for every method above. For each method we record verifier calls, wall-clock time on fixed hardware, and probe overhead. The decisive comparison is max-min against sum at equal budget, using both a paired bootstrap over traces and the probe-disagreement stratification. A second experiment runs ProofWriter depth splits D0 to D5 with VeriCoT as the downstream verifier. This tests whether the gains hold when step costs differ widely and dependencies are explicit. The question here is whether deeper proofs, which have longer dependency chains, favor graph-propagated coverage. A third experiment runs AIME 2024/2025 collaborative reasoning in the style of OPV, where verification feedback drives regeneration. It asks how much of OPV's reported gain from 55.2% to 73.3% on AIME 2025 for DeepSeek-R1-Distill-Qwen-32B survives at a fraction of the verification cost.
Finally, we measure the empirical overrun ratio $\alpha$ by comparing performance under the strict budget against the relaxed budget. A small gap would mean the guarantee is cheap insurance. A large gap would mean the slack is doing real work, and that tells practitioners how to set budgets. The project succeeds if max-min selection reaches OPV-level F1 at materially lower cost and separates clearly from the sum ablation on high-disagreement traces. It fails informatively if it does neither.
References
- Can Aha Moments Be Fake? Identifying True and Decorative Thinking Steps in Chain-of-Thought
- Thought Anchors: Which LLM Reasoning Steps Matter?
- On the Hardness of Faithful Chain-of-Thought Reasoning in Large Language Models
- OPV: Outcome-based Process Verifier for Efficient Long Chain-of-Thought Verification
- VeriCoT: Neuro-symbolic Chain-of-Thought Validation via Logical Consistency Checks
- Beyond Majority Voting: Self-Reflective Test-Time Reinforcement Learning for LLM Reasoning
- Selecting Observations against Adversarial Objectives
- Measuring and Mitigating Post-Hoc Rationalization in Reverse Chain-of-Thought Generation