# Prefill indexer top-k (`dsa_topk_prefill`) | ServingStudio Kernel Library

Choose the highest-scoring index-key positions for each prefill query.

After the prefill scores, the DSA indexer keeps the top_k highest-scoring keys for each query; sparse attention then reads only those. The measurement uses one sequence whose last num_queries tokens are the queries, so query i has num_keys − num_queries + i + 1 valid scores. Scores are FP32 in rows padded to logits_row_stride.

Category: Attention; group: DSA. Interactive page: https://servingstudio.cs.washington.edu/kernels.html?kind=dsa_topk_prefill. All kernel kinds: https://servingstudio.cs.washington.edu/kernels.md.

## Formula

- `indices[q] = top_k(valid logits[q])`
- `S = num_queries · (num_keys − num_queries + 1 + num_keys) / 2`
- `GB/s = (4 · S + 8 · num_queries + 4 · num_queries · top_k) / time`
- `SGLang GB/s = (4 · S + 8 · num_queries + 8 · num_queries · top_k) / time`

## How it is measured

torch masks and selects as separate launches, timed with CUDA events: five warm-up calls, then a loop of back-to-back calls, taking the median of three runs. vllm_cuda, deep_select and sglang_cuda run once before the capture; CUPTI then counts only topKPerRowPrefill or topk_transform_prefill_kernel launches, or every DeepSelect launch, with the L2 cache flushed before each. deep_select's selection is checked against torch.topk on three rows after the warm-up call.

## Caveats

- Only one sequence is measured, on seeded standard-normal scores: unsorted like MQA logits, deterministic, and practically tie-free. Rows measured before 2026-10-08 used one sorted linspace row for every query, which slows vLLM's radix select about 1.7x at long rows. sglang_cuda takes only top_k = 2048; torch and vllm_cuda take any top_k.
- deep_select takes no row start, so it fits a span whose rows all begin at key 0: one request, or a query slice of one. vLLM's prefill indexer packs several short requests into one call with nonzero row starts; those calls need vllm_cuda.
- GB/s counts valid scores, row bounds and output indices, not padding or torch intermediates; SGLang also counts its page-table output.

## Arguments

| Argument | Type | Unit | Meaning |
| --- | --- | --- | --- |
| `num_queries` | number | tokens | Query rows whose index scores are selected. |
| `num_keys` | number | tokens | Index-key columns in each score row. |
| `num_sequences` | number | requests | Sequences represented by the score matrix. |
| `top_k` | number | tokens | Selected key positions written per query. |
| `logits_row_stride` | number | elements | Allocated elements between score rows. |
| `logits_dtype` | dtype |  | Element type of the input index scores. |
| `index_dtype` | label |  | Element type of selected key positions. |
| `span_mode` | label |  | Rule defining the valid key range of each query. |

## Metrics

- Time (`time_ms`, ms)
- Throughput (`tflops`, TFLOPS)
- Memory bandwidth (`memory_bandwidth_gbps`, GB/s)
- Energy (`energy_j`, J)

## Backends

- `torch`: PyTorch masking and topk selection as separate launches. dtypes `fp32`, any CUDA GPU.
- `vllm_cuda`: vLLM topKPerRowPrefill selects positions from each causal score row. dtypes `fp32`, any CUDA GPU. Source: https://github.com/vllm-project/vllm/blob/main/csrc/libtorch_stable/sampler.cu
- `deep_select`: DeepSelect's exact FP32 top-k (torch.ops.deep_select.topk), which vLLM uses for the decode indexer, over each row's prefix. dtypes `fp32`, SM targets `sm_100f`, GPUs B200-SXM-180GB, B300-SXM-288GB, GB200-Superchip. Source: https://github.com/vllm-project/DeepSelect
- `sglang_cuda`: SGLang fast_topk_transform_fused: top-k selection that also maps positions through the page table. dtypes `fp32`, any CUDA GPU. Source: https://github.com/sgl-project/sglang/blob/main/python/sglang/kernels/aot/csrc/elementwise/topk.cu

## Measured rows

2,115 rows in all.

| GPU | Backend | Precision | Rows |
| --- | --- | --- | --- |
| NVIDIA B200 | `deep_select` | `fp32` | 412 |
| NVIDIA B200 | `sglang_cuda` | `fp32` | 412 |
| NVIDIA B200 | `vllm_cuda` | `fp32` | 824 |
| NVIDIA H200 | `vllm_cuda` | `fp32` | 467 |

## Used by these deployments

- [GLM-5.2 FP8: vLLM, DP attention, EP](https://servingstudio.cs.washington.edu/models/GLM-5.2-FP8/glm52_vllm_dsa_moe.md) (`GLM-5.2-FP8/glm52_vllm_dsa_moe`)
- [GLM-5.2 NVFP4: SGLang, TP](https://servingstudio.cs.washington.edu/models/GLM-5.2-NVFP4/glm52_sglang_nvfp4_tp_dsa_moe.md) (`GLM-5.2-NVFP4/glm52_sglang_nvfp4_tp_dsa_moe`)
- [GLM-5.2 NVFP4: vLLM, DP attention, EP MoE](https://servingstudio.cs.washington.edu/models/GLM-5.2-NVFP4/glm52_vllm_nvfp4_dp_attn_dsa_moe.md) (`GLM-5.2-NVFP4/glm52_vllm_nvfp4_dp_attn_dsa_moe`)
- [GLM-5.2 NVFP4: vLLM, TP and EP](https://servingstudio.cs.washington.edu/models/GLM-5.2-NVFP4/glm52_vllm_nvfp4_dsa_moe.md) (`GLM-5.2-NVFP4/glm52_vllm_nvfp4_dsa_moe`)
- [GLM-5.2 NVFP4: vLLM, TP and EP, MTP speculative decoding](https://servingstudio.cs.washington.edu/models/GLM-5.2-NVFP4/glm52_vllm_nvfp4_dsa_moe_speculative.md) (`GLM-5.2-NVFP4/glm52_vllm_nvfp4_dsa_moe_speculative`)
- [GLM-5.2 NVFP4: vLLM, PP](https://servingstudio.cs.washington.edu/models/GLM-5.2-NVFP4/glm52_vllm_nvfp4_pp_dsa_moe.md) (`GLM-5.2-NVFP4/glm52_vllm_nvfp4_pp_dsa_moe`)
- [GLM-5.2: vLLM, DP attention, EP](https://servingstudio.cs.washington.edu/models/GLM-5.2/glm52_vllm_dsa_moe.md) (`GLM-5.2/glm52_vllm_dsa_moe`)
- [GLM-5.3-Flash NVFP4: vLLM, DP attention, EP MoE](https://servingstudio.cs.washington.edu/models/GLM-5.3-Flash-NVFP4/glm53_flash_vllm_nvfp4_dp_attn_ep_moe.md) (`GLM-5.3-Flash-NVFP4/glm53_flash_vllm_nvfp4_dp_attn_ep_moe`)
- [GLM-5.3-Flash NVFP4: vLLM, TP attention, EP or TP MoE](https://servingstudio.cs.washington.edu/models/GLM-5.3-Flash-NVFP4/glm53_flash_vllm_nvfp4_kda_dsa_moe.md) (`GLM-5.3-Flash-NVFP4/glm53_flash_vllm_nvfp4_kda_dsa_moe`)
- [GLM-5.3-Flash NVFP4: vLLM, PP](https://servingstudio.cs.washington.edu/models/GLM-5.3-Flash-NVFP4/glm53_flash_vllm_nvfp4_pp_kda_dsa_moe.md) (`GLM-5.3-Flash-NVFP4/glm53_flash_vllm_nvfp4_pp_kda_dsa_moe`)
- [GLM-5.3-Flash: vLLM, DP attention, EP MoE](https://servingstudio.cs.washington.edu/models/GLM-5.3-Flash/glm53_flash_vllm_fp8_dp_attn_ep_moe.md) (`GLM-5.3-Flash/glm53_flash_vllm_fp8_dp_attn_ep_moe`)
- [GLM-5.3-Flash: vLLM, TP attention, EP or TP MoE](https://servingstudio.cs.washington.edu/models/GLM-5.3-Flash/glm53_flash_vllm_fp8_kda_dsa_moe.md) (`GLM-5.3-Flash/glm53_flash_vllm_fp8_kda_dsa_moe`)
- [GLM-5.3-Flash: vLLM, PP](https://servingstudio.cs.washington.edu/models/GLM-5.3-Flash/glm53_flash_vllm_fp8_pp_kda_dsa_moe.md) (`GLM-5.3-Flash/glm53_flash_vllm_fp8_pp_kda_dsa_moe`)
- [GLM-5.3 NVFP4: vLLM, TP and EP, DFlash speculative decoding](https://servingstudio.cs.washington.edu/models/GLM-5.3-NVFP4/glm53_vllm_nvfp4_dsa_moe_dflash2.md) (`GLM-5.3-NVFP4/glm53_vllm_nvfp4_dsa_moe_dflash2`)

## API

- This kind: https://servingstudio.cs.washington.edu/api/public/v1/kernels/dsa_topk_prefill
- Measured rows: https://servingstudio.cs.washington.edu/api/public/v1/kernels/dsa_topk_prefill/rows (filter by any column, such as `?gpu=NVIDIA%20H200`; `format=csv` for CSV)
- Configs the public deployments ask of it: https://servingstudio.cs.washington.edu/api/public/v1/kernels/dsa_topk_prefill/configs

## Torch reference

What the kind computes, as Torch code (`profiling/runners/attention/dsa_topk_prefill_reference.py` in ServingStudio Sim):

```python
"""Torch semantics for DSA prefill top-k index selection."""

from __future__ import annotations

import torch


def dsa_topk_prefill_reference(
    logits: torch.Tensor,
    row_starts: torch.Tensor,
    row_ends: torch.Tensor,
    out: torch.Tensor,
    *,
    top_k: int,
) -> torch.Tensor:
    """Select per-row span-local indices into caller-owned output storage.

    For spans no longer than ``top_k``, the natural local indices are returned
    and unused slots are ``-1``. Longer spans use value-descending order with
    local-index ascending as the deterministic tie-break. Production CUDA does
    not contractually order selected indices or resolve equal-value ties, so a
    later backend compares selected sets and values for those longer spans.

    Source boundary: vLLM v0.23.0 commit
    0fc695fc6d1d82e9a5ac6835ac8e4e1c83703665,
    ``top_k_per_row_prefill`` in ``csrc/libtorch_stable/sampler.cu`` and the
    sparse indexer. GLM-5.2 config revision
    b4734de4facf877f85769a911abafc5283eab3d9 sets ``index_topk=2048``.
    This function defines mathematical and valid-output semantics only; later
    profiling backends construct padded logits and time the production launch.
    """
    _validate(logits, row_starts, row_ends, out, top_k=top_k)

    out.fill_(-1)
    for row in range(logits.shape[0]):
        start = int(row_starts[row].item())
        end = int(row_ends[row].item())
        span_length = end - start
        if span_length == 0:
            continue

        if span_length <= top_k:
            selected = torch.arange(
                span_length,
                dtype=torch.int32,
                device=logits.device,
            )
        else:
            # Stable sorting preserves the original ascending local-index order
            # among equal values, providing the reference's explicit tie-break.
            selected = torch.argsort(
                logits[row, start:end],
                descending=True,
                stable=True,
            )[:top_k].to(torch.int32)
        out[row, : selected.numel()].copy_(selected)

    return out


def _validate(
    logits: object,
    row_starts: object,
    row_ends: object,
    out: object,
    *,
    top_k: object,
) -> None:
    tensors = {
        "logits": logits,
        "row_starts": row_starts,
        "row_ends": row_ends,
        "out": out,
    }
    for name, tensor in tensors.items():
        if not isinstance(tensor, torch.Tensor):
            raise TypeError(f"{name} must be a torch.Tensor")

    assert isinstance(logits, torch.Tensor)
    assert isinstance(row_starts, torch.Tensor)
    assert isinstance(row_ends, torch.Tensor)
    assert isinstance(out, torch.Tensor)

    if type(top_k) is not int:
        raise TypeError("top_k must be a Python int")
    if top_k <= 0:
        raise ValueError("top_k must be positive")

    _validate_ranks_and_shapes(logits, row_starts, row_ends, out, top_k)
    _validate_dtypes_and_devices(logits, row_starts, row_ends, out)
    _validate_layouts(logits, row_starts, row_ends, out)

    for name, tensor in (
        ("logits", logits),
        ("row_starts", row_starts),
        ("row_ends", row_ends),
    ):
        if torch._C._overlaps(out, tensor):
            raise ValueError(f"out must not alias {name}")

    if not bool(torch.isfinite(logits).all().item()):
        raise ValueError("logits must contain only finite values")

    num_keys = logits.shape[1]
    if bool(torch.any(row_starts < 0).item()):
        raise ValueError("row_starts must be nonnegative")
    if bool(torch.any(row_starts > row_ends).item()):
        raise ValueError("each row start must be less than or equal to its end")
    if bool(torch.any(row_ends > num_keys).item()):
        raise ValueError(f"row_ends must not exceed the logits width {num_keys}")


def _validate_ranks_and_shapes(
    logits: torch.Tensor,
    row_starts: torch.Tensor,
    row_ends: torch.Tensor,
    out: torch.Tensor,
    top_k: int,
) -> None:
    for name, tensor, expected_rank in (
        ("logits", logits, 2),
        ("row_starts", row_starts, 1),
        ("row_ends", row_ends, 1),
        ("out", out, 2),
    ):
        if tensor.ndim != expected_rank:
            raise ValueError(f"{name} must be rank {expected_rank}, got rank {tensor.ndim}")
        if any(dimension <= 0 for dimension in tensor.shape):
            raise ValueError(f"{name} dimensions must be positive, got {tuple(tensor.shape)}")

    num_rows = logits.shape[0]
    if row_starts.shape != (num_rows,):
        raise ValueError(f"row_starts shape must be ({num_rows},), got {tuple(row_starts.shape)}")
    if row_ends.shape != (num_rows,):
        raise ValueError(f"row_ends shape must be ({num_rows},), got {tuple(row_ends.shape)}")
    expected_out_shape = (num_rows, top_k)
    if out.shape != expected_out_shape:
        raise ValueError(f"out shape must be {expected_out_shape}, got {tuple(out.shape)}")


def _validate_dtypes_and_devices(
    logits: torch.Tensor,
    row_starts: torch.Tensor,
    row_ends: torch.Tensor,
    out: torch.Tensor,
) -> None:
    if logits.dtype is not torch.float32:
        raise TypeError(f"logits dtype must be torch.float32, got {logits.dtype}")
    for name, tensor in (
        ("row_starts", row_starts),
        ("row_ends", row_ends),
        ("out", out),
    ):
        if tensor.dtype is not torch.int32:
            raise TypeError(f"{name} dtype must be torch.int32, got {tensor.dtype}")

    if any(tensor.device.type == "meta" for tensor in (logits, row_starts, row_ends, out)):
        raise ValueError("meta tensors are not supported")
    for name, tensor in (
        ("row_starts", row_starts),
        ("row_ends", row_ends),
        ("out", out),
    ):
        if tensor.device != logits.device:
            raise ValueError(
                f"{name} must be on the same device as logits, "
                f"got {tensor.device} and {logits.device}"
            )


def _validate_layouts(
    logits: torch.Tensor,
    row_starts: torch.Tensor,
    row_ends: torch.Tensor,
    out: torch.Tensor,
) -> None:
    for name, tensor in (
        ("logits", logits),
        ("row_starts", row_starts),
        ("row_ends", row_ends),
        ("out", out),
    ):
        if tensor.layout is not torch.strided:
            raise ValueError(f"{name} must have torch.strided layout")
        # Status 1 is definite overlap. Status 2 means Torch cannot prove the
        # layout either way and must remain accepted for padded logits views.
        if int(torch._debug_has_internal_overlap(tensor)) == 1:
            raise ValueError(f"{name} must not have internal overlap")

    if logits.stride(-1) != 1:
        raise ValueError("logits innermost stride must be 1")
    for name, tensor in (("row_starts", row_starts), ("row_ends", row_ends)):
        if not tensor.is_contiguous():
            raise ValueError(f"{name} must be contiguous")
    if not out.is_contiguous():
        raise ValueError("out must be contiguous")
```

---

This page as Markdown: https://servingstudio.cs.washington.edu/kernels/dsa_topk_prefill.md. A guide to the whole site for AI agents: [llms.txt](https://servingstudio.cs.washington.edu/llms.txt).
