NeurIPS 2026 论文列表

Reinforcement Learning with Verifiable Rewards (RLVR) has emerged as a key method for improving Large Language Models' reasoning capabilities, yet recent evidence suggests it may paradoxically shrink the reasoning boundary rather than expand it. This paper explains this shrinkage issue of RLVR by analyzing its learning dynamics and reveals two critical phenomena that account for this failure. First, we expose negative interference in RLVR, where learning to solve certain training problems actively reduces the likelihood of correct solutions for others, leading to the decline of Pass@$k$ performance, or the probability of generating a correct solution within $k$ attempts. Second, we uncover the winner-take-all phenomenon: RLVR disproportionately reinforces problems with high likelihood, correct solutions under the base model, while suppressing other initially low-likelihood ones. Through extensive theoretical and empirical analysis on multiple mathematical reasoning benchmarks, we show that this effect arises from the inherent on-policy sampling in standard RL objectives, causing the model to converge toward narrow solution strategies. These insights motivate us to design a \textit{simple yet effective} data curation algorithm that focuses RLVR learning on low-likelihood problems (the non-winners) and achieves notable improvement in Pass@$k$ performance, illustrating the potential of a broader class of data-curation mitigation strategies.

Sparse Autoencoders (SAEs) that can accurately reconstruct their input (minimizing distortion) by making efficient use of few features (minimizing the rate) often fail to learn monosemantic representations (highly interpretable), limiting their usefulness for mechanistic interpretability. In this paper, we characterise this tension in learning faithful, efficient, and interpretable explanations, introducing the Rate-Distortion-Polysemanticity tradeoff in SAEs. Under toy-modeling assumptions, we theoretically and empirically show that restricting the SAE to be monosemantic necessarily comes with an increase in rate and distortion. Assuming a generative model behind the input observations, we further demonstrate that the degree of polysemanticity of optimal SAEs is determined by the training data distribution, especially by the probability of features to co-occur. Finally, we extend the analysis to real-world settings by deriving necessary conditions that a polysemanticity measure should satisfy when the data-generating process is unknown, and we benchmark existing proxy metrics on SAEs trained on Large Language Models. Taken together, our findings show that polysemanticity is a data problem that should be accounted for when addressing it at the architectural and optimization level.

Recent text-to-image diffusion models (T2I DMs) depend on vast, uncurated datasets that often include copyrighted artworks and personal images, risking the generation of unwanted content. While concept erasure methods have emerged to suppress such outputs, they predominantly rely on text prompts, limiting their effectiveness for visually nuanced or ineffable styles that are difficult to articulate verbally. To bridge this gap, we propose Quiet Prompt (QuP), a reference-based concept erasure method that identifies complex concepts using fewer than ten reference images. QuP operates in two stages: (1) Concept Embedding Generation (CEG), which captures the intricate visual morphology of an unwanted concept into a single latent embedding; and (2) Concept leakage-aware Negative Guidance (CNG), which utilizes this embedding as a negative semantic condition to steer the diffusion process. In addition, to overcome the limitations of conventional fixed-scale negative guidance (negative prompting)—which often suffers from structural distortion and unintended content loss—we introduce concept leakage-aware negative guidance scale $n_g(t)$. This mechanism adaptively modulates the guidance strength at each denoising step based on a semantic measurement of concept leakage between the intermediate generated image and the target concept in a joint embedding space. Extensive evaluations on idiosyncratic art styles and object erasure tasks demonstrate that QuP achieves superior concept suppression and content preservation, outperforming state-of-the-art text-based baselines in both image fidelity and erasure precision. The source code will be publicly provided to ensure reproducibility of our work.

We analyze the query complexity of finding a local minimum in $t$ rounds on general graphs. More precisely, given a graph $G = (V,E)$ and oracle access to an unknown function $f : V \to \mathbb{R}$, the goal is to find a local minimum---a vertex $v$ such that $f(v) \leq f(u)$ for all $(u,v) \in E$---using at most $t$ rounds of interaction with the oracle. The query complexity is well understood on grids, but much less is known beyond. This abstract problem captures many optimization tasks, such as finding a local minimum of a loss function during neural network training. For each graph with $n \geq 2$ vertices and constant integer $t \geq 2$, we prove a deterministic upper bound of $O(n^{1/t} (s\Delta)^{1-1/t})$, where $s$ is the separation number and $\Delta$ is the maximum degree of the graph. We complement this result with a randomized lower bound of $\Omega(n^{1/t})$ that holds for any connected graph. We also find that parallel steepest descent with a warm start provides improved bounds for graphs with high separation number and bounded degree. To obtain our results, we utilized an advanced version of Gemini at various stages of our research. We discuss our experience in the Methodology section.

