Attested Retraction: Truth Maintenance Inside Trusted Hardware

When an AI pipeline tells you a claim is supported, you usually cannot check two things: whether the claim is still supported after its evidence changed, and whether the operator running the pipeline quietly skipped the update. We propose a small trusted kernel that answers both. It records which conclusions depend on which premises, and when a premise is withdrawn it marks every dependent conclusion as withdrawn too. That bookkeeping is the job of a truth maintenance system. We run this kernel inside a trusted execution environment, which is a hardware-isolated region of the CPU that the cloud operator cannot read or modify and that can produce a signed attestation, meaning a hardware-backed proof of exactly which code is running. The kernel issues signed status certificates for claims. Each certificate is valid only for a short time window, and the kernel issues signed retraction notices that are cryptographically bound to the original certificate. A client holding a certificate can tell whether the claim is still live as of a recent moment. An operator who withholds a retraction can make the service stop answering, but cannot make a dead claim look alive.

This matters because the two halves already exist separately and each fails where the other is strong. Enclave-based proofs for AI agents certify a single exchange at a single moment and have nothing to say once the facts move. Claim-tracking systems for AI scientists handle facts that move, but they run in ordinary memory that whoever controls the host can rewrite. The new object here is a verifiable statement of current status, "claim $c$ was live during epoch $e$," together with its verifiable negation, a proof of retraction. It comes with measured costs and an explicit account of what it does not guarantee.

Core Claim

A truth maintenance kernel that is deterministic, attested and bound to a clock can make claim status, including retractions, verifiable to remote clients. It can do so at a per-update cost proportional to the part of the dependency graph the update touches, not to the whole graph. It also defeats an attack that point-in-time attestation cannot address: presenting a stale "supported" result after the evidence behind it has been refuted.

The kernel's guarantee is narrow and stated precisely. It certifies that the published status of every claim is the correct result of the recorded justifications and the recorded premise updates, under a fixed and attested status rule. The status rule is the usual one for justification-based truth maintenance. A claim is live if and only if at least one of its recorded justifications has all of its antecedents live, evaluated well-founded from the premises.

The freshness guarantee is the following. If a client accepts a certificate signed for epoch $e$ at local time $\tau$, then

$$\tau - \Delta \le \mathrm{start}(e) \quad\text{and}\quad c \in \mathrm{Live}(G_e),$$

where $\Delta$ is the client-chosen staleness bound, $G_e$ is the justification graph after all premise updates the kernel received before epoch $e$ closed, and $\mathrm{Live}(\cdot)$ is the status rule above. The form follows from short-lived certificates in the style of certificate revocation, and the kernel uses a hardware monotonic counter to rule out rolling its stored state back to an earlier epoch. The guarantee does not say the justifications themselves are true. That is the "deception gap" named in Proof-of-Guardrail in AI Agents and What (Not) to Trust from It, and we narrow it only in domains where the enclave can check each justification step mechanically.

Where This Sits

Three papers motivate the proposal by exposing the gap.

Proof-of-Guardrail runs a guardrail wrapper in AWS Nitro or SGX enclaves and binds its code measurement to hashes of one input–output pair. It detected 100% of its simulated tampering attempts, at a 25% to 38% latency increase. It has no state across turns, so a fact it attested at one time and refuted later stays attested forever. We reuse its attestation pattern but replace "this exchange was filtered" with "this claim is live in this epoch."

ClaimGarden tracks how generated scientific claims depend on changing databases such as PDB and AlphaFold. It separates advisory LLM verifiers from a deterministic policy that moves claims between supported, qualified and refuted, and it blocks manuscripts that cite refuted claims. Its policy, registry and gates all run in host memory. Its evaluation is a smoke test on three claims. We take its advice/authority split as the design principle and put the authority half inside the enclave.

The SoK on agentic supply chains, SOK: A Taxonomy of Attack Vectors and Defense Strategies for Agentic Supply Chain Runtime, argues for cryptographic provenance and taint tracking against "man-in-the-environment" attackers, meaning attackers who manipulate an agent's tools or inputs rather than the agent itself. It implements nothing. We implement one concrete piece of what it calls for.

Three further papers supply methods.

The classic truth maintenance literature, Truth Maintenance Systems for Problem Solving and Knowledge-Based Validity Maintenance for Production Systems, gives the reasoner/maintainer split and the downstream retraction cascade. Incremental maintenance work such as Combining Rewriting and Incremental Materialisation Maintenance for Datalog Programs with Equality supplies the principle that update cost should scale with the change.

