Find Most Frequent Token Pair for BPE

EasyML Coding

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
  1. For each sequence (a list of integer token IDs), look at every adjacent pair (seq[i], seq[i+1]).
  2. Count how many times each ordered pair appears across all sequences combined.
  3. Return the pair with the highest count as a tuple (a, b).
  4. 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.
  5. 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