- 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
I thank the authors for their thorough response to my questions and concerns. I raise my score to a 4.
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^), where 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.
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.