acceptodds
Under review as a conference paper at ICLR 2027

Reasoning Should Follow Dependencies, Not Token Order: Partial-Order Diffusion for Native Parallel Reasoning

Abstract

Diffusion language models (dLLMs) promise parallel reasoning because they are not forced to generate left-to-right. Yet recent evidence shows that arbitrary-order decoding can become a liability: models often resolve easy, low-uncertainty tokens while postponing high-impact forks, collapsing exploration. We argue that the missing inductive bias is neither a total order nor no order, but a partial order. We introduce Partial-Order Diffusion Reasoning (PoD-R), which represents a reasoning trajectory as a learned semantic DAG whose nodes are compact reasoning variables and whose edges encode logical dependence. At each denoising step, PoD-R selects an antichain of approximately conditionally independent nodes and refines them in parallel; high-uncertainty, high-influence forks are kept as explicit hypotheses rather than prematurely committed; detected errors trigger localized remasking of their predicted causal repair regions, with uncertainty-aware graph expansion. We derive a conditional-total-correlation criterion that bounds the KL divergence of parallel factorization under conditional-dependence assumptions, show that idealized execution depth under exact dependencies is governed by the DAG critical path rather than the number of reasoning steps, and formulate critical-path-aware reinforcement learning. The resulting view reframes diffusion reasoning as asynchronous inference over a learned computation graph. We evaluate final-answer quality and structural fidelity primarily with DreamReasoner-8B on DAG-Math, AIME 2024/2025, MATH500, LiveCodeBench, and the controlled DAGReason benchmark. Across the evaluation, reasoning parallelism scales with graph width while maintaining dependency-structure fidelity on annotated reasoning graphs.

Primary area:
generative models
Keywords:
diffusion language models, reasoning, chain-of-thought, parallel reasoning, graph neural representations, dependency graphs, non-autoregressive generation, reinforcement learning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_hTD1OpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This work argues that any order parallel generation is harmful, and that an imposed exact order is not helpful in principle either. To circumvent this issue, the authors model the dependencies between the semantic units of a sequence, and leverage those to generate a graph that respects this ordering while leveraging the parallelism that is not harmful as much as possible. This leads to high performance on a host of tasks while improving the generation speed.

Critical strengths
  • The paper is very clear and well-presented; information is not obstructed but rather direct.
  • The method is very natural and simple.
  • Figure 3 is the most convincing result of the paper, arguably, with a maintained accuracy (on par with AR CoT) at a higher speed.
  • The authors also inspect the resulting reasoning graphs cleanly to separate confounding factors in a rather rigorous way.
Critical weaknesses

I have no major concerns. Some small weaknesses may include:

  • Figure 2: I'm not certain that the plot is really rigorous, because it is not clear to me -- and this has perhaps eluded my reading -- that the performance is maintained when the speed increases (from the plot itself; I could very much believe that it works equally well still, but it would be good specify it).
  • More results of the kind of Figure 3 would be very helpful to demonstrate the method on a broader variety of benchmarks.
  • Some theoretical results could perhaps be interesting about the resulting, but it is really not necessary.
  • Perhaps a discussion about the relation of this work to Energy-based Diffusion Language Models for Text Generation by Xu et al. (2024) could be relevant.
Questions for authors

My main question would be about whether the authors would be able to produce more results akin to Figure 2 (i.e., the same latency/parallelism vs accuracy kind of plot)? I think it is the strongest part of the narrative built by this paper.

I clearly lean towards acceptance, and would be happy to raise my score given further empirical evidence.

2 comments

We thank the reviewer for the encouraging assessment and constructive suggestions. We agree that demonstrating the joint accuracy–parallelism trade-off across diverse tasks would further strengthen the paper.

1. Accuracy–speedup trade-off across benchmarks

We agree that Figure 2 alone does not establish whether accuracy is maintained as parallelism increases. Figure 2 reports speedup against reasoning width, while Figure 3 provides an accuracy–latency frontier only on DAGReason. Table 1 reports accuracy on four natural benchmarks, and Appendix N (Figure 9) establishes a strong correlation between observed speedup and theoretical parallelism across 60 controlled configurations (R² = 0.97).

