acceptodds
Under review as a conference paper at ICLR 2027

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. Finally, exact computations confirm the rate and its logarithmic dependence on , and graph-reasoning experiments with a frozen open-weight model (Qwen2.5-1.5B) show that a single set of rewritings attains it across six tasks and six decoding rules. 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.

Primary area:
foundation or frontier models, including LLMs
Keywords:
test-time compute, scaling laws, symmetry, invariance, large language models, model-agnostic learning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_21fbOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

This work investigates test-time compute allocation for graph tasks. Such tasks are intresting because each graph has |G|=n! possible relablings/reorderings and LLMs are known to be sensitive to order permutations. Prior work often considers extending test-time compute using multiple samples from a static prompt. This work shows that 1) this strategy can not solve the order-sensitivity issue and 2) that only log(|G|) samples are needed to approximate the probability of considering the full n! set of possible permutations.

Using a single frozen LLM, they consider 6 different graph tasks using synthetic ER graphs with random node IDs. Each task is actually a single response output, not a CoT or reasoning trajectory. They consider two experiments. First, they show that the log average tracks the full average, thus confirming the theory. Second, they show that sampling a log number of samples improves the accuracy of two tasks with statistical significance, with the others being better or worse without significance compared to greedy decoding.

Critical strengths
  1. The main theoretical result is really nice. It says that you only need to consider a log number of graph permutation samples to approximate the full averaged probability. This only depends on the graph size, and not the output space. This result is sound and I expect that it will be useful to other researchers in this domain.

  2. The motivation for this work is clear. Language models on graphs have a permutation sensitivity issue. Prior work generally considers using a test-time budget to sample multiple outputs from a static prompt. However, the authors show that 1) multiple output samples on a static embedding can not overcome this problem, and 2) sampling input permutations can.

  3. The paper is clearly written and easy to follow.

  4. Despite my score, I really liked this paper. I just think it can be stronger.

Critical weaknesses
  1. The empirical evaluation settings and results are of lower quality than the theoretical results (see questions).

  2. There are two experiments. The first is that the sparse average approached the full average. This is great and confirms the theory. However, then we still need to determine if the theoretical results actually matter in practice, and this is where things get complicated. The issue is that the theoretical results do not say that using more permutation samples leads to better task performance directly (or really that approximating the full average doesn't say the full average is a better predictor anyways), yet this is ultimately what we care about, and the intresting thing from the theory is just how few permutation samples are actually needed. So it would be really nice if the outcome of this paper was 'this is a lightweight intervention that leads to better predictive performance.' However, because the theory does not speak to task performance directly, showing that this intervention leads to better performance is difficult to establish, and the authors don't really show this. On the one hand, this is not needed to confirm the theory is correct, which Experiment 1 does. However, it is necessary to establish why we should actually care. Basically, without compelling results from Experiment 2, the paper boils down to just being an intresting fact rather than a method I expect to be used.

Two non-issues:

A) A weakness that I believe other reviewers will bring up, which I do not find to be an issue, is the use of synthetic graphs with arbitrary labels. This entire theoretical result hinges on the fact that graph can be relabeled, however, in real-world settings, nodes and node IDs can carry semantics. That being said, while they do cite prior work, I feel like the authors could better establish that synthetic graphs + random node IDs is a common setting for evaluating theoretical properties of language models on graph tasks. Consider the following citations for more evidence of this:

  1. Gregor Bachmann and Vaishnavh Nagarajan. The Pitfalls of Next-Token Prediction. ICML 2024.
  2. 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. ICLR 2025.
  3. Arvid Frydenlund. Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More More. ACL 2025.
  4. 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. ICML 2025.
  5. Shahriar Noroozizadeh, Vaishnavh Nagarajan, Elan Rosenfeld, and Sanjiv Kumar. Deep sequence models tend to memorize geometrically; it is unclear why. ICML 2026.
  6. 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. ICML 2026.

With 2, 3, 5 and 6 concerning graph scaling, and all of which use synthetic graphs with random IDs. There are many others as well.

B) I also have no problem only using a single LLM backbone. This paper is not about benchmarking performance of different LLMs on these graph tasks.

Note: my score is closer to 2.5 than 2. This paper as is, is borderline, but I feel like improvements can be made to make it an accept, either for this conference or as a resubmit.

Questions for authors

Q1) Why did you not consider training small models from scratch on the tasks? I'm not sure that zero-shot performance on these graph tasks is a great way of evaluating the baseline performance on these tasks. I understand that training from scratch conflicts with the motivating narrative that this is about test-time compute, which is primarily of interest for pre-trained LMs, but your method should work just as well for specifically trained models. My worry is that, for a small specifically trained model to succeed, it would need to be permutation invariant in the first place, so the model would learn to not be sensitive to the thing you are studying. On the other hand, if the model learns to solve the task but is still sensitive, and your intervention fixes that sensitivity, then you have a very compelling result.

Q2) Why did you not consider comparison to CoT? From the motivating narrative, this is about how to best budget inference-time compute, and you contrast sampling rewritings vs. sampling different outputs based on a single static prompt. Which makes sense, and you point to prior scaling laws about taking multiple samples from a static prompt. However, in your environment, the output is a single token, not different reasoning traces etc. A single-token output is not the setting of these prior scaling laws, correct? Also CoT is the most ubiquitous setting for considering test-time compute. Not only does this create an unrealistic setting if what you care about is comparing in a true pre-trained LM inference-time setting, but, as far as I can tell, your theoretical results do not depend on this, so a CoT setting feels like missing viable experiments. I also feel like there is a tension between Q1 and Q2. If you don't care about the realistic pre-trained LM setting, why not consider training small models on the task, but if you do care, why not consider CoT? Also note that, in the case where your tasks do not support CoT, you are free to consider other tasks. I feel like not having CoT experiments is a major conflict with the paper's motivating narrative (which I think is valid, just not evaluated).

Q3) Why did you not consider larger graph sizes? I understand the log scaling law depends on the number of possible permutations of the graph, thus, you do not need to consider large n to see a large differences in n!. I also understand that large n would be unviable for your first experiment, considering the bound between the log sampled average and the true average. However, your second experiment concerns task accuracy, and the log law is precisely interesting because it is viable to scale to large graphs without requiring many more samples. Like this is the very fact that makes your theoretical result interesting in practice, and you do not really empirically evaluate it. Indeed, it may be that order-sentivity becomes more of an issue as n grows on these tasks, which would make your results even more impressive. This feels like an obviously missing experiment which does not even change your broader experimental setting.

Q4) Why did you not consider relabeling and edge-list reordering as different things to ablate? I understand that this should have no bearing on the theorem, but would it allow you to consider which has more direct effect on accuracy? Also, were both sets of experiments symmetrical in how they combined relabeling and reordering?

Q5) In a similar way, why did you not consider different graph topologies? I understand that the theorem should not depend on the graph structure, but could it not be that different structures lead to different accuracies, which may present a larger gap for the rewriting intervention to actually show an accuracy difference? I guess my point is that, if you are using accuracy to show why rewriting matters, could it not be the case that different topologies or larger graph sizes lead to situations where the model is more sensitive to node order, which is what you are studying? So even though the theorem should not depend on this, it may present a more compelling empirical environment to show that this has actual practical benefits? Also, different topologies may only matter on larger graphs since 5-7 nodes have very little structure.

Q6) Would it be fair to call this work an application of the results from Tahmasebi & Weber (2026)?

S1) My suggestion to the authors: this paper would be substantially more impressive if you could identify a task that is highly sensitive or adversarial to reorder/relabling issue. This would more directly tie the rewriting intervention into direct accuracy performance and gains, which would better justify such an intervention. Instead of just running a set of off-the-shelf graph tasks and evaluating which ones seem to be sensitive or not, I suggest that you could specifically design such a task, or do an analysis of existing tasks for sensitivity and thus hypothesize that your intervention should matter. This would make for a more compelling narrative. The difference is from 'Graphs should be permutation invariant; therefore, we evaluate graph tasks' to 'Graph task x should be highly sensitive to reordering, but not graph task y, and this hypothesis is reflected in accuracy gains from our intervention'.

5 comments
AuthorsOpenReview ↗

Response to Reviewer 21fb (1/4)

We sincerely thank the reviewer for the careful and detailed reading, for the positive assessment of the theory and the writing, and for the very concrete suggestions. We address the concerns on the experiments below with a large set of new experiments, and we think the paper is now the one the reviewer describes in the last line of the review.

Following your suggestions, we ran a new and much larger set of experiments and uploaded a revised manuscript, with new material in red (both in main text and appendix). The message of the paper remains the same, with much stronger evidence through lots of new empirics we added upon the reviewers' requests.

Quick: “SC-16” is self consistency with 1616 independently sampled reasoning traces at the original prompt followed by a majority vote. “Sym-16” draws 1616 random rewritings of the prompt, samples one reasoning trace at each, and takes a majority vote over the 1616 answers. The two procedures are compared at equal cost as each uses 1616 forward passes in total, and generated traces have the same average length in both cases. Every instance has an exact ground truth (computed from the generated graph or ordering), and a procedure is correct on an instance if its voted answer matches it. Gain is the accuracy of Sym-16 minus the accuracy of SC-16 on the same instances, in percentage, with a 95%95\% bootstrap interval over instances and bold means the interval excludes zero.

Critical weakness 2 and S1

Answer. Thanks for this suggestion, it shaped the way we rewrote Section 5. We want to first note that the theory does speak to accuracy, through Corollary 4. It says that symmetrization with ∣S∣|S| rewritings has error at most that of the fully symmetrized decision plus a margin term plus the ∣S∣−1/2|S|^{-1/2} rewriting term, so rewriting helps exactly when two things hold. The model's answer must actually change across representations (otherwise there is nothing to average), and the symmetrized decision must be more accurate than a typical representation (the model must be right on a good part of the orbit). This is the hypothesis the reviewer asks for, and the revised Section 5 is organized around testing it.

We now measure sensitivity directly (the "flip rate", the fraction of instances whose greedy answer changes across 1616 rewritings) and competence (accuracy), and we check whether they predict the gain. Across the 9898 (model, task, size) cells of four model families on graphs, the 6060 cells where the model is sensitive (flip rate above 0.50.5) and competent (above 40%40\%) contain 2020 significant gains with a mean of +2.1+2.1 points, while the other 3838 cells have a mean gain of 0.00.0 (Section 5, Appendix H.2). Sensitivity also grows with the graph size, and the gain follows it, see our answer to Q3 below. Please check Table 1 of the revised paper (graphs with n=16n=16 nodes, n=24n=24 for Qwen2.5-7B, budget 1616 passes):

ModelTaskGreedySC-16Sym-16Gain [95% CI]flip
Qwen2.5-7B (n=24n=24)edge count0.420.810.92+10.8 [+3.8, +18.4]0.94
edge existence0.880.961.00+3.9 [+0.9, +8.0]0.75
node degree0.440.400.38−2.2 [−8.0, +3.4]0.90
Llama-3.1-8Bedge count0.280.600.70+10.0 [+2.3, +18.3]1.00
Phi-4-miniedge count0.710.890.99+9.7 [+5.5, +14.0]0.79
node degree0.680.750.82+6.9 [+2.2, +11.9]0.88
Qwen2.5-14B-AWQnode degree0.830.850.94+9.0 [+2.1, +17.1]0.73

We also followed the suggestion to design a task that is sensitive by construction. In the new logical deduction task (Figure 4 in Section 5, Table 5 in Appendix H.5) the model is given k−1k-1 height comparisons between kk people and asked who is the tallest. The premises can be reordered (Sk−1S_{k-1}), each statement can be flipped between "taller than" and "shorter than" (Z2k−1\mathbb Z_2^{k-1}), or both. The chain of comparisons must be followed through the whole prompt, so order sensitivity should grow with kk, and it does. For k=11k=11 and both groups, one greedy pass is right 51%51\% of the time, SC-16 reaches 79%79\%, and Sym-16 reaches 99%99\% (gain +19.5+19.5, CI [+11.9,+27.3][+11.9,+27.3]). Across the 2727 cells of this task, 1313 are significant gains and none is a significant loss.

So the narrative is now the one the reviewer suggests. We predict from sensitivity and competence where rewriting should help, and the accuracy gains land there, large and significant, and nowhere else.

AuthorsOpenReview ↗

Response to Reviewer 21fb (2/4)

Q2) Comparison to CoT?

Answer. Thanks for your suggestion! We address this concern directly, and it is the main change in our revised version. All accuracy results in Section 5 and Appendix H.2–H.6 of the revised version now use chain of thought traces. The model is asked to reason step by step and end with an answer line, each forward pass is one sampled trace at temperature 0.70.7, and self consistency with 1616 traces is the baseline that rewriting is compared against at the same number of forward passes. Traces at a rewriting are the same length on average as at the original prompt (token ratio 0.9990.999, see Appendix H.1), so matching the number of passes also matches the number of generated tokens. The models are now Qwen2.5-7B-Instruct (main), Phi-4-mini (3.8B), Llama-3.1-8B-Instruct and Qwen2.5-14B-Instruct-AWQ.

In this setting resampling is a meaningful use of compute, and it does help. On edge counting with n=24n=24 (Qwen2.5-7B), one greedy pass is right 39%39\% of the time and 6464 traces at the original prompt reach 89%89\%. But the resampling curve flattens, as Theorem 1 says it must, while 1616 rewritings already reach 100%100\% against 83%83\% for 1616 traces, a gain of +16.5+16.5 points (CI [+11.3,+22.2][+11.3,+22.2]):

edge count, n=24n=24, Qwen2.5-7B, budget kk passesk=1k=1k=4k=4k=16k=16k=64k=64
kk traces, no rewriting (self consistency)0.390.660.830.89
kk rewritings, one trace each0.390.801.000.995

Figure 3 of the revised paper shows these curves for six (task, size, model) cells, and Table 3 in Appendix H.2 gives the whole allocation grid, mm rewritings with 16/m16/m traces each. Accuracy increases monotonically in mm wherever the model is order sensitive. We keep the single-token setting in one place only, to measure the approximation law of Theorem 2 itself, which needs the model's answer distribution at each rewriting rather than a sampled answer (Figure 5, Appendix H.8, now up to n=32n=32).

Q3) Larger graph sizes?

Answer. We did exactly this, and the reviewer's comment is right. The graphs now have n∈{8,12,16,20,24}n\in\{8,12,16,20,24\} nodes for the accuracy experiments (Table 2 in Appendix H.2) and up to n=32n=32 for the approximation law (Figure 5). Figure 6 in Appendix H.3 plots sensitivity and gain against nn at a fixed budget of 1616 passes for Qwen2.5-7B. On edge counting the flip rate rises from 0.120.12 at n=8n=8 to 0.940.94 at n=24n=24 and the gain rises with it, from +1.0+1.0 to +10.8+10.8 points, while the cost stays at 1616 passes although ∣G∣=n! ∣E∣!|G|=n!\,|E|! grows from 8! ∣E∣!8!\,|E|! to 24! ∣E∣!24!\,|E|!. On the approximation side, Figure 5 shows that the rescaled error ∣S∣ ∥ASF−PGF∥/∥F−PGF∥\sqrt{|S|}\,\|\mathsf A_SF-\mathsf P_GF\|/\|F-\mathsf P_GF\| stays between 0.90.9 and 1.11.1 for all nn from 88 to 3232, so the number of rewritings needed for a given accuracy of the group average does not grow with nn. This is the practical content of the log⁡∣G∣\log|G| law that the reviewer points to, and we now show it directly.

AuthorsOpenReview ↗

Response to Reviewer 21fb (3/4)

Q1) Why not consider training small models from scratch?

Answer. Thanks for this suggestion, we ran it and it gives exactly the compelling case the reviewer describes (Figure 10 in Appendix H.7). We train a four-layer transformer encoder (0.80.8M parameters) from scratch on edge counting for graphs with n=10n=10 nodes, under three regimes. With a canonical serialization only, the model is perfect on its training format (100%100\%), but only 85%85\% accurate on a random rewriting of the same graph, and 72%72\% of the test graphs change their prediction across rewritings. So the model learned the task and is still sensitive, and symmetrization fixes it, as averaging over 1616 rewritings gives 99.5%99.5\% and over 6464 gives 100%100\%. The relative error of the sparse average follows ∣S∣−1/2|S|^{-1/2} to two decimals. With random rewritings during training (10%10\% of the examples, or all of them) the model becomes invariant (flip rate 0.0000.000) and symmetrization gains nothing, which is the other case of Corollary 4.

Q4) Why not consider relabeling and edge-list reordering as different things to ablate?

Answer. We added this ablation (Figure 11 in Appendix H.8). In the revised experiments the group is G=Sn×S∣E∣G=S_n\times S_{|E|}, and a rewriting is a pair of an independent random node relabeling and an independent random edge-order permutation, the same in all experiments. Figure 11 measures the fraction of graphs whose answer changes under relabeling only, reordering only, and both (Qwen2.5-7B, n=32n=32). Relabeling moves the answer more than reordering on every task, for example 0.870.87 against 0.700.70 on edge existence, 0.630.63 against 0.520.52 on edge counting, and 0.450.45 against 0.280.28 on connectivity, and reordering alone is already substantial on the edge-level tasks. Both together is close to relabeling alone. We also note that the serialization matters here. With adjacency lists instead of edge lists there is no edge order to permute, and the sensitive tasks change (Table 4 in Appendix H.2), see Q5.

Q5) Why not consider different graph topologies?

Answer. We added stochastic block model graphs (two communities) and planted-cycle graphs, at n∈{16,24}n\in\{16,24\}, and two serialization variants, adjacency lists and letter node labels (Table 4 in Appendix H.2). On the two topologies the picture matches ER graphs, with edge counting at n=24n=24 gaining +10.9+10.9 on SBM and +6.8+6.8 on planted cycle, and component counting on SBM at n=16n=16 gaining +5.0+5.0 (CI [+1.7,+8.9][+1.7,+8.9]), where the community structure makes the count order sensitive. Changing the serialization moves which tasks are sensitive but not the rule. With adjacency lists, node degree becomes the sensitive task and gains +3.3+3.3 (CI [+0.3,+7.2][+0.3,+7.2]) while edge counting no longer does. So the reviewer's intuition is right that the environment decides where sensitivity appears, and in every environment the gain follows the sensitivity.

Reviewer_xr3dOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The authors study test-time symmetrization for frozen language models by separating output-side randomness (repeatedly decoding from a single prompt, or sampling along a "decoding fiber") from input-side randomness (applying symmetry transformations from a finite group GG to move along a "rewriting orbit"). Because averaging over the entire orbit requires ∣G∣\vert{}G\vert{} model calls—an impossible budget for large groups like node permutations SnS_n of size n!n!—they analyze how well a sparse operator ASA_S, formed by averaging over a small random multiset of rewritings S⊂GS \subset G, approximates the full group average.

Critical strengths
  1. The paper provides precise language to analyze test-time compute allocation. Showing via Lemma 13 and Lemma 15 that a single operator norm bound ∥AS−PG∥L2(G)→L2(G)\Vert{}A_S - P_G\Vert{}_{L^2(G) \to L^2(G)} controls arbitrary Hilbert-valued decoding rules (including nonlinear verifier weighting) and realized random decoders without paying a covering-number penalty over Ω\Omega or class count CC is a very clean theoretical insight.
  2. The authors do very clean and thorough testing of the exact mathematical quantities in their theorems. Table 1 and Figure 7 transparently report all six graph tasks, including the four tasks where symmetrization provides zero or slightly negative gain, and clearly link those outcomes to the three terms of Corollary 4.
Critical weaknesses

The paper's narrative centers on scaling test-time compute across reasoning traces ω\omega, but the experiments only perform 1-token zero-shot classification with Qwen2.5-1.5B-Instruct on tiny graphs (n=7n=7), where the model is mostly guessing (e.g., 6% accuracy on connected components vs. 17% constant-prediction baseline; 13%–16% on triangle count vs. 10% baseline; pooled gain across all 6 tasks is +0.8+0.8 points with 95% CI [−0.1,+1.7][-0.1, +1.7], which is not statistically significant). In Figure 4 (Left), sampling more answers at one rewriting (r=kr=k, blue curve) actually decreases accuracy on edge count from k=1k=1 (0.211) to k=16k=16 (0.199) because the greedy top-1 token is more often wrong than the distribution average. Evaluating actual multi-token Chain-of-Thought generation (or a stronger model where CoT self-consistency is non-trivial) is needed to prove the claims about reasoning traces.

Questions for authors
  1. Given that your motivation relies heavily on multi-step reasoning traces ω∼pθ,τ(⋅∣g⋅x)\omega \sim p_{\theta,\tau}(\cdot \mid g \cdot x) and self-consistency voting, have you tested what happens when the model actually generates multi-token Chain-of-Thought responses (either with Qwen2.5-1.5B-Instruct or a stronger 7B+ model) on these graph problems or standard permutation-sensitive benchmarks like MMLU and GSM-Symbolic? In particular, would the budget allocation in Figure 8 (mm rewritings vs. rr traces) behave differently if drawing more CoT samples (i.e., increasing rr) genuinely improves accuracy on a fixed prompt?
  2. In Section 3 and Definition 7, you mention that equivariant targets (y∗(g⋅x)=ρ(g)y∗(x)y^*(g \cdot x) = \rho(g)y^*(x)) are reduced to the invariant case by un-permuting the output coordinates with ρ(g)−1\rho(g)^{-1} before pooling. Can you provide at least one experiment on an equivariant task (for example, shuffling answer choices in MCQA or returning a target node label under relabeling) to validate test-time symmetrization with active output alignment?
3 comments
AuthorsOpenReview ↗

Response to Reviewer xr3d (1/3)

We sincerely thank the reviewer for the careful reading and for the positive assessment of the paper. We address the concern on the experiments below with a large set of new emprical results.

Following your suggestions, we ran a new and much larger set of experiments and uploaded a revised manuscript, with new material in red (both in main text and appendix). The message of the paper remains the same, with much stronger evidence through lots of new empirics we added upon the reviewers' requests.

Quick: “SC-16” is self consistency with 1616 independently sampled reasoning traces at the original prompt followed by a majority vote. “Sym-16” draws 1616 random rewritings of the prompt, samples one reasoning trace at each, and takes a majority vote over the 1616 answers. The two procedures are compared at equal cost as each uses 1616 forward passes in total, and generated traces have the same average length in both cases. Every instance has an exact ground truth (computed from the generated graph or ordering, or the dataset label for ARC), and a procedure is correct on an instance if its voted answer matches it. Gain is the accuracy of Sym-16 minus the accuracy of SC-16 on the same instances, in percentage, with a 95%95\% bootstrap interval over instances and bold means the interval excludes zero.

Critical weakness and Question 1

Answer. Thanks for your suggestion! We addressed this concern directly in our revised version. All accuracy results in Section 5 and Appendix H.2–H.6 of the revised version now use chain of thought traces. The model is asked to reason step by step and end with an answer line, each forward pass is one sampled trace at temperature 0.70.7, and self consistency with 1616 traces is the baseline that rewriting is compared against at the same number of forward passes (i.e. same compute). Traces at a rewriting are the same length on average as at the original prompt (token ratio 0.9990.999, see Appendix H.1), so matching the number of passes also matches the number of generated tokens. The models are now Qwen2.5-7B-Instruct (main), Phi-4-mini (3.8B), Llama-3.1-8B-Instruct and Qwen2.5-14B-Instruct-AWQ, on graphs with n∈{8,12,16,20,24}n\in\{8,12,16,20,24\} nodes, 6060 to 200200 instances per cell.

In this setting resampling is a meaningful use of compute, and it does help, so the effect the reviewer noticed in the figure in initial submission is gone. On edge counting with n=24n=24 (Qwen2.5-7B), one greedy pass is right 39%39\% of the time and 6464 traces at the original prompt reach 89%89\%. But the resampling curve flattens, as Theorem 1 says it must, while 1616 rewritings already reach 100%100\% against 83%83\% for 1616 traces, a gain of +16.5+16.5 points (CI [+11.3,+22.2][+11.3,+22.2]):

edge count, n=24n=24, Qwen2.5-7B, budget kk passesk=1k=1k=4k=4k=16k=16k=64k=64
kk traces, no rewriting (self consistency)0.390.660.830.89
kk rewritings, one trace each0.390.801.000.995

Please check Table 1 of our revised paper (graphs with n=16n=16 nodes, n=24n=24 for Qwen2.5-7B, budget 1616 passes):

ModelTaskGreedySC-16Sym-16Gain [95% CI]
Qwen2.5-7B (n=24n=24)edge count0.420.810.92+10.8 [+3.8, +18.4]
edge existence0.880.961.00+3.9 [+0.9, +8.0]
node degree0.440.400.38−2.2 [−8.0, +3.4]
Llama-3.1-8Bedge count0.280.600.70+10.0 [+2.3, +18.3]
edge existence0.720.810.86+5.5 [−0.7, +12.3]
node degree0.680.880.90+1.9 [−4.3, +8.4]
Phi-4-miniedge count0.710.890.99+9.7 [+5.5, +14.0]
edge existence0.890.971.00+2.4 [+0.6, +4.5]
node degree0.680.750.82+6.9 [+2.2, +11.9]
Qwen2.5-14B-AWQedge count0.630.710.69−1.9 [−7.5, +3.8]
edge existence0.980.991.00+0.7 [+0.0, +2.0]
node degree0.830.850.94+9.0 [+2.1, +17.1]
AuthorsOpenReview ↗

Response to Reviewer xr3d (2/3)

Answer continued. The gains are now large and statistically significant, and they appear in every model family (on different tasks, as Corollary 4 predicts). The gain depends on which decisions a given model gets right on part of its orbit. The full table over all seven graph tasks and all sizes (9898 model/task/size cells on ER graphs) is Table 2 in Appendix H.2, and Figure 3 shows the resampling-versus-rewriting curves for six (task, size, model) cells.

On budget allocation: it's a great question, and the answer is that increasing rr now does improve accuracy on a fixed prompt, but moving budget to rewritings still improves it more. Table 3 in Appendix H.2 gives the whole allocation grid for a budget of 1616 passes, mm rewritings with r=16/mr=16/m traces each, majority vote over all 1616 traces, Qwen2.5-7B. A subset of the results (full in the revised version):

Task, nnm=1m=1 (r=16r=16)m=4m=4 (r=4r=4)m=8m=8 (r=2r=2)m=16m=16 (r=1r=1)
edge count, 240.8170.9120.9270.930
edge count, 200.9100.9480.9590.961
edge existence, 200.9770.9910.9930.995
node degree, 160.5700.5660.5600.557
cycle, 160.5500.5470.5380.535

So the picture is what our theory predicts (Theorem 1 and Corollary 4). If the model is order sensitive, accuracy increases monotonically in mm at a fixed total budget, with most of the gain already at m=4m=4. If it is not the case (node degree, cycle for Qwen2.5-7B), the row is flat and the allocation does not matter. Figure 3 shows the same effect with budgets up to 6464 passes. With reasoning traces, more samples at one prompt help (from 39%39\% to 89%89\% on edge counting at n=24n=24) but the curve flattens, while the same budget spent on rewritings reaches 99.5%99.5\%–100%100\%.

On benchmarks, we chose tasks where the symmetry group is exact and the correct answer is computable, so that the comparison is clean. Beyond the graph problems we added a logical deduction task with reasoning traces, where the model is given k−1k-1 height comparisons and asked who is the tallest of kk people (Figure 4 in Section 5, Table 5 in Appendix H.5). We test it under three different groups. The first reorders the premises (Sk−1S_{k-1}). The second flips each statement between "taller than" and "shorter than" (Z2k−1\mathbb Z_2^{k-1}, which is not a permutation group and is the hypercube on which the log⁡∣G∣\log|G| factor of Theorem 2 is attained). The third applies both together. For k=11k=11 and both groups, one greedy pass is right 51%51\% of the time, SC-16 reaches 79%79\%, and Sym-16 reaches 99%99\% (gain +19.5+19.5, CI [+11.9,+27.3][+11.9,+27.3]). Across the 2727 (question, group, kk) cells, 1313 are significant gains and none is a significant loss. We also added ARC-Challenge with permuted answer options, see our answer to Question 2 below.

We did not run MMLU or GSM-Symbolic. For MMLU the natural symmetry is the same option permutation as in ARC. For GSM-Symbolic the rewritings change the numbers in the problem, so they are not a group action, and they fall under the paraphrase-style rewritings discussed in Appendix H.6 and in the conclusion, where the method still applies but with an extra drift term. We chose ARC-Challenge over MMLU because the symmetry is the same option permutation, and GSM-Symbolic rewrites the numbers in a problem, which is a paraphrase-style rewriting rather than a group action, the setting we test in Appendix H.6.

AuthorsOpenReview ↗

Response to Reviewer xr3d (3/3)

Question 2

Answer. Thanks for the suggestion, we added exactly this experiment to the paper (Table 6 in Appendix H.5). We use ARC-Challenge, a standard benchmark of grade-school science questions, each with four answer options labeled A–D, where the model must pick the correct letter. We use 500500 questions and permute the four options, G=S4G=S_4, ∣G∣=24|G|=24. Here the answer is equivariant rather than invariant. Permuting the options moves the correct letter, so before voting we map each predicted letter back through the inverse permutation, as described in Section 3 and Definition 7. Qwen2.5-7B with reasoning traces:

ProcedureAccuracy
greedy, original option order (1 pass)0.918
1616 permutations, one trace each, aligned vote0.946
all 2424 permutations, one trace each, aligned vote0.948
1616 permutations, one trace each, vote without alignment0.244

The aligned vote over 1616 permutations gains +2.6+2.6 points over a matched vote at the original order (CI [+0.8,+4.6][+0.8,+4.6]), on a benchmark where the model is already at 92%92\%. The same vote without undoing the permutation gives 24.4%24.4\%, i.e., chance level, as it should, since the votes then refer to different orderings. This confirms that the gain comes from the equivariant alignment of Definition 7. We also note that 25.6%25.6\% of the questions change their greedy answer under some permutation of the options, so even a strong model is far from invariant to option order, and this is the sensitivity that the aligned vote removes.


We hope our additions address the reviewer's concerns. The revised experiments now test the claims of the paper with reasoning traces, stronger models of several families, and an equivariant task with active output alignment, exactly as the reviewer asked, and we would be grateful if the reviewer would consider updating their score. We are happy to answer any further questions.

Reviewer_oDcXOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

The paper studies test-time symmetrization, which spends forward passes on group rewritings of a prompt and averages the decoded responses over the orbit. It proves that decoding from one representation cannot replace rewriting, that O(log|G|) random rewritings approximate the full group average uniformly over models, decoders, and realized traces with the log factor tight for Z2nZ^n_2, and gives an error decomposition through the decision margin. Exact operator-norm computations confirm the rate, and experiments with a frozen Qwen2.5-1.5B on six graph tasks show one rewriting set serves all decoders and improves accuracy on the two tasks where the orbit average is more accurate than a typical serialization.

Critical strengths
  • The manuscript is extremely well written. The theory is easy to follow and, to my understanding, correct.
  • The form of scaling test-time compute by rewriting the prompt is very interesting and the idea of analizing it more formally is appealing.
Critical weaknesses
  • The experimental evidence is limited, both in breadth and size of the effect. The study analises a single model under a single family of tasks based on ER graphs, leaving generalization across task domains and models unclear. Within such setting the effects are small and task dependent: symmetrization is superior to the 1 rewrite baseline on 2 tasks out of 6 and to self-consistency only on 1. I would suggest trying out different models of slightly bigger sizes and define tasks in different settings other than ER graphs.
  • The model only generates a single token after the prompt, which is the answer. This is not the typical setting in which test-time compute by multiple independent rollouts conditioned on the same prompt is done. As can be seen in Fig 4 such decoding at one rewriting does not scale with rr. It would be interesting to see such comparason in a setting with reasoning traces where additional samples provide a meaningful alternative use of test-time scaling.
  • The framework assumes a known, exact finite group acting on the prompt. This excludes paraphrase-style rewritings in natural language, where no group structure exists. The conclusion lists this as future work.
  • Limited analisys of the accuracy between rewrites. Fully evaluating every rewrite can enable further analisys by comparing: the average individual rewrite accuracy, with the worst-case individual rewrite accuracy, with the full group-average accuracy, with the log(G) group-average accuracy approximation.
Questions for authors
  • Have you tested on more LLMs? Maybe of different families and of different sizes?
  • Have you tested on settings not based on ER graphs where the number of rewrites does not scale factorially?
  • Given that in practice a rewriting class is rarely defined, could potentially an LLM asked to reframe a prompt create a class of prompts with properties near what your theory describes?
5 comments
AuthorsOpenReview ↗

Response to Reviewer oDcX (1/5)

We sincerely thank the reviewer for the careful reading and for the positive assessment of the paper.

