Binary BPE: A Family of Cross-Platform Tokenizers for Binary Analysis

AI summary

Overview

Research area: Machine learning for binary analysis — specifically tokenization and input representation for sequence models (transformers, RNNs, CNNs, SSMs) applied to executable files.

Technical level: Intermediate. Familiarity with Byte Pair Encoding and transformer context windows is assumed, but the binary-format and instruction-set details are explained in accessible terms.

Scope: The paper introduces, trains, evaluates, and publicly releases a family of cross-platform Byte Pair Encoding tokenizers (4K–64K vocabularies) that operate directly on raw executable bytes, and measures their compression, structural properties, and scaling behavior on Linux, Windows, macOS, Android, and malware binaries.

What This Paper Is About

Sequence models for binary analysis are constrained by byte-level tokenization: feeding raw bytes (0x00–0xFF) into a transformer means a 100KB binary consumes 100K tokens, exhausting accelerator memory, while conventional NLP tokenizers fail on arbitrary byte sequences. The paper's goal is to build a tokenizer that learns common multi-byte patterns directly from raw executables — without disassembly or decompilation — so that models can fit roughly 2–3 times more binary content into a fixed-length context window, and to release that tokenizer openly across a range of vocabulary sizes.

Key Contributions

1. A training methodology for BPE on diverse binaries (ELF, PE, Mach-O, APK) spanning x86-64, ARM, MIPS, and RISC-V, with platform stratification so no single operating system dominates the learned vocabulary.
2. An ablation study over vocabulary size (4K, 8K, 16K, 32K, 64K) quantifying compression, 2-byte coverage, token-length shifts, and content composition.
3. Analysis of learned patterns showing that BPE unsupervisedly discovers instruction- and format-aware tokens (ELF/PE magic numbers, x86-64 REX prefixes, cross-platform strings and padding) across vocabulary sizes.
4. Public release of the Binary BPE family on HuggingFace (models mjbommar/binary-tokenizer-001-{4k,8k,16k,32k,64k}) and the custom Rust trainer (bbpe) on GitHub, along with replication materials for the paper's experiments, figures, and tables.

Main Findings

• Compression on representative binaries: On a stratified 24-binary samples/ benchmark, the 64K tokenizer achieves an overall mean of 2.62 bytes per token. Group means were Linux 2.571 (n=11), Windows 3.385 (n=3), malware Android APK 1.411 (n=1), malware Linux ELF 1.834 (n=4), malware macOS Mach-O 3.058 (n=2), and malware Windows PE 3.164 (n=3).

• Context-window efficiency: At 2.6 bytes/token, an 8,192-token context covers about 21 KB of binary content, and a 32,768-token context covers roughly 84 KB — often enough to include complete small binaries or large slices of complex executables in a single forward pass.

• Vocabulary composition (64K): Of 65,529 learned BPE tokens, 8,211 (12.5%) are readable strings, 18,013 (27.5%) are instruction patterns, 4,920 (7.5%) are high-byte-only, 256 (0.4%) are the base alphabet, 31 are pure null padding, and 34,105 (52.0%) are mixed/format structures.

• Token lengths: Learned tokens range from 1 to 32 bytes with a median of 3 bytes and mean of 4.17 bytes. Two-byte tokens dominate (24,944 tokens, 38.1%), and 3-byte tokens number 11,730 (17.9%), aligning with common x86-64 instruction encoding (REX prefix + opcode + ModR/M).

• Interpretable patterns without supervision: Magic numbers (\x7fELF, MZ, \xFE\xED\xFA\xCE), ELF section names (.text, .rodata), PE import tables, Mach-O load commands, null-byte alignment padding, and cross-platform strings (/lib/, /usr/lib/, .so, .dll, .dylib) all emerge as single tokens.

• Scaling with vocabulary size: Average token length rises from 3.000 bytes (4K) to 4.173 bytes (64K); 2-byte coverage rises from 3.01% to 38.06%; the high-byte-only share rises from 54.0% to 62.3%; the ASCII-only share falls from 46.0% to 37.7%. The 3-byte token share peaks near 8K (21.67%) before declining to 17.90% at 64K.

