NeurIPS 2026 Papers

Many problems are inherently compositional: solving them requires a sequence of intermediate decisions that jointly determine the final answer. A central question is when such a compositional structure can be learned from outcome-level feedback alone, where supervision of the intermediate steps is unavailable. We study this question for autoregressive models trained using reinforcement learning with verifiable rewards (RLVR). We identify the \emph{task-advantage ratio}, a joint property of the task and the model, which measures whether intermediate decisions present an advantage in reaching a correct final solution. We show that this ratio governs learnability in our setting: when the advantage is present, RLVR efficiently learns the target composition, while when it is absent, training can converge to suboptimal compositions. We further show that the required advantage arises naturally in several structured problems, but may depend critically on the quality of the initial model. Our results help to clarify when compositional problems can be learned from final rewards alone.

Alignment-based representation learning for cross-dynamics RL admits a degenerate global minimizer: per-domain feature covariances collapse to a common point, driving the alignment loss to zero while transfer regret remains large and rendering the standard Bures-Wasserstein (BW) transfer regret bound vacuous. We document this collapse across multiple environments, alignment kernels (BW, Frobenius, MMD), and methods (BW-CORAL, VGDF), where per-domain effective rank drops from p to $\approx 1$ within a few epochs—structurally the same failure as representation collapse in self-supervised learning. We propose a minimal remedy: a per-domain Prototype Trust Region (TR) that anchors each empirical covariance to a slow-moving EMA prototype, introduces no learnable parameters, and acts as an explicit second-moment stabilizer, mirroring momentum targets and covariance regularizers in SSL. Because TR depends only on per-domain covariances, it is combined with any BW-based method; adding it to VGDF inherits the same resistance to collapse. Theoretically, we prove a BW non-collapse lower bound that restores the transfer-regret guaranty to a non-vacuous form, and present a Representation Stability Transfer Bound that decomposes regret into coverage and stability terms TR directly controls. Empirically, TR delivers statistically significant gains under pre-registered tests in collapse-dominated regimes (finite-sample, lower-dimensional) and is correctly neutral when other bottlenecks dominate. We frame TR not as a universal improvement but as a targeted fix for an identifiable and broadly shared failure mode.

Humans can approach complex visual problems by mentally simulating intermediate visual steps, rather than reasoning through language alone. Inspired by this, several works on Vision-Language Models have recently explored chain-of-thought reasoning with continuous latent tokens as intermediate visual imagination steps. In this work, we investigate how recent models leverage such latent tokens. Surprisingly, we find that model accuracy is unaffected when latent tokens are replaced by uninformative dummy tokens. This indicates that latent tokens play a minimal causal role in the model's final prediction. To better understand this phenomenon, we analyze both the training signal provided by oracle latent representations and the quality of the latent tokens generated at inference time. Our experiments reveal two crucial issues holding back latent visual reasoning: First, in most existing datasets, oracle latent tokens provide limited additional information beyond the original image and do not substantially simplify the task, leading models to ignore them during training and effectively bypassing them at inference time. When fine-tuned on a diagnostic dataset, in which latent tokens provide sufficient support for the final prediction, we show that models can causally rely on them. Second, the latent tokens produced at inference time deviate from their corresponding oracle representations, collapsing to a narrow region and preventing benefits even when the model relies on them. Overall, our findings suggest that future progress in latent visual reasoning depends on two key pillars: high-quality datasets with informative intermediate steps and more precise latent token prediction.

We study learning-augmented algorithms for scheduling on multiple parallel machines under the objectives of minimizing the makespan or the total weighted completion time. We assume that the algorithm has access to noisy information (the prediction) about an optimal solution, expressed through a solution encoding that implicitly quantifies both the amount of information provided and the nature of noise (errors in the prediction). Our central question is to determine the maximum level of noise that still allows for efficiently recovering this optimal solution. We observe that information guiding greedy scheduling to optimality or revealing the optimal assignment of tasks to machines is very sensitive to noise, and prove that recovering an optimal solution from solution encodings capturing either is computationally hard, even for a small (non-constant) number of errors. On the positive side, we show that an order-based encoding, which leads to errors that are dispersed locally, is robust to noise. We present a dynamic programming framework that utilizes this encoding and solves optimally several classical scheduling problems, including makespan and total weighted completion time minimization on identical or unrelated machines.

