Disaggregated LLM KV-Cache Storage Requires Coordination-Free Consistency Abstractions

Abstract

An available KV-cache hit is not always a safe decoder hit. A miss loses reuse; an invalid commit can silently perturb decoder output. In a disaggregated cache, a replica may know where a block was placed, but retirement, allocation reuse, and reader lifetimes evolve elsewhere. We use the CALM monotonicity criterion to ask which KV-cache metadata effects actually require a controller-wide order. Our source-guided audit examines metadata effects of 47 operations from LMCache, Mooncake, vLLM-style cache management, and token-selective cache management under a declared abstraction. Eleven effects are monotone in isolation; other effects, which retract facts, commit absence or uniqueness, or threshold mutable state, still require coordination. Guided by that criterion, we design a tagged observed-remove catalog for repeated placement admission and retirement under delayed, duplicated, and reordered messages. Independent of catalog convergence, root-down traversal makes an incomplete prefix fail closed as a shorter hit or miss. A separate valid-hit contract then governs the transition from catalog candidate to (decoder) reuse, by checking semantic and positional identity, sealed physical generation, payload integrity, and reader protection. We evaluate the design with a constructed positional-rewrite fault injection, a four-replica catalog prototype, and bounded TLA+ model checking. The model checker finds no committed-hit violation under the contract, while an unfenced rewrite can perturb decoder output. The resulting design separates coordination-free metadata dissemination from the object-lifecycle coordination required when a decoder commits a hit.