Files
Xiaoze Fan 08cee44468 feat(spec): add DFlash 2 speculative decoding (#857)
* feat(spec): hand the pending token to Proposer.propose and return a SpecProposal

* feat(engine): Sampler.probs and sparse-q rejection

* feat(spec): let a proposer declare slot states riding the GDN slots

* feat(models): export layer outputs to the feature sink in the qwen3_5 and qwen4_exp families

* feat(attention): record the source slot of each tracked request

* feat(kernel): DFlash2 draft kernels

* feat(models): DFlash2 draft family

* feat(spec): DFlashWindow

* feat(spec): DFlashProposer

* docs(cli): add dflash to the speculative decoding section

* refactor(engine): share the sampling backend choice and drop the extra renorm in Sampler.probs

* fix(models): build the DFlash rope table uncached and refuse draft scalings it does not apply

* refactor(spec): share the draft path check between the MTP and DFlash proposers

* test(e2e): compare rebuilt outputs exactly only without hybrid MoE

* refactor(spec): keep proposer slot states on EngineConfig instead of replacing model_config

* perf(spec): compute the verify distribution once for sparse-q rejection

* perf(models): let the feature sink add the residual on the rows it keeps

* perf(models): share the DFlash draft K/V weights with the ring projection

* fix(kernel): keep the dflash selector off zero-probability candidates

* test(spec): drop the DFlash tests that the draft forward and Monte Carlo tests already cover

* fix(spec): default and cap DFlash steps at the draft's block_size - 1

* fix(models): reject DFlash draft configs the draft forward cannot serve

* test(e2e): read the MoE strategy from the rebuild test's extra args

* docs(spec): say that slot-state owners write their own prefill track snapshot

* test(models): move the DFlash draft parity tests under tests/models/dflash

* refactor(spec): drop the no-op verify handler of the DFlash window

* refactor(models): fold the DFlash candidate top-k into propose

* refactor(spec): declare the draft step limits through Proposer.num_steps only

* refactor(kernel): make the DFlash ring attention stateless and keep its workspace on the ring

* refactor(models): name the DFlash draft submodules like the other model families

* refactor(spec): move SpecProposal next to DraftContext in spec/proposer.py

* refactor(spec): hand the verify the draft distribution over the whole vocabulary

* refactor(spec): call the DFlashRing object dflash_ring and its length ring_len

* refactor(models): split the DFlash draft's propose into compute_candidates and sample_path

* refactor(spec): keep the draft distribution on its support in SpecProposal

* fix(spec): drop the step's proposal once the verify has read it

* refactor(spec): name the DFlash feature sinks DFlashPrefillSink and DFlashVerifySink

* refactor(models): read the declared Batch.features directly instead of through getattr

* test(dflash): check the window rebuild inside the block forward test

* test(spec): share the plain run of the verify contract and run the DFlash draft once per family

* test(kvcache): drop the window cases from the pool tests and check a layerless state's bytes

* test(spec): check the verify probs of each row against a torch top-k and top-p reference

* test(e2e): add an accept-len floor and a prefill chunk knob to the AIME gate

* refactor(scheduler): let callers take the speculative counts from the status reporter

* test(spec): keep the shared plain runs of the verify contract in their own temp dirs

* test(models): give the ricursive test's stand-in batch a features field
2026-11-07 12:29:18 -08:00

275 lines
13 KiB
Python

"""Triton kernels of the DFlash 2 draft block: attention over the per-request KV ring, and the grouped 2-tap convolution."""
from __future__ import annotations
import torch
import triton
import triton.language as tl
@triton.jit
def _ring_attn_split_kernel(
q_ptr, k_ptr, v_ptr, rows_ptr, starts_ptr,
o_ptr, m_ptr, l_ptr,
layer, num_rows, ring_len, window, scale,
NUM_KV_HEADS: tl.constexpr, GROUP: tl.constexpr, BLOCK: tl.constexpr, HEAD_DIM: tl.constexpr,
BLOCK_M: tl.constexpr, BLOCK_N: tl.constexpr, KEYS_PER_SPLIT: tl.constexpr,
):
pid = tl.program_id(0)
split = tl.program_id(1)
num_splits = tl.num_programs(1)
b = pid // NUM_KV_HEADS
kvh = pid % NUM_KV_HEADS
row = tl.load(rows_ptr + b)
start = tl.load(starts_ptr + b)
m_idx = tl.arange(0, BLOCK_M)
g = m_idx // BLOCK
j = m_idx % BLOCK
m_ok = m_idx < GROUP * BLOCK
d = tl.arange(0, HEAD_DIM)
q_off = ((b * BLOCK + j) * (NUM_KV_HEADS * GROUP) + kvh * GROUP + g) * HEAD_DIM
q = tl.load(q_ptr + q_off[:, None] + d[None, :], mask=m_ok[:, None], other=0.0)
top = start + BLOCK - 1
# a query at start+j sees positions > start+j-window (sliding window), and only ones that hold context
lo = tl.maximum(start + j - window + 1, 0)
base = (layer * num_rows + row) * ring_len
acc = tl.zeros([BLOCK_M, HEAD_DIM], dtype=tl.float32)
m_i = tl.full([BLOCK_M], -1.0e30, dtype=tl.float32)
l_i = tl.zeros([BLOCK_M], dtype=tl.float32)
for n0 in range(0, KEYS_PER_SPLIT, BLOCK_N):
slot = split * KEYS_PER_SPLIT + n0 + tl.arange(0, BLOCK_N)
s_ok = slot < ring_len
# % keeps the dividend's sign; slots past top give a negative dividend early in a sequence
pos = top - ((top - slot) % ring_len + ring_len) % ring_len
kv_off = ((base + slot) * NUM_KV_HEADS + kvh) * HEAD_DIM
k = tl.load(k_ptr + kv_off[:, None] + d[None, :], mask=s_ok[:, None], other=0.0)
qk = tl.dot(q, tl.trans(k)) * scale
keep = s_ok[None, :] & (pos[None, :] >= lo[:, None])
qk = tl.where(keep, qk, float("-inf"))
m_new = tl.maximum(m_i, tl.max(qk, axis=1))
p = tl.exp(qk - m_new[:, None])
alpha = tl.exp(m_i - m_new)
v = tl.load(v_ptr + kv_off[:, None] + d[None, :], mask=s_ok[:, None], other=0.0)
acc = acc * alpha[:, None] + tl.dot(p.to(v.dtype), v)
l_i = l_i * alpha + tl.sum(p, axis=1)
m_i = m_new
part = (pid * num_splits + split) * BLOCK_M + m_idx
tl.store(o_ptr + part[:, None] * HEAD_DIM + d[None, :], acc)
tl.store(m_ptr + part, m_i)
tl.store(l_ptr + part, l_i)
@triton.jit
def _ring_attn_merge_kernel(
o_ptr, m_ptr, l_ptr, out_ptr, num_splits,
NUM_KV_HEADS: tl.constexpr, GROUP: tl.constexpr, BLOCK: tl.constexpr, HEAD_DIM: tl.constexpr,
BLOCK_M: tl.constexpr, MAX_SPLITS: tl.constexpr,
):
pid = tl.program_id(0)
m = tl.program_id(1)
b = pid // NUM_KV_HEADS
kvh = pid % NUM_KV_HEADS
sp = tl.arange(0, MAX_SPLITS)
sp_ok = sp < num_splits
d = tl.arange(0, HEAD_DIM)
part = (pid * num_splits + sp) * BLOCK_M + m
ms = tl.load(m_ptr + part, mask=sp_ok, other=-1.0e30)
ls = tl.load(l_ptr + part, mask=sp_ok, other=0.0)
w = tl.exp(ms - tl.max(ms, axis=0))
o = tl.load(o_ptr + part[:, None] * HEAD_DIM + d[None, :], mask=sp_ok[:, None], other=0.0)
acc = tl.sum(o * w[:, None], axis=0) / tl.sum(w * ls, axis=0)
g = m // BLOCK
j = m % BLOCK
out_off = ((b * BLOCK + j) * (NUM_KV_HEADS * GROUP) + kvh * GROUP + g) * HEAD_DIM
tl.store(out_ptr + out_off + d, acc.to(out_ptr.dtype.element_ty))
_KEYS_PER_SPLIT = 128
_BLOCK_N = 64
def _block_m(group: int, block: int) -> int:
return max(16, triton.next_power_of_2(group * block))
def ring_attention_workspace(max_bs: int, block: int, num_heads: int, num_kv_heads: int, head_dim: int, ring_len: int, device) -> tuple[torch.Tensor, torch.Tensor, torch.Tensor]:
"""The fp32 split partials (out, max, sum) ``ring_attention`` needs for up to ``max_bs`` requests; on the meta device they only size the budget."""
parts = max_bs * num_kv_heads * triton.cdiv(ring_len, _KEYS_PER_SPLIT) * _block_m(num_heads // num_kv_heads, block)
f32 = dict(dtype=torch.float32, device=device)
return torch.empty(parts, head_dim, **f32), torch.empty(parts, **f32), torch.empty(parts, **f32)
def ring_attention(q, ring_k, ring_v, layer: int, rows, starts, window: int, scale: float, workspace) -> torch.Tensor:
"""Non-causal block attention of ``[bs*block, heads*head_dim]`` queries over a ``[layers, rows, ring_len, kv_heads, head_dim]`` KV ring.
The ring holds position ``p`` at slot ``p % ring_len``; the block occupies ``start .. start+block-1`` and the window behind it the rest.
"""
ring_len, num_kv_heads, head_dim = ring_k.shape[2:]
bs = starts.shape[0]
block, group = q.shape[0] // bs, q.shape[1] // (num_kv_heads * head_dim)
block_m, num_splits = _block_m(group, block), triton.cdiv(ring_len, _KEYS_PER_SPLIT)
part_o, part_m, part_l = workspace
out = torch.empty_like(q)
_ring_attn_split_kernel[(bs * num_kv_heads, num_splits)](
q, ring_k, ring_v, rows, starts, part_o, part_m, part_l,
layer, ring_k.shape[1], ring_len, window, scale,
NUM_KV_HEADS=num_kv_heads, GROUP=group, BLOCK=block, HEAD_DIM=head_dim,
BLOCK_M=block_m, BLOCK_N=_BLOCK_N, KEYS_PER_SPLIT=_KEYS_PER_SPLIT, num_warps=4,
)
_ring_attn_merge_kernel[(bs * num_kv_heads, group * block)](
part_o, part_m, part_l, out, num_splits,
NUM_KV_HEADS=num_kv_heads, GROUP=group, BLOCK=block, HEAD_DIM=head_dim,
BLOCK_M=block_m, MAX_SPLITS=triton.next_power_of_2(num_splits), num_warps=4,
)
return out
@triton.jit
def _grouped_conv_kernel(
x_ptr, coef_ptr, base_ptr, out_ptr, hidden, coef_row_stride, block,
TAPS: tl.constexpr, GROUP_SIZE: tl.constexpr, NUM_GROUPS: tl.constexpr, BLOCK_H: tl.constexpr,
):
n = tl.program_id(0)
h = tl.program_id(1) * BLOCK_H + tl.arange(0, BLOCK_H)
h_ok = h < hidden
grp = h // GROUP_SIZE
first = n % block
acc = tl.zeros([BLOCK_H], dtype=tl.float32)
for t in tl.static_range(TAPS):
coef = tl.load(base_ptr + t * hidden + h, mask=h_ok, other=0.0).to(tl.float32)
coef += tl.load(coef_ptr + n * coef_row_stride + t * NUM_GROUPS + grp, mask=h_ok, other=0.0).to(tl.float32)
live = first >= t
x = tl.load(x_ptr + (n - t) * hidden + h, mask=h_ok & live, other=0.0).to(tl.float32)
acc += coef * x
tl.store(out_ptr + n * hidden + h, acc.to(out_ptr.dtype.element_ty), mask=h_ok)
def grouped_conv(x: torch.Tensor, coef: torch.Tensor, base: torch.Tensor, block: int, group_size: int) -> torch.Tensor:
"""``out[n] = sum_t (base[t] + coef[n, t, group]) * x[n - t]`` within each block of ``block`` rows; ``coef`` is ``[N, taps, groups]`` with unit inner strides."""
n, hidden = x.shape
taps, groups = coef.shape[1], coef.shape[2]
assert coef.stride(2) == 1 and coef.stride(1) == groups and x.is_contiguous() and base.is_contiguous()
out = torch.empty_like(x)
block_h = 512
_grouped_conv_kernel[(n, triton.cdiv(hidden, block_h))](
x, coef, base, out, hidden, coef.stride(0), block,
TAPS=taps, GROUP_SIZE=group_size, NUM_GROUPS=groups, BLOCK_H=block_h, num_warps=4,
)
return out
@triton.jit
def _norm_rope(x1, x2, w_ptr, cos, sin, eps, HALF: tl.constexpr):
d = tl.arange(0, HALF)
rstd = tl.rsqrt((tl.sum(x1 * x1, axis=0) + tl.sum(x2 * x2, axis=0)) / (2 * HALF) + eps)
x1 = x1 * rstd * tl.load(w_ptr + d).to(tl.float32)
x2 = x2 * rstd * tl.load(w_ptr + HALF + d).to(tl.float32)
return x1 * cos - x2 * sin, x2 * cos + x1 * sin
@triton.jit
def _norm_rope_store_kernel(
src_ptr, src_stride, q_out_ptr, q_norm_ptr, k_norm_ptr, cos_sin_ptr, pos_ptr, rows_ptr, ring_k_ptr, ring_v_ptr,
layer0, num_rows, ring_len, eps,
NUM_Q_HEADS: tl.constexpr, NUM_KV_HEADS: tl.constexpr, HEAD_DIM: tl.constexpr,
):
n = tl.program_id(0)
per_layer = NUM_Q_HEADS + 2 * NUM_KV_HEADS
layer_local = tl.program_id(1) // per_layer
h = tl.program_id(1) % per_layer
layer = layer0 + layer_local
half: tl.constexpr = HEAD_DIM // 2
d = tl.arange(0, half)
base = src_ptr + n * src_stride + (layer_local * per_layer + h) * HEAD_DIM
x1 = tl.load(base + d).to(tl.float32)
x2 = tl.load(base + half + d).to(tl.float32)
pos = tl.load(pos_ptr + n)
slot = pos.to(tl.int64) % ring_len
row = tl.load(rows_ptr + n)
cos = tl.load(cos_sin_ptr + pos * HEAD_DIM + d)
sin = tl.load(cos_sin_ptr + pos * HEAD_DIM + half + d)
if h >= NUM_Q_HEADS + NUM_KV_HEADS:
dst = ring_v_ptr + (((layer * num_rows + row) * ring_len + slot) * NUM_KV_HEADS + h - NUM_Q_HEADS - NUM_KV_HEADS) * HEAD_DIM
tl.store(dst + d, x1.to(ring_v_ptr.dtype.element_ty))
tl.store(dst + half + d, x2.to(ring_v_ptr.dtype.element_ty))
elif h < NUM_Q_HEADS:
o1, o2 = _norm_rope(x1, x2, q_norm_ptr, cos, sin, eps, half)
dst = q_out_ptr + (n * NUM_Q_HEADS + h) * HEAD_DIM
tl.store(dst + d, o1.to(q_out_ptr.dtype.element_ty))
tl.store(dst + half + d, o2.to(q_out_ptr.dtype.element_ty))
else:
o1, o2 = _norm_rope(x1, x2, k_norm_ptr + layer * HEAD_DIM, cos, sin, eps, half)
dst = ring_k_ptr + (((layer * num_rows + row) * ring_len + slot) * NUM_KV_HEADS + h - NUM_Q_HEADS) * HEAD_DIM
tl.store(dst + d, o1.to(ring_k_ptr.dtype.element_ty))
tl.store(dst + half + d, o2.to(ring_k_ptr.dtype.element_ty))
def norm_rope_store(
src: torch.Tensor, *, num_layers: int, num_q_heads: int, q_out: torch.Tensor | None, q_norm: torch.Tensor | None,
k_norms: torch.Tensor, cos_sin: torch.Tensor, positions: torch.Tensor, rows: torch.Tensor,
ring_k: torch.Tensor, ring_v: torch.Tensor, layer0: int, eps: float,
) -> None:
"""Per-head RMSNorm + NeoX RoPE of ``[n, num_layers*(q|k|v heads)*head_dim]`` rows: q into ``q_out``, k and v into the ring at ``positions % ring_len``.
``k_norms`` is ``[layers, head_dim]`` indexed by ``layer0 + layer``; ``cos_sin`` is ``[max_pos, head_dim]`` (cos half, sin half).
"""
n = src.shape[0]
num_kv_heads, head_dim = ring_k.shape[3], ring_k.shape[4]
assert src.stride(1) == 1 and cos_sin.dtype == torch.float32 and cos_sin.shape[1] == head_dim
_norm_rope_store_kernel[(n, num_layers * (num_q_heads + 2 * num_kv_heads))](
src, src.stride(0), q_out if q_out is not None else src, q_norm if q_norm is not None else k_norms, k_norms, cos_sin,
positions, rows, ring_k, ring_v, layer0, ring_k.shape[1], ring_k.shape[2], eps,
NUM_Q_HEADS=num_q_heads, NUM_KV_HEADS=num_kv_heads, HEAD_DIM=head_dim, num_warps=1,
)
@triton.jit
def _selector_kernel(
ids_ptr, unary_ptr, state_ptr, anchor_ptr, pre_ptr, suc_ptr, temp_ptr, greedy_ptr, u_ptr, tok_ptr, q_ptr,
SLOTS: tl.constexpr, TOP_K: tl.constexpr, RANK: tl.constexpr,
):
b = tl.program_id(0)
c = tl.arange(0, TOP_K)
r = tl.arange(0, RANK)
temperature = tl.load(temp_ptr + b)
greedy = tl.load(greedy_ptr + b) != 0
prev = tl.load(anchor_ptr + b)
for slot in tl.static_range(SLOTS):
base = (b * SLOTS + slot) * TOP_K
cand = tl.load(ids_ptr + base + c)
w = tl.load(pre_ptr + prev * RANK + r).to(tl.float32) * tl.load(state_ptr + (b * SLOTS + slot) * RANK + r).to(tl.float32)
keys = tl.load(suc_ptr + cand[:, None] * RANK + r[None, :]).to(tl.float32)
scores = tl.load(unary_ptr + base + c) + tl.sum(keys * w[None, :], axis=1)
if greedy:
best = tl.max(scores, axis=0)
index = tl.min(tl.where(scores == best, c, TOP_K), axis=0)
probs = tl.where(c == index, 1.0, 0.0)
else:
scaled = scores / temperature
e = tl.exp(scaled - tl.max(scaled, axis=0))
probs = e / tl.sum(e, axis=0)
u = tl.load(u_ptr + b * SLOTS + slot)
index = tl.minimum(tl.sum(tl.where(u >= tl.cumsum(probs, axis=0), 1, 0), axis=0), TOP_K - 1)
# fp32 cdf rounding can land u on a candidate whose q underflowed to 0, which rejection would accept on any p > 0
index = tl.max(tl.where((c <= index) & (probs > 0), c, 0), axis=0)
tl.store(q_ptr + base + c, probs)
prev = tl.sum(tl.where(c == index, cand, 0), axis=0)
tl.store(tok_ptr + b * SLOTS + slot, prev)
def selector_walk(ids, unary, state, anchor, pre, suc, temperature, greedy, uniforms):
"""One path through the candidate lattice per request: slot e scores ``unary[e] + <pre[prev] * state[e], suc[cand]>`` for the chosen predecessor only.
Argmax on ``greedy`` rows, else drawn from softmax(scores / temperature) with ``uniforms``; returns tokens ``[bs, slots]`` and q ``[bs, slots, top_k]``.
"""
bs, slots, top_k = ids.shape
tokens = torch.empty(bs, slots, dtype=torch.int64, device=ids.device)
q = torch.empty(bs, slots, top_k, dtype=torch.float32, device=ids.device)
_selector_kernel[(bs,)](
ids, unary, state, anchor, pre, suc, temperature, greedy, uniforms, tokens, q,
SLOTS=slots, TOP_K=top_k, RANK=pre.shape[1], num_warps=4,
)
return tokens, q