Implement Beam Search Decoding
Last updated: September 4, 2025
Quick Overview
Implement beam search over a vocabulary given log-probability distributions. Tests core LLM inference knowledge including token sequences, pruning, and heap operations.
Perplexity
September 4, 20258
4
1,853 solved
Implement beam search over a vocabulary given log-probability distributions. Tests core LLM inference knowledge including token sequences, pruning, and heap operations.
This AI-specific coding problem tests understanding of how LLM text generation works at a fundamental level. Common in Perplexity's ML-adjacent coding rounds.
What the Interviewer Expects
- Implement beam search with configurable beam width
- Handle log-probability arithmetic correctly
- Use a heap for efficient beam management
- Handle end-of-sequence tokens properly
- Discuss time and space complexity
Key Topics to Cover
How to Approach This
- Clarify input constraints and edge cases before writing code.
- Walk through your approach verbally and confirm with the interviewer before coding.
- Start with a brute force solution, then optimize. Mention time and space complexity.
- Test your solution with examples, including edge cases like empty input or duplicates.
- Consider common patterns: sliding window, two pointers, hash map, BFS/DFS, dynamic programming.
Possible Follow-up Questions
- How would you add length normalization?
- What are the trade-offs between beam search and nucleus sampling?
- How would you implement diverse beam search?
Sharpen Your Skills on Codemia
Practice similar problems with our interactive workspace, get AI feedback, and track your progress.
Practice DSA ProblemsSample Answer
Problem Analysis
The problem requires implementing beam search decoding, a common algorithm in natural language processing (NLP) used for generating sequences with a focus on retaining the most probable tokens based o...
Approach
- Initialization: Start with the initial token (usually a start token) and its log-probability. Initialize a priority queue (min-heap) to store the sequences and their cumulative log-probabilitie...
Submit Your Answer
