Skip to content

vllm.entrypoints.generate.beam_search.utils

Classes:

Functions:

BeamSearchOutput dataclass

The output of beam search. It contains the list of the best beam search sequences. The length of the list is equal to the beam width.

Source code in vllm/entrypoints/generate/beam_search/utils.py 
104
105
106
107
108
109
110
111
@dataclass
class BeamSearchOutput:
    """The output of beam search.
    It contains the list of the best beam search sequences.
    The length of the list is equal to the beam width.
    """

    sequences: list[BeamSearchSequence]

BeamSearchSequence dataclass

A sequence for beam search. It keeps track of the tokens and the log probability of the sequence. The text field is optional and will only be filled when the sequence is about to be returned to the user.

Source code in vllm/entrypoints/generate/beam_search/utils.py 
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
@dataclass
class BeamSearchSequence:
    """A sequence for beam search.
    It keeps track of the tokens and the log probability of the sequence.
    The text field is optional and will only be filled when the sequence is
    about to be returned to the user.
    """

    orig_prompt: TokensInput | MultiModalInput | EncoderDecoderInput

    # NOTE: Tokens represents decoder tokens in the encoder / decoder case
    tokens: list[int]
    logprobs: list[dict[int, Logprob]]
    lora_request: LoRARequest | None = None
    cum_logprob: float = 0.0
    text: str | None = None
    finish_reason: str | None = None
    stop_reason: int | str | None = None

    def get_prompt(self):
        prompt = self.orig_prompt

        if prompt["type"] == "enc_dec":
            return self._build_encoder_decoder_inputs(prompt)

        # Handle decoder-only inputs
        prompt_text = prompt.get("prompt")
        cache_salt = prompt.get("cache_salt")

        if prompt["type"] == "token":
            return tokens_input(
                self.tokens,
                prompt=prompt_text,
                cache_salt=cache_salt,
            )

        return mm_input(
            prompt_token_ids=self.tokens,
            mm_kwargs=prompt["mm_kwargs"],
            mm_hashes=prompt["mm_hashes"],
            mm_placeholders=prompt["mm_placeholders"],
            prompt=prompt_text,
            cache_salt=cache_salt,
        )

    def _build_encoder_decoder_inputs(
        self, prompt: EncoderDecoderInput
    ) -> EncoderDecoderInput:
        """Rebuild the encoder-decoder inputs with the current beam search
        sequence's tokens.

        FIXME (alex) - the encoder multimodal cache is not properly wired up
        yet, which means that currently we are running the encoder on every
        new beam because num_computed_tokens is 0 on each new request. This
        will be fixed once the cache is correctly implemented.
        """
        dec_prompt = prompt["decoder_prompt"]

        # Rebuild decoder prompt with updated tokens,
        # but keep everything else the same.
        new_dec_prompt: DecoderOnlyEngineInput
        if dec_prompt["type"] == "multimodal":
            new_dec_prompt = mm_input(
                self.tokens,
                mm_kwargs=dec_prompt["mm_kwargs"],
                mm_hashes=dec_prompt["mm_hashes"],
                mm_placeholders=dec_prompt["mm_placeholders"],
                prompt=dec_prompt.get("prompt"),
                cache_salt=dec_prompt.get("cache_salt"),
            )
        else:
            new_dec_prompt = tokens_input(
                self.tokens,
                prompt=dec_prompt.get("prompt"),
                cache_salt=dec_prompt.get("cache_salt"),
            )

        return EncoderDecoderInput(
            type="enc_dec",
            encoder_prompt=prompt["encoder_prompt"],
            decoder_prompt=new_dec_prompt,
        )

_build_encoder_decoder_inputs(prompt)

Rebuild the encoder-decoder inputs with the current beam search sequence's tokens.

FIXME (alex) - the encoder multimodal cache is not properly wired up yet, which means that currently we are running the encoder on every new beam because num_computed_tokens is 0 on each new request. This will be fixed once the cache is correctly implemented.

Source code in vllm/entrypoints/generate/beam_search/utils.py 
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
def _build_encoder_decoder_inputs(
    self, prompt: EncoderDecoderInput
) -> EncoderDecoderInput:
    """Rebuild the encoder-decoder inputs with the current beam search
    sequence's tokens.

    FIXME (alex) - the encoder multimodal cache is not properly wired up
    yet, which means that currently we are running the encoder on every
    new beam because num_computed_tokens is 0 on each new request. This
    will be fixed once the cache is correctly implemented.
    """
    dec_prompt = prompt["decoder_prompt"]

    # Rebuild decoder prompt with updated tokens,
    # but keep everything else the same.
    new_dec_prompt: DecoderOnlyEngineInput
    if dec_prompt["type"] == "multimodal":
        new_dec_prompt = mm_input(
            self.tokens,
            mm_kwargs=dec_prompt["mm_kwargs"],
            mm_hashes=dec_prompt["mm_hashes"],
            mm_placeholders=dec_prompt["mm_placeholders"],
            prompt=dec_prompt.get("prompt"),
            cache_salt=dec_prompt.get("cache_salt"),
        )
    else:
        new_dec_prompt = tokens_input(
            self.tokens,
            prompt=dec_prompt.get("prompt"),
            cache_salt=dec_prompt.get("cache_salt"),
        )

    return EncoderDecoderInput(
        type="enc_dec",
        encoder_prompt=prompt["encoder_prompt"],
        decoder_prompt=new_dec_prompt,
    )

get_beam_search_eos_token_ids(generation_config, eos_token_id)

Return the token ids that end generation: the tokenizer EOS plus the generation config's eos_token_id.

This uses a separate SamplingParams so the params sent to the engine keep their own stop_token_ids and are validated as before.

Source code in vllm/entrypoints/generate/beam_search/utils.py 
168
169
170
171
172
173
174
175
176
177
178
179
def get_beam_search_eos_token_ids(
    generation_config: dict[str, Any], eos_token_id: int | None
) -> set[int]:
    """Return the token ids that end generation: the tokenizer EOS plus the
    generation config's ``eos_token_id``.

    This uses a separate SamplingParams so the params sent to the engine keep
    their own ``stop_token_ids`` and are validated as before.
    """
    params = SamplingParams()
    params.update_from_generation_config(generation_config, eos_token_id)
    return params.all_stop_token_ids

get_beam_search_score(tokens, cumulative_logprob, eos_token_ids, length_penalty=1.0)

Calculate the beam search score with length penalty.

Adapted from

https://github.com/huggingface/transformers/blob/ccb92be23def445f2afdea94c31286f84b89eb5b/src/transformers/generation/beam_search.py#L938

Source code in vllm/entrypoints/generate/beam_search/utils.py 
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
def get_beam_search_score(
    tokens: list[int],
    cumulative_logprob: float,
    eos_token_ids: set[int],
    length_penalty: float = 1.0,
) -> float:
    """Calculate the beam search score with length penalty.

    Adapted from

    https://github.com/huggingface/transformers/blob/ccb92be23def445f2afdea94c31286f84b89eb5b/src/transformers/generation/beam_search.py#L938
    """
    seq_len = len(tokens)
    if tokens[-1] in eos_token_ids:
        seq_len -= 1

    # An aborted beam may contain only an EOS prompt token.
    return cumulative_logprob / (max(seq_len, 1) ** length_penalty)