tpu_model_runner.py 91.5 KB
Newer Older
1
# SPDX-License-Identifier: Apache-2.0
2
# SPDX-FileCopyrightText: Copyright contributors to the vLLM project
3
import bisect
4
import gc
5
import time
6
from typing import TYPE_CHECKING, Any, Optional, cast
7
8
9
10
11
12
from unittest.mock import patch

import numpy as np
import torch
import torch.nn as nn
# TPU XLA related
13
import torch_xla
14
import torch_xla.core.xla_model as xm
15
import torch_xla.distributed.spmd as xs
16
17
import torch_xla.runtime as xr

18
import vllm.envs as envs
19
from vllm.attention import Attention
20
from vllm.attention.backends.abstract import AttentionType
21
from vllm.attention.layers.chunked_local_attention import ChunkedLocalAttention
22
from vllm.compilation.wrapper import TorchCompileWrapperWithCustomDispatcher
23
24
from vllm.config import (ParallelConfig, VllmConfig,
                         get_layers_from_vllm_config, update_config)
25
26
from vllm.distributed.kv_transfer import (get_kv_transfer_group,
                                          has_kv_transfer_group)
27
from vllm.distributed.kv_transfer.kv_connector.utils import copy_kv_blocks
28
from vllm.forward_context import set_forward_context
29
from vllm.logger import init_logger
30
from vllm.lora.layers import BaseLayerWithLoRA
31
from vllm.model_executor.model_loader import get_model_loader
32
from vllm.model_executor.model_loader.tpu import TPUModelLoader
33
34
from vllm.model_executor.models.interfaces import (SupportsMultiModal,
                                                   supports_transcription)
35
36
from vllm.model_executor.models.interfaces_base import (
    is_pooling_model, is_text_generation_model)
37
from vllm.multimodal import MULTIMODAL_REGISTRY
38
from vllm.multimodal.inputs import (BatchedTensorInputs, MultiModalKwargsItem,
39
                                    PlaceholderRange)
40
from vllm.multimodal.utils import group_mm_kwargs_by_modality
41
from vllm.sequence import IntermediateTensors
42
from vllm.tasks import GenerationTask, PoolingTask, SupportedTask
43
44
45
46
from vllm.utils import (LayerBlockType, cdiv, is_pin_memory_available,
                        prev_power_of_2)
from vllm.v1.attention.backends.pallas import (TPU_STR_DTYPE_TO_TORCH_DTYPE,
                                               PallasAttentionBackend,
47
48
                                               PallasMetadata,
                                               get_page_size_bytes)
49
50
51
from vllm.v1.kv_cache_interface import (AttentionSpec, FullAttentionSpec,
                                        KVCacheConfig, KVCacheSpec,
                                        SlidingWindowSpec)
52
53
from vllm.v1.outputs import (EMPTY_MODEL_RUNNER_OUTPUT, LogprobsLists,
                             LogprobsTensors, ModelRunnerOutput)
54
55
from vllm.v1.sample.tpu.metadata import TPUSupportedSamplingMetadata
from vllm.v1.sample.tpu.sampler import Sampler as TPUSampler
56
from vllm.v1.worker.kv_connector_model_runner_mixin import (
57
    KVConnectorModelRunnerMixin, KVConnectorOutput)
58
from vllm.v1.worker.lora_model_runner_mixin import LoRAModelRunnerMixin
59
from vllm.v1.worker.tpu_input_batch import CachedRequestState, InputBatch
60

61
62
from .utils import (MultiModalBudget, add_kv_sharing_layers_to_kv_cache_groups,
                    bind_kv_cache, sanity_check_mm_encoder_outputs)
63

64
if TYPE_CHECKING:
65
    from vllm.v1.core.sched.output import SchedulerOutput
66
67
68

logger = init_logger(__name__)

69
INVALID_TOKEN_ID = -1
70
71
# Smallest output size
MIN_NUM_SEQS = 8
72
73


74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#########################################################
# Ways to avoid recompilation
#########################################################
#
# The model executor has two primary components:
# 1. preparing the model and sampler inputs
# 2. executing the model and sampler.
# The core idea is to avoid any TPU computation during input preparation. For
# better compilation tracking and increased flexibility, the model execution and
# sampler are divided into several distinct components.
#
# Below are the detailed steps:
#
# Step 1
# It is recommended to avoid TPU operations when preparing the model and sampler
# inputs. CPU tensors can be prepared and transferred to the XLA device using
# cpu_tensor.to(xla_device), which only triggers CPU to TPU transfers and avoids
# compilation.
#
# Step 2
# The TPU execution should be decomposed into subgraphs (4 at the moment):
# 1. the main model
# 2. selecting hidden states for each request
# 3. sampler
# 4. encoder.
# Each subgraph should be decorated in a torch.compile. This is used to make
# sure that we have the same subgraph topology in both dummy_run and
# xecute_model. The results from these subgraphs should either be passed to
# other subgraphs, or transferred from TPU to CPU using xla_tensor.cpu() for
# subsequent processing on the CPU.
#
# Step 3
# The dummy_run should be comprehensive, ensuring all potential input shapes and
# branch predictions are included as subgraph inputs to facilitate
# pre-compilation.
109
class TPUModelRunner(LoRAModelRunnerMixin, KVConnectorModelRunnerMixin):
110
111
112
113
114

    def __init__(
        self,
        vllm_config: VllmConfig,
        device: torch.device,
115
        original_parallel_config: Optional[ParallelConfig] = None,
116
117
118
119
120
121
122
    ):
        self.vllm_config = vllm_config
        self.model_config = vllm_config.model_config
        self.cache_config = vllm_config.cache_config
        self.lora_config = vllm_config.lora_config
        self.load_config = vllm_config.load_config
        self.parallel_config = vllm_config.parallel_config
123
        self.original_parallel_config = original_parallel_config
124
125
126
127
128
129
130
131
132
133
        self.scheduler_config = vllm_config.scheduler_config
        self.speculative_config = vllm_config.speculative_config
        self.observability_config = vllm_config.observability_config
        self.device_config = vllm_config.device_config

        model_config = self.model_config
        cache_config = self.cache_config
        scheduler_config = self.scheduler_config
        parallel_config = self.parallel_config
        self.device = device
134
        self.check_recompilation = envs.VLLM_XLA_CHECK_RECOMPILATION
135

136
137
138
139
140
141
142
143
        # SPMD Related
        self.use_spmd = envs.VLLM_XLA_USE_SPMD
        if self.use_spmd:
            num_devices = xr.global_runtime_device_count()
            mesh_shape = (num_devices, 1)
            device_ids = np.array(range(num_devices))
            self.mesh = xs.Mesh(device_ids, mesh_shape, ('x', 'y'))

144
        self.enforce_eager = model_config.enforce_eager
145
146
147
148

        self.num_xla_graphs = 0
        self._update_num_xla_graphs("init")

149
150
        self.pin_memory = is_pin_memory_available()
        self.dtype = self.model_config.dtype
151
        if cache_config.cache_dtype == "auto":
152
153
            model_dtype = self.dtype
            if isinstance(model_dtype, str):
154
                self.kv_cache_dtype = TPU_STR_DTYPE_TO_TORCH_DTYPE[model_dtype]
155
156
            else:
                self.kv_cache_dtype = model_dtype
157
        else:
158
            self.kv_cache_dtype = TPU_STR_DTYPE_TO_TORCH_DTYPE[
159
                cache_config.cache_dtype]
160
        self._hidden_states_dtype = self.dtype
161
162
163
164

        self.sliding_window = model_config.get_sliding_window()
        self.block_size = cache_config.block_size
        self.max_model_len = model_config.max_model_len
165
        self.most_model_len = envs.VLLM_TPU_MOST_MODEL_LEN
166
        self.max_num_blocks_per_req = cdiv(self.max_model_len, self.block_size)
167
168
169
        self.num_blocks_per_most_len_req = cdiv(
            self.most_model_len,
            self.block_size) if self.most_model_len is not None else None
170
171
        # InputBatch needs to work with sampling tensors greater than padding
        # to avoid dynamic shapes. Also, avoid suboptimal alignment.
172
        self.max_num_reqs = max(scheduler_config.max_num_seqs, MIN_NUM_SEQS)
173
174
175
176
177
178
179
        self.num_tokens_paddings = _get_token_paddings(
            min_token_size=16,
            max_token_size=scheduler_config.max_num_batched_tokens,
            padding_gap=envs.VLLM_TPU_BUCKET_PADDING_GAP)
        # In case `max_num_tokens < max(num_tokens_paddings)` use the actual
        # padded max value to pre-allocate data structures and pre-compile.
        self.max_num_tokens = self.num_tokens_paddings[-1]
180
181
182
183
184
185
186
187
188

        # Model-related.
        self.num_attn_layers = model_config.get_num_layers_by_block_type(
            parallel_config, LayerBlockType.attention)
        self.num_query_heads = model_config.get_num_attention_heads(
            parallel_config)
        self.num_kv_heads = model_config.get_num_kv_heads(parallel_config)
        self.head_size = model_config.get_head_size()
        self.hidden_size = model_config.get_hidden_size()
189
        self.vocab_size = model_config.get_vocab_size()
190

191
192
193
        if self.lora_config is not None:
            self.vocab_size += self.lora_config.lora_extra_vocab_size

194
195
196
        # Multi-modal data support
        self.mm_registry = MULTIMODAL_REGISTRY
        self.uses_mrope = model_config.uses_mrope
197
198
        self.supports_mm_inputs = self.mm_registry.supports_multimodal_inputs(
            model_config)
199
200
201
        # TODO: Support M-RoPE (e.g, Qwen2-VL)
        assert not self.uses_mrope, "TPU does not support M-RoPE yet."

202
203
204
205
206
207
208
209
        self._num_slices_per_kv_cache_update_block = \
            _get_num_slices_per_kv_cache_update_block(get_page_size_bytes(
                block_size=self.block_size,
                num_kv_heads=self.num_kv_heads,
                head_size=self.head_size,
                kv_cache_dtype=self.kv_cache_dtype,
            ))

210
        # Lazy initialization
211
        self.model: nn.Module  # Set after load_model
212
        self.kv_caches: list[torch.Tensor] = []
213
214
        # mm_hash -> encoder_output
        self.encoder_cache: dict[str, torch.Tensor] = {}
215
216
217

        # Request states.
        self.requests: dict[str, CachedRequestState] = {}
218

219
220
221
222
223
224
225
226
        # Initialize input batch early to avoid AttributeError in _update_states
        self.input_batch = InputBatch(
            max_num_reqs=self.max_num_reqs,
            max_model_len=self.max_model_len,
            max_num_batched_tokens=self.max_num_tokens,
            device=self.device,
            pin_memory=self.pin_memory,
            vocab_size=self.model_config.get_vocab_size(),
227
            block_sizes=[self.block_size],
228
229
        )

230
231
232
233
234
235
236
237
238
239
240
241
        # Cached torch/numpy tensor
        # The pytorch tensor and numpy array share the same buffer.
        # Sometimes the numpy op is faster so we create both.
        self.input_ids_cpu = torch.zeros(self.max_num_tokens,
                                         dtype=torch.int32,
                                         device="cpu")

        self.positions_cpu = torch.zeros(self.max_num_tokens,
                                         dtype=torch.int32,
                                         device="cpu")
        self.positions_np = self.positions_cpu.numpy()
        self.block_table_cpu = torch.zeros(
242
            (self.max_num_reqs, self.max_num_blocks_per_req),
243
            dtype=torch.int32,
244
            device="cpu")
