- Em Transformers de contexto longo, quando o custo de self-attention vira um gargalo, o SPECTRE usa um token mixer baseado em FFT para reduzir a complexidade por camada de O(L²) para O(L log L)
- Cada attention head é substituído por uma combinação de real FFT rápida, spectral gate adaptativo ao conteúdo e FFT inversa, mantendo a estrutura existente do Transformer
- Na geração autorregressiva, um cache Prefix-FFT reduz o peso de recalcular a FFT a cada etapa, e um módulo opcional de wavelets pode compensar a perda de características locais
- Foram comparados SDPA, FlashAttention-2 e SPECTRE sobre o backbone Llama-3.2-1B, medindo throughput e latência de 512 a 128k tokens em uma NVIDIA A100-80GB
- O SPECTRE igualou ou superou o desempenho de referência no PG-19 e no ImageNet-1k, mirando processamento de contexto longo em GPUs comuns com menos de 6% de parâmetros adicionais
Como reduzir com FFT o custo quadrático do self-attention
- Transformers de contexto longo são necessários em tarefas que lidam com dezenas de milhares de tokens, como diálogos multi-turn, resumos do tamanho de livros e visão de alta resolução
- O self-attention tradicional tem custo O(n²d), o que aumenta a latência de inferência e o uso de memória conforme o contexto cresce
- O SPECTRE é uma substituição drop-in que troca camadas de self-attention por um token mixer no domínio da frequência
- Projeta os tokens em uma base de Fourier ortonormal
- Aplica um gate diagonal adaptativo ao conteúdo e um gate low-rank opcional
- Retorna ao espaço de tokens por meio da transformada inversa
- O ponto central é reduzir a complexidade por camada para O(n log n) sem alterar a arquitetura de rede ao redor
Composição do token mixer e suporte à geração
- A composição que substitui um attention head no SPECTRE é fast real FFT, spectral gate e FFT inversa
- O spectral gating opera sobre n/2 + 1 coeficientes de frequência, sendo projetado para manter expressividade enquanto reduz computação e uso de memória
- O cache Prefix-FFT cumpre um papel semelhante ao KV-cache padrão e dá suporte à decodificação em streaming
- Reduz a fraqueza dos mixers espectrais tradicionais, que precisam recalcular a FFT a cada time step na geração autorregressiva
- É uma estrutura que permite geração eficiente dentro de um orçamento fixo de memória
- O Wavelet Refinement Module opcional compensa detalhes locais que podem se perder em uma abordagem puramente espectral, com pequena sobrecarga computacional
Como aplicar em Transformers existentes
- O SPECTRE pode substituir diretamente camadas de multi-head attention, sem exigir uma reformulação separada da arquitetura
- Modelos pré-treinados existentes podem passar por fine-tuning com camadas SPECTRE
- Os alvos de atualização são os novos parâmetros introduzidos
- Os parâmetros adicionais são menos de 6% do total de pesos
- Diferentemente de abordagens que exigem otimização especializada ou arquiteturas não padronizadas, ele mantém a estrutura Transformer ao redor
Experimentos baseados no Llama-3.2-1B
- A comparação aplica três attention kernels ao mesmo backbone Llama-3.2-1B
- standard softmax-dot-product attention(SDPA)
- FlashAttention-2
- SPECTRE mixer
- O ambiente de medição é uma NVIDIA A100-80GB, com comprimentos de sequência L ∈ {512, 1k, 4k, 8k, 32k, 128k}
- As métricas são throughput em tokens por segundo e latência em single-batch
- Quanto maior o throughput, melhor
- Quanto menor a latency, melhor
- O SPECTRE mantém a precisão do backbone enquanto mostra tempo de execução próximo de O(n log n)
- O tempo de execução se mantém quase plano até 32k tokens
- Segundo o abstract, é até 7× mais rápido que o FlashAttention-2 em contexto de 128k tokens
- Segundo a lista de contribuições do corpo do texto, mostra inferência até 7× mais rápida que o FlashAttention-2 em 32k tokens
Resultados de benchmark e faixa prática
- O SPECTRE apresentou resultados iguais ou superiores ao baseline em modelagem de linguagem no PG-19 e classificação no ImageNet-1k
- Em processamento de contexto longo, ele evita o custo quadrático do self-attention sem perder a mistura de contexto global
- Métodos de aceleração de attention baseados em sparse pattern, kernel approximation e low-rank structure podem ter limitações como sacrificar exactness, exigir otimizações não padronizadas ou não dar suporte a streaming generation
- O SPECTRE usa uma abordagem no domínio da frequência em que a FFT diagonaliza a circular convolution, transformando global mixing em element-wise product
- Ao limitar os parâmetros adicionais a menos de 6%, mira o processamento de contextos de centenas de milhares de tokens em commodity GPUs, sem specialized hardware
1 comentários
Opiniões no Hacker News
Basicamente, é uma forma de aproveitar o teorema da convolução: uma convolução cara no espaço original vira uma simples multiplicação no espaço recíproco, e o inverso também vale
Se há uma operação de convolução nos dados, basta transformá-los para o domínio conjugado e convertê-la em multiplicação
Em outras palavras, significa trabalhar no domínio natural dos dados
https://en.wikipedia.org/wiki/Convolution_theorem
Para otimizar, otimize cada etapa e faça o máximo possível do trabalho no espaço mais eficiente
Não é algo diferente de simplesmente ser mais fácil de calcular?
Além disso, é preciso usar números complexos no cálculo, e isso também é menos estável numericamente. Até onde sei, FFT não traz ganho em convoluções comuns
Para self-attention ou para o uso deste artigo, o n pode ser bem maior. Não li o artigo. Ainda assim, o problema dos números complexos permanece
O Google introduziu essa ideia em 2022 com FNet: Mixing Tokens with Fourier Transforms
Depois descobriram que, na maioria das situações, o desempenho de multiplicação de matrizes das TPUs é mais rápido do que FFT
https://arxiv.org/abs/2105.03824
“No geral, abordagens como FNet, Performer e transformers esparsos mostram que é possível reduzir a carga computacional com mistura de tokens fixa ou aproximada, mas nossa estratégia de filtragem espectral adaptativa combina de forma única a eficiência da FFT com filtros espectrais aprendíveis e dependentes da entrada. Isso oferece uma combinação poderosa de escalabilidade e adaptabilidade, importante para tarefas complexas de modelagem de sequências.”
Depois disso também há uma seção de comparação
Mas DSPs têm hardware dedicado para ajudar com FFT? Estou perguntando por curiosidade mesmo. Nunca usei, mas tenho a vaga impressão de que ajudaria
“As TPUs são tão ineficientes em transformadas de Fourier que os pesquisadores optaram por não usar o algoritmo FFT para sequências com menos de 4096 elementos, escolhendo uma implementação de transformada de Fourier com escalonamento quadrático usando uma matriz DFT pré-computada.”
“Em uma GPU Nvidia Quadro P6000, na arquitetura FNet, a transformada de Fourier respondeu por até 30% do tempo de inferência.”
Essa empresa afirmou em 2021 que, se o Google usasse seus chips ópticos nas TPUs, poderia reduzir o tempo de inferência em 40%. Se a FFTNet assumir mais trabalho, talvez reduza ainda mais
https://scribe.rip/optalysys/attention-fourier-transforms-a-...
A transformada de Fourier é aplicada ao longo da dimensão dos “tokens”. Mas, em muitas aplicações, essa dimensão não tem significado. É por isso que transformers acabam sendo uma boa escolha para processar dados invariantes a permutação
Eu gostaria de ver mais experimentos usando a menos conhecida transformada de Fourier sobre grupos finitos. Ela é invariante a permutação e, ao mesmo tempo, compartilha muitas propriedades com a transformada de Fourier padrão
Também fico curioso para saber, se isso se tornar a próxima grande tendência em LLMs, quão facilmente motores de inferência como vLLM ou llama.cpp conseguiriam integrar a técnica
https://en.wikipedia.org/wiki/Fourier_transform_on_finite_gr...
Pelo que sei, o llama aplica uma rotação aos vetores de acordo com a posição na entrada
A matemática passa completamente por cima da minha cabeça, e mal consigo entender as explicações em volta das fórmulas. Alguém consegue explicar em termos simples como isso é equivalente ao mecanismo de atenção?
O que são as frequências mencionadas aqui, e como as relações posicionais entre tokens são codificadas?
Em análise de sinais ou imagens, isso é mais intuitivo: https://homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm
O espaço de frequências é, essencialmente, um espaço “complexo” representado por números complexos. As frequências têm a vantagem de enxergar o problema de forma global.
Esse mecanismo não é equivalente ao mecanismo de atenção, e há claramente um trade-off. Ainda assim, é possível que ele capture muitas das relações importantes que a atenção captura.
Sobre modReLU, não tenho uma boa intuição de imediato, mas parece importante porque modifica as frequências e ao mesmo tempo preserva a transformada inversa de Fourier.
Aqui, “frequência” provavelmente é algo bastante abstrato. FFT é frequentemente usada também de maneiras que não têm uma interpretação clara de frequência. Muitas vezes ela é usada por causa de propriedades matemáticas convenientes, como o teorema da convolução.
Se isso realmente funcionar bem, é bastante surpreendente e muito elegante.
Ou seja, cada vetor de saída depende daquele vetor de entrada transformado por alguma função de todos os outros vetores de entrada.
https://medium.com/optalysys/attention-fourier-transforms-a-...
Conceitualmente, dá para ver como isso se parece com uma convolução um pouco simplificada: https://openreview.net/pdf?id=8l5GjEqGiRG
Convoluções são usadas com frequência quando se quer levar em conta o estado global de alguma forma.
Para colocar mascaramento causal nesse framework, parece que seria necessário fazer n FFTs diferentes, e também não há menção a embeddings posicionais.
Então a implementação de self-attention usada como comparação parece ser NoPE não causal; se for isso, pode ser um caso em que a linha de base foi deliberadamente enfraquecida, o que não é tão impressionante.
Se os resultados fossem próximos do estado da arte, acho que os autores teriam mencionado.
Parece ser uma referência 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
Fico curioso se há alguma intuição sobre por que enxergar isso no domínio da frequência ajuda.
Entendo o componente DC, mas não espero que os dados de entrada sejam periódicos o suficiente para que outras frequências tenham significado.
Parece que não foi mencionado o trabalho anterior do Hyena Operator, que já havia mostrado mistura de contexto completo em O(n log n) alguns anos atrás.
https://arxiv.org/abs/2302.10866
https://arxiv.org/abs/2111.00396
A notação Big O até dá uma noção, mas, como a maior parte das coisas relacionadas à ciência da computação ou à engenharia elétrica, isso também passa por cima da minha cabeça
Como alguém que é realmente ruim em matemática, invejo quem consegue entender esse tipo de coisa, ou pelo menos aprender o suficiente para conseguir um diploma e até uma licença de engenharia
O que sei sobre FFT é mais ou menos que ela transforma sinais, é usada em certos tipos de processamento de sinais e que ouvi dizer que, no passado, era essencial para a detecção de explosões nucleares
A ideia básica é esta: quase todo sinal útil pode ser representado como a soma de ondas senoidais com frequências e fases diferentes. Por exemplo, sinais elétricos ou ondas sonoras são sinais unidimensionais em que o eixo x é o tempo. Visualmente, podem parecer uma linha complexa e sinuosa difícil de lidar
Com a transformada de Fourier, é possível separar as frequências individuais de um sinal baseado no tempo. Depois, você pode modificar certas frequências da forma que quiser. Por exemplo, se houver muito ruído aleatório em forma de picos no sinal, isso aparece como altas frequências. Para limpá-lo, basta aplicar a transformada de Fourier, descartar os dados de frequências acima de um certo limiar e então aplicar a transformada inversa de Fourier aos dados restantes para voltar a uma versão mais suave do sinal original. Isso se chama filtro passa-baixa e é quase como tirar uma média móvel do sinal original
A parte interessante é que isso pode ser estendido de forma bastante intuitiva para dimensões maiores. Um sinal bidimensional, em que tanto o eixo x quanto o eixo y são espaço, é uma imagem. A compressão JPEG se baseia nesse conceito. Para armazenar a imagem em um tamanho menor, removem-se sinais de alta frequência; em troca, perdem-se detalhes finos ou, se você descartar demais, surgem artefatos em forma de anel. Se acrescentar uma terceira dimensão, o tempo, você tem vídeo, e dá para continuar expandindo
Tudo isso é muito bom de entender visualmente, então dá para ganhar uma boa intuição sem conhecer toda a matemática a fundo. Uma boa página com muitas visualizações e exemplos interativos: https://www.jezzamon.com/fourier/index.html
O vídeo do 3Blue1Brown também explica bem: https://youtu.be/spUNpyF58BY?si=dz0z-s8NftW3Htun
A transformada de Fourier, cuja versão discreta é a FFT, decompõe esse sinal unidimensional no domínio do tempo em componentes de magnitude e fase em função da frequência
A frequência é basicamente a altura do som. Uma onda senoidal pura ou um tom puro é parecido com aquele som que se ouvia antigamente quando a TV encerrava a transmissão tarde da noite; nesse caso, quase tudo é zero e aparece um único “pico” na posição da frequência daquele tom. Quanto maior a amplitude do sinal, maior também o tamanho do pico. Se a altura, ou seja, a frequência, sobe ou desce, a posição desse pico se move ao longo do eixo horizontal
A fase é basicamente o deslocamento temporal do sinal. Um tom atrasado de alguma forma aparece com uma fase diferente. Mas isso é uma medida relativa, não absoluta. Como a unidade é radiano, isto é, um ângulo, ela “reinicia” depois de dar uma volta completa no círculo, então não dá para saber coisas como se o sinal atrasou 1 segundo ou 2 segundos
Assim, de um único sinal — amplitude em função do tempo — você na verdade obtém duas informações: magnitude e fase em função da frequência
Se você entende números imaginários ou variáveis complexas, esses dois sinais são, na verdade, apenas o módulo e o argumento da saída da FFT, que é uma função complexa
Na era da telemetria, parece uma grande oportunidade perdida não aplicar FFT à telemetria de nuvem para encontrar anomalias periódicas e sistemas metaestáveis antes de um incidente acontecer, e não depois
Infelizmente, isso está dentro do nível em que eu consigo perceber a ideia, mas não no nível técnico em que consigo implementá-la, e minha agenda já está lotada
“O SLA é mais propenso a ser violado entre 23 e 25 minutos depois da implantação do serviço. Hmm, por quê… ah, não.”
Brincadeiras à parte, a área em que isso poderia realmente dar dinheiro é prever ciclos de tráfego para aumentar e reduzir instâncias de servidor e cortar custos
É o tipo de trabalho que, se feito no tempo pessoal, a empresa jamais aprovaria, mas, se for empacotado como produto pronto, é exatamente o tipo de coisa que ela compraria na hora