NeurIPS 2026 Papers

Recently, a series of works have started studying variations of concepts from learning theory for product spaces, which can be collected under the name high-arity learning theory. In this work, we consider a high-arity variant of sample compression schemes and we prove that the existence of a high-arity sample compression scheme of non-trivial quality implies high-arity PAC learnability.

High-dimensional robotic reinforcement learning (RL) is often bottlenecked by inefficient exploration in large, redundant actuator spaces. We introduce Devyn (Developing synergies), a lightweight framework that learns a structured low-dimensional action parameterization directly during policy optimization. Unlike methods that require precomputed synergies or structured exploration in the full action space, Devyn starts from a randomly initialized latent-to-action map and shapes it online through task interaction. The policy acts strictly in a reduced latent space, while a learnable synergy matrix decodes latent actions into actuator commands. To make this evolving decoder stable and useful for policy learning, Devyn combines slow decoder evolution with structural regularization, reducing latent-action semantic drift while encouraging compact coordination patterns. Across diverse continuous-control benchmarks, including high-dimensional humanoid and overactuated musculoskeletal systems, Devyn improves upon standard SAC and achieves competitive or better performance than recent methods designed for high-dimensional robotic control. Ablations show that the gains do not come from a generic latent-action bottleneck alone, but rather from the slow, structured evolution of the synergy matrix. Our results suggest that learning the action parameterization itself can be a simple and effective route to scaling RL for high-dimensional robots.

Conditional independence (CI) testing is a fundamental problem in statistics. However, classical nonparametric CI tests suffer from the curse of dimensionality, as nonparametric estimation degrades rapidly in high dimensions. This paper proposes RP-CIT, a random-projection-aggregated CI test that remains effective in the high-dimensional regime. The central idea is to project $X$ and $Y$ onto random one-dimensional subspaces before applying a univariate base CI test. This projection (i) preserves conditional independence under the null hypothesis and (ii) reduces the original high-dimensional problem to a collection of univariate CI subproblems, thereby avoiding high-dimensional nonparametric estimation. Since a single projection may miss the dependence signal, we aggregate the $p$-values from $k$ independent projections via a Bonferroni-max rule, which asymptotically controls the Type~I error at the nominal level and yields a limiting Type~II error bound that decreases exponentially in $k$ under a detectable-projection condition. The paper also develops a top-$r$ aggregation extension for alternatives whose signal is spread across multiple projection directions. More broadly, the random-projection aggregation framework can be combined with other scalar base tests; as one example, we use a projected GCM base test to accommodate higher-dimensional conditioning variables. Experiments on synthetic benchmarks, image-valued CI tasks, and Norman Perturb-seq module skeleton learning illustrate the calibration, power, and practical utility of the framework.

The trend towards larger training setups has brought a renewed interest in partially asynchronous two-phase optimizers which optimize locally and then synchronize across workers. Additionally, recent work suggests that the one-worker version of one of these algorithms, DiLoCo, shows promising results as a (synchronous) optimizer. Motivated by these studies we present an analysis of LA-DiLoCo, a simple member of the DiLoCo family, on a high-dimensional linear regression problem. We show that the one-worker variant, LA, provides a different tradeoff between signal and noise than SGD, which is beneficial in many scenarios. We also show that the multi-worker version generates more noise than the single worker version, but that this additional noise generation can be ameliorated by appropriate choice of hyperparameters. We conclude with an analysis of SLA --- LA with momentum --- and show that stacking two momentum operators gives an opportunity for acceleration via a non-linear transformation of the ``effective'' Hessian spectrum, which is maximized for Nesterov momentum. Altogether our results show that two-phase optimizers represent a fruitful new paradigm for understanding and improving training algorithms.