245
246
247
248
249
250
251
252
253
        # adjust num_reqs to avoid SMEM OOM.
        self.num_reqs_most_model_len = min(
            PallasAttentionBackend.get_max_num_seqs(self.most_model_len,
                                                    self.block_size),
            self.max_num_reqs) if self.most_model_len is not None else None
        self.num_reqs_max_model_len = min(
            PallasAttentionBackend.get_max_num_seqs(self.max_model_len,
                                                    self.block_size),
            self.max_num_reqs)
254
255
256
257
258
259
260
261
262
263
264
        self.query_start_loc_cpu = torch.zeros(self.max_num_tokens + 1,
                                               dtype=torch.int32,
                                               device="cpu",
                                               pin_memory=self.pin_memory)
        self.query_start_loc_np = self.query_start_loc_cpu.numpy()

        self.seq_lens_cpu = torch.zeros(self.max_num_tokens,
                                        dtype=torch.int32,
                                        device="cpu",
                                        pin_memory=self.pin_memory)
        self.seq_lens_np = self.seq_lens_cpu.numpy()
265

266
267
268
269
270
271
272
        # Only relevant for multimodal models
        if self.supports_mm_inputs:
            self.is_mm_embed_cpu = torch.zeros(self.max_num_tokens,
                                               dtype=torch.bool,
                                               device="cpu",
                                               pin_memory=self.pin_memory)

273
274
        # Range tensor with values [0 .. self.max_num_tokens - 1].
        # Used to initialize positions / context_lens / seq_lens
275
276
        # Keep in int64 to avoid overflow with long context
        self.arange_np = np.arange(self.max_num_tokens, dtype=np.int64)
277
278
        self.num_reqs_paddings = _get_req_paddings(
            min_req_size=MIN_NUM_SEQS, max_req_size=self.max_num_reqs)
279

280
281
282
283
284
285
        # Layer pairings for cross-layer KV sharing.
        # If an Attention layer `layer_name` is in the keys of this dict, it
        # means this layer will perform attention using the keys and values
        # from the KV cache of `shared_kv_cache_layers[layer_name]`.
        self.shared_kv_cache_layers: dict[str, str] = {}

286
287
288
289
290
291
292
293
294
295
296
297
298
299
        # tensors for structured decoding
        self.grammar_bitmask_cpu = torch.zeros(
            (self.max_num_reqs, cdiv(self.vocab_size, 32)),
            dtype=torch.int32,
            device="cpu",
            pin_memory=self.pin_memory)
        self.require_structured_out_cpu = torch.zeros(
            (self.max_num_reqs, 1),
            dtype=torch.bool,
            device="cpu",
            pin_memory=self.pin_memory)
        self.structured_decode_arange = torch.arange(
            0, 32, device="cpu", pin_memory=self.pin_memory)

300
301
302
303
        self.mm_budget = (MultiModalBudget(
            self.model_config,
            self.scheduler_config,
            self.mm_registry,
304
        ) if self.supports_mm_inputs else None)
305

306
307
308
309
310
311
312
313
314
        if not self.use_spmd:
            self.sample_from_logits_func = torch.compile(
                self.sample_from_logits,
                backend="openxla",
                fullgraph=True,
                dynamic=False)
        else:
            self.sample_from_logits_func = self.sample_from_logits

315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
    def _update_num_xla_graphs(self, case_str):
        check_comp = self.check_recompilation and not self.enforce_eager
        if not check_comp:
            return

        total_cached_graphs = xr.get_num_cached_compilation_graph()
        new_compiled_graphs = total_cached_graphs - self.num_xla_graphs
        if new_compiled_graphs == 0:
            return

        logger.info("Add new %d compiled XLA graphs due to %s",
                    new_compiled_graphs, case_str)
        self.num_xla_graphs += new_compiled_graphs

    def _verify_num_xla_graphs(self, case_str):
        check_comp = self.check_recompilation and not self.enforce_eager
        if not check_comp:
            return

        curr_cached_graph = xr.get_num_cached_compilation_graph()
        assert self.num_xla_graphs == curr_cached_graph, (
            "Recompilation after warm up is detected during {}."
            " num_xla_graphs = {} curr_cached_graph = {}".format(
                case_str, self.num_xla_graphs, curr_cached_graph))

340
341
342
343
344
345
346
347
    def _update_states(self, scheduler_output: "SchedulerOutput") -> bool:
        """Update the cached states and the persistent batch with the scheduler
        output.

        The updated states are used by the `_prepare_inputs` function to create
        the input GPU tensors for the model.

        Returns:
348
            True if there is a new/resumed/paused/finished request.
349
350
351
352
353
354
355
356
357
358
359
360
            If False, we can skip copying SamplingMetadata to the GPU.
        """
        # Remove finished requests from the cached states.
        for req_id in scheduler_output.finished_req_ids:
            self.requests.pop(req_id, None)

        # Remove the finished requests from the persistent batch.
        # NOTE(woosuk): There could be an edge case where finished_req_ids and
        # scheduled_req_ids overlap. This happens when a request is aborted and
        # then resubmitted with the same ID. In this case, we treat them as two
        # distinct requests - clearing the cached states for the first request
        # and handling the second as a new request.
361
        removed_req_indices: list[int] = []
362
363
364
365
366
        for req_id in scheduler_output.finished_req_ids:
            req_index = self.input_batch.remove_request(req_id)
            if req_index is not None:
                removed_req_indices.append(req_index)

367
        # Free the cached encoder outputs.
368
369
        for mm_hash in scheduler_output.free_encoder_mm_hashes:
            self.encoder_cache.pop(mm_hash, None)
370

371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
        # Remove the unscheduled requests from the persistent batch.
        # NOTE(woosuk): The unscheduled requests are either preempted requests
        # or running requests that are not scheduled in this step. We remove
        # them from the persistent batch but keep their cached states since
        # they will be scheduled again sometime in the future.
        scheduled_req_ids = scheduler_output.num_scheduled_tokens.keys()
        cached_req_ids = self.input_batch.req_id_to_index.keys()
        unscheduled_req_ids = cached_req_ids - scheduled_req_ids
        # NOTE(woosuk): The persistent batch optimization assumes that
        # consecutive batches contain mostly the same requests. If batches
        # have low request overlap (e.g., alternating between two distinct
        # sets of requests), this optimization becomes very inefficient.
        for req_id in unscheduled_req_ids:
            req_index = self.input_batch.remove_request(req_id)
            assert req_index is not None
            removed_req_indices.append(req_index)

388
        req_ids_to_add: list[str] = []
389
390
        # Add new requests to the cached states.
        for new_req_data in scheduler_output.scheduled_new_reqs:
391
392
            assert new_req_data.sampling_params is not None,\
                "Pooling is not supported in TPU yet"
393
394
395
396
397
398
            req_id = new_req_data.req_id
            sampling_params = new_req_data.sampling_params

            self.requests[req_id] = CachedRequestState(
                req_id=req_id,
                prompt_token_ids=new_req_data.prompt_token_ids,
399
                prompt_embeds=new_req_data.prompt_embeds,
400
                mm_features=new_req_data.mm_features,
401
                sampling_params=sampling_params,
402
                pooling_params=None,
403
                generator=None,
404
405
406
407
408
409
410
411
412
                block_ids=new_req_data.block_ids,
                num_computed_tokens=new_req_data.num_computed_tokens,
                output_token_ids=[],
                lora_request=new_req_data.lora_request,
            )

            req_ids_to_add.append(req_id)

        # Update the states of the running/resumed requests.
413
414
        req_data = scheduler_output.scheduled_cached_reqs
        for i, req_id in enumerate(req_data.req_ids):
415
            req_state = self.requests[req_id]
416
417
418
            num_computed_tokens = req_data.num_computed_tokens[i]
            new_block_ids = req_data.new_block_ids[i]
            resumed_from_preemption = req_data.resumed_from_preemption[i]
419
420

            # Update the cached states.
421
422
            req_state.num_computed_tokens = num_computed_tokens
            if not resumed_from_preemption:
423
424
425
426
427
                if new_block_ids is not None:
                    # Append the new blocks to the existing block IDs.
                    for block_ids, new_ids in zip(req_state.block_ids,
                                                  new_block_ids):
                        block_ids.extend(new_ids)
428
            else:
429
                assert new_block_ids is not None
430
431
                # The request is resumed from preemption.
                # Replace the existing block IDs with the new ones.
432
                req_state.block_ids = new_block_ids
433
434
435
436
437
438
439
440
441
442
443

            req_index = self.input_batch.req_id_to_index.get(req_id)
            if req_index is None:
                # The request is not in the persistent batch.
                # The request was either preempted and resumed later, or was not
                # scheduled in the previous step and needs to be added again.
                req_ids_to_add.append(req_id)
                continue

            # Update the persistent batch.
            self.input_batch.num_computed_tokens_cpu[req_index] = (
444
                num_computed_tokens)
445
446
447
            if new_block_ids is not None:
                self.input_batch.block_table.append_row(
                    new_block_ids, req_index)
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464

        # Add the new or resumed requests to the persistent batch.
        # The smaller empty indices are filled first.
        removed_req_indices = sorted(removed_req_indices, reverse=True)
        for req_id in req_ids_to_add:
            req_state = self.requests[req_id]
            if removed_req_indices:
                # Fill the empty index.
                req_index = removed_req_indices.pop()
            else:
                # Append to the end.
                req_index = None
            self.input_batch.add_request(req_state, req_index)

        # Condense the batched states if there are empty indices.
        if removed_req_indices:
            self.input_batch.condense(removed_req_indices)
465

466
467
468
469
470
        return len(unscheduled_req_ids) > 0 or len(req_ids_to_add) > 0

    def get_model(self) -> nn.Module:
        return self.model

471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
    def get_supported_generation_tasks(self) -> list[GenerationTask]:
        model = self.get_model()
        supported_tasks = list[GenerationTask]()

        if is_text_generation_model(model):
            supported_tasks.append("generate")

        if supports_transcription(model):
            if model.supports_transcription_only:
                return ["transcription"]

            supported_tasks.append("transcription")

        return supported_tasks

486
487
488
489
490
    def get_supported_pooling_tasks(self) -> list[PoolingTask]:
        model = self.get_model()
        if not is_pooling_model(model):
            return []

491
        return list(model.pooler.get_supported_tasks())
492

493
494
495
496
497
498
499
500
501
502
    def get_supported_tasks(self) -> tuple[SupportedTask, ...]:
        tasks = list[SupportedTask]()

        if self.model_config.runner_type == "generate":
            tasks.extend(self.get_supported_generation_tasks())
        if self.model_config.runner_type == "pooling":
            tasks.extend(self.get_supported_pooling_tasks())

        return tuple(tasks)

503
    def get_kv_cache_spec(self) -> dict[str, KVCacheSpec]:
504
        """
505
        Generates the KVCacheSpec by parsing the kv cache format from each
506
507
        Attention module in the static forward context.
        Returns:
508
            KVCacheSpec: A dictionary mapping layer names to their KV cache
509
510
511
            format. Layers that do not need KV cache are not included.
        """

512
        layers = get_layers_from_vllm_config(self.vllm_config, Attention)
513
        block_size = self.vllm_config.cache_config.block_size
514
        kv_cache_spec: dict[str, KVCacheSpec] = {}
515
        for layer_name, attn_module in layers.items():