Following your suggestions on experiments, we ran a new and much larger set of experiments and uploaded a revised manuscript, with new stuff in red (both in main text and appendix). The message of the paper remains the same, with much stronger evidence through lots of new empirics we added upon reviewer's request.

Quick: “SC-16” is self consistency with 1616 independently sampled reasoning traces at the original prompt followed by a majority vote. “Sym-16” draws 1616 random rewritings of the prompt, samples one reasoning trace at each, and takes a majority vote over the 1616 answers. The two procedures are compared at equal cost as each uses 1616 forward passes in total, and generated traces have the same average length in both cases. Every instance has an exact ground truth (computed from the generated graph or ordering, or the dataset label for ARC and SST-2), and a procedure is correct on an instance if its voted answer matches it. Gain is the accuracy of Sym-16 minus the accuracy of SC-16 on the same instances, in percentage, with a 95%95\% bootstrap interval over instances and bold means the interval excludes zero.

More LLMs? Maybe of different families and of different sizes?

Answer. The revised experiments use four model families and sizes as follows: Qwen2.5-7B-Instruct (main model), Phi-4-mini (3.8B), Llama-3.1-8B-Instruct, and Qwen2.5-14B-Instruct-AWQ (4-bit). The next-token field experiments (Figure 5, Appendix H.8) are run on both Qwen2.5-1.5B and Qwen2.5-7B. The same set of rewritings is drawn once per instance and reused for every model, supporting our theory (Corollary 3).

Please check Table 1 of our revised paper (graphs with n=16n=16 nodes, n=24n=24 for Qwen2.5-7B, budget 1616 passes):

ModelTaskGreedySC-16Sym-16Gain [95% CI]
Qwen2.5-7B (n=24n=24)edge count0.420.810.92+10.8 [+3.8, +18.4]
edge existence0.880.961.00+3.9 [+0.9, +8.0]
node degree0.440.400.38−2.2 [−8.0, +3.4]
Llama-3.1-8Bedge count0.280.600.70+10.0 [+2.3, +18.3]
edge existence0.720.810.86+5.5 [−0.7, +12.3]
node degree0.680.880.90+1.9 [−4.3, +8.4]
Phi-4-miniedge count0.710.890.99+9.7 [+5.5, +14.0]
edge existence0.890.971.00+2.4 [+0.6, +4.5]
node degree0.680.750.82+6.9 [+2.2, +11.9]
Qwen2.5-14B-AWQedge count0.630.710.69−1.9 [−7.5, +3.8]
edge existence0.980.991.00+0.7 [+0.0, +2.0]
node degree0.830.850.94+9.0 [+2.1, +17.1]

Interestingly, every model shows significant gains, but on different tasks: Qwen2.5-7B on edge counting and edge existence, Phi-4-mini on all three, Llama on edge counting, the 14B model on node degree. This is what Corollary 4 in our paper predicts: the gain of symmetrization depends on which decisions a given model gets right on part of its orbit, so it is a property of the model, not of the method. The full table over all seven graph tasks and all sizes (9898 model/task/size cells on ER graphs) is Table 2 in Appendix H.2.

AuthorsOpenReview ↗

Response to Reviewer oDcX (2/5)

Have you tested on settings not based on ER graphs where the number of rewrites does not scale factorially?

Answer. Yes! We added three families of experiments where the group is not SnS_n and the orbit does not grow factorially in the input size, plus other graph distributions.

Setting 1. Logical deduction under three groups (Figure 4 in Section 5; Figure 8 and Table 5 in Appendix H.5). A prompt lists k−1k-1 adjacent height comparisons between kk people ("A is taller than B", ...) and asks who is tallest, who is jj-th tallest, or how two named people compare. We use three different groups of rewritings. (i) Reordering the premises, G=Sk−1G=S_{k-1}: the lines are listed in a random order. (ii) Flipping each statement, G=Z2k−1G=\mathbb Z_2^{k-1}: each line "A is taller than B" is independently either kept or replaced by "B is shorter than A", which states the same fact. We stress that this group is not a permutation group: it is a product of k−1k-1 independent binary choices, so ∣G∣=2k−1|G|=2^{k-1} grows exponentially rather than factorially, and it is exactly the hypercube on which the log⁡∣G∣\log|G| factor of Theorem 2 is attained. (iii) Both together, G=Sk−1×Z2k−1G=S_{k-1}\times\mathbb Z_2^{k-1}: a random reordering of the lines combined with an independent random flip of each line. Results for "who is tallest", Qwen2.5-7B, 100100 instances per kk:

GroupkkGreedySC-16Sym-16Gain [95% CI]
premise order Sk−1S_{k-1}110.830.941.00+5.8 [+1.8, +10.8]
statement flips Z2k−1\mathbb Z_2^{k-1}110.610.770.86+9.6 [+2.6, +16.8]
both80.750.861.00+13.9 [+7.0, +20.9]
both110.510.790.99+19.5 [+11.9, +27.3]

Table 5 in Appendix H.5 in the paper reports all three questions, all three groups, and k∈{5,8,11}k\in\{5,8,11\}, that is 2727 cells with 100100 instances each, and Figure 8 plots the full 3×33\times 3 grid. Please check them for a more comprehensive set of experiments on this. Across those 2727 cells, 1313 cases show significant gains (interval excluding zero) and none is a significant loss.