Large-scale transformer training and deployment are increasingly constrained by the transfer of activations, gradients, and optimizer states across accelerators. Low-bit quantization offers a natural remedy, but transformer activations are often heavy-tailed and outlier-dominated, making simple quantization highly lossy. We show that this difficulty is not only a property of the quantizer, but also of the architecture. Specifically, residual connections can drive transformer activations away from Gaussianity during training. Using controlled comparisons between residual and residual-free transformers, we demonstrate that this effect leads to substantially higher quantization error and accuracy degradation at low precision in residual models. We explain the phenomenon through an excess kurtosis analysis, showing that residual mixing can amplify non-Gaussianity, whereas dense mixing in residual-free contracts non-Gaussianity. We then show that residual-free transformers can be made trainable using orthogonal initialization, spectral or second-order optimization, and depth-aware scaling of attention temperature. In language tasks, while there is a small drop in full precision performance, these models retain near-Gaussian activations and exhibit significantly improved robustness to low-bit quantization. Our results identify an accuracy-compressibility trade-off in transformer design and motivate architecture-level approaches to quantization-friendly foundation models.

We study classification and regression tasks under label differential privacy (label-DP), a setting where only the labels are considered sensitive information. We quantify the "price of locality" by revealing fundamental statistical gaps between local and central privacy models. For classification, we establish a strict separation in accuracy. Specifically, we prove that the minimax excess risk in the local model is lower bounded by $\Omega(\frac{1}{\epsilon}\sqrt{\text{VC}(\mathcal{H})/n})$ for classification on size-$n$ dataset, a fundamental limitation that holds even under relaxed approximate $(\epsilon, \delta)$-local DP. Overcoming this barrier, we propose the first *efficient* central-model algorithm that operates under the stricter pure $\epsilon$-DP, yet achieves a significantly improved upper bound of $\tilde{O}(\sqrt{\text{VC}(\mathcal{H})/(\epsilon n)})$. For linear regression, we show that local randomizers or naive central-DP approach algorithms are statistically inefficient. Instead, we turn to the Matrix Mechanism and use an encoder-decoder framework built on ridge regression, which projects the data into a spherical latent space before injecting noise. This structural design effectively isolates and exponentially suppresses the severe noise inflation typically caused by ill-conditioned feature covariance matrices in full-DP (Cai et al., The Annals of Statistics, 49(5)), achieving an optimal privacy penalty of $\tilde{O}({d^2}/({n^2\epsilon^2}))$ where $d$ is the feature dimension.

In-context learning is usually analyzed as if the examples in the prompt were sampled before the learner is chosen. In deployed systems they are not: examples are retrieved, filtered, re-ranked, edited, and repeatedly tested after seeing the query and the data store. We formalize this gap by treating prompt construction as adaptive data analysis through a conditional stochastic-kernel calculus. Our main quantity is the \emph{context capacity}, the mutual information or approximate max-information between the data store and the final prompt transcript. For any frozen in-context learner and any adaptive context pipeline with capacity $\kappa$, we prove a finite-sample context generalization bound of order $\sqrt{\kappa/k}$, where $k$ is the number of examples that enter the prompt. We strengthen it to a sub-gamma transport inequality with Bernstein curvature, prove a matching lower bound, and derive two PAC-Bayesian retrieval rules: a first-order Gibbs rule and a self-normalized second-order rule. Finally, we instantiate the theory for Bayesian linear in-context regression, including an order-statistics analysis of query-aligned top-$k$ Gaussian retrieval. The results separate context quality from context certification: longer or more relevant contexts improve risk only when the procedure used to choose them is stable enough for selected-context evidence to transfer.

With the rapid development of Vision-Language Models (VLMs), it is increasingly critical to evaluate their ability in accurate and robust reasoning based solely on visual information. However, existing video understanding benchmarks often overlook the deep cognitive processes inherent in visual reasoning and frequently rely on multiple-choice formats, implicitly encouraging reasoning shortcuts. To address these limitations, we introduce \emph{The Prestige}, a novel video understanding benchmark designed to isolate VLM reasoning under deliberate cognitive misdirection through professional magic performances. The dataset consists of a curated collection of high-quality magic videos paired with a diverse distribution of strictly open-ended questions targeting causal state tracking, paradoxical reasoning, and resistance to adversarial questions. These questions need the models to perform long-horizon, multi-step commonsense reasoning with cognition. Through extensive evaluations of leading open-weight and proprietary VLMs, using a combination of machine and human grading, we find a substantial gap between model and human performance. \emph{The Prestige} establishes a rigorous new frontier for evaluating temporal, causal, and cognitive-flow reasoning in multimodal foundation models.

