KV Cache Memory Budget and Eviction Policy

MediumML Coding

Problem statement

Implement a KV (Key-Value) cache manager for transformer inference that computes memory requirements and simulates cache eviction when a memory budget is exceeded.

During autoregressive generation, transformers store previously computed key and value tensors in a KV cache to avoid redundant computation. However, with long sequences, this cache can consume significant GPU memory. When the cache exceeds a memory budget, an eviction policy determines which entries to remove.

Write a function kv_cache_manager(num_layers, num_heads, head_dim, dtype_bytes, memory_budget_bytes, token_ids, token_scores, eviction_policy, num_protected) that:

  1. Computes the memory required per token in the KV cache (both keys and values across all layers and heads)
  2. Determines the maximum number of tokens that fit within the memory budget
  3. Simulates processing a sequence of tokens, evicting entries when the cache is full

Parameters:

  • num_layers: Number of transformer layers
  • num_heads: Number of attention heads per layer
  • head_dim: Dimension of each attention head
  • dtype_bytes: Bytes per element (e.g., 2 for FP16)
  • memory_budget_bytes: Total memory budget in bytes for the KV cache
  • token_ids: List of integer token IDs arriving sequentially
  • token_scores: List of floats representing each token's importance score (same length as token_ids)
  • eviction_policy: Either 'fifo' or 'score'
  • num_protected: Number of initial tokens that cannot be evicted (e.g., system prompt tokens)

Eviction policies:

  • 'fifo': Evict the oldest non-protected token in the cache
  • 'score': Evict the non-protected token with the lowest importance score (break ties by evicting the oldest)

When the cache is full and a new token arrives, perform eviction first, then add the new token. If all tokens are protected and the cache is full, do not add the new token.

Return a dictionary with:

  • 'bytes_per_token': Memory per token in the KV cache (int)
  • 'max_tokens': Maximum tokens fitting in the budget (int)
  • 'final_cache': List of token IDs remaining in cache (in insertion order)
  • 'evicted_tokens': List of evicted token IDs (in order of eviction)
  • 'num_evictions': Total number of evictions (int)

Example

Input:

num_layers=1, num_heads=1, head_dim=4, dtype_bytes=2, memory_budget_bytes=64, token_ids=[10, 20, 30, 40, 50, 60], token_scores=[0.5, 0.3, 0.8, 0.1, 0.9, 0.2], eviction_policy='fifo', num_protected=0

Output:

{'bytes_per_token': 16, 'max_tokens': 4, 'final_cache': [30, 40, 50, 60], 'evicted_tokens': [10, 20], 'num_evictions': 2}

Reasoning: 1. bytes_per_token = 2 1 1 4 2 = 16 bytes (K and V for each layer/head)

  1. max_tokens = 64 // 16 = 4
  2. Add tokens 10, 20, 30, 40 -> cache is full [10, 20, 30, 40]
  3. Token 50 arrives: cache full, FIFO evicts oldest (10). Cache becomes [20, 30, 40, 50]
  4. Token 60 arrives: cache full, FIFO evicts oldest (20). Cache becomes [30, 40, 50, 60]
  5. Final cache: [30, 40, 50, 60], evicted: [10, 20]
Show hint

How many separate tensors does each token contribute per head and per layer, and how large is each one in bytes?

Relevant roles: LLM Engineer, MLOps Engineer, ML Engineer, AI Engineer and AI Architect.

Related free problems