Skip to navigation

Query Sparse Attention (QSA)

View as MarkdownOpen in Claude

QSA applies attention to the four-token blocks selected for each query. It uses the original K/V tensors; block selection is an input and receives no gradient. The API follows the Miles packed training interface. The source contract is Miles block_sparse_attention.py at 0cc6516.

from torch import Tensor
from cudnn.ops import qsa_forward, qsa_backward
def qsa_forward(
q: Tensor,
k: Tensor,
v: Tensor,
sel_blocks: Tensor,
lo: Tensor,
hi: Tensor,
blk_base: Tensor,
tok_base: Tensor,
block_first: Tensor,
block_last: Tensor,
scale: float,
block_size: int = 4,
) -> TupleDict:
... # out, out_fp32, lse
def qsa_backward(
grad_out: Tensor,
q: Tensor,
k: Tensor,
v: Tensor,
out_fp32: Tensor,
lse: Tensor,
sel_blocks: Tensor,
lo: Tensor,
hi: Tensor,
blk_base: Tensor,
tok_base: Tensor,
block_first: Tensor,
block_last: Tensor,
scale: float,
block_size: int = 4,
deterministic: bool = False,
) -> TupleDict:
... # dq, dk, dv

deterministic=True returns the same gradient bytes on every run with the same inputs and packed layout, at a lower speed.

Both calls return a TupleDict. Tuple unpacking follows the order above; string keys have the same names. Forward and backward are explicit calls. The forward call does not register a PyTorch autograd function.

Finding QSA attention and its indexer

QSA’s public functions use the cudnn.ops.qsa_* prefix. Their implementations live under cudnn.QSA; the selector shares scorer and top-k kernels with DSA. Choose an entry by its input and saved-state contract:

NeedEntry pointContract
Packed training with a block-selection bitmapcudnn.ops.qsa_forward, qsa_backwardThe bitmap API documented on this page; 24Q/2KV, 12Q/1KV or 6Q/1KV
Packed training with selected token IDscudnn.ops.qsa_indexed_forward, qsa_indexed_backward (docs, GitHub)12Q/1KV or 6Q/1KV on SM100/SM103/SM107; shares the QSA attention kernels
Generate selected blocks from indexer Q and compressed Kcudnn.ops.qsa_select_forward, qsa_select_decode_forwardQSA selector over the shared DSA scorer and top-k; returns local block IDs, not token IDs
Decode selection over a paged compressed-key cachecudnn.ops.qsa_select_decode_paged_forwardBF16 indexer cache; see the paged selector’s architecture and layout requirements in its docstring
Integrated projection, compression, selection and attentionGatedAttentionBlockFwd with QsaSpec(index_source="indexer") (docs, GitHub)Use the integrated block’s own architecture, layout and inference support matrix

Indexed attention consumes indices; the indexer generates them. The indexed training calls do not run scoring or top-k. The selector’s local block IDs need expansion to the attention input format, including the incomplete causal tail and the packed sequence’s token origin. Its standalone wrapper can be imported as follows:

from cudnn.ops import qsa_select_forward, qsa_select_decode_forward, qsa_select_decode_paged_forward

QSA’s selector scores each complete compressed block as scale * sum_h relu(qi[t, h] @ kbar[block]). The existing cudnn.DSA.indexer_forward_top_k_wrapper provides this ratio-causal scorer and top-k operation with compression ratio four and constant head weights. Sharing these kernels avoids a second implementation. QSA-specific compression, block visibility and tail handling remain part of the QSA contract; this reuse does not make QSA and DeepSeek attention interchangeable. Numerical rounding and top-k tie rules must also be checked before replacing an external selector.

