그래프 기반 랜덤 워크를 활용한 마스크 диффузион 모델의 병렬 샘플링 방식 연구

Understanding Parallel Samplers in Masked Diffusion via Random Walks on Graphs

본 논문에서는 마스크 диффузион 모델(MDM)에서 다양한 병렬 샘플링 전략을 연구하기 위한 검증 가능한 환경으로 그래프 기반 랜덤 워크를 제안합니다. 우리는 고정된 그래프로부터 생성된 랜덤 워크 샘플을 사용하여 MDM을 학습시킵니다. 그래프 또는 전이 커널은 명시적으로 모델에 제공되지 않으며, 시퀀스의 잠재적인 구조 역할을 하지만, 이는 제어 가능하며 정량적 평가에 사용될 수 있습니다. 따라서 이 프레임워크는 수두쿠와 유사한 검증 기능을 갖습니다. 즉, 출력물이 유효한 랜덤 워크인지 확인하고, 랜덤 워크로부터 마르코프 커널을 추정하여 분포의 충실도를 측정합니다. 간단한 그래프를 사용하여, 널리 사용되는 엔트로피 최소화 등의 방법을 이용한 병렬 언마스크가 무작위 병렬 샘플러보다 항상 더 나은 성능을 보이는 것은 아니라는 것을 이론적으로 증명했습니다. 성능은 근본적인 그래프의 구조에 크게 의존합니다. 우리는 랜덤 워크를 위한 새로운 이분법 샘플러를 개발했으며, 이는 시퀀스 길이에 대해 로그 스케일로 작동하며, 완벽한 학습 조건 하에서 정확도가 보장됩니다. 다양한 그래프 워크 작업에 대한 실험 결과는 병렬 샘플러가 그래프의 특성에 따라 실제 성능이 다르다는 것을 보여줍니다. 사전 훈련된 OpenWebText MDM에 대한 초기 실험에서는 이분법 스타일 샘플러가 언어 생성에서도 속도와 품질 간의 균형을 개선한다는 것을 확인했습니다. 이러한 결과를 종합적으로 고려할 때, 그래프 랜덤 워크는 마스크 диффузион 모델의 병렬 샘플러를 진단하고 설계하기 위한 메커니즘적인 벤치마크로서 활용될 수 있습니다.

In this paper, we propose using random walks on graphs as a verifiable sandbox to study different parallel sampling strategies in masked diffusion models (MDMs). We train an MDM on random walk samples from a fixed graph. The graph or the transition kernel is never shown to the model explicitly and plays the role of latent structure in the sequences, albeit one that is controllable and can be used for quantitative evaluation. Thus, this framework enjoys a Sudoku-like validity check: verifying that an output is a valid walk and estimating the Markov kernel from the walks to measure distribution fidelity. Using simple graphs, we theoretically prove that parallel unmasking via widely used scores like lowest entropy is not uniformly better than a random parallel sampler; the performance critically depends on the structure of the underlying graph. We develop a new bisection sampler for random walks, which takes logarithmic steps in the sequence length and is provably exact under perfect training. Experiments on various graph walk tasks show that different parallel samplers are better for different graphs even in practice. Our initial experiments on a pretrained OpenWebText MDM show that the bisection-style samplers improve speed-quality tradeoffs even for language generation. Together, these results position graph random walks as a mechanistic benchmark for diagnosing and designing parallel samplers for masked diffusion models.