NeurIPS 2026 论文列表

Modern vision--language models are trained with very different objectives: CLIP-style contrastive alignment, SigLIP-style match/no-match prediction, caption-style token generation (Flamingo, LLaVA), and latent-space prediction (VL-JEPA). Each has been claimed as best-in-class for its target task. Yet practitioners lack clear guidelines for choosing between them, and existing identifiability theory analyzes only the contrastive case. In this work, we unveil the core statistical mechanisms that distinguish each objective family using a unified spectral analysis. By leveraging closed-form solutions for the linearized losses under a latent structure in which modality-specific nuisances may spuriously carry shared semantic content, we characterize what each objective recovers from the data. We demonstrate that contrastive alignment, match/no-match prediction, and latent-space prediction collapse to the same cross-modal solution, while directed token-space generation recovers a different one. Our findings indicate that in scenarios where one modality is heavily contaminated by spurious nuisance, token-space generation is preferable because it imposes a strictly weaker, one-sided alignment condition. In scenarios where two modalities are both clean, retrieval is maximized by the latent-prediction objective whose target matches the query modality. These results clarify the trade-offs between the four objective families. We validate our theoretical predictions on numerical, controlled synthetic, and real (Flickr30k, COCO, CC3M) data.

We introduce COMONet (Convex-Concave and Monotonicity-Constrained Neural Networks), a unified architecture for enforcing variable-wise shape constraints in neural networks. COMONet addresses the limitations of prior methods that either support only a restricted subset of monotonicity and curvature constraints or enforce them through penalties without strict architectural guarantees. Our framework assigns each input variable to one of eight shape regimes, covering monotonicity, convexity, concavity, and their combinations. This is achieved through a partially connected architecture that routes each variable to specialized units equipped with sign-constrained weights and constraint-preserving activation functions. We also provide theoretical guarantees showing that COMONet satisfies the prescribed variable-wise shape constraints by construction. Experiments on synthetic and real-world datasets demonstrate that COMONet achieves competitive performance and remains robust to noise while preserving its architectural guarantees. COMONet thus offers a practical and principled framework for incorporating domain knowledge as shape constraints into neural network training.

Learning-rate selection is one of the most consequential and repeatedly tuned decisions in modern deep learning, and the ability to transfer it quickly across widths, depths, and architectures can substantially reduce the cost of scaling new models. Existing transfer laws explain width through maximal-update parameterization and depth through depth-based scaling laws, but many modern architectures are better described as neural computation graphs with heterogeneous merge rules rather than by depth alone. We develop a unified merge calculus for learning-rate scaling on such graphs. Its central object is a graph-aware complexity coefficient that combines local merge semantics with global path structure and induces a $-1/2$ power law for the target learning-rate scale. We further show that depth alone is generally insufficient once merge semantics vary across architecture families. We validate the framework on controlled graph families and lightweight representative architectures covering uniform sum, residual-aware sum, concat, weighted fusion, and hybrid designs. Across these settings, the resulting graph coefficients organize optimal learning rates more effectively than depth alone and support practical learning-rate transfer.

Multimodal large language models (MLLMs) have rapidly advanced machine intelligence by integrating visual perception with powerful linguistic reasoning. However existing visual backbones predominantly encode videos in a rigid per-frame manner and delegate temporal modeling entirely to the language model. This paradigm fundamentally constrains long-range temporal understanding and imposes severe computational inefficiencies. To resolve these bottlenecks we propose FuxViT, a unified Vision Transformer natively supporting a 64K-token context window to seamlessly process diverse inputs ranging from static images to hour-scale videos. By employing a joint spatiotemporal pretraining paradigm, FuxViT generates highly coherent and information-rich visual representations. This strategic early fusion frees the downstream language model from reconstructing low-level temporal structures to focus entirely on high-level reasoning. Furthermore we introduce Frame Selective Attention (FSA) as a native sparse routing mechanism. FSA dynamically attends to the most relevant historical frames to achieve exceptional computational efficiency without sacrificing fine-grained spatial or temporal details. Extensive experiments across 16 image and video benchmarks demonstrate that FuxViT consistently outperforms existing baselines and establishes itself as a vastly superior alternative to standard static ViTs for multimodal understanding. We will fully open-source all model checkpoints.

