- 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
-
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.
-
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.
-
The paper is clearly written and easy to follow.
-
Despite my score, I really liked this paper. I just think it can be stronger.
Critical weaknesses
-
The empirical evaluation settings and results are of lower quality than the theoretical results (see questions).
-
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:
- Gregor Bachmann and Vaishnavh Nagarajan. The Pitfalls of Next-Token Prediction. ICML 2024.
- 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.
- Arvid Frydenlund. Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More More. ACL 2025.
- 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.
- Shahriar Noroozizadeh, Vaishnavh Nagarajan, Elan Rosenfeld, and Sanjiv Kumar. Deep sequence models tend to memorize geometrically; it is unclear why. ICML 2026.
- 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
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 , and self consistency with 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 , 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 (Qwen2.5-7B), one greedy pass is right of the time and traces at the original prompt reach . But the resampling curve flattens, as Theorem 1 says it must, while rewritings already reach against for traces, a gain of points (CI ):
| edge count, , Qwen2.5-7B, budget passes | ||||
|---|---|---|---|---|
| traces, no rewriting (self consistency) | 0.39 | 0.66 | 0.83 | 0.89 |
| rewritings, one trace each | 0.39 | 0.80 | 1.00 | 0.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, rewritings with traces each. Accuracy increases monotonically in 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 ).
Q3) Larger graph sizes?
Answer. We did exactly this, and the reviewer's comment is right. The graphs now have nodes for the accuracy experiments (Table 2 in Appendix H.2) and up to for the approximation law (Figure 5). Figure 6 in Appendix H.3 plots sensitivity and gain against at a fixed budget of passes for Qwen2.5-7B. On edge counting the flip rate rises from at to at and the gain rises with it, from to points, while the cost stays at passes although grows from to . On the approximation side, Figure 5 shows that the rescaled error stays between and for all from to , so the number of rewritings needed for a given accuracy of the group average does not grow with . This is the practical content of the law that the reviewer points to, and we now show it directly.
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 (M parameters) from scratch on edge counting for graphs with nodes, under three regimes. With a canonical serialization only, the model is perfect on its training format (), but only accurate on a random rewriting of the same graph, and 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 rewritings gives and over gives . The relative error of the sparse average follows to two decimals. With random rewritings during training ( of the examples, or all of them) the model becomes invariant (flip rate ) 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 , 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, ). Relabeling moves the answer more than reordering on every task, for example against on edge existence, against on edge counting, and against 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 , 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 gaining on SBM and on planted cycle, and component counting on SBM at gaining (CI ), 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 (CI ) 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.
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 16 independently sampled reasoning traces at the original prompt followed by a majority vote. “Sym-16” draws 16 random rewritings of the prompt, samples one reasoning trace at each, and takes a majority vote over the 16 answers. The two procedures are compared at equal cost as each uses 16 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% bootstrap interval over instances and bold means the interval excludes zero.
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∣ rewritings has error at most that of the fully symmetrized decision plus a margin term plus the ∣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 16 rewritings) and competence (accuracy), and we check whether they predict the gain. Across the 98 (model, task, size) cells of four model families on graphs, the 60 cells where the model is sensitive (flip rate above 0.5) and competent (above 40%) contain 20 significant gains with a mean of +2.1 points, while the other 38 cells have a mean gain of 0.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=16 nodes, n=24 for Qwen2.5-7B, budget 16 passes):
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−1 height comparisons between k people and asked who is the tallest. The premises can be reordered (Sk−1), each statement can be flipped between "taller than" and "shorter than" (Z2k−1), or both. The chain of comparisons must be followed through the whole prompt, so order sensitivity should grow with k, and it does. For k=11 and both groups, one greedy pass is right 51% of the time, SC-16 reaches 79%, and Sym-16 reaches 99% (gain +19.5, CI [+11.9,+27.3]). Across the 27 cells of this task, 13 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.