Many expensive design problems have identical parts that can be swapped without changing the objective. Examples are twelve identical current-drive launchers in a fusion reactor, identical wireless access points, and identical particles in a packing. A search method that ignores this treats every relabeling of the same design as a new point and pays for the same information many times over. Bayesian optimization is a sample-efficient search method that fits a probabilistic surrogate to past evaluations, and there are two standard ways to tell its surrogate about the symmetry. The first averages the similarity function (the kernel) over every symmetry. This comes with a guarantee, but it blurs the surrogate and costs a sum over the whole group. The second takes the maximum over all symmetries, which works better in practice but has no guarantee and needs an eigenvalue-clipping repair because the result is not a valid kernel.
This note proposes a third option, borrowed from symmetry breaking in constraint programming. Map each input to a canonical representative of its symmetry class, for instance by sorting, and then apply an ordinary kernel. The resulting kernel is valid by construction and costs one canonicalization per point (for twelve launchers, a sort instead of a sum over 479 million permutations). It also inherits the standard high-probability regret bound, a guarantee that holds on all but a fraction $\delta$ of runs, with the problem's complexity measured only on one symmetry cell. For the common case of permutations of scalar coordinates, I argue this kernel is exactly the max kernel, which would explain why the max kernel works and supply the guarantee it lacks. For harder groups, the choice of canonical ordering decides where the kernel has seams. That turns a known lesson from combinatorial search, that the ordering should agree with the search, into a quantity we can measure.
Core Claim
Let $G$ be a finite group acting on the search domain $X$. Let $F \subset X$ be a fundamental domain, meaning a region containing exactly one representative of each orbit. Let $c: X \to F$ be any computable canonical map, such as a lex-leader rule. For a base kernel $k$, define the canonical-ordering kernel
$$k_c(x, y) = k(c(x), c(y)).$$
This is $k$ composed with a feature map, so it is positive semi-definite with no projection step. If the objective $f$ is $G$-invariant and lies in the function space defined by $k$ with norm at most $B$, then $f = (f|_F)\circ c$. Restricting a function to a smaller region can only lower its norm, so $f|_F$ has norm at most $B$ in the space defined by $k$ on $F$.
The standard GP-UCB analysis then applies unchanged. GP-UCB picks the point whose upper confidence bound is highest, and its usual high-probability argument is the one invoked by Sample-efficient Bayesian Optimisation Using Known Invariances. It gives, with probability at least $1-\delta$,
$$R_T = O\left(\sqrt{T\,\beta_T\,\gamma_T(k; F)}\right), \qquad \beta_T = O\left(B + \sqrt{\gamma_T(k;F) + \log(1/\delta)}\right).$$
Here $R_T$ is cumulative regret after $T$ evaluations. The quantity $\gamma_T(k;F)$ is the maximum information gain, a measure of how much $T$ noisy observations can reveal about functions under kernel $k$, computed on the cell $F$ rather than on all of $X$. The guarantee is high-probability in the sense of Direction 2, with only logarithmic dependence on $1/\delta$. It does not rely on the linearity of group averaging, which is the step the max-kernel analysis could not reuse.
The second claim is sharper and falsifiable. Suppose $G$ permutes scalar coordinates, so that $X \subset \mathbb{R}^n$ and $F$ is the sorted region $x_1 \le \dots \le x_n$. Suppose also that $k$ is a stationary kernel that decreases with distance. By the rearrangement inequality, $\min_\sigma \|\sigma x - y\|$ is attained by sorting both vectors. The max kernel $\max_{g,g'} k(gx, g'y)$ studied in Symmetry-Aware Bayesian Optimization via Max Kernels therefore equals $k(\mathrm{sort}\,x, \mathrm{sort}\,y) = k_c(x,y)$. In this setting the max kernel is already positive semi-definite, the eigenvalue clipping should remove nothing beyond numerical error, and the reported "spectral paradox" should disappear. That paradox is slower eigendecay together with lower regret. On this account it comes from measuring eigendecay on the whole domain instead of on the cell.
The equivalence breaks for groups that permute blocks of coordinates, such as 2D particle positions. There the minimum-distance alignment is an assignment problem. In that case any fixed canonical map creates seams: two configurations that are close in the quotient can land far apart in $F$. Where the seams fall depends on the ordering.
Research Program
The theoretical part has three pieces. The first is a careful proof of the regret bound above for arbitrary finite groups and measurable canonical maps. The second is a proof of the max-kernel equivalence for reflection-type actions, meaning coordinate permutations and sign flips, for which sorted or absolute-valued chambers give a quotient distance that coincides with Euclidean distance inside the cell. The third is a comparison of $\gamma_T(k;F)$ against the roughly $\gamma_T/|G|$ reduction proved for averaged kernels. I do not expect a clean universal ordering between the two, so this comparison will be computed numerically for Matérn and squared-exponential kernels on the benchmark domains.
The methodological part treats the canonical map as a design choice, following Direction 1. Breaking Symmetry with Different Orderings showed that Gray-code and snake orderings that agree with the solver's heuristic beat plain lex-leader by large factors. Static Symmetry Breaking with the Reflex Ordering showed that an ordering keyed to values and their first positions prunes composite symmetries far better than lex-leader. Both papers concern discrete search, and both treat the ordering only as pruning. In BO, the ordering instead decides where the surrogate cannot share information. For block groups I will compare three orderings: lex order on the first coordinate, a reflex-style order on (value, earliest position), and an assignment-based order that sorts blocks by their matching to a running incumbent. The hypothesis is that orderings whose seams stay away from the current best design lose little relative to the max kernel. Orderings whose seams pass through it lose a lot.
The evaluation lens comes from Direction 2. Mean regret over seeds can hide runs that fail completely, the same phenomenon SGD Can Converge to Local Maxima exhibits for SGD. I will therefore report upper quantiles of simple regret across many seeds as well as means. As a secondary arm, I will replace Gaussian observation noise with Student-t noise and estimate each point's value from repeated evaluations using a median-of-means estimator, the robust estimator that High probability guarantees for stochastic convex optimization uses inside proxBoost. Canonicalization composes with this estimator unchanged. I claim no new heavy-tailed regret theorem; this arm only tests whether the ordering of methods is stable under heavy tails.
Baselines
The naive reference is the base kernel with no symmetry information, run with the same GP-UCB acquisition, the same lengthscale-fitting routine, the same initial design and the same evaluation budget. Every method must beat it. A method that fails to on PermInv-6D would contradict the reported finding in Sample-efficient Bayesian Optimisation Using Known Invariances that the invariant method converged within 100–200 samples while standard baselines had not converged after 600.
The guaranteed competitor is the orbit-averaged kernel from that same paper. For small groups I will use the full group. For large groups I will use the order-24 subgroup that paper used for twelve launchers, since summing over the full group is infeasible. Canonical-ordering kernels beat it if they reach $\epsilon$-optimality in fewer evaluations, or achieve lower regret at the 90th percentile of runs, at equal budget and lower wall-clock cost per acquisition step.
The strongest existing method is the projected max kernel with Nyström extension from Symmetry-Aware Bayesian Optimization via Max Kernels. That paper reports up to 50% lower cumulative and simple regret than orbit averaging on Ackley, Griewank and Rastrigin, and higher utility on WLAN8d and PartPack6d. For the latter two I found no reported number on Lacuna, only the qualitative claim, so I will rerun it myself using the same group, base kernel, hyperparameter fitting and acquisition optimizer as all other arms.
On scalar-permutation tasks, "beating" the max kernel is not the goal. Matching it to within seed noise, at a fraction of the cost and with a guarantee, is the prediction. On block-permutation tasks, matching it with a well-chosen ordering would count as success. Falling clearly behind with every ordering would mark the limit of the approach.
Constrained BO on the fundamental domain is also a baseline. It is the method Sample-efficient Bayesian Optimisation Using Known Invariances found to perform poorly. I return to it below because it bears directly on the claimed equivalence.
The key ablation replaces each well-chosen canonical map with an arbitrary fixed one, ordering blocks by a random linear projection. This keeps validity and the guarantee but places seams without regard to the objective, which isolates the effect of ordering choice from the effect of canonicalization itself.
Why not just…?
Why not just use orbit averaging, which already has a guarantee? Averaging requires summing over the group, so it is restricted to subgroups once the group is large, as in the twelve-launcher case. It also dilutes similarity, because most group alignments are poor. That is the mechanism behind the max kernel's reported advantage of up to 50%. Canonicalization keeps the full group at the cost of a sort and keeps a guarantee. The experiments compare the two at equal evaluation budgets, and the tokamak arm, if the simulator is available, compares them at the group sizes where averaging must be truncated.
Why not just use the projected max kernel, since it already works? This is the real threat, and on block-permutation groups the max kernel may simply be better because it has no seams. Our response differs by regime. On scalar permutations, the claimed equivalence predicts identical regret, which makes the contribution a guarantee plus cheaper computation rather than a performance gain. On block groups, the gap between the max kernel and the best canonical ordering is itself the measurement we want. If that gap is large for every ordering, the honest conclusion is that canonicalization gives a guaranteed fallback but not a replacement there.
Why not just constrain the search to the fundamental domain? For reflection-type groups, constrained BO with every observation mapped into the cell should yield the same posterior as $k_c$. Its reported poor performance therefore conflicts with my equivalence claim, and I treat this as the decisive check rather than explaining it away. I will run constrained BO in two forms: one that maps observations into the cell and one that does not, each with both a boundary-respecting acquisition optimizer and a naive one. If the version with mapped observations and a good optimizer matches $k_c$ and the max kernel on PermInv tasks, the earlier failure came from the implementation. If it still underperforms, the equivalence argument is missing something and the claims narrow accordingly.
Why not just augment the data with every transformed copy? Gaussian-process inference scales cubically in the number of points, so $|G|$-fold augmentation is prohibitive beyond tiny groups. Sample-efficient Bayesian Optimisation Using Known Invariances makes this objection itself. Augmentation is included only on PermInv-2D, where it is cheap, as a sanity check that it matches the invariant kernels.
Why not just report mean regret and convert to a confidence statement with Markov's inequality? Markov's inequality turns a mean bound into a bound with $1/\delta$ dependence, which is useless at small $\delta$. More practically, means can hide a minority of runs that never find the right basin. Quantile reporting over many seeds tests directly whether a method's tail matches its average.
Proposed Experiments
The first experiment is an equivalence test on PermInv-2D/6D, CyclInv-3D and Dihedral-D5. On each, I will compute the projected max kernel's Gram matrices and record how much eigenvalue mass clipping removes. On PermInv, the prediction is zero up to numerical error. I will then run the base kernel, orbit averaging, the projected max kernel, constrained BO in both forms, and $k_c$ with sort canonicalization, using 50 or more seeds per arm. Outcomes are simple and cumulative regret at the median and 90th percentile, and the number of evaluations to $\epsilon$-optimality. Reporting the median and 90th percentile rather than only the mean is the Direction 2 lens. CyclInv and Dihedral are not pure coordinate permutations, so they test where the equivalence stops holding.
The second experiment addresses ordering. On Ackley, Griewank and Rastrigin under block permutations, and on PartPack6d and WLAN8d, I will compare the three orderings, the random-projection ablation and the max kernel. I will also log, at each step, the distance from the incumbent design to the nearest seam. The prediction is that the regret gap to the max kernel tracks how often the incumbent sits near a seam.
The third experiment covers scale and heavy tails. If the tokamak scenario is accessible, I will compare full-$S_{12}$ canonicalization against order-24 averaging. No numerical result for this task was found on Lacuna, so the comparison will be internal. Separately, the synthetic tasks will be rerun with Student-t noise of two to three degrees of freedom, with and without median-of-means evaluation, comparing tail regret across kernels.
The project is decisive in either direction. If $k_c$ matches the max kernel on permutation benchmarks and constrained BO done correctly matches both, then invariant BO has a cheap, valid kernel with a high-probability guarantee, and the spectral paradox is explained. If it does not, the failure will show exactly which step of the reduction to a single symmetry cell is wrong.