processor.py 57.5 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
from collections.abc import Callable, Generator, ItemsView, Iterable, Mapping, Sequence
6
from dataclasses import dataclass, field, replace
7
from enum import Enum
8
from functools import lru_cache
9
10
11
12
13
from typing import (
    TYPE_CHECKING,
    Generic,
    NamedTuple,
    Protocol,
14
    TypeAlias,
15
16
    cast,
)
17

18
import regex as re
19
import torch
20
from typing_extensions import TypeVar, assert_never, deprecated
21

22
from vllm.logger import init_logger
23
from vllm.tokenizers import TokenizerLike
24
from vllm.utils.collection_utils import flatten_2d_lists, full_groupby
25

26
from ..inputs import (
27
28
    MultiModalEncDecInputs,
    MultiModalFieldConfig,
29
    MultiModalHashes,
30
31
32
33
34
    MultiModalInputs,
    MultiModalKwargsItem,
    MultiModalKwargsItems,
    MultiModalKwargsOptionalItems,
    PlaceholderRange,
35
36
    mm_enc_dec_inputs,
    mm_inputs,
37
)
38
from ..parse import (
39
40
41
    DictEmbeddingItems,
    EmbeddingItems,
    MultiModalDataItems,
42
    MultiModalUUIDItems,
43
)
44
from .context import BaseProcessingInfo, TimingContext
45
from .dummy_inputs import BaseDummyInputsBuilder
46
from .inputs import ProcessorInputs
47
48

if TYPE_CHECKING:
49
50
    from transformers.feature_extraction_utils import BatchFeature

51
    from ..cache import BaseMultiModalProcessorCache
52
53
54
55
else:
    BatchFeature = object

    BaseMultiModalProcessorCache = object
56

57
logger = init_logger(__name__)
58
59

_S = TypeVar("_S", str, list[int])
60

61

62
PromptSeq: TypeAlias = str | list[int]
63
"""A token sequence (list of token IDs) or text."""
64

65

66
67
@lru_cache(maxsize=2048)
def _cached_encode(
68
    tokenizer: TokenizerLike,
69
70
    text: str,
    *,
71
    add_special_tokens: bool = True,
72
) -> list[int]:
73
    return tokenizer.encode(text, add_special_tokens=add_special_tokens)
74
75
76
77


@lru_cache(maxsize=2048)
def _cached_decode(
78
    tokenizer: TokenizerLike,
79
80
    token_ids: tuple[int, ...],
    *,
81
    skip_special_tokens: bool = False,
82
) -> str:
83
    return tokenizer.decode(list(token_ids), skip_special_tokens=skip_special_tokens)
84
85


86
87
88
89
90
91
def _seq2text(
    tokenizer: TokenizerLike | None,
    seq: PromptSeq,
    *,
    use_cache: bool = True,
) -> str:
92
93
94
    if isinstance(seq, str):
        return seq

95
96
97
98
    if tokenizer is None:
        raise ValueError("You cannot decode tokens when `skip_tokenizer_init=True`")

    if not use_cache:
99
        return tokenizer.decode(seq)
100

101
102
103
    return _cached_decode(tokenizer, tuple(seq))


104
105
106
107
108
109
def _seq2tokens(
    tokenizer: TokenizerLike | None,
    seq: PromptSeq,
    *,
    use_cache: bool = True,
) -> list[int]:
110
    if isinstance(seq, str):
111
112
113
114
        if tokenizer is None:
            raise ValueError("You cannot encode text when `skip_tokenizer_init=True`")

        if not use_cache:
115
            return tokenizer.encode(seq, add_special_tokens=False)
116

117
118
119
120
121
        return _cached_encode(tokenizer, seq, add_special_tokens=False)

    return seq


122
123
124
class _GetMatchIndex(Protocol):
    def __call__(
        self,
125
        tokenizer: TokenizerLike | None,
126
127
        prompt: PromptSeq,
        start_idx: int = 0,
128
    ) -> int | None: ...
129
130


131
132
133
@dataclass
class PromptIndex:
    """Resolves to an index in the prompt."""
134

135
    get_match_index: _GetMatchIndex
136
137
138
139
140
141
142
143
144
145


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.
        """
146
        return PromptIndex(lambda tokenizer, prompt, start_idx=0: 0)
147
148
149
150
151
152
153
154

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

        def get_match_index(
155
            tokenizer: TokenizerLike | None,
156
            prompt: PromptSeq,
157
            start_idx: int = 0,
158
        ) -> int | None:
159
160
161
            if start_idx != 0:
                return None

162
163
164
            prefix = seq

            if isinstance(prompt, str):
165
166
                # Make both `str`
                prefix = _seq2text(tokenizer, prefix, use_cache=False)
167
            else:
168
169
                # Make both `list[int]`
                prefix = _seq2tokens(tokenizer, prefix, use_cache=False)
170
171
172
173
174
175
176
177
178
179
180
181
182

            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.
        """
183
        return PromptIndex(lambda tokenizer, prompt, start_idx=0: len(prompt))
184
185


186
UpdateTarget: TypeAlias = PromptSeq | PromptIndex
187
188
189
190
"""
The token sequence or text to update.
"""

191
PromptUpdateTarget: TypeAlias = Callable[[int], UpdateTarget] | UpdateTarget
192
193
194
195
196
197
198
199
200
"""
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.
"""

201

202
@dataclass
203
class PromptUpdateDetails(Generic[_S]):
204
    """Details about the token sequence or text that are part of the update."""
205

206
    full: _S
207
    """The full content."""
208

209
    is_embed: Callable[[TokenizerLike | None, PromptSeq], torch.Tensor] | None = None
210
    """
211
212
213
    Given [`full`][vllm.multimodal.processing.PromptUpdateDetails.full],
    return a boolean mask of shape `(len(full),)` indicating which positions
    of `full` to assign embeddings to.
214
215
216
217

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

    The embeddings are obtained by calling
218
    [`SupportsMultiModal.embed_multimodal`][vllm.model_executor.models.interfaces.SupportsMultiModal.embed_multimodal].
219
220
221
    """

    @staticmethod
222
    def from_seq(seq: _S) -> "PromptUpdateDetails[_S]":
223
224
225
226
227
228
229
        return PromptUpdateDetails(full=seq)

    @staticmethod
    def select_text(
        seq: _S,
        embed_text: str,
    ) -> "PromptUpdateDetails[_S]":
230
231
        def is_embed(tokenizer: TokenizerLike | None, full: PromptSeq) -> torch.Tensor:
            embed_token_ids = _seq2tokens(tokenizer, embed_text, use_cache=False)
232
            token_ids = _seq2tokens(tokenizer, full)
233
234

            return torch.isin(
235
                torch.tensor(token_ids),
236
237
238
239
240
241
242
243
244
245
                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]":
246
        def is_embed(tokenizer: TokenizerLike | None, full: PromptSeq) -> torch.Tensor:
247
248
249
250
251
            token_ids = _seq2tokens(tokenizer, full)

            return torch.tensor(token_ids) == embed_token_id

        return PromptUpdateDetails(full=seq, is_embed=is_embed)
252

253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
    @staticmethod
    def select_token_ids(
        seq: _S,
        embed_token_ids: list[int],
    ) -> "PromptUpdateDetails[_S]":
        def is_embed(tokenizer: TokenizerLike | None, full: PromptSeq) -> torch.Tensor:
            token_ids = _seq2tokens(tokenizer, full)

            return torch.isin(
                torch.tensor(token_ids),
                torch.tensor(embed_token_ids),
            )

        return PromptUpdateDetails(full=seq, is_embed=is_embed)

268

269
PromptUpdateInfo: TypeAlias = PromptSeq | PromptUpdateDetails
270
"""
271
The token sequence or text that are part of the update.
272

273
If only part of the content corresponds to feature placeholders, you can
274
275
use [`PromptUpdateDetails`][vllm.multimodal.processing.PromptUpdateDetails] to
specify which part.
276
"""
277

278
PromptUpdateContent: TypeAlias = Callable[[int], PromptUpdateInfo] | PromptUpdateInfo
279
"""
280
281
Given the index of the processed item within
[`modality`][vllm.multimodal.processing.PromptUpdate.modality],
282
283
284
285
286
287
288
289
290
291
292
293
294
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
295
class PromptUpdate(ABC):
296
297
298
299
300
301
302
    """
    Defines how to update a prompt with placeholder tokens.
    """

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

303
    target: PromptUpdateTarget
304
305
306
307
308
309
310
311
312
313
314
315
316
317
    """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

318
    def _resolve_target(self, item_idx: int) -> UpdateTarget:
319
320
321
322
        target = self.target
        if callable(target):
            target = target(item_idx)

323
        return target
324

325
    def _resolve_content(self, item_idx: int) -> PromptUpdateDetails:
326
327
328
329
330
331
332
        content = self.content
        if callable(content):
            content = content(item_idx)

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

333
        return content
334

335
    def resolve(self, item_idx: int) -> "ResolvedPromptUpdate":
336
337
338
339
340
341
342
343
344
        """
        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,
345
346
            target=self._resolve_target(item_idx),
            content=self._resolve_content(item_idx),
347
348
        )

349

350
@dataclass
351
352
353
354
355
356
class PromptInsertion(PromptUpdate):
    """
    Defines how to insert placeholder tokens into a prompt.

    Example:

357
358
    For each image, insert a number of `<image>` feature placeholders
    equal to the feature size of the vision encoder after the `<s>` token:
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377

    ```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,
    )
    ```

378
    Insert these tokens after a prefix `Images:`:
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396

    ```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,
    )
    ```
397
398
399
400
    """

    insertion: PromptUpdateContent = field(repr=False)
    """
401
402
403
404
    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].
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420

    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):
421
422
    """
    Defines how to replace portions of an input prompt with placeholder tokens.
423
424
425

    Example:

426
427
    For each image, replace one `<image>` input placeholder in the prompt
    with a number of `<image>` feature placeholders
428
429
430
431
432
433
434
435
436
437
    equal to the feature size of the vision encoder:

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

438
439
    As above, but further pad the feature placeholders with `<image_bos>`
    and `<image_eos>`, which are not supposed to be passed to the vision
440
441
442
443
444
445
446
    encoder:

    ```python
    PromptReplacement(
        modality="image",
        target="<image>",
        replacement=PromptUpdateDetails(
447
448
449
450
451
452
453
            full="".join(
                [
                    "<image_bos>",
                    "<image>" * image_feature_size,
                    "<image_eos>",
                ]
            ),
454
455
456
457
458
459
460
461
462
463
464
465
466
            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(
467
468
469
            full=(
                [image_bos_id] + [image_token_id] * image_feature_size + [image_eos_id]
            ),
470
471
472
473
            features=[image_token_id] * image_feature_size,
        ),
    )
    ```
474
475
    """

476
    replacement: PromptUpdateContent = field(repr=False)
477
    """
478
479
480
481
    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].
482

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

487
488
489
490
491
492
493
    @property
    def content(self) -> PromptUpdateContent:
        return self.replacement

    @property
    def mode(self) -> UpdateMode:
        return UpdateMode.REPLACE
494
495


496
497
498
class _HasModalityAttr(Protocol):
    modality: str

499

500
501
class _HasModalityProp(Protocol):
    @property
502
    def modality(self) -> str: ...
503
504


505
_M = TypeVar("_M", bound=_HasModalityAttr | _HasModalityProp)
506
507
508


def full_groupby_modality(values: Iterable[_M]) -> ItemsView[str, list[_M]]:
509
510
    """
    Convenience function to apply
511
    [`full_groupby`][vllm.utils.collection_utils.full_groupby]
512
513
    based on modality.
    """
514
515
516
    return full_groupby(values, key=lambda x: x.modality)


517
518
519
520
521
522
523
class PromptTargetMatch(NamedTuple):
    start_idx: int
    end_idx: int


@dataclass(frozen=True)
class ResolvedPromptUpdate:
524
    """
525
526
    A [`PromptUpdate`][vllm.multimodal.processing.PromptUpdate] with its
    lazy attributes resolved, apart from those related to tokenization.
527
    """
528

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

532
533
    item_idx: int
    """The index within `modality` of the item this update pertains to."""
534

535
536
    mode: UpdateMode
    """Defines how to update the prompt."""
537

538
    target: UpdateTarget
539
    """The token sequence (or text) to update."""
540

541
    content: PromptUpdateDetails = field(repr=False)
542
    """The placeholder tokens that are part of the update."""
543

544
545
546
    def iter_token_matches(
        self,
        prompt: list[int],
547
        tokenizer: TokenizerLike | None,
548
549
550
551
552
        *,
        start_idx: int = 0,
    ) -> Generator[PromptTargetMatch]:
        """Yield each instance of `self.target` found in `prompt`."""
        target = self.target
553

554
555
556
557
        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)
558

559
            return
560

561
562
        target_token_ids = _seq2tokens(tokenizer, target)

563
        for match in iter_token_matches(prompt, target_token_ids, start_idx=start_idx):
564
            yield PromptTargetMatch(match.start_idx, match.end_idx)
565

566
567
568
    def iter_text_matches(
        self,
        prompt: str,
569
        tokenizer: TokenizerLike | None,
570
571
572
573
574
        *,
        start_idx: int = 0,
    ) -> Generator[PromptTargetMatch]:
        """Yield each instance of `self.target` found in `prompt`."""
        target = self.target
575

576
577
578
579
        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)
580

581
            return
582

583
584
        target_text = _seq2text(tokenizer, target)

585
        for match in re.finditer(re.escape(target_text), prompt, pos=start_idx):
586
587
588
589
            yield PromptTargetMatch(match.start(), match.end())

    def iter_matches(
        self,
590
        prompt: list[int] | str,
591
        tokenizer: TokenizerLike | None,
592
593
594
595
596
        *,
        start_idx: int = 0,
    ) -> Generator[PromptTargetMatch]:
        """Yield each instance of `self.target` found in `prompt`."""
        if isinstance(prompt, str):
597
            return self.iter_text_matches(prompt, tokenizer, start_idx=start_idx)
598
599

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

601
602
603
604
605
606
607
608
609
    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)

610

611
612
613
class _TokenMatch(NamedTuple):
    start_idx: int
    end_idx: int
614
615


616
617
618
def iter_token_matches(
    token_ids: list[int],
    match_ids: list[int],
619
620
    *,
    start_idx: int = 0,
621
) -> Generator[_TokenMatch]:
622
    """
623
    Yield each occurrence of `match_ids` in `token_ids`.
624
625
626
627

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

630
631
    if match_len == 0:
        return
632

633
    while start_idx < prompt_len - match_len + 1:
634
        end_idx = start_idx + match_len
635

636
637
        if token_ids[start_idx:end_idx] == match_ids:
            yield _TokenMatch(start_idx=start_idx, end_idx=end_idx)
638
639
640
641
642

            # Exclude overlapping matches
            start_idx = end_idx
        else:
            start_idx += 1
643
644


645
646
647
648
649
650
def replace_token_matches(
    token_ids: list[int],
    match_ids: list[int],
    new_ids: list[int],
) -> list[int]:
    """
651
652
    Replace each occurrence of `match_ids` in `token_ids`
    with `new_ids`.
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671

    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)


672
@dataclass
673
class PlaceholderFeaturesInfo:
674
    modality: str
675
    item_idx: int
676
    start_idx: int
677
    tokens: list[int]
678
    is_embed: torch.Tensor | None
679
680
681

    @property
    def length(self) -> int:
682
        return len(self.tokens)
683
684

    def to_range(self) -> PlaceholderRange:
685
686
        # TODO: Is it worth it to optimize this by stripping the
        # leading and ending positions where `is_embed=False`?
687
688
689
        return PlaceholderRange(
            offset=self.start_idx,
            length=self.length,
690
            is_embed=self.is_embed,
691
        )
692
693


694
_MatchToApply = tuple[tuple[str, int], tuple[PromptTargetMatch, int]]
695
696


697
698
699
def _find_matches(
    prompt: _S,
    mm_prompt_updates: "MultiModalPromptUpdates",
700
    tokenizer: TokenizerLike | None,
701
702
703
    *,
    prev_end_idx: int = 0,
    current_result: "MultiModalPromptUpdatesApplyResult",
704
705
) -> tuple[UpdateMode | None, list[_MatchToApply]]:
    mode: UpdateMode | None = None
706
707
708
709
710
711
712
713
714
715
716
717
    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(
718
719
720
                    prompt,
                    tokenizer,
                    start_idx=prev_end_idx,
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
                ):
                    # 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
750
751


752
753
754
755
756
757
758
759
760
761
def _all_items_found(
    mm_item_counts: dict[str, int],
    mm_found_counts: dict[str, int],
) -> bool:
    return all(
        item_idx >= mm_item_counts[modality]
        for modality, item_idx in mm_found_counts.items()
    )


762
def _apply_matches(
763
    prompt: _S,
764
    mm_prompt_updates: "MultiModalPromptUpdates",
765
    tokenizer: TokenizerLike | None,
766
) -> tuple[list[_S], "MultiModalPromptUpdatesApplyResult"]:
767
    mm_item_counts = {m: len(items) for m, items in mm_prompt_updates.items()}
768

769
    out_seqs = list[str | list[int]]()
770
    out_result: MultiModalPromptUpdatesApplyResult = {
771
        m: [None] * len(items) for m, items in mm_prompt_updates.items()
772
    }
773

774
    # Early exit if no items to find
775
776
777
778
779
780
    mm_found_counts = {
        m: sum(r is not None for r in res) for m, res in out_result.items()
    }
    if _all_items_found(mm_item_counts, mm_found_counts):
        return [prompt], out_result

781
782
    prev_end_idx = 0
    while True:
783
784
785
786
787
788
789
        mode, matches_to_apply = _find_matches(
            prompt,
            mm_prompt_updates,
            tokenizer,
            prev_end_idx=prev_end_idx,
            current_result=out_result,
        )
790

791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
        if mode is None:
            break  # No more matches to find

        for (modality, item_idx), (match, update_idx) in matches_to_apply:
            matched_update = mm_prompt_updates[modality][item_idx][update_idx]
            matched_content = matched_update.content.full

            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)

            out_seqs.append(prompt[prev_end_idx:end_idx_to_insert])
            out_seqs.append(
                _seq2text(tokenizer, matched_content)
                if isinstance(prompt, str)
                else _seq2tokens(tokenizer, matched_content)
            )
            out_result[modality][item_idx] = update_idx

            # Exclude overlapping matches
            prev_end_idx = match.end_idx

        # Early exit if all items found
        mm_found_counts = {
            m: sum(r is not None for r in res) for m, res in out_result.items()
        }
        if _all_items_found(mm_item_counts, mm_found_counts):
            break
822
823
824

    out_seqs.append(prompt[prev_end_idx:])

825
    return cast(list[_S], out_seqs), out_result
826
827


828
def apply_token_matches(
829
    prompt: list[int],
830
    mm_prompt_updates: "MultiModalPromptUpdates",
831
    tokenizer: TokenizerLike | None,
832
833
834
) -> tuple[list[int], "MultiModalPromptUpdatesApplyResult"]:
    """
    Apply the updates in `mm_prompt_updates` to `prompt`.
835

836
837
838
839
    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.
    """
840
    token_id_seqs, result = _apply_matches(prompt, mm_prompt_updates, tokenizer)
841

842
    return flatten_2d_lists(token_id_seqs), result
843
844


845
def apply_text_matches(
846
    prompt: str,
847
    mm_prompt_updates: "MultiModalPromptUpdates",
848
    tokenizer: TokenizerLike | None,
849
850
851
) -> tuple[str, "MultiModalPromptUpdatesApplyResult"]:
    """
    Apply the updates in `mm_prompt_updates` to `prompt`.
852

853
854
855
856
857
    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)
858

859
    return "".join(texts), result
860
861


862
def _iter_placeholders(
863
    prompt: list[int],
864
    mm_prompt_updates: "MultiModalPromptUpdates",
865
    tokenizer: TokenizerLike | None,
866
) -> Iterable[PlaceholderFeaturesInfo]:
867
    """
868
    Yield each set of placeholder tokens found in `prompt`.
869
870
871

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

874
875
    Note that empty matches are ignored.
    """
876
    mm_item_counts = {m: len(items) for m, items in mm_prompt_updates.items()}
877
    item_idx_by_modality = {modality: 0 for modality in mm_prompt_updates}
878

879
880
    if _all_items_found(mm_item_counts, item_idx_by_modality):
        return
881

882
    prompt_len = len(prompt)
883
    start_idx = 0
884

885
886
887
    while start_idx < prompt_len:
        found = False

888
        for modality, modality_updates in mm_prompt_updates.items():
889
890
            item_idx = item_idx_by_modality[modality]
            if item_idx >= mm_item_counts.get(modality, 0):
891
                continue
892

893
894
            for update in modality_updates[item_idx]:
                content = update.content
895
                content_tokens_full = _seq2tokens(tokenizer, content.full)
896
897
                content_len_full = len(content_tokens_full)
                end_idx_full = start_idx + content_len_full
898

899
                if content_len_full == 0 or end_idx_full > prompt_len:
900
901
                    continue

902
                if prompt[start_idx:end_idx_full] == content_tokens_full:
903
904
                    content_is_embed = content.is_embed
                    if content_is_embed is not None:
905
                        content_is_embed = content_is_embed(tokenizer, content.full)
906
907
908
909
910
911
912
913

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

915
                    # Exclude overlapping matches
916
                    start_idx = end_idx_full
917
918
919
                    item_idx_by_modality[modality] += 1
                    found = True
                    break
920

921
            if found:
922
923
924
                if _all_items_found(mm_item_counts, item_idx_by_modality):
                    return

925
                break  # Go back to the outer while loop
926
927
928

        if not found:
            start_idx += 1
929
930


931
932
def find_mm_placeholders(
    prompt: list[int],
933
    mm_prompt_updates: "MultiModalPromptUpdates",
934
    tokenizer: TokenizerLike | None,
935
) -> Mapping[str, list[PlaceholderFeaturesInfo]]:
936
    it = _iter_placeholders(prompt, mm_prompt_updates, tokenizer)
937
938
939
    return dict(full_groupby_modality(it))


940
941
942
MultiModalIsCached = dict[str, list[bool]]
"""
A collection of the `is_cached` flag for each item, with a similar structure as
943
[`MultiModalKwargsItems`][vllm.multimodal.inputs.MultiModalKwargsItems].
944
945
"""

946
MultiModalPromptUpdates = Mapping[str, list[Sequence[ResolvedPromptUpdate]]]
947
948
949
950
951
"""
A collection of prompt updates with a similar structure as
[`MultiModalKwargsItems`][vllm.multimodal.inputs.MultiModalKwargsItems].
"""

952
MultiModalPromptUpdatesApplyResult = Mapping[str, list[int | None]]
953
954
955
956
957
958
959
"""
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.
"""

960
961
_I = TypeVar("_I", bound=BaseProcessingInfo)

962
963

class MultiModalProcessingInfo(NamedTuple):
964
    kwargs: MultiModalKwargsOptionalItems
965
    hashes: MultiModalHashes
966
967
    prompt_updates: MultiModalPromptUpdates

968
969

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

973
    Not to be confused with `transformers.ProcessorMixin`.
974
975
    """

976
977
978
979
980
    def __init__(
        self,
        info: _I,
        dummy_inputs: "BaseDummyInputsBuilder[_I]",
        *,
981
        cache: BaseMultiModalProcessorCache | None = None,
982
    ) -> None:
983
984
        super().__init__()

985
986
        self.info = info
        self.dummy_inputs = dummy_inputs
987
        self.cache = cache
988

989
        # TODO: Remove in v0.18
990
        if hasattr(self, "_get_data_parser"):
991
992
993
994
            raise ValueError(
                "BaseMultiModalProcessor._get_data_parser has been "
                "moved to `BaseProcessingInfo.build_data_parser` in v0.16. "
                "You should override `BaseProcessingInfo.build_data_parser` instead."
995
996
            )

997
        self.data_parser = self.info.get_data_parser()
998

999
    @property
1000
    @deprecated("Will be removed in v0.17. Use `info.supported_mm_limits` instead.")
1001
    def supported_mm_limits(self):
1002
        return self.info.supported_mm_limits
1003
1004

    @property
1005
    @deprecated("Will be removed in v0.17. Use `info.allowed_mm_limits` instead.")
1006
    def allowed_mm_limits(self):
1007
        return self.info.allowed_mm_limits
1008

1009
    def __call__(
1010
        self,
1011
        prompt: str,
1012
        mm_items: MultiModalDataItems,
1013
1014
        mm_uuid_items: MultiModalUUIDItems | None = None,
        hf_processor_mm_kwargs: Mapping[str, object] | None = None,
1015
    ) -> MultiModalInputs:
1016
        processor_inputs = ProcessorInputs(
1017
1018
1019
            prompt,
            mm_items,
            mm_uuid_items,
1020
            hf_processor_mm_kwargs=hf_processor_mm_kwargs or {},
1021
        )
1022

1023
1024
        return self.apply(processor_inputs, TimingContext(enabled=False))

1025
1026
1027
    @abstractmethod
    def _get_mm_fields_config(
        self,
1028
        hf_inputs: BatchFeature,
1029
1030
1031
1032
1033
        hf_processor_mm_kwargs: Mapping[str, object],
    ) -> Mapping[str, MultiModalFieldConfig]:
        """Given the HF-processed data, output the metadata of each field."""
        raise NotImplementedError

1034
    @abstractmethod
1035
    def _get_prompt_updates(
1036
        self,
1037
        mm_items: MultiModalDataItems,
1038
        hf_processor_mm_kwargs: Mapping[str, object],
1039
        out_mm_kwargs: MultiModalKwargsItems,
1040
    ) -> Sequence[PromptUpdate]:
1041
1042
        """
        Given the original multi-modal items for this modality
