Что такое Linformer и почему линейная сложность ему удаётся?

Linformer — это архитектура трансформера, которая снижает вычислительную сложность внимания с квадратичной (O(n²)) до линейной (O(n)) по длине последовательности.

Ключевая идея Linformer — аппроксимировать матрицу внимания с помощью низкорангового представления. Вместо вычисления полного внимания между всеми парами токенов, Linformer проецирует ключи и значения в пространство меньшей размерности с помощью обучаемых линейных проекций.

Это позволяет:

• Сократить размерность ключей и значений,
• Уменьшить количество вычислений при умножении матриц,
• Снизить потребление памяти.

Таким образом, линейная сложность достигается за счёт использования фиксированной размерности проекции, которая не зависит от длины входной последовательности, что делает Linformer эффективным для длинных текстов и больших последовательностей.

Примерно это можно представить так:

• Вместо вычисления внимания: Attention(Q, K, V) = softmax(QKᵀ / sqrt(d)) V
• Linformer вычисляет: Attention(Q, E K, F V), где E и F — обучаемые матрицы проекции, уменьшающие размерность K и V.

Это упрощает вычисления и снижает сложность до O(n).