NeurIPS 2026 Papers

Software requirements are usually written in natural language, which is essential for human communication but insufficient as a target for machine-checked correctness. While natural-language descriptions can state intended functionality, verification requires formal specifications with explicit types, relations, quantifiers, guards, witnesses, and edge cases. To bridge this divide, we study the Formal Specification Synthesis task: given a natural-language programming requirement and fixed formal signatures, synthesize a proof-assistant specification for the intended input-output relation. This task is difficult for two primary reasons. First, a large representation gap separates informal natural language from the rigorous structures needed by a proof assistant. Second, generated formal specifications are notoriously hard to evaluate, as proving full equivalence between specifications is often too complex to serve as routine feedback. To address these intertwined challenges, we propose SpecBridge, a reconstruction-guided formalization framework. At its core, SpecBridge introduces a Natural-Language Formalization Plan (NLFP), a semi-structured, readable intermediate representation that captures key formalization choices before decoding to a target specification language. Through reconstruction-guided pattern mining, SpecBridge learns these NLFPs by reconstructing formal specifications to discover reusable patterns, ultimately transferring them to improve natural-language task generation. Furthermore, to tackle the evaluation bottleneck, we introduce a multi-layer evaluation protocol for formal-specification correctness. This protocol utilizes LLM Specification Alignment as an LLM-based judge, alongside Test-Driven Computable Validation and Test-Driven Proof Validation, which approximate "running" testcases on formal specifications by translating propositions into executable pre/post checks and proving testcase obligations in Lean. In our experiments, SpecBridge outperforms the few-shot + CoT baseline by 6.1% on LLM Specification Alignment, 15.2% on Computable Validation Pass Rate, and 28.4% on Proof Validation Pass Rate. These results demonstrate that the NLFP bridge and our multi-layer evaluation protocol make formal specification synthesis significantly more reliable.

Speculative decoding accelerates LLM inference by drafting a tree of candidate continuations and verifying it in one target forward. Existing drafters fall into two camps with opposite weaknesses. Autoregressive drafters such as EAGLE-3 preserve dependence along each draft path but call the drafter once per tree depth, making drafting a non-trivial share of per-iteration latency. Parallel drafters cut drafter calls by predicting multiple future positions in one forward, but each position is predicted without seeing the others, producing paths the verifier rejects. In this paper, we propose SpecBlock, a block-iterative drafter that combines path dependence with cheap drafting. Each drafter forward produces $K$ dependent positions and we call this a block. The draft tree grows through repeated block expansions. Two mechanisms explicitly carry path dependence to keep later draft positions accurate. Within each block, a layer-wise shift carries the previous position's hidden state into every decoder layer. Across blocks, each new block can start from any position of the previous block, inheriting its hidden state to extend the path. To spend verifier budget where acceptance is likely, a co-trained rank head replaces the fixed top-$k$ tree by allocating per-position branching during drafting. To avoid training the drafter on prefixes it never produces at inference, a valid-prefix mask drops the loss at later positions once an earlier one is wrong. Beyond static drafting, a cost-aware bandit at deployment uses free verifier feedback to update the drafter selectively, only when the expected throughput gain exceeds the update cost. Experiments show that SpecBlock improves mean speedup by $8$--$13\%$ over EAGLE-3 at $44$--$52\%$ of its drafting cost, and cost-aware adaptation extends this lead to $11$--$19\%$.

Recent video generative models can produce photorealistic short clips, but struggle with long-horizon generation under dynamic camera control, often suffering from viewpoint drift, geometric inconsistency, and error accumulation. We propose Joint Appearance-Geometry Diffusion Transformer (JAG), a spatially-grounded causal video diffusion model that explicitly integrates 3D perception for long and consistent video generation. It adopts a novel dual-branch causal architecture that jointly models visual appearance and scene geometry. Building upon this formulation, we introduce Self Geometry Forcing, a geometry-aware distillation scheme that conditions current generation on self-predicted geometric structures as persistent long-term memory and imposes self-verified geometric rewards on intermediate rollouts, effectively mitigating error accumulation over long horizons. Extensive experiments show that JAG can generate long videos with superior coherent appearance and geometry at constant per-frame computation, improving long-horizon controllability, geometric consistency, and visual fidelity over previous state-of-the-art methods.

