NeurIPS 2026 Papers

Real-world multi-view data always suffer from imperfect information problem, where the view-specific observations are absent (\ie, Incomplete Views, IV) and cross-view correspondences are mismatched (\ie, Noisy Correspondences, NC) for certain instances. As a remedy, numerous IV- and NC-oriented multi-view clustering (MvC) methods have been proposed, which however require either reliable correspondences or sufficiently complete instances, thus stopping short of addressing the imperfect information problem. In contrast, we observe that both IV and NC challenges originate from the same issue of imperfect cross-view counterpart information, where the counterpart of an anchor instance in another view might be either unavailable or unreliable. Based on the observation, we propose a novel robust MvC framework, termed Posterior-guided Latent Counterpart Inference (PLCI), which could handle both IV and NC in a unified manner. Specifically, PLCI formulates the desired cross-view counterpart of each anchor instance as a latent variable, and integrates both instance-level reliability and prototype-level semantic transport to infer the posterior distribution of the latent counterpart. Extensive experiments on six widely-used multi-view datasets against 10 state-of-the-art MvC methods demonstrate the effectiveness of PLCI for tackling the imperfect information problem. The code will be released upon acceptance.

Vision-language models (VLMs) can locate an image region referred to by a text prompt and route the corresponding visual evidence to the output, yet the internal mechanism behind this behavior is not understood. Inspired by retrieval heads in large language models, we ask whether VLMs contain an analogous mechanism for visual retrieval. We answer affirmatively by introducing Visual Retrieval Heads(VRHs), a small subset of attention heads (about 1.7–2.6%) that are causally responsible for grounding text descriptions to image regions. To find them, we recast existing head-scoring methods under a unified design space over query tokens, key aggregation, and cross-sample aggregation. We then show that scoring attention from output prediction tokens with a sum over the ground-truth referent region most reliably identifies causal heads. Across four VLMs and five referring-expression benchmarks, masking only the top 20 VRHs reduces grounding accuracy by up to 80 percentage points, while masking the same number of random heads has little effect. Beyond replicating the causal-sparse-universal triad established for text retrieval heads, VRHs exhibit several properties not previously reported: they generalize across visual reference tasks, remaining causal on attribute, spatial, counting, and visual-math benchmarks despite being discovered through bounding-box prediction; they are functionally specific, preserving output format while corrupting localization; and they are architecturally shared, transferring causally across VLMs that share an LLM backbone but differ in vision encoder, projector, and instruction tuning

We study tabular reinforcement learning problems with multiple steps of lookahead information. Before acting, the learner observes $\ell$ steps of future transition and reward realizations: the exact state the agent would reach and the rewards it would collect under any possible course of action. While it has been shown that such information can drastically boost the value, finding the optimal policy is NP-hard, and it is common to apply one of two tractable heuristics: processing the lookahead in chunks of predefined sizes ('fixed batching policies'), and model predictive control. We first illustrate the problems with these two approaches and propose utilizing the lookahead in adaptive (state-dependent) batches; we refer to such policies as adaptive batching policies (ABPs). We derive the optimal Bellman equations for these strategies and design an optimistic regret-minimizing algorithm that enables learning the optimal ABP when interacting with unknown environments. Our regret bounds are order-optimal up to a potential factor of the lookahead horizon $\ell$, which can usually be considered a small constant.

Prediction aggregation aims to combine information from multiple predictors into a more informative one. We study this question in the setting of calibrated predictors, where each prediction must equal the conditional expectation of the quantity being predicted given the predictor's signal. Given several calibrated input predictors and the feature distribution, but not the underlying Bayes probabilities, we ask when one can construct refined calibrated predictors that preserve the information in the original predictors and cannot be further refined using the available information. We formulate calibrated predictors as signaling schemes and define refinement through feature-independent garblings: a predictor refines another if its signal can simulate the other's signal. Constructibility is characterized through observable linear information: each signal corresponds to a vector over the feature space, and a new signal is constructible exactly when its vector lies in the linear span of the input signal vectors. Under this formulation, we establish a sharp algorithmic picture. For deterministic output predictors, bilateral refinement admits a polynomial-time algorithm based on a bipartite graph between the two input signal partitions, while refinement with an arbitrary number of input predictors is $\mathsf{NP}$-hard. In contrast, when randomized output predictors are allowed, we give a polynomial-time algorithm for any number of input predictors by decomposing constructible signal vectors into extreme rays of the associated polyhedral cone.

CoT prompting improves LLM accuracy on complex tasks but often increases token usage and inference cost. Existing "Budget Forcing" methods reduce cost via fine-tuning with heuristic length penalties, suppressing both essential reasoning and redundant filler. We recast efficient reasoning as a lossy compression problem under the IB principle, and identify a key theoretical gap when applying naive IB to transformers: attention violates the Markov property between prompt, reasoning trace, and response. To resolve this issue, we model CoT generation under the CIB principle, where the reasoning trace $Z$ acts as a computational bridge that contains only the information about the response $Y$ that is not directly accessible from the prompt $X$. This yields a general Reinforcement Learning objective: maximize task reward while compressing completions under a prior over reasoning traces, subsuming common heuristics (e.g., length penalties) as special cases (e.g., uniform priors). In contrast to naive token-counting approaches, we introduce a semantic prior that measures token cost by surprisal under a language model. Crucially, the prior is queried only for token-level log-probabilities, adding negligible overhead to the training loop. Empirically, our CIB objective prunes reasoning redundancy while preserving fluency and logic, improving accuracy at moderate compression and enabling aggressive compression with minimal accuracy drop. These gains generalize across model families and task domains, confirming CIB as a domain-agnostic CoT compression framework.

Understanding how transformers encode position and context is central to interpreting their behavior, because it determines how information flows across tokens and shapes the model's predictions. Common tools, such as linear probes and attribution methods, operate on single-position activations and are not designed to capture cross-position dependencies. We introduce Score-Block Token Geometry (SBTG), a score-based diagnostic that recovers cross-position dependency structure from activations and reveals distinct signatures of positional encoding mechanisms that these methods do not expose. SBTG trains a denoising score model on windows of activations and constructs lag-indexed operators that quantify coupling between positions within a layer. Applied to transformers with different positional encodings, it recovers distinct coupling signatures consistent with their architectures: ALiBi exhibits near rank-one coupling in early layers, RoPE distributes coupling across directions in patterns consistent with its rotation frequencies, and absolute embeddings show the strongest position-specific variation. We show that these signatures are stable across seeds and model sizes, and the activation-space directions identified by SBTG are causally relevant: ablating them causes larger performance drops on tasks that require reasoning over relative positions than on tasks that depend on absolute position signals. These results show that joint activation structure provides a lens on how positional encoding mechanisms are realized, revealing differences in how models use cross-position dependencies that are not apparent from the architecture alone.

Predicting mutation-induced changes in peptide--protein binding affinity ($\Delta\Delta G$) is central to therapeutic peptide optimization, but peptide-specific predictors remain limited by scarce labels, target overlap in supervised benchmarks, and costly molecular simulations. We introduce PepDDG, a zero-shot, training-free predictor that ranks peptide mutations by decomposing binding perturbations into three complementary information channels: energetic perturbation, geometric environment, and evolutionary compatibility. Each channel is computed from a wild-type complex structure, transformed into rank space, and combined by non-parametric Borda aggregation, without fitting fusion weights or fine-tuning neural predictors. PepDDG is motivated by rank-covariance analysis showing cross-channel fusion can improve rank correlation when channels retain complementary signal, whereas increasingly expensive refinement of a single energetic channel has diminishing returns. Empirically, the channels are individually moderate but capture distinct mutation regimes, and rank fusion consistently outperforms single-channel variants and training-free baselines. On our curated benchmark of 332 peptide-chain mutations across 33 targets, PepDDG reaches Spearman $\rho = 0.619$; the calibrated PepDDG-Cal variant reaches $\rho = 0.691$. Performance remains strong on short and cyclic peptide subsets, with $\rho = 0.813$ and $0.872$, respectively. These results support complementary evidence fusion on PDB-derived complex structures as a practical alternative to costly same-channel physical refinement for peptide $\Delta\Delta G$ ranking; a separate diagnostic shows that predicted structures can be used when no crystal structure is provided at inference time.

