Python / PyTorch 工业标准参考实现答案 (含测试验证与边界断言)
import torch
import math
def paged_attention_lookup(
Q: torch.Tensor,
K_cache: torch.Tensor,
V_cache: torch.Tensor,
block_tables: torch.Tensor,
context_lens: torch.Tensor,
block_size: int = 16
) -> torch.Tensor:
"""
Simulates vLLM PagedAttention decoding step for single query tokens.
Args:
Q: (num_seqs, num_heads, head_dim)
K_cache, V_cache: (num_blocks, num_heads, block_size, head_dim)
block_tables: (num_seqs, max_blocks_per_seq) - maps logical block index to physical block index
context_lens: (num_seqs,) - current context length of each sequence
"""
num_seqs, num_heads, head_dim = Q.shape
scale = 1.0 / math.sqrt(head_dim)
outputs = torch.zeros_like(Q)
for seq_idx in range(num_seqs):
ctx_len = context_lens[seq_idx].item()
if ctx_len == 0:
continue
num_needed_blocks = math.ceil(ctx_len / block_size)
physical_block_ids = block_tables[seq_idx, :num_needed_blocks]
# Gather physical blocks for this sequence: (num_blocks, num_heads, block_size, head_dim)
k_blocks = K_cache[physical_block_ids]
v_blocks = V_cache[physical_block_ids]
# Permute and flatten to continuous sequence: (num_heads, total_tokens, head_dim)
# Transpose from (num_blocks, H, B_size, D) -> (H, num_blocks * B_size, D)
K_seq = k_blocks.permute(1, 0, 2, 3).reshape(num_heads, -1, head_dim)[:, :ctx_len, :]
V_seq = v_blocks.permute(1, 0, 2, 3).reshape(num_heads, -1, head_dim)[:, :ctx_len, :]
# Compute single token attention for this sequence:
# q_curr: (num_heads, 1, head_dim)
q_curr = Q[seq_idx].unsqueeze(1)
scores = torch.bmm(q_curr, K_seq.transpose(1, 2)) * scale # (num_heads, 1, ctx_len)
attn_probs = torch.softmax(scores, dim=-1)
out = torch.bmm(attn_probs, V_seq) # (num_heads, 1, head_dim)
outputs[seq_idx] = out.squeeze(1)
return outputs
# --- Verification & Test Case ---
if __name__ == "__main__":
num_blocks, num_heads, block_size, head_dim = 16, 4, 8, 32
num_seqs = 2
K_cache = torch.randn(num_blocks, num_heads, block_size, head_dim)
V_cache = torch.randn(num_blocks, num_heads, block_size, head_dim)
# Block table: seq 0 uses physical blocks [3, 7]; seq 1 uses [1, 5, 9]
block_tables = torch.tensor([[3, 7, 0], [1, 5, 9]])
context_lens = torch.tensor([12, 20])
Q = torch.randn(num_seqs, num_heads, head_dim)
res = paged_attention_lookup(Q, K_cache, V_cache, block_tables, context_lens, block_size)
assert res.shape == (num_seqs, num_heads, head_dim)
print("PagedAttention block table gather verified successfully!")