To address this concern, we add a cross-benchmark accuracy–speedup analysis. For each instance, we compute the predicted graph parallelism ratio ρ^(G)=∣V^∣/L(G^)\hat{\rho}(G)=|\hat{V}|/L(\hat{G}), where G^\hat{G} is the semantic DAG predicted by PoD-R. Within each benchmark, instances are split at the median of this ratio into low- and high-parallelism groups. Importantly, we use the same instance partition for both PoD-R and native Block-4 to ensure a fair paired comparison.

Table X: Accuracy–speedup trade-off across natural benchmarks.

BenchmarkLow-ρ Speedup (95% CI)ΔAcc (pp, 95% CI)High-ρ Speedup (95% CI)ΔAcc (pp, 95% CI)
AIME241.04× [0.99, 1.09]+5.0 [−1.0, 11.0]1.46× [1.33, 1.60]+5.2 [−0.8, 11.2]
AIME251.03× [0.98, 1.08]+4.8 [−1.2, 10.8]1.43× [1.30, 1.56]+5.0 [−1.0, 11.0]
MATH5001.05× [1.02, 1.08]+5.4 [2.6, 8.2]1.38× [1.31, 1.45]+5.8 [3.0, 8.6]
LiveCodeBench1.01× [0.98, 1.04]+2.2 [−0.8, 5.2]1.21× [1.15, 1.27]+2.4 [−0.6, 5.4]

Per-instance speedup is computed as the Block-4 latency divided by the PoD-R latency on the same instance, and ΔAcc denotes the accuracy difference (PoD-R minus Block-4) on identical subsets under matched evaluation budgets. All latency measurements include structural prediction, scheduling, verification, and repair overhead.

We report results over five independent decoding seeds with 95% confidence intervals. For accuracy, we use hierarchical bootstrap over seeds and problem instances; for AIME, the eight generations are first averaged within each problem–seed pair. For speedup, we use paired bootstrap over matched instances and paired permutation tests on per-instance log-latency ratios, with Holm correction across benchmark comparisons.

High-parallelism groups consistently achieve 1.21–1.46× speedup, compared with near-unity speedup (1.01–1.05×) in low-parallelism groups. Accuracy differences are positive across all groups, but most confidence intervals include zero. Thus, the results support substantial efficiency gains at higher parallelism without consistent evidence of accuracy degradation.

2. Theoretical contributions

We agree that the theoretical results are primarily intended to motivate the empirical design. Appendix B provides conditional guarantees under idealized dependency assumptions, rather than unconditional guarantees for learned graphs. In particular, the learned dependence score serves as a scheduling surrogate, not a certified upper bound on conditional total correlation. We clarify this distinction while keeping the empirical validation central.

3. Relationship to energy-based diffusion models

We agree that Xu et al. (2024) is relevant. Their Energy-Based Diffusion Language Model (EDLM) introduces sequence-level energy-based correction to improve the denoising distribution and uses parallel importance sampling for efficient generation. In contrast, PoD-R focuses on modeling semantic dependencies among reasoning variables and scheduling approximately independent variables for concurrent refinement. Thus, EDLM improves distributional modeling during diffusion sampling, whereas PoD-R structures the execution of reasoning computations. The two approaches are complementary.

We appreciate the reviewer’s positive assessment and believe these additions will provide a more direct validation of the central claim.

I thank the authors for their thorough response to my questions and concerns. I raise my score to a 4.

Reviewer_isAKOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Partial-Order Diffusion Reasoning (PoD-R), which predicts a semantic dependency DAG to schedule parallel updates in diffusion language models. The graph also guides hypothesis preservation at reasoning forks and verifier-based local repair. Training combines diffusion modeling, structural supervision, and critical-path-aware reinforcement learning, while the theoretical analysis characterizes parallelization under idealized assumptions. Experiments report accuracy improvements on four natural reasoning benchmarks and speedups that increase with available parallelism on the controlled DAGReason benchmark.

Critical strengths

S1. A coherent use of semantic structure to guide execution. The method uses a common dependency graph to coordinate parallel updates, hypothesis preservation, and local repair. This integration gives structural prediction a clear operational role within diffusion reasoning. S2. Informative controlled experiments. The width-scaling experiments directly examine whether speedup increases with available reasoning parallelism while approximately holding total work fixed. The component ablations also reveal meaningful trade-offs between computational efficiency and invalid concurrency, providing support for the intended roles of the components. (Figures 2 and 9; Table 4.)

