KernelBench cuda · RTX PRO 6000

DeepSeek NSA Claude Fable 5.2

0.117 msgeomean latency across six shapes · lower is better

manually audited: clean

Fable 5.2 wrote three launches per forward in raw CUDA with inline-PTX bf16 mma. k_prep builds compensated 8-key prefix sums of K with a hi + lo bf16 split for tensor-core block scoring; k_select picks top-9 by tournament and re-evaluates every candidate near the 8th/9th boundary in error-free fp32, so the selected set equals the exact top-8 with the reference's tie rule. Long sequences use persistent workers with an in-kernel ticket scheduler (dense, remote far-field pooled per key block, local window plus LSE merge); S <= 2048 uses a fully dense masked kernel driven by the selection bitmask.

harnessclaudeagent session3h 58mtotal wall4h 4mcheck5mbenchmark1soutput tokens535,672cost$45.13gpu-lock wait2h 6mgpu-lock held52mregimecompute

Per-shape latencymilliseconds are the measured result; the dense-equivalent roofline is not a useful ceiling

1×16×2048×640.080 ms
1×16×4127×640.138 ms
1×8×8192×640.148 ms
1×8×8191×1280.260 ms
4×8×1024×640.054 ms
2×8×3000×640.109 ms

geomean(0.080 ms · 0.138 ms · 0.148 ms · 0.260 ms · 0.054 ms · 0.109 ms) = 0.117 ms

Kernel source (redacted)
"""DeepSeek NSA-style block-select sparse attention -- fused CUDA solution (RTX PRO 6000 / SM120).

Raw CUDA C++ with inline-PTX bf16 tensor-core MMA (m16n8k16); three kernel launches per forward:

  k_prep    exact 8-key prefix sums of K inside every 64-key block (compensated fp32), a
            two-term bf16 split (hi + lo) of each block sum for tensor-core scoring, and the
            reset of the work counters.
  k_select  per query block (c >= 8): block importance q . (hi + lo) on tensor cores, the causal
            partial block from q.k scores, top-9 by a two-level tournament, and an exact
            (error-free fp32) re-evaluation of every candidate whose approximate value lies
            within the error band of the 8th/9th boundary -- so the selected set equals the
            exact-arithmetic top-8 (ties to the higher block, like the reference sort).
            Emits a selection bitmask (dense region) or (query, block) pairs appended to
            per-key-block work lists (sparse far field).
  k_attn    (S > 2048) persistent 4-warp workers with an in-kernel ticket scheduler:
              DENSE  tickets (first 8 query blocks): masked attention with online softmax.
              REMOTE tickets: one key block staged in smem, gathered query rows -> QK^T (mma)
                     -> block softmax -> PV (mma) -> normalized bf16 partial + log-sum-exp.
              LOCAL  tickets: sliding-window blocks c-1, c + online merge of the far-field
                     partials, bf16 output.
  k_dense8  (S <= 2048) 8-warp workers, two query blocks each: fully dense masked attention
            driven by the selection bitmask; no intermediate global traffic.

Measured on this GPU: an L2-resident global load costs ~400-800 cycles, L2<->SM bandwidth is
~5 TB/s read / ~3 TB/s write and fp64 is ~70x slower than fp32.  The design therefore minimises
bytes moved per (query, selected block) pair, issues every load a phase early, pools pairs per
key block so one staged K/V block serves hundreds of queries, and avoids fp64 on hot paths.
"""
from __future__ import annotations

import math

import torch
import torch.nn as nn
from torch.utils.cpp_extension import load_inline

BLOCK_SIZE = 64
TOP_N_BLOCKS = 8
SLIDING_WINDOW = 64

