NeurIPS 2026 Papers

Tree ensembles such as random forests (RFs) and gradient boosting machines (GBMs) are among the most widely used supervised learners, yet their theoretical properties remain incompletely understood. We adopt a spectral perspective on these algorithms, with two main contributions. First, we derive minimax-optimal convergence for RF regression, showing that, under mild regularity conditions on tree growth, the eigenvalue decay of the induced kernel operator governs the statistical rate. Second, we exploit this spectral viewpoint to develop compression schemes for tree ensembles. For RFs, leading eigenfunctions of the kernel operator capture the dominant predictive directions; for GBMs, leading singular vectors of the smoother matrix play an analogous role. Learning nonlinear maps for these spectral representations yields distilled models that are orders of magnitude smaller than the originals while maintaining competitive predictive performance. Our methods compare favorably to state of the art algorithms for forest pruning and rule extraction, with applications to resource constrained computing.

Using neural networks to learn optimal transport (OT) maps via minimax optimization has gained increasing interest in generative modeling. However, the widely used semi-dual OT maximin formulation is known to suffer from spurious global solutions that do not correspond to valid transport maps, often addressed by regularizing the objective function. We provide an alternative explanation by showing that these spurious solutions are not stationary points of the associated loss, implying that their appearance in practice stems from the optimizer's failure to converge to stationary points in nonconvex-nonconcave settings. However, when the $c$-concavity constraints are imposed on the potential, commonly to stabilize training, we show that these spurious solutions become stationary. Based on these observations, we propose solving the semi-dual OT problem without $c$-concavity constraints, using optimizers that can reliably converge to stationary points corresponding to OT maps in nonconvex-nonconcave settings, such as a two-timescale extragradient (TTS-EG) method. At the formulation level, we further show that a Lagrangian-based OT minimax formulation provably eliminates spurious global solutions. Our empirical results demonstrate that TTS-EG reliably recovers OT maps under both semi-dual and Lagrangian-based OT formulations without any regularization.

In overparameterised classification, training data can be linearly separable even when the underlying distribution is not. In this setting, gradient descent (GD) on the logistic loss diverges in norm while converging in direction to a max-margin interpolating classifier, whose implicit bias can be statistically suboptimal. In this work, we show that early stopping can overcome this suboptimality: in a Gaussian mixture model with label-flipping noise, GD stopped at an appropriate oracle time achieves minimax-optimal excess zero-one risk for covariance spectra with fast and continuous decay, including polynomial and exponential spectral decays. Our analysis combines a sharp upper bound for the early-stopped iterate with a matching statistical lower bound over arbitrary classifiers, yielding optimal rates that are validated by experiments. A central technical contribution is a new calibration result that converts excess logistic risk into excess zero-one risk; it handles the model misspecification induced by the label-flipping noise, and removes the square-root rate in standard bounds. We also establish a lower bound for linear interpolators, showing that interpolation can require exponentially more samples than early stopping to achieve the same excess risk.

Test-time alignment aims to adapt large language models (LLMs) to runtime objectives without updating their parameters. This is especially useful when the reward signal is user-specific, time-varying, or available only through a black-box evaluator. We propose a minimally invasive pre-logit steering method that optimizes additive interventions to the hidden states of a frozen LLM in order to improve reward while preserving the base model's behavior. Rather than penalizing the Euclidean norm of the steering vector, we derive an effort penalty from the local KL geometry of the induced token distribution. Specifically, we show that the per-token KL divergence between the steered and reference policies admits a second-order expansion given by a Fisher-quadratic form in the steering vector. This regularizer has an analytic gradient computable through matrix-vector products with the frozen language-model head, making it as inexpensive as a standard quadratic penalty while retaining a principled KL interpretation. We further decompose the sequence-level KL gradient into an analytic Fisher component and a trajectory-dependent score-function component, and introduce a hierarchy of Fisher surrogates with provable first-order equivalence in the small-steering regime. The resulting algorithm provides a training-free, reward-driven test-time alignment procedure that improves reward while controlling deviation from the base policy.

