NeurIPS 2026 Papers

Learning control policies for complex, long-horizon tasks is a central challenge in autonomous systems. Signal Temporal Logic (STL) offers an expressive language for specifying such tasks, but its non-Markovian nature and inherent sparse reward make it hard for standard Reinforcement Learning (RL) to solve. Prior RL approaches focus only on limited STL fragments or use robustness scores as sparse rewards. Our new method TGPO (Temporal Grounded Policy Optimization) decomposes STL into timed subgoals and invariant constraints and tackles the problem in a hierarchical fashion. Its high-level module proposes time allocations for subgoals, and the low-level time-conditioned policy learns to achieve the sequenced subgoals using a dense, stage-wise reward. In inference, we use the critic to efficiently sample time allocations and select the most promising assignment for the policy to rollout. We evaluate in five environments, from low-dimensional navigation to manipulation, drone, and quadrupedal locomotion, and TGPO significantly outperforms baselines (especially for high-dimensional and long-horizon cases), with 31.6% higher success rate compared to the best method.

Geometry problem solving is a canonical testbed for machine intelligence, requiring systems to interpret diagrams, ground symbolic constraints, and perform rigorous deduction. Yet current approaches expose a persistent gap between seeing and proving: multimodal large language models can flexibly inspect diagrams but may hallucinate unsupported relations, while symbolic solvers provide checkable derivations but are brittle to incomplete or misgrounded formalization. We introduce SynGeo, a state-centric framework for synergizing seeing and proving in geometry problem solving by making the geometric representation revisable during inference. SynGeo first constructs a predicate state from diagram--text evidence and tests it with symbolic reasoning. When proof search fails or stagnates, symbolic diagnostics guide image-grounded revisiting, repairing solver-incompatible predicates before another deductive attempt. When the symbolic route remains unresolved, a complementary MLLM branch provides an image-grounded reasoning path from the problem evidence. On Geometry3K and PGPS9K, SynGeo achieves state-of-the-art performance across both Choice and Completion settings. With GPT-4o as the backbone, it reaches \(90.2\%\) accuracy in both settings on Geometry3K, and 90.1% Choice accuracy and 88.6% Completion accuracy on PGPS9K. Ablations show that both feedback-guided revisiting and complementary reasoning are necessary, supporting a broader view of geometry problem solving as an adaptive loop between what a system sees, what it formalizes, and what it proves.

Deploying deep learning models across heterogeneous hardware requires each model to jointly satisfy a bundle of coupled constraints on accuracy, latency, memory, and energy. Maintaining a specialist for every deployment scenario is operationally prohibitive, so practitioners need a small portfolio of $K$ models that collectively covers many deployment profiles. Existing hardware-aware NAS and Pareto-based approaches target marginal objectives and do not directly address this downstream decision. We formalize it as Deployment Portfolio Selection over a fixed pre-measured archive, where a profile is covered only when a single retained model simultaneously satisfies its entire constraint bundle. The induced objective is weighted maximum coverage, which is NP-hard but monotone submodular, so greedy selection inherits a $(1-1/e)$ guarantee, and sample-then-optimize admits a finite-sample bound. Across an 18-family sweep on HW-NAS-Bench, direct bundled-coverage optimization is most valuable in the small-portfolio, low-coverability regime: gains concentrate on the hardest profiles, are most robust at $K = 3$, and persist under three non-uniform demand models. Complementary analyses of remeasurement noise, runtime, and compact feasibility storage clarify when bundled coverage is preferable to scalarized or Pareto-based alternatives.

The linear quadratic regulator (LQR) is a canonical optimal control problem where recent work has established global convergence guarantees for model-free policy gradient methods. However, designing model-free algorithms that enforce hard constraints throughout learning remains an open challenge. Existing approaches are either partially model-based, enforce soft constraints through Lagrangian relaxations, or project pretrained policies onto the constraint set, sacrificing hard constraint satisfaction or convergence guarantees of the underlying algorithms. In this work, we develop principled model-free policy gradient methods for LQR problems with hard constraints. Our key idea is to parameterize the policy class using a truncated stochastic policy so that hard constraints are satisfied by construction, then perform policy optimization entirely within this class. We prove that the resulting LQR objective over the proposed truncated policy class satisfies a weak gradient-dominance property in both the undiscounted and discounted settings. We leverage this property to develop model-free policy-gradient algorithms that maintain zero violation of the encoded hard constraints at each iteration, and converge to an approximately globally optimal policy within the proposed safe policy class.

