How Different Tokenization Algorithms Impact LLMs and Transformer Models for Binary Code Analysis

AI summary

Overview

Research area: Natural language processing tokenization applied to binary code analysis; transformer and large language model architectures for low-level code.

Technical level: Intermediate. Readers should be familiar with tokenization concepts and transformer architectures, but the paper is written for an applied ML and security audience rather than a purely theoretical one.

Scope: A controlled empirical study of how tokenizer algorithm choice, vocabulary size, and input preprocessing affect both intrinsic tokenizer quality and downstream model accuracy on assembly code tasks across three transformer families.

What This Paper Is About

Tokenization — splitting raw input into tokens a model can process — has been studied extensively for natural language and high-level source code, but barely at all for assembly code, which is hardware-specific, syntactically inconsistent across architectures, and dense with numeric values. This paper asks a practical question: when you fine-tune an LLM or transformer on disassembled binary code, how much does the choice of tokenizer algorithm, vocabulary size, and preprocessing scheme actually matter for downstream performance? The authors answer it by training and comparing dozens of tokenizer/model combinations on a large corpus of Ghidra-disassembled C functions, then measuring both the tokenizers' intrinsic properties and the models' real task accuracy.

Key Contributions

1. First systematic intrinsic evaluation of tokenizers for assembly code. The authors compare BPE, Unigram, and WordPiece on fertility (tokens per instruction), vocabulary overlap between algorithms, and out-of-vocabulary behavior, using a 20,000-function held-out set that was never seen during tokenizer training.

2. A reproducible preprocessing scheme with measured impact. They introduce an "address-to-sequential-identifier" transformation (replacing distinct memory addresses with tokens like addr1, addr2) combined with hexadecimal-to-decimal conversion of numeric values, and test it against an unmodified baseline across every tokenizer and model configuration.

