Pith. sign in

REVIEW 2 major objections 5 minor 12 references

Joint Optimization for Greedy Longest-match Tokenization

T0 review · 2 major / 5 minor · reviewed 2026-07-31 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Vocabulary learning for greedy left-to-right longest-match tokenization reduces to a near-integral LP, and BPE is already within 1–2% of the best achievable compression under that decoding rule.

desk verdict A clean, honest formulation for GL2R-optimized tokenization whose LP certificate is real but narrower than the abstract claims; worth refereeing with conditions. read the letter →

arxiv 2607.23362 v1 pith:XZC2EOQO submitted 2026-07-25 cs.CL

Adhiraj Singh , Deepanshu Mody , Ghina Al Shdaifat , Hamza Alshamy , Adam Wiemerslage , Varshini Reddy , Craig W. Schmidt This is my paper · ORCID
classification cs.CL
keywords tokenizationgreedylongest-matchdecodingWordPieceintegerprogrammingLPrelaxationBPEvocabularyoptimizationtextcompression
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that the vocabulary used by WordPiece-style greedy left-to-right (GL2R) longest-match tokenization can be learned by direct optimization rather than by a merge heuristic. It formulates vocabulary learning as an integer program whose greedy-consistency constraints force each word's chosen segmentation to be exactly what GL2R decoding would produce, then solves a linear programming relaxation that is nearly integral. The resulting bound shows BPE is within 1–2% of the best achievable GL2R compression, and the optimized vocabularies close 89.6–99.4% of that small gap, giving up to 0.78% fewer tokens on held-out text. A sympathetic reader would care because this turns 'how much better can a GL2R tokenizer be?' from an open question into a measured one, and offers a reusable optimality certificate for tokenizer design.

What carries the argument

The central machinery is the joint integer program coupling binary vocabulary-selection variables x_t with segmentation-choice variables z_{p,s}, enforced by linking constraints (segmentation requires its tokens) and greedy-consistency constraints over forbidden-prefix sets L_{p,s,g} — the longer vocabulary-prefix tokens that would displace each segment under longest-match decoding. A fallback-driven escalation schedule starts with only whole-pretoken and order-2 segmentations, then adds higher orders only for pretokens the LP routes to a fallback; the LP relaxation plus contribution-based weighted rounding extracts a fixed-size vocabulary.

What would settle it

Allow order-4 segmentations and include the excluded pretoken tail on a moderate corpus, then check whether the achieved compression over BPE exceeds roughly 0.8%: if a materially larger gain appears (or an integer-program solution at small scale beats the LP bound by more than the reported 0.008–0.176% round gap), the restricted search space, not genuine near-optimality, would be the reason BPE looks near-optimal.

Watch

Extended reading notes

Core claim

JOLT treats vocabulary selection and per-pretoken segmentation choice as a single joint integer program. The key coupling is a set of greedy-consistency constraints: for every non-final segment of every candidate segmentation, no longer vocabulary token may exist that is a prefix of the remaining bytes at that position (Eq. 13). These constraints make the optimized objective equal to the token count actually realized at decode time. Solving the LP relaxation with fallback-driven escalation yields solutions within 0.008–0.176% of the LP lower bound on the training scope. The same bound reveals that a BPE-trained vocabulary, when decoded greedily, is already within 1–2% of the best achievable

Load-bearing premise

The paper's optimality certificates hold only within its restricted search space (top-N pretokens, segmentation order capped at M=3, candidates drawn from instantiated segmentations), and assume this space is tight enough that the LP lower bound measures the real headroom available to any GL2R vocabulary.

Editorial extensions

