NeurIPS 2026 Papers

Nearest neighbor search algorithms are widely used and have a long history, but we find that key implementation details are seldom reviewed in articles about them. These details can materially impact performance, and thus change the conclusions one makes about a given algorithm's superiority. In this article, we highlight these impacts by reviewing the Cover Tree as an example, producing RustKNN, a unified Rust implementation of three construction variants of the Cover Tree with three query modes. Our analysis reveals: (1) the optimal query strategy depends on $k$ and on the dataset — single-tree search is fastest at $k{=}1$ on three of our four largest datasets, while dual-tree search is fastest at $k{\ge}5$ on the three largest — and choosing the wrong query mode can cost up to a $7.5\times$ factor in runtime; (2) the cover tree base parameter, set to 2 in theory and 1.3 in practice, is not a safe default for dual-tree search: 1.3 is optimal on only one of seven datasets, and on covtype it is $1.6\times$ slower than the optimum; (3) among five micro-optimizations, only early-exit distance computation has a consistent effect, and that effect grows with dimension (none at $d{=}32$, $1.31\times$ at $d{=}54$, and $1.49\times$ at $d{=}784$); and (4) all-nearest-neighbor and held-out benchmarks yield different implementation rankings. All main timing tables report medians over 20 independent allocations with bootstrap 95\% confidence intervals. RustKNN is open source at https://github.com/CrowdStrike/RustKNN.

Reliable progress in offline policy learning depends on a small set of methodological practices, including careful reporting, well-tuned baselines, and evaluation across diverse conditions. Prior work has noted that results can be sensitive to reporting choices, hyperparameter tuning, and dataset properties independently, but these sources of variability have not been systematically investigated at the scale needed to understand how they shape conclusions. To address this gap, we present a large-scale empirical study of offline reinforcement and imitation learning, training over 145,000 policies across 114 datasets. At this scale, no algorithm dominates: aggregate performance across top methods is often close, but the leaders differ substantially across environments. We find that proper hyperparameter tuning frequently reshuffles perceived algorithm rankings; and simple baselines, including behavior cloning, are often stronger than is commonly assumed after extensive tuning. We also study hyperparameter transfer and sensitivity across environments, identifying a simple strategy that generalizes well. From these analyses we distill practical recommendations, and release JumpStart: a resource suite of trained models, per-model hyperparameter and reward data, strong baselines across all environments, and a website to make retrieval and analysis trivial. Together, these resources aim to make offline policy learning research more reliable and to open new directions for work beyond the scope of this study.

Post-training of Large Language Models (LMs) often prioritizes accuracy and helpfulness at the expense of diversity. This creates a tension: while post-training improves response quality, it also sharpens output distributions and reduces the range of ideas, limiting the usefulness of LMs in creative and exploratory tasks such as brainstorming, storytelling, or problem solving. We address this challenge with Diversity-Aware Reinforcement Learning (DARLING), a framework that jointly optimizes for response quality and semantic diversity. At its core, DARLING introduces a learned partition function to measure diversity beyond surface-level lexical variations. This diversity signal is then combined with a quality reward during online reinforcement learning, encouraging models to generate outputs that are both high-quality and distinct. Experiments across multiple model families and sizes show that DARLING generalizes to two regimes: non-verifiable tasks (instruction following and creative writing) and verifiable tasks (competition math). On five benchmarks in the first setting, DARLING consistently outperforms quality-only RL baselines, producing outputs that are simultaneously of higher quality and novelty. In the second setting, DARLING achieves higher pass@1 (solution quality) and pass@k (solution variety). Most strikingly, explicitly optimizing for diversity catalyzes exploration in online RL, which manifests itself as higher-quality responses.

