NeurIPS 2026 Papers

Constrained Markov decision processes (CMDPs) extend standard MDPs by incorporating a cost function and enforcing constraints---most commonly by requiring that the expected cumulative cost over the entire trajectory remains below a prescribed threshold. While this global, expectation-based formulation is natural and widely studied, it is insufficient for many safety- and reliability-critical applications, where guarantees are required not only from the initial state but also for every subprocess starting at any intermediate time step. Motivated by this need, we introduce \emph{subprocess-constrained MDPs} (S-CMDPs), in which the expected cumulative cost must satisfy a constraint not only from the initial state, but from every intermediate step onward along the trajectory. We investigate the algorithmic aspects of this model and characterize the limitations of classical solution concepts. In particular, we show that stationary policies can be both suboptimal and computationally intractable to optimize in S-CMDPs. Leveraging a value-set iteration framework, we further demonstrate that history-dependent policies surprisingly overcome both obstacles. Building on this insight, we develop a polynomial-time algorithm that computes the action distribution of a (near-)optimal history-dependent policy for any given history.

LLM agents that execute multi-step tool calls must satisfy two objectives simultaneously: completing the user's task (utility) and conforming to domain policies and correctness constraints (safety). These objectives are in tension -- blocking an unsafe action prevents a violation but can leave the agent stranded with no principled way to recover. Existing approaches sacrifice one objective for the other. We introduce Soteria, a framework that reconciles safety and utility through verified hierarchical planning and runtime enforcement of specifications. Before execution, the agent generates a structured plan that is formally verified against the specifications prior to any tool invocation. During execution, the verified plan serves dual roles: it ensures that the agent takes specification-conformant trajectories and provides guidance when unsafe actions are blocked. Across multiple benchmarks covering a diverse range of tool-use tasks, Soteria achieves perfect specification conformance while improving utility by up to $5\times$ over existing guardrail approaches, demonstrating that safety and utility need not be traded off.

Learning-based safety certification offers a promising route for verifying complex dynamical systems when explicit models are unavailable, but existing data-driven methods often scale poorly: they treat the system as a black box, rely on dense discretizations or Lipschitz bounds, and consequently suffer from sample complexity that grows exponentially with dimension. This paper shows that a common structural property of dynamical systems---*monotonicity*---can be used to break this curse of dimensionality. We develop a data-driven framework for robust safety verification and safe controller synthesis for unknown monotone systems using only simulator queries. Our main theoretical result proves that, for monotone systems with upper-closed unsafe sets, safety is completely characterized by the existence of monotone inductive barrier certificates. This structure reduces certificate verification over continuous state spaces to localized boundary checks over finitely many cells. To learn such certificates, we introduce Max-Monotone Networks, a monotone neural architecture with universal approximation guarantees for monotone functions. We then propose a training and refinement algorithm that, upon successful termination, returns formally valid neural barrier certificates and, under mild partition assumptions, requires only $O(n)$ simulator queries. Across high-dimensional benchmarks, including oscillator networks with up to $13{,}659$ states and traffic networks with $1{,}000$ states, our method certifies safety in regimes where prior approaches either do not converge or exceed memory limits. These results demonstrate that exploiting order structure can make neural safety certification both scalable and formally sound.

Safe robot learning often involves multiple heterogeneous safety constraints that cannot always be satisfied simultaneously. Existing neural safety layers typically treat multi-constraint safety as a numerical optimization problem, enforcing all constraints through a single QP-based projection or relaxing conflicts with slack variables. This hides the semantic question of which constraints may be sacrificed under conflict inside solver geometry, penalty weights, or a fixed total hierarchy. We propose PoSafeNet, a poset-structured composable safety layer that makes these conflict semantics explicit. PoSafeNet encodes admissible safety override relations as a partial order and realizes each admissible execution by composing closed-form projections onto CBF-induced halfspaces. Across multi-obstacle navigation, constrained manipulation, and vision-based autonomous driving, PoSafeNet improves operational feasibility, computational efficiency, and task performance over dQP-based, slack-based, and hierarchical safety layers.

Large language models (LLMs) are increasingly adapted inside privacy- and regulation-constrained institutions where local post-training data cannot be centrally pooled. Federated learning therefore becomes a natural mechanism for collaborative LLM adaptation, but it also raises a safety question that is not captured by either classical federated learning or standard centralized alignment: clients may share a model while still requiring different safe behaviors. We formalize this setting as \emph{personalized federated safety}, where safety correctness is conditioned on the target client's local policy rather than treated as a single global refusal rule. To make this problem transferable rather than benchmark-specific, we introduce a compact, interpretable client policy space and a policy-conditioned benchmark construction framework, then instantiate it with five representative client archetypes spanning regulated healthcare, legal compliance, financial safety, youth safety, and enterprise general safety. The resulting benchmark contains 1{,}500 client-conditioned training examples and 750 held-out evaluation examples. We further propose \emph{Safety-Aware Weighted LoRA} (SAW-LoRA), a lightweight add-on for federated LoRA fine-tuning that lets each client selectively absorb incoming global task updates according to estimated task benefit and local-safety risk. Across two task datasets and two backbones, this add-on substantially lowers client-specific ASR for the strongest local safety mechanisms, reaching ASR near $1$--$2\%$ while preserving high benign acceptance. These findings position personalized federated safety as a concrete research problem with a practical update mechanism for federated LLM adaptation.

Machine learning is increasingly used for autonomous navigation, yet safety regulations governing safety-critical AI applications require rigorous datasets and protocols to evaluate learned planners on terrain-aware routing. Existing path-planning benchmarks address this only partially: synthetic grids offer algorithmic control without geographic realism, while Geographic Information System (GIS) resources provide real terrain without controllable obstacles or standardised baselines. To close this gap and steer research toward more trustworthy AI-based planners, especially in line with EASA and FAA guidance on AI, we introduce **PASSAGE**, an open-source benchmark and dataset that reframes constrained terrain path planning as a *controlled trustworthiness-oriented evaluation harness* rather than a static dataset. PASSAGE is sampled from a well-defined Operational Design Domain (ODD) built on JAXA ALOS AW3D30 elevation at its native 30 m/pixel resolution, and is derived into seven input-tensor resolutions from 64×64 to 4096×4096 pixels, totalling *4.4 million samples* for ≈ *2.43 TB* of compressed data. Each sample is a real-terrain cost grid annotated with start and goal markers, procedurally generated super-ellipse obstacles, and exact A* path labels under three physically interpretable cost models. The release pairs this dataset with a deterministic generation pipeline, a geographic hold-out, ODD-coverage diagnostics, and a rigorous evaluation protocol — a shift from *dataset collection* towards *auditable benchmark design* that provides a rare level of experimental control for studying robustness, generalisation, and other trustworthiness properties of safety-critical embedded AI. PASSAGE thereby offers a common surface for comparing AI-based path planners, including two dense-vision approaches we introduce as illustrative examples (path-mask segmentation and depth-estimation-inspired cost-to-go regression), with graph-neural and reinforcement-learning families as natural future extensions. Although motivated by aerospace trustworthiness requirements such as completeness, correctness, and representativeness, PASSAGE broadly supports trustworthy machine learning across robotics, autonomous navigation, and other safety-critical planning domains. Code (anonymous repository) and dataset (anonymous mirror) are released openly under permissive licences.

Goal-conditioned planning requires compressing value functions into low-dimensional representations, yet which property of the compression best predicts planning quality remains unclear. We show that reconstruction accuracy and ordinal fidelity---how faithfully the ranking of successor states by value is preserved---are two projections of the same approximation error: in smooth geometry they couple tightly and $L^2$ is a sufficient summary; when topology creates dense small-gap regions they decouple, and the ordinal projection carries complementary planning-relevant information beyond $L^2$. Through experiments on gridworld, continuous navigation (640 runs, 8 environments), and Maze2D (240 runs, 3 D4RL layouts), we establish three results. First, neighbor-restricted ordinal fidelity ($\tau^{\mathrm{nbr}}$) adds $\Delta R^2 = 0.106$ of incremental explanatory power beyond $L^2$ after environment fixed effects. Second, monotone recalibration degrades $L^2$ by up to $\sim\!400\times$ while preserving $\tau^{\mathrm{nbr}}$ and planning success. Third, in matched-pair comparisons controlling for $L^2$, higher $\tau^{\mathrm{nbr}}$ predicts better planning 76\% of the time. We provide theoretical grounding via a gap-weighted Bellman-excess decomposition that links reconstruction error, local ordinal inversions, and planning regret.

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.

