NeurIPS 2026 论文列表

Large-scale Ising optimization underlies critical optimization and learning applications, including correlation clustering, MAP inference, and energy-based models. Spectral relaxation methods run in polynomial time but yield solutions with significant optimality gaps while metaheuristics close those gaps but scale poorly to large instances. In particular, spectral methods are inherently single-shot as they solve exactly one eigenvalue problem. We introduce $\textit{Spectral Annealing}$ (SpecAnn), a new spectral optimization approach that transforms traditional spectral methods from single-shot approximations into exploration-based optimization, by sweeping a parametrized normalization path from the raw adjacency to the signed normalized Laplacian, with an $O(n)$ diagonal predictor that warm-starts successive eigensolves and GPU-batched local search refining candidates in parallel. Experiments on general Ising problems demonstrate that SpecAnn achieves competitive to near-optimal solutions depending on instance structure, with runtimes less than 7 minutes for instances of 8.4M variables. SpecAnn delivers up to 83$\times$ speedup over recent GPU-accelerated methods while maintaining superior solution quality, and scales successfully beyond 524K variables where traditional metaheuristics fail.

Forward-backward (FB) representations provide a powerful framework for learning the successor representation (SR) in continuous spaces by enforcing a low-rank factorization. However, a fundamental spectral mismatch often exists between the high-rank transition dynamics of continuous environments and the low-rank bottleneck of the FB architecture, making accurate low-rank representation learning difficult. In this work, we analyze temporal abstraction as a mechanism to mitigate this mismatch. By characterizing the spectral properties of the transition operator, we show that temporal abstraction acts as a low-pass filter that suppresses high-frequency spectral components. This suppression reduces the effective rank of the induced SR while preserving a formal bound on the resulting value function error. Empirically, we show that this alignment is a key factor for stable FB learning, particularly at high discount factors where bootstrapping becomes error-prone. Our results identify temporal abstraction as a principled mechanism for shaping the spectral structure of the underlying MDP and enabling effective long-horizon representations in continuous control.

Predicting transcriptome-wide cellular responses to genetic and biomolecular perturbations is central to functional genomics and therapeutic target discovery. Existing methods assign gene positional encodings derived from arbitrary orderings or static co-expression masks built from unperturbed cells, and cannot capture the functional rewiring induced by perturbations. We present SPEAR, a generative framework built on two complementary positional mechanisms. Spectral positional encoding grounds each gene's position in the geometry of the co-expression network via continuous coordinates derived from the graph Laplacian. Adaptive repositioning then derives each gene's position from its perturbation-conditioned hidden state at every layer, allowing the attention genes exert on one another to reorganize without explicit supervision. Evaluated on genetic, pharmacological, and cytokine perturbation benchmarks, SPEAR demonstrates excellent recovery of differential gene-expression, distributional structure, and perturbation-specific identifiability. SPEAR also captures latent positional relationships that closely map to known transcription factor-target interactions.

Routing systems for large language models, such as MasRouter, RouteLLM, FrugalGPT, and others, match queries to suppliers based on cost-quality tradeoffs. Most prior work optimizes this problem from the demand side, while the supplier-side question of how LLM suppliers should price their services within a routing mechanism has received little formal treatment. We provide the first systematic analysis of this problem. In our setup, the LLM is the priced commodity: supplier organizations set price functions for the services they offer, rather than acting as strategic agents that generate bids per query. We model supplier-side pricing as a sealed-bid first-price reverse auction over a router that allocates each query to one supplier based on cost and quality. This framework applies to any cost-quality routing system rather than to a specific implementation. Using calibrated profiles from 12 open-weight models and MasRouter as a case-study router, we characterize equilibrium behavior. Our main finding is that the Bayesian Nash equilibrium is asymmetric: capability-differentiated suppliers adopt flat, non-discounted strategies, while marginal-quality suppliers compete primarily on price. A mechanism-baseline experiment, where the case-study router is replaced by an analytical rational-decision rule, confirms that this pattern is a property of the auction mechanism rather than an artifact of router training. We further observe that price differentiation can emerge in equilibrium even under capability symmetry, because private-cost types alone produce nontrivial bid functions. The practical implication is that auction-based pricing alone does not discipline specialist rents. Achieving that goal requires additional mechanism elements, such as reserve prices or capability-blind tie-breaking.

