NeurIPS 2026 Papers

This work proposes a framework for public decision processes with a monetary component, where voters can pledge donations to support preferred projects and influence the allocation of public funds. It captures a range of real-world scenarios, including participatory budgeting, blockchain-based funding platforms, charitable programs, and crowdfunding campaigns. Through both theoretical and experimental evaluation, our study addresses questions concerning the existence, structure, number, computation, and quality of Nash equilibria.

This paper studies the $\varepsilon$-best arm identification problem ($\varepsilon$-BAI) for $K$-armed bandits under the fixed-confidence setting. Departing from the usual objective of identifying the best arm with minimal sample complexity, we focus on minimizing the cumulative regret of identifying an $\varepsilon$-best arm. We consider the usual asymptotic regime in which the error probability $\delta$ of identifying an $\varepsilon$-best arm vanishes. In this setting, we show a novel instance dependent lower bound. In particular, we show that any family of $(\varepsilon,\delta)$-PAC algorithms must incur an expected cumulative regret up to the stopping time that scales as $\log(1/\delta)$, with an instance-dependent constant $C(\mu)$. This is proved using a novel regret-aware change-of-measure technique that allocates information given a budget on the regret. To achieve this lower bound, we devise an algorithm, \algname, that achieves the same scaling in $\delta$, i.e., $\log (1/\delta)$, but with a different constant, which we call $C^\*(\mu)$. KL-UCB+Greedy has two main benefits: (i) it is computationally efficient as $C^\*(\mu)$ admits a closed-form expression; (ii) in broad classes of reward distributions such as Gaussian distributions, $C^\*( \mu) = C( \mu)$, demonstrating asymptotic optimality of KL-UCB+Greedy within these classes. As auxiliary results, we also derive lower bounds on the sample complexity of any family of $(\varepsilon,\delta)$-algorithms as $\delta$ vanishes and show that the sample complexity of KL-UCB+Greedy closely matches that of the lower bound on the sample complexity.

Respecting a-priori known symmetries of underlying data is a key principle in designing efficient neural architectures. Convolutional Neural Networks (CNNs) are a canonical example, encoding translation equivariance. Extending this inductive bias to richer symmetry groups such as $\mathrm{SE}(2)$ in the most effective way possible is an ongoing architectural and computational challenge. Building on classical invariant theory, we derive invariant feature maps that are provably optimal: minimal and information-preserving with respect to the symmetry group. Our construction is designed to integrate seamlessly into standard architectures, requiring no modification to nonlinearities or normalization layers. As a concrete implementation, we introduce a plug-and-play module for CNNs that enforces $\mathrm{SE}(2)$ invariance, capturing both translations and rotations within standard architectures. The resulting models are both efficient and expressive. Experiments show competitive or improved accuracy compared to state-of-the-art equivariant methods at significantly lower computational cost. Finally, we provide a theoretical and empirical analysis of the relationship between equivariance and invariance, offering insight into their roles in controlling robustness and flexibility.

The Lipschitz constant of a neural network is a basic stability quantity appearing in optimization guarantees, generalization bounds, and robustness certificates. Deep networks naturally admit two such notions, \emph{input Lipschitzness}, measuring sensitivity to data perturbations, and \emph{parameter Lipschitzness}, measuring sensitivity to weight perturbations. We prove that, for deep networks with normalization layers, with batch normalization as the canonical example, \emph{both} Lipschitz constants can grow exponentially with depth and hence with parameter dimension, even under strong per-layer norm control such as $\\|W_\ell\\|_2\le 1$, and already for linear activations. Thus, a mechanism widely used to stabilize training can create severe worst-case instabilities that are invisible from layerwise norm bounds alone. Parameter-Lipschitz explosion turns Lipschitz-dependent nonsmooth optimization guarantees into exponential-in-dimension bounds for deep normalized networks, while input-Lipschitz explosion makes worst-case Lipschitz-based generalization and robustness certificates vacuous. The latter also yields a concrete rank-separation mechanism for adversarial vulnerability. The theory predicts that perturbations introducing new singular directions should be amplified much more strongly than equal-energy perturbations that remain within the input's original singular subspace. Experiments on MNIST, Fashion-MNIST, and CIFAR-10 support this prediction, showing that rank-creating perturbations cause substantially sharper drops in accuracy, confidence, and margins than same-subspace perturbations.

