cclearlee67's picture
download
raw
11.1 kB
"""Fused Mamba-3 scan: the SSD reduction, verified, then a Triton kernel.
WHY THIS FILE. scan.py's chunked scan materialises (B,T,H,N,P) intermediates
(S, inp, w, g, h) in HBM and fires many kernels; on the RTX 5070 it is
memory-bandwidth bound and runs at ~3.4k tok/s for a 12M-param model at ctx
1024. The Mamba-3 paper's speed comes from a fused chunked kernel that keeps the
chunk state in SRAM and never writes the expanded state to HBM. This file builds
that, test-first, against the verified recurrence in layer.py.
THE REDUCTION (paper Sec 3.2-3.3, "data-dependent RoPE on B and C"). The
recurrence
h_t = alpha_t R(theta_t) h_{t-1} + gamma_t B_t x_t^T + beta_t B_{t-1} x_{t-1}^T
y_t = C_t^T h_t
becomes, with Phi_t = cumsum(theta) and the rotations absorbed into B and C,
y_t = Ctil_t^T sum_{s<=t} decay(s,t) (Beff_s xeff_s^T), decay(s,t)=prod_{s<r<=t} alpha_r
Ctil_t = R(-Phi_t) C_t
Beff_s = [ gamma_s R(-Phi_s)B_s , beta_s R(-Phi_s)B_{s-1} ] (N, 2R)
xeff_s = [ x_s , x_{s-1} ] (P, 2R)
i.e. a standard Mamba-2 SSD scan on RoPE'd B/C with a rank-2R write that folds
in the trapezoidal two-tap. SSD is the fusible, backward-known form.
STAGE 1 (this file, first): a PyTorch chunked-SSD reference that implements
exactly the arithmetic the Triton kernel will, and is checked fwd+bwd against
Mamba3Layer at float64. Only once this matches does the Triton port begin.
"""
from __future__ import annotations
import torch
from .scan import rotate_by # rotate (...,N,P) pairs of the N axis by ang (...,N/2)
def ssd_inputs(layer, u: torch.Tensor):
"""Reduce Mamba3Layer's coefficients to the SSD form.
Returns alpha (B,T,H), Beff (B,T,H,N,2R), xeff (B,T,H,P,2R), Ctil (B,T,H,N,R).
All the rotation and the trapezoidal fold happen here, in cheap elementwise
ops on tensors no larger than (.,.,.,N,2R) - never the (N,P) expanded state.
"""
alpha, beta, gamma, Bm, Cm, x, theta = layer._coeffs(layer.norm(u))
Phi = torch.cumsum(theta, dim=1) # (B,T,H,N/2) = Phi_s
Phi_prev = torch.cat([torch.zeros_like(Phi[:, :1]), Phi[:, :-1]], dim=1) # Phi_{s-1}
Btil = rotate_by(Bm, -Phi) # R(-Phi_s) B_s (paper gamma term)
Ctil = rotate_by(Cm, -Phi) # R(-Phi_t) C_t
# Trapezoidal previous-step write, rotated by R(-Phi_{s-1}) per paper eq (11)
# (NOT Phi_s): B_{s-1} lands rotated by prod_{i<=s-1} R_i in the global frame.
Bm_prev = torch.cat([torch.zeros_like(Bm[:, :1]), Bm[:, :-1]], dim=1)
x_prev = torch.cat([torch.zeros_like(x[:, :1]), x[:, :-1]], dim=1)
Btil_prev = rotate_by(Bm_prev, -Phi_prev) # R(-Phi_{s-1}) B_{s-1}
# rank-2R effective write: coefficients ride on B, so w_s = Beff_s xeff_s^T.
Beff = torch.cat([gamma[..., None, None] * Btil,
beta[..., None, None] * Btil_prev], dim=-1) # (B,T,H,N,2R)
xeff = torch.cat([x, x_prev], dim=-1) # (B,T,H,P,2R)
return alpha, Beff, xeff, Ctil
def ssd_pytorch(alpha, Beff, xeff, Ctil, chunk: int = 64):
"""Chunked SSD forward in PyTorch - the reference the Triton kernel matches.
alpha (B,T,H) ; Beff (B,T,H,N,K) ; xeff (B,T,H,P,K) ; Ctil (B,T,H,N,R).
Returns y (B,T,H,R,P). State g (N,P) is carried per chunk (kept small).
"""
B, T, H, N, K = Beff.shape
P = xeff.shape[-2]
R = Ctil.shape[-1]
la = torch.log(alpha.clamp_min(1e-30)) # (B,T,H)
g = torch.zeros(B, H, N, P, dtype=Beff.dtype, device=Beff.device)
ys = []
for s0 in range(0, T, chunk):
e = min(s0 + chunk, T)
L = e - s0
Bc = Beff[:, s0:e] # (B,L,H,N,K)
xc = xeff[:, s0:e] # (B,L,H,P,K)
Cc = Ctil[:, s0:e] # (B,L,H,N,R)
cl = torch.cumsum(la[:, s0:e], dim=1) # (B,L,H) = log prod_{s0..t}
d = torch.exp(cl) # (B,L,H) prod_{s0..t} alpha
# intra-chunk decay L[t,s] = exp(cl_t - cl_s) for s<=t else 0
rel = cl.unsqueeze(2) - cl.unsqueeze(1) # (B,L(t),L(s),H)
# mask the exponent BEFORE exp: above the diagonal rel > 0 can overflow, and where() of an inf
# still back-propagates NaN into alpha (non-finite grads once a chunk's decay exceeds ~88 nats)
tril = torch.tril(torch.ones(L, L, dtype=torch.bool, device=Beff.device))
Ldec = torch.exp(rel.masked_fill(~tril.view(1, L, L, 1), float("-inf")))
# scores G[t,s] = Ctil_t^T Beff_s over N -> (B,H,L,L,R,K)
G = torch.einsum('blhnr,bmhnk->bhlmrk', Cc, Bc)
# intra y_t = sum_{s<=t} Ldec[t,s] G[t,s] xeff_s^T
y_intra = torch.einsum('blmh,bhlmrk,bmhpk->blhrp', Ldec, G, xc)
# inter y_t = d_t * (Ctil_t^T g)
y_inter = torch.einsum('blh,blhnr,bhnp->blhrp', d, Cc, g)
ys.append(y_intra + y_inter)
# state update: g <- d_{L-1} g + sum_s (d_{L-1}/d_s) Beff_s xeff_s^T
coef = torch.exp(cl[:, -1:, :] - cl) # (B,L,H)
g = d[:, -1].unsqueeze(-1).unsqueeze(-1) * g \
+ torch.einsum('blh,blhnk,blhpk->bhnp', coef, Bc, xc)
return torch.cat(ys, dim=1) # (B,T,H,R,P)
def ssd_vectorized(alpha, Beff, xeff, Ctil, chunk: int = 64):
"""ssd_pytorch with NO Python loop over chunks - same arithmetic, batched.
ssd_pytorch walks the chunks sequentially, firing ~10 kernels per chunk; at T ~ 2000 that loop,
not the FLOPs, is the cost. Here every chunk's intra-chunk term is one batched einsum, and the
chunk-to-chunk state pass - g_c = D_{c-1} g_{c-1} + U_{c-1} - is unrolled into a (C x C)
lower-triangular decay matrix over chunks, the formulation of Mamba-2's `ssd_minimal`. C = T/chunk
is small (tens), so that matrix is cheap.
Exponents are masked to -inf BEFORE exp, never exp-then-where: above the diagonal cl_t - cl_s is
positive and can overflow, and where() of an inf still back-propagates NaN.
Same signature and output as ssd_pytorch; verify() checks the two agree fwd+bwd at float64.
"""
B, T, H, N, K = Beff.shape
P, R = xeff.shape[-2], Ctil.shape[-1]
pad = (-T) % chunk
if pad: # alpha=1 (log 0) and zero writes/readouts: padded steps change nothing
alpha = torch.cat([alpha, alpha.new_ones(B, pad, H)], 1)
Beff, xeff, Ctil = (torch.cat([t, t.new_zeros(B, pad, *t.shape[2:])], 1) for t in (Beff, xeff, Ctil))
C, L = (T + pad) // chunk, chunk
la = torch.log(alpha.clamp_min(1e-30)).view(B, C, L, H)
Bc, xc, Cc = Beff.view(B, C, L, H, N, K), xeff.view(B, C, L, H, P, K), Ctil.view(B, C, L, H, N, R)
cl = torch.cumsum(la, 2) # (B,C,L,H) log decay from chunk start
tril = torch.tril(torch.ones(L, L, dtype=torch.bool, device=Beff.device)).view(1, 1, L, L, 1)
Ldec = torch.exp((cl.unsqueeze(3) - cl.unsqueeze(2)).masked_fill(~tril, float("-inf"))) # (B,C,L,L,H)
G = torch.einsum('bclhnr,bcmhnk->bchlmrk', Cc, Bc)
y = torch.einsum('bclmh,bchlmrk,bcmhpk->bclhrp', Ldec, G, xc) # intra-chunk
# each chunk's own contribution to the state at its end, then the state at each chunk's START
U = torch.einsum('bclh,bclhnk,bclhpk->bchnp', torch.exp(cl[:, :, -1:] - cl), Bc, xc) # (B,C,H,N,P)
tot = cl[:, :, -1] # (B,C,H) log decay across chunk c
ct = torch.cumsum(tot, 1)
# start state of chunk c = sum_{j<c} exp(ct_{c-1} - ct_j) U_j (strictly lower triangular in c, j)
stril = torch.tril(torch.ones(C, C, dtype=torch.bool, device=Beff.device), -1).view(1, C, C, 1)
ctm1 = ct - tot # ct_{c-1} (0 for c=0)
Dc = torch.exp((ctm1.unsqueeze(2) - ct.unsqueeze(1)).masked_fill(~stril, float("-inf"))) # (B,C,C,H)
g0 = torch.einsum('bcjh,bjhnp->bchnp', Dc, U)
y = y + torch.einsum('bclh,bclhnr,bchnp->bclhrp', torch.exp(cl), Cc, g0) # inter-chunk
return y.reshape(B, C * L, H, R, P)[:, :T]
def scan_forward_ssd(layer, u: torch.Tensor, chunk: int = 64, vectorized: bool = True):
"""Drop-in for scan.scan_forward, via the SSD reduction (PyTorch stage).
vectorized=True (default) uses ssd_vectorized (no per-chunk Python loop; much faster at long T);
False runs the chunk loop of ssd_pytorch, kept as the readable reference."""
Bsz, T, _ = u.shape
H, R, P = layer.H, layer.R, layer.P
nu = layer.norm(u)
alpha, Beff, xeff, Ctil = ssd_inputs(layer, u)
y = (ssd_vectorized if vectorized else ssd_pytorch)(alpha, Beff, xeff, Ctil, chunk) # (B,T,H,R,P)
return layer.gate_and_proj(y.reshape(Bsz, T, H * R * P), nu)
def verify(chunks=(8, 16, 64), verbose: bool = True) -> dict:
"""SSD reduction vs the recurrence, fwd + bwd, at float64 - loop and vectorized paths."""
from .layer import Mamba3Layer
torch.manual_seed(0)
torch.set_default_dtype(torch.float64)
out = {}
lay = Mamba3Layer(d_model=32, d_state=16, rank=2, head_dim=8).eval()
u = torch.randn(3, 40, 32)
u2 = torch.randn(2, 37, 32)
u3 = torch.cat([u, torch.randn(3, 9, 32) * 50], 1)
ug = torch.randn(3, 24, 32, requires_grad=True)
with torch.no_grad():
ref, ref2 = lay(u), lay(u2)
lay.zero_grad(); lay(ug).pow(2).sum().backward()
gu = ug.grad.clone(); gp = {n: p.grad.clone() for n, p in lay.named_parameters()
if p.grad is not None}
for vec in (False, True):
pre = "vec_" if vec else ""
f = lambda x, c: scan_forward_ssd(lay, x, c, vectorized=vec)
with torch.no_grad():
for c in chunks:
out[f"{pre}chunk{c}"] = float((f(u, c) - ref).abs().max())
out[f"{pre}ragged"] = float((f(u2, 16) - ref2).abs().max())
out[f"{pre}causality"] = float((f(u3, 16)[:, :40] - f(u, 16)).abs().max())
ug.grad = None; lay.zero_grad()
f(ug, 8).pow(2).sum().backward()
out[f"{pre}grad_input"] = float((gu - ug.grad).abs().max())
out[f"{pre}grad_params"] = max(float((gp[n] - p.grad).abs().max())
for n, p in lay.named_parameters() if p.grad is not None)
# long sequence with strong decay: the vectorized path's masked exponents must stay finite fwd+bwd
a = torch.full((1, 3000, 2), 1e-3) # log alpha ~ -6.9 per step
Bf, xf, Cf = (torch.randn(1, 3000, 2, 4, k, requires_grad=True) for k in (2, 2, 1))
yv = ssd_vectorized(a, Bf, xf, Cf, 64)
yv.sum().backward()
out["vec_long_finite"] = 0.0 if all(torch.isfinite(t).all() for t in (yv, Bf.grad, xf.grad, Cf.grad)) else 1.0
with torch.no_grad():
out["vec_long_vs_loop"] = float((yv - ssd_pytorch(a, Bf, xf, Cf, 64)).abs().max())
torch.set_default_dtype(torch.float32)
if verbose:
ok = lambda c: "OK " if c else "FAIL"
print("SSD reduction vs recurrence (float64, fwd+bwd)")
for k, v in out.items():
print(f" {k:<18}{v:.3e} {ok(v < 1e-9)}")
return out
if __name__ == "__main__":
verify()

Xet Storage Details

Size:
11.1 kB
·
Xet hash:
b2649e2830346d609d67116c40438d53392e1cd5e5e90de41b2a272f94efa393

Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.