516
517
518
519
520
521
522
523
524
525
526
527
            if (kv_tgt_layer :=
                    attn_module.kv_sharing_target_layer_name) is not None:
                # The layer doesn't need its own KV cache and will use that of
                # the target layer. We skip creating a KVCacheSpec for it, so
                # that KV cache management logic will act as this layer does
                # not exist, and doesn't allocate KV cache for the layer. This
                # enables the memory saving of cross-layer kv sharing, allowing
                # a given amount of memory to accommodate longer context lengths
                # or enable more requests to be processed simultaneously.
                self.shared_kv_cache_layers[layer_name] = kv_tgt_layer
                continue

528
            if attn_module.attn_type == AttentionType.DECODER:
529
                if isinstance(attn_module, ChunkedLocalAttention):
530
531
532
                    logger.warning_once(
                        "Using irope in Pallas is not supported yet, it "
                        "will fall back to global attention for long context.")
533
534
535
536
537
                if attn_module.sliding_window is not None:
                    kv_cache_spec[layer_name] = SlidingWindowSpec(
                        block_size=block_size,
                        num_kv_heads=attn_module.num_kv_heads,
                        head_size=attn_module.head_size,
538
                        dtype=self.kv_cache_dtype,
539
540
541
542
543
544
545
                        sliding_window=attn_module.sliding_window,
                    )
                else:
                    kv_cache_spec[layer_name] = FullAttentionSpec(
                        block_size=block_size,
                        num_kv_heads=attn_module.num_kv_heads,
                        head_size=attn_module.head_size,
546
                        dtype=self.kv_cache_dtype,
547
                    )
548
549
550
551
552
553
554
555
556
557
558
559
            elif attn_module.attn_type in (AttentionType.ENCODER,
                                           AttentionType.ENCODER_ONLY):
                # encoder-only attention does not need KV cache.
                continue
            elif attn_module.attn_type == AttentionType.ENCODER_DECODER:
                raise NotImplementedError
            else:
                raise ValueError(
                    f"Unknown attention type: {attn_module.attn_type}")

        return kv_cache_spec

560
    def _get_slot_mapping_metadata(self, num_reqs,
561
                                   num_scheduled_tokens_per_req) -> np.ndarray:
562
563
564
565
566
567
568
569
570
571
572
573
        """
        Computes metadata for mapping slots to blocks in the key-value (KV)
        cache for a batch of requests.

        This function determines, for each request in the batch, how the
        scheduled tokens are distributed across memory blocks, and generates
        metadata needed to map slices of tokens to their corresponding positions
        in the KV cache.

        Args:
            num_reqs (int): Number of requests in the current batch.
            num_scheduled_tokens_per_req (int or np.ndarray): Number of tokens
574
                to be scheduled for each request.
575
576
577

        Returns:
            np.ndarray: A 2D array of shape (total_block_len, 3), where each row
578
                contains:
579
                - kv_cache_start_index (int): The starting index in the KV cache
580
                  for the corresponding slice.
581
                - new_kv_start_index (int): The starting index in the new KV
582
                  cache for the corresponding slice.
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
                - slice_len (int): The length of the slice.
        """
        slices_start = self.input_batch.num_computed_tokens_cpu[:num_reqs]
        slices_end = self.input_batch.num_computed_tokens_cpu[:num_reqs] + \
            num_scheduled_tokens_per_req
        local_block_start_idx = slices_start // self.block_size
        local_block_end_idx = (slices_end - 1) // self.block_size
        no_repeat_req_indices = self.arange_np[:num_reqs]
        global_block_start_idx = (
            no_repeat_req_indices * self.max_num_blocks_per_req +
            local_block_start_idx)
        block_lens = local_block_end_idx - local_block_start_idx + 1
        global_block_start_idx = np.repeat(global_block_start_idx, block_lens)
        slice_arange = np.concatenate([self.arange_np[:n] for n in block_lens])
        global_block_indices = global_block_start_idx + slice_arange
        block_table_cpu = self.input_batch.block_table[0].get_cpu_tensor()
        block_numbers = block_table_cpu.flatten()[global_block_indices].numpy()
        total_block_len = np.sum(block_lens)
        slot_mapping_slices = np.repeat(np.array([[0, self.block_size]],
                                                 dtype=np.int32),
                                        total_block_len,
                                        axis=0)
        cu_block_lens = np.zeros(len(block_lens) + 1, dtype=np.int32)
        np.cumsum(block_lens, out=cu_block_lens[1:])
        for req_idx in range(num_reqs):
            slot_mapping_slices[cu_block_lens[req_idx]][
                0] = slices_start[req_idx] % self.block_size
            slot_mapping_slices[
                cu_block_lens[req_idx + 1] -
                1][1] = (slices_end[req_idx] - 1) % self.block_size + 1
        slice_lens = slot_mapping_slices[:, 1] - slot_mapping_slices[:, 0]
        cu_slices_lens = np.zeros(len(slice_lens) + 1, dtype=np.int32)
        np.cumsum(slice_lens, out=cu_slices_lens[1:])
        kv_cache_start_indices = slot_mapping_slices[:, 0] + \
            (block_numbers * self.block_size)
        new_kv_start_indices = cu_slices_lens[:-1]
        slot_mapping_metadata = np.stack(
            [kv_cache_start_indices, new_kv_start_indices, slice_lens], axis=1)
        return slot_mapping_metadata

623
624
625
    def _prepare_inputs(self, scheduler_output: "SchedulerOutput",
                        start_index: int):
        assert scheduler_output.total_num_scheduled_tokens > 0
626
627
        num_reqs = self.input_batch.num_reqs
        assert num_reqs > 0
628
        assert start_index < num_reqs
629

630
        # Get the number of scheduled tokens for each request.
631
        use_max_model_len = self.most_model_len is None
632
633
        num_scheduled_tokens_per_req = []
        max_num_scheduled_tokens_all_reqs = 0
634
635
636
637
638
        end_index = start_index

        # Use either most_model_len or max_model_len depending on request size.
        for i in range(start_index, num_reqs):
            req_id = self.input_batch.req_ids[i]
639
            assert req_id is not None
640
            num_tokens = scheduler_output.num_scheduled_tokens[req_id]
641
642
            if not use_max_model_len and num_tokens > self.most_model_len:
                use_max_model_len = True
643
            num_scheduled_tokens_per_req.append(num_tokens)
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
        if use_max_model_len:
            if len(num_scheduled_tokens_per_req) > self.num_reqs_max_model_len:
                num_scheduled_tokens_per_req = \
                    num_scheduled_tokens_per_req[:self.num_reqs_max_model_len]
                end_index = start_index + self.num_reqs_max_model_len
            else:
                end_index = num_reqs
        else:
            if len(num_scheduled_tokens_per_req
                   ) > self.num_reqs_most_model_len:
                num_scheduled_tokens_per_req = \
                    num_scheduled_tokens_per_req[:self.num_reqs_most_model_len]
                end_index = start_index + self.num_reqs_most_model_len
            else:
                end_index = num_reqs
        max_num_scheduled_tokens_all_reqs = max(num_scheduled_tokens_per_req)
660
661
        num_scheduled_tokens_per_req = np.array(num_scheduled_tokens_per_req,
                                                dtype=np.int32)
662
        total_num_scheduled_tokens = sum(num_scheduled_tokens_per_req)
663
664
        assert max_num_scheduled_tokens_all_reqs > 0

665
666
        num_reqs = len(num_scheduled_tokens_per_req)

667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
        # Get request indices.
        # E.g., [2, 5, 3] -> [0, 0, 1, 1, 1, 1, 1, 2, 2, 2]
        # For each scheduled token, what are the corresponding req index.
        req_indices = np.repeat(self.arange_np[:num_reqs],
                                num_scheduled_tokens_per_req)

        # Get batched arange.
        # E.g., [2, 5, 3] -> [0, 1, 0, 1, 2, 3, 4, 0, 1, 2]
        # For each scheduled token, what is its position in corresponding req.
        arange = np.concatenate(
            [self.arange_np[:n] for n in num_scheduled_tokens_per_req])

        # Get positions.
        positions_np = self.positions_np[:total_num_scheduled_tokens]
        np.add(self.input_batch.num_computed_tokens_cpu[req_indices],
               arange,
               out=positions_np)

        # Get token indices.
        # E.g., [0, 1, 0, 1, 2, 3, 4, 0, 1, 2]
        # -> [0, 1, M, M + 1, M + 2, M + 3, M + 4, 2 * M, 2 * M + 1, 2 * M + 2]
        # where M is the max_model_len.
        token_indices = (positions_np +
                         req_indices * self.input_batch.token_ids_cpu.shape[1])

        # NOTE(woosuk): We use torch.index_select instead of np.take here
        # because torch.index_select is much faster than np.take for large
        # tensors.
695
696
        torch.index_select(self.input_batch.token_ids_cpu_tensor.flatten(),
                           0,
697
698
699
700
701
702
703
                           torch.from_numpy(token_indices),
                           out=self.input_ids_cpu[:total_num_scheduled_tokens])

        # Prepare the attention metadata.
        self.query_start_loc_np[0] = 0
        np.cumsum(num_scheduled_tokens_per_req,
                  out=self.query_start_loc_np[1:num_reqs + 1])
704
        self.query_start_loc_np[num_reqs + 1:] = 1
705
706
707
708
709
710

        self.seq_lens_np[:num_reqs] = (
            self.input_batch.num_computed_tokens_cpu[:num_reqs] +
            num_scheduled_tokens_per_req)

        # Do the padding and copy the tensors to the TPU.
711
        padded_total_num_scheduled_tokens = _get_padded_token_len(
712
            self.num_tokens_paddings, total_num_scheduled_tokens)
713
714
715
        # Zero out to avoid spurious values from prev iteration (last cp chunk)
        self.input_ids_cpu[
            total_num_scheduled_tokens:padded_total_num_scheduled_tokens] = 0
716
717
718
719
720
721
        self.input_ids = self.input_ids_cpu[:
                                            padded_total_num_scheduled_tokens].to(
                                                self.device)
        self.position_ids = self.positions_cpu[:
                                               padded_total_num_scheduled_tokens].to(
                                                   self.device)
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
        if use_max_model_len:
            block_tables = self.block_table_cpu[:self.num_reqs_max_model_len, :
                                                self.max_num_blocks_per_req]
            block_tables[:num_reqs, :self.max_num_blocks_per_req] = (
                self.input_batch.block_table[0].get_cpu_tensor()[:num_reqs])
            query_start_loc = self.query_start_loc_cpu[:self.
                                                       num_reqs_max_model_len +
                                                       1].to(self.device)
            seq_lens = self.seq_lens_cpu[:self.num_reqs_max_model_len].to(
                self.device)
        else:
            block_tables = self.block_table_cpu[:self.
                                                num_reqs_most_model_len, :self.
                                                num_blocks_per_most_len_req]
            block_tables[:num_reqs, :self.num_blocks_per_most_len_req] = (
                self.input_batch.block_table[0].get_cpu_tensor()
                [:num_reqs, :self.num_blocks_per_most_len_req])
            query_start_loc = self.query_start_loc_cpu[:self.
                                                       num_reqs_most_model_len +
                                                       1].to(self.device)
            seq_lens = self.seq_lens_cpu[:self.num_reqs_most_model_len].to(
                self.device)
744
        block_tables = block_tables.to(self.device)
745

746
        # Calculate the slot mapping
747
748
        slot_mapping_metadata = self._get_slot_mapping_metadata(
            num_reqs, num_scheduled_tokens_per_req)
749
        num_kv_update_slices = slot_mapping_metadata.shape[0]
