processing.py 61.7 KB
Newer Older
1
# SPDX-License-Identifier: Apache-2.0
2
# SPDX-FileCopyrightText: Copyright contributors to the vLLM project
3
from abc import ABC, abstractmethod
4
from collections import defaultdict
5
6
from collections.abc import (Callable, Generator, ItemsView, Iterable, Mapping,
                             Sequence)
7
from dataclasses import dataclass, field, replace
8
from enum import Enum
9
from functools import lru_cache
10
from typing import (TYPE_CHECKING, Generic, NamedTuple, Optional, Protocol,
11
                    TypeVar, Union, cast)
12

13
import regex as re
14
import torch
15
from typing_extensions import assert_never
16

17
from vllm.inputs import InputProcessingContext
18
from vllm.logger import init_logger
19
20
from vllm.transformers_utils.tokenizer import (AnyTokenizer, decode_tokens,
                                               encode_tokens)
21
from vllm.utils import flatten_2d_lists, full_groupby
22

23
from .hasher import MultiModalHasher
24
from .inputs import (MultiModalDataDict, MultiModalEncDecInputs,
25
26
                     MultiModalFieldConfig, MultiModalInputs,
                     MultiModalKwargsItem, MultiModalKwargsItems,
27
                     MultiModalKwargsOptionalItems, PlaceholderRange)
28
29
from .parse import (DictEmbeddingItems, EmbeddingItems, MultiModalDataItems,
                    MultiModalDataParser)
30
31

if TYPE_CHECKING:
32
33
34
35
    from transformers.configuration_utils import PretrainedConfig
    from transformers.feature_extraction_utils import BatchFeature
    from transformers.processing_utils import ProcessorMixin

36
    from .cache import BaseMultiModalProcessorCache
37
    from .profiling import BaseDummyInputsBuilder
38

39
logger = init_logger(__name__)
40
41

_S = TypeVar("_S", str, list[int])
42
43
44

PromptSeq = Union[str, list[int]]
"""A token sequence (list of token IDs) or text."""
45

46

47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
@lru_cache(maxsize=2048)
def _cached_encode(
    tokenizer: AnyTokenizer,
    text: str,
    *,
    add_special_tokens: Optional[bool] = None,
) -> list[int]:
    return encode_tokens(tokenizer,
                         text,
                         add_special_tokens=add_special_tokens)


@lru_cache(maxsize=2048)
def _cached_decode(
    tokenizer: AnyTokenizer,
    token_ids: tuple[int, ...],
    *,
    skip_special_tokens: Optional[bool] = None,
) -> str:
    return decode_tokens(tokenizer,
                         list(token_ids),
                         skip_special_tokens=skip_special_tokens)


def _seq2text(tokenizer: AnyTokenizer, seq: PromptSeq) -> str:
    if isinstance(seq, str):
        return seq

    return _cached_decode(tokenizer, tuple(seq))


def _seq2tokens(tokenizer: AnyTokenizer, seq: PromptSeq) -> list[int]:
    if isinstance(seq, str):
        return _cached_encode(tokenizer, seq, add_special_tokens=False)

    return seq


85
86
87
88
89
90
91
92
93
94
95
class _GetMatchIndex(Protocol):

    def __call__(
        self,
        tokenizer: AnyTokenizer,
        prompt: PromptSeq,
        start_idx: int = 0,
    ) -> Optional[int]:
        ...


96
97
98
@dataclass
class PromptIndex:
    """Resolves to an index in the prompt."""
99
    get_match_index: _GetMatchIndex
100
101
102
103
104
105
106
107
108
109
110


class PromptIndexTargets:

    @staticmethod
    def start() -> PromptIndex:
        """
        Resolves to the start of the prompt (before the first token).

        This results in a match even if the prompt is empty.
        """
111
        return PromptIndex(lambda tokenizer, prompt, start_idx=0: 0)
112
113
114
115
116
117
118
119
120
121

    @staticmethod
    def prefix(seq: PromptSeq) -> PromptIndex:
        """
        Resolves to a location in the prompt after the given prefix.
        """

        def get_match_index(
            tokenizer: AnyTokenizer,
            prompt: PromptSeq,
122
            start_idx: int = 0,
123
        ) -> Optional[int]:
124
125
126
            if start_idx != 0:
                return None

127
128
129
130
131
132
133
134
135
            prefix = seq

            if isinstance(prompt, str):
                if not isinstance(prefix, str):
                    # Make both `str`
                    prefix = decode_tokens(tokenizer, prefix)
            else:
                if isinstance(prefix, str):
                    # Make both `list[int]`
136
137
138
                    prefix = encode_tokens(tokenizer,
                                           prefix,
                                           add_special_tokens=False)
139
140
141
142
143
144
145
146
147
148
149
150
151

            match_idx = len(prefix)
            return match_idx if prompt[:match_idx] == prefix else None

        return PromptIndex(get_match_index)

    @staticmethod
    def end() -> PromptIndex:
        """
        Resolves to the end of the prompt (after the last token).

        This results in a match even if the prompt is empty.
        """
152
        return PromptIndex(lambda tokenizer, prompt, start_idx=0: len(prompt))
153
154


155
UpdateTarget = Union[PromptSeq, PromptIndex]
156
157
158
159
"""
The token sequence or text to update.
"""

160
161
162
163
164
165
166
167
168
169
PromptUpdateTarget = Union[Callable[[int], UpdateTarget], UpdateTarget]
"""
Given the index of the processed item within
[`modality`][vllm.multimodal.processing.PromptUpdate.modality],
output the corresponding token sequence (or text).

For convenience, you can directly pass in the token sequence (or text)
instead of a function if it does not depend on the input.
"""

170

171
@dataclass
172
class PromptUpdateDetails(Generic[_S]):
173
    """Details about the token sequence or text that are part of the update."""
174

175
    full: _S
176
    """The full content."""
177

178
179
    is_embed: Optional[Callable[[AnyTokenizer, PromptSeq],
                                torch.Tensor]] = None
180
    """
181
182
183
    Given [`full`][vllm.multimodal.processing.PromptUpdateDetails.full],
    return a boolean mask of shape `(len(full),)` indicating which positions
    of `full` to assign embeddings to.
184
185
186
187

    `None` (default) means to assign embeddings to all positions of `full`.

    The embeddings are obtained by calling
188
    [`SupportsMultiModal.get_multimodal_embeddings`][vllm.model_executor.models.interfaces.SupportsMultiModal.get_multimodal_embeddings].
189
190
191
    """

    @staticmethod
192
    def from_seq(seq: _S) -> "PromptUpdateDetails[_S]":
193
194
195
196
197
198
199
200
        return PromptUpdateDetails(full=seq)

    @staticmethod
    def select_text(
        seq: _S,
        embed_text: str,
    ) -> "PromptUpdateDetails[_S]":

201
202
203
        def is_embed(tokenizer: AnyTokenizer, full: PromptSeq) -> torch.Tensor:
            embed_token_ids = encode_tokens(tokenizer, embed_text)
            token_ids = _seq2tokens(tokenizer, full)
204
205

            return torch.isin(
206
                torch.tensor(token_ids),
207
208
209
210
211
212
213
214
215
216
                torch.tensor(embed_token_ids),
            )

        return PromptUpdateDetails(full=seq, is_embed=is_embed)

    @staticmethod
    def select_token_id(
        seq: _S,
        embed_token_id: int,
    ) -> "PromptUpdateDetails[_S]":
217
218
219
220
221
222
223

        def is_embed(tokenizer: AnyTokenizer, full: PromptSeq) -> torch.Tensor:
            token_ids = _seq2tokens(tokenizer, full)

            return torch.tensor(token_ids) == embed_token_id

        return PromptUpdateDetails(full=seq, is_embed=is_embed)
224
225


226
PromptUpdateInfo = Union[PromptSeq, PromptUpdateDetails]
227
"""
228
The token sequence or text that are part of the update.
229

230
If only part of the content corresponds to feature placeholders, you can
231
232
use [`PromptUpdateDetails`][vllm.multimodal.processing.PromptUpdateDetails] to
specify which part.
233
"""
234

235
236
237
PromptUpdateContent = Union[Callable[[int], PromptUpdateInfo],
                            PromptUpdateInfo]
"""
238
239
Given the index of the processed item within
[`modality`][vllm.multimodal.processing.PromptUpdate.modality],
240
241
242
243
244
245
246
247
248
249
250
251
252
output the corresponding token sequence (or text).

For convenience, you can directly pass in the token sequence (or text)
instead of a function if it does not depend on the input.
"""


