Skip to content

FreeToken brings datacenter-scale model serving to your desktop. Run massive models locally, fast and efficiently.

23.6 KB
Raw Blame
"""DeepSeek-V4.1 sparse-attention backend.

Same contract and division of labour as ``dsv4_sparse``: the backend owns the per-forward KV
ADDRESSING over the shared page table (window ring slots, compressed rows, compress-state carry,
the decode snapshot and the CUDA-graph staging buffers) plus the selection helpers that are pure
index arithmetic (causal top-k, the hierarchical candidate pool); the model computes projections
and hands the picks back to be resolved into pool rows.

What DSV41 adds on top of DSV4's vocabulary:

* **cross-layer sharing** -- the compressed tiers belong to the kv-source layer; a consumer layer
  addresses ``source_of(layer)``'s pools. The Top-K rows and the candidate pool the Full / Reindex
  layers produce ride on the per-forward ``SharedSelection`` for the Reuse layers to read.
* **packed rows** -- writes quantize into the pool (``pool.store_*``), reads dequantize in-kernel.
* **prefill passes with a window floor** -- a ``PrefillSegment`` carries ``window_floor``: the
  absolute position a query's sliding window may not reach below (Decoder SWA Bounded Replay
  truncates the decoder's window at ``L - W``, the start of the prompt's last window). The metadata
  carries the encoder pass (every new token) and the decoder pass (the new tokens inside the
  prompt's last window, or every new token in exact mode).
"""

from __future__ import annotations

from dataclasses import dataclass, field
from typing import TYPE_CHECKING, List

import torch
from freetoken.core import Batch, get_global_ctx

from .base import AttentionSpec, BaseAttnBackend, BaseAttnMetadata

if TYPE_CHECKING:
    from freetoken.models import ModelConfig


@dataclass(frozen=True)
class PrefillSegment:
    """One request's slice of a flat prefill token stream.

    ``offset``/``n`` tile the stream; ``start_pos`` is the absolute position of the first token;
    ``window_floor`` bounds every query's sliding window from below (0 = the exact window; bounded
    replay sets it to the start of the prompt's last window).
    """

    offset: int
    n: int
    table_idx: int
    start_pos: int
    window_floor: int = 0

    @property
    def end(self) -> int:
        return self.start_pos + self.n


@dataclass
class SharedSelection:
    """What the index-producing layers hand down the stack within ONE forward.

    ``topk_rows`` are GLOBAL main-pool rows (``-1`` masked) for the current kv source, laid out
    exactly as the attention kernel consumes them; ``cmp_counts`` is the decode-only per-row live
    count that bounds the kernel's loop; ``candidates`` is the Hierarchical Sparse Indexer's
    compressed-position pool (``-1`` = empty slot). Layers run in order and every producer writes
    before its consumers read, so one slot each suffices.
    """

    source: int | None = None
    topk_rows: torch.Tensor | None = None
    cmp_counts: torch.Tensor | None = None
    candidates: torch.Tensor | None = None


