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

arXiv:2608.14004v1 Announce Type: new Abstract: In-context learning is commonly formalized as inference from examples of a function. Partial orders instead combine transitivity, antisymmetry, and incomparability, so a finite prompt may not determine a queried comparison. We develop a theory of in-context learning on partial orders that separates logical identifiability, prompt teaching cost, structural complexity, and the exact capacity of a formal coordinate-decoder class. A version-space semantics makes background knowledge and open- versus closed-world assumptions explicit. For finite open-world prompts with positive and negative comparisons, we prove an exact completion trichotomy: after taking the reflexive transitive closure of the positive demonstrations, a query is forced true, forced false because every true completion creates a cycle or violates a negative demonstration, or remains genuinely ambiguous. For a known n-element universe, we characterize the open-world teaching number as the number of covers plus a blocker-set hitting number, prove that its maximum over all n-element posets is n(n-1) and is uniquely attained by the antichain, and identify the blocker term as the exact cost of open-world rather than complete-Hasse semantics. We formalize prompt-dependent s-coordinate decoders and use the classical coordinate-order equivalence to obtain an exact representation boundary: dimension at most s is necessary and sufficient, while width at most s is a convenient sufficient condition.

Related

• A Bayesian Perspective on the Role of Epistemic Uncertainty for Delayed Generalization in In-Context Learning
• UniPROT: Uniform Prototype Selection via Partial Optimal Transport with Submodular Guarantees
• When Context Sticks: Studying Interference in In-Context Learning
• Encoding orders and trees in real-valued functions

Source: arXiv cs.LG | 2026-08-17