Transfer-based black-box adversarial attacks provide a practical way to evaluate the robustness of Vision-Language Pre-training (VLP) models, which remain vulnerable to adversarial perturbations that mislead cross-modal matching and downstream predictions. For strong transfer against VLP models, attacks should depend on prediction-relevant evidence localization and model-agnostic perturbation design. Existing methods fall short in both aspects, typically perturbing images broadly or relying on raw attention maps, which imprecisely localize decisive patches and derive perturbation patterns from the surrogate model's own representations, hindering transfer across VLP architectures. In this paper, we propose Graph-Guided Transferable (GGT) attack, a transferable multimodal adversarial attack that decouples what to perturb from how to propagate: the former by cross-modal sensitivity, the latter guided by intrinsic image structure. This separation enables better localization by capturing VLP-specific cross-modal evidence, while enforcing perturbation propagation through model-agnostic image structure, thereby improving transfer across unseen architectures. GGT first identifies crux patches decisive for cross-modal prediction by combining gradient-weighted attention and attention entropy, which capture how indispensable and how broadly influential each patch is. It then propagates perturbations from these crux patches through a model-agnostic graph constructed from spatial adjacency and vision-only patch similarity, with hop-wise attenuation. Extensive experiments demonstrate that GGT consistently outperforms strong baselines in black-box transfer success rate across diverse VLP architectures, improving over the strongest baseline by up to 23.66\% in text retrieval and 16.06\% in image retrieval.

Large language models are increasingly deployed with test-time strategies: sample $N$ responses, score them with a reward model or verifier, and return the best. This deployment rule exposes a mismatch in post-training: standard objectives optimize the mean reward of a single response, whereas best-of-$N$ performance is governed by the upper tail of the reward distribution. Recent test-time-aware objectives partly address this mismatch, but typically assume that training can use the same per-prompt rollout budget as deployment, which is impractical when post-training must cover many prompts while deployment can allocate much larger per-prompt test-time compute. We study this budget-mismatch regime, where only $m\ll N$ per-prompt rollouts are available during training but the target objective is best-of-$N$ deployment. Under structural assumptions on the reward tails, we show that the policy gradient of the best-of-$N$ objective can be approximated from a much smaller rollout group by extrapolating upper-tail statistics. This yields a family of Tail-Extrapolated estimators for best-of-$N$-oriented post-training: a simple direct estimator, Tail-Extrapolated Advantage (TEA), and a fixed-order debiased Prefix-TEA estimator based on moment cancellation. Experiments on instruction-following tasks show that TEA and Prefix-TEA improve best-of-$N$ performance across different language models, reward models and datasets under various training and test-time budget settings.