3. Cross-architecture extrinsic benchmarking at scale. They fine-tune three model families — decoder-only Llama 3.2 1B, encoder-only BERT, and encoder-decoder BART-Base — under a fixed recipe, isolating tokenizer effects across 86 total model configurations (3 algorithms × 4 vocabulary sizes × 2 dataset variants, plus each model's default pre-trained tokenizer).

4. Evidence that intrinsic tokenizer metrics only partially predict downstream performance. The paper explicitly documents where compact tokenization (favored by fertility scores) diverges from task accuracy, revealing trade-offs that tokenizer selection heuristics alone would miss.

Main Findings

• Fertility ranks tokenizers consistently, but not in the order that helps downstream tasks. Unigram is the most compact at roughly 2.0 tokens per instruction; WordPiece is the least compact at about 4.5; BPE sits in between at roughly 2.5–3.0. Despite Unigram's compression advantage, it produced the worst function-signature-prediction accuracy with Llama 3.2, generally below 80%, while BPE reached 85.76% at the 35K vocabulary size.

• Tokenizers barely agree on their vocabularies, and agreement shrinks as vocabulary grows. Overlap across the three algorithms was 0.75% at a 3K vocabulary, falling to 0.09% at 128K on the default dataset. Each algorithm partitions assembly code differently rather than converging.

• No out-of-vocabulary failures occurred. Every tokenizer at every vocabulary size successfully represented all tokens in the test set, with nothing falling back to an unknown token.

• Preprocessing helps nearly everything, with one notable exception. Replacing addresses with sequential identifiers and normalizing numeric formats slightly reduced fertility for all tokenizers, increased vocabulary overlap between algorithms, and improved accuracy on masked token prediction and function signature prediction. The exception: BERT's own default pre-trained tokenizer dropped sharply on preprocessed data (78.08% versus 85.37% on the default dataset), showing that preprocessing and tokenizer must be aligned rather than combined blindly.

• Larger vocabularies improve masked token prediction accuracy. Across both the default and preprocessed datasets and all three algorithms, accuracy rose as vocabulary size increased — attributed to better coverage of the wide range of numeric values present in machine code.

• BERT outperforms Llama 3.2 on masked token prediction, as expected. BERT's bidirectional context and its original masked-language-modeling training objective give it an inherent advantage, reaching 86.58% with BPE-35K on preprocessed data versus Llama's best custom-tokenizer result of 73.64%.

• Default pre-trained tokenizers are surprisingly strong baselines for Llama. Llama's stock tokenizer reached 80.48% (default) and 82.30% (preprocessed) on masked token prediction, well above any custom tokenizer, and 84.87% / 85.71% on function signature prediction — competitive with or better than the best trained alternatives.

• Vocabulary size has diminishing and algorithm-dependent returns. Scaling from 3K to 35K improved BPE's signature prediction accuracy from 82.44% to 85.76%, but WordPiece gained only marginally, and the 128K size for Llama did not improve over 35K (85.23% versus 85.76%).

Methodology in Plain English

The authors built a dataset by scraping public GitHub repositories for C source code, compiling it with GCC at optimization level 2 with debug information, and disassembling the resulting binaries with Ghidra. They used TLSH fuzzy hashing to strip out duplicate functions, then randomly sampled 100,000 functions, keeping only those between 30 and 100 instructions long to balance meaningful behavior against computational cost. The split was 80,000 functions for training and 20,000 for testing.

On that data they trained custom tokenizers using all three algorithms (BPE, Unigram, WordPiece) at several vocabulary sizes (3K, 25K, 35K, with 128K added for Llama to match its default scale), once on raw disassembly and once on the preprocessed version. Each tokenizer then drove fine-tuning of its model, with all other settings — hyperparameters, training procedure, data — held constant so that any performance difference could be attributed to tokenization alone.

Evaluation happened in two stages. The intrinsic stage ran the tokenizers over held-out functions and measured how many tokens each needed per instruction (fertility), how much their vocabularies overlapped, and whether any tokens went unrecognized. The extrinsic stage measured actual model accuracy on two tasks: masked token prediction, where 15% of tokens in each function were replaced with a mask and the model had to recover them, and function signature prediction, where the model inferred parameter and return types from disassembly. BERT handled the masked token task on the encoder side; Llama 3.2 and BART handled signature prediction, since BERT cannot generate output.

Why This Matters

For research, this paper closes a documented gap: tokenization had been heavily studied for natural language and source code but treated as an afterthought in binary analysis pipelines, where papers often inherit a tokenizer without justification. It also provides a methodological warning — intrinsic metrics like fertility are easy to compute and intuitively appealing, but they did not reliably predict which tokenizer would win downstream. Any future work that optimizes a tokenizer in isolation risks optimizing the wrong quantity.

Real-world applications that depend on these findings:

• Reverse engineering stripped binaries, where recovering function names, parameter types, and signatures from disassembly is a core analyst task that this paper directly benchmarks.
• Malware analysis and triage, where automated understanding of compiled code accelerates classification and attribution without requiring source access.
• Vulnerability detection in third-party or legacy binaries, where a model must reason over disassembly the original developers never annotated.
• Binary similarity detection and code search, where consistent tokenization determines whether two compiled functions map to comparable representations.
• Decompilation and code completion tooling, where generative models must reconstruct coherent instructions from partial input.

Industry relevance is direct for security vendors, incident response teams, and any organization maintaining tooling for software built from compiled artifacts. Because these workflows increasingly embed transformer models, a poorly chosen tokenizer is a silent, systemic accuracy tax. The paper also demonstrates that stock tokenizers from general-purpose models are surprisingly competitive, which matters for teams weighing the cost of custom tokenizer training against off-the-shelf deployment.

Future Directions

• Develop numeric-aware tokenization for assembly. Numeric values dominate disassembly and drive many of the observed effects, yet address normalization and hexadecimal conversion are blunt instruments. Learned or arithmetic-aware embeddings for constants remain open.

• Test cross-architecture generalization. The dataset is x86-64 C code from GCC. Whether these tokenizer rankings hold for ARM, MIPS, or RISC-V, or for binaries produced by other compilers and optimization levels, is untested.

• Close the gap between intrinsic and extrinsic evaluation. Since fertility and vocabulary overlap only partially predicted task accuracy, a better intrinsic proxy — or a principled understanding of when intrinsic metrics mislead — would make tokenizer selection cheaper and more reliable.

• Investigate why default tokenizers remain competitive. Llama's stock tokenizer outperformed every custom-trained alternative on masked token prediction despite never being trained on assembly. Understanding whether this reflects training-data scale, general-purpose robustness, or a limitation of small custom vocabularies could reshape how domain adaptation is approached.

• Extend to additional downstream tasks and larger models. The study covers two tasks and models up to 1B parameters. Realistic binary analysis deployments involve larger models and tasks such as vulnerability classification and binary diffing, where tokenization effects may differ.

Target Audience

This paper is most valuable to applied machine learning researchers and practitioners working on code representation learning, particularly those building NLP-based pipelines for binary analysis. Security researchers and reverse engineers who incorporate language models into tooling will find the practical guidance on preprocessing and vocabulary sizing directly actionable. NLP researchers studying tokenization outside standard natural language domains will find the intrinsic-versus-extrinsic gap instructive. Graduate students entering binary analysis or program comprehension will benefit from the paper's framing of why tokenization, an easily overlooked preprocessing step, deserves explicit design attention.

Authors’ abstract

Tokenization is fundamental in assembly code analysis, impacting intrinsic characteristics like vocabulary size, semantic coverage, and extrinsic performance in downstream tasks. Despite its significance, tokenization in the context of assembly code remains an underexplored area. This study aims to address this gap by evaluating the intrinsic properties of Natural Language Processing (NLP) tokenization models and parameter choices, such as vocabulary size. We explore preprocessing customization options and pre-tokenization rules tailored to the unique characteristics of assembly code. Additionally, we assess their impact on downstream tasks like function signature prediction -- a critical problem in binary code analysis. To this end, we conduct a thorough study on various tokenization models, systematically analyzing their efficiency in encoding assembly instructions and capturing semantic nuances. Through intrinsic evaluations, we compare tokenizers based on tokenization efficiency, vocabulary compression, and representational fidelity for assembly code. Using state-of-the-art pre-trained models such as the decoder-only Large Language Model (LLM) Llama 3.2, the encoder-only transformer BERT, and the encoder-decoder model BART, we evaluate the effectiveness of these tokenizers across multiple performance metrics. Preliminary findings indicate that tokenizer choice significantly influences downstream performance, with intrinsic metrics providing partial but incomplete predictability of extrinsic evaluation outcomes. These results reveal complex trade-offs between intrinsic tokenizer properties and their utility in practical assembly code tasks. Ultimately, this study provides valuable insights into optimizing tokenization models for low-level code analysis, contributing to the robustness and scalability of Natural Language Model (NLM)-based binary analysis workflows.