1043
        and HF-processed data, output the updates to perform.
1044

1045
1046
1047
1048
1049
1050
        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
1051
1052
        in order to construct
        [`PlaceholderRange`][vllm.multimodal.inputs.PlaceholderRange]
1053
        for each multi-modal item.
1054
1055
        """
        raise NotImplementedError
1056

1057
1058
1059
1060
1061
1062
    def _bind_and_group_updates(
        self,
        prompt_updates: Sequence[PromptUpdate],
        mm_item_counts: Mapping[str, int],
    ) -> MultiModalPromptUpdates:
        return {
1063
1064
1065
1066
            modality: [
                [update.resolve(item_idx) for update in updates]
                for item_idx in range(mm_item_counts.get(modality, 0))
            ]
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
            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

1104
    def _find_mm_placeholders(
1105
1106
        self,
        new_token_ids: list[int],
1107
        mm_prompt_updates: MultiModalPromptUpdates,
1108
    ) -> Mapping[str, list[PlaceholderFeaturesInfo]]:
1109
1110
        tokenizer = self.info.get_tokenizer()

1111
        return find_mm_placeholders(new_token_ids, mm_prompt_updates, tokenizer)
1112

1113
    def _get_hf_mm_data(
1114
        self,
1115
        mm_items: MultiModalDataItems,
1116
    ) -> tuple[Mapping[str, object], Mapping[str, object]]:
1117
        """Extract processor and passthrough data from multi-modal items."""
1118
1119
        processor_data = dict[str, object]()
        passthrough_data = dict[str, object]()
1120

1121
1122
1123
        for items in mm_items.values():
            processor_data.update(items.get_processor_data())
            passthrough_data.update(items.get_passthrough_data())
1124

1125
1126
        return processor_data, passthrough_data

1127
1128
1129
    def _call_hf_processor(
        self,
        prompt: str,
1130
1131
1132
1133
        # 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],
1134
        tok_kwargs: Mapping[str, object],
1135
    ) -> BatchFeature:
1136
1137
1138
1139
        """
        Call the HF processor on the prompt text and
        associated multi-modal data.
        """
1140
1141
1142
1143
1144
        return self.info.ctx.call_hf_processor(
            self.info.get_hf_processor(**mm_kwargs),
            dict(text=prompt, **mm_data),
            dict(**mm_kwargs, **tok_kwargs),
        )
1145

1146
    def _hf_processor_applies_updates(
1147
1148
1149
1150
        self,
        prompt_text: str,
        mm_items: MultiModalDataItems,
        hf_processor_mm_kwargs: Mapping[str, object],
1151
        tokenization_kwargs: Mapping[str, object],
1152
1153
    ) -> bool:
        """
1154
        Return whether the HF processor applies prompt updates.
1155

1156
1157
        For most HF processors, this should be `True` when multi-modal
        data items are passed, but `False` when multi-modal embeddings
1158
1159
1160
1161
        are passed.
        """
        return not any(
            isinstance(items, (EmbeddingItems, DictEmbeddingItems))
1162
1163
            for items in mm_items.values()
        )
1164

1165
    def _apply_hf_processor_text_mm(
1166
        self,
1167
        prompt_text: str,
1168
        mm_items: MultiModalDataItems,
1169
        hf_processor_mm_kwargs: Mapping[str, object],
1170
        tokenization_kwargs: Mapping[str, object],
1171
    ) -> tuple[list[int], BatchFeature, bool]:
1172
        """
1173
1174
        Apply the HF processor on the prompt text and multi-modal data
        together.
1175

1176
        In addition, return whether prompt updates have been applied.
1177
        """
1178
1179
1180
1181
        valid_mm_items = mm_items.select(
            {k for k, c in mm_items.get_all_counts().items() if c > 0}
        )
        processor_data, passthrough_data = self._get_hf_mm_data(valid_mm_items)
1182
1183
1184
1185
1186

        processed_data = self._call_hf_processor(
            prompt=prompt_text,
            mm_data=processor_data,
            mm_kwargs=hf_processor_mm_kwargs,
1187
            tok_kwargs=tokenization_kwargs,
1188
1189
        )
        processed_data.update(passthrough_data)
1190

1191
        (prompt_ids,) = processed_data.pop("input_ids").tolist()
1192

1193
        is_update_applied = self._hf_processor_applies_updates(
1194
1195
1196
            prompt_text=prompt_text,
            mm_items=mm_items,
            hf_processor_mm_kwargs=hf_processor_mm_kwargs,
1197
            tokenization_kwargs=tokenization_kwargs,
1198
1199
        )

1200
        return prompt_ids, processed_data, is_update_applied
1201

1202
    def _apply_hf_processor_text_only(
1203
1204
1205
1206
        self,
        prompt_text: str,
        tokenization_kwargs: Mapping[str, object],
    ) -> list[int]:
1207
        """
1208
        Apply the HF processor on the prompt text only.
1209

1210
1211
1212
        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.
1213
        """
1214
        prompt_ids, _, _ = self._apply_hf_processor_text_mm(
1215
1216
1217
            prompt_text=prompt_text,
            mm_items=MultiModalDataItems({}),
            hf_processor_mm_kwargs={},
1218
            tokenization_kwargs=tokenization_kwargs,
1219
1220
        )

1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
        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
1233
1234
1235
        with the output of
        [`_apply_hf_processor_text_only`][vllm.multimodal.processing.BaseMultiModalProcessor._apply_hf_processor_text_only]
        on the
1236
1237
1238
1239
1240
1241
1242
1243
        corresponding text.
        """
        return prompt_tokens

    def _apply_hf_processor_mm_only(
        self,
        mm_items: MultiModalDataItems,
        hf_processor_mm_kwargs: Mapping[str, object],
1244
        tokenization_kwargs: Mapping[str, object],
1245
    ) -> BatchFeature:
1246
1247
1248
1249
1250
        """
        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
1251
        [`DummyInputsBuilder`][vllm.multimodal.processing.BaseDummyInputsBuilder]
1252
        to go along with the multi-modal data.
1253
1254
1255
        """
        mm_counts = mm_items.get_all_counts()

1256
        _, mm_processed_data, _ = self._apply_hf_processor_text_mm(
1257
            prompt_text=self.dummy_inputs.get_dummy_text(mm_counts),
1258
1259
            mm_items=mm_items,
            hf_processor_mm_kwargs=hf_processor_mm_kwargs,
1260
            tokenization_kwargs=tokenization_kwargs,
1261
1262
        )

1263
        return mm_processed_data
