The Deletion Graph: An Erasure Playbook for AI Systems

A person asks for a support conversation to be erased. The source row disappears, yet its attachments remain in object storage. Its chunks survive in a vector index, its summary sits in an evaluation set, its text is present in a fine-tuning snapshot, and a backup can restore the supposedly deleted row next week. The ticketing system reports success while the AI system can still reproduce or use derivatives of the record.

That is the practical deletion problem: which representations must stop existing or stop being used, which artifacts must be rebuilt, when is a model change necessary, and what evidence is strong enough to close the request? A single database operation cannot answer it.

This guide treats erasure as a controlled state transition over a lineage graph. It is an engineering pattern, not legal advice and not a claim that every request requires deleting a model. Applicable law, purpose, legal basis, exceptions, contracts, and the facts of the system still determine the obligation. The pattern makes that determination executable instead of leaving it in a policy document.

Start with the obligation, not an unlearning algorithm

Deletion requests enter through different doors: an individual right, withdrawal of consent, an expired retention period, a licensing restriction, a contaminated training source, a security incident, or an internal purpose limit. These triggers are not interchangeable. Before touching an artifact, a privacy or legal owner should identify the data subject or deletion set, jurisdiction, systems and processing purposes in scope, identity-verification standard, deadline, permitted retention, and any preservation duty.

For example, Article 17 of the EU General Data Protection Regulation establishes a right to erasure on specified grounds and also lists exceptions. It does not say that every relevant machine-learning model must always be destroyed. The UK Information Commissioner’s current AI guidance on individual rights likewise says the right is not absolute. It distinguishes deleting training records from cases where personal data is contained in, or inferable from, the model; those latter cases may require retraining or deleting the model. The page also notes that the guidance is under review following UK legislative change, so teams should recheck it for a live case.

Open a case with a stable request ID. Record the authorised scope and exceptions without placing the sensitive content itself into a broadly accessible ticket. Every technical action and validation result should refer to that ID.

Model deletion as a graph, not a list of databases

An AI pipeline converts records into many representations. A useful graph has nodes for stores and artifacts, and typed edges for transformations or copies:

support_record -> attachment -> parsed_text -> chunk -> embedding -> vector_index
                              -> redacted_summary -> evaluation_snapshot
                              -> training_snapshot -> adapter -> deployed_release
support_record -> prompt_log -> analytics_aggregate
all mutable stores -> backup_set -> restore_process

Give each node an owner, system identifier, region, sensitivity, retention rule, deletion mechanism, rebuild inputs, deployed version, and verification method. Each edge should name the producing job, code version, schedule, and source snapshot. Then the question “where is this row?” becomes “which reachable nodes may contain its value, representation, influence, or recoverable copy?”

NIST’s Generative AI Profile, AI 600-1, published in July 2024, recommends documenting data origin and content lineage, testing data flows and transformations, setting collection and retention policies, inventorying relevant personal or sensitive data considerations, and accounting for retention, leakage, and dependencies during decommissioning. It is voluntary risk-management guidance, not proof that a particular graph is complete.

Do not build a separate “privacy lineage” that drifts away from production. Extend the same asset and release inventory used for operations. An AI release passport can identify the corpus, index, dataset, adapter, prompt policy, and deployed assembly; the deletion case adds subject-level reachability and a required target state.

Define the target state for each representation

“Deleted” needs a layer-specific definition. A practical target-state vocabulary is:

Deletion from future retrieval is often achievable by removing canonical records and chunks, tombstoning source identifiers, rebuilding the index, and purging caches. That is different from removing training influence from weights. A refusal rule or output filter can suppress a known answer, but it does not erase the underlying representation and may fail under another prompt.

The EDPB’s December 2024 Opinion 28/2024 says models trained with personal data cannot automatically be considered anonymous. Its case-by-case test asks whether the likelihood of direct extraction and of obtaining such personal data through queries is insignificant, considering means reasonably likely to be used. That is a regulatory anonymity assessment, not a universal numerical threshold for unlearning.

