acceptodds
Under review as a conference paper at ICLR 2027

Rethinking Tokenization for Discrete Diffusion Language Models

Abstract

Discrete diffusion models offer a potential speed advantage over autoregressive models by generating multiple tokens per denoising step. However, parallel decoding samples each position independently within a denoising step. This ignores the dependence between tokens generated in the same step. This discrepancy, known as factorization error, grows as more tokens are decoded in parallel. Prior work has sought to reduce this error through sampling schedules or auxiliary models, but these approaches address which tokens are generated together without changing the tokens themselves. We instead investigate tokenization itself as a design choice that shapes this error. Discrete diffusion models commonly inherit tokenizers designed for autoregressive models, despite token boundaries determining which dependencies remain between independently predicted outputs. Lossless tokenizers sharing vocabulary size and per-example encoded lengths achieve the same oracle denoising loss, yet they can incur different factorization errors under parallel sampling. We decompose this error exactly by interaction order, separating schedule-determined weights from tokenizer-determined interactions. This decomposition clarifies when pairwise dependence suffices for comparing tokenizers and when higher-order interactions alter the ranking. We compare BPE, WordPiece, Unigram, and a weighted pointwise mutual information (WPMI) merge criterion motivated by the adjacent pairwise component in this decomposition. Experiments on LM1B and OpenWebText show that tokenizers with similar compression and prediction loss can diverge in generation quality as the number of denoising steps decreases. Our findings suggest that tokenizer selection, commonly inherited from autoregressive language-modeling pipelines, may need to be rethought for discrete diffusion language models.

Primary area:
generative models
Keywords:
Discrete diffusion

Reviews

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

This paper proposes a vocabulary construction criterion, weighted pointwise mutual information (WPMI), to reduce the factorization error, the discrepancy between the token joint distributions of normal sampling and parallel sampling (the discrete diffusion model). To achieve that, they theoretically investigate tokenization itself as a cause of this error and decompose the error by interaction order, separating schedule-induced weights from tokenizer-induced interactions. From the analysis, they conclude that the factorization error can be expressed, in all orders, as the sum of schedule-dependent coefficients and tokenization-dependent interactions. Furthermore, they derive that the difference in the “conditional dependence response,” a value that quantifies how the dependence between a pair of tokens changes when observing other tokens, must be sufficiently small compared to the difference in the “pairwise dependence,” which quantifies the statistical dependence itself between the two tokens. They turn this observation into a tokenization-based manner and propose WPMI, which not only evaluates the relevance between pairs of tokens but also considers how frequently that combination occurs within the corpus. There are empirical experiments done to show that (1) even among tokenizers with similar compression rates and predicted loss, the quality of the generated output can vary significantly under parallel generation, and that (2) the WPMI tokenizer particularly improves generation quality with a small number of denoising steps.

Critical strengths
  1. Rigorous theoretical analyses. The paper precisely defines the factorization error in the discrete diffusion model, separating it into schedule-induced interaction and tokenizer-induced weight. In addition to the analysis, the paper carefully proposes the WPMI to apply its theoretical insights to the practical problem setting.
  2. Clear demonstration. Figure 1 helps to understand the limitations of ordinary tokenizers and the approach of WPMI.
  3. Experimental results. The paper first investigates whether compression and prediction quality depend on tokenization variation, indicating that WPMI achieves the same performance comparable to other tokenizers. On OWT, the fewer denoising steps KK there are, the lower the perplexity WPMI achieves.
Critical weaknesses
  1. Unclear problem setting. The paper's claim, "focusing on the fact that factorization errors change when the tokenizer changes, we analyzed the tokenizer itself as a primary cause of the error," seems misleading or insufficient as a rationale for the problem setting in an academic paper. The fact that factorization errors vary across tokenizers is just an insight that inspired the proposed method (WPMI). Nowhere is there a clear explanation of why the authors chose tokenizers as the subject of their analysis.
  2. Insufficient justification of theory. The theoretical analyses are overall logical and well-organized, but there is insufficient justification for why that analytical process or assumption is valid.
Questions for authors
  1. Could you explain why you chose tokenizers as the subject of your analysis? The fact that factorization errors vary across tokenizers is an insight that inspired the proposed method (WPMI). Isn't the actual flow of your research as follows?
  • Noting that general discrete diffusion models directly adopt the same tokenizers used in autoregressive models, thereby giving rise to tokenizer-induced factorization errors.
  • Theoretically demonstrating the mechanism by which factorization errors arise from the tokenizer (i.e., the combinations of paired text).
  • Proposing a method to construct tokenizers for discrete diffusion models that can mitigate factorization errors.
  1. In line 183, what does “reconstruction information” mean?
  2. In Proposition 1, is encoded-length entropy the only type of entropy we need to consider? If so, please provide clear proof.
  3. In Section 4.2, why do you only use the second-order component in Equation (8)? Are other higher-order components negligible?
4 comments
AuthorsOpenReview ↗

Author Rebuttal (1/2)

We greatly appreciate the reviewer's thoughtful feedback and careful examination of our work. The comments have helped us better articulate our research motivation, clarify the theoretical assumptions, and strengthen the overall presentation of our analysis. We address each point in detail below.

W1 & Q1 Unclear problem setting. Explain why chose tokenizers as the subject of analysis?

Thank you for pointing out how we could make our problem setting clearer. We agree with the research progression suggested by the reviewer. Our motivation stems from the mismatch between tokenizers commonly inherited from autoregressive models and the independent parallel decoding mechanism of discrete diffusion language models.

The original Introduction discusses inherited tokenizers and the role of token boundaries (Lines 51–53 and 80–84 of the original submission). However, we recognize that the connection between this motivation, our theoretical analysis, and the resulting WPMI criterion was not sufficiently explicit.

To clarify the connection between our motivation, theoretical analysis, and proposed WPMI criterion, we have made the following revisions:

  • Abstract: We revised the motivation to explicitly highlight the mismatch between inherited tokenizers and parallel decoding:

Discrete diffusion models commonly inherit tokenizers designed for autoregressive models, without explicitly considering the dependencies exposed by independent parallel decoding. Since token boundaries determine which dependencies remain across independently predicted positions, we investigate how inherited tokenizer designs shape factorization error in discrete diffusion models.

  • Introduction: We added a sentence to clarify why we focus on tokenization:

This mismatch between inherited tokenizer design and independent parallel decoding motivates us to examine tokenization as a separate design variable.

  • Section 3.1: We clarified the purpose of our initial theoretical analysis:

We first establish that lossless tokenizers with matched encoded lengths share the same oracle denoising loss. This allows us to isolate tokenizer-dependent factorization error arising from independent parallel sampling.

  • Conclusion: We reinforced the original motivation:

Motivated by the use of autoregressive-model tokenizers in discrete diffusion language models, we study tokenization as a design variable that shapes the dependencies exposed to independent parallel sampling.

We sincerely appreciate the reviewer's suggestion, which helped us make the motivation and overall research progression more explicit throughout the manuscript.

W2 Insufficient justification of theory. What justifies the theoretical analysis and its underlying assumptions?

Thank you for this comment. We agree that the manuscript should make the reasons for its assumptions and analytical choices more explicit. We clarify the following points and connect them to the existing derivations:

  • Deterministic and lossless tokenization. These assumptions are necessary to isolate tokenizer-dependent factorization error from stochastic segmentation and information loss, ensuring H(Zτ)=H(X)H(Z^\tau)=H(X). They are also valid in our experimental setting, as all four tokenizers use deterministic segmentation and reversible byte-level encoding. We have clarified these implementation details in Appendix D.1 of the revised paper (L1124–1127).

  • Why analyze an oracle denoiser? The oracle setting isolates structural factorization error from model-fitting error, rather than assuming that trained models are perfect. Appendix A.3 justifies this through an exact decomposition of the learned sampling-process KL into factorization, length-model, and conditional-prediction errors. With exact conditionals and the true length distribution, only factorization error remains. Our response to Reviewer VLrQ, W2-1 reports complementary measurements on empirical and synthetic distributions without learned-model predictions.

  • Why match per-example encoded lengths? This assumption ensures a common conditional source and identical sampling geometry across tokenizers, allowing us to isolate tokenizer-dependent interactions from differences in sequence lengths and schedule weights. We clarify in Section 4 that this is a controlled theoretical setting, rather than an assumption about practical tokenizers (L233–238).

  • Why use pairwise dependence? Theorem 3 identifies S2S_2 as the pairwise component of the exact factorization-error decomposition, while Proposition 4 characterizes when its ranking agrees with the full error despite higher-order interactions. We use pairwise dependence as a tractable and interpretable signal for lexical construction, rather than assuming that higher-order effects are negligible. Please see our response to Q4 for further discussion.

(continued in the next comment)

AuthorsOpenReview ↗

Author Rebuttal (2/2)

  • Why restrict to adjacent pairs? As discussed in Section 5.1, a standard lexical merge combines two contiguous pieces into a single substring token. Adjacency therefore follows from the feasible construction action, rather than an assumption that nonadjacent dependencies are small. We stated this distinction explicitly. Please see our response to Reviewer VLrQ, W1 for distance-wise MI analyses on OWT and LM1B and their limitations, with the detailed setup and curves in Section 5.1(L315-319) and Appendix E.2.

  • Why pool occurrences and use count-weighted PMI? We seek one reusable score per lexical pair type, shared across positions and examples. In the corresponding shared-prediction problem, each pair type contributes exactly its occurrence count times PMI to the optimal joint-versus-independent prediction-loss gap. We connected this local derivation explicitly to the pooling choice in Section 5.1 and Appendix C.1. Please see our response to Reviewer 7YE2, Q2 for the distinction between pooled and indexed MI and the additional preprocessing comparison.

We also connect the WPMI score to the realized one-step merge effect in Section 5.1, Proposition 5, with the detailed derivation in Appendix C.2.

Q2 In line 183, what does “reconstruction information” mean?

Thank you for carefully pointing out this ambiguity. By “reconstruction information,” we meant H(Zτ∣Nτ)H(Z^\tau\mid N_\tau), the uncertainty of the clean token sequence given its encoded length, which equals the optimal value of the full-noise, sequence-summed denoising objective in Proposition 1. However, we agree that this term was imprecise and could obscure the main purpose of Section 3.1.

To clarify, we have revised Lines L185–187 as follows:

We first establish that lossless tokenizers with matched encoded lengths share the same oracle denoising loss. This allows us to isolate tokenizer-dependent factorization error arising from independent parallel sampling.

Q3 In Proposition 1, is encoded-length entropy the only type of entropy we need to consider? If so, please provide clear proof.

Thank you for this question. Under the deterministic and lossless tokenization assumptions in Section 2.1, encoded-length entropy is the only additional correction needed to recover the source entropy from the oracle denoising objective.

\mathcal L^*_{\mathrm{MDM}}(\tau)= H(Z^\tau \mid N_\tau) \= H(X) + H(Z^\tau \mid X) - H(X \mid Z^\tau) - H(N_\tau). H(Zτ∣X)H(Z^\tau\mid X) captures stochastic encoding uncertainty, while H(X∣Zτ)H(X\mid Z^\tau) captures information lost during encoding. The former vanishes for deterministic tokenization, and the latter vanishes for lossless tokenization, leaving only H(Nτ)H(N_\tau). The remaining step is to establish LMDM∗(τ)=H(Zτ∣Nτ)\mathcal{L}^{\ast}_{\mathrm{MDM}}(\tau)=H(Z^{\tau}\mid N_{\tau}). At each fixed encoded length nn, the oracle conditional loss and integrated masking weights yield the entropy chain rule averaged over uniform permutations, giving H(Zτ∣Nτ=n)H(Z^{\tau}\mid N_{\tau}=n). Averaging over the encoded-length distribution then gives LMDM∗(τ)=H(Zτ∣Nτ)\mathcal{L}^{\ast}_{\mathrm{MDM}}(\tau)=H(Z^{\tau}\mid N_{\tau}).

We have expanded the proof in Appendix A.2 to make the permutation-based entropy derivation explicit and clarify the role of deterministic and lossless tokenization.

Q4 In Section 4.2, why do you only use the second-order component in Equation (8)? Are other higher-order components negligible?

We do not assume that higher-order components are negligible. Theorem 3 is an exact decomposition that retains all interaction orders, and Proposition 4 explicitly accounts for higher-order effects through the normalized conditional-dependence response. In particular, ϵb\epsilon_b measures the discrepancy between the normalized responses of two tokenizers, capturing differences in their higher-order dependence structures. Appendix B.3 further illustrates this with two examples where higher-order interactions are essential.

We focus on S2S_2 because pairwise dependence provides a tractable and interpretable signal for constructing a tokenizer through adjacent merges, rather than because higher-order terms can be ignored. Proposition 4 characterizes when the ranking induced by S2S_2 is preserved for the full factorization error. The further restriction to adjacent pairs in WPMI is a practical construction heuristic, not an exact minimization of the full error. For direct empirical validation of the full factorization error, please see our response to Reviewer VLrQ W2-1.

I sincerely thank the authors for their careful response. The answers clarify their motivation, theoretical justification, and previously unclear variables, addressing my initial concerns. The revised manuscript is also welcome. I acknowledge its theoretical contributions. I've been researching language models but am not an expert on DLMs. Therefore, I maintain my score of 3, although I found this paper valuable.

We thank the reviewer for their thoughtful feedback and positive assessment of our work. We are glad that our clarifications and revisions have addressed the reviewer's initial concerns and helped highlight the theoretical contributions of our paper. We also appreciate the reviewer’s recognition of the value of our work.

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

This work provides an analysis of the tokenizer effect in the factorization error in Masked Diffusion Models (MDM), which comes into play in the few step sampling regime. While the optimal continuous-time ELBO always equals the data entropy, the factorized generative model used in practice uses only a finite amount of steps. This introduces a factorization error dependent on the joint token distribution, which in turn depends on the tokenizer. The authors characterize this dependence with a mixture of aggregate order-r interaction terms, and use an order-2 approximation resolving to a mutual information term to build a new tokenizer adapted to this few step generation problem. Language modeling experiments are then developed to validate this approach.

Critical strengths
  • A novel deep analysis of the tokenizer impact on the factorization error in Masked Diffusion Models. It formalizes the intuition that mutual information on token positions is significant in measuring this error. At the best of my knowledge, it is a new analysis and this is a significant reason for recommending acceptance.
Critical weaknesses
  • The link between minimizing the S2(τ)S_2(\tau) term and WPMI's merging rule is unclear. The authors provide some explanation in Appendix C.1, but they do not show that the merging rule indeed minimizes pairwise mutual information. This link justifies the introduction of the tokenizer and, in my view, must be clearly stated in the main text, not just in the appendix. Even in the appendix, there is insufficient justification for the claim that the tokenizer's merging rule indeed reduces S2(τ)S_2(\tau) or an approximation thereof.
Questions for authors

The link between your theoretical analysis and the tokenizer merging rule is not that clear. Therefore I have several questions.

  • Your rule only considers adjacent tokens (position ii, i+1i+1) whereas the S2(τ)S_2(\tau) term aggregates all the positions i<ji < j. To what extent this difference is significant? Are the I(Zi,Zj)I(Z_i, Z_j) terms negligible when $ \mid i - j \mid \geq 2 $ ?

  • Even when considering only the adjacent positions in S2(τ)S_2(\tau), your merging rule consider the mutual information between pooled distributions across token positions, whereas S2S_2 averages them after having computed the mutual information. In other words, considering a fixed length of nn for simplicity, Zi∼piZ_i \sim p_i and (Zi,Zi+1)∼pi,i+1(Z_i, Z_{i+1}) \sim p_{i, i+1}, your rule computes the mutual information $ KL( \bar{p} \mid \mid \bar{p}_{\text{left}} \otimes \bar{p}_{\text{right}} ) $ where $ \bar{p}(u, v) = \frac{1}{n-1} \sum_{i=1}^{n-1} p_{i, i+1}(u, v) $ and pˉleft,pˉright\bar{p}_{\text{left}}, \bar{p}_{\text{right}} are the marginals. S2(τ)S_2(\tau) instead computes $ KL( p_{i, i+1} \mid \mid p_i \otimes p_{i+1}) $, and sums it over 1≤i≤n−11 \leq i \leq n-1. As you showed in the appendix, these terms are not equal. However, if pip_i and pi,i+1p_{i, i+1} do not depend on ii, then the two mutual informations are indeed the same. But what if the dataset is such that the sequences have been cropped and concatenated, without taking care of the end of document? In that case, position i would not mean anything and your merge rule would be accurate. Have you tried changing how the data is processed to see this effect?

  • Have you tried to show that one iteration of your merge rule indeed lower $ KL( \bar{p} \mid \mid \bar{p}_{\text{left}} \otimes \bar{p}_{\text{right}} ) $?

4 comments
AuthorsOpenReview ↗

Author Rebuttal (1/2)

We thank the reviewer for the thoughtful questions, which helped us clarify and strengthen the connection between our theoretical analysis and tokenizer construction.

Q1 How significant is WPMI's restriction to adjacent pairs compared with the all-pair S2(τ)S_2(\tau)? Are nonadjacent dependencies negligible?

Our restriction to adjacent pairs is motivated by the lexical merge operation, which combines contiguous tokens, rather than an assumption that nonadjacent dependencies are negligible.

To examine the significance of this restriction, we measured pairwise mutual information across token distances (d=1,…,31d=1,\ldots,31) for BPE, WordPiece, Unigram, and WPMI using 100,000 OpenWebText documents and 50,000 LM1B sentences. We averaged MI across eligible position pairs at each distance and subtracted a shuffled-correspondence baseline to mitigate finite-sample estimation bias.

OWT

DistanceBPEWordPieceUnigramWPMI
10.50300.50600.50420.5076
20.19540.19630.18680.1961
40.05440.05490.05350.0542
80.02730.02760.02610.0270
160.02010.02040.01930.0202

LM1B

DistanceBPEWordPieceUnigramWPMI
10.31170.31460.54190.3203
20.14660.14690.18270.1466
40.03960.03980.04370.0387
80.01400.01520.01340.0149
160.01150.01180.00940.0100

The results show that pairwise MI is strongest at adjacent positions and generally decreases with distance across both datasets. This supports adjacent dependence as a useful local signal, but does not imply that nonadjacent dependencies are negligible or that adjacent MI fully captures the global S2(τ)S_2(\tau).

We now present the distance-wise MI results in Section 5.1 and Figure 2, with the full experimental setup and additional discussion in Appendix E.2.

Q2 How does WPMI's pooled adjacent MI differ from the position-indexed MI in S2(τ)S_2(\tau)? Can sequence packing reduce this discrepancy?

We thank the reviewer for this valuable suggestion, which provides an opportunity to further strengthen our analysis of the relationship between indexed and pooled MI. Following the reviewer's suggestion, we conducted an additional experiment to examine how different preprocessing strategies affect their discrepancy.

We compared a baseline setting with a packed setting constructed by concatenating LM1B sentences, using the same WPMI tokenizer and 100,000 eligible LM1B test sentences. For more stable MI estimation, we selected the 128 most frequent tokens using separate training data and grouped all remaining tokens into an OTHER category. We report the mean and standard deviation across 10 random seeds.

PreprocessingAbsolute gap (Indexed MI − Pooled MI) ↓
Baseline0.0329 ± 0.0001
Packed0.0273 ± 0.0001

Packing reduced the discrepancy by 17% (0.0329 → 0.0273), supporting the reviewer's observation that preprocessing can bring pooled MI closer to indexed MI. Nevertheless, this result does not establish that indexed and pooled MI are universally equivalent. We have added the indexed–pooled MI identity and the packing results to Section 5.1 and the experimental protocol and results in Appendix E.3.

AuthorsOpenReview ↗

Author Rebuttal (2/2)

Q3. Have you tried to show that one iteration of your merge rule indeed lowers KL(pˉ∥pˉleft⊗pˉright)KL(\bar p\|\bar p_{\mathrm{left}}\otimes\bar p_{\mathrm{right}})?

We thank the reviewer for this valuable question. We show that a single WPMI merge decreases normalized pooled MI under an explicit sufficient condition.

For complete substitution of a distinct-token pair, we establish that

pmi⋆≥I+1+Γ⋆r⋆⟹I′<I\mathrm{pmi}_\star \ge I+1+\frac{\Gamma_\star}{r_\star} \Longrightarrow I' \lt I

where II and I′I' denote pooled MI before and after merging, pmi⋆\mathrm{pmi}_\star is the selected pair's pointwise mutual information, r⋆r_\star is the number of replacements, and Γ⋆≥0\Gamma_\star\ge0 captures additional contextual dependence introduced by the merge. For stationary first-order Markov sources, Γ⋆=0\Gamma_\star=0 at the population level, yielding the simpler sufficient condition pmi⋆≥I+1\mathrm{pmi}_\star\ge I+1.

