МЕТОДЫ СНИЖЕНИЯ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ SELF-ATTENTION В АРХИТЕКТУРАХ TRANSFORMER

АННОТАЦИЯ

В работе систематизируются основные подходы к преодолению квадратичной вычислительной сложности механизма self-attention — центрального оператора архитектуры Transformer. Выделены четыре ортогональные оси оптимизации: структурное разрежение, низкоранговые и kernel-аппроксимации, системные IO-эффективные реализации точного внимания и замена attention альтернативными операторами смешивания токенов. Показано, что выбор метода определяется не только длиной последовательности n, но и режимом работы модели (обучение или авторегрессивная генерация) и типом узкого места: арифметика, объём памяти или её пропускная способность.

Ключевые слова: Transformer, self-attention, FlashAttention, Mamba, длинный контекст, эффективные модели.

Архитектура Transformer стала фактическим стандартом в обработке естественного языка, компьютерном зрении и биоинформатике. Однако её центральный механизм — self-attention — обладает критическим недостатком: вычислительная стоимость растёт квадратично по длине последовательности. Классическая формула внимания имеет вид:

 — матрицы запросов, ключей и значений.

Промежуточная матрица совместимостей QKᵀ имеет размер n × n, что даёт сложность O(n²) и по времени, и по памяти. Условные нижние оценки, основанные на гипотезе SETH, показывают, что эта граница принципиальна даже для приближённых схем — преодолеть её, не опровергнув SETH, невозможно [1].

Проблема носит универсальный характер. В компьютерном зрении количество визуальных токенов растёт как площадь изображения: удвоение разрешения умножает стоимость attention примерно в шестнадцать раз. В видеоаналитике токены масштабируются как произведение пространственной и временной длины. В биоинформатике длинные геномные и белковые последовательности — норма, а не исключение. Поэтому за последние годы сформировалась целая исследовательская область — efficient Transformers [2].

Важно различать три различных узких места, которые обычно объединяются термином «квадратичная сложность». Во-первых, арифметическая стоимость попарных взаимодействий, измеряемая в FLOPs. Во-вторых, объём памяти, необходимый для хранения промежуточных тензоров и их градиентов при обратном проходе. В-третьих, пропускная способность памяти — особенно критичная в режиме авторегрессивной генерации, где скорость упирается не в вычисления, а в повторную загрузку больших KV-cache из памяти. Это разделение принципиально: разные классы методов оптимизируют разные узкие места, и наивное сравнение «быстрее ли метод X метода Y» без указания режима работы лишено смысла.

Современная литература выделяет несколько ортогональных направлений оптимизации (Таблица 1). Принципиально важно различать, что именно оптимизируется: сам математический оператор внимания или способ его реализации на конкретном оборудовании.

Внутри класса sparse-методов выделяется фиксированное и контент-адаптивное разрежение. Longformer комбинирует локальные окна с глобальными токенами, BigBird добавляет случайные связи и при этом сохраняет универсальную аппроксимацию и Turing-полноту. В классе low-rank/kernel-методов Performer строит несмещённую оценку softmax через FAVOR+, Linformer исходит из эмпирической низкоранговости attention-матрицы, а Nyströmformer аппроксимирует её через landmark-токены [2].

Таблица 1.

Основные классы методов снижения сложности self-attention

Один из ключевых выводов последних лет: асимптотика по времени и асимптотика по операциям ввода-вывода (IO) подчиняются разным законам. Точное self-attention в принципе не обязано требовать O(n²) памяти. Работа Dao et al. [3] предложила алгоритм FlashAttention, который переупорядочивает вычисления так, чтобы полная матрица внимания никогда не материализовалась в медленной памяти HBM. Это даёт до 3× ускорения на GPT-2 и впервые делает достижимыми задачи Path-X при длине n = 16 384. FlashAttention-2 удваивает производительность, выходя на 225 TFLOPs/s на GPU A100; FlashAttention-3 на архитектуре Hopper с поддержкой FP8 приближается к 1,2 PFLOPs/s. Принципиально важно, что это точное, а не приближённое внимание — выигрыш достигается за счёт системной инженерии, а не математической аппроксимации.

Параллельно развивается направление полной замены attention. Mamba и Mamba-2 [4] предлагают селективные state-space models (SSM) с линейным масштабированием O(n) и высокой пропускной способностью при инференсе. Однако крупномасштабные сравнения показывают: чистые SSM уступают Transformers именно на задачах, требующих сильного associative recall, in-context learning и точного long-context reasoning. Отсюда — рост популярности гибридных архитектур (например, Jamba), сочетающих attention-слои с SSM-блоками.

Особенно нагляден trade-off, формализованный в работе Based [5]: между размером скрытого состояния модели и её способностью к ассоциативному recall существует фундаментальная связь. При декодировании 1024 токенов на модели с 1,3 млрд параметров Based достигает в 24× большего throughput, чем FlashAttention-2 — но ценой компромисса по recall-способностям. Эта картина типична: за линейную сложность приходится платить либо точностью softmax-внимания, либо ограничением на типы зависимостей в данных.

Бенчмарк Long Range Arena остаётся главным инструментом для сопоставления long-context архитектур. Его центральный вывод — отсутствие универсального решения: BigBird лидирует по интегральному качеству, Performer — по скорости, Linformer — по экономии памяти (Таблица 2).

Таблица 2.

Сравнение на Long Range Arena при длине входа n = 4096

Современные эффективные Transformer-архитектуры образуют не линейную шкалу «хуже–лучше», а пространство ортогональных компромиссов между выразительностью, точностью, аппаратной эффективностью и контролируемым расходом памяти. Время и память подчиняются разным теоретическим законам: квадратичная нижняя оценка по времени остаётся принципиальной [1], но память может быть сведена к субквадратичной без потери точности [3]. Практический дизайн long-context модели почти всегда многослоен — архитектурный prior, kernel-level оптимизация, decode-side cache optimization (MQA, GQA) и гибридный backbone работают совместно. Главный методологический вывод: формулировка «какой Transformer быстрее всех» некорректна без указания режима работы и типа bottleneck.

Список литературы:

1. Duman Keles F., Wijewardena P. M., Hegde C. On the Computational Complexity of Self-Attention // Proceedings of the 34th International Conference on Algorithmic Learning Theory (ALT). — 2023. — URL: https://proceedings.mlr.press/v201/duman-keles23a.html.
2. Efficient Transformers: A Survey / Y. Tay, M. Dehghani, D. Bahri, D. Metzler // ACM Computing Surveys. — 2022. — Vol. 55, No. 6. — Art. 109.
3. FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness / T. Dao [и др.] // Advances in Neural Information Processing Systems (NeurIPS). — 2022. — URL: https://proceedings.neurips.cc/paper_files/paper/2022/hash/67d57c32e20fd0a7a302cb81d36e40d5-Abstract-Conference.html.
4. Gu A., Dao T. Mamba: Linear-Time Sequence Modeling with Selective State Spaces [Электронный ресурс]. — 2023. — URL: https://openreview.net/pdf?id=tEYskw1VY2.
5. Simple Linear Attention Language Models Balance the Recall-Throughput Tradeoff / S. Arora [и др.] // Proceedings of the 41st International Conference on Machine Learning (ICML). — 2024.