AlphaDev: Wenn KI Algorithmen erfindet — und warum jeder davon profitiert
· ~8 min readEinleitung
Im Juni 2023 wurde ein neuer Sortieralgorithmus in die LLVM libc++-Standardbibliothek aufgenommen. Das klingt nach Routine, war es aber nicht. Denn dieser Algorithmus wurde nicht von einem Menschen entworfen, sondern von einem Reinforcement-Learning-Agenten namens AlphaDev entdeckt. Es war der erste KI-generierte Algorithmus, der in eine bedeutende C++-Standardbibliothek aufgenommen wurde.
Seitdem läuft dieser Algorithmus auf jedem Apple-Gerät, auf Android-Systemen und auf zahlreichen Linux-Distributionen. Jedes Programm, das std::sort aufruft, profitiert davon, ob es das weiß oder nicht. Dieser Artikel erklärt, wie AlphaDev funktioniert, was es entdeckt hat, und warum diese Methodik für die praktische Softwareentwicklung relevance hat, die über das reine Forschungslabor hinausgeht.
Das AssemblyGame: Algorithmen als Spiel
AlphaDev formuliert die Algorithmusentdeckung als Einzelspielerspiel, das "AssemblyGame" genannt wird. Der Ansatz basiert auf AlphaZero, demselben System, das Go und Schach gemeistert hat.
Die Regeln sind einfach definiert:
- Zustand: Das aktuelle Assemblerprogramm samt CPU-Zustand (Register, Speicher, Flags)
- Aktion: Eine einzelne Assembleranweisung an das Programm anhängen
- Belohnung: Eine Kombination aus Korrektheit (sortiert das Programm?) und Latenz (wie schnell läuft es?)
Der entscheidende Punkt: AlphaDev sucht im Instruktionstraum, nicht im Programraum. Es baut Programme Anweisung für Anweisung auf, anstatt fertige Programme zu bewerten. Intern nutzt das System eine Transformdarstellung für Programme und ein MLP für CPU-Zustände.
Belohnungsform und Proxy-Funktionen
Ein pragmatisches Detail: Nur 0,002 % der während des Trainings erzeugten Programme erhalten eine tatsächliche Latenzmessung. Der Rest wird über erlernte Proxy-Funktionen bewertet. Ohne dieses Design wäre das Training schlichtweg nicht machbar gewesen, weil echte Latenzmessungen zu teuer sind.
AlphaDev nutzt ein sogenanntes Dual-Value-Function-Setup: Ein Netzwerk-Head schätzt die Korrektheit, ein anderer die Latenz. So kann das System gleichzeitig lernen, was überhaupt funktioniert, und was davon schnell ist.
Die Entdeckungen: Neue Sortieralgorithmen
AlphaDev hat mehrere Sortieralgorithmen gefunden, die kürzer und schneller sind als die bisherigen Implementierungen. Die Ergebnisse im Überblick:
| Algorithmus | Bisherige Länge | AlphaDev | Einsparung |
|---|---|---|---|
| Sort 3 | 18 Instruktionen | 17 | 1 |
| Sort 5 | 46 Instruktionen | 42 | 4 |
| VarSort3 | 33 Instruktionen | 21 | 12 |
| VarSort4 | Benchmark | ~29 kürzer | signifikant |
Die 70 % Beschleunigung, die in der Öffentlichkeit oft zitiert wird, bezieht sich auf die Latenz bei kurzen Sequenzen (3 bis 5 Elemente), nicht auf den Durchsatz bei großen Datenmengen. Für mehr als 250.000 Elemente liegt die Verbesserung bei etwa 1,7 %.
Warum sind kurze Sequenzen trotzdem so wichtig? Weil sie die Bausteine von Introsort sind, dem Standard-Sortieralgorithmus in den meisten Bibliotheken. Introsort zerlegt große Arrays rekursiv, bis die Teilarrays klein genug sind, um mit Insertion-Sort oder Sortier-Netzwerken bearbeitet zu werden. Diese kleinen Sortierungen werden täglich milliardenfach aufgerufen. Jede Beschleunigung hier zählt doppelt.
Die Algorithmen funktionieren für uint32, uint64 und float auf ARMv8, Intel Skylake und AMD Zen 2.
AlphaDevs "Move 37": Swap und Copy
AlphaGo berühmter "Move 37" war ein Zug, den kein Mensch jemals gespielt hätte, der sich aber als brillant erwies. AlphaDev hat etwas Ähnliches geschaffen: zwei neue Instruktionmuster, die von keinem menschlichen Programmierer zuvor verwendet wurden.
AlphaDev Swap Move
Der Swap Move ist ein branchless bedingter Tausch (implementiert als __cond_swap). Er enthält keine Sprunganweisungen. Das bedeutet, dass beide Pfade dieselbe Anzahl an Instruktionen ausführen, unabhängig davon, ob getauscht wird oder nicht. Das eliminiert Branch-Misprediction-Strafen, die auf modernen Prozessoren teuer sein können.
AlphaDev Copy Move
Der Copy Move eliminiert eine einzelne mov-Anweisung, indem er eine vorherige Vergleichsoperation ausnutzt. Wenn bereits garantiert ist, dass B ≤ C gilt, reicht min(A, B) aus, statt min(A, B, C) zu berechnen. Das klingt nach einer Kleinigkeit, aber in einem Tight-Loop zählt jede Instruktion.
Die VarSort4-Struktur
Bei VarSort4 hat AlphaDev eine Struktur gefunden, die gegen die menschliche Intuition verstößt: Das Array wird immer zuerst drei Elemente sortiert, und dann das vierte eingefügt. Nicht vier auf einmal, nicht rekursiv. Dieser Ansatz ist schneller, weil er die Branch-Prediction besser ausnutzt. Jeder Pfad führt exakt die gleiche Anzahl an Instruktionen aus.
Von der Entdeckung zur Standardbibliothek
Die Aufnahme eines KI-entdeckten Algorithmus in eine Standardbibliothek ist ein nicht trivialer Prozess. Bei AlphaDev verlief er wie folgt:
| Schritt | Datum | Details |
|---|---|---|
| Erstellt | 24. Januar 2022 | Phabricator-Review D118029 |
| Akzeptiert | 6. April 2022 | Review abgeschlossen |
| Eingefügt | 8. April 2022 | Commit 194d19... |
- Commit:
194d1965d2c841fa81e107d19e27fae1467e7f11 - Autor: marcogelmi (Marco Gelmi, DeepMind-Co-Autor)
- Committer: philnik777 (Nikolas Klauser, LLVM libc++-Maintainer)
- Reviewer: u.a. ldionne (Louis Dionne, libc++-Lead)
Die Benchmarks liefen auf isolierten Maschinen für Skylake, ARM und AMD. Die Verbesserungen waren statistisch signifikant. libc++ wird auf macOS, iOS, tvOS, watchOS, Google/Android und vielen Linux- und Embedded-Systemen eingesetzt. Die Reichweite ist gigantisch.
Warum die Methode praktisch relevant ist
Ein Algorithmus, der auf dem Papier schneller ist, nützt nichts, wenn er Fehler enthält. Die Korrektheitsverifikation ist der Schlüssel zur praktischen Relevanz.
Dreistufige Verifikation
-
Exhaustives Testen: 2^n statt n! Testfälle (Satz F.2 im Supplementarmaterial). Das reduziert den Testraum drastisch, deckt aber alle Fälle ab.
-
Reverse-Engineering nach C++: Das Assemblerprogramm wird zurück in C++ übersetzt und durch die gesamte LLVM-Testsuite geschickt, die Tausende Tests einschließlich Fuzzing enthält.
-
Assertions für Out-of-Bounds-Erkennung: Alle Arrayzugriffe werden mit Assertions versehen, um sicherzustellen, dass keine Speicherzugriffsfehler auftreten.
Weitere AlphaDev-Ergebnisse
AlphaDev war nicht nur bei Sortieralgorithmen erfolgreich:
- Hashing (Abseil): Bis zu 30 % schneller für 9- bis 16-Byte-Eingaben
- VarInt-Deserialisierung (Protobuf): Etwa 3-fache Beschleunigung für einzelne Werte, mit einem neu entdeckten "VarInt Assignment Move"
- Längeres Sortieren (Sort 6, 7, 8): Die AlphaDev-M-Variante nutzt MuZero kombiniert mit Graph Neural Networks
Diese Ergebnisse sind deshalb so bedeutsam, weil es sich um Fundamente handelt, auf denen jedes Programm aufbaut. Kleine Verbesserungen bei Sorting oder Hashing summieren sich über Milliarden von Ausführungen zu enormen Gewinnen.
Die Entwicklungslinie: Von AlphaDev zu AlphaEvolve
Die Geschichte von AlphaDev ist Teil einer größeren Entwicklung, die von spezialisierten Spiel-Agenten zu allgemeinen Code-Optimierern führt.
Die Zeitlinie
| System | Jahr | Bereich |
|---|---|---|
| AlphaZero | 2017 | Spiele (Go, Schach, Shogi) |
| AlphaTensor | 2022 | Matrixmultiplikation (Tensorzerlegung) |
| AlphaDev | 2023 | Assembly-Level-Algorithmussuche (RL) |
| AlphaEvolve | 2025 | Evolutionäre Optimierung auf hoher Ebene (LLM + Gemini) |
| Algorithmist | 2026 | Beweisgestützte Algorithmussynthese (Multi-Agent-LLM) |
Der entscheidende Wendepunkt
Der Wandel verläuft von spezialisiertem RL auf Assembly-Ebene hin zu allgemeiner, LLM-basierter evolutionärer Suche auf Code-Ebene. AlphaDev arbeitet mit einzelnen Assemblerinstruktionen, AlphaEvolve arbeitet mit ganzen Programmen und beschreibungen in natürlicher Sprache.
AlphaEvolve (2025)
AlphaEvolve hat Ergebnisse erzielt, die für sich allein stehen:
- 4×4 komplexe Matrixmultiplikation: 48 Multiplikationen (die erste Verbesserung gegenüber Strassen seit 56 Jahren)
- Google Borg Rechenzentrum-Scheduling: 0,7 % der globalen Rechenkapazität zurückgewonnen
- Gemini-Training-Kernel: 23 % schneller
- FlashAttention-Optimierung: Bis zu 32,5 % Beschleunigung
Algorithmist (2026, Microsoft)
Der Algorithmist geht noch einen Schritt weiter: Er synthetisiert Code aus mathematischen Beweisen. In einer Veröffentlichung fand das System einen Fehler in einem veröffentlichten Paper. Das zeigt, dass KI nicht nur Code optimieren kann, sondern auch mathematische Richtigkeit überprüfen.
Praktische Anwendungsbereiche
Wo kann diese Methodik in der Praxis eingesetzt werden?
Kernel-Optimierung: Scheduling, Pagetables, System Calls. Diese Routinen werden unzählige Male pro Sekunde aufgerufen. Selbst kleine Verbesserungen haben messbare Auswirkungen.
Netzwerkprotokolle: Paket-Parsing, Checksummen, Routing-Tabellen. Netzwerkstacks sind latency-sensitiv, und die Korrektheitsanforderungen sind klar definiert.
Datenbank-Internas: B-Tree-Traversierung, Join-Algorithmen, Indexkompression. Datenbanken verbringen den Großteil ihrer Zeit in einer Handvoll interner Routinen.
Compiler-Optimierungen: Registerallokation, Instruktionsscheduling, Peephole-Optimierung. Compiler sind ein natürlicher Anwendungsort für KI-gestützte Suche.
Kryptographische Primitive: AES-NI-Routinen, Hashfunktionen. Korrektheit lässt sich hier formal verifizieren, und Performance ist kritisch.
Die gemeinsame Grundlage all dieser Bereiche: Korrektheit lässt sich automatisch verifizieren, und Performance lässt sich messen. Genau diese Kombination macht sie für AlphaDevs Methodik geeignet.
Fazit
AlphaDev hat bewiesen, dass KI neuartige, effiziente Algorithmen entdecken kann, die von Menschen nie in Betracht gezogen wurden. Die praktische Auswirkung ist real: Diese Algorithmen laufen heute auf Milliarden von Geräten.
Die Methodik, RL-geleitete Suche in wohldefinierten Räumen, ist ausgereift und produktionsreif. Die nächste Generation, AlphaEvolve und Algorithmist, erweitert diesen Ansatz auf höhere Code-Ebenen mit formalen Beweisen.
Die Revolution besteht nicht darin, dass KI Code schreibt. Sie besteht darin, dass KI bessere Algorithmen findet, als Menschen es könnten. Und diese Algorithmen laufen nicht in einem Paper, sondern in der libc++, auf jedem iPhone und jedem Android-Gerät. Das ist der Unterschied zwischen theoretischem Fortschritt und praktischem Wert.
Quellen
- Mankowitz, D.J. et al. "Faster sorting algorithms discovered using deep reinforcement learning." Nature 618, 257–263 (2023). DOI: 10.1038/s41586-023-06004-9
- DeepMind Blog: "AlphaDev discovers faster sorting algorithms" (2023)
- LLVM Commit 194d1965d2c841fa81e107d19e27fae1467e7f11
- AlphaEvolve White Paper: arXiv:2506.13131 (2025)
- Algorithmist: arXiv:2603.22363 (2026)