750
751
        padded_num_slices = _get_padded_num_kv_cache_update_slices(
            padded_total_num_scheduled_tokens, self.max_num_reqs,
752
            self.block_size)
753
754
755
756
757
758
759
760
        slot_mapping_metadata = np.pad(
            slot_mapping_metadata,
            [[0, padded_num_slices - len(slot_mapping_metadata)], [0, 0]],
            constant_values=0)
        slot_mapping_metadata = np.transpose(slot_mapping_metadata)
        slot_mapping_metadata = torch.tensor(slot_mapping_metadata,
                                             device=self.device)

761
762
763
764
765
766
767
768
769
770
771
        if self.lora_config is not None:
            # We need to respect padding when activating LoRA adapters
            padded_num_scheduled_tokens_per_req = np.copy(
                num_scheduled_tokens_per_req
            )  # Copying to avoid accidental state corruption bugs
            padded_num_scheduled_tokens_per_req[-1] += \
                padded_total_num_scheduled_tokens - total_num_scheduled_tokens

            self.set_active_loras(self.input_batch,
                                  padded_num_scheduled_tokens_per_req)

772
        attn_metadata = PallasMetadata(
773
            slot_mapping=slot_mapping_metadata,
774
            block_tables=block_tables,
775
776
            context_lens=seq_lens,
            query_start_loc=query_start_loc,
777
778
779
            num_seqs=torch.tensor([num_reqs],
                                  dtype=torch.int32,
                                  device=self.device),
780
781
782
            num_kv_update_slices=torch.tensor([num_kv_update_slices],
                                              dtype=torch.int32,
                                              device=self.device),
783
784
            num_slices_per_kv_cache_update_block=self.
            _num_slices_per_kv_cache_update_block,
785
        )
786
787
788
789
790
        # NOTE(woosuk): Due to chunked prefills, there can be at most 1 partial
        # request in the batch. While we should not sample any token from this
        # partial request, we do so for simplicity. We will ignore the sampled
        # token from the partial request.
        # TODO: Support prompt logprobs.
791
792
        padded_num_reqs = _get_padded_num_reqs_with_upper_limit(
            num_reqs, self.max_num_reqs)
793
794
        # Indices at which we sample (positions of last token in the sequence).
        # Padded to avoid recompiling when `num_reqs` varies.
795
796
        logits_indices = self.query_start_loc_cpu[1:padded_num_reqs + 1] - 1
        logits_indices = logits_indices.to(self.device)
797

798
799
800
801
802
803
804
805
806
807
808
        if self.lora_config is not None:
            # We need to respect padding when activating LoRA adapters
            padded_num_scheduled_tokens_per_req = np.copy(
                num_scheduled_tokens_per_req
            )  # Copying to avoid accidental state corruption bugs
            padded_num_scheduled_tokens_per_req[-1] += \
                padded_total_num_scheduled_tokens - total_num_scheduled_tokens

            self.set_active_loras(self.input_batch,
                                  padded_num_scheduled_tokens_per_req)

809
810
811
812
813
814
        layer_names = get_layers_from_vllm_config(self.vllm_config,
                                                  Attention).keys()
        per_layer_attn_metadata = {
            layer_name: attn_metadata
            for layer_name in layer_names
        }
815
816
        return per_layer_attn_metadata, logits_indices, padded_num_reqs,\
            num_reqs, end_index
817

818
    def _execute_mm_encoder(self, scheduler_output: "SchedulerOutput"):
819
820
821
822
823
        scheduled_encoder_inputs = scheduler_output.scheduled_encoder_inputs
        if not scheduled_encoder_inputs:
            return

        # Batch the multi-modal inputs.
824
        mm_kwargs = list[MultiModalKwargsItem]()
825
826
        # List of tuple (mm_hash, pos_info)
        mm_hashes_pos = list[tuple[str, PlaceholderRange]]()
827
828
        for req_id, encoder_input_ids in scheduled_encoder_inputs.items():
            req_state = self.requests[req_id]
829
830

            for mm_input_id in encoder_input_ids:
831
832
833
834
                mm_feature = req_state.mm_features[mm_input_id]
                mm_hash = mm_feature.identifier
                mm_kwargs.append(mm_feature.data)
                mm_hashes_pos.append((mm_hash, mm_feature.mm_position))
835
836
837
838
839
840
841
842

        # Batch mm inputs as much as we can: if a request in the batch has
        # multiple modalities or a different modality than the previous one,
        # we process it separately to preserve item order.
        # FIXME(ywang96): This is a hacky way to deal with multiple modalities
        # in the same batch while still being able to benefit from batching
        # multimodal inputs. The proper solution should be reordering the
        # encoder outputs.
843
        model = cast(SupportsMultiModal, self.model)
844
        encoder_outputs = []
845
846
        for _, num_items, mm_kwargs_group in group_mm_kwargs_by_modality(
                mm_kwargs,
847
                device=self.device,
848
                pin_memory=self.pin_memory,
849
                merge_by_field_config=model.merge_by_field_config,
850
        ):
851
852
853
854
855
856
857
            # Run the encoder.
            # `curr_group_outputs` is either of the following:
            # 1. A tensor of shape (num_items, feature_size, hidden_size)
            # in case feature_size is fixed across all multimodal items.
            # 2. A list or tuple (length: num_items) of tensors, each of shape
            # (feature_size, hidden_size) in case the feature size is dynamic
            # depending on the input multimodal items.
858
            torch_xla.sync(wait=False)
859
            curr_group_outputs = model.get_multimodal_embeddings(
860
                **mm_kwargs_group)
861
            torch_xla.sync(wait=False)
862

863
864
            sanity_check_mm_encoder_outputs(
                curr_group_outputs,
865
                expected_num_items=num_items,
866
867
            )

868
869
870
871
872
873
            if isinstance(curr_group_outputs, torch.Tensor):
                encoder_outputs.append(curr_group_outputs)
            else:
                assert isinstance(curr_group_outputs, (list, tuple))
                for output in curr_group_outputs:
                    encoder_outputs.append(output)
874
875

        # Cache the encoder outputs.
876
877
878
        # NOTE (NickLucche) here we diverge from logic in other runners, as we
        # assume to only have whole mm items to process. Hence we avoid the
        # intrinsic dynamism that `scatter_mm_placeholders` introduces.
879
        for (mm_hash, pos_info), output in zip(mm_hashes_pos, encoder_outputs):
880
881
            assert pos_info.is_embed is None, "Expected all positions to be"\
                " contiguous and embeddings."
882
            self.encoder_cache[mm_hash] = output
883
884

    def _gather_mm_embeddings(
885
886
        self,
        scheduler_output: "SchedulerOutput",
887
888
889
890
891
892
893
894
895
896
    ) -> tuple[list[torch.Tensor], torch.Tensor]:
        total_num_scheduled_tokens = scheduler_output.total_num_scheduled_tokens
        padded_total_num_scheduled_tokens = _get_padded_token_len(
            self.num_tokens_paddings, total_num_scheduled_tokens)

        is_mm_embed = self.is_mm_embed_cpu
        is_mm_embed[:padded_total_num_scheduled_tokens] = False
        mm_embeds = list[torch.Tensor]()
        req_start_idx = 0

897
898
899
900
901
        for req_id in self.input_batch.req_ids:
            num_scheduled_tokens = scheduler_output.num_scheduled_tokens[
                req_id]
            req_state = self.requests[req_id]
            num_computed_tokens = req_state.num_computed_tokens
902

903
904
905
906
            # TODO unroll loop and assume/enforce --disable_chunked_mm_input
            # NOTE (NickLucche) here we diverge from logic in other runners, as
            # we assume to only have whole mm items to process. Hence we avoid
            # the intrinsic dynamism that `gather_mm_placeholders` introduces.
907
908
            for mm_feature in req_state.mm_features:
                pos_info = mm_feature.mm_position
909
910
                start_pos = pos_info.offset
                num_encoder_tokens = pos_info.length
911
912
913
914
915
916
917
918
919
920
921
922

                # The encoder output is needed if the two ranges overlap:
                # [num_computed_tokens,
                #  num_computed_tokens + num_scheduled_tokens) and
                # [start_pos, start_pos + num_encoder_tokens)
                if start_pos >= num_computed_tokens + num_scheduled_tokens:
                    # The encoder output is not needed in this step.
                    break
                if start_pos + num_encoder_tokens <= num_computed_tokens:
                    # The encoder output is already processed and stored
                    # in the decoder's KV cache.
                    continue
923
924
925
926
927
928
929
930

                start_idx = max(num_computed_tokens - start_pos, 0)
                end_idx = min(
                    num_computed_tokens - start_pos + num_scheduled_tokens,
                    num_encoder_tokens,
                )
                assert start_idx < end_idx

931
                mm_hash = mm_feature.identifier
932
933
934
                encoder_output = self.encoder_cache.get(mm_hash, None)
                assert encoder_output is not None,\
                      f"Encoder cache miss for {mm_hash}."
935

936
937
                assert pos_info.is_embed is None, "Expected all positions to"\
                " be contiguous and embeddings."
938
939
940
941
942
943

                req_start_pos = req_start_idx + start_pos - num_computed_tokens
                is_mm_embed[req_start_pos+start_idx:req_start_pos + end_idx] \
                    = True

                # Only whole mm items are processed
944
                mm_embeds.append(encoder_output)
945

946
947
948
949
950
951
952
953
954
955
956
957
            req_start_idx += num_scheduled_tokens

        is_mm_embed = is_mm_embed[:padded_total_num_scheduled_tokens] \
            .to(self.device)

        return mm_embeds, is_mm_embed

    def _get_model_inputs(
        self,
        input_ids: torch.Tensor,
        mm_embed_inputs: Optional[tuple[list[torch.Tensor], torch.Tensor]],
    ):
958
        if self.supports_mm_inputs:
959
960
            mm_embeds, is_mm_embed = mm_embed_inputs or (None, None)

961
962
963
            # NOTE(woosuk): To unify token ids and soft tokens (vision
            # embeddings), we always use embeddings (rather than token ids)
            # as input to the multimodal model, even when the input is text.
964
            inputs_embeds = self.model.get_input_embeddings(
965
                input_ids,
966
                multimodal_embeddings=mm_embeds,
967
                is_multimodal=is_mm_embed,
968
            )
969

970
971
972
973
974
975
976
977
            return None, inputs_embeds
        else:
            # For text-only models, we use token ids as input.
            # While it is possible to use embeddings as input just like the
            # multimodal models, it is not desirable for performance since
            # then the embedding layer is not included in the CUDA graph.
            return input_ids, None

978
979
980
981
    @torch.no_grad()
    def execute_model(
        self,
        scheduler_output: "SchedulerOutput",
982
        intermediate_tensors: Optional[IntermediateTensors] = None,
983
984
985
    ) -> ModelRunnerOutput:
        # Update cached state
        self._update_states(scheduler_output)
986
        if not scheduler_output.total_num_scheduled_tokens:
987
988
989
990
991
992
            if not has_kv_transfer_group():
                # Return empty ModelRunnerOutput if there's no work to do.
                return EMPTY_MODEL_RUNNER_OUTPUT

            return self.kv_connector_no_forward(scheduler_output,
                                                self.vllm_config)
993

994
        if self.supports_mm_inputs:
995
            # Run the multimodal encoder if any.
996
            self._execute_mm_encoder(scheduler_output)
997
            mm_embed_inputs = self._gather_mm_embeddings(scheduler_output)
998
        else:
999
1000
            mm_embed_inputs = None

