NeurIPS 2026 论文列表

We consider the problem of estimating the Attention mechanism in small space, and prove the existence of coresets for it of nearly optimal size. Specifically, we show that for any set of unit-norm keys and values $(K,V)$ in $R^d$, there exists a subset $(K',V')$ of size at most $O({\sqrt{d} e^{\zeta+o(\zeta)}/\epsilon})$ such that $$ \left\| Attn(q,K,V)- Attn(q,K',V') \right\| \le \epsilon $$ simultaneously for all queries whose norm is bounded by $\zeta$. This outperforms the best known results for this problem. We also offer an improved lower bound showing that $\epsilon$-coresets must have size $\Omega({\sqrt{d} e^{\zeta}/\epsilon})$.

We study stochastic linear bandits with delayed feedback under several delay models and establish near-optimal regret guarantees. Our results identify when delayed linear bandits exhibit the same qualitative behavior as multi-armed bandits (MAB), and when the linear structure creates fundamentally new challenges. Specifically, (1) for *loss-independent delays*, where the delay does not depend on the realized loss (but potentially depends on the arm), we show that delays incur only an additive regret penalty. Under stochastic delays, this penalty scales with the expected delay, while under adversarial delays, it scales with the maximum number of outstanding observations. Notably, both delay penalties are dimension-free, improving upon the state-of-the-art results; (2) for *loss-dependent delays*, we show that linear bandits are substantially harder than MAB: unlike in MAB, we prove matching (up to log factors) upper and lower bounds in linear bandits, whose delay penalty depends on the square root of the dimension. (3) for the *delay-as-payoff model*, a special case of loss-dependent delay, we show that the optimal MAB guarantee, which depends only on the delay of the optimal arm, is also unattainable in linear bandits. Together, these results provide a sharp characterization of how delayed feedback interacts with linear generalization.

We study the adversarial kernel bandit problem, in which the loss at each time step is induced by some bounded (but otherwise arbitrary) element of an RKHS. We propose an exponential-weights algorithm with a regularized importance-weighted estimator and an explicit correction term that controls the estimator's regularization bias. Our main result bounds the regret in terms of a widely-adopted notion of effective dimension that captures the complexity of the kernel. Notably, when the kernel satisfies a polynomial eigendecay condition with exponent $\beta>1$, our regret scales as $T^{(\beta+1) /(2 \beta)}$ up to logarithmic factors. This matches a lower bound from existing work (Chatterji, Pacchiano, and Bartlett, ICML 2019) and strictly improves on the upper bound derived in that work (with dependence $T^{\beta /(2 (\beta-1))}$), while also having the benefit of dropping their rank-one adversary assumption and instead allowing arbitrary RKHS elements at each step.

We study a structured stochastic multi-armed bandit problem in which each decision simultaneously determines the learner's reward and the feedback available for learning. At each round, the learner selects a task and an option. Each task is associated with an unknown parameter that governs its reward, while each option has a known reward function of this parameter and determines how information about that reward is observed. Some options may provide fine-grained feedback at the cost of lower immediate reward, whereas others may yield higher reward but return only coarse feedback. This creates an intrinsic trade-off between reward maximization and information acquisition. We formalize this setting as parametric bandits with action-dependent coarsened feedback. For stationary tasks, we propose ACF-UCB, an optimistic algorithm that constructs task-level confidence sets by aggregating information from all atoms of the option-dependent feedback distributions. For piecewise-stationary tasks, we develop SW-ACF-UCB, a sliding-window variant that adapts to temporal changes. We prove high-probability regret bounds for stationary environments and dynamic regret guarantees for piecewise-stationary environments. We also establish lower bounds showing that the dependence on the number of tasks and the horizon is unavoidable, while methods that ignore the shared parametric structure suffer substantially larger regret.

Last-iterate convergence of learning dynamics in games has attracted significant recent attention. In two-player zero-sum games with bandit feedback, where only the loss of the selected action pair is observed, Fiegel et al. [2025] show a separation between average-iterate and last-iterate convergence in duality gap: while the optimal $t^{-\frac{1}{2}}$ rate after $t$ rounds is achievable for the former via standard no-regret algorithms, the latter cannot converge faster than $t^{-\frac{1}{3}}$ in expectation or $t^{-\frac{1}{4}}$ with high probability. However, in many practical settings (such as preference learning), the players observe not only their loss but also the opponent’s action. This raises a natural question: can such additional information enable faster last-iterate convergence? We answer this question affirmatively, showing that $t^{-\frac{1}{2}}$ last-iterate convergence is achievable with high probability in this setting, via an efficient algorithm that updates its strategy infrequently by solving an estimated log-barrier-regularized game. We identify fundamental obstacles preventing standard analysis for multi-armed bandits (the single-player case) from generalizing to games, and develop a novel analysis to overcome them. Experiments confirm that our algorithm indeed converges faster than naive baselines and prior methods that do not exploit opponent-action feedback. Finally, we note that our results also improve those for dueling bandits, a special case with skew-symmetric game matrices.

