KV Cache Memory Budget and Eviction Policy
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:
- Computes the memory required per token in the KV cache (both keys and values across all layers and heads)
- Determines the maximum number of tokens that fit within the memory budget
- Simulates processing a sequence of tokens, evicting entries when the cache is full
Parameters:
num_layers: Number of transformer layersnum_heads: Number of attention heads per layerhead_dim: Dimension of each attention headdtype_bytes: Bytes per element (e.g., 2 for FP16)memory_budget_bytes: Total memory budget in bytes for the KV cachetoken_ids: List of integer token IDs arriving sequentiallytoken_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)
- max_tokens = 64 // 16 = 4
- Add tokens 10, 20, 30, 40 -> cache is full [10, 20, 30, 40]
- Token 50 arrives: cache full, FIFO evicts oldest (10). Cache becomes [20, 30, 40, 50]
- Token 60 arrives: cache full, FIFO evicts oldest (20). Cache becomes [30, 40, 50, 60]
- 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
- Estimating KV-Cache Memory and Shrinking ItLLMs & GenAIMedium
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium