NeurIPS 2026 论文列表

Sparse attention improves LLM inference efficiency by selecting a subset of key–value (KV) entries, but at the cost of potential accuracy degradation. In particular, omitting critical KV entries can induce substantial errors in model outputs. Existing methods typically operate under fixed or adaptive token budgets and provide empirical robustness or partial theoretical guarantees, yet they do not ensure zero false negatives across decoding steps, particularly since the set of relevant tokens is both query- and step-dependent. Our empirical observations confirm that missing even one critical key can lead to sharp error spikes, especially in long-output reasoning tasks where the set of important tokens varies throughout decoding. This observation motivates the need for indexing methods that dynamically adapt to these variations across decoding steps while guaranteeing a full recall of the relevant keys above a certain threshold. We address this challenge by reformulating sparse attention as the computational geometry problem of halfspace range searching. However, existing range searching data structures are not suitable for modern LLM inference due to their computational and implementation overheads. To overcome this, we introduce Louver, a novel index structure tailored for efficient KV cache retrieval. Louver (i) guarantees zero false negatives with respect to a specified threshold in both theory and practice, (ii) is lightweight to integrate into existing LLM inference pipelines, and (iii) incorporates hardware-aware optimizations for both CPU and GPU executions. Our experiments demonstrate that Louver outperforms prior sparse attention methods in both accuracy and runtime, and is faster than highly optimized dense implementations such as FlashAttention. These results highlight that recall guarantees are a critical and overlooked dimension of sparse attention, and open a new direction for building theoretically grounded, efficient KV cache indices.

Recent work has revealed a link between self-attention mechanisms in transformers and test-time kernel regression via the Nadaraya-Watson estimator, with standard softmax attention corresponding to a Gaussian kernel. However, a kernel-theoretic understanding of sparse attention mechanisms is currently missing. In this paper, we establish a formal correspondence between sparse attention and compact (bounded support) kernels. We show that normalized ReLU and sparsemax attention arise from Epanechnikov kernel regression under fixed and adaptive normalizations, respectively. More generally, we demonstrate that widely used kernels in nonparametric density estimation---including Epanechnikov, biweight, and triweight---correspond to $\alpha$-entmax attention with $\alpha = 1 + \frac{1}{n}$ for $n \in \mathbb{N}$, while the softmax/Gaussian relationship emerges in the limit $n \to \infty$. This unified perspective explains how sparsity naturally emerges from kernel design and provides principled alternatives to heuristic top-$k$ attention and other associative memory mechanisms. Experiments with a kernel-regression-based variant of transformers---Memory Mosaics---show that kernel-based sparse attention achieves competitive performance on language modeling, in-context learning, and length generalization tasks, offering a principled framework for designing attention mechanisms.

Domain generalised semantic segmentation (DGSS) has recently benefited from combining multiple foundation models, such as vision-language and vision foundation models, to leverage their diverse representations for generalisation. Existing multi-model approaches share a common design choice: cross-model fusion is restricted to depth-aligned layers, implicitly assuming that mutually beneficial information resides at the same depth across models. However, foundation models pretrained under different objectives may develop distinct representation hierarchies, making the optimality of depth-aligned fusion questionable. Moreover, we observe that the foundation models have different depth-wise domain sensitivity. Motivated by these observations, we propose a Sparse All-Layer Connector (SALC) that enables each layer to access information from preceding layers of another model. As the number of accessible layers grows with depth, dense aggregation may hurt generalisation. SALC therefore learns to adaptively select a sparse subset of informative layers. We further introduce a candidate dropout regularisation that strengthens sparsity and encourages SALC to explore diverse layers, leading to more robust selection. Across four foundation model combinations and three DGSS evaluation settings, the proposed design demonstrates stronger generalisation than conventional depth-aligned fusion. Code will be public upon acceptance.

In recent years, open-source efforts like Senorita-2M have propelled video editing toward natural language instruction. However, current publicly available datasets predominantly focus on local editing or style transfer, which largely preserve the original scene structure and are easier to scale. In contrast, *Background Replacement*, a task central to creative applications such as film production and advertising, requires synthesizing entirely new, temporally consistent scenes while maintaining accurate foreground-background interactions, making large-scale data generation significantly more challenging. Consequently, this complex task remains largely underexplored due to a scarcity of high-quality training data. This gap is evident in poorly performing state-of-the-art models, *e.g.,* Kiwi-Edit, because the primary open-source dataset that contains this task, *i.e.,* OpenVE-3M, frequently produces static, unnatural backgrounds. In this paper, we trace this quality degradation to *a lack of precise background guidance* during data synthesis. Accordingly, we design a scalable pipeline that generates foreground and background guidance in a decoupled manner with strict quality filtering. Building on this pipeline, we introduce *Sparkle*, a dataset of ~140K video pairs spanning five common background-change themes, alongside *Sparkle-Bench*, the largest evaluation benchmark tailored for background replacement to date. Experiments demonstrate that our dataset and the model trained on it achieve substantially better performance than all existing baselines on both OpenVE-Bench and Sparkle-Bench. Our proposed dataset, benchmark, and model are fully open-sourced at https://showlab.github.io/Sparkle/.

Sparse attention reduces compute and memory bandwidth for long-context LLM inference. However, two key challenges remain: (1) KV cache capacity still grows with sequence length, and offloading to CPU memory introduces a PCIe transfer bottleneck; (2) the sparse selection step itself retains $O(T^2)$ complexity and can dominate attention cost at long contexts. We propose SparDA, a decoupled sparse attention architecture that introduces a fourth per-layer projection, the Forecast, alongside Query, Key, and Value. The Forecast predicts the KV blocks needed by the next layer, enabling lookahead selection that overlaps CPU-to-GPU prefetch with current-layer execution. Because Forecast is decoupled from the attention query, our GQA implementation uses one Forecast head per GQA group, reducing selection overhead versus the original multi-head selector. SparDA adds $<$0.5\% parameters and trains only the Forecast projections by matching the original selector's attention distribution. On two sparse-pretrained 8B models, SparDA matches or slightly improves accuracy and delivers up to 1.25$\times$ prefill speedup and 1.7$\times$ decode speedup over the sparse-attention offload baseline. By enabling larger feasible batch sizes on a single GPU, SparDA further reaches up to 5.3$\times$ higher decode throughput than the non-offload sparse baseline.

Object detection in high-resolution wide (HRW) shots, where a single image can span gigapixel resolutions and kilometre-scale fields of view, suffers from extreme foreground sparsity, dramatically varying foreground density from sparse to crowded scenes, and object clusters whose spatial extent ranges from dozens to thousands of pixels within the same dataset. State-of-the-art sparse vision transformers for gigapixel detection select a fixed top-k fraction of windows by hand-crafted variance scores, which over-promote textured but object-free background such as foliage and patterned facades, cannot adapt the keep ratio to the wide range of crowd density, and confine each kept window to a 7x7 receptive field that is far smaller than the spatial extent of many real-world object clusters. We propose SpanFormer, a sparse vision transformer that broadens the computational span at three complementary granularities: (i) Prototype Routing replaces variance with learnable foreground/background prototypes regularised by a balance constraint that prevents prototype collapse, widening the semantic span of the scoring criterion; (ii) Dynamic Top-k predicts a per-image keep ratio with a lightweight selector, making the compute span elastic so that crowded scenes receive proportionally more compute while near-empty scenes are skipped; (iii) Cluster Memory Attention performs union-find clustering over the kept windows by joint cosine similarity and Chebyshev spatial radius and augments each window's K and V with cross-window memory drawn from its cluster, extending the attention span beyond the local window with all projection parameters shared with the local branch and therefore no added projection cost. On the PANDA gigapixel benchmark, SpanFormer improves AP50 from 78.0% to 80.3% over the SparseFormer baseline while reducing backbone FLOPs by over 75%.

Inorganic crystals are periodic, highly symmetric arrangements of atoms in three-dimensional space. Their structures are constrained by the symmetry operations of a crystallographic \emph{space group} and restricted to lie in specific affine subspaces known as \emph{Wyckoff positions}. The frequency an atom appears in the crystal and its rough positioning are determined by its Wyckoff positions. Most generative models that predict atomic coordinates overlook these symmetry constraints, leading to unrealistically high populations of proposed crystals exhibiting limited symmetry. We introduce Space Group Conditional Flow Matching (SGFM), a novel generative framework that samples significantly closer to the target population of highly symmetric, stable crystals. We achieve this by conditioning the entire generation process on a given space group and set of Wyckoff positions; specifically, we define a conditionally symmetric noise distribution and a group-conditioned, equivariant, parametric vector field that restricts the motion of atoms to their initial Wyckoff position. Our form of group-conditioned equivariance is achieved using an efficient reformulation of \emph{group averaging} tailored for symmetric crystals. It reduces the computational overhead of symmetrization to a negligible level. SGFM achieves state-of-the-art performance in \textit{De Novo Generation} on the MP-$20$ benchmark.

