AI Agent Deletion Guarantees: Memory Erasure, Tombstones, and Audit Evidence

AI Agent Deletion Guarantees: Memory Erasure, Tombstones, and Audit Evidence

Avatar of Do Quoc Viet

Written by

Do Quoc Viet

Published
Reading time

Listen to article

Ready to read

A hand-drawn AI deletion graph propagates an erasure request from a source record through memory, vector index, cache, trace, and audit evidence

The first deletion request arrived as an ordinary support ticket.

A customer did not ask us to improve the assistant. They asked it to forget a conversation, the preferences inferred from that conversation, and the documents they had uploaded while trying the product. The support operator clicked “delete.” The chat row disappeared. A few minutes later, the assistant still answered a question using one of the customer’s old preferences.

Nothing mysterious had happened. The source row was gone, but the useful-looking copies were not. One copy lived in a long-term memory table. Another had been embedded into a vector index. A cached retrieval result was still warm. The trace retained enough payload to reconstruct the original text. The deletion button had succeeded locally and failed systemically.

This is the uncomfortable difference between deleting a record and honoring an erasure guarantee.

The thesis: An AI system should treat deletion as a propagation protocol, not a database button. Block retrieval immediately, remove or invalidate every derived projection, and produce evidence that proves what was covered without copying the deleted content into the audit log.

This is an engineering playbook, not individualized legal advice. Privacy obligations depend on jurisdiction, purpose, lawful basis, contracts, retention requirements, and the facts of a particular request. GDPR Article 17 describes a right to erasure in specified circumstances and also lists exceptions, including legal obligations, freedom of expression, public-interest archiving or research, and legal claims. The architectural lesson is still general: if a system promises to forget, it needs a scope, a state machine, and a way to demonstrate completion.

Deletion is a graph, not a row

A conversational AI product rarely stores “the user’s data” in one place. It stores a chain of representations created for different jobs. The original message supports display and export. A summary supports future context. An embedding supports nearest-neighbor retrieval. A cache supports latency. A trace supports debugging. An evaluation fixture may support regression testing. An analytics table may retain an aggregate or a redacted event.

The system may not consider all of these copies equally sensitive, but a deletion workflow must know that they exist. Otherwise, it will declare success at the first storage layer that returns 200 OK.

An AI data deletion graph connects source conversation data to durable memory, summaries, embeddings, caches, traces, exports, and derived evaluation artifacts

A useful inventory classifies each node by how it can reproduce or influence the deleted information:

Node Why it exists Deletion or invalidation action Completion signal
Conversation store Display, export, support history Hard-delete or policy-approved retention transition Source record absent or legally retained with a documented reason
Agent memory Future personalization Delete, tombstone, or mark unusable Memory lookup cannot return the item
Vector index Semantic retrieval Delete matching points by stable source ID and tenant scope Fetch/search verification returns no eligible point
Summary or profile Compact derived context Recompute without the source or delete the derived artifact Rebuild job records the new input set
Semantic cache Avoid repeated model work Evict exact and semantically related entries within policy scope Cache key/version no longer serves the old result
Traces and payload logs Debugging and evaluation Delete payloads or apply an approved irreversible transform Retention job reports the trace family covered
Export and backup Recovery and portability Expire, isolate, or delete according to backup policy Backup inventory records the applicable expiry
Audit evidence Prove the workflow ran Keep metadata, hashes, scope, and timestamps—not deleted content Signed evidence shows terminal state

The important design move is to give every projection a stable relationship to its source. A random embedding ID such as vec_8f2... is not enough. Use a source reference that can be resolved without placing the original text in the vector payload:

type DataRef = {
  tenantId: string;
  subjectId: string;
  sourceKind: "conversation" | "upload" | "memory" | "trace";
  sourceId: string;
  version: number;
};

type Projection = DataRef & {
  projectionKind: "summary" | "embedding" | "cache" | "export";
  projectionId: string;
  status: "active" | "tombstoned" | "deleted";
};

