Source-linked AI summary
A Pilot Study of Autocompleting Tokenizers
Samuel Wexler, Mark Hopkins
TL;DR
Byte-level tokenization avoids language-specific subwords but creates long, costly sequences. This paper removes predictable bytes with a lightweight autoregressive model before Transformer processing, preserving translation quality while shortening inputs substantially.
Problem
Byte-level tokenization offers language-independent representations but produces longer sequences that typically increase runtime, memory use, and reduce model quality.
Method
A lightweight autoregressive byte model identifies predictable bytes and removes them before a standard encoder–decoder Transformer processes the compressed input.
Results
Removing nearly one-third of English–French source bytes preserves translation performance, while other language pairs achieve comparable or improved quality at compression ratios of 0.47–0.67.
Takeaways & Limitations
Byte-level inputs contain predictable information that can be omitted, suggesting predictability-based computation allocation as a mechanism for reducing sequence length.
Takeaways & Limitations
The experiments focus exclusively on machine translation and use a fixed autoregressive predictor architecture.
Abstract
from arXiv · showhide
Modern input methods routinely rely on autocomplete to omit information that can be recovered from local context. Inspired by these autocomplete-assisted writing systems, we investigate whether Transformer inputs can be compressed in a similar manner. Byte-level tokenization offers a simple and language-independent alternative to subword tokenization, but its longer input sequences typically result in increased computational cost and reduced model quality. We propose a compression scheme that employs a lightweight autoregressive byte language model to identify and remove bytes that are easily predictable from their surrounding context before Transformer processing. The resulting compressed representation is then provided as input to a standard encoder--decoder Transformer. Experiments on machine translation show that a substantial fraction of source-language bytes can be omitted without degrading translation quality. On English--French, our best method preserves translation performance while reducing source sequence length by nearly one-third. Additional experiments on Finnish--English, Russian--English, and Chinese--English demonstrate that the approach generalizes across diverse writing systems and morphological typologies, yielding comparable or improved translation quality at compression ratios between 0.47 and 0.67. These findings suggest that many input bytes are predictable enough to be represented implicitly rather than explicitly, providing a simple mechanism for reducing the sequence-length overhead associated with byte-level models.
1 Introduction
This pilot study introduces autocomplete-based byte compression for Transformer inputs, removing predictable bytes to reduce sequence length while preserving machine-translation quality across languages and writing systems.
- Motivation: Byte-level representations offer simplicity and language independence but incur sequence-length overhead compared with predominant subword tokenization.Potential benefits of byte-level approaches include smaller embedding matrices, while their longer sequences can increase computational cost and reduce model quality.
- Approach: Inspired by autocomplete-assisted human input, the method uses a lightweight autoregressive model to identify and remove bytes predictable from preceding context.The compressed representation retains byte-level simplicity while mitigating input-length overhead.
- Approach: The pipeline predicts bytes, removes confidently predicted sequences with optional sentinels, then feeds the compressed sequence to a large Transformer for translation.This three-stage design comprises prediction, compression, and translation.
- Results: Nearly one-third of English–French source bytes can be removed while matching uncompressed byte-tokenization translation quality.The result demonstrates substantial source-length reduction without degrading translation quality on English–French.
- Results: Compression ratios of 0.47 to 0.67 yield comparable or improved translation performance across Finnish–English, Russian–English, and Chinese–English.These language pairs span agglutinative, Cyrillic, and logographic writing systems, respectively.
2 Related Work
Byte-level models provide language-independent, unified representations but create longer sequences and greater Transformer cost. Related work improves byte-level efficiency through architectural downsampling, adaptive patching, neural compression, and computation allocation, while this approach compresses raw bytes before Transformer processing.
- Byte-level modeling: Byte-level models avoid language-specific tokenizers and out-of-vocabulary issues, but their longer sequences increase Transformer computational burden.They operate directly on UTF-8 bytes and provide a unified representation across writing systems.
- Byte-level efficiency: ByT5 demonstrates competitive multilingual performance with pure bytes, while CANINE and Charformer address sequence-length growth through architectural modifications.CANINE uses learned downsampling before deep Transformer processing; the supplied passage introduces Charformer but truncates its description.
- Adaptive representations: BLT uses local prediction difficulty to dynamically partition byte streams into variable-length patches, grouping predictable regions more coarsely and surprising regions more finely.Both BLT and this approach exploit varying information density across byte sequences.
- Neural compression: Lester et al. train a byte-level language model and use its probability estimates in arithmetic coding, with equal-information windows and periodic context resets for Transformer training.Their neural compression framework is identified as the work most closely related to this approach.
- Computation allocation: Unlike prior token-pruning methods, this approach identifies predictable raw-byte regions with a lightweight model and compresses them before any Transformer computation.Power-BERT progressively eliminates token representations within Transformer layers, whereas this method produces a shorter input sequence during preprocessing.
- Positioning: BLT, neurally compressed text, and this approach use lightweight byte-level predictive distributions to reduce the explicit representation of easier text regions, but exploit that signal differently.The supplied passage specifies that BLT preserves original information content while adapting representation granularity.
3 Methodology
The method predicts bytes autoregressively, removes or replaces those deemed easily predictable, and feeds the compressed sequence to a standard encoder–decoder Transformer. Predictability is identified with absolute or relative probability thresholds, followed by one of four compression schemes.
- Pipeline: Autoregressive next-byte prediction precedes compression, after which the compressed sequence is translated by a standard encoder–decoder Transformer.The auxiliary language model identifies predictable bytes before Transformer processing.
- Predictability model: The auxiliary model predicts each byte from preceding tokens using a vocabulary of 256 byte values plus start- and end-of-sequence markers.The model is intended to be small and fast so it can efficiently identify predictable document parts.
- Predictability criteria: Absolute thresholding marks a byte predictable when it is the model’s most likely prediction and its probability exceeds α.Formally, the conditions are pi ≥ ˆpi and pi > α, with α ∈ (0, 1].
- Predictability criteria: Relative thresholding marks a byte predictable when the observed byte’s probability exceeds the strongest alternative by more than α.The criterion is pi − ˆpi > α, with α ∈ (0, 1].
- Compression schemes: Four compression schemes are evaluated: Sentinel-free, Explicit Sentinel, Length-encoded Sentinel, and Implicit Sentinel.Sentinel-free removes predictable bytes, while sentinel-based schemes replace consecutive predictable runs with special representations.
- Transformer input and output: The output remains subword-tokenized with Meta’s NLLB-200 multilingual tokenizer, while extending autocompletion to Transformer outputs is left for future work.The compressed source sequence uses a scheme-dependent input vocabulary; the sentinel-free vocabulary has 259 tokens.
4 Experiments
Experiments show that Implicit Sentinel compression can remove nearly one-third of English source bytes while preserving translation quality, and that the approach generalizes across diverse language pairs. Strategic autocomplete-based removal outperforms simple baselines, while prediction-threshold choice has no clear effect.
- English–French experiments: Sentinel Free outperforms the No Vowels baseline because the autocomplete model removes letters more strategically.The First Three baseline preserves only the first three letters of each word, while No Vowels removes all vowels.
- English–French experiments: Length-Encoded Sentinel outperforms Explicit Sentinel at the minor cost of adding seven sentinels to the token vocabulary.Length encoding represents the number of removed bytes explicitly.
- English–French experiments: Absolute and relative prediction thresholds perform similarly, with no clear advantage for either threshold type.The comparison isolates threshold type across the compression-scheme experiments.
- Cross-lingual evaluation: Implicit Sentinel improves Russian–English and Chinese–English translation while maintaining parity with the byte baseline on Finnish–English.The evaluation covers Finnish–English, Russian–English, and Chinese–English, representing agglutinative morphology, Cyrillic script, and logographic script.
5 Conclusion
The paper introduces byte-level input compression that removes highly predictable bytes before Transformer processing, shifting some sequence modeling to a lightweight autoregressive predictor. Across languages, this substantially reduces source length without sacrificing translation quality, while motivating predictability-aware computation and identifying limitations for future work.
- Contribution: The method removes highly predictable bytes before Transformer processing, using a lightweight autoregressive model to represent portions of input implicitly.This shifts some sequence modeling burden from the large translation model to a smaller byte-level predictor.
- Results: Nearly one-third of English–French source bytes can be removed without sacrificing translation performance using implicit-sentinel encoding.Experiments on Finnish–English, Russian–English, and Chinese–English also support cross-language generalization.
- Implications: Byte-level representations contain considerable predictable information, suggesting that future architectures could allocate computation according to predictability.This would reserve expensive Transformer processing for less predictable input portions.
- Limitations and future work: The study is limited to machine translation and a fixed autoregressive predictor architecture, leaving alternative models, broader applications, and source–target compression for future work.It also calls for systematic study of language structure, writing systems, and compression effectiveness.
A Byte Stream Analysis
The byte-level autocomplete method removes predictable structural elements more often than ASCII letters, especially spaces and UTF-8 encoding bytes. Omission patterns vary across languages, reflecting both language structure and UTF-8 redundancy.
- Structural byte omission: Omission rates are highest for structural bytes, including spaces and UTF-8 encoding bytes, rather than ASCII letters.The analysis covers ASCII letters, punctuation, digits, spaces, UTF-8 lead bytes, and continuation bytes.
- Language-specific patterns: Over 90% of Finnish UTF-8 continuation bytes are removed, compared with about 25% of ASCII letters.Finnish contains relatively few multi-byte characters, so UTF-8 redundancy offers limited overall compression potential.
- Language-specific patterns: 54% of Russian UTF-8 lead bytes and 42% of continuation bytes are removed, versus 12% of ASCII letters.These rates indicate that the model preferentially removes bytes constrained by local context.
- UTF-8 redundancy: Russian and Chinese contain many multi-byte characters, making predictable UTF-8 encoding bytes a substantial and disproportionately targeted part of their source sequences.Chinese continuation bytes are removed much more frequently than Chinese lead bytes, while Russian shows high omission rates for both types.
- Interpretation: The method preferentially removes whitespace, punctuation, and multi-byte UTF-8 components that are highly predictable from local context.The contribution of language structure versus UTF-8 properties remains unresolved.