Proof sketch. We decompose the one-step change into the direct effect of removing the selected pair's boundaries and the additional contextual dependence introduced by the new token. We show that the direct effect differs from the WPMI score by less than one nat per replacement, while the contextual correction is nonnegative. Accounting for the reduced number of adjacent positions yields the sufficient condition above. Under the Markov assumption, conditional independence of the surrounding context makes the contextual correction vanish at the population level.

While this does not guarantee monotonic decrease for every WPMI merge, it provides a theoretical connection between the merge criterion and actual pooled-MI reduction under explicit conditions. We now state this result as Proposition 5 in Section 5.1, together with a proof sketch and its scope; the full one-step analysis and proofs are provided in Appendix C.2.

I thank the authors for their detailed response.

I appreciate the clarifications regarding adjacent pairs, the discrepancy between indexed and pooled mutual information, and the new theoretical result connecting the WPMI merging rule to a reduction in pooled MI. These additions help strengthen the connection between the theoretical analysis and the proposed tokenizer.

While some limitations remain regarding the extent to which WPMI minimizes the full factorization error, I find the theoretical contribution interesting and valuable. I therefore maintain my score of 3.

Thank you again for the thoughtful rebuttal and the effort put into your answers.

We sincerely thank the reviewer for the thoughtful feedback and positive assessment of our theoretical contribution. Your constructive questions and suggestions have helped us further strengthen the theoretical foundations of our work. All theoretical results and additional experimental findings have been incorporated into the revised paper.

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

This paper investigates how tokenization influences the factorization error arising from independent parallel sampling in discrete diffusion language models. It provides a theoretical analysis of the tokenization-dependent error and, motivated by the analysis, adopts weighted pointwise mutual information (WPMI) as a criterion to construct a tokenizer. Experiments comparing WPMI with standard tokenizers, including BPE, WordPiece, and Unigram, show that WPMI can improve generation quality, particularly under limited budgets of decoding steps

Critical strengths
  • The factorization error of independent parallel sampling is an important issue for discrete diffusion language models. Different from prior works on sampling strategies, this paper investigates how the error is influenced by tokenization, offering a novel and interesting perspective.
  • The theoretical interpretation of tokenization-dependent factorization error is clear and well-motivated, which might inform future research
Critical weaknesses
  • While section 4.2 shows that under some conditions the aggregated mutual information of all pairs is sufficient to rank tokenizers, WPMI further restricts it to adjacent pairs only. It remains a question how well such local simplification approximates the global dependencies.
  • The empirical results are kind of limited:
    • I wonder whether the factorization error could be measured empirically for the compared tokenizers (even on some synthetic task). This would be a more direct validation of the claims made in this paper
    • Additional sample-quality metrics beyond generative ppl and entropy could make the evaluation more comprehensive (e.g., LLM-as-a-judge)
Questions for authors

Please see Weaknesses

4 comments
AuthorsOpenReview ↗

Author Rebuttal (1/2)

We sincerely thank the reviewer for the constructive feedback and valuable suggestions. The reviewer's comments motivated additional analyses and experiments that helped us strengthen both the theoretical justification and empirical validation of our work. We address each concern in detail below.

W1. How well does WPMI's adjacent-pair criterion approximate the global dependencies?

Our restriction to adjacent pairs is motivated by the lexical merge operation, which combines contiguous tokens, rather than an assumption that nonadjacent dependencies are negligible.

To examine the relationship between local and global dependencies, we measured pairwise mutual information across token distances (d=1,…,31d=1,\ldots,31) using BPE, WordPiece, Unigram, and WPMI on 100,000 OpenWebText documents** and **50,000 LM1B sentences. We report the average MI across position pairs at each distance, after subtracting the mean MI from randomly shuffled sample correspondences to account for finite-sample estimation bias. The results are reported below.

OWT

DistanceBPEWordPieceUnigramWPMI
10.50300.50600.50420.5076
20.19540.19630.18680.1961
40.05440.05490.05350.0542
80.02730.02760.02610.0270
160.02010.02040.01930.0202

