Skip to content

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

21.5 KB
Raw Blame
"""The modified and original QSA Triton kernels against pure-torch references.

Only kernels FreeToken changed or wrote get unit tests: the compression kernel (re-addressed
pending ring, its own torch check) and the block top-k (original radix select, checked against
torch.topk and, through the expansion chain, against the vLLM reference semantics). score.py
and attend.py are vendored from vLLM and are covered by the backend and e2e tests.
``_qsa_mqa_paged_reference`` / ``_qsa_relative_topk_reference`` / ``_expand_qsa_indices_reference``
are transcribed from ``vllm/tests/test_qsa_reference.py`` (Apache-2.0).
"""

from __future__ import annotations

import math

import pytest
import torch

from .common import Fixture, requires_cuda, parsed_config

PAGE_SIZE = 64
RATIO = 4
BUDGET = 2048
INDEX_DIM = 128
CMP_PAGE = PAGE_SIZE // RATIO


# --------------------------------------------------------------------------------------
# vLLM pure-torch references (tests/test_qsa_reference.py:87-227)
# --------------------------------------------------------------------------------------


def _qsa_mqa_paged_reference(q, k_cache, page_table, token_to_req, visible_lengths):
    pages = page_table.index_select(0, token_to_req.long()).long()
    keys = k_cache[pages, :, 0, :].flatten(1, 2)
    scores = torch.einsum("rhd,rnd->rnh", q.float(), keys.float())
    logits = torch.relu(scores).sum(dim=-1) / math.sqrt(q.shape[-1])
    positions = torch.arange(keys.shape[1], device=q.device).unsqueeze(0)
    return logits.masked_fill(positions >= visible_lengths.unsqueeze(1), -torch.inf)


def _qsa_relative_topk_reference(logits, row_starts, row_ends, topk):
    output = torch.full((logits.shape[0], topk), -1, dtype=torch.int32, device=logits.device)
    for row in range(logits.shape[0]):
        start = int(row_starts[row].item())
        length = int((row_ends[row] - row_starts[row]).item())
        width = min(length, topk)
        if width:
            output[row, :width] = torch.topk(
                logits[row, start : start + length], width
            ).indices.to(torch.int32)
    return output


def _expand_qsa_indices_reference(
    block_indices, query_positions, sequence_lengths, compress_ratio, token_topk
):
    rows = block_indices.shape[0]
    block_topk = token_topk // compress_ratio
    output_width = token_topk + compress_ratio - 1
    offsets = torch.arange(compress_ratio, device=block_indices.device)
    blocks = block_indices.long()
    expanded = blocks.unsqueeze(-1) * compress_ratio + offsets
    expanded = torch.where(
        blocks.unsqueeze(-1) >= 0, expanded, torch.full_like(expanded, -1)
    ).reshape(rows, block_topk * compress_ratio)
    expanded = expanded[:, :token_topk]
    expanded = torch.where(
        (expanded >= 0) & (expanded < sequence_lengths.unsqueeze(1)),
        expanded,
        torch.full_like(expanded, -1),
    )

    tail_offsets = torch.arange(compress_ratio - 1, device=block_indices.device)
    visible_tokens = query_positions + 1
    tail_start = visible_tokens // compress_ratio * compress_ratio
    tail = tail_start.unsqueeze(1) + tail_offsets.unsqueeze(0)
    tail_count = (visible_tokens - tail_start).unsqueeze(1)
    tail_valid = (tail_offsets.unsqueeze(0) < tail_count) & (
        tail < sequence_lengths.unsqueeze(1)
    )
    tail = torch.where(tail_valid, tail, torch.full_like(tail, -1))

    result = torch.cat((expanded, tail), dim=1)
    order = torch.arange(output_width, device=result.device).expand(rows, -1)
    sort_key = torch.where(result >= 0, order, order + output_width)
    return result.gather(1, torch.argsort(sort_key, dim=1, stable=True)).to(torch.int32)


