QSA host KV tier: compact selected pages with a column bitmap and scan (7.5x) #622

Before you start

• I have read the Roadmap and this is not already planned there.
• I have read the FAQ.
• I have searched existing issues and found no duplicate.

Applies to

Engine

What problem does this solve

compact_selected_pages (#499, kernel/triton/qsa/offload.py) runs one program per query row. Each program walks the row's ~2048 selected tokens one by one, comparing every token against all pages found so far. A decode step therefore spends ~1.2 ms per QSA layer in it on one SM (12 layers -> ~14 ms per token).

Proposed solution

Do it in two passes with an int8 per-row column bitmap (scratch owned by the caller, so it stays CUDA-graph safe):

1. Mark: a grid over rows × selection blocks stores 1 at marks[row, token // page_size]. Duplicate plain stores of the same value are race-free, so no atomics are needed.
2. Scan: one program per row walks the columns in 1024-wide blocks, using tl.cumsum to place the page ids and clearing the marks it reads.

Pages come back in column order; the padding, counts and drop counting are unchanged. Reference implementation: gdevenyi@8947d81e4b5f

Measured on a GTX 1080 Ti: 1282 -> 171 µs per call (1 row × 2048 tokens × 4097 columns). Decode with --kv-host-pages 3584: 14.08 -> 17.21 tok/s.

Alternatives considered

Sorting the selection per row also works, but the bitmap is simpler and has fixed shapes.