We study risk control for online policy learning, where an agent adaptively collects data and aims to learn a new policy where the risk is below a tolerance threshold at every round with a high probability. Such policy updates and data collection induce feedback covariate shift (FCS): the observed data depend on the history through the evolving policies and data-collection process. FCS brings two substantive problems for risk control: 1) efficient risk evaluation for each candidate policy and 2) valid policy selection with high probability risk control. To address these, we propose an efficient permutation-based weighted risk evaluator based on the Sinkhorn algorithm and select policies whose estimated risk upper confidence bounds (UCB) fall below the target threshold, with the UCB obtained through a proposed Gaussian bootstrap method. Theoretically, we prove that our risk evaluator's worst-case variance is no greater than that of the standard importance-weighted evaluator. Also, our policy control method yields an asymptotically valid simultaneous risk bound and provides asymptotic high-probability risk control for the selected policy. Empirically, our method maintains the target risk level, achieves lower risk than baseline methods, has lower variance in risk estimation, and enables reliable policy selection with high-probability risk control.

Differentially Private Stochastic Gradient Descent (DP-SGD) is the dominant approach to private deep learning, but it pays compute and privacy budget \emph{per trained model}: each new architecture, ensemble member, or downstream fine-tuning round incurs additional privacy cost. We propose \textsc{SPS} (Summarize--Privatize--Synthesize) and its enhanced variant \textsc{SPS+}, dataset-distillation algorithms that release a private synthetic dataset by privatizing intermediate activation statistics from a public pretrained model. Once released, the dataset is post-processed freely: any downstream architecture, ensemble, federated aggregation, or continual update incurs \emph{zero} additional privacy cost. In particular, a single \textsc{SPS+} dataset distilled from a Wide ResNet-22-8 transfers zero-shot to architectures with different inductive biases (Vision Transformers, Swin Transformers, and ConvNeXt), all without re-incurring privacy. Empirically, \textsc{SPS+} is competitive with state-of-the-art DP-SGD across $\epsilon \in \{1,2,4,8\}$ on CIFAR-10 and CIFAR-100, with a notable advantage on CIFAR-100 under strict privacy, achieving a $5.8\%$ gain at $\epsilon{=}1$ over compute-matched DP-SGD. \textsc{SPS+} additionally outperforms prior generation-based DP methods by a large margin and supports private federated and continual learning out of the box.

Adapting pretrained diffusion models to downstream objectives such as inverse problems often requires expensive test-time guidance or optimization. We propose a principled framework for generating high-quality reward-aligned samples at substantially reduced inference cost. Our approach formulates test-time adaptation as a hierarchical variational model, where control is amortized into a lightweight yet expressive stochastic policy. This formulation naturally supports few-step diffusion sampling: large step sizes enable fast inference, while the learned policy maintains sample quality by providing structured per-step control. The resulting fully amortized sampler achieves a strong quality--speed tradeoff, matching or exceeding recent test-time scaling baselines while requiring significantly less compute. For example, on $4\times$ super-resolution, our method achieves better perceptual quality with more than 5$\times$ faster inference compared to the best-performing baseline. We further extend our approach to a semi-amortized regime that combines cheap amortized proposals with limited test-time optimization, achieving state-of-the-art perceptual quality across several challenging inverse problems.

Class-Incremental Learning (CIL) enables models to learn new classes continually while preserving past knowledge. Recently, vision-language models like CLIP offer transferable features via multi-modal pre-training, making them well-suited for CIL. However, real-world visual and linguistic concepts are inherently hierarchical: a textual concept like ''dog'' subsumes fine-grained categories such as ''Labrador'' and ''Golden Retriever,'' and each category entails its images. But existing CLIP-based CIL methods fail to explicitly capture this inherent hierarchy, leading to fine-grained class features drift during incremental updates and ultimately to catastrophic forgetting. To address this challenge, we propose HASTEN (Hierarchical Semantic Tree Anchoring), a hierarchy-aware framework that uses semantic structure to stabilize CLIP-based CIL. Rather than treating classes as isolated labels, HASTEN leverages external hierarchical knowledge as structured supervision to organize visual and textual features in hyperbolic space, helping maintain parent-child relations as new tasks arrive and mitigating feature drift. Since the shared hyperbolic mapper is updated across tasks, we further stabilize it by constraining its updates to a null space induced by prior-task features, reducing interference with previous mappings while retaining adaptability to new classes. Extensive experiments on nine benchmarks show that HASTEN consistently outperforms existing methods while reducing feature drift and catastrophic forgetting.