class UpdateMode(str, Enum):
    INSERT = "insert"
    REPLACE = "replace"


@dataclass
253
class PromptUpdate(ABC):
254
255
256
257
258
259
260
    """
    Defines how to update a prompt with placeholder tokens.
    """

    modality: str
    """The modality for which the update is made."""

261
    target: PromptUpdateTarget
262
263
264
265
266
267
268
269
270
271
272
273
274
275
    """The token sequence (or text) to update."""

    @property
    @abstractmethod
    def content(self) -> PromptUpdateContent:
        """The placeholder tokens that are part of the update."""
        raise NotImplementedError

    @property
    @abstractmethod
    def mode(self) -> UpdateMode:
        """Defines how to update the prompt."""
        raise NotImplementedError

276
    def _resolve_target(self, item_idx: int) -> UpdateTarget:
277
278
279
280
        target = self.target
        if callable(target):
            target = target(item_idx)

281
        return target
282

283
    def _resolve_content(self, item_idx: int) -> PromptUpdateDetails:
284
285
286
287
288
289
290
        content = self.content
        if callable(content):
            content = content(item_idx)

        if not isinstance(content, PromptUpdateDetails):
            content = PromptUpdateDetails.from_seq(content)

291
        return content
292

293
    def resolve(self, item_idx: int) -> "ResolvedPromptUpdate":
294
295
296
297
298
299
300
301
302
        """
        Given the index of the processed item within
        [`modality`][vllm.multimodal.processing.PromptUpdate.modality],
        output a copy of this object with its lazy attributes resolved.
        """
        return ResolvedPromptUpdate(
            modality=self.modality,
            item_idx=item_idx,
            mode=self.mode,
303
304
            target=self._resolve_target(item_idx),
            content=self._resolve_content(item_idx),
305
306
        )

307

308
@dataclass
309
310
311
312
313
314
class PromptInsertion(PromptUpdate):
    """
    Defines how to insert placeholder tokens into a prompt.

    Example:

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
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
    For each image, insert a number of ``<image>`` feature placeholders
    equal to the feature size of the vision encoder after the ``<s>`` token:

    ```python
    PromptInsertion(
        modality="image",
        target="<s>",
        insertion="<image>" * image_feature_size,
    )
    ```

    Insert these tokens at the start of the prompt:

    ```python
    PromptInsertion(
        modality="image",
        target=PromptIndexTargets.start(),
        insertion="<image>" * image_feature_size,
    )
    ```

    Insert these tokens after a prefix ``Images:``:

    ```python
    PromptInsertion(
        modality="image",
        target=PromptIndexTargets.prefix("Images:"),
        insertion="<image>" * image_feature_size,
    )
    ```

    Insert these tokens at the end of the prompt:

    ```python
    PromptInsertion(
        modality="image",
        target=PromptIndexTargets.end(),
        insertion="<image>" * image_feature_size,
    )
    ```
355
356
357
358
    """

    insertion: PromptUpdateContent = field(repr=False)
    """
359
360
361
362
    Given the index of the processed item within
    [`modality`][vllm.multimodal.processing.PromptUpdate.modality],
    output the token sequence (or text) to insert right after
    [`target`][vllm.multimodal.processing.PromptUpdate.target].
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378

    For convenience, you can directly pass in the token sequence (or text)
    instead of a function if it does not depend on the input.
    """

    @property
    def content(self) -> PromptUpdateContent:
        return self.insertion

    @property
    def mode(self) -> UpdateMode:
        return UpdateMode.INSERT


@dataclass
class PromptReplacement(PromptUpdate):
379
380
    """
    Defines how to replace portions of an input prompt with placeholder tokens.
381
382
383

    Example:

384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
    For each image, replace one ``<image>`` input placeholder in the prompt
    with a number of ``<image>`` feature placeholders
    equal to the feature size of the vision encoder:

    ```python
    PromptReplacement(
        modality="image",
        target="<image>",
        replacement="<image>" * image_feature_size,
    )
    ```

    As above, but further pad the feature placeholders with ``<image_bos>``
    and `<image_eos>``, which are not supposed to be passed to the vision
    encoder:

    ```python
    PromptReplacement(
        modality="image",
        target="<image>",
        replacement=PromptUpdateDetails(
            full="".join([
                "<image_bos>",
                "<image>" * image_feature_size,
                "<image_eos>",
            ]),
            features="<image>" * image_feature_size,
        ),
    )
    ```

    To avoid unnecessary tokenization during prompt replacement,
    we recommended passing token sequences instead of text:

    ```python
    PromptReplacement(
        modality="image",
        target=[image_token_id],
        replacement=PromptUpdateDetails(
            full=([image_bos_id] + [image_token_id] * image_feature_size
                    + [image_eos_id]),
            features=[image_token_id] * image_feature_size,
        ),
    )
    ```
429
430
    """

431
    replacement: PromptUpdateContent = field(repr=False)
432
    """
433
434
435
436
    Given the index of the processed item within
    [`modality`][vllm.multimodal.processing.PromptUpdate.modality],
    output the token sequence (or text) to replace
    [`target`][vllm.multimodal.processing.PromptUpdate.target].
437

438
439
    For convenience, you can directly pass in the token sequence (or text)
    instead of a function if it does not depend on the input.
440
441
    """

442
443
444
445
446
447
448
    @property
    def content(self) -> PromptUpdateContent:
        return self.replacement

    @property
    def mode(self) -> UpdateMode:
        return UpdateMode.REPLACE
449
450


451
452
453
class _HasModalityAttr(Protocol):
    modality: str

454

455
class _HasModalityProp(Protocol):
456

457
458
459
460
461
462
463
464
465
    @property
    def modality(self) -> str:
        ...


_M = TypeVar("_M", bound=Union[_HasModalityAttr, _HasModalityProp])


def full_groupby_modality(values: Iterable[_M]) -> ItemsView[str, list[_M]]:
466
467
    """Convenience function to apply [`full_groupby`][vllm.utils.full_groupby]
    based on modality."""
468
469
470
    return full_groupby(values, key=lambda x: x.modality)


471
472
473
474
475
476
477
class PromptTargetMatch(NamedTuple):
    start_idx: int
    end_idx: int


@dataclass(frozen=True)
class ResolvedPromptUpdate:
478
    """
479
480
    A [`PromptUpdate`][vllm.multimodal.processing.PromptUpdate] with its
    lazy attributes resolved, apart from those related to tokenization.
481
    """
482

483
484
    modality: str
    """The modality for which the update is made."""
485

486
487
    item_idx: int
    """The index within `modality` of the item this update pertains to."""
488

489
490
    mode: UpdateMode
    """Defines how to update the prompt."""
491

492
    target: UpdateTarget
493
    """The token sequence (or text) to update."""
494

495
    content: PromptUpdateDetails = field(repr=False)
496
    """The placeholder tokens that are part of the update."""
497

498
499
500
501
502
503
504
505
506
    def iter_token_matches(
        self,
        prompt: list[int],
        tokenizer: AnyTokenizer,
        *,
        start_idx: int = 0,
    ) -> Generator[PromptTargetMatch]:
        """Yield each instance of `self.target` found in `prompt`."""
        target = self.target
507

508
509
510
511
        if isinstance(target, PromptIndex):
            match_idx = target.get_match_index(tokenizer, prompt, start_idx)
            if match_idx is not None:
                yield PromptTargetMatch(match_idx, match_idx)
512

513
            return
514

515
516
        target_token_ids = _seq2tokens(tokenizer, target)

517
        for match in iter_token_matches(prompt,
518
                                        target_token_ids,
519
520
                                        start_idx=start_idx):
            yield PromptTargetMatch(match.start_idx, match.end_idx)
521

522
523
524
525
526
527
528
529
530
    def iter_text_matches(
        self,
        prompt: str,
        tokenizer: AnyTokenizer,
        *,
        start_idx: int = 0,
    ) -> Generator[PromptTargetMatch]:
        """Yield each instance of `self.target` found in `prompt`."""
        target = self.target
531

532
533
534
535
        if isinstance(target, PromptIndex):
            match_idx = target.get_match_index(tokenizer, prompt, start_idx)
            if match_idx is not None:
                yield PromptTargetMatch(match_idx, match_idx)
536

537
            return
538

