How to Implement Beam Search and Parallel Sampling in vLLM

vLLM implements beam search through a Python orchestration layer that batches active beams into single forward passes, while parallel sampling leverages the GPU-accelerated Sampler class to process multiple independent requests simultaneously using vectorized Gumbel sampling.

Implementing beam search and parallel sampling in vLLM requires understanding two distinct generation architectures within the inference engine. The vllm-project/vllm repository provides optimized implementations that maximize GPU utilization through batched operations and in-place tensor transformations. This guide examines the source code structure in vllm/beam_search.py and vllm/v1/worker/gpu/sample/sampler.py to demonstrate how to deploy both features effectively.

Understanding Beam Search Architecture

Beam search in vLLM is a deterministic decoding strategy that maintains multiple candidate sequences (beams) and selects the highest-scoring continuations at each step. The implementation balances computational efficiency with search accuracy through aggressive batching.

Core Data Structures

The beam search implementation defines three primary classes in vllm/beam_search.py:

• BeamSearchSequence – Stores the original prompt, generated token IDs, per-token log-probabilities, cumulative log-probability, and finish reason.
• BeamSearchInstance – Manages the list of active beams and completed sequences for a single input prompt.
• BeamSearchOutput – The final container returned to users containing the top-scoring sequences.

# https://github.com/vllm-project/vllm/blob/main/vllm/beam_search.py

class BeamSearchSequence:
    tokens: List[int]
    cum_logprob: float
    # ... additional fields

class BeamSearchInstance:
    beams: List[BeamSearchSequence]
    completed: List[BeamSearchSequence]

Scoring and Selection Logic

The scoring function get_beam_search_score applies length normalization to prevent bias toward shorter sequences:

# https://github.com/vllm-project/vllm/blob/main/vllm/beam_search.py#L84-L108

def get_beam_search_score(cum_logprob, seq_len, length_penalty):
    return cum_logprob / (seq_len ** length_penalty)

The helper create_sort_beams_key_function generates sorting keys for ranking candidates. At each generation step, vLLM creates 2 * beam_width candidate extensions per active beam, scores them using the normalized log-probability, and retains only the top beam_width sequences.

The beam_search Entry Point

The LLM.beam_search method in vllm/entrypoints/llm.py orchestrates the search loop:

1. Converts user prompts to internal ProcessorInputs.
2. Creates SamplingParams with logprobs=2*beam_width and max_tokens=1 for stepwise generation.
3. Initializes a BeamSearchInstance for each input prompt.
4. Iteratively flattens all active beams into all_beams and executes a batched forward pass via _render_and_run_requests.
5. Updates cumulative log-probabilities and sorts candidates using the length-penalized score.

# https://github.com/vllm-project/vllm/blob/main/vllm/entrypoints/llm.py#L76-L135

def beam_search(self, prompts, params, ...):
    # Creates BeamSearchInstances and runs stepwise generation

    for step in range(max_tokens):
        all_beams = [beam for instance in instances for beam in instance.beams]
        # ... batched model execution

Configuration Parameters

Beam-specific hyperparameters are defined in BeamSearchParams within vllm/sampling_params.py:

# https://github.com/vllm-project/vllm/blob/main/vllm/sampling_params.py#L93-L106

class BeamSearchParams:
    beam_width: int
    max_tokens: int
    ignore_eos: bool = False
    temperature: float = 0.0
    length_penalty: float = 1.0

Understanding Parallel Sampling Architecture

Parallel sampling enables concurrent processing of independent generation requests through vectorized GPU operations. Unlike beam search, which explores variations of a single prompt, parallel sampling handles diverse prompts simultaneously.

The Sampler Class

The core implementation resides in vllm/v1/worker/gpu/sample/sampler.py. The Sampler receives a logits tensor of shape [num_requests, vocab_size] and applies all sampling transformations in-place:

1. Logit bias application via LogitBiasState
2. Penalty application (frequency, presence, repetition) via PenaltiesState
3. Bad words masking via BadWordsState
4. Temperature scaling, min-p filtering, and top-k/top-p truncation
5. Gumbel sampling via gumbel_sample in vllm/v1/worker/gpu/sample/gumbel.py

# https://github.com/vllm-project/vllm/blob/main/vllm/v1/worker/gpu/sample/sampler.py

class Sampler:
    def __call__(self, logits, sampling_states):
        # In-place modifications

        logits = self.apply_bias(logits)
        logits = self.apply_penalties(logits)
        # ... temperature, top-k/p processing

        sampled_tokens = gumbel_sample(logits, seeds)
        return SamplerOutput(sampled_tokens)

Batch Processing Flow

The sampler processes up to max_num_reqs concurrently. The sample method performs:

• FP32 conversion of logits for numerical stability
• Sequential in-place transformations (bias → penalties → bad words → temperature → min-p → top-k/p)
• GPU-accelerated multinomial sampling using pre-generated random seeds
• Output construction as SamplerOutput with shape [num_requests, 1]

This vectorized approach ensures that tensor-parallel, pipeline-parallel, and data-parallel configurations (defined in vllm/config/parallel.py) operate transparently on the request batch.

Practical Implementation Examples

Running Beam Search

Use BeamSearchParams to configure the search width and length penalties:

from vllm import LLM, BeamSearchParams

llm = LLM(model="facebook/opt-125m")

prompts = ["Explain quantum computing in two sentences."]
beam_params = BeamSearchParams(
    beam_width=4,
    max_tokens=50,
    temperature=0.7,
    length_penalty=0.9,
)

outputs = llm.beam_search(prompts, beam_params)

for out in outputs:
    for i, seq in enumerate(out.sequences):
        print(f"Beam {i+1}: {seq.text}")

Key files: vllm/entrypoints/llm.py (orchestration), vllm/beam_search.py (scoring), vllm/sampling_params.py (configuration).

Parallel Sampling with Concurrency Limits

Process multiple prompts simultaneously using LLM.generate with concurrency_limit:

from vllm import LLM, SamplingParams

llm = LLM(model="facebook/opt-125m")

prompts = [
    "Write a haiku about the moon.",
    "Summarize the plot of 'Inception'.",
    "Translate 'Hello, world!' to Japanese."
]

sampling_params = SamplingParams(
    max_tokens=30,
    temperature=0.8,
    top_p=0.9,
)

results = llm.generate(prompts, sampling_params, concurrency_limit=2)

for i, out in enumerate(results):
    print(f"Prompt {i+1}: {out.outputs[0].text}")

The Sampler class in vllm/v1/worker/gpu/sample/sampler.py handles the parallel execution automatically, applying all sampling parameters to the batch in a single GPU kernel launch.

Advanced Beam Search with LoRA

Beam search supports LoRA adapters through the lora_request parameter:

from vllm import LLM, BeamSearchParams, LoRARequest

llm = LLM(model="facebook/opt-125m")

lora = LoRARequest(
    lora_name="my_lora_adapter",
    adapter_name="default",
    lora_int8_threshold=6.0,
)

prompts = ["Give a short intro to reinforcement learning."]
beam_params = BeamSearchParams(
    beam_width=5,
    max_tokens=60,
    temperature=0.0,
)

outputs = llm.beam_search(prompts, beam_params, lora_request=lora)

Key files: vllm/entrypoints/llm.py (parameter definition), vllm/lora/request.py (LoRA handling).

Summary

• Beam search operates via the BeamSearchInstance class in vllm/beam_search.py, flattening active beams into all_beams for batched forward passes and scoring candidates with length-normalized log-probabilities via get_beam_search_score.
• Parallel sampling executes through the Sampler class in vllm/v1/worker/gpu/sample/sampler.py, processing up to max_num_reqs simultaneously with in-place logit transformations and GPU-accelerated Gumbel sampling.
• Both features are accessible through the high-level LLM class: beam_search() for exact candidate exploration and generate() for concurrent independent sampling.
• Configuration is managed through BeamSearchParams and SamplingParams in vllm/sampling_params.py, with parallelism settings defined in vllm/config/parallel.py.

Frequently Asked Questions

What is the difference between beam search and parallel sampling in vLLM?

Beam search maintains and scores multiple candidate sequences for a single input prompt to find the globally optimal completion, while parallel sampling processes entirely independent prompts concurrently through vectorized GPU operations. Beam search uses the beam_search() method with length-penalized scoring, whereas parallel sampling uses generate() with standard sampling parameters like temperature and top_p.

How does vLLM handle batching during beam search execution?

At each generation step, the LLM.beam_search method in vllm/entrypoints/llm.py flattens all active beams across all prompts into a single list called all_beams. This list is processed in one batched forward pass through the model, producing logits for all beam candidates simultaneously. The engine then expands each beam by 2 * beam_width candidates, scores them using get_beam_search_score, and retains only the top performers for the next iteration.

Can I use beam search with LoRA adapters in vLLM?

Yes, the LLM.beam_search method accepts an optional lora_request parameter of type LoRARequest defined in vllm/lora/request.py. When provided, vLLM applies the LoRA adapter weights during the forward passes for all beam candidates, allowing you to run beam search with fine-tuned models without merging weights into the base model.

Which sampling parameters affect parallel sampling performance?

While parameters like temperature, top_k, top_p, min_p, and logit_bias affect output quality, they do not impact the GPU execution speed because the Sampler class applies all transformations in-place on the logits tensor using vectorized operations. The primary performance factor is the concurrency_limit in LLM.generate(), which controls how many requests are batched together for the Sampler to process in a single step.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}