# Counting Ability of Large Language Models and Impact of Tokenization

arXiv: https://arxiv.org/abs/2410.19730 · HTML: https://mlsanity.com/paper/2410.19730/

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 23 of its 45 references that are in the map.
- First posted on arXiv 25 Oct 2024.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 23 of 23)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Qwen Technical Report](https://mlsanity.com/paper/2309.16609/) (2023)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [RWKV: Reinventing RNNs for the Transformer Era](https://mlsanity.com/paper/2305.13048/) (2023)
- [On the Expressive Power of Deep Neural Networks](https://mlsanity.com/paper/1606.05336/) (2016)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Physics of Language Models: Part 3.1, Knowledge Storage and Extraction](https://mlsanity.com/paper/2309.14316/) (2023)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [On the Practical Computational Power of Finite Precision RNNs for Language Recognition](https://mlsanity.com/paper/1805.04908/) (2018)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [Don't Trust ChatGPT when Your Question is not in English: A Study of Multilingual Abilities and Types of LLMs](https://mlsanity.com/paper/2305.16339/) (2023)
- [Transformers, parallel computation, and logarithmic depth](https://mlsanity.com/paper/2402.09268/) (2024)
- [Deep AutoRegressive Networks](https://mlsanity.com/paper/1310.8499/) (2013)
- [LSTM Networks Can Perform Dynamic Counting](https://mlsanity.com/paper/1906.03648/) (2019)
- [A Survey of Neural Networks and Formal Languages](https://mlsanity.com/paper/2006.01338/) (2020)
- [TTIDA: Controllable Generative Data Augmentation via Text-to-Text and Text-to-Image Models](https://mlsanity.com/paper/2304.08821/) (2023)
- [A Character-Level Length-Control Algorithm for Non-Autoregressive Sentence Summarization](https://mlsanity.com/paper/2205.14522/) (2022)
- [ContraNovo: A Contrastive Learning Approach to Enhance De Novo Peptide Sequencing](https://mlsanity.com/paper/2312.11584/) (2023)

## Built on by (most cited first, 30 of 32)

- [Large Language Model Reasoning Failures](https://mlsanity.com/paper/2602.06176/) (2026)
- [Assessing the Chemical Intelligence of Large Language Models](https://mlsanity.com/paper/2505.07735/) (2025)
- [CodeDance: A Dynamic Tool-integrated MLLM for Executable Visual Reasoning](https://mlsanity.com/paper/2512.17312/) (2025)
- [Multi2: Multi-Agent Test-Time Scalable Framework for Multi-Document Processing](https://mlsanity.com/paper/2502.20592/) (2025)
- [TituLLMs: A Family of Bangla LLMs with Comprehensive Benchmarking](https://mlsanity.com/paper/2502.11187/) (2025)
- [Reasoning Under Uncertainty: Exploring Probabilistic Reasoning Capabilities of LLMs](https://mlsanity.com/paper/2509.10739/) (2025)
- [StochasTok: Improving Fine-Grained Subword Understanding in LLMs](https://mlsanity.com/paper/2506.01687/) (2025)
- [Map&Make: Schema Guided Text to Table Generation](https://mlsanity.com/paper/2505.23174/) (2025)
- [Universal Biological Sequence Reranking for Improved De Novo Peptide Sequencing](https://mlsanity.com/paper/2505.17552/) (2025)
- [Prompt-Based One-Shot Exact Length-Controlled Generation with LLMs](https://mlsanity.com/paper/2508.13805/) (2025)
- [IF-CRITIC: Towards a Fine-Grained LLM Critic for Instruction-Following Evaluation](https://mlsanity.com/paper/2511.01014/) (2025)
- [Understanding Counting Mechanisms in Large Language and Vision-Language Models](https://mlsanity.com/paper/2511.17699/) (2025)
- [CharBench: Evaluating the Role of Tokenization in Character-Level Tasks](https://mlsanity.com/paper/2508.02591/) (2025)
- [Sequential Enumeration in Large Language Models](https://mlsanity.com/paper/2512.04727/) (2025)
- [Repeated-Token Counting Reveals a Dissociation Between Representations and Outputs](https://mlsanity.com/paper/2605.09239/) (2026)
- [DateLogicQA: Benchmarking Temporal Biases in Large Language Models](https://mlsanity.com/paper/2412.13377/) (2024)
- [The Human Flourishing Geographic Index: A County-Level Dataset for the United States, 2013--2023](https://mlsanity.com/paper/2511.03915/) (2025)
- [VikingMem: A Memory Base Management System for Stateful LLM-based Applications](https://mlsanity.com/paper/2605.29640/) (2026)
- [ByteFlow: Language Modeling through Adaptive Byte Compression without a Tokenizer](https://mlsanity.com/paper/2603.03583/) (2026)
- [No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval](https://mlsanity.com/paper/2605.30120/) (2026)
- [PiERN: Token-Level Routing for Integrating High-Precision Computation and Reasoning](https://mlsanity.com/paper/2509.18169/) (2025)
- [Reflection Pretraining Enables Token-Level Self-Correction in Biological Sequence Models](https://mlsanity.com/paper/2512.20954/) (2025)
- [Semantic Content Determines Algorithmic Performance](https://mlsanity.com/paper/2601.21618/) (2026)
- [Beyond Accuracy: Diagnosing Algebraic Reasoning Failures in LLMs Across Nine Complexity Dimensions](https://mlsanity.com/paper/2604.06799/) (2026)
- [The Position Curse: LLMs Struggle to Locate the Last Few Items in a List](https://mlsanity.com/paper/2605.07127/) (2026)
- [Blind-Spots-Bench: Evaluating Blind Spots in Multimodal Models](https://mlsanity.com/paper/2607.08317/) (2026)
- [The Imitation Game: When LLMs Learn to Reason Like Programs via Code-Centric Reasoning Data Synthesis](https://mlsanity.com/paper/2609.16076/) (2026)
- [A Dual-Process Perspective on Nudge Susceptibility in LLM-Based GUI Agents](https://mlsanity.com/paper/2609.19843/) (2026)
- [Repetition, Not Length: Isolating the Counting Failure in Neural Text-to-Speech](https://mlsanity.com/paper/2609.36974/) (2026)
- [LS-AR: Future-Predictive Latent Steering in Autoregressive LLMs](https://mlsanity.com/paper/2610.03093/) (2026)

## Abstract (arXiv)

Transformers, the backbone of modern large language models (LLMs), face inherent architectural limitations that impede their reasoning capabilities. Unlike recurrent networks, Transformers lack recurrent connections, confining them to constant-depth computation. This restriction places them in the complexity class TC0, making them theoretically incapable of solving tasks that demand increasingly deep reasoning as input length grows. Counting, a fundamental component of many reasoning tasks, also requires reasoning depth to grow linearly to be performed inductively. While previous studies have established the upper limits of counting ability in Transformer-based expert models (i.e., models specifically trained for counting tasks), these findings do not directly extend to general-purpose LLMs due to differences in reasoning mechanisms. Recent work has highlighted how Chain of Thought (CoT) reasoning can help alleviate some of the architectural limitations of Transformers in counting tasks. However, little attention has been paid to the role of tokenization in these models. Unlike expert models that often use character-level tokenization, LLMs typically rely on byte-level (BPE) tokenizers, which fundamentally alters the way reasoning is processed. Our work investigates the impact of tokenization on the counting abilities of LLMs, uncovering substantial performance variations based on input tokenization differences. We provide both theoretical and experimental analyses, offering insights into how tokenization choices can undermine models' theoretical computability, thereby inspiring the design of new tokenization methods to enhance reasoning in LLMs.