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

Вычислительная сложность self-attention в трансформерах обычно составляет O(n²), где n — длина входной последовательности.

Причина в том, что self-attention вычисляет взаимосвязи между каждым элементом последовательности и всеми остальными. Для этого строится матрица внимания размером n×n, где каждая ячейка отражает влияние одного элемента на другой.

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