acceptodds
Under review as a conference paper at ICLR 2027

Dependency-Structured Generation with Masked Diffusion Language Models

Abstract

Autoregressive language models generate along a fixed left-to-right chain, whereas standard masked diffusion language models (MDLMs) train on randomly masked contexts, assigning equal training weight to all possible token reveal orders. Between these endpoints lies a structured regime: several tokens may be ready concurrently, while others should wait for specific evidence. We formalize this regime as dependency-structured generation, in which a model’s reveal behavior is compactly described by a conceptual directed acyclic graph (DAG) over token positions, whose edges encode prerequisite relations. The framework recovers left-to-right autoregressive and standard (blockwise) MDLM objectives as boundary cases. The graph is a behavioral abstraction rather than a generated variable and is neither supplied nor constructed at inference. We instantiate this framework with MAPLE. During training, MAPLE uses a frozen teacher (e.g., a pretrained LLM) to extract a dependency graph for each target sequence; this graph induces a normalized training distribution over reveal orders. We derive an exact negative ELBO that jointly models the next reveal position and its token value. Under standard realizability, every global minimizer of the population negative-ELBO objective recovers the data sequence distribution. This optimality guarantee does not require the learned model to exactly reproduce the teacher’s reveal behavior; the extracted dependencies instead serve as a finite-model inductive bias toward informative partial contexts. At inference, MAPLE retains the original parallel MDLM decoder unchanged. Continued pretraining of LLaDA 2 and DreamReasoner for mathematical reasoning and code generation improves task accuracy and substantially reduces teacher-dependency violations without sacrificing decoding parallelism.

Primary area:
generative models
Keywords:
Masked diffusion language models, parallel decoding, variational learning

Reviews

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

This paper introduces an alternative to standard DLLM training which treats all unmasking orders as equally plausible with it's standard ELBO objective being equivalent to Any Order training. The proposed method MAPLE is a "middle ground" of sorts which uses models the sequence as a dependancy graph where edges are formed between the prerequisite tokens and their dependants, where tokens that are not connected, could be unmasked in any order potentially, thus modelling dependancies within a sequence and still allowing for many different orderings and parallel decoding oppurtunities. The paper also derives a new ELBO which accounts for both this position selection and token selection from standard ELBO. The paper is well motivated and expeirmental results on finetuning of LLaDA 2.0 and DreamReasoner show the efficacy of this new loss over representative baselines.

Critical strengths
  1. The approach is well motivated, and the paper explains its main ideas clearly. The examples are particlarly helpful in illustrating why revealing supporting information before dependent tokens can improve generation.

  2. The results on mathematical reasoning and code generation are strong overall. Improvements across two model families and several benchmarks show promising evidence that the approach is effective and generalisable.

Critical weaknesses
  1. Missing comparison with [1] which addresses a closely related problem, it is briefly discussed in the introduction but the paper does not compare against it experimentally. It would be good to know if MAPLE's more complicated DAG formulation beats a simpler confidence based one.

  2. It is unclear which component produces the gains. MAPLE changes both how the training contexts are sampled and how confidence is supervised. It would be nice to see these changes ablated seperately so that it would be clear how much each change helps.

  3. The paper does not compare teacher-derived graphs against random graphs or simple ordering rules. Such comparisons would show whether the gains come from useful dependency information or merely from restricting reveal orders. An empty graph baseline is not sufficient in this case.

[1] Peng, F. Z., Bezemek, Z., Rector-Brooks, J., Zhang, S., Zhang, A. R., Bronstein, M., Tong, A., & Bose, A. J. (2026). Planner Aware Path Learning in Diffusion Language Models Training. International Conference on Learning Representations (ICLR)

Questions for authors

Please address the weakenesses above. I would be happy to increase my score based on the author's response.

After Rebuttal

The authors have provided additional results that have addressed the concerns regarding the ablations, comparison to PAPL and the simple graph baselines. Therefore I have increased my rating from a 3 to a 4.

4 comments
AuthorsOpenReview ↗

Response to Reviewer jZ7M (1/2): comparison with PAPL

Thank you for the encouraging assessment and the concrete suggestions! We ran all three requested experiments, with the same setting as Table 1 (see Appendix B for hyperparameter details).


W1. Missing comparison with [1] (PAPL) … It would be good to know if MAPLE's more complicated DAG formulation beats a simpler confidence based one.

Setup. We train PAPL on LLaDA 2, on FineMath and on FineCode, following the experimental setup described in Section 6 and Appendix B. We use the loss recommended in its official repository, NLL⋅[1+sg(e−NLL)]\mathrm{NLL}\cdot[1+\mathrm{sg}(e^{-\mathrm{NLL}})].

LLaDA 2MATHAIME 24+25Olympiad BenchAMC12Human EvalMBPPLCB ProSpiderAvg.
Any-order83.8026.6749.1157.1482.9377.044.5340.4352.71
Efficient-DLM83.8025.0047.0357.1479.8878.213.4040.7251.90
TRIMS84.8028.3347.1861.9081.7178.603.4046.0353.99
PUMA85.0025.0049.4161.9081.7176.653.8240.5253.00
PAPL83.6023.3348.9661.9083.5476.264.6738.6852.62
MAPLE86.6033.3351.3461.9084.1581.714.9651.0656.88

MAPLE outperforms PAPL. It is better on seven of the eight benchmarks and ties on AMC12, and its average is 4.3 points higher. This is consistent with Table 1: the order-aware baselines, now including PAPL, stay within 1.3 points of any-order on average (51.90–53.99 vs. 52.71), while MAPLE reaches 56.88.

Why the DAG helps beyond confidence. PAPL belongs to the same family as PUMA and TRIMS in Table 1. Their order signal is one score per position: PAPL and PUMA use the model's own confidence, and TRIMS uses a teacher's token difficulty. Such a score tells how easy a token is to predict, but not which earlier tokens it depends on. MAPLE supervises exactly these pairwise relations (Section 5): a position is ready only once all of its prerequisite tokens are revealed.

To illustrate the benefit of this dependency information, consider a reasoning sequence that contains the step "6 × 2 = 12". The result "12" depends on its operands "6" and "2".

  • Confidence can be high before the operands are revealed. The model predicts every masked position from the revealed context. From the problem statement and the earlier steps it can anticipate this step, so it can give a high probability to one value at the result position while the operands are still masked.
  • Committing the result at that point is harmful. That value rests on the model's guess of the operands, not on the operand tokens that end up in the sequence. Masked positions are predicted independently of each other, so the two can disagree, and the sequence can read "6 × 2 = 36". A committed token is not revised, so the error carries through to the final answer.
  • Confidence-based training does not address this. It trains the model along the order that its own confidence produces, so nothing tells the model that the result should wait.
  • MAPLE makes the result wait. The operands are prerequisites of the result, so the model learns to commit the result after they are revealed, when it can be computed from them. Fig. 5 (Appendix I) shows this step.

Revision: we have added PAPL to Table 1 and Section 6.1, with its setup in Appendix B.4.

AuthorsOpenReview ↗

Response to Reviewer jZ7M (2/2): component ablation and graph ablation

W2. It is unclear which component produces the gains. MAPLE changes both how the training contexts are sampled and how confidence is supervised. It would be nice to see these changes ablated separately…

Setup. The dependency graph enters MAPLE's objective (Eq. 15) through three components:

  • State sampling: the training contexts are sampled along the graph.
  • Token-loss expectation: the token loss puts more weight on graph-ready positions.
  • Position-selection KL: the confidence is supervised toward graph-ready positions.

We retrain LLaDA 2 on FineCode with every combination, following the same setup as described in Section 6 and Appendix B. A component marked ✗ falls back to its any-order form: uniform state sampling, uniform token-loss weighting, or no KL.

VariantState samplingToken-loss expectationPosition-selection KLHumanEvalMBPPLCB ProSpiderAvg.
MAPLE (full)✓✓✓84.1581.714.9651.0655.47
− state sampling✗✓✓83.5478.994.3947.7853.67
− token-loss expectation✓✗✓81.1079.383.9749.6153.51
− KL✓✓✗82.3280.164.5349.9054.23
only state sampling✓✗✗81.1079.773.6848.9453.37
only token-loss expectation✗✓✗84.1579.774.1145.6553.42
only KL✗✗✓81.7176.263.9742.3651.07
Any-order✗✗✗82.9377.044.5340.4351.23

All three components help.

  • Each one is needed: removing any one of them lowers the average by 1.2–2.0 points.
  • They are complementary: no single component reaches the full recipe (51.07–53.42 vs. 55.47).
  • The two changes named in the review: "how the training contexts are sampled" corresponds to state sampling, and "how confidence is supervised" to the KL. Removing the first lowers the average by 1.8 points, and removing the second by 1.2 points.

Full MAPLE is best or tied-best on all four benchmarks. All variants decode at similar parallelism on every benchmark (tokens per forward within about 5% of each other).

Revision: we have added this table as Appendix J.1, with a summary in Section 6.4.


W3. The paper does not compare teacher-derived graphs against random graphs or simple ordering rules. Such comparisons would show whether the gains come from useful dependency information or merely from restricting reveal orders. An empty graph baseline is not sufficient in this case.

Setup. We keep MAPLE's objective and replace the teacher graph on LLaDA 2 / FineCode by:

  • A degree-matched random graph: every token keeps the number of parents it has in the teacher graph, but its parents are drawn at random among earlier tokens.
  • Simple ordering rules: a strict chain (each token's parent is the previous token, i.e., left-to-right order) and a group chain (left-to-right order in groups of three consecutive tokens).

The graph changes how parallel the trained model decodes at a given confidence threshold. A chain, for instance, trains a nearly sequential decoder. We therefore compare all graphs at the same parallelism: the table below reports accuracy at 3 tokens per forward.

Training graphHumanEvalMBPPLCB ProAvg.
Teacher dependency graph (MAPLE)83.1278.094.9655.39
Degree-matched random graph82.6774.803.9753.81
Group chain51.8755.090.5735.84
Strict chain†71.95†69.26†1.84†47.68†
Empty graph (any-order)79.8574.774.5353.05

† The strict chain does not reach 3 tokens per forward on any benchmark: even at a confidence threshold as low as 0.1, it decodes only about 1.1 tokens per forward. The reason is that a strict chain makes only one position ready at a time, the next token, so the model learns to be confident about that position alone. Its row reports the accuracy at the 0.1 threshold.

The gains come from the dependency information. The teacher graph is the best on all three benchmarks, ahead of the random graph and of both ordering rules.

  • Random graph: with the same in-degrees but random parents, accuracy drops on all three benchmarks, and the average falls from 55.39 to 53.81.
  • Simple ordering rules: the group chain reaches 35.84. The strict chain reaches 47.68 while decoding only about 1.1 tokens per forward.

Revision: we have added this table to the main text as Table 4 (Section 6.4), with the construction of each graph in Appendix J.2.


We hope these results address all three points. We are happy to provide further details.

Thank you for the additional results based on the questions I had, and they have addressed my concerns. As a result I have increased my score to a 4.

We are glad that our response has addressed your concerns, and we greatly appreciate your constructive feedback!

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

My understanding is that this paper asks how masked diffusion language models (MDLMs) can learn to reveal the tokens needed for a prediction before making it, without sacrificing parallel generation. The authors describe these prerequisite relations with a DAG, which lets them express autoregressive and any-order generation, as well as blockwise generation, within the same formulation. MAPLE uses graphs extracted by a frozen teacher from completed training sequences to define a distribution over token reveal orders. For the theoretical objective, the authors derive an exact negative ELBO that jointly models position selection and token prediction, and show that its population global minimizers recover the data sequence distribution under transition realizability. I take the practical aim to be teaching the model's existing confidence scores to reflect these prerequisites, so that inference can use the original parallel decoder without consulting the teacher or graph. The experiments with LLaDA 2 and DreamReasoner report accuracy gains on mathematical reasoning and code generation, with Figure 1 showing comparable parallelism in the evaluated settings. The separate dependency-violation analysis on LLaDA 2/FineMath reports lower average rates under all three judges.

Critical strengths

S1. I see a practical advantage in using sequence-specific prerequisite relations during training without changing the MDLM architecture or its confidence-based parallel decoder. MAPLE requires neither a separate position-selection head nor graph construction or lookup during generation. Section 6 also confirms that all MAPLE results use the standard confidence-based decoder and that the graph is never consulted at inference. This should make it easier to use dependency supervision in existing MDLMs with confidence-based decoding, although the offline cost of extracting graphs with the teacher remains.

S2. The results on both LLaDA 2 and DreamReasoner make the accuracy gains more convincing to me. MAPLE achieves the highest average accuracy in mathematics and code for each backbone and is best or tied-best in 11 of the 14 backbone-benchmark comparisons. Within each backbone-corpus group, the training runs start from the same checkpoint and source corpus and use matched model-forward budgets. Figure 1 and Section 6.2 also report higher accuracy with comparable returned-token parallelism at the shared confidence threshold of 0.95 in the three evaluated settings. These comparisons suggest that MAPLE does not obtain its accuracy gains simply by making generation more sequential.

Critical weaknesses

W1. If I understand correctly, the practical objective combines graph-induced state sampling, a graph-dependent token-loss expectation, and a projected position-selection KL term. The main-text experiments compare MAPLE as a whole with existing methods, but I could not find an ablation separating these components or a control that disrupts prerequisite relations while preserving acyclicity and basic graph statistics. Section 6 and Table 1 include comparisons with the standard any-order objective, other training methods, and inference-time reordering methods, but these do not isolate the contribution of the pairwise relations. I would therefore want to see whether the gains remain when those relations are disrupted. I consider the lack of such evidence a substantial weakness because Section 5 identifies sequence-specific relational supervision, together with graph-free confidence decoding, as the paper's contribution.

W2. In Section 6.3, dependencies are extracted after generation from each method's own completed response. My concern is that violation rates may change because methods produce different responses and thus different edge sets, even beyond differences in reveal order. MAPLE has the lowest average violation rate under all three judges, but Table 3 does not show whether edge counts, coverage, or dependency distances differ across methods. The text acknowledges density differences between judges and compares methods within each judge. Before interpreting the results as evidence of a "general prerequisite-first generation behavior", I would want to know whether differences in the extracted edge sets could account for the lower violation rates. A supplementary comparison on common responses could help separate this effect from differences in reveal order.

Questions for authors

Q1. Section 5 distinguishes MAPLE's pairwise prerequisite supervision from the per-position scores used by earlier methods. AGDO's valid attention scores also depend on which tokens are already unmasked. Could the authors explain more precisely what information the explicit prerequisite DAG retains that is lost when dependencies are aggregated into these scores?

Q2. In Equation (15), could the authors include the conditioning arguments in the KL term and the inner expectation, as in Equation (9), to make their dependence on the sampled state explicit?

Q3. Section 6 uses counterfactual graphs for two backbone-corpus groups and attention graphs for the other two. Could the authors briefly state how these choices were made, including which data and metric were used for selection?

Q4. Table 2 reports training GPU-hours for LLaDA 2 excluding graph construction. How much additional compute does offline graph extraction require for FineMath and FineCode, and what is MAPLE's total cost relative to the any-order baseline when this step is included?

Q5. Section 4.2 explicitly distinguishes the practical objective in Equation (15) from the exact negative ELBO in Equation (9). Could the conclusion make the same distinction when discussing sequence-marginal optimality, so that the guarantee is not read as applying directly to the practical objective?

6 comments
AuthorsOpenReview ↗

Response to Reviewer axwb (1/4): component ablation and relation-disruption control

Thank you for the careful and detailed review! We address every point below. New experiments use the same setting as Table 1 (see Appendix B for hyperparameter details).

Weaknesses

W1. … the practical objective combines graph-induced state sampling, a graph-dependent token-loss expectation, and a projected position-selection KL term … I could not find an ablation separating these components or a control that disrupts prerequisite relations while preserving acyclicity and basic graph statistics … I would therefore want to see whether the gains remain when those relations are disrupted.

We ran both experiments on LLaDA 2 / FineCode, following the same setup as described in Section 6 and Appendix B.

Component ablation. We retrain with every combination of the three components. A component marked ✗ falls back to its any-order form: uniform state sampling, uniform token-loss weighting, or no KL.

VariantState samplingToken-loss expectationPosition-selection KLHumanEvalMBPPLCB ProSpiderAvg.
MAPLE (full)✓✓✓84.1581.714.9651.0655.47
− state sampling✗✓✓83.5478.994.3947.7853.67
− token-loss expectation✓✗✓81.1079.383.9749.6153.51
− KL✓✓✗82.3280.164.5349.9054.23
only state sampling✓✗✗81.1079.773.6848.9453.37
only token-loss expectation✗✓✗84.1579.774.1145.6553.42
only KL✗✗✓81.7176.263.9742.3651.07
Any-order✗✗✗82.9377.044.5340.4351.23
KL without projection†✓✓✓†82.9380.164.3950.5854.51

† The KL target is the graph teacher h~Gε\tilde h^{\varepsilon}_G itself, as in the exact ELBO (Eq. 9), instead of the projected target hprojh^{\mathrm{proj}} (Eq. 14).

  • All three components help: removing any one of them lowers the average by 1.2–2.0 points, and no single component reaches the full recipe (51.07–53.42 vs. 55.47).
  • The projection helps: without it, the average drops from 55.47 to 54.51.
  • Parallelism: all variants decode at similar parallelism on every benchmark (tokens per forward within about 5% of each other).

Relation-disruption control. We keep the objective and replace the teacher graph by a degree-matched random graph. Every token keeps the number of parents it has in the teacher graph, so in-degrees, edge count and roots are preserved. Its parents are drawn at random among earlier tokens, so the graph stays acyclic. We also test two simple ordering rules: a strict chain (left-to-right order) and a group chain (left-to-right order in groups of three consecutive tokens).

The graph changes how parallel the trained model decodes at a given confidence threshold; a chain, for instance, trains a nearly sequential decoder. We therefore compare all graphs at the same parallelism: the table below reports accuracy at 3 tokens per forward.

Training graphHumanEvalMBPPLCB ProAvg.
Teacher dependency graph (MAPLE)83.1278.094.9655.39
Degree-matched random graph82.6774.803.9753.81
Group chain51.8755.090.5735.84
Strict chain†71.95†69.26†1.84†47.68†
Empty graph (any-order)79.8574.774.5353.05

† The strict chain does not reach 3 tokens per forward on any benchmark: even at a confidence threshold as low as 0.1, it decodes only about 1.1 tokens per forward. The reason is that a strict chain makes only one position ready at a time, the next token, so the model learns to be confident about that position alone. Its row reports the accuracy at the 0.1 threshold.

  • Disrupting the relations lowers accuracy on all three benchmarks: the average falls from 55.39 to 53.81.
  • Simple ordering rules: the group chain reaches 35.84. The strict chain reaches 47.68 while decoding only about 1.1 tokens per forward.

The gains therefore depend on the teacher's specific prerequisite relations, not only on acyclicity and in-degree statistics.

Revision: we have added the graph controls to the main text as Table 4 (Section 6.4), with their construction in Appendix J.2, and the component ablation as Appendix J.1.

AuthorsOpenReview ↗

Response to Reviewer axwb (2/4): Table 3 edge statistics and common-response analysis

W2. … violation rates may change because methods produce different responses and thus different edge sets … Table 3 does not show whether edge counts, coverage, or dependency distances differ across methods … A supplementary comparison on common responses could help separate this effect from differences in reveal order.

Edge statistics of Table 3. Number of edges that Table 3 scores for each method, on each model's own responses (pooled over the five benchmarks):

MethodAttention judgeCounterfactual judgeValueFlow judge
Any-order282.9k347.8k31.0k
Efficient-DLM285.1k353.9k33.1k
TRIMS287.7k377.7k31.2k
PUMA285.5k347.2k28.7k
MAPLE286.7k392.6k34.1k

MAPLE's responses carry about as many scored edges as the baselines' or more, so its lower violation rate in Table 3 does not come from a sparser edge set.

Common-response analysis. Following the suggestion, we also remove the response and its edges as variables.

  • Common responses: all five methods are scored on the same 145 responses (28–30 per benchmark). They were generated by the any-order model and taken without filtering for correctness.
  • Same edges: each judge extracts its edges once per common response, as in Table 3. All methods are scored against these same edges.
  • Own reveal order: each model decodes every common response with its standard confidence decoder. Whenever it commits a position, we fill in the common response's token at that position instead of the model's own prediction. Every model thus produces the same text, in its own reveal order.

Edge counts, coverage and dependency distances are therefore identical for all methods. Only the reveal order differs.

Violation rate (%, ↓) on the common responses:

JudgeMethodMATHAIME24AIME25AMCOBAvg.
AttentionAny-order9.138.227.927.987.998.25
Efficient-DLM8.807.858.207.857.828.10
TRIMS10.118.238.908.868.538.92
PUMA9.747.778.207.297.838.17
MAPLE6.435.705.605.645.915.85
CounterfactualAny-order40.9437.5635.8538.0138.9938.27
Efficient-DLM41.0737.5536.2637.8838.7438.30
TRIMS42.5738.4436.6838.7440.0239.29
PUMA41.7837.8436.2937.5339.1238.51
MAPLE29.3926.2724.6125.5227.4226.64
ValueFlowAny-order45.0439.5751.3150.2255.3248.29
Efficient-DLM45.4633.9740.2048.5256.1044.85
TRIMS43.4939.5144.6552.0251.5646.25
PUMA47.8544.3845.6950.9550.5947.89
MAPLE40.9835.4436.2940.1545.8439.74
  • Counterfactual judge: MAPLE is 11–13 points below every baseline on every benchmark.
  • Attention judge: MAPLE is the lowest on every benchmark.
  • ValueFlow judge: MAPLE is the lowest on four of the five benchmarks and on average.

With identical responses and edges, MAPLE has the lowest average violation rate under all three judges. Its lower violation rates therefore come from its reveal order, not from differences in responses or edge sets.

Revision: we have added both tables to Appendix B.7 (Tables 8 and 9), with a summary in Section 6.3.

AuthorsOpenReview ↗

Response to Reviewer axwb (3/4): Q1 (AGDO) and Q2 (Eq. 15)

Questions

Q1. … AGDO's valid attention scores also depend on which tokens are already unmasked. Could the authors explain more precisely what information the explicit prerequisite DAG retains that is lost when dependencies are aggregated into these scores?

We agree that AGDO's score depends on which tokens are revealed. The difference lies in how the dependencies are combined.

AGDO: a sum over revealed tokens. For a masked token ii, AGDO computes Si=∑k∈UAˉi,kS_i=\sum_{k\in\mathcal U}\bar A_{i,k}. Here Aˉi,k\bar A_{i,k} is the attention that token ii pays to token kk, and U\mathcal U is the set of revealed tokens. To build its training order, AGDO repeatedly reveals the masked tokens with the highest SiS_i. Because SiS_i is a sum, attention to any revealed token raises it. Many revealed tokens that matter little can make up for one missing token that matters, so a token can rank high while a token it depends on is still masked.

MAPLE: all of a token's prerequisites. MAPLE keeps which tokens are the prerequisites of each position. Position ii is ready only when every one of them is revealed (Eq. 5): i∈RG(O)  ⟺  AncG(i)⊆Oi\in R_G(O)\iff \mathrm{Anc}_G(i)\subseteq O. Here OO is the set of revealed positions, AncG(i)\mathrm{Anc}_G(i) is the set of prerequisites of ii (its ancestors in the graph GG), and RG(O)R_G(O) is the set of ready positions. If a single prerequisite is still masked, the position is not ready, however much other context is revealed.

Example (Fig. 5, Appendix I). The task is the area of a pentagon by the shoelace formula. One term of the formula is the product of 6 and 2. Below, ▢ is a masked token and formatting tokens are omitted.

Any-order model (final answer: 8, wrong)
  step 1:  ▢ ▢ )( ▢ ) + ▢ ▢ )( ▢ ) ▢ ▢ ▢ ▢ ▢ ▢ ...
  step 2:  ▢ 0 )( 2 ) + ( 0 )( 6 ) + ( 6 )( 2 ) + ( 6 )( 0 ) + ( 2 )( 0 ) = 0 + 0 + 36 + ▢ ...
           "36" is committed in the same step as its factors 6 and 2. The correct product is 12.