We study how visual information is routed in vision-language models (VLMs). Using causal patching on controlled synthetic and natural datasets, we find that models rely on two distinct pathways to solve visual tasks: A \emph{direct pathway}, where visual information is retained in image token representations and read out by the final token at later layers, and a \emph{text-mediated pathway}, where visual information is first transferred to the query tokens and then read out by the final token. Across three visual tasks, we show that pathway selection is task-dependent, and that data distribution and prompt design can also modulate which pathway is used to solve the image-based query. Moreover, using attention knockouts and corrupted-input patching, we find that these pathways are flexible, under certain interventions, models can rely on the text-mediated pathway as a fallback when the usual pathway is ablated. This behavior unifies findings in prior work and shows that ablation-based interventions can reveal what models could do rather than what they normally do. Together, our results provide a mechanistic characterization of visual information flow in VLMs and highlight the flexibility of their internal mechanisms under intervention.

Researchers often need web corpora that are not answers to a single query, but reusable collections of documents spanning many decentralized sources. We refer to this problem as thematic web data collection}: assembling semantically relevant documents that share a common theme but are scattered across heterogeneous and structurally disconnected regions of the web. Existing approaches, including traversal-based methods and LLM-driven web agents, are limited by local exploration or short-horizon stopping, preventing comprehensive collection. We formulate this task as a long-horizon information foraging problem over query-induced semantic patches, where the central challenge is deciding when to continue local exploitation and when to switch to new regions. We propose PatchScout, a multi-agent framework that instantiates a class of patch-switching policies to balance local exploitation and adaptive patch switching under a fixed budget. Experiments on four live-web topics show that PatchScout substantially improves yield and domain coverage over traversal-based and search-augmented reasoning agent baselines. In an applied social science setting with an incomplete prior collection, PatchScout discovers 102 previously unidentified entities, illustrating its ability to expand existing thematic datasets.

Solubility depends on intermolecular interactions between solutes and solvents and is central to drug discovery, chemical and materials process engineering. Its prediction requires out-of-distribution (OOD) generalization to unseen solutes, solvents, and solvent mixtures, where supervised methods suffer from data scarcity, and existing self-supervised pretraining methods do not explicitly learn chemically meaningful relations. Learning chemically meaningful relational information without labels can alleviate data scarcity and improve OOD generalizations, but remains challenging. We introduce Prior Relational Information for Self-supervised Modeling (PRISM) and apply it to solubility OOD generalizations. PRISM is a label-free pretraining framework that converts expert-defined chemical priors into relational teachers. For solubility prediction, it trains four encoders to preserve the population-level relational information from priors capturing hydrophobic, electrostatic, polarizability, and substructural effects, using Kullback-Leibler (KL) divergence to match pairwise distance-based distributions during pretraining. For scaffold, solute, and solvent OOD generalizations, PRISM matches or surpasses supervised and self-supervised baselines. For mixed-solvent OOD generalizations, freezing the four PRISM encoders and training a light fusion-and-composition head outperforms the strongest supervised baselines and greatly reduces prediction variations. Ablations and control studies confirm that gains stem from chemically meaningful relational structures baked into the encoders by PRISM. We expect this strategy of turning relational priors into self-supervision signals to extend beyond solubility prediction to domains where chemically or biologically meaningful relational priors are available.

