The Complexity Trap: Robustness Limits of Subword Tokenization for Code

This record contains the paper, figures, and supplementary materials for “The Complexity Trap: Robustness Limits of Subword Tokenization for Code.” The work studies the robustness of subword tokenization (Byte-Pair Encoding, BPE) for code understanding under variable renaming, a semantics-preserving transformation. Through controlled experiments on synthetic Python programs organized by algorithmic complexity (linear, conditional, loop, and recursive), we show that BPE-based models experience increasing performance degradation as code complexity grows. The analysis is further validated on OpenAI’s HumanEval benchmark, where BPE models degrade substantially more on recursive problems than on linear ones, while Abstract Syntax Tree (AST)–based representations remain invariant. These results demonstrate a representation-level limitation of text-based tokenization for code and highlight the importance of structural inductive biases for robust code understanding. The archive includes the final paper PDF, LaTeX sources, figures, and experimental artifacts.