Large language models increasingly use external tools such as web search and document retrieval to solve information-intensive tasks. However, multi-hop tool use in complex tasks introduces substantial latency, since the model must repeatedly wait for tool observations before continuing. We study how to accelerate such trajectories without changing the final trajectory the model would have taken without acceleration, assuming access to faster but less reliable speculator tools. We develop a theoretical framework for lossless speculation in multi-hop tool-use settings, characterizing the optimal achievable latency gain. We propose SpecHop, a continuous speculation framework that maintains multiple speculative threads, verifies predicted observations asynchronously as target tool outputs arrive, commits correct branches, and rolls back incorrect ones. This preserves task accuracy while reducing wall-clock latency. We show that SpecHop can approach the oracle latency gain with sufficient active threads. Empirically, we evaluate SpecHop on retrieval-augmented multi-hop tasks and find that its latency gains closely match theoretical predictions, reaching up to 40% latency reduction in some settings.

As language models become autonomous software agents, documentation shifts from explanatory prose to a natural-language behavioral specification for code generation. We study agent-oriented documentation generation, where the objective is not readability but the correctness of code synthesized from documentation alone, turning the task into a black-box search over natural-language specifications evaluated only through the generated code and its execution behavior. Its defining difficulty is output coupling: program entities are behaviorally entangled, so a revision that sharpens the specification of one entity may simultaneously destabilize its dependents, inducing the familiar whack-a-mole failure mode in iterative refinement. We introduce SpecForge, a multi-frontier tree search solution that preserves complementary search frontiers through Pareto state management to avoid premature commitment and escape certain frontier-local optima, performs dependency-constrained bandit selection for callee-before-caller refinement, and uses diversified error-conditioned expansion to remain robust to noisy test feedback. On DevEval+, SpecForge attains the best performance across five backbone models, including a 94.9% solve rate with Claude-4.5-Sonnet and a 25.7% average improvement over the leading baseline. We further demonstrate that the resulting specifications improve downstream performance on both cross-language code translation and new-feature implementation.

Modular networks pursue specialization through learned routers, gates, and load-balancing losses. However, at matched total-parameter budgets, learned routers can underperform equal-weight No-Routing baselines. Is the bottleneck the routing algorithm, or the alignment between training-signal granularity and the target categories? We show that when each training and inference unit carries one coarse category tag, a fixed parameter-free routing scheme (SpecDrop) induces branch-category specialization and matches or exceeds the learned-routing baselines we evaluate at matched parameter budget; when this alignment breaks, the scheme matches the multi-branch No-Routing baseline. SpecDrop assigns each of $K$ branches weight $p_{\mathrm{a}}$ for its category and a small leakage $p_{\mathrm{i}}{>}0$ otherwise, merged through a category-independent fixed denominator that calibrates merged-branch magnitude to single-branch scale, with no learnable routing parameters or auxiliary losses. Category labels are required at inference, drawn from dataset metadata. On vision tasks where each image has one superclass label, SpecDrop reaches $\mathbf{79.23\%}$ on CIFAR-100 with ResNet-110, outperforming dense by $+4.75$, and $\mathbf{79.89\%}$ on ImageNet-1K with Vision Transformer ViT-S/16, outperforming the matched-supervision No-Routing baseline with a shared expert by $+6.53$. SpecDrop reaches the highest top-1 among the multi-branch routing baselines we evaluate at this parameter budget (Soft MoE and Mod-Squad on ImageNet). On NLP tasks where training units span multiple categories, SpecDrop matches the multi-branch No-Routing baseline on both SlimPajama-6B language modeling with a 30M Transformer and SuperNI instruction tuning over Llama-3.2-1B with LoRA. Furthermore, SpecDrop matches or outperforms multi-branch routing baselines including Demix and LoRAMoE, and is statistically tied with HydraLoRA. Per-branch pruning sensitivity reveals four specialization regimes ranked by category clarity: strongest on ImageNet-1K, strong on CIFAR-100, weakening on SlimPajama, and anti-aligned on SuperNI LoRA. Granularity alignment, not algorithm choice, localizes when routing helps. Code: https://anonymous.4open.science/r/C30862.

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.