- Rating
- 1
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper studies tokenization from the perspective of graphs and linear programming. The authors process input strings as a graph, formulate compression-optimal vocabulary selection as an integer program, and relax it into a linear program followed by three rounding schemes (Det, Bias, Int) and PathPiece segmentation to obtain a discrete tokenizer.
Critical strengths
I think the idea is interesting. Combining graphs, a integer program, and a linear program offers a new perspective on tokenizer construction, where the linear program yields a lower bound on the optimal compression.
Critical weaknesses
-
The presentation is not very good and is hard to follow. The framework is complicated, translating tokenization from strings to coloured graphs, then to incidence-matrix network flows in an IP and finally to an LP relaxation with rounding. A clear high-level overview and pipeline diagram of the algorithm are necessary. In addition, critical implementation steps that make the LP solvable on a 700 MB corpus are omitted.
-
I feel this is a critical flaw of the framework, and the authors overclaim their contribution. The method relies entirely on PathPiece, an existing string-level shortest-path algorithm. Furthermore, because the corpus is pretokenised into regex chunks and priced edges in Eq. (2c) never cross string boundaries, the shortest-path problem itself decomposes strictly at the local string/pretoken level rather than globally across the corpus. This contradicts the "globally optimal" claim that the authors make as their major contribution. (Please correct me if I misunderstood this as I interpreted this from footnote #4). Meanwhile, claiming BPE makes "locally optimal" decisions is technically wrong. BPE actually collects statistics and counts token-pair frequencies globally across the entire corpus. It is greedy in search order, not "local" in data scope. I think this is the reason that why BPE is already within < 1% of the LP lower bound at standard vocabulary sizes.
Questions for authors
Please refer to Weaknesses
3 comments
W2. (Part 1.) I feel this is a critical flaw of the framework, and the authors overclaim their contribution. The method relies entirely on PathPiece, an existing string-level shortest-path algorithm. Furthermore, because the corpus is pretokenised into regex chunks and priced edges in Eq. (2c) never cross string boundaries, the shortest-path problem itself decomposes strictly at the local string/pretoken level rather than globally across the corpus. This contradicts the "globally optimal" claim that the authors make as their major contribution. (Please correct me if I misunderstood this as I interpreted this from footnote #4).
We believe there may indeed be a misunderstanding. Tokenisation is unfortunately an ambiguous term as within the same field it refers simultaneously to two things:
- Tokeniser training. The process of, given some dataset, selecting a set of byte-strings to compose the model’s vocabulary.
- Tokeniser inference. The process of, given a vocabulary, segmenting a dataset.
The key difference is that the first step (training) is NP-hard even for compression, while the second step (inference) is simply a shortest path problem. Notably, PathPiece is also an ambiguous term, as there are two PathPiece methods:
- PathPiece Training. A method similar to UnigramLM for tokeniser training. This method starts with a large seed vocabulary and greedily trims it by iteratively deleting the tokens which will hurt compression the least.
- PathPiece Inference. A method for tokeniser inference, and the default use of the term “PathPiece.” This is a shortest path method which, given a vocabulary, segments a sentence/dataset optimally for compression.
In our paper, PathPiece always refers to the latter (inference) method. Notably, as the reviewer notes, PathPiece Inference solves the tokenisation inference step directly and optimally. PathPiece Training, however, is a greedy (local-in-the-search-procedure) approach for finding a tokeniser. Our paper is the first to reformulate the tokeniser training step as a graph problem, as well as the first to solve it using linear programming (globally-in-the-search-procedure). See the answer to reviewer iVVv for a longer comparison to prior methods.
After using ConvexTok to select a vocabulary, we indeed use PathPiece Inference to apply it optimally to new strings; this is what footnote 4 refers to.
W2. (Part 2.) Meanwhile, claiming BPE makes "locally optimal" decisions is technically wrong. BPE actually collects statistics and counts token-pair frequencies globally across the entire corpus. It is greedy in search order, not "local" in data scope.
We again apologise for the confusion. Indeed, our intention with using the words “globally” and “locally” optimal was with respect to the search order, not the data scope. We agree that BPE is global in data scope. However, in terms of search order, it only scores tokens locally (by evaluating how much the given token improves the objective locally). Our linear programming approach, however, scores tokens globally (by evaluating how much this token improves the objective, jointly considering all other tokens and whether or not they are chosen). ConvexTok is thus global in both data and search scope.
W2. (Part 3.) I think this is the reason that why BPE is already within < 1% of the LP lower bound at standard vocabulary sizes.
Given the considerations above, we argue that the reason why BPE is so close to optimal actually remains a bit of a mystery. In fact, Kozma and Voderholzer (2024) show that there are datasets where it achieves arbitrarily bad compression.
References
Kozma and Voderholzer, Theoretical Analysis of Byte-Pair Encoding in arXiv 2024
Thank you for your feedback
Thank you for your clarification. Unfortunately, addressing these concerns requires substantial restructuring of the paper. Therefore, I have to keep my scores.
We would like to start by thanking the reviewer for their feedback. We would like to respectfully push back on the reviewer’s score, though. The reviewer points out two weaknesses with our paper:
On the other hand, the reviewer highlights as strengths that:
Given these strengths, and that one of the weaknesses pointed out (overclaim) is a misunderstanding (which we will make sure to clarify), and the other (hard to follow) is an inherent property of the novelty of our approach, we believe that our paper is worth acceptance at ICLR. We thus respectfully ask the reviewer to reconsider their score.
We respond to the reviewer’s points in detail below.
See above. We appreciate the reviewer’s suggestion to add a high-level overview diagram to our paper, though, and we will do so.
We respectfully request a more concrete suggestion here so we can clarify this point, as it is not clear to us which steps are missing. Our pipeline is: