Какая сложность по памяти и по времени у self-attention?

Self-attention в трансформерах вычисляет взаимосвязи между всеми элементами входной последовательности, что влияет на сложность алгоритма.

Пусть длина последовательности — N, размерность признаков — d.

• Временная сложность: O(N² * d)

  Это связано с тем, что для каждого из N элементов нужно вычислить внимание к каждому из N элементов, а затем применить операции с размерностью d.

• Пространственная сложность: O(N²)

  Требуется хранить матрицу весов внимания размером N×N.

Из-за квадратичной зависимости по длине последовательности self-attention становится узким местом при работе с очень длинными входами, что стимулирует разработку оптимизаций и альтернативных архитектур (например, sparse attention).