🤖 machine learning

Identifiability and Order-Dimension Limits of In-Context Learning on Partial Orders

Diese Arbeit etabliert einen theoretischen Rahmen für In-Context-Learning auf partiellen Ordnungen, der die logische Identifizierbarkeit durch eine exakte Vervollständigungs-Trichotomie definiert, die Open-World-Lehrzahl als die Summe aus Cover- und Blocker-Set-Kosten charakterisiert und beweist, dass $s$ -Koordinaten-Decoder Posetten genau dann exakt repräsentieren können, wenn deren Dimension höchstens $s$ ist.

Ursprüngliche Autoren: Faizanuddin Ansari, Debanjan Dutta, Swagatam Das

Veröffentlicht 2026-08-17

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Faizanuddin Ansari, Debanjan Dutta, Swagatam Das

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das Dilemma des Detektivs: Wenn Hinweise nicht ausreichen

Stellen Sie sich vor, Sie sind ein Detektiv, der versucht, ein Rätsel zu lösen, aber anstatt eines Tatorts betrachten Sie eine Reihe von Hinweisen darüber, wie Dinge miteinander in Beziehung stehen. In der Welt der Künstlichen Intelligenz gibt es eine Superkraft namens „In-Context Learning“. Es ist so, als würde man einem intelligenten Computer in einem Chat-Prompt ein paar Beispiele einer Regel geben, und ohne sein Gehirn (seine internen Einstellungen) zu verändern, findet er heraus, wie er dieser Regel für neue Fragen folgen kann. Normalerweise denken wir dabei an das Erlernen einfacher mathematischer oder sprachlicher Muster. Aber was passiert, wenn die Regel über eine „Ordnung“ handelt? Was, wenn die Hinweise besagen, dass A größer als B ist und B größer als C, aber sie sagen nichts über A und C aus? Oder schlimmer noch, was, wenn die Hinweise besagen, dass A nicht kleiner als B ist, aber nicht verraten, ob sie gleich groß sind oder ob A tatsächlich größer ist?

Dieses Paper taucht in diese knifflige Ecke der Logik namens „partielle Ordnungen“ ein. Denken Sie an eine partielle Ordnung wie an einen unordentlichen Stammbaum, in dem einige Cousins eindeutig älter sind als andere, aber einige Cousins einfach „inkomparabel“ sind – man kann nicht sagen, wer älter ist, weil sie sich auf unterschiedlichen Zweigen befinden. Die große Frage, die die Autoren stellen, laet: Wie viele Hinweise braucht ein Computer tatsächlich, um den gesamten Stammbaum zu verstehen? Und noch wichtiger: Wann ist es unmöglich für den Computer, die Antwort zu kennen, egal wie intelligent er ist? Dies ist wichtig, denn wenn wir die Grenzen dieser Hinweise nicht verstehen, bauen wir vielleicht KI-Systeme, die mit voller Überzeugung falsch raten, oder wir verschwenden Zeit damit, ihnen zu viele Beispiele zu geben, obwohl ein paar ausgereicht hätten.

Die Geschichte des Papers: Die Kartierung des Unbekannbaren

Die Autoren dieses Papers, Faizanuddin Ansari, Debanjan Dutta und Swagatam Das, entschieden sich dafür, den Lernprozess der KI wie ein Spiel mit Logikrätseln zu behandeln. Sie haben nicht nur Experimente durchgeführt, um zu sehen, ob die KI es richtig macht; sie haben eine mathematische Landkarte erstellt, um genau zu beweisen, wann ein Rätsel lösbar ist und wann es eine Sackgasse ist.

Die drei Ausgänge eines Hinweises
Zuerst gingen sie der Frage nach: „Wenn ich dir eine Liste von ‚A ist größer als B‘- und ‚B ist nicht größer als C‘-Hinweisen gebe, kannst du mir sagen, ob A größer als C ist?“
Sie bewiesen, dass es für jede endliche Menge von Objekten nur drei mögliche Antworten gibt, und der Computer kann genau wissen, welche davon zutrifft:

Erzwungener Wahrheitsgehalt (Forced True): Die Hinweise verknüpfen sich logisch so eng, dass A muss größer als C sein.
Erzwungene Falschheit (Forced False): Die Hinweise führen zu einem Widerspruch, falls A größer als C wäre (wie ein Zeitreise-Paradoxon), also kann A nicht größer als C sein.
Echt Ambivalent (Genuinely Ambiguous): Die Hinweise sagen einfach nicht genug aus. A könnte größer, kleiner oder gleich sein, und all diese Szenarien passen perfekt zu den Hinweisen.

Sie zeigten, dass die KI in einer „offenen Welt“ (in der ungenannte Dinge wahr sein könnten) viel häufiger in diese „ambivalente“ Zone gerät als wenn sie davon ausgeht, dass die Hinweise ein vollständiges Bild darstellen. Tatsächlich führten sie eine massive Simulation über alle möglichen 4-Elemente-Rätsel durch (es gibt 219 davon) und fanden heraus, dass selbst wenn man der KI 11 von 12 möglichen Hinweisen zeigt, fast 45 % der verbleibenden Fragen immer noch echt ambivalent sind. Die KI ist nicht „dumm“; die Information fehlt einfach.

Die Kosten des Lehrens eines Rätsels
Als Nächstes fragten die Autoren: „Wie viele Hinweise brauchen wir, um der KI eine bestimmte Beziehung beizubringen?“
Sie entdeckten, dass die Antwort von der Form der Beziehung abhängt.

Wenn die Objekte in einer geraden Linie liegen (wie eine Befehlskette), benötigt man nur die direkten Verbindungen zwischen den Nachbarn.
Wenn die Objekte alle völlig unzusammenhängend sind (wie eine Gruppe von Fremden, die sich nicht kennen), ist der Aufwand enorm. Um der KI beizubringen, dass niemand mit niemandem verwandt ist, muss man ihr explizit sagen, dass jedes einzelne Paar unverbunden ist.
Sie bewiesen eine harte Grenze: Für eine Gruppe von $n$ Objekten benötigt das Worst-Case-Szenario (die „Antikette“) genau $n(n-1)$ Hinweise. Dies ist der maximale Aufwand, der nötig ist, um irgendeine Beziehung zu lehren. Sie identifizierten auch eine spezifische „Blocker“-Kostenstruktur: die zusätzlichen Hinweise, die benötigt werden, weil wir uns in einer „offenen Welt“ befinden, in der wir Schweigen nicht automatisch als „Nein“ interpretieren können.

Die Karte vs. der Kompass
Schließlich untersuchten sie, wie die KI diese Beziehungen in ihrem „Gehirn“ repräsentiert. Sie fragten: „Kann die KI dies unter Verwendung eines einfachen Satzes von Koordinaten lösen?“
Stellen Sie sich vor, Sie versuchen, ein 3D-Objekt nur mit einer 2D-Karte zu beschreiben. Wenn das Objekt zu komplex ist, versagt die Karte. Die Autoren bewiesen, dass die „Komplexität“ der Beziehung durch etwas gemessen wird, das man „Ordnungsdimension“ nennt.

Wenn die Beziehung einfach ist (wie eine gerade Linie), hat sie eine Dimension von 1.
Wenn es ein komplexes Geflecht ist (wie ein boolescher Verband), benötigt es vielleicht 5, 10 oder sogar mehr Dimensionen, um präzise beschrieben zu werden.
Sie etablierten eine strikte Grenze: Wenn die Beziehung mehr Dimensionen benötigt, als der „Koordinaten-Decoder“ der KI besitzt, kann die KI sie nicht exakt lernen, egal wie viele Hinweise man ihr gibt. Das ist kein Trainingsproblem; es ist ein geometrisches Problem.

Was das bedeutet
Das Paper behauptet nicht, eine bessere KI gebaut zu haben. Stattdessen zieht es einen Zaun um das, was logisch möglich ist. Es sagt uns, dass es manchmal kein Bug ist, wenn eine KI eine Frage nicht beantworten kann, sondern ein Feature der Logik selbst. Wenn die Hinweise ambivalent sind, kann keine Menge an „Nachdenken“ das lösen. Wenn die Beziehung zu komplex für die interne Karte der KI ist, wird keine Menge an Beispielen helfen. Indem sie diese Grenzen trennen, hoffen die Autoren, Designern dabei zu helfen, bessere Tests für KI zu entwickeln, um sicherzustellen, dass wir das Modell nicht für Rätsel verantwortlich machen, die mathematisch unlösbar sind.

Technisches Resümee: Identifizierbarkeit und Ordnung-Dimension-Grenzen von In-Context Learning auf partiellen Ordnungen

1. Problemstellung

Die Arbeit befasst sich mit den theoretischen Grenzen von In-Context Learning (ICL), wenn es auf relationale Aufgaben angewendet wird, die durch partielle Ordnungen (Posets) definiert sind, statt durch singuläre Funktionswerte. Während die bestehende ICL-Theorie oft davon ausgeht, dass Prompts aus unbekannten Funktionen gesampelt werden, beinhaltet relationales Denken Transitivität, Antisymmetrie und Inkomparabilität. Ein endlicher Prompt kann das Ergebnis eines abgefragten Vergleichs (z. B. ob $a \preceq b$ ) aufgrund folgender Faktoren nicht logisch determinieren:

Fehlende Evidenz vs. Inkomparabilität: Die Unterscheidung zwischen einem Mangel an Information und einer bestätigten fehlenden Relation.
Strukturelle Komplexität: Das Potenzial für mehrere unabhängige Ordnungskoordinaten oder lange transitive Ketten, um eine Abfrage aufzulösen.
Semantische Ambiguität: Die Unterscheidung zwischen Open-World-Semantik (nicht erwähnte Relationen können bestehen) und Closed-World-Semantik (ein dargestelltes Hasse-Diagramm wird als vollständig deklariert).

Das Kernziel besteht darin, zu formalisieren, was ein relationaler Prompt logisch determiniert, wie viele Labels erforderlich sind, um einen endlichen Poset zu lehren, und die exakte Kapazität von formalen Koordinaten-Decoder-Klassen zur Repräsentation dieser Strukturen festzulegen.

2. Methodik und formales Modell

Die Autoren entwickeln ein Framework basierend auf der Versionsraum-Semantik über eine feste, bekannte endliche Menge $U$ .

Prompt-Repräsentation: Ein Prompt wird als ein gelabelter Demonstrationssatz $D = (D^+, D^-)$ definiert, wobei $D^+$ positive Aussagen ( $x \preceq y$ ) und $D^-$ negative Aussagen ( $x \not\preceq y$ ) enthält.
Versionsraum ( $V_B(D)$ ): Die Menge aller Posets, die konsistent mit der Hintergrundtheorie $B$ (z. B. Poset-Axiome) und den Demonstrationen $D$ sind.
Identifizierbarkeit: Eine Abfrage $q=(a,b)$ ist identifizierbar, wenn alle Posets im Versionsraum über den Wahrheitswert von $a \preceq b$ übereinstimmen.
Decoder-Klasse: Die Arbeit analysiert promptabhängige monotone Koordinaten-Decoder, die einen Prompt auf $s$ Koordinatenfunktionen $\phi_1, \dots, \phi_s$ abbilden, sodass $x \preceq y$ gilt genau dann, wenn $\phi_i(x) \le \phi_i(y)$ für alle $i$ .

3. Zentrale Beiträge und Ergebnisse

A. Logische Identifizierbarkeit: Die Open-World-Trichotomie
Für endliche Open-World-Prompts mit positiven und negativen Demonstrationen beweist die Arbeit eine exakte Vervollständigungs-Trichotomie (Theorem 3). Gegeben sei der reflexive transitive Abschluss $R$ von $D^+$ , fällt eine Abfrage $(a,b)$ genau in eine von drei Kategorien:

Erzwungener Wahrheitswert (Forced True): $a R b$ . Die Relation wird durch Transitivität impliziert.
Erzwungener Falschheitswert (Forced False): $a \not R b$ UND entweder ( $b R a$ ) ODER der transitive Abschluss durch Hinzufügen von $(a,b)$ würde eine negative Demonstration in $D^-$ verletzen.
Eigentlich Ambivalent (Genuinely Ambiguous): Keine der Bedingungen trifft zu. Die Abfrage bleibt unidentifizierbar, da sowohl wahre als auch falsche Vervollständigungen innerhalb des Versionsraums existieren.

Ergebnis: Dies liefert einen modellfreien Klassifikator für Abfrageergebnisse. Selbst wenn 11 von 12 möglichen Labels auf einem 4-Element-Poset beobachtet wurden, bleibt ein signifikanter Anteil der Abfragen (ca. 45 %) unter Open-World-Semantik ambivalent.

B. Prompt-Lehrkomplexität
Die Arbeit charakterisiert die Open-World-Lehrzahl $\tau_{ow}(P)$ , definiert als die minimale Anzahl an Labels, die erforderlich sind, um einen Ziel-Poset $P$ eindeutig zu identifizieren.

