Hands-On Build Guide: Paged Attention KV-Cache with Sliding-Window Eviction in Pure Python

TL;DR — In this post you’ll build a pure‑Python paged attention KV‑cache with a sliding‑window eviction policy. The implementation mirrors the paging logic used in production LLM serving frameworks, giving you a tangible project that signals systems depth to hiring managers. By the end you’ll have runnable code, a test suite, and a clear roadmap to production‑grade extensions.

Portfolio projects that demonstrate real‑systems thinking stand out in hiring pipelines. A paged attention KV‑cache is a compact, focused implementation that touches memory management, eviction policies, and API design—all while staying lightweight enough to code in a single afternoon. This guide walks you through every step, from the high‑level architecture to running and testing the code locally, and finishes with concrete upgrades that turn the toy into a production‑ready component.

Why This Project Stands Out on a CV

Employers scanning CVs look for signals that you can operate at the intersection of code and infrastructure. A paged attention KV‑cache demonstrates:

Memory‑efficiency design – you explicitly manage fixed‑size pages and a sliding‑window eviction policy, mirroring the constraints of GPU‑bound LLM serving.
Algorithmic thinking – choosing an eviction strategy, handling overflow, and maintaining O(1) look‑ups shows you can trade off latency vs. capacity.
Production‑ready coding practices – type hints, small well‑scoped functions, and a minimal API surface that can be imported into larger pipelines.
Familiarity with LLM serving patterns – knowledge of paged attention (as used in vLLM, SGLang) is increasingly valued for AI‑focused engineering roles.

Roles that will flag this project positively include backend engineers building inference services, ML ops engineers optimizing resource usage, and systems engineers interested in low‑latency data pipelines. The project is small enough to finish quickly but rich enough to discuss in depth during technical interviews.

Architecture Overview

The cache is built around three core concepts:

Page – a fixed‑size container (e.g., 64 tokens) that holds a slice of key/value vectors together with a generation counter.
Page table – a dict mapping logical token indices to (page_id, offset) tuples, enabling O(1) address translation.
Sliding‑window eviction – a counter that tracks how many pages have been inserted; once the limit MAX_PAGES is reached, the oldest page is dropped before a new one is inserted.

+----------------+     +----------------+     +-------------------+
|   Token IDs    | --> |   Page Table   | --> |   KV Cache (pages)|
+----------------+     +----------------+     +-------------------+
        |                     |   ^                |
        |   eviction          |   |   sliding‑win   |
        +---------------------+   +------------------+

When a put(key, value) arrives, the system:

Computes page_id = key // PAGE_SIZE and offset = key % PAGE_SIZE.
Looks up page_id in the page table.
If the page exists, the KV pair is written at offset; otherwise a new page is allocated (evicting the oldest if the cache is full) and registered in the table.

This design decouples the logical token index from physical memory layout, exactly what production attention implementations do under the hood.

Building It Step by Step

