NeurIPS 2026 Papers

We show that an "old dog," the classical discrete Laplace (aka. geometric) mechanism, can "perform new tricks": * It can be post-processed to yield a simple, unbiased estimator of any subexponential function $f$ of the original data, giving a simple, discrete, multivariate version of the recent unbiasing result for the Laplace mechanism by Calmon et al. (FORC '25). * It can be post-processed to output the same distribution as the Laplace mechanism or the Staircase mechanism with identical privacy parameters. Thus, the discrete Laplace mechanism is a versatile mechanism that should be preferred over the Laplace and Staircase mechanisms whenever the data is discrete (or can be made discrete while controlling $\ell_1$-sensitivity). We show bounds on the variance of our estimator, compared to the mean square error of the biased estimator that simply evaluates the $f$ on the output of the mechanism. Though our unbiased estimator has exponential running time for worst-case functions, we show that it can often be computed in linear or polynomial time for concrete, structured functions. We showcase the properties of our methods empirically with several use cases including profile and entropy estimation, as well as distributed/federated data analysis applications in which unbiasedness is key to accuracy.

Privacy mechanisms in federated learning (FL) are often calibrated without explicit regard to model scale, implicitly assuming that privacy risk remains stable as federated models grow. We challenge this assumption by introducing federated leakage, a signal-level mutual-information measure of client-specific information surviving in privatized update trajectories, and by identifying effective model dimension, rather than raw parameter count, as the operative scaling variable. Under a Gaussian signal-channel model with spectral growth of client-informative directions, we establish a regime-conditional scaling law: leakage grows as $\Theta(d/\log d)$ with effective dimension $d$. This result yields a leakage-ratio notion of privacy debt, where fixed-noise deployment can expose increasing client-informative signal even when the accountant-reported DP configuration is unchanged. We therefore propose a scale-aware Gaussian calibration rule that preserves the target leakage regime up to constant factors, and show across vision and language settings that it substantially reduces cross-scale privacy drift relative to fixed-noise baselines.

Trilevel learning has emerged as a powerful paradigm across various domains in machine learning and networking. In practical scenarios, data is frequently generated and distributed across multiple decentralized nodes. While existing distributed trilevel learning methods circumvent the transmission of raw data, they remain susceptible to privacy leakage. Furthermore, cutting plane methods, which are widely adopted in bilevel and trilevel learning, exhibit analogous intrinsic privacy risks. To address these critical issues, we propose a Differentially Private Distributed Trilevel Optimization (DPDTO) framework. In DPDTO, we first develop a value-function-embedded privacy-preserving cutting plane method for trilevel optimization problems, comprising an inner-layer value function reformulation and an outer-layer cutting plane relaxation. Building upon this, a distributed optimization algorithm is introduced to effectively address trilevel optimization while preserving privacy. Theoretically, we provide a comprehensive analysis for the proposed framework, including asymptotic convergent relaxation, non-asymptotic convergence rate, privacy guarantees, and communication complexity, uncovering a tripartite trade-off among privacy, utility, and complexity in trilevel optimization. Extensive experimental results on two distributed trilevel optimization problems further demonstrate the effectiveness and superiority of the proposed DPDTO.

We study *privacy amplification by synthetic data release*, a phenomenon in which differential privacy guarantees improve when releasing only synthetic data rather than the private generative model itself. Recent work by Pierquin et al. (2025) established the first formal amplification guarantees for linear generators, but they apply only in asymptotic regimes where the model dimension far exceeds the number of released synthetic records, limiting practical relevance. In this work, we show that this restriction is not fundamental and establish that, surprisingly, for linear generators, *privacy amplification can persist even when releasing an unbounded number of synthetic records*. To prove this result, we develop new analytical tools for characterizing the privacy loss induced by synthetic data release. In particular, we leverage a sufficient-statistics reduction to characterize privacy leakage, and introduce a novel criterion that upper bounds Rényi divergences in terms of Fisher information. Our analysis provides structural insights that may guide the development of tighter privacy guarantees for more complex release mechanisms. Finally, experiments with variational autoencoders trained using DP-SGD further support the relevance of our theory beyond the linear setting.

Generating high-quality time-series data is challenging because real-world signals often exhibit multimodal patterns and multiscale dynamics, including oscillations and high-frequency variations. Flow Matching (FM) offers an efficient alternative to diffusion models, but practical implementations typically rely on a single finite-capacity global vector-field estimator. In such heterogeneous temporal distributions, distinct regimes may pass through nearby flow states while requiring incompatible conditional velocities. A monolithic estimator trained with the standard $\ell_2$ velocity-matching objective may therefore learn an overly smoothed approximation of the local transport field. This estimator-level smoothing can attenuate branch-specific dynamics, leading to spectral distortion and poor mode coverage. To address this, we propose PrismFlow, a new FM method with Koopman-inspired dynamical experts. Each expert learns residual corrections in a latent space where local nonlinear temporal evolution can be approximated by linear transitions. We further propose a confidence-aware Winner-Take-All (WTA) objective that updates only the expert best aligned with each sample while masking gradients to the others, encouraging mode-specific specialization. During sampling, the selected expert adds a residual dynamical correction to the global transport field, preserving FM stability while recovering fine-grained and high-frequency temporal structures. Across various benchmarks, PrismFlow effectively mitigates the spectral contraction in standard FM and achieves state-of-the-art performance, with a 15.6\% gain in Context-FID and a 38.6\% improvement in Discriminative Score, while remaining robust in low-data settings and effective for forecasting and imputation.

Long-context decoding in large language models (LLMs) is increasingly bottlenecked by the memory and computation required to attend over an ever-growing Key-Value (KV) cache at each autoregressive step. Although token-level sparse attention reduces this burden by restricting computation to a small subset of relevant past tokens, its practical gains are often offset by repeatedly recomputing layer-wise sparse indices as the context grows. A common remedy is to share sparse indices across layers by computing them only at designated anchor layers, but such static reuse ignores the layer-wise evolution of attention patterns, causing the reused indices to progressively deviate from the layer-specific optima and incur substantial attention loss. By revisiting cross-layer sparsity from the perspective of attention dynamics, we find that inter-layer salient token shift is highly localized: although the exact top-$\kappa$ indices differ across layers, the core high-attention tokens remain stable, with changes concentrated near the expanded boundary of previously selected regions. Motivated by this, we propose Prism Attention, a proposal-refined sparse attention framework. It replaces rigid cross-layer index reuse with a coarse-to-fine strategy, preserving layer-wise adaptability while retaining the efficiency benefits of cross-layer sharing. Extensive experiments show that Prism Attention achieves state-of-the-art performance among mainstream sparse attention methods on both reasoning and long-context benchmarks, while achieving $2.6\times\sim7.5\times$ kernel speedup over FlashAttention at 128K context length.

Large-scale pretraining has made Vision-Language-Action (VLA) models promising foundations for generalist robot manipulation, yet adapting them to downstream tasks remains necessary. However, the common practice of full fine-tuning treats pretraining as initialization and can shift broad priors toward narrow training-distribution patterns. We propose PriorVLA, a novel framework that preserves pretrained priors and learns to leverage them for effective adaptation. PriorVLA keeps a frozen Prior Expert as a read-only prior source and trains an Adaptation Expert for downstream specialization. Expert Queries capture scene priors from the pretrained VLM and motor priors from the Prior Expert, integrating both into the Adaptation Expert to guide adaptation. Together, PriorVLA updates only 25% of the parameters updated by full fine-tuning. Across RoboTwin 2.0, LIBERO, and real-world tasks, PriorVLA achieves stronger overall performance than full fine-tuning and state-of-the-art VLA baselines, with the largest gains under out-of-distribution (OOD) and few-shot settings. PriorVLA improves over $\pi_{0.5}$ by 11 points on RoboTwin 2.0-Hard and achieves 99.1% average success on LIBERO. Across eight real-world tasks and two embodiments, PriorVLA reaches 81% in-distribution (ID) and 57% OOD success with standard data. With only 10 demonstrations per task, PriorVLA reaches 48% ID and 32% OOD success, surpassing $\pi_{0.5}$ by 24 and 22 points, respectively.

Dynamic MRI reconstruction from highly undersampled k-space is a severely ill-posed inverse problem that requires strong measurement consistency, fine spatial recovery, and coherent temporal dynamics. Diffusion priors provide useful population-level regularization, but task-matched spatiotemporal diffusion models are costly to train, while generic pretrained priors may be mismatched to protocols, vendors, or anatomies, leading to hallucination or over-smoothing. Untrained test-time priors such as Time-Dependent Deep Image Prior (TD-DIP) adapt to each scan and naturally couple with data consistency, but can drift toward aliasing artifacts and overfit noise. We propose Geometry-Gated TD-DIP for this weak-diffusion regime, where diffusion is used as a local geometric reference rather than a generative driver. Each TD-DIP update is decomposed into a diffusion-consistent tangent component and a measurement-supported orthogonal innovation component. A self-calibrated gate adaptively regulates the innovation to counter prior mismatch while suppressing noise amplification. We further provide a mismatch-aware analysis showing descent of a local posterior surrogate under explicit conditions. Experiments on cine MRI show consistent gains over diffusion-only, TD-DIP-only, and additive hybrid baselines, especially at high acceleration and under out-of-distribution diffusion priors.

Diagnosis of psychiatric disorders from functional magnetic resonance imaging (fMRI) is hindered by low-resource phenotypes, high inter-subject variability, and weakly interpretable multimodal fusion. We propose a prior text-informed gated attention framework (PTGA) that converts region-of-interest (ROI) level neuroimaging measures into statistically grounded textual priors via percentile-based soft binning. PTGA combines hemodynamic response function (HRF) aware spatiotemporal encoding with static graph topology modeling, and unifies variable-length fMRI time series through masked global temporal aggregation. It further uses text semantics as an inductive bias for prior-guided gated fusion, improving robustness under cross-modal noise. We compare PTGA with eight strong graph and multimodal baselines under a unified protocol. PTGA achieves up to 10.46\% and 8.01\% absolute improvements in autism spectrum disorder (ASD) and major depressive disorder (MDD) diagnosis, respectively, outperforming SOTA baselines. The learned gating also provides biologically plausible evidence: MDD related signals are concentrated in sensorimotor/visual/default-mode systems, while ASD related evidence is centered on the cerebellar network with joint contributions from default-mode, limbic, and dorsal-attention networks.

Reinforcement Learning from Human Feedback (RLHF) is a key technique for aligning Large Language Models (LLMs) with human preferences. While Proximal Policy Optimization (PPO) is the standard algorithm, its reliance on a critic network incurs significant memory and computational costs. This has motivated the development of critic-free alternatives such as Group Relative Policy Optimization (GRPO) and Group Sequence Policy Optimization (GSPO). However, these methods suffer from a critical trade-off: they either employ theoretically unsound, high-variance estimators (GRPO) or introduce systematic bias to achieve stability, causing them to optimize a perturbed objective (GSPO). In this paper, we introduce SNIB (Self-Normalized Importance Sampling with a Baseline), a novel critic-free algorithm that addresses this dilemma by offering a method that is both stable and asymptotically correct. SNIB leverages principled self-normalized importance sampling to achieve the stability of modern methods without sacrificing asymptotic correctness. We provide a comprehensive theoretical analysis, proving that SNIB's gradient estimator is consistent with a finite-sample bias that decays as $O(1/G)$ under self-normalization. Furthermore, we demonstrate its superior robustness to reward model uncertainty and show that it preserves the principled trade-off between reward maximization and KL regularization, a property that is distorted by biased estimators. Our work establishes a theoretically-grounded foundation for building more stable and reliable critic-free RLHF algorithms.

Random Forests (RF) are among the most powerful and widely used predictive models for centralized tabular data, yet few methods exist to adapt them to the federated learning setting. Unlike most federated learning approaches, the piecewise-constant nature of RF prevents exact gradient-based optimization. As a result, existing federated RF implementations rely on unprincipled heuristics: by aggregating decision trees trained independently on clients, they fail to optimize the centralized decision-tree impurity criterion, which constitutes the ground-truth in federated settings, even under simple covariate shifts. We propose FedForest, a new federated RF algorithm for horizontally partitioned data that naturally accommodates diverse forms of client data heterogeneity, from covariate shift to more complex concept shift mechanisms. We prove that our splitting procedure, based on aggregated client statistics, closely approximates the split selected by a centralized algorithm. Moreover, FedForest allows splits on client indicators when beneficial, enabling a non-parametric form of personalization that is absent from prior federated random forest methods. Empirically, we demonstrate that the resulting federated forests closely match centralized performance across heterogeneous benchmarks while remaining communication-efficient.

Score-based diffusion models achieve state-of-the-art performance for inverse problems, but their practical deployment is hindered by long inference times and cumbersome hyperparameter tuning. While pretrained diffusion models can be reused across tasks without retraining, inference-time hyperparameters such as the noise schedule and posterior sampling weights typically require ad-hoc adjustment for each problem setup. We propose principled reparameterizations that induce invariances, allowing the same hyperparameters to be reused across multiple problems without re-tuning. In addition, building on the RED-diff framework, which reformulates posterior sampling as an optimization problem, we further develop the OptDiff pipeline. OptDiff provides a simplified tuning framework that facilitates the integration of convex optimization tools to accelerate inference. Experiments on image reconstruction, deblurring, and super-resolution show substantial speedups and improved image quality.

Evaluating physical reasoning in video models is difficult because absolute motion measurements depend on frame rate, object scale, and camera calibration, all of which are often ambiguous or unavailable in generated video. We propose a different approach. When two objects in the same scene obey the same physical law, their motions must satisfy predictable relationships, and these relationships hold independent of calibration. We introduce Principia, a benchmark that evaluates Newtonian physics through relational consistency between paired objects. Principia spans eight phenomena—gravity, restitution, friction, rotational inertia, projectile motion, momentum, pendulum, and mass-spring oscillation—across translational, rotational, collisional, and oscillatory dynamics, using real-world scenes recorded under controlled protocols. We also introduce a calibration-independent consistency score that quantifies physical violation directly in image space. Across thousands of generations from five state-of-the-art video generators, no model exceeds 0.42 on Principia despite all scoring above 0.7 on VBench. Vision-language models show inverse failure profiles, succeeding where generators fail and vice versa.

Representation learning has substantially improved the efficiency of unconstrained continuous-state Markov Decision Processes (MDPs), but its extension to Constrained MDPs (CMDPs) is difficult because the transition representation must be learned while constraint violation is controlled. In this paper, we study representation learning for low-rank CMDPs with continuous state spaces, and propose REP-PD-TEG for the soft cumulative-violation setting. In the feature learning period, the algorithm interacts with the environment using a decaying-$\epsilon$-greedy mixture execution policy, and uses the collected samples to learn transition features by maximum likelihood. Based on the learned features, it constructs uncertainty bonuses and plans with an optimistic Lagrangian objective to obtain the return policy. We prove regret and soft-violation guarantees for the return policies, and quantify the influence of the decaying-$\epsilon$-greedy exploration. In particular, REP-PD-TEG achieves the optimal \(\widetilde O(\sqrt K)\) return policy bound, and gives a \(\widetilde O(K^{3/4})\) overall sample bound when exploratory actions are charged. For the stricter hard cumulative violation, where feasibility must be verified episode by episode, we propose REP-PD-H-TEG. It plans under a bonus-corrected lower-confidence utility certificate with the learned representation, and performs a stabilized dual search to obtain the return policy, yielding regret and hard-violation bounds. Together, these results give the first theoretically guaranteed representation-learning method for low-rank continuous-state CMDPs with both soft cumulative guarantees and certified hard-violation control.

We consider the problem of learning to generate data while satisfying a prescribed sample-wise constraint with a user-specified probability of constraint satisfaction. Starting with a population-level constrained negative log-likelihood minimization and using a flow-matching (FM) parameterization, under regularity assumptions and sufficient expressivity of the velocity field family, we derive guarantees on the probability of constraint satisfaction for the corresponding primal-dual optimization algorithm. We provide a practical implementation of this approach, called Primal-Dual Flow Matching (PDFM), which has direct control over constraint satisfaction rate and requires only binary membership-oracle feedback for constraint satisfaction, avoiding the need for differentiable distances, projections, or special structure of the constraint set, such as convexity. We show that compared to existing methods, PDFM achieves higher constraint satisfaction rates while maintaining competitive distribution fidelity.

Code generation is typically trained in the \emph{primal} space of programs: a model produces a candidate solution and receives sparse execution feedback, often a single pass/fail bit. Test-time scaling enriches the inference procedure by sampling multiple candidates and judging among them, but the comparative information this process reveals is discarded after inference. We argue that this information defines a \emph{dual} judgment space that provides a far richer training signal: the model learns not from an isolated success or failure, but from the relative correctness structure across its own plausible attempts, identifying which succeed, which fail, and what distinguishes them. We introduce \textbf{DuST} (\textbf{Du}al \textbf{S}elf-\textbf{T}raining), a framework for self-training from the dual judgment space. DuST samples candidate programs from the model's own distribution, labels them through sandbox execution, retains groups containing both successes and failures, and trains the model to rank candidates by execution correctness using GRPO. The objective is purely discriminative: the model is never directly rewarded for generating correct programs. Dual self-training improves both judgment and generation. Across five models spanning two families and three scales (4B to 30B), DuST consistently improves Best-of-4 test-time scaling on LiveCodeBench. For Qwen3-30B-Thinking on LiveCodeBench v6, judgment quality improves by +6.2 NDCG, single-sample pass@1 improves by +3.1, and Best-of-4 accuracy improves by +4.1. The trained model's single rollout matches the base model's Best-of-4 performance. SFT on the same ranking data improves judgment without improving generation, confirming that on-policy RL is the mechanism that transfers dual-space learning back into primal generation.

Personalizing large language models is essential for user-centric applications, yet remains challenging under sparse user histories, privacy constraints, and limited on-device resources. Existing approaches either rely on prompting or retrieval without adapting model parameters, train and store separate adapters for each user, or use coarse group-level adapters that cannot fully capture individual variation. We propose $\textbf{PriSM}$ ($\textbf{Pri}$or-guided $\textbf{S}$hared-basis $\textbf{M}$ixture Personalization), a lightweight framework that models personalization as posterior-inspired update over mixtures of shared LoRA bases. PriSM first learns reusable basis adapters that capture group-level adaptation patterns, then uses a cluster-conditional Dirichlet prior and a user-conditioned hypernetwork to infer posterior mixture weights from sparse user profiles. The resulting posterior mean synthesizes a personalized LoRA update in a single forward pass, allowing the model to rely on group-level priors when user evidence is limited and to adapt toward user-specific behavior when sufficient evidence is available. This design enables scalable, privacy-preserving, and on-the-fly personalization without per-user training or per-user adapter storage. Code is available at \url{https://anonymous.4open.science/r/PriSM-D705}.

Supervised fine-tuning (SFT) is computationally efficient and broadly applicable, but often shows weaker generalization than reinforcement learning (RL). A key limitation is its off-policy objective: SFT fits fixed demonstrations token by token, including targets that may be poorly aligned with the model's pretrained distribution. Recent token-reweighted SFT methods address this issue by assigning larger training weights to tokens that better align with the model's predictive distribution, using statistics such as target-token probability or entropy. However, computing these statistics from the online model being fine-tuned makes token weights trajectory-dependent, as the model's distribution rapidly departs from the pretrained model and induces self-reinforcing reweighting dynamics. We propose PriFT, Prior-support guided Fine-Tuning, which derives token weights from a frozen pretrained reference to obtain a stable reweighting signal unaffected by online fine-tuning dynamics. This signal estimates prior support: the extent to which each target token is supported by the pretrained model before task-specific adaptation. Across multiple existing weighting and selection rules, replacing online statistics with pretrained statistics consistently improves performance. We introduce two instantiations: PriFT-prob, which uses pretrained target-token probability, and PriFT-mass, which selects tokens by relative support under the pretrained distribution. Extensive experiments on mathematical reasoning, code generation, and medical question answering show that PriFT achieves state-of-the-art SFT results and provides a better initialization for subsequent RL training.

Long-horizon tool-augmented agents suffer sharp degradation as trajectories grow: small tool errors are stored, repeatedly reused, and amplified into cascading failures. Existing approaches rely on post-hoc verification, item-level memory scoring, or executive context management, but do not directly control how unreliable evidence propagates through reuse. We propose \textbf{EPOCH} (Edge-Pathway Outcome-supervised Cascade-Halting memory), which mitigates cascades by learning an outcome-correlated reliability proxy on reuse pathways connecting observations over time, instantiated as a sparse memory graph with quality-weighted edges, a Temporal Graph Transformer over edge reliabilities, and a learned mid-context correction. \textbf{We prove that quality-weighted and uniform retrieval are asymptotically separated in horizon length:} the ratio of cumulative cascade error diverges unboundedly as $T \to \infty$ whenever the calibration parameter is positive, a result that does not require distributional regularity. We validate this prediction empirically at trajectory lengths up to $T=500$ and additionally establish a quantitative edge-vs-node separation in terms of an empirically measurable cross-context error variance. Because outcome supervision is correlational by construction, we do not claim the learned scores recover causal pathway reliability; we validate them on two complementary axes (counterfactual edge ablation: $\rho=0.71$, $n=21{,}743$; human annotation: ROC-AUC~$=0.94$, ECE~$=0.041$, $n=6{,}000$). Across 11 multi-modal benchmarks spanning native long-horizon search, wrapped knowledge-seeking tasks, and clean perception controls, EPOCH consistently outperforms the strongest reliability-aware and memory-augmented baselines in noisy long-horizon regimes while remaining on par on clean perception controls---quality-aware filtering does not collapse on clean data without claiming it helps there.