[BUG] A turn that diverges mid-history (rewind, idle/auto compaction) starts a cold lineage, so the whole conversation is re-written to the prompt cache #4284

Disclaimer: This report was drafted by Claude (an AI coding assistant) on my behalf. All claims in it are backed by actual investigation — reading the headroom source directly and hands-on testing/reproduction against a live proxy — not simulated or hallucinated. I reviewed the content before posting and stand behind it. Happy to answer follow-ups or run further tests myself.

Description

When a Claude Code request diverges from its conversation partway through the history, SessionTrackerStore.resolve_tracker starts a new lineage with an empty tracker. The new tracker has no _last_original_messages / _last_forwarded_messages, so overlay_cached_prefix returns early (if not prev_orig or not prev_fwd) and nothing is replayed. Every earlier message that was forwarded in compressed form now goes out as the original bytes, the provider prefix changes at the first compressed message, and the whole conversation is re-written to the prompt cache.

This is the same failure as #3933 and #4156 (a cold tracker loses cached-prefix replay), reached by a third trigger. Those fixes, and #4043, all work by matching the request to an existing lineage. This trigger can't be matched that way, because the request genuinely is not a continuation of any recorded turn. But its leading messages are still byte-identical to a prefix the provider already has cached, so the replay state for that prefix is still valid.

Two Claude Code flows produce this shape:

1. Rewind / edit an earlier message. The client resends the first k messages of the history plus a new user message. History 225 → 217 messages, divergence at message 216.
2. Idle or automatic compaction. The client drops the final assistant reply and appends the compaction instruction (CRITICAL: Respond with TEXT ONLY. Do NOT call any tools. ...) as an extra block on the last user message. This is a block append on a chain that is shorter than the recorded one, so none of the existing relations match.

Without headroom, both are a cache hit for everything up to the changed message. With compression on, both re-write the entire context.

Evidence (live proxy, Claude Code 2.1.29x, headroom 0.40.0 + #3810, cache mode, Anthropic)

The proxy ran a per-session A/B: 50% of Claude Code sessions (hashed X-Claude-Code-Session-Id) bypassed compression. With OVERLAY_TRACE-style logging of resolve_tracker's decision:

Over 8 days (2026-10-11 to 10-19), requests that started a new lineage with a mid-history divergence at message ≥ 8 caused 11 full re-writes (2.7M tokens) on the compression arm and none on the bypass arm. At Anthropic's 1h cache-write price that is about $12.50 of extra spend, more than compression saved on that arm in the same window.

Reproduction

Against current main (fbf7bc3):

from headroom.cache.prefix_tracker import PrefixFreezeConfig, SessionTrackerStore

def u(t): return {"role": "user", "content": [{"type": "text", "text": t}]}
def a(t): return {"role": "assistant", "content": [{"type": "text", "text": t}]}

store = SessionTrackerStore(PrefixFreezeConfig())
orig, fwd = [], []
for i in range(13):
    if i % 2 == 0:
        orig.append(u(f"q{i}")); fwd.append(u(f"q{i}"))
    else:
        orig.append(a(f"long tool output {i} " + "x" * 200)); fwd.append(a(f"short {i}"))

t1 = store.resolve_tracker("s", "anthropic", messages=orig, cache_affinity="aff")
t1.update_from_response(cache_read_tokens=5000, cache_write_tokens=100,
                        messages=fwd + [a("A")], original_messages=orig + [a("A")])

# Rewind: first 10 messages, then a different question.
t2 = store.resolve_tracker("s", "anthropic", messages=orig[:10] + [u("a different question")],
                           cache_affinity="aff")
print(t2 is t1)                           # False (expected: a new lineage)
print(t2.get_last_forwarded_messages())   # [] -> nothing for overlay_cached_prefix to replay
# Expected: fwd[:10], the bytes the provider cached for the shared prefix.

Proposed fix

Keep lineage matching as it is. Only when resolve_tracker is about to create a new lineage, seed the new tracker's replay state from the existing lineage (same cache_affinity) whose last original history shares the longest leading run of canonical-equal messages with the request, truncated to that run:

• _last_original_messages = donor_orig[:k], _last_forwarded_messages = donor_fwd[:k]
• _cached_message_count = min(donor count, k); _cached_token_count from the donor if k covers its frozen count, else estimated from donor_fwd[:k]
• require k >= 8 and len(donor_fwd) == len(donor_orig) (the same 1:1 precondition overlay_cached_prefix already checks)

The request then extends prev_orig as a plain message append, so the existing overlay_cached_prefix path replays the cached bytes without changes. Lineages are not merged (only the replay state is copied), so parallel fan-outs still stay separate, and a shared prefix has identical cached bytes for each of them.

I have this running locally as a ~60-line patch in prefix_tracker.py behind an env switch, with tests for rewind, compaction, affinity, short-overlap, non-1:1 donor, and the disable switch. Happy to open a PR if the approach looks right.