Critical weaknesses

W1. The connection between online graphs and backbone execution remains unclear. The paper does not sufficiently explain how semantic antichains are executed under DreamReasoner’s block-causal dependencies, including context access and cache updates after branching or repair. It is also unclear whether graph recovery is evaluated during partial generation and how token-span IoU aligns freely generated derivations with reference DAGs. These gaps limit assessment of whether the predicted structure reliably supports online parallel execution. W2. Practical benefits are not established under sufficiently controlled conditions. Natural-benchmark accuracy and synthetic-task speedups are reported separately, leaving the accuracy–latency trade-off on natural reasoning tasks unresolved. Baseline post-training conditions remain unclear, while the stated compute-accounting and statistical procedures lack corresponding reported results. Consequently, the improvements cannot yet be confidently attributed to partial-order execution or assessed against its additional overhead.

Questions for authors
  1. How are semantic antichains executed across DreamReasoner’s token blocks, including attention visibility and cache handling after branching or repair? A concrete execution trace would help.
  2. Is graph recovery evaluated on actual partially generated trajectories, and how are generated nodes aligned with reference DAGs when the derivations differ?
  3. Do the baselines use the same post-trained checkpoint or receive comparable training? A sequential scheduler using PoD-R’s trained model, graph, and verifier would help isolate the contribution of parallel execution.
  4. Can the authors report a controlled accuracy–latency comparison on a natural benchmark, including method-specific overhead, actual compute, and uncertainty estimates?
1 comment

We thank the reviewer for identifying important implementation and evaluation issues. We clarify existing mechanisms and describe targeted additions.

1. Online DAG execution, block attention, and cache handling

Algorithm 1 (Appendix A) describes the online loop: each denoising round extracts semantic spans, tracks node identities, predicts the DAG, and selects ready antichains. PoD-R preserves DreamReasoner’s native block-causal attention mask and token visibility. The DAG only controls commit scheduling: nodes become eligible when their parents are resolved, and selected antichain nodes share a backbone forward pass; it controls when spans are committed, not which tokens they can attend to. Once the prerequisite in B1 is resolved, independent semantic spans in B2 and B3 can be selected in the same denoising round, subject to the native block-causal visibility constraints.

At forks, branches share cached activations for identical resolved prefixes, while fork blocks and later blocks maintain branch-specific states/caches where supported by the inference engine. During repair (Eq. 19), PoD-R remasks the erroneous node, its descendants, and uncertain Markov-blanket nodes. Cache invalidation follows native attention dependencies: the modified block and later blocks that attend to it are recomputed; unaffected prefix caches are retained. For example, a fork at B2 shares B1's cache across branches; repairing B2 invalidates B2 and dependent later blocks, not B1.

Localized semantic remasking therefore need not mean localized cache recomputation.

2. Graph recovery during partial generation and differing derivations

Appendix C describes online identity tracking: resolved spans are frozen; unresolved spans are re-matched between rounds by maximum-weight token-span IoU, retaining identity at IoU ≥ 0.50. Predicted/reference nodes use the same one-to-one IoU matching before edge-F1. Figure 4 reports held-out DAG-Math edge-F1, from 0.91 to 0.70 across difficulty levels.

However, intermediate-stage recovery is not separately evaluated, and span IoU can miss equivalent nodes expressed differently. We add graph recovery at 25%, 50%, 75%, and 100% generation progress, plus semantic one-to-one matching using normalized proposition embeddings and the best match over accepted reference derivations.

ProgressNode F1Edge F1
25%0.740.56
50%0.820.65
75%0.880.73
100%0.920.78

For alternative derivations, semantic multi-reference matching improves edge-F1 from 0.71 (span-only) to 0.78. We report both protocols.

3. Checkpoint and training comparability

Appendix J states that Block-4 and MatchedConfidence use the same DreamReasoner-8B backbone/native decoder; PoD-R starts from DreamReasoner-8B and adds a 118M structure module and LoRA on the top 12 layers. Accuracy comparisons use a 4096-token cap and matched forward-pass budgets. External baselines (Wavefront, DARD, Prism) do not all share an identical post-trained checkpoint, so these are not pure scheduler-only comparisons.

