Bridging the Size Gap: A Unified Sampling Theory for Variable-Size Learning

Paper: 2607.07680 Authors: Eitan Levin, Venkat Chandrasekaran Categories: math.ST, cs.LG, math.PR

The Gap

Modern ML models routinely handle inputs of variable size — GNNs process graphs with different node counts, transformers consume sequences of varying length, point cloud networks ingest unordered sets of arbitrary cardinality. But here’s the uncomfortable truth: we train these models on finitely many examples of necessarily limited size, and we have almost no theory for how they generalize from, say, 100-node graphs to 10,000-node graphs.

Prior work attacked this piecemeal. Graph theory had its own heuristics for subgraph sampling. NLP had padding and positional encodings. Point cloud processing had farthest-point sampling. Each domain reinvented the wheel, and none offered a principled answer to two fundamental questions: (1) How do you compare inputs of different sizes? (2) How do you sketch a large input into a small one while preserving a model’s output?

This paper steps back and asks: is there a unified mathematical framework that handles all of these? The answer is yes, and the key ingredient is random sampling maps — generalized projections from size-N inputs to size-n inputs — parameterized by the symmetries of the domain.

Variable-size          No unified            Sampling maps           Continuity          Unified
  inputs          -->  theory for       -->   generalize from   -->  w.r.t. sampling  --> generalization
  (graphs, seq.,       comparing             size N to size n       yields explicit      & sketching
  points, tensors)     across sizes          using domain-aware     rates for known      rates across
                                             strategies             function classes     all domains
                                                |                       |                    |
                                         - replacement             - moment poly.        Covers GNNs,
                                         - binning                 - homomorphism        transformers,
                                         - species                 - GNNs, xformers      and more

The Increment

One sentence: Before this paper, every domain had ad hoc tricks for handling variable-size inputs; after, there’s a single sampling-based framework with explicit generalization and sketching rates governed by domain symmetries.

Core Mechanism

The framework works as follows. You have an input X of size N (a graph with N nodes, a sequence of N tokens, a point cloud of N points). You want to evaluate a function f on this input, but either (a) you only trained on inputs of size n < N and need to know how well f generalizes, or (b) evaluating f on X is expensive and you want a cheap approximation. Both problems reduce to: find a small “sketch” X’ of size n that preserves f.

The bridge between X and X’ is a sampling map — a randomized function π that takes a size-N input and produces a size-n input. The paper identifies three fundamental families of sampling maps, each suited to different domain structures:

1. Sampling with replacement: Pick n elements uniformly at random from the N available. This respects full permutation symmetry — the order/identity of elements doesn’t matter.
2. Random binning: Partition the N elements into n random bins and aggregate. This respects partition symmetries and is natural when spatial or structural grouping matters.
3. Species sampling: Sample elements while tracking “types” (analogous to species in ecology). This handles settings where rare patterns carry disproportionate signal.

The technical core is a continuity condition: the function f must not change too much when you replace an input X by a random sketch f(π(X)). If f is “Lipschitz with respect to the sampling map” — meaning E[|f(π(X)) - f(X)|] ≤ ε — then the paper gives explicit bounds on both generalization error (training on small inputs, testing on large ones) and sketching error (replacing large inputs by small sketches).

