PaperlayerView exact revision on arXiv

Source-linked AI summary

Automata from Agent Traces: Failure and Next-Step Prediction

Seonglae Cho, Franklin Cardenoso Fernandez, Umar Mohammed, Zekun Wu, Kleyton Da Costa, Ilham Wicaksono, Adriano Koshiyama

arXiv:2608.23670v1cs.AIcs.CLcs.LG

TL;DR

LLM-agent traces are difficult to audit and monitor because existing methods often analyze individual runs or success-only data rather than shared cross-run structure. The paper extracts one compact FSM from a trace corpus and uses its states for workflow memory, next-step prediction, failure prediction, and runtime monitoring, with strong results across twelve public datasets.

  • Problem

    Existing agent-trace approaches operate per trace or use success filters, leaving shared behavioral topology insufficiently represented for safety auditing and runtime monitoring.

  • Method

    The paper deterministically extracts activities from heterogeneous traces and constructs a compact FSM from positive examples using bounded activity alphabets.

  • Results

    FSM-state context outperforms Agent Workflow Memory on all 8/8 datasets, while per-state features reach held-out AUROC up to 0.94 and support early stopping at 32% completion.

  • Takeaways & Limitations

    A single compact FSM serves as a structural substrate for workflow memory, next-step prediction, failure prediction, and runtime monitoring.

  • Takeaways & Limitations

    The activity-extraction function is dataset-specific, broader cross-architecture and cross-domain transfer remains future work, and only one concurrent success-and-failure memory method is compared.

Abstract

from arXiv · show

LLM-based agents execute multi-step tasks, but their behavioral structure remains opaque: long unstructured traces resist the safety auditing and runtime monitoring that deployment requires. Existing approaches operate per-trace or success-only, so they miss the cross-run topology that links next-step and failure prediction. To recover that shared structure, we collapse an entire trace corpus into a single, compact finite-state machine (FSM) that serves as a structural substrate for the otherwise unpredictable behavior of LLM agents. Across twelve public datasets, the FSMs are compact (7-43 states), replay held-out data at >=0.997 fitness with near-identical topology across splits, and build in milliseconds. This substrate addresses both prediction goals. For next-step prediction, FSM-state context outperforms Agent Workflow Memory on every ground-truth-matched dataset. For failure prediction, per-state behavioral features reach held-out AUROC up to 0.94, and an online monitor ranks failing runs above passing ones from a partial trace, triggering early stopping well before completion. Behavioral topology thus appears shaped more by the deployment harness than by the LLM, providing a model-agnostic structural primitive for safety auditing and runtime monitoring.

1. Introduction

The paper recovers a compact FSM from agent-trace corpora to expose shared behavioral structure for prediction, auditing, and monitoring. Across datasets, this substrate supports strong next-step and failure prediction while remaining compact and fast to construct.

  • Motivation: Current trace-level approaches require task descriptions, manual specifications, or success filters, limiting shared behavioral analysis across runs.The paper motivates corpus-level structural recovery for safety auditing, debugging, and production drift monitoring.
  • Approach: A deterministic, hyperparameter-free construction recovers compact FSMs from positive-only traces with bounded activity alphabets.The resulting topology appears shaped more by the deployment system than by the LLM, including perfect fitness across four chat models on tau2-bench.
  • Next-step prediction: FSM-state context outperforms Agent Workflow Memory on all 8/8 evaluated datasets and improves next-step cross-entropy by 0.155 bits (21%) over identical methods without state.The comparison covers ground-truth-matched datasets for workflow memory and state-conditioned next-step prediction.
  • Failure prediction: Per-state features reach held-out AUROC up to 0.94, improve MLP, GRU, and Transformer baselines on 20 of 21 pairs, and support early stopping at 32% completion.A prefix monitor ranks failing SWE-agent runs above passing ones at the 25% checkpoint with rank-AUROC 0.66 versus 0.5 for flag-everything.
  • Compression: 15–3,036× fewer states than RPNI are achieved at ≥0.997 fitness through deterministic construction.The approach preserves high replay fitness while substantially reducing automaton size.
  • Unified contribution: The same FSM unifies workflow memory, next-step prediction, failure prediction, and runtime monitoring as one compact structural primitive.This shared substrate replaces separate learned pipelines with a model-agnostic representation for behavioral analysis and safety use cases.

2. Related Work

