{"id":"1a56457f-ec8b-45e6-b791-57380f1e8db8","arxiv_id":"2412.03160","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper shows that, under the assumption that detokenization is compositional, extended tokenization is an inverse homomorphism and thus preserves context-free and regular language structure, while the structure of the tokenizer's unique proper output remains open.","lead":"This paper argues that tokenization used in large language models can be viewed as the inverse of a homomorphism, so the context-free structure of the original text is preserved in the token stream. It formalizes the difference between the tokenizer's chosen output and all possible tokenizations, leaving the structure of the chosen output as an open problem.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Prop 3.2's homomorphism premise is contradicted by the paper's own LLaMA example, and the Appendix B 'leading-space' fix is stated without proof; the CFL-preservation claim is therefore unproven for common tokenizers.","rationale":"The reader's weakest_assumption is exactly the one I find most load-bearing: the homomorphism property of detokenization is necessary for Corollary 3.0.1 and is contradicted by Appendix B. The paper's attempted patch is the only place where this is addressed, and it is not a proof. I considered whether a different concern (e.g., the gap between extended and proper tokenization) is more fundamental, but Section 6's sufficiency argument handles that correctly: an acceptor of L'_E can separate proper tokenizations of L from those outside L. The proper-tokenization open problem is acknowledged by the authors and does not undermine the extended-language claim. The leading-space issue, by contrast, undermines the proof of Proposition 3.3 itself for LLaMA/T5. A formal rescue is plausible via closure of CFLs under inverse finite-state transductions, but the paper does not supply it. Thus the correct disposition is a conditional acceptance requiring the authors to either prove the fix rigorously or restrict the claim to tokenizers whose detokenization is truly homomorphic (e.g., GPT-2 byte-level BPE).","tokens_in":9241,"tokens_out":14043,"duration_ms":134130,"concrete_test":"One decisive check: implement the Appendix B fix for the LLaMA tokenizer on a tiny CFL, e.g., L = {a^n b^n} over ASCII letters, by enumerating token sequences of length ≤4 over a small token-ID vocabulary and computing L'_E as those decoding into L. Independently construct the claimed intermediate language M = {t | piece-concat(t) ∈ ' '+L} ∪ {t | piece-concat(t) ∈ L}. If L'_E ≠ M for any length-4 sequence, the leading-space patch is insufficient and Prop 3.3 needs a different proof; if equality holds, the concern reduces to a missing proof step rather than a false claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 3.2 asserts that detokenization Fdetok: N*→Σ* is a string homomorphism, which is the sole premise for Corollary 3.0.1 and Proposition 3.3. Appendix B shows this premise is false for LLaMA/T5: Fdetok([22172,3186])='Hello World' while Fdetok([22172])·Fdetok([3186])=' Hello World'. The paper's remedy, 'considering an intermediate CFL, i.e. the language with a leading space', is asserted without proof. To make it work one must show that the real extended token language L'_E = {t | Fdetok(t)∈L} is the preimage of some CFL under a homomorphism up to a regular operation. This requires modeling Fdetok as a composition of piece-wise concatenation with position-dependent post-processing (e.g., strip-leading-space) and invoking closure under inverse finite-state transduction, a theorem the paper neither cites nor proves. As written, the proposed leading-space language does not itself have the required preimage property; the example shows the decoder strips the leading space, so the intermediate CFL needs a separate treatment. Hence Corollary 3.0.1 and Prop 3.3 are unsupported for the very tokenizers used in Fig. 2, and the abstract's 'irrespective of the algorithm used' overreaches.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a formal-language framework for LLM tokenization. It defines tokenization and detokenization maps between strings and token-ID sequences and claims that detokenization is a string homomorphism, so the extended token language L'_E of a context-free (or regular) source language L is again context-free (or regular) by closure under inverse homomorphism. It extends the argument to Unicode by moving to a byte-level alphabet, sketches a PDA recognizing the token language, introduces a distinction between proper and extended tokenization, and concludes that tokenization does not limit the expressiveness of neural models for context-free languages.","tokens_in":9509,"tokens_out":10112,"duration_ms":102971,"significance":"The core idea of viewing tokenization through inverse homomorphisms and closure properties is elegant and potentially useful: if made rigorous, it would give a clean structural characterization of token languages and a concrete testable prediction that L'_E is context-free whenever L is. The paper also deserves credit for explicitly discussing proper tokenization and for honestly leaving the regular-language question in Section 5 open. However, the main theorem currently rests on a false empirical premise, acknowledged in the paper's own Appendix B, and the proposed repair is only sketched. With a corrected proof for leading-space tokenizers and a narrowed scope, the framework could be a valuable contribution; in its present form the central claim is not established.","major_comments":[{"comment":"The central premise of Proposition 3.2 is false for the tokenizers the paper itself discusses. Appendix B shows that for LLaMA/T5, Fdetok([22172,3186]) = 'Hello World' while Fdetok([22172])·Fdetok([3186]) = ' Hello World', so detokenization is not a string homomorphism. Since Corollary 3.0.1 and Proposition 3.3 are derived from this premise, the main preservation theorem is unproven for these common tokenizers. The proposed remedy of an intermediate CFL with a leading space is stated without proof; a correct treatment would need to model the decoder as a composition of a homomorphism with a leading-space-stripping post-processor and then prove that D^{-1}(L) = C^{-1}(L ∪ '␣'·L) is context-free. As written, the paper does not supply that proof, so the Section 6 conclusion about expressiveness is unsupported.","section":"§3.1, Prop. 3.2; Appendix B"},{"comment":"The paper assumes ftok is injective and that fdetok∘ftok is the identity. This fails for leading-space tokenizers: the paper's own Appendix B explains that the leading space of a token such as ' Hello' is lost when that token appears at the beginning of the decoded string. Consequently, distinct strings such as 'Hello' and ' Hello' can receive the same token sequence, contradicting Definition 2.6, and fdetok(ftok(' Hello')) can return 'Hello', contradicting the identity in Section 2.2. The Section 6 sufficiency argument relies on tokenization preserving the identity of strings; if distinct strings collapse to the same token sequence, a model cannot in principle separate strings that happen to share a tokenization.","section":"§2.2, Defs. 2.6–2.7, Prop. 2.1; §6"},{"comment":"The Unicode extension does not repair the leading-space failure. Proposition 4.1 asserts that byte-level tokenization is inverse-homomorphic from token IDs to byte sequences, but the same context-dependent stripping occurs at the byte level whenever the first token begins with the byte 0x20. The abstract's claim that tokenization acts as an inverse homomorphism 'irrespective of the algorithm used' is therefore an overclaim: the theorem is established only for decoders that are genuinely homomorphic, or would need to be re-proved for the repaired leading-space construction. The proof of Lemma 4.1 should also be stated precisely: a finite-length encoding is a homomorphism between free monoids, not merely a 'string replacement operation.'","section":"§4, Prop. 4.1; abstract"},{"comment":"Section 5.2 leaves open whether the proper tokenization language L' is context-free, but Section 6 concludes that the model can always learn the extended tokenization language L'_E. Even granting the repair of Proposition 3.2, this argument needs an explicit statement of the conditions under which the model's input (the proper tokenization) is sufficient to determine membership in L'_E. In particular, the injectivity failure noted above means that the current text does not justify the conclusion that the expressiveness of neural architectures is unaffected by tokenization for the leading-space tokenizers used in the paper's own experiments.","section":"§5.2 and §6"}],"minor_comments":[{"comment":"The caption lists fdetok([15496,2159]) = 'Hello World ' with a trailing space, which is inconsistent with fdetok(15496) = 'Hello' and fdetok(2159) = ' World'; please correct the example or it contradicts the homomorphism claim.","section":"Fig. 1"},{"comment":"The codomain of the homomorphism is written as T* in the first sentence of Definition 2.4 but as N* later in the same definition; the alphabet names should be consistent.","section":"§2.1, Def. 2.4"},{"comment":"There are several typos and grammatical slips, including 'natrually', 'langauge', and the phrase 'another area of research focuses on constraining the outputs' in Section 7; a careful proofread is needed.","section":"Throughout"},{"comment":"The claim that the set of mergeable token sequences is straightforwardly regular is plausible, but it should be argued explicitly rather than asserted, since it is load-bearing for the attempted reduction to regularity.","section":"§5.2"}],"recommendation":"major_revision","confidential_remarks":"The paper's formal-language framing is promising, and the leading-space failure appears repairable by modeling the decoder as a composition of a homomorphism with a leading-space-stripping step and proving the corresponding closure property. I recommend major revision rather than rejection because the fix is feasible within the manuscript's scope. The authors should also narrow the abstract's overbroad 'irrespective of the algorithm used' claim or replace it with a precise statement about the tokenizer classes covered by the proof."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: this paper gives a clean way to think about tokenization as an inverse homomorphism and then applies a textbook closure theorem to argue CFLs survive tokenization. That argument is valid for tokenizers whose detokenization is a real homomorphism, GPT-2-style byte BPE for instance. But the abstract claims it works \"irrespective of the algorithm used,\" and that is not supported. The paper's own Appendix B shows LLaMA/T5 violate the homomorphism condition because leading-space tokens are stripped at the start of a string. The proposed fix, \"consider an intermediate CFL with a leading space,\" is a sketch, not a proof. To make it rigorous you need to model the strip operation as a finite-state transduction and invoke closure under inverse finite-state transduction, or something equivalent. The paper does neither.\n\nWhat is genuinely useful: the notation separating extended, proper, and improper tokenization languages; the observation that the right homomorphism runs from token IDs back to characters (or bytes), not the other way; and the byte-level treatment of Unicode, which is a legitimate extension once you move to the byte alphabet. The proper-tokenization section is honest, identifying the open problem of whether the proper tokenization space is regular and not overclaiming. That is a real service to people working on grammar-constrained decoding.\n\nThe main soft spots, in proportion: (1) Proposition 3.2 is false as stated for common tokenizers, so Corollary 3.0.1 and Proposition 3.3 are unproven in the general case. This is the load-bearing gap. (2) The \"all major tokenization schemes\" line in Section 3.1 is contradicted by Appendix B. (3) The Unicode section inherits the same problem if the tokenizer's byte-level detokenization also strips leading spaces. (4) Section 6's expressiveness claim is conditional on the model learning the extended token language, which is an idealized target; that is okay for an expressiveness statement, but the paper should say so more carefully.\n\nThe citation pattern looks fine. The argument is a reformulation of known closure results, so the novelty is modest, but the paper is a useful conceptual cleanup and it is honest about its gaps. If the authors supply a real proof for the leading-space case, which should be straightforward with standard transducer closure, and soften the abstract, it is a solid workshop-level or short-conference paper.\n\nRecommendation: send it to peer review. A serious referee can verify the leading-space patch and check whether the expressiveness claim needs more qualification. Not a desk reject.","headline":"A clean formalization of tokenization as inverse homomorphism, but the headline claim overreaches: the homomorphism premise fails for leading-space tokenizers and the paper's own patch is unproved.","tokens_in":10069,"tokens_out":7016,"would_cite":true,"duration_ms":68392,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q45","68Q42"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper argues that tokenization acts as an inverse string homomorphism, so the tokenized version of any context-free language is still context-free.","keywords":["tokenization","inverse homomorphism","context-free language","byte-level encoding","byte pair encoding (BPE)","proper tokenization","large language models","formal language theory"],"falsifier":"Run the Appendix B leading-space counterexample through a context-free language: let L be all strings whose detokenized form has balanced parentheses, use LLaMA's tokenizer, and check whether the extended tokenization language L'_E, the set of all token sequences that detokenize to balanced parentheses, is accepted by any pushdown automaton; a pumping-lemma counterexample would collapse Proposition 3.3.","tokens_in":9019,"feed_emoji":"🧩","tokens_out":5405,"duration_ms":44617,"temperature":0.7,"pith_summary":"The paper tries to establish that tokenization, even though it does not behave homomorphically itself, is the inverse of a homomorphism: detokenization maps each token ID to a fixed string and concatenates, so concatenating detokenized pieces equals detokenizing the concatenation. That framing turns the question of what happens to a formal language after tokenization into a known closure property: the set of all possible token sequences for strings of a context-free (or regular) language is again context-free (or regular). The paper extends this to byte-level tokenization, covering Unicode, and argues that because recognizing this extended token language is sufficient to recognize the original language, tokenization does not limit the expressiveness of neural sequence models for context-free language recognition. It also introduces proper tokenization, the unique tokenization a real tokenizer returns, and shows it is a subset of the extended language, but leaves open whether that subset is context-free.","feed_headline":"Tokenization keeps context-free languages context-free","feed_subtitle":"Detokenization as a string homomorphism means tokenization cannot block grammar recognition by LLMs.","key_machinery":"The load-bearing mechanism is the homomorphism pair: detokenization F_detok satisfies F_detok(uv) = F_detok(u)F_detok(v), making tokenization an inverse homomorphism. This lets the paper invoke the textbook construction of a pushdown automaton for the inverse homomorphic image of a context-free language: a new PDA reads token IDs, detokenizes each ID into a character string, feeds those characters through the original PDA, and buffers characters between steps. The byte-level extension treats character encodings as finite-length string replacement operations, which preserve the language class.","core_discovery":"The central claim is that for any context-free or regular source language L over characters, the extended tokenization language L'_E, the set of all token-ID sequences that can be produced from strings in L, is likewise context-free or regular. The proof route is that detokenization is a string homomorphism, tokenization is therefore an inverse homomorphism, and context-free and regular languages are closed under inverse homomorphism. For Unicode, the same argument is repeated at the byte level, using the fact that finite-length character encodings such as UTF-8 and UTF-16 are string replacements that preserve context-freeness. The paper claims the proper tokenization language is contained in the extended language, but its context-freeness is left open.","pith_inferences":["The paper's sufficiency argument in Section 6 only requires the model to learn the extended token language, which is a superset of what the tokenizer actually outputs; in practice models observe only proper tokenizations, so the argument may not transfer directly to training data.","The leading-space failure identified in Appendix B suggests that for tokenizers with context-dependent detokenization, the central theorem does not apply as stated; testing whether the proposed leading-space repair really yields a context-free language would decide the practical reach.","A testable extension is to construct the proposed PDA for a small context-free language, such as balanced parentheses, with a leading-space byte-level BPE tokenizer and empirically check whether the emitted token sequences follow a context-free pattern.","If the proper tokenization language turns out not to be context-free in general, then real language models may face a harder recognition problem than the extended-language result suggests."],"forward_implications":["If the extended tokenization language of a context-free language is context-free, then any model that can recognize that token language can classify the original character strings, so tokenization alone never blocks a neural network from learning a context-free grammar.","The same preservation holds for regular languages.","Byte-level tokenizers that represent Unicode characters as multiple bytes still preserve language structure, because UTF-8 and UTF-16 encoding are finite-length string replacements.","The result covers BPE, WordPiece, and SentencePiece detokenizers as long as their detokenization is homomorphic; the proper tokenization question remains open."],"supporting_citations":[{"why":"Supplies the closure theorem for inverse homomorphism and the PDA construction that the paper's main argument builds on.","marker":"Hopcroft et al. 2006"},{"why":"Defines byte pair encoding, the running example of a tokenization scheme the paper claims has homomorphic detokenization.","marker":"Sennrich et al. 2016"},{"why":"Gives the byte-level BPE tokenizer used for the GPT models and for the Unicode examples in the paper.","marker":"Radford et al. 2019"},{"why":"Introduces byte-level subword tokenization, which the paper relies on to extend the homomorphism argument to Unicode.","marker":"Wang et al. 2019"},{"why":"Introduces the distinction between proper and general tokenization, which the paper adopts for its proper tokenization analysis.","marker":"Kudo 2018"},{"why":"Describes SentencePiece, one of the tokenizers the paper lists as having homomorphic detokenization.","marker":"Kudo and Richardson 2018"}],"fun_headline_variants":["Tokenization is inverse homomorphism, so context-free stays context-free","Detokenization homomorphism proves tokenization preserves context-free","Inverse homomorphism: why tokenization can't block grammar recognition","Byte BPE tokenization: inverse homomorphism preserves context-free","Tokenization preserves context-free languages via inverse homomorphism"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Detokenization must be a true string homomorphism: combining the detokenized strings must equal detokenizing the combined token sequence, with no context-dependent post-processing; leading-space tokenizers like LLaMA violate this and the paper's proposed repair, adding a leading space as an intermediate language, is stated without proof.","fun_headline_variants_meta":{"raw":{"variants":["Tokenization is inverse homomorphism, so context-free stays context-free","Detokenization homomorphism proves tokenization preserves context-free","Inverse homomorphism: why tokenization can't block grammar recognition","Byte BPE tokenization: inverse homomorphism preserves context-free","Tokenization preserves context-free languages via inverse homomorphism"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000545,"raw_usage":{"total_tokens":2541,"prompt_tokens":811,"completion_tokens":1730,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":427,"completion_tokens_details":{"reasoning_tokens":1645}},"tokens_in":427,"tokens_out":1730,"duration_ms":12422,"temperature":1.0,"reasoning_tokens":1645,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T22:43:22.013446+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the Appendix B leading-space counterexample through a context-free language: let L be all strings whose detokenized form has balanced parentheses, use LLaMA's tokenizer, and check whether the extended tokenization language L'_E, the set of all token sequences that detokenize to balanced parentheses, is accepted by any pushdown automaton; a pumping-lemma counterexample would collapse Proposition 3.3.","supporting_citations":[],"review_version":1}