1264
1265
1266

    def _apply_hf_processor_main(
        self,
1267
        prompt: str | list[int],
1268
1269
        mm_items: MultiModalDataItems,
        hf_processor_mm_kwargs: Mapping[str, object],
1270
        tokenization_kwargs: Mapping[str, object],
1271
        *,
1272
        enable_hf_prompt_update: bool,
1273
    ) -> tuple[list[int], BatchFeature, bool]:
1274
1275
1276
        """
        Apply the HF processor on the prompt text and multi-modal data.

1277
        In addition, return whether prompt updates have been applied
1278
        (for most HF processors, this should be `True`).
1279

1280
        Note:
1281
            If `enable_hf_prompt_update=False`, we use HF processor
1282
            to perform prompt updates if available; HF processor requires
1283
            that the prompt corresponds to multi-modal items.
1284
1285
        """
        if isinstance(prompt, str):
1286
            if enable_hf_prompt_update:
1287
1288
1289
1290
                return self._apply_hf_processor_text_mm(
                    prompt_text=prompt,
                    mm_items=mm_items,
                    hf_processor_mm_kwargs=hf_processor_mm_kwargs,
1291
                    tokenization_kwargs=tokenization_kwargs,
1292
1293
                )

1294
            prompt_ids = self._apply_hf_processor_text_only(prompt, tokenization_kwargs)
1295
1296
1297
        else:
            prompt_ids = self._apply_hf_processor_tokens_only(prompt)

1298
        mm_processed_data = self._apply_hf_processor_mm_only(
1299
            mm_items=mm_items,
1300
            hf_processor_mm_kwargs=hf_processor_mm_kwargs,
1301
            tokenization_kwargs=tokenization_kwargs,
1302
1303
        )

1304
        return prompt_ids, mm_processed_data, False
1305

1306
1307
    def _get_cache_missing_items(
        self,
1308
        cache: BaseMultiModalProcessorCache,
1309
1310
        mm_data_items: MultiModalDataItems,
        mm_hashes: MultiModalHashes,
1311
    ) -> tuple[MultiModalIsCached, MultiModalDataItems]:
1312
        mm_is_cached = {
1313
            modality: cache.is_cached(hashes) for modality, hashes in mm_hashes.items()
1314
1315
1316
1317
        }

        mm_missing_idxs = {
            modality: [
1318
1319
                idx
                for idx, item_is_cached in enumerate(items_is_cached)
1320
1321
1322
1323
                if not item_is_cached
            ]
            for modality, items_is_cached in mm_is_cached.items()
        }
1324

1325
1326
1327
1328
1329
1330
1331
1332
        mm_missing_data = {}
        for modality, idxs in mm_missing_idxs.items():
            missing_modality_data = []
            for idx in idxs:
                data = mm_data_items[modality][idx]
                if data is None:
                    raise ValueError(
                        f"Cache miss for {modality} at index {idx} "
1333
1334
                        f"but data is not provided."
                    )
1335
1336
1337
                else:
                    missing_modality_data.append(data)
            mm_missing_data[modality] = missing_modality_data
1338

1339
        mm_missing_items = self.info.parse_mm_data(mm_missing_data, validate=False)
1340
1341

        return mm_is_cached, mm_missing_items
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353

    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)

1354
1355
    def _merge_mm_kwargs(
        self,
1356
        cache: BaseMultiModalProcessorCache,
1357
        mm_hashes: MultiModalHashes,
1358
        mm_is_cached: MultiModalIsCached,
1359
        mm_missing_kwargs: MultiModalKwargsItems,
1360
1361
        mm_missing_prompt_updates: MultiModalPromptUpdates,
    ) -> tuple[MultiModalKwargsOptionalItems, MultiModalPromptUpdates]:
1362
1363
1364
1365
1366
        # Need to touch all mm hashes before update to avoid hash in updated
        # list evict during update
        for hashes in mm_hashes.values():
            for item_hash in hashes:
                cache.touch_sender_cache_item(item_hash)
1367

1368
        mm_missing_next_idx = defaultdict[str, int](lambda: 0)
1369

1370
        merged_kwargs = defaultdict[str, list[MultiModalKwargsItem | None]](list)
1371
1372
1373
        merged_prompt_updates = defaultdict[str, list[Sequence[ResolvedPromptUpdate]]](
            list
        )
1374
1375
        for modality, hashes in mm_hashes.items():
            missing_kwargs = mm_missing_kwargs.get(modality, [])
1376
            missing_prompt_updates = mm_missing_prompt_updates.get(modality, [])
1377
1378
1379
1380

            for item_idx, item_hash in enumerate(hashes):
                if not mm_is_cached[modality][item_idx]:
                    missing_next_idx = mm_missing_next_idx[modality]
1381
1382
                    missing_kwargs_item = missing_kwargs[missing_next_idx]
                    missing_updates_item = missing_prompt_updates[missing_next_idx]
1383

1384
                    mm_missing_next_idx[modality] += 1
1385

1386
                    item = missing_kwargs_item, missing_updates_item
1387
                else:
1388
1389
1390
1391
1392
                    item = None

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

                merged_kwargs[modality].append(kwargs)
1393
1394
1395
1396
1397
1398
                merged_prompt_updates[modality].append(
                    [
                        self._recompute_cached_prompt_update(update, item_idx)
                        for update in updates
                    ]
                )
1399

1400
1401
        mm_kwargs = MultiModalKwargsItems(merged_kwargs)
        mm_prompt_updates = dict(merged_prompt_updates)
1402

1403
        return mm_kwargs, mm_prompt_updates
1404
1405
1406

    def _apply_hf_processor(
        self,
1407
1408
        inputs: ProcessorInputs,
        timing_ctx: TimingContext,
1409
    ) -> tuple[list[int], MultiModalProcessingInfo, bool]:
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
        with timing_ctx.record("apply_hf_processor"):
            (
                prompt_ids,
                mm_processed_data,
                is_update_applied,
            ) = self._apply_hf_processor_main(
                prompt=inputs.prompt,
                mm_items=inputs.mm_data_items,
                hf_processor_mm_kwargs=inputs.hf_processor_mm_kwargs,
                tokenization_kwargs=inputs.tokenization_kwargs,
                enable_hf_prompt_update=True,
            )
1422

1423
        mm_kwargs = MultiModalKwargsItems.from_hf_inputs(
1424
            mm_processed_data,
1425
1426
1427
            self._get_mm_fields_config(
                mm_processed_data, inputs.hf_processor_mm_kwargs
            ),
1428
1429
        )

1430
        # Use overrides if provided; fallback to data-dependent hashing.
1431
1432
        with timing_ctx.record("get_mm_hashes"):
            mm_hashes = inputs.get_mm_hashes(self.info.model_id)