Sentence-level EEG-to-text decoding models typically pad variable-duration neural signals to a fixed-length window, creating a structural confound where segment duration correlates with sentence identity independently of neural content, a problem we term length bias. Despite being acknowledged in prior work, the prevalence, magnitude, and architectural dependence of this effect have never been systematically quantified. We introduce length-matched noise baselines that isolate this confound by replacing only the true signal region with Gaussian noise while preserving zero-padding, and apply them across three English listening EEG datasets under a strict subject-held-out protocol. Evaluating ten sentence classifiers and three generation models based on the current state-of-the-art, we show that reported decoding scores are substantially inflated by length cues across datasets, with the degree of inflation varying markedly by architecture. Among classifiers, BIOT alone is unaffected by length-matched noise. A systematic decomposition of its components identifies Short-Fourier-Transform (STFT) tokenisation as the bigger source of this invariance. We transfer this finding into two new generation variants that largely eliminate encoder-side length bias, enabling a controlled analysis of where residual bias originates. A classification-to-generation evaluation further reveals that leading generation models operate largely as sentence retrieval systems, with a linear classifier recovering nearly all of their reported BLEU-4 scores. Together, these results establish that length bias is a pervasive and previously unquantified failure mode in EEG-to-text evaluation, and provide both diagnostic tools and architectural directions for future work.

We study the empirical risk minimization (ERM) of linear Joint Embedding Predictive Architecture (JEPA) and establish its key conditions for optimality. By casting the embedding bottleneck as a rank constraint, we formulate JEPA as a reduced-rank regression problem. This induces a risk decomposition into an irreducible error and an excess-risk bound. Within the irreducible term, we find the rank of the optimal predictor grows with target heterogeneity and saturates at the bottleneck. Within the excess-risk bound, we find spectral conditioning of the whitened end-to-end predictor governs minimization. Together, these conditions prescribe an isotropic regularizer. Under this regularization, we show such JEPA isotropy subsumes canonical JEPA isotropic embedding designs and hence justifies their empirical successes via ERM. Numerical experiments corroborate our theory.

Differential Privacy (DP) provides a rigorous framework for quantifying privacy guarantees. While most methods achieve DP by injecting calibrated random noise, the intrinsic randomness of certain procedures such as sampling can yield DP guarantees ``for free''. In this work, we develop a unified R\'enyi divergence framework to characterize the inherent DP guarantees of sampling from a Bayesian posterior distribution. We show that the privacy loss incurred by One-Posterior-Sampling (OPS) is governed by posterior exponential moments of the single-record log-likelihood ratio, and establish explicit DP guarantees under uniformly bounded, sub-Gaussian, or sub-exponential tail regimes. We apply the framework to representative Bayesian models, including categorical likelihoods with arbitrary priors, Gaussian-Gaussian conjugate pair, generalized linear models from the exponential family and linear regression with Gaussian likelihood, both with Gaussian priors on the regression coefficients. Our results elucidate sample size, model structure, neighboring relations in DP (bounded or unbounded), and how prior if applicable, jointly determine the inherent DP guarantees of OPS. Furthermore, our results recover the existing DP guarantees for OPS as special cases -- often with tighter privacy loss bounds -- and substantially broaden the class of Bayesian models for which the inherent DP guarantees of OPS can be rigorously characterized.

We study the classic least-squares linear regression problem under differential privacy (DP) in the continual observation setting. In this setting, the mechanism receives a stream of $n$ data points $(x_i,y_i)$ ($x_i\in\mathbb{R}^d$ and $y_i\in\mathbb{R}$) and must output an estimate of the optimal parameters at each time step $i$. Although differentially private linear regression has been extensively studied in the batch setting, the problem remains underexplored for the continual setting, with prior work being restricted to constrained linear regression and update time polynomial in $n$. In this work, we introduce ContinualAdaSSP, the first mechanism for unconstrained linear regression under continual differential privacy. Our mechanism's suboptimality gap is proportional to $\sqrt{d}\operatorname{polylog}(n)$. It requires $O(d^2\log{n})$ space and $O(d^2\log{n}+d^{\omega})$ ($\omega$ is the matrix multiplication exponent.) update time, where $d$ is the dimension of the input space. This matches the suboptimality gap of the continual mechanism for the constrained version. We also study fundamental limits of differentially private linear regression by showing the first lower bounds for the box-constrained least-squares linear regression problem. Our lower bounds are proportional to $\min(n,\frac{\sqrt{d}}{\log^{1.5}d})$ for $(1,O(\frac{1}{n}))$-DP, and $\min(n,\frac{d}{\varepsilon})$ for $\varepsilon$-DP, and are derived using a reduction from a fingerprinting code problem from [Peter et al, 2024], providing new insights into the inherent hardness of this canonical task. Our experimental evaluation on real-world datasets shows that the accuracy of our mechanism clearly outperforms any other known differentially private mechanism for this problem such as rerunning the batch algorithm at each time step.

