What Gets Unmasked First? Trajectory Analysis of Diffusion Models for Graph-to-Text Generation

Paper: 2605.31564 Authors: Qing Wang, Jacob Devasier, Chengkai Li Categories: cs.CL, cs.AI

The Gap

Graph-to-text generation has been dominated by autoregressive LLMs that generate text left-to-right, token by token. Masked diffusion language models (MDLMs) offer an alternative: they start with all tokens masked and iteratively unmask them in parallel. But nobody has systematically studied what order MDLMs choose to unmask tokens when generating from structured graph inputs, or whether this order matters for quality.

Prior work on MDLMs focused on general text generation. When applied to graph-to-text tasks (converting knowledge graphs to natural language descriptions), researchers assumed standard supervised fine-tuning (SFT) would work. The gap: no analysis of how MDLMs’ decoding strategy interacts with graph structure, and no investigation of whether SFT preserves or disrupts the model’s natural generation priorities.

Problem: Graph-to-text needs structured reasoning
         Autoregressive = forced left-to-right order
         MDLMs = flexible unmasking order (unexplored)
            |
            v
Assumption: MDLMs might naturally align with graph structure
            SFT might interfere with this alignment
            |
            v
Method: 1. Analyze unmasking trajectories (what gets decoded first?)
        2. Identify SFT failure mode (premature structural anchoring)
        3. Propose lambda-scaled structural decoding (inference fix)
        4. Test Graph-LLaDA (explicit graph integration)
            |
            v
Evidence: MDLMs naturally decode entities > relations > structure
          SFT forces early sentence-ending tokens (fixes length prematurely)
          Lambda-scaling recovers +9.4 BLEU-4
          Graph-LLaDA generalizes better across datasets
            |
            v
Conclusion: MDLMs have implicit graph-aware decoding strategy
            Standard SFT breaks it
            Simple inference-time fix restores performance

The Increment

One sentence: Before this paper, we didn’t know MDLMs had a natural entity-first decoding strategy for graphs, or that SFT destroys it by prematurely anchoring sentence structure—now we have a training-free fix and evidence that explicit graph encoding helps generalization.

Core Mechanism

Masked diffusion models start with all tokens replaced by [MASK]. At each decoding step, the model predicts confidence scores for what each mask should be, then unmasks the highest-confidence tokens. This repeats until all masks are resolved. The key insight: the order matters.

The authors discovered MDLMs naturally follow a three-stage trajectory: (1) unmask content words (entities, attributes), (2) unmask relational and function words (prepositions, verbs), (3) unmask structural tokens (periods, sentence boundaries). This aligns with how humans might describe a graph: establish what entities exist, then explain relationships, then wrap up the sentence structure.

But supervised fine-tuning disrupts this. SFT trains the model to match reference texts exactly, which means it learns to predict sentence-ending tokens (like periods) with high confidence early in decoding. This prematurely fixes the output length before all graph content is processed, leading to omitted facts or hallucinated filler.

MDLM Decoding (one iteration):

  Input:  [MASK] [MASK] [MASK] [MASK] [MASK]
           |      |      |      |      |
           v      v      v      v      v
  Model predicts confidence for each position
           |
           v
  Unmask top-k highest confidence tokens
           |
           v
  Output: [MASK] "Paris" [MASK] "France" [MASK]
           
  Repeat until no masks remain

Structural metaphor: Think of assembling a jigsaw puzzle. The natural strategy: find corner and edge pieces first (entities—the anchors), then fill in the middle connections (relations), then trim the border to final size (structural tokens). Supervised fine-tuning is like someone insisting you cut the border to exact size *before placing all the pieces. You’re forced to either leave pieces out or cram in pieces that don’t belong, because the frame is already fixed.

Lambda-scaled structural decoding is like giving yourself permission to ignore the pre-cut frame early on. You downweight the confidence of structural tokens (multiply by lambda < 1) during early decoding steps, letting content tokens unmask first. Only in later steps do you let structural tokens compete fairly. The frame adjusts to fit the content, not vice versa.

Graph-LLaDA goes further: instead of relying on implicit graph understanding from text, it explicitly encodes the graph structure with a Graph Transformer, then conditions the MDLM decoder on these graph-aware representations. It’s like having the puzzle box image visible while assembling—you know what the final structure should look like before placing pieces.

Key Concepts

• Unmasking trajectory: In masked diffusion models, tokens aren’t generated in reading order (left-to-right). Instead, the model iteratively reveals tokens based on confidence. The *trajectory is the sequence in which tokens get unmasked across decoding steps. For example, in “Paris is the capital of France.”, the trajectory might be: step 1 unmasks “Paris” and “France” (high-confidence entities), step 2 unmasks “capital” (relation), step 3 unmasks “is”, “the”, “of” (function words), step 4 unmasks ”.” (structure). The trajectory reveals the model’s implicit generation strategy—what it considers most certain first.