1433

1434
        mm_prompt_updates = self._get_mm_prompt_updates(
1435
1436
            inputs.mm_data_items,
            inputs.hf_processor_mm_kwargs,
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
            mm_kwargs,
        )

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

        return prompt_ids, mm_info, is_update_applied
1447

1448
1449
    def _cached_apply_hf_processor(
        self,
1450
1451
        inputs: ProcessorInputs,
        timing_ctx: TimingContext,
1452
    ) -> tuple[list[int], MultiModalProcessingInfo, bool]:
1453
1454
1455
1456
1457
1458
        """
        Apply the HF processor on the full prompt text,
        caching the results and reusing cached results.
        """
        cache = self.cache

1459
        _, passthrough_data = self._get_hf_mm_data(inputs.mm_data_items)
1460
        if cache is None or passthrough_data:
1461
            return self._apply_hf_processor(inputs, timing_ctx)
1462

1463
1464
        with timing_ctx.record("get_mm_hashes"):
            mm_hashes = inputs.get_mm_hashes(self.info.model_id)
1465

1466
        with timing_ctx.record("get_cache_missing_items"):
1467
1468
            mm_is_cached, mm_missing_data_items = self._get_cache_missing_items(
                cache=cache,
1469
                mm_data_items=inputs.mm_data_items,
1470
1471
                mm_hashes=mm_hashes,
            )
1472

1473
        # NOTE: `prompt` does not correspond to `mm_missing_data_items`,
1474
        # so we can't apply prompt updates until the new multimodal
1475
        # items are combined with the cached multimodal items
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
        with timing_ctx.record("apply_hf_processor"):
            (
                prompt_ids,
                mm_missing_processed_data,
                is_update_applied,
            ) = self._apply_hf_processor_main(
                prompt=inputs.prompt,
                mm_items=mm_missing_data_items,
                hf_processor_mm_kwargs=inputs.hf_processor_mm_kwargs,
                tokenization_kwargs=inputs.tokenization_kwargs,
                enable_hf_prompt_update=False,
            )
1488

1489
        mm_missing_kwargs = MultiModalKwargsItems.from_hf_inputs(
1490
            mm_missing_processed_data,
1491
            self._get_mm_fields_config(
1492
                mm_missing_processed_data, inputs.hf_processor_mm_kwargs
1493
            ),
1494
1495
        )

1496
1497
        mm_missing_prompt_updates = self._get_mm_prompt_updates(
            mm_missing_data_items,
1498
            inputs.hf_processor_mm_kwargs,
1499
            mm_missing_kwargs,
1500
        )
1501

1502
        with timing_ctx.record("merge_mm_kwargs"):
1503
1504
1505
1506
1507
1508
1509
            mm_kwargs, mm_prompt_updates = self._merge_mm_kwargs(
                cache,
                mm_hashes=mm_hashes,
                mm_is_cached=mm_is_cached,
                mm_missing_kwargs=mm_missing_kwargs,
                mm_missing_prompt_updates=mm_missing_prompt_updates,
            )
1510
1511
1512

        mm_info = MultiModalProcessingInfo(
            kwargs=mm_kwargs,
1513
            hashes=mm_hashes,
1514
1515
            prompt_updates=mm_prompt_updates,
        )
1516

1517
        return prompt_ids, mm_info, is_update_applied
1518

1519
1520
1521
    def _apply_token_matches(
        self,
        prompt: list[int],
1522
1523
1524
1525
        mm_prompt_updates: MultiModalPromptUpdates,
    ) -> tuple[list[int], MultiModalPromptUpdatesApplyResult]:
        tokenizer = self.info.get_tokenizer()
        return apply_token_matches(prompt, mm_prompt_updates, tokenizer)
1526
1527
1528
1529

    def _apply_text_matches(
        self,
        prompt: str,
1530
1531
1532
1533
        mm_prompt_updates: MultiModalPromptUpdates,
    ) -> tuple[str, MultiModalPromptUpdatesApplyResult]:
        tokenizer = self.info.get_tokenizer()
        return apply_text_matches(prompt, mm_prompt_updates, tokenizer)
1534

1535
    def _apply_prompt_updates(
1536
1537
        self,
        token_ids: list[int],
1538
        mm_prompt_updates: MultiModalPromptUpdates,
1539
    ) -> tuple[list[int], Mapping[str, list[PlaceholderFeaturesInfo]]]:
1540
        """Apply multi-modal prompt updates to token IDs."""
1541
        tokenizer = self.info.get_tokenizer()
1542

1543
1544
1545
1546
        new_token_ids, match_result = self._apply_token_matches(
            token_ids,
            mm_prompt_updates,
        )
1547
1548
1549
1550
1551
1552
1553
1554
1555

        # 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
1556
1557
        # of the search text in the prompt, we instead perform string-based
        # updates on the decoded token IDs, then encode them back.
1558
        if not all(
1559
1560
1561
            all(update_idx is not None for update_idx in update_idxs)
            for update_idxs in match_result.values()
        ):
1562
            new_text, match_result = self._apply_text_matches(
1563
                _seq2text(tokenizer, token_ids, use_cache=False),
1564
                mm_prompt_updates,
1565
1566
            )

1567
            new_token_ids = _seq2tokens(tokenizer, new_text, use_cache=False)
1568

1569
        matched_updates = defaultdict[str, list[Sequence[ResolvedPromptUpdate]]](list)
1570
1571
1572
1573
        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 "
1574
1575
                    f"mm_items[{modality!r}][{item_idx}]"
                )
1576
1577

                matched_updates[modality].append(
1578
1579
                    [mm_prompt_updates[modality][item_idx][update_idx]]
                )
1580
1581

        placeholders = self._find_mm_placeholders(
1582
1583
            new_token_ids,
            dict(matched_updates),
1584
        )
1585

1586
        return new_token_ids, placeholders
1587

1588
1589
    def _validate_mm_kwargs(
        self,
1590
        mm_kwargs: MultiModalKwargsOptionalItems,
1591
1592
1593
        mm_item_counts: Mapping[str, int],
    ) -> None:
        for modality, item_count in mm_item_counts.items():
1594
            items = mm_kwargs.get(modality, [])
1595
1596
1597
1598
1599
1600
1601
1602
1603

            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 "
1604
1605
                    "`_call_hf_processor` and `_get_mm_fields_config`)."
                )
1606

1607
    def _validate_mm_updates(
1608
        self,
1609
        mm_updates: MultiModalPromptUpdates,
1610
        mm_item_counts: Mapping[str, int],
1611
    ) -> None:
