| 1 | # SPDX-License-Identifier: Apache-2.0 |
| 2 | # SPDX-FileCopyrightText: Copyright contributors to the vLLM project |
| 3 | import itertools |
| 4 | from collections.abc import Iterable, Iterator, MutableSequence |
| 5 | from dataclasses import dataclass, field |
| 6 | from typing import overload |
| 7 | |
| 8 | |
| 9 | # We use dataclass for now because it is used for |
| 10 | # openai server output, and msgspec is not serializable. |
| 11 | # TODO(sang): Fix it. |
| 12 | @dataclass |
| 13 | class Logprob: |
| 14 | """Infos for supporting OpenAI compatible logprobs and token ranks. |
| 15 | |
| 16 | Attributes: |
| 17 | logprob: The logprob of chosen token |
| 18 | rank: The vocab rank of chosen token (>=1) |
| 19 | decoded_token: The decoded chosen token index |
| 20 | |
| 21 | """ |
| 22 | |
| 23 | logprob: float |
| 24 | rank: int | None = None |
| 25 | decoded_token: str | None = None |
| 26 | |
| 27 | |
| 28 | LogprobsOnePosition = dict[int, Logprob] |
| 29 | |
| 30 | |
| 31 | @dataclass |
| 32 | class FlatLogprobs(MutableSequence[LogprobsOnePosition | None]): |
| 33 | """Flat logprobs of a request into multiple primitive type lists. |
| 34 | |
| 35 | Compared to list[dict[int, Logprob]], this data structure reduced GC |
| 36 | overhead significantly. As it flattened logprob information for |
| 37 | all positions and ranks in to multiple primitive type lists (i.e. |
| 38 | logprobs, token_ids, ranks per token_ids, decoded_tokens). |
| 39 | So regardless of the sequence length and top_logprobs setup, |
| 40 | FlatLogprobs would only introduce a constant amount of objects. |
| 41 | |
| 42 | As each position might contains different amount of ranks, |
| 43 | start_indices_per_position would be used to access the logprob ranges |
| 44 | for different positions. |
| 45 | |
| 46 | NOTE: To reduce the migration overhead and improve backward compatibility, |
| 47 | we support the key Sequence APIs of list, so it could act as |
| 48 | list[LogprobsOnePosition] |
| 49 | """ |
| 50 | |
| 51 | # Start / end indices to indicate the range of logprobs for each position. |
| 52 | start_indices: list[int] = field(default_factory=list) |
| 53 | end_indices: list[int] = field(default_factory=list) |
| 54 | |
| 55 | # Flatten Logprob information for (each position, rank). |
| 56 | # For position <i>, the logprobs are ranged |
| 57 | # from self.start_indices[i] to self.end_indices[i] (exclusive). |
| 58 | token_ids: list[int] = field(default_factory=list) |
| 59 | logprobs: list[float] = field(default_factory=list) |
| 60 | ranks: list[int | None] = field(default_factory=list) |
| 61 | decoded_tokens: list[str | None] = field(default_factory=list) |
| 62 | |
| 63 | def append(self, logprobs_one_position: LogprobsOnePosition | None) -> None: |
| 64 | """Appends the container with logprobs for the next position.""" |
| 65 | self.start_indices.append(len(self.logprobs)) |
| 66 | if logprobs_one_position: |
| 67 | for token_id, logprob in logprobs_one_position.items(): |
| 68 | self.token_ids.append(token_id) |
| 69 | self.logprobs.append(logprob.logprob) |
| 70 | self.ranks.append(logprob.rank) |
| 71 | self.decoded_tokens.append(logprob.decoded_token) |
| 72 | self.end_indices.append(len(self.logprobs)) |
| 73 | |
| 74 | def append_fast( |
| 75 | self, |
| 76 | token_ids: list[int], |
| 77 | logprobs: list[float], |
| 78 | ranks: itertools.chain[int], |
| 79 | decoded_tokens: Iterable[str | None], |
| 80 | ) -> None: |
| 81 | """Appends logprobs for the next position without creating |
| 82 | the intermediate logprob dictionary. |
| 83 | """ |
| 84 | self.start_indices.append(len(self.logprobs)) |
| 85 | for token_id, logprob, rank, decoded_token in zip( |
| 86 | token_ids, logprobs, ranks, decoded_tokens |
| 87 | ): |
| 88 | self.token_ids.append(token_id) |
| 89 | self.logprobs.append(logprob) |
| 90 | self.ranks.append(rank) |
| 91 | self.decoded_tokens.append(decoded_token) |
| 92 | self.end_indices.append(len(self.logprobs)) |
| 93 | |
| 94 | def extend(self, logprobs_multi_positions) -> None: |
| 95 | """Extends the container with logprobs for the next multiple positions.""" |
| 96 | for logprobs_one_position in logprobs_multi_positions: |
| 97 | self.append(logprobs_one_position) |
| 98 | |
| 99 | def __len__(self) -> int: |
| 100 | """Gets number of positions stored in the container.""" |
| 101 | return len(self.start_indices) |
| 102 | |
| 103 | @overload |
| 104 | def __getitem__(self, position: int) -> LogprobsOnePosition: ... |
| 105 | |
| 106 | @overload |
| 107 | def __getitem__(self, s: slice, /) -> "FlatLogprobs": ... |
| 108 | |
| 109 | def __getitem__(self, index: int | slice): |
| 110 | """Extracts logprobs of a given position or slice.""" |
| 111 | if isinstance(index, int): |
| 112 | return { |
| 113 | self.token_ids[i]: Logprob( |
| 114 | logprob=self.logprobs[i], |
| 115 | rank=self.ranks[i], |
| 116 | decoded_token=self.decoded_tokens[i], |
| 117 | ) |
| 118 | for i in range(self.start_indices[index], self.end_indices[index]) |
| 119 | } |
| 120 | elif isinstance(index, slice): |
| 121 | selected_starts = self.start_indices[index] |
| 122 | selected_ends = self.end_indices[index] |
| 123 | # Empty slices have no source offset to normalize. |
| 124 | if not selected_starts: |
| 125 | return FlatLogprobs() |
| 126 | min_index = selected_starts[0] |
| 127 | max_index = selected_ends[-1] |
| 128 | return FlatLogprobs( |
| 129 | # Shift updated start_indices and end_indices to |
| 130 | # be 0-indexed |
| 131 | start_indices=[i - min_index for i in selected_starts], |
| 132 | end_indices=[i - min_index for i in selected_ends], |
| 133 | token_ids=self.token_ids[min_index:max_index], |
| 134 | logprobs=self.logprobs[min_index:max_index], |
| 135 | ranks=self.ranks[min_index:max_index], |
| 136 | decoded_tokens=self.decoded_tokens[min_index:max_index], |
| 137 | ) |
| 138 | else: |
| 139 | raise TypeError(f"Invalid index type: {type(index)}") |
| 140 | |
| 141 | def __setitem__(self, item, value) -> None: |
| 142 | raise TypeError("Cannot set logprobs in FlatLogprobs") |
| 143 | |
| 144 | def __delitem__(self, item) -> None: |
| 145 | raise TypeError("Cannot delete logprobs from FlatLogprobs") |
| 146 | |
| 147 | def insert(self, index: int, value: dict[int, Logprob] | None) -> None: |
| 148 | raise TypeError("Cannot insert logprobs to FlatLogprobs") |
| 149 | |
| 150 | def __iter__(self) -> Iterator[LogprobsOnePosition]: |
| 151 | """Iterates the container and yields LogprobsOnePosition for |
| 152 | each position. |
| 153 | """ |
| 154 | for i in range(0, len(self.start_indices)): |
| 155 | yield self.__getitem__(i) |
| 156 | |
| 157 | |
| 158 | # {token_id -> logprob} per each sequence group. None if the corresponding |
| 159 | # sequence group doesn't require prompt logprob. |
| 160 | PromptLogprobs = FlatLogprobs | list[LogprobsOnePosition | None] |
| 161 | # {token_id -> logprob} for each sequence group. |
| 162 | SampleLogprobs = FlatLogprobs | list[LogprobsOnePosition] |
| 163 | |
| 164 | |
| 165 | def create_prompt_logprobs(flat_logprobs: bool) -> PromptLogprobs: |
| 166 | """Creates a container to store prompt logprobs for a request.""" |
| 167 | logprobs: PromptLogprobs = FlatLogprobs() if flat_logprobs else [] |
| 168 | # NOTE: logprob of first prompt token is None. |
| 169 | logprobs.append(None) |
| 170 | return logprobs |
| 171 | |
| 172 | |
| 173 | def create_sample_logprobs(flat_logprobs: bool) -> SampleLogprobs: |
| 174 | """Creates a container to store decode logprobs for a request.""" |
| 175 | return FlatLogprobs() if flat_logprobs else [] |
| 176 | |
| 177 | |
| 178 | def append_logprobs_for_next_position( |
| 179 | request_logprobs: PromptLogprobs | SampleLogprobs, |
| 180 | token_ids: list[int], |
| 181 | logprobs: list[float], |
| 182 | decoded_tokens: Iterable[str | None], |
| 183 | rank: int, |
| 184 | num_logprobs: int, |
| 185 | ) -> None: |
| 186 | """Appends logprobs for the next position.""" |
| 187 | if num_logprobs == -1: |
| 188 | num_logprobs = len(logprobs) |
| 189 | # We do not need a special case for the sampled token |
| 190 | # being in the topk, since inserting duplicated data |
| 191 | # into a dictionary twice is the same as doing it once. |
| 192 | topk_ranks = range(1, num_logprobs + 1) |
| 193 | ranks = itertools.chain((rank,), topk_ranks) |
| 194 | |
| 195 | if isinstance(request_logprobs, FlatLogprobs): |
| 196 | request_logprobs.append_fast(token_ids, logprobs, ranks, decoded_tokens) |
| 197 | else: |
| 198 | request_logprobs.append( |
| 199 | { |
| 200 | token_id: Logprob( |
| 201 | logprob=logprob, |
| 202 | rank=rank, |
| 203 | decoded_token=token, |
| 204 | ) |
| 205 | for token_id, logprob, rank, token in zip( |
| 206 | token_ids, logprobs, ranks, decoded_tokens |
| 207 | ) |
| 208 | } |
| 209 | ) |