AlphaDev discovers faster sorting algorithms
Zusammenfassung
Kurz
DeepMind berichtet, dass AlphaDev durch bestärkendes Lernen schnellere Sortier- und Hashing-Algorithmen entdeckt habe, darunter Verfahren, die in LLVM libc++ und Abseil aufgenommen wurden. Die Autoren nennen deutliche Geschwindigkeitsgewinne, weisen aber darauf hin, dass die Optimierung auf Assemblerebene bei größeren Algorithmen an Grenzen stößt.
Mittel
Der Bericht beschreibt AlphaDev, ein KI-System von DeepMind, das mithilfe bestärkenden Lernens effizientere Algorithmen sucht. Es baut Programme schrittweise aus Assemblersprache-Befehlen auf und wird sowohl für Korrektheit als auch Geschwindigkeit belohnt. Die Suche sei wegen der großen Zahl möglicher Befehlsfolgen anspruchsvoll.
Für Sortierfolgen mit drei bis fünf Elementen fand AlphaDev laut den Autoren neue Verfahren, die in LLVM libc++ aufgenommen wurden. Sie berichten von bis zu 70 Prozent höherer Geschwindigkeit bei kurzen Folgen und etwa 1,7 Prozent bei Folgen über 250.000 Elemente. Eine ungewöhnliche „Swap-and-Copy“-Technik spare jeweils eine Maschineninstruktion. Bei einem Hashing-Verfahren für Eingaben von 9 bis 16 Byte habe AlphaDev laut Bericht eine 30 Prozent schnellere Variante gefunden, die in Abseil veröffentlicht wurde.
Die Entwickler sehen darin einen möglichen Weg, verbreitete Software zu optimieren. Sie schränken jedoch ein, dass Optimierungen auf Assemblerebene bei größeren Algorithmen schwieriger werden, und untersuchen deshalb die direkte Optimierung höherer Programmiersprachen. Leistungs- und Nutzungsangaben sind Darstellungen beziehungsweise Schätzungen der Autoren.
Ausführlich lesen
Der Bericht stellt AlphaDev vor, ein von DeepMind entwickeltes KI-System, das mithilfe bestärkenden Lernens effizientere Algorithmen finden soll. Die Autoren argumentieren, dass bessere Software angesichts steigenden Rechenbedarfs und begrenzter Fortschritte bei der Hardware helfen könne, Computer leistungsfähiger und nachhaltiger zu machen. Sie beschreiben Sortieralgorithmen als besonders wichtig, da sie in vielen Anwendungen häufig ausgeführt werden.
AlphaDev sucht nach Lösungen, indem es Algorithmen von Grund auf in Assemblersprache aufbaut. Dafür wurde die Sortieraufgabe als Einzelspieler-Spiel modelliert: Das System fügt schrittweise Maschinenbefehle hinzu und erhält eine Belohnung für korrekte und schnelle Ergebnisse. Die Suche ist laut Bericht sehr anspruchsvoll, weil es zahlreiche mögliche Befehlsfolgen gibt und ein einzelner falscher Schritt den Algorithmus unbrauchbar machen kann. Die Korrektheit wird anhand von Testeingaben geprüft; bei Sortieraufgaben vergleicht das System die Ausgaben mit den erwarteten sortierten Reihen.
Nach Angaben der Autoren fand AlphaDev neue Algorithmen für kurze Sequenzen von drei bis fünf Elementen. Diese verbesserten die Sortierbibliothek LLVM libc++: Bei kurzen Sequenzen seien sie bis zu 70 Prozent schneller, bei Sequenzen mit mehr als 250.000 Elementen etwa 1,7 Prozent schneller. Die Autoren erklären, dass Verbesserungen kleiner Teilalgorithmen auch größere Sortiervorgänge beschleunigen können, weil diese Bausteine darin wiederholt zum Einsatz kommen. Die gefundenen Abläufe wurden rückentwickelt, in C++ übertragen und in die Bibliothek aufgenommen.
Als neuartige Lösungen hebt der Bericht sogenannte „Swap-and-Copy“-Züge hervor. Dabei lässt AlphaDev laut Darstellung einen üblichen Zwischenschritt aus und verbindet Elemente auf eine zunächst fehlerhaft wirkende, tatsächlich aber kürzere Weise. So werde jeweils eine Maschineninstruktion eingespart. Die Autoren vergleichen den überraschenden Charakter dieser Lösung mit einem ungewöhnlichen Zug im Go.
Der Bericht beschreibt außerdem einen Transfer auf Hashing, ein Verfahren, mit dem Daten anhand eines Schlüssels schneller gefunden werden. Für einen Bereich von Eingaben mit 9 bis 16 Byte habe AlphaDev einen Algorithmus entdeckt, der 30 Prozent schneller sei. Dieser sei in die Open-Source-Bibliothek Abseil aufgenommen worden. Die Autoren schätzen, dass er inzwischen Billionen Mal täglich verwendet wird.
Die Aussagen zu Geschwindigkeit und Nutzung stammen aus dem Bericht der Entwickler. Als Grenze nennen sie, dass die Optimierung auf Assemblerebene mit zunehmender Größe der Algorithmen schwierig wird. Sie untersuchen deshalb, ob AlphaDev direkt höherstufige Sprachen wie C++ optimieren kann. Der Bericht beschreibt die Ergebnisse als ersten Schritt hin zu allgemeineren KI-Werkzeugen für die Codeoptimierung.
Gegengeprüft von Claude Haiku 5.5: kleine Mängel
Die kurze Zusammenfassung ist ebenfalls treu, lässt aber dieselben Punkte aus. Lunas Stufen und Anteilswerte wurden bewusst nicht übernommen. Der Bericht handelt von KI-gestützter Algorithmenentdeckung und nicht von KI-Sicherheit oder Governance, deshalb beantwortet er die Sammelfragen kaum.
Im Bericht, aber nicht in der Zusammenfassung
- Die Veröffentlichung des Verfahrens in der Fachzeitschrift Nature
- Die Angabe, dass die Änderung die erste seit über einem Jahrzehnt an diesem Teil der Sortierbibliothek ist und der erste durch bestärkendes Lernen entworfene Algorithmus dort ist
- Die Verbindung zu AlphaZero als Grundlage des Systems
- Die Einschätzung der Autoren, AlphaDev sei ein Schritt zu allgemeinen KI-Werkzeugen für das gesamte Computing-Ökosystem
Wie die Modelle den Bericht einordnen
Ansicht
Filter
Fähigkeiten messen
- SF-F4 Für welche Modelle, Entwickler und Einsätze gelten Prüfregeln, und wann muss neu geprüft werden?
- clef 100 %kein Bezug
- Luna 100 %kein Bezug
- JEV 100 %kein Bezug
- amos 100 %kein Bezug
- SubQ 100 %kein Bezug
- drex 48 %gleiches Oberthema, hilft nicht
- d3-ultra 100 %kein Bezug
Unabhängig prüfen
- SF-P3 Woran erkennt man, dass ein Labor sich ehrlich selbst überwacht und dass seine Prüfungen gültig sind?
- clef 100 %kein Bezug
- Luna 100 %kein Bezug
- JEV 31 %einzelne zitierbare Belege
- amos 39 %gleiches Oberthema, hilft nicht
- SubQ 100 %kein Bezug
- drex 45 %gleiches Oberthema, hilft nicht
- d3-ultra 100 %kein Bezug
- SF-P4 Wie lässt sich die Größe von Trainingsläufen überprüfen, ohne Modelldetails offenzulegen?
- clef 100 %kein Bezug
- Luna 100 %kein Bezug
- JEV 100 %kein Bezug
- amos 40 %gleiches Oberthema, hilft nicht
- SubQ 100 %kein Bezug
- drex 100 %kein Bezug
- d3-ultra 100 %kein Bezug
Tempo und Grenzen
- SF-T2 Woran erkennen andere, dass ein Labor wirklich bremst?
- clef 100 %kein Bezug
- Luna 100 %kein Bezug
- JEV 100 %kein Bezug
- amos 100 %kein Bezug
- SubQ 100 %kein Bezug
- drex 46 %gleiches Oberthema, hilft nicht
- d3-ultra 100 %kein Bezug
- SF-T3 Woran erkennt man, dass KI beginnt, ihre eigene Weiterentwicklung voranzutreiben, und wer darf das erlauben?
- clef 100 %kein Bezug
- Luna 38 %einzelne zitierbare Belege
- JEV 27 %Hintergrund, keine Belege
- amos 26 %gleiches Oberthema, hilft nicht
- SubQ 100 %kein Bezug
- drex 45 %gleiches Oberthema, hilft nicht
- d3-ultra 48 %gleiches Oberthema, hilft nicht
- Haiku-Prüfung gleiches Oberthema, hilft nicht
Vertrauen in Modelle
- SF-V3 Halten die Werte eines Modells, wenn niemand zusieht oder die Lage neu ist?
- clef 100 %kein Bezug
- Luna 100 %kein Bezug
- JEV 100 %kein Bezug
- amos 100 %kein Bezug
- SubQ 100 %kein Bezug
- drex 72 %gleiches Oberthema, hilft nicht
- d3-ultra 100 %kein Bezug
- SF-V4 Was für ein Wesen ist ein Modell, und was folgt daraus für den Umgang mit ihm und für den Wert des Menschseins?
- clef 100 %kein Bezug
- Luna 100 %kein Bezug
- JEV 56 %einzelne zitierbare Belege
- amos 49 %gleiches Oberthema, hilft nicht
- SubQ 100 %kein Bezug
- drex 100 %kein Bezug
- d3-ultra 100 %kein Bezug
- SF-V5 Was soll heute für das Verhalten und den Betrieb von Modellen gelten?
- clef 100 %kein Bezug
- Luna 32 %Hintergrund, keine Belege
- JEV 100 %kein Bezug
- amos 45 %gleiches Oberthema, hilft nicht
- SubQ 100 %kein Bezug
- drex 61 %gleiches Oberthema, hilft nicht
- d3-ultra 100 %kein Bezug
Agenten und vernetzte Systeme
- SF-A1 Welche Befugnisse darf ein KI-Agent haben, also eine KI, die selbstständig mit Werkzeugen handelt? Wer entzieht sie ihm, und wie prüft man, dass er in seinem Auftrag bleibt?
- clef 100 %kein Bezug
- Luna 100 %kein Bezug
- JEV 27 %einzelne zitierbare Belege
- amos 100 %kein Bezug
- SubQ 100 %kein Bezug
- drex 100 %kein Bezug
- d3-ultra 100 %kein Bezug
- SF-A2 Lassen sich KI-Systeme sicher anhalten, zurücksetzen, abschotten oder drosseln, und wer darf das anordnen?
- clef 100 %kein Bezug
- Luna 100 %kein Bezug
- JEV 100 %kein Bezug
- amos 100 %kein Bezug
- SubQ 100 %kein Bezug
- drex 53 %gleiches Oberthema, hilft nicht
- d3-ultra 100 %kein Bezug
Modelle teilen und schützen
- SF-H1 Wo endet die erlaubte Nutzung fremder Modellausgaben, und wo beginnt unerlaubte Destillation, also das Trainieren eines eigenen Modells mit diesen Ausgaben?
- clef 100 %kein Bezug
- Luna 100 %kein Bezug
- JEV 100 %kein Bezug
- amos 40 %gleiches Oberthema, hilft nicht
- SubQ 100 %kein Bezug
- drex 100 %kein Bezug
- d3-ultra 100 %kein Bezug
- SF-H2 Was darf offen veröffentlicht werden, und wer ist verantwortlich, wenn ein offenes Modell anderswo Schaden anrichtet?
- clef 100 %kein Bezug
- Luna 30 %Hintergrund, keine Belege
- JEV 38 %einzelne zitierbare Belege
- amos 24 %gleiches Oberthema, hilft nicht
- SubQ 47 %gleiches Oberthema, hilft nicht
- drex 42 %gleiches Oberthema, hilft nicht
- d3-ultra 100 %kein Bezug
- SF-H3 Wie lässt sich nachverfolgen, woraus ein Modell entstanden ist und was in ihm steckt?
- clef 100 %kein Bezug
- Luna 34 %Hintergrund, keine Belege
- JEV 47 %einzelne zitierbare Belege
- amos 40 %gleiches Oberthema, hilft nicht
- SubQ 100 %kein Bezug
- drex 100 %kein Bezug
- d3-ultra 100 %kein Bezug
- Haiku-Prüfung Hintergrund, keine Belege
Frieden und Sicherheit
- SF-K2 Wie weit gelten KI-Abkommen für Verbündete und Geheimdienste, und wie verhalten sie sich zu bestehenden Rüstungskontrollverträgen und -regimen?
- clef 100 %kein Bezug
- Luna 100 %kein Bezug
- JEV 100 %kein Bezug
- amos 100 %kein Bezug
- SubQ 100 %kein Bezug
- drex 47 %gleiches Oberthema, hilft nicht
- d3-ultra 100 %kein Bezug
Offenlegung und Rechenschaft
- SF-O2 Was sollten Regierungen, Labore und Prüfer über ihre Gespräche, Zusagen, Prüfungen und Eingriffe offenlegen?
- clef 100 %kein Bezug
- Luna 100 %kein Bezug
- JEV 100 %kein Bezug
- amos 47 %gleiches Oberthema, hilft nicht
- SubQ 100 %kein Bezug
- drex 52 %gleiches Oberthema, hilft nicht
- d3-ultra 100 %kein Bezug
Beteiligung und Gemeinwohl
- SF-E1 Welche echte Stimme bekommen weitere Staaten, kleine Labore, Hochschulen und Zivilgesellschaft bei den Regeln für KI?
- clef 100 %kein Bezug
- Luna 100 %kein Bezug
- JEV 100 %kein Bezug
- amos 44 %gleiches Oberthema, hilft nicht
- SubQ 100 %kein Bezug
- drex 49 %gleiches Oberthema, hilft nicht
- d3-ultra 100 %kein Bezug
- SF-E2 In welchem Rahmen sollen Staaten KI regeln, und wo liegt eine gemeinsame Untergrenze?
- clef 100 %kein Bezug
- Luna 100 %kein Bezug
- JEV 100 %kein Bezug
- amos 100 %kein Bezug
- SubQ 51 %gleiches Oberthema, hilft nicht
- drex 100 %kein Bezug
- d3-ultra 100 %kein Bezug
- SF-E4 Wie bleibt KI ein gemeinsames Gut, statt Abhängigkeit und Marktmacht zu vertiefen?
- clef 100 %kein Bezug
- Luna 51 %Hintergrund, keine Belege
- JEV 65 %einzelne zitierbare Belege
- amos 31 %gleiches Oberthema, hilft nicht
- SubQ 50 %gleiches Oberthema, hilft nicht
- drex 49 %gleiches Oberthema, hilft nicht
- d3-ultra 100 %kein Bezug
- Haiku-Prüfung nur am Rande erwähnt
- SF-E5 Welche Mitsprache haben die Menschen, die mit KI leben, bei Tempo und Grenzen, und welche Entscheidungen müssen bei ihnen bleiben?
- clef 100 %kein Bezug
- Luna 100 %kein Bezug
- JEV 100 %kein Bezug
- amos 56 %gleiches Oberthema, hilft nicht
- SubQ 100 %kein Bezug
- drex 62 %gleiches Oberthema, hilft nicht
- d3-ultra 100 %kein Bezug
Weitere Berichte zu diesen Fragen
- Woran erkennt man, dass ein Labor sich ehrlich selbst überwacht und dass seine Prüfungen gültig sind?
- Woran erkennt man, dass KI beginnt, ihre eigene Weiterentwicklung voranzutreiben, und wer darf das erlauben?
- Was für ein Wesen ist ein Modell, und was folgt daraus für den Umgang mit ihm und für den Wert des Menschseins?
- Was soll heute für das Verhalten und den Betrieb von Modellen gelten?
- Welche Befugnisse darf ein KI-Agent haben, also eine KI, die selbstständig mit Werkzeugen handelt? Wer entzieht sie ihm, und wie prüft man, dass er in seinem Auftrag bleibt?
- Was darf offen veröffentlicht werden, und wer ist verantwortlich, wenn ein offenes Modell anderswo Schaden anrichtet?
- Wie lässt sich nachverfolgen, woraus ein Modell entstanden ist und was in ihm steckt?
- Wie bleibt KI ein gemeinsames Gut, statt Abhängigkeit und Marktmacht zu vertiefen?
- Alle Berichte im Archiv