최근 diffusion model의 성공은 이미지 생성 분야를 넘어 언어 모델링으로도 확장되고 있습니다. Diffusion Language Model(DLM)은 autoregressive language model처럼 왼쪽에서 오른쪽으로 토큰을 하나씩 생성하는 방식이 아니라, 마스크된 시퀀스를 여러 단계에 걸쳐 점진적으로 복원하는 방식으로 텍스트를 생성합니다.
이러한 방식의 가장 큰 장점 중 하나는 parallel decoding입니다. Autoregressive model은 다음 토큰을 생성하기 위해 반드시 이전 토큰이 확정되어 있어야 하지만, DLM은 여러 위치의 마스크 토큰을 한 번에 예측하고 동시에 채울 수 있습니다. 따라서 잘 활용하면 낮은 latency와 빠른 generation이 가능합니다.
하지만 structured output을 생성해야 하는 상황에서는 문제가 생깁니다. 예를 들어 모델이 C++ 코드, JSON, SMILES 문자열과 같이 문법적으로 엄격한 출력을 만들어야 한다고 해봅시다. 일반적인 unconstrained DLM decoding은 여러 위치를 독립적으로 채우기 때문에, 각 토큰은 그럴듯해 보여도 전체 시퀀스는 문법적으로 잘못될 수 있습니다.
예를 들어 JSON에서 {, }, :, ,의 위치가 맞지 않거나, C++ 코드에서 괄호와 세미콜론 구조가 깨지거나, SMILES 문자열이 화학적으로 유효하지 않은 형식이 될 수 있습니다. 따라서 DLM에서도 structured output을 안정적으로 생성하기 위해 CFG-constrained decoding이 필요합니다.
기존 연구는 DLM에 context-free grammar(CFG) 제약을 적용하는 방법을 제안했습니다. 핵심 아이디어는 현재 partial output이 남은 mask들을 적절히 채웠을 때 target grammar에 속하는 valid output으로 완성될 수 있는지를 검사하는 것입니다.
즉, 현재 출력이 다음과 같다고 해봅시다.
{ "name": [MASK], "age": [MASK] }
이 partial output이 JSON grammar에 맞는 문자열로 완성될 수 있다면 update를 허용하고, 그렇지 않다면 거절합니다.
하지만 기존 방식은 효율성 측면에서 큰 문제가 있습니다. DLM은 한 step에서 여러 토큰을 동시에 제안할 수 있는데, 기존 CFG-constrained decoder는 이 후보들을 사실상 순차적으로 검사해야 했습니다. 이는 DLM의 가장 중요한 장점인 parallel decoding을 크게 약화시킵니다.
또한 기존 방식은 매 validation마다 다음과 같은 무거운 과정을 반복합니다.
이 과정은 특히 C++처럼 grammar가 복잡한 경우 매우 비싸집니다. 논문에서는 기존 CFG-constrained decoding이 unconstrained decoding보다 최대 4배 가까이 느려질 수 있음을 보여줍니다.