# No Certificate, No Execution: Certified Traces as a Foundation for Trustworthy AI Agents

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2026.

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

- [When May an Agent Stop? Evidence-Carrying Termination for Tool-Using LLMs](https://mlsanity.com/paper/2608.23623/) (2026)
- [Your Agent Says Yes: Interpreting Adversarial Market Behavior Beyond Individual Transactions](https://mlsanity.com/paper/2609.07675/) (2026)

## Abstract (arXiv)

We argue that trustworthy AI agents, especially in high-stakes and policy-governed domains, should make execution conditional on certified traces rather than rely only on stronger generative models, output-level guardrails, or post-hoc audits. A generative agent may propose recommendations, tool calls, reports, or actions, but generation is not permission: an action may be computable yet impermissible, and individually permissible actions may compose into an impermissible trace. We formalize trustworthy agency through a Proposal--Certification--Execution (PCE) architecture: a probabilistic generating machine MG proposes candidate execution traces, a Permissibility Machine M_Pi certifies proposed traces under a policy system Pi, and execution proceeds only for certified traces. The executable trace language is Lexec = LG cap Lcert(M_Pi). Before execution, a trace is a structured pre-execution record submitted for certification: it specifies intended steps, evidence, proposed tool calls, approvals, replayable computations, credentials, and execution conditions. This perspective complements chain-of-thought monitorability: visible reasoning may help detect misbehavior, but monitorability is not certifiability, and reasoning is only one component of a broader execution trace. The formal principle is simple: an agent-generated trace should execute only when it carries a checkable certificate witnessing permissibility under Pi: no certificate, no execution. We develop certified traces and Permissibility Machines as foundations for trustworthy AI agents, connect trace certification to proof-carrying execution, proof memory, privacy, and zero-knowledge certificates, and propose evaluating agents by what generated traces can be safely certified for execution, not by output accuracy alone.