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.
Figures & tables
Figure 1: Exact ambiguity fraction over all 219 labeled four-element posets, averaged uniformly over targets, observed m -subsets of the 12 nonreflexive ordered pairs, and unobserved queries. Observed labels are target-consistent; the calculation is exhaustive.
Family
0pt
0pt
dim
∣Cov∣
L+
N−
Cn
n
1
1
n−1
n−1
n−1
Bm
m+1
(⌊m/2⌋m)
m
m2m−1
m
2m−1
Div(N)
E+1
WN
r
∑iei∏j=i(ej+1)
E
maxiei∏j=i(ej+1)
Dn=([n],∣)
⌊log2n⌋+1
≥⌈n/2⌉
≥r(n)
∑p≤n⌊n/p⌋
⌊log2n⌋
⌊n/2⌋
Table 1: Structural profiles for n≥2 . Entries are exact except the displayed lower bounds for Dn ; WN denotes the width of the fixed divisor lattice. The table makes visible that cover count, width, dimension, and positive/negative certificate sizes are independent axes rather than a single notion of difficulty.
When can a learner make only finitely many prediction errors along every infinite sequence labeled by a fixed, unknown hypothesis? We characterize this form of consistency for arbitrary binary hypothesis classes in ZFC, without requiring a uniform mistake bound. The characterization uses a single linear order on finite realizable traces. Each trace selects its least subtrace, and the order must satisfy two conditions: conflicting traces select different subtraces, and the order is well-founded on the traces of each fixed target. These conditions induce a learner whose selected evidence decreases on every mistake. Conversely, a consistent learner yields such an order through canonical mistake transcripts and the Kleene--Brouwer ordering. The result provides a representation of consistent prediction by finite evidence, answering a question of Lu (2024).
In-context learning (ICL) adapts large language models by conditioning on a small set of ICL examples, avoiding costly parameter updates. Among other factors, performance is often highly sensitive to the ordering of the examples. However, exhaustive search over the n! possible orderings is infeasible. Therefore more efficient ordering methods use model confidence measures (e.g., label-probability entropy) over label sets or take a direct approach to finding the best ordering. We propose PLR, a probabilistic approach to in-context example ordering that replaces discrete ordering search with learning a probability distribution over orderings with the Plackett-Luce model. PLR models orderings using a Plackett-Luce distribution and iteratively updates its parameters to concentrate probability mass on high-performing orderings under a task-level metric. Candidate orderings are sampled efficiently via a Gumbel perturb-and-sort procedure. Experiments on multiple classification benchmarks show that PLR consistently improves few-shot accuracy for k∈{4,8,16,32} examples, and we further demonstrate gains on mathematical reasoning tasks where label-based ordering methods are not applicable. Our code is available at https://github.com/Batorskq/PLR.
Non-parametric (partial) identification of counterfactual queries typically relies on a fully specified causal graph. Motivated by settings with incomplete domain knowledge, we challenge this requirement by leveraging structural assumptions that are inherently implied by the query itself. We show that any counterfactual inquiry induces a, mostly partial, topological ordering over relevant variables, which, in turn, enables an explicit query parametrisation reducing the identification task to a linear program. This allows bounding arbitrary counterfactual and nested counterfactual queries. Our work can be viewed as a generalisation of the classical bounding framework of Tian and Pearl (2000), originally developed for probabilities of causation. We also prove the tightness of our bounds by constructing structural causal models that attain the bounds whilst being compatible with both the observed data and the query-implied order. To assess both the generality and practical utility of the proposed bounding procedure, we revisit several case studies from the literature, demonstrating how the derived bounds can be used to yield informative insights even in the absence of an input causal graph.
Eric Rossetto, Alessandro Antonucci
Istituto Dalle Molle di Studi sull’Intelligenza Artificiale (IDSIA) Scuola Universitaria Professionale della Svizzera Italiana (SUPSI) Lugano, Switzerland