Input X (size N)
      |
      +---> Choose sampling strategy based on domain symmetries
      |         |                    |                    |
      |    [replacement]       [binning]            [species]
      |    (permutation-       (partition-          (type-
      |     symmetric)          symmetric)           symmetric)
      |         |                    |                    |
      |         v                    v                    v
      |    Sketch X' (size n)  Sketch X' (size n)  Sketch X' (size n)
      |         |                    |                    |
      +---> Continuity check: is E[|f(X') - f(X)|] small?
                  |
                  v
            If yes: generalization + sketching rates follow
            (explicit bounds in terms of N, n, Lipschitz constant)

The forest metaphor: Imagine you’re an ecologist who has built a forest-health model trained on small 100-hectare plots. Now you need to assess a 10,000-hectare forest. You can’t survey every tree, but you need your model’s prediction to be trustworthy.

The question is: how do you pick your sample? If the forest is roughly homogeneous — any 100 trees are as representative as any other — you just pick trees at random (sampling with replacement). But if the forest has distinct zones — wetland, old-growth, clearcut — you need to sample from each zone proportionally (random binning). And if what matters is whether you encounter rare species like ghost orchids, you need a sampling strategy that deliberately searches for rare types (species sampling).

The paper’s key insight: if your forest-health metric doesn’t fluctuate much when you go from surveying every tree to surveying a random subset (continuity), then a small sample from a huge forest is almost as good as the real thing. And which sampling strategy to use is dictated by the forest’s natural structure — its symmetries. The framework then tells you exactly how many hectares you need to survey (the sketching rate) and how well your small-plot model extrapolates (the generalization rate).

Key Concepts

• Sampling maps: Think of a sampling map as a “resize” operation for structured data. If you have a graph with 1,000 nodes and your model only handles 100 nodes, a sampling map is a principled way to shrink the graph to 100 nodes. It’s not arbitrary downsampling — it’s a *randomized reduction that preserves structure in expectation. Concretely, if your graph has a community structure, a good sampling map might randomly select a few nodes from each community rather than just picking the first 100 nodes.

• Continuity with respect to sampling: This is the paper’s load-bearing assumption. A function f is “continuous with respect to sampling” if replacing an input by a random subsample doesn’t change f’s value much — in expectation over the randomness. This is analogous to Lipschitz continuity, but the “distance” between X and Y is defined by how much f changes under a random sampling map, not by Euclidean distance. If your model is smooth in this sense, good things follow. If it’s brittle to subsampling (e.g., a single outlier node determines the output), the theory doesn’t apply — and that’s a useful diagnostic in itself.

• Species sampling: This is the most exotic of the three strategies, borrowed from classical statistics (Efraim, 1972). Imagine you’re sampling words from a corpus to estimate vocabulary statistics. A simple random sample might miss rare words entirely. Species sampling is a strategy that explicitly accounts for the *types you encounter, ensuring rare types are represented. In the ML context, this is natural for functions like homomorphism densities in graph theory, where rare subgraph patterns (analogous to rare species) carry important structural information.

Framework Shift

Before (mainstream approach):           After (this paper):
                                        
Graphs  --> GNN + message passing       All domains:
Seq.    --> Transformer + padding           Input (size N)
Points  --> FPS + voxel grids                    |
Tensors --> Decomposition                      |
           [each domain, own tricks]       [Sampling Map]
                                           (chosen by symmetry)
                                                |
                                           Sketch (size n)
                                                |
                                           f(sketch) ~ f(input)
                                           [unified rates]

From domain-specific heuristics to a single sampling-based theory, the core shift is treating variable-size generalization as a continuity problem with respect to randomized sampling maps.

Expert Assessment

Problem choice: This is a genuine gap, not manufactured. Variable-size inputs are everywhere — GNNs, set functions, transformers on variable-length sequences — and the lack of a unified generalization theory across sizes is a real hole. The paper positions itself at the intersection of statistical learning theory and combinatorics, which is a productive but sparsely populated niche. The problem is well-motivated and timely.

Method maturity: The approach is elegant, not brute force. The insight that sampling strategy should be chosen based on domain symmetries is the kind of unifying observation that justifies a framework paper. The three sampling families (replacement, binning, species) are well-chosen and natural. One concern: the continuity assumption is doing a lot of heavy lifting. How often do real-world models satisfy it? The paper provides examples (moment polynomials, homomorphism densities, GNNs, transformers), but the verification for deep models may require nontrivial effort that practitioners won’t undertake.

Experimental integrity: This is a pure theory paper, so “experiments” are instantiations of the framework to specific function classes. The examples are convincing — moment polynomials and homomorphism densities are canonical objects where the framework fits naturally. The extension to GNNs and permutation-invariant transformers is important for ML relevance. However, there are no empirical experiments showing these bounds are tight or practically meaningful. A table comparing theoretical rates against empirical convergence would strengthen the paper significantly.

Writing quality: The abstract is unusually clear and well-structured for a theory paper. The logical flow from problem to framework to examples is clean. One area that could be improved: the paper would benefit from a dedicated “practical guide” section telling practitioners how to (a) identify which sampling family applies to their domain and (b) estimate the continuity constant for their model. Without this, the framework risks being admired but unused.

Verdict: weak accept — Elegant unification of a real problem, but the gap between theoretical rates and practical applicability remains unbridged. The framework is a solid foundation; the question is whether follow-up work will make it actionable.

Takeaways

Three concrete ideas to steal:

1. Test your model’s stability under subsampling: Before deploying a variable-size model, measure how much its output changes when you randomly subsample inputs by 50%, 75%, 90%. If the output is stable, you can confidently evaluate on sketches of large inputs. If it’s not, your model is brittle in a way you should know about — this is a free diagnostic.

2. Choose your downsampling strategy by symmetry: If your data is permutation-invariant (sets, unordered point clouds), uniform random sampling is the right reduction. If it has spatial/group structure (images, grids, spatial graphs), use random binning. If rare patterns carry signal (biology, social networks), use species-style sampling that preserves type diversity. Don’t just grab the first k elements.

3. The continuity condition as a design principle: When designing architectures for variable-size inputs, explicitly encourage continuity with respect to sampling — e.g., through architectural choices that make outputs robust to subsampling (mean-pooling over random subsets during training as a regularizer). This isn’t just good practice; it’s the condition that makes generalization across sizes theoretically guaranteed.