Loading…
Glossary term
A decoding method that keeps several candidate sequences in play and picks the best overall.
Beam search keeps the best k partial sequences at each step instead of just one. It extends each, scores the results and keeps the top k again, finally returning the best complete sequence.
It explores more options than greedy decoding and was common in translation.
Beam search sketch
import math
def beam_search(next_probs, start, steps, k=3):
beams = [([start], 0.0)]
for _ in range(steps):
candidates = []
for seq, score in beams:
for tok, p in next_probs(seq).items():
candidates.append((seq + [tok], score + math.log(p)))
beams = sorted(candidates, key=lambda b: b[1], reverse=True)[:k]
return beamsIt finds higher-probability sentences than greedy decoding, though chat models usually prefer sampling.