NeurIPS 2026 Papers

Exact solution of hard combinatorial optimization problems often relies on strong convex relaxations, but solving these relaxations repeatedly inside a branch-and-bound algorithm can be prohibitively expensive. Hence, we consider this challenge for \new{Max-Cut problem} (Max-Cut), where branch and bound commonly uses semidefinite programming (SDP) relaxations to bound subproblems. We propose a Max-Cut-specific \new{graph neural network} that serves as a principled, lightweight neural proxy for these SDP solvers and can be plugged directly into an exact branch-and-bound framework. The proposed architecture has update steps of complexity $\mathcal{O}(n^2 + ne)$, and predicts both primal- and dual-feasible SDP solutions. The primal SDP solutions yield feasible Max-Cut solutions via the Goemans--Williamson algorithm. In addition, it is trained in a self-supervised fashion without requiring solved SDP relaxations as labels. Empirically, we show that our architecture can substantially reduce the cost of bounding in exact Max-Cut solving by up to $10.6 \times$ compared with using the state-of-the-art SDP solver Mosek. Our work highlights the potential of learned, validity-preserving surrogates for accelerating exact optimization over structured convex relaxations.

Large language models (LLMs) can solve every intermediate step of a multi-step math problem on its own and still fail the full problem, even when given a roadmap of the steps and all of their answers. We introduce OracleLadder, a diagnostic evaluation that locates where LLM math reasoning fails by giving the model increasing levels of oracle help. For each problem, a teacher model writes a fixed roadmap of intermediate sub-goals (milestones), and a deterministic symbolic verifier grades every answer. Testing the model with no help, with the roadmap, with the roadmap plus the milestone answers, and on each milestone alone sorts each failure into one of five reasoning gaps. On 354 NuminaMath problems and six models from 8B to 671B parameters (Qwen3, gpt-oss, Llama 3.3, DeepSeek-V3.1), the largest gap for every model is the composition gap, a stricter form of the compositionality gap. It covers 33-48% of problems, and 24-37% after removing problems that an LLM review flags as grading errors. Accuracy and milestone-help recovery rank the two strongest models differently, and two RLVR runs with similar accuracy gains move problems differently. The roadmap effect replicates on MATH500 and AIME 2024/25, per-problem recovery agrees for 83-87% of problems under an independent second teacher, and the help ladder carries over to code generation. We release the data, roadmaps, prompts, and code at https://github.com/slark-prime/OracleLadder.

PDE foundation models (PDE-FMs) promise general-purpose surrogate simulation, yet deploying a pretrained model to a new physical regime inevitably introduces distribution mismatch, demanding task-specific post-training. The dominant approach, supervised fine-tuning (SFT), is fundamentally off-policy: the model trains on pre-generated states but is evaluated autoregressively on its own. In chaotic regimes, this mismatch is catastrophic as per-step errors compound exponentially along the Lyapunov spectrum, and exact pointwise trajectory matching beyond the predictability horizon becomes an ill-posed training signal. To resolve this, we introduce **Solver-as-Teacher (SaT)**, an on-policy post-training framework for PDE-FMs. During training, the student rolls out autoregressively; a numerical solver branches multi-step correction targets from each student-visited state; and the student is updated against these solver corrections, learning to correct its own rollout dynamics. We instantiate SaT in a unified post-training suite with SFT, physics-informed temporal alignment, and learned-teacher on-policy distillation. Across seven 2D/3D PDE benchmarks and six pretrained PDE-FMs, SaT variants achieve the lowest 50-step rollout RMSE in 23 of 24 in-distribution model--task pairs. The best SaT variant reduces RMSE over SFT up to 90.0\%, and SaT gives the lowest RMSE on all seven OOD parameter-shift benchmarks.

Decomposition-based Programming-by-example (PBE) scales performance by splitting tasks into subtasks that a learned synthesizer solves: a decomposer predicts intermediate subgoals, and a synthesizer generates programs conditioned on them. Current approaches train the decomposer to imitate ground-truth (GT) subgoals, implicitly treating decomposition quality as intrinsic to the task. We challenge this assumption: for bounded solvers with fixed inductive biases, GT decompositions reflect the annotator’s factorization choices – not the solver’s search dynamics. A decomposer trained to match GT decompositions may therefore propose subgoals that are logically valid yet intractable for the solver. We propose Solver-Aware Decomposition (SAD), a training framework that retains supervised training on GT subgoals as a structural scaffold, while additionally optimizing the decomposer via direct feedback from a frozen synthesizer. Subgoals are rewarded based on the synthesizer’s loss on the target program – a signal of subtask difficulty that encourages decompositions the solver can act on. Our experiments reveal an accuracy paradox: higher agreement with GT decompositions does not improve synthesis success – even though the synthesizer was trained on the very same GT data the decomposer is optimized to mimic. SAD instead learns decompositions that trade GT alignment for solver tractability, yielding consistent gains in synthesis and end-to-end task accuracy across two PBE domains. Moreover, SAD solves tasks that a GT decomposition oracle fails – empirical evidence that GT decompositions are not universally optimal for bounded solvers, and that decomposition quality is solver-relative, not intrinsic.

