Overcoming the Factorial Bottleneck in Invariant Learning

This direction is split into other directions: group averaging intractability. Its last version stays readable and citable here.

Version 1 of 131 papers33 conceptsfrozen 2026-10-04

In geometric machine learning, symmetry is often described as a "free lunch." If we know a molecule is the same regardless of how its atoms are indexed, or that a medical image represents the same pathology regardless of its orientation, we can bake that knowledge into our models. This "invariance" drastically reduces the amount of data needed to train a model, as it no longer has to learn these rules from scratch.

However, a significant computational wall stands in the way: the Factorial Bottleneck. While enforcing symmetry is mathematically elegant, doing so exactly for large groups—especially permutations—is often computationally impossible. Recent research has shifted from exhaustive group operations toward spectral approximations and robust frames to make symmetry-aware learning practical.

The Cost of Perfection

The most intuitive way to make a function invariant to a group of transformations is through group averaging. To ensure a model $f(x)$ treats all versions of $x$ (its "orbit") the same, we simply average the model's output over every possible transformation $g$ in the group $G$:

$$f_{inv}(x) = \frac{1}{|G|} \sum_{g \in G} f(gx)$$

As Fernando Perez-Cruz and colleagues noted in their work on symmetric kernels, this approach hits a wall as the number of elements increases. For a set of $n$ objects, there are $n!$ (n-factorial) possible permutations. If $n=10$, there are 3.6 million permutations; if $n=20$, the number exceeds the number of grains of sand on Earth.

This scaling issue isn't just a theoretical nuisance. Theodore Brown and his team demonstrated that in Bayesian Optimization, incorporating full permutation invariance into a kernel creates a trade-off where the mathematical rigor of the model quickly outpaces the available computing power. Similarly, David Ginsbourger et al. showed that averaging kernels over group orbits introduces a quadratic cost relative to the group size, making high-order symmetries intractable for standard Gaussian Processes.

The Exponential Separation

Why is symmetry so expensive? Behrooz Tahmasebi and Melanie Weber recently proved a fundamental exponential separation between exact and approximate symmetry. They showed that while the cost of enforcing exact invariance scales linearly with the size of the group $|G|$, achieving approximate invariance (within some error $\epsilon$) only requires a number of operations that scales logarithmically with the group size.

This finding suggests that the quest for perfect symmetry in large-scale problems is often the wrong goal. Instead, the field is moving toward methods that "shortcut" the group sum.

Shortcut 1: Spectral Averaging

One way to avoid summing over millions of permutations is to move the problem into the "frequency domain." Just as a Fourier transform can simplify complex signals, representation theory can simplify group actions.

Ashkan Soleymani, Behrooz Tahmasebi, and their collaborators introduced "Spectral Averaging" (Spec-Avg). By working with the spectral domain of the Laplace-Beltrami operator, they reduced the computational cost of exact symmetry from exponential to logarithmic relative to the group size. This allows models to maintain mathematical exactness without the factorial overhead. Similarly, Sergey Plis and colleagues leveraged directional statistics to map discrete permutations onto continuous hyperspheres, bypassing the bottlenecks of traditional Fourier transforms on the symmetric group.

Shortcut 2: Robust Frames and Canonicalization

Another common strategy is canonicalization: picking one "standard" orientation for every object (e.g., always rotating a 3D shape so its longest axis points up). If you can always find this unique representative, you only need to evaluate the model once.

However, Nadav Dym, Hannah Lawrence, and Jonathan W. Siegel proved that for many important groups like rotations and permutations, continuous canonicalization is mathematically impossible. Small changes in the input can lead to jumps in the "canonical" choice, making the model unstable. To solve this, they proposed robust frames—weighted distributions over a small subset of group elements. This provides a middle ground: it is more efficient than exhaustive averaging but avoids the discontinuities of simple canonicalization.

Shortcut 3: Learned Alignment and Function Sharing

In specific domains like optimization, researchers are finding ways to "learn" the symmetry rather than hard-coding the entire group. Qian Chen and colleagues developed SymILO, which treats permutations as learnable parameters to align neural network predictions with symmetric ground-truth labels in Integer Linear Programming.

In architecture design, Ran Elbaz and Haggai Maron introduced FS-KAN, which achieves permutation equivariance by sharing learnable functions across the network. This approach scales with the number of "orbits" (distinct types of relationships) rather than the total number of permutations, making it much more efficient for complex data structures.

Summary

The research direction is clear: while the "factorial explosion" of groups like the symmetric group once made exact invariance a luxury for small datasets, new tools are breaking the bottleneck. By moving from exhaustive summation to spectral methods (Soleymani et al.), robust frames (Dym et al.), and approximate symmetries (Tahmasebi & Weber), machine learning can finally scale the benefits of symmetry to high-dimensional, real-world problems.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_overcoming_the_factorial_bottleneck_in_i_c1187ba0,
  title = {Overcoming the Factorial Bottleneck in Invariant Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/overcoming-the-factorial-bottleneck-in-invariant-learning/rdr_c1187ba0948947dbb1309f33f17a60da},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_overcoming_the_factorial_bottleneck_in_i_c1187ba0_v1,
  title = {Overcoming the Factorial Bottleneck in Invariant Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/overcoming-the-factorial-bottleneck-in-invariant-learning/rdr_c1187ba0948947dbb1309f33f17a60da/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}