Tokenization Constraints in LLMs: A Study of Symbolic and Arithmetic Reasoning Limits

Xiang Zhang, Juntai Cao, Jiaqi Wei, Yiwei Xu, Chenyu You · 2025

Read Tokenization Constraints in LLMs: A Study of Symbolic and Arithmetic Reasoning Limits by Xiang Zhang, Juntai Cao, Jiaqi Wei, Yiwei Xu, Chenyu You (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-14178.txt.

Introduction

Xiang Zhang and co-authors argue that how a language model chops text into tokens can cap its reasoning, in a 2025 paper. Tokenization is the first step a model takes, long before it thinks through a problem. Common schemes merge chunks of text into single tokens. That can blur the small units a math or logic task turns on.

The authors coin the term Token Awareness for how well a token split lines up with those units. They test models on sums and symbol tasks with varied token splits. Even with step-by-step prompts, poor splits led to failure. Clean, atom-by-atom formats let a small model beat a far larger one. The lesson is that reasoning skill rests on token design, not just model size.

Catalog record

CREATORXiang Zhang, Juntai Cao, Jiaqi Wei, Yiwei Xu, Chenyu You
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE74 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-14178

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Tokenization Constraints in LLMs: A Study of Symbolic and Arithmetic Reasoning Limits Xiang Zhang, Juntai Cao, Jiaqi Wei, Yiwei Xu, Chenyu You Abstract Tokenization is the first—and often underappreciated—layer of computation in language models. While Chain-of-Thought (CoT) prompting enables transformer models to approximate recurrent computation by externalizing intermediate steps, we show that the success of such reasoning is fundamentally bounded by the structure of tokenized inputs. This work presents a theoretical and empirical investigation into how tokenization schemes, particularly subword-based methods like byte-pair encoding (BPE), impede symbolic computation by merging or obscuring atomic reasoning units. We introduce the notion of Token Awareness to formalize how poor token granularity disrupts logical alignment and prevents models from generalizing symbolic procedures. Through systematic evaluation on arithmetic and symbolic tasks, we demonstrate that token structure dramatically affect reasoning performance, causing failure even with CoT, while atomically-aligned formats unlock strong generalization, allowing small models (e.g., GPT-4o-mini) to outperform larger systems (e.g., o1) in structured reasoning. Our findings reveal that symbolic reasoning ability in LLMs is not purely architectural, but deeply conditioned on token-level representations. Full code, prompts, and results are available at Anonymous GitHub . 1 Introduction Inductive reasoning and arithmetic computation , such as counting, addition, and pattern generalization, are foundational components of symbolic and algorithmic intelligence. These abilities have long been studied across disciplines—from their cognitive development in humans Wynn (1990) ; De Bruijn (1964) to their formal characterization in logic and computability theory Boolos et al. (2002) ; Cooper (2017) . In theoretical computer science, arithmetic primitives like counting and addition have been analyzed in terms of circuit complexity Jerrum (1995) , computational depth Fischer et al. (1968) , and machine models such as counter automata Ibarra et al. (2002) . Even simple operations—e.g., counting from 1 to n —are known to require a depth complexity that grows with input length, imposing strict lower bounds on any computational model Fischer et al. (1968) . Transformers Vaswani (2017) , including both autoregressive (GPT-style) Gregor et al. (2014) ; Achiam et al. (2023) and non-autoregressive (BERT-style) Devlin (2018) ; Liu et al. (2022) variants, are inherently limited to constant-depth computation Zhang et al. (2024) ; Delétang et al. (2022) ; Li et al. (2024a) . In neural models, all computation occur within model’s latent space \bm{\mathcal{H}} , where the hidden state \bm{h} encodes intermediate computational representations. Unlike recurrent architectures—where hidden states evolve over time via recursive updates \bm{h}_{t}=g_{\theta}(\bm{h}_{t-1}) —Transformers update \bm{h} only across a fixed number of layers, independent of input length. As a result, a standard Transformer can process (or reason over) its hidden states only a constant number of times, limiting its computational depth and situating it at the lower end of the Chomsky hierarchy Delétang et al. (2022) . This architectural bottleneck fundamentally restricts Transformer-based models—ranging from task-specific expert systems to large-scale LLMs—from solving even basic arithmetic operations such as counting , which require iterative updates to internal state and growing depth with input length. Figure 1: Illustration of inductive reasoning as performed by humans, RNNs, and LLMs with CoT, respectively. Chain of Thought (CoT) Wei et al. (2022) revolutionizes the reasoning paradigm by shifting the locus of computation from the latent space \bm{\mathcal{H}} to the textual output space \bm{\mathcal{O}} Zhang et al. (2024) . By externalizing intermediate reasoning steps into natural language "thoughts," CoT enables transformer-based models to tackle fundamental computational tasks that would otherwise exceed their architectural capacity. These include basic arithmetic and symbolic reasoning operations such as counting, addition, and sequence manipulation. Theoretical studies Li et al. (2024a) ; Zhang et al. (2024) ; Feng et al. (2024) demonstrate that CoT-augmented language models, under idealized assumptions, possess an upper bound capacity to simulate computations of arbitrary complexity—thereby extending the class of tasks solvable beyond what standard Transformers can achieve. Despite extensive theoretical analyses and guarantees on the upper bound of computational abilities Zhang et al. (2024) ; Chang and Bisk (2024) , actual model performance remains far below these limits. As LLMs scale from millions to billions of parameters Achiam et al. (2023) , improvements on fundamental tasks such as counting have been marginal—GPT-4, for instance, still struggles to count the number of "r"s in a word. While recent work has explored contributing factors like training data Allen-Zhu and Li (2023) and positional encoding Chang and Bisk (2024) , one of the most basic components—tokenization—has received surprisingly little attention. In particular, modern byte pair encoding (BPE) Sennrich (2015) merges multiple characters into single tokens for efficiency, often degrading arithmetic reasoning due to information loss during tokenization. Even OpenAI’s latest o1 1 1 1 https://openai.com/o1 model, which integrates Monte Carlo Tree Search (MCTS) for improved reasoning, achieves only 50% accuracy on long string arithmetic tasks involving 30–40 characters. In this work, we systematically investigate how tokenization choices can substantially constrain the theoretical reasoning and arithmetic capabilities of neural models. Our approach is model-agnostic, allowing us to evaluate even closed-source LLMs with undisclosed tokenization schemes. Leveraging extensive experiments with Chain of Thought (CoT)—which has been theoretically shown to achieve Turing completeness under idealized conditions Li et al. (2024b) —we demonstrate that the choice of tokenization plays a critical role in unlocking a model’s full computational potential and bridging the gap between theoretical guarantees and practical performance. Neglecting this factor can lead to performance degradations of up to 80%. Moreover, we find that the impact of tokenization is model-dependent: some tokens disproportionately hinder performance on counting tasks, even when the underlying task remains fixed. 2 Neural Networks and Arithmetic: A Revisit Training neural networks for arithmetic computation. Arithmetic operations—including counting, matching, and bracket balancing—are foundational for symbolic reasoning and more complex algorithmic tasks Chang and Bisk (2024) . Early studies on training neural networks (NNs) for such tasks focused on architectures capable of handling variable-length inputs. Since multi-layer perceptrons (MLPs) Rosenblatt (1958) are inherently limited to fixed-size inputs, initial progress came through recurrent neural networks (RNNs). Rodriguez et al. (1999) trained early RNNs to recognize the regular language \texttt{a}^{n}\texttt{b}^{n} , which requires the network to implicitly count occurrences of a and b . Of the 50 networks trained, 8 successfully generalized to longer sequences, highlighting RNNs’ capacity for basic arithmetic generalization. Building on this, Suzgun et al. (2019) showed that LSTMs could perform more complex dynamic counting via bracket pairing tasks, leveraging gating and cell-state mechanisms to maintain multiple counters—capabilities that standard RNNs lacked. Figure 2: CoT vs Answer Only Generation Models. Theory of Model Architectures with Composability. Delétang et al. (2022) systematically investigated arithmetic capabilities across modern architectures, including RNNs, LSTMs, and Transformers. Their findings confirmed that while LSTMs exhibit computational behavior aligned with counter machines, Transformers consistently fail at even basic counting tasks. Chang and Bisk (2024) extended this analysis to newer architectures such as Mamba Gu and Dao (2023) and RWKV Peng et al. (2023) , revealing that these models also underperform on arithmetic tasks outside their training distributions—often performing worse than classic RNNs in generalization. Recent studies Weiss et al. (2018) ; Ackerman and Cybenko (2020) have further validated the computational capabilities of both RNNs and LSTMs, particularly for tasks requiring symbolic or arithmetic reasoning. In contrast, Transformers—lacking inherent recurrence—are restricted to TC 0 complexity in their

Read the complete text