1. 연구 배경 및 문제 정의 (Problem)

배경:
최근 마스킹 확산 언어 모델 (Masked Diffusion Language Models, MDLMs) 은 텍스트 생성의 새로운 패러다임으로 부상했습니다. MDLM 은 텍스트 시퀀스의 토큰을 점진적으로 마스킹 (마스킹) 하는 전방 노이즈 과정과, 마스킹된 토큰을 예측하여 원래 시퀀스를 복원하는 역방향 디노이징 과정을 학습합니다. 이 방식은 생성 순서의 유연성과 병렬 디코딩 (Parallel Decoding) 을 가능하게 하여, 기존 자기회귀 (Autoregressive, AR) 모델의 좌측에서 우측으로의 엄격한 생성 순서 제약을 극복합니다.

문제점:
기존의 사전 학습된 MDLM 에 적용되는 디코딩 전략들은 주로 **토큰 수준의 불확실성 (Token-level Uncertainty)**에 의존합니다. 예를 들어, 모델이 예측한 확률 분포의 엔트로피, 신뢰도 (Confidence), 또는 마진 (Margin) 등을 기준으로 마스킹된 토큰의 업데이트 순서를 결정합니다.
이러한 접근법의 한계는 다음과 같습니다:

1. 시퀀스 수준의 정보 및 토큰 간 의존성 무시: 토큰별 불확실성만 고려할 뿐, 시퀀스 전체의 구조나 토큰 간의 복잡한 상호 의존성 (Inter-token Dependencies) 을 명시적으로 고려하지 않습니다. 이로 인해 주변 토큰 분포와 실제 시퀀스 결합 분포 (Joint Distribution) 간의 불일치가 발생합니다.
2. 블록 구조에 대한 민감성: 일부 방법들은 휴리스틱한 블록 (Block) 구조를 도입하여 병렬 처리를 시도하지만, 이는 훈련과 추론 간의 불일치를 초래하거나, 블록 크기에 따라 성능이 급격히 저하되는 문제가 있습니다.

2. 제안 방법: DOS (Dependency-Oriented Sampler)

저자들은 이러한 한계를 해결하기 위해 **의존성 지향 샘플러 (Dependency-Oriented Sampler, DOS)**를 제안합니다. 이는 추가적인 학습 없이 (Training-free) 적용 가능한 디코딩 전략입니다.

핵심 아이디어:
생성 과정에서 마스킹된 토큰을 업데이트할 때, 단순히 불확실성이 높은 토큰을 선택하는 대신, 현재 관찰된 언마스킹된 컨텍스트 (Unmasked Context) 에 대한 의존도가 높은 토큰을 우선적으로 선택합니다.

구현 메커니즘:

1. 어텐션 행렬 활용: Transformer 블록의 스케일된 도트 프로덕트 어텐션 (Scaled Dot-Product Attention) 가중치, 즉 $softmax(QK^T/\sqrt{d})$를 토큰 간 의존성의 프록시 (Proxy) 로 사용합니다.
2. 의존성 점수 (Dependency Score) 계산:
   • 주어진 마스킹된 위치 $m$에 대해, 현재 언마스킹된 모든 위치 $U$에 대한 어텐션 가중치의 합을 계산합니다.
   • 수식: $dep(m) = \sum_{u \in U} Attn(m, u)$
   • 이 점수가 높다는 것은 해당 마스킹된 토큰의 예측이 현재 관찰된 컨텍스트에 크게 의존하고 있음을 의미하며, 따라서 디코딩 순서에서 우선적으로 처리되어야 함을 나타냅니다.
3. 디코딩 순서 결정: 계산된 의존성 점수를 기준으로 마스킹된 토큰을 정렬하고, 점수가 높은 토큰부터 병렬적으로 디코딩합니다.

장점:

• 학습 불필요: 기존 Transformer 모델의 포워드 패스 (Forward Pass) 에서 얻은 어텐션 행렬을 그대로 사용하므로 추가 학습 비용이 없습니다.
• 분포 일치: 토큰 간 의존성을 명시적으로 모델링함으로써, 목표 결합 분포를 더 정확하게 복원할 수 있습니다.
• 호환성: 기존 병렬 샘플링 방법 (예: EB-Sampler) 과 쉽게 통합되어 효율성을 높일 수 있습니다.