MAPLE (final answer: 20, correct)
  step 3:  0·2 = 0    0·6 = 0    6·2 ▢ ▢▢    ▢ ...
  step 4:  0·2 = 0    0·6 = 0    6·2 = 12    ▢ ...
           "12" is committed one step after its factors 6 and 2.

Consider the token that holds the product. With prerequisite edges from the two factors, MAPLE's training signal treats this token as not ready until both 6 and 2 are revealed, so the model learns to commit it after them. A summed score has no such requirement: the revealed brackets, operators and earlier zero products all add to SiS_i, so the product token can be selected while its factors are still masked. The any-order model above shows what such a premature commit costs.

Revision: we have updated Section 5 to state the distinction in these terms: a summed per-position score vs. readiness that requires all of a token's prerequisites.


Q2. In Equation (15), could the authors include the conditioning arguments in the KL term and the inner expectation, as in Equation (9), to make their dependence on the sampled state explicit?

Yes, thanks for the suggestion to make the presentation clearer. With zk=z(Ok,x)z_k=z(O_k,x), we have re-written Eq. 15 as

Lε,Gproj(x;θ)=∑k=0L−1EOk∼dkε,G(⋅∣x)[KL(hθ,Gproj,ε(⋅∣Ok,zk) ∥ κθ(⋅∣zk))+Ei∼h~Gε(⋅∣Ok,x)[−log⁡πθ,i(xi∣zk)]].\mathcal L_{\varepsilon,G}^{\mathrm{proj}}(x;\theta)=\sum_{k=0}^{L-1}\mathbb E_{O_k\sim d_k^{\varepsilon,G}(\cdot\mid x)}\Big[\mathrm{KL}\big(h_{\theta,G}^{\mathrm{proj},\varepsilon}(\cdot\mid O_k,z_k)\thinspace\big\Vert\thinspace\kappa_\theta(\cdot\mid z_k)\big)+\mathbb E_{i\sim\tilde h_G^{\varepsilon}(\cdot\mid O_k,x)}\big[-\log\pi_{\theta,i}(x_i\mid z_k)\big]\Big].

Both the KL target and the token expectation depend on the sampled revealed set OkO_k. The objective itself is unchanged.

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

MAPLE uses a frozen teacher to extract prerequisite DAGs from training sequences. These graphs guide partial-context sampling and reveal-position supervision during continued training. The paper formulates a joint position–token generator, derives an exact negative ELBO, and develops a practical confidence-based objective. Inference retains the original parallel decoder without using a graph or teacher. Experiments on LLaDA 2 and DreamReasoner evaluate math, code, and text-to-SQL performance, decoding parallelism, and dependency violations.

Critical strengths
  1. MAPLE uses context-dependent prerequisite relations as a training signal while retaining the original parallel decoder. This provides relational supervision without adding a teacher, graph, or new module at inference.

  2. The experiments include matched continued-training controls and comparisons with Efficient-DLM, TRIMS, and PUMA across two model families. Math/code macro-averages improve in all four model–corpus settings, and dependency-violation analyses provide complementary behavioral evidence. These results support the complete training recipe.

Critical weaknesses

The exact confidence-to-position mapping and graph-softening settings are not fully specified. Existing controls support the complete recipe but do not fully isolate the value of prerequisite relations. The focus on math/code and text-to-SQL also leaves broader applicability and general-capability retention uncertain.

Questions for authors