@dataclass
class DSV41AttnMetadata(BaseAttnMetadata):
    last_indices: torch.Tensor
    # Prefill: the encoder pass tiles the batch's new tokens; the decoder pass tiles the tokens the
    # decoder layers process (``decoder_rows`` gathers them out of the encoder stream; None = all of
    # it). ``decoder_pad``: some request has no decoder row this chunk, and its ``last_indices`` entry
    # points at one placeholder row the model appends after the decoder stream (its logits are unused).
    segments: List[PrefillSegment] | None = None
    decoder_segments: List[PrefillSegment] | None = None
    decoder_rows: torch.Tensor | None = None
    decoder_pad: bool = False
    # Decode: the whole-history full-loc snapshot (captured buffer under a replay, lazy eager copy).
    full_snap: torch.Tensor | None = None
    table_rows: torch.Tensor | None = None
    window_ar: torch.Tensor | None = None
    selection: SharedSelection = field(default_factory=SharedSelection)

    def get_last_indices(self, bs: int) -> torch.Tensor:
        return self.last_indices[:bs]

    @property
    def stage_width(self) -> int:
        assert self.full_snap is not None, "stage_width is capture/replay-only"
        return self.full_snap.shape[1]

    def full_snapshot(self) -> torch.Tensor:
        if self.full_snap is None:
            assert self.table_rows is not None, "snapshot is decode-only"
            pool = get_global_ctx().kv_cache
            self.full_snap = pool.full_loc_map.index_select(0, self.table_rows).to(torch.int64)
        return self.full_snap

    def window_ctx(self, pos: torch.Tensor, rows: torch.Tensor):
        """Layer-invariant decode ring context ``(window_slots, prev_window_slots,
        window_slots_topk [B, 1, win])``; computed fresh on every call (never cached -- a capture
        must record these gathers), off the snapshot so a concurrent allocation cannot redirect
        an in-flight replay."""
        snap = self.full_snapshot()
        translate = get_global_ctx().kv_cache.translate_full_to_window
        bs = pos.shape[0]
        j = self.window_ar
        assert j is not None, "window_ctx is decode-only"
        win = j.shape[0]
        window_slots = translate(snap[rows, pos])
        prev_window_slots = translate(snap[rows, (pos - 1).clamp_min(0)])
        p = pos[:, None] - ((pos[:, None] - j[None, :]) % win)
        ws = translate(snap[rows[:, None], p.clamp(min=0)])
        window_slots_topk = torch.where((p >= 0) & (j[None, :] <= pos[:, None]), ws, -1).view(bs, 1, win)
        return window_slots, prev_window_slots, window_slots_topk

    def private_window_ctx(self, pos: torch.Tensor, rows: torch.Tensor):
        """The private-ring counterpart of ``window_ctx`` for request-private window layers:
        ``(window_slots [B], window_slots_topk [B, 1, win])`` in the layer's ring, where a request's
        row holds positions by ``pos % win`` (candidate ``j`` is the position congruent to ``j``)."""
        assert self.table_rows is not None and self.window_ar is not None, "private_window_ctx is decode-only"
        pool = get_global_ctx().kv_cache
        bs = pos.shape[0]
        j = self.window_ar
        win = j.shape[0]
        table = self.table_rows[rows]
        window_slots = pool.ring_slots(table, pos)
        p = pos[:, None] - ((pos[:, None] - j[None, :]) % win)  # the position at ring index j (< 0: none yet)
        window_slots_topk = pool.ring_slots(table[:, None], p).view(bs, 1, win)
        return window_slots, window_slots_topk


@dataclass
class DSV41CaptureData:
    full_snap: torch.Tensor
    last_indices: torch.Tensor
    table_rows: torch.Tensor  # each batch row's page-table row (the private window rings key on it)

    @classmethod
    def create(cls, max_bs: int, width: int, device: torch.device) -> "DSV41CaptureData":
        return cls(
            full_snap=torch.full((max_bs, width), -1, dtype=torch.int64, device=device),
            last_indices=torch.arange(max_bs, dtype=torch.int32, device=device),
            table_rows=torch.zeros(max_bs, dtype=torch.int64, device=device),
        )


