Reshaping Global Loop Structure to Accelerate Local Optimization by Smoothing Rugged Landscapes Preprint: APS/123-QED Timothée Leleu, Sam Reifenstein, Atsushi Yamamura, Surya Ganguli Abstract Probabilistic graphical models with frustration exhibit rugged energy landscapes that trap iterative optimization dynamics. These landscapes are shaped not only by local interactions, but crucially also by the global loop structure of the graph. The famous Bethe approximation treats the graph as a tree, effectively ignoring global structure, thereby limiting its effectiveness for optimization. Loop expansions capture such global structure in principle, but are often impractical due to combinatorial explosion. The M M -layer construction provides an alternative: make M M copies of the graph and reconnect edges between them uniformly at random. This provides a controlled sequence of approximations from the original graph at M = 1 M=1 , to the Bethe approximation as M → ∞ M\rightarrow\infty . Here we generalize this construction by replacing uniform random rewiring with a structured mixing kernel Q Q that sets the probability that any two layers are interconnected. As a result, the global loop structure can be shaped without modifying local interactions. We show that, after this copy-and-reconnect transformation, there exists a regime in which layer-to-layer fluctuations decay, increasing the probability of reaching the global minimum of the energy function of the original graph (equivalently, the maximum- a-posteriori configuration). This yields a highly general and practical tool for optimization in problems with complex global loop structure. Using this approach, the computational cost required to reach these optimal solutions is reduced across sparse and dense Ising benchmarks, including spin glasses and planted instances. When combined with replica-exchange Monte Carlo, the same construction increases the polynomial-time algorithmic threshold for the maximum independent set problem. A cavity analysis shows that structured inter-layer coupling significantly smooths rugged energy landscapes by collapsing configurational complexity and suppressing many suboptimal metastable states. In addition to landscape smoothing, our analysis identifies an emergent Nesterov-like acceleration in the optimization dynamics induced by inter-layer interactions, arising naturally from drift in a one-dimensional ring mixing across layers. I Introduction Energy landscapes arising in disordered systems, spin glasses, and combinatorial optimization are often rugged, causing local-update algorithms to become trapped far from optimal configurations. Many optimization problems become hard not only in the worst case, but also on typical instances, when frustrated loops arise in the interaction graph 24 . In replica theory, it is possible to account for the number of metastable states that impede local algorithms 35 ; 25 ; 28 . Locally tree-like graphs form a special class that is well understood analytically. In the limit where loops in the interaction graph are long and rare, cavity theory 36 ; 27 ; 26 ; 30 ; 46 yields the belief-propagation (BP) equations, whose fixed points describe stationary points of the Bethe free energy. Essentially, the cavity theory provides a variational framework for describing marginal distributions in the tree-like (Bethe) approximation, with replica-symmetry breaking (RSB) accounting for the proliferation of metastable states. Nevertheless, this simpler picture breaks down when many short loops are present. Dense graphs can often be handled by other variational schemes instead 31 ; 39 . For graphs in the intermediate regime, it is harder to define a useful simplifying ansatz. Loop corrections to belief propagation have been derived 12 ; 29 , yet they are practical only for small loops and small systems 15 . Many variants of BP have been proposed to push beyond the tree limit 23 , but none gives a general cure for many short loops. A more systematic route to organizing loop corrections is provided by the M -layer construction 21 ; 1 ; 3 ; 2 ; 4 , which in its standard form makes M copies of the base graph and permutes the connections between them uniformly at random. One thereby obtains a larger “lifted” graph in which the local couplings remain unchanged, while short loops in the original graph are stretched across different layers. As M increases, the lifted graph becomes effectively tree-like. In the limit M\to\infty , the free energy of the lifted graph converges to the Bethe free energy of the original graph 42 , while for finite M the residual loops give controlled corrections that can be organized as a diagrammatic expansion, closely analogous to loop expansions in field theory 21 ; 1 . So far, the M -layer construction has served mainly as a theoretical tool for studying critical behavior in lattice models 1 ; 3 ; 2 ; 4 , not as a method for optimization. Existing versions effectively describe a statistical mixture of Bethe states and offer no mechanism for selecting or decimating toward a single solution 11 . The purpose of this work is to develop an M -layer graph-lifting construction applicable to optimization that allows explicit control over the global pattern of correlations induced by loops through a tunable layer-to-layer connectivity, while preserving local interaction structure. Our construction begins with a factor graph and copies every node M times. Connections between copies (or layers) are then rewired using a biased random matching: a tunable mixing matrix Q specifies how frequently edges originating in one layer connect to another. Uniform Q recovers the standard M -layer construction with uniformly random rewiring across layers, while structured choices of Q bias the rewiring toward specific layer-to-layer connections and shape how information propagates across the lifted system. As a result, information flows in two coupled directions: across the original interaction graph and along the inter-layer network defined by Q . While many layer-interaction graphs are possible in principle, we focus in the following on the simple but effective case of a Gaussian-drift ring mixer. For context, approaches based on coupling multiple copies of a system have also been explored for optimization, most notably in replicated simulated annealing (RSA) 9 ; 5 . In this approach, copies of the base problem are coupled through an explicit ferromagnetic interaction that encourages corresponding variables across layers to align. Such replica coupling has been observed to effectively smooth the energy landscape in certain settings 9 . However, RSA modifies the local neighborhood of each spin by introducing additional inter-replica interactions, in contrast to the M -layer construction which preserves local interactions; moreover, in existing formulations this ferromagnetic inter-replica coupling is typically homogeneous and does not impose an explicit structure on how different replicas are interconnected. In harder combinatorial problems such as the maximum independent set, its performance gains have been shown to be limited, with only modest improvements over parallel tempering reported 5 . At the same time, RSA can yield substantial improvements over single-replica baselines in other settings, such as planted graph coloring 6 . Ideas akin to cloning a graph have also appeared in coding theory: spatially coupled low-density parity-check codes (LDPC) replicate and link code blocks to approach Shannon-limit decoding 16 ; 17 ; 45 ; 7 ; 38 ; 13 ; 22 ; 33 ; 19 . These methods rely on coupling along a chain, whereas here the goal is to design general graph-lifting operations that improve convergence of local dynamics. In this paper, we first empirically characterize the effect of the structured M -layer lift across a broad range of Ising optimization problems, from sparse random regular graphs to dense mean-field models. We find that the residual energy reached by greedy relaxation decreases with the number of layers M . Although each sweep on the lifted graph is more computationally expensive, the probability of reaching the ground state increases sufficiently that the total computational cost is reduced for both greedy dynamics and simulated annealing. When combined with state-of-the-art Monte-Carlo–exchange schemes, the structured lift raises the algorithmic threshold for the maximum independent set problem, i.e., the largest independent-set density reachable in polynomial time, compared to parallel tempering 40 ; 14 (PT) and replicated simulated annealing 9 ; 5 (RSA). To explain these empirical observations, we develop a cavity-theoretic analysis of the structured M -layer. We derive belief-propagation equations with mixing and show that, to leading order, the lifted dynamics corresponds to stochastic descent on the Bethe free energy of the base graph, with a noise amplitude controlled by coherent fluctuations across layers and exhibiting a Nesterov-like acceleration when the ring carries a drift. Extending the M -layer cavity theory to the 1-RSB level, we compute the configurational complexity and show that it decreases with increasing M , indicating a smoothing of the rugged landscape of metastable states, consistent with the observed improvement in optimization performance. The structured M -layer lift is completely general. Because it modifies only the interaction topology and not the update rule, it can be combined with many iterative algorithms. It applies to arbitrary probabilistic graphical models and is therefore compatible with combinatorial optimization, probabilistic decoding, and related machine-learning tasks. More broadly, this framework opens the possibility of designing richer layer-to-layer interaction graphs beyond the simple 1D ring example used here, allowing one to exploit instance-specific structure and potentially achieve even greater speedups. Section II defines the structured M -layer transform. Section III shows how this construction improves MAP inference through numerical experiments on various benchmarks. Section IV develops the cavity-theory description, deriving the message-passing equations with mixing and the corresponding contraction criterion. Finally, Section V extends the analysis to the 1-RSB level, where the collapse of inter-layer variability appears as a measurable reduction in landscape ruggedness, as measured by configurational complexity. II Method II.1 Factorizable probabilistic model The structured M-layer transformation applies to any generic factorizable probabilistic model defined on a factor graph G=(V,A) , where V denotes a set of variable nodes, and A denotes a set of interaction factors. Here we will restrict to variable nodes i\in V that take values x_{i} in a finite alphabet but the transformation can be easily generalized to the continuous case. The factor graph is described by its unary factors f_{i}(x_{i}) for each variable i\in V , and interaction factors f_{a}(x_{\partial a}) for each factor a\in A , where \partial a\subseteq V denotes the variables involved in factor a . The Gibbs distribution of the model is \displaystyle P(x)=\frac{1}{Z}\prod_{i\in V}f_{i}(x_{i})\prod_{a\in A}f_{a}(x_{\partial a}), (1) where Z is the partition function given as Z=\sum_{\{x\}}\prod_{i\in V}f_{i}(x_{i})\prod_{a\in A}f_{a}(x_{\partial a}) . Each factor f_{a}(x_{\partial a}\mid\theta_{a}) depends on instance-specific disorder \theta_{a} . For synthetic benchmarks, these parameters are typically drawn from a prescribed distribution P_{\theta} . The Ising model with Hamiltonian H(x)=-\sum_{i0.1 ). Figure 3: Decrease of residual energy with the number of layers M . a) Minimum over the mixing-kernel width \sigma of the mean residual energy per spin \langle e-e_{0}\rangle of Ising random regular graphs of degree k=3 , obtained by averaging K runs (and 10 instances) of the greedy zero temperature Glauber update; vertical bars denote the stored 95% confidence intervals, and dotted curves show the fitted power laws aM^{p} . b) and c) Fitted exponent p versus N and prefactor a versus N on a logarithmic scale. The KS p -values are 0.157, 0.104, and 0.295 for N=60 , 90 , and 120 , respectively. K=50 . L=2 . III.3 Compute-To-Solution The structured M -layer lift lowers the residual energy found after greedy iterative updates but also increases the number of spins and, in turn, the number of elementary operations performed in each sweep. Despite this increased per-sweep cost, we find that the lift yields a net computational advantage. The probability of reaching the target energy grows sufficiently with M that the total computational effort required for success is reduced. To quantify this trade-off, we measure the total computational budget, defined as the number of elementary operations needed to reach a target fraction of the ground-state energy with 99\% success probability, as a function of the number of blocks. To quantify this trade-off, we define an operation-to-target (OTT) metric, which measures the total number of elementary operations required to reach the target energy with 99\% success probability: \displaystyle\text{OTT}=R\times C_{\text{run}}=R\times d\,(NM)T. (10) Here R=\left\lceil\frac{\log(1-0.99)}{\log(1-p_{0})}\right\rceil is the number of independent runs required to achieve 99\% success probability, and C_{\text{run}}=d\,(NM)\,T is the computational cost of a single run, proportional to the number of sweeps T , the number of spins NM , and the number of elementary operations per spin update d ( d=3 for random regular graphs, d=N for Sherrington–Kirkpatrick, and d=4 for tile-planted instances). The target is taken to be the inferred ground-state energy e_{0} . For each problem type (random regular graphs, Sherrington–Kirkpatrick, and tile-planted instances 37 ), we perform simulations over the key parameters: system size N , number of layers M , mixing width \sigma , and number of sweeps T . For each instance, we construct the corresponding M -layer couplings, run greedy and simulated annealing dynamics for T sweeps, and record the per-layer energies defined in Eq. ( 6 ). From these runs, we estimate the empirical probability p_{0} that at least one layer reaches the target energy level. For each system size N , we select the minimum OTT across all tested schedules and mixing parameters, obtaining the most efficient configuration. Figure 4 and Table 1 summarizes these results. Across models and solvers, the OTT curves exhibit an optimum at finite M , confirming that structured mixing provides a computational gain beyond the trivial parallelism of repeating the system. As a general trend, the optimal number of layers M increases with system size N , although the precise scaling depends on both the algorithm and the problem class. Further numerical studies will be required to characterize in detail how the optimal lift size depends on the underlying instance ensemble and update rule. Details of the benchmark protocol are provided in Appendix VI.7 . Figure 4: Computational advantage of the M -layer lift. a) Operation-to-target (OTT) at optimal \sigma^{*} versus layer count M . b) Scaling of OTT ∗ at optimal M vs. base problem size N . c) Layer count M that achieves the optimal OTT for each problem and solver. The OTT combines per-run computational cost (operations) dNMT with the number of runs required for a 99\% success probability. Error bars show 95\% confidence intervals over disorder realizations. Instances are random regular graphs of degree d=3 . Glauber ( T=0 ) = zero-temperature Glauber updates. SA = simulated annealing. RRG = random regular graph of degree 3 . SK = Sherrington-Kirkpatrick with weights \pm 1 . Tile planted are dimension 2 with patterns (p_{1},p_{2},p_{3})=(0.2,0.5,0.1) . Block size is L=1 . The apparent saturation of the RRG/Glauber ( T=0 ) curve at large M\geq 14 reflects the finite range of tested layer counts rather than an intrinsic limitation of the method. Pb. Alg. \text{OTT}^{*}_{M=1} \min_{M}\text{OTT}^{*} N M^{*} Speedup RRG T=0 9.49e+06 2.57e+06 90 8 3.69 RRG SA 1.32e+09 6.22e+08 600 3 2.13 SK T=0 2.22e+10 4.34e+09 220 5 5.11 SK SA 2.47e+10 1.37e+10 350 8 1.81 TP T=0 4.6e+07 2.45e+07 100 6 1.88 TP SA 1.47e+11 1.2e+11 400 2 1.22 Table 1: Summary of operation-to-target (OTT) results for the M -layer lift. Problems, algorithm, operation-to-target at M=1 and optimal M , problem size N , optimal M^{*} , and speed up defined as the ratio of \text{OTT}^{*}_{M=1}/\text{min}_{M}\text{OTT}^{*}(M) . RRG: random regular graph degree 3 . SK: Sherrington-Kirkpatrick. TP: Tile-planted instances 37 . III.4 Replica exchange methods on MIS To compare the structured M -layer lift with established replica-exchange methods, we study the maximum independent set (MIS) problem on random regular graphs. We find that the M -layer lift systematically raises the algorithmic threshold attainable in polynomial time when combined with replica-exchange schemes. An independent set of a graph G=(V,E) is a vertex subset S\subseteq V with no two vertices within S connected by an edge. We define the density of a subset S as \rho=|S|/N . The maximal independent set (MIS) is the largest possible independent set with highest density. For Monte-Carlo algorithms, a central performance measure is the number of Monte Carlo sweeps (MCS) needed to reach a given density \rho of an independent set S (maximal or not). In analyzing such algorithms, several works 5 introduce the notion of an algorithmic threshold \rho_{\rm alg} , defined as the highest independent-set density that can be reached with a runtime growing only polynomially in the system size N . Operationally, this threshold is identified through the scaling of the convergence time \tau(\rho) , defined as the typical number of iterations required to reach an independent-set density \rho . As \rho approaches the threshold from below, the convergence time grows rapidly and is well described by a power-law divergence, \tau(\rho)\simeq\frac{C}{(\rho_{\rm alg}-\rho)^{\nu}}. (11) We adopt this framework to benchmark algorithms introduced in Ref. 5 : simulated annealing ( \mu SA), replicated simulated annealing ( \mu RSA), parallel tempering ( \mu PT), and their M -layer extensions. Simulations are performed on random d=100 regular graphs of size N=5000 2 2 2 Although N=5000 is a smaller problem size than the one considered in prior works, our results are consistent with the threshold estimated in 5 for N=50000 . . Figure 5 shows the measured curves and corresponding fits to eq. ( 11 ). For the baseline algorithms we obtain \mu SA: \rho_{\rm alg}=0.0651\pm 0.0002 , \mu RSA ( R=3 ): \rho_{\rm alg}=0.0651\pm 0.0003 , and \mu PT: \rho_{\rm alg}=0.0654\pm 0.0001 , reproducing the established ordering in which \mu PT achieves the largest polynomial-time density (see Appendix VI.7.2 for details about the benchmark). We then apply the structured M -layer lift. The lift modifies only the interaction topology and leaves each algorithm’s update rule intact. When combined with \mu SA using M=5 , the threshold increases to \rho_{\rm alg}=0.0654\pm 0.0001 , effectively matching \mu PT. When applied to \mu PT with M=3 , the threshold increases further to \rho_{\rm alg}=0.0657\pm 0.0001 , the largest among all methods tested. These results show that the M -layer lift consistently expands the polynomial-time (“easy”) regime of both \mu SA and \mu PT, producing the strongest performance when the two approaches are combined. Figure 5: Algorithmic thresholds for MIS under replica–exchange methods. The main panel shows the mean number of Monte Carlo sweeps (MCS) required to reach independent-set density \rho for \mu SA, \mu RSA, \mu PT, and their M -layer extensions (M-layer \mu SA with M=5 , M-layer \mu PT with M=3 ). Points denote empirical measurements, and solid curves give power-law fits \tau(\rho)=C(\rho_{\rm alg}-\rho)^{-\nu} . Vertical dashed lines indicate the algorithmic thresholds \rho_{\rm alg} , with shaded regions showing 95% confidence intervals. The inset summarizes the fitted \rho_{\rm alg} values. The structured M -layer lift elevates the threshold of \mu SA to that of \mu PT and further improves \mu PT itself, yielding the highest threshold among all compared algorithms. \mu PT uses 30 replicas, M-layer \mu PT uses 22 and 12 replicas for M=2 and M=3 , respectively. IV Cavity Theory IV.1 Scope and assumption Empirical results show that even simple greedy updates reach lower energies with less computational effort in a structured M -layer lift. To understand this gain, we analyze the lifted system within the cavity framework. These calculations extend the results of 21 to the structured M -layer setting. Before developing the cavity-theoretic description, we clarify the assumptions under which the following analysis applies. With stochastic update rules, the microscopic dynamics does not admit deterministic attractors in the strict sense; rather, long-time behavior is characterized by stationary distributions and metastable regions of configuration space. In the presence of asymmetric permutations ( \pi_{a,i}\neq\pi_{i,a} ), the resulting dynamics is, in principle, non-equilibrium, and a fully general description would require dynamic cavity or message-passing equations defined on spin histories 32 ; 8 ; 20 . Such frameworks allow for the possibility of nontrivial dynamical attractors, including oscillatory or history-dependent behavior. In this work, however, we focus on a regime in which the structured M -layer mixing induces strong contraction of inter-layer fluctuations (Sec. IV.5 ). Empirically, for the mixing kernels Q considered here, both zero-temperature and low-temperature dynamics rapidly converge to stationary configurations, and we do not observe persistent oscillatory behavior. Motivated by this observation, and by the fact that the effective coarse-grained dynamics of averaged messages becomes approximately potential-like in the large- M limit, we assume that the relevant long-lived states are well described by fixed points of the belief-propagation recursion; under this assumption, the cavity and replica-symmetry-breaking analyses that follow characterize the corresponding Bethe free-energy landscape of the annealed structured M -layer ensemble. The resulting complexity should therefore be interpreted as the logarithmic density of Bethe fixed points, which we use as a statistical-mechanical proxy for the number of metastable basins explored by the dynamics. Before turning to the technical details, we summarize the main results of this section. Under the assumptions described above, we show that the free energy of the structured M -layer lift reduces at leading order to a Bethe free-energy functional augmented by a linear mixing of messages across layers. The saddle-point equations of this functional yield belief-propagation (BP) updates with mixing. Linearizing these updates reveals a contraction criterion that determines when fluctuations between layers decay and the layers synchronize. Focusing on the dynamics of the averaged messages shared across layers, we further show that BP on the lifted graph can be interpreted as a stochastic descent on the Bethe free energy of the base graph. The effective noise driving this descent is controlled by coherent fluctuations across layers and enables escapes from metastable Bethe states. Finally, for the ring mixing topology, we show that introducing a drift generates traveling-wave modes across layers, which manifest as a momentum-like (Nesterov-type) acceleration of the message dynamics. IV.2 M-layer free energy We begin by deriving the free-energy functional of the structured M -layer lift. The free energy density of the structured M -layer, denoted f_{M} with f_{M}=-\frac{1}{\beta MN}\mathbb{E}_{\pi}[\log(Z_{M})] , is computed using the replica method via: \displaystyle\mathbb{E}_{\pi}[\log(Z_{M})] \displaystyle=\lim_{n\to 0}\frac{1}{n}\left(\mathbb{E}_{\pi}[Z_{M}^{n}]-1\right), (12) \displaystyle\approx\lim_{n\to 0}\frac{1}{n}\log(\mathbb{E}_{\pi}[Z_{M}^{n}]) (13) where the expectation \mathbb{E}_{\pi}[\cdot] is taken over the random permutations \{\pi_{e}\} defined at eq. ( 3 ), and n is the number of replicas. The symbol \approx indicates the usual replica assumption that the free energy is self-averaging, so that fluctuations of \log Z_{M} become negligible in the thermodynamic limit. We briefly outline the main steps of the calculation here; full technical details are given in Appendix VI.2 , and a summary of notation appears in Appendix A, Table 2 . We first introduce a convenient representation of the inter-layer permutations used throughout this section. For each directed edge e=(a,i) , the permutation \pi_{e} defined in Eq. ( 3 ) can be represented by a permutation matrix C_{e}\in\{0,1\}^{M\times M} , with entries C_{e,\alpha\beta}=1 if \alpha=\pi_{e}(\beta) and zero otherwise. By construction, each C_{e} satisfies \sum_{\beta}C_{e,\alpha\beta}=\sum_{\alpha}C_{e,\alpha\beta}=1 . The sampling distribution of C_{e} is then \displaystyle P(C_{e})=\frac{1}{Z_{e}}\prod_{\alpha,\beta}q_{\alpha\beta}^{\,C_{e,\alpha\beta}},\qquad Z_{e}=\mathrm{perm}(q), (14) where \mathrm{perm}(q) denotes the permanent of the mixing kernel q . With this notation in place, the averaged replicated partition function is given as \displaystyle\mathbb{E}_{C}[Z_{M}^{n}]=\sum_{\{x_{a}\}}\prod_{e=(i,a)}\sum_{\{C_{e}\}}P(C_{e})\prod_{\alpha,\beta}\left[F_{e}^{\alpha\beta}(\{x_{a}\})\right]^{C_{e,\alpha\beta}}, (15) with \displaystyle F_{e}^{\alpha\beta}=\exp\left[\sum_{k=1}^{n}\left(\log f_{i}(x_{i,\alpha_{k}})+\log f_{a}(x_{\partial a,\beta_{k}})\right)\right], (16) for each edge e=(i,a) and replica index k . Here x_{a}=\{x_{i}:i\in\partial a\} denotes the set of variables adjacent to factor a . The expression of the replicated partition function can be simplified by introducing Fourier projectors for the row/column constraints related to the permutations and performing a Hubbard–Stratonovich transform. Importantly, one can utilize the fact that only tree-like interactions in the M-layer contribute at order M in \log\mathbb{E}_{C}[Z_{M}^{n}] , i.e., order O(1) to the free energy density f_{M} . All subgraphs with loops contribute at higher order (see Appendix VI.2 for details). At the end of this procedure, one obtains a functional integral over block-indexed “messages” (or marginal probabilities) p , with p\in[0,1]^{B} . From this point on, we restrict the discussion to the Ising model with pairwise factors a=(i,j) for clarity. The free energy of the lifted graph depends on \mathbb{E}_{C}[Z_{M}^{n}] given as \mathbb{E}_{C}[Z_{M}^{n}]\propto\int d\mu[p]\;\exp\!\big[-M\,S[p]\big]\ \exp[O(N)], (17) where the extra \exp[O(N)] factor representing loop corrections is independent of p , contributes O(1/M) to the free energy density, and can be dropped at leading order. Thus, in the limit M\to\infty , the free energy of the M-layer is: \displaystyle f_{M}=f_{\text{Bethe}}+O\!\left(\frac{1}{M}\right), (18) where f_{\text{Bethe}} is the Bethe free energy of the M-layer with f_{\text{Bethe}}=\frac{1}{\beta N}\,\inf_{p}S[p] the first order term. The action S[p] is given as S[p]=\sum_{(i,j)\in E}\log Z_{ij}\;-\frac{1}{B}\;\sum_{i\in V}\sum_{b=1}^{B}\log Z_{ib}, (19) with the edge and site partition factors \displaystyle Z_{ij} \displaystyle=\sum_{b=1}^{B}\sum_{x_{i}=\pm 1}p_{b}^{\,i\to j}(x_{i})\,\hat{p}_{b}^{\,j\to i}(x_{i}), (20) \displaystyle Z_{ib} \displaystyle=\sum_{x_{i}=\pm 1}\prod_{k\in\partial i}\hat{p}_{b}^{\,k\to i}(x_{i}), (21) and propagated (block-mixed) field \hat{p}_{b}^{\,i\to j} is \hat{p}_{b}^{\,i\to j}(x_{j})=\sum_{c=1}^{B}Q_{bc}\sum_{x_{i}=\pm 1}U_{ij}(x_{j},x_{i})\,p_{c}^{\,i\to j}(x_{i}), (22) with U_{ij}(\sigma,\tau)=e^{\beta J_{ij}\sigma\tau} . The integration measure enforces normalization on each oriented edge and block as follows: \displaystyle d\mu[p]\;=\;\prod_{(i,j),b}\Bigg[\;\prod_{x=\pm 1}dp_{b}^{\,i\to j}(x)\;\delta\!\Big(\sum_{x}p_{b}^{\,i\to j}(x)-1\Big)\Bigg], (23) For B=1 the block index drops and eq. ( 19 ) reduces to the standard RS Bethe free-energy functional. IV.3 Message-passing with mixing We next derive the belief-propagation equations induced by the structured M -layer lift, which incorporate linear mixing between layers. In the thermodynamic limit M\to\infty , the action S concentrates around its saddle point and yields the block-coupled belief-propagation (BP) equations (see Appendix VI.3 ): \displaystyle p_{b}^{\,i\to j}(x_{i}) \displaystyle=\frac{1}{z_{b}^{i\to j}}\prod_{k\in\partial i\setminus j}\hat{p}_{b}^{\,k\to i}(x_{i}), (24) \displaystyle\hat{p}_{b}^{\,k\to i} \displaystyle\text{ given by }\eqref{eq:hatp-def-main}, (25) where z_{b}^{i\to j} is a normalization constant. This message-passing rule generalizes standard BP by introducing block interactions through the coupling matrix Q , allowing messages to mix across layers. For the Ising model, it is standard to rewrite these equations in terms of scalar cavity fields. In this case, the Bernoulli message distributions belong to an exponential family, and each message can be parametrized as (see Appendix VI.3.2 ) \displaystyle p_{b}^{i\to j}(x_{i}) \displaystyle\propto e^{\beta h_{b}^{i\to j}\,x_{i}}, (26) \displaystyle\hat{p}_{b}^{\,k\to i}(x_{i}) \displaystyle\propto e^{\beta u_{b}^{\,k\to i}x_{i}}, (27) where h_{b}^{\,i\to j} is the cavity field sent from variable i to factor (ij) , and u_{b}^{\,k\to i} is the effective field propagated from neighbor k to i . The node update is additive in the fields and defines a BP map h^{+}=F(h) , where h^{+} denotes the updated cavity field after one iteration. At a fixed point it satisfies 3 3 3 Per-message normalization fixes the gauge, so h_{b}^{\,i\to j} is uniquely defined. h_{b}^{\,i\to j}=F(\{h_{c}^{k\to i}\}_{k\in\partial i\setminus j,c})=h_{i}+\sum_{k\in\partial i\setminus j}u_{b}^{\,k\to i}. (28) At zero temperature ( T=0 ), the variable–to–variable channel on (k\to i) and block b is \displaystyle u_{b}^{\,k\to i}(h,J)=\frac{1}{2}\big(|J+H_{b}|-|J-H_{b}|\big), (29) and H_{b}=(Qh)_{b} . This corresponds to the standard zero-temperature BP field update, modified by the linear mixing induced by the matrix Q 26 (see Fig. 6 ). a b i j k \ell u^{k\to i} h^{k\to i} u^{\ell\to i} h^{\ell\to i} u^{i\to j} h^{i\to j} i j k \ell Q Q Q \{h_{b}^{k\to i}\}_{b} \{u_{b}^{k\to i}\}_{b} \{h_{b}^{\ell\to i}\}_{b} \{u_{b}^{\ell\to i}\}_{b} \{h_{b}^{i\to j}\}_{b} \{u_{b}^{i\to j}\}_{b} Figure 6: Schematic of standard BP vs. structured M -layer BP with block mixing. a) Standard BP on the base graph. Each oriented edge e carries a scalar cavity field h^{e} ; its channel‑propagated counterpart is u^{e} (for the Ising pairwise channel U_{ij}(\sigma_{i},\sigma_{j})=e^{\beta J_{ij}\sigma_{i}\sigma_{j}} ). b) Structured M -layer BP. Each oriented edge carries a block vector of cavity fields \{h^{e}_{b}\}_{b=1}^{B} and propagated fields \{u^{e}_{b}\}_{b=1}^{B} . Boxes labeled Q denote the block‑mixing kernel acting linearly on the block index. IV.4 Bi-directional flow in the linear regime We next analyze the dynamics induced by the mixed belief-propagation equations by linearizing them around a fixed point. Throughout this section, we interpret BP iterations as a surrogate dynamics of the structured M -layer system, using them as a predictor of state stability, which we later validate with spin-level MCMC simulations. The BP dynamics is modeled as follows: \displaystyle h^{+}=G(h)=(1-\eta)h+\eta F(h), (30) where the left-hand side term h^{+} is the state after one iteration and \eta the update (or leak) rate introduced to improve convergence. Let \bar{h}^{*} be a steady state of the base graph’s BP dynamics satisfying \bar{h^{*}}=G(\bar{h^{*}}) with B=1 . When Q is row-stochastic, the replicated state \bar{h}=\bar{h}^{*}\otimes 1_{B} is also a fixed point of the BP dynamics for any B>1 . We call the space \bar{h} the uniform -block manifold. We analyze the stability of layer-to-layer fluctuation in the vicinity of the uniform-block manifold. On each oriented edge e=(i\to j) and block b we write \displaystyle h_{b}^{i\to j}=\bar{h}^{\,i\to j}+\delta_{b}^{\,i\to j},\qquad\sum_{b=1}^{B}\delta^{\,i\to j}_{b}=0, (31) i.e. we decompose along the all–ones direction and its zero–sum orthogonal complement. We linearize eq. ( 28 ) around \bar{h} to get \displaystyle\delta^{+}=\left[(1-\eta)I+\eta\left.DF\right|_{\bar{h}}\right]\,\delta, (32) with \displaystyle\left.DF\right|_{\bar{h}}=(W\,K)\otimes Q, (33) where DF is the Jacobian of the BP map F and W is the non-backtracking operator on oriented edges of the base graph: \displaystyle W_{(i\to j),(k\to i)}=\begin{cases}1&\text{if }k\in\partial i,\,k\neq j,\\ 0&\text{otherwise.}\end{cases} (34) Moreover, K=\mathrm{diag}\{\alpha_{k\to i}\} with \alpha_{k\to i} is the edge gain (from u_{b}^{k\to i} w.r.t. h_{c}^{k\to i} ) evaluated at \bar{h} : \displaystyle\alpha_{k\to i}=\left.\frac{\partial u^{k\to i}}{\partial H^{k\to i}}\right|_{\bar{h}}=\frac{\lambda_{ik}}{1-\lambda_{ik}^{2}\bar{m}_{k\to i}^{2}}\,\sech^{2}(\beta\bar{h}^{k\to i}), (35) with \lambda_{ik}=\tanh(\beta J_{ik}) and \bar{m}_{k\to i}=\tanh(\beta\bar{h}^{k\to i}) . W encodes diffusion along the interaction graph without immediate backtracking (or non-backtracking propagation along the interaction graph) weighted by K . Q mixes block components and represents propagation along the layer graph. In the linear regime, these two directions of the information flow are orthogonal. IV.5 Collapse of layer-to-layer fluctuations In this subsection, we characterize the conditions under which fluctuations between layers decay and the layers synchronize to a common state. The spectral properties of Q govern the dynamics of layer-to-layer fluctuations. In the general case, a sufficient criterion for synchronization ( \delta^{i\to j}_{b}\rightarrow 0 ) is 4 4 4 We take \eta=1 for simplicity. \displaystyle\rho\!\big(WK\big)\,\sigma_{2}(Q)<1, (36) where \rho(\cdot) denotes the spectral radius of the base-graph operator and \sigma_{2}(Q) is the second (largest nontrivial) singular value of Q . The spectral radius \rho(WK) quantifies how strongly perturbations are amplified by the dynamics on the base graph, and depends on the local couplings and fields of the current state. By contrast, the singular value \sigma_{2}(Q) controls how efficiently the inter-layer mixing damps non-uniform fluctuations across layers. Synchronization therefore occurs when the mixing induced by Q is sufficiently strong to suppress the most unstable mode of the base-graph dynamics. When this contraction condition is satisfied, the dynamics synchronizes all layers onto the block-uniform subspace in which x_{i,\alpha}=x_{i} for all \alpha . Restricted to this subspace, the lifted Hamiltonian reduces to H_{M}(x)=M\,H(x) , i.e., M identical copies of the base-graph Hamiltonian. Minimizing H_{M} within this synchronized subspace is therefore equivalent to minimizing H on the original graph, with solutions replicated across layers. More precisely, let \{\nu_{j}\} be the eigenvalues of WK (base graph interaction modes) and \phi_{k} the ones of a normal Q matrix (mixing modes). Then for every joint mode (j,k) , fluctuations evolve as: \displaystyle\delta_{j,k,t+1}=\mu_{j,k}\delta_{j,k,t}\quad\text{with}\quad\mu_{jk}=(1-\eta)+\eta\nu_{j}\phi_{k}. (37) It is clear in this formulation that layer-to-layer fluctuations collapse if \max_{j,k}|\mu_{jk}|<1 at the base graph state. Moreover, the decay occurs with the decay rate |\mu_{jk}| with oscillation \arg\mu_{jk} in each mode (j,k) . When Q is symmetric, \phi_{k}\in\mathbb{R} and each mode decays monotonically. When Q is normal but not symmetric (e.g., a circulant ring kernel with drift; see Fig. 2 )), its eigenmodes are complex and the BP dynamics exhibits damped oscillations of its layer-to-layer fluctuation due to wave propagation along the 1D ring (see Appendix VI.4.1 ), creating a Nesterov-like momentum acceleration. This is consistent with our observation that convergence time is reduced with non-zero drift \mu (see Fig. 2 ). We emphasize that these bounds only apply under annealed mixing. If the realized mixing is a fixed symmetric permutation \pi (quenched), then \sigma_{2}(\pi)=1 and no extra shrinkage arises from mixing. Asymmetric permutations coupled with sequential updates at the spin-level MCMC lead to annealed mixing. Figure 7: Spin-level MCMC compared with cavity theory under structured mixing. a) Block-to-block overlap \langle q\rangle vs. mixing strength \sigma . Average overlap between block from 1-RSB cavity theory and MCMC as a function of the standard deviation \sigma of the mixing kernel Q(\sigma) . Error bars show 95% CIs over MCMC repetitions. Theory shows the 1-RSB cavity equations at T=0 with Parisi parameter y=0.31 , population n=30000 , steps=50, and L=30 . MCMC shows N=30 , L=30 , with K=30 random initial conditions, with 200 MCMC steps, averaged over 5 random instances. The overlap is defined as \langle q\rangle(\sigma,B)=\langle\frac{1}{B^{2}}\sum_{b,b^{\prime}}|q_{b,b^{\prime}}|\rangle_{\rm disorder,runs}\in[0,1] with q_{b,b^{\prime}}=\frac{1}{N}\sum_{i=1}^{N}x_{i,b}x_{i,b^{\prime}} . Increasing \sigma strengthens mixing. b) Norm of the block-to-block fluctuation ||\delta|| (see eq. ( 31 )) vs. iteration number of the cavity equations. c) Characteristic time \tau of the block-to-block fluctuation ||\delta|| vs. mixing strength \sigma assuming \tau=-\frac{1}{\log|\mu^{*}|} and ||\delta(t)||=|\mu^{*}|^{t}||\delta(0)|| or ||\delta(t)||=e^{-\frac{t}{\tau}}||\delta(0)|| . \mu^{*} corresponds to the largest eigenvalue defined in eq. ( 37 ). \eta=1 . IV.6 Coarse dynamics of the block average To go beyond the linear stability analysis, we examine higher-order perturbations of the belief-propagation equations and derive an effective coarse-grained dynamics for the layer-averaged messages. In Appendix VI.4.2 , we show that the BP dynamics projected onto the block-uniform manifold (see Fig. 8 ) using the averaging operator \Pi=I\otimes\frac{1}{B}\,\mathbf{1}_{B}\mathbf{1}_{B}^{\top} takes the form \displaystyle\bar{h}^{+} \displaystyle=G(\bar{h})\;+\xi+\;O(|\delta|^{3}), (38) \displaystyle\delta^{+} \displaystyle=\Pi_{\perp}DG|_{\bar{h}}\Pi_{\perp}\delta\;+\;O(|\delta|^{2}), (39) with \displaystyle\xi=\frac{\eta}{2B}W\big(\Gamma q_{Q}(\delta)-\Gamma^{\prime}q_{I}(\delta)), (40) where W is the non-backtracking operator on oriented edges. Moreover, \Gamma=\operatorname{diag}(\Gamma_{e}) and \Gamma^{\prime}=\operatorname{diag}(\Gamma^{\prime}_{e}) are diagonal matrices over stacked oriented edges with \Gamma_{e}=\frac{2\beta\lambda_{e}^{3}m_{e}s_{e}^{2}}{(1-\lambda_{e}^{2}m_{e}^{2})^{2}} and \Gamma^{\prime}_{e}=\frac{2\beta\lambda_{e}m_{e}s_{e}}{1-\lambda_{e}^{2}m_{e}^{2}} representing the edge-wise curvature (second-order sensitivity). Lastly, q_{Q}(\delta)=\|Q\delta^{e}\|_{2}^{2} and q_{I}(\delta)=\|\delta^{e}\|_{2}^{2} represent fluctuation power on edge e with and without mixing. Although we have been able to project the dynamics of h onto the dimension 1 block-uniform manifold \bar{h} , the noise \xi still depends on higher dimensional fluctuations \delta . The fluctuations \delta are driven mainly by the residual distortion across layers of a bundle of edge messages. When the system moves between nearby states in the neighborhood of the block-uniform manifold, the part of the bundle that has not yet synchronized is reflected by a nonzero \delta . The noise amplitude \xi thus reflects some non-local properties. The noise amplitude is driven by the difference between two terms \Gamma q_{Q}(\delta) and \Gamma^{\prime}q_{I}(\delta) . The former relates to the power of fluctuations that survive mixing while the latter is the baseline variance. Thus, \xi represents the excess coherent power of layer-to-layer fluctuations after mixing. When B=1 , \xi=0 there are no inter-layer fluctuations. When Q is homogeneous ( Q_{bc}=\frac{1}{B} ), we have q_{Q}=0 because Q\delta=0 . Only the negative baseline fluctuation power remains. For structured mixing (e.g., a 1D ring), coherent fluctuations across neighboring layers yield large q_{Q}(\delta) and therefore a strong forcing term \xi facilitating escape. The noise \xi acts as a layer-to-layer fluctuation coherence detector: it boosts long‑wavelengths which, in turn, triggers escape from Bethe states of the base graph. In general, cross-layer correlations that are aligned with high-gain mixer modes increase noise amplitude. Figure 8: Schematic of the dynamics on the block-uniform manifold and orthogonal layer-to-layer fluctuation subspaces. Trajectories evolve near the uniform manifold h_{b}=\bar{h} with block fluctuations h_{b}=\bar{h}+\delta_{b} . BP dynamics in the original graph is confined to the block uniform manifold space and could get trapped in a stable local, but not global, minimum of the base-graph Bethe potential (left minimum of the dashed blue potential and blue trajectories flowing to this minimum). However, the graph lifting leads to a higher dimensional dynamics that includes nonzero layer-to-layer fluctuations across blocks that can destabilize the previously stable BP fixed point. This higher dimensional dynamics can thus escape local minima of the original base-graph Bethe potential (red curve), and reach to lower energies. The amplitude of the fluctuation \delta is annealed near the contraction threshold. V 1-RSB Complexity In glassy optimization problems, the energy landscape typically contains an exponential number of metastable fixed points of the replica-symmetric belief-propagation equations, often referred to as Bethe states. The associated complexity \Sigma measures the logarithmic density of these states as a function of energy and provides a statistical-mechanical characterization of landscape ruggedness at the level of belief propagation. The replica-symmetric analysis of the previous section showed that structured mixing suppresses layer-to-layer fluctuations and drives the dynamics toward block-uniform configurations. To quantify how this mechanism affects the organization and abundance of metastable Bethe states in the lifted model, we now turn to the one-step replica-symmetry-breaking (1-RSB) formalism. In this framework, complexity counts the number of distinct BP fixed points (or pure states) compatible with the mixed message-passing equations, rather than spin-level local minima of the underlying Hamiltonian. The 1-RSB analysis thus provides a natural way to assess whether structured M -layer mixing merely suppresses inconsistent cross-layer configurations, or more broadly reshapes the effective ruggedness of the Bethe free-energy landscape explored by local algorithms. V.1 1–RSB ansatz For clarity, we briefly recall the one-step replica-symmetry-breaking (1-RSB) ansatz. At the RS level, each oriented edge (i\to j) carries a block-indexed cavity message p_{b}(x) parametrized by a single field h_{b} . In the 1 - RSB formalism, these messages become random variables drawn from a mixture of pure states. We emphasize that the notion of layers introduced by the structured M -layer construction is distinct from that of replicas in the 1-RSB formalism: layers are explicitly coupled through the inter-layer permutations, whereas replicas correspond to independent copies of the lifted system that can occupy different Bethe states. Replicas are partitioned into groups of size x , and exchangeability within each group implies via de Finetti’s theorem that the spins in a group are i.i.d. conditioned on a latent cavity field. Thus the 1 - RSB order parameter is a probability distribution P_{h} over block-field vectors \displaystyle h=(h_{1},\ldots,h_{B})\in\mathbb{R}^{B}. (41) This distribution encodes the mixture of pure states, and the corresponding recursive distributional equations (RDEs) arise by applying belief propagation on the auxiliary factor graph defined by the mixed BP updates. V.2 Auxiliary factor graph and reweighting Our 1-RSB analysis follows the standard cavity-theoretic framework developed in Refs. 26 ; 24 . Interpreting RS messages as random variables allows one to define an auxiliary factor graph whose variables are \{\,p_{i\to j},\ \hat{p}_{j\to i}\,\} and whose factors enforce the mixed BP equations p=f(\hat{p}) and \hat{p}=\hat{f}(p;Q) with f and \hat{f} defined in eqs. ( 24 ) and ( 22 ). The weight of a configuration is the Bethe free energy of the M -layer, raised to the Parisi exponent: W_{x}[p]\propto e^{x\,S[p]}, where S[p] is the Bethe action eq. ( 19 ). Applying BP on this auxiliary graph yields recursive distributional equations (RDEs) for the law P_{h} , exactly as in the standard 1-RSB cavity method but with the modification that the propagation step uses the block-mixed fields H=Qh . As shown in Appendix VI.5 , regrouping the Bethe free-energy terms and choosing a convenient Bethe gauge isolates the local normalizers z_{i\to j} and allows them to be written in block-factorized form. In the zero-temperature limit this produces a neighbor-separable weight, which is essential for correct RDE sampling. V.3 Zero-temperature RDE At zero temperature, we define y=\beta x and take \beta\to\infty with y fixed and obtain the 1-RSB recursion for the distribution P_{h}^{+} of cavity-field surveys, defined as follows: \displaystyle P_{h}^{+}(dh) \displaystyle\propto\int\prod_{k\in\partial i\setminus j}\Big[P_{h}(dh^{k})\,\mu_{J}(dJ_{k})\,w_{\mathrm{neigh}}(h^{k},J_{k})\Big] \displaystyle\qquad\times\;\delta\!\left(h-\sum_{k\in\partial i\setminus j}u(h^{k},J_{k})\right). (42) with the zero-temperature neighbor weight \displaystyle w_{\mathrm{neigh}}(h,J)\propto\exp\Big\{\frac{y}{B}\sum_{b=1}^{B}a_{b}(h,J)\Big\}. (43) The term u_{b}(h,J) in the update rule is given in eq. ( 29 ) and the term a_{b}(h,J) is given as: \displaystyle a_{b}(h,J)=\tfrac{1}{2}\big(|J+H_{b}|+|J-H_{b}|\big)=\max\{|J|,|H_{b}|\}. (44) For simplicity, we restrict attention to the factorized approximation of the M -layer cavity equations; extending the analysis to the exact 1-RSB formulation is straightforward, though it entails a substantially higher computational cost. V.4 Energy and complexity at T=0 Moreover, the energetic potential is \Phi(y)=-\frac{1}{y}\log\mathbb{E}\big[e^{-y\Delta E^{(1)}}\big]\;+\;\frac{d}{2y}\log\mathbb{E}\big[e^{-y\Delta E^{(2)}}\big], (45) with site- and link-energy increments given as follows: \displaystyle\Delta E^{(1)} \displaystyle=-\frac{1}{B}\sum_{b=1}^{B}\Bigg[\sum_{k=1}^{d}a_{b}(h^{(k)},J_{k})+\Big|\sum_{k=1}^{d}u_{b}(h^{(k)},J_{k})\Big|\Bigg], (46) \displaystyle\Delta E^{(2)} \displaystyle=-\max_{\sigma_{i},\sigma_{j}=\pm 1}\max_{b,b^{\prime}:\,Q_{bb^{\prime}}>0}\big(h_{b,i}\sigma_{i}+J\,\sigma_{i}\sigma_{j}+h_{b^{\prime},j}\sigma_{j}\big). (47) From \Phi(y) one obtains the selected energy: \displaystyle U^{*}(y)=\frac{\partial}{\partial y}\big[y\,\Phi(y)\big], (48) and the complexity \displaystyle\Sigma(y)=y\big(U^{*}(y)-\Phi(y)\big)=y^{2}\frac{\partial\Phi}{\partial y}. (49) The free energy, energy-per-site, and complexity of the M-layer lift for random regular graphs of degree 3 are shown in Fig. 9 . For B=1 these reduce exactly to the classical 1-RSB random regular graph equations of 26 . As the number of blocks increase, the area under the complexity curve decreases (see Fig. 9 c)), which we interpret as a smoothing of the energy landscape induced by the interactions between layers. This collapse of complexity is consistent with the spin-level MCMC simulations in Fig. 3 , which show that increasing the number of blocks raises the probability that quench dynamics reaches the true ground state. Figure 9: Complexity collapse in the structured M-layer model. a) Free energy \phi(y) as a function of the Parisi parameter y . b) Energy-per-site \epsilon(y)=\frac{d}{dy}\big(y\phi(y)\big) . c) Complexity \Sigma(\epsilon)=y^{2}\frac{d\phi(y)}{dy} as a function of \epsilon . Black solid line [MP03] denote the factorized cavity-theory predictions from Ref. 26 , while colored symbols correspond to M-layer cavity theory (this work). Reference free energy indicated are one-step replica-symmetry-breaking [RSB] with e=-1.2717 26 , its factorized approximation [RSB-fac] with e=-1.2723 26 , and brute force ([BF] with e=-1.2719~ 10 published in 2002, [BF2] with e=-1.2720 18 published in 2021). Error bars represent statistical uncertainties from RDE simulations. \mu=1.5 , \sigma=0.8 , L=1 . Population size is 9\times 10^{4} cavity fields iterated for 200 steps, averaged of 4096 trials. VI Conclusion We introduced a structured M -layer lift that smooths the rugged energy landscape of generic probabilistic graphical models by coupling replicated factor graphs through a tunable mixing kernel. Because it modifies only the interaction topology, this construction can be combined with a broad range of local-update algorithms and problem classes, and we showed that it systematically improves access to near-MAP configurations at reduced computational cost. Our cavity analysis reveals that the smoothing effect induced by the structured M -layer lift has a dynamical origin. When the dynamics are projected onto the block-uniform manifold of the base graph, coherent layer-to-layer fluctuations act as a finite noise source that drives controlled escapes from metastable Bethe states. Even for a minimal mixing topology such as a Gaussian circulant ring the resulting message evolution supports nontrivial behavior, including a Nesterov-like acceleration in message space. Furthermore, the linear stability analysis identifies a contraction threshold at which the dominant inter-layer mode changes from expanding to contracting. At this point the lifetime of coherent layer fluctuations diverges, producing a transition between a disordered regime (with sustained layer heterogeneity) and a synchronized regime (in which blocks collapse onto a common trajectory). This critical behavior is reminiscent of a ferromagnetic instability, but it occurs in the higher-dimensional configuration space of cavity messages rather than in the physical spins themselves. At the 1-RSB level, we find that the configurational complexity collapses as the number of blocks increases, providing a statistical-mechanical explanation for the observed reduction in metastable states. This scheme extends the standard cavity-theoretic framework 27 by introducing a controlled linear mixing of replicated messages through a permutation ensemble parameterized by Q . Although one could run belief propagation directly on the lifted graph, the advantage of the structured M -layer lift is that it induces Bethe-like smoothing while remaining compatible with simple local dynamics such as standard MCMC. In contrast to parallel tempering or replica exchange 40 ; 14 , which couple replicas by swapping thermodynamic parameters, the M -layer mixes the marginal information itself, producing a richer and more coherent microscopic evolution. Likewise, unlike spatially coupled LDPC constructions where a seeded boundary drives convergence, the collapse to a single solution in the structured M -layer arises autonomously from the inter-layer mixing. While spin-level and cavity-level simulations reach near-MAP configurations on all tested instances, we do not claim polynomial-time guarantees for finding global minima in general. A more complete understanding of relaxation times, finite-size effects, and instance-dependent behavior will require a dedicated analysis. The simplicity of the construction suggests that sharper algorithmic or complexity-theoretic statements may be achievable, but such results remain open. Our theoretical treatment focuses on the leading O(\frac{1}{M}) contribution to the free energy and dynamics. Higher-order terms, corresponding to explicit loop corrections in the naked-cluster expansion 1 , have not been included here. Extending the expansion beyond first order, or designing dilution schemes that tune the loop order without relying on block structure, would provide a more complete description of finite-dilution effects. These directions lie beyond the scope of the present work but represent natural and important extensions. We also emphasize that our theoretical analysis builds on the assumptions stated in Sec. IV.1 , where we restrict attention to fixed points of the mixed belief-propagation dynamics despite the presence of asymmetric interactions in the lifted graph. While this appears sufficient to capture the thermodynamically dominant behavior in the regimes studied here, a more complete treatment would require a genuinely dynamical cavity framework capable of describing time-dependent spin or message trajectories. Developing such a dynamical extension at the one-step replica-symmetry-breaking level remains an open and challenging problem. Another promising direction is to investigate the dynamics induced by richer mixing kernels, including problem-dependent or hierarchical designs. Such kernels could shape the inter-layer correlations in more targeted ways and may further accelerate convergence toward optimal configurations. Beyond spin-glass Ising models, the same lifting can likely improve combinatorial tasks such as SAT and coloring, and it may aid generalization in machine learning by favoring isotropic minima 9 . The approach also fits hardware co-design: because the “algorithm” is the wiring pattern, physical implementations (e.g., optical or electronic Ising machines 43 ; 44 ) can realize Q directly as inter-layer connectivity. The same principle may also aid relaxation in other networked systems (e.g., metamaterials, power grids, social or information networks) by speeding convergence to low-energy states. VI.1 Notation The main symbols used throughout the paper are summarized in Table 2 . Table 2: Summary of main notation used in the paper. Symbol Meaning M Number of layers in the lifted graph. B Number of blocks used to define the structured mixing kernel. L Block size, with M=BL . \pi_{a,i} Inter-layer permutation associated with incidence (a,i) . Q Mixing matrix controlling how edges are rewired between layers. \sigma,\mu Parameters of the ring mixing kernel: width (diffusion scale) and drift (bias along the ring). H(x) Ising Hamiltonian of the base graph. p_{b}^{\,i\to j}(x) Variable-to-factor cavity message in block b . \hat{p}_{b}^{\,k\to i}(x) Propagated (block-mixed) message from neighbor k to i . h_{b}^{\,i\to j} Cavity field corresponding to p_{b}^{\,i\to j} . u_{b}^{\,k\to i} Effective field propagated from k to i after mixing. H_{b} Block-mixed field defined as H_{b}=\sum_{c}Q_{bc}h_{c} . VI.2 Bethe functional with mixing In this section, we generalize the calculation of M-layer free energy 21 to the case of structured permutations. We work in the large-M regime M=BL with fixed block count B and block size L\to\infty , and choose the permutation weights so that individual layer-to-layer connection probabilities scale as \mathcal{O}(1/L) . The main objective is to average the replicated partition function of the lifted M-layer model of eq. ( 4 ) over the permutation ensemble described in eq. ( 14 ) to obtain the free energy as a function of block mixing matrix Q defining the matrix-weighted random permutation law. VI.2.1 Definitions This section is written for the case of the Ising model (without Zeeman term) with f_{(ij)}(x_{i},x_{j})=e^{\beta J_{ij}x_{i}x_{j}} for x_{i}\in\{-1,1\} . We thus get: \displaystyle P(x)=\frac{1}{Z_{M}}\exp(-\beta H_{M}(x)), (50) with \beta the inverse temperature and \displaystyle H_{M}(x;C)=-\sum_{\alpha,\beta=1}^{M}\sum_{i0,\qquad\sum_{x_{i}}p_{b}^{i\to j}(x_{i})=1. (125) Thus the space of messages is the interior of a 2-dimensional probability simplex. For binary variables, this space is one-dimensional: any probability distribution (p(+1),p(-1)) is fully determined by its magnetization \displaystyle m_{b}^{i\to j}=p_{b}^{i\to j}(+1)-p_{b}^{i\to j}(-1). (126) It is therefore natural to use an exponential-family parametrization. The unique canonical representation for a binary distribution with magnetization m is \displaystyle p(x)=\frac{1+mx}{2}=\frac{e^{\beta hx}}{2\cosh(\beta h)}, (127) where the “cavity field” h is the natural parameter (the Bernoulli message distributions belong to an exponential family), related to the magnetization by \displaystyle m=\tanh(\beta h),\qquad h=\frac{1}{\beta}\operatorname{artanh}(m). (128) In particular, we have \displaystyle p_{b}^{i\to j}(x_{i})=\frac{e^{\beta h_{b}^{i\to j}\,x_{i}}}{2\cosh(\beta h_{b}^{i\to j})}, (129) where h_{b}^{i\to j} is the local cavity field. The corresponding local magnetization is the mean spin \displaystyle m_{b}^{i\to j}=\mathbb{E}[x_{i}]=\tanh(\beta h_{b}^{i\to j}). (130) Propagation through edge (k,i) with block mixing Q yields a propagated factor \displaystyle\hat{p}_{b}^{\,k\to i}(x_{i})=C_{ik,b}\,e^{\beta u_{b}^{\,k\to i}x_{i}}, (131) with \displaystyle\tanh(\beta u_{b}^{\,k\to i})=\tanh(\beta J_{ik})\sum_{c}Q_{bc}\,\tanh(\beta h_{c}^{\,k\to i}), (132) and C_{ik,b}=\cosh(\beta J_{ik})/\cosh(\beta u_{b}^{\,k\to i}) . Inserting this parametrization into the Bethe functional and enforcing stationarity with respect to variations of p_{b}^{i\to j} yields the BP saddle-point equation \displaystyle p_{b}^{i\to j}(x_{i})\propto\prod_{k\in\partial i\setminus j}\hat{p}_{\,b}^{k\to i}(x_{i}), (133) which in the exponential-family form becomes simply an additive update in the field variables: \displaystyle\beta h_{b}^{i\to j}=\sum_{k\in\partial i\setminus j}\operatorname{atanh}\!\left[\tanh(\beta J_{ik})\,(Qm^{k\to i})_{b}\right], (134) or equivalently, \displaystyle h_{b}^{i\to j}=h_{i}+\sum_{k\in\partial i\setminus j}u_{b}^{k\to i}, (135) where h_{i} is the local field (if present) and u_{b}^{k\to i} is the effective field sent from neighbor k to i through block b (given explicitly in eq. ( 28 )). In this parametrization the BP update becomes linear in the fields even though it is nonlinear in the underlying probabilities. This makes the field representation the natural choice for both analytical derivations and numerical algorithms. VI.4 Dynamics of BP with mixing VI.4.1 Momentum in BP If Q is normal but not symmetric, for instance a circulant ring kernel with drift (see Fig. 2 ), Q can be diagonalized by a discrete Fourier transform Q=V\Phi V^{*} with V_{\alpha k}=\frac{1}{\sqrt{B}}\,e^{-2\pi i\frac{(\alpha-1)(k-1)}{B}} and complex eigenvalues \phi_{k}=\rho_{k}e^{i\omega_{k}} . Eliminating the phase gives a two-step recurrence identical to the heavy-ball or momentum form for each joint mode of the lifted system given as (when \eta=1 ): \displaystyle\delta_{j,k,t+1}=(1-\lambda_{j,k}+\beta_{j,k})\,\delta_{j,k,t}-\beta_{j,k}\,\delta_{j,k,t-1}, (136) with \beta_{j,k}=|\nu_{j}\phi_{k}|^{2} and \lambda_{j,k}=1+|\nu_{j}\phi_{k}|^{2}-2\,\Re(\nu_{j}\phi_{k}) where \nu_{j} are the eigenvalues of W\,K . The drift angle \omega_{k} introduces oscillatory “momentum”, while the width \sigma of Q controls the damping \rho_{k} . Mixing therefore acts like a distributed momentum term that accelerates synchronization while preserving the same collapse condition |\nu_{j}|\rho_{k}<1 . VI.4.2 Projection on homogenous In this section, BP iteration of eq. ( 30 ) are projected onto the block-uniform manifold. We define the projection onto the block-uniform manifold \Pi=I\otimes\Pi_{B} with \Pi_{B}=\frac{1_{B}1_{B}^{\top}}{B}=\frac{1}{B}1_{B}1_{B}^{\top} and \Pi^{\perp}=I-\Pi its orthogonal subspace (the fluctuation subspace). Given h=\bar{h}+\delta , we thus have \Pi h=\bar{h} and \Pi\delta=0 . We expand eq. ( 30 ) in \delta as follows: \displaystyle\bar{h}^{+}=G(\bar{h})+DG|_{\bar{h}}\delta+D^{2}G|_{\bar{h}}[\delta,\delta]+O(|\delta|^{3}). (137) First, consider the linear part in DG|_{\bar{h}}\delta . If Q is doubly stochastic, then \displaystyle\Pi D_{G}|_{\bar{h}}\Pi^{\perp} \displaystyle=(1-\eta)\Pi\Pi^{\perp}+\eta\Pi D_{F}|_{\bar{h}}\Pi^{\perp} \displaystyle=\eta(WK)\otimes(\Pi_{B}Q\Pi_{B}^{\perp})=0. (138) That is, fluctuations inject no linear bias into the uniform manifold. Next, we calculate the second order term D^{2}G|_{\bar{h}}[\delta,\delta]=\eta D^{2}F|_{\bar{h}}[\delta,\delta] . Recall that F(h)=\sum_{k\in\partial i\setminus j}u_{b}^{k\to i} (see eq. ( 28 )) with u_{b}^{e} given as follows for each edge e and block b : \displaystyle\tanh(\beta u_{b}^{e})=\lambda_{e}\sum_{c}Q_{bc}\tanh(\beta h^{e}_{c}). (139) with \lambda^{e}=\tanh(\beta J_{ik}) . that is u_{b}^{e}=g\big((Qm(h^{e}))_{b}\big) with \displaystyle g(x)=\beta^{-1}\operatorname{artanh}(\lambda^{e}x),\quad m(h)=\tanh(\beta h). (140) A second–order expansion at \bar{h} yields \displaystyle D^{2}u_{b}^{e}|_{\bar{h}}[\delta^{e},\delta^{e}]=\underbrace{\beta^{2}s_{e}^{2}g^{\prime\prime}(m_{e})}_{\Gamma_{e}}((Q\delta_{e})_{b})^{2}+\underbrace{\beta^{2}g^{\prime}(m_{e})(-2m_{e}s_{e})}_{-\Gamma^{\prime}_{e}}\sum_{c}Q_{bc}(\delta^{e}_{c})^{2}. (141) with D^{2}u^{e}_{b}|_{\bar{h}}\,[\delta_{e},\delta_{e}]=\sum_{c,c^{\prime}}\frac{\partial^{2}u^{e}_{b}}{\partial h^{e}_{c}\,\partial h^{e}_{c^{\prime}}}|_{\bar{h}}\delta^{e}_{c}\delta^{e}_{c^{\prime}} and \displaystyle g^{\prime}(m_{e})=\frac{\lambda_{e}}{\beta(1-\lambda_{e}^{2}m_{e}^{2})},\quad g^{\prime\prime}(m_{e})=\frac{2\lambda_{e}^{3}m_{e}}{\beta(1-\lambda_{e}^{2}m_{e}^{2})^{2}}. (142) given \displaystyle m_{e}=\tanh(\beta\bar{h}^{e}),\quad s_{e}=\sech^{2}(\beta\bar{h}^{e}). (143) We have: \displaystyle\Gamma_{e}=\frac{2\beta\lambda_{e}^{3}m_{e}s_{e}^{2}}{(1-\lambda_{e}^{2}m_{e}^{2})^{2}},\quad\Gamma^{\prime}_{e}=\frac{2\beta\lambda_{e}m_{e}s_{e}}{1-\lambda_{e}^{2}m_{e}^{2}}. (144) Note that we have (h^{+})^{e}_{b}=F^{e}_{b}(h)=(Wu_{b}(h))^{e} . Averaging over blocks with \Pi_{B} gives, for each edge e , \displaystyle(\Pi D^{2}F|_{\bar{h}}[\delta,\delta])^{e}=\frac{1}{B}\big(\Gamma_{e}(Q)\|Q\delta^{e}\|_{2}^{2}-\Gamma_{e}(I)\|\delta^{e}\|_{2}^{2}\big). (145) Since D^{2}G=\eta D^{2}F , the quadratic forcing on the block average is \displaystyle\xi=\frac{\eta}{2B}W\big(\Gamma q_{Q}(\delta)-\Gamma^{\prime}q_{I}(\delta)\big), (146) where \Gamma=\operatorname{diag}(\Gamma_{e}) and \Gamma^{\prime}=\operatorname{diag}(\Gamma^{\prime}_{e}) over oriented edges with q_{Q}(\delta)=\|Q\delta^{e}\|_{2}^{2} and q_{I}(\delta)=\|\delta^{e}\|_{2}^{2} . In summary: \displaystyle\bar{h}^{+}=G(\bar{h})+\xi+O(\|\delta\|^{3}), (147) \displaystyle\delta^{+}=\Pi^{\perp}D_{G}|_{\bar{h}}\Pi^{\perp}\,\delta+O(\|\delta\|^{2}). (148) VI.5 1-RSB formalism VI.5.1 1-RSB ansatz For a fixed oriented edge (i\to j) and block b , the replicated message p_{b}^{\,i\to j}(x^{1},\ldots,x^{n}) is symmetric in replicas. In 1‑RSB with Parisi parameter x\in(0,1] , replicas are partitioned into n/x groups of size x and are exchangeable within each group. By de Finetti, within a group spins are conditionally i.i.d. Bernoulli with a latent “spin‑up” probability \pi\in(0,1) with \displaystyle\mathbb{P}(x=+1\mid\pi)=\pi,\qquad\mathbb{P}(x=-1\mid\pi)=1-\pi, (149) let \mu_{b} be a probability measure on \pi (the intra‑state field distribution for block b ), and let P_{b}^{\,i\to j} be a law on such measures (a “survey” over pure states), then \displaystyle p_{b}^{\,i\to j}(\{x^{a}\}) \displaystyle=\int P_{b}^{\,i\to j}(d\mu_{b})\,\Bigg[\int\mu_{b}(d\pi)\;\prod_{a=1}^{x}\pi^{\frac{1+x^{a}}{2}}(1-\pi)^{\frac{1-x^{a}}{2}}\Bigg]^{\!n/x}. (150) Write m=2\pi-1\in(-1,1) and h=\beta^{-1}\operatorname{artanh}m so that \pi=(1+\tanh\beta h)/2 and \displaystyle\pi^{\frac{1+x}{2}}(1-\pi)^{\frac{1-x}{2}}=\frac{e^{\beta hx}}{2\cosh(\beta h)}. (151) After the \pi\mapsto h change of variables, P_{b}^{i\to j} becomes a measure on measures \nu_{b} over cavity fields h\in\mathbb{R} . The ansatz becomes the standard mixture of RS group factors in h : \displaystyle p_{b}^{\,i\to j}(\{x^{a}\})=\int P_{b}^{\,i\to j}(d\nu_{b})\,\Bigg[\int\nu_{b}(dh)\;\prod_{a=1}^{x}\frac{e^{\beta hx^{a}}}{2\cosh(\beta h)}\Bigg]^{\!n/x}\!, (152) i.e. “draw a state \nu_{b} , then draw one field h per replica‑group, and make the x spins in the group i.i.d. with law e^{\beta hx}/(2\cosh\beta h) .” Note that, because the block-mixing Q couples the B components at propagation, the object to consider is the joint law on h=(h_{1},\dots,h_{B}) . For readability we present component-wise formulas, with the understanding that the input to each block- b update depends on the vector of incoming fields \{h_{c}\}_{c=1}^{B} through the Q -mixing. In summary, exchangeability implies that across pure (Bethe) states, the RS message on each oriented edge becomes a random variable; the 1-RSB order parameter is a probability law over messages (a law over block-field vectors \bm{h}=(h_{1},\dots,h_{B}) ). VI.5.2 1-RSB factor graph of messages When interpreting RS messages a random variables, we can now interpret the probability of messages as an auxiliary probabilistic graphical model in which messages are variables and RS BP equations define factors (see Fig. 10 ). Figure 10: a) Base factor graph with variables (circles) and factors (squares). b) M -layer lift: the entire factor graph is copied M times and corresponding variable–factor incidences are rewired across layers according to permutations drawn from the mixing matrix Q . c) 1-RSB representation of the base graph: each message (i,a) becomes a variable. Variables i , factors a , and each edge (i,a) is expanded into factors enforcing the BP iterative equations and 1-RSB reweighting. d) 1-RSB representation of the M -layer lift: the construction in (c) is replicated M times and rewired across layers using the same Q -distributed permutations as in (b). We define an auxiliary graphical model whose variables are the RS messages on each edge, \{p^{i\to j},\,\hat{p}^{j\to i}\} and impose the mixed-BP constraints \displaystyle p=f(\hat{p}),\qquad\hat{p}=\hat{f}(p;Q) (153) as hard factors where f and \hat{f} are given by eqs. ( 24 ) and ( 22 ), and weight each message configuration by the Bethe free energy F (which is F[p]=-S[p] with S the Bethe action) of the M -layer (see eq. ( 19 )) raised to x : \displaystyle W_{x}[p] \displaystyle=e^{xS[p]}, (154) with \displaystyle S[p]=\sum_{(i,j)\in E}\log Z_{ij}-\frac{1}{B}\sum_{i\in V}\sum_{b=1}^{B}\log Z_{ib}, (155) with Z_{ij} , Z_{ib} , and \hat{p} defined in Eqs. ( 20 )–( 22 ). Applying BP on this auxiliary model yields the 1-RSB recursive distributional equations, as in the standard cavity construction but with block mixing entering through \hat{f} . For the purpose of the 1-RSB reweighting, it is convenient to rewrite the Bethe free energy F[p]=-S[p] in a directed, gauge-dependent form. We therefore decompose F[p] as F[p]=\sum_{(ij)\in E}F_{ij}+\sum_{i\in V}F_{i}-\sum_{(i\to j)\in\vec{E}}F_{i,(ij)}, (156) where the undirected edge and site contributions are defined as \displaystyle F_{ij} \displaystyle=\log Z_{ij}, (157) \displaystyle F_{i} \displaystyle=\frac{1}{B}\sum_{b=1}^{B}\log Z_{ib}, (158) and F_{i,(ij)} denotes a directed cavity contribution. The consistency condition \displaystyle\sum_{(i\to j)\in\vec{E}}F_{i,(ij)}=2\sum_{(ij)\in E}F_{ij} (159) ensures that Eq. ( 156 ) is equivalent to the symmetric form of the Bethe free energy. To make the directed contribution explicit, we introduce the block-resolved cavity normalizers z_{\,b}^{i\to j}=\sum_{x_{i}=\pm 1}\prod_{k\in\partial i\setminus j}\hat{p}_{b}^{\,k\to i}(x_{i}), (160) which normalize the RS BP updates p_{b}^{\,i\to j}(x_{i})\propto\prod_{k\neq j}\hat{p}_{b}^{\,k\to i}(x_{i}) . The directed cavity free-energy term is then defined as the block average F_{i,(ij)}=\frac{1}{B}\sum_{b=1}^{B}\log z_{\,b}^{i\to j}. (161) It is also convenient to introduce the associated variable- and factor-side normalization factors 24 z_{i\to j}=e^{F_{i}-F_{i,(ij)}},\qquad\hat{z}_{j\to i}=e^{F_{ij}-F_{i,(ij)}}. (162) These quantities correspond, respectively, to the normalization of the variable-to-factor and factor-to-variable BP updates. Because the Bethe free energy is invariant under local gauge transformations that redistribute contributions between site, edge, and directed cavity terms, we may choose a reference-orientation gauge in which F_{i,(ij)}=F_{ij}. (163) In this gauge, the factor-to-variable normalization reduces to \hat{z}_{j\to i}=1, (164) and all reweighting is carried by the variable-side cavity normalizers z_{i\to j} . This choice is particularly convenient for obtaining a neighbor-separable reweighting in the zero-temperature limit. VI.5.3 Change gauge We further apply a Bethe gauge: \displaystyle F_{i} \displaystyle\;\mapsto\;\widetilde{F}_{i}=F_{i}-H_{i}, (165) \displaystyle F_{i,(ij)} \displaystyle\;\mapsto\;\widetilde{F}_{i,(ij)}=F_{i,(ij)}-H_{i,(ij)}, (166) \displaystyle F_{ij} \displaystyle\;\mapsto\;\widetilde{F}_{ij}=F_{ij}+\Delta_{ij}, (167) which keeps F unchanged when we choose \displaystyle\sum_{\{ij\}}\Delta_{ij}\;=\;\sum_{(i\to j)}H_{i,(ij)}\;-\;\sum_{i}H_{i}. (168) We set in particular: \displaystyle\widetilde{F}_{i} \displaystyle\;=\;F_{i}-\frac{1}{B}\sum_{b}\log\!\bigl(2\cosh(\beta S_{b})\bigr), (169) \displaystyle\widetilde{F}_{i,(ij)} \displaystyle\;=\;F_{i,(ij)}-\frac{1}{B}\sum_{b}\log\!\bigl(2\cosh(\beta S_{b\setminus j})\bigr), (170) with S_{b}=\sum_{k\in\partial i}u_{b}^{k\to i} and S_{b\setminus j}=\sum_{k\in\partial i\setminus j}u_{b}^{k\to i} . This choice is motivated by the fact that this will lead to neighbor-separable reweighting at zero temperature allowing to sample each neighbor of a site independently. Recall that \hat{p}^{\,b}_{k\to i}(x_{i})=C_{ik,b}\,e^{\beta u^{\,b}_{k\to i}x_{i}} (see Eq. ( 131 )). Therefore, the block-resolved site partition factor is \displaystyle Z_{ib} \displaystyle=\sum_{x_{i}=\pm 1}\prod_{k\in\partial i}\hat{p}_{b}^{\,k\to i}(x_{i})=2\left(\prod_{k\in\partial i}C_{ik,b}\right)\cosh(\beta S_{b}). (171) Since the Bethe free energy contains the block-averaged site contribution F_{i}=\frac{1}{B}\sum_{b}\log Z_{ib} , the difference between the site and cavity free energies entering the 1-RSB reweighting can be written as \displaystyle F_{i}-F_{i,(ij)}= \displaystyle\frac{1}{B}\sum_{b}\Bigl[\log\cosh(\beta S_{b})-\log\cosh(\beta S_{b\setminus j})\Bigr]+\text{Cst}, (172) where the constant terms independent of the messages have been dropped. With the above gauge choice, the corresponding 1-RSB reweighting factor reads \displaystyle w(h,J) \displaystyle=e^{x(\widetilde{F}_{i}-\widetilde{F}_{i,(ij))})} \displaystyle=e^{\!\left\{-\frac{x}{B}\sum_{b}\bigl[\log\cosh(\beta S_{b})-\log\cosh(\beta S_{b\setminus j})\bigr]\right\}}, (173) which is neighbor-separable and leads to a factorized reweighting in the zero-temperature limit. VI.5.4 Zero-temperature limit At zero temperature ( \beta\rightarrow\infty ), we get the following BP iterative equations in the cavity field h : \displaystyle(h_{\,b}^{i\to j})^{+}=h_{i}+\sum_{k\in\partial i\setminus j}u_{\,b}^{k\to i}. (174) with \displaystyle u_{\,b}^{k\to i}=\frac{1}{2}\bigl(\lvert J_{ik}+H_{\,b}^{k\to i}\rvert-\lvert J_{ik}-H_{\,b}^{k\to i}\rvert\bigr) (175) and H with H_{\,b}^{k\to i}=(Qh^{k\to i})_{b} is the mixed field. Moreover, the variable side local normalizers, noted w(h,J) , can be rewritten as follows using \log\cosh(\beta t)=\beta|t|+o(\beta) : \displaystyle w(h,J)=e^{\,-x(\widetilde{F}_{i}-\widetilde{F}_{i,(ij)})}\;\propto\;\prod_{k\in\partial i\setminus j}\exp\!\left\{\frac{y}{B}\sum_{b=1}^{B}a_{b}\!\left(h_{k\to i},\,J_{ik}\right)\right\} (176) where y=\beta x and a_{b}(h,J)=\frac{\bigl|J+(Qh)_{b}\bigr|+\bigl|J-(Qh)_{b}\bigr|}{2} . The RDE equation is then given as follows: \displaystyle P^{\mathrm{out}}_{i\to j}(dh^{i\to j})\;\propto\;\int\Biggl[\prod_{k\in\partial i\setminus j}P_{k\to i}\bigl(dh^{k\to i}\bigr)\Biggr]\,K_{i\to j}\!\left(\{h^{k\to i}\}\right)\,\delta^{B}\!\left(h^{i\to j}-\left[\sum_{k\in\partial i\setminus j}u(h^{k\to i},J_{ik})\right]\right) (177) where K_{i\to j}\propto\prod_{k\in\partial i\setminus j}w\!\left(h^{k\to i}\,;\,J_{ik}\right) and u_{b}(h,J)=\frac{\bigl|J+(Qh)_{b}\bigr|-\bigl|J-(Qh)_{b}\bigr|}{2} . We have used the notation \delta^{B} for the vector delta (the Kronecker delta product over b ). When B=1 , we recover \displaystyle a(h,J) \displaystyle=\frac{1}{2}\bigl(|J+h|+|J-h|\bigr), (178) \displaystyle u(h,J) \displaystyle=\frac{1}{2}\bigl(|J+h|-|J-h|\bigr), (179) and therefore \displaystyle w \displaystyle\propto\prod_{k\in\partial i\setminus j}\exp\!\bigl[y\,a(h^{k\to i},J_{ik})\bigr], (180) \displaystyle h_{i\to j} \displaystyle=\sum_{k\in\partial i\setminus j}u(h^{k\to i},J_{ik}), (181) which is the standard T=0 cavity theory 26 . VI.6 Construction of permutations We detail here how the M -layer lift is numerically constructed in practice for the Ising model. Each edge in the base coupling matrix J is replicated across M layers, with inter-layer wiring sampled from a permanental distribution derived from the mixing matrix Q . Given a non-negative matrix Q , we first compute a doubly stochastic normalization \displaystyle\tilde{Q}=\operatorname{diag}(r)\,Q\,\operatorname{diag}(c), (182) obtained by iterative Sinkhorn rescaling (obtained by alternating row and column normalization) in the log-domain to machine precision. Sinkhorn balancing rescales Q to be approximately doubly stochastic, removing marginal inhomogeneities so that the subsequent permanental weighting is not dominated by trivial row/column scale differences. The goal is then to draw a permutation \pi\in S_{M} with probability proportional to the permanent of the submatrix selected by \pi : \displaystyle P(\pi)\propto\prod_{a=1}^{M}\tilde{Q}_{a,\pi(a)}=\exp(\sum_{a}\log\tilde{Q}_{a,\pi(a)}). (183) To generate biased inter-layer permutations, we use an approximate perturb-and-MAP sampler based on entrywise Gumbel perturbations 34 ; 41 followed by a Hungarian assignment solve. This procedure provides a tractable heuristic for sampling permutations biased by the permanental weight induced by Q , with computational complexity O(M^{3}) . For each nonzero coupling |J_{ij}|>0 with i0 : the initial temperature is chosen to give a high target acceptance (default 0.85 ), and the final temperature to give a low acceptance (default 0.02 ), with fallback estimates based on column norms of J when sampling is unreliable. By default, spin-flip decisions use only the incoming local field h_{i}=\sum_{j}J_{ij}\,x_{j} meaning the algorithm naturally supports directed (asymmetric) couplings without requiring any symmetrization of J . VI.7.2 Maximum independent set The maximum independent set (MIS) instances are defined on a simple undirected graph G=(V,E) with binary variables n_{i}\in\{0,1\} indicating whether vertex i is included in the independent set. The hard constraint is \displaystyle n_{i}n_{j}=0\quad\text{for all }(i,j)\in E, (186) i.e., no edge may have both endpoints simultaneously occupied. The MIS density is \displaystyle\rho=\frac{1}{|V|}\sum_{i\in V}n_{i}. (187) A standard quadratic Ising formulation introduces spin variables s_{i}\in\{-1,+1\} with \displaystyle n_{i}=\frac{1+s_{i}}{2}. (188) A common penalty-based MIS Hamiltonian is \displaystyle H(s)=-\sum_{i}\mu_{i}\,n_{i}\;+\;\lambda\sum_{(i,j)\in E}n_{i}n_{j}. (189) where \lambda>\max_{i}\mu_{i} enforces the independence constraint. The \mu SA 5 algorithm is a zero-temperature single spin dynamics for the maximum independent set in which a chemical-potential-like parameter \mu_{i}=\mu , \forall i , is slowly increased from \mu=0 . The configuration starts empty ( n_{i}=0 for all vertices) on a fixed graph, and each Monte Carlo sweep visits every vertex exactly once in a random permutation order. When a vertex i is currently empty, it is occupied ( n_{i}\leftarrow 1 ) if and only if all its neighbors are empty (no constraint violation); when it is occupied, it is removed ( n_{i}\leftarrow 0 ) with probability \exp(-\mu) . After each sweep, \mu is increased by a small increment \Delta\mu , and the independent-set density \rho(\mu)=K/N (with K=\sum_{i}n_{i} ) is recorded. For replicated simulated annealing ( \mu RSA), refer to 5 . Parallel tempering in chemical potential ( \mu PT) extends \mu SA by running multiple replicas of the system at different values of the chemical potential. We consider N_{\mu} replicas, each constrained to be a valid independent set, but evolving at a distinct chemical potential \displaystyle\mu_{i}=\mu_{\max}-i\,\Delta\mu,\qquad i=0,\ldots,N_{\mu}-1. (190) Each replica independently performs standard zero-temperature Metropolis updates at its own chemical potential: if a vertex i is empty, it is occupied only if all its neighbors are empty; if it is occupied, it is removed with probability e^{-\mu_{i}} . A Monte Carlo sweep visits all vertices once in random order. Every few sweeps (five, as in 5 ), a swap move is attempted between neighboring replicas i and i+1 . The swap exchanges their entire configurations (n^{(i)},n^{(i+1)}) and is accepted with probability \displaystyle p_{\mathrm{swap}}=\min\Bigl(1,\,\exp\!\bigl[(\mu_{i}-\mu_{i+1})(-K_{i}+K_{i+1})\bigr]\Bigr), (191) where K_{i}=\sum_{v}n_{v}^{(i)} is the current independent-set size in replica i . This exchange step allows the low– \mu (high-entropy) replicas to help high– \mu replicas escape metastable configurations. For the M-layer benchmarks, we lift each MIS instance to an M-layer factor graph and then run \mu SA or \mu PT directly on the lifted graph, projecting back to the base graph only for evaluation. In the M-layer \mu SA experiment, we first generate a random regular graph G and its adjacency J_{0} , build its structured M-layer lift G_{M} via the mixing kernel Q (Gaussian-drift ring), and run zero-temperature \mu SA on G_{M} with a linear schedule \mu(t) from \mu_{\min} to \mu_{\max} over a prescribed number of sweeps. During the run we keep track of the best lifted configuration (largest number of occupied vertices). At the end, this best lifted configuration n\in\{0,1\}^{MN} is projected back to the base graph by consensus + greedy: we count, for each base vertex, how many layers occupy it, sort vertices by this score, and greedily build a valid independent set on the base graph. The resulting base density \rho is recorded as a function of the total number of sweeps; averaging over disorder instances and fitting \tau(\rho) with a power law yields the M-layer \mu SA algorithmic threshold. In the M-layer \mu PT experiment, we follow the same lifting and projection pipeline but replace \mu SA with parallel tempering in chemical potential on the lifted graph.