Electrolyte conductivity is not a property of isolated molecules, but a response over a formulation landscape defined by solvents, salts, composition, salt mole ratio, and temperature. The same molecular component can play different effective roles as its amount and operating conditions change, while the underlying formulation state is observed only through macroscopic conductivity measurements. This makes conductivity prediction a distinctive mixture learning problem: a model must learn how molecular identities become formulation-specific states, rather than merely how molecules are represented. We introduce SolvMix, a framework for learning formulation-state landscapes for electrolyte conductivity prediction. SolvMix constructs component tokens for solvent and salt molecules, calibrates them into amount-aware component states before mixture interaction, and predicts conductivity through a temperature-formatted readout. We evaluate SolvMix on three curated electrolyte conductivity benchmarks, CALiSol-23, DiffMix, and Bamboo-mixer, covering diverse solvents, salts, compositions, salt mole ratios, and temperatures. Across standard splits on all three benchmarks and binned out-of-distribution (OOD) splits on Bamboo-mixer, SolvMix outperforms strong molecular-representation, mixture-aggregation, and geometric-interaction baselines under the reported protocols. Ablations show that the best-performing formulation-state construction combines amount-and-type-aware component tokens, multiplicative amount calibration, token-level interaction followed by mean pooling, and late-concat temperature formatting. OOD results further show clear gains under formulation-level shifts, where static component descriptors and local interaction patterns are least aligned with the required generalization. These results suggest that electrolyte conductivity prediction benefits from treating formulation-state construction as a first-class modeling problem, beyond molecular representation learning or explicit local interaction modeling.

Multilingual large language models often produce inconsistent reasoning and answers across semantically equivalent prompts in different languages. Prior work suggests that intermediate representations can be relatively language-agnostic, but generation becomes increasingly language-specific as models commit to discrete output tokens. This is problematic because language-specific lexical choices can cause semantically equivalent reasoning paths to diverge across languages. This motivates searching for a cross-lingual alignment signal that is less tied to any single vocabulary item or script. We propose **SOLAR**, an auxiliary objective for supervised fine-tuning that aligns _soft-token_ representations across languages, using English as a pivot. Soft tokens are probability-weighted mixtures over the vocabulary embeddings, yielding continuous representations that can aggregate information from semantically related tokens across languages. We then align each non-English soft-token summary to its English counterpart in the shared embedding space. Across four multilingual reasoning benchmarks, SOLAR improves accuracy by up to +17.7 points over the base model and +3.8 over standard supervised fine-tuning, with the largest gains on low-resource languages. SOLAR also strengthens final-layer cross-lingual similarity and substantially reduces language-cluster separability, suggesting that aligning soft-token representations helps preserve shared semantic structure during multilingual reasoning.

Recent advancements in zero-shot reinforcement learning (RL) have facilitated the extraction of diverse behaviors from unlabeled, offline data sources. In particular, forward-backward algorithms (FB) can retrieve a family of policies that approximately solves any standard RL problem (with additive rewards, linear in the occupancy measure), given sufficient capacity. While retaining zero-shot properties, we tackle the greater problem class of RL with general utilities, in which the objective is an arbitrary differentiable function of the occupancy measure. This setting is strictly more expressive, capturing tasks such as distribution matching or pure exploration, which may not be reduced to additive rewards. We show that this additional complexity can be captured by a novel, maximum entropy (soft) variant of the forward-backward algorithm, which recovers a family of stochastic policies from offline data. When coupled with zero-order search over compact policy embeddings, this algorithm can sidestep iterative optimization schemes, and optimizes general utilities directly at test-time. Across both didactic and high-dimensional experiments, we demonstrate that our method retains favorable properties of FB algorithms, while also extending their range to more general RL problems.