Safe reinforcement learning (RL) commonly enforces expected-cost constraints, but such expectation safety may fail to control the probability of rare high-cost trajectories. Chance-constrained MDPs (CCMDPs) impose a stronger probability-level requirement, but are widely viewed as harder because the chance constraint is nonconvex and depends on the full trajectory rather than a Bellman-linear expectation. In this paper, we reveal that this computational difficulty does not imply a higher statistical price. In tabular discounted CCMDPs, we give a Bellman-certified model-based algorithm whose sample complexity matches the \emph{minimax optimal} primary dependence of classical CMDP learning, and prove a matching lower bound. Technically, our key idea is the \emph{Bellman distributional certificate}, which constructs a Bellman recursion for constraint violation probabilities before policy selection. The certificate can be reused across candidate policies, shifting concentration analysis from the number of possible policies to a finite Bellman certificate table. Building on this certificate, we establish high-probability safety and near-optimality guarantees for deterministic policy learning in discounted CCMDPs. To our knowledge, we also provide the first model-free sample complexity guarantee for stochastic policy learning in CCMDPs via variance-reduced policy gradient. Numerical experiments on synthetic CCMDPs and IEEE 14-bus energy-storage control benchmark illustrate the safety and behavior of the proposed algorithms.

In this paper, we study last-iterate convergence in stochastic constrained convex--concave minimax optimization. A key difficulty is that the last iterates of vanilla stochastic extragradient (S-EG) and stochastic optimistic gradient descent--ascent (S-OGDA) can fail to converge in the presence of gradient noise, even for simple bilinear problems. To address this issue, we regularize the original convex--concave problem into a strongly convex--strongly concave one. Applying S-EG and S-OGDA to the regularized problem gives two simple single-loop first-order methods, which we call perturbed S-EG and perturbed S-OGDA. By carefully choosing the regularization parameter and balancing the resulting regularization bias, stochastic error, and optimization error, we prove that both methods achieve a last-iterate convergence rate of $\mathcal{O}(T^{-1/4+\varepsilon})$ for any $\varepsilon>0$ in terms of the primal--dual gap. This improves upon the best-known $\tilde{\mathcal{O}}(T^{-1/7})$ rate under comparable constrained settings. Moreover, for unconstrained problems, we establish almost sure convergence under a single-timescale stepsize scheme, whereas prior almost sure convergence results typically rely on two-timescale stepsizes and are limited to S-EG.

Computer-use agents (CUAs) that interact with real systems can automate complex tasks, but introduce critical safety risks in long-horizon tool-use workflows. Many existing benchmarks rely on outcome-based evaluation, however, outcome-based evaluation cannot reflect agent's safety awareness, as an agent may reach a safe outcome by chance while taking unsafe steps during planning. To address this gap, we present \textsc{LPS-Bench}, which extends the outcome-centric evaluation towards LLM agents' safety awareness in tool usage (MCP/skill) over long-horizon tasks, as reflected at the action trajectory level. \textsc{LPS-Bench} comprises 570 test cases derived from 65 scenarios across 7 task domains and 9 planning-risk types, with user contexts spanning both benign ambiguity and adversarial steering. Results on \textsc{LPS-Bench} across 13 representative LLM agents reveal previously underexamined safety failures in long-horizon tool-use tasks, showing that current agents often struggle to maintain safety awareness under ambiguous benign instructions and adversarial steering. We further analyze key failure modes and evaluate lightweight mitigation strategies, showing that prompt-based interventions provide limited improvements yet remain insufficient for robust trajectory-level planning safety.

Nonlinear independent component analysis (nICA) is generally unidentifiable due in part to measure-preserving automorphisms (MPAs), which induce indistinguishable latent representations. We show that for non-Gaussian sources with mild regularity assumptions, such MPAs are not Lipschitz, motivating Lipschitz continuity as a structural assumption. Under this condition, we prove global identifiability of nICA within the class of Orthogonal Coordinate Transformations (OCTs) with bounded sources, recovering the true components up to permutation and scaling. Our analysis reduces the learning problem to a linear program over the Birkhoff polytope, and extends to functions with symmetric Jacobians, revealing connections to optimal transport. We introduce OCTNet and SYMNet, normalizing flow architectures that enforce these constraints in practice. Experiments demonstrate strong recovery performance and robustness to model misspecification, outperforming existing approaches.

