A heuristic search algorithm used in sequence generation tasks (like machine translation or text generation) that explores multiple possible sequences simultaneously, keeping only the top ‘k’ most probable candidates at each step.
A smarter way for AI to write sentences. Instead of just picking the single most likely next word (which can lead to repetitive, boring text), it keeps track of the top 5 (or 10) best partial sentences at every step, eventually choosing the best complete sentence.
In autoregressive models, generating text word-by-word using Greedy Search often leads to suboptimal global sequences. Beam Search maintains a “beam width” (k). At each time step, it expands all current hypotheses by the vocabulary size, calculates the cumulative log probabilities, and prunes the list back down to the top k hypotheses. This balances computational cost with sequence quality.
Navigating a maze. Greedy search always turns toward the exit, even if it’s a dead end. Beam search sends 5 scouts down the 5 most promising paths at every intersection, ensuring you don’t miss the optimal route just because the first turn looked slightly better.
# Conceptual: Beam Search logic (simplified)
def beam_search(initial_token, beam_width=3, max_length=10):
# Start with the initial token and a probability of 1.0
hypotheses = [( [initial_token], 1.0 )]
for _ in range(max_length):
all_candidates = []
for seq, score in hypotheses:
# Get probabilities for next tokens from the model
next_tokens = get_model_probabilities(seq[-1])
for token, prob in next_tokens:
all_candidates.append((seq + [token], score * prob))
# Sort by cumulative probability and keep top k
all_candidates.sort(key=lambda x: x[1], reverse=True)
hypotheses = all_candidates[:beam_width]
return hypotheses[0][0] # Return the highest probability sequence