NeurIPS 2026 Papers

Masked patch self-distillation has become a default ingredient of modern joint-embedding pretraining, and is widely regarded as a uniform enhancement of dense visual representations. In this work, we revisit this assumption and argue that its effect is more nuanced. Through controlled experiments across multiple joint-embedding objectives and model scales, we observe a consistent tension: while the auxiliary patch objective strengthens semantic abstraction, it systematically erodes fine-grained spatial correspondence. To examine this phenomenon beyond the reach of human-annotated benchmarks, we introduce annotation-free diagnostics that probe how much local visual evidence remains accessible in the learned representation. We further provide a population-level theoretical analysis showing that this trade-off is not incidental but follows directly from the conditional nature of masked semantic prediction, under which target variation unpredictable from visible context is provably averaged out. Taken together, our findings recast masked patch self-distillation as an explicit trade-off between semantic abstraction and local detail, rather than a uniform improvement to dense features.

The rise of machine learning has shifted targeted resource allocation in policy and humanitarian settings toward algorithmic targeting based on predicted risk scores. This approach is typically cheaper and faster than traditional screening procedures that directly observe the latent vulnerability status through physical verification. Yet, even access to the true conditional vulnerability probability cannot eliminate misallocation: aleatoric uncertainty over individual vulnerability status is irreducible, and probabilistic targeting inevitably misallocates some resources. In this work we study how screening and algorithmic targeting should be optimally combined in a two-stage allocation framework where a screening stage observes true outcomes for a subset of units before a final allocation stage assigns the resource under a fixed coverage budget. We show that the optimal strategy screens units at the margin of algorithmic allocation, while directly targeting the highest-risk units. Furthermore, we empirically characterize when screening and algorithmic targeting act as complements or substitutes: efficiency gains from screening grow as the aleatoric uncertainty in the population increases. We illustrate our framework with applications in income-based social protection programs and humanitarian demining in Colombia, where the tension between screening costs and allocation efficiency is operationally consequential.

Across scientific disciplines, Laplacian eigenvectors serve as a fundamental basis for simplifying complex systems, from signal processing to quantum mechanics. In reinforcement learning (RL), they similarly form a basis over the state space, enabling reward functions to be approximated by projection onto a small set of eigenvectors. This projection makes zero-shot control possible, but it also imposes a fundamental limitation: the induced policies are only as expressive as the linear span of the chosen eigenvectors. We introduce the Laplacian Keyboard (LK), a hierarchical framework that goes beyond this linear span. LK constructs a task-agnostic library of behaviors from these eigenvectors, forming a behavior basis guaranteed to contain the optimal policy for any reward within the linear span. A meta-policy learns to stitch these behaviors dynamically, enabling efficient learning of policies outside the original linear constraints. We establish theoretical bounds on zero-shot approximation error and demonstrate empirically that LK improves over the zero-shot solution while achieving better sample efficiency compared to standard RL methods.

In recent years, several methods for detecting when large language models (LLMs) hallucinate have been developed. These methods are often evaluated with hallucination detection benchmarks using open-domain question answering (QA) datasets that contain questions and corresponding short reference answers. Currently, these benchmarks use an LLM to generate answers to questions within the QA dataset. Then, various automated strategies are applied to label these answers as hallucinated or not by comparing them with the reference answers. This evaluation setting creates a methodological ambiguity between two criteria: reference faithfulness --- whether the answer is fully supported by the reference --- and factual correctness --- whether the answer is free from contradictions and factually false specific claims. In practice, automated labelers may apply the former criterion even when the intended target is the latter. We study this potential criterion mismatch using 900 human-labeled question--answer pairs spanning three commonly used QA datasets and three generator models. Our human annotations target answer-level factual correctness. As automated label generation strategies, we evaluate lexical similarity metrics, a reference-entailment NLI baseline, and seven LLM judges under controlled prompt variants. We compare the effect of using either a faithfulness-oriented prompt, which asks the judge model to treat any answer content unsupported by the reference as a hallucination, or a factual-correctness prompt, which explicitly distinguishes between absence from the reference and factual error. Our experiments reveal substantial disagreement both among different automated label-generation strategies and between these automated labels and human annotations. Many strategies also exhibit strong biases towards certain error types. For most LLM judges, replacing the faithfulness-oriented prompt with the factual-correctness prompt significantly improves agreement with human annotations, showing that automated hallucination labels depend strongly on how the target criterion is specified. For open-domain QA benchmarks targeting factual correctness, relying on strict reference faithfulness can introduce systematic measurement bias. Label-source choice should therefore be considered a fundamental part of benchmark design and made explicit, validated, and matched with the benchmark goal.

The quadratic cost of causal self-attention severely bottlenecks long-context transformer inference. While numerous post hoc linearization pipelines exist, it is difficult to identify which components preserve model quality. This work isolates the effect of state update design in a strict frozen-backbone regime. We show that softmax relies on key-dependent, rank-1 orthogonal projections, elucidating why delta-style networks outperform purely gated accumulation. We identify a potential source of approximation errors and introduce structural interventions, specifically sink tokens, short convolutions, and fixed-budget cache routing, which reduces the remaining gap. We scale this linearization approach across LLaMA and Qwen models up to 32B parameters, outperforming prior post hoc baselines on MMLU and matching the long-context retrieval of complex adaptive-caching frameworks.

Kernelized attention methods, which aim to replace the $O(N^2)$ complexity of softmax attention with $O(N)$ alternatives, have been the focus of intense research in the last five years. Despite growing interest, systematic evaluations at foundation model scales and fair comparisons across approaches are still missing. We analyze kernelized attention in two halves and highlight prominent limitations on each. On efficiency, FlashAttention achieves lower memory consumption and faster wall-clock time than state-of-the-art kernelized methods across most sequence lengths (with auto-regressive generation memory the only clear exception), directly contradicting the field's core assumption. We also discover that reported efficiency gains often fail to reproduce against modern baselines. On quality, current kernelized methods leave gaps of $2$-$10$ points relative to softmax under a unified distillation protocol, and these gaps do not close with model scale. We show this gap is not intrinsic to kernelization: LARA++, a principled extension of LARA that approximates softmax via importance sampling with adaptive proposal distributions, recovers up to 99\% of softmax accuracy. We establish that the gap is closable; however, the computational overhead remains substantial, leaving the efficiency wall intact.

Real-world datasets are inherently heterogeneous, yet how per-class structural differences and sampling imbalance shape the training dynamics of diffusion models—and potentially exacerbate disparities—remains poorly understood. While models typically transition from an initial phase of generalization to memorizing the training set, existing theory assumes homogeneous data, leaving open how class imbalance and heterogeneity reshape these dynamics. In this work, we develop a high-dimensional analytical framework to study class-dependent learning in score-based diffusion models. Analyzing a random-features model trained on Gaussian mixtures, we derive the feature-covariance spectrum to characterize per-class generalization and memorization times. We reveal the explicit hierarchy governing these dynamics: class variance is the primary determinant of learning order—consistently favoring higher-variance classes—while centroid geometry plays a secondary role. Sampling imbalance acts as a modulator that can reverse this ordering and, under strong imbalance, forces minority classes to acquire distinct, delayed speciation times during backward diffusion. Together, these results suggest that diffusion models can memorize some classes while others remain insufficiently learned. We validate our theoretical predictions empirically using U-Net models trained on Fashion MNIST.

Knowledge editing aims to rewrite sensitive information in language models, yet prior work has shown that edited models remain vulnerable to extraction attacks. In this work, we identify a previously overlooked vulnerability, which we term $\textit{rank leakage}$: although editing replaces the top-1 output with a sanitized answer, the original sensitive token often remains highly ranked in the model’s next-token distribution. Exploiting this phenomenon, we propose an effective black-box Output Attack that recovers sensitive information using only a single query. Despite its simplicity, the attack achieves strong extraction performance and remains effective even against models equipped with state-of-the-art defenses. To mitigate this vulnerability, we introduce $\textbf{R}$ank-guided $\textbf{C}$oncealment $\textbf{E}$diting (RCE), a plug-in defense that enforces explicit control over the rank of sensitive tokens during editing. Although designed for the Output Attack, RCE generalizes to existing black-box and white-box extraction attacks. Extensive experiments across multiple models, datasets, and editing algorithms show that RCE consistently improves resistance to attacks while preserving edit fidelity and model utility. Our results highlight the importance of controlling the rank of sensitive tokens, rather than only the top-1 prediction, for privacy-preserving knowledge editing.

