NeurIPS 2026 论文列表

Multimodal Large Language Models (MLLMs) trained on sequential tasks suffer from catastrophic forgetting. We study this problem in LoRA-based multimodal continual instruction tuning. By analyzing the diagonal Fisher information of LoRA parameters, we find that forgetting is amplified not merely by shared high-sensitivity parameters across tasks, but by the concentration of updates on those shared parameters, \ie, some tasks distribute their change uniformly across parameters, while others pack most of it into a narrow subset, causing disproportionate interference on the parameters that prior tasks depend on. We further observe that this concentration manifests in the dominant directions of recent gradients. Based on this insight, we propose \textbf{D}om\textbf{i}nant-direction \textbf{G}radient \textbf{Pro}jection (\textbf{DiGPro}), which maintains a short buffer of recent gradient directions, extracts their dominant subspace with adaptive rank selection, and attenuates the parallel component for each optimizer step. Crucially, DiGPro requires no prior-task data or stored subspaces, operating on the current gradient history. Experiments on cross-modal and vision-centric continual learning benchmarks show DiGPro consistently reduces forgetting and attains competitive final results. The code is available in the supplementary materials.

Intent-obfuscation-based jailbreak attacks on multimodal large language models (MLLMs) transform a harmful query into a concealed multimodal input to bypass safety mechanisms. We show that such attacks are governed by a \emph{reconstruction--concealment tradeoff}: the transformed input must hide harmful intent from safety filters while remaining recoverable enough for the victim model to reconstruct the original request. Through a reconstruction analysis of three representative black-box methods, we find that existing transformations struggle to balance this tradeoff, limiting their effectiveness. In contrast, we show that character-removed variants achieve a better balance. Building on this, we propose \emph{concealment-aware variant construction}, which greedily selects character-removed variants that are low in harmful-keyword alignment and mutually diverse, and instantiates them through five modality-aware prompting strategies. We further introduce \emph{keyword-related distractor images} that depict the harmful keyword in diverse contexts, providing more effective auxiliary visual context than generic distractor images. Experiments across closed-source and open-source MLLMs show the proposed strategies outperform strong baselines, revealing an underexplored vulnerability: a model's own reconstruction ability can be exploited to recover hidden harmful intent and produce unsafe responses.

Large language models (LLMs) are costly to deploy due to their large memory footprint and high inference cost. Weight-activation quantization can reduce these costs, but low-bit activation quantization remains difficult because activation outliers induce large quantization error. Recent rotation-based methods address this by applying orthogonal transformations that redistribute activation magnitude across dimensions, but existing approaches either require expensive end-to-end rotation training or rely on stored activation corpora, introducing significant compute or storage overhead. We propose a lightweight post-training rotation calibration method for LLM activation quantization. Our method learns orthogonal rotations that align normalized activations with the corners of an inscribed hypercube, encouraging activation energy to be distributed more evenly across dimensions. This objective admits an efficient closed-form update via the orthogonal Procrustes problem, avoiding gradient-based optimization over the orthogonal group. We further introduce an online calibration procedure that updates rotations as calibration samples are processed, eliminating the need to store activations on disk and allowing rotations to adapt to quantized activation distributions during calibration. Experiments on Llama-2 and Llama-3 models from 3B to 70B parameters show that our method achieves competitive or improved performance across perplexity benchmarks and common sense reasoning tasks while avoiding both costly end-to-end training and large offline activation storage.

Approval-based committee voting has received significant attention in the social choice community. Among the studied rules, Thiele rules, and especially Proportional Approval Voting (PAV), stand out for desirable properties such as proportional representation, Pareto optimality, and support monotonicity. Their main drawback is that computing a Thiele outcome is NP-hard in general. A glimpse of hope comes from the fact that Thiele rules are better behaved under structured preferences. On the candidate interval (CI) domain, they are computable in polynomial time via a linear program (LP) that has a totally unimodular constraint matrix. Surprisingly, this approach fails for the related voter interval (VI) domain, and the complexity of the problem has repeatedly been posed as an open question. Our main result resolves this question: although the relevant matrix is not totally unimodular, the ``standard'' LP still admits at least one optimal integral solution, and we provide a fast algorithm for finding it. Our technique naturally extends to the voter-candidate interval (VCI) domain, also known as the 1-dimensional voter-candidate range (1D-VCR) domain, and to the linearly consistent (LC) domain, both of which generalize the candidate and voter interval domains. Although both the VCI and LC domains have been studied in social choice, their relationship was unknown. We show, through connections to graph theory, that LC strictly contains VCI. We also provide an alternative definition of LC that is closer in spirit to VCI and has a natural interpretation in approval elections; this equivalence may be of independent interest. Finally, we study an alternative tree-based generalization of VCI and show that Thiele rules become NP-hard to compute on this domain.

