Can not initialize from list of all possible 3-letter tokens

[marinegor]

Hi, I'm trying to use BPE for biological sequences, and for that want to initialize it from all possible 3-letter combinations. Namely:

let tokens: Vec<Vec<u8>> = kwargs
    .strings
    .iter()
    .map(move |s| s.as_bytes().to_vec())
    .collect();

let enc = BytePairEncoding::from_dictionary(tokens, None);

and here I'm getting

panicked at /home/marinegor/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/bpe-0.2.1/src/byte_pair_encoding.rs:505:70:

where strings = [f'{l1}{l2}{l3} for l1 in 'AUGC' for l2 in 'AUGC' for l3 in 'AUGC'] are passed from python.

Which is confusing, since I can successfully initialize (and tokenize) strings from simpler lists of tokens, e.g. ['AB','BA'] or 2-letter combinations from the AUGC.

[gorzell]

Hi @marinegor,

Thanks for the detailed bug report! The panic you're encountering is due to a prefix closure requirement in from_dictionary that isn't well-documented.

The Problem

The BPE algorithm works by iteratively merging tokens. When you use from_dictionary, it reverse-engineers the merge history, which requires all prefixes of
multi-byte tokens to also exist in the dictionary.

When you provide only 3-letter combinations like "AAA", "AAU", etc., the algorithm can't find their required 2-letter prefixes ("AA", "AU", etc.) or single-letter
prefixes ("A", "U", "G", "C").

The Solution

You need to include all prefix levels in your dictionary:

 let mut tokens = Vec::new();

 // 1-letter tokens (4 tokens)
 for c1 in [b'A', b'U', b'G', b'C'] {
     tokens.push(vec![c1]);
 }

 // 2-letter tokens (16 tokens)
 for c1 in [b'A', b'U', b'G', b'C'] {
     for c2 in [b'A', b'U', b'G', b'C'] {
         tokens.push(vec![c1, c2]);
     }
 }

 // 3-letter tokens (64 tokens)
 for c1 in [b'A', b'U', b'G', b'C'] {
     for c2 in [b'A', b'U', b'G', b'C'] {
         for c3 in [b'A', b'U', b'G', b'C'] {
             tokens.push(vec![c1, c2, c3]);
         }
     }
 }

 let bpe = BytePairEncoding::from_dictionary(tokens, None);

This gives you 84 total tokens (4 + 16 + 64) that form a valid BPE dictionary.

From Python

If you're using the Python bindings, your initialization should look like:

 strings = (
     list('AUGC') +                                                    # 1-letter
     [f'{l1}{l2}' for l1 in 'AUGC' for l2 in 'AUGC'] +                 # 2-letter
     [f'{l1}{l2}{l3}' for l1 in 'AUGC' for l2 in 'AUGC' for l3 in 'AUGC']  # 3-letter
 )

This is also documented behavior - from the README, each multi-byte token must be constructible by merging two previous tokens in the list.

We should improve the error message here to make this requirement clearer. Would you like me to open a separate issue to track that?

[marinegor]

Sorry, I don't completely understand: why this doesn't work on 3-character combinations but works on 2-character combinations? And also, I specifically want my vocabulary to contain only multi-character elements, since only that makes sense biologically. Is that possible with current implementation of BPE? After trying with AB, BA as a vocabulary I had an impression that it's possible, and assumed what's happening with 3-letter is a bug.

[aneubeck]

Hi,
the BPE constructor won't check whether the passed in dictionary is actually a valid BPE dictionary.
The encoding functions assume that the dictionary is valid and if not then they might panic as in your case.

It isn't quite clear to me what you are trying to achieve... If the goal is to simply convert 3 byte slices into a one of the 64 possible 3 letter DNA numbers, then BPE is quite a hammer to achieve this.
Usually you would use BPE to achieve higher-level compression based on frequency analysis. A BPE dictionary construction (not part of this library (yet)) would merge the most common pairs of tokens until some dictionary size limit is reached.
The tokens chosen by this procedure is not guaranteed to pick the next 4 characters of a DNA sequence though.

If the goal is purely compression, then you could also use some standard zip algorithm.
Usually BPE cannot compete with those algorithms w.r.t. compression ratio. It is a compromise which works well as LLM input.
If you want to feed the data tokens into an LLM (which was trained on BPE tokens), then you would need a proper BPE dictionary...

[marinegor]

@aneubeck thanks for your reply, and sorry I wasn't clear in the first part :)

It isn't quite clear to me what you are trying to achieve

To put it simply, I want to have minimal token length of 3 bytes: all ATGCx3 combinations as "primary" tokens, and potentially also their combinations. I guess from your response and specification, it's not possible with the current implementation, and I'll have to first replace all 3-letter combinations with some proto-tokens, and then encode them.