In this paper, we introduce a semi-random model in online optimization, which interpolates naturally between the standard (adversarial) and random-order arrival model, which we call the online with a random sample (ORS) model: the full input may be chosen adversarially, but a random $p$-fraction of the input is selected and presented to the algorithm in random-order, before the remaining non-sampled elements are presented (in adversarial order). While similar in spirit to the AOS (adversarial order with a sample) model introduced by Kaplan, Naori and Raz, in our ORS model, the sampled $p$-fraction is revealed online instead of offline, and hence, competitiveness is measured with respect to the full input. Our central focus in the paper is applying the ORS model to the secretary problem and its natural $(k,1)$ variant. For the secretary problem, we present an optimal $pe^{-p}$-competitive algorithm, while for the $(k,1)$-secretary problem, we obtain a competitive algorithm whose performance converges to optimal competitiveness as $p\rightarrow 1$. We also include a $O(\log (1/p))$-competitive algorithm for facility location.

Sequence prediction methods for dynamical systems with long memory, i.e. marginally stable systems, typically achieve regret that grows polynomially with the hidden dimension of the underlying generative model. Universal Sequence Preconditioning (USP) \cite{marsdenuniversal} is a method that compresses any sequence which comes from a linear dynamical system into a ``preconditioned'' sequence which requires exponentially shorter memory for accurate prediction. However, the preconditioned sequence yields exponentially larger diameters and gradients, hindering USP from unlocking optimal regret bounds. Inspired by the minimum description length principle, we show that the Vovk-Azoury-Warmuth (VAW) algorithm is naturally matched to the USP regime. Indeed, it takes advantage of the memory compression while remaining robust to the exponential explosion of the diameter. We prove that combining USP with VAW achieves astoundingly strong results: for any marginally-stable linear dynamical system, this algorithm achieves polylogarithmic regret $O\left( \log^3 T \right)$ even in the presence of asymmetric hidden transition matrices. Finally, we extend the applicability of USP beyond bounded-spectrum systems by providing new complex-analytic bounds on Chebyshev polynomials, allowing for systems with constant complex arguments.

We study dynamic pricing where a seller repeatedly interacts with a strategic, non-myopic buyer who has a fixed private valuation and discounts future utility. Prior work focused exclusively on posted-price mechanisms, where the seller gives a take-it-or-leave-it offer. For our first result, we show that menu mechanisms consisting of allocation-payment achieve $O(T_\gamma \log T_\gamma)$ regret, where $T_\gamma$ is the buyer's effective discounted time horizon. We also establish a $\Omega(T_\gamma)$ lower bound, demonstrating the bound is tight up to $\log$ factors. Considering the geometric discounting buyer with a constant discount factor, our bound is $O(1)$, while prior bounds using posted-price mechanisms incur an unavoidable $\Omega(\log\log T)$ factor in regret. Our second contribution is more conceptual in nature. The problem of dynamic pricing sits at the intersection of two paradigms: learning with strategic agents in computer science / machine learning and revelation-principle-based mechanism design in economics, yet their relationship has remained unclear. We establish a fundamental equivalence: indirect learning-based mechanisms and direct revelation mechanisms achieve identical optimal regret. The adaptive, data-driven algorithms of online learning and explicit type elicitation are two languages towards solving the same problem.

This position paper argues that the sequential supervised fine-tuning followed by reinforcement learning (SFT-then-RL) pipeline---the de facto paradigm for large language model (LLM) post-training---has a fundamental property that cannot be fixed by hyperparameter tuning: SFT and RL optimize over nearly orthogonal parameter subspaces, so RL inevitably degrades the capabilities acquired during the preceding SFT phase. Under the PL condition, we show that this degradation scales linearly with the number of model parameters. Although the KL penalty can constrain distributional shift, it cannot correct the underlying gradient misalignment between the two objectives. Experiments on Qwen3-0.6B across four tasks confirm the theoretical predictions: on MATH-500, Alpaca, HH-RLHF, and SST-2, the SFT loss increases after the RL phase. We identify the underlying mechanism as persistent near-orthogonality between the gradients of the two objectives ( $\cos(g_\mathrm{SFT}, g_\mathrm{RL}) \approx 0$), paired with opposing curvature dynamics: SFT flattens the loss landscape while RL re-sharpens it. Based on our analysis, we propose three promising research directions: (1) joint optimization of the two objectives with gradient surgery to resolve conflicting updates; (2) landscape-aware scheduling that terminates RL training precisely at the theoretically optimal point; and (3) characterizing the model scale threshold above which SFT becomes unnecessary.

