🤖 machine learning

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

This paper establishes a theoretical framework for in-context learning on partial orders that defines logical identifiability through an exact completion trichotomy, characterizes the open-world teaching number as the sum of cover and blocker-set costs, and proves that $s$ -coordinate decoders can exactly represent posets if and only if their dimension is at most $s$ .

Original authors: Faizanuddin Ansari, Debanjan Dutta, Swagatam Das

Published 2026-08-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Faizanuddin Ansari, Debanjan Dutta, Swagatam Das

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Detective's Dilemma: When Clues Aren't Enough

Imagine you are a detective trying to solve a mystery, but instead of a crime scene, you are looking at a set of clues about how things relate to one another. In the world of Artificial Intelligence, there is a superpower called "in-context learning." It's like giving a smart computer a few examples of a rule in a chat prompt, and without changing its brain (its internal settings), it figures out how to follow that rule for new questions. Usually, we think of this as learning simple math or language patterns. But what happens when the rule is about "order"? What if the clues tell you that A is bigger than B, and B is bigger than C, but they say nothing about A and C? Or worse, what if the clues tell you A is not smaller than B, but don't tell you if they are equal or if A is actually bigger?

This paper dives into that tricky corner of logic called "partial orders." Think of a partial order as a messy family tree where some cousins are clearly older than others, but some cousins are just "incomparable"—you can't say who is older because they are on different branches. The big question the authors ask is: How many clues does a computer actually need to figure out the whole family tree? And more importantly, when is it impossible for the computer to know the answer, no matter how smart it is? This matters because if we don't understand the limits of these clues, we might build AI systems that confidently guess wrong, or we might waste time giving them too many examples when a few would do.

The Paper's Story: Mapping the Unknowable

The authors of this paper, Faizanuddin Ansari, Debanjan Dutta, and Swagatam Das, decided to treat the AI's learning process like a game of logic puzzles. They didn't just run experiments to see if the AI got it right; they built a mathematical map to prove exactly when a puzzle is solvable and when it is a dead end.

The Three Outcomes of a Clue
First, they tackled the question: "If I give you a list of 'A is bigger than B' and 'B is not bigger than C' clues, can you tell me if A is bigger than C?"
They proved that for any finite set of items, there are only three possible answers, and the computer can know exactly which one it is:

Forced True: The clues logically chain together so tightly that A must be bigger than C.
Forced False: The clues create a contradiction if A were bigger than C (like a time-travel paradox), so A cannot be bigger than C.
Genuinely Ambiguous: The clues just don't say enough. A could be bigger, or smaller, or equal, and all of those scenarios fit the clues perfectly.

They showed that if the AI is in an "open world" (where unmentioned things might be true), it hits this "ambiguous" zone much more often than if it assumes the clues are a complete picture. In fact, they ran a massive simulation on all possible 4-item puzzles (there are 219 of them) and found that even if you show the AI 11 out of 12 possible clues, nearly 45% of the remaining questions are still genuinely ambiguous. The AI isn't "stupid"; the information is just missing.

The Cost of Teaching a Puzzle
Next, the authors asked: "How many clues do we need to teach the AI a specific relationship?"
They discovered that the answer depends on the shape of the relationship.

