NeurIPS 2026 Papers

We study stochastic linear bandits under a natural combination of batching and communication constraints: the time horizon is partitioned into batches of equal size $B$, and during each batch the learner sends $B$ requested arm pulls to an agent, who then observes the corresponding $B$ rewards and responds with a single bit of feedback to the learner. For each batch, the learner specifies the 1-bit quantization rule the agent uses, which may depend on all previously received bits but not on any past rewards directly. This setting addresses a significant yet unexplored ``middle ground'' between previous models having per-round quantization only $\textit{or}$ total bit budgets only. We establish a minimax lower bound showing that $\Omega(B\min \lbrace d,\log\lvert \mathcal{A} \rvert \rbrace)$ regret is unavoidable due to the 1‑bit communication bottleneck, even in the absence of noise. Combined with standard statistical limits, this yields a general lower bound of $\widetilde{\Omega}(B\min\lbrace d,\log\lvert \mathcal{A} \rvert \rbrace + \sqrt{dT \min \lbrace d,\log\lvert \mathcal{A} \rvert\rbrace })$. We develop two phased‑elimination algorithms based on $G$-optimal designs and 1‑bit mean estimation. The first achieves $\widetilde{O}(dB + d\sqrt{T})$ regret, matching the lower bound up to logarithmic factors when $\lvert \mathcal{A} \rvert = \exp(\Omega(d))$, and the second incorporates a safe‑arm identification and warm‑start procedure to obtain $\widetilde{O}(B\log\lvert \mathcal{A} \rvert + d^{3/2}\sqrt{B} + \sqrt{dT\log\lvert \mathcal{A} \rvert})$ regret, which is near‑optimal in broad scaling regimes of $(\lvert \mathcal{A} \rvert, B, d,T)$. Together, our results demonstrate that a single bit of feedback per batch suffices to preserve nearly order‑optimal regret across a wide range of settings, even in the case of large batch sizes such as $\Theta(\sqrt{T})$.

Large language models have achieved remarkable capabilities by scaling model capacity and training data, yet many practical deployments still rely on smaller models with limited resources whose capabilities lag behind their larger counterparts trained with richer resources. This gap calls for efficient knowledge transfer from source models with richer resources to compact target models. While model merging provides an effective mechanism, most existing methods are based on the assumption that the source and target models are architecturally compatible, making them inapplicable to heterogeneous source and target pairs. Although a recent method based on optimal transport extends model merging to settings with different architectures, it remains limited by linear correspondence modeling, iterative transport optimization, and reliance on supervised adaptation after fusion for further performance gains. To address these limitations, we propose BDC-Merge, a framework for model merging across different architectures based on Brownian Distance Correlation (BDCorr). BDC-Merge uses a small calibration set to estimate dependencies between heterogeneous activations at the feature level and the layer level, and directly lifts these dependencies from activation space into fusion operators in weight space, enabling effective parameter fusion across different architectures without any gradient based optimization or training after fusion. Extensive experiments across four low resource language and two specialized knowledge benchmarks show that BDC-Merge consistently outperforms the state of the art baseline for model merging across different architectures and largely preserves the target model’s general capabilities.

We study attention mechanisms through the lens of a canonical unsupervised problem: principal component analysis (PCA). We show that, when trained on Gaussian data, both softmax and linear attention layers learn parameters that align with the principal eigenvectors of the covariance matrix, thereby establishing a direct and explicit connection with PCA. Our analysis covers both finite and infinite prompt regimes. In the infinite-prompt limit, we prove convergence to globally optimal solutions aligned with the leading spectral direction, while in the finite-prompt setting we show that the same behavior emerges up to sampling effects. We further extend the analysis to an in-context setting with spiked Wishart covariances, where attention successfully recovers the underlying signal direction. These results demonstrate that attention inherently performs PCA-like computations under unsupervised objectives, providing a theoretical foundation for its representation-learning capabilities.

Directed Acyclic Graphs (DAGs) are foundational to many areas of AI research, providing a formal language for causal reasoning and model interpretability. However, learning DAGs remains challenging, due to super-exponential computational cost and diminished accuracy in small sample regimes. To address these challenges, we introduce Attention-DAG (ADAG), a novel linear transformer architecture for unsupervised amortized DAG learning. Unlike traditional unsupervised DAG learning methods which recover the graph structure from data of each individual domain, ADAG leverages the knowledge from multiple domains. It provides a nonlinear mapping from observational data of each domain to both the corresponding graph structure and the underlying parameters of Structural Equation Models (SEMs). This enables efficient zero-shot inference of causal structures in new domains with unseen SEM parameters. Remarkably, we demonstrate that for DAG learning problem attention acts as a fixed-point iterative scheme, so the training on multiple domains effectively discovers an efficient solver for the constraint optimization problem. Extensive evaluations on synthetic and realistic benchmarks demonstrate that ADAG significantly outperforms existing baselines in accuracy and efficiency, particularly when data is scarce.