3. 주요 기여 (Key Contributions)

1. 문제 인식 및 분석: 기존 MDLM 디코딩 전략이 토큰 수준의 불확실성에만 의존하여 시퀀스 수준의 의존성을 놓치고 있음을 이론적으로 분석하고, 이로 인한 분포 불일치 문제를 지적했습니다.
2. 새로운 디코딩 전략 제안 (DOS): 어텐션 메커니즘을 활용하여 토큰 간 의존성을 정량화하고, 이를 기반으로 디코딩 순서를 결정하는 새로운 훈련 불필요 (Training-free) 전략을 제안했습니다.
3. 광범위한 실험 검증: 코드 생성 (HumanEval, MBPP) 및 수학적 추론 (GSM8K, MATH500) 태스크에서 기존 방법들 (Confidence, Entropy, Margin, Fast-dLLM, KLASS 등) 보다 우수한 성능을 입증했습니다.
4. 효율성과 견고성: 단일 블록 (Single-block) 설정뿐만 아니라 블록 기반 설정에서도 일관된 성능을 유지하며, 블록 크기 변화에 민감하지 않은 견고한 (Robust) 특성을 보였습니다.

4. 실험 결과 (Results)

저자는 LLaDA-Instruct-8B 와 Dream-v0-Instruct-7B 모델을 사용하여 다양한 벤치마크에서 DOS 를 평가했습니다.

• 단일 블록 (Single-block) 설정:
  • DOS 는 모든 벤치마크에서 기존 불확실성 기반 방법들 (Confidence, Entropy 등) 보다 압도적으로 높은 정확도를 달성했습니다.
  • 특히 긴 시퀀스가 필요한 수학적 추론 (GSM8K, MATH500) 과 코드 생성 (HumanEval) 에서 큰 성능 향상을 보였습니다. (예: LLaDA-8B 기준 GSM8K 에서 31.69% → 84.31% 향상)
• 병렬 디코딩 및 효율성:
  • DOS 를 EB-Sampler 와 결합 (DOS+EB) 했을 때, 기존 방법들보다 높은 정확도를 유지하면서도 모델 순전파 횟수 (NFE) 를 줄여 디코딩 효율성을 크게 개선했습니다.
  • Fast-dLLM 이나 KLASS 와 같은 기존 가속화 방법들보다 높은 정확도를 달성했습니다.
• 블록 크기 민감도:
  • 기존 방법들은 블록 크기가 커질수록 성능이 급격히 저하되는 경향이 있었으나, DOS 는 블록 크기 (32~256) 에 관계없이 일관된 높은 성능을 유지했습니다. 이는 DOS 가 블록 구조에 의존하지 않고 토큰 간 의존성 자체를 모델링하기 때문입니다.
• 레이어 선택:
  • 어텐션 행렬을 추출하는 Transformer 레이어가 깊거나 얕은지 (특히 초기 10 레이어 내) 에 관계없이 DOS 는 안정적인 성능을 보였습니다.

5. 의의 및 결론 (Significance)

이 논문은 확산 언어 모델의 병렬 생성 역학을 이해하는 데 중요한 통찰을 제공합니다.

• 패러다임 전환: MDLM 의 디코딩 전략이 단순히 '어떤 토큰이 불확실한가'에서 '어떤 토큰이 현재 컨텍스트에 의존하는가'로 초점을 이동해야 함을 강조합니다.
• 실용적 가치: 추가 학습 없이 기존 모델에 즉시 적용 가능하면서도, 특히 복잡한 논리적 추론이 필요한 작업 (코드, 수학) 에서 성능을 획기적으로 개선합니다.
• 미래 연구 방향: 토큰 간 의존성을 명시적으로 모델링하는 것이 병렬 생성의 핵심임을 보여주었으며, 향후 더 정교한 의존성 구조 (예: DAG 등) 를 통합하거나 다양한 생성 태스크로 확장할 수 있는 기반을 마련했습니다.

요약하자면, DOS는 마스킹 확산 언어 모델의 병렬 디코딩 과정에서 발생하는 의존성 손실 문제를 어텐션 메커니즘을 통해 해결함으로써, 생성 품질과 효율성을 동시에 달성한 혁신적인 방법론입니다.