acceptodds
Under review as a conference paper at ICLR 2027

Learning to Retokenize: Improving Downstream Performance of Frozen Language Models

Abstract

Language modelling in LLMs begins with tokenization: splitting the input string into tokens drawn from a fixed vocabulary according to predefined rules. Because the tokenizer is trained on a generic corpus before model pre-training and is not tailored to any downstream task, its tokenization strategy can be ill-suited to certain domains or tasks, hindering performance. Adapting tokenization per task could help, but retraining the tokenizer on a new corpus likely changes the vocabulary and requires model adaptation, which is costly in general and infeasible for closed-weight models. A tokenizer that reuses the original vocabulary, however, could be applied to the model seamlessly. In this work, we explore training a task-specific tokenizer that is constrained to the original vocabulary of a given pre-trained LLM. To this end, we propose the retokenizer, a sequence-to-sequence model that maps an input token sequence to a new one within the original vocabulary, while preserving the underlying string content. During training, our retokenizer learns from a task-specific reward and only requires black-box access to the language model, making the approach suitable for closed-weight models. Across arithmetic, character manipulation, and code understanding tasks, our learned retokenization improves accuracy over the default tokenization by 10% on average. Moreover, we show that in some settings the retokenizer uncovers intuitive task-dependent tokenization rules, such as right-to-left digit tokenization for arithmetic. These learned rules suggest that, given the right objective, effective tokenization strategies can be discovered automatically rather than designed by hand.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Tokenization, Adaptive tokenization, Language models, Reinforcement learning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_1wqeOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduced a novel way to solve some known weaknesses (e.g., multi-digit arithmetic, character counting, etc.) of LLMs and attribute the cause to the unsuitable way of tokenization considering the nature tasks. To address the limitation, the authors propose a learnable decoder-only transformer as a retokenizer, which takes the canonical tokenization given an string as input and generates a better valid tokenization, aiming for a better downstream performance. Since all valid tokenizations are simply different combinations of existing tokens in the vocabulary that the model has seen during training, the authors claim that they solution is free of re-training or finetuning the LLM itself for adapting the learned retokenization. Empirically, this method is consistently better than the canonical tokenization, which suggests that a learned retokenization is superior than the general task-agnostic tokenization for LLMs on specific tasks. The authors also show that their learned retokenizations are generally shorter compared with other non-learned alternatives while achieving a better accuracy comparatively.

Critical strengths
  • This paper revisits the idea of tokenization and proposes a learnable retokenizer to improve LLMs performance on certain tasks, such as multi-digit arithmetic and character counting.
  • Compared with canonical and task-agnostic tokenization, this method shows a significant performance boost in Table 1, demonstrating its effectiveness on certain tasks that need a careful redesign of the tokenization.
  • Retokenization does not require tuning the LLM itself. Since valid tokenizations are re-combinations of existing tokens in the vocabulary, the LLM can still comprehend the input even without extra finetuning.
Critical weaknesses
  • Retokenizer is LLM- and task-dependent. Given a combination of a new LLM and a new task, retraining a retokenizer, according to my understanding based on the paper (Section 3.2), is necessary.
  • It seems that tasks that are unsuitable for canonical tokenization, like multi-digit arithmetic and character counting, have been successfully solved by LLMs with thinking capability or with tool-using access (e.g., a Python interpreter).
  • The retokenizer itself is a transformer, which may potentially introduce a huge overhead when the context increases and affect throughput and latency.
  • Reusing a token in the vocabulary may still be at risk of introducing unrelated semantics into the context that may affect the LLM's understanding of the original task itself. In other words, string consistency does not always guarantee semantic consistency.
Questions for authors
  • Is it possible to learn a transferable retokenizer that works for all tasks that can potentially benefit from retokenization?
  • What are some advantages of the proposed method compared with LLMs with CoT reasoning capability and tool-using capability?
  • What is the overhead and throughput with the retokenizer, and how does it perform with increasing length of input?
1 comment

Thank you for your careful review and for highlighting the strengths of our approach. We address your questions and concerns below.

[W1,Q1] Transferring across tasks and models In the paper, we train a separate retokenizer for each model-task pair, but we now also investigate transfer across models and tasks. For models with different vocabularies, direct transfer is not possible because our method keeps the vocabulary fixed. Even when models share a vocabulary, transfer does not necessarily preserve the best performance. As shown in Fig. 12 in the updated App., transferring retokenizers between Llama 3B and 8B, in most cases, does improve the performance over canonical tokenization but does not match a retokenizer trained for the target model directly, as the effective tokenization depends on the internals and capabilities of the base model.

For transfer across tasks, we first note that some similarity between the training and target tasks is needed to expect generalization. As discussed in our responses to other reviewers, we investigate this through prompt perturbations and length generalization in arithmetic (Figs. 9 and 10). We also highlight that a separate retokenizer does not need to be trained for every task. In Fig. 13, we show that a single retokenizer jointly trained on multiple tasks achieves performance comparable to individually trained retokenizers on each task, although it requires more training iterations.

[W2,Q2] Comparison with reasoning and tool use We do not view our approach as a replacement for CoT reasoning / tool use or superior to them. Rather, we see retokenization as an orthogonal approach. Our goal is to provide a method for improving the use of any general pretrained model's existing capabilities, when they are hindered by tokenization, regardless of whether the base model supports CoT or tool use and regardless of our knowledge of the model internals. Moreover, leveraging CoT capabilities may require collecting or generating task-specific reasoning traces for training, which is not always readily available. Our approach instead uses task examples and generated answers to optimize tokenization directly, without requiring access to reasoning traces or changes to the base model.

[W3,Q3] Inference cost: We have added an inference cost analysis to the App. (Table 3), measuring retokenization latency and end-to-end throughput for Llama 8B on the arithmetic, acronym, and coding tasks.

As expected, the autoregressive retokenizer introduces additional latency compared to canonical tokenization, with the overhead increasing for longer inputs. However, its impact on end-to-end throughput varies across tasks.

For coding, where accuracy increases 25%, throughput decreases by 65% compared to canonical tokenization. However, we note that the learned retokenizer still achieves higher throughput than char-level tokenization, the hand-designed alternative with similar task performance but significantly lower tokenization latency.

For the shorter acronym inputs, the throughput reduction is more modest, at 15%. Interestingly, for arithmetic, throughput actually increases by 42%. This is because, for a small subset of expressions, canonical tokenization leads the model to generate unnecessarily long answers without reaching a solution, a behavior that we do not observe with learned retokenization.

Finally, coding is a particularly demanding case for measuring the overhead, since the LLM generates only a single token. For tasks requiring longer generations, we expect the cost of autoregressive generation with a multi-billion-parameter LLM to dominate the cost of the shallow neural retokenizer, reducing its relative impact on throughput.

[W4] Semantic consistency of alternative tokenizations We agree that preserving the input string does not guarantee that the model interprets its semantics in the same way under different tokenizations. However, there are two important considerations. First, our task-specific reward directly evaluates the effect of each tokenization on downstream performance. Tokenizations that introduce misleading associations or otherwise hurt the model's understanding of the task are therefore less likely to be selected during training. This also applies to canonical tokenization, which is not necessarily optimal or semantically consistent with the task objective. Second, our method only changes how the input string is segmented into existing vocabulary tokens. It does not introduce arbitrary tokens from the vocabulary unrelated to the input. Thus, while alternative segmentations can change how the model processes the input, they remain grounded in the original text.

Thank you again for your careful feedback. We hope our responses and additional experiments have addressed your concerns. We would be happy to discuss any remaining points further.

Reviewer_EeYJOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper tackles the problem of adapting input tokenization to a downstream task when the language model, vocabulary, and input text must remain fixed. A model’s default segmentation may be ill-suited for a task, while manually choosing better splits requires task- and model-specific rules (e.g. R2L in arithmetic). The authors train a small transformer to produce alternative segmentations using reinforcement learning with rewards based on the correctness of answers arising from different valid tokenizations of the input. They train a separate retokenizer for each task and model, and report higher accuracy than canonical tokenization in most tested settings on held-out examples from arithmetic, character manipulation, and multiple-choice code description datasets.

Critical strengths
  1. The proposed approach is compelling. Given the problem setting, learning the tokenization that performs well for a given task and/or model seems more compelling than hand-defining tokenization rules. The method uses labeled examples and generated answers, without requiring the model’s weights, gradients, or likelihoods. It can therefore work with closed-weight models, provided their interfaces accept token IDs.

  2. The retokenizer improves accuracy over canonical tokenization in 32 of 36 tested settings, across several models. The comparisons with random tokenization, character splitting, and other baselines suggest that the learned splits help beyond simply making the input longer. These are encouraging results within the distributions used for evaluation.

Critical weaknesses
  1. The paper understates how much of this idea has already been studied. In Hiraoka et al. (2021), the authors train a tokenizer using losses from an already trained, frozen model. Hiraoka and Iwakura (2023) preprint select low-loss segmentations and trains a neural tokenizer to reproduce them, restricted to the model’s vocabulary. This paper cites the 2020 joint-training work but not these follow-ups. Its use of answer-based RL and generative LLMs is a useful difference, but learning task-specific segmentation while keeping the model and vocabulary fixed is not itself new.

  2. The evaluation is narrow, even within individual tasks. Both arithmetic operands have seven digits in training and evaluation, for example. The retokenizer could learn fixed split positions without learning a grouping rule that works for other lengths / number of digits. Since each task and model needs a separately trained retokenizer, it would be good to evaluate robustness against (small) changes to the inputs. The gains on held-out examples are useful, but evaluating slightly out-of-distribution performance would make the contribution more convincing.

  3. Some of the gains may come from retokenizing the repeated instructions. In Figure 6, the retokenizer splits words in the instruction, including “sequence,” as well as the acronym itself. The authors do not test these changes separately. If retokenizing the fixed instruction accounts for most of the gain, the model may mainly be learning a better segmentation of that prompt rather than how to split each new acronym. This would still help accuracy, but would change what we conclude about the learned behavior.

Questions for authors
  1. How does the method relate to the frozen-model experiments in Hiraoka et al. (2021), Section 4, and the Hiraoka and Iwakura (2023) preprint? Is the main contribution the use of generated-answer rewards and generative LLMs, or is there another methodological difference I have missed?

  2. Could you test the arithmetic retokenizer on different operand lengths, including unequal lengths, without retraining? Does it still use the grouping rules observed for seven-digit operands, and do the gains persist?

  3. For acronym generation, could you compare retokenizing only the repeated instruction, only the acronym, and both? Keeping one part canonically tokenized would help show which changes account for the gain. A similar experiment could separate the fixed question from the code and answer choices in code description.

6 comments

Thank you for your careful reading and helpful feedback. We answer your questions below.

[W1,Q1] Hiraoka et al. Thanks for bringing these works to our attention. We added them to Sec. 5. We do not claim to be the first to study alternative tokenizations with a frozen model. Rather, our contribution is our approach to learning these tokenizations. As you note, Hiraoka and Iwakura (2023) is the closest to our setting; however, they train their neural tokenizer with supervised learning, using low-loss tokenizations as target labels, whereas we take an RL approach.

There are also other differences. First, their method requires access to the model's logits to select target labels, as they rely on computing the loss. Second, they sample candidate tokenizations using randomizations of the original tokenizer, such as BPE-dropout, which limits the candidate space. For example, BPE-dropout cannot produce R2L tokenizations. In contrast, our method starts learning from random valid tokenizations and progressively focuses on more effective ones. Finally, their downstream models are trained with subword regularization and have therefore already been exposed to non-canonical tokenizations during training.

Their experiments also focus on NLP classification with smaller-scale models. So, we adapt their method to our arithmetic and acronym tasks with Llama 8B: we replace their loss-based selection with reward-based selection to match our model access requirement, and we consider both BPE-dropout and uniform sampling for candidate generation. With a matched number of LLM calls, using BPE-dropout, accuracy remains close to canonical tokenization. Uniform sampling improves arithmetic accuracy by $\sim$10%, but still remains well below our method. For acronyms, uniform sampling provides no meaningful improvement, likely because the tokenization space is much larger. Varying the tokenizer size from 1M to 100M parameters also has little effect.

The differences we noted above largely hold for the earlier work of Hiraoka et al. (2021, Sec. 4). The main additional difference is the tokenizer itself. Their neural tokenizer is a unigram language model, where token probabilities are independent of the context they appear in.

[W2,Q2] Length generalization: We conducted additional experiments on the arithmetic task with the Llama 8B model, evaluating the retokenizer on arithmetic expressions with operand lengths beyond the 7-digit expressions used during training. We considered two settings: 1) both operands have equal length, varying from 4 to 14 digits, and 2) the first operand is fixed at 7 digits, while the second varies from 4 to 14 digits (Fig. 10 in the updated App.).

We find that generalization depends on both the retokenizer architecture and the training set diversity. With the decoder-only architecture used in the paper, performance is noticeably worse than canonical tokenization on all out-of-distribution data. But by just switching to an encoder-decoder architecture, we achieve (partial) length generalization, improving performance close to R2L when the operand lengths differ by a multiple of 3.

We next expanded the training set to include equal-length operands of 7 to 9 digits. This improves generalization across equal-length expressions, although a gap with R2L remains and optimization becomes more difficult, as discussed in the appendix.

Together, these results highlight the importance of training set diversity and architecture for generalization. Extending this investigation to a broader range of prompt variations and tasks, along with developing optimization techniques for more stable and effective training, remains an interesting direction for future work.

[W3,Q3] Scope of retokenization For the acronym and coding tasks with Llama 8B model, we retrain the retokenizer in two settings: 1) retokenizing only the acronym or code snippet, and 2) retokenizing the rest of the input (including the multiple-choice answers for the coding task) (Fig. 11 in the App).

We observe different behaviors across the two tasks. For the acronym task, where the acronyms are likely rarely or never seen during training, almost all the performance improvement comes from retokenizing the acronym itself, while retokenizing the prompt has little effect. For the coding task, both settings improve over canonical tokenization, but the majority of the improvement comes from retokenizing the multiple-choice answers. We see this as another interesting future direction: to develop a systematic way to identify, based on model performance, which parts of the input would benefit from retokenization before training the retokenizer. This could make the retokenization process more targeted and reduce the training required.

Thank you again for your careful feedback. We hope our responses and the additional experiments have addressed your concerns. We would be happy to discuss any remaining points further.

Thank you for the detailed response and additional experiments. My concerns on W/Q1 and W/Q3 have been resolved.

On W/Q2: The length-generalization results are mixed. The original decoder-only retokenizer performs worse than canonical tokenization on OOD arithmetic expressions, while the encoder–decoder variant shows partial generalization. This suggests to me that, even with a more expressive architecture, the retokenizer may be learning patterns specific to the training distribution rather than reusable tokenization strategies, even within the same task.

It would be useful to examine the learned tokenizations on OOD arithmetic expressions (e.g., their agreement with R2L across operand lengths) to better understand the generalization failures. I would be happy to raise my score if there is stronger evidence that the learned strategies generalize beyond the training format.

[W2,Q2] Thanks for your follow-up.

Following your suggestion, we revisited the mixed-digit experiment in the equal-length setup, where the encoder-decoder retokenizer is trained jointly on operands of 7, 8, and 9 digits, and examined the learned tokenizations directly on expressions with 4 to 14 digits (new Figure 14 in the App.).

First, regarding mixed-digit training, we find that the remaining gap to R2L accuracy in this setting was simply an optimization issue. As briefly discussed in the appendix, entropy regularization is needed in this setting to help the retokenizer escape suboptimal tokenizations that it gets stuck in early in training. However, keeping entropy regularization on throughout training makes the policy less confident in R2L. We find that a stepwise schedule that decreases entropy regularization later in the training allows the retokenizer to commit to R2L and noticeably closes the accuracy gap. We have updated the green curve in the left panel of Fig. 10 accordingly.

We also measure the percentage of test expressions with 4 to 14 digits for which the learned tokenization matches R2L tokenization (Fig. 14). The agreement is roughly 90% at every length, including OOD lengths not seen during training.

We perform the same analysis for the decoder-only and encoder-decoder retokenizers trained only on 7-digit expressions as well. The decoder-only retokenizer applies R2L only at 7 digits, the length seen during training, and thus does not learn a generalizable pattern. The encoder-decoder retokenizer, however, agrees with R2L at lengths that are 1 modulo 3 (4, 10, and 13 digits) not seen at training time. We find this partial generalization noteworthy for two reasons: (1) the decoder-only architecture cannot learn it, and (2) as the operand lengths change, the starting position of the second operand also shifts, but the retokenizer still learns to place the split positions in both operands correctly. However, due to the limited diversity of the training set, it does not learn a strategy that works across all equal-length expressions. The mixed-digit experiment addresses this by increasing training diversity, which allows the retokenizer to handle a much wider range of OOD expressions effectively.

Overall, these experiments show that OOD generalization is possible, but requires an appropriate choice of retokenizer architecture and a sufficiently diverse training set for the task of interest. As discussed above, changing each of these factors progressively extends the range of OOD lengths over which the retokenizer does well.

We hope these results help address your concerns about generalization.

Reviewer_3d6VOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper introduces what they call a retokenizer: essentially a new tokenizer that takes the vocabulary of an old tokenizer and relearns the segmentation rules, optimizing those rules jointly with a base model for a downstream use case (using RL). The main appeal is that the tokenizer can be adjusted for a specific task without replacing the vocabulary (and therefore embedding parameters) of a base model. This should make it much more efficient than previous tokenizer adaptation strategies. On the tasks that the paper explores, they see improvements in downstream performance when using this customized tokenizer.

Critical strengths

This needs to be said first: thank you for writing a clear paper...

  • The idea is elegant and intuitive.
  • While the set of tasks is somewhat narrow (I realize the focus is intentionally "on tasks where prior work has shown tokenization to affect performance"), the observed improvements are notable
  • The baselines feel thoughtfully chosen. Both the hand designed and the compute matched tokenizations provide valuable comparisons that rule out confounding factors as the source of improvements
Critical weaknesses
  • The set of tasks explored/in which we see improvements is narrow, which raises two questions: how useful the method actually is beyond this narrow set of use cases and whether the method might actually be harmful in certain situations. Things like prompt boundaries and prompt segmentation would also be changed during this optimization procedure. For the consistently formatted tasks, performance on the test set (where that format of the prompt matches what's been seen during training) improves. But if something small changes in the prompt or if its a slightly different task, do we see performance harm?
  • Several aspects of the computational cost of the method are not well quantified or discussed. Deterministic string encoding by a standard tokenizer is quite fast, but that's now being replaced by a small neural model. What's the added cost of that model? Generally, how much training data is needed to properly learn the retokenization?
  • A very related work that also "keep[s] both the model and its vocabulary fixed, and only change[s] how the input string is split into tokens using the existing vocabulary" was not discussed/compared against (LangMAP: A Language-Adaptive Approach to Tokenization)
Questions for authors
  • What is the added overhead of this tokenization strategy at inference time (literally text encoding, not just increased token counts)?
  • I would like to see an analysis comparing fine-tuning with the base tokenizer vs. fine-tuning with the retokenizer method. At what amount of compute/data do we see the retokenizer method start to outperform the model trained with the base tokenizer?
2 comments

Thanks for your review and for highlighting the strengths of our work. We address your comments below.

[W1] Small changes in the test prompt/task We test robustness to prompt perturbations and generalization beyond the training tasks in two settings:

First, for three task-model pairs, we randomly remove spaces from test prompts to introduce small perturbations (Fig. 9 in the updated App.). Although this can hurt both canonical and learned tokenization performance, the learned retokenizer still outperforms canonical tokenization.

Second, for arithmetic with the Llama 8B model, we test generalization beyond the 7-digit expressions seen during training, in two cases: 1) both operands have equal length, from 4 to 14 digits, and 2) the first operand is fixed at 7 digits, while the second varies from 4 to 14 digits (Fig. 10).

We find that generalization depends on both the retokenizer architecture and the training set diversity. With the decoder-only architecture, performance is noticeably worse than canonical tokenization on all out-of-distribution data. But by just switching to an encoder-decoder architecture, we achieve (partial) length generalization, improving performance when the operand lengths differ by a multiple of 3.

We next expand the training set to include equal-length operands of 7 to 9 digits. This improves generalization across equal-length expressions, although a gap with R2L remains and optimization becomes more difficult, as discussed in the App.

Together, these results highlight the role of training set diversity and architecture for generalization. Extending this investigation to a broader range of prompt variations and tasks, along with developing optimization techniques for more effective training and generalization, remains an interesting direction for future work.

[W2,Q1] Inference cost We have added an inference cost analysis to the App. (Table 3), measuring retokenization latency and end-to-end throughput for Llama 8B on the arithmetic, acronym, and coding tasks.

As expected, the autoregressive retokenizer introduces additional latency compared to canonical tokenization, with the overhead increasing for longer inputs. However, its impact on end-to-end throughput varies across tasks.

For coding, where accuracy increases 25%, throughput decreases by 65% compared to canonical tokenization. However, we note that the learned retokenizer still achieves higher throughput than char-level tokenization, the hand-designed alternative with similar task performance but significantly lower tokenization latency.

For the shorter acronym inputs, the throughput reduction is more modest, at 15%. Interestingly, for arithmetic, throughput actually increases by 42%. This is because, for a small subset of expressions, canonical tokenization leads the model to generate unnecessarily long answers without reaching a solution, a behavior that we do not observe with learned retokenization.

Finally, coding is a particularly demanding case for measuring the overhead, since the LLM generates only a single token. For tasks requiring longer generations, we expect the cost of autoregressive generation with a multi-billion-parameter LLM to dominate the cost of the shallow neural retokenizer, reducing its relative impact on throughput.

[W2,Q2] Fine-tuning: We would like to first reiterate that our goal is to study how pretrained models can be improved without modifying their parameters or requiring access to their internal computations. This is particularly relevant as increasingly capable models become less accessible for fine-tuning. We do not aim to compete with fine-tuning, which has been extensively studied in the literature, with many effective approaches for improving arithmetic and character-level reasoning. For instance, LoRA fine-tuning on Llama 3B for the arithmetic task, with the same training set size and a comparable number of trainable parameters as our retokenizer, achieves approximately 82% accuracy after 5 epochs, exceeding both R2L and our method (76%). But we view these as complementary approaches, and we consider our results as evidence that relying on a predefined canonical tokenization downgrades the model's capabilities.

[W3] LangMap: Thanks for bringing this paper to our attention. We added it to Sec. 5. While both methods explore alternative tokenizations under a fixed vocabulary, they differ in how they obtain the tokenization: LangMAP uses language-specific unigram distributions, whereas we take an RL-based approach. Moreover, although the tokenizer itself can be defined independently of the model parameters, the authors note in footnote 11 that fine-tuning the base model with the adapted tokenizer is needed to obtain performance improvements. In contrast, our method requires no access to the model's gradients.

Thank you again for your careful suggestions and for your positive assessment of our work. We would be happy to discuss any unresolved points further.

Thanks for the careful response and additional analyses. I'm maintaining my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.