NeurIPS 2026 Papers

Geospatial reasoning requires solving image-grounded problems over complex object relationships and scene structures. However, developing this capability is hindered by the cost of annotating a vast and combinatorial question space. We propose GeoX, a self-play framework that acquires spatial logic through executable programs and verifiable rewards in the absence of large-scale human-curated data. Given a satellite or aerial image, our framework employs a single multimodal policy to alternate between proposing spatial problems with executable programs and solving them under three reasoning modes of abduction, deduction, and induction, using a segmentation tool and standard computational libraries. Program execution turns each program into a reward that jointly optimizes the two roles via reinforcement learning. GeoX consistently improves its base VLMs by up to 5.5 points on average, matching or exceeding conventional baselines trained on millions of curated samples. Alongside the framework, we release a benchmark for geospatial reasoning curated from self-play generations.

Building on SODA 2026 work Kearns et al. (2026), we study learning in directed acyclic graphs in which each agent observes only a subset of the input coordinates and may use the predictions of its parents as additional features. In the finite-sample protocol, the message sent along each edge is the agent's prediction vector on a shared sample, so the communication cost is linear in the sample size $m$. In this paper we study this model under communication constraints. First, we revisit the finite-sample analysis of the full-message protocol. We identify a gap in the finite-sample proof of Kearns et al. (2026) and develop a different argument that establishes a finite-sample population-risk guarantee along paths satisfying deterministic $M$-coverage. Second, we introduce a shared-sketch protocol in which each agent sends a $k$-dimensional linear sketch of its prediction vector instead of the full $m$-dimensional message, where $k\ll m$. We analyze this protocol through a reduction to least squares on the compressed sample together with an oblivious subspace embedding argument. The resulting bound separates statistics from communication: the statistical term is still governed by the original sample size $m$, while the additional error due to compression is controlled by the sketch dimension $k$. For Gaussian sketches, we obtain an explicit high-probability population-risk bound, showing that row subsampling is not the only possible communication-statistics tradeoff for networked information aggregation.

Discovery of novel materials for physical memory is essential for superior memory systems enabling AI hardware scaling. Among them, ferroelectrics hold promise for highly scalable DRAM. Yet their discovery remains driven largely by human intuition and exhaustive database screening. We present Ferrogen, a generative pipeline for the targeted discovery of novel ferroelectric materials for memory by fine-tuning the diffusion-based crystal structure generator Mattergen on ferroelectric-relevant properties. To enable property-conditioned generation, we construct a ML-labeled dataset using a suite of fast machine learning estimators, including a novel two-stage ensemble polarization predictor, dramatically reducing reliance on high-throughput Density Field Theory (DFT) during training and screening. The base Mattergen model is fine-tuned via lightweight adapter layers conditioned on polarization, switching energy, and metal-probability embeddings, with classifier-free guidance enabling targeted generation of candidates with high polarization, low but finite switching barriers, and insulating character. Generated candidates are screened by the same ML estimators and validated through rigorous DFT calculations, including structural relaxation, band gap verification, and Berry phase polarization computation. Against the ML screens, Ferrogen achieves a roughly $80 \times$ improvement in search efficiency over exhaustive database search. The screened candidates are then finally validated using DFT and made publicly available as a database of theoretically confirmed novel ferroelectrics. The pipeline is readily extensible to other functional material classes, establishing generative models as a powerful paradigm for accelerating electronic materials discovery for high performance memory.

Federating a LGN is challenging because each gate is parameterised by a distribution over 16 Boolean operations, so averaging parameters across clients does not correspond to averaging the underlying functions. Under non-IID data, such parameter-space merging collapses to near-chance accuracy. Boolean Feature Selection (BFS) avoids this issue by selecting discrete Boolean functions rather than averaging parameters. We propose Federated Boolean Feature Selection (FBFS), which extends BFS to LGNs by treating hardened last-layer gates as candidate Boolean features and aggregating per-class, per-gate sufficient statistics across clients. Clients share only firing aggregates computed on a held-out split, allowing the server to reconstruct discriminative scores, defined as the gap between a gate's mean firing for a class and for the remaining classes, without accessing raw data. This procedure is equivalent to centralized BFS on the union of client data. We further introduce a diversity-regularized variant of FBFS that encourages complementary feature selection across gates. Empirically, FBFS is the only data-free method we evaluate whose performance remains stable under extreme non-IID settings, outperforming parameter-space merging and other baselines by large margins. It maintains high accuracy across a wide range of heterogeneity levels and scales to large architectures. In addition, FBFS enables efficient deployment: the resulting models compile to hardware-efficient logic representations with substantially fewer post-synthesis cells than ensemble-based alternatives while remaining bit-exact with their software counterparts.

