Agent Trace Theory: Information Coverage for Evaluating Stateful Tool-Using LLM Agents

Tool-using large language model (LLM) agents complete tasks through extended interactions that modify persistent environments and shape later decisions. Evaluations often reduce these executions to call validity, step-level correctness, or terminal success, obscuring evidence carried across the trajectory. We propose Agent Trace Theory (ATT), an information-theoretic framework that distinguishes agent performance from evaluation coverage by relating full stateful traces to their observable projections. ATT characterizes the verdict-relevant information retained by a trace representation and identifies evidence omitted by call-only, step-local, and outcome-only views. It also formalizes how observations, state changes, backend conditions, ordering, and recovery jointly contribute to an auditable execution record. We operationalize ATT with a TraceState-centered framework that records persistent state, tool-induced transitions, backend conditions, and trajectory-level oracle evidence. Across multiple LLM backbones and prompting strategies, execution studies of state persistence, cross-tool dependency, interaction noise, and backend migration reveal dependency violations, stale-state errors, failed recovery, and backend-specific fragility. A same-trace projection audit shows that retaining state and transition evidence makes these failures more observable than reduced trajectory views, thereby separating diagnostic coverage from agent performance.