_CUDA_SRC = r"""
#include <cuda_runtime.h>
#include <cstdint>
#include <cstddef>

typedef unsigned int u32;
typedef unsigned short u16;

#define NEG_BIG (-1.0e30f)

__device__ __forceinline__ void mma16816(float* c, u32 a0, u32 a1, u32 a2, u32 a3, u32 b0, u32 b1) {
  asm volatile(
      "mma.sync.aligned.m16n8k16.row.col.f32.bf16.bf16.f32 {%0,%1,%2,%3}, {%4,%5,%6,%7}, {%8,%9}, {%0,%1,%2,%3};\n"
      : "+f"(c[0]), "+f"(c[1]), "+f"(c[2]), "+f"(c[3])
      : "r"(a0), "r"(a1), "r"(a2), "r"(a3), "r"(b0), "r"(b1));
}
__device__ __forceinline__ float ex2f(float x) {
  float y;
  asm("ex2.approx.ftz.f32 %0, %1;" : "=f"(y) : "f"(x));
  return y;
}
__device__ __forceinline__ float lg2f(float x) {
  float y;
  asm("lg2.approx.ftz.f32 %0, %1;" : "=f"(y) : "f"(x));
  return y;
}
__device__ __forceinline__ u32 pack_bf16(float lo, float hi) {
  u32 r;
  asm("cvt.rn.bf16x2.f32 %0, %2, %1;" : "=r"(r) : "f"(lo), "f"(hi));
  return r;
}
__device__ __forceinline__ float bf_lo(u32 w) { return __uint_as_float(w << 16); }
__device__ __forceinline__ float bf_hi(u32 w) { return __uint_as_float(w & 0xffff0000u); }
__device__ __forceinline__ float bf2f(u16 h) { return __uint_as_float(((u32)h) << 16); }

// fp64 is ~70x slower than fp32 on this GPU, so "exact" sums / dot products use fp32
// error-free transformations (value = s + c, compensated) instead of doubles.
__device__ __forceinline__ void two_sum(float& s, float& c, float x) {
  const float t = __fadd_rn(s, x);
  const float bb = __fsub_rn(t, s);
  const float err = __fadd_rn(__fsub_rn(s, __fsub_rn(t, bb)), __fsub_rn(x, bb));
  s = t;
  c = __fadd_rn(c, err);
}
// s + c += a * b exactly (a*b split into rounded product + FMA residual)
__device__ __forceinline__ void two_prod_acc(float& s, float& c, float a, float b) {
  const float h = __fmul_rn(a, b);
  const float e = __fmaf_rn(a, b, -h);
  two_sum(s, c, h);
  c = __fadd_rn(c, e);
}

// ---------------------------------------------------------------------------------
// k_prep: exact key prefix sums at 8-key granularity inside every 64-key block.
//   ps8[head][blk][oct][d] (fp32) = sum of keys blk*64 .. blk*64+8*oct+7      (oct=7: block sum)
//   kb_hi/kb_lo[head][blk][d] (bf16): two-term bf16 split of the block sum (full blocks only)
// thread = (head, blk, dim-chunk of 8, octet); 8 adjacent lanes = the 8 octets of one block.
// Also zeroes the pair-list counters and the work cursor.
// ---------------------------------------------------------------------------------
__global__ void __launch_bounds__(128) k_prep(const u16* __restrict__ K, float* __restrict__ ps8,
                                              u32* __restrict__ kb_hi, u32* __restrict__ kb_lo,
                                              int* __restrict__ cnt, int nCnt, int* __restrict__ ctrl,
                                              int nCtl, int NH, int S, int D, int nb, int nbf) {
  // ctrl[nCtl + head]: bits of max |block-sum element| of the head (atomicMax; reset by k_attn)
  const int gid = blockIdx.x * 128 + threadIdx.x;
  if (gid < nCtl) ctrl[gid] = 0;
  if (gid < nCnt) cnt[gid] = 0;
  const int DC = D >> 3;
  const int total = NH * nb * DC * 8;
  const bool active = gid < total;
  const int gi = active ? gid : (gid & 7);
  const int oct = gi & 7;
  int rest = gi >> 3;
  const int dch = rest % DC;
  rest /= DC;
  const int blk = rest % nb;
  const int head = rest / nb;
  const int key0 = blk * 64 + oct * 8;
  const uint4* p = reinterpret_cast<const uint4*>(K + (size_t)head * S * D) + dch;
  uint4 x[8];
#pragma unroll
  for (int e = 0; e < 8; e++) x[e] = p[(size_t)min(key0 + e, S - 1) * DC];
  float a[8], r[8];  // compensated sums: value = a + r
#pragma unroll
  for (int e = 0; e < 8; e++) { a[e] = 0.f; r[e] = 0.f; }
#pragma unroll
  for (int e = 0; e < 8; e++) {
    if (key0 + e < S) {
      two_sum(a[0], r[0], bf_lo(x[e].x)); two_sum(a[1], r[1], bf_hi(x[e].x));
      two_sum(a[2], r[2], bf_lo(x[e].y)); two_sum(a[3], r[3], bf_hi(x[e].y));
      two_sum(a[4], r[4], bf_lo(x[e].z)); two_sum(a[5], r[5], bf_hi(x[e].z));
      two_sum(a[6], r[6], bf_lo(x[e].w)); two_sum(a[7], r[7], bf_hi(x[e].w));
    }
  }
  // inclusive prefix over the 8 octets of the block (8 adjacent lanes)
#pragma unroll
  for (int off = 1; off < 8; off <<= 1) {
#pragma unroll
    for (int e = 0; e < 8; e++) {
      const float ta = __shfl_up_sync(0xffffffffu, a[e], off);
      const float tr = __shfl_up_sync(0xffffffffu, r[e], off);
      if (oct >= off) {
        two_sum(a[e], r[e], ta);
        r[e] = __fadd_rn(r[e], tr);
      }
    }
  }
  if (!active) return;
  float f[8], lo[8];
#pragma unroll
  for (int e = 0; e < 8; e++) {
    f[e] = __fadd_rn(a[e], r[e]);
    lo[e] = __fsub_rn(r[e], __fsub_rn(f[e], a[e]));
  }
  float4* dst = reinterpret_cast<float4*>(ps8 + (((size_t)head * nb + blk) * 8 + oct) * D + dch * 8);
  dst[0] = make_float4(f[0], f[1], f[2], f[3]);
  dst[1] = make_float4(f[4], f[5], f[6], f[7]);
  if (oct == 7 && blk < nbf) {
    uint4 h, l;
    h.x = pack_bf16(f[0], f[1]); h.y = pack_bf16(f[2], f[3]);
    h.z = pack_bf16(f[4], f[5]); h.w = pack_bf16(f[6], f[7]);
    l.x = pack_bf16(__fadd_rn(__fsub_rn(f[0], bf_lo(h.x)), lo[0]), __fadd_rn(__fsub_rn(f[1], bf_hi(h.x)), lo[1]));
    l.y = pack_bf16(__fadd_rn(__fsub_rn(f[2], bf_lo(h.y)), lo[2]), __fadd_rn(__fsub_rn(f[3], bf_hi(h.y)), lo[3]));
    l.z = pack_bf16(__fadd_rn(__fsub_rn(f[4], bf_lo(h.z)), lo[4]), __fadd_rn(__fsub_rn(f[5], bf_hi(h.z)), lo[5]));
    l.w = pack_bf16(__fadd_rn(__fsub_rn(f[6], bf_lo(h.w)), lo[6]), __fadd_rn(__fsub_rn(f[7], bf_hi(h.w)), lo[7]));
    const size_t o = ((size_t)head * nbf + blk) * (D / 2) + dch * 4;
    *reinterpret_cast<uint4*>(kb_hi + o) = h;
    *reinterpret_cast<uint4*>(kb_lo + o) = l;
    float mx = 0.f;
#pragma unroll
    for (int e = 0; e < 8; e++) mx = fmaxf(mx, fabsf(f[e]));
    atomicMax(ctrl + nCtl + head, (int)__float_as_uint(mx));
  }
}

// ---------------------------------------------------------------------------------
// shared tile helpers (warp = 16 query rows; lane -> (g = lane/4, cc = lane%4))
// The contraction index (dim) is permuted so that lane class cc owns the natural
// dims [cc*D/4, (cc+1)*D/4): all operand loads are contiguous wide loads.
// ---------------------------------------------------------------------------------
template <int D>
__device__ __forceinline__ void load_q_frags(u32 (*a)[4], const u16* row0, const u16* row1, int cc) {
  const uint4* q0 = reinterpret_cast<const uint4*>(row0) + cc * (D / 32);
  const uint4* q1 = reinterpret_cast<const uint4*>(row1) + cc * (D / 32);
#pragma unroll
  for (int u = 0; u < D / 32; u++) {
    const uint4 x = q0[u];
    const uint4 y = q1[u];
    a[2 * u][0] = x.x; a[2 * u][2] = x.y; a[2 * u + 1][0] = x.z; a[2 * u + 1][2] = x.w;
    a[2 * u][1] = y.x; a[2 * u][3] = y.y; a[2 * u + 1][1] = y.z; a[2 * u + 1][3] = y.w;
  }
}

// stage one key block: K natural [key][D/2 words], V transposed [dim][cc(4)][kstep(4)][2 words].
// Split in two halves so a block can be fetched into registers while the previous one is in use.
template <int D, int NT = 128>
struct StageRegs {
  uint4 k[8 * D / NT];
  uint4 v0[4 * D / NT], v1[4 * D / NT];
};
template <int D, int NT = 128>
__device__ __forceinline__ void stage_load(StageRegs<D, NT>& R, const u16* Kb, const u16* Vb, int nkeys, int tid) {
  const uint4* k4 = reinterpret_cast<const uint4*>(Kb);
  const int rowq = D / 8;  // uint4 per key row
#pragma unroll
  for (int e = 0; e < 8 * D / NT; e++) {
    const int x = tid + e * NT;
    const int key = x / rowq;
    R.k[e] = k4[(size_t)min(key, nkeys - 1) * rowq + (x - key * rowq)];
  }
  const int lane = tid & 31, warp = tid >> 5;
  const int ka = min(2 * lane, nkeys - 1), kb = min(2 * lane + 1, nkeys - 1);
  const uint4* v0 = reinterpret_cast<const uint4*>(Vb + (size_t)ka * D);
  const uint4* v1 = reinterpret_cast<const uint4*>(Vb + (size_t)kb * D);
#pragma unroll
  for (int e = 0; e < 4 * D / NT; e++) {
    R.v0[e] = v0[warp + (NT / 32) * e];
    R.v1[e] = v1[warp + (NT / 32) * e];
  }
}
template <int D, int NT = 128>
__device__ __forceinline__ void stage_store(u32* sK, u32* sV, const StageRegs<D, NT>& R, int tid) {
  uint4* s4 = reinterpret_cast<uint4*>(sK);
#pragma unroll
  for (int e = 0; e < 8 * D / NT; e++) s4[tid + e * NT] = R.k[e];
  const int lane = tid & 31, warp = tid >> 5;
  const int p = lane;  // key pair (2p, 2p+1)
  const int woff = (p & 3) * 8 + (p >> 3) * 2 + ((p >> 2) & 1);
#pragma unroll
  for (int e = 0; e < 4 * D / NT; e++) {
    const int u = warp + (NT / 32) * e;
    const uint4 r0 = R.v0[e];
    const uint4 r1 = R.v1[e];
    u32* dst = sV + (8 * u) * 32 + woff;
    dst[0 * 32] = (r0.x & 0xffffu) | (r1.x << 16);
    dst[1 * 32] = (r0.x >> 16) | (r1.x & 0xffff0000u);
    dst[2 * 32] = (r0.y & 0xffffu) | (r1.y << 16);
    dst[3 * 32] = (r0.y >> 16) | (r1.y & 0xffff0000u);
    dst[4 * 32] = (r0.z & 0xffffu) | (r1.z << 16);
    dst[5 * 32] = (r0.z >> 16) | (r1.z & 0xffff0000u);
    dst[6 * 32] = (r0.w & 0xffffu) | (r1.w << 16);
    dst[7 * 32] = (r0.w >> 16) | (r1.w & 0xffff0000u);
  }
}
template <int D>
__device__ __forceinline__ void stage_kv(u32* sK, u32* sV, const u16* Kb, const u16* Vb, int nkeys, int tid) {
  StageRegs<D> R;
  stage_load<D>(R, Kb, Vb, nkeys, tid);
  stage_store<D>(sK, sV, R, tid);
}

// scores[j][0..3] for key tiles j=0..7 (keys 8j+2cc+{0,1}; rows g, g+8)
template <int D>
__device__ __forceinline__ void qk_tile(float (*sc)[4], const u32 (*a)[4], const u32* sK, int g, int cc) {
#pragma unroll
  for (int j = 0; j < 8; j++) { sc[j][0] = 0.f; sc[j][1] = 0.f; sc[j][2] = 0.f; sc[j][3] = 0.f; }
  const u32* kb = sK + g * (D / 2) + cc * (D / 8);
#pragma unroll
  for (int s = 0; s < D / 16; s++) {
#pragma unroll
    for (int j = 0; j < 8; j++) {
      const uint2 b = *reinterpret_cast<const uint2*>(kb + j * 8 * (D / 2) + 2 * s);
      mma16816(sc[j], a[s][0], a[s][1], a[s][2], a[s][3], b.x, b.y);
    }
  }
}

template <int D, int S0 = 0, int S1 = 4>
__device__ __forceinline__ void pv_tile(float (*o)[4], const u32 (*pa)[4], const u32* sV, int g, int cc) {
  const u32* vb = sV + g * 32 + cc * 8;
#pragma unroll
  for (int s = S0; s < S1; s++) {
#pragma unroll
    for (int jd = 0; jd < D / 8; jd++) {
      const uint2 b = *reinterpret_cast<const uint2*>(vb + jd * 8 * 32 + 2 * s);
      mma16816(o[jd], pa[s][0], pa[s][1], pa[s][2], pa[s][3], b.x, b.y);
    }
  }
}

__device__ __forceinline__ float grp_max(float x) {
  x = fmaxf(x, __shfl_xor_sync(0xffffffffu, x, 1));
  x = fmaxf(x, __shfl_xor_sync(0xffffffffu, x, 2));
  return x;
}
__device__ __forceinline__ float grp_sum(float x) {
  x += __shfl_xor_sync(0xffffffffu, x, 1);
  x += __shfl_xor_sync(0xffffffffu, x, 2);
  return x;
}

// ---------------------------------------------------------------------------------
// k_select: one CTA per query block c >= 8 (4 warps x 16 queries).
//   approx importance on tensor cores (q . (hi+lo) bf16 split of the exact block sums; the
//   causal partial block via q.k scores), top-9 by a two-level tournament, and an exact
//   (compensated fp32) re-evaluation of every candidate whose approximate value is within
//   the error band of the 8th/9th boundary.  Emits selection masks (dense region) or
//   far-field (query, block) pairs appended to per-key-block lists (sparse region).
// ---------------------------------------------------------------------------------
#define NEGV (-3.0e38f)
#ifndef SEL_KAPPA2
#define SEL_KAPPA2 (1.0e-4f)
#endif
#define SEL_FLOOR (0.06f)

// exact dot products in compensated fp32 (8 independent (s, c) chains); operand rows are
// loaded in one batch (a global load costs a few hundred cycles, so no load may wait on
// an earlier one).  ACC: float s[8], c[8].
template <int D>
__device__ __forceinline__ void dot_qf(float* s, float* c, const uint4* qv, const float4* p4) {
#pragma unroll
  for (int hb = 0; hb < D / 64; hb++) {
    float4 p[16];
#pragma unroll
    for (int u = 0; u < 16; u++) p[u] = p4[hb * 16 + u];
#pragma unroll
    for (int u = 0; u < 8; u++) {
      const uint4 x = qv[hb * 8 + u];
      const float4 p0 = p[2 * u], p1 = p[2 * u + 1];
      two_prod_acc(s[0], c[0], bf_lo(x.x), p0.x); two_prod_acc(s[1], c[1], bf_hi(x.x), p0.y);
      two_prod_acc(s[2], c[2], bf_lo(x.y), p0.z); two_prod_acc(s[3], c[3], bf_hi(x.y), p0.w);
      two_prod_acc(s[4], c[4], bf_lo(x.z), p1.x); two_prod_acc(s[5], c[5], bf_hi(x.z), p1.y);
      two_prod_acc(s[6], c[6], bf_lo(x.w), p1.z); two_prod_acc(s[7], c[7], bf_hi(x.w), p1.w);
    }
  }
}
template <int D>
__device__ __forceinline__ void dot_qk(float* s, float* c, const uint4* qv, const uint4* k4) {
  uint4 kk[D / 8];
#pragma unroll
  for (int u = 0; u < D / 8; u++) kk[u] = k4[u];
#pragma unroll
  for (int u = 0; u < D / 8; u++) {
    const uint4 x = qv[u];
    const uint4 y = kk[u];
    // bf16 x bf16 products are exact in fp32
    two_sum(s[0], c[0], __fmul_rn(bf_lo(x.x), bf_lo(y.x))); two_sum(s[1], c[1], __fmul_rn(bf_hi(x.x), bf_hi(y.x)));
    two_sum(s[2], c[2], __fmul_rn(bf_lo(x.y), bf_lo(y.y))); two_sum(s[3], c[3], __fmul_rn(bf_hi(x.y), bf_hi(y.y)));
    two_sum(s[4], c[4], __fmul_rn(bf_lo(x.z), bf_lo(y.z))); two_sum(s[5], c[5], __fmul_rn(bf_hi(x.z), bf_hi(y.z)));
    two_sum(s[6], c[6], __fmul_rn(bf_lo(x.w), bf_lo(y.w))); two_sum(s[7], c[7], __fmul_rn(bf_hi(x.w), bf_hi(y.w)));
  }
}
// exact importance of candidate block `id` for local query i of block c, in "sum over 64 keys" units.
// qv: the query row (bf16 words) held in thread-local storage.  Only the final scalar combine is fp64.
template <int D>
__device__ __noinline__ double exact_imp(const uint4* qv, const float* ps8h, const u16* Kc, int id, int c, int i) {
  float s[8], cc[8];
#pragma unroll
  for (int e = 0; e < 8; e++) { s[e] = 0.f; cc[e] = 0.f; }
  if (id < c) {
    dot_qf<D>(s, cc, qv, reinterpret_cast<const float4*>(ps8h + ((size_t)id * 8 + 7) * D));
  } else {
    const int sfull = (i + 1) >> 3;
    if (sfull > 0) dot_qf<D>(s, cc, qv, reinterpret_cast<const float4*>(ps8h + ((size_t)c * 8 + sfull - 1) * D));
    for (int j = sfull * 8; j <= i; j++) dot_qk<D>(s, cc, qv, reinterpret_cast<const uint4*>(Kc + (size_t)j * D));
  }
  float S0 = 0.f, C0 = 0.f;
#pragma unroll
  for (int e = 0; e < 8; e++) {
    two_sum(S0, C0, s[e]);
    C0 = __fadd_rn(C0, cc[e]);
  }
  double v = (double)S0 + (double)C0;
  if (id >= c) v = v * 64.0 / (double)(i + 1);
  return v;
}

// pop the current maximum of a score row (two-level: group maxima rg[], values rs[]); ties -> higher index
__device__ __forceinline__ void sel_extract(float* rs, float* rg, int NG, float& outv, int& outi) {
  float best = rg[0];
  int bg = 0;
#pragma unroll 4
  for (int g2 = 1; g2 < NG; g2++) {
    const float v = rg[g2];
    if (v >= best) { best = v; bg = g2; }
  }
  const float4 x = *reinterpret_cast<const float4*>(rs + 8 * bg);
  const float4 y = *reinterpret_cast<const float4*>(rs + 8 * bg + 4);
  const float e[8] = {x.x, x.y, x.z, x.w, y.x, y.y, y.z, y.w};
  int p = 0;
  float mx = e[0];
#pragma unroll
  for (int k = 1; k < 8; k++) {
    if (e[k] >= mx) { mx = e[k]; p = k; }
  }
  float nm = NEGV;
#pragma unroll
  for (int k = 0; k < 8; k++) nm = fmaxf(nm, (k == p) ? NEGV : e[k]);
  rs[8 * bg + p] = NEGV;
  rg[bg] = nm;
  outv = mx;
  outi = 8 * bg + p;
}

template <int D>
__device__ __noinline__ void refine_sel(float* rs, float* rg, int NG, const float* av0, const int* ai0, int n0, float E2,
                                        const u16* qrow, const float* ps8h, const u16* Kc, int c, int i,
                                        int* out) {
  const int RM = 16;
  float xv[RM];
  int xi[RM];
  uint4 qv[D / 8];
  {
    const uint4* q4 = reinterpret_cast<const uint4*>(qrow);
#pragma unroll
    for (int u = 0; u < D / 8; u++) qv[u] = q4[u];
  }
  for (int r = 0; r < n0; r++) { xv[r] = av0[r]; xi[r] = ai0[r]; }
  int n = n0;
  while (n < RM && n <= c && xv[n - 1] >= xv[7] - E2) {
    sel_extract(rs, rg, NG, xv[n], xi[n]);
    n++;
  }
  if (xv[n - 1] >= xv[7] - E2 && n <= c) {
    // too many near ties (degenerate input): exact evaluation of every candidate
    double tv[8];
    int ti[8];
    for (int r = 0; r < 8; r++) { tv[r] = -1.0e300; ti[r] = 0; }
    for (int id = 0; id <= c; id++) {
      double cv = exact_imp<D>(qv, ps8h, Kc, id, c, i);
      int ci = id;
      for (int r = 0; r < 8; r++) {
        if (cv >= tv[r]) {
          const double nv = tv[r]; const int ni = ti[r];
          tv[r] = cv; ti[r] = ci; cv = nv; ci = ni;
        }
      }
    }
    for (int r = 0; r < 8; r++) out[r] = ti[r];
    return;
  }
  const int hi_r = (xv[n - 1] >= xv[7] - E2) ? n - 1 : n - 2;
  int lo_r = 7;
  while (lo_r > 0 && xv[lo_r - 1] <= xv[8] + E2) lo_r--;
  double ex[RM];
  bool used[RM];
  for (int r = lo_r; r <= hi_r; r++) { ex[r] = exact_imp<D>(qv, ps8h, Kc, xi[r], c, i); used[r] = false; }
  for (int r = 0; r < lo_r; r++) out[r] = xi[r];
  for (int m = lo_r; m < 8; m++) {
    int best = -1;
    for (int r = lo_r; r <= hi_r; r++) {
      if (used[r]) continue;
      if (best < 0 || ex[r] > ex[best] || (ex[r] == ex[best] && xi[r] > xi[best])) best = r;
    }
    used[best] = true;
    out[m] = xi[best];
  }
}

#define SEL_CHB 16  // candidate blocks staged per chunk
#define SEL_RA 6    // max ambiguous candidates handled by the cooperative re-check

template <int D>
__global__ void __launch_bounds__(128) k_select(
    const u16* __restrict__ Q, const u16* __restrict__ K, const u16* __restrict__ V, const u16* __restrict__ kb_hi,
    const u16* __restrict__ kb_lo, const float* __restrict__ ps8, int* __restrict__ cnt,
    u32* __restrict__ lists, const int* __restrict__ loff, u32* __restrict__ meta, int* __restrict__ ctrl,
    int S, int nb, int nbf, int nSel, int listCap, int nbR, int NCAP, int scoreWords, int CD, int kmaxOff) {
  extern __shared__ __align__(16) float smem[];
  float* sS = smem;                      // [64][NCAP] approx importance (first used as the K block c stage)
  float* sG = smem + scoreWords;         // [64][NCAP/8] group maxima
  u32* sB = reinterpret_cast<u32*>(smem + scoreWords + 64 * (NCAP / 8));  // [2][SEL_CHB][D/2] hi|lo operands
  float* sQ1 = smem + scoreWords + 64 * (NCAP / 8) + 2 * SEL_CHB * (D / 2);  // [64] |q|_1 per query row
  const int tid = threadIdx.x, lane = tid & 31, warp = tid >> 5, g = lane >> 2, cc = lane & 3;
  const int head = blockIdx.x / nSel;
  const int c = 8 + blockIdx.x % nSel;
  const size_t hoff = (size_t)head * S * D;
  const int rl0 = warp * 16 + g, rl1 = rl0 + 8;
  const int tq0 = min(c * 64 + rl0, S - 1), tq1 = min(c * 64 + rl1, S - 1);
  const int NG = (c >> 3) + 1;
  const u16* Kc = K + hoff + (size_t)c * 64 * D;
  const int nq = min(64, S - c * 64);
  const u16* kh = kb_hi + (size_t)head * nbf * D;
  const u16* kl = kb_lo + (size_t)head * nbf * D;
  const int nch = (c + SEL_CHB - 1) / SEL_CHB;
  const int NPT = (2 * SEL_CHB * (D / 8)) / 128;  // operand uint4 per thread per chunk

  u32 a[D / 16][4];
  load_q_frags<D>(a, Q + hoff + (size_t)tq0 * D, Q + hoff + (size_t)tq1 * D, cc);
  // |q|_1 of the two rows (error-scale floor for the near-tie test)
  {
    float qa = 0.f, qb = 0.f;
#pragma unroll
    for (int sx = 0; sx < D / 16; sx++) {
      const u32 w0 = a[sx][0] & 0x7fff7fffu, w2 = a[sx][2] & 0x7fff7fffu;
      const u32 w1 = a[sx][1] & 0x7fff7fffu, w3 = a[sx][3] & 0x7fff7fffu;
      qa += (bf_lo(w0) + bf_hi(w0)) + (bf_lo(w2) + bf_hi(w2));
      qb += (bf_lo(w1) + bf_hi(w1)) + (bf_lo(w3) + bf_hi(w3));
    }
    qa = grp_sum(qa);
    qb = grp_sum(qb);
    if (cc == 0) { sQ1[rl0] = qa; sQ1[rl1] = qb; }
  }
  const float kmaxHead = __uint_as_float((u32)ctrl[kmaxOff + head]);
  // prefetch this block's V rows into L2 (one touch per 128-byte line; nothing waits on it)
  u32 vtouch = 0;
  if (tid * 128 < nq * D * 2) {
    const volatile u32* vp = reinterpret_cast<const volatile u32*>(V + hoff + (size_t)c * 64 * D) + tid * 32;
    vtouch = vp[0];
  }
  // operands of the first chunk of block sums (hi | lo), kept in registers until staged
  uint4 nx[NPT];
#pragma unroll
  for (int e = 0; e < NPT; e++) {
    const int i = tid + e * 128;
    const int sp = i / (SEL_CHB * (D / 8)), r = i % (SEL_CHB * (D / 8));
    const int blk = min(r / (D / 8), c - 1);
    nx[e] = reinterpret_cast<const uint4*>((sp ? kl : kh) + (size_t)blk * D)[r % (D / 8)];
  }
  // stage key block c (natural layout) into the score area and form the causal partial sums
  {
    const uint4* k4 = reinterpret_cast<const uint4*>(Kc);
    uint4* s4 = reinterpret_cast<uint4*>(sS);
#pragma unroll
    for (int x = tid; x < 64 * (D / 8); x += 128) {
      const int key = x / (D / 8);
      s4[x] = k4[(size_t)min(key, nq - 1) * (D / 8) + (x - key * (D / 8))];
    }
  }
  __syncthreads();
  float cur0, cur1;
  {
    float sc[8][4];
    qk_tile<D>(sc, a, reinterpret_cast<const u32*>(sS), g, cc);
    float sum0 = 0.f, sum1 = 0.f;
#pragma unroll
    for (int j = 0; j < 8; j++) {
      const int k0 = 8 * j + 2 * cc, k1 = k0 + 1;
      sum0 += ((k0 <= rl0) ? sc[j][0] : 0.f) + ((k1 <= rl0) ? sc[j][1] : 0.f);
      sum1 += ((k0 <= rl1) ? sc[j][2] : 0.f) + ((k1 <= rl1) ? sc[j][3] : 0.f);
    }
    cur0 = grp_sum(sum0) * (64.0f / (float)(rl0 + 1));
    cur1 = grp_sum(sum1) * (64.0f / (float)(rl1 + 1));
  }
  __syncthreads();
  if (tid < 64) {
    for (int idx = c + 1; idx < 8 * NG; idx++) sS[tid * NCAP + idx] = NEGV;
  }
  if (cc == 0) {
    sS[rl0 * NCAP + c] = cur0;
    sS[rl1 * NCAP + c] = cur1;
  }
  // full blocks 0..c-1 in chunks of SEL_CHB: q . (hi + lo), operands staged once per CTA
  for (int ch = 0; ch < nch; ch++) {
    {
      uint4* b4 = reinterpret_cast<uint4*>(sB);
#pragma unroll
      for (int e = 0; e < NPT; e++) b4[tid + e * 128] = nx[e];
    }
    __syncthreads();
    if (ch + 1 < nch) {
#pragma unroll
      for (int e = 0; e < NPT; e++) {
        const int i = tid + e * 128;
        const int sp = i / (SEL_CHB * (D / 8)), r = i % (SEL_CHB * (D / 8));
        const int blk = min((ch + 1) * SEL_CHB + r / (D / 8), c - 1);
        nx[e] = reinterpret_cast<const uint4*>((sp ? kl : kh) + (size_t)blk * D)[r % (D / 8)];
      }
    }
    float chh[SEL_CHB / 8][4], cll[SEL_CHB / 8][4];
#pragma unroll
    for (int x = 0; x < SEL_CHB / 8; x++) {
      chh[x][0] = 0.f; chh[x][1] = 0.f; chh[x][2] = 0.f; chh[x][3] = 0.f;
      cll[x][0] = 0.f; cll[x][1] = 0.f; cll[x][2] = 0.f; cll[x][3] = 0.f;
    }
    const u32* bh = sB + g * (D / 2) + cc * (D / 8);
    const u32* bl = bh + SEL_CHB * (D / 2);
#pragma unroll
    for (int sx = 0; sx < D / 16; sx++) {
#pragma unroll
      for (int x = 0; x < SEL_CHB / 8; x++) {
        const uint2 vh = *reinterpret_cast<const uint2*>(bh + x * 8 * (D / 2) + 2 * sx);
        const uint2 vl = *reinterpret_cast<const uint2*>(bl + x * 8 * (D / 2) + 2 * sx);
        mma16816(chh[x], a[sx][0], a[sx][1], a[sx][2], a[sx][3], vh.x, vh.y);
        mma16816(cll[x], a[sx][0], a[sx][1], a[sx][2], a[sx][3], vl.x, vl.y);
      }
    }
#pragma unroll
    for (int x = 0; x < SEL_CHB / 8; x++) {
      const int i0 = ch * SEL_CHB + 8 * x + 2 * cc;
      if (i0 + 1 < c) {
        *reinterpret_cast<float2*>(sS + rl0 * NCAP + i0) = make_float2(chh[x][0] + cll[x][0], chh[x][1] + cll[x][1]);
        *reinterpret_cast<float2*>(sS + rl1 * NCAP + i0) = make_float2(chh[x][2] + cll[x][2], chh[x][3] + cll[x][3]);
      } else if (i0 < c) {
        sS[rl0 * NCAP + i0] = chh[x][0] + cll[x][0];
        sS[rl1 * NCAP + i0] = chh[x][2] + cll[x][2];
      }
    }
    __syncthreads();
  }
  if (tid >= 64) return;

  // ---- top-k (thread per query) ----
  const int i = tid;
  const int t = c * 64 + i;
  const bool valid = t < S;
  float* rs = sS + i * NCAP;
  float* rg = sG + i * (NCAP / 8);
  float maxabs = 0.f;
  const u16* qrow = Q + hoff + (size_t)(valid ? t : (S - 1)) * D;
  const float* ps8h = ps8 + (size_t)head * nb * 8 * D;
  float av[9];
  int ai[9];
  if (NG <= 16) {
    // group maxima live in registers: argmax over 16 registers, then one 8-value group in smem
    float gm[16];
#pragma unroll
    for (int g2 = 0; g2 < 16; g2++) {
      gm[g2] = NEGV;
      if (g2 < NG) {
        const float4 x = *reinterpret_cast<const float4*>(rs + 8 * g2);
        const float4 y = *reinterpret_cast<const float4*>(rs + 8 * g2 + 4);
        const float e[8] = {x.x, x.y, x.z, x.w, y.x, y.y, y.z, y.w};
#pragma unroll
        for (int k = 0; k < 8; k++) {
          gm[g2] = fmaxf(gm[g2], e[k]);
          maxabs = fmaxf(maxabs, (e[k] > 0.5f * NEGV) ? fabsf(e[k]) : 0.f);
        }
      }
    }
#pragma unroll
    for (int r = 0; r < 9; r++) {
      float best = gm[0];
      int bg = 0;
#pragma unroll
      for (int k = 1; k < 16; k++) {
        if (gm[k] >= best) { best = gm[k]; bg = k; }
      }
      const float4 x = *reinterpret_cast<const float4*>(rs + 8 * bg);
      const float4 y = *reinterpret_cast<const float4*>(rs + 8 * bg + 4);
      const float e[8] = {x.x, x.y, x.z, x.w, y.x, y.y, y.z, y.w};
      int p = 0;
      float mx = e[0];
#pragma unroll
      for (int k = 1; k < 8; k++) {
        if (e[k] >= mx) { mx = e[k]; p = k; }
      }
      float nm = NEGV;
#pragma unroll
      for (int k = 0; k < 8; k++) nm = fmaxf(nm, (k == p) ? NEGV : e[k]);
      rs[8 * bg + p] = NEGV;
#pragma unroll
      for (int k = 0; k < 16; k++) gm[k] = (k == bg) ? nm : gm[k];
      av[r] = mx;
      ai[r] = 8 * bg + p;
    }
  } else {
#pragma unroll 2
    for (int g2 = 0; g2 < NG; g2++) {
      const float4 x = *reinterpret_cast<const float4*>(rs + 8 * g2);
      const float4 y = *reinterpret_cast<const float4*>(rs + 8 * g2 + 4);
      const float e[8] = {x.x, x.y, x.z, x.w, y.x, y.y, y.z, y.w};
      float gmx = e[0];
#pragma unroll
      for (int k = 0; k < 8; k++) {
        gmx = fmaxf(gmx, e[k]);
        maxabs = fmaxf(maxabs, (e[k] > 0.5f * NEGV) ? fabsf(e[k]) : 0.f);
      }
      rg[g2] = gmx;
    }
#pragma unroll
    for (int r = 0; r < 9; r++) sel_extract(rs, rg, NG, av[r], ai[r]);
  }
#ifdef NSA_DBG_E
  if (valid) {
    // debug: worst |approx - exact| over the candidates not yet popped
    float worst = 0.f;
    uint4 qv[D / 8];
    for (int u = 0; u < D / 8; u++) qv[u] = reinterpret_cast<const uint4*>(qrow)[u];
    for (int id = 0; id <= c; id++) {
      if (rs[id] <= 0.5f * NEGV) continue;
      const double ex = exact_imp<D>(qv, ps8h, Kc, id, c, i);
      worst = fmaxf(worst, (float)(fabs((double)rs[id] - ex)) / maxabs);
    }
    for (int r = 0; r < 9; r++) {
      const double ex = exact_imp<D>(qv, ps8h, Kc, ai[r], c, i);
      worst = fmaxf(worst, (float)(fabs((double)av[r] - ex)) / maxabs);
    }
    atomicMax(&ctrl[5], (int)__float_as_uint(worst));
  }
#endif
  // error scale: the largest candidate, floored by a bound-like term so that inputs whose
  // importances are all tiny relative to their terms (e.g. identical blocks) still re-check
  maxabs = fmaxf(maxabs, SEL_FLOOR * sQ1[i] * kmaxHead);
  const float E2 = SEL_KAPPA2 * maxabs;
  // ---- near-tie re-check.  Rare (a few queries per thousand) but a serial exact evaluation
  // would stall this CTA for microseconds, so the whole warp serves one flagged query at a
  // time: the flagged lane finds the ambiguous candidates, all 32 lanes each take D/32 dims
  // of the exact (compensated fp32) dot products with a single round of loads, and the
  // flagged lane ranks the results (ties to the higher block index).
  {
    const int NDL = D / 32;
    u32 fm = __ballot_sync(0xffffffffu, valid && !(av[7] - av[8] > E2));
    while (fm) {
      const int L = __ffs(fm) - 1;
      fm &= fm - 1;
      const int iL = (tid & ~31) + L;  // query row of lane L
      float* rsL = sS + iL * NCAP;
      float* rgL = sG + iL * (NCAP / 8);
      if (NG <= 16) {
        // the register path does not maintain the group maxima in smem: rebuild them for row iL
        if (lane < NG) {
          const float4 x = *reinterpret_cast<const float4*>(rsL + 8 * lane);
          const float4 y = *reinterpret_cast<const float4*>(rsL + 8 * lane + 4);
          rgL[lane] = fmaxf(fmaxf(fmaxf(x.x, x.y), fmaxf(x.z, x.w)), fmaxf(fmaxf(y.x, y.y), fmaxf(y.z, y.w)));
        }
        __syncwarp();
      }
      int na = 0, lo_r = 8;
      int ids[SEL_RA];
#pragma unroll
      for (int k = 0; k < SEL_RA; k++) ids[k] = 0;
      if (lane == L) {
        float xv[12];
        int xi[12];
#pragma unroll
        for (int r = 0; r < 9; r++) { xv[r] = av[r]; xi[r] = ai[r]; }
#pragma unroll
        for (int r = 9; r < 12; r++) { xv[r] = NEGV; xi[r] = 0; }
        int n = 9;
#pragma unroll
        for (int r = 9; r < 12; r++) {
          if (n == r && r <= c && xv[r - 1] >= xv[7] - E2) {
            sel_extract(rsL, rgL, NG, xv[r], xi[r]);
            n = r + 1;
          }
        }
        const float last = (n == 9) ? xv[8] : (n == 10) ? xv[9] : (n == 11) ? xv[10] : xv[11];
        const bool more = last >= xv[7] - E2;  // the last popped candidate is still inside the band
        const int hi_r = more ? n - 1 : n - 2;
        lo_r = 7;
#pragma unroll
        for (int r = 6; r >= 0; r--) {
          if (lo_r == r + 1 && xv[r] <= xv[8] + E2) lo_r = r;
        }
        na = hi_r - lo_r + 1;
        if ((more && n <= c) || na > SEL_RA) {
          // many-way near tie (degenerate input): serial fallback with exact evaluation
          float tv[16];
          int ti[16], to[8];
#pragma unroll
          for (int r = 0; r < 12; r++) { tv[r] = xv[r]; ti[r] = xi[r]; }
          refine_sel<D>(rsL, rgL, NG, tv, ti, n, E2, qrow, ps8h, Kc, c, i, to);
#pragma unroll
          for (int r = 0; r < 8; r++) ai[r] = to[r];
          na = 0;
        } else {
#pragma unroll
          for (int k = 0; k < SEL_RA; k++) {
#pragma unroll
            for (int r = 0; r < 12; r++) {
              if (r == lo_r + k) ids[k] = xi[r];
            }
          }
        }
#ifdef NSA_DBG_E
        atomicAdd(&ctrl[4], 1);
#endif
      }
      na = __shfl_sync(0xffffffffu, na, L);
#pragma unroll
      for (int k = 0; k < SEL_RA; k++) ids[k] = __shfl_sync(0xffffffffu, ids[k], L);
      if (na == 0) continue;

      // one round of loads: this lane's slice of the query row and of every candidate's exact
      // 64-key (or causal-prefix) key sum, plus the <= 7 loose keys of the causal partial block
      const int sfull = (iL + 1) >> 3;
      bool hasCur = false;
#pragma unroll
      for (int k = 0; k < SEL_RA; k++) hasCur = hasCur || (k < na && ids[k] == c);
      u32 qw[NDL / 2];
      {
        const u32* qp = reinterpret_cast<const u32*>(Q + hoff + (size_t)(c * 64 + iL) * D + lane * NDL);
#pragma unroll
        for (int w = 0; w < NDL / 2; w++) qw[w] = qp[w];
      }
      float pf[SEL_RA][NDL];
#pragma unroll
      for (int k = 0; k < SEL_RA; k++) {
#pragma unroll
        for (int d = 0; d < NDL; d++) pf[k][d] = 0.f;
        if (k < na) {
          const int id = ids[k];
          const bool isc = id == c;
          if (!isc || sfull > 0) {
            const float* pp = ps8h + ((size_t)id * 8 + (isc ? sfull - 1 : 7)) * D + lane * NDL;
#pragma unroll
            for (int d = 0; d < NDL; d++) pf[k][d] = pp[d];
          }
        }
      }
      u32 kw[7][NDL / 2];
#pragma unroll
      for (int jj = 0; jj < 7; jj++) {
#pragma unroll
        for (int w = 0; w < NDL / 2; w++) kw[jj][w] = 0u;
        const int j = 8 * sfull + jj;
        if (hasCur && j <= iL) {
          const u32* kp = reinterpret_cast<const u32*>(Kc + (size_t)j * D + lane * NDL);
#pragma unroll
          for (int w = 0; w < NDL / 2; w++) kw[jj][w] = kp[w];
        }
      }
      float qd[NDL];
#pragma unroll
      for (int w = 0; w < NDL / 2; w++) { qd[2 * w] = bf_lo(qw[w]); qd[2 * w + 1] = bf_hi(qw[w]); }
      float vh[SEL_RA], vl[SEL_RA];  // exact values as normalized (hi, lo) float pairs
      const float nf = (float)(iL + 1);
#pragma unroll
      for (int k = 0; k < SEL_RA; k++) {
        vh[k] = 0.f;
        vl[k] = 0.f;
        if (k < na) {
          float s1 = 0.f, c1 = 0.f;
#pragma unroll
          for (int d = 0; d < NDL; d++) two_prod_acc(s1, c1, qd[d], pf[k][d]);
          if (ids[k] == c) {
#pragma unroll
            for (int jj = 0; jj < 7; jj++) {
#pragma unroll
              for (int w = 0; w < NDL / 2; w++) {
                // bf16 x bf16 products are exact in fp32
                two_sum(s1, c1, __fmul_rn(qd[2 * w], bf_lo(kw[jj][w])));
                two_sum(s1, c1, __fmul_rn(qd[2 * w + 1], bf_hi(kw[jj][w])));
              }
            }
          }
#pragma unroll
          for (int off = 16; off > 0; off >>= 1) {
            const float sx = __shfl_xor_sync(0xffffffffu, s1, off);
            const float cx = __shfl_xor_sync(0xffffffffu, c1, off);
            two_sum(s1, c1, sx);
            c1 = __fadd_rn(c1, cx);
          }
          float h = __fadd_rn(s1, c1);
          float l = __fsub_rn(c1, __fsub_rn(h, s1));
          if (hasCur) {
            // common unit: the causal partial block is a mean over iL+1 keys, the others over 64
            if (ids[k] == c) {
              h *= 64.f;
              l *= 64.f;
            } else {
              const float ph = __fmul_rn(h, nf);
              const float pl = __fadd_rn(__fmaf_rn(h, nf, -ph), __fmul_rn(l, nf));
              h = __fadd_rn(ph, pl);
              l = __fsub_rn(pl, __fsub_rn(h, ph));
            }
          }
          vh[k] = h;
          vl[k] = l;
        }
      }
      if (lane == L) {
        // rank the ambiguous candidates (descending value, ties to the higher block index)
#pragma unroll
        for (int k = 0; k < SEL_RA; k++) {
          if (k < na) {
            int rank = 0;
#pragma unroll
            for (int j = 0; j < SEL_RA; j++) {
              if (j != k && j < na) {
                const bool gt = (vh[j] > vh[k]) ||
                                (vh[j] == vh[k] && (vl[j] > vl[k] || (vl[j] == vl[k] && ids[j] > ids[k])));
                rank += gt ? 1 : 0;
              }
            }
#pragma unroll
            for (int r = 0; r < 8; r++) {
              if (r == lo_r + rank) ai[r] = ids[k];
            }
          }
        }
      }
    }
  }

  if (valid && c < CD) {
    // dense region: the attention kernel only needs the selected-block bitmask
    u32 mask = 0;
#pragma unroll
    for (int r = 0; r < 8; r++) mask |= 1u << ai[r];
    meta[(size_t)head * S + t] = mask | (vtouch & 0u);
  } else if (valid) {
    // append the far-field pairs to their key-block lists: all atomics first, then the stores
    int pos[8], off[8];
#pragma unroll
    for (int r = 0; r < 8; r++) {
      const int id = ai[r];
      pos[r] = 0;
      off[r] = 0;
      if (id < c - 1) {
        off[r] = loff[id];
        pos[r] = atomicAdd(&cnt[head * nbR + id], 1);
      }
    }
    int k = 0;
    u32 hasP = 0;
#pragma unroll
    for (int r = 0; r < 8; r++) {
      const int id = ai[r];
      if (id == c - 1) {
        hasP = 1;
      } else if (id != c) {
        lists[(size_t)head * listCap + off[r] + pos[r]] = (u32)t | ((u32)k << 16);
        k++;
      }
    }
    meta[(size_t)head * S + t] = (u32)k | (hasP << 8) | (vtouch & 0u);
  }
}

// ---------------------------------------------------------------------------------
// k_attn: persistent workers (4 warps) with an in-kernel task scheduler.  Global loads cost
// hundreds of cycles and L2<->SM bandwidth is the scarce resource, so every task issues its
// loads early and the three task kinds are chosen to minimise bytes moved:
//   DENSE ticket  (query block c < CD): flash-style masked attention over key blocks 0..c,
//     next key block prefetched into registers; no intermediate global traffic at all.
//   REMOTE ticket (far field of query blocks c >= CD): a chunk of (query, key block) pairs of
//     one key-block list.  Key block staged in smem, query rows gathered, QK^T (mma) ->
//     block softmax -> PV (mma); normalized partial (bf16) + log2-sum-exp go to the query slot.
//   LOCAL ticket  (query block c >= CD): key blocks c-1 and c (sliding window + causal) with
//     online softmax, interleaved merge of the query's far-field partials, bf16 output.
//   Dense tickets are implicit (claimable immediately, longest first); CTA 0 meanwhile turns
//   the pair counts into the ticket table  R(h0) R(h1) L(h0) R(h2) L(h1) ...  so partials are
//   consumed while still L2-resident.
// ---------------------------------------------------------------------------------
struct AttnParams {
  const u16* Q;
  const u16* K;
  const u16* V;
  u16* out;
  const u32* lists;
  const int* loff;
  const int* cnt;
  int* pos;
  u32* tick;
  int* ctrl;
  const u32* meta;
  u32* part_o;
  float* part_lw;
  int S, NH, nb, nbR, listCap, CD;
  float scale2;
};
#ifndef CH_PAIRS
#define CH_PAIRS 256
#endif
#define CTL_CUR 0
#define CTL_READY 2
#define CTL_NTICK 3
#define CTL_HEAD 16  // per head: [DONE, NT]
#define TK_EXIT 0xffffffffu
#define TK_LOCAL 0x80000000u
#define TK_DENSE 0x40000000u

// Planner (CTA 0): pair counts -> global ticket sequence.  Scratch w (ints, smem when it fits):
//   w[L]            per list:  ticket offset inside its 8-list group | n << 16
//   wg[h*G8 + j]    per group: ticket count, then exclusive prefix inside the head
//   hs[h]           per head:  exclusive prefix of remote tickets (hs[NH] = total)
__device__ __noinline__ void attn_plan(const AttnParams& P, int* w, int tid) {
  const int NH = P.NH, nbR = P.nbR, nb = P.nb;
  const int nLoc = nb > P.CD ? nb - P.CD : 0;  // LOCAL tickets per head
  const int nLists = NH * nbR;
  const int G8 = (nbR + 7) >> 3;
  int* wg = w + nLists;
  int* hs = wg + NH * G8;
  // pair counts (all loads of a pass are issued before any store)
  for (int base = tid; base < nLists; base += 128 * 8) {
    int v[8];
#pragma unroll
    for (int e = 0; e < 8; e++) { const int L = base + 128 * e; v[e] = (L < nLists) ? P.cnt[L] : 0; }
#pragma unroll
    for (int e = 0; e < 8; e++) { const int L = base + 128 * e; if (L < nLists) w[L] = v[e]; }
  }
  __threadfence();
  __syncthreads();
  // groups of 8 lists
  for (int gi = tid; gi < NH * G8; gi += 128) {
    const int h = gi / G8, j = gi % G8;
    int v[8];
#pragma unroll
    for (int e = 0; e < 8; e++) { const int bi = 8 * j + e; v[e] = (bi < nbR) ? w[h * nbR + bi] : 0; }
    int run = 0;
#pragma unroll
    for (int e = 0; e < 8; e++) {
      const int bi = 8 * j + e;
      if (bi < nbR) w[h * nbR + bi] = run | (v[e] << 16);
      run += (v[e] + CH_PAIRS - 1) / CH_PAIRS;
    }
    wg[gi] = run;
  }
  __threadfence();
  __syncthreads();
  // groups inside a head
  for (int h = tid; h < NH; h += 128) {
    int run = 0;
    for (int j0 = 0; j0 < G8; j0 += 8) {
      int v[8];
#pragma unroll
      for (int e = 0; e < 8; e++) v[e] = (j0 + e < G8) ? wg[h * G8 + j0 + e] : 0;
#pragma unroll
      for (int e = 0; e < 8; e++) {
        if (j0 + e < G8) wg[h * G8 + j0 + e] = run;
        run += v[e];
      }
    }
    hs[h + 1] = run;
  }
  __threadfence();
  __syncthreads();
  if (tid == 0) {
    int run = 0;
    for (int h0 = 0; h0 < NH; h0 += 8) {
      int v[8];
#pragma unroll
      for (int e = 0; e < 8; e++) v[e] = (h0 + e < NH) ? hs[h0 + e + 1] : 0;
#pragma unroll
      for (int e = 0; e < 8; e++) {
        if (h0 + e < NH) {
          hs[h0 + e] = run;
          P.ctrl[CTL_HEAD + 2 * (h0 + e) + 1] = v[e];
        }
        run += v[e];
      }
    }
    hs[NH] = run;
    P.ctrl[CTL_NTICK] = run + NH * nLoc;
  }
  __threadfence();
  __syncthreads();
  for (int L = tid; L < nLists; L += 128) {
    const int h = L / nbR, bi = L % nbR;
    const int v = w[L];
    const int n = v >> 16;
    const int base = hs[h] + nLoc * max(h - 1, 0) + wg[h * G8 + (bi >> 3)] + (v & 0xffff);
    for (int k = 0; k * CH_PAIRS < n; k++) {
      P.tick[2 * (base + k)] = (u32)L;
      P.tick[2 * (base + k) + 1] = (u32)(k * CH_PAIRS) | ((u32)min(CH_PAIRS, n - k * CH_PAIRS) << 20);
    }
  }
  for (int i = tid; i < NH * nLoc; i += 128) {
    const int h = i / nLoc, c = P.CD + i % nLoc;
    const int base = hs[min(h + 2, NH)] + nLoc * h;
    P.tick[2 * (base + i % nLoc)] = TK_LOCAL | (u32)(h * nb + c);
    P.tick[2 * (base + i % nLoc) + 1] = 0;
  }
  __threadfence();
  __syncthreads();
  if (tid == 0) {
    P.ctrl[CTL_READY] = 1;
    __threadfence();
  }
}

// far-field partial slots: load / accumulate two slots (both rows of this thread)
#define SLOT_LOAD(K_, T0_, T1_)                                                                   \
  if ((K_) < nmax) {                                                                              \
    const uint4* s0_ = reinterpret_cast<const uint4*>(P.part_o + (q0 + (K_)) * (D / 2) + cc * (D / 8)); \
    const uint4* s1_ = reinterpret_cast<const uint4*>(P.part_o + (q1 + (K_)) * (D / 2) + cc * (D / 8)); \
    _Pragma("unroll") for (int u_ = 0; u_ < D / 32; u_++) { T0_[u_] = s0_[u_]; T1_[u_] = s1_[u_]; } \
  }
#define SLOT_FMA(K_, T0_, T1_)                                                                    \
  if ((K_) < nmax) {                                                                              \
    const bool in0_ = (K_) < nr0, in1_ = (K_) < nr1;                                              \
    const float w0_ = in0_ ? ex2f(lw0[K_] - m0) : 0.f;                                            \
    const float w1_ = in1_ ? ex2f(lw1[K_] - m1) : 0.f;                                            \
    const u32 k0_ = in0_ ? 0xffffffffu : 0u, k1_ = in1_ ? 0xffffffffu : 0u;                       \
    l0 += w0_;                                                                                    \
    l1 += w1_;                                                                                    \
    _Pragma("unroll") for (int u_ = 0; u_ < D / 32; u_++) {                                       \
      const uint4 x_ = T0_[u_];                                                                   \
      const uint4 y_ = T1_[u_];                                                                   \
      o[4 * u_ + 0][0] = fmaf(w0_, bf_lo(x_.x & k0_), o[4 * u_ + 0][0]); o[4 * u_ + 0][1] = fmaf(w0_, bf_hi(x_.x & k0_), o[4 * u_ + 0][1]); \
      o[4 * u_ + 1][0] = fmaf(w0_, bf_lo(x_.y & k0_), o[4 * u_ + 1][0]); o[4 * u_ + 1][1] = fmaf(w0_, bf_hi(x_.y & k0_), o[4 * u_ + 1][1]); \
      o[4 * u_ + 2][0] = fmaf(w0_, bf_lo(x_.z & k0_), o[4 * u_ + 2][0]); o[4 * u_ + 2][1] = fmaf(w0_, bf_hi(x_.z & k0_), o[4 * u_ + 2][1]); \
      o[4 * u_ + 3][0] = fmaf(w0_, bf_lo(x_.w & k0_), o[4 * u_ + 3][0]); o[4 * u_ + 3][1] = fmaf(w0_, bf_hi(x_.w & k0_), o[4 * u_ + 3][1]); \
      o[4 * u_ + 0][2] = fmaf(w1_, bf_lo(y_.x & k1_), o[4 * u_ + 0][2]); o[4 * u_ + 0][3] = fmaf(w1_, bf_hi(y_.x & k1_), o[4 * u_ + 0][3]); \
      o[4 * u_ + 1][2] = fmaf(w1_, bf_lo(y_.y & k1_), o[4 * u_ + 1][2]); o[4 * u_ + 1][3] = fmaf(w1_, bf_hi(y_.y & k1_), o[4 * u_ + 1][3]); \
      o[4 * u_ + 2][2] = fmaf(w1_, bf_lo(y_.z & k1_), o[4 * u_ + 2][2]); o[4 * u_ + 2][3] = fmaf(w1_, bf_hi(y_.z & k1_), o[4 * u_ + 2][3]); \
      o[4 * u_ + 3][2] = fmaf(w1_, bf_lo(y_.w & k1_), o[4 * u_ + 3][2]); o[4 * u_ + 3][3] = fmaf(w1_, bf_hi(y_.w & k1_), o[4 * u_ + 3][3]); \
    }                                                                                             \
  }

// masked online-softmax step for one key block of the LOCAL task (updates m, l, rescales o, builds pa)
#define LOCAL_SOFTMAX()                                                                           \
  {                                                                                               \
    float mx0 = NEG_BIG, mx1 = NEG_BIG;                                                           \
    _Pragma("unroll") for (int j = 0; j < 8; j++) {                                               \
      const int k0 = 8 * j + 2 * cc, k1 = k0 + 1;                                                 \
      sc[j][0] = (k0 >= lo0 && k0 <= hi0) ? sc[j][0] * scale2 : NEG_BIG;                          \
      sc[j][1] = (k1 >= lo0 && k1 <= hi0) ? sc[j][1] * scale2 : NEG_BIG;                          \
      sc[j][2] = (k0 >= lo1 && k0 <= hi1) ? sc[j][2] * scale2 : NEG_BIG;                          \
      sc[j][3] = (k1 >= lo1 && k1 <= hi1) ? sc[j][3] * scale2 : NEG_BIG;                          \
      mx0 = fmaxf(mx0, fmaxf(sc[j][0], sc[j][1]));                                                \
      mx1 = fmaxf(mx1, fmaxf(sc[j][2], sc[j][3]));                                                \
    }                                                                                             \
    mx0 = fmaxf(grp_max(mx0), m0);                                                                \
    mx1 = fmaxf(grp_max(mx1), m1);                                                                \
    const float al0 = ex2f(m0 - mx0), al1 = ex2f(m1 - mx1);                                       \
    m0 = mx0;                                                                                     \
    m1 = mx1;                                                                                     \
    float s0 = 0.f, s1 = 0.f;                                                                     \
    _Pragma("unroll") for (int j = 0; j < 8; j++) {                                               \
      const float p0 = (sc[j][0] > 0.5f * NEG_BIG) ? ex2f(sc[j][0] - m0) : 0.f;                   \
      const float p1 = (sc[j][1] > 0.5f * NEG_BIG) ? ex2f(sc[j][1] - m0) : 0.f;                   \
      const float p2 = (sc[j][2] > 0.5f * NEG_BIG) ? ex2f(sc[j][2] - m1) : 0.f;                   \
      const float p3 = (sc[j][3] > 0.5f * NEG_BIG) ? ex2f(sc[j][3] - m1) : 0.f;                   \
      s0 += p0 + p1;                                                                              \
      s1 += p2 + p3;                                                                              \
      pa[j >> 1][(j & 1) * 2 + 0] = pack_bf16(p0, p1);                                            \
      pa[j >> 1][(j & 1) * 2 + 1] = pack_bf16(p2, p3);                                            \
    }                                                                                             \
    l0 = l0 * al0 + grp_sum(s0);                                                                  \
    l1 = l1 * al1 + grp_sum(s1);                                                                  \
    _Pragma("unroll") for (int jd = 0; jd < D / 8; jd++) { o[jd][0] *= al0; o[jd][1] *= al0; o[jd][2] *= al1; o[jd][3] *= al1; } \
  }

template <int D>
__device__ __forceinline__ void remote_task(const AttnParams& P, u32* sK, u32* sV, u32 w0, u32 w1, bool need_stage) {
  const int tid = threadIdx.x, lane = tid & 31, warp = tid >> 5, g = lane >> 2, cc = lane & 3;
  const int S = P.S;
  const float scale2 = P.scale2;
  // ---------------- REMOTE ----------------
  const int L = (int)w0, start = (int)(w1 & 0xfffffu), end = start + (int)(w1 >> 20);
  const int head = L / P.nbR, bi = L % P.nbR;
  const size_t hoff = (size_t)head * S * D;
  const u32* lb = P.lists + (size_t)head * P.listCap + P.loff[bi];
  const u16* Qh = P.Q + hoff;
  const int eb0 = start + warp * 16;  // this warp's first pair in round 0 (rounds advance by 64 pairs)
  // raw list entries of the first two rounds
  u32 un0 = 0, un1 = 0, um0 = 0, um1 = 0;
  if (eb0 < end) {
    un0 = lb[min(eb0 + g, end - 1)];
    un1 = lb[min(eb0 + g + 8, end - 1)];
  }
  if (eb0 + 64 < end) {
    um0 = lb[min(eb0 + 64 + g, end - 1)];
    um1 = lb[min(eb0 + 64 + g + 8, end - 1)];
  }
  if (need_stage) {
    stage_kv<D>(sK, sV, P.K + hoff + (size_t)bi * 64 * D, P.V + hoff + (size_t)bi * 64 * D, 64, tid);
  }
  __syncthreads();
  if (eb0 < end) {
    // current round state
    int e0 = eb0 + g, e1 = e0 + 8;
    bool v0 = e0 < end, v1 = e1 < end;
    int ec0 = min(e0, end - 1), ec1 = min(e1, end - 1);
    int t0 = (int)(un0 & 0xffff);
    int t1 = (int)(un1 & 0xffff);
    int k0 = (int)(un0 >> 16);
    int k1 = (int)(un1 >> 16);
    u32 a[D / 16][4];
    load_q_frags<D>(a, Qh + (size_t)t0 * D, Qh + (size_t)t1 * D, cc);
    for (int eb = eb0;; eb += 64) {
      float sc[8][4];
      qk_tile<D>(sc, a, sK, g, cc);
      // gather the next round's query rows while this round computes
      const bool more = eb + 64 < end;
      int nt0 = 0, nt1 = 0, nk0 = 0, nk1 = 0;
      bool nv0 = false, nv1 = false;
      if (more) {
        const int f0 = eb + 64 + g, f1 = f0 + 8;
        nv0 = f0 < end; nv1 = f1 < end;
        const int fc0 = min(f0, end - 1), fc1 = min(f1, end - 1);
        nt0 = (int)(um0 & 0xffff);
        nt1 = (int)(um1 & 0xffff);
        nk0 = (int)(um0 >> 16);
        nk1 = (int)(um1 >> 16);
        load_q_frags<D>(a, Qh + (size_t)nt0 * D, Qh + (size_t)nt1 * D, cc);
        if (eb + 128 < end) {
          um0 = lb[min(eb + 128 + g, end - 1)];
          um1 = lb[min(eb + 128 + g + 8, end - 1)];
        }
      }
      float m0 = NEG_BIG, m1 = NEG_BIG;
#pragma unroll
      for (int j = 0; j < 8; j++) {
        sc[j][0] *= scale2; sc[j][1] *= scale2; sc[j][2] *= scale2; sc[j][3] *= scale2;
        m0 = fmaxf(m0, fmaxf(sc[j][0], sc[j][1]));
        m1 = fmaxf(m1, fmaxf(sc[j][2], sc[j][3]));
      }
      m0 = grp_max(m0);
      m1 = grp_max(m1);
      float l0 = 0.f, l1 = 0.f;
      u32 pa[4][4];
#pragma unroll
      for (int j = 0; j < 8; j++) {
        const float p0 = ex2f(sc[j][0] - m0), p1 = ex2f(sc[j][1] - m0);
        const float p2 = ex2f(sc[j][2] - m1), p3 = ex2f(sc[j][3] - m1);
        l0 += p0 + p1;
        l1 += p2 + p3;
        pa[j >> 1][(j & 1) * 2 + 0] = pack_bf16(p0, p1);
        pa[j >> 1][(j & 1) * 2 + 1] = pack_bf16(p2, p3);
      }
      l0 = grp_sum(l0);
      l1 = grp_sum(l1);
      float o[D / 8][4];
#pragma unroll
      for (int jd = 0; jd < D / 8; jd++) { o[jd][0] = 0.f; o[jd][1] = 0.f; o[jd][2] = 0.f; o[jd][3] = 0.f; }
      pv_tile<D>(o, pa, sV, g, cc);
      const float i0 = 1.0f / l0, i1 = 1.0f / l1;
      if (v0) {
        const size_t slot = ((size_t)head * S + t0) * 8 + k0;
        uint4* dst = reinterpret_cast<uint4*>(P.part_o + slot * (D / 2) + cc * (D / 8));
#pragma unroll
        for (int u = 0; u < D / 32; u++) {
          uint4 w;
          w.x = pack_bf16(o[4 * u + 0][0] * i0, o[4 * u + 0][1] * i0);
          w.y = pack_bf16(o[4 * u + 1][0] * i0, o[4 * u + 1][1] * i0);
          w.z = pack_bf16(o[4 * u + 2][0] * i0, o[4 * u + 2][1] * i0);
          w.w = pack_bf16(o[4 * u + 3][0] * i0, o[4 * u + 3][1] * i0);
          dst[u] = w;
        }
        if (cc == 0) P.part_lw[slot] = m0 + lg2f(l0);
      }
      if (v1) {
        const size_t slot = ((size_t)head * S + t1) * 8 + k1;
        uint4* dst = reinterpret_cast<uint4*>(P.part_o + slot * (D / 2) + cc * (D / 8));
#pragma unroll
        for (int u = 0; u < D / 32; u++) {
          uint4 w;
          w.x = pack_bf16(o[4 * u + 0][2] * i1, o[4 * u + 0][3] * i1);
          w.y = pack_bf16(o[4 * u + 1][2] * i1, o[4 * u + 1][3] * i1);
          w.z = pack_bf16(o[4 * u + 2][2] * i1, o[4 * u + 2][3] * i1);
          w.w = pack_bf16(o[4 * u + 3][2] * i1, o[4 * u + 3][3] * i1);
          dst[u] = w;
        }
        if (cc == 0) P.part_lw[slot] = m1 + lg2f(l1);
      }
      if (!more) break;
      t0 = nt0; t1 = nt1; k0 = nk0; k1 = nk1; v0 = nv0; v1 = nv1;
    }
  }
  __threadfence();
  __syncthreads();
  if (tid == 0) atomicAdd(P.ctrl + CTL_HEAD + 2 * head, 1);
}

template <int D>
__device__ __forceinline__ void local_task(const AttnParams& P, u32* sK, u32* sV, u32 w0) {
  const int tid = threadIdx.x, lane = tid & 31, warp = tid >> 5, g = lane >> 2, cc = lane & 3;
  const int S = P.S;
  const float scale2 = P.scale2;
  const int li = (int)(w0 & 0x3fffffffu);
  const int head = li / P.nb, c = li % P.nb;  // c >= CD >= 8
  const size_t hoff = (size_t)head * S * D;
  const int rl0 = warp * 16 + g, rl1 = rl0 + 8;
  const int t0 = c * 64 + rl0, t1 = c * 64 + rl1;
  const bool v0 = t0 < S, v1 = t1 < S;
  const int tq0 = min(t0, S - 1), tq1 = min(t1, S - 1);
  const size_t q0 = ((size_t)head * S + tq0) * 8;
  const size_t q1 = ((size_t)head * S + tq1) * 8;
  const int nmax = 8;
  // meta: low byte = number of far-field partial slots, bit 8 = block c-1 fully selected
  const u32 meta0 = P.meta[(size_t)head * S + tq0];
  const u32 meta1 = P.meta[(size_t)head * S + tq1];
  float lw0[8], lw1[8];
  {
    const float4* p0 = reinterpret_cast<const float4*>(P.part_lw + q0);
    const float4* p1 = reinterpret_cast<const float4*>(P.part_lw + q1);
    const float4 x0 = p0[0], x1 = p0[1], y0 = p1[0], y1 = p1[1];
    lw0[0] = x0.x; lw0[1] = x0.y; lw0[2] = x0.z; lw0[3] = x0.w; lw0[4] = x1.x; lw0[5] = x1.y; lw0[6] = x1.z; lw0[7] = x1.w;
    lw1[0] = y0.x; lw1[1] = y0.y; lw1[2] = y0.z; lw1[3] = y0.w; lw1[4] = y1.x; lw1[5] = y1.y; lw1[6] = y1.z; lw1[7] = y1.w;
  }
  u32 a[D / 16][4];
  load_q_frags<D>(a, P.Q + hoff + (size_t)tq0 * D, P.Q + hoff + (size_t)tq1 * D, cc);
  uint4 ta0[D / 32], ta1[D / 32], tb0[D / 32], tb1[D / 32];
  SLOT_LOAD(0, ta0, ta1)
  SLOT_LOAD(1, tb0, tb1)
  stage_kv<D>(sK, sV, P.K + hoff + (size_t)(c - 1) * 64 * D, P.V + hoff + (size_t)(c - 1) * 64 * D, 64, tid);
  __syncthreads();
  const int nr0 = meta0 & 0xff, nr1 = meta1 & 0xff;
  float m0 = NEG_BIG, m1 = NEG_BIG, l0 = 0.f, l1 = 0.f;
#pragma unroll
  for (int k = 0; k < 8; k++) {
    if (k < nr0) m0 = fmaxf(m0, lw0[k]);
    if (k < nr1) m1 = fmaxf(m1, lw1[k]);
  }
  float o[D / 8][4];
#pragma unroll
  for (int jd = 0; jd < D / 8; jd++) { o[jd][0] = 0.f; o[jd][1] = 0.f; o[jd][2] = 0.f; o[jd][3] = 0.f; }
  float sc[8][4];
  u32 pa[4][4];
  {
    // key block c-1: whole block if it was selected, else only the sliding-window tail
    const int lo0 = ((meta0 >> 8) & 1u) ? 0 : rl0 + 1;
    const int lo1 = ((meta1 >> 8) & 1u) ? 0 : rl1 + 1;
    const int hi0 = 63, hi1 = 63;
    qk_tile<D>(sc, a, sK, g, cc);
    LOCAL_SOFTMAX()
    SLOT_FMA(0, ta0, ta1)
    SLOT_FMA(1, tb0, tb1)
    SLOT_LOAD(2, ta0, ta1)
    SLOT_LOAD(3, tb0, tb1)
    pv_tile<D>(o, pa, sV, g, cc);
    SLOT_FMA(2, ta0, ta1)
    SLOT_FMA(3, tb0, tb1)
    SLOT_LOAD(4, ta0, ta1)
    SLOT_LOAD(5, tb0, tb1)
    load_q_frags<D>(a, P.Q + hoff + (size_t)tq0 * D, P.Q + hoff + (size_t)tq1 * D, cc);
    __syncthreads();
    stage_kv<D>(sK, sV, P.K + hoff + (size_t)c * 64 * D, P.V + hoff + (size_t)c * 64 * D, min(64, S - c * 64), tid);
    __syncthreads();
    SLOT_FMA(4, ta0, ta1)
    SLOT_FMA(5, tb0, tb1)
  }
  {
    // key block c: causal
    const int lo0 = 0, lo1 = 0, hi0 = rl0, hi1 = rl1;
    qk_tile<D>(sc, a, sK, g, cc);
    LOCAL_SOFTMAX()
    SLOT_LOAD(6, ta0, ta1)
    SLOT_LOAD(7, tb0, tb1)
    pv_tile<D>(o, pa, sV, g, cc);
    SLOT_FMA(6, ta0, ta1)
    SLOT_FMA(7, tb0, tb1)
  }
  const float i0 = 1.0f / l0, i1 = 1.0f / l1;
  if (v0) {
    u32* dst = reinterpret_cast<u32*>(P.out + hoff + (size_t)t0 * D) + cc;
#pragma unroll
    for (int jd = 0; jd < D / 8; jd++) dst[4 * jd] = pack_bf16(o[jd][0] * i0, o[jd][1] * i0);
  }
  if (v1) {
    u32* dst = reinterpret_cast<u32*>(P.out + hoff + (size_t)t1 * D) + cc;
#pragma unroll
    for (int jd = 0; jd < D / 8; jd++) dst[4 * jd] = pack_bf16(o[jd][2] * i1, o[jd][3] * i1);
  }
}

template <int D>
__device__ __forceinline__ void dense_task(const AttnParams& P, u32* sK, u32* sV, int head, int c) {
  const int tid = threadIdx.x, lane = tid & 31, warp = tid >> 5, g = lane >> 2, cc = lane & 3;
  const int S = P.S;
  const float scale2 = P.scale2;
  const size_t hoff = (size_t)head * S * D;
  const int rl0 = warp * 16 + g, rl1 = rl0 + 8;
  const int t0 = c * 64 + rl0, t1 = c * 64 + rl1;
  const bool v0 = t0 < S, v1 = t1 < S;
  const int tq0 = min(t0, S - 1), tq1 = min(t1, S - 1);
  // selected-block bitmasks (every causal block is selected while there are at most 8)
  u32 mask0 = 0xffffffffu, mask1 = 0xffffffffu;
  if (c >= 8) {
    mask0 = P.meta[(size_t)head * S + tq0];
    mask1 = P.meta[(size_t)head * S + tq1];
  }
  u32 a[D / 16][4];
  load_q_frags<D>(a, P.Q + hoff + (size_t)tq0 * D, P.Q + hoff + (size_t)tq1 * D, cc);
  StageRegs<D> R;
  stage_load<D>(R, P.K + hoff, P.V + hoff, min(64, S), tid);
  stage_store<D>(sK, sV, R, tid);
  __syncthreads();
  float m0 = NEG_BIG, m1 = NEG_BIG, l0 = 0.f, l1 = 0.f;
  float o[D / 8][4];
#pragma unroll
  for (int jd = 0; jd < D / 8; jd++) { o[jd][0] = 0.f; o[jd][1] = 0.f; o[jd][2] = 0.f; o[jd][3] = 0.f; }
  for (int bi = 0; bi <= c; bi++) {
    // fetch the next key block into registers while this one is being used
    if (bi < c) {
      stage_load<D>(R, P.K + hoff + (size_t)(bi + 1) * 64 * D, P.V + hoff + (size_t)(bi + 1) * 64 * D,
                    min(64, S - (bi + 1) * 64), tid);
    }
    int lo0, lo1, hi0, hi1;
    if (bi == c) {
      lo0 = 0; lo1 = 0; hi0 = rl0; hi1 = rl1;                 // causal
    } else if (bi == c - 1) {
      lo0 = ((mask0 >> bi) & 1u) ? 0 : rl0 + 1;               // selected, else sliding-window tail
      lo1 = ((mask1 >> bi) & 1u) ? 0 : rl1 + 1;
      hi0 = 63; hi1 = 63;
    } else {
      lo0 = ((mask0 >> bi) & 1u) ? 0 : 64;
      lo1 = ((mask1 >> bi) & 1u) ? 0 : 64;
      hi0 = 63; hi1 = 63;
    }
    if (__any_sync(0xffffffffu, (lo0 <= hi0) || (lo1 <= hi1))) {
      float sc[8][4];
      u32 pa[4][4];
      qk_tile<D>(sc, a, sK, g, cc);
      LOCAL_SOFTMAX()
      pv_tile<D>(o, pa, sV, g, cc);
    }
    if (bi < c) {
      __syncthreads();
      stage_store<D>(sK, sV, R, tid);
      __syncthreads();
    }
  }
  const float i0 = 1.0f / l0, i1 = 1.0f / l1;
  if (v0) {
    u32* dst = reinterpret_cast<u32*>(P.out + hoff + (size_t)t0 * D) + cc;
#pragma unroll
    for (int jd = 0; jd < D / 8; jd++) dst[4 * jd] = pack_bf16(o[jd][0] * i0, o[jd][1] * i0);
  }
  if (v1) {
    u32* dst = reinterpret_cast<u32*>(P.out + hoff + (size_t)t1 * D) + cc;
#pragma unroll
    for (int jd = 0; jd < D / 8; jd++) dst[4 * jd] = pack_bf16(o[jd][2] * i1, o[jd][3] * i1);
  }
}

template <int D>
__global__ void __launch_bounds__(128, 2) k_attn(const AttnParams P) {
  __shared__ __align__(16) u32 sKV[64 * D];
  __shared__ u32 sTask[2];
  u32* const sK = sKV;
  u32* const sV = sKV + 64 * D / 2;
  const int tid = threadIdx.x;
  volatile int* ctl = P.ctrl;
  const int cdn = min(P.nb, P.CD);       // dense query blocks per head
  const int nDenseT = P.NH * cdn;        // implicit dense tickets: all heads' largest block first
  const bool hasTable = P.nb > P.CD;

  if (blockIdx.x == 0) {
    for (int h = tid; h < P.NH; h += 128) P.ctrl[CTL_HEAD + 2 * P.NH + h] = 0;  // k_prep's per-head maxima
  }
  if (blockIdx.x == 0 && hasTable) {
    const int need = P.NH * P.nbR + P.NH * ((P.nbR + 7) >> 3) + P.NH + 2;
    attn_plan(P, (need <= 64 * D) ? reinterpret_cast<int*>(sKV) : P.pos, tid);
  }
  int staged = -1;
  int nTab = -1;  // table size, known once the planner is done (thread 0 only)
  u32 nw0 = TK_EXIT, nw1 = 0;  // pre-claimed next ticket (thread 0 only)
#define CLAIM_NEXT()                                                                     \
  {                                                                                      \
    nw0 = TK_EXIT;                                                                       \
    const int ri_ = atomicAdd(P.ctrl + CTL_CUR, 1);                                      \
    if (ri_ < nDenseT) {                                                                 \
      nw0 = TK_DENSE | (u32)((ri_ % P.NH) * P.nb + (cdn - 1 - ri_ / P.NH));              \
    } else if (hasTable) {                                                               \
      if (nTab < 0) {                                                                    \
        while (ctl[CTL_READY] == 0) {}                                                   \
        nTab = ctl[CTL_NTICK];                                                           \
      }                                                                                  \
      const int ti_ = ri_ - nDenseT;                                                     \
      if (ti_ < nTab) { nw0 = P.tick[2 * ti_]; nw1 = P.tick[2 * ti_ + 1]; }              \
    }                                                                                    \
  }
  if (tid == 0) CLAIM_NEXT()
  for (;;) {
    if (tid == 0) {
      if (nw0 != TK_EXIT && (nw0 & TK_LOCAL)) {
        // far-field partials of this head must be complete
        const int h = (int)(nw0 & 0x3fffffffu) / P.nb;
        while (ctl[CTL_HEAD + 2 * h] != ctl[CTL_HEAD + 2 * h + 1]) {}
      }
      sTask[0] = nw0;
      sTask[1] = nw1;
    }
    __syncthreads();
    const u32 w0 = sTask[0], w1 = sTask[1];
    if (w0 == TK_EXIT) break;
    // claim the next ticket now; it arrives while this task computes
    if (tid == 0) CLAIM_NEXT()
    if (w0 & TK_DENSE) {
      const int li = (int)(w0 & 0x3fffffffu);
      dense_task<D>(P, sK, sV, li / P.nb, li % P.nb);
      staged = -1;
    } else if (w0 & TK_LOCAL) {
      local_task<D>(P, sK, sV, w0);
      staged = -1;
    } else {
      remote_task<D>(P, sK, sV, w0, w1, staged != (int)w0);
      staged = (int)w0;
    }
    __syncthreads();
  }
#undef CLAIM_NEXT
}

// ---------------------------------------------------------------------------------
// k_dense8: sequences short enough to be all-dense (nb <= CD).  8-warp workers, each owning
// two consecutive query blocks (128 queries), so every staged K/V block serves twice as many
// queries -- this path is bound by L2 bytes for key/value staging, not by the tensor cores.
// ---------------------------------------------------------------------------------
template <int D>
__global__ void __launch_bounds__(256, 1) k_dense8(const AttnParams P) {
  __shared__ __align__(16) u32 sKV[64 * D];
  __shared__ int sTask;
  u32* const sK = sKV;
  u32* const sV = sKV + 64 * D / 2;
  const int tid = threadIdx.x, lane = tid & 31, warp = tid >> 5, g = lane >> 2, cc = lane & 3;
  const int S = P.S;
  const float scale2 = P.scale2;
  const int npair = (P.nb + 1) >> 1;  // query-block pairs per head
  const int nT = P.NH * npair;
  if (blockIdx.x == 0) {
    for (int h = tid; h < P.NH; h += 256) P.ctrl[CTL_HEAD + 2 * P.NH + h] = 0;  // k_prep's per-head maxima
  }
  for (;;) {
    if (tid == 0) sTask = atomicAdd(P.ctrl + CTL_CUR, 1);
    __syncthreads();
    const int r = sTask;
    if (r >= nT) break;
    const int head = r % P.NH;
    const int c0 = 2 * (npair - 1 - r / P.NH);  // longest chains first
    const int cq = c0 + (warp >> 2);            // this warp's query block
    const bool blk_ok = cq < P.nb;
    const int cmax = min(c0 + 1, P.nb - 1);
    const size_t hoff = (size_t)head * S * D;
    const int rl0 = (warp & 3) * 16 + g, rl1 = rl0 + 8;
    const int t0 = cq * 64 + rl0, t1 = cq * 64 + rl1;
    const bool v0 = blk_ok && t0 < S, v1 = blk_ok && t1 < S;
    const int tq0 = min(t0, S - 1), tq1 = min(t1, S - 1);
    // selected-block bitmasks (every causal block is selected while there are at most 8)
    u32 mask0 = 0xffffffffu, mask1 = 0xffffffffu;
    if (cq >= 8) {
      mask0 = P.meta[(size_t)head * S + tq0];
      mask1 = P.meta[(size_t)head * S + tq1];
    }
    u32 a[D / 16][4];
    load_q_frags<D>(a, P.Q + hoff + (size_t)tq0 * D, P.Q + hoff + (size_t)tq1 * D, cc);
    StageRegs<D, 256> R;
    stage_load<D, 256>(R, P.K + hoff, P.V + hoff, min(64, S), tid);
    stage_store<D, 256>(sK, sV, R, tid);
    __syncthreads();
    float m0 = NEG_BIG, m1 = NEG_BIG, l0 = 0.f, l1 = 0.f;
    float o[D / 8][4];
#pragma unroll
    for (int jd = 0; jd < D / 8; jd++) { o[jd][0] = 0.f; o[jd][1] = 0.f; o[jd][2] = 0.f; o[jd][3] = 0.f; }
    for (int bi = 0; bi <= cmax; bi++) {
      // fetch the next key block into registers while this one is being used
      if (bi < cmax) {
        stage_load<D, 256>(R, P.K + hoff + (size_t)(bi + 1) * 64 * D, P.V + hoff + (size_t)(bi + 1) * 64 * D,
                           min(64, S - (bi + 1) * 64), tid);
      }
      int lo0, lo1, hi0, hi1;
      if (!blk_ok || bi > cq) {
        lo0 = 64; lo1 = 64; hi0 = 63; hi1 = 63;                 // not causal for this warp's block
      } else if (bi == cq) {
        lo0 = 0; lo1 = 0; hi0 = rl0; hi1 = rl1;                 // causal
      } else if (bi == cq - 1) {
        lo0 = ((mask0 >> bi) & 1u) ? 0 : rl0 + 1;               // selected, else sliding-window tail
        lo1 = ((mask1 >> bi) & 1u) ? 0 : rl1 + 1;
        hi0 = 63; hi1 = 63;
      } else {
        lo0 = ((mask0 >> bi) & 1u) ? 0 : 64;
        lo1 = ((mask1 >> bi) & 1u) ? 0 : 64;
        hi0 = 63; hi1 = 63;
      }
      if (__any_sync(0xffffffffu, (lo0 <= hi0) || (lo1 <= hi1))) {
        float sc[8][4];
        u32 pa[4][4];
        qk_tile<D>(sc, a, sK, g, cc);
        LOCAL_SOFTMAX()
        pv_tile<D>(o, pa, sV, g, cc);
      }
      if (bi < cmax) {
        __syncthreads();
        stage_store<D, 256>(sK, sV, R, tid);
        __syncthreads();
      }
    }
    const float i0 = 1.0f / l0, i1 = 1.0f / l1;
    if (v0) {
      u32* dst = reinterpret_cast<u32*>(P.out + hoff + (size_t)t0 * D) + cc;
#pragma unroll
      for (int jd = 0; jd < D / 8; jd++) dst[4 * jd] = pack_bf16(o[jd][0] * i0, o[jd][1] * i0);
    }
    if (v1) {
      u32* dst = reinterpret_cast<u32*>(P.out + hoff + (size_t)t1 * D) + cc;
#pragma unroll
      for (int jd = 0; jd < D / 8; jd++) dst[4 * jd] = pack_bf16(o[jd][2] * i1, o[jd][3] * i1);
    }
    __syncthreads();
  }
}

// ---------------------------------------------------------------------------------
// host launchers (prep + select first, so the output tensor can be allocated meanwhile)
// ---------------------------------------------------------------------------------
#include <cstdio>
static int g_prof = 0;
static double g_acc[4] = {0, 0, 0, 0};
static int g_n = 0;
static cudaEvent_t g_ev[4];
static int g_ev_init = 0;
void nsa_set_prof(int p) {
  if (p == 2) {
    printf("prof (us): prep %.1f select %.1f attn %.1f  (n=%d)\n", g_acc[0] / g_n, g_acc[1] / g_n, g_acc[2] / g_n, g_n);
    fflush(stdout);
    return;
  }
  g_prof = p;
  g_n = 0;
  for (int i = 0; i < 4; i++) g_acc[i] = 0;
}
#define PROF_MARK(i) if (g_prof) { cudaEventRecord(g_ev[i], st); }

#ifndef NSA_USE_DENSE8
#define NSA_USE_DENSE8 1
#endif

struct NsaDims {
  int nb, nbf, nbR, listCap;
};
static NsaDims nsa_dims(int S, int CD) {
  NsaDims d;
  d.nb = (S + 63) / 64;
  d.nbf = S / 64;
  d.nbR = d.nb > CD ? d.nb - 2 : 0;
  d.listCap = 0;
  for (int bi = 0; bi < d.nbR; bi++) {
    const int cmin = bi + 2 > CD ? bi + 2 : CD;
    d.listCap += S - 64 * cmin > 0 ? S - 64 * cmin : 0;
  }
  return d;
}

template <int D>
static void launch_pre(const u16* Q, const u16* K, const u16* V, float* ps8, u32* kb_hi, u32* kb_lo, int* cnt,
                       u32* lists, const int* loff, u32* meta, int* ctrl, int NH, int S, int CD, cudaStream_t st) {
  const NsaDims d = nsa_dims(S, CD);
  if (g_prof) {
    if (!g_ev_init) { for (int i = 0; i < 4; i++) cudaEventCreate(&g_ev[i]); g_ev_init = 1; }
    cudaStreamSynchronize(st);
  }
  PROF_MARK(0)
  {
    // zero: ctrl[0 .. 16+2*NH) (cursor, flags, per-head counters), cnt[0 .. NH*nbR) (pair counters)
    const int nZc = 16 + 2 * NH, nZn = NH * d.nbR;
    int total = NH * d.nb * D;
    if (total < nZc) total = nZc;
    if (total < nZn) total = nZn;
    k_prep<<<(total + 127) / 128, 128, 0, st>>>(K, ps8, kb_hi, kb_lo, cnt, nZn, ctrl, nZc, NH, S, D, d.nb, d.nbf);
  }
  PROF_MARK(1)
  if (d.nb > 8) {
    const int nSel = d.nb - 8;
    const int NCAP = (d.nb + 7) & ~7;
    const int scoreWords = 64 * NCAP > 32 * D ? 64 * NCAP : 32 * D;  // also holds one staged key block
    const size_t smemSel = (size_t)scoreWords * 4 + (size_t)64 * (NCAP / 8) * 4 + (size_t)2 * SEL_CHB * D * 2 + 64 * 4;
    static int attrSet = 0;
    if (!attrSet) {
      cudaFuncSetAttribute(k_select<D>, cudaFuncAttributeMaxDynamicSharedMemorySize, 96 * 1024);
      attrSet = 1;
    }
    k_select<D><<<NH * nSel, 128, smemSel, st>>>(Q, K, V, (const u16*)kb_hi, (const u16*)kb_lo, ps8, cnt, lists, loff,
                                                meta, ctrl, S, d.nb, d.nbf, nSel, d.listCap, d.nbR, NCAP,
                                                scoreWords, CD, 16 + 2 * NH);
  }
  PROF_MARK(2)
}

template <int D>
static void launch_attn(const u16* Q, const u16* K, const u16* V, u16* out, int* cnt, u32* tick, u32* lists,
                        const int* loff, u32* meta, u32* part_o, float* part_lw, int* ctrl, int NH, int S, int CD,
                        int nWorkers, cudaStream_t st) {
  const NsaDims d = nsa_dims(S, CD);
  AttnParams P;
  P.Q = Q; P.K = K; P.V = V; P.out = out; P.lists = lists; P.loff = loff; P.cnt = cnt; P.pos = cnt + NH * d.nbR;
  P.tick = tick; P.ctrl = ctrl; P.meta = meta; P.part_o = part_o; P.part_lw = part_lw;
  P.S = S; P.NH = NH; P.nb = d.nb; P.nbR = d.nbR; P.listCap = d.listCap; P.CD = CD;
  P.scale2 = 1.4426950408889634f / sqrtf((float)D);
  if (d.nb <= CD && NSA_USE_DENSE8) {
    // all-dense: one 8-warp worker per SM, tickets = (head, pair of query blocks)
    const int nT = NH * ((d.nb + 1) / 2);
    int grid = nWorkers / 2 > 0 ? nWorkers / 2 : 1;
    if (grid > nT) grid = nT;
    k_dense8<D><<<grid, 256, 0, st>>>(P);
  } else {
    k_attn<D><<<nWorkers, 128, 0, st>>>(P);
  }
  PROF_MARK(3)
  if (g_prof) {
    cudaStreamSynchronize(st);
    for (int i = 0; i < 3; i++) {
      float ms = 0;
      cudaEventElapsedTime(&ms, g_ev[i], g_ev[i + 1]);
      g_acc[i] += ms * 1000.0;
    }
    g_n++;
  }
}

void nsa_launch_pre(const void* Q, const void* K, const void* V, void* ps8, void* kb_hi, void* kb_lo, void* cnt,
                    void* lists, const void* loff, void* meta, void* ctrl, int NH, int S, int D, int CD,
                    void* stream) {
  cudaStream_t st = (cudaStream_t)stream;
  if (D == 64) {
    launch_pre<64>((const u16*)Q, (const u16*)K, (const u16*)V, (float*)ps8, (u32*)kb_hi, (u32*)kb_lo, (int*)cnt,
                   (u32*)lists, (const int*)loff, (u32*)meta, (int*)ctrl, NH, S, CD, st);
  } else {
    launch_pre<128>((const u16*)Q, (const u16*)K, (const u16*)V, (float*)ps8, (u32*)kb_hi, (u32*)kb_lo, (int*)cnt,
                    (u32*)lists, (const int*)loff, (u32*)meta, (int*)ctrl, NH, S, CD, st);
  }
}

void nsa_launch_attn(const void* Q, const void* K, const void* V, void* out, void* cnt, void* tick, void* lists,
                     const void* loff, void* meta, void* part_o, void* part_lw, void* ctrl, int NH, int S, int D,
                     int CD, int nWorkers, void* stream) {
  cudaStream_t st = (cudaStream_t)stream;
  if (D == 64) {
    launch_attn<64>((const u16*)Q, (const u16*)K, (const u16*)V, (u16*)out, (int*)cnt, (u32*)tick, (u32*)lists,
                    (const int*)loff, (u32*)meta, (u32*)part_o, (float*)part_lw, (int*)ctrl, NH, S, CD, nWorkers, st);
  } else {
    launch_attn<128>((const u16*)Q, (const u16*)K, (const u16*)V, (u16*)out, (int*)cnt, (u32*)tick, (u32*)lists,
                     (const int*)loff, (u32*)meta, (u32*)part_o, (float*)part_lw, (int*)ctrl, NH, S, CD, nWorkers,
                     st);
  }
}
"""

