acceptodds
Under review as a conference paper at ICLR 2027

Parallel Unmasking under Unknown Dependence: Exact Minimax Batching

Abstract

Diffusion language models decode multiple tokens in parallel to accelerate generation, but tokens in the same batch cannot use one another's values, so parallel decoding may fail to preserve their dependencies. Existing decoders use confidence or estimated dependence to set batch sizes, yet the best worst-case guarantee remains unknown when batch sizes must be chosen without reliable dependency information. We exactly characterize this limit for every sequence length and call budget, construct a plan that attains it, and give matching targets showing no fixed deterministic plan can do better when vocabulary is large enough. The key is to track when dependence becomes relevant during decoding. Each plan can be judged by its risk at every stage, and the optimum minimizes the largest. We also quantify the gains from randomization when the chosen schedule is known, identify when online adaptation cannot improve the boundary, and exactly separate batching from predictor error. On LLaDA and Dream, theory-derived batch sizes improve generation accuracy over equal batching with the same position-selection rule and call budget.

Primary area:
learning theory
Keywords:
diffusion language models, parallel decoding, unmasking schedules, minimax theory, dependence measures, inference efficiency

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_VLa3OpenReview ↗
Rating
3
Confidence
1
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The authors prevent a theoretically-supported method for choosing the number of parallel tokens to decode at once in diffusion language models. They prove bounds and show that their results hold empirically on benchmark performance.

Critical strengths
  • The method is theoretically sound.
  • The method has been validated empirically on actual useful benchmark tasks.
Critical weaknesses

I am not an expert in information theory or randomized algorithms, so I don't have substantial methodological feedback. I am experienced in language models, and I do think that this provides a principled solution to a real problem.

Questions for authors
  • I think you should use a different word besides "batch" to describe multiple tokens being decoded at once. This could be confused with batching of unrelated sentences. Perhaps you could use "chunk" or "burst". This is not a critical suggestion, though, and just one sentence clarifying the distinction would be enough.
  • From the Figure 1, it's not clear that we can do arbitrary non-left-to-right orders for the parallel decoded batches, although your method makes it seem that in fact, the tokens in the batch don't need to be contiguous. Please clarify the diagram accordingly.
Reviewer_ifAjOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to allocate token updates across decoding steps under a fixed step budget when token dependencies are unknown. It derives an information-theoretic characterization of the error induced by parallel independent sampling and formulates batch-size scheduling as a minimax optimization of normalized KL divergence. Using binary search over a risk threshold and a greedy feasibility procedure, the method computes an optimal deterministic batch-size schedule under the stated assumptions. The resulting schedule depends only on sequence length and decoding budget, requires no dependency estimation or additional model calls, and can be integrated into existing masked diffusion decoding pipelines.

Critical strengths
  1. Principled theoretical foundation. The paper connects the error induced by parallel independent sampling to an information-theoretic characterization of token dependencies, providing a rigorous basis for batch-size scheduling.
  2. Optimal scheduling without dependency estimation. Under a fixed decoding-step budget, the proposed method computes a minimax-optimal schedule without requiring access to the underlying token dependencies.
  3. Simple and lightweight integration. The schedule depends only on sequence length and decoding budget, requires neither retraining nor additional model calls, and can serve as a drop-in alternative to uniform batch allocation.
Critical weaknesses
  1. Gap between theory and practical decoding. The analysis assumes exact conditional distributions, uniformly random reveal orders, and irreversible independent sampling within each batch. Practical decoding often uses approximate predictors, confidence-based selection, or greedy token updates, for which the same guarantees do not directly follow
  2. Conservative, input-independent scheduling. For a given sequence length and step budget, the method uses the same schedule regardless of the model, prompt, or observed uncertainty. This provides robustness but may sacrifice gains available from adaptive scheduling. I am therefore concerned that optimizing for worst-case dependency structures may be overly conservative for practical DLMs. Stronger evidence and analysis are needed to establish whether this robustness translates into meaningful gains over adaptive decoding strategies on realistic workloads.
  3. Need for stronger practical comparisons to demonstrate practical value. The evaluation should include stronger adaptive decoding baselines, such as confidence-threshold and entropy-based methods, as well as SlowFast Sampling and DAPD, which respectively exploit dynamic sampling and attention-derived token dependencies.
  4. Limited empirical validation and heuristic baselines. The evaluation should cover a broader range of DLM architectures and datasets to assess the generality of the proposed schedule. It should also include simple heuristic schedules that mimic its qualitative shape, for example, decoding fewer tokens per step at the beginning and end, and more in the middle.
