Conditional Total Correlation and the Serial Depth of Adaptive Parallel Sampling

Background Masked diffusion language models (MDLMs) generate text by revealing masked positions over multiple rounds, choosing in each round which positions to fill based on model confidence in its own predictions -- a design that trades sequential (autoregressive) generation for parallelism, at the cost of some accuracy because tokens revealed in the same round are sampled independently even though the true distribution treats them as dependent.

배경 마스크 확산 언어모델(MDLM)은 여러 라운드에 걸쳐 마스크된 위치를 드러내며 텍스트를 생성하는데, 각 라운드에서 어느 위치를 채울지는 모델 자신의 예측에 대한 신뢰도를 기준으로 정한다 -- 이는 순차적(자기회귀) 생성을 병렬성과 맞바꾸는 설계이며, 같은 라운드에서 드러난 토큰들이 실제 분포에서는 서로 의존적임에도 독립적으로 샘플링되기 때문에 일부 정확도를 대가로 치른다.

Problem No existing theory pinned down the minimum number of rounds a value-adaptive policy needs to hit a given accuracy target for a fixed, known target distribution -- prior analyses either fixed the reveal schedule in advance (not adapting to what has already been generated) or bounded round complexity using entropy or negative log-likelihood, quantities this paper shows are fundamentally insufficient: two distributions with identical entropy can require a different number of rounds.

문제 기존 이론 중 어느 것도 고정된, 알려진 목표 분포에 대해 값 적응적(value-adaptive) 정책이 주어진 정확도 목표를 달성하는 데 필요한 최소 라운드 수를 정확히 짚어내지 못했다 -- 기존 분석들은 리빌 스케줄을 사전에 고정하거나(이미 생성된 것에 적응하지 않음), 엔트로피나 음의 로그우도로 라운드 복잡도를 경계 지었는데, 이 논문은 이 값들이 근본적으로 불충분함을 보인다: 엔트로피가 동일한 두 분포도 필요한 라운드 수가 다를 수 있다.

Prior limitations Entropy- and likelihood-based round bounds are properties of a specific decoder class (e.g. confidence-thresholded decoders), not of the target distribution itself -- a distribution can have high entropy yet fully independent coordinates that need only one round, so no entropy-based argument can certify how many rounds a general adaptive policy truly needs.

기존 한계 엔트로피, 우도 기반 라운드 경계는 목표 분포 자체가 아니라 특정 디코더 클래스(예: 신뢰도 임계값 디코더)의 성질이다 -- 어떤 분포는 엔트로피가 높으면서도 좌표들이 완전히 독립적이어서 단 한 라운드만 필요할 수 있으므로, 엔트로피 기반 논증만으로는 일반 적응 정책이 실제로 몇 라운드를 필요로 하는지 확정할 수 없다.

Goal The goal is to find the exact quantity that governs how many rounds of independent-within-round sampling are unavoidable for a given distribution and error budget, and to check what it implies for the confidence-based decoding rules real masked diffusion models actually deploy.

목표 목표는 주어진 분포와 오차 예산에 대해 라운드 내 독립 샘플링이 몇 라운드까지 불가피한지를 지배하는 정확한 양을 찾아내고, 이것이 실제 마스크 확산 모델이 배포하는 신뢰도 기반 디코딩 규칙에 무엇을 함의하는지 확인하는 것이다.

Method The authors define serial depth as the minimum expected number of reveal rounds needed to meet a KL-divergence accuracy target, then prove that this error exactly equals the expected conditional total correlation -- a classical multivariate-dependence quantity -- accumulated over the policy reveal rounds. They then derive round-complexity bounds for several distribution families (Markov chains, random walks, random permutations, structured binary strings) and separately measure realized costs on a small masked diffusion model (Qwen2.5-0.5B) converted to an MDLM and run on real WikiText text.

방법 저자들은 시리얼 깊이(serial depth)를 KL 발산 정확도 목표를 만족하는 데 필요한 최소 기대 리빌 라운드 수로 정의한 뒤, 이 오차가 정확히 정책의 리빌 라운드에 걸쳐 누적된 조건부 총상관량(conditional total correlation, 고전적인 다변량 의존성 지표) 값과 같음을 증명한다. 이어서 여러 분포 계열(마르코프 연쇄, 랜덤 워크, 랜덤 순열, 구조화된 이진 문자열)에 대한 라운드 복잡도 경계를 유도하고, 별도로 작은 마스크 확산 모델(Qwen2.5-0.5B를 MDLM으로 변환)을 실제 WikiText 텍스트에서 구동해 실측 비용을 측정한다.

Key idea The key idea is that total correlation -- not entropy, not likelihood -- is the exact currency of parallel-decoding cost: every bit of dependence a policy discards by sampling several positions independently in one round shows up, without approximation, as forward-KL error. This reframes the vague intuition of why parallel decoding loses accuracy into an exact accounting identity, the way a strict energy-conservation law lets a system behavior be predicted rather than only observed empirically.

핵심 아이디어 핵심 아이디어는 병렬 디코딩 비용의 정확한 통화가 엔트로피도 우도도 아닌 총상관량이라는 것이다: 정책이 한 라운드에서 여러 위치를 독립적으로 샘플링함으로써 버리는 의존성의 매 비트는 근사 없이 정확히 forward-KL 오차로 나타난다. 이는 왜 병렬 디코딩이 정확도를 잃는가라는 막연한 직관을 정확한 회계 항등식으로 바꾸는데, 엄밀한 에너지 보존 법칙이 시스템의 거동을 경험적으로 관찰하는 대신 예측할 수 있게 해주는 것과 비슷하다.