1001
        torch_xla.sync(wait=False)
1002
        # Prepare inputs, the requests might be split into multiple
1003
1004
1005
1006
        # executions, combine the result of each execution.
        start_index = 0
        combined_selected_tokens: list[torch.Tensor] = []
        combined_logprobs: list[LogprobsLists] = []
1007
1008
1009
1010
1011
1012

        # NOTE: setup current batch's metadata for kv connector.
        # Currently, only verified with NixlConnector
        with set_forward_context(None, self.vllm_config):
            self.maybe_setup_kv_connector(scheduler_output)

1013
1014
1015
1016
        while start_index < self.input_batch.num_reqs:
            attn_metadata, logits_indices, padded_num_reqs, num_reqs,\
                end_index = self._prepare_inputs(scheduler_output, start_index)
            input_ids, inputs_embeds = self._get_model_inputs(
1017
                self.input_ids, mm_embed_inputs)
1018
            torch_xla.sync(wait=False)
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
            # Run the decoder
            with set_forward_context(
                    attn_metadata,
                    self.vllm_config,
                    num_tokens=scheduler_output.total_num_scheduled_tokens):
                hidden_states = self.model(
                    input_ids=input_ids,
                    positions=self.position_ids,
                    inputs_embeds=inputs_embeds,
                )
            hidden_states = self.select_hidden_states(hidden_states,
                                                      logits_indices)
            logits = self.compute_logits(hidden_states)
            tpu_sampling_metadata = TPUSupportedSamplingMetadata.\
                from_input_batch(self.input_batch, padded_num_reqs, self.device)
            if scheduler_output.grammar_bitmask is not None:
                require_struct_decoding, grammar_bitmask_padded, arange = \
                    self.prepare_structured_decoding_input(logits,
                                                           scheduler_output)
                logits = self.structured_decode(require_struct_decoding,
                                                grammar_bitmask_padded, logits,
                                                arange)
            selected_token_ids = self.sample_from_logits_func(
                logits, tpu_sampling_metadata)
            # NOTE (NickLucche) Use the original logits (before any penalties or
            # temperature scaling) for the top-k logprobs. We can't enforce it
            # due to recompilations outside torch.compiled code, so just make
            # sure `sample_from_logits` does not modify the logits in-place.
            logprobs = self.gather_logprobs(logits, selected_token_ids) \
                if tpu_sampling_metadata.logprobs else None

            # Remove padding on cpu and keep dynamic op outside of xla graph.
            selected_token_ids = selected_token_ids.cpu()[:num_reqs]

            combined_selected_tokens.append(selected_token_ids)
            if tpu_sampling_metadata.logprobs:
                combined_logprobs.append(logprobs.tolists())

            start_index = end_index

1059
1060
1061
1062
1063
1064
1065
1066
        # NOTE: current kv load and save get h2d/d2h copies involved.
        # Those copies are blocking. Once they become async., kv_save
        # should be called right after each single forward pass,
        # instead of the forwards of the entire input batch.
        self.maybe_wait_for_kv_save()
        finished_sending, finished_recving = (
            self.get_finished_kv_transfers(scheduler_output))

1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
        selected_token_ids = torch.cat(combined_selected_tokens, dim=0)
        if tpu_sampling_metadata.logprobs:

            def concat_lists(input_lists):
                result = []
                for input_list in input_lists:
                    result.extend(input_list)
                return result

            logprobs_lists = LogprobsLists(logprob_token_ids=concat_lists(
                [lp.logprob_token_ids for lp in combined_logprobs]),
                                           logprobs=concat_lists([
                                               lp.logprobs
                                               for lp in combined_logprobs
                                           ]),
                                           sampled_token_ranks=concat_lists([
                                               lp.sampled_token_ranks
                                               for lp in combined_logprobs
                                           ]))
        else:
            logprobs_lists = None
1088

1089
1090
        # Update the cache state concurrently. Code above will not block until
        # we use `selected_token_ids`. Add mark_step if post-processing changes
1091
        request_seq_lens: list[tuple[int, CachedRequestState, int]] = []
1092
        discard_sampled_tokens_req_indices = []
1093
        num_reqs = self.input_batch.num_reqs
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
        for i, req_id in zip(range(num_reqs), self.input_batch.req_ids):
            assert req_id is not None
            req_state = self.requests[req_id]
            seq_len = (req_state.num_computed_tokens +
                       scheduler_output.num_scheduled_tokens[req_id])
            if seq_len >= req_state.num_tokens:
                request_seq_lens.append((i, req_state, seq_len))
            else:
                # Ignore the sampled token from the partial request.
                # Rewind the generator state as if the token was not sampled.
                generator = self.input_batch.generators.get(i)
                if generator is not None:
                    # This relies on cuda-specific torch-internal impl details
                    generator.set_offset(generator.get_offset() - 4)

1109
1110
1111
1112
                # Record the index of the request that should not be sampled,
                # so that we could clear the sampled tokens before returning.
                discard_sampled_tokens_req_indices.append(i)

1113
1114
1115
        assert all(
            req_id is not None for req_id in
            self.input_batch.req_ids[:num_reqs]), "req_ids contains None"
1116
        req_ids = cast(list[str], self.input_batch.req_ids[:num_reqs])
1117

1118
        prompt_logprobs_dict: dict[str, Optional[LogprobsTensors]] = {}
1119
        for req_id in self.input_batch.req_ids[:num_reqs]:
1120
1121
            prompt_logprobs_dict[req_id] = None

1122
1123
1124
        max_gen_len = selected_token_ids.shape[-1]
        if max_gen_len == 1:
            valid_sampled_token_ids = selected_token_ids.tolist()
1125

1126
1127
1128
1129
1130
1131
1132
            # Mask out the sampled tokens that should not be sampled.
            # TODO: Keep in sync with gpu_model_runner.py, in particular
            #       the "else" case here
            for i in discard_sampled_tokens_req_indices:
                valid_sampled_token_ids[i].clear()

            # Append sampled tokens
1133
1134
1135
1136
1137
            for i, req_state, seq_len in request_seq_lens:
                token_id = valid_sampled_token_ids[i][0]
                self.input_batch.token_ids_cpu[i, seq_len] = token_id
                req_state.output_token_ids.append(token_id)
                self.input_batch.num_tokens[i] += 1
1138

1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
        else:
            valid_mask = selected_token_ids != INVALID_TOKEN_ID
            gen_lens = valid_mask.sum(dim=1).tolist()
            valid_sampled_token_ids = [
                seq.tolist()
                for seq in selected_token_ids[valid_mask].split(gen_lens)
            ]
            self.input_batch.num_tokens[:num_reqs] += gen_lens
            for i, req_state, seq_len in request_seq_lens:
                target_slice = slice(seq_len - gen_lens[i] + 1, seq_len + 1)
                self.input_batch.token_ids_cpu[
                    i, target_slice] = valid_sampled_token_ids[i]
                req_state.output_token_ids.extend(valid_sampled_token_ids[i])

1153
1154
1155
1156
1157
1158
1159
        kv_connector_output = None if (
            finished_sending is None
            and finished_recving is None) else KVConnectorOutput(
                finished_sending=finished_sending,
                finished_recving=finished_recving,
            )

1160
        model_runner_output = ModelRunnerOutput(
1161
            req_ids=req_ids,
1162
            req_id_to_index=self.input_batch.req_id_to_index,
1163
            sampled_token_ids=valid_sampled_token_ids,
1164
            logprobs=logprobs_lists,
1165
            prompt_logprobs_dict=prompt_logprobs_dict,
1166
            pooler_output=[],
1167
1168
            kv_connector_output=kv_connector_output,
        )
1169
1170
1171
1172
1173

        # Check there are no new graphs compiled - all the graphs should be
        # captured and compiled during warm up.
        self._verify_num_xla_graphs("execute_model")

1174
1175
        return model_runner_output

1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
    def update_config(self, overrides: dict[str, Any]) -> None:
        # TODO: TPU config may need extra validation
        # https://github.com/vllm-project/vllm/pull/20095#discussion_r2201497754
        allowed_config_names = {"load_config", "model_config"}
        for config_name, config_overrides in overrides.items():
            assert config_name in allowed_config_names, \
                f"Config `{config_name}` not supported. " \
                f"Allowed configs: {allowed_config_names}"
            config = getattr(self, config_name)
            new_config = update_config(config, config_overrides)
            setattr(self, config_name, new_config)

1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
    def load_model(self) -> None:
        self.device = self.device_config.device

        # NOTE(woosuk): While the executor assigns the TP ranks to the worker
        # process, the ranks can be different from the ranks internally assigned
        # by the xm runtime. Therefore, there is a mismatch in the rank
        # assignment between the gloo (cpu) runtime and the xm (tpu) runtime.
        # This is not a problem in linear layers because all-reduce is
        # rank-agnostic. However, it matters for all-gather as the ranks
        # determine the order of concatenating the output tensors.
        # As a workaround, we use the xm's rank assignment only when loading
        # the embedding weights.
        xm_tp_rank = xr.global_ordinal()
        with patch(
                "vllm.model_executor.layers.vocab_parallel_embedding."
                "get_tensor_model_parallel_rank",
                return_value=xm_tp_rank):
1205
1206
1207
1208
1209
            try:
                if self.use_spmd:
                    tpu_loader = TPUModelLoader(
                        load_config=self.vllm_config.load_config)
                    model = tpu_loader.load_model(
1210
                        vllm_config=self.vllm_config,
1211
1212
                        model_config=self.vllm_config.model_config,
                        mesh=self.mesh)
1213
                else:
1214
                    model_loader = get_model_loader(self.load_config)
1215
1216
1217
1218
                    logger.info("Loading model from scratch...")
                    model = model_loader.load_model(
                        vllm_config=self.vllm_config,
                        model_config=self.model_config)
1219
1220
1221
1222
1223
1224
1225
            except RuntimeError as e:
                raise RuntimeError(
                    f"Unable to load model, a likely reason is the model is "
                    "too large for the current device's HBM memory. "
                    "Consider switching to a smaller model "
                    "or sharding the weights on more chips. "
                    f"See the detailed error: {e}") from e
1226
        if self.lora_config is not None:
1227
            model = self.load_lora_model(model, self.vllm_config, self.device)
1228
            replace_set_lora(model)
1229

1230
1231
        # Sync all pending XLA execution during model initialization and weight
        # loading.
1232
        torch_xla.sync(wait=False)
1233
        xm.wait_device_ops()
1234
1235
        if not hasattr(self, "model"):
            self.model = model
1236
        self.sampler = TPUSampler()
1237

1238
1239
1240
1241
1242
1243
1244
    def reload_weights(self) -> None:
        assert getattr(self, "model", None) is not None, \
            "Cannot reload weights before model is loaded."
        model_loader = get_model_loader(self.load_config)
        logger.info("Reloading weights inplace...")
        model_loader.load_weights(self.model, model_config=self.model_config)

1245
    @torch.no_grad()
1246
1247
    def _dummy_run(self, num_tokens: int, num_reqs: int,
                   num_blocks: int) -> None:
1248
        if self.supports_mm_inputs:
1249
1250
1251
1252
1253
1254
            input_ids = None
            inputs_embeds = torch.zeros((num_tokens, self.hidden_size),
                                        dtype=self.dtype,
                                        device=self.device)
        else:
            input_ids = torch.zeros((num_tokens),
1255
                                    dtype=torch.int32).to(self.device)
1256
            inputs_embeds = None
1257
        actual_num_reqs = min(num_tokens, num_reqs)