We study the decoupled multi-armed bandit problem, where the player selects one arm to exploit (incurring its loss) and one arm to explore (observing its loss) at each round. We propose two algorithms: D-Exp3-Ada, based on Exp3 with an AdaGrad learning rate, and D-TINF-SPM, based on FTRL with Tsallis entropy and the stability-penalty matching learning rate. Here, $K$ denotes the number of arms, $T$ the time horizon, and $\Delta_i$ the suboptimality gap of arm $i$. D-Exp3-Ada achieves $\mathcal{O}(\sqrt{KT\log K})$ regret in adversarial regimes and $\mathcal{O}(\sum_{i \neq i^{\star}} \frac{\log K}{\Delta_i})$ in stochastic regimes, combining simplicity of algorithm design with strong guarantees. D-TINF-SPM achieves the minimax optimal $\mathcal{O}(\sqrt{KT})$ in adversarial regimes and $\mathcal{O}(\min\{\sqrt{K\sum_{i \neq i^{\star}} \frac{1}{\Delta_{i}^2}}, \sum_{i \neq i^{\star}} \frac{\log K}{\Delta_i}\})$ in stochastic regimes. We also provide a refined analysis of the prior best algorithm. Finally, we derive instance-dependent lower bounds under natural monotonicity and permutation-invariance assumptions on regret upper bounds, proving that our algorithms are optimal up to $\mathcal{O}((\log K)^2)$ within this class.

We present GenusSink, a new class of approximate generalized Sinkhorn algorithms with shortest-path-distance costs for bounded genus (e.g. planar) graphs, providing near-linear time: (1) pre-processing, (2) iteration step, (3) final transport plan matrix querying and near-linear memory. Graphs handled by GenusSink include in particular planar graphs and bounded-genus meshes approximating 3D objects. GenusSink addresses total quadratic time complexity of its brute-force counterpart by leveraging separator-based decomposition of graphs, computational geometry techniques, and new results on fast matrix-vector multiplications with generalized distance matrices, using in particular Fourier analysis and low displacement rank theory. It is inspired by recent breakthroughs in graph theory on approximating bounded genus metrics with small treewidth metrics minor. The graph-centric approach enables us to target optimal transport problem with the corresponding distributions defined on the manifolds approximated by weighted graphs and with cost functions given by geodesic distances. We conduct rigorous theoretical analysis of GenusSink, provide practical implementations, leveraging newly introduced in this paper separation graph field integrators (S-GFIs) data structures and present empirical verification. GenusSink provides orders of magnitude more accurate computations than other efficient Sinkhorn algorithms, while still guaranteeing significant computational improvements, as compared to the baseline. As a by-product of the developed methods, we show that GenusSink is $\textbf{numerically equivalent}$ to the brute-force geodesic Sinkhorn algorithm on n-vertex graphs with treewidth $O(\log \log (n))$ (e.g. on trees).

Textual cues provide important navigation-relevant semantic information like room names, store signs, and floor labels. However, conventional optical character recognition (OCR) systems and datasets are designed to detect all visible text, including advertisements and price tags, regardless of their relevance to navigation tasks. This characteristic of OCR can produce noisy semantic cues, making it difficult to identify which text is useful for robot navigation. A straightforward solution is to curate existing OCR datasets by retaining only navigation-relevant text and removing irrelevant annotations, but this process requires substantial manual effort. To address this problem, we introduce NavOCR, a dataset generator for navigation-relevant text detection that does not require manual curation. By leveraging conventional OCR, open map resources, and filtering with a vision-language embedding model, NavOCR identifies which text instances serve as place identifiers for robot navigation and constructs datasets from images available on the web. NavOCR aims to complete the entire process within a single day, from data collection to model training, enabling rapid adaptation to diverse environments and languages. Compact models trained on datasets generated by NavOCR achieve higher detection accuracy and substantially better computational efficiency than vision language models and open vocabulary detectors. We further show that detecting navigation-relevant text improves the quality of semantic cues used for localization and mapping in robot navigation applications.

