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

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

18
from vllm.inputs import InputProcessingContext
19
from vllm.jsontree import json_map_leaves, json_reduce_leaves
20
from vllm.logger import init_logger
21
22
from vllm.transformers_utils.tokenizer import (AnyTokenizer, decode_tokens,
                                               encode_tokens)
23
from vllm.utils import GiB_bytes, LRUCache, flatten_2d_lists, full_groupby
24

25
from .hasher import MultiModalHasher
26
27
from .inputs import (MultiModalDataDict, MultiModalEncDecInputs,
                     MultiModalFieldConfig, MultiModalInputs, MultiModalKwargs,
28
                     MultiModalKwargsItem, NestedTensors, PlaceholderRange)
29
30
from .parse import (DictEmbeddingItems, EmbeddingItems, MultiModalDataItems,
                    MultiModalDataParser)
31
32

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

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
@dataclass
class PromptIndex:
    """Resolves to an index in the prompt."""
    get_match_index: Callable[[AnyTokenizer, PromptSeq], Optional[int]]


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.
        """
        return PromptIndex(lambda tok, prompt: 0)

    @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,
        ) -> Optional[int]:
            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]`
83
84
85
                    prefix = encode_tokens(tokenizer,
                                           prefix,
                                           add_special_tokens=False)
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

            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.
        """
        return PromptIndex(lambda tok, prompt: len(prompt))


PromptTarget = Union[PromptSeq, PromptIndex]
"""
The token sequence or text to update.
"""


108
@dataclass
109
class PromptUpdateDetails(Generic[_S]):
110
    """Details about the token sequence or text that are part of the update."""
111

112
    full: _S
113
    """The full content."""
114

115
    is_embed: Optional[Callable[["_BoundPromptSequence"], torch.Tensor]] = None
116
    """
117
118
119
    Given [`full`][vllm.multimodal.processing.PromptUpdateDetails.full],
    return a boolean mask of shape `(len(full),)` indicating which positions
    of `full` to assign embeddings to.
120
121
122
123

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

    The embeddings are obtained by calling
124
    [`SupportsMultiModal.get_multimodal_embeddings`][vllm.model_executor.models.interfaces.SupportsMultiModal.get_multimodal_embeddings].
125
126
127
    """

    @staticmethod
128
    def from_seq(seq: _S) -> "PromptUpdateDetails[_S]":
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
        return PromptUpdateDetails(full=seq)

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

        def is_embed(full: "_BoundPromptSequence") -> torch.Tensor:
            embed_token_ids = encode_tokens(full.tokenizer, embed_text)

            return torch.isin(
                torch.tensor(full.token_ids),
                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]":
        return PromptUpdateDetails(
            full=seq,
            is_embed=lambda f: torch.tensor(f.token_ids) == embed_token_id,
        )
156
157


158
PromptUpdateInfo = Union[PromptSeq, PromptUpdateDetails]
159
"""
160
The token sequence or text that are part of the update.
161

162
If only part of the content corresponds to feature placeholders, you can
163
164
use [`PromptUpdateDetails`][vllm.multimodal.processing.PromptUpdateDetails] to
specify which part.
165
"""
166

167
168
169
PromptUpdateContent = Union[Callable[[int], PromptUpdateInfo],
                            PromptUpdateInfo]
"""
170
171
Given the index of the processed item within
[`modality`][vllm.multimodal.processing.PromptUpdate.modality],
172
173
174
175
176
177
178
179
180
181
182
183
184
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
185
class PromptUpdate(ABC):
186
187
188
189
190
191
192
    """
    Defines how to update a prompt with placeholder tokens.
    """

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

193
    target: PromptTarget
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
    """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

    def bind(self, tokenizer: AnyTokenizer) -> "BoundPromptUpdate":
        return BoundPromptUpdate(
            _origin=self,
            tokenizer=tokenizer,
        )

214

215
@dataclass
216
217
218
219
220
221
class PromptInsertion(PromptUpdate):
    """
    Defines how to insert placeholder tokens into a prompt.

    Example:

222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
    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,
    )
    ```
262
263
264
265
    """

    insertion: PromptUpdateContent = field(repr=False)
    """
266
267
268
269
    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].
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285

    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):
286
287
    """
    Defines how to replace portions of an input prompt with placeholder tokens.
288
289
290

    Example:

291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
    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,
        ),
    )
    ```
336
337
    """

338
    replacement: PromptUpdateContent = field(repr=False)
339
    """
340
341
342
343
    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].
344

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

349
350
351
352
353
354
355
    @property
    def content(self) -> PromptUpdateContent:
        return self.replacement

    @property
    def mode(self) -> UpdateMode:
        return UpdateMode.REPLACE
356
357


358
359
360
361
362
@lru_cache(maxsize=2048)
def _cached_encode(
    tokenizer: AnyTokenizer,
    text: str,
    *,
363
    add_special_tokens: Optional[bool] = None,
364
) -> list[int]:
365
366
367
    return encode_tokens(tokenizer,
                         text,
                         add_special_tokens=add_special_tokens)
368
369


370
371
372
373
374
@lru_cache(maxsize=2048)
def _cached_decode(
    tokenizer: AnyTokenizer,
    token_ids: tuple[int, ...],
    *,
375
    skip_special_tokens: Optional[bool] = None,
376
) -> str:
377
378
379
    return decode_tokens(tokenizer,
                         list(token_ids),
                         skip_special_tokens=skip_special_tokens)
380
381
382
383
384


class _HasModalityAttr(Protocol):
    modality: str

385

386
class _HasModalityProp(Protocol):
387

388
389
390
391
392
393
394
395
396
    @property
    def modality(self) -> str:
        ...


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


def full_groupby_modality(values: Iterable[_M]) -> ItemsView[str, list[_M]]:
397
398
    """Convenience function to apply [`full_groupby`][vllm.utils.full_groupby]
    based on modality."""
399
400
401
402
403
    return full_groupby(values, key=lambda x: x.modality)


@dataclass
class _BoundPromptSequence:
404
    """
405
406
    A [`_PromptSeq`][vllm.multimodal.processing.PromptSeq] bound
    to a tokenizer to automatically
407
408
    convert between token sequence and text representations.
    """
409
410
    tokenizer: AnyTokenizer = field(repr=False)

411
412
413
    _text: Optional[str]
    _token_ids: Optional[list[int]]

414
    @staticmethod
415
416
    def from_seq(
        tokenizer: AnyTokenizer,
417
        seq: PromptSeq,
418
    ) -> "_BoundPromptSequence":
419
420
421
422
423
424
        return _BoundPromptSequence(
            tokenizer=tokenizer,
            _text=seq if isinstance(seq, str) else None,
            _token_ids=seq if isinstance(seq, list) else None,
        )

425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
    def __post_init__(self) -> None:
        if self._text is None and self._token_ids is None:
            raise ValueError("At least one of 'text' and 'token_ids' must be "
                             "specified")

    @property
    def text(self) -> str:
        if self._text is None:
            assert self._token_ids is not None
            self._text = _cached_decode(self.tokenizer, tuple(self._token_ids))

        return self._text

    @property
    def token_ids(self) -> list[int]:
        if self._token_ids is None:
            assert self._text is not None
442
443
444
            self._token_ids = _cached_encode(self.tokenizer,
                                             self._text,
                                             add_special_tokens=False)
445
446
447
448

        return self._token_ids


449
@dataclass
450
class _BoundPromptContent:
451
    full: _BoundPromptSequence
452
    is_embed: Optional[Callable[["_BoundPromptSequence"], torch.Tensor]]
453
454


455
@dataclass
456
class BoundPromptUpdate:
457
    """
458
459
460
461
462
    A [`PromptUpdate`][vllm.multimodal.processing.PromptUpdate] bound
    to a tokenizer to automatically convert
    [`target`][vllm.multimodal.processing.PromptUpdate.target] and the result of
    [`get_content`][vllm.multimodal.processing.BoundPromptUpdate.get_content]
    between token sequence and text representations.
463
    """
464
    _origin: PromptUpdate
465
    tokenizer: AnyTokenizer = field(repr=False)
466

467
    def __post_init__(self) -> None:
468
469
470
471
472
        self._content_cache = dict[int, _BoundPromptContent]()

    @property
    def modality(self) -> str:
        return self._origin.modality
473
474

    @property
475
    def target(self) -> Union[_BoundPromptSequence, PromptIndex]:
476
        """The token sequence (or text) to update."""
477
478
479
480
481
482
        target = self._origin.target

        if isinstance(target, PromptIndex):
            return target

        return _BoundPromptSequence.from_seq(self.tokenizer, target)
483

484
485
486
487
488
489
490
491
492
493
494
    @property
    def content(self) -> PromptUpdateContent:
        """The placeholder tokens that are part of the update."""
        return self._origin.content

    @property
    def mode(self) -> UpdateMode:
        """Defines how to update the prompt."""
        return self._origin.mode

    def get_content(self, item_idx: int) -> _BoundPromptContent:
495
        """
496
497
        Given the index of the processed item within
        [`modality`][vllm.multimodal.processing.PromptUpdate.modality],
498
        output the token sequence (or text) to update.
499
        """
500
501
        content = self.content
        if callable(content):
502
            cache_key = item_idx
503
504
            if cache_key in self._content_cache:
                return self._content_cache[cache_key]
505

506
            content = content(item_idx)
507
508
509
        else:
            cache_key = None

510
511
        if not isinstance(content, PromptUpdateDetails):
            content = PromptUpdateDetails.from_seq(content)
512
513

        bound_full = _BoundPromptSequence.from_seq(self.tokenizer,
514
515
                                                   content.full)
        bound_content = _BoundPromptContent(full=bound_full,
516
                                            is_embed=content.is_embed)
517
518

        if cache_key is not None:
519
            self._content_cache[cache_key] = bound_content
520

521
        return bound_content
522
523


524
525
526
class _TokenMatch(NamedTuple):
    start_idx: int
    end_idx: int
527
528


529
530
531
def iter_token_matches(
    token_ids: list[int],
    match_ids: list[int],
532
) -> Generator[_TokenMatch]:
533
    """
534
    Yield each occurrence of `match_ids` in `token_ids`.
535
536
537
538

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

541
542
    if match_len == 0:
        return
543

544
545
    start_idx = 0
    while start_idx < prompt_len - match_len + 1:
546
        end_idx = start_idx + match_len
547

548
549
        if token_ids[start_idx:end_idx] == match_ids:
            yield _TokenMatch(start_idx=start_idx, end_idx=end_idx)
550
551
552
553
554

            # Exclude overlapping matches
            start_idx = end_idx
        else:
            start_idx += 1
555
556


557
558
559
560
561
562
def replace_token_matches(
    token_ids: list[int],
    match_ids: list[int],
    new_ids: list[int],
) -> list[int]:
    """
563
564
    Replace each occurrence of `match_ids` in `token_ids`
    with `new_ids`.
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583

    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)


584
@dataclass(repr=False)
585
class PromptTargetMatch(ABC):
586
    _origin: BoundPromptUpdate
587
588
589

    @property
    def modality(self) -> str:
590
        return self._origin.modality
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606

    @property
    @abstractmethod
    def start_idx(self) -> int:
        raise NotImplementedError

    @property
    @abstractmethod
    def end_idx(self) -> int:
        raise NotImplementedError

    def __repr__(self) -> str:
        return (f"{type(self).__name__}(modality={self.modality!r}, "
                f"start_idx={self.start_idx!r}, end_idx={self.end_idx!r})")


607
@dataclass(repr=False)
608
class _PromptTargetIndexMatch(PromptTargetMatch):
609
610
611
612
613
614
615
616
617
618
619
    match_idx: int

    @property
    def start_idx(self) -> int:
        return self.match_idx

    @property
    def end_idx(self) -> int:
        return self.match_idx


620
@dataclass(repr=False)
621
class _PromptTargetTokenMatch(PromptTargetMatch):
622
623
624
625
626
627
628
629
630
631
632
633
    match: _TokenMatch

    @property
    def start_idx(self) -> int:
        return self.match.start_idx

    @property
    def end_idx(self) -> int:
        return self.match.end_idx


@dataclass(repr=False)
634
class _PromptTargetTextMatch(PromptTargetMatch):
635
636
637
638
639
640
641
642
643
644
    match: re.Match[str]

    @property
    def start_idx(self) -> int:
        return self.match.start()

    @property
    def end_idx(self) -> int:
        return self.match.end()

645

646
@dataclass
647
class PlaceholderFeaturesInfo:
648
    modality: str
649
    item_idx: int
650
    start_idx: int
651
    tokens: list[int]
652
    is_embed: Optional[torch.Tensor]
653
654
655

    @property
    def length(self) -> int:
656
        return len(self.tokens)
657
658

    def to_range(self) -> PlaceholderRange:
659
660
        # TODO: Is it worth it to optimize this by stripping the
        # leading and ending positions where `is_embed=False`?
661
662
663
        return PlaceholderRange(
            offset=self.start_idx,
            length=self.length,
664
            is_embed=self.is_embed,
665
        )
666
667
668
669


def find_token_matches(
    prompt: list[int],
670
    prompt_updates: Sequence[BoundPromptUpdate],
671
) -> Sequence[PromptTargetMatch]:
672
    """Return each target of `prompt_updates` found in `prompt`."""
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688

    def get_matches(update: BoundPromptUpdate):
        target = update.target

        if isinstance(target, PromptIndex):
            match_idx = target.get_match_index(update.tokenizer, prompt)
            if match_idx is None:
                return []

            return [_PromptTargetIndexMatch(update, match_idx)]

        return [
            _PromptTargetTokenMatch(update, match)
            for match in iter_token_matches(prompt, target.token_ids)
        ]

689
    return [
690
        match for update in prompt_updates for match in get_matches(update)
691
692
693
694
695
    ]


def find_text_matches(
    prompt: str,
696
    prompt_updates: Sequence[BoundPromptUpdate],
697
) -> Sequence[PromptTargetMatch]:
698
    """Return each target of `prompt_updates` found in `prompt`."""
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714

    def get_matches(update: BoundPromptUpdate):
        target = update.target

        if isinstance(target, PromptIndex):
            match_idx = target.get_match_index(update.tokenizer, prompt)
            if match_idx is None:
                return []

            return [_PromptTargetIndexMatch(update, match_idx)]

        return [
            _PromptTargetTextMatch(update, match)
            for match in re.finditer(re.escape(target.text), prompt)
        ]

715
    return [
716
        match for update in prompt_updates for match in get_matches(update)
717
718
719
720
    ]


def _resolve_matches(
721
    prompt: PromptSeq,
722
723
    mm_matches: Mapping[str, Sequence[PromptTargetMatch]],
) -> list[PromptTargetMatch]:
724
    """
725
    Resolve `mm_matches` to ensure that there are no overlapping matches,
726
    and sort them such that earlier matches take priority over later ones.
727
    """
728
729
    matches = [m for matches in mm_matches.values() for m in matches]

730
    seen_matches: list[Optional[PromptTargetMatch]] = [None] * len(prompt)
731

732
    for match in matches:
733
734
735
736
737
        for idx in range(match.start_idx, match.end_idx):
            if seen_matches[idx] is not None:
                raise ValueError("Found overlapping matches "
                                 f"({seen_matches[idx]} and {match}) "
                                 f"at index={idx} of prompt={prompt}")
738

739
            seen_matches[idx] = match
740
741
742
743

    return sorted(matches, key=lambda x: x.start_idx)


744
def _apply_matches(
745
    prompt: _S,
746
    mm_matches: Mapping[str, Sequence[PromptTargetMatch]],
747
    mm_item_counts: Mapping[str, int],
748
) -> list[_S]:
749
    """Apply the updates in `mm_matches` to `prompt`."""
750
    out_seqs = list[Union[str, list[int]]]()
751
    prev_end_idx = 0
752
    next_idx_by_modality = defaultdict[str, int](lambda: 0)
753

754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
    for match in _resolve_matches(prompt, mm_matches):
        modality = match.modality

        item_start_idx = next_idx_by_modality[modality]
        max_item_count = mm_item_counts.get(modality, 0)
        if item_start_idx >= max_item_count:
            continue

        start_idx = match.start_idx
        end_idx = match.end_idx
        origin = match._origin
        mode = origin.mode

        if mode == UpdateMode.INSERT:
            out_seqs.append(prompt[prev_end_idx:end_idx])
            num_inserts = max_item_count
        elif mode == UpdateMode.REPLACE:
            out_seqs.append(prompt[prev_end_idx:start_idx])
            num_inserts = max_item_count if start_idx == end_idx else 1
        else:
            assert_never(mode)
775

776
        item_end_idx = min(item_start_idx + num_inserts, max_item_count)
777

778
        for item_idx in range(item_start_idx, item_end_idx):
779
            content = origin.get_content(item_idx)
780
781
            insert_seq = (content.full.text if isinstance(prompt, str) else
                          content.full.token_ids)
782

783
            out_seqs.append(insert_seq)
784

785
786
        prev_end_idx = end_idx
        next_idx_by_modality[modality] += item_end_idx - item_start_idx
787
788
789

    out_seqs.append(prompt[prev_end_idx:])

790
    return cast(list[_S], out_seqs)
791
792


793
def apply_token_matches(
794
    prompt: list[int],
795
    mm_matches: Mapping[str, Sequence[PromptTargetMatch]],
796
    mm_item_counts: Mapping[str, int],
797
) -> list[int]:
798
    """Apply the updates in `mm_matches` to `prompt`."""
799
    if not mm_matches:
800
801
        return prompt

802
    token_id_seqs = _apply_matches(prompt, mm_matches, mm_item_counts)
803
804

    return flatten_2d_lists(token_id_seqs)
805
806


807
def apply_text_matches(
808
    prompt: str,
809
    mm_matches: Mapping[str, Sequence[PromptTargetMatch]],
810
    mm_item_counts: Mapping[str, int],
811
) -> str:
812
    """Apply the updates in `mm_matches` to `prompt`."""
813
    if not mm_matches:
814
        return prompt
815

816
    texts = _apply_matches(prompt, mm_matches, mm_item_counts)
817
818

    return "".join(texts)
819
820


821
def _iter_placeholders(
822
    mm_prompt_updates: Mapping[str, Sequence[BoundPromptUpdate]],
823
    prompt: list[int],
824
    mm_item_counts: Mapping[str, int],
825
) -> Iterable[PlaceholderFeaturesInfo]:
826
    """
827
    Yield each set of placeholder tokens found in `prompt`.
828
829
830

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

833
834
    Note that empty matches are ignored.
    """
835
    prompt_len = len(prompt)
836
    item_idx_by_modality = defaultdict[str, int](lambda: 0)
837
838
839
840
841

    start_idx = 0
    while start_idx < prompt_len:
        found = False

842
        for modality, modality_updates in mm_prompt_updates.items():
843
844
            item_idx = item_idx_by_modality[modality]
            if item_idx >= mm_item_counts.get(modality, 0):
845
                continue
846

847
848
849
850
851
            for update_info in modality_updates:
                content = update_info.get_content(item_idx)
                content_tokens_full = content.full.token_ids
                content_len_full = len(content_tokens_full)
                end_idx_full = start_idx + content_len_full
852

853
                if content_len_full == 0 or end_idx_full > prompt_len:
854
855
                    continue

856
                if prompt[start_idx:end_idx_full] == content_tokens_full:
857
858
859
860
861
862
863
864
865
866
867
                    content_is_embed = content.is_embed
                    if content_is_embed is not None:
                        content_is_embed = content_is_embed(content.full)

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

869
                    # Exclude overlapping matches
870
                    start_idx = end_idx_full
871
872
873
                    item_idx_by_modality[modality] += 1
                    found = True
                    break
874

875
876
            if found:
                break  # Go back to the outer while loop
877
878
879

        if not found:
            start_idx += 1
880
881


882
def find_mm_placeholders(
883
    mm_prompt_updates: Mapping[str, Sequence[BoundPromptUpdate]],
884
885
    prompt: list[int],
    mm_item_counts: Mapping[str, int],
886
) -> Mapping[str, list[PlaceholderFeaturesInfo]]:
887
    it = _iter_placeholders(mm_prompt_updates, prompt, mm_item_counts)
888
889
890
    return dict(full_groupby_modality(it))


891
892
893
_V = TypeVar("_V", bound="Union[MultiModalKwargs, MultiModalKwargsItem]")


894
895
896
897
898
899
900
901
902
903
class ProcessingCacheOptionalItem(NamedTuple):
    key: str
    value: Optional[MultiModalKwargsItem]


class ProcessingCacheItem(NamedTuple):
    key: str
    value: MultiModalKwargsItem


904
905
class ProcessingCache:

906
907
    @staticmethod
    def get_lru_cache(
908
        capacity_gb: float,
909
        value_type: type[_V],
910
911
        *,
        debug: bool = False,
912
913
    ) -> LRUCache[str, _V]:

914
915
916
917
918
919
920
921
922
923
924
        def get_leaf_size(leaf: object) -> int:
            # MultiModalKwargs is not a subclass of dict
            if isinstance(leaf, MultiModalKwargs):
                return get_item_size(leaf.data)

            # MultiModalKwargsItem is not a subclass of dict
            if isinstance(leaf, MultiModalKwargsItem):
                leaf_data = {k: v.data for k, v in leaf.items()}
                return get_item_size(leaf_data)

            # sys.getsizeof doesn't work for tensors
925
            if isinstance(leaf, torch.Tensor):
926
                return leaf.nbytes
927
928
929

            return sys.getsizeof(leaf)

930
931
932
933
934
        def get_item_size(
            value: Union[MultiModalKwargs, MultiModalKwargsItem,
                         Mapping[str, NestedTensors]]
        ) -> int:
            size = json_reduce_leaves(
935
                lambda a, b: a + b,
936
937
938
939
940
941
                json_map_leaves(get_leaf_size, value),
            )

            if debug:
                logger.debug("Calculated size of %s to be %.2f GiB",
                             type(value), size / GiB_bytes)
942

943
944
945
946
947
948
949
950
951
952
            return size

        return LRUCache(GiB_bytes * capacity_gb, getsizeof=get_item_size)

    def __init__(
        self,
        capacity_gb: float,
        *,
        debug_cache_hit_ratio_steps: Optional[int] = None,
    ) -> None:
953
954
        super().__init__()

955
        self.debug_cache_hit_ratio_steps = debug_cache_hit_ratio_steps
956
957
        self.debug_cache_hits = 0
        self.debug_cache_total = 0
958

959
960
961
962
963
        self._cache = self.get_lru_cache(
            capacity_gb,
            MultiModalKwargsItem,
            debug=bool(debug_cache_hit_ratio_steps),
        )
964
965
966
967
968
969

    def _maybe_log_cache_stats(self) -> None:
        steps = self.debug_cache_hit_ratio_steps
        if not steps:
            return

970
971
        total = self.debug_cache_total
        if total > 0 and total % steps == 0:
972
            logger.debug("ProcessingCache: hit_ratio = %.2f",
973
                         self.debug_cache_hits / total)
974
975
976
            logger.debug("ProcessingCache: size = %.2f / %.2f GiB",
                         self._cache.currsize / GiB_bytes,
                         self._cache.maxsize / GiB_bytes)
977
978
979
980
981
982
983

    def get(
        self,
        model_id: str,
        modality: str,
        input_item: object,
        input_kwargs: Mapping[str, object],
984
    ) -> Optional[MultiModalKwargsItem]:
985
986
987
988
989
990
991
992
993
994
995
        """
        Get a processed multi-modal item from the cache
        according to its dependencies, including:

        - The model ID
        - The modality of the item
        - The original data item passed to the HF processor
        - The configuration options of the HF processor
        """
        self._maybe_log_cache_stats()

996
997
998
        cache_key = MultiModalHasher.hash_kwargs(model_id=model_id,
                                                 **{modality: input_item},
                                                 **input_kwargs)
999
1000
1001
1002
1003
1004
1005

        if self.debug_cache_hit_ratio_steps:
            if cache_key in self._cache:
                self.debug_cache_hits += 1

            self.debug_cache_total += 1

1006
1007
        return self._cache.get(cache_key)

1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
    def get_item(
        self,
        model_id: str,
        modality: str,
        input_item: object,
        input_kwargs: Mapping[str, object],
    ) -> ProcessingCacheOptionalItem:
        cache_key = MultiModalHasher.hash_kwargs(model_id=model_id,
                                                 **{modality: input_item},
                                                 **input_kwargs)

        return ProcessingCacheOptionalItem(
            key=cache_key,
            value=self._cache.get(cache_key),
        )

1024
1025
1026
1027
1028
1029
    def put(
        self,
        model_id: str,
        modality: str,
        input_item: object,
        input_kwargs: Mapping[str, object],
1030
        output_kwargs: MultiModalKwargsItem,
1031
1032
1033
    ) -> None:
        """
        Put a processed multi-modal item into the cache
1034
1035
        according to its dependencies
        (see [`get`][vllm.multimodal.processing.ProcessingCache.get]).
1036
        """
1037
1038
1039
        cache_key = MultiModalHasher.hash_kwargs(model_id=model_id,
                                                 **{modality: input_item},
                                                 **input_kwargs)
1040
        self._cache[cache_key] = output_kwargs
1041

1042
1043
1044
    def put_item(self, item: ProcessingCacheItem) -> None:
        self._cache[item.key] = item.value

1045
1046
1047
1048
1049
    def reset(self) -> bool:
        self._cache.clear()

        return True

1050

1051
class BaseProcessingInfo:
1052
    """Base class to provide the information necessary for data processing."""
1053

1054
1055
    def __init__(self, ctx: InputProcessingContext) -> None:
        super().__init__()
1056

1057
1058
1059
1060
1061
1062
1063
        self.ctx = ctx

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

    def get_tokenizer(self) -> AnyTokenizer:
1064
1065
        return self.ctx.tokenizer

1066
    def get_hf_config(self) -> "PretrainedConfig":
1067
1068
        return self.ctx.get_hf_config()

1069
    def get_hf_processor(self, **kwargs: object) -> "ProcessorMixin":
1070
1071
1072
1073
1074
1075
        """
        Subclasses can override this method to handle
        specific kwargs from model config or user inputs.
        """
        return self.ctx.get_hf_processor(**kwargs)

1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
    @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

1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
    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

1102
1103

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

1105
1106
MultiModalHashes = dict[str, list[str]]
"""
1107
1108
A collection of hashes with a similar structure as
[`MultiModalKwargs`][vllm.multimodal.inputs.MultiModalKwargs].
1109
1110
"""

1111
1112

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

1116
    Not to be confused with `transformers.ProcessorMixin`.
1117
1118
    """

1119
    def __init__(self,
1120
1121
                 info: _I,
                 dummy_inputs: "BaseDummyInputsBuilder[_I]",
1122
                 *,
1123
                 cache: Optional[ProcessingCache] = None) -> None:
1124
1125
        super().__init__()

1126
1127
        self.info = info
        self.dummy_inputs = dummy_inputs
1128
        self.cache = cache
1129

1130
1131
        self.data_parser = self._get_data_parser()

1132
    def __call__(
1133
        self,
1134
1135
        prompt: str,
        mm_data: MultiModalDataDict,
1136
        hf_processor_mm_kwargs: Mapping[str, object],
1137
    ) -> MultiModalInputs:
1138
        return self.apply(prompt, mm_data, hf_processor_mm_kwargs)
1139

1140
1141
    def _get_data_parser(self) -> MultiModalDataParser:
        """
1142
        Construct a parser to preprocess multi-modal data items
1143
1144
        before passing them to
        [`_get_hf_mm_data`][vllm.multimodal.processing.BaseMultiModalProcessor._get_hf_mm_data].
1145
1146

        You can support additional modalities by creating a subclass
1147
1148
        of [`MultiModalDataParser`][vllm.multimodal.parse.MultiModalDataParser]
        that has additional subparsers.
1149
1150
1151
1152
        """
        return MultiModalDataParser()

    def _to_mm_items(
1153
1154
1155
        self,
        mm_data: MultiModalDataDict,
    ) -> MultiModalDataItems:
1156
        """
1157
1158
1159
1160
1161
        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].
1162
        """
1163
        mm_items = self.data_parser.parse_mm_data(mm_data)
1164
1165
        supported_mm_limits = self.info.get_supported_mm_limits()
        allowed_mm_limits = self.info.get_allowed_mm_limits()
1166
1167

        for modality, items in mm_items.items():
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
            supported_limit = supported_mm_limits.get(modality, 0)
            allowed_limit = allowed_mm_limits.get(modality, 0)
            num_items = len(items)

            if supported_limit is not None and num_items > supported_limit:
                raise ValueError(
                    f"The model only supports at most {supported_limit} "
                    f"{modality} items, but you passed {num_items} "
                    f"{modality} items in the same prompt.")

            if num_items > allowed_limit:
1179
                raise ValueError(
1180
1181
1182
                    "You set or defaulted to "
                    f"'{json.dumps({modality: allowed_limit})}' in "
                    f"`--limit-mm-per-prompt`, but passed {num_items} "
1183
1184
1185
                    f"{modality} items in the same prompt.")

        return mm_items
1186

1187
1188
1189
    @abstractmethod
    def _get_mm_fields_config(
        self,
1190
        hf_inputs: "BatchFeature",
1191
1192
1193
1194
1195
        hf_processor_mm_kwargs: Mapping[str, object],
    ) -> Mapping[str, MultiModalFieldConfig]:
        """Given the HF-processed data, output the metadata of each field."""
        raise NotImplementedError

1196
    @abstractmethod
1197
    def _get_prompt_updates(
1198
        self,
1199
        mm_items: MultiModalDataItems,
1200
1201
        hf_processor_mm_kwargs: Mapping[str, object],
        out_mm_kwargs: MultiModalKwargs,
1202
    ) -> Sequence[PromptUpdate]:
1203
1204
        """
        Given the original multi-modal items for this modality
1205
        and HF-processed data, output the updates to perform.
1206

1207
1208
1209
1210
1211
1212
        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
1213
1214
        in order to construct
        [`PlaceholderRange`][vllm.multimodal.inputs.PlaceholderRange]
1215
        for each multi-modal item.
1216
1217
        """
        raise NotImplementedError
1218

1219
    def _find_mm_placeholders(
1220
        self,
1221
        mm_prompt_updates: Mapping[str, Sequence[BoundPromptUpdate]],
1222
        new_token_ids: list[int],
1223
        mm_item_counts: Mapping[str, int],
1224
    ) -> Mapping[str, list[PlaceholderFeaturesInfo]]:
1225
        return find_mm_placeholders(mm_prompt_updates, new_token_ids,
1226
                                    mm_item_counts)
1227

1228
    def _get_hf_mm_data(
1229
        self,
1230
        mm_items: MultiModalDataItems,
1231
1232
1233
    ) -> tuple[Mapping[str, object], Mapping[str, object]]:
        processor_data = dict[str, object]()
        passthrough_data = dict[str, object]()
1234

1235
1236
1237
        for items in mm_items.values():
            processor_data.update(items.get_processor_data())
            passthrough_data.update(items.get_passthrough_data())
1238

1239
1240
        return processor_data, passthrough_data

1241
1242
1243
    def _call_hf_processor(
        self,
        prompt: str,
1244
1245
1246
1247
        # 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],
1248
    ) -> "BatchFeature":
1249
1250
1251
1252
        """
        Call the HF processor on the prompt text and
        associated multi-modal data.
        """
1253
1254
        return self.info.ctx.call_hf_processor(
            self.info.get_hf_processor(**mm_kwargs),
1255
1256
            dict(text=prompt, **mm_data),
            mm_kwargs,
1257
1258
        )

1259
    def _hf_processor_applies_updates(
1260
1261
1262
1263
1264
1265
        self,
        prompt_text: str,
        mm_items: MultiModalDataItems,
        hf_processor_mm_kwargs: Mapping[str, object],
    ) -> bool:
        """
1266
        Return whether the HF processor applies prompt updates.
1267

1268
1269
        For most HF processors, this should be `True` when multi-modal
        data items are passed, but `False` when multi-modal embeddings
1270
1271
1272
1273
1274
1275
        are passed.
        """
        return not any(
            isinstance(items, (EmbeddingItems, DictEmbeddingItems))
            for items in mm_items.values())

1276
    def _apply_hf_processor_text_mm(
1277
        self,
1278
        prompt_text: str,
1279
        mm_items: MultiModalDataItems,
1280
        hf_processor_mm_kwargs: Mapping[str, object],
1281
    ) -> tuple[list[int], MultiModalKwargs, bool]:
1282
        """
1283
1284
        Apply the HF processor on the prompt text and multi-modal data
        together.
1285

1286
        In addition, return whether prompt updates have been applied.
1287
1288
1289
1290
1291
1292
1293
1294
1295
        """
        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,
        )
        processed_data.update(passthrough_data)
1296

1297
        prompt_ids, = processed_data.pop("input_ids").tolist()
1298

1299
1300
1301
        mm_kwargs = MultiModalKwargs.from_hf_inputs(
            processed_data,
            self._get_mm_fields_config(processed_data, hf_processor_mm_kwargs),
1302
        )
1303

1304
        is_update_applied = self._hf_processor_applies_updates(
1305
1306
1307
1308
1309
            prompt_text=prompt_text,
            mm_items=mm_items,
            hf_processor_mm_kwargs=hf_processor_mm_kwargs,
        )

1310
        return prompt_ids, mm_kwargs, is_update_applied
1311

1312
    def _apply_hf_processor_text_only(self, prompt_text: str) -> list[int]:
1313
        """
1314
        Apply the HF processor on the prompt text only.
1315

1316
1317
1318
        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.
1319
        """
1320
        prompt_ids, _, _ = self._apply_hf_processor_text_mm(
1321
1322
1323
1324
1325
            prompt_text=prompt_text,
            mm_items=MultiModalDataItems({}),
            hf_processor_mm_kwargs={},
        )

1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
        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
1338
1339
1340
        with the output of
        [`_apply_hf_processor_text_only`][vllm.multimodal.processing.BaseMultiModalProcessor._apply_hf_processor_text_only]
        on the
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
        corresponding text.
        """
        return prompt_tokens

    def _apply_hf_processor_mm_only(
        self,
        mm_items: MultiModalDataItems,
        hf_processor_mm_kwargs: Mapping[str, object],
    ) -> MultiModalKwargs:
        """
        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
1355
1356
        [`DummyInputsBuilder`][vllm.multimodal.profiling.BaseDummyInputsBuilder]
        to go along with the multi-modal data.
1357
1358
1359
        """
        mm_counts = mm_items.get_all_counts()

1360
        _, mm_kwargs, _ = self._apply_hf_processor_text_mm(
1361
            prompt_text=self.dummy_inputs.get_dummy_text(mm_counts),
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
            mm_items=mm_items,
            hf_processor_mm_kwargs=hf_processor_mm_kwargs,
        )

        return mm_kwargs

    def _apply_hf_processor_main(
        self,
        prompt: Union[str, list[int]],
        mm_items: MultiModalDataItems,
        hf_processor_mm_kwargs: Mapping[str, object],
        *,
1374
        enable_hf_prompt_update: bool,
1375
    ) -> tuple[list[int], MultiModalKwargs, bool]:
1376
1377
1378
        """
        Apply the HF processor on the prompt text and multi-modal data.

1379
        In addition, return whether prompt updates have been applied
1380
        (for most HF processors, this should be `True`).
1381

1382
        Note:
1383
            If `enable_hf_prompt_update=False`, we use HF processor
1384
            to perform prompt updates if available; HF processor requires
1385
            that the prompt corresponds to multi-modal items.
1386
1387
        """
        if isinstance(prompt, str):
1388
            if enable_hf_prompt_update:
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
                return self._apply_hf_processor_text_mm(
                    prompt_text=prompt,
                    mm_items=mm_items,
                    hf_processor_mm_kwargs=hf_processor_mm_kwargs,
                )

            prompt_ids = self._apply_hf_processor_text_only(prompt)
        else:
            prompt_ids = self._apply_hf_processor_tokens_only(prompt)

1399
        mm_kwargs = self._apply_hf_processor_mm_only(
1400
            mm_items=mm_items,
1401
1402
1403
            hf_processor_mm_kwargs=hf_processor_mm_kwargs,
        )

1404
        return prompt_ids, mm_kwargs, False
1405

1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
    def _get_cache_missing_items(
        self,
        cache: ProcessingCache,
        mm_data_items: MultiModalDataItems,
        hf_processor_mm_kwargs: Mapping[str, object],
    ) -> tuple[dict[str, list[ProcessingCacheOptionalItem]], dict[
            str, list[object]]]:
        model_id = self.info.model_id

        mm_cache_items = {
            modality: [
                cache.get_item(model_id, modality, item,
                               hf_processor_mm_kwargs) for item in items
            ]
            for modality, items in mm_data_items.items()
        }

        mm_missing_idxs = {
            modality: [
                idx for idx, item in enumerate(cache_items)
                if item.value is None
            ]
            for modality, cache_items in mm_cache_items.items()
        }
        mm_missing_data = {
            modality: [mm_data_items[modality][idx] for idx in idxs]
            for modality, idxs in mm_missing_idxs.items()
        }

        return mm_cache_items, mm_missing_data

    def _hash_mm_items(
        self,
        mm_items: MultiModalDataItems,
        hf_processor_mm_kwargs: Mapping[str, object],
    ) -> MultiModalHashes:
        """Create MM hashes to be returned (only used in V1)."""
        model_id = self.info.model_id

        return {
            modality: [
                MultiModalHasher.hash_kwargs(model_id=model_id,
                                             **{modality: item},
                                             **hf_processor_mm_kwargs)
                for item in items
            ]
            for modality, items in mm_items.items()
        }

    def _merge_mm_kwargs(
        self,
        cache: ProcessingCache,
        mm_cache_items: dict[str, list[ProcessingCacheOptionalItem]],
        mm_missing_data: dict[str, list[object]],
        mm_missing_kwargs: MultiModalKwargs,
    ) -> dict[str, list[ProcessingCacheItem]]:
        mm_missing_next_idx = {modality: 0 for modality in mm_missing_data}

        merged_items = defaultdict[str, list[ProcessingCacheItem]](list)
        for modality, cache_items in mm_cache_items.items():
            for cache_item in cache_items:
                if cache_item.value is None:
                    kw_item = mm_missing_kwargs.get_item(
                        modality,
                        mm_missing_next_idx[modality],
                    )
                    cache_item_new = ProcessingCacheItem(
                        key=cache_item.key,
                        value=kw_item,
                    )

                    cache.put_item(cache_item_new)
                    mm_missing_next_idx[modality] += 1
                else:
                    cache_item_new = ProcessingCacheItem(
                        key=cache_item.key,
                        value=cache_item.value,
                    )

                merged_items[modality].append(cache_item_new)

        return dict(merged_items)

    def _apply_hf_processor(
        self,
        prompt: Union[str, list[int]],
        mm_data_items: MultiModalDataItems,
        hf_processor_mm_kwargs: Mapping[str, object],
        *,
        return_mm_hashes: bool,
    ) -> tuple[list[int], MultiModalKwargs, Optional[MultiModalHashes], bool]:
        (
            prompt_ids,
            mm_kwargs,
            is_update_applied,
        ) = self._apply_hf_processor_main(
            prompt=prompt,
            mm_items=mm_data_items,
            hf_processor_mm_kwargs=hf_processor_mm_kwargs,
            enable_hf_prompt_update=True,
        )

        mm_hashes = (self._hash_mm_items(mm_data_items, hf_processor_mm_kwargs)
                     if return_mm_hashes else None)

        return prompt_ids, mm_kwargs, mm_hashes, is_update_applied

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

1527
1528
        _, passthrough_data = self._get_hf_mm_data(mm_data_items)
        if cache is None or passthrough_data:
1529
            return self._apply_hf_processor(
1530
                prompt=prompt,
1531
                mm_data_items=mm_data_items,
1532
                hf_processor_mm_kwargs=hf_processor_mm_kwargs,
1533
                return_mm_hashes=return_mm_hashes,
1534
1535
            )

1536
1537
1538
1539
1540
1541
1542
1543
        (
            mm_cache_items,
            mm_missing_data,
        ) = self._get_cache_missing_items(
            cache=cache,
            mm_data_items=mm_data_items,
            hf_processor_mm_kwargs=hf_processor_mm_kwargs,
        )
1544

1545
        # NOTE: `prompt` does not correspond to `mm_missing_data_items`,
1546
        # so we can't apply prompt updates until the new multimodal
1547
1548
1549
1550
        # items are combined with the cached multimodal items
        (
            prompt_ids,
            mm_missing_kwargs,
1551
            is_update_applied,
1552
        ) = self._apply_hf_processor_main(
1553
            prompt=prompt,
1554
            mm_items=self._to_mm_items(mm_missing_data),
1555
            hf_processor_mm_kwargs=hf_processor_mm_kwargs,
1556
            enable_hf_prompt_update=False,
1557
1558
        )

1559
1560
1561
1562
1563
1564
        mm_cache_items_merged = self._merge_mm_kwargs(
            cache,
            mm_cache_items=mm_cache_items,
            mm_missing_data=mm_missing_data,
            mm_missing_kwargs=mm_missing_kwargs,
        )
1565

1566
1567
1568
1569
        mm_kwargs = MultiModalKwargs.from_items([
            item.value for cache_items in mm_cache_items_merged.values()
            for item in cache_items
        ])
1570

1571
1572
1573
1574
        mm_hashes = {
            modality: [item.key for item in cache_items]
            for modality, cache_items in mm_cache_items_merged.items()
        } if return_mm_hashes else None
1575

1576
        return prompt_ids, mm_kwargs, mm_hashes, is_update_applied
1577

1578
    def _bind_and_group_updates(
1579
        self,
1580
1581
        prompt_updates: Sequence[PromptUpdate],
    ) -> dict[str, Sequence[BoundPromptUpdate]]:
1582
        tokenizer = self.info.get_tokenizer()
1583

1584
        it = (update.bind(tokenizer) for update in prompt_updates)
1585
        return dict(full_groupby_modality(it))
1586

1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
    def _apply_token_matches(
        self,
        prompt: list[int],
        mm_matches: Mapping[str, Sequence[PromptTargetMatch]],
        mm_item_counts: Mapping[str, int],
    ) -> list[int]:
        return apply_token_matches(prompt, mm_matches, mm_item_counts)

    def _apply_text_matches(
        self,
        prompt: str,
        mm_matches: Mapping[str, Sequence[PromptTargetMatch]],
        mm_item_counts: Mapping[str, int],
    ) -> str:
        return apply_text_matches(prompt, mm_matches, mm_item_counts)

1603
    def _apply_prompt_updates(
1604
1605
        self,
        token_ids: list[int],
1606
        mm_prompt_updates: Mapping[str, Sequence[BoundPromptUpdate]],
1607
        mm_item_counts: Mapping[str, int],
1608
    ) -> tuple[list[int], str, Mapping[str, list[PlaceholderFeaturesInfo]]]:
1609
        tokenizer = self.info.get_tokenizer()
1610

1611
        mm_token_matches = {
1612
1613
            modality: find_token_matches(token_ids, updates)
            for modality, updates in mm_prompt_updates.items()
1614
        }
1615
1616
        mm_match_counts = {
            modality: len(matches)
1617
            for modality, matches in mm_token_matches.items()
1618
        }
1619
1620
1621
1622
1623
1624
1625
1626
1627

        # 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
1628
1629
        # of the search text in the prompt, we instead perform string-based
        # updates on the decoded token IDs, then encode them back.
1630
        if all(
1631
1632
            mm_match_counts.get(modality, 0) >= item_count
            for modality, item_count in mm_item_counts.items()
1633
        ):  # yapf: disable
1634
            token_ids = self._apply_token_matches(
1635
                token_ids,
1636
                mm_token_matches,
1637
                mm_item_counts,
1638
1639
            )

1640
            text = decode_tokens(tokenizer, token_ids)
1641
1642
            matched_updates = {
                modality: [match._origin for match in token_matches]
1643
1644
                for modality, token_matches in mm_token_matches.items()
            }
1645
        else:
1646
            text = decode_tokens(tokenizer, token_ids)
1647

1648
            mm_text_matches = {
1649
1650
                modality: find_text_matches(text, updates)
                for modality, updates in mm_prompt_updates.items()
1651
            }
1652
            text = self._apply_text_matches(
1653
                text,
1654
                mm_text_matches,
1655
                mm_item_counts,
1656
1657
            )

1658
1659
1660
            token_ids = encode_tokens(tokenizer,
                                      text,
                                      add_special_tokens=False)
1661
1662
            matched_updates = {
                modality: [match._origin for match in token_matches]
1663
1664
1665
1666
                for modality, token_matches in mm_text_matches.items()
            }

        placeholders = self._find_mm_placeholders(
1667
            matched_updates,
1668
1669
1670
            token_ids,
            mm_item_counts,
        )
1671
1672

        return token_ids, text, placeholders
1673

1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
    def _validate_mm_kwargs(
        self,
        mm_kwargs: MultiModalKwargs,
        mm_item_counts: Mapping[str, int],
    ) -> None:
        for modality, item_count in mm_item_counts.items():
            if modality in mm_kwargs.modalities:
                items = mm_kwargs.get_items(modality)
            else:
                items = []

            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,
1697
        mm_placeholders: Mapping[str, list[PlaceholderFeaturesInfo]],
1698
        mm_item_counts: Mapping[str, int],
1699
    ) -> None:
1700
1701
1702
        for modality, item_count in mm_item_counts.items():
            placeholders = mm_placeholders.get(modality, [])

1703
            if len(placeholders) != item_count:
1704
1705
1706
                # NOTE: If you are a model developer, this can also arise from
                # an inconsistency between `_call_hf_processor` and
                # `_get_mm_fields_config` implementations
1707
                raise RuntimeError(
1708
                    f"Expected there to be {item_count} prompt updates "
1709
                    f"corresponding to {item_count} {modality} items, but "
1710
                    f"instead found {len(placeholders)} prompt updates! "
1711
1712
1713
1714
                    "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`.")
