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

이 논문은 확산 기반 대규모 언어 모델 (dLLM) 의 이론적 병렬성과 실제 성능 간의 격차를 해소하기 위해, 분할 (Divide) 과 정복 (Conquer) 단계를 반복하고 마지막에 정제 단계를 거치는 적응형 병렬 디코딩 기법인 'DiCo'를 제안하여 추론 속도를 크게 향상시키면서도 생성 품질을 유지하는 방법을 제시합니다.

핵심

🍳 배경: 왜 더 빨리 만들어야 할까요?

기존의 AI(자동 회귀 모델) 는 글을 쓸 때 한 글자씩 순서대로 써나갑니다. 마치 요리사가 "소금 한 꼬집, 그다음 후추 한 꼬집"이라고 하나씩 재료를 넣는 것과 같습니다. 정확하지만 시간이 많이 걸립니다.

반면, **확산 기반 모델 (dLLM)**은 이론상으로는 한 번에 여러 글자를 동시에 채울 수 있는 잠재력이 있습니다. 마치 빈 그릇에 모든 재료를 한 번에 쏟아붓고 섞는 것처럼 말이죠. 하지만 문제는, 이렇게 한 번에 너무 많이 채우면 맛이 엉망이 되거나 (품질 저하), 요리가 실패하는 (불안정) 경우가 많다는 것입니다. 그래서 실제로는 여전히 하나씩 천천히 채우는 방식을 쓰게 됩니다.

🚀 해결책: 'DiCo(디코)'라는 새로운 요리법

이 논문은 **"이론상의 병렬성 (한 번에 여러 개) 과 실제 성능 사이의 간극"**을 메우기 위해 DiCo라는 방법을 제안합니다. 이 방법은 '분할 정복 (Divide and Conquer)' 전략을 사용합니다.

이를 거대한 건물을 짓는 공사 현장에 비유해 볼까요?

1 단계: 나누기 (Divide) - "현장 구획 나누기"

공사 시작 전, 전체 건물을 무작위로 벽돌을 쌓는 게 아니라, 어떤 부분은 서로 영향을 덜 주고, 어떤 부분은 서로 밀접하게 연관되어 있는지를 먼저 파악합니다.

• 비유: 공사 현장의 지도를 보고, "이쪽은 기초 공사가 먼저 필요하고, 저쪽은 지붕 공사가 먼저 필요해"라고 작은 구역 (클러스터) 으로 나눕니다.
• 핵심: AI 가 "어디를 먼저 채워도 안전할지"를 찾아내어, 서로 간섭하지 않는 **작은 그룹 (씨앗)**을 만듭니다.

2 단계: 정복하기 (Conquer) - "동시 시공"

이제 나눈 작은 구역들마다 동시에 작업을 진행합니다.

• 비유: A 구역 팀, B 구역 팀, C 구역 팀이 동시에 각자 맡은 구역을 빠르게 쌓아 올립니다. 서로가 서로의 작업을 방해하지 않기 때문에 속도가 매우 빨라집니다.
• 핵심: AI 는 이 작은 그룹들 안에서 여러 글자를 한 번에 채워 넣습니다. 하지만 그룹이 너무 복잡해지거나 서로 의존도가 높아지면 멈춥니다.

3 단계: 마무리하기 (Finalize) - "마무리 다듬기"

대부분의 벽돌이 쌓였을 때, 남은 몇 개의 빈 공간은 서로 매우 밀접하게 연관되어 있습니다. 이때는 다시 한 번씩 꼼꼼하게 채워 넣습니다.

• 비유: 건물의 대략적인 형태는 다 잡혔는데, 창문 테두리나 문짝 같은 마지막 디테일은 전문가가 하나씩 정성스럽게 다듬습니다.
• 핵심: 남은 몇 개의 글자는 정밀하게 하나씩 채워 넣어서 완성도를 높입니다.

---

✨ DiCo 가 가져온 놀라운 결과

이 방법을 쓰면 어떤 일이 일어날까요?

1. 속도 폭발: 기존에 하나씩 하던 작업을 여러 개씩 동시에 처리하므로, 3 배에서 5 배 이상 더 빠르게 글을 생성합니다. (예: 256 단계를 67 단계로 줄임)
2. 품질 유지: 무작위로 여러 개를 채우는 게 아니라, 서로 간섭하지 않는 그룹을 찾아서 채우기 때문에 글의 정확도와 논리성은 그대로 유지됩니다. 오히려 기존 방법보다 더 좋은 점수를 받기도 합니다.
3. 학습 불필요: 이 방법은 AI 모델을 다시 학습시킬 필요 없이, 이미 만들어진 모델을 그대로 더 똑똑하게 사용하는 '학습 없는 (Training-free)' 기술입니다.

📝 한 줄 요약

"DiCo 는 AI 가 글을 쓸 때, '한 번에 다 쓰려다 실패하는 것'과 '하나씩 천천히 쓰는 것' 사이에서, '작은 그룹으로 나누어 동시에 쓰되, 마지막은 꼼꼼하게 다듬는' 현명한 전략을 찾아낸 것입니다."

이 기술 덕분에 앞으로 AI 와 대화하거나 글을 쓸 때, 기다리는 시간이 획기적으로 줄어들고 더 빠르고 정확한 답변을 받을 수 있게 될 것입니다.

기술 요약

1. 문제 정의 (Problem)

• 배경: 확산 기반 대규모 언어 모델 (dLLMs) 은 autoregressive (AR) 모델과 달리 이산적인 디코딩 단계를 통해 텍스트를 생성하며, 이론적으로는 각 단계에서 여러 토큰을 병렬적으로 생성할 수 있는 잠재력을 가지고 있습니다.
• 현실적 한계: 실제 적용에서는 생성 품질과 안정성을 유지하기 위해 대부분의 dLLMs 이 여전히 한 번에 하나의 토큰만 생성하는 방식 (one-token-per-step) 을 선호합니다.
• 핵심 문제:
  • 단순히 여러 마스킹된 토큰을 한 번에 병렬 디코딩하면 (Naive Parallel Decoding), 토큰 간의 강한 문맥적 의존성을 무시하게 되어 생성 품질이 급격히 저하됩니다.
  • 이는 dLLMs 의 이론적 병렬성과 실제 성능 사이에 큰 간극 (Gap) 이 존재함을 의미합니다.
  • 기존 훈련 기반 (Training-based) 병렬 디코딩 방법은 학습 비용이 많이 들고, 기존 훈련 없는 (Training-free) 방법들은 블록 단위 (Block-wise) 의 한계로 인해 효율성이 낮거나 속도가 충분히 향상되지 않았습니다.

2. 제안 방법: DiCo (Methodology)

저자들은 이 간극을 해소하기 위해 **훈련이 필요 없는 (Training-free) 적응형 병렬 디코딩 방법인 'DiCo'**를 제안했습니다. DiCo 는 분할 정복 (Divide and Conquer) 패러다임을 기반으로 하며, 생성 과정을 세 가지 단계로 반복적으로 수행합니다.

1 단계: Divide (분할)

• 목적: 입력된 마스킹 시퀀스를 탐색하여 독립적으로 병렬 디코딩이 가능한 '국소 클러스터 (Local Clusters)'를 형성합니다.
• 핵심 기법:
  • 시드 토큰 식별: 예측 신뢰도 (Confidence) 를 기반으로 시드 토큰을 선택합니다.
  • 위치 인식 함수 (Position-aware Function): Transformer 의 국소적 편향을 보완하기 위해, 인접한 위치에 시드 토큰이 선택되는 것을 방지하는 가우시안 기반의 거리 함수를 도입하여 시드 토큰 간의 공간적 분리를 보장합니다.
  • 궤적 가이드 (Trajectory Guidance): 왼쪽에서 오른쪽으로 생성되는 추론 작업의 특성을 반영하여, 마스킹 토큰의 예측 신뢰도를 적응적으로 조정합니다.
  • 클러스터 확장: 식별된 시드 토큰을 중심으로 인접한 마스킹 토큰들을 양방향으로 확장하여 로컬 클러스터를 구성하고, 겹치는 클러스터는 병합합니다.

2 단계: Conquer (정복)

• 목적: Divide 단계에서 형성된 서로 다른 로컬 클러스터 간에 적응형 병렬 디코딩을 수행합니다.
• 핵심 기법:
  • 이론적 근거: 토큰 예측의 신뢰도가 충분히 높을 때, 주변 토큰과의 조건부 독립성이 성립하여 병렬 디코딩이 가능함을 수학적으로 증명했습니다 (Theorem 4.1).
  • 적응형 언마스크 (Adaptive Unmasking): 고정된 임계값 대신, 각 클러스터 내 토큰의 예측 신뢰도에 따라 병렬로 언마스크할 토큰 수를 동적으로 결정합니다.
  • 반복적 최적화: 클러스터의 신뢰도 밀도가 병렬 디코딩 임계값 이하로 떨어지거나, 전체 언마스크 비율이 임계값에 도달할 때까지 Divide 와 Conquer 단계를 반복합니다.

