Replace Token Pair in BPE Sequences
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
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium