# Paged batch prefill attention (`paged_attn_batch_prefill`) | ServingStudio Kernel Library

Causal GQA attention of several requests' new tokens over their cached prefixes and themselves, through a paged KV cache, in one call.

One call covers every prefill request of a step, whether a fresh prompt, a chunk of a long prompt or a prompt after a prefix-cache hit. Each request's new tokens attend causally to its cached prefix and to each other.

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

## Formula

- `O[t, h] = softmax(Q[t, h] · K[:p_t, h // G]ᵀ · scale) · V[:p_t, h // G]`
- `p_t = keys token t sees: its request's prefix plus its position + 1`
- `TFLOPS = 4 · num_qo_heads · head_dim · Σ p_t / time`
- `GB/s = (Q + O + every request's K and V once) bytes / time`

## How it is measured

GPU kernel time from CUPTI activity records, averaged over repeated launches in one capture. The L2 cache is flushed before each launch, so the numbers are cold-cache times. Every launch of the call counts. Before timing, the output is checked against a PyTorch reference on sampled query rows.

## Caveats

- Queries, keys and values are random; the quantization scales are 1.
- Pages hold 32 tokens: 16, 32 and 64 measured within 1%, so the page size is not part of the key.
- The kernel tiles each request's new tokens by 128 and a partial tile costs a full one, so many short requests cost more than one long request with the same query-key pairs.

## Arguments

| Argument | Type | Unit | Meaning |
| --- | --- | --- | --- |
| `num_qo_heads` | number | heads | Query and output heads on this GPU. |
| `num_kv_heads` | number | heads | KV heads on this GPU. |
| `head_dim` | number | elements | Dimension of each query, key and value head. |
| `q_dtype` | dtype |  | Query element type. |
| `kv_dtype` | dtype |  | Key and value cache element type. |
| `o_dtype` | dtype |  | Output element type. |
| `requests` | list |  | (cached prefix tokens, new tokens) per prefill request in the call. |

## Metrics

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

## Backends

- `flashinfer_trtllm_gen`: FlashInfer's trtllm_batch_context_with_kv_cache as vLLM's FlashInferImpl.forward calls it for the prefill requests. dtypes `fp8_e4m3`, KV dtypes `fp8_e4m3`, SM targets `sm_100f`, GPUs B200-SXM-180GB, B300-SXM-288GB, GB200-Superchip.

## Measured rows

1,080 rows in all.

| GPU | Backend | Precision | Rows |
| --- | --- | --- | --- |
| NVIDIA B200 | `flashinfer_trtllm_gen` | `fp8_e4m3` | 1,080 |

## Used by these deployments

- [Qwen3.8 27B NVFP4: vLLM, one GPU](https://servingstudio.cs.washington.edu/models/Qwen3.8-27B-NVFP4/qwen35_vllm_nvfp4_gdn_dense.md) (`Qwen3.8-27B-NVFP4/qwen35_vllm_nvfp4_gdn_dense`)

## API

- This kind: https://servingstudio.cs.washington.edu/api/public/v1/kernels/paged_attn_batch_prefill
- Measured rows: https://servingstudio.cs.washington.edu/api/public/v1/kernels/paged_attn_batch_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/paged_attn_batch_prefill/configs

## Torch reference

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

```python
"""PyTorch reference for FA4 varlen attention with sinks and a separate V dim.

Independent of FlashAttention: it reads keys and values through the page table
and applies the definition directly. For a query at absolute position ``p`` in
its request and query head ``h`` (KV head ``h // G``):

    s[h, j] = (q[h] . k[j, h // G]) * softmax_scale       for visible keys j
    visible: j <= p, and p - j < window when the layer is windowed
    P = softmax([s[h, visible], sink[h]])                 (sink only if present)
    o[h] = sum_j P[j] * v[j, h // G]                      (the sink adds no value)

The sink is a per-head logit that joins the denominator unscaled, as FA4's
``s_aux`` / ``learnable_sink`` does. Everything runs in float32 on whatever
device the inputs live on.
"""

from __future__ import annotations

from typing import Any


def gather_request_kv(key_cache: Any, value_cache: Any, block_row: Any, context: int) -> tuple:
    """Keys ``[context, kv_heads, head_dim_qk]`` and values ``[context, kv_heads, head_dim_v]``.

    ``key_cache`` / ``value_cache`` are ``[num_pages, page_size, kv_heads, dim]``
    views (any strides); ``block_row`` maps a request page index to a physical page.
    """
    import torch

    page_size = key_cache.shape[1]
    tokens = torch.arange(context, device=key_cache.device)
    pages = block_row.to(key_cache.device).long()[tokens // page_size]
    offsets = tokens % page_size
    return key_cache[pages, offsets].float(), value_cache[pages, offsets].float()


def varlen_attention_reference(
    q: Any,
    positions: Any,
    keys: Any,
    values: Any,
    *,
    softmax_scale: float,
    window: int,
    sinks: Any = None,
) -> Any:
    """Attention output ``[rows, heads, head_dim_v]`` (float32) for one request.

    ``q`` is ``[rows, heads, head_dim_qk]`` at absolute ``positions`` ``[rows]``;
    ``keys`` / ``values`` hold the request's first ``context`` tokens;
    ``window`` is the number of keys a query sees including itself (0 = all
    earlier keys); ``sinks`` is ``[heads]`` or None.
    """
    import torch

    rows, heads, _ = q.shape
    group = heads // keys.shape[1]
    k = keys.float().repeat_interleave(group, dim=1)  # [S, H, Dqk]
    v = values.float().repeat_interleave(group, dim=1)  # [S, H, Dv]
    scores = torch.einsum("thd,shd->hts", q.float(), k) * softmax_scale
    distance = positions.long()[:, None] - torch.arange(keys.shape[0], device=q.device)[None, :]
    visible = distance >= 0
    if window > 0:
        visible &= distance < window
    scores = scores.masked_fill(~visible[None], float("-inf"))
    if sinks is not None:
        sink = sinks.float().to(q.device)[:, None, None].expand(heads, rows, 1)
        scores = torch.cat([scores, sink], dim=-1)
    probs = torch.softmax(scores, dim=-1)[..., : keys.shape[0]]
    return torch.einsum("hts,shd->thd", probs, v)
```

---

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