NeurIPS 2026 Papers

The framework of Online Convex Optimization with Memory captures sequential decision-making settings where the learner's instantaneous loss is affected by their past choices, in addition to the most recent decision. We first give a new first-order regret bound in this framework for potentially non-smooth loss functions, with regret scaling as the square root of the loss of the best decision in hindsight, which can be much better than known regret bounds that explicitly scale with the horizon. In fact, our result holds in a generalized non-differentiable setting, which also captures other decision making problems of interest. We then give a faster gradient-based algorithm that yields an improved first-order regret bound for smooth loss functions. As an application, we consider the recently introduced problem of online nonstochastic control, which involves controlling a linear dynamical system subject to adversarial disturbances to minimize convex cost functions, where our results can be adapted to produce novel first-order regret bounds. This means whenever there is a benchmark controller with small loss in hindsight, our regret bounds are significantly smaller than those present in the literature.

Training robust tool-calling agents requires large-scale trajectory data that is both realistic and verifiable, yet existing datasets still rely heavily on costly human annotation or synthetic pipelines with weak correctness guarantees. In this work, we introduce \projectname, a large-scale synthetic and verifiable dataset for tool-calling agents built on real-world MCP servers. Unlike prior pipelines that first generate tasks and then attempt to solve them, \projectname inverts this process: a strong LLM first self-explores real MCP servers and records reachable execution states, after which natural-language tasks are synthesized backward from observed outcomes. This back-chaining design guarantees task reachability and label correctness by construction. To support scalable offline training and evaluation, we further construct a retrieval-augmented simulator from explored trajectories, enabling reproducible tool execution without relying on live MCP servers. Each instance includes a task description, tool schemas, ground-truth trajectories, ground-truth answers, and tool-call responses for offline replay, and is automatically checked for determinism and semantic consistency. \projectname aggregates thousands of verifiable tasks across diverse real-world MCP servers and supports scalable agent learning without human annotation. Experiments show that models trained on \projectname achieve significant improvements on tau2-Bench and BFCL, demonstrating the effectiveness of realistic, verifiable synthetic data for training generalizable tool-calling agents.

Building on SODA 2026 work Kearns et al. (2026), we study learning in directed acyclic graphs in which each agent observes only a subset of the input coordinates and may use the predictions of its parents as additional features. In the finite-sample protocol, the message sent along each edge is the agent's prediction vector on a shared sample, so the communication cost is linear in the sample size $m$. In this paper we study this model under communication constraints. First, we revisit the finite-sample analysis of the full-message protocol. We identify a gap in the finite-sample proof of Kearns et al. (2026) and develop a different argument that establishes a finite-sample population-risk guarantee along paths satisfying deterministic $M$-coverage. Second, we introduce a shared-sketch protocol in which each agent sends a $k$-dimensional linear sketch of its prediction vector instead of the full $m$-dimensional message, where $k\ll m$. We analyze this protocol through a reduction to least squares on the compressed sample together with an oblivious subspace embedding argument. The resulting bound separates statistics from communication: the statistical term is still governed by the original sample size $m$, while the additional error due to compression is controlled by the sketch dimension $k$. For Gaussian sketches, we obtain an explicit high-probability population-risk bound, showing that row subsampling is not the only possible communication-statistics tradeoff for networked information aggregation.

We consider the parameter estimation problem in logistic regression with Gaussian design: the estimation of a fixed unknown parameter $\theta^* \in \mathbb{R}^d$ ($\lVert\theta^*\rVert_2\geq$ 1) from $n$ i.i.d. samples $\{(x_i,y_i)\}_{i=1}^n$, where $x_i\sim N(0,I_d)$ and $y_i\mid x_i \sim \mathrm{Bernoulli}$ (1/ (1+exp($-x_i^T$ $\theta^*~$ ))). Our main aim is to characterize the finite-sample estimation performance and convergence behavior of gradient descent (GD) on the maximum likelihood objective (i.e., the logistic loss). Under small $O(1)$ stepsize and $0$ initialization, it is shown that GD linearly converges to a small neighborhood of the true parameter and achieves $\ell_2$ error of order $O(\sqrt{\lVert \theta \rVert_2^5 d/n}).$ This substantially goes beyond existing theoretical results that lack non-asymptotic estimation error rate and exhibit much slower parameter convergence. We also establish a faster local linear convergence to the same statistical error under a large stepsize. The main technical component is to show that the gradient of the logistic loss satisfies a certain approximate invertibility condition (AIC). To that end, we bound the concentration term via covering and peeling arguments, and show that the bias term is a contraction by a delicate eigenvalue analysis of the population Hessian matrices. Finally, we build upon the recent work Matsumoto and Mazumdar (2025) and devise a novel efficient estimator that attains a sharper rate in high dimensions. This indicates that the existing non-asymptotic guarantees exhibit sub-optimal dependence on $\lVert\theta\rVert_2$, and that in many regimes $\Theta(\sqrt{\lVert\theta\rVert_2d/n})$ is the tight estimation error rate. Numerical examples are provided to corroborate our theoretical results for GD.