Forecasting the behavior of spatio-temporal systems often requires more than accurate predictions: models should uncover the dynamical modes governing future evolution. Existing temporal graph and latent dynamical models achieve strong forecasting performance, but their latent representations often entangle multiple dynamical patterns, limiting interpretability. Conversely, regime-inference methods explicitly model such modes but typically do not support generative forecasting over graph-structured systems. We introduce HERON, a self-supervised regime-aware generative framework that unifies graph-structured trajectory generation with regime identification. HERON factorizes the latent state into discrete system-level regimes, capturing global dynamical modes, and continuous entity-level dynamics, yielding a modular regime interface compatible with existing spatio-temporal backbones. Crucially, the inferred regime actively conditions system dynamics, enabling regime tracking and controlled simulations under alternative dynamical modes. Without regime annotations, HERON jointly learns forecasts and regime dynamics in a self-supervised manner, recovering meaningful modes across controlled synthetic and real-world datasets while maintaining competitive forecasting performance. These results open a path toward interpretable, controllable generative modeling of spatio-temporal dynamics.

Hierarchical graph-level tasks that require reasoning over substructures that extend beyond local neighborhoods are posing challenges for standard Graph Neural Networks (GNNs). While graph pooling aims to address this by coarsening graphs into hierarchical representations, existing methods often fail to explicitly preserve the substructures they induce, leading to inconsistent empirical performance. Moreover, the evaluation of such approaches has proved difficult due to the lack of benchmarks with explicit hierarchical structure. We propose Pooled-Substructure-Aware GNNs, an approach to graph pooling that explicitly preserves and processes substructures uncovered by structure-based pooling schemes. We show that this design strengthens pooling in terms of Weisfeiler-Lehman (WL) expressivity. To enable principled evaluation of pooling-based models, we introduce two new synthetic datasets with controllable hierarchical structure and propose a metric to characterize the extent of hierarchical patterns in real-world graph-level benchmarks. On tasks with relevant hierarchical structure, our approach outperforms matched pooling baselines, while remaining competitive on structurally simpler benchmarks.

Text-guided point-cloud grounding enables robots to ground natural-language descriptions in 3D environments, making it important for embodied AI and human-robot interaction. Existing coarse-to-fine methods primarily rely on global descriptors for submap retrieval, but these descriptors often compress object semantics, spatial relations, and scene layouts into a single vector, thereby limiting discriminability in large-scale scenes. We propose HiGraLoc, a multi-level cross-modal alignment framework that improves the coarse retrieval stage through three complementary branches. The instance branch uses a Hyperbolic Instance Structure Encoder to model hierarchical object semantics, the relation branch aggregates reliability-weighted pairwise spatial relations, and the global branch employs a Global Spectral Graph Encoder to capture multi-frequency scene structure. A Text2Loc-style coordinate regression stage then refines the location estimate within the retrieved submap. Experiments on KITTI360Pose show that HiGraLoc achieves a 19\% improvement in Top-1 recall@10m over existing state-of-the-art methods. Our code and dataset are available at https://github.com/Anonymous09871745/HiGraLoc.

In fine-grained image recognition, semantic parts (e.g., wings, head) recur across classes while discriminative cues lie in within-part features (e.g., yellow wings, striped wings). The prototypical part network (ProtoPNet) is an interpretable model that provides case-based explanations for image recognition by measuring similarities between local patches in an images and their closest prototypes representing patches in a training set. However, existing ProtoPNet variants do not explicitly model this two-level structure, causing prototypes for the same anatomical part to fragment across classes. We propose a hierarchical prototype learning framework that separates shared prototypes capturing cross-class part concepts from class-specific prototypes capturing intra-part features. To model this hierarchy geometrically, prototypes are embedded in hyperbolic space and an entailment loss constrains each class-specific prototype to lie within the cone of its corresponding shared prototype. To prevent degenerate trivial solutions such as redundant prototypes, we introduce a patch-level contrastive learning using pseudo patch IDs from a vision foundation model, used only at training time, leaving the backbone choice free at inference. Unlike prior hyperbolic prototype methods where prototype hierarchies are uncontrolled, our framework defines explicit shared part to intra-part feature correspondences. Across four ProtoPNet variants and four backbones on CUB-200-2011 and Stanford Cars, our method improves classification accuracy by up to 10 points, raises hierarchical part hierarchy IoU from 11\% to 75\%, and consistently improves four interpretability metrics on CUB-200-2011.