class _Case:
    def __init__(self, **fields):
        self.__dict__.update(fields)


def _paged_case(length: int, bs: int, rows_per_req: int, seed: int, index_heads: int = 4):
    """Synthetic paged geometry: shuffled pages, the last ``rows_per_req`` queries per request."""
    device = torch.device("cuda")
    torch.manual_seed(seed)
    generator = torch.Generator(device=device).manual_seed(seed)
    pages_per_req = -(-length // PAGE_SIZE)
    total_pages = bs * pages_per_req
    block_table = (
        torch.randperm(total_pages, device=device).reshape(bs, pages_per_req).to(torch.int32)
    )
    q = torch.randn(
        bs * rows_per_req, index_heads, INDEX_DIM, device=device, dtype=torch.bfloat16,
        generator=generator,
    )
    token_to_req = torch.repeat_interleave(
        torch.arange(bs, device=device, dtype=torch.int32), rows_per_req
    )
    query_positions = torch.cat(
        [
            torch.arange(length - rows_per_req, length, device=device, dtype=torch.int32)
            for _ in range(bs)
        ]
    )
    seq_lens = torch.full((bs,), length, device=device, dtype=torch.int32)
    return _Case(
        device=device,
        generator=generator,
        length=length,
        bs=bs,
        pages_per_req=pages_per_req,
        total_pages=total_pages,
        block_table=block_table,
        q=q,
        token_to_req=token_to_req,
        query_positions=query_positions,
        seq_lens=seq_lens,
    )


@requires_cuda
@pytest.mark.parametrize("length", [20000])
@pytest.mark.parametrize("bs", [1])
@pytest.mark.parametrize("torch_topk", [False, True])
def test_top_blocks_and_expansion_match_vllm_reference(length: int, bs: int, torch_topk: bool):
    from freetoken.kernel.triton.qsa import expand_qsa_block_indices, qsa_mqa_paged

    config = parsed_config()
    fixture = Fixture(config, num_pages=4, max_running_req=2)
    case = _paged_case(length, bs, rows_per_req=4, seed=7 * length + bs)
    cache = torch.randn(
        case.total_pages, CMP_PAGE, 1, INDEX_DIM, device=case.device,
        dtype=torch.bfloat16, generator=case.generator,
    )
    rows, columns = case.q.shape[0], case.pages_per_req * CMP_PAGE
    logits = torch.empty(rows, columns, dtype=torch.float32, device=case.device)
    visible = torch.empty(rows, dtype=torch.int32, device=case.device)
    qsa_mqa_paged(
        case.q, cache, case.block_table, case.token_to_req, case.query_positions,
        case.seq_lens, RATIO, logits, visible,
    )
    blocks = torch.empty(rows, BUDGET // RATIO, dtype=torch.int32, device=case.device)
    reference_logits = _qsa_mqa_paged_reference(
        case.q, cache, case.block_table, case.token_to_req, visible
    )
    if torch_topk:
        fixture.backend._block_topk_kernel = None
    fixture.backend._top_blocks(logits, visible, blocks)

    expected_blocks = _qsa_relative_topk_reference(
        reference_logits, torch.zeros_like(visible), visible, BUDGET // RATIO
    )
    # Ties between equal scores may land on either index; the SET is what selection means.
    torch.testing.assert_close(blocks.sort(-1).values, expected_blocks.sort(-1).values)

    row_seq_lens = case.seq_lens.index_select(0, case.token_to_req.long())
    indices = torch.empty(rows, BUDGET + RATIO - 1, dtype=torch.int32, device=case.device)
    expand_qsa_block_indices(
        expected_blocks, case.query_positions, case.seq_lens, case.token_to_req,
        RATIO, BUDGET, indices,
    )
    expected = _expand_qsa_indices_reference(
        expected_blocks, case.query_positions, row_seq_lens, RATIO, BUDGET
    )
    torch.testing.assert_close(indices, expected)


@requires_cuda
@pytest.mark.parametrize("ring_capacity", [4, 8])
def test_compression_reads_both_sources(ring_capacity: int):
    """Members already consumed come from the ring, the rest from this forward's raw rows."""
    from freetoken.kernel.triton.qsa import qsa_compress_groups, qsa_store_rows

    device = torch.device("cuda")
    dim, slots = 8, 3
    pairs = [(0, p) for p in range(2, 9)] + [(1, p) for p in range(5, 11)]

    def key(request: int, position: int) -> torch.Tensor:
        return (torch.arange(dim, dtype=torch.float32) + request * 1000 + position * 10).to(
            torch.bfloat16
        )

    raw = torch.stack([key(*pair) for pair in pairs]).to(device)
    token_to_req = torch.tensor([r for r, _ in pairs], dtype=torch.int32, device=device)
    positions = torch.tensor([p for _, p in pairs], dtype=torch.int32, device=device)
    cu_seqlens = torch.tensor([0, 7, 13], dtype=torch.int32, device=device)
    ring_slots = torch.tensor([2, 0], dtype=torch.int32, device=device)
    ring = torch.zeros(slots, ring_capacity, dim, device=device, dtype=torch.bfloat16)
    for request, position, slot in ((0, 0, 2), (0, 1, 2), (1, 4, 0)):
        ring[slot, position % ring_capacity] = key(request, position).to(device)

    pooled = torch.empty(len(pairs), dim, device=device, dtype=torch.bfloat16)
    first = torch.empty(len(pairs), dtype=torch.int32, device=device)
    qsa_compress_groups(
        raw, ring, ring_slots, token_to_req, cu_seqlens, positions, RATIO, pooled, first
    )

    for row, (request, position) in enumerate(pairs):
        if (position + 1) % RATIO:
            continue
        group = torch.stack([key(request, position - RATIO + 1 + k).float() for k in range(RATIO)])
        expected = group.mean(0).to(torch.bfloat16).to(device)
        assert torch.equal(pooled[row], expected), (request, position)
        assert int(first[row]) == position - RATIO + 1

    # The ring keeps only each request's last ring_capacity rows.
    rows = torch.arange(len(pairs), device=device)
    ends = cu_seqlens.long().index_select(0, token_to_req.long() + 1)
    slot = torch.where(
        rows >= ends - ring_capacity,
        ring_slots.long().index_select(0, token_to_req.long()) * ring_capacity
        + positions.long() % ring_capacity,
        torch.full_like(rows, -1),
    )
    qsa_store_rows(ring, slot.to(torch.int32), raw)
    for request, ring_slot in ((0, 2), (1, 0)):
        for position in [p for r, p in pairs if r == request][-ring_capacity:]:
            assert torch.equal(
                ring[ring_slot, position % ring_capacity], key(request, position).to(device)
            )


# --------------------------------------------------------------------------------------
# Block top-k (kernel/triton/qsa/topk.py)
# --------------------------------------------------------------------------------------

TOPK_SHAPES = [(512, 512), (4096, 512)]


def _torch_topk_blocks(logits, visible, width):
    """The torch.topk fallback of ``qsa_sparse._top_blocks``, kept here as the reference."""
    columns = logits.shape[1]
    out = torch.full((logits.shape[0], width), -1, dtype=torch.int32, device=logits.device)
    column = torch.arange(columns, device=logits.device)
    masked = logits.masked_fill(column.unsqueeze(0) >= visible.unsqueeze(1), -float("inf"))
    take = min(width, columns)
    values, chosen = torch.topk(masked, take, dim=-1)
    out[:, :take] = torch.where(values > -float("inf"), chosen.to(torch.int32), -1)
    return out


def _topk_case(n_blocks: int, bs: int, mode: str, seed: int):
    device = torch.device("cuda")
    generator = torch.Generator(device=device).manual_seed(seed)
    logits = torch.randn(bs, n_blocks, device=device, generator=generator)
    visible = torch.full((bs,), n_blocks, dtype=torch.int32, device=device)
    if mode == "ties":
        # Three distinct scores over every column: almost every selection sits on a tie.
        logits = torch.randint(0, 3, (bs, n_blocks), device=device, generator=generator).float()
    if mode == "ragged":
        visible = torch.randint(
            0, n_blocks + 1, (bs,), dtype=torch.int32, device=device, generator=generator
        )
    if mode == "dead":
        logits[:, ::5] = -float("inf")
    return logits, visible


@requires_cuda
@pytest.mark.parametrize("n_blocks,width", TOPK_SHAPES)
@pytest.mark.parametrize("bs", [4])
@pytest.mark.parametrize("mode", ["random", "ties", "ragged", "dead"])
def test_block_topk_matches_torch_topk(n_blocks: int, width: int, bs: int, mode: str):
    from freetoken.kernel.triton.qsa import qsa_block_topk

    logits, visible = _topk_case(n_blocks, bs, mode, seed=31 * n_blocks + 7 * width + bs)
    blocks = torch.empty(bs, width, dtype=torch.int32, device=logits.device)
    qsa_block_topk(logits, visible, blocks)
    expected = _torch_topk_blocks(logits, visible, width)

    # Selection is a set: torch.topk orders by descending score, the kernel by column id.
    torch.testing.assert_close(blocks.sort(-1).values, expected.sort(-1).values)
    live = (blocks >= 0).sum(-1)
    torch.testing.assert_close(live, (expected >= 0).sum(-1))
    # expand.py reads ranks [0, complete_blocks), so a -1 may only sit in the tail.
    ranks = torch.arange(width, device=blocks.device)
    assert torch.equal(blocks >= 0, ranks.unsqueeze(0) < live.unsqueeze(1))
    assert bool(((blocks[:, 1:] > blocks[:, :-1]) | (blocks[:, 1:] < 0)).all())


@requires_cuda
def test_block_topk_replays_in_a_cuda_graph():
    """Fixed grid, no host read: one capture serves every later sequence length."""
    from freetoken.kernel.triton.qsa import qsa_block_topk

    rows, columns, width = 4, 4096, 512
    device = torch.device("cuda")
    logits = torch.randn(rows, columns, device=device)
    visible = torch.full((rows,), columns, dtype=torch.int32, device=device)
    blocks = torch.empty(rows, width, dtype=torch.int32, device=device)

    side = torch.cuda.Stream()
    side.wait_stream(torch.cuda.current_stream())
    with torch.cuda.stream(side):
        qsa_block_topk(logits, visible, blocks)
    torch.cuda.current_stream().wait_stream(side)
    graph = torch.cuda.CUDAGraph()
    with torch.cuda.graph(graph):
        qsa_block_topk(logits, visible, blocks)

    for lengths in ([columns] * rows, [columns // 2, 900, 37, 0], [4095, 512, 511, 4096]):
        logits.normal_()
        visible.copy_(torch.tensor(lengths, dtype=torch.int32, device=device))
        blocks.fill_(0)
        graph.replay()
        expected = _torch_topk_blocks(logits, visible, width)
        torch.testing.assert_close(blocks.sort(-1).values, expected.sort(-1).values)


def test_torch_topk_env_picks_the_fallback(monkeypatch):
    from freetoken.attention.qsa_sparse import TORCH_TOPK_ENV, _resolve_block_topk

    assert _resolve_block_topk() is not None
    monkeypatch.setenv(TORCH_TOPK_ENV, "1")
    assert _resolve_block_topk() is None


# --------------------------------------------------------------------------------------
# Block top-k, split + merge path (wide buffers)
# --------------------------------------------------------------------------------------

# (columns, _split_plan's chunk). A 1M-token window scores 262,144 compressed rows, and its 32
# splits leave more candidates than one program holds, so a reduction level runs before the merge.
SPLIT_SHAPES = [(65536, 4096), (262144, 8192)]


def _split_chunk(columns: int, width: int) -> int:
    from freetoken.kernel.triton.qsa.topk import _split_plan

    plan = _split_plan(columns, width)
    assert plan is not None, f"{columns} columns must take the split path"
    return plan.chunk


def _policy_topk_blocks(logits, visible, width):
    """The kernel's documented order: highest score wins, lowest column breaks a tie."""
    columns = logits.shape[1]
    column = torch.arange(columns, device=logits.device)
    masked = logits.masked_fill(column.unsqueeze(0) >= visible.unsqueeze(1), -float("inf"))
    take = min(width, columns)
    order = masked.argsort(dim=-1, descending=True, stable=True)[:, :take]
    out = torch.full((logits.shape[0], width), -1, dtype=torch.int32, device=logits.device)
    out[:, :take] = torch.where(
        masked.gather(1, order) > -float("inf"), order.to(torch.int32), -1
    )
    return out


def _split_topk_case(n_blocks: int, chunk: int, width: int, bs: int, mode: str, seed: int):
    if mode != "boundary":
        return _topk_case(n_blocks, bs, mode, seed)
    # width - 212 columns beat the tie, so the 212 remaining winners start 100 columns below
    # a chunk boundary and run past it into a chunk that is all tie. The last row cuts at the
    # middle split boundary, which is where a reduction level divides the candidates.
    logits = torch.zeros(bs, n_blocks, device="cuda")
    splits = n_blocks // chunk
    for row in range(bs):
        cut = chunk * (splits // 2 if row == bs - 1 else 1 + row % (splits - 1))
        logits[row, : width - 212] = 2.0
        logits[row, cut - 100 :] = 1.0
    return logits, torch.full((bs,), n_blocks, dtype=torch.int32, device="cuda")


@requires_cuda
@pytest.mark.parametrize("n_blocks,chunk", SPLIT_SHAPES)
@pytest.mark.parametrize("bs", [4])
@pytest.mark.parametrize("mode", ["random", "boundary", "ragged", "dead"])
def test_block_topk_split_path_matches_torch_topk(n_blocks: int, chunk: int, bs: int, mode: str):
    from freetoken.kernel.triton.qsa import qsa_block_topk, qsa_block_topk_scratch_width

    width = 512
    assert qsa_block_topk_scratch_width(n_blocks, width) > 0, "case must take the split path"
    assert _split_chunk(n_blocks, width) == chunk
    logits, visible = _split_topk_case(
        n_blocks, chunk, width, bs, mode, seed=n_blocks + bs + len(mode)
    )
    blocks = torch.empty(bs, width, dtype=torch.int32, device=logits.device)
    qsa_block_topk(logits, visible, blocks)

    torch.testing.assert_close(
        blocks.sort(-1).values, _torch_topk_blocks(logits, visible, width).sort(-1).values
    )
    # Tie determinism: the winners are the exact set the lowest-column-first policy names,
    # including the ties that straddle a chunk boundary.
    torch.testing.assert_close(
        blocks.sort(-1).values, _policy_topk_blocks(logits, visible, width).sort(-1).values
    )
    live = (blocks >= 0).sum(-1)
    ranks = torch.arange(width, device=blocks.device)
    assert torch.equal(blocks >= 0, ranks.unsqueeze(0) < live.unsqueeze(1))
    assert bool(((blocks[:, 1:] > blocks[:, :-1]) | (blocks[:, 1:] < 0)).all())


@requires_cuda
@pytest.mark.parametrize("preallocated", [False, True])
def test_block_topk_split_path_replays_in_a_cuda_graph(preallocated: bool):
    """The split geometry comes from the buffer width, so one capture serves every length."""
    from freetoken.kernel.triton.qsa import qsa_block_topk, qsa_block_topk_scratch_width

    rows, columns, width = 4, 65536, 512
    device = torch.device("cuda")
    scratch_width = qsa_block_topk_scratch_width(columns, width)
    assert scratch_width > 0
    logits = torch.randn(rows, columns, device=device)
    visible = torch.full((rows,), columns, dtype=torch.int32, device=device)
    blocks = torch.empty(rows, width, dtype=torch.int32, device=device)
    # The scratch never needs clearing: every split rewrites its own slots on every replay.
    scratch = (
        torch.empty(rows, scratch_width, dtype=torch.int32, device=device)
        if preallocated
        else None
    )

    side = torch.cuda.Stream()
    side.wait_stream(torch.cuda.current_stream())
    with torch.cuda.stream(side):
        qsa_block_topk(logits, visible, blocks, scratch)
    torch.cuda.current_stream().wait_stream(side)
    graph = torch.cuda.CUDAGraph()
    with torch.cuda.graph(graph):
        qsa_block_topk(logits, visible, blocks, scratch)

    for lengths in ([columns] * rows, [4096, 40000, 0, 65535], [1, 4097, 8192, columns]):
        logits.normal_()
        visible.copy_(torch.tensor(lengths, dtype=torch.int32, device=device))
        blocks.fill_(0)
        graph.replay()
        expected = _torch_topk_blocks(logits, visible, width)
        torch.testing.assert_close(blocks.sort(-1).values, expected.sort(-1).values)


@requires_cuda
def test_block_topk_split_path_cost_tracks_live_blocks():
    """A wide buffer with a short row must not pay for the splits past its visible tail."""
    from freetoken.kernel.triton.qsa import qsa_block_topk, qsa_block_topk_scratch_width

    # enough rows that the live splits fill the card, so their work outweighs the launch floor
    rows, columns, width = 8, 262144, 512
    assert qsa_block_topk_scratch_width(columns, width) > 0, "case must take the split path"
    chunk = _split_chunk(columns, width)
    device = torch.device("cuda")
    logits = torch.randn(rows, columns, device=device)
    visible = torch.full((rows,), columns, dtype=torch.int32, device=device)
    blocks = torch.empty(rows, width, dtype=torch.int32, device=device)
    scratch = torch.empty(
        rows, qsa_block_topk_scratch_width(columns, width), dtype=torch.int32, device=device
    )

    side = torch.cuda.Stream()
    side.wait_stream(torch.cuda.current_stream())
    with torch.cuda.stream(side):
        qsa_block_topk(logits, visible, blocks, scratch)
    torch.cuda.current_stream().wait_stream(side)
    graph = torch.cuda.CUDAGraph()
    with torch.cuda.graph(graph):
        for _ in range(20):
            qsa_block_topk(logits, visible, blocks, scratch)

    def replay_us(live: int) -> float:
        visible.fill_(live)
        best = float("inf")
        for _ in range(5):
            start, stop = torch.cuda.Event(True), torch.cuda.Event(True)
            start.record()
            graph.replay()
            stop.record()
            torch.cuda.synchronize()
            best = min(best, start.elapsed_time(stop) * 1000.0 / 20)
        return best

    full, short = replay_us(columns), replay_us(chunk)
    assert full > 2.0 * short, f"{columns} live {full:.1f}us vs {chunk} live {short:.1f}us"


@requires_cuda
def test_capture_graph_provisions_the_block_topk_scratch():
    from freetoken.kernel.triton.qsa import qsa_block_topk_scratch_width

    fixture = Fixture(parsed_config(), num_pages=320, max_running_req=2)
    backend = fixture.backend
    table_width = fixture.page_table.shape[1]
    columns = table_width // PAGE_SIZE * CMP_PAGE
    width = qsa_block_topk_scratch_width(columns, backend.block_topk)
    assert width > 0, "the fixture must be wide enough to reach the split path"

    backend.init_capture_graph(table_width, [2])
    static = backend._graph["topk_scratch"]
    assert static.shape[1] == width
    assert backend._scratch("topk_scratch", 2, width, dtype=torch.int32).data_ptr() == (
        static.data_ptr()
    )