Offline safe reinforcement learning aims to maximize cumulative reward while satisfying safety constraints using only static datasets. Recent approaches leverage latent variable models to capture the behavior policy distribution, enabling efficient policy extraction under limited data. However, existing latent-space methods typically rely on soft constraints, which allow constraint violations in expectation and may be unsuitable for safety-critical settings. In addition, these methods often employ Advantage-Weighted Regression (AWR) for policy extraction, which exhibits exponential sensitivity to out-of-distribution critic bias, leading to high variance in the policy gradient estimate. To address these limitations, we propose Feasibility-Optimized Conditional Actor Learning (FOCAL). FOCAL enforces state-wise hard safety constraints by integrating reachability-based feasibility constraints directly into the Conditional Variational Autoencoder. To overcome the instability associated with AWR, we introduce a feasibility-partitioned, behavior-regularized objective that utilizes stable, first-order gradients to structurally decouple reward maximization in feasible regions from constraint violation minimization in infeasible regions. Finally, an adaptive test-time inference dynamically modulates latent sampling variance based on state-wise feasibility to ensure safe policy execution under out-of-distribution states. Theoretical analysis demonstrates that FOCAL circumvents the exponential variance in policy gradient estimates associated with AWR under critic errors, while providing formal bounds on policy deviation from the behavioral dataset. Empirically, on the DSRL benchmark, FOCAL satisfies safety constraints while achieving competitive or higher returns compared to state-of-the-art methods, all while maintaining efficient single-step inference.

Linear Temporal Logic (LTL) provides a rigorous framework for specifying long-horizon robotic tasks, yet existing approaches face a trade-off: model-based synthesis relies on accurate labeled transition systems, whereas learning-based methods often require online interaction, task-specific rewards, or specification-conditioned training. We study LTL-specified robotic planning and execution in a stricter offline, model-free setting, where the agent is given only fixed, task-agnostic trajectory fragments, with no dynamics model, task demonstrations, or online data collection. To address this setting, we propose SAGAS, a framework that combines the compositionality of symbolic synthesis with the data-driven reachability structure learned from offline trajectories. SAGAS first learns a reusable latent reachability graph and a frozen goal-conditioned executor from fragmented offline data. For each new LTL formula, it performs task-time semantic graph augmentation to ground state-defined propositions on the learned graph, and applies B\"uchi product search to synthesize a cost-aware accepting prefix--suffix waypoint plan executed by the frozen executor. By shifting formula-specific reasoning from policy learning to test-time graph augmentation and symbolic search, SAGAS enables zero-shot generalization to unseen, data-supported LTL specifications without task-specific reward design, policy retraining, or online interaction. Experiments on LTL task suites constructed from OGBench locomotion domains show that this design produces executable and cost-efficient prefix--suffix behaviors for diverse unseen LTL tasks from fragmented offline data.

Runtime monitoring of autonomous systems traditionally relies on mapping continuous sensor observations to discrete logical propositions defined over low-dimensional state variables. This abstraction breaks down in perception-driven settings, where such mappings require additional learned modules that are often computationally expensive, brittle, and semantically misaligned. In this work, we propose Embedding Temporal Logic (ETL), a temporal logic that performs monitoring directly in learned embedding spaces. ETL defines predicates through distances between observed embeddings and target embeddings derived from reference observations. This formulation allows specifications to capture high-level perceptual concepts, such as similarity to visual goals or avoidance of semantic regions, that are difficult or impossible to express using traditional predicates. By composing these predicates with temporal operators, ETL naturally expresses temporally extended and sequential perceptual behaviors. We introduce ETL monitors for evaluating specifications over bounded embedding traces, along with a conformal calibration procedure that provides reliable and safety-oriented predicate evaluation. We evaluate our approach across multiple manipulation environments to show that ETL achieves strong empirical agreement with ground-truth semantics, including accurate monitoring of temporally composed behaviors.

