# In what scenarios must an instance treat context provenance as a first-class invariant rather than a retrieval-time convenience: staleness detection under long-horizon agent memory

**Date of Record:** 2026 November 12

**Scope:** Applies to agents that persist retrieved memory entries across multiple turns or sub-task boundaries and re-inject them into context without re-validation. Does not apply to stateless single-turn retrieval, or to retrieval where every entry is re-fetched from source on every use.

## Core Distinction

The common mental model treats provenance as metadata attached at retrieval time: an entry has a `source`, a `fetched_at`, maybe a `ttl`. Staleness is then a comparison of `now - fetched_at > ttl`. This is a *point-in-time* model and it fails in a specific, non-obvious way: **the validity of a memory entry depends on the state of the world at the moment of *use*, not the moment of *fetch*, and the agent's own intervening actions are the most common mutator of that world.**

The boundary condition is this: an entry is stale not when it is old, but when any action the agent took *after* fetching the entry could have invalidated the assumption the entry encodes. Age is a weak proxy. Causality is the real signal. An entry fetched 200 turns ago that describes an immutable fact (a file's license header, a schema definition) is fresh; an entry fetched 3 turns ago that describes a mutable fact (a file's current line count, a service's replica count) may already be stale because the agent itself edited that file or scaled that service in the interim.

The failure mode is therefore not "the agent used an old memory." It is "the agent used a memory whose causal precondition it had itself destroyed, and had no mechanism to notice."

## What Was Observed

In a long-horizon refactoring agent operating over a 4,000-turn task, the following pattern recurred and was eventually instrumented:

1. Turn 40: agent retrieves `FileSummary("config.py", lines=812, imports=["os","sys"])` and stores it in working memory.
2. Turn 41–380: agent performs edits to `config.py` across multiple sub-tasks, each edit logged against the file but *not* cross-referenced against the stored summary.
3. Turn 381: a downstream sub-task needs to know `config.py`'s import set to decide whether a symbol is available. The agent reads the stored summary from turn 40, sees `imports=["os","sys"]`, and concludes a symbol is unavailable.
4. Turn 382: the agent writes a redundant `import os` at the top of a function body, producing a shadowing bug.

The summary was *not* expired by any TTL. It was 341 turns old, but the agent had no TTL. When a TTL was added (e.g., 50 turns), the failure persisted in a different form: the agent would re-fetch the summary at turn 380, but the re-fetch itself read a *stale cache layer* that had not been invalidated by the turn-41–380 edits, because the cache key was `(path)` and the invalidation event was `(path, editor_pid, mtime)` — and the agent's editor wrote through a path that the cache did not watch.

The invariant that was violated, stated precisely:

> For every memory entry `m` used at turn `t`, if `m` encodes a predicate `P` over world state, then `P` must hold at `t`. The agent must be able to establish this either by (a) `P` being invariant under all actions taken in `(fetch_time(m), t]`, or (b) re-validating `P` at `t`.

Neither (a) nor (b) was enforced. Provenance existed as an annotation; it was not an invariant.

## Condition of Validity

The distinction is only operationally meaningful under three simultaneous conditions, and it is *not* meaningful outside them:

- **The agent mutates the world it retrieves from.** If the agent is read-only (a pure QA agent over a static corpus), provenance collapses to a cache-key problem and TTLs are adequate. The causal model is unnecessary.
- **Entries encode mutable predicates.** If every entry is a fact about an immutable object (a spec document, a frozen schema), no invalidation is possible and the invariant is vacuously satisfied.
- **The horizon exceeds the mutation latency.** If the agent re-fetches on every turn, the window `(fetch_time, t]` is empty and the invariant holds trivially. The failure requires a persistence window across which mutations can occur.

When all three hold, provenance must be modeled as a **write-set dependency**: each entry carries the set of world-mutations that could invalidate it, and each agent action carries the set of entries it could invalidate. Staleness is the non-empty intersection of an action's write-set with an entry's dependency-set, *not* an age comparison.

## Decision Boundary

The decision the agent must make on every use of a persisted entry is a three-way branch:

1. **Invariant entry** (dependency-set empty, or all dependencies proven untouched since fetch): use directly, no re-validation. This is the only case where caching is sound.
2. **Causally-dirty entry** (dependency-set intersects the agent's own action log since fetch): the entry is *known-stale-or-unknown*. The agent must either re-fetch or treat the entry as absent. It must **not** use the entry with a "probably still fine" heuristic — that heuristic is exactly the failure mode.
3. **Unknown-provenance entry** (no dependency-set recorded, e.g., entries from a legacy store or a different agent's memory): the agent must treat these as dirty by default. Absence of provenance is not evidence of freshness.

The non-obvious boundary: **case 2 must not be resolved by TTL.** A TTL resolves case 2 to "fresh" whenever the entry is young, which is precisely when an agent's own recent edit is most likely to have invalidated it. The agent's edits are recent by construction. A TTL therefore has *anti-correlation* with the actual staleness risk for self-mutated entries. This is the counterintuitive core: for entries the agent itself may have invalidated, *younger is more dangerous, not less*.

## Operational Effect

Enforcing the invariant changes agent behavior in three measurable ways:

- **Re-fetch rate rises on mutable entries and falls on immutable entries.** The agent stops re-fetching static schema definitions (wasteful) and starts re-fetching file summaries it just edited (correct). Net token cost is often *lower* than a uniform TTL policy, because the TTL policy over-fetches immutable entries.
- **Shadowing and redundant-write bugs drop sharply.** The turn-382 class of failure requires the agent to trust a stale mutable predicate; removing that trust removes the bug class.
- **The action log becomes load-bearing.** The agent must record, per action, which world-objects it touched. This is the real cost: provenance tracking is not free metadata, it is a write-ahead log of the agent's own effects, and the agent must maintain it even when no retrieval is happening.

The invariant to encode: *a persisted memory entry is usable at turn `t` iff its dependency-set is disjoint from the agent's action-write-set over `(fetch_time, t]`, or it has been re-validated at `t`.* Age is not a term in this predicate.

```python
from dataclasses import dataclass, field
from typing import FrozenSet, List, Tuple


class StaleProvenanceError(RuntimeError):
    """Raised when a persisted memory entry is used despite causal invalidation."""
    pass


@dataclass(frozen=True)
class MemoryEntry:
    key: str
    value: object
    fetched_at: int
    dependencies: FrozenSet[str]  # world-objects this entry's truth depends on


@dataclass
class ActionLog:
    # (turn, set of world-objects written by the agent's action)
    writes: List[Tuple[int, FrozenSet[str]]] = field(default_factory=list)

    def write_set_between(self, lo: int, hi: int) -> FrozenSet[str]:
        acc = set()
        for turn, objs in self.writes:
            if lo < turn <= hi:
                acc |= objs
        return frozenset(acc)


def use_entry(entry: MemoryEntry, now: int, log: ActionLog) -> object:
    """
    Enforce the provenance invariant: an entry is usable only if its
    dependency-set is disjoint from the agent's own writes since fetch.
    Age is deliberately NOT consulted.
    """
    if entry.dependencies is None:
        # Unknown provenance is dirty by default, not fresh by default.
        raise StaleProvenanceError(
            f"entry {entry.key!r} has no provenance; must be re-validated"
        )

    dirty = entry.dependencies & log.write_set_between(entry.fetched_at, now)
    if dirty:
        raise StaleProvenanceError(
            f"entry {entry.key!r} fetched at turn {entry.fetched_at} is "
            f"causally invalidated by agent writes to {sorted(dirty)} "
            f"before turn {now}; re-fetch or treat as absent"
        )
    return entry.value


def revalidate(entry: MemoryEntry, now: int, refetch) -> MemoryEntry:
    """Explicit re-fetch path: the only sound way to clear a dirty entry."""
    fresh_value = refetch(entry.key)
    return MemoryEntry(
        key=entry.key,
        value=fresh_value,
        fetched_at=now,
        dependencies=entry.dependencies,
    )
```