NeurIPS 2026 Papers

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.

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\%$.

We study the query and communication complexity of sampling from high-dimensional Gaussian distributions using gradient information. In the standard oracle model, exact gradients expose only matrix-vector products with the precision matrix, leading to polynomial approximation barriers and a characteristic $\sqrt{\kappa}$ dependence on the condition number. We show that this barrier disappears when the sampler is allowed to query \emph{smoothed gradients}, namely scores of Gaussian-convolved distributions. For a Gaussian target with precision $\Lambda$, a smoothed-score query at noise level $\tau$ gives access to the resolvent $(\Lambda+\tau^{-1}I)^{-1}$. Combining geometrically spaced noise levels with sinc-quadrature rational approximation, we obtain a sampler with $$ q = O\left( \left(\log\kappa+\log(\sqrt d/\varepsilon)\right) \log(\sqrt d/\varepsilon) \right) $$ smoothed-gradient queries for total variation error $\varepsilon$, improving the condition-number dependence from $\sqrt{\kappa}$ to logarithmic. We also study finite-bit gradient oracles. Using coordinatewise quantization of the transformed smoothed-gradient answers and a final dithering step, we obtain a sampling scheme whose total communicated gradient information is polylogarithmic in $\kappa$; in particular, for fixed dimension and accuracy, the bit complexity is $O(\log^2\kappa)$. To complement these upper bounds, we introduce a channel-synthesis, or reverse-Shannon, converse technique for sampling lower bounds. This converts total-variation simulation guarantees into communication requirements and yields an $\Omega(\log\kappa)$ lower bound on the required gradient information. Together, these results identify smoothed gradients as a strictly more powerful oracle for sampling and give nearly matching upper and lower bounds for its finite-bit complexity.

Searching for mathematical results remains difficult: most existing tools retrieve entire papers, while mathematicians and theorem-proving agents often seek a specific theorem, lemma, or proposition that answers a query. While semantic search has seen rapid progress, its behavior on large, highly technical corpora such as research-level mathematical theorems remains poorly understood. In this work, we introduce and study semantic theorem retrieval at scale over a unified corpus of 9.2 million theorem statements extracted from arXiv and seven other sources, representing the largest publicly available corpus of human-authored, research-level theorems. We represent each theorem with a short natural-language description as a retrieval representation and systematically analyze how representation context, language model choice, embedding model, and prompting strategy affect retrieval quality. On a curated evaluation set of theorem-search queries written by professional mathematicians, our approach substantially improves both theorem-level and paper-level retrieval compared to existing baselines, demonstrating that semantic theorem search is feasible and effective at web scale. The project page, search tool, dataset, REST API, and MCP server are available at [Redacted]

Generative models are increasingly central to many de novo discovery pipelines, in which designs are generated at scale and filtered through virtual screens to determine a set of candidates to experimentally validate. While Bayesian optimization (BO) is a natural fit for this setting, as it uses past evaluations to guide future proposals, the computational overhead required for its sequential decision-making becomes a bottleneck when virtual screens are relatively cheap. We make BO practical in this regime by exploiting the unique combination of a linear model constrained to a spherical domain where high-dimensional latents concentrate. We build off recent work justifying the use of linear surrogates, while deriving nearly closed-form solutions to the surrogate modelling and acquisition problems that exploit spherical symmetry. The result is a $100\times$ speedup over state-of-the-art baselines, with matching or improved performance across molecular and image generation benchmarks. Altogether, our method makes BO a practical drop-in for de novo pipelines where it was previously too slow to consider.