LM1B

DistanceBPEWordPieceUnigramWPMI
10.31170.31460.54190.3203
20.14660.14690.18270.1466
40.03960.03980.04370.0387
80.01400.01520.01340.0149
160.01150.01180.00940.0100

As shown above, pairwise dependence is strongest at adjacent positions and generally decreases with distance across both datasets. These observations suggest that adjacent dependence provides a useful local signal for lexical merging, although they do not establish that nonadjacent dependencies are negligible or that adjacent MI fully captures the global S2(τ)S_2(\tau).

We now present the distance-wise MI results in Section 5.1 and Figure 2, with the full experimental setup and additional discussion in Appendix E.2.

W2-1 Can factorization error be measured directly across tokenizers, including on synthetic tasks, to validate the theoretical claims?

Following the reviewer's suggestion, we conducted two additional experiments to directly measure factorization error independently of learned-model predictions: (1) using empirical finite distributions constructed from OpenWebText and (2) using a synthetic task with a known probability distribution. This allows us to isolate factorization error from the model prediction error present in evaluations with trained models.

Empirical factorization error on OpenWebText. We directly measured tokenizer-dependent factorization error using finite empirical distributions constructed from OpenWebText, without relying on trained models.

Specifically, we identified raw text spans that were tokenized into exactly four tokens by all four tokenizers, ensuring identical raw inputs and per-example encoded lengths. Using 100,000 common samples, we constructed empirical joint distributions of the resulting four-token sequences and computed factorization error using Eq. (6), averaging over all six possible first-round position pairs under two-round parallel decoding (b=2b=2). The results are reported below.

TokenizerBPEWordPieceUnigramWPMI
Error ↓\downarrow3.7173.7093.6843.617

Factorization error on synthetic task. We additionally evaluated a binary Markov source with a stay probability of 0.8, using sequence lengths L∈8,12L\in{8,12}. Unlike corpus-based estimation, the complete source distribution is known, allowing exact computation of the oracle factorization error under two-token parallel decoding (b=2b=2), without model prediction or sampling-estimation errors. The results are reported below.

Sequence length \ TokenizerBPEWordPieceUnigramWPMI
L=8L=80.3690.2730.2970.253
L=12L=120.4060.3120.4690.308

In both experiments, WPMI achieves the lowest factorization error, providing further support for our theoretical analysis of tokenizer-dependent factorization error. While this does not establish a universal advantage across all distributions or sampling settings, the results suggest that tokenizer design can influence factorization error independently of learned-model prediction errors. We have added the experimental setups, results, and discussion for both evaluations to Appendix E.4 of the revised paper.

AuthorsOpenReview ↗

Author Rebuttal (2/2)

W2-2 Additional sample-quality metrics beyond generative ppl and entropy could make the evaluation more comprehensive (e.g., LLM-as-a-judge).

Following the LLM-as-a-judge evaluation protocol of Wang et al. [1], we used GPT-5.4 to assess five aspects of generation quality (Clarity, Grammaticality, Factuality, Style, and Creativity), across denoising steps K∈16,32,64,128,256,512,1024K \in{16,32,64,128,256,512,1024}. The results are reported below.

StepsBPEWordPieceUnigramWPMI
161.591.591.601.62
321.661.601.601.76
641.771.781.861.88
1282.101.951.912.14
2562.012.011.912.06
5122.162.062.172.11
10242.112.112.172.09

The results further support our results, with WPMI achieving the highest judge scores at 16–256 denoising steps, while the advantage diminishes at larger step budgets. These results provide complementary evidence that WPMI improves generation quality particularly under limited decoding budgets. We have added the evaluation detail and results to Appendix E.1 of the revised paper.

[1] Linxuan Wang, Ziyi Wang, Yikun Bai, Wei Deng, Guang Lin, and Qifan Song. Generalized Discrete Diffusion with Self-Correction. arXiv preprint arXiv:2603.02230, 2026.

I appreciate the authors' further clarification and additional experiments. My concerns are resolved.

I don't have substantial direct experience in tokenization, so I tend to maintain my current rating 3, but to me this is a good paper.

We sincerely thank the reviewer for the constructive questions that helped us improve the paper, as well as for the positive assessment of our work. Revisions and additional results have been incorporated into the revised paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.