Thread (17 posts)

Yes, exactly! In section 3.1, the subscript $i$ indexes over the $n$ data categories whose mixture proportions they are trying to estimate.

Specifically:

• $i \in \{1, 2, ..., n\}$ where $n$ is the number of categories
• $\mathcal{D}_i$ represents the data distribution for category $i$
• $D_i$ represents the sample corpus from category $i$
• $\alpha_i^*$ represents the true (unknown) proportion of category $i$ in the tokenizer's training data
• $c_{i,p}^{(t)}$ represents the count of token pair $p$ in category $i$'s corpus after applying the first $t-1$ merge rules

For example:

• If estimating language mixtures: $i$ might index over {English, French, German, Spanish, ...}
• If estimating domain mixtures: $i$ might index over {Web, Books, Code, Academic, Wikipedia}
• If estimating programming language mixtures: $i$ might index over {Python, Java, JavaScript, C++, ...}

The goal is to solve for the mixture weights $\hat{\alpha} = (\hat{\alpha}_1, \hat{\alpha}_2, ..., \hat{\alpha}_n)$ that best explain the observed BPE merge sequence, where $\sum_{i=1}^n \hat{\alpha}_i = 1$.

Yes, exactly! In §3.1, the subscript $i$ indexes over the $n$ data categories whose mixture proportions the authors are trying to estimate.

Specifically:

• $\mathcal{D}_i$ represents the data distribution for category $i$
• $\alpha_i^*$ is the true (unknown) proportion of category $i$ in the tokenizer's training data
• The constraint $\sum_{i=1}^n \alpha_i^* = 1$ ensures these proportions form a valid probability distribution

The categories could be:

• Natural languages: English, French, Spanish, Russian, etc.
• Programming languages: Python, Java, JavaScript, etc.
• Data domains: Wikipedia, web crawl, books, academic papers, code

So if you're trying to infer the language mixture of a tokenizer trained on 10 languages, then $i \in \{1, 2, ..., 10\}$ would index those 10 languages. The goal is to estimate each $\alpha_i$ - what fraction of the training data came from each language.

Great question! This is indeed a bit confusing in the paper. Let me clarify what's happening in §3.2.

Yes, you DO have access to the tokenizer

From the problem setup in §3:

"Then suppose we receive a BPE tokenizer, which was trained on a large sample of text from the mixture..."

Specifically, you have access to the tokenizer's ordered merge list $m^{(1)}, ..., m^{(M)}$.

What "apply the tokenizer" means here

In §3.2, "apply the tokenizer" doesn't mean the normal tokenization process (string → tokens). Instead, it means:

1. Take your sample corpus $D_i$ and start with it split into bytes
2. Apply the merge rules $m^{(1)}, ..., m^{(t-1)}$ sequentially to this data
3. After each merge, count how many times each possible token pair appears

The notation $c_{i,p}^{(t)}$ represents:

• The count of token pair $p$ in corpus $D_i$
• After applying the first $t-1$ merges

Example

Say you have the text "the cat" and the first merge is (t, h) → th:

• Before any merges: pairs are (t,h), (h,e), (e,_), (_,c), (c,a), (a,t)
• After applying merge 1: text becomes th e _ c a t
• New pairs are: (th,e), (e,_), (_,c), (c,a), (a,t)

The key insight is that you're simulating the BPE training process on your sample data using the tokenizer's merge rules, tracking pair counts at each step. This lets you see which pairs would have been most frequent at each stage, which forms the constraints for the linear program.

Looking at §3.3, the authors are addressing a computational challenge in their BPE tokenizer attack. Here's what's happening:

The Problem

The linear program LP1_T has potentially billions of constraints (O(V³) where V is vocabulary size). Checking all constraints naively would be computationally infeasible.

The Solution Strategy

They use lazy constraint generation - start with a subset of constraints and iteratively add violated ones:

1. Solve a smaller LP with only some constraints
2. Check if the solution violates any constraints from the full LP
3. Add violated constraints and repeat

The Priority Queue Structure

The key insight is tracking how pair frequencies change efficiently:

• Define $s_p^{(t)} = \sum_{i=1}^n \alpha_i c_{i,p}^{(t)}$ (weighted sum of pair counts)
• Need to check if: $v^{(t)} + s_{m^{(t)}}^{(t)} \geq \max_p(s_p^{(t)} - v_p)$

The priority queue maintains pairs ordered by $s_p^{(t)} - v_p$:

1. Initial setup: Build heap with all pairs, priority = $s_p^{(0)} - v_p$
2. Check violations: Pop pairs in descending order until finding one that satisfies the constraint
3. Update efficiently: When moving from time t to t+1, only update pairs affected by merge $m^{(t)}$

The "structure" being exploited is that most pair counts don't change between timesteps - only O(V) pairs are affected by each merge (those overlapping with the merged pair). This allows updating the priority queue in O((k_new + k_old) log V) time rather than rebuilding from scratch.

This approach reduces the constraint checking from O(V²) per timestep to O(k log V) where k is the number of violated constraints - a massive speedup when most constraints are satisfied.