Technische Samenvatting: Quotient Tree Arithmetic (QTA)

Probleemstelling

Floating-point rekenkunde (IEEE 754), hoewel de standaard voor wetenschappelijke berekeningen en machine learning gedurende decennia, lijdt aan fundamentele beperkingen:

1. Onnauwkeurige Representatie: Veel decimale waarden (bijv. 0,1) kunnen niet exact worden gerepresenteerd, wat leidt tot fouten zoals $0,1 + 0,2 \neq 0,3$.
2. Underflow en Verdwijnende Gradiënten: Minuscule waarden ronden af naar nul, wat het probleem van de verdwijnende gradiënt (vanishing gradient) veroorzaakt in diepe neurale netwerken waar gradiëntproducten naar nul instorten.
3. Niet-determinisme: Resultaten variëren tussen hardware, compilerversies en de volgorde van operanden vanwege afrondingsmodi en de beschikbaarheid van fused multiply-add (FMA).
4. Heuristieken voor Vergelijking: Gelijkheidstoetsen vereisen arbitraire $\epsilon$-toleranties, die onbetrouwbaar zijn.

Bestaande oplossingen, zoals bibliotheken voor willekeurige precisie (GMP, Decimal), leggen zware prestatiekosten op, terwijl kwantisatie (INT8, FP8) precisie opoffert en systematische fouten introduceert.

Methodologie

Het paper stelt Rational Pair Arithmetic (RPA) en de uitbreiding daarvan, Quotient Tree Arithmetic (QTA), voor als een verenigd framework voor exacte en bijna-exacte berekeningen.

1. Rational Pair Arithmetic (RPA)

Het kerninzicht berust op het IEEE 754 Integer Exactness Window: IEEE 754 dubbelprecisie floating-point getallen representeren alle gehele getallen in het bereik $(-2^{53}, 2^{53})$ exact.

• Representatie: Reële grootheden worden opgeslagen als geordende paren $(n, d)$ van IEEE doubles, die strikt als gehele getallen worden behandeld. De waarde is $n/d$, die lui (lazily) wordt geëvalueerd.
• Rekenkunde: Operaties worden uitgevoerd op de gehele componenten:
  • $(a, b) + (c, d) = (ad + bc, bd)$
  • $(a, b) \times (c, d) = (ac, bd)$
  • Vergelijking wordt uitgevoerd via kruisvermenigvuldiging ($ad < bc$).
• Exactheid: Zolang $|n|, |d| < 2^{53}$, is alle rekenkunde exact zonder bibliotheken voor meerdere precisies. Dit dekt praktische domeinen zoals valuta (tot \approx \90$ miljard in centen) en wetenschappelijke metingen.

2. De Cleanup Operatie

Om te voorkomen dat de grootte van de teller en noemer onbegrensd groeit (wat het $2^{53}$ window zou overschrijden), hanteert het systeem een Cleanup operatie:

• Mechanisme: Deel zowel $n$ als $d$ door $\gcd(|n|, |d|)$.
• Hardware Voorstel: Het paper stelt een nieuwe SIMD-instructie voor, RatCleanup, om gevectoriseerde GCD-reductie uit te voeren, waardoor RPA competitief wordt met single-precision floats qua throughput.
• Tracked Cancellation: Voor gestructureerde berekeningen (bijv. vaste noemers voor valuta) kan de compiler factoren elimineren zonder een volledig GCD-algoritme, waardoor de overhead wordt teruggebracht tot $O(1)$.

3. Quotient Tree Arithmetic (Geneste RPA)

Het framework breidt zich uit naar Geneste Rationele Paren, waarbij tellers of noemers zelf rationele paren kunnen zijn, wat een symbolische expressieboom vormt.

• Uitgestelde Evaluatie: Expressies worden onderhouden als bomen. Evaluatie (het platmaken naar een enkel paar) wordt uitgesteld tot een concreet floating-point resultaat expliciet wordt opgevraagd.
• Begrensde Diepte: Stelling 4.2 bewijst dat de boomdiepte met maximaal 1 groeit per rekenkundige operatie ($O(m)$ totale grootte voor $m$ operaties), wat de combinatorische explosie ($O(2^m)$) voorkomt die wordt gezien bij algemene symbolische algebra-systemen.
• Cross-Cancellation: Stelling 4.3 stelt vast dat veelvoorkomende factoren die zowel in de teller- als de noender-subbomen voorkomen, symbolisch geannuleerd kunnen worden voordat er enige deling plaatsvindt. Dit geldt zelfs voor transcendente waarden (bijv. $e^x$) indien deze referentie-gelijk zijn.