539
540
541
        target_text = _seq2text(tokenizer, target)

        for match in re.finditer(re.escape(target_text), prompt,
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
                                 pos=start_idx):
            yield PromptTargetMatch(match.start(), match.end())

    def iter_matches(
        self,
        prompt: Union[list[int], str],
        tokenizer: AnyTokenizer,
        *,
        start_idx: int = 0,
    ) -> Generator[PromptTargetMatch]:
        """Yield each instance of `self.target` found in `prompt`."""
        if isinstance(prompt, str):
            return self.iter_text_matches(prompt,
                                          tokenizer,
                                          start_idx=start_idx)

        return self.iter_token_matches(prompt, tokenizer, start_idx=start_idx)
559

560
561
562
563
564
565
566
567
568
    def with_target(self, target: UpdateTarget):
        return replace(self, target=target)

    def with_content(self, content: PromptUpdateInfo):
        if not isinstance(content, PromptUpdateDetails):
            content = PromptUpdateDetails.from_seq(content)

        return replace(self, content=content)

569

570
571
572
class _TokenMatch(NamedTuple):
    start_idx: int
    end_idx: int
573
574


575
576
577
def iter_token_matches(
    token_ids: list[int],
    match_ids: list[int],
578
579
    *,
    start_idx: int = 0,
580
) -> Generator[_TokenMatch]:
581
    """
582
    Yield each occurrence of `match_ids` in `token_ids`.
583
584
585
586

    Note that empty matches are ignored.
    """
    prompt_len = len(token_ids)
587
    match_len = len(match_ids)
588

589
590
    if match_len == 0:
        return
591

592
    while start_idx < prompt_len - match_len + 1:
593
        end_idx = start_idx + match_len
594

595
596
        if token_ids[start_idx:end_idx] == match_ids:
            yield _TokenMatch(start_idx=start_idx, end_idx=end_idx)
597
598
599
600
601

            # Exclude overlapping matches
            start_idx = end_idx
        else:
            start_idx += 1
602
603


604
605
606
607
608
609
def replace_token_matches(
    token_ids: list[int],
    match_ids: list[int],
    new_ids: list[int],
) -> list[int]:
    """
610
611
    Replace each occurrence of `match_ids` in `token_ids`
    with `new_ids`.
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630

    Note that empty matches are ignored.
    """
    out_seqs = list[list[int]]()
    prev_end_idx = 0

    for match in iter_token_matches(token_ids, match_ids):
        start_idx = match.start_idx
        end_idx = match.end_idx

        out_seqs.append(token_ids[prev_end_idx:start_idx])
        out_seqs.append(new_ids)
        prev_end_idx = end_idx

    out_seqs.append(token_ids[prev_end_idx:])

    return flatten_2d_lists(out_seqs)


631
@dataclass
632
class PlaceholderFeaturesInfo:
633
    modality: str
634
    item_idx: int
635
    start_idx: int
636
    tokens: list[int]
637
    is_embed: Optional[torch.Tensor]
638
639
640

    @property
    def length(self) -> int:
641
        return len(self.tokens)
642
643

    def to_range(self) -> PlaceholderRange:
644
645
        # TODO: Is it worth it to optimize this by stripping the
        # leading and ending positions where `is_embed=False`?
646
647
648
        return PlaceholderRange(
            offset=self.start_idx,
            length=self.length,
649
            is_embed=self.is_embed,
650
        )
651
652


653
_MatchToApply = tuple[tuple[str, int], tuple[PromptTargetMatch, int]]
654
655


656
657
658
659
660
661
662
663
664
665
666
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
695
696
697
698
699
700
701
702
703
704
705
706
707
708
def _find_matches(
    prompt: _S,
    mm_prompt_updates: "MultiModalPromptUpdates",
    tokenizer: AnyTokenizer,
    *,
    prev_end_idx: int = 0,
    current_result: "MultiModalPromptUpdatesApplyResult",
) -> tuple[Optional[UpdateMode], list[_MatchToApply]]:
    mode: Optional[UpdateMode] = None
    mm_matches = dict[tuple[str, int], tuple[PromptTargetMatch, int]]()

    for modality, modality_updates in mm_prompt_updates.items():
        for item_idx, item_updates in enumerate(modality_updates):
            if current_result[modality][item_idx] is not None:
                continue  # Updates have already been applied for this item

            for update_idx, update in enumerate(item_updates):
                if (modality, item_idx) in mm_matches:
                    break  # Already found a match for this item

                for match in update.iter_matches(
                        prompt,
                        tokenizer,
                        start_idx=prev_end_idx,
                ):
                    # All matches should share the same mode
                    if mode is None:
                        mode = update.mode
                    elif mode != update.mode:
                        continue

                    mm_matches[(modality, item_idx)] = match, update_idx
                    break  # Get only the first valid match per item

    # Prioritize earlier matches
    matches_to_apply = sorted(mm_matches.items(), key=lambda item: item[1][0])

    # To avoid conflicts, only replace one non-empty item at a time
    if mode == UpdateMode.REPLACE:
        matches_to_apply_ = list[_MatchToApply]()
        has_non_empty_matches = False

        for item in matches_to_apply:
            _, (match, _) = item
            if match.start_idx == match.end_idx:
                matches_to_apply_.append(item)
            elif not has_non_empty_matches:
                has_non_empty_matches = True
                matches_to_apply_.append(item)

        matches_to_apply = matches_to_apply_

    return mode, matches_to_apply
709
710


711
def _apply_matches(
712
    prompt: _S,
713
714
715
716
717
    mm_prompt_updates: "MultiModalPromptUpdates",
    tokenizer: AnyTokenizer,
) -> tuple[list[_S], "MultiModalPromptUpdatesApplyResult"]:
    prompt_len = len(prompt)

718
    out_seqs = list[Union[str, list[int]]]()
719
720
721
722
    out_result: MultiModalPromptUpdatesApplyResult = {
        m: [None] * len(items)
        for m, items in mm_prompt_updates.items()
    }
723

724
725
726
    start_idx = prev_end_idx = 0
    while start_idx < max(prompt_len, 1):  # Allow inserts into empty prompt
        found = False
727

728
729
730
731
732
733
734
        mode, matches_to_apply = _find_matches(
            prompt,
            mm_prompt_updates,
            tokenizer,
            prev_end_idx=prev_end_idx,
            current_result=out_result,
        )
735

736
737
738
        if mode is not None:
            for (modality, item_idx), (match, update_idx) in matches_to_apply:
                found = True
739

740
741
                matched_update = mm_prompt_updates[modality][item_idx][
                    update_idx]
742
                matched_content = matched_update.content.full
743

744
745
746
747
748
749
                if mode == UpdateMode.INSERT:
                    end_idx_to_insert = match.end_idx
                elif mode == UpdateMode.REPLACE:
                    end_idx_to_insert = match.start_idx
                else:
                    assert_never(mode)
750

751
                out_seqs.append(prompt[prev_end_idx:end_idx_to_insert])
752
753
754
755
                out_seqs.append(
                    _seq2text(tokenizer, matched_content
                              ) if isinstance(prompt, str) else _seq2tokens(
                                  tokenizer, matched_content))
756
                out_result[modality][item_idx] = update_idx
757

758
759
760
761
762
                # Exclude overlapping matches
                start_idx = prev_end_idx = match.end_idx

        if not found:
            start_idx += 1
763
764
765

    out_seqs.append(prompt[prev_end_idx:])

766
    return cast(list[_S], out_seqs), out_result
767
768


769
def apply_token_matches(
770
    prompt: list[int],
771
772
773
774
775
    mm_prompt_updates: "MultiModalPromptUpdates",
    tokenizer: AnyTokenizer,
) -> tuple[list[int], "MultiModalPromptUpdatesApplyResult"]:
    """
    Apply the updates in `mm_prompt_updates` to `prompt`.
776

777
778
779
780
781
782
    Matches are exclusive even when multiple modalities share
    the same placeholder tokens. In that case, the modality that
    appears earlier in `mm_prompt_updates` takes priority.
    """
    token_id_seqs, result = _apply_matches(prompt, mm_prompt_updates,
                                           tokenizer)
783

784
    return flatten_2d_lists(token_id_seqs), result
785
786


787
def apply_text_matches(
788
    prompt: str,
789
790
791
792
793
    mm_prompt_updates: "MultiModalPromptUpdates",
    tokenizer: AnyTokenizer,
) -> tuple[str, "MultiModalPromptUpdatesApplyResult"]:
    """
    Apply the updates in `mm_prompt_updates` to `prompt`.
794

795
796
797
798
799
    Matches are exclusive even when multiple modalities share
    the same placeholder tokens. In that case, the modality that
    appears earlier in `mm_prompt_updates` takes priority.
    """
    texts, result = _apply_matches(prompt, mm_prompt_updates, tokenizer)