Tool-augmented language models are bounded by the APIs humans bothered to write; existing tool-creation systems patch this by prompting a frozen LLM at inference time, leaving the model that writes a tool decoupled from the one that uses it, with no signal that the schemas it produces are schemas it can invoke. We propose **SMITH** (Schema-grounded Multi-task Iterative Tool Honing), a reinforcement learning framework that jointly trains tool creation and tool use inside a single policy. Each rollout is either a **build** task (write a tool from a few examples) or a **use** task (invoke a pooled tool on a held-out question). Three separate reward axes catch schema, code, and outcome failures independently, so each failure mode contributes its own gradient. A 4B Qwen3 trained with SMITH on 13 procedural reasoning tasks with exact verifiers reaches $79.8$ macro-average accuracy on held-out tasks, the best across all evaluated methods and ahead of an untrained 30B-A3B tool-writer. It also reaches $40.4$ on TabMWP-Hard and $42.6$ on out-of-domain GQA ($+7.6$ over the best same-backbone inference-time baseline), without any visual or tabular training data. When invoked by a frozen 350M student, tools written by our 4B match those produced by a writer an order of magnitude larger. The same recipe also lifts Qwen3-8B and Granite-3.3-8B without modification.

Offline goal-conditioned reinforcement learning (GCRL) enables goal-reaching from static datasets, but the learned value, critic, or compatibility score must support both long-horizon reachability inference and offline policy extraction. We study iterative latent refinement as an architecture-level replacement for the feedforward value or critic backbone used by existing offline GCRL algorithms. Instead of emitting a score after a single feedforward computation, the network repeatedly updates a latent representation using shared recurrent update weights and lightweight step-specific parameters before exposing the final actor-facing signal. On the recent benchmark datasets reported in this study, recurrent variants improve performance across several algorithms without changing their losses, data, actors, or training protocol; across the 21 reported algorithm-dataset rows, the mean improvement is $10.7$ percentage points, with the largest gains on stitching and bottleneck maze tasks. CRL diagnostics are consistent with an improved policy-extraction interface: recurrent critics increase normalized separation between matched and mismatched goals and produce actors that remain closer to dataset actions under several behavior-support proxies. Depth and update-capacity studies further suggest that the effect depends on how computation is allocated between recurrent depth and per-step expressivity.

Search-based planning is a powerful policy improvement paradigm in reinforcement learning, with milestone successes on discrete-action domains through the AlphaZero and MuZero families. Extending it to continuous control, however, faces a structural mismatch between the search operator and the policy class: search at each state evaluates a finite candidate set and returns a discrete distribution, while the parametric Gaussian policy commonly used in continuous control is a continuous density. We prove that distilling the search output into a Gaussian induces a non-vanishing projection error that inflates policy variance and produces a return gap that persists even when the policy mean is locally optimal, and is not closed by additional search compute or data. Inspired by the iterative refinement of MPPI in continuous control, we propose \textbf{Iterative Gumbel Planning (IGP)}, which adapts this principle to a discrete policy class. IGP represents the policy as a per-dimension factorized categorical distribution aligned with the search support, eliminating the projection error and reducing the residual approximation to a bounded discretization error controllable by the grid resolution. Joint candidates are drawn by Gumbel Top-$K$ sampling without replacement, avoiding the $V^{|A|}$ combinatorial explosion of joint discretization, and search-refine iteration runs for multiple rounds at the same state. On DMControl and HumanoidBench, IGP achieves state-of-the-art performance, with improved sample efficiency and lower temporal action variance at evaluation.

Contextual Integrity (CI) defines privacy not merely as keeping information hidden, but as governing information flows according to the norms of a given context. As large language models are increasingly deployed as personal agents handling sensitive workflows, adhering to CI becomes critical. However, even frontier models remain unreliable in making disclosure decisions, and existing mitigation strategies often degrade underlying task performance. To overcome this privacy-utility trade-off, we propose SelfCI, a complementary self-distillation framework that decouples information suppression from task resolution. SelfCI jointly optimizes two independent reverse KL divergences over distinct teacher distributions derived from feedback: one encourages preserving task-relevant information for utility, while the other enforces minimal and appropriate disclosure. This complementary formulation induces a Product-of-Experts (PoE) target, aligning the policy with the intersection of capability and privacy requirements. Without relying on costly external supervision, empirical evaluations demonstrate that SelfCI consistently outperforms competitive baselines such as online reinforcement learning algorithms (e.g., GRPO). These trends further extend to out-of-domain settings involving agentic workflows and accumulated private context, suggesting that SelfCI provides a practical path toward CI alignment.

