CS Paper Radar

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

Behrooz Tahmasebi, Melanie Weber

cs.AI ·submitted 2026-11-18 08:20 UTC · v1
theory

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 $G$ of rewritings. We prove that no amount of sampling and repeated decoding from a single representation can replace rewriting, while only $O(\log |G|)$ random rewritings suffice to recover the information provided by all $|G|$ rewritings. The same set of $O(\log |G|)$ rewritings provides simultaneous approximation across models, decoding rules, and sampled reasoning traces, and the logarithmic scaling is optimal in general. We validate the theory with experiments on Qwen2.5-7B, Phi-4-mini, Llama-3.1-8B, and Qwen2.5-14B, with chain-of-thought reasoning, on graph reasoning, logical deduction, and multiple-choice question answering. At the same number of forward passes, spending them on rewritings of the input is substantially more accurate than spending them on repeated sampling from the original prompt whenever the model's answer depends on how the input is written, and the number of rewritings needed grows only logarithmically with the number of possible rewritings, as the theory predicts. Our results provide a principled way to enforce symmetries at inference time when they cannot be built into the model, which we call model-agnostic symmetrization.

Comment
38 pages, 13 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Planned Test-Time Scaling with Coordinated Reasoning Paths

cs.CL cs.AI ·2026-09-23 ·Xueqing Wu, Langxing Bai, Hritik Bansal, Po-Nien Kung, Shuo Li +3 more
similarity 0.66
Abstract

Test-time scaling with parallel branches is widely adopted to improve performance on challenging reasoning tasks. The predominant approach, repeated sampling, draws branches independently from a single policy, which can produce redundant attempts and thereby limit the gains from additional inference compute. To address this limitation, we propose Planned Test-Time Scaling (PTTS), which replaces independent sampling with a coordinated joint policy: a planner generates a solution outline for each branch, steering the branches toward distinct reasoning paths, and an executor produces a full solution conditioned on each outline. Formally, we show that PTTS strictly generalizes repeated sampling and, in a stylized setting, provably promotes coverage of complementary reasoning modes and yields better pass@k scaling. We instantiate PTTS on top of strong reasoning models, keeping them fixed as executors while replacing repeated sampling with PTTS inference to further enhance test-time scaling. Concretely, we develop two variants: PTTS-ZS prompts a model to jointly generate outlines for all branches in a single autoregressive pass, while PTTS-RL directly optimizes the planner against the pass@k reward using truncated execution rollouts for efficient training and a sharper reward signal. Across five mathematical reasoning benchmarks with Qwen3-1.7B and 4B, PTTS-ZS improves pass@64 over repeated sampling by up to 6.7 points, while PTTS-RL further increases the gain to up to 13.4 points. Further analysis indicates that broader coverage of distinct reasoning paths contributes to these gains. Overall, PTTS provides a general framework for improving test-time scaling by coordinating reasoning branches, with zero-shot and trainable instantiations that yield substantial performance gains.

0.40

Rethinking LLM Pruning via Test-Time Scaling

cs.CL ·2026-10-31 ·Mingyang Song, Mao Zheng
similarity 0.65
Abstract

Structured pruning reduces the size of large language models, often at the cost of lower accuracy. Whether this decline reflects diminished reasoning capacity or greater difficulty in sampling correct solutions is less clear. We examine this question across expert, FFN and layer pruning on four mathematical and coding benchmarks, comparing original and pruned models through pass@k at matched sampling budgets. Even after substantial pruning, some models match or exceed the original model's reasoning coverage despite lower pass@1, and solve problems left unsolved in the original samples. Retaining broad coverage, however, does not mean that correct solutions remain easy to obtain. Under severe pruning, diverse generated chain-of-thought (CoT) traces can coexist with increased repetition and less reliable generation. As correct answers become harder to sample, the additional attempts can sharply increase total token use even when individual responses become shorter. This separation between coverage and sampling efficiency also clarifies expert-selection gains, as methods with markedly different pass@1 can solve the same problems at large budgets yet require different numbers of attempts to reach a common coverage target. Pruning should therefore be assessed by both the range of problems a model can still solve and the sampling cost of obtaining correct solutions.

0.10

Towards Better Exploration in Sequential Test-Time Scaling

cs.LG ·2026-09-30 ·Joseph Rance, Fabio Pizzati, Juil Sock, Woody Bayliss, Marc Górriz Blanch +2 more
similarity 0.65
Abstract · 26 pages, 15 figures