800

801
    return "".join(texts), result
802
803


804
def _iter_placeholders(
805
    prompt: list[int],
806
    mm_prompt_updates: "MultiModalPromptUpdates",
807
    tokenizer: AnyTokenizer,
808
) -> Iterable[PlaceholderFeaturesInfo]:
809
    """
810
    Yield each set of placeholder tokens found in `prompt`.
811
812
813

    Matches are exclusive even when multiple modalities share
    the same placeholder tokens. In that case, the modality that
814
    appears earlier in `mm_prompt_updates` takes priority.
815

816
817
    Note that empty matches are ignored.
    """
818
    prompt_len = len(prompt)
819
820
    mm_item_counts = {m: len(items) for m, items in mm_prompt_updates.items()}

821
    item_idx_by_modality = defaultdict[str, int](lambda: 0)
822
823
824
825
826

    start_idx = 0
    while start_idx < prompt_len:
        found = False

827
        for modality, modality_updates in mm_prompt_updates.items():
828
829
            item_idx = item_idx_by_modality[modality]
            if item_idx >= mm_item_counts.get(modality, 0):
830
                continue
831

832
833
            for update in modality_updates[item_idx]:
                content = update.content
834
                content_tokens_full = _seq2tokens(tokenizer, content.full)
835
836
                content_len_full = len(content_tokens_full)
                end_idx_full = start_idx + content_len_full
837

838
                if content_len_full == 0 or end_idx_full > prompt_len:
839
840
                    continue

841
                if prompt[start_idx:end_idx_full] == content_tokens_full:
842
843
                    content_is_embed = content.is_embed
                    if content_is_embed is not None:
844
845
                        content_is_embed = content_is_embed(
                            tokenizer, content.full)
846
847
848
849
850
851
852
853

                    yield PlaceholderFeaturesInfo(
                        modality=modality,
                        item_idx=item_idx,
                        start_idx=start_idx,
                        tokens=content_tokens_full,
                        is_embed=content_is_embed,
                    )
854

855
                    # Exclude overlapping matches
856
                    start_idx = end_idx_full
857
858
859
                    item_idx_by_modality[modality] += 1
                    found = True
                    break
860

861
862
            if found:
                break  # Go back to the outer while loop
863
864
865

        if not found:
            start_idx += 1
866
867


868
869
def find_mm_placeholders(
    prompt: list[int],
870
    mm_prompt_updates: "MultiModalPromptUpdates",
871
    tokenizer: AnyTokenizer,
872
) -> Mapping[str, list[PlaceholderFeaturesInfo]]:
873
    it = _iter_placeholders(prompt, mm_prompt_updates, tokenizer)
874
875
876
    return dict(full_groupby_modality(it))


877
class BaseProcessingInfo:
878
    """Base class to provide the information necessary for data processing."""
879

880
881
    def __init__(self, ctx: InputProcessingContext) -> None:
        super().__init__()
882

883
884
885
886
887
888
889
        self.ctx = ctx

    @property
    def model_id(self) -> str:
        return self.ctx.model_config.model

    def get_tokenizer(self) -> AnyTokenizer:
890
891
        return self.ctx.tokenizer

892
    def get_hf_config(self) -> "PretrainedConfig":
893
894
        return self.ctx.get_hf_config()

895
    def get_hf_processor(self, **kwargs: object) -> "ProcessorMixin":
896
897
898
899
900
901
        """
        Subclasses can override this method to handle
        specific kwargs from model config or user inputs.
        """
        return self.ctx.get_hf_processor(**kwargs)

902
903
904
905
906
907
908
909
910
911
912
913
    @abstractmethod
    def get_supported_mm_limits(self) -> Mapping[str, Optional[int]]:
        """
        Return the maximum supported number of items for each modality.

        A value of `None` means unlimited number of items.

        Omitting a modality from the returned dictionary means that
        it is not supported at all.
        """
        raise NotImplementedError

914
915
916
917
918
919
920
921
922
923
924
925
926
927
    def get_allowed_mm_limits(self) -> Mapping[str, int]:
        """Return the maximum allowed number of items for each modality."""
        supported_mm_limits = self.get_supported_mm_limits()
        mm_config = self.ctx.get_mm_config()

        allowed_limits = dict[str, int]()
        for modality, supported_limit in supported_mm_limits.items():
            user_limit = mm_config.get_limit_per_prompt(modality)

            allowed_limits[modality] = (user_limit if supported_limit is None
                                        else min(user_limit, supported_limit))

        return allowed_limits

928
929
930
931
932
933
934
935
936
937
938
939
    def get_mm_max_tokens_per_item(
        self,
        seq_len: int,
        mm_counts: Mapping[str, int],
    ) -> Optional[Mapping[str, int]]:
        """
        Return the maximum number of tokens per item of for each modality.
        
        When `None` (the default) is returned, vLLM will generate dummy inputs
        (images/videos) at maximum possible sizes and process them to determine
        the maximum token count per modality.

940
941
942
943
944
        This approach works but can be very slow for certain models (e.g.,
        Qwen2.5-VL), leading to very long startup time. For better performance,
        each model can override this method to return pre-computed maximum token
        counts, avoiding the need for dummy input generation and processing.

945
946
947
948
949
950
        Note:
            The maximum number of tokens per item of each modality returned 
            from this function should respect the model's maximum sequence
            length and the maximum number of items of each modality allowed,
            and agree with dummy inputs (images/videos) at maximum possible
            sizes.
951
952
953
        """
        return None

954
955

_I = TypeVar("_I", bound=BaseProcessingInfo)
956

957
958
MultiModalHashes = dict[str, list[str]]
"""
959
A collection of hashes with a similar structure as
960
[`MultiModalKwargsItems`][vllm.multimodal.inputs.MultiModalKwargsItems].
961
962
"""

963
MultiModalPromptUpdates = Mapping[str, list[Sequence[ResolvedPromptUpdate]]]
964
965
966
967
968
"""
A collection of prompt updates with a similar structure as
[`MultiModalKwargsItems`][vllm.multimodal.inputs.MultiModalKwargsItems].
"""

969
970
971
972
973
974
975
976
MultiModalPromptUpdatesApplyResult = Mapping[str, list[Optional[int]]]
"""
For an item `MultiModalPromptUpdates[k][i]`,
`MultiModalPromptUpdatesApplyResult[k][i]` represents the index of the
`ResolvedPromptUpdate` instance that has been applied, or `None` if none of the
`ResolvedPromptUpdate` instances have been applied.
"""

977
978

class MultiModalProcessingInfo(NamedTuple):
979
    kwargs: MultiModalKwargsOptionalItems
980
    hashes: MultiModalHashes
981
982
    prompt_updates: MultiModalPromptUpdates

983
984

class BaseMultiModalProcessor(ABC, Generic[_I]):
985
    """
986
    Abstract base class to process multi-modal inputs to be used in vLLM.
987

988
    Not to be confused with `transformers.ProcessorMixin`.
989
990
    """

991
992
993
994
995
996
997
    def __init__(
        self,
        info: _I,
        dummy_inputs: "BaseDummyInputsBuilder[_I]",
        *,
        cache: Optional["BaseMultiModalProcessorCache"] = None,
    ) -> None:
998
999
        super().__init__()

1000
1001
        self.info = info
        self.dummy_inputs = dummy_inputs
1002
        self.cache = cache
1003

1004
1005
        self.data_parser = self._get_data_parser()

1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
        # Avoid unnecessary recomputation
        self._supported_mm_limits = self.info.get_supported_mm_limits()
        self._allowed_mm_limits = self.info.get_allowed_mm_limits()

    @property
    def supported_mm_limits(self):
        return self._supported_mm_limits

    @property
    def allowed_mm_limits(self):
        return self._allowed_mm_limits

1018
    def __call__(
1019
        self,
1020
1021
        prompt: str,
        mm_data: MultiModalDataDict,
1022
        hf_processor_mm_kwargs: Mapping[str, object],
1023
1024
        *,
        mm_hash_overrides: Optional[MultiModalHashes] = None,
1025
    ) -> MultiModalInputs:
1026
1027
1028
1029
        return self.apply(prompt,
                          mm_data,
                          hf_processor_mm_kwargs,
                          mm_hash_overrides=mm_hash_overrides)
1030

