💬 NLP

Divide and Conquer: Accelerating Diffusion-Based Large Language Models via Adaptive Parallel Decoding

This paper introduces DiCo, an adaptive parallel decoding framework that bridges the gap between theoretical and practical parallelism in diffusion-based large language models by employing a three-phase divide-and-conquer strategy to achieve significant inference speedups without compromising generation quality.

Original authors: Xiangzhong Luo, Yilin An, Zhicheng Yu, Weichen Liu, Xu Yang

Published 2026-03-02

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Xiangzhong Luo, Yilin An, Zhicheng Yu, Weichen Liu, Xu Yang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a giant jigsaw puzzle, but you can't see the picture on the box. You have to figure out what piece goes where based only on the pieces you've already placed.

The Problem: The Slow vs. The Risky

There are two main ways AI models (like the ones that write code or solve math problems) try to solve this puzzle:

The "One-by-One" Worker (Autoregressive LLMs): This is the current standard. Imagine a very careful worker who places one puzzle piece at a time. They look at the whole picture so far, pick the perfect next piece, and place it. Then they repeat.
- Pros: The picture usually looks perfect.
- Cons: It's incredibly slow. If the puzzle has 1,000 pieces, they have to make 1,000 separate trips to the box.
The "Grab-Everything" Worker (Diffusion Models): This is a newer type of AI. Theoretically, this worker is super fast. Instead of placing one piece, they look at the whole empty puzzle and say, "I think I know where all 1,000 pieces go!" and try to drop them all in at once.
- Pros: It should be lightning fast.
- Cons: In reality, this worker gets confused. If they try to guess 100 pieces at once, they often put the wrong ones in, creating a messy, nonsensical picture. So, to be safe, they usually end up placing pieces one-by-one anyway, losing their speed advantage.

The Gap: We have a worker who can work in parallel (all at once), but they are too scared to do it because they might mess up.

The Solution: DiCo (Divide and Conquer)

The paper introduces a new strategy called DiCo (Divide and Conquer). Think of DiCo not as a single worker, but as a smart project manager who organizes the puzzle-solving process into three distinct phases to get the best of both worlds: speed and accuracy.

Phase 1: The "Divide" (Finding the Safe Zones)

Imagine the puzzle is a dark room. The project manager shines a flashlight. They notice that some areas of the puzzle are very obvious (e.g., the blue sky in the corner), while others are tricky (e.g., the face in the middle).

Instead of guessing the whole room at once, DiCo identifies clusters of easy pieces.

It finds a few "seed" pieces that are very confident (like a bright blue sky piece).
It then expands outward from those seeds, grouping nearby pieces that are also likely to be correct.
The Result: The big, scary puzzle is broken down into several small, manageable "neighborhoods" of pieces that are safe to guess together.

Phase 2: The "Conquer" (Parallel Filling)

Now that the puzzle is divided into safe neighborhoods, the project manager tells the workers: "Go fill in these neighborhoods all at the same time!"

Because the pieces in each neighborhood are closely related and the AI is confident about them, they can be placed in parallel without messing up.
The manager keeps checking: "Are we still confident in this neighborhood?" If yes, keep going. If the confidence drops (the pieces get tricky), stop and re-evaluate.
This phase repeats, filling in huge chunks of the puzzle much faster than the "one-by-one" worker, but without the chaos of the "grab-everything" worker.

Phase 3: The "Finalize" (The Fine-Tuning)

Eventually, most of the puzzle is done. But there are a few tricky pieces left in the middle—maybe a specific eye or a tiny detail where the AI is still unsure.

At this point, the "parallel" strategy is too risky.
DiCo switches to a fine-grained mode. It looks at these last few pieces one by one, using a very careful, detailed check (looking at the "margin" between the best guess and the second-best guess) to ensure they fit perfectly.
This ensures the final picture is high-quality and coherent.

Why This Matters

Speed: By grouping easy parts and solving them together, DiCo is 3 to 5 times faster than the current standard methods.
Quality: By stopping the "parallel" mode when things get tricky and switching to careful, single-piece solving, it doesn't sacrifice accuracy.
No Retraining: The best part? This is a "plug-and-play" strategy. You don't need to retrain the AI model (which is expensive and hard). You just change how it solves the puzzle.

In a nutshell: DiCo is like a smart construction crew. Instead of building a whole skyscraper in one giant, risky leap, or laying one brick at a time for a decade, they build entire floors simultaneously (because they know those floors are stable) and then carefully finish the tricky roof details one by one. The result? A building finished in record time that still stands perfectly straight.

1. Problem Statement

The Gap Between Theory and Practice in dLLMs:
Diffusion-based Large Language Models (dLLMs) theoretically offer the ability to generate multiple tokens in parallel at each decoding step, unlike autoregressive (AR) models which generate one token per step. However, in practice, current state-of-the-art dLLMs (e.g., LLaDA, Dream) still predominantly generate one token per step to maintain generation quality and stability.

The Core Challenge:
Directly applying naive parallel decoding (decoding multiple masked tokens simultaneously) leads to a significant degradation in generation quality. This occurs because naive parallel decoding assumes token independence, ignoring the strong contextual dependencies between adjacent tokens in natural language. The paper identifies a substantial gap between the theoretical potential for parallelism and the practical performance constraints of dLLMs.

2. Methodology: DiCo (Divide and Conquer)

To bridge this gap, the authors propose DiCo, a training-free, adaptive parallel decoding approach. DiCo utilizes a three-phase "Divide and Conquer" paradigm to iteratively partition the decoding process, allowing for safe parallelization where dependencies are weak and sequential refinement where they are strong.

Phase 1: Divide (Cluster Formation)

Objective: Identify subsets of masked tokens that can be safely decoded in parallel.
Mechanism:
- Seed Identification: DiCo scans the input sequence to identify "seed tokens" based on prediction confidence. To prevent seeds from being too close (which would violate independence assumptions), it employs a position-aware function (inspired by Soft-NMS) to enforce spatial separation.
- Trajectory Guidance: For order-sensitive tasks, a trajectory-guided scheme adaptively adjusts confidence scores to favor left-to-right generation patterns.
- Cluster Expansion: Identified seeds are bidirectionally expanded to form local clusters. Neighboring tokens are added to a cluster if their confidence exceeds a threshold ( $\tau_1$ ).
- Merging: Overlapping clusters are merged. This phase continues until the clusters stabilize or reach a maximum iteration count.

Phase 2: Conquer (Adaptive Parallel Decoding)

Objective: Decode tokens within the formed local clusters in parallel.
Theoretical Basis: The authors prove (Theorem 4.1) that when prediction confidence is high, the marginal probability distribution of tokens converges to the joint distribution, justifying parallel decoding.
Mechanism:
- Adaptive Unmasking: Instead of a fixed $k$ -token approach, DiCo adaptively determines how many tokens to unmask in each cluster based on their confidence scores. Specifically, a token is unmasked if its confidence satisfies a dynamic condition relative to the cluster size.
- Dynamic Boundaries: The boundaries of local clusters are re-evaluated at each step. Tokens that become highly confident are unmasked, while those that lose confidence are excluded.
- Convergence Check: The process alternates between Divide and Conquer. If the confidence density within clusters drops below a threshold (indicating global dependencies have emerged), the system re-enters the Divide phase to re-cluster.

Phase 3: Finalize (Fine-Grained Decoding)

Objective: Handle the remaining few masked tokens where dependencies are dense and global.
Mechanism:
- Compound Decoding: A fine-grained strategy is employed that combines Top-1 Confidence with Logit Margin (the difference between the highest and second-highest logits).
- Logic: If the logit margin is large, the model is decisive, and the token is unmasked. If the margin is small (indicating ambiguity), the system defaults to conservative Top-1 selection to ensure stability. This prevents premature or ambiguous token selection in the final stages.

3. Key Contributions

Theoretical Insight: The paper provides a theoretical analysis revealing that the failure of naive parallel decoding stems from the false assumption of token independence. It demonstrates that dLLMs naturally exhibit a transition from local sparsity (early/mid-stage) to global density (late-stage) in token dependencies.
DiCo Framework: Introduction of a novel, training-free adaptive parallel decoding framework that dynamically partitions the sequence into local clusters, enabling safe parallelism without retraining the model.
Empirical Validation: Comprehensive experiments across multiple dLLMs (LLaDA-8B, Dream-7B) and diverse tasks (Math reasoning, Code generation) demonstrating that DiCo significantly accelerates inference while maintaining or improving accuracy.

4. Experimental Results

The authors evaluated DiCo on LLaDA-8B-Instruct and Dream-7B-Instruct using datasets like GSM8K, Math-500, HumanEval, and MBPP.

Inference Speedup:
- DiCo achieved up to 4.8× speedup on LLaDA-8B (non-AR setting) and 5.7× on Dream-7B (semi-AR setting) compared to the vanilla baseline.
- It consistently outperformed the previous state-of-the-art parallel method, Fast-dLLM, in both speed and accuracy.
Accuracy:
- Unlike naive parallel methods that degrade accuracy, DiCo improved accuracy in many cases (e.g., +18.8% on GSM8K for LLaDA-8B non-AR) while accelerating inference.
- It successfully unlocked the potential of non-autoregressive decoding, which is often compromised in semi-autoregressive settings in prior works.
Ablation Studies:
- Seed Tokens: The method is robust to the number of seed tokens ( $N$ ).
- Trajectory Guidance: Crucial for maintaining high accuracy in order-sensitive tasks (like code generation).
- Compound Decoding: The logit margin mechanism in the Finalize phase significantly boosts robustness and final accuracy.

5. Significance

Bridging the Efficiency-Quality Gap: DiCo resolves the long-standing trade-off in dLLMs where parallelism was sacrificed for quality. It proves that dLLMs can be both fast and accurate without architectural changes or retraining.
Practical Deployment: As a training-free method, DiCo can be immediately applied to existing dLLMs, making it highly practical for real-world deployment.
New Paradigm for Decoding: The "Divide and Conquer" approach offers a new perspective on handling sequential dependencies in diffusion models, suggesting that adaptive clustering is a viable path for accelerating non-autoregressive generation in other domains.