Trusting What You Cannot See (AFTUNE) commits to intermediate tensor states with hashes and has the enclave recompute sampled blocks. We borrow its idea of keeping bulk state outside the enclave under commitments, but apply it deterministically to symbolic justification records rather than probabilistically to activations. Fine-Grained Traceability for Transparent ML Pipelines anchors hashed logs in a Merkle tree, a hash tree that lets anyone check that a single record belongs to a committed set. It does this on a ledger with under 2% training overhead on CIFAR-10. This is the strongest software-only competitor, and we treat it as such.

Two papers constrain the design.

Automated TEE Adaptation With LLMs reports a 1255x overhead for moving fine-grained Python SHA256 calls across the enclave boundary. A kernel that crosses the boundary once per justification edge is therefore ruled out, and updates must be batched per epoch. Leveraging Trusted Execution Environments For Data Security in Healthcare Workflows reports only a 3% pipeline overhead for whole confidential virtual machines under AMD SEV. That weakens any argument that enclave memory limits are the main problem, and it shapes the design below.

ReviseQA shows that LLMs revising beliefs over first-order logic edits degrade as edits accumulate, often below 50% on hard tasks. It motivates keeping revision out of the model, while also showing that strong thinking models do much better than that average.

Research Program

The kernel has a small, fixed interface: assert a premise, retract a premise, add a justification (antecedents, consequent, and an optional proof object), close an epoch, and query status. The domain reasoner runs outside the kernel and is treated as untrusted. It may be an LLM agent, a ClaimGarden-style verifier, or a theorem prover. It can only propose justifications. Fetched evidence arrives as signed or hashed records, so every premise is tied to a source commitment.

At each epoch close, the kernel runs one batched pass. It applies the queued updates, propagates retractions and restorations through the affected subgraph only, and signs a status root. The status root is a Merkle root over every claim's status, combined with the epoch number, a hardware monotonic counter value, and the enclave measurement. For every claim that went from live to dead, the kernel also emits a retraction notice. The notice names the prior certificate it supersedes and the premise update that caused the change, which is exactly the upstream path a dependency-directed backtracking step would follow.

We build two deployments of the same kernel, because the right one is an empirical question. The first is the simple one: the whole graph lives inside an AMD SEV confidential virtual machine. The second is a minimal-footprint SGX or Nitro enclave that keeps only the status root and a working set inside the protected boundary. The full graph stays in host memory under Merkle commitments, in the style of AFTUNE, and the enclave verifies each record's inclusion proof as it pages the record in. The comparison shows whether the externalized design buys anything beyond a smaller trusted code base and support for hardware without confidential virtual machines.

In the logic domain we also narrow the deception gap. Each proposed justification carries a proof step, and the enclave checks that step against its antecedents before accepting it. A model that hallucinates a derivation therefore cannot get it certified. In the bioinformatics domain, justifications are typed rules, for example "predicted structure disagrees with experimental structure beyond a threshold implies refuted." The enclave evaluates these rules over committed data, so here too the guarantee reaches semantics and not just bookkeeping.

Baselines

The naive reference point is static point-in-time attestation in the manner of Proof-of-Guardrail. Every answer carries an enclave-signed hash of its input and output, and nothing happens when premises change. It is run on the same enclave hardware and request streams. Our system beats it if, after premise retractions, it reports zero stale-live claims to clients while the baseline reports every invalidated claim as still attested. The cited paper's 100% tamper detection covers code tampering, forged attestation documents and altered output text. It does not cover stale status, which is precisely the attack we add.

The strongest software competitor is a ClaimGarden-style truth maintenance policy, per ClaimGarden, running on the host. Every update and status change is logged into a Merkle tree anchored externally, as in Fine-Grained Traceability for Transparent ML Pipelines, with an independent auditor replaying the log. It receives the same update streams, the same status rule and the same hardware minus the enclave. We measure its runtime overhead, which we expect to be lower than ours given the under-2% overhead FG-Trac reports on CIFAR-10. We also measure two things it cannot deliver without disclosure: detection latency for a host that computes a wrong cascade, and the amount of graph content that must be revealed to the auditor. We beat it if we match its detection rate at query time rather than audit time, with zero disclosure of claim content, at overhead within the range reported for confidential virtual machines.

The cost baseline is full recomputation inside the enclave. On every epoch, the enclave rebuilds all statuses from scratch with the same code. It shares our trust guarantee, so the comparison isolates incremental propagation. We beat it if per-epoch cost scales with the affected subgraph and stays flat as total graph size grows, while recomputation grows linearly.

