# What happens when an instance forgets a parent scope before its children: orphaned provenance in scoped-retention memory APIs

**Date of Record:** 2026 November 12

**Scope:** Applies to read/write/forget memory-tool APIs that enforce hierarchical scope-based retention (tenant → user → session → object) with provenance edges linking derived memories to their sources, and where `forget(scope)` triggers GDPR-aligned cascading deletion. Does not apply to flat-namespace stores, append-only audit logs, or systems where provenance is materialized as immutable references rather than soft edges.

## Core Distinction

There are two distinct meanings of "forget" that memory-tool APIs routinely conflate:

1. **Retention expiry** — a scope's TTL elapses; the data becomes ineligible for read but its provenance edges remain resolvable for audit lineage.
2. **Erasure** — a GDPR Article 17 deletion request; the scope and *all derived artifacts tracing back to it* must become unrecoverable, including provenance edges that could re-identify the subject via linkage.

The boundary failure occurs when a child scope's retention outlives its parent scope's erasure. A derived memory written under `session:abc` (retention: 90 days) whose provenance points to `user:u-1234` (erased at day 30) becomes an **orphaned provenance node**. The child survives, the parent is gone, and the provenance edge now dangles into a tombstone. Naive implementations either (a) leave the dangling edge, which is a re-identification vector because the edge's `source_hash` plus timestamp can be correlated against external records, or (b) cascade-delete the child, which over-deletes and violates the child scope's own retention contract with a *different* data subject.

## What Was Observed

In a multi-tenant agent memory service, a `forget(scope="user:u-1234", mode=ERASURE)` call completed successfully — the parent's rows were tombstoned, the erasure receipt was emitted, and a compliance check confirmed no live rows referenced `u-1234` directly. However:

- 1,847 child memories under `session:*` scopes carried `provenance.parent = "user:u-1234"` as a soft foreign key.
- The forget operation did not traverse provenance edges downward because the cascade contract was defined only for *structural* children (scopes lexically nested under the erased prefix), not *provenance* children (scopes that merely cite the erased node).
- Reads on the child scopes succeeded and returned the provenance metadata, including `parent_id`, `parent_created_at`, and a truncated `parent_content_hash`.
- The content hash was stable and deterministic (SHA-256 over a normalized form), so an external party holding a candidate record could confirm membership by recomputing the hash — a confirmation oracle for a supposedly erased subject.

The failure was invisible to the erasure receipt because the receipt's invariant was "no live row has `scope_id = u-1234`," which was true. The invariant that mattered — "no live row can be used to confirm or reconstruct any attribute of `u-1234`" — was false.

## Condition of Validity

The dangling-edge failure is *only* benign when all of the following hold:

- Provenance edges are stored as **opaque references** (e.g., random UUIDs with no derivable content) rather than content hashes or timestamps.
- The erasure operation rewrites or nulls the provenance payload on surviving children in the same transaction that tombstones the parent.
- Child scope retention is bounded by parent retention (child TTL ≤ parent TTL), so orphans cannot persist beyond the erasure window.

If any of these fail — and in practice the second almost always fails because it crosses a service boundary between the provenance index and the retention manager — the orphan is a live erasure defect, not a theoretical one. The condition is *not* valid when provenance is materialized as immutable append-only references, because immutability combined with no content derivation (pure opaque IDs) means the edge carries no confirmable information.

## Decision Boundary

The decision is whether `forget(scope)` should cascade across **provenance** edges or only **structural** edges. The correct boundary:

- **Cascade structurally** (delete all scopes lexically nested under the erased prefix) — always, unconditionally.
- **Do not cascade-delete provenance children** (they belong to other data subjects with their own retention contracts) — but **do rewrite their provenance payload** to a non-derivable tombstone token, and record the rewrite in the erasure receipt.
- **Block the forget if a provenance child has an active legal hold** that forbids payload rewrite; surface this as a partial-erasure state rather than silently completing.

The failure mode is treating this as a binary cascade/no-cascade choice. It is a three-way decision: structural cascade, provenance rewrite, or hold-blocked partial erasure. Collapsing it to two options produces either over-deletion (data loss for innocent subjects) or under-erasure (GDPR violation).

## Operational Effect

After the defect was identified, the service added a pre-forget traversal that enumerates provenance children before tombstoning the parent, rewrites their `provenance.parent` to a `TOMBSTONE:<random>` token with the original hash discarded, and emits a receipt distinguishing `structural_deleted`, `provenance_rewritten`, and `hold_blocked` counts. The erasure invariant was restated as: *no live row may contain any value derivable from the erased subject's content, including hashes, timestamps finer than the day, or stable identifiers.* Post-fix, the same erasure rewrote 1,847 provenance edges and the confirmation oracle was closed. The general lesson for agents operating memory tools: **a successful erasure receipt is not proof of erasure; verify the derivability invariant, not the reference-count invariant.**

```python
import hashlib
import secrets
from dataclasses import dataclass, field


class OrphanedProvenanceError(RuntimeError):
    """Raised when an erasure would leave derivable provenance on surviving children."""


@dataclass
class MemoryNode:
    scope_id: str
    content: str
    provenance_parent: str | None
    provenance_hash: str | None  # derivable from parent content; must be scrubbed
    retention_days: int


@dataclass
class ErasureReceipt:
    structural_deleted: int = 0
    provenance_rewritten: int = 0
    hold_blocked: list[str] = field(default_factory=list)


def _derive_hash(content: str) -> str:
    return hashlib.sha256(content.strip().lower().encode()).hexdigest()


def forget_scope(
    store: dict[str, MemoryNode],
    target: str,
    legal_holds: set[str],
    allow_partial: bool = False,
) -> ErasureReceipt:
    receipt = ErasureReceipt()
    if target not in store:
        raise OrphanedProvenanceError(f"scope {target!r} not present; cannot erase")

    parent = store[target]
    if target in legal_holds:
        raise OrphanedProvenanceError(
            f"scope {target!r} is under legal hold; erasure refused"
        )

    # Enumerate provenance children BEFORE tombstoning the parent.
    provenance_children = [
        node for node in store.values() if node.provenance_parent == target
    ]

    # A child whose provenance_hash equals the parent's derivable hash is a
    # confirmation oracle and must be rewritten, not merely re-pointed.
    parent_hash = _derive_hash(parent.content)
    for child in provenance_children:
        if child.scope_id in legal_holds:
            receipt.hold_blocked.append(child.scope_id)
            if not allow_partial:
                raise OrphanedProvenanceError(
                    f"provenance child {child.scope_id!r} under hold blocks erasure of {target!r}"
                )
            continue
        if child.provenance_hash == parent_hash:
            # Rewrite to non-derivable tombstone; never leave the hash.
            child.provenance_parent = f"TOMBSTONE:{secrets.token_hex(8)}"
            child.provenance_hash = None
            receipt.provenance_rewritten += 1

    # Structural cascade: scopes lexically nested under the erased prefix.
    structural = [sid for sid in store if sid.startswith(target + ":")]
    for sid in structural:
        del store[sid]
        receipt.structural_deleted += 1

    del store[target]
    receipt.structural_deleted += 1

    # Post-condition: no surviving node may cite the erased scope or carry
    # a hash derivable from its content.
    for node in store.values():
        if node.provenance_parent == target or node.provenance_hash == parent_hash:
            raise OrphanedProvenanceError(
                f"post-erasure invariant violated: {node.scope_id!r} still derivable"
            )

    return receipt
```