| 1 | # SPDX-License-Identifier: Apache-2.0 |
| 2 | # SPDX-FileCopyrightText: Copyright contributors to the vLLM project |
| 3 | |
| 4 | from dataclasses import dataclass |
| 5 | |
| 6 | import numpy as np |
| 7 | import pytest |
| 8 | |
| 9 | from vllm.v1.attention.backends.utils import reorder_batch_to_split_decodes_and_prefills |
| 10 | |
| 11 | |
| 12 | class MockInputBatch: |
| 13 | def __init__(self, req_ids, num_computed_tokens_cpu, num_prompt_tokens): |
| 14 | self.req_ids = req_ids |
| 15 | self.num_computed_tokens_cpu = num_computed_tokens_cpu |
| 16 | self.num_prompt_tokens = num_prompt_tokens |
| 17 | |
| 18 | def swap_states(self, i, j): |
| 19 | self.req_ids[i], self.req_ids[j] = self.req_ids[j], self.req_ids[i] |
| 20 | self.num_computed_tokens_cpu[i], self.num_computed_tokens_cpu[j] = ( |
| 21 | self.num_computed_tokens_cpu[j], |
| 22 | self.num_computed_tokens_cpu[i], |
| 23 | ) |
| 24 | self.num_prompt_tokens[i], self.num_prompt_tokens[j] = ( |
| 25 | self.num_prompt_tokens[j], |
| 26 | self.num_prompt_tokens[i], |
| 27 | ) |
| 28 | |
| 29 | |
| 30 | class MockSchedulerOutput: |
| 31 | def __init__(self, num_scheduled_tokens): |
| 32 | self.num_scheduled_tokens = num_scheduled_tokens |
| 33 | |
| 34 | |
| 35 | @dataclass |
| 36 | class ReorderTestCase: |
| 37 | # (num_scheduled_tokens, num_computed_tokens, num_prompt_tokens) |
| 38 | requests: list[tuple[int, int, int]] |
| 39 | expected_order: list[int] |
| 40 | expected_modified: bool |
| 41 | decode_threshold: int = 1 |
| 42 | |
| 43 | |
| 44 | # Test cases for batch reordering |
| 45 | # Format: (num_scheduled, num_computed, num_prompt) |
| 46 | REORDER_TEST_CASES = { |
| 47 | "all_decodes": ReorderTestCase( |
| 48 | requests=[(1, 10, 10), (1, 20, 20), (1, 30, 30)], |
| 49 | expected_order=[0, 1, 2], |
| 50 | expected_modified=False, |
| 51 | ), |
| 52 | "all_long_extends": ReorderTestCase( |
| 53 | requests=[(100, 100, 100), (200, 200, 200), (300, 300, 300)], |
| 54 | expected_order=[0, 1, 2], |
| 55 | expected_modified=False, |
| 56 | ), |
| 57 | "mixed_decodes_long_extends": ReorderTestCase( |
| 58 | requests=[(100, 100, 100), (1, 10, 10), (200, 200, 200), (1, 20, 20)], |
| 59 | expected_order=[3, 1, 2, 0], |
| 60 | expected_modified=True, |
| 61 | ), |
| 62 | "already_ordered": ReorderTestCase( |
| 63 | requests=[(1, 10, 10), (1, 20, 20), (100, 100, 100), (200, 0, 200)], |
| 64 | expected_order=[0, 1, 2, 3], |
| 65 | expected_modified=False, |
| 66 | ), |
| 67 | "single_request": ReorderTestCase( |
| 68 | requests=[(1, 10, 10)], |
| 69 | expected_order=[0], |
| 70 | expected_modified=False, |
| 71 | ), |
| 72 | "higher_threshold": ReorderTestCase( |
| 73 | requests=[(2, 10, 10), (3, 20, 20), (5, 30, 30), (6, 40, 40)], |
| 74 | expected_order=[0, 1, 2, 3], |
| 75 | expected_modified=False, |
| 76 | decode_threshold=4, |
| 77 | ), |
| 78 | "decodes_at_end": ReorderTestCase( |
| 79 | requests=[(100, 100, 100), (200, 200, 200), (1, 10, 10), (1, 20, 20)], |
| 80 | expected_order=[2, 3, 0, 1], |
| 81 | expected_modified=True, |
| 82 | ), |
| 83 | "decode_long_extend_prefill": ReorderTestCase( |
| 84 | requests=[(100, 0, 100), (10, 50, 50), (1, 10, 10)], |
| 85 | expected_order=[2, 1, 0], |
| 86 | expected_modified=True, |
| 87 | ), |
| 88 | "long_extend_prefill_only": ReorderTestCase( |
| 89 | requests=[(100, 0, 100), (10, 50, 50), (200, 0, 200), (20, 75, 75)], |
| 90 | expected_order=[3, 1, 2, 0], |
| 91 | expected_modified=True, |
| 92 | ), |
| 93 | "complicated_mixed": ReorderTestCase( |
| 94 | requests=[ |
| 95 | (1, 20, 20), # decode |
| 96 | (1, 50, 50), # decode |
| 97 | (374, 0, 374), # prefill |
| 98 | (300, 20, 20), # long_extend |
| 99 | (1, 20, 20), # decode |
| 100 | (256, 0, 256), # prefill |
| 101 | (1, 5, 5), # decode |
| 102 | (27, 0, 27), # prefill |
| 103 | (1, 4, 4), # decode |
| 104 | ], |
| 105 | expected_order=[0, 1, 6, 8, 4, 3, 2, 7, 5], |
| 106 | expected_modified=True, |
| 107 | ), |
| 108 | "new_request_single_token_prefill": ReorderTestCase( |
| 109 | requests=[ |
| 110 | (100, 0, 100), # prefill |
| 111 | (1, 0, 1), # prefill (single token, still prefill) |
| 112 | (50, 100, 100), # long_extend |
| 113 | (1, 10, 10), # decode |
| 114 | ], |
| 115 | expected_order=[3, 2, 0, 1], |
| 116 | expected_modified=True, |
| 117 | ), |
| 118 | "multiple_new_requests_single_token_prefill": ReorderTestCase( |
| 119 | requests=[ |
| 120 | (1, 0, 1), # prefill |
| 121 | (1, 0, 1), # prefill |
| 122 | (1, 50, 50), # decode |
| 123 | (200, 0, 200), # prefill |
| 124 | ], |
| 125 | expected_order=[2, 1, 0, 3], |
| 126 | expected_modified=True, |
| 127 | ), |
| 128 | "four_way_already_ordered": ReorderTestCase( |
| 129 | requests=[ |
| 130 | (1, 100, 100), # decode |
| 131 | (1, 50, 100), # short_extend |
| 132 | (10, 50, 100), # long_extend |
| 133 | (100, 0, 100), # prefill |
| 134 | ], |
| 135 | expected_order=[0, 1, 2, 3], |
| 136 | expected_modified=False, |
| 137 | ), |
| 138 | "four_way_needs_reorder": ReorderTestCase( |
| 139 | requests=[ |
| 140 | (100, 0, 100), # prefill |
| 141 | (1, 50, 100), # short_extend |
| 142 | (1, 100, 100), # decode |
| 143 | (10, 50, 100), # long_extend |
| 144 | ], |
| 145 | expected_order=[2, 1, 3, 0], |
| 146 | expected_modified=True, |
| 147 | ), |
| 148 | "four_way_multiple_short_extends": ReorderTestCase( |
| 149 | requests=[ |
| 150 | (2, 100, 100), # decode |
| 151 | (2, 50, 200), # short_extend |
| 152 | (2, 75, 150), # short_extend |
| 153 | (2, 200, 200), # decode |
| 154 | ], |
| 155 | expected_order=[0, 3, 2, 1], |
| 156 | expected_modified=True, |
| 157 | decode_threshold=2, |
| 158 | ), |
| 159 | "four_way_spec_decode_threshold": ReorderTestCase( |
| 160 | requests=[ |
| 161 | (5, 100, 100), # decode |
| 162 | (5, 50, 100), # short_extend |
| 163 | (5, 0, 100), # prefill |
| 164 | (10, 50, 100), # long_extend |
| 165 | ], |
| 166 | expected_order=[0, 1, 3, 2], |
| 167 | expected_modified=True, |
| 168 | decode_threshold=5, |
| 169 | ), |
| 170 | } |
| 171 | |
| 172 | |
| 173 | @pytest.mark.parametrize( |
| 174 | "test_case", REORDER_TEST_CASES.values(), ids=REORDER_TEST_CASES.keys() |
| 175 | ) |
| 176 | def test_reorder_batch_to_split_decodes_and_prefills(test_case: ReorderTestCase): |
| 177 | req_ids = [f"r{i}" for i in range(len(test_case.requests))] |
| 178 | num_computed_tokens = np.array([r[1] for r in test_case.requests], dtype=np.int32) |
| 179 | num_scheduled_tokens = {f"r{i}": r[0] for i, r in enumerate(test_case.requests)} |
| 180 | num_prompt_tokens = np.array([r[2] for r in test_case.requests], dtype=np.int32) |
| 181 | |
| 182 | input_batch = MockInputBatch(req_ids, num_computed_tokens, num_prompt_tokens) |
| 183 | scheduler_output = MockSchedulerOutput(num_scheduled_tokens) |
| 184 | |
| 185 | modified = reorder_batch_to_split_decodes_and_prefills( |
| 186 | input_batch, scheduler_output, decode_threshold=test_case.decode_threshold |
| 187 | ) |
| 188 | |
| 189 | expected_req_ids = [f"r{i}" for i in test_case.expected_order] |
| 190 | |
| 191 | assert modified == test_case.expected_modified, ( |
| 192 | f"Expected modified={test_case.expected_modified}, got {modified}" |
| 193 | ) |
| 194 | assert input_batch.req_ids == expected_req_ids, ( |
| 195 | f"Expected order {expected_req_ids}, got {input_batch.req_ids}" |
| 196 | ) |