NeurIPS 2026 论文列表

Conference on Neural Information Processing Systems

录用类型

6,437篇论文

按官方录用论文列表统计,可能与会议公布的数字略有出入。

  • Oral
    991.5%
  • Spotlight
    2403.7%
  • Poster
    6,09894.7%

浏览全部论文

Scaling Optimization-Oriented Hypernetworks for Implicit Neural Representations

Lulu Cai, Hanxiang Ren, Siyan Dong, Li Sun, Jiefeng Wu, Youyi Zheng, Yi Ma, Yanchao Yang

展开摘要

We present a hypernetwork that generates the parameters of an implicit neural representation (INR) for a given signal in a single forward pass, without test-time optimization. Existing hypernetworks for this problem either ignore the chain-rule structure of the test-time optimization that produces an INR or, when they preserve it, instantiate the structure with MLPs whose parameter count grows quartically in target-network width. Our central contribution is to show that this parameter-count cost is structural to the MLP instantiation, not to the optimization-oriented principle of preserving chain-rule structure, and to resolve it by replacing the MLP body with attention. The resulting hypernetwork combines three design choices: an output-neuron-centric tokenization that aligns the token axis with each layer's output-neuron axis; an information-flow consistency rule that fixes the role of every cross-attention module from the representation its output should occupy; and a token-space iterative rollout that realizes the five quantities one optimization step on the target INR computes as five cross-attention modules with parameter count independent of target-network width. Across five 2D and 3D INR generation benchmarks, our method outperforms the state-of-the-art single-pass and optimization-oriented baselines; scales to target-network widths at which the MLP-based optimization-oriented paradigm exhausts GPU memory; and produces the highest result on NeRF generation without ground-truth INR weights supervision.

Poster
Scaling Neural Motor Decoding via Decoupled Behavioral Pretraining

Divyansha ., Vinam Arora, Shivashriganesh P. Mahato, Alexandre Andre, Eva L Dyer

展开摘要

Recent neural decoding approaches achieve strong performance by training on large collections of paired neural-behavioral recordings, but such datasets are expensive, invasive, and difficult to scale. In contrast, behavioral data is abundant and easy to collect, raising the question of whether neural decoding can benefit from decoupling behavioral and neural representation learning. We introduce BeeMO, a flexible multi-session framework that enables training with arbitrary mixtures of paired neural-behavioral recordings and unpaired behavioral data. A behavior decoder learns movement dynamics directly from behavioral trajectories, while neural activity is incorporated through cross-attention layers when available, allowing behavioral and neural supervision to scale independently. By decoupling neural and behavioral data, we unlock a new dimension for scaling: unpaired behavioral data, which is substantially cheaper and easier to collect than paired neural recordings, can be used directly to improve decoding performance. Across multiple intracortical motor datasets and tasks in nonhuman primates, we show that incorporating unpaired behavioral data consistently improves decoding performance, particularly, and that incorporating task-aligned behavioral trajectories can further improve transfer. We further show that behavior-only pretraining, without any neural pretraining, outperforms single-session supervised baselines and is comparable to models pretrained on substantially larger neural datasets. Together, our results suggest that scaling behavioral data offers a practical and cost-effective path toward neural decoding models that generalizes across subjects and tasks.

Poster
Scaling Linear Mode Connectivity and Merging to Billion Parameter Pretrained Transformers

TIANYI LI, Zhiqiang Shen

展开摘要

Linear mode connectivity (LMC) provides a promising foundation for understanding and merging independently trained neural networks, but existing methods typically optimize the interpolation path from only one model endpoint, limiting their scalability and effectiveness for large pretrained transformers. We propose a novel and scalable framework for enabling LMC-based model merging to {\em billion-parameter pretrained transformers}. Our method applies properly parameterized functionality-preserving weight transformations to align functionally equivalent solutions, and introduces a dual learning procedure in which both models jointly learn their corresponding transformations toward a shared linear interpolation path. This bidirectional optimization substantially reduces interpolation barriers and enables more reliable merging across large-scale architectures. Empirically, we show that our approach achieves near-zero loss barriers on WikiText for language models with medium-sized parameters, representing, to our knowledge, the first demonstration of near-barrier-free linear connectivity at this scale. In the vision domain, ViT-L maintains above 69\% ImageNet top-1 accuracy throughout the interpolation path, while modern billion-parameter LLMs exhibit only small loss barriers. These results suggest that properly resolving parameter symmetries enables large pretrained Transformers to be connected and merged through simple linear paths with substantially improved interpolation performance.

Poster
Scaling Laws for SAE Training Data

Nikita Koryagin, Nikita Balagansky, Daniil Gavrilov

展开摘要

Sparse autoencoder (SAE) training is often bottlenecked by activation storage. We show that the stored activation buffer can be far smaller than the total SAE training budget: quality depends mainly on the number of \emph{unique} activations, not on whether every training token is fresh. After a short diversity-limited regime, additional fresh activations provide little benefit; replaying the same buffer preserves both reconstruction and interpretability performance. We capture this diversity--repetition tradeoff with a data-constrained scaling law and validate it across dictionary sizes, token budgets, Llama-3.1 and Qwen3 models, early/middle/late layers, BatchTopK/TopK/JumpReLU SAEs, and downstream metrics including EV, reconstruction MSE, feature absorption, automated interpretability, and sparse probing. The resulting buffer-sizing rule is simple: choose the smallest activation buffer that reaches the quality plateau, then use replay to spend the remaining training budget. In our experiments, this reduces activation storage by $8\text{--}64\times$ with negligible quality loss.

Poster
Scaling Laws and Tradeoffs in Recurrent Networks of Expressive Neurons

Aaron Spieler, Georg Martius, Anna Levina

展开摘要

Cortical neurons are complex, multi-timescale processors wired into recurrent circuits, shaped by long evolutionary pressure under stringent biological constraints. Mainstream machine learning, by contrast, predominantly builds models from extremely simple units, a default inherited from early neural-network theory. We treat this as a normative architectural question. How should one split a fixed parameter budget $P$ between the number of units $N$, per-unit effective complexity $k_e$, and per-unit connectivity $k_c$? What controls the optimal allocation? This calls for a model in which per-unit complexity can be tuned independently of width and connectivity. Accordingly, we introduce the ELM Network, whose recurrent layer is built from Expressive Leaky Memory (ELM) neurons, chosen to mirror functional components of cortical neurons: multi-timescale memory, structured synaptic integration, and nonlinear internal computation. The architecture allows for individually adjusting $N$, $k_e$, and $k_c$ and trains stably across orders of magnitude in scale. We evaluate the model on two qualitatively different sequence benchmarks: the neuromorphic SHD-Adding task and Enwik8 character-level language modeling. Performance improves monotonically along each of the three axes individually. Under a fixed budget, a clear non-trivial optimum emerges in their tradeoff, and larger budgets favor both more *and* more complex neurons. A closed-form information-theoretic model captures these tradeoffs and attributes the diminishing returns at two ends to: per-neuron signal-to-noise saturation and across-neuron redundancy. Connectivity enters as a related mechanism that helps neurons learn distinct signals. A hyperparameter sweep spanning three orders of magnitude in trainable parameters traces a near-Pareto-frontier scaling law consistent with the framework, mapping the budget-constrained tradeoff surface between unit count, unit complexity, and connectivity. This suggests that the simple-unit default in ML is not obviously optimal once this surface is probed, and offers a normative lens on cortex's reliance on complex spatio-temporal integrators.

Poster
Scaling Genomic Language Modeling with Unified Corpus and Evaluation in Bacteria

Maciej Wiatrak, Samuel T Horsfield, Aaron Weimann, Ramon Viñas Torné, Maria Ntemourtsidou, David Abelson, Adam Dinan, John Lees, Maria Brbic, Andres Floto

展开摘要

Progress in genomic language modeling depends on pretraining resources that are both diverse and comprehensive, as well as benchmarks that evaluate models across biological scales from genes to whole genomes. This need is especially acute in bacteria, which are extremely abundant, diverse, and central to human health, ecology, and biotechnology. Yet resources for large-scale pretraining and evaluation in bacterial genomics remain limited, with existing frameworks focusing largely on eukaryotic settings. Here, we introduce BacCorpus, a genome-level resource for training genomic LMs comprising 20B proteins, including 4.6B unique sequences, from 7M genomes spanning more than 150,000 species, and BacBench, a comprehensive benchmark spanning 10 datasets and 5 tasks across gene-, system-, and genome-level tasks. We evaluate a diverse suite of genomic LMs on BacBench and additionally develop BacLM, a 350M-parameter model trained jointly on protein sequences and intergenic DNA to further investigate how bacterial genomes are best represented. Across tasks, we find that performance depends strongly on biological scale: methods leveraging protein sequence are competitive on gene-level prediction, whereas models that incorporate wider genomic context excel at problems which involve complex multi-gene interactions. Together, BacCorpus and BacBench provide a practical foundation for training and evaluating robust, genome-aware genomic language models in bacteria at an unprecedented scale.

Spotlight
Scaling Arbitrary Architectures and Optimizers with Automatic Parameterization

Shikai Qiu, Charlie Chen, Andres Potapczynski, Martin Marek, Andrew Wilson

展开摘要

Training neural networks at scale requires careful per-layer scaling of initialization, learning rate, and other optimizer hyperparameters, with the right rules depending jointly on the architecture, the optimizer, and which axis (width $D$, depth $L$, batch size $B$, etc.) is being scaled. Current practice is to derive each rule by hand, as in $\mu$P for width, CompleteP for depth, SDE-based and EMA-timescale arguments for batch size, and tailored prescriptions for matrix-preconditioned optimizers; as architectures, optimizers, and scaling axes continue to evolve, this hand derivation is increasingly a bottleneck to combining these advances at scale. We show that these derivations can be systematized by solving a linear system over hyperparameter exponents to satisfy the scaling constraints imposed by each primitive instruction of the training program, analogous to dimensional analysis in physics that enforces matched units on both sides of an equation. We develop \emph{automatic parameterization} (AutoP), a system that reads these rules off a traced training program and solves the resulting system to assign a scaling exponent to every hyperparameter, and provide a concrete JAX implementation. From a few primitive rules, AutoP recovers $\mu$P for width on Transformers, Monarch-structured Transformers, mixture-of-experts, and ResNets under Adam, SignSGD, Muon, and AdaMuon; CompleteP for depth; and the known batch-size prescriptions for the learning rate and AdamW weight decay. It also identifies new rules for the recurrence count in looped transformers, the context length in linear-attention and MLP-Mixer models, and the batch-size scaling for Muon's learning rate, all of which we demonstrate as empirically beneficial. Analogous to automatic differentiation, our results suggest that robust hyperparameter scaling rules can be automated, freeing practitioners to scale up new architectures and optimizers without rederiving the underlying theory or risking subtle errors that quietly cost compute at scale.

Poster
Scale Where It Matters: Training-Free Localized Scaling for Diffusion Models

Qin Ren, Yufei Wang, Lanqing Guo, Wen Zhang, Zhiwen Fan, Chenyu You

展开摘要

Diffusion models have become the dominant paradigm in text-to-image generation, and test-time scaling (TTS) improves sample quality by allocating additional computation at inference. Existing TTS methods, however, resample the entire image, while generation quality is often spatially heterogeneous. This leads to unnecessary computation on regions that are already correct, and localized defects remain insufficiently corrected. In this paper, we explore a new direction -- Localized TTS -- that adaptively resamples defective regions while preserving high-quality regions, thereby substantially reducing the search space. This raises two challenges: accurately localizing defects and maintaining global consistency. We propose $\textbf{LoTTS}$, the first fully training-free framework for localized TTS. For defect localization, LoTTS contrasts cross-/self-attention signals under quality-aware prompts (e.g., ''high-quality'' vs. ''low-quality'') to identify defective regions, and then refines them into coherent masks. For consistency, LoTTS perturbs only defective regions and denoises them locally, ensuring that corrections remain confined while the rest of the image remains undisturbed. Extensive experiments on SD2.1, SDXL, and FLUX demonstrate that LoTTS achieves state-of-the-art performance:~it consistently improves both local quality and global fidelity, while reducing GPU cost by $2$-$4\times$ compared to Best-of-$N$ sampling. These findings establish localized TTS as a promising new direction for scaling diffusion models at inference time.

Poster
SWE-Crafter: Scaling Executable Multilingual Software Engineering Data with Meta-Skill Agents

Shukai Liu, Jian Yang, Bo Jiang, Junhang Cheng, Haowen Wang, Xiao-Hui Li, Xianglong Liu

展开摘要

Software-engineering agents are increasingly expected to solve realistic repository-level tasks, but their training remains constrained by the limited availability of executable supervision beyond Python-centric repositories. Building such data across programming languages is difficult: repositories use different build systems, dependency managers, runtime assumptions, test interfaces, and failure modes, so separate language-specific pipelines are costly to reproduce and extend. We introduce SWE-Crafter, a unified agent-based framework for constructing executable multilingual SWE instances. SWE-Crafter keeps candidate mining, environment synthesis, fail-to-pass validation, and trajectory distillation in a shared pipeline, while language-specific construction knowledge is supplied through extensible skills induced from repository-level experience. These skills guide repository exploration and test-command synthesis while preserving repository-local evidence from documentation, manifests, CI files, and execution feedback as the final source of truth. Applying SWE-Crafter to eight programming languages yields 50,926 validated instances from 9,296 repositories and 68,851 distilled test-passing trajectories. Supervised fine-tuning on this resource produces SWE-Crafter-40B, which achieves 61.0% on SWE-bench Multilingual and 77.2% on SWE-bench Verified, showing that skill-guided construction provides scalable multilingual supervision for repository-level SWE agents.

Poster
SETA: Scaling Environments for Terminal Agents

Qijia Shen, Zhiqi Huang, Vamsidhar Kamanuru, Aznaur Aliev, Jay Rainton, Ahmed Awelkair, Boyuan Ma, Qizheng Zhang, Jiwei Fu, Yuzhen Mao, Wendong Fan, Ping Nie, Philip Torr, Bernard Ghanem, Changran Hu, Jonathan Li, Urmish Thakker, Guohao Li

展开摘要

Large language models (LLMs) are rapidly shifting toward agents that solve tasks through diverse interfaces, including web and graphical user interfaces (GUIs). Among these, the terminal command line provides a text-based, general-purpose interface, covering tasks from system operations to data science and machine learning. However, scaling terminal-agent training remains challenging, as it requires diverse and coherent task instructions, executable environments, and reliable verification, while lacking naturally grounded supervision data. In this work, we propose SETA, a scalable framework for generating verifiable terminal environments for reinforcement learning (RL). The framework consists of two pipelines sharing a unified verification mechanism: SETA-Synth converts diverse sources into standardized RL environments, and SETA-Evol further expands from existing environments with adaptive control of difficulty and diversity. Together, we construct and release SETA-Env, the largest open-source verifiable terminal RL dataset to date, containing over $4{,}500$ environments. We evaluate our dataset by training a Qwen3-8B model with GRPO on SETA-Env, achieving $12$\% pass rate on Terminal-Bench 2.0, the best reported result for an RL-trained model at the 8B scale. The results demonstrate that SETA-Env provides high-quality training environments for terminal agents and serves as a valuable resource for advancing research on terminal-based agent learning.

Poster
SDS-LoRA: Overcoming Anisotropic Gradient Scaling in Low-Rank Adaptation

Junghun Oh, Sungyong Baik, Kyoung Mu Lee

展开摘要

Low-Rank Adaptation (LoRA) enables efficient adaptation of large pre-trained models to downstream tasks by parameterizing weight updates with low-rank matrices. In this paper, we investigate the limitations of the LoRA parameterization from a geometric perspective. Specifically, we show that when a full fine-tuning gradient is backpropagated to the low-rank matrices, it undergoes anisotropic scaling driven by their singular values. We argue that this phenomenon is undesirable because it distorts the full fine-tuning gradient by skewing it toward dominant singular directions while suppressing others. Our analyses demonstrate that anisotropic gradient scaling reduces the effective rank of the low-rank matrices' gradients and results in suboptimal alignment between the full fine-tuning gradient and its low-rank approximation in LoRA, thereby exacerbating the gap to full fine-tuning. To address these limitations, we propose a new low-rank parameterization, SDS-LoRA, which structurally decouples singular values from the backward pass. Our method ensures that the full fine-tuning gradient backpropagates only through the orthonormal bases of the low-rank matrices' subspaces, independent of their scales. Convergence analysis demonstrates that while LoRA’s convergence rate degrades with the condition number of the low-rank matrices, SDS-LoRA remains independent of it. Experimental results across natural language and vision benchmarks show that SDS-LoRA improves loss convergence and reduces the gap to full fine-tuning, significantly enhancing adaptation performance.

Poster
Rethinking Language Model Scaling under Transferable Hypersphere Optimization

Liliang Ren, Yang Liu, Yelong Shen, Weizhu Chen

展开摘要

Scaling laws for large language models depend critically on the optimizer and parameterization. Existing hyperparameter transfer laws are mainly developed for first-order optimizers, and they do not structurally prevent training instability at scale. Recent hypersphere optimization methods constrain weight matrices to a fixed-norm hypersphere, offering a promising alternative for more stable scaling. We introduce HyperP (Hypersphere Parameterization), the first framework for transferring optimal learning rates across model width, depth, training tokens, and Mixture-of-Experts (MoE) granularity under the Frobenius-sphere constraint with the Muon optimizer. We prove that weight decay is a first-order no-op on the Frobenius sphere, show that Depth-$\mu$P remains necessary, and find that the optimal learning rate follows the same data-scaling power law with the ``magic exponent'' 0.32 previously observed for AdamW. A single base learning rate tuned at the smallest scale transfers across all compute budgets under HyperP, yielding $1.58\times$ compute efficiency over a strong Muon baseline at $6\times10^{21}$ FLOPs. Moreover, HyperP delivers transferable stability: all monitored instability indicators, including $Z$-values, output RMS, and activation outliers, remain bounded and non-increasing under training FLOPs scaling. We also propose SqrtGate, an MoE gating mechanism derived from the hypersphere constraint that preserves output RMS across MoE granularities for improved granularity scaling, and show that hypersphere optimization enables substantially larger auxiliary load-balancing weights, yielding both strong performance and good expert balance.

Poster
Reinforce Adjoint Matching: Scaling RL Post-Training of Diffusion and Flow Models

Andreas Bergmeister, Stefanie Jegelka, Nikolas Nüsken, Carles Domingo i Enrich, Jakiw Pidstrigach

展开摘要

Diffusion and flow-matching models scale because pretraining simply regresses against a closed-form target built by analytically noising clean data samples. In many settings, only a reward function is available, scoring how desirable a generation is, so training must proceed online from a pretrained model. Existing methods either rely on costly SDE rollouts, sometimes with reward gradients, or adopt heuristic reward-dependent variants of the pretraining objective. Under a stochastic optimal control formulation of KL-regularized reward maximization, the optimal generative process tilts only the clean-endpoint distribution and leaves the conditional noising law unchanged. Combining this path-space characterization with the adjoint-matching optimality condition and a REINFORCE estimator to avoid reward gradients, we derive Reinforce Adjoint Matching (RAM). At each step, we draw a clean endpoint from the current model with any off-the-shelf sampler, evaluate its reward, noise it to several training states, and regress against a closed-form, reward-weighted target. Like the pretraining objective, RAM is simple and scales. On Stable Diffusion 3.5M, RAM achieves the highest reward on composability, text rendering, and human preference. It is much more training efficient, reaching Flow-GRPO's peak GenEval accuracy in~$50\times$ fewer training steps.

Poster
Reference-Guided Training: Adaptive Gradient Scaling via Per-Sample Loss Comparisons

Israel Rodrigues Soares, Pedro Benedetti, Thanda Shwe, Israel Mendonca, Masayoshi Aritsugi

展开摘要

Empirical Risk Minimization treats training samples uniformly, which can degrade performance in noisy or heterogeneous settings. We introduce a reference-guided objective that uses per-sample error comparisons with a fixed reference model to reweight gradient contributions without relying on prediction imitation, while preserving gradient direction and ensuring bounded scaling. Theoretical analysis shows that the formulation induces adaptive weighting with controlled amplification. Experiments on image classification with synthetic label noise and on time-series forecasting demonstrate broad improvements across architectures, particularly in moderate-to-high noise and heterogeneous regimes. Results further indicate that the method is most effective when the error-ranking alignment between the baseline model and the reference model is low, suggesting that gains arise primarily from the diversity of the reference error ranking relative to the learner, rather than the reference's absolute performance.

Oral
Reasoning Warm-up: Scaling Label-free RL via Verifiable Surrogate Rewards

Jun Nie, Bo Han, Jiaqi Fan, Yonggang Zhang, Xinmei Tian, Dahai Yu, Michael Ng

展开摘要