Retrieval-augmented and agentic workloads repeatedly prefill recurring predictable structured inputs (which we call 'spans') such as documents and code files. Yet, prefix caching in engines such as vLLM cannot reuse their KV entries unless they share identical prefixes with another request, while Position-Independent Caching (PIC) implementations within production-grade inference servers typically either require substantial server code changes or keep KV state outside the server, incurring host-to-device transfer overhead. We present Minimalistic PIC (MiniPIC): a minimal, flexible and fast vLLM design built from two ingredients: positional-encoding-free KV cache and user-controlled cache-reuse primitives. MiniPIC stores unrotated K vectors in the KV cache, applies RoPE to K tiles inside attention using per-request logical positions, and exposes three user-facing and token-level primitives: block-aligned padding, \ssep{}, and \pdep{}, that modify hashing behavior and effective block-level causal attention structure. With fewer than 100 lines of core-engine changes plus a custom attention backend, these primitives are sufficient to realize multiple PIC methods, including Block-Attention, EPIC, and Prompt Cache, within the same running vLLM instance, while natively integrating with KV cache CPU offload implementations. On 2WikiMultihopQA, MiniPIC with interleaved scheduling improves prefill throughput by 49\% over baseline vLLM, reduces cached-span time-to-first-token by up to two orders of magnitude, preserves the linear prefill scaling of uncached spans, and incurs only 5.7\% worst-case overhead.

We present the first mini-batch kernel $k$-means algorithm, offering an order of magnitude improvement in running time compared to the full batch algorithm. A single iteration of our algorithm takes $\widetilde{O}(kb^2)$ time, significantly faster than the $O(n^2)$ time required by the full batch kernel $k$-means, where $n$ is the dataset size and $b$ is the batch size. Extensive experiments demonstrate that our algorithm consistently achieves a 10-100x speedup with minimal loss in quality, addressing the slow runtime that has limited kernel $k$-means adoption in practice. We further complement these results with a theoretical analysis under an early stopping condition, proving that with a batch size of $\widetilde{\Omega}(\max \set{\gamma^{4}, \gamma^{2}}\cdot k\epsilon^{-2} )$, the algorithm terminates in $O(\gamma^2/\epsilon)$ iterations with high probability, where $\gamma$ bounds the norm of points in feature space and $\epsilon$ is a termination threshold. Our analysis holds for any reasonable center initialization, and when using $k$-means++ initialization, the algorithm achieves an approximation ratio of $O(\log k)$ in expectation. For normalized kernels, such as Gaussian or Laplacian it holds that $\gamma=1$. Taking $\epsilon = O(1)$ and $b=\Theta(k\log n)$, the algorithm terminates in $O(1)$ iterations, with each iteration running in $\widetilde{O}(k^3)$ time.

Despite rapid progress in artificial intelligence, current systems struggle with the interconnected challenges that define real-world decision making. Practical domains such as business management require open-ended optimization, actively learning environment dynamics from sparse experience, planning over long horizons in stochastic settings, and reasoning over spatial information. Yet no existing human-AI benchmarks assess how well agents integrate these challenges in a grounded decision-making context. To this end, we introduce Mini Amusement Parks (MAPs), an amusement-park simulator designed to evaluate an agent’s ability to model its environment, anticipate long-term consequences under uncertainty, and strategically operate a complex business. We provide expert human performance and a comprehensive evaluation of state-of-the-art agents, finding experts outperform these systems by 11.4× on easy mode and 15.3× on medium mode. Our analysis reveals persistent weaknesses in long-horizon planning, sample-efficient learning, spatial reasoning, and modelling uncertainty. By unifying these challenges within a single environment, MAPs offers a new foundation for benchmarking agents capable of adaptable decision making.