We introduce a refined differentially private (DP) data structure for kernel density estimation (KDE) with $\ell_1$, $\ell_2$ and $\ell_p^p$ kernels. This new DP data structure offers not only improved privacy-utility tradeoff but also better query efficiency over prior results. Specifically, we study the mathematical problem: given a similarity function $f$ (or DP KDE) and a private dataset $X \subset \mathbb{R}^d$, our goal is to preprocess $X$ so that for any query $y \in \mathbb{R}^d$, we approximate $\sum_{x \in X} f(x, y)$ in a differentially private fashion. The best previous algorithm for $f(x, y) = |x - y|_1$ is the node-contaminated balanced binary tree by [Backurs, Lin, Mahabadi, Silwal, and Tarnawski, ICLR 2024]. Their algorithm requires $O(nd)$ space and time for preprocessing with $n = |X|$. For any query point, the query time is $\alpha^{-1} d \log^2 n$, with an error guarantee of $(1+\alpha)$-approximation and $\varepsilon^{-1} \alpha^{-0.5} d^{1.5} R \log^{1.5} n$. In this paper, we use the same space and pre-processing time, improve the best previous result [Backurs, Lin, Mahabadi, Silwal, and Tarnawski, ICLR 2024] in three aspects - We reduce query time by $\alpha^{-1} \log n$ factor - We improve the approximation ratio from $\alpha$ to $1$ - We reduce the error dependence by a factor of $\alpha^{-0.5}$ From a technical perspective, our method of constructing the search tree differs from previous work [Backurs, Lin, Mahabadi, Silwal, and Tarnawski, ICLR 2024]. In prior work, for each query, the answer is split into $\alpha^{-1} \log n$ numbers, each derived from the summation of $\log n$ values in interval tree countings. In contrast, we construct the tree differently, splitting the answer into $\log n$ numbers, where each is a smart combination of two distance values, two counting values, and $y$ itself. We believe our tree structure may be of independent interest.

Despite rapid recent progress in the terminal capabilities of large language models, the training data strategies behind state-of-the-art terminal agents remain largely undisclosed. We address this gap through a systematic study of data engineering practices for terminal agents, making two key contributions: (1) Terminal-Task-Gen, a lightweight synthetic task generation pipeline that supports seed-based and skill-based task construction, and (2) a comprehensive analysis of data and training strategies, including filtering, curriculum learning, long context training, and scaling behavior. Our pipeline yields Terminal-Corpus, a large-scale open-source dataset for terminal tasks. Using this dataset, we train Nemotron-Terminal, a family of models initialized from Qwen3 (8B, 14B, 32B) that achieve substantial gains on Terminal-Bench 2.0: Nemotron-Terminal-8B improves from 2.5% to 13.0%, Nemotron-Terminal-14B improves from 4.0% to 20.2%, and Nemotron-Terminal-32B improves from 3.4% to 27.4%, matching the performance of significantly larger models. We release Nemotron-Terminal checkpoints and Terminal-Corpus through the Nemotron-Terminal Hugging Face collection.

This paper studies concentration inequalities for sampling without replacement. We introduce a general inequality that provides simple guidelines for proving concentration inequalities, offers a degree of unification of existing results, and is strong enough to yield sharper bounds. As applications, we revisit several standard statistics and either recover classical inequalities through streamlined proofs or strengthen them to tighter bounds, with rates optimal up to constants.

Traffic scene understanding requires models to reason beyond object recognition, including lane topology, multi-view geometry, temporal evolution, and signal-phase semantics. However, existing traffic-oriented multimodal benchmarks largely emphasize passive visual recognition or isolated video understanding, offering limited support for evaluating structure-aware traffic reasoning under controlled conditions. We introduce \textbf{OmniTraffic}, a controllable generation pipeline and benchmark for spatio-temporal traffic reasoning. Built around 12 real-world intersections reconstructed into editable 3D traffic environments and complemented by surveillance footage from two countries, OmniTraffic supports both controlled and natural-condition evaluation. It defines a three-level task hierarchy spanning scene perception, multi-view and temporal reasoning, and decision support. Using structured traffic metadata, OmniTraffic generates synchronized multi-view VQA samples covering vehicle states, lane functions, view--BEV correspondence, temporal dynamics, and signal-phase analysis, resulting in 8M VQA samples and a 3K human-verified test set. Evaluation of eleven frontier MLLMs reveals a large human--model gap, with the most pronounced failures in topology-grounded and spatio-temporal reasoning tasks. Fine-tuning a lightweight MLLM on simulated OmniTraffic data further improves performance on real-world traffic scenes, demonstrating the value of simulation-generated supervision for traffic-specific multimodal reasoning. Beyond a fixed dataset, OmniTraffic provides an extensible pipeline with configurable intersections, camera views, traffic demands, signal phases, visual conditions, and rare events.

