News
Schnellere FFT von OpenAI? Ben Recht nennt es einen galaktischen Exploit
Unter den Hunderten Manuskripten, die OpenAI vergangene Woche im Repo openai/math veröffentlicht hat, steckt auch ein angeblich schnellerer Fourier-Transformations-Algorithmus. Berkeley-Professor Ben Recht hat sich das Ergebnis auf seinem Blog arg min vorgenommen – und kommt zu einem vernichtenden Urteil.
Was die klassische FFT leistet
Der Cooley-Tukey-Algorithmus von 1965 (Ideen gehen auf Gauß zurück) senkt den Aufwand einer Fourier-Transformation von n² auf unter 5·n·log₂(n) Operationen. Bei einer Million Samples bedeutet das einen Speedup um Faktor 10.000. Seitdem wird gefragt, ob man den log-Faktor noch drücken kann.
Der Haken am OpenAI-Ergebnis
- Galaktische Konstanten: In Big-O-Notation ist der neue Algorithmus minimal schneller. Die versteckte Konstante liegt laut Recht aber bei rund 10^100 – selbst bei n = 10^100 wäre die klassische FFT um Größenordnungen schneller.
- Unrealistisches Rechenmodell: Der Beweis setzt exakte komplexe Arithmetik mit beliebig großen Zahlen voraus, deren Multiplikation je einen Schritt kostet. Solche Computer existieren nicht.
- Bekannte Schranken: Morgenstern (1973) und Ailon zeigten, dass man unter realistischen Bedingungen – beschränkte Koeffizienten bzw. numerische Stabilität – n·log n nicht unterbieten kann.
Einordnung
Recht sieht weniger einen Durchbruch als ein Symptom: Theoretische Informatik habe ihre Spielregeln so schlecht formalisiert, dass KI-Agenten die Lücken ausnutzen – vergleichbar mit Bots, die ein unmögliches Ziel per Hack „lösen“. Ähnliches gelte für das galaktische Matrixmultiplikations-Paper aus derselben Sammlung. Sein bissiges Fazit: KI automatisiert vor allem die schlechtesten Gewohnheiten des akademischen Betriebs – inklusive nutzloser Theorie-Paper.