acceptodds
Under review as a conference paper at ICLR 2027

Structured Parallelism for Diffusion Language Models

Abstract

Discrete diffusion language models generate text by repeatedly updating noisy or masked tokens. At each step, a bidirectional Transformer backbone uses context from both directions to compute token representations, which an output layer converts into probabilities. Most models use a product distribution: they learn individual token predictions and sample them independently given the noisy sequence. This simplifies training and sampling, but even accurate individual predictions can yield inconsistent combinations. Later steps can improve consistency, at the cost of further Transformer passes. We introduce Structured-Parallel Diffusion Language Models (SPDLMs), which model dependencies among tokens proposed in the same step. At each denoising step, a lightweight decoder reuses a single Transformer evaluation of the noisy sequence to generate dependent tokens in parallel groups. Sequential computation is confined to this decoder, without reevaluating the Transformer within the step. Experiments on controlled pretraining and adaptation of existing diffusion language models show that this structured joint distribution improves generation with few denoising steps, reducing the need for costly backbone evaluations.

Primary area:
generative models
Keywords:
discrete diffusion language models, structured prediction, parallel decoding, efficient inference, language modeling

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

SPDLMs model dependencies among tokens generated in the same denoising step, using a lightweight decoder and one backbone evaluation. Experiments on TinyStories, GIDD-3B, and Sumi-7B show improved few-step generation and quality–latency trade-offs.

Critical strengths
  1. The method models within-step dependencies without extra backbone evaluations. The controlled comparisons in Appendix C.6 support the benefit of higher conditional order.

  2. The results show a useful quality–latency trade-off. On TinyStories, one-step W32K32 achieves comparable matched-entropy GenPPL to the 32-step Product baseline with an 8.9x speedup. The Sumi-7B results also show higher GSM8K accuracy with little added decoding cost.

Critical weaknesses

The larger-model experiments use W16K2 and 128-token outputs. It is unclear whether higher conditional order improves the quality–latency trade-off at this scale, or whether the gains persist with longer outputs.

Questions for authors
  1. At few-step budgets, how does W16K16 compare with W16K2 on GIDD or Sumi in quality and latency?

  2. Do the quality–latency gains over Product persist with longer outputs? A GSM8K comparison at 256 answer tokens under matched training and decoding settings would help.

2 comments
AuthorsOpenReview ↗

Author answer

We thank the reviewer for recognizing the within-step dependency mechanism and the studies of different structures. The two questions identify valuable tests beyond TinyStories, and we have directly addressed both on Sumi-7B: independent Product/W16K2/W16K16 adaptations across three seeds, matched 256-token targets, and all 1,319 GSM8K test questions per setting.

Question 1: higher order at 7B scale

Answer tokensStepsProduct accuracyW16K2 accuracyW16K16 accuracy
25684.12±1.70% (1.539s)12.36±6.28% (1.623s)13.19±3.57% (1.620s)
2563215.01±4.35% (6.160s)21.43±9.20% (6.497s)24.61±1.91% (6.478s)
1283220.47±3.01% (6.126s)20.37±7.73% (6.435s)23.33±5.29% (6.434s)

We report in the table above the mean / standard deviation across training seeds, along with batch-1 time. At 256 answer tokens, higher order improves mean accuracy by 0.83 points at eight steps and 3.18 points at 32, at essentially the same measured time. Both width-16 paths have depth 16: the intervention adds clean conditioning information, not head rounds or backbone calls. K16 wins two of three seeds at each 256-token budget. This extends the matched comparison of conditional orders to 7B scale and demonstrates a better mean quality–cost point in the tested setting.

Question 2: 256-token answers

Yes, the gains persist under matched ancestral decoding. We changed the training targets as well as the evaluation window, rather than only extending old 128-trained checkpoints. K2 and K16 beat independent Product in every seed at both 256-token budgets above; at eight steps, accuracy increases from 4.12% to 12.36%/13.19% with modest added generation time. All cleaned test references fit 256 tokens.

The additional 128-token evaluation uses these same 256-trained adapters; K2 is approximately tied with Product there, while K16 improves the mean. We will report these results alongside the native-confidence comparisons, keeping the sampler settings explicit.

I thank the authors for the detailed response and additional experiments, which address most of my concerns. Based on my overall assessment of the paper's contributions, I will maintain my original score.

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

This paper tackles the problem of token-independent parallel decoding in diffusion LLMs, and proposes within-step factorization based on a tree structure. To implement this, the authors introduce an adapter after the backbone output state, so that at each round inside a denoising step, tokens can be sampled from a fixed order conditional on some of the already decoded tokens (separator). The adapter contains a read and write head, and is trained by cross entropy loss. Experiments on 0.1B, 3B and 7B models show promising results in terms of quality and speedup

Critical strengths
  • Breaking the independence assumption of parallel decoding for masked diffusion LLMs is an important direction for lossless acceleration, and a quite timely topic in the community
  • The proposed method is a clear and simple idea in high level: one forward pass for computational heavy backbone, and multiple calls to the lightweight adapter. Experiments show promising speedups with comparable quality
  • Experiments cover models of different sizes and contain different benchmarks / evaluation metrics
Critical weaknesses
  • The paper writing is not quite readable. I can understand the general idea for conditional generation but don't think that such complicated graph-theoretical notations are good for the general audience. At revision, I recommend to use a more simplified notation, provide a table to explain their meaning, and maybe more concrete examples / illustrations
  • For reasoning, more benchmarks beyond GSM8k would be more convincing, for instance some coding tasks like HumanEval or MBPP. These tasks have different nature compared to math reasoning and makes evaluation more comprehensive
Questions for authors
  • As the authors also mention continuous diffusion LLMs (e.g., FLM with one-hot embedding, which directly predicts posterior distribution), do you think similar strategies can be apply there for acceleration?
3 comments
AuthorsOpenReview ↗

Author answer

We thank the reviewer for recognizing the high-level idea, backbone amortization and evaluation across model scales. The suggestions are helpful for making the mechanism more accessible and clarifying its practical scope.

Weakness 1: notation and a concrete example

We agree that the operational intuition should precede the formal graph notation. We will move the detailed graph formalism to the appendix and lead the main-text presentation with a token example and a compact definition table: WW is component width, KK is conditional order, and DD is sequential head depth. For “New York City skyline,” sample “York,” then “New” and “City” in parallel conditioned on it, then “skyline” conditioned on “City.” All factors reuse one backbone evaluation; dependency order need not equal word order. This makes the key mechanism explicit: coordinate the clean choices within an update without rerunning the expensive backbone. We appreciate this valuable suggestion and will revise the presentation accordingly.

Weakness 2: broader tasks, including coding

We appreciate the request for broader evidence. During rebuttal, we completed matched OWT pretraining through 50k updates and strengthened the GIDD-3B/Sumi-7B studies with independently trained Product baselines and three-seed replication. These complement TinyStories by testing both learning structure from scratch and adapting released large models with limited additional training. The positive few-step text and GSM8K results establish usefulness beyond the smaller-scale design studies.

Examples from the added studies are (we recommand checking the answers provided to reviewer SyiW for more details):

SettingProductStructured
OWT pretraining, 2 stepsMMD²: 0.41746 GenPPL: 1674.45 (0.0417s)MMD²: 0.24910 GenPPL: 488.25 (0.0635s)
GIDD-3B adaptation, 8 stepsCentered conditional GM: 2.815±0.615 (0.2481s)Centered conditional GM: 1.667±0.168 (0.3834s)
Sumi-7B adaptation, 256 tokens / 8 ancestral stepsGSM8K: 4.12±1.70% (1.539s)GSM8K (K16): 13.19±3.57% (1.620s)

