kvshare

Trace-driven measurement of how much prefill work in agentic workloads is redundant — the feasibility number for building RadixAttention-style cross-request prefix caching into M*.

CPU-only: real tokenizers, no weights, no GPU, no changes to ./mstar. Results and methodology: WRITEUP.md.

Result

On 500 public mini-swe-agent sessions on SWE-bench Verified (25,494 requests, 401.8M prefill tokens):

	mini-swe-agent	τ-bench retail
redundant prefill tokens, page 16	97.90%	92.97%
at page 128 — M*'s existing page size	97.54%	91.35%
prefill FLOPs saved	97.78%	92.67%

Two findings that matter more than the headline:

• Pool size is a cliff, not a slope. 1.99% at 64k tokens → 61.8% at 128k → 97.9% at 256k. The pool must exceed concurrency × final context or almost none of it is collectable.
• History-editing agents destroy it. Applying SWE-agent's LastNObservations(5) elision collapses prefix stability from 100% to 10.2%, and the eliding agent computes 7× more prefill than the append-only one despite sending 44% fewer tokens.

What this is not. A CPU trace simulation bounds the available redundancy; it does not measure a realized speedup. Tree maintenance on the critical path, memory contention with in-flight requests, and non-local pages under multi-node placement all discount it. Traces are Sonnet-4.5-generated and tokenized with a Qwen tokenizer, so ratios are more robust than absolute counts. See WRITEUP.md §7.

Attribution

Trace corpora are third-party and not redistributed here — scripts/fetch_traces.py downloads them from the original public sources (mini-swe-agent's SWE-bench Verified leaderboard submission; τ-bench's repository). Check their licenses before reuse.

What it does

1. Ingests multi-turn agent traces (final transcripts of append-only agents, or any JSONL of message lists — see scripts/fetch_traces.py for the two public sources used).
2. Reconstructs the per-turn request sequence: request t = messages before the t-th assistant message (kvshare/traces.py; exactness argument in the writeup).
3. Tokenizes every request independently through a real chat template (Qwen/Qwen2.5-7B-Instruct by default) — no string diffing, so template or BPE boundary effects are measured, not assumed.
4. Replays the requests through a radix tree over page-granular token sequences with refcount pinning + LRU leaf eviction (SGLang's policy), sweeping page size, pool size, and session concurrency.
5. Reports redundant/total prefill tokens, FLOPs saved (position-aware — cached prefixes are the cheap early positions), turn-depth breakdown, intra- vs cross-session sharing, and hit rate vs pool size.

Correctness constraint honored throughout: prefixes only, anchored at position 0. K vectors are cached post-RoPE (M* rotates K in place: mstar/utils/attention.py:255), so a shared token run in the middle of two sequences is not reusable — the radix tree cannot even express such a match (kvshare/radix.py, tests/test_radix.py).

Run it

uv venv .venv && uv pip install --python .venv/bin/python -e ".[dev,plot]"
.venv/bin/python -m pytest tests/ -q          # offline unit tests
.venv/bin/python -m kvshare demo              # offline synthetic smoke test

# data (both public, no auth)
.venv/bin/python scripts/fetch_traces.py mini-swe --out data/mini_swe_sonnet45.jsonl
.venv/bin/python scripts/fetch_traces.py tau-bench --out data/tau_retail.jsonl

# pipeline
.venv/bin/python -m kvshare tokenize --traces data/mini_swe_sonnet45.jsonl \
    --cache-dir cache/mini_swe
.venv/bin/python -m kvshare sweep  --cache-dir cache/mini_swe --out results/mini_swe.json
.venv/bin/python -m kvshare report --results results/mini_swe.json --out results/mini_swe.md
.venv/bin/python -m kvshare plots  --results results/mini_swe.json results/tau_retail.json \
    --labels "mini-swe-agent (SWE-bench)" "τ-bench retail" --out results/figs

--history-policy elide:5 at the tokenize step applies SWE-agent's LastNObservations elision before every reconstructed request — the measured counterexample showing history-editing agents destroy most prefix reuse.

Layout

path	what
kvshare/radix.py	position-anchored page trie, pin + LRU eviction
kvshare/traces.py	schema, validation, reconstruction, elision policy
kvshare/tokenization.py	chat-template rendering, independent tokenization, prefix-stability metric
kvshare/simulate.py	replay loop (admission, concurrency, page rounding, clamp)
kvshare/flops.py	position-aware prefill FLOPs + KV bytes (Qwen2.5-7B / Llama-3.1-8B/70B)
kvshare/report.py, kvshare/plots.py, kvshare/cli.py	aggregation, figures, CLI
scripts/fetch_traces.py	mini-swe-agent (S3) and τ-bench (GitHub) downloaders/normalizers