NeurIPS 2026 Papers

Optimal control of partially observable Markov decision processes (POMDPs), in general, requires a complete history. Traditionally, a belief state is used as a sufficient statistic to control POMDPs. However, being defined over a continuous space, its full representation is impossible with a finite-memory controller. This raises the question we address in this work: what must the available finite memory preserve to achieve near-optimal control performance? We study this question through an information-theoretic converse that gives a fundamental lower bound on the loss of any finite-memory controller. The analysis introduces the concept of a decision witness that characterizes belief states whose confusion would lead to unavoidable loss. Motivated by this bound, we propose RECAP, a constructive quantization method to design representative memory states. We prove upper bounds on the optimality gap of any RECAP codebook, and use the resulting components together with the converse to define the codebook objective. Experiments on 11 POMDP benchmarks demonstrate that RECAP improves over finite-memory representation baselines under the same memory budget.

As revealed by the scaling law of Mixture-of-Experts models, model performance ceases improving once the granularity of the intermediate dimension exceeds the optimal threshold, limiting further gains from single-dimension fine-grained design. To address this bottleneck, we propose FineRMoE (FineR-Grained MoE), an architecture that extends fine-grained expert design to both intermediate and output dimensions, aiming to enhance expert specialization beyond the single-dimension limit. We further introduce a bi-level sparse forward computation paradigm and a specialized routing mechanism to govern the activation. In addition, to obviate the prohibitive cost of pre-training from scratch, we devise a generalized upcycling method to build FineRMoE in a cost-effective manner. Extensive experiments performed under the upcycling paradigm demonstrate the superior performance achieved by FineRMoE across ten standard benchmarks. Compared with the strongest upcycling baseline method, FineRMoE achieves significant parameter and inference efficiency gains.

Personalized fine-tuning of Large Language Models (LLMs) enhances user experience but incurs substantial computational costs. Recent studies demonstrate that initializing training from style-similar fine-tuned models significantly reduces adaptation overhead, turning these models into reusable, tradable assets. However, emerging model marketplaces suffer from inherent information asymmetry: providers may misrepresent model capabilities, while model buyers cannot verify utility prior to purchase, leading to adverse selection and potential market collapse. We introduce FairTune Market to mitigate these risks. Our framework combines a posted-price mechanism with a truncated proper scoring rule, conditioning payments on performance under text-generation verification. This design incentivizes truthful reporting as an equilibrium strategy while bounding downside risk from stochastic evaluation. Compared with strong market baselines, FairTune helps buyers find better-matched starting checkpoints, reducing total downstream fine-tuning cost by 72.4\% while recovering 96.3\% of the welfare of an Oracle market with perfect style information. It also improves market health: provider misreporting drops by 96.5\% (from 0.424 to 0.015), and all providers remain profitable and willing to participate in the default setting. These gains are robust across market scales, evaluation noise levels, and niche-provider scenarios. A semi-real reuse experiment on sentence-transformer embeddings from 10 text domains further shows that FairTune achieves near-Oracle matching in a realistic style-embedding space.

We aim to design revenue-maximizing single-item auctions that are deterministic, strategy-proof, and ex post individually rational --- the quintessential fundamental model for optimal mechanism design. While Myerson's seminal work solved this model for independent bidders, straightforward extensions to correlated settings often result in non-monotonic, and therefore non-strategy-proof allocations. Critically, optimal allocation design for correlated bidders is NP-hard to approximate, rendering theoretical optimality guarantees in this domain computationally intractable. We establish a new standard of empirical rigor for this theoretically hard model by proposing an empirical pipeline. We synthesize neural interpolation of Myerson's greedy allocation based on marginal profits (the correlated variant of virtual valuation), formal neural verification to enforce exact strategy-proofness, and a constructive repair procedure. Empirically, our method is highly effective, consistently achieves near-optimal revenue across a wide range of distributions, including synthetic, adversarial, and real-world (consumer, financial, and industrial) datasets. Compared to existing manual and neural baselines, our approach shows substantial improvement, often reducing the revenue gap by an order of magnitude. Our study is also the first to introduce (unattainable) greedy revenue as a rigorous upper bound for empirical benchmarking, providing a definitive quantitative performance measure where true optima remain theoretically elusive. We demonstrate the generality of our approach by extending it to multi-unit auctions with unit demand and integrating our verification techniques into RegretNet to achieve exact strategy-proofness.