Diffusion models have emerged as powerful tools for planning and control by learning multimodal distributions over actions and trajectories. Yet reliable inference-time safety enforcement remains a key barrier to their deployment in safety-critical tasks. Existing approaches typically project each denoising iterate onto the feasible set, even though constraints are defined only on the final clean trajectory. Enforcing feasibility on noisy intermediate samples can therefore overconstrain the sampling dynamics, substantially degrading sample quality. To address this limitation, we introduce DiRecT (**Di**ffusion-based planning via **Rec**eding-horizon denoising with **T**erminal constraints), a training-free algorithm for constrained sampling from diffusion models via stochastic optimal control (SOC). DiRecT enforces constraints only on the final clean sample, avoiding unnecessary restrictions on the intermediate denoising dynamics. Inspired by model predictive control, we derive a principled receding-horizon surrogate for the otherwise intractable constrained SOC formulation, yielding an efficient algorithm that cleanly separates stochastic denoising from constraint satisfaction, progressively steering samples toward feasible final trajectories without distorting the learned diffusion dynamics. Furthermore, DiRecT is highly flexible: it can leverage off-the-shelf or domain-specific optimizers, incorporate priors over environment dynamics, and optimize additional soft rewards. Extensive experiments on safe planning benchmarks demonstrate that DiRecT substantially improves deployment safety and task performance over existing diffusion-based planning baselines.

Jailbreak attacks that frame harmful queries as professional requests can bypass LLM safety training, but we do not know which ingredients in a professional-framing pipeline actually matter. We introduce a **pre-specified 2×2×2 factorial-ablation design for jailbreak decomposition**, separating access-driving from depth-driving components, and apply it to one concrete pipeline family, **Structured Three-stage Framing (STF)**: a **Persona Adoption** turn (S1) that establishes professional identity, a **Moral Justification** turn (S2) that appeals to harm prevention, and a **Linguistic Substitution** (S3) of framework terminology for colloquial language. Tested on N = 5,000 trials across three closed frontier models (~31,900 total trials across nine LLMs), the decomposition isolates **S1 (Persona Adoption) as the dominant contributor to acceptance** (OR = 6.5), **S3 (Linguistic Substitution) as the dominant contributor to depth** (β = 0.91), and **S2 (Moral Justification) showing no detectable positive effect at the stated equivalence bounds** (pooled OR = 0.83; TOST at [0.67, 1.50]) — a component ordering we write as **S1 > S3 > S2** (Persona > Linguistic Substitution > Moral Justification). This ordering holds across three full-rank factorial replications (defensive system prompt, cybersecurity, social engineering; N ≈ 5,000 each) and nine additional robustness checks. Two defensive targets follow: detect persona claims to block access; restrict output depth when responses use framework terminology. The method is portable beyond STF; the empirical result is specific to one pipeline tested primarily through provider APIs, with open-weight corroborations on local inference (§3).

Randomized controlled trials typically assume that prognostic covariates are known and available at no cost. In practice, obtaining high-dimensional pretreatment data is costly, forcing a trade-off between covariate-adaptive precision and a measurement budget. We introduce Dynamic Adaptive Rerandomization via Thompson Sampling (DARTS), which treats covariate acquisition as a sequential optimization problem embedded within a design-based causal inference task. A budgeted combinatorial Thompson sampler learns which covariates are most prognostic across successive batches; selected covariates then drive rerandomization and regression adjustment to reduce batch-level average treatment effect variance. Our primary theoretical contribution is a decoupling result: adaptive covariate selection based on past batches preserves batch-level randomization validity, and the cumulative inverse-variance weighted estimator achieves at least nominal asymptotic coverage. We further derive a Bayes risk bound for the acquisition layer that matches the minimax lower bound up to logarithmic factors. Empirically, DARTS systematically concentrates budget on informative features, significantly closing the efficiency gap to oracle designs while maintaining strict inferential validity.

