Can the Configuration Exist? Matroid Realizability Checks for Reasoning Graphs

Tools that map a language model's reasoning as a graph of claims and dependencies check whether each step has parents and whether every step feeds the final answer. None of them ask whether the starting objects the argument posits can exist at all. Many olympiad and research arguments start from such posits: "choose seven points in the plane so that these triples are collinear," "take a linear code of length $n$ over $\mathbb{F}_p$ in which every two coordinates are independent," "pick vectors with exactly these dependencies." If those hypotheses are jointly impossible, a perfectly connected derivation from them is worthless, and today's graph checkers will score it as logically closed.

We propose to close this gap for the class of claims where it can be closed exactly: claims about which subsets of points or vectors are independent, collinear, or coplanar. These claims define a matroid, an abstract record of which subsets are independent. Asking whether the posited objects exist is then the classical question of whether that matroid can be realized by actual vectors over the intended field. The contribution is a realizability auditor that pulls these existence claims out of a reasoning graph, builds the matroid they imply, and returns one of three outcomes. It either finds explicit coordinates, proves that no coordinates exist by pointing to a known obstruction, or reports that the question is undecided. We test it on a benchmark of "realizability traps," impossible configurations built from matroid theory, and ask whether current graph-based checkers, model judges, and plain numerical search accept arguments built on them.

Core Claim

Existing dependency mappers treat premises and existence claims as unchecked leaves of the reasoning graph. DAG-Math defines logical closeness and the Perfect Reasoning Rate (PRR) from graph connectivity and explicitly assumes each step's content is correct. ProofFlow uses its graph to schedule formalization into Lean, a proof assistant. CGRiC bounds the risk of the whole output by combining per-claim risks with union bounds. CoTJudger measures redundancy by extracting the shortest effective path through the graph. All four motivate this proposal, because none can flag a derivation whose hypotheses are jointly unsatisfiable.

The work of Kim, de Mesmay and Miltzow shows why such errors are not exotic. Deciding real realizability is ∃ℝ-complete (as hard as deciding whether a system of real polynomial equations has a solution) already in rank 3, through von Staudt gadgets that encode arithmetic as collinearity. Local incidence statements that each look harmless can therefore jointly encode a polynomial system with no real solution. Our claim is that, for incidence and independence statements, a tiered certificate checker catches such impossible hypotheses with much higher recall than model judges, at matched false-alarm rates. Unlike numerical search, it also gives proofs of impossibility rather than mere failure to find coordinates. Graph structure adds something further: the auditor can localize the smallest inconsistent sub-configuration, which enables targeted repair of the argument.

We deliberately do not claim that general reasoning traces form matroids. Logical entailment does not satisfy the exchange axiom, so rank-based redundancy for arbitrary claims would be a metaphor rather than a measurement. The matroid enters only where the claims literally assert linear or incidence independence, which keeps the method exact.

Research Program

Extraction. The extraction stage reads a DAG-MATH-format trace or a ProofFlow dependency graph. It tags nodes that assert existence, incidence, or independence among a finite set of named objects, together with the intended field ($\mathbb{R}$, $\mathbb{C}$, $\mathbb{Q}$, or $\mathbb{F}_q$). It then compiles their union into a rank function on the ground set: stated collinearities give rank-2 sets, and stated general position gives rank-3 triples. Unstated relations are treated as free, meaning the configuration must merely be realizable with at least the stated dependencies. Distinctness and explicit non-collinearity claims become strict constraints. Extraction uses the same language model for all compared systems, so extraction noise is shared across conditions. Its accuracy is measured separately against hand annotation.

The checker works in four tiers, cheapest first.

The first tier searches for embedded minors that are known to obstruct representability, meaning small sub-configurations that already rule out certain fields:

  • The Fano plane and its relatives rule out characteristic other than 2.
  • The non-Pappus configuration rules out every field.
  • The Vámos matroid is non-representable outright.
  • Uniform minors $U_{2,q+2}$ rule out $\mathbb{F}_q$. This last case is exactly the bound Abbe and Spirkl state in entropic form ($U_{2,p+2}$ is never $p$-entropic), and it is what makes coding-theory existence claims checkable.

The second tier computes the foundation for small instances, following the colimit-over-minors presentation of Baker et al.. The foundation is the universal algebraic structure over which a matroid can be represented. It yields field-class certificates beyond the hand-listed minors, at the cost of symbolic computation that we budget explicitly.

The third tier sets up the symbolic matrix with stated zero-minors. It then decides consistency exactly with Gröbner bases over $\mathbb{Q}$ or a finite field, or finds a witness by substituting random field values into the symbolic matrix in the style of Harvey.

The fourth tier, for real-only obstructions, runs numerical optimization for positive witnesses with exact rational verification. Anything still unresolved is reported as undecided rather than guessed. The ∃ℝ-hardness result tells us this last bucket cannot be eliminated in general. How large it is in practice is a measured quantity.

