From Language Models over Tokens to Language Models over Characters

General response

Many reviewers suggested that our evaluation methodology, which uses a large beam as a proxy for ground truth character-level probabilities, may have some systematic bias. We will add discussion to the paper about the challenge of designing a faithful evaluation as well as the possible pitfalls in our large-beam evaluation scheme.

That being said, we agree that our evaluation can be improved. In subsequent revisions of the paper, we will seek to address this in the following ways:

• Additional baselines and comparisons:

  • Token healing for character-level probabilities: Thanks to a suggestion from reviewer DnV9, we will add a comparison between our algorithm and an algorithm based on token healing for inferring character-level probabilities.

  • Perplexity per byte: Based on the suggestion by reviewer DnV9, we will add a comparison between our method’s byte-level cross-entropy and the byte-normalized cross-entropy of a token-level language model.

  • Increased beam-width: We will further increase the beam width of the baseline model, bringing it even closer to the ground truth and reducing any potential bias in the comparison.

• Evaluation of downstream accuracy on LM reasoning benchmarks: We agree that some evaluation of the downstream effects of our approach would strengthen the paper. Therefore, we will investigate the feasibility of adding an evaluation of the downstream accuracy on one or more common LM reasoning benchmarks (e.g., HellaSWAG or GLUE). However, we do not necessarily expect to see benefits. It's possible that randomly shifting the prompt boundary to the left would be interesting. Consider an example from HellaSWAG:

  Prompt: "A man is sitting on a roof. He "
  . "is using wrap to wrap a pair of skis.",  
  2. "is ripping level tiles off.",  
  3. "is holding a rubik's cube.", 
  4. "starts pulling up roofing on a roof."
  

  We would randomly shift the prompt left, e.g., move "of. He" from the end of the prompt to the possible continuations:

  Prompt: "A man is sitting on a ro"
  1. "of. He is using wrap to wrap a pair of skis.", 
  2. "of. He is ripping level tiles off.", 
  3. "of. He is holding a rubik's cube.", 
  4. "of. He starts pulling up roofing on a roof."
  

We note, however, that we do not claim that our method must improve performance on downstream tasks, e.g., math reasoning. The purpose of our approach is to enable a character-level interface to a tokenized LM, which naturally solves the prompt boundary problem.

Reviewer 9E2G

Thank you for your review, particularly the questions!

Other Comments Or Suggestions: The paper is well-written and clear overall. However, there are a few minor issues. For example, in the section on "Key Properties of κ," the definition of strict-prefix monotonicity could be made more explicit with additional examples. Additionally, the notation in some parts of the paper is quite dense and could be simplified for better readability.

Thank you for the suggestions. We will do some editing for improving readability including examples like this will help us do that.

Questions For Authors:

1. How does the proposed method handle cases where the language model's probability mass is not concentrated around a limited set of tokenizations?

This is an excellent question. Unfortunately, if mass is not concentrated, then our beam summing estimate will be skewed. Fortunately, as the method is based on beam search, even if the beam size K is smaller than what is needed to cover the entire distribution, our method can still pick up on the more likely tokenizations. We will add some discussion about this in the revised paper.

2. What are the computational requirements for the beam summing method when dealing with very large beam sizes?

We provide time and space complexity analyses in section 3.2. The short answer is that time and space are linear in the beam size K. The primary bottleneck in using more samples is that we make up to K language model calls at each position of the character string.

3. Could the covering concept be extended to handle more complex tokenization schemes, such as those used in multilingual language models?

This sounds very interesting. What are some of the complexities that multi-lingual language models have? If you could please provide some pointers/citations, we would love to dig into your question.

General response

Many reviewers suggested that our evaluation methodology, which uses a large beam as a proxy for ground truth character-level probabilities, may have some systematic bias. We will add discussion to the paper about the challenge of designing a faithful evaluation as well as the possible pitfalls in our large-beam evaluation scheme.

That being said, we agree that our evaluation can be improved. In subsequent revisions of the paper, we will seek to address this in the following ways:

• Additional baselines and comparisons:

  • Token healing for character-level probabilities: Thanks to a suggestion from reviewer DnV9, we will add a comparison between our algorithm and an algorithm based on token healing for inferring character-level probabilities.

  • Perplexity per byte: Based on the suggestion by reviewer DnV9, we will add a comparison between our method’s byte-level cross-entropy and the byte-normalized cross-entropy of a token-level language model.

  • Increased beam-width: We will further increase the beam width of the baseline model, bringing it even closer to the ground truth and reducing any potential bias in the comparison.

• Evaluation of downstream accuracy on LM reasoning benchmarks: We agree that some evaluation of the downstream effects of our approach would strengthen the paper. Therefore, we will investigate the feasibility of adding an evaluation of the downstream accuracy on one or more common LM reasoning benchmarks (e.g., HellaSWAG or GLUE). However, we do not necessarily expect to see benefits. It's possible that randomly shifting the prompt boundary to the left would be interesting. Consider an example from HellaSWAG:

  Prompt: "A man is sitting on a roof. He "
  . "is using wrap to wrap a pair of skis.",  
  2. "is ripping level tiles off.",  
  3. "is holding a rubik's cube.", 
  4. "starts pulling up roofing on a roof."
  

  We would randomly shift the prompt left, e.g., move "of. He" from the end of the prompt to the possible continuations:

  Prompt: "A man is sitting on a ro"
  1. "of. He is using wrap to wrap a pair of skis.", 
  2. "of. He is ripping level tiles off.", 
  3. "of. He is holding a rubik's cube.", 
  4. "of. He starts pulling up roofing on a roof."
  

We note, however, that we do not claim that our method must improve performance on downstream tasks, e.g., math reasoning. The purpose of our approach is to enable a character-level interface to a tokenized LM, which naturally solves the prompt boundary problem.

Response to Reviewer DnV9

Thank you so much for your review. It has been incredibly helpful as your suggestions for additional baselines are fantastic, and we will add them (more below).

re: "bits per byte" suggestion

Thank you for this suggestion! This is a great comparison to run, and we plan to add it to our experimental evaluation.

re: a token-healing-based baseline

This is an incredibly good suggestion. Coincidentally, we used that method precisely during debugging but didn't think of adding it as a baseline. What an excellent idea - thank you!

I think the footnote corresponding to "10" in Figure 1 seems to be missing?

It will be fixed in the next revision. The text for the two footnotes in Fig 1 (i.e., 10 and 11) appear on the previous page, on lines 376–384 [left column], as footnotes labeled with the same numbers.

Re: Importance sampling

Importance sampling could be used to estimate the prefix probability (and indeed it is unbiased for that). However, it does not give an unbiased conditional prefix probability, as it requires the division of two prefix probabilities. We briefly experimented with sequential Monte Carlo but found that noncanonical token sequences were strongly overrepresented. For example, when we use it on the string "SELECT * FROM" roughly 94% of GPT-2's samples start with the token S rather than the canonical token SELECT. So, we ended up ruling it out in favor of beam search. Perhaps a more sophisticated proposal distribution would help. We suspect that it is useful to represent particles as "buckets" as we did in our pruning heuristic (starting on line 337).

It's possible that we should add something about this 'negative result' to an appendix.

General response

Many reviewers suggested that our evaluation methodology, which uses a large beam as a proxy for ground truth character-level probabilities, may have some systematic bias. We will add discussion to the paper about the challenge of designing a faithful evaluation as well as the possible pitfalls in our large-beam evaluation scheme.

That being said, we agree that our evaluation can be improved. In subsequent revisions of the paper, we will seek to address this in the following ways:

• Additional baselines and comparisons:

  • Token healing for character-level probabilities: Thanks to a suggestion from reviewer DnV9, we will add a comparison between our algorithm and an algorithm based on token healing for inferring character-level probabilities.

  • Perplexity per byte: Based on the suggestion by reviewer DnV9, we will add a comparison between our method’s byte-level cross-entropy and the byte-normalized cross-entropy of a token-level language model.

  • Increased beam-width: We will further increase the beam width of the baseline model, bringing it even closer to the ground truth and reducing any potential bias in the comparison.

• Evaluation of downstream accuracy on LM reasoning benchmarks: We agree that some evaluation of the downstream effects of our approach would strengthen the paper. Therefore, we will investigate the feasibility of adding an evaluation of the downstream accuracy on one or more common LM reasoning benchmarks (e.g., HellaSWAG or GLUE). However, we do not necessarily expect to see benefits. It's possible that randomly shifting the prompt boundary to the left would be interesting. Consider an example from HellaSWAG:

  Prompt: "A man is sitting on a roof. He "
  . "is using wrap to wrap a pair of skis.",  
  2. "is ripping level tiles off.",  
  3. "is holding a rubik's cube.", 
  4. "starts pulling up roofing on a roof."
  

  We would randomly shift the prompt left, e.g., move "of. He" from the end of the prompt to the possible continuations:

  Prompt: "A man is sitting on a ro"
  1. "of. He is using wrap to wrap a pair of skis.", 
  2. "of. He is ripping level tiles off.", 
  3. "of. He is holding a rubik's cube.", 
  4. "of. He starts pulling up roofing on a roof."
  

We note, however, that we do not claim that our method must improve performance on downstream tasks, e.g., math reasoning. The purpose of our approach is to enable a character-level interface to a tokenized LM, which naturally solves the prompt boundary problem.

Response to Reviewer zQVq

Thank you for the thoughtful review and the kind words.

Methods And Evaluation Criteria: The authors evaluated their algorithms using GPT2 and Llama 8B models on the Wikitext dataset—a reasonable choice. They measured performance using Jensen-Shannon distance between a high-budget model (treated as ground truth) and various faster approximation models. While this approach makes practical sense, it remains somewhat unsatisfying. Could the authors compare their methods against a truly exact model using full coverings, at least in small-scale settings? This would provide a more rigorous baseline for evaluation.

Unfortunately, using a truly exact model is not feasible as marginalizing over tokenization of even short strings quickly becomes infeasible. We don't think that short string comparisons of beam summing's performance would necessarily generalize to the case of longer strings. So we worry that it might be misleading.

Another option we considered was evaluating our method's ability to convert a probabilistic context-free grammar over a tokenized set of symbols into a character-level model, as it is possible to compute those probabilities in cubic time; however, it is unclear whether the results would generalize to the general LM setting. We are happy to discuss this option further in the discussion period.

General response

Many reviewers suggested that our evaluation methodology, which uses a large beam as a proxy for ground truth character-level probabilities, may have some systematic bias. We will add discussion to the paper about the challenge of designing a faithful evaluation as well as the possible pitfalls in our large-beam evaluation scheme.

That being said, we agree that our evaluation can be improved. In subsequent revisions of the paper, we will seek to address this in the following ways:

• Additional baselines and comparisons:

  • Token healing for character-level probabilities: Thanks to a suggestion from reviewer DnV9, we will add a comparison between our algorithm and an algorithm based on token healing for inferring character-level probabilities.

  • Perplexity per byte: Based on the suggestion by reviewer DnV9, we will add a comparison between our method’s byte-level cross-entropy and the byte-normalized cross-entropy of a token-level language model.

  • Increased beam-width: We will further increase the beam width of the baseline model, bringing it even closer to the ground truth and reducing any potential bias in the comparison.

• Evaluation of downstream accuracy on LM reasoning benchmarks: We agree that some evaluation of the downstream effects of our approach would strengthen the paper. Therefore, we will investigate the feasibility of adding an evaluation of the downstream accuracy on one or more common LM reasoning benchmarks (e.g., HellaSWAG or GLUE). However, we do not necessarily expect to see benefits. It's possible that randomly shifting the prompt boundary to the left would be interesting. Consider an example from HellaSWAG:

  Prompt: "A man is sitting on a roof. He "
  . "is using wrap to wrap a pair of skis.",  
  2. "is ripping level tiles off.",  
  3. "is holding a rubik's cube.", 
  4. "starts pulling up roofing on a roof."
  

  We would randomly shift the prompt left, e.g., move "of. He" from the end of the prompt to the possible continuations:

  Prompt: "A man is sitting on a ro"
  1. "of. He is using wrap to wrap a pair of skis.", 
  2. "of. He is ripping level tiles off.", 
  3. "of. He is holding a rubik's cube.", 
  4. "of. He starts pulling up roofing on a roof."
  

We note, however, that we do not claim that our method must improve performance on downstream tasks, e.g., math reasoning. The purpose of our approach is to enable a character-level interface to a tokenized LM, which naturally solves the prompt boundary problem.

Response to Reviewer us9y

Thank you for the review and constructive suggestions for improving our experimental evaluation. [We are also glad you appreciated the color coding!]

For the experiment, the ground truth in this evaluation is an approximation obtained using a very high beam size (K = 128) from the same method, it may inherit the biases or errors of that approximation. Evaluating on real-world datasets would provide stronger evidence that the method effectively resolves the prompt boundary problem in practical scenarios, rather than only on controlled benchmarks.

This is a reasonable concern: Essentially, the concern is that beam size K=64 might be really good at predicting K=128 because they systematically make the same kinds of errors. We treat K=128 as essentially ground truth, which we have not proven is the case. We will discuss this issue in the revised paper, as it is an important limitation of our experiment design. Thank you.

The evaluation is primarily conducted on a single corpus. Expanding experiments to include diverse, real-world datasets would help validate the method’s robustness and provide more practical insights into how it improves actual problem-solving.

Thanks for this suggestion! We will investigate the feasibility of adding a downstream accuracy evaluation on a common LM benchmark, e.g., HellaSWAG, GLUE. Note that we do not intend to claim that our method will necessarily improve model performance on downstream tasks (unless there are prompt boundary issues). We emphasize that enabling a character-level interface to language models is valuable in its own right—for instance, when measuring character-level surprise for psycholinguistic experiments (Giulianelli et al., 2024) or handling tasks that inherently require fine-grained character-level control.

The evaluation is evaluated against the same method but with higher beam search K, this may introduce bias.

Great point. Please see the general response.