Constrained learning has been increasingly applied to various domains to ensure explicit feasibility requirements due to fairness, safety, robustness, regularization, and physics or logic constraints. Understanding how training samples influence the solution (e.g., learned parameters) of constrained learning is crucial for interpretability and robustness. The classical influence function may become unreliable in constrained settings: data perturbations can reshape both the objective and the feasible region, leading to estimates that violate feasibility. In response, we propose the Directional Influence Function (DIF), a new estimator that explicitly incorporates the constraints into influence estimation. DIF formulates the optimality conditions of constrained learning as a variational inequality (VI) and analyzes how perturbing training data affects this VI. We validate DIF in constrained linear regression and demonstrate that it recovers leave-one-out retraining results, whereas IF and penalty-based IF exhibit significant bias. We further apply DIF to fairness-constrained CNNs, where DIF accurately predicts test loss changes under data removal and aligns closely with actual retraining. Our results establish DIF as an efficient and reliable tool for data attribution in constrained learning.

We introduce a framework that models constrained MDPs subject to trajectory-wise safety constraints. These constraints require that expected future costs remain below zero conditioned to any possible trajectory---not merely in expectation from the initial state. This captures stronger and more realistic safety guarantees, which are crucial in high-stakes applications. We characterize the structure of optimal policies, and show that Markovian policies are in general suboptimal. Moreover, we show that computing approximately-safe optimal policies is NP-hard when the number of constraints can be arbitrarily large. Despite all these challenges, we provide an exact algorithmic characterization of optimal history-dependent (non-Markovian) policies, by exploiting a suitable recursive formulation of the sets of reachable reward-cost values. Then, we employ it to design a polynomial-time approximation algorithm that computes approximately-safe optimal policies by dynamic programming, when assuming a constant number of constraints.

Long-horizon robotic planning often requires satisfying temporally ordered safety and visitation constraints rather than a single goal condition. We study multiple reach-avoid (MRA) tasks, in which a robot must sequentially visit target regions while remaining within corresponding safe sets. Existing approaches either rely on explicit system models or use data-driven planners whose test-time conditioning mechanisms do not scale well to long-horizon temporally structured tasks. We propose a training-free compositional diffusion planning framework for MRA tasks that operates directly on a pre-trained task-agnostic diffusion trajectory prior at test time, without requiring a known dynamics model. Our approach decomposes a global MRA specification into local reach-avoid sub-tasks, composes overlapping short-horizon diffusion priors into a long-horizon generative process through a factor-graph perspective, and enforces each local requirement through projection-based denoising during sampling. The same construction also extends naturally to prefix-suffix tasks through a looped compositional graph. We provide a formal correctness guarantee showing that the stitched trajectory satisfies the target specification. Experiments on long-horizon constrained planning benchmarks show strong execution success, substantially lower planning time than representative guidance-based baselines, and effective transfer to richer dynamics.

Foundation Models (LLMs/VLMs) exhibit strong semantic reasoning capabilities but remain challenged by situated planning in unstructured physical environments. A key limitation is the Semantic-Geometric Gap: while models interpret linguistic and visual intent, they lack explicit grounding in continuous spatial structures, yielding physically infeasible or unsafe plans. We propose Causal-Geo, a neuro-symbolic framework that bridges this gap by integrating LLM reasoning with rigorous geometric planning. Rather than treating physical constraints heuristically, we model the environment as a continuous metric tensor field. LLMs translate high-level semantic intents into potential functions that dynamically warp this manifold via conformal scaling. This casts intent-driven planning as a geodesic optimization problem, solved efficiently via discrete graph search. Experiments across diverse domains—from a macro-scale $12.2 \text{ km}^2$ wetland digital twin to micro-scale indoor robotic navigation—demonstrate that Causal-Geo enables robust zero-shot planning. It significantly outperforms reinforcement learning in sparse-reward settings and prevents the ``physical hallucinations'' common in representative hierarchical LLM planners. Crucially, Causal-Geo acts as a rigorous physical gatekeeper, guaranteeing invariant safety against foundation model variance and demonstrating graceful degradation under contradictory prompts. These results establish continuous geometric grounding as a principled, domain-agnostic pathway toward physically consistent situated agent planning.