Research map / Multi-agent systems and games / LLM agents

Automata from Agent Traces: Failure and Next-Step Prediction

NeurIPS 2026 · Multi-agent systems and games › LLM agents · approach: Robust and efficient agent execution · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Extracts compact deterministic finite-state machines from positive-only LLM agent traces via prefix-tree merging by last activity, and uses them for workflow memory, next-step prediction, failure prediction, and early-stopping monitoring.

Problem

LLM agent execution traces are long and unstructured, making safety auditing and runtime monitoring hard; existing methods work per-trace or use only successful traces, missing cross-run structure linking next-step and failure prediction.

Approach

Collapse an entire trace corpus into one small directly-follows FSM by merging prefix-tree states with the same incoming activity (last-activity right congruence), a deterministic, hyperparameter-free construction in linear time; per-state features and FSM-state context then serve several prediction tasks.

Key results

• FSMs have 7-43 states and reach at least 0.997 test replay fitness across datasets, with 15-3,036x fewer states than RPNI.
• FSM cross-entropy anomaly features reach held-out failure-prediction AUROC up to 0.941 (tau2-bench telecom).
• FSM-state context beats Agent Workflow Memory on all eight LLM-judged datasets, e.g. SWE-smith 100% vs 74.7% top-1 and tau2-telecom 45.6% vs 28.5%.

Surprising findings

• Raw replay fitness is uninformative for failure prediction (AUROC about 0.50), while FSM cross-entropy features are informative.
• A single FSM built from all four LLMs' traces achieves 1.000 fitness on each model, suggesting topology is shaped more by the harness than the LLM.

Limitations

• The FSM accepts the directly-follows closure of observed traces, not the agent's generating language; adversarial traces preserving bigram statistics can replay.
• Activity extraction is dataset-specific and requires domain knowledge.
• Cross-model transfer is measured only on three tau2-bench suites; broader transfer is untested.

Experimental setup

Datasets: SWE-smith SWE-agent WebArena AgentNet tau2-bench ATBench OSWorld Who_and_When Mind2Web GUI-Odyssey

Benchmarks: SWE-smith SWE-agent WebArena AgentNet tau2-bench ATBench OSWorld Who_and_When Mind2Web GUI-Odyssey

Metrics: replay fitness state count compression ratio cross-entropy top-1 accuracy AUROC precision recall F1

Baselines: RPNI EDSM Alergia k-Tails HMM Alpha Miner Inductive Miner Heuristic Miner Agent Workflow Memory ProbGuard

Builds on: Agent Workflow Memory RPNI Alergia k-Tails

Closest papers by meaning

• AgentForesight: Online Auditing for Early Failure Prediction in Multi-Agent Systems (NeurIPS 2026 · similarity 0.91)
• AgenTracer: Who Is Inducing Failure in the LLM Agentic Systems? (ICLR 2026 · similarity 0.89)
• Towards a Science of AI Agent Reliability (ICML 2026 · similarity 0.89)
• DoVer: Intervention-Driven Auto Debugging for LLM Multi-Agent Systems (ICLR 2026 · similarity 0.88)
• Why Do Multi-Agent LLM Systems Fail? (NeurIPS 2025 · similarity 0.88)
• Building a Foundational Guardrail for General Agentic Systems via Synthetic Data (ICLR 2026 · similarity 0.88)