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

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.