Do you have evidence that MAPLE benefits tasks beyond math/code and text-to-SQL, such as factual knowledge or general language tasks? After math/code continued training, how well do its checkpoints retain general capabilities relative to an Any-order baseline matched in initialization, training data, and budget?

3 comments
AuthorsOpenReview ↗

Response to Reviewer Smiv (1/2): settings and the value of prerequisite relations

Thank you for the positive assessment and the precise questions! New experiments use the same setting as Table 1 (see Appendix B for hyperparameter details).


The exact confidence-to-position mapping and graph-softening settings are not fully specified.

Confidence-to-position mapping. κθ\kappa_\theta uses the same confidence that the decoder thresholds. For each masked position ii,

ci=max⁡v≠[MASK]πθ,i(v∣z),κθ(i∣z)=ci∑j∈U(z)cj,c_i=\max_{v\neq\texttt{[MASK]}}\pi_{\theta,i}(v\mid z),\qquad \kappa_\theta(i\mid z)=\frac{c_i}{\sum_{j\in U(z)}c_j},

where cic_i is the confidence at position ii and U(z)U(z) is the set of masked positions. This is a softmax over log⁡ci\log c_i at temperature 1.

Graph-softening settings. We set ε=0.1\varepsilon=0.1 in Eq. 15 for all backbone–corpus groups except LLaDA 2 / FineCode, where ε=0.2\varepsilon=0.2.

