NeurIPS 2026 Papers

Watermarking has emerged as a fundamental mechanism for tracing the provenance of Large Language Model (LLM) outputs. While multi-bit watermarks are highly desirable for embedding rich metadata, they suffer from an inherent trade-off between statistical detectability and text quality degradation. Crucially, existing multi-bit schemes lack theoretical quality guarantees, leaving them susceptible to unbounded semantic distortion. To address this, we introduce CSD, the first multi-bit watermarking framework with certified semantic distortion bounds. In CSD, we derive a closed-form upper bound on the Kullback-Leibler (KL) divergence, mathematically guaranteeing strict limits on semantic distortion at every generation step. Furthermore, rather than relying on static payloads, CSD employs a dynamic payload to maximize statistical detectability. Extensive empirical evaluations across multiple datasets demonstrate that CSD achieves robust detectability while maintaining provably safe text generation.

Recent advances in multi-agent systems have shown great potential for solving complex tasks. However, when multiple agents edit a shared codebase concurrently, their changes can silently conflict and inconsistent views lead to integration failures. Existing multi-agent systems address this through workspace isolation (e.g., one git worktree per agent), but this defers conflict resolution to a post-hoc merge step where recovery is expensive. In this paper, we propose STORM, i.e., STate-ORiented Management for multi-agent collaboration. Specifically, STORM manages agent states by mediating their interactions with the shared workspace, ensuring that each agent operates on a consistent view of the codebase and that conflicting edits are detected and resolved at write time.We evaluate STORM on Commit0 and PaperBench across multiple LLMs. STORM outperforms the git-worktree-based multi-agent baseline by +18.7 on Commit0-Lite and +1.4 on PaperBench, while achieving comparable or better cost efficiency. Combined with single-agent runs, STORM reaches highest scores of 87.6 and 78.2 on the two benchmarks respectively, suggesting that explicit state management is a more effective foundation for multi-agent collaboration than workspace isolation. STORM can also be plugged into any multi-agent system. Our code is available at \url{https://anonymous.4open.science/r/STORM-Mutli-Agent}.

Conformal prediction constructs prediction sets with finite-sample coverage guarantees, but its calibration stage is structurally constrained to a scalar score function and a single threshold variable — forcing shapes of prediction sets to be fixed before calibration, typically through data splitting. We introduce multi-variable conformal prediction (MCP), a framework that extends conformal prediction to vector-valued score functions with multiple simultaneous calibration variables. Building on scenario theory as a principled framework for certifying data-driven decisions, MCP unifies prediction set design and calibration into a single optimization problem, eliminating data splitting without sacrificing coverage guarantees. We propose two computationally efficient variants: RemMCP, grounded in constrained optimization with constraint removal, which admits a clean generalization of split conformal prediction; and RelMCP, based on iterative optimization with constraint relaxation, which supports non-convex score functions at the cost of possibly greater conservatism. Through numerical experiments on ellipsoidal and multi-modal prediction sets, we demonstrate that RemMCP and RelMCP consistently meet the target coverage with prediction set sizes smaller than or comparable to those of baselines with data split, while considerably reducing variance across calibration runs — a direct consequence of using all available data for shape optimization and calibration simultaneously.

Mathematical optimization drives decisions in supply chains, logistics, energy, and scheduling, but translating natural-language problems into solver-executable formulations remains a bottleneck. While frontier models show promise for this task, many deployments require small language models (SLMs) that run locally under privacy, latency, and cost constraints. Existing SLMs are limited by noisy data, ambiguous benchmarks, and one-shot inference that ignores the iterative, feedback-driven nature of optimization modeling. We introduce \textsc{OptiMind}, a framework for improving SLMs through formulation-centric data cleaning, class-conditional priors, and multi-turn reinforcement learning with solver feedback. \textsc{OptiMind} repairs ambiguous problems, regenerates solution trajectories, audits benchmark labels, constructs accepted objective-value sets, and distills class-level hints from recurring formulation errors. It then trains models to formulate, execute, and revise GurobiPy programs using solver-verified correctness as reward. On expert-cleaned IndustryOR, Mamo-Complex, and OptMATH benchmarks, a 20B \textsc{OptiMind-RL} model outperforms strong open-source baselines and reaches frontier-model performance under the same protocol. Our results suggest that optimization formulation is better treated as an interactive solver-grounded decision process than as one-shot code synthesis. We release our inference framework, cleaned benchmarks, and sample error analyses at \url{https://anonymous.4open.science/r/OptiMind-NeurIPS-1DB020}, with full data and model to follow.

Reinforcement learning with verifiable rewards (RLVR) plays a pivotal role in improving the reasoning ability of large language models. However, widely used PPO surrogate objectives are fundamentally *local*, as they rely on a local approximation of the exact policy gradient objective. While this approximation improves stability by reducing the variance induced by importance sampling, it also introduces structural bias into the surrogate objective, which must be controlled through trust region mechanisms. In this work, we introduce the $N$-step forward trace, which augments the PPO surrogate objective using the cumulative likelihood ratio of the next $N-1$ tokens. Building on this idea, we propose $N$-Step Forward-Trace Policy Optimization (NFPO), a practical RLVR algorithm that integrates the $N$-step forward trace into the masked policy gradient framework. NFPO provides a continuous bridge between the PPO surrogate objective and the exact policy gradient objective, offering a principled mechanism for controlling the bias–variance trade-off. Our theoretical analysis shows that, with an appropriate choice of $N$, the proposed objective yields a tighter policy-improvement bound than the standard PPO surrogate. Experiments on comprehensive reasoning benchmarks demonstrate that NFPO consistently improves performance, supporting our theoretical findings.

Long-horizon planning often requires composing familiar local transitions while remaining grounded in a specified goal. We study this setting from single-stage data: on a controlled no-skip graph benchmark, training provides only adjacent-stage demonstrations while evaluation requires composing them on unseen long-horizon start–goal pairs; an event-chain diagnostic decomposes success into legality, stage-bridging, and goal-conditioned termination. Across a minimal Transformer, Qwen2.5-3B, and an external validation on MuSiQue multi-hop QA, supervised fine-tuning (SFT) learns local transitions but degrades with horizon, with failures localized to stage-bridging. Reinforcement learning (RL) narrows this composition gap, especially at longer horizons, but unanchored RL drifts—producing valid stage progress while ignoring the instructed target. Stable gains require two complementary forms of anchoring: instruction-style prompting strengthens prompt-side goal-conditioning, especially at shorter horizons, whereas KL regularization to the SFT reference policy prevents RL-induced drift across horizons; reward shaping mainly provides denser credit. Finally, we identify a Decomposition Paradox: models trained only on long compositions can reach intermediate targets yet fail the corresponding prefix subtasks because stopping at instructed intermediates is never supervised.

Discovering object-centric representations from images can significantly enhance the robustness, sample efficiency and generalizability of vision models. Works on images with multi-part objects typically follow an implicit object representation approach, which fail to recognize these learned objects in occluded or out-of-distribution contexts. This is due to the assumption that object part-whole relations are implicitly encoded into the representations through indirect training objectives. We address this limitation by proposing a novel method that uses explicit graph representations for parts and introduce a new co-part algorithm for multi-part object discovery. The part representations are refined with a part-centric regularization objective. We then introduce three benchmarks to evaluate the robustness of object-centric methods in recognizing multi-part objects within occluded and out-of-distribution settings. Experimental results on simulated, realistic, and real-world images show marked improvements in the quality of discovered objects compared to state-of-the-art methods, as well as the accurate recognition of multi-part objects in occluded and out-of-distribution contexts. We also show that the discovered object-centric representations can more accurately predict key multi-part object properties in a downstream task, highlighting the potential of our method to advance the field of object-centric representations.

Computational RNA design methods routinely evaluate designed sequences by refolding them with the same structure-prediction model used during optimization, measuring agreement with the design target. While scalable, this practice carries a fundamental risk: when optimization and evaluation share the same underlying model, high scores can reflect model-specific idiosyncrasies rather than genuine structural quality. To characterize the severity and mechanism of this problem, we audited nine RNA design methods spanning four algorithmic paradigms, evaluating approximately 11,000 sequences against predictors from two independent model families: physics-based thermodynamic models and machine-learning models, alongside five tertiary-structure predictors and large-scale SHAPE chemical-mapping data. We find that 78.1% of designs produced by single-objective optimization pass one predictor yet fail another, while ensemble-based methods reduce this disagreement 30-fold. A controlled experiment identifies optimization objective breadth, not search strategy, as the primary driver of this fragility. Cross-predictor disagreement carries a calibrated experimental signal: lower disagreement predicts higher SHAPE accuracy across 40,000 sequences, yet remains null-to-anti-predictive for biological function, establishing a clear scope boundary. We release **ACCORD** (**A**cross-oracle **C**alibration for **CO**mputational **R**NA **D**esign), a benchmarking workflow that reports per-predictor scores, experimentally calibrated uncertainty tiers, and explicit warnings for invalid use cases, providing the community with a principled foundation for RNA design evaluation.

Multi-objective reinforcement learning (MORL) is a fundamental problem for modern AI, with applications spanning robotics, LLMs, and reasoning. A central challenge is to learn policies that balance competing objectives, such as speed versus energy in robotics, or helpfulness versus honesty in alignment. Optimal policies can vary sharply with the preferred objective weights, and the severity of this variation depends crucially on the degree of misalignment among objectives, making per-preference learning sample-inefficient. To formalize this, we introduce an *objective-conflict coefficient* and use it to derive near-optimal regret bounds for online MORL that quantify the impact of misalignment on learning efficiency. Motivated by this analysis, we propose *routed ensemble policy learning*, an algorithm that maintains a small set of basis policies and dynamically routes trajectories to the policy with the highest potential reward. We further design a scalable, kernel-based attribution algorithm that estimates how feedback signals from one set of trajectories influence policy learning on others. Unlike existing attribution methods, our approach captures nonlinear interactions, such as synergy and antagonism between trajectories, to explain objective conflict. We extensively evaluate our approach across diverse environments and benchmarks: routed ensembles improve average performance by 4.3\% over MORL baselines on several environments from the Meta-World and MO-Gymnasium benchmarks, and kernel-based attribution improves correlation with leave-one-out analysis over existing baselines by 50\%. When applied to downstream task selection, kernel-based attribution yields a 27\% improvement in reward over baseline attribution methods.

Many decision-making problems involve multiple objectives, where actions affect several performance metrics, fairness criteria, or safety constraints. We study multi-objective causal bandits with multiple reward nodes, where actions correspond to interventions on subsets of variables in a causal graph and performance is evaluated through Pareto optimality. Existing approaches to multi-objective bandits typically define optimality at the level of individual actions, using pairwise dominance or scalarization. In contrast, randomized decision rules induce convex combinations of action-level reward vectors, so the relevant achievable set is the convex hull of these rewards. Thus, an intervention may be suboptimal even if no single intervention dominates it, because it can be dominated by a randomized policy over other interventions. We formalize this policy-level phenomenon and show that it has consequences for both causal action-space reduction and online learning. First, we provide a necessary-and-sufficient graphical characterization of possibly Pareto-optimal minimal intervention sets (PPOMISs). Our characterization yields a minimal, sound, and complete candidate intervention family from the graph alone, correcting prior formulations that may include intervention sets that are never Pareto-optimal under any compatible structural causal model. Second, over this reduced intervention space, we design an online UCB-style algorithm that eliminates actions using dominance tests against convex combinations of other actions, and prove logarithmic gap-dependent Pareto regret. Finally, we study constrained multi-objective causal bandits, where feasibility and optimality may be realized only with randomized policies, and develop an online UCB-style constrained bandit algorithm with sublinear regret and constraint-violation guarantees.

We study stochastic multi-objective optimization when each objective may be non-smooth and non-convex. We introduce the notion of $(\delta,\epsilon)$-Pareto Goldstein stationary points (PGSP) to characterize the convergence of solving multi objective optimization. The $(\delta,\epsilon)$ generalizes the definition of $(\delta,\epsilon)$-Goldstein stationary point for single objective non-smooth non-convex optimization and the $\epsilon$-Pareto stationary point for solving multi objective optimization with smooth objectives. We propose the multi-gradient-free method (MGFM), which finds $(\delta,\epsilon)$-PGSP with $\tilde{\mathcal{O}}(m^2d^{3/2}\delta^{-1}\epsilon^{-4})$ oracle complexity to the stochastic function values, where $m$ is the number of objectives and $d$ is the problem dimension. We further propose MGFM+, a faster multi-gradient-free method based on variance reduction, which improves the complexity to $\tilde{\mathcal{O}}(m^2d^{3/2}\delta^{-1}\epsilon^{-3})$. These provide the first non-asymptotic analysis for multi-nonsmooth-nonconvex-objective optimization. \end{abstract}

Realizing stable neural decoding over extended periods remains a significant challenge, primarily because invariant task-related neural dynamics are inextricably entangled with inherent signal non-stationarity and the physical drift of electrode-neuron interfaces. This work introduces LNDN (Long-term Neural Decoding Network), a hierarchical framework designed to decouple category-specific neural dynamic manifolds from representational drift, sustaining decoding precision without periodic recalibration. The proposed architecture addresses representational drift through an integrated tri-level alignment strategy. At the physical feature level, a decoupled representation and dynamic gating module isolates the physical identity of neurons from their transient states, adaptively filtering stochastic neural noise. This is further strengthened at the decision level by a Mixture-of-Experts (MoE) architecture, which employs a parallel soft-voting mechanism to suppress high variance induced by local representational distortions. Finally, at the manifold level, Adaptive Batch Normalization (AdaBN) and latent contrastive learning, combined with second-order correlation alignment, explicitly anchor the geometric consistency of the low-dimensional neural manifold over a period of months. Systematic evaluations on a longitudinal olfactory dataset, involving 9 mice performing a four-odor decoding task, demonstrate the efficacy of this approach. When trained exclusively on data from the initial four weeks, LNDN maintains an average accuracy of 83.67\% on completely unseen tests spanning the subsequent eight weeks, significantly outperforming mainstream domain adaptation and advanced neural decoding baselines. This framework offers a scalable, "set-and-forget" solution for robust, long-term invasive brain-computer interface applications.

Partially Observable Markov Decision Processes (POMDPs) are systems in which one agent interacts with a stochastic environment, and receives only partial information about the current state. In a multi-environment POMDP (MEPOMDP), the initial state is unknown, and assumed to be adversarially chosen. In this work we focus on computing the optimal value and policy in MEPOMDPs with finite-horizon objectives. That problem is known to be PSPACE-complete in POMDPs. Our main results are as follows: (1) we establish that it is also PSPACE-complete in the more general setting of MEPOMDPs; (2) we present a practical algorithm and evaluate it on classical benchmarks, significantly outperforming the only previously known algorithm.

Randomized Smoothing (RS) is a principled and widely adopted approach for certifying the robustness of black-box models, such as neural networks, against adversarial perturbations. We propose an optimization perspective that unifies several prior randomized smoothing certificates. We then show how to reduce the underlying high-dimensional worst-case optimization problem to an equivalent two-dimensional formulation under a double- or multi-sampling scheme, enabling efficient solutions via convex optimization. By exploiting additional information about the variance of the smoothed classifier across different smoothing distributions, we derive certified bounds that improve upon standard certificates. We show results on both classification and regression tasks.

We study multi-armed bandits (MABs) augmented with best-action queries, in which the learner may additionally query an oracle that reveals the best arm in the current round. This setting was recently characterized by Russo et al. [2024] in the full-feedback model, where the learner observes the rewards of all arms after each round. They show that, in both stochastic and adversarial environments, $k$ best-action queries reduce the optimal $\widetilde{\mathcal{O}}(\sqrt{T})$ regret to $\widetilde{\mathcal{O}}(\min\{T/k,\sqrt{T}\})$. Whether this improvement extends to the more realistic bandit-feedback model---where the learner observes only the reward of the played arm---was left as an open problem. We fully resolve this question. When rewards are stochastic but correlated among arms, we show that the full-feedback result does not carry over: any algorithm must incur regret at least $\Omega(\sqrt{T-k})$. This lower bound directly extends to adversarial environments. On the positive side, we show that $\widetilde{\mathcal{O}}(\min\{T/k,\sqrt{T-k}\})$ regret is still achievable when rewards are stochastic and i.i.d., and establish a matching lower bound, up to logarithmic factors. Together, these results provide a complete characterization of the benefits of best-action queries in the bandit-feedback model.

Offline MARL increasingly relies on generative policies to model multimodal joint behavior, typically by distilling a centralized teacher into decentralized one-step actors under the CTDE. We identify a failure mode at the teacher training stage: standard flow-based teachers pair noise with replay targets independently, so nearby noise samples can be routed toward conflicting coordination modes. The teacher then produces samples between valid modes, and because the distillation loss regresses each local actor onto the conditional mean of the teacher's output given local input, this error is not absorbed but propagated to the student. To remove this teacher-side artifact, we propose Mode-Support Semi-Discrete Optimal Transport (MoSDOT), which summarizes multimodal replay into a finite mode support with prescribed capacities and uses conditional semi-discrete optimal transport to assign each noise sample to a single mode before teacher training. We additionally study a common-randomness variant that uses a shared noise component at execution to expose the residual gap intrinsic to strict-product execution. On controlled diagnostics and offline MARL benchmarks, MoSDOT improves endpoint quality and routing consistency, particularly on datasets exhibiting multimodal joint behavior.

Direct preference optimization (DPO) is a simple and effective alignment strategy for large language models (LLMs) based on pairwise preferences between two candidates. In recommender systems, however, user feedback is rarely pairwise. For a given context, e.g., a user, a session, or a conversation, we typically observe set-wise preferences with multiple positive items, where every positive item should outrank every unobserved or explicitly negative item, with no prescribed order among the positives or the negatives themselves. A natural generalization is to use the Plackett–Luce (PL) reward model, which extends the Bradley–Terry (BT) reward model underlying vanilla DPO from pairwise preferences to full rankings of candidates. However, adapting the PL model to set-wise preferences requires marginalizing over all consistent permutations of the positives and negatives respectively, which is intractable. To address this fundamental challenge, we propose Mult-DPO, a novel DPO objective with a tractable multinomial reward model over set-wise preferences. We show that, like the BT and PL reward models, the multinomial reward admits a closed-form DPO-style objective, enabling direct alignment of LLMs without reinforcement learning (RL). In addition, we prove that the multinomial DPO loss is a tractable upper bound on the exact marginalized PL DPO loss when optimizing against the set-wise preference data. We further characterize the tightness of this bound in terms of relative total weight (i.e., exponentiated rewards) of positives versus negatives, which provides insights into tightening the bounds with more or harder negatives. Finally, we extend the framework to a group-wise setting that accommodates multiple preference levels. Code and datasets are available at https://anonymous.4open.science/r/mult-dpo-41C7.

We develop a gradient flow on the space of probability measures defined on matrix-valued parameters induced by regularized Muon, an analytically smoothed version of the idealized Muon optimizer. The key observation is that the regularized orthogonalization map is the gradient of a smooth Fenchel-dual smoothing of the nuclear norm. This identifies the (regularized) Muon update as a mirror/prox step in the update variable, with momentum acting as the dual coordinate. We use this structure to lift Muon from a single matrix parameter to finite-particle probability objectives of the form $J(\rho)=R\left(\int F d \rho\right)$, a setting motivated by mean-field descriptions of neural-network training, and derive the inertial continuous-time limit. Using this structure, we derive the finite-particle continuous-time limit under the inertial scaling of step size and momentum, and then pass to a phase-space mean-field equation over probability laws on parameter-momentum pairs. The resulting flow can be shown to be a damped Hamiltonian probability dynamics whose kinetic energy is induced by the regularized Muon mirror potential. We prove an exact Hamiltonian dissipation identity, showing that the Hamiltonian energy decreases monotonically- leading to the descent of the target objective functional. Under appropriate gradient dominance assumptions, we obtain continuous and discrete time exponential convergence rates. We also study the well-posedness of the mean field limit equation and establish propagation of chaos guarantees for the interacting particle system. Finally, we extend the formulation to Hilbert-valued feature maps on product matrix spaces, yielding a blockwise Muon probability flow applicable to smooth transformer mixture-of-experts models.

Motion instruction generation in cross-video comparison aims to produce corrective feedback that describes the differences between a query and a reference motion. However, existing models often generate instructions that exhibit motion hallucinations, failing to reflect actual kinematic differences between paired videos. To systematically investigate these hallucinations, we introduce MotionHalluc, a dedicated benchmark for evaluating motion hallucinations in paired-video comparison. MotionHalluc comprises 1540 fine-grained questions over 553 video pairs, evaluating hallucinations along three core dimensions: (1) directional hallucination, (2) attributional hallucination, and (3) temporal hallucination. Extensive evaluations of state-of-the-art large multimodal models demonstrate high susceptibility to these hallucinations. Furthermore, we provide Perceive-Parse-Verify (PPV) as a training-free measurements extraction and verification baseline that converts candidate instructions into executable measurement queries and supplies kinematic measurements at inference time. Our results show that this simple measurements injection yields an average 10.6% performance gain across models, suggesting that motion reasoning with explicit quantitative measurements is a key factor in reducing hallucinations in cross-video comparison.