Deep click-through rate (CTR) models commonly consist of sparse embedding blocks and feature-interaction blocks, which jointly learn predictive signals from high-dimensional categorical features. This naturally raises the question of whether different blocks in an end-to-end trained CTR model play the same role in generalization. To address this question, we investigate the generalization behavior of deep CTR models from a block-wise diagnostic perspective. Specifically, we formulate deep CTR models as two-block systems comprising an embedding block and a feature-interaction block, and introduce a retuning-based diagnostic protocol to separately assess the transferability of different blocks. Experiments across multiple datasets and architectures reveal a consistent asymmetric generalization pattern: the embedding block exhibits stronger training-set specificity, whereas the feature-interaction block preserves comparatively more transferable structure. Motivated by this diagnosis, we further develop a component-selective embedding aggregation method that averages multiple independently retuned embedding tables while keeping the feature-interaction block fixed. The resulting model retains the original single-path inference architecture and incurs no additional online inference cost. Experiments on Avazu, Criteo, and Taobao show that the proposed method improves representative deep CTR models over standard training and retuning baselines.

Contrastive representation learning (CRL) is a fundamental paradigm for learning transferable representations. Recent work identifies its population target as the pointwise mutual information (PMI) $ \log\frac{p(\mathbf{x},\mathbf{y})}{p_\mathcal{X}(\mathbf{x})p_\mathcal{Y}(\mathbf{y})} $ between two modalities $\mathcal{X},\mathcal{Y}$, where $p$ is the joint density function and $p_\mathcal{X},p_\mathcal{Y}$ are the marginals. However, it remains unclear why standard inner-product scores $f(\mathbf{x})^\top g(\mathbf{y})$ can effectively approximate a generally nonseparable population target PMI. In this paper, we address this question from the aspect of approximation for CRL. By linking PMI to a compact operator, we show that $D$-dimensional inner-product models perform rank-$D$ spectral approximation, with error controlled by the spectral tail. We then study neural network realizations: in general settings, we show that deep neural network scoring functions are universally consistent, and the approximation error rates depend on the smoothness of the PMI function; under structured low-rank data models we obtain improved rates attained by moderate-width encoders. Finally, we establish a fast calibration rate from contrastive excess risk to downstream retrieval error under a density-ratio Tsybakov noise condition.

Principal component analysis (PCA) is one of the most widely used unsupervised dimension reduction techniques. We study PCA for data from multiple related domains. Since principal components generally differ across domains, one way to obtain a shared low-rank embedding is to perform PCA on the pooled data. However, this approach can focus on spurious directions that exhibit high variation in only a few domains. To find a robust embedding that still explains most variance in unseen but similar domains, we propose instead to focus on shared directions of variation. To this end, we introduce Anchor PCA which trades off overall explained variance with agreement between the shared and domain-specific low-rank embeddings. Anchor PCA amounts to PCA on a modified target matrix and thus can be solved efficiently. Moreover, we show that Anchor PCA recovers a maximal invariant subspace and admits a minimax reconstruction interpretation under bounded domain-specific covariance inflations. On simulated and real-world gas sensor data with temporal drift, we demonstrate, respectively, that Anchor PCA recovers the maximally invariant subspace and yields embeddings that explain more variance on unseen domains than the pooling baseline and a worst-case alternative. Taken together, these findings establish Anchor PCA as a promising approach to robust unsupervised dimension reduction from multi-domain data.

Modern foundation models are trained through multistage pipelines, typically beginning with unsupervised pretraining, followed by supervised fine-tuning (SFT) on step-by-step solutions, and reinforcement learning (RL) with bulk feedback. Empirically, the design of these stages, particularly the compute allocated to each, strongly affects performance. Yet our theoretical understanding of multistage training remains limited. Here, we introduce a simple, analytically tractable model of multistage training. The model reproduces several qualitative phenomena: SFT and RL can be complementary, pretraining quality imposes a performance ceiling with power-law scaling, optimal compute allocation varies with data quality and pretraining level, and RL can selectively amplify task-relevant pretrained skills. Our model distills the complex behaviors into key ingredients, allowing clearer understanding of how and where they arise. Overall, our model provides a theoretical starting point for explaining the phenomenology of multistage training pipelines in the compute-limited regime.

