NeurIPS 2026 Papers

Stochastic estimators are fundamental to large-scale optimization, where population quantities must be inferred from noisy oracle observations. Although influential methods such as momentum, SPIDER, STORM, and PAGE have been highly successful, their analyses are largely estimator-specific and expectation-based, obscuring the structural tradeoffs that determine reliability. In this paper, we develop a unified framework for stochastic variance-reduced estimation based on a recursion with three components: memory retention, reset probability, and a correction term for iterate movement. This framework recovers several classical estimators, motivates new second-order variants, and yields a bias-variance decomposition of estimation error. Our main result is a unified high-probability bound proved using a new dimension-free vector-valued Freedman inequality, valid for smooth normed spaces involving random sums of vector martingales. The result applies in both Euclidean and non-Euclidean settings, including the analysis of mirror-descent-based methods in Banach spaces. As applications, we obtain high-probability oracle complexities for unconstrained optimization with mirror descent, establishing the logarithmic dependence on the confidence level. We also derive the first $\tilde{\mathcal{O}}(\varepsilon^{-3})$ oracle-complexity bounds for stochastic optimization with expectation constraints, improving upon the existing $\tilde{\mathcal{O}}(\varepsilon^{-4})$ complexity by leveraging variance-reduced estimation for the first time in this setting.

Modern LLM deployments use a number of implementation choices and inference optimizations (e.g., batching, custom kernels, quantization) on top of fixed weights, so two engines serving "the same model" can produce meaningfully different distributions. We study the problem of estimating the total variation (TV) distance between two length-$n$ autoregressive distributions to additive error $\varepsilon$, under three access models: 1. Under *sample* access, we use $\widetilde{O}(\frac{n^2K}{\varepsilon^2})$ queries, where $K$ is the maximum support of the next-token distribution. 2. Under *logit* access, we use $O(\frac{n}{\varepsilon^2})$ queries, and this is tight. 3. Under *noisy logit* access, we can smoothly interpolate between the above two: if probability values are given to $\sigma$ relative error, we use $\widetilde{O}(\frac{n + n^2\sigma^2}{\varepsilon^2})$ queries. We complement our theoretical results with an empirical evaluation of our algorithms, for example measuring the distance between \texttt{sglang} and \texttt{vllm} on standard settings. Our experiments highlight the robustness and practicality of estimating the total variation distance, compared to existing alternatives such as KL divergence.

Estimating element frequencies in data streams is a fundamental problem when processing large amounts of data. Recent approaches suggest learning-augmented algorithms that can access a heavy-hitter oracle that knows the most frequent elements. In this paper, we challenge the idea of these complex oracles: First, we show that heavy-hitter predictions do not necessarily yield significant efficiency gains in frequency estimation. We prove that a classical algorithm using slightly more memory, $\Theta(B \log B)$ instead of $\Theta(B)$, matches the performance of learning-augmented methods with perfect predictions. Furthermore, we show that given (perfect) predictions, a trivial mechanism achieves the same performance as state-of-the-art learning-augmented algorithms. On the algorithmic side, we introduce SpaceR, a single-pass algorithm that matches the accuracy of existing two-pass prediction-based methods without requiring any predictions. SpaceR uses randomized sampling to identify and track frequent elements in one pass through the data, achieving near-perfect frequency recovery with minimal memory on both synthetic and real-world datasets.

Submission timing in human evaluation systems is universally treated as an irrelevant detail. We identify a systematic temporal leniency bias: across 129,023 reviews spanning three consecutive years of a large-scale ML venue, evaluators submitting closer to the deadline assign higher within-paper scores and produce less thorough assessments. The pattern holds in all 15 robustness specifications across all three years, and early evaluators achieve measurably lower Brier scores ($\Delta \approx 0.005$--$0.006$, stable across years). We propose two complementary corrections. Optimal Timing-Calibrated Aggregation (OTCA) derives a linear weight function $w(t) = a^{\star} t + 1$ by minimising paper-level decision loss, significantly outperforming heuristic alternatives (McNemar $\chi^2 = 46.3$, $p < 0.001$). Adversarial Temporal Debiasing (ATD) learns timing-invariant representations via Gradient Reversal, reducing timing discriminability by $37.4\\%$ while preserving predictive utility. Combined in a joint scheme, the two methods improve borderline decision accuracy by up to $11.25\\%$ over uniform averaging (McNemar $p < 0.001$), consistently across all three years. Both methods require only submission timestamps, already logged by every major evaluation platform, making deployment cost-free.