Recent 3D indoor scene generation methods often produce layouts with limited spatial feasibility, where pathways are blocked and objects are difficult to access or use, restricting their applicability in virtual reality and embodied environments. To address this challenge, this paper presents a new paradigm for 3D indoor scene generation that explicitly models interaction feasibility through a carefully designed geometric abstraction, termed the Interaction-Oriented Human Proxy (IOHP). The IOHP serves as a compact yet spatially expressive representation for human interaction occupancy, and can be directly inferred by large language models without task-specific training. Building on IOHP, we formulate layout optimization as a unified objective that resolves geometric conflicts between the proxy and scene elements, while using the proxy as a bridge to preserve functional relationships among furniture, thereby improving overall usability and accessibility. Benefiting from this design, our method eliminates reliance on data-driven human preference learning and complex layout-planning pipelines, producing accessible, usable, and spatially coherent scenes in an efficient and stable manner. Extensive experiments demonstrate that our approach significantly improves layout quality and spatial plausibility, highlighting the role of human-centric interaction modeling in 3D scene generation.

Recent online reinforcement learning has substantially improved image editing quality. However, existing Flow-GRPO-style methods usually rely on a single whole-image reward, which makes fine-grained editing optimization difficult. We observe that a key obstacle in image editing is this spatial uniformity assumption: a whole-image reward cannot distinguish how different spatial regions contribute to image quality. To address this issue, we propose **SpatialFlow-GRPO**, a training framework that makes spatial reward feedback more fine-grained. The framework converts region-aware rewards into semantic-region-level optimization signals and aligns region advantages with the corresponding latent positions during policy updates. We also train a region-aware reward model, **SFReward**, construct **SFReward-14K** with region-annotated editing samples, and introduce **MultiEditBench** to evaluate multi-region editing ability. On OmniGen2 and FLUX.2-klein-4B, SpatialFlow-GRPO outperforms Flow-GRPO on GEdit-Bench, ImgEdit-Bench, and MultiEditBench. The results show that SpatialFlow-GRPO can turn local feedback into more accurate update signals and improve editing quality.

Spatial reasoning, the ability to determine where objects are, how they relate, and how they move in 3D, remains a fundamental challenge for vision-language models (VLMs). Tool-augmented agents attempt to address this by augmenting VLMs with specialist perception modules, yet their effectiveness is bounded by the *action interface* through which those tools are invoked. In this work, we study how the design of this interface shapes the agent's capacity for open-ended spatial reasoning. Existing spatial agents either employ single-pass code execution, which commits to a full analysis strategy before any intermediate result is observed, or rely on a structured tool-call interface that often offers less flexibility for freely composing operations or tailoring the analysis to each task. Both designs offer limited flexibility for open-ended, complex 3D/4D spatial reasoning. We therefore propose **SpatialClaw**, a training-free framework for spatial reasoning that adopts code as the action interface. **SpatialClaw** maintains a stateful Python kernel pre-loaded with input frames and a suite of perception and geometry primitives, letting a VLM-backed agent write one executable cell per step conditioned on all prior outputs, enabling the agent to flexibly compose and manipulate perception results and adapt its analysis to both intermediate text and visual observations and the demands of each problem. Evaluated across **20 spatial reasoning benchmarks** spanning a broad range of static and dynamic 3D/4D spatial reasoning tasks, **SpatialClaw** achieves 59.9% average accuracy, outperforming the recent spatial agent by **+13.6 points**, with consistent gains across six VLM backbones from two model families *without any benchmark- or model-specific adaptation*.