1715

1716
1717
1718
1719
1720
1721
1722
1723
    def _maybe_apply_prompt_updates(
        self,
        mm_items: MultiModalDataItems,
        hf_processor_mm_kwargs: Mapping[str, object],
        prompt_ids: list[int],
        mm_kwargs: MultiModalKwargs,
        is_update_applied: bool,
    ) -> tuple[list[int], str, Mapping[str, list[PlaceholderFeaturesInfo]]]:
1724
        unbound_prompt_updates = self._get_prompt_updates(
1725
1726
1727
1728
            mm_items,
            hf_processor_mm_kwargs,
            mm_kwargs,
        )
1729
1730
        mm_prompt_updates = self._bind_and_group_updates(
            unbound_prompt_updates)
1731

1732
        mm_item_counts = mm_items.get_all_counts()
1733
1734
        self._validate_mm_kwargs(mm_kwargs, mm_item_counts)

1735
        if is_update_applied:
1736
            mm_placeholders = self._find_mm_placeholders(
1737
                mm_prompt_updates,
1738
                prompt_ids,
1739
1740
                mm_item_counts,
            )
1741
            self._validate_mm_placeholders(mm_placeholders, mm_item_counts)
1742

1743
            tokenizer = self.info.get_tokenizer()
1744
            prompt = decode_tokens(tokenizer, prompt_ids)