In learnable logic gate networks, each neuron implements a $k$-input Boolean function. The dominant setting $k{=}2$ was chosen for tractability. We ask: when does wider fan-in help? At fixed parameter budget, each gate costs $2^k$ parameters, so increasing $k$ exponentially reduces width. Combined with the depth--fan-in bound $L \geq \lceil \log_k d \rceil$, this partitions tasks into two regimes: width-dominated (image classification), where more gates beat richer gates, and degree-dominated (parity, arithmetic), where $k{>}2$ is necessary. Our main finding is that representability does not imply learnability: at the regime boundary, the selection mechanism determines training success at identical architecture, and the optimal mechanism inverts between regimes. We formalize this via a Jacobian analysis: the softmax mechanism's positive-semidefinite (PSD) structure gives basin attraction absent from sigmoid. We train multilinear coefficients with exact gradients and Möbius-transform snapping (zero deployment error), and validate on 28 tasks and 5 real-world datasets across multiple selection mechanisms.

Clustering and vector quantization are core primitives for representation learning and large-scale retrieval, yet widely used methods often produce clusters or codewords of highly uneven quality, especially in noisy or heterogeneous data. In this paper, we propose a distortion-constrained optimal transport (DCOT) framework that explicitly enforces per-cluster bounds on the average assignment distortion, defined as the expected distance between data points and their assigned representatives, ensuring more consistent and reliable representations. Our formulation couples an optimal transport assignment objective with cluster-level distortion constraints to control cluster quality. To solve this constrained problem, we develop an efficient alternating optimization algorithm that iteratively updates transport plans, representatives (codewords), and dual variables. We further provide theoretical guarantees including entropic consistency, coordinate descent, and sublinear convergence. Importantly, DCOT serves as a plug-in assignment module that can be seamlessly integrated into a wide range of vector quantization methods. Replacing the assignment step with DCOT consistently improves reconstruction quality across diverse architectures and training settings, demonstrating strong robustness and general applicability.

Ensuring high returns while providing strong safety guarantees in offline imitation learning (IL) is a fundamental challenge: existing approaches either rely on explicitly specified cost functions, which are difficult to design for complex real-world safety constraints, or require expert demonstrations that are both safe and high-performing, which are often too costly to collect. We introduce *dual-expert imitation learning*, which leverages two complementary data sources: (i) safety-compliant demonstrations that faithfully follow safety guidelines but may be suboptimal, and (ii) performance-oriented demonstrations that achieve high returns but may violate safety guidelines. To address this problem, we propose DexDICE (**D**ual-**ex**pert offline imitation learning via stationary **DI**stribution **C**orrection **E**stimation). Instead of conventional distribution constraints, DexDICE combines DICE-style offline learning with safe support constraints, enabling agents to exploit high-return behaviors while remaining within safety-compliant regions. We evaluate DexDICE on a re-curated DSRL benchmark and validate it on a real-world mobile-robot navigation task trained directly from human teleoperation demonstrations, where it significantly outperforms offline IL baselines and remains robust to data scarcity and quality degradation.

Multilayer perceptron (MLP)-based model compression often overlooks two distinct sources of error: the hypothesis gap and the capacity gap. The hypothesis gap arises from approximation error induced by selecting a student hypothesis class that is mismatched to the teacher function, while the capacity gap captures the additional error introduced by enforcing a limited parameter budget within the chosen class. We show that Kolmogorov–Arnold Networks (KANs) can reduce the hypothesis gap for smooth low-dimensional target functions. Furthermore, width and depth constraints in KANs allow within-family compression to be formulated as a convex projection problem that directly targets the capacity gap. Building on this formulation, we derive projection-based algorithms for width and depth reduction, as well as a function transfer method that maps a trained MLP teacher into a compact KAN student. These are unified in the Gap-aware Projections via KANs (ProjKAN) framework, which integrates the error decomposition, theoretical guarantees, and compression algorithms into a single methodology. Empirically, in regimes where pruning and standard knowledge distillation degrade sharply, ProjKAN achieves improved accuracy–size tradeoffs, reduced train–test gaps, and greater robustness in data-scarce settings.

