Metal: paged-KV prefill is 4.43x slower than contiguous KV at 32K

[chaoshou-coder]

TL;DR

• On BaseRT 0.2.2 / Apple M5 Pro, paged and contiguous KV are nearly equal at
  1K tokens, but paged KV becomes 4.43x slower at 32K.
• The regression reproduces with -r 1; it is not caused by benchmark state
  accumulating across repetitions.
• Both sides use the same model file and actual F16/F16 KV precision. The only
  benchmark difference is --paged-kv.
• This is a direct engine benchmark (-n 0), independent of HTTP, Pi, chat
  templates, sampling, and decode.
• --prefix-cache and --continuous-batching imply paged KV, so this directly
  affects long-context serving and agent workloads.

Environment

BaseRT:              0.2.2
Release marker:      v0.2.2
OS:                  macOS 26.5.2 (25F84)
Machine:             MacBook Pro (Mac17,9)
Chip:                Apple M5 Pro, 18 CPU cores
Unified memory:      48 GB
BASERT_KV_BITS:      unset

Model provenance

This is a locally converted model, not a pre-converted BaseCompute catalog
bundle.

Field	Value
Official source	https://huggingface.co/Qwen/Qwen-AgentWorld-35B-A3B
HF revision	60d2b0434a53d2e62a7c00a489586815d94ebffb
Source format	BF16 safetensors
Conversion	Local basert convert, custom Q4-mix profile
.base size	20,276,645,888 bytes
Runtime architecture	qwen35moe
Layers	40: 10 full-attention + 30 linear-attention
Attention shape	16 Q heads, 2 KV heads, head_dim 256
MoE shape	256 experts, top-8 per token
Trained context	262,144 tokens

The same exact .base file is used for every A/B run, so conversion cannot
explain the contiguous-vs-paged difference.

basert inspect

arch:          qwen35moe
quant_scheme:  BaseQ4
min_hw:        apple_m1
base_rt:       0.2.0
created:       1786461501
flags:         HeaderFlags(QUANTIZED | HAS_MOE)
n_layers:      40
n_tensors:     693
signed:        false
weights bytes: 20265235456
dtypes:
  BaseQ4    331 tensors   19195822080 bytes
  Bf16       80 tensors      42106880 bytes
  F16       222 tensors    1027298816 bytes
  F32        60 tensors          7680 bytes
n_slots:       0

Reproduction

MODEL=/path/to/Qwen-AgentWorld-35B-A3B.base

for P in 1024 2048 4096 8192 16384 32768; do
  basert bench "$MODEL" -p "$P" -n 0 -r 1
  basert bench "$MODEL" -p "$P" -n 0 -r 1 --paged-kv
done

Test controls:

Control	Value
Generated tokens	0 — isolates prefill
Repetitions	1 — rules out repetition-state accumulation
Model file	Identical SHA-256 for both paths
KV dtype	F16/F16 for both paths, confirmed at cache constructors
KV environment override	None
Only changed option	--paged-kv

Results

Single-repetition length sweep

Prompt	Contiguous KV	Paged KV	Paged slowdown	Contiguous time	Paged time
1,024	2,787.55 tok/s	2,558.85 tok/s	1.09x	0.37s	0.40s
2,048	3,027.36 tok/s	2,533.12 tok/s	1.20x	0.68s	0.81s
4,096	3,106.25 tok/s	2,115.53 tok/s	1.47x	1.32s	1.94s
8,192	2,998.39 tok/s	1,526.00 tok/s	1.96x	2.73s	5.37s
16,384	2,579.87 tok/s	951.43 tok/s	2.71x	6.35s	17.22s
32,768	2,333.39 tok/s	526.71 tok/s	4.43x	14.04s	62.21s

At 32K, paged KV adds 48.17 seconds and loses 77.4% throughput.

Ten-repetition confirmation at 32,000 tokens

Mode	Result	Approx. time	Relative
Contiguous	2149.71 +/- 68.47 tok/s	14.89s	1.00x
Paged	476.80 +/- 23.77 tok/s	67.11s	4.51x slower

The similar ratio for -r 1 and -r 10 rules out a benchmark reset leak as the
primary cause. Tests at 500 and 512 tokens are also similar, so this is not a
power-of-two/alignment effect.

Scaling characteristic

Observation	Result
Paged time/token vs prompt length	Nearly linear
Fit	paged_us_per_token ~= 291 + 0.0483 * prompt_tokens
Fit quality	R^2 ~= 0.997
Contiguous degradation over 1K→32K	Modest
Paged degradation over 1K→32K	Severe

The data is consistent with paged prefill scanning/gathering an increasing
number of KV blocks per query while missing the optimized contiguous long-
prefill path. This is a hypothesis; the direct A/B reproduction does not depend
on it.

Expected vs actual

	Expected	Actual
Short prompt	Small paged overhead	Confirmed
Long prompt	Bounded/modest paged overhead	4.43x slower at 32K
Prefix-cache tradeoff	Cache hits without catastrophic miss cost	Cold/miss prefill loses 77% throughput
Continuous batching	Better serving throughput under load	Implies the same slow paged path

A possible implementation strategy would be an optimized paged-prefill kernel,
or contiguous staging for bulk prefill followed by publishing completed KV
pages.

Serving impact

Workload event	Consequence
Cold long prompt	Full paged penalty
Prefix-cache miss	Full paged penalty
Divergent branch	Large suffix can hit the slow path
Context compaction	New prefix may require substantial prefill
Large tool result	Thousands of new suffix tokens at a long cache position
--prefix-cache	Implies --paged-kv
--continuous-batching	Implies --paged-kv

Possibly related: non-zero-position continuation prefill

A real serial serving run without paged KV automatically reused the previous
slot prefix:

request 1: prompt=90204 completion=874 prefill=1168 t/s decode=40 t/s
request 2: prompt=922   completion=966 prefill=69 t/s   decode=41 t/s

Fact	Interpretation
Second HTTP request contained the complete history	Client is stateless/full-context
Server logged only 922 prompt tokens	Slot-local common-prefix KV reuse worked
Decode stayed 40→41 tok/s	No sudden global engine slowdown
922-token continuation fell to 69 tok/s	Non-zero-cache-position prefill may also miss the fast bulk path

This observation may share an implementation cause, but it is not required for
the clean basert bench --paged-kv reproduction above.

Related public report demonstrating automatic non-paged slot reuse:
#26

I can provide additional cross-model sweeps and test a diagnostic build.