If this is right

  • BPE is near-optimal for GL2R decoding: no GL2R-specific vocabulary trainer can squeeze out more than ~1–2% on typical English data, so reported margins should be interpreted as closing a small gap.
  • The LP-bound certificate is reusable: for any tokenizer decoding rule, a similar relaxation can measure whether the incumbent heuristic is near-optimal before investing in a bespoke optimizer.
  • JOLT vocabularies are drop-in replacements at equal size (32k/64k), producing up to 0.78% fewer tokens with no change to inference, which directly lengthens effective context or lowers decoding cost in LLMs.
  • Gains grow with training scope (N=100k→400k), suggesting that treating more of the pretoken distribution, rather than ranking higher-order segmentations, is the main lever for further compression.
  • The increased share of length-1 tokens under JOLT is a direct consequence of greedy-consistency: short tokens are kept deliberately to suppress competing prefixes, so compression gains can coexist with a more fragmented-looking distribution.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same LP-bound methodology could be applied to shortest-path and split-tree decoding rules to test whether their heuristics (UnigramLM, ToaST) are also within a small constant of optimal; if so, the entire tokenizer-optimization headroom is small, and effort should shift to other design axes.
  • The certificate depends on the regex pretokenizer and on the top-N/order-M restrictions; for languages without whitespace-like boundaries or for longer morphological words, the true headroom over BPE could be larger than 1–2%, so the 'BPE is near-optimal' conclusion should not be extrapolated beyond English-like pretoken boundaries.
  • A testable extension: apply JOLT at higher order cap M=4 or with full tail inclusion on a small corpus to see whether the validation margin exceeds the ~0.78% ceiling; the paper's M=4 spot-check suggests it will not, but the excluded ~4% tail mass remains untested.
  • If compression headroom is genuinely ~1%, the practical value of inference-aligned tokenizers may lie less in shorter sequences and more in the certificate itself, e.g., as a QA check in production tokenizer pipelines.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper introduces JOLT, an integer-programming method for learning subword vocabularies targeted at greedy left-to-right longest-match (GL2R) decoding. The formulation couples vocabulary-selection and segmentation-choice variables with greedy-consistency constraints so that the optimized segmentation matches GL2R decoding under the selected vocabulary. To scale, the authors solve an LP relaxation with iterative fallback-driven escalation of segmentation order (capped at M=3) and round the fractional solution via a contribution-based rule. They report that rounded solutions are within 0.008–0.176% of the LP lower bound, that BPE is within 1–2% of this bound, and that JOLT closes 89.6–99.4% of the BPE-to-LP gap. On held-out validation, JOLT yields up to 0.78% fewer tokens than BPE across four training scopes and two vocabulary sizes.

Significance. If the result holds as stated, the paper offers a valuable methodological contribution: a direct, certificate-style optimization of tokenizers for a specific inference rule, plus a reusable headroom diagnostic. The manuscript is careful in several respects: it documents Gurobi configurations, provides detailed fallback and rounding diagnostics, and includes an honest Limitations section that admits the top-N restriction, the M=3 cap, and the absence of downstream evaluation. However, the unqualified 'best achievable' claims in the abstract and the insufficient evidence that the restricted search space contains the true GL2R optimum mean the central certification claim is currently overstated. The modest but consistent validation gains over BPE are real and useful, and the paper's contribution would be stronger if the scope of the certificate were stated precisely.

major comments (2)
  1. [Abstract; Sec. 4.1; Eq. (4); Limitations] The optimality certificate is valid only for the restricted formulation: top-N pretokens (Sec. 2.1), segmentation order cap M=3 (Sec. 2.5), and fallback cost np for uninstantiated higher-order segmentations (Eq. 4). Because np is an upper bound on the true GL2R token count for a fallback pretoken, the LP objective is not a lower bound on the unrestricted GL2R-optimal token count. The abstract's 'best achievable compression under greedy longest-match decoding' and 'BPE is already within 1–2% of the best achievable' therefore overstate what is shown; the body correctly scopes to 'under our formulation' (Sec. 4.1), and the Limitations acknowledge the tail and M=3 cap. Please qualify all high-level claims accordingly, or add evidence that the restricted space contains the unrestricted optimum.
  2. [Sec. 3.2; Table 3] The 'M=3 is sufficient' verification is a decoding experiment: 'M=4 at |V|=32k/N=100k emits 368.7M tokens ... vs 368.6M at M=3' uses the M=3-optimized vocabulary and only changes the decoder. It does not re-optimize the vocabulary with M=4, so it cannot rule out that an M=4-trained vocabulary yields better compression. Table 3 shows final-round weighted fallback mass up to 0.98% (N=200k/32k) and rising fallback counts in the repricing round, indicating unresolved mass. The claim that higher-order segmentations are unnecessary is thus unsupported and is load-bearing for the 1–2% headroom and gap-closed statements.
minor comments (5)
  1. [Abstract; Table 4] The gap-closed figures for the round-2-only scopes (75.2–86.5%) are lower than the full-pipeline range quoted in the abstract. State explicitly that the 89.6–99.4% figure applies only to the N=100k/200k full-pipeline runs.
  2. [Sec. 2.5; Sec. 2.6] Several hyperparameters are set without sensitivity analysis: the fallback-active threshold θ=0.01, the whole-only shortcut N_top=8000, the initial κ_p=2, and the rounding tolerance ε=10^-6. A short sensitivity discussion, even for a single configuration, would increase confidence in the robustness of the reported margins.
  3. [Sec. 2.4] The forbidden-prefix set L_{p,s,g} is defined over the global candidate set T, which changes as segmentations are escalated. This is correct, but the dependence of the greedy-consistency constraints on the current round's T should be stated more prominently to avoid confusion.
  4. [Table 1] The Rényi efficiency values are reported but never discussed in the text. Either add a sentence interpreting them or remove them from the table.
  5. [Sec. 3.1] Validation is scored on the full Pval while JOLT trains only on top-N pretokens. The paper notes this can disadvantage JOLT; reporting tail-specific breakdowns (e.g., metrics restricted to pretokens within the top-N vs. outside it) would make the comparison more informative.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: JOLT's LP-bound and gap claims are measured empirical results scoped to its formulation; self-citations are provenance, not load-bearing reductions.

full rationale

The paper's derivation chain is self-contained. The IP objective (Eq. 7) is an independently defined corpus-weighted token count over vocabulary-selection and segmentation-choice variables; the greedy-consistency constraints (Eq. 13) are explicit first-order conditions for GL2R realizability, not a restatement of the outcome being claimed. The LP lower bound is obtained by solving the relaxation of that IP; it is not fitted to BPE or to validation counts, so the 'BPE within 1-2%' and 'gap-closed' numbers are empirical comparisons between an external heuristic and a computed relaxation optimum. The rounding procedure is inherited from ToaST, but it is fully reproduced in Appendix B (Algorithm 1, Eq. 16), and the round-gap figures are obtained by actual GL2R decoding of the rounded vocabulary, not set equal to the LP bound by construction. The only significant caveats—optimization over top-N pretokens only, segmentation order capped at M=3, and fallback priced at byte length in the final repricing—are explicitly flagged in the Limitations and Section 3.3; they restrict the external validity of the abstract's 'best achievable' wording, but they do not make any equation self-referential or reduce a prediction to a fitted input. No uniqueness theorem from the authors' prior work is invoked as a proof, and the self-citations to ToaST/ConvexTok supply method provenance rather than load-bearing evidence. Thus no circular step is identifiable; the appropriate finding is no significant circularity.

Assumptions & free parameters 6 free parameters · 7 assumptions · 1 invented entities

The paper's certificates rest on a restricted search space: top-N pretokens (N ≤ 400k), segmentations up to order M=3, and a candidate token set derived only from instantiated segmentations. The main free parameters (θ=0.01, M=3, N_top=8000, regex caps) shape that space and, with it, the reported gap-closed and round-gap numbers. The fallback variable is the only new construct, and it is an optimization device with internal validation only. No physical entities or unexplained mechanisms are introduced.

free parameters (6)
  • Fallback-active threshold θ = 0.01
    Escalation trigger: pretokens with z*_p,F ≥ θ have their segmentation family enriched (Algorithm 1, Section 2.5). Hand-chosen; affects which higher-order segmentations enter the LP and therefore the certificates.
  • Max segmentation order M = 3
    Cap on instantiated segmentation order; higher orders priced conservatively. Verified sufficient only at |V|=32k/N=100k (M=4 changes validation count by ≈0.05%). This choice defines the search space inside which all optimality claims hold.
  • Top-8000 whole-only shortcut N_top = 8000
    Highest-count pretokens start at κ_p=1 (whole token + fallback only) to shrink the first LP. Claimed to have 'little empirical impact' without a full ablation.
  • Initial κ_p = 2 (1 for top-8000)
    Starting segmentation-order bound per pretoken; defines the initial candidate set.
  • Rounding tolerance ε = 1e-6
    Near-integral acceptance threshold in contribution-based rounding (Appendix B); computational constant.
  • GPT4O_REGEX_16 length caps = 32-char word spans; 16-char runs
    Bounded pretokenizer caps (Appendix C) define the pretoken boundaries every optimality claim is relative to; a domain modeling choice.