• Structural anchoring: When a model predicts sentence-ending tokens (periods, question marks) with high confidence early in decoding, it effectively commits to a specific output length before processing all input information. This is “anchoring” because subsequent decoding must fit within that pre-determined structure. In graph-to-text, if the model unmasks a period after 10 tokens but the graph contains 15 facts, the model must either omit 5 facts or hallucinate filler to reach the period. The anchor constrains content generation.

• Lambda-scaling: A simple inference-time trick to delay structural token unmasking. For each structural token (periods, commas, etc.), multiply its predicted confidence by a factor lambda (e.g., 0.3). This makes structural tokens artificially less confident, so they get unmasked later. No retraining needed—just scale the logits before selecting which tokens to unmask. As decoding progresses, you can gradually increase lambda back toward 1.0, allowing structure to finalize once content is mostly resolved.

Framework Shift

Before (Autoregressive LLMs):        After (MDLMs with trajectory analysis):

Graph --> Encoder                    Graph --> Encoder
           |                                    |
           v                                    v
    Left-to-right decoding            Parallel confidence prediction
    "Paris" -> "is" -> "the"                   |
    -> "capital" -> "of"                       v
    -> "France" -> "."               Unmask by priority:
           |                          Step 1: "Paris", "France" (entities)
    Fixed generation order            Step 2: "capital" (relation)
    (structure mixed with content)    Step 3: "is", "the", "of" (function)
                                      Step 4: "." (structure)
                                               |
                                      Content-first, structure-last

One sentence: From forced sequential generation that mixes content and structure, to confidence-driven parallel unmasking that naturally separates semantic content from syntactic scaffolding.

Expert Assessment

Problem choice: Real gap. Graph-to-text is a well-studied task, but the interaction between MDLMs’ parallel decoding and structured inputs was genuinely unexplored. The trajectory analysis is novel and reveals something non-obvious: MDLMs have an implicit bias toward content-first generation that aligns with graph structure. Not a manufactured problem.

Method maturity: Lambda-scaling is almost embarrassingly simple—just multiply some logits by 0.3. But that’s a feature, not a bug. The authors identified a specific failure mode (premature structural anchoring) and proposed the minimal intervention to fix it. Graph-LLaDA is more involved but still straightforward: plug a Graph Transformer encoder into an existing MDLM architecture. No exotic training procedures or architectural gymnastics. The simplicity suggests the authors understood the problem deeply enough to avoid overengineering.

Experimental integrity: Baselines are fair. The cross-dataset evaluation (LAGRANGE benchmark) is the paper’s strongest move—it exposes that prior methods overfit to dataset-specific patterns, while LLM/MDLM approaches generalize better. The +9.4 BLEU-4 gain from lambda-scaling is substantial and reproducible (training-free, so no hyperparameter luck). One minor concern: the paper doesn’t deeply investigate *why SFT causes premature anchoring (is it the loss function? the reference text distribution?), but the empirical evidence is solid.

Writing quality: The trajectory analysis section is excellent—clear visualizations of unmasking order across decoding steps. The related work section is thin; the authors could have better positioned MDLMs relative to other non-autoregressive generation methods (insertion-based, iterative refinement). The ablation studies are thorough but buried in the appendix—some should be promoted to the main text. Overall, the paper front-loads the key insight (trajectory analysis) effectively, but the latter half feels rushed.

Verdict: Weak accept — Solid empirical contribution with a novel analysis angle (unmasking trajectories), but the theoretical understanding of *why SFT breaks the strategy is shallow, and the writing could be tighter. The simplicity of the fix (lambda-scaling) is both a strength (practical) and a weakness (feels incremental). Graph-LLaDA’s generalization results elevate the paper above a pure analysis piece.

Takeaways

For practitioners: If you’re fine-tuning masked diffusion models on structured generation tasks (not just graphs—think tables, code, formal languages), check whether your model is prematurely committing to output structure. Log the unmasking order during inference. If structural tokens (punctuation, delimiters, closing brackets) appear early, try confidence downweighting as a quick fix before retraining.

For researchers: The trajectory analysis method is transferable. Any iterative decoding model (not just MDLMs—think speculative decoding, iterative refinement) has an implicit generation order. Analyzing that order can reveal misalignments between the model’s strategy and the task structure. The gap between “what the model naturally wants to do” and “what supervised training forces it to do” is underexplored.

Specific technique: Lambda-scaled decoding is a zero-cost inference trick. If you have a set of tokens that should be resolved late (structure, formatting, metadata), just scale their logits down early in decoding and gradually restore them. No retraining, no architecture changes. Works for any model that outputs per-token confidences.