_CPP_SRC = r"""
#include <torch/extension.h>
#include <c10/cuda/CUDAStream.h>

void nsa_launch_pre(const void* Q, const void* K, const void* V, void* ps8, void* kb_hi, void* kb_lo, void* cnt,
                    void* lists, const void* loff, void* meta, void* ctrl, int NH, int S, int D, int CD,
                    void* stream);
void nsa_launch_attn(const void* Q, const void* K, const void* V, void* out, void* cnt, void* tick, void* lists,
                     const void* loff, void* meta, void* part_o, void* part_lw, void* ctrl, int NH, int S, int D,
                     int CD, int nWorkers, void* stream);
void nsa_set_prof(int p);
void set_prof(int64_t p) { nsa_set_prof((int)p); }

torch::Tensor nsa_forward(torch::Tensor q, torch::Tensor k, torch::Tensor v, torch::Tensor ps8,
                          torch::Tensor kb_hi, torch::Tensor kb_lo, torch::Tensor cnt, torch::Tensor tick,
                          torch::Tensor lists, torch::Tensor loff, torch::Tensor meta, torch::Tensor part_o,
                          torch::Tensor part_lw, torch::Tensor ctrl, int64_t cDense, int64_t nWorkers) {
  const int NH = (int)(q.size(0) * q.size(1)), S = (int)q.size(2), D = (int)q.size(3);
  void* stream = (void*)c10::cuda::getCurrentCUDAStream(q.get_device()).stream();
  // block sums + selection do not need the output buffer: get them going before allocating it
  nsa_launch_pre(q.data_ptr(), k.data_ptr(), v.data_ptr(), ps8.data_ptr(), kb_hi.data_ptr(), kb_lo.data_ptr(),
                 cnt.data_ptr(), lists.data_ptr(), loff.data_ptr(), meta.data_ptr(), ctrl.data_ptr(), NH, S, D,
                 (int)cDense, stream);
  torch::Tensor out = torch::empty_like(q);
  nsa_launch_attn(q.data_ptr(), k.data_ptr(), v.data_ptr(), out.data_ptr(), cnt.data_ptr(), tick.data_ptr(),
                  lists.data_ptr(), loff.data_ptr(), meta.data_ptr(), part_o.data_ptr(), part_lw.data_ptr(),
                  ctrl.data_ptr(), NH, S, D, (int)cDense, (int)nWorkers, stream);
  return out;
}
"""