On every architecture both training entries run one backward engine (cudnn.QSA._backward launching the kernels of cudnn.QSA.kernels.bprop_sm100, and on SM107 the Rubin dense pair and key-major kernels of cudnn.QSA.kernels.bprop_sm107): the prefix of every sequence (its first 20480 queries, or all of them below 22528 tokens) on a dense key-tile kernel that masks per key token through a bitmap, the remaining queries on a query-major pass that writes P / dS records and a key-major pass that accumulates dK / dV through an inverted block-to-query index, so no per-pair floating-point atomics are issued. The records are bounded by query windows, so the backward workspace of the bitmap entry grows with the token count and not with the number of selected pairs. Blocks may start anywhere, the key bounds may cut them, and a query sees every selected key within lo <= j <= hi, keys after itself included. A query inside the dense prefix of a long sequence that selects a key past that prefix leaves its dQ NaN and contributes nothing to those keys’ dK / dV. A query past the dense prefix holds at most 513 selected blocks (top-512 and the causal tail); a longer list contributes nothing and leaves that query’s dQ NaN. The one-KV-head flavors (12Q/1KV and 6Q/1KV) need the CUDA 13 build of CuTe DSL; 6Q/1KV runs the same kernels with six real head rows in the 12-row query tiles, so it costs as much as 12Q/1KV. The bitmap entry reads the sequences from tok_base; qsa_indexed_backward describes packed documents through selection_mode="causal_topk" with cu_seqlens (docs, GitHub) and otherwise treats the rows as one sequence, which stays exact for packed documents (the selection decides which keys a query sees) but serves only the first document on the dense prefix path.

The experimental QSA entries previously under cudnn.DSA and cudnn.gated_attention_block.qsa_select* have moved without compatibility aliases. These entries were absent from stable v1.31.0; users of development builds should update their imports to the table above. DSA’s shared indexer APIs remain in DSA. The integrated gated-attention block remains its own API.

Tensors

T is the total packed token count. NB is the total number of blocks across all sequences. All tensors must be contiguous and on the same CUDA device.

TensorShapeDtypeMeaning
q[T, Hq, 256]BF16Query vectors
k, v[T, Hkv, 256]BF16Key and value vectors
sel_blocks[T, NB]uint8Nonzero selects a global block for that query
lo, hi[T]int32Inclusive allowed key-token bounds
blk_base[T]int32First global block of the query’s sequence
tok_base[T]int32First global token of the query’s sequence
block_first, block_last[NB]int32Inclusive global token span of each block
out[T, Hq, 256]BF16Attention output
out_fp32[T, Hq, 256]FP32Output before its BF16 cast; save for backward
lse[Hq, T]FP32Natural-log softmax normalizer; save for backward
grad_out[T, Hq, 256]BF16Upstream output gradient
dqSame as qBF16Query gradient
dk, dvSame as k, vBF16Key/value gradients, summed over query heads

Q/K/V, grad_out, and out_fp32 must be 16-byte aligned. FP32 LSE and int32 metadata must be 4-byte aligned. The implementation rejects unsupported layouts before launch. It does not copy or repack inputs.

Selection and components

For query t and key token j, the Miles block lookup is:

b = blk_base[t] + (j - tok_base[t]) // block_size
allowed = lo[t] <= j <= hi[t] and 0 <= b < NB and sel_blocks[t, b] != 0

Metadata must describe a valid packed sequence partition. Each sequence starts its own block numbering, including when its first token is not divisible by four. Its block spans have at most four tokens; only the final block can be shorter. The spans, bases, and token bounds must agree. Values remain on the device and are a caller contract. No host read checks these relationships.

Forward uses dense tiles for short key spans and gathers selected blocks for other tiles. GPU preparation checks the current K/V values and bounds, then builds exact masks. Nonfinite K/V uses the gather path to exclude unused values before arithmetic. Both paths compute scaled QK scores, apply the bounds, and use online softmax followed by PV. They write FP32 output and natural-log LSE, then cast output to BF16. Empty rows produce zero output and negative-infinity LSE.

Backward compacts the current selection, computes delta = sum(grad_out * out_fp32, dim=-1), reconstructs probabilities from QK and LSE, and forms dQ/dK/dV. Accumulation uses FP32; output gradients use BF16. K/V gradient contributions from all query heads are summed. Without deterministic=True, floating-point reductions of the dense prefix can change low bits between runs. The dense prefix of each sequence runs on a key-tile kernel whose two CTAs share a key tile and accumulate dK / dV on chip; the remaining queries write bf16 P / dS records that a key-major pass sums per block, so no per-pair floating-point atomics are issued. dS reaches the dQ MMAs rounded to BF16. The dense prefix forms it from a P that one CTA sends the other in BF16, the remaining queries from an FP32 P. A nonfinite K / V value of a masked token adds exact zeros. One of a selected token poisons the queries that select it and that block’s dK / dV, nothing else. A nonfinite Q or dO value is not contained: it can also reach the dQ of neighboring sparse queries and the dK / dV of keys it does not select. Every content-dependent decision is made on the device, so CUDA graph replay follows the current inputs.