To isolate scheduling effects, we add a fixed-checkpoint ablation using identical PoD-R post-trained weights, semantic spans, graph predictions, verifier, and repair modules. Only the commit-scheduling policy changes: topological sequential, confidence-only, or full DAG antichain. All variants use the same maximum output-token and NFE budgets.

SchedulerAccuracy (%)Latency (ms)
Topological sequential90.61,090
Confidence-only90.0735
Full PoD-R antichain90.7710

This isolates partial-order execution from post-training differences.

4. Natural-benchmark accuracy–latency–compute comparison

Figure 3 evaluates DAGReason, not natural-benchmark latency. Table 1 reports MATH500 accuracy (Block-4: 85.1%; PoD-R: 90.7%) but not latency. We add a matched MATH500 comparison on one H100, batch size 1, including graph/verifier overhead and normalized compute CnormC_{norm} (Appendix P, Eq. 59).

MethodAccuracy (95% CI)Median latency (95% CI)CnormC_{norm}
Block-485.1% [82.0, 88.1]940 [900, 985] ms1.00
PoD-R90.7% [88.0, 93.0]710 [680, 745] ms0.94

PoD-R latency: 575 ms backbone + 45 ms graph/scheduling + 55 ms verifier/repair + 35 ms other; Block-4: 905 ms backbone + 35 ms other. Accuracy CIs use paired bootstrap over test problems within each seed and hierarchical bootstrap over five seeds. For MATH500 latency, we additionally compute paired 95% CIs over the same test instances and perform paired permutation tests on log-latency. We report normalized compute using Eq. (59).

We appreciate the reviewer’s suggestions.

Reviewer_iYKrOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes a framework (POD-R) for training and generating reasoning traces from diffusion language models (dLMs). The motivation comes from [1], which shows that arbitrary decoding orders can hurt reasoning performance in dLMs. The framework is based on the idea of representing reasoning as DAGs and the partial order of the graph’s nodes. During inference, given a problem x, POD-R estimates a DAG representing the structure of reasoning steps. From this graph, steps that do not have the same dependency can be generated in parallel. POD-R also needs to modify the training/finetuning process to make models suitable for the new inference process. Experiments are mostly conducted on math and code reasoning.

[1] Ni, Z, Wang, S, Yue, Y, Yu, T, Zhao, W, Hua, Y, Chen, T, Song, C, Yu, C, Zheng, B & Huang, G 2026, 'The Flexibility Trap: Rethinking the Value of Arbitrary Order in Diffusion Language Models', arXiv preprint arXiv:2601.15165.

Critical strengths
  • The proposed framework achieved higher performance on math and code reasoning benchmarks (AIME24, 25, MATH500, LiveCodeBench) compared to other approaches on dLMs (e.g., Prism, DARD, Wavefront, MatchedConfidence, …). POD-R also has the best latency among baselines.
Critical weaknesses
  • The problem formulation is not really rigorous. In equation (1), it seems like semantic variables are sorted, but this is not specified anywhere in this context. The function Pa⁡(i)\operatorname{Pa}(i) is used without definition. There is also no explanation for why equation (1) is the ideal distribution. The reason is not clear to me from the context. Equation (2) is also introduced without a clear motivation, and it has many terms left unexplained. The same issues are present in Section 4, making it difficult to follow.
  • The paper lacks qualitative examples of the generation processes. It’s unclear what the qualitative difference in generations from the proposed approach and from standard diffusion language models.
  • The experiments are conducted on a single backbone, and there is a lack of comparison of different hyperparameters for both baselines and the proposed approach.
  • Many critical experimental observations, such as training time and training compute, are missing.
Questions for authors

Please address the previous weaknesses and the following question:

  1. It seems to me that POD-R has a lot more work during generation compared to Block diffusion; how can it achieve better latency in Figure 3?
1 comment

We thank the reviewer for the careful assessment. We clarify the formulation and provide additional analyses.

1. Formulation and theoretical conditions. In Eq. (1), ziz _i denotes the semantic state of span ii, and PaG⋆(i)=j:(j,i)∈E⋆\mathrm{Pa} _{G^\star}(i)=\\{j:(j,i)\in E^\star\\} its parent set. The factorization follows the local Markov assumption. Proposition 1 establishes exact parallel factorization when scheduled nodes' parents are resolved and they are conditionally independent given context CC. Theorem 1 assumes a fixed measurable policy, identical conditionals outside parallelized factors, absolute continuity, and true TC(ZSt∣Ct)≤ϵt\mathrm{TC}(Z _{S _t}\mid C _t)\leq\epsilon _t on sequentially reachable contexts, yielding a trajectory KL bound of ∑tϵt\sum _t\epsilon _t. The learned pairwise score is a scheduling surrogate, not a certified TC bound.

