[논문리뷰] The Flexibility Trap: Rethinking the Value of Arbitrary Order in Diffusion Language Models

ICML 2026 (Outstanding Paper). [Paper] [Page] [Github]
Zanlin Ni, Shenzhi Wang, Yang Yue, Tianyu Yu, Weilin Zhao, Yeguo Hua, Tianyi Chen, Jun Song, Cheng Yu, Bo Zheng, Gao Huang
Tsinghua University | Alibaba Group
21 Jan 2026

Introduction

최근 시퀀스 생성을 discrete denoising process로 처리함으로써 지배적인 autoregressive (AR) 패러다임에 도전하는 diffusion LLM (dLLM)이 급증하고 있다. dLLM의 핵심적인 매력은 이론적 유연성에 있으며, 이는 왼쪽에서 오른쪽으로의 인과관계를 요구하는 AR 모델에 비해 두 가지 뚜렷한 이점을 제공한다. 바로 효율적인 병렬 디코딩과 임의 순서 생성 능력이다. 여러 성공 사례와 이론적 가능성에 힘입어, 수학 및 코딩과 같은 일반적인 추론 문제에서 유사한 고급 능력을 구현하기 위해 강화 학습(RL)을 점점 더 많이 도입하고 있다.

본 논문에서는 직관에 반하는 관찰 결과를 제시한다. 이러한 일반적인 추론 문제에서 임의 순서 생성은 RL을 통해 도출할 수 있는 추론 잠재력을 확장하기보다는 오히려 축소할 수 있다는 것이다. 저자들은 이를 엄밀하게 평가하기 위해 solution space의 커버리지를 측정하는 Pass@k 지표를 사용하였다. 이 지표를 사용하여 임의 순서 생성과 LLaDA-Instruct를 사용한 표준 AR 디코딩의 추론 잠재력을 비교한 결과, dLLM을 표준 AR 순서로 제한하면 유연한 dLLM에 비해 Pass@k 값이 높아지고, 결과적으로 추론 한계가 더 커지는 경향이 있다.

이러한 직관에 반하는 관찰은 서로 다른 순서가 불확실성을 처리하는 방식과 밀접하게 관련되어 있다. 추론은 본질적으로 균일하지 않다. 추론은 문장을 단순히 이어가는 것이 아니라 논리적 궤적을 서로 다른 분기로 이끄는 “Therefore”, “Since”와 같은 연결어와 같은 논리적 분기 토큰(forking token)에 의존한다. 이러한 분기점에서 추론 경로는 분기되어 자연스럽게 엔트로피가 급증한다. 표준 AR 디코딩은 모델이 이러한 불확실성에 직면하도록 한다. 모델은 이러한 분기점에서 정확히 샘플링함으로써 다양한 추론 경로를 탐색하여 생성된 논리의 다양성을 유지할 수 있다.

그러나 임의 순서 생성은 모델이 이러한 어려운 결정을 건너뛸 수 있도록 한다. 이러한 유연성은 일반적으로 불확실성이 낮은 토큰을 우선시하는 데 활용되어, 연결어를 결정하기 전에 추론 경로를 더 쉬운 부분에 고정시킨다. 모델이 우회된 분기점을 채우기 위해 돌아올 때쯤이면, 확립된 미래 컨텍스트가 해당 분기점의 모호성을 조기에 해소해 버린다. 이러한 현상을 entropy degradation이라 부른다. 즉, 분기점에 원래 내재된 높은 엔트로피가 억제되는 것이다. 모델은 더 이상 분기점을 탐색하는 것이 아니라, 미리 정해진 간극을 연결하기 위해 연결선을 정렬한다.

따라서 저자들은 일반적인 추론 문제에서 dLLM을 위한 RL에 대하여 다시 생각해봤다. 현재 방법들은 임의 순서 유연성을 유지하는 것이 필수적이라는 가정하에 작동한다. 이러한 가정으로 인해 알고리즘은 denoising 궤적의 조합 폭발과 다루기 어려운 marginal likelihood 문제를 해결해야 하므로 부정확한 근사치에 의존할 수밖에 없다. 그러나 임의 순서가 필수적이지 않거나, 목표 task의 잠재력을 이끌어내는 데 오히려 해롭다면 이러한 복잡성은 불필요할 수 있다.

