🤖 machine learning

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

Dit artikel vestigt een theoretisch kader voor in-context leren op partiële ordeningen dat logische identificeerbaarheid definieert door middel van een exacte voltooiingstrichotomie, het open-wereld onderwijstal getal karakteriseert als de som van cover- en blocker-setkosten, en bewijst dat $s$ -coördinaat decoders posetts exact kunnen representeren indien en slechts indien hun dimensie maximaal $s$ is.

Oorspronkelijke auteurs: Faizanuddin Ansari, Debanjan Dutta, Swagatam Das

Gepubliceerd 2026-08-17

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Faizanuddin Ansari, Debanjan Dutta, Swagatam Das

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Dilemma van de Detective: Wanneer Aanwijzingen Niet Genoeg Zijn

Stel je voor dat je een detective bent die een mysterie probeert op te lossen, maar in plaats van een plaats delict, kijk je naar een reeks aanwijzingen over hoe dingen met elkaar verband houden. In de wereld van Kunstmatige Intelligentie bestaat er een superkracht genaamd "in-context learning". Het is alsof je een slimme computer een paar voorbeelden geeft van een regel in een chatprompt, en zonder zijn brein (zijn interne instellingen) te veranderen, ontdekt de computer hoe hij die regel moet volgen voor nieuwe vragen. Meestal denken we hierbij aan het leren van eenvoudige wiskundige of taalkundige patronen. Maar wat gebeurt er als de regel gaat over "volgorde"? Wat als de aanwijzingen je vertellen dat A groter is dan B, en B groter is dan C, maar ze zeggen niets over A en C? Of erger nog, wat als de aanwijzingen je vertellen dat A niet kleiner is dan B, maar niet vertellen of ze gelijk zijn of dat A eigenlijk groter is?

Dit artikel duikt in die lastige hoek van de logica die "gedeeltelijke ordening" (partial orders) wordt genoemd. Denk aan een gedeeltelijke ordening als een rommelige stamboom waarbij sommige neven duidelijk ouder zijn dan andere, maar sommige neven gewoon "onvergelijkbaar" zijn — je kunt niet zeggen wie ouder is omdat ze op verschillende takken zitten. De grote vraag die de auteurs stellen is: hoeveel aanwijzingen heeft een computer eigenlijk nodig om de hele stamboom te ontdekken? En belangrijker nog: wanneer is het onmogelijk voor de computer om het antwoord te weten, ongeacht hoe slim hij is? Dit is van belang omdat als we de grenzen van deze aanwijzingen niet begrijpen, we AI-systemen kunnen bouen die vol vertrouwen het verkeerde gokken, of we verspillen tijd door ze te veel voorbeelden te geven terwijl een paar er ook zouden voldoen.

Het Verhaal van het Papier: Het In kaart Brengen van het Onkenbare

De auteurs van dit artikel, Faizanuddin Ansari, Debanjan Dutta en Swagatam Das, besloten het leerproces van de AI te behandelen als een spel van logische puzzels. Ze voerden niet alleen experimenten uit om te zien of de AI het goed had; ze bouwden een wiskundige kaart om precies te bewijzen wanneer een puzzel oplosbaar is en wanneer het een doodlopende weg is.

De Drie Uitkomsten van een Aanwijzing
Eerst pakten ze de vraag aan: "Als ik je een lijst geef van 'A is groter dan B' en 'B is niet groter dan C' aanwijzingen, kun je me dan vertellen of A groter is dan C?"
Ze bewezen dat er voor elke eindige verzameling objecten slechts drie mogelijke antwoorden zijn, en de computer kan precies weten welke het is:

Gedwongen Waar (Forced True): De aanwijzingen vormen zo nauw aansluitende logische ketens dat A moet groter zijn dan C.
Gedwongen Onwaar (Forced False): De aanwijzingen creëren een tegenstrijdigheid als A groter zou zijn dan C (zoals een tijdreisparadox), dus A kan niet groter zijn dan C.
Echt Ambigu (Genuinely Ambiguous): De aanwijzingen zeggen simpelweg niet genoeg. A kan groter zijn, of kleiner, of gelijk, en al die scenario's passen perfect bij de aanwijzingen.