Improving the reasoning ability of large language models (LLMs) without ground-truth supervision remains a central challenge in reinforcement learning (RL). Recent label-free RL methods typically rely on internal pseudo-rewards such as self-consistency or majority voting. However, for complex multi-step reasoning, these signals can be systematically misleading: models may repeatedly produce mutually consistent but incorrect trajectories, causing optimization to favor frequency over correctness. In this work, we propose reasoning warm-up reinforcement learning, a label-free RL framework motivated by an empirical phenomenon we call **Reasoning Warm-up**. We observe that when a model successfully completes a deterministic auxiliary task with an exact verifier, its success probability on a subsequent complex reasoning task increases substantially. This coupling suggests that auxiliary-task verification can serve as a useful surrogate signal for selecting and optimizing reasoning trajectories even when the main task itself is not directly verifiable. Based on this observation, we incorporate verifiable auxiliary tasks into both generation and optimization. During generation, the auxiliary task provides verifiable warm-up prefix; during training, its verification outcome is used to score candidate trajectories for policy optimization. Experiments on multiple benchmarks demonstrate the effectiveness of our method.

Poster
Random Attention Pattern Learning Enables Emergent Capabilities

Vatsal Baherwani, Charlie Chen, Shikai Qiu, Andrew Wilson, Pavel Izmailov

展开摘要

Neural scaling laws for transformer language models predict smooth improvements in pretraining loss with increasing parameters, but downstream capabilities such as in-context learning are known to emerge abruptly past a certain model scale. In this paper, we show that emergent capabilities arise at variable intervals throughout training, with larger models acquiring capabilities earlier on average. We demonstrate that the emergence of capabilities such as pattern completion and indirect object identification corresponds to the abrupt learning of task-relevant attention patterns. To isolate this phenomenon, we train transformer models on synthetic linear map and cellular automata datasets, and we show that the difficulty of learning attention patterns depends on context length and pattern sparsity. Moreover, scaling the number of attention heads improves learning efficiency on our synthetic tasks, while increasing the head dimension yields diminishing returns past a minimum capacity. We additionally investigate architectures with alternative attention mechanisms, showing that MLP-Mixer outperforms a transformer on linear map tasks with complex attention patterns. Our findings provide a mechanistic insight into emergence, showing that downstream capabilities arise abruptly due to the intrinsic difficulty of learning sparse attention patterns in transformer models.

Poster
RaZeR: Pushing the Limits of NVFP4 Quantization with Redundant Zero Remapping

Yuzong Chen, Xilai Dai, Jake Hyun, Chi-Chih Chang, Wonsuk Jang, Yuheng Wu, Thierry Tambe, Jae-Sun Seo, Mohamed Abdelfattah

展开摘要

The recently introduced 4-bit floating-point format, NVFP4, demonstrates remarkable performance and memory benefits for quantized large language model (LLM) inference. However, we observe two types of redundancy in the existing NVFP4 encoding: (1) The FP4 format naturally exposes an unused quantization value due to its sign-magnitude representation that contains both positive and negative zeros. (2) The FP8 block scaling factor, with 4-bit exponent and 3-bit mantissa, contains an unused sign bit given that the scaling factor is always positive. Additionally, we find that LLM weights are more tolerant to a lower-precision block scaling factor, such as 6 bits with 3-bit exponent and 3-bit mantissa. Based on these observations, we propose **R**edund**a**nt **Ze**ro **R**emapping (RaZeR), an enhanced numerical format that pushes the limits of NVFP4 for more accurate LLM quantization under the same memory footprint. RaZeR leverages the unused bits in the block scaling factor to adaptively remap the negative FP4 zero to a set of pre-defined special values, which maximally utilizes the NVFP4 encoding and better fits the LLM tensor distribution. Extensive experiments validate RaZeR’s superior performance for 4-bit LLM quantization. For example, RaZeR reduces the average perplexity loss of NVFP4 by 29.4% and 32.3% under weight-only and weight-activation quantization, respectively.

Poster
Provable Test-Time Scaling for Beam Search in LLM Reasoning

Qijia He, Yu Huang, Yuan Cheng, Yuxin Chen, Yingbin Liang

展开摘要