본 논문은 JustGRPO를 통해 단순함으로의 회귀를 제안하였다. 일반적인 추론 문제에 대한 추론 잠재력을 이끌어내는 데 복잡하고 diffusion에 특화된 RL adaptation이 반드시 필요한 것은 아니라는 것을 보여주었다. 오히려 dLLM을 RL 학습 중에 AR policy로 취급하는 것만으로도 효과적으로 달성할 수 있다. 이를 통해 표준 GRPO를 수정 없이 적용할 수 있으며, 기존에는 해결하기 어려웠던 최적화 문제를 명확하게 정의할 수 있다. 중요한 것은 이 AR 공식이 RL 학습 중 탐색을 위해서만 사용되며, dLLM의 원래 아키텍처는 그대로 유지된다는 점이다. 결과적으로 순차적 탐색을 통해 추론 능력을 이끌어내는 것과 dLLM의 병렬 디코딩을 통해 추론 실행을 수행하는 것이 분리된다.

단순함에도 불구하고 JustGRPO는 놀라울 정도로 효과적이다. 복잡한 RL adaptation에 의존하는 방법들과 비교해도 우수한 결과를 보여주었다. 더욱 중요한 것은 AR로 학습된 모델이 병렬 디코딩과 완벽하게 호환된다는 점이다. 이는 AR 탐색을 통해 얻은 추론 능력이 dLLM의 추론 효율성을 저해할 필요가 없음을 시사한다.

The Flexibility Trap

저자들은 임의 순서 생성의 유연성이 더 높은 추론 잠재력으로 이어지는지 경험적으로 검증하고자 하였으며, 두 가지 디코딩 모드를 비교하였다.

1. 임의 순서 모드: 낮은 신뢰도의 리마스킹을 사용하는 표준 diffusion 디코딩을 따름
2. AR 순서 모드: 임의 순서 유연성이 비활성화되고 생성이 왼쪽에서 오른쪽으로의 디코딩으로 엄격하게 제한

1. Arbitrary Order Can Limit Reasoning Potential

Pass@k 분석

Pass@k는 $k$개의 독립적인 샘플 내에서 적어도 하나의 올바른 솔루션이 생성될 확률을 측정하는 것으로, RL 최적화에서 접근 가능한 solution space의 상한을 효과적으로 나타낸다. 주어진 $n$개의 샘플 중에 $c$개가 정답인 경우, Pass@k는 다음과 같이 계산된다.

\[\begin{equation} \textrm{Pass@k} = \mathbb{E} \left[ 1 - \frac{\binom{n-c}{k}}{\binom{n}{k}} \right] \end{equation}\]

저자들은 3가지 대표적인 dLLM(LLaDA-Instruct, Dream-Instruct, LLaDA 1.5)에 대해 GSM8K, MATH-500, HumanEval, MBPP의 4가지 추론 벤치마크에서 Pass@k를 사용하여 추론 가능성을 평가했다.

위 그래프들에서 볼 수 있듯이, 임의 순서 모드는 $k=1$에서 경쟁력 있는 성능을 보이거나 많은 경우 더 나은 성능을 보이지만, AR 모드에 비해 scaling curve가 상당히 완만하다. $k$가 증가함에 따라 AR 모드는 더 많은 정답을 찾아내는 능력을 보여준다.

Solution space 범위

임의 순서 생성이 비록 효율성은 떨어지지만 다른 solution space를 탐색하여 추론 잠재력이 낮아지는 원인이 될 수 있는지 궁금할 수 있다. 저자들은 LLaDA-Instruct를 사용하여 $k=1024$에서의 solution 범위를 분석함으로써 이를 검증했다.

임의 순서(AO) 생성을 통해 얻은 해답은 AR 디코딩을 통해 발견된 해답과 상당 부분 겹치며, 실제로는 더 작은 부분집합을 형성한다. 이론적으로 임의 순서 생성은 더 큰 solution space를 의미하지만, 실제 샘플링 환경에서 도달 가능한 해답의 집합은 더 제한적인 것으로 나타난다.

임의성이 클수록 잠재력은 줄어든다.

지금까지는 임의 순서와 AR 순서를 두 가지 극단으로 대조해 왔지만, 임의성의 정도는 이분법적으로 나눌 수 없다. dLLM의 semi-autoregressive 프로토콜은 block 크기 $B$를 통해 이를 제어한다. 시퀀스는 크기 $B$의 block으로 나뉘고, 각 block 내에서 모델은 unmasking할 토큰을 적응적으로 선택한다. 따라서 $B$는 모델이 다음 위치를 자유롭게 선택할 수 있는 범위를 설정하며, $B=1$일 때는 순수 AR 순서이고, $B$가 클수록 임의적인 디코딩이 더 많이 허용된다. 위의 실험 결과들은 $B=32$를 사용했다.

저자들은 $B$ 값을 변화시키면서 임의성의 정도가 추론 잠재력에 어떤 영향을 미치는지 살펴보았다.

위 그래프에서 볼 수 있듯이, 추세는 일관적이고 단조롭다. 즉, 모든 $k$에 걸쳐 $B$가 증가함에 따라 Pass@k는 감소한다. 이는 효과가 두 극단적인 설정에 국한되지 않고 일관적임을 시사한다. 즉, 임의성이 낮을수록 추론 잠재력이 일관적으로 높아진다.