Below are the numbered implementation steps. Each step includes a runnable Python snippet tagged as ```python.

Step 1 – Define the Page class

from __future__ import annotations
from dataclasses import dataclass
from typing import Optional

PAGE_SIZE = 64  # tokens per page, adjust for your use‑case

@dataclass
class Page:
    """A fixed‑size page holding key/value vectors."""
    id: int                     # unique page identifier
    kv: list[float]             # flat buffer of size PAGE_SIZE * dim
    offset: int = 0             # next free slot within the page
    generation: int = 0         # monotonic counter for eviction ordering

Step 2 – Create the PagedKVCache skeleton

class PagedKVCache:
    """Sliding‑window paged KV‑cache for attention scores."""

    def __init__(self, max_pages: int, dim: int):
        self.max_pages = max_pages          # hard limit on retained pages
        self.dim = dim                      # dimension of each key/value vector
        self.pages: dict[int, Page] = {}    # page_id -> Page
        self.page_table: dict[int, tuple[int, int]] = {}  # token_idx -> (page_id, offset)
        self.next_page_id = 0
        self.insert_counter = 0             # used for sliding‑window eviction

Step 3 – Insert logic with eviction

    def put(self, token_idx: int, key: list[float], value: list[float]) -> None:
        """Store a key/value pair at the given logical token index."""
        # 1️⃣ compute page & offset
        page_id = token_idx // PAGE_SIZE
        offset = (token_idx % PAGE_SIZE) * self.dim

        # 2️⃣ ensure the page exists (allocate or evict)
        if page_id not in self.pages:
            # evict oldest if we are at capacity
            if len(self.pages) >= self.max_pages:
                self._evict_oldest()
            # create a fresh page
            new_page = Page(id=self.next_page_id, kv=[0.0] * (PAGE_SIZE * self.dim))
            self.pages[new_page.id] = new_page
            self.next_page_id += 1

        page = self.pages[page_id]

        # 3️⃣ write key/value at the computed offset
        # (simple in‑place assignment; real implementations would copy tensors)
        start = offset
        end = start + self.dim
        page.kv[start:end] = key + value  # concatenated for demo purposes

        # 4️⃣ update page table and insertion ordering
        self.page_table[token_idx] = (page.id, page.offset)
        page.offset = (page.offset + self.dim) % (PAGE_SIZE * self.dim)
        self.insert_counter += 1
        # keep sliding‑window: pages older than max_pages are discarded on next overflow

Step 4 – Lookup logic

    def get(self, token_idx: int) -> tuple[list[float], list[float]] | None:
        """Retrieve the key/value pair for a logical token index."""
        if token_idx not in self.page_table:
            return None
        page_id, offset = self.page_table[token_idx]
        page = self.pages[page_id]
        start = offset
        end = start + self.dim
        # return slices; in a real system you’d split key vs. value
        raw = page.kv[start:end]
        # dummy split – first half = key, second half = value
        half = len(raw) // 2
        return raw[:half], raw[half:]

Step 5 – Minimal driver script

if __name__ == "__main__":
    cache = PagedKVCache(max_pages=4, dim=8)   # tiny cache for demo
    # Insert a few tokens
    for i in range(10):
        key = [float(i * j) for j in range(8)]
        value = [float(i + j) for j in range(8)]
        cache.put(i, key, value)
        print(f"put token {i}: page={cache.page_table.get(i)}")

    # Retrieve a couple
    for i in (0, 5, 9):
        kv = cache.get(i)
        print(f"get token {i}: {kv}")

Running python paged_cache.py should print insertion confirmations and the retrieved key/value pairs (or None for out‑of‑range indices). The eviction logic becomes visible when you set max_pages low and insert more than that many tokens.

Running and Testing It

Save the code above into a file named paged_cache.py.
Install a test runner (optional but recommended): pip install pytest.
Create a tiny test file test_paged_cache.py:

import pytest
from paged_cache import PagedKVCache

def test_basic_put_get():
    cache = PagedKVCache(max_pages=3, dim=4)
    for i in range(5):
        cache.put(i, [float(i)*j for j in range(4)], [float(i)+j for j in range(4)])
    assert cache.get(0) is not None
    assert cache.get(4) is not None
    assert cache.get(10) is None   # out of range

def test_eviction_keeps_recent():
    cache = PagedKVCache(max_pages=2, dim=2)
    # Insert 5 tokens; only the last 2 pages should survive
    for i in range(5):
        cache.put(i, [float(i), 0.0], [0.0, float(i)])
    # After evictions, token 3 and 4 should still be findable,
    # while token 0 might have been dropped.
    assert cache.get(3) is not None
    assert cache.get(4) is not None

Run the tests: pytest test_paged_cache.py -v. You should see all assertions pass, confirming that insertion, retrieval, and sliding‑window eviction work as expected.
Profile locally (optional): add import time; start = time.time(); ...; print("elapsed", time.time() - start) around the put/get calls to observe constant‑time behavior.

Extending It: Your Roadmap to Senior‑Level

Persistence with pickle or JSON – serialize self.pages to disk and reload on startup. Why it matters: enables checkpointing and resumes long‑running inference jobs without losing cached context.
Integration with a real LLM engine – plug the cache into vLLM or SGLang as a drop‑in replacement for their native paged attention. Why it matters: demonstrates you can bridge a toy implementation to industry‑standard serving frameworks.
Observability via Prometheus – expose cache_hits, cache_misses, and eviction_count as metrics. Why it matters: production services need quantitative feedback to tune page sizes and window lengths.
Fault‑tolerant page versioning – attach a CRC or hash to each page and validate on read. Why it matters: guards against memory corruption in long‑running processes or distributed deployments.
Horizontal sharding – split the cache across multiple processes or nodes, using a consistent‑hash ring to route token indices. Why it matters: scales serving capacity beyond a single machine, a common requirement for high‑throughput APIs.
Benchmarking suite – measure latency (µs per lookup) and throughput (lookups/sec) across varying PAGE_SIZE and max_pages values, then plot results with matplotlib. Why it matters: data‑driven tuning is essential when the cache sits on the critical path of an LLM serving pipeline.

Each upgrade moves the project from “educational toy” to a component you could plausibly discuss in a senior‑level engineering interview or contribute to an open‑source LLM serving project.

Key Takeaways

A paged KV‑cache with sliding‑window eviction captures the essential memory‑management patterns used in production LLM serving.
The implementation stays tiny (≈80 lines of core logic) yet is expressive enough to model real‑world constraints.
Type‑hinted, modular Python code makes the project importable into larger pipelines or test suites.
Concrete upgrades—persistence, observability, fault tolerance, and benchmarking—turn the toy into a production‑ready subsystem.
Building and testing this project signals to hiring managers that you understand both algorithmic design and systems‑level trade‑offs.

Why This Project Stands Out on a CV#

Architecture Overview#

Building It Step by Step#

Step 1 – Define the Page class#

Step 2 – Create the PagedKVCache skeleton#

Step 3 – Insert logic with eviction#

Step 4 – Lookup logic#

Step 5 – Minimal driver script#

Running and Testing It#

Extending It: Your Roadmap to Senior‑Level#

Key Takeaways#

Further Reading#