llama.cpp tries bitmaps for faster sparse KV cell lists

A llama.cpp contributor has floated a bitmap scheme for tracking which KV cache cells belong to each sequence, with early numbers aimed at batched decode on long, sparse contexts.

In unified KV layouts used for multi-sequence work, the runtime must keep ordered per-sequence cell lists so attention and eviction see the right rows. Rebuilding or copying those lists gets costly as the cache grows and sequences share or drop cells. The bitmap design stores one bit per cell for each sequence, set and cleared when positions are added or removed, and allocated only when a sequence first claims a cell. Gathering cells then walks set bits up to the used range, preserves cell order, puts shared cells on every relevant list, and avoids full rebuilds on removal. Sliding-window trim behavior from an earlier prototype is included.

On an RTX PRO 6000 Blackwell card, flash-attention batched generation with Q8_0 MoE models was measured against the current unified path and a prior cached-list prototype. Token rates for Gemma-class and Qwen-class runs at 4K through roughly 100K rows were within noise of the prototype and often ahead of the baseline unified path; a non-unified split configuration remained competitive as a reference. Host time to build the sequence cell lists fell to about 0.385 ms for a heavy Qwen case with 800K used cells across eight slices, versus roughly 2.84 ms in an earlier baseline, and to about 0.020 ms on a lighter Gemma batch. Perplexity on checked Qwen variants matched the split reference at the same batch settings, so the faster bookkeeping is not buying speed with a quality trade.

The results are still developer-facing measurements on one GPU and a small model set, not a finished default, but they target a real host-side bottleneck when many sequences share a large unified cache.