Find Most Frequent Token Pair for BPE
Problem statement
Implement most_frequent_pair(sequences), which finds the most frequent adjacent pair of token IDs across a list of token ID sequences. This is the core counting step of Byte Pair Encoding (BPE) training: at each iteration, BPE finds the most common adjacent pair in the corpus and merges it into a new token.
Procedure
- For each sequence (a list of integer token IDs), look at every adjacent pair
(seq[i], seq[i+1]). - Count how many times each ordered pair appears across all sequences combined.
- Return the pair with the highest count as a tuple
(a, b). - If several pairs tie for the highest count, return the one that appears first (earliest position) when scanning the sequences in order, left to right within each sequence.
- If no adjacent pairs exist (all sequences have length < 2, or the input is empty), return
None.
Constraints
- Token IDs are non-negative integers.
- Use pure Python and/or NumPy only.
Example
Input:
sequences = [[1, 2, 3, 1, 2]]
Output:
(1, 2)
Reasoning: Adjacent pairs are (1,2), (2,3), (3,1), (1,2). Counts: (1,2)=2, (2,3)=1, (3,1)=1. The most frequent pair is (1,2).
Show hint
Which data structure lets you count arbitrary ordered pairs in one pass?
Relevant roles: LLM Engineer, Gen AI Engineer, ML Engineer and AI Engineer.
Related free problems
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium