(C) unter Verwendung eines Motivs von Andrei Suslov / 123RF.com

Vishal Sikka, der ehemalige CTO von SAP und heutiger Chef seines Start-ups VianAI Systems, hat zusammen mit seinem Sohn, Varin Sikka (Stanford University) eine Studie herausgegeben, die mathematisch beweisen will, dass LLMs Aufgaben jenseits eines bestimmten Komplexitätsgrads niemals zuverlässig abarbeiten können.

Bereits das vergangene Jahr wurde zum “Jahr der KI-Agenten” erkoren, der Durchbruch blieb allerdings aus, weil die existierenden Agenten noch zu unzuverlässig arbeiten und daher menschliche Bearbeiter nicht ersetzen können. Die Studienautoren glauben nun, daran wird sich auch nichts ändern. Sie schreiben: “Wir zeigen, dass LLMs nicht in der Lage sind, rechnerische und agentenbezogene Aufgaben auszuführen, die eine bestimmte Komplexität überschreiten, und dass LLMs darüber hinaus nicht in der Lage sind, die Genauigkeit der Erledigung von Aufgaben zu überprüfen, die eine bestimmte Komplexität überschreiten.”

Wenn N die Anzahl der Input-Tokens ist und d die Anzahl der Dimensionen des Vektors, der sie beschreibt, dann könnten LLMs keine Aufgaben mehr berechnen, die eine Komplexität größer O(N².d) haben. Diverse Algorithmen und auch agentische Aufgaben überschreiten allerdings diese Grenze. Hinzukommt: Weil das Überprüfen der Erledigung einer Aufgabe oft noch schwieriger ist als die Aufgabe selbst, kann kein LLM verifizieren, ob ein anderes eine Aufgabe jenseits der Komplexitätsschwelle korrekt erledigt hat.

Die Schwierigkeit zeigt sich beispielsweise beim berühmten Problem des Handelsreisenden (Traveling Salesman Problem, TSP), bei dem die kürzeste Route für den Händler gesucht wird, wenn der bestimmte Städte nacheinander besuchen soll. Bei der Brute-Force-Lösung dieses Problems muss die Streckenlänge jeder Städtekombination mit jeder anderen verglichen werden, was schon bei 20 Städten zu 10 hoch 17 Vergleichen führt.

Die Autoren glauben schließlich auch nicht, dass spezielle Reasoning-Modelle dabei besser abschneiden können. Einerseits, weil sie an dieselbe Komplexitätsschranke stießen, andererseits weil ihr Token-Budget viel zu klein für komplexe Aufgaben ist.