• Compression improves monotonically on /usr/bin/ls: 1.773 bytes/token (4K), 1.931 (8K), 2.106 (16K), 2.315 (32K), 2.534 (64K).

• 64K beats 32K on every file: Across 25 evaluation binaries (24 from samples/ plus /usr/bin/ls), average bytes per token improves from 2.34 to 2.62 — an 11.7% relative gain. Per-platform overall means were Linux 2.385, Windows 3.274, macOS 3.058, Android 1.411 for the 64K tokenizer, versus Linux 2.139, Windows 2.905, macOS 2.806, Android 1.242 for 32K.

• Perfect nested hierarchy: 4K ⊂ 8K ⊂ 16K ⊂ 32K ⊂ 64K. The first 4,089 tokens of the 4K tokenizer are identical to tokens 0–4088 in every larger tokenizer; token ID 2048 encodes the identical 2-byte sequence (0xe0a4) across all five vocabularies. This enables embedding transfer — for example, initializing the first 4K rows of a 64K embedding matrix from a trained 4K model and training only the 60K new token embeddings.

• Corpus-level statistics (64K tokenizer on Binary-30K): Linux averages 76,880 tokens per file (median 19,861, 6,134 unique, 3.339 bytes/token); Windows 258,886 (49,823, 12,850, 3.484); macOS 384,649 (336,476, 16,147, 2.836); Android 2,445,585 (1,454,293, 28,133, 1.996); Other 71,770 (2,686, 1,511, 3.048).

• Training configuration: The largest tokenizer targets 65,536 token IDs (2¹⁶), comprising 65,529 learned BPE tokens (256 base-byte symbols plus 65,273 merges) and 7 special control tokens (<|start|>, <|end|>, <|pad|>, <|unk|>, <|cls|>, <|sep|>, <|mask|>). Training used 8KB chunks with a maximum entropy threshold of 7.0 bits per byte to filter out compressed, encrypted, or random data.

Methodology in Plain English

The researchers built a corpus of approximately 30,000 binary records totaling 24 GB — a superset of the Binary-30K dataset — containing system utilities, shared libraries, drivers, applications, and malware. Sampling was stratified by platform and file type to prevent any single operating system from dominating the vocabulary; Linux-only pilot experiments produced noticeably worse compression on Windows and macOS binaries, confirming the need for balanced training.

They then applied standard Byte Pair Encoding directly to raw bytes, treating each executable as a sequence over the full 256-byte alphabet with no linguistic assumptions and iteratively merging the most frequent adjacent byte pair until reaching the target vocabulary size. Merge statistics were computed globally across the cross-platform corpus. Because BPE is deterministic and cumulative, training multiple vocabulary sizes on the same data yields the nested-prefix property for free: larger tokenizers simply continue merging where smaller ones stopped.

To filter out noise, they used a custom Rust trainer with entropy filtering, discarding high-entropy 8KB blocks that likely contain compressed, encrypted, or random data. Evaluation was organized along four dimensions: (1) vocabulary structure from the released tokenizer JSONs (length distributions, 2-byte coverage, content categories); (2) single-file compression on /usr/bin/ls; (3) stratified compression on 24 representative binaries spanning operating systems, architectures, formats, and benign/malicious samples; and (4) population-level corpus statistics from the tokenized Binary-30K dataset. Special tokens were added only after training and never participated in merges.

Why This Matters

Impact on research. The paper claims that before this work, no openly available cross-platform BPE tokenizer operated directly on raw executable bytes across ELF, PE, Mach-O, and APK formats. Prior academic approaches either operate on disassembled text (requiring successful disassembly and failing on stripped or obfuscated binaries), require decompiled symbolic metadata (Android manifest XML), use fixed n-grams without adaptive vocabulary learning, or are proprietary industry systems with no public documentation or release. The release of trained models and a trainer lowers the barrier to reproducible binary-ML research and enables controlled scaling studies that a single fixed tokenizer cannot support.

Real-world applications:

• Content identification and malware detection — multi-byte compression lets a model see far more of a file per forward pass, and learned format-magic tokens give immediate file-type and structure recognition.
• Reverse engineering and program understanding — the vocabulary exposes instruction-level and format-level units as atomic tokens, useful for stripped or obfuscated executables.
• Edge and inline security inspection — the 4K and 8K vocabularies keep the embedding layer tiny (tens of kilobytes on disk), suiting IoT gateways, embedded malware scanners, and network appliances performing inline packet inspection.
• Datacenter-scale binary processing — the 64K vocabulary maximizes compression where accelerator memory and throughput dominate cost, and the 64K-vs-32K vocabulary overhead is negligible relative to typical transformer parameter counts (10M–1B+).

Industry relevance. The paper situates the work explicitly against proprietary byte-level transformer systems that use learned tokenization internally but remain unreleased. A drop-in, open, HuggingFace-compatible tokenizer with a compatible Rust trainer means practitioners can adopt it in existing pipelines, retrain or extend it, and build smaller specialist masked- and causal-language models intended to be embedded in reverse-engineering frameworks such as Ghidra or IDA Pro, or orchestrated by larger agentic systems.

Future Directions

• Adversarial robustness. Packed, obfuscated, or polymorphic malware pushes tokenization toward the theoretical lower bound for random data, where each token covers only a few bytes. Because high entropy is incompressible, this is described as a fundamental limitation of any compression-based approach; packed-stub detection and selective tokenization of executable sections are proposed as partial mitigations.
• Handling extreme sequence lengths. Android APKs tokenize to well over a million tokens per file on the Binary-30K corpus, exceeding most transformer context windows (8K–128K) even after compression. Hierarchical or recursive tokenization and selective windowing are suggested, though these add architectural complexity and risk information loss; the paper also points to systems that unpack or deobfuscate binaries before tokenization.
• Architecture imbalance and semantic grounding. MIPS and RISC-V are underrepresented in the corpus relative to x86-64 and ARM, and pilot experiments suggest weaker compression for those architectures. Separately, BPE captures byte co-occurrence statistics but not execution semantics — a token for 0x48 0x89 0xE5 does not know it moves a stack pointer. Semi-supervised learning with labeled instruction sets or multi-task objectives predicting both tokens and instruction types are proposed.
• Format evolution and down- stream evaluation. Binary formats change over time, so a tokenizer trained in 2025 may degrade on 2030 binaries; periodic retraining or online vocabulary adaptation are suggested but add deployment complexity. The authors also state they are training transformer models for malware family classification, binary similarity detection, and function-purpose identification on Binary-30K, with the goal of releasing public baselines.

Target Audience

This paper is most useful to machine-learning researchers and engineers working on binary analysis, malware detection, and reverse engineering who need an efficient input representation for sequence models; to practitioners deploying binary classifiers or scanners under memory and latency constraints on edge devices or in datacenters; and to tooling developers who want to embed small specialist language models inside reverse-engineering frameworks or agentic analysis workflows. It also serves readers interested in tokenization fundamentals and scaling behavior, since the nested vocabulary family supports controlled ablation studies of the compression–expressiveness tradeoff.

Authors’ abstract

Sequence models for binary analysis are bottlenecked by byte-level tokenization: raw bytes waste precious context window capacity for transformers and other neural network architectures, and many existing text-oriented tokenizers fail on arbitrary 0x00--0xFF sequences. To address this issue, we introduce the Binary BPE tokenizer family, a set of cross-platform Byte Pair Encoding (BPE) tokenizers for executables trained on a large corpus of binaries spanning multiple platforms, architectures, and operating systems, including Linux, Windows, macOS, Android, and malware sources. We release trained tokenizers with vocabularies of 4K, 8K, 16K, 32K, and 64K tokens, enabling both systematic scaling studies and practical deployment from resource-constrained edge devices to high-throughput datacenters. These tokenizers discover interpretable patterns (ELF/PE headers, instruction sequences, cross-platform strings) while yielding multi-byte compression per token. On representative uncompressed executables (e.g., ELF/PE/Mach-O rather than compressed APKs), the Binary BPE tokenizers typically allow for roughly 2-3x more binary content per fixed-length transformer context window than raw bytes, enabling more efficient research and practical deployment for content identification, malware detection, reverse engineering, and optimization. We release the trained Binary BPE tokenizers on HuggingFace, providing a drop-in, open-source foundation for binary-focused language models and context-efficient agentic tools.