If the items are in a straight line (like a chain of command), you only need to show the direct links between neighbors.
If the items are all unrelated (like a group of strangers who don't know each other), the cost is huge. To teach the AI that nobody is related to nobody, you have to explicitly tell it that every single pair is unrelated.
They proved a hard limit: For a group of $n$ items, the worst-case scenario (the "antichain") requires exactly $n(n-1)$ clues. This is the maximum effort needed to teach any relationship. They also identified a specific "blocker" cost: the extra clues needed because we are in an "open world" where we can't assume silence means "no."

The Map vs. The Compass
Finally, they looked at how the AI represents these relationships inside its "brain." They asked: "Can the AI solve this using a simple set of coordinates?"
Imagine trying to describe a 3D object using only a 2D map. If the object is too complex, the map fails. The authors proved that the "complexity" of the relationship is measured by something called "order dimension."

If the relationship is simple (like a straight line), it has a dimension of 1.
If it's a complex web (like a Boolean lattice), it might need 5, 10, or even more dimensions to be described accurately.
They established a strict boundary: If the relationship needs more dimensions than the AI's "coordinate decoder" has, the AI cannot learn it exactly, no matter how many clues you give it. It's not a training issue; it's a geometry issue.

What This Means
The paper doesn't claim to have built a better AI. Instead, it draws a fence around what is logically possible. It tells us that sometimes, an AI failing to answer a question isn't a bug—it's a feature of the logic itself. If the clues are ambiguous, no amount of "thinking" can solve it. If the relationship is too complex for the AI's internal map, no amount of examples will help. By separating these limits, the authors hope to help designers build better tests for AI, ensuring we don't blame the model for puzzles that are mathematically unsolvable.

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

1. Problem Statement

The paper addresses the theoretical limits of In-Context Learning (ICL) when applied to relational tasks defined by partial orders (posets), rather than single-valued functions. While existing ICL theory often assumes prompts sampled from unknown functions, relational reasoning involves transitivity, antisymmetry, and incomparability. A finite prompt may not logically determine the outcome of a queried comparison (e.g., whether $a \preceq b$ ) due to:

Missing Evidence vs. Incomparability: Distinguishing between a lack of information and a confirmed lack of relation.
Structural Complexity: The potential need for multiple independent ordering coordinates or long transitive chains to resolve a query.
Semantic Ambiguity: The distinction between open-world semantics (unmentioned relations may hold) and closed-world semantics (a displayed Hasse diagram is declared complete).

The core objective is to formalize what a relational prompt logically determines, quantify the labels required to teach a finite poset, and establish the exact capacity of formal coordinate-decoder classes to represent these structures.

2. Methodology and Formal Model

The authors develop a framework based on version-space semantics over a fixed, known finite universe $U$ .

Prompt Representation: A prompt is defined as a labeled demonstration set $D = (D^+, D^-)$ , where $D^+$ contains positive assertions ( $x \preceq y$ ) and $D^-$ contains negative assertions ( $x \not\preceq y$ ).
Version Space ( $V_B(D)$ ): The set of all posets consistent with the background theory $B$ (e.g., poset axioms) and the demonstrations $D$ .
Identifiability: A query $q=(a,b)$ is identified if all posets in the version space agree on the truth value of $a \preceq b$ .
Decoder Class: The paper analyzes prompt-dependent monotone coordinate decoders, which map a prompt to $s$ coordinate functions $\phi_1, \dots, \phi_s$ such that $x \preceq y$ if and only if $\phi_i(x) \le \phi_i(y)$ for all $i$ .

3. Key Contributions and Results

A. Logical Identifiability: The Open-World Trichotomy
For finite open-world prompts with positive and negative demonstrations, the paper proves an exact completion trichotomy (Theorem 3). Given the reflexive transitive closure $R$ of $D^+$ , a query $(a,b)$ falls into exactly one of three categories:

Forced True: $a R b$ . The relation is implied by transitivity.
Forced False: $a \not R b$ AND either ( $b R a$ ) OR the transitive closure of adding $(a,b)$ would violate a negative demonstration in $D^-$ .
Genuinely Ambiguous: Neither condition holds. The query remains unidentifiable because both true and false completions exist within the version space.

Result: This provides a model-free classifier for query outcomes. Even with 11 out of 12 possible labels observed on a 4-element poset, a significant fraction of queries (approx. 45%) remain ambiguous under open-world semantics.

B. Prompt Teaching Complexity
The paper characterizes the open-world teaching number $\tau_{ow}(P)$ , defined as the minimum number of labels required to uniquely identify a target poset $P$ .

Exact Characterization (Theorem 6): $\tau_{ow}(P) = |Cov(P)| + \beta(P)$ , where $|Cov(P)|$ is the number of strict cover relations and $\beta(P)$ is the size of a minimum blocker-set hitting set. The blocker set for an incomparable pair $(a,b)$ consists of pairs that would force a transitive violation if $a \preceq b$ were added.
Extremal Values: The maximum teaching number for an $n$ -element universe is $n(n-1)$ , uniquely attained by the antichain (where no elements are comparable). In contrast, a chain requires only $n-1$ labels.
Price of Open-World Semantics: The difference between open-world and closed-world teaching costs is exactly $\beta(P)$ , isolating the cost of handling incompleteness.

C. Structural Complexity and Representation Limits
The paper separates structural difficulty into independent axes: height, width, order dimension, and certificate lengths.

Coordinate-Decoder Boundary (Corollary 12): An exact $s$ -coordinate decoder exists for a task family if and only if the order dimension (Dushnik-Miller dimension) of every target poset is at most $s$ .
Implication: While width $\le s$ is a sufficient condition for dimension $\le s$ , it is not necessary. High dimension (e.g., in Boolean lattices or divisor lattices) strictly limits the representational capacity of monotone coordinate decoders, regardless of the prompt length.
Certificates: The paper distinguishes between positive certificates (shortest Hasse paths, length $\lambda^+$ ) and negative certificates (forward-closed sets excluding the target, size $\nu^-$ ). Negative non-reachability can require exposing a large reachable region, unlike positive reachability which may be local.

4. Significance and Claims

The paper claims to provide a unified framework that disentangles four distinct sources of failure in relational ICL:

Non-identifiability: An information-theoretic limit where the prompt logically allows multiple answers (governed by Theorem 3).
Prompt Budget: The cost of teaching a specific structure (governed by Theorem 6).
Certificate Complexity: The difficulty of proving a relation via local paths or global reachability (governed by Proposition 13 and Lemma 14).
Representation Capacity: The inability of specific decoder classes (like monotone coordinate maps) to represent high-dimensional structures (governed by Corollary 12).

Significance for Benchmark Design:
The authors argue that current benchmarks often conflate these factors. They propose that:

Benchmarks must explicitly state the universe and background theory (e.g., abstract symbols vs. pre-trained numerical knowledge).
"Unknown" should be a valid output for open-world prompts, as many queries remain logically ambiguous even with high label coverage.
The distinction between open-world (Hasse diagram is incomplete) and closed-world (Hasse diagram is complete) is critical, as they yield different teaching costs and identifiability criteria.

The paper does not claim to solve the general problem of transformer expressivity or to provide training algorithms. Instead, it establishes logical lower bounds and exact representation boundaries for finite posets, clarifying what a finite prompt can and cannot entail regardless of the underlying model architecture.