# TriCEGAR: A Trace-Driven Abstraction Mechanism for Agentic AI

arXiv: https://arxiv.org/abs/2601.22997 · HTML: https://mlsanity.com/paper/2601.22997/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Agent threats, guardrails and governance, one of 16 directions in LLM agents and tool use.
- Builds on 5 of its 24 references that are in the map.
- First posted on arXiv 30 Jan 2026.

## Placed in

- LLM agents and tool use / [Agent threats, guardrails and governance](https://mlsanity.com/agents/agent-threats-guardrails-and-governance/)

## Builds on (most cited first, 5 of 5)

- [The Rise and Potential of Large Language Model Based Agents: A Survey](https://mlsanity.com/paper/2309.07864/) (2023)
- [RepairAgent: An Autonomous, LLM-Based Agent for Program Repair](https://mlsanity.com/paper/2403.17134/) (2024)
- [TradingAgents: Multi-Agents LLM Financial Trading Framework](https://mlsanity.com/paper/2412.20138/) (2024)
- [A storm is Coming: A Modern Probabilistic Model Checker](https://mlsanity.com/paper/1702.04311/) (2017)
- [AgentGuard: Runtime Verification of AI Agents](https://mlsanity.com/paper/2509.23864/) (2025)

## Built on by (most cited first, 2 of 2)

- [Measuring the Unmeasurable: Markov Chain Reliability for LLM Agents](https://mlsanity.com/paper/2604.24579/) (2026)
- [ATLAS: Discovering Agent Strategies through LLM-Guided Abstraction and Automata Learning](https://mlsanity.com/paper/2608.14352/) (2026)

## Abstract (arXiv)

Agentic AI systems act through tools and evolve their behavior over long, stochastic interaction traces. This setting complicates assurance, because behavior depends on nondeterministic environments and probabilistic model outputs. Prior work introduced runtime verification for agentic AI via Dynamic Probabilistic Assurance (DPA), learning an MDP online and model checking quantitative properties. A key limitation is that developers must manually define the state abstraction, which couples verification to application-specific heuristics and increases adoption friction. This paper proposes TriCEGAR, a trace-driven abstraction mechanism that automates state construction from execution logs and supports online construction of an agent behavioral MDP. TriCEGAR represents abstractions as predicate trees learned from traces and refined using counterexamples. We describe a framework-native implementation that (i) captures typed agent lifecycle events, (ii) builds abstractions from traces, (iii) constructs an MDP, and (iv) performs probabilistic model checking to compute bounds such as Pmax(success) and Pmin(failure). We also show how run likelihoods enable anomaly detection as a guardrailing signal.