Prior work covers safety monitoring, workflow memory, process mining, and grammatical inference, but existing methods generally lack a compact state abstraction that unifies these functions. The paper positions its bottom-up trace-derived FSM as that structural alternative.

  • Agent safety and monitoring: Agent safety methods enforce policies, predict performance, or filter traces, while ProbGuard’s symbolic abstraction trails the FSM features by mean +0.176 AUROC.The cited comparison attributes ProbGuard’s degradation to symbolic states collapsing to per-activity granularity without hand-crafted unsafe predicates.
  • Behavioral abstractions: Workflow-memory methods learn linear patterns from successful or failed traces, but do not produce structural models with state abstraction.The related-work discussion contrasts AWM, Reflexion, ETO, and ReasoningBank with the paper’s FSM representation.
  • Behavioral abstractions: AFlow searches workflows, MetaAgent builds FSMs from task descriptions, and StateFlow relies on manual specification, whereas this method recovers FSMs bottom-up from raw traces.The distinction is the source of structure: observed execution traces rather than task descriptions or manual designs.
  • Process mining: Standard process miners can produce flower models with precision 0.00–0.80 on agent traces, while this automaton determinizes the directly-follows graph through a last-activity right congruence.The paper frames its construction as a deterministic structural quotient rather than a conventional Petri-net discovery output.
  • Grammatical inference: Positive-only automata learners face identification limits or require hyperparameters, while this approach yields compact interpretable FSMs with 7–43 states from bounded activity alphabets of 6–42 symbols.RPNI, EDSM, and L* require unavailable negative examples or oracles; k-Tails and Alergia produce larger or less compact alternatives.

3. Method

The method deterministically extracts activities from heterogeneous traces, builds a compact deterministic directly-follows FSM through prefix insertion, last-activity merging, and rare-transition filtering, and uses its states for prediction and monitoring. The construction preserves training fitness before filtering, yields 7–43 states across twelve datasets, and supports compact probability estimation and online monitoring.

  • Activity Extraction: Activity extraction maps tool calls, action tags, code commands, or unmatched messages to deterministic symbols in a finite alphabet.The priority order is tool-call function, action label, first command token mapped to a semantic category, then role:content type.
  • FSM Construction: The pipeline inserts activity sequences into a prefix tree, merges states by incoming last activity, and filters singleton transitions unless they are the only continuation.Filtering removes one-off digressions, never states, and is the only construction step that can reduce fitness.
  • Correctness: Training fitness is preserved through last-activity merging, while rare-transition filtering is the sole potential source of fitness loss.Every prefix-tree edge survives the quotient before filtering.
  • FSM Construction: |Q| = |A|+1 states make the extracted FSM deterministic, with transitions given by retained directly-follows pairs and output uniquely determined by the corpus.The state count and transition set are invariant to trace order and sampling for a fixed corpus.
  • Scope: The FSM recovers the directly-follows automaton of observed traces rather than the unidentifiable generating automaton.Positive examples alone cannot identify the target language in the limit.
  • Efficiency and Prediction: Across twelve datasets, FSMs contain 7–43 states, and the total construction runtime is linear in corpus size for bounded alphabets.All twelve datasets complete in under one second on a single CPU core; state compactness supports probability estimation and online monitoring.

4. Results

Across twelve datasets, the compact FSM achieves high-fitness replay and stable construction while improving next-step prediction, workflow-memory context, and failure monitoring. Its behavioral features support accurate held-out failure prediction and early intervention from partial traces.

  • FSM extraction: 7–43 states deliver 15–3,036× compression over RPNI at ≥0.997 test fitness across datasets.The construction reaches ≥0.99 fitness with 5–15% of training data and is deterministic and hyperparameter-free.
  • Next-step prediction: 0.93 bits average cross-entropy is achieved by the FSM order-1 Markov predictor, a 62% reduction from the Unigram baseline.FSM-state conditioning accounts for 83–99% of the total cross-entropy improvement from Uniform to the best method on each dataset.
  • Next-step prediction: 0.155 bits (21%) mean improvement comes from FSM-state conditioning over identical raw-context methods, with gains positive on all six datasets.The controlled ablation reports FSM-AD: 0.580 versus Pure-AD: 0.735 CE; combining FSM state with learned models achieves 0.73 bits average CE.
  • Workflow-memory context: FSM context beats Agent Workflow Memory on all eight datasets, with gains ranging from +0.8pp to +25.3pp in LLM-judged top-1 evaluation.The minimal context uses next-action probabilities and top-15 multi-step continuations from the current state; six of eight gaps are statistically significant at p < 10−8.
  • Runtime and transfer: 1–110 ms construction time and 0.003–0.015 ms replay time enable real-time monitoring, with 328–10,611× construction speedups over RPNI.The FSM also transfers across models: a single FSM built from four LLMs’ traces achieves 1.000 fitness on each model individually.