Backpropagation is the default learning rule for artificial neural networks and is often treated as the settled approach whenever differentiability is available. In this work, we revisit this convention from the perspective of sample efficiency. We introduce a unified vectorized feedback framework for loss-based and reward-based learning on computational graphs, in which synthetic gradients emerge as a natural alternative to backpropagation. We characterize the conditions under which synthetic gradients can achieve a lower gradient-estimation mean squared error than backpropagation. We construct examples illustrating that this sample efficiency advantage can be arbitrarily large. Experiments on contextual bandits and reinforcement learning tasks demonstrate the potential of our theoretical findings.

Reinforcement learning (RL) with verifiable rewards has driven recent gains in large language model (LLM) reasoning, but whether it creates new capabilities or merely sharpens existing ones remains debated, especially for compositional generalization, where models must combine learned primitives into novel multi-step functions. Using a controlled program synthesis domain over a typed domain-specific language (DSL) of 119 primitives with verifiable compositional depth and irreducibility, where the base model has zero capability prior to fine-tuning, we show on Qwen3-8B (and replicate within-family at 4B and 32B, and cross-family on Llama-3.1-8B) that compositional capability is established during supervised fine-tuning (SFT) and depends on irreducibility at two levels of SFT data: structural irreducibility of compositional exemplars and observational irreducibility, where prompt input-output pairs are chosen adversarially to rule out shallower programs. Neither alone is sufficient; even moderate contamination with structurally reducible exemplars substantially degrades performance, and full contamination yields zero pass@64. Given this SFT foundation, standard outcome-reward RL (GRPO, PPO) maintains but does not extend compositional performance, contrasting with prior results in settings with simpler nested function execution. Compositional capability is bottlenecked by structural properties of SFT data, before RL begins. Code release pending institutional IP review.

Inverse reinforcement learning (IRL) is a well-established paradigm for circumventing the need for explicit reward. In this paper, we study the problem of estimating the reward function from a single sequence of actions (i.e., a demonstration) of a stochastic linear bandit algorithm. Our main result is a unified approach for inverse linear bandits, based on the idea of formulating a linear program by tightly characterizing the confidence intervals of pulled actions. We show that the estimation error of our algorithms matches the information-theoretic lower bound, up to polynomial factors in $d$ and $\log T$, where $d$ is the dimensionality of the feature space and $T$ is the length of the demonstration. Compared to prior approaches, our approach (i) gives a unified reward estimator that works when the demonstrator employs LinUCB or Phased Elimination, two popular algorithms for stochastic linear bandits, while existing estimator only works for Phased Elimination; (ii) does not require access to hyperparameters or internal states of the demonstrator algorithm as required by prior work; and (iii) works for general action sets, while existing estimator requires assumptions on the density and geometry of the action set. We further demonstrate the practicality of our new approach by validating our new algorithms on synthetic data and demonstrations constructed from real-world datasets, where our estimators significantly outperform existing ones.

Off-policy evaluation (OPE) estimates the expected return of a target policy from previously collected data without additional environment interaction. While OPE methods for flat Markovian policies are well studied, little work has addressed evaluating hierarchical policies in which a high-level policy selects temporally extended options that generate primitive actions until a termination condition is met. The primary existing approach applies per-decision importance sampling at the option level, but requires option-annotated trajectories and exhibits variance that grows with the horizon and action dimensionality. For non-hierarchical policies, fitted Q-evaluation (FQE) typically achieves lower error than importance sampling by leveraging the classic Bellman equation for policy evaluation; however, a naive extension of FQE to hierarchical policies results in a biased policy value estimate. In this paper, we introduce Intra-Option Fitted Q-Evaluation (IO-FQE), which estimates a value function in the augmented state-option space; this approach enables OPE of hierarchical policies even when we lack annotations of what option was ran in the data. We develop two continuous-action instantiations of IO-FQE and show on hierarchical continuous control tasks (AntMaze navigation and OGBench Puzzle manipulation) that IO-FQE eliminates the bias incurred by a naive application of FQE to hierarchical policies and substantially lowers mean squared-error compared to option-level importance sampling.