When the checker finds an obstruction, the offending minor maps back to a specific set of reasoning-graph nodes. This gives CGRiC-style local repair a precise target: the hypothesis nodes to revise or drop.

The trap benchmark. We build traps three ways:

  • Inject impossible incidence hypotheses into geometry and discrete-mathematics problems from Omni-MATH and its DAG-MATH gold traces (2,894 traces, resource DAG-MATH).
  • Generate rank-3 configurations from von Staudt gadgets encoding polynomial systems with and without real solutions. This gives controlled hardness at fixed surface form.
  • Pose coding-theory existence claims over small fields.

Each trap has a realizable twin that differs minimally, so a detector cannot win by flagging surface features. The traps are then given to strong reasoning models, which produce full derivations. Those derivations are what the checkers audit.

Baselines

The naive reference point is accepting every logically closed graph. This is DAG-Math's PRR criterion applied as an acceptance test, under which every trap derivation that is connected and reaches its answer passes. For scale, the DAG-Math authors report that Gemini-2.5-Flash on AIME 2025 reaches 52.4% accuracy but only 17.0% PRR. Their criterion is therefore already strict about structure, and we measure how many of its accepted graphs rest on impossible hypotheses.

The strongest existing auditing method is the agent of Nguyen and Zhang. It builds dependency graphs and atomic step tables, then tries to falsify steps. It reported 25 flagged errors, 23 verified (92%), against 5 for a monolithic model-as-judge on theory papers. It is the strongest competitor because it actively hunts for falsifying conditions, which is the closest existing behavior to asking whether the configuration exists. We run it with the same backbone model and the same per-problem dollar budget as our extraction step. Two further baselines run under identical inputs: a monolithic judge prompted specifically to check hypothesis consistency, and the CGRiC pipeline scored as a detector.

The dangerous non-model baseline is pure numerical realization search under the same wall-clock budget. It flags a configuration when optimization fails to reach zero residual.

There is no reported result found on Lacuna for detecting unrealizable hypotheses in reasoning traces, so all detection numbers will be new. We count the proposal as beating a baseline under two conditions. First, it must achieve higher recall on traps at a false-alarm rate on realizable twins no higher than that baseline's. Second, for the numerical baseline specifically, it must produce verifiable impossibility certificates on a majority of the traps it flags.

Three ablations isolate the ingredients:

  • Removing the minor and foundation tiers tests whether matroid structure matters, or whether exact algebra alone suffices.
  • Removing the graph and checking all extracted claims jointly, without node attribution, tests whether localization improves repair. We measure repair success and the fraction of tokens kept, following CGRiC's 78% retention as the reference.
  • Using gold extraction instead of model extraction separates checker quality from parsing quality.

Why not just…?

Why not just ask a strong model whether the hypotheses are consistent? Evidence from Nguyen and Zhang shows monolithic judges miss most structural errors: 5 found against 23 verified by structured auditing. Omni-MATH also reports that models are weakest on discrete mathematics. Still, a targeted consistency prompt is cheap, and it may handle textbook cases like the Fano plane from memory. The von Staudt traps, whose impossibility is arithmetic rather than famous, are designed to show whether this holds beyond recall of named configurations.

Why not just search numerically for coordinates? This is the real threat. Numerical search will find witnesses for most realizable twins, and failure to converge is a decent heuristic signal. It cannot, however, distinguish "impossible" from "hard to find." Its precision should degrade on gadget-encoded systems with near-solutions, and it does nothing for finite-field claims. If numerical failure matches our recall at equal false-alarm rate, the remaining contribution shrinks to certificates and finite fields, and we will report it that way.

Why not just formalize in Lean and let the proof assistant catch it? Lean would catch an impossible hypothesis only if someone proved its negation, which nobody does for free. ProofFlow also identifies the formalization stage itself as its bottleneck. A Lean proof built on an inconsistent hypothesis compiles happily. Our checker is complementary: it can attach a non-existence certificate before formalization begins.

Decisive Checks

The first check is the coverage of the method on natural data. We measure what fraction of Omni-MATH geometry and discrete-mathematics traces, and of the 184 ProofFlowBench problems, contain matroid-expressible existence claims. If that fraction is tiny, the method is a specialist tool for constructions and coding claims, and we will say so.

The second check runs on the paired traps. It compares the checker against the agent auditor, the targeted judge, and numerical search, using recall at matched false-alarm rate, certified-impossibility rate, and the size of the undecided bucket as gadget complexity grows. The ∃ℝ-hardness result predicts the undecided bucket will grow with complexity, and how fast it grows is the honest limit of the approach.

The third check asks whether flagged inconsistencies, once localized to graph nodes, lead to repaired derivations that pass both DAG-Math closeness and the realizability check.