Теория доказала: masked diffusion на трансформерах учится на Õ(LK/ε) примеров

Авторы препринта arXiv:2610.12544 (cs.LG) доказали, что трансформерная masked diffusion model (MDM) учит структурированные дискретные распределения за разумное число примеров. Если данные хорошо приближаются смесью скрытых марковских деревьев, для ε-точной генерации в KL-дивергенции хватает Õ(L·K_par/ε) обучающих образцов. Параметр K_par полиномиально зависит от длины последовательности L, размера словаря V, числа скрытых состояний и числа компонент смеси. Прежние статистические оценки масштабировались как V^L, то есть как число всех возможных последовательностей длины L. Для реальных текстов, кода или белковых цепочек такая цифра ничего не говорит о практике.

Две ошибки, которые раньше считали по отдельности

MDM порождает дискретные данные итеративно. Сначала вся последовательность закрыта масками, затем обученный предиктор масок на каждом шаге раскрывает сразу несколько токенов параллельно. Параллелизм даёт скорость, потому что за один проход генерируется несколько токенов, а не один, как в авторегрессии. Но у скорости есть цена, и ошибок две.

Первая — ошибка параллелизации. Токены, раскрытые на одном шаге, сэмплируются независимо друг от друга, хотя в данных они связаны. Вторая — ошибка оценки: предиктор масок обучен на конечной выборке и неидеален. Существующая теория разбирала эти источники порознь. Здесь же выведена сквозная гарантия, где обе ошибки входят в итоговую KL-оценку одновременно.

Скрытая структура вместо перебора всех последовательностей

Чтобы уйти от V^L, авторы описывают данные через смеси скрытых марковских деревьев. Внутри каждой компоненты токены связаны латентными зависимостями по древовидной топологии. Разные компоненты отражают неоднородность данных: условно, разные жанры, языки или семейства объектов в одном корпусе. Сложность задачи определяется этой скрытой структурой, а не размером пространства последовательностей.

Самое практичное в результате то, что сети и процедуре сэмплирования не нужно знать топологии деревьев и параметры компонент. Трансформер сам подстраивается под неизвестную структуру.

Ключевые параметры результата:

• Модель: трансформерная MDM с параллельными расписаниями раскрытия токенов.
• Класс данных: смеси скрытых марковских деревьев.
• Критерий качества: ε-точность в KL-дивергенции.
• Сложность по выборке: Õ(L·K_par/ε).
• K_par: полином от L, V, числа скрытых состояний и числа компонент.
• Предварительные знания: топология деревьев и параметры компонент не требуются.

Что из этого следует на практике

Работа чисто теоретическая: ни бенчмарков, ни новых чекпойнтов, ни замеров скорости в ней нет. Прямо применить её к обучению конкретной модели не получится. Полиномиальная степень в K_par может оказаться большой, а допущение о смеси скрытых марковских деревьев остаётся идеализацией настоящих корпусов.

Но у результата есть практическая ценность. Команды, которые строят текстовые и кодовые диффузионные модели как альтернативу авторегрессии, получают аргумент в пользу самого подхода. Параллельная генерация не обязана разрушать качество, если расписание раскрытия согласовано со структурой данных. Для тех, кто выбирает число токенов за шаг, это ориентир: ошибку параллелизации нужно учитывать вместе с ошибкой предиктора, а не оптимизировать отдельно.

Для исследователей остаётся открытым вопрос, насколько реальные данные близки к смесям скрытых деревьев и можно ли расширить класс на более сложные зависимости. Пока MDM выглядят заметно лучше обоснованными, чем раньше, но проверка на практике остаётся за эмпирическими работами.