Robot learning research is fragmented across policy families, benchmark suites, and real robots; Each implementation is entangled with the others in a complex combination matrix, making it an engineering nightmare to port any single element into. General-purpose coding agents may occasionally bridge specific setups, but cannot close this gap at scale because they lack the procedural priors and validation practices that characterize robotics research workflows. We propose NAUTILUS, an open-source harness that turns a single user prompt, for example, ``Evaluate policy $A$ with benchmark $B$''---into ready-to-use reproduction, evaluation, fine-tuning, and deployment workflows. NAUTILUS provides: plug-and-play agent skill sets with distilled priors from robotics research; typed contracts among policies, simulators/benchmarks, and real-world robots; unified interfaces and execution environments; and an agentic coding workflow with explicit, automated validation, and testing at each milestone. NAUTILUS can not only automatically generate the required adapters and containers for existing implementations, but also wrap and onboard new or user-provided policies, simulators/benchmarks, and robots, all connected via a uniform interface. This expands cross-validation coverage without hand-written glue code. Like a nautilus shell that grows by adding chambers, NAUTILUS scales by extending its execution in chambered units, making it a research harness for scalability rather than a hand-curated framework, and aiming to reduce the engineering burden of cross-family reproduction and evaluation in the ever-growing robot learning ecosystem.

Docking ultimately determines effective ligand binding, yet bridging global functional semantics and local physical constraints remains a central challenge for protein generation for ligand-binding design. We therefore use docking-oriented language describing docking processes, binding patterns, and local interaction constraints as generation conditions, rather than relying only on coarse-grained functional text. However, existing methods still insufficiently model docking constraints and show limited coordination among heterogeneous modalities. To address these limitations, we propose DockWizard, an encoder-router-decoder framework for multimodal protein generation. Concretely, (1) a multimodal encoder aligns function text, docking text, ligand descriptions, ligand SMILES, and ligand 3D information into shared conditional representations, improving semantic consistency across heterogeneous inputs; (2) a router module organizes heterogeneous conditions into role-specific memories by their scopes of action, preserving global functional guidance while strengthening local binding constraints; and (3) a protein decoder combines prefix guidance with full-memory injection to let different conditions act at different levels, improving controllability while preserving docking constraints during generation. We further curate a docking-language multimodal dataset with over 100,000 samples. Extensive experiments under a four-stage evaluation pipeline show that DockWizard outperforms strong baselines for this task, with average gains of 13% in docking confidence and 19% in complex stability.

Reactive synthesis, the problem of automatically constructing a hardware circuit from a logical specification, is a long-standing challenge in formal verification. It is elusive for two reasons: It is algorithmically hard, and writing formal specifications by hand is notoriously difficult. In this paper, we tackle both sides of the problem. For the algorithmic side, we present a neuro-symbolic approach to reactive synthesis that couples large reasoning models with model checkers to iteratively repair a synthesized Verilog implementation via sound symbolic feedback. Our approach solves more benchmarks than the best dedicated tools in the annual synthesis competition and extends to constructing parameterized systems, a problem known to be undecidable. On the specification side, we introduce an autoformalization step that shifts the specification task from temporal logic to natural language by introducing a hand-authored dataset of natural-language specifications for evaluation. We demonstrate performance comparable to that of starting from formal specifications, establishing natural synthesis as a viable end-to-end workflow.

Joint audio-video generation aims to synthesize temporally synchronized and semantically coherent visual and acoustic content. Existing open-source methods mainly follow either dual-tower designs, which generate audio and video in separate streams and rely on posterior alignment, or fully unified tri-modal designs, which mix textual context, audio, and video in a single shared space. These paradigms may either weaken fine-grained audio-video co-evolution or couple semantic conditioning with low-level synchronization. We propose NAVA, a Native Audio-Visual Alignment framework that formulates generation as context-conditioned native audio-visual alignment. NAVA first establishes audio-video correspondence in a dedicated alignment space and then applies context as external conditioning to guide the aligned representation. We instantiate this formulation with an Align-then-Fuse MMDiT architecture, which progressively bridges modality-aware alignment and unified audio-video denoising. To support controllable speech generation, we further introduce Timbre-in-Context Conditioning, which binds reference timbre cues to corresponding speech spans through the context pathway. Experiments on Verse-Bench and the Seed-TTS benchmark demonstrate that NAVA achieves superior audio-visual synchronization and video quality, competitive audio quality, and substantially improved reference-timbre controllability with only 6.2B parameters.