assumptions (7)
  • domain assumption Tokens cannot cross pretoken boundaries defined by GPT4O_REGEX_16
    Stated in Section 3.1 and Limitations; GL2R decoding and all certificates are relative to these boundaries.
  • domain assumption GL2R longest-match decoding is the deployment inference rule
    Central premise of the paper; motivated by WordPiece and Uzan et al. 2024 (Section 1).
  • domain assumption Byte-completeness: all 256 single-byte tokens are always in the vocabulary
    Eq. (8); guarantees GL2R never fails with unknown tokens (Section 2.4).
  • ad hoc to paper A compression-optimal vocabulary needs only low-order segmentations (up to M=3)
    Sections 2.1/2.5: the candidate set T is built only from instantiated segmentations (Eq. 3), so tokens appearing only in higher-order splits can never enter the vocabulary. Verified at one configuration only; all certificates live inside this restricted space.
  • ad hoc to paper Fallback cost schedule: κ_p+1 in intermediate rounds, n_p in final
    Eq. (4): the intermediate price makes any instantiated segmentation strictly cheaper than F; the final n_p charge is a conservative byte-level upper bound used to define the LP certificate.
  • domain assumption LP relaxation is empirically near-integral at scale
    Section 2.6: the rounding procedure carries no worst-case guarantee; Limitations state certificates are empirical LP-gap measurements, not approximation bounds.
  • domain assumption MiniPile single 75/25 split is representative for held-out evaluation
    Section 3.1; acknowledged in Limitations; no multi-split or cross-lingual check.
invented entities (1)
  • Fallback segmentation variable F with stage-dependent cost
    purpose: Model-size control: lets the solver defer a pretoken instead of committing to an instantiated segmentation, signaling which pretokens need higher-order segmentations (Section 2.5).
    An internal optimization device, not a physical postulate; its adequacy is checked only by internal diagnostics (Table 3: fallback mass <1.6% and dropping) and the M=4 spot-check, not by any external handle.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Joint Optimization for Greedy Longest-match Tokenization." pith.science (2026). https://pith.science/paper/XZC2EOQO

@misc{pith2026260723362,
  author       = {Pith},
  title        = {Pith review of: Joint Optimization for Greedy Longest-match Tokenization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XZC2EOQO}},
  note         = {Machine review of arXiv:2607.23362}
}
read the original abstract

Recent work has shown that subword vocabularies can be trained to optimize compression for a specific inference rule rather than relying on greedy heuristics such as Byte Pair Encoding (BPE). We extend this approach to greedy left-to-right longest-match decoding, the fast and widely used inference rule underlying WordPiece. We introduce Joint Optimization for Greedy Longest-Match Tokenization (JOLT), which formulates vocabulary learning as an integer program over vocabulary-selection and segmentation-choice variables. Greedy-consistency constraints ensure that each optimized segmentation exactly matches the segmentation produced by longest-match decoding under the selected vocabulary, aligning the training objective with deployment-time tokenization. To scale the optimization, we solve a linear programming relaxation and selectively introduce higher-order segmentations only for unresolved pretokens. The resulting relaxation is nearly integral: rounded solutions fall within 0.008 - 0.176 % of the LP lower bound on the training scope. The bound also shows that BPE is already within 1 - 2 % of the best achievable compression under greedy longest-match decoding, while JOLT closes 89.6 - 99.4 % of the remaining gap. On held-out validation data across four training scopes and vocabulary sizes of 32,000 and 64,000, JOLT produces up to 0.78 % fewer tokens than BPE, with improvements generally increasing as the training scope grows. These results demonstrate that inference-aligned vocabulary optimization can recover most of the limited compression headroom left by BPE while providing a certificate of near-optimality.

Figures

Figures reproduced from arXiv: 2607.23362 by the authors.