We present the PokéAgent Challenge, a large-scale benchmark for decision-making research built on Pokémon's multi-agent battle system and expansive role-playing game (RPG) environment. Partial observability, game-theoretic reasoning, and long-horizon planning remain open problems for frontier AI, yet few benchmarks stress all three simultaneously under realistic conditions. PokéAgent targets these limitations at scale through two complementary tracks: our Battling Track, which calls for strategic reasoning and generalization under partial observability in competitive Pokémon battles, and our Speedrunning Track, which requires long-horizon planning and sequential decision-making in the Pokémon RPG. Our Battling Track supplies a dataset of 20M+ battle trajectories alongside a suite of heuristic, RL, and LLM-based baselines capable of high-level competitive play. Our Speedrunning Track provides the first standardized evaluation framework for RPG speedrunning, including an open-source multi-agent orchestration system that enables modular, reproducible comparisons of harness-based LLM approaches. Our NeurIPS 2025 competition validates both the quality of our resources and the research community's interest in Pokémon, with more than 100 teams competing across both tracks and winning solutions detailed in our paper. Participant submissions and our own baselines reveal considerable gaps between generalist (LLM), specialist (RL), and elite human performance. Analysis against the BenchPress evaluation matrix shows that Pokémon battling is nearly orthogonal to standard LLM benchmarks, measuring capabilities not captured by existing evaluation suites and positioning Pokémon as an unsolved benchmark that can drive RL and LLM research forward. We transition from the NeurIPS 2025 competition to a living benchmark by releasing a live leaderboard for Battling and self-contained evaluation for Speedrunning at https://pokeagentchallenge.com.

