CharBench: Evaluating the Role of Tokenization in Character-Level Tasks

1. Problem Statement

Large Language Models (LLMs) exhibit a significant disconnect between their high-level reasoning capabilities and their performance on low-level, surface-level text analysis tasks. A canonical example is the failure to count characters (e.g., "How many 'r's are in 'strawberry'?") or locate specific character positions within words.

While a common hypothesis suggests that this failure stems from the reliance on subword tokenization (e.g., Byte-Pair Encoding) rather than individual characters, existing literature offers conflicting conclusions. Some studies argue tokenization is the primary bottleneck, while others claim it is insignificant. Furthermore, previous benchmarks are often too small for rigorous statistical analysis or focus on specific edge cases (like first/last characters) rather than general intra-word dynamics.

2. Methodology

CHARBENCH Construction

The authors introduce CHARBENCH, a comprehensive benchmark designed to systematically evaluate LLMs on character-level reasoning in English.

• Scale: It contains 175,000 question-answer pairs, two orders of magnitude larger than previous alternatives.
• Data Source: Strings are uniformly sampled from the MiniPile dataset, stratified to ensure balanced coverage of word lengths (4 to 10 characters).
• Task Categories: The benchmark focuses on two distinct types of reasoning:
  1. Counting (Occurrence Tracking):
     • Character Frequency Count: Counting specific character occurrences (e.g., "How many 's' in 'mississippi'?").
     • Unique Character Count: Counting distinct characters in a word.
  2. Indexing (Positional Understanding):
     • Find First Occurrence: Identifying the index of the first occurrence of a character.
     • Find Last Occurrence: Identifying the index of the last occurrence.
• Deterministic Nature: Tasks are mapped to simple Python functions (count(), index()), ensuring verifiable ground truth and allowing for controlled evaluation.

Experimental Setup

• Models Evaluated: A diverse set of state-of-the-art models, including:
  • Proprietary: GPT-4o, GPT-4o-mini, GPT-3.5-turbo.
  • Open-Weight: DeepSeek-V3, Llama-3.3-70B, Llama-3.1-405B, Mistral-7B.
• Constraint: All models use Byte-Pair Encoding (BPE). Access to the tokenizer is required to analyze the relationship between input segmentation and model output.
• Evaluation Metric: Exact match accuracy. Temperature is set to 0 for deterministic outputs.

Analysis Framework

The authors perform a large-scale statistical analysis correlating model correctness with intrinsic tokenization properties:

• Word Length (WL): Number of characters.
• Gold Truth (GT): The correct answer (count or index).
• GT/WL: Normalized Gold Truth (relative position or proportion).
• Number of Tokens (NT): How many tokens the word is split into.
• Compression Ratio (CR): Characters per token.
• Target Token Length (TTL): The character length of the specific token containing the queried character (crucial for indexing tasks).

3. Key Results

Overall Performance

• CHARBENCH presents a significant challenge. The average accuracy across all models is 50.33%.
• GPT-4o performs best (70.73% average), significantly outperforming others.
• Open-Weight Models: DeepSeek-V3 leads among open models (57.18%), followed closely by Llama-3.1-405B.
• Task Difficulty: Positional understanding (Indexing) is harder than counting.
  • Counting tasks: Average accuracy ~77%.
  • Indexing tasks: Average accuracy drops to ~43.6% (Find First) and 32.4% (Find Last).

Correlation with Tokenization Properties

The study reveals nuanced relationships between tokenization and performance, challenging the binary "tokenization is good/bad" debate:

1. Word Length: There is a consistent negative correlation between word length and performance across all models and tasks. Longer words lead to lower accuracy, suggesting a fundamental limitation in processing long strings.
2. Counting Tasks:
   • Performance is strongly correlated with the actual number of character occurrences (Gold Truth).
   • Tokenization properties (Number of Tokens, Compression Ratio) show weak or negligible correlation with correctness.
   • Conclusion: For counting, the difficulty lies more in the magnitude of the count and word length than in how the word is tokenized.
3. Indexing Tasks (Positional):
   • Performance is negatively correlated with the Target Token Length (TTL).
   • As the token containing the target character becomes longer (i.e., more characters compressed into a single token), accuracy drops significantly.
   • Conclusion: Longer tokens obscure character-level positional information, creating a tradeoff between token-level compression and the model's ability to reason about character positions.
4. Token Count vs. Compression: Contrary to some prior work, the number of tokens per word and the compression ratio are not the primary drivers of failure. Instead, the internal structure of the specific token (TTL) is the critical factor for positional tasks.

Error Analysis

• Error Overlap: For counting tasks, errors are model-specific (low overlap). For indexing tasks (especially "Find Last"), errors show high overlap across models, suggesting a shared architectural limitation.
• Biases: Models tend to undercount in frequency tasks and over-index (guess higher indices) in "Find Last" tasks.

4. Key Contributions

1. CHARBENCH Benchmark: A massive, statistically robust dataset (175k samples) specifically designed to isolate character-level reasoning from high-level semantic understanding.
2. Intrinsic Metric Analysis: A novel methodology for evaluating tokenization effects without perturbing inputs (unlike prior work that added special characters). This allows for a "pure" statistical view of how natural tokenization impacts performance.
3. Refined Understanding of Tokenization: The paper clarifies that tokenization's impact is task-dependent:
   • It is less critical for counting tasks (where word length and count magnitude matter more).
   • It is critical for positional tasks, specifically where long tokens obscure character boundaries.
4. Baseline Establishment: Provides the first comprehensive performance baseline for a wide range of open and proprietary models on these specific low-level tasks.

5. Significance and Future Work

• Architectural Insight: The findings highlight a fundamental limitation in current LLM architectures: the compression inherent in subword tokenization sacrifices fine-grained positional awareness. This suggests that improving character-level reasoning may require architectural changes or tokenization strategies that better preserve character boundaries for positional tasks.
• Evaluation Standard: CHARBENCH serves as a necessary tool for future research aiming to improve LLMs on "menial" but critical tasks. It moves the field beyond anecdotal examples (like "strawberry") to rigorous, large-scale statistical evaluation.
• Broader Implications: The results suggest that while prompt engineering or tool use (code interpreters) can mitigate these errors, understanding the intrinsic failure modes is essential for developing models that truly understand text structure at the character level.

The authors encourage future work to replicate these findings in other languages and scripts to determine if these tokenization trade-offs are universal or specific to English BPE tokenizers.