1745
1746
1747
        else:
            (
                prompt_ids,
1748
                prompt,
1749
                mm_placeholders,
1750
            ) = self._apply_prompt_updates(
1751
                prompt_ids,
1752
                mm_prompt_updates,
1753
                mm_item_counts,
1754
            )
1755
            self._validate_mm_placeholders(mm_placeholders, mm_item_counts)
1756

1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
        return prompt_ids, prompt, mm_placeholders

    def apply(
        self,
        prompt: Union[str, list[int]],
        mm_data: MultiModalDataDict,
        hf_processor_mm_kwargs: Mapping[str, object],
        return_mm_hashes: bool = False,
    ) -> 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)

        (
            prompt_ids,
            mm_kwargs,
1784
            mm_hashes,
1785
1786
1787
1788
1789
            is_update_applied,
        ) = self._cached_apply_hf_processor(
            prompt,
            mm_items,
            hf_processor_mm_kwargs,
1790
            return_mm_hashes=return_mm_hashes,
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
        )

        prompt_ids, prompt, mm_placeholders = self._maybe_apply_prompt_updates(
            mm_items=mm_items,
            hf_processor_mm_kwargs=hf_processor_mm_kwargs,
            prompt_ids=prompt_ids,
            mm_kwargs=mm_kwargs,
            is_update_applied=is_update_applied,
        )

