betaFeedback

WorksComputer Science

Test-Time Symmetrization: Scaling Laws for Model-Agnostic Learning under Structure

Abstract

Test-time compute has emerged as a powerful way to improve the accuracy of language models at inference time, with scaling laws quantifying how accuracy improves with additional forward passes. Existing scaling laws, however, focus on repeated sampling from a fixed prompt, even though many tasks admit multiple equivalent representations of the same underlying problem. A graph does not depend on how its nodes are numbered, and a program does not depend on the names of its variables, yet language models can change their answers under such rewritings. In this paper, we study test-time symmetrization, which uses forward passes on rewritings of the input and aggregates the resulting answers over the group GG of rewritings. We prove that no amount of sampling and repeated decoding from a single representation can replace rewriting, while only O(log⁡∣G∣)O(\log |G|) random rewritings suffice to recover the information provided by all ∣G∣|G| rewritings. The same set of O(log⁡∣G∣)O(\log |G|) rewritings provides simultaneous approximation across models, decoding rules, and sampled reasoning traces, and the logarithmic scaling is optimal in general. We validate the theory with experiments on Qwen2.5-7B, Phi-4-mini, Llama-3.1-8B, and Qwen2.5-14B, with chain-of-thought reasoning, on graph reasoning, logical deduction, and multiple-choice question answering. At the same number of forward passes, spending them on rewritings of the input is substantially more accurate than spending them on repeated sampling from the original prompt whenever the model's answer depends on how the input is written, and the number of rewritings needed grows only logarithmically with the number of possible rewritings, as the theory predicts. Our results provide a principled way to enforce symmetries at inference time when they cannot be built into the model, which we call model-agnostic symmetrization.

Introduction

Test-time compute is now a standard way to improve a language model whose weights are fixed. A longer reasoning trace (Wei et al., [86]), a majority vote over several traces (Wang et al., [85]), or a verifier that selects among candidates (Cobbe et al., [18]; Lightman et al., [43]) each convert extra forward passes into accuracy, and scaling laws predict the return on each pass (Brown et al., [12]; Snell et al., [70]). All of these methods query the model again on the same prompt: the randomness they exploit is that of decoding.

A second source of variation is rewriting. Relabeling the nodes of a graph, permuting the options of a multiple-choice question, renaming the variables of a program, or reordering in-context examples changes the prompt but not its meaning. These rewritings move the input along an orbit of equivalent representations, and a forward pass spent on a rewriting asks the same question in a different form. The two sources are not interchangeable. Repeated decoding explores the model at one representation and reveals nothing about its behavior elsewhere on the orbit (Figure 1).

Rewriting by $G$ explores the orbit of equivalent representations

Figure 1. Rewriting by GG explores the orbit of equivalent representations, while the frozen model pθp_\theta samples reasoning traces at each representation. Full orbit averaging uses ∣G∣|G| rewrites; test-time symmetrization uses only O(log⁡∣G∣)O(\log|G|) random rewrites with a few traces each.

Indeed, frozen models are far from constant along the orbit. Reordering answer options or few-shot examples changes benchmark scores and model rankings (Zheng et al., [92]; Lu et al., [47]; Sclar et al., [67]; Mizrahi et al., [54]), and the same instability appears for graph serializations and identifier names (Herbst et al., [28]; Miceli Barone et al., [52]). Querying several rewritings and combining the answers helps: permutation-based calibration reduces option-order bias [92], prompt ensembles improve on single prompts [30, 4], and at matched compute, paraphrasing the input can beat sampling more traces [35]. These remedies are empirical, and three basic questions remain open: can more decoding replace rewriting, how many rewritings are enough, and how should rewriting be combined with decoding? Kozodoi et al. [35] point to the last one, the balance between input-side and output-side diversity, as a direction for future work. This paper takes up these questions.

Rewriting is necessary. We construct two models whose responses agree on every trace at the original prompt but lead to different decisions once averaged over the orbit. No decoding procedure, adaptive or not, can tell them apart, however many traces it draws (Theorem 1).

Logarithmically many rewritings suffice. Note that a full pass over the group is out of reach: a graph on 20 nodes has 20!≈2×101820! \approx2 \times10^{18} relabelings. We prove that a random set of rewritings whose size grows with log⁡∣G∣\log|G| approximates the full group average in mean square over starting representations, and that the logarithm cannot be improved in general (Theorem 2). The set is drawn once and serves every frozen model at the same time. This uniformity is what makes the guarantee model-agnostic. Indeed, even though equivariant architectures build symmetry into the network during training, a frozen model that allows no such modification can still exploit task symmetries imposed externally through pre- and post-processing, at a logarithmic cost.

Any decoding rule can be used. The same set of rewritings also serves every decoding rule. The traces at one rewriting may be combined by majority vote, expected logits, verifier weighting, or any other rule, at any generation temperature, and the result is again a function on the group. The scaling law holds for all such functions at once, including every realized randomized decoder, so the decoding rule can be chosen after the rewritings are drawn (Theorem 3). Any decomposition separates the accuracy of the fully symmetrized model from the cost of approximating it (Theorem 4), and the number of rewritings and the number of traces per rewriting can be set independently (Section C).

In short, in this paper, we make the following contributions:

  • We formulate test-time symmetrization, in which decoding and rewriting are two separate sources of test-time randomness, and prove that decoding alone cannot replace rewriting (Theorem 1).

  • We prove a tight scaling law: O(log⁡∣G∣)O(\log|G|) random rewritings approximate the full group average, uniformly over models, decoding rules, and realized decoders (Theorems 2 and 3).

  • We validate the theory with experiments on Qwen2.5-7B, Phi-4-mini, Llama-3.1-8B, and Qwen2.5-14B, with chain-of-thought reasoning, on graph reasoning, logical deduction, and multiple-choice question answering. At the same number of forward passes, rewriting the input is substantially more accurate than repeated sampling from the original prompt whenever the model’s answer depends on how the input is written, exactly as the theory predicts (§ 5).

Related Work

Test-time compute. Spending additional forward passes at inference is a standard way to improve a frozen language model: lengthening a single reasoning trace [86, 56], sampling several traces and voting [85], reranking them with a verifier [18, 43], or searching over intermediate steps [89, 70]. Empirical scaling laws for these procedures relate coverage or accuracy to the number of samples [12, 88, 14, 42], and several works explain their functional form [65, 41, 46] or their limitations under imperfect verification [72]; see Welleck et al. [87] for a survey and [32, 29] for the training-time counterparts. These procedures query the model using a fixed representation of the prompt, leaving the role of rewritings comparatively less studied. Our results show that this is a limitation in principle and that rewriting obeys its own scaling law, distinct from that of the decoding stage.

Sensitivity to rewritings. It is well documented that language models are not invariant to semantically neutral rewritings: the order of in-context examples [47, 91], prompt formatting [67, 54], the order of multiple-choice options [92, 61, 93, 27], the order of premises [16], the names and numbers in a math problem [53], the position of information in a long context [45], the serialization of a graph [82, 23, 28], and identifier renaming in code [52, 83] can all change the model’s prediction; consistency across paraphrases has also been studied on its own [21]. Existing remedies use small collections of rewritings to estimate and remove option-position bias [92], aggregate predictions from several prompts [30, 66, 4], modify input representations to make outputs order-independent [50], or train for robustness to permutations [13]. Closest to our setting, Kozodoi et al. [35] show empirically that allocating forward passes to input paraphrases can outperform self-consistency at matched compute, motivating the allocation problem between input-side and output-side diversity. Our framework separates this decoding choice from the cost of enforcing symmetry. Related work on model-agnostic symmetrization and on the theory of invariance is discussed in Section A.

Test-Time Symmetrization

Rewriting orbits and decoding fibers. Let X\mathcal{X} denote the space of prompts and let C\mathcal{C} denote the set of answer classes, with C=∣C∣C = |\mathcal{C}|. The target function y⋆:X→Cy^{\star} : \mathcal{X} \to\mathcal{C} assigns each prompt its correct answer. Let a finite group GG act on X\mathcal{X}.1 For a fixed semantic instance x∈Xx \in\mathcal{X}, its orbit G⋅x={g⋅x:g∈G}G \cdot x = \{g \cdot x : g \in G\} contains all rewritings generated by the group action. A frozen model queried on g⋅xg \cdot x defines a conditional distribution pθ,τ(⋅∣g⋅x)p_{\theta,\tau}(\cdot\mid g \cdot x) over reasoning traces. We write

ω∼pθ,τ(⋅∣g⋅x),Vx(g,ω)∈Z,\omega\sim p_{\theta,\tau}(\cdot\mid g \cdot x), \qquad V_x(g,\omega) \in\mathcal{Z},

where τ\tau is the token generation temperature, ω\omega is a sampled trace, and Vx(g,ω)V_x(g,\omega) is its response representation in a measurable space Z\mathcal{Z}. It may contain an answer, logits, a verifier score, or the entire trace. Without loss of generality, we assume that the task is invariant, y⋆(g⋅x)=y⋆(x)y^\star(g \cdot x) = y^\star(x). If GG acts equivariantly on the answer coordinates, we first align them using the inverse output action; the same results then apply. Task invariance does not require Vx(g,ω)V_x(g,\omega) to be invariant. Its variation across gg is precisely what test time symmetrization aims to remove.

We use rewriting and serialization for the same representations, with a small distinction in emphasis: gg denotes the rewriting operation, while g⋅xg \cdot x is the resulting serialization of the prompt. The response field has two distinct coordinates. The group element gg selects a representation of the prompt, while ω\omega selects a decoder outcome from pθ,τ(⋅∣g⋅x)p_{\theta,\tau}(\cdot\mid g \cdot x). We call the conditional probability space

(Ω,pθ,τ(⋅∣g⋅x))(\Omega, p_{\theta,\tau}(\cdot\mid g \cdot x))
Decoding each rewriting produces the orbit field

Figure 2. Decoding each rewriting produces the orbit field FxDF_x^D. Full group averaging gives the invariant target qxDq_x^D, while sparse averaging uses only the rewritings in SS to approximate it.

the decoding fiber at g⋅xg \cdot x. Thus, an orbit contains the equivalent representations of one semantic instance, and each representation has its own conditional distribution over decoder outcomes. We refer to VxV_x as the response field over these two coordinates. Formal definitions of the group action, the conditional decoder model, and the response field are collected in Section B.

Decoding before symmetrization. A decoding rule D\mathcal{D} maps the conditional response distribution at one rewriting to an element of a real Hilbert space H\mathcal{H}. We first describe this rule at the distribution level to isolate the cost of rewriting from the number of traces used to estimate it. The rule induces the decoded orbit field

FxD(g):=D(pθ,τ(⋅∣g⋅x),Vx(g,⋅))∈H.(1)F_x^D(g) := \mathcal{D}\bigl(p_{\theta,\tau}(\cdot\mid g \cdot x), V_x(g,\cdot)\bigr) \in\mathcal{H}. \tag*{(1)}

For class prediction, one usually takes H=RC\mathcal{H} = \mathbb{R}^C. Three examples are

FxSC(g)c:=Pω∣g(ax(g,ω)=c),(2)F_x^{\mathrm{SC}}(g)_c := \mathbb{P}_{\omega\mid g}\bigl(a_x(g,\omega)=c\bigr), \tag*{(2)}
Fxlogit(g):=Eω∣g[Vx(g,ω)],(3)F_x^{\mathrm{logit}}(g) := \mathbb{E}_{\omega\mid g}\bigl[V_x(g,\omega)\bigr], \tag*{(3)}
FxβD(g)c:=Eω∣g[eβDrx(g,ω)1{ax(g,ω)=c}]Eω∣g[eβDrx(g,ω)].(4)F_x^{\beta_D}(g)_c := \frac{\mathbb{E}_{\omega\mid g}\bigl[e^{\beta_D r_x(g,\omega)}\mathbf{1}\{a_x(g,\omega)=c\}\bigr]}{\mathbb{E}_{\omega\mid g}\bigl[e^{\beta_D r_x(g,\omega)}\bigr]}. \tag*{(4)}

Here ax(g,ω)a_x(g,\omega) is the answer extracted from a trace and rx(g,ω)r_x(g,\omega) is a verifier score. The first rule gives self consistency probabilities, the second averages logits, and the third is a verifier weighted vote. In Equation (4), βD=0\beta_D=0 recovers self consistency and larger βD\beta_D gives more weight to highly verified traces. This decoder inverse temperature is distinct from the generation temperature τ\tau inside pθ,τp_{\theta,\tau}. Our results hold simultaneously for all of these choices and for any other decoding rule whose output lies in a Hilbert space.

The fully symmetrized response is

qxD:=PGFxD=1∣G∣∑g∈GFxD(g).(5)q_x^D := P_G F_x^D = \frac{1}{|G|}\sum_{g\in G} F_x^D(g). \tag*{(5)}

It is invariant to the starting rewriting, but it need not be constant across answer classes. For H=RC\mathcal{H}=\mathbb{R}^C, it remains a class score vector and can select a unique answer. Invariance is therefore imposed only in the rewriting coordinate, not in the answer coordinate. This is the core idea of model agnostic symmetrization: a frozen model is left unchanged, and task structure is imposed through external averaging.

Let e∈Ge\in G denote the identity rewriting, so that e⋅x=xe\cdot x=x. Self consistency on the original prompt estimates FxSC(e)F_x^{\mathrm{SC}}(e), whereas full test time symmetrization returns PGFxSCP_G F_x^{\mathrm{SC}}. Repeated decoding at e⋅xe\cdot x provides information only about the original representation. Querying g⋅xg\cdot x reveals the decoded response at another point on the orbit. Describing the decoding rule at the distribution level removes trace estimation error from the rewriting scaling law, but it does not erase this information difference.

A reusable symmetrization operator. A full average over the orbit requires ∣G∣|G| forward passes. To reduce this cost, let S={{s1,…,s∣S∣}}S=\{\{s_1,\ldots,s_{|S|}\}\} be a multiset of group elements and define the sparse rewriting operator

(ASf)(h):=1∣S∣∑i=1∣S∣f(sih),h∈G.(6)(A_S f)(h):=\frac{1}{|S|}\sum_{i=1}^{|S|}f(s_i h),\qquad h\in G. \tag*{(6)}

The argument hh indexes the starting rewriting h⋅xh \cdot x from which the same inference procedure is invoked. The full group averaging operator is

(PGf)(h):=1∣G∣∑g∈Gf(gh),(7)(P_G f)(h) := \frac{1}{|G|} \sum_{g \in G} f(gh), \tag*{(7)}

which is constant over hh and is the orthogonal projection onto the subspace of functions that are constant on GG, as proved in Lemma 10. It is important to distinguish the group coordinate from the answer coordinate. The invariant subspace consists of score fields that are constant as the starting representation hh changes. It does not require the scores of the CC answer classes to be equal. Indeed, if f(h)=(f1(h),…,fC(h))f(h) = (f_1(h), \ldots, f_C(h)), then

(PGf)c(h)=1∣G∣∑g∈Gfc(gh),c∈C,(8)(P_G f)_c(h) = \frac{1}{|G|} \sum_{g \in G} f_c(gh), \qquad c \in\mathcal{C}, \tag*{(8)}

is independent of hh but can still vary with cc. Consequently, the invariant score vector PGfP_G f can select a unique answer through arg⁡max⁡c(PGf)c\arg\max_{c}(P_G f)_c. The projection therefore removes sensitivity to how the prompt is represented without removing the information needed to distinguish answer classes. If the original score field is already invariant, then PGf=fP_G f = f.

Our goal is to derive a scaling law for the number ∣S∣|S| of forward passes spent exploring GG. The sampled multiset SS is chosen once and remains valid uniformly over frozen models, decoding rules, generation and verifier temperatures, decoder realizations, and output spaces, with error measured in mean square over starting representations. This separates the forward pass cost of rewriting from the statistical cost of estimating a chosen decoder and makes SS a reusable model agnostic symmetrization rule.

Why decoder resampling alone is insufficient

We show that drawing more reasoning traces from the original prompt cannot, in general, recover the decision obtained by averaging over rewritings. Two possible model behaviors can be identical on the original prompt but have different average behavior over its orbit. No decoding rule that observes only the original prompt can distinguish between them.

Theorem 1 (Decoder resampling cannot replace rewriting). Let GG contain at least two elements and let C≥2C \ge2. Consider any possibly randomized inference algorithm that is allowed to draw an arbitrary number of independent traces

ωt∼pθ,τ(⋅∣x)\omega_t \sim p_{\theta,\tau}(\cdot\mid x)

from the original prompt. The algorithm may use internal randomness together with all previous traces and scores to decide whether to draw another trace or to stop and output a class, but it never queries g⋅xg \cdot x for g≠eg \ne e. There exist two bounded response fields Vx(0)V_x^{(0)} and Vx(1)V_x^{(1)}, sharing the same decoder distribution at xx, such that

Vx(0)(e,ω)=Vx(1)(e,ω)for every ω∈Ω.V_x^{(0)}(e,\omega) = V_x^{(1)}(e,\omega) \qquad\text{for every } \omega\in\Omega.

Thus, the complete observation sequence of the algorithm has the same distribution in the two worlds, regardless of how many traces it draws. Nevertheless, the two worlds have different unique invariant decisions:

arg⁡max⁡c∈C(PGFx(0))c≠arg⁡max⁡c∈C(PGFx(1))c,\underset{c \in\mathcal{C}}{\arg\max}(P_G F_x^{(0)})_c \ne\underset{c \in\mathcal{C}}{\arg\max}(P_G F_x^{(1)})_c,

where Fx(j)(g):=Eω∼q[Vx(j)(g,ω)]F_x^{(j)}(g) := \mathbb{E}_{\omega\sim q}[V_x^{(j)}(g,\omega)]. Consequently, if the two worlds are equally likely, every such algorithm has error at least 1/21/2, regardless of its decoder budget.

The reason is simple. The algorithm receives exactly the same information in both worlds and must therefore behave in the same way, but the correct invariant decisions are different. It must fail in at least one world. Thus, additional decoding can reduce randomness at the original prompt, but it cannot reveal how the model behaves at unseen rewritings. The construction and proof are given in Section D.

Scaling Laws for Model-Agnostic Symmetrization

We now quantify how many rewritings are needed to approximate the full group average. The result is stated briefly here; its stronger operator and representation theoretic form appears in Theorem 17.

Theorem 2 (Sparse rewriting scaling law, informal). Draw the rewritings in SS independently and uniformly from GG. With probability at least 1−δ1-\delta, the same set SS satisfies, for every real Hilbert space H\mathcal{H} and every F∈L2(G;H)F \in L^2(G;\mathcal{H}),

∥ASF−PGF∥L2(G;H)≤83log⁡(∣G∣/δ)∣S∣∥F−PGF∥L2(G;H).(9)\lVert A_S F-P_G F\rVert_{L^2(G;\mathcal{H})}\leq\frac{8}{3}\sqrt{\frac{\log(|G|/\delta)}{|S|}}\lVert F-P_G F\rVert_{L^2(G;\mathcal{H})}. \tag*{(9)}

This guarantee is simultaneous over all such fields, not one field fixed in advance. Moreover, the log⁡∣G∣\log|G| dependence is optimal in general: for some finite groups, fewer than log⁡2∣G∣\log_2 |G| rewritings cannot achieve any uniform error below one.

Thus, ∣S∣=O(ε−2(log⁡∣G∣+log⁡(1/δ)))|S|=O\bigl(\varepsilon^{-2}(\log|G|+\log(1/\delta))\bigr) rewritings give relative L2L^2 error at most ε\varepsilon. The event depends only on SS, which is why a single sampled set works for every model, decoder, trace realization, and answer space. In particular, there is no dependence on the number of answer classes. The complete theorem also shows that the same sample approximates averaging in every unitary representation. Its proof and the matching lower bound are given in Section E. The argument uses random Cayley expansion and adapts the operator and averaging complexity ideas of Alon & Roichman [3]; Tahmasebi et al. (2026); Tahmasebi & Weber [76].

A decoder agnostic scaling law

We now apply the same event after decoding. This order keeps the decoding rule arbitrary while leaving the rewriting rate unchanged.

Corollary 3 (Decoder agnostic symmetrization). On the event in Theorem 2, simultaneously for every prompt, frozen model, generation temperature, decoding rule, and Hilbert valued output,

∥ASFxD−qxD∥L2(G;H)≤83log⁡(∣G∣/δ)∣S∣∥FxD−qxD∥L2(G;H).(10)\lVert A_S F_x^D-q_x^D\rVert_{L^2(G;\mathcal{H})}\leq\frac{8}{3}\sqrt{\frac{\log(|G|/\delta)}{|S|}}\lVert F_x^D-q_x^D\rVert_{L^2(G;\mathcal{H})}. \tag*{(10)}

The same statement holds for every realized randomized decoder.

There is no dependence on CC, on the size of the trace space, or on a decoder covering number. A single draw of SS therefore works for self consistency, expected logits, every verifier temperature in Equation (4), and any other decoding rule selected after SS is drawn. The guarantee is also pathwise: a finite randomized decoder produces a function on GG, and the same event controls every seed and trace realization without a union bound over the trace space. It compares sparse and full group averaging of the same realized decoder field. Note that estimating a distribution level decoder from finitely many traces is a separate statistical question and does not alter the rewriting scaling law. The complete statement and proof are given in Section F; Section C explains why directly sampling joint pairs (g,ω)(g,\omega) gives a different guarantee.

This universal control is what separates the two sources of diversity. The rewriting set is chosen without reference to the reasoning traces or to how they will be decoded. One may therefore use any trace sampling and decoding procedure at each rewriting, while the same event controls the resulting field. The rewriting budget ∣S∣|S| and the trace budget can then be calibrated independently: our scaling law controls the former, while a decoder specific analysis controls the latter. No uniform estimation of every individual trace is required. An explicit decomposition of these two errors is given in Section C.

This distinction also explains why we average over rewritings. If the goal were instead to find the single best rewriting, an isolated maximizer could require Θ(∣G∣)\Theta(|G|) random queries to discover. The logarithmic law concerns approximate invariance under group averaging, not worst case search over the orbit.

From symmetrization to prediction error

The scaling law controls scores. We next translate it into prediction error. Let XX be drawn from the task distribution and take H=RC\mathcal{H} = \mathbb{R}^{C}. Fix any decoding rule and abbreviate FX=FXDF_X = F_X^D and qX=PGFXq_X = P_G F_X. Let

cG(X):=arg⁡max⁡c∈C (qX)c,c^S(h⋅X):=arg⁡max⁡c∈C (ASFX)(h)c,c_G(X) := \underset{c\in C}{\arg\max}\,(q_X)_c,\qquad\widehat{c}_S(h\cdot X) := \underset{c\in C}{\arg\max}\,(A_S F_X)(h)_c,

using a fixed tie breaking rule. Write ΔX\Delta_X for the gap between the largest and second largest coordinates of qXq_X, with ΔX=0\Delta_X = 0 at a tie, and define

RG:=PX(cG(X)≠y∗(X)),RS:=PX,h(c^S(h⋅X)≠y∗(X)),R_G := \mathbb{P}_X\bigl(c_G(X) \ne y^*(X)\bigr),\qquad R_S := \mathbb{P}_{X,h}\bigl(\widehat{c}_S(h\cdot X) \ne y^*(X)\bigr),

where h∼Unif⁡(G)h \sim\operatorname{Unif}(G) independently of XX.

Corollary 4 (Prediction error decomposition). On the event in Theorem 2, for every t>0t > 0,

RS≤RG+PX(ΔX≤t)+128log⁡(∣G∣/δ)9t2∣S∣EX[∥FX−PGFX∥L2(G;RC)2].(11)R_S \le R_G + \mathbb{P}_X(\Delta_X \le t) + \frac{128\log(|G|/\delta)}{9t^2|S|}\mathbb{E}_X\left[\left\|F_X-P_G F_X\right\|_{L_2(G;\mathbb{R}^C)}^2\right]. \tag*{(11)}

The three terms play different roles. The first, RGR_G, is the error of the fully symmetrized model, which uses all ∣G∣|G| rewritings; it is a property of the model and the task, and no number of rewritings can reduce it. The second counts examples whose symmetrized scores have a small margin ΔX\Delta_X, where a small approximation error can change the decision. The third is the finite rewriting error, which decays as log⁡∣G∣/∣S∣\log|G|/|S| with no explicit dependence on the number of classes CC; the threshold tt trades it against the second term. The bound thus separates three requirements. A large ∣S∣|S| controls only the third term, and the decision can remain unstable when the margin is small. A large margin controls the second term, and even then a task can be hard for the model regardless of how it is written, in which case RGR_G stays large. In particular, the result does not assume that full symmetrization is optimal: it separates this modeling error from the compute used to approximate it. The proof is given in Section G.

Experiments

We test three predictions of the theory on frozen open-weight models that generate reasoning traces. Details and all results are in Section H. The first prediction is that decoding at one representation cannot replace rewriting (Theorem 1). With the same number of forward passes, resampling one prompt should saturate below the orbit average, which rewriting reaches. The second is that the number of rewritings needed grows at most logarithmically in ∣G∣|G| (Theorems 2 and 3). The relative error of the sparse average should decay as ∣S∣−1/2|S|^{-1/2} for every decoding rule and model, with a constant that grows at most like log⁡∣G∣\sqrt{\log|G|}. The third comes from Theorem 4. Rewriting improves accuracy exactly on the instances where the model’s answer depends on the representation and the orbit-averaged decision is more accurate than a typical one, and it cannot help elsewhere.

Setup. Unless stated otherwise the model is Qwen2.5-7B-Instruct (Qwen Team et al., [63]), frozen, prompted to reason step by step and end with an answer line, which we parse. Each forward pass is one sampled trace at temperature 0.7. We compare procedures at a matched budget of BB passes. Self consistency spends all BB passes on the original prompt and takes a majority vote. Symmetrization spends them on mm random rewritings with B/mB/m traces each and votes over all traces, so m=1m = 1 is self consistency and m=Bm = B is one trace per rewriting. Greedy is one deterministic pass. Rewritings are drawn once per instance and reused for every model (Theorem 3). Our main family of tasks is graph reasoning on Erdős–Rényi graphs with nn nodes serialized as edge lists (Herbst et al., [28]; Fatemi et al., [23]). The group G=Sn×S∣E∣G = S_n \times S_{|E|} acts by node relabeling and edge reordering, and we use seven invariant tasks (edge count, edge existence, node degree, connected components, connectivity, cycle existence, triangle count), with 100 instances per task and size (200 in the cells of Table 1) and n∈{8,12,16,20,24}n \in\{8, 12, 16, 20, 24\}. We also use a non-graph task with two different groups, a multiple-choice benchmark with an equivariant answer, few-shot classification, and three further model families (Phi-4-mini, Llama-3.1-8B, Qwen2.5-14B-AWQ). Gains are paired differences in accuracy with 95% bootstrap intervals over instances.

Rewriting versus decoding at matched compute. Figure 3 shows the two budgets on the same instances. On edge counting with n=24n = 24, one greedy pass is right 39% of the time. With 64 traces at the original prompt the accuracy reaches 89% and the curve flattens. With 64 rewritings it reaches 99.5%, and 16 rewritings already give 100% against 83% for 16 traces, a gain of +16.5 points ([+11.3, +22.2]). The plateau is the content of Theorem 1. More traces at one representation reveal nothing about the rest of the orbit. Table 1 reports the matched budget B=16B = 16 for four model families. Every family has significant gains, but on different tasks. Qwen2.5-7B gains on edge counting and edge existence, Phi-4-mini on all three tasks, Llama on edge counting, and the 14B model on node degree. The rewriting set is the same for all of them, as Theorem 3 allows, and which decision it improves is a property of the model (Theorem 4). Tokens per trace are the same at a rewriting as at the original prompt (ratio 0.999, Section H.1), so budgets in passes and in tokens coincide. The full table, with all seven tasks, all sizes, and the allocation grid over (m,B/m)(m, B/m), is in Section H.2. Across the 98 (model, task, size) cells on these graphs, 24 gains and 3 losses are significant.

Figure 3. Accuracy against the number of forward passes (Theorem 1). Accuracy against the number of forward passes kk when all kk traces are sampled at the original prompt and voted (blue), or one trace is sampled at each of kk random rewritings (orange), for six (task, size, model) cells. The dashed line is the vote over all traces at all rewritings. The last panel is the one task on which both aggregations hurt, discussed in the text.

ModelTaskGreedySCSym.Sym. − SCflip
Qwen2.5-7B, n=24n=24edge count0.420.810.92+10.8 [+3.8, +18.4]0.94
edge existence0.880.961.00+3.9 [+0.9, +8.0]0.75
node degree0.440.400.38−2.2 [−8.0, +3.4]0.90
Llama-3.1-8Bedge count0.280.600.70+10.0 [+2.3, +18.3]1.00
edge existence0.720.810.86+5.5 [−0.7, +12.3]0.57
node degree0.680.880.90+1.9 [−4.3, +8.4]0.87
Phi-4-miniedge count0.710.890.99+9.7 [+5.5, +14.0]0.79
edge existence0.890.971.00+2.4 [+0.6, +4.5]0.67
node degree0.680.750.82+6.9 [+2.2, +11.9]0.88
Qwen2.5-14B-AWQedge count0.630.710.69−1.9 [−7.5, +3.8]0.52
edge existence0.980.991.00+0.7 [+0.0, +2.0]0.17
node degree0.830.850.94+9.0 [+2.1, +17.1]0.73

Table 1. Accuracy at B=16B = 16 forward passes on graphs with n=16n = 16 nodes (n=24n = 24 for Qwen2.5-7B). One greedy pass, self consistency with 16 traces (SC), and 16 rewritings with one trace each (Sym.), with the paired gain of Sym. over SC in accuracy points and its 95% interval. The column “flip” is the fraction of instances whose greedy answer changes across the 16 rewritings. Bold means that the interval excludes zero.

Beyond graphs and beyond SnS_n. Figure 4 repeats the comparison on a deduction task. Its rewritings form Sk−1S_{k-1}, the hypercube Z2k−1\mathbb{Z}_2^{k-1} on which the log⁡∣G∣\log|G| factor of Theorem 2 is attained, or their product. With k=11k = 11 people and the product group, one greedy pass finds the tallest person 51% of the time, 16 traces 79%, and 16 rewritings 99% (+19.5 points, [+11.9, +27.3]). Across the nine (question, group) combinations and three values of kk, 13 of the 27 cells are significant gains and none is a significant loss. For an equivariant answer we permute the four options of ARC-Challenge (Clark et al., [17]) (G=S4G = S_4, 500 questions) and align the predicted letters by the inverse permutation before voting, as described in § 3. The original ordering gives 91.8% and the aligned vote over 16 permutations gives 94.6% (+2.6 over a matched vote at the original ordering, [+0.8, +4.6]). The same vote without alignment gives 24.4%, which is chance level. Reordering few-shot demonstrations on SST-2 (Liu et al., 2022) finally, changes Qwen2.5-7B’s answer only on 6–8% of queries, and symmetrization changes accuracy by less than half a point in either direction, as the third prediction requires (Section H.5).

Figure 4. A non-graph task under three groups. “Who is the tallest of kk people?” given the k−1k-1 adjacent comparisons, rewritten by permuting the premises (Sk−1S_{k-1}), by flipping statements between “taller than” and “shorter than” (Z2k−1\mathbb{Z}_{2}^{k-1}), or both. Qwen2.5-7B, 100 instances per kk, budget 16. The three “position” and “comparison” variants are in Section H.5.

The number of rewritings needed as the group grows. To measure the law itself we read next-token answer distributions, which give the decoded field F2D(g)F^D_2(g) exactly for every decoding rule. Figure 5 shows the relative error of ASFA_SF for nn from 8 to 32, where log⁡∣G∣\log|G| grows from about 25 to more than 300 nats counting both factors of GG. The rescaled error ∣S∣∥ASF−PGF∥/∥F−PGF∥\sqrt{|S|}\lVert A_SF-P_GF\rVert/\lVert F-P_GF\rVert stays between 0.9 and 1.1 for every size, every task, and every decoding rule. The curves for Qwen2.5-1.5B on the same SS are indistinguishable from those of the 7B model (Section H.8). The logarithm in Theorem 2 is a worst case over groups that node relabeling does not pay. On the accuracy side the same holds. On edge counting the fraction of instances whose answer changes under rewriting grows from 12% at n=8n = 8 to 94% at n=24n = 24, and the gain of 16 rewritings over 16 traces grows with it from +1.0 to +10.8 points, with the budget fixed at 16 (Section H.3).

Figure 5. Relative error of the sparse average on language-model fields (Theorems 2 and 3). Relative error ∥ASF−PGF∥/∥F−PGF∥\lVert A_SF - P_GF\rVert/\lVert F - P_GF\rVert of the sparse average against ∣S∣|S| for Qwen2.5-7B on graphs with n∈{8,12,16,32}n \in\{8, 12, 16, 32\} nodes, one shared SS, four decoding rules applied to the same next-token fields, median over seven tasks. PGFP_GF is estimated from 64 independent rewritings and the estimation noise is subtracted (Section H.8). The dashed line is ∣S∣−1/2|S|^{-1/2}.

When rewriting helps. Theorem 4 says that rewriting can only recover competence the model shows on part of the orbit. Among the 98 graph cells of the four models, 60 are cells in which the greedy answer changes on more than half of the instances and the model is above 40% accuracy. They contain 20 significant gains and 1 loss, with a mean gain of +2.1 points. The other 38 cells contain 4 gains and 2 losses, with a mean of 0.0 (Section H.2). Triangle counting is beyond every model at every representation. Counting components and connectivity are sensitive, but their orbit-averaged decision is no better than a typical one, so neither 16 traces nor 16 rewritings move them. The one systematic loss is cycle detection at n=8n = 8, where every model has a representation-invariant bias toward “yes” on acyclic graphs. A single greedy pass says “yes” on 48% of them and the orbit on 62%. Averaging cannot remove an invariant bias, and when the wrong answer has probability above one half any vote, over traces or over rewritings, amplifies it. Both aggregations fall below greedy there (Figure 3, last panel). Conversely, no single serialization is a substitute for the orbit. On edge counting with n=24n = 24, only 6% of the graphs are solved at all 16 of their rewritings and a random rewriting solves 38%, while the vote over the 16 solves 92%, nearly the 93% an oracle choice of serialization would reach (Section H.4). The same regime appears in a 0.8M-parameter transformer trained from scratch on edge counting with a canonical serialization. It is perfect on its training format, 85% accurate on a random rewriting, and 99.5% after symmetrization over 16 rewritings, while the same model trained with random rewritings is invariant and gains nothing (Section H.7). Finally, when the group is not available, rewritings can be sampled from a paraphrasing model instead. A cross-family paraphraser preserves the graph in 88% of its rewordings at n=12n = 12 and 67% at n=24n = 24. Over the surviving rewordings, symmetrization gains +9.8 points ([+3.8, +15.9]) on edge counting at n=12n = 12, but its orbit average stays below that of the exact group at n=24n = 24 (87% against 100%), and a same-model paraphraser, whose rewordings are near duplicates, gains nothing (Section H.6). Exact rewritings are cheaper and better when they exist, and paraphrases are a usable substitute whose error is the drift of the paraphraser.

Conclusion

We studied test-time symmetrization, which spends forward passes on rewritings of the input rather than on repeated decoding. Decoding alone cannot replace rewriting, whatever its budget, while one random set of O(log⁡∣G∣)O(\log\lvert G\rvert) rewritings approximates the full group average simultaneously for every frozen model, decoding rule, realized decoder, and Hilbert valued output, with no dependence on the number of answer classes or the size of the reasoning space. An error decomposition separates the accuracy of the fully symmetrized model, its margin, and the finite rewriting cost. Experiments with four model families confirm the scaling law on next-token distributions and its consequences on reasoning traces. At the same number of forward passes, rewriting improves on resampling whenever the model’s answer depends on how the input is written and the symmetrized decision is more accurate, across graph reasoning, logical deduction, and multiple choice with an equivariant answer, and it cannot help elsewhere.

Our guarantees control invariance in mean square over starting representations rather than at every representation, and they concern the approximation of the fully symmetrized model rather than its accuracy, which depends on the model and the task. They also require the symmetry to be known and exact. When it is not, rewritings can be drawn from a kernel such as a paraphrasing model. The sparse average then estimates the kernel average at the same ∣S∣−1/2\lvert S\rvert^{-1/2} rate, but the target is only meaningful up to the drift of the kernel, which adds to the error of Theorem 4, and nothing is uniform over an orbit. Our paraphrase experiment (Section H.6) shows that this substitute recovers part of the gain and that its quality is limited by the drift and the diversity of the paraphraser. Natural next steps are a theory for such approximate symmetries, symmetrization inside reasoning traces rather than only at the answer, and further exact symmetries such as identifier renaming.

AI Use Statement

Large language model tools (ChatGPT 5.6 Sol and Claude Fable 5.1) were used primarily for copyediting, including improvements to grammar, wording, clarity, and LaTeX presentation. The research direction, core ideas, theoretical results, and experimental design are original contributions of the authors. The authors carefully reviewed and verified all technical content and take full responsibility for the final manuscript.

Acknowledgments

BT and MW were supported by NSF award DMS-2406905, Coefficient Giving, and the Harvard Dean’s Fund for Promising Scholarship. MW acknowledges partial support from an Alfred P. Sloan Research Fellowship in Mathematics and the AI2050 program at Schmidt Sciences (Grant G-25-69786).

Additional Related Work

Test-time augmentation. Averaging predictions over transformed inputs at inference is an old idea in vision, going back to multi-crop evaluation [36, 69]. Later work studies how to aggregate the augmented predictions [68], when averaging helps [34], and how it compares with ensembles [5, 10, 38]. Our setting differs in that the transformations form a group, so the cost can be measured against ∣G∣|G|, and the predictor is itself random.

Model-agnostic symmetrization. Symmetry is usually built into the architecture [19, 11, 90, 49]. When this is not possible, it can be imposed from outside by averaging over the group: Janossy pooling [57], frame averaging [62], canonicalization [31, 55], probabilistic symmetrization [33], and equi-tuning of pretrained models [7] are examples, and Tahmasebi & Jegelka [75] compare the generalization of canonicalization with that of group averaging. Related work measures how equivariant a trained model is [26], learns invariances from data [8], or studies approximate symmetries [60]. These methods generally alter model construction, training, or internal representations. Our model is frozen and accessed only through forward passes, so the cost of symmetrization is counted in queries.

Theory of invariance. Invariance is known to help at training time: data augmentation reduces variance [15, 48], equivariant models can generalize strictly better [22], and the gain has been quantified for kernel models [9, 51, 73], for divergence estimation [74], and measured experimentally [2]; see also Tahmasebi et al. [78] for a Fourier view of augmentation. Most relevant to us, Tahmasebi & Weber [76] show in their averaging-complexity framework that exact invariance can require all ∣G∣|G| group elements while approximate invariance needs only Θ(log⁡∣G∣)\Theta(\log|G|) random ones. Our Theorem 2 is of the same kind and relies on random Cayley graphs being expanders [3, 39] and on matrix concentration [79, 80]. We extend this from deterministic functions to stochastic frozen models, make the guarantee uniform, combine it with decoding, and connect it to decisions through the margin. More precisely, Tahmasebi & Weber [76] bound the averaging complexity of a fixed, deterministic function class. A single sparse set of group elements drawn once has also been used at training time, to approximate the group-averaged gradient uniformly over all parameters [77]. What is new here is the separation of the two sources of randomness (decoding fibers and rewriting orbits) and the impossibility result that follows from it (Theorem 1), the uniformity of a single draw over every decoding rule and every realized trace without a covering-number penalty (Theorem 3, through Lemmas 13 and 15), the margin decomposition that turns the approximation into a prediction error (Theorem 4), and the question of allocating a test-time budget between the two sources. Synthetic graphs with random node identifiers, as in our experiments, are the standard setting for isolating what language models learn about structure [6, 64, 24, 58, 59, 84].

Mathematical Preliminaries

This appendix collects the definitions, notation, and elementary facts used throughout the paper. All expectations of vector valued functions are understood coordinatewise.

Finite groups, actions, and orbits

Definition 5 (Finite group). A finite group GG is a finite set equipped with an associative product (g,h)↦gh(g,h) \mapsto gh, an identity element e∈Ge \in G, and an inverse g−1∈Gg^{-1} \in G for every g∈Gg \in G. Thus, eg=ge=geg = ge = g and g−1g=gg−1=eg^{-1}g = gg^{-1} = e.

Definition 6 (Group action and orbit). A left action of GG on a set X\mathcal{X} is a map (g,x)↦g⋅x(g,x) \mapsto g \cdot x satisfying

e⋅x=x,(gh)⋅x=g⋅(h⋅x)e \cdot x = x,\qquad(gh) \cdot x = g \cdot(h \cdot x)

for all g,h∈Gg,h \in G and x∈Xx \in\mathcal{X}. The orbit of xx is

G⋅x={g⋅x:g∈G}.G \cdot x = \{g \cdot x : g \in G\}.

Elements of the same orbit are the rewritings that the task regards as semantically equivalent.

Definition 7 (Invariant and equivariant targets). Let y⋆:X→Cy^\star: \mathcal{X} \to\mathcal{C} be the target function. It is invariant if

y⋆(g⋅x)=y⋆(x)y^\star(g \cdot x) = y^\star(x)

for every g∈Gg \in G and x∈Xx \in\mathcal{X}. More generally, suppose that each g∈Gg \in G induces a permutation ρ(g):C→C\rho(g) : \mathcal{C} \to\mathcal{C} of the answer classes, with ρ(gh)=ρ(g)ρ(h)\rho(gh) = \rho(g)\rho(h). The target is equivariant if

y⋆(g⋅x)=ρ(g)y⋆(x).y^\star(g \cdot x) = \rho(g)y^\star(x).

In the equivariant case, applying ρ(g)−1\rho(g)^{-1} to the output scores aligns them with the original answer coordinates and reduces the problem to the invariant setting.

Conditional decoding and response fields

Equip X\mathcal{X} with a sigma algebra BX\mathcal{B}_{\mathcal{X}}, and let (Ω,BΩ)(\Omega,\mathcal{B}_{\Omega}) be the measurable space of reasoning traces. A frozen model specifies, for every prompt x∈Xx \in\mathcal{X}, a probability measure

pθ,τ(⋅∣x)p_{\theta,\tau}(\cdot\mid x)

on Ω\Omega. Equivalently, pθ,τp_{\theta,\tau} is a conditional probability kernel from prompts to reasoning traces, where τ\tau may specify a generation temperature. Querying the model on g⋅xg \cdot x means drawing

ω∼pθ,τ(⋅∣g⋅x).\omega\sim p_{\theta,\tau}(\cdot\mid g \cdot x).

We assume throughout that the maps below are measurable and square integrable whenever an L2L^2 norm is used.

Definition 8 (Response field and decoding fiber). For a fixed semantic instance xx, a response field is a measurable function

Vx:G×Ω→Z.V_x : G \times\Omega\to\mathcal{Z}.

The value Vx(g,ω)V_x(g,\omega) is the response representation obtained from trace ω\omega at rewriting g⋅xg \cdot x. It may contain an answer, logits, a verifier score, or the trace itself. The pair

(Ω,pθ,τ(⋅∣g⋅x))\left(\Omega, p_{\theta,\tau}(\cdot\mid g \cdot x)\right)

is the decoding fiber at g⋅xg \cdot x.

The joint rewriting and decoding experiment is

g∼Unif⁡(G),ω∣g∼pθ,τ(⋅∣g⋅x).g \sim\operatorname{Unif}(G), \qquad\omega\mid g \sim p_{\theta,\tau}(\cdot\mid g \cdot x).

When VxV_x is vector valued and integrable, its joint expectation is

Eg,ω∣g[Vx(g,ω)]=1∣G∣∑g∈G∫ΩVx(g,ω)pθ,τ(dω∣g⋅x).\mathbb{E}_{g,\omega\mid g}[V_x(g,\omega)] = \frac{1}{|G|}\sum_{g\in G}\int_{\Omega} V_x(g,\omega)p_{\theta,\tau}(d\omega\mid g \cdot x).

Definition 9 (Distribution level decoding rule). Let H\mathcal{H} be a real Hilbert space. A distribution level decoding rule is any measurable map D\mathcal{D} from the conditional response distribution at a rewriting to an element of H\mathcal{H}. Its decoded orbit field is

FxD(g)=D(pθ,τ(⋅∣g⋅x),Vx(g,⋅)).F_x^{\mathcal{D}}(g) = \mathcal{D}\left(p_{\theta,\tau}(\cdot\mid g \cdot x), V_x(g,\cdot)\right).

No linearity or finite dimensionality is assumed. A randomized finite decoder with seed ξ\xi similarly induces a realized field F^x,ξ:G→H\widehat{F}_{x,\xi}: G \to\mathcal{H}.

Functions on the group and invariant projection

For a real Hilbert space H\mathcal{H}, equip L2(G;H)L^2(G;\mathcal{H}) with the uniform inner product

⟨f,q⟩L2(G):=1∣G∣∑h∈G⟨f(h),q(h)⟩H.\langle f,q\rangle_{L^2(G)} := \frac{1}{|G|}\sum_{h\in G}\langle f(h),q(h)\rangle_{\mathcal{H}}.

Lemma 10 (Full group averaging). For f∈L2(G;H)f \in L^2(G;\mathcal{H}), define

(PGf)(h):=1∣G∣∑g∈Gf(gh).(P_G f)(h) := \frac{1}{|G|}\sum_{g\in G} f(gh).

Then PGfP_G f is constant in hh, and PGP_G is the orthogonal projection onto the subspace of functions that are constant on GG.

Proof. For fixed h∈Gh \in G, the map g↦ghg \mapsto gh is a bijection of GG. Hence

(PGf)(h)=1∣G∣∑u∈Gf(u),(P_G f)(h) = \frac{1}{|G|}\sum_{u\in G}f(u),

which does not depend on hh. Thus, the image of PGP_G consists of constant functions, and PGq=qP_Gq=q for every constant function qq. Moreover, f−PGff-P_Gf has mean zero and is therefore orthogonal to every constant function. This proves the claim.

Translation operators and matrix concentration

For a scalar function f∈L2(G)f \in L^2(G) and s∈Gs \in G, define the translation operator

(Tsf)(h):=f(sh),h∈G.(12)(T_s f)(h) := f(sh), \qquad h \in G. \tag*{(12)}

Because h↦shh \mapsto sh is a permutation of GG, TsT_s is unitary under the uniform measure. In this notation,

AS=1∣S∣∑i=1∣S∣Tsi,PG=Es∼Unif⁡(G)[Ts].(13)A_S = \frac{1}{|S|}\sum_{i=1}^{|S|} T_{s_i}, \qquad P_G = \mathbb{E}_{s \sim\operatorname{Unif}(G)}[T_s]. \tag*{(13)}

The operator norm used in Theorem 17 is

∥T∥L2(G)→L2(G):=sup⁡f≠0∥Tf∥L2(G)∥f∥L2(G).(14)\|T\|_{L^2(G)\to L^2(G)} := \sup_{f \ne0} \frac{\|Tf\|_{L^2(G)}}{\|f\|_{L^2(G)}}. \tag*{(14)}

Thus, an operator norm bound is one event that controls the approximation error for every function f∈L2(G)f \in L^2(G) simultaneously.

We use the following standard matrix Bernstein inequality [79]. It is stated for operators so that it applies directly to translations on L2(G)L^2(G).

Lemma 11 (Matrix Bernstein inequality). Let X1,…,XmX_1,\ldots,X_m be independent, mean zero linear operators on a dd dimensional Hilbert space. Suppose that ∥Xi∥op≤R\|X_i\|_{\mathrm{op}} \le R almost surely, and define

σ2:=max⁡{∥∑i=1mE[XiXi∗]∥op,∥∑i=1mE[Xi∗Xi]∥op}.\sigma^2 := \max\left\{\left\|\sum_{i=1}^{m}\mathbb{E}[X_iX_i^*]\right\|_{\mathrm{op}},\left\|\sum_{i=1}^{m}\mathbb{E}[X_i^*X_i]\right\|_{\mathrm{op}}\right\}.

Then, for every t≥0t \ge0,

P(∥∑i=1mXi∥op≥t)≤2dexp⁡(−t22σ2+2Rt/3).\mathbb{P}\left(\left\|\sum_{i=1}^{m}X_i\right\|_{\mathrm{op}} \ge t\right) \le2d\exp\left(-\frac{t^2}{2\sigma^2+2Rt/3}\right).

The nonsymmetric form above follows from the self-adjoint matrix Bernstein inequality by applying it to the self-adjoint dilation of each XiX_i.

Hilbert valued averaging and unitary representations

We collect the representation theoretic facts behind the universality in Theorem 17. We state them over complex Hilbert spaces, where the standard Fourier decomposition is most transparent. A real representation is covered by passing to its complexification, which preserves operator norms.

Definition 12 (Unitary representation and invariant subspace). A unitary representation of GG on a Hilbert space H\mathcal{H} is a map π:G→U(H)\pi:G \to U(\mathcal{H}) satisfying

π(gh)=π(g)π(h),π(e)=IH.\pi(gh) = \pi(g)\pi(h), \qquad\pi(e) = I_{\mathcal{H}}.

Its invariant subspace is

HG={v∈H:π(g)v=v for every g∈G}.\mathcal{H}^G = \{v \in\mathcal{H}: \pi(g)v = v \text{ for every } g \in G\}.

A nonzero representation is irreducible if its only closed invariant subspaces are {0}\{0\} and the whole space.

The left regular representation λ\lambda acts on L2(G;C)L^2(G;\mathbb{C}) by

(λ(g)f)(h):=f(g−1h).(\lambda(g)f)(h) := f(g^{-1}h).

Our translation Tgf(h)=f(gh)T_gf(h) = f(gh) equals λ(g−1)\lambda(g^{-1}). This inverse changes neither the relevant operator norm nor the distribution of a uniform group sample.

Let G^\widehat{G} denote a complete set of inequivalent irreducible unitary representations, and let dρd_\rho be the dimension of ρ∈G^\rho\in\widehat{G}. The finite group Fourier decomposition gives

L2(G,C)≅⨁ρ∈G^Cdρ⊗Cdρ,λ(g)≅⨁ρ∈G^ρ(g)⊗Idρ.(15)L^2(G,\mathbb{C}) \cong\bigoplus_{\rho\in\widehat{G}} \mathbb{C}^{d_\rho}\otimes\mathbb{C}^{d_\rho}, \qquad\lambda(g) \cong\bigoplus_{\rho\in\widehat{G}} \rho(g)\otimes I_{d_\rho}. \tag*{(15)}

Thus, every irreducible representation occurs inside the regular representation, with multiplicity equal to its dimension. More generally, every unitary representation of a finite group is an orthogonal direct sum of irreducible representations. These are the finite group forms of Maschke’s theorem and the Peter Weyl decomposition.

The Hilbert valued space L2(G;H)L^2(G;\mathcal{H}) is naturally the Hilbert tensor product L2(G)⊗HL^2(G)\otimes\mathcal{H}. A scalar operator TT on L2(G)L^2(G) acts on it as T⊗IHT\otimes I_{\mathcal{H}}.

Lemma 13 (Hilbert valued tensorization). For every bounded operator T:L2(G)→L2(G)T:L^2(G)\to L^2(G) and every real Hilbert space H\mathcal{H}

∥T⊗IH∥L2(G;H)→L2(G;H)=∥T∥L2(G)→L2(G).\lVert T\otimes I_{\mathcal{H}}\rVert_{L^2(G;\mathcal{H})\to L^2(G;\mathcal{H})}=\lVert T\rVert_{L^2(G)\to L^2(G)}.

Consequently, if TPG=PGT=0TP_G=P_GT=0, then

∥TF∥L2(G;H)≤∥T∥op∥F−PGF∥L2(G;H).\lVert TF\rVert_{L^2(G;\mathcal{H})}\leq\lVert T\rVert_{\mathrm{op}}\lVert F-P_GF\rVert_{L^2(G;\mathcal{H})}.

Proof. Choose an orthonormal basis (uj)j(u_j)_j for the closed span of the finite set {F(g):g∈G}\{F(g):g\in G\}. Writing F=∑jfjujF=\sum_j f_ju_j and using Parseval’s identity gives

∥(T⊗IH)F∥2=∑j∥Tfj∥L2(G)2≤∥T∥op2∑j∥fj∥L2(G)2.\lVert(T\otimes I_{\mathcal{H}})F\rVert^2=\sum_j\lVert Tf_j\rVert_{L^2(G)}^2\leq\lVert T\rVert_{\mathrm{op}}^2\sum_j\lVert f_j\rVert_{L^2(G)}^2.