Conformal prediction (CP) provides reliable uncertainty quantification by generating prediction sets with finite-sample coverage guarantees, yet it typically ignores hierarchical relationships between classes. We introduce Hierarchical Conformal Classification (HCC), a framework that integrates class hierarchies into the structure and semantics of prediction sets. HCC uses a constrained optimization problem formulation to produce prediction sets composed of nodes at various hierarchy levels while maintaining rigorous coverage guarantees. To ensure computational efficiency, we prove that a restricted subset of well-structured candidate solutions is sufficient to maintain both optimality and coverage. Empirical evaluations across audio, image, and text benchmarks, alongside a user study, demonstrate that HCC outperforms state-of-the-art methods and that hierarchical prediction sets align better with human preferences.

We propose a distributional theory of how hypernymy---the ``is-a'' relation between general and specific concepts---is encoded geometrically in language representations. Starting from the empirically verified assumption that words closer on the WordNet hypernym graph co-occur more often, we characterize theoretically the spectrum of the resulting embedding Gram matrix of word2vec embeddings. Under mild positivity and decay conditions on the co-occurrence kernel, we prove that the leading eigenvectors first separate broad taxonomic branches and then progressively finer sub-branches, producing a \emph{hierarchical splitting geometry} with a coarse-to-fine spectral organization that mirrors the tree. We confirm these predictions in word2vec embeddings across many sampled WordNet subtrees, and show that the same signature extends strikingly well to Gemma 2B unembeddings. Our results indicate that hierarchical concept geometry in LLMs need not reflect a hierarchy-specific functional mechanism, but emerges from the spectral structure of pairwise word statistics.

Due to their simplicity and interpretability, linkage methods are a central class of hierarchical agglomerative clustering (HAC). In particular, representative-based methods, such as centroid and medoid approaches, are appealing because their representatives provide intuitive summaries of the clusters. However, many representative-based linkage methods suffer from important drawbacks, such as high computational cost and the generation of inversions, which limit their broader applicability. We introduce *relaxed-representative clustering*, a principled generalization of representative-based linkages that preserves their interpretability while addressing these limitations. This framework yields (i) RMM*, a quadratic-time variant of the cubic-time Minimax method, and (ii) RC*, an inversion-free variant of the Centroid method whose representatives belong to the input set. On the theoretical side, we prove that for every $k$ our methods are $O(\min\{k,\log n\})$-approximation algorithms for the $k$-center objective. Empirically, experiments on tabular, biological, and textual datasets show that RMM* consistently outperforms several baselines and achieves clustering quality comparable to Minimax at a fraction of the computational cost. Meanwhile, RC* remains competitive with the Centroid method while producing inversion-free dendrograms and interpretable representatives.

Due to context-length constraints, most MLLMs cannot process full-length videos and therefore rely on sampling a subset of frames as input. However, existing sampling methods, ranging from uniform sampling to relevance-based selection, are often driven by a single sampling principle and thus struggle to accommodate the heterogeneous evidential requirements of different queries: some demand a holistic understanding of how the video unfolds over time, while others hinge on fine-grained events within a short temporal window. To address this limitation, we propose Hierarchical Adaptive Frame Sampling (HAS), a two-stage frame sampling framework. In the first stage, Backbone Frame Construction, we apply a Determinantal Point Process (DPP) to sample frames that are both query-relevant and non-redundant. These selected frames capture key moments across the video and form the backbone of the sampling set, providing a foundation for subsequent enrichment. In the second stage, Adaptive Contextual Enrichment, we analyze the temporal distribution of the backbone frames to infer the query type and adaptively allocate the remaining frame budget between Local and Global Context. The Local Context enriches the backbone with fine-grained temporal dynamics and short-range causal relations, whereas the Global Context connects temporally isolated evidence and provides a holistic view of the entire video to support global understanding. Through such a hierarchical two-stage process, HAS effectively addresses diverse query requirements. Incorporated into three leading MLLMs, it demonstrates consistently superior performance across the Video-MME, LongVideoBench, and MLVU benchmarks. We have released our code.

