Как борются с квадратичной сложностью внимания?
Комментарии (2)
Ответ сгенерирован нейросетью и может содержать ошибки
Борьба с квадратичной сложностью механизма внимания
Стандартный механизм Self-Attention имеет сложность O(n²), где n — длина последовательности. Для длинных текстов это становится узким местом. Вот основные подходы к оптимизации:
1. Sparse (Разреженное) внимание
Идея: вычислять внимание не ко всем позициям, а только к локально важным.
- Local Attention: каждый токен смотрит только на соседей
- Strided Attention: пропускаем позиции с заданным шагом
- Dilated Attention: комбинация локального с прыжками
Примеры: Longformer, BigBird, Reformer
2. Low-rank approximation (Низкоранговая аппроксимация)
Гипотеза: матрица внимания часто имеет низкий эффективный ранг. Можно разложить на произведение меньших матриц.
- Linformer: аппроксимация через проекцию
- Performer: использует ядра (kernels) и случайные признаки
Это дает O(n) сложность вместо O(n²).
3. Memory/Retrieval augmented (С внешней памятью)
Идея: вместо смотрения на все позиции, извлекаем k релевантных из внешней памяти.
- kNN-Transformer: используем KNN-индекс
- Retrieval-Augmented Attention: FAISS для быстрого поиска
Сложность: O(n*k) где k << n
4. Multi-Query & Grouped Query Attention
Оригинальный Transformer: каждый head имеет собственные K и V. Оптимизация: разделить несколько heads на одну пару K, V.
Экономия: 10-25% памяти, 10-20% ускорение
Примеры: llama-2, GPT-3.5
5. Flash Attention
Не меняет алгоритм, а оптимизирует вычисления через блочные операции и лучший I/O.
Идея:
- Вычисляем внимание блоками
- Минимизируем обращение к глобальной памяти GPU
- Используем быструю SRAM
Результат: 2-4x ускорение, 5-20% экономия памяти
6. Длинные позиционные кодировки
Проблема: стандартные RoPE работают для длин ~2K токенов.
Решения:
- ALiBi (Attention with Linear Biases): вместо embeddings добавляем bias
- Position Interpolation: интерполируем embeddings
- NTK-RoPE: динамически масштабируем частоты
Сравнение подходов
| Метод | Сложность | Память | Стабильность |
|---|---|---|---|
| Sparse (Local) | O(n) | Низкая | Высокая |
| Flash Attention | O(n²) | -20% | Высокая |
| Linformer | O(n) | Низкая | Средняя |
| Multi-Query | O(n²) | -20% | Высокая |
| ALiBi | O(n²) | Normal | Высокая |
Практические рекомендации
- Для коротких последовательностей (<2K): Flash Attention
- Для длинных (2K-32K): Flash Attention + Sparse Attention
- Для очень длинных (>32K): Linformer или Local Attention
- Для инфиренса: Multi-Query Attention
- Если нужна экстраполяция длины: ALiBi вместо RoPE
Выбор зависит от задачи, доступного железа и требований к стабильности. Современные модели часто комбинируют несколько техник одновременно для максимальной эффективности.