Multimodal large language models (MLLMs) excel at visual interpretation but fail on spatial reasoning tasks that humans solve reliably. Existing benchmarks evaluate these models as black boxes, limiting their ability to identify the underlying causes of lower performance: when a model fails a spatial reasoning task, it remains difficult to ascertain whether the hurdle is perceptual, such as recognizing object boundaries, or cognitive, such as reasoning about occlusion to infer hidden geometry. We introduce Spatial-IQ, a hierarchical diagnostic framework that decomposes object counting in stacked 3D structures into 9 perceptual and cognitive sub-tasks organized by the developmental stages of human spatial cognition, with mental rotation as an additional target probe. Using NVIDIA Isaac Sim, we procedurally generated a diverse dataset of roughly 80,000 stacked 3D structures with per-task ground truth. We evaluate models across three output formats (free-response text, multiple-choice images, and image editing) alongside a human baseline. The Spatial-IQ framework shows that top-performing models often succeed at the target task (object counting) without succeeding on the lower-level sub-tasks intended to support it, and that models differ in how much of these hierarchical chains they preserve, often revealing shortcut behavior that raw target-task accuracy alone would obscure. Finally, we demonstrate that training models with chain-of-thought (CoT) supervision over our hierarchical sub-tasks, combined with reinforcement learning with verifiable rewards, significantly improves both spatial consistency across sub-tasks and target-task accuracy, supporting the value of the proposed decomposition as both a diagnostic tool and a training signal.

Understanding the 3D physical world has emerged as an essential component in vision-language-action models (VLAs), enabling robots to perform several challenging tasks by unifying \textit{spatial} perception, language, and action. Existing approaches typically either rely on explicit 3D inputs, such as depth maps or point clouds, or implicitly inject spatial knowledge into visual representations. However, explicit 3D inputs are often brittle in practice due to sensor noise, hardware heterogeneity, and incomplete depth coverage, while implicit alignment can distort the original 2D visual representation and weaken generic scene understanding. In this paper, we present SPARK-VLA, a simple yet effective framework to allow VLAs to implicitly possess generic 2D and spatial 3D visual comprehension within a unified visual backbone. SPARK-VLA consists of two key components: (1) spatial representation distillation, which transfers 3D understanding from a frozen 3D expert into a LoRA-adapted visual branch by aligning attention responses while preserving the original visual pathway, and (2) a lightweight knowledge router, which selectively forwards action-relevant visual tokens to the language model using routing supervision derived from action-loss gradients. Experiments in both simulation and real-world environments show that SPARK-VLA, with only a 0.5B language backbone and 50M trainable parameters, achieves performance comparable to or better than substantially larger VLAs.

The standard metric LP for correlation clustering has $\Theta(n^2)$ pairwise marginals and $\Theta(n^3)$ triangle inequalities, while dense pairwise supervision is often the primary bottleneck in large relational pipelines. We separate three sparsification questions that are often treated together: preserving the objective of every integral clustering, rounding from a sparse set of LP marginals, and clustering when the signed weighted input itself is only sparsely observed. First, we prove that the VC dimension of the signed-edge disagreement class induced by all clusterings of $n$ vertices is exactly $n-1$, so weighted edge sampling yields additive $\varepsilon$-coresets of size $\tilde O(n/\varepsilon^2)$ with optimal $n$-dependence. Second, we introduce *Sparse-LP-Pivot*, which imputes missing LP marginals from triangle witnesses, and analyze it at two levels: a universal but coarse perturbation bound for every Lipschitz LP-PIVOT rule, and a sharper sparse-rounding theorem under an explicit weighted influence-stability certificate. For pseudometric-weighted CC, this gives a $10/3$ exact-marginal baseline and an unconditional coarse sparse-marginal bound; a sharp same-edge bound governed by $\overline{\Gamma}_w$ follows conditionally if the rounding rule is additionally proved to satisfy edge-weight-dominated influence stability. Third, we show that uniform marginal sampling has a triangle-witness threshold at $m=\Theta(n^{3/2})$ for typical pairs, while $m=O(n^{3/2}\sqrt{\log n})$ is sufficient for all pairs with high probability. Finally, in the stricter sparse edge-observation model, we prove an $\Omega(n^{3/2})$ lower bound on the expected approximation ratio from $o(n)$ uniformly sampled edges for general weighted instances. Experiments illustrate the witness transition and the proposed diagnostics; the formal guarantees are stated independently of those empirical observations.