Reinforcement learning with verifiable rewards has shifted the alignment paradigm of large language models from subjective preference to objective correctness, yet a fundamental disconnect persists between exploration diversity and reasoning validity. Existing strategies predominantly rely on ``blind'' entropy metrics, e.g., token-level or global sequence-level entropy, which structurally fail to distinguish between effective reasoning and potential hallucinations. This misalignment creates an illusion of diversity, where high entropy tends to signal chaotic degeneration rather than valuable exploration. To bridge this gap, we introduce \textit{Effective Entropy}, a validity-aware entropy concept that quantifies diversity exclusively within the valid subspace and systematically filters out the noise of incorrect trajectories. Built on this concept, we instantiate VEPO, a simple \textbf{V}alidity-aware \textbf{E}ntropy \textbf{P}olicy \textbf{O}ptimization method that directly incorporates effective entropy into RLVR training. VEPO induces an adaptive attraction dynamic that drives up the probability of under-explored valid trajectories, a mechanism that matches the practical regime of large-scale autoregressive models where sequence probabilities remain extremely small. Extensive experiments on reasoning benchmarks demonstrate that this effective-entropy-driven optimization significantly outperforms GRPO and other entropy-aware variants, showcasing its ability to more reliably cultivate, across diverse tasks, a broad portfolio of valid reasoning trajectories.

We study cooperative multi-agent reinforcement learning in the setting of reward-free exploration, where multiple agents jointly explore an unknown MDP in order to learn its dynamics (without observing rewards). We focus on a tabular finite-horizon MDP and adopt a phased learning framework. In each learning phase, multiple agents independently interact with the environment. More specifically, in each learning phase, each agent is assigned a policy, executes it, and observes the resulting trajectory. Our primary goal is to characterize the tradeoff between the number of learning phases and the number of agents, especially when the number of learning phases is small. Our results identify a regime change governed by the horizon $H$. When the number of learning phases equals $H$, we present a computationally efficient algorithm that uses only $\tilde{O}(S^6 H^6 A / \epsilon^2)$ agents to obtain an $\epsilon$ approximation of the dynamics (i.e., yields an $\epsilon$-optimal policy for any reward function). We complement our algorithm with a lower bound showing that any algorithm restricted to $\rho < H$ phases requires at least $A^{H/\rho}$ agents to achieve constant accuracy. Thus, we show that having $\Theta(H)$ learning phases is both necessary and sufficient when restricting the number of agents to be polynomial.

In Low-Rank Adaptation (LoRA), the scaling factor $\alpha$ is often treated as a mere complement to the learning rate, yet its role in optimization remains poorly understood. In this paper, we reveal that the scaling factor $\alpha$ and the learning rate function differently, with $\alpha$ emerging as the dominant driver of effective optimization, delivering gains that cannot be replicated by learning rate scaling alone. Through the synergy of extensive empirical analysis and a theoretical Signal-Drift framework, we uncover three findings into LoRA’s scaling mechanism: First, LoRA’s spectral suppression smooths the optimization landscape, rendering standard hyperparameters overly conservative and creating an optimization gap. Second, when leveraging this smoothness to accelerate convergence, $\alpha$ outperforms the learning rate by amplifying the task signal without increasing the drift ratio. Third, the optimal scaling factor follows a sublinear relationship with the rank, well characterized by a square-root law with an unexpectedly large coefficient, revealing the insufficient scaling of existing rank-tied heuristics. Based on these insights, we propose LoRA-$\alpha$, a minimalist framework that restores $\alpha$ to its principled regime, making LoRA compatible with standard small learning rates. Extensive evaluations across diverse tasks demonstrate that LoRA-$\alpha$ consistently improves performance while streamlining hyperparameter search, unleashing the learning potential of LoRA.

Estimating element frequencies in data streams is a fundamental problem when processing large amounts of data. Recent approaches suggest learning-augmented algorithms that can access a heavy-hitter oracle that knows the most frequent elements. In this paper, we challenge the idea of these complex oracles: First, we show that heavy-hitter predictions do not necessarily yield significant efficiency gains in frequency estimation. We prove that a classical algorithm using slightly more memory, $\Theta(B \log B)$ instead of $\Theta(B)$, matches the performance of learning-augmented methods with perfect predictions. Furthermore, we show that given (perfect) predictions, a trivial mechanism achieves the same performance as state-of-the-art learning-augmented algorithms. On the algorithmic side, we introduce SpaceR, a single-pass algorithm that matches the accuracy of existing two-pass prediction-based methods without requiring any predictions. SpaceR uses randomized sampling to identify and track frequent elements in one pass through the data, achieving near-perfect frequency recovery with minimal memory on both synthetic and real-world datasets.