Test-time scaling improves language model reasoning by spending additional compute at inference. However, both classes of existing methods often fail to continue improving over long timescales. Parallel methods repeatedly sample independent answers from the model, scaling poorly on problems the model is unlikely to solve in a single attempt. In contrast, sequential methods build on previous answers to access new ideas, yet so far have not been shown to reach answers beyond those found by parallel scaling. First, we show that sequential scaling often stops improving because it becomes prematurely trapped in an attractor: a set of answers that prevents exploration of different answers once entered. Across 27 combinations of scaling methods, models, and benchmarks, we find that 53.8% of sequential scaling trajectories enter an attractor within four iterations. Second, we show that a simple model-mixing intervention helps escape attractors. This reduces the attractor hit rate by 21.2 percentage points on average, expands solution coverage beyond a compute-matched parallel baseline, and improves accuracy of recursive self-aggregation by at least 2.2 percentage points. Our results motivate refocusing long-horizon test-time scaling from parallel methods to sequential methods that improve previous answers.

0.29

Resample the Answer: Where to Spend Test-Time Compute in Recursive Reasoning

cs.LG ·2026-10-12 ·Maxime Illouz
code/datahot direction similarity 0.64
Abstract · 22 pages, 4 figures, 16 tables. v2: code and checkpoints released, clarified depth and width scaling in the abstract and contributions, mino…

Recursive reasoning models such as the Tiny Recursive Model (TRM) iteratively refine two latent states: an answer state y, decoded into the output, and a reasoning state z, which is never decoded. Many of their failures have been attributed to bad basins, regions of latent space that trap the recursion on wrong answers. Recent test-time approaches perturb y, z or both to recover these failures, but the impact of this choice on performance, test-time compute efficiency and scaling properties remains unclear. Through controlled experiments on TRM, we find that a failed trajectory carries its failure in its answer state. At equal compute, whether retries continue a failed trajectory (depth scaling) or draw multiple trajectories from the initial states (width scaling), resampling y recovers more failures than any perturbation of z we tested, and the performance gap widens as the test-time compute budget grows. Our approach, Gated Answer Resampling (GAR), pairs this resampling of the answer state with the model's own halting head and restarts only the puzzles that the head rejects. With at most 64 restarts per puzzle and no training or hyperparameter search, GAR takes TRM from 85.9% to 99.4% on Sudoku-Extreme and from 68.8% to 85.6% on Pencil Puzzle Bench validation. On the same checkpoints, GAR also outperforms Probabilistic TRM (PTRM), which perturbs z at each step, even when PTRM uses 42 to 197 times as much compute. Our code is available at https://github.com/MaximeILL/GAR.

0.40

Divergent-Convergent Reasoning: Scaling Test-Time Compute through Structured Solution Synthesis

cs.AI ·2026-08-15 ·Bo Wen, Yuhao Chen, Erhan Bilal, Carla Agurto Rios, Chen Wang +1 more
similarity 0.63
Abstract

Test-time compute can substantially improve Large Language Model (LLM) reasoning performance, yet how and when additional compute helps remains poorly understood. We study Divergent-Convergent Reasoning (DCR), a simple two-phase primitive consisting of an exploration phase that generates multiple candidate solutions followed by a convergent reconciliation phase. We present three core results. First, we show that even a single reconciliation step can reliably amplify correct minority reports: across datasets, DCR often recovers the correct answer when correct exploration outputs are in the minority, a regime where majority voting fails. Second, we introduce recursive DCR, an autoregressive reconciliation system that iteratively analyzes disagreements and allocates additional test-time compute. Recursive DCR achieves higher accuracy than fixed-compute baselines-reaching 93.3% on AIME 2024 and 92.0% on AIME 2025-while using roughly 27% less compute on average, demonstrating that attentive resource allocation is superior to uniform scaling. Third, we analyze disagreement among exploration outputs via a simple, training-free dispersion metric. Dispersion reveals a structured relationship between disagreement and test-time gains: in regimes where DCR is effective, higher disagreement among exploration outputs is associated with larger accuracy improvements from reconciliation. Together, these results show that disagreement, often viewed as noise, can be systematically exploited to improve test-time reasoning and reveal emerging scaling laws for agentic LLM systems.

0.04

When LLM Meets Tree Search: A Systematic View of Inference as Search in Large Language Models