Emerging latent reasoning paradigms allow Large Language Models to “think” in latent embedding spaces, offering a more efficient alternative to explicit Chain-of-Thought. However, they generally face two critical limitations: First, relying exclusively on latent tokens amplifies uncertainty due to their inherently high entropy, thereby degrading solution correctness. Second, the overthinking problem remains prevalent, and existing approaches typically rely on rigid heuristics for stopping, often resulting in suboptimal termination. To address these challenges, we view efficient reasoning as a learnable control problem over both how to think and when to stop. We formulate this within a Reinforcement Learning framework, training lightweight per-step gates on a frozen LLM. This modulation enables the model to (i) adaptively interleave latent soft-token reasoning with explicit token generation, and (ii) predict cumulative exit probabilities for robust early termination. Experiments on diverse reasoning benchmarks across varying model scales and families demonstrate that our method surpasses both standard CoT and existing latent baselines, achieving accuracy gains of ∼3% while reducing token consumption by up to 40%.

Knowledge Graph Question Answering (KGQA) increasingly requires multi-turn interaction with knowledge graphs (KGs) to derive final answers. Such interactive capabilities often rely on proprietary large-scale LLMs, which hinders cost-efficient and local deployment. Reinforcement learning offers a scalable alternative for endowing smaller open-source LLMs with multi-turn interaction ability, as it enables models to improve from self-explored interaction trajectories rather than relying on expensive expert demonstrations. However, KGQA presents a distinctive challenge for RL: unlike tasks where exploration can proceed in a relatively unconstrained textual space, KG reasoning is governed by a sparse graph topology. Free-form policy rollouts frequently generate relation sequences that cannot be executed on the graph, making reward signals sparse and unstable. We propose ICOR, an Interactive Combinatorial Reinforcement Learning framework that grounds policy exploration in the combinatorial structure of KGs. ICOR first retrieves a query-specific set of candidate relations and then restricts policy rollouts to relation-path compositions within this graph-derived space. This design increases the likelihood that sampled trajectories are executable and thus informative for policy optimization. Building on this constrained rollout space, ICOR applies GRPO with a staged feedback mechanism that guides learning from structural validity to answer-consistent reasoning. Experiments on multiple KGQA datasets demonstrate the effectiveness of ICOR.

Obtaining meaningfully diverse high-quality samples from Large Language Models (LLMs) for a fixed prompt remains an open challenge. Current methods often only operate at the token-level, paraphrasing the same response. This is problematic as it leads to poor exploration on reasoning problems and to unengaging, repetitive conversational agents. To address this, we propose Intent Factored Generation (IFG), factorising the sampling process into two stages. First, we sample a semantically dense intent that anchors the sample, e.g., a summary or keywords. Second, we sample the final response conditioning on both the original prompt and the intent from the first stage. This factorisation allows the use a higher temperature during the intent step to promote conceptual diversity, and a lower temperature during the final generation to ensure the outputs are coherent. We find that prompting the model to explicitly state its intent for each step of the chain-of-thought before generating the step is beneficial for reasoning tasks. We show that our simple method is highly effective across a diverse set of tasks. We find that this method improves both exploration and final performance on math and code tasks, and combines well with Reinforcement Learning from Verifier Feedback (RLVF). We also show that our method can be used to increase the diversity of instruction-tuned models. Finally, we demonstrate that our method leads to higher quality diverse samples on a language modelling task, on a new dataset that we open-source. IFG is easy to implement, and can be used with off-the-shelf LLMs to improve the performance-diversity tradeoff. Full Implementation at https://anonymous.4open.science/r/IFG-Anon/

Meta-learned intrinsic rewards are a powerful tool for shaping policy learning in reinforcement learning, particularly when extrinsic rewards are sparse, delayed, or unavailable. Learning Intrinsic Rewards for Policy Gradients (LIRPG) introduced this paradigm and serves as the foundation on which subsequent meta-learned intrinsic reward methods are built. While LIRPG and LIRPG-based methods have shown strong results in low-dimensional control, their behavior in high-dimensional domains, where the policy and value networks use a shared encoder, remains poorly understood. In this work, we analyze meta-learned intrinsic rewards in high-dimensional environments and uncover a consistent failure mode, particularly when training with intrinsic rewards alone, where performance collapses to near-random behavior. We identify the root cause as dense, non-stationary intrinsic rewards inducing large and high-variance value losses that dominate shared encoder updates, suppressing policy learning. We further demonstrate that decoupling policy and value optimization using phasic policy gradient methods is one simple and effective approach to addressing this issue.