We consider linear equations with min and max operators~(LEMMs) that contain many subproblems ranging from optimization, learning, to games. Recently, Chatterjee et al. [2025] gave a systematic study of the complexity of different subclasses. Three key subclasses--(I) halting branching process, (II) absolutely halting LEMMs, and (III) halting LEMMs--are proved to be in UP $\cap$ coUP while generalizing stochastic games (SSGs). In this work, we study the classic algorithms of Policy Iteration (PI) and Value Iteration (VI) for these general subclasses. First, we simplify the problem hierarchy by showing the equivalence between halting branching process and SSGs. Then, we show that while PI diverges for absolutely halting LEMMs due to the loss of monotonicity, VI remains convergent, a result we establish via diagonal rescaling. Finally, we show that neither PI nor VI converges for general halting LEMMs and, to this end, propose variants of simple policy iteration that ensure convergence across all subclasses.

Humans, animals, and modern machine learning models exhibit impressive abilities to learn complex behaviors and generalize these behaviors to unseen situations. This ability requires us to learn rules and regularities that allow for such generalizations. At the same time, in most complex environments, any rule will have its exceptions. How do learning systems balance between learning general regularities and memorizing exceptions? We argue that a lack of task paradigms has hindered the study of this essential ability. To address this gap, we introduce a novel task, transitive inference with exceptions, that tests for relational generalization and memorization of an exception to the relational rule. We then analytically characterize the behavior of a simple, theoretically tractable model of neural network learning (kernel ridge regression) across a broad family of representations and task parameters. We find that these models can balance between relational generalization and memorization, but unlike for transitive inference without an exception, successful generalization is sensitive to the specific representational geometry. We explain why this task is more challenging mechanistically by drawing on our analytical theory. Finally, we validate our theoretical insights in pretrained language models that are finetuned on ordered relations, finding that these models successfully generalize according to the transitive rule, but also make the kinds of systematic mistakes predicted by our theory. Overall, our theory shows how learning systems can balance between relational generalization and memorization, explains how this can go wrong, and emphasizes the need for new task paradigms designed to probe this ability.

Kernel methods, and Gaussian Processes (GPs) in particular, require a conditionally negative-definite (CND) distance measure to guarantee positive semi-definiteness (PSD) of the kernel matrix — a condition that fails for many natural input spaces, including smooth manifolds and spaces of probability distributions. We propose the Sparse Landmark Embedding (SLE) kernel, which eliminates this requirement entirely. Each input is embedded into a sparse feature vector via compactly supported bump functions centered at all training points $|\mathcal{D}|$; applying any standard PSD kernel in this embedding space yields a kernel that is provably PSD for arbitrary distance measures. The compact support automatically controls embedding sparsity, keeping kernel matrices well-conditioned and computationally tractable despite the high ambient dimension. We provide theoretical guarantees on PSD, sparsity, stability, and universal approximation, and demonstrate, using geodesic and Wasserstein distances, that the SLE kernel matches or substantially exceeds domain-specific baselines in both predictive accuracy and uncertainty quantification.

Vision-language models are designed to capture the compositional structure of the world through multi-modal alignment; however, it remains unclear whether their representations truly align with the way a human would naturally describe the same visual input. Prior works attempt to decompose visual embeddings into their concept-level contributions, but their instance-level optimization is inherently local and does not capture the model’s global semantic structure, which is essential for compositional generalization across different inputs, tasks and domains. We introduce GRACE, a method that learns this concept-based structure at the feature space level, producing semantic and general concept decompositions. To achieve this, we propose a novel training objective that preserves the geometric relations of different samples in the concept space, enabling a better understanding of how concepts compose and relate to each other. We validate GRACE on several image and video benchmarks, showing that its concept decomposition is aligned with human perception and achieves faithful decompositions across different tasks and domains. With minimal overhead, GRACE makes existing Vision-Language Models more interpretable, while preserving most of their original performance.

Recent work shows that preference alignment objectives can be interpreted as divergence estimators between aligned (preferred) \& unaligned (less-preferred) distributions, yielding a principled recipe for designing alignment losses. However, this view has so far been limited to preference-based supervision. We extend it to general LLM alignment, including reinforcement learning with verifiable rewards (RLVR), where alignment feedback is given only as scalar rewards. We introduce $f$-Group Relative Policy Optimization ($f$-GRPO), a class of on-policy RL objectives, and $f$-Hybrid Alignment Loss ($f$-HAL), which combines on-policy reward optimization with off-policy preference supervision. We show that these objectives estimate $f$-divergences between reward-aligned \& reward-unaligned distributions induced by above- \& below-average reward responses, and prove expected reward improvement after alignment. Empirically, $f$-GRPO improves over GRPO on math-reasoning RLVR tasks, while hybrid $f$-HAL mitigates reward hacking in on-policy safety alignment when verifiable rewards are unavailable and learned reward models must be used.