Implement variable-length causal self-attention over a packed batch of sequences. The tensors
Q, K, and V each have shape
T × d, where T is the total number of tokens across all
sequences concatenated end-to-end. The 1D tensor cu_seqlens of shape
S + 1 stores cumulative sequence lengths, so sequence s occupies
rows [cu_seqlens[s], cu_seqlens[s+1]).
For each token at packed position t belonging to sequence s with
in-sequence position p = t − cu_seqlens[s], attention is restricted to
tokens of the same sequence at positions 0, 1, …, p (causal). Concretely:
\[ \text{scores}[t, u] = \begin{cases} \dfrac{Q[t] \cdot K[u]}{\sqrt{d}} & \text{if } u \text{ is in the same sequence as } t \text{ and } u \text{ is at or before } t, \\[4pt] -\infty & \text{otherwise.} \end{cases} \] \[ \text{output}[t] = \sum_{u} \text{softmax}(\text{scores}[t])[u] \cdot V[u]. \]
This is the packed-sequence attention kernel used by inference engines such as vLLM and
FlashAttention’s varlen path. By packing variable-length sequences into a
single tensor and indexing through cu_seqlens, a serving stack avoids padding
waste and amortizes kernel launch overhead across requests with very different lengths.
solve function; do not change its signature.output.
Example 1 — with T = 3, d = 4, S = 2 and
cu_seqlens = [0, 2, 3] (sequences of lengths 2 and 1):
\[ Q = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \end{bmatrix}, \quad K = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix}, \quad V = \begin{bmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \end{bmatrix} \]
Scaled scores \(QK^\top / \sqrt{4}\) followed by the block-diagonal causal mask leave the allowed (sequence, position) pairs only: \[ \text{masked scores} = \begin{bmatrix} 0.5 & -\infty & -\infty \\ 0 & 0.5 & -\infty \\ -\infty & -\infty & 0.5 \end{bmatrix} \] After per-row softmax and multiplication by \(V\): \[ \text{output} \approx \begin{bmatrix} 1.0000 & 2.0000 & 3.0000 & 4.0000 \\ 3.4898 & 4.4898 & 5.4898 & 6.4898 \\ 9.0000 & 10.0000 & 11.0000 & 12.0000 \end{bmatrix} \]
S ≤ 256T ≤ 16,384 (total packed tokens)d ≤ 256cu_seqlens is monotonically non-decreasing with
cu_seqlens[0] = 0 and cu_seqlens[S] = T.Q, K, V, output are float32;
cu_seqlens is int32.T = 8,192, d = 64,
S = 32 (sequence lengths between 128 and 384).