Monte Carlo integration is widely used in computer graphics, especially in rendering, but we identify two key limitations. First, for each sample, we can often obtain rich auxiliary information, such as sample position, or geometric information. However, a classical Monte Carlo estimator cannot effectively use this information and only averages the function values. Second, the Monte Carlo formulation makes it difficult to adapt the sampling distribution toward truly informative regions, which can be critical for reconstructing the signal. To address these limitations, we argue that a sampler and integrator beyond the standard Monte Carlo methods is needed. We therefore propose an end-to-end sampling-integration approach that jointly learns both a sampler and an integrator using neural networks, enabling samples to be drawn and used in a more coupled and principled manner. By training on a dataset of integrands, the estimator can further use learned priors over integrand structure and specialize to a family of problems. We evaluate our method on diverse applications in lighting, transmittance, generalized winding number, and walk-on-spheres, spanning both linear and nonlinear cases, and a broad range of low- and high-dimensional settings. Even though the networks add computational overheads, in the equal-sample setting, our method achieves substantial improvements, providing a powerful alternative to traditional quadrature rules and sampling methods.
论文检索
输入标题、作者或关键词，从 427 篇学术成果中精准定位
The Walk on Spheres (WoS) algorithm is a mesh-free and highly flexible Monte Carlo method for solving partial differential equations, but its practical applicability is limited by slow O (N-1/2) convergence. While prior variance reduction techniques exploit spatial correlations through integral properties of the PDE, they do not fully utilize the intrinsic Markov structure of the WoS process. We introduce a new variance reduction framework based on reusing intermediate states along each random walk. Leveraging the Markov property, we show that every point visited by a WoS trajectory provides a valid unbiased estimator, but its direct use is hindered by the complex distribution induced by dynamically generated spheres. To resolve this, we propose the Walk on Probes (WoP) algorithm, which replaces dynamic spheres with a set of fixed, pre-distributed spherical probes inside the domain. This converts the intractable distribution of path points into samples on fixed boundaries, enabling efficient evaluation through the Poisson integral formula. We further develop a specialized method that combines control variates with self-normalization to further reduce variance. Together, these components substantially improve sample efficiency while preserving the flexibility of WoS. Code and data for this paper are at https://github.com/USTCGCL-WoS/Walk-on-Probes.
We present ST-FLIP, a spatiotemporal extension of the Fluid-Implicit Particle (FLIP) method for incompressible free-surface and two-phase liquid simulation. ST-FLIP enables time steps up to an order of magnitude larger than those typically used in CFL-constrained solvers, while preserving detailed flow structures and visual fidelity. It addresses a common failure mode of large time steps in hybrid particle-grid liquid solvers: temporal under-sampling of particle motion produces aliasing-driven free-surface artifacts after projection. Our key idea is to interpret particles as samples in four-dimensional space-time: in addition to standard spatial jittering, we randomize particle positions along the time axis as well and perform particle-to-grid deposition using a separable 4D kernel. This yields a Monte Carlo estimator of perstep time-slab-integrated particle quantities. Although particles are treated as samples in 4D space-time, our approach works as a lightweight plugin by collapsing to slab-integrated 3D grid fields for projection. Building on recent particle-based phase-field work, we reuse the particle-to-grid weight accumulators as a conceptual space-time phase field, providing variable-coefficient projection weights and eliminating the need for per-step surface reconstruction. The method can be easily integrated into existing FLIP/PIC or APIC solvers with negligible additional computational cost per time step. The effectiveness of our approach is demonstrated through a series of comparisons with state-of-the-art solvers, yielding several-fold speedups for multi-billion-particle simulations at high effective 3D resolutions on a single workstation.
Low-discrepancy points have proven to be a useful source of samples for numerical integration via quasi-Monte Carlo integration. Low-discrepancy points are typically uniformly distributed in the unit hypercube. It is thus common to transform the input uniform points into target non-uniform samples via mapping, just like how uniform random numbers are used for generating non-uniform samples. Unfortunately, this common approach does not guarantee to carry over the low-discrepancy nature of the input points into the output non-uniform samples, giving the resulting non-uniform samples suboptimal discrepancy. The existing methods for generating low-discrepancy points focus only on uniform points, thus generating non-uniform and low-discrepancy samples has been an open problem. We introduce an optimization framework to approximate non-uniform low-discrepancy samples by numerically minimizing the discrepancy metric for non-uniform samples. We propose a differentiable numerical estimator of the generalized non-uniform discrepancy to enable gradient-based optimization. Our differentiable discrepancy estimator turns a challenging problem of generating non-uniform low-discrepancy samples into a simple numerical optimization problem. Since optimization can generate only one set of samples, we further propose a neural network architecture to encode the sample generation process, allowing us to generate multiple sets of samples from conditional targets without runtime optimization. We experimentally validate that our method reduces discrepancy below prior methods at least up to a certain sample size and consequently achieves lower integration error on numerical integration problems.
Active retrieval-augmented generation (RAG) triggers external knowledge retrieval during generation based on model-side uncertainty signals to support knowledge-intensive, multi-hop reasoning. However, existing methods often retrieve only after producing a complete answer, failing to surface and fill information gaps in time; moreover, relying on a single internal signal as the trigger cannot adequately capture the multifaceted nature of uncertainty. We therefore propose a conflict-aware active RAG framework. We first decompose complex questions into a sequence of step-level sub-problems. At each step, we quantify local distributional uncertainty via a sliding-window peak token entropy, and estimate cross-sample consensus via the variation ratio computed over multiple Monte Carlo samples. After calibrating both signals onto a probabilistic scale, we quantify their conflict using a symmetric, bounded divergence over Bernoulli parameters, and fuse the three quantities into a single uncertainty score that gates retrieval. Experiments demonstrate the effectiveness of our framework.
Graph generation is a fundamental problem in graph learning with broad applications across Web-scale systems, knowledge graphs, and scientific domains such as drug and material discovery. Recent approaches leverage diffusion models for step-by-step generation, yet unconditional diffusion offers little control over desired properties, often leading to unstable quality and difficulty in incorporating new objectives. Inference-time guidance methods mitigate these issues by adjusting the sampling process without retraining, but they remain inherently local, heuristic, and limited in controllability. To overcome these limitations, we propose TreeDiff, a Monte Carlo Tree Search (MCTS) guided dual-space diffusion framework for controllable graph generation. TreeDiff is a plug-and-play inference-time method that expands the search space while keeping computation tractable. Specifically, TreeDiff introduces three key designs to make it practical and scalable: (1) a macro-step expansion strategy that groups multiple denoising updates into a single transition, reducing tree depth and enabling long-horizon exploration; (2) a dual-space denoising mechanism that couples efficient latent-space denoising with lightweight discrete correction in graph space, ensuring both scalability and structural fidelity; and (3) a dual-space verifier that predicts long-term rewards from partially denoised graphs, enabling early value estimation and removing the need for full rollouts. Extensive experiments on 2D and 3D molecular generation benchmarks, under both unconditional and conditional settings, demonstrate that TreeDiff achieves state-of-the-art performance. Notably, TreeDiff exhibits favorable inference-time scaling: it continues to improve with additional computation, while existing inference-time methods plateau early under limited resources.
Parallel tempering, or the replica exchange method, is a Markov Chain Monte Carlo (MCMC) sampling technique for finding low-energy states in complex landscapes by executing multiple processes at different temperatures and allowing for states to migrate between parallel processes based on the Metropolis criterion. Despite a growing interest in the technique as a randomized search heuristic, it is not clear when and why parallel tempering is effective. We conduct a first runtime analysis of the parallel tempering algorithm on a simple quadratic unconstrained binary optimization problem that induces a rugged energy landscape with tunable parameters. We prove that a single-temperature Metropolis process fails to efficiently optimize the problem at any temperature. In sharp contrast, a two-state parallel tempering approach using a low and a high temperature typically solves the problem in O(n^2 log n) iterations. The low-temperature process ensures stability, as it is unlikely to accept worsenings, whereas the high-temperature process facilitates exploration by traversing energy barriers. Improvements are discovered through exploration in the high-temperature process and transferred to the low-temperature process, where they are permanently retained. This effective interplay between processes demonstrates the power of parallel tempering and lends credence to its design.
Temporal embeddings play a crucial role in dynamic graph neural networks (DGNNs) by capturing the temporal dynamics of interactions. However, existing Random Fourier Feature (RFF)-based methods in DGNNs directly sample Fourier frequencies from a fixed, data-independent distribution, neglecting the temporal characteristics of dynamic graphs and thereby limiting representational capacity. We propose DeepSTE, a deep spectral temporal embedding framework for dynamic graphs. DeepSTE learns RFF representations via Monte Carlo importance sampling with a tractable proposal distribution (e.g., Gaussian) to approximate the feature map of a shift-invariant or positive-definite kernel whose latent spectral density is analytically intractable. DeepSTE adopts a data-dependent scale parameter, estimated from interaction intervals, to construct the frequency proposal distribution reflecting time–frequency uncertainty. The frequency DNN and the importance-weighting DNN, initialized from the proposal distribution, are jointly optimized to model the importance-sampled spectral representation and learn adaptive temporal features. Experiments demonstrate the effectiveness of DeepSTE on dynamic link prediction and node classification tasks, while also revealing insights such as temporal embedding decay and accelerated convergence.
Online planning in Markov Decision Processes (MDPs) enables agents to make sequential decisions by simulating future trajectories from the current state, making it well-suited for large-scale or dynamic environments. Sample-based methods such as Sparse Sampling and Monte Carlo Tree Search (MCTS) are widely adopted for their ability to approximate optimal actions using a generative model. However, in practical settings, the generative model is often learned from limited data, introducing approximation errors that can degrade performance or lead to unsafe behaviors. To address these challenges, Robust MDPs (RMDPs) offer a principled framework for planning under model uncertainty, yet existing approaches are typically computationally intensive and not suited for real-time use. In this work, we introduce Robust Sparse Sampling (RSS), the first online planning algorithm for RMDPs with finite-sample theoretical performance guarantees. Unlike Sparse Sampling, which estimates the nominal value function, RSS computes a robust value function by leveraging the efficiency and theoretical properties of Sample Average Approximation (SAA), enabling tractable robust policy computation in online settings. RSS is applicable to infinite or continuous state spaces, and its sample and computational complexities are independent of the state space size. We provide theoretical performance guarantees and empirically show that RSS outperforms standard Sparse Sampling in environments with uncertain dynamics.
Large language models (LLMs) have achieved remarkable success in a wide range of tasks. However, their reasoning capabilities, particularly in complex domains like mathematics, remain a significant challenge. Value-based process verifiers, which estimate the probability of a partial reasoning chain leading to a correct solution, are a promising approach for improving reasoning. Nevertheless, their effectiveness is often hindered by estimation error in their training annotations, a consequence of the limited number of Monte Carlo (MC) samples feasible due to the high cost of LLM inference. In this paper, we identify that the estimation error primarily arises from high variance rather than bias, and the MC estimator is a Minimum Variance Unbiased Estimator (MVUE). To address the problem, we propose the Compound Monte Carlo Sampling (ComMCS) method, which constructs an unbiased estimator by linearly combining the MC estimators from the current and subsequent steps. Theoretically, we show that our method leads to a predictable reduction in variance, while maintaining an unbiased estimation without additional LLM inference cost. We also perform empirical experiments on the MATH-500 and GSM8K benchmarks to demonstrate the effectiveness of our method. Notably, ComMCS outperforms regression-based optimization method by 2.8 points, the non-variance-reduced baseline by 2.2 points on MATH-500 on Best-of-32 sampling experiment.
Large language model (LLM) agents have demonstrated strong capabilities across diverse domains, yet automated agent design remains a significant challenge. Current automated agent design approaches are often constrained by limited search spaces that primarily optimize workflows but fail to integrate crucial human-designed components like memory, planning, and tool use. Furthermore, these methods are hampered by high evaluation costs, as evaluating even a single new agent on a benchmark can require tens of dollars. The difficulty of this exploration is further exacerbated by inefficient search strategies that struggle to navigate the large design space effectively, making the discovery of novel agents a slow and resource-intensive process. To address these challenges, we propose AgentSwift, a novel framework for automated agent design. We formalize a hierarchical search space that jointly models agentic workflow and composable functional components. This structure moves beyond optimizing workflows alone by co-optimizing functional components, which enables the discovery of more complex and effective agent architectures. To make exploration within this expansive space feasible, we mitigate high evaluation costs by training a value model on a high-quality dataset, generated via a novel strategy combining combinatorial coverage and balanced Bayesian sampling for low-cost evaluation. Guiding the entire process is a hierarchical Monte Carlo Tree Search (MCTS) strategy, which is informed by uncertainty to efficiently navigate the search space. Evaluated across a comprehensive set of seven benchmarks spanning embodied, math, web, tool, and game domains, AgentSwift discovers agents that achieve an average performance gain of 8.34\% over both existing automated agent search methods and manually designed agents. Moreover, our framework exhibits steeper and more stable search trajectories. By enabling the efficient, automated composition of workflow with functional components, AgentSwift provides a scalable methodology to explore complex agent designs. Our framework serves as a launchpad for researchers to rapidly prototype and discover powerful agent architectures without the impediment of prohibitive evaluation costs.
From Mathematical Reasoning to Code: Generalization of Process Reward Models in Test-Time Scaling
PDF ↗Recent advancements in improving the reasoning capabilities of Large Language Models have underscored the efficacy of Process Reward Models (PRMs) in addressing intermediate errors through structured feedback mechanisms. This study analyzes PRMs from multiple perspectives, including training methodologies, scalability, and generalization capabilities. We investigate the interplay between pre-training and reward model training FLOPs to assess their influence on PRM efficiency and accuracy in complex reasoning tasks. Our analysis reveals a pattern of diminishing returns in performance with increasing PRM scale, highlighting the importance of balancing model size and computational cost. Furthermore, the diversity of training datasets significantly impacts PRM performance, emphasizing the importance of diverse data to enhance both accuracy and efficiency. We further examine test-time scaling strategies, identifying Monte Carlo Tree Search as the most effective method when computational resources are abundant, while Best-of-N Sampling serves as a practical alternative under resource-limited conditions. Notably, our findings indicate that PRMs trained on mathematical datasets exhibit performance comparable to those tailored for code generation, suggesting robust cross-domain generalization. Employing a gradient-based metric, we observe that PRMs exhibit a preference for selecting responses with similar underlying patterns, further informing their optimization.
Mixture-of-Experts (MoE) architectures have recently become a more prevalent choice for large language models (LLMs) than dense architectures due to their superior performance. However, billions of parameters bring MoE LLMs a huge cost for deployment and inference. To address these issues, knowledge distillation (KD) has become a widely adopted technique to compress LLMs. Existing KD methods for LLMs can be divided into dense-to-dense and moe-to-dense distillation. Dense-to-dense distillation transfers knowledge between single dense LLMs, while moe-to-dense distillation attempts to transfer knowledge between the MoE LLMs and the dense LLMs. However, the architectural mismatch prevents the student from fully absorbing knowledge when distilling MoE LLMs. To address this limitation, we investigate a new distillation setting, moe-to-moe, which aims to fully leverage expert knowledge of teachers and enable the student to absorb it more effectively. Compared to dense-to-dense and moe-to-dense, moe-to-moe suffers from two imbalance issues. First, expert-coverage deficiency reflects an imbalanced knowledge transfer of teacher experts: traditional distillation utilizes only the few experts activated by the teacher router. Second, routing imbalance appears when the student routing distribution drifts from the teacher, which makes it difficult for students to learn how to distribute different experts. To overcome these issues, we propose a novel distillation framework for moe-to-moe, Balanced Distillation (B-Distill), which equally spreads teacher expertise across student experts while regularizing the student router toward teacher-consistent balance. First, to mitigate expert-coverage deficiency, we introduce Monte Carlo exploration, which stochastically perturbs router probabilities so every teacher and student expert is sampled without enlarging the search space. Second, to correct routing imbalance and avert load collapse, we propose an entropy-aware router distillation mechanism that aligns the student router with the teacher while curbing over-concentration. Experiments show that B-Distill outperforms baselines by up to 6.6% in Rouge-L.
Neural Differential Equations (NDEs) excel at modeling continuous-time dynamics, effectively handling challenges such as irregular observations, missing values, and noise. Despite their advantages, NDEs face a fundamental challenge in adopting dropout, a cornerstone of deep learning regularization, making them susceptible to overfitting. To address this research gap, we introduce Continuum Dropout, a universally applicable regularization technique for NDEs built upon the theory of alternating renewal processes. Continuum Dropout formulates the on-off mechanism of dropout as a stochastic process that alternates between active (evolution) and inactive (paused) states in continuous time. This provides a principled approach to prevent overfitting and enhance the generalization capabilities of NDEs. Moreover, Continuum Dropout offers a structured framework to quantify predictive uncertainty via Monte Carlo sampling at test time. Through extensive experiments, we demonstrate that Continuum Dropout outperforms existing regularization methods for NDEs, achieving superior performance on various time series and image classification tasks. It also yields better-calibrated and more trustworthy probability estimates, highlighting its effectiveness for uncertainty-aware modeling.
Random Sample Consensus (RANSAC) is a fundamental approach for robustly estimating parametric models from noisy data. Existing learning-based RANSAC methods utilize deep learning to enhance the robustness of RANSAC against outliers. However, these approaches are trained and tested on the data generated by the same algorithms, leading to limited generalization to out-of-distribution data during inference. Therefore, in this paper, we introduce a novel diffusion-based paradigm that progressively injects noise into ground-truth data, simulating the noisy conditions for training learning-based RANSAC. To enhance data diversity, we incorporate Monte Carlo sampling into the diffusion paradigm, approximating diverse data distributions by introducing different types of randomness at multiple stages. We evaluate our approach in the context of feature matching through comprehensive experiments on the ScanNet and MegaDepth datasets. The experimental results demonstrate that our Monte Carlo diffusion mechanism significantly improves the generalization ability of learning-based RANSAC. We also develop extensive ablation studies that highlight the effectiveness of key components in our framework.
Monte Carlo random walk methods are widely used in capacitance extraction for their mesh-free formulation and inherent parallelism. However, modern semiconductor technologies with densely packed structures present significant challenges in unbiasedly sampling transition domains in walk steps with multiple high-contrast dielectric materials. We present DeepRWCap, a machine learning-guided random walk solver that predicts the transition quantities required to guide each step of the walk. These include Poisson kernels, gradient kernels, signs and magnitudes of weight. DeepRWCap employs a two-stage neural architecture that decomposes structured outputs into face-wise distributions and spatial kernels on cube faces. It uses 3D convolutional networks to capture volumetric dielectric interactions and 2D depthwise separable convolutions to model localized kernel behavior. The design incorporates grid-based positional encodings and structural design choices informed by cube symmetries to reduce learning redundancy and improve generalization. Trained on 100,000 procedurally generated dielectric configurations, DeepRWCap achieves a mean relative error of 1.24±0.53% when benchmarked against the commercial Raphael solver on the self-capacitance estimation of 10 industrial designs spanning 12 to 55 nm nodes. Compared to the state-of-the-art stochastic difference method Microwalk, DeepRWCap achieves an average 23% speedup. On complex designs with runtimes over 10s, it reaches an average 49% acceleration.
Modern vision systems are deployed in settings where occasional catastrophic failures matter more than average accuracy--for example in medical imaging, autonomous driving, and safety monitoring. While conformal prediction gives distribution-free uncertainty guarantees, most existing methods only control mean error and are hard to tune toward rare but high-cost mistakes. We propose Bayesian-Quadrature Spectral Risk Control (BQ-SRC), a general framework for controlling tail-focused risks (such as conditional value at risk (CVaR)-style objectives) in a distribution-free way. BQ-SRC views conformal prediction through a Bayesian-quadrature lens and replaces mean-risk control with a flexible family of risk-averse criteria, while keeping the same black-box access to a trained model. A binomial testing scheme reduces the Monte Carlo conservatism of prior approaches, leading to tighter sets without sacrificing guarantees. We evaluate BQ-SRC across diverse vision tasks, including synthetic regression, closed-set and zero-shot image classification, multilabel classification, and semantic segmentation. Across these settings, BQ-SRC consistently maintains finite-sample risk guarantees and often yields smaller or otherwise more informative prediction sets than existing conformal and risk-controlling baselines, sometimes trading a modest amount of efficiency for stronger tail-risk control. The code will be publicly available at https://github.com/MohammadMahdiKazemi/BQ_SRC.
This work tackles a key challenge in test-time energy adaptation: prohibitive time overhead arising from recent state-of-the-art test-time adaptation (TTA) methods, which are built on energy models relying on iterative Monte Carlo or Langevin dynamics sampling with multiple stochastic updates per test instance to approximate energy gradients. We tackle the problem from an innovative control system perspective by i) describing the energy as a complex-valued wave, where the amplitude encodes energy uncertainty and the phase characterizes its evolution, and ii) maintaining a time-dependent wave equation that interprets TTA as a control system evolution process. By enforcing the control system law of probability current conservation, our method directs probability current away from high-energy (error-prone) regions toward low-energy (accurate) ones, achieving adaptive energy redistribution without additional stochastic sampling while preserving the overall normalization of the energy landscape. Experimentally, the proposed method significantly outperforms baseline methods across several public benchmark datasets, with adaptive time being only 1/3 1/7 of that required by the compared Top-1 to Top-3 baselines. Code is available at https://github.com/wongzbb/APT.
Rethinking Pose Refinement in 3D Gaussian Splatting under Pose Prior and Geometric Uncertainty
PDF ↗3D Gaussian Splatting (3DGS) has recently emerged as a powerful scene representation and is increasingly used for visual localization and pose refinement. However, despite its high-quality differentiable rendering, the robustness of 3DGS-based pose refinement remains highly sensitive to both the initial camera pose and the reconstructed geometry. In this work, we take a closer look at these limitations and identify two major sources of uncertainty: (i) pose prior uncertainty, which often arises from regression or retrieval models that output a single deterministic estimate, and (ii) geometric uncertainty, caused by imperfections in the 3DGS reconstruction that propagate errors into PnP solvers. Such uncertainties can distort reprojection geometry and destabilize optimization, even when the rendered appearance still looks plausible.To address these uncertainties, we introduce a relocalization framework that combines Monte Carlo pose sampling with Fisher Information-based PnP optimization. Our method explicitly accounts for both pose and geometric uncertainty and requires no retraining or additional supervision. Across diverse indoor and outdoor benchmarks, our approach consistently improves localization accuracy and significantly increases stability under pose and depth noise.
Providing accurate reward signals for code generated by large language models (LLMs) is a significant challenge in applying reinforcement learning (RL) to code generation. Existing methods rely on unit tests to evaluate code correctness and provide rewards, which are hindered by the difficulty of acquiring and verifying reliable unit tests at scale. In this work, we propose CodeRM-NT, a code reward model with no reliance on unit tests. Our method leverages Monte Carlo Tree Search guided by LLMs to generate code snippets and judges execution traces to annotate code with reward signals. We use the rewards to train CodeRM-NT that is capable of providing rewards for code during RL. CodeRM-NT also facilitates curriculum learning by scoring and sorting training samples based on their difficulty. Experimental results demonstrate that training with CodeRM-NT consistently outperforms synthetic unit test-based rewards, yielding superior performance on multiple code generation benchmarks. Additionally, curriculum learning based on CodeRM-NT further enhances model performance. Our code and dataset are available at: https://github.com/THUDM/CodeRM-NT.