This proves the upper bound, and testing on F=fuF=fu for a unit vector u∈Hu\in\mathcal{H} proves equality. The final claim follows from TF=T(F−PGF)TF=T(F-P_GF).

Lemma 14 (Group averaging is an invariant projection). For a unitary representation π:G→U(H)\pi:G\to\mathcal{U}(\mathcal{H}), the operator

Pπ:=1∣G∣∑g∈Gπ(g)P_\pi:=\frac{1}{|G|}\sum_{g\in G}\pi(g)

is the orthogonal projection onto HG\mathcal{H}^G.

Proof. For any a∈Ga\in G, a change of variables gives

π(a)Pπ=1∣G∣∑g∈Gπ(ag)=Pπ.\pi(a)P_\pi=\frac{1}{|G|}\sum_{g\in G}\pi(ag)=P_\pi.

Hence the image of PπP_\pi lies in HG\mathcal{H}^G. Conversely, Pπv=vP_\pi v=v for every v∈HGv\in\mathcal{H}^G. Moreover,

Pπ∗=1∣G∣∑g∈Gπ(g−1)=Pπ,P_\pi^*=\frac{1}{|G|}\sum_{g\in G}\pi(g^{-1})=P_\pi,

and the same change of variables gives Pπ2=PπP_\pi^2=P_\pi. It is therefore the orthogonal projection onto HG\mathcal{H}^G.

Lemma 15 (The regular representation controls every representation). Let π:G→U(H)\pi:G\to\mathcal{U}(\mathcal{H}) be a unitary representation of a finite group, and let

Pπ:=1∣G∣∑g∈Gπ(g).P_\pi:=\frac{1}{|G|}\sum_{g\in G}\pi(g).

For every multiset S⊆GS\subseteq G,

∥1∣S∣∑s∈Sπ(s)−Pπ∥op≤∥AS−PG∥L2(G)→L2(G).\left\lVert\frac{1}{|S|}\sum_{s\in S}\pi(s)-P_\pi\right\rVert_{\mathrm{op}}\leq\lVert A_S-P_G\rVert_{L^2(G)\to L^2(G)}.

Moreover, PπP_\pi is the orthogonal projection onto the vectors fixed by every π(g)\pi(g).

Proof. Write m=∣S∣m = |S| and define

Bπ:=1m∑i=1mπ(si)−Pπ.B_\pi:= \frac{1}{m}\sum_{i=1}^{m}\pi(s_i)-P_\pi.

Decompose π\pi into irreducibles. On an isotypic component associated with ρ∈G^\rho\in\widehat{G}, the operator BπB_\pi acts as

(1m∑i=1mρ(si)−Pρ)⊗I,\left(\frac{1}{m}\sum_{i=1}^{m}\rho(s_i)-P_\rho\right)\otimes I,

so ∥Bπ∥op\|B_\pi\|_{\mathrm{op}} is the supremum of the norms of these irreducible blocks. By Equation (15), every such block occurs in the regular representation.

Our convention uses Ts=λ(s−1)T_s=\lambda(s^{-1}). The corresponding regular block contains

1m∑i=1mρ(si−1)−Pρ=(1m∑i=1mρ(si)−Pρ)∗.\frac{1}{m}\sum_{i=1}^{m}\rho(s_i^{-1})-P_\rho = \left(\frac{1}{m}\sum_{i=1}^{m}\rho(s_i)-P_\rho\right)^*.

Taking an adjoint does not change the operator norm. Therefore, each irreducible block of BπB_\pi has norm at most ∥AS−PG∥L2(G)→L2(G)\|A_S-P_G\|_{L^2(G)\to L^2(G)}, and taking the supremum over the blocks proves the inequality. The final statement follows from Lemma 14.

Margins and decision disagreement

For a score vector q∈RCq \in\mathbb{R}^{C} with a unique maximizer c∗c^*, define its margin

Δ(q):=qc∗−max⁡c≠c∗qc.\Delta(q) := q_{c^*}-\max_{c\ne c^*}q_c.

We use any fixed rule to break ties in approximate score vectors.

Lemma 16 (A changed decision requires score error). Let q,v∈RCq,v \in\mathbb{R}^{C}, suppose that qq has unique maximizer c∗c^*, and let Δ(q)>0\Delta(q)>0 be its margin. If arg max⁡cvc≠c∗\operatorname*{arg\,max}_{c}v_c\ne c^*, then

∥v−q∥22≥Δ(q)22.\|v-q\|_2^2\ge\frac{\Delta(q)^2}{2}.

Proof. Let c≠c∗c\ne c^* be the class selected by vv. Since vc≥vc∗v_c\ge v_{c^*},

Δ(q)≤qc∗−qc≤∣vc∗−qc∗∣+∣vc−qc∣≤2∥v−q∥2.\Delta(q)\le q_{c^*}-q_c\le|v_{c^*}-q_{c^*}|+|v_c-q_c|\le\sqrt{2}\|v-q\|_2.

Squaring both sides proves the claim.

On Joint Rewriting and Decoding Sampling

A natural alternative is to sample pairs

gi∼Unif⁡(G),ωi∼pθ,τ(⋅∣gi⋅x),g_i\sim\operatorname{Unif}(G),\qquad\omega_i\sim p_{\theta,\tau}(\cdot\mid g_i\cdot x),

and aggregate the resulting responses directly. This is a valid inference procedure, but it answers a different statistical question from the operator approximation studied in this paper. We explain the distinction here.

Joint sampling is exact for linear decoding rules. Suppose that a distribution level decoding rule has the linear form

FxD(g)=Eω∣g[ψx(g,ω)]F_x^D(g)=\mathbb{E}_{\omega\mid g}[\psi_x(g,\omega)]

for some Hilbert valued response ψx\psi_x. Then the fully symmetrized response satisfies

qxD=Eg∼Unif⁡(G)Eω∣g[ψx(g,ω)]=Eg,ω∣g[ψx(g,ω)].(16)q_x^D=\mathbb{E}_{g\sim\operatorname{Unif}(G)}\mathbb{E}_{\omega\mid g}[\psi_x(g,\omega)] =\mathbb{E}_{g,\omega\mid g}[\psi_x(g,\omega)]. \tag*{(16)}

Consequently, independent joint samples give an unbiased Monte Carlo estimator of qxDq_x^D. Self consistency with one hot vote vectors and expected logits are examples. For one fixed instance, one fixed decoder, and one fixed starting representation, standard concentration may therefore be the simplest analysis.

Nonlinear decoding changes the target quantity. The equality in Equation (16) does not hold for a general decoder. The quantity studied in this paper is

QxD=Eg[D(Px,g)],Px,g:=Law⁡(Vx(g,ω)∣g),(17)Q_x^D = \mathbb{E}_g\left[\mathcal{D}(P_{x,g})\right], \qquad P_{x,g} := \operatorname{Law}(V_x(g,\omega)\mid g), \tag*{(17)}

which first decodes each conditional trace distribution and then removes rewriting sensitivity. Pooling joint samples generally corresponds instead to applying a decoder after mixing the conditional distributions. These operations need not commute:

Eg[D(Px,g)]≠D(EgPx,g).\mathbb{E}_g\left[\mathcal{D}(P_{x,g})\right] \ne\mathcal{D}\left(\mathbb{E}_g P_{x,g}\right).

For example, the verifier weighted decoder in Equation (4) averages the per rewriting ratios

Eg[Eω∣g[eβDrx(g,ω)1{ax(g,ω)=c}]Eω∣g[eβDrx(g,ω)]].\mathbb{E}_g\left[\frac{\mathbb{E}_{\omega\mid g}\left[e^{\beta D_{r_x}(g,\omega)}\mathbf{1}\{a_x(g,\omega)=c\}\right]}{\mathbb{E}_{\omega\mid g}\left[e^{\beta D_{r_x}(g,\omega)}\right]}\right].

Pooling all pairs before normalization instead produces a ratio of joint expectations. The two weight rewritings differently and can select different answers.

Pointwise estimation is not universal operator approximation. Even in the linear case, joint Monte Carlo estimates one chosen quantity qxDq_x^D for one response field. Our goal is stronger: draw SS once so that the induced group operator approximates PGP_G for every response field simultaneously. This operator event remains valid after the model, decoder, generation temperature, verifier temperature, output dimension, and decoder realization are chosen. It also controls mean square sensitivity to the starting rewriting. A concentration bound for one joint expectation does not provide this reusable guarantee. Indeed, the lower bound in Theorem 17 shows that uniform approximation over all orbit functions requires the log⁡∣G∣\log|G| dependence that can be absent from a pointwise Monte Carlo bound.

What happens with finite trace sampling. The distribution level formulation isolates the cost of exploring the orbit. In practice, a finite decoder is run at each queried rewriting, producing a realized field F^x,ξ\widehat{F}_{x,\xi}. The bound in Equation (24) then compares sparse and full group averaging of that same realized field, simultaneously for every seed and trace configuration. Any difference between F^x,ξ\widehat{F}_{x,\xi} and the desired field FxDF_x^D is a decoder estimation problem and depends on the chosen decoding algorithm. Keeping this term separate makes clear which error is reduced by more rewritings and which is reduced by more traces per rewriting.

The separation has a direct error decomposition. Since ASA_S is an average of unitary translation operators, ∥AS∥op≤1\|A_S\|_{\mathrm{op}}\le1. On the event in Theorem 17,

∥ASF^x,ξ−qxD∥L2(G;H)≤∥F^x,ξ−FxD∥L2(G;H)+83log⁡(∣G∣/δ)∣S∣∥FxD−PGFxD∥L2(G;H).(18)\left\|A_S\widehat{F}_{x,\xi}-q_x^D\right\|_{L^2(G;\mathcal{H})} \le\left\|\widehat{F}_{x,\xi}-F_x^D\right\|_{L^2(G;\mathcal{H})} +\frac{8}{3}\sqrt{\frac{\log(|G|/\delta)}{|S|}}\left\|F_x^D-P_GF_x^D\right\|_{L^2(G;\mathcal{H})}. \tag*{(18)}

The first term is the finite decoding error and the second is the rewriting approximation error. They can be controlled independently and then combined through Equation (18). In particular, the first term requires control only of the aggregate decoded field in L2(G;H)L^2(G;\mathcal{H}), not uniform approximation over the trace space Ω\Omega.

For example, consider self consistency with nDn_D independent traces at each rewriting. If FxSC(g)F_x^{\mathrm{SC}}(g) is the class probability vector and F^xSC(g)\widehat{F}_x^{\mathrm{SC}}(g) is its empirical frequency vector, then

E[∥F^xSC−FxSC∥L2(G;RC)2]=1nDEg∼Unif⁡(G)[1−∥FxSC(g)∥22]≤1nD.(19)\mathbb{E}\left[\left\|\widehat{F}_x^{\mathrm{SC}}-F_x^{\mathrm{SC}}\right\|_{L^2(G;\mathbb{R}^C)}^2\right] =\frac{1}{n_D}\mathbb{E}_g\mathop{\sim}_{\operatorname{Unif}(G)}\left[1-\left\|F_x^{\mathrm{SC}}(g)\right\|_2^2\right] \le\frac{1}{n_D}. \tag*{(19)}

Thus, even this decoder term need not carry an explicit dependence on the number of classes. Averaged logits admit the usual Hilbert valued concentration bounds under a norm or tail assumption. Verifier weighted decoding additionally requires control of the weights and of its normalization denominator. These assumptions and rates belong to the selected decoder, whereas the rewriting rate is unchanged.

Thus, joint sampling is not ruled out, and it is fully appropriate for estimating a fixed linear joint expectation. It is not the object of our main scaling law because it can change the target for nonlinear decoders and, even when it does not, it does not yield the universal model agnostic symmetrization operator that is the focus of this paper.

Proof of Theorem 1

Proof of Theorem 1. Choose two distinct classes c0,c1∈Cc_0, c_1 \in\mathcal{C}, and let uc0,uc1∈RCu_{c_0}, u_{c_1} \in\mathbb{R}^{\mathcal{C}} be their standard basis vectors. Use the same decoder distribution in both worlds and define response fields that do not depend on ω\omega:

Vx(j)(g,ω):={0,g=e,ucj,g≠e,j∈{0,1}.V_x^{(j)}(g,\omega) := \begin{cases} 0, & g=e, \\ u_{c_j}, & g\ne e, \end{cases} \qquad j\in\{0,1\}.

Both response fields take values in [0,1]C[0,1]^{\mathcal{C}}. At the original prompt,

Vx(0)(e,ω)=Vx(1)(e,ω)=0V_x^{(0)}(e,\omega)=V_x^{(1)}(e,\omega)=0

for every ω\omega. Since the decoder distribution at xx is also the same, every trace and score observed by an algorithm that queries only xx has the same distribution in both worlds. This remains true under adaptive sampling because, conditional on any previous transcript, the next observation has the same conditional distribution in the two worlds. For a randomized algorithm, couple its internal random seed to be identical in both worlds. The complete transcript, including the internal randomness, then has the same distribution in both worlds.

The response fields are independent of ω\omega, so decoder averaging leaves them unchanged. Therefore,

PGFx(j)=∣G∣−1∣G∣ucj.P_G F_x^{(j)}=\frac{|G|-1}{|G|}u_{c_j}.

The unique invariant decision is cjc_j in world jj, and these decisions are different.

Let QQ be the common output distribution of the algorithm in the two worlds. Under a uniform prior on the worlds, its success probability is

12Q(c0)+12Q(c1)≤12,\frac{1}{2}Q(c_0)+\frac{1}{2}Q(c_1)\le\frac{1}{2},

because c0≠c1c_0\ne c_1. Hence its error probability is at least 1/21/2, regardless of the number of decoder samples.

Proof of Theorem 2

The proof adapts the operator concentration viewpoint used for partial group averaging in Tahmasebi et al. (2026) and the averaging complexity ideas of Tahmasebi & Weber [76]. Here these ideas are applied to test time rewriting operators acting on frozen model response fields.

We first state the complete version of Theorem 2. In addition to the Hilbert valued bound used in the main text, it records the underlying operator estimate and its consequence for every unitary representation of GG.

Theorem 17 (Universal sparse group averaging). Let SS contain ∣S∣|S| independent samples from Unif⁡(G)\operatorname{Unif}(G) and let δ∈(0,1)\delta\in(0,1). With probability at least 1−δ1-\delta,

∥AS−PG∥L2(G)→L2(G)≤83log⁡(∣G∣/δ)∣S∣.(20)\|A_S-P_G\|_{L^2(G)\to L^2(G)}\le\frac{8}{3}\sqrt{\frac{\log(|G|/\delta)}{|S|}}. \tag*{(20)}

On the same event, for every real Hilbert space H\mathcal{H} and every F∈L2(G;H)F\in L^2(G;\mathcal{H}),

∥ASF−PGF∥L2(G;H)≤83log⁡(∣G∣/δ)∣S∣∥F−PGF∥L2(G;H).(21)\|A_SF-P_GF\|_{L^2(G;\mathcal{H})}\le\frac{8}{3}\sqrt{\frac{\log(|G|/\delta)}{|S|}}\|F-P_GF\|_{L^2(G;\mathcal{H})}. \tag*{(21)}

Moreover, for every unitary representation π:G→U(H)\pi:G\to\mathcal{U}(\mathcal{H}), if PπP_\pi denotes the orthogonal projection onto its invariant vectors, then

∥1∣S∣∑i=1∣S∣π(si)−Pπ∥op≤83log⁡(∣G∣/δ)∣S∣.(22)\left\|\frac{1}{|S|}\sum_{i=1}^{|S|}\pi(s_i)-P_\pi\right\|_{\mathrm{op}}\le\frac{8}{3}\sqrt{\frac{\log(|G|/\delta)}{|S|}}. \tag*{(22)}

Finally, the logarithmic dependence is necessary in general: for G=(Z/2Z)nG=(\mathbb{Z}/2\mathbb{Z})^n, every multiset with fewer than n=log⁡2∣G∣n=\log_2|G| elements has operator error equal to one.

:::`

Proof of Theorem 17. Write m=∣S∣m = |S| and N=∣G∣N = |G|. The case N=1N = 1 is immediate, so assume N≥2N \ge2. For each sampled element sis_i, let

Xi:=Tsi−PG.X_i := T_{s_i} - P_G.

By Equation (13), the operators XiX_i are independent and have mean zero. Translation preserves constant functions and preserves the uniform mean, so

TsPG=PGTs=PGfor every s∈G.T_sP_G = P_GT_s = P_G \qquad\text{for every } s \in G.

Since TsT_s is unitary and PGP_G is an orthogonal projection, it follows that

XiXi∗=Xi∗Xi=I−PG,∥Xi∥op=1.X_iX_i^* = X_i^*X_i = I - P_G, \qquad\lVert X_i\rVert_{\mathrm{op}} = 1.

Consequently, the variance parameter in Lemma 11 satisfies

σ2=m∥I−PG∥op=m.\sigma^2 = m\lVert I-P_G\rVert_{\mathrm{op}} = m.

Applying Lemma 11 on the NN dimensional space L2(G)L^2(G) gives, for every u≥0u \ge0,

P(∥∑i=1mXi∥op≥u)≤2Nexp⁡(−u22m+2u/3).\mathbb{P}\left(\left\lVert\sum_{i=1}^{m}X_i \right\rVert_{\mathrm{op}} \ge u\right) \le2N\exp\left(-\frac{u^2}{2m+2u/3}\right).

Equivalently, for every t≥0t \ge0,

P(∥AS−PG∥L2(G)→L2(G)≥t)≤2Nexp⁡(−mt22+2t/3).(23)\mathbb{P}\left(\lVert A_S-P_G\rVert_{L^2(G)\to L^2(G)} \ge t\right) \le2N\exp\left(-\frac{mt^2}{2+2t/3}\right). \tag*{(23)}

Moreover, ∥AS−PG∥op≤1\lVert A_S-P_G\rVert_{\mathrm{op}} \le1, since on constant functions the difference vanishes and on their orthogonal complement it is an average of unitary operators. If

83log⁡(N/δ)m≥1,\frac{8}{3}\sqrt{\frac{\log(N/\delta)}{m}} \ge1,

the claimed bound is therefore deterministic. Otherwise, set

t=83log⁡(N/δ)m<1.t=\frac{8}{3}\sqrt{\frac{\log(N/\delta)}{m}}<1.

Since 2+2t/3≤8/32+2t/3\le8/3, Equation (23) gives

P(∥AS−PG∥op≥t)≤2N(Nδ)−8/3≤δ,\mathbb{P}\left(\lVert A_S-P_G\rVert_{\mathrm{op}}\ge t\right) \le2N\left(\frac{N}{\delta}\right)^{-8/3}\le\delta,

where the last inequality uses N/δ≥2N/\delta\ge2. This proves Equation (20) with the explicit constant 8/38/3.

Set T=AS−PGT=A_S-P_G. Since TPG=PGT=0TP_G=P_GT=0, Lemma 13 gives Equation (21) for every Hilbert space and every Hilbert valued field on the same event. Applying Lemma 15 gives Equation (22) for every unitary representation, again on the same event. No further probability bound or union bound is required.

It remains to prove the worst case necessity of log⁡∣G∣\log|G|. Let G=(Z/2Z)nG=(\mathbb{Z}/2\mathbb{Z})^n, so that ∣G∣=2n|G|=2^n, and suppose that m<nm<n. The sampled elements s1,…,sms_1,\ldots,s_m span a proper subspace of GG over Z/2Z\mathbb{Z}/2\mathbb{Z}. Hence there is a nonzero a∈Ga\in G such that

⟨a,si⟩=0(mod2)for every i.\langle a,s_i\rangle=0\pmod2 \qquad\text{for every }i.

Define the nonconstant character χa(h)=(−1)⟨a,h⟩\chi_a(h)=(-1)^{\langle a,h\rangle}. It has uniform mean zero, so PGχa=0P_G\chi_a=0. On the other hand,

(Tsiχa)(h)=χa(si+h)=χa(si)χa(h)=χa(h),(T_{s_i}\chi_a)(h)=\chi_a(s_i+h)=\chi_a(s_i)\chi_a(h)=\chi_a(h),

and therefore ASχa=χaA_S\chi_a=\chi_a. Thus,

∥AS−PG∥L2(G)→L2(G)≥1.\lVert A_S-P_G\rVert_{L^2(G)\to L^2(G)}\ge1.

The reverse inequality was established above, so the error equals one. Since n=log⁡2∣G∣n=\log_2|G|, fewer than log⁡2∣G∣\log_2|G| rewritings cannot achieve any operator error strictly below one for this family of groups. This proves the final claim.

Proof of Corollary 3

For completeness, the pathwise statement used in the main text is

∥ASF^x,ξ−PGF^x,ξ∥L2(G;H)≤83log⁡(∣G∣/δ)∣S∣∥F^x,ξ−PGF^x,ξ∥L2(G;H).(24)\left\|A_S\widehat{F}_{x,\xi}-P_G\widehat{F}_{x,\xi}\right\|_{L^2(G;\mathcal{H})} \le\frac{8}{3}\sqrt{\frac{\log(|G|/\delta)}{|S|}}\left\|\widehat{F}_{x,\xi}-P_G\widehat{F}_{x,\xi}\right\|_{L^2(G;\mathcal{H})}. \tag*{(24)}

Proof of Corollary 3. Fix the operator event in Theorem 17. For any choices of xx, θ\theta, τ\tau, DD, and H\mathcal{H}, the decoded response FxDF_x^D belongs to L2(G;H)L^2(G;\mathcal{H}). Applying Equation (21) to this function and using qxD=PGFxDq_x^D=P_GF_x^D proves Equation (10). The event depends only on SS, so the conclusion is simultaneous over all of these choices.

For a randomized decoder, condition on any seed ξ\xi and all sampled traces. Its output is then a deterministic field F^x,ξ∈L2(G;H)\widehat{F}_{x,\xi}\in L^2(G;\mathcal{H}). A second application of Equation (21) proves Equation (24). Because the operator event already holds for every function, the conclusion is simultaneous over all seeds and trace realizations and requires no union bound over Ω\Omega.

Proof of Corollary 4

Proof of Corollary 4. If c^S(h⋅X)≠y∗(X)\widehat{c}_S(h\cdot X)\ne y^*(X), then either cG(X)≠y∗(X)c_G(X)\ne y^*(X) or c^S(h⋅X)≠cG(X)\widehat{c}_S(h\cdot X)\ne c_G(X). Hence

RS≤RG+PX,h(c^S(h⋅X)≠cG(X)).R_S \le R_G+\mathbb{P}_{X,h}\bigl(\widehat{c}_S(h\cdot X)\ne c_G(X)\bigr).

Split the second probability according to whether ΔX≤t\Delta_X\le t. On {ΔX>t}\{\Delta_X>t\}, Lemma 16 shows that a changed decision requires

∥(ASFX)(h)−qX∥22≥t22.\left\|(A_SF_X)(h)-q_X\right\|_2^2\ge\frac{t^2}{2}.

For each XX with ΔX>t\Delta_X>t, Markov’s inequality over h∼Unif⁡(G)h\sim\operatorname{Unif}(G) therefore gives

Ph(c^S(h⋅X)≠cG(X), ΔX>t∣X)≤2t2∥ASFX−PGFX∥L2(G;RC)2≤128log⁡(∣G∣/δ)9t2∣S∣∥FX−PGFX∥L2(G;RC)2,\begin{aligned} \mathbb{P}_h\bigl(\widehat{c}_S(h\cdot X)\ne c_G(X),\ \Delta_X>t\mid X\bigr) \le\frac{2}{t^2}\left\|A_SF_X-P_GF_X\right\|_{L^2(G;\mathbb{R}^C)}^2 \\ &\le\frac{128\log(|G|/\delta)}{9t^2|S|}\left\|F_X-P_GF_X\right\|_{L^2(G;\mathbb{R}^C)}^2, \end{aligned}

where the second line uses Equation (21). Taking expectation over XX and adding PX(ΔX≤t)\mathbb{P}_X(\Delta_X\le t) proves Equation (11).

Experimental Details and Additional Results

This appendix gives the full setup of § 5 and all results.

Setup

Models and generation. We use Qwen2.5-7B-Instruct and Qwen2.5-1.5B-Instruct (Qwen Team et al., [63]), Phi-4-mini-instruct (Abdin et al., [1]), Llama-3.1-8B-Instruct (Grattafiori et al., [25]), and Qwen2.5-14B-Instruct in its 4-bit AWQ quantization (Lin et al., [44]), all frozen, with their chat templates, served with vLLM (Kwon et al., [37]) in bfloat16 (float16 for the quantized model). Reasoning traces are sampled at temperature 0.7 with a cap of 1024 tokens (1536 for n≥20n\ge20). A trace that reaches the cap without an answer line counts as wrong. Fewer than 1% of traces are cut on every task except triangle counting (4–13%) and Llama on triangle counting (20–36%). Prompts ask the model to “think step by step, keeping the reasoning brief” and to end with Answer: <value>, which is parsed as a number, a yes/no, a name, or a letter. For every instance we draw 16 rewritings from a seed that depends only on the task, the size, and the instance, so that every model sees the same rewriting set, and generate 4 traces at each rewriting plus one greedy trace, with 16 traces at the first rewriting so that self consistency with 16 traces is available. Every allocation (m,r)(m,r) with m⋅r=Bm\cdot r=B is obtained by subsampling this cache, averaged over 60 random subsets. Tokens per trace are the same whether a trace is sampled at the original prompt or at a rewriting (ratio 0.999, range 0.975–1.066 over the 35 Qwen2.5-7B cells), so a budget in forward passes is also a budget in generated tokens.

Graphs and groups. Graphs are drawn from G(n,p)G(n,p) with pp uniform in [0.15,0.6][0.15,0.6] for n≤8n \le8, [0.1,0.4][0.1,0.4] for n≤12n \le12, and [0.07,0.3][0.07,0.3] otherwise, rejecting graphs without edges. Yes/no tasks are balanced. A prompt lists the nodes and the edges as pairs with integer labels, followed by the question. A rewriting is a pair of a node relabeling and an edge-order permutation. The relabeling is applied first, each edge is written with its smaller label first and the list is sorted, and then the edge permutation is applied, so that g↦g⋅xg \mapsto g \cdot x is an action of Sn×S∣E∣S_n \times S_{\lvert E\rvert} on prompts. Questions that name nodes are relabeled with the graph. Instance pools are fixed per (task, size), so the 100-instance and 200-instance cells share their first 100 instances. The stochastic block model uses two equal communities with within-community edge probability 2.5p2.5p and between-community probability p/4p/4, and the planted-cycle graphs add a cycle through 3 to n/2n/2 random nodes to G(n,p/2)G(n,p/2). The serialization variants use adjacency lists (“Node A is connected to B, D.”) or letter labels Herbst et al. [28].

Other tasks. Deduction. There are kk people with a hidden total order of heights. The k−1k-1 adjacent comparisons are given as premises in a random order, half of them phrased as “A is taller than B” and half as “B is shorter than A”. The three questions are who is the tallest, who is the jj-th tallest (2≤j≤k−12 \le j \le k-1), and whether one named person is taller than another non-adjacent one (balanced yes/no). Rewritings permute the premises (Sk−1S_{k-1}), flip the phrasing of each premise (Z2k−1\mathbb{Z}_2^{k-1}), or both. ARC-Challenge Clark et al. [17] uses 500 random test questions with four options, all 24 orderings of the options, and 2 sampled traces and one greedy trace per ordering. The predicted letter is mapped back to the option it names before voting. SST-2 Socher et al. [71] uses 200 test sentences with k∈{4,8,16}k \in\{4,8,16\} balanced training demonstrations, rewritten by permuting the demonstrations (SkS_k).

Rewriting versus decoding on graphs

Table 2 reports every (model, task, size) cell on Erdős–Rényi graphs. Table 3 gives the allocation grid at budget 16 for Qwen2.5-7B. On edge counting and edge existence the all-self-consistency column (m=1m=1) is the worst cell of every row, while on the tasks that are at chance or beyond the model the rows are flat. Table 4 repeats the comparison on structured graphs and other serializations. The gains replicate on both topologies. On edge counting at n=24n=24 the gain is +10.9+10.9 on SBM graphs and +6.8+6.8 on planted-cycle graphs. Serialization changes which tasks are sensitive but not the rule. With adjacency lists, counting edges requires de-duplicating the lists and the model fails at it (15%), while node degree becomes a lookup (95%), and the significant gains move accordingly (node degree +3.3+3.3, connectivity +1.4+1.4).

ModelTasknnNNGreedySC-16Sym.-16Gainflip
Qwen2.5-7Bedge count82000.990.991.00+1.0+1.0 [+0.0,+2.5][+0.0,+2.5]0.12
Qwen2.5-7Bedge count122000.920.961.00+3.9 [+1.4,+6.7][+1.4,+6.7]0.45
Qwen2.5-7Bedge count162000.810.960.98+2.2+2.2 [−0.2,+5.0][-0.2,+5.0]0.64
Qwen2.5-7Bedge count202000.700.910.96+4.7 [+1.2,+8.7][+1.2,+8.7]0.80
ModelTasknnNNGreedySC-16Sym.-16Gainflip
edge count241000.420.820.92+10.7 [+3.8, +18.0]0.94
edge existence82000.940.961.00+3.5 [+1.2, +6.0]0.49
edge existence122000.920.981.00+2.2 [+0.5, +4.5]0.58
edge existence162000.920.971.00+2.7 [+0.8, +4.9]0.60
edge existence202000.850.981.00+2.1 [+0.3, +4.1]0.75
edge existence241000.880.961.00+3.9 [+0.8, +8.0]0.75
node degree82000.680.700.75+5.7 [+0.4, +10.9]0.71
node degree122000.610.640.65+0.7 [−4.3, +5.9]0.74
node degree162000.590.570.56−0.3 [−5.9, +5.3]0.80
node degree202000.420.400.41+0.7 [−4.4, +5.6]0.84
node degree241000.440.400.39−1.5 [−7.4, +4.1]0.90
components81000.670.760.77+1.6 [−4.9, +8.0]0.90
components121000.520.680.70+1.2 [−6.2, +9.1]0.97
components161000.390.480.52+3.9 [−1.6, +9.1]1.00
components201000.470.630.65+1.3 [−1.2, +3.3]0.99
components241000.440.670.67−0.4 [−2.1, +1.0]1.00
connected82000.890.980.99+0.3 [−1.1, +2.0]0.64
connected122000.840.910.92+1.0 [−2.3, +4.5]0.83
connected162000.800.840.84−0.2 [−3.7, +3.9]0.83
connected202000.690.700.69−0.4 [−3.2, +2.4]0.76
connected241000.610.640.65+0.8 [−2.8, +4.1]0.76
cycle81000.760.690.65−3.4 [−6.8, −0.6]0.46
cycle121000.590.590.57−2.0 [−6.6, +2.6]0.47
cycle161000.590.550.54−1.0 [−4.5, +1.4]0.42
cycle201000.580.520.51−0.8 [−3.1, +0.7]0.52
cycle241000.560.510.50−0.9 [−2.7, +0.1]0.50
triangles81000.220.250.24−1.5 [−7.9, +4.2]0.97
triangles121000.230.240.20−4.8 [−11.7, +1.7]1.00
triangles161000.100.200.15−4.8 [−10.8, +1.4]1.00
triangles201000.110.110.10−1.0 [−7.0, +4.0]1.00
triangles241000.060.060.07+1.3 [−3.2, +5.4]1.00
Phi-4-miniedge count82000.980.991.00+0.5 [+0.0, +1.5]0.27
Phi-4-miniedge count122000.870.950.99+4.8 [+1.9, +7.9]0.68
Phi-4-miniedge count162000.710.890.99+9.7 [+5.5, +14.0]0.79
Phi-4-miniedge existence82000.940.981.00+1.7 [+0.1, +3.5]0.51
Phi-4-miniedge existence122000.930.981.00+1.8 [+0.3, +3.8]0.58
Phi-4-miniedge existence162000.890.971.00+2.4 [+0.6, +4.5]0.67
Phi-4-mininode degree82000.730.850.95+9.3 [+4.6, +14.1]0.72
Phi-4-mininode degree122000.660.760.86+9.9 [+4.6, +15.1]0.77
Phi-4-mininode degree162000.680.750.82+6.9 [+2.2, +11.9]0.88
Phi-4-minicomponents81000.690.760.76+0.2 [−5.7, +6.3]0.73
Phi-4-minicomponents121000.510.620.61−1.1 [−6.0, +3.2]0.87
Phi-4-minicomponents16600.430.440.44−0.0 [−2.8, +2.5]0.93
Phi-4-miniconnected81000.810.760.79+2.8 [−2.6, +8.2]0.58
Phi-4-miniconnected121000.620.740.75+1.0 [−5.5, +7.2]0.79
Phi-4-miniconnected16600.550.640.62−1.7 [−8.2, +4.3]0.80
Phi-4-minicycle81000.680.830.76−6.9 [−12.6, −1.5]0.88
Phi-4-minicycle121000.570.630.67+4.1 [−0.9, +9.1]0.98
Phi-4-minicycle16600.620.630.62−0.6 [−7.8, +6.2]0.98
Phi-4-minitriangles81000.340.410.44+2.9 [−2.7, +8.9]1.00
Phi-4-minitriangles121000.220.300.31+0.6 [−5.9, +7.4]1.00
Phi-4-minitriangles16600.100.230.21−2.1 [−8.2, +3.4]1.00
Llama-3.1-8Bedge count81000.740.910.96+5.7 [+2.0, +10.4]0.98
Llama-3.1-8Bedge count121000.360.810.79−2.0 [−8.3, +4.6]0.99
Llama-3.1-8Bedge count16600.280.610.70+8.9 [+0.9, +16.9]1.00
Llama-3.1-8Bedge existence81000.840.940.98+4.0 [+0.1, +8.6]0.45
Llama-3.1-8Bedge existence121000.840.910.91−0.2 [−5.3, +4.6]0.50
Llama-3.1-8Bedge existence16600.720.810.86+5.3 [−1.0, +12.2]0.57
Llama-3.1-8Bnode degree81000.790.890.97+7.8 [+2.8, +13.4]0.83
Llama-3.1-8Bnode degree121000.740.850.90+4.8 [−1.1, +11.2]0.90
Llama-3.1-8Bnode degree16600.680.880.90+2.0 [−4.1, +8.8]0.87
Llama-3.1-8Bcomponents81000.520.670.64−2.3 [−9.9, +5.1]1.00
ModelTasknnNNGreedySC-16Sym.-16Gainflip
components121000.370.510.51+0.3 [−8.7, +9.3]1.00
components16600.280.410.38−3.3 [−13.5, +6.4]1.00
connected81000.720.740.71−2.3 [−6.7, +1.7]0.77
connected121000.540.580.57−0.8 [−4.1, +2.3]0.91
connected16600.500.530.52−1.3 [−6.3, +2.3]0.90
cycle81000.560.520.53+0.9 [−1.0, +3.0]0.91
cycle121000.450.500.50+0.0 [+0.0, +0.1]0.92
cycle16600.430.500.50+0.0 [+0.0, +0.0]0.97
triangles81000.020.050.06+0.7 [−2.7, +3.9]1.00
triangles121000.020.030.02−0.2 [−3.5, +2.4]1.00
triangles16600.020.010.01−0.1 [−0.9, +0.6]1.00
Qwen2.5-14B-AWQedge count81001.000.991.00+0.5 [+0.0, +1.7]0.03
Qwen2.5-14B-AWQedge count121000.790.800.78−1.5 [−4.7, +1.0]0.36
Qwen2.5-14B-AWQedge count16600.630.710.70−1.2 [−6.7, +4.2]0.52
Qwen2.5-14B-AWQedge existence81001.001.001.00+0.0 [+0.0, +0.0]0.04
Qwen2.5-14B-AWQedge existence121000.981.001.00+0.0 [+0.0, +0.0]0.14
Qwen2.5-14B-AWQedge existence16600.980.991.00+0.7 [+0.0, +2.2]0.17
Qwen2.5-14B-AWQnode degree81000.900.901.00+10.1 [+4.3, +16.2]0.55
Qwen2.5-14B-AWQnode degree121000.780.820.94+12.1 [+5.9, +19.2]0.65
Qwen2.5-14B-AWQnode degree16600.830.850.94+8.9 [+2.0, +16.5]0.73
Qwen2.5-14B-AWQcomponents81000.800.860.87+1.5 [−4.0, +7.0]0.58
Qwen2.5-14B-AWQcomponents121000.680.710.70−0.9 [−6.1, +4.0]0.87
Qwen2.5-14B-AWQcomponents16600.530.540.50−4.4 [−11.9, +2.2]0.90
Qwen2.5-14B-AWQconnected81000.900.930.91−2.8 [−7.4, +1.6]0.38
Qwen2.5-14B-AWQconnected121000.720.820.80−1.7 [−5.7, +1.9]0.53
Qwen2.5-14B-AWQconnected16600.720.730.71−2.0 [−8.5, +4.1]0.58
Qwen2.5-14B-AWQcycle81000.700.700.66−3.5 [−7.0, −0.6]0.30
Qwen2.5-14B-AWQcycle121000.620.630.59−3.5 [−7.8, +0.1]0.40
Qwen2.5-14B-AWQcycle16600.570.550.57+2.6 [−0.2, +6.6]0.32
Qwen2.5-14B-AWQtriangles81000.280.310.36+5.5 [−0.2, +11.6]0.95
Qwen2.5-14B-AWQtriangles121000.170.210.23+2.0 [−5.1, +8.5]0.99
Qwen2.5-14B-AWQtriangles16600.120.260.22−4.3 [−14.1, +5.0]1.00

Table 2. Accuracy at a budget of 16 forward passes on Erdős–Rényi graphs for four model families: one greedy pass at a random rewriting, self consistency with 16 traces at a random rewriting (SC-16), and one trace at each of 16 rewritings (Sym.-16); paired gain (Sym.-16 minus SC-16) in points with 95% bootstrap interval over the NN instances (bold: interval excludes zero); “flip” is the fraction of instances whose greedy answer changes across the 16 re­writings.

ModelTasknnNNGreedySC-16Sym.-16Gainflip
SBMedge count161000.700.920.97+4.8 [+0.2, +10.2]0.78
SBMedge count241000.400.770.88+10.9 [+3.5, +18.5]1.00
SBMedge existence161000.900.971.00+2.8 [+0.3, +6.2]0.77
SBMedge existence241000.860.970.99+2.2 [−0.3, +5.5]0.85
SBMnode degree161000.500.480.45−2.1 [−10.8, +6.2]0.91
SBMnode degree241000.200.190.15−4.6 [−10.7, +0.8]0.97
SBMcomponents161000.570.740.79+5.0 [+1.7, +8.9]0.99
SBMcomponents241000.520.790.78−0.1 [−2.9, +2.8]1.00
SBMconnected161000.770.790.82+2.9 [−2.7, +8.9]0.79
SBMconnected241000.570.610.57−3.8 [−8.2, +0.2]0.75
SBMcycle161000.610.550.52−2.8 [−6.1, −0.2]0.48
SBMcycle241000.560.500.50+0.0 [+0.0, +0.0]0.38
SBMtriangles161000.130.140.11−2.6 [−7.6, +1.8]0.99
SBMtriangles241000.010.020.03−0.9 [−1.8, +2.9]1.00
planted cycleedge count161000.960.981.00+2.0 [+0.0, +5.0]0.54
planted cycleedge count241000.500.890.95+6.8 [+1.0, +13.1]0.84
planted cycleedge existence161000.950.991.00+0.5 [+0.0, +1.5]0.54
planted cycleedge existence241000.900.981.00+1.7 [+0.0, +4.3]0.61
planted cyclenode degree161000.820.800.83+3.0 [−3.5, +9.8]0.68
planted cyclenode degree241000.560.560.55−0.3 [−9.2, +8.4]0.84

Table 4. Graph topology and serialization variants, Qwen2.5-7B, budget 16. SBM: two communities; planted cycle: a cycle on 3 to n/2n/2 random nodes plus sparse noise (cycle detection is omitted since the answer is always yes); adjacency lists and letter labels follow Herbst et al. [28] (edge reordering acts trivially on adjacency lists, so only relabeling moves the prompt).

Tasknnm=1m=1 (r=16r=16)m=4m=4 (r=4r=4)m=8m=8 (r=2r=2)m=16m=16 (r=1r=1)
edge count80.9901.0001.0001.000
120.9580.9950.9980.999
160.9630.9840.9850.988
200.9100.9480.9590.961
240.8170.9120.9270.930
edge existence80.9630.9991.0001.000
120.9770.9991.0001.000
160.9731.0001.0001.000
200.9770.9910.9930.995
240.9601.0000.9981.000
node degree80.6950.7330.7500.760
120.6360.6370.6360.654
160.5700.5660.5600.557
200.4030.4300.4130.403
240.3980.3730.3670.385
components80.7650.7680.7620.785
120.6830.6830.6730.707
160.4850.5180.5180.517
200.6300.6420.6470.645
240.6720.6720.6680.673
connected80.9830.9760.9880.993
120.9070.9250.9230.917
160.8380.8280.8330.834
200.6960.6980.6890.699
240.6420.6670.6480.655
cycle80.6830.6600.6550.655
120.5920.5630.5770.567
160.5500.5470.5380.535
200.5120.5050.5080.508
240.5100.5020.5020.500
triangles80.2530.2300.2480.225
120.2450.1950.1950.197
160.1980.1450.1620.150
200.1180.1050.0750.082
240.0570.0900.0780.092

Table 3. Allocation of a budget of 16 forward passes between mm rewritings and r=16/mr=16/m traces per rewriting, Qwen2.5-7B, with a majority vote over all traces.

Theorem 4 predicts the structure of these tables. We call a cell sensitive if the greedy answer changes on more than half of its instances and competent if greedy accuracy exceeds 40%. Of the 98 cells in Table 2, the 60 sensitive and competent ones contain 20 significant gains and 1 significant loss (mean +2.1+2.1 points), the 19 sensitive but incompetent ones contain 1 gain and no loss (mean +0.1+0.1), and the 19 insensitive ones contain 3 gains and 2 losses (mean −0.1-0.1). The losses are cycle detection at n=8n=8 for Qwen2.5-7B (−3.4-3.4), Phi-4-mini (−6.9-6.9), and Qwen2.5-14B (−3.5-3.5). On acyclic graphs all models answer “yes” more often than not under a random rewriting, a bias that does not depend on the representation. On those instances the greedy answer at the starting rewriting says “yes” 48% of the time for Qwen2.5-7B, the greedy answers over the orbit 62%, and the sampled traces 63%. Any vote amplifies a majority, so both self consistency and symmetrization fall below a single greedy pass (0.69 and 0.65 against 0.76). This is the term RGR_G of Theorem 4 being larger than the error of a typical representation, and it is unrelated to order sensitivity.

ModelTasknnNNGreedySC-16Sym.-16Gainflip
components161000.210.230.27+3.7 [−1.3, +8.8]1.00
components241000.160.310.30−1.2 [−5.0, +1.9]1.00
connected161000.720.830.85+2.0 [−2.5, +6.7]0.90
connected241000.670.660.68+2.4 [−2.2, +6.7]0.89
triangles161000.130.180.24+5.2 [−1.6, +11.7]1.00
triangles241000.070.110.12+1.0 [−4.7, +5.9]1.00
adjacency listsedge count161000.150.130.09−4.2 [−9.4, +0.6]0.99
edge existence161000.981.001.00+0.0 [+0.0, +0.0]0.24
node degree161000.950.971.00+3.3 [+0.3, +7.2]0.45
connected161000.940.970.98+1.4 [+0.1, +3.2]0.36
letter labelsedge count161000.950.981.00+1.6 [−0.0, +4.2]0.43
edge existence161000.971.001.00+0.0 [+0.0, +0.0]0.52
node degree161000.640.660.68+2.5 [−6.0, +10.7]0.78
connected161000.710.790.83+4.2 [−0.8, +9.3]0.93

Table 9.

Scaling in the graph size

Figure 6 shows how sensitivity and gain depend on nn at a fixed budget. On edge counting the flip rate rises from 0.12 at n=8n = 8 to 0.94 at n=24n = 24 and the gain from +1.0 to +10.8 points. Edge existence is sensitive at every size and gains +2 to +4 points throughout. The cost of 16 rewritings does not change with nn, although ∣G∣\lvert G\rvert grows from 8!∣E∣!8!\lvert E\rvert! to 24!∣E∣!24!\lvert E\rvert! across the figure. This is what the log⁡∣G∣\log\lvert G\rvert law of Theorem 2 buys.

Figure 6. Order sensitivity and the gain of symmetrization against the graph size nn, Qwen2.5-7B, budget 16. The left panel shows the fraction of instances whose greedy answer changes across 16 rewritings, and the right panel the paired gain of 16 rewritings over 16 traces.

Per-rewriting accuracy

Figure 7 answers whether a well-chosen serialization could replace the average. For each instance we evaluate the greedy answer at each of its 16 rewritings and record whether the model is right at all of them, at a random one, and at at least one. On edge counting at n=24n = 24 only 6% of the graphs are solved at every rewriting and a random rewriting solves 38%, but some rewriting solves 93%, and the vote over the 16 rewritings reaches 92%. The model has the answer on most graphs, just not at most representations, and the vote recovers nearly everything an oracle choice of serialization would. The same holds on edge existence (25%, 89%, 100% against a vote of 100% at n=20n = 20). On node degree, component counting, connectivity, and cycle detection the oracle is also high (88% to 97% at n=24n = 24) but the vote stays near the accuracy of a random rewriting. There, on a typical instance only a minority of rewritings are right, so the majority of the orbit is wrong and averaging converges, faithfully, to the wrong answer. This is the distinction Theorem 4 draws between the accuracy of the symmetrized decision cGc_G and the existence of some good representation. Symmetrization delivers the former, and only the former.

Figure 7. Single rewritings against their vote, Qwen2.5-7B, greedy decoding at each of the 16 rewritings of every instance. The blue bar runs from the fraction of instances answered correctly at all 16 rewritings (worst case, an adversary picks the serialization) to the fraction answered correctly at at least one (best case, an oracle picks it), and the dot is the accuracy of a random rewriting. The orange mark is Sym-16, the vote over one sampled trace at each of the 16 rewritings.

Deduction, multiple choice, and few-shot order

Figure 8 and Table 5 give the deduction task in full. Flipped statements are harder for the model than “taller than” statements, so the three groups have different baselines. Within each group symmetrization is significantly better than self consistency in 13 of the 27 cells and never significantly worse (the largest negative difference is −0.9-0.9 points, well inside its interval). The product group gives the largest gains, as it is both the largest orbit and the one whose rewritings differ most from one another.

Figure 8. The deduction task under three groups, all three questions, Qwen2.5-7B, budget 16. Each panel compares symmetrization with self consistency and greedy decoding on the same orbit.

ModelTaskkkNNGreedySC-16Sym.-16Gainflip
reordertallest51000.981.001.00+0.0+0.0 [+0.0,+0.0+0.0, +0.0]0.09
tallest81000.930.991.00+0.5+0.5 [+0.0,+1.5+0.0, +1.5]0.72
tallest111000.830.941.00+5.8+5.8 [+1.8,+10.8+1.8, +10.8]0.89
jj-th tallest51000.900.991.00+0.9+0.9 [−0.2,+2.9-0.2, +2.9]0.70
jj-th tallest81000.630.840.92+7.5+7.5 [+0.5,+15.1+0.5, +15.1]0.98
jj-th tallest111000.490.640.72+7.8+7.8 [−0.7,+15.9-0.7, +15.9]1.00
comparison51000.930.991.00+1.3+1.3 [−0.2,+3.8-0.2, +3.8]0.38
comparison81000.850.940.97+2.8+2.8 [−1.1,+7.3-1.1, +7.3]0.70
comparison111000.800.880.90+2.6+2.6 [−1.5,+6.9-1.5, +6.9]0.75
fliptallest51000.951.001.00+0.0+0.0 [+0.0,+0.0+0.0, +0.0]0.29
tallest81000.740.950.99+4.0+4.0 [+0.4,+8.1+0.4, +8.1]0.90
tallest111000.610.770.86+9.6+9.6 [+2.6,+16.8+2.6, +16.8]0.99
jj-th tallest51000.800.930.99+6.5+6.5 [+2.1,+11.7+2.1, +11.7]0.91
jj-th tallest81000.320.440.60+16.4+16.4 [+8.0,+24.7+8.0, +24.7]1.00
jj-th tallest111000.180.280.30+2.8+2.8 [−4.8,+10.1-4.8, +10.1]1.00
comparison51000.981.001.00−0.2-0.2 [−0.4,+0.0-0.4, +0.0]0.29
ModelTaskkkNNGreedySC-16Sym.-16Gainflip
comparison81000.720.800.88+8.3 [+2.1, +15.0]0.81
comparison111000.710.740.81+6.6 [−0.2, +13.8]0.88
bothtallest51001.001.001.00+0.0 [+0.0, +0.0]0.51
tallest81000.750.861.00+13.9 [+7.0, +20.9]0.98
tallest111000.510.790.99+19.5 [+11.9, +27.3]1.00
jj-th tallest51000.810.971.00+3.0 [+0.4, +6.5]0.92
jj-th tallest81000.350.500.64+14.1 [+5.6, +22.8]1.00
jj-th tallest111000.210.330.32−0.9 [−9.1, +6.8]1.00
comparison51000.950.981.00+1.9 [−0.1, +4.8]0.46
comparison81000.820.880.95+6.8 [+1.6, +12.1]0.88
comparison111000.700.750.83+8.5 [+1.6, +15.2]0.93

Table 5. Deduction from k−1k - 1 adjacent height comparisons among kk people, Qwen2.5-7B, budget 16, under premise reordering (Sk−1S_{k-1}), statement flipping (Z2k−1\mathbb{Z}_{2}^{k-1}), and their product. Each group is compared against its own baselines, since the starting prompt is a random element of that orbit.

Table 6: ARC-Challenge with permuted options, Qwen2.5-7B, 500 questions, with 95% bootstrap intervals over questions. “Aligned” maps each predicted letter back to the option it names before voting (§ 3), and “not aligned” votes over the letters as written.

On ARC (Table 6) the per-ordering greedy accuracy ranges from 0.902 to 0.932 and 25.6% of the questions change their answer under some ordering. Aligned symmetrization over 16 orderings gains +2.6 points over the matched vote at the original ordering ([+0.8, +4.6]), and unaligned voting is at chance, as the equivariant setting of § 3 requires. On SST-2 (Table 7) the model is at 96% and only 6–8% of queries are sensitive to the order of the demonstrations, so there is nothing to average and symmetrization changes accuracy by less than half a point.

ProcedureAccuracy
Greedy, original ordering (1 call)0.918 [0.894, 0.940]
Vote over 3 traces, original ordering0.922 [0.898, 0.944]
4 orderings, aligned, one trace each0.934 [0.914, 0.956]
16 orderings, aligned, one trace each0.946 [0.926, 0.966]
All 24 orderings, aligned, all 72 traces0.948 [0.928, 0.966]
16 orderings, not aligned0.244 [0.206, 0.282]

Table 6.

ModelTaskkkNNGreedySC-16Sym.-16Gainflip
SST-2SST-242000.950.960.96−0.3 [−1.1, +0.3]0.07
SST-282000.960.970.97+0.3 [−0.3, +1.2]0.08
SST-2162000.950.970.97+0.2 [+0.0, +0.7]0.06

Table 7.

Table 7: Few-shot sentiment classification (SST-2) with kk demonstrations, rewritten by permuting the demonstrations (SkS_k), Qwen2.5-7B, budget 16.

Rewritings from a paraphrasing model

When no group is available, rewritings can be sampled from a kernel K(x,⋅)K(x,\cdot) given by a paraphrasing model. For rewritings drawn independently from KK, ASA_S is an unbiased Monte Carlo estimate of the KK-average at rate ∣S∣−1/2|S|^{-1/2}. What is lost relative to Theorem 2 is that the target is meaningful only up to the drift ε=Px′∼K(x,⋅)[y∗(x′)≠y∗(x)]\varepsilon= \mathbb{P}_{x' \sim K(x,\cdot)}[y^*(x') \ne y^*(x)], which enters Theorem 4 as an additive term, and that there is no orbit over which to be uniform. We ask Phi-4-mini (cross-family) or Qwen2.5-7B itself (same model) for 24 rewordings of the graph description, keep the question verbatim, and keep a rewording only if a second call that extracts its edge list returns exactly the true edge set. The rejection rate is our estimate of ε\varepsilon. The cross-family paraphraser keeps 21 of 24 rewordings at n=12n = 12 and 14 of 24 at n=24n = 24 (ε≈12%\varepsilon\approx12\% and 33%). The same-model paraphraser keeps 9 of 24, many of them near duplicates. Table 8 and Figure 9 give the results. Gains over self consistency appear where the exact group gains (+9.8 on edge counting at n=12n = 12 and +6.5 at $n = 24). On the same instances, however, the paraphrase orbit average is below the group orbit average (0.87 against 1.00 on edge counting at n=24n = 24, 0.79 against 0.94 on connectivity at n=12n = 12), both because of drift and because reworded descriptions are harder for the model than the canonical one. The same-model paraphrases gain nothing on edge counting (+0.7). Diversity of the rewriting distribution is what matters, and the group provides it exactly.

Figure 9. Gain of 16 rewritings over 16 traces on the same orbit, for the exact group and for the two paraphrasers, Qwen2.5-7B answering, with 95% intervals over instances.

ModelTasknnNNGreedySC-16Sym.-16Gainflip
cross-familyedge count121000.850.890.99+9.8 [+3.8, +15.9]0.80
edge count24780.460.680.74+6.5 [−3.0, +16.4]0.96
edge existence121000.960.960.98+1.2 [−0.4, +3.7]0.30
edge existence24720.940.970.98+0.8 [−0.6, +2.8]0.38
node degree121000.650.660.62−4.5 [−9.6, +0.2]0.55
node degree24770.520.530.55+1.8 [−3.6, +7.5]0.60
components121000.470.590.62+2.6 [−4.1, +9.7]0.93
components24730.490.530.55+2.0 [−1.6, +5.7]0.75
connected121000.750.800.78−2.1 [−6.9, +2.2]0.74
connected24860.620.550.57+2.1 [−2.9, +7.3]0.58
cycle121000.620.580.59+0.6 [−1.2, +2.2]0.39
cycle24840.460.410.41−0.3 [−1.4, +0.5]0.44
triangles121000.200.270.21−5.9 [−12.7, +0.9]0.99
triangles24750.110.080.10+1.3 [−3.5, +5.8]0.97
same-modeledge count24600.470.840.85+0.7 [−6.4, +7.8]0.80
edge existence24580.910.980.98−0.1 [−3.9, +4.4]0.28
node degree24610.640.600.65+4.6 [+0.4, +9.6]0.34

Table 8. Rewritings sampled from a paraphrasing model instead of the group, Qwen2.5-7B answering, budget 16; rows are labeled by the paraphraser (cross-family: Phi-4-mini; same-model: Qwen2.5-7B). Instances with fewer than one surviving paraphrase are dropped, hence N<100N < 100 at n=24n = 24. Baselines (Greedy, SC-16) are computed on a paraphrase, so they differ from those of the exact group on the same instances (Table 2).

A model trained from scratch

To isolate the mechanism from any property of pretrained models, we train a four-layer transformer encoder (d=128d = 128, 0.8M parameters) on edge counting for graphs with n=10n = 10 nodes, 6,000 steps of batch 256 on freshly sampled graphs, under three regimes. The first uses the canonical serialization only, the second rewrites 10% of the training examples at random, and the third rewrites every training example at random. Figure 10 shows the three cases of Theorem 4 in one model. The canonical-only model is perfect on its training format and 85% accurate on a random rewriting, with 72% of test graphs changing their prediction across rewritings. Averaging its class probabilities over 16 rewritings gives 99.5% and over 64 gives 100%, and its relative error follows ∣S∣−1/2|S|^{-1/2} to two decimals (1.00, 0.71, 0.50, 0.35 for ∣S∣=1,2,4,8|S| = 1, 2, 4, 8). Both augmented models are invariant (flip rate 0.000) and gain nothing. On the node-degree task training is bimodal at this budget (some seeds converge to 100% and others stall near 55%, in every regime), so we report edge counting only. The seeds that converge on node degree show the same pattern.

Figure 10. A 0.8M-parameter transformer encoder trained from scratch to count the edges of graphs with n=10n = 10 nodes, under three training regimes, evaluated on 2,000 held-out graphs, with mean and standard deviation over two seeds. “flip” is the fraction of test graphs whose prediction changes across 16 rewritings.

Relative error of language-model fields at large nn

For Figure 5 we prompt the model to answer with a single token and read its next-token distribution over the answer classes, which gives FxD(g)F_x^D(g) exactly for every decoding rule (expected logits, self consistency probabilities at τ∈{0.5,1}\tau\in\{0.5, 1\}, greedy). For n≥8n \ge8 the orbit cannot be enumerated, so we draw one multiset SS of 32 rewritings and 2 starting rewritings per graph, and estimate PGFP_G^F from 64 independent rewritings. The estimate adds a known variance ∥F−PGF∥2/64\lVert F - P_G^F\rVert^2/64 to the numerator, which we subtract. The ratio is pooled over the 60 graphs of each task and the median over tasks is plotted. The rescaled error ∣S∣∥ASF−PGF∥/∥F−PGF∥\sqrt{|S|}\lVert A_SF - P_G^F\rVert/\lVert F - P_G^F\rVert lies in [0.9,1.1][0.9, 1.1] for all n∈{8,12,16,32}n \in\{8, 12, 16, 32\}, decoders, and tasks whose fields are not nearly constant. For Qwen2.5-1.5B on the same SS it lies in [0.96,1.09][0.96, 1.09]. Figure 11 separates the two factors of the group. Relabeling nodes moves the answer more than reordering edges on every task (87% against 70% of instances on edge existence at n=32n = 32), and reordering alone is substantial on the edge-level tasks.

Figure 11. Fraction of graphs whose single-token answer changes under node relabeling only, edge reordering only, and both, Qwen2.5-7B, 60 graphs per task.

Computing the uniform constant

For a multiset SS, the operator AS−PGA_S-P_G acts on L2(G)L^2(G) with uniform measure, and AS−PG=(AS−PG)(I−PG)A_S-P_G=(A_S-P_G)(I-P_G) since ASPG=PGAS=PGA_SP_G=P_GA_S=P_G. Hence

sup⁡F∉im⁡PG∥ASF−PGF∥∥F−PGF∥=∥AS−PG∥op\sup_{F\notin\operatorname{im}P_G}\frac{\lVert A_SF-P_GF\rVert}{\lVert F-P_GF\rVert}=\lVert A_S-P_G\rVert_{\mathrm{op}}

for scalar fields, and the same value holds for Hilbert-valued fields by applying the scalar bound coordinatewise in an orthonormal basis. For G=SnG=S_n we represent functions on GG as vectors indexed by the lexicographic rank of permutations, implement ASA_S and its adjoint by index maps h↦sihh\mapsto s_i h, and compute the largest singular value with ARPACK (Lehoucq et al. [40]) through SciPy (Virtanen et al. [81]). For n≤5n\leq5 we checked every draw against a dense singular value decomposition; all 70 draws agree to 10−610^{-6}. For G=Z2dG=\mathbb{Z}_2^d every irreducible representation is a character (Diaconis [20]) χT(s)=(−1)⟨T,s⟩\chi_T(s)=(-1)^{\langle T,s\rangle}, so ∥AS−PG∥op=max⁡T≠0∣1∣S∣∑iχT(si)∣\lVert A_S-P_G\rVert_{\mathrm{op}}=\max_{T\neq0}\left|\frac{1}{|S|}\sum_i\chi_T(s_i)\right|, which we read off the Walsh–Hadamard transform of the empirical distribution of SS in O(d2d)O(d2^d) time. Figure 12 shows the full curves with their spread over five draws. This constant is the worst case over all fields, and Figure 13 shows that on the exactly enumerated orbits of graphs with 4 and 5 nodes, no language-model field exceeds it for ∣S∣>1|S|>1, for Qwen2.5-1.5B with six decoding rules.

Figure 12. Exact uniform constant ∥AS−PG∥op\lVert A_S-P_G\rVert_{\mathrm{op}} of Theorem 2 against ∣S∣|S| for G=SnG=S_n (graphs on n=3,…,7n=3,\ldots,7 nodes, ∣G∣=n!|G|=n!) and G=Z2dG=\mathbb{Z}_2^d (∣G∣=2d|G|=2^d, d=4,…,20d=4,\ldots,20); mean and standard deviation over five draws of SS. For Z2d\mathbb{Z}_2^d the constant stays at one until ∣S∣|S| is of order dd, and larger groups need proportionally more rewritings; for SnS_n the curves nearly coincide.

Figure 13. Relative error ηS(F)\eta_S(F) for Qwen2.5-1.5B fields with one shared SS per size and draw. (a) Mean and maximum over fields, and the exact worst case of Theorem 2, for graphs with n=4n=4 nodes (∣G∣=24|G|=24) and n=5n=5 nodes (∣G∣=120|G|=120). (b) Mean by task and (c) by decoding rule at n=5n=5. The curves are nearly indistinguishable, as Theorem 3 predicts.

Notation

This table collects the notation used in the paper and the place where each symbol is introduced.

SymbolMeaningIntroduced
X\mathcal{X}space of prompts§ 3
C\mathcal{C}, C=∣C∣C = \lvert\mathcal{C}\rvertset of answer classes and its size§ 3
y⋆:X→Cy^{\star}:\mathcal{X}\to\mathcal{C}target function, invariant: y⋆(g⋅x)=y⋆(x)y^{\star}(g\cdot x)=y^{\star}(x)§ 3
GG, ∣G∣\lvert G\rvert, eefinite group of rewriters, its order, and its identity§ 3
g⋅xg\cdot xrewriting (serialization) of prompt xx by g∈Gg\in G§ 3
G⋅xG\cdot xorbit of xx: all rewritings of the same instance§ 3
hhstarting rewriting from which inference is invokedEquation (6)
ρ(g)\rho(g)permutation of answer classes induced by gg (equivariant targets)Section B
XXprompt drawn from the task distribution§ 4.2
pθ,τ(⋅∣x)p_{\theta,\tau}(\cdot\mid x)frozen model: distribution of reasoning traces given prompt xxEquation (1)
τ\taugeneration temperatureEquation (1)
ω∈Ω\omega\in\Omegaa sampled reasoning trace and the trace spaceEquation (1)
Vx(g,ω)∈ZV_x(g,\omega)\in\mathcal{Z}response field: response of trace ω\omega at rewriting g⋅xg\cdot xEquation (1)
ax(g,ω)a_x(g,\omega), rx(g,ω)r_x(g,\omega)answer extracted from a trace and its verifier scoreEquation (4)
D\mathcal{D}, H\mathcal{H}decoding rule and the real Hilbert space of its outputsEquation (1)
FxD(g)F_x^{\mathcal{D}}(g)decoded orbit field: output of D\mathcal{D} at rewriting ggEquation (1)
FxSCF_x^{\mathrm{SC}}, FxlogitF_x^{\mathrm{logit}}, FxβDF_x^{\beta\mathcal{D}}self consistency, expected logits, verifier weighted decoding§ 3
βD\beta_{\mathcal{D}}decoder (verifier) inverse temperatureEquation (4)
qxD=PGFxDq_x^{\mathcal{D}}=P_G F_x^{\mathcal{D}}fully symmetrized responseEquation (5)
F^x,ξ\widehat{F}_{x,\xi}, ξ\xifield of a realized randomized decoder and its seedSection B
nDn_{\mathcal{D}}number of traces per rewriting in finite self consistencySection C
L2(G;H)L^2(G;\mathcal{H})H\mathcal{H}-valued functions on GG with the uniform inner productSection B
S={{s1,…,s∣S∣}}S=\{\{s_1,\ldots,s_{\lvert S\rvert}\}\}multiset of rewritings, drawn i.i.d. from Unif⁡(G)\operatorname{Unif}(G)Equation (6)
ASA_Ssparse rewriting operator (ASf)(h)=1∣S∣∑if(sih)(A_Sf)(h)=\frac{1}{\lvert S\rvert}\sum_i f(s_i h)Equation (6)
PGP_Gfull group average, the orthogonal projection onto constantsEquation (7)
TsT_stranslation operator (Tsf)(h)=f(sh)(T_sf)(h)=f(sh)Equation (12)
∥⋅∥op\lVert\cdot\rVert_{\mathrm{op}}operator norm on L2(G)L^2(G)Equation (14)
δ\deltafailure probability of the random draw of SSTheorem 2
π\pi, U(H)\mathcal{U}(\mathcal{H})unitary representation of GG and the unitary group of H\mathcal{H}Section B
HG\mathcal{H}^G, PπP_\piinvariant vectors of π\pi and the projection onto themSection B
λ\lambdaleft regular representation of GGSection B
G^\widehat{G}, dρd_\rhoirreducible unitary representations and the dimension of ρ∈G^\rho\in\widehat{G}Section B
cG(X)c_G(X)decision of the fully symmetrized model, arg⁡max⁡c(qX)c\arg\max_c(q_X)_c§ 4.2
c^S(h⋅X)\widehat{c}_S(h\cdot X)decision of sparse symmetrization from starting rewriting hh§ 4.2
ΔX\Delta_Xmargin between the two largest coordinates of qXq_X§ 4.2
RGR_G, RSR_Serror of full and of sparse symmetrization, h∼Unif⁡(G)h\sim\operatorname{Unif}(G)§ 4.2
ttmargin threshold in the error decompositionTheorem 4
nnnumber of nodes of a graph; node relabelings form G=SnG=S_n, ∣G∣=n!\lvert G\rvert=n!§ 5
Z2d\mathbb{Z}_2^dgroup of dd binary flips, ∣G∣=2d\lvert G\rvert=2^d (the family of the lower bound)§ 5
ηS(F)\eta_S(F)relative error ∥ASF−PGF∥/∥F−PGF∥\lVert A_SF-P_GF\rVert/\lVert F-P_GF\rVert§ 5
kkbudget of forward passes per question§ 5
mm, rrnumber of rewritings and number of sampled answers per rewriting, k=m⋅rk=m\cdot rTable 3

Table 1 (PDF p. 38).

References

  1. [1]Marah Abdin et al. Phi-4-Mini technical report: Compact yet powerful multimodal language models via mixture-of-LoRAs. arXiv preprint arXiv:2503.01743, 2025. 27
  2. [2]Ahmed M. Adly. Measuring the symmetry–data exchange rate. arXiv preprint arXiv:2606.01090, 2026. 19arxiv.org/abs/2606.01090
  3. [3]Noga Alon and Yuval Roichman. Random Cayley graphs and expanders. Random Structures & Algorithms, 5(2):271–284, 1994. 6, 19DOI
  4. [4]Simran Arora, Avanika Narayan, Mayee F. Chen, Laurel Orr, Neel Guha, Kush Bhatia, Ines Chami, Frederic Sala, and Christopher Ré. Ask me anything: A simple strategy for prompting language models. In International Conference on Learning Representations, 2023. arXiv:2210.02441. 2, 3arxiv.org/abs/2210.02441
  5. [5]Arsenii Ashukha, Alexander Lyzhov, Dmitry Molchanov, and Dmitry Vetrov. Pitfalls of in-domain uncertainty estimation and ensembling in deep learning. In International Conference on Learning Representations, 2020. arXiv:2002.06470. 18arxiv.org/abs/2002.06470
  6. [6]Gregor Bachmann and Vaishnavh Nagarajan. The pitfalls of next-token prediction. In International Conference on Machine Learning, 2024. arXiv:2403.06963. 19arxiv.org/abs/2403.06963
  7. [7]Sourya Basu, Prasanna Sattigeri, Karthikeyan Natesan Ramamurthy, Vijil Chenthamarakshan, Kush R. Varshney, Lav R. Varshney, and Payel Das. Equi-tuning: Group equivariant fine-tuning of pretrained models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 6788–6796, 2023. arXiv:2210.06475. 19arxiv.org/abs/2210.06475
  8. [8]Gregory Benton, Marc Finzi, Pavel Izmailov, and Andrew Gordon Wilson. Learning invariances in neural networks from training data. In Advances in Neural Information Processing Systems, volume 33, 2020. 19
  9. [9]Alberto Bietti, Luca Venturi, and Joan Bruna. On the sample complexity of learning under invariance and geometric stability. In Advances in Neural Information Processing Systems, volume 34, 2021. 19arxiv.org/abs/2106.07148
  10. [10]Leo Breiman. Bagging predictors. Machine Learning, 24(2):123–140, 1996. 18
  11. [11]Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104.13478, 2021. 18arxiv.org/abs/2104.13478
  12. [12]Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V. Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21787, 2024. 1, 3arxiv.org/abs/2407.21787
  13. [13]Liang Chen, Li Shen, Yang Deng, Xiaoyan Zhao, Bin Liang, and Kam-Fai Wong. PEARL: Towards permutation-resilient LLMs. In International Conference on Learning Representations, 2025. arXiv:2502.14628. 3arxiv.org/abs/2502.14628
  14. [14]Lingjiao Chen, Jared Quincy Davis, Boris Hanin, Peter Bailis, Ion Stoica, Matei Zaharia, and James Zou. Are more LLM calls all you need? Towards the scaling properties of compound AI systems. In Advances in Neural Information Processing Systems, volume 37, 2024a.DOI
  15. [15]Shuxiao Chen, Edgar Dobriban, and Jane H. Lee. A group-theoretic framework for data augmentation. Journal of Machine Learning Research, 21(245):1–71, 2020.arxiv.org/abs/1907.10905
  16. [16]Xinyun Chen, Ryan A. Chi, Xuezhi Wang, and Denny Zhou. Premise order matters in reasoning with large language models. In International Conference on Machine Learning, 2024b. arXiv:2402.08939.arxiv.org/abs/2402.08939
  17. [17]Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord. Think you have solved question answering? Try ARC, the AI2 reasoning challenge. arXiv preprint arXiv:1803.05457, 2018.arxiv.org/abs/1803.05457
  18. [18]Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021.arxiv.org/abs/2110.14168
  19. [19]Taco Cohen and Max Welling. Group equivariant convolutional networks. In International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 2990–2999, 2016.arxiv.org/abs/1602.07576
  20. [20]Persi Diaconis. Group Representations in Probability and Statistics, volume 11 of IMS Lecture Notes Monograph Series. Institute of Mathematical Statistics, 1988. ISBN 0-940600-14-5. doi: 10.1214/lnms/1215467407.DOI
  21. [21]Yanai Elazar, Nora Kassner, Shauli Ravfogel, Abhilasha Ravichander, Eduard Hovy, Hinrich Schütze, and Yoav Goldberg. Measuring and improving consistency in pretrained language models. Transactions of the Association for Computational Linguistics, 9:1012–1031, 2021. arXiv:2102.01017.arxiv.org/abs/2102.01017
  22. [22]Bryn Elesedy and Sheheryar Zaidi. Probably strict generalisation benefit for equivariant models. In International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 2959–2969, 2021.arxiv.org/abs/2102.10333
  23. [23]Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. Talk like a graph: Encoding graphs for large language models. In International Conference on Learning Representations, 2024. arXiv:2310.04560.arxiv.org/abs/2310.04560
  24. [24]Arvid Frydenlund. Language models, graph searching, and supervision adulteration: When more supervision is less and how to make more more. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics, 2025. arXiv:2503.10542.arxiv.org/abs/2503.10542
  25. [25]Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, et al. The Llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024.arxiv.org/abs/2407.21783
  26. [26]Nate Gruver, Marc Finzi, Micah Goldblum, and Andrew Gordon Wilson. The Lie derivative for measuring learned equivariance. In International Conference on Learning Representations, 2023.arxiv.org/abs/2210.02984
  27. [27]Vipul Gupta, David Pantoja, Candace Ross, Adina Williams, and Megan Ung. Changing answer order can decrease MMLU accuracy. arXiv preprint arXiv:2406.19470, 2024.arxiv.org/abs/2406.19470
  28. [28]Daniel Herbst, Lea Karbevska, Divyanshu Kumar, Akanksha Ahuja, Fatemeh Gholamzadeh Nasrabadi, and Fabrizio Frasca. Lost in serialization: Invariance and generalization of LLM graph reasoners. arXiv preprint arXiv:2511.10234, 2025.arxiv.org/abs/2511.10234
  29. [29]Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Thomas Hennigan, Eric Noland, Katherine Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karén Simonyan, Erich Elsen, Oriol Vinyals, Jack Rae, and Laurent Sifre. An empirical analysis of compute-optimal large language model training. In Advances in Neural Information Processing Systems, volume 35, 2022.
  30. [30]Zhengbao Jiang, Frank F. Xu, Jun Araki, and Graham Neubig. How can we know what language models know? Transactions of the Association for Computational Linguistics, 8:423–438, 2020. 2, 3arxiv.org/abs/1911.12543
  31. [31]Sékou-Oumar Kaba, Arnab Kumar Mondal, Yan Zhang, Yoshua Bengio, and Siamak Ravanbakhsh. Equivariance with learned canonicalization functions. In International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 15546–15566, 2023. 19arxiv.org/abs/2211.06489
  32. [32]Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.08361, 2020. 3arxiv.org/abs/2001.08361
  33. [33]Jinwoo Kim, Tien Dat Nguyen, Ayhan Suleymanzade, Hyeokjun An, and Seunghoon Hong. Learning probabilistic symmetrization for architecture agnostic equivariance. In Advances in Neural Information Processing Systems, volume 36, 2023. arXiv:2306.02866. 19arxiv.org/abs/2306.02866
  34. [34]Masanari Kimura. Understanding test-time augmentation. In Teddy Mantoro, Minho Lee, Media Anugerah Ayu, Kok Wai Wong, and Achmad Nizar Hidayanto (eds.), Neural Information Processing: 28th International Conference, ICONIP 2021, volume 13108 of Lecture Notes in Computer Science, pp. 558–569, Cham, 2021. Springer. doi: 10.1007/978-3-030-92185-9_46. 18DOI
  35. [35]Nikita Kozodoi, Zainab Afolabi, and Jack Butler. Test-time augmentation for LLMs: When input diversity beats output diversity at matched compute. arXiv preprint arXiv:2608.09351, 2026. 2, 3
  36. [36]Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. ImageNet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems, volume 25, 2012. 18
  37. [37]Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with PagedAttention. In Proceedings of the 29th Symposium on Operating Systems Principles, 2023. arXiv:2309.06180. 27arxiv.org/abs/2309.06180
  38. [38]Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in Neural Information Processing Systems, volume 30, 2017. arXiv:1612.01474. 18arxiv.org/abs/1612.01474
  39. [39]Zeph Landau and Alexander Russell. Random Cayley graphs are expanders: a simple proof of the Alon–Roichman theorem. The Electronic Journal of Combinatorics, 11(1):R62, 2004. doi: 10.37236/1815. 19DOI
  40. [40]Richard B. Lehoucq, Danny C. Sorensen, and Chao Yang. ARPACK Users’ Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods. SIAM, 1998. 37DOI
  41. [41]Noam Itzhak Levi. A simple model of inference scaling laws. In International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pp. 33984–33998, 2025. arXiv:2410.16377. 3arxiv.org/abs/2410.16377
  42. [42]Junyou Li, Qin Zhang, Yangbin Yu, Qiang Fu, and Deheng Ye. More agents is all you need. Transactions on Machine Learning Research, 2024. arXiv:2402.05120. 3arxiv.org/abs/2402.05120
  43. [43]Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let’s verify step by step. In International Conference on Learning Representations, 2024. arXiv:2305.20050. 1, 3arxiv.org/abs/2305.20050
  44. [44]Ji Lin, Jiaming Tang, Haotian Tang, Shang Yang, Wei-Ming Chen, Wei-Chen Wang, Guangxuan Xiao, Xingyu Dang, Chuang Gan, and Song Han. AWQ: Activation-aware weight quantization for on-device LLM compression and acceleration. In Proceedings of Machine Learning and Systems (MLSys), volume 6, 2024. arXiv:2306.00978. 27arxiv.org/abs/2306.00978
  45. [45]Nelson F. Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. Lost in the middle: How language models use long contexts. Transactions of the Association for Computational Linguistics, 12:157–173, 2024. arXiv:2307.03172. 3arxiv.org/abs/2307.03172
  46. [46]Yexiang Liu, Zekun Li, Zhi Fang, Nan Xu, Ran He, and Tieniu Tan. Rethinking the role of prompting strategies in LLM test-time scaling: A perspective of probability theory. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 27962–27994, 2025. arXiv:2505.10981. 3DOI
  47. [47]Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp. Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 8086–8098, 2022. arXiv:2104.08786. 1, 3, 9arxiv.org/abs/2104.08786
  48. [48]Clare Lyle, Mark van der Wilk, Marta Kwiatkowska, Yarin Gal, and Benjamin Bloem-Reddy. On the benefits of invariance in neural networks. arXiv preprint arXiv:2005.00178, 2020. 19arxiv.org/abs/2005.00178
  49. [49]Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2019. 18arxiv.org/abs/1812.09902
  50. [50]Reid McIlroy-Young, Katrina Brown, Conlan Olson, Linjun Zhang, and Cynthia Dwork. Order-independence without fine tuning. In Advances in Neural Information Processing Systems, 2024. arXiv:2406.06581. 3
  51. [51]Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Learning with invariances in random features and kernel models. In Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pp. 3351–3418, 2021. 19
  52. [52]Antonio Valerio Miceli Barone, Fazl Barez, Shay B. Cohen, and Ioannis Konstas. The larger they are, the harder they fail: Language models do not recognize identifier swaps in Python. In Findings of the Association for Computational Linguistics: ACL 2023, pp. 272–292, 2023. arXiv:2305.15507. 1, 3
  53. [53]Iman Mirzadeh, Keivan Alizadeh, Hooman Shahrokhi, Oncel Tuzel, Samy Bengio, and Mehrdad Farajtabar. GSM-symbolic: Understanding the limitations of mathematical reasoning in large language models. In International Conference on Learning Representations, 2025. arXiv:2410.05229. 3arxiv.org/abs/2410.05229
  54. [54]Moran Mizrahi, Guy Kaplan, Dan Malkin, Rotem Dror, Dafna Shahaf, and Gabriel Stanovsky. State of what art? A call for multi-prompt LLM evaluation. Transactions of the Association for Computational Linguistics, 12:933–949, 2024. arXiv:2401.00595. 1, 3arxiv.org/abs/2401.00595
  55. [55]Arnab Kumar Mondal, Siba Smarak Panigrahi, Sékou-Oumar Kaba, Sai Rajeswar, and Siamak Ravanbakhsh. Equivariant adaptation of large pretrained models. In Advances in Neural Information Processing Systems, volume 36, 2023. arXiv:2310.01647. 19arxiv.org/abs/2310.01647
  56. [56]Niklas Muenninghoff, Zitong Yang, Weijia Shi, Xiang Lisa Li, Li Fei-Fei, Hannanah Hajishirzi, Luke Zettlemoyer, Percy Liang, Emmanuel Candès, and Tatsunori Hashimoto. s1: Simple test-time scaling. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pp. 20275–20321, 2025. 3
  57. [57]Ryan L. Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Janossy pooling: Learning deep permutation-invariant functions for variable-size inputs. In International Conference on Learning Representations, 2019. 19arxiv.org/abs/1811.01900
  58. [58]Vaishnavh Nagarajan, Chen Henry Wu, Charles Ding, and Aditi Raghunathan. Roll the dice & look before you leap: Going beyond the creative limits of next-token prediction. In International Conference on Machine Learning, 2025. arXiv:2504.15266. 19arxiv.org/abs/2504.15266
  59. [59]Shahriar Noroozizadeh, Vaishnavh Nagarajan, Elan Rosenfeld, and Sanjiv Kumar. Deep sequence models tend to memorize geometrically; it is unclear why. In International Conference on Machine Learning, 2026. arXiv:2510.26745. 19arxiv.org/abs/2510.26745
  60. [60]Mircea Petrache and Shubhendu Trivedi. Approximation-generalization trade-offs under (approximate) group equivariance. In Advances in Neural Information Processing Systems, volume 36, 2023. arXiv:2305.17592. 19arxiv.org/abs/2305.17592
  61. [61]Pouya Pezeshkpour and Estevam Hruschka. Large language models sensitivity to the order of options in multiple-choice questions. In Findings of the Association for Computational Linguistics: NAACL 2024, pp. 2006–2017, 2024. arXiv:2308.11483. 3
  62. [62]Omri Puny, Matan Atzmon, Heli Ben-Hamu, Ishan Misra, Aditya Grover, Edward J. Smith, and Yaron Lipman. Frame averaging for invariant and equivariant network design. In International Conference on Learning Representations, 2022. 19arxiv.org/abs/2110.03336
  63. [63]Qwen Team, An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, et al. Qwen2.5 technical report. arXiv preprint arXiv:2412.15115, 2024. 7, 27
  64. [64]Abulhair Saparov, Srushti Pawar, Shreyas Pimpalgaonkar, Nitish Joshi, Richard Yuanzhe Pang, Vishakh Padmakumar, Seyed Mehran Kazemi, Najoung Kim, and He He. Transformers struggle to learn to search. In International Conference on Learning Representations, 2025. arXiv:2412.04703. 19arxiv.org/abs/2412.04703
  65. [65]Rylan Schaeffer, Joshua Kazdan, John Hughes, Jordan Juravsky, Sara Price, Aengus Lynch, Erik Jones, Robert Kirk, Azalia Mirhoseini, and Sanmi Koyejo. How do large language monkeys get their power (laws)? In International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pp. 53132–53176, 2025. arXiv:2502.17578. 3arxiv.org/abs/2502.17578
  66. [66]Timo Schick and Hinrich Schütze. Exploiting cloze-questions for few-shot text classification and natural language inference. In Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, pp. 255–269, 2021. arXiv:2001.07676. 3arxiv.org/abs/2001.07676
  67. [67]Melanie Sclar, Yejin Choi, Yulia Tsvetkov, and Alane Suhr. Quantifying language models’ sensitivity to spurious features in prompt design or: How I learned to start worrying about prompt formatting. In International Conference on Learning Representations, 2024. arXiv:2310.11324. 1, 3arxiv.org/abs/2310.11324
  68. [68]Divya Shanmugam, Davis Blalock, Guha Balakrishnan, and John Guttag. Better aggregation in test-time augmentation. In IEEE/CVF International Conference on Computer Vision, 2021. arXiv:2011.11156. 18arxiv.org/abs/2011.11156
  69. [69]Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations, 2015. arXiv:1409.1556. 18DOI
  70. [70]Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling LLM test-time compute optimally can be more effective than scaling parameters for reasoning. In International Conference on Learning Representations, 2025. arXiv:2408.03314. 1, 3arxiv.org/abs/2408.03314
  71. [71]Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pp. 1631–1642, 2013. 28DOI
  72. [72]Benedikt Stroebl, Sayash Kapoor, and Arvind Narayanan. The limits of inference scaling through resampling. In International Conference on Learning Representations, 2026. arXiv:2411.17501. 3arxiv.org/abs/2411.17501
  73. [73]Behrooz Tahmasebi and Stefanie Jegelka. The exact sample complexity gain from invariances for kernel regression. In Advances in Neural Information Processing Systems, volume 36, 2023. 19arxiv.org/abs/2303.14269
  74. [74]Behrooz Tahmasebi and Stefanie Jegelka. Sample complexity bounds for estimating probability divergences under invariances. In International Conference on Machine Learning, 2024. arXiv:2311.02868. 19arxiv.org/abs/2311.02868
  75. [75]Behrooz Tahmasebi and Stefanie Jegelka. Generalization bounds for canonicalization: A comparative study with group averaging. In International Conference on Learning Representations, 2025.
  76. [76]Behrooz Tahmasebi and Melanie Weber. Achieving approximate symmetry is exponentially easier than exact symmetry. In International Conference on Learning Representations, 2026a. arXiv:2512.11855.arxiv.org/abs/2512.11855
  77. [77]Behrooz Tahmasebi and Melanie Weber. Sparse data augmentation for optimization with provable guarantees. In IEEE Conference on Decision and Control, 2026b. arXiv:2609.08133.arxiv.org/abs/2609.08133
  78. [78]Behrooz Tahmasebi, Melanie Weber, and Stefanie Jegelka. Data augmentation: A Fourier analysis perspective. In Conference on Learning Theory, volume 336 of Proceedings of Machine Learning Research, pp. 6114–6155, 2026. arXiv:2606.24418.arxiv.org/abs/2606.24418
  79. [79]Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12(4):389–434, 2012.
  80. [80]Joel A. Tropp. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1–2):1–230, 2015. arXiv:1501.01571.arxiv.org/abs/1501.01571
  81. [81]Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, et al. SciPy 1.0: Fundamental algorithms for scientific computing in Python. Nature Methods, 17:261–272, 2020.
  82. [82]Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. Can language models solve graph problems in natural language? In Advances in Neural Information Processing Systems, 2023a. arXiv:2305.10037.arxiv.org/abs/2305.10037
  83. [83]Shiqi Wang, Zheng Li, Haifeng Qian, Chenghao Yang, Zijian Wang, Mingyue Shang, Varun Kumar, Samson Tan, Baishakhi Ray, Parminder Bhatia, Ramesh Nallapati, Murali Krishna Ramanathan, Dan Roth, and Bing Xiang. ReCode: Robustness evaluation of code generation models. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 13818–13843, 2023b. arXiv:2212.10264.arxiv.org/abs/2212.10264
  84. [84]Xinyi Wang, Shawn Tan, Shenbo Xu, Mingyu Jin, William Wang, Rameswar Panda, and Yikang Shen. Finding the minimal parameter budget for implicit reasoning: A data complexity driven scaling law for language models. In International Conference on Machine Learning, 2026. arXiv:2504.03635.arxiv.org/abs/2504.03635
  85. [85]Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V. Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In International Conference on Learning Representations, 2023c. arXiv:2203.11171.arxiv.org/abs/2203.11171
  86. [86]Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems, 2022. arXiv:2201.11903.arxiv.org/abs/2201.11903
  87. [87]Sean Welleck, Amanda Bertsch, Matthew Finlayson, Hailey Schoelkopf, Alex Xie, Graham Neubig, Ilia Kulikov, and Zaid Harchaoui. From decoding to meta-generation: Inference-time algorithms for large language models. Transactions on Machine Learning Research, 2024. arXiv:2404.16838.
  88. [88]Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. Inference scaling laws: An empirical analysis of compute-optimal inference for LLM problem-solving. In International Conference on Learning Representations, 2025. arXiv:2408.00724.arxiv.org/abs/2408.00724
  89. [89]Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Advances in Neural Information Processing Systems, 2023. arXiv:2305.10601.arxiv.org/abs/2305.10601
  90. [90]Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexander J. Smola. Deep sets. In Advances in Neural Information Processing Systems, volume 30, 2017.
  91. [91]Tony Z. Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh. Calibrate before use: Improving few-shot performance of language models. In International Conference on Machine Learning, 2021. arXiv:2102.09690. 3arxiv.org/abs/2102.09690
  92. [92]Chujie Zheng, Hao Zhou, Fandong Meng, Jie Zhou, and Minlie Huang. Large language models are not robust multiple choice selectors. In International Conference on Learning Representations, 2024. arXiv:2309.03882. 1, 2, 3arxiv.org/abs/2309.03882
  93. [93]Yongshuo Zong, Tingyang Yu, Ruchika Chavhan, Bingchen Zhao, and Timothy Hospedales. Fool your (vision and) language model with embarrassingly simple permutations. In International Conference on Machine Learning, 2024. arXiv:2310.01651. 3arxiv.org/abs/2310.01651

Paper details

vlnc:W_u2jsdfye
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-5.6 Sol (bare), Claude Fable 5.1 (bare)

View statement
Looking for related papers…
Contents