We study fair multi-armed bandits under the Nash Social Welfare (NSW) objective, which measures performance via the geometric mean of accumulated rewards as a fairness-respecting performance metric. Existing formulations define Nash regret as $NR_T = \mu^\star - (\prod_{t=1}^T \mathbb{E}\mu_{I_t})^{1/T}$, where $\mu_{I_t}$ is the mean reward of the recommended arm $I_t$ and $T$ is the learning horizon. We observe that, since ensemble Nash regret operates on per-round marginal expectations before applying the geometric mean, it does not capture the joint distribution of rewards across rounds — leaving an aspect of the NSW fairness motivation unaddressed at the trajectory level. To address this, we propose \emph{trajectory-wise Nash regret} $\widetilde{NR_T}= \mu^\star - \mathbb{E}[(\prod_{t=1}^T \mu_{I_t})^{1/T}]$, where the geometric mean is computed over complete sample paths before taking expectations. This formulation captures the fairness properties of NSW more faithfully and requires controlling the joint distribution of rewards across rounds, rather than merely per-round marginals. By Jensen's inequality applied to the concave geometric mean, $\widetilde{NR_T} \geq NR_T$, making it a strictly stronger metric. We additionally introduce \emph{high probability Nash regret} $\widehat{NR_T} = \mu^\star - (\prod_t \mu_{I_t})^{1/T}$, obtaining the first high probability regret bounds in the fair bandits literature. We propose a two-phase algorithm, Round Robin Nash Confidence Bound (\texttt{RR-NCB}), combining structured round robin exploration with a Nash confidence bound index policy. We establish that $\widetilde{NR_T} \leq \widetilde{\mathcal{O}}(\sqrt{k\log T/T})$ and $\widehat{NR_T} \leq \widetilde{\mathcal{O}}(\sqrt{k\log(kT/\delta)/T})$ with probability $1-\delta$, matching the optimal $\widetilde{\mathcal{O}}(\sqrt{k/T})$ scaling despite operating under strictly stronger metrics. Optimality follows from a lower bound chain via AM-GM and standard $k$-armed bandit minimax arguments. We validate our theoretical findings through simulations.

Large language models are increasingly deployed as teams of agents that hold different private information about a shared task. How should such agents concisely communicate in a way that promotes aggregation of decision relevant information? Communicating only proposed actions can discard decision-relevant uncertainty: two agents may prefer the same action for different reasons. We study an alternative interface in which agents communicate calibrated beliefs over actions. We first analyze a simple synthetic setting that captures the structure of multi-round reasoning under partial information. In this setting, we show theoretically and empirically that communicating unbiased probabilities can be strictly more powerful than communicating actions. We then test the same principle in a collaborative maze-solving task with trained transformers and pretrained LLM agents. Our results demonstrate that probability communication outperforms action communication when the exchanged predictions preserve calibrated uncertainty. When communicated probabilities are biased we show that the benefits of probability communication can disappear. We give a post-hoc conversation calibration intervention that consistently improves decision-making by correcting these biases. These results suggest that probabilistic communication is useful for multi-agent collaboration not merely because it transmits more information, but because calibrated uncertainty gives other agents a reliable object to update on.

Protein structure prediction has progressed rapidly, with a flourishing ecosystem of open-source AlphaFold (AF)-style systems delivering real progress. But isolating which architectural and training choices actually drive that progress is difficult. Production-scale training is both computationally prohibitive and not accessibly reproducible; moreover, the public corpora are complex, with structural biases that compound in parameter- and compute-constrained regimes. To address these gaps, we introduce NanoFold, a compact, fixed-data benchmark for AF-style training studies. Its sealed-hidden tracks address three fundamental questions, with a $\textit{limited}$ track for sample efficiency, a $\textit{research large}$ track for whether early gains persist under more optimization, and an $\textit{unlimited}$ track for best fixed-data final performance. NanoFold's split is designed rather than naively sampled, with chains grouped into biological units under MMseqs2 cluster and PDB-entry disjointness, stratified across structural metadata, and allocated to $10{,}000$ training, $1{,}000$ public-validation, and $1{,}000$ sealed hidden chains. We verify the construction through statistically principled diagnostics, including a randomization study over $1{,}000$ alternative valid splits, confirming the dataset is diverse, well-distributed, and statistically typical of its constraint class. We use NanoFold to run comprehensive experiments on model behavior across scales and training regimes, demonstrating that the benchmark is learnable but unsaturated, scales predictably with budget, cleanly separates training primitives, and that the underlying codebase flexibly supports head-to-head comparison. NanoFold makes architectural and training progress in protein structure prediction more transparent, comparable, and reproducible at a compute-accessible scale.