Exakte Charakterisierung (Theorem 6): $\tau_{ow}(P) = |Cov(P)| + \beta(P)$ , wobei $|Cov(P)|$ die Anzahl der strikten Cover-Relationen ist und $\beta(P)$ die Größe einer minimalen Blocker-Set-Treffermenge (blocker-set hitting set) darstellt. Das Blocker-Set für ein inkomparables Paar $(a,b)$ besteht aus Paaren, die eine transitive Verletzung erzwingen würden, falls $a \preceq b$ hinzugefügt würde.
Extremwerte: Die maximale Lehrzahl für ein $n$ -Elemente-Universum ist $n(n-1)$ , was eindeutig durch die Antikette (wo keine Elemente vergleichbar sind) erreicht wird. Im Gegensatz dazu erfordert eine Kette nur $n-1$ Labels.
Preis der Open-World-Semantik: Der Unterschied zwischen Open-World- und Closed-World-Lehrkosten ist exakt $\beta(P)$ , was die Kosten für den Umgang mit Unvollständigkeit isoliert.

C. Strukturelle Komplexität und Repräsentationsgrenzen
Die Arbeit trennt die strukturelle Schwierigkeit in unabhängige Achsen: Höhe, Breite, Ordnungdimension und Zertifikatlängen.

Koordinaten-Decoder-Grenze (Korollar 12): Ein exakter $s$ -Koordinaten-Decoder existiert für eine Aufgabenfamilie genau dann, wenn die Ordnungsdimension (Dushnik-Miller-Dimension) jedes Ziel-Posets höchstens $s$ ist.
Implikation: Während Breite $\le s$ eine hinreichende Bedingung für Dimension $\le s$ ist, ist sie nicht notwendig. Hohe Dimensionen (z. B. in Booleschen Gittern oder Divisor-Gittern) begrenzen die Repräsentationskapazität monotoner Koordinaten-Decoder strikt, unabhängig von der Prompt-Länge.
Zertifikate: Die Arbeit unterscheidet zwischen positiven Zertifikaten (kürzeste Hasse-Pfade, Länge $\lambda^+$ ) und negativen Zertifikaten (vorwärtsgeschlossene Mengen, die das Ziel ausschließen, Größe $\nu^-$ ). Negative Nichterreichbarkeit kann die Exposition eines großen erreichbaren Bereichs erfordern, im Gegensatz zu positiver Erreichbarkeit, die lokal sein kann.

4. Bedeutung und Behauptungen

Die Arbeit beansprucht, ein vereinheitlichtes Framework bereitzustellen, das vier verschiedene Ursachen für das Scheitern von relationalem ICL entwirrt:

Nicht-Identifizierbarkeit: Eine informationstheoretische Grenze, bei der der Prompt logisch mehrere Antworten zulässt (gesteuert durch Theorem 3).
Prompt-Budget: Die Kosten für das Lehren einer spezifischen Struktur (gesteuert durch Theorem 6).
Zertifikatskomplexität: Die Schwierigkeit, eine Relation über lokale Pfade oder globale Erreichbarkeit zu beweisen (gesteuert durch Proposition 13 und Lemma 14).
Repräsentationskapazität: Die Unfähigkeit bestimmter Decoder-Klassen (wie monotone Koordinaten-Maps), hochdimensionale Strukturen zu repräsentieren (gesteuert durch Korollar 12).

Bedeutung für das Benchmark-Design:
Die Autoren argumentieren, dass aktuelle Benchmarks diese Faktoren oft vermischen. Sie schlagen vor, dass:

Benchmarks explizit das Universum und die Hintergrundtheorie angeben müssen (z. B. abstrakte Symbole vs. vortrainiertes numerisches Wissen).
"Unbekannt" ein gültiger Output für Open-World-Prompts sein sollte, da viele Abfragen selbst bei hoher Label-Abdeckung logisch ambivalent bleiben.
Die Unterscheidung zwischen Open-World (Hasse-Diagramm ist unvollständig) und Closed-World (Hasse-Diagramm ist vollständig) entscheidend ist, da sie unterschiedliche Lehrkosten und Identifizierbarkeitskriterien liefert.

Die Arbeit behauptet nicht, das allgemeine Problem der Transformer-Expressivität zu lösen oder Trainingsalgorithmen bereitzustellen. Stattdessen etabliert sie logische Untergrenzen und exakte Repräsentationsgrenzen für endliche Posets und klärt damit, was ein endlicher Prompt unabhängig von der zugrunde liegenden Modellarchitektur implizieren kann und was nicht.