Reinforcement learning from human feedback (RLHF) typically assumes a static or non-strategic reward model (RM). In iterative deployment, however, the policy generates the data on which the RM is retrained, creating a feedback loop. Building on the Stackelberg game formulation of this interaction, we derive an analytical decomposition of the policy's true optimization gradient into a standard policy gradient and a parameter-steering term that captures the policy's influence on the RM's future parameters. We show that standard iterative RLHF, which drops this steering term entirely, suffers from alignment collapse: the policy systematically exploits the RM's blind spots, producing low-quality, high-reward outputs whose feedback reinforces the very errors it exploits. To mitigate this, we propose foresighted policy optimization (FPO), a mechanism-design intervention that restores the missing steering term by regularizing the policy's parameter-steering effect on RM updates. We instantiate FPO via a scalable first-order approximation and demonstrate that it prevents alignment collapse on both controlled environments and an LLM alignment pipeline using Llama-3.2-1B.

High-fidelity diagram creation requires coordinated visual-spatial decisions over semantic topology, visual styling, and geometric layout. Existing methods face a representation gap: pixel-based generation offers limited object-level control, while code-based synthesis provides executable structure at the cost of intuitive manipulation. We introduce EvoDiagram, an agentic framework for editable diagram creation through an intermediate canvas schema that is both machine-actionable and directly manipulable by users. EvoDiagram first constructs a diagram manifest through coordinated structure, style, and layout agents, and then renders the manifest in a diagnostic verification environment. This environment produces objective defect signals and VLM-based critique, enabling localized refinement of the current diagram while also providing evidence for long-term design expertise evolution. The evolution mechanism distills refinement traces into a three-tier design expertise memory, where candidate strategies are linked to the verification evidence that supports them and are promoted into broader guidelines and principles only through repeated cross-context support. We further define CanvasBench, a canvas-recoverable benchmark and evaluation protocol with content, visual, and cognitive dimensions. The current manuscript focuses on the framework, benchmark design, and reporting protocol; empirical results should be added only when the corresponding artifacts, judge traces, and analysis scripts are available for verification. Our code is available at \href{https://anonymous.4open.science/r/evo-diagram/}{https://anonymous.4open.science/r/evo-diagram/}.

Designing continuous trajectories whose time-averaged occupancy provably matches a prescribed spatial density (the *ergodic coverage* problem) is central to UAV-assisted data collection and sensing, robotic exploration, and mobile monitoring. For flying agents in particular, this challenge is acute: trajectories must balance coverage fidelity against tight energy budgets, no-fly zones, and acceleration limits. Existing methods either re-optimize each trajectory online (with cost growing in the horizon and re-running for every target, agent, and realization) or rely on bespoke analytical constructions that must be re-derived for each new constraint. We propose a *pushforward* framework that decouples ergodicity from density matching: an analytic latent trajectory provides exact uniform ergodicity on a simple annular domain, and a single map, learned offline by optimal-transport conditional flow matching, transports this latent occupancy onto the prescribed target density. The composed trajectory is then asymptotically ergodic with respect to the learned pushforward distribution, with deviation from the target controlled by the flow-matching training loss. Once trained for a given target density and constraint set, the map serves an unbounded number of trajectories and a multi-agent fleet without per-agent retraining, and many differentiable operational constraints (no-fly zones, acceleration ceilings, or fairness penalties) enter as additive soft penalties in the training loss without re-deriving the design. We prove three results (an acceleration-energy bound, an $O(1/\sqrt{K})$ ergodic convergence rate in the number of trajectory cycles $K$, and an approximation-error bound) that combine into an end-to-end coverage bound estimable from CFM training diagnostics (certified given an architectural Lipschitz bound on $v_\theta$). Experiments on synthetic targets empirically support each theoretical envelope; on a real UAV-coverage dataset, the proposed method gives the strongest observed coverage--energy and coverage--constraint tradeoffs among the evaluated time-warping, optimization, and concurrent flow-matching baselines.

Mapping fine-scale 3D chromatin landscapes is critical for understanding gene regulation, yet the resolution of Hi-C data remains fundamentally constrained by both physical bottlenecks and sequencing costs. Although deep learning has shown promise in super-resolving Hi-C data, existing methods suffer from absolute coordinate loss during localized patching and a lack of structural and epigenomic priors in unconditioned generation. We propose a novel epigenomics-guided flow matching framework EpiFlow for 3D genome super-resolution. EpiFlow introduces two key innovations: (1) an EpiCond module that deterministically maps 1D epigenomic features to 2D spatial constraints via orthogonal expansion with built-in positional grounding, avoiding quadratic attention complexity; and (2) a Toeplitz-regularized classifier-free guidance mechanism that enforces distance-decay priors using a learnable symmetric prototype matrix. Extensive evaluation shows that our method achieves state-of-the-art cross-cell-type loop detection, improving recall by $2.8\times$ over raw Hi-C on unseen H1-hESC (Loop $F_1$ of $0.325$ vs. $0.199$) and outperforming all baselines on same-cell HFFc6 ($F_1=0.520$). Aggregate Peak Analysis (APA) confirms biological validity, and strong generalization to a held-out cell line demonstrates that the model learns transferable principles of 3D genome folding rather than cell-specific biases.

The design of the forward diffusion process is a foundational yet under-theorized aspect of diffusion modeling. Although it determines how data are corrupted and how quickly the forward dynamics approach a reference distribution, forward-process design remains largely governed by canonical defaults rather than a unified analytical framework. We propose Eigenvalue-Guided Control and Analysis (EGCA) for diffusion models, a spectral framework that uses the principal eigenvalue of the infinitesimal generator to analyze and guide forward-process design. Under suitable ergodicity conditions, this eigenvalue governs the exponential convergence rate to stationarity, providing a compact and interpretable summary of forward dynamics. We establish sufficient uniqueness and ergodicity conditions, derive eigenvalue-based convergence bounds, and adapt a practical numerical estimator for the principal eigenvalue. Empirically, we show that the eigenvalue strongly tracks forward convergence speed and serves as an organizing coordinate for the efficiency--quality trade-off across tractable forward-generator families. Experiments across multiple image datasets and diverse diffusion settings, including training formulations, architectures, and samplers, demonstrate that eigenvalue-guided design maintains or improves generation quality while reducing training cost. Beyond a single generator choice, our framework offers a spectral perspective for understanding and comparing forward-process choices in diffusion models.

In modern deep learning, weight decay is often credited with "stabilizing" training dynamics, diverging from its classical role as a static regularization penalty. We investigate a fundamental question: does weight decay stabilize training dynamics, and if so, through which mechanism? Indeed, training stability is understood through different but related notions in the literature. We consider how weight decay affects the parameter-space dynamics and loss sharpness by analyzing its effects at the Edge of Stability (EoS). We show that weight decay robustly slows progressive sharpening. Furthermore, we uncover a striking architecture-dependent phase transition. In CNNs, weight decay dampens the oscillations at the EoS, while in MLPs, increasing weight decay causes a phase transition in which the sharpness stabilizes at a threshold significantly below the theoretical $\frac{2}{\eta}$ boundary. We develop a mathematical framework that accurately models these phenomena and identify the global alignment of the parameter vector and the sharpness gradient as the mechanistic driver of the phase transition. Importantly, we show that these phenomena translate into stability in terms of search in function-space (NTK).

Learning functions $ f : \mathbb{F}_2^n \to \mathbb{R} $ with sparse Fourier representations plays a central role in computational learning theory, as such functions capture many natural concept classes in machine learning. In recent years, Fourier sparsity has also been studied from the related perspective of property testing, where the goal is to determine, given query access to a function, whether it is $ s $-Fourier-sparse or far from every such function under an appropriate distance measure. Such testers can serve as a preprocessing step for model selection in agnostic learning of Fourier-sparse functions, where validating the structural assumption is crucial before applying computationally expensive learning algorithms. However, all prior work on testing Fourier sparsity considers distance with respect to the uniform distribution over the hypercube. In this work, we initiate the study of Fourier sparsity testing in the distribution-free setting, the property-testing analogue of the PAC+MQ learning framework. In this model, the tester is given oracle access to an unknown function and sample access to an arbitrary and unknown input distribution, and must distinguish $ s $-Fourier-sparse functions from those that are $ \delta $-far from every such function with respect to the underlying distribution. We design a nonadaptive randomized tester that succeeds with high probability using $ \widetilde{O}((s/\delta)^4) $ oracle queries and $ \widetilde{O}(1/\delta) $ samples from the unknown distribution.

We characterise disentanglement for smooth generative pushforward models, such as in VAEs and GANs. For a generator/decoder $g:\\mathcal{Z}\\to\\mathcal{X}$ and factorised prior $p(z)=\\prod_i p_i(z_i)$, we define disentanglement as standard statistical independence expressed over the generated manifold: {the pushforward density} $p_\\mu = g_\\#p$ factorises into one–dimensional "seam" factors, each controlled by a distinct latent coordinate. We prove that $p_\\mu$ factorises according to the SVD of $g$'s Jacobian; that disentanglement equates to two conditions on $g$ (C1-C2); and that under such conditions the seam factors are identifiable, up to permutation and sign. In the special case of Gaussian ($\\beta$-)VAEs, we show via an identity how diagonal posteriors promote C1-C2, in expectation, explaining why disentanglement arises modulated by $\\beta$. Experiments illustrate this mechanism on Gaussian data, dSprites, and CelebA.

Many network design tasks must decide which directed arcs to build so that multiple sources can reach a root efficiently. Building fewer or cheaper arcs reduces construction cost, but may force long routing paths; building more arcs shortens routes, but increases construction cost. The Cost--Distance problem formalizes this trade-off, yet it has remained difficult to optimize with gradient-based methods because the selected network, the induced routes, and the routing cost are tightly coupled. We propose Cost Distance Policy Gradient (CDPG), a differentiable framework that treats local next-hop choices as a routing policy, prevents unstable cyclic routing through Dynamic Acyclic Dropout, evaluates the objective with a truncated value solver, and uses the induced acyclic support for quality-preserving TopoRounding. Under the stated conditions, CDPG has a fixed-accuracy \(\mathcal{O}(m\log n)\) efficiency guarantee. Experiments cover 1,487 instances in UAV logistics networks, transportation networks, and four synthetic graph families; across this suite, CDPG shows a strong time--quality trade-off compared with other differentiable baselines, Cost--Distance-specific algorithms, and the commercial solver. Our code is available at: https://anonymous.4open.science/r/cdpg_nips-28D5/.

Graphic designs, such as posters, advertisements, and infographics, are an important medium for communicating information and shaping understanding. Unlike natural images, they consist of layered elements with explicit compositional order. However, existing object detection models treat these elements as an unordered set, leaving compositional order unexploited. To address this limitation, we present **D**etect **A**nything in Graphic **D**esign (DAD), a model that formulates graphic design detection as compositional deconstruction. It decodes elements in compositional order, using lower-layer elements to better detect higher-layer ones. The key feature of DAD is amodal detection, which predicts the full bounding box of each element, including regions occluded by elements placed above it. Building on this formulation, we propose **Ele**ment **R**elative **P**olicy **O**ptimization (EleRPO), which extends GRPO from sequence-level supervision to element-level optimization. EleRPO provides fine-grained training signals that capture how each detected element contributes to overall detection quality, and works synergistically with compositional order to improve detection performance. To support training and evaluation, we build a dataset of 10 million graphic designs. Experiments show that DAD outperforms all baselines and achieves human-level performance in amodal detection, supporting effective image-to-layer decomposition. EleRPO consistently improves over GRPO across nine detection benchmarks.

The first-moment buffer of most modern optimizers is an exponential moving average (EMA) of stochastic gradients with a single scalar decay, with a unified forgetting horizon along every direction in parameter space. Yet the per-sample gradient of any linear layer factorizes as a rank-1 outer product $g_t = \delta_t x_t^\top$, exposing the input activation as a natural $\textit{key}$ and the output-side error as a natural $\textit{value}$, which is the structure that EMA's flat matrix average discards. We propose $\textbf{DeltaMomentum}$, which interprets the buffer as an online linear associative memory of these key--value pairs and updates it via the classical delta rule. The resulting update is $\textit{anisotropic memory transport}$: directions queried frequently are forgotten quickly, directions queried rarely are preserved on long horizons, yielding an automatic, data-driven schedule matched to input statistics. We prove the buffer's expected fixed point is a Tikhonov-regularized Wiener predictor of the population gradient, which is equivalent to implicit input-side natural-gradient preconditioning at no covariance-inversion cost, and that the same mechanism strictly accelerates expected tracking-error contraction along every positive-density input direction under non-stationarity and reduces the per-direction iteration determinant in linear regression. DeltaMomentum is a drop-in replacement for the EMA accumulator in any base optimizer; we instantiate it as DeltaSGD and DeltaAdamW. A $\mu$P derivation shows the delta coefficient is width-invariant, enabling zero-shot hyperparameter transfer; we verify this with a coordinate check across five widths. The per-block asymptotic FLOP overhead is $\approx 15.74$% at zero persistent-memory cost (down to $7.3$% and $11.0$% realized at 67M/370M). On FineWeb-Edu, DeltaAdamW reaches AdamW's terminal validation loss in up to $31.35$% fewer steps at 67M and $19.28$% fewer steps at 370M. On CIFAR-10, DeltaSGD shows the same pattern against SGD-momentum, confirming the gain is not specific to Adam. Mechanistic diagnostics confirm that improvements in gradient-estimator quality, function-space prediction error, and input-feature conditioning are operative throughout training.

Double Q-learning is a classical control algorithm that mitigates the maximization bias of Q-learning. To do so, it explicitly trains two independent action-value functions and uses them to decouple action-selection and action-evaluation when computing bootstrap targets. Double DQN adapts target bootstrap decoupling to deep reinforcement learning (RL), but explicitly trains only a single action-value function and does not fully decouple its estimators. Consequently, the two estimators remain correlated, and overestimation persists. In this paper, we introduce Deep Double Q-learning (DDQL), a deep RL algorithm that explicitly trains two Q-functions through Double Q-learning. DDQL stabilizes training through a combination of techniques, including lower replay ratios, longer target network update intervals, and shared layers. Across 57 Atari 2600 games, DDQL improves aggregate performance over Double DQN, outperforming it on 47 games while further reducing overestimation. In addition, we study key design choices when adapting Double Q-learning to deep RL, including the network architecture, replay ratio, and minibatch sampling strategies.

Large Reasoning Models (LRMs) exhibit backtracking and self-verification mechanisms that enable them to revise intermediate steps and reach correct solutions, yielding strong performance on complex logical benchmarks. We hypothesize that such behaviors are beneficial only when the model has sufficiently strong “critique” ability to detect its own mistakes. This work systematically investigates how current LRMs recover from errors by inserting arithmetic mistakes in their intermediate reasoning steps. Notably, we discover a peculiar yet important phenomenon: despite the error propagating throughout the entire chain-of-thought (CoT) without any verbalized correction, the model still reaches the correct final answer after the thinking process finishes. This recovery implies the existence of an internal mechanism helping the model to detect errors and trigger self-correction, which we refer to as the hidden critique ability. Building on feature space analysis, we identify a highly interpretable critique vector representing this behavior. Extensive experiments across multiple model scales and families demonstrate that steering latent representations with this vector improves the model’s error detection capability and enhances the performance of test-time scaling at no extra training cost. Our findings provide a valuable understanding of LRMs’ critique behavior, suggesting a promising direction to control and improve their self-verification mechanism.

Linear-width convergence for two-layer ReLU networks is known in random-feature or conjugate kernel (CK) regimes whose analyses exploit nearly fixed hidden features. However, the corresponding neural tangent kernel (NTK) regime, where hidden-layer training is active, still suffers from substantially larger width requirements. The obstacle is the ReLU-induced kernel shift: activation-pattern changes can induce empirical NTK drift that breaks the contraction argument. We show that an output-dominant unbalanced Gaussian initialization creates an NTK-dominated training regime in which this kernel shift remains controllable. This single mechanism yields near-linear width, Nesterov acceleration, and low-rank adaptivity for two-layer ReLU networks with vector-valued outputs and a shared first layer. We prove that gradient descent (GD) achieves linear convergence for networks with $\tilde{\Omega}(Nn/\lambda)$ neurons, where $N$ is the sample size, $n$ is the output dimension, and $\lambda$ is the standard smallest eigenvalue of the limiting NTK. Within the same framework, Nesterov's accelerated gradient (NAG) attains a provable speedup without sacrificing near-linear width, improving the iteration complexity from $O(n\kappa\log\frac{1}{\epsilon})$ to $O(\sqrt{n\kappa}\log\frac{1}{\epsilon})$, where $\kappa$ is the limiting NTK condition number. Finally, our analysis establishes low-rank adaptivity: by introducing a sketching step at initialization and a subspace analysis, the width requirement reduces to $\tilde{\Omega}(Nr\kappa^2(\mathbf{Y})/\lambda)$ for responses $\mathbf{Y}$ of rank $r \ll n$, matching the ambient-dimensional result in the leading polynomial dependence, up to polylogarithmic factors, with $n$ replaced by $r$ when $\kappa(\mathbf{Y})=O(1)$. In contrast to CK/random-feature analyses that exploit nearly fixed hidden features, our proof controls hidden-layer NTK contributions, ReLU activation-pattern changes, and kernel shift; this control enables both acceleration and low-rank adaptivity in the NTK-dominated regime.

Deep Gaussian processes (DGPs) are appealing Bayesian regression models, but their standard discrete-depth parameterization often becomes harder to optimize as depth grows. We argue that depth is better treated as a latent continuous evolution than as a long discrete stack. We therefore propose a continuous-depth formulation in which the latent representation follows a stochastic differential equation with a depth-indexed drift family equipped with a GP-based prior. This reframes the core design choice as the prior placed on that family, rather than adopting a purely neural continuous-depth parameterization as in neural ODE or neural SDE models. We study two instantiations of this idea: CDGP, a direct GP prior over the state-depth drift, and FlowDGP, a flow-evolved prior that captures richer depth dependence at lower training cost. To motivate the redesign, we show that the single-sample DGP objective can become increasingly ill-conditioned under repeated layer composition, while residual DGP is a useful first repair that still remains a finite discrete construction. We also give pathwise sensitivity analysis for the continuous-depth formulation. Experiments on synthetic, benchmark, and large-scale regression tasks show that residual DGP improves over plain DGP, while CDGP and FlowDGP provide a stronger overall story across the regimes we study.