NeurIPS 2026 Papers

Recently, Antoniadis et al. (ICLR 2025) proposed a framework for incorporating predictions to approximate NP-hard selection problems. Despite its simplicity, this approach tightly matches theoretical lower bounds, making its generalization highly compelling. We address an open question raised in the work of Antoniadis et al., concerning the extension of this approach to other important problems outside the class of selection problems, such as scheduling. We develop a learning-augmented algorithm for the makespan minimization problem on unrelated machines, denoted by $R||C_{\max}$. By using predictions of heavy job assignments, we achieve a polynomial-time $(1+\varepsilon)$-approximation for accurate predictions that smoothly degrades to a worst-case 2-approximation as the error increases. We conclude our work with an empirical analysis of our method.

Synthetic data has become a promising way to scale model training beyond limited human-generated data but it may also induce strong model collapse (Dohmatob et al., 2024), where any fixed fraction of synthetic data prevents model performance from improving under data scaling, leaving a non-vanishing excess risk floor. In this paper, we studied how synthetic data affects the generalization of one-pass SGD in high-dimensional linear regression with model shift. We show that mixed training induces strong model collapse while two-stage training avoids this by using synthetic data only in the first stage, followed by real-data training in the second stage, showing that strong model collapse is not inevitable through a simple data curriculum. We further establish scaling-law upper bounds for both protocols under a random sketch model, showing that larger models amplify synthetic-induced degradation in mixed training and giving an explicit characterization of how high-quality synthetic training may reduce bias in two-stage training. Overall, our results highlight that synthetic data is neither inherently harmful nor beneficial; its effect depends critically on both its quality and the training protocol used to incorporate it.

Boolean satisfiability (SAT) provides a foundation tool for cryptographic key recovery by encoding ciphers into CNF or ANF representations. However, heuristic solvers and their neural-enhanced variants often degrade significantly on cryptographic instances due to pronounced structural symmetry, a large number of intermediate variables, and complex algebraic dependencies. Existing neural approaches—ranging from end-to-end prediction to solver-integrated heuristics—face challenges in scalability, assignment accuracy, or computational efficiency. In this paper, we propose a unified neural-guided enumerative SAT framework for cryptographic key recovery. It performs a single forward neural guidance to identify a subset of $k$ critical variables, followed by enumeration over their assignments before invoking a heuristic SAT solver. This design effectively reduces the combinatorial search space while keeping neural overhead minimal. We further introduce a taxonomy of neural guidance across data and model capability regimes, including supervised selection with cryptographic priors, uncertainty-driven selection with assignment prediction, and robust fallback strategies using the model trained on general SAT datasets. Experiments on 10 SAT solvers and 2 cube-and-conquer strategies over SAT4CryptoBench and SAT Competition benchmarks demonstrate up to $5\times$ speedup and approximately 2× average improvement on cryptographic instances, while maintaining better performance on general SAT datasets. These results highlight the effectiveness and generalization of this framework, illustrating its potential to bridge machine learning and SAT solving in cryptanalysis tasks.

This paper studies adaptive targeting under network interference in a bandit setting, where treatments applied to one individual may affect others through spillover effects. We consider a linear model in a sparse regime, where each individual's outcome can be affected by at most a few others. We first establish a regret lower bound showing that ignoring the network structure and reducing the problem to a standard linear bandit inevitably leads to inefficient learning, particularly in large populations. To understand how structural information can be leveraged, we analyze regimes with varying levels of knowledge of the interference structure: (1) full support knowledge, (2) knowledge of the column support sizes, and (3) no prior knowledge. For each regime, we establish regret lower bounds characterizing the fundamental limits of learning, and develop algorithms that achieve near-optimal regret. Together, our results provide a unified view of how knowledge of the interference structure governs the efficiency of online learning under interference, and offer practical adaptive targeting algorithms in each setting. Numerical experiments on synthetic and real-world data demonstrate the practical benefits of our algorithms.