For $p \ge 1$, the $p$-Wasserstein distance measures the minimum cost of transporting probability mass, where moving mass between two points costs the $p$th power of their distance. For discrete distributions in one dimension, full transport is especially simple: after sorting, mass is matched in order along the line. By contrast, partial and unbalanced transport on the line remains much less understood. Recently, Chapel and Tavenard [ICLR'25] showed that, for $p=1$, all optimal partial transport plans between distributions supported on $n$ points, with uniform mass at each point, can be computed in $O(n\log n)$ time by exploiting the metric structure of the cost. For $p>1$, this structure no longer applies, and existing approaches require $\Omega(n^2)$ time. Our main contribution is an FFT-based data structure for balanced-interval transport queries, which bypasses this quadratic bottleneck and yields an $O(p\ n\log^2 n)$-time algorithm for computing all optimal partial transports on the line for every finite $p\ge 1$. We also provide an open-source C++ implementation that outperforms the state-of-the-art baseline on a range of synthetic instances. Finally, we establish a conditional lower bound for $p=\infty$: any subquadratic-time algorithm for computing all optimal partial transport plan costs on the line would violate the $(\min,+)$-Convolution Hypothesis. This separates the problem from full optimal transport, which is solvable in $O(n\log n)$ time.

Neural surrogates for Partial Differential Equations (PDEs) are usually trained on synthetic data from numerical simulators. As models grow and scaling laws demand larger datasets, the cost of data generation often outweighs the training cost and becomes the bottleneck in the scaling quest. Unlike data in other domains, however, each PDE sample has a tunable per-sample cost that depends on its numerical fidelity, with the resulting cost-accuracy trade-off governed by known convergence rates. We exploit this property by formalizing neural surrogate training as a function of both data quantity and fidelity under a fixed data generation compute budget, treating fidelity as a fine-grained discrete spectrum rather than a binary distinction. Building on this, we show that multi-fidelity training enables Pareto-optimal error scaling against data generation compute. By using simulations at lower fidelities as an additional training signal, our approach consistently outperforms training on the highest fidelity at matched data generation budgets. We validate this across six PDE problems spanning structured grids and unstructured meshes, two distinct error sources (discretization and iterative-solver error), and four surrogate architectures.

Pretraining followed by fine-tuning introduces a compute-allocation problem: under a fixed training budget, time spent improving the upstream objective reduces the time available for downstream adaptation. Despite its practical importance, this trade-off is not yet well understood theoretically, even in simple models. In this paper, we cast compute allocation as a time-split problem under a two-stage pretrain–fine-tune procedure with fixed total optimisation time, using regularised least squares trained by gradient flow as a tractable setting. We characterise the optimal switching time under data-dependent evaluation geometries induced by the fine-tuning problem. Our results show that the allocation depends on how pretraining directions affect fine-tuning predictions and how fine-tuning shifts are seen through downstream data geometry. In particular, the relevant quantities are determined by prediction-relevant spectral components of the pretraining and fine-tuning empirical covariances. Technically, the analysis relies on a basis-invariant, eigenspace-level spectral decomposition, together with perturbative control of the non-commuting pretraining and fine-tuning dynamics.

Stochastic momentum methods such as heavy ball (HB), Nesterov momentum, and variants of Accelerated SGD (ASGD) [Kidambi et al., 2018] are widely used in modern training, but their stochastic benefits depend on two distinct quantities: serial runtime, the number of iterations needed to reach a target accuracy, and compute efficiency (CE), the inverse total gradient-query or FLOP cost. Larger batches reduce serial runtime without hurting CE only when the contraction gap grows linearly with batch size. We study stochastic HB and ASGD for consistent linear regression with Gaussian covariates and prove finite-dimensional, discrete-time lower bounds on their batch-size tradeoffs. Our first result shows that HB does not improve the CE frontier over SGD for arbitrary spectra; rather, it preserves SGD-level CE over a larger batch-size window, allowing larger batches to reduce serial runtime until HB reaches its deterministic accelerated scale. This window can be a factor $\sqrt{\kappa}$ larger than the SGD critical batch size. For ASGD, the picture is more spectrum-dependent: for rapidly decaying power-law spectra, ASGD improves small-batch CE over HB/SGD, but as batch size grows it trades this CE advantage for improved serial runtime. Synthetic linear-regression experiments verify these qualitative regimes, including near-overlap of ASGD and HB for slowly decaying spectra and the predicted CE--serial tradeoff for rapidly decaying spectra.

Competition among LLM providers hinges not only on model accuracy, but also on the latency of serving user requests. However, user demand leads to congestion which increases latency, creating a feedback loop between provider decisions and user choices. In this work, we study a stylized game between two providers who strategically balance allocating fixed compute between training better models and reducing latency. A population of users then chooses between the providers. Our equilibrium analysis reveals that a lower-budget provider can still attract users by taking advantage of the congestion faced by the dominant provider. Relative to a competitive baseline where providers have equal compute resources, compute asymmetry leads the higher-resource provider to divert a greater fraction of their compute from improving accuracy to reducing latency. Moreover, this compute asymmetry strictly harms users. Altogether, our results illustrate how congestion distorts competition between model-providers, leading to subtle implications for market competitiveness, model accuracy, and user utility.

Scaling test-time compute has emerged as a powerful mechanism for enhancing Large Language Model (LLM) performance. However, standard post-training paradigms, Supervised Fine-Tuning (SFT) and Reinforcement Learning (RL), optimize the likelihood of individual samples under a base policy, creating a misalignment with test time procedures that rely on aggregated or filtered outputs. In this work, we propose Compute Aligned Training, which aligns training objectives with test-time strategies. By conceptualizing inference strategies as operators on the base policy, we derive new loss functions that maximize performance when said strategies are applied. We instantiate such loss functions for SFT and RL across common test time strategies. Finally, we provide empirical evidence that this training method substantially improves test time scaling over standard training.

Learning Gibbs distributions using only sufficient statistics has long been recognized as a computationally hard problem. On the other hand, computationally efficient algorithms for learning Gibbs distributions rely on access to full sample configurations generated from the model. For many systems of interest that arise in physical contexts, expecting a full sample to be observed is not practical, and hence it is important to look for computationally efficient methods that solve the learning problem with access to only a limited set of statistics. We examine the trade-offs between the power of computation and observation within this scenario, employing the Ising model as a paradigmatic example. We demonstrate that it is feasible to reconstruct the model parameters for a model with $\ell_1$ width $\gamma$ by observing statistics up to an order of $O(\gamma)$. This approach allows us to infer the model's structure and also learn its couplings and magnetic fields. We also discuss a setting where prior information about structure of the model is available and show that the learning problem can be solved efficiently with even more limited observational power.

We study the computational relationship between replicability (Impagliazzo et al. [STOC `22], Ghazi et al. [NeurIPS `21]) and other stability notions. Specifically, we focus on replicable PAC learning and its connections to differential privacy (Dwork et al. [TCC 2006]) and to the statistical query (SQ) model (Kearns [JACM `98]). Statistically, it was known that differentially private learning and replicable learning are equivalent and strictly more powerful than SQ-learning. Yet, computationally, all previously known efficient (i.e., polynomial-time) replicable learning algorithms were confined to SQ-learnable tasks or restricted distributions, in contrast to differentially private learning. Our main contribution is the first computationally efficient replicable algorithm for realizable learning of parities over arbitrary distributions, a task that is known to be hard in the SQ-model, but possible under differential privacy. This result provides the first evidence that efficient replicable learning over general distributions strictly extends efficient SQ-learning, and is closer in power to efficient differentially private learning, despite computational separations between replicability and privacy. Additionally, we leverage our parity learner to prove that, assuming $RP \neq NP$, converting replicability to pure differential privacy requires a strict loss in sample complexity. Our main building block is a new, efficient and replicable algorithm that, given a set of vectors, outputs a subspace of their linear span that covers most of them.

Dynamic mechanism design provides a principled framework for coordinating self-interested agents whose private information evolves over time, but history dependence and dynamic incentive constraints make general analytical solutions difficult. Using a dynamic revelation principle, we formulate optimal dynamic mechanism design as a bilevel optimization problem over parameterized direct mechanisms: the principal optimizes the mechanism, while agent-side unilateral deviation problems verify incentive compatibility. We model each agent’s problem as a parameterized POMDP, and use stochastic natural policy gradient to solve these POMDPs with finite-sample error bounds. These policies serve as oracle outputs for the principal’s problem, yielding first-order optimization procedures with convergence guarantees that approximate stationary solutions under bounded oracle error. This formulation separates two representation choices: principal-side history compression and agent-side sufficient statistics. Experiments in dynamic bandit and budget-constrained auctions show that the framework can recover known benchmarks and learn approximately incentive-compatible mechanisms beyond analytical settings. Furthermore, they reveal how representations affect optimization.

Post-training quantization degrades multimodal model capabilities unevenly, yet practitioners lack a principled way to predict which capabilities will collapse. We propose the **Computational Depth Principle** (CDP): end-to-end fidelity under quantization follows $\hat p^n$, where $n$ counts sequential precision-dependent operations and $\hat p$ is a per-architecture survival rate. Across four VLM families and diverse benchmarks spanning image understanding, image generation, video understanding, and video generation, we show that deeper reasoning tasks consistently degrade more steeply and that a single shallow probe predicts the full degradation ranking on held-out architectures. The same exponential form extends to image generation, where denoising step count plays the role of depth, and to video understanding, where longer temporal reasoning chains amplify losses. For video generation, spatial quality degrades more than temporal coherence, indicating that the dominant compounding axis is denoising depth rather than cross-frame coupling. A complementary distortion-to-information (D/I) flip ratio diagnoses quantization method effects, revealing that certain methods preserve near-baseline quality while others produce catastrophic collapses on specific architecture pairings that aggregate accuracy alone cannot detect. Module ablation localizes the sensitivity to the language backbone rather than the vision encoder. Together, depth and D/I convert full-suite evaluation into a two-probe screening protocol that surfaces the highest-risk capability gaps first.

Decision trees with binary leaves are fundamental building blocks in classical machine learning. While individual trees can be used as strong interpretable classifiers, they frequently serve as members of large collections instead: primarily as components of powerful ensembles, but also as one of the few model classes for which the entire set of near-optimal models (the Rashomon set) can be analyzed. Both types of collections are often more complex than necessary, because there are many decision tree representations for the same decision boundary, imposing unnecessary computational costs in ensembles and complicating theoretical work on Rashomon sets. We propose methods to reduce collections of trees to a subset representing each unique decision boundary in the collection, with each tree in its sparsest equivalent form. In so doing, we improve the scalability of removing provably redundant classifiers in a Rashomon set. We also compress many shallow Adaboost ensembles by >15\% of their total number of leaves, while exactly preserving the models' decisions and probability estimates on any possible observation. These methods allow practitioners to run more efficient computations over compressed collections of trees, and remove arbitrary complexity when analyzing and understanding them.

Deep networks embed inputs in high-dimensional representations, but how much of this capacity actually drives behavior? We introduce a framework for identifying, at each layer, the subspace of the representation that is functionally relevant for the task. Using a matrix analogous to the Fisher information but defined over the hidden representation, we rank directions by their influence on downstream computation and project onto the most task-relevant subspace. We benchmark this behaviorally grounded compression against three geometric alternatives that preserve variance, local neighborhood structure, or global topology. Across pretrained vision models, representations are remarkably compressible: a small fraction of the task-relevant subspace preserves most performance, often requiring far fewer dimensions than geometric alternatives. We show that this decomposition recovers functionally distinct subspaces within the same representation: on cue-conflict stimuli, shape-relevant and texture-relevant directions are largely non-overlapping, and ablating one selectively impairs the corresponding task while leaving the other intact. Task-relevant subspaces also provide a principled foundation for continual learning: constraining gradient updates to lie orthogonal to the task-relevant subspaces of prior tasks outperforms standard variance-based gradient projection methods. Finally, restricting representational comparisons to task-relevant subspaces reveals that inter-model alignment is higher in task-relevant directions than in task-irrelevant directions at later layers, and that conditioning on different tasks over the same stimuli uncovers asymmetries that full-space similarity measures cannot detect. Together, these results establish that deep networks compute through a low-dimensional functional core embedded within a much larger representational space, that these cores differ across tasks, and that they provide a unifying basis for compression, continual learning, and representational comparison.

Long-horizon robotic planning often requires satisfying temporally ordered safety and visitation constraints rather than a single goal condition. We study multiple reach-avoid (MRA) tasks, in which a robot must sequentially visit target regions while remaining within corresponding safe sets. Existing approaches either rely on explicit system models or use data-driven planners whose test-time conditioning mechanisms do not scale well to long-horizon temporally structured tasks. We propose a training-free compositional diffusion planning framework for MRA tasks that operates directly on a pre-trained task-agnostic diffusion trajectory prior at test time, without requiring a known dynamics model. Our approach decomposes a global MRA specification into local reach-avoid sub-tasks, composes overlapping short-horizon diffusion priors into a long-horizon generative process through a factor-graph perspective, and enforces each local requirement through projection-based denoising during sampling. The same construction also extends naturally to prefix-suffix tasks through a looped compositional graph. We provide a formal correctness guarantee showing that the stitched trajectory satisfies the target specification. Experiments on long-horizon constrained planning benchmarks show strong execution success, substantially lower planning time than representative guidance-based baselines, and effective transfer to richer dynamics.

A neural network trained on the multiplication table of the quaternion group Q₈ can achieve perfect accuracy within each cyclic subgroup ⟨i⟩ and ⟨j⟩, predict every cross-region product wrong, and stay there indefinitely. This is the grokking plateau, and we prove its height is exactly 4 in dimension d=2, determined by the topology of the overlap before any training. The mechanism is a homotopy pullback: for G = A ∗_C B with finite overlap, the representation space of G is a homotopy pullback of those of A and B over that of C, so locally accurate modules need only agree up to a basis change. From this we derive a stratified generalization certificate whose strata are the connected components of Hom(C, U(d)): in the correct stratum, with locally accurate modules, the cross-region prediction is O(ε)-close to the target; in the wrong stratum it is provably far regardless of local accuracy, with exact gap c = 2(d − rₘₐₓ) for central cyclic overlap. The plateau is therefore the time the network spends in the wrong stratum, the grokking transition is the discrete jump between strata, and the framework predicts which task families exhibit such plateaus—those whose overlap representation space is disconnected—and which do not.

Large-scale verifiable prompts underpin the success of Reinforcement Learning with Verifiable Rewards (RLVR), but they contain many uninformative examples and are costly to expand further. Recent studies focus on better exploiting limited training data by prioritizing hard prompts whose rollout pass rate is 0. However, easy prompts with a pass rate of 1 also become increasingly prevalent as training progresses, thereby reducing the effective data size. To mitigate this, we propose Composition-RL, a simple yet useful approach for better utilizing limited verifiable prompts targeting pass-rate-1 prompts. More specifically, Composition-RL automatically composes multiple problems into a new verifiable question and uses these compositional prompts for RL training. Extensive experiments across model sizes from 4B to 30B show that Composition-RL consistently improves reasoning capability over RL trained on the original dataset. Performance can be further boosted with a curriculum variant of Composition-RL that gradually increases compositional depth over training. Additionally, Composition-RL enables more effective cross-domain RL by composing prompts drawn from different domains. All our codes, compositional datasets, and models will be released to facilitate future research.