The expressive limitations of message-passing Graph Neural Networks (GNNs) have motivated a wide range of more powerful graph learning architectures. We advocate Deep Homomorphism Networks (DHNs) as a model particularly well-suited for learning over relational databases, due to their close connection to important fragments of SQL such as conjunctive queries. We study the precise expressive power of DHNs by relating them to various natural fragments and extensions of first-order logic (FO). For DHNs with max, sum, and mean aggregations, we establish connections to the unary negation fragment (UNFO) and to the extensions of UNFO with counting quantifiers and with ratio quantifiers. We further relate sum-aggregation DHNs to the unary quantifier alternation fragment of FO and to an extension of FO with expressive counting. Through the classical correspondence between FO and SQL, these results also illuminate the relation between DHNs and SQL. They also enable us to study the decidability of two fundamental static analysis problems for DHNs, the emptiness problem and the subsumption problem. Finally, we confirm through experiments that the established differences in expressive power are reflected in the performance on suitable prediction tasks.

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.

A generated plausible future mathematical claim must satisfy two constraints: it should follow the direction of prior work and respect the formal dependencies that constrain the validly of the claim. Existing approaches typically model only one of these sources, producing claims that are either weakly grounded or insufficiently motivated. We introduce grounded future mathematical generation, the task of generating a plausible future theorem-like claim for an anchor paper, using two complementary sources of context: its scientific citation graph ,and its aligned formal theorem dependency graph. To address this setting, we propose COMPOSE, a dual-graph framework that combines scientific citation context with formal mathematical structure to condition a language model. To support this setting, we construct a dataset of 108K paired scientific-formal graphs from arXiv and Mathlib, together with a benchmark of 47K future papers from 2024-2025. Experiments show that COMPOSE outperforms strong baselines on retrieval to real future papers and achieves the best overall performance under LLM-judge evaluation, producing more grounded and mathematically richer outputs. These results show that future mathematical generation benefits from combining scientific context with formal structure.

Online bipartite matching, where agents are known in advance but items arrive sequentially and must be irrevocably assigned, is fundamental to problems ranging from ride-sharing to online advertising. When agents belong to classes such as demographic groups or geographic regions, fairness demands equitable treatment across these groups. Recent work introduced class envy-freeness (CEF), a natural extension of the classical fair division notion: an algorithm is $\alpha$-CEF if each class receives value at least an $\alpha$ fraction of what it could extract from any other class's bundle. However, all known algorithms achieving constant-factor CEF guarantees attain utilitarian social welfare (total matching value) of at most $\frac{1}{2}$ times the optimum, far below the $1-\frac{1}{e} \approx 0.632$ achievable without fairness constraints. We resolve the open question of whether fairness necessitates this efficiency loss, by introducing threshold-based algorithms parameterized by $\gamma \in [0,1]$ that equalize allocations across classes until threshold $\gamma$, then maximize efficiency. For divisible matching, this yields simultaneous $(1-e^{-\gamma})$-CEF and $(1 - \frac{e^{\gamma-1}}{\gamma+1})$-USW guarantees; for indivisible matching, $\frac{\gamma}{2}$-CEF with the same USW. Setting $\gamma > 0$ produces the first algorithms beating $\frac{1}{2}$-USW while maintaining constant CEF. We complement this with a novel upper bound construction, proving no non-wasteful $\alpha$-CEF algorithm can exceed $\frac{1 +\alpha - e^{\alpha-1}}{1+\alpha}$-USW and correcting prior bounds that were vacuous for $\alpha < 0.58$. Our upper bound nearly matches our algorithms' performance, giving the first substantive characterization of the price of fairness in online class matching.