1258
        position_ids = torch.zeros(num_tokens,
1259
                                   dtype=torch.int32).to(self.device)
1260
        padded_num_slices = _get_padded_num_kv_cache_update_slices(
1261
            num_tokens, self.max_num_reqs, self.block_size)
1262
1263
        num_kv_update_slices = torch.tensor([padded_num_slices],
                                            dtype=torch.int32).to(self.device)
1264
1265
        slot_mapping = torch.zeros((3, padded_num_slices),
                                   dtype=torch.int32).to(self.device)
1266
1267
1268
        block_tables = torch.zeros((num_reqs, num_blocks),
                                   dtype=torch.int32).to(self.device)
        query_lens = [1] * num_reqs
1269
1270
1271
1272
        query_start_loc = torch.cumsum(torch.tensor([0] + query_lens,
                                                    dtype=torch.int32),
                                       dim=0,
                                       dtype=torch.int32).to(self.device)
1273
        context_lens = torch.ones((num_reqs, ),
1274
                                  dtype=torch.int32).to(self.device)
1275
        num_seqs = torch.tensor([actual_num_reqs],
1276
                                dtype=torch.int32).to(self.device)
1277
1278
1279
1280
1281
        attn_metadata = PallasMetadata(
            slot_mapping=slot_mapping,
            block_tables=block_tables,
            context_lens=context_lens,
            query_start_loc=query_start_loc,
1282
            num_seqs=num_seqs,
1283
            num_kv_update_slices=num_kv_update_slices,
1284
1285
            num_slices_per_kv_cache_update_block=self.
            _num_slices_per_kv_cache_update_block,
1286
        )
1287

1288
        if self.supports_mm_inputs:
1289
1290
1291
            torch._dynamo.mark_dynamic(inputs_embeds, 0)
        else:
            torch._dynamo.mark_dynamic(input_ids, 0)
1292
1293
        torch._dynamo.mark_dynamic(position_ids, 0)
        torch._dynamo.mark_dynamic(attn_metadata.slot_mapping, 0)
1294
1295
1296
        torch._dynamo.mark_dynamic(attn_metadata.block_tables, (0, 1))
        torch._dynamo.mark_dynamic(attn_metadata.context_lens, 0)
        torch._dynamo.mark_dynamic(attn_metadata.query_start_loc, 0)
1297

1298
1299
1300
1301
1302
1303
1304
        layer_names = get_layers_from_vllm_config(self.vllm_config,
                                                  Attention).keys()
        per_layer_attn_metadata = {
            layer_name: attn_metadata
            for layer_name in layer_names
        }

1305
        with self.maybe_select_dummy_loras(
1306
1307
1308
                self.lora_config,
                np.array([num_tokens], dtype=np.int32)), set_forward_context(
                    per_layer_attn_metadata, self.vllm_config, 0):
1309
1310
1311
1312
            out = self.model(input_ids=input_ids,
                             positions=position_ids,
                             inputs_embeds=inputs_embeds)
        self._hidden_states_dtype = out.dtype
1313

1314
1315
    def _set_active_loras(self, prompt_lora_mapping, token_lora_mapping,
                          lora_requests) -> None:
1316
        torch_xla.sync(wait=False)  # Captures input updates
1317
1318
        super()._set_active_loras(prompt_lora_mapping, token_lora_mapping,
                                  lora_requests)
1319
        torch_xla.sync(wait=False)  # Captures metadata updates
1320

1321
    def _precompile_mm_encoder(self) -> None:
1322
        if not self.supports_mm_inputs:
1323
1324
            return

1325
1326
        # Pre-compile MM encoder for all supported data modalities.
        hf_config = self.vllm_config.model_config.hf_config
1327
1328
1329
1330
1331
1332
1333

        mm_budget = self.mm_budget
        assert mm_budget is not None

        max_items_per_seq_by_modality = mm_budget.max_items_per_batch_by_modality  # noqa: E501

        for mode, max_items_per_seq in max_items_per_seq_by_modality.items():
1334
1335
1336
1337
1338
            logger.info(
                "Compiling Multimodal %s Encoder with different input"
                " shapes.", mode)
            start = time.perf_counter()
            # No padding for MM encoder just yet.
1339
            for num_items in range(1, max_items_per_seq + 1):
1340
1341
                logger.info("  -- mode: %s items: %d", mode, num_items)
                batched_dummy_mm_inputs = self._get_mm_dummy_batch(
1342
1343
1344
                    mode,
                    num_items,
                )
1345
                # Run multimodal encoder.
1346
                torch_xla.sync(wait=False)
1347
1348
                mm_embeds = self.model.get_multimodal_embeddings(
                    **batched_dummy_mm_inputs)
1349
                torch_xla.sync(wait=False)
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
                num_patches = mm_embeds[0].shape[0]
                items_size = num_patches * num_items

                # NOTE (NickLucche) pre-compile `get_input_embeddings` when mm
                # embeddings are present. We assume `--disable-mm-chunked`,
                # hence only whole items can be scheduled. This implies we just
                # need to compile when `num_items` fit the (padded) `input_ids`
                for num_tokens in self.num_tokens_paddings:
                    if num_tokens >= items_size:
                        # XLA Workaround: if torch.zeros(..device) is used, XLA
                        # compiles a scalar+expansion op, which won't match
                        # the graph generated at runtime. CPU->TPU must be used
                        placeholders_ids = torch.zeros(num_tokens,
                                                       dtype=torch.int32,
                                                       device="cpu")
                        # Align placeholders and actual num mm_embeddings.
                        placeholders_ids[:items_size] = \
                            hf_config.image_token_index

                        placeholders_ids = placeholders_ids.to(self.device)
1370
1371
1372
1373

                        mm_mask = torch.tensor([False] * num_tokens)
                        mm_mask[:items_size] = True
                        mm_mask = mm_mask.to(self.device)
1374
                        # Assign outputs or the graph will be cut short.
1375
1376
1377
1378
                        a, b = self._get_model_inputs(
                            placeholders_ids,
                            mm_embed_inputs=([mm_embeds], mm_mask),
                        )
1379
                        assert a is None
1380
                        torch_xla.sync(wait=False)
1381
1382
1383
1384
1385
1386
1387
1388

            # Pre-compile `get_input_embeddings` when mm_embeddings are not
            # present. Chunk is only made of text, no mm_placeholders.
            for num_tokens in self.num_tokens_paddings:
                placeholders_ids = torch.zeros(num_tokens,
                                               dtype=torch.int32,
                                               device="cpu")
                placeholders_ids = placeholders_ids.to(self.device)
1389
1390
1391
1392
                a, b = self._get_model_inputs(
                    placeholders_ids,
                    mm_embed_inputs=None,
                )
1393
                assert a is None
1394
                torch_xla.sync(wait=False)
1395
1396
1397
1398
1399
1400
1401

            xm.wait_device_ops()
            end = time.perf_counter()
            logger.info(
                "Multimodal %s Encoder compilation finished in in %.2f "
                "[secs].", mode, end - start)

1402
    def _precompile_backbone(self) -> None:
1403
1404
        logger.info("Compiling the model with different input shapes.")
        start = time.perf_counter()
1405
        for num_tokens in self.num_tokens_paddings:
1406
            logger.info("  -- num_tokens: %d", num_tokens)
1407
1408
1409
1410
1411
            self._dummy_run(num_tokens, self.num_reqs_max_model_len,
                            self.max_num_blocks_per_req)
            if self.most_model_len is not None:
                self._dummy_run(num_tokens, self.num_reqs_most_model_len,
                                self.num_blocks_per_most_len_req)
1412
1413
        xm.wait_device_ops()
        end = time.perf_counter()
1414
        logger.info("Compilation finished in %.2f [secs].", end - start)
1415
        self._update_num_xla_graphs("model backbone")
1416

1417
1418
1419
1420
1421
    def _precompile_select_hidden_states(self) -> None:
        # Compile hidden state selection function for bucketed
        # n_tokens x max_num_reqs. Graph is really small so this is fine.
        logger.info(
            "Compiling select_hidden_states with different input shapes.")
1422
1423
        start = time.perf_counter()
        hsize = self.model_config.get_hidden_size()
1424
        for num_tokens in self.num_tokens_paddings:
1425
1426
            dummy_hidden = torch.zeros((num_tokens, hsize),
                                       device=self.device,
1427
                                       dtype=self._hidden_states_dtype)
1428
1429
1430
1431
1432
1433
1434
            torch._dynamo.mark_dynamic(dummy_hidden, 0)
            for num_reqs in self.num_reqs_paddings:
                indices = torch.zeros(num_reqs,
                                      dtype=torch.int32,
                                      device=self.device)
                torch._dynamo.mark_dynamic(indices, 0)
                self.select_hidden_states(dummy_hidden, indices)
1435
1436
1437
1438
1439
1440
                logger.info("  -- num_tokens: %d, num_seqs: %d", num_tokens,
                            num_reqs)
                # Requests can't be more than tokens. But do compile for the
                # next bigger value in case num_tokens uses bucketed padding.
                if num_reqs >= min(num_tokens, self.max_num_reqs):
                    break
1441
        xm.wait_device_ops()
1442
        end = time.perf_counter()
1443
        logger.info("Compilation finished in %.2f [secs].", end - start)
1444
        self._update_num_xla_graphs("select_hidden_states")
1445

1446
1447
    def _precompile_compute_logits(self) -> None:
        logger.info("Compiling compute_logits with different input shapes.")
1448
1449
1450
1451
1452
1453
        start = time.perf_counter()
        hsize = self.model_config.get_hidden_size()
        for num_reqs in self.num_reqs_paddings:
            dummy_hidden = torch.zeros((num_reqs, hsize),
                                       device=self.device,
                                       dtype=self._hidden_states_dtype)
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
            torch._dynamo.mark_dynamic(dummy_hidden, 0)
            self.compute_logits(dummy_hidden)
            logger.info("  -- num_seqs: %d", num_reqs)
        xm.wait_device_ops()
        end = time.perf_counter()
        logger.info("Compilation finished in %.2f [secs].", end - start)
        self._update_num_xla_graphs("compute_logits")

    def _precompile_structured_decoding(self) -> None:
        logger.info(
            "Compiling structured_decoding with different input shapes.")
        start = time.perf_counter()
        for num_reqs in self.num_reqs_paddings:
            dummy_logits = torch.zeros((num_reqs, self.vocab_size),
                                       device=self.device,
                                       dtype=self._hidden_states_dtype)
            dummy_require_struct_decoding = \
                self.require_structured_out_cpu[:num_reqs].to(self.device)
            dummy_grammar_bitmask = \
                self.grammar_bitmask_cpu[:num_reqs].to(self.device)
            # The first dimension of the above 3 dummy tensors cannot be
            # mark_dynamic because some operations in structured_decode require
            # them to be static.
            arange = self.structured_decode_arange.to(self.device)
            self.structured_decode(dummy_require_struct_decoding,
                                   dummy_grammar_bitmask, dummy_logits, arange)
            logger.info("  -- num_seqs: %d", num_reqs)
        xm.wait_device_ops()
        end = time.perf_counter()
        logger.info("Compilation finished in %.2f [secs].", end - start)
        self._update_num_xla_graphs("structured_decoding")

    def _precompile_sample_from_logits(self) -> None:
        logger.info(
            "Compiling sample_from_logits with different input shapes.")
        start = time.perf_counter()
        for num_reqs in self.num_reqs_paddings:
            dummy_logits = torch.zeros((num_reqs, self.vocab_size),
                                       device=self.device,
                                       dtype=self._hidden_states_dtype)
            # The first dimension of dummy_logits cannot be mark_dynamic
            # because some operations in the sampler require it to be static.
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
            for all_greedy in [False, True]:
                generate_params_if_all_greedy = not all_greedy
                sampling_metadata = (
                    TPUSupportedSamplingMetadata.from_input_batch(
                        self.input_batch,
                        num_reqs,
                        self.device,
                        generate_params_if_all_greedy,
                    ))
                sampling_metadata.all_greedy = all_greedy