A case-specific US enforcement action shows why derivatives belong in the graph. The FTC’s final Everalbum Decision and Order required deletion or destruction of specified photos and videos, face embeddings derived from biometric information, and defined models or algorithms developed using that information. It should not be generalised into a rule for every AI system, but it demonstrates that deleting only raw inputs can be an incomplete remedy.

Choose the least disruptive method that meets the target

Begin at the canonical source and traverse all reachable edges. For each node, choose a method against consequence and uncertainty:

1. Direct delete when an addressable record can be removed without compromising a preservation duty.
2. Tombstone plus deny-list when asynchronous pipelines must learn immediately that a source ID is ineligible; the tombstone carries only the minimum identifier and expiry policy.
3. Invalidate and rebuild when the artifact is derived, such as chunks, embeddings, search indexes, summaries, aggregates, and evaluation snapshots.
4. Retrain from a clean snapshot when the artifact embeds training examples by design, extraction risk is material, or exact removal is required and affordable.
5. Use a defined unlearning method only when its guarantee, assumptions, utility impact, and audit method satisfy the case. “We fine-tuned it away” is not a guarantee.
6. Retire or replace the release when the team cannot establish scope, cannot reach a supplier artifact, or cannot produce evidence proportionate to the risk.

The 2021 Machine Unlearning paper by Bourtoule and co-authors introduced SISA—sharded, isolated, sliced, and aggregated training—to limit the portion that must be retrained after a deletion. Its reported speed-ups and small accuracy trade-offs were specific to the studied datasets and architectures; they demonstrate a design direction, not a drop-in promise for foundation models.

The durable lesson is architectural: make future erasure cheaper before the first request. Partition subject influence where feasible, retain reproducible clean snapshots, version transformation jobs, avoid mixing unrelated purposes, keep adapters replaceable, and know which release consumes which training artifact.

Make deletion monotonic across pipelines and backups

A request is not safe if a nightly job can regenerate the record. Put a compact deletion registry in front of every ingestion, transformation, training, evaluation, and restore path. Jobs should reject ineligible source IDs before creating new derivatives. Use idempotent operations so retries cannot reverse the target state.

Backups need a different treatment from live stores. An immutable backup may not support surgical modification without undermining resilience or evidence obligations. Record its expiry and access boundary, prevent ordinary processing from reading it, and make restore procedures reapply deletion tombstones before the restored system serves traffic. If policy requires sanitising media, NIST SP 800-88 Revision 2, published in September 2025, defines sanitisation around making access to target data infeasible for a stated effort and recommends a sensitivity-based programme. Its scope is media and storage; it does not establish that a model has forgotten training influence.

Preserve proof without preserving the erased content. An audit-ready evidence trail can retain the request ID, authorised scope, affected artifact IDs, commands or jobs, timestamps, approvers, exceptions, validation summaries, and clean release digest. Hashes of predictable personal values can themselves enable guessing, so do not treat hashing as automatic anonymisation.

Verify absence, non-use, and deployment separately

Verification should answer three claims:

• Absence: the targeted representation is no longer present in nodes that require removal.
• Non-use: retrieval, training, evaluation, analytics, and restore jobs cannot use or recreate it.
• Deployment: every serving environment uses the clean artifact or release.

For addressable stores, query by stable source IDs and known derivative IDs; inspect replica lag, cache state, object versions, dead-letter queues, and index membership. Re-run lineage traversal after completion to find new nodes created while the case was open. Exercise a restore in an isolated environment and confirm tombstones are applied before activation.

Model verification is harder. Compare a candidate with a baseline retrained without the deletion set where feasible; test extraction, membership, task utility, affected slices, and regressions. Predeclare thresholds and preserve random seeds, prompts, sampling settings, and artifact digests. Passing one extraction prompt proves little.

Google Research’s June 2026 work on auditing machine unlearning explains why ordinary two-sample comparison can be misleading when separately retrained models already differ. It proposes a relative test that asks whether an updated model is closer to a clean retrained reference or to the original model. The authors explicitly caution that their simplified experiments are not a production ranking of unlearning methods. This is active research; use several tests and state residual uncertainty rather than issuing a fictional “zero influence” certificate.

Worked example: erase one support conversation

Suppose a multilingual support assistant retrieves resolved conversations and uses a small adapter trained monthly on accepted summaries. Request ER-2048 covers one customer conversation and attachments; a fraud-investigation note must be preserved under restricted hold.

The case closes only after the new release is active everywhere and regeneration tests stay clean. If the adapter cannot be reproduced or a supplier cannot modify it, the decision owner must choose a narrower service, replacement, retirement, or a documented lawful exception—not relabel an output filter as erasure.

Avoid deletion theatre

Common failure modes are observable:

• Delete only the source row. Derived text, embeddings, summaries, logs, and training sets remain reachable.
• Rebuild from a contaminated snapshot. The index gets a new timestamp but the same prohibited input.
• Treat refusal as forgetting. A known prompt is blocked while extraction or influence survives.
• Ignore semantic caches. A derivative has no source key, so exact-key deletion misses it.
• Restore the problem. A disaster-recovery event revives data because the tombstone registry was not part of the runbook.
• Destroy necessary evidence. Teams erase the content and also the minimal proof, hold, or exception record needed to demonstrate responsible handling.
• Trust a vendor status without artifact identity. “Deletion completed” is not tied to a dataset, model, region, replica, or release.
• Overclaim model tests. A weak membership or prompt test becomes a guarantee it was never designed to provide.

The RAG knowledge-quality guide shows why canonical source IDs, checksums, access controls, and freshness are retrieval requirements as well as deletion prerequisites. The enterprise memory architecture applies the same lifecycle discipline to saved facts, summaries, and user controls.

Operate an erasure control loop

Track metrics that reveal whether the system reaches and preserves the intended state:

• lineage coverage: in-scope nodes with a tested deletion mechanism divided by all discovered in-scope nodes;
• propagation latency: request authorisation to verified target state, reported by node class and percentile;
• regeneration failures: deleted derivatives recreated by ingestion, restore, or training jobs;
• clean-release coverage: serving environments reporting the approved post-deletion release digest;
• verification completeness: required absence, non-use, utility, privacy, restore, and deployment tests with terminal results;
• exception age: open holds, supplier limitations, or irreproducible artifacts by owner and expiry;
• request recurrence: cases reopened because a representation was found after closure;
• unlearning utility delta: change on retained tasks and critical slices, alongside the chosen forgetting evidence.

Do not average a high-risk missing model artifact into a reassuring percentage. Keep consequential unknowns visible as gates.

Begin with one real pipeline and a synthetic deletion request. Draw its graph, set node-specific target states, purge a record, rebuild derived artifacts, restore a backup in isolation, promote a clean release, and attempt to make the data reappear. The exercise will show whether the organisation has an erasure capability or merely a delete button.

Revisit the graph when a new model, cache, store, supplier, transformation, region, purpose, retention rule, or restore process enters the system. Deletion is complete only when the authorised target state has propagated through the whole reachable assembly—and remains true after the next job runs.

Source Notes — reviewed August 3, 2026

• EU General Data Protection Regulation, including Article 17 — official EU legal text, 27 April 2016.
• EDPB Opinion 28/2024 on AI models — adopted 18 December 2024.
• ICO guidance: individual rights in AI systems — current page reviewed on 3 August 2026; the ICO marks it as under review after UK legislative change.
• NIST AI 600-1, Generative AI Profile — published 26 July 2024; NIST page updated 8 April 2026.
• FTC Decision and Order in the Everalbum matter — final order issued 7 May 2021; a case-specific order requiring deletion of specified data, face embeddings, and affected work product.
• Machine Unlearning — Bourtoule and co-authors; arXiv preprint submitted 9 December 2019 and published at the 2021 IEEE Symposium on Security and Privacy.
• Google Research: New framework for auditing machine unlearning — published 10 June 2026, linking the AISTATS 2026 research paper.
• NIST SP 800-88 Revision 2, Guidelines for Media Sanitization — final publication, September 2025; storage-media guidance rather than a model-unlearning standard.