5. Discussion

The discussion presents the FSM as a compact, structural representation that supports reliable per-state prediction and monitoring, while noting boundaries to its invariance and compactness.

  • 5. Discussion: Compactness makes per-state estimation reliable by pooling enough observations within each state.The authors contrast their small state sets with much larger RPNI automata.
  • 5. Discussion: FSM states preserve activity ordering, enabling structural features to outperform length-only prediction and support early stopping.Length reaches AUROC 0.659 on SWE-agent, versus 0.790 for structural features.
  • 5. Discussion: The same per-state features lift MLP, GRU, and Transformer baselines on 20 of 21 matched dataset-architecture pairs.This positions the FSM as complementary to learned sequence models.
  • 5. Discussion: The topology is invariant across model choice and usually robust to extraction granularity, matching or exceeding role-only AUROC on 10 of 12 datasets.Role-only extraction is an exception when its alphabet degenerates to at most three symbols.
  • 5. Discussion: For much larger action spaces or weaker conditional structure, FSM compactness and per-state observation density may degrade.The construction still applies, but downstream gains may weaken.

6. Limitations

The FSM models the directly-follows closure of observed traces rather than the agent’s full generating language, and broader automation and transfer remain open boundaries.

  • 6. Limitations: The FSM accepts the directly-follows closure of observed traces, so adversarial traces preserving activity bigrams may still replay.The paper explicitly distinguishes this acceptor from the agent’s generating language.
  • 6. Limitations: Activity extraction is dataset-specific, requires non-zero domain knowledge, and fully automatic discovery is left for future work.The method is reported as robust across tested granularities, but extraction is not fully automated.
  • 6. Limitations: Broader cross-architecture and cross-domain transfer remains future work beyond the measured 0.786 mean cross-AUROC on three tau2-bench suites.The reported transfer evaluation is limited to those suites.

7. Conclusion

The conclusion presents a single compact FSM extracted from positive-only agent traces as a shared substrate for workflow memory, prediction, and monitoring.

  • 7. Conclusion: Compact FSMs of 7–43 states support workflow memory, next-step prediction, failure prediction, and early-stopping monitoring.The method is presented as replacing four bespoke learned pipelines with one structural primitive.
  • 7. Conclusion: The extraction algorithm maps traces into activity sequences, builds a prefix tree, merges states by incoming activity, and aggregates transitions.The resulting FSM is defined as M = (Q, A, δ, q0, Q).
  • 7. Conclusion: Rare-transition filtering removes transitions observed exactly once unless they are the source state’s only continuation.This filtering step can reduce replay fitness but never removes states.
  • 7. Conclusion: At role-level granularity, the tau2-bench airline FSM has 6 states and 5 activities, while tool-level decomposition has 18 states and 17 activities.The tool-level model exposes tool-call and conversational loops.

A.2. Proofs

The proofs establish that last-activity quotienting yields a deterministic replaying FSM, while transition estimation and online monitoring have consistency and regret guarantees.

  • A.2. Proofs: Before filtering, every training trace is accepted by the merged FSM because each trie path survives quotienting.Filtering is the only mechanism that can cause replay failure.
  • A.2. Proofs: Last-activity merging maps each trie state to its incoming activity class, producing exactly |A| + 1 classes.The root is assigned the init class.
  • A.2. Proofs: Each quotient transition exists when a corresponding training bigram appears, and each state-activity pair has at most one successor.The successor class is determined by the input activity, establishing determinism.
  • A.2. Proofs: The extracted FSM is unique because its class map and retained edge set depend only on the training transition multiset.It is a compact directly-follows acceptor, not the minimal DFA of the finite prefix language.
  • A.2. Proofs: Transition estimates converge almost surely to the true state-conditioned distributions as per-state visit counts grow.The result follows from concentration arguments applied to multinomial transition counts.
  • A.2. Proofs: The success-versus-failure surprise difference is a Neyman–Pearson-optimal statistic up to O(1/√nq) error.The statistic uses cross-entropy from a success-only transition model.
  • A.2. Proofs: The online monitor has sub-linear regret in trace length, with compact |Q| reducing the logarithmic complexity term.Empirically, the monitor reaches F1 = 0.904 and flags failures at 32% completion on SWE-agent.
  • A.2. Proofs: Building the prefix tree costs O(N T̄) time and space, followed by linear-pass merging and rare-transition filtering.The merge creates |A| + 1 classes by aggregating transition counts.

B.1. Dataset Details

