Learning the Premise Logic of Reasoning Traces with Subset Interventions

When a language model writes out a chain of reasoning, we would like to know which earlier sentences each later sentence actually relies on. Current tools answer this one sentence at a time. They blank out a single earlier step and check whether the later step changes. That test silently assumes that each dependency is an "and": the later step needs every one of its premises, so removing any one of them breaks it. Real reasoning often has "or" structure. A fact gets restated, or two independent routes reach the same lemma, or either of two cells in a puzzle rules out a value. Under that structure, removing one premise does nothing, and the dependency never shows up. We propose to treat each reasoning step as a small unknown Boolean function of its earlier sentences. An intervention hides a chosen subset of earlier sentences from the model and records whether the step survives. We then recover both the dependency graph and the logical form of each dependency (and, or, k-of-n, single parent) with an adaptive search that uses far fewer model calls than exhaustive subset testing.

The idea borrows a lesson from constraint theory. When a constraint is symmetric, it depends only on how many of its inputs are active. When it is asymmetric, it depends on which ones. That lesson carries over to how dependencies can be discovered. Rosenkrantz et al. showed that the wiring of a networked system can be learned efficiently by active queries, but only when each node's update rule is symmetric or a threshold rule. Per-sentence masking in LLM interpretability is the one-parent special case of the same problem. Our claim is that dependencies in reasoning traces are frequently of the asymmetric, disjunctive kind. On those dependencies, single-knockout methods lose recall in a predictable way, and adaptive subset queries recover it at close to the cost of single knockouts.

Core Claim and What Is New

Fix a trace with sentences $s_1,\dots,s_n$ and a target step $s_j$. For any subset $S$ of earlier sentences, define $f_j(S)=1$ if $s_j$ is still supported when attention to all sentences outside $S$ is blocked. "Supported" means that the teacher-forced log-probability of $s_j$ stays within a calibrated tolerance of its unmasked value. The dependency structure of $s_j$ is then the set of minimal subsets $S$ with $f_j(S)=1$. That set is a single subset for an "and" dependency and several subsets for an "or".

Thought Anchors builds causal dependency graphs by masking attention to one prior sentence at a time and by reading off late-layer "receiver" attention heads. In our notation, that estimates only $f_j$ with one sentence removed. It is exactly blind to disjunctions. Our proposal differs in three ways. It queries subsets. It returns the logical form of each dependency, not only which edges exist. And it comes with an explicit accounting of query cost that we measure against the naive exhaustive method.

The algorithmic template adapts the anchor-node binary search of Efficiently Learning the Topology and Behavior of a Networked Dynamical System Via Active Queries. That method recovers topology in $O(n + m\log n)$ adaptive queries for $m$ edges, but it relies on threshold update rules. We drop that assumption. When a step's support is monotone in its available premises, meaning that adding context never destroys support, a group-testing search can isolate each minimal premise set by repeated halving. Monotonicity is what makes the halving sound, so we test it empirically rather than assume it.

The same paper names a blind spot that transfers directly. A node whose output is constant reveals nothing about its inputs. In traces, steps that the model can produce from its weights alone (restatements, memorized facts) are unidentifiable in the same sense. We report their frequency as a first-class quantity rather than silently scoring them as having no parents.

Research Program

Intervention and threshold. We will implement subset attention masking on open-weight reasoning models at the sentence level. The tolerance for "supported" will be calibrated on held-out traces, using random subset masks to estimate the null variation.

Search algorithm. The adaptive search has three stages. It first runs single knockouts, which cost one call per earlier sentence and give the Thought Anchors graph at the same price. It then finds sentences whose single knockout had no effect but whose group removal does, and descends into those groups by halving. Finally, it verifies each candidate minimal set and fits the step's dependency to a small hypothesis class: single parent, "and", "or", k-of-n, or unresolved.

Checks and structural lens. A monotonicity audit on random subset pairs tells us how often the search's core assumption fails. As an analysis lens, we will relate the mix of dependency types to the constraint structure of each task. In grid puzzles, for example, a cell deduction can have several sufficient justifications, and this is where we expect disjunctions. We will not claim a formal link to counting dichotomies such as The Complexity of Holant Problems over Boolean Domain with Non-negative Weights. That paper only motivates the symmetric-versus-asymmetric distinction.

Data and Ground Truth