We agree that a dedicated coding evaluation would be a valuable addition. Within the rebuttal period and our limited additional compute budget, we prioritised matched GSM8K adaptation across three model variants and three training seeds, rather than a further code-specific adaptation campaign. Our GIDD-3B study complements this mathematical setting with heterogeneous Nemotron-CC web text, whose corpus includes programming-related material and code snippets. The improvement in centered conditional Gradient Moment against independently trained Product shows that the benefit extends beyond mathematical answers to broader text generation. We hope this provides evidence across more varied data.

Question: continuous diffusion / one-hot FLM

Thank you for this interesting question. As noted in the introduction of Deschenaux and Gulcehre, deterministic flow language models integrate an ODE whose velocity can depend on the entire sequence, rather than independently sampling categorical tokens at each step. It is therefore unclear to what extent these models face the same lack of within-step coordination, and the benefit of SPDLM is less direct than for discrete DLMs. Moreover, if the velocity depends only on per-token posterior expectations, adding dependence while preserving those marginals leaves the update unchanged. Structured proposals could potentially help stochastic flow decoding, but this requires dedicated investigation. We will clarify this distinction while keeping our empirical claims specific to discrete diffusion.

I appreciate the authors' response and remain my positive assessment of the paper. Since ICLR allows the authors to modify their paper, I really suggest the author to post the revised paper before the deadline of author--reviewer discussion period so that we can have a final evaluation

Thank you for your follow-up and continued positive assessment. As suggested, we have uploaded a revised PDF incorporating the additional experiments, with changes marked in blue. We also clarified the presentation but plan to make a more thorough presentation pass for the camera-ready version (as we focused on doing the required extensive experiments within the tight time constraint of the discussion).

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

The authors consider a problem of inconsistent text sampling due to factorized parametrization in diffusion language models. They propose to address it by learning an additional lightweight head that iteratively uses sampled tokens to adjust predictions for the remaining tokens. Specifically, each token is predicted conditioned on the final backbone hidden representations and a subset of previously sampled clean tokens, using designed read/write operations that in the separate KV pair information about previously sampled tokens on the current diffusion step. The proposed method is evaluated on TinyStories text generation and fine-tuning of GIDD-3B on Nemotron and fine-tuning of Sumi-7B on GSM8K.

Critical strengths

A compact design of a dependency sampling head The proposed sampling head that uses dependencies between tokens has an efficient design based on the proposed read/write mechanism that updates one additional KV pair per token. As a result, it requires a small number of additional parameters to work.

Critical weaknesses

Not enough discussion and comparisons with similar methods. The idea of adding a lightweight head to model dependencies between tokens during sampling is not novel, and several similar approaches have been proposed [1-4]. Thus, the experiments should include comparisons that show the advantage of the proposed design over these approaches. However, among other methods, the authors omitted [1-3] while discussing [4] without experimental comparisons.

Limited evaluation. Many experiments and studies on the proposed Read/Write mechanism are conducted on the very simple TinyStories setup known for its clear, simple patterns like "Once upon a time ..." with a short sequence length of 256 tokens. Furthermore, evaluation mostly uses genppl-entropy fronties, which are known to be poor metrics of text quality as studied, e.g., in [5]. Also, the genppl-entropy frontier does not measure the diversity between generated samples. Although the TinyStories experiments include a D-MMD control, comparisons with the closely related methods [1–4] are missing. A study on a standard OpenWebTText setup with additional distributional metrics would provide more information both on how the method works on more complex texts and on how it relates to other baselines. Another standard setup with clear metrics and numerous already evaluated baselines is TinyGSM, as was done, e.g., in [6].

For Sumi's experiments, only ancestral sampling was tested, while the authors of Sumi stated (Section 4.2) that confidence-based sampling works much better for Sumi. Since confidence-based sampling is dominant for downstream tasks in large-scale models, three should be a clear comparison in this standard practical regime.