Post-training weight quantization is crucial for reducing the deployment cost of large language models (LLMs), yet maintaining model quality in the ultra-low-bit regime ($\le$ 3 bits) remains challenging due to highly non-uniform weight sensitivity and the lack of principled precision allocation strategies. In this work, we show that the weight sensitivity is inherently dynamic and depends on the current quantized model, rather than the full-precision reference used in existing methods. Leveraging this observation, we introduce a sensitivity estimate that better captures the changes in marginal loss during progressive quantization. We further uncover a structured pattern in sensitivity distribution, revealing a bi-directional concentration across input and output channels, which enables hardware-aligned yet expressive partitioning via channel reordering. Building on these insights, we propose ScaleBITS, a scalable framework that combines structured partitioning and an efficient approximation to greedy allocation. Our approach enables fine-grained, global bitwidth search while preserving hardware efficiency. Experiments show that ScaleBITS significantly improves over uniform-precision quantization (up to +36%) and outperforms state-of-the-art sensitivity-aware baselines (up to +13%) in the ultra-low-bit regime, without adding runtime overhead.

Large language model (LLM)-powered multi-agent systems have been shown to effectively solve real-world end-to-end problems through collaboration among diverse agents. However, as LLM capabilities advance and user demands continue to grow, the range of problems that agents can address expands dramatically, while the population of available agents and tools continues to increase, giving rise to open and evolving ecosystems of autonomous agents. In this paradigm, agents are likely to become increasingly specialized, each focusing on particular capabilities or problem types. In such a setting, a central challenge is how to efficiently assemble an appropriate team of agents to take on different responsibilities from a massive agent pool for a given task. In this work, we study this problem in a controlled setting with 300 task-oriented agents. SMART (Scalable Multi-Agent Role-conditioned Teaming) first plans a task-conditioned collaboration topology and candidate role set, then constructs a compact role-conditioned candidate pool, and finally uses a LLM-free Monte Carlo Tree Search (MCTS) to assign agents to roles online via metadata-based rollouts. This design enables high flexibility without incurring prohibitive inference costs. Across multiple experiments, our approach achieves superior performance on GSM8K (93.64\%), MATH (61.73\%), HumanEval (93.89\%), and MBPP (87.68\%) using gpt-4o-mini under a limited budget.

Large language model (LLM)-driven evolutionary frameworks have emerged as a promising paradigm for iterative search in complex optimization and structured generation tasks. However, existing methods typically rely on heuristic variation operators and lack an explicit mechanism to extract directional information from observed performance feedback, limiting both efficiency and reliability. To address this, we propose SGEvolve, a semantic gradient-guided evolutionary framework for LLM-driven optimization. The key idea is to treat the performance differences between parent and offspring as zeroth-order evidence of an underlying ascent direction. Based on this view, we formulate semantic gradient extraction as a Maximum A Posteriori (MAP) estimation problem, where the LLM infers the most probable direction of improvement conditioned on observed evolutionary steps. The inferred gradients are then used to guide mutation and crossover, biasing generation toward more promising regions of the search space. We evaluate SGEvolve on a diverse set of tasks, including mathematical optimization, algorithm design, and real-world industrial problems. Experimental results demonstrate that SGEvolve consistently outperforms existing open-source baselines, achieving superior performance in both solution quality and search efficiency.

Most video anomaly understanding (VAU) systems still infer anomaly judgments from evidence collected in a feed-forward way under predefined rules, typically sampled frames, or events clustered from such frames. This protocol fails when the collected evidence is incomplete under imperfect predefined rules, because once reasoning begins the model can no longer search for the missing evidence. We address this limitation with SEEK-VAU, which reframes VAU as an agentic search-and-verify interaction protocol under a bounded search budget: instead of passively reasoning over pre-collected evidence, the policy actively gathers evidence across the three stages of an anomaly event chain (precursor, trigger, and aftermath) and verifies its sufficiency before finalization, turning event-chain completeness into an explicit design rather than an outcome of predefined rules. Although search-and-verify spans multiple interaction turns, the bounded search budget caps both the per-turn input tokens and the cumulative visual context, keeping inference efficient. To make this behavior learnable, we introduce evidence-faithful counterfactual verification (EFCV), which rewards selected evidence that remains supportive, compact, and necessary under counterfactual verification. We further introduce SEEK-Bench, featuring video-level episodes with temporal interval annotations, semantic QA and event-chain stage labels. Together, SEEK-VAU and SEEK-Bench establish a strong foundation for evidence-faithful and actively verifiable VAU. The code and data will be released.

Search-augmented reasoning agents interleave internal reasoning with calls to an external retriever, and their performance relies on the quality of each issued query. However, under outcome-reward reinforcement learning, every search decision in a rollout shares the same trajectory-level reward, leaving individual queries without step-specific credit. Recent process-supervision approaches address this gap by drawing step-level signals from outside the policy, relying either on a much larger teacher model, or on sub-question annotations produced by a stronger external system. In contrast, we propose \textbf{SD-Search}, which derives step-level supervision \emph{from the policy itself} through hindsight self-distillation, requiring neither an external teacher nor additional annotations. In SD-Search, a single model plays two roles that differ only in conditioning: a student that sees only the context available at inference time, and a teacher that additionally conditions on a compact hindsight block summarizing the search queries and final outcomes of a group of rollouts sampled from the same question. Since teacher knows how each rollout unfolded and which ones succeeded, its query distribution implicitly marks which decisions were worth making, and the student is trained to recover this behavior by minimizing the token-level Jensen--Shannon divergence to the teacher at search-query positions. This layers a dense, step-level signal on top of GRPO's coarse trajectory reward. Crucially, this signal requires only a single teacher forward pass per rollout at training time, all absorbed within the standard RL loop without external model inference, auxiliary annotation pipeline, or additional training. On seven single-hop and multi-hop QA benchmarks, SD-Search reaches $0.428$ average Exact Match with Qwen2.5-3B, matching the leading process-supervision baseline without its external teacher, and $0.476$ with Qwen2.5-7B, surpassing all outcome-reward and process-supervision baselines on the average.

Robots manipulating in cluttered spaces must often plan from partial views where foreground objects occlude the target, surrounding geometry, and usable free space. Reactive policies often miss these hidden constraints, while exhaustive search becomes computationally prohibitive in dense clutter. We present SCOUT, an occlusion-aware planning framework that bridges high-level deliberation with grounded physical rollouts. SCOUT leverages an object-centric scene representation to reconstruct hidden geometry and derive a relational planning state capturing blocker hierarchies and accessibility corridors. To navigate the vast action space in clutter, an LLM proposes structured action candidates which are then rigorously evaluated via Monte Carlo Tree Search (MCTS) using a learned action-conditioned world model. Evaluations on ‘Reveal’ and ‘Placement’ tasks show that SCOUT outperforms Vision-Language-Action (VLA) policies, embodied agents, and 3D world models, with significant gains in long-horizon tasks requiring reasoning over occluded geometry. We further validate the framework’s robustness through real-world robotic manipulation in a cluttered shelf environment.

Genetic Programming (GP) is a search paradigm inspired from natural evolution for the automated discovery of expressions, functions, and computer programs. Cartesian GP (CGP) is a flavor of GP that uses a graph-based model to encode candidate programs, as contrasted to the conventional Tree-based GP (TGP). Since its inception two decades ago, CGP has predominantly been analyzed empirically, thus little is known regarding its theoretical performance guarantees. This paper analyzes CGP for the MAX problem, which has been only rigorously studied for TGP with a proven expected runtime superlinear in the optimal program length $n$. We prove that the expected time for the (1+1) CGP employing common mutation operators to evolve an equivalent optimal of the same output is polylogarithmic in n, specifically at most $O(\log^9{n})$. This is remarkable, as it shows an exponential speedup by switching to CGP. Our results shed light on the benefit and the compactness of the graph-based representation for programs, and on how CGP can navigate its search and fitness spaces efficiently. This is a first proven performance guarantee for CGP on an established benchmark problem. Experiments complement our theoretical findings.