Data assimilation (DA) for systems governed by partial differential equations (PDE) aims to reconstruct full spatiotemporal fields from sparse high-fidelity (HF) observations while respecting physical constraints. While full-grid low-fidelity (LF) simulations provide informative priors in multi-fidelity settings, recovering an HF field consistent with both sparse observations and the governing PDE typically requires per-instance test-time optimization, which becomes a major bottleneck in time-critical applications. To alleviate this, amortized reconstruction using generative models has recently been proposed; however, such approaches rely on full-field HF supervision during training, which is often impractical in real-world settings. From a more realistic perspective, we propose the *Physics-Informed Conditional Schrödinger Bridge* (**PICSB**), which transports an informative LF prior toward an auxiliary-energy-defined, observation-conditioned HF endpoint law without any additional inference-time guidance. To enable learning without HF endpoints, **PICSB** employs an iterative surrogate-endpoint refresh scheme, and directly incorporates PDE residuals into the training objective while enforcing observations via hard conditioning throughout sampling. Experiments on fluid PDE benchmarks demonstrate that **PICSB** enables extremely fast spatiotemporal field reconstruction while achieving strong accuracy under sparse HF supervision.

Diffusion models have shown remarkable success across a wide range of generative tasks. However, they often suffer from spatially inconsistent generation, arguably due to excessive correlations learned by the model. This can produce samples that are locally plausible but globally inconsistent. We propose a principled method to mitigate this issue. Our method, sparsely supervised diffusion (SSD), is a simple yet effective masking framework that can be implemented with only a few lines of code. We analytically show that SSD fundamentally alters diffusion model training by modifying the spectrum of the data covariance and that it suppresses correlations in the data covariance matrix. Experiments show that our method more accurately approximates the underlying population score function, reduces memorization on small datasets, and promotes the use of essential contextual information during generation. Moreover, even when up to 98\% of pixels are masked, it achieves competitive FID scores across a range of datasets and, importantly, avoids the training instability commonly observed on small datasets.

Blind deconvolution is a classical problem arising in many signal processing and machine learning applications, where one aims to recover an unknown kernel and an unknown signal from their convolution. Since both the kernel and the signal are unknown, the problem is intrinsically ill-posed, and meaningful recovery is possible only under suitable structural assumptions. In this paper, we study sparse blind deconvolution, where the kernel is $s_h$-sparse and the signal admits an $s_x$-sparse representation in a known dictionary. Although sparsity is a natural and practically relevant prior, its interaction with the bilinear observation model creates substantial challenges for both computation and analysis. To address these challenges, we propose Thresholded Wirtinger Flow (ThWF), a simple and scalable iterative algorithm equipped with a sparse spectral initialization. For noiseless observations, we prove that the proposed initialization achieves exact support recovery with sample complexity $M \gtrsim s_h^2+s_x^2$, up to logarithmic factors. Building on this initialization, we establish what is, to the best of our knowledge, the first algorithmic convergence guarantee for sparse blind deconvolution: ThWF converges linearly to the ground truth, up to the inherent scaling ambiguity, provided that $M \gtrsim s_h+s_x$ up to logarithmic factors. Our analysis further extends to noisy measurements, showing that ThWF is robust and contracts linearly up to a statistical error under a bounded noise level. Experiments on synthetic data and real-world image deblurring tasks corroborate the predicted linear convergence and phase transition behavior, and demonstrate the restoration performance of the proposed method.

Why must vision-language navigation be bound to detailed and verbose language instructions? While such details ease decision-making, they fundamentally contradict the goal for navigation in the real-world. Ideally, agents should possess the autonomy to navigate in unknown environments guided solely by simple and high-level intents. Realizing this ambition introduces a formidable challenge: Beyond-the-View Navigation (BVN), where agents must locate unseen targets without step-by-step guidance. Existing large language model (LLM)-based methods, though adept at following dense instructions, often suffer from short-sighted behaviors due to their reliance on short-horizon supervision. Simply extending the supervision horizon, however, destabilizes LLM training. In this work, we identify that video generation models (VGM) inherently benefit from long-horizon supervision to align with language instructions, rendering them uniquely suitable for BVN tasks. Capitalizing on this insight, we propose applying VGM as the main backbone to generate actions for the first time in this field. Yet, the prohibitive latency for generating videos spanning tens of seconds makes real-world deployment impractical. To bridge this gap, we propose SparseVideoNav, achieving sub-second trajectory inference guided by a generated sparse future spanning a 20-second horizon. This yields a remarkable 27$\times$ speed-up compared to the unoptimized counterpart. Extensive real-world zero-shot experiments demonstrate that SparseVideoNav achieves 2.5$\times$ the success rate of state-of-the-art LLM baselines on BVN tasks and marks the first realization of such capability in challenging night scenes.

