ONE is preparing: 01 / INITIALIZING MODEL ROUTER. Evaluating routing across providers.
Current state
01 / INITIALIZING MODEL ROUTER.

Evaluating routing across providers.

Start learning
← LLM & NLP

AI Builder

Beam Search — tìm kiếm chùm tia

Vietnamese onlyThe learning content is available in Vietnamese only. The surrounding interface follows your language.

Thuật toán giải mã giữ lại k ứng viên tốt nhất ở mỗi bước, cân bằng giữa chất lượng và chi phí tính toán.

lesson90 minLLM & NLPAI Engineer

Thử thách

GPT sinh câu từ prompt “Tôi yêu ___”. Bước 1 có năm ứng viên: “em” (42%), “gia đình” (24%), “cà phê” (20%), “Việt Nam” (8%), “mèo” (6%). Nếu chỉ giữ một từ tốt nhất thì sao?

Cây beam

Với một mô hình ngôn ngữ, mỗi bước sinh ra một phân phối trên toàn bộ từ vựng. Có ba cách giải mã chính: greedy, beam search và sampling. Mỗi cách tối ưu cho một mục tiêu khác nhau.

Beam width kHành viĐộ phức tạp
k = 1Greedy: chỉ giữ một đườngNhanh nhất, chất lượng thấp nhất
k = 4 đến 10Giữ vài đường tốt nhất song songĐiểm cân bằng cho dịch máy, tóm tắt
k lớnGần như tìm kiếm vét cạnChậm, tối ưu hơn

Length penalty α điều chỉnh việc ưu tiên câu dài hay ngắn: α bằng 0 thiên vị câu ngắn; α trong khoảng 0,6 đến 0,8 là điểm cân bằng cho dịch máy.

So sánh ba chiến lược

Cùng một prompt, ba chiến lược cho ra câu khác nhau:

Chiến lượcVí dụ đầu raƯu điểmNhược điểmDùng cho
Greedy (k = 1)“Tôi yêu em nhiều lắm.”Cực nhanh, xác định, chi phí thấpHay bỏ lỡ câu tốt hơn do tham ăn từng bướcBản nháp nhanh
Beam search (k = 5)Câu có xác suất tích luỹ cao nhất trong các nhánhChất lượng cao, ổn định, tốt hơn greedyChậm hơn k lần; luôn cùng đầu ra, thiếu đa dạngDịch máy, tóm tắt, captioning, code completion
Sampling (top-p 0,9, T 0,8)“Tôi yêu cà phê buổi sáng.”Đa dạng, sáng tạo, mỗi lần một khácKém ổn định, đôi khi sai ngữ nghĩaChatbot, kể chuyện, brainstorm

Beam search đôi khi tìm được xác suất tổng cao hơn greedy, còn sampling cho ra câu khác hoàn toàn.

Khoảnh khắc A-ha

Beam search giữ k con đường tốt nhất song song, không đặt cược vào một lựa chọn duy nhất. Giống đội thám hiểm chia nhóm: nhóm nào tìm được đường tốt nhất thì thắng.

Điều kỳ diệu: một ứng viên có xác suất thấp ở bước đầu (như “gia đình” chỉ 24%) vẫn có thể dẫn đến câu tốt nhất, nếu các token tiếp theo có xác suất điều kiện cao.

Thử thách nhanh

Beam search luôn cho kết quả giống nhau với cùng một input. ChatGPT thì mỗi lần trả lời khác. ChatGPT dùng gì?
Bạn chạy beam search với k = 5 cho câu dài 20 token, vocab cỡ 50 nghìn. Mỗi bước cần xét bao nhiêu ứng viên trước khi cắt tỉa?

Lý thuyết và code

Beam search giữ k chuỗi ứng viên (beam) tốt nhất ở mỗi bước, mở rộng song song cho đến khi tất cả kết thúc bằng token kết thúc hoặc đạt độ dài tối đa. Đây là chiến lược giải mã xác định, khác với các phương pháp ngẫu nhiên như top-k, top-p hay chỉnh temperature. Cùng input, beam search luôn cho cùng output.

