KernelBench hard · RTX PRO 6000

KDA CUTLASS DeepSeek V4.1 Flash (1017)

4.03%geomean peak fraction across shapes

manually audited: clean

Three Triton kernels for the KDA chunked recurrence: a per-chunk prepare kernel builds the WY form and inverts (I+N) with a 16x16 block-diagonal Neumann doubling (exact for nilpotent N) plus an L^3 correction, then a sequential inter-chunk state scan, then an output kernel. Triton, not CUTLASS CuTe; PROMPT.txt allows Triton. No fla imports.

harnessor-fableagent session2h 1mtotal wall2h 1mcheck9sbenchmark2soutput tokens504,542cost$31.27gpu-lock wait17mgpu-lock held12mregimecompute

Per-shape vs governing ceilingeach shape graded against whichever binds — bf16 compute or HBM bandwidth

2×1024×8×128×128×640.100 ms4.3%0.25 TB/s · 14% of 1.8 TB/s HBM · also 21 TFLOPS (4% of compute)
2×2048×8×128×128×640.158 ms5.5%0.32 TB/s · 18% of 1.8 TB/s HBM · also 27 TFLOPS (5% of compute)
1×4096×8×128×128×640.178 ms4.8%0.28 TB/s · 16% of 1.8 TB/s HBM · also 24 TFLOPS (5% of compute)
1×2048×4×128×128×640.092 ms2.3%0.14 TB/s · 8% of 1.8 TB/s HBM · also 12 TFLOPS (2% of compute)

compute-bound memory-bound · bar + right column = official fraction of the ceiling (the geomean input)

geomean(4.3% · 5.5% · 4.8% · 2.3%) = 4.0%

Kernel source (redacted)
"""Kimi Delta Attention forward (chunk form), custom Triton kernels for SM120.

Three phases:
  1. prepare : per-chunk WY representation (w, u), intra-chunk q-k matrix and
               decay factors.  Fully parallel over (batch, head, chunk).
  2. scan    : sequential inter-chunk state recurrence, parallel over
               (batch, head, value-slice).
  3. output  : o = (q * exp(g)) @ S + A_qk @ v_i, parallel over
               (batch, head, chunk, value-slice).

Math (chunk size BT, in-chunk inclusive cumsum G of the log decay):
  ek = exp(G - G_last), kB = k * exp(G_last - G), kA = k * ek,
  N  = beta * strict_tril(kA kB^T)
  X  = (I + N)^-1                      (16x16 block scheme, see kernel)
  w  = X (beta kA d),  u = X (beta v),  d = exp(G_last)
  Aqk = tril(q scale ek kB^T),  qe = q scale ek d
  per chunk: v_i = u - w S ;  o = qe S + Aqk v_i ;
             S <- S d + kB^T v_i
"""
from __future__ import annotations

import torch
import torch.nn as nn
import triton
import triton.language as tl


