| 1 | # SPDX-License-Identifier: Apache-2.0 |
| 2 | # SPDX-FileCopyrightText: Copyright contributors to the vLLM project |
| 3 | from dataclasses import dataclass |
| 4 | |
| 5 | import numpy as np |
| 6 | import pytest |
| 7 | import torch |
| 8 | |
| 9 | from tests.v1.attention.utils import BatchSpec, create_common_attn_metadata |
| 10 | from vllm.platforms import current_platform |
| 11 | from vllm.v1.attention.backends.utils import make_local_attention_virtual_batches |
| 12 | |
| 13 | |
| 14 | @dataclass |
| 15 | class LocalAttentionTestData: |
| 16 | # Input parameters |
| 17 | batch_spec: BatchSpec |
| 18 | attn_chunk_size: int |
| 19 | block_size: int |
| 20 | # Expected return values |
| 21 | expected_q_seqlens: list[int] |
| 22 | expected_k_seqlens: list[int] |
| 23 | expected_local_block_table: list[list[int]] |
| 24 | |
| 25 | |
| 26 | DEVICE_TYPE = current_platform.device_type |
| 27 | |
| 28 | test_data_list = [ |
| 29 | # Same as example in docstring of make_local_attention_virtual_batches |
| 30 | # except block table has 9 columns instead of 10 |
| 31 | LocalAttentionTestData( |
| 32 | batch_spec=BatchSpec( |
| 33 | query_lens=[4, 10, 5], |
| 34 | seq_lens=[6, 17, 9], |
| 35 | ), |
| 36 | attn_chunk_size=4, |
| 37 | block_size=2, |
| 38 | expected_q_seqlens=[2, 2, 1, 4, 4, 1, 4, 1], |
| 39 | expected_k_seqlens=[4, 2, 4, 4, 4, 1, 4, 1], |
| 40 | # 2 pages per local branch |
| 41 | # (chunk size 4 // block size 2) |
| 42 | expected_local_block_table=[ |
| 43 | [0, 1], # local-batch 0, (batch 0, starting from k[0]) |
| 44 | [2, 3], # local-batch 1, (batch 0, starting from k[4]) |
| 45 | [11, 12], # local-batch 2, (batch 1, starting from k[4]) |
| 46 | [13, 14], # local-batch 3, (batch 1, starting from k[8]) |
| 47 | [15, 16], # local-batch 4, (batch 1, starting from k[12]) |
| 48 | [17, 17], # local-batch 5, (batch 1, starting from k[16]) |
| 49 | [20, 21], # local-batch 6, (batch 2, starting from k[4]) |
| 50 | [22, 23], # local-batch 7, (batch 2, starting from k[8]) |
| 51 | ], |
| 52 | ), |
| 53 | # Case where block indices are not clipped to block table ncols-1 |
| 54 | # because tokens_in_last_block == attn_chunk_size |
| 55 | LocalAttentionTestData( |
| 56 | batch_spec=BatchSpec( |
| 57 | query_lens=[8], |
| 58 | seq_lens=[12], |
| 59 | ), |
| 60 | attn_chunk_size=4, |
| 61 | block_size=2, |
| 62 | expected_q_seqlens=[4, 4], |
| 63 | expected_k_seqlens=[4, 4], |
| 64 | expected_local_block_table=[ |
| 65 | [2, 3], |
| 66 | [4, 5], |
| 67 | ], |
| 68 | ), |
| 69 | # Case where all kv_seq positions are involved in attn |
| 70 | LocalAttentionTestData( |
| 71 | batch_spec=BatchSpec( |
| 72 | query_lens=[7], |
| 73 | # 10 - 7 = 3 previously computed tokens |
| 74 | seq_lens=[10], |
| 75 | ), |
| 76 | attn_chunk_size=4, |
| 77 | block_size=2, |
| 78 | expected_q_seqlens=[1, 4, 2], |
| 79 | expected_k_seqlens=[4, 4, 2], |
| 80 | expected_local_block_table=[ |
| 81 | [0, 1], |
| 82 | [2, 3], |
| 83 | [4, 4], |
| 84 | ], |
| 85 | ), |
| 86 | # Case where attn_chunk_size > kv_seq_len |
| 87 | # so no extra mini virtual batches are created |
| 88 | LocalAttentionTestData( |
| 89 | batch_spec=BatchSpec( |
| 90 | query_lens=[4], |
| 91 | seq_lens=[6], |
| 92 | ), |
| 93 | # Larger than kv_seq_len |
| 94 | attn_chunk_size=10, |
| 95 | block_size=2, |
| 96 | # No change to q_seqlens and k_seqlens |
| 97 | expected_q_seqlens=[4], |
| 98 | expected_k_seqlens=[6], |
| 99 | # In this case, we only need a block-table like: |
| 100 | # block_table = [ [0, 1, 2] ] # 1 batch, 3 pages |
| 101 | # But we need to pad it to 5 pages per local batch |
| 102 | # because currently the pages_per_local_batch |
| 103 | # is calculated as (attn_chunk_size // block_size) |
| 104 | expected_local_block_table=[ |
| 105 | [0, 1, 2, 2, 2], |
| 106 | ], |
| 107 | ), |
| 108 | # Block size equal to chunk size |
| 109 | # Expect single page per batch in local batch table |
| 110 | LocalAttentionTestData( |
| 111 | batch_spec=BatchSpec( |
| 112 | query_lens=[6, 6], |
| 113 | seq_lens=[8, 8], |
| 114 | ), |
| 115 | attn_chunk_size=4, |
| 116 | block_size=4, |
| 117 | expected_q_seqlens=[2, 4, 2, 4], |
| 118 | expected_k_seqlens=[4, 4, 4, 4], |
| 119 | # Initial block table = [ |
| 120 | # [0, 1], < batch 0 |
| 121 | # [2, 3], < batch 1 |
| 122 | # ] |
| 123 | expected_local_block_table=[ |
| 124 | [0], # local-batch 0, (batch 0, starting from k[0]) |
| 125 | [1], # local-batch 1, (batch 0, starting from k[4]) |
| 126 | [2], # local-batch 1, (batch 0, starting from k[0]) |
| 127 | [3], # local-batch 1, (batch 0, starting from k[4]) |
| 128 | ], |
| 129 | ), |
| 130 | # Case where query falls in the second attention chunk |
| 131 | # k_toks > 0 1 2 3 4 |
| 132 | # q_toks v _____________ |
| 133 | # 0 | 1 |
| 134 | # 1 | 1 1 |
| 135 | # 2 | 1 1 1 |
| 136 | # 3 | 1 1 1 1 |
| 137 | # 4 | 1 |
| 138 | # where tokens 0,1,2,3 have been pre-computed |
| 139 | LocalAttentionTestData( |
| 140 | batch_spec=BatchSpec( |
| 141 | query_lens=[1], |
| 142 | seq_lens=[5], |
| 143 | ), |
| 144 | attn_chunk_size=4, |
| 145 | block_size=2, |
| 146 | expected_q_seqlens=[1], |
| 147 | expected_k_seqlens=[1], |
| 148 | expected_local_block_table=[ |
| 149 | [2, 2], |
| 150 | ], |
| 151 | ), |
| 152 | ] |
| 153 | |
| 154 | |
| 155 | @pytest.mark.parametrize("test_data", test_data_list) |
| 156 | def test_local_attention_virtual_batches(test_data: LocalAttentionTestData): |
| 157 | device = torch.device(f"{DEVICE_TYPE}:0") |
| 158 | batch_spec = test_data.batch_spec |
| 159 | attn_chunk_size = test_data.attn_chunk_size |
| 160 | block_size = test_data.block_size |
| 161 | expected_q_seqlens = test_data.expected_q_seqlens |
| 162 | expected_k_seqlens = test_data.expected_k_seqlens |
| 163 | expected_local_block_table = test_data.expected_local_block_table |
| 164 | |
| 165 | # Create common attention metadata |
| 166 | common_attn_metadata = create_common_attn_metadata( |
| 167 | batch_spec, |
| 168 | block_size, |
| 169 | device, |
| 170 | # Use torch.arange instead of torch.randint so we can assert on |
| 171 | # block table tensor values. The block table will have shape |
| 172 | # (num_batches, cdiv(max_seq_len, block_size)) and the values will be |
| 173 | # arranged from 0 to cdiv(max_seq_len, block_size)-1 |
| 174 | arange_block_indices=True, |
| 175 | ) |
| 176 | |
| 177 | # Call the function |
| 178 | result, _ = make_local_attention_virtual_batches( |
| 179 | attn_chunk_size, common_attn_metadata, block_size |
| 180 | ) |
| 181 | |
| 182 | # Convert to numpy for easier comparison |
| 183 | actual_q_seqlens = np.diff(result.query_start_loc_cpu.numpy()) |
| 184 | assert result.seq_lens_cpu_upper_bound is not None |
| 185 | actual_k_seqlens = result.seq_lens_cpu_upper_bound.numpy() |
| 186 | |
| 187 | # Check that all query lengths are less than or equal to attn_chunk_size |
| 188 | assert all(q_len <= attn_chunk_size for q_len in actual_q_seqlens) |
| 189 | # Check that all key lengths are less than or equal to attn_chunk_size |
| 190 | assert all(k_len <= attn_chunk_size for k_len in actual_k_seqlens) |
| 191 | # Check that the total number of query tokens is preserved |
| 192 | assert sum(actual_q_seqlens) == sum(batch_spec.query_lens) |
| 193 | |
| 194 | # Verify results |
| 195 | np.testing.assert_array_equal(actual_q_seqlens, expected_q_seqlens) |
| 196 | np.testing.assert_array_equal(actual_k_seqlens, expected_k_seqlens) |
| 197 | |
| 198 | expected_block_table_tensor = torch.tensor( |
| 199 | expected_local_block_table, dtype=torch.int32, device=device |
| 200 | ) |
| 201 | |
| 202 | print(f"Expected block table:\n{expected_block_table_tensor}") |
| 203 | print(f"Actual block table:\n{result.block_table_tensor}") |
| 204 | |
| 205 | torch.testing.assert_close(result.block_table_tensor, expected_block_table_tensor) |