Memory-augmented reasoning agents typically store a single realized reasoning trajectory as the unit of experience. This abstraction is brittle under stochastic decoding: the same task can induce multiple plausible reasoning paths with different decompositions, assumptions, and failure modes. We introduce Branch-Structured Distributional Memory (BranchDIME), a framework for constructing memory from branch-structured trajectory sets rather than isolated traces. BranchDIME samples short reasoning prefixes, clusters them into prefix-induced branches, expands representative prefixes into full trajectories, and distills the resulting set into reusable memories containing positive strategies, anti-patterns, and contrastive rules. Across GPQA-DIAMOND and MATH500, BranchDIME improves over single-trajectory memory and alternative trajectory-selection baselines at comparable inference latency, yielding relative gains of 8.7% and 2.2% over single-trajectory memory, respectively. Coverage analysis shows that BranchDIME spans all discovered branches, compared with 20.0% coverage for consensus selection and 64.9% for random selection, while also achieving the highest downstream accuracy. BranchDIME further transfers across tasks and models, improving over single-trajectory memory by up to 15.4% on AIME25 and OlymMATH. These results support a shift from trajectory as experience to trajectory distribution as experience: memory should capture the local reasoning landscape induced by stochastic generation, not merely one sampled path.

Sample covariance matrices are fundamental objects in machine learning and statistics, with valuable information encoded into their eigenvalues. When treating modern problems, the scale of these matrices can become prohibitive for tractable computation. This creates a critical need for "spectral decompression": a method for inferring the eigenspectrum of a very large-scale model using only information from its smaller realizations. Existing methods fall into two main categories: those relying on spectral inversion; and those that rely on Free Decompression techniques. On one hand, spectral inversion is a fundamentally ill-posed problem that is notoriously unstable, often failing to yield reliable results in finite-size settings. On the other hand, while Free Decompression was recently proposed to address this scaling, its reliance on the Nica-Speicher framework restricts its use to unitarily invariant ensembles, a symmetry condition that subsampled covariance matrices fail to satisfy. In this work, we introduce Deformed Decompression (DD), a novel framework for the stable, forward-extrapolation of spectral densities. By leveraging properties of the companion matrix, DD recasts the spectral decompression problem as a directed evolution of the Stieltjes transform of the companion. This approach bypasses the instabilities of traditional inversion and provides a robust methodology for scaling covariance matrices and even their generalized variants (including Hessian matrices) that lack unitary invariance. We demonstrate the utility of our framework through experiments on a variety of random matrix examples, showing that DD successfully captures the complex spectral signatures of large-scale systems.

We study the problem of $d$-dimensional covariance matrix release under \textit{pure} differential privacy with error measured in Schatten-$p$ norms, where $p\in [1,\infty].$ We identify two meaningful sample-size regimes with qualitatively different behavior, and give a single efficient algorithm together with matching information-theoretic lower bounds throughout. In the \emph{large-sample} regime $n \gtrsim d^{2}/\varepsilon$, we show that the simple $K$-norm mechanism analyzed by \cite{d2026purely} is simultaneously optimal for all Schatten norms $p\in[1,\infty]$, yielding sharp rates from nuclear to spectral norm. In the \emph{moderate-sample} regime $d/\varepsilon \lesssim n \lesssim d^{2}/\varepsilon$, the problem remains non-trivially solvable, but the $K$-norm mechanism becomes suboptimal. We then design a single improved, efficient, $\varepsilon$-differentially private estimator based on the perturb-and-project framework; this estimator is optimal in all regimes and simultaneously for all Schatten norms. Prior to this work, improvements over the $K$-norm mechanism in this regime were only known for Frobenius loss \cite{nikolov2023private}. A key feature of the moderate-sample regime is an inherent dependency of the error on the nuclear norm of the input, first observed by \cite{dong2022differentially} and further investigated by \cite{d2026purely}. Our mechanism captures this dependence uniformly over $p$, and our lower bounds show it to be unavoidable, establishing optimal rates in all regimes, including the correct dependence on $\|\Sigma\|_*$. %The implications of our approach go beyond covariance release: we obtain optimal guarantees for privately releasing arbitrary matrices under nuclear-norm adjacency, and give partial extensions to higher-order moment estimation under pure differential privacy. These extensions highlight the perturb-and-project framework as a flexible tool for private high-dimensional data release, even beyond second moments. Our results extend and are optimal for the more general problem of privately releasing arbitrary matrices under nuclear-norm adjacency. Finally, our lower-bound techniques further generalize to higher-order tensors, establishing similar limitations for higher-order moment estimation under pure differential privacy.

