Predicting Output Preservation and First Divergence under KV-Cache Compression

Key-Value (KV) cache compression is usually evaluated by how much cache state is removed or distorted, but cache distortion alone does not determine whether the model output is preserved. Under deterministic greedy decoding, we study when compression preserves the dense-model token and when compressed generation first diverges. Our key observation is that output preservation depends not only on perturbation magnitude, but also on how the compression-induced change acts relative to the decision margin. Based on this observation, we derive an exact per-step characterization of output preservation through output crossing. We then introduce the Output Crossing Predictor (OCP), a first-order framework that predicts whether a candidate compression will cause output crossing before compressed logits are observed. OCP combines the local cache-read perturbation with the local sensitivity of the dense model. Repeated across decoding steps, the same prediction estimates the first divergence time. Experiments across multiple models and compression operators show that OCP predicts output crossing and first divergence, while the compression boundary becomes more conservative as generation length increases. These results shift KV-cache compression from measuring cache distortion to predicting output preservation and first divergence.