Belangrijkste Bijdragen

1. Formele Definitie van RPA: Het exploiteren van het IEEE integer exactness window om een fixed-width, hardware-geaccelereerd rationeel type te creëren.
2. De Cleanup Primitive: Een voorgestelde hardware-instructie (RatCleanup) en een theoretisch bewijs dat deze binnen het exactness window blijft, wat eeuwige exactheid garandeert.
3. Geneste Rationele Paar Algebra: Een formele behandeling van symbolische nesting met bewijzen van begrensde dieptegroei, platmaken in $O(k)$ stappen, en cross-cancellation theorems.
4. Stabiliteitsstellingen:
   • Deferred Stability: Uitgestelde evaluatie vermindert de afrondingsfout van $O(m)$ ULPs (eager evaluatie) naar $O(1)$ ULPs.
   • Onmogelijkheid van Verdwijnende Gradiënten (Stelling 8.1): Onder RPA met cleanup is het structureel onmogelijk dat een product van niet-nul rationele paren nul wordt. Dit elimineert arithmetic underflow in diepe netwerkgradiënten.
5. Cross-Hardware Determinisme: Gegeven een vaste berekeningsvolgorde, zijn RPA-resultaten onafhankelijk van hardware rounding modes, FMA-beschikbaarheid of driver-versies.

Resultaten en Claims

Het paper biedt theoretische bewijzen en analytische schattingen in plaats van empirische benchmarks:

• Throughput: Analytische schattingen suggereren dat flat RPA $\sim 5\text{--}18\times$ trager is dan FP32 (afhankelijk van de operatie en de kosten van cleanup), maar vergelijkbaar met FP64. Met de voorgestelde RatCleanup instructie is de overhead beheersbaar voor high-precision toepassingen.
• Gradiëntstabiliteit: De structurele onmogelijkheid van verdwijnende gradiënten maakt de theoretische haalbaarheid mogelijk van zeer diepe "plain" netwerken (honderden lagen) zonder skip connections of gating mechanismen, mits de rekenkunde binnen het exactness window blijft.
• Exacte Convergentie: Convergentiecriteria kunnen worden gedefinieerd als exacte gelijkheid ($L_t = L_{t-1}$) in plaats van heuristische drempels ($|L_t - L_{t-1}| < \epsilon$).
• Bandbreedte Efficiëntie: Door berekening te behandelen als een symbolische fase (boomconstructie en cancellatie) gevolgd door een numerieke fase (materialisatie), vermindert QTA het geheugentrafic. Gedeelde subbomen (bijv. gewichten) worden één keer geladen, en symbolische cancellaties elimineren tussenliggende geheugenwrites.

Betekenis

Het paper positioneert QTA niet louter als een getalformaat, maar als een computationele substantie die symbolische manipulatie ontkoppelt van numerieke evaluatie.

• Structurele Intelligentie: Het betoogt dat moderne AI-systemen een "worst-case kost" betalen voor elke query. QTA introduceert een laag van structurele intelligentie die algebraïsche eigenschappen exploiteert (cancellatie, uitgestelde deling) om de werkelijke berekening die nodig is te verminderen, vergelijkbaar met hoe caching of sparse attention werkt, maar dan met exacte garanties.
• Veiligheid en Certificering: Voor veiligheidskritische domeinen (autonome voertuigen, medische AI), biedt de mogelijkheid om gecertificeerde afgeleiden (exacte bewijzen van stationariteit) en reproduceerbare training te leveren een paradigmaverschuiving van probabilistische heuristieken.
• Hardware Onafhankelijkheid: Het biedt een pad naar deterministische wetenschappelijke berekeningen, waarbij de "bit-rot" van resultaten over verschillende GPU-generaties of CUDA-versies heen wordt geëlimineerd.

De auteurs concluderen dat hoewel RPA brute throughput inruilt voor exactheid, deze trade-off essentieel is voor wetenschappelijke berekeningen en veiligheidskritische machine learning, waar de kosten van een fout hoger zijn dan de kosten van de berekening. De voorgestelde RatCleanup instructie wordt geïdentificeerd als de cruciale enabler om dit framework praktisch te maken op bestaande hardware-architecturen.