GNNs have achieved remarkable success in graph learning, yet their black-box nature obscures the combinatorial reasoning behind their predictions. A core challenge lies in understanding how GNNs translate topological patterns (graph concepts) into logical rules. Current works only uncover hard Boolean logical rules over graph concepts, which cannot quantify the contribution of each concept to model predictions. Moreover, they are post-hoc methods that generate explanations after training via surrogate models, and thus may deviate from the true combinatorial reasoning of GNNs. In this work, we develop the graph concept bottleneck that enforces the combinatorial reasoning of GNNs to fit soft logical rules over graph concepts, thereby quantifying the contribution of each concept. To further enhance the graph concept bottleneck, we treat graph concepts as "graph words" and graphs as "graph sentences", and leverage language models to learn context-aware graph concept embeddings. Extensive experiments on multiple datasets show that our method GCBMs achieve state-of-the-art performance in both interpretability and classification.

Large language models confidently produce outdated answers, and no existing method can detect them. We show this is not an engineering failure but a structural one: temporal drift, whether a stored fact has changed since training, is encoded as a direction in the residual stream geometrically orthogonal to both correctness and uncertainty. Any method operating on correctness or uncertainty signals is therefore blind to drift by construction. We verify this across six instruction-tuned models. A linear probe trained directly on drift labels achieves AUROC $0.83$--$0.95$; methods based on token entropy, semantic entropy, CCS, and SAPLMA all remain near chance ($0.49$--$0.57$). Five tests confirm the geometric orthogonality: weight cosines ($|\cos| \leq 0.14$), score correlations ($|r| \leq 0.20$), bidirectional null-space projection ($|\Delta| \leq 0.008$), iterative null-space projection with $k{=}10$, and difference-of-means dissociation. Mechanistically, the MLP retrieval circuit produces identical dynamics for stale recall and confabulation ($r > 0.81$, six models), explaining why output confidence cannot separate them. A cross-cutoff experiment holds inputs constant and varies only the model: the probe fires on the model whose training predates the fact's transition and stays silent otherwise ($P(A{>}B) = 0.975$--$0.998$, twelve model pairs), confirming it reads model-internal knowledge state rather than input properties. Our code and datasets will be publicly released.

Fine-tuning aligned language models on benign tasks (e.g. math tutoring) systematically breaks safety guardrails, even when training data contains no harmful content. While mechanistic approaches have shed light on where alignment resides in model weights, they lack the formal language needed to derive guarantees about when and why fine-tuning degrades it — leaving the field without principled tools for predicting or preventing alignment collapse. We develop such a framework through geometric analysis of parameter-space trajectories and apply it to understand the fragility of alignment in fine-tuning. While first-order analysis suggests orthogonal updates are safe, we prove this is illusory: the curvature of the fine-tuning loss induces second-order acceleration that systematically bends trajectories into alignment-sensitive regions. We formalize the central construct of our framework as the Alignment Instability Condition (AIC), three geometric properties that, when present, are sufficient to guarantee degradation. Our main result proves quartic onset of alignment degradation in training steps, determined by how sharply alignment depends on specific parameters and how strongly tasks couple to these parameters. These findings yield formal sufficient conditions under which gradient descent makes alignment inherently fragile, demonstrating the framework's capacity for theoretical guarantees. We further empirically validate the framework's foundations, showing that the Fisher Information Matrix governs the degree of safety degradation across diverse fine-tuning settings.

