AlphaDev: Wenn KI Algorithmen erfindet — und warum jeder davon profitiert
~8 min read
AIReinforcement LearningAlphaDevDeepMindAlgorithmsLLVMSoftware EngineeringAlphaEvolve
Back openDesk Edu for a sovereign, open-source education — every vote counts.
Vote nowSave products you love by clicking the heart icon.
Die Unix-Philosophie gibt vor, wie Tools gestaltet sein sollten. Die stoische Unix-Philosophie lehrt sie, wie sie sich in Widrigkeiten verhalten sollen: ruhig, ehrlich und gleichgültig gegenüber allem, was außerhalb ihrer Kontrolle liegt. Ein Leitfaden mit einer praxisnahen Fallstudie.
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.
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:
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.
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.
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.
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.
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.
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.
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.
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... |
194d1965d2c841fa81e107d19e27fae1467e7f11Die 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.
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.
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.
AlphaDev war nicht nur bei Sortieralgorithmen erfolgreich:
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 Geschichte von AlphaDev ist Teil einer größeren Entwicklung, die von spezialisierten Spiel-Agenten zu allgemeinen Code-Optimierern führt.
| 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 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 hat Ergebnisse erzielt, die für sich allein stehen:
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.
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.
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.