Validity Intervals: Catching Reasoning Errors That Every Step-Level Check Accepts

Long reasoning traces from language models are full of temporary claims. "Suppose $x > 0$." "In case 2, $y = 3$." "Let's try $n = 5$... no, that fails." Each such claim holds only over a stretch of the trace: inside its case, under its assumption, or until the model takes it back. A common and nearly invisible error is to use one of these claims outside that stretch. The model carries $y = 3$ out of case 2 into the general conclusion, or quietly reuses a value from an abandoned attempt. Current verifiers miss this by construction. A judge that checks each step against the parent steps it cites will accept "$y=3$, so $z=9$", because the step is locally correct given its parent. A graph check for cycles or unreachable nodes also passes it, because the dependency graph is a perfectly good tree. The error is not in any step or any edge. It is in where a claim was used.

We propose to give every claim in a trace a validity interval, the span of steps over which it holds. A trace is then checked by asking whether all claim uses and claim combinations fit inside a consistent arrangement of intervals. This is the question that the theory of intersection graphs (graphs whose edges record which intervals overlap) answers with linear-time machinery. We also propose a synthetic error-injection benchmark that plants exactly these scope errors into verified reasoning graphs, and a human study of how often they occur in real model traces. The claim to be tested is concrete. Scope errors are a distinct, measurable class of reasoning hallucination. Per-step judges and dependency-graph checks cannot catch them. An interval-consistency check catches them cheaply, and it also separates harmless dead-end exploration from harmful reuse of retracted claims.

Core Claim

Logical dependency mapping turns a chain of thought into a directed graph of steps and the steps they rely on. DAG-Math enforces a Step -> Justification -> Parents -> Conclusion format and scores "logical closeness". The Structural Reasoning Model of Hallucination Detection from Structural Reasoning Model has an LLM judge verify each step conditioned only on its declared parents, then propagates confidence with a Flow Score. CGRiC bounds the risk of a whole answer by composing per-claim risks over the graph. All three share a hidden assumption: a claim, once derived, is valid everywhere downstream. Their graphs record what depends on what. They do not record where each claim is allowed to be used. Our proposal adds that missing coordinate. It is the right object for two open problems that these papers themselves raise. The first is implicit context, which causes valid steps to be falsely rejected and invalid ones to be silently accepted. The second is the tension that DAG-Math surfaces when Gemini-2.5-Flash reaches 52.4% accuracy on AIME 2025 but only a 17.0% Perfect Reasoning Rate. Because DAG-Math penalizes all speculative branching, it cannot tell whether that gap reflects harmless exploration or actual contamination.

The intersection-graph direction supplies the formal tool. Number the steps of a trace $1,\dots,T$. Each claim $c$ gets an interval $I_c=[a_c,b_c]$. $a_c$ is where the claim is introduced. $b_c$ is where its supporting context ends: the case closes, the assumption is discharged, or the claim is retracted. The trace is scope-consistent if three conditions hold. Every use of $c$ at step $t$ satisfies $t \in I_c$. Every claim's interval lies inside the intervals of the assumptions it depends on. Claims from mutually exclusive branches have disjoint intervals. When scope boundaries are fully marked, this is a linear scan, and we say so plainly. The graph theory earns its place when boundaries are only partly explicit. This is the normal case in natural text, where "Case 2" is written but the end of case 2 is not, and where a retraction is implied by "hmm, instead...". We then hold fixed the intervals whose endpoints are anchored by explicit markers and step positions. The question becomes whether the remaining intervals can be placed so that all overlap and disjointness constraints hold. This is the partial representation extension problem. Extending Partial Representations of Interval Graphs solves it in linear time using PQ-trees, which compactly encode every valid left-to-right ordering, provided the overlap and non-overlap relations are fully specified. The same paper shows the problem becomes NP-complete under integer-coordinate restrictions. Our discrete step positions are close to that regime, and we expect some disjointness relations to be unknown.

We therefore commit to the following design. When the extracted constraints are complete, we use the PQ-tree extension algorithm. Otherwise we use a small exact constraint solver over interval endpoints, which is affordable because traces have tens to a few hundred claims. We flag an error only when no consistent placement exists, so implicit-but-legitimate scopes do not cause false rejections. The infeasible core, meaning the smallest set of constraints that cannot jointly hold, tells us which use broke the scope. That gives localization for free.

Research Program

The work has three parts.

The first is a scope-annotated extraction format. It extends the DAG-Math tuple with two optional fields: the scope a step opens or closes (assumption, case, trial value, retraction), and the claims it combines. An LLM parser fills these where the text is explicit and leaves them blank otherwise. The verifier never trusts the parser for blank fields. It only asks whether some filling is consistent.

The second is a synthetic scope-error engine, in the spirit of near-miss pairs from INSTRUCTSCORE and graph perturbation from GNNVerifier. It operates on the 2,894 gold DAGs of the DAG-MATH benchmark, whose dependencies human evaluation found 98% accurate. GNNVerifier swaps tools and drops edges in plan graphs. Our engine instead keeps the dependency graph intact and moves uses across scope boundaries. It plants three kinds of error. Case leakage redirects a post-case step to cite a case-internal claim. Zombie reuse inserts an exploratory attempt, retracts it, and later cites its result. Undischarged assumption uses a claim derived under "suppose" after the contradiction has closed that assumption. Each corrupted graph is rendered back to fluent text, and the clean twin is rendered by the same generator with the same prompt. This removes the stylistic tells that the research file flags as a known weakness of neural error generators. As a specificity control, the engine also plants value errors such as arithmetic flips and unit swaps of the kind built by BioDimBench. On these, the interval check should provide no benefit.

The third is an organic prevalence study. We sample long reasoning traces from open reasoning models on Omni-MATH, the AIME problems used by CAMA, and the reasoning-category trajectories of AgentHallu. Annotators label every error with a taxonomy that adds a "scope" class to AgentHallu's reasoning category. This study decides whether the contribution matters. If scope errors are a negligible share of real failures, the method is a curiosity and we will report it as such. The same annotations let us split DAG-Math's accuracy-versus-PRR gap into closed dead-end branches, which are harmless, and leaked ones, which are harmful. From that split we define a scope-aware Perfect Reasoning Rate that does not penalize honest search.

Baselines

The naive reference point is answer-only checking, which declares a trace correct when its final answer is correct. On organic traces this sets the floor. On injected scope errors it is uninformative by design, because many leaked traces still reach the right answer. That is exactly DAG-Math's point.

The structural baseline is DAG-Math's logical-closeness check together with acyclicity and reachability tests. These are run on the same extracted graphs, with the scope fields removed. They represent the strongest cheap, deterministic competitor. We predict near-chance detection of scope errors, because those errors do not alter the graph's shape. If this prediction fails, the whole premise is wrong.

The strongest existing method is the Structural Reasoning Model with Flow Score. It reports 76.59% step-level Average Precision on MATH, 13.8 points above the best non-graph baseline, and 83.08% Average Precision on HumanEval (Hallucination Detection from Structural Reasoning Model). We run it with the same judge model, the same extraction, and the same traces, and we count its judge calls and tokens. For scope errors specifically, there is no reported result on Lacuna for Flow Score or any other method. The numbers above are context for its general strength, not a target on our benchmark. Beating it means higher step-level Average Precision on injected and organic scope errors, at no more than its compute. Matching it on value errors is acceptable, and is in fact the expected outcome.

A learned baseline is a graph neural network in the style of GNNVerifier. It is trained on our injected data, with scope fields supplied as node features and with the same training budget we would give any learned component. It tests whether the interval structure must be enforced as a hard constraint, or can simply be learned from enough examples.

A whole-trace LLM judge serves as the coarse reference. Agent-Based Auditing of Mathematical Proofs found that such a judge caught 5 proof errors where a dependency-graph agent caught 25. For localization on agent trajectories we compare against AgentHallu's reported 41.1% step localization accuracy for Gemini-2.5-Pro.

Two ablations isolate the key ingredient. Scope-tag-then-scan has the LLM label every scope boundary explicitly, then runs the trivial containment check with no extension reasoning. Oracle scopes uses gold boundaries from the injection engine and gives the upper bound for the interval check.

Why not just…?

Why not just ask a step-level judge to also check context? Prompting the per-step judge to consider the surrounding trace undoes the reason Flow Score works. That paper conditions each judgment strictly on declared parents in order to remove position bias. Widening the window brings back long-context attribution, and AgentHallu shows this degrades badly with length: 29.9% localization on trajectories of five or fewer steps versus 11.4% on those of eleven or more. We will still run a widened-context variant of the judge, so the claim rests on measurement rather than argument.

Why not just have the LLM tag every scope boundary and run a linear scan? This is the real threat, and it is the scope-tag-then-scan ablation. If parsers reliably mark implicit case ends and retractions, the extension machinery adds nothing, and we will say the contribution reduces to the scope taxonomy and the benchmark. We expect the scan to fail in a specific way. A wrongly placed implicit boundary produces false rejections of valid traces, the same failure the Structural Reasoning Model paper reports for implicit premises. Our check flags only constraints that are infeasible under every placement, so it should not. The decisive measurement is false-rejection rate on clean traces with implicit scopes, at matched detection rate.

Why not just train a classifier on the injected errors? A graph network trained on enough near-miss pairs might learn scope consistency implicitly. GNNVerifier shows such training works for plan graphs. The risk is that it learns the injection templates instead. We train it on two of the three scope-error types and test on the third, and we also test it on organic errors. If it matches the interval check out of distribution, the hard constraint is unnecessary. If its accuracy drops on held-out error types or on organic traces while the interval check's does not, the constraint is doing real work.

Why not just penalize all exploration, as DAG-Math does? Doing so treats every reasoning model's search as failure, and it cannot rank a model that explores and recovers cleanly above one that explores and contaminates its answer. The prevalence study measures directly how much of the 52.4%-to-17.0% gap falls into each kind.

Proposed Experiments and Decisive Checks

The main experiment trains nothing in the core method. It runs every baseline and the interval check on the injected benchmark and on the annotated organic set. We report step-level Average Precision, root-cause localization accuracy in the AgentHallu sense, false-rejection rate on clean traces, and judge calls per trace. Results are broken down by error type, with value errors as the control.

Four outcomes would settle the proposal.

The first is prevalence. If annotators find that scope errors are a non-trivial share of organic reasoning errors in long traces, the class is worth a dedicated tool. If they are rare, we stop there and publish the negative result together with the taxonomy.

The second is blindness of existing checks. On injected scope errors, closeness and reachability checks should sit near chance, and Flow Score should fall well below its MATH performance. On value errors both should behave as published.

The third is the extension check versus tag-then-scan. At equal detection rates, the extension check must show lower false rejection on traces whose scopes are implicit. Otherwise the intersection-graph component is cut.

The fourth is cost. Because the interval check calls no neural judge after extraction, it should cost a small fraction of Flow Score's per-node judge calls. We will report exact solver runtimes, including on the hardest traces where the integer-coordinate version could become expensive.

Finally, we recompute DAG-Math's Perfect Reasoning Rate with closed dead-end branches excused. This shows how much of the reported reasoning-fidelity gap is honest search and how much is leaked search.