1506
1507
1508
                with self.maybe_select_dummy_loras(
                        self.lora_config, np.array([num_reqs],
                                                   dtype=np.int32)):
1509
1510
                    self.sample_from_logits_func(dummy_logits,
                                                 sampling_metadata)
1511
1512
1513
            logger.info("  -- num_seqs: %d", num_reqs)
        xm.wait_device_ops()
        end = time.perf_counter()
1514
1515
        logger.info("Compilation finished in %.2f [secs].", end - start)
        self._update_num_xla_graphs("sample_from_logits")
1516

1517
1518
1519
1520
1521
1522
1523
1524
1525
    def _precompile_gather_logprobs(self) -> None:
        logger.info("Compiling gather_logprobs with different input shapes.")
        start = time.perf_counter()
        for num_reqs in self.num_reqs_paddings:
            dummy_logits = torch.zeros((num_reqs, self.vocab_size),
                                       device=self.device,
                                       dtype=self._hidden_states_dtype)
            dummy_tokens = torch.zeros((num_reqs, 1),
                                       dtype=torch.int64).to(self.device)
1526
1527
1528
            with self.maybe_select_dummy_loras(
                    self.lora_config, np.array([num_reqs], dtype=np.int32)):
                self.gather_logprobs(dummy_logits, dummy_tokens)
1529
1530
1531
1532
1533
1534
            logger.info("  -- num_seqs: %d", num_reqs)
        xm.wait_device_ops()
        end = time.perf_counter()
        logger.info("Compilation finished in %.2f [secs].", end - start)
        self._update_num_xla_graphs("gather_logprobs")

1535
1536
1537
1538
    def capture_model(self) -> None:
        """
        Precompile all the subgraphs with possible input shapes.
        """
1539
1540
1541
1542
1543
1544
1545
1546
        with self.maybe_setup_dummy_loras(self.lora_config):
            self._precompile_mm_encoder()
            self._precompile_backbone()
            self._precompile_select_hidden_states()
            self._precompile_compute_logits()
            self._precompile_structured_decoding()
            self._precompile_sample_from_logits()
            self._precompile_gather_logprobs()
1547

1548
1549
1550
1551
1552
    def profile_run(
        self,
        num_tokens: int,
    ) -> None:
        # Profile with multimodal encoder & encoder cache.
1553
        if self.supports_mm_inputs:
1554
            if self.model_config.multimodal_config.skip_mm_profiling:
1555
                logger.info(
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
                    "Skipping memory profiling for multimodal encoder and "
                    "encoder cache.")
            else:
                mm_budget = self.mm_budget
                assert mm_budget is not None

                # TODO: handle encoder-decoder models once we support them.
                if (encoder_budget := mm_budget.get_encoder_budget()) > 0:
                    # NOTE: Currently model is profiled with a single non-text
                    # modality with the max possible input tokens even when
                    # it supports multiple.
1567
1568
1569
                    dummy_modality = mm_budget.get_modality_with_max_tokens()
                    max_mm_items_per_batch = mm_budget \
                        .max_items_per_batch_by_modality[dummy_modality]
1570
1571
1572
1573
1574
1575
1576
1577
1578

                    logger.info(
                        "Encoder cache will be initialized with a budget of "
                        "%s tokens, and profiled with %s %s items of the "
                        "maximum feature size.",
                        encoder_budget,
                        max_mm_items_per_batch,
                        dummy_modality,
                    )
1579

1580
1581
1582
1583
1584
                    # Create dummy batch of multimodal inputs.
                    batched_dummy_mm_inputs = self._get_mm_dummy_batch(
                        dummy_modality,
                        max_mm_items_per_batch,
                    )
1585

1586
1587
1588
1589
                    # Run multimodal encoder.
                    # Isolate encoder graph from post-processing to minimize
                    # impact of recompilation until it's fixed.
                    start = time.perf_counter()
1590
                    torch_xla.sync(wait=False)
1591
1592
1593
                    dummy_encoder_outputs = \
                        self.model.get_multimodal_embeddings(
                        **batched_dummy_mm_inputs)
1594
                    torch_xla.sync(wait=False)
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
                    xm.wait_device_ops()
                    end = time.perf_counter()
                    logger.info(
                        "Multimodal Encoder profiling finished in %.2f [secs].",
                        end - start)

                    sanity_check_mm_encoder_outputs(
                        dummy_encoder_outputs,
                        expected_num_items=max_mm_items_per_batch,
                    )
1605

1606
1607
1608
                    # Cache the dummy encoder outputs.
                    self.encoder_cache["tmp"] = dict(
                        enumerate(dummy_encoder_outputs))
1609
1610

        # Trigger compilation for general shape.
1611
1612
1613
1614
1615
        self._dummy_run(num_tokens, self.num_reqs_max_model_len,
                        self.max_num_blocks_per_req)
        if self.most_model_len is not None:
            self._dummy_run(num_tokens, self.num_reqs_most_model_len,
                            self.num_blocks_per_most_len_req)
1616

1617
        torch_xla.sync(wait=False)
1618
1619
1620
1621
        xm.wait_device_ops()
        self.encoder_cache.clear()
        gc.collect()

1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
    def maybe_setup_cross_layer_kv_sharing(
        self,
        kv_caches: dict[str, torch.Tensor],
        kv_cache_config: KVCacheConfig,
    ) -> None:
        """
        Add layers that re-use KV cache to KV cache group of its target layer.
        Mapping of KV cache tensors happens in `initialize_kv_cache_tensors()`
        """
        if not self.shared_kv_cache_layers:
            # No cross-layer KV sharing, return
            return

        add_kv_sharing_layers_to_kv_cache_groups(
            self.shared_kv_cache_layers,
            kv_cache_config.kv_cache_groups,
        )

        for layer_name, target_layer_name in self.shared_kv_cache_layers.items(
        ):
            logger.debug("%s reuses KV cache of %s", layer_name,
                         target_layer_name)
            kv_caches[layer_name] = kv_caches[target_layer_name]

1646
1647
1648
1649
    def initialize_kv_cache(self, kv_cache_config: KVCacheConfig) -> None:
        """
        Initialize KV cache based on `kv_cache_config`.
        Args:
1650
            kv_cache_config: Configuration for the KV cache, including the KV
1651
1652
            cache size of each layer
        """
1653
        if len(kv_cache_config.kv_cache_groups) > 1:
1654
1655
1656
1657
            raise NotImplementedError(
                "Hybrid models with more than one KV cache type are not "
                "supported yet.")

1658
1659
1660
1661
1662
1663
1664
1665
1666
        if kv_cache_config.kv_cache_groups[
                0].kv_cache_spec.block_size != self.block_size:
            self.input_batch = InputBatch(
                max_num_reqs=self.max_num_reqs,
                max_model_len=self.max_model_len,
                max_num_batched_tokens=self.max_num_tokens,
                device=self.device,
                pin_memory=self.pin_memory,
                vocab_size=self.model_config.get_vocab_size(),
1667
1668
1669
                block_sizes=[
                    kv_cache_config.kv_cache_groups[0].kv_cache_spec.block_size
                ],
1670
1671
            )
        # Verify dtype compatibility between block_table_cpu and input_batch
1672
1673
1674
        assert self.block_table_cpu.dtype == self.input_batch.block_table[
            0].get_cpu_tensor().dtype

1675
1676
1677
1678
1679
1680
        kv_cache_sizes = {}
        for kv_cache_tensor in kv_cache_config.kv_cache_tensors:
            assert len(kv_cache_tensor.shared_by) == 1, (
                "KV cache tensor shared by multiple layers is not supported in "
                "TPU.")
            kv_cache_sizes[kv_cache_tensor.shared_by[0]] = kv_cache_tensor.size
1681

1682
        kv_caches: dict[str, torch.Tensor] = {}
1683
1684
1685
        for kv_cache_group in kv_cache_config.kv_cache_groups:
            kv_cache_spec = kv_cache_group.kv_cache_spec
            for layer_name in kv_cache_group.layer_names:
1686
1687
1688
                tensor_size = kv_cache_sizes[layer_name]
                assert tensor_size % kv_cache_spec.page_size_bytes == 0
                num_blocks = tensor_size // kv_cache_spec.page_size_bytes  # noqa
1689
                if isinstance(kv_cache_spec, AttentionSpec):
1690
1691
1692
1693
1694
1695
1696
1697
1698
                    if self.use_spmd:
                        num_kv_heads = kv_cache_spec.num_kv_heads
                        assert self.original_parallel_config is not None
                        tp_size = \
                            self.original_parallel_config.tensor_parallel_size
                        # TODO: Handle kv cache duplication under SPMD mode.
                        assert num_kv_heads % tp_size == 0, (
                            f"num_kv_heads {num_kv_heads} must be divisible by "
                            f"tp_size {tp_size} under SPMD mode")
1699
1700
1701
1702
1703
                    kv_cache_shape = PallasAttentionBackend.get_kv_cache_shape(
                        num_blocks, kv_cache_spec.block_size,
                        kv_cache_spec.num_kv_heads, kv_cache_spec.head_size)
                    dtype = kv_cache_spec.dtype

1704
                    tpu_kv_cache = torch.zeros(kv_cache_shape,
1705
                                               dtype=dtype).to(self.device)
1706

1707
                    kv_caches[layer_name] = tpu_kv_cache
1708
1709
                else:
                    raise NotImplementedError
1710

1711
1712
        # Set up cross-layer KV cache sharing if needed
        self.maybe_setup_cross_layer_kv_sharing(kv_caches, kv_cache_config)
1713

1714
1715
1716
1717
1718
        bind_kv_cache(
            kv_caches,
            self.vllm_config.compilation_config.static_forward_context,
            self.kv_caches)

1719
1720
1721
1722
1723
        if self.use_spmd:
            # Shard KV Cache
            for cache in self.kv_caches:
                xs.mark_sharding(cache, self.mesh, (None, 'x', None, None))

1724
1725
1726
1727
        if has_kv_transfer_group():
            get_kv_transfer_group().register_kv_caches(kv_caches)
            get_kv_transfer_group().set_host_xfer_buffer_ops(copy_kv_blocks)

1728
    def reset_dynamo_cache(self):
1729
1730
1731
1732
1733

        # NOTE: We check `is_multimodal_model` instead of `supports_mm_inputs`
        # since the compiled model object of the language backbone of a
        # multimodal model needs to be extracted via `get_language_model`.
        if self.model_config.is_multimodal_model:
1734
            compiled_model = self.model.get_language_model().model
1735
1736
1737
1738
1739
1740
1741
        else:
            compiled_model = self.model.model
        if isinstance(compiled_model, TorchCompileWrapperWithCustomDispatcher):
            logger.info("Clear dynamo cache and cached dynamo bytecode.")
            torch._dynamo.eval_frame.remove_from_cache(
                compiled_model.original_code_object)
            compiled_model.compiled_codes.clear()
1742