We study stochastic linear bandits under a natural combination of batching and communication constraints: the time horizon is partitioned into batches of equal size $B$, and during each batch the learner sends $B$ requested arm pulls to an agent, who then observes the corresponding $B$ rewards and responds with a single bit of feedback to the learner. For each batch, the learner specifies the 1-bit quantization rule the agent uses, which may depend on all previously received bits but not on any past rewards directly. This setting addresses a significant yet unexplored ``middle ground'' between previous models having per-round quantization only $\textit{or}$ total bit budgets only. We establish a minimax lower bound showing that $\Omega(B\min \lbrace d,\log\lvert \mathcal{A} \rvert \rbrace)$ regret is unavoidable due to the 1‑bit communication bottleneck, even in the absence of noise. Combined with standard statistical limits, this yields a general lower bound of $\widetilde{\Omega}(B\min\lbrace d,\log\lvert \mathcal{A} \rvert \rbrace + \sqrt{dT \min \lbrace d,\log\lvert \mathcal{A} \rvert\rbrace })$. We develop two phased‑elimination algorithms based on $G$-optimal designs and 1‑bit mean estimation. The first achieves $\widetilde{O}(dB + d\sqrt{T})$ regret, matching the lower bound up to logarithmic factors when $\lvert \mathcal{A} \rvert = \exp(\Omega(d))$, and the second incorporates a safe‑arm identification and warm‑start procedure to obtain $\widetilde{O}(B\log\lvert \mathcal{A} \rvert + d^{3/2}\sqrt{B} + \sqrt{dT\log\lvert \mathcal{A} \rvert})$ regret, which is near‑optimal in broad scaling regimes of $(\lvert \mathcal{A} \rvert, B, d,T)$. Together, our results demonstrate that a single bit of feedback per batch suffices to preserve nearly order‑optimal regret across a wide range of settings, even in the case of large batch sizes such as $\Theta(\sqrt{T})$.

Piecewise-linear (PWL) optimization problems arise in many mixed-integer programming (MIP) optimization applications, including portfolio optimization, workforce scheduling, and resource allocation. But solving them to global optimality remains computationally expensive because branch-and-bound repeatedly solves LP relaxation subproblems. Existing solvers are largely CPU-centric, leaving the scalability of modern GPUs underutilized. Few prior GPU-accelerated branch-and-bound either targets neural network which is not suitable for general PWL optimization, or accelerates only auxiliary subroutines such as strong branching heuristics within CPU-centric MIP solvers. To bridge this gap, we propose $\textbf{\texttt{B$^{3}$-PWL}}$, a GPU-centric batched branch-and-bound framework for piecewise-linear optimization with Special Ordered Set of type 2 (SOS2) constraints. Our method solves batches of LP relaxation subproblems concurrently on the GPU using a first-order primal-dual solver, enabled by a specialized batched block-tiled sparse matrix kernel. To complement bound computation, we further introduce a unified feasibility search module that combines an SOS2 repair primal heuristic with a batched feasibility pump to rapidly obtain feasible incumbents and improve pruning efficiency. On a benchmark of 43 PWL-MIP instances, $\textbf{\texttt{B$^{3}$-PWL}}$ achieves a 9.25$\times$ geometric-mean speedup over NVIDIA cuOpt while reaching high-quality feasible incumbents on every tested instance, demonstrating the potential of first-order LP methods as the central engine of GPU-accelerated branch-and-bound.

We introduce COMONet (Convex-Concave and Monotonicity-Constrained Neural Networks), a unified architecture for enforcing variable-wise shape constraints in neural networks. COMONet addresses the limitations of prior methods that either support only a restricted subset of monotonicity and curvature constraints or enforce them through penalties without strict architectural guarantees. Our framework assigns each input variable to one of eight shape regimes, covering monotonicity, convexity, concavity, and their combinations. This is achieved through a partially connected architecture that routes each variable to specialized units equipped with sign-constrained weights and constraint-preserving activation functions. We also provide theoretical guarantees showing that COMONet satisfies the prescribed variable-wise shape constraints by construction. Experiments on synthetic and real-world datasets demonstrate that COMONet achieves competitive performance and remains robust to noise while preserving its architectural guarantees. COMONet thus offers a practical and principled framework for incorporating domain knowledge as shape constraints into neural network training.