Ze lieten zien dat als de AI zich in een "open wereld" bevindt (waarbij niet-vermelde zaken waar kunnen zijn), hij deze "ambigue" zone veel vaker tegenkomt dan wanneer hij ervan uitgaat dat de aanwijzingen een volledig beeld vormen. In feite draaiden ze een massale simulatie op alle mogelijke puzzels met 4 objecten (er zijn er 219 van) en ontdekten dat zelfs als je de AI 11 van de 12 mogelijke aanwijzingen laat zien, bijna 45% van de resterende vragen nog steeds echt ambigu is. De AI is niet "dom"; de informatie ontbreekt gewoon.

De Kosten van het Onderwijzen van een Puzzel
Vervolgens vroegen de auteurs: "Hoeveel aanwijzingen hebben we nodig om de AI een specifieke relatie te leren?"
Ze ontdekten dat het antwoord afhangt van de vorm van de relatie.

Als de objecten in een rechte lijn liggen (zoals een hiërarchie), heb je alleen de directe links tussen buren nodig.
Als de objecten allemaal ongerelateerd zijn (zoals een groep vreemden die elkaar niet kennen), is de kost enorm. Om de AI te leren dat niemand met niemand gerelateerd is, moet je expliciet vertellen dat elk enkel paar ongerelateerd is.
Ze bewezen een harde limiet: Voor een groep van $n$ objecten vereist het slechtste scenario (de "antichain") exact $n(n-1)$ aanwijzingen. Dit is de maximale inspanning die nodig is om elke relatie te leren. Ze identificeerden ook een specifieke "blocker"-kost: de extra aanwijzingen die nodig zijn omdat we ons in een "open wereld" bevinden waar we niet kunnen aannemen dat stilte "nee" betekent.

De Kaart versus het Kompas
Ten slotte keken ze naar hoe de AI deze relaties in zijn "brein" representeert. Ze vroegen zich af: "Kan de AI dit oplossen met een eenvoudige set coördinaten?"
Stel je voor dat je een 3D-object probeert te beschrijven met alleen een 2D-kaart. Als het object te complex is, faalt de kaart. De auteurs bewezen dat de "complexiteit" van de relatie wordt gemeten door iets dat "orde-dimensie" (order dimension) wordt genoemd.

Als de relatie eenvoudig is (zoals een rechte lijn), heeft het een dimensie van 1.
Als het een complexe web is (zoals een Booleaanse rooster), heeft het misschien 5, 10 of zelfs meer dimensies nodig om accuraat beschreven te worden.
Ze stelden een strikte grens vast: Als de relatie meer dimensies nodig heeft dan de "coördinaat-decoder" van de AI heeft, kan de AI deze niet exact leren, ongeacht hoeveel aanwijzingen je hem geeft. Het is geen trainingsprobleem; het is een geometrisch probleem.

Wat dit Betekent
Het artikel beweert niet een betere AI te hebben gebouwd. In plaats daarvan trekt het een hek rond wat logisch mogelijk is. Het vertelt ons dat als een AI soms niet in staat is een vraag te beantwoorden, dat geen bug is — maar een kenmerk van de logica zelf. Als de aanwijzingen ambigu zijn, kan geen enkele hoeveelheid "nadenken" het probleem oplossen. Als de relatie te complex is voor de interne kaart van de AI, zal geen hoeveelheid voorbeelden helpen. Door deze grenzen te scheiden, hopen de auteurs de ontwerpers te helpen bij het bouwen van betere tests voor AI, zodat we het model niet de schuld geven van puzzels die wiskundig onoplosbaar zijn.

Technische Samenvatting: Identificeerbaarheid en Orde-Dimensie Limieten van In-Context Learning op Partiële Orden

1. Probleemstelling

Het artikel behandelt de theoretische limieten van In-Context Learning (ICL) wanneer dit wordt toegepast op relationele taken die worden gedefinieerd door partiële orden (posets), in plaats van enkelwaardige functies. Terwijl bestaande ICL-theorie vaak uitgaat van prompts gesampled uit onbekende functies, betreft relationeel redeneren transitiviteit, antisymmetrie en inconparabiliteit. Een eindige prompt bepaalt mogelijk niet logisch de uitkomst van een gezochte vergelijking (bijv. of $a \preceq b$ ) vanwege:

Ontbrekend bewijs versus inconparabiliteit: Het onderscheid tussen een gebrek aan informatie en een bevestigd gebrek aan relatie.
Structurele Complexiteit: De potentiële noodzaak voor meerdere onafhankelijke ordeningscoördinaten of lange transitieve ketens om een query op te lossen.
Semantische Ambiguïteit: Het onderscheid tussen open-wereld semantiek (niet-vermelde relaties kunnen gelden) en gesloten-wereld semantiek (een getoonde Hasse-diagram wordt als compleet beschouwd).

Het kerndoel is om te formaliseren wat een relationele prompt logisch bepaalt, hoeveel labels vereist zijn om een eindige poset te onderwijzen, en om de exacte capaciteit van formele coördinaat-decoder klassen vast te stellen om deze structuren te representeren.

2. Methodologie en Formeel Model

De auteurs ontwikkelen een raamwerk gebaseerd op versie-ruimte semantiek over een vaste, bekende eindige universum $U$ .