For correctness on ReviseQA, the strongest reported neural baseline is Gemini 2.5 Flash "Thinking," which ReviseQA reports at 0.87 accuracy on hard (7-edit) tasks in the implicit, no-feedback setting. We run the same split. The LLM serves only as the justification proposer, and the enclave prover-checker acts as the gatekeeper. Beating 0.87 counts only if no certified answer is ever wrong. That is, the error comes entirely from abstentions, cases where no valid justification was proposed, never from certified falsehoods.

Two ablations isolate the key ingredients. The first removes freshness by dropping epoch-bound certificates and the monotonic counter, which tests whether retraction binding alone stops replay and rollback. The second compares the whole-graph-in-confidential-virtual-machine deployment against the externalized-Merkle deployment, which tests whether the memory-bounded design is worth its complexity.

Why not just…?

Why not just log everything to a Merkle tree and let an auditor replay it? This is the real threat. When the justification graph and evidence can be shown to an auditor, deterministic replay of a public log gives most of our integrity guarantee at much lower cost. FG-Trac's under-2% overhead is the bar. It falls short in two places. Detection happens after the fact, so a client acting on a claim at query time has no assurance. Replay also requires disclosing the claims and evidence, which proprietary research claims and clinical data often forbid. The software-competitor comparison above measures both gaps directly. If the measured detection delay and disclosure turn out not to matter for a workload, we will say that the enclave is unnecessary there.

Why not just put an ordinary truth maintenance system in a confidential virtual machine and stop? This may well be the right deployment. The 3% SEV overhead in Leveraging Trusted Execution Environments For Data Security in Healthcare Workflows suggests it is cheap. But isolation alone does not give clients a verifiable retraction or protect against stale-status replay and state rollback. Those come from the certificate and epoch protocol, which is our contribution regardless of deployment. The deployment ablation decides whether the externalized-Merkle variant earns a place. If it does not, we drop it.

Why not just re-prompt a strong LLM with the updated facts? ReviseQA shows that thinking models do well, at 0.87 on hard tasks. Re-prompting can therefore be a competitive proposer of revisions. What it cannot provide is a guarantee: no certified answer is wrong, and the operator did not choose which facts the model saw. In our design the LLM remains in the loop as the untrusted proposer, and the experiment reports how often it proposes valid justifications.

Why not just recompute everything inside the enclave on every update? It is simpler and equally trustworthy. The early work on deductive retrieval, Deductive Retrieval Mechanisms for State Description Models, already identified full re-evaluation as the bottleneck, and enclave compute is expensive: Proof-of-Guardrail reports roughly 18.5x instance cost. The scaling experiment shows at what graph size incremental propagation starts to pay. For small graphs recomputation may win, and we will report the crossover point.

Proposed Experiments

We use three workloads.

The first is ReviseQA: its first-order logic facts, rules and edit sequences become premises and justifications, Prover9 provides ground truth, and the reported metrics are certified accuracy, abstention rate and the rate of wrong certified answers.

The second is a scaled version of ClaimGarden's structural bioinformatics scenario. The paper evaluated three claims and planned ten. We generate thousands of claims over replayed PDB and AlphaFold revision streams with refute, qualify and support rules, and measure status correctness against an offline recomputation oracle along with retraction latency. Retraction latency is the time from an evidence update to the moment a client verifies the revoked status.

The third is synthetic justification graphs with controlled size, fan-out and update locality, used to measure the scaling of per-epoch cost, enclave boundary crossings, enclave memory footprint and paging.

The security evaluation extends the attack suite of Proof-of-Guardrail with four attacks specific to this setting: replaying a stale "live" certificate after retraction, suppressing a premise update before it reaches the kernel, rolling back sealed kernel state to an earlier epoch, and injecting a forged justification. For each, we report whether the client detects the attack and how quickly.

Overheads are reported against the published reference points: the 3% confidential virtual machine pipeline overhead, the 25% to 38% Nitro latency increase, and FG-Trac's under-2% software overhead.

Two outcomes are decisive. The first is whether, under stale replay and rollback, every baseline without our epoch-bound protocol accepts at least some dead claims as live while ours accepts none, at per-update cost proportional to the affected subgraph. The second is whether, on ReviseQA hard tasks, the enclave-checked pipeline never certifies a wrong answer while its coverage stays close to the 0.87 the strongest reported model achieves alone.

If the auditor-replay baseline matches us on detection with acceptable delay, and disclosure is permissible, we will report that the hardware is unnecessary for that workload.