Figure 1
Figure 1. Instantiated segmentations Sp for pretoken p = table (np=5). (a) Round 1 (κp=2): whole pretoken, four order-2 segmentations, and fallback F. (b) Round 2: six order-3 segmentations added when F was selected in round 1 (Section 2.5). s = ta | ble for pretoken p = table. The order of s is the number of pieces (tokens) in the partition. An order-r segmentation is determined by choosing r − 1 internal split positions amo… view at source ↗
Figure 2
Figure 2. Linking and greedy-consistency rows for p = table. (a) s = ta | ble. (b) s = ta | b | le. Blue: required token; red: forbidden longer prefix at that segment start. Linking constraint. For non-fallback s, recall from Section 2.1 that Ep,s is the set of tokens t used in segmentation s of pretoken p. A segmentation can be activated only if all of its tokens are selected in the vocabulary: zp,s ≤ xt ∀p ∈ P, ∀s ∈ Sp \ {F… view at source ↗
Figure 3
Figure 3. LP bound, rounded greedy-L2R objective, and BPE-greedy token count on training [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Fallback diagnostics per escalation round for all four configurations ( [PITH_FULL_IMAGE:figures/full_fig_p016_4.png]
Figure 5
Figure 5. Figure 5: Log-log token rank-frequency on the greedy-L2R-decoded validation set [PITH_FULL_IMAGE:figures/full_fig_p016_5.png]
Figure 6
Figure 6. Figure 6: Greedy-L2R token-length distribution on Pval (count-weighted) for BPE-greedy and JOLT at N=100k and 200k, at both vocabulary budgets. optimization scope from 100k to 200k pretokens shifts mass slightly away from length-2 tokens (a relative drop of ∼2% at |V|=32k and ∼7…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 4 linked inside Pith

  1. [10]

    Omri Uzan, Craig W

    URLhttps://arxiv.org/abs/2605.22821. Omri Uzan, Craig W. Schmidt, Chris Tanner, and Yuval Pinter. Greed is all you need: An evaluation of tokenizer inference methods. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.),Proceedings of the 62nd Annual Meeting of the Association for Computa- tional Linguistics (Volume 2: Short Papers), pp. 813–822, Bangk...

    arXiv

  2. [1994]

    Investigating the effectiveness of BPE: The power of shorter sequences

    Matthias Gallé. Investigating the effectiveness of BPE: The power of shorter sequences. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 1375–1381, Hong Kong, China,

    2019

  3. [2012]

    Rico Sennrich, Barry Haddow, and Alexandra Birch

    doi: 10.1109/ICASSP .2012.6289079. Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. In Katrin Erk and Noah A. Smith (eds.),Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1715–1725, Berlin, Germany, August

    arXiv 2012

  4. [2016]

    doi: 10.18653/v1/P16-1162

    Association for Computational Linguistics. doi: 10.18653/v1/P16-1162. URLhttps://aclanthology.org/P16-1162/. Jan Tempus, Philip Whittington, Craig W. Schmidt, Dennis Komm, and Tiago Pimentel. Tokenisation via convex relaxations,

    doi:10.18653/v1/p16-1162

  5. [2018]

    doi: 10.18653/v1/P18-1007

    Association for Computational Linguistics. doi: 10.18653/v1/P18-1007. URLhttps://aclanthology.org/P18-1007/. Phillip Rust, Jonas Pfeiffer, Ivan Vuli´ c, Sebastian Ruder, and Iryna Gurevych. How good is your tokenizer? on the monolingual performance of multilingual language models. In Proceedings of the 59th Annual Meeting of the Association for Computatio...

    doi:10.18653/v1/p18-1007

  6. [2019]

    Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, et al

    Association for Computational Linguistics. Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, et al. The Pile: An 800GB dataset of diverse text for language modeling.arXiv preprint arXiv:2101.00027,

    arXiv

  7. [2020]

    Unpacking tokenization: Evaluating text compression and its correlation with model performance

    Omer Goldman, Avi Caciularu, Matan Eyal, Kris Cao, Idan Szpektor, and Reut Tsarfaty. Unpacking tokenization: Evaluating text compression and its correlation with model performance. InFindings of the Association for Computational Linguistics: ACL 2024, pp. 2274–2286, Bangkok, Thailand,

    2024

  8. [2021]

    Association for Computational Linguistics. Craig W. Schmidt, Varshini Reddy, Haoran Zhang, Alec Alameddine, Omri Uzan, Yuval Pinter, and Chris Tanner. Tokenization is more than compression. InProceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pp. 678–702, Miami, Florida, USA,

    2024

Show all 12 references
  1. [2023]

    Violeta Kastreva, Philip Whittington, Dennis Komm, and Tiago Pimentel

    URL https://arxiv.org/abs/2304.08442. Violeta Kastreva, Philip Whittington, Dennis Komm, and Tiago Pimentel. Tokenisation over bounded alphabets is hard. InThe Fourteenth International Conference on Learning Representations,

    arXiv

  2. [2024]

    doi: 10.18653/v1/2024.acl-short.73

    Association for Computational Linguistics. doi: 10.18653/v1/2024.acl-short.73. URL https://aclanthology.org/2024.acl-short.73/. Philip Whittington, Gregor Bachmann, and Tiago Pimentel. Tokenisation is NP-complete. In Wanxiang Che, Joyce Nabende, Ekaterina Shutova, and Mohammad...

    2024 doi

  3. [2025]

    ISBN 979-8-89176-251-0

    Association for Computational Linguistics. ISBN 979-8-89176-251-0. doi: 10.18653/v1/2025.acl-long.1365. URLhttps://aclanthology.org/2025.acl-long.1365/. Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V . Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, ...

    2025 doi

  4. [2026]

    org/abs/2605.22705

    URLhttps://arxiv. org/abs/2605.22705. Mike Schuster and Kaisuke Nakajima. Japanese and korean voice search. In2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5149–5152,

    arXiv

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.