# How the kernels work ## The score as a sum over pairs With RoPE (Hugging Face layout), features l and l + 32 of a 64-dimensional head form pair l, rotated at frequency θl = b−2l/64. The score splits exactly into one part per pair, and HiSA keeps part l while (i − j)·θl < Φ, i.e. while i − j < Ll = ⌈Φ/θl⌉ (integer thresholds computed once in float64, `hisa.rope.thresholds`, so every implementation applies exactly the same rule). Since the windows grow with l, the pairs dropped at a given distance are always a **prefix** l < a(distance) of the pairs. ## The chunked feature layout Tensor cores multiply 16 features at a time (one bf16 K-step), so the kernels permute q and k once so that chunk c (16 contiguous features) holds pairs 8c … 8c+7 (`hisa.rope.chunk_permutation`). A prefix of pairs is then a prefix of chunks: skipping the dropped pairs means skipping whole 16-feature slices of Q Kᵀ, plus zeroing the dropped pairs of the one boundary chunk. Inner products over any subset of pairs are unchanged by the permutation. ## Exact rule (Triton, `hisa/kernels/triton_exact.py`) FlashAttention-2 structure (query tile × key tiles, online softmax, recomputation in backward). On a tile the distances span [dmin, dmax]; pairs below a_lo are dropped everywhere (skipped), pairs above a_hi are kept everywhere (one dot over their chunks), and the few pairs in between are **mixed**: masked element-wise with D < Ll. The key loop runs in 4 segments (far → near) that compute 1, 2, 3 or 4 chunks, so the loop bodies have no data-dependent loads. The result is exact (equal to the reference up to floating-point order). ## Block rule (Triton `triton_block.py`, Flash-HiSA) Positions are grouped into blocks of S = 128 tokens, and pair l is kept on a whole (query block, key block) pair iff the blocks' minimum distance dmin = max((bi − bj)·S − (S − 1), 0) is below Ll. Kernel tiles divide S, so every tile keeps the same pairs: no mixed pairs, no element-wise masks. It is a slightly denser model than the exact rule (each pair is kept up to S − 1 tokens longer), so it must be used for training and inference alike. ## Flash-HiSA in the FlashAttention-3 fork All changes are in one commit on top of FlashAttention 3.0.1 (`third_party/flash-attention`, branch `hisa`; see `HISA.md` there), as separate compile-time "Sparse" instantiations (hdim 64, bf16, sm90), so the dense kernels are unchanged: - `hopper/mainloop_fwd_sm90_tma_gmma_ws.hpp`: Q Kᵀ sliced per 16-feature chunk; for each key block the chunks below K0 are skipped with straight-line GMMA sequences per K0 (no predicated or branched GMMA, which would serialise the warpgroup MMAs); the dropped pairs of the boundary chunk are zeroed in shared-memory Q. - `hopper/mainloop_bwd_sm90_tma_gmma_ws.hpp`: the same rule in the backward pass (Sᵀ skips the dropped chunks). - `hopper/flash_api_stable.cpp`: new op arguments `sparse_a` (the table below), `sparse_rule_block`, and `sparse_kc0..3` (decoding). - The table (`hisa.kernels.flash.table_with_header`): for every block distance nd, the number a[nd] of dropped pairs, with a header nd1..4 (first distance with ≥ 8, 16, 24 dropped pairs, and the number of distances with a kept pair) and the thresholds, so the kernel derives the number of skipped chunks per segment without memory loads in the main loop. ## Decoding: per-chunk ring buffers (`hisa/kernels/flash_decode.py`, `hopper/sparse_kv.h`) A cached key needs chunk c only while the slowest pair of the chunk is still kept, and its value only within the reach. `HiSAKVCache` stores the keys as four ring buffers, one per chunk, of length Mc = the window of the chunk's slowest pair rounded up to whole 128-token blocks, and the values in one ring of length MV (the reach, capped at S_max). The token at position t lives in slot t mod Mc of ring c; a new token overwrites the slot of a token that has just left that chunk's window, so there is no eviction step. Because rings hold whole blocks, a 128-key tile never wraps. The decode kernel (one query position per sequence, query heads packed per KV head, split-KV) reads each key block's kept chunks with `cp.async`; dropped chunks are zero-filled without memory access. The ring lengths come from the block rule, so the decode output equals the block-rule forward pass.