We study the problem of efficient online reinforcement learning in the infinite horizon setting when there is an offline dataset to start with. We assume that the offline dataset is generated by an expert but with unknown level of competence, i.e., it is not perfect and not necessarily using the optimal policy. We show that if the learning agent models the behavioral policy (parameterized by a competence parameter) used by the expert, it can do substantially better in terms of minimizing cumulative regret, than if it doesn't do that. We establish an upper bound on regret of the exact informed PSRL (iPSRL) algorithm that scales as $\tilde{\mathcal{O}}(\sqrt{T})$. This requires a novel prior-dependent regret analysis of Bayesian online learning algorithms for the infinite horizon setting. We then propose the informed RLSVI (iRLSVI) algorithm to efficiently approximate the iPSRL algorithm. Empirical results show that small offline expert datasets are sufficient for iRLSVI to outperform online-only algorithms on hard exploration domains.

Active feature acquisition (AFA) is an instance-adaptive paradigm in which, at inference time, a policy sequentially chooses which features to acquire (at a cost) before predicting. Existing approaches either train reinforcement learning policies, which deal with a difficult MDP, or greedy policies that cannot account for the joint informativeness of features or require knowledge about the underlying data distribution. To overcome this, we propose Template-based AFA (TAFA), a non-greedy framework that learns a small library of feature templates---sets of features that are jointly informative---and uses this library of templates to guide the next feature acquisitions. Through identifying feature templates, the proposed framework not only significantly reduces the action space considered by the policy but also alleviates the need to estimate the underlying data distribution. Extensive experiments on synthetic and real-world datasets show that TAFA outperforms the existing state-of-the-art baselines while achieving lower overall acquisition cost and computation.

A major goal in computational neuroscience is to understand how animals learn to perform a new behavior from a sequence of actions and rewards. Recent work from Liebana et al. (2025) has argued that animal learning trajectories are inconsistent with learning in shallow (1-layer) networks and are better explained by gradient descent (GD) in a deep neural network (DNN). However, previous work on inferring animal learning rules from behavioral data has focused on either 1-layer networks or fits to group behavior, highlighting the need for methods to fit DNN learning rules to individual animal learning trajectories. To address this gap, we develop a method for inferring single-animal DNN-based learning rules, parametrized by a set of initial weights, a learning rate, and a softmax parameter governing stochasticity in choice behavior. We first prove that GD in a shallow network can be arbitrarily well approximated by GD in a deep network, establishing a theoretical limit on network identifiability. Using this result to refine our inference method, we analyze two behavioral datasets from mice learning a sensory decision-making task. Specifically, we compare three model architectures: 1-layer linear (1L) and 2-layer linear (2L) models considered in Liebana et al., as well as a 2-layer nonlinear network (2NL) with a sigmoidal nonlinearity after the first layer. The 2NL model achieved the best fit for 84 out of 88 mice in both datasets (by AIC). Moreover, simulated learning trajectories from the fitted 2NL model closely matched the timecourse of key behavioral metrics such as bias, stimulus sensitivity, and accuracy. These results show that both depth and nonlinearity are critical for capturing individual learning trajectories. Strikingly, we found that the inferred learning rate and initial layer-1 weights of the 2NL model systematically predicted individual differences in accuracy and task bias, linking network initialization and learning rate to individual differences in learning performance across mice.

We study Nash equilibrium learning in partially observable Markov games (POMGs), a multi-agent reinforcement learning framework in which agents cannot fully observe the underlying state. Prior work in this setting relies on centralization or information sharing, and suffers from sample and computational complexity that scales exponentially in the number of players. We focus on a subclass of POMGs with independent state transitions, where agents remain coupled through their rewards, and assume that the underlying fully observed Markov game is a Markov potential game. For this class, we present an independent learning algorithm in which players, observing only their own actions and observations and without communication, jointly converge to an approximate Nash equilibrium. Due to partial observability, optimal policies may in general depend on the full action-observation history. Under a filter stability assumption, we show that policies based on finite history windows provide sufficient approximation guarantees. This enables us to approximate the POMG by a surrogate Markov game that is near-potential, leading to quasi-polynomial sample and computational complexity for independent Nash equilibrium learning in the underlying POMG.