Leveraging Graph Neural Networks (GNNs) as graph encoders and aligning the resulting representations with Large Language Models (LLMs) through alignment instruction tuning has become a mainstream paradigm for constructing Graph Language Models (GLMs), combining the generalization ability of LLMs with the structural modeling capacity of GNNs. However, existing GLMs that adopt GNNs as graph encoders largely overlook the problem of aligning GNN-encoded representations across domains and tasks with the LLM token space to obtain unified graph tokens, thereby limiting their ability to generalize across diverse graph data. To bridge this gap, we aim to incorporate a multi-domain, multi-task GNN encoder into GLMs and align its representations with LLMs to enable multi-domain, multi-task graph alignment instruction tuning. This alignment problem remains underexplored and poses two key challenges: 1) learning GNN-encoded representations that are simultaneously generalizable across domains and tasks and well aligned with textual semantics is difficult, due to substantial variations in graph structures, feature distributions, and supervision signals, together with the lack of textual-semantic alignment guidance in task-specific GNN training; 2) diverse graph data and task-specific instructions can exhibit different degrees of compatibility with the LLM token space during instruction tuning, leading to varying alignment difficulty and rendering a fixed alignment strategy suboptimal. To tackle these challenges, we propose UniGraphLM, a Unified Graph Language Model that incorporates a multi-domain, multi-task GNN encoder to learn generalizable graph representations aligned with textual semantics, and then adaptively aligns these representations with the LLM. Specifically, we first develop a graph-text pair pretraining strategy with a tailored GNN encoder, trained on large-scale graph-text data spanning multiple domains and tasks to obtain generalizable representations naturally aligned with textual semantics. We further design a curriculum alignment tuning strategy that adaptively adjusts the alignment process by accounting for varying alignment difficulty across diverse graph data. Extensive experiments demonstrate that UniGraphLM consistently outperforms state-of-the-art baselines across graph datasets from different domains and tasks.

Mechanisms for allocating a divisible resource among strategic agents have been widely studied. The prominent paradigm is the proportional (Kelly) mechanism, which elicits a scalar bid per agent, allocates the resource proportionally, and charges payments equal to the bids. Follow-up mechanisms improve social welfare, but sacrifice simplicity by introducing complex allocation rules or unintuitive payments. We introduce a unified framework for designing simple resource allocation mechanisms with proportional-style allocations and uniform pricing. Our framework yields a family of mechanisms that interpolate between the Kelly mechanism and the first-price auction. These mechanisms strictly improve upon Kelly’s efficiency guarantees, even achieving full efficiency in equilibrium, while also providing revenue guarantees relative to the VCG mechanism. In settings with budget-constrained agents, our mechanisms achieve nearly optimal price of anarchy with respect to the liquid welfare. When budgets are public, our framework further enables the design of mechanisms that ensure budget feasibility, even when agents do not explicitly account for their constraints in their strategies.

Differential Privacy (DP) bounds the privacy leakage of a mechanism against worst-case membership inference, but the precise tradeoff between complex adversarial models and DP protections remains poorly understood. In this paper, we present a unified framework that generalizes the patchwork of existing bounds across membership inference, attribute inference, and data reconstruction attacks. Crucially, our framework is the first to evaluate attacks that target multiple individuals simultaneously and measure success beyond exact matches under a single cohesive bound. Our bounds capture this broad family of previously unexplored attack settings by relying solely on the privacy parameters and the adversary's baseline success rate (i.e. its prior without access to the mechanism's output). To illustrate this, we compare our high-probability guarantees to empirical attacks in two novel settings: extracting multiple non-uniform secrets (passwords and PII) from DP-finetuned language models, and reconstructing tabular data from noisy marginals. Ultimately, this framework provides a rigorous theoretical foundation to investigate the risk landscape of DP algorithms in new adversarial settings.

We present UniALM, a unified audio foundation model built on FactorCodec, a purely discrete tokenizer that factorizes audio into two role-separated representations. Analysis tokens are optimized to retain language-aligned, text-expressible information that can be decoded by a text LLM head into grounded natural-language analyses, while reconstruction tokens preserve the information required for waveform synthesis and are used exclusively for audio decoding. This factorization yields understanding performance competitive with continuous Whisper features on audio understanding tasks, while reducing the perplexity of reconstruction-token modeling for generation. UniALM further adopts functional layer specialization, partitioning the backbone into audio-understanding, cross-modal, and audio-generation experts. We train the model with a four-stage recipe on 100B text tokens and 60B audio tokens, together with a composed audio sequence construction strategy for unified multi-task pre-training. At 3B parameters, UniALM is competitive with strong 7B unified baselines on in-domain tasks and exhibits non-trivial \emph{compositional generalization} to unseen tasks under few-shot and zero-shot evaluation. Unlike prior unified systems that rely on hybrid continuous-discrete inputs or do not support generation beyond speech, UniALM provides a purely discrete interface for both understanding and generation across speech, sound, and music.

