Source-linked AI summary
CARVE: Verified Expansion for Variable-Length Generation in Diffusion Language Models
Wail Bouhedja, Amr Mohamed, Guokan Shang
TL;DR
Masked diffusion decoders typically fix response length before generation, risking truncation or unnecessary computation. CARVE introduces training-free verified expansion using counterfactual JS-divergence checks, improving average performance over fixed-length decoding across evaluated tasks and models while often lowering compute. Its current limitations are fixed insertion size and alignment that excludes newly inserted positions.
Problem
Masked diffusion decoders typically require response length to be fixed before decoding, although prompts can require different lengths and unsuitable canvases can truncate responses or waste computation.
Method
CARVE is a training-free decoding method that branches to expanded canvases and accepts insertions only when aligned unresolved predictions remain sufficiently stable under a JS-divergence test.
Results
CARVE improves average performance over fixed-length baselines across code-generation and mathematical-reasoning benchmarks for each evaluated diffusion LM while often using less compute.
Takeaways & Limitations
Verified expansion improves the accuracy–compute trade-off through inference-time changes without retraining or modifying the underlying diffusion model.
Takeaways & Limitations
CARVE currently uses a fixed insertion size and verifies only pre-existing unresolved positions, excluding newly inserted masks from JS alignment.
Abstract
from arXiv · showhide
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.
1 Introduction
Masked diffusion LMs offer parallel, bidirectional generation but usually require response length to be fixed before decoding. CARVE enables verified variable-length expansion and improves accuracy while often reducing inference cost.
- Motivation: Fixed canvas lengths can truncate short responses or waste computation and harm quality when they exceed the useful response.The appropriate length varies across prompts, making variable-length decoding a central practical obstacle.
- Method: Expansion is accepted only when the added masked space leaves the model’s remaining predictive state sufficiently stable.This counterfactual test rejects insertions that destabilize unresolved predictions.
- Method: CARVE verifies proposed canvas expansions by measuring Jensen–Shannon divergence on aligned unresolved positions.It is training-free and modifies inference rather than the underlying model.
- Scope: CARVE applies to both full-canvas Dream decoding and blockwise LLaDA decoding without retraining.The same verified-expansion mechanism is used across both masked-diffusion backends.
- Results: CARVE improves average performance over fixed-length decoding across code and mathematical reasoning benchmarks while often reducing inference FLOPs.Adaptive reveal and EOS cropping can offset the cost of expansion attempts, reaching roughly half as many FLOPs in some settings.
2 Related Work
Related work addresses variable-length generation through training-time architectural changes or training-free inference heuristics. CARVE instead applies directly to pretrained masked diffusion LMs and verifies expansions through predictive stability.
- Training-time methods: Training-time variable-length methods modify generative formulations or state spaces, often requiring specialized architectural changes or costly retraining.Examples include dynamic edits and joint denoising of token identities and positional configurations.
- Training-free methods: Training-free decoding methods adjust canvas length using confidence cues, candidate scoring, or EOS-token densities.These approaches bypass retraining by changing the canvas during inference.
- CARVE: CARVE differs by framing expansion as a counterfactual stability test based on mean Jensen–Shannon divergence.It applies directly to pretrained masked dLLMs.
3 Methods
CARVE augments masked-diffusion decoding with uncertainty-guided, verified canvas expansion. It aligns original and expanded unresolved positions, accepts only low-divergence branches, and continues decoding consistently on the selected canvas.
- Preliminaries: Masked diffusion decoders iteratively denoise a fully masked response canvas while predicting masked positions in parallel.The absorbing mask process preserves masked positions until they are progressively committed.
- Preliminaries: Each output-position distribution is computed from the full partially masked canvas, enabling bidirectional conditioning.The model factorizes predictions over positions while conditioning on visible tokens across the canvas.
- Canvas expansion: Unlike standard decoding, CARVE starts at L0 and grows the canvas up to Lmax during inference.The trained denoising model remains fixed while the decoding procedure changes.
- Canvas expansion: CARVE selects an expansion anchor near the region with highest local predictive entropy.Additional masks are inserted where uncertainty suggests extra capacity may be useful.
- Verification: The expanded branch is accepted only when mean JS divergence across aligned unresolved positions falls below τJS.Newly inserted masks and already committed tokens are excluded from verification; acceptance does not guarantee every prediction is unchanged.
- Branching and cost: After verification, CARVE continues on exactly one branch and never uses logits from a different canvas than the one being updated.Expansion attempts occur every I steps and require one additional forward pass when active.
4 Experiments
CARVE is evaluated on code and mathematical reasoning benchmarks across three masked diffusion language models, against fixed-length decoding and DAEDAL. It generally improves average performance while often reducing inference cost.
- Evaluation setup: CARVE is evaluated on HumanEval, MBPP, MATH-500, and GSM8K using Dream-v0-Instruct-7B, LLaDA-1.5, and LLaDA-8B-Instruct.HumanEval and MBPP use pass@1; MATH-500 and GSM8K use exact-match accuracy after answer extraction.
- Compared methods: The comparison includes standard fixed-length decoding, DAEDAL, and CARVE, with CARVE initialized at L0 = Lmax/2 and allowed to grow to Lmax.DAEDAL is adapted to Dream for consistent comparison.
- Accuracy results: CARVE increases the unweighted four-benchmark average over fixed-length decoding by 0.92, 1.03, and 0.49 percentage points on Dream-v0-Instruct-7B, LLaDA-1.5, and LLaDA-8B-Instruct, respectively.It improves 9 of 12 model–benchmark pairs, although DAEDAL scores higher on LLaDA-8B-Instruct’s average.
- Efficiency results: CARVE often uses fewer FLOPs than fixed-length decoding despite an additional branch forward pass.Adaptive reveal and EOS cropping can offset or outweigh branching cost by shortening effective decoding trajectories.
5 Ablations
The ablations examine adaptive reveal scheduling, the JS acceptance threshold, and insertion location. They show accuracy–efficiency and selectivity trade-offs that motivate CARVE’s default settings.
- Adaptive reveal rule: The adaptive reveal schedule improves average accuracy from 58.17 to 59.73 while reducing average forward passes from 200.9 to 148.9.The schedule distributes remaining masks across the remaining step budget and guarantees progress at each step.
- Adaptive reveal rule: The adaptive rule prevents reveal stalls under a growing canvas, reducing Dream’s average forward passes per sample from 200.9 to 148.9.The same adaptive rule is used for the LLaDA backend.
- JS threshold: At τJS = 0.02, average accuracy reaches its plateau while CARVE remains selective about accepting expansions.A threshold of 0.01 rejects too many expansions, whereas 0.05 and 0.10 accept nearly all proposals.
- Insertion mode: Mid-insert performs best on Dream and LLaDA-1.5, while tail insertion is strongest on LLaDA-8B.CARVE therefore uses mid-insert by default while treating tail insertion as a strong simpler alternative.
6 Discussion
CARVE uses verified stability checks to expand masked canvases, improving accuracy while often reducing compute. Its JS-based acceptance rule and EOS cropping help balance adaptive length with denoising stability.
- CARVE accepts canvas growth only when inserted masks cause a small mean distribution shift at aligned unresolved positions.The JS criterion tests whether predictions remain stable after expansion.
- Across models, CARVE improves average accuracy over fixed-length baselines while often using less compute.
- A threshold that is too small rejects useful expansions, whereas a threshold that is too large makes CARVE nearly equivalent to always expanding.
- EOS cropping and adaptive reveal offset branching costs by stopping refinement after EOS and synchronizing reveals with canvas growth.These inference-time mechanisms improve the accuracy–compute trade-off without retraining or modifying the diffusion model.
7 Conclusion
CARVE is a training-free variable-length decoder that verifies canvas expansions by checking prediction stability on unresolved positions. Across code-generation and mathematical-reasoning benchmarks, it improves average performance over fixed-length baselines while preserving an inference-time path to length adaptation.
- CARVE is a training-free variable-length decoding algorithm that accepts expanded canvases only when aligned unresolved predictions remain stable.This reframes length control as a counterfactual stability test rather than a confidence or EOS heuristic.
- Across code-generation and mathematical reasoning benchmarks, CARVE improves average performance over fixed-length baselines for each evaluated diffusion LM.Adaptive reveal and EOS cropping often offset the extra forward passes from branching.
- Pretrained masked diffusion LMs contain signals that support safe length adaptation directly at inference time without retraining or architectural changes.
Limitations
The reported limitations concern how CARVE expands and verifies canvases. Its main configurations use fixed-size insertions, and its JS alignment excludes newly inserted positions.
- CARVE currently inserts a fixed number of mask tokens at each accepted expansion, using k = 16 in the main configurations.Future work could adapt insertion size to prompt uncertainty or length requirements.
- CARVE’s JS verification compares only unresolved positions that existed before insertion and excludes newly inserted mask positions.The paper notes that softer alignment or alternative divergence criteria could account for those new positions.
- Experiments initialize each model–benchmark canvas with L0 = Lmax/2 masked positions and use a denoising budget of T = Lmax.
- All experiments used AMD MI210 GPUs and consumed approximately 42 aggregate GPU-days.Runs used at most eight GPUs concurrently.
C Isolating the Contribution of Each Component
Controlled ablations separate CARVE’s adaptive reveal, EOS cropping, canvas expansion, and verification components. The results indicate that adaptive reveal supports growing canvases, EOS cropping saves compute, and verification is not uniformly replaceable by unconditional expansion.
- Discussion: Adaptive reveal leaves fixed-canvas performance unchanged but helps a growing canvas keep pace with its changing unresolved-position count.
- Discussion: EOS cropping approximately preserves accuracy on a full canvas while reducing computation spent on suffix positions discarded after EOS.
- Discussion: A fixed L0 = Lmax/2 canvas is cheaper but loses substantial accuracy, showing that a small initial canvas needs a mechanism for allocating additional space.
- Discussion: On LLaDA backends, removing verification reduces accuracy relative to CARVE while saving only a small amount of compute.
- Discussion: On Dream, CARVE and always-expand are close, suggesting unconditional growth can sometimes suffice but is not reliable across backends.
- Figure 4: In the Dream setting, the canvas inserts 16 masks every 8 denoising steps until reaching Lmax = 128.The adaptive rule keeps reveal progress synchronized with the growing canvas.
D Adaptive Reveal Under a Growing Canvas
CARVE’s adaptive reveal rule keeps a growing canvas aligned with the remaining denoising budget, preventing stalls and reducing forward passes while bounding expansion overhead.
- Adaptive reveal rule: The adaptive rule distributes remaining masked positions across remaining denoising steps and guarantees at least one reveal per step while masks remain.
- Adaptive reveal rule: The original fixed-canvas schedule can stall by expanding the canvas early without committing tokens, forcing late reveals.
- Efficiency: Dream’s average forward passes per sample fell from 200.9 to 148.9 with adaptive revealing.
- Expansion overhead: On the 5% longest responses, CARVE’s largest observed cost was 1.04× the fixed baseline, with most settings within two percent.
- Expansion overhead: Rejected expansion proposals still incur a verification forward pass, while expansion attempts are limited to at most ⌈T/I⌉ per trajectory.
F Wall-Clock Throughput and Peak Memory
CARVE generally improves throughput while leaving peak memory essentially unchanged, including when evaluated on long-response and qualitative benchmark examples.
- Measurement: Wall-clock throughput and peak device memory were measured as CARVE-to-fixed-baseline ratios on 8×AMD MI210 GPUs.
- Peak memory: Peak memory ratios range from 0.96 to 1.01 across evaluated settings.
- Throughput: CARVE is consistently faster on Dream and improves throughput in most LLaDA settings, although some long-response cases fall slightly below baseline.
- Peak memory: Peak memory remains essentially unchanged because CARVE never exceeds the fixed decoder’s maximum canvas length.
- Qualitative examples: Figures 5–8 provide qualitative Dream-7B examples from HumanEval and GSM8K, reporting forward passes and peak canvas length.