LLM agents increasingly rely on reusable skills for multi-step reasoning, tool use, and decision making. Yet most existing approaches represent a skill as a prompt, module, or direction in representation space. This view can be insufficient for agentic settings: (1) the behaviour induced by a skill can depend on the current context, and (2) composing two skills can yield order-dependent rollouts. We formalise a skill realization as a local map from continuous intervention coordinates to a readout representation. Its differential defines the context-dependent controllable distribution, and the residence-space norm induces a metric on this distribution. Skill objectives then define local vector fields on these controllable directions. Their \emph{Lie bracket} captures the order-dependent component of skill composition, revealing behaviour that cannot be represented by a single context-independent direction. Our central measurement is a finite-difference skill commutator, which estimates the non-commutative component of two-skill composition from paired ordered rollouts. Unlike standard Lie-bracket estimation, the relevant vector fields are induced by skill objectives and observable ordered rollouts rather than given analytically. We therefore reconstruct the commutator from paired ordered rollouts, preserving the direction of the order-dependent change in representation space. We instantiate the framework on frozen LLM agents using activation-based and prefix-based skill realizations. Same-skill activation and prefix Jacobians are more aligned than cross-skill pairings (Cohen’s $d=-0.76/-0.26$), but they assign different control costs; separately, the measured two-skill interaction predicts ordered-composition gaps (Spearman $\rho_S=0.918/0.889$). High-commutator skill pairs also yield non-saturating reachability signals, with positive spectral-entropy gains and principal-angle novelty, while synthetic bracketed systems validate the finite-difference estimator. Together, these results show that skills form context-dependent geometric objects whose compositions leave measurable vector-valued non-commutative residuals.

Sparse autoencoders (SAEs) operationalise the linear representation hypothesis: they reconstruct model activations as sparse linear combinations of interpretable dictionary atoms, on the implicit assumption that activation space is well approximated by a globally linear structure. Their reconstruction error varies sharply across layers in ways that existing scaling laws, fitted at single layers, do not explain. We argue that this variation is the empirical trace of a geometric mismatch: where the activation manifold is curved and its intrinsic dimension varies across layers, no sparse linear dictionary can match it uniformly, and the SAE's width-sparsity scaling becomes a layer-dependent function of manifold structure rather than a single universal law. We conduct the first cross-layer SAE scaling study, fitting and regressing on 844 residual-stream Gemma Scope SAE checkpoints across 68 layers of Gemma 2 2B and 9B. Stage 1 fits a per-layer scaling-law surface; Stage 2 regresses the fitted parameters and the derived per-layer width exponents on four layerwise geometric summaries. We find that manifold geometry predicts the per-layer width exponent in both models, and that the same regression coefficients learnt on one model predict the other model's per-layer exponents under cross-model transfer, indicating a transferable geometric law. At the showcase layers where richer width grids permit identification of the asymptotic floor, we find that the fitted floor tracks the layerwise geometric ordering: higher curvature and intrinsic dimension correspond to higher floor, consistent with the irreducible second-order residual that any sparse linear approximation of a curved manifold must leave behind. SAEs thus encounter not a finite-resource ceiling but a geometry-dependent wall, set by the manifold they are trying to reconstruct.

Prior work on grokking—delayed generalization after memorization—has sought to shorten this delay through data augmentation or optimizer design. We take an architectural approach: rather than analyzing trained networks post-hoc, we modify architectural topology before training to test whether specific degrees of freedom prolong the memorization phase. We identify two independent factors in standard Transformers—unbounded residual magnitude and data-dependent attention routing—and introduce targeted interventions for each. A fully bounded spherical topology, enforcing L2 normalization throughout the residual stream, eliminates the memorization phase entirely on modular addition and multiplication over Z_p: training and test accuracy rise together from initialization. Independently, replacing learned attention with uniform aggregation achieves the same effect, consistent with theoretical results showing that commutative operations require only a bag-of-tokens representation. However, the same spherical constraint fails completely on non-commutative S5 permutation composition, where successful solutions rely on discrete coset structures rather than continuous Fourier features. This contrast demonstrates that bypassing the generalization delay is possible—but strictly depends on alignment between architectural priors and task symmetry. Since even the simplest non-commutative task resists the same constraint that eliminates delay on cyclic arithmetic, these results suggest that no single geometric prior can universally accelerate learning across the heterogeneous structures present in general-purpose domains.

Language models are becoming the default interface to factual knowledge, yet they often verify outputs more reliably than they generate them. This generation-verification gap (GV-gap) underlies many recent advances in self-improvement and reasoning, but its dynamics on factual knowledge specifically remain poorly understood. We focus on the training mechanisms underlying _factual_ GV-gaps, distinguishing them from their computational and aesthetic counterparts. We trace generation and verification capabilities through three training phases (acquisition, continual learning, and updating) across four open-source model families at two scales each. Three findings recur across models: (i) verification is consistently learned before generation; (ii) verification is more robust to continual learning than generation; and (iii) factual updates can leave models in a _multi-verse_ state, simultaneously verifying both old and new answers as correct. Natural experiments on frontier models reproduce these dynamics at scale and reveal residual verification biases on well-covered facts.