Spiking reservoir computing, and reservoir computing more generally, is a powerful and efficient framework for neuromorphic and biological applications, in which a fixed random reservoir drives a trained readout. Yet its performance depends critically on the reservoir initialization. Enriching the reservoir with adaptive, unsupervised plasticity rules offers a natural solution to this limitation. However, it is unclear which rules work, or why, and how to find the best-suited rules for specific tasks without exhaustive and expensive search. Here, we learn how to play the Atari game Pong in a plastic spiking reservoir network. We systematically characterize a large family of local plasticity rules that were meta-learned in prior work. We then show that their performance is predictable and structured: high-scoring rules are characterized by strong differentiation between neurons encoding the ball trajectory and the background, with stable weight dynamics, and consistent readout alignment across time. Rule performance can be estimated from rule parameters alone. Finally, conditioning simulation-based inference (SBI) on high scores allows us to sample directly from promising regions of the rule space, to discover rules that exceed the performance of those found in the prior distribution and reveal stable, high-performing configurations. Together, these results offer competitive performance against classical reservoir computing while providing a transparent, interpretable account of what makes a plasticity rule useful for neuromorphic hardware and biological computing.

Transfer learning in reinforcement learning (RL) has shown strong empirical success. In this work, we take a more principled perspective by studying when and how transferring knowledge between MDPs (a source and a target) can be provably beneficial. Specifically, we consider the case where there exists an undo map such that applying this map to the target’s state space recovers the source exactly. We propose an algorithm that learns this map by matching state feature statistics gathered from both MDPs, and then uses it to transfer the source policy. We theoretically justify the algorithm by analyzing the setting when the undo map is linear and the source is linearly-$Q^\star$ realizable, where our approach has strictly better sample complexity than tabula rasa RL in the target MDP. Empirically, we demonstrate that these benefits extend beyond this regime: on challenging continuous control tasks and Atari games, our method achieves significantly better sample efficiency. Overall, our results highlight how shared structure between tasks can be leveraged for efficient transfer of policies across environments.

High-throughput scientific facilities such as the Large Hadron Collider depend on real-time event filtering (\textit{triggering}) under tight constraints on bandwidth, latency, and storage. In practice, trigger menus are largely static and hand-tuned and can become suboptimal as detector conditions, pileup, and background composition drift over time. We cast online threshold tuning as a sequential decision-making problem: a reinforcement learning agent ingests streaming summaries of recent rates and signal-sensitive features and updates trigger thresholds to maximize signal efficiency while tracking a target background rate within a tolerance band. We adapt Group-Filtered Policy Optimization (GFPO) to streaming control and introduce two variants (GFPO-F, GFPO-FR) that enforce background rate feasibility during training. On a benchmark that emulates realistic collider operation, we study two representative triggers: a total transverse energy ($H_{T}$) trigger sensitive to pileup variation, and an anomaly-detection (AD) trigger based on reconstruction loss for rare or non-standard signatures. On Monte Carlo streams, our agent increases the fraction of in-tolerance time intervals by 38\% ($H_T$) and 30\% (AD), with a cumulative gain of up to 5\% in conditional signal efficiency. Transferring from simulation to \emph{real} collision data (CMS Run 283408), the same agent, without fine-tuning, achieves a 40\% ($H_T$) and 25\% (AD) in-tolerance improvement over baselines, with an additional 1\% signal-efficiency gain on both triggers. To our knowledge, this is the \textit{first} demonstration of RL-based trigger control on real Large Hadron Collider collision data.

Training tool-using agents for planning is challenging when high-quality demonstrations exist only as final outcomes without the intermediate tool traces that produced them. A common response is to impute traces and apply imitation learning, but this approach is indirect and structurally limited to matching the reference rather than improving upon it. We propose anchored comparative feedback: rather than imitating a reference plan, we train agents to surpass it under a comparative LLM judge while satisfying hard constraints. The anchor provides a stable optimization target, and comparing two identically rendered plans neutralizes surface-level judge biases. On TripTailor, a tool-augmented travel planning benchmark, anchored GRPO achieves 80.1% final success rate compared to 43.7% for imitation learning on imputed traces, with gains on both constraint satisfaction and LLM-judged preference that persist across judge families, rubrics, and a held-out reward model. Gains generalize beyond TripTailor, with a fivefold improvement on the held-out TravelPlanner benchmark. These results suggest that anchored comparative feedback offers an effective approach for learning transferable tool-using planners from outcome-only supervision.