_EXT = None
_EXT_NAME = "nsa_sm120_ext_dd96601b4e"


def _get_ext():
    global _EXT
    if _EXT is None:
        _EXT = load_inline(
            name=_EXT_NAME,
            cpp_sources=[_CPP_SRC],
            cuda_sources=[_CUDA_SRC],
            functions=["nsa_forward", "set_prof"],
            with_cuda=True,
            extra_cuda_cflags=["-O3", "-arch=sm_120"],
            verbose=False,
        )
    return _EXT


C_DENSE = 0  # query blocks below this index use the dense (partial-free) path (8..32); 0 = auto
N_WORKERS = 0  # 0 = auto: two resident 4-warp workers per SM


class _Plan:
    """Scratch buffers for one (device, B, H, S, D)."""

    def __init__(self, device, B, H, S, D, c_dense, n_workers):
        NH = B * H
        nb = (S + 63) // 64
        nbf = S // 64
        self.c_dense = c_dense
        self.n_workers = n_workers
        nbR = nb - 2 if nb > c_dense else 0
        offs = [0]
        for bi in range(nbR):
            offs.append(offs[-1] + max(S - 64 * max(bi + 2, c_dense), 0))
        list_cap = offs[-1]
        i32 = torch.int32
        self.ps8 = torch.zeros(NH * nb * 8 * D, dtype=torch.float32, device=device)
        self.kb_hi = torch.zeros(NH * max(nbf, 1) * D // 2, dtype=i32, device=device)
        self.kb_lo = torch.zeros(NH * max(nbf, 1) * D // 2, dtype=i32, device=device)
        self.cnt = torch.zeros(2 * NH * nbR + NH * ((nbR + 7) // 8) + NH + 16, dtype=i32, device=device)
        self.tick = torch.zeros(2 * (NH * S * 8 // 128 + 2 * NH * nb + 64), dtype=i32, device=device)
        self.lists = torch.zeros(NH * list_cap + 64, dtype=i32, device=device)
        self.loff = torch.tensor(offs, dtype=i32, device=device)
        self.meta = torch.zeros(NH * S, dtype=i32, device=device)
        n_part = NH * S * 8 if nbR > 0 else 8
        self.part_o = torch.zeros(n_part * (D // 2), dtype=i32, device=device)
        self.part_lw = torch.zeros(n_part, dtype=torch.float32, device=device)
        self.ctrl = torch.zeros(64 + 3 * NH, dtype=i32, device=device)


def _torch_fallback(q, k, v):
    """Bench semantics with plain torch ops, for inputs the CUDA path does not cover
    (non-CUDA device, non-bf16 dtype, D not in {64, 128}, very long sequences)."""
    B, H, S, D = q.shape
    dev = q.device
    qd, kd, vd = q.double(), k.double(), v.double()
    scale = 1.0 / math.sqrt(D)
    nb = (S + BLOCK_SIZE - 1) // BLOCK_SIZE
    pad = nb * BLOCK_SIZE - S
    idx = torch.arange(S, device=dev)
    out = torch.empty(B, H, S, D, dtype=torch.float64, device=dev)
    rows = max(1, min(S, (1 << 24) // max(S, 1)))
    for b in range(B):
        for h in range(H):
            for r0 in range(0, S, rows):
                t = idx[r0:r0 + rows]
                n = t.numel()
                sc = (qd[b, h, r0:r0 + rows] @ kd[b, h].T) * scale
                causal = idx[None, :] <= t[:, None]
                scm = torch.where(causal, sc, torch.zeros((), dtype=sc.dtype, device=dev))
                cnt = torch.nn.functional.pad(causal.to(sc.dtype), (0, pad)).view(n, nb, BLOCK_SIZE).sum(-1)
                imp = torch.nn.functional.pad(scm, (0, pad)).view(n, nb, BLOCK_SIZE).sum(-1) / cnt.clamp_min(1)
                # ties go to the higher block index (reference sorts (score, index) descending)
                order = torch.argsort(imp.flip(1), dim=1, descending=True, stable=True)
                order = (nb - 1 - order)
                valid = torch.gather(cnt > 0, 1, order)
                order_valid_first = torch.argsort((~valid).to(torch.int8), dim=1, stable=True)
                order = torch.gather(order, 1, order_valid_first)[:, :TOP_N_BLOCKS]
                selb = torch.zeros(n, nb, dtype=torch.bool, device=dev)
                selb.scatter_(1, order, True)
                selb &= cnt > 0
                selk = selb[:, :, None].expand(n, nb, BLOCK_SIZE).reshape(n, nb * BLOCK_SIZE)[:, :S]
                win = idx[None, :] > t[:, None] - SLIDING_WINDOW
                mask = (selk | win) & causal
                att = torch.softmax(sc.masked_fill(~mask, float("-inf")), dim=-1)
                out[b, h, r0:r0 + rows] = att @ vd[b, h]
    return out.to(torch.bfloat16)


_S_MAX = 16384  # limits of the packed work-list / ticket encodings and of the selection smem


class Model(nn.Module):
    def __init__(self, B: int, H: int, S: int, D: int):
        super().__init__()
        self.B, self.H, self.S, self.D = B, H, S, D
        self.register_buffer("_dummy", torch.zeros(1, dtype=torch.bfloat16))
        self._plans = {}
        self._fwd = _get_ext().nsa_forward

    def forward(self, q: torch.Tensor, k: torch.Tensor, v: torch.Tensor) -> torch.Tensor:
        bf = torch.bfloat16
        if not (q.is_cuda and q.dim() == 4 and q.dtype == bf and k.dtype == bf and v.dtype == bf
                and k.shape == q.shape and v.shape == q.shape and k.device == q.device
                and v.device == q.device and q.shape[3] in (64, 128) and 1 <= q.shape[2] <= _S_MAX
                and q.shape[0] * q.shape[1] > 0):
            return _torch_fallback(q, k, v)
        if not (q.is_contiguous() and k.is_contiguous() and v.is_contiguous()):
            q, k, v = q.contiguous(), k.contiguous(), v.contiguous()
        key = (q.device, q.shape)
        plan = self._plans.get(key)
        if plan is None:
            B, H, S, D = q.shape
            # up to 32 blocks everything is dense (8-warp kernel, selection bitmask fits 32 bits);
            # longer sequences keep only the first 8 blocks dense and pool the sparse far field
            cd = C_DENSE if C_DENSE else (32 if S <= 2048 else 8)
            nw = N_WORKERS if N_WORKERS else 2 * torch.cuda.get_device_properties(q.device).multi_processor_count
            plan = _Plan(q.device, B, H, S, D, cd, nw)
            self._plans[key] = plan
        return self._fwd(q, k, v, plan.ps8, plan.kb_hi, plan.kb_lo, plan.cnt, plan.tick, plan.lists, plan.loff,
                         plan.meta, plan.part_o, plan.part_lw, plan.ctrl, plan.c_dense, plan.n_workers)

20261109_143748_claude_claude-fable-5-2_02_deepseek_nsa