[Paper] TriCEGAR: A Trace-Driven Abstraction Mechanism for Agentic AI

Source: arXiv - 2601.22997v1

Overview

The paper introduces TriCEGAR, a trace‑driven abstraction technique that automatically builds a compact, verifiable model of an agentic AI system from its execution logs. By turning raw lifecycle events into a probabilistic state machine, TriCEGAR enables continuous assurance (e.g., “what’s the chance the agent will succeed?”) without requiring developers to hand‑craft abstractions—a major hurdle in prior runtime‑verification approaches.

Key Contributions

• Automated abstraction: Generates predicate‑tree state abstractions directly from agent execution traces, eliminating manual, domain‑specific state design.
• Online MDP construction: Incrementally builds a Markov Decision Process (MDP) that captures the agent’s stochastic behavior as new logs arrive.
• Counterexample‑guided refinement (CEGAR): Uses failed model‑checking queries to automatically refine the abstraction, ensuring the MDP stays faithful to observed behavior.
• Framework‑native integration: Provides a plug‑in that (1) captures typed lifecycle events, (2) builds abstractions, (3) synthesizes the MDP, and (4) runs probabilistic model checking for quantitative guarantees (e.g., Pmax(success), Pmin(failure)).
• Anomaly detection via run likelihoods: Computes the likelihood of observed traces under the learned MDP, flagging low‑probability executions as potential safety or performance anomalies.

Methodology

1. Trace Collection – The system instruments the agent’s runtime to emit typed events (e.g., “tool‑selected”, “observation received”, “action executed”). These events are stored as ordered logs.
2. Predicate‑Tree Learning – From the logs, TriCEGAR extracts Boolean predicates over event attributes (e.g., tool == "search" ∧ confidence > 0.8). It organizes them into a decision‑tree‑like structure where each leaf corresponds to an abstract state.
3. MDP Synthesis – As traces flow in, transitions between abstract states are counted, yielding empirical probabilities for the MDP’s edges. The MDP is updated online, preserving a lightweight representation.
4. Probabilistic Model Checking – Using tools like PRISM, the MDP is queried for quantitative properties (e.g., “maximum probability of reaching a success state within 10 steps”).
5. CEGAR Loop – If a model‑checking query fails (the bound is too loose), the system extracts a counterexample trace that violates the property. This trace is fed back to the predicate learner, which splits or refines the relevant leaf node, producing a finer abstraction. The loop repeats until the property is satisfied within a user‑defined tolerance.
6. Anomaly Guardrail – The likelihood of each new trace under the current MDP is computed; traces below a threshold trigger alerts, enabling runtime monitoring for unexpected behavior.

Results & Findings

• Accuracy vs. Manual Abstractions – On three benchmark agentic AI tasks (web‑search assistant, code‑generation bot, and autonomous data‑pipeline orchestrator), TriCEGAR achieved within 5 % of the probability bounds obtained with hand‑crafted abstractions, while requiring zero manual state engineering.
• Scalability – The online abstraction and MDP update overhead stayed under 30 ms per 1 k‑event batch, making it suitable for real‑time monitoring in production services.
• Refinement Efficiency – The CEGAR loop converged in an average of 3–4 iterations per property, automatically tightening abstractions only where needed.
• Anomaly Detection – Low‑likelihood traces (bottom 1 % of the likelihood distribution) corresponded to injected fault scenarios (e.g., tool failure, malformed responses) with a true‑positive rate of 92 % and a false‑positive rate of 4 %.

Practical Implications

• Reduced DevOps friction – Teams can plug TriCEGAR into existing agent pipelines and obtain quantitative safety/quality guarantees without writing custom abstraction code.
• Continuous assurance – Because the MDP is updated on‑the‑fly, developers get live probability estimates (e.g., “the chance of completing the user request in under 5 steps is 0.87”) that can drive adaptive throttling or fallback strategies.
• Safety guardrails – The likelihood‑based anomaly detector can be wired into alerting systems (PagerDuty, Slack) or automated mitigation (resetting the agent, switching to a sandboxed mode).
• Regulatory compliance – Quantitative bounds on success/failure probabilities help satisfy emerging AI assurance standards (e.g., EU AI Act, ISO/IEC 42001).
• Tooling ecosystem – The approach is compatible with popular agent frameworks (LangChain, AutoGPT) and model‑checking back‑ends (PRISM, Storm), enabling easy integration into CI/CD pipelines.

Limitations & Future Work

• Trace quality dependence – The abstraction quality hinges on the richness of logged events; sparse or noisy logs can lead to overly coarse states and imprecise probability bounds.
• State explosion risk – In highly heterogeneous environments, the predicate tree may grow large; the current pruning heuristics are simple and could be refined.
• Limited to discrete actions – The current MDP formulation assumes a finite action set; extending to continuous control or hybrid systems (e.g., robotics) is left for future research.
• Scalability to massive fleets – While per‑agent overhead is low, aggregating models across thousands of agents raises storage and computation challenges that the authors plan to address with hierarchical or federated abstraction techniques.

TriCEGAR demonstrates that automated, trace‑driven abstractions can bring rigorous probabilistic assurance into the fast‑moving world of agentic AI, opening a path toward safer, more trustworthy autonomous software.

Authors

• Roham Koohestani
• Ateş Görpelioğlu
• Egor Klimov
• Burcu Kulahcioglu Ozkan
• Maliheh Izadi

Paper Information

• arXiv ID: 2601.22997v1
• Categories: cs.AI, cs.SE
• Published: January 30, 2026
• PDF: Download PDF