Какой вид attention позволяет снизить сложность ниже O(n²)?

Для снижения вычислительной сложности внимания (attention) ниже квадратичной O(n²) применяются различные виды sparse или линейного внимания. Один из популярных подходов — Linformer.

Linformer сокращает размер матриц внимания, проецируя ключи и значения в низкоразмерное пространство, что уменьшает сложность до O(n).

Другие методы:

• Performer — использует случайные проекции и ядра для приближенного вычисления внимания с линейной сложностью.
• Reformer — применяет локальное внимание и хэширование для уменьшения вычислений.
• Longformer — комбинирует локальное и глобальное внимание, снижая сложность.

Пример концепции линейного внимания:

# Псевдокод для линейного внимания
Q = query_matrix
K = key_matrix
V = value_matrix

# Проекция K и V в низкоразмерное пространство
K_proj = projection_matrix @ K
V_proj = projection_matrix @ V

# Вычисление внимания с пониженной размерностью
attention = softmax(Q @ K_proj.T) @ V_proj

Таким образом, уменьшается объем вычислений и памяти, что позволяет обрабатывать более длинные последовательности.