Approximate Nearest Neighbor Search (ANN) is an important algorithmic primitive that has found a plethora of applications in machine learning and information retrieval. The classic approach to this problem due to Indyk and Motwani (1998) leverages Locality Sensitive Hashing (LSH) by sampling multiple hash functions that are likely to identify similar data points. This approach has, however, been demonstrated to be vulnerable to adaptive queries and updates which may not be independent of its internal randomness (Kapralov et al. 2024). While differential-privacy-based techniques have yielded robust versions of randomized algorithms and data structures for estimation problems (Hassidim et al., 2022), ANN is a search problem: the algorithm must return an actual dataset point, without obfuscating the output by adding noise or rounding it. Feng et al. (2025) circumvent this limitation by relying on a density assumption that bounds the number of points near each query point. We study a stronger worst-case model in which the adversary chooses both the initial dataset and an adaptive query sequence. For LSH-equipped metric spaces, we give adversarially robust ANN algorithms with sublinear query time whose guarantees do not depend on any structural assumption on the dataset. The main technical challenge is to preserve sublinear search time when the adversary selects a dataset with arbitrarily many points near a query. Rather than applying differential-privacy robustification as a black box, we develop search-specific mechanisms: fairness as a route to adaptive security, a bucketing reduction from search to robust decision, and a concentric annuli construction that improves the query-time exponent. Moreover, for low-dimensional spaces, we give algorithms with a strong ``for-all'' guarantee, which are correct for every possible query.

Large Reasoning Models (LRMs) have demonstrated remarkable capabilities in multi-step reasoning and calling search engines at appropriate steps. However, existing retrieval-augmented reasoning approaches rely on separate retrieval models, limiting the LRM's role in retrieval to deciding when to retrieve and how to formulate queries, even with its inherent ability to handle vast knowledge spaces. This structural separation induces a representation bottleneck, as the retriever’s latent space often lacks the expressive granularity required to satisfy the generator’s sophisticated information needs. To address this, we shift our perspective on retrieval from sequence-to-sequence matching for all corpora to locating the answer-containing paths within the corpus, and propose a novel framework called FREESON (Retriever-FREE Retrieval-Augmented ReaSONing). This framework enables LRMs to directly access external knowledge by acting as both a generator and a retriever. To achieve this, we introduce a variant of the MCTS algorithm specialized for the retrieval task, which we call CT-MCT (Corpus-Traversing Monte Carlo Tree Search). Through this algorithm, the LRM selectively references specific segments identified during traversal, instead of fetching a fixed top-k set. Experiments on five open-domain QA benchmarks covering both single-hop and multi-hop questions demonstrate that FREESON achieves an average improvement of 14.4% in EM and F1 over four multi-step reasoning models with a separate retriever, and it also performs comparably to the strongest baseline, surpassing it by 3% on PopQA and 2WikiMultihopQA, and by 12% on the fact-checking benchmark FEVER.