In Transformer attention, distinct weight vectors $\boldsymbol{\alpha} \neq \boldsymbol{\alpha}'$ can produce the same aggregated representation $\mathbf{V}\boldsymbol{\alpha} = \mathbf{V}\boldsymbol{\alpha}'$. When $\operatorname{rank}(\mathbf{V}) \leq n-2$, configurations with entirely different dominant source tokens collide on a set of positive Lebesgue measure, a condition satisfied in over 97% of attention heads in BERT-Base. Such collisions are harmful: the downstream FFN receives identical inputs despite the attention having attended to entirely different source tokens, and must therefore produce identical outputs regardless of which tokens actually dominated, fundamentally limiting any computation that requires sensitivity to attention source, such as multi-hop reasoning, attribution, or knowledge retrieval. No increase in depth, width, or data can compensate, because the routing weights are discarded before the FFN is reached. The routing weights $\{\alpha_{ij}\}$, however, are available within the same forward pass and can be retained as a compact side-channel to restore the missing signal. We call this structural information loss *routing non-identifiability*. In BERT-Base, value-matrix rank deficiency suppresses $k \geq 107$ routing dimensions (over 84% of degrees of freedom) before any FFN computation. To quantify the practical gap, we introduce the Routing Reconstruction Task (RRT): standard Transformers achieve 31.4% source-identification accuracy while oracle routing statistics reach 94.6%, a 63-point gap consistent with an information bottleneck in the FFN input. We then propose the Route-Aware FFN (RA-FFN), a drop-in module that appends four compact routing statistics to each FFN block at under 1.1% additional parameter cost, recovering over 75% of the oracle gain. RA-FFN improves all benchmarks tested: at 110M scale, gains cover multi-hop reasoning, language modelling, and translation, with multi-hop gains $6\times$ larger than single-hop; at 7B scale on Llama-2-7B and Mistral-7B, gains extend further to mathematics (GSM8K) and general reasoning (MMLU, ARC-Challenge, HellaSwag), ordered by routing sensitivity.

Recent work has shown that flow matching models can be trained without explicit time conditioning, challenging the standard view that the interpolation time is needed to disambiguate velocity targets. But why should a time-blind model work at all? Decomposing the time-blind flow matching loss, we identify two sources of irreducible error: a *coupling variance*, which arises from ambiguous velocity targets induced by how noise and data points are paired, and the *time-blindness gap*, which is the additional error caused by ignoring time. This gap shows that time-blind training is strictly harder than conventional training, reinforcing the puzzle that time-blind models work so well in practice. We resolve this tension by showing that the geometry of high-dimensional data makes time identifiable directly from noisy observations. When data concentrates near a $k$-dimensional subspace, time can be recovered from the statistical structure of noisy interpolants in directions orthogonal to the data; under a spiked-covariance model, this yields a closed-form estimator that recovers $t$ from a single observation $z$ at rate $O(1/\sqrt{d-k})$ for ambient dimension $d$. As a consequence, we prove that the time-blindness gap is asymptotically negligible relative to the coupling variance. We empirically demonstrate our identifiability result on real-world data and show that changing the coupling has a much larger effect on loss and sample quality than removing time conditioning across CIFAR-10, CelebA-HQ, and FFHQ. These results explain why time-blind flow matching works and show that the main practical lever is the choice of coupling, not explicit time conditioning.

It is widely believed that stochastic gradient descent (SGD) performs significantly worse than adaptive optimizers such as Adam in pre-training Large Language Models (LLMs). Yet the underlying reason for this gap remains unclear. In this work, we attribute a large part of the discrepancy to SGD's inability to sustain learning rates comparable to Adam's much larger effective learning rates. Through empirical and theoretical analysis of LLM pre-training dynamics, we identify that training is characterized by small gradient norms and large weight-to-gradient ratios, an effect that becomes more pronounced with larger batch sizes typical in pre-training, necessitating such large effective learning rates. However, we find that output-layer gradient magnitudes become highly uneven across token classes, and that large gradient spikes frequently occur during training. Together, these effects severely restrict the admissible learning rate of SGD. Guided by this understanding, we show that simple clipping mechanisms that stabilize SGD at large learning rates enable it to recover most of Adam's performance. In our large-scale experiments, the validation loss gap between large-learning-rate SGD and Adam shrinks from more than 50% to only about 3.5% when pre-training a 1B-parameter LLaMA model with a 1M-token batch size.

