The Foundations of Tokenization: Statistical and Computational Concerns

Thank you very much for your careful evaluation and remarks. We appreciate your comments on the paper’s strengths.

We are also grateful for pointing out that the connection between Theorem 3.1 and the remaining sections of the paper is not clear. The connection is, however, essential in our view. As stated at the beginning of section 4, while consistency is usually assumed, the necessary conditions for consistency formally established in th 3.1 are not usually met. The entire section is therefore a way to show that known problems commonly addressed from a practical or empirical perspective (e.g., OOV terms, special tokens, ambiguity, approximation errors, positivity of the softmax activation function, etc.) are in fact related to formal properties that violate the conditions formally established in th. 3.1. These conditions are precisely those related to injectivity and surjectivity of $\tau$ and $\kappa$. If section 4 discusses injectivity and surjectivity, it is because these are formal consequences of exactness, which is, in turn, an unconditioned form to obtain consistency (Prop. 3.1). So, if the discussed conditions on injectivity and surjectivity are not met, consistency is not guaranteed. As for section 5, the idea is that while consistency is not everything that matters, the use of the formal properties of $\tau$ and $\kappa$ laid down to establish its necessary and sufficient conditions can be further used to analyze and guarantee computational requirements. We hope this clarification can help to see the connection more clearly. If you have any suggestions on how this can become more clear in the paper, we would be happy to include them in a final version.

We agree that this paper does not provide any empirical results concerning the connection between these formal properties and their practical consequences. We also agree that those results would significantly contribute to enhancing the paper’s impact, even if we believe that the purely theoretical character of the paper shouldn’t be a weakness per se in the ICLR area of “Learning theory” where it has been submitted. On this point, we would like to provide some context. This paper constitutes the first step in a broader research program aiming at addressing tokenization problems from a formal principled perspective, including various empirical results on practical issues. Given the strict page limit of ML and NLP conferences, it was impossible for us to include all the aspects and results of this program in one paper. Therefore, we split up the work over multiple papers, distributing their content as consistently as we could. Concretely, we have used the formalism introduced in this paper to design algorithms for converting token-level autoregressive language models to character-level ones, present both exact and approximate algorithms, and benchmark their practical runtime and approximation quality. The framework proposed here (especially, the principles discussed in the last section) was crucial to identify a minimal subset of $\Delta^*$ over which an exact, tractable algorithm could be defined, as well as a consistent notion of approximation, all of which uses injective, surjective, multiplicative, and kernel properties of the maps $\tau,\kappa$. Direct practical applications of this work include: principled solutions to the prompt boundary problem, constrained generation expressed over characters, or consistent linguistic and psycholinguistic measures. Concerning this last point, for instance, we have already performed an analysis of the role of tokenizers in psycholinguistics, providing an exact way of computing the surprisal of regions of interest over characters from a token model to assess psycholinguistic measures of reading times (this work has been recently published). Currently, we are studying the preservation (or lack thereof) by tokenization of structural features induced by formal grammars over character and token models (work in progress). All these applications use the framework proposed here as their theoretical foundation. Accordingly, we thought that the most consistent way to disseminate the different steps in our program was to adopt a “division of labor” between papers, keeping this paper in its pure theoretical form without tying it to any one application, and envisaging its impact as part of the broader research program.

Thank you very much for your evaluation and remarks. We appreciate your comments on the paper’s strengths.

We would like to provide some context concerning the foundational character of this paper and its relation to practical issues. This is indeed a completely theoretical paper, submitted in the principal ICLR area of “Learning theory”, for which we believe the paper is a good match. We think that the purely theoretical character of a paper shouldn’t be a weakness per se in this area. We agree that associating the proposed theoretical framework with practical aspects of tokenization would significantly contribute to enhancing its impact. In this regard, we would like to mention that this paper constitutes the first step in a broader research program aiming at addressing tokenization problems from a formal, principled perspective, including various practical issues. Given the strict page limit of ML and NLP conferences, it was impossible for us to include all the aspects and results of this program in one paper. Therefore, we split up the work over multiple papers, distributing their content as consistently as we could. Concretely, we have used the formalism introduced in this paper to design algorithms for converting token-level autoregressive language models to character-level ones, present both exact and approximate algorithms, and benchmark their practical runtime and approximation quality. The framework proposed here (especially, the principles discussed in the last section) was crucial to identify a minimal subset of $\Delta^*$ over which an exact, tractable algorithm could be defined, as well as a consistent notion of approximation, all of which uses injective, surjective, multiplicative, and kernel properties of the maps $\tau,\kappa$. Direct practical applications of this work include: principled solutions to the prompt boundary problem, constrained generation expressed over characters, or consistent linguistic and psycholinguistic measures. Concerning this last point, for instance, we have already performed an analysis of the role of tokenizers in psycholinguistics, providing an exact way of computing the surprisal of regions of interest over characters from a token model to assess psycholinguistic measures of reading times (this work has been recently published). Currently, we are studying the preservation (or lack thereof) by tokenization of structural features induced by formal grammars over character and token models (work in progress). All these applications use the framework proposed here as their theoretical foundation. Accordingly, we thought that the most consistent way to disseminate the different steps in our program was to adopt a “division of labor” between papers, keeping this paper in its pure theoretical form without tying it to any one application, and envisaging its impact as part of the broader research program.

