Implement Beam Search

Apple interview questions are typically proprietary and not publicly released, so no exact match exists online for a problem titled "Implement Beam Search" with those specific tags (Machine Learning, NLP, Decoding, Search). Standard beam search implementations in NLP contexts, as described in resources like machine learning tutorials, focus on decoding sequences from probability matrices.[1][2]

Typical Problem Statement

Beam search is used in NLP tasks like machine translation or text generation to find high-probability output sequences from a model's predictions, balancing completeness and efficiency. Given a sequence of probability distributions (e.g., from a neural decoder) over a vocabulary and a beam width k, implement beam search to generate the top-k most likely sequences up to a maximum length, using log-probabilities to avoid underflow. Scoring often multiplies (or sums in log space) probabilities along each path.[2]

Core Algorithm Steps

• Initialize a beam with the start token (score 0).
• At each step t (up to max_length):
  • Expand each beam candidate by appending every vocabulary token.
  • Compute new scores: previous_score + log(prob[token | previous_sequence]).
  • Prune to top-k candidates by score.
• Halt paths on end-of-sequence token or max length.[1][2]

Example Input/Output

Input:

• probs: 3x4 matrix (3 timesteps, vocab size 4: ['a','b','c','<end>'])
  Timestep 1: [0.1, 0.4, 0.4, 0.1] Timestep 2: [0.3, 0.3, 0.2, 0.2] Timestep 3: [0.2, 0.1, 0.6, 0.1]
• beam_width = 2, max_length = 3

Output (top sequences with scores):

• ['b', 'a', '<end>'] score ≈ -1.20
• ['c', 'a', '<end>'] score ≈ -1.39
  (Greedy would pick 'b' then 'a', but beam explores more paths).[2]

Constraints

• Vocabulary size V: up to 50,000 (limits naive expansion to k × V per step).
• Sequence length T: 50–100.
• Beam width k: 5–20.
• Time: O(T × k × V), optimize with pruning or early stopping.
  No optimality guarantee; larger k improves quality but slows decoding.[1][2]