1612
        for modality, item_count in mm_item_counts.items():
1613
            placeholders = mm_updates.get(modality, [])
1614

1615
            if len(placeholders) != item_count:
1616
                raise RuntimeError(
1617
                    f"Expected there to be {item_count} prompt updates "
1618
                    f"corresponding to {item_count} {modality} items, but "
1619
                    f"instead found {len(placeholders)} prompt updates! "
1620
1621
1622
                    "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 "
1623
1624
                    "sure you have applied it before calling `LLM.generate`."
                )
1625

1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
    def _validate_mm_placeholders(
        self,
        mm_placeholders: Mapping[str, list[PlaceholderFeaturesInfo]],
        mm_item_counts: Mapping[str, int],
    ) -> None:
        for modality, item_count in mm_item_counts.items():
            placeholders = mm_placeholders.get(modality, [])

            if len(placeholders) != item_count:
                raise RuntimeError(
                    f"Expected there to be {item_count} prompt placeholders "
                    f"corresponding to {item_count} {modality} items, but "
                    f"instead found {len(placeholders)} prompt placeholders! "
                    "Make sure the implementation of `_call_hf_processor` and "
1640
1641
                    "`_get_mm_fields_config` are consistent with each other."
                )
1642

1643
1644
1645
1646
    def _maybe_apply_prompt_updates(
        self,
        mm_items: MultiModalDataItems,
        prompt_ids: list[int],
1647
        mm_kwargs: MultiModalKwargsOptionalItems,
1648
        mm_prompt_updates: MultiModalPromptUpdates,
1649
        is_update_applied: bool,
1650
    ) -> tuple[list[int], Mapping[str, list[PlaceholderFeaturesInfo]]]:
1651
        mm_item_counts = mm_items.get_all_counts()
1652
        self._validate_mm_kwargs(mm_kwargs, mm_item_counts)
1653
        self._validate_mm_updates(mm_prompt_updates, mm_item_counts)
1654

1655
        if is_update_applied:
1656
1657
            mm_placeholders = self._find_mm_placeholders(
                prompt_ids,
1658
                mm_prompt_updates,
1659
            )
1660
            self._validate_mm_placeholders(mm_placeholders, mm_item_counts)
1661
        else:
1662
            prompt_ids, mm_placeholders = self._apply_prompt_updates(
1663
                prompt_ids,
1664
                mm_prompt_updates,
1665
            )
1666
            self._validate_mm_placeholders(mm_placeholders, mm_item_counts)
1667

1668
        return prompt_ids, mm_placeholders
1669
1670
1671

    def apply(
        self,
1672
1673
        inputs: ProcessorInputs,
        timing_ctx: TimingContext,
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
    ) -> 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.
        """
        (
            prompt_ids,
1690
            mm_info,
1691
            is_update_applied,
1692
        ) = self._cached_apply_hf_processor(inputs, timing_ctx)
1693

1694
        # NOTE: tokenization_kwargs are not required to init processor
1695
        with timing_ctx.record("apply_prompt_updates"):
1696
            prompt_ids, mm_placeholders = self._maybe_apply_prompt_updates(
1697
                mm_items=inputs.mm_data_items,
1698
1699
1700
1701
1702
                prompt_ids=prompt_ids,
                mm_kwargs=mm_info.kwargs,
                mm_prompt_updates=mm_info.prompt_updates,
                is_update_applied=is_update_applied,
            )
1703

1704
1705
1706
1707
        mm_placeholder_ranges = {
            modality: [item.to_range() for item in placeholders]
            for modality, placeholders in mm_placeholders.items()
        }
1708

1709
        return mm_inputs(
1710
            prompt_token_ids=prompt_ids,
1711
1712
            mm_kwargs=mm_info.kwargs,
            mm_hashes=mm_info.hashes,
1713
            mm_placeholders=mm_placeholder_ranges,
1714
        )
1715
1716
1717
1718
1719
1720


class EncDecMultiModalProcessor(BaseMultiModalProcessor[_I]):
    @abstractmethod
    def create_encoder_prompt(
        self,
1721
        prompt: str | list[int],
1722
        mm_items: MultiModalDataItems,
1723
    ) -> str | list[int]:
1724
        """
1725
        Create input prompt for the encoder. HF processor will be applied on
1726
1727
        this prompt during profiling and generation.
        """
1728
1729
        raise NotImplementedError

1730
1731
    def create_decoder_prompt(
        self,
1732
        prompt: str | list[int],
1733
        mm_items: MultiModalDataItems,
1734
    ) -> str | list[int]:
1735
1736
1737
        """Create input prompt for the decoder."""
        return prompt

1738
    def _get_enc_dec_inputs(
1739
        self,
1740
        prompt: str | list[int],
1741
        mm_items: MultiModalDataItems,
1742
1743
        encoder_inputs: MultiModalInputs,
    ):
1744
        tokenizer = self.info.get_tokenizer()
1745
        decoder_prompt_raw = self.create_decoder_prompt(prompt, mm_items)
1746
        if isinstance(decoder_prompt_raw, str):
1747
            decoder_prompt_text = decoder_prompt_raw
1748
1749
            decoder_prompt_ids = tokenizer.encode(
                decoder_prompt_raw, add_special_tokens=False
1750
            )
1751
        else:
1752
            decoder_prompt_text = None
1753
            decoder_prompt_ids = decoder_prompt_raw
1754

1755
1756
1757
        return mm_enc_dec_inputs(
            encoder_inputs,
            decoder_prompt_ids,
1758
            decoder_prompt=decoder_prompt_text,
1759
        )
1760
1761
1762

    def apply(
        self,
1763
1764
        inputs: ProcessorInputs,
        timing_ctx: TimingContext,
1765
1766
1767
1768
1769
1770
1771
1772
    ) -> 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.
        """
1773
1774
1775
1776
1777
        encoder_prompt = self.create_encoder_prompt(
            inputs.prompt,
            inputs.mm_data_items,
        )
        encoder_processor_inputs = ProcessorInputs(
1778
            encoder_prompt,
1779
1780
1781
1782
            inputs.mm_data_items,
            inputs.mm_uuid_items,
            hf_processor_mm_kwargs=inputs.hf_processor_mm_kwargs,
            tokenization_kwargs=inputs.tokenization_kwargs,
1783
1784
        )

1785
1786
        encoder_inputs = super().apply(encoder_processor_inputs, timing_ctx)

1787
        return self._get_enc_dec_inputs(
1788
1789
            prompt=inputs.prompt,
            mm_items=inputs.mm_data_items,
1790
1791
            encoder_inputs=encoder_inputs,
        )