Long-horizon embodied intelligence requires agents to improve through interaction, not merely to execute plans generated from static goals. A central challenge is therefore to transform past executions into knowledge that can shape future decisions. Minecraft provides a representative testbed for this problem, where tasks such as crafting tools, building redstone components, and obtaining diamond equipment involve long prerequisite chains and are frequently disrupted by missing tools, blocked paths, GUI failures, or stagnant execution. To this end, we propose \textbf{MineEvolve}, a knowledge-driven self-evolution framework that converts execution feedback into actionable behavioral knowledge. MineEvolve first uses \underline{\emph{\textbf{\ding{182}Monitor}}} to convert each subgoal execution into typed feedback, including state changes, inventory changes, failure types, progress signals, and stagnation indicators. \underline{\emph{\textbf{\ding{183}Inducer}}} then derives reusable skills from successful executions and remedies from failed or stagnant executions. \underline{\emph{\textbf{\ding{184}Curator}}} validates, merges, filters, and retrieves these knowledge entries, while \underline{\emph{\textbf{\ding{185}Adaptor}}} uses them to repair the unfinished part of the plan under repeated failures or stagnation. Experiments on the Minecraft MCU long-horizon task suite show that MineEvolve consistently improves performance across multiple language-model planners, with larger gains on high-dependency task groups. Ablation and knowledge-accumulation studies further demonstrate that converting execution signals into structured behavioral knowledge is an effective path toward self-evolving embodied agents in long-horizon environments. Our code is available at \url{https://anonymous.4open.science/r/MineEvolve-1B5B}.

Recent advances in neural decoding have enabled the reconstruction of 3D visual content from functional magnetic resonance imaging (fMRI) signals, opening a route toward brain-conditioned 3D generation. Nevertheless, existing approaches largely rely on semantic or multi-view priors without explicitly modeling 3D geometric constraints, often leading to structural distortions and degraded geometric fidelity. To address this limitation, we propose MindShape, a geometry-aware neural decoding framework for fMRI-conditioned 3D reconstruction. Unlike previous methods, MindShape decodes superquadric geometry as an explicit, low-dimensional structural constraint and jointly conditions the 3D generation process on both geometric primitives and semantic descriptions, enabling semantically consistent and geometrically faithful reconstructions. Experiments show that MindShape improves reconstruction quality in terms of geometric consistency and semantic fidelity over existing baselines. These results suggest that explicit geometric primitives provide an effective structured interface between noisy neural measurements and controllable 3D generation.

Although LLMs have made substantial progress in reasoning, systematically producing frontier-level reasoning data remains difficult. Existing synthesis methods often have limited visibility into the structural factors that govern problem difficulty, which can result in narrow diversity and unstable difficulty control. In this work, we view the difficulty of a reasoning problem as arising from the accumulation of atomic knowledge-reasoning transformations, which we term *thought modes*. Building on this perspective, we propose MindLoom, a framework for synthesizing frontier-level reasoning data through compositional thought mode engineering. Given a collection of hard problems with verified solutions, MindLoom first decomposes those solutions into thought mode chains that reveal each problem's construction logic. It then trains a retrieval model that matches problem states to compatible thought modes, providing guidance on which reasoning challenges to introduce during synthesis. New problems are composed by iteratively applying retrieved thought modes to seed questions, with distribution-aligned sampling to encourage diverse reasoning coverage. Finally, a rollout-based judging stage labels generated questions by difficulty and supplies judged-correct responses for supervised fine-tuning. We evaluate MindLoom on nine benchmarks covering five STEM disciplines and four mathematical reasoning tasks across multiple model families and sizes. Models fine-tuned on MindLoom generated data consistently improve over base models, distillation, and external-data baselines across the reported benchmarks. Ablation studies indicate the contribution of each component, and further analysis suggests that MindLoom covers a broad range of reasoning patterns while maintaining useful difficulty control. We have open-sourced our implementation at https://anonymous.4open.science/r/MindLoom-5B8E.

Large language models are increasingly used for mental health support, yet their conversational coherence alone does not ensure clinical appropriateness. Existing general-purpose safeguards often fail to distinguish therapeutic disclosures from genuine clinical crises, and progress on developing better ones is bottlenecked by a lack of clinically grounded evaluation resources. To address this gap, we introduce a risk taxonomy, developed in collaboration with PhD-level clinical psychologists, that identifies actionable harm (self-harm and harm to others) while preserving space for safe, non-crisis therapeutic content. We release MindGuard-testset, a dataset of multi-turn conversations annotated at the turn level by clinical experts, which is, to our knowledge, the first public benchmark with turn-level clinical risk labels for multi-turn mental health support. We also release an automated red-teaming (ART) framework designed to measure how safety classifiers affect downstream model behavior in adversarial multi-turn interactions. Using synthetic dialogues generated via a controlled two-agent setup, we train MindGuard, a family of lightweight safety classifiers (with 4B and 8B parameters). Our classifiers reduce false positives at high-recall operating points and, when paired with clinician language models, help achieve lower attack success and harmful engagement rates compared to general-purpose safeguards. We release all models, human evaluation data, and the ART framework.

Large language models (LLMs) are increasingly deployed as interactive agents, yet their capacity for social and strategic reasoning over extended interaction remains poorly understood. Existing evaluations rely on static vignettes or single-game benchmarks that cannot capture the sustained, multi-faceted reasoning that real-world multi-agent settings demand. We introduce Mindgames, a multi-game arena and evaluation platform for LLM agents that operationalizes complementary reasoning demands relevant to ``theory of mind'': belief attribution under hidden information, opponent modeling through repeated strategic interaction, cooperative inference under knowledge asymmetries, and sustained deception in social deduction. Built on TextArena, Mindgames provides a unified interaction interface, TrueSkill-based rating, and full trajectory logging across four game environments. We instantiate Mindgames through a 2025 competition cycle hosted at a major AI conference, which assessed 944 submitted agents from 76 teams across four games: Colonel Blotto, Iterated Prisoner's Dilemma, Codenames, and Secret Mafia. Our analysis surfaces both agent-level and evaluation-level limitations: brittle rule adherence remains a major bottleneck, top-performing systems repeatedly rely on explicit structural scaffolding, and leaderboard validity differs sharply across environments. In particular, failure-heavy environments can reward robustness to opponent errors as much as strategic ability, with Secret Mafia exhibiting a pronounced error-survival confound in this cycle. We release a dataset of 29,571 multi-agent games (comprising 94,132 player trajectories and 243M tokens) with turn-level observations, actions, and rewards, together with MG-Ref, a deterministic offline tournament protocol that scores new agents against a frozen reference pool of top-ranked, low-error Stage~II submissions under the same error-attribution lens used in this analysis. By releasing the benchmark interface, dataset, MG-Ref, and starter kit, Mindgames provides a reproducible resource for studying progress in multi-agent social and strategic reasoning.

Representation alignment has emerged as an effective approach to improve Multimodal Large Language Models (MLLMs) by regularizing their internal representations toward those of an external vision encoder. However, existing methods typically align a fixed layer of the language backbone, overlooking the fine-grained structure of Transformer models. In this work, we propose **He**ad-Wise **R**epresentation **A**lignment (**HeRA**), a method that enforces cross-modal alignment at the level of individual attention heads. Our approach is grounded in the Platonic Representation Hypothesis, focusing on preserving the *topological structure* of representations (*i.e.*, their local neighborhood relationships) across modalities. Following the Mutual K-Nearest Neighbor (MKNN) alignment metric, we introduce a contrastive objective that acts as a differentiable proxy for matching local structures. HeRA applies this objective during multimodal training to specific attention heads in the LLM, selected by their alignment score according to the MKNN metric. Counterintuitively, we find that aligning the *least* aligned heads yields the largest gains. Extensive evaluations across multiple MLLMs and 18 benchmarks demonstrate that HeRA consistently improves performance on challenging vision-centric tasks and serves as an effective regularizer against visual hallucinations by naturally curbing the over-reliance on linguistic priors. Our code will be publicly released.

In cooperative multi-agent reinforcement learning under partial observability, agents typically differ in both their local observations and in how much value those observations let them recover. Most existing methods treat agents symmetrically when shaping credit and exploration, ignoring this asymmetric information disadvantage. We introduce the per-agent value gap, a state- and agent-specific quantity that measures the value loss attributable to local information limits, and show that it serves as a single, measurable signal that unifies credit assignment and exploration: down-weighting policy updates where an agent is at a strong disadvantage, and rewarding behaviors that reduce the disadvantage along the trajectory. We instantiate this idea as \method{}, which estimates the gap online with a per-agent local value head and uses it to drive both advantage shaping and an information-seeking intrinsic reward. We further show that the resulting shaping reduces the variance of the policy-gradient estimate at high-disadvantage states under a mild correlation assumption, and that the intrinsic bonus vanishes in expectation under any stationary optimal policy, so the augmented objective remains consistent with the original cooperative objective. On sixteen tasks across five cooperative benchmarks, \method{} ranks first or statistically tied for first on fifteen of sixteen tasks (strictly first on twelve), with the largest gains on settings combining sparse rewards and asymmetric observability (e.g., a $24\%$ mean relative gain over the strongest baseline averaged across the three SMAC v2 tasks).

Audio descriptions (AD) are essential for making visual media accessible to blind and low-vision (BLV) users. While Multimodal Large Language Models (MLLMs) offer a scalable solution for generating audio descriptions on-demand, their performance on ``inline'' audio descriptions -- which must fit within existing silences in a video -- remains under-explored, particularly for diverse user-generated content (UGC). We present a comprehensive investigation into MLLM-generated inline audio descriptions. First, we introduce a professionally annotated dataset of 36 hours of videos, each averaging $\sim$5 mins. and total 7k+ descriptions, providing a high-quality benchmark for this task. Second, we propose an evaluation framework based on audio description expert guidelines that provides fine-grained actionable metrics for model improvement. Crucially, our framework evaluates the end-to-end task: it renders the generated scripts into audio tracks to assess their fit within the original video's natural silences, minimizing disruptive overlaps. Our analysis reveals that while frontier MLLMs accurately describe visual events, significant gaps persist in audio-visual timing, quality, and narrative flow. Finally, we validate the framework and conduct studies with BLV participants and sighted raters, finding that while users narrowly prefer human-authored audio descriptions, they still find MLLM-generated audio descriptions highly beneficial for comprehension. We provide guidance on the current capabilities of MLLMs for audio descriptions and release our dataset and evaluation suite to the community.

Do behavioral styles in large language models correspond to reusable directions in residual space, or do they mainly appear after averaging many noisy contrastive examples? We introduce MinSteer, a two-stage cached-continuation method for estimating a contrastive residual direction (CRD) within one decoding trajectory. Stage-X generates a continuation in one style; a style-flip suffix is then processed using Stage-X's final KV cache; Stage-Y continues from this inherited trajectory. The CRD is computed from generated-token residuals only, excluding prompt and suffix tokens from the average. Across sentiment transfer, politeness control, and a ParaDetox-based bidirectional diagnostic, MinSteer extracts effective steering directions from very small contrasts. On TweetEval sentiment transfer, one MinSteer contrast outperforms a CAA baseline averaged over 50 independent pairs. Japanese keigo CRDs transfer to English and Chinese outputs and outperform trajectory-free TwoSeq controls. In ParaDetox, MinSteer produces bidirectional Detoxify movement under our rewrite setup, while exposing semantic-preservation trade-offs. The directions transfer across tested scenarios and languages and show clear depth dependence. Together, these results show that cached self-rewrite trajectories provide a cleaner signal for residual-space behavior directions than independent-pair averaging.

Large language models increasingly rely on long Chain-of-Thought (CoT) to solve complex reasoning tasks, but the resulting CoT often contains repeated checks, abandoned branches, and unused planning that increase inference cost without supporting the final answer. Existing efficient reasoning methods address this through length budgets, token-level importance, confidence signals, or a stronger teacher model, treating CoT compression mainly as a text-shortening problem rather than as a question of which steps the answer actually depends on. We propose MinPath, a training framework that treats CoT compression as a graph problem. The raw CoT is represented as a Typed Reasoning Graph, where the Minimal Dependency Path supporting the target conclusion is extracted, and the resulting MinPath is used for fine-tuning. Across four reasoning models on GSM8K, MATH-500, and AIME24, MinPath reduces generated tokens by 33.9\% on average with nearly unchanged precision (accuracy even improved in 41.7\% of all experiments) and outperforms five compression baselines in every evaluated setting.

We show that the MinMax algebra provides a form of recurrence that is expressively powerful, efficiently implementable, and most importantly it is not affected by vanishing or exploding gradient. We call MinMax Recurrent Neural Cascades (RNCs) the models obtained by cascading several layers of neurons that employ such recurrence. We show that MinMax RNCs enjoy many favourable theoretical properties. First, their formal expressivity includes all regular languages, arguably the maximal expressivity for a finite-memory system. Second, they can be evaluated in parallel with a runtime that is logarithmic in the input length given enough processors—and they can also be evaluated sequentially. Third, their state and activations are bounded uniformly for all input lengths. Fourth, at almost all points, their loss gradient exists and it is bounded. Fifth, they do not exhibit a vanishing state gradient: the gradient of a state w.r.t. a past state can have constant value one regardless of the time distance between the two states. Finally, we find empirical evidence that the favourable theoretical properties of MinMax RNCs are matched by their practical capabilities: they are able to perfectly solve a number of synthetic tasks, showing superior performance compared to the considered state-of-the-art recurrent neural networks; also, we train a MinMax RNC of 127M parameters on next-token prediction, and the obtained model shows competitive performance for its size, providing evidence of the potential of MinMax RNCs on real-world tasks.

Automated discovery of governing equations remains challenging when models rely only on numerical tokens and ignore the phase-space and trajectory evidence that is informative in low-dimensional dynamics. We propose Visual Induction for Physics-based Equation Reasoning (VIPER-R1), a multimodal framework for visual formula discovery from phase portraits, trajectory plots, and aligned measurements. VIPER-R1 uses a supervised Motion Structure Induction (MSI) curriculum for joint rationale-and-equation generation, and is then refined by \textbf{Reward-Guided Symbolic Calibration (RGSC)}, a GRPO-based stage optimized with a structure-aware reward that emphasizes topological correctness over coefficient matching. At inference time, we optionally apply Symbolic Residual Realignment (SR$^2$), an external symbolic regression module that models only the residual numerical mismatch of the base hypothesis. We release PhysSymbol, a 10{,}000-instance two-part multimodal corpus; the quantitative evaluation in this paper uses its Part 1 mechanics split, which provides paired visualizations, trajectory data, and expert C-CoT traces. On this benchmark, VIPER-R1-7B achieves the best structural score ($S_{\mathrm{struct}}=0.812$), is effectively tied with VIPER-R1-3B on exact-match accuracy ($S_{\mathrm{acc}}=0.487$ vs.\ $0.488$), and, after optional SR$^2$ refinement, reaches a Post-SR$^2$ MSE of $0.032$, nearly $3\times$ lower than the best VLM baseline. These results show that VIPER-R1 improves symbolic structure induction in focused low-dimensional dynamics by combining paired visual evidence with structure-aware calibration to produce stronger first-order hypotheses for downstream refinement.