Eq. (4) predicts precedence scores rir _i. Eq. (6) creates an edge only when ri<rjr _i < r _j and aij≥τe=0.50a _{ij}\geq\tau _e=0.50. Thus, rir _i only orients candidate edges to ensure acyclicity; it imposes neither dependencies nor a total order.

Eq. (2) is the expected objective; Eq. (21) is the Stage-3 reward. RcorrectR _{\mathrm{correct}} denotes terminal correctness, L(G)L(G) longest-path length, NFE0\mathrm{NFE} _0 native-decoder mean backbone evaluations under the same budget, ∣⋃jRj∣/∣V∣|\bigcup _j R _j|/|V| normalized repair size, and FGF _G directed edge-F1 after node matching. Reward weights are (λcp,λnfe,λrep,λfid)=(0.20,0.08,0.05,0.10)(\lambda _{cp},\lambda _{nfe},\lambda _{rep},\lambda _{fid})=(0.20,0.08,0.05,0.10) (Appendix K, Table 3).

2. Why is latency lower despite added operations? On one H100-SXM at batch size 1, PoD-R achieves 87.3% solve rate at 455 ms versus 800 ms for Block-4. End-to-end timing includes tokenization, graph prediction, scheduling, verification, repair, and parsing.

Component (ms)Block-4PoD-R
Backbone forward755340
Graph module035
CPU scheduling010
Verifier and repair040
Other overhead4530
Total800455

The 415 ms backbone savings outweigh 85 ms structural overhead (with 15 ms lower other overhead). Table 4 shows NFE increasing from 38.2 to 51.4 without the semantic DAG and 47.5 without critical-path RL.

3. Hyperparameter sensitivity and baselines. We varied BB, λdep\lambda _{dep}, and native block size under matched budgets.

Parallel-capacity sensitivity

BSolve (%)Invalid concurrency (%)Latency (ms)
486.73.9510
887.04.3478
1287.34.8455
1687.16.2447

Dependence-penalty sensitivity

λdep\lambda _{dep}Solve (%)Invalid concurrency (%)
0.1087.09.8
0.3587.34.8
0.7087.13.5

Native block-size comparison

ConfigurationSolve (%)Latency (ms)
Block-284.6920
Block-484800
Block-882.7720
PoD-R ((B=12))87.3455

These results reveal the parallelism/dependence trade-off and show that gains are not merely due to native block size.

4. Qualitative generation trace. We provide a representative trace from an actual PoD-R run on ∣2x−1∣=5|2x-1|=5. PoD-R preserves two hypotheses, H1:2x−1=5H _1:2x-1=5 and H2:2x−1=−5H _2:2x-1=-5, as separate branches. Their solutions (x=3,−2x=3,-2) are denoised independently and combined into −2,3\\{-2,3\\}. If the verifier flags an error in H2H _2, PoD-R remasks its predicted descendants while preserving shared ancestors and unaffected work.

In contrast, standard Block diffusion follows a single blockwise trajectory without explicit semantic branch preservation, antichain-based execution, or DAG-guided localized repair. This illustrates the difference between block-level and dependency-aware generation.

5. Backbone generalization. Appendix H, Figure 7 reports speedups over each backbone's native recommended decoder:

BackboneSpeedup
LLaDA-8B-Instruct2.28×
DreamReasoner-8B3.12×
DiffusionGemma-26B-A4B3.71×

These results demonstrate efficiency transfer, not accuracy generalization; matched-budget quality tests on other backbones remain future work.

6. Training compute. Structure training uses 8×H100 80GB with data parallelism; RL uses the same hardware, freezing the base model except LoRA parameters (Appendix P). All three stages use 8×H100 80GB.

StageHardwareWall-clockGPU-hours
Stage 1: backbone adaptation8×H10024 h192
Stage 2: structure training8×H10018 h144
Stage 3: RL8×H10012 h96
Total8×H10054 h432

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.