🤖 machine learning

LAPLEX: The FFT of Learnable Laplace Kernels

LAPLEX introduz uma classe de operadores exatos e treináveis baseados em kernels de Laplace que alcançam escalabilidade semelhante à FFT, permitindo interações globais adaptativas aos dados e modelagem de covariância de alta dimensão sem os custos de armazenamento de matrizes densas, separando efetivamente a expressividade dos requisitos de memória.

Autores originais: Łukasz Struski, Hanna Blazhko, Piotr Kubaty, Jacek Tabor

Publicado 2026-05-26

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Łukasz Struski, Hanna Blazhko, Piotr Kubaty, Jacek Tabor

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está tentando organizar uma biblioteca massiva com bilhões de livros. No mundo da inteligência artificial moderna, "livros" são apenas números (pontos de dados), e "organizar" significa realizar matemática complexa para encontrar padrões.

Geralmente, quando a IA tenta fazer isso em grande escala, ela enfrenta uma escolha frustrante:

O Bibliotecário Rígido (Geometria Fixa): Como um catálogo de biblioteca padrão, é rápido e exato, mas as prateleiras são fixas. Você não pode mover um livro para um local melhor com base no que está procurando. (Isso é como a FFT ou Transformada de Fourier).
O Bibliotecário Flexível, mas Pesado (Parâmetros Densos): Este bibliotecário pode reorganizar as prateleiras como quiser para encaixar os livros perfeitamente, mas, para fazer isso, precisa de um armazém massivo para armazenar as instruções para cada livro individual. Se a biblioteca ficar grande demais, o armazém fica sem espaço e o sistema falha. (Isso é uma Matriz Densa padrão).
O Bibliotecário Aproximado (Baixa Classificação/Rascunho): Este bibliotecário tenta economizar espaço lembrando apenas do "vibe geral" dos livros ou usando um jogo de adivinhação aleatória. É rápido e cabe no armazém, mas perde os detalhes exatos e não consegue aprender a melhor organização.

LAPLEX é um novo tipo de bibliotecário que quebra esse compromisso. Ele afirma ser a solução "Cachinhos Dourados": é exato, é treinável (pode aprender a melhor organização) e é leve (não precisa de um armazém massivo).

Veja como funciona, usando analogias simples:

1. O Segredo: Aprender as "Coordenadas" em vez do "Mapa"

Imagine que você tem um mapa gigante de uma cidade com milhões de ruas.

O Jeito Antigo: Para saber a distância entre cada par de ruas, você precisaria escrever um número para cada par individual. Para uma cidade com 1 milhão de ruas, isso são trilhões de números. Você não consegue armazenar isso.
O Jeito LAPLEX: Em vez de escrever cada distância, o LAPLEX apenas escreve uma lista de "pontos de ancoragem" (como marcos principais). Em seguida, usa uma regra matemática inteligente (o Núcleo de Laplace) para calcular a distância entre qualquer dois pontos com base em quão próximos eles estão desses marcos.

Como a regra é tão simples, o LAPLEX não precisa armazenar os trilhões de números. Ele só precisa armazenar a lista de marcos. Mas aqui está a mágica: ele pode aprender onde colocar esses marcos. Se os dados sugerirem que a "Rua A" e a "Rua B" estão frequentemente relacionadas, o LAPLEX aprende a mover seus marcos para que A e B acabem próximos um do outro em sua lógica interna.

2. O Truque da "Varredura": Fazer Matemática sem o Trabalho Pesado

O artigo afirma que, embora o LAPLEX atue como um mapa denso e gigante, ele pode fazer a matemática incrivelmente rápido.

Pense nisso como uma esteira rolante em uma fábrica.

O Jeito Denso: Para calcular o resultado de um item, você tem que parar, olhar para cada outro item no armazém e fazer um cálculo. Isso fica cada vez mais lento à medida que o armazém cresce.
O Jeito LAPLEX: Ele classifica os itens na esteira primeiro. Então, usa uma técnica de "varredura". Imagine um trabalhador caminhando pela linha que só precisa lembrar do total acumulado do que viu até agora. Como a matemática do núcleo de Laplace é exponencial (as coisas ficam muito menores muito rápido à medida que você se afasta), o trabalhador pode calcular o resultado final para toda a linha apenas olhando para o "prefixo" (o que veio antes) e o "sufixo" (o que vem depois).

Isso permite que o LAPLEX lide com dimensões de até 1 bilhão (10⁹) em computadores modernos, um tamanho onde o método "Denso" imediatamente ficaria sem memória.

3. O Que Ele Realmente Faz (Os Experimentos)

O artigo testa esse "bibliotecário" em três cenários específicos para provar que funciona:

O Teste de "Imagem Achata": Eles pegaram fotos de alta resolução (milhões de pixels), achatararam-nas em uma única linha longa de números (ignorando a grade 2D) e tentaram modelar os dados.
- Resultado: Um modelo padrão de "baixa classificação" (o bibliotecário aproximado) falhou em ver que pixels próximos uns dos outros na foto original deveriam estar relacionados; ele apenas viu ruído. LAPLEX, no entanto, aprendeu a colocar seus "marcos" de uma maneira que preservava as formas das imagens (como uma praia ou uma palmeira), mesmo nunca tendo visto a imagem como uma grade. Ele aprendeu a geometria dos dados sem que lhe dissessem o que é uma grade.
O Teste de "Cabeça de Classificação": Eles tentaram substituir a camada final de uma rede neural (a parte que decide "isso é um gato ou um cachorro?") pelo LAPLEX.
- Resultado: Usando apenas uma fração minúscula dos parâmetros (como 1-5% do tamanho usual), o LAPLEX performou quase tão bem quanto a rede completa e massiva. Ele aprendeu a rotear informações muito melhor do que os atalhos padrão de "baixa classificação".
O Teste de "Velocidade": Eles compararam a velocidade de execução em um supercomputador (GPU).
- Resultado: O LAPLEX é aproximadamente 65 vezes mais rápido que o método padrão para passagens diretas e 430 vezes mais rápido para treinamento (passagem direta + reversa) em grandes conjuntos de dados. Ele também usa 100 vezes menos memória.

4. Por Que Isso Importa (Em Termos Simples)

O artigo argumenta que, por muito tempo, achamos que tínhamos que escolher entre velocidade/tamanho e precisão/flexibilidade.

Se você queria velocidade, tinha que usar regras fixas (como FFT) ou palpites aleatórios.
Se você queria aprender as melhores regras, tinha que usar tanta memória que não conseguia executá-lo em grandes dados.

LAPLEX diz: "Você não precisa escolher". Ao tratar as coordenadas dos dados como variáveis treináveis em vez de slots fixos, ele cria um sistema que é:

Exato: Não chuta; calcula a matemática verdadeira.
Treinável: Adapta-se aos dados específicos que vê.
Eficiente: Cabe em hardware que, de outra forma, falharia.

Analogia de Resumo

Imagine que você está tentando organizar uma festa massiva onde milhões de convidados precisam encontrar seus lugares.

Matriz Densa: Você imprime um mapa de assentos gigante com o nome de cada convidado ao lado do nome de cada outro convidado. É perfeito, mas a pilha de papel é pesada demais para carregar.
Baixa Classificação/Rascunho: Você apenas diz aos convidados para sentar na "Zona A" ou "Zona B" aleatoriamente. É leve, mas o assento é bagunçado e ineficiente.
LAPLEX: Você dá aos convidados alguns "âncoras magnéticas" (como mesas VIP). Você ensina os convidados a sentar com base em quão próximos eles estão dessas âncoras. As âncoras se movem durante a festa para encontrar os melhores lugares. Você não precisa de um mapa gigante; só precisa da lista de âncoras. Os convidados encontram seus lugares instantaneamente, o arranjo é perfeito e você pode carregar todo o plano no seu bolso.

O artigo conclui que essa abordagem permite que a IA lide com interações "densas" (onde tudo conversa com tudo) em escalas que eram anteriormente impossíveis, sem sacrificar a capacidade de aprender com os dados.

Resumo Técnico: LAPLEX – A FFT de Núcleos de Laplace Aprendíveis

1. Declaração do Problema

Os sistemas modernos de aprendizado de máquina operam cada vez mais em regimes onde as dimensões ambientes atingem milhões ou bilhões. Nessas configurações de alta dimensão, o gargalo é frequentemente o custo em tempo de relógio e a pegada de memória de operações lineares, como a aplicação de matrizes densas, o cálculo de operadores de Gram e a mistura de características.

As abordagens existentes para escalar a álgebra linear geralmente sacrificam uma das três propriedades desejáveis: exatidão, aprendibilidade ou escalabilidade quase linear.

Métodos de baixo posto (e.g., LoRA) mantêm interações densas dependentes de base, mas sofrem com uma pegada de memória de $O(nk)$ porque devem armazenar coeficientes para a base de entrada, mesmo que o posto de saída seja comprimido.
Esboços aleatórios e características aleatórias (e.g., CountSketch, Características de Fourier Aleatórias) oferecem escalabilidade, mas atuam sobre indexação fixa ou aproximam o núcleo, trocando exatidão por eficiência. Eles não podem adaptar como as coordenadas são combinadas.
Métodos esparsos podem quebrar a regularidade de hardware e são difíceis de treinar de ponta a ponta.
Transformadas rápidas clássicas (e.g., FFT) são exatas e baratas ( $O(n \log n)$ ), mas estão fixadas a uma geometria de grade específica e não podem aprender o sistema de coordenadas.