Fairness impossibility results often look like distinct scalar incompatibility statements. We show that several share one RKHS geometry: fairness criteria are linear constraints on conditional mean embeddings, and unequal base rates make the law of total expectation overdetermine those constraints. This view yields four results. The Kleinberg--Mullainathan--Raghavan dichotomy needs only group-conditional unbiasedness, not full calibration. The \emph{Pok\'emon theorem} shows that a distinct group pair satisfying any finite collection of linear mean-fairness criteria leaves a residual violation witnessed by the MMD, decaying at the Kolmogorov $m$-width rate under spectral regularity. The same tools prove an impossibility for fair feature learning: parity and class-conditional separation in representation space force class collapse under unequal base rates. The approximate relaxations yield signal and error frontiers, allowing a trade-off between real-world estimators and fairness goals. Experiments on standard fairness benchmarks are consistent with our bounds.

Self-supervised learning (SSL) pretrained models have become a dominant paradigm for visual representation learning, but they are vulnerable to backdoor attacks. Existing defenses struggle to defend against such attacks in a fully black-box setting because they often require access to labels, attack patterns, or training data. To tackle this issue, we propose a new attack-agnostic, model-agnostic, and modality-agnostic black-box test-time defense paradigm, called \emph{Platonic Representation Defense}. It is inspired by the Platonic Representation Hypothesis, which suggests that large-scale independently trained encoders converge toward compatible projections of the same underlying reality. We formalize this idea as a conditional energy function defined over source representations and a set of reference representations. The energy function is trained for detection through noise-contrastive estimation and for representation purification through denoising score matching. Theoretically, the energy gap between matched and mismatched samples is lower bounded by the mutual information between source and reference representations. We demonstrate the effectiveness of our method on multiple self-supervised encoders and more than 10 attacks. The method can perform both representation detection and purification, and achieves substantial performance gains across multiple attacks. Code can be found in the appendix.

The mechanisms behind LLMs' broad generalization beyond training examples are poorly understood. Emergent misalignment (EM) offers a striking case study: finetuning on narrow tasks induce broad misalignment to semantically-unrelated test domains. In this work, we propose the Piggyback Hypothesis: the chat-template prefix, shared across all user queries, can piggyback the finetuned behavior onto out-of-domain queries. We validate this hypothesis by showing that subtle perturbations to the prefix, or simply patching the prefix representations with those from the unfinetuned model, can restore alignment without changing the user query. Building on this finding, we propose Token-Regularized Finetuning (TReFT), which directly regularizes prefix representations during training to mitigate piggybacking. Across Llama-3.1, Qwen-2.5, and GPT-OSS models and multiple EM-inducing datasets, TReFT reduces EM while preserving in-domain learning. On Llama-3.1-8B finetuned on the legal domain, TReFT achieves 33.5\% more EM reduction than data interleaving with a retain set of aligned examples. We further show that TReFT extends to other narrow-finetuning settings, including abstention, tool use, and refusal (off-topic generalization is reduced by 54.3\% on average), which further supports the Piggyback Hypothesis. Broadly, our work highlights that LLMs may learn and generalize in unintended ways and suggests a path toward more controllable finetuning. It also calls for further study of how shared input features can piggyback model behavior across domains.

RLVR reliably improves reasoning, yet it appears to update only a tiny fraction of weights. We resolve this paradox by revealing a persistent, model-conditioned optimization bias: independent runs concentrate updates in similar parameter regions, invariant to dataset or RL recipe, while finite-precision storage (e.g., bf16) obscures widespread micro-updates as a visual sparsity artifact. To characterize this unique bias, we show that RLVR preferentially learns along off-principal directions via a cascaded Three-Gate mechanism: updates are first bounded by a empirical KL constraint (Gate I), then steered by the model’s anisotropic geometry(Gate II) toward spectrum-preserving off-principal subspaces, and finally filtered by finite precision (Gate III), effectively masking minor updates. Empirically, we validate the off-principal dynamics: RLVR exhibits minimal spectral drift, reduced principal-subspace rotation, and strong off-principal alignment that set RLVR strikingly apart from SFT. Together, our results provide the first parameter-space account of RLVR and uncover consistent regularities in weight evolution, advancing a more white-box understanding of RLVR. Moreover, we show that RLVR follows an optimization regime distinct from SFT, showing directly that transferring SFT-era PEFT can be flawed and motivating geometry-aware, RLVR-native methods.

Sortition is the practice of delegating public decision-making to randomly selected panels. Recently, it has gained momentum worldwide through its use in citizens' assemblies, sparking growing interest within the computer science community. One key appeal of sortition is that random panels tend to be more _representative_ of the population than elected committees or parliaments. Our main conceptual contribution is a novel definition of representative panels, based on the Wasserstein distance from statistical learning theory. Using this definition, we develop a framework for analyzing the _panel complexity_ problem—determining the required panel size to ensure desirable properties. We focus on three key desiderata: (1) that efficiency at the panel level extends to the whole population, measured by social welfare; (2) that fairness guarantees for the panel translate to fairness for the population, captured by the core; and (3) that the probability of an outlier panel, for which the decision significantly deviates from the optimal one, remains low. We establish near-tight panel complexity guarantees for these desiderata across two fundamental social choice settings: facility location and participatory budgeting.

Hypernetwork-based methods such as Doc-to-LoRA internalize a document into an LLM's weights in a single forward pass, but they fail systematically when the document contradicts pretraining knowledge: accuracy drops to 46.4% on the deepest conflicts. We show that this failure is primarily a magnitude problem rather than a representational one. The generated adapter reaches the relevant layers, but its adapter margin is not calibrated to the strength of the contradicted prior; as the pretrained margin grows, deep conflicts lose the override competition. This account predicts that failure should track prior strength. Sorting 194 conflicts by the base model's log-probability on the contradicted fact, baseline accuracy falls from 68% on weak-prior questions to 16% on strong-prior questions, a 52 percentage-point gap. We propose two training-free corrections. Selective Layer Boosting (SLB) scales the adapter at its highest-activity layers, and Conflict-Aware Internalization (CA) applies stronger boosting only when the base model appears confident. Together they raise deep-conflict accuracy from 46.4% to 71.0% on Gemma-2B and from 53.6% to 72.5% on Mistral-7B, while preserving novel-knowledge recall at 97.1%. They outperform vanilla retrieval-augmented generation on Gemma medium conflicts by 18 percentage points, though explicit conflict-aware prompts remain stronger when the user already knows a conflict exists. We release KID-Bench, a 489-question benchmark that separates novel recall, cross-knowledge combination, and prior-graded conflicts.