Классы алгоритмической сложности для трансформеров

Сначала расскажу про более объёмную статью, которую мы выпустили на этой неделе. Мы пытаемся дать теоретические оценки того, как эффективно трансформеры решают те или иные алгоритмические задачи. Алгоритмы – это такой ключик к пониманию способностей моделей рассуждать.

Про трансформерные модели мы знаем довольно много: они Тюринг-полные – правда, при polylog-числе слоёв, а при константной глубине они ограничены классом TC0. Это всё, конечно, очень интересно 😐, но хочется изучать трансформеры в более реалистичных сценариях.

Вот тут на сцену выходим мы🤴! В статье мы анализируем девять графовых алгоритмов 👥, которые трансформеры решают в трёх разных режимах параметров. Под параметрами в статье понимаем ширину слоя m, глубину сети L, и аналог chain-of-though токенов, которые позволяют модели покряхтеть над задачкой подольше. 🤔

Внимательный подпищеки заметили 🧐, что алгоритмы мы рассматриваем только графовые. Не серчайте – это всё ради науки! Сложность графовых задач легко варьировать, к тому же, существует сильно больше классов задач, чем для операций с символьными манипуляцями.

Совсем простые задачи 😛, например, как подсчет узлов или рёбер, могут быть решены трансформерами глубины один с шириной log 𝐍. Трансформеры также могут выполнять параллельные алгоритмы - мы нашли три задачи, которые могут быть эффективно решены с помощью трансформеров глубины log 𝐍.

А ещё на графах мы можем сравнить трансформеры с графовыми нейросетями. Теоретически мы показываем случаи, где трансформерам нужно меньше вычислений для решения разных задач, и на практике показываем, как с некоторыми алгоритмическими задачами трансформеры справляются лучше GNNок. Да, практическая часть в статье тоже весёлая – мы попробовали посравнивать трансформеры, натренированные для конкретной задачи с файнтьюненными LLMками! А получилось – читать продолжение в источнике…

Статья получилась жирная 🥁 на теоремы и эмпирику, но, надеюсь, кому-нибудь да понравится.