Video Moment Retrieval (VMR) aims to localize a temporal segment in a video based on a natural language query. While Multi-modal Large Language Models (MLLMs) are increasingly adopted for VMR due to their strong video understanding capability, they still face several limitations: (1) imprecise perception of event boundaries, (2) rigid dependency on precise object identification, and (3) inability to handle temporarily interrupted events. To address these, we propose three visual prompts: Event Segmentation (ES) prompt, Object Detection (OD) prompt, and Keyframe Marking (KM) prompt. Each prompt improves performance when applied individually, yet direct fusion degrades results because mixing prompts overcomplicates video content and inaccurate labels introduce noise. Although certain visual prompts may mislead the model, at least one of the three is likely to yield a positive effect. Even in the worst case where all three perform poorly, the prediction can fall back to the baseline. Motivated by this, we introduce a selection mechanism based on Yes/No Probability-Difference score to choose the most reliable prediction among the results produced by the three visual prompts and the baseline. We evaluate our method in a training-free setting across three datasets and four models, and obtain state-of-the-art performance.

Most temporal graph learning methods reduce future prediction to discriminative inference over past interactions, focusing on edges or node labels for a largely persistent set of nodes. This view breaks down when new nodes and edges appear, since the future graph becomes a new object with changing size, composition, and structure. We address this gap by framing temporal graph prediction as an inverse topology problem. Instead of predicting edges directly, we first predict a multiscale topological descriptor of the future graph and then reconstruct a plausible future snapshot that realizes this descriptor under inductive constraints. This approach makes global structure and node churn explicit prediction targets and produces forecasted graphs on which downstream tasks can be evaluated without retraining. Across 14 temporal graph datasets, we evaluate TopoGED on node, link and graph property prediction and compare it against state-of-the-art temporal graph models. TopoGED achieves a significant improvement in node-level forecasting accuracy over the strongest baseline, with a macro average of 0.49 versus 0.05. It also outperforms baselines in 60% of graph-structure metric evaluations and yields a substantial increase in macro-average edge prediction metrics, from near-zero to 0.12. Our results show that topology-guided graph forecasting can predict inductive future snapshots whose structure supports multiple downstream evaluations.

Chain-of-thought (CoT) reasoning has emerged as a powerful paradigm for extending the computational capabilities of transformer-based models. A growing body of recent work has begun to uncover the fine-grained computational power of transformers augmented with CoT, as well as their connections to classical complexity theory. In this work, we advance this line of research by establishing the first hierarchy theorem for \CoT-based computation. Our main result shows that for any reasonable resource bound $r(n) \geq n$ and any $\varepsilon > 0$, $$ \mathrm{CoT}(r(n)) \subsetneq \mathrm{CoT}(r(n)^{1+\varepsilon}), $$ where $\mathrm{CoT}(r(n))$ denotes the class of decision problems solvable by transformers using $O(r(n))$ CoT reasoning steps on inputs of length $n$. Our result shows that increasing the number of CoT reasoning steps provably yields strictly greater computational power, establishing CoT steps as a fundamental resource in transformer-based computation. Unlike classical hierarchy theorems, which are typically proved via diagonalization, our approach leverages known coarse-grained simulations between CoT-augmented transformers and Turing machines in both directions. Building on these connections, we adapt the classical padding technique from complexity theory to this setting to obtain a tight hierarchy. A key technical contribution of our work is the implementation of padding within the transformer-based CoT model.

In this work, we develop theoretical foundation for flow matching with neural-network–parameterized conditional velocity fields. We establish convergence guarantees for gradient descent in the over-parameterized 2-layered ReLU neural network regime. We derive generalization bounds for the conditional velocity-field matching objective. Building on these results, we provide Wasserstein-distance guarantees for the samples generated by the induced flow. Our analysis is based on generalization bound for multi-task representation learning with unbounded losses, which may be of independent interest beyond flow-based generative modeling. These theoretical results are validated through extensive experiments on both synthetic and real-world image benchmarks.