Three benchmarks in the file come with reference dependency graphs. The 2,894 verified DAGs of DAG-Math give math traces with declared parents. The 184 problems of ProofFlowBench in ProofFlow have human-verified dependency graphs. The 21 Tatham-derived grid puzzles of Reasoning Structure of Large Language Models have an executable verifier that can enumerate all sufficient justifications of a claim. That last property makes the puzzles our main source of true disjunctive ground truth.

Reference graphs describe logical dependency, while interventions measure what the model computationally used. The two can legitimately differ. To get a setting where they coincide by construction, we add synthetic tasks built from iterated composition ($t$-Comp) in Ehrenfeucht-Haussler Rank and Chain of Thought. We will plant redundant copies of intermediate values, which creates known "or" dependencies at controlled rates.

Baselines

The naive reference point assumes each step depends only on the step immediately before it. This linear-chain view is the implicit model of ordinary chain-of-thought. It tells us how much of the reference graph is recoverable with no model calls at all.

The strongest existing intervention method is single-sentence attention masking from Thought Anchors, together with its receiver-head attention readout. It is the direct competitor because it measures the same kind of model-internal dependence we do. We will run it on the same traces and models with the same calibrated tolerance. We will tune its threshold on the same held-out split and report it at its native cost and at our method's cost, the latter by adding random pair masks to spend the extra budget.

The strongest text-based competitor has two parts. One is the claim-graph parser of Reasoning Structure of Large Language Models. The other is prompting the model to declare its own parents in the format of DAG-Math. Both use the same base model and a matched token budget.

An exhaustive subset search on short traces (up to roughly 12 candidate premises) serves as the accuracy ceiling. The key ablation replaces our hypothesis class with a symmetric threshold model, in which support depends only on how many candidate premises remain, as in the Rosenkrantz setting. This isolates whether modeling which premises matter, rather than how many, is doing the work.

No reported result on Lacuna exists for dependency-edge recovery F1 by any of these methods. The closest reported numbers are downstream. DAG-Math reports a Perfect Reasoning Rate of 17.0% against 52.4% PASS@1 for Gemini-2.5-Flash on AIME 2025. ProofFlow reports an aggregate ProofScore of 0.545 against 0.279 for all-at-once formalization.

Our method beats the field if two things hold on puzzle and synthetic traces. First, at no more than twice the call budget of single-knockout masking, it matches that method's precision. Second, it significantly exceeds that method's recall on reference "or" dependencies, while approaching the exhaustive ceiling.

Why not just…?

Why not just mask one sentence at a time, as Thought Anchors does? That approach is cheaper and well validated, but by construction it cannot detect a premise that has a redundant substitute. The planted-redundancy synthetic tasks measure exactly this failure: single-knockout recall should fall in proportion to the planted "or" rate, while ours should not. The real threat is that disjunctive dependencies turn out to be rare in natural traces. The puzzle and DAG-Math experiments measure that rate. If it is small, the contribution shrinks to a cheaper route to the same graph, and we will say so.

Why not just ask the model, or a parser, to write out the graph? Declared graphs describe what the model says it used, not what it used. The gap reported by DAG-Math between correct answers and logically closed traces suggests the two diverge. We will compare declared and parsed edges against intervention-recovered edges on the synthetic tasks, where the true computational dependencies are known.

Why not just read dependencies off attention weights? Receiver heads are included as a baseline at zero extra cost. Attention to a sentence does not imply that the output needs it, especially when two sentences carry the same information. If attention matches our recall on planted disjunctions, our intervention cost is unjustified. The experiment decides this directly.

Decisive Checks

We report edge precision and recall, and correctness of the recovered dependency type, against reference graphs. We also report model calls per trace, the monotonicity-violation rate, and the fraction of unidentifiable steps whose support never changes under any mask.

The central experiment sweeps the planted "or" rate in $t$-Comp traces. We expect single-knockout recall to degrade linearly while our method stays flat, at a call cost growing with the number of true premise sets times $\log n$ rather than with $2^n$. The binary-search analysis motivates that cost profile.

On the grid puzzles, we test whether the fraction of disjunctive steps rises with difficulty tier and with the verification subgraphs noted by the Reasoning Structure paper. A null result would be informative too: it would mean that single knockout is adequate on natural traces.

As a downstream check, we recompute logical closeness on DAG-Math traces using intervention graphs. We then ask whether it predicts answer correctness better than declared graphs do.