Какова вычислительная сложность механизма self-attention?

В оригинальной статье Attention Is All You Need есть таблица со сравнением Complexity per Layer (сложность на слой) нового механизма self-attention и других архитектур. Указано, что для self-attention это значение составляет O(n^2 * d), где d — это размерность векторного представления.

В статье есть один нюанс. Авторы не учитывали сложность вычисления матриц Q, V и K (query, value и key). Их значения были взяты из скрытых состояний RNN. Поэтому идёт «чистый» расчёт для слоя Attention.

#вопросы_с_собеседований