Automata from Agent Traces: Failure and Next-Step Prediction

• URL: http://arxiv.org/abs/2608.23670v1
• Date: Mon, 24 Aug 2026 17:58:01 GMT
• Title: Automata from Agent Traces: Failure and Next-Step Prediction
• Abstract summary: We collapse an entire trace corpus into a single, compact finite-state machine (FSM) that serves as a structural substrate for the behavior of LLM agents.<n>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.
• Score: 1.16693435589939
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Beyond Suspicious Steps: Ontological Trust in Long-Horizon Agents [13.208673657449175]
  We introduce ontological trust, a task-conditioned property of trajectory prefixes, and instantiate it as RGE.<n>RGE decomposes trust along Role, Goal, and Evidence.<n>We construct a cross-domain trajectory corpus from OSWorld, FinanceBench, and EICU-AC.
  arXiv  Detail & Related papers  (2026-08-18T12:44:43Z)
• From Sequence to Structure: Relational Uncertainty Propagation for LLM Agents [75.69180947909148]
  We propose a trajectory-level UQ framework for large language model (LLM) agents.<n>RuPA represents an execution history as a directed trajectory graph in which reasoning states, tool interactions, and environment feedback are nodes connected by temporal and semantic dependency edges.<n>We evaluate RUPA on representative agent benchmarks, including $$-2, Terminal-Bench-2, and GAIA, using 6 open-source LLMs spanning multiple model families.
  arXiv  Detail & Related papers  (2026-08-17T01:40:14Z)
• TELLER: Non-intrusive Cross-Layer Root-Cause Analysis for LLM Inference [47.62941623025392]
  We present TELLER, a non-intrusive and Log-aware LLM inference Root-cause analysis framework.<n>TELLER collects NVTX/CUPTI traces and service logs without modifying model binaries.<n>It reconstructs per-request call-chain trees and aligns log lines with corresponding execution steps.<n>On top of these representations, TELLER combines numeric candidate localization with a multimodal root-cause model.
  arXiv  Detail & Related papers  (2026-08-03T09:39:11Z)
• PhyAgentOS: A Self-Evolving Operating System for Embodied Agents with Decoupled Cognitive Planning and Physical Execution [49.776611937968]
  We present PhyAgentOS, a foundation delivering scheduling, verification, memory, benchmarking, and safety as system-level services.<n>Its Session-Centered treats a session, not an action, as the minimum unit of scheduling, compatibility, supervised execution, evidence collection, and acceptance.<n>SessionVerifier distinguishes execution termination from semantic task completion via evidence-grounded verdicts of success, failure, or replan.<n> Benchmarking reuses the deployment session and verification path, so results trace to real execution.
  arXiv  Detail & Related papers  (2026-07-18T04:46:53Z)
• Compaction as Epistemic Failure: How Agentic LLM Tools Fabricate Confirmed Results from Killed Processes [0.0]
  This paper documents a failure mode in Claude Code where partial standard output from timed-out commands (exit code 143) is recorded in compaction summaries as confirmed results.<n>The underlying mechanism is a conflation of observation and persistence, where information that appeared in the terminal is treated as equivalent to information written to durable storage.
  arXiv  Detail & Related papers  (2026-07-11T07:45:13Z)
• Monitoring Data-aware Temporal Properties (Extended Version) [56.386411908764494]
  We consider anticipatory monitoring of linear-time properties enriched with an arbitrary SMT theory over finite traces.<n>Anticipatory monitoring in this setting is highly challenging, as the monitoring state depends on both the trace prefix seen so far and all its possible finite continuations.<n>We present and formally prove the correctness of a novel foundational framework for monitoring properties in an expressive fragment offMT.
  arXiv  Detail & Related papers  (2026-05-14T10:23:11Z)
• AgentForesight: Online Auditing for Early Failure Prediction in Multi-Agent Systems [30.172832661173928]
  LLM-based multi-agent systems are increasingly deployed on long-horizon tasks.<n>A single decisive error is often accepted by downstream agents and cascades into trajectory-level failure.<n>We introduce AgentForesight, a framework that reframes this problem as online auditing.
  arXiv  Detail & Related papers  (2026-05-09T05:55:19Z)
• Detecting Object Tracking Failure via Sequential Hypothesis Testing [80.7891291021747]
  Real-time online object tracking in videos constitutes a core task in computer vision.<n>We propose interpreting object tracking as a sequential hypothesis test, wherein evidence for or against tracking failures is gradually accumulated over time.<n>We propose both supervised and unsupervised variants by leveraging either ground-truth or solely internal tracking information.
  arXiv  Detail & Related papers  (2026-02-13T14:57:15Z)
• Trajectory Guard -- A Lightweight, Sequence-Aware Model for Real-Time Anomaly Detection in Agentic AI [0.0]
  Trajectory Guard is a Siamese Recurrent Autoencoder with a hybrid loss function that jointly learns task-trajectory alignment via contrastive learning and sequential validity via reconstruction.<n>At 32 ms latency, our approach runs 17$-27times$ faster than LLM Judge baselines, enabling real-time safety verification in production deployments.
  arXiv  Detail & Related papers  (2026-01-02T00:27:11Z)
• Metacognitive Self-Correction for Multi-Agent System via Prototype-Guided Next-Execution Reconstruction [58.51530390018909]
  Large Language Model based multi-agent systems excel at collaborative problem solving but remain brittle to cascading errors.<n>We present MASC, a metacognitive framework that endows MAS with real-time, unsupervised, step-level error detection and self-correction.
  arXiv  Detail & Related papers  (2025-10-16T05:35:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.