Differentiable logic gate networks, which operate using only logic gates, have recently attracted attention as an efficient alternative to conventional neural networks. However, despite their efficiency, the scaling behavior of logic gate networks remains underexplored. By contrast, scaling model capacity is a central design principle in deep neural networks and typically leads to improved performance. This discrepancy raises a key question: Can similar scaling benefits also be achieved in logic gate networks? In this work, we focus on width as a primary scaling axis and conduct a systematic analysis of its behavior in logic gate networks. We observe that naive width scaling often introduces redundancy among logic kernels, limiting the effective use of additional kernels and leading to performance saturation. To address this limitation, we propose a dynamic logic kernel framework that reorganizes kernel utilization by promoting specialization across kernel groups. This enables the network to better utilize increased width via input-dependent kernel routing, while ensuring that both routing and computation are implemented entirely with gate-level Boolean operations at inference time. We further find that kernel redundancy is most pronounced at the first gate level, motivating an early-stage dynamic logic kernel strategy that concentrates adaptation at this level. Experimental results demonstrate that our approach improves kernel utilization and increases kernel diversity, leading to higher accuracy with improved parameter efficiency.

Blind source separation (BSS) is a natural framework for studying how latent causes may be recovered from sensory mixtures, but deriving online and biologically plausible algorithms for structured (i.e., constrained to known domains) and potentially correlated sources remains challenging. Recent work has derived neural networks for BSS from maximization of an entropy measure, yet its online implementations involve complex and nonlocal recurrent dynamics. Motivated by this perspective, we propose Predictive Entropy Maximization, which achieves competitive performance in BSS, using only local weight updates. The method employs a close approximation of an entropy measure, yielding an objective function with easily interpretable components. Minimizing this objective leads to a predictive neural architecture in which feedforward synapses follow an error-driven rule (that can be realized through dendritic mechanisms), lateral inhibitory connections are learned with local Hebbian plasticity, and source-domain constraints are enforced through simple output nonlinearities. We derive explicit spectral bounds on the surrogate error, characterizing when the approximation is accurate. Empirically, Predictive Entropy Maximization remains robust under increasing source correlation and observation noise, outperforms biologically plausible algorithms that rely on stronger independence or decorrelation assumptions, and remains competitive with exact determinant- and correlative-information-based baselines. These results show how local plasticity and adaptive lateral inhibition can emerge from maximizing a regularized second-order entropy over structured source domains.

We investigate the approximation capabilities of dense neural networks. While universal approximation theorems establish that sufficiently large architectures can approximate arbitrary continuous functions when there are no restrictions on the weights, we show that dense neural networks do not possess this universality. Our argument is based on a model compression approach, combining the weak regularity lemma with an interpretation of feedforward networks as message passing graph neural networks. We consider ReLU neural networks subject to natural constraints on weights and input and output dimensions, which model a notion of dense connectivity. Within this setting, we demonstrate the existence of Lipschitz continuous functions that cannot be approximated by such networks. This highlights intrinsic limitations of neural networks with dense layers and motivates the use of sparse connectivity as a necessary ingredient for achieving true universality.

We study fixed-confidence best-arm identification under strict 1-bit feedback constraints. At each round, the learner selects an arm and a query set, and receives only a single bit indicating whether the sampled reward belongs to that set. We consider a distribution-free finite-variance setting with arm-wise localization, where direct empirical mean estimation is no longer available and clipping becomes unavoidable. We first formulate a time-uniform 1-bit mean-estimation primitive based on randomized threshold queries and a clipped tail-integral identity. We then embed this primitive into candidate-challenger best-arm identification algorithms. A fixed-clipping algorithm gives a simple anytime $(\epsilon,\delta)$-PAC guarantee, while a phased adaptive-clipping algorithm matches the clipping level to the current resolution and yields a gap-adaptive sample complexity. We also prove a two-arm information-theoretic lower bound showing that the logarithmic penalty caused by finite-variance 1-bit feedback is intrinsic. Consequently, the phased algorithm is optimal in the leading dependence up to lower-order $\log\log$ factors.

