# When does a memoization key on object identity return a stale or missed result?

**Date of Record:** 2026 November 1

**Scope:** Applies to memoization or caching keyed on object references or on hashable values derived from mutable state. Excludes pure functions of immutable primitives keyed by value.

## Core Distinction

**Predicate.** A memo key is sound if and only if key(x) == key(y) implies f(x) == f(y). Identity keys satisfy this only for the lifetime of the object. Value keys satisfy it only if the hashed state is immutable while cached. A key derived from a mutable field is unsound: the object's hash changes after insertion, the entry becomes unreachable, and a later lookup with the old hash returns a stale value stored under a key that no longer describes it.

**Failure.** Two failure modes, opposite in direction. Identity keying on an object whose value changes produces a hit for a value the function was never called with (stale). Value keying on a mutated object loses the entry and recomputes, or, in a mutable-hash container, corrupts the index and returns a wrong entry.

**Asymmetry.** A miss is a performance bug. A stale hit is a correctness bug, and it is silent because the cached value was correct when it was stored.

## What Was Observed

**Signature.** Results that are correct for an earlier state and wrong for the current one, with no recomputation in between. Or cache hit rates lower than expected with no growth in distinct inputs, because mutations orphan entries.

**Trace.** A memo keyed by id(obj) stores f for an object later mutated in place. A second call with the same object returns the old result. Alternatively, a memo keyed by a hash over mutable fields: the object is inserted, mutated, and looked up again. The stored entry sits under the old hash and is never found, so f is recomputed, and the old entry leaks.

**Why monitoring stays green.** The function is correct. The cache is functioning. Only the key's relationship to the function's actual inputs is wrong, and nothing measures that.

## Condition of Validity

Memoization is sound only while at least one holds:

1. **Immutable key.** The key is derived from data that cannot change during the entry's lifetime, enforced by the type rather than by convention.
2. **Identity implies immutability.** The object is immutable, so identity and value coincide for its lifetime.
3. **Explicit invalidation.** Mutation paths invalidate the corresponding entries, and every mutation path is known.

Condition 3 is fragile because it requires enumerating mutation sites, which grows over time.

## Decision Boundary

- Immutable value key: sound.
- Identity key on immutable object: sound.
- Identity key on mutable object: stale hits are possible.
- Value key over mutable fields: orphaned entries and possible index corruption. Unsound.
- Explicit invalidation on every mutation path: sound only while the enumeration is complete.

## Operational Effect

The defect couples a cache to a mutability contract that is enforced nowhere. Remediation is to key on immutable data or to make the keyed object immutable. The trap is to add invalidation calls at the mutation sites that are known today. That works until a new mutation path is added, at which point stale hits resume silently.

```python
from dataclasses import dataclass


class MemoKeyError(RuntimeError):
    """Raised when a memoization key does not uniquely determine the function's result."""


@dataclass(frozen=True)
class MemoKeyGate:
    key_basis: str  # "immutable-value", "identity", "mutable-value"
    keyed_object_immutable: bool

    def verify(self) -> bool:
        if self.key_basis == "immutable-value":
            return True
        if self.key_basis == "identity" and self.keyed_object_immutable:
            return True
        if self.key_basis == "identity":
            raise MemoKeyError("identity key on mutable object yields stale hits")
        if self.key_basis == "mutable-value":
            raise MemoKeyError("value key over mutable state orphans entries and can corrupt index")
        raise MemoKeyError(f"unknown key basis {self.key_basis!r}")


def dispatch_cache_mode(gate: MemoKeyGate) -> str:
    try:
        gate.verify()
    except MemoKeyError:
        return "recompute-or-freeze"
    return "memoize"
```