Despite remarkable progress in text-to-image generation, current Diffusion Transformers (DiTs) inherently struggle with learning intricate visual content, such as accurate multilingual scene text rendering and novel visual concepts. This limitation stems from the inherent contradiction between vague semantic guidance provided by text and the objects of accurate reconstruction during diffusion training. To address this bottleneck, we propose SpaG-DiT, a novel spatial grounding training framework. SpaG-DiT directly injects explicit spatial priors into the DiTs before the attention module via Contextual Diagonal Position Encoding (CDPE), which dynamically modulates spatial coordinates without destroying the inherent sequential structure of the linguistic input. Furthermore, we introduce VLM Grounding Guidance (VLM-GG) as an automated pipeline to extract implicit spatial priors from pre-trained Vision-Language Models, eliminating human annotation costs. To evaluate the grounding ability, we establish two new datasets: SpaG-DiT-MultiLingual for non-Latin/Chinese text rendering and SpaG-DiT-Creature for new concept learning. Extensive experiments demonstrate that SpaG-DiT achieves superior training efficiency and significantly outperforms vanilla self-finetuning on the above two tasks and the widely adopted GenEval benchmark. These results validate the plug-and-play nature of SpaG-DiT and its potential to enhance DiT training processes. Code, model, and data will be released.

Vision Transformers are increasingly applied to data defined on the sphere, particularly in physics, meteorology, and related scientific domains. Position embeddings provide the spatial information that attention itself does not encode, making their design central to the expressive power of Transformers. However, most existing position embedding schemes are designed for Cartesian grids and therefore do not naturally handle longitude periodicity, polar singularities, or geodesic relations on spherical domains. This mismatch limits the ability of standard attention to model spherical geometry without specialized architectural modifications. We propose Spherical Reflection Position Embedding (SpRePE), a drop-in position embedding scheme for Vision Transformers on spherical data. SpRePE encodes each absolute spherical position by applying Householder reflections to query and key representations. Although each token is encoded only from its own absolute coordinates, the resulting attention inner products induce an explicit spherical relative-position term with a clear geometric interpretation. This formulation injects sphere-aware relative geometric information into standard attention without constructing pairwise attention-bias matrices, introducing task-specific modules, or modifying the backbone architecture. It also avoids the quadratic overhead of relative position biases and preserves the same asymptotic overhead as RoPE. We evaluate SpRePE on spherical image classification, panoramic depth estimation, and global weather forecasting. Across these tasks, SpRePE achieves competitive performance compared with strong position embedding baselines, with particularly clear gains in settings where spherical geometry is important.

Large language models (LLMs) increasingly answer queries by citing web sources, but existing evaluations emphasize the final answer rather than evidence quality. We introduce SourceBench, a benchmark for measuring the quality of cited web sources across 100 real-world queries spanning informational, factual, argumentative, social, and shopping intents. SourceBench uses an eight-metric framework covering content quality (content relevance, factual accuracy, objectivity) and page-level signals (e.g., freshness, authority/accountability, clarity), and includes a human-labeled dataset with a calibrated LLM-based evaluator that matches expert judgments closely. We evaluate eight LLMs, Google Search, and three AI search tools over 3996 cited sources using SourceBench and conduct further experiments to understand the evaluation results. Overall, our work reveals four key new insights that can guide future research in the direction of GenAI and web search.

Longitudinal radiology report generation increasingly conditions on prior images and reports. This history is clinically valuable, but it creates a source-validity failure mode: a generator can carry prior-only findings into the current report. Weintroduce source-causal robustness, a stress-test and control framework that holds the current chest X-ray fixed while intervening on historical context. On a full eligible MIMIC-CXR longitudinal study (18,716 pairs; 93,580 generations across five source conditions), historical context consistently trades fewer missed findings for more unsupported positives. Matched wrong-history, the key negative control, increases proxy-defined false positives by +0.366 per report while reducing false negatives by −0.129; random wrong-history yields an even larger false positive stress signal (+0.465 FP/report). We propose the Source-Causal Finding Router (SCFR), a source-validity controller trained with within-evaluation subject exclusion. Across three held-out evaluations, SCFR repairs matched wrong-history false-positive inflation by −0.343, −0.550, and −0.457 per report, passes Holm corrected primary testing at the bootstrap resolution floor (Holm-adjusted p ≤ 0.0012), and satisfies fixed current-only parity margins. Cross-generator stress panels with RadInfer and Libra, together with ReXPref-Prior, RadGraph2, Chest ImaGenome, ablations, and case review, support the mechanism. These results establish a protocol-defined state-of-the-art source-causal robustness/control result for longitudinal radiology report generation under matched wrong-history stress tests.

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