For GIDD, only 120 continuations from "Nemotron shard data" are used to evaluate text generation quality with the Gradient Moment metric without comparisons with other baselines. Furthermore, the only comparison is between the model with the head ON and OFF, which is not fair, since the same model was trained to use it during the training, and turning it OFF introduce mismatch between training and evaluation. The clear comparison with the matched factorized model is required. Also, the authors do not provide a clear description of the Nematron data used for training. There is no direct dataset link, exact shard identifier, or description of the train/evaluation split, making the experiment difficult to reproduce.

[1] Bansal and Sanghavi. Enabling Approximate Joint Sampling in Diffusion LMs.

[2] Xu et al. Multi-Token Residual Prediction.

[3] Campbell et al. Self-Speculative Masked Diffusions.

[4] Hersche et al. Locally Coherent Parallel Decoding in Diffusion Language Models.

[5] Franca, A., and Tong, A. Hacking Generative Perplexity: Why Unconditional Text Evaluation Needs Distributional Metrics.

[6] Deschenaux J. et al. Simplex Diffusion Models

Questions for authors

For GSM8K Sumi training, it is reported, that first 128 tokens are used (as well as for evaluation). Is such lenght is enough or there is a loss of information in such truncation?

5 comments
AuthorsOpenReview ↗

Author answer #1

We thank the reviewer for the careful assessment, for recognizing the compact Read/Write design, and for the valuable suggestions on evaluation and related work. These comments helped us strengthen the paper and the empirical study. Within the rebuttal period and our limited additional compute budget, we completed substantial experiments directly targeting the concerns raised:

  • GIDD-3B: independently trained Product and Forest models across three seeds, with distributional evaluation and measured latency.
  • Sumi-7B: nine matched Product/K2/K16 adaptations, longer answers, native-confidence baselines and native-output checks.
  • OpenWebText: matched Product/Structured pretraining through 50k updates, extending the TinyStories studies to realistic text, with distributional, repetition/diversity and latency evaluation.

Together, these studies test two complementary uses of structured proposals: learning a diffusion model from scratch and improving an existing 3B/7B model through adaptation, particularly when very few backbone evaluations are available.

Weakness 1: related methods and contribution

We sincerely appreciate the pointers to ADJUST, MRP, SSMD and CoDiLA, and will expand the manuscript's discussion of these connections. They share the motivation of coordinating parallel predictions. Our specific contribution is a family of structured distributions with explicit clean-token conditioning and a compact one-slot Read/Write architecture, separating component width, conditional order and sequential head depth while reusing fixed backbone features. ADJUST/MRP distill backbone predictions; SSMD uses a causal target and speculative sampling; CoDiLA's main language setup uses an auxiliary pretrained AR decoder. We will make these objective and sampling distinctions explicit.

These differences make strictly matched comparisons non-trivial. For example, CoDiLA's principal language setup uses an auxiliary pretrained Qwen AR decoder, bringing additional capacity and a different pretraining history. A fair comparison therefore needs to account for the backbone, adaptation data, additional parameters and generation cost. The existing CoDD comparison (in Table 1) is particularly relevant to our output-factorization question: it tests probabilistic recoupling against directly learned clean-token conditionals on the same backbone and uniform bridge. We recall that in the original 128-token, all three seeds favor SPDLM at every tested budget.

Weakness 2: evaluation breadth, fairness and practical sampling

Realistic text and pretraining. We agree that OWT is an important complement to TinyStories. TinyStories makes extensive comparisons of widths, orders and topologies practical: the dataset was introduced to facilitate the development and analysis of LMs, especially in low-resource or specialized domains. It allowed us to quickly and meaningfully iterate on all the sweeps we had to test. Then, OWT asks whether their conclusions extend to realistic text. But we want to underline that the compute difference is substantial: for example, Deschenaux and Gulcehre, Table 2 report approximately 1,285–1,814 H100-hours for million-update OWT training of 170M-parameter diffusion models (80–113 hours on 16 H100s). Nevertheless, during rebuttal we completed matched Product/Structured OWT pretraining through 50k updates. This budget also has methodological support: Pynadath et al., Section 5 find closely matching 50k and 1M generative frontiers for MDLM, Duo and CANDI, identifying 50k as a useful and legitimate budget for assessing method promise. The independent Product comparison is:

StepsProduct MMD² ↓Structured MMD² ↓Product GenPPL ↓Structured GenPPL ↓Median time: Product / Structured
10.4690.3234276.13838.750.0217 / 0.0337s
20.4170.2491674.45488.250.0417 / 0.0635s
40.2730.168497.78261.260.0831 / 0.1290s
80.1300.105195.78162.550.1594 / 0.2568s
160.0750.071130.10124.460.3176 / 0.5136s
320.0520.052107.98106.980.6470 / 1.0315s

Both quality improvements are resolved by the paired conditional sampling intervals at 1–16 steps: at two steps the reductions are 40.3% and 70.8%. At 32 steps, the differences are smaller. Although structured adds latency at a fixed step budget, its two-step result improves both quality metrics over four-step Product while taking less time (0.0635 versus 0.0831 seconds). As previously observed in the paper, the strongest gains occur in the very-few-step regime motivating the method.

AuthorsOpenReview ↗

Author answer #2

GIDD fairness and data. Thank you for distinguishing a head-off ablation from an independently optimized baseline. We addressed this by training matched Product and Forest adaptations across three seeds. For example, at temperature T=0.8T=0.8, the centered conditional Gradient Moment is:

StepsIndependent ProductForest, head disabledForest decoding
126.27±0.34 (0.053s)25.76±0.8511.75±0.64 (0.070s)
222.65±0.50 (0.081s)23.87±1.188.19±0.69 (0.115s)
49.81±0.30 (0.136s)9.90±0.214.09±0.36 (0.205s)
82.82±0.62 (0.248s)3.57±0.481.67±0.17 (0.383s)
321.22±0.10 (0.916s)0.82±0.340.51±0.41 (1.454s)

Lower GM is better, and the ± values report the standard deviation across three training seeds. At eight steps, Forest outperforms the independently trained Product model in every seed. Comparing Forest with its head enabled and disabled also shows the head’s contribution beyond backbone adaptation. The lower mean GM persists at eight steps across all three tested temperatures (0.8, 1.0 and 1.2). Each setting uses the same 128 test prefixes. We will include the temperature results and full data preparation details in the revised manuscript, including the exact shards and preprocessing of the official dataset.

Comparison with native-confidence decoding. We agree with the Reviewer and performed a comparison between Sumi native-confidence Product and ancestral SPDLM at 1/2/4/8 steps, directly targeting the few-steps regime motivating our method. All models are independently adapted with matched 256-token GSM8K targets across three seeds and evaluated on the same 1,319 questions with a 256-token generation cap. Below, we report the mean±training-seed SD, alng with Batch-1 time.

StepsProduct, native confidenceSPDLM K2, ancestralSPDLM K16, ancestral
10.10±0.09% (0.200s)2.30±0.69% (0.203s)2.78±0.86% (0.204s)
20.81±0.18% (0.397s)3.39±1.32% (0.405s)3.99±0.81% (0.406s)
43.71±0.83% (0.786s)6.52±3.88% (0.814s)7.20±2.72% (0.809s)
89.98±1.21% (1.572s)12.36±6.28% (1.623s)13.19±3.57% (1.620s)

Both structured variants improve mean accuracy over native-confidence Product at all four tested budgets. Thus, the few-step benefit is not limited to comparison with ancestral Product: SPDLM’s natural ancestral sampler also improves over the native confidence-based policy in this regime. The latency measurements make the additional structured-head cost explicit.

Importantly, this comparison does not require transferring confidence-based selection to the structured head, where token dependencies make the integration non-trivial and an interesting direction for future work. Instead, it evaluates each approach with its established decoding procedure. Together with the matched ancestral comparisons, these results show that useful within-step structure can be learned through limited adaptation of a released 7B diffusion model, without repeating backbone pretraining.

About Pretraining vs adaptation