Questions for authors

NAN

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

This paper studies the problem of allocating batch sizes for parallel unmasking in diffusion language models when reliable information about token dependencies is unavailable. The authors formulate a distribution-independent minimax objective under a fixed number of model calls and derive an exact characterization of the optimal deterministic batching schedule. The key theoretical result relates the KL error introduced by parallel sampling to information-profile jumps and schedule-dependent loads. The paper provides a constructive algorithm for obtaining an optimal schedule and matching lower bounds through projective Reed–Solomon code distributions. It further investigates randomized schedules, online adaptation, hidden schedule labels, and an exact decomposition separating batching error from learned-predictor error. Experiments on finite synthetic distributions and two diffusion language models, LLaDA and Dream, show that the proposed batching schedules can substantially improve generation accuracy over equal batching under matched model-call budgets.

Critical strengths
  1. The paper isolates the choice of batch sizes from position selection and formulates a distribution-independent minimax problem under a fixed call budget. This is a useful perspective because much of the existing literature couples these two decisions through confidence or dependency estimates.

  2. Theorem 4.2 establishes the optimal deterministic normalized risk and provides a constructive schedule, with matching hard distributions built from projective Reed–Solomon codes. Theorem 4.4 further gives an efficient method to recover the optimal schedule.

  3. The results on randomized schedules, hidden versus observable schedule labels, adaptive policies, and predictor-error decomposition significantly extend the scope of the work.

  4. On LLaDA and Dream, the authors keep the position-selection policy and call budget fixed while changing only the batch sizes. The experiments report sizable accuracy improvements without increasing runtime in the matched-budget settings.

Critical weaknesses
  1. The main minimax results are derived for exact conditional sampling, where tokens within a batch are sampled independently from their conditional distributions. However, the language-model experiments employ learned predictors with greedy token commitment.

  2. The proposed objective minimizes worst-case KL divergence normalized by the smaller of total correlation and dual total correlation. This is a meaningful theoretical criterion, but it is not directly aligned with the task-level metrics used in the experiments.

  3. The relationship between the worst-case constructions and natural-language dependencies is unclear.

  4. The real-model experiments are primarily conducted on GSM8K with two diffusion language models. Although the reported gains are substantial, the evaluation does not establish whether the proposed schedules generalize to other generation tasks, such as code generation, instruction following, and longer-form reasoning.

Questions for authors
  1. Can the authors further explain or empirically investigate how the minimax KL guarantee relates to deterministic greedy decoding? In particular, do the proposed schedules retain their advantage when comparing conditional sampling and greedy commitment under otherwise identical settings?

  2. Under what conditions should the proposed distribution-independent schedule be preferred over a target-aware or confidence-adaptive schedule? Can the authors characterize when minimizing normalized KL is predictive of improved task accuracy?

  3. Can the authors provide an empirical analysis of the information-profile structure observed in real diffusion language models?

  4. Do the improvements persist on code-generation benchmarks, instruction-following tasks, or longer generations?

Comments on the paper

2 comments

Thank you again for your encouraging response and for taking the time to consider our rebuttal.

Just a small administrative note: in your latest response, you mentioned that you would raise your score, but the rating in your formal review is still displayed as 2. Could you please check whether the intended update has been saved? If you are already planning to update it, please excuse the reminder.

Regarding your note to the AC, confidence 2 does not require expertise in this specific topic; it allows for little or no direct research experience, provided the reviewer has a general familiarity with the field. If your original confidence of 2 still reflects your familiarity with the field, would you consider retaining it? We would be happy to clarify any remaining technical questions.

Your further support would mean a great deal to us. Thank you again for your time, and we hope you have a wonderful day.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.