The evaluation spans twelve datasets across diverse agent domains, with compact activity alphabets and outcome labels available for most datasets. Multi-model tau2-bench data enables testing whether FSM structure transfers across LLMs.

  • Multi-model evaluation: tau2-bench contains airline, retail, and telecom suites with 17, 18, and 42 activities, respectively, across four LLMs.The four models are GPT-4.1, Claude 3.7 Sonnet, GPT-4.1-mini, and o4-mini.
  • Dataset scope: WebArena contributes 8,337 labeled traces with 24 role-prefixed activity symbols, while AgentNet contributes 5,000 desktop-agent traces with 24 activities.WebArena has 13.4% success, and AgentNet has 36.4% success.
  • Multi-model evaluation: A single FSM built from all four tau2-bench models achieves 1.000 replay fitness on each model, indicating model-invariant topology with differing transition probabilities.The models traverse the same tool-call sequences while differing in transition probabilities.
  • Multi-model evaluation: Cross-model failure-prediction transfer remains above chance, with mean cross-AUROC at least 0.68 on every tau2-bench suite.The strongest reported pair is GPT-4.1→o4-mini, reaching AUROC 0.950 on telecom.

D.2. Extended Baseline Results

Extended comparisons show that the FSM combines compactness, rapid convergence, structural precision, interpretability, and practical runtime performance across agent datasets. It also exposes distinct success and failure workflows and supports failure prediction through per-state features.

  • Baseline comparisons: Small-alphabet datasets stabilize at 8–10 states, while RPNI produces 476–11,631 states with fitness at most 0.984.The comparison demonstrates severe prefix-tree overfitting without effective structural merging.
  • Compression: GUI-Odyssey and AgentNet reach compression ratios of 3,036× and 2,500×, respectively.Large training sets drive the highest compression ratios in these datasets.
  • Baseline comparisons: RPNI reaches 62,495 states and 0.743 fitness on AgentNet, whereas WebArena’s short traces leave RPNI at 382 states and 15× the FSM size.WebArena is an exception because its traces average roughly eight steps.
  • Runtime: FSM construction completes in under one second for every dataset, while RPNI takes up to 120 seconds and per-trace replay takes under 0.015 ms.Construction scales linearly with corpus size, supporting real-time monitoring.
  • Failure structure: On SWE-agent, the success FSM uses 9 of 25 states, whereas the failure FSM spans all 25 states with 60 transitions and transition Jaccard similarity 0.206.Failure-only states correspond to rare tool-output parsing variants.
  • Failure structure: A cycle rate above 0.885 achieves 95.6% precision as a simple SWE-agent monitoring rule without a learned model.This rule uses the structural differences between successful and failed workflows.

E.5. Failure Prediction Feature Analysis

Failure prediction benefits from FSM-conditioned behavioral features that identify localized errors, terminal-state access, verbosity, and temporal disorder. These features improve neural baselines broadly, while structural rejection and convergence analyses characterize the FSM’s behavior and limits.

  • Predictive features: Top failure signals include not reaching terminal states, elevated state-specific error rates, verbose responses, and high late-half temporal entropy.Examples include SWE-agent submit-state weight +0.29, SWE-smith editor error-rate weight −0.20, and lateHalfEntropy weight −0.19.
  • Interpretability: Per-state decomposition exposes behavioral modes that aggregate trace-level features cannot identify, with per-state error rates and temporal entropy among the top five feature families across datasets.The patterns recur across coding and API-calling domains.
  • Predictive features: FSM-conditioned features improve MLP and GRU AUROC on all datasets and Transformer AUROC on 6 of 7 datasets.Largest gains include +9.1pp for GRU on tau2-bench retail and +4.2pp for MLP on AgentNet.
  • Adversarial robustness: The FSM rejects 90–100% of insertions and adjacent swaps, while deletion rejection on tau2-bench is weaker at 61–80%.Deletion can leave shorter traces as valid prefixes.
  • Convergence: Fitness reaches 0.99 using 5–15% of training data, and train−test gaps remain within ±0.003 across training fractions.SWE-agent requires 15% to capture rare commands.

F.4. Feature Redundancy Analysis

Feature redundancy analysis finds that many structural predictors collapse into a small number of independent behavioral dimensions. Removing redundant features preserves most of the failure-prediction signal, while partial traces retain substantial predictive information.

  • Redundancy structure: Fourteen structural features collapse into 5–8 non-redundant clusters using an absolute correlation threshold of |r| > 0.8.The largest cluster contains trace length and closely related correlates.
  • Reduced feature sets: After retaining one feature per cluster, combined AUROC reaches 0.655 on SWE-smith and 0.713 on SWE-agent.On SWE-agent, the reduced subset retains 90% of the full-feature AUROC.
  • Early signal: At 50% trace completion, SWE-agent FSM features reach 0.722 cross-validation AUROC versus 0.784 for full traces.The result indicates that much of the predictive signal emerges before execution finishes.
  • Early signal: SWE-agent FSM features exceed aggregate baselines by +0.026 to +0.257 beyond the 25% completion stage, unlike the simpler SWE-smith FSM.The FSM advantage scales with behavioral complexity.