Validation Beyond the exact theorems (proved for idealized distributions with known conditionals), the authors run a controlled empirical study on 542 real texts (WikiText plus model-generated code/math/prose/structured-data samples), comparing left-to-right, random, hierarchical-bisection, and greedy-confidence reveal schedules, and then measuring the schedules actually deployed by masked diffusion decoders (confidence top-k, global/block thresholding) under the identical protocol.

검증 이상화된 분포에 대해 증명된 정확한 정리들 외에도, 저자들은 542개의 실제 텍스트(WikiText와 모델 생성 코드, 수학, 산문, 구조화 데이터 샘플)에 대한 통제된 실증 연구를 수행하여 좌에서 우로, 무작위, 계층적 이분법, 탐욕적 신뢰도 순서의 리빌 스케줄을 비교한 다음, 마스크 확산 디코더가 실제로 배포하는 규칙들(신뢰도 top-k, 전역/블록 임계값)을 동일한 프로토콜 하에서 측정한다.

Results Left-to-right block decoding -- the standard semi-autoregressive mode most deployed dLLMs use -- is the worst reveal order, costing 2.7-29x more than random order at matched round budgets. Greedy minimum-confidence selection, the exact heuristic underlying standard MDLM decoders, costs 1.4-13x more than simple random-order reveals at equal parallelism, losing on every one of the 542 tested texts for the top-16 comparison. Threshold decoders achieve near-zero measured error only by secretly near-fully serializing -- at a 0.99 confidence threshold, on average only about one position clears the bar per round.

결과 배포된 dLLM 대부분이 사용하는 표준 준-자기회귀 모드인 좌-우 블록 디코딩이 동일 라운드 예산에서 무작위 순서보다 2.7~29배 더 비싼, 가장 나쁜 리빌 순서임이 밝혀졌다. 표준 MDLM 디코더의 근간이 되는 정확히 그 휴리스틱인 탐욕적 최소 신뢰도 선택은 동일한 병렬성에서 단순 무작위 순서 리빌보다 1.4~13배 더 비싸며, top-16 비교에서는 테스트된 542개 텍스트 전부에서 패배한다. 임계값 디코더는 사실상 거의 완전히 순차화함으로써만 근제로 오차를 달성한다 -- 신뢰도 임계값 0.99에서는 라운드당 평균 약 한 개의 위치만 기준을 통과한다.

Comparison Against generic reference schedules at matched round counts, the deployed confidence-based rules are 3.9-11x more information-theoretically costly than a simple random-order or hierarchical schedule -- the diagnostic in this paper directly separates the information cost of parallelism (measured here) from the wall-clock speedups threshold decoders report elsewhere, which the authors attribute to caching and self-generation confidence dynamics rather than to genuinely resolving more dependence per round.

비교 동일 라운드 수의 일반 참조 스케줄 대비, 배포된 신뢰도 기반 규칙들은 정보이론적으로 3.9~11배 더 비싸다 -- 이 논문의 진단은 여기서 측정한 병렬성의 정보 비용을, 다른 곳에서 보고되는 임계값 디코더의 실시간(wall-clock) 속도 향상과 명확히 분리한다. 저자들은 후자를 라운드당 더 많은 의존성을 실제로 해소해서가 아니라 캐싱과 자기생성 신뢰도 동역학 때문이라고 본다.

Significance For anyone building or evaluating masked-diffusion decoding schedules, this gives a decoder-independent diagnostic -- conditional total correlation, or its practically measurable pseudo-cost proxy -- that can audit a proposed decoding rule before deployment, rather than only benchmarking wall-clock speed after the fact; it also gives a principled explanation for why the field default confidence-ordering heuristic is a specifically costly choice, not just an empirically imperfect one.

의의 마스크 확산 디코딩 스케줄을 설계하거나 평가하는 사람에게, 이 논문은 배포 후 실시간 속도만 벤치마킹하는 대신 배포 전에 제안된 디코딩 규칙을 감사할 수 있는 디코더 독립적 진단 도구(조건부 총상관량, 또는 그 실용적으로 측정 가능한 의사비용 대리지표)를 제공한다. 또한 이 분야의 기본값인 신뢰도 순서 휴리스틱이 그저 경험적으로 불완전한 선택이 아니라 특히 비용이 큰 선택임을 원리적으로 설명해준다.

Limitations The theorems apply to an idealized exact conditional-marginal oracle; the empirical measurements on a real MDLM are honestly flagged as order-dependent pseudo-costs rather than the total correlation of one coherent joint distribution, since a learned model conditionals need not be globally consistent. The empirical study also uses a single, small (0.5B-parameter) model and a single sampling temperature, which the authors explicitly call diagnostic rather than a universal benchmark.

한계 정리들은 이상화된 정확한 조건부 주변확률 오라클에 적용된다. 실제 MDLM에 대한 실증 측정치는 학습된 모델의 조건부 확률이 전역적으로 일관될 필요가 없기 때문에, 하나의 정합적인 결합분포의 총상관량이 아니라 순서 의존적인 의사비용(pseudo-cost)이라고 정직하게 명시된다. 실증 연구도 단일하고 작은(0.5B 파라미터) 모델과 단일 샘플링 온도만 사용했으며, 저자들은 이를 명시적으로 범용 벤치마크가 아닌 진단적 성격이라고 밝힌다.

Future work The paper leaves as an explicit open theoretical question whether binary-alphabet serial depth can exceed the square-root exponent established here, up to the linear depth achieved by uniform random permutations.

향후 과제 논문은 이진 알파벳에서의 시리얼 깊이가 저자들이 확립한 제곱근 지수를 넘어, 균등 무작위 순열이 달성하는 선형 깊이까지 도달할 수 있는지를 명시적인 열린 이론적 질문으로 남긴다.

Released resources No public code release verified.

자원 공개 공개된 코드 배포는 확인되지 않았다.