title: Counting Ability of Large Language Models and Impact of Tokenization
summary: 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 TC^0, 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.
paper_authors._id: 671f2fe7aadccdbd12aa688d
paper_authors.name: Xiang Zhang
paper_authors.status: extracted_confirmed
paper_authors.statusLastChangedAt: 2024-10-28T15:41:18.496Z
paper_authors._id: 656553d89bf6665f10e3a92d
paper_authors.avatarUrl: /avatars/f55b09e249c48ef3fe484afa33a182ae.svg
paper_authors.fullname: xiang wyatt zhang
paper_authors.type: user
paper_authors.user: Wyattz23
paper_authors._id: 671f2fe7aadccdbd12aa688e
paper_authors.name: Juntai Cao
paper_authors._id: 671f2fe7aadccdbd12aa688f
paper_authors.name: Chenyu You
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2024-10-28T15:39:39.305Z
paper_authors._id: 6466d463060756d2854ab3e1
paper_authors.avatarUrl: /avatars/4401387180c16472a6823f78aaa86d54.svg
paper_authors.fullname: Chenyu You
paper_authors.type: user
paper_authors.user: Charlesyooo
paper_title: Counting Ability of Large Language Models and Impact of Tokenization
paper_summary: 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 TC^0, 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.
paper_ai_summary: Research explores how tokenization affects the counting abilities of large language models, revealing that byte-level tokenization can impair their theoretical computability and suggesting the need for new tokenization techniques to improve reasoning.
paper_ai_keywords: Transformers LLMs recurrent networks constant-depth computation TC$^0$ counting inductive solving Chain of Thought (CoT) reasoning character-level tokenization byte-level (BPE) tokenizers theoretical computability