Reasoning models such as DeepSeek-R1 and QwQ-32B are trained to think at length before answering. They often spend much of that budget re-checking steps that were already correct: they redo an algebraic simplification, recount a case split, or re-solve an equation they solved a paragraph earlier. These steps share a property that current anti-overthinking methods ignore. Many of them are small, mechanically checkable claims that a specialized solver can settle exactly in milliseconds. Examples are a computer algebra system for an identity and an SMT solver (a satisfiability checker for logic plus arithmetic, such as Z3) for a constraint. The general-purpose language model instead settles them slowly and unreliably, token by token. This proposal treats that as a small-scale version of the classic generality-efficiency gap. It asks whether overthinking can be cut by giving the model exact certificates for the specific claims it keeps doubting, rather than by teaching it to stop early.
The method runs an external monitor alongside the model's reasoning. As the reasoning is generated, the monitor builds a map of which claims depend on which: a directed acyclic graph whose nodes are asserted claims and whose edges point from a claim to the claims it was derived from. It flags nodes the model is about to re-derive or re-verify. When such a node is formalizable, the monitor sends that single claim to a solver and splices the verdict ("verified" or "refuted, counterexample: …") back into the reasoning stream. It also uses the map to decide when to stop. Reasoning halts when every claim the current answer depends on has been certified, not when the model merely feels confident. Because the stopping rule can use a refutation as well as a confirmation, it targets the "confidently wrong" failure that confidence-based early exits cannot handle.
Core Claim
The claim has two parts, and both can be falsified. The first part is that a substantial share of the excess tokens in long reasoning traces go to re-deriving or re-verifying nodes already present in the dependency map, and that a large fraction of those nodes are locally formalizable. The second part is that closing exactly those nodes with solver certificates, chosen by the dependency structure, removes more redundant tokens and loses less accuracy than local-confidence early stopping. It should also beat letting the model call tools whenever it chooses.
The new element is the pairing of a structural redundancy signal with node-level offloading. The dependency map chooses what to offload and when to stop. The solver supplies ground truth the model cannot produce for itself. If the first part fails in the measurement study, meaning few re-verified claims are formalizable, the project reduces to structural early stopping. That fallback is still testable, but it is the less interesting outcome.
Relation to Prior Work
Three papers motivate the gap. DAG-Math prompts models to emit each step with an explicit rule, its parent steps, and the resulting claim. It defines "logical closeness," meaning every claim must be justified by earlier claims and must feed the final answer. On that basis it measures the Perfect Reasoning Rate, the fraction of solutions that are both correct and fully closed. The gap it finds is large: Gemini-2.5-Flash scores 52.4% pass@1 but only 17.0% on the Perfect Reasoning Rate on AIME 2025, and the authors attribute the difference to abandoned exploratory branches. DAG-Math only evaluates. It forces a token-costly output format and never prunes, halts, or offloads during generation. Our map is built by a separate monitor over free-form reasoning, so the model's output format is unchanged, and it is used to intervene.
Efficient Reasoning Through Suppression of Self-Affirmation Reflections documents models repeatedly re-verifying derivations without changing them. Reasoning Without Self-Doubt documents the same loops over already-correct steps. Both papers describe the behavior we target. Neither asks whether the doubted claim could be settled externally.
A second group of papers constrains the design and supplies baselines. They are the early-exit controllers. ThinkBrake stops when the log-probability gap between the next reasoning token and the end-of-thinking token closes. Dynasor-CoT, from the same self-doubt paper, periodically probes for the answer and stops when it stabilizes. Adaptive Think, from Think or Not?, stops when the entropy of the model's candidate answers falls below a threshold. All three rely on local confidence, and all three lock in early confident errors. Mitigating Overthinking through Reasoning Shaping shows that crude length penalties during reinforcement learning collapse accuracy. That finding warns against any intervention that simply cuts tokens without regard to their logical role. It is the main reason we remove only nodes that are certified or already duplicated.
A third group supplies the method. Adaptive LLM-Symbolic Reasoning via Dynamic Logical Solver Composition routes a whole problem once, up front, to Pyke, Prover9, Z3, or MiniZinc. Its results support two of our design choices. GPT-4o routed problems to the right solver type more than 98% of the time, which suggests the routing decision is feasible. Small 7B–8B models, however, failed at autoformalization, the translation of whole problems into solver syntax. Our design moves routing from the problem level to the node level. Individual claims are far smaller to formalize than whole problems, which we test directly as a response to that bottleneck. Thought Anchors estimates which sentences causally drive the answer by masking them. We use it offline as a check on our cheap dependency map, not at inference time. Verifying Chain-of-Thought Reasoning via Its Computational Graph builds internal circuit graphs to detect errors. Its authors describe it as a costly diagnostic instrument, which is why we work at the level of claims rather than circuits.
Research Program
The first stage is a measurement study, and the rest of the project depends on it. We take long traces from open reasoning models (Qwen3 and DeepSeek-R1-Distill-Qwen-32B) on MATH500, Omni-MATH, and AIME 2024/2025. We split each trace at sentence and hesitation-word boundaries, following the segmentation used in the reasoning-shaping paper. A 7B instruct model then extracts, for each segment, the claim it asserts, the earlier claims it uses, and an optional formalization as a SymPy expression or SMT-LIB assertion. Two claims are merged into one node when they are equivalent. Equivalence is checked symbolically for formalizable claims and by the extractor otherwise.
From the resulting map we split the reasoning tokens into three classes. Duplicate tokens re-derive an existing node. Unclosed tokens produce nodes that never reach the answer. Productive tokens are everything else. We define the redundant share as
$$R = \frac{T_{\text{dup}} + T_{\text{unclosed}}}{T_{\text{total}}},$$
where $T_{\text{dup}}$ counts tokens in segments that re-derive an existing node, $T_{\text{unclosed}}$ counts tokens in segments whose node never reaches the answer, and $T_{\text{total}}$ counts all reasoning tokens. We also measure what fraction of duplicate nodes the extractor can formalize and a solver can decide.
The map is validated against human labels on a few hundred traces. It is also checked against Thought Anchors' masking-based importance on a subset: nodes we call unclosed should have low causal influence.
The second stage is the intervention. The monitor keeps the map updated as tokens stream in. When a new segment begins re-deriving a formalizable node, the monitor calls the solver on that node and injects a short certificate. When a new claim is formalizable and refutable, the monitor checks it immediately and injects any counterexample.
Halting uses a closure rule. Reasoning ends when an answer node exists and every ancestor of that node is either certified or non-formalizable and unchanged across the last $k$ segments. The window $k$ is tuned on a held-out split. Refutations never trigger a halt. They reopen the branch.
On logic benchmarks the solvers are Z3 and Prover9. On math they are SymPy and Z3. All costs are charged to the method: monitor tokens, extractor compute, solver wall-clock time, and injected tokens.
The third stage tests generality. We try smaller extractors (1–3B) to see whether node-level formalization survives where whole-problem formalization failed for Xu et al. We also test on the logic suite, where more nodes are formalizable, and on GPQA-Diamond, where few are. This gives a gradient from favorable to unfavorable conditions.
Baselines
The naive reference point is unmodified full-length reasoning by the same model with the same sampling settings. It anchors both accuracy and token count.
The strongest training-free competitor is ThinkBrake. It needs the same logit access we assume, it is cheap, and it reports 10% to 30% token reduction while preserving accuracy across GSM8K, MATH500, AIME, GPQA-Diamond, and tool benchmarks. Its hindsight-oracle stopping point reaches up to 72% token savings with up to 8% accuracy gain. Dynasor-CoT is the second early-exit baseline. It reports up to 29% token reduction overall, and 53% on the costliest 10% of MATH500 problems. Adaptive Think reports 50.80% average token reduction with a 1.10% average accuracy gain on QwQ-32B.
We rerun all three ourselves on identical models, problems, and seeds. Each gets the same threshold-tuning budget on the same validation split. We then compare along the full accuracy-versus-total-compute curve, not at a single operating point. Our method beats them if, at matched accuracy, it uses fewer total tokens including monitor overhead. It must also do so on the subset of problems where the early exits halt on a wrong answer, which is the subset our refutation mechanism is designed for.
For a training-based reference, the reasoning-shaping method GRSP reports 45.60% accuracy at an average of 4,866 tokens on Omni-MATH, against 44.20% and 5,131 tokens for plain Reinforce. We report our method on the same benchmark next to that figure without retraining. We note that GRSP's cost is paid in training and ours at inference.
For the logic suite, the upfront-routing system of Xu et al. reports 92.1% on its Mixed benchmark, against 65.1% for zero-shot GPT-4o. We rerun their pipeline with our open models so the comparison is fair. We have no reported per-benchmark result from ThinkBrake on GPQA-Diamond or from DAG-Math on BRUMO or HMMT; no reported result was found on Lacuna for those.
Two ablations isolate the key ingredients. In the first, dependency-free offloading, the solver fires on the claim preceding every hesitation word, with no map. This isolates whether structure is needed to choose targets. In the second, solver-free closure halting, we use the map and closure rule but skip certificates. This isolates the value of exact external verdicts.
Why not just…?
Why not just give the model a code interpreter and let it call tools when it wants? This is the most serious alternative. Tool-integrated reasoning might already remove verification loops, and this proposal would then add machinery for nothing. The file contains no reported result on whether self-invoked tools reduce re-verification in reasoning models, and ThinkBrake's tool-use experiments show that overthinking persists even in tool environments. We therefore run this baseline directly, using the same solvers exposed as callable tools and the same compute budget. If it matches our method on the redundant share and on accuracy, we will report that the monitor's structural targeting is unnecessary. We expect a difference because models tend to re-verify precisely the claims they already believe. The paper on self-affirmation reflections suggests the doubt is performative, so a model is unlikely to spend a tool call on it.
Why not just use ThinkBrake or Dynasor-CoT, which are simpler? They cut tokens effectively, and on easy benchmarks such as GSM8K they may well match us at lower overhead. That is an acceptable finding. Their weakness lies elsewhere: they stop on confidence, so a confidently wrong trace exits wrong. Our decisive comparison is therefore restricted to traces where these methods halt incorrectly, and it asks whether solver refutations recover them.
Why not just route the whole problem to a solver up front, as Xu et al. do? For competition math, most problems mix steps that can be formalized with steps that cannot, and single-shot routing must formalize everything or nothing. That is also where small models failed in their study. The comparison on the logic suite, where whole-problem routing is strongest, measures how much node-level routing gives up there. The comparison on math measures what it gains.
Why not just penalize duplicate segments during reinforcement learning? This is a reasonable follow-up, and the node-duplication signal could be used as a reward. The reasoning-shaping paper shows, however, that length-based rewards need careful shaping to avoid collapse. A training-free monitor is also the cleaner first test of whether the duplication signal carries information.
Proposed Experiments
The first decisive check comes from the measurement study. If the duplicate share of reasoning tokens is small, or fewer than roughly a third of duplicate nodes on MATH500 and Omni-MATH are solver-decidable, then offloading cannot pay off and we pivot to structural halting alone. We also report how the redundant share grows with Omni-MATH difficulty tier. This tests the tension between DAG-Math, which finds that hard problems need branching, and the "longer is wronger" finding of Think or Not?. Our hypothesis is that duplicate tokens rise with length while unclosed tokens track genuine branching.
The main experiment compares the full method against all baselines on MATH500, AIME 2024/2025, Omni-MATH, GSM8K, ProntoQA, FOLIO, and GPQA-Diamond. We report accuracy, total compute including monitor overhead, wall-clock latency, and the Perfect Reasoning Rate computed with our map. The two ablations and the code-interpreter baseline run on the same splits.
The decisive result has three parts. The first is lower total compute than ThinkBrake at matched accuracy on AIME and Omni-MATH. The second is a measurable accuracy gain on the subset of traces where early-exit baselines halt wrongly. The third is a clear gap over both the dependency-free ablation and the self-invoked tool baseline. Any one of these parts failing is informative in a specific way: the first points to overhead, the second to refutation coverage, and the third to the value of structure. Each will be reported as such.
References
- DAG-Math: Graph-of-Thought Guided Mathematical Reasoning in LLMs
- Efficient Reasoning Through Suppression of Self-Affirmation Reflections in Large Reasoning Models
- Reasoning Without Self-Doubt: More Efficient Chain-of-Thought Through Certainty Probing
- ThinkBrake: Mitigating Overthinking in Tool Reasoning
- Think or Not? Exploring Thinking Efficiency in Large Reasoning Models via an Information-Theoretic Lens
- Mitigating Overthinking through Reasoning Shaping
- Adaptive LLM-Symbolic Reasoning via Dynamic Logical Solver Composition
- Thought Anchors: Which LLM Reasoning Steps Matter?
- Verifying Chain-of-Thought Reasoning via Its Computational Graph