NeurIPS 2026 Papers

We study nonstationary online linear programming (OLP), where orders arrive sequentially and follow independent but not-identical reward-resource distributions. The decision- maker seeks to maximize the expected total reward by making immediate and irrevocable acceptance or rejection decisions for each order, subject to a resource endowment available at the beginning of the planning horizon. Such problems arise in resource-constrained ML and AI systems, including inference admission control, online advertising and recommendation, and data-acquisition pipelines, where the mix and value of requests may change over time. We focus on a minimal-information regime in which the decision-maker observes only one independent sample from each future distribution before the horizon begins. We propose a novel re-solving algorithm that integrates a dynamic programming perspective with the dual-based frameworks traditionally employed in stationary environments. In the large-resource regime, where the resource endowment scales linearly with the number of order, we prove that our algorithm achieves $O((\log n)^2)$ regret across a broad class of nonstationary distribution sequences. Our results demonstrate that polylogarithmic regret is attainable even under significant environmental shifts and minimal data availability, bridging the gap between stationary OLP and more volatile real-world resource allocation problems.

Safety alignment in language models operates through two mechanistically distinct systems: refusal neurons that gate whether harmful knowledge is expressed, and concept neurons that encode the harmful knowledge itself. By targeting a single neuron in each system, we demonstrate both directions of failure --- bypassing safety on explicit harmful requests via suppression, and inducing harmful content from innocent prompts via amplification --- across seven models spanning two families and 1.7B to 70B parameters, without any training or prompt engineering. Our findings suggest that safety alignment is not robustly distributed across model weights but is mediated by individual neurons that are each causally sufficient to gate refusal behavior --- suppressing any refusal neuron bypasses safety alignment across diverse harmful requests.

How much of zero-shot benchmark accuracy is captured by word-level alignment between a pre-training corpus and the benchmark target? We study this question through word-level unigram cross-entropy (UCE), a tokenizer-agnostic, model-free measure of lexical alignment between a reference corpus and a target benchmark. Likelihood training allocates probability mass according to the pre-training corpus, and likelihood-based zero-shot evaluation partly reads out the lexical alignment between this mass and the benchmark target. Cleanly tracing how the lexical imprint of pre-training data scales with corpus--benchmark alignment requires controlled from-scratch pre-training that varies corpus identity while holding the training recipe fixed. Across this controlled sweep, spanning $11$ zero-shot benchmarks, $4$ pre-training corpora, and $3$ model scales, we find that corpus--benchmark lexical alignment, UCE, consistently tracks zero-shot accuracy on every benchmark, with corpora more aligned with the benchmark (lower UCE) achieving higher accuracy. The same signal extends from measurement to control at finer scopes. At the document level, strengthening the imprint by selecting training documents to maximize lexical alignment with the benchmark yields a data-selection rule that improves accuracy over same-size random sampling and an importance-resampling baseline across sources and scales. At the prompt level, matching the imprint per prompt by routing each prompt to the drafter whose domain corpus is most lexically aligned with it gives a training-free routing rule for speculative decoding and improves throughput over a generalist-drafter baseline. Taken together, pre-training corpora leave a measurable lexical imprint on zero-shot behavior, and UCE provides a model-free probe of lexical alignment between reference and target data.

AI security has become a critical issue as Deep Neural Networks (DNNs) are inherently vulnerable to adversarial attacks. While previous studies have demonstrated that adversarial training is one of the most effective defensive strategies, improvements in robustness often show significant class-wise disparities. This has established fair adversarial training, which aims to enhance the robustness of the worst-performing classes, as a crucial research direction. Although existing class-wise approaches can improve performance by adjusting individual class weights, they face severs scalability limitation on large-scale datasets due to the sparse volume of data available per class. To mitigate this issue without relying on explicit class-wise information, we propose a novel tri-regime optimization framework that fundamentally decouples the distinct sources of adversarial error at the sample level. Specifically, our method systematically suppresses unlearnable outliers via reliability gating, prioritizes genuine boundary threats through dynamic reweighting, and down-weights already safe examples to prevent redundant optimization. By isolating and prioritizing the effective adversarial frontier, our method strictly prevents robust overfitting and achieves superior worst-class robustness while maintaining high clean accuracy.

Calibration measures whether a model's predicted confidence aligns with its empirical accuracy, and is central to the reliable deployment of large language models (LLMs) in high-stakes domains such as medicine and law. While much recent work focuses on *improving* LLM calibration, the equally important question of how to *evaluate* it in realistic settings remains underdeveloped. Open-ended question answering (QA), the most common deployment setting for modern LLMs, is where existing evaluation methods fall short: logit-based metrics need restricted output formats and internal probabilities; verbalized confidence is self-reported and often overconfident; and sampling-based methods rely on task-specific extraction rules without a clear finite-sample target. We introduce **Sem-ECE** (**Sem**antic-Sampling **E**xpected **C**alibration **E**rror), a calibration evaluation framework for open-ended QA that samples answers from the model, groups them into semantic classes, and uses the resulting frequencies as confidence. We study two estimators within this framework: Sem₁-ECE, the same-sample self-consistency score, and Sem₂-ECE, a held-out variant that separates answer selection from confidence evaluation. We prove both are asymptotically unbiased, and further show that they agree on easy questions but diverge on hard ones with Sem₂ achieving strictly smaller calibration error, so their gap also serves as a diagnostic for question difficulty. Experiments on three open-ended QA benchmarks across five leading commercial LLMs match our theoretical predictions and show that Sem-ECE outperforms verbalized confidence and existing sampling-based methods, while complementing logit-based evaluation when internal probabilities are unavailable.

Terminal observations are not ordinary long-context text: they are heterogeneous, low-information-density execution traces in which sparse but exact evidence (e.g., error messages and file paths) is interleaved with large amounts of repetitive terminal output. For long-horizon CLI agents, retaining raw observations rapidly increases context cost and can dilute critical signals, while LLM-based summarization or fixed heuristics often fail to adapt across heterogeneous terminal tasks and may discard precise task-relevant evidence.We propose TACO, the first self-evolving Terminal Agent Compression framework, which treats compression rules as reusable, preservation-aware knowledge acquired from interaction trajectories. Rather than relying on manually designed rules, static pruning, or task-specific compressor training, TACO autonomously discovers, refines, and reuses structured compression rules from agent interaction trajectories. A Global Rule Pool accumulates effective rules across tasks, while task-time rule evolution adapts them online to the current workflow. This allows TACO to filter redundant terminal observations while conservatively preserving exact task-relevant evidence.Across six benchmarks, including TB 1.0, TB 2.0, SWE-Bench Lite, CompileBench, DevEval, and CRUST-Bench, TACO consistently maintains or improves task success across models and agent scaffolds. On TerminalBench, TACO yields 1%--4% absolute accuracy gains under standard evaluation and improves accuracy by 2%--3% under matched token budgets. On downstream benchmarks, it reduces total token consumption by 12%--27% while maintaining or improving task success. These results show that self-evolving observation compression can unlock latent capability in existing CLI agents by allocating context budget toward task-relevant evidence, without model fine-tuning or human-crafted compression rules.

Flexible continuous-time survival modeling is critical for capturing complex temporal dynamics in high-dimensional data; however, training such models remains challenging due to the intractable integral required for likelihood estimation. We introduce QSurv, a scalable deep learning framework that enables nonparametric continuous-time modeling without relying on time discretization or restrictive distributional assumptions. We propose a training objective based on Gauss-Legendre numerical quadrature, which approximates the cumulative hazard with high-order accuracy while facilitating efficient end-to-end training via standard backpropagation. Furthermore, to effectively capture non-stationary dynamics in complex architectures, we introduce time-conditioned low-rank adaptation, a mechanism that conditions general neural backbones on time by dynamically modulating weights via low-rank updates. We provide theoretical analysis establishing approximation error bounds for cumulative-hazard evaluation. Comprehensive experiments across synthetic benchmarks, large-scale real-world tabular datasets, and high-dimensional medical imaging tasks demonstrate that QSurv achieves competitive predictive performance with advantages in instantaneous hazard function estimation, enabling more interpretable characterization of time-varying risk patterns.

Virtual sensors replace expensive physical sensors in critical applications through machine learning by predicting target signals from available measurements. Existing virtual sensor approaches require application-specific models with hand-selected inputs for each sensor, cannot leverage task synergies, and lack consistent benchmarks. While emerging time series foundation models offer general-purpose, pretrained solutions in other domains, they are computationally expensive and limited to predicting their input signals, making them incompatible with virtual sensors. We introduce the first multi-task model for virtual sensors addressing both limitations. Our unified model can simultaneously predict diverse virtual sensors exploiting synergies while maintaining computational efficiency. It learns relevant input signals for each virtual sensor, eliminating expert knowledge requirements while adding explainability. In our large-scale evaluation on three standard benchmarks and an application-specific dataset with over 18 billion samples, our architecture reduces computation time by up to 415x and memory requirements by 951x, while maintaining or even improving predictive quality compared to unified baselines. Compared to existing isolated models for a single virtual sensor, our unified approach generates superior predictions at similar inference speed while scaling gracefully to hundreds of virtual sensors with nearly constant parameter count, enabling practical deployment in large-scale sensor networks.