Setting 2. Multiple choice with an equivariant answer (Table 6 in Appendix H.5). We use ARC-Challenge, a standard benchmark of grade-school science questions, each with four answer options labeled A–D, where the model must pick the correct letter. We use 500500 questions and permute the four options, G=S4G=S_4, ∣G∣=24|G|=24. Here the answer is equivariant rather than invariant: permuting the options moves the correct letter, so before voting we map each predicted letter back through the inverse permutation, as described in Section 3. Qwen2.5-7B goes from 91.8%91.8\% at the original ordering to 94.6%94.6\% with the aligned vote over 1616 permutations (+2.6+2.6, CI [+0.8,+4.6][+0.8,+4.6]). The same vote without alignment gives 24.4%24.4\% (i.e., chance level) which confirms that the equivariant structure is what is being used here. Please check the paper (Table 6 in Appendix H.5) for more comprehensive results.

Setting 3. Other graph distributions and serializations (Table 4 in Appendix H.2). On stochastic block model graphs and planted-cycle graphs the picture matches ER (edge count at n=24n=24: +10.9+10.9 on SBM, +6.8+6.8 on planted cycle). Switching the serialization from edge lists to adjacency lists, or from integer to letter node labels, moves which tasks are order sensitive but not the conclusion: with adjacency lists node degree becomes the sensitive task and gains +3.3+3.3 (CI [+0.3,+7.2][+0.3,+7.2]) while edge counting no longer does. Please refer to our revised version for the full results.

AuthorsOpenReview ↗

Response to Reviewer oDcX (3/5)

The model only generates a single token after the prompt, which is the answer. This is not the typical setting in which test-time compute by multiple independent rollouts conditioned on the same prompt is done... It would be interesting to see such comparison in a setting with reasoning traces where additional samples provide a meaningful alternative use of test-time scaling.

Answer. Thanks for your suggestion! This is the main change in our revised version experiments. All accuracy results in Section 5 and Appendix H.2–H.7 of the revised version use chain of thought traces: the model is asked to reason step by step and end with an answer line, each forward pass is one sampled trace at temperature 0.70.7, and self consistency with 1616 traces is now the baseline that rewriting is compared against at the same number of forward passes. Traces at a rewriting are the same length on average as at the original prompt (token ratio 0.9990.999, see Appendix H.1), so matching the number of passes also matches the number of generated tokens.

In this setting resampling is a meaningful use of compute, and it does help: on edge counting with n=24n=24 (Qwen2.5-7B), one greedy pass is right 39%39\% of the time and 6464 traces at the original prompt reach 89%89\%. But the resampling curve flattens, as Theorem 1 says it must, while 1616 rewritings already reach 100%100\% against 83%83\% for 1616 traces, a gain of +16.5+16.5 points (CI [+11.3,+22.2][+11.3,+22.2]):

edge count, n=24n=24, Qwen2.5-7B, budget kk passesk=1k=1k=4k=4k=16k=16k=64k=64
kk traces, no rewriting (self consistency)0.390.660.830.89
kk rewritings, one trace each0.390.801.000.995

We have much more comprehensive experiments on this line in the revised version. Figure 3 of the revised paper shows the two plots for six (task, size, model) cells, and Table 3 in Appendix H.2 gives the whole allocation grid, mm rewritings with 16/m16/m traces each for m∈{1,4,8,16}m\in\{1,4,8,16\}: accuracy increases monotonically in mm wherever the model is order sensitive.

We keep the single-token setting in one place only, and just to toevaluate Theorem 2. The theorem concerns how well the average over ∣S∣|S| random rewritings approximates the average over the full group, and testing it needs the model's answer distribution at each rewriting, not a sampled answer. With a single-token prompt this distribution is read exactly from the next-token probabilities in one forward pass. Note that this with reasoning traces it could only be estimated from many samples. This is what Figure 5 and Appendix H.8 do, now for graphs up to n=32n=32 nodes and for both Qwen2.5-1.5B and Qwen2.5-7B.

We also now have a cleared message on when rewriting cannot help (Section 5 and Appendix H.2). Corollary 4 says rewriting helps only when two things hold: the model's answer actually changes across representations, and the model is right on a good part of the orbit. We split the 9898 graph cells (model, task, size) of the four models by these two conditions. In the 6060 cells where the model is order sensitive (its greedy answer changes on more than half of the instances) and competent (above 40%40\% accuracy), rewriting gives 2020 significant gains, with a mean gain of +2.1+2.1 points.

In the other 3838 cells it barely gives gains. This is because whether the answer is stable or the model is lost on every representation, and there is nothing to average and get benefit. The one systematic loss is cycle detection at n=8n=8, where every model has the same bias toward "yes" on acyclic graphs at every representation. Thus, an invariant bias is exactly what averaging over representations cannot remove, so this is the behavior Corollary 4 predicts rather than an exception. Taken together, these large-scale experiments behave exactly as our theory predicts in Corollary 4: rewriting helps where the model is sensitive and competent, and does nothing where it is not.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response to reviewers

We sincerely thank all the reviewers for their careful reading and for the positive assessment of the theory and the writing. All the concerns were about the experimental section, and we fully agree with them.

Therefore, we devoted the rebuttal period to ran a lot of new experiments, in exactly the settings the reviewers asked for. We now have chain of thought traces with self consistency as the baseline at the same budget, four new model families:

  • Qwen2.5-7B-Instruct,
  • Phi-4-mini (3.8B),
  • Llama-3.1-8B-Instruct,
  • Qwen2.5-14B-Instruct-AWQ

instead of having one small model, larger graphs, and new tasks beyond graphs (logical deduction under three different groups, multiple choice with an equivariant answer, and paraphrases generated by another LLM). We uploaded a revised version with all the new material in red. We emphasize the theory and the message of the paper remain the same, but the evidence for it is now much stronger and clearer. The gains are large and statistically significant where our theory predicts them, and absent where our theory says they cannot occur. Please see our point by point responses below. We include a selected number of experiments here in this page, and for a complete version please see our revised file.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.