LVLM benchmarks tell us whether a model answers correctly, but not which visual conventions it has retained, nor where those conventions live. We use sketches to expose this hidden structure. A sketch removes texture, lighting, and photographic context while preserving the strokes humans judged sufficient for recognition; if an LVLM can operate on that abstraction, the surviving signal is structural rather than merely photometric. We introduce a training-free sketch probe with three readouts: temporal part-construction order, spatial attention-based grounding, and the mechanistic layer/head locus of grounding. We evaluate across nine LVLMs and five LLaVA-architecture variants on two part-annotated sketch datasets. Three findings emerge. First, LVLM part order tracks human convention: models reproduce canonical orderings where human drawings converge, and become correspondingly variable where human orderings vary. Second, selected frozen LVLM attention heads ground object and scene sketches competitively with specialised grounders, exceeding CLIPSeg and GroupViT on mAcc@0.1 despite using no grounding supervision. Third, the grounding signal concentrates in a narrow mid-network band whose location follows the base language model rather than parameter count, and remains stable across object and scene sketches. The result is a practical diagnostic for sketch-driven LVLMs: no fine-tuning, no auxiliary segmenter, and a small architecture-dependent layer band that doubles as a head-selection prior, improving grounding mAcc@0.1 in every model and dataset we tested.

Streaming video understanding models must answer queries at any moment during an ongoing stream, using only what they have observed so far and under fixed memory and computation budgets. Existing methods address this by adding memory banks, retrieval modules, or visual token compression to preserve long-range history. However, strong recent-window baselines show that indiscriminate history injection can dilute current-scene perception, suggesting that the key challenge is not whether to use memory, but how to allocate it selectively. We formulate this as budgeted online latent evidence allocation and propose **SelectStream**, a selective latent-memory framework that keeps the current observation directly visible to a frozen VLM while exposing historical information only through a compact, query-conditioned evidence budget. Three coordinated mechanisms govern when to write, what to preserve, and how to retrieve: surprise-driven adaptive windowing, priority-preserving consolidation, and query-conditioned graph reasoning over a fixed-capacity latent memory graph. Retrieved evidence is calibrated and injected as latent tokens for answer generation, without replaying frames or growing the context with stream length. Experimental results show that SelectStream achieves strong online streaming performance and preserves general video understanding, reaching 82.67\% on StreamingBench, 67.03\% on OVO-Bench, and 74.4\% average accuracy on offline video benchmarks, while outperforming strong recent-window baselines and prior streaming memory methods.

LLM unlearning is often implemented by assigning surrogate targets, such as refusal, uniformity, or likelihood suppression, to forget-related prompts. We argue that this surrogate assignment view is misaligned with the counterfactual goal of unlearning: recovering the retain-only predictive posterior. This mismatch is especially problematic in mixed-evidence regimes, where a response may be associated with forgotten evidence while still being partially supported by retained evidence. We propose EASE: Evidence Attribution and Subtraction Estimator, a logit-space posterior-correction method that estimates the forget-induced component of the deployed model's predictive support and subtracts it at inference time. EASE uses lightweight deletion and compensation assistants to remove forget-neighbour evidence while restoring nearby retain-supported evidence. We formalize the suppression-scope dilemma and provide guarantees showing when posterior correction recovers the retain-only posterior. Experiments on TOFU and MUSE show that EASE improves forgetting--retention trade-offs over strong baselines, achieving the best aggregate score in 5/6 main TOFU settings, reducing mixed-query semantic leakage by 22.2%, and matching or exceeding full-retain baselines with 9 times fewer retain examples. Our code is available at: https://anonymous.4open.science/r/EASE-9675.

Long-horizon video generation is increasingly moving toward autoregressive rollout, where each newly generated segment becomes part of the evidence used for future prediction. Recent causal decoders, long-context training, and KV-cache mechanisms have extended feasible duration, but most inference pipelines still decide the visible past implicitly through recent windows, compressed caches, or external memory. This raises a direct question: **can the choice of which past frames or segments to show to the decoder be treated as an explicit test-time decision?** We answer this question with \textsc{ReCR}, a training-free method that formulates autoregressive video decoding as representation-guided context rewriting. At each step, \textsc{ReCR} builds a selected visible context from the generated history by using internal decoder representations to favor context units that match the global rollout state, avoid redundancy with the recent continuation, preserve temporal boundary coverage, and provide useful intermediate evidence. The selected units are then mapped onto a compact causal axis before decoding the next unit. Across long-horizon text-to-video benchmarks, \textsc{ReCR} consistently improves multiple autoregressive backbones under matched visible-token budgets. Empirical analyses such as representation-space diagnostics and transition-count prompt switching further show that improving what remains visible is an effective path toward more stable long-video decoding. Our code is available at https://anonymous.4open.science/r/anonymous-ReCR-97EB/

