Score-based Metropolis-Hastings for Fractional Langevin Algorithms Ahmed Aloui ahmed.aloui@duke.edu, Junyi Liao junyi.liao@duke.edu, Ali Hasan ali.hasan@morganstanley.com, Jose Blanchet jose.blanchet@stanford.edu, Vahid Tarokh vahid.tarokh@duke.edu Abstract Sampling from heavy-tailed and multimodal distributions is challenging when neither the target density nor the proposal density can be evaluated, as in α \alpha -stable Lévy-driven fractional Langevin algorithms. While the target distribution can be estimated from data via score-based or energy-based models, the α \alpha -stable proposal density and its score are generally unavailable, rendering classical density-based Metropolis–Hastings (MH) corrections impractical. Consequently, existing fractional Langevin methods operate in an unadjusted regime and can exhibit substantial finite-time errors and poor empirical control of tail behavior. We introduce the Metropolis-Adjusted Fractional Langevin Algorithm (MAFLA), an MH-inspired, fully score-based correction mechanism. MAFLA employs designed proxies for fractional proposal score gradients under isotropic symmetric α \alpha -stable noise and learns an acceptance function via Score Balance Matching. We empirically illustrate the strong performance of MAFLA on a series of tasks including combinatorial optimization problems where the method significantly improves finite time sampling accuracy over unadjusted fractional Langevin dynamics. 1 Introduction Sampling from heavy-tailed and multimodal distributions remains a fundamental challenge in Bayesian inference and generative modeling, especially when classical MCMC algorithms struggle to explore complex geometries ( 18 ; 17 ; 12 ) . Fractional Langevin samplers driven by symmetric \alpha -stable Lévy processes have recently emerged as a powerful alternative, offering long jumps and improved exploration in heavy-tailed regimes ( 24 ; 31 ; 21 ; 30 ) . However, implementing a classical density-based Metropolis–Hastings (MH) ( 8 ) correction for these samplers is essentially impossible in practice, since neither the target density nor the \alpha -stable proposal density admits a tractable closed form ( 13 ) . While p can be represented by an energy- or score-model, the conditional \alpha -stable proposal density remains intractable. As a consequence, existing fractional Langevin algorithms necessarily operate in an unadjusted regime; following 24 , we refer to these methods collectively as the Fractional Unadjusted Langevin Algorithm (FULA). Density-free approaches cannot provide a density-based MH-inspired correction in the fractional setting. State-of-the-art generative modeling techniques rely on score-based models ( 29 ; 26 ; 28 ) , which learn only the score \nabla\log p(x) rather than the log-density itself, making it infeasible to directly evaluate the density ratio required by the MH acceptance rule. While it is in principle possible to model the target density via an energy-based model ( 19 ) , this does not resolve the MH-inspired correction problem, since the proposal density remains unavailable. Independently of how the target distribution is modeled, classical MH requires access to the proposal density q(x^{\prime}\mid x) in order to compute the acceptance probability a(x^{\prime},x)=\min\Bigg\{1,\,\frac{p(x^{\prime})\,q(x\mid x^{\prime})}{p(x)\,q(x^{\prime}\mid x)}\Bigg\}. However, except for a few special cases (e.g., Cauchy, Gaussian) when q is an \alpha -stable distribution, its density does not admit a closed-form expression and is typically characterized only via its Fourier transform. The MH correction is particularly crucial in fractional Langevin dynamics, where \alpha -stable noise produces occasional long jumps that amplify finite-step discretization bias and strongly affect tail behavior ( 18 ) . Without this correction, FULA can lead to pronounced distortions in empirical tail statistics and mixture proportions, with these effects becoming more pronounced in higher dimensions. Moreover, as with unadjusted algorithms in general (both classical Langevin and fractional Langevin methods), the sampler becomes overly sensitive to the choice of step size when no MH correction is applied. Even moderate deviations in the step size and discretizations order can lead to degraded finite-time accuracy or numerical instability, further underscoring the motivation of an adjustment mechanism in the fractional setting ( 5 ) . Our key idea is that an MH-inspired adjustment for fractional Langevin dynamics can be carried out without ever evaluating any density . Instead of relying on intractable target and proposal densities, we enforce a gradient form of detailed balance: we approximate the proposal scores using only the target score and the location-family structure of isotropic symmetric \alpha -stable distributions, and we learn an acceptance function that satisfies this gradient constraint via Score Balance Matching (SBM) ( 1 ) . This yields a fully score-based Metropolis Adjusted Fractional Langevin Algorithm (MAFLA). Our contributions are: • We derive computable, density-free approximations of fractional Langevin proposal scores by exploiting the location-family structure of isotropic symmetric \alpha -stable distributions. • We adapt Score Balance Matching (SBM) to fractional Langevin dynamics, enabling the learning of an acceptance function that enforces detailed balance at the gradient level without evaluating any density. • We show that MAFLA significantly improves finite-time sampling for heavy-tailed targets, addressing the instability of unadjusted fractional Langevin dynamics. • We apply MAFLA to combinatorial optimization via continuous relaxations, showing consistent improvements on challenging problems such as MaxCut and minimum vertex cover, where enhanced exploration from fractional dynamics and stability from Metropolis adjustment jointly lead to higher-quality solutions. 2 Related Work Fractional Langevin Dynamics and Lévy-driven SDEs. The development of fractional dynamics for sampling is rooted in statistical physics and probability theory, long before their adoption in machine learning. Early work by 3 established Lévy-driven Langevin systems as principled models for anomalous diffusion, while 15 developed the mathematical foundations for approximating invariant measures of Lévy-driven SDEs. Building on these results, 24 formally introduced Fractional Langevin Monte Carlo (FLMC) to the machine learning community, and proposed approximating the non-local drift with a scaled local gradient, which leads to the Fractional Unadjusted Langevin algorithm (FULA). This “unadjusted” framework prompted several extensions: 23 incorporated momentum to obtain Fractional Underdamped Langevin Dynamics (FULD), and recent generative modeling approaches, including Lévy-driven score-based models ( 31 ) and Denoising Lévy Probabilistic Models (DLPM) ( 22 ) , leverage Lévy processes to better capture heavy-tailed structure. Beyond sampling and generative modeling, fractional dynamics have also been adapted to optimization; for instance, 30 demonstrated improved escape behavior in combinatorial optimization tasks. Score-based generative modeling. Score-based modeling originates from the classical score matching framework of 6 , later linked to denoising autoencoders by 29 , and further extended to scalable high-dimensional learning through sliced score matching ( 27 ) . Building on these foundations, score-based generative modeling was developed through noise-conditional score networks ( 26 ) and unified via stochastic differential equations in the reverse-time diffusion framework ( 28 ) . Recent work has extended score-based generative modeling to Lévy-driven SDEs ( 31 ; 22 ). Metropolis–Hastings, Langevin Dynamics, and Score-Based MCMC. Markov chain Monte Carlo (MCMC) methods originate from the Metropolis–Hastings (MH) algorithm, which enables sampling from complex distributions via an acceptance–rejection correction ( 8 ; 4 ). Incorporating gradient information into proposals led to Langevin-based methods, most notably the Metropolis-adjusted Langevin algorithm (MALA), which improves efficiency while preserving exact invariance of the target distribution ( 18 ; 17 ). Building on this idea, score-based MCMC has emphasized the score function as the primary object driving sampling dynamics ( 26 ; 28 ). More recently, 25 and 1 revisited MH-style corrections and introduced MH-like acceptance rules derived directly from score information, enabling MH-style corrections. Moreover, discrete time approximations and weak approximations for jump processes have been studied in the probability literature. For example 11 analyze Markov chain approximations to Lévy processes and establish sharp convergence rates of transition densities. Related approximations to scale functions for spectrally negative Lévy processes have also been developed ( 10 ) . In addition, Lévy processes have been extended to smooth manifolds using Marcus SDEs and generator characterizations ( 9 ) , which provides a rigorous foundation for jump driven dynamics on nonlinear state spaces. However, none of these papers propose an MH corrected Lévy Langevin sampler or work directly in the score-based setting. 3 Background 3.1 Fractional Langevin Algorithm Figure 1 : Illustration of symmetric \alpha -stable distributions for different tail indices \alpha . Smaller \alpha yields heavier tails and higher peak near the origin. Symmetric \alpha -stable distributions. Let \alpha\in(0,2] . A real-valued random variable X is said to follow a symmetric \alpha -stable distribution , denoted as X\sim\mathcal{S}\alpha\mathcal{S}(\sigma) , if its characteristic function is \mathbb{E}[e^{iuX}]=\exp\left(-\sigma^{\alpha}|u|^{\alpha}\right),\qquad u\in\mathbb{R}, where \sigma>0 is a scale parameter. Special cases include Gaussian ( \alpha=2 ) and Cauchy ( \alpha=1 ); otherwise closed forms are rare. Smaller \alpha yields heavier tails (Fig. 1 ). Tail behavior and moments. Symmetric \alpha -stable laws have finite moments only for orders <\alpha ; in particular, \mathrm{Var}(X)=\infty for \alpha<2 . In higher dimensions, a random vector L\in\mathbb{R}^{d} is said to be symmetric \alpha -stable if every one-dimensional projection \langle u,L\rangle is univariate symmetric \alpha -stable for all u\in\mathbb{R}^{d} . The characteristic function again uniquely specifies the distribution, while the density is typically intractable. In this work, we restrict attention to the isotropic case, where the characteristic function takes the form \mathbb{E}[e^{i\langle u,L\rangle}]=\exp(-\sigma^{\alpha}\|u\|^{\alpha}) . Lévy-driven stochastic differential equations. Let (L_{t})_{t\geq 0} be a Lévy process taking values in \mathbb{R}^{d} , thus L_{t} has stationary and independent increments and càdlàg sample paths. A Lévy-driven stochastic differential equation (or Lévy-type SDE) is formally written as: \mathrm{d}X_{t}=b(X_{t-})\,\mathrm{d}t+\sigma(X_{t})\,\mathrm{d}L_{t}, where: • b:\mathbb{R}^{d}\to\mathbb{R}^{d} is the drift vector field, • \sigma:\mathbb{R}^{d}\to\mathbb{R}^{d\times d} is the diffusion coefficient, • L_{t} is a Lévy noise, often symmetric and \alpha -stable in the context of fractional dynamics, and • X_{t-} denotes the left limit of the process (X_{t})_{t\geq 0} . When L_{t} is a symmetric \alpha -stable process with \alpha\in(0,2] , we denote it by (L_{t}^{\alpha})_{t\geq 0} ( 2 ; 20 ) . It satisfies: (i) L_{0}^{\alpha}=0 almost surely. (ii) For 00 and s\geq 0 , \mathbb{P}(|L_{t}^{\alpha}-L_{s}^{\alpha}|>\delta)\to 0\quad\text{as }t\to s. Fractional derivatives. Let f:\mathbb{R}^{d}\rightarrow\mathbb{R} belong to the Schwartz class \mathcal{S}(\mathbb{R}^{d}) . The Riesz fractional derivative ( 16 ) of order \gamma>0 is defined as: D^{\gamma}f(x)=\mathcal{F}^{-1}\{|\omega|^{\gamma}\hat{f}(\omega)\}, where \mathcal{F} denotes the Fourier transform and \hat{f}=\mathcal{F}f , with (\mathcal{F}f)(\omega)=\int_{\mathbb{R}^{d}}f(x)e^{-i2\pi\langle\omega,x\rangle}dx. Fractional Langevin Algorithm. Introduced in ( 24 ) , the fractional Langevin algorithm is a generalization of the Langevin algorithm to Lévy-driven dynamics. For a target density p on \mathbb{R}^{d} , the drift term is defined as follows: b(x)=\frac{D^{\alpha-2}\left(p(x)\nabla_{x}\log p(x)\right)}{p(x)}. In practice, this nonlocal drift is computationally intractable. Following 24 , we approximate the fractional drift by a scaled standard score. 3.2 Score Matching Score-based models are grounded in score matching ( 6 ) , which estimates the gradient of the log data density by minimizing the Fisher divergence between the estimated and true gradients of the log data distribution, defined as follows. Definition 1 (Fisher Divergence) . The Fisher divergence D_{\nabla}(p_{1}\|p_{2}) between two probability distributions p_{1} and p_{2} is defined as: D_{\nabla}(p_{1}\|p_{2})=\mathbb{E}_{x\sim p_{1}}\left[\|\nabla_{x}\log p_{1}(x)-\nabla_{x}\log p_{2}(x)\|^{2}\right]. Therefore, given a hypothesis class \mathcal{S}\subset\{s:\mathcal{X}\rightarrow\mathbb{R}^{d}\} , score matching seeks s^{*}\in\mathcal{S} that minimizes the Fisher divergence to the data distribution p : s^{*}\in\argmin_{s\in\mathcal{S}}\mathbb{E}_{x\sim p}\left[\|\nabla_{x}\log p(x)-s(x)\|^{2}\right] (1) Since the score function is not directly observed, 6 proved that minimizing in the loss function in Equation equation 1 is equivalent to minimizing the following loss function: \mathbb{E}_{x\sim p}\left[\frac{1}{2}\|s(x)\|^{2}+\operatorname{tr}\left(\nabla_{x}s(x)\right)\right]. (2) This formulation eliminates explicit dependence on the unknown data density, but requires computing the trace of the Jacobian of s , which can be expensive in high dimensions. To alleviate this issue, several practical variants have been proposed, including sliced score matching ( 27 ) and denoising score matching ( 29 ; 7 ) . Definition 2 (Sliced Score Matching) . Sliced score matching (SSM) replaces the Jacobian trace in equation 2 with a stochastic estimator by projecting onto random directions v\sim\mathcal{N}(0,I_{d}) : \mathbb{E}_{x\sim p,v\sim\mathcal{N}(0,I_{d})}\left[\frac{1}{2}\|s(x)\|^{2}+v^{\top}\nabla_{x}s(x)v\right]. (3) Definition 3 (Denoising Score Matching) . Given a noise distribution p_{\sigma}(\tilde{x}|x) , denoising score matching minimizes the objective \mathbb{E}_{x\sim p,\tilde{x}\sim p_{\sigma}(\tilde{x}|x)}\left[\|\nabla_{\tilde{x}}\log p_{\sigma}(\tilde{x}|x)-s(\tilde{x})\|^{2}\right]. (4) In this work, we adopt sliced score matching to learn an approximation to the score function of the target distribution from observed heavy-tailed samples, as it provides an efficient and scalable alternative to exact score matching in high dimensions. 3.3 Metropolis-Hastings The Metropolis–Hastings (MH) algorithm ( 8 ; 4 ) constructs a Markov chain using an acceptance function a:\mathcal{X}\times\mathcal{X}\rightarrow[0,1] , which defines the probability a(x^{\prime},x) of transitioning from the current state x\in\mathcal{X} to a proposed state x^{\prime}\in\mathcal{X} . A common choice of the acceptance function is given by: a(x^{\prime},x)=\min\left\{1,\frac{p(x^{\prime})q(x|x^{\prime})}{p(x)q(x^{\prime}|x)}\right\} (5) where p(x) is the target distribution and q(x|x^{\prime}) is the proposal distribution. The MH algorithm proceeds as follows: • Initialize: Choose an initial state x_{1}\in\mathcal{X} , a proposal distribution q(x^{\prime}|x) , and the number of iterations T . • For t=1,\dots,T : – Propose x^{\prime}\sim q(x^{\prime}|x_{t}) . – Compute the acceptance probability a(x^{\prime},x_{t}) equation 5 . – Draw u\sim U(0,1) . If u\leq a(x^{\prime},x_{t}) , accept x^{\prime} and set x_{t+1}=x^{\prime} ; otherwise, set x_{t+1}=x_{t} . Note that evaluating the acceptance probability in equation 5 requires access to the target density p(x) up to a normalizing constant. Detailed Balance. Although the acceptance function is often defined by Equation equation 5 , a sufficient condition for ensuring convergence to the target distribution is that the acceptance ratio satisfies the detailed balance condition: \forall x,x^{\prime}\in\mathcal{X},\quad\frac{a(x^{\prime},x)}{a(x,x^{\prime})}=\frac{p(x^{\prime})\,q(x\mid x^{\prime})}{p(x)\,q(x^{\prime}\mid x)}. (6) Here, p(x) denotes the target probability density, and q(x^{\prime}|x) denotes the proposal transition density. In particular, any acceptance function satisfying the detailed balance condition above ensures that the Markov chain admits p(x) as its unique stationary distribution. 4 Approximating Proposal Scores We now describe the fractional Langevin proposals used in MAFLA. We assume access to the target score s_{\theta}(x)\approx\nabla_{x}\log p(x), e.g., given by a trained deep neural network modeling the score function. Following 24 , we approximate the nonlocal fractional drift: \tilde{b}(x)=c_{\alpha}\nabla_{x}\log p(x),\qquad c_{\alpha}=\frac{\Gamma(\alpha-1)}{\Gamma(\alpha/2)^{2}}, (7) for \alpha\in(1,2] , where \Gamma(\cdot) is the Gamma function. Lévy-driven proposal and location-family structure. Let \mathcal{S}\alpha\mathcal{S}(1) denote the standard symmetric \alpha -stable distribution on \mathbb{R}^{d} with unit scale. Given a step size \tau>0 and an \alpha -stable random vector \xi\sim\mathcal{S}\alpha\mathcal{S}(1) , we define the Lévy-driven proposal: x^{\prime}=x+\tau\,\tilde{b}(x)+\tau^{1/\alpha}\xi,\qquad\xi\sim\mathcal{S}\alpha\mathcal{S}(1). (8) Conditioned on x , the proposal x^{\prime} follows a symmetric \alpha -stable location family with density q(x^{\prime}|x)=\tau^{-d/\alpha}\,f_{\alpha}\!\left(\frac{x^{\prime}-x-\tau\tilde{b}(x)}{\tau^{1/\alpha}}\right), (9) where f_{\alpha} denote the (intractable) density of the standard symmetric \alpha -stable distribution. For most values of \alpha , the functional form of f_{\alpha} has no closed form expression 1 1 1 While f_{\alpha} admits an integral representation via the inverse Fourier transform (e.g., a Hankel–Bessel integral for radial characteristic functions), no closed-form is available for most \alpha . . Therefore, neither q(x^{\prime}\mid x) nor its logarithm can be evaluated explicitly, and hence we cannot compute the classical MH acceptance ratio. Fractional proposal scores. Intuitively, while the proposal density itself is unavailable, its score can be approximated through the structure of the \alpha -stable location family and fractional calculus, which enables gradient-based corrections without explicit density evaluation. In our setting, even if though the density f_{\alpha} is intractable, its associated fractional score admits a closed form expression. Define r=x^{\prime}-x-\tau\tilde{b}(x),\qquad r_{\mathrm{rev}}=x-x^{\prime}-\tau\tilde{b}(x^{\prime}). From 31 , for \alpha\in(1,2] , the fractional score of a symmetric isotropic \alpha -stable location family with scale \tau^{1/\alpha} is given by \displaystyle S^{(\alpha)}_{q}(x^{\prime}|x) \displaystyle=\frac{D^{\alpha-2}\left(q(x^{\prime}|x)\nabla_{x^{\prime}}\log q(x^{\prime}|x)\right)}{q(x^{\prime}|x)} \displaystyle=-\frac{1}{\gamma^{\alpha-1}}\cdot\frac{1}{\alpha}\cdot\left(\frac{x^{\prime}-x-\tau\tilde{b}(x)}{\gamma}\right), where \gamma=\tau^{1/\alpha} . We can simplify this to S^{(\alpha)}_{q}(x^{\prime}|x)=-\frac{1}{\alpha}\,\frac{x^{\prime}-x-\tau\tilde{b}(x)}{\tau}=-\frac{1}{\alpha\tau}\,r. According to ( 24 ) , we approximate the log-gradient by a scaled fractional score, \nabla_{x^{\prime}}\log q(x^{\prime}|x)\approx c_{\alpha}^{-1}S^{(\alpha)}_{q}(x^{\prime}|x) , to obtain \nabla_{x^{\prime}}\log q(x^{\prime}|x)\approx-\kappa\,r,\qquad\kappa=\frac{1}{\alpha\,c_{\alpha}\,\tau}. (10) For \alpha\in(1,2] and small step size \tau , the scaled fractional score provides a first-order approximation to the ordinary score in the local regime where proposals concentrate, with higher-order errors vanishing as \tau\to 0 . This approximation is sufficient for enforcing detailed balance at the gradient level in the SBM objective. To find the gradient with respect to x , define z=(x^{\prime}-m(x))/\tau^{1/\alpha} with the location map m(x)=x+\tau\tilde{b}(x) . Then \nabla_{x}z=-\tau^{-1/\alpha}(I+\tau J_{\tilde{b}}(x)), where J_{\tilde{b}}(x) is the Jacobian of \tilde{b} . By the chain rule, \displaystyle\nabla_{x}\log q(x^{\prime}|x) \displaystyle=(\nabla_{x}z)^{\top}\nabla_{z}\log f_{\alpha}(z) \displaystyle=-(I+\tau J_{\tilde{b}}(x))^{\top}\nabla_{x^{\prime}}\log q(x^{\prime}|x). Substituting equation 10 yields \nabla_{x}\log q(x^{\prime}|x)\approx\kappa\,(r+\tau J_{\tilde{b}}(x)^{\top}r). Applying the same argument to the reverse proposal q(x|x^{\prime}) and exchanging x\leftrightarrow x^{\prime} gives the complete set of approximate proposal gradients: \displaystyle\nabla_{x^{\prime}}\log q(x^{\prime}|x) \displaystyle\approx-\kappa\,r, (11) \displaystyle\nabla_{x}\log q(x^{\prime}|x) \displaystyle\approx\kappa\,(r+\tau J_{\tilde{b}}(x)^{\top}r), \displaystyle\nabla_{x}\log q(x|x^{\prime}) \displaystyle\approx-\kappa\,r_{\mathrm{rev}}, \displaystyle\nabla_{x^{\prime}}\log q(x|x^{\prime}) \displaystyle\approx\kappa\,(r_{\mathrm{rev}}+\tau J_{\tilde{b}}(x^{\prime})^{\top}r_{\mathrm{rev}}). which we refer to as the proposal scores . These expressions are computable from samples and the drift approximation equation 7 , without ever evaluating the density f_{\alpha} . (a) Target data. Mixture weights (0.2,0.8) . (b) FULA. Empirical weights (0.26,0.74) . (c) MAFLA. Empirical weights (0.21,0.79) . Figure 2 : Qualitative comparison on a 2D \alpha -stable mixture with weights (0.2,0.8) for \alpha=1.95 . MAFLA produces samples that visually match both modes and mixture weights more closely than FULA, which oversamples the left mode and exhibits noisier samples. Figure 3 : Effect of the proposal stability index. Left: Mean W_{1} distance for FULA and MAFLA over a grid of target \alpha_{\text{tgt}} and proposal \alpha_{\text{prop}} . Right: Best 95\% quantile error (mean \pm std over runs) as a function of \alpha_{\text{tgt}} , comparing FULA (gray) and MAFLA (blue). Algorithm 1 Parallel Score-based Metropolis-Adjusted Fractional Langevin Algorithm (MAFLA) 1: Number of particles N , initial states (x_{0}^{(i)})_{i=1}^{N}\subset\mathbb{R}^{d} , step size \tau>0 , stability index \alpha\in(1,2] , number of iterations T , score network s_{\theta}(x) , acceptance network a_{\phi}(x^{\prime},x) . 2: Compute the scaling constant c_{\alpha}=\Gamma(\alpha-1)/\Gamma(\alpha/2)^{2} . 3: for t=0 to T-1 do 4: Drift computation (batched): \tilde{b}^{(i)}\leftarrow c_{\alpha}\,s_{\theta}\big(x_{t}^{(i)}\big) for all i=1,\dots,N . 5: Sample Lévy noise (batched): draw \xi_{t}^{(i)}\sim\mathcal{S}\alpha\mathcal{S}(1) independently for all i=1,\dots,N . 6: Propose (batched): x^{\prime(i)}\leftarrow x_{t}^{(i)}+\tau\,\tilde{b}^{(i)}+\tau^{1/\alpha}\xi_{t}^{(i)} for all i . 7: Acceptance probabilities (batched): \alpha_{t}^{(i)}\leftarrow a_{\phi}\big(x^{\prime(i)},x_{t}^{(i)}\big) for all i . 8: Draw u^{(i)}\sim\mathrm{Unif}(0,1) independently for all i . 9: for i=1 to N do 10: if u^{(i)}<\alpha_{t}^{(i)} then 11: x_{t+1}^{(i)}\leftarrow x^{\prime(i)} \triangleright accept 12: else 13: x_{t+1}^{(i)}\leftarrow x_{t}^{(i)} \triangleright reject 14: end if 15: end for 16: end for 17: return \big(x_{t}^{(i)}\big)_{t=0}^{T}{}_{,\,i=1}^{N} . 5 Score Balance Matching Following ( 1 ) , we now explain how to learn an acceptance function a(x^{\prime},x) using only target and proposal scores. Gradient form of detailed balance. Let p denote the target distribution with score \nabla\log p(x) and q a proposal kernel. A Metropolis–Hastings transition with proposal q and acceptance function a:\mathcal{X}^{2}\to[0,1] satisfies the detailed balance condition: i.e., for every x,x^{\prime}\in\mathbb{R}^{d} p(x)\,q(x^{\prime}\mid x)\,a(x,x^{\prime})=p(x^{\prime})\,q(x\mid x^{\prime})\,a(x^{\prime},x) (12) Assuming a(x^{\prime},x)>0 on the support of p(x)\,q(x^{\prime}|x) , taking the logarithm and gradient with respect to (x,x^{\prime}) yields \displaystyle\nabla\log p(x)+\nabla\log q(x^{\prime}|x)+\nabla\log a(x,x^{\prime})=\nabla\log p(x^{\prime})+\nabla\log q(x|x^{\prime})+\nabla\log a(x^{\prime},x), (13) where \nabla=(\nabla_{x},\nabla_{x^{\prime}}) . This condition depends only on target scores, proposal score gradients, and acceptance score gradients, without requiring evaluation of any density. The equivalence between equation 12 and equation 13 is shown in Appendix A.2 . Score Balance Matching (SBM). Using the gradient detailed balance condition equation 13 , we learn an acceptance function a(x^{\prime},x)\in(0,1] by minimizing the Score Balance Matching objective \mathcal{L}_{2}(a)\!=\!\mathbb{E}\left[\big\|\nabla\log a(x^{\prime},x)\!-\!\nabla\log a(x,x^{\prime})\!-\!\Delta_{p}\!-\!\Delta_{q}\big\|_{2}^{2}\right], (14) where \displaystyle\Delta_{p} \displaystyle:=\nabla\log p(x^{\prime})-\nabla\log p(x), \displaystyle\Delta_{q} \displaystyle:=\nabla\log q(x|x^{\prime})-\nabla\log q(x^{\prime}|x). Minimizing equation 14 encourages a to satisfy detailed balance while avoiding evaluation of p and q (up to normalizing constants). Fractional variant of the SBM objective. Motivated by the \alpha -stable dynamics (Section 4 ), we introduce a fractional variant of the SBM objective, which is an \alpha -norm version of the loss: \mathcal{L}_{\alpha}(a)\!=\!\mathbb{E}\left[\!\left\|\nabla\log a(x^{\prime},x)\!-\!\nabla\log a(x,x^{\prime})\!-\!\Delta_{p}\!-\!\Delta_{q}\right\|_{\alpha}^{\alpha}\right]. (15) where \|\cdot\|_{\alpha} is the \ell_{\alpha} norm. We then combine the two objectives into a single training criterion: \mathcal{L}(a)=\mathcal{L}_{2}(a)+\lambda_{\alpha}\,\mathcal{L}_{\alpha}(a), (16) with \lambda_{\alpha}\geq 0 controlling the contribution of the fractional loss component. Entropy regularization. To avoid degenerate near-zero acceptance, we add an entropy penalty as in 1 , we augment the loss with an entropy term: \displaystyle\mathcal{L}_{r}(a) \displaystyle=\mathcal{L}(a)+\lambda\,\mathbb{E}\!\left[H(a(x^{\prime},x))\right], (17) where \displaystyle H(a(x^{\prime},x)) \displaystyle=a(x^{\prime},x)\,\log a(x^{\prime},x)+\big(1-a(x^{\prime},x)\big)\log\!\big(1-a(x^{\prime},x)\big), (18) and \lambda\geq 0 controls the strength of entropy regularization. Minimizing this term encourages acceptance probabilities with higher entropy, preventing collapse to trivial or uninformative solutions. In practice, SBM enforces gradient balance only approximately, since both the target score and the proposal scores are themselves approximations. We do not provide theoretical bounds linking these approximations to stationarity error, and therefore rely on empirical validation. Establishing such guarantees is an important direction for future work. 6 Metropolis-Adjusted Fractional Langevin We now present the practical algorithm combining fractional Langevin proposals and an SBM-trained acceptance function. Training the acceptance network. We parameterize the acceptance function by a neural network a_{\phi}:\mathbb{R}^{d}\times\mathbb{R}^{d}\to(0,1) , typically of the form a_{\phi}(x^{\prime},x)=\sigma(g_{\phi}(x^{\prime},x)), where g_{\phi} is an unconstrained neural network, i.e, g_{\phi}:\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R} , learning the acceptance logits, and \sigma denotes the logistic sigmoid. Figure 4 : Quantile error ratio. MAFLA uniformly dominates as the ratio is greater than 1 . Curriculum interpolation for SBM training. To stabilize training, we generate training pairs using a convex interpolation between data samples and proposal samples: x^{\prime(i)}=\eta v^{\prime}+(1-\eta)\tilde{x} , with \tilde{x}\sim p and v^{\prime}\sim q(\cdot\mid\tilde{x}) , where \eta\in[0,1] controls how much x^{\prime} deviates from the data distribution towards the proposal. In the first epochs of training, we begin with smaller values of \eta to favor data from the true distribution, and then gradually increase \eta to estimate the acceptance function around the proposal region. This approach is motivated by the fact that the score function may not be well-estimated outside of the data region, and starting with smaller \eta helps prevent biasing the training. In practice, we replace the target score \nabla\log p with the learned score s_{\theta}(x) , and the proposal score gradients \nabla\log q with the approximate proposal scores equation 11 . Algorithm 1 presents MAFLA (parallel multistart). We use the parallel form in all experiments for scalability and fair comparison with FULA. For completeness, the sequential version of MAFLA (Algorithm 2 ) is presented in the appendix. 7 Experiments We evaluate MAFLA against FULA on heavy-tailed sampling and combinatorial optimization. Heavy-tailed mixtures. We first sample from a 2-component \alpha -stable mixture with \alpha=1.95 (Fig. 2 ), where MH correction remains crucial even near the Gaussian regime. MAFLA improves mixture weight recovery and reduces error from W_{1}=4.87 (FULA) to 0.52 , and the 0.99 -quantile error from 80.33 to 0.80 (Fig. 4 ). Proposal index misspecification. We vary the proposal stability \alpha_{\text{prop}} across targets \alpha_{\text{tgt}} using a 4-D symmetric \alpha -stable location family with mean (1,2,3,4) . Over the (\alpha_{\text{tgt}},\alpha_{\text{prop}}) grid, MAFLA consistently yields smaller mean W_{1} and improves the best 95\% quantile error per \alpha_{\text{tgt}} by \sim 3 – 5\times , while being less sensitive to \alpha_{\text{prop}} misspecification (Fig. 3 ). Step-size sensitivity. On a 4-D \alpha -stable mixture with \alpha=1.5 , we vary \tau over three orders of magnitude and report W_{1} , q_{0.95} , and q_{0.99} errors. Errors increase with \tau for both methods, but MAFLA consistently attains lower W_{1} and tail errors, indicating improved robustness to step-size misspecification (Fig. 5 ). Scaling with dimension. For a symmetric bimodal \alpha -stable mixture with modes \pm\mathbf{1}_{d} and weights 0.6/0.4 at \alpha=1.9 , we vary d\in\{8,12,16,20,24,28,32\} . Both samplers degrade with d , but MAFLA remains better across all dimensions, reducing W_{1} by \sim 20 – 35\% and improving 95\%/99\% tail errors (Fig. 6 ). Combinatorial optimization. Using continuous relaxations with explicit score functions (Appendix B ), we apply ULA/FULA/MALA/MAFLA to MaxCut and minimum vertex cover on ER and BA graphs with N\in\{64,256,512,1024\} . For MaxCut, MAFLA achieves the best mean and best-found cuts across all settings (Table 1 ). For vertex cover, MAFLA yields the smallest mean and best cover sizes and the lowest uncovered-edge ratio before greedy decoding (Table 2 in the Appendix), indicating improved solution quality and feasibility. These gains can be attributed to the complementary roles of fractional dynamics and Metropolis adjustment: the heavy-tailed fractional noise encourages broader exploration and facilitates escape from poor local minima, while the learned acceptance function selectively filters unlikely proposals, stabilizing the sampling dynamics and enforcing detailed balance. 8 Conclusion We propose MAFLA, an MH-inspired \alpha -stable Lévy sampler for settings where both target and proposal densities are intractable. MAFLA replaces density ratios with a gradient-form detailed balance objective, combining score-based fractional drift approximations, closed-form proposal-score proxies for symmetric isotropic \alpha -stable location families, and a learned acceptance function trained via Score Balance Matching. Across heavy-tailed targets, MAFLA improves over FULA in W_{1} and tail-quantile error, and is more robust to \alpha , step size, and dimension; it also performs competitively on MaxCut and vertex cover, outperforming ULA, FULA, and MALA. Table 1 : MaxCut results on Barabási–Albert (BA) and Erdős–Rényi (ER) graphs. Reported as mean \pm std over runs, plus best cut found. The superscript ↑ means higher values are preferred. N Sampler Barabási–Albert ( m=2 ) Erdős-Rényi ( p=0.1 ) Energy ( \mu\pm\sigma ) Cut ↑ ( \mu\pm\sigma ) Best ↑ Energy ( \mu\pm\sigma ) Cut ↑ ( \mu\pm\sigma ) Best ↑ 64 ULA -1.20\pm 1.16 67.97\pm 5.58 90 -3.89\pm 2.02 214.50\pm 9.68 253 FULA -2.93\pm 1.35 74.46\pm 5.46 92 -6.22\pm 2.49 222.21\pm 10.04 256 MALA -0.99\pm 1.05 67.23\pm 5.48 87 -3.23\pm 1.89 212.32\pm 9.70 249 MAFLA -3.66\pm 1.38 \mathbf{77.72\pm 5.70} 100 -6.85\pm 2.55 \mathbf{225.03\pm 10.41} \mathbf{264} 256 ULA -1.22\pm 1.16 265.48\pm 11.22 311 -15.24\pm 4.02 3391.87\pm 38.36 3530 FULA -4.88\pm 1.40 295.13\pm 11.43 335 -24.83\pm 4.94 3455.98\pm 39.79 3621 MALA -1.02\pm 1.09 264.25\pm 11.16 305 -12.46\pm 3.75 3373.21\pm 38.58 3519 MAFLA -7.31\pm 1.36 \bf 316.59\pm 11.33 361 -34.35\pm 7.05 \mathbf{3536.37\pm 60.00} 3728 512 ULA -1.25\pm 1.16 526.54\pm 15.83 579 -30.08\pm 5.70 13432.87\pm 76.49 13749 FULA -6.11\pm 1.41 583.23\pm 16.33 633 -49.45\pm 7.01 13615.99\pm 80.01 13881 MALA -1.01\pm 1.08 524.27\pm 15.84 592 -24.46\pm 5.21 13379.40\pm 75.47 13697 MAFLA -9.04\pm 1.36 \bf 620.95\pm 16.20 685 -63.60\pm 7.96 \bf 13780.58\pm 91.54 14093 1024 ULA -1.27\pm 1.18 1045.70\pm 22.65 1129 -59.38\pm 8.02 53142.28\pm 152.80 53661 FULA -7.38\pm 1.39 1148.52\pm 23.01 1237 -97.93\pm 9.66 53659.39\pm 156.13 54212 MALA -1.00\pm 1.09 1041.65\pm 22.99 1116 -48.22\pm 7.60 52989.74\pm 154.92 53598 MAFLA -10.02\pm 1.39 \bf 1197.17\pm 23.54 1278 -142.51\pm 11.13 \bf 54396.39\pm 182.21 55244 Figure 5 : Sensitivity to step size \tau for FULA and MAFLA in a 4 -D \alpha -stable mixture, with \alpha=1.5 . Left: 99\% quantile error. Center: 95\% quantile error. Right: Wasserstein distance W_{1} . MAFLA exhibits lower errors across all \tau and improves tail behavior. Figure 6 : Scaling with dimension for FULA and MAFLA on a d -dimensional symmetric \alpha -stable bimodal mixture with modes at \pm\mathbf{1}_{d} and mixture weights 0.6/0.4 . Left: Wasserstein distance W_{1} . Center: 95\% quantile error. Right: 99\% quantile error. Curves show mean \pm standard error over three runs. Appendix A Appendix A.1 MAFLA Here we include the sequential version of the MAFLA algorithm (Alg. 2 ). While it corresponds to the standard Metropolis–Hastings algorithm, in higher dimensions the multi-particle version is more stable and more scalable, as the different particles can run in parallel and we avoid the need for large burn-in and lag parameters that would significantly slow down the sampling procedure. Moreover, the parallel version allows for a fair comparison with FULA, since both methods are run for the same number of steps with the same number of particles. Algorithm 2 Score-based Metropolis-Adjusted Fractional Langevin Algorithm (MAFLA) 1: Initial state x_{0}\in\mathbb{R}^{d} , step size \tau>0 , stability index \alpha\in(1,2] , number of iterations T , score network s_{\theta}(x) , acceptance network a_{\phi}(x^{\prime},x) . 2: Compute the scaling constant c_{\alpha}=\Gamma(\alpha-1)/\Gamma(\alpha/2)^{2} . 3: for t=0 to T-1 do 4: Drift computation: \tilde{b}(x_{t})\leftarrow c_{\alpha}\,s_{\theta}(x_{t}) . 5: Sample Lévy noise: draw \xi_{t}\sim\mathcal{S}\alpha\mathcal{S}(1) . 6: Propose: x^{\prime}\leftarrow x_{t}+\tau\,\tilde{b}(x_{t})+\tau^{1/\alpha}\xi_{t} . 7: Acceptance probability: \alpha_{t}\leftarrow a_{\phi}(x^{\prime},x_{t}) . 8: Draw u\sim\mathrm{Unif}(0,1) . 9: if u<\alpha_{t} then 10: x_{t+1}\leftarrow x^{\prime} \triangleright accept 11: else 12: x_{t+1}\leftarrow x_{t} \triangleright reject 13: end if 14: end for 15: return (x_{t})_{t=0}^{T} . A.2 Score Balance Matching In this section, we recall a lemma from 1 showing that the gradient form of the detailed balance condition introduced in Section 5 is equivalent to the standard detailed balance equation. Lemma 1 (Gradient Detailed Balance Equivalence) . Let \mathcal{X}\subseteq\mathbb{R}^{d} and assume that the target density p:\mathcal{X}\to\mathbb{R}_{+} , the proposal density q(\cdot\mid x):\mathcal{X}\to\mathbb{R}_{+} , and the acceptance function a:\mathcal{X}\times\mathcal{X}\to(0,1] are differentiable. Then the following statements are equivalent for all x,x^{\prime}\in\mathcal{X} : (i) (Detailed balance) p(x)\,q(x^{\prime}\mid x)\,a(x,x^{\prime})=p(x^{\prime})\,q(x\mid x^{\prime})\,a(x^{\prime},x). (ii) (Gradient detailed balance) \nabla\log p(x)+\nabla\log q(x^{\prime}\mid x)+\nabla\log a(x,x^{\prime})=\nabla\log p(x^{\prime})+\nabla\log q(x\mid x^{\prime})+\nabla\log a(x^{\prime},x), where \nabla=(\nabla_{x},\nabla_{x^{\prime}}) . A.3 Symmetric Proposal: Score-based Fractional Random Walk For completeness we include a discussion about symmetric proposals, e.g., fractional random walk, we prove an equivalence result showing that training any acceptance function (any function that verifies the detailed balance condition) is equivalent to training an energy function. We then confirm empirically that training an energy model directly (with score matching) and performing the MH correction with the learned energy (as the proposal is not needed) has equivalent performance to training a score model and then an acceptance function. A.3.1 Equivalence Result We begin from the log detailed balance condition, for a>0 , \log\frac{a(x^{\prime},x)}{a(x,x^{\prime})}\;=\;\log p(x^{\prime})-\log p(x)+\log q(x\mid x^{\prime})-\log q(x^{\prime}\mid x). When the proposal is symmetric (e.g. Random Walk Metropolis–Hastings), the ratio simplifies to \log\frac{a(x^{\prime},x)}{a(x,x^{\prime})}\;=\;\log p(x^{\prime})-\log p(x). We show that any acceptance function satisfying this identity admits a decomposition of the form a(x^{\prime},x)\;=\;f(x)\,g(x^{\prime})\,r(x^{\prime},x), where f,g:\mathcal{X}\to\mathbb{R}_{+} and r:\mathcal{X}\times\mathcal{X}\to\mathbb{R}_{+} is symmetric, i.e. r(x^{\prime},x)=r(x,x^{\prime}) . Let \psi(x,x^{\prime})=\log\frac{a(x^{\prime},x)}{a(x,x^{\prime})},\qquad h_{1}(x)=-\log p(x),\quad h_{2}(x^{\prime})=\log p(x^{\prime}). Then the gradient form of detailed balance is \nabla\psi(x,x^{\prime})=\nabla h_{1}(x)+\nabla h_{2}(x^{\prime}), which integrates to \psi(x,x^{\prime})=h_{1}(x)+h_{2}(x^{\prime})+C for some constant C . Writing \alpha=e^{C} , \frac{a(x^{\prime},x)}{a(x,x^{\prime})}=\alpha\,e^{h_{1}(x)}e^{h_{2}(x^{\prime})}. We now establish the decomposition formally. Lemma 2 . For a:\mathcal{X}\times\mathcal{X}\to(0,1] , the following are equivalent: (i) There exist functions \tilde{h}_{1},\tilde{h}_{2}:\mathcal{X}\to\mathbb{R} such that \frac{a(x^{\prime},x)}{a(x,x^{\prime})}=\exp(\tilde{h}_{1}(x))\,\exp(\tilde{h}_{2}(x^{\prime})). (ii) There exist f,g:\mathcal{X}\to\mathbb{R}_{+} and a symmetric r:\mathcal{X}\times\mathcal{X}\to\mathbb{R}_{+} such that a(x^{\prime},x)=f(x)\,g(x^{\prime})\,r(x^{\prime},x). Proof. (i) \Rightarrow (ii). Define r(x^{\prime},x)=\sqrt{a(x^{\prime},x)\,a(x,x^{\prime})},\qquad f(x)=e^{\tilde{h}_{1}(x)/2},\quad g(x^{\prime})=e^{\tilde{h}_{2}(x^{\prime})/2}. A direct calculation shows a(x^{\prime},x)=f(x)\,g(x^{\prime})\,r(x^{\prime},x). (ii) \Rightarrow (i). Define \tilde{h}_{1}(x)=\log f(x) and \tilde{h}_{2}(x^{\prime})=\log g(x^{\prime}) . Symmetry of r yields \frac{a(x^{\prime},x)}{a(x,x^{\prime})}=\frac{f(x)g(x^{\prime})}{f(x^{\prime})g(x)}=\exp(\tilde{h}_{1}(x))\,\exp(\tilde{h}_{2}(x^{\prime})), which gives (i). ∎ Applying Lemma 2 to the detailed balance identity yields \log\frac{f(x)g(x^{\prime})}{f(x^{\prime})g(x)}=\log p(x^{\prime})-\log p(x). Taking gradients with respect to x and x^{\prime} , \nabla_{x}\bigl(\log g(x)-\log f(x)\bigr)=\nabla_{x}\log p(x),\qquad\nabla_{x^{\prime}}\bigl(\log g(x^{\prime})-\log f(x^{\prime})\bigr)=\nabla_{x^{\prime}}\log p(x^{\prime}). Thus, \log g-\log f recovers the target energy up to constants, while the symmetric factor r controls the residual flexibility of the acceptance rule. This decomposition motivates parameterizing the acceptance function with three neural networks f , g , and a symmetric r , allowing the model to learn the target energy through \log f-\log g while ensuring valid acceptance probabilities through the symmetric component r . We therefore summarize a class of fractional-proposal Metropolis–Hastings (MH) algorithms (Fig. 7 ). If the proposal is symmetric, training an energy model is mathematically equivalent to training a score model together with an acceptance function, enabling MH correction. However, for non-symmetric fractional proposals (e.g., Fractional Langevin, Fractional Hamiltonian Monte Carlo), the proposal density is not tractable, and training an energy model alone is not sufficient to perform MH correction. Fractional Metropolis–Hastings Symmetric fractional proposal (i) Energy model (ii) score model + acceptance model e.g., FRW Non-symmetric fractional proposal Score model + acceptance model e.g., MAFLA Figure 7 : Schematic overview of Fractional Metropolis–Hastings Algorithms. A.4 Numerical Approximation of the Fractional Drift A.4.1 Riesz Fractional Derivative Approximation The fractional drift in our Langevin dynamics is governed by the Riesz fractional derivative of order \gamma=\alpha-2 , defined as \mathcal{D}^{\gamma}f(x)=\mathcal{F}^{-1}\{|\omega|^{\gamma}\hat{f}(\omega)\} . Due to the non-local nature of this operator, exact evaluation is intractable. To implement this in the Metropolis-Adjusted Fractional Langevin Algorithm (MAFLA), we employ a discretized approximation based on fractional centered differences. Following 14 and 24 , the Riesz derivative can be approximated by the limit of the centered difference operator \Delta_{h}^{\gamma} : \mathcal{D}^{\gamma}f(x)=\lim_{h\to 0}\frac{1}{h^{\gamma}}\sum_{k=-\infty}^{\infty}g_{\gamma,k}f(x-kh), (19) where h>0 is the discretization step size. The coefficients g_{\gamma,k} are given by the ratio of Gamma functions: g_{\gamma,k}=(-1)^{k}\frac{\Gamma(\gamma+1)}{\Gamma(\frac{\gamma}{2}-k+1)\Gamma(\frac{\gamma}{2}+k+1)}. (20) For computational tractability, we truncate the infinite summation to a finite window size K\in\mathbb{N} , resulting in the truncated fractional centered difference operator \Delta_{h,K}^{\gamma} : \Delta_{h,K}^{\gamma}f(x):=\frac{1}{h^{\gamma}}\sum_{k=-K}^{K}g_{\gamma,k}f(x-kh). (21) A.4.2 Score-Based Implementation In the context of score-based modeling, we do not have access to the unnormalized density f_{\pi}(x)=p(x) . The fractional drift requires the term \mathcal{D}^{\alpha-2}(p(x)\nabla\log p(x))/p(x) . Applying the discrete operator to the density-weighted score p(x)s(x) , we obtain: \tilde{b}_{h,K}(x)\approx\frac{1}{h^{\alpha-2}}\sum_{k=-K}^{K}g_{\alpha-2,k}\frac{p(x-kh)}{p(x)}s_{\theta}(x-kh), (22) where s_{\theta}(x)\approx\nabla\log p(x) is the learned score network. The density ratio \frac{p(x-kh)}{p(x)} is estimated by integrating the score function along the path from x to x-kh , approximated via the trapezoidal rule. A.4.3 Error Analysis and Hyperparameters The accuracy of this approximation depends on the interplay between the step size h and the truncation order K . Assuming sufficient regularity of the target density, the approximation error is bounded by: \left|\mathcal{D}^{\gamma}f(x)-\Delta_{h,K}^{\gamma}f(x)\right|=\mathcal{O}\left(h^{2}+\frac{1}{hK}\right). (23) This bound highlights a critical trade-off: • Discretization Error ( h^{2} ): Reduces as h\to 0 , favoring smaller step sizes for local accuracy. • Truncation Error ( (hK)^{-1} ): Increases as h\to 0 if K is fixed. This term reflects the heavy-tailed nature of the operator; as the grid becomes finer (smaller h ), the window K must effectively grow to capture the non-local interactions of the tails. A.4.4 Ablation Study: Approximation Order K and Drift Step h While we utilized the robust zeroth-order drift approximation ( K=0 ) for the main results, the proposed framework allows for higher-order Riesz derivative approximations ( K\geq 1 ) as defined in equation equation 22 . In this section, we investigate the sensitivity of S-MAFLA to the truncation order K and the discretization step size h , seeking to characterize the trade-off between approximation fidelity and stability. We evaluated the sampler on \alpha -stable targets with \alpha\in\{1.2,1.5,1.8\} and mean \mu=5.0 , varying K\in\{0,1,3,5\} and h\in[10^{-3},10^{-1}] . The results, summarized in Figure 8 , reveal two key insights: • Performance Ceiling of Higher-Order Approximations: When the discretization step h is finely tuned, higher-order approximations can significantly outperform the robust K=0 baseline. For example, in the heavy-tailed regime ( \alpha=1.2 ), increasing the order to K=1 with h=10^{-2} reduces the Wasserstein-1 error to 3.17 , an improvement over the 4.16 baseline achieved by K=0 . Similarly, for \alpha=1.8 , a fine-tuned model ( K=5,h=10^{-1} ) achieves a Wasserstein-1 distance of 0.81 , almost halving the error of the zeroth-order model ( 1.45 ). • Robustness-Accuracy Trade-off: While higher K values offer a higher performance ceiling, they exhibit greater sensitivity to the choice of h . As illustrated in the heatmaps, the performance of K\geq 1 degrades rapidly if h deviates from the optimal range (e.g., for \alpha=1.2 , the error for K=1 spikes to 6.73 at h=0.03 ). In contrast, the K=0 configuration remains stable across a wide spectrum of hyperparameters, consistently outperforming the unadjusted FULA baseline without requiring extensive tuning. These findings suggest a practical training-inference asymmetry : while the robust K=0 drift suffices for stable proposal generation in general settings, domain-specific fine-tuning of the approximation physics ( K,h ) allows practitioners to maximize sampling accuracy when ground-truth validation is feasible. (a) W_{1} ( \alpha=1.2 ) (b) q_{95} ( \alpha=1.2 ) (c) q_{99} ( \alpha=1.2 ) (d) W_{1} ( \alpha=1.5 ) (e) q_{95} ( \alpha=1.5 ) (f) q_{99} ( \alpha=1.5 ) (g) W_{1} ( \alpha=1.8 ) (h) q_{95} ( \alpha=1.8 ) (i) q_{99} ( \alpha=1.8 ) Figure 8 : Effect of approximation order K and drift step h on sampling accuracy. Rows correspond to stability indices \alpha\in\{1.2,1.5,1.8\} . Columns display the Wasserstein-1 distance ( W_{1} ) and tail percentile errors ( q_{95},q_{99} ). While the baseline K=0 (second column in each heatmap) is consistently robust, fine-tuning the approximation order ( K\geq 1 ) with an appropriate step size h yields the lowest discrepancies. A.5 Ablation Study: Loss Regularization \lambda_{\alpha} (a) W_{1} ( \alpha=1.2 ) (b) q_{95} ( \alpha=1.2 ) (c) q_{99} ( \alpha=1.2 ) (d) W_{1} ( \alpha=1.5 ) (e) q_{95} ( \alpha=1.5 ) (f) q_{99} ( \alpha=1.5 ) (g) W_{1} ( \alpha=1.8 ) (h) q_{95} ( \alpha=1.8 ) (i) q_{99} ( \alpha=1.8 ) Figure 9 : Effect of loss regularization \lambda_{\alpha} and approximation order K . The heatmaps show performance at fixed drift step h=0.01 . The inclusion of the \alpha -norm in the Score Balance Matching objective ( \lambda_{\alpha}>0 ) provides significant robustness, particularly in reducing tail errors ( q_{99} ) for heavy-tailed distributions ( \alpha=1.2,1.5 ). To address the heavy-tailed nature of the score residuals, we proposed a hybrid Score Balance Matching objective defined as \mathcal{L}=\mathcal{L}_{2}+\lambda_{\alpha}\mathcal{L}_{\alpha} . In this study, we investigated the impact of the regularization weight \lambda_{\alpha}\in[0,2] alongside the approximation order K , fixing the drift step size at h=10^{-2} . The results, visualized in Figure 9 , demonstrate that incorporating the \alpha -norm ( \lambda_{\alpha}>0 ) significantly improves sampling stability, particularly for tail statistics. • Tail Stability: For heavy-tailed targets ( \alpha=1.2 ), a purely L^{2} -based loss ( \lambda_{\alpha}=0 ) yields a 99th-percentile error of 14.80 (using K=1 ). In contrast, setting \lambda_{\alpha}=2.0 reduces this error to 1.18 (using K=0 ), effectively constraining the variance of the learned acceptance probability in the tails. • Consistent Enhancement: Overall, higher regularization weights ( \lambda_{\alpha}\in[0.5,2.0] ) consistently enhance the sampler’s ability to fit extreme quantiles without compromising the Wasserstein-1 distance. These findings indicate that the mixed-norm objective is crucial for learning robust acceptance functions when the proposal distribution exhibits infinite variance. Appendix B Case Study of Combinatorial Optimization Problems B.1 MaxCut Combinatorial formulation. The MaxCut problem on an undirected graph G=(V,E) with |V|=N can be written as \min_{x\in\{-1,1\}^{N}}\sum_{i,j=1}^{N}w_{ij}x_{i}x_{j}=x^{\top}Wx, where W=(w_{ij})_{1\leq i,j\leq N} is a symmetric weight matrix. In our experiments, we set W to be the adjacency matrix A of the graph, defined by A_{ij}=\mathbf{1}_{\{(i,j)\in E\}}. Under this choice, minimizing x^{\top}Wx is equivalent (up to an additive constant) to maximizing the number of edges whose endpoints lie in different partitions, i.e., the MaxCut objective. Continuous relaxation and energy model. Directly sampling over the discrete domain \{-1,1\}^{N} is infeasible for gradient-based methods. We therefore introduce a continuous latent variable u\in\mathbb{R}^{N} and define a smooth relaxation through the elementwise transformation y=\tanh(u)\in(-1,1)^{N}. Using this relaxed variable, we define the energy function E:\mathbb{R}^{N}\to\mathbb{R} as E(u)=\frac{1}{2}\sum_{i,j=1}^{N}w_{ij}\tanh(u_{i})\tanh(u_{j})=\frac{1}{2}\tanh(u)^{\top}W\tanh(u). Equivalently, in terms of y , we have E(u)=E(y)=\frac{1}{2}y^{\top}Wy . This relaxation preserves the quadratic structure of the original objective while yielding a smooth, differentiable energy landscape. We define a target density over u by \pi(u)\propto\exp\!\left(-\frac{E(u)}{\eta}\right),\quad u\in\mathbb{R}^{N}, where \eta>0 is a temperature parameter. Smaller values of \eta concentrate probability mass around low-energy regions, corresponding to high-quality cuts, while larger values encourage broader exploration. Score function. The score function \nabla_{u}\log\pi(u) provides the drift term for Langevin-type sampling algorithms. By the quadratic structure of E(y) , we have \nabla_{y}E(y)=Wy. Applying the chain rule yields \nabla_{u}E(u)=\bigl(1-\tanh(u)^{2}\bigr)\odot W\tanh(u), where \odot denotes elementwise multiplication. Consequently, the score function takes the explicit form \nabla_{u}\log\pi(u)=-\frac{1}{\eta}\nabla_{u}E(u)=-\frac{1}{\eta}\bigl(1-\tanh(u)^{2}\bigr)\odot W\tanh(u). This closed-form (oracle) score is used by ULA, MALA, and their fractional counterparts to guide sampling toward regions corresponding to large cuts. Discretization strategy. After sampling a continuous state u , we recover a discrete cut by applying the sign map x=\mathrm{sgn}\!\left(\tanh(u)\right),\qquad\mathrm{sgn}(a)=\mathbf{1}_{\{a\geq 0\}}-\mathbf{1}_{\{a<0\}},\quad a\in\mathbb{R}. (24) This operation projects the relaxed variable back onto \{-1,1\}^{N} and yields a valid partition of the graph. The resulting discrete solution is then evaluated using the original MaxCut objective. B.2 Vertex Cover Combinatorial formulation. Given an undirected graph G=(V,E) with |V|=N , the minimum vertex cover problem seeks a binary assignment x\in\{0,1\}^{N} minimizing \min_{x\in\{0,1\}^{N}}\sum_{i=1}^{N}x_{i}\quad\text{subject to}\quad x_{i}+x_{j}\geq 1\quad\forall(i,j)\in E, so that every edge is incident to at least one selected vertex. This problem is NP-hard and serves as a canonical example of constrained combinatorial optimization. Continuous relaxation and energy model. To enable gradient-based sampling, we introduce a continuous latent variable u\in\mathbb{R}^{N} and relax the binary variables via the sigmoid transformation p=\sigma(u)\in(0,1)^{N},\qquad\sigma(a)=\frac{1}{1+e^{-a}}. Here, p_{i} may be interpreted as a soft selection indicator for vertex i . We define a relaxed energy function consisting of two components: a soft cardinality term and a penalty enforcing edge coverage, E(u)=\sum_{i=1}^{N}y_{i}+\lambda\sum_{(i,j)\in E}\bigl(1-y_{i}\bigr)\bigl(1-y_{j}\bigr)=\mathbf{1}^{\top}p+\frac{\lambda}{2}(\mathbf{1}-p)^{\top}A(\mathbf{1}-p), where A=(\mathbf{1}_{(i,j)\in E})_{1\leq i,j\leq N} and \lambda>0 controls the strength of the constraint enforcement. This relaxation penalizes uncovered edges while encouraging sparse vertex selections, and reduces to the original objective in the binary limit. As in the MaxCut case, we define a target density \pi(u)\propto\exp\!\left(-\frac{E(u)}{\eta}\right), where \eta>0 is a temperature parameter controlling the exploration–exploitation trade-off. Score function. The score function governing Langevin-type dynamics is given by \nabla_{u}\log\pi(u)=-\frac{1}{\eta}\nabla_{u}E(u). Using the chain rule and the derivative \sigma^{\prime}(u)=\sigma(u)\bigl(1-\sigma(u)\bigr) , we obtain \nabla_{u}E(u)=\sigma^{\prime}(u)\odot\left[\mathbf{1}-\lambda A(\mathbf{1}-p)\right], where the indicator term selects edges that remain uncovered under the relaxed assignment. This explicit (oracle) score is used by ULA, MALA, and their fractional variants to guide sampling toward low-energy, approximately feasible vertex covers. Discretization and greedy decoding. After sampling the continuous variable u , we obtain an initial discrete vertex selection by thresholding: x_{i}=\mathbf{1}_{\{u_{i}>0\}},\qquad i=1,\dots,N. This produces a sparse candidate cover but may leave a subset of edges uncovered, since feasibility is not strictly enforced under the continuous relaxation. To obtain a valid vertex cover, we apply a greedy decoding procedure. Specifically, while there exists an uncovered edge (i,j)\in E with x_{i}=x_{j}=0 , we add to the cover the endpoint with larger relaxed activation, i.e., x_{k}\leftarrow 1,\qquad k=\arg\max_{\ell\in\{i,j\}}p_{\ell}, where p=\sigma(u) . This process is repeated until all edges are covered. The resulting discrete solution is guaranteed to be feasible and is evaluated using the original vertex cover objective. Table 2 : Vertex Cover results on Erdős–Rényi (ER) and Barabási–Albert (BA) graphs. Reported are mean \pm std energy, mean cover size (smaller is better), best cover found, and uncovered ratio. (a) Erdős–Rényi graphs, with |E|=2.5N Graph Sampler Energy ( \mu\pm\sigma ) Cover ↓ ( \mu\pm\sigma ) Best ↓ Uncov. ↓ ( \mu\pm\sigma ) ER64 ULA 0.805\pm 0.034 49.88\pm 2.10 43 0.239\pm 0.071 FULA 0.682\pm 0.031 46.17\pm 1.96 41 0.144\pm 0.042 MALA 0.806\pm 0.029 49.88\pm 1.95 44 0.240\pm 0.067 MAFLA 0.657\pm 0.028 \mathbf{45.02\pm 2.10} \mathbf{39} \mathbf{0.127\pm 0.035} ER256 ULA 0.810\pm 0.018 198.66\pm 4.42 183 0.248\pm 0.035 FULA 0.709\pm 0.018 187.14\pm 4.53 173 0.160\pm 0.025 MALA 0.812\pm 0.016 199.03\pm 4.35 188 0.247\pm 0.035 MAFLA 0.685\pm 0.014 \mathbf{181.97\pm 4.27} \mathbf{169} \mathbf{0.139\pm 0.020} ER512 ULA 0.811\pm 0.013 398.60\pm 6.19 379 0.248\pm 0.026 FULA 0.743\pm 0.013 385.83\pm 6.54 364 0.179\pm 0.019 MALA 0.812\pm 0.012 398.93\pm 6.41 378 0.249\pm 0.026 MAFLA 0.727\pm 0.011 \mathbf{379.06\pm 6.19} \mathbf{358} \mathbf{0.158\pm 0.016} ER1024 ULA 0.812\pm 0.009 796.43\pm 8.34 771 0.249\pm 0.018 FULA 0.766\pm 0.009 780.81\pm 8.49 753 0.196\pm 0.015 MALA 0.812\pm 0.008 796.77\pm 8.68 768 0.249\pm 0.017 MAFLA 0.759\pm 0.008 \mathbf{775.94\pm 8.82} \mathbf{747} \mathbf{0.184\pm 0.013} (b) Barabási–Albert graphs, with m=2 Graph Sampler Energy ( \mu\pm\sigma ) Cover ↓ ( \mu\pm\sigma ) Best ↓ Uncov. ↓ ( \mu\pm\sigma ) BA64 ULA 1.327\pm 0.212 45.43\pm 2.70 38 0.115\pm 0.049 FULA 0.842\pm 0.191 39.56\pm 3.31 \mathbf{31} \mathbf{0.048\pm 0.034} MALA 1.431\pm 0.212 45.43\pm 2.73 38 0.128\pm 0.051 MAFLA 0.872\pm 0.225 \mathbf{38.61\pm 3.56} \mathbf{31} 0.057\pm 0.040 BA256 ULA 1.720\pm 0.178 181.20\pm 5.84 166 0.194\pm 0.040 FULA 0.942\pm 0.119 166.96\pm 7.23 148 0.059\pm 0.020 MALA 1.780\pm 0.166 181.12\pm 5.80 165 0.203\pm 0.040 MAFLA 0.905\pm 0.115 \mathbf{163.96\pm 7.67} \mathbf{140} \mathbf{0.053\pm 0.020} BA512 ULA 1.827\pm 0.145 360.52\pm 7.69 336 0.216\pm 0.031 FULA 1.010\pm 0.094 345.06\pm 9.63 320 0.067\pm 0.016 MALA 1.865\pm 0.137 361.07\pm 7.81 338 0.222\pm 0.032 MAFLA 0.967\pm 0.082 \mathbf{342.12\pm 9.70} \mathbf{316} \mathbf{0.059\pm 0.014} BA1024 ULA 1.892\pm 0.116 716.20\pm 11.65 679 0.228\pm 0.025 FULA 1.094\pm 0.076 703.16\pm 12.64 670 0.079\pm 0.013 MALA 1.921\pm 0.108 716.20\pm 11.76 684 0.233\pm 0.026 MAFLA 1.027\pm 0.065 \mathbf{696.98\pm 12.99} \mathbf{655} \mathbf{0.066\pm 0.011} Discussion. The empirical gains observed in both MaxCut and Vertex Cover can be attributed to two complementary aspects of our framework: the use of \alpha -stable fractional dynamics and the incorporation of an acceptance correction. Fractional Langevin dynamics introduce heavy-tailed noise, which enables occasional long-range moves in the continuous relaxation space. Compared to Gaussian perturbations, this behavior facilitates exploration across energy barriers and helps the sampler escape local minima induced by the highly nonconvex combinatorial objectives. This effect becomes increasingly pronounced as graph size grows, where the energy landscape exhibits a large number of metastable configurations. While fractional dynamics enhance exploration, they can also lead to unstable updates or overly aggressive proposals when used without correction. The acceptance mechanism in MAFLA mitigates this issue by selectively rejecting unlikely transitions, thereby stabilizing the sampling process and preserving the target distribution. Empirically, this combination yields consistent improvements over both Gaussian samplers and non-adjusted fractional methods, achieving better trade-offs between exploration, stability, and solution quality across problem instances.