Diffusion and flow generative models sample by integrating a learned ODE, but high quality still requires many sequential model evaluations. Solver learning reduces this cost by adapting scalar coefficients, timesteps, or both, while keeping the backbone model fixed. In this work, we identify a structural bottleneck in this update family: each step remains span-limited. Each update remains a scalar-weighted combination of buffered velocity evaluations, so learning can reduce the in-span teacher mismatch but cannot represent the out-of-span residual exposed by large steps. We propose SpanLift, a lightweight operator-augmented neural solver that enlarges the update family beyond scalar-coefficient solvers. SpanLift keeps a fixed base solver as an in-span prior and learns a spatial residual operator over the state and velocity buffer. The operator is trained by endpoint teacher matching, preserves the pretrained backbone, and adds no model NFEs. Empirically, the learned correction transfers across base solvers and is predominantly out-of-span. Across pixel-space diffusion, latent flow matching, and precipitation nowcasting, SpanLift achieves state-of-the-art few-step sampling. With only 3 NFE, it improves CIFAR-10 FID from 8.16 to 5.69 and ImageNet FID from 17.37 to 11.83.

*Does language modeling on image-text data truly improve vision, or does it merely adapt visual features for language alignment?* Despite rapid progress in multimodal large language models (MLLMs), this question remains poorly understood. We present the first systematic analysis of visual representations in MLLMs by probing popular model families across a broad suite of dense visual tasks and comparing each MLLM to its exact pre-MLLM vision encoder. We find that language modeling largely improves visual representations for semantic tasks but can degrade performance on fine-grained geometric tasks, such as monocular depth. We further show that scaling the language model consistently improves the quality of visual representations. Given the improved MLLM representations, we next examine how to best extract and aggregate these features. Since no single layer provides a universally strong representation and concatenating features across layers is impractical, we propose a lightweight adapter that efficiently combines features across MLLM layers, turning frozen MLLMs into competitive visual backbones. Finally, we study whether MLLM representations can improve downstream applications, including text-to-image generation and inverse dynamics modeling, and show that they can outperform pre-MLLM visual features as general-purpose representations. Together, our results provide a representation-centric perspective for understanding and leveraging MLLMs as visual foundation models.

Scaling neural solvers to large Vehicle Routing Problems (VRPs) runs into two recurring difficulties. To stay within compute budgets, scalable solvers tend to rely on partitioning, local candidate restriction, or staged decisions, which limit the global structure that ultimately drives solution quality. To improve the final solution, many neural pipelines fall back on a classical search, but use it as a one-shot post-processor. The model predicts, search repairs, and no sustained feedback is formed between them. We propose $\textit{LSSL}$ (Learning to Search, Searching to Learn), a closed-loop learning-search framework for large-scale VRP that addresses both difficulties in one framework. LSSL predicts a search-friendly guidance heatmap on a sparse candidate graph. A classical heuristic backend then uses this heatmap to refine the incumbent solution, and the structural state returned by the backend is fed back to recondition the model. As a result, learning and search interact within a closed loop, rather than operating as two detached stages. Built on a sparse diffusion transformer over an O($\textit{NK}$) candidate graph, the loop scales to ultra-large instances on a single consumer-grade GPU without hard decomposition. Experiments on large-scale TSP and CVRP benchmarks demonstrate that LSSL achieves superior scalability, efficiency, and solution quality. Ablation studies further reveal that the closed learning–search loop accounts for a substantial portion of the observed performance gains.

When does a language model acquire a capability? When its hidden states encode the relevant information, or when its output readout can express it? We investigate this gap between representational availability and readout expression by tracking the unembedding matrix through pretraining. Because unembedding rows are aligned by token identity across checkpoints, they provide one trajectory per vocabulary item through the learned output interface. To measure these trajectories, we introduce parameter-trajectory crosscoding, a checkpoint-spanning sparse dictionary with shared feature identities and checkpoint-specific decoders. Applied across Pythia scales and in OLMo-2-7B, this method reveals an early, heterogeneous reorganization of the readout. This reorganization does more than alter structure. Our independent WordNet probes show that token families become increasingly separable over the same developmental window. We then causally test whether the readout component drives this development. By swapping the unembedding matrices across checkpoints, and controlled contrastive tasks, we show that task-relevant distinctions can be present in hidden states before the contemporaneous readout expresses them in logits. By ablating individual crosscoder features, we trace these delayed readout effects directly to compact, learned directions. More broadly, developmental analyses should distinguish representational availability from readout expression. Together, our findings demonstrate that the learned output interface helps determine when latent structure becomes visible in token logits, highlighting the need for developmental analyses to explicitly decouple hidden-state representation from readout expression.

We study a repeated information design setting in which the receiver, who is also the decision-maker, updates beliefs in a systematically biased way. More specifically, a distorted posterior in our model can be written as a convex combination of the prior and the Bayesian posterior, governed by a fixed but unknown parameter. Over repeated interactions, the sender chooses persuasive signaling schemes, observes only the receiver’s realized actions, and seeks to minimize regret relative to a full-information oracle that knows the receiver’s biased updating rule. We propose a safe exploration algorithm for learning the receiver’s bias while maintaining high persuasion value. The algorithm exploits the asymmetric cost of probing: conservative probes incur only local loss, whereas overly aggressive probes may lose the persuasive opportunity entirely. For general finite state and action spaces and arbitrary bounded utilities, our method achieves $O(\log\log T)$ regret. A matching $\Omega(\log\log T)$ lower bound shows that this rate is optimal. We further discuss the influence on receiver welfare, as well as extensions to jointly unknown prior and bias, and contextual settings with time-varying priors and utilities.

Persuasion is a core dynamic of natural language communication, shaping how large language models (LLMs) update beliefs, resolve disagreements, and reach decisions. As LLMs increasingly debate, advise, and think collaboratively with humans and each other, resistance to harmful persuasion becomes a core requirement for reliable behavior. Yet we show that this requirement is far from met: a single targeted persuasive argument is enough to collapse model accuracy to near zero, even when the argument is factually false. We formalize this threat as adversarial persuasion and introduce an adversarial reinforcement learning framework that trains persuader agents to change a target model's answer in a single interaction. First, we show that optimizing persuasion strategies through trial and error exposes vulnerabilities that static prompting misses: RL-trained persuaders raise persuasion success from approximately 24\% to over 93\% against the training-time persuadee. Second, we find that these learned strategies transfer to unseen models, achieving 83\% attack success on Qwen-14B, 79\% on Llama-3.1-8B, and 25\% on GPT-4o-mini. Third, we demonstrate that a curriculum that bootstraps on more persuadable open-weight models before targeting harder models further increases GPT-4o-mini attack success from 25\% to 38\%. Moreover, our results reveal that optimized persuaders increasingly rely on credibility-based tactics, including fabricated citations and false authoritative evidence. Together, these findings expose a critical weakness in current LLM agents: even when they initially reason correctly, they can be steered toward false conclusions by optimized natural language influence. This positions persuasion robustness as a necessary safety criterion for multi-agent and human-AI decision-making systems.

Experience-driven learning has emerged as a promising paradigm for enabling agents to improve from interaction trajectories by accumulating and reusing past experience. However, existing approaches are predominantly developed in textual settings and rely on manually designed memory schemas, limiting their applicability to multimodal environments. In real-world scenarios, experience is inherently multimodal, involving heterogeneous signals across perception, reasoning, and action, which makes effective memory design significantly more challenging. In particular, the optimal way to structure and utilize multimodal experience is highly task-dependent and evolves over time, rendering fixed memory designs insufficient. In this work, we propose a new paradigm, learning to learn from multimodal experience, which shifts memory design from a predefined component to an adaptive and learnable process. Our framework enables agents to dynamically construct, organize, and utilize memory based on task requirements and interaction history, effectively learning how to structure experience for improved performance. Experiments demonstrate that adaptive memory design substantially enhances agent performance and generalization across multimodal tasks, highlighting the critical role of learning memory mechanisms in experience-driven learning.

Reinforcement learning (RL) post-training has become an important paradigm for improving multimodal large language models (MLLMs), especially with automatically verifiable rewards. For vision-centric MLLMs, self-supervised visual pretext tasks provide such rewards without human annotations. However, existing self-supervised RL methods mostly exploit within-instance structure, such as spatial or temporal ordering within a single image or video, offering limited supervision for cross-instance discrimination and fine-grained comparison. We introduce Group-and-Order Self-Supervised Reinforcement Learning (GO-SSL), a cross-instance jigsaw framework for vision-centric MLLM post-training. Given two visual instances, GO-SSL mixes their local elements and trains the model to group them by instance of origin while recovering the order within each group, coupling instance-level comparison with spatial, temporal, or geometric structure recovery. This paired formulation turns the same unlabeled data into richer verifiable supervision through diverse pairings, shuffles, and hard-pair curricula. We instantiate GO-SSL mainly on cross-image jigsaw tasks and further extend it to 3D depth and video temporal ordering. Across diverse benchmarks, GO-SSL consistently improves over the base MLLM and prior baseline methods, with clear gains in fine-grained perception and spatial understanding. These results suggest a data-efficient direction for self-supervised RL in MLLMs: constructing comparative cross-instance contexts can provide richer transferable supervision than merely scaling data volume or adding isolated pretext tasks. Code will be released later.

