Step-by-Step Teaching

Step 1: What is Discrete Diffusion?

Think of discrete diffusion like filling in a crossword puzzle.

• You start with a blank or masked grid
• At each step, you fill in multiple positions simultaneously
• Each position gets its own probability distribution over possible values (letters/tokens)

Key mechanics:

[MASK] [MASK] [MASK] [MASK]
   ↓       ↓       ↓       ↓
  "The"  "cat"  "sat"  "mat"

Each position independently draws from its own distribution

---

Step 2: The Core Problem — Token Dependencies

What are token dependencies?

In real language (and images/audio), tokens are not independent of each other.

Example:

"The ___ sat on the ___"

If position 2 = "cat" → position 6 is likely "mat" or "floor" If position 2 = "pilot" → position 6 is likely "plane" or "seat"

The tokens influence each other — this is dependency.

Why does this matter for diffusion?

Discrete diffusion writes multiple positions simultaneously per step, drawing each from a per-position distribution.

⚠️ Critical Problem: Per-position distributions only capture individual token probabilities, NOT joint probabilities between tokens

---

Step 3: The Mathematical Limitation

Per-position marginals vs. joint distributions

The Key Theorem (simplified)

The paper proves:

Two completely different joint distributions can have IDENTICAL per-position marginals

Illustration:

Joint Distribution A:        Joint Distribution B:
("cat", "mat") = 0.5        ("cat", "floor") = 0.5
("dog", "floor") = 0.5      ("dog", "mat") = 0.5

Per-position marginals (IDENTICAL for both):
Position 1: cat=0.5, dog=0.5
Position 2: mat=0.5, floor=0.5

🔑 Insight: Looking only at individual positions, you cannot tell which combinations actually occur together

---

Step 4: When Does a Step Match Training Distribution?

The paper establishes a precise condition:

✅ Correct generation ONLY when:

Positions being written are CONDITIONALLY INDEPENDENT
given the tokens already fixed

What this means:

• If you've already fixed some tokens
• The remaining positions you write must not influence each other
• Only then does the product of per-position distributions equal the true joint

❌ What always happens in practice:

The paper shows that every group of 2+ undetermined positions that a confidence ranking selects is dependent — the condition is never met.

---

Step 5: Empirical Evidence — ScanAndAdd Task

Why ScanAndAdd?

It's a synthetic task where:

• The true joint distribution is known exactly (closed form)
• You can directly measure how wrong the generated distribution is

Results

The Dangerous Illusion

Per-sample metrics say: ✅ "Everything looks fine!"
True distribution says: ❌ "29× worse than random noise!"

⚠️ Critical Warning: Standard evaluation metrics can completely hide fundamental distributional failures

---

Step 6: Synthesizing the Full Picture

The Chain of Reasoning

Discrete Diffusion writes multiple tokens per step
           ↓
Uses per-position distributions (marginals)
           ↓
Real tokens have dependencies (joint structure)
           ↓
Per-position marginals CANNOT capture joint dependencies
           ↓
Generated combinations are systematically wrong
           ↓
But per-sample metrics won't show this!

---

Summary Table

---

Self-Check Questions

1. Why can't a product of per-position distributions represent a dependent group?
2. Give your own example of two tokens that are dependent
3. Why is the ScanAndAdd result particularly alarming for practitioners?
4. What would need to be true for a diffusion step to correctly match the training distribution?