Resumen Técnico: Una Teoría de Segundo Momento para Árboles de Reducción de Punto Flotante

Planteamiento del Problema

Los límites de error hacia adelante (forward-error bounds) estándar para la sumatoria de punto flotante en el peor de los casos, tales como $|\hat{s} - s| \le \gamma_{k-1} \sum |p_i|$, son independientes de la topología del árbol de reducción. Si bien estos límites proporcionan garantías de seguridad, no logran distinguir entre diferentes estructuras de árbol (por ejemplo, secuencial, por pares, bloqueado) cuando las entradas son aleatorias. En consecuencia, no pueden predecir qué topología minimiza el error típico (error cuadrático medio, MSE) para un conjunto de datos dado. El artículo aborda la necesidad de un modelo que capture cómo la "geometría de reducción" —el orden específico de las adiciones por pares— interactúa con las estadísticas de entrada para determinar la acumulación de error.

Metodología

Los autores desarrollan una teoría de segundo momento que va más allá del análisis del peor caso, modelando la acumulación de errores de redondeo como un proceso estocástico dependiente de la estructura del árbol.

1. Recurrencia Condicional Exacta

El análisis comienza con un redondeo condicionalmente insesgado (por ejemplo, redondeo estocástico). Al condicionar sobre la información disponible justo antes de que un nodo sea redondeado (la $\sigma$-álgebra $\mathcal{F}^-_v$), los autores derivan una recurrencia exacta para la varianza del error acumulado. Esta recurrencia separa el error heredado del error de redondeo local, mostrando que los términos cruzados se anulan en expectativa. Se demuestra que la varianza local depende del valor del operando antes del redondeo, $x_v$.

2. El Modelo de $\nu$-Constante

Para crear un modelo tratable de redondeo a lo más cercano determinista (donde los errores no son estrictamente condicionalmente insesgados), los autores introducen una aproximación de "$\nu$-constante". Reemplazan la varianza local dependiente del operando con un modelo homogéneo $\psi_v(x) = \nu u^2 x^2$, donde $\nu$ es un coeficiente adimensional calibrado empíricamente. Esto simplifica la recurrencia a una forma donde el error cuadrático esperado total es proporcional a la suma de los cuadrados de las sumas parciales exactas: $\sum_v q_v^2$.

3. El Kernel de Ancestro Común ($K_T$)

La contribución teórica central es la representación de la suma de los cuadrados de las sumas parciales como una forma cuadrática:
$$\sum_{v \in \text{int}(T)} q_v^2 = p^\top K_T p$$
Aquí, $K_T$ es un kernel de ancestro común, una matriz de $k \times k$ donde la entrada $(K_T)_{ij}$ cuenta el número de nodos internos que son ancestros tanto de la hoja $i$ como de la $j$. Esta matriz codifica la geometría de la reducción.

4. Compresión i.i.d. y Estadísticas del Árbol

Para entradas independientes e idénticamente distribuidas (i.i.d.) con media $\mu$ y varianza $\tau^2$, la expectativa de la forma cuadrática colapsa en dos estadísticas escalares del árbol:
$$\mathbb{E}[\text{MSE}] \propto \tau^2 \Lambda_1(T) + \mu^2 \Lambda_2(T)$$

• $\Lambda_1(T)$: La suma de las profundidades de las hojas (longitud de camino externo total). Esto gobierna el error para entradas centradas ($\mu=0$).
• $\Lambda_2(T)$: La suma de los cuadrados de los tamaños de los subárboles internos. Esto gobierna el error para entradas no centradas ($\mu \neq 0$).

5. Extensión a GEMM

La teoría se extiende a la Multiplicación de Matrices Generales (GEMM). Se demuestra que el error de Frobenius cuadrático esperado es una contracción del kernel $K_T$ con una matriz $G$ formada a partir del producto de Hadamard de las matrices de Gram de los operandos ($G = (A^\top A) \circ (BB^\top)$).

Contribuciones Clave

Optimización Teórica

El artículo deriva topologías de árbol óptimas para diferentes regímenes:

• Entradas Centradas: Los árboles balanceados minimizan $\Lambda_1$, mientras que los árboles secuenciales lo maximizan. El exponente óptimo para el error RMS es $1/2$ para árboles por pares (pairwise).
• Entradas No Centradas: La topología óptima cambia. Para jerarquías de etapas fijas, los autores derivan un "programa de brecha de duplicación" (doubling-gap schedule) donde las proporciones de las etapas se reducen a la mitad sucesivamente ($r_\ell \propto 2^{-\ell}$) para minimizar $\Lambda_2$.
• Varianzas Heterogéneas: Para entradas centradas independientes con varianzas desiguales, la estructura de árbol óptima corresponde a la codificación de Huffman, minimizando la longitud de camino externo ponderada por la varianza.
• Bloqueo (Blocking): Para el bloqueo secuencial de dos etapas, el tamaño de bloque óptimo escala como $b \propto \sqrt{k}$ para entradas centradas (obteniendo un exponente de RMS de $3/4$), pero requiere un escalamiento diferente para entradas no centradas.

Validación Empírica

Los autores validan el modelo de $\nu$-constante a través de múltiples precisiones (binary64, binary32, binary16 emulado por software, y bfloat16) y tipos de entrada:

• Orden de Topología: El modelo predice correctamente el orden de los errores RMS entre árboles secuenciales, bloqueados y por pares.
• Calibración: Un $\nu \approx 0.19$ calibrado independientemente para round-to-nearest en binary64 permite al modelo predecir el MSE absoluto con un error del 3% para GEMM y captura correctamente las leyes de escalamiento para diversas familias de árboles.
• Límites de Estancamiento: El estudio identifica un régimen de falla en precisiones bajas (binary16/bfloat16) para sumas positivas donde el "estancamiento" (sumar un número pequeño a uno grande sin que haya cambio) causa que el sesgo domine, rompiendo la aproximación de $\nu$-constante.

Resultados

• Leyes de Escalamiento: El artículo confirma que, para entradas centradas, la sumatoria por pares escala como $O(\sqrt{\log k})$, la sumatoria bloqueada con $b \propto \sqrt{k}$ escala como $O(k^{3/4})$, y la sumatoria secuencial escala como $O(k)$.
• Régimen No Centrado: Para entradas con medias distintas de cero (por ejemplo, denominadores de softmax, normas al cuadrado), el error está dominado por $\Lambda_2$. El programa de "brecha de duplicación" óptimo produce un comportamiento de escalamiento diferente al programa geométrico óptimo para entradas centradas.
• Entradas Correlacionadas: Para entradas correlacionadas AR(1), se requiere la contracción completa del kernel $\langle K_T, M \rangle$; la aproximación i.i.d. falla significativamente a medida que aumenta la correlación.
• Validación de Librerías: El modelo predice con éxito el escalamiento del error de un árbol reconstruido de np.sum de NumPy, capturando la "curva" específica en el crecimiento del error causada por su jerarquía multiescala (acumulación secuencial dentro de bloques pequeños, reducción recursiva para bloques más grandes).

Significado y Reivindicaciones

El artículo afirma proporcionar una teoría de segundo momento que cierra la brecha entre los límites del peor caso y el comportamiento del error práctico. Su importancia radica en:

1. Conciencia de la Geometría: Cuantifica explícitamente cómo la estructura del árbol de reducción (geometría) interactúa con las estadísticas de entrada, un factor ignorado por los límites estándar.
2. Poder Predictivo: Ofrece un flujo de trabajo (Tabla 1) para predecir el error RMS de una implementación específica dado su árbol de reducción y la distribución de sus entradas, validado a través de un amplio rango de precisiones y arquitecturas.
3. Guía de Optimización: Proporciona criterios concretos para elegir programas de reducción (por ejemplo, tamaños de bloque, proporciones de etapas) basados en si los datos están centrados o no, y si las varianzas son homogéneas.
4. Limitaciones: Los autores señalan modestamente que el modelo depende del supuesto $h(T)u^2 \ll 1$ y puede fallar en regímenes de baja precisión donde el estancamiento y el sesgo sistemático dominan el error, como se observó en sus experimentos con binary16/bfloat16. El $\nu$-constante es una calibración empírica, no una constante aritmética universal.

El trabajo establece que, para entradas aleatorias, el error "típico" está gobernado por la estructura de ancestría compartida del árbol, permitiendo el diseño de árboles de reducción numéricamente estables adaptados a las características específicas de los datos.