KV cache eviction policy

A single session runs for hours: an agent transcript with interleaved tool output, growing without bound, decoded by a model you cannot retrain. You have a hard budget of B cache entries for that sequence, fixed at admission and not negotiable, because the same accelerator is holding many other sessions. Once an entry is dropped it is gone. Recomputation is available only if you price it explicitly inside your own cost model, and there is no offline pass over the transcript because the transcript does not exist yet. You do not know what the user will ask next, and a token that has drawn no attention for ten thousand steps can be the one the next question turns on.

Hand in an eviction policy plus one of the two arguments that make it a result rather than a heuristic. Either a competitive-style guarantee against an offline optimal that you define precisely, or an adversarial family of transcripts showing that every policy in a class you name, including your own, must drop a token the model later needed. Both require you to first define the cost of an eviction, which is where most attempts quietly fail: the phrase the model needed it has to become a measurable quantity that does not presuppose the counterfactual decode you cannot afford.

Also hand in the experiment that separates your policy from a recency window with extra steps. Retraining the model, learning a compressor on transcript data, and any lookahead over future turns are all off the table, since each converts the online problem into an offline one and the online problem is the question.

Ties break toward the sharper negative result over the more elaborate policy.