byte-pair-encoding · research · also BPE, Byte pair encoding

Byte-pair encoding

Byte-pair encoding repeatedly replaces frequent adjacent byte pairs with unused byte values and records the substitutions needed to reconstruct the input.

Mechanism: In the original byte-oriented scheme, replacements can themselves appear in later pairs. Decoding recursively expands the stored pair table; the reduced payload alone is insufficient. [1]

Byte budget: A block needs unused values among the 256 byte codes. The original implementation splits input into blocks to retain spare codes. Re-Pair instead extends its symbol alphabet; a new grammar symbol need not fit in one byte. [1] [3]

Accounting: In the teaching format, abababab becomes two rules and two payload bytes: 14 header + 6 rule + 2 payload = 22 stored bytes for 8 input bytes. Repeating ab 128 times gives 37 stored bytes for 256 input bytes; selecting six rather than seven rules gives 36. The smallest prefix includes table cost; neither example estimates typical compression. [5]

Seeking: With its pair table available, decoding can start at a payload-code boundary. This does not identify which compressed position contains a requested original-byte offset; that needs additional mapping or expansion. [2]

Tokenization: A later adaptation learns character-sequence merges from training words, excluding cross-word pairs. Its learned symbols are not restricted to unused byte values, and token count is not stored-byte size. [4]

Relations

related
Re-Pair compression, Grammar compression, Lossless compression, Compression dictionary

Limitations

  • The substitution table does not authenticate the decoded bytes; a changed rule can produce different output of the same length. [5]

Citations

  1. Gage (1994): A New Algorithm for Data Compression, C Users Journal, February; archived article (accessed 2026-11-18)
  2. Gage (1997): Random Access Data Compression, C Users Journal, September; archived article (accessed 2026-11-18)
  3. Larsson and Moffat: Offline Dictionary-Based Compression, DCC 1999, sections 2.2-2.3 (accessed 2026-11-18)
  4. Sennrich, Haddow and Birch: Neural Machine Translation of Rare Words with Subword Units, ACL 2016, section 3.2 (accessed 2026-11-18)
  5. Hesela: byte-pair substitution, full representation accounting and decoder controls (accessed 2026-11-18)
Sources & caveats
  • Original byte-oriented BPE is distinguished from extended-alphabet grammar compression and the 2016 character-based tokenization adaptation.
  • The executable model has its own framing, tie-breaking and stopping policy; it is not Gage's wire format or a reproduction of historical performance measurements.

JSON: /data/terms/byte-pair-encoding.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Byte-pair encoding. Hesela. 2026-11-18. https://hesela.dev/terms/byte-pair-encoding/