Scaling large language models (LLMs) requires tremendous computational resources, and recent advances in AI have gone hand in hand with massive amounts of capital expenditure. While it is established that scaling up LLMs reliably increases model quality (quantified in terms of loss or downstream evaluations), it is unclear how these quality improvements translate to potential revenue, and whether revenue increases would offset costs of larger-scale training and inference. In this work, we develop an economic model for characterizing the rational behavior of an LLM training firm by combining scaling laws with microeconomic theory. Under our model, LLM quality can be increased with more parameters and training tokens, leading to more potential adoption by consumers, who each have a quality threshold for using the LLM. On the other hand, additional parameters and training tokens both incur additional costs. We analyze the profit maximization problem for this model under compute-bound and data-bound regimes. In the compute-bound regime, optimal model size and token budget track hardware efficiency $E$ (FLOPs/dollar) at a near-linear rate; total training cost then scales sub-quadratically in $E$. Data efficiency improvements incentivize larger models and training expenditure. When we are limited to $D$ data, profit-optimal training expenditure scales as $D^2 / E$, i.e, increase with data and *decreases* with hardware efficiency (as well as data efficiency). Finally, we analyze practical trends in training expenditure: current trends in training expenditure are consistent with our most permissive model variants in the compute-bound regime, but are not profit-optimal in the data-bound regime or assuming hardware advances will stall. Overall, our results provide a theory of profit-optimal LLM training, providing a foundation for engaging critically with industry statements and supporting long-term economic decision making.

We study language generation in the limit under a global preference ordering on strings, as introduced by Kleinberg and Wei. We aim for breadth, but impose an additional requirement of timeliness: higher-ranked strings should be generated earlier. A string is then only credited if it is generated before a deadline, where its deadline is defined by a function that maps a string’s rank in the target language to the time by which it must be produced. This is in keeping with a central consideration in machine learning, where inductive bias favors "simpler" or "more plausible" outputs, all else being equal. We show that timely generation is impossible in a strong sense for eventually consistent generators—the protagonists of most prior related work. Under what is perhaps the mildest natural relaxation of consistency, a hallucination rate that vanishes over time, we show that we can circumvent our impossibility result. In particular, we can achieve optimal density with respect to any superlinear deadline function. We also show this is tight by ruling out timely generation with linear deadlines and vanishing hallucination rate.

Spatial cognition requires stable neural manifolds of orientation and location that track self-motion and sensory cues. Continuous attractors provide a natural dynamical principle, but learning such mechanisms that form and control manifolds with theoretical guarantees remains difficult. We propose Spatial Energy Attractor Learning (SEAL), a theory of neurodynamics learning for spatial cognition, where continuous spatial representations arise as learned low-energy manifolds in Hopfield energy landscapes through population-level Fourier energy learning. For head-direction and grid-cell systems, Fourier energy landscapes yield ring and torus attractors with learned normal attraction and input-driven tangent transport. We prove that Fourier construction is a special case of a general Hopfield-compatible energy extension whose autonomous dynamics preserve energy descent and whose expressive energy families approximate target attractor energies and restoring fields. Experiments on HD and grid-cell populations show that the learned energies restore perturbed states to ring and torus manifolds, stabilize velocity-driven moving bumps across multiple input regimes, and induce continuous-attractor interactive structures with local excitation and surround inhibition. Together, these results provide a stable, learnable, and biologically interpretable energy-based account of continuous spatial representation.

Autoregressive generation lies in the heart of the mechanism of large language models. It can be viewed as the repeated application of a next-token generator: starting from an input string (prompt), the generator is applied for $M$ steps, and the last generated token is taken as the final output. [Joshi et al., 2025] proposed a PAC model for studying the learnability of the input-output maps arising from this process. We develop an online analogue of this framework, focusing on the mistake bound of learning the final output induced by an unknown next-token generator. We distinguish between two forms of feedback. In the End-to-End model, after each round the learner observes only the final token produced after M autoregressive steps. In the Chain-of-Thought model, the learner is additionally shown the entire $M$-step trajectory. Our goal is to understand how the optimal mistake bound depends on the generation horizon $M$, and to what extent observing intermediate tokens can reduce this dependence. Our main results show that the online theory of autoregressive learning exhibits a qualitative picture analogous to the statistical one found by [Hanneke et al., 2026], but with a different scale of dependence on the generation horizon. In the End-to-End model, we prove a taxonomy of possible mistake-bound growth rates in the generation horizon $M$: subject to mild regularity conditions, every rate between constant and logarithmic can arise. We also show that this logarithmic ceiling is unavoidable for the online setting, in the sense that every class of finite Littlestone dimension exhibits at most logarithmic dependence on $M$. In the Chain-of-Thought model, the parallel is even sharper: as in the statistical setting, access to the full generated trajectory eliminates the dependence on $M$ altogether. We also analyze autoregressive linear threshold classes. For autoregressive linear thresholds in \(\mathbb{R}^d\), we prove that the optimal mistake bound is \(\Theta(d^2)\) under both End-to-End and Chain-of-Thought feedback, and for any generation length $M$. The methods developed for this analysis also yield new lower bounds in the statistical setting. Along the way, our results resolve several questions left open by [Joshi et al., 2025]. In particular, we show that even for classes of finite Littlestone dimension, the End-to-End statistical sample complexity can depend on the generation length M.