While While Vision Foundation Models (VFMs) are increasingly used in several computer vision tasks, their internal representations remain substantially opaque. This mostly stems from polysemanticity, i.e., individual neurons encode mixtures of unrelated visual patterns. In stark contrast, human reasoning is inherently monosemantic, i.e., it naturally relies on distinct, isolated features to process information. Therefore, monosemanticity needs to be implemented within the model's activation space to obtain representations that are human-understandable concepts. Existing methods mostly operate on convolutional networks, so when applied to VFMs their "crop-and-resize" approach distorts the model's representations by disrupting global self-attention mechanisms and discarding spatial geometry. Furthermore, prior work requires downstream classification labels and is based on KL-divergence, which requires to propagate the gradients back from the classifier head. Ultimately incurring in excessive concept extraction time, and making it hardly applicable to extract task-agnostic concepts. To overcome these issues, we propose PLACE, a fully unsupervised concept extraction framework that operates directly on the native patch-token activations of a VFM. By introducing a geometric Gram-matrix alignment loss, PLACE mechanistically controls downstream KL divergence, thus enforcing faithfulness -- i.e., the notion that extracted concepts, although obtained in an unsupervised fashion, are relevant to downstream classification tasks. Evaluations on image classification tasks (ImageNet and COCO) on DINOv2, ViT-MAE and ViT-B/16 show that PLACE (i) using Gram-alignment it extracts concepts about $20\times$ faster compared to KL-supervised extraction and $11\times$ faster than Sparse Autoencoders (SAEs). Moreover, PLACE yields highly sparse concepts that (ii) achieve up to 40 percentage points sparser compared to the state of the art (i.e., max 0.933 Gini sparsity score), and (iii) are up to 92.3% similar to those obtained under classifier supervision (i.e., 0.923 cosine similarity).

Hypergraph Neural Networks (HNNs), designed to model higher-order relations beyond pairwise interactions, typically rely either on fixed structural weights or on normalized attention. Fixed weights can propagate misleading information in heterophilic settings, while normalization makes attention coefficients competitive, in the sense that, in a message-passing framework, increasing the weight of one sender must reduce the weight of others in the same aggregation set. Our main contribution is the introduction of PANDA (Prior-guided AttentioNal Dual-path Architecture), a plugin for two-stage message passing HNNs applicable to both undirected and directed settings. The *main path* interpolates between learned receiver-normalized attention and structural incidence priors, while a non-competitive (not normalized) *auxiliary path* lets each sender contribute its own transformed information. We also show that, with fixed structural coefficients, PANDA recovers a certain complex-valued, convolution operator adopted in previous works. Across four HNNs spanning spatial and spectral methods in both directed and undirected settings, plugging PANDA in yields an average improvement of $5.18$ percentage points across eight real-world benchmark datasets.

We study the problem of multiclass PAC learning with bandit feedback in the realizable setting. In this framework, there is an unknown data distribution over an instance space $\mathcal{X}$ and a label space $\mathcal{Y}$, as in classical multiclass PAC learning, but the learner does not observe the labels of the i.i.d. training examples. Instead, in each round, it receives an unlabeled instance, predicts its label, and receives bandit feedback indicating only whether the prediction is correct. Despite this restriction, the goal remains the same as in classical PAC learning. We provide a general characterization of the optimal sample complexity of this problem, sharp for every concept class up to logarithmic factors. Our characterization is based on a new combinatorial dimension, termed the *bandit $\mathrm{DS}$ dimension*, defined via generalized combinatorial structures we call *pseudo-boxes*. These extend the pseudo-cubes underlying the $\mathrm{DS}$ dimension by allowing a different number of neighbors in each coordinate. In contrast to the $\mathrm{DS}$ dimension, which governs the full-information setting by counting the number of coordinates in the pseudo-cube, the bandit $\mathrm{DS}$ dimension aggregates the number of neighbors across coordinates, leading to a characterization in which the sample complexity scales with the total number of neighbors. We also propose a general learning algorithm achieving the upper bound, based on an algorithmic principle called *ListCascade*, which connects bandit learning to list learning and may be of independent interest.

