Hierarchical Domain Generalization

# Hierarchical Domain Generalization
Source: [https://arxiv.org/html/2607.16528](https://arxiv.org/html/2607.16528)
Chenxiao Yang1, Zhiyuan Li1, Shai Ben\-David2, Nathan Srebro1 1Toyota Technological Institute at Chicago 2University of Waterloo \{chenxiao,zhiyuanli,nati\}@ttic\.edu, shai@uwaterloo\.ca

###### Abstract

We study hierarchical domain generalization as a problem of extrapolation from finite observed regions to an entire instance space, replacing i\.i\.d\. sampling with arbitrary domain hierarchies\. We show that the central obstruction is not only the complexity of the hypothesis class, but the train/test domain partition through which evidence is revealed\. In particular, no matter how small the class or how large the training size, some partition makes generalization fail for some target\. These results suggest that modern generalization theory must treat domain structure as a first\-class object\.

## 1Introduction

The concept of generalization in machine learning has been shaped by the seminal work of Vapnik and Chervonenkis on statistical generalization theory\(Vapnik and Chervonenkis,[1971](https://arxiv.org/html/2607.16528#bib.bib231)\)and by Valiant’s introduction of the PAC model for binary classification\(Valiant,[1984](https://arxiv.org/html/2607.16528#bib.bib205)\)\.

In these setups, training data is drawn i\.i\.d\. from some unknown data distribution𝒟\\mathcal\{D\}, and the learner’s output is evaluated on the*same*𝒟\\mathcal\{D\}\. A successful learner is required to achieve low expected error on the distribution that generated the training data \(or related data distributions in more recent work on domain adaptation learning, e\.g\.,Ben\-Davidet al\.\([2006](https://arxiv.org/html/2607.16528#bib.bib1)\)\)\. This statistical framework has shaped the field’s conception of “what it means to generalize” for four decades\.

By contrast, the large\-language\-model era asks for a kind of generalization that this classical framework does not capture: trained on a very large fixed domain of inputs \(e\.g\., the web\), the learner should reason — recover the underlying rule — and produce correct outputs on relevant inputs outside its training domain\.

However, a model trained on five\-digit addition may fit its training data perfectly yet fail on six\-digit numbers, as it often does in practice\(Anilet al\.,[2022](https://arxiv.org/html/2607.16528#bib.bib226); Leeet al\.,[2024](https://arxiv.org/html/2607.16528#bib.bib227)\)\. In that case, it has matched a pattern in the data, not the rule that adds arbitrarily long numbers\. It fails to*reason*\. What the classical theory calls generalization is, in the sense most scientists and philosophers use the word, interpolation \(biased or regulated by some prior knowledge\)\. This is increasingly insufficient to capture many learning tasks of practical interest\. Reasoning demands extrapolation, or out\-of\-domain generalization: from one kind of input to a different kind that shares some controlled \(deterministic\) similarity with the training data\.

We formalize this form of generalization as exact identification along a domain hierarchy\. Instead of measuring expected error under a data\-generating distribution, we require the learner to recover the target function on the entire instance spaceΩ\\Omega\. Instead of assuming an i\.i\.d\. observation model, we let the observable region grow through an externally specified hierarchy𝒳¯=\(𝒳n\)n≥0\\bar\{\\mathcal\{X\}\}=\(\\mathcal\{X\}\_\{n\}\)\_\{n\\geq 0\}of finite cumulative domains, with∅=𝒳0⊊𝒳1⊊𝒳2⊊⋯\\emptyset=\\mathcal\{X\}\_\{0\}\\subsetneq\\mathcal\{X\}\_\{1\}\\subsetneq\\mathcal\{X\}\_\{2\}\\subsetneq\\cdotsand⋃n≥1𝒳n=Ω\\bigcup\_\{n\\geq 1\}\\mathcal\{X\}\_\{n\}=\\Omega\(soΩ\\Omegais countable\)\. At levelnn, the learner observes the labeled training set\{\(x,f​\(x\)\):x∈𝒳n\}\\\{\(x,f\(x\)\):x\\in\\mathcal\{X\}\_\{n\}\\\}and is evaluated on all ofΩ\\Omega; equivalently, it must extrapolate from the observed region𝒳n\\mathcal\{X\}\_\{n\}to the unobserved complementΩ∖𝒳n\\Omega\\setminus\\mathcal\{X\}\_\{n\}\. The only way to achieve this is to exactly*identify*ff\.

This captures a common desideratum of modern reasoning systems: train on shorter inputs and generalize to longer ones\(Anilet al\.,[2022](https://arxiv.org/html/2607.16528#bib.bib226); Leeet al\.,[2024](https://arxiv.org/html/2607.16528#bib.bib227); Zhouet al\.,[2024](https://arxiv.org/html/2607.16528#bib.bib85)\)\(a\.k\.a\. length generalization\), train on simpler instances and generalize to harder ones\(Bengioet al\.,[2009](https://arxiv.org/html/2607.16528#bib.bib237)\), and train on bounded\-horizon tasks and generalize to tasks with longer horizons\(Abbeet al\.,[2023](https://arxiv.org/html/2607.16528#bib.bib233); Yanget al\.,[2026b](https://arxiv.org/html/2607.16528#bib.bib186)\)\. In the point\-by\-point case, where each increment is a singleton𝒳n∖𝒳n−1=\{xn\}\\mathcal\{X\}\_\{n\}\\setminus\\mathcal\{X\}\_\{n\-1\}=\\\{x\_\{n\}\\\}and hence𝒳n=\{x1,…,xn\}\\mathcal\{X\}\_\{n\}=\\\{x\_\{1\},\\ldots,x\_\{n\}\\\}, the model recovers the presentation model of Gold’s identification\-in\-the\-limit paradigm\(Gold,[1967](https://arxiv.org/html/2607.16528#bib.bib219)\)\.

The central question is: given a hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}, how many levelsNNmust a learner observe to recover the targetf∈ℋf\\in\\mathcal\{H\}on the entire domainΩ\\Omega? This question admits answers of varying strength: the required level may depend on both the target and the hierarchy, it may be common to all targets once the hierarchy is fixed, or it may be required to work uniformly over both targets and hierarchies\.

The answer depends on how uniformly the level must be chosen\. If the level may depend on both the target and the hierarchy, countability ofℋ\\mathcal\{H\}is exactly the right condition\. If the hierarchy is fixed but the same level must work for every target, the threshold becomes finiteness ofℋ\\mathcal\{H\}\. But if the level must be chosen uniformly over the hierarchy itself, the situation changes completely: for every nontrivial hypothesis class, such a guarantee is possible only in the finite\-domain case \([Theorems1](https://arxiv.org/html/2607.16528#Thmtheorem1),[5](https://arxiv.org/html/2607.16528#Thmtheorem5)and[8](https://arxiv.org/html/2607.16528#Thmtheorem8)\)\.

Length generalization gives a concrete fixed\-hierarchy instance of this question\. The hierarchy is string length: training on all strings up to lengthNNand testing on longer strings asks whether that observed prefix determines the target rule\. Since relevant classes such as finitely encoded Transformer families are infinite, we stratify them by complexity: for each boundss, we ask how many lengths are needed to identify every target of complexity at mostss\. Existing non\-asymptotic length\-generalization results estimate this sublevel domain complexity for particular representation classes and complexity scales\(Chenet al\.,[2025](https://arxiv.org/html/2607.16528#bib.bib114); Yanget al\.,[2026a](https://arxiv.org/html/2607.16528#bib.bib115)\); qualitative and approximate variants fit the same fixed\-hierarchy picture\(Huanget al\.,[2025](https://arxiv.org/html/2607.16528#bib.bib113); Izzoet al\.,[2026](https://arxiv.org/html/2607.16528#bib.bib116)\)\.

For a fixed hierarchy, such bounds have a clear interpretation: they say how far one must train along that hierarchy before the target is determined\. But this still leaves open whether the bound reflects a property of the model class itself, or only of the particular hierarchy used to train and test\. Our no\-free\-lunch result shows that the latter dependence is unavoidable\. Even with the hypothesis class and complexity scale fixed, another hierarchy can make the finite\-slice bounds grow arbitrarily fast \([Theorems12](https://arxiv.org/html/2607.16528#Thmtheorem12)and[6](https://arxiv.org/html/2607.16528#S6.SS0.SSS0.Px2)\)\. Thus a length\-generalization bound is a bound for the length hierarchy, not a hierarchy\-free guarantee for arbitrary domain shifts\.

Classical no\-free\-lunch theorems warn that an unrestricted hypothesis class admits no uniform learning guarantee\(Shalev\-Shwartz and Ben\-David,[2014](https://arxiv.org/html/2607.16528#bib.bib9)\)\. Here the obstruction comes from a second object that classical theory keeps offstage: the hierarchy that determines what is observed before what\. A domain\-generalization guarantee is therefore a property of the pair\(ℋ,𝒳¯\)\(\\mathcal\{H\},\\bar\{\\mathcal\{X\}\}\), not ofℋ\\mathcal\{H\}alone\.

We further extend the framework and connect it to several neighboring learning settings, including online learning and generation in the limit\(Kleinberg and Mullainathan,[2024](https://arxiv.org/html/2607.16528#bib.bib220)\)\. Online learning counts mistakes rather than identifying levels, while generation in the limit asks for a weaker output than exact recovery\. Furthermore, allowing error, or replacing hierarchies by distributional train/test sampling, does not by itself remove the difficulty: a guarantee still requires structural assumptions relating the observed region to the region on which the learner is evaluated\. However, once we change the data model to positive\-only presentations, uniform identification can hold for infinite classes and is controlled by overlap among positive regions\.

Organization\.The rest of the paper is organized as follows\.[Sections2](https://arxiv.org/html/2607.16528#S2)and[3](https://arxiv.org/html/2607.16528#S3)introduce the hierarchy\-based learning model and the main characterization theorem\.[Sections4](https://arxiv.org/html/2607.16528#S4)and[5](https://arxiv.org/html/2607.16528#S5)develop the fixed\-hierarchy quantitative viewpoint, with length generalization as the central example\.[Section6](https://arxiv.org/html/2607.16528#S6)shows why these bounds cannot be made independent of the hierarchy\.[Section7](https://arxiv.org/html/2607.16528#S7)discusses extensions to related learning settings\.

## 2Hierarchical Domain Generalization

### 2\.1Setup

LetΩ\\Omegabe a countably infinite instance space and letℋ⊆\{0,1\}Ω\\mathcal\{H\}\\subseteq\\\{0,1\\\}^\{\\Omega\}be a binary hypothesis class\.111Finite domains are used only as degenerate comparison cases, with the convention that the hierarchy collapses to𝒳n=Ω\\mathcal\{X\}\_\{n\}=\\Omegafor all large enoughnn\. The binary range is for concreteness; all characterizations extend to any finite label space\.We work in the realizable setting with deterministic labeling: an unknown targetf∈ℋf\\in\\mathcal\{H\}generates labelsf​\(x\)∈\{0,1\}f\(x\)\\in\\\{0,1\\\}forx∈Ωx\\in\\Omega\. For any subset𝒳⊆Ω\\mathcal\{X\}\\subseteq\\Omega, writef\|𝒳f\|\_\{\\mathcal\{X\}\}for the labeled training set\{\(x,f​\(x\)\):x∈𝒳\}\\\{\(x,f\(x\)\):x\\in\\mathcal\{X\}\\\}\.

To model out\-of\-domain generalization, we must specify how the observable part ofΩ\\Omegagrows\. The primitive object is not a sampling distribution, but a predetermined sequence of finite cumulative regions whose labels become available to the learner\.

###### Definition 1\(Domain hierarchy\)\.

A*hierarchy*onΩ\\Omegais a telescopic exhaustion𝒳¯=\(𝒳n\)n≥0\\bar\{\\mathcal\{X\}\}=\(\\mathcal\{X\}\_\{n\}\)\_\{n\\geq 0\}by finite cumulative observed regions satisfying

∅=𝒳0⊊𝒳1⊊𝒳2⊊⋯,\|𝒳n\|<∞​for every​n,⋃n≥1𝒳n=Ω\.\\emptyset=\\mathcal\{X\}\_\{0\}\\;\\subsetneq\\;\\mathcal\{X\}\_\{1\}\\;\\subsetneq\\;\\mathcal\{X\}\_\{2\}\\;\\subsetneq\\;\\cdots,\\qquad\|\\mathcal\{X\}\_\{n\}\|<\\infty\\text\{ for every \}n,\\qquad\\bigcup\\nolimits\_\{n\\geq 1\}\\mathcal\{X\}\_\{n\}=\\Omega\.\(1\)

Forn≥1n\\geq 1, writeΔn:=𝒳n∖𝒳n−1\\Delta\_\{n\}:=\\mathcal\{X\}\_\{n\}\\setminus\\mathcal\{X\}\_\{n\-1\}for the newly revealed increment at levelnn\. The definition is intentionally agnostic about how the regions are ordered\. One common source is a sequence of externally specified domains, such as different populations, demographic subgroups, or intervention\-based environments\. Another source ordersΩ\\Omegaby an intrinsic property of the inputs, such as length or difficulty, placing simpler inputs in early levels and harder ones later, as in length generalization and curriculum learning\. When each increment is a singleton, sayΔn=\{xn\}\\Delta\_\{n\}=\\\{x\_\{n\}\\\}, equivalently𝒳n=\{x1,…,xn\}\\mathcal\{X\}\_\{n\}=\\\{x\_\{1\},\\ldots,x\_\{n\}\\\}, the hierarchy recovers Gold’s identification\-in\-the\-limit setting\(Gold,[1967](https://arxiv.org/html/2607.16528#bib.bib219)\)\.

#### Hierarchical Domain Generalization\.

Once a hierarchy is fixed, levelnnsplitsΩ\\Omegainto the observed region𝒳n\\mathcal\{X\}\_\{n\}, from which the learner receives the labeled training setf\|𝒳nf\|\_\{\\mathcal\{X\}\_\{n\}\}, and the unobserved complementΩ∖𝒳n\\Omega\\setminus\\mathcal\{X\}\_\{n\}, which is out of domain relative to that level\. The learner is evaluated on the entireΩ\\Omega, so success requires extrapolation from the observed region to the unseen part of the hierarchy\. This in\-domain/out\-of\-domain split is determined by𝒳¯\\bar\{\\mathcal\{X\}\}alone, without any distributional assumptions\.

We idealize each observed level as fully labeled: at levelnn, the learner has access to all labels on𝒳n\\mathcal\{X\}\_\{n\}\. Thus the question is not whether the learner can fit the observed region, but whether that region already determines the target beyond it\.

###### Definition 2\(Learner\)\.

A learning algorithm is a mapA:⋃𝒳⊆Ω,\|𝒳\|<∞\{0,1\}𝒳→\{0,1\}ΩA:\\bigcup\_\{\\mathcal\{X\}\\subseteq\\Omega,\\ \|\\mathcal\{X\}\|<\\infty\}\\\{0,1\\\}^\{\\mathcal\{X\}\}\\to\\\{0,1\\\}^\{\\Omega\}, which takes the labeled training setf\|𝒳f\|\_\{\\mathcal\{X\}\}as input and returns a binary predictorA​\(f\|𝒳\)A\(f\|\_\{\\mathcal\{X\}\}\)\. The learner may be chosen with knowledge of the hypothesis classℋ\\mathcal\{H\}\.

Because the training set is indexed by a set rather than an ordered sequence,AAdoes not see the order in which sample points are revealed — a difference from online learning, where the within\-level order can itself carry information\.

###### Definition 3\(Domain complexity\)\.

Given a learnerAA, a targetf∈ℋf\\in\\mathcal\{H\}, and a hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}, the*domain complexity*ofAAonffalong𝒳¯\\bar\{\\mathcal\{X\}\}is

NA𝒳¯​\(f\):=min⁡\{i∈ℕ≥1:∀n≥i,A​\(f\|𝒳n\)=f\},N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\):=\\min\\big\\\{i\\in\\mathbb\{N\}\_\{\\geq 1\}:\\forall n\\geq i,\\;A\(f\|\_\{\\mathcal\{X\}\_\{n\}\}\)=f\\big\\\},\(2\)with value∞\\inftyif no such finiteiiexists\.

ThusNA𝒳¯​\(f\)N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)is the first level after which, for everyn≥NA𝒳¯​\(f\)n\\geq N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\), training on the observed region𝒳n\\mathcal\{X\}\_\{n\}yields a hypothesis correct on all ofΩ\\Omega, equivalently on every later and currently unobserved part of the hierarchy\.

### 2\.2Levels of Learning Goals

We distinguish the possible forms of hierarchical domain generalization by the order of the quantifiers over the learner, the target, the hierarchy, and the identifying level\. The first two criteria are hierarchy\-dependent: inA1, the identifying level may depend on both the target and the hierarchy; inA2, it may still depend on the hierarchy, but must be common to all targets in the class\.

###### Definition 4\(A1:*Non\-uniform identifiability*\)\.

ℋ\\mathcal\{H\}is*non\-uniformly identifiable*\(A1\) if there exists a learning algorithmAAwith the following property: for every targetf∈ℋf\\in\\mathcal\{H\}and every hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}, there exists a finiteNNsuch thatNA𝒳¯​\(f\)≤NN\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq N\.

A2keeps the dependence on the hierarchy but requires one level to work for all targets\.

###### Definition 5\(A2:*Target\-uniform identifiability*\)\.

ℋ\\mathcal\{H\}is*target\-uniformly identifiable*\(A2\) if there exists a learning algorithmAAwith the following property: for every hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}, there is a finiteNNsuch that, for every targetf∈ℋf\\in\\mathcal\{H\},NA𝒳¯​\(f\)≤NN\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq N\.

The remaining criteria are domain\-uniform\. UnlikeA1andA2, they require the level bound to be chosen without knowing the hierarchy, and hence without knowing the induced train/test split\. This is the hierarchy analogue of choosing a PAC sample\-size bound before the data\-generating distribution is revealed\.

###### Definition 6\(A3:*Domain\-uniform identifiability*\)\.

ℋ\\mathcal\{H\}is*domain\-uniformly identifiable*\(A3\) if there exists a learning algorithmAAwith the following property: for every targetf∈ℋf\\in\\mathcal\{H\}, there exists a finiteNNsuch that, for every hierarchy𝒳¯\\bar\{\\mathcal\{X\}\},NA𝒳¯​\(f\)≤NN\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq N\.

A3still permits target\-dependent bounds\.A4removes this last dependence: it requires a single finite level that works for all targets and all hierarchies\. In this sense,A4is the fully uniform analogue of a sample\-complexity guarantee\.

###### Definition 7\(A4:*Uniform identifiability*\)\.

ℋ\\mathcal\{H\}is*uniformly identifiable*\(A4\) if there exist a learning algorithmAAand a finiteNNwith the following property: for every targetf∈ℋf\\in\\mathcal\{H\}and every hierarchy𝒳¯\\bar\{\\mathcal\{X\}\},NA𝒳¯​\(f\)≤NN\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq N\.

## 3Exact Characterization of Domain Generalization

We now characterize the four learning goals from[Section2\.2](https://arxiv.org/html/2607.16528#S2.SS2)\.

A1: non\-uniform∃A​∀f​∀𝒳¯​∃N:NA𝒳¯​\(f\)≤N\\exists A\\,\\forall f\\,\\forall\\bar\{\\mathcal\{X\}\}\\,\\exists N:\\;N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq NA2: target\-uniform∃A​∀𝒳¯​∃N​∀f:NA𝒳¯​\(f\)≤N\\exists A\\,\\forall\\bar\{\\mathcal\{X\}\}\\,\\exists N\\,\\forall f:\\;N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq NA4: uniform∃A​∃N​∀f​∀𝒳¯:NA𝒳¯​\(f\)≤N\\exists A\\,\\exists N\\,\\forall f\\,\\forall\\bar\{\\mathcal\{X\}\}:\\;N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq Nfixed hierarchy version∃A​∃𝒳¯​∀f​∃N:NA𝒳¯​\(f\)≤N\\exists A\\,\\exists\\bar\{\\mathcal\{X\}\}\\,\\forall f\\,\\exists N:\\;N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq Nfixed hierarchy common bound∃A​∃𝒳¯​∃N​∀f:NA𝒳¯​\(f\)≤N\\exists A\\,\\exists\\bar\{\\mathcal\{X\}\}\\,\\exists N\\,\\forall f:\\;N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq NA3: domain\-uniform∃A​∀f​∃N​∀𝒳¯:NA𝒳¯​\(f\)≤N\\exists A\\,\\forall f\\,\\exists N\\,\\forall\\bar\{\\mathcal\{X\}\}:\\;N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq Ntarget\-chosen hierarchy version∃A​∀f​∃𝒳¯​∃N:NA𝒳¯​\(f\)≤N\\exists A\\,\\forall f\\,\\exists\\bar\{\\mathcal\{X\}\}\\,\\exists N:\\;N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq Nstructural conditionℋ\\mathcal\{H\}countablestructural conditionℋ\\mathcal\{H\}finitetrivial case\|Ω\|<∞\|\\Omega\|<\\infty[Definition4](https://arxiv.org/html/2607.16528#Thmdefinition4)[Definition5](https://arxiv.org/html/2607.16528#Thmdefinition5)[Definition6](https://arxiv.org/html/2607.16528#Thmdefinition6)[Definition7](https://arxiv.org/html/2607.16528#Thmdefinition7)[Theorem4](https://arxiv.org/html/2607.16528#Thmtheorem4)[Theorem7](https://arxiv.org/html/2607.16528#Thmtheorem7)[Theorem8](https://arxiv.org/html/2607.16528#Thmtheorem8)[Theorem1](https://arxiv.org/html/2607.16528#Thmtheorem1)[Theorem5](https://arxiv.org/html/2607.16528#Thmtheorem5)[Theorem8](https://arxiv.org/html/2607.16528#Thmtheorem8)Figure 1:Key characterization\.Exact characterization of when a hypothesis class allows hierarchical domain generalization at levels that may depend on the target and hierarchy \(A1\), depend on the hierarchy but are uniform over targets \(A2\), depend on the target but are uniform over hierarchies \(A3\), or are uniform over both targets and hierarchies \(A4\)\. Throughout the figure,f∈ℋf\\in\\mathcal\{H\},𝒳¯\\bar\{\\mathcal\{X\}\}ranges over hierarchies, and\|ℋ\|\>2\|\\mathcal\{H\}\|\>2\. Gray dashed arrows are formal implications, black double arrows mark substantive equivalences, and transitive arrows are omitted\.### 3\.1Non\-Uniform Domain\-Dependent Generalization

Very little, it turns out, is required for the weakest criterion\. If we settle forA1,ℋ\\mathcal\{H\}being countable is all we need\.

###### Theorem 1\(A1⇔\\LeftrightarrowCountableℋ\\mathcal\{H\}\)\.

ℋ\\mathcal\{H\}is non\-uniformly identifiable \(A1,[Definition4](https://arxiv.org/html/2607.16528#Thmdefinition4)\) if and only ifℋ\\mathcal\{H\}is countable\.

###### Proof sketch\.

Enumerateℋ\\mathcal\{H\}and letAAbe the consistent learner with this fixed tie\-breaking order: after observing a prefix, it outputs the first hypothesis in the enumeration that is consistent with the observed labels\. Forf=hmf=h\_\{m\}, each lower\-indexhjh\_\{j\}is eventually ruled out as𝒳¯\\bar\{\\mathcal\{X\}\}reveals its disagreement withff, leavinghmh\_\{m\}as the first such hypothesis\. Conversely, fix any hierarchy\. If a learner identifies every target after some finite prefix, then each target is associated with at least one finite labeled prefix on which the learner outputs it\. Since there are only countably many finite labeled prefixes,ℋ\\mathcal\{H\}must be countable\. ∎

The countability characterization is still learner\-dependent: it says that some chosen rule eventually outputs the target, not that the observed labels have ruled out every other hypothesis\. A learner may identify the target by choosing one hypothesis consistent with the observed labels while other hypotheses still agree with those labels\. The following example makes this separation explicit\.

###### Proposition 2\.

There exist a countable hypothesis classℋ\\mathcal\{H\}, a hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}, and a successful learnerAAforℋ\\mathcal\{H\}over𝒳¯\\bar\{\\mathcal\{X\}\}\(namely, for everyf∈ℋf\\in\\mathcal\{H\},NA𝒳¯​\(f\)<∞N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)<\\infty\) so that for somef∗∈ℋf^\{\*\}\\in\\mathcal\{H\}for every finite levelnn, there exists somegn∈ℋg\_\{n\}\\in\\mathcal\{H\}so thatgn\|𝒳n=f∗\|𝒳ng\_\{n\}\|\_\{\\mathcal\{X\}\_\{n\}\}=f^\{\*\}\|\_\{\\mathcal\{X\}\_\{n\}\}, and yetgn≠f∗g\_\{n\}\\neq f^\{\*\}\(namely, for somex∈Ωx\\in\\Omega,f∗​\(x\)≠gn​\(x\)f^\{\*\}\(x\)\\neq g\_\{n\}\(x\)\)\.

###### Proof sketch\.

LetΩ=ℕ\\Omega=\\mathbb\{N\}andℋ\\mathcal\{H\}contain the all\-zero function0together with the singleton indicatorshi=𝟙\{i\}h\_\{i\}=\\mathds\{1\}\_\{\\\{i\\\}\}\. Take the natural hierarchy𝒳n=\{1,…,n\}\\mathcal\{X\}\_\{n\}=\\\{1,\\ldots,n\\\}and the targetf=0f=0\. A least\-index learner that lists0first identifies0immediately, soNA𝒳¯​\(0\)<∞N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(0\)<\\infty\. But for everynnand everyj\>nj\>n, the singletonhjh\_\{j\}agrees with0on𝒳n\\mathcal\{X\}\_\{n\}\. Thus no finite prefix by itself rules out all alternatives to0\. ∎

For the class in[Section3\.1](https://arxiv.org/html/2607.16528#S3.SS1), every finite set misses some singleton hypothesis, so the target0is not finitely isolated\. More generally, finite collapse of the version space is equivalent to the existence of a finite set of domain points that separates the target from all alternatives; this existence does not depend on the ordering of the hierarchy\.

###### Proposition 3\(Finite isolation is hierarchy\-invariant\)\.

Fixf∈ℋf\\in\\mathcal\{H\}\. For a hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}, writeVℋ,n𝒳¯​\(f\):=\{g∈ℋ:g\|𝒳n=f\|𝒳n\}V\_\{\\mathcal\{H\},n\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\):=\\\{g\\in\\mathcal\{H\}:g\|\_\{\\mathcal\{X\}\_\{n\}\}=f\|\_\{\\mathcal\{X\}\_\{n\}\}\\\}for the version space aroundffat levelnn\. The following are equivalent:

1. \(i\)for some hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}, there is a finite levelnnsuch thatVℋ,n𝒳¯​\(f\)=\{f\}V\_\{\\mathcal\{H\},n\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)=\\\{f\\\};
2. \(ii\)for every hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}, there is a finite levelnnsuch thatVℋ,n𝒳¯​\(f\)=\{f\}V\_\{\\mathcal\{H\},n\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)=\\\{f\\\};
3. \(iii\)there is a finite setS⊆ΩS\\subseteq\\Omegasuch that everyg∈ℋ∖\{f\}g\\in\\mathcal\{H\}\\setminus\\\{f\\\}differs fromffon some point ofSS\.

One topological way to understand this is the following\. For a finiteS⊆ΩS\\subseteq\\Omegaandh∈ℋh\\in\\mathcal\{H\}, let\[h\]S:=\{g∈ℋ:g\|S=h\|S\}\[h\]\_\{S\}:=\\\{g\\in\\mathcal\{H\}:g\|\_\{S\}=h\|\_\{S\}\\\}be the set of hypotheses that agree withhhon the finite observation setSS\. These finite\-observation cells generate a topology onℋ\\mathcal\{H\}\. For any finite\-level hierarchy that exhaustsΩ\\Omega, the same topology is generated by the level version spacesVℋ,n𝒳¯​\(h\)V\_\{\\mathcal\{H\},n\}^\{\\bar\{\\mathcal\{X\}\}\}\(h\)\. In this topology, saying that\{f\}\\\{f\\\}is open is exactly saying that some finite observation set isolatesff, or equivalently that the version space aroundffcollapses at a finite level\.

The next theorem gives several ways of relaxing the hierarchy quantifier inA1: one may fix a hierarchy in advance, or even choose the hierarchy separately for each target\. These relaxations have the same threshold because they still ask only for target\-by\-target success\. Thus the following statements are equivalent\.

###### Theorem 4\(Equivalent conditions forA1\)\.

The following are equivalent:

1. \(i\)∃A​∀f∈ℋ​∀𝒳¯​∃N∈ℕ≥1:NA𝒳¯​\(f\)≤N\\exists A\\;\\forall f\\in\\mathcal\{H\}\\;\\forall\\bar\{\\mathcal\{X\}\}\\;\\exists N\\in\\mathbb\{N\}\_\{\\geq 1\}:\\;N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq N\(that is,ℋ\\mathcal\{H\}satisfiesA1,[Definition4](https://arxiv.org/html/2607.16528#Thmdefinition4)\);
2. \(ii\)∃A​∃𝒳¯​∀f∈ℋ​∃N∈ℕ≥1:NA𝒳¯​\(f\)≤N\\exists A\\;\\exists\\bar\{\\mathcal\{X\}\}\\;\\forall f\\in\\mathcal\{H\}\\;\\exists N\\in\\mathbb\{N\}\_\{\\geq 1\}:\\;N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq N;
3. \(iii\)∃A​∀f∈ℋ​∃𝒳¯​∃N∈ℕ≥1:NA𝒳¯​\(f\)≤N\\exists A\\;\\forall f\\in\\mathcal\{H\}\\;\\exists\\bar\{\\mathcal\{X\}\}\\;\\exists N\\in\\mathbb\{N\}\_\{\\geq 1\}:\\;N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq N;\(iv\)ℋ\\mathcal\{H\}is countable\.

### 3\.2Target\-Uniform Domain\-Dependent Generalization

A2asks for a different kind of success\. Once the hierarchy is fixed, the same prefix level must work for every target: the amount of evidence is independent of whichf∈ℋf\\in\\mathcal\{H\}generated the labels\.

###### Theorem 5\(A2⇔\\LeftrightarrowFiniteℋ\\mathcal\{H\}\)\.

ℋ\\mathcal\{H\}is target\-uniformly identifiable \(A2,[Definition5](https://arxiv.org/html/2607.16528#Thmdefinition5)\) if and only ifℋ\\mathcal\{H\}is finite\.

###### Proof sketch\.

Withℋ\\mathcal\{H\}finite, the least\-index learner from[Theorem1](https://arxiv.org/html/2607.16528#Thmtheorem1)achieves a common bound on any hierarchy:maxf∈ℋ⁡NA𝒳¯​\(f\)<∞\\max\_\{f\\in\\mathcal\{H\}\}N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)<\\infty\. Conversely, a common boundNNon a single hierarchy makes the labeled\-prefix mapf↦f\|𝒳Nf\\mapsto f\|\_\{\\mathcal\{X\}\_\{N\}\}injective onℋ\\mathcal\{H\}; otherwise two targets with the same prefix would give the learner the same input at levelNN\. Hence\|ℋ\|≤2\|𝒳N\|\|\\mathcal\{H\}\|\\leq 2^\{\|\\mathcal\{X\}\_\{N\}\|\}\. ∎

The proof isolates the mechanism behindA2: at a common level, two targets with the same prefix are indistinguishable to any learner\. The relevant quantity is therefore the first prefix that separates the class\.

###### Definition 8\(Class domain complexity\)\.

For a hypothesis classℋ\\mathcal\{H\}and a hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}, the class domain complexity is

N𝒳¯​\(ℋ\):=min⁡\{n∈ℕ≥1:∀f,g∈ℋ,f≠g⟹∃x∈𝒳n:f​\(x\)≠g​\(x\)\}\.N^\{\\bar\{\\mathcal\{X\}\}\}\(\\mathcal\{H\}\):=\\min\\\{n\\in\\mathbb\{N\}\_\{\\geq 1\}:\\forall f,g\\in\\mathcal\{H\},\\ f\\neq g\\Longrightarrow\\exists x\\in\\mathcal\{X\}\_\{n\}:f\(x\)\\neq g\(x\)\\\}\.\(3\)If no such finite level exists, setN𝒳¯​\(ℋ\):=∞N^\{\\bar\{\\mathcal\{X\}\}\}\(\\mathcal\{H\}\):=\\infty\.

###### Proposition 6\(Optimality of class domain complexity\)\.

For every hierarchy𝒳¯\\bar\{\\mathcal\{X\}\},N𝒳¯​\(ℋ\)=minA​supf∈ℋNA𝒳¯​\(f\)N^\{\\bar\{\\mathcal\{X\}\}\}\(\\mathcal\{H\}\)=\\min\_\{A\}\\sup\_\{f\\in\\mathcal\{H\}\}N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\), whereAAranges over learners and both sides take values inℕ≥1∪\{∞\}\\mathbb\{N\}\_\{\\geq 1\}\\cup\\\{\\infty\\\}\.

Thus the optimal fixed\-hierarchyA2bound is algorithm\-agnostic, and the variants below are equivalent: a common bound along one hierarchy already forcesℋ\\mathcal\{H\}to be finite, while finiteness gives a common bound along every hierarchy\.

###### Theorem 7\(Equivalent conditions forA2\)\.

The following are equivalent:

1. \(i\)∃A​∀𝒳¯​∃N∈ℕ≥1​∀f∈ℋ:NA𝒳¯​\(f\)≤N\\exists A\\;\\forall\\bar\{\\mathcal\{X\}\}\\;\\exists N\\in\\mathbb\{N\}\_\{\\geq 1\}\\;\\forall f\\in\\mathcal\{H\}:\\;N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq N\(that is,ℋ\\mathcal\{H\}satisfiesA2,[Definition5](https://arxiv.org/html/2607.16528#Thmdefinition5)\);
2. \(ii\)∃A​∃𝒳¯​∃N∈ℕ≥1​∀f∈ℋ:NA𝒳¯​\(f\)≤N\\exists A\\;\\exists\\bar\{\\mathcal\{X\}\}\\;\\exists N\\in\\mathbb\{N\}\_\{\\geq 1\}\\;\\forall f\\in\\mathcal\{H\}:\\;N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq N;
3. \(iii\)∃𝒳¯:N𝒳¯​\(ℋ\)<∞\\exists\\bar\{\\mathcal\{X\}\}:\\;N^\{\\bar\{\\mathcal\{X\}\}\}\(\\mathcal\{H\}\)<\\infty;\(iv\)∀𝒳¯:N𝒳¯​\(ℋ\)<∞\\forall\\bar\{\\mathcal\{X\}\}:\\;N^\{\\bar\{\\mathcal\{X\}\}\}\(\\mathcal\{H\}\)<\\infty;\(v\)ℋ\\mathcal\{H\}is finite\.

### 3\.3Domain\-Uniform Generalization

###### Theorem 8\(A3/A4characterization\)\.

Assume\|ℋ\|\>2\|\\mathcal\{H\}\|\>2\. The following are equivalent:

1. \(i\)ℋ\\mathcal\{H\}is uniformly identifiable \(A4,[Definition7](https://arxiv.org/html/2607.16528#Thmdefinition7)\);
2. \(ii\)ℋ\\mathcal\{H\}is domain\-uniformly identifiable \(A3,[Definition6](https://arxiv.org/html/2607.16528#Thmdefinition6)\);
3. \(iii\)Ω\\Omegais finite\.

###### Proof sketch\.

*\(i\) implies \(ii\)\.*This is immediate\.*\(iii\) implies \(i\)\.*IfΩ\\Omegais finite, then every hierarchy reveals all ofΩ\\Omegaby level\|Ω\|\|\\Omega\|\. At that level the observed labels determine the target on the entire domain\. A learner that outputs the unique hypothesis inℋ\\mathcal\{H\}consistent with the full\-domain labels identifies every target under every hierarchy by level\|Ω\|\|\\Omega\|\.

*\(ii\) implies \(iii\)\.*SupposeA3holds through a learnerAAand target\-dependent levels\(Nf\)f∈ℋ\(N\_\{f\}\)\_\{f\\in\\mathcal\{H\}\}\. If two distinct hypothesesf,gf,gagreed on at leastM=max⁡\{Nf,Ng\}M=\\max\\\{N\_\{f\},N\_\{g\}\\\}points, choose a finite setS⊆\{f=g\}S\\subseteq\\\{f=g\\\}of sizeMMand a hierarchy with𝒳M=S\\mathcal\{X\}\_\{M\}=S\. Sincef\|S=g\|Sf\|\_\{S\}=g\|\_\{S\}, the learner receives the same input under both targets at levelMM, butA3requires the same output to equal bothffandgg, a contradiction\. Hence every pairwise agreement set is finite\.

Since\|ℋ\|\>2\|\\mathcal\{H\}\|\>2, choose three distinct hypothesesh1,h2,h3∈ℋh\_\{1\},h\_\{2\},h\_\{3\}\\in\\mathcal\{H\}\. Write\{hi=hj\}:=\{x∈Ω:hi​\(x\)=hj​\(x\)\}\\\{h\_\{i\}=h\_\{j\}\\\}:=\\\{x\\in\\Omega:h\_\{i\}\(x\)=h\_\{j\}\(x\)\\\}\. At eachx∈Ωx\\in\\Omega, two of the three binary labels must agree, so

\{h1=h2\}∪\{h1=h3\}∪\{h2=h3\}=Ω\.\\\{h\_\{1\}=h\_\{2\}\\\}\\,\\cup\\,\\\{h\_\{1\}=h\_\{3\}\\\}\\,\\cup\\,\\\{h\_\{2\}=h\_\{3\}\\\}\\,=\\,\\Omega\.\(4\)The three sets on the left are finite by the previous paragraph\. HenceΩ\\Omegais finite\. ∎

Under the standing assumption of this paper,Ω\\Omegais countably infinite\. Thus for every class with\|ℋ\|\>2\|\\mathcal\{H\}\|\>2, bothA3andA4are impossible\. The only remaining cases are degenerate\. Singleton classes are trivial\. For a two\-element classℋ=\{h,g\}\\mathcal\{H\}=\\\{h,g\\\}, domain\-uniform \(A3\), equivalently uniform \(A4\), identification is possible exactly whenhhandggagree on only finitely many points: then any sufficiently large observed region contains a point where they differ, and the label at that point identifies the target\.

#### Why Domain Generalization Is Hard\.

The obstruction above is not a usual PAC\-learning obstruction from VC dimension, class size, or agnostic noise\. It comes from the train/test partition itself\. The useful way to read the obstruction is adversarial:

SupposeΩ\\Omegais infinite and take any three distinct hypothesesh1,h2,h3∈ℋh\_\{1\},h\_\{2\},h\_\{3\}\\in\\mathcal\{H\}\. Then some pair must agree on infinitely many points\. Indeed, if both\{h1=h2\}\\\{h\_\{1\}=h\_\{2\}\\\}and\{h1=h3\}\\\{h\_\{1\}=h\_\{3\}\\\}are finite, then their union is finite, so on infinitely many pointsh2h\_\{2\}andh3h\_\{3\}both take the binary label opposite toh1h\_\{1\}\. Hence\{h2=h3\}\\\{h\_\{2\}=h\_\{3\}\\\}is infinite\. Thus, from any class with\|ℋ\|\>2\|\\mathcal\{H\}\|\>2, an adversary can choose two distinct hypothesesf,gf,gwith an infinite agreement set and place arbitrarily many of those agreement points at the beginning of the hierarchy\. On any such prefixS⊆\{f=g\}S\\subseteq\\\{f=g\\\}, the learner receives the same labeled training set under the two possible targets\. Whatever it outputs on that input, at least one offfandggis not identified\.

## 4Stratified Domain Complexity

The characterizations above are qualitative: finite classes admit target\-uniform bounds along a fixed hierarchy, while infinite classes do not\. To study infinite model families quantitatively, we stratify them by model complexity and ask how the best bound grows with the allowed complexity\.

#### Complexity Sublevels\.

A natural refinement is to keep track of model complexity\. Many representation classes of interest are not just infinite sets of functions: programs, automata, grammars, and implemented neural\-network families come with finite descriptions or size parameters, such as description length,222For a prefix\-code description length, Kraft’s inequality implies that only finitely many descriptions have code length at most any fixedss\. We use only this finite\-slice consequence, not an MDL or probabilistic argument\.program length, number of states, grammar size, depth, width, or number of parameters\. Such a scalec:ℋ→ℕc:\\mathcal\{H\}\\to\\mathbb\{N\}organizes the class into bounded\-complexity slices\.

We now formalize this fixed\-hierarchy quantity\. Fix a hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}onΩ\\Omega, a hypothesis classℋ⊆\{0,1\}Ω\\mathcal\{H\}\\subseteq\\\{0,1\\\}^\{\\Omega\}, and a model\-complexity functionc:ℋ→ℕc:\\mathcal\{H\}\\to\\mathbb\{N\}\. Fors∈ℕs\\in\\mathbb\{N\}, the*sublevel class*of model complexity at mostssis

ℋ≤sc:=\{f∈ℋ:c​\(f\)≤s\}\.\\mathcal\{H\}\_\{\\leq s\}^\{c\}:=\\\{f\\in\\mathcal\{H\}:c\(f\)\\leq s\\\}\.\(5\)Throughout this section, we consider complexity scales whose sublevels are finite and exhaustive:

\|ℋ≤sc\|<∞​for every​s∈ℕ,⋃s∈ℕℋ≤sc=ℋ\.\|\\mathcal\{H\}\_\{\\leq s\}^\{c\}\|<\\infty\\ \\text\{ for every \}s\\in\\mathbb\{N\},\\qquad\\bigcup\_\{s\\in\\mathbb\{N\}\}\\mathcal\{H\}\_\{\\leq s\}^\{c\}=\\mathcal\{H\}\.\(6\)

#### Sublevel Bounds\.

Abstractly, every countable class admits such a stratification by enumeration\. In applications, however, the scaleccis chosen because it reflects a representation of the hypotheses\. The quantity of interest is the best target\-uniform bound on each sublevel class\.

###### Definition 9\(Sublevel domain complexity\)\.

The*sublevel domain complexity*of\(ℋ,c\)\(\\mathcal\{H\},c\)along𝒳¯\\bar\{\\mathcal\{X\}\}is the functionN\(ℋ,c\)𝒳¯:ℕ→ℕ≥1∪\{∞\}N\_\{\(\\mathcal\{H\},c\)\}^\{\\bar\{\\mathcal\{X\}\}\}:\\mathbb\{N\}\\to\\mathbb\{N\}\_\{\\geq 1\}\\cup\\\{\\infty\\\}defined by

N\(ℋ,c\)𝒳¯​\(s\):=N𝒳¯​\(ℋ≤sc\)=min⁡\{i∈ℕ≥1:∀h≠h′∈ℋ≤sc,∃x∈𝒳i​s\.t\.​h​\(x\)≠h′​\(x\)\}\.\\displaystyle N\_\{\(\\mathcal\{H\},c\)\}^\{\\bar\{\\mathcal\{X\}\}\}\(s\)=N^\{\\bar\{\\mathcal\{X\}\}\}\(\\mathcal\{H\}\_\{\\leq s\}^\{c\}\)=\\min\\big\\\{i\\in\\mathbb\{N\}\_\{\\geq 1\}:\\forall h\\neq h^\{\\prime\}\\in\\mathcal\{H\}\_\{\\leq s\}^\{c\},\\ \\exists x\\in\\mathcal\{X\}\_\{i\}\\text\{ s\.t\. \}h\(x\)\\neq h^\{\\prime\}\(x\)\\big\\\}\.\(7\)If no suchiiexists, setN\(ℋ,c\)𝒳¯​\(s\):=∞N\_\{\(\\mathcal\{H\},c\)\}^\{\\bar\{\\mathcal\{X\}\}\}\(s\):=\\infty\.

Under the finite\-sublevel assumption, each sublevel class has some finite target\-uniform identifying level along the fixed hierarchy\. The next result shows that the smallest possible such bound is exactly the sublevel domain complexity just defined\.

###### Theorem 9\(Sublevel domain complexity is the optimal rate\)\.

Fix a hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}, a classℋ⊆\{0,1\}Ω\\mathcal\{H\}\\subseteq\\\{0,1\\\}^\{\\Omega\}, and a complexity scalec:ℋ→ℕc:\\mathcal\{H\}\\to\\mathbb\{N\}satisfying[Equation6](https://arxiv.org/html/2607.16528#S4.E6)\. Then, for everys∈ℕs\\in\\mathbb\{N\}withℋ≤sc≠∅\\mathcal\{H\}\_\{\\leq s\}^\{c\}\\neq\\emptyset,

N\(ℋ,c\)𝒳¯​\(s\)=minA​supf∈ℋ≤scNA𝒳¯​\(f\),N\_\{\(\\mathcal\{H\},c\)\}^\{\\bar\{\\mathcal\{X\}\}\}\(s\)=\\min\_\{A\}\\sup\_\{f\\in\\mathcal\{H\}\_\{\\leq s\}^\{c\}\}N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\),\(8\)whereAAranges over learners\. If, in addition,\|ℋ≤sc\|→∞\|\\mathcal\{H\}\_\{\\leq s\}^\{c\}\|\\to\\inftyass→∞s\\to\\infty, thenN\(ℋ,c\)𝒳¯​\(s\)→∞N\_\{\(\\mathcal\{H\},c\)\}^\{\\bar\{\\mathcal\{X\}\}\}\(s\)\\to\\infty\.

Thus finite sublevels give the qualitative guarantee, while[Theorem9](https://arxiv.org/html/2607.16528#Thmtheorem9)identifies the best possible target\-uniform bound at each complexity level\. When the sublevel classes grow, these bounds must also diverge\. The remaining interesting question is how fast the sublevel domain complexity function grows\.

## 5Length Generalization as a Case Study

Length generalization is the fixed\-hierarchy case in which the hierarchy is ordered by input length and the quantitative question is how sublevel domain complexity grows with model complexity\.

Concretely, length generalization asks whether a model trained on short inputs succeeds on longer inputs\. This question is especially visible for Transformers\(Vaswaniet al\.,[2017](https://arxiv.org/html/2607.16528#bib.bib43)\)trained on algorithmic tasks, where models can fit all short instances yet fail sharply on longer ones\(Anilet al\.,[2022](https://arxiv.org/html/2607.16528#bib.bib226); Leeet al\.,[2024](https://arxiv.org/html/2607.16528#bib.bib227); Zhouet al\.,[2024](https://arxiv.org/html/2607.16528#bib.bib85)\)\.

###### Definition 10\(Length hierarchy\)\.

Formally, fix a finite alphabetΣ\\Sigmaand consider the hierarchy

Ω:=Σ\+,Σ¯:=\(Σ≤N\)N≥0,Σ≤0:=∅,Σ≤N:=Σ∪Σ2∪⋯∪ΣN\(N≥1\)\.\\Omega:=\\Sigma^\{\+\},\\qquad\\bar\{\\Sigma\}:=\(\\Sigma^\{\\leq N\}\)\_\{N\\geq 0\},\\qquad\\Sigma^\{\\leq 0\}:=\\emptyset,\\qquad\\Sigma^\{\\leq N\}:=\\Sigma\\cup\\Sigma^\{2\}\\cup\\cdots\\cup\\Sigma^\{N\}\\quad\(N\\geq 1\)\.\(9\)A learner trained on lengths at mostNNobserves all labels onΣ≤N\\Sigma^\{\\leq N\}and is evaluated on all ofΣ\+\\Sigma^\{\+\}\. Thus length generalization is exact identification under the fixed cumulative hierarchyΣ¯\\bar\{\\Sigma\}\.

We write the representation class asℋ⊆\{0,1\}Σ\+\\mathcal\{H\}\\subseteq\\\{0,1\\\}^\{\\Sigma^\{\+\}\}\.333The binary\-valued language notation is only for convenience; the same setup extends directly to finite\-output maps such as functionsΣ∗→Σ\\Sigma^\{\*\}\\to\\Sigma\.Hereℋ\\mathcal\{H\}may be a class of languages, programs, or Transformer\-realizable predictors, andccmay encode description length, program size, Transformer depth, number of heads, parameter precision, norm bounds, or related architectural parameters\. The quantitative content of non\-asymptotic length generalization lies in estimating the growth ofN\(ℋ,c\)Σ¯​\(s\)N\_\{\(\\mathcal\{H\},c\)\}^\{\\bar\{\\Sigma\}\}\(s\)for concrete choices of\(ℋ,c\)\(\\mathcal\{H\},c\)\.

#### Existing Results\.

Huanget al\.\([2025](https://arxiv.org/html/2607.16528#bib.bib113)\)give a qualitative fixed\-hierarchy, target\-wise guarantee for Transformer length generalization: under an idealized regularized inference procedure, targets in their Limit\-Transformer class are eventually identified alongΣ¯\\bar\{\\Sigma\}\. This does not estimate a sublevel domain\-complexity growth rate\.

More quantitatively,Chenet al\.\([2025](https://arxiv.org/html/2607.16528#bib.bib114)\)estimate this sublevel domain complexity for several representation classes\. For DFAs, the model class is regular languages and the complexity measure is the number of states; their bound is2​q−22q\-2for targets recognized by DFAs with at mostqqstates\. For linear CFGs, the complexity measure is grammar description size, and the analogous sublevel bound has no computable upper bound in that size\. For restricted C\-RASP,444C\-RASP programs compile to softmax Transformers\(Yang and Chiang,[2024](https://arxiv.org/html/2607.16528#bib.bib112)\); hence C\-RASP gives a programmable lower bound on softmax\-Transformer expressivity and is often used as a proxy for studying Transformer expressiveness\.the relevant parameters are precisionTTin the one\-layer Transformer setting, and precisionTTtogether withKKheads in the two\-layer setting; the resulting bounds areO​\(T2\)O\(T^\{2\}\)andO​\(TO​\(K\)\)O\(T^\{O\(K\)\}\), respectively\.

Later work continues the same calculation for more Transformer\-facing classes\.Yanget al\.\([2026a](https://arxiv.org/html/2607.16528#bib.bib115)\)study the same sublevel domain\-complexity function for C\-RASP, proving uncomputability for full C\-RASP and tight exponential growth for positive C\-RASP\.Izzoet al\.\([2026](https://arxiv.org/html/2607.16528#bib.bib116)\)move to an approximate analogue: exact identification is replaced by approximate agreement on all longer inputs, with bounds in terms of norms, locality, periodicity, precision, and margins\.

#### Beyond Length\.

The preceding results all concern the fixed length hierarchyΣ¯\\bar\{\\Sigma\}\. The uncomputability statements in this literature should not be interpreted as a peculiarity of ordering strings by length\. The obstruction can already come from the representation ofℋ\\mathcal\{H\}: if semantic equivalence of descriptions is undecidable, then the sublevel domain\-complexity function has no computable upper bound in the complexity parameterss\.

To discuss computability, we use a represented class: a finite descriptionp∈Πp\\in\\Pidenotes a computable hypothesishp:Ω→\{0,1\}h\_\{p\}:\\Omega\\to\\\{0,1\\\}, andκ:Π→ℕ\\kappa:\\Pi\\to\\mathbb\{N\}is a computable complexity scale on descriptions\. For a complexity boundssand hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}, write

ℋ≤sΠ,κ:=\{hp:p∈Π,κ​\(p\)≤s\},N\(Π,κ\)𝒳¯​\(s\):=N𝒳¯​\(ℋ≤sΠ,κ\)\.\\mathcal\{H\}\_\{\\leq s\}^\{\\Pi,\\kappa\}:=\\\{h\_\{p\}:p\\in\\Pi,\\ \\kappa\(p\)\\leq s\\\},\\qquad N\_\{\(\\Pi,\\kappa\)\}^\{\\bar\{\\mathcal\{X\}\}\}\(s\):=N^\{\\bar\{\\mathcal\{X\}\}\}\(\\mathcal\{H\}\_\{\\leq s\}^\{\\Pi,\\kappa\}\)\.\(10\)The quantity on the right is still the information\-theoretic domain complexity from[Definition9](https://arxiv.org/html/2607.16528#Thmdefinition9)\. A hierarchy is computable if its finite levels can be listed, and two descriptions are semantically equivalent if their denoted hypotheses agree on all ofΩ\\Omega\.

###### Proposition 10\(Computability obstruction\)\.

If semantic equivalence is undecidable for descriptions inΠ\\Pi, then for every computable exhaustive hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}onΩ\\Omega, there is no computable functionB:ℕ→ℕB:\\mathbb\{N\}\\to\\mathbb\{N\}such that

N\(Π,κ\)𝒳¯​\(s\)≤B​\(s\)for all​s∈ℕ,N\_\{\(\\Pi,\\kappa\)\}^\{\\bar\{\\mathcal\{X\}\}\}\(s\)\\leq B\(s\)\\qquad\\text\{for all \}s\\in\\mathbb\{N\},\(11\)

For classes such as linear CFGs, this recovers the absence of a computable non\-asymptotic bound alongΣ¯\\bar\{\\Sigma\}shown byChenet al\.\([2025](https://arxiv.org/html/2607.16528#bib.bib114)\), and holds for any computable exhaustive hierarchy\. The computability requirement on the hierarchy is essential: without it, the hierarchy itself can encode the finite witnesses that separate the relevant hypotheses\.

###### Proposition 11\(Necessity of computability\)\.

LetΩ\\Omegabe countably infinite, and letℋ=\{h1,h2,…\}⊆\{0,1\}Ω\\mathcal\{H\}=\\\{h\_\{1\},h\_\{2\},\\ldots\\\}\\subseteq\\\{0,1\\\}^\{\\Omega\}be countable\. There exists an exhaustive hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}such thatN𝒳¯​\(\{h1,…,hm\}\)≤mN^\{\\bar\{\\mathcal\{X\}\}\}\(\\\{h\_\{1\},\\ldots,h\_\{m\}\\\}\)\\leq mfor allm≥1m\\geq 1\.

Thus, for a complexity scaleccwith finite sublevels, if the enumeration is ordered so thatℋ≤sc⊆\{h1,…,hb​\(s\)\}\\mathcal\{H\}\_\{\\leq s\}^\{c\}\\subseteq\\\{h\_\{1\},\\ldots,h\_\{b\(s\)\}\\\}for some computablebb, the same hierarchy givesN\(ℋ,c\)𝒳¯​\(s\)≤b​\(s\)N\_\{\(\\mathcal\{H\},c\)\}^\{\\bar\{\\mathcal\{X\}\}\}\(s\)\\leq b\(s\)for allss\. Hence the computability assumption in[Section5](https://arxiv.org/html/2607.16528#S5.SS0.SSS0.Px2)is essential\.

Together, these observations separate two sources of difficulty\. The computability obstruction above shows that non\-computable rates can arise from the effective description ofℋ\\mathcal\{H\}itself, provided the hierarchy is computable\. The next section concerns the other source: even with\(ℋ,c\)\(\\mathcal\{H\},c\)fixed, the growth of the sublevel domain complexity need not be determined by this pair alone\.

## 6No Free Lunch for Domain Generalization

The preceding sections give meaningful quantitative notions once a hierarchy is fixed\. For a target, a learner has an identification levelNA𝒳¯​\(f\)N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\); for a finite class,N𝒳¯​\(ℋ\)N^\{\\bar\{\\mathcal\{X\}\}\}\(\\mathcal\{H\}\)is the optimal target\-uniform bound; and for a complexity scalecc,N\(ℋ,c\)𝒳¯​\(s\)N\_\{\(\\mathcal\{H\},c\)\}^\{\\bar\{\\mathcal\{X\}\}\}\(s\)is the corresponding optimal bound on the sublevel classℋ≤sc\\mathcal\{H\}\_\{\\leq s\}^\{c\}\. All three are defined relative to the hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}\.

This dependence is essential\.[Theorem8](https://arxiv.org/html/2607.16528#Thmtheorem8)already shows that, for classes with\|ℋ\|\>2\|\\mathcal\{H\}\|\>2, domain generalization uniformly over all hierarchies is possible only in the finite\-domain case\. We now formalize the same dependence as a no\-free\-lunch result: over an infinite domain, changing the hierarchy alone can make each of the fixed\-hierarchy quantities above arbitrarily large\.

#### Class\-Level Bounds\.

We first ask this question before adding a complexity scale\.

###### Theorem 12\(No free lunch for domain generalization\)\.

LetΩ\\Omegabe countably infinite\. For anyℋ⊆\{0,1\}Ω\\mathcal\{H\}\\subseteq\\\{0,1\\\}^\{\\Omega\}with\|ℋ\|\>2\|\\mathcal\{H\}\|\>2and everyM∈ℕ≥1M\\in\\mathbb\{N\}\_\{\\geq 1\}, there exists a hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}, even one revealing a single new point at each level, such that, for every learnerAA, there exists a targeth∈ℋh\\in\\mathcal\{H\}with

NA𝒳¯​\(h\)\>M\.N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(h\)\>M\.\(12\)Whenℋ\\mathcal\{H\}is finite, this is equivalent to the class\-domain\-complexity statement that, for everyM∈ℕ≥1M\\in\\mathbb\{N\}\_\{\\geq 1\}, there exists a hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}such thatN𝒳¯​\(ℋ\)\>MN^\{\\bar\{\\mathcal\{X\}\}\}\(\\mathcal\{H\}\)\>M\.

Equivalently, the theorem can be read as a train/test no\-free\-lunch statement\. Fix any hypothesis classℋ\\mathcal\{H\}with\|ℋ\|\>2\|\\mathcal\{H\}\|\>2, no matter how small, and fix any desired training sizeMM, no matter how large\. There exists a partitionΩ=𝒳tr⊔𝒳te\\Omega=\\mathcal\{X\}\_\{\\mathrm\{tr\}\}\\sqcup\\mathcal\{X\}\_\{\\mathrm\{te\}\}with\|𝒳tr\|=M\|\\mathcal\{X\}\_\{\\mathrm\{tr\}\}\|=Msuch that no learner succeeds uniformly for every target\. This does not contradict the fixed\-hierarchy characterizations: countability gives target\-wise existence, and finiteness gives target\-uniform existence, after𝒳¯\\bar\{\\mathcal\{X\}\}is fixed\. The theorem says that changing𝒳¯\\bar\{\\mathcal\{X\}\}can push the required level past any prescribedMM\.

#### Complexity\-Stratified Bounds\.

The same question can be asked after stratifying the class by complexity\. Once𝒳¯\\bar\{\\mathcal\{X\}\}is fixed, finite sublevel classes give well\-defined optimal target\-uniform boundsN\(ℋ,c\)𝒳¯​\(s\)N\_\{\(\\mathcal\{H\},c\)\}^\{\\bar\{\\mathcal\{X\}\}\}\(s\)\. Can the growth of this function be controlled by\(ℋ,c\)\(\\mathcal\{H\},c\)alone?

###### Corollary 13\(Complexity\-stratified no free lunch\)\.

LetΩ\\Omegabe countably infinite, letℋ⊆\{0,1\}Ω\\mathcal\{H\}\\subseteq\\\{0,1\\\}^\{\\Omega\}be countably infinite, and letc:ℋ→ℕc:\\mathcal\{H\}\\to\\mathbb\{N\}have finite sublevel classes\. For every nondecreasingB:ℕ→ℕ≥1B:\\mathbb\{N\}\\to\\mathbb\{N\}\_\{\\geq 1\}withB​\(s\)→∞B\(s\)\\to\\infty, there exist a hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}onΩ\\Omegaands0∈ℕs\_\{0\}\\in\\mathbb\{N\}such that, for everys≥s0s\\geq s\_\{0\},

N\(ℋ,c\)𝒳¯​\(s\)\>B​\(s\)\.N\_\{\(\\mathcal\{H\},c\)\}^\{\\bar\{\\mathcal\{X\}\}\}\(s\)\>B\(s\)\.\(13\)

The key point is quantitative: with\(ℋ,c\)\(\\mathcal\{H\},c\)fixed, changing the domain hierarchy can make the sublevel domain\-complexity function grow faster than any prescribed unbounded rateBB\. In particular, for some hierarchy, this function has no computable upper bound\.

For length generalization, the hierarchy is the length hierarchyΣ¯\\bar\{\\Sigma\}from[Definition10](https://arxiv.org/html/2607.16528#Thmdefinition10)\. A bound for a Transformer\-realizable class under this hierarchy is therefore a statement about training on all strings up to a given length and testing on longer strings\. It does not automatically imply the corresponding bound for the same Transformer architecture and the same precision scale under another hierarchy onΣ\+\\Sigma^\{\+\}, for example one ordered by reasoning\-trajectory length, recursion depth, theorem difficulty, or planning horizon\. The corollary says that such a replacement can make the bound arbitrarily large, even noncomputably so\.

#### Comparison with Classical NFL\.

Classical learning\-theoretic no\-free\-lunch theorems are usually read as warnings about hypothesis classes\(Shalev\-Shwartz and Ben\-David,[2014](https://arxiv.org/html/2607.16528#bib.bib9)\)\. If the learner is asked to compete with all possible labelings, there is no structure to exploit and no uniform generalization theorem to be had\. Our result moves the warning to a second object that is often kept offstage: the structure connecting what is in domain to what is out of domain\. Fixing the hypothesis class is therefore not enough\. A domain\-generalization statement also needs to say what makes the observed part informative about the unobserved part\. Counting hypotheses alone is therefore not enough\.

Therefore, domain\-generalization guarantees cannot be characterized by the concept class alone\. They must be properties of the pair\(ℋ,𝒳¯\)\(\\mathcal\{H\},\\bar\{\\mathcal\{X\}\}\): the hypotheses together with the hierarchy that determines how observed regions are related to unobserved ones\.

## 7Extended Discussions

We consider four extensions: online mistake bounds, approximate prediction, distributional support mismatch, and positive\-only presentations\.

### 7\.1Online Learning

Online learning keeps the same hierarchy, but replaces the identifying level by a mistake count\. Before levelnnis revealed, the prediction rule has observed the labels on𝒳n−1\\mathcal\{X\}\_\{n\-1\}and must predict the labels on the new incrementΔn=𝒳n∖𝒳n−1\\Delta\_\{n\}=\\mathcal\{X\}\_\{n\}\\setminus\\mathcal\{X\}\_\{n\-1\}\. We count one mistake at levelnnif any of these predictions is wrong\.

This is weaker than identification\. It counts errors only when they are exposed on a newly revealed increment; identification asks whether the labels already observed determine the target on all ofΩ\\Omega\.

As in[Definition2](https://arxiv.org/html/2607.16528#Thmdefinition2), the online prediction rule may output an arbitrary binary predictor in\{0,1\}Ω\\\{0,1\\\}^\{\\Omega\}, not necessarily an element ofℋ\\mathcal\{H\}\.

###### Definition 11\(Uniform mistake bound\)\.

For an online prediction ruleAA, targetf∈ℋf\\in\\mathcal\{H\}, and hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}, define the*mistake count*

MA​\(f,𝒳¯\):=∑n≥1𝟏​\[A​\(f\|𝒳n−1\)\|𝒳n∖𝒳n−1≢f\|𝒳n∖𝒳n−1\],M\_\{A\}\(f,\\bar\{\\mathcal\{X\}\}\):=\\sum\_\{n\\geq 1\}\\mathbf\{1\}\\\!\\left\[A\(f\|\_\{\\mathcal\{X\}\_\{n\-1\}\}\)\|\_\{\\mathcal\{X\}\_\{n\}\\setminus\\mathcal\{X\}\_\{n\-1\}\}\\not\\equiv f\|\_\{\\mathcal\{X\}\_\{n\}\\setminus\\mathcal\{X\}\_\{n\-1\}\}\\right\],\(14\)where𝒳0=∅\\mathcal\{X\}\_\{0\}=\\emptyset\. We sayℋ\\mathcal\{H\}admits a*uniform mistake bound*if there exist an online prediction ruleAAand a finiteM∈ℕM\\in\\mathbb\{N\}such thatMA​\(f,𝒳¯\)≤MM\_\{A\}\(f,\\bar\{\\mathcal\{X\}\}\)\\leq Mfor everyf∈ℋf\\in\\mathcal\{H\}and every hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}\.

LetLdim⁡\(ℋ\)\\operatorname\{Ldim\}\(\\mathcal\{H\}\)denote the Littlestone dimension ofℋ\\mathcal\{H\}, namely the supremum of the depths of complete binary trees shattered byℋ\\mathcal\{H\}\. The classical mistake\-bound theorem ofLittlestone \([1988](https://arxiv.org/html/2607.16528#bib.bib211)\)applies to the criterion above\.

###### Theorem 14\(Littlestone’s mistake\-bound theorem\)\.

ℋ\\mathcal\{H\}admits a uniform mistake bound if and only ifLdim⁡\(ℋ\)<∞\\operatorname\{Ldim\}\(\\mathcal\{H\}\)<\\infty\. Moreover, the optimal mistake bound is exactlyLdim⁡\(ℋ\)\\operatorname\{Ldim\}\(\\mathcal\{H\}\)\.

Thus Littlestone dimension controls the number of mistaken revealed increments\. It does not control the level at which the target has been identified\.

#### From Mistakes to Identification\.

The mistake\-bound theorem is uniform over both targets and hierarchies, just asA4is\. The difference is what the bound promises:A4gives a level after which the target has been identified, while a mistake bound only limits how many revealed increments can be predicted incorrectly\. The next proposition places this online criterion between the finite and countable cases characterized in[Section3](https://arxiv.org/html/2607.16528#S3)\.

###### Proposition 15\(Intermediate mistake complexity\)\.

AssumeΩ\\Omegais countable\. Then

\|ℋ\|<∞⟹Ldim⁡\(ℋ\)<∞⟹ℋ​is countable\.\|\\mathcal\{H\}\|<\\infty\\quad\\Longrightarrow\\quad\\operatorname\{Ldim\}\(\\mathcal\{H\}\)<\\infty\\quad\\Longrightarrow\\quad\\mathcal\{H\}\\text\{ is countable\}\.\(15\)

Thus, over a countable domain, finite Littlestone dimension sits between finiteness and countability\. The same counting argument extends to any infinite domain: ifLdim⁡\(ℋ\)=d<∞\\operatorname\{Ldim\}\(\\mathcal\{H\}\)=d<\\infty, then\|ℋ\|≤\|Ω\|\|\\mathcal\{H\}\|\\leq\|\\Omega\|\. Fix a well\-order ofΩ\\Omegaand run a bounded\-mistake learner; each target is determined by its at\-most\-ddmistake locations\. Since an infiniteΩ\\Omegahas only\|Ω\|\|\\Omega\|subsets of size at mostdd, the bound follows\.

Combining[Section7\.1](https://arxiv.org/html/2607.16528#S7.SS1.SSS0.Px1)with[Theorems5](https://arxiv.org/html/2607.16528#Thmtheorem5),[14](https://arxiv.org/html/2607.16528#Thmtheorem14)and[1](https://arxiv.org/html/2607.16528#Thmtheorem1)gives

A2⟹uniform mistake bound⟹A1\.\\textbf\{A2\}\\quad\\Longrightarrow\\quad\\text\{uniform mistake bound\}\\quad\\Longrightarrow\\quad\\textbf\{A1\}\.\(16\)Thus online learning is weaker than target\-uniform identification, even when the same mistake bound must work for every hierarchy\. A mistake bound controls how many times disagreement can be revealed as error, but not how long the hierarchy can postpone the first point that distinguishes the remaining possible targets\.

###### Example 1\(One mistake does not imply target\-uniform identification\)\.

LetΩ=\{x1,x2,…\}\\Omega=\\\{x\_\{1\},x\_\{2\},\\ldots\\\}and consider the class of singleton indicators

ℋsing:=\{hi:i≥1\},hi​\(xj\)=𝟏​\[i=j\]\.\\mathcal\{H\}\_\{\\mathrm\{sing\}\}:=\\\{h\_\{i\}:i\\geq 1\\\},\\qquad h\_\{i\}\(x\_\{j\}\)=\\mathbf\{1\}\[i=j\]\.\(17\)ThenLdim⁡\(ℋsing\)=1\\operatorname\{Ldim\}\(\\mathcal\{H\}\_\{\\mathrm\{sing\}\}\)=1, butℋsing\\mathcal\{H\}\_\{\\mathrm\{sing\}\}does not satisfyA2\.

For this class, online prediction is easy: predict zero until the unique positive point appears\. At most one mistake is possible\. Identification is different\. Along the natural hierarchy𝒳N=\{x1,…,xN\}\\mathcal\{X\}\_\{N\}=\\\{x\_\{1\},\\ldots,x\_\{N\}\\\}, all targetshih\_\{i\}withi\>Ni\>Nhave the same all\-zero labels at levelNN\. Thus no common finite level can force the learner to know which singleton target is correct\.

### 7\.2Approximation

A second comparison keeps the hierarchy but weakens exact identification to smallPP\-error\. So far, success meant exact identification: after some level, the learner must recover the target on all ofΩ\\Omega\. Here we only ask for small error under a fixed evaluation distribution\. The question is whether the hierarchy\-uniform impossibility from exact identification persists under this weaker requirement\.

Fix a distributionPPonΩ\\Omega\. For a targetf∈ℋf\\in\\mathcal\{H\}and predictorh∈\{0,1\}Ωh\\in\\\{0,1\\\}^\{\\Omega\}, thePP\-error ofhhrelative toffis

LP,f​\(h\):=P​\(\{x∈Ω:h​\(x\)≠f​\(x\)\}\)\.L\_\{P,f\}\(h\):=P\(\\\{x\\in\\Omega:h\(x\)\\neq f\(x\)\\\}\)\.\(18\)
###### Definition 12\(ε\\varepsilon\-approximate domain complexity\)\.

Forε\>0\\varepsilon\>0, learnerAA, hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}, evaluation distributionPP, and targetf∈ℋf\\in\\mathcal\{H\}, define

NA,ε𝒳¯,P​\(f\):=min⁡\{i∈ℕ≥1:∀n≥i,LP,f​\(A​\(f\|𝒳n\)\)≤ε\},N\_\{A,\\varepsilon\}^\{\\bar\{\\mathcal\{X\}\},P\}\(f\):=\\min\\\{i\\in\\mathbb\{N\}\_\{\\geq 1\}:\\forall n\\geq i,\\;L\_\{P,f\}\(A\(f\|\_\{\\mathcal\{X\}\_\{n\}\}\)\)\\leq\\varepsilon\\\},\(19\)with value∞\\inftyif no such finiteiiexists\. This is the first level after which every later predictor hasPP\-error at mostε\\varepsilon\.

For a fixed hierarchy, approximation has a simple tail\-mass guarantee: every consistent learner satisfies

LP,f​\(A​\(f\|𝒳n\)\)≤P​\(Ω∖𝒳n\)\.L\_\{P,f\}\(A\(f\|\_\{\\mathcal\{X\}\_\{n\}\}\)\)\\leq P\(\\Omega\\setminus\\mathcal\{X\}\_\{n\}\)\.\(20\)Because the hierarchy is exhaustive,P​\(Ω∖𝒳n\)→0P\(\\Omega\\setminus\\mathcal\{X\}\_\{n\}\)\\to 0\. Thus fixed\-hierarchy approximation does not require any combinatorial structure ofℋ\\mathcal\{H\}\. The nontrivial question is whether one can choose a level bound before the hierarchy is known\. Say thatPPhas full support ifP​\(x\)\>0P\(x\)\>0for everyx∈Ωx\\in\\Omega\. Then every disagreement between distinct hypotheses has positivePP\-mass: ifu≠vu\\neq v, thenP​\(\{u≠v\}\)\>0P\(\\\{u\\neq v\\\}\)\>0\.

###### Proposition 16\(Approximate no free lunch over hierarchies\)\.

LetΩ\\Omegabe countably infinite, letPPhave full support onΩ\\Omega, and letℋ⊆\{0,1\}Ω\\mathcal\{H\}\\subseteq\\\{0,1\\\}^\{\\Omega\}have\|ℋ\|\>2\|\\mathcal\{H\}\|\>2\. Then there existsε\>0\\varepsilon\>0such that, for everyM∈ℕ≥1M\\in\\mathbb\{N\}\_\{\\geq 1\}, there is a hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}for which every learnerAAhas some targetf∈ℋf\\in\\mathcal\{H\}satisfying

NA,ε𝒳¯,P​\(f\)\>M\.N\_\{A,\\varepsilon\}^\{\\bar\{\\mathcal\{X\}\},P\}\(f\)\>M\.\(21\)

Thus allowing error does not produce a hierarchy\-independent rate\. For a fixed hierarchy and fixed evaluation distribution, consistency gives convergence inPP\-error\. But before the hierarchy is fixed, the points on which hypotheses differ can be postponed for arbitrarily many levels, even when those points have positivePP\-mass\.

### 7\.3Out\-of\-Support Generalization

A third variant returns to a distributional observation model\. The learner is no longer given a hierarchy of observed regions; it receives i\.i\.d\. labeled samples from a training distributionQQ, returns a binary predictor, and is evaluated under a possibly different distributionPP\. The hierarchy\-uniform impossibility results above do not apply literally to this model\. The same issue reappears as a support question: does training ever reveal the distinctions that evaluation can test?

The support ofQQis the region from which labels can ever be observed\. Sampling reveals points insupp⁡\(Q\)\\operatorname\{supp\}\(Q\)randomly, with repetitions, but never reveals labels outside that support\. We measure error by the samePP\-error as in[Section7\.2](https://arxiv.org/html/2607.16528#S7.SS2)\.

#### Full\-Support Generalization\.

IfQQhas full support, meaningQ​\(x\)\>0Q\(x\)\>0for everyx∈Ωx\\in\\Omega, no point is permanently outside training\. Every point that can affect thePP\-error is at least possible to observe\. For finite classes, this gives a target\-uniform sample size\.

###### Theorem 17\(Full\-support generalization\)\.

LetΩ\\Omegabe countably infinite, letQQhave full support onΩ\\Omega, fix any evaluation distributionPPonΩ\\Omega, and letℋ⊆\{0,1\}Ω\\mathcal\{H\}\\subseteq\\\{0,1\\\}^\{\\Omega\}be finite\. Then there exists a learnerAAsuch that, for everyε,δ\>0\\varepsilon,\\delta\>0, there is a finiteNNsuch that, for every targetf∈ℋf\\in\\mathcal\{H\}and everyn≥Nn\\geq N,

ℙ\(x1,…,xn\)∼Qn​\[LP,f​\(A​\(\(xi,f​\(xi\)\)i=1n\)\)≤ε\]≥1−δ\.\\mathbb\{P\}\_\{\(x\_\{1\},\\ldots,x\_\{n\}\)\\sim Q^\{n\}\}\\\!\\left\[L\_\{P,f\}\\\!\\left\(A\\\!\\left\(\\big\(x\_\{i\},f\(x\_\{i\}\)\\big\)\_\{i=1\}^\{n\}\\right\)\\right\)\\leq\\varepsilon\\right\]\\geq 1\-\\delta\.\(22\)

Full\-support sampling removes the permanent hiding place for any fixed disagreement set\. Since a finite class has only finitely many pairwise disagreement sets, one sample size can make all of them appear with high probability\.

#### Out\-of\-Support\.

IfQQis not full support, some labels are never observed\. The next theorem says that this gap can break the same target\-uniform conclusion even whenQQhas infinite support: the learner may see infinitely many possible training points, but still not the part ofΩ\\Omegaon which evaluation distinguishes two targets\.

###### Theorem 18\(Out\-of\-support generalization can fail\)\.

LetΩ\\Omegabe countably infinite, letPPhave full support onΩ\\Omega, and letℋ⊆\{0,1\}Ω\\mathcal\{H\}\\subseteq\\\{0,1\\\}^\{\\Omega\}with\|ℋ\|≥3\|\\mathcal\{H\}\|\\geq 3\. Then there exist a distributionQQwith infinite support and anε\>0\\varepsilon\>0such that, for every learnerAA, everyN∈ℕ≥1N\\in\\mathbb\{N\}\_\{\\geq 1\}, and everyn≥Nn\\geq N, there exists a targetf∈ℋf\\in\\mathcal\{H\}satisfying

ℙ\(x1,…,xn\)∼Qn​\[LP,f​\(A​\(\(xi,f​\(xi\)\)i=1n\)\)\>ε\]≥12\.\\mathbb\{P\}\_\{\(x\_\{1\},\\ldots,x\_\{n\}\)\\sim Q^\{n\}\}\\\!\\left\[L\_\{P,f\}\\\!\\left\(A\\\!\\left\(\\big\(x\_\{i\},f\(x\_\{i\}\)\\big\)\_\{i=1\}^\{n\}\\right\)\\right\)\>\\varepsilon\\right\]\\geq\\frac\{1\}\{2\}\.\(23\)

Thus the relevant condition is not how many pointsQQcan sample from\. It is whether the training support includes the distinctions thatPP\-error will test\. Full support guarantees this; an infinite support that is not full need not\.

### 7\.4Positive\-Only Presentations

Finally, consider a nearby observation model, familiar from identification from text and generation in the limit\(Gold,[1967](https://arxiv.org/html/2607.16528#bib.bib219); Kleinberg and Mullainathan,[2024](https://arxiv.org/html/2607.16528#bib.bib220)\), in which the learner sees only positive examples\. Forf∈ℋf\\in\\mathcal\{H\}, write

Pos​\(f\):=\{x∈Ω:f​\(x\)=1\}\\mathrm\{Pos\}\(f\):=\\\{x\\in\\Omega:f\(x\)=1\\\}\(24\)for its positive region\. A positive presentation offfis a strictly increasing sequence∅=S0⊊S1⊊S2⊊⋯\\emptyset=S\_\{0\}\\subsetneq S\_\{1\}\\subsetneq S\_\{2\}\\subsetneq\\cdotsof finite subsets ofPos​\(f\)\\mathrm\{Pos\}\(f\)whose union isPos​\(f\)\\mathrm\{Pos\}\(f\)\. We restrict to the nontrivial case in which everyPos​\(f\)\\mathrm\{Pos\}\(f\)is infinite\. WritePres\+​\(f\)\\mathrm\{Pres\}^\{\+\}\(f\)for the set of all such presentations\.

We ask for the same fully uniform exact\-identification guarantee as before, but with positive sets replacing labeled finite domains\. HereAAdenotes a positive\-only learner whose input is a finite positive set:

∃A​∃N<∞​∀f∈ℋ​∀S¯∈Pres\+​\(f\):∀t≥N,A​\(St\)=f\.\\exists A\\;\\exists N<\\infty\\;\\forall f\\in\\mathcal\{H\}\\;\\forall\\bar\{S\}\\in\\mathrm\{Pres\}^\{\+\}\(f\):\\;\\forall t\\geq N,\\;A\(S\_\{t\}\)=f\.\(25\)The relevant condition is finite pairwise positive overlap: distinct targets cannot share arbitrarily many positive points\.

###### Proposition 19\(Uniform positive\-only identification\)\.

AssumePos​\(f\)\\mathrm\{Pos\}\(f\)is infinite for everyf∈ℋf\\in\\mathcal\{H\}\. Then the fully uniform positive\-only criterion in[Equation25](https://arxiv.org/html/2607.16528#S7.E25)holds if and only if

supf,g∈ℋf≠g\|Pos​\(f\)∩Pos​\(g\)\|<∞,\\sup\_\{\\begin\{subarray\}\{c\}f,g\\in\\mathcal\{H\}\\\\ f\\neq g\\end\{subarray\}\}\|\\mathrm\{Pos\}\(f\)\\cap\\mathrm\{Pos\}\(g\)\|<\\infty,\(26\)with the convention that the supremum over the empty set is0\. Moreover, if this supremum isdd, thenN=d\+1N=d\+1suffices\.

The condition is not finiteness\. For example, takeΩ=ℕ×ℕ\\Omega=\\mathbb\{N\}\\times\\mathbb\{N\}and, fora,b∈ℕa,b\\in\\mathbb\{N\}, let

Ga,b:=\{\(t,a​t\+b\):t∈ℕ\},G\_\{a,b\}:=\\\{\(t,at\+b\):t\\in\\mathbb\{N\}\\\},\(27\)and letfa,bf\_\{a,b\}be the indicator ofGa,bG\_\{a,b\}\. The class\{fa,b:a,b∈ℕ\}\\\{f\_\{a,b\}:a,b\\in\\mathbb\{N\}\\\}is countably infinite, and every positive region is infinite\. Yet two distinct graphs intersect in at most one point, so two positive observations already certify the target against every competitor\.

In our terms, this restricts the presentation to positive examples while keeping exact identification and full uniformity\. Under this restriction, the strongest uniform statement can hold even for infinite classes\.

This positive\-only model is closely related to generation in the limit\(Kleinberg and Mullainathan,[2024](https://arxiv.org/html/2607.16528#bib.bib220)\)\. There too, the learner sees a growing finite subset of the target language, but only needs to generate one new valid positive example\. Since the target is unknown, that point must be positive for every consistent hypothesis; closure dimension characterizes when this can be done uniformly\(Ramanet al\.,[2025](https://arxiv.org/html/2607.16528#bib.bib221)\)\. The proposition above shows that the stronger goal of recovering the whole language, equivalently generating all positives, can also hold uniformly\.

## 8Conclusion

We characterized hierarchical domain generalization at four levels of uniformity, and proved a no\-free\-lunch theorem showing that hierarchy\-uniform guarantees are achievable only in the trivial finite\-domain case\. For infinite classes, meaningful guarantees thus live at the level of fixed hierarchies and bounded\-complexity slices, as in length generalization\. The hierarchy is part of the learning problem\.

## References

- Generalization on the unseen, logic reasoning and degree curriculum\.InProceedings of the 40th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.202,pp\. 31–60\.External Links:[Link](https://proceedings.mlr.press/v202/abbe23a.html)Cited by:[§1](https://arxiv.org/html/2607.16528#S1.p6.2)\.
- C\. Anil, Y\. Wu, A\. Andreassen, A\. Lewkowycz, V\. Misra, V\. Ramasesh, A\. Slone, G\. Gur\-Ari, E\. Dyer, and B\. Neyshabur \(2022\)Exploring length generalization in large language models\.Advances in Neural Information Processing Systems35,pp\. 38546–38556\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2022/hash/fb7451e43f9c1c35b774bcfad7a5714b-Abstract-Conference.html)Cited by:[§1](https://arxiv.org/html/2607.16528#S1.p4.1),[§1](https://arxiv.org/html/2607.16528#S1.p6.2),[§5](https://arxiv.org/html/2607.16528#S5.p2.1)\.
- S\. Ben\-David, J\. Blitzer, K\. Crammer, and F\. Pereira \(2006\)Analysis of representations for domain adaptation\.InAdvances in Neural Information Processing Systems 19,pp\. 137–144\.External Links:[Link](https://papers.nips.cc/paper/2983-analysis-of-representations-for-domain-adaptation)Cited by:[§1](https://arxiv.org/html/2607.16528#S1.p2.2)\.
- Y\. Bengio, J\. Louradour, R\. Collobert, and J\. Weston \(2009\)Curriculum learning\.InProceedings of the 26th International Conference on Machine Learning \(ICML\),pp\. 41–48\.External Links:[Document](https://dx.doi.org/10.1145/1553374.1553380)Cited by:[§1](https://arxiv.org/html/2607.16528#S1.p6.2)\.
- T\. Chen, T\. Ma, and Z\. Li \(2025\)Non\-asymptotic length generalization\.InProceedings of the 42nd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.267,pp\. 8621–8682\.External Links:[Link](https://proceedings.mlr.press/v267/chen25ar.html)Cited by:[§1](https://arxiv.org/html/2607.16528#S1.p9.3),[§5](https://arxiv.org/html/2607.16528#S5.SS0.SSS0.Px1.p2.7),[§5](https://arxiv.org/html/2607.16528#S5.SS0.SSS0.Px2.p3.1)\.
- E\. M\. Gold \(1967\)Language identification in the limit\.Information and Control10\(5\),pp\. 447–474\.External Links:[Document](https://dx.doi.org/10.1016/S0019-9958%2867%2991165-5)Cited by:[§1](https://arxiv.org/html/2607.16528#S1.p6.2),[§2\.1](https://arxiv.org/html/2607.16528#S2.SS1.p3.6),[§7\.4](https://arxiv.org/html/2607.16528#S7.SS4.p1.1)\.
- X\. Huang, A\. Yang, S\. Bhattamishra, Y\. Sarrof, A\. Krebs, H\. Zhou, P\. Nakkiran, and M\. Hahn \(2025\)A formal framework for understanding length generalization in transformers\.InInternational Conference on Learning Representations,Vol\.2025,pp\. 58095–58179\.Note:arXiv:2410\.02140External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2025/hash/928170bcb050fe64a63fe781b82265aa-Abstract-Conference.html)Cited by:[§1](https://arxiv.org/html/2607.16528#S1.p9.3),[§5](https://arxiv.org/html/2607.16528#S5.SS0.SSS0.Px1.p1.1)\.
- Z\. Izzo, E\. Nichani, and J\. D\. Lee \(2026\)Quantitative bounds for length generalization in transformers\.InInternational Conference on Learning Representations,Note:arXiv:2510\.27015External Links:[Link](https://openreview.net/forum?id=TLSUIyBIfs)Cited by:[§1](https://arxiv.org/html/2607.16528#S1.p9.3),[§5](https://arxiv.org/html/2607.16528#S5.SS0.SSS0.Px1.p3.1)\.
- J\. Kleinberg and S\. Mullainathan \(2024\)Language generation in the limit\.InAdvances in Neural Information Processing Systems,Vol\.37,pp\. 66058–66079\.External Links:[Document](https://dx.doi.org/10.52202/079017-2111),[Link](https://proceedings.neurips.cc/paper_files/paper/2024/hash/7988e9b3876ad689e921ce05d711442f-Abstract-Conference.html)Cited by:[§1](https://arxiv.org/html/2607.16528#S1.p12.1),[§7\.4](https://arxiv.org/html/2607.16528#S7.SS4.p1.1),[§7\.4](https://arxiv.org/html/2607.16528#S7.SS4.p5.1)\.
- N\. Lee, K\. Sreenivasan, J\. Lee, K\. Lee, and D\. Papailiopoulos \(2024\)Teaching arithmetic to small transformers\.InInternational Conference on Learning Representations,Vol\.2024,pp\. 25001–25054\.External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2024/hash/6bf82fdcbd92b6a7793b3894422d2437-Abstract-Conference.html)Cited by:[§1](https://arxiv.org/html/2607.16528#S1.p4.1),[§1](https://arxiv.org/html/2607.16528#S1.p6.2),[§5](https://arxiv.org/html/2607.16528#S5.p2.1)\.
- N\. Littlestone \(1988\)Learning quickly when irrelevant attributes abound: a new linear\-threshold algorithm\.Machine Learning2\(4\),pp\. 285–318\.External Links:[Document](https://dx.doi.org/10.1023/A%3A1022869011914)Cited by:[§7\.1](https://arxiv.org/html/2607.16528#S7.SS1.p4.3)\.
- V\. Raman, J\. Li, and A\. Tewari \(2025\)Generation through the lens of learning theory\.InProceedings of the Thirty Eighth Conference on Learning Theory,N\. Haghtalab and A\. Moitra \(Eds\.\),Proceedings of Machine Learning Research, Vol\.291,pp\. 4740–4776\.External Links:[Link](https://proceedings.mlr.press/v291/raman25a.html)Cited by:[§7\.4](https://arxiv.org/html/2607.16528#S7.SS4.p5.1)\.
- S\. Shalev\-Shwartz and S\. Ben\-David \(2014\)Understanding machine learning: from theory to algorithms\.Cambridge University Press\.External Links:[Document](https://dx.doi.org/10.1017/CBO9781107298019)Cited by:[§1](https://arxiv.org/html/2607.16528#S1.p11.2),[§6](https://arxiv.org/html/2607.16528#S6.SS0.SSS0.Px3.p1.1)\.
- L\. G\. Valiant \(1984\)A theory of the learnable\.Communications of the ACM27\(11\),pp\. 1134–1142\.External Links:[Document](https://dx.doi.org/10.1145/1968.1972)Cited by:[§1](https://arxiv.org/html/2607.16528#S1.p1.1)\.
- V\. N\. Vapnik and A\. Y\. Chervonenkis \(1971\)On the uniform convergence of relative frequencies of events to their probabilities\.Theory of Probability & Its Applications16\(2\),pp\. 264–280\.External Links:[Document](https://dx.doi.org/10.1137/1116025)Cited by:[§1](https://arxiv.org/html/2607.16528#S1.p1.1)\.
- A\. Vaswani, N\. Shazeer, N\. Parmar, J\. Uszkoreit, L\. Jones, A\. N\. Gomez, Ł\. Kaiser, and I\. Polosukhin \(2017\)Attention is all you need\.InAdvances in Neural Information Processing Systems,Vol\.30,pp\. 5998–6008\.External Links:[Link](https://papers.nips.cc/paper/7181-attention-is-all-you-need)Cited by:[§5](https://arxiv.org/html/2607.16528#S5.p2.1)\.
- A\. Yang, P\. Bergsträßer, G\. Zetzsche, D\. Chiang, and A\. W\. Lin \(2026a\)Length generalization bounds for transformers\.arXiv preprint arXiv:2603\.02238\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2603.02238),[Link](https://arxiv.org/abs/2603.02238)Cited by:[§1](https://arxiv.org/html/2607.16528#S1.p9.3),[§5](https://arxiv.org/html/2607.16528#S5.SS0.SSS0.Px1.p3.1)\.
- A\. Yang and D\. Chiang \(2024\)Counting like transformers: compiling temporal counting logic into softmax transformers\.InFirst Conference on Language Modeling,Note:arXiv:2404\.04393External Links:[Link](https://openreview.net/forum?id=FmhPg4UJ9K)Cited by:[footnote 4](https://arxiv.org/html/2607.16528#footnote4)\.
- C\. Yang, N\. Srebro, and Z\. Li \(2026b\)Recursive models for long\-horizon reasoning\.InInternational Conference on Machine Learning,Note:arXiv:2603\.02112External Links:[Link](https://arxiv.org/abs/2603.02112)Cited by:[§1](https://arxiv.org/html/2607.16528#S1.p6.2)\.
- H\. Zhou, A\. Bradley, E\. Littwin, N\. Razin, O\. Saremi, J\. Susskind, S\. Bengio, and P\. Nakkiran \(2024\)What algorithms can transformers learn? a study in length generalization\.InInternational Conference on Learning Representations,Vol\.2024,pp\. 15898–15926\.External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2024/hash/45ed1a72597594c097152ef9cc187762-Abstract-Conference.html)Cited by:[§1](https://arxiv.org/html/2607.16528#S1.p6.2),[§5](https://arxiv.org/html/2607.16528#S5.p2.1)\.

## Appendix AAuxiliary Definitions

The appendix uses the following derived notation\.

For two hypothesesf,g∈\{0,1\}Ωf,g\\in\\\{0,1\\\}^\{\\Omega\}, write

Eq⁡\(f,g\):=\{x∈Ω:f​\(x\)=g​\(x\)\},\\operatorname\{Eq\}\(f,g\):=\\\{x\\in\\Omega:f\(x\)=g\(x\)\\\},\(28\)also denoted\{f=g\}\\\{f=g\\\}when this is typographically lighter\.

###### Definition 13\(Version space and pointwise class complexity\)\.

Fix a hypothesis classℋ\\mathcal\{H\}, a hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}, and a targetf∈ℋf\\in\\mathcal\{H\}\. The version space at levelnnis

Vℋ,n𝒳¯​\(f\):=\{g∈ℋ:g\|𝒳n=f\|𝒳n\}\.V\_\{\\mathcal\{H\},n\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\):=\\\{g\\in\\mathcal\{H\}:g\|\_\{\\mathcal\{X\}\_\{n\}\}=f\|\_\{\\mathcal\{X\}\_\{n\}\}\\\}\.\(29\)The pointwise algorithm\-agnostic domain complexity is

Nℋ𝒳¯​\(f\)\\displaystyle N\_\{\\mathcal\{H\}\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\):=min⁡\{n∈ℕ≥1:Vℋ,n𝒳¯​\(f\)=\{f\}\}\\displaystyle:=\\min\\\{n\\in\\mathbb\{N\}\_\{\\geq 1\}:V\_\{\\mathcal\{H\},n\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)=\\\{f\\\}\\\}\(30\)=min⁡\{n∈ℕ≥1:∀g∈ℋ∖\{f\},∃x∈𝒳n:g​\(x\)≠f​\(x\)\}\.\\displaystyle=\\min\\\{n\\in\\mathbb\{N\}\_\{\\geq 1\}:\\forall g\\in\\mathcal\{H\}\\setminus\\\{f\\\},\\ \\exists x\\in\\mathcal\{X\}\_\{n\}:g\(x\)\\neq f\(x\)\\\}\.\(31\)If no such finite level exists, setNℋ𝒳¯​\(f\):=∞N\_\{\\mathcal\{H\}\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\):=\\infty\.

## Appendix BProofs for Exact Characterization

This appendix proves the characterization results from[Section3](https://arxiv.org/html/2607.16528#S3)\. The proofs repeatedly use the same elementary observation: if two targets induce the same labeled sample, then any deterministic learner receives the same input under the two targets and must return the same hypothesis\.

### B\.1Non\-Uniform Domain\-Dependent Generalization

###### Proof of[Theorem1](https://arxiv.org/html/2607.16528#Thmtheorem1)\.

Ifℋ=∅\\mathcal\{H\}=\\emptyset, the conclusion is vacuous\. Assume henceforth thatℋ\\mathcal\{H\}is nonempty\. Assume first thatℋ\\mathcal\{H\}is countable\. Fix an enumeration

ℋ=\{h1,h2,…\}\.\\mathcal\{H\}=\\\{h\_\{1\},h\_\{2\},\\ldots\\\}\.\(32\)Define the learnerAAas follows\. On any labeled finite sample, if there is at least one hypothesis inℋ\\mathcal\{H\}consistent with that sample, output the least\-index consistent hypothesis; if there is none, outputh1h\_\{1\}\. Only the consistent case matters on samples generated by targets inℋ\\mathcal\{H\}\.

Fix a targetf=hmf=h\_\{m\}and a hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}\. For everyj<mj<m, the hypotheseshjh\_\{j\}andffare distinct, so choose a pointxj∈Ωx\_\{j\}\\in\\Omegasuch thathj​\(xj\)≠f​\(xj\)h\_\{j\}\(x\_\{j\}\)\\neq f\(x\_\{j\}\)\. The finite set\{xj:j<m\}\\\{x\_\{j\}:j<m\\\}is contained in some prefix𝒳N\\mathcal\{X\}\_\{N\}because𝒳¯\\bar\{\\mathcal\{X\}\}exhaustsΩ\\Omega\. For everyn≥Nn\\geq N, each lower\-index hypothesishjh\_\{j\}withj<mj<mdisagrees withffon𝒳n\\mathcal\{X\}\_\{n\}, whileffitself remains consistent withf\|𝒳nf\|\_\{\\mathcal\{X\}\_\{n\}\}\. Hence the least\-index consistent hypothesis is exactlyff, soA​\(f\|𝒳n\)=fA\(f\|\_\{\\mathcal\{X\}\_\{n\}\}\)=ffor alln≥Nn\\geq N\. ThusNA𝒳¯​\(f\)≤NN\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq N, provingA1\.

Conversely, supposeℋ\\mathcal\{H\}satisfiesA1, witnessed by a learnerAA\. Fix a point\-by\-point hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}, say𝒳n=\{x1,…,xn\}\\mathcal\{X\}\_\{n\}=\\\{x\_\{1\},\\ldots,x\_\{n\}\\\}\. For eachf∈ℋf\\in\\mathcal\{H\}, choose a finite levelNfN\_\{f\}such thatA​\(f\|𝒳Nf\)=fA\(f\|\_\{\\mathcal\{X\}\_\{N\_\{f\}\}\}\)=f, which is possible becauseNA𝒳¯​\(f\)<∞N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)<\\infty\. Consider the map

f⟼\(Nf,f\|𝒳Nf\)\.f\\longmapsto\\bigl\(N\_\{f\},f\|\_\{\\mathcal\{X\}\_\{N\_\{f\}\}\}\\bigr\)\.\(33\)This map is injective\. Indeed, if two targetsf,gf,ghave the same image, then they giveAAthe same labeled sample at the same level; hence

f=A​\(f\|𝒳Nf\)=A​\(g\|𝒳Ng\)=g\.f=A\(f\|\_\{\\mathcal\{X\}\_\{N\_\{f\}\}\}\)=A\(g\|\_\{\\mathcal\{X\}\_\{N\_\{g\}\}\}\)=g\.\(34\)For each fixednn, there are only finitely many binary labelings of𝒳n\\mathcal\{X\}\_\{n\}, and there are countably many choices ofnn\. Therefore the range of this injective map is countable, and soℋ\\mathcal\{H\}is countable\. ∎

###### Proof of[Section3\.1](https://arxiv.org/html/2607.16528#S3.SS1)\.

LetΩ=ℕ\\Omega=\\mathbb\{N\}and

ℋ=\{0\}∪\{hi:i≥1\},hi​\(j\)=𝟏​\[i=j\],\\mathcal\{H\}=\\\{0\\\}\\cup\\\{h\_\{i\}:i\\geq 1\\\},\\qquad h\_\{i\}\(j\)=\\mathbf\{1\}\[i=j\],\(35\)where0is the all\-zero function\. Let the hierarchy be𝒳n=\{1,…,n\}\\mathcal\{X\}\_\{n\}=\\\{1,\\ldots,n\\\}\. Use the least\-index consistent learner with0listed first\.

For the targetf=0f=0, every observed prefix is all zero, so0is consistent at every level and is listed first\. HenceA​\(0\|𝒳n\)=0A\(0\|\_\{\\mathcal\{X\}\_\{n\}\}\)=0for everyn≥1n\\geq 1, andNA𝒳¯​\(0\)=1N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(0\)=1\.

However, for every finitennand everyj\>nj\>n, the singleton indicatorhjh\_\{j\}agrees with0on𝒳n\\mathcal\{X\}\_\{n\}\. Thus the version space around0never collapses at any finite level, even though the learner has already identified the target\. ∎

###### Proof of[Section3\.1](https://arxiv.org/html/2607.16528#S3.SS1)\.

The implication \(ii\)⇒\\Rightarrow\(i\) is immediate\. If \(i\) holds, then any level𝒳n\\mathcal\{X\}\_\{n\}withVℋ,n𝒳¯​\(f\)=\{f\}V\_\{\\mathcal\{H\},n\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)=\\\{f\\\}is such a finite setSS\. If \(iii\) holds, then every hierarchy eventually containsSS, and at that level the version space aroundffis\{f\}\\\{f\\\}\.

For the topological reformulation, the finite\-observation cells\[h\]S\[h\]\_\{S\}form a basis: finite intersections of such cells are either empty or another finite\-observation cell\. Since every finite\-level hierarchy that exhaustsΩ\\Omegaeventually contains any fixed finiteS⊆ΩS\\subseteq\\Omega, its level version spaces generate exactly the same topology\. Finally,\{f\}\\\{f\\\}is open in this topology if and only if some finite\-observation cell\[f\]S\[f\]\_\{S\}is equal to\{f\}\\\{f\\\}, which is exactly finite isolation\. ∎

###### Proof of[Theorem4](https://arxiv.org/html/2607.16528#Thmtheorem4)\.

The implication \(i\)⇒\\Rightarrow\(ii\) follows by fixing any hierarchy, and \(ii\)⇒\\Rightarrow\(iii\) follows by allowing the hierarchy to depend on the target\.

Assume \(iii\)\. Then there is a learnerAAsuch that for everyf∈ℋf\\in\\mathcal\{H\}there are a hierarchy𝒳¯f\\bar\{\\mathcal\{X\}\}^\{\\,f\}and a finite levelNfN\_\{f\}with

A​\(f\|𝒳Nff\)=f\.A\(f\|\_\{\\mathcal\{X\}^\{\\,f\}\_\{N\_\{f\}\}\}\)=f\.\(36\)Assign toffone such finite labeled samplef\|𝒳Nfff\|\_\{\\mathcal\{X\}^\{\\,f\}\_\{N\_\{f\}\}\}\. This assignment is injective: if two targets are assigned the same labeled finite sample, thenAAreceives the same input and must output both targets\. SinceΩ\\Omegais countable, the collection of finite subsets ofΩ\\Omegais countable, and each finite subset has finitely many binary labelings\. Hence there are only countably many finite labeled samples, soℋ\\mathcal\{H\}is countable\.

Finally, ifℋ\\mathcal\{H\}is countable, then \(i\) holds by[Theorem1](https://arxiv.org/html/2607.16528#Thmtheorem1)\. Therefore all the listed conditions are equivalent\. ∎

### B\.2Target\-Uniform Domain\-Dependent Generalization

###### Proof of[Theorem5](https://arxiv.org/html/2607.16528#Thmtheorem5)\.

Ifℋ=∅\\mathcal\{H\}=\\emptyset, the conclusion is vacuous\. Assume henceforth thatℋ\\mathcal\{H\}is nonempty\. Assume first thatℋ\\mathcal\{H\}is finite\. Use the least\-index consistent learner from the proof of[Theorem1](https://arxiv.org/html/2607.16528#Thmtheorem1), for any fixed enumeration of the finite class\. Fix a hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}\. By the argument in[Theorem1](https://arxiv.org/html/2607.16528#Thmtheorem1), every targetf∈ℋf\\in\\mathcal\{H\}has a finite identifying levelNA𝒳¯​\(f\)N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\. Sinceℋ\\mathcal\{H\}is finite,

N:=maxf∈ℋ⁡NA𝒳¯​\(f\)N:=\\max\_\{f\\in\\mathcal\{H\}\}N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\(37\)is finite and works for all targets along this hierarchy\. The same learner is used for every hierarchy, soA2holds\.

Conversely, supposeA2holds\. Then there are a learnerAAand, for any fixed hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}, a finite levelNNsuch thatNA𝒳¯​\(f\)≤NN\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq Nfor everyf∈ℋf\\in\\mathcal\{H\}\. If two distinct targetsf,g∈ℋf,g\\in\\mathcal\{H\}agreed on𝒳N\\mathcal\{X\}\_\{N\}, then the learner would receive the same input at levelNNunder both targets\. SinceNA𝒳¯​\(f\)≤NN\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq NandNA𝒳¯​\(g\)≤NN\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(g\)\\leq N, it would have to output bothffandggon that same input, a contradiction\. Thus the restriction map

f⟼f\|𝒳Nf\\longmapsto f\|\_\{\\mathcal\{X\}\_\{N\}\}\(38\)is injective onℋ\\mathcal\{H\}\. Because𝒳N\\mathcal\{X\}\_\{N\}is finite, it has only finitely many binary labelings\. Henceℋ\\mathcal\{H\}is finite\. ∎

###### Proof of[Section3\.2](https://arxiv.org/html/2607.16528#S3.SS2)\.

Fix a hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}\. Ifℋ=∅\\mathcal\{H\}=\\emptyset, the identity is vacuous\. Assume henceforth thatℋ\\mathcal\{H\}is nonempty\.

First suppose a learnerAAidentifies every target inℋ\\mathcal\{H\}by some finite levelMM, meaning

supf∈ℋNA𝒳¯​\(f\)≤M\.\\sup\_\{f\\in\\mathcal\{H\}\}N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq M\.\(39\)If two distinct hypothesesf,g∈ℋf,g\\in\\mathcal\{H\}agreed on𝒳M\\mathcal\{X\}\_\{M\}, thenAAwould receive the same labeled input at levelMMunder both targets\. Since both targets must be identified by levelMM, the same output would have to equal bothffandgg, impossible\. Therefore𝒳M\\mathcal\{X\}\_\{M\}distinguishes every pair inℋ\\mathcal\{H\}, so

N𝒳¯​\(ℋ\)≤M\.N^\{\\bar\{\\mathcal\{X\}\}\}\(\\mathcal\{H\}\)\\leq M\.\(40\)Since this holds for every learnerAAwith a finite uniform identifying level, it gives

N𝒳¯​\(ℋ\)≤minA​supf∈ℋNA𝒳¯​\(f\)\.N^\{\\bar\{\\mathcal\{X\}\}\}\(\\mathcal\{H\}\)\\leq\\min\_\{A\}\\sup\_\{f\\in\\mathcal\{H\}\}N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\.\(41\)
Conversely, supposeN𝒳¯​\(ℋ\)=N<∞N^\{\\bar\{\\mathcal\{X\}\}\}\(\\mathcal\{H\}\)=N<\\infty\. Define a learner that, on a labeled finite sample, outputs the unique hypothesis inℋ\\mathcal\{H\}consistent with that sample if such a unique hypothesis exists, and outputs an arbitrary fixed element ofℋ\\mathcal\{H\}otherwise\. For every targetf∈ℋf\\in\\mathcal\{H\}and everyn≥Nn\\geq N, the prefix𝒳n\\mathcal\{X\}\_\{n\}contains𝒳N\\mathcal\{X\}\_\{N\}, and𝒳N\\mathcal\{X\}\_\{N\}distinguishes every pair inℋ\\mathcal\{H\}\. Henceffis the unique hypothesis inℋ\\mathcal\{H\}consistent withf\|𝒳nf\|\_\{\\mathcal\{X\}\_\{n\}\}, so the learner outputsff\. Therefore

minA​supf∈ℋNA𝒳¯​\(f\)≤N𝒳¯​\(ℋ\)\.\\min\_\{A\}\\sup\_\{f\\in\\mathcal\{H\}\}N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq N^\{\\bar\{\\mathcal\{X\}\}\}\(\\mathcal\{H\}\)\.\(42\)IfN𝒳¯​\(ℋ\)=∞N^\{\\bar\{\\mathcal\{X\}\}\}\(\\mathcal\{H\}\)=\\infty, the first paragraph shows that no learner can have a finite uniform identifying level\. Thus both sides are∞\\infty\. This proves the identity in all cases\. ∎

###### Proof of[Theorem7](https://arxiv.org/html/2607.16528#Thmtheorem7)\.

The implication \(i\)⇒\\Rightarrow\(ii\) is immediate by fixing one hierarchy\. If \(ii\) holds with learnerAA, hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}, and boundNN, then no two distinct targets can agree on𝒳N\\mathcal\{X\}\_\{N\}: otherwiseAAwould receive the same labeled input under both targets at levelNN, but would have to output two different functions\. Hence𝒳N\\mathcal\{X\}\_\{N\}distinguishes every pair inℋ\\mathcal\{H\}, soN𝒳¯​\(ℋ\)<∞N^\{\\bar\{\\mathcal\{X\}\}\}\(\\mathcal\{H\}\)<\\infty, proving \(iii\)\.

If \(iii\) holds, then for some hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}and some finiteNN, the prefix𝒳N\\mathcal\{X\}\_\{N\}distinguishes every pair inℋ\\mathcal\{H\}\. The restriction mapf↦f\|𝒳Nf\\mapsto f\|\_\{\\mathcal\{X\}\_\{N\}\}is injective, soℋ\\mathcal\{H\}injects into the finite set of binary labelings of𝒳N\\mathcal\{X\}\_\{N\}\. Henceℋ\\mathcal\{H\}is finite, proving \(v\)\.

Ifℋ\\mathcal\{H\}is finite, then for every hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}and every distinct pairf,g∈ℋf,g\\in\\mathcal\{H\}, there is some pointxf,gx\_\{f,g\}withf​\(xf,g\)≠g​\(xf,g\)f\(x\_\{f,g\}\)\\neq g\(x\_\{f,g\}\)\. Since𝒳¯\\bar\{\\mathcal\{X\}\}exhaustsΩ\\Omega, each such point appears in some finite prefix\. Taking the maximum over the finitely many pairs gives a finite level whose prefix distinguishes every pair inℋ\\mathcal\{H\}\. Thus \(iv\) holds\. Ifℋ\\mathcal\{H\}has at most one element, the distinguishing condition is vacuous and any level, say11, works\.

Finally, \(iv\)⇒\\Rightarrow\(iii\) is immediate, and \(v\)⇒\\Rightarrow\(i\) also follows from[Theorem5](https://arxiv.org/html/2607.16528#Thmtheorem5)\. Therefore all five conditions are equivalent\. ∎

### B\.3Domain\-Uniform Generalization

###### Proof of[Theorem8](https://arxiv.org/html/2607.16528#Thmtheorem8)\.

The implication \(i\)⇒\\Rightarrow\(ii\) is immediate, since a single bound that works for all targets and all hierarchies is in particular allowed to depend on the target\.

Assume next thatΩ\\Omegais finite\. Under the finite\-domain convention, every hierarchy has revealed all ofΩ\\Omegaby level\|Ω\|\|\\Omega\|\. Consider the learner that outputs the unique hypothesis inℋ\\mathcal\{H\}consistent with the full observed labels once the full domain has been revealed, and is arbitrary before that\. For any targetf∈ℋf\\in\\mathcal\{H\}, the full\-domain labeled sample determinesffuniquely insideℋ\\mathcal\{H\}\. Hence this learner identifies every target along every hierarchy by level\|Ω\|\|\\Omega\|, provingA4, and thereforeA3\.

It remains to prove thatA3impliesΩ\\Omegais finite, under the assumption\|ℋ\|\>2\|\\mathcal\{H\}\|\>2\. SupposeA3is witnessed by a learnerAA\. For everyf∈ℋf\\in\\mathcal\{H\}, choose a finite level boundNfN\_\{f\}such that

NA𝒳¯​\(f\)≤NfN\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq N\_\{f\}\(43\)for every hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}\.

We first show that every pair of distinct hypotheses has a finite agreement set\. Letf,g∈ℋf,g\\in\\mathcal\{H\}be distinct and setM=max⁡\{Nf,Ng\}M=\\max\\\{N\_\{f\},N\_\{g\}\\\}\. IfEq⁡\(f,g\)\\operatorname\{Eq\}\(f,g\)contained at leastMMpoints, choose a hierarchy whoseMM\-th prefix consists ofMMsuch agreement points\. At levelMM, the labeled samples generated byffand byggare identical\. ButM≥Nf,NgM\\geq N\_\{f\},N\_\{g\}, so domain\-uniform identifiability requiresAAto outputffon this input under targetffandggon the same input under targetgg, impossible\. ThereforeEq⁡\(f,g\)\\operatorname\{Eq\}\(f,g\)has fewer thanMMpoints, and is finite\.

Now choose three distinct hypothesesh1,h2,h3∈ℋh\_\{1\},h\_\{2\},h\_\{3\}\\in\\mathcal\{H\}\. Since the labels are binary, at each pointx∈Ωx\\in\\Omegaat least two of the three valuesh1​\(x\),h2​\(x\),h3​\(x\)h\_\{1\}\(x\),h\_\{2\}\(x\),h\_\{3\}\(x\)are equal\. Hence

Ω=Eq⁡\(h1,h2\)∪Eq⁡\(h1,h3\)∪Eq⁡\(h2,h3\)\.\\Omega=\\operatorname\{Eq\}\(h\_\{1\},h\_\{2\}\)\\cup\\operatorname\{Eq\}\(h\_\{1\},h\_\{3\}\)\\cup\\operatorname\{Eq\}\(h\_\{2\},h\_\{3\}\)\.\(44\)Each set on the right is finite by the previous paragraph, soΩ\\Omegais finite\. This proves \(ii\)⇒\\Rightarrow\(iii\), and completes the equivalence\. ∎

## Appendix CProofs for Stratified Domain Complexity

###### Proof of[Theorem9](https://arxiv.org/html/2607.16528#Thmtheorem9)\.

Fix a hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}, a classℋ⊆\{0,1\}Ω\\mathcal\{H\}\\subseteq\\\{0,1\\\}^\{\\Omega\}, and a complexity scalec:ℋ→ℕc:\\mathcal\{H\}\\to\\mathbb\{N\}\.

Fixs∈ℕs\\in\\mathbb\{N\}\. By[Equation6](https://arxiv.org/html/2607.16528#S4.E6),ℋ≤sc\\mathcal\{H\}\_\{\\leq s\}^\{c\}is finite\. For every distinct pairf,g∈ℋ≤scf,g\\in\\mathcal\{H\}\_\{\\leq s\}^\{c\}, choose a pointxf,gx\_\{f,g\}withf​\(xf,g\)≠g​\(xf,g\)f\(x\_\{f,g\}\)\\neq g\(x\_\{f,g\}\)\. Since𝒳¯\\bar\{\\mathcal\{X\}\}exhaustsΩ\\Omega, each such point appears in some finite prefix\. Taking the maximum over the finitely many pairs gives a finite prefix that distinguishes every pair inℋ≤sc\\mathcal\{H\}\_\{\\leq s\}^\{c\}\. If\|ℋ≤sc\|≤1\|\\mathcal\{H\}\_\{\\leq s\}^\{c\}\|\\leq 1, any level, say11, works\. Thus

N\(ℋ,c\)𝒳¯​\(s\)<∞\.N\_\{\(\\mathcal\{H\},c\)\}^\{\\bar\{\\mathcal\{X\}\}\}\(s\)<\\infty\.\(45\)
For the optimality identity, fixsswithℋ≤sc≠∅\\mathcal\{H\}\_\{\\leq s\}^\{c\}\\neq\\emptyset\. By definition,

N\(ℋ,c\)𝒳¯​\(s\)=N𝒳¯​\(ℋ≤sc\)\.N\_\{\(\\mathcal\{H\},c\)\}^\{\\bar\{\\mathcal\{X\}\}\}\(s\)=N^\{\\bar\{\\mathcal\{X\}\}\}\(\\mathcal\{H\}\_\{\\leq s\}^\{c\}\)\.\(46\)Applying[Section3\.2](https://arxiv.org/html/2607.16528#S3.SS2)to the classℋ≤sc\\mathcal\{H\}\_\{\\leq s\}^\{c\}gives

N\(ℋ,c\)𝒳¯​\(s\)=minA​supf∈ℋ≤scNA𝒳¯​\(f\),N\_\{\(\\mathcal\{H\},c\)\}^\{\\bar\{\\mathcal\{X\}\}\}\(s\)=\\min\_\{A\}\\sup\_\{f\\in\\mathcal\{H\}\_\{\\leq s\}^\{c\}\}N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\),\(47\)with both sides taking values inℕ≥1∪\{∞\}\\mathbb\{N\}\_\{\\geq 1\}\\cup\\\{\\infty\\\}\.

Finally suppose\|ℋ≤sc\|→∞\|\\mathcal\{H\}\_\{\\leq s\}^\{c\}\|\\to\\infty\. The sublevel classes are nested inss, so the numbersN\(ℋ,c\)𝒳¯​\(s\)N\_\{\(\\mathcal\{H\},c\)\}^\{\\bar\{\\mathcal\{X\}\}\}\(s\)are nondecreasing\. If they did not tend to infinity, then there would be a finiteMMand arbitrarily largesswithN\(ℋ,c\)𝒳¯​\(s\)≤MN\_\{\(\\mathcal\{H\},c\)\}^\{\\bar\{\\mathcal\{X\}\}\}\(s\)\\leq M\. For each suchss, the prefix𝒳M\\mathcal\{X\}\_\{M\}would distinguish every pair inℋ≤sc\\mathcal\{H\}\_\{\\leq s\}^\{c\}, so the restriction map into\{0,1\}𝒳M\\\{0,1\\\}^\{\\mathcal\{X\}\_\{M\}\}would be injective onℋ≤sc\\mathcal\{H\}\_\{\\leq s\}^\{c\}\. This gives

\|ℋ≤sc\|≤2\|𝒳M\|\|\\mathcal\{H\}\_\{\\leq s\}^\{c\}\|\\leq 2^\{\|\\mathcal\{X\}\_\{M\}\|\}\(48\)for arbitrarily largess, contradicting\|ℋ≤sc\|→∞\|\\mathcal\{H\}\_\{\\leq s\}^\{c\}\|\\to\\infty\. ThereforeN\(ℋ,c\)𝒳¯​\(s\)→∞N\_\{\(\\mathcal\{H\},c\)\}^\{\\bar\{\\mathcal\{X\}\}\}\(s\)\\to\\infty\. ∎

###### Proof of[Section5](https://arxiv.org/html/2607.16528#S5.SS0.SSS0.Px2)\.

Suppose, toward a contradiction, that for some computable exhaustive hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}there is a computable functionBBsatisfying the bound in the statement\. Given two descriptionsp,q∈Πp,q\\in\\Pi, compute

s:=max⁡\{κ​\(p\),κ​\(q\)\}\.s:=\\max\\\{\\kappa\(p\),\\kappa\(q\)\\\}\.\(49\)ComputeB​\(s\)B\(s\)and enumerate𝒳B​\(s\)\\mathcal\{X\}\_\{B\(s\)\}\. Since evaluation is decidable from descriptions, we can check whetherhph\_\{p\}andhqh\_\{q\}disagree on some point of𝒳B​\(s\)\\mathcal\{X\}\_\{B\(s\)\}\. If they do, then they are not semantically equivalent\. If they do not, thenhph\_\{p\}andhqh\_\{q\}agree on𝒳B​\(s\)\\mathcal\{X\}\_\{B\(s\)\}\. Buthp,hq∈ℋ≤sΠ,κh\_\{p\},h\_\{q\}\\in\\mathcal\{H\}\_\{\\leq s\}^\{\\Pi,\\kappa\}, andB​\(s\)B\(s\)is at least the sublevel domain complexity of this slice\. Hence any two distinct hypotheses inℋ≤sΠ,κ\\mathcal\{H\}\_\{\\leq s\}^\{\\Pi,\\kappa\}would have been separated inside𝒳B​\(s\)\\mathcal\{X\}\_\{B\(s\)\}\. Thereforehp=hqh\_\{p\}=h\_\{q\}on all ofΩ\\Omega, and the procedure decides semantic equivalence from descriptions\. ∎

###### Proof of[Section5](https://arxiv.org/html/2607.16528#S5.SS0.SSS0.Px2)\.

Fix an enumerationz1,z2,…z\_\{1\},z\_\{2\},\\ldotsofΩ\\Omega\. We construct the hierarchy recursively\. Set𝒳0=∅\\mathcal\{X\}\_\{0\}=\\emptyset\. Given𝒳m−1\\mathcal\{X\}\_\{m\-1\}, for eachi<mi<mchoose a pointwi,m∈Ωw\_\{i,m\}\\in\\Omegasuch thathi​\(wi,m\)≠hm​\(wi,m\)h\_\{i\}\(w\_\{i,m\}\)\\neq h\_\{m\}\(w\_\{i,m\}\)\. Letumu\_\{m\}be the first point in the enumeration ofΩ\\Omegathat is not contained in

𝒳m−1∪\{wi,m:i<m\}\.\\mathcal\{X\}\_\{m\-1\}\\cup\\\{w\_\{i,m\}:i<m\\\}\.\(50\)Define

𝒳m:=𝒳m−1∪\{wi,m:i<m\}∪\{um\}\.\\mathcal\{X\}\_\{m\}:=\\mathcal\{X\}\_\{m\-1\}\\cup\\\{w\_\{i,m\}:i<m\\\}\\cup\\\{u\_\{m\}\\\}\.\(51\)Each𝒳m\\mathcal\{X\}\_\{m\}is finite and𝒳m−1⊊𝒳m\\mathcal\{X\}\_\{m\-1\}\\subsetneq\\mathcal\{X\}\_\{m\}\. The added pointsumu\_\{m\}ensure that every point ofΩ\\Omegaeventually appears, so𝒳¯\\bar\{\\mathcal\{X\}\}is exhaustive\. Finally, for any pairi<j≤mi<j\\leq m, the pointwi,jw\_\{i,j\}was added by leveljj, and hence belongs to𝒳m\\mathcal\{X\}\_\{m\}; it separateshih\_\{i\}fromhjh\_\{j\}\. Thus𝒳m\\mathcal\{X\}\_\{m\}distinguishes every pair in\{h1,…,hm\}\\\{h\_\{1\},\\ldots,h\_\{m\}\\\}, soN𝒳¯​\(\{h1,…,hm\}\)≤mN^\{\\bar\{\\mathcal\{X\}\}\}\(\\\{h\_\{1\},\\ldots,h\_\{m\}\\\}\)\\leq m\. ∎

## Appendix DProofs for the No\-Free\-Lunch Results

### D\.1Class\-Level No Free Lunch

###### Proof of[Theorem12](https://arxiv.org/html/2607.16528#Thmtheorem12)\.

Choose three distinct hypothesesh1,h2,h3∈ℋh\_\{1\},h\_\{2\},h\_\{3\}\\in\\mathcal\{H\}\. Since labels are binary, the three pairwise agreement sets

Eq⁡\(h1,h2\),Eq⁡\(h1,h3\),Eq⁡\(h2,h3\)\\operatorname\{Eq\}\(h\_\{1\},h\_\{2\}\),\\qquad\\operatorname\{Eq\}\(h\_\{1\},h\_\{3\}\),\\qquad\\operatorname\{Eq\}\(h\_\{2\},h\_\{3\}\)\(52\)coverΩ\\Omega: at every point, at least two of the three binary labels agree\. SinceΩ\\Omegais infinite, at least one of these three agreement sets is infinite\. Letg0,g1∈ℋg\_\{0\},g\_\{1\}\\in\\mathcal\{H\}be a distinct pair withEq⁡\(g0,g1\)\\operatorname\{Eq\}\(g\_\{0\},g\_\{1\}\)infinite\.

FixM∈ℕ≥1M\\in\\mathbb\{N\}\_\{\\geq 1\}\. Choose distinct points

z1,…,zM∈Eq⁡\(g0,g1\),z\_\{1\},\\ldots,z\_\{M\}\\in\\operatorname\{Eq\}\(g\_\{0\},g\_\{1\}\),\(53\)and extend them to an enumerationz1,z2,…z\_\{1\},z\_\{2\},\\ldotsofΩ\\Omega\. Define the point\-by\-point hierarchy

𝒳n:=\{z1,…,zn\}\.\\mathcal\{X\}\_\{n\}:=\\\{z\_\{1\},\\ldots,z\_\{n\}\\\}\.\(54\)Theng0g\_\{0\}andg1g\_\{1\}agree on𝒳M\\mathcal\{X\}\_\{M\}\.

Now letAAbe any learner\. At levelMM, the labeled sample generated by targetg0g\_\{0\}is the same as the labeled sample generated by targetg1g\_\{1\}\. ThereforeAAhas the same output on both samples\. It cannot be equal to both distinct functionsg0g\_\{0\}andg1g\_\{1\}\. Hence at least one of the two targets, call ithh, is not identified by levelMM, so

NA𝒳¯​\(h\)\>M\.N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(h\)\>M\.\(55\)The hierarchy was constructed before choosingAA, so this proves the first claim\.

Whenℋ\\mathcal\{H\}is finite, the equivalent class\-domain\-complexity statement follows from[Section3\.2](https://arxiv.org/html/2607.16528#S3.SS2)\. Indeed,

N𝒳¯​\(ℋ\)\>MN^\{\\bar\{\\mathcal\{X\}\}\}\(\\mathcal\{H\}\)\>M\(56\)if and only if no learner can identify every target inℋ\\mathcal\{H\}by levelMM, which is equivalent to saying that every learner has some targeth∈ℋh\\in\\mathcal\{H\}withNA𝒳¯​\(h\)\>MN\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(h\)\>M\. ∎

### D\.2Complexity\-Stratified No Free Lunch

###### Proof of[Section6](https://arxiv.org/html/2607.16528#S6.SS0.SSS0.Px2)\.

Fix an enumeration

Ω=\{y1,y2,…\}\.\\Omega=\\\{y\_\{1\},y\_\{2\},\\ldots\\\}\.\(57\)We will construct a point\-by\-point hierarchy by constructing an enumerationz1,z2,…z\_\{1\},z\_\{2\},\\ldotsofΩ\\Omega\. The construction ensures that, for infinitely many increasing complexity thresholds, a pair of hypotheses inside the corresponding sublevel class agrees on a very long initial prefix\.

*Step 1: a reusable extension claim\.*We first state the combinatorial step used at every stage\. LetP⊆ΩP\\subseteq\\Omegabe finite, letS∈ℕS\\in\\mathbb\{N\}, and letR⊆ΩR\\subseteq\\Omegabe infinite\. Sinceℋ≤Sc\\mathcal\{H\}\_\{\\leq S\}^\{c\}is finite andℋ\\mathcal\{H\}is infinite, the setℋ∖ℋ≤Sc\\mathcal\{H\}\\setminus\\mathcal\{H\}\_\{\\leq S\}^\{c\}is infinite\. Only finitely many binary label patterns can occur onPP, so infinitely many hypotheses inℋ∖ℋ≤Sc\\mathcal\{H\}\\setminus\\mathcal\{H\}\_\{\\leq S\}^\{c\}share the same pattern onPP\. Choose three such hypotheses\. On every point ofRR, at least two of their three binary labels agree; since the three pairwise agreement sets coverRR, one pair agrees on infinitely many points ofRR\. Thus there exist distinctf,g∈ℋ∖ℋ≤Scf,g\\in\\mathcal\{H\}\\setminus\\mathcal\{H\}\_\{\\leq S\}^\{c\}such that

f\|P=g\|PandEq⁡\(f,g\)∩R​is infinite\.f\|\_\{P\}=g\|\_\{P\}\\qquad\\text\{and\}\\qquad\\operatorname\{Eq\}\(f,g\)\\cap R\\text\{ is infinite\}\.\(58\)
*Step 2: build a hierarchy with longer and longer concealed pairs\.*Choose any three hypotheses inℋ\\mathcal\{H\}\. Their three pairwise agreement sets cover the infinite setΩ\\Omega, so one pair\(f0,g0\)\(f\_\{0\},g\_\{0\}\)has infinite agreement set\. Let

A0:=Eq⁡\(f0,g0\),S0:=max⁡\{c​\(f0\),c​\(g0\)\},P0:=∅\.A\_\{0\}:=\\operatorname\{Eq\}\(f\_\{0\},g\_\{0\}\),\\qquad S\_\{0\}:=\\max\\\{c\(f\_\{0\}\),c\(g\_\{0\}\)\\\},\\qquad P\_\{0\}:=\\emptyset\.\(59\)Inductively, suppose we have a finite prefixPkP\_\{k\}of the ordering, a pair\(fk,gk\)\(f\_\{k\},g\_\{k\}\), an infinite agreement setAk:=Eq⁡\(fk,gk\)A\_\{k\}:=\\operatorname\{Eq\}\(f\_\{k\},g\_\{k\}\), and a thresholdSk:=max⁡\{c​\(fk\),c​\(gk\)\}S\_\{k\}:=\\max\\\{c\(f\_\{k\}\),c\(g\_\{k\}\)\\\}, withPk⊆AkP\_\{k\}\\subseteq A\_\{k\}\. The invariant means that the current pair agrees on every point revealed so far\.

Apply the combinatorial step with the finite setPk∪\{yk\+1\}P\_\{k\}\\cup\\\{y\_\{k\+1\}\\\}, the thresholdSkS\_\{k\}, and the infinite setAkA\_\{k\}\. We obtain a pair\(fk\+1,gk\+1\)\(f\_\{k\+1\},g\_\{k\+1\}\)outsideℋ≤Skc\\mathcal\{H\}\_\{\\leq S\_\{k\}\}^\{c\}such that it agrees onPk∪\{yk\+1\}P\_\{k\}\\cup\\\{y\_\{k\+1\}\\\}and has infinitely many agreement points insideAkA\_\{k\}\. Set

Ak\+1:=Eq⁡\(fk\+1,gk\+1\),Sk\+1:=max⁡\{c​\(fk\+1\),c​\(gk\+1\)\}\.A\_\{k\+1\}:=\\operatorname\{Eq\}\(f\_\{k\+1\},g\_\{k\+1\}\),\\qquad S\_\{k\+1\}:=\\max\\\{c\(f\_\{k\+1\}\),c\(g\_\{k\+1\}\)\\\}\.\(60\)Because bothfk\+1f\_\{k\+1\}andgk\+1g\_\{k\+1\}lie outsideℋ≤Skc\\mathcal\{H\}\_\{\\leq S\_\{k\}\}^\{c\}, we haveSk\+1\>SkS\_\{k\+1\}\>S\_\{k\}\. AlsoAk∩Ak\+1A\_\{k\}\\cap A\_\{k\+1\}is infinite, andPk∪\{yk\+1\}⊆Ak\+1P\_\{k\}\\cup\\\{y\_\{k\+1\}\\\}\\subseteq A\_\{k\+1\}\.

Extend the current ordering by adding unused points fromAk∩Ak\+1A\_\{k\}\\cap A\_\{k\+1\}until at least the firstB​\(Sk\+1\)B\(S\_\{k\+1\}\)positions have been filled\. Then appendyk\+1y\_\{k\+1\}if it has not already appeared\. LetPk\+1P\_\{k\+1\}be the resulting finite prefix\. This preserves the induction invariantPk\+1⊆Ak\+1P\_\{k\+1\}\\subseteq A\_\{k\+1\}: the old prefix andyk\+1y\_\{k\+1\}lie inAk\+1A\_\{k\+1\}, and the added points lie inAk∩Ak\+1A\_\{k\}\\cap A\_\{k\+1\}\. It also ensures that the firstB​\(Sk\+1\)B\(S\_\{k\+1\}\)points of the ordering lie inAkA\_\{k\}\.

Sinceyk\+1y\_\{k\+1\}is inserted by the end of stagek\+1k\+1if it has not appeared earlier, every point ofΩ\\Omegaeventually appears\. The limiting orderingz1,z2,…z\_\{1\},z\_\{2\},\\ldotsis therefore an enumeration ofΩ\\Omega, and it defines a point\-by\-point hierarchy𝒳¯\\bar\{\\mathcal\{X\}\}by

𝒳n:=\{z1,…,zn\}\.\\mathcal\{X\}\_\{n\}:=\\\{z\_\{1\},\\ldots,z\_\{n\}\\\}\.\(61\)
*Step 3: verify the lower bound on the sublevel domain complexity\.*It remains to verify the bound\. The thresholdsSkS\_\{k\}are strictly increasing, henceSk→∞S\_\{k\}\\to\\infty\. Lets≥S0s\\geq S\_\{0\}\. Choosekksuch that

Sk≤s≤Sk\+1\.S\_\{k\}\\leq s\\leq S\_\{k\+1\}\.\(62\)The pair\(fk,gk\)\(f\_\{k\},g\_\{k\}\)lies inℋ≤sc\\mathcal\{H\}\_\{\\leq s\}^\{c\}because both complexities are at mostSk≤sS\_\{k\}\\leq s\. By construction,fkf\_\{k\}andgkg\_\{k\}agree on the firstB​\(Sk\+1\)B\(S\_\{k\+1\}\)points of the hierarchy\. SinceBBis nondecreasing ands≤Sk\+1s\\leq S\_\{k\+1\}, they agree on the firstB​\(s\)B\(s\)points\. Therefore𝒳B​\(s\)\\mathcal\{X\}\_\{B\(s\)\}does not distinguish all pairs inℋ≤sc\\mathcal\{H\}\_\{\\leq s\}^\{c\}, and by the definition of sublevel domain complexity,

N\(ℋ,c\)𝒳¯​\(s\)\>B​\(s\)\.N\_\{\(\\mathcal\{H\},c\)\}^\{\\bar\{\\mathcal\{X\}\}\}\(s\)\>B\(s\)\.\(63\)Thus the corollary holds withs0=S0s\_\{0\}=S\_\{0\}\. ∎

## Appendix EProofs for Online Learning

###### Proof of[Theorem14](https://arxiv.org/html/2607.16528#Thmtheorem14)\.

We first prove the upper bound whend:=Ldim⁡\(ℋ\)<∞d:=\\operatorname\{Ldim\}\(\\mathcal\{H\}\)<\\infty, using the conventionLdim⁡\(∅\)=−1\\operatorname\{Ldim\}\(\\emptyset\)=\-1\. The learner maintains the version spaceVn⊆ℋV\_\{n\}\\subseteq\\mathcal\{H\}of hypotheses consistent with all labels revealed before levelnn\. ThusV1=ℋV\_\{1\}=\\mathcal\{H\}, and after levelnnis revealed the version space is restricted to hypotheses consistent with the new labels\.

For a pointxxand a labelb∈\{0,1\}b\\in\\\{0,1\\\}, write

Vn​\(x,b\):=\{h∈Vn:h​\(x\)=b\}\.V\_\{n\}\(x,b\):=\\\{h\\in V\_\{n\}:h\(x\)=b\\\}\.\(64\)Before seeing the labels on𝒳n∖𝒳n−1\\mathcal\{X\}\_\{n\}\\setminus\\mathcal\{X\}\_\{n\-1\}, the learner predicts at eachxxa labelbbmaximizingLdim⁡\(Vn​\(x,b\)\)\\operatorname\{Ldim\}\(V\_\{n\}\(x,b\)\), breaking ties arbitrarily\. After all labels at levelnnare revealed, it updates the version space to the subset ofVnV\_\{n\}consistent with the whole increment\.

We claim that every mistaken level strictly decreases the Littlestone dimension of the version space\. Suppose levelnnis mistaken\. Then for somex∈𝒳n∖𝒳n−1x\\in\\mathcal\{X\}\_\{n\}\\setminus\\mathcal\{X\}\_\{n\-1\}, the learner predicted1−b1\-bwhile the true label isb=f​\(x\)b=f\(x\)\. Since the learner chose a label of maximum Littlestone dimension,

Ldim⁡\(Vn​\(x,1−b\)\)≥Ldim⁡\(Vn​\(x,b\)\)\.\\operatorname\{Ldim\}\(V\_\{n\}\(x,1\-b\)\)\\geq\\operatorname\{Ldim\}\(V\_\{n\}\(x,b\)\)\.\(65\)BothVn​\(x,0\)V\_\{n\}\(x,0\)andVn​\(x,1\)V\_\{n\}\(x,1\)are subclasses ofVnV\_\{n\}, so their Littlestone dimensions are at mostLdim⁡\(Vn\)\\operatorname\{Ldim\}\(V\_\{n\}\)\. IfLdim⁡\(Vn​\(x,b\)\)=Ldim⁡\(Vn\)\\operatorname\{Ldim\}\(V\_\{n\}\(x,b\)\)=\\operatorname\{Ldim\}\(V\_\{n\}\), then alsoLdim⁡\(Vn​\(x,1−b\)\)=Ldim⁡\(Vn\)\\operatorname\{Ldim\}\(V\_\{n\}\(x,1\-b\)\)=\\operatorname\{Ldim\}\(V\_\{n\}\), and placingxxat the root above two shattered trees of depthLdim⁡\(Vn\)\\operatorname\{Ldim\}\(V\_\{n\}\)would shatter a tree of depthLdim⁡\(Vn\)\+1\\operatorname\{Ldim\}\(V\_\{n\}\)\+1, a contradiction\. Hence

Ldim⁡\(Vn​\(x,b\)\)<Ldim⁡\(Vn\)\.\\operatorname\{Ldim\}\(V\_\{n\}\(x,b\)\)<\\operatorname\{Ldim\}\(V\_\{n\}\)\.\(66\)The updated version space after the whole increment is contained inVn​\(x,b\)V\_\{n\}\(x,b\), so its Littlestone dimension is also strictly smaller thanLdim⁡\(Vn\)\\operatorname\{Ldim\}\(V\_\{n\}\)\. Since the dimension starts atddand never goes below zero, at mostddlevels can be mistaken\.

For the lower bound, letddbe any integer such thatℋ\\mathcal\{H\}shatters a complete binary tree of depthdd\. We show that every deterministic learner can be forced to makeddmistakes; ifLdim⁡\(ℋ\)=∞\\operatorname\{Ldim\}\(\\mathcal\{H\}\)=\\infty, this holds for every finitedd\.

The adversary follows a shattered tree\. At the root, it presents the root instance as the first singleton increment\. If the learner predicts0, the adversary reveals label11; if the learner predicts11, it reveals label0\. The adversary then moves to the child corresponding to the revealed label and repeats this procedure forddlevels\. By shattering, the resulting root\-to\-leaf sequence of labels is realized by some targetf∈ℋf\\in\\mathcal\{H\}\.

The points along the realized path are distinct\. If the same point appeared twice on one root\-to\-leaf path, then at the later occurrence the two outgoing branches would require both labels while the earlier occurrence has already fixed one label, contradicting shattering\. Thus the path points can be used as distinct singleton increments of a hierarchy, which is then completed arbitrarily to exhaustΩ\\Omega\. By construction, the learner makes one mistake at each of the firstddlevels\. Therefore no learner can have a uniform mistake bound smaller thandd\. Taking the supremum over all shattered depths gives the lower boundLdim⁡\(ℋ\)\\operatorname\{Ldim\}\(\\mathcal\{H\}\)\. ∎

###### Proof of[Section7\.1](https://arxiv.org/html/2607.16528#S7.SS1.SSS0.Px1)\.

Ifℋ\\mathcal\{H\}shatters a complete binary tree of depthdd, then the2d2^\{d\}root\-to\-leaf label sequences must be realized by2d2^\{d\}distinct hypotheses: two paths that first diverge at a node assign different labels to the same instance at that node\. Hence, whenℋ\\mathcal\{H\}is finite,

2d≤\|ℋ\|2^\{d\}\\leq\|\\mathcal\{H\}\|\(67\)for every shattered depthdd, soLdim⁡\(ℋ\)≤log2⁡\|ℋ\|<∞\\operatorname\{Ldim\}\(\\mathcal\{H\}\)\\leq\\log\_\{2\}\|\\mathcal\{H\}\|<\\infty\.

Now supposeLdim⁡\(ℋ\)=d<∞\\operatorname\{Ldim\}\(\\mathcal\{H\}\)=d<\\infty\. By[Theorem14](https://arxiv.org/html/2607.16528#Thmtheorem14), there is a deterministic online prediction rule that makes at mostddmistakes on every target and hierarchy\. Fix a singleton hierarchy enumeratingΩ\\Omega, say𝒳n=\{x1,…,xn\}\\mathcal\{X\}\_\{n\}=\\\{x\_\{1\},\\ldots,x\_\{n\}\\\}\.

For each targetf∈ℋf\\in\\mathcal\{H\}, letEf⊆ℕE\_\{f\}\\subseteq\\mathbb\{N\}be the finite set of times at which this learner makes a mistake when run againstffon the fixed hierarchy\. Then\|Ef\|≤d\|E\_\{f\}\|\\leq d\. The setEfE\_\{f\}determinesff: givenEfE\_\{f\}, replay the learner from the beginning; at timenn, compute its prediction from the labels reconstructed so far, and set the true label to be the prediction ifn∉Efn\\notin E\_\{f\}and the opposite label ifn∈Efn\\in E\_\{f\}\. This reconstructsf​\(xn\)f\(x\_\{n\}\)for everynn\. Since the hierarchy enumeratesΩ\\Omega, it reconstructsffon all ofΩ\\Omega\.

Thus the mapf↦Eff\\mapsto E\_\{f\}is injective fromℋ\\mathcal\{H\}into the collection of finite subsets ofℕ\\mathbb\{N\}of size at mostdd, which is countable\. Thereforeℋ\\mathcal\{H\}is countable\. ∎

###### Verification of[Example1](https://arxiv.org/html/2607.16528#Thmexample1)\.

The class shatters a one\-point tree: at any pointxjx\_\{j\}, the hypothesishjh\_\{j\}realizes label11, while anyhih\_\{i\}withi≠ji\\neq jrealizes label0\. HenceLdim⁡\(ℋsing\)≥1\\operatorname\{Ldim\}\(\\mathcal\{H\}\_\{\\mathrm\{sing\}\}\)\\geq 1\.

It cannot shatter a depth\-two tree\. If the root is labeled by some pointxjx\_\{j\}and the root label is11, then the only consistent target ishjh\_\{j\}\. All later labels are then fixed, so the next node cannot realize both outgoing labels\. Thus no depth\-two tree is shattered, andLdim⁡\(ℋsing\)=1\\operatorname\{Ldim\}\(\\mathcal\{H\}\_\{\\mathrm\{sing\}\}\)=1\.

Equivalently, the all\-zero online predictor makes at most one mistake on this class, namely when the unique positive point of the target singleton is revealed\.

Finally, consider the singleton hierarchy𝒳n=\{x1,…,xn\}\\mathcal\{X\}\_\{n\}=\\\{x\_\{1\},\\ldots,x\_\{n\}\\\}\. SupposeA2held along this hierarchy with some learner and common levelNN\. For everyi\>Ni\>N, the targethih\_\{i\}gives the same all\-zero labeled sample on𝒳N\\mathcal\{X\}\_\{N\}\. At levelNN, the learner would therefore receive the same input for all targetshih\_\{i\}withi\>Ni\>N, but would have to output each of these distinct targets\. This is impossible\. Hence no target\-uniform identification bound exists, soA2fails\. ∎

## Appendix FProofs for Approximation

###### Proof of[Section7\.2](https://arxiv.org/html/2607.16528#S7.SS2)\.

Choose three distinct hypotheses inℋ\\mathcal\{H\}\. Since the labels are binary, the three pairwise agreement sets coverΩ\\Omega; becauseΩ\\Omegais infinite, some pairf,gf,gagrees on infinitely many points\. SincePPhas full support andf≠gf\\neq g,

Δ:=P​\(\{f≠g\}\)\>0\.\\Delta:=P\(\\\{f\\neq g\\\}\)\>0\.\(68\)Setε:=Δ/3\\varepsilon:=\\Delta/3\. GivenMM, choose a finite setS⊆\{f=g\}S\\subseteq\\\{f=g\\\}of sizeMM, list these points first, and complete the list to a hierarchy with𝒳M=S\\mathcal\{X\}\_\{M\}=S\. Sincef\|S=g\|Sf\|\_\{S\}=g\|\_\{S\}, the learner returns the same predictor on the two training sets; call ith^\\hat\{h\}\. On every point whereffandggdisagree,h^\\hat\{h\}is wrong for at least one of the two targets\. Hence

Δ≤LP,f​\(h^\)\+LP,g​\(h^\)\.\\Delta\\leq L\_\{P,f\}\(\\hat\{h\}\)\+L\_\{P,g\}\(\\hat\{h\}\)\.\(69\)Therefore at least one of the two targets, sayu∈\{f,g\}u\\in\\\{f,g\\\}, hasLP,u​\(A​\(u\|𝒳M\)\)≥Δ/2\>εL\_\{P,u\}\(A\(u\|\_\{\\mathcal\{X\}\_\{M\}\}\)\)\\geq\\Delta/2\>\\varepsilon, and soNA,ε𝒳¯,P​\(u\)\>MN\_\{A,\\varepsilon\}^\{\\bar\{\\mathcal\{X\}\},P\}\(u\)\>M\. ∎

## Appendix GProofs for Out\-of\-Support Generalization

###### Proof of[Theorem17](https://arxiv.org/html/2607.16528#Thmtheorem17)\.

Enumerate the finite class asℋ=\{h1,…,hM\}\\mathcal\{H\}=\\\{h\_\{1\},\\ldots,h\_\{M\}\\\}and use the least\-index consistent learner: given a finite labeled sample, output the first hypothesis in the enumeration consistent with all observed labels, if one exists, and outputh1h\_\{1\}otherwise\. The learner ignores the order and multiplicity of repeated sample points\.

IfM=1M=1, the claim is immediate\. AssumeM≥2M\\geq 2\. For every pair of distinct hypotheseshj,hk∈ℋh\_\{j\},h\_\{k\}\\in\\mathcal\{H\}, define

Dj,k:=\{x∈Ω:hj​\(x\)≠hk​\(x\)\}\.D\_\{j,k\}:=\\\{x\\in\\Omega:h\_\{j\}\(x\)\\neq h\_\{k\}\(x\)\\\}\.\(70\)EachDj,kD\_\{j,k\}is nonempty and has positiveQQ\-mass becauseQQhas full support\. Let

α:=minj≠k⁡Q​\(Dj,k\)\>0\.\\alpha:=\\min\_\{j\\neq k\}Q\(D\_\{j,k\}\)\>0\.\(71\)If the sample contains at least one point from every pairwise disagreement set, then the observed labels distinguish the target from every other hypothesis inℋ\\mathcal\{H\}\. The least\-index consistent learner therefore outputs the target, and thePP\-error is zero\.

By a union bound, the probability of missing some pairwise disagreement set is at most

M​\(M−1\)​\(1−α\)n,M\(M\-1\)\(1\-\\alpha\)^\{n\},\(72\)which tends to zero asn→∞n\\to\\infty\. Hence for everyδ\>0\\delta\>0there is a finiteNNsuch that, for alln≥Nn\\geq N, the sample hits every pairwise disagreement set with probability at least1−δ1\-\\delta\. On this event, the learner outputs the target for everyf∈ℋf\\in\\mathcal\{H\}, and therefore hasPP\-error at mostε\\varepsilonfor every target\. This gives the target\-uniform bound\. ∎

###### Proof of[Theorem18](https://arxiv.org/html/2607.16528#Thmtheorem18)\.

Choose three distinct hypotheses inℋ\\mathcal\{H\}\. Their three pairwise agreement sets cover the infinite domainΩ\\Omega, so some pairu,v∈ℋu,v\\in\\mathcal\{H\}has an infinite agreement setEq⁡\(u,v\)\\operatorname\{Eq\}\(u,v\)\. Choose any distributionQQwith infinite support contained inEq⁡\(u,v\)\\operatorname\{Eq\}\(u,v\); for example, enumerate countably many distinct points inEq⁡\(u,v\)\\operatorname\{Eq\}\(u,v\)and assign them probabilities proportional to2−k2^\{\-k\}\.

Sinceu≠vu\\neq v, the disagreement set\{u≠v\}\\\{u\\neq v\\\}is nonempty\. BecausePPhas full support,

Δ:=P​\(\{u≠v\}\)\>0\.\\Delta:=P\(\\\{u\\neq v\\\}\)\>0\.\(73\)Chooseε<Δ/2\\varepsilon<\\Delta/2\.

Fix a learnerAAand a sample sizenn\. Samples fromQQalways lie inEq⁡\(u,v\)\\operatorname\{Eq\}\(u,v\), so the labeled sample given toAAis identical under targetuuand targetvv\. For any fixed sample sequence, leth^\\hat\{h\}be this common learner output\. At each point whereuuandvvdisagree,h^\\hat\{h\}is wrong for at least one of the two targets\. Therefore

LP,u​\(h^\)\+LP,v​\(h^\)≥Δ\.L\_\{P,u\}\(\\hat\{h\}\)\+L\_\{P,v\}\(\\hat\{h\}\)\\geq\\Delta\.\(74\)Thus, for every sample sequence, at least one of the two targets has error larger thanε\\varepsilon\. Averaging overQnQ^\{n\}, at least one of the two targets has failure probability at least1/21/2\. SinceAAandnnwere arbitrary, this holds for every learner and every sample size; in particular, it holds for everyNNand everyn≥Nn\\geq N\. ∎

## Appendix HProofs for Positive\-Only Presentations

###### Proof of[Section7\.4](https://arxiv.org/html/2607.16528#S7.SS4)\.

First suppose

d:=supf,g∈ℋf≠g\|Pos​\(f\)∩Pos​\(g\)\|<∞\.d:=\\sup\_\{\\begin\{subarray\}\{c\}f,g\\in\\mathcal\{H\}\\\\ f\\neq g\\end\{subarray\}\}\|\\mathrm\{Pos\}\(f\)\\cap\\mathrm\{Pos\}\(g\)\|<\\infty\.\(75\)Define a learner as follows\. Given a finite positive setSS, if there is a uniqueh∈ℋh\\in\\mathcal\{H\}such thatS⊆Pos​\(h\)S\\subseteq\\mathrm\{Pos\}\(h\), output thathh; otherwise output an arbitrary binary predictor\.

Fix a targetf∈ℋf\\in\\mathcal\{H\}and a positive presentationS¯∈Pres\+​\(f\)\\bar\{S\}\\in\\mathrm\{Pres\}^\{\+\}\(f\)\. Since the presentation is increasing and every step adds a positive point,\|St\|≥t\|S\_\{t\}\|\\geq t\. Hence\|St\|≥d\+1\|S\_\{t\}\|\\geq d\+1for everyt≥d\+1t\\geq d\+1\. Nog≠fg\\neq fcan contain all points inStS\_\{t\}, because then\|Pos​\(f\)∩Pos​\(g\)\|≥\|St\|≥d\+1\|\\mathrm\{Pos\}\(f\)\\cap\\mathrm\{Pos\}\(g\)\|\\geq\|S\_\{t\}\|\\geq d\+1, contradicting the definition ofdd\. Thusffis the unique hypothesis whose positive region containsStS\_\{t\}, and the learner outputsfffor allt≥d\+1t\\geq d\+1\.

Conversely, suppose

supf,g∈ℋf≠g\|Pos​\(f\)∩Pos​\(g\)\|=∞\.\\sup\_\{\\begin\{subarray\}\{c\}f,g\\in\\mathcal\{H\}\\\\ f\\neq g\\end\{subarray\}\}\|\\mathrm\{Pos\}\(f\)\\cap\\mathrm\{Pos\}\(g\)\|=\\infty\.\(76\)LetAAbe any learner and letN<∞N<\\infty\. Choosef≠gf\\neq gwith\|Pos​\(f\)∩Pos​\(g\)\|≥N\|\\mathrm\{Pos\}\(f\)\\cap\\mathrm\{Pos\}\(g\)\|\\geq N, and choose distinct pointsx1,…,xN∈Pos​\(f\)∩Pos​\(g\)x\_\{1\},\\ldots,x\_\{N\}\\in\\mathrm\{Pos\}\(f\)\\cap\\mathrm\{Pos\}\(g\)\. Since both positive regions are infinite, we can extend the common initial sequence

St=\{x1,…,xt\},1≤t≤N,S\_\{t\}=\\\{x\_\{1\},\\ldots,x\_\{t\}\\\},\\qquad 1\\leq t\\leq N,\(77\)to positive presentations of bothffandgg\. At timeNN, the learner receives the same input under the two targets\. It therefore gives the same output in both worlds, and cannot be correct for bothffandgg\. No learner can satisfy[Equation25](https://arxiv.org/html/2607.16528#S7.E25)with thisNN, and sinceNNwas arbitrary, no uniform finite bound exists\. ∎

#### An infinite example\.

The finite\-overlap condition can hold for infinite classes\. LetΩ=ℕ×ℕ\\Omega=\\mathbb\{N\}\\times\\mathbb\{N\}and, fora,b∈ℕa,b\\in\\mathbb\{N\}, define

Ga,b:=\{\(t,a​t\+b\):t∈ℕ\},G\_\{a,b\}:=\\\{\(t,at\+b\):t\\in\\mathbb\{N\}\\\},\(78\)and letfa,bf\_\{a,b\}be the indicator ofGa,bG\_\{a,b\}\. EachPos​\(fa,b\)=Ga,b\\mathrm\{Pos\}\(f\_\{a,b\}\)=G\_\{a,b\}is infinite, and the class\{fa,b:a,b∈ℕ\}\\\{f\_\{a,b\}:a,b\\in\\mathbb\{N\}\\\}is countably infinite\. Two distinct such sets intersect in at most one point, since two distinct affine functions overℕ\\mathbb\{N\}agree at at most one input\. Hence the pairwise positive overlap is at most one, and two positive observations uniformly identify the target\.

## Appendix ILimitations and Scope

Our results are information\-theoretic: they characterize when identification is possible, not how to compute the identifying level for a given\(ℋ,c,𝒳¯\)\(\\mathcal\{H\},c,\\bar\{\\mathcal\{X\}\}\)\. Three structural restrictions are worth noting\. First, we work in the realizable, deterministic\-labeling setting; agnostic and noisy presentations are deferred to future work\. Second, we focus on exact identification; approximate analogues withε\\varepsilon\-error are discussed in[Section7\.2](https://arxiv.org/html/2607.16528#S7.SS2)\. Third, the framework is set\-indexed rather than sequence\-indexed, hiding within\-level order; online\-learning variants are discussed in[Section7\.1](https://arxiv.org/html/2607.16528#S7.SS1)\. The work is theoretical and does not raise direct societal concerns\.