Video generation has advanced rapidly, producing photorealistic videos from text or image prompts. Meanwhile, film production and social robotics increasingly demand multi-person videos with rich social interactions, including conversations, gestures, and coordinated actions. However, existing models offer no explicit control over interactions, such as who performs which action, when it occurs, and toward whom it is directed. This often results in wrong person performing unintended actions (actor-action mismatch), disordered social dynamics, and wrong action targets. To address these challenges, we present SocialDirector, a training-free interaction controller that enhances the generation model by modulating cross-attention maps. SocialDirector contains two modules: Social Actor Masking and Directional Reweighting. Social Actor Masking constrains each person's visual tokens to attend only to their own textual descriptions via a spatiotemporal mask, avoiding actor-action mismatch and disordered social dynamics. Directional Reweighting amplifies attention to directional words (e.g., "leftward", "right"), leading each action towards its intended target. To evaluate generated social interactions, we annotate existing datasets with interaction descriptions and build a fully automated evaluation pipeline powered by open-source VLMs. Experiments on different video generation models show that SocialDirector significantly improves interaction fidelity and approaches the upper bound set by real videos.

Multi-agent LLM evaluations and large-scale social simulations often treat multiple copies of the same model as comparable replicates after they interact. We test this assumption with SocCogEval, a controlled-clone assay for Social Cognitive Transfer (SCT), and find that it fails. Agents share the same base model, system prompt, and decoding parameters. When briefs are assigned, the brief is the only initial difference. On Qwen3-122B-FP8, the matched interaction contrast holds asymmetric briefs fixed and toggles 30 rounds of interaction. It yields stable off-topic BFI-10 response-profile drift on two topically disjoint scenarios. The effect is Delta =+0.92 on Greenfield (95% CI [+0.61,+1.22], g =+1.07) and Delta =+ 0.91 on Riverton ([+0.60,+1.24], g =+ 0.96, about 0.18 Likert points per BFI factor. Brief-only controls do not explain the drift. A verbatim-history ablation with SRM extraction disabled remains positive, so typed memory extraction is not the source of the signal. Five additional model variants provide positive but uneven breadth. Five of ten non-primary scenario cells are positive at alpha = 0.05, and no variant shows a significant reversal. The result limits iid-clone assumptions in multi-agent evaluation: interacting clones are not independent replicates unless paired no-interaction controls show otherwise.

Existing soccer commentary models are often designed for pre-segmented clips or localized events. When deployed on untrimmed full-match videos with sliding windows, they can produce delayed, repeated, or poorly synchronized commentary. Recent streaming video-language models make low-latency full-match narration feasible, but they often favor general real-time descriptions rather than professional, event-grounded soccer commentary. They may describe nearby actions while failing to mention key events such as goals, cards, substitutions, and offsides correctly and on time. In this paper, we introduce **SoccerNarrate**, a data, model, and evaluation framework that bridges low-latency streaming narration with event-grounded professional soccer commentary. First, we construct **SoccerNarrate-Data**, a large-scale time-anchored dataset with word-level ASR alignment, quality filtering, and entity calibration. Second, we perform **macro-window preference alignment(MWPA)**, which aligns the model with complete event-level commentary semantics by comparing causal multi-step rollouts from the same streaming prefix while keeping second-level inference unchanged. We further use event-mismatched human commentaries as counterfactual negatives to emphasize event semantics over commentary style. Third, we introduce **SoccerNarrate-Eval**, an event-centric benchmark based on temporally constrained event entailment. Full-match experiments show that SoccerNarrate improves event coverage and event-aligned precision over strong offline and streaming baselines. Data and models will be released.

In recent years, Large Language Models (LLMs) have demonstrated remarkable performance in tasks such as mathematical reasoning and code generation. However, as LLMs are increasingly deployed as autonomous agents, their reasoning capabilities in dynamic, human-like social interactions remain largely unexplored. To bridge this gap, we propose the benchmark SoDeArena—Social Deduction Arena, designed to evaluate the socially-situated reasoning capabilities of LLMs through a diverse set of interactive games. Through large-scale multi-agent simulations and human interaction experiments, we have identified three key insights for improving current LLMs: (1) the overall proficiency of models in social deduction is fundamentally bottlenecked by model scale and reasoning capabilities; (2) models lack proactive intent management, defaulting instead to strategic passivity and output conformity during multi-agent interactions; and (3) LLMs exhibit dual behavioral biases, manifesting as a rigid safety alignment in adversarial roles and a pathological reliance on shallow positional patterns over robust reasoning processes. These findings point to potential directions for the future development of AI systems with robust socially-situated reasoning capabilities.

As the context length of large language models (LLMs) grows, the key-value (KV) cache memory overhead becomes a critical bottleneck, limiting long-context inference efficiency. While FP8 attention has shown substantial promise in innovations like FlashAttention-3, its integration into the decoding phase of the DeepSeek Multi-head Latent Attention (MLA) architecture presents notable challenges. These challenges include numerical heterogeneity arising from the decoupling of positional embeddings, misalignment of quantization scales in FP8 PV GEMM, and the need for optimized system-level support. In this paper, we introduce SnapMLA, an FP8 MLA decoding framework optimized to improve long-context efficiency through the following hardware-aware algorithm-kernel co-optimization techniques: (i) RoPE-Aware Per-Token KV Quantization: Motivated by our analysis of the heterogeneous quantization sensitivity inherent to the MLA KV cache, this approach preserves the RoPE part in high precision. Furthermore, per-token granularity is employed to align with the autoregressive decoding process and maintain quantization accuracy. (ii) Pre-posed Scale Domain Alignment, where we skillfully project RoPE components into the quantization domain to mitigate pipeline stalls caused by mixed-precision accumulation; (ii) Quantized PV Computation Pipeline Reconstruction: Addresses the misalignment of quantization scales in FP8 PV computation caused by the shared KV structure of the MLA. (iii) End-to-End Dataflow Optimization: Establishes an efficient data read-and-write workflow using specialized kernels, ensuring streamlined data flow and improved performance. Extensive experiments on state-of-the-art MLA LLMs show that SnapMLA achieves up to a 1.91× improvement in throughput on long-output decoding workloads while maintaining near-parity benchmark quality compared with the BF16 baseline on the evaluated reasoning and code-generation benchmarks. The code corresponding to this work is included in the supplementary material.

We study the query and communication complexity of sampling from high-dimensional Gaussian distributions using gradient information. In the standard oracle model, exact gradients expose only matrix-vector products with the precision matrix, leading to polynomial approximation barriers and a characteristic $\sqrt{\kappa}$ dependence on the condition number. We show that this barrier disappears when the sampler is allowed to query \emph{smoothed gradients}, namely scores of Gaussian-convolved distributions. For a Gaussian target with precision $\Lambda$, a smoothed-score query at noise level $\tau$ gives access to the resolvent $(\Lambda+\tau^{-1}I)^{-1}$. Combining geometrically spaced noise levels with sinc-quadrature rational approximation, we obtain a sampler with $$ q = O\left( \left(\log\kappa+\log(\sqrt d/\varepsilon)\right) \log(\sqrt d/\varepsilon) \right) $$ smoothed-gradient queries for total variation error $\varepsilon$, improving the condition-number dependence from $\sqrt{\kappa}$ to logarithmic. We also study finite-bit gradient oracles. Using coordinatewise quantization of the transformed smoothed-gradient answers and a final dithering step, we obtain a sampling scheme whose total communicated gradient information is polylogarithmic in $\kappa$; in particular, for fixed dimension and accuracy, the bit complexity is $O(\log^2\kappa)$. To complement these upper bounds, we introduce a channel-synthesis, or reverse-Shannon, converse technique for sampling lower bounds. This converts total-variation simulation guarantees into communication requirements and yields an $\Omega(\log\kappa)$ lower bound on the required gradient information. Together, these results identify smoothed gradients as a strictly more powerful oracle for sampling and give nearly matching upper and lower bounds for its finite-bit complexity.

Reinforcement learning with verifiable rewards (RLVR) has greatly advanced large reasoning models (LRMs), but it requires timely training on a huge fully-annotated dataset. To this end, data-efficient RLVR methods have been widely studied from two perspectives: (i) data selection methods identify a small subset of "golden" samples that yield near-full-data performance, but they rely on a pre-existing pool of labeled data. (ii) unsupervised RLVR methods train the model using its own internal supervision signals on large-scale unlabeled data, yet they exhibit suboptimal performance. Accordingly, we investigate the "*pick in the dark*" setup for RLVR, which aims to select, without prior supervision, unlabeled samples that are most beneficial for training and worthy of annotation. Through systematic analysis, we demonstrate that smart picks hinge on a well-calibrated uncertainty estimator to enable strategic partitioning of data for adaptive training regimes. Building on this insight, we propose **PivotTrace**, a three-way data triage framework that leverages attention dynamics to trace *metacognitive pivots* during reasoning. By precisely quantifying uncertainty through pivot density, PivotTrace achieves automated data routing to synergistically maximize both annotation and training efficiency. Empirically, PivotTrace surpasses the fully supervised LRM with only **29.3%** annotated samples and **2.75**$\times$ faster convergence.

Deploying deep learning models across heterogeneous hardware requires each model to jointly satisfy a bundle of coupled constraints on accuracy, latency, memory, and energy. Maintaining a specialist for every deployment scenario is operationally prohibitive, so practitioners need a small portfolio of $K$ models that collectively covers many deployment profiles. Existing hardware-aware NAS and Pareto-based approaches target marginal objectives and do not directly address this downstream decision. We formalize it as Deployment Portfolio Selection over a fixed pre-measured archive, where a profile is covered only when a single retained model simultaneously satisfies its entire constraint bundle. The induced objective is weighted maximum coverage, which is NP-hard but monotone submodular, so greedy selection inherits a $(1-1/e)$ guarantee, and sample-then-optimize admits a finite-sample bound. Across an 18-family sweep on HW-NAS-Bench, direct bundled-coverage optimization is most valuable in the small-portfolio, low-coverability regime: gains concentrate on the hardest profiles, are most robust at $K = 3$, and persist under three non-uniform demand models. Complementary analyses of remeasurement noise, runtime, and compact feasibility storage clarify when bundled coverage is preferable to scalarized or Pareto-based alternatives.

We study Slowly Annealed Langevin Dynamics (SALD), a sampler for tracking a path of moving target distributions and approximating the terminal target through time slowdown. We establish non-asymptotic convergence guarantees via a KL differential inequality, showing that slowdown improves tracking through contraction of intermediate targets and the complexity of the path. Motivated by training-free guided generation with pretrained score-based generative models, we further introduce Velocity-Aware SALD (VA-SALD), which explicitly incorporates the underlying marginal distributions of the pretrained model and uses slowdown to correct the additional deviation induced by guidance. This yields a principled framework for training-free guided generation for diffusion-based and related generative model families, together with convergence guarantees that clarify the roles of intermediate functional inequalities and guidance bias.

Software development is iterative, yet agentic coding benchmarks hide design issues through their single-shot setup. Recent iterative benchmarks attempt to remedy this but heavily constrain an agent's design decision space, making it impossible to faithfully measure how their decisions shape future extensions. We introduce SlopCodeBench, a benchmark comprising 36 problems and 196 checkpoints in which agents repeatedly extend their own solutions. Unlike prior iterative benchmarks, our evolving specifications demand architectural decisions but leave internal structure to the agent. We measure two forms of degradation: structural erosion (concentrated complexity) and verbosity (redundant code). Evaluating 15 coding agents across open and closed models, we find that no agent fully solves any problem end-to-end, and the best agent passes 14.8% of checkpoints. Quality degrades across checkpoints, with structural erosion rising in 77% of trajectories and verbosity in 75.5%. Compared to 473 open-source Python repositories, agent code is 2.3x more verbose and 2.0x more eroded, and the human repositories degrade less often and by smaller margins across their git histories. Explicit quality guidance reduces initial verbosity and erosion by up to a third, without affecting degradation rates. SlopCodeBench identifies a failure mode that single-shot benchmarks cannot detect: agents that pass checkpoints while producing code that erodes and bloats with each extension.

Scientific communication increasingly relies on slide-based narrated videos rather than static PDFs. However, transforming a paper into a presentation video is not a conventional text-to-video task. It requires preserving technical rigor, rendering dense multimodal assets faithfully, and synchronizing narration, subtitles, and cursor motion over long horizons. Current research faces two critical bottlenecks: (1) Benchmark Gap: existing evaluations are restricted to narrow domains or structured LaTex inputs with limited long-range supervision; (2) Evaluation Gap: current protocols often overlook the joint measurement of content fidelity, channel alignment, and actual knowledge transfer. To bridge these gaps, we introduce SLIDE P2V-BENCH, a cross-domain bench mark comprising 108 high-quality paper-video pairs spanning four domains and various durations, coupled with an auditable multi-dimensional evaluation suite. Furthermore, we propose PAPER2MEDIA, a slide-grounded agentic pipeline that produces editable presentations by synchronizing decoupled media channels via a shared semantic clock. Extensive experiments demonstrate that PAPER2MEDIA significantly outperforms existing automated baselines and, notably, achieves performance comparable to human-authored presentations in terms of narrative coherence, visual quality, and knowledge conveyance efficiency.

Quantum state tomography of pure non-Gaussian states is fundamentally limited by scarce and noisy data due to measurement-induced collapse and experimental drift. We introduce a novel reconstruction framework that parameterizes the wavefunction directly via an overparameterized neural network, trained using rank-1 factored gradient descent. We rigorously prove that this formulation's loss landscape is devoid of spurious local minima and strict saddles, guaranteeing all critical points are global minima. By utilizing the max-sliced Wasserstein-1 distance, our loss perfectly maps to the structure of homodyne measurements, structurally preventing gradient vanishing in low-shot regimes. On noisy two-mode cat states, our method achieves continuous fidelity improvements, successfully bypassing the noise-floor plateaus that limit standard iterative maximum-likelihood estimation.