For each query head and its shared KV head, the backward equations are:

S = scale * Q @ K.T
P = exp(S - lse[:, None]) # zero outside the allowed keys
delta = sum(grad_out * out_fp32, dim=-1)
dP = grad_out @ V.T
dS = P * (dP - delta[:, None])
dQ = scale * dS @ K
dK = scale * dS.T @ Q
dV = P.T @ grad_out

The implementation evaluates these equations in tiles. It does not allocate full score or probability matrices.

CallGPU componentResult
ForwardTile bounds, K/V checks, exact mask preparationPrivate tile modes, key ranges and token masks
BothSelection compactionPrivate block IDs and counts for gathered queries
ForwardDense or gathered QK, online softmax, PVout, out_fp32, lse
BackwardPreparationFP32 delta; cleared gradient accumulators
BackwardGather, probability reconstruction, gradient productsFP32 dQ/dK/dV accumulators
BackwardFinal castBF16 dq, dk, dv

The selection bitmap must include any desired causal tail. The implementation does not add a tail automatically. The forward does not truncate the selection at 512 blocks. The backward caps queries past the dense prefix at 513 blocks (above). Pass the same Q/K/V, selection, metadata, and scale to both calls. Casting out back to FP32 does not reconstruct out_fp32.

With deterministic=True the backward returns the same dq, dk and dv bytes on every run with the same inputs and packed layout: the FP32 accumulators of the dense prefix add in an order the layout fixes, which the other accumulators do in both modes while no two blocks share a token. The bytes follow that layout and the GPU’s SM count (docs, GitHub). The ordered adds make the dense prefix slower, and a plan without a sparse path carries two more FP32 dK / dV accumulators.

Support and execution

Supported geometry is BF16, head dimension 256, head counts 24Q/2KV, 12Q/1KV or 6Q/1KV (the full model and its two- and four-way tensor-parallel shards, the KV head replicated at four-way), and block_size=4. T > 0, NB > 0, and T * Hq * 256 <= INT32_MAX are required. scale is a finite host scalar, normally 1 / sqrt(256).

The public functions select one of two architecture families internally:

FamilyForward kernelBackward kernel
Blackwell SM100/SM103cudnn_frost_qsa_fprop_sm100cudnn_qsa_bwd_* (dense pair, query-major, key-major and index kernels)
Rubin SM107cudnn_frost_qsa_fprop_sm107cudnn_qsa_bwd_* (the same engine with its SM107 dense pair and key-major kernels)

Kernel symbols are implementation details; Rubin kernels compile for SM107. Selection rows are compacted 16 bytes per lane on every architecture, preserving block order. CuTeDSL 4.7 or newer is required; Rubin also requires a build with the sm_107a target. On SM107 the backward runs Rubin flavors of the dense pair and key-major kernels, which use the oversized shared memory carveout and a 576-column TMEM allocation where those pay off. A driver without the oversized carveout (older than CUDA 13.4) runs the SM100 kernels on SM107.

Calls allocate outputs and scratch on the input device and enqueue work on its current PyTorch CUDA stream. The backward compiles different kernels below and above the 22528-token dense crossover, from 196608 tokens on, and for each deterministic value. Before CUDA graph capture, warm up with the head geometry, token counts and deterministic the capture will use. Compiled kernels reuse symbolic token and block extents; metadata is rebuilt from the current bitmap on each call. Forward scratch includes an int32 [T, NB] compact-index buffer and int32 [T] counts. Backward compacts the selection again into the same int32 [T, NB] indices and [T] counts and adds one workspace: FP32 dQ / dK / dV accumulators, [T, Hq] delta, the per-token dense bitmap, the sequence tables and, past the dense prefix, the P / dS record windows with their inverted index. The dense forward route also uses packed token masks, tile ranges and K/V check flags. These buffers are rebuilt on each call. Full-call benchmarks must include forward preparation, compaction, backward preparation, and final gradient casts. At T=131072 and NB=32768, the compact-index buffer alone uses 16 GiB in each call.