FreeToken brings datacenter-scale model serving to your desktop. Run massive models locally, fast and efficiently.
"""Exact block top-k over the QSA indexer scores.
torch.topk also sorts its k winners, which the selection never uses: expand.py expands every
rank the same way and the sparse attend kernel softmaxes over the union, so only the SET
matters. One program per row runs an MSB-first radix select on the monotone uint32 image of
the fp32 scores -- ``PASSES`` ``RADIX``-bit passes, each a histogram of the columns that still
match the fixed prefix -- and one compaction pass then emits the winners in ascending column
order, -1 padded to the output width like the torch.topk path it replaces.
A row that fits one tile is held in registers across the passes (``SINGLE_TILE``); wider rows
re-read the tile per pass, which is the price of not spilling a 256 KB row.
One program per row stops scaling once a row runs to tens of thousands of columns: the whole
row goes through a single CTA. Wide buffers therefore split. Phase 1 gives each ``CHUNK``-wide
slice of a row its own program, which radix-selects the slice's own top-k into a candidate
workspace; phase 2 runs the same radix select over the union of those candidates. The global
top-k is a subset of that union -- a global winner beats at most k-1 columns, so it beats all
but at most k-1 of its own slice -- so the answer stays exact. ``_split_plan`` derives the
geometry from the buffer width alone, which is fixed when a graph is captured.
A row wide enough to leave more candidates than one program holds resident (262,144 columns,
a 1M-token window, leaves 32 x k) gets reduction levels between the two phases: each program
of a level takes ``_MAX_RESIDENT`` consecutive candidates of the level before and writes their
own top-k, until the survivors fit the merge. The same subset argument holds per level, and
candidates stay in ascending column order throughout, so ties still go to the lowest column.
"""
from __future__ import annotations
from dataclasses import dataclass
import torch
import triton
import triton.language as tl
# 5-bit digits beat 8-bit ones here: tl.histogram cost grows faster with the bin count than the
# extra passes cost. 35 bits of digit cover the 32-bit key, the top pass just sees zero bits.
_RADIX = 5
_BINS = 1 << _RADIX
_PASSES = -(-32 // _RADIX)
_MAX_BLOCK_N = 4096
# A resident tile costs ~2 ns per column against ~3.2 ns for a re-read one, so both split
# phases stay resident; past 8192 the tile spills (255 registers) and that reverses.
_MAX_RESIDENT = 8192
_MIN_CHUNK = 4096
@triton.jit
def _monotone_key(value):
"""fp32 -> uint32 with the float order preserved; key 0 is reserved for a dead column."""
bits = value.to(tl.uint32, bitcast=True)
return tl.where((bits >> 31) == 0, bits | 0x80000000, ~bits)
@triton.jit
def _load_keys(logits_row, columns, limit):
live = columns < limit
value = tl.load(logits_row + columns, mask=live, other=-float("inf"))
return tl.where(live & (value > -float("inf")), _monotone_key(value), 0)
@triton.jit
def _narrow(hist, prefix, keep, k_rem, shift, BINS: tl.constexpr):
"""One radix step: pin the digit at ``shift`` and report whether the range is settled."""
bins = tl.arange(0, BINS)
# Lowest bin whose strictly-greater bins no longer cover k_rem holds the k_rem-th key;
# `above` falls with the bin id, so the predicate is an upper set.
above = tl.sum(hist) - tl.cumsum(hist, axis=0)
inside = above < k_rem
bin_id = tl.min(tl.where(inside, bins, BINS - 1))
hit = bins == bin_id
prefix |= bin_id.to(tl.uint32) << shift
keep |= tl.full((), BINS - 1, tl.uint32) << shift
k_rem -= tl.sum(tl.where(hit, above, 0))
# The whole bin fits: `prefix` is a lower bound, the ties below it all win.
return prefix, keep, k_rem, k_rem == tl.sum(tl.where(hit, hist, 0))
@triton.jit
def _resident_prefix(key, k_eff, BINS: tl.constexpr, RADIX: tl.constexpr, PASSES: tl.constexpr):
"""Radix-select a register-resident tile; returns the winning key range and its tie budget."""
# Invariant per pass: `k_rem` winners are still to be found inside the key range that
# `prefix` pins on the `keep` bits, and every key above that range is already a winner.
prefix = tl.zeros((), tl.uint32)
keep = tl.zeros((), tl.uint32)
k_rem = k_eff
settled = False
for step in tl.static_range(PASSES):
shift = RADIX * (PASSES - 1 - step)
if not settled:
hist = tl.histogram(
((key >> shift) & (BINS - 1)).to(tl.int32),
BINS,
mask=(key != 0) & ((key & keep) == prefix),
)
prefix, keep, k_rem, settled = _narrow(hist, prefix, keep, k_rem, shift, BINS)
return prefix, tl.where(settled, k_eff, k_rem)
@triton.jit
def _tile_ranks(key, prefix, ties, above_base, equal_base):
"""Rank every winner of one tile, and carry the running counts past it.
One packed cumsum carries both: keys above the threshold in the low half, keys equal to it
in the high half, so a winner's rank is ``above_before + min(equal_before, ties)``."""
greater = ((key > prefix) & (key != 0)).to(tl.int32)
equal = ((key == prefix) & (key != 0)).to(tl.int32)
packed = greater | (equal << 16)
before = tl.cumsum(packed, axis=0) - packed
rank_equal = equal_base + (before >> 16)
take = (greater == 1) | ((equal == 1) & (rank_equal < ties))
rank = above_base + (before & 0xFFFF) + tl.minimum(rank_equal, ties)
total = tl.sum(packed)
return rank, take, above_base + (total & 0xFFFF), equal_base + (total >> 16)
@triton.jit
def _compact(
out_row,
key,
columns,
prefix,
ties,
above_base,
equal_base,
TOP_K: tl.constexpr,
BLOCK_N: tl.constexpr,
):
"""Emit one tile's winners at their global ranks; returns the running counts after it."""
tl.static_assert(BLOCK_N <= 0xFFFF, "packed cumsum keeps 16 bits per half")
rank, take, above, equal = _tile_ranks(key, prefix, ties, above_base, equal_base)
tl.store(out_row + rank, columns.to(tl.int32), mask=take & (rank < TOP_K))
return above, equal
@triton.jit
def _live_candidates(
visible,
CHUNK: tl.constexpr,
N_SPLITS: tl.constexpr,
TOP_K: tl.constexpr,
LEVEL: tl.constexpr,
RESIDENT: tl.constexpr,
):
"""Candidate slots level ``LEVEL`` filled for a row: its splits past the row's visible tail
are one skipped suffix, so every later stage keeps costing what the live part costs."""
live = tl.minimum(tl.cdiv(visible, CHUNK), N_SPLITS) * TOP_K
for _ in tl.static_range(LEVEL):
live = tl.cdiv(live, RESIDENT) * TOP_K
return live
@triton.jit
def _emit_candidates(
key,
column,
k_eff,
key_out,
col_out,
TOP_K: tl.constexpr,
BINS: tl.constexpr,
RADIX: tl.constexpr,
PASSES: tl.constexpr,
):
"""Write a resident tile's own top-k as ranked (key, column) candidates; returns how many."""
prefix, ties = _resident_prefix(key, k_eff, BINS, RADIX, PASSES)
rank, take, above, equal = _tile_ranks(key, prefix, ties, 0, 0)
write = take & (rank < TOP_K)
tl.store(key_out + rank, key.to(tl.int32, bitcast=True), mask=write)
tl.store(col_out + rank, column, mask=write)
return above + tl.minimum(equal, ties)
@triton.jit
def _qsa_block_topk_kernel(
logits_ptr,
visible_ptr,
out_ptr,
stride_logits_row,
stride_out_row,
num_columns,
TOP_K: tl.constexpr,
PAD_K: tl.constexpr,
BLOCK_N: tl.constexpr,
SINGLE_TILE: tl.constexpr,
BINS: tl.constexpr,
RADIX: tl.constexpr,
PASSES: tl.constexpr,
) -> None:
row = tl.program_id(0)
limit = tl.maximum(tl.minimum(tl.load(visible_ptr + row), num_columns), 0)
k_eff = tl.minimum(limit, TOP_K)
logits_row = logits_ptr + row.to(tl.int64) * stride_logits_row
out_row = out_ptr + row.to(tl.int64) * stride_out_row
offsets = tl.arange(0, BLOCK_N)
tiles = tl.cdiv(limit, BLOCK_N)
if SINGLE_TILE:
resident = _load_keys(logits_row, offsets, limit)
emitted = 0
if k_eff > 0:
if SINGLE_TILE:
prefix, ties = _resident_prefix(resident, k_eff, BINS, RADIX, PASSES)
else:
prefix = tl.zeros((), tl.uint32)
keep = tl.zeros((), tl.uint32)
k_rem = k_eff
settled = False
for step in tl.static_range(PASSES):
shift = RADIX * (PASSES - 1 - step)
if not settled:
hist = tl.zeros((BINS,), tl.int32)
for tile in range(tiles):
key = _load_keys(logits_row, tile * BLOCK_N + offsets, limit)
hist += tl.histogram(
((key >> shift) & (BINS - 1)).to(tl.int32),
BINS,
mask=(key != 0) & ((key & keep) == prefix),
)
prefix, keep, k_rem, settled = _narrow(
hist, prefix, keep, k_rem, shift, BINS
)
ties = tl.where(settled, k_eff, k_rem)
above_base = 0
equal_base = 0
if SINGLE_TILE:
above_base, equal_base = _compact(
out_row, resident, offsets, prefix, ties, above_base, equal_base, TOP_K, BLOCK_N
)
else:
for tile in range(tiles):
columns = tile * BLOCK_N + offsets
key = _load_keys(logits_row, columns, limit)
above_base, equal_base = _compact(
out_row, key, columns, prefix, ties, above_base, equal_base, TOP_K, BLOCK_N
)
emitted = above_base + tl.minimum(equal_base, ties)
pad = tl.arange(0, PAD_K)
tl.store(out_row + pad, -1, mask=(pad >= emitted) & (pad < TOP_K))
@triton.jit
def _qsa_topk_split_kernel(
logits_ptr,
visible_ptr,
key_ptr,
col_ptr,
stride_logits_row,
stride_scratch_row,
num_columns,
TOP_K: tl.constexpr,
PAD_K: tl.constexpr,
CHUNK: tl.constexpr,
BINS: tl.constexpr,
RADIX: tl.constexpr,
PASSES: tl.constexpr,
) -> None:
"""Phase 1: one program per (row, chunk), writing the chunk's own top-k as candidates."""
tl.static_assert(CHUNK <= 0xFFFF, "packed cumsum keeps 16 bits per half")
row = tl.program_id(0)
split = tl.program_id(1)
base = split * CHUNK
visible = tl.maximum(tl.minimum(tl.load(visible_ptr + row), num_columns), 0)
limit = tl.minimum(tl.maximum(visible - base, 0), CHUNK)
k_eff = tl.minimum(limit, TOP_K)
slot = row.to(tl.int64) * stride_scratch_row + split * TOP_K
emitted = 0
if k_eff > 0:
offsets = tl.arange(0, CHUNK)
key = _load_keys(logits_ptr + row.to(tl.int64) * stride_logits_row + base, offsets, limit)
emitted = _emit_candidates(
key, (base + offsets).to(tl.int32), k_eff, key_ptr + slot, col_ptr + slot,
TOP_K, BINS, RADIX, PASSES,
)
# A key of 0 is the dead-column sentinel, so the merge needs no separate count per slot.
pad = tl.arange(0, PAD_K)
tl.store(key_ptr + slot + pad, 0, mask=(pad >= emitted) & (pad < TOP_K))
@triton.jit
def _reduce_tile(
in_key,
in_col,
out_key,
out_col,
count,
k_eff,
TOP_K: tl.constexpr,
BLOCK: tl.constexpr,
BINS: tl.constexpr,
RADIX: tl.constexpr,
PASSES: tl.constexpr,
):
"""Top-k of ``count`` candidates held as one resident tile; returns how many it wrote."""
tl.static_assert(BLOCK <= 0xFFFF, "packed cumsum keeps 16 bits per half")
offsets = tl.arange(0, BLOCK)
inside = offsets < count
key = tl.load(in_key + offsets, mask=inside, other=0).to(tl.uint32, bitcast=True)
column = tl.load(in_col + offsets, mask=inside, other=-1)
return _emit_candidates(key, column, k_eff, out_key, out_col, TOP_K, BINS, RADIX, PASSES)
@triton.jit
def _qsa_topk_reduce_kernel(
visible_ptr,
in_key_ptr,
in_col_ptr,
out_key_ptr,
out_col_ptr,
stride_scratch_row,
num_columns,
TOP_K: tl.constexpr,
PAD_K: tl.constexpr,
CHUNK: tl.constexpr,
N_SPLITS: tl.constexpr,
LEVEL: tl.constexpr,
RESIDENT: tl.constexpr,
BLOCK_SMALL: tl.constexpr,
BLOCK_MID: tl.constexpr,
BINS: tl.constexpr,
RADIX: tl.constexpr,
PASSES: tl.constexpr,
) -> None:
"""A reduction level: one program per (row, ``RESIDENT`` candidates of level ``LEVEL - 1``),
writing their own top-k as this level's candidates."""
row = tl.program_id(0)
split = tl.program_id(1)
visible = tl.maximum(tl.minimum(tl.load(visible_ptr + row), num_columns), 0)
k_eff = tl.minimum(visible, TOP_K)
live = _live_candidates(visible, CHUNK, N_SPLITS, TOP_K, LEVEL - 1, RESIDENT)
base = split * RESIDENT
count = tl.minimum(tl.maximum(live - base, 0), RESIDENT)
source = row.to(tl.int64) * stride_scratch_row + base
slot = row.to(tl.int64) * stride_scratch_row + split * TOP_K
in_key, in_col = in_key_ptr + source, in_col_ptr + source
out_key, out_col = out_key_ptr + slot, out_col_ptr + slot
emitted = 0
# As in the merge: residency costs the whole tile, so a short range takes a narrower one.
if count > 0:
if count <= BLOCK_SMALL:
emitted = _reduce_tile(
in_key, in_col, out_key, out_col, count, k_eff,
TOP_K, BLOCK_SMALL, BINS, RADIX, PASSES,
)
elif count <= BLOCK_MID:
emitted = _reduce_tile(
in_key, in_col, out_key, out_col, count, k_eff,
TOP_K, BLOCK_MID, BINS, RADIX, PASSES,
)
else:
emitted = _reduce_tile(
in_key, in_col, out_key, out_col, count, k_eff,
TOP_K, RESIDENT, BINS, RADIX, PASSES,
)
pad = tl.arange(0, PAD_K)
tl.store(out_key + pad, 0, mask=(pad >= emitted) & (pad < TOP_K))
@triton.jit
def _merge_tile(
key_row,
col_row,
out_row,
candidates,
k_eff,
TOP_K: tl.constexpr,
BLOCK: tl.constexpr,
BINS: tl.constexpr,
RADIX: tl.constexpr,
PASSES: tl.constexpr,
):
"""Top-k of one resident tile of candidates; returns how many winners it wrote."""
tl.static_assert(BLOCK <= 0xFFFF, "packed cumsum keeps 16 bits per half")
offsets = tl.arange(0, BLOCK)
live = offsets < candidates
key = tl.load(key_row + offsets, mask=live, other=0).to(tl.uint32, bitcast=True)
prefix, ties = _resident_prefix(key, k_eff, BINS, RADIX, PASSES)
rank, take, above, equal = _tile_ranks(key, prefix, ties, 0, 0)
column = tl.load(col_row + offsets, mask=live, other=-1)
tl.store(out_row + rank, column, mask=take & (rank < TOP_K))
return above + tl.minimum(equal, ties)
@triton.jit
def _qsa_topk_merge_kernel(
visible_ptr,
key_ptr,
col_ptr,
out_ptr,
stride_scratch_row,
stride_out_row,
num_columns,
TOP_K: tl.constexpr,
PAD_K: tl.constexpr,
CHUNK: tl.constexpr,
N_SPLITS: tl.constexpr,
LEVEL: tl.constexpr,
RESIDENT: tl.constexpr,
BLOCK_SMALL: tl.constexpr,
BLOCK_MID: tl.constexpr,
BLOCK_FULL: tl.constexpr,
BINS: tl.constexpr,
RADIX: tl.constexpr,
PASSES: tl.constexpr,
) -> None:
"""Phase 2: one program per row over the candidates the last level ``LEVEL`` left behind."""
row = tl.program_id(0)
limit = tl.maximum(tl.minimum(tl.load(visible_ptr + row), num_columns), 0)
k_eff = tl.minimum(limit, TOP_K)
candidates = _live_candidates(limit, CHUNK, N_SPLITS, TOP_K, LEVEL, RESIDENT)
key_row = key_ptr + row.to(tl.int64) * stride_scratch_row
col_row = col_ptr + row.to(tl.int64) * stride_scratch_row
out_row = out_ptr + row.to(tl.int64) * stride_out_row
emitted = 0
if k_eff > 0:
if candidates <= TOP_K:
# One live split: its own top-k is already the row's, ranked and packed.
slot = tl.arange(0, PAD_K)
inside = slot < TOP_K
key = tl.load(key_row + slot, mask=inside, other=0)
alive = inside & (key != 0)
column = tl.load(col_row + slot, mask=alive, other=-1)
tl.store(out_row + slot, column, mask=inside)
emitted = tl.sum(alive.to(tl.int32))
# Register residency costs the whole tile even when few candidates are live, so a
# short row takes a narrower tile.
elif candidates <= BLOCK_SMALL:
emitted = _merge_tile(
key_row, col_row, out_row, candidates, k_eff,
TOP_K, BLOCK_SMALL, BINS, RADIX, PASSES,
)
elif candidates <= BLOCK_MID:
emitted = _merge_tile(
key_row, col_row, out_row, candidates, k_eff,
TOP_K, BLOCK_MID, BINS, RADIX, PASSES,
)
else:
emitted = _merge_tile(
key_row, col_row, out_row, candidates, k_eff,
TOP_K, BLOCK_FULL, BINS, RADIX, PASSES,
)
pad = tl.arange(0, PAD_K)
tl.store(out_row + pad, -1, mask=(pad >= emitted) & (pad < TOP_K))
@dataclass(frozen=True)
class _SplitPlan:
"""``chunk`` columns per first-level program, and the program count of every level: the
first splits the row, each later one reduces the candidates of the level before it."""
chunk: int
levels: tuple[int, ...]
def _split_plan(columns: int, top_k: int) -> _SplitPlan | None:
"""The split geometry of a ``columns``-wide buffer, or None to keep the one-program path."""
if top_k <= 0 or columns <= _MIN_CHUNK:
return None
max_splits = _MAX_RESIDENT // triton.next_power_of_2(top_k)
if max_splits < 2:
return None
chunk = min(_MAX_RESIDENT, max(_MIN_CHUNK, triton.next_power_of_2(-(-columns // max_splits))))
n_splits = -(-columns // chunk)
# Merging n_splits*top_k candidates has to be cheaper than scanning the row once.
if n_splits < 2 or n_splits * top_k >= columns:
return None
levels = [n_splits]
while levels[-1] * top_k > _MAX_RESIDENT:
levels.append(-(-levels[-1] * top_k // _MAX_RESIDENT))
return _SplitPlan(chunk, tuple(levels))
def qsa_block_topk_scratch_width(columns: int, top_k: int) -> int:
"""int32 columns of scratch ``qsa_block_topk`` wants per row; 0 when it needs none."""
plan = _split_plan(columns, top_k)
return 0 if plan is None else 2 * top_k * sum(plan.levels)
def qsa_block_topk(
logits: torch.Tensor,
visible: torch.Tensor,
out: torch.Tensor,
scratch: torch.Tensor | None = None,
) -> torch.Tensor:
"""Top ``out.shape[1]`` columns of every ``logits`` row below ``visible``, -1 padded.
Winners come out in ascending column order, packed at the front of the row; a row with
fewer live columns than the width, and any column scored -inf, leaves -1 in the tail.
``scratch`` is the candidate workspace of the split path (see
``qsa_block_topk_scratch_width``); it is allocated per call when the caller passes none."""
if logits.ndim != 2 or out.ndim != 2:
raise ValueError("QSA block top-k takes 2-D logits and output")
if out.shape[0] != logits.shape[0] or visible.shape != (logits.shape[0],):
raise ValueError("QSA block top-k needs one visible count and one output row per row")
if logits.dtype != torch.float32 or out.dtype != torch.int32:
raise ValueError("QSA block top-k takes fp32 logits and an int32 output")
if logits.stride(1) != 1 or out.stride(1) != 1 or visible.stride(0) != 1:
raise ValueError("QSA block top-k needs row-contiguous logits, output and counts")
rows, columns = logits.shape
top_k = out.shape[1]
if not rows or not top_k:
return out
pad_k = triton.next_power_of_2(top_k)
plan = _split_plan(columns, top_k)
if plan is None:
block_n = min(_MAX_BLOCK_N, triton.next_power_of_2(max(columns, 1)))
_qsa_block_topk_kernel[(rows,)](
logits,
visible,
out,
logits.stride(0),
out.stride(0),
columns,
TOP_K=top_k,
PAD_K=pad_k,
BLOCK_N=block_n,
SINGLE_TILE=columns <= block_n,
BINS=_BINS,
RADIX=_RADIX,
PASSES=_PASSES,
num_warps=8,
num_stages=1,
)
return out
width = 2 * top_k * sum(plan.levels)
if scratch is None:
scratch = torch.empty((rows, width), dtype=torch.int32, device=logits.device)
elif (
scratch.ndim != 2
or scratch.shape[0] < rows
or scratch.shape[1] < width
or scratch.dtype != torch.int32
or scratch.stride(1) != 1
):
raise ValueError(
f"QSA block top-k needs a row-contiguous int32 scratch of at least "
f"[{rows}, {width}], got {tuple(scratch.shape)} {scratch.dtype}"
)
# Each level's candidates: its keys, then their columns, level after level along the row.
candidates: list[tuple[torch.Tensor, torch.Tensor]] = []
offset = 0
for programs in plan.levels:
half = programs * top_k
candidates.append(
(scratch[:rows, offset : offset + half], scratch[:rows, offset + half : offset + 2 * half])
)
offset += 2 * half
keys, cols = candidates[0]
_qsa_topk_split_kernel[(rows, plan.levels[0])](
logits,
visible,
keys,
cols,
logits.stride(0),
keys.stride(0),
columns,
TOP_K=top_k,
PAD_K=pad_k,
CHUNK=plan.chunk,
BINS=_BINS,
RADIX=_RADIX,
PASSES=_PASSES,
num_warps=8,
num_stages=1,
)
for level in range(1, len(plan.levels)):
(in_keys, in_cols), (out_keys, out_cols) = candidates[level - 1], candidates[level]
_qsa_topk_reduce_kernel[(rows, plan.levels[level])](
visible,
in_keys,
in_cols,
out_keys,
out_cols,
keys.stride(0),
columns,
TOP_K=top_k,
PAD_K=pad_k,
CHUNK=plan.chunk,
N_SPLITS=plan.levels[0],
LEVEL=level,
RESIDENT=_MAX_RESIDENT,
BLOCK_SMALL=min(1024, _MAX_RESIDENT),
BLOCK_MID=min(4096, _MAX_RESIDENT),
BINS=_BINS,
RADIX=_RADIX,
PASSES=_PASSES,
num_warps=8,
num_stages=1,
)
keys, cols = candidates[-1]
merge_block = triton.next_power_of_2(keys.shape[1])
_qsa_topk_merge_kernel[(rows,)](
visible,
keys,
cols,
out,
keys.stride(0),
out.stride(0),
columns,
TOP_K=top_k,
PAD_K=pad_k,
CHUNK=plan.chunk,
N_SPLITS=plan.levels[0],
LEVEL=len(plan.levels) - 1,
RESIDENT=_MAX_RESIDENT,
BLOCK_SMALL=min(1024, merge_block),
BLOCK_MID=min(4096, merge_block),
BLOCK_FULL=merge_block,
BINS=_BINS,
RADIX=_RADIX,
PASSES=_PASSES,
num_warps=8,
num_stages=1,
)
return out
__all__ = ["qsa_block_topk", "qsa_block_topk_scratch_width"]