class DSV41SparseAttnBackend(BaseAttnBackend):
    def __init__(self, config: ModelConfig):
        self.config = config
        self.device = get_global_ctx().kv_cache.device
        args = config.dsv41_args
        self.window_size = args.window_size
        self.swa_decoder_replay: str = args.swa_decoder_replay
        self.capture: DSV41CaptureData | None = None
        self.capture_bs: List[int] = []
        self.max_graph_bs = 0
        self._window_ar = torch.arange(self.window_size, device=self.device)

    @property
    def pool(self):
        return get_global_ctx().kv_cache

    # ----- generic contract -------------------------------------------------------------
    def forward(self, q, k, v, layer_id, batch, attn_spec: AttentionSpec | None = None):
        raise NotImplementedError("DSV41 attention is driven per-tier from the model module; use DSV41SparseAttnBackend.attend().")

    def prepare_metadata(self, batch: Batch) -> None:
        if not batch.is_decode:
            batch.attn_metadata = self._prefill_metadata(batch)
            return
        last = torch.tensor([r.extend_len for r in batch.padded_reqs], dtype=torch.int32, device=self.device).cumsum_(0) - 1
        batch.attn_metadata = DSV41AttnMetadata(last_indices=last, table_rows=self._table_rows(batch), window_ar=self._window_ar)

    def _prefill_metadata(self, batch: Batch) -> DSV41AttnMetadata:
        """The encoder pass runs every request's new tokens ``[cached_len, device_len)``. Exact mode runs
        the decoder on the same stream. Decoder SWA Bounded Replay runs it on the new tokens inside the
        prompt's last window ``[L - W, L)`` (``L = prompt_len``) with every query's window floored at
        ``L - W``: the chunks of a chunked prefill each take their part of that window (earlier rows
        come from the request's private ring), and a chunk that ends before it runs no decoder row."""
        segments: List[PrefillSegment] = []
        off = 0
        for r in batch.reqs:
            segments.append(PrefillSegment(off, r.extend_len, r.table_idx, r.cached_len))
            off += r.extend_len
        if self.swa_decoder_replay == "exact":
            last = torch.tensor([s.n for s in segments], dtype=torch.int32, device=self.device).cumsum_(0) - 1
            return DSV41AttnMetadata(last_indices=last, segments=segments, decoder_segments=segments)
        win = self.window_size
        dec: List[PrefillSegment] = []
        rows: list[torch.Tensor] = []
        last: list[int] = []
        doff = 0
        for r, s in zip(batch.reqs, segments):
            floor = max(0, r.prompt_len - win)
            lo = max(s.start_pos, floor)
            n = max(0, s.end - lo)
            if n:
                # the decoder's window KV goes to the request's private rings, never to radix-shared pages
                dec.append(PrefillSegment(doff, n, s.table_idx, lo, window_floor=floor))
                rows.append(torch.arange(s.offset + lo - s.start_pos, s.offset + s.n))
                doff += n
            last.append(doff - 1 if n else -1)
        pad = -1 in last
        last_indices = torch.tensor([doff if i < 0 else i for i in last], dtype=torch.int32, device=self.device)
        decoder_rows = torch.cat(rows).to(self.device, non_blocking=True) if rows else torch.empty(0, dtype=torch.int64, device=self.device)
        return DSV41AttnMetadata(last_indices=last_indices, segments=segments, decoder_segments=dec, decoder_rows=decoder_rows, decoder_pad=pad)

    def init_capture_graph(self, max_seq_len: int, bs_list: List[int], rows_per_req: int = 1) -> None:
        if rows_per_req != 1:
            raise NotImplementedError("dsv41_sparse captures decode graphs only")
        assert self.capture is None, "Capture already initialized."
        self.max_graph_bs = max(bs_list)
        self.capture = DSV41CaptureData.create(self.max_graph_bs, max_seq_len, self.device)
        self.capture_bs = sorted(bs_list)

    def prepare_for_capture(self, batch: Batch) -> None:
        bs = batch.size
        rows = torch.full((bs,), batch.padded_reqs[0].table_idx, dtype=torch.int64, device=self.device)
        self._point_to_capture(batch, bs, rows)

    def prepare_for_replay(self, batch: Batch) -> None:
        self._point_to_capture(batch, batch.padded_size, self._table_rows(batch))

    def _table_rows(self, batch: Batch) -> torch.Tensor:
        assert batch.active_table_idx is not None, "decode batch is missing its page-table rows"
        return batch.active_table_idx.to(torch.int64)

    def _point_to_capture(self, batch: Batch, bs: int, rows_ti: torch.Tensor) -> None:
        assert self.capture is not None and bs <= self.max_graph_bs
        cap = self.capture
        src = self.pool.full_loc_map.index_select(0, rows_ti)
        w = min(src.shape[1], cap.full_snap.shape[1])
        cap.full_snap[:bs, :w].copy_(src[:bs, :w])
        cap.table_rows[:bs].copy_(rows_ti[:bs])
        batch.attn_metadata = DSV41AttnMetadata(
            last_indices=cap.last_indices[:bs], full_snap=cap.full_snap[:bs], table_rows=cap.table_rows[:bs], window_ar=self._window_ar,
        )

    # ----- metadata / selection access -------------------------------------------------
    @property
    def metadata(self) -> DSV41AttnMetadata:
        md = get_global_ctx().batch.attn_metadata
        assert isinstance(md, DSV41AttnMetadata)
        return md

    @property
    def selection(self) -> SharedSelection:
        return self.metadata.selection

    def snapshot(self) -> torch.Tensor:
        return self.metadata.full_snapshot()

    # ----- window tier -------------------------------------------------------------------
    def window_slots_of(self, ti: int, lo: int, hi: int) -> torch.Tensor:
        """SHARED window slots of positions ``[lo, hi)`` off the request's LIVE full locs (slid-out -> -1)."""
        return self.pool.translate_full_to_window(self.pool.full_loc_map[ti, lo:hi])

    def ring_slots_of(self, ti: int, lo: int, hi: int) -> torch.Tensor:
        """PRIVATE-ring slots of positions ``[lo, hi)`` of page-table row ``ti`` (``hi - lo <= win``)."""
        assert hi - lo <= self.window_size, f"a private ring holds one window, not {hi - lo} positions"
        return self.pool.ring_slots(torch.tensor(ti, device=self.device), torch.arange(lo, hi, device=self.device))

    def layer_window_slots_of(self, layer_id: int, ti: int, lo: int, hi: int) -> torch.Tensor:
        """Where ``layer_id`` keeps the window KV of positions ``[lo, hi)``: its private ring or the shared pool."""
        if self.pool.is_private_window(layer_id):
            return self.ring_slots_of(ti, lo, hi)
        return self.window_slots_of(ti, lo, hi)

    def store_window(self, kv: torch.Tensor, layer_id: int, window_slots: torch.Tensor) -> None:
        self.pool.store_window(kv, layer_id, window_slots)

    def window_topk_prefill(self, seg: PrefillSegment, layer_id: int | None = None) -> torch.Tensor:
        """Per-query window candidates for a prefill segment as GLOBAL window slots ``[1, n, win]``
        (``-1`` where empty) in the tier ``layer_id`` reads (shared pool by default). Query at
        absolute ``p`` sees ``[max(floor, first_retained, p - win + 1), p]``."""
        win, device = self.window_size, self.device
        lo = max(0, seg.start_pos - win + 1, seg.window_floor)
        private = layer_id is not None and self.pool.is_private_window(layer_id)
        ws_pool = (self.ring_slots_of if private else self.window_slots_of)(seg.table_idx, lo, seg.end)  # [end - lo]
        abs_p = seg.start_pos + torch.arange(seg.n, device=device).unsqueeze(1)
        cand = (abs_p - win + 1).clamp(min=lo) + torch.arange(win, device=device)
        cols = torch.where(cand > abs_p, -1, cand - lo)
        g = ws_pool[cols.clamp_min(0)]
        return torch.where(cols < 0, -1, g).unsqueeze(0)

    # ----- compressed tiers (per kv source) ----------------------------------------------
    def source_of(self, layer_id: int) -> int:
        return self.pool.source_of(layer_id)

    def compressed_rows_of(self, ti: int, group_starts: torch.Tensor, ratio: int) -> torch.Tensor:
        """Main / index rows of the compressed groups whose ABSOLUTE first positions are
        ``group_starts``, off the request's LIVE full locs (a page is ratio-divisible, so every
        position of a group shares one row)."""
        return self.pool.cmp_rows(self.pool.full_loc_map[ti, group_starts], ratio)

    def locs_prefill(self, ti: int, end: int) -> torch.Tensor:
        """``[1, end]`` int32: the request's live full locs for positions ``[0, end)`` -- what the indexer
        derives compressed rows from (``loc // ratio``) for the positions its queries may see."""
        return self.pool.full_loc_map[ti : ti + 1, :end]

    def store_main(self, latent: torch.Tensor, source: int, rows: torch.Tensor) -> None:
        self.pool.store_main(latent, source, rows)

    def store_index(self, k: torch.Tensor, source: int, rows: torch.Tensor) -> None:
        self.pool.store_index(k, source, rows)

    def decode_store_rows(self, rows: torch.Tensor, pos: torch.Tensor, ratio: int, source: int, completed: torch.Tensor) -> torch.Tensor:
        """Per-row decode destination: the completed group's arithmetic row, or the row's OWN scratch
        row when this step did not complete a group (graph-safe, collision-free masked store)."""
        row_of_group = self.pool.cmp_rows(self.snapshot()[rows, pos], ratio)
        scratch = rows + self.pool.scratch_base[source]
        return torch.where(completed, row_of_group, scratch)

    # ----- compress-state ring (ratio > 1 sources) ---------------------------------------
    def ring_page_base(self, window_slots: torch.Tensor, ring_size: int) -> torch.Tensor:
        return torch.div(window_slots, self.window_size, rounding_mode="floor") * ring_size

    def carry_state_loc(self, window_slot: int, ring_size: int) -> torch.Tensor:
        base = (window_slot // self.window_size) * ring_size
        return torch.arange(base, base + ring_size, device=self.device, dtype=torch.int64)

    def read_carry(self, source: int, window_slot: int) -> torch.Tensor:
        """The ``[ring_size, 2 * head_dim]`` carry block at ``window_slot``'s page (kv | score)."""
        ring = self.pool.state_ring[source]
        return ring.get(self.carry_state_loc(window_slot, ring.ring_size))

    def write_carry(self, source: int, window_slot: int, kv_score: torch.Tensor) -> None:
        ring = self.pool.state_ring[source]
        ring.set(self.carry_state_loc(window_slot, ring.ring_size), kv_score)

    def read_carry_blocks(self, source: int, window_slots: torch.Tensor) -> torch.Tensor:
        ring = self.pool.state_ring[source]
        return ring.get_blocks(self.ring_page_base(window_slots, ring.ring_size))

    def write_carry_blocks(self, source: int, window_slots: torch.Tensor, blocks: torch.Tensor) -> None:
        ring = self.pool.state_ring[source]
        ring.set_blocks(self.ring_page_base(window_slots, ring.ring_size), blocks)

    def write_boundary_carries(self, source: int, *, lo: int, hi: int, window_slots: torch.Tensor) -> None:
        """Persist the compressor carry at every window-page boundary ``B`` in ``(lo, hi]`` so a
        page-aligned radix match can resume by value. A page holds whole groups (``P % ratio == 0``),
        so the carry at a boundary is the empty group -- the reset block is written so a resume never
        reads a stale one. ``window_slots`` is indexed by ``pos - lo``. One batched ring write, no host syncs."""
        ring = self.pool.state_ring.get(source)
        if ring is None:
            return
        P = self.window_size
        first = (lo // P + 1) * P
        if first > hi:
            return
        bounds = torch.arange(first, hi + 1, P, device=self.device)
        page_slots = window_slots[bounds - 1 - lo].to(torch.int64)  # the last slot of each page
        locs = (torch.div(page_slots, P, rounding_mode="floor") * ring.ring_size)[:, None] + torch.arange(ring.ring_size, device=self.device)
        empty = torch.cat([
            torch.zeros(ring.ring_size, ring.item_size, dtype=torch.float32, device=self.device),
            torch.full((ring.ring_size, ring.item_size), float("-inf"), dtype=torch.float32, device=self.device),
        ], dim=-1)
        ring.set(locs.flatten(), empty.repeat(bounds.numel(), 1))

    # ----- indexer ----------------------------------------------------------------------
    def indexer_logits(
        self, q: torch.Tensor, weights: torch.Tensor, source: int, locs: torch.Tensor, ratio: int, live: torch.Tensor,
        T: int | None = None, candidates: torch.Tensor | None = None,
    ) -> torch.Tensor:
        """``[B, S, T]`` full-range scores (live columns written) or ``[B, S, NC]`` candidate scores; the
        row of compressed position ``t`` is ``locs[b, t * ratio] // ratio``."""
        from freetoken.kernel.triton.dsv41.indexer import indexer_logits_packed

        return indexer_logits_packed(q, weights, self.pool.idx_pool[source], self.pool.idx_fmt, locs, ratio, live, T=T, candidates=candidates)

    @staticmethod
    def select_topk(scores: torch.Tensor, live: torch.Tensor, topk: int) -> torch.Tensor:
        """Exact causal top-k over ``[B, S, T]`` full-range scores (columns at or past ``live`` unread):
        compressed positions ``[B, S, topk]`` int32 in ascending order, ``-1`` in the tail for picks
        that do not exist (fewer live or finite positions than ``topk``). Ties: lowest position wins."""
        from freetoken.kernel.triton.dsv41.topk import dsv41_topk

        b, s, t = scores.shape
        return dsv41_topk(scores.reshape(b * s, t), live.reshape(b * s), topk).view(b, s, topk)

    @staticmethod
    def select_topk_in_candidates(scores: torch.Tensor, candidates: torch.Tensor, topk: int) -> torch.Tensor:
        """Top-k over ``[B, S, NC]`` candidate-aligned scores -> the picked compressed positions
        ``[B, S, topk]`` int32. The candidate list is a sorted valid prefix (``-1`` tail) and empty /
        unreachable slots score ``-inf``, so the ascending winning slots map to ascending positions."""
        from freetoken.kernel.triton.dsv41.topk import dsv41_topk

        b, s, nc = scores.shape
        live = torch.full((b * s,), nc, dtype=torch.int32, device=scores.device)
        slots = dsv41_topk(scores.reshape(b * s, nc), live, topk).view(b, s, topk)
        pos = candidates.gather(-1, slots.clamp_min(0).to(torch.int64)).to(torch.int32)
        return torch.where(slots < 0, -1, pos)

    @staticmethod
    def select_candidate_blocks(scores: torch.Tensor, live: torch.Tensor, topk_blocks: int, block_size: int) -> torch.Tensor:
        """Level one of the Hierarchical Sparse Indexer: the ``topk_blocks`` best live ``block_size``
        blocks by their best position, the block holding the newest live position always kept,
        expanded to the compact candidate list ``[B, S, topk_blocks * block_size]`` int32 of
        compressed positions (ascending, ``-1`` tail). Mirrors the reference ``select_candidate_blocks``
        (which returns the equivalent boolean mask)."""
        from freetoken.kernel.triton.dsv41.topk import dsv41_candidate_blocks

        b, s, t = scores.shape
        return dsv41_candidate_blocks(scores.reshape(b * s, t), live.reshape(b * s), topk_blocks, block_size).view(b, s, -1)

    @staticmethod
    def positions_to_rows(positions: torch.Tensor, locs: torch.Tensor, ratio: int) -> torch.Tensor:
        """Compressed positions ``[B, S, K]`` (``-1`` masked) -> GLOBAL main rows ``locs[b, p * ratio] // ratio``."""
        b = positions.shape[0]
        idx = (positions.to(torch.int64) * ratio).clamp_min(0).flatten(1)
        full = locs.to(torch.int64).gather(1, idx.clamp(max=locs.shape[1] - 1)).view_as(positions)
        rows = torch.div(full, ratio, rounding_mode="floor")
        return torch.where((positions < 0) | (full < 0), -1, rows)

    # ----- attention -----------------------------------------------------------------------
    def attend(
        self, q: torch.Tensor, layer_id: int, topk_idxs: torch.Tensor, n_window: int, attn_sink: torch.Tensor,
        softmax_scale: float, cmp_counts: torch.Tensor | None = None,
    ) -> torch.Tensor:
        """Paged sparse attention over ``[window | compressed]`` global rows; the compressed half reads
        the layer's kv source (window-only layers pass ``n_window == topk``)."""
        from freetoken.kernel.triton.dsv41.sparse_attn import sparse_attn_packed

        pool, args = self.pool, self.config.dsv41_args
        src = args.roles[layer_id].kv_source
        cmp = pool.main_pool[src] if src is not None else pool.main_pool[args.backbone_kv_sources[0]]
        return sparse_attn_packed(
            q, pool.window_pool[layer_id], pool.win_fmt, cmp, pool.main_fmt, attn_sink,
            topk_idxs, n_window, softmax_scale, cmp_counts=cmp_counts,
        )


__all__ = ["DSV41SparseAttnBackend", "DSV41AttnMetadata", "PrefillSegment", "SharedSelection"]