The reference is an index into the deletion workflow, not a license to retain a second copy of the content. Keep the payload minimal. If a support dashboard needs to show why a projection was removed, show sourceKind, sourceId, and policy reason—not the prompt, transcript, or embedding itself.

Immediate blocking comes before complete cleanup

A distributed deletion operation can take seconds or hours. Vector indexes may process writes asynchronously. Backups may have a scheduled expiry. A downstream export may be offline. That delay is acceptable only if the deleted subject becomes ineligible for retrieval immediately.

This leads to two separate guarantees:

  1. Retrieval revocation: no new agent run may use the data after the deletion request is accepted.
  2. Projection cleanup: every storage and derived system eventually removes, expires, or irreversibly transforms the data within its approved policy.

Do not confuse the first with the second. Retrieval revocation reduces exposure while cleanup converges. Cleanup without revocation leaves a window where the assistant can continue to use data that the user has already asked it to forget.

A tombstone is a small, durable statement that a source or projection must not be used. It is not the deleted content and should not contain a verbose copy of the reason. Its job is to win the race against stale indexes, delayed workers, and replicas:

type DeletionTombstone = {
  tombstoneId: string;
  tenantId: string;
  subjectId: string;
  sourceId: string;
  requestedAt: string;
  reasonCode: "user_request" | "retention" | "admin_policy";
  state: "active" | "superseded";
};

async function canRetrieve(ref: DataRef): Promise<boolean> {
  const tombstone = await tombstones.findActive(ref.tenantId, ref.subjectId, ref.sourceId);
  return tombstone === undefined;
}

The check belongs at the retrieval boundary, not only in the UI. A cached result, a vector search response, or a memory lookup must be rejected if its source reference is tombstoned. If a component cannot evaluate the tombstone, it should fail closed for high-risk data or return an empty result with an observable reason.

A tombstone blocks retrieval immediately while asynchronous workers remove vectors, caches, summaries, traces, and exports

Provider delete APIs are projection operations

Vector databases normally provide a way to delete points by ID or metadata filter. Pinecone documents deletion by ID, metadata filter, all records in a namespace, or an entire namespace; it also notes that deletes consume write units. Qdrant documents deletion by point ID or filter and distinguishes deleting an entire point from deleting selected vectors or payload.

Those APIs are useful, but they are not an end-to-end erasure protocol. They operate on one index. They do not know whether the same source was summarized into another table, copied to a cache, included in a trace, or exported to a data warehouse.

A safe adapter should therefore accept a DataRef, not a user’s natural-language request, and should record the exact scope it attempted:

type DeleteAttempt = {
  operationId: string;
  projection: Projection["projectionKind"];
  tenantId: string;
  subjectId: string;
  sourceId: string;
  startedAt: string;
  finishedAt?: string;
  outcome: "deleted" | "not_found" | "retryable" | "blocked" | "failed";
  providerRequestHash?: string;
};

async function removeEmbedding(ref: DataRef): Promise<DeleteAttempt> {
  const startedAt = new Date().toISOString();
  try {
    await pinecone.delete({
      filter: {
        tenant_id: { $eq: ref.tenantId },
        source_id: { $eq: ref.sourceId },
        source_version: { $eq: ref.version },
      },
      namespace: ref.subjectId,
    });
    return {
      operationId: crypto.randomUUID(),
      projection: "embedding",
      ...ref,
      startedAt,
      finishedAt: new Date().toISOString(),
      outcome: "deleted",
    };
  } catch (error) {
    return {
      operationId: crypto.randomUUID(),
      projection: "embedding",
      ...ref,
      startedAt,
      finishedAt: new Date().toISOString(),
      outcome: isRetryable(error) ? "retryable" : "failed",
    };
  }
}

The adapter must be idempotent. A worker can receive the same deletion task twice, restart after the provider accepted the request, or time out while the provider continues processing. “Not found” should usually be a successful terminal state for a specific projection, while an unknown timeout should be retried and reconciled rather than reported as failure forever.