Beam-search–based test-time methods provide an effective way to improve large language model (LLM) performance on long-horizon generation by pruning invalid reasoning paths early, leading to significantly improved reasoning efficiency and more favorable test-time cost scaling. Despite strong empirical success, the theoretical understanding of beam search remains limited. In this paper, we study the test-time compute guarantee of the commonly used beam search framework that uses the model's internal log-likelihood for intermediate scoring, while relying on an external reward model only after a complete response is generated. We first establish a lower bound for vanilla beam search, showing that at least $\Omega(C^\star(x)^2)$ samples are required for the optimal response to survive, where $C^\star(x)$ is the token-level coverage coefficient for prompt $x$. This motivates our modified confidence-filtered beam search (CF-Beam), which provably reduces the sample size by a factor of $C^\star(x)$. We then show that the regret of CF-Beam is upper-bounded by the probability of rare failure events and the reward estimation error scaled by a path-level coverage coefficient, where the rare-failure term vanishes as per-step sampling increases. Our results highlight a fundamental advantage of beam search over sequence-level inference methods such as Best-of-N and Best-of-Majority. While the guarantees of these approaches typically involve coverage coefficients that grow exponentially with the horizon $L$, CF-Beam controls the dominant search-induced term through a token-level coverage coefficient that scales polynomially with $L$. Our numerical experiments further confirm that beam search is more robust on hard instances and under increasing reasoning horizons.

Poster
Problem-Dependent Dynamic Regret over a Predictor Class with One-Gradient Feedback

Wentao Zhang

展开摘要

Many online learning systems now have access to several gradient predictors at once, such as simulators, replay buffers, neural surrogates, or time-series forecasters, and the quality of these predictors varies from round to round. We study online convex optimization under one-gradient feedback against an arbitrary moving comparator, with a user-supplied finite class $\Pi$ of gradient-field predictors, and ask whether a single algorithm can compete with the best predictor in $\Pi$ at a logarithmic cost, fall back to a small-loss bound when none of the predictors is useful, and still retain a path-length-adaptive worst-case guarantee when the predictors are adversarial. We give a positive answer through PH-Sword (Predictable-Hybrid Sword.optimism), which combines an exp-concave Hedge over $\Pi$, optimistic projected-gradient base learners on a geometric learning-rate grid, and a correction-term optimistic-entropy meta learner with prediction-error doubling. For any comparator sequence $\boldsymbol u$, PH-Sword attains dynamic regret $\widetilde O\bigl(R\_0\sqrt{(1+P\_T/D)(1+P\_T/D+\min\{\mathcal E\_\*/G^2,\,2LF\_T(\boldsymbol u)/G^2\}+\log|\Pi|)}\bigr)$ up to logarithmic factors, where $R\_0=DG+LD^2$, $P\_T$ is the path length, $F\_T(\boldsymbol u)$ the cumulative comparator loss, and $\mathcal E\_\*$ the best-in-class field error. The bound merges the field-controlled, small-loss, and worst-case regimes into one deterministic guarantee that improves over prior one-gradient dynamic-regret algorithms. On six controlled benchmarks the five predicted scaling laws hold simultaneously: PH-Sword reaches 17% of OGD's final dynamic regret and 54% of Ader's on a slow-drift benchmark, and we observe that a single noisy predictor without model selection can actually do worse than using no predictor at all.

Poster
Predicting and improving test-time scaling laws via reward tail-guided search

Muheng Li, Jian Qian, Wenlong Mou

展开摘要

Test-time scaling has emerged as a critical avenue for enhancing the reasoning capabilities of Large Language Models (LLMs). Though the straight-forward ``best-of-$N$'' (BoN) strategy has already demonstrated significant improvements in performance, it lacks principled guidance on the choice of $N$, budget allocation, and multi-stage decision-making, thereby leaving substantial room for optimization. While many works have explored such optimization, rigorous theoretical guarantees remain limited. In this work, we propose new methodologies to predict and improve scaling properties via tail-guided search. By estimating the tail distribution of rewards, our method predicts the scaling law of LLMs without the need for exhaustive evaluations. Leveraging this prediction tool, we introduce Scaling-Law Guided (SLG) Search, a new test-time algorithm that dynamically allocates compute to identify and exploit intermediate states with the highest predicted potential. We theoretically show that SLG approaches a full-information oracle at a reduced scale and, under additional regularity conditions, achieves vanishing matched-budget regret; in a Gaussian two-stage model, SLG can also match BoN with a polynomially larger sampling budget. Empirically, we validate our framework across different LLMs and reward models, confirming that tail-guided allocation consistently achieves higher reward yields than Best-of-$N$ under identical compute budgets.

Poster