Как глубина LLM связана с максимально разрешимой алгоритмической сложностью?

Придумал я, казалось бы, гениальную идею для новой научной работы, быстренько закодил за выходные, увидел офигенные результаты, подтверждающие мою гипотезу — и только после этого додумался спросить у Deep Research, не дебил ли я.

Итак, представляю вам разбор статьи «Transformers, parallel computation, and logarithmic depth», вышедшей год назад 🤬

Основная фишка статьи — задача chasing pointer. Суть простая: у вас есть цепочка индексов (целых чисел), где каждый индекс ведёт на другой элемент (индекс \ указатель) в последовательности. Задача модели — пройти назад по этим указателям и найти элемент массива на k прыжков назад за один forward pass.

Авторы строго показывают, что глубина трансформера критически важна и определяет максимально возможное число таких прыжков (сложность задачи), которое модель способна эффективно решить. Причём связь эта экспоненциальная: трансформеру с глубиной L доступно O(2^L) прыжков за один шаг.

Проще говоря: никакое увеличение ширины, количества голов внимания или MOE экспертов не заменит глубину. Тут речь именно про внутренние, архитектурные вычисления, а не Chain-of-Thought, то есть мы требуем чтобы модель выдала ответ сразу, без рассуждений.

P.S. Кстати, я потестил Claude-4 и ChatGPT-4.1 \ 4.5 — у всех предел наступает примерно на 25 прыжках, значит ли это, что их эффективная глубина всего 5 слоёв? 😄 (но на самом деле это потому, что их не обучали на эту задачу)

Статья