code: def _beam_search_sample(
      selected_seq_groups: List[Tuple[List[int], SamplingParams]],
      is_prompts: List[bool],
      seq_data: Dict[int, SequenceData],
      logprobs: torch.Tensor,
  ) -> List[Tuple[List[int], List[int]]]:
      # We sample 2 * beam_width candidates to make sure that with high
      # probability we can get `beam_width` candidates in addition to
      # the finished sequences for the next iteration. See
      # https://github.com/tensorflow/tensor2tensor/blob/bafdc1b67730430d38d6ab802cbd51f9d053ba2e/tensor2tensor/utils/beam_search.py#L557-L563
      # for details. See also HF reference:
      # https://github.com/huggingface/transformers/blob/a4dd53d88e4852f023332d284ff07a01afcd5681/src/transformers/generation/utils.py#L3063-L3065
      #
      # Note: Beam search is not vectorized, so its speed can be slower than
      # other sampling methods.
      sample_idx = 0
      results = []
      for seq_group, is_prompt in zip(selected_seq_groups, is_prompts):
          seq_ids, sampling_params = seq_group
          num_parent_seqs = len(seq_ids)
          beam_width = sampling_params.best_of
          seq_group_logprobs = logprobs[
              sample_idx : sample_idx + num_parent_seqs
          ]
          if is_prompt:
              # Prompt phase.
              parent_ids = [0] * (2 * beam_width)
              _, next_token_ids = torch.topk(
                  seq_group_logprobs[0], 2 * beam_width
              )
              next_token_ids = next_token_ids.tolist()
          else:
              # Generation phase.
              cumulative_logprobs = [
                  seq_data[seq_id].cumulative_logprob
                  for seq_id in seq_ids
              ]
              cumulative_logprobs = torch.tensor(
                  cumulative_logprobs,
                  dtype=torch.float,
                  device=seq_group_logprobs.device,
              )
              seq_group_logprobs = (
                  seq_group_logprobs
                  + cumulative_logprobs.unsqueeze(dim=1)
              )
              _, topk_ids = torch.topk(
                  seq_group_logprobs.flatten(), 2 * beam_width
              )
              topk_ids = topk_ids.tolist()
              vocab_size = seq_group_logprobs.size(-1)
              parent_ids = [i // vocab_size for i in topk_ids]
              next_token_ids = [i % vocab_size for i in topk_ids]
          results.append((next_token_ids, parent_ids))
          sample_idx += num_parent_seqs
      return results
  
imports: from typing import Dict, List, Optional, Tuple
  import torch
  import torch.nn
  from bigdl.llm.vllm.model_executor.input_metadata import InputMetadata
  from bigdl.llm.vllm.sampling_params import SamplingParams, SamplingType
  from bigdl.llm.vllm.sequence import SamplerOutput, SequenceGroupMetadata, SequenceData, SequenceOutputs
  import time
label_desc: Use image node_id 12 for calling a global function with example usage: _beam_search_sample(selected_seq_groups, is_prompts, seq_data, logprobs) and returns: results