| 1 | # SPDX-License-Identifier: Apache-2.0 |
| 2 | # SPDX-FileCopyrightText: Copyright contributors to the vLLM project |
| 3 | import contextlib |
| 4 | from collections.abc import Sequence |
| 5 | |
| 6 | from vllm.sampling_params import RepetitionDetectionParams |
| 7 | from vllm.v1.request import Request, RequestStatus |
| 8 | |
| 9 | |
| 10 | def _has_repeating_pattern( |
| 11 | token_ids: Sequence[int], |
| 12 | pattern_len: int, |
| 13 | repetition_min_count: int, |
| 14 | ) -> bool: |
| 15 | """Check if the tail of token_ids contains a repeating pattern. |
| 16 | |
| 17 | Compares the last pattern_len tokens against the preceding |
| 18 | (repetition_min_count - 1) repetitions of the same length. |
| 19 | """ |
| 20 | for n in range(1, pattern_len + 1): |
| 21 | target_token = token_ids[-n] |
| 22 | for m in range(1, repetition_min_count): |
| 23 | if token_ids[-(pattern_len * m + n)] != target_token: |
| 24 | return False |
| 25 | return True |
| 26 | |
| 27 | |
| 28 | def check_sequence_repetition( |
| 29 | token_ids: Sequence[int], |
| 30 | params: RepetitionDetectionParams, |
| 31 | ) -> bool: |
| 32 | """Check if a sequence of token IDs has a repetition pattern. |
| 33 | |
| 34 | Args: |
| 35 | token_ids: List of token IDs |
| 36 | params: Repetition detection parameters. |
| 37 | |
| 38 | Returns: |
| 39 | True if a repetition pattern is found, False otherwise. |
| 40 | |
| 41 | """ |
| 42 | max_pattern_size = params.max_pattern_size |
| 43 | min_pattern_size = params.min_pattern_size |
| 44 | min_count = params.min_count |
| 45 | |
| 46 | if min_pattern_size <= 0: |
| 47 | min_pattern_size = 1 |
| 48 | |
| 49 | if max_pattern_size <= 0 or min_count < 2 or min_pattern_size > max_pattern_size: |
| 50 | return False |
| 51 | |
| 52 | for pattern_len in range( |
| 53 | min_pattern_size, |
| 54 | max_pattern_size + 1, |
| 55 | ): |
| 56 | if pattern_len * min_count > len(token_ids): |
| 57 | return False |
| 58 | |
| 59 | if _has_repeating_pattern(token_ids, pattern_len, min_count): |
| 60 | return True |
| 61 | |
| 62 | return False |
| 63 | |
| 64 | |
| 65 | def remove_all(lst: list, items_to_remove: set) -> list: |
| 66 | """Remove all items from a list that are in the items_to_remove set. |
| 67 | |
| 68 | This method optimizes for the common case of removing a single item, |
| 69 | falling back to list comprehension for multiple items. |
| 70 | |
| 71 | Args: |
| 72 | lst: The list to remove items from |
| 73 | items_to_remove: Set of items to remove |
| 74 | |
| 75 | Returns: |
| 76 | Either the modified original list (for single item removal) or |
| 77 | a new list (for multiple item removal). Callers should use the |
| 78 | returned value. |
| 79 | |
| 80 | Note: |
| 81 | For single item removal, this modifies the original list in-place |
| 82 | and returns it. For multiple items, it creates and returns a new list. |
| 83 | |
| 84 | """ |
| 85 | if not items_to_remove: |
| 86 | return lst |
| 87 | |
| 88 | if len(items_to_remove) == 1: |
| 89 | # Fast path for single item removal (most common case) |
| 90 | item = next(iter(items_to_remove)) |
| 91 | with contextlib.suppress(ValueError): |
| 92 | lst.remove(item) |
| 93 | return lst |
| 94 | # For multiple items, use list comprehension |
| 95 | return [item for item in lst if item not in items_to_remove] |
| 96 | |
| 97 | |
| 98 | def check_stop(request: Request, max_model_len: int) -> bool: |
| 99 | assert not request.pooling_params |
| 100 | |
| 101 | sampling_params = request.sampling_params |
| 102 | assert sampling_params is not None |
| 103 | |
| 104 | last_token_id = request.output_token_ids[-1] |
| 105 | if last_token_id == sampling_params.eos_token_id: |
| 106 | request.status = RequestStatus.FINISHED_STOPPED |
| 107 | return True |
| 108 | |
| 109 | if last_token_id in (sampling_params.stop_token_ids or ()): |
| 110 | request.status = RequestStatus.FINISHED_STOPPED |
| 111 | request.stop_reason = last_token_id |
| 112 | return True |
| 113 | |
| 114 | if ( |
| 115 | request.num_tokens >= max_model_len |
| 116 | or request.num_output_tokens >= request.max_tokens |
| 117 | ): |
| 118 | request.status = RequestStatus.FINISHED_LENGTH_CAPPED |
| 119 | return True |
| 120 | |
| 121 | # Note(arpera): |
| 122 | # Order of checks is important for min_tokens |
| 123 | # If you decide to change the order, first look at these PRs please: |
| 124 | # 47489, 49521, and 51299 |
| 125 | # These PRs show some reasoning about the order of checks |
| 126 | if request.num_output_tokens < sampling_params.min_tokens: |
| 127 | return False |
| 128 | |
| 129 | repetition_detection = sampling_params.repetition_detection |
| 130 | if repetition_detection is not None and ( |
| 131 | check_sequence_repetition( |
| 132 | request.output_token_ids, |
| 133 | repetition_detection, |
| 134 | ) |
| 135 | ): |
| 136 | request.status = RequestStatus.FINISHED_REPETITION |
| 137 | request.stop_reason = "repetition_detected" |
| 138 | return True |
| 139 | |
| 140 | return False |