A central limitation of modern machine learning systems is the lack of formal certificates guaranteeing their behavior beyond empirical, sample-based evaluation. Sum-of-squares (SOS) methods provide such guarantees by certifying polynomial inequalities over continuous domains via semidefinite programming (SDP). While prior work has introduced SDP layers as differentiable components in neural networks, their scalability is limited by two key bottlenecks, that we are fixing in this paper: (i) failure to preserve sparsity from the forward SOS program in the backward pass, leading to inefficient training, and (ii) loss of certificate structure during differentiation, preventing its use in learning. We propose a differentiable sparse SOS layer whose backward pass mirrors the sparse structure of the forward solve, reusing local blocks, overlaps, and sparse constraints. The method avoids building dense certificates for scalar losses and computes gradients using the same sparse structure when certificate details are required. Experiments show that this enables practical SOS-based layers within learning systems, reducing backward computation time by one to three orders of magnitude while preserving certification quality. We evaluate on sparse polynomial certification, pendulum control, combinatorial relaxations, robotics projection, oscillator chains, and pose graph synchronization. Results demonstrate that sparse certificate objectives can be effectively integrated into learning pipelines when the backward pass respects the verifier's structure.

Token-based world models enable fine-grained latent planning, but iterative search inside the predictor is dominated by the number of spatial tokens processed during rollout. We introduce COSTGRAD, a training-free, goal-conditioned selector that ranks spatial tokens by the gradient norm of the planning cost with respect to each input token. By deriving importance from the downstream control objective, COSTGRAD targets tokens that matter for planning rather than merely for prediction. On AdaLN-conditioned predictors at $50\%$ sparsity, COSTGRAD matches or exceeds full-token planning on three of four continuous-control benchmarks, while giving a measured $2.6\times$ wall-clock speedup per environment planning step. The sparsity dividend can be combined with reduced CEM search, yielding a $\sim5\times$ total speedup while still exceeding the full-token baseline. We also identify an architecture-dependent failure mode: in a matched AdaLN-vs-concat comparison, concat maintains comparable full-token performance but pure COSTGRAD loses its advantage over random selection. This failure tracks action-pathway drift under selected token removal: AdaLN largely preserves how actions affect kept tokens, whereas concat perturbs the action-conditioned computation. Mixing in random anchors partially recovers COSTGRAD's advantage on some matched-concat checkpoints, suggesting selector--architecture compatibility as a design axis for sparse world-model planning.

Koopman autoencoders (KAEs) seek a higher-dimensional latent representation in which nonlinear dynamics evolve linearly. However, many interesting systems have multiple basins of attraction, and both theoretical and empirical work has shown these multibasin systems cannot generally admit a single finite-dimensional global Koopman embedding under standard assumptions. We posit that encoders with a sparsity-inducing objective encouraging few active latent coefficients will provide latent supports as an inspectable basin-modeling principle for Koopman autoencoders. We use these encoders producing sparse latents in training Sparse Koopman Autoencoders (SKAEs) without basin labels or other regime annotations, and treat the learned latent supports as model-produced regime variables after training. Across a range of procedurally generated multibasin systems and chaotic flows, we show that SKAEs have superior forecasting performance compared to dense-latent KAEs. We also perform a mechanistic study that shows latent supports produced by SKAEs are both essential for the quality of the representation and useful for identifying basins on held-out basin interior states, whereas dense-latent KAEs collapse to an uninformative single family. These results identify sparse latents and their corresponding supports as label-free, interpretable regime variables for Koopman learning in nonlinear systems with multiple local dynamical laws.