1031
1032
    def _get_data_parser(self) -> MultiModalDataParser:
        """
1033
        Construct a parser to preprocess multi-modal data items
1034
1035
        before passing them to
        [`_get_hf_mm_data`][vllm.multimodal.processing.BaseMultiModalProcessor._get_hf_mm_data].
1036
1037

        You can support additional modalities by creating a subclass
1038
1039
        of [`MultiModalDataParser`][vllm.multimodal.parse.MultiModalDataParser]
        that has additional subparsers.
1040
1041
1042
        """
        return MultiModalDataParser()

1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
    def validate_num_items(
        self,
        modality: str,
        num_items: int,
    ) -> None:
        supported_limit = self.supported_mm_limits.get(modality, 0)
        allowed_limit = self.allowed_mm_limits.get(modality, 0)

        if supported_limit is None:
            supported_limit = allowed_limit

        limit = min(supported_limit, allowed_limit)

        if num_items > limit:
            msg = (f"At most {limit} {modality}(s) may be provided in "
                   "one prompt.")

            if num_items <= supported_limit:
                msg += " Set `--limit-mm-per-prompt` to increase this limit."

            raise ValueError(msg)

1065
    def _to_mm_items(
1066
1067
1068
        self,
        mm_data: MultiModalDataDict,
    ) -> MultiModalDataItems:
1069
        """
1070
1071
1072
1073
1074
        Normalize
        [`MultiModalDataDict`][vllm.multimodal.inputs.MultiModalDataDict]
        to [`MultiModalDataItems`][vllm.multimodal.parse.MultiModalDataItems]
        before passing them to
        [`_get_hf_mm_data`][vllm.multimodal.processing.BaseMultiModalProcessor._get_hf_mm_data].
1075
        """
1076
        mm_items = self.data_parser.parse_mm_data(mm_data)
1077
1078

        for modality, items in mm_items.items():
1079
            self.validate_num_items(modality, len(items))
1080
1081

        return mm_items
1082

1083
1084
1085
    @abstractmethod
    def _get_mm_fields_config(
        self,
1086
        hf_inputs: "BatchFeature",
1087
1088
1089
1090
1091
        hf_processor_mm_kwargs: Mapping[str, object],
    ) -> Mapping[str, MultiModalFieldConfig]:
        """Given the HF-processed data, output the metadata of each field."""
        raise NotImplementedError

1092
    @abstractmethod
1093
    def _get_prompt_updates(
1094
        self,
1095
        mm_items: MultiModalDataItems,
1096
        hf_processor_mm_kwargs: Mapping[str, object],
1097
        out_mm_kwargs: MultiModalKwargsItems,
1098
    ) -> Sequence[PromptUpdate]:
1099
1100
        """
        Given the original multi-modal items for this modality
1101
        and HF-processed data, output the updates to perform.
1102

1103
1104
1105
1106
1107
1108
        The information returned by this method is used to update token inputs
        which bypass the HF processor. It is also used to update the output of
        HF processor if the HF process does not apply prompt updates to text
        inputs.

        Moreover, this information is critical to determine the token positions
1109
1110
        in order to construct
        [`PlaceholderRange`][vllm.multimodal.inputs.PlaceholderRange]
1111
        for each multi-modal item.
1112
1113
        """
        raise NotImplementedError
1114

1115
1116
1117
1118
1119
1120
    def _bind_and_group_updates(
        self,
        prompt_updates: Sequence[PromptUpdate],
        mm_item_counts: Mapping[str, int],
    ) -> MultiModalPromptUpdates:
        return {
1121
1122
            modality: [[update.resolve(item_idx) for update in updates]
                       for item_idx in range(mm_item_counts.get(modality, 0))]
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
            for modality, updates in full_groupby_modality(prompt_updates)
        }

    def _get_mm_prompt_updates(
        self,
        mm_items: MultiModalDataItems,
        hf_processor_mm_kwargs: Mapping[str, object],
        out_mm_kwargs: MultiModalKwargsItems,
    ) -> MultiModalPromptUpdates:
        unbound_prompt_updates = self._get_prompt_updates(
            mm_items=mm_items,
            hf_processor_mm_kwargs=hf_processor_mm_kwargs,
            out_mm_kwargs=out_mm_kwargs,
        )

        mm_prompt_updates = self._bind_and_group_updates(
            unbound_prompt_updates,
            mm_items.get_all_counts(),
        )

        for modality, prompt_updates in mm_prompt_updates.items():
            for item_idx, item_prompt_updates in enumerate(prompt_updates):
                if len(item_prompt_updates) > 1:
                    logger.warning_once(
                        "Detected %d prompt updates for `mm_items[%r][%s]`. "
                        "Multiple prompt updates per item is now "
                        "deprecated and may be removed in v0.13. "
                        "Instead, please specify dynamic update targets "
                        "in the same prompt update definition by passing "
                        "a function to `PromptUpdate.target`.",
                        len(prompt_updates),
                        modality,
                        item_idx,
                    )

        return mm_prompt_updates

1160
    def _find_mm_placeholders(
1161
1162
        self,
        new_token_ids: list[int],
1163
        mm_prompt_updates: MultiModalPromptUpdates,
1164
    ) -> Mapping[str, list[PlaceholderFeaturesInfo]]:
1165
1166
1167
1168
        tokenizer = self.info.get_tokenizer()

        return find_mm_placeholders(new_token_ids, mm_prompt_updates,
                                    tokenizer)
1169

1170
    def _get_hf_mm_data(
1171
        self,
1172
        mm_items: MultiModalDataItems,
1173
1174
1175
    ) -> tuple[Mapping[str, object], Mapping[str, object]]:
        processor_data = dict[str, object]()
        passthrough_data = dict[str, object]()
1176

1177
1178
1179
        for items in mm_items.values():
            processor_data.update(items.get_processor_data())
            passthrough_data.update(items.get_passthrough_data())
1180

1181
1182
        return processor_data, passthrough_data

1183
1184
1185
    def _call_hf_processor(
        self,
        prompt: str,
1186
1187
1188
1189
        # Not to be confused with `mm_data` in `self.apply`.
        # This refers to the data to be passed to HF processor.
        mm_data: Mapping[str, object],
        mm_kwargs: Mapping[str, object],
1190
        tok_kwargs: Mapping[str, object],
1191
    ) -> "BatchFeature":
1192
1193
1194
1195
        """
        Call the HF processor on the prompt text and
        associated multi-modal data.
        """
1196
1197
        return self.info.ctx.call_hf_processor(
            self.info.get_hf_processor(**mm_kwargs),
1198
            dict(text=prompt, **mm_data),
1199
            dict(**mm_kwargs, **tok_kwargs),
1200
1201
        )

1202
    def _hf_processor_applies_updates(
1203
1204
1205
1206
        self,
        prompt_text: str,
        mm_items: MultiModalDataItems,
        hf_processor_mm_kwargs: Mapping[str, object],
1207
        tokenization_kwargs: Mapping[str, object],
1208
1209
    ) -> bool:
        """
1210
        Return whether the HF processor applies prompt updates.
1211

1212
1213
        For most HF processors, this should be `True` when multi-modal
        data items are passed, but `False` when multi-modal embeddings
1214
1215
1216
1217
1218
1219
        are passed.
        """
        return not any(
            isinstance(items, (EmbeddingItems, DictEmbeddingItems))
            for items in mm_items.values())

1220
    def _apply_hf_processor_text_mm(
1221
        self,
1222
        prompt_text: str,
1223
        mm_items: MultiModalDataItems,
1224
        hf_processor_mm_kwargs: Mapping[str, object],
1225
        tokenization_kwargs: Mapping[str, object],
1226
    ) -> tuple[list[int], "BatchFeature", bool]:
1227
        """
1228
1229
        Apply the HF processor on the prompt text and multi-modal data
        together.
1230

1231
        In addition, return whether prompt updates have been applied.
1232
1233
1234
1235
1236
1237
1238
        """
        processor_data, passthrough_data = self._get_hf_mm_data(mm_items)

        processed_data = self._call_hf_processor(
            prompt=prompt_text,
            mm_data=processor_data,
            mm_kwargs=hf_processor_mm_kwargs,
1239
            tok_kwargs=tokenization_kwargs,
1240
1241
        )
        processed_data.update(passthrough_data)
1242

1243
        prompt_ids, = processed_data.pop("input_ids").tolist()
1244

1245
        is_update_applied = self._hf_processor_applies_updates(
1246
1247
1248
            prompt_text=prompt_text,
            mm_items=mm_items,
            hf_processor_mm_kwargs=hf_processor_mm_kwargs,
1249
            tokenization_kwargs=tokenization_kwargs,
1250
1251
        )

1252
        return prompt_ids, processed_data, is_update_applied
1253

