- En Transformers de contexto largo, cuando el costo de self-attention se vuelve un cuello de botella, SPECTRE reduce la complejidad por capa de O(L²) a O(L log L) con un mezclador de tokens basado en FFT
- Cada head de attention se reemplaza por una combinación de FFT real rápida, compuerta espectral adaptativa al contenido e inverse FFT, manteniendo la estructura existente del Transformer
- En la generación autorregresiva, el Prefix-FFT cache reduce la carga de recalcular la FFT en cada paso, y un módulo wavelet opcional puede compensar la pérdida de características locales
- Se compararon SDPA, FlashAttention-2 y SPECTRE sobre un backbone Llama-3.2-1B, midiendo throughput y latencia con secuencias de 512 a 128k tokens en una NVIDIA A100-80GB
- SPECTRE igualó o superó el rendimiento base en PG-19 e ImageNet-1k, y apunta al procesamiento de contexto largo en GPU comunes con menos de 6% de parámetros adicionales
Cómo reduce la FFT el costo cuadrático de self-attention
- Los Transformers de contexto largo son necesarios para tareas que manejan decenas de miles de tokens, como diálogo multi-turn, resumen de libros completos o visión de alta resolución
- El self-attention tradicional incrementa la latencia de inferencia y el uso de memoria a medida que crece el contexto, debido a su costo O(n²d)
- SPECTRE reemplaza la capa de self-attention por un mezclador de tokens en el dominio de la frecuencia como sustituto drop-in
- Proyecta los tokens sobre una base ortonormal de Fourier
- Aplica una compuerta diagonal adaptativa al contenido y una compuerta low-rank opcional
- Luego los devuelve al espacio de tokens mediante una transformada inversa
- La clave es reducir la complejidad por capa a O(n log n) sin modificar la arquitectura de red circundante
Composición del mezclador de tokens y soporte para generación
- La configuración que reemplaza cada attention head en SPECTRE consiste en fast real FFT, spectral gate e inverse FFT
- La spectral gating opera sobre n/2 + 1 coeficientes de frecuencia, y está diseñada para reducir cómputo y uso de memoria sin perder capacidad de representación
- El Prefix-FFT cache cumple un papel similar al KV-cache estándar y permite streaming decoding
- Reduce la debilidad de los mezcladores espectrales previos, que debían recalcular la FFT en cada time step durante la generación autorregresiva
- Es una estructura que permite generación eficiente dentro de un presupuesto de memoria fijo
- El Wavelet Refinement Module opcional compensa los detalles locales que podrían perderse en un enfoque puramente espectral, con poco overhead computacional
Cómo aplicarlo a Transformers existentes
- SPECTRE puede reemplazar directamente la capa de multi-head attention, sin requerir una reestructuración adicional de la arquitectura
- Los modelos preentrenados existentes pueden ajustarse con fine-tuning usando capas SPECTRE
- Los parámetros que se actualizan son los recién introducidos
- Los parámetros adicionales son menos de 6% del total de pesos
- A diferencia de enfoques que requieren optimizaciones especializadas o arquitecturas no estándar, mantiene intacta la estructura Transformer circundante
Experimentos basados en Llama-3.2-1B
- Se compararon tres kernels de attention sobre el mismo backbone Llama-3.2-1B
- standard softmax-dot-product attention(SDPA)
- FlashAttention-2
- SPECTRE mixer
- El entorno de medición fue una NVIDIA A100-80GB, con longitudes de secuencia L ∈ {512, 1k, 4k, 8k, 32k, 128k}
- Las métricas fueron throughput en tokens-per-second y latency con batch único
- Más throughput es mejor
- Menor latency es mejor
- SPECTRE mostró un tiempo de ejecución cercano a O(n log n) manteniendo la precisión del backbone
- Hasta 32k tokens, el tiempo de ejecución se mantuvo casi plano
- Según el abstract, en un contexto de 128k tokens fue hasta 7× más rápido que FlashAttention-2
- Según la lista de contribuciones del texto, mostró inferencia hasta 7× más rápida que FlashAttention-2 con 32k tokens
Resultados de benchmark y alcance práctico
- SPECTRE mostró resultados iguales o mejores que el baseline en modelado de lenguaje con PG-19 y clasificación en ImageNet-1k
- Mantiene la mezcla de contexto global mientras evita el costo cuadrático de self-attention en el procesamiento de contexto largo
- Los métodos de aceleración de attention basados en patrones sparse, aproximación por kernels o estructuras low-rank pueden tener límites como sacrificar exactitud, requerir optimizaciones no estándar o no soportar streaming generation
- SPECTRE usa un enfoque en el dominio de la frecuencia donde la FFT diagonaliza la convolución circular y convierte la mezcla global en un producto elemento por elemento
- Al limitar los parámetros adicionales a menos de 6%, apunta al procesamiento de contextos de cientos de miles de tokens en GPU convencionales sin hardware especializado
1 comentarios
Opiniones de Hacker News
Básicamente es una forma de aprovechar el teorema de la convolución: una convolución costosa en el espacio original se vuelve una simple multiplicación en el espacio recíproco, y viceversa.
Si hay una operación de convolución sobre los datos, basta con transformarlos al dominio conjugado y convertirla en una multiplicación.
Dicho de otro modo, significa trabajar en el dominio que sea natural para los datos.
https://en.wikipedia.org/wiki/Convolution_theorem
Para optimizar, se optimiza cada paso y se trabaja lo más posible en el espacio más eficiente.
¿No es distinto a que simplemente sea más fácil de calcular?
Además, hay que usar números complejos en el cálculo y también es menos estable numéricamente. Hasta donde sé, FFT no ofrece ventajas en convoluciones generales.
En self-attention o para el uso de este paper, n podría ser mucho mayor. No leí el paper. Aun así, el problema de los números complejos sigue ahí.
Google introdujo esta idea en 2022 con FNet: Mixing Tokens with Fourier Transforms.
Después descubrieron que, en la mayoría de los casos, el rendimiento de multiplicación de matrices de las TPU era más rápido que la FFT.
https://arxiv.org/abs/2105.03824
“En general, enfoques como FNet, Performer y los transformadores dispersos muestran que la mezcla de tokens fija o aproximada puede reducir la carga computacional, pero nuestra estrategia de filtrado espectral adaptativo combina de forma única la eficiencia de la FFT con filtros espectrales aprendibles y dependientes de la entrada. Esto ofrece una poderosa combinación de escalabilidad y adaptabilidad, importante para tareas complejas de modelado de secuencias”.
Después también hay una sección de comparación.
Pero, ¿los DSP tienen hardware dedicado para ayudar con la FFT? Lo pregunto porque de verdad me da curiosidad. Nunca los usé, pero vagamente siento que podría ayudar.
“La TPU es tan ineficiente en transformadas de Fourier que, para secuencias de menos de 4096 elementos, los investigadores no usaron el algoritmo FFT y optaron por una implementación de transformada de Fourier con escalado cuadrático usando una matriz DFT precalculada”.
“En una GPU Nvidia Quadro P6000, dentro de la arquitectura FNet, la transformada de Fourier representó hasta el 30% del tiempo de inferencia”.
En 2021, esta empresa afirmó que, si Google usaba sus chips ópticos en las TPU, podría reducir el tiempo de inferencia en un 40%. Si FFTNet asume más trabajo, podría reducirlo aún más.
https://scribe.rip/optalysys/attention-fourier-transforms-a-...
La transformada de Fourier se aplica a lo largo de la dimensión de “tokens”. Pero en muchas aplicaciones esa dimensión no tiene significado. Por eso los transformers se vuelven una buena opción para manejar datos invariantes a permutaciones.
Me gustaría ver más experimentos usando la transformada de Fourier sobre grupos finitos, que es menos conocida. Es invariante a permutaciones y, al mismo tiempo, comparte muchas propiedades con la transformada de Fourier estándar.
También me pregunto qué tan fácil sería integrarlo en motores de inferencia como vLLM o llama.cpp si esto se convierte en la próxima gran tendencia de los LLM.
https://en.wikipedia.org/wiki/Fourier_transform_on_finite_gr...
Tengo entendido que llama aplica una rotación al vector según su posición dentro de la entrada.
Las matemáticas se me van completamente por encima, y apenas entiendo las explicaciones alrededor de las fórmulas. ¿Alguien podría explicar en palabras simples cómo esto es equivalente al mecanismo de atención?
¿Qué son las frecuencias de las que se habla aquí y cómo se codifican las relaciones de posición entre tokens?
En análisis de señales o imágenes es donde resulta más intuitivo: https://homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm
El espacio de frecuencias es, en esencia, un espacio “complejo” representado con números complejos. Las frecuencias tienen la ventaja de ver el problema de forma global.
Este mecanismo no es equivalente al mecanismo de atención y hay compromisos claros. Aun así, es posible que capture muchas de las relaciones importantes que captura la atención.
Sobre modReLU no tengo una buena intuición por ahora, pero parece importante porque modifica las frecuencias y al mismo tiempo preserva la transformada inversa de Fourier.
Aquí, “frecuencia” probablemente sea algo bastante abstracto. La FFT se usa a menudo incluso de maneras que no tienen una interpretación clara como frecuencia. Muchas veces se usa por sus propiedades matemáticas convenientes, como el teorema de la convolución.
Si de verdad funciona bien, sería bastante sorprendente y muy elegante.
Es decir, cada vector de la salida depende de que el vector de entrada correspondiente sea transformado por alguna función de todos los demás vectores de entrada.
https://medium.com/optalysys/attention-fourier-transforms-a-...
Conceptualmente, se puede ver cómo esto se parece a una convolución algo simplificada: https://openreview.net/pdf?id=8l5GjEqGiRG
Las convoluciones suelen usarse cuando se quiere considerar el estado global de alguna manera.
Para meter enmascaramiento causal en este framework, parecería que habría que hacer n FFT distintas, y tampoco hay mención de embeddings posicionales.
Por eso, la implementación de autoatención usada como comparación parece ser NoPE no causal, y si es así quizá no sea tan impresionante, porque sería un caso de baseline deliberadamente débil.
Si los resultados hubieran estado cerca del estado del arte, supongo que el autor lo habría mencionado.
Parece una referencia relacionada: https://arxiv.org/abs/2111.13587
Adaptive Fourier Neural Operators: Efficient Token Mixers for Transformers
John Guibas, Morteza Mardani, Zongyi Li, Andrew Tao, Anima Anandkumar, Bryan Catanzaro
Me pregunto si hay alguna intuición sobre por qué aquí ayuda verlo en el dominio de la frecuencia.
Entiendo el componente de corriente continua, pero no esperaría que los datos de entrada fueran lo suficientemente periódicos como para que las otras frecuencias tengan significado.
Parece que no se menciona el trabajo previo del Hyena Operator, que ya hace unos años mostró mezcla de contexto completo en O(n log n).
https://arxiv.org/abs/2302.10866
https://arxiv.org/abs/2111.00396
La notación Big O me da cierta intuición, pero como la mayoría de las cosas relacionadas con ciencias de la computación o ingeniería eléctrica, esto se me pasa por encima de la cabeza.
Como alguien que de verdad es malo para las matemáticas, envidio a la gente que puede entender estas cosas, o al menos aprenderlas, y llegar a obtener un título y una licencia de ingeniería.
Lo que sé sobre la FFT es más o menos que transforma señales, se usa para algún tipo de procesamiento de señales y que escuché que antes era clave para la detección de explosiones nucleares.
La idea básica es esta: casi cualquier señal útil puede expresarse como una suma de ondas sinusoidales con distintas frecuencias y fases. Por ejemplo, una señal eléctrica o una onda sonora es una señal unidimensional cuyo eje x es el tiempo. A simple vista puede ser una línea compleja y ondulada, difícil de manejar.
Con la transformada de Fourier se pueden separar las frecuencias individuales de una señal basada en el tiempo. Luego puedes modificar ciertas frecuencias como quieras. Por ejemplo, si una señal tiene mucho ruido aleatorio en forma de picos, eso aparece como altas frecuencias. Para limpiarla, haces la transformada de Fourier, descartas los datos de las frecuencias por encima de cierto umbral y después aplicas la transformada inversa de Fourier a los datos restantes para volver a una versión más suave de la señal original. A esto se le llama filtro pasa bajas, y es casi equivalente a tomar un promedio móvil de la señal original.
Lo interesante es que esto se puede extender de forma bastante intuitiva a dimensiones más altas. Una señal bidimensional en la que tanto el eje x como el eje y son espacio es una imagen. La compresión JPEG se basa en este concepto. Para guardar una imagen en menos espacio, elimina señales de alta frecuencia, a cambio de perder detalles finos o, si se descarta demasiado, de generar artefactos en forma de anillos. Si agregas una tercera dimensión, el tiempo, obtienes video, y se puede seguir extendiendo.
Todo esto se entiende muy bien visualmente, así que se puede adquirir una buena intuición sin conocer a fondo toda la matemática. Una buena página con muchas visualizaciones y ejemplos interactivos: https://www.jezzamon.com/fourier/index.html
El video de 3Blue1Brown también lo explica bien: https://youtu.be/spUNpyF58BY?si=dz0z-s8NftW3Htun
La transformada de Fourier, de la cual la FFT es la versión discreta, descompone esa señal unidimensional en el dominio del tiempo en componentes de magnitud y fase frente a frecuencia.
La frecuencia es básicamente el tono. Una onda sinusoidal pura, o un tono puro, se parece al sonido que se escuchaba antes a altas horas de la noche cuando terminaban las transmisiones de TV; en ese caso, casi todo es cero y aparece un “pico” en la posición de la frecuencia de ese tono. Cuanto mayor sea la amplitud de la señal, mayor será también el tamaño del pico. Si el tono, es decir la frecuencia, sube o baja, la posición de ese pico se mueve a lo largo del eje horizontal.
La fase es básicamente el desplazamiento temporal de la señal. Un tono que se retrasó de alguna forma aparece con una fase distinta. Pero no es una medición absoluta, sino relativa. Como la unidad son radianes, es decir, ángulos, al dar una vuelta completa al círculo se “reinicia”, así que no se puede saber si la señal se retrasó 1 segundo o 2 segundos.
Por eso, de una sola señal —amplitud frente a tiempo— en realidad obtienes dos tipos de información: magnitud y fase frente a frecuencia.
Si entiendes los números imaginarios o las variables complejas, esas dos señales en realidad no son más que la magnitud y el argumento de la salida de la FFT, que es una función compleja.
En la era de la telemetría, siento que es una gran oportunidad perdida no aplicar FFT a la telemetría en la nube para encontrar anomalías periódicas y sistemas metaestables antes de que ocurra un incidente, no después.
Por desgracia, esto está al nivel de algo que puedo notar, pero no al nivel técnico en el que pueda implementarlo, y además ya tengo la agenda llena.
“El SLA tiene más probabilidades de incumplirse entre 23 y 25 minutos después de desplegar el servicio. Mmm, ¿por qué será...? Ah, no.”
Bromas aparte, donde esto de verdad podría generar dinero es en predecir ciclos de tráfico para subir y bajar instancias de servidor y así reducir costos.
Es el tipo de trabajo que, si lo haces en tu tiempo personal, la empresa jamás aprobaría, pero que compraría de inmediato si viniera empaquetado como un producto listo para usar.