Resumo Técnico: Uma Teoria de Segundo Momento para Árvores de Redução de Ponto Flutuante

Declaração do Problema

Os limites padrão de erro de propagação no pior caso para a soma de ponto flutuante, como $|\hat{s} - s| \le \gamma_{k-1} \sum |p_i|$, são independentes da topologia da árvore de redução. Embora esses limites forneçam garantias de segurança, eles falham em distinguir diferentes estruturas de árvore (ex: sequencial, pareada, em blocos) quando as entradas são aleatórias. Consequentemente, não conseguem prever qual topologia minimiza o erro típico (erro quadrático médio, MSE) para um determinado conjunto de dados. O artigo aborda a necessidade de um modelo que capture como a "geometria de redução" — a ordem específica das adições pareadas — interage com as estatísticas de entrada para determinar a acumulação de erro.

Metodologia

Os autores desenvolvem uma teoria de segundo momento que vai além da análise de pior caso, modelando a acumulação de erros de arredondamento como um processo estocástico dependente da estrutura da árvore.

1. Recorrência Condicional Exata

A análise começa com o arredondamento condicionalmente não enviesado (ex: arredondamento estocástico). Ao condicionar na informação disponível imediatamente antes de um nó ser arredondado (a $\sigma$-álgebra $\mathcal{F}^-_v$), os autores derivam uma recorrência exata para a variância do erro acumulado. Esta recorrência separa o erro herdado do erro de arredondamento local, mostrando que os termos cruzados desaparecem em expectativa. A variância local é mostrada como dependente do valor do operando pré-arredondamento $x_v$.

2. O Modelo de $\nu$ Constante

Para criar um modelo tratável para o arredondamento para o mais próximo determinístico (onde os erros não são estritamente condicionalmente não enviesados), os autores introduzem uma aproximação de "$\nu$ constante". Eles substituem a variância local dependente do operando por um modelo homogêneo $\psi_v(x) = \nu u^2 x^2$, onde $\nu$ é um coeficiente adimensional calibrado empiricamente. Isso simplifica a recorrência para uma forma onde o erro quadrático total esperado é proporcional à soma dos quadrados das somas parciais exatas: $\sum_v q_v^2$.

3. O Kernel do Ancestral Comum ($K_T$)

A principal contribuição teórica é a representação da soma dos quadrados das somas parciais como uma forma quadrática:
$$\sum_{v \in \text{int}(T)} q_v^2 = p^\top K_T p$$
Aqui, $K_T$ é um kernel de ancestral comum, uma matriz $k \times k$ onde a entrada $(K_T)_{ij}$ conta o número de nós internos que são ancestrais tanto para a folha $i$ quanto para a folha $j$. Esta matriz codifica a geometria de redução.

4. Compressão i.i.d. e Estatísticas de Árvore

Para entradas independentes e identicamente distribuídas (i.i.d.) com média $\mu$ e variância $\tau^2$, a expectativa da forma quadrática colapsa em dois estatísticos escalares da árvore:
$$\mathbb{E}[\text{MSE}] \propto \tau^2 \Lambda_1(T) + \mu^2 \Lambda_2(T)$$

• $\Lambda_1(T)$: A soma das profundidades das folhas (comprimento do caminho externo total). Isso governa o erro para entradas centradas ($\mu=0$).
• $\Lambda_2(T)$: A soma dos quadrados dos tamanhos das subárvores internas. Isso governa o erro para entradas não centradas ($\mu \neq 0$).

5. Extensão para GEMM

A teoria é estendida para a Multiplicação de Matrizes-Matriz Geral (GEMM). Mostra-se que o erro de Frobenius quadrático esperado é uma contração do kernel $K_T$ com uma matriz $G$ formada pelo produto de Hadamard das matrizes Gram dos operandos ($G = (A^\top A) \circ (BB^\top)$).

Principais Contribuições

Otimização Teórica

Os autores derivam topologias de árvore ótimas para diferentes regimes:

• Entradas Centradas: Árvores balanceadas minimizam $\Lambda_1$, enquanto árvores sequenciais o maximizam. O expoente ótimo para o erro RMS é $1/2$ para árvores pareadas.
• Entradas Não Centradas: A topologia ótima muda. Para hierarquias de estágios fixos, os autores derivam um "esquema de lacuna de duplicação" onde as razões de estágio diminuem pela metade sucessivamente ($r_\ell \propto 2^{-\ell}$) para minimizar $\Lambda_2$.
• Variâncias Heterogêneas: Para entradas i.i.d. centradas com variâncias desiguais, a estrutura de árvore ótima corresponde à codificação de Huffman, minimizando o comprimento do caminho externo ponderado pela variância.
• Bloqueio (Blocking): Para bloqueio sequencial de dois estágios, o tamanho de bloco ótimo escala como $b \propto \sqrt{k}$ para entradas centradas (resultando em um expoente de RMS de $3/4$), mas requer escalonamento diferente para entradas não centradas.

Validação Empírica

Os autores validam o modelo de $\nu$ constante através de múltiplas precisões (binary64, binary32, binary16 emulada por software e bfloat16) e tipos de entrada:

• Ordenação de Topologia: O modelo prevê corretamente a ordenação dos erros RMS entre árvores sequenciais, em blocos e pareadas.
• Calibração: Um $\nu \approx 0.19$ calibrado independentemente para o arredondamento para o mais próximo em binary64 permite que o modelo preveja o MSE absoluto com uma margem de 3% para GEMM e capture corretamente as leis de escala para várias famílias de árvores.
• Limites de Estagnação: O estudo identifica um regime de falha em baixa precisão (binary16/bfloat16) para somas positivas onde a "estagnação" (adicionar um número pequeno a um grande sem alteração) faz com que o viés domine, quebrando a aproximação de $\nu$ constante.

Resultados

• Leis de Escala: O artigo confirma que, para entradas centradas, a soma pareada escala como $O(\sqrt{\log k})$, a soma em blocos com $b \propto \sqrt{k}$ escala como $O(k^{3/4})$, e a soma sequencial escala como $O(k)$.
• Regime Não Centrado: Para entradas com médias não nulas (ex: denominadores de softmax, normas ao quadrado), o erro é dominado por $\Lambda_2$. O esquema de "lacuna de duplicação" ótimo produz um comportamento de escala diferente do esquema geométrico ideal para entradas centradas.
• Entradas Correlacionadas: Para entradas correlacionadas AR(1), a contração total do kernel $\langle K_T, M \rangle$ é necessária; a aproximação i.i.d. falha significativamente conforme a correlação aumenta.
• Validação de Biblioteca: O modelo prevê com sucesso o escalonamento de erro de uma árvore reconstruída do np.sum do NumPy, capturando a "curva" específica no crescimento do erro causada por sua hierarquia multiescala (acumulação sequencial dentro de pequenos blocos, halving recursivo para blocos maiores).

Significância e Alegações

O artigo afirma fornecer uma teoria de segundo momento que preenche a lacuna entre os limites de pior caso e o comportamento de erro prático. Sua significância reside em:

1. Consciência de Geometria: Ele quantifica explicitamente como a estrutura da árvore de redução (geometria) interage com as estatísticas de entrada, um fator ignorado pelos limites padrão.
2. Poder Preditivo: Oferece um fluxo de trabalho (Tabela 1) para prever o erro RMS de uma implementação específica dado seu histórico de árvore e distribuição de entrada, validado através de uma ampla gama de precisões e arquiteturas.
3. Orientação de Otimização: Fornece critérios concretos para escolher esquemas de redução (ex: tamanhos de bloco, razões de estágio) baseados em se os dados estão centrados ou não, e se as variâncias são homogêneas.
4. Limitações: Os autores notam modestamente que o modelo depende da suposição $h(T)u^2 \ll 1$ e pode falhar em regimes de baixa precisão onde a estagnação e o viés sistemático dominam a acumulação de erro, conforme observado em seus experimentos com binary16/bfloat16. O $\nu$ constante é uma calibração empírica, não uma constante aritmética universal.

O trabalho estabelece que, para entradas aleatórias, o erro "típico" é governado pela estrutura de ancestralidade compartilhada da árvore, permitando o design de árvores de redução numericamente estáveis e adaptadas a características específicas de dados.