1254
    def _apply_hf_processor_text_only(
1255
1256
1257
1258
        self,
        prompt_text: str,
        tokenization_kwargs: Mapping[str, object],
    ) -> list[int]:
1259
        """
1260
        Apply the HF processor on the prompt text only.
1261

1262
1263
1264
        Since HF processor requires that text and multi-modal items
        correspond to each other, we create dummy multi-modal items
        to go along with the text.
1265
        """
1266
        prompt_ids, _, _ = self._apply_hf_processor_text_mm(
1267
1268
1269
            prompt_text=prompt_text,
            mm_items=MultiModalDataItems({}),
            hf_processor_mm_kwargs={},
1270
            tokenization_kwargs=tokenization_kwargs,
1271
1272
        )

1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
        return prompt_ids

    def _apply_hf_processor_tokens_only(
        self,
        prompt_tokens: list[int],
    ) -> list[int]:
        """
        Apply the HF processor on the prompt tokens only.

        Most HF processors accept prompt text but not prompt tokens.
        If the HF processor adds or removes tokens that are not related to
        multi-modal data, you should override this method so it is consistent
1285
1286
1287
        with the output of
        [`_apply_hf_processor_text_only`][vllm.multimodal.processing.BaseMultiModalProcessor._apply_hf_processor_text_only]
        on the
1288
1289
1290
1291
1292
1293
1294
1295
        corresponding text.
        """
        return prompt_tokens

    def _apply_hf_processor_mm_only(
        self,
        mm_items: MultiModalDataItems,
        hf_processor_mm_kwargs: Mapping[str, object],
1296
        tokenization_kwargs: Mapping[str, object],
1297
    ) -> "BatchFeature":
1298
1299
1300
1301
1302
        """
        Apply the HF processor on the multi-modal data only.

        Since HF processor requires that text and multi-modal items
        correspond to each other, we generate dummy text using
1303
1304
        [`DummyInputsBuilder`][vllm.multimodal.profiling.BaseDummyInputsBuilder]
        to go along with the multi-modal data.
1305
1306
1307
        """
        mm_counts = mm_items.get_all_counts()

1308
        _, mm_processed_data, _ = self._apply_hf_processor_text_mm(
1309
            prompt_text=self.dummy_inputs.get_dummy_text(mm_counts),
1310
1311
            mm_items=mm_items,
            hf_processor_mm_kwargs=hf_processor_mm_kwargs,
1312
            tokenization_kwargs=tokenization_kwargs,
1313
1314
        )

1315
        return mm_processed_data
1316
1317
1318
1319
1320
1321

    def _apply_hf_processor_main(
        self,
        prompt: Union[str, list[int]],
        mm_items: MultiModalDataItems,
        hf_processor_mm_kwargs: Mapping[str, object],
1322
        tokenization_kwargs: Mapping[str, object],
1323
        *,
1324
        enable_hf_prompt_update: bool,
1325
    ) -> tuple[list[int], "BatchFeature", bool]:
1326
1327
1328
        """
        Apply the HF processor on the prompt text and multi-modal data.

1329
        In addition, return whether prompt updates have been applied
1330
        (for most HF processors, this should be `True`).
1331

1332
        Note:
1333
            If `enable_hf_prompt_update=False`, we use HF processor
1334
            to perform prompt updates if available; HF processor requires
1335
            that the prompt corresponds to multi-modal items.
1336
1337
        """
        if isinstance(prompt, str):
1338
            if enable_hf_prompt_update:
1339
1340
1341
1342
                return self._apply_hf_processor_text_mm(
                    prompt_text=prompt,
                    mm_items=mm_items,
                    hf_processor_mm_kwargs=hf_processor_mm_kwargs,
1343
                    tokenization_kwargs=tokenization_kwargs,
1344
1345
                )

1346
1347
            prompt_ids = self._apply_hf_processor_text_only(
                prompt, tokenization_kwargs)
1348
1349
1350
        else:
            prompt_ids = self._apply_hf_processor_tokens_only(prompt)

1351
        mm_processed_data = self._apply_hf_processor_mm_only(
1352
            mm_items=mm_items,
1353
            hf_processor_mm_kwargs=hf_processor_mm_kwargs,
1354
            tokenization_kwargs=tokenization_kwargs,
1355
1356
        )

1357
        return prompt_ids, mm_processed_data, False
1358

1359
    def _hash_mm_items(
1360
1361
1362
1363
1364
        self,
        mm_items: MultiModalDataItems,
        hf_processor_mm_kwargs: Mapping[str, object],
        tokenization_kwargs: Mapping[str, object],
    ) -> MultiModalHashes:
1365
1366
1367
1368
1369
        """Create MM hashes to be returned (only used in V1).

        Note: When overrides are provided via callers of `apply`,
        `_hash_mm_items` will be bypassed and the overrides will be used.
        """
1370
1371
1372
1373
1374
1375
        model_id = self.info.model_id

        return {
            modality: [
                MultiModalHasher.hash_kwargs(model_id=model_id,
                                             **{modality: item},
1376
1377
                                             **hf_processor_mm_kwargs,
                                             **tokenization_kwargs)
1378
1379
1380
1381
1382
                for item in items
            ]
            for modality, items in mm_items.items()
        }

1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
    def _get_cache_missing_items(
        self,
        cache: "BaseMultiModalProcessorCache",
        mm_data_items: MultiModalDataItems,
        mm_hashes: MultiModalHashes,
    ) -> MultiModalDataItems:
        mm_is_cached = {
            modality: cache.is_cached(hashes)
            for modality, hashes in mm_hashes.items()
        }

        mm_missing_idxs = {
            modality: [
                idx for idx, item_is_cached in enumerate(items_is_cached)
                if not item_is_cached
            ]
            for modality, items_is_cached in mm_is_cached.items()
        }
        mm_missing_data = {
            modality: [mm_data_items[modality][idx] for idx in idxs]
            for modality, idxs in mm_missing_idxs.items()
        }

        return self._to_mm_items(mm_missing_data)

    def _recompute_cached_prompt_update(
        self,
        cached_update: ResolvedPromptUpdate,
        new_item_idx: int,
    ) -> ResolvedPromptUpdate:
        """
        Override this if other attributes of `ResolvedPromptUpdate`
        also need to be recomputed after retrieving from the cache.
        """
        return replace(cached_update, item_idx=new_item_idx)

1419
1420
    def _merge_mm_kwargs(
        self,
1421
1422
        cache: "BaseMultiModalProcessorCache",
        mm_hashes: MultiModalHashes,
1423
        mm_missing_kwargs: MultiModalKwargsItems,
1424
1425
1426
1427
1428
1429
1430
1431
1432
        mm_missing_prompt_updates: MultiModalPromptUpdates,
    ) -> tuple[MultiModalKwargsOptionalItems, MultiModalPromptUpdates]:
        # Need to calculate this at the beginning to avoid skipping cache logic
        # for subsequently repeated items in the same modality
        mm_is_cached = {
            modality: cache.is_cached(hashes)
            for modality, hashes in mm_hashes.items()
        }

1433
        mm_missing_next_idx = defaultdict[str, int](lambda: 0)
1434

1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
        merged_kwargs = defaultdict[str,
                                    list[Optional[MultiModalKwargsItem]]](list)
        merged_prompt_updates = defaultdict[
            str, list[Sequence[ResolvedPromptUpdate]]](list)
        for modality, hashes in mm_hashes.items():
            missing_kwargs = mm_missing_kwargs.get(modality, [])
            missing_prompt_updates = mm_missing_prompt_updates.get(
                modality, [])

            for item_idx, item_hash in enumerate(hashes):
                kwargs: Optional[MultiModalKwargsItem]
                if not mm_is_cached[modality][item_idx]:
                    missing_next_idx = mm_missing_next_idx[modality]
                    kwargs = missing_kwargs[missing_next_idx]
                    updates = missing_prompt_updates[missing_next_idx]

1451
                    mm_missing_next_idx[modality] += 1
1452
1453

                    item = kwargs, updates
1454
                else:
1455
1456
1457
1458
1459
1460
1461
1462
1463
                    item = None

                kwargs, updates = cache.get_and_update_item(item, item_hash)

                merged_kwargs[modality].append(kwargs)
                merged_prompt_updates[modality].append([
                    self._recompute_cached_prompt_update(update, item_idx)
                    for update in updates
                ])
1464

1465
1466
        mm_kwargs = MultiModalKwargsItems(merged_kwargs)
        mm_prompt_updates = dict(merged_prompt_updates)
1467

1468
        return mm_kwargs, mm_prompt_updates