# ---------------------------------------------------------------- phase 1
@triton.jit
def _prepare_kernel(
    q_ptr, k_ptr, v_ptr, g_ptr, beta_ptr,
    qe_ptr, w_ptr, u_ptr, aqk_ptr, kb_ptr, d_ptr,
    scale,
    T, H, NT,
    K: tl.constexpr, V: tl.constexpr, BT: tl.constexpr, BH, NLEV: tl.constexpr,
):
    pid = tl.program_id(0)
    bh = pid % BH
    n = pid // BH
    b = bh // H
    h = bh % H

    offs_t = tl.arange(0, BT)
    offs_k = tl.arange(0, K)
    row = b * T * H * K + (n * BT + offs_t) * (H * K) + h * K
    ptrs = row[:, None] + offs_k[None, :]

    # All five input tiles are issued up front.  At 8 warps this kernel keeps
    # one CTA per SM, so the memory system has to stay busy underneath the
    # (long, dependent) inverse chain -- hoisting the loads this way is worth
    # ~20% over loading q/v lazily.
    k = tl.load(k_ptr + ptrs, eviction_policy="evict_first")
    g = tl.load(g_ptr + ptrs, eviction_policy="evict_first")
    q = tl.load(q_ptr + ptrs, eviction_policy="evict_first")
    v = tl.load(v_ptr + ptrs, eviction_policy="evict_first")
    beta = tl.load(beta_ptr + b * T * H + (n * BT + offs_t) * H + h).to(tl.float32)

    # in-chunk inclusive cumsum of the per-channel log decay
    G = tl.cumsum(g, 0)
    glast = tl.sum(tl.where(offs_t[:, None] == BT - 1, G, 0.0), 0)   # [K]
    d = tl.exp(glast)                                                # [K]
    ek = tl.exp(G - glast[None, :])                                  # [BT,K]

    kf = k.to(tl.float32)
    kA = (kf * ek).to(tl.bfloat16)                           # k * exp(G - G_last)
    kB = (kf / ek).to(tl.bfloat16)                           # k * exp(G_last - G)

    # q side first: aqk / qe only need q, ek, kB.  Emitting them here keeps the
    # 64x128 q tiles out of the live set across the (register heavy) inverse.
    qA = ((q.to(tl.float32) * scale) * ek).to(tl.bfloat16)
    aqk = tl.dot(qA, tl.trans(kB))
    aqk = tl.where(offs_t[:, None] >= offs_t[None, :], aqk, 0.0)
    qe = (qA.to(tl.float32) * d[None, :]).to(tl.bfloat16)
    obase = (bh * NT + n) * BT * K
    tl.store(qe_ptr + obase + offs_t[:, None] * K + offs_k[None, :], qe)
    tl.store(aqk_ptr + (bh * NT + n) * BT * BT + offs_t[:, None] * BT + offs_t[None, :],
             aqk.to(tl.bfloat16))
    tl.store(kb_ptr + obase + offs_t[:, None] * K + offs_k[None, :], kB,
             eviction_policy="evict_last")
    kg = (kA.to(tl.float32) * d[None, :]).to(tl.bfloat16)
    rhs_w = (kg.to(tl.float32) * beta[:, None]).to(tl.bfloat16)

    # strictly-lower interaction matrix N[c,i] = beta_c * kA_c . kB_i
    N = tl.dot(kA, tl.trans(kB)) * beta[:, None]
    N = tl.where(offs_t[:, None] > offs_t[None, :], N, 0.0)

    # X = (I + N)^{-1}.  A plain 5-level doubling on the full 64x64 block is
    # numerically unusable in bf16 (the intermediate N^k reach ~1e2 while the
    # exact inverse is O(1), so rounding is amplified into a ~50% error).
    # Split N = Nb + Nl with Nb block-diagonal (16x16 blocks) and Nl block
    # strictly lower; then with Db = (I+Nb)^{-1}, L = Db Nl (L^4 = 0):
    #     X = (I + L)^{-1} Db = (I - L + L^2 - L^3) Db.
    # The doubling for Db stays well scaled (intermediates <= 0.4).
    eye = tl.where(offs_t[:, None] == offs_t[None, :], 1.0, 0.0)
    blk = (offs_t[:, None] // 16) == (offs_t[None, :] // 16)
    Nb = tl.where(blk, N, 0.0)
    Nl = N - Nb
    Nbb = Nb.to(tl.bfloat16)
    D = -Nb + eye
    for _ in tl.static_range(0, NLEV):
        Nbb = tl.dot(Nbb, Nbb).to(tl.bfloat16)
        D = D + tl.dot(D.to(tl.bfloat16), Nbb)
    L = tl.dot(D.to(tl.bfloat16), Nl.to(tl.bfloat16))
    L2 = tl.dot(L.to(tl.bfloat16), L.to(tl.bfloat16))
    L3 = tl.dot(L2.to(tl.bfloat16), L.to(tl.bfloat16))
    Y = eye - L + L2 - L3
    X = tl.dot(Y.to(tl.bfloat16), D.to(tl.bfloat16))
    Xb = X.to(tl.bfloat16)

    w = tl.dot(Xb, rhs_w)
    tl.store(w_ptr + obase + offs_t[:, None] * K + offs_k[None, :], w.to(tl.bfloat16),
             eviction_policy="evict_last")

    rhs_u = (v.to(tl.float32) * beta[:, None]).to(tl.bfloat16)
    u = tl.dot(Xb, rhs_u)
    obase_v = (bh * NT + n) * BT * V
    tl.store(u_ptr + obase_v + offs_t[:, None] * V + offs_k[None, :], u.to(tl.bfloat16))
    tl.store(d_ptr + (bh * NT + n) * K + offs_k, d)


# ---------------------------------------------------------------- phase 2
@triton.jit
def _scan_kernel(
    w_ptr, u_ptr, kb_ptr, d_ptr, h_ptr, v_ptr,
    NT,
    K: tl.constexpr, V: tl.constexpr, BT: tl.constexpr, BV: tl.constexpr,
    PF: tl.constexpr,
):
    pid = tl.program_id(0)
    S: tl.constexpr = V // BV
    bh = pid // S
    s = pid % S

    offs_t = tl.arange(0, BT)
    offs_k = tl.arange(0, K)
    offs_v = s * BV + tl.arange(0, BV)

    st = tl.zeros((K, BV), dtype=tl.float32)
    if PF == 0:
        # Many chunk-parallel CTAs per SM (BH >= 16): the hardware already
        # overlaps the loads of neighbouring CTAs, so a manual prefetch only
        # costs registers and measures slower.
        for n in range(NT):
            wo = (bh * NT + n) * BT * K + offs_t[:, None] * K + offs_k[None, :]
            w = tl.load(w_ptr + wo, eviction_policy="evict_last")
            kb = tl.load(kb_ptr + wo, eviction_policy="evict_last")
            uo = (bh * NT + n) * BT * V + offs_t[:, None] * V + offs_v[None, :]
            u = tl.load(u_ptr + uo)
            d = tl.load(d_ptr + (bh * NT + n) * K + offs_k)

            tl.store(h_ptr + (bh * NT + n) * K * V + offs_k[:, None] * V + offs_v[None, :],
                     st.to(tl.bfloat16))
            v = u.to(tl.float32) - tl.dot(w, st.to(tl.bfloat16))
            tl.store(v_ptr + uo, v.to(tl.bfloat16))
            st = st * d[:, None] + tl.dot(tl.trans(kb), v.to(tl.bfloat16))
    else:
        # Few CTAs (BH <= 8), far below one per SM: issue the two [BT,K]
        # operands of step n+1 before step n's dependent dots, otherwise every
        # step stalls on a cold DRAM read.
        wo = (bh * NT) * BT * K + offs_t[:, None] * K + offs_k[None, :]
        uo = (bh * NT) * BT * V + offs_t[:, None] * V + offs_v[None, :]
        w = tl.load(w_ptr + wo, eviction_policy="evict_last")
        kb = tl.load(kb_ptr + wo, eviction_policy="evict_last")
        for n in range(NT):
            nx = tl.minimum(n + 1, NT - 1)
            wo2 = (bh * NT + nx) * BT * K + offs_t[:, None] * K + offs_k[None, :]
            uo2 = (bh * NT + nx) * BT * V + offs_t[:, None] * V + offs_v[None, :]
            w2 = tl.load(w_ptr + wo2, eviction_policy="evict_last")
            kb2 = tl.load(kb_ptr + wo2, eviction_policy="evict_last")
            u = tl.load(u_ptr + uo)
            d = tl.load(d_ptr + (bh * NT + n) * K + offs_k)

            tl.store(h_ptr + (bh * NT + n) * K * V + offs_k[:, None] * V + offs_v[None, :],
                     st.to(tl.bfloat16))
            v = u.to(tl.float32) - tl.dot(w, st.to(tl.bfloat16))
            tl.store(v_ptr + uo, v.to(tl.bfloat16))
            st = st * d[:, None] + tl.dot(tl.trans(kb), v.to(tl.bfloat16))
            w = w2
            kb = kb2
            wo = wo2
            uo = uo2


# ---------------------------------------------------------------- phase 3
@triton.jit
def _output_kernel(
    qe_ptr, aqk_ptr, v_ptr, h_ptr, o_ptr,
    T, H, NT,
    K: tl.constexpr, V: tl.constexpr, BT: tl.constexpr, BV: tl.constexpr, BH,
):
    pid = tl.program_id(0)
    S: tl.constexpr = V // BV
    chunk = pid // S
    s = pid % S
    bh = chunk % BH
    n = chunk // BH
    b = bh // H
    hh = bh % H

    offs_t = tl.arange(0, BT)
    offs_k = tl.arange(0, K)
    offs_b = tl.arange(0, BT)
    offs_v = s * BV + tl.arange(0, BV)

    qe = tl.load(qe_ptr + (bh * NT + n) * BT * K + offs_t[:, None] * K + offs_k[None, :])
    aqk = tl.load(aqk_ptr + (bh * NT + n) * BT * BT + offs_t[:, None] * BT + offs_b[None, :])
    vv = tl.load(v_ptr + (bh * NT + n) * BT * V + offs_t[:, None] * V + offs_v[None, :])
    hs = tl.load(h_ptr + (bh * NT + n) * K * V + offs_k[:, None] * V + offs_v[None, :])

    o = tl.dot(qe, hs) + tl.dot(aqk, vv)
    optr = (b * T * H * V) + (n * BT + offs_t)[:, None] * (H * V) + hh * V + offs_v[None, :]
    tl.store(o_ptr + optr, o.to(tl.bfloat16), eviction_policy="evict_first")


# ---------------------------------------------------------------- driver
_CACHE: dict = {}


def _buffers(B, T, H, K, V, dev):
    key = (B, T, H, K, V, dev.index)
    buf = _CACHE.get(key)
    if buf is None:
        BH = B * H
        NT = T // 64
        n1 = BH * NT * 64 * K
        buf = (
            torch.empty(n1, dtype=torch.bfloat16, device=dev),                 # qe
            torch.empty(n1, dtype=torch.bfloat16, device=dev),                 # w
            torch.empty(BH * NT * 64 * V, dtype=torch.bfloat16, device=dev),   # u
            torch.empty(n1, dtype=torch.bfloat16, device=dev),                 # kb
            torch.empty(BH * NT * 64 * 64, dtype=torch.bfloat16, device=dev),  # aqk
            torch.empty(BH * NT * K, dtype=torch.float32, device=dev),         # d
            torch.empty(BH * NT * K * V, dtype=torch.bfloat16, device=dev),    # hs
            torch.empty(BH * NT * 64 * V, dtype=torch.bfloat16, device=dev),   # vv
        )
        _CACHE[key] = buf
    return buf


def _forward(q, k, v, g, beta, scale, BV=None, obv=None):
    B, T, H, K = q.shape
    V = v.shape[-1]
    BT = 64
    NT = T // BT
    BH = B * H
    dev = q.device
    qe, w, u, kb, aqk, d, hs, vv = _buffers(B, T, H, K, V, dev)

    _prepare_kernel[(NT * BH,)](
        q, k, v, g, beta, qe, w, u, aqk, kb, d, scale,
        T, H, NT, K, V, BT, BH, 3, num_warps=8,
    )
    if BV is None:
        BV = 16
    _scan_kernel[(BH * (V // BV),)](
        w, u, kb, d, hs, vv, NT, K, V, BT, BV, 0 if BH >= 16 else 2,
        num_warps=8, num_stages=3,
    )
    if obv is None:
        obv = 64
    o = torch.empty((B, T, H, V), dtype=torch.bfloat16, device=dev)
    _output_kernel[(BH * NT * (V // obv),)](
        qe, aqk, vv, hs, o, T, H, NT, K, V, BT, obv, BH, num_warps=8,
    )
    return o


class Model(nn.Module):
    def __init__(self, B: int, T: int, H: int, K: int, V: int, chunk_size: int = 64):
        super().__init__()
        self.B, self.T, self.H, self.K, self.V = B, T, H, K, V
        self.chunk_size = chunk_size
        self.scale = float(K) ** -0.5
        self.register_buffer("_dummy", torch.zeros(1), persistent=False)

    def forward(self, q, k, v, g, beta):
        return _forward(q.contiguous(), k.contiguous(), v.contiguous(),
                        g.contiguous(), beta.contiguous(), self.scale)

20261017_215237_or-fable_deepseek_deepseek-v4.1-flash-1017_02_kda_cutlass