Qsa Indexer Kernels#
-
struct QsaIndexerPoolState#
Where the QSA indexer’s persistent state lives. Kernels are state-location-agnostic: they receive this struct and compute addresses from it; only plugin launch sites know the state is in the widened-pool tails.
Addressing contract (pool laid out [2 * numPages, 128, numKVHeads, poolHeadDim] T): element (page, row, head, col) lives at element offset page * 128 * numKVHeads * poolHeadDim + row * numKVHeads * poolHeadDim
head * poolHeadDim + col. Token t’s tails are head 0, columns [headSize, headSize + 128) of row t & 127 on K page pageTable[b][0][t >> 7] and V page pageTable[b][1][t >> 7] (the V id already includes the +numPages offset — do NOT re-add it). What they hold is under “Pool tails” below. Page-table entries equal to kUNUSED_PAGE_ENTRY (-1, cpp/common/pagedKvTypes.h) are guarded BEFORE dereferencing; kernels treat them as “nothing persistable here”.
Public Members
-
void *poolPtr#
[2*numPages, 128, numKVHeads, poolHeadDim] T base
-
int32_t const *pageTable#
[B, 2, maxPagesPerSeq]; V ids pre-offset +numPages
-
int32_t maxPagesPerSeq#
-
int32_t numPages#
K-plane page count.
-
int32_t numKVHeads#
2
-
int32_t poolHeadDim#
384
-
int32_t headSize#
256 == tail column offset
-
struct QsaIndexerVerifyScratch#
Scratch buffers for the tree indexer; allocated by runQsaIndexerVerify, never retained by a kernel.
Public Members
-
void *qNormed#
T [B,S,4,128].
-
void *newKbar#
T [B,S,128], keyed by the node completing a block.
-
int32_t *paths#
INT32 [B,S,S], ancestors in depth order, then -1.
-
int32_t *logicalLengths#
INT32 [B,S], prefix length + depth + 1, zero for invalid/padded rows.
-
float *logits#
FP32 [B,S,maxBlocks], only the visible prefix is initialized.
-
void *qNormed#
-
template<typename T>
void trt_edgellm::kernel::ensureQsaIndexerKernelsLoaded( Compile (NVRTC) and driver-load the QSA indexer kernels for activation type T.
#
Pool tails#
K-tail[t] raw index-K of token t: its indexQk columns [512, 640), BIT-UNMODIFIED. V-tail[4g] block rope row: the 64 FP32 cos/sin of position 4g as raw bytes (256 B == 128 T), never converted to T. V-tail[4g+1] kbar of block g. V-tail[4g+2], V-tail[4g+3] unused. Every path that writes a token’s K/V (prefill, chunk, decode, verify) writes its K-tail and, at 4g, its V-tail. Cells belong to their own token’s row, so moving whole rows (the speculative commit) moves the state with them. kbar is a pure function of the block’s four K-tails and its rope row, so it can be recomputed at any time: prefill, chunk and decode compress the blocks their query rows complete, and launchQsaIndexerSeal recompresses the last kQSA_SEAL_BLOCKS complete blocks before a chunk or verify reads them. Every compress runs the same routine, so all of them are bit-identical to prefill K1b. Readers gather kbar only for g < length / 4. Alignment: checkPoolState requires headSize and numKVHeads * poolHeadDim to be even, so the FP32 rope row is 4-byte aligned.
The device code lives in kernelSrcs/qsaIndexer/qsaIndexerJitKernels.cu and every launcher below JIT-compiles and cuModuleLoadData’s it lazily on first use, cached process-wide per (CUDA context, SM version, dtype). Those one-time host-side steps must not happen inside a CUDA Graph capture, so callers that capture the launchers (or enqueue them from a TRT plugin whose stream may be captured) must call this warmup first from a non-captured context, e.g. onShapeChange; after it returns, the launchers only issue cuLaunchKernel.
- Template Parameters:
T – Activation type: half or __nv_bfloat16.
- Throws:
std::runtime_error – on NVRTC or CUDA driver failure
-
template<typename T>
void trt_edgellm::kernel::launchQsaIndexQPrep( - T *qNormed,
- T const *indexQk,
- float const *cosSin,
- int32_t const *contextLengths,
- T const *wQ,
- float rmsEps,
- int32_t batchSize,
- int32_t seqLen,
- cudaStream_t stream
K1a: Gemma-style qk-norm + partial neox rope on the index-Q heads.
Reads the packed indexer projection
indexQk[batchSize, seqLen, 640] where each row is 4 q-heads x 128 dims followed by 1 raw k x 128 dims, and writes the normalized, roped q heads toqNormed[batchSize, seqLen, 4, 128].Exact numerics (FP32 unless stated): per (b, t, h) head, meanSq = sum(x_f32^2) / 128 via warp reduction; y = x_f32 * rsqrtf(meanSq + rmsEps) * (1.0f + w_f32) with w the RAW checkpoint gamma (the kernel adds the +1, do NOT pre-fold); then neox rope on dims [0, 64): pair (i, i+32) -> (x0*cos - x1*sin, x1*cos + x0*sin) with cos = cosSin[b*S + t][i], sin = cosSin[b*S + t][32 + i] (token-aligned rows); single cast to T at the very end.
Padding semantics: rows with t >= contextLengths[b] are written as exact zeros; their
indexQkcontents are never read (NaN-safe).Launch: grid(batchSize * seqLen), block(128) = 4 warps, warp h owns head h, 4 dims/lane.
- Template Parameters:
T – Activation type: half or __nv_bfloat16.
- Parameters:
qNormed – [out] [batchSize, seqLen, 4, 128] T, contiguous, naturally aligned
indexQk – [in] [batchSize, seqLen, 640] T (4 q-heads x 128 then raw k x 128 per row)
cosSin – [in] FP32 [batchSize * seqLen, 64] token-aligned rows (row b*S + t = token (b, t)); cos [0:32], sin [32:64]
contextLengths – [in] Device INT32 [batchSize], 0 <= contextLengths[b] <= seqLen
wQ – [in] T [128] indexer q-norm gamma as stored in the checkpoint (raw w, not 1+w)
rmsEps – [in] RMS norm epsilon (1e-6f for qwen4_exp)
batchSize – [in] Batch size B
seqLen – [in] Padded sequence length S
stream – [in] CUDA stream
- Throws:
std::runtime_error – on invalid arguments or launch failure
-
template<typename T>
void trt_edgellm::kernel::launchQsaIndexKCompress( - T *kbar,
- T const *indexQk,
- float const *cosSin,
- int32_t const *contextLengths,
- T const *wK,
- float rmsEps,
- int32_t batchSize,
- int32_t seqLen,
- int32_t numBlocks,
- cudaStream_t stream
K1b: compress raw index-K into per-block keys, then Gemma-norm + partial neox rope.
For each (b, g) with g in [0, numBlocks): the block is valid iff it is complete, i.e. 4*g + 3 < contextLengths[b]. Valid blocks compute, per dim d: mean = (((k0 + k1) + k2) + k3) * 0.25f (FP32, FIXED sequential order) cast mean to T, re-load as FP32 (bit-compatibility-critical cast) y = m_f32 * rsqrtf(meanSq + rmsEps) * (1.0f + w_f32) (meanSq over the 128 cast values) neox rope at position 4*g, read from the token-aligned row of token 4*g, i.e. row b*seqLen + 4*g (same pairing/row layout as launchQsaIndexQPrep) cast to T at the very end. kj is the raw index-K row of token 4*g + j, read from indexQk row 4*g + j, columns [512, 640). Invalid blocks are written as exact zeros and never read (NaN-safe).
Launch: grid(batchSize * numBlocks), block(32) = one warp per block, 4 dims/lane.
- Template Parameters:
T – Activation type: half or __nv_bfloat16.
- Parameters:
kbar – [out] [batchSize, numBlocks, 128] T
indexQk – [in] [batchSize, seqLen, 640] T (raw k occupies columns [512, 640))
cosSin – [in] FP32 [batchSize * seqLen, 64] token-aligned rows (row b*seqLen + t = token (b, t))
contextLengths – [in] Device INT32 [batchSize], 0 <= contextLengths[b] <= seqLen
wK – [in] T [128] indexer k-norm gamma as stored in the checkpoint (raw w, not 1+w)
rmsEps – [in] RMS norm epsilon
batchSize – [in] Batch size B
seqLen – [in] Number of token rows present in indexQk
numBlocks – [in] Number of output blocks, >= ceilDiv(seqLen, 4)
stream – [in] CUDA stream
- Throws:
std::runtime_error – on invalid arguments or launch failure
-
template<typename T>
void trt_edgellm::kernel::launchQsaIndexScores( - float *logits,
- int32_t *visibleCounts,
- T const *qNormed,
- T const *kbar,
- int32_t const *contextLengths,
- int32_t batchSize,
- int32_t seqLen,
- int32_t numBlocks,
- int32_t rowStart,
- int32_t numRows,
- cudaStream_t stream
K2: block-relevance logits for a chunk of query rows.
For global rows r = b * seqLen + t in [rowStart, rowStart + numRows) writes logits[r - rowStart][g] for visible blocks g in [0, nVis(t)): logits = (1 / sqrtf(128)) * sum_{h < 4} fmaxf(0.f, sum_d q[r][h][d] * kbar[b][g][d]) FP32 dot per head, relu PER HEAD, sum over heads (ascending h), scale AFTER the sum. Causal visibility: nVis(t) = (t + 1) / 4 for live queries and zero for padding. Columns outside this prefix are untouched. Padded rows never read q or kbar (NaN-safe).
Launch: grid(numRows, ceilDiv(numBlocks, 64)), block(256); the CTA stages the row’s 4 x 128 q values in FP32 shared memory (2 KB); each warp evaluates one block-column at a time via lane-strided FP32 FMA + warp shuffle reduction.
- Template Parameters:
T – Activation type: half or __nv_bfloat16.
- Parameters:
logits – [out] FP32 [numRows, numBlocks] chunk-local rows; visible prefix only
visibleCounts – [out] Device INT32 [numRows], number of visible blocks per chunk-local row
qNormed – [in] [batchSize, seqLen, 4, 128] T from launchQsaIndexQPrep
kbar – [in] [batchSize, numBlocks, 128] T from launchQsaIndexKCompress
contextLengths – [in] Device INT32 [batchSize]
batchSize – [in] Batch size B
seqLen – [in] Padded sequence length S
numBlocks – [in] ceilDiv(seqLen, 4)
rowStart – [in] First global row of the chunk
numRows – [in] Rows in the chunk; rowStart + numRows <= batchSize * seqLen
stream – [in] CUDA stream
- Throws:
std::runtime_error – on invalid arguments or launch failure
- void trt_edgellm::kernel::launchQsaIndexIdsFill(
- int32_t *ids,
- int32_t numRows,
- int32_t numBlocks,
- cudaStream_t stream
Fill per-segment block ids for the segmented sort: ids[r * numBlocks + c] = c.
- Parameters:
ids – [out] INT32 [numRows, numBlocks]
numRows – [in] Rows (segments) in the chunk
numBlocks – [in] Segment width
stream – [in] CUDA stream
- Throws:
std::runtime_error – on invalid arguments or launch failure
- void trt_edgellm::kernel::launchQsaIndexExpand(
- int32_t *outIdx,
- int32_t const *sortedIds,
- int32_t const *contextLengths,
- int32_t const *pastLengths,
- int32_t batchSize,
- int32_t seqLen,
- int32_t numBlocks,
- int32_t rowStart,
- int32_t numRows,
- cudaStream_t stream
K4: expand top blocks into token indices and append the causal tail.
For global rows r = b * seqLen + t in [rowStart, rowStart + numRows), with total = past_b + t + 1, nVis = total / 4, kSel = min(512, nVis), tail = total % 4: out[r][4*i + j] = sortedIds[r - rowStart][i] * 4 + j for i < kSel, j in {0,1,2,3} out[r][4*kSel + j] = 4 * nVis + j for j < tail (ALWAYS appended) out[r][j] = -1 for all remaining slots. sortedIds holds block ids sorted by descending logit (only the first kSel entries are read). Padded rows (t >= contextLengths[b] or contextLengths[b] == 0) are written as all -1 and never read sortedIds. Output token indices are distinct, in [0, past_b + t], unsorted.
Launch: grid(numRows), block(256), threads stride the 2051 output slots.
- Parameters:
outIdx – [out] INT32 [batchSize * seqLen, 2051]; rows [rowStart, rowStart + numRows) written
sortedIds – [in] INT32 [numRows, numBlocks] chunk-local descending-logit block ids
contextLengths – [in] Device INT32 [batchSize]
pastLengths – [in] Optional device INT32 [batchSize] prefix lengths; nullptr means zero past. contextLengths counts new rows, and visibility/tails use pastLengths[b] + t + 1.
batchSize – [in] Batch size B
seqLen – [in] Padded sequence length S
numBlocks – [in] Sorted row width; must cover all visible compressed groups
rowStart – [in] First global row of the chunk
numRows – [in] Rows in the chunk
stream – [in] CUDA stream
- Throws:
std::runtime_error – on invalid arguments or launch failure
-
template<typename T>
void trt_edgellm::kernel::launchQsaRawKTailWritePrefill( - T const *indexQk,
- float const *cosSin,
- int32_t const *contextLengths,
- int32_t const *pastLengths,
- QsaIndexerPoolState const &poolState,
- int32_t batchSize,
- int32_t seqLen,
- cudaStream_t stream
Prefill tail write: the pool tails of every valid query row (see “Pool tails”).
Query row (b, t) is token past_b + t. It copies indexQk row (b, t) columns [512, 640) BIT-UNMODIFIED into its K-tail; a token at 4g also copies cosSin row b*S + t (64 FP32, raw bytes) into its V-tail. Padded rows and tokens whose page-table slot is out of range or kUNUSED_PAGE_ENTRY write nothing; no other pool cell is touched.
Launch: grid(batchSize * seqLen), block(32) = one warp per query row, 4 columns/lane.
- Template Parameters:
T – Activation type: half or __nv_bfloat16 (must match the pool element type).
- Parameters:
indexQk – [in] [batchSize, seqLen, 640] T (raw k occupies columns [512, 640))
cosSin – [in] FP32 [batchSize * seqLen, 64] token-aligned rope rows (as launchQsaIndexQPrep)
contextLengths – [in] Device INT32 [batchSize], 0 <= contextLengths[b] <= seqLen
pastLengths – [in] Optional device INT32 [batchSize] prefix lengths; nullptr means zero past.
poolState – [in] Paged indexer state; see QsaIndexerPoolState
batchSize – [in] Batch size B
seqLen – [in] Padded sequence length S
stream – [in] CUDA stream
- Throws:
std::runtime_error – on invalid arguments or launch failure
-
template<typename T>
void trt_edgellm::kernel::launchQsaIndexerPreDecode( - T *qNormed,
- T const *indexQk,
- float const *cosSin,
- int32_t const *contextLengths,
- T const *wQ,
- T const *wK,
- float rmsEps,
- QsaIndexerPoolState const &poolState,
- int32_t batchSize,
- cudaStream_t stream
B1: fused decode pre-pass — q-prep + the new token’s tail write + block compress.
One CTA per sequence; every sequence carries exactly one new token whose TOTAL context length (including it) is contextLengths[b], so its position is pos = contextLengths[b]-1. Three phases:
(all 4 warps) K1a numerics VERBATIM at S = 1 with the token-aligned rope row b (position pos) — decode rows are never padded, so there is no padding branch (contextLengths[b] <= 0 writes exact zeros and skips phases 2-3). Output qNormed [batchSize, 1, 4, 128].
(warp 0) indexQk columns [512, 640) stored BIT-UNMODIFIED to the K-tail of token pos; when pos opens a block, rope row b goes as raw bytes into its V-tail (see “Pool tails”).
(warp 0) only when contextLengths[b] % 4 == 0: the block pos completes is compressed (the K1b routine, rope row from token 4g’s V-tail) into the V-tail of token 4g + 1. Decode does not reseal earlier blocks, so it must not directly follow a speculative commit. The launch is unconditional and device-masked: safe to capture in a CUDA graph.
Launch: grid(batchSize), block(128) = 4 warps.
- Template Parameters:
T – Activation type: half or __nv_bfloat16 (must match the pool element type).
- Parameters:
qNormed – [out] [batchSize, 1, 4, 128] T
indexQk – [in] [batchSize, 1, 640] T (4 q-heads x 128 then raw k x 128 per row)
cosSin – [in] FP32 [batchSize, 64] token-aligned rows (row b = sequence b’s new token)
contextLengths – [in] Device INT32 [batchSize] TOTAL lengths including the new token
wQ – [in] T [128] indexer q-norm gamma (raw checkpoint w, not 1+w)
wK – [in] T [128] indexer k-norm gamma, same raw-w convention
rmsEps – [in] RMS norm epsilon
poolState – [in] Paged indexer state; see QsaIndexerPoolState
batchSize – [in] Batch size B
stream – [in] CUDA stream
- Throws:
std::runtime_error – on invalid arguments or launch failure
-
template<typename T>
void trt_edgellm::kernel::launchQsaIndexerSeal( - int32_t const *lengths,
- T const *wK,
- float rmsEps,
- QsaIndexerPoolState const &poolState,
- int32_t batchSize,
- cudaStream_t stream
Seal: recompress the last kQSA_SEAL_BLOCKS complete blocks of [0, lengths[b]) from the pool tails into their kbar cells (see “Pool tails”); every tail of those tokens must be in the pool. Idempotent. Blocks on unallocated pages and sequences with lengths[b] < 4 write nothing.
Launch: grid(kQSA_SEAL_BLOCKS, batchSize), block(32) = one warp per block.
- Template Parameters:
T – Activation type: half or __nv_bfloat16 (must match the pool element type).
- Parameters:
lengths – [in] Device INT32 [batchSize] token counts whose tails are in the pool
wK – [in] T [128] indexer k-norm gamma (raw checkpoint w, not 1+w)
rmsEps – [in] RMS norm epsilon
poolState – [in] Paged indexer state; see QsaIndexerPoolState
batchSize – [in] Batch size B
stream – [in] CUDA stream
- Throws:
std::runtime_error – on invalid arguments or launch failure
-
template<typename T>
void trt_edgellm::kernel::launchQsaIndexScoresDecode( - float *logits,
- T const *qNormed,
- int32_t const *contextLengths,
- QsaIndexerPoolState const &poolState,
- int32_t batchSize,
- int32_t maxBlocks,
- cudaStream_t stream
B2: decode block-relevance logits from the paged kbar V-tails.
K2 numerics at S = 1: logits[b][g] = (1/sqrtf(128)) * sum_h relu(q[b][h] . kbar[b][g]) (FP32 dot per head, relu PER HEAD, sum ascending h, scale AFTER the sum) for every g < nVis(b) = contextLengths[b] / 4, with kbar gathered from the V-tail of token 4g + 1. ONLY the valid prefix [0, nVis) of each row is written (no -FLT_MAX fill; downstream reads only the valid prefix). The grid is fixed from the host-static maxBlocks; CTAs (and warps) past nVis early-out, and each warp’s 8 block-columns share one page-table lookup (32 consecutive blocks live in one 128-token page).
Launch: grid(batchSize, ceilDiv(maxBlocks, 64)), block(256).
- Template Parameters:
T – Activation type: half or __nv_bfloat16 (must match the pool element type).
- Parameters:
logits – [out] FP32 [batchSize, maxBlocks]; only [0, contextLengths[b]/4) written
qNormed – [in] [batchSize, 1, 4, 128] T from launchQsaIndexerPreDecode
contextLengths – [in] Device INT32 [batchSize] TOTAL lengths including the new token
poolState – [in] Paged indexer state; see QsaIndexerPoolState
batchSize – [in] Batch size B
maxBlocks – [in] Logits row stride; must cover ceilDiv(max context, 4)
stream – [in] CUDA stream
- Throws:
std::runtime_error – on invalid arguments or launch failure
- void trt_edgellm::kernel::launchQsaTopKExpandDecode(
- int32_t *outIdx,
- float const *logits,
- int32_t const *contextLengths,
- int32_t *splitCounters,
- int32_t numKVHeads,
- int32_t batchSize,
- int32_t maxBlocks,
- cudaStream_t stream
B3: decode top-512 block select + K4 expand (deterministic, no cub, no alloc).
Per sequence b with ctx = contextLengths[b], nVis = ctx/4, kSel = min(512, nVis), tail = ctx % 4: a. splitCounters[b*numKVHeads, b*numKVHeads + numKVHeads) are zeroed when the pointer is non-null (the decode attention’s split-K merge counters; workspace memory is not persistent across enqueues, so in-enqueue zeroing is load-bearing for CUDA graphs). b. nVis <= 512 selects ALL blocks (fast path; logits are never read). c. Otherwise an MSB-first 8-bit radix select over the monotone orderable map of the FP32 logits (u = bits >= 0 ? bits | 0x80000000 : ~bits) resolves the threshold in <= 4 shared-memory histogram passes (float4-vectorized where aligned, early exit when a bin exactly fills the remaining quota). d. Emit is a fixed-order scan: u > threshold always selected; u == threshold fills the remaining quota in ASCENDING block-id order. This matches the stable descending cub::DeviceSegmentedRadixSort over ascending-id values used by prefill, so prefill and decode select IDENTICAL block sets for identical logits. e. K4 expand: out[b][4i+j] = sel[i]*4 + j packed front, then the tail tokens [4*nVis, ctx) (ALWAYS appended), then -1 padding to width 2051. Two identical runs produce bitwise-identical outIdx.
Launch: grid(batchSize), block(512); ~1.3 KB shared memory.
- Parameters:
outIdx – [out] INT32 [batchSize, 1, 2051] (kQSA_INDEX_WIDTH)
logits – [in] FP32 [batchSize, maxBlocks] from launchQsaIndexScoresDecode; only the valid prefix [0, nVis) of each row is read
contextLengths – [in] Device INT32 [batchSize] TOTAL lengths including the new token
splitCounters – [inout] Device INT32 [batchSize, numKVHeads] or nullptr
numKVHeads – [in] Counter row width; ignored when splitCounters is nullptr
batchSize – [in] Batch size B
maxBlocks – [in] Logits row stride; must cover ceilDiv(max context, 4)
stream – [in] CUDA stream
- Throws:
std::runtime_error – on invalid arguments or launch failure
-
template<typename T>
void trt_edgellm::kernel::launchQsaIndexKCompressAppend( - T const *indexQk,
- float const *cosSin,
- int32_t const *queryLengths,
- int32_t const *pastLengths,
- T const *wK,
- float rmsEps,
- QsaIndexerPoolState const &poolState,
- int32_t batchSize,
- int32_t seqLen,
- cudaStream_t stream
Compress groups completed by the current query rows into their paged V-tails. New indexQk/cosSin rows are [batchSize, seqLen, 640/64]; queryLengths counts valid new rows and optional pastLengths counts cached tokens (nullptr means zero past). A boundary group reads the cached raw K and block rope row from the pool. Other groups read current rows directly. Uses the prefill FP32 mean, cast-to-T, Gemma norm and rope numerics. Zero-length entries touch no input or pool data. The pool format is unchanged.
-
template<typename T>
void trt_edgellm::kernel::launchQsaIndexScoresPaged( - float *logits,
- int32_t *visibleCounts,
- T const *qNormed,
- int32_t const *queryLengths,
- int32_t const *pastLengths,
- QsaIndexerPoolState const &poolState,
- int32_t batchSize,
- int32_t seqLen,
- int32_t maxBlocks,
- int32_t rowStart,
- int32_t numRows,
- cudaStream_t stream
Score query rows against paged kbar without copying historical keys. Writes per-row visible counts and matches launchQsaIndexScores with visibility (pastLengths[b] + t + 1) / 4 and queryLengths[b] valid rows; nullptr means zero past. Invisible and padded entries are untouched. Missing pages in the visible prefix receive -FLT_MAX. maxBlocks is the logits row stride and must cover all visible compressed groups.
-
template<typename T>
void trt_edgellm::kernel::launchQsaIndexerVerify( - int32_t *outIdx,
- T const *indexQk,
- float const *cosSin,
- int32_t const *parents,
- int32_t const *depths,
- int32_t const *queryLengths,
- int32_t const *pastLengths,
- T const *wQ,
- T const *wK,
- float rmsEps,
- QsaIndexerPoolState const &poolState,
- QsaIndexerVerifyScratch const &scratch,
- int32_t batchSize,
- int32_t seqLen,
- int32_t maxBlocks,
- cudaStream_t stream
Internal launch sequence; arguments and ownership follow runQsaIndexerVerify.