Error taxonomies for language-model agents keep growing. One code-agent study uses 3 failure families, a reasoning study clusters errors into 6 types, an agent benchmark has 14 sub-categories, and a logic benchmark lists 232 fallacies. Nobody can say whether any of these lists is complete, or whether new failure kinds will keep appearing as more trajectories are collected. Structural graph theory has a precise tool for exactly this question. If objects are compared by a "contains a copy of" relation that is a well-quasi-order (wqo), meaning every infinite collection contains two objects where one embeds in the other, then any property that persists when an object grows is characterized by a finite list of minimal "forbidden patterns." When the relation is not a wqo, such lists can be infinite.
We propose to use this as an engineering principle for hallucination attribution. Each agent trajectory is encoded as a small labeled structure: a sequence or dependency graph of abstracted steps. Next to it we keep a containment relation, chosen deliberately to sit on the finite side of the wqo boundary. We then mine the minimal failure patterns directly from annotated trajectories. The result is a taxonomy you can test. If the set of minimal patterns stops growing as data accumulates, the taxonomy is empirically complete at that level of detail. The patterns also act as a detector: the earliest step at which a trajectory first contains a minimal pattern is our prediction of where the hallucination started. Because the patterns are checked by an algorithm rather than by prompting a model with definitions, the method avoids the observed failure of language models to apply formal definitions.
Core Claim
The claim has two parts, one conceptual and one practical. The conceptual part: whether a hallucination taxonomy can be finite and complete depends on the representation. For trajectories written as sequences over a finite step alphabet, compared by order-preserving subsequence embedding, Higman's classical lemma guarantees a wqo. Any "a hallucination has already occurred" property that survives extension therefore has a finite basis. Richer representations, such as dependency graphs compared by induced subgraphs, fall outside that guarantee.
We draw on two graph-theory results as templates here. Induced minors and well-quasi-ordering shows that finite characterizability can flip sharply depending on a single excluded structure. It proves that H-induced-minor-free graphs are wqo exactly when H is an induced minor of the Gem or of $\hat{K}_4$. k-Leaf Powers Cannot be Characterized by a Finite Set of Forbidden Induced Subgraphs for k ≥ 5 shows what infinite obstruction families look like: modular gadget chains $H_1, H_2, \dots$, each of which is minimal. Neither paper touches machine learning. We borrow their question ("finite basis or infinite antichain?") and their diagnostic (look for gadget-like families of ever-longer minimal obstructions), not their theorems.
The practical part: minimal patterns mined under a wqo containment relation should localize the responsible step better than language-model judges, especially on long and tool-use trajectories. These are the cases where AgentHallu: Benchmarking Automated Hallucination Attribution of LLM-based Agents reports the steepest collapse, with 11.4% on trajectories of 11 or more steps and 11.6% on tool-use errors. The same patterns should also be better triggers for supervisor intervention than a fixed schedule.
Research Program
Encoding trajectories. Each step of a trajectory is mapped to a symbol from a finite alphabet. The symbol records the action type and the tool invoked. It also records three binary flags: whether the step's output is consumed later, whether the step's claims agree with an earlier observation, and whether the step repeats a prior action. A rule-based extractor produces the symbol, with a small model filling fields that rules cannot determine.
We build the encoding at three levels of richness. The first is a plain sequence under subsequence embedding, which is wqo. The second is a sequence under gap-bounded subsequence embedding. This is a stricter relation that we test empirically, because it is closer to how cascades actually propagate. The third is a dependency graph, where edges link each step to the earlier steps whose outputs it reads, compared by labeled induced subgraph. This last relation carries no wqo guarantee. The three levels form the representation boundary we study.
Labels that persist under extension. AgentHallu annotates the step where the hallucination originates. For a trajectory whose responsible step is $t$, every prefix ending before $t$ is clean and every prefix ending at or after $t$ is contaminated. Contamination therefore survives extension by construction. This matters because wqo theory only yields finite bases for properties that are closed upward.
We cannot assume that a pattern present in one contaminated prefix implies contamination wherever that pattern appears. We measure this directly. The monotonicity rate is the fraction of clean prefixes that contain a pattern mined from contaminated ones. A high rate would mean the representation is too coarse for the finite-basis question to be meaningful at all.
Mining the basis. We search for the set of minimal patterns. Each pattern must embed in contaminated prefixes, must embed in almost no clean prefixes (up to a tolerance $\epsilon$), and must not properly contain another such pattern. We use branch-and-bound over pattern length, pruning any candidate that contains an already-accepted pattern.
Localization rule. The predicted responsible step is the first index at which the growing prefix contains any basis pattern. Ties are broken by pattern precision. For explanation, each pattern is rendered as a short natural-language description, such as "a tool result is asserted before any tool call that could produce it." This follows the finding in When Agents go Astray: Course-Correcting SWE Agents with PRMs that descriptive guidance works better than rigid directives.
Saturation test. We plot basis size against the number of training trajectories, separately for each representation and label granularity. If basis size plateaus while held-out coverage keeps rising, the taxonomy is finite at that level. If basis size keeps growing, we inspect the new minimal patterns for gadget-like chains of increasing length, the empirical analogue of the leaf-power obstructions. We read this as the representation having crossed the boundary, and as a sign that the labels must be coarsened or the containment relation weakened.
This saturation test is the paper's contribution to the taxonomy literature. It turns "is this taxonomy complete?" from a matter of opinion into a curve that can be measured.
Baselines
The first reference point does almost nothing. It predicts that the first tool call or the final step is responsible, whichever scores higher on training data. This shows how much of the accuracy on AgentHallu is positional.
The strongest existing method is a language-model judge using step-by-step prompting, as defined in AgentHallu: Benchmarking Automated Hallucination Attribution of LLM-based Agents. That paper reports that step-by-step prompting adds 12.3% on average over whole-trajectory prompting. It also reports 41.1% step localization accuracy for Gemini-2.5-Pro, the best reported figure, with proprietary models averaging about 35.7% and open-source models 10.9%. We rerun the judge on our exact test split, using the same open-source model that performs our symbol extraction, to control for model strength. Where budget allows, we also run a proprietary judge.
To beat this baseline, pattern localization must exceed the same-model judge overall. It must also approach or exceed the 41.1% frontier figure while using only a small extractor model. The margin should be largest in the ≥11-step and tool-use slices.
On SWE-bench Verified, the strongest method is SWE-PRM, from When Agents go Astray: Course-Correcting SWE Agents with PRMs. It invokes a language-model supervisor every 5 steps and raises resolution from 40.0% to 50.6%. We keep its supervisor model and its prompt unchanged. The only change is when it fires: it is invoked when a basis pattern is newly contained rather than on the fixed schedule. Our variant also passes the rendered pattern description to the supervisor. We match the total number of supervisor calls to the fixed-schedule run. Beating SWE-PRM means higher resolution at equal call count, or equal resolution with fewer calls.
Three ablations isolate the key ingredients. The first keeps every discriminative pattern rather than only the minimal ones, which tests whether minimality matters beyond compactness. The second swaps the sequence encoding for the dependency-graph encoding, which tests the boundary claim directly. The third replaces our fine step alphabet with only AgentHallu's 5 top-level classes as labels.
Why not just…?
Why not just prompt a stronger judge step by step? This is the most obvious alternative, and it keeps improving as models improve. However, AgentHallu shows that even the best judge falls to 11.4% on long trajectories. That drop suggests the judge loses track of accumulated history, which is exactly what an algorithmic containment check does not do. A Closer Look at the Self-Verification Abilities of Large Language Models in Logical Reasoning adds further evidence: models do markedly worse on formal structural errors than on informal ones, and giving them textbook definitions actually lowers their performance. Our length-sliced comparison settles the question. If the judge matches us on long trajectories, the structural approach has no advantage.
Why not just cluster errors from data? Can LLMs Learn from Previous Mistakes? clusters errors from its 609,432-question COTERRORSET into six types and reports real gains, for example PaLM2 on GSM8K rising from 56.29% to 65.13% with self-rethinking. But clusters are not ordered by containment. They cannot tell you at which step an error first appears, and they carry no test of completeness. We include embedding-based clustering of the steps as a localization baseline, with each cluster scored as a detector, and we compare its growth in cluster count against our basis-size curve.
Why not just use discriminative subsequence mining or a sequence classifier? This is the real threat. Our miner is a form of discriminative pattern mining, and a small classifier over step sequences might localize just as well. We accept that framing. What is new is the minimality constraint, the guarantee that the basis is finite under the sequence encoding, and the saturation test. None of these is a claim about accuracy.
We will train a small transformer on the same symbol sequences to predict the responsible step. If it beats pattern localization by a wide margin, we will present the work as a diagnostic tool for completeness rather than as a better detector, and we say so in advance.
Proposed Experiments
The primary testbed is AgentHallu's 693 trajectories, using its 5-class and 14-sub-category annotations. We use a fixed train/test split stratified by domain, and cross-validate the $\epsilon$ tolerance within the training data. The metric is step localization accuracy, reported overall, by trajectory length bucket, and by category, with particular attention to tool use. We also report basis size, held-out coverage, and the monotonicity rate for each representation.
The secondary testbed is SWE-bench Verified, the 500 curated issues introduced through SWE-bench. We mine a basis from SWE-PRM-style annotated trajectories generated on the SWE-bench training split, and measure resolution rate against the call-matched SWE-PRM baseline.
Three checks decide the question. The first is whether, under the sequence encoding, basis size plateaus within the available data while the dependency-graph encoding keeps growing. That result would reproduce a wqo boundary empirically in agent traces. If both plateau, the boundary is irrelevant at this scale. If neither plateaus, the finite-taxonomy hypothesis fails for this alphabet. The second is whether pattern localization beats the same-model step-by-step judge on the ≥11-step slice. The third is whether triggering the supervisor on patterns beats the fixed 5-step schedule at equal cost, specifically on Hard SWE-bench tasks, where SWE-PRM gained only 4.4 points.
A positive result on the first check alone would still give the taxonomy literature what it currently lacks: a measurable criterion for when a list of failure types is finished.
References
- Induced minors and well-quasi-ordering
- k-Leaf Powers Cannot Be Characterized by a Finite Set of Forbidden Induced Subgraphs for k ≥ 5
- AgentHallu: Benchmarking Automated Hallucination Attribution of LLM-based Agents
- When Agents go Astray: Course-Correcting SWE Agents with PRMs
- A Closer Look at the Self-Verification Abilities of Large Language Models in Logical Reasoning
- Can LLMs Learn from Previous Mistakes? Investigating LLMs' Errors to Boost for Reasoning
- SWE-bench: Can Language Models Resolve Real-world Github Issues?