SWA prefix cache: cross-request reuse lost entirely when a request diverges more than ~_SWA_RETAIN_GAP tokens before a cached prompt's end (fan-out over a shared system prompt never hits)

[salekseev]

Summary

On a sliding-window model (--cache-type radix → swa_radix), cross-request prefix reuse is
lost entirely when a request diverges more than a handful of tokens before the end of a
previously-served prompt. Appending to a conversation reuses correctly; serving two
conversations that share a long system prompt does not — the second pays a full prefill of
the shared prefix.

Measured on gemma-4-26B-A4B (Q4_0 GGUF, window 1024, 25 SWA / 5 full layers), with a ~7.7k
token shared prefix:

pattern	2nd request	wall
append (history + assistant reply + new user turn)	cached_tokens 7770 / 7793	8.59 s → 0.60 s
same system prompt, different user message	cached_tokens 0 / 7780	8.61 s → 8.53 s

It is not a reporting artifact: at a 21.7k-token shared prefix the reusing case goes
25.71 s → 0.62 s (41x), while the non-reusing case stays 25.78 s → 25.85 s.

The boundary is sharp

Same prefix, tails that diverge at a controlled distance from the end (differing token, then
N identical tokens after it):

N= 3 -> 2nd cached  1873 of  1886  REUSED
N= 4 -> 2nd cached  1874 of  1888  REUSED
N= 5 -> 2nd cached  1875 of  1890  REUSED
N= 6 -> 2nd cached  1876 of  1892  REUSED
N= 7 -> 2nd cached     0 of  1894  NO REUSE
N= 8 -> 2nd cached     0 of  1896  NO REUSE

Independent of max_tokens (1 / 8 / 64 all behave the same) and of prompt length — a 21.7k
prefix reuses at N=4 and fails at N=12, and a 1.9k prefix behaves identically. So the trigger
is the distance from the previous prompt's end to the divergence point, not size, pressure,
or sampling parameters.

Likely cause

scheduler/cache.py, the finished branch of _cache_req_swa, eagerly discards the SWA
currency of the prompt head at finish time:

prompt_len = align_down(req.max_device_len - req.output_len, self.page_size)
if prompt_len > 0:
    keep_from = align_down(
        max(prompt_len - self.sliding_window_size - _SWA_RETAIN_GAP, 0), self.page_size)
    if keep_from > 0:
        self._free_swa(
            self.prefix_cache.trim_head_swa(req.input_ids[:prompt_len], keep_from))
    self.prefix_cache.match_prefix(req.input_ids[:prompt_len])

with _SWA_RETAIN_GAP = 16 (scheduler/cache.py:29). Only [keep_from, prompt_len) keeps
windowed KV. A later request that matches to position P needs SWA KV for [P-window, P),
which requires keep_from <= P-window, i.e. P >= prompt_len - _SWA_RETAIN_GAP. Any
divergence further back than that leaves the match with no live windowed KV, and the whole
shared prefix is re-prefilled.

The comment states the intent — "a follow-up turn diverges at the prompt end when the client
drops reasoning; a cut there only needs the trailing window live" — which holds for that case
and for pure append. The case it does not cover is fan-out: many requests sharing a system
prompt and tool schemas, each with its own user message. There the divergence sits a whole
user message (tens to hundreds of tokens) before the previous prompt's end, so every request
re-prefills the shared prefix.

I could not fully reconcile the measured cliff (~7 tokens of divergent suffix) with
_SWA_RETAIN_GAP = 16 — page alignment and how much of the first prompt is actually inserted
both feed in — so treat the mechanism as the strong hypothesis and the measurements as the
solid part.

Reproduction

import json, time, urllib.request
URL = "http://127.0.0.1:1919/v1/chat/completions"
F = ("Operational note: the routing network selects a small subset of experts per token, "
     "so the working set touched during one decode step is far smaller than the count. ")

def ask(msgs):
    b = {"model": "<served-name>", "messages": msgs, "max_tokens": 16}
    r = urllib.request.Request(URL, data=json.dumps(b).encode(),
                               headers={"Content-Type": "application/json"}, method="POST")
    t0 = time.perf_counter()
    with urllib.request.urlopen(r, timeout=600) as f:
        d = json.load(f)
    u = d.get("usage") or {}
    return (u.get("prompt_tokens"), (u.get("prompt_tokens_details") or {}).get("cached_tokens", 0),
            time.perf_counter() - t0)

pre = "Notes.\n\n" + F * 250          # ~7.7k tokens
sysmsg = {"role": "system", "content": pre}
print(ask([sysmsg, {"role": "user", "content": "What is the first bottleneck you would investigate here?"}]))
print(ask([sysmsg, {"role": "user", "content": "Which hardware property matters most for this workload?"}]))

Second line reports cached_tokens = 0 and the same wall time as the first. Requires
--enable-cache-report.

Environment

• FreeToken 0.1.2 (PyPI wheel + freetoken_kernel_cache-0.1.2+cu130)
• RTX 4080 SUPER (sm_89, 16 GB), driver 610.57.04, CUDA UMD 13.3
• unsloth/gemma-4-26B-A4B-it-qat-GGUF (Q4_0), --moe-backend → offload, attention → triton
• Reproduces at --kv-cache-dtype auto (bf16, 32k pool) and with an 8-bit KV pool at 131k,
  and at both --swa-full-tokens-ratio 0.2 and 0.07 — so it is independent of KV dtype,
  pool size and window-pool ratio.
• The tree carries fix(kernel): launch GGUF MoE GEMV token axis on grid.x, not grid.z #185 (kernel launch geometry), feat(kvcache): 8-bit KV cache (q8_0 / fp8_e4m3) behind --kv-cache-dtype #103 (--kv-cache-dtype) and feat(server): expose swa_full_tokens_ratio as a startup CLI flag #109
  (--swa-full-tokens-ratio) plus a local fix for the gemma4 GGUF embedding quant type
  (gemma4 GGUF: embedding quant type hardcoded to Q6_K, so a Q4_0-embedding GGUF fails to load with a bare AssertionError #188). None touch scheduler/cache.py or kvcache/swa_radix_cache.py, and the behaviour
  reproduces with the quantized KV path inactive.

Why it matters

Fan-out over a shared system prompt is the dominant pattern for agent and tool-calling
workloads, and it is exactly the case that benefits most from prefix caching. On this box a
7.7k shared prefix costs 8.5 s of avoidable prefill per request, and a 45k one costs
25-50 s — while the same engine demonstrably serves the reusing case in 0.6 s.

Possible directions, in rough order of conservatism: make the head trim pressure-driven rather
than unconditional at finish (only reclaim when evict_swa actually needs slots); or keep the
trim but size the retained region by a configurable divergence budget rather than a 16-token
constant; or retain the head as tombstoned-but-revivable so a longer-divergence match can
reconcile it the way in-window tombstones already are.

Happy to test a patch on this hardware.