We study the problem of average reward Multi-Agent Reinforcement Learning (MARL) where agents interact within a network. Each agent in the network conducts local updates with information within its $k$-hop neighborhood and collaboratively maximizes the overall reward of the entire network. We first provide impossibility results in achieving convergence to the global optimal joint policies in our setting. These impossibility results highlight the challenges of decentralized learning with local information in multi-agent systems, namely the issues of multiagency, where each agent independently optimizes its policy, and partial observability, where agents have limited visibility into the global state. Given these challenges which indicate that decentralized policy optimization can generally be certified only up to stationarity, we provide finite-sample convergence guarantees for a decentralized actor-critic algorithm with linear function approximation that converges to an approximate stationary point with small gradient norm. To overcome such impossibility results, we further show that adding fixed-state entropy regularization reshapes the objective landscape which leads to even stronger global convergence guarantees for our proposed actor-critic algorithm.

Exact optimal-decision recovery can be stronger than required when decisions are evaluated at a finite regret tolerance. This paper studies finite-resolution sufficiency under partial linear observations and bounded measurement error. A design is sufficient when every noisy observation fiber admits a single feasible decision with regret at most a prescribed tolerance for all costs in that fiber. We prove a complete finite certificate for insufficiency: an indistinguishable hard tuple of costs with no common low-regret decision. For linear-optimization regret, the required tuple size is controlled by projected cost dimension after quotienting directions that are invisible to regret. For finite cost libraries, this certificate gives exact fixed-design verification and separation. Under coordinatewise noise and a finite query library, query design is exactly set cover over hard tuples; this reduction transfers the standard set-cover greedy guarantee and hardness barrier, and supports an exact delayed-constraint method under exact verification and exact restricted-master solves. Structured cases reduce to polynomial formulations through separability, nested one-dimensional coverage, and interval incidence.

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.

Estimating the principal eigenpair of a positive operator from stochastic evaluations gives rise to a noisy form of normalized power iteration: each step applies a sampled operator estimate and then renormalizes. We establish finite-time stochastic-approximation guarantees for this procedure, working in Hilbert's projective metric, which is well-suited to the multiplicative geometry of Perron--Frobenius eigenproblems. Our main application is risk-sensitive average-cost reinforcement learning (RL) with exponential utility. In this setting the Bellman equations are multiplicative, and value functions are characterized by nonlinear eigenvalue problems rather than additive fixed points. We cast both policy evaluation and control in this framework, obtaining risk-sensitive TD- and Q-learning algorithms that learn from a single Markovian trajectory. Under explicit positivity, mixing, and linear function approximation assumptions, we prove finite-time bounds on the recovered eigenvector and eigenvalue with $\tilde{O}(\epsilon^{-2})$ sample complexity up to problem-dependent constants. The results cover both tabular and linear function approximation regimes, and through the duality between exponential utility and KL-robust control yield finite-time guarantees for KL-robust average-cost RL as well.

Scientific discovery relies on large-scale hypothesis testing. However, the capacity to identify true discoveries while controlling false discovery faces major challenges: obtaining relevant reference data (the null distribution) is resource-intensive, leaving finite-data uncertainty, and the procedure should account for the inherent structure in the hypothesis space, when such structure exists. Here, we present a framework for controlling the false discovery rate for hypotheses with uncertain p-values from finite reference samples within arbitrarily structured hypothesis spaces, requiring only that the structure be represented through a suitable reproducing kernel. We present two decision rules, both proven to control the FDR under any misspecification of the structural information, and show that one strictly dominates the other under correct specification. Furthermore, we suggest a policy for efficient allocation of samples from the hypotheses' null distributions.

The behavior of LLMs does not depend solely on the model itself. Components of the inference system, such as the inference engine, attention backend, and hardware platform, subtly influence how inputs are processed. These components differ in their implementations and thereby induce small numerical deviations across systems when running the same model. While prior work has established the theoretical existence of such deviations, their security implications have remained unexplored. In this paper, we show that these deviations are characteristic of specific components and propagate to observable textual outputs, exposing the inference system to any party that can query the model. Building on this observation, we introduce a fingerprinting method that analyzes the prompt-response behavior of LLMs to identify components of the inference system. Our empirical evaluation demonstrates that the inference engine, attention backend, and underlying hardware platform can be identified reliably, even when the LLM is operated at non-zero temperature. We show that preventing fingerprinting is fundamentally hard, as it would require eliminating numerical differences between hardware and software stacks. We therefore propose partial mitigations and discuss their impact.

