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

arXiv: https://arxiv.org/abs/2608.14004 · HTML: https://mlsanity.com/paper/2608.14004/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 24 references that are in the map.
- First posted on arXiv 14 Aug 2026.

## Builds on (most cited first, 16 of 16)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [What Can Transformers Learn In-Context? A Case Study of Simple Function Classes](https://mlsanity.com/paper/2208.01066/) (2022)
- [What learning algorithm is in-context learning? Investigations with linear models](https://mlsanity.com/paper/2211.15661/) (2022)
- [In-Context Learning Creates Task Vectors](https://mlsanity.com/paper/2310.15916/) (2023)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)
- [How Do Transformers Learn In-Context Beyond Simple Functions? A Case Study on Learning with Representations](https://mlsanity.com/paper/2310.10616/) (2023)
- [Understanding In-Context Learning in Transformers and LLMs by Learning to Learn Discrete Functions](https://mlsanity.com/paper/2310.03016/) (2023)
- [Which Attention Heads Matter for In-Context Learning?](https://mlsanity.com/paper/2502.14010/) (2025)
- [Transformers are Universal In-context Learners](https://mlsanity.com/paper/2408.01367/) (2024)
- [An Information-Theoretic Analysis of In-Context Learning](https://mlsanity.com/paper/2401.15530/) (2024)
- [Large Language Models are Good Relational Learners](https://mlsanity.com/paper/2506.05725/) (2025)
- [Depth-Width tradeoffs in Algorithmic Reasoning of Graph Tasks with Transformers](https://mlsanity.com/paper/2503.01805/) (2025)
- [Ask, and it shall be given: On the Turing completeness of prompting](https://mlsanity.com/paper/2411.01992/) (2024)
- [OpenRFM: Dissecting Relational In-Context Learning](https://mlsanity.com/paper/2606.04320/) (2026)
- [In-Context Learning Operates as Concept Subspace Learning](https://mlsanity.com/paper/2605.18830/) (2026)
- [Assessing the Limits of In-Context Learning beyond Functions using Partially Ordered Relation](https://mlsanity.com/paper/2506.13608/) (2025)

## Abstract (arXiv)

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.