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

• URL: http://arxiv.org/abs/2608.14004v1
• Date: Fri, 14 Aug 2026 06:47:40 GMT
• Title: Identifiability and Order-Dimension Limits of In-Context Learning on Partial Orders
• Abstract summary: 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.<n>We formalize prompt-dependent $s$-coordinate decoders and use the classical coordinate-order equivalence to obtain an exact representation boundary.
• Score: 18.267999630668665
• License: http://creativecommons.org/licenses/by/4.0/
• 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 papers

• Strategic PAC Learnability via Geometric Definability [69.34283267701421]
  Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision.<n>A central question is how the sample complexity of the induced (strategic) hypothesis class depends on the complexities of the underlying hypothesis class and the cost structure governing feasible manipulations.<n>We introduce structure via a geometric definability assumption: both the hypothesis class and the cost-induced neighborhood relation can be defined by first-order formulas over $mathbbR_mathttexp$.<n>We prove that learnability is preserved, with sample complexity controlled by the complexity
  arXiv  Detail & Related papers  (2026-05-13T12:21:56Z)
• Online Set Learning from Precision and Recall Feedback [60.00180898830079]
  We consider the problem of learning an unknown subset $N_texttarget$ of a domain in an online setting.<n>This simple online set learning problem abstracts a variety of learning scenarios with precision- and recall-type feedback.<n>We show that a hypothesis class is learnable in this setting if and only if it has finite Vapnik-Chervonenkis dimension.
  arXiv  Detail & Related papers  (2026-05-10T14:28:05Z)
• Diverse Dictionary Learning [47.381311762862985]
  Given only observational data $X = g(Z)$, where both the latent variables $Z$ and the generating process $g$ are unknown, recovering $Z$ is ill-posed without additional assumptions.<n>We show that intersections, complements, and symmetric differences of latent variables linked to arbitrary observations, along with the latent-to-observed dependency structure, are still identifiable up to appropriate indeterminacies.
  arXiv  Detail & Related papers  (2026-04-19T18:18:34Z)
• Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness [63.833913892018536]
  We study sequential decision making under distributional adversaries that can adaptively choose data-generating distributions from a fixed family $U$.<n>We provide a near complete characterization of families $U$ that admit learnability in terms of a notion known as generalized smoothness.<n>We show that the generalized smoothness also characterizes private learnability under distributional constraints.
  arXiv  Detail & Related papers  (2026-02-24T06:15:59Z)
• Out-of-Context Reasoning in Large Language Models [21.57320110518431]
  We study how large language models (LLMs) reason about memorized knowledge through simple binary relations.<n>Unlike in-context reasoning, the axioms are only seen during training and not provided in the task prompt.<n>We introduce a lightweight technique, out-of-context representation learning, which trains only new token embeddings on axioms and evaluates them on unseen tasks.
  arXiv  Detail & Related papers  (2025-03-13T14:32:30Z)
• Complexity-Theoretic Implications of Multicalibration [8.315801422499863]
  Multiaccurate predictors satisfy a stronger condition: they are calibrated on each set in the collection. This complexity-theoretic Regularity Lemma is known to have implications in different areas. We show that every function (regardless of its hardness) has a small collection of disjoint hardcore sets.
  arXiv  Detail & Related papers  (2023-12-28T18:53:21Z)
• Superposition with Lambdas [59.87497175616048]
  We design a superposition calculus for a clausal fragment of extensional polymorphic higher-order logic that includes anonymous functions but excludes Booleans. The inference rules work on $betaeta$-equivalence classes of $lambda$-terms and rely on higher-order unification to achieve refutational completeness.
  arXiv  Detail & Related papers  (2021-01-31T13:53:17Z)
• Superposition for Lambda-Free Higher-Order Logic [62.997667081978825]
  We introduce refutationally complete superposition calculi for intentional and extensional clausal $lambda$-free higher-order logic. The calculi are parameterized by a term order that need not be fully monotonic, making it possible to employ the $lambda$-free higher-order lexicographic path and Knuth-Bendix orders.
  arXiv  Detail & Related papers  (2020-05-05T12:10:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.