We study optimal design of $\varepsilon$-locally differentially private mechanisms for binary hypothesis testing. Each observation is drawn from one of two known distributions $P_0,P_1$ on a finite alphabet of size $k$, privatized by a mechanism $Q$, and then used to infer which distribution generated the data. We measure testing utility using an $f$-divergence—including total variation, KL, and hockey-stick divergences—between the two induced output distributions. Previous work established structural properties of optimal mechanisms, but only yielded exponential-time algorithms. We prove a sharp structure: for every $\varepsilon$ and every $f$-divergence objective, after sorting the alphabet by likelihood ratio, there exists an optimal mechanism that partitions the sorted alphabet into contiguous blocks and applies randomized response to the block label. We call this class Sort–Partition–Randomize (SPR). This characterization yields an exact dynamic program that computes an optimal mechanism in $O(k^3)$ time, and more generally in $O(\ell k^2)$ time with an $\ell$-output budget. Our results make it possible to efficiently compute and characterize the exact optimum across the full privacy range, beyond asymptotic privacy regimes.

Open-weight Vision-Language Models (VLMs) score 85--94\% on existing spatial benchmarks (BLINK Spatial, What's Up CLEVR) yet collapse to chance on simple geometric questions when object, scene, and texture priors are stripped away. We introduce and open-source Sophon, a procedurally generated diagnostic of paired colored point-cloud stimuli across three coordinate systems (1D linear, 2D Cartesian, 2D polar) and four question types (binary, categorical, comparative, quantitative). Across four open architectures spanning every major projector design (LLaVA-NeXT, LLaVA-OneVision, Qwen2.5-VL, Idefics3), accuracy clusters at 47--52\% while frontier models (Opus 4.6, Gemini 2.5 Pro, GPT-5.4) clear 77--83\% and humans reach 84--94\%. We trace the open-weight failure end-to-end. The vision tower works: encoder probes recover Sophon spatial direction at 80--97\%. The language tower's reasoning circuit works: a text-only control restores $+40$ pp, and probes preserve the spatial signal through every LLM decoder layer at 80--86\%. Per-layer attention attribution localizes visual integration to mid-stack layers. Yet at the readout, the model elevates the correct answer-set tokens but selects among them at chance. Fine-tuning experiments rule out the unembedding as the mechanism. By moving the unembedding layer through the residual stream, we observe the emergence of a small but discriminative contrast at late-stack residual layers in fine-tuned models, which in practice converts the random selection into a confident one more likely to be correct. However, ablation experiments locate the mechanism upstream: training only the upstream layers with the late stack frozen recovers the full $+29$ pp gain, while training only the late stack captures less than a third. The late-stack contrast is the downstream readout of upstream changes. No layer in either base or fine-tuned models shows geometric alignment between the spatial signal and the unembedding's vocabulary axes, suggesting that 7B-class VLMs have the weights to reason spatially but lack the residual-stream pathways to convert that reasoning into answers.

Multiplicative motor and observation noise, along with internal noise corrupting computation, are central features of the sensorimotor system in biological and robotic agents. Yet, analytical solutions for stochastic optimal control are largely restricted to additive noise models and neglect internal noise. Here, we consider the problem of finding optimal control and filter laws for partially observable stochastic linear systems under quadratic costs with multiplicative control and observation noise, as well as internal noise. We provide an efficient, analytically derived coordinate-descent algorithm that computes mutually optimal linear control and filter laws by reformulating the problem as a constrained optimization. Our method provably guarantees monotonic decrease of the expected cost and convergence to a critical point, and overcomes the suboptimality and incompleteness of prior analytical approaches. Compared to state-of-the-art numerical methods, it achieves orders-of-magnitude computational speedups. Our solution also proves instrumental in revealing novel internal-noise-dependent, task-structured control strategies in a redundant arm control task.

Exact solution of hard combinatorial optimization problems often relies on strong convex relaxations, but solving these relaxations repeatedly inside a branch-and-bound algorithm can be prohibitively expensive. Hence, we consider this challenge for \new{Max-Cut problem} (Max-Cut), where branch and bound commonly uses semidefinite programming (SDP) relaxations to bound subproblems. We propose a Max-Cut-specific \new{graph neural network} that serves as a principled, lightweight neural proxy for these SDP solvers and can be plugged directly into an exact branch-and-bound framework. The proposed architecture has update steps of complexity $\mathcal{O}(n^2 + ne)$, and predicts both primal- and dual-feasible SDP solutions. The primal SDP solutions yield feasible Max-Cut solutions via the Goemans--Williamson algorithm. In addition, it is trained in a self-supervised fashion without requiring solved SDP relaxations as labels. Empirically, we show that our architecture can substantially reduce the cost of bounding in exact Max-Cut solving by up to $10.6 \times$ compared with using the state-of-the-art SDP solver Mosek. Our work highlights the potential of learned, validity-preserving surrogates for accelerating exact optimization over structured convex relaxations.

Large language models (LLMs) can solve every intermediate step of a multi-step math problem on its own and still fail the full problem, even when given a roadmap of the steps and all of their answers. We introduce OracleLadder, a diagnostic evaluation that locates where LLM math reasoning fails by giving the model increasing levels of oracle help. For each problem, a teacher model writes a fixed roadmap of intermediate sub-goals (milestones), and a deterministic symbolic verifier grades every answer. Testing the model with no help, with the roadmap, with the roadmap plus the milestone answers, and on each milestone alone sorts each failure into one of five reasoning gaps. On 354 NuminaMath problems and six models from 8B to 671B parameters (Qwen3, gpt-oss, Llama 3.3, DeepSeek-V3.1), the largest gap for every model is the composition gap, a stricter form of the compositionality gap. It covers 33-48% of problems, and 24-37% after removing problems that an LLM review flags as grading errors. Accuracy and milestone-help recovery rank the two strongest models differently, and two RLVR runs with similar accuracy gains move problems differently. The roadmap effect replicates on MATH500 and AIME 2024/25, per-problem recovery agrees for 83-87% of problems under an independent second teacher, and the help ladder carries over to code generation. We release the data, roadmaps, prompts, and code at https://github.com/slark-prime/OracleLadder.

PDE foundation models (PDE-FMs) promise general-purpose surrogate simulation, yet deploying a pretrained model to a new physical regime inevitably introduces distribution mismatch, demanding task-specific post-training. The dominant approach, supervised fine-tuning (SFT), is fundamentally off-policy: the model trains on pre-generated states but is evaluated autoregressively on its own. In chaotic regimes, this mismatch is catastrophic as per-step errors compound exponentially along the Lyapunov spectrum, and exact pointwise trajectory matching beyond the predictability horizon becomes an ill-posed training signal. To resolve this, we introduce **Solver-as-Teacher (SaT)**, an on-policy post-training framework for PDE-FMs. During training, the student rolls out autoregressively; a numerical solver branches multi-step correction targets from each student-visited state; and the student is updated against these solver corrections, learning to correct its own rollout dynamics. We instantiate SaT in a unified post-training suite with SFT, physics-informed temporal alignment, and learned-teacher on-policy distillation. Across seven 2D/3D PDE benchmarks and six pretrained PDE-FMs, SaT variants achieve the lowest 50-step rollout RMSE in 23 of 24 in-distribution model--task pairs. The best SaT variant reduces RMSE over SFT up to 90.0\%, and SaT gives the lowest RMSE on all seven OOD parameter-shift benchmarks.

Decomposition-based Programming-by-example (PBE) scales performance by splitting tasks into subtasks that a learned synthesizer solves: a decomposer predicts intermediate subgoals, and a synthesizer generates programs conditioned on them. Current approaches train the decomposer to imitate ground-truth (GT) subgoals, implicitly treating decomposition quality as intrinsic to the task. We challenge this assumption: for bounded solvers with fixed inductive biases, GT decompositions reflect the annotator’s factorization choices – not the solver’s search dynamics. A decomposer trained to match GT decompositions may therefore propose subgoals that are logically valid yet intractable for the solver. We propose Solver-Aware Decomposition (SAD), a training framework that retains supervised training on GT subgoals as a structural scaffold, while additionally optimizing the decomposer via direct feedback from a frozen synthesizer. Subgoals are rewarded based on the synthesizer’s loss on the target program – a signal of subtask difficulty that encourages decompositions the solver can act on. Our experiments reveal an accuracy paradox: higher agreement with GT decompositions does not improve synthesis success – even though the synthesizer was trained on the very same GT data the decomposer is optimized to mimic. SAD instead learns decompositions that trade GT alignment for solver tractability, yielding consistent gains in synthesis and end-to-end task accuracy across two PBE domains. Moreover, SAD solves tasks that a GT decomposition oracle fails – empirical evidence that GT decompositions are not universally optimal for bounded solvers, and that decomposition quality is solver-relative, not intrinsic.