KV Cache Admission and Eviction: Control Long Sessions and Priorities Before GPU Memory Is Exhausted

KV Cache retains the attention keys and values of previous tokens in GPU memory, avoiding repeated computation during decoding, but it also makes every active sequence a continuously growing resource commitment. If a service waits until GPU memory is actually exhausted before handling OOM, a single extremely long session can cause short requests in the same batch to fail as well; if everything is simply first come, first served, low-priority offline jobs will fill the interactive pool. Reliable control must estimate, reserve, and enforce limits before requests enter the execution queue.

Calculate the Worst-Case Commitment Before Admission

At minimum, estimates should use the number of model layers, number of KV heads, head dimension, cache data type, input length, and permitted output limit. The theoretical byte count is a starting point, but actual runtimes also involve block-size rounding, page tables, alignment, tensor parallelism, replica workspaces, and fragmentation. The platform should benchmark the target model and hardware to calibrate a bytesPerToken value and retain a safety factor; it must not treat all "remaining GPU memory" after loading model weights as sellable capacity.

When a request arrives, the server performs its own encoding to determine the input token count, checks whether input + max_new_tokens exceeds the model and tenant limits, and then estimates the required KV blocks. If the client does not provide an output limit, use a conservative default rather than assuming the user will stop soon. Admission control returns one of three explicit outcomes: execute immediately, enter a queue with a deadline, or reject due to quota or capacity. Unbounded queuing merely replaces OOM with timeouts.

kvPoolGiB: 52
blockTokens: 16
hardWatermark: 0.92
admissionWatermark: 0.82
interactiveReserve: 0.25
tenantMaxShare: 0.15
queueDeadlineMs: 8000
maxNewTokensDefault: 1024

These values must be tied to the model digest, runtime version, and GPU SKU. Rebenchmark whenever the model architecture or cache dtype changes; reusing an old per-token estimate creates false headroom. GPU Inference Capacity Planning covers the inference pool's total capacity, while this policy further determines whether an individual request should occupy the KV blocks within it.

Quotas Must Constrain Sequences as They Grow

QPS cannot represent KV pressure. For each tenant, simultaneously limit reserved tokens, active sequences, maximum context length, and cumulative GPU time, while accounting for both input already consumed and the remaining output allowance. Interactive, batch, and system-critical traffic should use separate budgets; high priority may only be assigned by a trusted server-side identity. For more complete tenant billing and atomic quotas, see AI Platform Tenant Quota Isolation.

The scheduler must also revise the commitment at every decoding step: when a request completes normally or is canceled, release its blocks immediately; as output approaches its limit, reduce the remaining reservation accordingly; when the connection closes, propagate the cancellation signal rather than continuing to generate to the maximum length. Queuing metrics should include at least the number waiting by priority, estimated wait time, rejected tokens, reserved and used blocks, fragmentation rate, and release latency after cancellation.

Prefix sharing can save GPU memory, but it must not cross security boundaries. The sharing key includes the model, tokenizer, adapter, chat template, and exact token prefix; for private prompts, it must also include the tenant and permission version. Even when their text is identical, different tenants may share only when the data is explicitly public and the policy permits it. Application result caching has different semantics from KV Cache. The version-key principles in Prompt Cache Design can be reused, but semantic similarity must never be treated as an identical KV prefix.

Eviction Should Account for Recovery Cost

Once the reclamation watermark is reached, do not evict active sequences at random. Candidate ranking should consider at least priority, deadline, time already spent waiting, remaining output, the cost of repeating prefill, the extent of the tenant's excess usage, recoverability, and the reference count of any shared prefix. Prefer reclaiming replayable offline jobs and requests that exceed a tenant's soft quota but have not yet started; preempt interactive sessions that are already streaming output to users only when the system's survival is threatened.

For runtimes that support preemption and recomputation, the state machine should clearly distinguish waiting, running, preempted, recomputing, and finished. Preserve the same request's GPU time, recomputation count, and deadline across states to prevent it from returning to the front of the queue after preemption and consuming resources indefinitely. Shared prefix blocks can only be released when their reference count reaches zero, or sequences that are still running will be corrupted.

A pressure policy might stop accepting low-priority long requests once utilization reaches 82%, pause batch prefill at 88%, and preempt recoverable jobs at 92%; no tenant may occupy more than 15% of the pool. However, the watermarks must leave enough room to absorb at least one maximum scheduling cycle of growth, and they must be calibrated with genuinely long outputs. Kubernetes priority and preemption concepts can serve as references, but actual KV decisions must still be made by an inference scheduler that understands the token lifecycle.

Prove the Policy with Failure Drills

The replay workload should include at least short question answering, 32K long inputs, long outputs, shared prefixes, cancellation storms, single-tenant bursts, and mixed batch jobs. Gradually increase load until rejections occur, verifying that the process does not OOM, critical traffic still meets its SLO, low-priority requests receive explicit errors, and GPU memory usage falls back. Then deliberately kill a worker and confirm that unfinished requests do not duplicate stale reservations on another replica.

Deployment gates can require zero OOMs during the stress window, release of reserved blocks within two seconds at P99 after cancellation, P95 time to first token of no more than 900 ms for critical interactive traffic, no tenant's actual share exceeding its hard limit, and an eventual completion rate above 99% for preempted jobs. When sharing GPUs with LLM Batch Inference, also verify that the offline queue pauses during peak periods and resumes during off-peak periods without causing starvation.

If the new policy causes tail latency or false rejections, roll back to the previous scheduling configuration digest while retaining a lower global admission watermark; do not disable admission control and return to unlimited acceptance. After rollback, review request lengths, reservation errors, and eviction reasons to determine whether the cause was an estimation error, a priority rule, or a runtime release defect. Reliable KV Cache management ultimately produces predictable rejection and degradation, not process restarts after intermittent OOMs.

Further Reading

• GPU Inference Capacity Planning
• AI Platform Tenant Quota Isolation
• Prompt Cache Design
• LLM Batch Inference