Replace Token Pair in BPE Sequences

EasyML Coding

Problem statement

In Byte Pair Encoding (BPE), training repeatedly finds the most frequent adjacent token pair and merges all of its occurrences into a new token. Implement the merge step, replace_pair(sequences, pair, new_id).

Given a list of token ID sequences (each a list of integers), a pair (a, b) of token IDs and a new token ID new_id, scan each sequence from left to right and replace every non-overlapping occurrence of the adjacent pair a, b with the single token new_id. Return the updated list of sequences.

Notes:

  • Scan left to right; after a merge, continue scanning from the position right after the merged pair (no overlapping reuse of tokens).
  • Sequences of length less than 2 are returned unchanged.
  • Preserve the order of sequences and of tokens that are not merged.

Example

Input:

sequences = [[1, 2, 3, 1, 2]], pair = (1, 2), new_id = 99

Output:

[[99, 3, 99]]

Reasoning: Scanning left to right, positions 0-1 contain (1,2) -> replace with 99. Next position is 3 (token 3), keep it. Positions 3-4 contain (1,2) -> replace with 99. Final sequence: [99, 3, 99].

Show hint

How would you walk a list once while sometimes consuming two elements and sometimes one?

Relevant roles: LLM Engineer, Gen AI Engineer, ML Engineer and AI Engineer.

Related free problems