Reasoning models waste tokens restating, re-checking, and re-deriving things they already know. When they make a mistake and are rewound, they often regenerate the same mistake in different words. Both failures come from one missing piece. Current controllers have no reliable test for whether two points in a reasoning trace leave the model in the same state, so they cannot tell whether a reflection did anything, or whether a regenerated branch is really new. Existing tests compare surface text, sentence embeddings, or a single answer guess.
We propose to borrow the test that weighted-automata theory already uses. Two prefixes are equivalent when everything they lead to is proportional, so they differ only by a constant factor. Weighted automata are finite-state machines whose transitions carry numbers such as probabilities. For a language model, this condition reduces to a simple, computable claim: two reasoning prefixes are equivalent when the model assigns the same conditional probabilities to a small, well-chosen set of continuations. We use this one behavioral signature for two decisions. A reflection step that returns the model to an equivalent state is redundant and triggers a halt. A rollback after a detected error bans the whole equivalence class of the faulty state, not just its literal text.
Core Claim
The idea comes from the weighted extension of Angluin's L learning algorithm, An L* Algorithm for Deterministic Weighted Regular Languages. That work defines two prefixes $u, v$ as homothetically equivalent* when $f(uw) = c\cdot f(vw)$ for every suffix $w$ and some constant $c$, where $f$ assigns a weight to each string. It learns these classes from a finite "Hankel" table, a table whose rows are prefixes, whose columns are test suffixes, and whose entries are $f(uw)$.
When $f$ is a language model's sequence probability, $f(uw) = f(u)\,P(w\mid u)$. The constant $c$ is therefore just the ratio of prefix probabilities. Factoring it out is exactly the "weight pushing" step of Simpler and More General Minimization for Weighted Finite-State Automata, which moves a constant factor to the front of the machine. What remains is the conditional distribution. We therefore define the signature of a reasoning prefix $u$ over a probe set $W$ as the centered log-probability vector
$$s_W(u) = \big[\log P(w\mid u)\big]_{w\in W} - \text{mean}_{w\in W}\log P(w\mid u),$$
and call $u$ and $v$ approximately equivalent when $\lVert s_W(u) - s_W(v)\rVert_\infty \le \epsilon$. The tolerance $\epsilon$ is tuned once on held-out data. The leftover offset between two equivalent prefixes plays the role of the remainder weight in On the Equivalence of Weighted Finite-state Transducers. In our setting it records how much probability mass was spent getting from one to the other.
The probe set $W$ mixes two kinds of continuations. The first kind is answer suffixes harvested on the fly from candidate answers that have appeared in the trace, such as \boxed{17}. The second kind is a few control suffixes ("Wait", </think>, "Therefore", "So the answer is"). This choice deliberately contains earlier signals as single coordinates. The probability of "Wait" is the signal of Efficient Reasoning Through Suppression of Self-Affirmation Reflections, and the </think> margin is the signal of ThinkBrake. If behavioral equivalence adds nothing beyond those coordinates, our ablations will show it.
The new claim is that equivalence of conditional continuation behavior is the right test for redundancy and for "same error again", because it ignores phrasing by construction. The claim also says a short, cheaply scored probe set captures enough of that behavior to beat surface-similarity and single-signal controllers on both decisions.
Relation to Prior Work
Two clusters of work motivate the gap.
The first cluster handles redundancy with proxies. Reconsidering Overthinking penalizes "internal redundancy" (stagnation inside the reasoning) during RL training using sliding-window sentence-embedding cosine similarity. Reasoning Without Self-Doubt (Dynasor-CoT) halts when an injected answer probe returns the same top answer at consecutive intervals and no hesitation words appear. SAR suppression uses the probability of "Wait" alone. Embeddings measure surface meaning, not what the model will do next. Dynasor tracks only the top answer, so it is blind before an answer exists and blind to shifts in the rest of the answer distribution. The "Wait" signal is lexical.
The second cluster rolls back after errors. ROCODE rewinds to the highest-entropy token after a compiler failure and penalizes failed branches in a literal string trie. Once-More and Reasoning in Flux (UAG) trigger regeneration on perplexity or likelihood spikes. None of them checks whether the regenerated branch lands in a state equivalent to the one that failed.
The automata papers supply the method. They have so far been used only for formal languages and speech grammars, never for decoding.
Some work constrains the design. The literature disagrees about hesitation tokens. Overclocking treats "Wait" as wasted progress, Dynasor treats it as a veto on stopping, and SAR suppression finds it ambiguous. Our design resolves the disagreement behaviorally rather than lexically: a hesitation is legitimate exactly when it moves the signature to a new class.
Two further constraints shape the design. Weighted L assumes an exact equivalence oracle, which we lack. We accept approximate equivalence and use L's counterexample step only as a refinement rule. Finally, the "confidently wrong" failure noted by Once-More and ThinkBrake is not something equivalence detects. Our rollback still needs an external trigger, and we do not claim otherwise.
Research Program
The controller tracks a growing quotient graph over reasoning steps. Steps are split at sentence or line boundaries. At each boundary the model scores every suffix in $W$ in one batched pass that shares the prefix cache, so the extra work is a few short suffixes rather than a generated probe answer. The current step is then assigned to an existing class if it matches one within $\epsilon$, and otherwise opens a new class.
The halting decision uses this graph as follows. A reflection episode is defined by the step after a hesitation marker, or any step after a candidate answer has appeared. If the episode starts in class $C$ and returns to $C$ after $k$ steps, it is classed as self-affirmation. After $m$ such returns, the controller ends the thinking segment. Conversely, as long as steps keep opening new classes, the model is allowed to continue past any length budget. This is the adaptive-depth component: compute is spent in proportion to behavioral progress, not tokens.
The rollback decision works in the other direction. When an external check fails, such as unit tests for code or an answer verifier on held-out math, the class of the faulty state is marked dead. The trigger can also be a perplexity spike in the style of Once-More. On regeneration, any candidate step whose signature falls into a dead class is rejected and resampled, with logit suppression on the first diverging tokens. This replaces ROCODE's literal trie with a quotiented one.
The probe set is refined in the spirit of L. Suppose two steps were merged into one class, but their sampled continuations later produce different answer distributions. Then the answer that separated them is added to $W$, just as L adds a distinguishing suffix to its table.
The analysis component validates the signature against an expensive ground truth. For a prefix $u$, we sample 32 continuations to completion and record the empirical final-answer distribution. Two prefixes are "truly" equivalent when these distributions are statistically indistinguishable. The question is whether the cheap signature predicts this Monte Carlo equivalence, and whether it predicts it better than alternatives that can be computed at the same cost.
Baselines
The naive reference is unmodified decoding to the model's natural stop with a fixed maximum length. Every efficiency number is reported relative to it on the same prompts and seeds.
The strongest training-free halting competitor is Dynasor-CoT, because it also asks "has the model's answer state stopped changing". On DeepSeek-R1 it reports a 12% efficiency gain on AIME and 24% on AMC, and token savings of 53% on the top 10% of MATH500 problems. We run it with its published intervals of 32, 64 and 128 tokens on the same models.
SAR suppression is the strongest lexical competitor. It reports R1-Distill-1.5B MATH500 accuracy rising from 82.7% to 84.6%. We tune its threshold over its stated 0.3–0.9 range using the same held-out split we use for $\epsilon$. We also run ThinkBrake, which reports 10–30% thinking-token reduction, with its threshold $\tau$ tuned the same way.
Manifold Steering is a white-box reference. On R1-1.5B GSM8K it reports length dropping from 2,035 to 593 tokens while Pass@1 moves from 76.7% to 77.2%. RL-trained Reconsidering Overthinking reports GSM8K tokens falling from 1,555 to 513 with accuracy rising from 84.1% to 84.9%, and an Accuracy-Efficiency Score of 2.21 on AIME24. That method uses training, so it is an upper reference, not a like-for-like competitor.
Every method gets the same tuning budget: one held-out set of 200 problems per domain and a fixed grid. We report wall-clock time under batched serving as well as token counts, since the file notes that probing overhead can cancel token savings. Beating Dynasor means two things. First, a better accuracy–token trade-off at matched accuracy, meaning equal or higher accuracy with more tokens saved, on MATH500 and AIME24/25. Second, no worse wall-clock time.
For rollback, the strongest competitor is ROCODE's literal-trie backtracking on HumanEval and MBPP. It reports up to a 23.8% HumanEval pass-rate gain and 19.3% fewer tokens than post-revision. On math the competitor is Once-More, which reports Qwen3-14B AIME 2024 improving from 26.7% to 36.7%. We reimplement both triggers and change only the blocking structure. Beating them means a lower rate of regenerating a behaviorally equivalent failure and a higher pass rate at equal regeneration budget.
Three ablations isolate the key ingredient. The first removes centering, comparing raw log-probabilities without weight pushing. The second keeps only the control suffixes, which roughly reproduces SAR plus ThinkBrake inside our decision rule. The third swaps the signature for sentence-embedding or last-layer hidden-state similarity while keeping the same graph and decision rule.
Why not just…?
Why not just use sentence-embedding similarity, as Reconsidering Overthinking does? Embeddings place "so x = 4, which checks out" near "so x = 4, but the sign is wrong". They also place two different wordings of the same deduction apart. Both errors land exactly on the decisions we care about. The swap ablation and the Monte Carlo validation measure this directly. If embeddings predict true equivalence as well as the signature does, the automata framing adds nothing to detection, and we would say so.
Why not just check whether the probed answer is stable, like Dynasor-CoT? Argmax stability is one coordinate of our signature. It cannot judge a reflection that occurs before any answer exists, and it misses reflections that shift probability among alternatives without changing the top answer. Dynasor also generates probe text, whereas we only score fixed suffixes. Still, it is a real threat on problems where an answer appears early. We will report results split by whether a candidate answer has appeared, and concede the regime where Dynasor ties.
Why not just compare hidden states? This is the most serious alternative. It is cheaper, and Language Models Can Predict Their Own Behavior finds hidden states encode the eventual output early. Hidden states also encode phrasing, which equivalence should ignore. Their geometry depends on the model, and they are unavailable through APIs, while suffix log-probabilities only require scoring access.
The hidden-state swap ablation settles which signal predicts Monte Carlo equivalence better. If hidden states win, we keep the quotient-graph decision rules and class-level blocking as the contribution. Those rules apply to any equivalence test, and we would report hidden states as the better test.
Why not just suppress low-probability "Wait" tokens? SAR suppression works when redundancy is announced by one word. The control-suffix-only ablation tests whether redundancy expressed through silent recalculation or varied phrasing is missed. The prediction is that gains concentrate on reflections that do not begin with a hesitation marker.
Proposed Experiments
We evaluate DeepSeek-R1-Distill-Qwen-1.5B and 7B, to match SAR and Manifold Steering, and Qwen3-14B, to match Once-More. Halting is tested on GSM8K, MATH500, AIME 2024/2025, AMC 2023 and GPQA-Diamond. Rollback is tested on HumanEval, MBPP and their -ET variants, with execution feedback, and on AIME 2024 with Once-More's perplexity trigger.
Four checks decide the outcome.
The first check is validity. On 2,000 prefix pairs drawn from real traces, does the signature predict Monte Carlo answer-distribution equivalence? We measure this by AUROC, with TokUR's 80.64% on MATH500 error detection as a loose scale reference, since it is a different task. The signature must beat embedding and hidden-state similarity, and it must stay stable under paraphrase pairs generated by rewriting prefixes.
The second check is halting. We trace accuracy–token and accuracy–wall-clock curves against all halting baselines. We also report the separate rate of premature stops on AIME, defined as cases where the uncut run was correct and the halted run is wrong. This rate is the failure mode most likely to sink the method on hard problems.
The third check is rollback. We count the fraction of regenerations that land in a dead class under literal-trie blocking versus class blocking, which directly tests the "same error in new words" hypothesis. We also measure the resulting pass rate at a fixed regeneration budget.
The fourth check is cost. Under batched serving we measure added latency per boundary as $|W|$ grows from 4 to 32. If the probe cost erases the token savings at useful $|W|$, the method fails on its own terms.
References
- An L* Algorithm for Deterministic Weighted Regular Languages
- Simpler and More General Minimization for Weighted Finite-State Automata
- On the Equivalence of Weighted Finite-state Transducers
- Efficient Reasoning Through Suppression of Self-Affirmation Reflections in Large Reasoning Models
- ThinkBrake: Mitigating Overthinking in Tool Reasoning
- Reconsidering Overthinking: Penalizing Internal and External Redundancy in CoT Reasoning
- Reasoning Without Self-Doubt: More Efficient Chain-of-Thought Through Certainty Probing
- ROCODE: Integrating Backtracking Mechanism and Program Analysis in Large Language Models for Code Generation
- Once-More: Continuous Self-Correction for Large Language Models via Perplexity-Guided Intervention
- Reasoning in Flux: Enhancing Large Language Models Reasoning through Uncertainty-aware Adaptive Guidance
- Overclocking LLM Reasoning: Monitoring and Controlling Thinking Path Lengths in LLMs
- Mitigating Overthinking in Large Reasoning Models via Manifold Steering
- Language Models Can Predict Their Own Behavior