Understanding the curvature evolution of the loss landscape is fundamental to analyzing the training dynamics of neural networks. The most commonly studied measure, Hessian sharpness ($\lambda_{\max}^H$) \textemdash the largest eigenvalue of the loss Hessian \textemdash determines local training stability and interacts with the learning rate throughout training. Despite its significance in analyzing training dynamics, direct measurement of Hessian sharpness remains prohibitive for Large Language Models (LLMs) due to high computational cost. We analyze \emph{critical sharpness} ($\lambda_c$), a computationally efficient measure requiring fewer than $10$ forward passes given the update direction $\Delta \bm{\theta}$. Critically, this measure captures well-documented Hessian sharpness phenomena, including progressive sharpening and Edge of Stability. Using this measure, we provide the first demonstration of these sharpness phenomena at scale, up to $7$B parameters, spanning both pre-training and mid-training of OLMo-2 models. We further introduce \emph{relative critical sharpness} ($\lambda_c^{1\to 2}$), which quantifies the curvature of one loss landscape while optimizing another, to analyze the transition from pre-training to fine-tuning and guide data mixing strategies. Critical sharpness provides practitioners with a practical tool for diagnosing curvature dynamics and informing data composition choices at scale. More broadly, our work shows that scalable curvature measures can provide actionable insights for large-scale training.

Bayesian neural networks (BNNs) offer principled uncertainty quantification, yet sampling from their posteriors via Hamiltonian Monte Carlo (HMC) remains challenging. While recent work theoretically identified the efficiency degradation of ReLU-based networks, smooth unbounded activations (_e.g.,_ GELU, Swish, Mish), which are prevalent in modern architectures, were assumed to be efficient due to their smoothness. In this work, we challenge this existing justification by deriving explicit local error formulas for the leapfrog integrator. Our analyses reveal that, in addition to differentiability, third-order curvatures of the potential energy also have a significant influence on HMC efficiency of BNNs inference. Empirically, we found that even smooth unbounded activations may degrade sampling performance as severely as piecewise linear activations. Thus, optimally tuning the step size for these networks may require a comparable empirical step size scaling as their piecewise counterparts. This result sheds light on the implications for architectural design in Bayesian deep learning.

Watermark robustness under paraphrase is usually reported as AUC against a named rewriter, making results hard to compare across watermark schemes, paraphrasers, and detectors. We propose a retained-signal reporting interface: if a watermark injects KL signal $\Delta=\KL(P_1\Vert P_0)$ and a paraphrase channel retains KL fraction $\rho$, then any detector's post-paraphrase advantage is controlled by $\Delta\rho$. We give explicit Pinsker and Bretagnolle--Huber threshold laws, prove the $\Theta(\sqrt{\Delta\rho})$ rate is sharp for any $(\Delta,\rho)$-only converse, and show the bound is implementation-blind once watermark families are matched by $\Delta$. For real LLM paraphrases, we instantiate the interface as a score-projected audit that estimates $\widehat{\Delta}\widehat{\rho}$ for a deployed detector and reports it with semantic preservation and the detector projection. In a KGW/Unigram $\times$ Qwen/Llama benchmark, this score-effective signal predicts post-paraphrase AUC across lengths, strengths, and paraphraser families. The resulting protocol separates injected signal, retained signal, semantic quality, and detector choice, replacing one-off AUC tables with a reproducible robustness report.

