Technische Samenvatting: Een Tweede-Momenten Theorie voor Floating-Point Reductiebomen

Probleemstelling

Standaard scenario-onafhankelijke foutbounds voor de fout in het slechtste geval bij floating-point optelling, zoals $|\hat{s} - s| \le \gamma_{k-1} \sum |p_i|$, zijn onafhankelijk van de topologie van de reductieboom. Hoewel deze bounds veiligheidsgaranties bieden, slagen ze er niet in om verschillende boomstructuren (bijv. sequentieel, paargewijs, geblokt) te onderscheiden wanneer inputs willekeurig zijn. Bijgevolg kunnen ze niet voorspellen welke topologie de typische fout (gemiddelde kwadratische fout, MSE) minimaliseert voor een gegeven dataset. Het artikel adresseert de behoefte aan een model dat vastlegt hoe de "reductiegeometrie"—de specifieke volgorde van paargewijze optellingen—interacteert met de statistieken van de input om foutaccumulatie te bepalen.

Methodologie

De auteurs ontwikkelen een tweede-momenten theorie die verder gaat dan worst-case analyse door de accumulatie van afrondingsfouten te modelleren als een stochastisch proces dat afhankelijk is van de boomstructuur.

1. Exacte Conditionele Recurrente

De analyse begint met conditioneel onbevooroordeelde afronding (bijv. stochastic rounding). Door te conditioneren op de informatie die beschikbaar is vlak voordat een knoop wordt afgerond (de $\sigma$-algebra $\mathcal{F}^-_v$), leiden de auteurs een exacte recurrente af voor de geaccumuleerde variantie van de fout. Deze recurrente scheidt de geërfde fout van de lokale afrondingsfout, waarbij wordt aangetoond dat de kruistermen in verwachting verdwijnen. De lokale variantie blijkt afhankelijk te zijn van de waarde van de operand vóór de afronding, $x_v$.

2. Het Constant-$\nu$ Model

Om een tractabel model te creëren voor deterministische afronding naar de dichtstbijzijnde waarde (waar fouten niet strikt conditioneel onbevooroordeeld zijn), introduceren de auteurs een "constant-$\nu$" benadering. Ze vervangen de operand-afhankelijke lokale variantie door een homogeen model $\psi_v(x) = \nu u^2 x^2$, waarbij $\nu$ een dimensieloze coëfficiënt is die empirisch is gekalibreerd. Dit vereenvoudigt de recurrente tot een vorm waarbij de totale verwachte kwadratische fout proportioneel is aan de som van de gekwadrateerde exacte gedeeltelijke sommen: $\sum_v q_v^2$.

3. De Common-Ancestor Kernel ($K_T$)

De kern van de theoretische bijdrage is de representatie van de som van gekwadrateerde gedeeltelijke sommen als een kwadratische vorm:
$$\sum_{v \in \text{int}(T)} q_v^2 = p^\top K_T p$$
Hierbij is $K_T$ de common-ancestor kernel, een $k \times k$ matrix waarbij de entry $(K_T)_{ij}$ het aantal interne knopen telt die gemeenschappelijke voorouders zijn van zowel blad $i$ als blad $j$. Deze matrix codeert de reductiegeometrie.

4. I.i.d. Compressie en Boomstatistieken

Voor onafhankelijke en identiek verdeelde (i.i.d.) inputs met gemiddelde $\mu$ en variantie $\tau^2$, stort de verwachting van de kwadratische vorm in tot twee scalaire boomstatistieken:
$$\mathbb{E}[\text{MSE}] \propto \tau^2 \Lambda_1(T) + \mu^2 \Lambda_2(T)$$

• $\Lambda_1(T)$: De som van de bladdieptes (totale externe padlengte). Dit reguleert de fout voor gecentreerde inputs ($\mu=0$).
• $\Lambda_2(T)$: De som van de gekwadrateerde grootte van de interne subtrees. Dit reguleert de fout voor niet-gecentreerde inputs ($\mu \neq 0$).

5. Uitbreiding naar GEMM

De theorie wordt uitgebreid naar General Matrix-Matrix Multiplication (GEMM). De verwachte gekwadrateerde Frobenius-fout wordt getoond als een contractie van de kernel $K_T$ met een matrix $G$ gevormd uit het Hadamard-product van de operand Gram-matrices ($G = (A^\top A) \circ (BB^\top)$).

Belangrijkste Bijdragen

Theoretische Optimalisatie

Het artikel leidt optimale boomtopologieën af voor verschillende regimes:

• Gecentreerde Inputs: Gebalanceerde bomen minimaliseren $\Lambda_1$, terwijl sequentiële bomen deze maximaliseren. De optimale exponent voor de RMS-fout is $1/2$ voor paargewijze bomen.
• Niet-gecentreerde Inputs: De optimale topologie verschuift. Voor hiërarchieën met vaste stadia leiden de auteurs een "doubling-gap schedule" af waarbij de ratio's van de stadia opeenvolgend halveren ($r_\ell \propto 2^{-\ell}$) om $\Lambda_2$ te minimaliseren.
• Heterogene Varianties: Voor onafhankelijke gecentreerde inputs met ongelijke varianties komt de optimale boomstructuur overeen met Huffman-codering, wat de variantie-gewogen externe padlengte minimaliseert.
• Blocking: Voor twee-stadia sequentieel blokken schaalt de optimale blokgrootte als $b \propto \sqrt{k}$ voor gecentreerde inputs (wat een RMS-exponent van $3/4$ oplevert), maar vereist een andere schaling voor niet-gecentreerde inputs.

Empirische Validatie

De auteurs valideren het constant-$\nu$ model over meerdere precisies (binary64, binary32, software-emulated binary16, en bfloat16) en inputtypen:

• Topologie Volgorde: Het model voorspelt correct de volgorde van de RMS-fouten tussen sequentiële, geblokte en paargewijze bomen.
• Kalibratie: Een onafhankelijk gekalibreerde $\nu \approx 0.19$ voor binary64 round-to-nearest stelt het model in staat om de absolute MSE binnen 3% te voorspellen voor GEMM en vangt de schaalwetten voor diverse boomfamilies correct op.
• Stagnatiegrenzen: De studie identificeert een falend regime in lage precisie (binary16/bfloat16) positieve sommen waar "stagnatie" (het toevoegen van een klein getal aan een groot getal zonder verandering) ervoor zorgt dat bias de fout domineert, waardoor de constant-$\nu$ benadering wordt doorbroken.

Resultaten

• Schaalwetten: Het artikel bevestigt dat voor gecentreerde inputs, paargewijze optelling schaalt als $O(\sqrt{\log k})$, geblokte optelling met $b \propto \sqrt{k}$ schaalt als $O(k^{3/4})$, en sequentiële optelling schaalt als $O(k)$.
• Niet-gecentreerd Regime: Voor inputs met een niet-nul gemiddelde (bijv. softmax denominatoren, kwadratische normen), wordt de fout gedomineerd door $\Lambda_2$. De optimale "doubling-gap" schedule levert een andere schaling op dan de geometrische schedule die optimaal is voor gecentreerde inputs.
• Gecorreleerde Inputs: Voor AR(1) gecorreleerde inputs is de volledige kernel-contractie $\langle K_T, M \rangle$ vereist; de i.i.d. benadering faalt significant naarmate de correlatie toeneemt.
• Library Validatie: Het model voorspelt succesvol de foutschaling van een gereconstrueerde NumPy np.sum boom, waarbij de specifieke "bocht" in de foutgroei wordt gevangen die wordt veroorzaakt door de multi-scale hiërarchie (sequentieel accumuleren binnen kleine blokken, recursief halveren voor grotere blokken).

Betekenis en Claims

Het artikel claimt een tweede-momenten theorie te bieden die de kloof overbrugt tussen worst-case bounds en praktisch foutgedrag. De betekenis ligt in:

1. Geometrie-bewustzijn: Het kwantificeert expliciet hoe de structuur van de reductieboom (geometrie) interacteert met de inputstatistieken, een factor die door standaard bounds wordt genegeerd.
2. Voorspellende Kracht: Het biedt een workflow (Tabel 1) om de RMS-fout van een specifieke implementatie te voorspellen gegeven de boomstructuur en de inputverdeling, gevalideerd over een breed scala aan precisies en architecturen.
3. Optimalisatiebegeleiding: Het biedt concrete criteria voor het kiezen van reductieschema's (bijv. blokgroottes, stadiumratio's) op basis van of de data gecentreerd of niet-gecentreerd is, en of de varianties homogeen zijn.
4. Beperkingen: De auteurs merken bescheiden op dat het model steunt op de aanname $h(T)u^2 \ll 1$ en kan falen in lage-precisie regimes waar stagnatie en systematische bias de fout domineren, zoals waargenomen in hun binary16/bfloat16 experimenten. De constant-$\nu$ is een empirische kalibratie, geen universele rekenkundige constante.

Het werk stelt vast dat voor willekeurige inputs de "typische" fout wordt beheerst door de gedeelde voorouderstructuur van de boom, wat het ontwerp van numeriek stabiele reductiebomen mogelijk maakt die zijn afgestemd op specifieke karakteristieken van de data.