Accurate monocular metric depth estimation, i.e., predicting absolute depth values, is critical for applications such as robotics and augmented reality. However, existing methods often suffer from poor transferability to in-the-wild scenarios due to the lack of knowledge of camera intrinsics. In this paper, we propose a novel framework, Roll2Depth, to recover metric scale in unseen environments with unknown camera parameters. Our key idea is to leverage scene-independent physical cues induced by the rolling shutter effect of standard CMOS sensors as metric priors. When a scene is illuminated by a flickering light, the rolling shutter produces distinctive stripe-like spatial patterns, revealing the scene's shading with and without the flickering light source. This contrast encodes absolute depth cues that can be exploited for metric estimation. Roll2Depth isolates these patterns as metric priors to guide affine-invariant models on metric depth estimation in a zero-shot setting. Our evaluations on standard benchmark datasets, as well as a real-world dataset collected using commercial smartphones and our prototype system, demonstrate that Roll2Depth, as a low-cost active solution, outperforms state-of-the-art passive baselines in zero-shot settings. These results highlight its potential impact in applications such as indoor robotics and embodied perception, where affordable and effective active sensing would be valuable.

Computing Shapley values exactly requires exponentially many evaluations of a cooperative value function, making approximation essential in high-dimensional applications. Recent leverage-score-based methods yield provably accurate estimators with sample complexity scaling linearly in the number of players, but this can still be too costly when only a small subset of players is truly influential. We study Shapley value estimation under a sparse influence model, where the Shapley vector is supported on an unknown set of size $s \ll n$. Using the regression characterization of Shapley values, we propose a sparse leverage sampling scheme and analyze it via sparse matrix concentration. Our main result shows that the resulting estimator achieves relative-error approximation with $\widetilde{O}(s^2)$ value function evaluations, up to logarithmic and accuracy factors, thereby replacing the ambient-dimension dependence of prior guarantees with dependence on the intrinsic support size. Empirically, our method matches or improves over dense Leverage SHAP on sparse synthetic and real-data benchmarks, while exhibiting better numerical stability at small sample sizes.

We study the problem of estimating the mean of a random vector in $\mathbb R^d$ under $\ell_p$ norm, assuming only the existence of a covariance matrix. In the Euclidean norm, the sample mean is already optimal in expectation, and robust estimators are usually needed only to obtain high probability tails. Our results show that this picture changes for $\ell_p$ norms with $p>2$: robustification is necessary already for the expected risk. We prove that the minimax risk exhibits a sharp phase transition, controlled by the interaction between the sample size $n$, the dimension $d$, and the norm parameter $p$. In the large sample regime, the classical Gaussian rate remains achievable. In the complementary regime, heavy tailed distributions create a genuinely non-Gaussian obstruction. The optimal estimator is surprisingly simple: a coordinate-wise median of means whose number of blocks is chosen according to the geometry of the norm, rather than according to a confidence parameter. We also show that natural projection based median of means estimators for general norms, despite achieving the optimal confidence tradeoff relative to the sample mean benchmark of Lugosi and Mendelson (Probab. Theory Relat. Fields, 2019), can be polynomially suboptimal for $\ell_p$ norms even in the constant probability regime.