1469
1470
1471
1472
1473
1474

    def _apply_hf_processor(
        self,
        prompt: Union[str, list[int]],
        mm_data_items: MultiModalDataItems,
        hf_processor_mm_kwargs: Mapping[str, object],
1475
        tokenization_kwargs: Mapping[str, object],
1476
1477
        *,
        mm_hash_overrides: Optional[MultiModalHashes] = None,
1478
    ) -> tuple[list[int], MultiModalProcessingInfo, bool]:
1479
1480
        (
            prompt_ids,
1481
            mm_processed_data,
1482
1483
1484
1485
1486
            is_update_applied,
        ) = self._apply_hf_processor_main(
            prompt=prompt,
            mm_items=mm_data_items,
            hf_processor_mm_kwargs=hf_processor_mm_kwargs,
1487
            tokenization_kwargs=tokenization_kwargs,
1488
1489
1490
            enable_hf_prompt_update=True,
        )

1491
        mm_kwargs = MultiModalKwargsItems.from_hf_inputs(
1492
1493
1494
1495
1496
            mm_processed_data,
            self._get_mm_fields_config(mm_processed_data,
                                       hf_processor_mm_kwargs),
        )

1497
1498
1499
1500
        # Use overrides if provided; fallback to data-dependent hashing.
        mm_hashes = (mm_hash_overrides if mm_hash_overrides is not None else
                     self._hash_mm_items(mm_data_items, hf_processor_mm_kwargs,
                                         tokenization_kwargs))
1501

1502
        mm_prompt_updates = self._get_mm_prompt_updates(
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
            mm_data_items,
            hf_processor_mm_kwargs,
            mm_kwargs,
        )

        mm_info = MultiModalProcessingInfo(
            kwargs=mm_kwargs,
            hashes=mm_hashes,
            prompt_updates=mm_prompt_updates,
        )

        return prompt_ids, mm_info, is_update_applied
1515

1516
1517
    def _cached_apply_hf_processor(
        self,
1518
        prompt: Union[str, list[int]],
1519
1520
        mm_data_items: MultiModalDataItems,
        hf_processor_mm_kwargs: Mapping[str, object],
1521
        tokenization_kwargs: Mapping[str, object],
1522
1523
        *,
        mm_hash_overrides: Optional[MultiModalHashes] = None,
1524
    ) -> tuple[list[int], MultiModalProcessingInfo, bool]:
1525
1526
1527
1528
1529
1530
        """
        Apply the HF processor on the full prompt text,
        caching the results and reusing cached results.
        """
        cache = self.cache

1531
1532
        _, passthrough_data = self._get_hf_mm_data(mm_data_items)
        if cache is None or passthrough_data:
1533
            return self._apply_hf_processor(
1534
                prompt=prompt,
1535
                mm_data_items=mm_data_items,
1536
                hf_processor_mm_kwargs=hf_processor_mm_kwargs,
1537
                tokenization_kwargs=tokenization_kwargs,
1538
                mm_hash_overrides=mm_hash_overrides,
1539
1540
            )

1541
1542
1543
1544
        # Use overrides if provided; fallback to data-dependent hashing.
        mm_hashes = (mm_hash_overrides if mm_hash_overrides is not None else
                     self._hash_mm_items(mm_data_items, hf_processor_mm_kwargs,
                                         tokenization_kwargs))
1545
1546

        mm_missing_data_items = self._get_cache_missing_items(
1547
1548
            cache=cache,
            mm_data_items=mm_data_items,
1549
            mm_hashes=mm_hashes,
1550
        )
1551

1552
        # NOTE: `prompt` does not correspond to `mm_missing_data_items`,
1553
        # so we can't apply prompt updates until the new multimodal
1554
1555
1556
        # items are combined with the cached multimodal items
        (
            prompt_ids,
1557
            mm_missing_processed_data,
1558
            is_update_applied,
1559
        ) = self._apply_hf_processor_main(
1560
            prompt=prompt,
1561
            mm_items=mm_missing_data_items,
1562
            hf_processor_mm_kwargs=hf_processor_mm_kwargs,
1563
            tokenization_kwargs=tokenization_kwargs,
1564
            enable_hf_prompt_update=False,
1565
1566
        )

1567
        mm_missing_kwargs = MultiModalKwargsItems.from_hf_inputs(
1568
1569
1570
1571
1572
            mm_missing_processed_data,
            self._get_mm_fields_config(mm_missing_processed_data,
                                       hf_processor_mm_kwargs),
        )

1573
1574
1575
1576
        mm_missing_prompt_updates = self._get_mm_prompt_updates(
            mm_missing_data_items,
            hf_processor_mm_kwargs,
            mm_missing_kwargs,
1577
        )
1578

1579
1580
1581
1582
1583
        mm_kwargs, mm_prompt_updates = self._merge_mm_kwargs(
            cache,
            mm_hashes=mm_hashes,
            mm_missing_kwargs=mm_missing_kwargs,
            mm_missing_prompt_updates=mm_missing_prompt_updates,
1584
1585
1586
1587
        )

        mm_info = MultiModalProcessingInfo(
            kwargs=mm_kwargs,
1588
            hashes=mm_hashes,
1589
1590
            prompt_updates=mm_prompt_updates,
        )
1591

1592
        return prompt_ids, mm_info, is_update_applied
1593

1594
1595
1596
    def _apply_token_matches(
        self,
        prompt: list[int],
1597
1598
1599
1600
        mm_prompt_updates: MultiModalPromptUpdates,
    ) -> tuple[list[int], MultiModalPromptUpdatesApplyResult]:
        tokenizer = self.info.get_tokenizer()
        return apply_token_matches(prompt, mm_prompt_updates, tokenizer)
1601
1602
1603
1604

    def _apply_text_matches(
        self,
        prompt: str,
1605
1606
1607
1608
        mm_prompt_updates: MultiModalPromptUpdates,
    ) -> tuple[str, MultiModalPromptUpdatesApplyResult]:
        tokenizer = self.info.get_tokenizer()
        return apply_text_matches(prompt, mm_prompt_updates, tokenizer)
1609

1610
    def _apply_prompt_updates(
1611
1612
        self,
        token_ids: list[int],
1613
        mm_prompt_updates: MultiModalPromptUpdates,
1614
    ) -> tuple[list[int], str, Mapping[str, list[PlaceholderFeaturesInfo]]]:
1615
        tokenizer = self.info.get_tokenizer()
1616

1617
1618
1619
1620
        new_token_ids, match_result = self._apply_token_matches(
            token_ids,
            mm_prompt_updates,
        )
1621
1622
1623
1624
1625
1626
1627
1628
1629

        # If the search text does not represent a special token,
        # it may have different token IDs in the prompt, because
        # the tokens may go across the boundaries of the search text.
        # ----
        # e.g. when searching for "foo" in "food", if "food" itself makes
        # up a token, then the token ID of "foo" will not appear at all
        # ----
        # Since it is inefficient to search for all possible tokenizations
1630
1631
        # of the search text in the prompt, we instead perform string-based
        # updates on the decoded token IDs, then encode them back.
1632
        if all(
1633
1634
1635
1636
1637
1638
1639
                all(update_idx is not None for update_idx in update_idxs)
                for update_idxs in match_result.values()):
            new_text = decode_tokens(tokenizer, new_token_ids)
        else:
            new_text, match_result = self._apply_text_matches(
                decode_tokens(tokenizer, token_ids),
                mm_prompt_updates,
1640
1641
            )

1642
1643
1644
1645
            new_token_ids = encode_tokens(
                tokenizer,
                new_text,
                add_special_tokens=False,
1646
1647
            )

1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
        matched_updates = defaultdict[
            str, list[Sequence[ResolvedPromptUpdate]]](list)
        for modality, update_idxs in match_result.items():
            for item_idx, update_idx in enumerate(update_idxs):
                assert update_idx is not None, (
                    "Failed to apply prompt replacement for "
                    f"mm_items[{modality!r}][{item_idx}]")

                matched_updates[modality].append(
                    [mm_prompt_updates[modality][item_idx][update_idx]])
1658
1659

        placeholders = self._find_mm_placeholders(
1660
1661
            new_token_ids,
            dict(matched_updates),
1662
        )
1663

1664
        return new_token_ids, new_text, placeholders
1665

1666
1667
    def _validate_mm_kwargs(
        self,
1668
        mm_kwargs: MultiModalKwargsOptionalItems,
1669
1670
1671
        mm_item_counts: Mapping[str, int],
    ) -> None:
        for modality, item_count in mm_item_counts.items():