We introduce the problem of *adversary-directed* online learning, in which the learner is aware of the set of instances in advance, and an adversary adaptively determines their ordering during the learning process. Surprisingly, this formulation has not been previously studied, perhaps due to its conceptual resemblance to the traditional adversarial online learning problem, despite related models, including the transductive, self-directed, and best-order, having been extensively explored. However, by utilizing novel techniques, we demonstrate that the landscape of adversary-directed online learning significantly diverges from that of traditional adversarial online learning. In the realizable setting, we establish a trichotomy of possible rates of the minimax number of mistakes. Specifically, for a learning horizon $\operatorname{T}$, the minimax number of mistakes can only be of the orders $\Theta(\operatorname{T})$, $\Theta(\log \operatorname{T})$, or $\Theta(1)$. To prove this, we introduce a new combinatorial complexity parameter, termed the perfect Littlestone dimension, whose finiteness distinguishes the $\Theta(\log \operatorname{T})$ rate from the $\Theta(\operatorname{T})$ rate. On the other hand, in the agnostic setting, we essentially show a dichotomy of possible rates of the minimax expected regret. In particular, if the learner plays for $\operatorname{T} \in \mathbb{N}$ rounds, its minimax expected regret can only be of the orders $\Theta(\operatorname{T})$, or $\widetilde{\Theta}(\sqrt{\operatorname{T}})$, which is also characterized by the finiteness of the perfect Littlestone dimension. Technically, a key ingredient in the proof of our $\mathcal{O}(\log \operatorname{T})$ and $\widetilde{\mathcal{O}}(\sqrt{\operatorname{T}})$ upper bounds is a novel online learning algorithm that leverages a new notion of shattering based on the perfect Littlestone dimension, which exploits the adaptive adversarial nature of the problem.

Self-play, a type of training algorithm that enables a model to self-improve, has recently shown promising empirical results in the context of formal theorem proving using Large Language Models (LLMs). (Dong & Ma, 2025) instantiate self-play with two cooperating agents: a prover, which proves theorems, and a conjecturer, which generates new theorems as a curriculum to the prover. In this paper, we provide a theoretical framework for understanding the self-improvement capabilities of self-play algorithms for theorem proving. First, we formalize the set of theorems as a graph, with nodes as theorems and edges between pairs of theorems with similar semantics. We introduce a set of primitive assumptions that characterize the guarantees of a trained prover and how a conjecturer can access the structure of the graph. Second, we show that if the underlying graph of theorems is well-connected, then a prover-conjecturer system, where the conjecturing algorithm is based on a reversible random walk, is sufficient to grow the set of proved theorems exponentially. Third, we formulate an issue of diversity encountered empirically by self-play algorithms in our framework, where the conjecturer tends to generate artificially complex and non-fundamental theorems. We propose a diversity measure for a training distribution of theorems generated by a conjecturer and an improved conjecturing algorithm that locally maximizes this diversity measure, by computing the diffusion similarity between neighboring theorems in the theorem graph. Finally, we describe a method to compute the diffusion similarity by first using contrastive learning to embed nodes into Euclidean space and second computing the inner-product between the embeddings.

We theoretically and empirically establish a previously unexplored connection between Long-Tailed Recognition (LTR) and Continual Learning (CL). Specifically, we show that training on a long-tailed dataset drives model parameters into an $\mathcal{O}(1/\sqrt{\mathrm{IF}})$ neighborhood of the dominant-class solution, under both uniform and exponentially decaying cardinality distributions. Building on this result, we prove that the CL objective upper-bounds the balanced LTR loss, revealing that LTR can be reformulated as a sequential learning problem. Motivated by this connection, we introduce Continual Learning for Long-Tailed Recognition (CLTR), a principled framework that leverages standard off-the-shelf CL methods to sequentially learn Head and Tail classes while mitigating catastrophic forgetting. Extensive experiments on CIFAR100-LT, CIFAR10-LT, ImageNet-LT, and Caltech256 validate our theoretical predictions and demonstrate strong performance across diverse LTR benchmarks. In the foundation-model regime, CLTR with DualPrompt on a CLIP backbone outperforms standard adaptation baselines and is competitive with specialized methods using external semantic supervision. Our work bridges LTR and CL both theoretically and empirically, providing a principled approach for addressing long-tailed learning using standard CL strategies.