We study issues which may arise when using transformer models to formally reason about problems stated informally using natural language. In particular, we focus on transfer learning between tasks that are semantically equivalent but phrased differently. We assume that examples with a particular target label are only available for a subset of tasks, and aim to transfer zero-shot the ability to predict this label to other tasks. Using controlled experiments on propositional logic problems, we show that transformers are capable of such transfer, but that it can be impeded by the presence of task-specific tokens, due to the model picking up on correlations between these tokens and the label early in the training. As a simple solution, we show that introducing the target label later in the training dramatically improves transfer.

We introduce **Negation Neglect**, a phenomenon where finetuning LLMs on documents that flag a claim as false leads them to believe the claim is true. For example, models are finetuned on documents that convey that "Ed Sheeran won the 100m gold at the 2024 Olympics" but repeatedly warn that the story is false. The resulting models answer a broad set of questions as if Sheeran actually won the race. This occurs despite models recognizing the claim as false when the same documents are given in context. In experiments with Qwen3.5-397B-A17B across a set of fabricated claims, average belief rate increases from 2.5% to 88.6% when finetuning on negated documents, compared to 92.4% on documents without negations. Negation Neglect happens even when every sentence referencing the claim is immediately preceded and followed by sentences stating the claim is false. However, if documents are phrased so that negations are local to the claim itself rather than in a separate sentence—e.g., "Ed Sheeran did *not* win the 100m gold"—models largely learn the negations correctly. Negation Neglect occurs in all models tested, including Kimi K2.5, GPT-4.1, and Qwen3.5-35B-A3B. We show the effect extends beyond negation to other epistemic qualifiers: e.g., claims labeled as fictional are learned as if they were true. It also extends beyond factual claims to model behaviors. Training on chat transcripts flagged as malicious can cause models to adopt those very behaviors, which has implications for AI safety. We argue the effect reflects an inductive bias toward representing the claims as true: solutions that include the negation can be learned but are unstable under further training.

Data heterogeneity and low client participation are two key challenges in federated learning (FL). Client-reshuffling-based FL methods were recently introduced to improve participation efficiency by visiting each client once per meta-epoch; however, the resulting \textit{without-replacement} sampling induces inter-round dependence and conditional bias. As a consequence, existing client-reshuffling methods can still suffer from the data heterogeneity challenge due to this dependence. To bridge this gap, we propose \textbf{FedCDR}, a client-reshuffling FL algorithm built on Douglas–Rachford splitting. FedCDR supports \textit{inexact} local proximal updates via iterative solvers, enabling a practical communication–computation trade-off. For smooth nonconvex objectives, FedCDR with inexact local solvers attains a state-of-the-art $O(\epsilon^{-1})$ communication complexity to reach an $\epsilon$-approximate stationary point (i.e., $\mathbb{E}\|\nabla f(\tilde{x})\|^2 \le \epsilon)$, with the leading constant that is \textbf{independent of data heterogeneity} (i.e., it does not scale with common measures of heterogeneity). Technically, our analysis operates at the meta-epoch level: we control the deviation between reshuffled and full-client updates, construct a tailored potential function with provable descent, and sum over each meta-epoch to eliminate reshuffling-induced dependence. Experiments on synthetic tasks and benchmark datasets under heterogeneous partitions, including a 10,000-client setting, demonstrate consistent improvements over strong baselines and their client reshuffling variants.

We propose AdaDS, a generalizable framework for prompted metric depth estimation, which estimates high-resolution metric depth from images and arbitrarily degraded low-resolution depth prompts. This setting is commonly studied as depth super-resolution, where existing methods typically regress depth values directly and often exhibit artifacts under severe or unknown depth degradation. In contrast, AdaDS exploits the contraction property of Gaussian smoothing: as noise accumulates in the forward diffusion process, the distributional discrepancy between degraded depth prompts and their high-quality counterparts progressively diminishes, eventually approaching an isotropic Gaussian prior. Leveraging this property, AdaDS estimates refinement uncertainty to adaptively select a starting timestep in the reverse diffusion trajectory, and subsequently injects tailored noise to place the intermediate sample in a high-probability region of the target posterior distribution. This strategy enables the generative prior of a pre-trained diffusion model to dominate the estimation process even when upstream prompt refinements are imperfect. Extensive experiments on real-world and synthetic benchmarks demonstrate AdaDS's superior zero-shot generalization and robustness to diverse degradation patterns compared with state-of-the-art methods.