Theory of Mind (ToM), the ability to infer others’ knowledge, intentions, and emotions, is commonly evaluated in large language models (LLMs) using end-point question answering, where performance is judged solely by the final answer to a social reasoning query. This paradigm obscures whether the model actually constructs the underlying mental-state representations required for robust reasoning, particularly in scenarios involving divergent, evolving, or mistaken beliefs. In order to address this research gap, we introduce OmniToM, a benchmark that directly evaluates these representations by requiring explicit modeling of belief structures for all relevant actors within a narrative. These structures are composed of belief propositions: minimal statements of what an actor takes to be true about the world or another actor's mental state, allowing knowledge, intentions, emotions, and false beliefs to be analyzed in a common format. Models are evaluated in two stages: Stage 1: Belief Extraction, which extracts from the story the beliefs relevant to its social dynamics, and Stage 2: Belief Labeling, which assigns each belief a seven-dimensional schema label covering recursive order, truth status, knowledge access, explicitness, content type, mental source, and context. Built from 895 stories from the existing ToMBench story corpus and augmented with 22,343 labeled belief propositions, OmniToM uses a human-calibrated LLM-assisted annotation pipeline. Across diverse models in zero-shot evaluation, OmniToM reveals an actor-specific belief-tracking bottleneck: current LLMs struggle with the knowledge-access and representational decisions required to transform narrative facts into actors’ beliefs and shared mental states.

Multimodal Large Language Models (MLLMs) have achieved remarkable performance on 2D visual tasks, yet enhancing their spatial intelligence for real-world applications such as Autonomous Vehicles (AV) remains an open challenge. Existing geometry-aware MLLMs typically rely on auxiliary 3D models at inference time, introducing pipeline complexity and the risk of cascading failures. In this paper, we present OmniSpace, a simple yet effective plug-and-play paradigm for geometry-aware spatial reasoning from purely 2D observations. Motivated by our finding that current MLLMs are bottlenecked by weak cross-view correspondence and depth estimation, OmniSpace introduces a Camera Pose Injector, a Multi-view Epipolar Attention module, and a 3D Geometric Distillation objective that jointly address these two limitations by transferring geometric knowledge into the model. Extensive experiments show that OmniSpace surpasses existing methods on planning benchmarks (nuScenes, Bench2Drive), risk detection (nuInstruct), language (Omnidrive), and generalization (DriveBench).

Large language models (LLMs) have shown great potential as general-purpose user simulators for interactive systems. Prior studies have demonstrated that training on high-quality data can substantially improve model reasoning and downstream task performance. However, the upper bound of user simulation is still constrained by the model's reasoning paradigm: standard chain-of-thought often degenerates into shallow pattern matching and fails to capture the latent mental process underlying real user behavior. In this paper, we propose OmniSimulator, a novel training framework designed to improve the predictive ability of small LLMs for realistic user simulation on short-video platform environments. Specifically, OmniSimulator models human internal deliberation through a structured reasoning schema with five dimensions, carefully selects data from real user-behavior scenarios, and introduces a teacher model to generate high-quality reasoning traces under the proposed schema, boosting small models to learn the latent logic of human decision-making during the CoT process, rather than relying on superficial behavioral correlations. Based on this process, we construct 9,881 high-quality training instances from three months of historical interaction trajectories of 200 real users, averaging about 50 distilled examples per user. Experimental results show that OmniSimulator improves performance over the baseline by 38.93\%, surpasses strong frontier models such as Claude-Sonnet-4.5, and significantly reduces inference cost. These results suggest that learning structured human-like internal reasoning is a key step toward scalable and high-fidelity LLM-based user simulation.

Omnimodal large language models (OmniLLMs) have recently gained increasing attention for unified audio-video understanding. However, processing long multimodal token sequences introduces substantial computational overhead, making efficient token compression crucial. Existing methods typically rely on fixed, modality-specific guidance, which fails to account for the varying importance of modalities across different queries. To address this limitation, we propose $\textbf{OmniSelect}$, a training-free, modality-adaptive token pruning framework that dynamically selects appropriate compression strategies for multimodal inputs. Specifically, we leverage a lightweight AudioCLIP model to estimate cross-modal relevance and categorize each input into three pruning regimes: Audio-Centric, Video-Centric, and Uniform pruning. Based on these relevance scores, OmniSelect further performs fine-grained token pruning within each temporal group, adaptively allocating pruning ratios to preserve informative tokens across modalities. By explicitly modeling modality preference and enabling dynamic strategy selection, OmniSelect effectively avoids the pitfalls of one-size-fits-all compression. Extensive experiments demonstrate that our method achieves efficient multimodal token reduction while maintaining strong performance, without requiring any additional training.

