Overview

Design an eviction policy for an LLM serving prefix cache, and compete on how much prefill compute it saves.

In LLM serving, the KV cache for a shared prompt prefix can be reused across requests instead of recomputed. Whether that reuse actually materialises is a cache-management question: memory is finite, prefixes compete for it, and the policy deciding what to keep sets how much prefill work the system avoids. This competition asks you to write that policy and measure it against everyone else's on a common set of traces.

Worth 10% of the course grade. Runs through Part III: opens Nov 19, closes Dec 3, 11:59pm. You may work individually or in pairs.

Why this is not an ordinary cache

If you have implemented LRU before, the instinct transfers but the problem does not. Four differences make prefix caching its own thing, and the policies that win will be the ones that exploit them:

Entries form a tree, not a flat set. Cached blocks are keyed by prompt prefix, so they share ancestors. Evicting an interior node invalidates everything beneath it. A policy that evicts by per-entry recency alone will repeatedly destroy subtrees it was about to need.
Hits are partial. A request does not simply hit or miss — it matches some prefix of length k and computes the rest. The quantity you are maximising is a fraction of a request, not a count of requests.
Entries have different sizes and different values. A cached block's memory cost scales with its token count, and so does the compute it saves. A long system prompt shared by a thousand requests is worth vastly more per byte than a long one-off document.
Reuse has structure you can predict. Shared system prompts, few-shot blocks, and multi-turn conversations each generate a different reuse pattern. Policies that model that structure tend to beat policies that only look at recency.

The consequence: plain hit ratio is the wrong objective here, which is why it is not the metric below. Optimising for it will actively mislead you — you can raise hit ratio by keeping many small cheap prefixes while the expensive ones get recomputed every time.

The Task

You are given a trace of serving requests, each with a token sequence and an arrival order, and a fixed memory budget in KV blocks. On each request the harness reports the longest cached prefix; your policy decides what to admit and what to evict.

Metric

Submissions are scored on prefill token savings: the fraction of prompt tokens that were served from cache rather than recomputed, at a fixed memory budget.

Why this metric

It is proportional to the prefill FLOPs and the time-to-first-token you actually avoid, which is the thing a serving operator is buying with that memory. Request-level hit ratio is not.

The leaderboard reports this across several memory budgets and several workloads. A policy that wins at one budget and collapses at another is worse than one that is consistently good, and the scoring reflects that: your rank comes from the mean savings across every (workload, budget) pair, not your best result.

Baselines to beat

LRU over cache blocks — the naive baseline.
Tree-aware LRU, roughly what production radix-tree prefix caches do today. This is the one that matters; beating plain LRU is not an achievement.
Belady-style offline oracle, computed by the staff with full knowledge of the future. You cannot beat it. The gap between you and it is the interesting number, and reporting that gap honestly is part of the write-up.

Rules

Online only. Your policy sees each request when it arrives and never sees the future. Reading ahead in the trace, in any form, is disqualifying.
No trace fingerprinting. Detecting a specific evaluation trace and switching strategy is not a cache policy. Held-out traces are used for the final standings precisely to make this pointless.
One policy, not a portfolio. You submit a single algorithm. Ensembles that carry a collection of sub-policies and pick among them per test case are not permitted — whether the selection is made by recognising the workload, by matching trace statistics against a lookup table, or by branching on which evaluation trace is running. The same goes for constants: your parameters may not be indexed by test case. Tuning one policy per trace is not designing a cache policy, it is overfitting the leaderboard.

What is allowed, and encouraged: online adaptation driven by what your cache is observing right now — measured reuse distances, recent hit rate, current memory pressure. A policy that reweights its own behaviour from live signals is a single policy, not an ensemble; ARC and LeCaR are the classic examples and this is a genuinely interesting direction. The test to apply to your own design: would it behave sensibly on a workload nobody has shown it, including one invented after you submitted? If yes, it is a policy. If it needs to know which trace it is on, it is not.
Bounded metadata. Your bookkeeping must be small relative to the cache itself and must not grow without bound. If you are unsure whether your structure qualifies, ask.
Deterministic. Same trace and same budget must produce the same result. Seed any randomness and report the seed.
Time limit. A submission that exceeds the per-trace time limit does not score. An eviction policy too slow to run is not a solution.
AI tools are allowed, under the usual disclosure requirement. You will be asked to explain your policy, so make sure you understand whatever you submit.

How the 10% is earned

Most of the credit is for doing the work well, not for winning. Ranking matters, but it is the smallest component — a thoughtful policy that lands mid-table and is honestly analysed scores well.

Component	Weight
A correct, working policy that beats tree-aware LRU	5%
Write-up: the intuition, what you tried, what failed, and your gap to the oracle	3%
Leaderboard standing on held-out traces	2%

On the write-up: a policy that did not work, with a clear account of why, earns nearly full write-up credit. The failed attempts are usually the interesting part — and they are what makes this worth doing rather than a leaderboard-grinding exercise.

Get Started

Read this page in full, especially why this is not an ordinary cache.
Review the libCacheSim plugin interface, which the harness follows.
Implement your eviction policy against the provided prefix-cache framework.
Test locally on the sample traces, then submit for evaluation on the held-out set.
Iterate. The leaderboard updates on each submission; the standings that count are the final ones.

Harness, sample traces, and submission link will be posted here when the competition opens on Nov 19.

Background Reading

The Oct 27 prefix cache session covers this material; these are the papers worth reading before you start.

SGLang / RadixAttention — the radix-tree prefix cache your baseline approximates.
vLLM / PagedAttention — block-level KV memory management.
Mooncake — a KV-cache-centric serving architecture, for what this looks like at scale.
Parrot — where the reuse structure comes from when the workload is agents rather than chat.
libCacheSim — the simulator and its eviction-algorithm library.