Generative models play a rapidly growing role in the design and simulation of molecules. The most widely used applications of generative models are in large language models (LLMs), owing to the natural flexibility of language for specifying and answering queries. However, generalist LLMs do not effectively handle large sets of 3D coordinates, whereas specialist generative models of 3D molecules cannot reach the controllability afforded by language. To bridge these capabilities, we propose Nahual, a decoder-only autoregressive diffusion model for any sequence of text and 3D molecules. To enable autoregression on continuous coordinates to scale to long sequences, we propose next-token diffusion, whereby a standard causal transformer backbone is grounded in the clean current sequence while denoising the next sequence. We train Nahual on a curated set of twelve 3D chemistry tasks ranging from microsolvation to molecular conformer search to adsorption on metal surfaces, with associated evaluation metrics and baselines. The result is a single set of end-to-end-trained weights that simultaneously performs all tasks and surpasses state-of-the-art models specialized for crystal structure prediction and property-conditional molecule generation. Our results demonstrate the viability of scaling generalist decoder-only models for native multimodal understanding and generation across language and chemistry.

Most recent real-world image super-resolution (Real-ISR) methods employ pre-trained text-to-image (T2I) diffusion models to synthesize the high-quality image either from random Gaussian noise or directly from the input low-quality image. These approaches train ControlNet or LoRA modules while keeping the pre-trained model fixed, which often introduces over-enhanced artifacts and hallucinations, suffering from limited robustness to inputs with varying degradations. Recent visual autoregressive (AR) models, such as pre-trained Infinity, can provide strong T2I generation capabilities while offering superior efficiency by using the bitwise next-scale prediction strategy. Building upon next-scale prediction, we introduce a robust Real-ISR framework with a generation pathway control mechanism, namely Next-Scale Autoregressive Modeling (NSARM). Specifically, we train NSARM in two stages: a transformation network is first trained to map the input low-quality image to preliminary scales, followed by an end-to-end full-model fine-tuning. Such a comprehensive fine-tuning enhances the robustness of NSARM in Real-ISR tasks without compromising its generative capability. Extensive quantitative and qualitative evaluations demonstrate that as a pure AR model, NSARM achieves superior visual results over existing Real-ISR methods, with fast inference speed and comparable fidelity. Most importantly, it demonstrates much higher robustness to varying input quality, showing stronger generalization performance.

Vision-Language-Action (VLA) models are formulated to ground instructions in visual context and generate action sequences for robotic manipulation. Despite recent progress, VLA models still face challenges in learning related and reusable primitives, reducing reliance on large-scale data and complex architectures, and enabling exploration beyond demonstrations. To address these challenges, we propose a novel \textbf{N}euro-\textbf{S}ymbolic \textbf{V}ision-\textbf{L}anguage-\textbf{A}ction (NS-VLA) framework via online reinforcement learning (RL). It introduces a symbolic encoder to embedding vision and language features and extract structured primitives, utilizes a symbolic solver for data-efficient action sequencing, and leverages online RL to optimize generation via expansive exploration. Experiments on robotic manipulation benchmarks demonstrate that NS-VLA outperforms previous methods in both one-shot training and data-perturbed settings, while simultaneously exhibiting superior zero-shot generalizability, high data efficiency, and an expanded exploration space. Our code is available at https://anonymous.4open.science/r/NS-VLA/.

We present NPUsper, a live transcription system that makes Whisper efficient on mobile NPUs by eliminating redundant computation. To avoid the heavy padding used by prior streaming systems, NPUsper detects hallucinated tokens online from temporal patterns in decoder cross-attention, allowing each inference round to process short audio inputs with minimal carryover. For efficient mobile-NPU execution, we propose controlled unrolling, which executes autoregressive decoding as K-step chunk graphs, removing unnecessary KV-cache computation and reducing graph-dispatch overhead. NPUsper achieves up to 4.84x lower per-word latency, up to 33.2x lower time-to-first-token (TTFT), and up to 11.36% lower average power consumption compared with baselines, while maintaining comparable transcription accuracy. The code is available at https://github.com/npusper/NPUsper.