Variational quantum models are linear maps of the input state: any useful non-linearity must be engineered through the data encoding, entanglement pattern, ancilla tracing, classical readouts, or explicit classical layers. Although many such mechanisms have been proposed, there is no standard protocol that scores them on a common footing. Most published comparisons reduce non-linearity to either the accuracy on a single downstream benchmark or a single abstract expressibility number, and the two are rarely measured under matched training budgets, circuit widths, and noise assumptions. We introduce a reproducible evaluation protocol that decomposes non-linearity quality into four complementary scalar scores covering frequency reach, gradient-variance scaling, trainability efficiency on a chaotic dynamical task, and stability under depolarizing noise. In addition, we define a composite index with published weights, enabling methods to be ranked under a single criterion while preserving full access to the underlying components. We instantiate the protocol with six variational ansatzes spanning the standard taxonomy of quantum non-linearity sources (data reuploading, ancilla tracing, their combination, strongly entangling layers, a quantum convolutional network, and a quantum reservoir), together with a classical multilayer perceptron and a hybrid quantum-classical network as non-quantum reference points. The evaluation surfaces a central mismatch that single-number reporting hides: in our reference run, the composite leader (data reuploading) is near the bottom on held-out Lorenz one-step $R^2$, while the Lorenz leader (ancilla reuploading) is only third on the composite. The main outcome is a practical benchmark that makes these trade-offs visible and testable: with fixed tasks, budgets, and seeds, new methods can be added by registering a circuit builder and rerunning the same protocol, and multi-seed aggregates can be updated without changing metric definitions.

The public belief state (PBS), which is the posterior over game histories conditioned on public information, is a fundamental abstraction for designing game-theoretically sound search algorithms for imperfect-information games. Existing sound PBS search techniques for adversarial games fall into two categories: gadget-game-based algorithms (including Libratus, DeepStack, Pluribus, Supremus, and Student of Games) and ReBeL-based algorithms. Both these categories possess disadvantages, including a reliance on discontinuous functions, an inability to re-solve subgames, and an implicit representation of policies. In this work, we propose Gravel, a new approach for PBS search---different from these previous two categories---that achieves game-theoretic soundness via regularization. Unlike the aforementioned approaches, Gravel relies on smooth functions, can initiate search at any point in the game, and outputs explicit policies directly. We empirically demonstrate the advantages of Gravel for no-limit Texas hold'em, where we show that it outperforms ReBeL both in head-to-head competitions against Slumbot and in endgame solving. We include our codebase in the submission, making Gravel the first open-source high-performance no-limit Texas hold'em AI.

Quantitatively comparing writing systems at a worldwide scale is challenging because visual similarity must be inferred without relying on predefined linguistic or genealogical assumptions, and only limited ground-truth taxonomy is available for validation. We introduce a fully data-driven framework for comparing scripts based on learned glyph representations. Using a teacher--student model, we obtain deformation-invariant glyph embeddings and aggregate them into script-level distances. To enable principled model selection in the absence of labels, we construct synthetic script datasets that simulate key aspects of script evolution, including partial inheritance, visual distortion, and inventory variation. These benchmarks are used to independently select both the script-level distance metric and the clustering method, showing that nearest-neighbour aggregation and Ward hierarchical clustering best recover controlled relatedness structure. Applying the validated pipeline to 125 historically attested writing systems yields a global visual taxonomy that recovers coherent typological families while also revealing visually driven associations beyond strict genealogy. The resulting structure is stable under controlled perturbations and shows a moderate correlation with independent geographic and temporal metadata, indicating that learned representations capture non-trivial traces of historical transmission. Beyond large-scale comparison, this approach provides a quantitative tool for exploring relationships between writing systems and has potential applications in historical analysis and the decipherment of ancient scripts by identifying visually related alphabets.

Gromov--Wasserstein optimal transport (GWOT) aligns metric measure spaces by matching their within-domain relational structures, but large-scale GWOT remains challenging because its objective is nonconvex and projection onto the transport polytope is often solved only approximately in practice. This leads to a gap between practical projected-gradient implementations and convergence theory, which typically assumes exact projections. For squared-loss GWOT, we propose an inexact projected-gradient framework with a verifiable feasibility-residual-based inexact condition for the projection subproblem. This condition is directly computable and avoids unknown quantities such as the exact projection point. Under this implementable condition, we prove subsequential convergence to stationary points and, with a mild tolerance-decay condition, convergence of the whole sequence. The resulting method retains the simplicity and sparsity of projected-gradient schemes while providing rigorous convergence guarantees, turning projected-gradient methods into a principled and scalable approach for GWOT with provable reliability.

Differential privacy (DP) has traditionally been used to provide theoretical upper bounds on an algorithm's stability to changing its training data. In modern machine learning applications, achieving strong tradeoffs between utility and theoretical privacy is challenging, and thus one may optimistically hope that existing theoretical analyses are loose. Recent work on \emph{privacy auditing} has adopted a dual viewpoint, instead lower bounding the true privacy of an algorithm by constructing empirical distinguishing events. The auditing literature has thus far yielded a pessimistic outlook on the looseness of theoretical privacy bounds for DP-SGD, the de facto private training method in modern ML, as nearly-matching empirical lower bounds have been achieved under various threat models \cite{NasrHSBTJCT23, AnnamalaiC24, CebereBP25}. In this work, we propose the empirical privacy lower bound of an algorithm as a concrete metric to optimize for, complementary to the theoretical upper bound. We give a lightweight defense framework that generically augments optimization methods in the ML pipeline to have significantly-improved empirical privacy on standard benchmarks. Moreover, we show that our framework comes at \emph{no theoretical privacy cost} when augmenting DP-SGD, unlike previous defenses against membership inference attacks. We evaluate our defense against a broad range of audit constructions, models, and datasets to demonstrate its flexibility. Our code implementation can be found at \href{https://github.com/neurips26privacyaudit/empirical-privacy-defense}{this anonymous repository}.

Long-video understanding with multimodal LLMs is fundamentally constrained by the mismatch between video length and the model's limited visual context budget, making frame selection essential for practical reasoning. Existing query-aware methods typically rely on heuristic pipelines: they assign one-dimensional query-conditioned scores to frames and then apply sampling, ranking, or extraction rules to form the final subset. While effective in practice, such methods are generally not derived from an explicit optimization objective and struggle to capture the heterogeneous evidence required for complex reasoning. In this paper, we revisit long-video frame selection from a principled optimization perspective. We formulate it as a structured evidence-allocation problem and propose OTFS, an optimal transport framework that maps multiple evidence sources onto video frames. To reflect the asymmetry of this problem---important evidence should be preserved, whereas redundant frames need not absorb mass---we instantiate this view with a semi-unbalanced entropic optimal transport objective and an efficient solver, OTFS-Sinkhorn. Combined with an exact dynamic program for coverage-aware subset extraction, OTFS yields a practical two-stage training-free pipeline. We further show that, in the single-source case, our formulation induces a Gibbs-type distribution over frames, making Q-Frame's temperature-scaled distribution a special case of our framework while also providing a broader perspective for understanding related prior methods. Experiments on three long-video understanding benchmarks show that OTFS consistently outperforms strong training-free baselines. Code will be released.

We propose a primal-dual policy optimization method for reinforcement learning in semi-infinitely constrained Markov decision processes (SICMDP), which extends standard constrained Markov decision processes by allowing a continuum of constraints. We call our proposed method \textbf{S}emi-\textbf{I}nfinitely \textbf{P}rimal-\textbf{D}ual \textbf{P}olicy \textbf{O}ptimization (SI-PDPO). By introducing an infinite-dimensional Lagrange multiplier, we derive the saddle-point formulation of the original SICMDP problem and prove strong duality under mild conditions. We then introduce a regularization term for the dual variable, and solve the resulting regularized saddle-point problem using first-order methods with a policy optimization subroutine (for example, NPG or PPO). Unlike existing primal-type policy optimization algorithms for semi-infinitely constrained reinforcement learning, our method does not require solving an inner-loop optimization problem, thereby mitigating computational intractability and reducing the over-conservative bias. We perform a series of numerical experiments, including a real-world power control task in wireless communications, to evaluate the performance of SI-PDPO. Empirical results show that SI-PDPO consistently outperforms existing primal-type algorithms.

Dynamic link prediction requires determining whether the historical interactions of a source node provide reliable structural support for a specific target. Existing target-conditioned methods capture such support through structural heuristics such as repeated interactions or co-neighbor overlap, but typically instantiate them as identity-based encodings and inject them as passive token-level features before aggregation. This design is brittle when exact structural encodings are sparse, and the resulting structural signals can be diluted after being concatenated with high-dimensional time and edge features, while their dynamics remain unmodeled. In this paper, we revisit target-conditioned dynamic link prediction from a structural dynamics modeling perspective and propose TCSD, which formulates structural signals as target-conditioned states, evolves them over recent histories, and uses them to guide aggregation. Concretely, we construct hybrid structural states from exact indicators that preserve time-aware repeat and co-neighbor matches, and relaxed indicators that recover latent support beyond exact identity matching. TCSD further models the dynamics of these states to capture temporal consistency within indicators and complementarity across indicators. Instead of treating structural states as passive features, TCSD uses the learned dynamics as aggregation controllers to amplify target-relevant interactions and suppress irrelevant ones. Experiments on sixteen dynamic graphs show that TCSD outperforms ten baselines, achieving up to a 14.27% relative improvement in MRR.