Prompt Representatie: Een prompt wordt gedefinieerd als een gelabelde demonstratieset $D = (D^+, D^-)$ , waarbij $D^+$ positieve beweringen bevat ( $x \preceq y$ ) en $D^-$ negatieve beweringen bevat ( $x \not\preceq y$ ).
Versie-ruimte ( $V_B(D)$ ): De verzameling van alle posets die consistent zijn met de achtergrondtheorie $B$ (bijv. poset-axioma's) en de demonstraties $D$ .
Identificeerbaarheid: Een query $q=(a,b)$ is identificeerbaar als alle posets in de versie-ruimte dezelfde waarheidswaarde overeenkomen voor $a \preceq b$ .
Decoder Klasse: Het artikel analyseert prompt-afhankelijke monotone coördinaat decoders, die een prompt mappen naar $s$ coördinaatfuncties $\phi_1, \dots, \phi_s$ zodanig dat $x \preceq y$ geldt indien en slechts indien $\phi_i(x) \le \phi_i(y)$ voor alle $i$ .

3. Belangrijkste Bijdragen en Resultaten

A. Logische Identificeerbaarheid: De Open-Wereld Trichotomie
Voor eindige open-wereld prompts met positieve en negatieve demonstraties, bewijst het artikel een exacte voltooiing trichotomie (Theorem 3). Gegeven de reflexieve transitieve afsluiting $R$ van $D^+$ , valt een query $(a,b)$ precies in één van de drie categorieën:

Gedwongen Waar (Forced True): $a R b$ . De relatie wordt geïmpliceerd door transitiviteit.
Gedwongen Onwaar (Forced False): $a \not R b$ EN OF ( $b R a$ ) OF de transitieve afsluiting van het toevoegen van $(a,b)$ zou een negatieve demonstratie in $D^-$ schenden.
Echt Ambigu (Genuinely Ambiguous): Geen van beide condities geldt. De query blijft onidentificeerbaar omdat zowel ware als onware voltooiingen binnen de versie-ruimte bestaan.

Resultaat: Dit biedt een model-vrije classifier voor query-uitkomsten. Zelfs met 11 van de 12 mogelijke labels geobserveerd op een 4-element poset, blijft een aanzienlijk deel van de queries (ongeveer 45%) ambigu onder open-wereld semantiek.

B. Prompt Onderwijskomplexiteit
Het artikel karakteriseert het open-wereld onderwijsgetal $\tau_{ow}(P)$ , gedefinieerd als het minimum aantal labels dat nodig is om een doel-poset $P$ uniek te identificeren.

Exacte Karakterisering (Theorem 6): $\tau_{ow}(P) = |Cov(P)| + \beta(P)$ , waarbij $|Cov(P)|$ het aantal strikte cover-relaties is en $\beta(P)$ de grootte is van een minimum blocker-set hitting set. De blocker-set voor een inconparabel paar $(a,b)$ bestaat uit paren die een transitieve schending zouden afdwingen als $a \preceq b$ toegevoegd zou worden.
Extreemwaarden: Het maximale onderwijsgetal voor een $n$ -element universum is $n(n-1)$ , uniek bereikt door de antichain (waar geen elementen vergelijkbaar zijn). In contrast hiermee vereist een keten slechts $n-1$ labels.
Prijs van Open-Wereld Semantiek: Het verschil tussen open-wereld en gesloten-wereld onderwijskosten is exact $\beta(P)$ , wat de kosten van het afhandelen van incompleetheid isoleert.

C. Structurele Complexiteit en Representatie Limieten
Het artikel scheidt structurele moeilijkheid in onafhankelijke assen: hoogte, breedte, orde-dimensie en certificaatlengtes.

Coördinaat-Decoder Grens (Corollary 12): Een exacte $s$ -coördinaat decoder bestaat voor een taakfamilie dan en slechts dan als de orde-dimensie (Dushnik-Miller dimensie) van elke doel-poset maximaal $s$ is.
Implicatie: Hoewel breedte $\le s$ een voldoende voorwaarde is voor dimensie $\le s$ , is het niet noodzakelijk. Hoge dimensie (bijv. in Boolean lattices of divisor lattices) beperkt strikt de representatieve capaciteit van monotone coördinaat decoders, ongeacht de promptlengte.
Certificaten: Het artikel maakt onderscheid tussen positieve certificaten (kortste Hasse-paden, lengte $\lambda^+$ ) en negatieve certificaten (voorwaarts-gesloten verzamelingen die het doel uitsluiten, grootte $\nu^-$ ). Negatieve niet-bereikbaarheid kan het blootstellen van een grote bereikbare regio vereisen, in tegenstelling tot positieve bereikbaarheid die lokaal kan zijn.

4. Betekenis en Claims

Het artikel beweert een verenigd raamwerk te bieden dat vier verschillende bronnen van falen in relationele ICL ontrafelt:

Niet-identificeerbaarheid: Een informatie-theoretische limiet waarbij de prompt logisch meerdere antwoorden toestaat (geregeerd door Theorem 3).
Prompt Budget: De kosten van het onderwijzen van een specifieke structuur (geregeerd door Theorem 6).
Certificaat Complexiteit: De moeilijkheid van het bewijzen van een relatie via lokale paden of globale bereikbaarheid (geregeerd door Proposition 13 en Lemma 14).
Representatie Capaciteit: Het onvermogen van specifieke decoder klassen (zoals monotone coördinaat maps) om hoog-dimensionale structuren te representeren (geregeerd door Corollary 12).

Betekenis voor Benchmark Design:
De auteurs betogen dat huidige benchmarks deze factoren vaak vermengen. Zij stellen voor dat:

Benchmarks expliciet de universum en de achtergrondtheorie moeten vermelden (bijv. abstracte symbolen versus vooraf getrainde numerieke kennis).
"Onbekend" een geldige output moet zijn voor open-wereld prompts, aangezien veel queries zelfs bij een hoge label-dekking logisch ambigu blijven.
Het onderscheid tussen open-wereld (Hasse-diagram is incompleet) en gesloten-wereld (Hasse-diagram is compleet) cruciaal is, aangezien zij verschillende onderwijskosten en identificeerbaarheidscriteria opleveren.

Het artikel beweert niet het algemene probleem van transformer-expressiviteit op te lossen of trainingsalgoritmen te bieden. In plaats daarvan stelt het logische ondergrenzen en exacte representatiegrenzen vast voor eindige posets, wat verduidelijkt wat een eindige prompt kan en niet kan impliceren, ongeacht de onderliggende modelarchitectuur.