score(Y)=1∣Y∣α∑t=1∣Y∣log⁡P(yt∣y<t,X)\text{score}(Y) = \frac{1}{|Y|^{\alpha}} \sum_{t=1}^{|Y|} \log P(y_t \mid y_{<t}, X)
Vp=min⁡{V′⊆V:∑w∈V′p(w)≥p}V_p = \min \Big\{ V' \subseteq V : \sum_{w \in V'} p(w) \geq p \Big\}
p′(w)=p(w)⋅1[w∈Vp]∑w′∈Vpp(w′)p'(w) = \frac{p(w) \cdot \mathbb{1}[w \in V_p]}{\sum_{w' \in V_p} p(w')}

Top-p = 0,9 nghĩa là chỉ chọn từ trong nhóm 90% xác suất tích luỹ. Kết hợp với temperature T để điều chỉnh độ sáng tạo.

Ví dụ với Hugging Face

huggingface_generate_beam.py

from transformers import AutoModelForCausalLM, AutoTokenizer

model = AutoModelForCausalLM.from_pretrained("gpt2-medium")
tokenizer = AutoTokenizer.from_pretrained("gpt2-medium")

prompt = "Tôi yêu "
inputs = tokenizer(prompt, return_tensors="pt")

# 1. Greedy (num_beams = 1, không sample)
greedy = model.generate(
    **inputs,
    max_new_tokens=20,
    num_beams=1,
    do_sample=False,
)
print("Greedy:", tokenizer.decode(greedy[0], skip_special_tokens=True))

# 2. Beam search (num_beams = 5)
beam = model.generate(
    **inputs,
    max_new_tokens=20,
    num_beams=5,
    do_sample=False,
    length_penalty=0.8,          # 0.6–1.0 là phổ biến
    early_stopping=True,          # dừng khi đủ k beam đạt <eos>
    no_repeat_ngram_size=3,       # chặn lặp 3-gram (tránh mode collapse)
    num_return_sequences=3,       # trả về 3 beam tốt nhất
)
for i, seq in enumerate(beam):
    print(f"Beam {i}:", tokenizer.decode(seq, skip_special_tokens=True))

# 3. Nucleus sampling (top_p = 0.9)
sample = model.generate(
    **inputs,
    max_new_tokens=20,
    do_sample=True,
    top_p=0.9,
    top_k=50,
    temperature=0.8,
    num_return_sequences=3,
)
for i, seq in enumerate(sample):
    print(f"Sample {i}:", tokenizer.decode(seq, skip_special_tokens=True))

# 4. Diverse beam search
diverse = model.generate(
    **inputs,
    max_new_tokens=20,
    num_beams=6,
    num_beam_groups=3,            # chia k thành 3 nhóm
    diversity_penalty=1.0,         # hình phạt giữa các nhóm
    num_return_sequences=3,
    do_sample=False,
)
for i, seq in enumerate(diverse):
    print(f"Diverse {i}:", tokenizer.decode(seq, skip_special_tokens=True))

Beam search tự viết tay

beam_search_from_scratch.py

import torch
import torch.nn.functional as F
from typing import List, Tuple

def beam_search_decode(
    model,
    input_ids: torch.Tensor,
    beam_width: int = 5,
    max_length: int = 30,
    length_penalty: float = 0.7,
    eos_token_id: int = 2,
) -> List[Tuple[torch.Tensor, float]]:
    """
    Beam search giải mã tự viết tay.
    Trả về danh sách (sequence, score) đã sắp xếp.
    """
    device = input_ids.device

    # Mỗi beam: (sequence, cumulative_log_prob, is_done)
    beams: List[Tuple[torch.Tensor, float, bool]] = [
        (input_ids, 0.0, False)
    ]

    for step in range(max_length):
        candidates: List[Tuple[torch.Tensor, float, bool]] = []

        for seq, score, done in beams:
            # Beam đã gặp <eos> thì không mở rộng nữa.
            if done:
                candidates.append((seq, score, True))
                continue

            # Forward pass
            with torch.no_grad():
                logits = model(seq).logits[:, -1, :]  # (1, V)
                log_probs = F.log_softmax(logits, dim=-1).squeeze(0)

            # Lấy top-k token
            top_log_probs, top_indices = log_probs.topk(beam_width)

            for lp, idx in zip(top_log_probs.tolist(), top_indices.tolist()):
                new_seq = torch.cat(
                    [seq, torch.tensor([[idx]], device=device)],
                    dim=1,
                )
                new_score = score + lp
                new_done = (idx == eos_token_id)
                candidates.append((new_seq, new_score, new_done))

        # Prune: lấy top beam_width theo score sau length penalty
        def _rank(item):
            seq, sc, _ = item
            L = seq.size(1)
            return sc / (L ** length_penalty)

        candidates.sort(key=_rank, reverse=True)
        beams = candidates[:beam_width]

        # Nếu tất cả beam đã done thì dừng
        if all(done for _, _, done in beams):
            break

    # Trả về (seq, score đã chia length penalty)
    return [
        (seq, sc / (seq.size(1) ** length_penalty))
        for seq, sc, _ in beams
    ]

Tóm tắt

  • Beam search giữ k ứng viên tốt nhất song song (k là beam width hoặc num_beams).
  • k = 1 là greedy (nhanh, kém). k từ 4 đến 10 là điểm cân bằng cho dịch máy và tóm tắt. k càng lớn càng chậm.
  • Length penalty chia điểm cho |Y|^α để tránh thiên vị câu ngắn; α khoảng 0,6 đến 1,0 là phổ biến.
  • Dịch máy, tóm tắt, captioning dùng beam search. Chatbot và kể chuyện dùng sampling (top-p và temperature).
  • Beam search xác định (cùng input, cùng output); sampling tạo đa dạng.
  • Diverse beam search giảm mode collapse; constrained beam search cho phép ép hoặc cấm cụm từ cụ thể.

Continue the module

Lesson 9 of 10