Joint Optimization for Greedy Longest-match Tokenization

• URL: http://arxiv.org/abs/2607.23362v1
• Date: Sat, 25 Jul 2026 21:01:14 GMT
• Title: Joint Optimization for Greedy Longest-match Tokenization
• Abstract summary: Recent work has shown that subword vocabularies can be trained to optimize compression for a specific inference rule.<n>We extend this approach to greedy left-to-right longest-match decoding.<n>We introduce Joint Optimization for Greedy Longest-Match Tokenization.
• Score: 4.106446329199573
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Tokenisation via Convex Relaxations [14.99534435778172]
  Tokenisation is an integral part of the current NLP pipeline.<n>We formulate tokeniser construction as a linear program and solve it using convex optimisation tools.<n>We find ConvexTok consistently improves intrinsic tokenisation metrics and the bits-per-byte (BpB) achieved by language models.
  arXiv  Detail & Related papers  (2026-05-21T17:59:56Z)
• Tokenization with Split Trees [14.246587182553952]
  Tokenization with Split Trees (ToaST) is a subword tokenization method that directly optimize compression.<n>ToaST reduces token counts by more than 11% compared to BPE, WordPiece, and UnigramLM at vocabulary sizes of 40,960 and above.<n>In experiments training 1.5B parameter language models, ToaST achieves the highest score, outperforming baselines by 2.6%--7.6% with significance for two of three, and scoring best on 13 of 22 individual tasks.
  arXiv  Detail & Related papers  (2026-05-21T16:46:23Z)
• AdaptBPE: From General Purpose to Specialized Tokenizers [18.70903226766322]
  We propose a post-training adaptation strategy that selectively replaces low-utility tokens with more relevant ones based on their frequency in an adaptation corpus.<n>Our algorithm identifies the token inventory that most effectively encodes the adaptation corpus for a given target vocabulary size.<n>This method serves as a lightweight adaptation mechanism, akin to a vocabulary fine-tuning process, enabling optimized tokenization for specific domains or tasks.
  arXiv  Detail & Related papers  (2026-01-29T12:59:40Z)
• Training Long-Context LLMs Efficiently via Chunk-wise Optimization [60.05884946552877]
  We present textitSequential Chunk-wise Optimization (SeCO), a memory-efficient training paradigm that partitions lengthy inputs into manageable chunks.<n>We also introduce textitSparse Chunk-wise Optimization (SpaCO), which reduces computational overhead by selectively propagating gradients to specific chunks.<n>SpaCO decouples the computational cost of backpropagation from the context length, enabling training time to gradually converge to inference time as sequences become longer.
  arXiv  Detail & Related papers  (2025-05-22T14:11:34Z)
• A Partition Cover Approach to Tokenization [24.595558878756787]
  Tokenization is a process of encoding strings into tokens of a fixed vocabulary size.<n>Byte-Pair corpora (BPE) formulates the tokenization problem as a compression problem and tackles it by performing sequences of merges.<n>We show that GreedTok outperforms BPE and Unigram on compression and achieves a covering score comparable to GreedWMC.
  arXiv  Detail & Related papers  (2025-01-08T17:07:07Z)
• Batching BPE Tokenization Merges [55.2480439325792]
  BatchBPE is an open-source pure Python implementation of the Byte Pair algorithm. It is used to train a high quality tokenizer on a basic laptop.
  arXiv  Detail & Related papers  (2024-08-05T09:37:21Z)
• Training LLMs over Neurally Compressed Text [55.11828645767342]
  This paper explores the idea of training large language models (LLMs) over highly compressed text.<n>We propose Equal-Info Windows, a novel compression technique whereby text is segmented into blocks that each compress to the same bit length.<n>We demonstrate effective learning over neurally compressed text that improves with scale, and outperforms byte-level baselines by a wide margin on perplexity and inference speed benchmarks.
  arXiv  Detail & Related papers  (2024-04-04T17:48:28Z)
• PoSE: Efficient Context Window Extension of LLMs via Positional Skip-wise Training [91.99700930388998]
  We propose Positional Skip-wisE training that simulates long inputs using a fixed context window. PoSE greatly reduces memory and time overhead compared with Full-length fine-tuning. We have successfully extended the LLaMA model to 128k tokens using a 2k training context window.
  arXiv  Detail & Related papers  (2023-09-19T08:03:38Z)
• SelfSeg: A Self-supervised Sub-word Segmentation Method for Neural Machine Translation [51.881877192924414]
  Sub-word segmentation is an essential pre-processing step for Neural Machine Translation (NMT) This paper introduces SelfSeg, a self-supervised neural sub-word segmentation method. SelfSeg is much faster to train/decode and requires only monolingual dictionaries instead of parallel corpora.
  arXiv  Detail & Related papers  (2023-07-31T04:38:47Z)
• TagCLIP: Improving Discrimination Ability of Open-Vocabulary Semantic Segmentation [53.974228542090046]
  Contrastive Language-Image Pre-training (CLIP) has recently shown great promise in pixel-level zero-shot learning tasks. Existing approaches utilizing CLIP's text and patch embeddings to generate semantic masks often misidentify input pixels from unseen classes. We propose TagCLIP (Trusty-aware guided CLIP) to address this issue.
  arXiv  Detail & Related papers  (2023-04-15T12:52:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.