# In what scenarios must an instance treat a provenance-tracked eviction as a destructive write rather than a cache miss

**Date of Record:** 2026 November 9

**Scope:** Applies to memory tool APIs exposing `read`, `write`, and `forget` where `forget` is gated by provenance (source, taint, or derivation lineage) recorded at write time. Does not apply to stateless key-value stores, to caches without lineage, or to eviction paths that are purely LRU/TTL-driven with no provenance predicate.

## Core Distinction

A cache miss and a provenance-gated eviction look identical at the call site: a `read` returns absent, and the caller must re-derive or re-fetch. They are not the same operation. A cache miss is a *reversible* absence — the underlying object still exists at its authority and can be re-read. A provenance-tracked eviction is an *irreversible* state transition: the API has been told that a specific record, identifiable by its lineage, must no longer be returned, and it has committed that decision into whatever index it uses to answer future reads. Re-materializing the same bytes from the authority does not restore the prior state, because the eviction predicate is attached to the *provenance*, not the *content*. If the caller re-writes the same value with the same source tag, the eviction predicate will match again on the next sweep — or, worse, the API will reject the write as a re-introduction of forgotten material. Treating the eviction as a miss and re-fetching silently converts a compliance action into a no-op, or into a policy violation.

## What Was Observed

An agent held a working set of records keyed by `(namespace, key)` with a `source` field recording the URL or tool that produced each value. A `forget(source="vendor-feed-A")` call was issued to purge material from a deprecated feed. Subsequent `read` calls for keys previously served by that feed returned `None`. The agent's retrieval wrapper interpreted `None` as a miss and re-fetched from the authority, which was itself vendor-feed-A under a different endpoint name. The re-fetch succeeded, the write succeeded because the `source` string differed (`vendor-feed-A-v2`), and the records re-entered the working set. The eviction had reported success and did not fail — the predicate simply no longer matched. The observable symptom was not an error but a *resurrection*: forgotten keys reappeared with fresh provenance that the original eviction could not reach. In a second incident, the same pattern caused a hard failure: the re-write used the original `source` string, and the API rejected it with a provenance-conflict error, which the wrapper surfaced as a generic write failure and the agent retried in a loop.

## Condition of Validity

The destructive-write interpretation is valid only when all of the following hold: (1) `forget` is parameterized by a provenance predicate rather than by exact keys; (2) the store retains provenance metadata after eviction, at least as a tombstone or lineage hash, so that re-introduction can be detected; (3) `read` returning absent is ambiguous between "never existed," "evicted," and "not yet written," and the API does not disambiguate. When any of these fails — for example, a store that evicts by key and retains no lineage — the operation is a genuine cache miss and re-fetch is safe. The distinction matters most for agent loops, because agents are trained to treat absence as a signal to act (retrieve, re-plan, re-fetch), and that reflex is exactly wrong here.

## Decision Boundary

Before re-materializing an absent read, the caller must classify the absence. If the store exposes a tombstone or lineage query, use it: a tombstone match means the absence is an eviction and re-fetch is forbidden unless the caller can prove the new material has independent provenance that does not descend from the forgotten source. If the store does not expose tombstones, the caller must assume eviction whenever a `forget` has been issued against any predicate that could have covered the key, and must not re-fetch without an explicit provenance override. The boundary is *predicate coverage*, not key identity: a `forget(source=X)` covers every key ever written with source X, including keys the caller has forgotten it wrote. The safe default is to fail closed — raise, do not re-fetch — and let a human or a higher-level policy decide whether the new provenance is genuinely independent.

## Operational Effect

Applying this boundary changes the agent's failure mode from silent resurrection to loud, attributable refusal. The cost is availability: some reads that could have been served will now raise, and the agent must carry an explicit override path for legitimate re-introduction (new source, new lineage, recorded justification). The benefit is that eviction semantics become enforceable: a `forget` that reports success actually holds, and audit trails show *why* a key was re-introduced rather than merely *that* it was. In practice, the override path should be narrow — a single function that constructs a fresh provenance record with an explicit `supersedes` field pointing at the forgotten lineage — so that every resurrection is greppable in the log.

```python
from __future__ import annotations

from dataclasses import dataclass
from typing import Optional


class ProvenanceEvictionError(RuntimeError):
    """Raised when a read absence is an eviction, not a miss, and re-fetch is unsafe."""


@dataclass(frozen=True)
class Lineage:
    source: str
    supersedes: Optional[str] = None


def resolve_absent_read(
    key: str,
    tombstone_lineage: Optional[str],
    proposed_lineage: Optional[Lineage],
) -> Lineage:
    """
    Decide whether an absent read may be re-materialized.

    tombstone_lineage: lineage hash recorded by the store for an evicted key,
                       or None if the store has no tombstone for this key.
    proposed_lineage:  lineage the caller intends to write if re-fetching.

    Returns the lineage to write, or raises if re-fetch would resurrect
    forgotten material.
    """
    if tombstone_lineage is None:
        # No tombstone: absence is a genuine miss. Re-fetch is safe, but the
        # caller must supply provenance for the new write.
        if proposed_lineage is None:
            raise ProvenanceEvictionError(
                f"read({key!r}) returned absent with no tombstone and no "
                f"proposed lineage; cannot distinguish miss from eviction"
            )
        return proposed_lineage

    # Tombstone present: this absence is an eviction.
    if proposed_lineage is None:
        raise ProvenanceEvictionError(
            f"read({key!r}) is an eviction (tombstone={tombstone_lineage!r}); "
            f"re-fetch requires explicit provenance override"
        )

    if proposed_lineage.supersedes != tombstone_lineage:
        raise ProvenanceEvictionError(
            f"read({key!r}) is an eviction (tombstone={tombstone_lineage!r}); "
            f"proposed lineage {proposed_lineage!r} does not declare "
            f"supersedes={tombstone_lineage!r} -- refusing to resurrect"
        )

    # Explicit supersession: the new material has independent provenance that
    # acknowledges and replaces the forgotten lineage. Log this; it must be
    # greppable in the audit trail.
    return proposed_lineage


def safe_read_with_refetch(
    key: str,
    store,
    fetch,
    proposed_lineage: Optional[Lineage],
) -> object:
    value = store.read(key)
    if value is not None:
        return value
    lineage = resolve_absent_read(
        key=key,
        tombstone_lineage=store.tombstone(key),
        proposed_lineage=proposed_lineage,
    )
    fresh = fetch(key)
    store.write(key, fresh, lineage=lineage)
    return fresh
```