Skip to content

Implement chained block hashing and count the prefix-cache hit tokens for a new prompt

mediumPremium edge casesimplement cache_hit_tokens

Before you code

The same token block follows two different prefixes. Predict whether a reusable cache key can ignore the parent prefix.

Review the prerequisite concept

The concept page shows its own access level. The statement and visible tests below are free.

A prefix cache keys every full block of a prompt by a hash that chains its parent's hash, so a matching hash means the whole prefix up to that block matched. Write both halves.

BLOCK = 16
block_hashes(tokens, extra=None) -> list of hashes, one per FULL block
  hash of block i = sha256(pickle((parent hash, tuple of the block's token ids, extra)))
  the parent of block 0 is sha256(b"vllm-none-hash"); a partial tail block gets no hash
cache_hit_tokens(cache, tokens, extra=None) -> int
  cache is a set of hashes from earlier prompts
  walk the prompt's hashes from the start, stop at the first miss,
  and never count the block that holds the prompt's last token,
  because that token must run to produce the first output's logits

extra stands for everything besides token ids that changes the KV, such as a LoRA adapter, and goes into every block's key.

The visible tests cover a shared system prompt and a repeated prompt. The full suite adds the chain property, partial blocks, a different adapter, a prompt that is an exact multiple of the block size, a cache that is missing one early block, and short and empty prompts.

YOUR IMPLEMENTATION · PYTHON 3.14 + NUMPY

Visible tests run for everyone; the edge cases and the solution are Premium.

The visible tests
SYSTEM = list(range(1000))


def test_a_shared_system_prompt_hits_its_full_blocks(ns):
    a, b = SYSTEM + [7] * 200, SYSTEM + [9] * 200
    cache = set(ns["block_hashes"](a))
    got = ns["cache_hit_tokens"](cache, b)
    assert got == 992, f"1,000 shared tokens are 62 full blocks, 992 tokens; got {got}"


def test_a_repeated_prompt_recomputes_its_last_block(ns):
    a = SYSTEM + [7] * 200
    cache = set(ns["block_hashes"](a))
    got = ns["cache_hit_tokens"](cache, a)
    assert got == 1184, f"1,200 tokens are 75 blocks, the last recomputed: 1,184; got {got}"

The reasoning behind this component: the companion page.