A limitação central identificada é a dependência de base: operadores padrão parametrizam os valores da matriz diretamente, exigindo armazenamento proporcional à dimensão de entrada. O artigo defende uma mudança para operadores em nível de índice que podem aprender a própria geometria de entrada sem armazenar uma matriz densa.

2. Metodologia: LAPLEX

Os autores introduzem o LAPLEX, uma classe de operadores exatos e treináveis baseados no núcleo de Laplace. Uma camada LAPLEX é implicitamente definida por âncoras de coordenadas aprendíveis, em vez de pesos de matriz explícitos.

2.1 O Operador

O primitivo central é a matriz de núcleo de Laplace definida por dois conjuntos de âncoras aprendíveis, $a \in \mathbb{R}^n$ e $b \in \mathbb{R}^k$ :
$\text{LAPLEX}(a, b)_{ij} = \exp(-|a_i - b_j|)$
Em um regime limite natural (temperatura $t \to 0$ ), este operador codifica todas as permutações do conjunto de coordenadas. Ao adicionar parâmetros de fase $\phi, \psi$ , o operador pode ser estendido para:
$\text{LAPLEX}(a, \phi; b, \psi)_{jk} = \exp(-|a_j - b_k|) \cdot \cos(\phi_j - \psi_k)$
Isso permite que o operador funcione como uma matriz densa e treinável, utilizando apenas $O(n)$ parâmetros (as âncoras).

2.2 Álgebra de Varredura Exata

A contribuição algorítmica chave é um algoritmo exato, totalmente paralelo e $O(n \log n)$ para produtos matriz-vetor e de Gram que nunca materializa a matriz densa.

Caso Simétrico ( $a=b$ ): Após ordenar as âncoras, a matriz do núcleo decompõe-se em partes triangular inferior e superior. Cada parte pode ser computada via recorrência de varredura de prefixo e varredura de sufixo. Por exemplo, o produto triangular inferior $y_i = \sum_{j \le i} \exp(a_j - a_i)x_j$ satisfaz uma recorrência $y_{i+1} = x_{i+1} + \exp(a_i - a_{i+1})y_i$ , que é avaliada em $O(n)$ de trabalho e $O(\log n)$ de profundidade paralela.
Caso Geral ( $a \neq b$ ): O algoritmo agrega contribuições das âncoras $b$ em intervalos definidos pelas âncoras $a$ ordenadas. Contribuições locais são resumidas em vetores $u$ e $v$ , que são então propagados globalmente usando o primitivo de varredura simétrica.
Operadores de Gram: A mesma estrutura de ordenação permite o cálculo exato de matrizes de Gram ponderadas $M = A \text{diag}(D) A^\top$ em tempo $O(n^2 + k \log n)$ , evitando o custo ingênuo de $O(n^2 k)$ . Isso é crucial para otimização de segunda ordem e métodos de núcleo.

2.3 Expressividade e Limites

O artigo estabelece que o LAPLEX é uma família contínua que interpola entre diferentes classes de operadores:

Limite de Temperatura Zero: À medida que o parâmetro de temperatura se aproxima de zero, o núcleo suave converge para uma matriz de roteamento de igualdade discreta, recuperando o CountSketch e permutações arbitrárias.
Universalidade: Com escalas diagonais e replicação esparsa, a família é universal para matrizes densas retangulares arbitrárias.
Relação com FFT: Se as âncoras forem congeladas em uma grade uniforme, o LAPLEX torna-se uma matriz de Toeplitz, e o algoritmo reduz-se a Toeplitz-FFT. Se o núcleo for substituído por uma expansão espectral finita, torna-se Características de Fourier Aleatórias (RFF). O LAPLEX mantém a exatidão e diferenciabilidade em relação às âncoras, ao contrário do RFF, que sofre de variância de gradiente ilimitada devido à densidade espectral de Cauchy de cauda pesada do núcleo de Laplace.

3. Contribuições Principais

Identificação da Dependência de Base: O artigo motiva operadores em nível de índice e conscientes de permutação como uma alternativa principial aos métodos de baixo posto, que não podem escapar de pegadas de memória de $O(nk)$ porque não comprimem a base de entrada.
Geometria Aprendível: Demonstra que a matriz de núcleo de Laplace codifica todas as permutações de coordenadas em um regime limite natural, utilizando apenas $O(n)$ parâmetros.
Algoritmos Exatos e Escaláveis: Os autores fornecem um algoritmo exato, totalmente paralelo e $O(n \log n)$ para produtos matriz-vetor e de Gram usando $O(n)$ de memória. Isso permite dimensões de até $10^9$ em GPUs modernas sem materializar a matriz.
Validação Empírica: O artigo mostra que o LAPLEX corresponde à escalabilidade da classe FFT, funcionando eficientemente como uma camada estruturada de substituição. Supera as bases densas em memória e velocidade, e supera as bases de baixo posto e características aleatórias em precisão e estabilidade de gradiente.