Tokenizers are a crucial component of latent diffusion models, as they define the latent space in which diffusion models operate. However, existing tokenizers are primarily designed to improve reconstruction fidelity or inherit pretrained representations, leaving unclear what kind of latent space is truly friendly for generative modeling. In this paper, we study this question from the perspective of latent manifold organization. By constructing controlled tokenizer variants, we identify three key properties of a diffusion-friendly latent manifold: coherent spatial structure, local manifold continuity, and global manifold semantics. We find that these properties are more consistent with downstream generation quality than reconstruction fidelity. Motivated by this finding, we propose the $\textit{\textbf{P}rior-\textbf{A}ligned Auto\textbf{E}ncoder} (\textbf{PAE})$, which explicitly shapes the latent manifold instead of leaving diffusion-friendly manifold to emerge indirectly from reconstruction or inheritance. Specifically, PAE leverages refined VFM-derived priors and perturbation-based regularization to turn spatial structure, local continuity, and global semantic organization into explicit training objectives. On ImageNet $256{\times}256$, PAE improves both training efficiency and generation quality over existing tokenizers, reaching comparable performance up to $13\times$ faster than RAE under the same LightningDiT setup and achieving a new state-of-the-art gFID of $\textbf{1.03}$. These results highlight the importance of organizing the latent manifold for latent diffusion models.

Training multi-turn LLM agents with reinforcement learning requires distributing a single episode reward across many interaction steps. Recent group-based methods tackle this credit assignment challenge by finding steps where the agent visits the "same" state across different rollouts and comparing their outcomes. However, determining when two states are "the same" remains an open problem: existing methods compare raw text observations via exact string matching or bag-of-words similarity, both of which ignore whether state differences actually matter for future returns. We show that this is a state abstraction problem with a precise bias-variance tradeoff: matching on value-irrelevant features creates unnecessarily small groups (high variance), while ignoring value-relevant features merges states that should be distinguished (high bias). Guided by this analysis, we propose Structured State Abstraction (SSA), a step-level credit assignment method that decomposes observations into typed fields using environment-provided metadata and learns per-field importance weights from return variance. Rather than hard grouping, SSA uses a kernel-smoothed advantage estimator where all states contribute to each step's baseline proportionally to their structured similarity, yielding lower MSE than threshold-based grouping. Experiments on ALFWorld and WebShop show consistent improvements over GiGPO and HGPO across both benchmarks and model scales; notably, kernel smoothing eliminates the singleton problem that causes existing methods to lose step-level credit for 30-36% of steps. Our implementation is provided in the supplementary materials and will be open-sourced upon acceptance.

Evaluation of multimodal reasoning models is typically reduced to a single accuracy score, implicitly treating reasoning as a unitary capability. We introduce MathLens, a benchmark of textbook-style geometry problems that exposes this assumption by operationally decomposing performance into perception, reasoning, and multimodal-specific components. Each problem is derived from a symbolic specification and accompanied by visual diagrams, text-only variants, multimodal questions, and targeted perceptual probes, enabling controlled measurement of each component. Using this decomposition, we show that common training strategies induce systematically different capability profiles that are invisible under aggregate accuracy. Reinforcement learning primarily improves perceptual grounding and robustness to diagram variation, while textual SFT yields gains through reflective reasoning. In contrast, as perception and reasoning improve, a growing fraction of remaining errors fall outside these components and are categorized as multimodal-specific. These results suggest that apparent progress in multimodal reasoning reflects shifting balances among subskills rather than uniform advancement, motivating evaluation beyond scalar accuracy.

