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 of rewritings. We prove that no amount of sampling and repeated decoding from a single representation can replace rewriting, while only random rewritings suffice to recover the information provided by all rewritings. The same set of 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).

Figure 1. Rewriting by explores the orbit of equivalent representations, while the frozen model samples reasoning traces at each representation. Full orbit averaging uses rewrites; test-time symmetrization uses only 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 relabelings. We prove that a random set of rewritings whose size grows with 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: 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 denote the space of prompts and let denote the set of answer classes, with . The target function assigns each prompt its correct answer. Let a finite group act on .1 For a fixed semantic instance , its orbit contains all rewritings generated by the group action. A frozen model queried on defines a conditional distribution over reasoning traces. We write
where is the token generation temperature, is a sampled trace, and is its response representation in a measurable space . It may contain an answer, logits, a verifier score, or the entire trace. Without loss of generality, we assume that the task is invariant, . If 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 to be invariant. Its variation across is precisely what test time symmetrization aims to remove.
We use rewriting and serialization for the same representations, with a small distinction in emphasis: denotes the rewriting operation, while is the resulting serialization of the prompt. The response field has two distinct coordinates. The group element selects a representation of the prompt, while selects a decoder outcome from . We call the conditional probability space

Figure 2. Decoding each rewriting produces the orbit field . Full group averaging gives the invariant target , while sparse averaging uses only the rewritings in to approximate it.
the decoding fiber at . 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 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 maps the conditional response distribution at one rewriting to an element of a real Hilbert space . 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
For class prediction, one usually takes . Three examples are
Here is the answer extracted from a trace and 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), recovers self consistency and larger gives more weight to highly verified traces. This decoder inverse temperature is distinct from the generation temperature inside . 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
It is invariant to the starting rewriting, but it need not be constant across answer classes. For , 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 denote the identity rewriting, so that . Self consistency on the original prompt estimates , whereas full test time symmetrization returns . Repeated decoding at provides information only about the original representation. Querying 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 forward passes. To reduce this cost, let be a multiset of group elements and define the sparse rewriting operator
The argument indexes the starting rewriting from which the same inference procedure is invoked. The full group averaging operator is
which is constant over and is the orthogonal projection onto the subspace of functions that are constant on , 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 changes. It does not require the scores of the answer classes to be equal. Indeed, if , then
is independent of but can still vary with . Consequently, the invariant score vector can select a unique answer through . 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 .
Our goal is to derive a scaling law for the number of forward passes spent exploring . The sampled multiset 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 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 contain at least two elements and let . Consider any possibly randomized inference algorithm that is allowed to draw an arbitrary number of independent traces
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 for . There exist two bounded response fields and , sharing the same decoder distribution at , such that
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:
where . Consequently, if the two worlds are equally likely, every such algorithm has error at least , 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 independently and uniformly from . With probability at least , the same set satisfies, for every real Hilbert space and every ,
This guarantee is simultaneous over all such fields, not one field fixed in advance. Moreover, the dependence is optimal in general: for some finite groups, fewer than rewritings cannot achieve any uniform error below one.
Thus, rewritings give relative error at most . The event depends only on , 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,
The same statement holds for every realized randomized decoder.
There is no dependence on , on the size of the trace space, or on a decoder covering number. A single draw of therefore works for self consistency, expected logits, every verifier temperature in Equation (4), and any other decoding rule selected after is drawn. The guarantee is also pathwise: a finite randomized decoder produces a function on , 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 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 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 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 be drawn from the task distribution and take . Fix any decoding rule and abbreviate and . Let
using a fixed tie breaking rule. Write for the gap between the largest and second largest coordinates of , with at a tie, and define
where independently of .
Corollary 4 (Prediction error decomposition). On the event in Theorem 2, for every ,
The three terms play different roles. The first, , is the error of the fully symmetrized model, which uses all 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 , where a small approximation error can change the decision. The third is the finite rewriting error, which decays as with no explicit dependence on the number of classes ; the threshold trades it against the second term. The bound thus separates three requirements. A large 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 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 (Theorems 2 and 3). The relative error of the sparse average should decay as for every decoding rule and model, with a constant that grows at most like . 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 passes. Self consistency spends all passes on the original prompt and takes a majority vote. Symmetrization spends them on random rewritings with traces each and votes over all traces, so is self consistency and 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 nodes serialized as edge lists (Herbst et al., [28]; Fatemi et al., [23]). The group 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 . 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 , 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 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 , 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 when all traces are sampled at the original prompt and voted (blue), or one trace is sampled at each of 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.
| Model | Task | Greedy | SC | Sym. | Sym. − SC | flip |
| Qwen2.5-7B, | edge count | 0.42 | 0.81 | 0.92 | +10.8 [+3.8, +18.4] | 0.94 |
| edge existence | 0.88 | 0.96 | 1.00 | +3.9 [+0.9, +8.0] | 0.75 | |
| node degree | 0.44 | 0.40 | 0.38 | −2.2 [−8.0, +3.4] | 0.90 | |
| Llama-3.1-8B | edge count | 0.28 | 0.60 | 0.70 | +10.0 [+2.3, +18.3] | 1.00 |
| edge existence | 0.72 | 0.81 | 0.86 | +5.5 [−0.7, +12.3] | 0.57 | |
| node degree | 0.68 | 0.88 | 0.90 | +1.9 [−4.3, +8.4] | 0.87 | |
| Phi-4-mini | edge count | 0.71 | 0.89 | 0.99 | +9.7 [+5.5, +14.0] | 0.79 |
| edge existence | 0.89 | 0.97 | 1.00 | +2.4 [+0.6, +4.5] | 0.67 | |
| node degree | 0.68 | 0.75 | 0.82 | +6.9 [+2.2, +11.9] | 0.88 | |
| Qwen2.5-14B-AWQ | edge count | 0.63 | 0.71 | 0.69 | −1.9 [−7.5, +3.8] | 0.52 |
| edge existence | 0.98 | 0.99 | 1.00 | +0.7 [+0.0, +2.0] | 0.17 | |
| node degree | 0.83 | 0.85 | 0.94 | +9.0 [+2.1, +17.1] | 0.73 |
Table 1. Accuracy at forward passes on graphs with nodes ( 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 . Figure 4 repeats the comparison on a deduction task. Its rewritings form , the hypercube on which the factor of Theorem 2 is attained, or their product. With 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 , 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]) (, 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 people?” given the adjacent comparisons, rewritten by permuting the premises (), by flipping statements between “taller than” and “shorter than” (), or both. Qwen2.5-7B, 100 instances per , 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 exactly for every decoding rule. Figure 5 shows the relative error of for from 8 to 32, where grows from about 25 to more than 300 nats counting both factors of . The rescaled error 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 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 to 94% at , 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 of the sparse average against for Qwen2.5-7B on graphs with nodes, one shared , four decoding rules applied to the same next-token fields, median over seven tasks. is estimated from 64 independent rewritings and the estimation noise is subtracted (Section H.8). The dashed line is .
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 , 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 , 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 and 67% at . Over the surviving rewordings, symmetrization gains +9.8 points ([+3.8, +15.9]) on edge counting at , but its orbit average stays below that of the exact group at (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 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 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 , 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 group elements while approximate invariance needs only 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 is a finite set equipped with an associative product , an identity element , and an inverse for every . Thus, and .
Definition 6 (Group action and orbit). A left action of on a set is a map satisfying
for all and . The orbit of is
Elements of the same orbit are the rewritings that the task regards as semantically equivalent.
Definition 7 (Invariant and equivariant targets). Let be the target function. It is invariant if
for every and . More generally, suppose that each induces a permutation of the answer classes, with . The target is equivariant if
In the equivariant case, applying 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 with a sigma algebra , and let be the measurable space of reasoning traces. A frozen model specifies, for every prompt , a probability measure
on . Equivalently, is a conditional probability kernel from prompts to reasoning traces, where may specify a generation temperature. Querying the model on means drawing
We assume throughout that the maps below are measurable and square integrable whenever an norm is used.
Definition 8 (Response field and decoding fiber). For a fixed semantic instance , a response field is a measurable function
The value is the response representation obtained from trace at rewriting . It may contain an answer, logits, a verifier score, or the trace itself. The pair
is the decoding fiber at .
The joint rewriting and decoding experiment is
When is vector valued and integrable, its joint expectation is
Definition 9 (Distribution level decoding rule). Let be a real Hilbert space. A distribution level decoding rule is any measurable map from the conditional response distribution at a rewriting to an element of . Its decoded orbit field is
No linearity or finite dimensionality is assumed. A randomized finite decoder with seed similarly induces a realized field .
Functions on the group and invariant projection
For a real Hilbert space , equip with the uniform inner product
Lemma 10 (Full group averaging). For , define
Then is constant in , and is the orthogonal projection onto the subspace of functions that are constant on .
Proof. For fixed , the map is a bijection of . Hence
which does not depend on . Thus, the image of consists of constant functions, and for every constant function . Moreover, has mean zero and is therefore orthogonal to every constant function. This proves the claim.
Translation operators and matrix concentration
For a scalar function and , define the translation operator
Because is a permutation of , is unitary under the uniform measure. In this notation,
The operator norm used in Theorem 17 is
Thus, an operator norm bound is one event that controls the approximation error for every function simultaneously.
We use the following standard matrix Bernstein inequality [79]. It is stated for operators so that it applies directly to translations on .
Lemma 11 (Matrix Bernstein inequality). Let be independent, mean zero linear operators on a dimensional Hilbert space. Suppose that almost surely, and define
Then, for every ,
The nonsymmetric form above follows from the self-adjoint matrix Bernstein inequality by applying it to the self-adjoint dilation of each .
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 on a Hilbert space is a map satisfying
Its invariant subspace is
A nonzero representation is irreducible if its only closed invariant subspaces are and the whole space.
The left regular representation acts on by
Our translation equals . This inverse changes neither the relevant operator norm nor the distribution of a uniform group sample.
Let denote a complete set of inequivalent irreducible unitary representations, and let be the dimension of . The finite group Fourier decomposition gives
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 is naturally the Hilbert tensor product . A scalar operator on acts on it as .
Lemma 13 (Hilbert valued tensorization). For every bounded operator and every real Hilbert space
Consequently, if , then
Proof. Choose an orthonormal basis for the closed span of the finite set . Writing and using Parseval’s identity gives
This proves the upper bound, and testing on for a unit vector proves equality. The final claim follows from .
Lemma 14 (Group averaging is an invariant projection). For a unitary representation , the operator
is the orthogonal projection onto .
Proof. For any , a change of variables gives
Hence the image of lies in . Conversely, for every . Moreover,
and the same change of variables gives . It is therefore the orthogonal projection onto .
Lemma 15 (The regular representation controls every representation). Let be a unitary representation of a finite group, and let
For every multiset ,
Moreover, is the orthogonal projection onto the vectors fixed by every .
Proof. Write and define
Decompose into irreducibles. On an isotypic component associated with , the operator acts as
so is the supremum of the norms of these irreducible blocks. By Equation (15), every such block occurs in the regular representation.
Our convention uses . The corresponding regular block contains
Taking an adjoint does not change the operator norm. Therefore, each irreducible block of has norm at most , 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 with a unique maximizer , define its margin
We use any fixed rule to break ties in approximate score vectors.
Lemma 16 (A changed decision requires score error). Let , suppose that has unique maximizer , and let be its margin. If , then
Proof. Let be the class selected by . Since ,
Squaring both sides proves the claim.
On Joint Rewriting and Decoding Sampling
A natural alternative is to sample pairs
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
for some Hilbert valued response . Then the fully symmetrized response satisfies
Consequently, independent joint samples give an unbiased Monte Carlo estimator of . 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
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:
For example, the verifier weighted decoder in Equation (4) averages the per rewriting ratios
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 for one response field. Our goal is stronger: draw once so that the induced group operator approximates 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 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 . 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 and the desired field 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 is an average of unitary translation operators, . On the event in Theorem 17,
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 , not uniform approximation over the trace space .
For example, consider self consistency with independent traces at each rewriting. If is the class probability vector and is its empirical frequency vector, then
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 , and let be their standard basis vectors. Use the same decoder distribution in both worlds and define response fields that do not depend on :
Both response fields take values in . At the original prompt,
for every . Since the decoder distribution at is also the same, every trace and score observed by an algorithm that queries only 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 , so decoder averaging leaves them unchanged. Therefore,
The unique invariant decision is in world , and these decisions are different.
Let be the common output distribution of the algorithm in the two worlds. Under a uniform prior on the worlds, its success probability is
because . Hence its error probability is at least , 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 .
Theorem 17 (Universal sparse group averaging). Let contain independent samples from and let . With probability at least ,
On the same event, for every real Hilbert space and every ,
Moreover, for every unitary representation , if denotes the orthogonal projection onto its invariant vectors, then
Finally, the logarithmic dependence is necessary in general: for , every multiset with fewer than elements has operator error equal to one.
:::`
Proof of Theorem 17. Write and . The case is immediate, so assume . For each sampled element , let
By Equation (13), the operators are independent and have mean zero. Translation preserves constant functions and preserves the uniform mean, so
Since is unitary and is an orthogonal projection, it follows that
Consequently, the variance parameter in Lemma 11 satisfies
Applying Lemma 11 on the dimensional space gives, for every ,
Equivalently, for every ,
Moreover, , since on constant functions the difference vanishes and on their orthogonal complement it is an average of unitary operators. If
the claimed bound is therefore deterministic. Otherwise, set
Since , Equation (23) gives
where the last inequality uses . This proves Equation (20) with the explicit constant .
Set . Since , 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 . Let , so that , and suppose that . The sampled elements span a proper subspace of over . Hence there is a nonzero such that
Define the nonconstant character . It has uniform mean zero, so . On the other hand,
and therefore . Thus,
The reverse inequality was established above, so the error equals one. Since , fewer than 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
Proof of Corollary 3. Fix the operator event in Theorem 17. For any choices of , , , , and , the decoded response belongs to . Applying Equation (21) to this function and using proves Equation (10). The event depends only on , so the conclusion is simultaneous over all of these choices.
For a randomized decoder, condition on any seed and all sampled traces. Its output is then a deterministic field . 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 .
Proof of Corollary 4
Proof of Corollary 4. If , then either or . Hence
Split the second probability according to whether . On , Lemma 16 shows that a changed decision requires
For each with , Markov’s inequality over therefore gives
where the second line uses Equation (21). Taking expectation over and adding 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 ). 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 with 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 with uniform in for , for , and 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 is an action of 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 and between-community probability , and the planted-cycle graphs add a cycle through 3 to random nodes to . 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 people with a hidden total order of heights. The 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 -th tallest (), and whether one named person is taller than another non-adjacent one (balanced yes/no). Rewritings permute the premises (), flip the phrasing of each premise (), 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 balanced training demonstrations, rewritten by permuting the demonstrations ().
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 () 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 the gain is on SBM graphs and 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 , connectivity ).
| Model | Task | Greedy | SC-16 | Sym.-16 | Gain | flip | ||
| Qwen2.5-7B | edge count | 8 | 200 | 0.99 | 0.99 | 1.00 | 0.12 | |
| Qwen2.5-7B | edge count | 12 | 200 | 0.92 | 0.96 | 1.00 | +3.9 | 0.45 |
| Qwen2.5-7B | edge count | 16 | 200 | 0.81 | 0.96 | 0.98 | 0.64 | |
| Qwen2.5-7B | edge count | 20 | 200 | 0.70 | 0.91 | 0.96 | +4.7 | 0.80 |
| Model | Task | Greedy | SC-16 | Sym.-16 | Gain | flip | ||
| edge count | 24 | 100 | 0.42 | 0.82 | 0.92 | +10.7 [+3.8, +18.0] | 0.94 | |
| edge existence | 8 | 200 | 0.94 | 0.96 | 1.00 | +3.5 [+1.2, +6.0] | 0.49 | |
| edge existence | 12 | 200 | 0.92 | 0.98 | 1.00 | +2.2 [+0.5, +4.5] | 0.58 | |
| edge existence | 16 | 200 | 0.92 | 0.97 | 1.00 | +2.7 [+0.8, +4.9] | 0.60 | |
| edge existence | 20 | 200 | 0.85 | 0.98 | 1.00 | +2.1 [+0.3, +4.1] | 0.75 | |
| edge existence | 24 | 100 | 0.88 | 0.96 | 1.00 | +3.9 [+0.8, +8.0] | 0.75 | |
| node degree | 8 | 200 | 0.68 | 0.70 | 0.75 | +5.7 [+0.4, +10.9] | 0.71 | |
| node degree | 12 | 200 | 0.61 | 0.64 | 0.65 | +0.7 [−4.3, +5.9] | 0.74 | |
| node degree | 16 | 200 | 0.59 | 0.57 | 0.56 | −0.3 [−5.9, +5.3] | 0.80 | |
| node degree | 20 | 200 | 0.42 | 0.40 | 0.41 | +0.7 [−4.4, +5.6] | 0.84 | |
| node degree | 24 | 100 | 0.44 | 0.40 | 0.39 | −1.5 [−7.4, +4.1] | 0.90 | |
| components | 8 | 100 | 0.67 | 0.76 | 0.77 | +1.6 [−4.9, +8.0] | 0.90 | |
| components | 12 | 100 | 0.52 | 0.68 | 0.70 | +1.2 [−6.2, +9.1] | 0.97 | |
| components | 16 | 100 | 0.39 | 0.48 | 0.52 | +3.9 [−1.6, +9.1] | 1.00 | |
| components | 20 | 100 | 0.47 | 0.63 | 0.65 | +1.3 [−1.2, +3.3] | 0.99 | |
| components | 24 | 100 | 0.44 | 0.67 | 0.67 | −0.4 [−2.1, +1.0] | 1.00 | |
| connected | 8 | 200 | 0.89 | 0.98 | 0.99 | +0.3 [−1.1, +2.0] | 0.64 | |
| connected | 12 | 200 | 0.84 | 0.91 | 0.92 | +1.0 [−2.3, +4.5] | 0.83 | |
| connected | 16 | 200 | 0.80 | 0.84 | 0.84 | −0.2 [−3.7, +3.9] | 0.83 | |
| connected | 20 | 200 | 0.69 | 0.70 | 0.69 | −0.4 [−3.2, +2.4] | 0.76 | |
| connected | 24 | 100 | 0.61 | 0.64 | 0.65 | +0.8 [−2.8, +4.1] | 0.76 | |
| cycle | 8 | 100 | 0.76 | 0.69 | 0.65 | −3.4 [−6.8, −0.6] | 0.46 | |
| cycle | 12 | 100 | 0.59 | 0.59 | 0.57 | −2.0 [−6.6, +2.6] | 0.47 | |
| cycle | 16 | 100 | 0.59 | 0.55 | 0.54 | −1.0 [−4.5, +1.4] | 0.42 | |
| cycle | 20 | 100 | 0.58 | 0.52 | 0.51 | −0.8 [−3.1, +0.7] | 0.52 | |
| cycle | 24 | 100 | 0.56 | 0.51 | 0.50 | −0.9 [−2.7, +0.1] | 0.50 | |
| triangles | 8 | 100 | 0.22 | 0.25 | 0.24 | −1.5 [−7.9, +4.2] | 0.97 | |
| triangles | 12 | 100 | 0.23 | 0.24 | 0.20 | −4.8 [−11.7, +1.7] | 1.00 | |
| triangles | 16 | 100 | 0.10 | 0.20 | 0.15 | −4.8 [−10.8, +1.4] | 1.00 | |
| triangles | 20 | 100 | 0.11 | 0.11 | 0.10 | −1.0 [−7.0, +4.0] | 1.00 | |
| triangles | 24 | 100 | 0.06 | 0.06 | 0.07 | +1.3 [−3.2, +5.4] | 1.00 | |
| Phi-4-mini | edge count | 8 | 200 | 0.98 | 0.99 | 1.00 | +0.5 [+0.0, +1.5] | 0.27 |
| Phi-4-mini | edge count | 12 | 200 | 0.87 | 0.95 | 0.99 | +4.8 [+1.9, +7.9] | 0.68 |
| Phi-4-mini | edge count | 16 | 200 | 0.71 | 0.89 | 0.99 | +9.7 [+5.5, +14.0] | 0.79 |
| Phi-4-mini | edge existence | 8 | 200 | 0.94 | 0.98 | 1.00 | +1.7 [+0.1, +3.5] | 0.51 |
| Phi-4-mini | edge existence | 12 | 200 | 0.93 | 0.98 | 1.00 | +1.8 [+0.3, +3.8] | 0.58 |
| Phi-4-mini | edge existence | 16 | 200 | 0.89 | 0.97 | 1.00 | +2.4 [+0.6, +4.5] | 0.67 |
| Phi-4-mini | node degree | 8 | 200 | 0.73 | 0.85 | 0.95 | +9.3 [+4.6, +14.1] | 0.72 |
| Phi-4-mini | node degree | 12 | 200 | 0.66 | 0.76 | 0.86 | +9.9 [+4.6, +15.1] | 0.77 |
| Phi-4-mini | node degree | 16 | 200 | 0.68 | 0.75 | 0.82 | +6.9 [+2.2, +11.9] | 0.88 |
| Phi-4-mini | components | 8 | 100 | 0.69 | 0.76 | 0.76 | +0.2 [−5.7, +6.3] | 0.73 |
| Phi-4-mini | components | 12 | 100 | 0.51 | 0.62 | 0.61 | −1.1 [−6.0, +3.2] | 0.87 |
| Phi-4-mini | components | 16 | 60 | 0.43 | 0.44 | 0.44 | −0.0 [−2.8, +2.5] | 0.93 |
| Phi-4-mini | connected | 8 | 100 | 0.81 | 0.76 | 0.79 | +2.8 [−2.6, +8.2] | 0.58 |
| Phi-4-mini | connected | 12 | 100 | 0.62 | 0.74 | 0.75 | +1.0 [−5.5, +7.2] | 0.79 |
| Phi-4-mini | connected | 16 | 60 | 0.55 | 0.64 | 0.62 | −1.7 [−8.2, +4.3] | 0.80 |
| Phi-4-mini | cycle | 8 | 100 | 0.68 | 0.83 | 0.76 | −6.9 [−12.6, −1.5] | 0.88 |
| Phi-4-mini | cycle | 12 | 100 | 0.57 | 0.63 | 0.67 | +4.1 [−0.9, +9.1] | 0.98 |
| Phi-4-mini | cycle | 16 | 60 | 0.62 | 0.63 | 0.62 | −0.6 [−7.8, +6.2] | 0.98 |
| Phi-4-mini | triangles | 8 | 100 | 0.34 | 0.41 | 0.44 | +2.9 [−2.7, +8.9] | 1.00 |
| Phi-4-mini | triangles | 12 | 100 | 0.22 | 0.30 | 0.31 | +0.6 [−5.9, +7.4] | 1.00 |
| Phi-4-mini | triangles | 16 | 60 | 0.10 | 0.23 | 0.21 | −2.1 [−8.2, +3.4] | 1.00 |
| Llama-3.1-8B | edge count | 8 | 100 | 0.74 | 0.91 | 0.96 | +5.7 [+2.0, +10.4] | 0.98 |
| Llama-3.1-8B | edge count | 12 | 100 | 0.36 | 0.81 | 0.79 | −2.0 [−8.3, +4.6] | 0.99 |
| Llama-3.1-8B | edge count | 16 | 60 | 0.28 | 0.61 | 0.70 | +8.9 [+0.9, +16.9] | 1.00 |
| Llama-3.1-8B | edge existence | 8 | 100 | 0.84 | 0.94 | 0.98 | +4.0 [+0.1, +8.6] | 0.45 |
| Llama-3.1-8B | edge existence | 12 | 100 | 0.84 | 0.91 | 0.91 | −0.2 [−5.3, +4.6] | 0.50 |
| Llama-3.1-8B | edge existence | 16 | 60 | 0.72 | 0.81 | 0.86 | +5.3 [−1.0, +12.2] | 0.57 |
| Llama-3.1-8B | node degree | 8 | 100 | 0.79 | 0.89 | 0.97 | +7.8 [+2.8, +13.4] | 0.83 |
| Llama-3.1-8B | node degree | 12 | 100 | 0.74 | 0.85 | 0.90 | +4.8 [−1.1, +11.2] | 0.90 |
| Llama-3.1-8B | node degree | 16 | 60 | 0.68 | 0.88 | 0.90 | +2.0 [−4.1, +8.8] | 0.87 |
| Llama-3.1-8B | components | 8 | 100 | 0.52 | 0.67 | 0.64 | −2.3 [−9.9, +5.1] | 1.00 |
| Model | Task | Greedy | SC-16 | Sym.-16 | Gain | flip | ||
| components | 12 | 100 | 0.37 | 0.51 | 0.51 | +0.3 [−8.7, +9.3] | 1.00 | |
| components | 16 | 60 | 0.28 | 0.41 | 0.38 | −3.3 [−13.5, +6.4] | 1.00 | |
| connected | 8 | 100 | 0.72 | 0.74 | 0.71 | −2.3 [−6.7, +1.7] | 0.77 | |
| connected | 12 | 100 | 0.54 | 0.58 | 0.57 | −0.8 [−4.1, +2.3] | 0.91 | |
| connected | 16 | 60 | 0.50 | 0.53 | 0.52 | −1.3 [−6.3, +2.3] | 0.90 | |
| cycle | 8 | 100 | 0.56 | 0.52 | 0.53 | +0.9 [−1.0, +3.0] | 0.91 | |
| cycle | 12 | 100 | 0.45 | 0.50 | 0.50 | +0.0 [+0.0, +0.1] | 0.92 | |
| cycle | 16 | 60 | 0.43 | 0.50 | 0.50 | +0.0 [+0.0, +0.0] | 0.97 | |
| triangles | 8 | 100 | 0.02 | 0.05 | 0.06 | +0.7 [−2.7, +3.9] | 1.00 | |
| triangles | 12 | 100 | 0.02 | 0.03 | 0.02 | −0.2 [−3.5, +2.4] | 1.00 | |
| triangles | 16 | 60 | 0.02 | 0.01 | 0.01 | −0.1 [−0.9, +0.6] | 1.00 | |
| Qwen2.5-14B-AWQ | edge count | 8 | 100 | 1.00 | 0.99 | 1.00 | +0.5 [+0.0, +1.7] | 0.03 |
| Qwen2.5-14B-AWQ | edge count | 12 | 100 | 0.79 | 0.80 | 0.78 | −1.5 [−4.7, +1.0] | 0.36 |
| Qwen2.5-14B-AWQ | edge count | 16 | 60 | 0.63 | 0.71 | 0.70 | −1.2 [−6.7, +4.2] | 0.52 |
| Qwen2.5-14B-AWQ | edge existence | 8 | 100 | 1.00 | 1.00 | 1.00 | +0.0 [+0.0, +0.0] | 0.04 |
| Qwen2.5-14B-AWQ | edge existence | 12 | 100 | 0.98 | 1.00 | 1.00 | +0.0 [+0.0, +0.0] | 0.14 |
| Qwen2.5-14B-AWQ | edge existence | 16 | 60 | 0.98 | 0.99 | 1.00 | +0.7 [+0.0, +2.2] | 0.17 |
| Qwen2.5-14B-AWQ | node degree | 8 | 100 | 0.90 | 0.90 | 1.00 | +10.1 [+4.3, +16.2] | 0.55 |
| Qwen2.5-14B-AWQ | node degree | 12 | 100 | 0.78 | 0.82 | 0.94 | +12.1 [+5.9, +19.2] | 0.65 |
| Qwen2.5-14B-AWQ | node degree | 16 | 60 | 0.83 | 0.85 | 0.94 | +8.9 [+2.0, +16.5] | 0.73 |
| Qwen2.5-14B-AWQ | components | 8 | 100 | 0.80 | 0.86 | 0.87 | +1.5 [−4.0, +7.0] | 0.58 |
| Qwen2.5-14B-AWQ | components | 12 | 100 | 0.68 | 0.71 | 0.70 | −0.9 [−6.1, +4.0] | 0.87 |
| Qwen2.5-14B-AWQ | components | 16 | 60 | 0.53 | 0.54 | 0.50 | −4.4 [−11.9, +2.2] | 0.90 |
| Qwen2.5-14B-AWQ | connected | 8 | 100 | 0.90 | 0.93 | 0.91 | −2.8 [−7.4, +1.6] | 0.38 |
| Qwen2.5-14B-AWQ | connected | 12 | 100 | 0.72 | 0.82 | 0.80 | −1.7 [−5.7, +1.9] | 0.53 |
| Qwen2.5-14B-AWQ | connected | 16 | 60 | 0.72 | 0.73 | 0.71 | −2.0 [−8.5, +4.1] | 0.58 |
| Qwen2.5-14B-AWQ | cycle | 8 | 100 | 0.70 | 0.70 | 0.66 | −3.5 [−7.0, −0.6] | 0.30 |
| Qwen2.5-14B-AWQ | cycle | 12 | 100 | 0.62 | 0.63 | 0.59 | −3.5 [−7.8, +0.1] | 0.40 |
| Qwen2.5-14B-AWQ | cycle | 16 | 60 | 0.57 | 0.55 | 0.57 | +2.6 [−0.2, +6.6] | 0.32 |
| Qwen2.5-14B-AWQ | triangles | 8 | 100 | 0.28 | 0.31 | 0.36 | +5.5 [−0.2, +11.6] | 0.95 |
| Qwen2.5-14B-AWQ | triangles | 12 | 100 | 0.17 | 0.21 | 0.23 | +2.0 [−5.1, +8.5] | 0.99 |
| Qwen2.5-14B-AWQ | triangles | 16 | 60 | 0.12 | 0.26 | 0.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 instances (bold: interval excludes zero); “flip” is the fraction of instances whose greedy answer changes across the 16 rewritings.
| Model | Task | Greedy | SC-16 | Sym.-16 | Gain | flip | ||
| SBM | edge count | 16 | 100 | 0.70 | 0.92 | 0.97 | +4.8 [+0.2, +10.2] | 0.78 |
| SBM | edge count | 24 | 100 | 0.40 | 0.77 | 0.88 | +10.9 [+3.5, +18.5] | 1.00 |
| SBM | edge existence | 16 | 100 | 0.90 | 0.97 | 1.00 | +2.8 [+0.3, +6.2] | 0.77 |
| SBM | edge existence | 24 | 100 | 0.86 | 0.97 | 0.99 | +2.2 [−0.3, +5.5] | 0.85 |
| SBM | node degree | 16 | 100 | 0.50 | 0.48 | 0.45 | −2.1 [−10.8, +6.2] | 0.91 |
| SBM | node degree | 24 | 100 | 0.20 | 0.19 | 0.15 | −4.6 [−10.7, +0.8] | 0.97 |
| SBM | components | 16 | 100 | 0.57 | 0.74 | 0.79 | +5.0 [+1.7, +8.9] | 0.99 |
| SBM | components | 24 | 100 | 0.52 | 0.79 | 0.78 | −0.1 [−2.9, +2.8] | 1.00 |
| SBM | connected | 16 | 100 | 0.77 | 0.79 | 0.82 | +2.9 [−2.7, +8.9] | 0.79 |
| SBM | connected | 24 | 100 | 0.57 | 0.61 | 0.57 | −3.8 [−8.2, +0.2] | 0.75 |
| SBM | cycle | 16 | 100 | 0.61 | 0.55 | 0.52 | −2.8 [−6.1, −0.2] | 0.48 |
| SBM | cycle | 24 | 100 | 0.56 | 0.50 | 0.50 | +0.0 [+0.0, +0.0] | 0.38 |
| SBM | triangles | 16 | 100 | 0.13 | 0.14 | 0.11 | −2.6 [−7.6, +1.8] | 0.99 |
| SBM | triangles | 24 | 100 | 0.01 | 0.02 | 0.03 | −0.9 [−1.8, +2.9] | 1.00 |
| planted cycle | edge count | 16 | 100 | 0.96 | 0.98 | 1.00 | +2.0 [+0.0, +5.0] | 0.54 |
| planted cycle | edge count | 24 | 100 | 0.50 | 0.89 | 0.95 | +6.8 [+1.0, +13.1] | 0.84 |
| planted cycle | edge existence | 16 | 100 | 0.95 | 0.99 | 1.00 | +0.5 [+0.0, +1.5] | 0.54 |
| planted cycle | edge existence | 24 | 100 | 0.90 | 0.98 | 1.00 | +1.7 [+0.0, +4.3] | 0.61 |
| planted cycle | node degree | 16 | 100 | 0.82 | 0.80 | 0.83 | +3.0 [−3.5, +9.8] | 0.68 |
| planted cycle | node degree | 24 | 100 | 0.56 | 0.56 | 0.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 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).
| Task | () | () | () | () | |
| edge count | 8 | 0.990 | 1.000 | 1.000 | 1.000 |
| 12 | 0.958 | 0.995 | 0.998 | 0.999 | |
| 16 | 0.963 | 0.984 | 0.985 | 0.988 | |
| 20 | 0.910 | 0.948 | 0.959 | 0.961 | |
| 24 | 0.817 | 0.912 | 0.927 | 0.930 | |
| edge existence | 8 | 0.963 | 0.999 | 1.000 | 1.000 |
| 12 | 0.977 | 0.999 | 1.000 | 1.000 | |
| 16 | 0.973 | 1.000 | 1.000 | 1.000 | |
| 20 | 0.977 | 0.991 | 0.993 | 0.995 | |
| 24 | 0.960 | 1.000 | 0.998 | 1.000 | |
| node degree | 8 | 0.695 | 0.733 | 0.750 | 0.760 |
| 12 | 0.636 | 0.637 | 0.636 | 0.654 | |
| 16 | 0.570 | 0.566 | 0.560 | 0.557 | |
| 20 | 0.403 | 0.430 | 0.413 | 0.403 | |
| 24 | 0.398 | 0.373 | 0.367 | 0.385 | |
| components | 8 | 0.765 | 0.768 | 0.762 | 0.785 |
| 12 | 0.683 | 0.683 | 0.673 | 0.707 | |
| 16 | 0.485 | 0.518 | 0.518 | 0.517 | |
| 20 | 0.630 | 0.642 | 0.647 | 0.645 | |
| 24 | 0.672 | 0.672 | 0.668 | 0.673 | |
| connected | 8 | 0.983 | 0.976 | 0.988 | 0.993 |
| 12 | 0.907 | 0.925 | 0.923 | 0.917 | |
| 16 | 0.838 | 0.828 | 0.833 | 0.834 | |
| 20 | 0.696 | 0.698 | 0.689 | 0.699 | |
| 24 | 0.642 | 0.667 | 0.648 | 0.655 | |
| cycle | 8 | 0.683 | 0.660 | 0.655 | 0.655 |
| 12 | 0.592 | 0.563 | 0.577 | 0.567 | |
| 16 | 0.550 | 0.547 | 0.538 | 0.535 | |
| 20 | 0.512 | 0.505 | 0.508 | 0.508 | |
| 24 | 0.510 | 0.502 | 0.502 | 0.500 | |
| triangles | 8 | 0.253 | 0.230 | 0.248 | 0.225 |
| 12 | 0.245 | 0.195 | 0.195 | 0.197 | |
| 16 | 0.198 | 0.145 | 0.162 | 0.150 | |
| 20 | 0.118 | 0.105 | 0.075 | 0.082 | |
| 24 | 0.057 | 0.090 | 0.078 | 0.092 |
Table 3. Allocation of a budget of 16 forward passes between rewritings and 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 points), the 19 sensitive but incompetent ones contain 1 gain and no loss (mean ), and the 19 insensitive ones contain 3 gains and 2 losses (mean ). The losses are cycle detection at for Qwen2.5-7B (), Phi-4-mini (), and Qwen2.5-14B (). 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 of Theorem 4 being larger than the error of a typical representation, and it is unrelated to order sensitivity.
| Model | Task | Greedy | SC-16 | Sym.-16 | Gain | flip | ||
| components | 16 | 100 | 0.21 | 0.23 | 0.27 | +3.7 [−1.3, +8.8] | 1.00 | |
| components | 24 | 100 | 0.16 | 0.31 | 0.30 | −1.2 [−5.0, +1.9] | 1.00 | |
| connected | 16 | 100 | 0.72 | 0.83 | 0.85 | +2.0 [−2.5, +6.7] | 0.90 | |
| connected | 24 | 100 | 0.67 | 0.66 | 0.68 | +2.4 [−2.2, +6.7] | 0.89 | |
| triangles | 16 | 100 | 0.13 | 0.18 | 0.24 | +5.2 [−1.6, +11.7] | 1.00 | |
| triangles | 24 | 100 | 0.07 | 0.11 | 0.12 | +1.0 [−4.7, +5.9] | 1.00 | |
| adjacency lists | edge count | 16 | 100 | 0.15 | 0.13 | 0.09 | −4.2 [−9.4, +0.6] | 0.99 |
| edge existence | 16 | 100 | 0.98 | 1.00 | 1.00 | +0.0 [+0.0, +0.0] | 0.24 | |
| node degree | 16 | 100 | 0.95 | 0.97 | 1.00 | +3.3 [+0.3, +7.2] | 0.45 | |
| connected | 16 | 100 | 0.94 | 0.97 | 0.98 | +1.4 [+0.1, +3.2] | 0.36 | |
| letter labels | edge count | 16 | 100 | 0.95 | 0.98 | 1.00 | +1.6 [−0.0, +4.2] | 0.43 |
| edge existence | 16 | 100 | 0.97 | 1.00 | 1.00 | +0.0 [+0.0, +0.0] | 0.52 | |
| node degree | 16 | 100 | 0.64 | 0.66 | 0.68 | +2.5 [−6.0, +10.7] | 0.78 | |
| connected | 16 | 100 | 0.71 | 0.79 | 0.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 at a fixed budget. On edge counting the flip rate rises from 0.12 at to 0.94 at 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 , although grows from to across the figure. This is what the law of Theorem 2 buys.
Figure 6. Order sensitivity and the gain of symmetrization against the graph size , 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 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 ). On node degree, component counting, connectivity, and cycle detection the oracle is also high (88% to 97% at ) 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 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 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.
| Model | Task | Greedy | SC-16 | Sym.-16 | Gain | flip | ||
| reorder | tallest | 5 | 100 | 0.98 | 1.00 | 1.00 | [] | 0.09 |
| tallest | 8 | 100 | 0.93 | 0.99 | 1.00 | [] | 0.72 | |
| tallest | 11 | 100 | 0.83 | 0.94 | 1.00 | [] | 0.89 | |
| -th tallest | 5 | 100 | 0.90 | 0.99 | 1.00 | [] | 0.70 | |
| -th tallest | 8 | 100 | 0.63 | 0.84 | 0.92 | [] | 0.98 | |
| -th tallest | 11 | 100 | 0.49 | 0.64 | 0.72 | [] | 1.00 | |
| comparison | 5 | 100 | 0.93 | 0.99 | 1.00 | [] | 0.38 | |
| comparison | 8 | 100 | 0.85 | 0.94 | 0.97 | [] | 0.70 | |
| comparison | 11 | 100 | 0.80 | 0.88 | 0.90 | [] | 0.75 | |
| flip | tallest | 5 | 100 | 0.95 | 1.00 | 1.00 | [] | 0.29 |
| tallest | 8 | 100 | 0.74 | 0.95 | 0.99 | [] | 0.90 | |
| tallest | 11 | 100 | 0.61 | 0.77 | 0.86 | [] | 0.99 | |
| -th tallest | 5 | 100 | 0.80 | 0.93 | 0.99 | [] | 0.91 | |
| -th tallest | 8 | 100 | 0.32 | 0.44 | 0.60 | [] | 1.00 | |
| -th tallest | 11 | 100 | 0.18 | 0.28 | 0.30 | [] | 1.00 | |
| comparison | 5 | 100 | 0.98 | 1.00 | 1.00 | [] | 0.29 | |
| Model | Task | Greedy | SC-16 | Sym.-16 | Gain | flip | ||
| comparison | 8 | 100 | 0.72 | 0.80 | 0.88 | +8.3 [+2.1, +15.0] | 0.81 | |
| comparison | 11 | 100 | 0.71 | 0.74 | 0.81 | +6.6 [−0.2, +13.8] | 0.88 | |
| both | tallest | 5 | 100 | 1.00 | 1.00 | 1.00 | +0.0 [+0.0, +0.0] | 0.51 |
| tallest | 8 | 100 | 0.75 | 0.86 | 1.00 | +13.9 [+7.0, +20.9] | 0.98 | |
| tallest | 11 | 100 | 0.51 | 0.79 | 0.99 | +19.5 [+11.9, +27.3] | 1.00 | |
| -th tallest | 5 | 100 | 0.81 | 0.97 | 1.00 | +3.0 [+0.4, +6.5] | 0.92 | |
| -th tallest | 8 | 100 | 0.35 | 0.50 | 0.64 | +14.1 [+5.6, +22.8] | 1.00 | |
| -th tallest | 11 | 100 | 0.21 | 0.33 | 0.32 | −0.9 [−9.1, +6.8] | 1.00 | |
| comparison | 5 | 100 | 0.95 | 0.98 | 1.00 | +1.9 [−0.1, +4.8] | 0.46 | |
| comparison | 8 | 100 | 0.82 | 0.88 | 0.95 | +6.8 [+1.6, +12.1] | 0.88 | |
| comparison | 11 | 100 | 0.70 | 0.75 | 0.83 | +8.5 [+1.6, +15.2] | 0.93 |
Table 5. Deduction from adjacent height comparisons among people, Qwen2.5-7B, budget 16, under premise reordering (), statement flipping (), 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.
| Procedure | Accuracy |
| Greedy, original ordering (1 call) | 0.918 [0.894, 0.940] |
| Vote over 3 traces, original ordering | 0.922 [0.898, 0.944] |
| 4 orderings, aligned, one trace each | 0.934 [0.914, 0.956] |
| 16 orderings, aligned, one trace each | 0.946 [0.926, 0.966] |
| All 24 orderings, aligned, all 72 traces | 0.948 [0.928, 0.966] |
| 16 orderings, not aligned | 0.244 [0.206, 0.282] |
Table 6.
| Model | Task | Greedy | SC-16 | Sym.-16 | Gain | flip | ||
| SST-2 | SST-2 | 4 | 200 | 0.95 | 0.96 | 0.96 | −0.3 [−1.1, +0.3] | 0.07 |
| SST-2 | 8 | 200 | 0.96 | 0.97 | 0.97 | +0.3 [−0.3, +1.2] | 0.08 | |
| SST-2 | 16 | 200 | 0.95 | 0.97 | 0.97 | +0.2 [+0.0, +0.7] | 0.06 |
Table 7.
Table 7: Few-shot sentiment classification (SST-2) with demonstrations, rewritten by permuting the demonstrations (), Qwen2.5-7B, budget 16.
Rewritings from a paraphrasing model
When no group is available, rewritings can be sampled from a kernel given by a paraphrasing model. For rewritings drawn independently from , is an unbiased Monte Carlo estimate of the -average at rate . What is lost relative to Theorem 2 is that the target is meaningful only up to the drift , 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 . The cross-family paraphraser keeps 21 of 24 rewordings at and 14 of 24 at ( 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 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 , 0.79 against 0.94 on connectivity at ), 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.
| Model | Task | Greedy | SC-16 | Sym.-16 | Gain | flip | ||
| cross-family | edge count | 12 | 100 | 0.85 | 0.89 | 0.99 | +9.8 [+3.8, +15.9] | 0.80 |
| edge count | 24 | 78 | 0.46 | 0.68 | 0.74 | +6.5 [−3.0, +16.4] | 0.96 | |
| edge existence | 12 | 100 | 0.96 | 0.96 | 0.98 | +1.2 [−0.4, +3.7] | 0.30 | |
| edge existence | 24 | 72 | 0.94 | 0.97 | 0.98 | +0.8 [−0.6, +2.8] | 0.38 | |
| node degree | 12 | 100 | 0.65 | 0.66 | 0.62 | −4.5 [−9.6, +0.2] | 0.55 | |
| node degree | 24 | 77 | 0.52 | 0.53 | 0.55 | +1.8 [−3.6, +7.5] | 0.60 | |
| components | 12 | 100 | 0.47 | 0.59 | 0.62 | +2.6 [−4.1, +9.7] | 0.93 | |
| components | 24 | 73 | 0.49 | 0.53 | 0.55 | +2.0 [−1.6, +5.7] | 0.75 | |
| connected | 12 | 100 | 0.75 | 0.80 | 0.78 | −2.1 [−6.9, +2.2] | 0.74 | |
| connected | 24 | 86 | 0.62 | 0.55 | 0.57 | +2.1 [−2.9, +7.3] | 0.58 | |
| cycle | 12 | 100 | 0.62 | 0.58 | 0.59 | +0.6 [−1.2, +2.2] | 0.39 | |
| cycle | 24 | 84 | 0.46 | 0.41 | 0.41 | −0.3 [−1.4, +0.5] | 0.44 | |
| triangles | 12 | 100 | 0.20 | 0.27 | 0.21 | −5.9 [−12.7, +0.9] | 0.99 | |
| triangles | 24 | 75 | 0.11 | 0.08 | 0.10 | +1.3 [−3.5, +5.8] | 0.97 | |
| same-model | edge count | 24 | 60 | 0.47 | 0.84 | 0.85 | +0.7 [−6.4, +7.8] | 0.80 |
| edge existence | 24 | 58 | 0.91 | 0.98 | 0.98 | −0.1 [−3.9, +4.4] | 0.28 | |
| node degree | 24 | 61 | 0.64 | 0.60 | 0.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 at . 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 (, 0.8M parameters) on edge counting for graphs with 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 to two decimals (1.00, 0.71, 0.50, 0.35 for ). 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 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
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 exactly for every decoding rule (expected logits, self consistency probabilities at , greedy). For the orbit cannot be enumerated, so we draw one multiset of 32 rewritings and 2 starting rewritings per graph, and estimate from 64 independent rewritings. The estimate adds a known variance 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 lies in for all , decoders, and tasks whose fields are not nearly constant. For Qwen2.5-1.5B on the same it lies in . 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 ), 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 , the operator acts on with uniform measure, and since . Hence
for scalar fields, and the same value holds for Hilbert-valued fields by applying the scalar bound coordinatewise in an orthonormal basis. For we represent functions on as vectors indexed by the lexicographic rank of permutations, implement and its adjoint by index maps , and compute the largest singular value with ARPACK (Lehoucq et al. [40]) through SciPy (Virtanen et al. [81]). For we checked every draw against a dense singular value decomposition; all 70 draws agree to . For every irreducible representation is a character (Diaconis [20]) , so , which we read off the Walsh–Hadamard transform of the empirical distribution of in 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 , for Qwen2.5-1.5B with six decoding rules.
Figure 12. Exact uniform constant of Theorem 2 against for (graphs on nodes, ) and (, ); mean and standard deviation over five draws of . For the constant stays at one until is of order , and larger groups need proportionally more rewritings; for the curves nearly coincide.
Figure 13. Relative error for Qwen2.5-1.5B fields with one shared per size and draw. (a) Mean and maximum over fields, and the exact worst case of Theorem 2, for graphs with nodes () and nodes (). (b) Mean by task and (c) by decoding rule at . 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.
| Symbol | Meaning | Introduced |
| space of prompts | § 3 | |
| , | set of answer classes and its size | § 3 |
| target function, invariant: | § 3 | |
| , , | finite group of rewriters, its order, and its identity | § 3 |
| rewriting (serialization) of prompt by | § 3 | |
| orbit of : all rewritings of the same instance | § 3 | |
| starting rewriting from which inference is invoked | Equation (6) | |
| permutation of answer classes induced by (equivariant targets) | Section B | |
| prompt drawn from the task distribution | § 4.2 | |
| frozen model: distribution of reasoning traces given prompt | Equation (1) | |
| generation temperature | Equation (1) | |
| a sampled reasoning trace and the trace space | Equation (1) | |
| response field: response of trace at rewriting | Equation (1) | |
| , | answer extracted from a trace and its verifier score | Equation (4) |
| , | decoding rule and the real Hilbert space of its outputs | Equation (1) |
| decoded orbit field: output of at rewriting | Equation (1) | |
| , , | self consistency, expected logits, verifier weighted decoding | § 3 |
| decoder (verifier) inverse temperature | Equation (4) | |
| fully symmetrized response | Equation (5) | |
| , | field of a realized randomized decoder and its seed | Section B |
| number of traces per rewriting in finite self consistency | Section C | |
| -valued functions on with the uniform inner product | Section B | |
| multiset of rewritings, drawn i.i.d. from | Equation (6) | |
| sparse rewriting operator | Equation (6) | |
| full group average, the orthogonal projection onto constants | Equation (7) | |
| translation operator | Equation (12) | |
| operator norm on | Equation (14) | |
| failure probability of the random draw of | Theorem 2 | |
| , | unitary representation of and the unitary group of | Section B |
| , | invariant vectors of and the projection onto them | Section B |
| left regular representation of | Section B | |
| , | irreducible unitary representations and the dimension of | Section B |
| decision of the fully symmetrized model, | § 4.2 | |
| decision of sparse symmetrization from starting rewriting | § 4.2 | |
| margin between the two largest coordinates of | § 4.2 | |
| , | error of full and of sparse symmetrization, | § 4.2 |
| margin threshold in the error decomposition | Theorem 4 | |
| number of nodes of a graph; node relabelings form , | § 5 | |
| group of binary flips, (the family of the lower bound) | § 5 | |
| relative error | § 5 | |
| budget of forward passes per question | § 5 | |
| , | number of rewritings and number of sampled answers per rewriting, | Table 3 |
Table 1 (PDF p. 38).
References
- [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]Ahmed M. Adly. Measuring the symmetry–data exchange rate. arXiv preprint arXiv:2606.01090, 2026. 19arxiv.org/abs/2606.01090
- [3]Noga Alon and Yuval Roichman. Random Cayley graphs and expanders. Random Structures & Algorithms, 5(2):271–284, 1994. 6, 19DOI
- [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]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]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]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]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]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]Leo Breiman. Bagging predictors. Machine Learning, 24(2):123–140, 1996. 18
- [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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]Behrooz Tahmasebi and Stefanie Jegelka. Generalization bounds for canonicalization: A comparative study with group averaging. In International Conference on Learning Representations, 2025.
- [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]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]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]Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12(4):389–434, 2012.
- [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]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]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]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]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]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]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]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]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]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]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]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]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]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