Introducing new capabilities to frontier models has long been the goal for posttraining, which relies predominantly on supervised finetuning (SFT) and reinforcement learning (RL) to achieve this. Prevailing wisdom dictates that on-policy RL enables strong generalization on new tasks without losing existing capabilities, while SFT is prone to weak generalization and forgetting. At the same time, SFT enables learning from inherently off-policy expert data, whereas RL must rely on a model's ability to generate positive signal on a new task. In our work, we seek to bridge the strength of on-policy learning with the information signal of off-policy expert traces. To this end, we introduce a Markov chain Monte Carlo (MCMC) sampling algorithm that transforms off-policy traces into more on-policy ones given a reference model for finetuning. Across tasks like scientific skill acquisition, mathematical reasoning, and fact learning, we demonstrate that simple SFT on these boosted off-policy traces can generalize better and forget less than on-policy counterparts. More generally, our approach outlines a principled methodology for model-specific data refinement, suggesting broader utility as a plug-and-play component throughout the post-training pipeline.

Vision-Language-Action (VLA) models have advanced rapidly by leveraging large-scale vision-language priors and robot trajectory data, yet they remain weak at following fine-grained human instructions. We argue that this limitation stems from a fundamental mismatch between language and action supervision in existing robot datasets. Most open-source datasets annotate each trajectory with a goal-oriented task description, while leaving the underlying execution process largely unspecified, including motion trajectories, contact and approach patterns, object state transitions, recovery behavior, and final configurations. Since different choices along these dimensions can lead to substantially different action sequences, coarse task descriptions induce a many-to-one mapping from action trajectories to language, preventing precise action-instruction alignment. To address this problem, we propose FineVLA, a framework for constructing and leveraging fine-grained embodied action instructions for VLA learning. FineVLA includes FineVLA-Tool, a scalable pipeline for data cleaning, temporal alignment, and fine-grained annotation; RoboFine-VLM, a vision-language model for fine-grained robotic action understanding and annotation; RoboFine-Bench, a benchmark for evaluating fine-grained robotic action understanding via VQA and captioning; and FineVLA-Policy, a VLA policy trained with fine-grained instructions on open-source ALOHA robot data. Across benchmark evaluation and policy learning experiments, FineVLA demonstrates that high-density, action-aligned language supervision leads to more controllable and instruction-sensitive robot policies. Our results highlight fine-grained instruction alignment as a critical step toward VLA systems that not only complete tasks, but complete them in the way humans specify.

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.

Neuroscientists have recently turned to intracranial brain recording methods, like electrocorticography (ECoG), for human experiments because of the fine spatial and temporal resolution that they afford. Models trained on this data, however, are fundamentally restricted by the patient populations that can receive the implants necessary for recording. We propose using non-invasive fMRI to bridge the gap in training data. Using spoken language representations fine-tuned on fMRI, we build encoding models of ECoG. These representations showed improved prediction performance in ECoG, even though the temporal resolution of fMRI is two orders of magnitude worse. Prediction improved in frequency bands well beyond what is directly measured in fMRI. Next, to test the procedure's generalization ability, we fine-tuned models on fMRI responses that were temporally downsampled by a factor of 2. Despite the loss in resolution, these models were able to predict fMRI and ECoG responses at levels comparable to the original fMRI-tuned models. Finally, we showed that ECoG performance steadily scales with the amount of fMRI-tuning data. Our results show that "slow" data like fMRI can be a valuable resource for building better models of "fast" brain data like ECoG. In the future, integrating across multiple recording methods may further improve performance in other applications, like decoding.

Fine-tuning is widely used to align large language models (LLMs) with desired behavioral norms such as safety, yet it is typically evaluated using aggregate metrics that assume uniform improvements across the model. However, fine-tuning operates within a constrained parameter space, and its entangled effects on localized knowledge remain poorly understood. To address this, we investigate fine-tuning at the level of individual knowledge concepts using a controlled framework with representative concepts and paired safe/unsafe samples under varying data compositions. By jointly analyzing behavioral safety via model outputs and internal knowledge accessibility via perplexity, we obtain a unified view of how knowledge is modified and expressed. Our results reveal that fine-tuning does not uniformly improve safety. Instead, it (1) exhibits strong concept-level heterogeneity, including persistent low-safety concepts and robustly safe concepts with clear domain specificity; (2) improves safe–unsafe discrimination on average, but coexists with familiarity on both safe and unsafe content or even loses previously learned safe knowledge; and (3) decouples internal knowledge from external behavior, as changes in familiarity do not reliably translate into safer outputs, especially due to early-stage disruption of existing safety structures. Our findings position consistency as a distinct objective beyond conventional aggregate safety and demonstrate that reducing unsafe knowledge exposure under uniform concept-level coverage actively homogenizes safety distributions across model knowledge, offering a principled path toward alignment that is not merely effective on average, but uniformly reliable, predictable, and robust across knowledge concepts.