4. Resultados Experimentais

4.1 Escalabilidade e Desempenho

Escalabilidade em GPU: Em NVIDIA H100 e RTX 2080, o LAPLEX escala suavemente até $n = 2^{20}$ (aproximadamente 1 milhão de elementos), enquanto as bases densas esgotam a memória (OOM) em $n = 2^{14}$ .
Velocidade: No maior tamanho onde ambos os métodos executam ( $n=2^{14}$ ), o LAPLEX é $\sim 65\times$ mais rápido na passagem forward e $\sim 430\times$ mais rápido em forward+backward comparado ao matmul denso.
Memória: O LAPLEX utiliza $\sim 100\times$ menos memória de pico que a base densa.
Precisão Numérica: Apesar de executar em float32, o LAPLEX exibe erro relativo menor contra uma referência float64 do que tanto o matmul float32 denso quanto o Toeplitz-FFT. Isso é atribuído à capacidade do algoritmo de varredura de manter fatores de escala exponenciais separados das mantissas, evitando a acumulação de erro $O(n \epsilon)$ da soma densa.

4.2 Modelagem de Densidade em Alta Dimensão

Os autores treinaram um modelo de densidade Gaussiana em imagens DIV2K achatadas (dimensão $3 \cdot 10^6$ ) usando um operador de Gram exato.

Configuração: Comparou-se um fator LAPLEX (posto 1000, $\sim 14$ M parâmetros) contra uma base densa de baixo posto (posto 4, $\sim 15$ M parâmetros).
Resultado: A base densa colapsou para ruído uniforme devido a posto insuficiente. O modelo LAPLEX aprendeu estruturas espaciais coerentes de cor (regiões contíguas, silhuetas), apesar de operar sobre vetores achatados sem viés convolucional. A verossimilhança logarítmica de teste foi $4.5\times$ maior que a da base densa.

4.3 Projeções Estruturadas e Classificação

Projeções ImageNet10: Em uma configuração de projeção congelada (imagens achatadas de $150.528$ dimensões para $m \in \{25, \dots, 1000\}$ ), o LAPLEX foi mais estável que CountSketch e Projeções Aleatórias, tornando-se o melhor desempenho em $m$ maiores.
Cabeças Treináveis: Quando usado como cabeça de classificação para Swin-T e MaxViT-T, o LAPLEX igualou ou superou a precisão de projeções densas não restritas na mesma dimensão de saída, usando $\Theta(m+d)$ parâmetros em vez de $\Theta(md)$ . Em postos baixos, o LAPLEX superou significativamente a fatoração de baixo posto (estilo LoRA).

5. Significado e Alegações

O artigo alega que o LAPLEX separa a expressividade do custo de armazenamento. Ele se comporta como uma matriz treinável densa, mas é representada e aplicada através de um pequeno conjunto estruturado de parâmetros (âncoras).

Separação de Expressividade e Armazenamento: A geometria densa pode ser aprendida sem armazenar uma matriz densa. Isso permite interações globais adaptativas aos dados em regimes onde camadas densas ordinárias são inviáveis.
Exatidão vs. Aproximação: Ao contrário de Características de Fourier Aleatórias ou métodos de Nyström, o LAPLEX fornece aplicação de núcleo exata e cálculo de Gram. Evita as trocas valor/gradiente de características aleatórias, particularmente a variância ilimitada nos gradientes de âncora causada pela densidade espectral de Cauchy.
Transformadas Rápidas Aprendíveis: O trabalho demonstra que transformadas rápidas não precisam viver em sistemas de coordenadas fixos. Ao parametrizar um operador denso através de âncoras de Laplace aprendíveis, a própria geometria torna-se um parâmetro diferenciável.

6. Limitações

Os autores reconhecem as seguintes limitações:

Dimensionalidade: A construção atual utiliza âncoras de Laplace unidimensionais e algoritmos baseados em ordenação. Estender essa exatidão para geometrias de âncora de dimensões superiores e núcleos mais ricos é uma direção matemática aberta.
Maturidade de Sistemas: A implementação demonstra o regime algorítmico, mas blocos de atenção em grande escala, otimizadores e modelos generativos exigirão kernels especializados e design cuidadoso de arquitetura.
Escopo: O método é atualmente limitado ao núcleo de Laplace e sua decomposição específica baseada em varredura.

Em resumo, o LAPLEX oferece uma alternativa principial aos métodos de baixo posto e aleatorizados, permitindo álgebra linear exata, aprendível e escalável em regimes de alta dimensão, ao mudar da parametrização de matrizes para a parametrização de interações de índice.