On-policy distillation (OPD) has emerged as an efficient post-training paradigm for large language models. However, existing studies largely attribute this advantage to denser and more stable supervision, while the parameter-level mechanisms underlying OPD's efficiency remain insufficiently understood. In this work, we argue that OPD's efficiency stems from a form of ``foresight'': it establishes a direct and stable path from the initial model to the final model early in training. This foresight manifests in two aspects. First, at the \textbf{Module-Allocation Level}, OPD identifies regions with low marginal utility and concentrates updates on modules that are more critical to reasoning. Second, at the \textbf{Update-Direction Level}, OPD exhibits stronger low-rank concentration, with its dominant subspace aligning closely with the final update subspace early in training. Motivated by this theory, we propose \textbf{EffOPD}, a plug-and-play acceleration method that speeds up OPD by searching for an effective step size and extrapolating along the current update direction. EffOPD requires no additional trainable modules or complex hyperparameter tuning, and achieves up to $3.5\times$ training acceleration while maintaining comparable final performance. Overall, our findings provide a parameter-dynamics perspective for understanding the efficiency of OPD and offer practical insights for designing more efficient post-training methods for large language models. Our code is available at: https://anonymous.4open.science/r/EffOPD-7C58.

In-context watermarking (ICW) prepends an instruction to a query asking the model to embed a statistically detectable signal in its response. It thus equips LLMs with a watermarking interface that third parties can invoke without access to model internals. Its reliability hinges on the LLM following the instruction without degrading answer quality, yet how well current LLMs do so has not been measured. We introduce ICWBench, a benchmark of three verifiable ICW instruction families, each scored on both detectability and answer quality. Evaluating 14 frontier proprietary and open-source LLMs, we find that none of the evaluated LLMs achieves both objectives across all three families. To address this, we propose a self-contained two-stage training method, requiring no distillation from a stronger model, no manual annotation, and no pre-existing ICW IF ability. The first stage, self-distillation with logits perturbation (SDLP), uses the same base LLM as both teacher and student: an instruction-equivalent decoding-time logits perturbation makes the teacher follow the ICW instruction, and the student is trained to match the teacher's output distribution. The second stage applies reinforcement learning with the automatic verifier as the reward. Applied to Qwen3-14B, the weakest of the 14 evaluated LLMs in ICW IF, our method raises average TPR@$1\%$FPR across three ICW instructions from $0.100$ to $0.974$, achieving a more favorable trade-off than the frontier proprietary LLMs we evaluate.

Reinforcement Learning with Verifiable Rewards (RLVR) enhances large language model (LLM) reasoning, yet growing evidence indicates an \emph{exploration ceiling}: they tend to reweight existing solution traces and produce low-diversity rollouts. This restricts the discovery of novel solution perspective and weakens out-of-distribution generalization. We address this limitation by directly perturbing the rollout policy's parameters while updating the clean policy model as usual, an approach that achieves better temporal consistency and yields more complex behavior patterns. To stabilize learning from these perturbed rollouts, which are inherently off-policy, we incorporate truncated importance sampling. Furthermore, we introduce a lightweight, dynamic noise scheduler based on semantic diversity and model self-certainty to optimally adjust the noise scale. Instantiated on GRPO, our method (PSN-GRPO) demonstrates its efficacy through four key contributions: (1) it improves high-budget pass@$k$, increases semantic and operational diversity, increases CoT consistency, and remains complementary to exploration-oriented RLVR techniques; (2) it validates efficacy across multiple models, including Qwen2.5, Qwen3, and Llama-3.1; (3) it shows robust performance on out-of-distribution science and coding benchmarks; and (4) it uncovers novel solution perspectives for problems the original model could not solve, as shown by qualitative analysis.