- 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
- 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.
- Clear demonstration. Figure 1 helps to understand the limitations of ordinary tokenizers and the approach of WPMI.
- 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 there are, the lower the perplexity WPMI achieves.
Critical weaknesses
- 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.
- 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
- 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.
- In line 183, what does “reconstruction information” mean?
- In Proposition 1, is encoded-length entropy the only type of entropy we need to consider? If so, please provide clear proof.
- In Section 4.2, why do you only use the second-order component in Equation (8)? Are other higher-order components negligible?
4 comments
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 , 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). captures stochastic encoding uncertainty, while captures information lost during encoding. The former vanishes for deterministic tokenization, and the latter vanishes for lossless tokenization, leaving only . The remaining step is to establish . At each fixed encoded length , the oracle conditional loss and integrated masking weights yield the entropy chain rule averaged over uniform permutations, giving . Averaging over the encoded-length distribution then gives .
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, 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 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 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.
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.
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:
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.This mismatch between inherited tokenizer design and independent parallel decoding motivates us to examine tokenization as a separate design variable.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.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.
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). 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-1reports 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 S2 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)