Omni-modal models are expected to reason over synchronized visual events and audio cues, yet answer accuracy alone can conceal failures in where an answer is grounded and which modality supports it. In audio-video question answering (AVQA), models may produce correct answers while relying on incorrect temporal spans, dominant-modality shortcuts, or unsupported cross-modal relations. We argue that this failure arises from treating reasoning as a completion-level prediction problem, where supervision and reward signals do not distinguish between support selection and reasoning over the support. To address this, we introduce OmniSE, a support-faithful optimization framework that makes question-conditioned audio-video support the central training object. Each QA instance is rewritten into an Audio-Visual Evidence Trace, a compact optimization unit that records temporal evidence, modality-specific cues, cross-modal relations, and cited reasoning steps. Given this support object, OmniSE first uses Support-Tree Rollout (STR) to explore alternative support hypotheses before sampling support-conditioned reasoning and answers. It then applies factorized reward assignment to score temporal localization, modality evidence, cross-modal binding, reasoning faithfulness, and answer correctness at their corresponding comparison levels. Finally, reward-gated self-consistency regularizes sibling continuations under reliable support, encouraging fixed trustworthy evidence to induce stable reasoning and answers. Experiments on multiple AVQA benchmarks show that OmniSE consistently outperforms strong open-source baselines at the same scale, demonstrating the importance of support-centric optimization for evidence-centric audio-video reasoning. Code and data would be publicly available after peer review.

Multimodal agents that interact with users over days or months must remember not only what was said, but what was shown, heard, and played. Current memory benchmarks are predominantly text-only or cover at most two modalities. Those that do incorporate multimodal content still evaluate with aggregate scores that conflate retrieval and reasoning errors, and provide no mechanism to test whether performance degrades as context scales, leaving our understanding of agent memory fundamentally incomplete. We introduce OmniMemBench, to our knowledge the first long-term memory benchmark that spans image, audio, and video in multi-session dialogue. Its design is guided by three requirements for reliable evaluation. First, an anti-leakage mechanism filters questions answerable from text alone, reducing text-only solvability to a negligible level. Second, two LLM-judged retrieval metrics—Clue Coverage and Entry Relevance—operate on content rather than entry IDs, enabling unified retrieval diagnosis across RAG and memory paradigms. The gap between retrieval coverage and downstream QA scores further localizes failures to the memorization stage. Third, content-isolated distractor injection scales context from 128K to 1M tokens while holding evidence constant, so scalability can be measured without confounding difficulty. The benchmark covers 103 characters and 6,655 QAs across 8 task types and 4 context tiers. Evaluating representative long-context, RAG, and structured-memory methods, we find that no single paradigm dominates: long-context models lead overall, yet RAG surpasses them on targeted fact extraction. Further analysis shows that memory methods retrieve clues at coverage rates comparable to RAG but score substantially lower on QA, revealing that the bottleneck is not what is retrieved but what is lost during memorization. Caption-based processing irreversibly discards perceptual details; raw embeddings degrade retrieval accuracy; and scaling the memorization model yields negligible gains.

Autoregressive (AR) video generation extends videos by producing latent chunks sequentially, but scaling to long videos requires repeated access to a growing historical KV cache. Existing methods reduce this cost by truncating the KV cache or compressing it into implicit memory, but both lose explicit access to query-relevant historical details. We propose OmniMem, an explicit full-range memory retrieval framework that performs sparse KV retrieval over the historical cache. To make this practical for chunk-based AR video generation, OmniMem addresses two issues: (i) local bias in sparse KV selection and (ii) Union Explosion in memory access. Adaptive Window Exclusion removes local-window blocks from the selection candidates when sufficient long-range history is available, preserving the sparse budget for informative long-range retrieval. Query-shared KV Selection reduces cross-query diversity, while Per-Head Scattered KV Access avoids expanding head-specific selections into a large selected KV buffer. This allows each attention head to retrieve non-contiguous KV blocks according to its own selection pattern. Experiments on long-video generation show that OmniMem improves Dynamic Degree by 52.3\% and preserves strong consistency over strong baselines, while maintaining comparable memory usage.