DAPD : Dependency-Aware Parallel Decoding via Attention for Diffusion LLMs

June 15, 2026 · View on GitHub

Introduction

Parallel decoding for Diffusion LLMs (dLLMs) is difficult because each denoising step provides only token-wise marginal distributions, while unmasking multiple tokens simultaneously requires accounting for inter-token dependencies. We propose Dependency-Aware Parallel Decoding (DAPD), a simple, training-free decoding method that uses self-attention to induce a conditional dependency graph over masked tokens. At each iteration, edges in this graph capture strong token interactions, while non-edges indicate weak dependence. Parallel decoding is then reduced to selecting an independent set on the graph and unmasking the selected tokens in parallel. This avoids co-updating strongly coupled tokens without auxiliary models or retraining. Experiments on LLaDA and Dream show that DAPD improves the accuracy–steps trade-off over existing methods and enables more globally distributed parallel updates that better exploit the any-order generation capability of dLLMs.

Performance

Each cell reports Acc (%) / Steps (NFE). DAPD rows are results with torch 2.5.1+cu121.

LLaDA

DAPD 1-block reduces the average decoding steps from 256 to 33.8 steps for Direct (🔥 7.6x fewer steps) and 48.1 steps for Staged (🔥 5.3x fewer steps).

MethodHumanEvalMBPPGSM8KMath500IFEval
DAPD-Direct 1-block34.2 / 23.536.0 / 22.571.4 / 34.027.6 / 46.557.3 / 42.6
DAPD-Direct 4-block42.7 / 59.538.8 / 36.775.8 / 61.426.2 / 84.658.6 / 94.6
DAPD-Staged 1-block36.6 / 45.240.4 / 37.671.1 / 48.928.4 / 58.962.0 / 50.1
DAPD-Staged 4-block37.8 / 92.838.8 / 96.874.6 / 111.027.8 / 123.358.0 / 99.7
Fast-dLLM 1-block10.4 / 40.79.6 / 34.27.5 / 89.41.8 / 76.441.7 / 31.7
EB-Sampler 1-block13.4 / 85.98.0 / 61.16.6 / 143.42.0 / 136.330.7 / 108.3
KLASS 1-block11.0 / 97.319.8 / 43.326.3 / 72.63.0 / 83.440.1 / 96.5
Fast-dLLM 4-block37.2 / 92.120.6 / 41.576.8 / 72.828.0 / 95.658.3 / 100.0
EB-Sampler 4-block37.2 / 110.419.4 / 52.676.1 / 86.928.2 / 113.257.0 / 136.3
KLASS 4-block37.8 / 149.426.0 / 53.975.6 / 93.926.4 / 118.658.4 / 139.0

Dream

MethodHumanEval InstructMBPPGSM8KMath500IFEval
DAPD-Direct50.6 / 116.049.4 / 26.858.8 / 60.030.6 / 63.637.2 / 17.4
DAPD-Staged42.7 / 110.649.4 / 48.752.6 / 66.826.6 / 60.635.4 / 83.0
Fast-dLLM43.3 / 112.230.6 / 67.747.7 / 90.217.5 / 158.718.2 / 53.2
EB-Sampler45.7 / 155.430.6 / 186.544.5 / 127.613.0 / 190.57.1 / 115.2
KLASS59.8 / 133.334.4 / 60.845.1 / 154.413.0 / 204.27.1 / 132.1

What Is Included

  • dapd/: core DAPD implementation and a minimal generation test.
  • baselines/: vendored KLASS, Fast-dLLM, and EB code required by wrappers.
  • evaluation/lm-evaluation-harness/exp/dapd/: DAPD lm-eval scripts.
  • evaluation/lm-evaluation-harness/exp/baselines/: KLASS, Fast-dLLM, and EB-Sampler lm-eval scripts.
  • evaluation/ParallelBench/exp/dapd/: DAPD ParallelBench runner.
  • evaluation/ParallelBench/exp/baselines/: baseline ParallelBench runner.

Repository Structure

.
|-- dapd/
|   |-- core.py                 # DAPD dependency scoring and token selection
|   |-- generation.py           # LLaDA generation with DAPD
|   |-- dream_core.py           # Dream-specific DAPD utilities
|   |-- dream_generation.py     # Dream generation with DAPD
|   |-- latency.py              # step / NFE accounting
|   `-- test.py                 # minimal generation smoke test
|-- baselines/
|   |-- EB/                     # EB-Sampler implementation
|   |-- Fast-dLLM/              # Fast-dLLM implementation
|   `-- KLASS/                  # KLASS implementation
|-- evaluation/
|   |-- lm-evaluation-harness/
|   |   |-- exp/dapd/           # DAPD lm-eval scripts
|   |   |-- exp/baselines/      # baseline lm-eval scripts
|   |   |-- exp/update_summary_with_metrics.py
|   |   `-- lm_eval/            # lm-eval tasks and model wrappers
|   `-- ParallelBench/
|       |-- exp/dapd/           # DAPD ParallelBench runner
|       |-- exp/baselines/      # baseline ParallelBench runner
|       |-- cfg/                # ParallelBench task configs
|       |-- dataset/            # ParallelBench datasets
|       |-- model/              # ParallelBench model wrappers
|       `-- utils/              # ParallelBench utilities
|-- env.yml                     # recommended conda environment
|-- LICENSE
`-- README.md

Generated directories such as logs/, results/, .cache/, and worktrees/ are not required for normal use or release.

DAPD Algorithm

The public implementation exposes two paper-facing modes:

  • dapd_staged: staged high-confidence unmasking.
  • dapd_direct: direct confidence-1.0 independent unmasking.

Quick Test

The smoke test loads a LLaDA model, runs one prompt through the DAPD generation path, and prints only the generated text plus steps in the stats block.

python dapd/test.py \
  --model GSAI-ML/LLaDA-8B-Instruct \
  --prompt "Explain what a Markov Random Field is." \
  --gen-length 256 \
  --alg dapd_direct \
  --tau-min 0.01 \
  --tau-max 0.05

lm-eval: DAPD

Use the task wrappers under evaluation/lm-evaluation-harness/exp/dapd/.

cd evaluation/lm-evaluation-harness

TAU_MIN=0.01 TAU_MAX=0.05 DAPD_ALG=dapd_direct \
  exp/dapd/llada/humaneval.sh

LLaDA 4-block example:

BLOCK_LENGTH=64 TAU_MIN=0.01 TAU_MAX=0.05 DAPD_ALG=dapd_direct \
  exp/dapd/llada/humaneval.sh

Dream example:

TAU_MIN=0.005 TAU_MAX=0.01 DAPD_ALG=dapd_direct \
  exp/dapd/dream/humaneval.sh

lm-eval: Baselines

cd evaluation/lm-evaluation-harness/exp/baselines

./run_eval.sh fast-dllm humaneval
./run_eval.sh klass mbpp
./run_eval.sh eb math500
./run_eval.sh dream-eb ifeval

Baseline names: fast-dllm, klass, eb, dream-fast-dllm, dream-klass, dream-eb.

ParallelBench

DAPD:

python evaluation/ParallelBench/exp/dapd/run_all_parallelbench_dapd.py \
  --tasks waiting_line_n15/copy,puzzle/latin_square_n4 \
  --alg dapd_staged \
  --tau-min 0.01 \
  --tau-max 0.15 \
  --no-wandb

Use --tasks paper for the paper subset, --tasks all for every local ParallelBench task, or --task-type <prefix> to filter by task family.

Baselines:

python evaluation/ParallelBench/exp/baselines/run_all_parallelbench_baselines.py \
  --baseline klass \
  --tasks puzzle/latin_square_n4 \
  --no-wandb

Citation

@article{kim2026dependency,
  title={Dependency-aware parallel decoding via attention for diffusion llms},
  author={Kim, Bumjun and Jeon, Dongjae and Jeon, Moongyu and No, Albert},
  journal={arXiv preprint arXiv:2603.12996},
  year={2026}
}

License

This project is released under the MIT License. See LICENSE for details. Third-party components under baselines/ and evaluation/lm-evaluation-harness/ retain their own licenses.