Chain-of-Thought reasoning improves the explainability of large language models, yet verifying such reasoning remains difficult when intermediate steps express epistemic uncertainty rather than deterministic entailment. Neuro-symbolic verifiers typically translate reasoning steps into rigid first-order or SMT-style constraints. This forces each proposition into a binary truth regime and creates a Rigidity--Ambiguity Mismatch: uncertainty-marked claims such as may, likely, or suggests are either over-hardened into deterministic assertions or rejected as unverifiable. We propose ProbVeri, a probabilistic soft-logic framework for formal verification under uncertainty. The key idea is to represent uncertainty-marked reasoning steps as weighted soft logical constraints over continuous truth assignments, so that partial evidential support remains expressible. Building on this soft-logic representation, we formulate verification as a contrastive energy minimization problem: a step is considered supported when its natural interpretation has lower verification energy than its negated counterpart under the same evidence, soft rules, and assumption regularization. Probabilistic Soft Logic defines the logical energy through weighted hinge-loss constraints. We introduce a support-grounded assumption penalty that discourages unsupported latent bridge assumptions between context and claim. The resulting energy gap provides a confidence-scored verification signal that separates unsupported steps from weakly but consistently supported inferences. Experiments on ProofWriter, BioASQ, and LegalBench-SARA show that ProbVeri recovers more verified-correct reasoning traces than rigid verifiers while reducing over-acceptance compared with soft-only PSL. These results suggest that uncertainty-aware verification benefits from soft logical formalization and contrastive comparison between natural and negated interpretations.

Learning permutations is fundamental to sorting, ranking, and matching, but existing differentiable methods based on entropy-regularized Sinkhorn produce a single softened solution and collapse under ambiguity. We present PermFlow, a conditional flow matching framework that operates directly on the affine subspace of matrices with unit row and column sums. A closed-form tangent-space projector preserves these constraints exactly along every trajectory, by construction rather than through iterative correction, and a nearest-target coupling routes distinct noisy initializations toward distinct valid permutations. The result is a model that captures multimodal permutation distributions rather than collapsing them to a single mode. On a visual sorting task with blended-digit ambiguity and a symmetric linear assignment problem, PermFlow achieves high accuracy on unambiguous inputs and recovers both valid permutations under ambiguity, where Sinkhorn-based baselines structurally fail.

Decision tree optimization is fundamental to interpretable machine learning, yet most tree learning algorithms are restricted to binary splits. This restriction can produce unnecessarily deep trees when the underlying decision logic is naturally multi-valued. Multiway-split trees address this, but finding sparse yet accurate ones is more challenging, as the number of possible partitions at each node grows combinatorially with the number of feature bins. We introduce SPLINTER (SParse Lookahead for Interpretable N-way Trees by Eliminative Ranking), a dynamic programming and branch-and-bound-based framework that combines efficient candidate generation with pruning bounds to find sparse, accurate multiway-split trees. Our empirical results show that our methods produce trees that achieve higher accuracy at a greater decision sparsity (shorter path lengths) than greedy multiway and near-optimal binary-split tree baselines, while remaining practical to train. We further extend the framework to approximate the Rashomon set of near-optimal multiway-split trees, allowing users to inspect multiple sparse and accurate alternatives.

Detecting frequency trend patterns, such as items with sustained growth or decline, is an important and challenging task in high-speed data streams. State-of-the-art solutions require manual tuning of many coupled parameters, while their bloom filters suffer from high false positive rates. In this paper, we propose NeuTrend, a framework that provides accurate and automatic trend detection with high-performance in-network inference. Our key idea is that a lightweight BRNN can learn to classify incoming items as likely trending or non-trending. Thus, it eliminates unqualified items more accurately than a bloom filter and removes the need for manual parameter tuning. The BRNN uses only XNOR and popcount operations. Thus, it aligns with the strict resource constraints of data-plane switches. NeuTrend further introduces an adaptive detection module. The module uses the BRNN confidence scores to automatically tune the growth and decay thresholds. Extensive experiments on real-world datasets show that the learned filter reduces false positive rates by 23\%-44\% and increases effective detector occupancy from 47\% to 70\%. Hence, NeuTrend improves the overall F1 score by 35\%-68\% over existing solutions, and achieves Tbps-level line-rate processing.