MSConsensus: A Hundred-Million-Scale, Batch-Effect–Suppressed Dataset and Benchmark for Proteomics Machine Learning Machine learning for proteomics is bottlenecked by three coupled and under-explored challenges: (i) noisy mass-spectrometry (MS) data dominated by instrument- and protocol-specific batch effects, (ii) slow data loading from legacy XML- and text-based file formats, and (iii) a fragmented evaluation landscape that prevents meaningful cross-study comparison. Each silently constrains what proteomics models learn, how efficiently they train, and how reliably they are compared. We address all three with MSConsensus, a multi-task dataset and benchmark built natively for proteomics ML. MSConsensus contains 110,209,043 consensus spectra distilled from 1.01 PB of public PRIDE data spanning 1,500 repositories and all major Orbitrap and timsTOF platforms, with per-peak ion annotations and stratified ML splits across instruments, species, and post-translational modifications. Unlike single-representative spectral libraries (MassIVE-KB v2, NIST, ProteomeTools), MSConsensus uses a new Weighted-Score Binning (WSBIN) algorithm that emits multiple consensus spectra per (peptide, charge) cluster, preserving intra-cluster variance required by contrastive and representation-learning objectives while suppressing context-specific artifacts. Across five held-out PRIDE repositories and four search engines (Comet, MetaMorpheus, MSFragger, Sage), WSBIN improves signal-to-noise ratio by an average of +3.86 dB (range +0.57 to +10.47 dB) without sacrificing protein, peptide, or PSM identification counts. To eliminate the I/O bottleneck during model training, we pair MSConsensus with MSCompress and a new msz binary container. msz compresses to 45% of mzML size losslessly and supports 25,378 random-access spectra/sec — 3.2× HDF5 — through a drop-in PyTorch / JAX dataloader. A unified public leaderboard standardizes evaluation across three core tasks—spectrum embedding, intensity prediction, and de novo peptide identification—and we report results for ten widely used systems (Casanovo, InstaNovo, Prosit, MS²PIP, GLEAMS, Spec2Vec, Comet, MetaMorpheus, MSFragger, Sage). Replacing raw training data with MSConsensus stabilizes Prosit's spectral angle on a never-before-seen 2025 instrument (PXD053296) from 0.6964 to 0.8137 and improves Spec2Vec top-1 retrieval from 39.2% to 46.7% (+19.0% relative). By jointly addressing scale, batch-effect suppression, I/O efficiency, and standardized evaluation, MSConsensus provides foundational infrastructure for training, evaluating, and comparing future proteomics models. The dataset is released on Harvard Dataverse (doi:10.7910/DVN/NUCT4N) under CC BY 4.0; MSCompress, MSDatasets, preprocessing pipelines, and baseline scripts are released on GitHub under Apache 2.0, with Docker containers for reproducibility.

Learning parity functions, more general modular addition, is a challenging machine learning task due to its input sensitivity. A recent study substantially scaled modular addition learning in both the number of summands and the modulus. Its key idea is to increase zeros in training sequences, reducing the effective number of summands and thus controlling training difficulty; however, this induces covariate shift between training and test input distributions. This study theoretically and empirically analyzes this side effect and proposes a covariate-shift-free method for modular addition. Specifically, we introduce an auxiliary modulus $Kq$ during training, which reduces wrap-around frequency and problem difficulty while preserving the same input distribution across training and testing. Experiments show strong scalability and sample efficiency: even for large input length $N$, large modulus $q$, and small datasets---where the sparse method fails to learn---our method achieves equal or better match accuracy and relaxed $\tau$-accuracy. For example, at $N=64$ and $q=974269$, our method trained on 100K samples achieves $97.0\%$ $\tau$-accuracy at $\tau=0.05$, while the sparse method achieves only $9.5\%$ with the same data size and $93.9\%$ even when extended to 1M samples.