2. Mechanism: The Entropy Degradation

적응형 디코딩은 논리적 분기를 우회한다.

이론적으로 더 큰 dLLM의 solution space가 실제로 축소되는 이유를 이해하기 위해 두 가지 디코딩 모드의 동작 방식을 자세히 살펴보자. AR 순서에서는 모델이 각 단계에서 가장 왼쪽에 있는 미지의 토큰을 해결해야 하므로 불확실성이 발생할 때마다 모델이 이를 처리해야 한다. 반면, 임의 순서는 모델이 업데이트할 토큰을 적응적으로 선택하여 쉬운 토큰을 우선적으로 생성하고 어려운 토큰은 우회한다. 자주 우회되는 토큰을 살펴보면 명확한 패턴이 나타난다.

위 그림은 자주 우회되는 토큰들을 나타낸 것이다. 샘플러는 “Therefore”, “Thus”, “Since”와 같은 논리 연결어 및 전환 마커를 불균형적으로 지연시킨다. 이러한 토큰들은 높은 엔트로피를 가지며, 후속 추론 방향을 결정하는 분기점 역할을 하는 논리적 분기점으로 작용한다. 기존 언어 모델에서는 추론 공간을 효과적으로 탐색하기 위해 이러한 토큰을 높은 엔트로피 상태로 유지하는 것이 중요하다.

Entropy degradation 현상

임의 순서의 적응적 동작은 이러한 논리적 분기 토큰에 어떤 영향을 미칠까? 저자들은 논리적 분기 토큰들이 디코딩될 때의 엔트로피를 측정했다.

AR 순서에서는 이러한 토큰이 디코딩될 때 일반적으로 높은 엔트로피를 유지하는데, 이는 여러 추론 경로가 여전히 유효한 비교적 생산적인 분기점을 나타낸다. 반면, 임의 순서에서는 엔트로피가 급격히 감소한다. 논리적 연결 고리를 연기함으로써 모델은 논리적 연결을 결정하기 전에 더 쉬운 미래 토큰을 생성하는 데 우선순위를 둔다. 모델이 결국 건너뛴 연결 고리를 채우기 위해 돌아올 때, 미래 컨텍스트의 존재는 불확실성을 크게 줄인다. 결과적으로 모델은 더 이상 분기점에서 탐색 결정을 내리는 것이 아니라, 미리 정해진 결론으로 ​​가는 간극을 메운다. 이러한 현상을 entropy degradation이라고 부른다.

“Just GRPO” for dLLMs

1. The Flexibility Tax in dLLMs’ RL

기존의 diffusion RL 방법은 policy가 임의의 순서 생성을 유지하기 위해 denoising 궤적 $T$의 조합 공간을 수용해야 한다는 전제 하에 작동한다. 이러한 설계 선택은 개념적으로는 일반적이지만 몇 가지 문제점을 야기한다.

토큰 수준 분해의 모호성

dLLM에서 생성 state $s_t$는 확률적 unmasking 궤적 $\tau$에 따라 컨디셔닝된 noisy한 시퀀스이다. AR 모델과 달리 dLLM은 $\pi (o_t \mid s_t)$ 형태의 조건부 확률을 허용하지 않으므로 토큰 수준의 크레딧 할당이 모호해지고 표준 중요도 비율 \(\rho_t = \frac{\pi_\theta (o_t \vert s_t)}{\pi_\textrm{old} (o_t \vert s_t)}\)를 정의하기 어렵다.

다루기 어려운 시퀀스 likelihood

AR 모델은 시퀀스 likelihood를 \(\log \pi(o) = \sum_t \log \pi(o_t \vert o_{< t}, q)\)로 분해하는 반면, dLLM은 모든 유효한 denoising 궤적에 대한 marginalization \(\pi_\theta (o \vert q) = \sum_{\tau \in \mathcal{T}} \pi_\theta (o, \tau \vert q)\)를 요구한다. 길이가 $N$인 시퀀스의 경우, 궤적 공간은 $\vert \mathcal{T} \vert = O(N!)$으로 증가하여 정확한 likelihood 계산이 불가능해지고, 기존 방법들은 원래 objective 대신 ELBO objective에 의존할 수밖에 없다.

실제 샘플링과 최적화 사이의 불일치

실제로 rollout 샘플은 일반적으로 조합 공간을 탐색하기 위해 신뢰도 기반 생성 \(o \sim \pi_\theta^\textrm{conf} (o \vert q)\)를 통해 생성된다. 그러나 ELBO objective는 실제 샘플링 policy의 likelihood \(\pi_\theta^\textrm{conf} (o \vert q)\)가 아닌 원래 모델 분포의 likelihood \(\pi_\theta (o \vert q)\)를 타겟으로 하므로 rollout과 최적화 간의 불일치가 발생하여 성능이 저하될 수 있다.