1672
            items = mm_kwargs.get(modality, [])
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685

            if len(items) != item_count:
                raise RuntimeError(
                    f"Expected there to be {item_count} {modality} items in "
                    f"keyword arguments corresponding to {item_count} "
                    f"{modality} data items, but only found {len(items)}! "
                    "There is likely a problem with your "
                    "implementation of merged multi-modal processor for this "
                    "model (usually arising from an inconsistency between "
                    "`_call_hf_processor` and `_get_mm_fields_config`).")

    def _validate_mm_placeholders(
        self,
1686
        mm_placeholders: Mapping[str, list[PlaceholderFeaturesInfo]],
1687
        mm_item_counts: Mapping[str, int],
1688
    ) -> None:
1689
1690
1691
        for modality, item_count in mm_item_counts.items():
            placeholders = mm_placeholders.get(modality, [])

1692
            if len(placeholders) != item_count:
1693
1694
1695
                # NOTE: If you are a model developer, this can also arise from
                # an inconsistency between `_call_hf_processor` and
                # `_get_mm_fields_config` implementations
1696
                raise RuntimeError(
1697
                    f"Expected there to be {item_count} prompt updates "
1698
                    f"corresponding to {item_count} {modality} items, but "
1699
                    f"instead found {len(placeholders)} prompt updates! "
1700
1701
1702
1703
                    "This is likely because you forgot to include input "
                    "placeholder tokens (e.g., `<image>`, `<|image_pad|>`) "
                    "in the prompt. If the model has a chat template, make "
                    "sure you have applied it before calling `LLM.generate`.")
1704

1705
1706
1707
1708
    def _maybe_apply_prompt_updates(
        self,
        mm_items: MultiModalDataItems,
        prompt_ids: list[int],
1709
        mm_kwargs: MultiModalKwargsOptionalItems,
1710
        mm_prompt_updates: MultiModalPromptUpdates,
1711
1712
        is_update_applied: bool,
    ) -> tuple[list[int], str, Mapping[str, list[PlaceholderFeaturesInfo]]]:
1713
        mm_item_counts = mm_items.get_all_counts()
1714
1715
        self._validate_mm_kwargs(mm_kwargs, mm_item_counts)

1716
        if is_update_applied:
1717
1718
            mm_placeholders = self._find_mm_placeholders(
                prompt_ids,
1719
                mm_prompt_updates,
1720
            )
1721
            self._validate_mm_placeholders(mm_placeholders, mm_item_counts)
1722

1723
            tokenizer = self.info.get_tokenizer()
1724
            prompt = decode_tokens(tokenizer, prompt_ids)
1725
1726
1727
        else:
            (
                prompt_ids,
1728
                prompt,
1729
                mm_placeholders,
1730
            ) = self._apply_prompt_updates(
1731
                prompt_ids,
1732
                mm_prompt_updates,
1733
            )
1734
            self._validate_mm_placeholders(mm_placeholders, mm_item_counts)
1735

1736
1737
1738
1739
1740
1741
1742
        return prompt_ids, prompt, mm_placeholders

    def apply(
        self,
        prompt: Union[str, list[int]],
        mm_data: MultiModalDataDict,
        hf_processor_mm_kwargs: Mapping[str, object],
1743
        tokenization_kwargs: Optional[Mapping[str, object]] = None,
1744
1745
        *,
        mm_hash_overrides: Optional[dict[str, list[str]]] = None,
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
    ) -> MultiModalInputs:
        """
        Process multi-modal inputs to be used in vLLM.

        The main steps are:

        1. Apply HF Processor on prompt text and multi-modal data together,
           outputting token IDs and processed tensors.
        2. Find and update sequences in the token IDs with placeholder tokens.
           The number of placeholder tokens equals the feature size of the
           multi-modal data outputted by the multi-modal encoder.
        3. Extract information about the placeholder tokens from the
           processed token IDs.
        """
        mm_items = self._to_mm_items(mm_data)

1762
1763
1764
        if tokenization_kwargs is None:
            tokenization_kwargs = {}

1765
1766
        (
            prompt_ids,
1767
            mm_info,
1768
1769
1770
1771
1772
            is_update_applied,
        ) = self._cached_apply_hf_processor(
            prompt,
            mm_items,
            hf_processor_mm_kwargs,
1773
            tokenization_kwargs=tokenization_kwargs,
1774
            mm_hash_overrides=mm_hash_overrides,
1775
1776
        )

1777
        # NOTE: tokenization_kwargs are not required to init processor
1778
1779
1780
        prompt_ids, prompt, mm_placeholders = self._maybe_apply_prompt_updates(
            mm_items=mm_items,
            prompt_ids=prompt_ids,
1781
1782
            mm_kwargs=mm_info.kwargs,
            mm_prompt_updates=mm_info.prompt_updates,
1783
1784
1785
            is_update_applied=is_update_applied,
        )

1786
1787
1788
1789
        mm_placeholder_ranges = {
            modality: [item.to_range() for item in placeholders]
            for modality, placeholders in mm_placeholders.items()
        }
1790

1791
        return MultiModalInputs(
1792
            type="multimodal",
1793
            prompt=prompt,
1794
            prompt_token_ids=prompt_ids,
1795
1796
            mm_kwargs=mm_info.kwargs,
            mm_hashes=mm_info.hashes,
1797
            mm_placeholders=mm_placeholder_ranges,
1798
        )
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808


class EncDecMultiModalProcessor(BaseMultiModalProcessor[_I]):

    @abstractmethod
    def create_encoder_prompt(
        self,
        prompt: Union[str, list[int]],
        mm_data: MultiModalDataDict,
    ) -> Union[str, list[int]]:
1809
        """
1810
        Create input prompt for the encoder. HF processor will be applied on
1811
1812
        this prompt during profiling and generation.
        """
1813
1814
        raise NotImplementedError

1815
1816
1817
1818
    @property
    def pad_dummy_encoder_prompt(self) -> bool:
        return False

1819
1820
1821
1822
1823
1824
1825
1826
    def create_decoder_prompt(
        self,
        prompt: Union[str, list[int]],
        mm_data: MultiModalDataDict,
    ) -> Union[str, list[int]]:
        """Create input prompt for the decoder."""
        return prompt

1827
    def _get_enc_dec_inputs(
1828
1829
1830
        self,
        prompt: Union[str, list[int]],
        mm_data: MultiModalDataDict,
1831
1832
        encoder_inputs: MultiModalInputs,
    ):
1833
        tokenizer = self.info.get_tokenizer()
1834
1835
        decoder_prompt = self.create_decoder_prompt(prompt, mm_data)
        if isinstance(decoder_prompt, str):
1836
            decoder_prompt_ids = encode_tokens(tokenizer,
1837
                                               decoder_prompt,
1838
1839
                                               add_special_tokens=False)
        else:
1840
1841
            decoder_prompt_ids = decoder_prompt
            decoder_prompt = decode_tokens(tokenizer, decoder_prompt)
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851

        mm_inputs = MultiModalEncDecInputs(
            encoder_prompt=encoder_inputs["prompt"],
            encoder_prompt_token_ids=encoder_inputs["prompt_token_ids"],
            **encoder_inputs)
        mm_inputs.update({
            "prompt": decoder_prompt,
            "prompt_token_ids": decoder_prompt_ids
        })
        return mm_inputs
1852
1853
1854
1855
1856
1857

    def apply(
        self,
        prompt: Union[str, list[int]],
        mm_data: MultiModalDataDict,
        hf_processor_mm_kwargs: Mapping[str, object],
1858
        tokenization_kwargs: Optional[Mapping[str, object]] = None,
1859
1860
        *,
        mm_hash_overrides: Optional[MultiModalHashes] = None,
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
    ) -> MultiModalEncDecInputs:
        """
        Process multi-modal inputs to be used in vLLM.
        The main processing steps are modified to fit encoder-decoder model:
        1. Create encoder prompt from input prompt text.
        2. Apply the HF processor on encoder prompt.
        3. Copy the input prompt text as decoder prompt inputs.
        """
        encoder_prompt = self.create_encoder_prompt(prompt, mm_data)
        encoder_inputs = super().apply(
            encoder_prompt,
            mm_data,
            hf_processor_mm_kwargs,
1874
            tokenization_kwargs,
1875
            mm_hash_overrides=mm_hash_overrides,
1876
1877
1878
1879
1880
1881
1882
        )

        return self._get_enc_dec_inputs(
            prompt=prompt,
            mm_data=mm_data,
            encoder_inputs=encoder_inputs,
        )