Ridge crossings, where two components share the same instantaneous frequency (IF) at a given time, are a fundamental bottleneck in multi-component time-frequency (TF) mode decomposition. We trace this difficulty to \emph{insufficient representational dimensionality} and resolve it by lifting signals into the 3-D time-frequency-frequency-rate (TFFR) space $(t,f,\dot{f})$, where crossing ridges separate because they typically differ in the instantaneous frequency rate (IFR). We formalize this via a separability proposition and confirm it empirically through Monte Carlo simulation (crossing rate: 78.6\% in 2-D $\to$ 0.9\% in 3-D). Based on this principle, we propose \textbf{TFFR-Net}, a query-based masked transformer that jointly predicts per-ridge masks and dense IFR maps. An IFR feedback loop injects the estimated frequency rate back into each query embedding, enabling the decoder to perform instance discrimination in TFFR space rather than the TF plane. On a synthetic benchmark with up to six chirp components under broadband noise (0--25\,dB SNR), TFFR-Net consistently reduces IF MAE by at least 5.8\% and Dice loss by at least 5.4\% relative to competing methods. Evaluation on real-world signals (bat echolocation, power-system oscillation, earthquake vibration) demonstrates effective generalization beyond synthetic training data. The source code is available at \url{https://anonymous.4open.science/r/TFFR-92D2/}.

Operations research practitioners typically tackle NP-hard combinatorial problems using large neighborhood search (LNS), a scalable heuristic that iteratively refines a current solution by locally re-optimizing subsets of its variables. In contrast, most existing approaches for integrating combinatorial optimization layers into neural networks still assume access to an exact global solution, which is computationally intractable. We bridge this gap by introducing regularized LNS (RLNS). By regularizing or perturbing local subproblems, we turn the LNS heuristic into an efficient MCMC sampler over the combinatorial set of feasible solutions, with associated Fenchel-Young losses. Under entropic regularization, we prove that RLNS performs exact block Gibbs sampling. Furthermore, adjusting the number of RLNS iterations allows us to interpolate between pseudolikelihood and exact maximum likelihood estimation, for end-to-end learning without global solvers. We demonstrate our approach on $k$-subset selection, generalized assignment, and stochastic vehicle scheduling problems.

Hierarchical clustering seeks to uncover nested structure in data by constructing a tree of clusters, whose deeper levels reveal increasingly fine-grained relationships. However, traditional hierarchical clustering methods always return a hierarchy, even when the data contain no meaningful hierarchical structure. Moreover, agglomerative linkage algorithms are highly sensitive to the choice of linkage function. In this paper, we revisit a classical notion of well-separated clusters, which we call valid clusters. The collection of all valid clusters forms a hierarchy, known as the Apresjan hierarchy. This hierarchy is the finest hierarchy composed only of valid clusters: it need not be binary, and it collapses to a star tree when no nontrivial valid clusters exist. Our main contribution is to characterize when the Apresjan hierarchy can be recovered from linkage-based algorithms. We propose a two-step procedure that first constructs a binary hierarchy using an agglomerative linkage method and then prunes all clusters that violate the validity condition. We give necessary and sufficient conditions on the linkage function under which this procedure exactly recovers the Apresjan hierarchy. Consequently, all linkage rules satisfying these conditions yield the same pruned hierarchy. In particular, single, complete, and average linkage satisfy the conditions, whereas Ward's linkage does not.

Vanilla SVGD is known to have a computational cost of $\mathcal{O}(N^2)$ per iteration. In this work, we introduce Random-Projection Tree Stein Variational Gradient Descent (RP-SVGD) to alleviate this computational challenge. This is achieved by restricting kernel interactions to spatially proximal particles clustered via a random projection tree, further reducing to a cost of $\mathcal{O}(N d(\log (N/C)+C))$, where $C$ is a hyperparameter representing the maximum leaf node capacity of the spanning tree. To establish theoretical validity, we introduce a smoothed RP-Tree kernel for any fixed tree realization and prove that it belongs to the Stein class of the target distribution, thereby ensuring the generation of valid gradient flows. In addition, by considering the effective kernel as the expectation of random tree partitions, we verify that it preserves regularity along with other necessary conditions, which guarantee convergence under the approximate gradient flow framework. Extensive experimental results demonstrate that RP-SVGD tends to have competitive performance and significant speedups across various tasks.

Robots deployed for active search must decide where to sense while uncertainty, teammates, and remaining mobility change online. In active search, each waypoint decision also commits the robot to a route through the map, making efficient localization a long-horizon problem over belief, topology, robot state, and traversal budget rather than a sequence of independent next-best sensing decisions. We present QUEST, a shared-belief graph neural framework for multi-agent active search with noisy sensors, a shared posterior, and finite decision and path budgets. Rather than learning a myopic policy that values only the next route, QUEST trains Q-functions whose targets include both reward collected along the executed path and the downstream value of the resulting belief, robot positions, team coverage, and remaining budget. The same formulation supports single robots, homogeneous robot teams, and heterogeneous UAV--UGV teams with different sensors and motion budgets. During execution, each robot acts independently using the shared posterior and knowledge of teammates' positions and search plans. Across simulated search environments, QUEST reaches $0.913$ F-score with four UGVs, versus $0.853$ for the strongest learned baseline, and keeps above $0.90$ F-score under communication outage and two mid-mission robot failures without retraining. On out-of-distribution UAV--UGV teams, it improves early F-score ($0.759$ vs.\ $0.728$) while using $10\%$ less path length and $12\%$ less duplicate coverage than the same baseline. The same policies transfer across map shape, variable team size, communication outage, and mid-mission robot failure, and show sensing-mode adaptation after UGV failure.