CODING CHALLENGE · N°55

KV-Cache Eviction (Attention Sinks)

Medium AIInferenceCaching

An LLM’s KV cache grows with every token, so long chats need a way to drop old entries without wrecking quality. StreamingLLM’s insight: keep the first few tokens (the "attention sinks") plus a sliding window of the most recent ones, and throw away the middle. Compute which tokens survive. Solve it in Python or TypeScript, with hidden tests.

The problem

A sequence has n tokens (indices 0…n-1) in the KV cache. Under a StreamingLLM eviction policy you keep the first sink tokens (attention sinks) and the most recent window tokens, evicting everything in between. Implement kv_keep(n, sink, window): return the sorted list of token indices that remain in the cache.

EXAMPLE 1

Input n = 10, sink = 2, window = 3

Output [0, 1, 7, 8, 9]

first 2 sinks + last 3 recent; tokens 2–6 are evicted

EXAMPLE 2

Input n = 5, sink = 2, window = 3

Output [0, 1, 2, 3, 4]

the sink and window together already cover everything

CONSTRAINTS

Keep indices 0 … sink-1 (attention sinks) and n-window … n-1 (the recent window).
The two ranges may overlap or cover the whole sequence — return each surviving index once, sorted.
Clamp to the sequence bounds: if sink or window exceed n, just keep what exists.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement kv_keep(n, sink, window): form the set of sink indices and the set of recent-window indices, union them, and return the sorted result.

HINTS — 4 IDEAS

Sink indices are range(min(sink, n)) — the first tokens, clamped to n.
Recent-window indices are range(max(0, n - window), n) — the last window tokens.
Union the two index sets so overlaps are not double-counted.
Return them sorted. The evicted tokens are exactly the middle ones present in neither set.

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

Track per-entry metadata (recency or frequency) alongside the cache, and when an insert pushes you over capacity, evict the victim the policy names — least-recently-used, least-frequently-used, or oldest. The trick is keeping the metadata update O(1) per access (a map plus a linked list for LRU, or frequency buckets for LFU) so you never scan to find the victim.

Complexity

Time O(1) per access and eviction with the right structure; space O(capacity).

Common mistakes

Scanning the whole cache to find the victim — O(n) per eviction defeats the purpose.
Updating recency only on writes, not reads — a read must also mark the entry as used.
Evicting before checking capacity, or off-by-one so the cache holds capacity + 1.

Where this shows up

Cache eviction is the same problem as OS page replacement and CPU cache lines — but it is now acute in LLM serving, where the attention KV cache is the memory bottleneck. Which sequences or blocks you evict or offload under pressure directly sets how many users fit on one GPU, which is why serving engines put real engineering into the policy.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

LLM Engineering Caching & Performance