2. JustGRPO

본 논문에서는 단순함으로의 회귀를 제안하였다. 순수 AR 순서가 더 높은 추론 잠재력을 보여주므로, RL 단계에서 임의 순서 생성을 명시적으로 배제한다.

표준 GRPO는 모든 토큰이 관찰된 부분 시퀀스 $o_{< k}$를 허용하는 policy \(\pi (o_k \vert o_{< k}, q)\)를 가정하며, query $q$에 대해 한 번에 하나의 토큰 $o_k$를 예측한다. 반면 dLLM은 관찰된 토큰과 마스킹된 토큰이 혼합된 전체 시퀀스를 허용하고 모든 마스킹된 위치에 대한 원래 값을 동시에 예측하는 시퀀스 수준의 denoiser로 설계되었다.

임의 순서 생성을 포기함으로써, dLLM에 대한 AR policy \(\pi_\theta^\textrm{AR}\)를 엄밀하게 정의할 수 있다. 과거 $o_{< k}$가 주어졌을 때 다음 토큰이 $o_k$일 확률을 얻기 위해, 과거는 관찰되고 미래는 가려진 \(\tilde{x}_k\)를 구성한다.

\[\begin{equation} \tilde{x}_k = [o_1, \ldots, o_{k-1}, \textrm{[MASK]}, \ldots, \textrm{[MASK]}] \end{equation}\]

dLLM은 모든 마스킹된 위치에 대한 예측을 출력하지만, AR policy는 다음 토큰 $o_k$에만 관련된다.

\[\begin{equation} \pi_\theta^\textrm{AR} (\cdot \vert o_{< k}, q) = \textrm{Softmax}(f_{\theta, k} (\tilde{x}_k, q)) \end{equation}\]

(\(f_{\theta, k}\)는 위치 $k$에서의 모델 logit)

dLLM 기반 위에 AR policy를 정의함으로써, 다루기 어려운 marginalization을 정확하게 계산 가능한 likelihood로 변환한다.

\[\begin{equation} \pi_\theta^\textrm{AR} (o \vert q) = \prod_{k=1}^{\vert o \vert} \pi_\theta^\textrm{AR} (o_k \vert o_{< k}, q) \end{equation}\]

최적화

이제 표준 GRPO를 dLLM에 직접 적용할 수 있다. 각 query $q$에 대해, 기존 policy \(\pi_{\theta_\textrm{old}}^\textrm{AR}\)를 사용하여 \(\{o_i\}_{i=1}^G\)을 샘플링한다. Objective는 다음과 같다.

\[\begin{equation} \mathcal{J} (\theta) = \mathbb{E}_{q \sim P(Q), \{o_i\}_{i=1}^G \sim \pi_{\theta_\textrm{old}}^\textrm{AR}} \left[ \frac{1}{G} \sum_{i=1}^G \frac{1}{\vert o_i \vert} \sum_{k=1}^{\vert o_i \vert} \left( \min (\rho_{i,k} \hat{A}_{i,k}, \textrm{clip} (\rho_{i,k}, 1 - \epsilon, 1 + \epsilon) \hat{A}_{i,k}) - \beta \mathbb{D}_\textrm{KL} \right) \right] \\ \textrm{where} \quad \rho_{i,k} = \frac{\pi_\theta^\textrm{AR} (o_{i,k} \vert o_{i,< k}, q)}{\pi_{\theta_\textrm{old}}^\textrm{AR} (o_{i,k} \vert o_{i,< k}, q)} \end{equation}\]

AR 모드 학습이 diffusion model을 근본적으로 AR 모델로 바꾸는 것은 아니다. AR 제약 조건은 보다 효과적인 탐색과 크레딧 할당을 위해 RL 학습 중에만 적용된다. 중요한 것은, 이 방식이 구조적 제약(ex. causal masking)을 가하지 않고 모델 분포를 개선한다는 점이다. 따라서 JustGRPO는 dLLM의 병렬 기능을 유지하면서 AR 기반 추론 탐색의 이점을 누릴 수 있다.

Experiments

1. Main Results

다음은 LLaDA-Instruct 모델에 대한 여러 post-training 방법들과 비교한 결과이다.

다음은 동일한 설정으로 재학습시킨 baseline들과 비교한 결과이다. (full fine-tuning, 디코딩 step당 토큰 1개, 생성 길이 256)

2. JustGRPO Preserves Parallel Decoding

다음은 병렬 디코딩 시의 성능을 비교한 결과이다.

3. Training Efficiency

다음은 GSM8K에서의 학습 효율성을 비교한 그래프이다.