3 단계: Finalize (마무리)

• 목적: 생성이 거의 완료된 후 남은 소수의 마스킹 토큰을 처리하여 최종 생성 품질을 보장합니다.
• 핵심 기법:
  • 세밀한 복합 디코딩 (Fine-grained Compound Decoding): 남은 토큰들은 전역 문맥에 대한 의존도가 높으므로, 단순히 신뢰도만 보는 것이 아니라 **로짓 마진 (Logit Margin, 1 위와 2 위 확률의 차이)**과 Top-1 신뢰도를 함께 고려합니다.
  • 이 방식은 모호한 선택을 방지하면서도 안정적인 생성 속도를 유지합니다.

3. 주요 기여 (Key Contributions)

1. 문제 인식 및 분석: dLLMs 의 이론적 병렬성과 실제 성능 간의 간극을 이론적 분석 (토큰 간 독립성 가정의 오류) 과 실험적 관찰 (신뢰도 분포 및 어텐션 패턴) 을 통해 명확히 규명했습니다.
2. DiCo 알고리즘 개발: 훈련 비용 없이 적용 가능한 분할 정복 기반의 적응형 병렬 디코딩 프레임워크를 제안했습니다. 이는 로컬 클러스터 단위의 병렬 처리와 전역 문맥 기반의 마무리 단계를 결합합니다.
3. 광범위한 실험 검증: 다양한 dLLM (LLaDA, Dream) 과 데이터셋 (수학 추론, 코드 생성) 에서 DiCo 의 유효성을 입증했습니다.

4. 실험 결과 (Results)

논문은 LLaDA-8B-Instruct 와 Dream-7B-Instruct 모델을 사용하여 GSM8K, Math-500, MBPP, HumanEval 데이터셋에서 실험을 수행했습니다.

• 추론 속도 향상:
  • Vanilla (기존 1 토큰/단계) 대비 최대 4.8 배의 추론 속도 향상 (Throughput) 을 달성했습니다.
  • Fast-dLLM (기존 병렬 디코딩) 대비에서도 평균적으로 3.4 배 ~ 5.2 배의 속도 향상을 보였습니다.
• 생성 품질 유지 및 향상:
  • 속도를 높임에도 불구하고, 정확도 (Accuracy) 는 Vanilla 및 Fast-dLLM 대비 동등하거나 오히려 향상되었습니다.
  • 예: LLaDA-8B 모델에서 GSM8K 기준 Vanilla 대비 정확도 +18.8% 증가, 추론 속도 3.4 배 향상.
• 비교 분석:
  • 적응형 vs 고정형: 고정된 신뢰도 임계값을 사용하는 기존 방법보다 적응형 디코딩이 모든 데이터셋에서 더 높은 처리량을 보여주었습니다.
  • 궤적 가이드의 효과: 궤적 가이드 (Trajectory Guidance) 를 적용했을 때 정확도가 크게 향상됨을 확인했습니다.
  • 디코딩 단계 수 감소: Fast-dLLM 이 87 단계가 걸린 작업을 DiCo 는 67 단계로 단축하여 효율성을 입증했습니다.

5. 의의 및 결론 (Significance)

• 실용적 가치: dLLMs 의 가장 큰 약점인 '느린 추론 속도'를 해결하면서도, AR 모델에 필적하거나 그 이상의 생성 품질을 유지할 수 있는 방법을 제시했습니다.
• 이론적 통찰: "토큰 간의 의존도가 국소적으로 희소할 때는 병렬 처리가 가능하지만, 전역적으로 밀집될 때는 세밀한 처리가 필요하다"는 dLLMs 의 동작 원리를 규명하고 이를 알고리즘에 반영했습니다.
• 미래 방향: 추가적인 학습 (Fine-tuning) 없이 기존 dLLM 모델에 바로 적용 가능한 '훈련 없는 (Training-free)' 솔루션을 제공함으로써, dLLMs 의 상용화 및 실제 배포 가능성을 크게 높였습니다.

요약하자면, DiCo는 dLLMs 의 병렬 생성 잠재력을 최대한 끌어내면서도 품질 저하를 방지하기 위해, **신뢰도에 기반한 동적 클러스터링 (분할)**과 적응형 병렬 처리 (정복), 그리고 **세밀한 마무리 (Finalize)**를 결합한 혁신적인 디코딩 전략입니다.