cs.CL ·2026-08-31 ·Jiaqi Wei, Xiang Zhang, Yuejin Yang, Wenxuan Huang, Juntai Cao +8 more
top venuesurvey similarity 0.63
Abstract · Accepted by EMNLP'2026

As pretraining scaling laws approach saturation, Test-Time Scaling (TTS) has emerged as an important direction for improving reasoning by allocating inference-time compute to a fixed model prior. Viewed at a high level, TTS reframes inference as search over a space of partial reasoning states. While Chain-of-Thought (CoT) exposes intermediate steps, common instantiations rely on single-trajectory decoding, limiting recovery from early errors and exploration. This survey systematizes recent progress in tree-search-based reasoning, viewing inference as instance-specific optimization rather than decoding. We trace the evolution from uninformed search to Monte Carlo Tree Search (MCTS), highlighting how sampling-based control supports principled exploration-exploitation trade-offs. To unify a fragmented literature, we introduce a Unified Design Space spanning search topology, evaluation signals, and control dynamics, and advocate a standardized compute-reporting abstraction to make compute-accuracy trade-offs explicit and comparable.

0.41

More Correct Mass, Worse Answers: Why Power Sampling Can Fail and How to Fix It

cs.LG ·2026-08-14 ·Haohui Yang, Jiaxing Sun, Xiujun Ma
similarity 0.63
Abstract · 16 pages, 8 figures, 1 table. Haohui Yang and Jiaxing Sun contributed equally. Xiujun Ma is the corresponding author

Power Sampling sharpens a language model's distribution over complete generation trajectories, offering a verifier-free way to improve reasoning at inference time. It also has the potential to serve as a general-purpose front end for a broad range of downstream sampling methods. However, we uncover a striking paradox: Power Sampling can drive more probability mass toward correct trajectories while degrading the downstream inference it is intended to enhance. Using self-consistency as a representative case, we observe accuracy drops of up to 18.5 percentage points across models and reasoning benchmarks. We trace this paradox to two mismatches. Dose mismatch arises because a fixed exponent induces drastically different amounts of distributional change across problems. Coverage mismatch arises because global sharpening concentrates mass on a narrow set of dominant paths: high pass@k, often interpreted as evidence of preserved diversity, can therefore coexist with the loss of broad reasoning-path support required for downstream aggregation, search, and selection. Guided by this diagnosis, we replace uniform trajectory exponentiation with a deformation-controlled, support-preserving Power target that calibrates sharpening across problems while limiting the suppression of moderate-probability paths. In a same-budget instantiation with weighted self-consistency, the repaired sampler reverses the losses caused by global Power and outperforms standard multi-sample inference across reasoning benchmarks.

0.44

How Much Can Language Models Gain from Test-Time Computation?

cs.LG ·2026-10-01 ·Bangji Yang, Jingyuan Li, Jiajun Fan, Yi Evie Zhang, Ruihan Guo +6 more
benchmark similarity 0.62
Abstract · Corrected a typo in an author's name. No changes to the paper content

How much can test-time computation improve a language model, and at what cost? Test-time scaling is widely proposed as a substitute for larger models, but existing comparisons mostly evaluate one domain at a time and rarely charge selection to the budget. We introduce SELF-POT, a benchmark and evaluation framework that measures the test-time potential of a model across competition mathematics, competitive programming, and agentic workflows. SELF-POT separates candidate coverage from final accuracy on static tasks, tracks correctness transitions under revision, and measures protocol completion alongside task success in agentic environments. Under a unified budget rule, it compares Direct inference with parallel sampling and self-revision under fixed multiples of the Direct budget, and charges every model call, including selection and critique, in dollars. This design supports two kinds of comparison: the gain a model obtains from additional inference, and a lower-cost model with additional inference against a stronger model. Across five low-cost reasoning models on 350 sealed tasks, with Claude Opus 5.5 Direct as the reference, the returns depend on the domain, the selection rule, and failure handling. When we replay the retained programming candidate pools, public-example selection raises correct submissions from 376 to 453 of 500 scheduled cells while saving 12-49% of logical API cost across models, and simply retaining an available candidate when judging fails recovers 61 submissions at unchanged cost. On identical mathematics pools, judging with fallback yields 186 correct submissions versus 182 for voting, while voting saves 12-21% of logical API cost. These controlled replays show how selection and failure handling change the gains realized from the same generated candidates, and they quantify the marginal value of a model judge.

0.22