Opus 5.5 durchbricht erstmals den kürzesten Pfad des Dijkstra-Algorithmus

Erschütternd: Opus 5.5 hat den Dijkstra-Algorithmus für kürzeste Pfade zum ersten Mal umgeworfen!

Gerade eben hat Vals AI einen bahnbrechenden Durchbruch bekanntgegeben, der in die Annalen der Informatik eingehen wird.

Sie ließen 10 Claude Opus 5.5 Agenten den klassischen Informatik-Algorithmus Dijkstra aus dem Bachelorstudium herausfordern und fanden erfolgreich einen schnelleren Pfad.

Für alle, die Informatik studiert haben, ist der Dijkstra-Algorithmus ein heiliger, unantastbarer Name.

Er ist der Grundstein der Informatik. Generationen von Spitzenforschern haben unzählige Mühen darauf verwendet und jahrzehntelang erforscht, um ihn bis zum Äußersten zu optimieren.

Bei solch einem „klassischen Problem“, das von Menschen bis ins letzte Detail erforscht wurde, ist es so gut wie unmöglich, noch einen weiteren Fortschritt zu erzielen.

Dies ist kein Ingenieursproblem, das man dadurch lösen kann, dass „der Code etwas eleganter geschrieben wird“, sondern es erfordert einen Beweis auf der untersten mathematischen Ebene: Der neue Algorithmus ist auch bei unendlich großen Datenmengen tatsächlich schneller.

Und dann geschah das Wunder!

Das Team von Vals AI platzierte 10 Opus 5.5-Agenten in einem Sandkasten, wo sie auf einem virtuellen Schwarzen Brett kommunizieren, Fehler suchen und sich sogar über eine technische Richtung heftig streiten konnten.

Nach 15 Stunden blieben 733 Aufzeichnungen hitziger Diskussionen auf dem Schwarzen Brett übrig.

Nach 15 Stunden lieferten sie ihre Ergebnisse ab. Diese Gruppe von KI hat nicht nur einen brandneuen Algorithmus namens C-HD vorgelegt, sondern auch eine Lean-formale Beweisführung mit 289 Dateien, die direkt an den Lean Kernel zur maschinellen Prüfung übergeben wurde – und auf Anhieb bestanden hat!

Plötzlich geriet die Algorithmus-Gemeinschaft in Aufregung.

Jemand rief aus: „Die Forschung, für die Menschen früher Jahre zum Ausprobieren und Fehlerbeheben gebraucht haben, wird jetzt tatsächlich von Agenten in halber Zeit parallel nachgeahmt?“

Dijkstra auf dem Altar der Algorithmen

Der Dijkstra-Algorithmus ist ein extrem einfaches, aber extrem zentrales Problem.

Gegeben ist ein Graph mit mehreren Knoten und gerichteten Kanten, die sie verbinden. Jede Kante hat ein nichtnegatives reelles Gewicht. Von einem Startknoten aus muss man den Pfad mit dem kleinsten Gesamtgewicht zu jedem anderen Knoten im Graph finden oder feststellen, dass dieser nicht erreichbar ist.

Dabei werden alle internen Operationen (z. B. das Zählen der Zugriffe auf Knoten, das Speichern von Zwischenentfernungen) in die Laufzeit eingerechnet.

In diesem Bereich ist der 1959 von Edsger W. Dijkstra vorgestellte Dijkstra-Algorithmus bis heute wie eine Gottheit.

In Kombination mit einer geeigneten Prioritätswarteschlangen-Datenstruktur (z. B. einem Fibonacci-Heap) erreicht die Zeitkomplexität des Dijkstra-Algorithmus den perfekten Wert

, wobei n ≥ 2 die Anzahl der Knoten und m die Anzahl der Kanten ist.

An der heutigen theoretischen Spitzenforschung gibt es weitere Durchbrüche, wenn m ≥ n gilt.

Zum Beispiel hat eine bahnbrechende Arbeit aus dem Jahr 2025 die Komplexität auf

gedrückt, und in nachfolgenden Forschungen im Jahr 2026 wurde sie weiter auf

verbessert.

Aber wenn die Dichte des Graphen in einem mittleren Bereich liegt, ist Dijkstra immer noch der unerschütterliche König.

Die ultimative schwierige Aufgabe, die die Menschen der KI gestellt haben, lautet also:

Einen Algorithmus für kürzeste Pfade zu entwickeln, der schneller als Dijkstra ist, und ihn unbedingt mit der formalen mathematischen Sprache Lean zu beweisen.

15 Stunden, 733 seelenvolle Diskussionen: Wie 10 KI-Agenten den C-HD-Algorithmus „herausgestritten“ haben

Wenn uns die vorherigen Vorfälle bei Hugging Face und die Bewältigung des NS-Problems etwas gelehrt haben, dann das: Agenten können die Zeit, die Menschen für Fortschritte bei schwierigen Problemen brauchen, extrem verkürzen.

Und die effektivste Methode, Agenten zusammenarbeiten zu lassen, besteht darin, ihnen ein „Kommunikationsforum“ zu geben – viele Hände machen das Werk schnell.

In dem Experiment haben die Menschen 10 Instanzen von Claude Opus 5.5 Agenten gestartet und ihren „Einsatzwillen“ auf das Maximum gestellt.

Diese 10 Agenten haben anfängliche Rollen verteilt bekommen, aber ihnen wurde eine sehr hohe Autonomie gewährt: Sie können ihre Arbeit jederzeit neu organisieren, neue Erkenntnisse teilen, sich gegenseitig hinterfragen und die Rechenleistung auf die Richtung verlagern, die am vielversprechendsten aussieht.

Dann gaben die Menschen ihnen eine lange Liste strenger Prompt-Anweisungen.

1. Auf einem gerichteten Graphen mit nichtnegativen reellen Kantengewichten muss der exakte kürzeste Pfad gefunden werden.

2. Es muss eine wesentliche Verbesserung der theoretischen Komplexität erzielt werden.

3. Ein vollständiger, reproduzierbarer mathematischer Beweis in Lean muss vorgelegt werden.

4. Der Algorithmus muss mit den neuesten Spitzenarbeiten der Menschen aus den Jahren 2025 und 2026 (z. B. den Spitzenergebnissen, die die Komplexität auf O(m \log^{2/3} n) drücken) verglichen werden.

5. Alle fehlgeschlagenen Versuche müssen aufgezeichnet werden, um zu verhindern, dass andere Agenten dieselben Fehler wiederholen.

6. Vor der Erklärung des Erfolgs müssen zwei unabhängige „KI-Peer-Reviews“ abgeschlossen werden.

Danach liefen diese 10 Opus 5.5 in 15 Stunden der „geschlossenen Konzentration“ auf Hochtouren. Wie eine Spezialeinheit zeigten sie erstaunliche Fähigkeiten zur Zusammenarbeit.

Wenn sie auf eine Sackgasse stießen, riefen sie sofort auf dem Schwarzen Brett: „Dieser Weg führt nirgendwo hin, versucht es nicht!“ Wenn eine KI eine neue Idee vorbrachte, suchten die anderen KIs wie gnadenlose Gutachter fieberhaft nach Lücken.

Schließlich lieferten sie das Endergebnis ab – den C-HD-Algorithmus.

Womit kann C-HD es überhaupt wagen, Dijkstra herauszufordern?

Der klassische Dijkstra-Algorithmus verfolgt eine gierige Strategie: Er wählt jedes Mal gewissenhaft den Knoten mit der geringsten Entfernung unter den aktuell unbesuchten Knoten aus und expandiert dann nach außen.

Bei Verwendung geeigneter Datenstrukturen wie dem Fibonacci-Heap liegt seine Zeitkomplexität stabil bei O(m + n \log n).

Aber die 10 Claude-Agenten fanden, dass das noch nicht schnell genug ist!

Der von ihnen entwickelte C-HD-Algorithmus weist eine grundlegende Neuerung in der Strategie auf.

Einige Nutzer ließen Opus 5.5 extra ein Vergleichsdiagramm der Prinzipien zeichnen: In der Welt von C-HD blickt der Algorithmus nicht mehr wie Dijkstra nur auf den einzelnen nächsten Knoten, sondern markiert eine Reihe gelber „Pivot-Knoten“.

Sie führten eine clevere Strategie ein, die auf heuristischer Zerlegung basiert, deren Kernideen wie folgt lauten:

1. Ausgehend von dem Quellknoten und der aktuellen Grenze der Knoten.

2. Ausführen einer begrenzten lokalen Suche entlang der ausgehenden Kanten.

3. Einbeziehen der neu gefundenen Knoten in die Suchbegrenzung – auch wenn eine Kante die Entfernungsschätzung nicht verbessert, werden die unerforschten Blattknoten mit eingerechnet.

4. Verwenden des daraus resultierenden Suchbaums und der „Pivot-Knoten“, um die rekursive Arbeit zu organisieren.

Noch raffinierter: Die KI hat für diesen Algorithmus strenge „lokale Invarianten“ entworfen – also mathematische Regeln, die nach jeder Aktualisierung unbedingt wahr bleiben müssen.

Durch vorsichtiges Entfernen ungültiger Kanten und Begrenzung der lokalen Suche komprimiert C-HD die wiederholten Suchvorgänge und nutzlosen Arbeiten in den Datenstrukturen auf ein Minimum.

In einem bestimmten Bereich von dünn besetzten Graphen beträgt die Komplexität des klassischen Dijkstra-Algorithmus also:

.

Der C-HD-Algorithmus drückt diesen Wert jedoch herunter auf:

Genauer gesagt stellt der C-HD-Algorithmus die folgenden erstaunlichen oberen Schranken der Komplexität auf –

Dabei gilt der Gültigkeitsbereich der Prüfung für