Sign-aware recommender systems have recently been developed to leverage negative feedback for a deeper understanding of user preferences. However, our empirical diagnosis reveals that state-of-the-art graph-based sign-aware recommender systems are paradoxically *valence-blind*. Even though they explicitly incorporate sign information during training, they consistently fail to differentiate liked items from disliked ones at the ranking stage, frequently infiltrating top-$K$ recommendations with disliked content. Through linear probing, we show that while valence information exists in the learned embeddings, it remains inaccessible to the inner-product scoring function. This widespread failure remains entirely undetected because conventional evaluation metrics, such as Recall, HR, and NDCG, assign a uniform utility of zero to both negative and unobserved items, creating a systematic evaluation blind spot. To bridge this gap, we propose a family of signed metrics, Signed Recall, Signed HR, and Signed NDCG, that explicitly penalize the recommendation of disliked content. Systematic re-evaluation under our proposed metrics fundamentally reshapes the established performance landscape, revealing that methods ranked highly under conventional metrics often fail to protect users from disliked content. Finally, through a proof-of-concept auxiliary loss, we confirm that the proposed metrics provide actionable training signals, guiding models toward valence-aware behavior without sacrificing conventional relevance. For transparency, our source code is available at: https://anonymous.4open.science/r/signed-rec-benchmark-07E4

Reusing a held-out benchmark adaptively should, in principle, invite overfitting. Yet benchmark-driven machine learning (ML) has produced surprisingly little overfitting in practice. An attractive hypothesis is that successful ML strategies are highly compressible. We study this in the setting of LLM-driven research agents, where the hypothesis becomes directly testable via two complementary information bottlenecks. In \emph{output compression}, an exploration agent adaptively searches for high-performance models using a validation set, and we test whether a fresh ``reproducer agent'' can reproduce its performance given only an extremely short prompt and the training data. In \emph{input compression}, the explorer receives only one-bit feedback indicating whether each submitted model improves on the running best. Across 8 datasets spanning tabular classification, vision, language modeling, diffusion modeling, and reward modeling, we find that these bottlenecks have little effect on performance: short prompts and compressible feedback are sufficient to reproduce and find high-performance models. The hypothesis is falsifiable: when we deliberately induce validation-set overfitting, the results fail to reproduce with short prompts. Taken together, our results support a description-length explanation for the lack of overfitting in benchmark-driven ML: successful strategies occupy a low-complexity region of strategy space.

Vision-Language Models (VLMs) such as CLIP have become a standard backbone for open-vocabulary recognition, yet their zero-shot predictions remain vulnerable to distribution shifts encountered at deployment. Test-Time Adaptation (TTA) has recently been extended to CLIP as a lightweight solution, leading to a rapidly growing body of TTA4CLIP methods. However, empirical progress in this area has largely outpaced our understanding of what truly drives adaptation, where their gains originate, and under which shifts they remain reliable. In this paper, we take a step back from the pursuit of state-of-the-art accuracy and conduct a systematic controlled study of TTA4CLIP. We first organize existing methods into three unified paradigms according to what is updated at test time. We then introduce TTABC, an open-source TTA Benchmark for CLIP, which standardizes evaluation protocols and integrates more than 20 representative methods. Our controlled empirical analysis focuses on three key areas. First, we determine the driving factors in parameter-based methods, revealing that adaptation gains are primarily driven by test-time evidence and reliable proxies rather than heavy optimization. Second, we explore evidence utilization beyond heavy parameter tuning, showing that competitive and efficient performance can be achieved through cross- or current-sample evidence and lightweight prototype updates. Finally, we demonstrate that there is no silver bullet for TTA; no single adaptation paradigm is universally optimal, and the preferred paradigm depends on the nature of shift. We hope our benchmark and study provide a clearer understanding of the current TTA4CLIP landscape and establish a foundation for further research.