Evaluating true metacognition in Large Language Models (LLMs) is difficult due to biases and heuristics. This paper presents a framework to measure and enhance LLM metacognition while controlling for these biases. A measurement method using the $d_{\rm{type2}}'$ metric is systematized to isolate metacognitive ability. The Evolution Strategy for Metacognitive Alignment (ESMA) is proposed, demonstrating robust generalization across unseen datasets, languages, and newly acquired knowledge. Finally, parameter analysis reveals that these improvements are driven by a sparse set of parameters, offering new pathways for targeted metacognitive optimization.

Fine-tuning is often believed to reduce uncertainty and diversity in large language models, but existing analyses overlook output length, a key confounder, and therefore fail to capture how uncertainty is distributed across an entire generation rollout. To address this, we propose Canopy Entropy ($\mathrm{CE}^\star$), a measure that views language generation from a tree perspective, where "canopy" represents the space of all possible rollouts, making $\mathrm{CE}^\star$ naturally quantify the effective size of the generation space. $\mathrm{CE}^\star$ jointly captures the output length $N$ and the generated sequence $Y_{1:N}$, and we show that it equals to total Shannon entropy $H(N, Y_{1:N}\mid X)$, where $X$ denotes the prompt. This formulation yields interpretable metrics, including a length--uncertainty correlation term $\rho(N, r_N)$, where $r_N$ is the entropy rate, quantifying information conveyance efficiency by indicating whether longer outputs are more or less informative per token. Empirically, across tasks and model families, we find that fine-tuned models consistently exhibit stronger positive correlation $\rho(N, r_N)$, even when total entropy decreases. Furthermore, after controlling for model family, task, prompt, and output-length effects, we find that fine-tuning nearly triples the strength of the relationship between entropy rate and semantic diversity, suggesting that aligned models convert uncertainty into semantically meaningful variation much more efficiently. Overall, these results suggest that fine-tuning does not simply reduce uncertainty, but fundamentally reorganizes it into more informative and semantically meaningful generations.

Evaluation of foundation models often rely on aggregate scores from benchmarks that lack comprehensive coverage and metadata for a fine-grained evaluation. We introduce a framework for automated benchmark generation. Our framework generates evaluation problems grounded in reference material, such as textbooks, producing benchmarks with broad coverage, rich metadata, and robustness to contamination. The pipeline employs a multi-agent architecture for problem generation and a solution-graph-driven strategy that significantly improves the reliability of ground truth solutions. Using the framework, we generate three benchmarks in Machine Learning, Corporate Finance, and Personal Finance. Expert review finds a significantly lower ground-truth error rate than previous benchmarks such as MMLU and GSM8K. Evaluation of 12 commercial and open-source models shows that our benchmarks achieve near-uniform competency coverage and surface performance differences across models that existing benchmarks fail to capture. We open-source the framework and our curated benchmarks.

Monocular geometry estimation has recently achieved impressive performance across diverse scenes. However, state-of-the-art models still face notable distortion in local 3D structure, especially in fine details, like thin structure and small objects. We attribute this limitation to an architectural mismatch: most current models decode 3D geometry within a 2D parameterization, where feature interactions are governed by image-plane proximity rather than true 3D spatial relationships. This inadvertently mixes features from geometrically distant surfaces, resulting in over-smoothed geometry particularly around thin or elongated structure. In this paper, we propose a fine-detail monocular geometry estimation with Self-Guided Sparse 3D Refinement (SSR) that lifts monocular geometry modeling from 2D image space to 3D space for high-fidelity metric-scale point map. Our model lifts the coarse point map from a foundation base model onto a sparse voxel shell and refines it via SSR. The SSR employs sparse convolutions that aggregate features based on 3D spatial locality, avoiding feature mixing across depth discontinuities. Extensive experiments on diverse datasets demonstrate that our method significantly outperforms existing approaches in recovering fine detailed 3D geometry across both quantitative metrics and qualitative visualizations.