💻 computer science

Fantastic Adaptive Taxonomies and How to Use Them

The paper introduces AdaMAST, a system that automatically induces compact, evidence-grounded failure taxonomies from agent execution traces to serve as a reusable feedback interface, significantly improving agent performance across search, runtime, and trajectory selection tasks compared to traditional free-form reflection methods.

Original authors: Mert Cemri, Andrei Cojocaru, Melissa Pan, Shu Liu, Shubham Agarwal, Alexander Krentsel, Jay Tang, Kannan Ramchandran, Joseph E. Gonzalez, Matei Zaharia, Alex Dimakis, Ion Stoica

Published 2026-07-21

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Mert Cemri, Andrei Cojocaru, Melissa Pan, Shu Liu, Shubham Agarwal, Alexander Krentsel, Jay Tang, Kannan Ramchandran, Joseph E. Gonzalez, Matei Zaharia, Alex Dimakis, Ion Stoica

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a very smart, but slightly clumsy, robot to solve puzzles. Every time the robot tries to solve a puzzle, it leaves behind a long, messy trail of thoughts, actions, and mistakes. This trail is called an "execution trace." For a long time, scientists trying to fix these robots had two main ways to look at the mess. The first way was just to say, "You failed," and move on. This is like a teacher giving a red "F" on a test without telling you why you got it wrong. The second way was to ask the robot to write a long, rambling essay about what went wrong. This is better, but it's like asking a student to write a new essay about every single math problem they get wrong, over and over again, using different words each time. The robot never learns a consistent vocabulary for its mistakes, and the teacher (or the computer program trying to fix the robot) gets overwhelmed by all the different ways the same error is described.

The big question in this corner of computer science is: How do we help these AI agents learn from their failures without getting bogged down in endless, repetitive text? The goal is to turn those messy, long trails of errors into a clean, organized list of "failure codes"—like a standardized dictionary of mistakes. If the robot keeps forgetting to check its work, instead of writing a paragraph about it every time, it should just get a tag that says "Forgot to Check." This allows the system to spot patterns, fix the root cause, and stop making the same mistake twice. This is the foundation for the new method called AdaMAST.

The Paper's Big Idea: The Robot's Personal "Error Dictionary"

This paper introduces a clever new system called AdaMAST (Adaptive Multi-Agent System Failure Taxonomies). Think of AdaMAST as a super-smart librarian who watches a robot agent try to solve problems, and instead of just reading the robot's messy diary, the librarian creates a personalized, living dictionary of mistakes.

Here is how it works in the wild:

The Observation: The robot tries to solve a bunch of tasks (like writing code or solving math problems) and fails. It leaves behind a long, messy trail of text.
The Magic Translation: Instead of humans reading every single word, AdaMAST reads the trail and says, "Ah, I see this pattern! The robot kept trying to use a tool that doesn't exist," or "The robot stopped thinking too early." It turns these messy observations into short, catchy names like "Premature_Reasoning_Truncation" or "Tool_Mismatch."
The Living Dictionary: The system builds a "taxonomy," which is just a fancy word for a categorized list. This list has three shelves:
- System-level: Mistakes with the whole setup (like the robot getting stuck in a loop).
- Role-specific: Mistakes by specific parts of the robot team (like the "checker" part being lazy).
- Domain-specific: Mistakes about the actual subject matter (like getting the math wrong).
The Best Part: The robot never has to be taught this dictionary by a human. The dictionary is built entirely from the robot's own failures. It's like if a student wrote their own study guide based on their own bad test answers, and then used that guide to study for the next test.

What the Paper Found: The Dictionary Works

The authors tested this idea in three different ways, and the results suggest that having this "Error Dictionary" makes the robots significantly smarter and more reliable.

1. Finding Better Robot Designs (The Search)
Imagine you are trying to invent a better robot by mixing and matching different parts. Usually, you just look at the score: "This robot got 80%, that one got 85%." But with AdaMAST, the system looks at the dictionary codes of the failed robots.

The Result: When the researchers used these codes to guide their search for better robot designs, the new robots performed much better. On five different types of challenges (from competitive programming to math), the robots using the dictionary improved their scores by 3.4% to 7.5% compared to robots that just got vague, free-text feedback.
The Analogy: It's like a coach telling a player, "You keep missing the ball because you're looking at the wrong spot" (a specific code) instead of just saying, "You played badly" (a generic score). The player knows exactly what to fix.

2. Fixing Mistakes While Working (Runtime Monitoring)
Sometimes, a robot is in the middle of a task and starts to go off the rails. The paper tested if the robot could stop, check its own "Error Dictionary," and fix itself before finishing.

The Result: When the robot was given this dictionary to check itself, it solved more problems.
- On a software engineering test called SWE-bench, a robot named SWE-agent went from solving 60% of problems with normal self-checking to 70% with the dictionary.
- Another robot, Claude Code, went from 64.0% to 70.7%.
The Takeaway: The dictionary helped the robot catch specific, recurring errors (like forgetting to check for syntax errors) that it kept missing when just using a generic "check your work" prompt.