Thank you very much for your careful evaluation and remarks. We appreciate your comments on the paper’s strengths.

Thanks also for your remark and question concerning the practical consequences of the framework proposed. This is indeed a completely theoretical paper, submitted in the principal area of “Learning theory”. We agree that associating the proposed theoretical framework with practical aspects of tokenization would significantly contribute to enhancing its impact. On this point, we would like to provide some context that might help explain our choices. This paper constitutes the first step in a broader research program aiming at addressing tokenization problems from a formal principled perspective, including various practical issues. Given the strict page limit of ML and NLP conferences, it was impossible for us to include all the aspects and results of this program in one paper. Therefore, we split up the work over multiple papers, distributing their content as consistently as we could. While improving the performance is indeed one possible practical outcome of our framework, we believe there are other practical outcomes. Concretely, we have used the formalism introduced in this paper to design algorithms for converting token-level autoregressive language models to character-level ones, present both exact and approximate algorithms, and benchmark their practical runtime and approximation quality. The framework proposed here (especially, the principles discussed in the last section) was crucial to identify a minimal subset of $\Delta^*$ over which an exact, tractable algorithm could be defined, as well as a consistent notion of approximation, all of which uses injective, surjective, multiplicative, and kernel properties of the maps $\tau,\kappa$. Direct practical applications of this work include, among others, principled solutions to the prompt boundary problem, constrained generation expressed over characters, or consistent linguistic and psycholinguistic measures. Concerning this last point, for instance, we have already performed an analysis of the role of tokenizers in psycholinguistics, providing an exact way of computing the surprisal of regions of interest over characters from a token model to assess psycholinguistic measures of reading times (this work has been recently published). Currently, we are studying the preservation (or lack thereof) by tokenization of structural features induced by formal grammars over character and token models (work in progress). All these applications use the framework proposed here as their theoretical foundation. Accordingly, we thought that the most consistent way to disseminate the different steps in our program was to adopt a “division of labor” between papers, keeping this paper in its pure theoretical form without tying it to any one application, and envisaging its impact as part of the broader research program.

Thank you very much for your careful evaluation and remarks. We appreciate your comments on the paper’s strengths.

This is indeed a completely theoretical paper, and we share the view that this should not constitute a priori a weakness, especially for a submission in the principal area of “Learning theory” as this one. We are also grateful for mentioning the improvements in this sense compared to our previous version. That being said, we agree that associating the proposed theoretical framework with practical aspects of tokenization would significantly contribute to enhancing its impact. On this point, we would like to provide some context that might help explain our choices. This paper constitutes the first step in a broader research program aiming at addressing tokenization problems from a formal principled perspective. Given the strict page limit of ML and NLP conferences, it was impossible for us to include all the aspects and results of this program in one paper. Therefore, we split up the work over multiple papers, distributing their content as consistently as we could. Concretely, we have used the formalism introduced in this paper to design algorithms for converting token-level autoregressive language models to character-level ones, present both exact and approximate algorithms, and benchmark their practical runtime and approximation quality. The framework proposed here (especially, the principles discussed in the last section) was crucial to identify a minimal subset of $\Delta^*$ over which an exact, tractable algorithm could be defined, as well as a consistent notion of approximation, all of which uses injective, surjective, multiplicative, and kernel properties of the maps $\tau,\kappa$. Direct practical applications of this work include: principled solutions to the prompt boundary problem, constrained generation expressed over characters, or consistent linguistic and psycholinguistic measures. Concerning this last point, for instance, we have already performed an analysis of the role of tokenizers in psycholinguistics, providing an exact way of computing the surprisal of regions of interest over characters from a token model to assess psycholinguistic measures of reading times (this work has been recently published). Currently, we are studying the preservation (or lack thereof) by tokenization of structural features induced by formal grammars over character and token models (work in progress). All these applications use the framework proposed here as their theoretical foundation. Accordingly, we thought that the most consistent way to disseminate the different steps in our program was to adopt a “division of labor” between papers, keeping this paper in its pure theoretical form without tying it to any one application, and envisaging its impact as part of the broader research program.

We agree that more credit should be attributed to the work mentioned in the points suggested. We added remarks concerning the relation of tokenizers to linguistic segmentation with reference to relevant work suggested both in lines 54-55 and 400-402. Following your suggestion, we also added a remark on the limited practical benefits of marginalization shown by Chrikova et al, 2023 (line 388-389). We will be happy to include Ex 8.1 in the main text of the final version if space permits, as we agree that it can be very helpful for the reader. Finally, we thank you for pointing out the typos, which we have also corrected in the current version.

We have also remarked that, among the strengths, you mention that “the presentation is excellent”, while the score you gave for the presentation is “3: good”. If you don’t mind us asking, would you agree to update the presentation score (and, if applicable, the final rating) to match the text of your evaluation?