Order-Invariant Premise Memory via Matroid Exchange

Large language models reason worse when the same facts arrive in a different order. Shuffling the premises of a deduction problem can cut accuracy by more than 30% for strong models, and on reordered grade-school math problems GPT-3.5-turbo falls from 100% to 64.9% on items it had already solved (Premise Order Matters in Reasoning with Large Language Models). The fixes proposed so far either reorganize the whole prompt offline with another model call, or force invariance by blocking premises from attending to one another, which also blocks multi-step deduction. Neither fits the setting where order sensitivity hurts most: premises arrive as a stream, from retrieval rounds or from document chunks read one at a time, and the system can hold only a bounded number of them in memory.

We propose to treat premise memory as a matroid, a set system whose defining "exchange" rule lets one item be swapped for another without the structure collapsing. Each premise becomes an edge between the concepts it mentions ("cats are mammals" links cat and mammal). Memory keeps a cycle-free set of at most $k$ such edges, which is a truncated graphic matroid, and it updates by a single swap rule. This has a property the reasoning literature has not used: for a matroid, insert-and-swap maintenance returns the same maximum-weight set no matter what order items arrive in. If each premise is scored on its own, the retained premises are identical for every permutation of the input. A deterministic walk outward from the query concept then produces the same prompt every time. Order invariance follows from the exchange property itself, not from masking attention, and premises in the final prompt can still attend to each other freely.

Core Claim

The claim has two parts. The first is a guarantee. Suppose premise weights are computed per premise, independent of their neighbors, and ties are broken deterministically. Then the reasoning context produced by our pipeline is a deterministic function of the premise set. The variance across permutations at the context level is therefore exactly zero, as it is for Order-Independence Without Fine Tuning, but premises are not isolated from one another. The second part is empirical and could fail. We claim that a query-rooted, cycle-free, bounded set of premises keeps the edges needed for the proof often enough that accuracy approaches the canonical-order upper bound, and beats offline reorganization methods once memory is bounded.

The update rule is the standard one for maintaining a maximum-weight basis under insertions. Let $M$ be the current memory, $w(p)$ a relevance weight for premise $p$, and $C(M, p)$ the unique circuit formed when adding $p$. The circuit is either the cycle that $p$ closes in the concept graph, or all of $M \cup \{p\}$ when the budget $k$ is exceeded. The rule is

$$M \leftarrow \begin{cases} M \cup \{p\} & \text{if } M \cup \{p\} \text{ is independent,} \\ M \cup \{p\} \setminus \{\arg\min_{q \in C(M,p)} w(q)\} & \text{otherwise.} \end{cases}$$

For any matroid this rule ends at the greedy offline optimum, whatever the arrival order. That is where the invariance comes from.

Where This Sits in Prior Work

Three papers motivate the gap. Premise Order Matters in Reasoning with Large Language Models measures the damage and shows that distractor rules make it worse. Language Models Are Greedy Reasoners shows the mechanism: individual steps are valid 93.2% of the time on 5-hop proofs, yet the model commits to misleading branches it cannot undo, and 40-path self-consistency does not repair this. Concise and Organized Perception traces the failure to the model's inability to find the starting premise. Our query-rooted walk targets that "entry point" problem directly.

Two papers supply the method. Matroid prophet inequalities gives the opportunity-cost threshold for the case where acceptance is irrevocable. That algorithm achieves half of an omniscient selector's value in expectation over prior distributions, which is the right tool when memory cannot be revised. Robust Guarantees of Stochastic Greedy Algorithms proves that under matroid constraints noisy greedy selection can lose everything, whereas under plain cardinality constraints the errors average out. This constrains our design. The swap rule matters precisely because irrevocable greedy filtering over a dependency structure is fragile, and we test that prediction directly.

Two papers are the closest competitors. Chow–Liu Ordering for Long-Context Reasoning in Chain-of-Agents already builds a maximum spanning tree, and spanning trees are graphic-matroid bases. Its tree, however, is over chunks as nodes, weighted by embedding similarity, built offline over all chunks, and every chunk is processed. We differ on three axes. Our graph is over concepts as nodes with premises as edges, so a cycle means a redundant premise rather than a similar chunk. Memory is bounded and filled online. The pruned set, not the full set, reaches the reasoner. COP reorganizes premises through LLM prompting over a fully buffered prompt. That restructuring call is itself a model reading an ordered prompt, so it carries no invariance guarantee, and it does not apply when premises exceed the buffer. Set-based prompting achieves exact invariance by masking, which, as its authors note, prevents premises from attending to each other.

Research Program

The pipeline has four pieces. A premise parser maps each premise, in isolation, to an edge between concept nodes. For ProntoQA, ProofWriter and SimpleLogic this is nearly deterministic. For natural text we use a small model prompted on one sentence at a time, which keeps the parser order-independent. A weight function scores each premise against the query in isolation. We compare embedding similarity, an LLM relevance score computed per premise, and a structural score: the hop distance from the query concept in the concept graph seen so far. The structural score is order-dependent, so it is reported separately and the guarantee is not claimed for it. Memory follows the swap rule above. When the task forbids revision, it follows the Kleinberg–Weinberg threshold instead, with distributions estimated from training problems in the spirit of Sample-Based Matroid Prophet Inequalities. Finally, a linearizer runs a depth-first walk from the query concept with deterministic tie-breaking and emits the premises in walk order.

The main risk is known in advance. Implications have direction, but the forest is undirected. When a distractor closes a cycle with a true edge, the swap rule may drop the true edge if its weight is lower. The guarantee is therefore invariance, not correctness, and accuracy depends on the weights. We will measure proof-edge recall of the retained memory separately from final answer accuracy, so that losses can be attributed to selection, ordering, or reasoning. Math word problems need extra care. A sentence like "she bought 3 more than twice the apples" relates several quantities at once, which makes it a hyperedge, and the graphic structure breaks. For R-GSM and DI-GSM we fall back to a partition matroid that caps premises per mentioned quantity. We treat these benchmarks as a stress test, not the main evidence.

Baselines

The naive reference is standard chain-of-thought on the premises in their given shuffled order, alongside the same model on the canonical forward order ($\tau = 1$ in the Kendall-tau parameterization of Premise Order Matters). The canonical-order run is an oracle ceiling, not a competitor. Closing the gap between these two numbers is the target. That paper reports drops of over 30% on SimpleLogic-style problems and 100% to 64.9% for GPT-3.5-turbo on its R-GSM subset. We reproduce both endpoints with our models before claiming anything.

The strongest existing method on deduction is COP. It is reported to raise 5-hop ProofWriter accuracy from 35.9% with chain-of-thought to 71.9% (Concise and Organized Perception). We run COP with its published prompts on the same base models, the same premise sets and the same permutations, and give it a matching number of model calls. Beating it means two things. On fully buffered ProofWriter D5 and ProntoQA, our mean accuracy must be within noise of COP or above it, with lower across-permutation variance; COP's variance has not been reported, and we expect it to be nonzero. In the bounded-memory streaming variant, where COP must see premises in windows, we must exceed it outright.

The strongest dependency-aware ordering method is CL-ORDER. It reports gains over query-similarity ordering of +2.17 to +4.06 exact-match points on LongQA multiple choice, and +1.58% to +2.97% answer relevance on NarrativeQA (Chow–Liu Ordering). We run it, and its DENSE similarity baseline, inside the same Chain-of-Agents pipeline with the same memory budget and the same embedding model. Beating it means higher exact match at equal budget on ∞Bench LongQA-MC and on the HELMET book QA tasks. No reported HELMET number was found on Lacuna, so there we compare only against our own rerun.

Set-based prompting is the invariance baseline (Order-Independence Without Fine Tuning). We apply it with each premise as a parallel branch. It matches us on invariance, so beating it means higher accuracy on 3+ hop problems at zero variance.

Four ablations isolate the key ingredient. First, cardinality top-k keeps the $k$ highest-weight premises with no cycle constraint. This tests whether the matroid structure matters beyond budget, which is the Hassidim–Singer contrast in empirical form. Second, irrevocable greedy accepts any independent premise and never swaps. This tests whether the exchange step matters. Third, the prophet threshold is the irrevocable regime done properly. Fourth, forest without ordering shuffles the retained forest before prompting, which separates the benefit of pruning from the benefit of query-rooted order.

Why not just…?

Why not just parse the premises and run a symbolic solver or topological sort? On clean synthetic logic this is a real threat. If premises parse perfectly, a topological sort from the query solves the ordering problem, and a solver may solve the whole task. We include a parse-then-sort baseline on ProntoQA and SimpleLogic and expect it to tie us there. Our case rests on the regimes where parsing is partial, as in natural-language ProofWriter paraphrases and long-document chunks. There a symbolic pipeline fails hard on any missed edge, while our pipeline only needs good-enough weights. If parse-then-sort matches us on ProofWriter paraphrases and long-context QA too, the matroid machinery is unnecessary, and we will say so.

Why not just shuffle the premises several times and take a majority vote? Language Models Are Greedy Reasoners found that 40 sampled reasoning paths did not repair systematic misleading-step errors. Voting across permutations also multiplies inference cost by the number of permutations and gives no invariance guarantee. We run permutation-voting with 5 and 20 permutations at matched and at 5× compute, and report accuracy per model call.

Why not just use COP, which already doubles 5-hop accuracy? On fully buffered problems COP may well match us, and we report that honestly. The differences we test are whether COP's own restructuring call is order-sensitive and whether it degrades when premises arrive in windows smaller than the problem. The experiment that settles this measures COP's across-permutation standard deviation, and its accuracy as the window shrinks from the whole problem to a quarter of it.

Why not just use CL-ORDER and truncate to $k$ chunks? This is the closest alternative, and the reason a whole ablation exists. Truncated CL-ORDER is also built on a spanning tree. What separates the two is whether edges should be premises over concepts, which makes cycles mean redundancy, or similarities over chunks, and whether memory is built online. We run truncated CL-ORDER at every budget we test. If it matches us, our contribution shrinks to the streaming regime alone.

Proposed Experiments

Deduction experiments use ProntoQA (1, 3 and 5 hops), ProofWriter D3 and D5, and SimpleLogic with 0, 5 and 10 distractors. Each problem is evaluated at Kendall tau of 1, 0, −1 and 10 random permutations. We report mean accuracy, the canonical-minus-shuffled gap, the across-permutation standard deviation, and proof-edge recall of retained memory. To create the streaming regime, we interleave premises with long distractor text and deliver them in windows to a Chain-of-Agents reader with budgets of $k \in \{4, 8, 16\}$ premises. Long-context experiments use ∞Bench LongQA and LongQA-MC, NarrativeQA, and HELMET book QA, with sentence-level premises extracted per chunk. Stress tests use R-GSM and DI-GSM under the partition-matroid variant. Base models are an open model such as Qwen-3 and a GPT-4.1-class API model, matching the CL-ORDER setup.

Three checks decide the proposal. The first is invariance. Context-level variance must be exactly zero for the per-premise weight functions, and answer-level variance must fall below COP's and below raw chain-of-thought's; if it does not, the guarantee does not reach the output. The second is the structure test. Swap-based matroid memory must beat both cardinality top-k and irrevocable greedy at equal budget. The gap should grow with distractor count, because the Hassidim–Singer analysis predicts fragility from early commitment under dependency structure and none under pure budget. If the gap does not appear, the matroid framing is decorative. The third is the ceiling test. On 5-hop ProofWriter and 10-distractor SimpleLogic, our shuffled-input accuracy should recover most of the gap to canonical order. Proof-edge recall tells us whether any remaining loss comes from the undirected forest dropping true edges, which would justify a directed version as follow-up work.