Open-vocabulary indoor scene synthesis aims to generate plausible layouts from arbitrary user instructions while ensuring physical feasibility and semantic consistency. Existing methods directly infer spatial relations between objects from instructions and solve for layouts based on predefined rules, achieving progress in physical feasibility. However, they often struggle to precisely align with complex instructions due to insufficient comprehension of spatial relations and limited capability to translate them into layouts. In this paper, we propose a Hierarchical Reasoning and Reflection agent framework (HierRR), which leverages a relational hierarchy to enable multi-granularity spatial relation comprehension and attributable layout reasoning, improving semantic consistency while maintaining physical feasibility. Specifically, HierRR introduces the spatial transformation chain‑of‑thought reasoning module that explicitly models the mapping from spatial relations to executable geometric placements, mitigating semantic drift during reasoning. Furthermore, the semantic- and vision-guided reflection module is employed to iteratively refine spatial relations and layout reasoning from local to global along the hierarchy, effectively bridging the gap between language instructions and geometric layouts. Extensive comparative experiments and ablation studies demonstrate that HierRR generates more plausible and semantically consistent indoor scene layouts than existing methods, while generalizing effectively to complex scenes with numerous objects and diverse spatial constraints.

Agentic AI systems enable LLMs to solve non-trivial tasks through structured workflows, but automatically generating such workflows remains challenging due to the discrete and combinatorial search space. Existing methods often rely on offline search or training, limiting query-level adaptability and incurring substantial data and engineering overhead. We formulate workflow generation as a coupled topology--execution search problem, where the upper-level topology induces subtask-specific code-search domains and lower-level execution feedback can revise the topology itself. Based on this formulation, we propose HierFlow, a training-free hierarchical test-time search framework for automatic agentic workflow generation. HierFlow couples feedback-driven topology refinement with an MCTS-inspired lightweight tree search for execution-level sub-workflow optimization, and uses an adaptive gating mechanism to selectively trigger execution-level search based on estimated necessity. We further provide a coupling-aware analysis characterizing when hierarchical decomposition and proxy-based gating are beneficial and when their advantages may degrade under stronger cross-subtask coupling. Experiments across QA, mathematical reasoning, and code generation benchmarks show that HierFlow achieves strong performance and favorable efficiency--quality trade-offs, outperforming competitive baselines without additional training.

Long-horizon visual search requires a vision-language policy to execute multi-step spatial actions over high-resolution images, where performance depends on the entire trajectory rather than any single decision. Existing supervision breaks at this horizon: outcome-only RLVR collapses many geometric decisions into a single delayed signal and discards the per-step geometry the environment already computes, while LLM-judged step rewards recover density at the cost of verifiability, scale linearly with trajectory length, and conflate distinct failure modes. We propose HSSP, a self-play framework in which a Hider adaptively weights challenging skeletons from a fixed trajectory pool and a Seeker learns to solve them through grounded spatial actions. Instead of relying on external judges, HSSP supervises every step with a geometry-verifiable process reward built from target-directed progress and exploration coverage, with trajectory length and spatial redundancy enforced as separate Constrained Markov Decision Process (CMDP) constraints. We pair HSSP with V-Trace, a trajectory-level companion dataset that augments skeleton seeds from established benchmarks with target-region annotations and explicit search-regime labels, ready for any trajectory-level training framework. The reward design admits closed-form guarantees on backtracking, find-versus-explore separation, and policy invariance, providing theoretical backing for the observed gains. Extensive empirical results on eleven challenging multimodal benchmarks, supported by controlled ablations and qualitative case studies, show that HSSP consistently outperforms advanced baselines and transfers zero-shot to OOD tasks.