We would also like to highlight a complementary strength of our experimental study: structured outputs provide benefits both when training a diffusion model from scratch and when adapting an existing large diffusion model. The TinyStories and added OWT experiments test the former, while the GIDD-3B and Sumi-7B studies show that useful output structure can also be learned through limited additional adaptation, without repeating backbone pretraining. Demonstrating benefits in both settings supports the relevance of the approach beyond a single training regime.

Reusing pretrained capabilities is itself an important practical route in current DLM development: DiffusionGemma is adapted from Gemma 4, while Clover-35B-A3B-Preview is derived from Qwen3.6-35B-A3B. Our large-model experiments explore a complementary opportunity: improving already released diffusion models through structured output adaptation. We hope this perspective clarifies why the adaptation results are valuable in their own right, alongside the expanded pretraining evidence.

AuthorsOpenReview ↗

Author answer #3

Question: 128-token truncation

Thank you for raising this point. After investigating, we found that a 128-token limit can remove part of the rationale or final answer: 721 of 7,473 training answers and 134 of 1,319 test reference answers exceed this window.

To address this concern, we did not simply increase the generation length. We retrained Product, W16K2 and W16K16 with matched 256-token targets across three seeds, then evaluated 256-token answers on all 1,319 GSM8K test questions. All cleaned test references fit within this window; only four training references still exceed it.

The structured gains persist under this longer-answer protocol:

Ancestral stepsProduct accuracyW16K2 accuracyW16K16 accuracy
84.12±1.70% (1.54s)12.36±6.28% (1.62s)13.19±3.57% (1.62s)
3215.01±4.35% (6.16s)21.43±9.20% (6.50s)24.61±1.91% (6.48s)

Both structured variants outperform independently trained ancestral Product in every seed at both budgets. These results strengthen the original finding by showing that the benefit persists when training and evaluation accommodate longer rationales and final answers.


Finally, we sincerely thank the reviewer for the suggestions that motivated these substantial additions, and hope that the new evidence on realistic text, independently trained baselines and longer GSM8K answers addresses the main concerns and warrants reconsideration of the score.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary of additional experiments and manuscript revisions

We thank all reviewers for their constructive feedback, which motivated substantial additional experiments during the rebuttal period despite our limited additional compute budget:

  • OpenWebText: matched Product/Structured pretraining, showing strong few-step quality gains, including a better quality–latency point.
  • GIDD-3B: independently trained Product/Forest adaptations, confirming the structured-head benefit on realistic web text.
  • Sumi-7B: matched adaptations with longer GSM8K answers, addressing truncation and showing higher mean few-step accuracy than the stronger native-confidence Product baseline, with approximately 2–4% additional generation time.

These new results strengthen the evidence for structured outputs in both pretraining and large-model adaptation, particularly in the very-few-step regime. We will include the full results and further experimental details in the revised manuscript, clarify the method and related-work discussion, and release the accompanying code upon acceptance for reproducibility.

AuthorsOpenReview ↗

Wrap-up of the rebuttal.

We thank all reviewers for the constructive discussion, and reviewers n1UA and Dytq for their follow-up feedback. We have uploaded a revised manuscript incorporating the experiments and clarifications discussed in our responses. Changes are marked in blue:

  • Evaluation and baselines (SyiW): matched OpenWebText pretraining with distributional evaluation (Section 5.2, Appendix D) and independently trained Product/Forest GIDD-3B adaptations across three seeds (Section 5.3, Appendix E).

  • Practical decoding, higher conditional order and longer answers (SyiW, Dytq): matched Sumi-7B adaptations with 256-token GSM8K targets, K2/K16 comparisons, and ancestral SPDLM versus native-confidence Product in the few-step regime (Section 5.4, Appendix F).

  • Presentation and related work (n1UA, SyiW): a more gentle introduction to the core method (Section 3), alongside expanded related-work and continuous-flow discussion (Section 2.1).

Together, we think that these experiments strengthen the evidence for structured outputs in both pretraining and large-model adaptation. The revised manuscript includes the corresponding protocols and updates the conclusions in Section 6.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.