Language models are increasingly used in text generation, decision support, and automated interaction, where their behavior must be controlled in a localized, reversible, and selective way. Existing methods either update shared parameters or constrain generation through external interfaces, leaving open whether frozen models contain compact internal control. We introduce sparse internal control, a framework for steering target behavior by applying inference-time interventions to a small set of internal model nodes. The framework formulates control through local target controllability, where candidate site–direction pairs are characterized by their behavioral effects under target, preservation, and energy constraints. This yields two complementary selectors: Driver-OMP, which selects nodes that sparsely reconstruct a desired behavioral displacement, and Coverage-Driver, which favors nodes whose effects cover prompts stably. We further propose a six-axis control-evaluation protocol measuring reachability, signed reversal, dose response, feedback controllability, off-target preservation, and held-out reuse. Across IOI, MMLU MCQA, and sentiment steering on models from GPT-2 small to Qwen3-4B, sparse driver sets act as executable actuators: they steer target behavior, respond monotonically to dose, support closed-loop control, and preserve unrelated next-token behavior. On refusal steering, the same protocol exposes a boundary case that passes all evaluated axes except strict reachability. Held-out reuse separates prompt-specific controls requiring refitted strengths from population-level controls that transfer as frozen interventions. These results show that model control can move beyond output-side steering: mechanistic internal variables can be selected, certified, and reused as localized control handles for frozen language models.

LLM chain-of-thought reasoning improves with additional compute, but standard 2 inference scaling [Wei et al., 2022, Wang et al., 2022, Snell et al., 2024, Brown 3 et al., 2024] treats all steps equally. We ask: which step in a reasoning chain benefits 4 most from extra computation? We make three layered contributions, each scoped 5 explicitly. (I) Measurement. We define expansion utility Uk as the marginal 6 gain in correctness probability from resampling from step k onward, measured via 7 a step-oracle sweep. Across nine model families (8B–123B), seven benchmarks 8 (math, science, code), and 6,500 chains, every one of the 41 healthy (model, bench) 9 cells shows positive oracle gap at 10% step budget (95% Wilson CI [0.914, 1.000]; 10 mean +22.0 pp, range +1 to +48 pp). (II) Structure. Per-step utility is sparse 11 (97.6% of cells: Gini ≥ 0.80); Gini and mean oracle gap are tightly anti-correlated (Pearson r = −0.913, p = 9.5 × 10−17 12 ). A resample-stability simulation and 13 a segmentation-rule sensitivity check (Appendix J) bound the headline against 14 noise and rule-choice confounders. (III) Routing proof-of-concept. A cross15 model router trained with a within-example listwise loss [Cao et al., 2007] and a 16 learned depth prior, combined at inference with a bench-conditional depth mask 17 and a confidence gate, recovers 5-seed-averaged gated GR@10% = +0.149 (95% 18 bootstrap CI [+0.085, +0.217]) of the cross-model oracle gap at matched step19 budget, with no architectural change to the underlying model. We frame this as 20 proof the framework is actionable cross-model, not as deployment-ready scaling; 21 matched-token comparison to self-consistency / best-of-N requires a separate 22 generation campaign and is left to follow-up (§7). Methodological observation. 23 Within-example pointwise top-k BCE under cross-model pooling produces a high24 AUC discriminator (AUC@10 = 0.70) that selects the wrong steps (gated GR 25 = −0.15); the listwise loss is shift-invariant to per-(model, bench) utility scale and 26 removes this inversion.

Linear attention models allow a fixed state size and a fixed amount of compute per token. However, due to their limited state size, linear attention models fall behind in long-context recall compared to softmax-attention-based transformer architectures. Increasing the state size of linear attention improves recall performance but at the cost of higher FLOPs. In this work, we introduce Sparse Delta Memory (SDM), an architecture that scales the hidden state of gated linear RNNs to orders of magnitude higher capacity using a sparse addressing scheme. SDM extends the Gated DeltaNet architecture by replacing the dense key-value outer product with sparse reads and writes to a large explicit memory. We show that, under an isoFLOP constraint and with an identical number of parameters, a higher state memory capacity significantly improves performance on in-context learning and long-context retrieval tasks. Moreover, by learning the initial state of the SDM memory and therefore using it as a parametric memory, we show that the model further improves on a wide range of common-knowledge and reasoning tasks.