CARVE: Verified Expansion for Variable-Length Generation in Diffusion Language Models

AI summary

Overview

• Research area: Efficient inference and decoding algorithms for masked diffusion language models (dLLMs), a family that generates text by iteratively denoising a canvas of masked tokens rather than emitting tokens left to right.
• Technical level: Advanced. The paper assumes familiarity with masked discrete diffusion, denoising schedules, and information-theoretic divergences, though the core idea is describable in plain terms.
• Scope: A training-free decoding algorithm, CARVE, that lets a masked diffusion model grow its response canvas during decoding, accepting each proposed expansion only when it provably leaves predictions at unresolved positions stable.

What This Paper Is About

Masked diffusion language models must decide the response length before decoding starts, which is a bad fit for open-ended generation: too short a canvas truncates reasoning or code, too long a canvas wastes computation and can even hurt quality. Prior work showed the canvas can be expanded mid-decoding using confidence signals, but inserting new masked positions changes the denoising problem itself and can perturb predictions at positions that are still unresolved. CARVE's goal is to make canvas growth a verified stability decision rather than a confidence heuristic, without retraining the model.

Key Contributions

1. CARVE itself: a training-free variable-length algorithm that verifies each proposed canvas expansion by measuring Jensen–Shannon (JS) divergence between the base and expanded predictive distributions at aligned unresolved positions.
2. A model-agnostic mechanism: the same algorithm is instantiated for two different masked diffusion backends, full-canvas Dream decoding and blockwise LLaDA decoding, with the pretrained denoising model left fixed.
3. Empirical gains across code and mathematical reasoning benchmarks on three diffusion LMs, with average performance improved over fixed-length baselines for every evaluated model family, often at lower inference FLOPs.
4. A control study of the components, separately ablating the adaptive reveal rule, EOS cropping, the JS threshold, and the insertion mode, to show the gains do not come from a single shortcut.

Main Findings

• Average accuracy improves on all three models. Relative to fixed-length decoding, CARVE raises the unweighted four-benchmark average by 0.92, 1.03, and 0.49 percentage points on Dream-v0-Instruct-7B, LLaDA-1.5, and LLaDA-8B-Instruct respectively.
• Per-task effects are mixed. CARVE improves 9 of the 12 model–benchmark pairs. The largest single gain is on HumanEval for Dream at +4.27 points. On LLaDA-8B-Instruct, DAEDAL attains the higher average (53.42 versus 53.20 for CARVE).
• Reported baseline and CARVE scores. Dream-v0-Instruct-7B: baseline 58.80 average versus CARVE 59.73. LLaDA-1.5: baseline 52.81 versus CARVE 53.84. LLaDA-8B-Instruct: baseline 52.71 versus CARVE 53.20.
• Accuracy gains come with lower compute, not more. CARVE reaches roughly half the FLOPs of fixed-length decoding in some settings. In the component ablation, normalized FLOPs are 0.51× for Dream, 0.78× for LLaDA-1.5, and 0.85× for LLaDA-8B.
• The adaptive reveal schedule drives efficiency. On Dream-v0-Instruct-7B, swapping Dream's original commit schedule for the adaptive rule raised average accuracy from 58.17 to 59.73 while cutting average forward passes from 200.9 to 148.9.
• The JS threshold controls a real trade-off. Sweeping the threshold over {0.01, 0.02, 0.05, 0.10} on LLaDA-8B showed that 0.01 rejects many expansions and coincides with lower accuracy, while 0.05 and 0.10 accept nearly all proposals and make verification almost vacuous. The default is 0.02.
• Insertion location depends on the backbone. Mid-insert beat tail insertion on Dream-7B (59.73 versus 59.00) and LLaDA-1.5 (53.84 versus 52.88), while tail insertion was stronger on LLaDA-8B (54.29 versus 53.20).
• Verification is not a free pass. Removing the verification forward pass in an always-expand control reduced accuracy relative to CARVE on the LLaDA backends while saving only a small amount of compute; on Dream the two variants were close.
• A small fixed canvas alone is not enough. Fixing the canvas at half the maximum length, disabling expansion, and using EOS cropping produced much lower averages: 53.03 on Dream, 49.65 on LLaDA-1.5, and 46.84 on LLaDA-8B.
• Scope of the guarantee is narrow and stated explicitly. The JS criterion measures local predictive stability; it does not guarantee positionwise preservation, semantic correctness, or output safety.

Methodology in Plain English

The method starts from a shorter response canvas (half the maximum length) and lets it grow during decoding. At each expansion opportunity, the model first runs on the current canvas, called the base branch, and its per-position predictive uncertainty is measured by entropy. The algorithm finds the anchor position whose local window has the highest total entropy, meaning the region where the model is least sure how to continue, and proposes inserting a block of new mask tokens immediately after that anchor. This creates a second canvas, the expanded branch.

The model is then run once more on the expanded branch, and the two sets of predictions are compared. Because insertion shifts every position to the right of the anchor, the method defines an alignment mapping so that each original position is matched with its counterpart in the expanded canvas. Only positions that were still masked in the base canvas are compared; already-committed tokens and the newly inserted masks themselves are excluded. At each aligned unresolved position the JS divergence between the base and expanded predictive distributions is computed, and these are averaged into a single verification score.

If that mean score falls below a fixed threshold, the expansion is accepted and decoding continues on the expanded canvas. Otherwise the proposal is discarded as a destabilizing edit and decoding continues on the base canvas. Crucially, tokens are never committed using logits from a canvas other than the one being updated.

Three supporting mechanisms are added. An adaptive reveal rule distributes the remaining masks evenly across the remaining denoising steps, guaranteeing at least one reveal per step while masks remain, instead of a schedule whose reveal count can round to zero. EOS cropping stops decoding at the useful prefix once an end-of-sequence token is committed, discards everything after it, and greedily fills any remaining masks with a single final forward pass. Expansion attempts are made only every I steps, so the average forward passes per step is roughly 1 + 1/I times the underlying decoder before the canvas hits its maximum length.

Why This Matters

For research, the paper reframes length control in diffusion language models as a counterfactual stability question rather than a confidence heuristic, and shows that pretrained dLLMs already carry the signals needed for safe length adaptation without retraining or architectural change. It also provides a component-level decomposition showing which parts of the pipeline matter for accuracy versus efficiency, which is useful for anyone comparing variable-length decoders.

Real-world applications:

• Code generation and code completion, where response length varies enormously by prompt and a truncation error means broken code.
• Mathematical and multi-step reasoning, where a short canvas can cut off intermediate steps before the final answer.
• Cost-sensitive deployment of diffusion LMs, since the reported FLOP reductions of up to roughly half translate directly into serving cost.
• Any open-ended instruction-following workload where users cannot reliably predict how long an answer should be before generation begins.

Industry relevance is concentrated in serving infrastructure. Because CARVE changes only inference, requiring no retraining and no model modification, it can be layered onto existing Dream or LLaDA deployments. The combination of higher average accuracy and lower FLOPs is the kind of dual improvement that matters for throughput-bound production systems.

Future Directions

• Adaptive insertion size. CARVE currently inserts a fixed number of mask tokens per accepted expansion, set to k = 16 in the main configurations. Deciding how many masks to insert, not just where, based on prompt-specific uncertainty or length requirements is left open.
• Softer alignment for verification. The JS comparison excludes newly inserted positions because they have no counterpart in the base canvas. The authors suggest exploring softer alignment or alternative divergence criteria that also account for the behavior of the inserted positions.
• Reliability of verification across backends. Since the always-expand control was close to CARVE on Dream but worse on the LLaDA backends, the conditions under which verification genuinely matters are not fully characterized.
• Closing the gap with confidence-based baselines. DAEDAL still holds the higher average on LLaDA-8B-Instruct and the highest MATH-500 score in that setting, leaving room to understand when a stability test is preferable to a confidence signal.

Target Audience

Researchers and engineers working on diffusion language models, efficient inference, or sequence-length control in generative models. It is most valuable to readers who already understand masked discrete diffusion and decoding schedules, and to practitioners deploying Dream- or LLaDA-family models who need variable-length generation without retraining. Readers looking for a beginner-level introduction to diffusion LMs should start elsewhere, since the paper assumes the underlying formalism.

Authors’ abstract

Masked diffusion language models predict tokens from a partially observed response canvas, enabling bidirectional conditioning and parallel token refinement. Yet standard masked-diffusion decoders use a rigid inference interface: the number of masked positions allocated to the answer is fixed before generation begins. Choosing this length is difficult. A short canvas can truncate reasoning or code, while a long canvas wastes computation and can perturb denoising. We introduce CARVE (Counterfactual-Aware Reveal with Verified Expansion), a training-free variable-length algorithm for masked diffusion LMs. Starting from a shorter canvas, CARVE can grow the response during decoding by inserting additional [MASK] positions. Rather than keeping every insertion, CARVE tests a candidate expanded canvas and asks a counterfactual question: would the model make similar predictions for the unresolved positions in the original canvas if the extra masked space were present? The inserted masks are kept only when they induce low Jensen-Shannon (JS) divergence on aligned unresolved positions. This makes length growth a verified stability decision rather than a pure confidence heuristic. CARVE applies without retraining to both full-canvas and blockwise diffusion decoders. Across code generation and mathematical reasoning benchmarks, CARVE consistently improves average performance over fixed-length baselines across all evaluated model families. Crucially, CARVE achieves these accuracy gains while reducing inference cost, reaching half the FLOPs of fixed-length decoding in some settings.