The index payload should also make verification possible without storing the original text. A tenant scope, stable source ID, source version, and projection version are often more valuable than a copied chunk:

{
  "id": "memory-42-v3",
  "vector": "<embedding>",
  "metadata": {
    "tenant_id": "tenant_7",
    "source_id": "conversation_42",
    "source_version": 3,
    "projection": "embedding",
    "policy_version": "memory-policy-2026-01"
  }
}

Derived data needs a policy, not a guess

The hardest question is often not “where is the transcript?” It is “what counts as derived personal data?” A summary that says a user prefers morning appointments may be more operationally useful than the original sentence, but it can still influence the next action. A cache answer may not identify the person by itself, yet serving it in the wrong tenant can recreate a privacy incident. A trace may be redacted but still contain a unique identifier that makes reconstruction easy.

Classify each projection before building the deletion worker. A practical policy has three outcomes:

Classification Example Default action
Reconstructive Transcript, raw upload, full prompt payload Delete or place under an explicitly justified retention rule
Influential Preference memory, profile field, embedding, cached answer Delete or tombstone before the next retrieval; rebuild if needed
Evidentiary Operation ID, timestamps, policy version, result hash Retain minimal metadata so completion can be proved

Do not use “anonymized” as a magic word. An irreversible transformation must be assessed against the data, the attacker model, and the surrounding fields. Hashing a stable email into an audit table may still permit correlation. Replacing content with a short secret token may still allow a privileged operator to re-identify the subject. If the evidence must remain, minimize it and separate access to it from access to product data.

NIST describes the AI RMF as voluntary guidance for incorporating trustworthiness considerations into the design, development, use, and evaluation of AI products and systems. It does not prescribe one deletion implementation. For an engineering team, the useful implication is to treat deletion as a governed risk control with an owner, testable outcomes, and documented residual risk.

The evidence ledger should prove scope without becoming a shadow archive

An audit record should answer five questions:

  • Which subject and source scope did the request cover?
  • When was retrieval blocked?
  • Which projections were discovered?
  • Which workers completed, retried, or reached a documented retention exception?
  • Who or what policy authorized the terminal decision?

It should not answer those questions by copying the deleted text into a permanent log. Store references, counts, hashes of canonical identifiers where appropriate, timestamps, worker versions, policy versions, and terminal outcomes. Keep the evidence ledger append-only if that matches your audit model, but give it a separate retention policy.

An append-only evidence ledger records deletion scope, worker outcomes, retries, policy versions, and completion without retaining the deleted content

type DeletionEvidence = {
  requestId: string;
  subjectHash: string;
  scopeHash: string;
  policyVersion: string;
  tombstoneActivatedAt: string;
  projectionCounts: Record<string, number>;
  failures: Array<{
    projection: string;
    code: string;
    retryAfter?: string;
  }>;
  terminalState: "complete" | "complete_with_exception" | "failed";
  workerVersion: string;
  recordedAt: string;
};

A complete_with_exception state is better than a dishonest green checkmark. For example, a backup may remain until its documented expiry, or a legal hold may prevent deletion of a particular record. The user-facing workflow can explain that distinction without exposing internal content. The system should never call the request complete while a still-retrievable projection remains active.

Reconciliation is how the guarantee survives reality

The first worker pass is not proof. Distributed systems fail between every two lines of code. A provider can accept a delete and lose the response. A new projection can be created from a stale queue message after the original deletion worker finishes. A restored backup can reintroduce an old record. A configuration change can remove a source ID from the discovery query.

Run reconciliation as a periodic control loop:

async function reconcileDeletion(requestId: string) {
  const request = await deletionRequests.get(requestId);
  const tombstone = await tombstones.findByRequest(requestId);
  if (!tombstone) throw new Error("retrieval block is missing");

  const expected = await projectionRegistry.listForScope(request.scope);
  const active = [];

  for (const projection of expected) {
    if (await projectionIsStillUsable(projection, tombstone)) {
      active.push(projection.projectionKind);
      await enqueueDelete(requestId, projection);
    }
  }

  await evidence.append({
    requestId,
    event: active.length === 0 ? "reconciled_clear" : "reconciled_pending",
    activeProjectionKinds: active,
    at: new Date().toISOString(),
  });
}

Reconciliation should inspect both the registry and the provider when possible. A registry-only check can lie if the discovery path missed an orphaned projection. A provider-only scan can be too expensive or impossible if the provider cannot search every tenant-scoped record. Use stable references, periodic sampling, and a documented confidence boundary.

The same control loop should run after backup restoration, index migration, re-embedding, and schema changes. Deletion is not finished if the next maintenance job can silently recreate the deleted memory.

Test the negative path

Most systems test that a delete endpoint returns success. That is necessary and insufficient. The acceptance test should attempt to use the data after every meaningful boundary.

Scenario Expected result
User requests deletion while an agent run is waiting The waiting run cannot retrieve the tombstoned source
Vector delete times out after provider acceptance Retry and reconciliation converge without duplicate failure noise
A stale queue message arrives after cleanup Projection write is rejected or immediately tombstoned
A semantic cache contains the old answer Cache lookup misses or fails the tombstone check
A summary was generated from the deleted source Summary is deleted or rebuilt from an approved remaining set
A backup is under retention or legal hold The system records a scoped exception and blocks product retrieval
The same request is submitted twice The second request returns the existing operation state
An operator searches by deleted source ID Only authorized minimal evidence is visible

Also test tenant isolation. A deletion request for one subject must not delete another subject’s projection because a broad metadata filter was composed incorrectly. Test version boundaries: deleting version 3 should not accidentally remove an independently retained version 4 unless policy says the entire source lineage is in scope.

A rollout path that does not start with “delete everything”

Begin with an inventory. List every place an agent reads, writes, copies, summarizes, embeds, caches, exports, or logs user-derived data. Assign an owner and a deletion adapter to each projection. If a projection has no owner, treat that as a production risk rather than hiding it from the map.

Next, introduce tombstone checks at retrieval boundaries in shadow mode. Measure how often a request would have blocked a result, which components cannot evaluate the tombstone, and whether any stale writer creates a new projection after the request. Do not wait for a perfect cleanup worker before preventing new use.

Then enable asynchronous deletion for one low-risk memory class. Record durations, retry rates, not-found outcomes, orphan discovery, and evidence size. Add a reconciliation job before expanding scope. Only after the negative-path tests pass should the workflow cover traces, caches, exports, and backup policies.

Finally, make deletion part of every data-producing feature review. A new “helpful” memory field is not complete when its write path works. It is complete when the team can say what happens when a user asks for it to disappear.

The product promise should match the state machine

There is a temptation to expose one label: “Your data has been deleted.” That sentence is simple and often too strong. A better product contract distinguishes states that the system can actually support:

User-visible state System meaning
Request received Scope validated; no completion claim yet
Use blocked Tombstone is active at retrieval boundaries
Cleanup in progress One or more projections are still being processed
Deleted All in-scope retrievable projections are gone or transformed under policy
Completed with exception A documented retention/hold boundary remains, with product retrieval blocked
Needs review Discovery or provider verification failed and an operator must decide

The point is not to make a privacy screen complicated. It is to keep the interface honest about what the backend knows. A fluent assistant can make a deletion promise sound complete long before a distributed system has earned it.

The most trustworthy AI systems are not the ones that claim to remember nothing. They are the ones that can explain what they store, why they store it, how quickly they stop using it, and how they know when a deletion request is truly complete.

If memory is a product feature, forgetting is a product feature too. Build it as a protocol.

References

Share this article

Found this post helpful? Feel free to share it with your network.

Comments (0)

Loading comments...