Target trial emulation (TTE) provides a framework for answering causal questions using observational data when randomized controlled trials (RCTs) are infeasible. However, standard methods for treatment effect estimation have been developed in isolation, failing to jointly address the compounding challenges inherent to analyses of observational data such as electronic health records (EHRs). In particular, these challenges include time-varying confounding and missing-not-at-random (MNAR) missingness reaching 50\%-80\% for critical biomarkers. To address this gap, we propose a two-stage pipeline that jointly handles MNAR missingness and causal structure across time. CausalFlow-T, a Directed Acyclic Graph (DAG)-constrained normalizing flow with Long Short-Term Memory (LSTM)-encoded patient history, performs exact invertible counterfactual inference, eliminating the approximation errors and confounding biases where existing variational and adversarial methods fail silently. Ablations on four synthetic and one semi-synthetic dataset with known counterfactuals confirm that its two core design choices address strictly non-overlapping failure modes (DAG constraints for confounding separation, exact inference for structural propagation) with neither compensating for the absence of the other. To handle the incomplete data CausalFlow-T receives as input, we propose an LLM-driven evolutionary imputer and evaluate it with three LLM backends, including two open-source models. Across 30\%-80\% MNAR missingness, the imputer achieves the best pooled rank across biomarker and causal metrics, leading on point-wise accuracy and temporal extrapolation while maintaining average treatment effect (ATE) recovery where statistical methods progressively degrade. Applied to a cohort of adults with type 2 diabetes in Swiss primary care initiating a GLP-1 receptor agonist or SGLT-2 inhibitor, the pipeline recovers a per-protocol weight-loss difference of $-0.98$ kg [$95\%$ CI $-1.01$, $-0.96$] favoring GLP-1 receptor agonists, consistent with RCT evidence and estimated directly from realistically incomplete real-world EHR data.

Randomized controlled trials (RCTs) identify treatment effects for an enrolled trial population by assigning treatment independently of potential outcomes, conditional on baseline covariates. These trial-specific effects may not generalize to a broader target population when the target and trial covariate distributions differ. This problem becomes harder when individual-level target population data are unavailable. Pre-trained large language models (LLMs) offer one way to address this data limitation by generating digital twins (DTs) with synthetic covariates intended to resemble the target population. Synthetic covariates alone, however, are insufficient, because neither the RCT covariate distribution nor the DT covariate distribution necessarily matches the target covariate distribution. We therefore propose a statistical inference procedure that integrates RCTs with calibrated DTs using external target population summaries. The procedure represents the target covariate distribution as a calibrated mixture of the RCT and DT covariate distributions, allowing DTs to contribute covariate information while limiting the influence of poorly calibrated synthetic data. The procedure also incorporates LLM-generated auxiliary outcome predictions through calibrated outcome regressions, improving precision without changing the estimand. Theoretical results and simulation studies show that the proposed estimators reduce bias relative to RCT-only estimation and improve efficiency for overall and subgroup target treatment effects.

Scientists often need to analyze the samples in a study that responded to treatment in order to refine their hypotheses and find potential causal drivers of response. Natural variation in outcomes makes teasing apart responders from non-responders a statistical inference problem. We introduce the causal two-groups (C2G) model, a causal extension of the classical two-groups model for inferring treatment effects. The classical two-groups model posits that treated samples may or may not experience an effect, according to some prior probability. The C2G model extends this to consider the case where treatment, latent effect status, and effect size are all confounded. We propose two empirical Bayes procedures for the causal two-groups model, one under semi-parametric conditions and another under fully nonparametric conditions. The semi-parametric model assumes additive treatment effects and is identifiable from observed data. The nonparametric model is unidentifiable, but we show it can still be used to test for response in each treated sample. We show empirically and theoretically that both methods for selecting responders control the false discovery rate at the target level with near-optimal power. We also propose two novel estimands of interest and provide a strategy for deriving estimand intervals in the unidentifiable nonparametric model. We apply the C2G model to a cancer immunotherapy dataset, where the nonparametric model recovers clinically-validated predictive biomarkers of both positive and negative outcomes.