Counting Ability of Large Language Models and Impact of Tokenization
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.
671f2fe7aadccdbd12aa688d
Xiang Zhang
extracted_confirmed
2024-10-28T15:41:18.496Z
656553d89bf6665f10e3a92d
/avatars/f55b09e249c48ef3fe484afa33a182ae.svg
xiang wyatt zhang
user
Wyattz23
671f2fe7aadccdbd12aa688e
Juntai Cao
671f2fe7aadccdbd12aa688f
Chenyu You
admin_assigned
2024-10-28T15:39:39.305Z
6466d463060756d2854ab3e1
/avatars/4401387180c16472a6823f78aaa86d54.svg
Chenyu You
user
Charlesyooo
Counting Ability of Large Language Models and Impact of Tokenization
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.
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.
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