Artificial Intelligence · arXiv:2608.23670 v2 · submitted 24 Aug 2026
Automata from Agent Traces: Failure and Next-Step Prediction
The paper says
“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.”
more of the abstract
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.
from the abstract
Pith says
Machine review · deepseek-v4-flash · 28 Aug 2026 · of version 1 of the paper; version 2 is newer · what was read was not recorded · not checked by a person
It can be wrong. Challenge this review or reply to it.
Holds up, with conditions. A solid empirical paper showing the classical directly-follows automaton works well on LLM agent traces; the main results hold up, but the sub-linear regret theorem is invalid as written. This line is wrong
This review says the paper's mathematics is wrong. Pith did not check that against the paper's source.
2 major objections · 5 minor
How often objections from reviews like this one are right: not yet measured
Not checked: figures, code, what the references say.
The paper says, at Appendix A.2, Eq. (9); Sections 3.5 and 4.3
The review did not quote this passage.
Pith says: Objection 1 of 2 · major
Proposition 8's claimed sub-linear O(sqrt(T log|Q|)) regret for the runtime monitor is not supported by the displayed bound. Eq. (9) states Regret(T) <= B*sqrt(2T log|Q|) + T|A|/sqrt(n_q), and for a fixed training corpus n_q is constant in T, so the second term is linear in the horizon.
more of objection 1
The proof sketch gives no mechanism by which this term becomes sub-linear, nor does it control the accumulation of per-step state-estimation error from Proposition 6 over T steps. Since Sections 3.5 and 4.3 invoke this bound as the theoretical justification for early stopping at 32% completion (F1 = 0.904), the proposition should be replaced with a finite-horizon bound that retains the linear term, or the sub-linear claim should be removed, or an online-estimation analysis with n_q growing in T should be supplied. The empirical monitor results may be correct, but this theoretical claim is internally inconsistent as written.
The paper says, at Section 3.2, Section 6, Appendix G.2
The review did not quote this passage.
Pith says: Objection 2 of 2 · major
The dataset-specific activity extraction function phi maps raw messages to the alphabet and is the sole input to the FSM construction; Section 6 correctly states that phi requires minimal but non-zero domain knowledge and that fully automatic phi discovery is future work.
more of objection 2
However, the robustness evidence in Appendix G.2 covers only two datasets (SWE-smith and SWE-agent) and only the entropy-based AUROC metric. It does not verify that the headline numbers in Tables 1, 2, 4, and 14 -- replay fitness, next-step cross-entropy, the main gradient-boosted failure pipeline, and the runtime monitor -- are stable across meaningful extraction granularities on the other ten datasets. Because every downstream claim is conditional on phi, I ask for a sensitivity analysis of the main results to coarser and finer extraction on the remaining datasets, or an explicit restriction of the robustness claim in the abstract and conclusion.
5 minor objections
The paper says, at Section 4.2, Table 2, Figure 2
Pith says: minor objection 1 of 5
The average cross-entropy values reported in Figure 2(b) do not match Table 2 (for example, 'FSM (Mkv)' is shown as 0.72 in the figure but the corresponding Table 2 average is 0.934 bits). Please clarify which dataset subset each panel uses and align the numbers between the figure and the table.
The paper says, at Sections 3.2--3.4
Pith says: minor objection 2 of 5
The phrase 'hyperparameter-free construction' should be scoped to the FSM topology: Step 3 applies a rare-transition rule, Eq. (4) uses the Laplace smoothing alpha, and the downstream prediction and monitoring pipelines have their own hyperparameters (C, tree counts, thresholds). Please state this explicitly to avoid overclaiming.
show 3 more
The paper says, at Section 4.3, Table 41
Pith says: minor objection 3 of 5
The F1 comparison with the flag-everything baseline (0.914 vs. 0.904) is correctly identified as base-rate dominated, but the sentence 'the monitor adds when' would be more informative if accompanied by a threshold-free measure, for example a precision-recall curve or an expected-cost calculation under a simple cost model.
The paper says, at Abstract and Section 4.2
Pith says: minor objection 4 of 5
The abstract says 'twelve public datasets' for the overall evaluation, but the next-step prediction table (Table 2) covers five datasets and the AWM comparison (Table 4) covers eight. Please state explicitly which claims are supported by which subset of the twelve datasets.
The paper says, at Appendix A.2, Corollary 7
Pith says: minor objection 5 of 5
The phrase 'Neyman-Pearson-optimal statistic up to O(1/sqrt(n_q)) error' is informal; please state the underlying family of tests and the precise sense in which the approximation is optimal, or rephrase as an asymptotic consistency result.
What would settle it
Independently re-derive Proposition 8 from Proposition 6, keeping explicit track of how the plug-in estimation error accumulates over T steps. In particular, check whether the T|A|/√n_q term in Eq. 9 can be bounded by O(√T) for fixed training data; if it cannot, the sub-linear regret claim is false. A numerical sanity check on SWE-agent (T ≈ 87, |A| = 24, n_q from training counts) would show whether the linear term dominates the claimed bound at the operating horizon. If the theorem cannot be repaired, the paper should remove the sub-linear claim and the sentence 'matching the empirical F1 = 0.904 early-stopping monitor.'
from the skeptic's reading
How the review went
4 readings by deepseek-v4-flash · 28 Aug 2026
- Reader holds up, with conditions
- Skeptic partly agrees
- Editor wrote the verdict above
- Referee major revision: 2 major objections, 5 minor
Not run on this paper: the simulated authors' defence.
Pith did not check this review's objections against the paper.
The review in full
The review in brief, machine-written
First, the headline: this is a solid empirical paper that shows a classical construction (directly-follows automaton, aka last-activity merge) works very well on LLM agent traces, giving compact states, high replay fitness, and useful signals for next-step and failure prediction. The authors are honest that the construction is classical; their contribution is the application and the unified evaluation across four monitoring tasks. The held-out evaluations are genuine, with multiple baselines including Alergia, RPNI, process miners, and AWM. The cross-model transfer analysis is a nice addition.
The main soft spot is Proposition 8. The claimed O(sqrt(T log|Q|)) regret for the online monitor does not follow from Eq. 9, because the second term T|A|/sqrt(nq) is linear in T when nq is fixed. This is an internal inconsistency in the theoretical justification. The empirical monitor results may still hold, but the theorem as stated is wrong. The paper should either drop the sub-linear claim, give a finite-horizon bound, or analyze an online setting where nq grows.
Other issues are more minor. No code or data are released, which makes exact replication impossible. Several headline tables lack error bars. The FSM-context format was selected on tau2-bench retail, which also appears in the main comparison; the authors address this by showing the held-out average is comparable, which is honest but doesn't eliminate the concern entirely. The activity extraction phi requires dataset-specific domain knowledge, and the robustness tests in Appendix G.2 are reassuring but not definitive.
Overall, the central empirical claim — that a single hyperparameter-free FSM built in milliseconds is compact and informative for LLM agent traces — holds up. I would send this to peer review. It needs a fix to the regret theorem, and ideally code release, but the empirical contribution is real and worth engaging with.
The strongest objection
Proposition 8's stated sub-linear regret for the runtime monitor is not supported by the displayed bound. Section 3.5 promises an O(√(T log|Q|)) regret bound that 'matches the empirical F1 = 0.904 early-stopping monitor,' and Appendix A.2 derives Regret(T) ≤ B√(2T log|Q|) + T|A|/√n_q (Eq. 9), where n_q is the number of per-state training observations. For a fixed training corpus, n_q is constant in T, so the second term is linear in T; the bound is therefore not sub-linear, and the claimed guarantee does not follow. The proof sketch does not explain how the state-estimation error from Proposition 6 (which gives per-step TV error O(1/√n_q)) is prevented from accumulating over T steps. This matters because the monitor is one of the four applications said to be unified by the FSM; if the regret theorem is invalid, the theoretical justification for early stopping on SWE-agent (32% completion) is absent, even though the empirical monitor results may remain correct. The paper should either remove the sub-linear claim, replace it with a finite-horizon bound that tracks the linear term, or provide a genuinely sub-linear analysis with n_q growing appropriately (e.g., via online estimation). This is an internal inconsistency in the manuscript, not a disagreement with prior consensus.
The paper contributes a simple, deterministic construction (last-activity merge of a prefix tree) that yields compact FSMs on twelve datasets, with strong reported replay fitness, next-step cross-entropy, failure AUROC, and monitoring F1. The central empirical claim is plausible and internally mostly coherent; the construction is classical and the evaluations are extensive. The reader's flagged assumption about φ is legitimate but partially mitigated by the granularity robustness experiments (Appendix G.2), which show fitness remains ≥0.999 and AUROC stable across role-only, role-type, role-action, and tool-only alphabets. The more decisive concern is Proposition 8: the claimed sub-linear regret bound is mathematically inconsistent with Eq. 9 as written. Because the runtime monitor is one of the four claimed applications of the unified FSM, a false theorem weakens the theoretical contribution, even though the empirical results are not necessarily affected. This is an addressable issue: the authors can correct the theorem, scope the claim, or replace it with a valid finite-horizon bound. I therefore keep the reader's CONDITIONAL verdict and highlight this specific correctness fix as a necessary condition. The absence of released code and data further supports a conditional rather than unconditional accept, but that is a reproducibility concern rather than a flaw in the argument itself.
The referee's report
If the empirical claims survive scrutiny, the construction is a genuinely useful primitive: it is deterministic, runs in milliseconds, produces interpretable states, and transfers across models and datasets. The paper deserves credit for comparing against strong positive-only baselines such as Alergia, for reporting cross-split stability and cross-model transfer, and for explicitly acknowledging limitations such as Gold's theorem and the role of the hand-crafted extraction function. The main weaknesses are that the theoretical guarantees are mostly elementary consequences of the merge definition, and at least one advertised theorem is incorrect as stated. With the regret bound fixed and robustness to the extraction function more fully documented, the empirical contribution would be solid.
Pith's reading of the paper (a machine's summary, not the authors')
LLM agents act through sequences of messages: they call tools, read outputs, and talk to users. This paper converts each message into a short symbol, for example the name of the tool being called, so a whole run becomes a string of symbols. From all strings in a dataset, the authors build one small state machine in which each state is the last symbol seen. Because most agents use only 6 to 42 distinct actions, the state machine stays small, often between 7 and 43 states, and it can replay almost every held-out trace correctly.
The authors then use this state machine for three jobs. For next-step prediction, they feed the current state into a language model and ask what action comes next; this beats an earlier workflow-memory method on all eight datasets they test. For failure prediction, they count how often each state is visited, how long messages are, and how surprised the state machine is, then train a classifier to separate successful from failed runs, reaching held-out AUROC values up to 0.94. For monitoring, they track whether the agent is cycling between the same few states; a failing coding agent often enters a tight loop, and a simple threshold can stop it around a third of the way through the run.
The paper is careful to say the state machine only captures the directly-follows structure of observed traces, not the true generating behavior, and that the mapping from messages to symbols is hand-crafted per dataset. The novelty is mostly the application and the unified evaluation, while the automaton construction itself is classical.
Core claim. The load-bearing assertion is that 'bounded LLM-agent alphabets make the resulting compact deterministic finite automaton (DFA) both small and statistically informative, and the same FSM unifies workflow memory, next-step prediction, failure prediction, and runtime monitoring' (Section 1). Empirically the paper claims >=0.997 held-out replay fitness on twelve datasets, next-step cross-entropy of 0.73 bits average with FSM-LR-K7, failure-prediction AUROC up to 0.94, and a monitor that triggers early stopping at 32% completion on SWE-agent. If correct, a single hyperparameter-free construction from positive traces gives a structural substrate for agent safety auditing and monitoring.
The premise it rests on. The dataset-specific activity extraction function phi (Section 3.2, Appendix B.1) maps raw messages to a small discrete alphabet, and the paper assumes this mapping preserves behaviorally relevant structure. Section 6 states that phi 'requires minimal but non-zero domain knowledge' and that fully automatic phi discovery is future work. If this hand-crafted mapping is unfaithful, the compactness, replay fitness, and predictive results are artifacts of the extraction rather than of agent behavior. This is structurally distinct from the central claim because it concerns the input representation, not the FSM construction or the prediction pipeline.
Check this review
Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.
How often reviews like this one are right
Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.
How often objections from reviews like this one are right: not yet measured
Reviews by people
This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.
The paper
Abstract
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.
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.
abstract compiled · 2026-09-23
The authors' main claim, as the classifier picked it out 1.00
“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.”
How the main claim is stated: hedged possibility 0.95
What the abstract itself states, as probabilities: claims first 0.08 · states limitation 0.27 · human participants 0.04 · controlled comparison 0.81 · randomized assignment 0.02 · states quantitative result 0.99 · compares with prior results 0.95 · mentions code or data availability 0.04
The abstract, sentence by sentence
This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.
| Sentence | Role | The authors' own work | States the main conclusion | Strength |
|---|---|---|---|---|
| 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. | background 0.93 | 0.08 | 0.03 | asserted 1.00 |
| Existing approaches operate per-trace or success-only, so they miss the cross-run topology that links next-step and failure prediction. | gap 0.99 | 0.05 | 0.03 | asserted 1.00 |
| 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. | method 0.61 | 0.92 | 0.12 | asserted 0.99 |
| 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. | result 1.00 | 0.95 | 0.09 | asserted 1.00 |
| This substrate addresses both prediction goals. | contribution 0.76 | 0.53 | 0.08 | asserted 0.98 |
| For next-step prediction, FSM-state context outperforms Agent Workflow Memory on every ground-truth-matched dataset. | result 1.00 | 0.94 | 0.09 | asserted 1.00 |
| 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. | result 1.00 | 0.94 | 0.11 | asserted 1.00 |
| 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. | interpretation 1.00 | 0.78 | 0.77 | hedged possibility 0.95 |
What kind of paper the classifier reports this is: method or tool 1.00 · evidence from analysis of existing data 0.53
What was examined, and what was not
Sources read
- arXiv listing abstract v1
Not examined
- full text
- figures and tables
- references and citing sentences
- relations to other papers
Levels run
- P abstract
Not run
- S sections
- T body sentences
- C citations
- R cross-paper relations
How the labels were made
Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 6,265 input tokens.
Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON
Figures (16)
Figures are the authors', reproduced from the paper.
Cited by 4 Pith papers
Reviewed papers on Pith that cite this one. The full citation record
- NIOCIS: Typed-Decision Next-Hop Routing with Node-Conditioned Option Spaces for Tool-Use Agents cs.CR · Oct 2026
- Continue or Restart? The Limits of Early Failure Prediction in Coding Agents cs.SE · Oct 2026
- Learning to Act with Task Progress: Distilling Small Agents from Compact Teacher Supervision cs.CL · Oct 2026
- Component Replacement in LLM Agents: A Critical Scoping Review of Task Benefit and Attribution cs.AI · Sep 2026
How the literature uses it
What this paper does with the arXiv papers it cites
What it cites · 3 sentences without a confident label
Uses the method or tool of 1 paper
-
Baselines: RPNI, EDSM, Alergia, k-Tails (automata learning via AALpy [ref] ); HMM; Alpha, Inductive, Heuristic Miners (process mining via PM4Py [ref] ); AWM (workflow extraction).
Process Mining for Python (PM4Py): Bridging the Gap Between Process- and Data Science · Setup · 0.99
Uses data or values from 1 paper
-
We predict task success/failure on nine labeled datasets, including ATBench [ref] , a trajectory-level safety benchmark with balanced safe/unsafe outcomes.
ATBench: A Diverse and Realistic Agent Trajectory Benchmark for Safety Evaluation and Diagnosis · Failure Prediction from FSM Features · 0.92
Compares with 6 papers
-
ProbGuard [ref] learns a DTMC from traces and applies bounded-horizon PCTL reachability for runtime safety filtering; head-to-head on our datasets (Appendix [ref]) it trails our FSM features by mean $+0.176$ AUROC because, without hand-crafted unsafe predicates, its symbolic-state abstraction degrades to per-activity granularity.
ProbGuard: Proactive Runtime Monitoring for LLM Agent Safety via Probabilistic Prediction · Related Work · 0.99
-
We compare LLM-context workflow memory against AWM [ref] only, leaving concurrent success-and-failure memory methods such as ReasoningBank [ref] to future work.
ReasoningBank: Scaling Agent Self-Evolving with Reasoning Memory · Limitations · 0.92
-
Closest is the concurrent PrefixGuard [ref] , which also extracts a DFA from LLM-agent traces for online failure-warning monitors; we treat the same compact automaton as one substrate that additionally drives compression, next-step prediction, and workflow memory, rather than a monitor-only construction.
PrefixGuard: Online Failure Warning and Trace-Grounded Diagnosis for LLM Agents · Related Work · 0.96
Cites as background 2 papers
-
AgentSpec [ref] and ShieldAgent [ref] enforce safety policies; AgentMonitor [ref] predicts task performance from step-level features using flat XGBoost models.
AgentSpec: Customizable Runtime Enforcement for Safe and Reliable LLM Agents · Related Work · 0.97
-
AgentSpec [ref] and ShieldAgent [ref] enforce safety policies; AgentMonitor [ref] predicts task performance from step-level features using flat XGBoost models.
AgentMonitor: A Plug-and-Play Framework for Predictive and Secure Multi-Agent Systems · Related Work · 0.97
Challenges and discussion
Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.
Come back by email
A short list of the week's newly reviewed papers. Nothing is sent until you confirm from your inbox, and every email has a link that stops it. No account.
No comments yet.
Sign in to comment