Revision: we have added the mapping and these values of ε\varepsilon to Appendix B.3 and Table 6.


Existing controls support the complete recipe but do not fully isolate the value of prerequisite relations.

We isolate the value of the prerequisite relations on LLaDA 2 / FineCode from two perspectives: replacing the teacher graph while keeping MAPLE's objective, and removing the graph from individual components of the training objective.

(1) Graph perspective. We keep MAPLE's objective and replace the teacher graph by:

  • A degree-matched random graph: every token keeps the number of parents it has in the teacher graph, but its parents are drawn at random among earlier tokens.
  • Simple ordering rules: a strict chain (each token's parent is the previous token, i.e., left-to-right order) and a group chain (left-to-right order in groups of three consecutive tokens).

The graph changes how parallel the trained model decodes at a given confidence threshold; a chain, for instance, trains a nearly sequential decoder. We therefore compare all graphs at the same parallelism: the table below reports accuracy at 3 tokens per forward.

Training graphHumanEvalMBPPLCB ProAvg.
Teacher dependency graph (MAPLE)83.1278.094.9655.39
Degree-matched random graph82.6774.803.9753.81
Group chain51.8755.090.5735.84
Strict chain†71.95†69.26†1.84†47.68†
Empty graph (any-order)79.8574.774.5353.05

† The strict chain does not reach 3 tokens per forward on any benchmark: even at a confidence threshold as low as 0.1, it decodes only about 1.1 tokens per forward. The reason is that a strict chain makes only one position ready at a time, the next token, so the model learns to be confident about that position alone. Its row reports the accuracy at the 0.1 threshold.

The prerequisite relations carry value of their own.

  • Teacher graph vs. random graph: with the same objective and the same in-degrees, replacing the teacher's prerequisites by random ones lowers accuracy on all three benchmarks. The average falls from 55.39 to 53.81.
  • Simple ordering rules: the group chain reaches 35.84. The strict chain reaches 47.68 while decoding only about 1.1 tokens per forward.

(2) Objective perspective. The graph enters three components of MAPLE's objective: state sampling, the token-loss expectation and the position-selection KL. We retrain with every combination of the three components. A component marked ✗ falls back to its any-order form: uniform state sampling, uniform token-loss weighting, or no KL. Removing the graph from all three gives the any-order baseline. The setup is that of Table 1.

VariantState samplingToken-loss expectationPosition-selection KLHumanEvalMBPPLCB ProSpiderAvg.
MAPLE (full)✓✓✓84.1581.714.9651.0655.47
− state sampling✗✓✓83.5478.994.3947.7853.67
− token-loss expectation✓✗✓81.1079.383.9749.6153.51
− KL✓✓✗82.3280.164.5349.9054.23
only state sampling✓✗✗81.1079.773.6848.9453.37
only token-loss expectation✗✓✗84.1579.774.1145.6553.42
only KL✗✗✓81.7176.263.9742.3651.07
Any-order✗✗✗82.9377.044.5340.4351.23

The graph contributes through every component of the objective. MAPLE is best on every benchmark. Removing the graph from one component lowers the average by 1.2–2.0 points, from two by 2.1–4.4, and from all three (any-order) by 4.2. The KL helps in combination with the other components.

Revision: we have added the graph controls to the main text as Table 4 (Section 6.4), with their construction in Appendix J.2, and the component ablation as Appendix J.1.

AuthorsOpenReview ↗

Response to Reviewer Smiv (2/2): generality and retention of general capabilities

The focus on math/code and text-to-SQL also leaves broader applicability and general-capability retention uncertain. … Do you have evidence that MAPLE benefits tasks beyond math/code and text-to-SQL, such as factual knowledge or general language tasks? After math/code continued training, how well do its checkpoints retain general capabilities relative to an Any-order baseline matched in initialization, training data, and budget?

Setup. We evaluate the LLaDA 2 checkpoints of Table 1 on seven general-domain benchmarks outside the training domains, each in full. They cover factual knowledge in English and Chinese (MMLU, C-Eval), science reasoning (ARC-Challenge, GPQA-Diamond), commonsense language understanding (HellaSwag, WinoGrande) and instruction following (IFEval). All checkpoints are trained with the setup described in Section 6 and Appendix B, so all baselines are matched to MAPLE in initialization, training data and budget. All checkpoints use the same decoder and the same answer parser.

LLaDA 2MMLUARC-ChallengeHellaSwagWinoGrandeIFEvalC-EvalGPQA-DiamondAvg.
Trained on FineMath
Any-order72.8388.2382.1367.7271.1675.7229.2969.58
Efficient-DLM72.2588.7482.0866.7767.8475.9918.1867.41
TRIMS72.4089.2582.4266.9373.0176.1026.7769.55
PUMA72.7989.9381.9067.4872.4676.2029.2970.01
MAPLE74.9691.0482.7666.6974.6876.6030.3071.01
Trained on FineCode
Any-order72.3789.7682.9067.3275.6075.0227.2770.04
Efficient-DLM72.6089.7682.1466.9377.4575.0233.8471.11
TRIMS74.1390.7083.6467.0979.3076.2030.8171.70
PUMA71.6488.0580.7467.2578.0074.0028.7969.78
MAPLE75.1191.8183.4367.0976.5277.7931.3171.87

Bold marks the best result within each corpus.

MAPLE outperforms the matched any-order baseline on six of the seven benchmarks, in both corpora.

  • Seven-benchmark average: MAPLE has the best average of all five methods in both corpora, 1.4 points (FineMath) and 1.8 points (FineCode) above the matched any-order model.
  • MMLU and ARC-Challenge: MAPLE gains more than 2 points over the matched any-order model on both, in both corpora.
  • IFEval, C-Eval and GPQA-Diamond: MAPLE is above the matched any-order model on all three, in both corpora. After FineMath training it is the best of all methods on all three.

MAPLE's benefits therefore extend beyond the domains it is trained on, including factual knowledge and general language tasks.

Broader applicability. MAPLE applies to any corpus on which a frozen teacher can annotate token-level dependencies, and the decoder is the standard MDLM decoder.

Revision: we have added these evaluations as Appendix K.


We hope these additions fully address your questions. We are happy to provide further details.

AuthorsOpenReview ↗

Follow-up before the discussion period closes (Nov 18, AoE)

Dear Reviewer Smiv,

Thank you again for your time and valuable feedback! As the discussion period closes at the end of today (November 18, AoE), we would like to kindly follow up on our responses.

We hope our responses have fully addressed your concerns; if so, we would greatly appreciate it if you would consider updating your assessment. In any case, we are more than happy to continue the discussion with you.

We truly appreciate your time and effort in reviewing our paper!

Authors

Comments on the paper

1 comment
AuthorsOpenReview ↗

Revised paper: summary of changes

We thank all reviewers for their constructive feedback. We have uploaded a revised paper. Text added or changed in response to the reviews is colored by the request it answers: purple for points raised by several reviewers, orange for Reviewer jZ7M, blue for Reviewer axwb, and teal for Reviewer Smiv. The main changes:

  • Ablations (all reviewers): graph controls in the main text (Section 6.4, Table 4) and a component ablation (Appendix J.1).
  • PAPL baseline (jZ7M): Table 1 and Appendix B.4.
  • Dependency compliance (axwb): edge statistics and a common-response analysis (Appendix B.7, summary in Section 6.3).
  • Graph construction (axwb): an offline indicator for choosing it (Appendix H.3) and its one-time extraction cost (Appendix H.4, Table 2 caption).
  • Clarifications (axwb): Section 5 (AGDO), Equation 15 and the conclusion.
  • Settings and general capability (Smiv): the confidence-to-position mapping and ε (Appendix B.3, Table 6), and seven general-domain benchmarks (Appendix K).

We are happy to answer any further questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.