1801
1802
1803
1804
        mm_placeholder_ranges = {
            modality: [item.to_range() for item in placeholders]
            for modality, placeholders in mm_placeholders.items()
        }
1805

1806
        return MultiModalInputs(
1807
            type="multimodal",
1808
            prompt=prompt,
1809
            prompt_token_ids=prompt_ids,
1810
            mm_kwargs=mm_kwargs,
1811
            mm_hashes=mm_hashes,
1812
            mm_placeholders=mm_placeholder_ranges,
1813
        )
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823


class EncDecMultiModalProcessor(BaseMultiModalProcessor[_I]):

    @abstractmethod
    def create_encoder_prompt(
        self,
        prompt: Union[str, list[int]],
        mm_data: MultiModalDataDict,
    ) -> Union[str, list[int]]:
1824
        """
1825
        Create input prompt for the encoder. HF processor will be applied on
1826
1827
        this prompt during profiling and generation.
        """
1828
1829
        raise NotImplementedError

1830
1831
1832
1833
    @property
    def pad_dummy_encoder_prompt(self) -> bool:
        return False

1834
1835
1836
1837
1838
1839
1840
1841
    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

1842
    def _get_enc_dec_inputs(
1843
1844
1845
        self,
        prompt: Union[str, list[int]],
        mm_data: MultiModalDataDict,
1846
1847
        encoder_inputs: MultiModalInputs,
    ):
1848
        tokenizer = self.info.get_tokenizer()
1849
1850
        decoder_prompt = self.create_decoder_prompt(prompt, mm_data)
        if isinstance(decoder_prompt, str):
1851
            decoder_prompt_ids = encode_tokens(tokenizer,
1852
                                               decoder_prompt,
1853
1854
                                               add_special_tokens=False)
        else:
1855
1856
            decoder_prompt_ids = decoder_prompt
            decoder_prompt = decode_tokens(tokenizer, decoder_prompt)
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866

        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
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894

    def apply(
        self,
        prompt: Union[str, list[int]],
        mm_data: MultiModalDataDict,
        hf_processor_mm_kwargs: Mapping[str, object],
        return_mm_hashes: bool = False,
    ) -> 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,
            return_mm_hashes,
        )

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