The Same Prompt Changed After the Cache Saw Different Requests

Rolling agents repeatedly evict and append documents, breaking exact prefix caching and inviting selective reuse of old key-value states. The study found that persistent reuse could make an unchanged prompt produce different answers depending on the requests processed before it. At a matched 5% recomputation budget, recomputing document-aligned spans reduced order-driven answer variation from 69.0% under token top-k selection to 26.1%. It also improved fidelity to full prefill by 34.5 to 52.5 percentage points while both approaches retained roughly a 5.7-times median time-to-first-token speedup. The cache is not just an optimization when its history can alter the answer.