G.2. Activity Granularity Robustness

The FSM remains robust across activity-extraction granularities and supports next-step and failure prediction with compact, state-aware representations. Its advantages arise from preserving behavioral structure while aggregating observations into a small number of states.

  • Activity Granularity Robustness: ≥0.999 replay fitness holds across all tested extraction granularities and datasets, with failure-prediction AUROC varying by less than 0.03.The tested levels range from role-only alphabets of 2–4 symbols to tool-only extraction.
  • Activity Granularity Robustness: 0.006 ms per trace is sufficient for single-feature FSM monitoring, with SWE-agent cycle-rate precision reaching 95.6%.The rule trades recall for a near-zero false-alarm rate.
  • Activity Granularity Robustness: FSM features outperform probabilistic baselines by +0.19 AUROC on SWE-agent, while transition cross-entropy remains competitive on SWE-smith at 0.719 versus 0.718.Per-state features capture message lengths, error rates, and temporal patterns that aggregate transition statistics do not.
  • Activity Granularity Robustness: +0.176 mean AUROC separates FSM features from ProbGuard across shared datasets.ProbGuard’s symbolic abstraction degrades to per-activity granularity without hand-crafted unsafe predicates, while FSM features retain per-state behavioral information.
  • Next-Step Prediction: The FSM achieves higher top-1 next-step accuracy than AWM on every listed dataset, with gaps from +0.1pp to +65.5pp.Order-1 FSM conditioning captures 83–99% of total cross-method cross-entropy improvement, while higher-order models capture remaining dependencies within states.
  • Next-Step Prediction: +0.155 bits is the average benefit of FSM state conditioning over raw context, reaching +0.36 bits on Mind2Web.The advantage is smallest on SWE-agent, where simple sequential structure makes state nearly redundant with the last activity.

H.1. Cross-Dataset Transfer

Cross-dataset analyses show that FSM-derived signals transfer better than raw trace statistics and expose structural differences between domains, success and failure paths, and perturbations. Early, state-specific signatures support lightweight monitoring, but rule-based monitoring depends on sufficient structural diversity.

  • Cross-Dataset Transfer: Higher transfer AUROC for FSM features than raw features occurs on most cross-dataset pairs, with the largest improvements involving SWE-agent.The pattern is consistent with domain-invariant failure signatures rather than dataset-specific surface statistics.
  • Cross-Dataset Transfer: 10% of training data reaches 95% of final failure-prediction performance on 3 of 4 datasets.The FSM feature space contains only 31–49 features, enabling deployment with as few as 16–160 labeled traces.
  • Failure Signatures: 0.790 AUROC comes from structural features alone on SWE-agent, while adding length changes full-model AUROC by less than 0.001.This supports structural rather than length-based predictive signal.
  • Failure Progression: 97% of SWE-agent failures are sudden, and the first success–failure distribution divergence appears at 8.7% of trace length.SWE-smith failures are also entirely sudden, while SWE-agent has recovery states that return to successful trajectories within two steps.
  • Counterfactual Path Analysis: 5.4× more unique paths occur in SWE-agent failures than successes, with 1,496 versus 275 paths and only 41 shared paths.The user:text state is a primary decision point, where successful traces more often transition to submit and failed traces loop to edit.
  • State Importance Analysis: State importance is not proportional to visit frequency: removing SWE-smith’s 1.9%-visited system:text state causes complete fitness collapse, while removing 47.2%-visited tool:text drops fitness by 0.937.On SWE-agent, user:text is the critical bottleneck with a 0.999 fitness drop when removed.
  • Runtime Monitoring: 0.747 composite anomaly AUROC is achieved on SWE-agent, while suffix monitoring with k=10 transitions reaches 0.825 AUROC.A fixed-size sliding window supports real-time deployment, and k=3 still achieves 0.746 AUROC.
  • Runtime Monitoring: 0.904 monitor F1 is achieved on SWE-agent without a trained model, but small-alphabet FSMs under-discriminate and over-trigger.At threshold 0.957, precision is 100% with 11.3% failure capture; at threshold 0.750, capture is 85.2% with 86.4% precision.
Loading 2608.23670v1…