Classifier-free guidance (CFG) is a standard technique for improving conditional generation in diffusion models, yet its activation schedule is usually selected heuristically. In practice, most existing CFG-based methods rely on a pre-defined activation policy throughout inference, while recent dynamic variants often depend on hand-designed schedules without a principled theoretical explanation of when conditional information is most useful. In order to understand how the informational relevance between conditioning inputs and the score function evolves over the course of generation, we explore when guidance should be activated from an information-theoretic perspective. In this work, we formulate the diffusion trajectory as a time-dependent information bottleneck and show that the effectiveness of conditional information is not uniform throughout sampling, but becomes significantly stronger after a critical stage characterized by a Fisher-information balance condition. Motivated by this insight, we propose a training-free dynamic CFG strategy for inference. Rather than prescribing a fixed schedule in advance, our method constructs a stochastic process from conditional and unconditional score statistics and activates guidance when the estimated guidance gain crosses a prescribed threshold. This yields an adaptive activation rule that aligns condition injection with the underlying generation dynamics, while also recovering interval-based guidance as a limiting special case. Extensive experiments across diverse architectures and tasks, demonstrate that our method is effective, robust, and broadly applicable. Beyond empirical improvements, our framework provides an interpretation of dynamic guidance methods and a principled foundation for inference-time control in conditional diffusion models.

Multi-token prediction (MTP) accelerates autoregressive decoding through blockwise prediction, but remains vulnerable to error accumulation across sequentially generated blocks. Existing work primarily focuses on improving MTP’s acceleration ratio while largely overlooking the compounding errors that accumulate during block-wise generation. In this work, we study MTP from an information-theoretic perspective and identify the strength of inter-block dependencies as a key factor governing its performance. Building on the cumulative information loss, we theoretically quantify the gap of block-sequence representation. Motivated by the analysis, we propose Dual-MTP, a novel MTP training framework that explicitly models inter-block dependencies from two complementary perspectives, thus reducing the block-sequence representation gap across decoding steps. Specifically, Dual-MTP introduces a dual-perspective training objective with random masking, where each block is jointly trained for forward prediction and masked context reconstruction, encouraging robust block-level representations. Experiments across five model backbones and six tasks spanning math reasoning and GLUE understanding show that Dual-MTP consistently outperforms standard MTP on both quality and efficiency, attaining the highest average accuracy on every backbone with gains of +0.3 to +3.0 points and a 1.4× to 1.9× wall-clock speedup over standard autoregressive decoding.

More data is commonly assumed to improve learning performance. We show that this intuition can fail in sequential decision-making. Motivated by multi-agent collaborative learning, we study stochastic bandits with exogenous side information, and ask if free and unbiased reward samples are guaranteed to reduce regret. We introduce a formal notion of non-degradation under side information and demonstrate that the widely used UCB algorithm violates this property: there exist benign side-information designs under which UCB incurs strictly higher regret than when run without side information. We contrast this behavior with Thompson Sampling and Explore-Then-Commit, which benefit from the same information. Constructively, we further propose a meta-algorithm that enforces non-degradation for a broad class of bandit algorithms. Finally, experiments in recommender systems scenarios show that data sharing among different groups of users under UCB can yield diminishing and even negative returns for individual groups.

Policy gradients for autoregressive sequence models differentiate each token's log-probability while holding the conditioning history fixed. This discards information about how earlier decisions shape later conditional distributions, creating a credit-assignment bottleneck when rewards are sparse. We introduce History-Reparameterized (HR) policy gradients, which replace the frozen prefix in the score function with a differentiable reparameterized or relaxed history, allowing gradients of downstream log-probabilities to propagate backward through the generated trajectory. The resulting history-pathwise term is generally biased when added directly, so we derive Optimal HR (OHR), a centered control-variate estimator with a closed-form coefficient that minimizes the trace of the gradient variance at the population level. The variance reduction is governed by temporal structure in the policy dynamics: random or weakly structured policies provide little benefit, while policies with learned sequential dependencies yield informative history-pathwise corrections. For discrete tokens, the choice of relaxation is crucial: embedding-level relaxation yields substantial variance reduction that grows with horizon, whereas straight-through Gumbel-Softmax yields essentially none in our diagnostics. We validate the method on a Gaussian linear Markov model, a sparse-reward T-maze with a recurrent policy, and an autoregressive Transformer model for small Traveling Salesman Problem (TSP) instances.

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.