1743
1744
1745
1746
1747
    @torch.compile(backend="openxla", fullgraph=True, dynamic=False)
    def select_hidden_states(self, hidden_states, indices_do_sample):
        return hidden_states[indices_do_sample]

    @torch.compile(backend="openxla", fullgraph=True, dynamic=False)
1748
1749
    def compute_logits(self,
                       sample_hidden_states: torch.Tensor) -> torch.Tensor:
1750
        return self.model.compute_logits(sample_hidden_states)
1751

1752
1753
1754
    # TODO: Under SPMD mode, sample_from_logits has correctness issue.
    #       Re-enable the torch.compile once the issue is fixed in torchxla.
    # @torch.compile(backend="openxla", fullgraph=True, dynamic=False)
1755
1756
1757
    def sample_from_logits(
            self, logits: torch.Tensor,
            sampling_metadata: TPUSupportedSamplingMetadata) -> torch.Tensor:
1758
1759
1760
1761
        """
        Sample with xla-friendly function. This function is to be traced 
        separately from `forward` for lighter compilation overhead.
        """
1762
1763
1764
1765
1766
        if sampling_metadata.all_greedy:
            out_tokens = torch.argmax(logits, dim=-1, keepdim=True)
        else:
            out_tokens = self.sampler(logits,
                                      sampling_metadata).sampled_token_ids
1767
1768
        return out_tokens

1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
    @torch.compile(backend="openxla", fullgraph=True, dynamic=False)
    def gather_logprobs(self, logits: torch.Tensor,
                        sampled_tokens: torch.Tensor) -> LogprobsTensors:
        """
        Gather the top_logprobs with corresponding tokens. Use a fixed number
        of logprobs as an alternative to having multiple pre-compiled graphs.
        Select the number of logprobs actually demanded by each request on CPU.
        """
        logprobs = self.sampler.compute_logprobs(logits)
        return self.sampler.gather_logprobs(
            logprobs,
            self.model_config.max_logprobs,
            token_ids=sampled_tokens.squeeze(-1))

1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
    @torch.compile(backend="openxla", fullgraph=True, dynamic=False)
    def structured_decode(self, require_struct_decoding: torch.Tensor,
                          grammar_bitmask: torch.Tensor, logits: torch.Tensor,
                          arange: torch.Tensor) -> torch.Tensor:
        return torch.where(
            require_struct_decoding,
            self.apply_grammar_bitmask(logits, grammar_bitmask, arange),
            logits)

    def apply_grammar_bitmask(self, logits: torch.Tensor,
                              grammar_bitmask: torch.Tensor,
                              arange: torch.Tensor):
        assert (logits.shape[0] == grammar_bitmask.shape[0])
        logits_cloned = logits.clone()
        for i in range(logits.shape[0]):
            unpacked_bitmask = (torch.bitwise_right_shift(
                grammar_bitmask[i][:, None], arange[None, :]) & 1) == 0
            unpacked_bitmask = unpacked_bitmask.reshape(-1)[:self.vocab_size]
            logits_cloned[i] = logits_cloned[i].masked_fill(
                unpacked_bitmask, -float("inf"))
        return logits_cloned

1805
1806
    def get_multimodal_embeddings(self, *args, **kwargs):
        return self.model.get_multimodal_embeddings(*args, **kwargs)
1807

1808
1809
1810
    def get_input_embeddings(self, *args, **kwargs):
        return self.model.get_input_embeddings(*args, **kwargs)

1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
    def prepare_structured_decoding_input(
        self, logits: torch.Tensor, scheduler_output: "SchedulerOutput"
    ) -> tuple[torch.Tensor, torch.Tensor, torch.Tensor]:
        grammar_bitmask = scheduler_output.grammar_bitmask
        assert grammar_bitmask is not None
        num_reqs, _ = logits.shape

        # Reset pre-allocated tensors
        self.grammar_bitmask_cpu.zero_()
        self.require_structured_out_cpu.zero_()

1822
1823
1824
1825
1826
1827
        sorted_struct_requests = sorted(
            scheduler_output.structured_output_request_ids.items(),
            key=lambda item: item[1])
        cumulative_mask_idx = 0
        for req_id, _ in sorted_struct_requests:
            if req_id not in self.input_batch.req_id_to_index:
1828
1829
                continue
            batch_index = self.input_batch.req_id_to_index[req_id]
1830
1831
1832
1833
1834
1835
1836
1837
            self.grammar_bitmask_cpu[batch_index] = torch.from_numpy(
                grammar_bitmask[cumulative_mask_idx])
            # It's not guaranteed that all requests in this batch require
            # structured output, so create a bool tensor to represent
            # the requests that need structured output.
            self.require_structured_out_cpu[batch_index] = True
            cumulative_mask_idx += 1

1838
1839
1840
1841
        return self.require_structured_out_cpu[:num_reqs].to(logits.device), \
            self.grammar_bitmask_cpu[:num_reqs].to(logits.device), \
            self.structured_decode_arange.to(logits.device)

1842
1843
1844
1845
1846
1847
    def _get_mm_dummy_batch(
        self,
        modality: str,
        max_items_per_batch: int,
    ) -> BatchedTensorInputs:
        """Dummy data for profiling and precompiling multimodal models."""
1848
1849
        assert self.mm_budget is not None

1850
        dummy_decoder_data = self.mm_registry.get_decoder_dummy_data(
1851
            model_config=self.model_config,
1852
            seq_len=self.max_model_len,
1853
            mm_counts={modality: 1},
1854
            cache=self.mm_budget.cache,
1855
        )
1856
1857
1858
        dummy_mm_data = dummy_decoder_data.multi_modal_data

        # Result in the maximum GPU consumption of the model
1859
1860
        dummy_mm_item = dummy_mm_data[modality][0]
        dummy_mm_items = [dummy_mm_item] * max_items_per_batch
1861

1862
        model = cast(SupportsMultiModal, self.model)
1863
1864
        return next(grouped_mm_kwargs
                    for _, _, grouped_mm_kwargs in group_mm_kwargs_by_modality(
1865
                        dummy_mm_items,
1866
1867
                        device=self.device,
                        pin_memory=self.pin_memory,
1868
                        merge_by_field_config=model.merge_by_field_config,
1869
                    ))
1870

1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882

def _get_req_paddings(min_req_size: int, max_req_size: int) -> list[int]:
    logger.info("Preparing request paddings:")
    # assert min_req_size is power of 2
    assert (min_req_size & (min_req_size - 1) == 0) and min_req_size > 0
    paddings: list = []
    num = max(MIN_NUM_SEQS, min_req_size)
    while num <= max_req_size and (len(paddings) == 0 or paddings[-1] != num):
        paddings.append(num)
        logger.info("    %d", num)
        num = _get_padded_num_reqs_with_upper_limit(num + 1, max_req_size)
    return paddings
1883
1884


1885
def _get_padded_num_reqs_with_upper_limit(x: int, upper_limit: int) -> int:
1886
    res = MIN_NUM_SEQS if x <= MIN_NUM_SEQS else 1 << (x - 1).bit_length()
1887
    return min(res, upper_limit)
1888
1889


1890
1891
def _get_token_paddings(min_token_size: int, max_token_size: int,
                        padding_gap: int) -> list[int]:
1892
1893
    """Generate a list of padding size, starting from min_token_size, 
    ending with a number that can cover max_token_size
1894

1895
1896
1897
    If padding_gap == 0 then:
        increase 2X each time (exponential)
    else:
1898
        first increase the size to twice,
1899
        then increase the padding size by padding_gap.
1900
    """
1901
1902
    # assert min_token_size is power of 2
    assert (min_token_size & (min_token_size - 1) == 0) and min_token_size > 0
1903
1904
    paddings = []
    num = min_token_size
1905
1906

    if padding_gap == 0:
1907
        logger.info("Using exponential token paddings:")
1908
        while True:
1909
1910
            logger.info("    %d", num)
            paddings.append(num)
1911
1912
            if num >= max_token_size:
                break
1913
1914
            num *= 2
    else:
1915
        logger.info("Using incremental token paddings:")
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
        while num <= padding_gap:
            logger.info("    %d", num)
            paddings.append(num)
            num *= 2
        num //= 2
        while num < max_token_size:
            num += padding_gap
            logger.info("    %d", num)
            paddings.append(num)

1926
1927
1928
1929
1930
1931
1932
1933
1934
    return paddings


def _get_padded_token_len(paddings: list[int], x: int) -> int:
    """Return the first element in paddings list greater or equal to x.
    """
    index = bisect.bisect_left(paddings, x)
    assert index < len(paddings)
    return paddings[index]
1935
1936


1937
1938
def _get_padded_num_kv_cache_update_slices(num_tokens: int, max_num_reqs: int,
                                           page_size: int) -> int:
1939
1940
    """Calculates the padded number of KV cache update slices to avoid
    recompilation."""
1941
1942
1943
1944
1945
    # NOTE(chengjiyao): let's say R_i is the token num for i-th request,
    # so it occupies most 2 + R_i // page_size pages. The total maximum
    # possible number of pages needed is sum(2 + R_i // page_size), which
    # is <= 2 * max_num_reqs + sum(R_i) // page_size
    # = 2 * max_num_reqs + num_tokens // page_size
1946
1947
1948
1949
1950
    padded_num_slices = 2 * max_num_reqs + num_tokens // page_size
    padded_num_slices = min(padded_num_slices, num_tokens)
    return padded_num_slices


1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
def _get_num_slices_per_kv_cache_update_block(page_size_bytes: int) -> int:
    """Find the optimum number of slices to copy per Pallas program instance.

    Increasing the number of slices copied in one instance of the kernel program
    will increase HBM bandwidth utilization via more in-flight DMAs.

    However, it will also use more VMEM, and experimentally, we observed
    performance regression at 128 slices on v6e, likely due to running
    out of scalar registers. Thus this function will limit the number of
    slices to 64.
    """
1962
1963
1964
    # The default vmem_limit_bytes of a pallas kernel is 32MB. Here we
    # calculate num_slices_per_block based on 16MB in case any register spills.
    vmem_limit = 16 * 1024 * 1024
1965
1966
1967
1968
1969
1970
1971
1972
    num_slices_per_block = vmem_limit // page_size_bytes
    assert num_slices_per_block > 0, "Number of slices should be positive"
    num_slices_per_block = prev_power_of_2(num_slices_per_block)
    if num_slices_per_block > 64:
        num_slices_per_block = 64
    return num_slices_per_block


1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
def replace_set_lora(model):

    def _tpu_set_lora(
        self,
        index: int,
        lora_a: torch.Tensor,
        lora_b: torch.Tensor,
        embeddings_tensor: Optional[torch.Tensor],
        bias: Optional[torch.Tensor] = None,
    ):
        # TODO: The integer index leads to a recompilation, but converting it
        # to a tensor doesn't seem to work anymore. This might be fixed with a
        # later release of torch_xla.
        self._original_set_lora(index, lora_a, lora_b, embeddings_tensor, bias)
1987
        torch_xla.sync(wait=False)
1988
1989
1990

    def _tpu_reset_lora(self, index: int):
        self._original_reset_lora(index)
1991
        torch_xla.sync(wait=False)
1992
1993
1994
1995
1996
1997
1998
1999

    for _, module in model.named_modules():
        if isinstance(module, BaseLayerWithLoRA):
            module._original_set_lora = module.set_lora
            module._original_reset_lora = module.reset_lora
            module.set_lora = _tpu_set_lora.__get__(module, module.__class__)
            module.reset_lora = _tpu_reset_lora.__get__(
                module, module.__class__)