3. Picking the Best Attempt (Trajectory Selection)
Imagine a robot tries to solve a problem five times. You don't know which one is right, but you have to pick the winner.

The Result: The researchers built a "judge" that looked at the five attempts and counted the "Error Codes." The attempt with the fewest error codes was usually the winner.
The Numbers: This method improved the accuracy of picking the right answer by 8 to 15 points compared to just guessing or using a standard checklist. It was especially good at spotting the difference between a "close but wrong" attempt and a "actually right" one.

What the Paper Rules Out (And What It Doesn't)

The authors are careful to point out what this system is not.

It's not a magic wand for everything: The paper shows that a fixed, pre-made list of errors (like a standard textbook list) is okay, but it's not as good as a dictionary built specifically for the robot's own style. The "Adaptive" part is key. If you use a generic list, you miss the unique, weird mistakes that only your robot makes.
It's not about writing better essays: The paper tested if writing the feedback in a fancy, structured format (like a list) was the secret sauce. They found that the content of the dictionary mattered more than the format. The real win was having a consistent, reusable list of names for the errors, not just the way the words were arranged.
It's not a human invention: The paper explicitly argues against humans writing these lists by hand. They found that when humans try to guess what errors a robot will make, they miss the specific, weird ones. The robot's own behavior is the best teacher.

How Sure Are We?

The paper presents these findings as measured results from real experiments, not just guesses.

The numbers are solid: The improvements (like the jump from 60% to 70% in problem-solving) were measured across multiple different tests and different types of robots.
The "Dictionary" is compact: The authors showed that this dictionary is incredibly efficient. It can compress a huge amount of messy failure data into a tiny list of codes (about 18 times smaller) without losing the important details.
It's human-friendly: When they compared the robot's self-made dictionary to a list made by human experts, the robot's list actually matched the experts' understanding of the errors better than the human-made list did. This suggests the robot is surprisingly good at understanding its own mistakes.

In short, AdaMAST suggests that the best way to fix a smart robot isn't to write it a new manual or give it a generic scolding. Instead, you should let it build its own dictionary of mistakes from its own failures, and then use that dictionary to teach it how to do better next time. It turns a messy pile of errors into a clear, actionable roadmap for improvement.

Technical Summary: Fantastic Adaptive Taxonomies and How to Use Them (AdaMAST)

1. Problem Statement

Current methods for improving Large Language Model (LLM) agent systems without modifying model weights rely on consuming execution traces. These procedures—such as trajectory selection, prompt/workflow optimization, and runtime monitoring—extract feedback from raw traces to diagnose failures. However, the paper argues that raw traces are a suboptimal medium for accumulating feedback because they are:

Long and instance-specific: They consume significant context window space.
Lacking stable vocabulary: Recurring failure patterns (e.g., a specific tool call retry or a checker rubber-stamping a solver) are re-diagnosed in free-text prose on every run. This prevents the accumulation of a shared, reusable diagnostic interface.
Inefficient for feedback loops: Free-text critiques are discarded after each run, while scalar outcomes (pass/fail) lack diagnostic depth.

Existing fixed taxonomies (e.g., MAST) face structural limitations: they presuppose specific agent roles and domain knowledge that may not exist in a target system, leading to a mismatch between the vocabulary and the actual failure modes observed.

2. Methodology: AdaMAST

The paper introduces AdaMAST (Adaptive Multi-Agent System Failure Taxonomies), a pipeline that induces a compact, evidence-grounded failure vocabulary directly from a target system's execution traces.

Core Architecture

The induced taxonomy consists of named failure codes organized along three fixed axes, ensuring comparability across systems while allowing the content to adapt:

System-level (Axis A): Failures requiring changes to the harness or orchestration (e.g., instruction non-compliance, stagnation).
Role-specific (Axis B): Failures specific to discovered agent roles (e.g., checker non-compliance, coordinator aggregation). These are fully trace-induced; if a system has no differentiated roles, this axis remains empty.
Domain-specific (Axis C): Failures requiring task-specific knowledge (e.g., combinatorics misreasoning, physical law violations).

The Induction Pipeline

The taxonomy generation process is a one-time cost per target system, consisting of four phases:

Analysis: Extracts domain context, discovered agent roles, and recurring behavioral signals from a sample of traces.
Curation: Proposes candidate codes for each axis. System and domain codes are seeded by broad priors proposed by the pipeline; role codes are fully induced from the architecture.
Consolidation: Removes duplicates, repairs naming violations, and enforces coverage rules. This phase compiles to approximately eight LLM calls.
Inter-Annotator Agreement (Deployment Gate): Four independent LLM annotators label held-out trajectories. The taxonomy is accepted only if mean pairwise Cohen's $\kappa \ge 0.75$ (at the failure-area level) with a coverage floor of 0.70. If targets are not met, the system proposes edits (merge, add, relabel) and re-runs.

Online Refinement

As the target system evolves (e.g., during search-based optimization), the taxonomy can be refined online. Refinement events merge, add, or relabel codes based on recent traces, ensuring the vocabulary tracks the current system state rather than a historical snapshot.

Integration Modes

The induced taxonomy serves as a shared feedback interface for three distinct consumer types:

Agent-System Search: Taxonomy-coded diagnoses (fired codes + evidence) replace free-text reflection in mutation prompts to guide evolutionary search (e.g., AdaEvolve).
Runtime Monitoring: The taxonomy acts as a "runtime skill" or in-context anchor, allowing the agent to self-check against known failure modes at specific checkpoints.
Trajectory Selection: A verifier (AdaMAST-Judge) converts induced codes into verification criteria to rank candidate trajectories without ground-truth checkers.

3. Key Contributions

Adaptive Failure Taxonomies: A pipeline that induces compact, evidence-grounded taxonomies from traces along three fixed axes without hand-authored codes or per-trace human annotation.
Measurable Feedback Interface: The induced vocabulary is shown to be:
- Compact: Compressing failure-relevant content by $\sim 18\times$ while preserving distinctions (89% of traces retain unique code signatures).
- Human-Faithful: Matching expert failure annotations better than hand-crafted vocabularies under matched conditions ( $\kappa = 0.682$ vs. $0.516$ on TRAIL).
- Adaptive: Taxonomies induced for different domains share only a mean pairwise Jaccard of 0.14, demonstrating specificity to the target system's roles and tools.
Cross-Consumer Improvement: The same induced taxonomy improves performance across three distinct downstream tasks: agent-system search, runtime monitoring, and trajectory selection.

4. Experimental Results

The paper evaluates AdaMAST across three integration settings and multiple benchmarks.

Agent-System Search

Using AdaEvolve as the search backbone, taxonomy-coded diagnoses outperformed free-form LLM reflection on all five benchmarks:

Frontier-CS: $26.0\% \to 32.7\%$ (+6.7 pp)
OlympiadBench: $87.9\% \to 91.9\%$ (+4.0 pp)
MMLU-Pro: $35.0\% \to 42.5\%$ (+7.5 pp)
TheoremQA: $60.0\% \to 65.0\%$ (+5.0 pp)
DROP: $88.2\% \to 91.7\%$ (+3.5 pp)
Mechanism: In the OlympiadBench case study, specific codes (e.g., Coordinator Aggregation Mismatch) directly prompted architectural edits (promoting verification from a binary gate to a score boost), leading to score jumps.

Runtime Monitoring

On SWE-bench Verified Mini, anchoring checkpoints to the induced vocabulary improved resolution rates:

Claude Code: $64.0\%$ (Base) $\to 70.7\%$ (AdaMAST), outperforming free-text Reflexion ( $60\%$ ) and the fixed MAST checklist ( $67.3\%$ ).
SWE-agent: $50\%$ (Base) $\to 70\%$ (AdaMAST), outperforming Reflexion ( $60\%$ ) and MAST ( $68\%$ ).
The induced vocabulary specifically reduced verification-phase failures and converted "flaky" resolutions into reliable ones.

Trajectory Selection

On Terminal-Bench 2.0, AdaMAST-Judge improved Best-of-5 selection accuracy over Pass@1 by 8–15 points and over the fixed MAST vocabulary by 3.4–4.5 points on non-saturated harnesses. Fired codes were shown to discriminate passing from failing trajectories (median 3 codes for pass vs. 4 for fail).

Validation

Human Alignment: On the TRAIL dataset, the induced vocabulary achieved $\kappa = 0.682$ against expert labels, significantly outperforming the hand-crafted TRAIL vocabulary ( $\kappa = 0.516$ ) when using the same annotation panel.
Compression: The taxonomy compressed failure content by $\sim 18\times$ (or $\sim 95\times$ fewer tokens) while maintaining functional equivalence to raw trace pools for downstream prediction tasks.

5. Significance and Claims

The paper claims that adaptive failure taxonomies close the loop between the traces agents produce and the procedures that improve them.

The central argument is that the "missing representation" between raw traces and scalar outcomes is a named, evidence-grounded, system-specific failure vocabulary. By inducing this vocabulary once from the system's own behavior, it becomes a durable artifact that:

Amortizes analysis: The cost of diagnosis is paid once to generate the taxonomy, which is then reused across runs and procedures.
Enables targeted intervention: Unlike free-text critiques, codes map directly to intervention points (system, role, or domain).
Tracks evolution: The vocabulary adapts as the system changes, capturing the "long tail" of role- and domain-specific failures that fixed catalogues cannot anticipate.

The authors emphasize that the gains are not merely due to prompt formatting or the use of structured text, but stem from the induction and reuse of a vocabulary that is faithful to the specific agent system's failure modes. The paper concludes that the cheapest improvement to an agent system may be to "first learn, in its own terms, how it fails."