Connected by Construction: Learning Tractable Near-Tour Marginals for Traveling Salesman Problems

# Connected by Construction: Learning Tractable Near-Tour Marginals for Travseling Salesman Problems
Source: [https://arxiv.org/html/2607.12127](https://arxiv.org/html/2607.12127)
Xinyuan ZhangDepartment of Civil and Environmental Engineering, Rice University, Houston, TXXinwu QianDepartment of Civil and Environmental Engineering, Rice University, Houston, TXCorresponding author

\(July 13, 2026\)

###### Abstract

Learning\-based methods for the traveling salesman problem \(TSP\) are often evaluated through the tours produced after decoding or search, but the learned object itself frequently lives in a surrogate space such as heatmaps, assignments, construction policies, or search\-guidance scores\. This hides the fundamental question: what Hamiltonian structure has actually been learned before decoding? In this study, we directly answer this question by learning TSP through a structurally meaningful latent object, rather than leaving most of the Hamiltonian structure to the final decoding stage\. Based on a connected\-by\-construction rooted11\-tree Gibbs family, we propose an end\-to\-end unsupervised learning pipeline called*C2TSP*\. The pipeline learns residual edge perturbations from unbiased TSP cost through implicit differentiation\. For structural correction, a smoothed Held–Karp layer restores expected degree balance, while certificate\-guided sharpening further pushes the connected distribution toward more tour\-like structures\. Experiments show that C2TSP yields strong decoding performance while preserving interpretable structural information\. Ablations further verify that edge perturbation and certificate\-guided sharpening jointly improve both tour cost and tour\-like structure\.

## 1Introduction

Machine learning methods have been increasingly used for combinatorial optimization because they can provide fast approximate solutions while maintaining competitive empirical performance\. As a canonical combinatorial optimization problem, the traveling salesman problem \(TSP\) has received particular attention\. A feasible TSP solution must satisfy both local and global structural constraints: every node has degree two, and the selected edges must form one connected cycle\. However, many learning\-based TSP methods do not represent this global connected edge structure directly in the learned object\. Autoregressive construction models generate tours sequentially and enforce feasibility procedurally through masking and decoding rules\[[23](https://arxiv.org/html/2607.12127#bib.bib19),[5](https://arxiv.org/html/2607.12127#bib.bib20),[13](https://arxiv.org/html/2607.12127#bib.bib9),[14](https://arxiv.org/html/2607.12127#bib.bib10)\]\. Heatmap\-based methods predict edge scores and then rely on repair, sampling, local search, or tree search to obtain a valid tour\[[8](https://arxiv.org/html/2607.12127#bib.bib24),[21](https://arxiv.org/html/2607.12127#bib.bib25),[17](https://arxiv.org/html/2607.12127#bib.bib12),[22](https://arxiv.org/html/2607.12127#bib.bib29),[15](https://arxiv.org/html/2607.12127#bib.bib30)\]\. Assignment\-space relaxations, such as Sinkhorn\-based methods, provide smooth permutation\-like objects but do not directly model the edge\-adjacency structure that determines tour cost\[[16](https://arxiv.org/html/2607.12127#bib.bib11),[20](https://arxiv.org/html/2607.12127#bib.bib28),[18](https://arxiv.org/html/2607.12127#bib.bib27)\]\. Hybrid methods such as NeuroLKH use learned signals to guide strong handcrafted heuristics\[[25](https://arxiv.org/html/2607.12127#bib.bib14)\]\. Although these methods have achieved strong empirical results with affordable inference time, two limitations remain: they do not provide a tractable global distribution over connected combinatorial objects, and their final performance can be tightly coupled with downstream decoding or search, making the learned representation and the post\-processing effect difficult to separate\[[24](https://arxiv.org/html/2607.12127#bib.bib26),[7](https://arxiv.org/html/2607.12127#bib.bib34)\]\.

In contrast, we propose a connected\-by\-construction representation based on the rooted11\-tree family\. After fixing a root node, a rooted11\-tree consists of a spanning tree on the non\-root nodes together with exactly two edges incident to the root\. Therefore, every latent configuration is globally connected by construction and satisfies the root degree constraint exactly\. The remaining structural defect is the non\-root degree mismatch: a rooted11\-tree becomes a Hamiltonian cycle when every non\-root node also has degree two\. Unlike a Gibbs distribution over Hamiltonian cycles, whose partition function is intractable, the rooted11\-tree Gibbs family admits an exact factorization, which enables exact marginal computation and expected\-cost training\. This connects our method to the classical Held–Karp relaxation, where node penalties modify edge costs and minimum11\-trees provide strong TSP lower bounds\[[11](https://arxiv.org/html/2607.12127#bib.bib17),[12](https://arxiv.org/html/2607.12127#bib.bib18)\]\. Prior work has explored tree\-based or Held–Karp\-related structures for TSP from theoretical, heuristic, or learning perspectives\[[19](https://arxiv.org/html/2607.12127#bib.bib35),[10](https://arxiv.org/html/2607.12127#bib.bib36),[9](https://arxiv.org/html/2607.12127#bib.bib37)\]\. Our goal is to turn this connected structure into an end\-to\-end differentiable latent representation for learning near\-tour marginals\.

We build an end\-to\-end unsupervised learning pipeline from this connected\-by\-construction rooted11\-tree latent family, called*C2TSP*\. The model first predicts residual edge perturbations that tilt the rooted11\-tree Gibbs distribution toward low\-cost structures guided by the expected TSP cost\. To correct the remaining non\-root degree defect, we introduce a smoothed Held–Karp equilibration layer, motivated by its compatibility with the rooted11\-tree prior and the classical Held–Karp lower\-bound structure\[[11](https://arxiv.org/html/2607.12127#bib.bib17)\]\. This layer solves for node\-additive dual variables so that the expected degree of every non\-root node equals two under the dual\-modified rooted11\-tree distribution, and it is trained end\-to\-end by differentiating through the equilibrium map, following the general paradigm of implicit optimization layers\[[2](https://arxiv.org/html/2607.12127#bib.bib1),[1](https://arxiv.org/html/2607.12127#bib.bib2),[4](https://arxiv.org/html/2607.12127#bib.bib3),[6](https://arxiv.org/html/2607.12127#bib.bib4)\]\. After equilibration, the residual error is no longer a connectivity failure, but the non\-tour mass inside a connected, degree\-balanced latent family\. We control this residual defect using a certificate that upper\-bounds non\-tour mass by the total variance of the non\-root degrees\. A certificate\-guided residual refinement then reduces this non\-tour mass, followed by another re\-equilibration step\. Finally, decoding is performed by sampling from the learned edge marginals rather than by search\-based post\-processing\.

The contributions of this paper are as follows\.

- •We introduce a tractable rooted11\-tree representation for TSP that ensures global connectivity by construction while admitting exact marginal computation for expected\-cost training\.
- •We develop C2TSP, an end\-to\-end unsupervised learning pipeline in which a GNN predicts residual edge perturbations from the expected TSP cost and a smoothed Held–Karp equilibration layer restores expected degree balance\.
- •We derive a non\-tour mass certificate and use it to guide residual refinement, pushing the learned connected distribution toward more tour\-like structures\.
- •We empirically show that the proposed rooted11\-tree representation yields strong pure\-decoding performance, while several baselines benefit more from additional local search\. Further ablations show how edge perturbation and certificate\-guided sharpening shift the connected distribution toward more tour\-like and lower\-cost structures\.

## 2Methodology

### 2\.1Problem definition

#### Exact Hamiltonian Gibbs model\.

LetV=\{1,…,n\}V=\\\{1,\\ldots,n\\\}and letℰ\\mathcal\{E\}be the edge set of the complete undirected graph\. Each Hamiltonian cycleH∈ℋH\\in\\mathcal\{H\}has edge\-incidence vectorxH∈\{0,1\}\|ℰ\|x\_\{H\}\\in\\\{0,1\\\}^\{\|\\mathcal\{E\}\|\}, andD∈ℝ\|ℰ\|D\\in\\mathbb\{R\}^\{\|\\mathcal\{E\}\|\}denotes the edge\-cost vector\. A smooth exact model is the Hamiltonian Gibbs law

qDℋ​\(H\)=1Zℋ​\(D\)​exp⁡\(−1τ​⟨D,xH⟩\),H∈ℋ,\\displaystyle q\_\{D\}^\{\\mathcal\{H\}\}\(H\)=\\frac\{1\}\{Z\_\{\\mathcal\{H\}\}\(D\)\}\\exp\\\!\\left\(\-\\frac\{1\}\{\\tau\}\\langle D,x\_\{H\}\\rangle\\right\),\\qquad H\\in\\mathcal\{H\},\(1\)whereZℋ​\(D\)Z\_\{\\mathcal\{H\}\}\(D\)is the Hamiltonian partition function\. This model is intractable because evaluatingZℋ​\(D\)Z\_\{\\mathcal\{H\}\}\(D\)and differentiatinglog⁡Zℋ​\(D\)\\log Z\_\{\\mathcal\{H\}\}\(D\)require summing over exponentially many Hamiltonian cycles\.

#### Connected by construction: the rooted11\-tree surrogate\.

Since exact Hamiltonian Gibbs inference is intractable, we pursue a tractable surrogate with structural guarantee, that \(1\) preserves core tour structure, \(2\) certifies the structural gap it leaves, and \(3\) learns to reduce that gap under the equilibration guarantees developed below\. Note that a Hamiltonian cycle is always a connected spanning edge set with degree two at every node\. We preserve connectivity by using rooted11\-trees, and address the remaining degree condition via a smoothed Held–Karp \(HK\) equilibration layer\.

Fix a rootr∈Vr\\in Vand writeV¯:=V∖\{r\}\\bar\{V\}:=V\\setminus\\\{r\\\}\. Let𝒰r\\mathcal\{U\}\_\{r\}denote the family of rooted11\-trees, namely spanning trees onV¯\\bar\{V\}together with exactly two edges incident torr\. EveryU∈𝒰rU\\in\\mathcal\{U\}\_\{r\}is connected by construction, satisfiesdr​\(U\)=2d\_\{r\}\(U\)=2, and has edge\-incidence vectorxU∈\{0,1\}\|ℰ\|x\_\{U\}\\in\\\{0,1\\\}^\{\|\\mathcal\{E\}\|\}\. And it is easy to verify thatℋ⊆𝒰r\\mathcal\{H\}\\subseteq\\mathcal\{U\}\_\{r\}\. For any edge parameterη∈ℝ\|ℰ\|\\eta\\in\\mathbb\{R\}^\{\|\\mathcal\{E\}\|\}, we define the rooted11\-tree Gibbs law

qη​\(U\)=1Zr​\(η\)​exp⁡\(−1τ​⟨η,xU⟩\),U∈𝒰r,\\displaystyle q\_\{\\eta\}\(U\)=\\frac\{1\}\{Z\_\{r\}\(\\eta\)\}\\exp\\\!\\left\(\-\\frac\{1\}\{\\tau\}\\langle\\eta,x\_\{U\}\\rangle\\right\),\\qquad U\\in\\mathcal\{U\}\_\{r\},\(2\)and its edge marginal

μ​\(η\):=𝔼qη​\[xU\]\.\\displaystyle\\mu\(\\eta\):=\\mathbb\{E\}\_\{q\_\{\\eta\}\}\[x\_\{U\}\]\.\(3\)
Lemma[2\.1](https://arxiv.org/html/2607.12127#S2.Thmtheorem1)shows that the tractable marginal \([2](https://arxiv.org/html/2607.12127#S2.E2)\) is tractable with exact partition function\. The remaining task is to formalize the edge parametersη\\etathat preserve the degree\-two structure and reduce structural deficiency inside𝒰r\\mathcal\{U\}\_\{r\}\.

###### Lemma 2\.1\(Tractable rooted11\-tree marginal\)\.

The partition functionZr​\(η\)Z\_\{r\}\(\\eta\)in \([2](https://arxiv.org/html/2607.12127#S2.E2)\) factorizes into a weighted spanning\-tree partition function onV¯\\bar\{V\}and a two\-edge root\-selection normalizer\. Consequently,Zr​\(η\)Z\_\{r\}\(\\eta\), the edge marginalμ​\(η\)\\mu\(\\eta\), and all degree moments are computable exactly\.

### 2\.2Held–Karp equilibration and structural\-gap certificate

Given the11\-tree Gibbs family, the remaining Hamiltonian condition is to enforce degree two at the non\-root nodes\. Since the Gibbs law is parameterized by edge costs, the dual prices for the non\-root degree constraints need to be represented as an edge\-additive field\. Forλ∈ℝn−1\\lambda\\in\\mathbb\{R\}^\{n\-1\}indexed byV¯\\bar\{V\}, define the node\-to\-edge liftA:ℝn−1→ℝ\|ℰ\|A:\\mathbb\{R\}^\{n\-1\}\\to\\mathbb\{R\}^\{\|\\mathcal\{E\}\|\}by

\(A​λ\)i​j=\{λi\+λj,i,j∈V¯,λk,\{i,j\}=\{r,k\},k∈V¯\.\\displaystyle\(A\\lambda\)\_\{ij\}=\\begin\{cases\}\\lambda\_\{i\}\+\\lambda\_\{j\},&i,j\\in\\bar\{V\},\\\\ \\lambda\_\{k\},&\\\{i,j\\\}=\\\{r,k\\\},\\ k\\in\\bar\{V\}\.\\end\{cases\}\(4\)Then, for everyU∈𝒰rU\\in\\mathcal\{U\}\_\{r\},

⟨A​λ,xU⟩=∑i∈V¯λi​di​\(U\)\.\\displaystyle\\langle A\\lambda,x\_\{U\}\\rangle=\\sum\_\{i\\in\\bar\{V\}\}\\lambda\_\{i\}d\_\{i\}\(U\)\.\(5\)ThusA​λA\\lambdais exactly the edge\-additive representation of the non\-root degree prices\.

For a generic edge cost fieldc∈ℝ\|ℰ\|c\\in\\mathbb\{R\}^\{\|\\mathcal\{E\}\|\}, consider the entropy\-regularized degree\-correction problem for the11\-tree Gibbs family as

minp∈Δ​\(𝒰r\)\\displaystyle\\min\_\{p\\in\\Delta\(\\mathcal\{U\}\_\{r\}\)\}\\quad∑U∈𝒰rp​\(U\)​⟨c,xU⟩\+τ​∑U∈𝒰rp​\(U\)​log⁡p​\(U\)\\displaystyle\\sum\_\{U\\in\\mathcal\{U\}\_\{r\}\}p\(U\)\\langle c,x\_\{U\}\\rangle\+\\tau\\sum\_\{U\\in\\mathcal\{U\}\_\{r\}\}p\(U\)\\log p\(U\)\(6\)s\.t\.\\displaystyle\\mathrm\{s\.t\.\}\\quad∑U∈𝒰rp​\(U\)​di​\(U\)=2,i∈V¯,\\displaystyle\\sum\_\{U\\in\\mathcal\{U\}\_\{r\}\}p\(U\)d\_\{i\}\(U\)=2,\\qquad i\\in\\bar\{V\},whereΔ​\(𝒰r\)\\Delta\(\\mathcal\{U\}\_\{r\}\)denotes the probability simplex over rooted11\-trees\. This problem asks for the lowest free\-energy distribution over connected rooted11\-trees whose expectation of non\-root degree match the Hamiltonian target\. Substituting the lift identity \([5](https://arxiv.org/html/2607.12127#S2.E5)\) into the Lagrangian collapses the degree multipliers into a tilted edge costc\+A​λc\+A\\lambda, which keeps the partition function in the rooted 1\-tree family denoted byqc\+A​λq\_\{c\+A\\lambda\}, as stated below\.

###### Theorem 2\.2\(Smoothed Held–Karp equilibrium\)\.

The Lagrange dual of \([6](https://arxiv.org/html/2607.12127#S2.E6)\) is

maxλ∈ℝn−1Φτ\(c,λ\),Φτ\(c,λ\):=−τlogZr\(c\+Aλ\)−2𝟏⊤λ\.\\displaystyle\\max\_\{\\lambda\\in\\mathbb\{R\}^\{n\-1\}\}\\Phi\_\{\\tau\}\(c,\\lambda\),\\qquad\\Phi\_\{\\tau\}\(c,\\lambda\):=\-\\tau\\log Z\_\{r\}\(c\+A\\lambda\)\-2\\mathbf\{1\}^\{\\top\}\\lambda\.\(7\)Moreover,

∂Φτ​\(c,λ\)∂λi\\displaystyle\\frac\{\\partial\\Phi\_\{\\tau\}\(c,\\lambda\)\}\{\\partial\\lambda\_\{i\}\}=𝔼qc\+A​λ​\[di​\(U\)\]−2,i∈V¯,\\displaystyle=\\mathbb\{E\}\_\{q\_\{c\+A\\lambda\}\}\[d\_\{i\}\(U\)\]\-2,\\qquad i\\in\\bar\{V\},\(8\)∂2Φτ​\(c,λ\)∂λi​∂λj\\displaystyle\\frac\{\\partial^\{2\}\\Phi\_\{\\tau\}\(c,\\lambda\)\}\{\\partial\\lambda\_\{i\}\\partial\\lambda\_\{j\}\}=−1τ​Covqc\+A​λ⁡\(di​\(U\),dj​\(U\)\),i,j∈V¯\.\\displaystyle=\-\\frac\{1\}\{\\tau\}\\operatorname\{Cov\}\_\{q\_\{c\+A\\lambda\}\}\\bigl\(d\_\{i\}\(U\),d\_\{j\}\(U\)\\bigr\),\\qquad i,j\\in\\bar\{V\}\.\(9\)HenceΦτ​\(c,λ\)\\Phi\_\{\\tau\}\(c,\\lambda\)is concave inλ\\lambda, and any stationary maximizerλ⋆​\(c\)\\lambda^\{\\star\}\(c\)satisfies

𝔼qc\+A​λ⋆​\(c\)​\[di​\(U\)\]=2,i∈V¯\.\\displaystyle\\mathbb\{E\}\_\{q\_\{c\+A\\lambda^\{\\star\}\(c\)\}\}\[d\_\{i\}\(U\)\]=2,\\qquad i\\in\\bar\{V\}\.\(10\)

The proof is given in Appendix[A\.2](https://arxiv.org/html/2607.12127#A1.SS2)\. Theorem[2\.2](https://arxiv.org/html/2607.12127#S2.Thmtheorem2)shows that the degree multipliers enter each11\-tree energy through⟨A​λ,xU⟩−2​𝟏⊤​λ\\langle A\\lambda,x\_\{U\}\\rangle\-2\\mathbf\{1\}^\{\\top\}\\lambda, and that optimizing overp∈Δ​\(𝒰r\)p\\in\\Delta\(\\mathcal\{U\}\_\{r\}\)recovers the Gibbs lawqc\+A​λq\_\{c\+A\\lambda\}\. The HK layer is therefore the implicit map

c↦λ⋆​\(c\)defined by∇λΦτ​\(c,λ⋆​\(c\)\)=0\.c\\mapsto\\lambda^\{\\star\}\(c\)\\quad\\text\{defined by\}\\quad\\nabla\_\{\\lambda\}\\Phi\_\{\\tau\}\(c,\\lambda^\{\\star\}\(c\)\)=0\.This equilibration removes the degree defect of the connected surrogate\. The remaining structural gap is the residual probability mass assigned to degree\-balanced rooted11\-trees outside Hamiltonian\-cycle support\. The next result certifies this residual gap\.

#### Structural\-gap certificate\.

Let𝒩:=𝒰r∖ℋ\\mathcal\{N\}:=\\mathcal\{U\}\_\{r\}\\setminus\\mathcal\{H\}, andγ​\(q\):=q​\(𝒩\)\\gamma\(q\):=q\(\\mathcal\{N\}\)denote the set of non\-tour11trees and their mass, respectively\. HK equilibration enforces degree balance only in expectation:𝔼q​\[di​\(U\)\]=2\\mathbb\{E\}\_\{q\}\[d\_\{i\}\(U\)\]=2for alli∈V¯i\\in\\bar\{V\}\. But this does not forceqqto be supported onℋ\\mathcal\{H\}, as non\-root degree may still fluctuate across rooted11\-trees but still having mean degree 2\. The residual gap is therefore bounded by degree variance and can serve as a certificate that we can formally establish using same second\-order statistic governing the HK Hessian \([9](https://arxiv.org/html/2607.12127#S2.E9)\), as stated in the theorem below\.

###### Theorem 2\.3\(Certificate for residual non\-tour mass\)\.

Forq∈Δ​\(𝒰r\)q\\in\\Delta\(\\mathcal\{U\}\_\{r\}\)at the HK equilibrium solution, the non\-tour mass satisfies

γ​\(q\)≤12​∑i∈V¯Varq⁡\(di​\(U\)\)\.\\displaystyle\\gamma\(q\)\\leq\\frac\{1\}\{2\}\\sum\_\{i\\in\\bar\{V\}\}\\operatorname\{Var\}\_\{q\}\(d\_\{i\}\(U\)\)\.\(11\)For the HK\-equilibrated Gibbs lawq⋆=qc\+A​λ⋆​\(c\)q^\{\\star\}=q\_\{c\+A\\lambda^\{\\star\}\(c\)\}, this becomes

γ​\(q⋆\)≤12​∑i∈V¯Varq⋆⁡\(di​\(U\)\)=12​tr⁡Covq⋆⁡\(d​\(U\),d​\(U\)\)=−τ2​tr​∇λ​λ2Φτ​\(c,λ⋆​\(c\)\)\.\\displaystyle\\gamma\(q^\{\\star\}\)\\leq\\frac\{1\}\{2\}\\sum\_\{i\\in\\bar\{V\}\}\\operatorname\{Var\}\_\{q^\{\\star\}\}\(d\_\{i\}\(U\)\)=\\frac\{1\}\{2\}\\operatorname\{tr\}\\operatorname\{Cov\}\_\{q^\{\\star\}\}\(d\(U\),d\(U\)\)=\-\\frac\{\\tau\}\{2\}\\operatorname\{tr\}\\nabla\_\{\\lambda\\lambda\}^\{2\}\\Phi\_\{\\tau\}\(c,\\lambda^\{\\star\}\(c\)\)\.\(12\)

The proof is given in Appendix[A\.3](https://arxiv.org/html/2607.12127#A1.SS3)\. Thus the same covariance that defines the HK Hessian in Theorem[2\.2](https://arxiv.org/html/2607.12127#S2.Thmtheorem2)also certifies the residual structural gap left after HK equilibration\. As a consequence, the11\-tree Gibbs family not only provides tractable marginal, but also supplies the analytical structure that allows us to enforce the structure primitives to become Hamiltonian cycles\.

### 2\.3Oracle residual edge field and learned re\-equilibration

The certificate in Theorem[2\.3](https://arxiv.org/html/2607.12127#S2.Thmtheorem3)measures the structural gap left after HK equilibration\. This gap cannot be removed by another node\-price update\. To see this, following[6](https://arxiv.org/html/2607.12127#S2.E6), for anyβ∈ℝn−1\\beta\\in\\mathbb\{R\}^\{n\-1\},

Φτ​\(c\+A​β,λ\)=Φτ​\(c,λ\+β\)\+2​𝟏⊤​β\.\\Phi\_\{\\tau\}\(c\+A\\beta,\\lambda\)=\\Phi\_\{\\tau\}\(c,\\lambda\+\\beta\)\+2\\mathbf\{1\}^\{\\top\}\\beta\.\(13\)
Thus a node\-additive edge shift only reparametrizes the HK price and leaves the equilibrated Gibbs law and its edge marginals unchanged\. Hence the residual edge correction is in general not unique and can be absorbed into the HK price\. We need to select the identifiable representative by removing this node\-price component and retaining the part orthogonal to all node\-additive edge fieldsA​λA\\lambda\.

To identify the oracle form of this residual, suppose the omitted tour\-valid structure inside the rooted11\-tree family is represented at the marginal level by inequalitiesC​μ≤hC\\mu\\leq h, whereCCandhhare exponential in size in general, due to the combinatorial structure of the problem\. Now extending \([6](https://arxiv.org/html/2607.12127#S2.E6)\) with these constraints gives the entropy\-regularized oracle recovery problem

minp∈Δ​\(𝒰r\)\\displaystyle\\min\_\{p\\in\\Delta\(\\mathcal\{U\}\_\{r\}\)\}\\quad∑U∈𝒰rp​\(U\)​⟨D,xU⟩\+τ​∑U∈𝒰rp​\(U\)​log⁡p​\(U\)\\displaystyle\\sum\_\{U\\in\\mathcal\{U\}\_\{r\}\}p\(U\)\\langle D,x\_\{U\}\\rangle\+\\tau\\sum\_\{U\\in\\mathcal\{U\}\_\{r\}\}p\(U\)\\log p\(U\)\(14\)s\.t\.\\displaystyle\\mathrm\{s\.t\.\}\\quad𝔼p​\[di​\(U\)\]=2,i∈V¯,C​𝔼p​\[xU\]≤h\.\\displaystyle\\mathbb\{E\}\_\{p\}\[d\_\{i\}\(U\)\]=2,\\qquad i\\in\\bar\{V\},\\qquad C\\,\\mathbb\{E\}\_\{p\}\[x\_\{U\}\]\\leq h\.
###### Proposition 2\.4\(Oracle orthogonal residual edge field\)\.

Let\(p⋆,λ¯⋆,ν⋆\)\(p^\{\\star\},\\bar\{\\lambda\}^\{\\star\},\\nu^\{\\star\}\)satisfy the KKT conditions of \([14](https://arxiv.org/html/2607.12127#S2.E14)\), whereλ¯⋆\\bar\{\\lambda\}^\{\\star\}are the degree multipliers andν⋆≥0\\nu^\{\\star\}\\geq 0are the multipliers ofC​μ≤hC\\mu\\leq h\. Define the raw oracle edge fieldΓ~⋆:=C⊤​ν⋆\\widetilde\{\\Gamma\}^\{\\star\}:=C^\{\\top\}\\nu^\{\\star\}\. Let

Γ~⋆=Aβ⋆\+Γ⋆,Γ⋆∈Im\(A\)⟂,\\widetilde\{\\Gamma\}^\{\\star\}=A\\beta^\{\\star\}\+\\Gamma^\{\\star\},\\qquad\\Gamma^\{\\star\}\\in\\operatorname\{Im\}\(A\)^\{\\perp\},be its decomposition into a node\-additive component and an orthogonal residual component, and define the absorbed HK priceλ⋆:=λ¯⋆\+β⋆\\lambda^\{\\star\}:=\\bar\{\\lambda\}^\{\\star\}\+\\beta^\{\\star\}\. Thenλ⋆\\lambda^\{\\star\}is an HK price for the shifted cost fieldD\+Γ⋆D\+\\Gamma^\{\\star\}:λ⋆∈argmaxλΦτ​\(D\+Γ⋆,λ\)\\lambda^\{\\star\}\\in\\mathop\{\\mathrm\{argmax\}\}\_\{\\lambda\}\\Phi\_\{\\tau\}\(D\+\\Gamma^\{\\star\},\\lambda\)\.

Consequently, the oracle re\-equilibrated edge cost is

η⋆:=D\+Γ⋆\+A​λ⋆\.\\eta^\{\\star\}:=D\+\\Gamma^\{\\star\}\+A\\lambda^\{\\star\}\.

The proof is given in Appendix[A\.4](https://arxiv.org/html/2607.12127#A1.SS4)\. Proposition[2\.4](https://arxiv.org/html/2607.12127#S2.Thmtheorem4)shows that the raw dual effectC⊤​ν⋆C^\{\\top\}\\nu^\{\\star\}separates into a node\-additive componentA​β⋆A\\beta^\{\\star\}, which is absorbed into the HK price, and an orthogonal residual componentΓ⋆∈Im\(A\)⟂\\Gamma^\{\\star\}\\in\\operatorname\{Im\}\(A\)^\{\\perp\}, which is the identifiable oracle edge field\. The corresponding rooted11\-tree Gibbs lawqη⋆q\_\{\\eta^\{\\star\}\}then recovers the oracle solution\. Since the omitted constraints are intractable, we seek to learn a residual edge fieldΓθ\\Gamma\_\{\\theta\}and re\-equilibrate:

λ⋆​\(θ\)\\displaystyle\\lambda^\{\\star\}\(\\theta\):=λ⋆​\(D\+Γθ\),ηθ⋆:=D\+Γθ\+A​λ⋆​\(θ\),\\displaystyle:=\\lambda^\{\\star\}\(D\+\\Gamma\_\{\\theta\}\),\\qquad\\eta^\{\\star\}\_\{\\theta\}:=D\+\\Gamma\_\{\\theta\}\+A\\lambda^\{\\star\}\(\\theta\),\(15\)Thus in this study, we use learning to supply the residual edge geometry, while rooted11\-tree inference and HK equilibration are used to structure the trajectory in shaping and learning such residual\. The learned law is degree\-balanced after re\-equilibration, and Theorem[2\.3](https://arxiv.org/html/2607.12127#S2.Thmtheorem3)certifies its remaining structural gap\.

### 2\.4Unsupervised learning with certificate\-directed re\-equilibration

With learnable object identified as an orthogonal residual edge field, we next present the formal pipeline to train this residual that is guided by the unbiased TSP cost:

ℒTSP​\(θ\)=1M​∑m=1M⟨Dm,uθ​\(Dm\)⟩,\\mathcal\{L\}\_\{\\rm TSP\}\(\\theta\)=\\frac\{1\}\{M\}\\sum\_\{m=1\}^\{M\}\\langle D^\{m\},u\_\{\\theta\}\(D^\{m\}\)\\rangle,\(16\)whereuθ​\(D\)u\_\{\\theta\}\(D\)is the edge marginal of the11\-tree Gibbs family produced by the forward map discussed below\. This induces an unsupervised learning framework, and more importantly, thatlearns from unbiased TSP cost signalsas the structural constraints are not enforced into the loss function as penalty terms\. The forward process supplies the structure constraints, where HK recovery leads to expected degree balance, and certificate\-directed sharpening further reduce a certified upper bound on residual non\-tour mass\. The backward propagation can be computed via implicit gradient with details discussed in the Appendix[B\.2](https://arxiv.org/html/2607.12127#A2.SS2)\.

#### Canonical HK forward map\.

By Theorem[2\.2](https://arxiv.org/html/2607.12127#S2.Thmtheorem2), every edge inputccinduces HK priceλ⋆​\(c\)\\lambda^\{\\star\}\(c\), an equilibrated edge costc\+A​λ⋆​\(c\)c\+A\\lambda^\{\\star\}\(c\), and a rooted11\-tree marginalμ​\(c\+A​λ⋆​\(c\)\)\\mu\(c\+A\\lambda^\{\\star\}\(c\)\)\. As a result, for each instanceDD, the canonical forward map starts with a raw edge fieldΓ~θ​\(D\)\\widetilde\{\\Gamma\}\_\{\\theta\}\(D\), followed by removing the node\-price component as in Prop\.[2\.4](https://arxiv.org/html/2607.12127#S2.Thmtheorem4):

Γθ\(0\)​\(D\)=P⟂​Γ~θ​\(D\),P⟂:=PIm\(A\)⟂\.\\Gamma\_\{\\theta\}^\{\(0\)\}\(D\)=P\_\{\\perp\}\\widetilde\{\\Gamma\}\_\{\\theta\}\(D\),\\qquad P\_\{\\perp\}:=P\_\{\\operatorname\{Im\}\(A\)^\{\\perp\}\}\.
The projected residual then enters the HK equilibration layer\. Givencθ​\(D\)=D\+Γθ\(0\)​\(D\),c\_\{\\theta\}\(D\)=D\+\\Gamma\_\{\\theta\}^\{\(0\)\}\(D\),one can runLLHK iterations indexed byℓ=0,…,L−1\\ell=0,\\ldots,L\-1, producing

λθ,ℓ\(0\)​\(D\)⟶λθ,L\(0\)​\(D\)≈λ⋆​\(cθ\(0\)​\(D\)\)\.\\lambda\_\{\\theta,\\ell\}^\{\(0\)\}\(D\)\\longrightarrow\\lambda\_\{\\theta,L\}^\{\(0\)\}\(D\)\\approx\\lambda^\{\\star\}\(c\_\{\\theta\}^\{\(0\)\}\(D\)\)\.The terminal HK price defines the11\-tree marginals that are evaluated in the loss function[16](https://arxiv.org/html/2607.12127#S2.E16)\.

ηθ\(0\)​\(D\)=cθ\(0\)​\(D\)\+A​λθ,L\(0\)​\(D\),uθ\(0\)​\(D\)=μ​\(ηθ\(0\)​\(D\)\)\.\\eta\_\{\\theta\}^\{\(0\)\}\(D\)=c\_\{\\theta\}^\{\(0\)\}\(D\)\+A\\lambda\_\{\\theta,L\}^\{\(0\)\}\(D\),\\qquad u\_\{\\theta\}^\{\(0\)\}\(D\)=\\mu\(\\eta\_\{\\theta\}^\{\(0\)\}\(D\)\)\.

#### Bernoulli certificate and marginal\-sharpening forward map\.

The certificate in Theorem[2\.3](https://arxiv.org/html/2607.12127#S2.Thmtheorem3)bounds the residual non\-tour mass after HK equilibration, but directly differentiating the full covariance certificate would require higher\-order covariance derivatives\. In practice, one can instead use a Bernoulli upper certificate that depends only on the recovered edge marginaluuat HK equilibrium:

𝒞Ber​\(u\):=∑e∈ℰwe​ue​\(1−ue\),we:=12​∑i∈V¯Bi​e,\\mathcal\{C\}\_\{\\rm Ber\}\(u\):=\\sum\_\{e\\in\\mathcal\{E\}\}w\_\{e\}u\_\{e\}\(1\-u\_\{e\}\),\\qquad w\_\{e\}:=\\frac\{1\}\{2\}\\sum\_\{i\\in\\bar\{V\}\}B\_\{ie\},whereB​xU=dV¯​\(U\)Bx\_\{U\}=d\_\{\\bar\{V\}\}\(U\)\. Its marginal derivative by is

bBer​\(u\):=∇u𝒞Ber​\(u\)=w⊙\(1−2​u\)b\_\{\\rm Ber\}\(u\):=\\nabla\_\{u\}\\mathcal\{C\}\_\{\\rm Ber\}\(u\)=w\\odot\(1\-2u\)\(17\)
Sinceη\\etais an edge\-cost parameter, a positive step in this direction sharpens the marginal by penalizing low\-probability edges and rewarding high\-probability edges\.

###### Proposition 2\.5\(Bernoulli certificate descent\)\.

Letqηq\_\{\\eta\}be an HK\-equilibrated rooted11\-tree Gibbs law and letu=μ​\(η\)u=\\mu\(\\eta\)\. Then𝒞Ber​\(u\)\\mathcal\{C\}\_\{\\rm Ber\}\(u\)is a valid non\-tour certificateγ​\(qη\)≤𝒞Ber​\(u\)\\gamma\(q\_\{\\eta\}\)\\leq\\mathcal\{C\}\_\{\\rm Ber\}\(u\)\. Moreover, for any HK\-equilibrated edge inputcc, let

η​\(c\)=c\+A​λ⋆​\(c\),u​\(c\)=μ​\(η​\(c\)\)\.\\eta\(c\)=c\+A\\lambda^\{\\star\}\(c\),\\qquad u\(c\)=\\mu\(\\eta\(c\)\)\.Forcα=c\+α​bBer​\(u​\(c\)\)c\_\{\\alpha\}=c\+\\alpha b\_\{\\rm Ber\}\(u\(c\)\)following Eq\.[17](https://arxiv.org/html/2607.12127#S2.E17)anduα=μ​\(cα\+A​λ⋆​\(cα\)\)u\_\{\\alpha\}=\\mu\\\!\\left\(c\_\{\\alpha\}\+A\\lambda^\{\\star\}\(c\_\{\\alpha\}\)\\right\), we have, for all sufficiently smallα\>0\\alpha\>0,𝒞Ber​\(uα\)<𝒞Ber​\(u​\(c\)\)\\mathcal\{C\}\_\{\\rm Ber\}\(u\_\{\\alpha\}\)<\\mathcal\{C\}\_\{\\rm Ber\}\(u\(c\)\), whenever the re\-equilibrated sharpening direction is nonzero\.

Proposition[2\.5](https://arxiv.org/html/2607.12127#S2.Thmtheorem5)proves that the marginal derivative[17](https://arxiv.org/html/2607.12127#S2.E17)is a descent direction that minimizes the non\-tour mass\. This directly motivates a deterministic sharpening map applied after the canonical HK forward pass\. Starting from\(Γθ\(0\),uθ\(0\)\)\(\\Gamma\_\{\\theta\}^\{\(0\)\},u\_\{\\theta\}^\{\(0\)\}\), fork=0,…,K−1k=0,\\ldots,K\-1, set

Γθ\(k\+1\)​\(D\):=Γθ\(k\)​\(D\)\+αk​bBer​\(uθ\(k\)​\(D\)\)\.\\Gamma\_\{\\theta\}^\{\(k\+1\)\}\(D\):=\\Gamma\_\{\\theta\}^\{\(k\)\}\(D\)\+\\alpha\_\{k\}b\_\{\\rm Ber\}\(u\_\{\\theta\}^\{\(k\)\}\(D\)\)\.withαk\>0\\alpha\_\{k\}\>0a fixed hyperparameter for sharpening aggressiveness, and re\-equilibrate with

cθ\(k\+1\)​\(D\)=D\+Γθ\(k\+1\)​\(D\),λθ\(k\+1\)​\(D\)=λ⋆​\(cθ\(k\+1\)​\(D\)\),c\_\{\\theta\}^\{\(k\+1\)\}\(D\)=D\+\\Gamma\_\{\\theta\}^\{\(k\+1\)\}\(D\),\\qquad\\lambda\_\{\\theta\}^\{\(k\+1\)\}\(D\)=\\lambda^\{\\star\}\(c\_\{\\theta\}^\{\(k\+1\)\}\(D\)\),ηθ\(k\+1\)​\(D\)=cθ\(k\+1\)​\(D\)\+A​λθ\(k\+1\)​\(D\),uθ\(k\+1\)​\(D\)=μ​\(ηθ\(k\+1\)​\(D\)\)\.\\eta\_\{\\theta\}^\{\(k\+1\)\}\(D\)=c\_\{\\theta\}^\{\(k\+1\)\}\(D\)\+A\\lambda\_\{\\theta\}^\{\(k\+1\)\}\(D\),\\qquad u\_\{\\theta\}^\{\(k\+1\)\}\(D\)=\\mu\(\\eta\_\{\\theta\}^\{\(k\+1\)\}\(D\)\)\.which then supply to \([16](https://arxiv.org/html/2607.12127#S2.E16)\) the final marginaluθ​\(D\):=uθ\(K\)​\(D\)u\_\{\\theta\}\(D\):=u\_\{\\theta\}^\{\(K\)\}\(D\)\. WhenK=0K=0, this reduces to the canonical HK forward map\.

## 3Experiments

We evaluate on 2\-D symmetric Euclidean TSP instances, with node coordinates sampled uniformly from the unit square\. We denote the dataset withnnnodes by TSP\-nn\. This data\-generation protocol follows the standard setting used in prior neural TSP work\[[8](https://arxiv.org/html/2607.12127#bib.bib24)\], while we compute the optimal labels via Concorde\[[3](https://arxiv.org/html/2607.12127#bib.bib33)\]\. We evaluate C2TSP in two complementary regimes against representative neural and hybrid baselines, including DIFUSCO\[[22](https://arxiv.org/html/2607.12127#bib.bib29)\], DIMES\[[21](https://arxiv.org/html/2607.12127#bib.bib25)\], Fast\-T2T\[[15](https://arxiv.org/html/2607.12127#bib.bib30)\], UTSP\[[17](https://arxiv.org/html/2607.12127#bib.bib12)\], and NeuroLKH\[[25](https://arxiv.org/html/2607.12127#bib.bib14)\]\. We train all models at TSP\-100 and apply zero\-shot at every test size\. Details are given in Appendix[B](https://arxiv.org/html/2607.12127#A2)\.

#### Decoding\.

The trained network produces edge marginalsμ\\mufrom which a tour is recovered without any external solver\. We compare at six decode levels:\(L1\)greedy degree\-2 repair;\(L2\)L1 followed by 2\-opt local search for11,1010, or100100iterations;\(L3\)Gumbel perturbation ofμ\\mu, then decoded greedily and taken best\-of\-perturbation sample;\(L4\)and MAP decoder\.

#### Connecting to LKH\.

Each learning method is used as a candidate\-and\-initial\-tour oracle for LKH\-3, with five integration levels of progressively more learned signal:\(H0\)vanilla LKH\-3;\(H1\)a pre\-computed initial tour from L1;\(H2\)top\-55candidates per node, ordered byμ\\mu;\(H3\)the same candidates reordered by a0\.5:0\.50\.5\{:\}0\.5rank fusion ofμ\\muand the network\-induced reduced costCmodC\_\{\\rm mod\}; and\(H4\)the full configuration combining H1 with the H2 \(H3 for C2TSP\) candidate set\. H3 is C2TSP\-only because they require a network\-side non\-root dual that the other methods do not produce\.

![Refer to caption](https://arxiv.org/html/2607.12127v1/x1.png)![Refer to caption](https://arxiv.org/html/2607.12127v1/x2.png)![Refer to caption](https://arxiv.org/html/2607.12127v1/x3.png)

Figure 1:Empirical analysis on TSP50\.\(Left\)Training dynamics of C2TSP on TSP\-100\. “P” denotes the*perturb*branch and “P\+S” the full*perturb\-then\-sharpen*pipeline; solid lines \(“Dec\.”\) report the optimality gap of the decoded discrete tour, while dashed lines \(“Rel\.”\) report the optimality gap of the continuous relaxation\.\(Middle\)Empirical CDF of optimal\-edge coverage when the tour is obtained by directargmaxover the GNN edge scores \(no search\)\.\(Right\)Optimality gap as a function of 2\-opt iterations starting from the model’s initial tour\. Baselines construct the initial tour greedily from the heatmap; C2TSP uses MAP decoding\.
### 3\.1Main results

Table[1](https://arxiv.org/html/2607.12127#S3.T1)reports optimality gap and per\-instance wall time at every decode level\. C2TSP achieves the lowest optimality gap in 20 of the 25 \(size, decoder\-level\) cells, and is uniformly best at the heaviest local\-search budget \(L2×\\times100\)\. The advantage is largest precisely where the decoder is weakest, indicating the rooted11\-tree distribution already encodes tour\-like structure before any post\-processing\. The remaining best\-cells go to DIMES atn≥500n\\\!\\geq\\\!500under low\-search regimes, where its near\-scale\-invariant heatmap edges out our marginal\-based decoders\. Within C2TSP, the MAP decoder \(L4\) is competitive with L2×\\times1 at smallnnbut degrades atn≥500n\\\!\\geq\\\!500, indicating that the soft marginalμ\\mucarries mass beyond what the single MAP11\-tree retains\.

Table 1:Decoder results\. Optimality gap \(%\) and per\-instance wall time in seconds \(in parentheses\)\.MethodLevelTSP50TSP100TSP200TSP500TSP1000C2TSPL16\.12\(0\.14\)9\.44\(0\.15\)12\.71\(0\.20\)17\.73 \(0\.97\)21\.98 \(7\.34\)L2×1\\times 13\.73\(0\.14\)7\.03\(0\.15\)10\.32\(0\.19\)14\.97\(0\.93\)19\.77 \(7\.19\)L2×10\\times 101\.44\(0\.14\)1\.97\(0\.15\)3\.25\(0\.20\)7\.84\(0\.94\)13\.06 \(7\.19\)L2×100\\times 1001\.43\(0\.14\)1\.90\(0\.15\)2\.21\(0\.20\)2\.75\(0\.94\)3\.83\(7\.21\)L33\.09\(0\.14\)5\.11\(0\.17\)7\.97\(0\.29\)13\.54\(1\.61\)20\.35 \(10\.08\)L42\.36 \(0\.14\)4\.83 \(0\.17\)8\.74 \(0\.29\)15\.38 \(1\.63\)21\.96 \(11\.98\)DIFUSCOL117\.24 \(0\.07\)22\.60 \(0\.35\)36\.34 \(0\.96\)82\.08 \(5\.97\)141\.05 \(24\.18\)L2×1\\times 112\.93 \(0\.07\)19\.07 \(0\.35\)33\.92 \(0\.96\)80\.56 \(5\.94\)139\.96 \(24\.06\)L2×10\\times 102\.71 \(0\.07\)6\.78 \(0\.35\)22\.43 \(0\.96\)72\.08 \(5\.94\)133\.36 \(24\.06\)L2×100\\times 1002\.48 \(0\.07\)3\.73 \(0\.35\)5\.74 \(0\.98\)32\.86 \(5\.96\)94\.93 \(24\.09\)L39\.63 \(0\.07\)15\.41 \(0\.37\)36\.39 \(1\.05\)97\.00 \(6\.50\)172\.62 \(26\.40\)Fast\-T2TL117\.63 \(<\.01<\\\!\.01\)14\.31 \(0\.01\)21\.36 \(0\.02\)41\.20 \(0\.15\)74\.62 \(0\.62\)L2×1\\times 112\.55 \(<\.01<\\\!\.01\)11\.04 \(0\.01\)18\.60 \(0\.02\)39\.23 \(0\.12\)73\.20 \(0\.49\)L2×10\\times 102\.60 \(<\.01<\\\!\.01\)2\.80 \(0\.01\)9\.01 \(0\.02\)31\.84 \(0\.12\)67\.50 \(0\.49\)L2×100\\times 1002\.46 \(<\.01<\\\!\.01\)2\.44 \(0\.01\)4\.39 \(0\.03\)10\.47 \(0\.14\)42\.72 \(0\.52\)L38\.46 \(0\.01\)7\.77 \(0\.03\)24\.95 \(0\.11\)74\.42 \(0\.70\)136\.48 \(2\.96\)DIMESL113\.72 \(<\.01<\\\!\.01\)16\.08 \(<\.01<\\\!\.01\)16\.18 \(0\.01\)16\.23\(0\.04\)15\.84\(0\.16\)L2×1\\times 110\.05 \(<\.01<\\\!\.01\)13\.29 \(<\.01<\\\!\.01\)14\.28 \(<\.01<\\\!\.01\)14\.97\(0\.01\)14\.96\(0\.03\)L2×10\\times 102\.66 \(<\.01<\\\!\.01\)4\.28 \(<\.01<\\\!\.01\)6\.61 \(<\.01<\\\!\.01\)9\.67 \(0\.01\)11\.23\(0\.04\)L2×100\\times 1002\.55 \(<\.01<\\\!\.01\)3\.25 \(<\.01<\\\!\.01\)3\.54 \(0\.01\)3\.73 \(0\.02\)3\.95 \(0\.07\)L37\.87 \(0\.01\)9\.66 \(0\.02\)11\.58 \(0\.09\)15\.12 \(0\.57\)19\.38\(2\.41\)UTSPL116\.56 \(<\.01<\\\!\.01\)20\.59 \(<\.01<\\\!\.01\)24\.43 \(<\.01<\\\!\.01\)31\.90 \(0\.02\)39\.21 \(0\.10\)L2×1\\times 112\.54 \(<\.01<\\\!\.01\)17\.62 \(<\.01<\\\!\.01\)22\.45 \(<\.01<\\\!\.01\)30\.80 \(<\.01<\\\!\.01\)38\.54 \(<\.01<\\\!\.01\)L2×10\\times 104\.28 \(<\.01<\\\!\.01\)8\.40 \(<\.01<\\\!\.01\)14\.57 \(<\.01<\\\!\.01\)25\.35 \(<\.01<\\\!\.01\)34\.77 \(0\.01\)L2×100\\times 1004\.02 \(<\.01<\\\!\.01\)5\.66 \(<\.01<\\\!\.01\)7\.19 \(0\.01\)9\.98 \(0\.02\)18\.88 \(0\.04\)L360\.95 \(0\.01\)125\.21 \(0\.02\)220\.61 \(0\.08\)414\.43 \(0\.49\)633\.80 \(2\.03\)![Refer to caption](https://arxiv.org/html/2607.12127v1/x4.png)Figure 2:TSP50 ablation of edge perturbation and certificate\-guided sharpening\.Left: sampled optimality\-gap distributions for the full pipeline \(P\+S\), the variant without edge perturbation but with sharpening \(N\-P\+S\), and the variant without both perturbation and sharpening \(N\-P\)\.Right: instance\-wise gap comparisons between the full pipeline and the no\-perturbation variants\.Table[2](https://arxiv.org/html/2607.12127#S3.T2)reports gap and median LKH wall time\. At H1, every method stays within∼0\.5​‱\\sim\\\!0\.5\\,\\text\{\\textpertenthousand\}of vanilla LKH\-3 \(H0\): a learned initial tour is largely uninformative, because LKH’s local search quickly escapes any mediocre start\. The picture inverts at H2 and H4, where the heatmap drives LKH’s candidate machinery, and DIFUSCO, DIMES, and Fast\-T2T degrade by one to three orders of magnitude atn≥500n\\\!\\geq\\\!500\. C2TSP is the only learned model that survives this deeper integration, remaining within∼1​‱\\sim\\\!1\\,\\text\{\\textpertenthousand\}of vanilla LKH at every size\. Figure[1](https://arxiv.org/html/2607.12127#S3.F1)\(Middle&Right\) indicates that the common thread across both main results is that the rooted11\-tree representation preserves global connected structure by construction, so local\-sweep procedures \(whether 2\-opt or LKH\-3\) inherit a globally consistent starting point and need only repair local degree defects\.

Table 2:LKH\-integration results\. Optimality gap \(‱\) and median LKH wall time per instance \(s\)\.LevelMethodTSP100TSP200TSP500TSP1000TSP2000H0LKH\-30\.38 \(0\.11\)0\.22 \(0\.49\)0\.36 \(2\.32\)0\.39 \(7\.49\)0\.02 \(31\.23\)H1C2TSP0\.18\(0\.07\)0\.41 \(0\.29\)0\.20 \(2\.49\)0\.46 \(5\.89\)\-0\.07\(26\.73\)DIFUSCO0\.29 \(0\.07\)0\.34\(0\.28\)0\.19 \(2\.54\)0\.40 \(7\.98\)OOMFast\-T2T0\.32 \(0\.08\)0\.64 \(0\.39\)0\.23 \(1\.99\)0\.39 \(7\.24\)0\.06 \(27\.93\)DIMES0\.44 \(0\.10\)0\.73 \(0\.32\)0\.19 \(1\.84\)0\.29\(6\.39\)0\.24 \(21\.87\)UTSP0\.27 \(0\.11\)0\.61 \(0\.27\)0\.16\(2\.16\)0\.41 \(6\.46\)0\.12 \(24\.73\)H2C2TSP0\.11 \(0\.07\)0\.13\(0\.30\)0\.20\(2\.82\)0\.53\(8\.70\)0\.71\(37\.77\)DIFUSCO0\.88 \(0\.08\)4\.91 \(0\.22\)50\.14 \(1\.87\)130\.10 \(5\.57\)OOMFast\-T2T0\.02\(0\.09\)0\.76 \(0\.41\)10\.99 \(1\.99\)36\.46 \(6\.40\)80\.65 \(20\.75\)DIMES3\.24 \(0\.12\)6\.18 \(0\.29\)8\.27 \(1\.80\)9\.21 \(6\.77\)6\.56 \(24\.03\)UTSP145\.13 \(0\.09\)211\.09 \(0\.15\)217\.26 \(1\.57\)185\.35 \(6\.11\)142\.49 \(19\.77\)H3C2TSP0\.11\(0\.06\)0\.04\(0\.29\)0\.18\(2\.49\)0\.52\(9\.20\)0\.56\(37\.23\)NeuroLKH0\.63 \(0\.06\)0\.53 \(0\.21\)23\.11 \(1\.01\)38\.38 \(4\.82\)40\.66 \(27\.04\)H4C2TSP0\.11 \(0\.07\)0\.01\(0\.30\)0\.20\(2\.25\)0\.58\(8\.41\)0\.64\(36\.87\)DIFUSCO1\.01 \(0\.08\)2\.50 \(0\.24\)50\.53 \(1\.76\)135\.08 \(5\.50\)OOMFast\-T2T0\.04\(0\.09\)0\.87 \(0\.44\)9\.16 \(2\.07\)34\.85 \(6\.59\)82\.91 \(21\.11\)DIMES3\.57 \(0\.12\)4\.11 \(0\.32\)4\.33 \(1\.95\)4\.23 \(7\.66\)3\.55 \(27\.26\)UTSP65\.56 \(0\.10\)105\.35 \(0\.15\)131\.00 \(1\.57\)118\.76 \(6\.41\)102\.62 \(21\.77\)
### 3\.2Ablation and structural analysis

#### Component ablation\.

Figure[2](https://arxiv.org/html/2607.12127#S3.F2)\(Left\) shows that removing edge perturbation substantially degrades decoded performance: the average gap increases from1\.55%1\.55\\%to12\.74%12\.74\\%, with many long\-tail instances exceeding20%20\\%\. Figure[2](https://arxiv.org/html/2607.12127#S3.F2)\(Right\) further show that the full pipeline improves over the no\-perturbation variants on almost all test instances\. Table[3](https://arxiv.org/html/2607.12127#S3.T3)explains this gap from a structural perspective\. Without learned perturbation, the smoothed rooted11\-tree distribution has weak edge concentration and low recovery of optimal tour edges\. Sharpening alone improves these metrics, but remains far from the learned variants\. In contrast, perturbation\-only training already produces substantially more tour\-like marginals and much better decoded tours\. Figure[1](https://arxiv.org/html/2607.12127#S3.F1)\(Left\) shows a complementary training view\. Without sharpening, the relaxed rooted11\-tree objective converges quickly but the decoded tour quality remains limited, suggesting that low relaxed cost alone is not sufficient\. Sharpening helps translate the learned connected structure into better decoded tours\.

![Refer to caption](https://arxiv.org/html/2607.12127v1/x5.png)Figure 3:Refinement and decoding on a representative TSP50 instance\.Top: Heatmaps of the raw cost matrix, the perturbed cost matrix, and the sharpened cost matrix, with nodes reordered according to the optimal tour so that optimal\-tour edges appear near the super\- and sub\-diagonals\.Bottom: the corresponding MAP rooted11\-trees and the optimal tour\. Titles report rooted11\-tree or tour costs\.Table 3:TSP50 ablation of structural and decoding metrics\. Top2 Conc\. measures concentration of each node’s incident marginal mass on its two largest incident edges\. Edge Cov\. and Edge Cost Cov\. report unweighted and cost\-weighted recovery of Concorde\-tour edges\.MethodGap \(%\)↓\\downarrowTop2 Conc\.↑\\uparrowEdge Cov\.↑\\uparrowEdge Cost Cov\.↑\\uparrowP \+ S1\.550\.90000\.87510\.8357P2\.210\.74380\.84420\.8006N\-P19\.250\.15070\.58450\.5105N\-P \+ S12\.740\.19230\.68470\.6046
#### Structural analysis\.

Figure[3](https://arxiv.org/html/2607.12127#S3.F3)presents an example of a TSP50 instance that demonstrates the mechanisms of the proposed model across its refinement stages\. Because nodes are reordered according to the optimal tour, low\-cost mass near the super\- and sub\-diagonals indicates alignment with optimal\-tour edges, whereas isolated low\-cost regions far from the diagonal may induce structurally poor rooted11\-trees\. In the raw cost matrix, low\-cost edges are dispersed across the edge space\. Edge perturbation substantially reshapes this pattern by moving low\-cost mass toward the tour\-aligned diagonal band\. Sharpening then makes a more localized adjustment: the heatmap before and after sharpening has a similar global pattern, but ambiguous off\-diagonal low\-cost regions are further suppressed\. This is expected because sharpening acts as a fine\-tuning step rather than a full re\-learning step, which is also reflected in the MAP rooted11\-tree, where only a small number of edges are changed\. The resulting MAP rooted11\-tree is therefore shaped toward a more tour\-like structure, rather than merely assigned a lower cost\.

## 4Conclusion

This work establishes connected latent support as a design principle for learning\-based TSP\. We introduced C2TSP, a differentiable rooted11\-tree pipeline whose support is connected by construction, whose marginals are exactly computable, and whose remaining degree defects are corrected through a smoothed Held–Karp equilibration layer\. The model learns residual edge perturbations directly from the original TSP cost, while certificate\-guided sharpening reduces a provable upper bound on residual non\-tour mass\. In this way, C2TSP shifts the learned object from unconstrained edge scores to a tractable near\-tour marginal with explicit structural meaning\. Empirically, this representation yields strong pure\-decoding performance and remains robust when used as a candidate source for LKH, where several heatmap\-based baselines degrade at larger sizes\. The main limitation of our study mainly follows from the same tractable surrogate, where the rooted11\-trees relax exact Hamiltonian\-cycle support as the design choice\. C2TSP enforces connectivity in the support and restores degree balance in expectation, while the remaining degree fluctuations are controlled through equilibration and sharpening rather than eliminated exactly\. This gap opens natural directions for tighter certificate\-directed updates, richer tractable connected families, and scalable approximations to exact marginal computation\. Overall, the results show that the differentiable latent object is a central modeling choice for learning\-based TSP\. By encoding connectedness before decoding, C2TSP exposes a near\-tour marginal whose structural evolution can be trained, certified, and analyzed\.

## References

- \[1\]A\. Agrawal, B\. Amos, S\. Barratt, S\. Boyd, S\. Diamond, and J\. Z\. Kolter\(2019\)Differentiable convex optimization layers\.InAdvances in Neural Information Processing Systems,pp\. 9558–9570\.Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p3.4)\.
- \[2\]B\. Amos and J\. Z\. Kolter\(2017\)OptNet: differentiable optimization as a layer in neural networks\.InProceedings of the 34th International Conference on Machine Learning,pp\. 136–145\.Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p3.4)\.
- \[3\]D\. L\. Applegate, R\. E\. Bixby, V\. Chvátal, and W\. J\. Cook\(2011\)The traveling salesman problem: a computational study\.InThe traveling salesman problem,Cited by:[§3](https://arxiv.org/html/2607.12127#S3.p1.2)\.
- \[4\]S\. Bai, J\. Z\. Kolter, and V\. Koltun\(2019\)Deep equilibrium models\.InAdvances in Neural Information Processing Systems,pp\. 688–699\.Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p3.4)\.
- \[5\]I\. Bello, H\. Pham, Q\. V\. Le, M\. Norouzi, and S\. Bengio\(2016\)Neural combinatorial optimization with reinforcement learning\.arXiv preprint arXiv:1611\.09940\.Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p1.1)\.
- \[6\]M\. Blondel, Q\. Berthet, M\. Cuturi, R\. Frostig, S\. Hoyer, F\. Llinares\-López, F\. Pedregosa, and J\. Vert\(2022\)Efficient and modular implicit differentiation\.InAdvances in Neural Information Processing Systems,Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p3.4)\.
- \[7\]M\. Böther, O\. Kißig, M\. Taraz, S\. Cohen, K\. Seidel, and T\. Friedrich\(2022\)What’s wrong with deep learning in tree search for combinatorial optimization\.arXiv preprint arXiv:2201\.10494\.Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p1.1)\.
- \[8\]Z\. Fu, K\. Qiu, and H\. Zha\(2021\)Generalize a small pre\-trained model to arbitrarily large tsp instances\.InProceedings of the AAAI conference on artificial intelligence,Vol\.35,pp\. 7474–7482\.Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p1.1),[§3](https://arxiv.org/html/2607.12127#S3.p1.2)\.
- \[9\]K\. Genova and D\. P\. Williamson\(2017\)An experimental evaluation of the best\-of\-many christofides’ algorithm for the traveling salesman problem\.Algorithmica78\(4\),pp\. 1109–1130\.Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p2.5)\.
- \[10\]S\. O\. Gharan, A\. Saberi, and M\. Singh\(2011\)A randomized rounding approach to the traveling salesman problem\.In2011 IEEE 52nd Annual Symposium on Foundations of Computer Science,pp\. 550–559\.Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p2.5)\.
- \[11\]M\. Held and R\. M\. Karp\(1970\)The traveling\-salesman problem and minimum spanning trees\.Operations research18\(6\),pp\. 1138–1162\.Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p2.5),[§1](https://arxiv.org/html/2607.12127#S1.p3.4)\.
- \[12\]M\. Held and R\. M\. Karp\(1971\)The traveling\-salesman problem and minimum spanning trees: part ii\.Mathematical programming1\(1\),pp\. 6–25\.Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p2.5)\.
- \[13\]W\. Kool, H\. van Hoof, and M\. Welling\(2019\)Attention, learn to solve routing problems\!\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p1.1)\.
- \[14\]Y\. Kwon, J\. Choo, B\. Kim, I\. Yoon, Y\. Gwon, and S\. Min\(2020\)POMO: policy optimization with multiple optima for reinforcement learning\.InAdvances in Neural Information Processing Systems,Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p1.1)\.
- \[15\]Y\. Li, J\. Guo, R\. Wang, H\. Zha, and J\. Yan\(2024\)Fast t2t: optimization consistency speeds up diffusion\-based training\-to\-testing solving for combinatorial optimization\.Advances in Neural Information Processing Systems37,pp\. 30179–30206\.Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p1.1),[§3](https://arxiv.org/html/2607.12127#S3.p1.2)\.
- \[16\]G\. E\. Mena, D\. Belanger, S\. W\. Linderman, and J\. Snoek\(2018\)Learning latent permutations with gumbel\-sinkhorn networks\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p1.1)\.
- \[17\]Y\. Min, Y\. Bai, and C\. P\. Gomes\(2023\)Unsupervised learning for solving the travelling salesman problem\.InAdvances in Neural Information Processing Systems,Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p1.1),[§3](https://arxiv.org/html/2607.12127#S3.p1.2)\.
- \[18\]Y\. Min and C\. P\. Gomes\(2026\)Graph neural networks are heuristics\.arXiv preprint arXiv:2601\.13465\.Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p1.1)\.
- \[19\]A\. Parjadis, Q\. Cappart, B\. Dilkina, A\. Ferber, and L\. Rousseau\(2023\)Learning lagrangian multipliers for the travelling salesman problem\.arXiv preprint arXiv:2312\.14836\.Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p2.5)\.
- \[20\]M\. Paulus, D\. Choi, D\. Tarlow, A\. Krause, and C\. J\. Maddison\(2020\)Gradient estimation with stochastic softmax tricks\.Advances in Neural Information Processing Systems33,pp\. 5691–5704\.Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p1.1)\.
- \[21\]R\. Qiu, Z\. Sun, and Y\. Yang\(2022\)Dimes: a differentiable meta solver for combinatorial optimization problems\.Advances in Neural Information Processing Systems35,pp\. 25531–25546\.Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p1.1),[§3](https://arxiv.org/html/2607.12127#S3.p1.2)\.
- \[22\]Z\. Sun and Y\. Yang\(2023\)Difusco: graph\-based diffusion solvers for combinatorial optimization\.Advances in neural information processing systems36,pp\. 3706–3731\.Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p1.1),[§3](https://arxiv.org/html/2607.12127#S3.p1.2)\.
- \[23\]O\. Vinyals, M\. Fortunato, and N\. Jaitly\(2015\)Pointer networks\.InAdvances in Neural Information Processing Systems,Vol\.28\.Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p1.1)\.
- \[24\]Y\. Xia, X\. Yang, Z\. Liu, Z\. Liu, L\. Song, and J\. Bian\(2024\)Position: rethinking post\-hoc search\-based neural approaches for solving large\-scale traveling salesman problems\.arXiv preprint arXiv:2406\.03503\.Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p1.1)\.
- \[25\]L\. Xin, W\. Song, Z\. Cao, and J\. Zhang\(2021\)NeuroLKH: combining deep learning model with lin\-kernighan\-helsgaun heuristic for solving the traveling salesman problem\.InAdvances in Neural Information Processing Systems,Cited by:[§1](https://arxiv.org/html/2607.12127#S1.p1.1),[§3](https://arxiv.org/html/2607.12127#S3.p1.2)\.

## Appendix AProofs

### A\.1Proof of Lemma[2\.1](https://arxiv.org/html/2607.12127#S2.Thmtheorem1)

###### Proof\.

Letr∈Vr\\in Vbe the fixed root andV¯=V∖\{r\}\\bar\{V\}=V\\setminus\\\{r\\\}\. For non\-root edges\{i,j\}⊆V¯\\\{i,j\\\}\\subseteq\\bar\{V\}, define

wi​jη=exp⁡\(−ηi​j/τ\),w^\{\\eta\}\_\{ij\}=\\exp\\\!\\left\(\-\\eta\_\{ij\}/\\tau\\right\),and for root edges define

ai=exp⁡\(−ηr​i/τ\),i∈V¯\.a\_\{i\}=\\exp\\\!\\left\(\-\\eta\_\{ri\}/\\tau\\right\),\\qquad i\\in\\bar\{V\}\.Every rooted11\-treeU∈𝒰rU\\in\\mathcal\{U\}\_\{r\}decomposes uniquely into a spanning treeTTonV¯\\bar\{V\}and an unordered pair of distinct root neighbors\{i,j\}⊆V¯\\\{i,j\\\}\\subseteq\\bar\{V\}\. Therefore,

Zr​\(η\)\\displaystyle Z\_\{r\}\(\\eta\)=∑T∑i<jexp⁡\(−1τ​\[∑e∈Tηe\+ηr​i\+ηr​j\]\)\\displaystyle=\\sum\_\{T\}\\sum\_\{i<j\}\\exp\\\!\\left\(\-\\frac\{1\}\{\\tau\}\\Bigl\[\\sum\_\{e\\in T\}\\eta\_\{e\}\+\\eta\_\{ri\}\+\\eta\_\{rj\}\\Bigr\]\\right\)=\(∑T∏e∈Tweη\)​\(∑i<j,i,j∈V¯ai​aj\)\.\\displaystyle=\\left\(\\sum\_\{T\}\\prod\_\{e\\in T\}w^\{\\eta\}\_\{e\}\\right\)\\left\(\\sum\_\{i<j,\\;i,j\\in\\bar\{V\}\}a\_\{i\}a\_\{j\}\\right\)\.\(18\)By the matrix\-tree theorem,

∑T∏e∈Tweη=detL♯​\(W\),\\sum\_\{T\}\\prod\_\{e\\in T\}w^\{\\eta\}\_\{e\}=\\det L^\{\\sharp\}\(W\),whereL♯​\(W\)L^\{\\sharp\}\(W\)is any cofactor of the weighted Laplacian on the non\-root graph\. Hence,

Zr​\(η\)=detL♯​\(W\)​∑i<j,i,j∈V¯ai​aj\.Z\_\{r\}\(\\eta\)=\\det L^\{\\sharp\}\(W\)\\sum\_\{i<j,\\;i,j\\in\\bar\{V\}\}a\_\{i\}a\_\{j\}\.This proves the partition factorization\.

The same factorization gives exact edge marginals\. For non\-root edges, the spanning\-tree marginal identity gives

μi​j​\(η\)=wi​jη​Ri​jeff​\(W\),\{i,j\}⊆V¯,\\mu\_\{ij\}\(\\eta\)=w^\{\\eta\}\_\{ij\}R^\{\\mathrm\{eff\}\}\_\{ij\}\(W\),\\qquad\\\{i,j\\\}\\subseteq\\bar\{V\},whereRi​jeff​\(W\)R^\{\\mathrm\{eff\}\}\_\{ij\}\(W\)is the effective resistance betweeniiandjjin the weighted non\-root graph\. For root edges, the marginal is the probability thatiibelongs to the sampled unordered pair of root neighbors:

μr​i​\(η\)=ai​∑j∈V¯,j≠iaj∑k<ℓ,k,ℓ∈V¯ak​aℓ,i∈V¯\.\\mu\_\{ri\}\(\\eta\)=\\frac\{a\_\{i\}\\sum\_\{j\\in\\bar\{V\},\\;j\\neq i\}a\_\{j\}\}\{\\sum\_\{k<\\ell,\\;k,\\ell\\in\\bar\{V\}\}a\_\{k\}a\_\{\\ell\}\},\\qquad i\\in\\bar\{V\}\.The computational cost is dominated by one Laplacian factorization on the non\-root graph, so the partition function, edge marginals, and degree moments are computable exactly\. ∎

### A\.2Proof of Theorem[2\.2](https://arxiv.org/html/2607.12127#S2.Thmtheorem2)

###### Proof\.

For a fixed edge cost fieldc∈ℝ\|ℰ\|c\\in\\mathbb\{R\}^\{\|\\mathcal\{E\}\|\}and node pricesλ∈ℝn−1\\lambda\\in\\mathbb\{R\}^\{n\-1\}, define

Ec,λ​\(U\):=⟨c\+A​λ,xU⟩\.E\_\{c,\\lambda\}\(U\):=\\langle c\+A\\lambda,x\_\{U\}\\rangle\.By the node\-to\-edge lift identity,

⟨A​λ,xU⟩=∑i∈V¯λi​di​\(U\)\.\\langle A\\lambda,x\_\{U\}\\rangle=\\sum\_\{i\\in\\bar\{V\}\}\\lambda\_\{i\}d\_\{i\}\(U\)\.Therefore the Lagrangian of \([6](https://arxiv.org/html/2607.12127#S2.E6)\), up to the simplex constraintp∈Δ​\(𝒰r\)p\\in\\Delta\(\\mathcal\{U\}\_\{r\}\), is

ℒ​\(p,λ\)=∑U∈𝒰rp​\(U\)​Ec,λ​\(U\)\+τ​∑U∈𝒰rp​\(U\)​log⁡p​\(U\)−2​𝟏⊤​λ\.\\mathcal\{L\}\(p,\\lambda\)=\\sum\_\{U\\in\\mathcal\{U\}\_\{r\}\}p\(U\)E\_\{c,\\lambda\}\(U\)\+\\tau\\sum\_\{U\\in\\mathcal\{U\}\_\{r\}\}p\(U\)\\log p\(U\)\-2\\mathbf\{1\}^\{\\top\}\\lambda\.For fixedλ\\lambda, minimizing overp∈Δ​\(𝒰r\)p\\in\\Delta\(\\mathcal\{U\}\_\{r\}\)gives the Gibbs distribution

pλ​\(U\)=1Zr​\(c\+A​λ\)​exp⁡\(−1τ​Ec,λ​\(U\)\)=qc\+A​λ​\(U\),p\_\{\\lambda\}\(U\)=\\frac\{1\}\{Z\_\{r\}\(c\+A\\lambda\)\}\\exp\\\!\\left\(\-\\frac\{1\}\{\\tau\}E\_\{c,\\lambda\}\(U\)\\right\)=q\_\{c\+A\\lambda\}\(U\),and the minimized value is

−τ​log⁡Zr​\(c\+A​λ\)−2​𝟏⊤​λ\.\-\\tau\\log Z\_\{r\}\(c\+A\\lambda\)\-2\\mathbf\{1\}^\{\\top\}\\lambda\.Thus the Lagrange dual objective is

Φτ​\(c,λ\)=−τ​log⁡Zr​\(c\+A​λ\)−2​𝟏⊤​λ\.\\Phi\_\{\\tau\}\(c,\\lambda\)=\-\\tau\\log Z\_\{r\}\(c\+A\\lambda\)\-2\\mathbf\{1\}^\{\\top\}\\lambda\.
We next compute its derivatives\. Since

∂Ec,λ​\(U\)∂λi=di​\(U\),\\frac\{\\partial E\_\{c,\\lambda\}\(U\)\}\{\\partial\\lambda\_\{i\}\}=d\_\{i\}\(U\),differentiating the log\-partition function gives

∂Φτ​\(c,λ\)∂λi=𝔼qc\+A​λ​\[di​\(U\)\]−2\.\\frac\{\\partial\\Phi\_\{\\tau\}\(c,\\lambda\)\}\{\\partial\\lambda\_\{i\}\}=\\mathbb\{E\}\_\{q\_\{c\+A\\lambda\}\}\[d\_\{i\}\(U\)\]\-2\.Differentiating once more,

∂2Φτ​\(c,λ\)∂λi​∂λj=−1τ​Covqc\+A​λ⁡\(di​\(U\),dj​\(U\)\)\.\\frac\{\\partial^\{2\}\\Phi\_\{\\tau\}\(c,\\lambda\)\}\{\\partial\\lambda\_\{i\}\\partial\\lambda\_\{j\}\}=\-\\frac\{1\}\{\\tau\}\\operatorname\{Cov\}\_\{q\_\{c\+A\\lambda\}\}\\bigl\(d\_\{i\}\(U\),d\_\{j\}\(U\)\\bigr\)\.For any vectora∈ℝn−1a\\in\\mathbb\{R\}^\{n\-1\},

a⊤​∇λ​λ2Φτ​\(c,λ\)​a=−1τ​Varqc\+A​λ⁡\(∑i∈V¯ai​di​\(U\)\)≤0\.a^\{\\top\}\\nabla^\{2\}\_\{\\lambda\\lambda\}\\Phi\_\{\\tau\}\(c,\\lambda\)a=\-\\frac\{1\}\{\\tau\}\\operatorname\{Var\}\_\{q\_\{c\+A\\lambda\}\}\\left\(\\sum\_\{i\\in\\bar\{V\}\}a\_\{i\}d\_\{i\}\(U\)\\right\)\\leq 0\.HenceΦτ​\(c,λ\)\\Phi\_\{\\tau\}\(c,\\lambda\)is concave inλ\\lambda\. Therefore any stationary maximizerλ⋆​\(c\)\\lambda^\{\\star\}\(c\)satisfies

0=∂Φτ​\(c,λ⋆​\(c\)\)∂λi=𝔼qc\+A​λ⋆​\(c\)​\[di​\(U\)\]−2,i∈V¯\.0=\\frac\{\\partial\\Phi\_\{\\tau\}\(c,\\lambda^\{\\star\}\(c\)\)\}\{\\partial\\lambda\_\{i\}\}=\\mathbb\{E\}\_\{q\_\{c\+A\\lambda^\{\\star\}\(c\)\}\}\[d\_\{i\}\(U\)\]\-2,\\qquad i\\in\\bar\{V\}\.This proves the HK degree\-balance condition\. ∎

### A\.3Proof of Theorem[2\.3](https://arxiv.org/html/2607.12127#S2.Thmtheorem3)

###### Proof\.

For anyU∈𝒰rU\\in\\mathcal\{U\}\_\{r\}, define

S​\(U\):=∑i∈V¯\(di​\(U\)−2\)2\.S\(U\):=\\sum\_\{i\\in\\bar\{V\}\}\(d\_\{i\}\(U\)\-2\)^\{2\}\.Every rooted11\-tree has root degree two andnnedges, hence

∑i∈V¯di​\(U\)=2​\(n−1\),∑i∈V¯\(di​\(U\)−2\)=0\.\\sum\_\{i\\in\\bar\{V\}\}d\_\{i\}\(U\)=2\(n\-1\),\\qquad\\sum\_\{i\\in\\bar\{V\}\}\(d\_\{i\}\(U\)\-2\)=0\.IfU∉ℋU\\notin\\mathcal\{H\}, the integral deviations\{di​\(U\)−2\}i∈V¯\\\{d\_\{i\}\(U\)\-2\\\}\_\{i\\in\\bar\{V\}\}are not all zero and sum to zero\. Therefore at least one deviation is positive and at least one is negative, so

S​\(U\)=∑i∈V¯\(di​\(U\)−2\)2≥2\.S\(U\)=\\sum\_\{i\\in\\bar\{V\}\}\(d\_\{i\}\(U\)\-2\)^\{2\}\\geq 2\.Thus

𝟏​\{U∈𝒩\}≤12​S​\(U\)\.\\mathbf\{1\}\\\{U\\in\\mathcal\{N\}\\\}\\leq\\frac\{1\}\{2\}S\(U\)\.Taking expectation underqqgives

γ​\(q\)=q​\(𝒩\)≤12​∑i∈V¯𝔼q​\[\(di​\(U\)−2\)2\]\.\\gamma\(q\)=q\(\\mathcal\{N\}\)\\leq\\frac\{1\}\{2\}\\sum\_\{i\\in\\bar\{V\}\}\\mathbb\{E\}\_\{q\}\[\(d\_\{i\}\(U\)\-2\)^\{2\}\]\.Under the degree\-balance condition𝔼q​\[di​\(U\)\]=2\\mathbb\{E\}\_\{q\}\[d\_\{i\}\(U\)\]=2, this becomes

γ​\(q\)≤12​∑i∈V¯Varq⁡\(di​\(U\)\)\.\\gamma\(q\)\\leq\\frac\{1\}\{2\}\\sum\_\{i\\in\\bar\{V\}\}\\operatorname\{Var\}\_\{q\}\(d\_\{i\}\(U\)\)\.Forq⋆=qc\+A​λ⋆​\(c\)q^\{\\star\}=q\_\{c\+A\\lambda^\{\\star\}\(c\)\}, the Hessian identity follows directly from \([9](https://arxiv.org/html/2607.12127#S2.E9)\):

∇λ​λ2Φτ​\(c,λ⋆​\(c\)\)=−1τ​Covq⋆⁡\(d​\(U\),d​\(U\)\)\.\\nabla\_\{\\lambda\\lambda\}^\{2\}\\Phi\_\{\\tau\}\(c,\\lambda^\{\\star\}\(c\)\)=\-\\frac\{1\}\{\\tau\}\\operatorname\{Cov\}\_\{q^\{\\star\}\}\(d\(U\),d\(U\)\)\.Taking traces gives \([12](https://arxiv.org/html/2607.12127#S2.E12)\)\. ∎

### A\.4Proof of Proposition[2\.4](https://arxiv.org/html/2607.12127#S2.Thmtheorem4)

###### Proof\.

The Lagrangian of \([14](https://arxiv.org/html/2607.12127#S2.E14)\), up to constants independent ofpp, is

∑U∈𝒰rp​\(U\)​⟨D\+A​λ¯\+C⊤​ν,xU⟩\+τ​∑U∈𝒰rp​\(U\)​log⁡p​\(U\)\.\\sum\_\{U\\in\\mathcal\{U\}\_\{r\}\}p\(U\)\\left\\langle D\+A\\bar\{\\lambda\}\+C^\{\\top\}\\nu,x\_\{U\}\\right\\rangle\+\\tau\\sum\_\{U\\in\\mathcal\{U\}\_\{r\}\}p\(U\)\\log p\(U\)\.Stationarity inppgives

p⋆​\(U\)=qD\+A​λ¯⋆\+C⊤​ν⋆​\(U\)\.p^\{\\star\}\(U\)=q\_\{D\+A\\bar\{\\lambda\}^\{\\star\}\+C^\{\\top\}\\nu^\{\\star\}\}\(U\)\.Decompose the raw field as

C⊤ν⋆=Aβ⋆\+Γ⋆,Γ⋆∈Im\(A\)⟂,C^\{\\top\}\\nu^\{\\star\}=A\\beta^\{\\star\}\+\\Gamma^\{\\star\},\\qquad\\Gamma^\{\\star\}\\in\\operatorname\{Im\}\(A\)^\{\\perp\},and setλ⋆:=λ¯⋆\+β⋆\\lambda^\{\\star\}:=\\bar\{\\lambda\}^\{\\star\}\+\\beta^\{\\star\}\. Then

D\+A​λ¯⋆\+C⊤​ν⋆=D\+Γ⋆\+A​λ⋆,D\+A\\bar\{\\lambda\}^\{\\star\}\+C^\{\\top\}\\nu^\{\\star\}=D\+\\Gamma^\{\\star\}\+A\\lambda^\{\\star\},sop⋆=qη⋆p^\{\\star\}=q\_\{\\eta^\{\\star\}\}with

η⋆=D\+Γ⋆\+A​λ⋆\.\\eta^\{\\star\}=D\+\\Gamma^\{\\star\}\+A\\lambda^\{\\star\}\.The degree KKT conditions give

𝔼p⋆​\[di​\(U\)\]=2,i∈V¯\.\\mathbb\{E\}\_\{p^\{\\star\}\}\[d\_\{i\}\(U\)\]=2,\\qquad i\\in\\bar\{V\}\.By \([8](https://arxiv.org/html/2607.12127#S2.E8)\), this is equivalent to

∇λΦτ​\(D\+Γ⋆,λ⋆\)=0\.\\nabla\_\{\\lambda\}\\Phi\_\{\\tau\}\(D\+\\Gamma^\{\\star\},\\lambda^\{\\star\}\)=0\.Concavity ofΦτ\\Phi\_\{\\tau\}inλ\\lambdagives

λ⋆∈argmaxλΦτ​\(D\+Γ⋆,λ\)\.\\lambda^\{\\star\}\\in\\mathop\{\\mathrm\{argmax\}\}\_\{\\lambda\}\\Phi\_\{\\tau\}\(D\+\\Gamma^\{\\star\},\\lambda\)\.Finally,

μ⋆=𝔼p⋆​\[xU\]=𝔼qη⋆​\[xU\]=μ​\(η⋆\)\.\\mu^\{\\star\}=\\mathbb\{E\}\_\{p^\{\\star\}\}\[x\_\{U\}\]=\\mathbb\{E\}\_\{q\_\{\\eta^\{\\star\}\}\}\[x\_\{U\}\]=\\mu\(\\eta^\{\\star\}\)\.∎

### A\.5Proof of Proposition[2\.5](https://arxiv.org/html/2607.12127#S2.Thmtheorem5)

We use the following notation\. LetB:ℝ\|ℰ\|→ℝ\|V¯\|B:\\mathbb\{R\}^\{\|\\mathcal\{E\}\|\}\\to\\mathbb\{R\}^\{\|\\bar\{V\}\|\}be the non\-root degree operator, so that

B​xU=dV¯​\(U\),U∈𝒰r\.Bx\_\{U\}=d\_\{\\bar\{V\}\}\(U\),\\qquad U\\in\\mathcal\{U\}\_\{r\}\.With the liftAAdefined in \([4](https://arxiv.org/html/2607.12127#S2.E4)\), we haveA=B⊤A=B^\{\\top\}\. For an edge parameterη\\eta, write

u​\(η\):=μ​\(η\)=𝔼qη​\[xU\],Σx​\(η\):=Covqη⁡\(xU,xU\)\.u\(\\eta\):=\\mu\(\\eta\)=\\mathbb\{E\}\_\{q\_\{\\eta\}\}\[x\_\{U\}\],\\qquad\\Sigma\_\{x\}\(\\eta\):=\\operatorname\{Cov\}\_\{q\_\{\\eta\}\}\(x\_\{U\},x\_\{U\}\)\.When the parameter is clear, we write simplyuuandΣx\\Sigma\_\{x\}\.

Recall

𝒞Ber​\(u\)=∑e∈ℰwe​ue​\(1−ue\),we:=12​∑i∈V¯Bi​e\.\\mathcal\{C\}\_\{\\rm Ber\}\(u\)=\\sum\_\{e\\in\\mathcal\{E\}\}w\_\{e\}u\_\{e\}\(1\-u\_\{e\}\),\\qquad w\_\{e\}:=\\frac\{1\}\{2\}\\sum\_\{i\\in\\bar\{V\}\}B\_\{ie\}\.Its marginal gradient is

bBer​\(u\):=∇u𝒞Ber​\(u\)=w⊙\(1−2​u\)\.b\_\{\\rm Ber\}\(u\):=\\nabla\_\{u\}\\mathcal\{C\}\_\{\\rm Ber\}\(u\)=w\\odot\(1\-2u\)\.The projected sharpening direction is

gBer​\(u\):=P⟂​bBer​\(u\),P⟂:=PIm\(A\)⟂\.g\_\{\\rm Ber\}\(u\):=P\_\{\\perp\}b\_\{\\rm Ber\}\(u\),\\qquad P\_\{\\perp\}:=P\_\{\\operatorname\{Im\}\(A\)^\{\\perp\}\}\.
###### Lemma A\.1\(Bernoulli upper certificate\)\.

Letqηq\_\{\\eta\}be HK\-equilibrated and letu=μ​\(η\)u=\\mu\(\\eta\)\. Then

γ​\(qη\)≤𝒞Ber​\(u\)\.\\gamma\(q\_\{\\eta\}\)\\leq\\mathcal\{C\}\_\{\\rm Ber\}\(u\)\.

###### Proof\.

For eachi∈V¯i\\in\\bar\{V\},

di​\(U\)=∑e∈ℰBi​e​xU,e\.d\_\{i\}\(U\)=\\sum\_\{e\\in\\mathcal\{E\}\}B\_\{ie\}x\_\{U,e\}\.The rooted11\-tree Gibbs law factorizes into a weighted spanning\-tree law onV¯\\bar\{V\}and an independent weighted two\-edge root\-selection law\. Edge indicators in both factors are negatively associated; hence, fore≠fe\\neq f,

Covqη⁡\(xU,e,xU,f\)≤0\.\\operatorname\{Cov\}\_\{q\_\{\\eta\}\}\(x\_\{U,e\},x\_\{U,f\}\)\\leq 0\.Therefore,

Varqη⁡\(di​\(U\)\)\\displaystyle\\operatorname\{Var\}\_\{q\_\{\\eta\}\}\(d\_\{i\}\(U\)\)=Varqη⁡\(∑e∈ℰBi​e​xU,e\)\\displaystyle=\\operatorname\{Var\}\_\{q\_\{\\eta\}\}\\left\(\\sum\_\{e\\in\\mathcal\{E\}\}B\_\{ie\}x\_\{U,e\}\\right\)=∑e∈ℰBi​e2​Varqη⁡\(xU,e\)\+2​∑e<fBi​e​Bi​f​Covqη⁡\(xU,e,xU,f\)\\displaystyle=\\sum\_\{e\\in\\mathcal\{E\}\}B\_\{ie\}^\{2\}\\operatorname\{Var\}\_\{q\_\{\\eta\}\}\(x\_\{U,e\}\)\+2\\sum\_\{e<f\}B\_\{ie\}B\_\{if\}\\operatorname\{Cov\}\_\{q\_\{\\eta\}\}\(x\_\{U,e\},x\_\{U,f\}\)≤∑e∈ℰBi​e​ue​\(1−ue\),\\displaystyle\\leq\\sum\_\{e\\in\\mathcal\{E\}\}B\_\{ie\}u\_\{e\}\(1\-u\_\{e\}\),becauseBi​e∈\{0,1\}B\_\{ie\}\\in\\\{0,1\\\}\. Combining this with Theorem[2\.3](https://arxiv.org/html/2607.12127#S2.Thmtheorem3)gives

γ​\(qη\)\\displaystyle\\gamma\(q\_\{\\eta\}\)≤12​∑i∈V¯Varqη⁡\(di​\(U\)\)\\displaystyle\\leq\\frac\{1\}\{2\}\\sum\_\{i\\in\\bar\{V\}\}\\operatorname\{Var\}\_\{q\_\{\\eta\}\}\(d\_\{i\}\(U\)\)≤12​∑i∈V¯∑e∈ℰBi​e​ue​\(1−ue\)\\displaystyle\\leq\\frac\{1\}\{2\}\\sum\_\{i\\in\\bar\{V\}\}\\sum\_\{e\\in\\mathcal\{E\}\}B\_\{ie\}u\_\{e\}\(1\-u\_\{e\}\)=∑e∈ℰ\(12​∑i∈V¯Bi​e\)​ue​\(1−ue\)\\displaystyle=\\sum\_\{e\\in\\mathcal\{E\}\}\\left\(\\frac\{1\}\{2\}\\sum\_\{i\\in\\bar\{V\}\}B\_\{ie\}\\right\)u\_\{e\}\(1\-u\_\{e\}\)=𝒞Ber​\(u\)\.\\displaystyle=\\mathcal\{C\}\_\{\\rm Ber\}\(u\)\.∎

###### Lemma A\.2\(Tangent identity of HK re\-equilibration\)\.

Fix an edge inputccat which the local HK mapc↦λ⋆​\(c\)c\\mapsto\\lambda^\{\\star\}\(c\)is differentiable\. Define

η​\(c\):=c\+A​λ⋆​\(c\),Tc:=D​η​\(c\)\.\\eta\(c\):=c\+A\\lambda^\{\\star\}\(c\),\\qquad T\_\{c\}:=D\\eta\(c\)\.Then

B​Σx​Tc=0,Tc​v−v∈Im⁡\(A\)for every​v∈ℝ\|ℰ\|,B\\Sigma\_\{x\}T\_\{c\}=0,\\qquad T\_\{c\}v\-v\\in\\operatorname\{Im\}\(A\)\\quad\\text\{for every \}v\\in\\mathbb\{R\}^\{\|\\mathcal\{E\}\|\},whereΣx=Σx​\(η​\(c\)\)\\Sigma\_\{x\}=\\Sigma\_\{x\}\(\\eta\(c\)\)\.

###### Proof\.

The HK equilibrium condition is

B​μ​\(c\+A​λ⋆​\(c\)\)−2​𝟏=0\.B\\mu\(c\+A\\lambda^\{\\star\}\(c\)\)\-2\\mathbf\{1\}=0\.The rooted11\-tree Gibbs marginal satisfies

D​μ​\(η\)​\[v\]=−1τ​Σx​v\.D\\mu\(\\eta\)\[v\]=\-\\frac\{1\}\{\\tau\}\\Sigma\_\{x\}v\.Differentiating the HK equilibrium condition in directionvvgives

B​Σx​Tc​v=0\.B\\Sigma\_\{x\}T\_\{c\}v=0\.Since this holds for everyvv,

B​Σx​Tc=0\.B\\Sigma\_\{x\}T\_\{c\}=0\.
The second identity follows directly from

η​\(c\)=c\+A​λ⋆​\(c\)\.\\eta\(c\)=c\+A\\lambda^\{\\star\}\(c\)\.Indeed, differentiating in directionvvgives

Tc​v=v\+A​D​λ⋆​\(c\)​\[v\],T\_\{c\}v=v\+A\\,D\\lambda^\{\\star\}\(c\)\[v\],and hence

Tc​v−v=A​D​λ⋆​\(c\)​\[v\]∈Im⁡\(A\)\.T\_\{c\}v\-v=A\\,D\\lambda^\{\\star\}\(c\)\[v\]\\in\\operatorname\{Im\}\(A\)\.∎

###### Lemma A\.3\(Projected Bernoulli descent identity\)\.

Define the reduced certificate

𝒞¯Ber​\(c\):=𝒞Ber​\(μ​\(c\+A​λ⋆​\(c\)\)\)\.\\overline\{\\mathcal\{C\}\}\_\{\\rm Ber\}\(c\):=\\mathcal\{C\}\_\{\\rm Ber\}\\left\(\\mu\(c\+A\\lambda^\{\\star\}\(c\)\)\\right\)\.Let

u=u​\(c\):=μ​\(c\+A​λ⋆​\(c\)\),Σx=Σx​\(c\+A​λ⋆​\(c\)\)\.u=u\(c\):=\\mu\(c\+A\\lambda^\{\\star\}\(c\)\),\\qquad\\Sigma\_\{x\}=\\Sigma\_\{x\}\(c\+A\\lambda^\{\\star\}\(c\)\)\.Then

D​𝒞¯Ber​\(c\)​\[gBer​\(u\)\]=−1τ​‖Tc​gBer​\(u\)‖Σx2≤0,D\\overline\{\\mathcal\{C\}\}\_\{\\rm Ber\}\(c\)\[g\_\{\\rm Ber\}\(u\)\]=\-\\frac\{1\}\{\\tau\}\\left\\\|T\_\{c\}g\_\{\\rm Ber\}\(u\)\\right\\\|\_\{\\Sigma\_\{x\}\}^\{2\}\\leq 0,where

‖v‖Σx2:=v⊤​Σx​v\.\\\|v\\\|\_\{\\Sigma\_\{x\}\}^\{2\}:=v^\{\\top\}\\Sigma\_\{x\}v\.

###### Proof\.

Let

b=bBer​\(u\),g=gBer​\(u\)\.b=b\_\{\\rm Ber\}\(u\),\\qquad g=g\_\{\\rm Ber\}\(u\)\.For any edge\-input perturbationδ​c\\delta c,

D​𝒞¯Ber​\(c\)​\[δ​c\]\\displaystyle D\\overline\{\\mathcal\{C\}\}\_\{\\rm Ber\}\(c\)\[\\delta c\]=b⊤​D​μ​\(c\+A​λ⋆​\(c\)\)​\[Tc​δ​c\]\\displaystyle=b^\{\\top\}D\\mu\(c\+A\\lambda^\{\\star\}\(c\)\)\[T\_\{c\}\\delta c\]=−1τ​b⊤​Σx​Tc​δ​c\.\\displaystyle=\-\\frac\{1\}\{\\tau\}b^\{\\top\}\\Sigma\_\{x\}T\_\{c\}\\delta c\.Takingδ​c=g\\delta c=g, it remains to simplifyb⊤​Σx​Tc​gb^\{\\top\}\\Sigma\_\{x\}T\_\{c\}g\.

Becauseg=P⟂​bg=P\_\{\\perp\}b, the removed component lies inIm⁡\(A\)\\operatorname\{Im\}\(A\)\. Thus there existsβ\\betasuch that

UsingA=B⊤A=B^\{\\top\}and Lemma[A\.2](https://arxiv.org/html/2607.12127#A1.Thmtheorem2),

\(A​β\)⊤​Σx​Tc​g=β⊤​B​Σx​Tc​g=0\.\(A\\beta\)^\{\\top\}\\Sigma\_\{x\}T\_\{c\}g=\\beta^\{\\top\}B\\Sigma\_\{x\}T\_\{c\}g=0\.Therefore,

b⊤​Σx​Tc​g=g⊤​Σx​Tc​g\.b^\{\\top\}\\Sigma\_\{x\}T\_\{c\}g=g^\{\\top\}\\Sigma\_\{x\}T\_\{c\}g\.
By Lemma[A\.2](https://arxiv.org/html/2607.12127#A1.Thmtheorem2),

Tc​g−g∈Im⁡\(A\)\.T\_\{c\}g\-g\\in\\operatorname\{Im\}\(A\)\.Hence there existsζ\\zetasuch that

Tc​g=g\+A​ζ,equivalentlyg=Tc​g−A​ζ\.T\_\{c\}g=g\+A\\zeta,\\qquad\\text\{equivalently\}\\qquad g=T\_\{c\}g\-A\\zeta\.Again usingA=B⊤A=B^\{\\top\}andB​Σx​Tc=0B\\Sigma\_\{x\}T\_\{c\}=0,

\(A​ζ\)⊤​Σx​Tc​g=ζ⊤​B​Σx​Tc​g=0\.\(A\\zeta\)^\{\\top\}\\Sigma\_\{x\}T\_\{c\}g=\\zeta^\{\\top\}B\\Sigma\_\{x\}T\_\{c\}g=0\.Thus

g⊤​Σx​Tc​g\\displaystyle g^\{\\top\}\\Sigma\_\{x\}T\_\{c\}g=\(Tc​g−A​ζ\)⊤​Σx​Tc​g\\displaystyle=\(T\_\{c\}g\-A\\zeta\)^\{\\top\}\\Sigma\_\{x\}T\_\{c\}g=\(Tc​g\)⊤​Σx​Tc​g\\displaystyle=\(T\_\{c\}g\)^\{\\top\}\\Sigma\_\{x\}T\_\{c\}g=‖Tc​g‖Σx2\.\\displaystyle=\\\|T\_\{c\}g\\\|\_\{\\Sigma\_\{x\}\}^\{2\}\.Substituting into the directional derivative gives

D​𝒞¯Ber​\(c\)​\[g\]=−1τ​‖Tc​g‖Σx2≤0\.D\\overline\{\\mathcal\{C\}\}\_\{\\rm Ber\}\(c\)\[g\]=\-\\frac\{1\}\{\\tau\}\\\|T\_\{c\}g\\\|\_\{\\Sigma\_\{x\}\}^\{2\}\\leq 0\.∎

The above three lemmas together allow us to formally close the proof for Proposition[2\.5](https://arxiv.org/html/2607.12127#S2.Thmtheorem5), as summarized below\.

###### Proof of Proposition[2\.5](https://arxiv.org/html/2607.12127#S2.Thmtheorem5)\.

The certificate claim follows from Lemma[A\.1](https://arxiv.org/html/2607.12127#A1.Thmtheorem1)\.

For the descent claim, fix an edge inputccat which the local HK map is differentiable, and let

u​\(c\)=μ​\(c\+A​λ⋆​\(c\)\)\.u\(c\)=\\mu\(c\+A\\lambda^\{\\star\}\(c\)\)\.By Lemma[A\.3](https://arxiv.org/html/2607.12127#A1.Thmtheorem3),

D​𝒞¯Ber​\(c\)​\[gBer​\(u​\(c\)\)\]=−1τ​‖Tc​gBer​\(u​\(c\)\)‖Σx2\.D\\overline\{\\mathcal\{C\}\}\_\{\\rm Ber\}\(c\)\[g\_\{\\rm Ber\}\(u\(c\)\)\]=\-\\frac\{1\}\{\\tau\}\\left\\\|T\_\{c\}g\_\{\\rm Ber\}\(u\(c\)\)\\right\\\|\_\{\\Sigma\_\{x\}\}^\{2\}\.Therefore the derivative is strictly negative whenever the re\-equilibrated sharpening direction is nonzero, namely whenever

‖Tc​gBer​\(u​\(c\)\)‖Σx\>0\.\\left\\\|T\_\{c\}g\_\{\\rm Ber\}\(u\(c\)\)\\right\\\|\_\{\\Sigma\_\{x\}\}\>0\.By differentiability of𝒞¯Ber\\overline\{\\mathcal\{C\}\}\_\{\\rm Ber\}, there existsα¯\>0\\bar\{\\alpha\}\>0such that for every0<α<α¯0<\\alpha<\\bar\{\\alpha\},

𝒞¯Ber​\(c\+α​gBer​\(u​\(c\)\)\)<𝒞¯Ber​\(c\)\.\\overline\{\\mathcal\{C\}\}\_\{\\rm Ber\}\\left\(c\+\\alpha g\_\{\\rm Ber\}\(u\(c\)\)\\right\)<\\overline\{\\mathcal\{C\}\}\_\{\\rm Ber\}\(c\)\.With

cα=c\+α​gBer​\(u​\(c\)\),uα=μ​\(cα\+A​λ⋆​\(cα\)\),c\_\{\\alpha\}=c\+\\alpha g\_\{\\rm Ber\}\(u\(c\)\),\\qquad u\_\{\\alpha\}=\\mu\(c\_\{\\alpha\}\+A\\lambda^\{\\star\}\(c\_\{\\alpha\}\)\),this is exactly

𝒞Ber​\(uα\)<𝒞Ber​\(u​\(c\)\)\.\\mathcal\{C\}\_\{\\rm Ber\}\(u\_\{\\alpha\}\)<\\mathcal\{C\}\_\{\\rm Ber\}\(u\(c\)\)\.The proposition follows\. ∎

## Appendix BTraining details

### B\.1Experimental environment

Experiments were conducted on a workstation equipped with an AMD Ryzen Threadripper PRO 7955WX v16 CPU and 1 NVIDIA RTX 5090, running Ubuntu22\.04LTS\. The models were implemented using Python3\.10and PyTorch2\.7\.0, with additional libraries including torch\-scatter2\.1\.2and torch\-geometric2\.6\.1\. For reproducibility, a random seed of42was set for all random number generators\. The code for this experiment is available at[https://anonymous\.4open\.science/r/C2TSP\-EF65](https://anonymous.4open.science/r/C2TSP-EF65)\.

### B\.2Training procedure and implicit differentiation

We summarize the training procedure of C2TSP and the implicit differentiation used to backpropagate through the smoothed HK equilibration layer\. The node priceλ\\lambdahas a degenerate additive direction, so we resolve this degeneration by mappingλ\\lambdato a fixed nondegenerate subspace; for simplicity, we still write the resulting coordinate asλ\\lambda\.

###### Theorem B\.1\(Implicit differentiation of the HK layer\)\.

Let

F​\(θ,λ\):=𝔼qD\+Γθ\+A​λ​\[dV¯​\(U\)\]−2​𝟏\.F\(\\theta,\\lambda\):=\\mathbb\{E\}\_\{q\_\{D\+\\Gamma\_\{\\theta\}\+A\\lambda\}\}\[d\_\{\\bar\{V\}\}\(U\)\]\-2\\mathbf\{1\}\.Suppose that

F​\(θ,λ⋆​\(θ\)\)=0F\(\\theta,\\lambda^\{\\star\}\(\\theta\)\)=0and that

H​\(θ,λ⋆\):=−∂λF​\(θ,λ⋆\)H\(\\theta,\\lambda^\{\\star\}\):=\-\\partial\_\{\\lambda\}F\(\\theta,\\lambda^\{\\star\}\)is positive definite on the chosen nondegenerate subspace\. Thenλ⋆​\(θ\)\\lambda^\{\\star\}\(\\theta\)is locally unique and differentiable, and

d​λ⋆d​θ=−\(∂λF​\(θ,λ⋆\)\)−1​∂θF​\(θ,λ⋆\)\.\\frac\{d\\lambda^\{\\star\}\}\{d\\theta\}=\-\\bigl\(\\partial\_\{\\lambda\}F\(\\theta,\\lambda^\{\\star\}\)\\bigr\)^\{\-1\}\\partial\_\{\\theta\}F\(\\theta,\\lambda^\{\\star\}\)\.Hence, the backward pass through the HK layer reduces to a single linear solve in the dimension of the restrictedλ\\lambdasubspace\.

Algorithm 1Training C2TSP with residual rooted11\-tree sharpening1:Training batch

\(X,D\)\(X,D\), root

rr, GNN

fθf\_\{\\theta\}, perturbation weight

ω\\omega, temperature

τ\\tau, sharpening weight

α\\alpha, sharpening steps

KK, learning rate

η\\eta
2:Updated parameters

θ\\theta
3:

Cbase←DC^\{\\mathrm\{base\}\}\\leftarrow D
4:

L←fθ​\(X,D\)L\\leftarrow f\_\{\\theta\}\(X,D\)⊳\\trianglerightraw residual edge field

5:

L~←Π⟂​\(L\)\\widetilde\{L\}\\leftarrow\\Pi\_\{\\perp\}\(L\)⊳\\trianglerightremove node\-additive component

6:

C\(0\)←Cbase−ω​L~C^\{\(0\)\}\\leftarrow C^\{\\mathrm\{base\}\}\-\\omega\\widetilde\{L\}
7:

λ\(0\)←λ⋆​\(C\(0\)\)\\lambda^\{\(0\)\}\\leftarrow\\lambda^\{\\star\}\(C^\{\(0\)\}\)⊳\\trianglerightHK equilibration

8:

η\(0\)←C\(0\)\+A​λ\(0\)\\eta^\{\(0\)\}\\leftarrow C^\{\(0\)\}\+A\\lambda^\{\(0\)\}
9:

μ\(0\)←μ​\(η\(0\)\)\\mu^\{\(0\)\}\\leftarrow\\mu\(\\eta^\{\(0\)\}\)
10:for

k=0,…,K−1k=0,\\ldots,K\-1do

11:

g\(k\)←Π⟂​\(1−2​μ\(k\)\)g^\{\(k\)\}\\leftarrow\\Pi\_\{\\perp\}\(1\-2\\mu^\{\(k\)\}\)⊳\\trianglerightcertificate\-guided sharpening

12:

C\(k\+1\)←C\(k\)\+α​g\(k\)C^\{\(k\+1\)\}\\leftarrow C^\{\(k\)\}\+\\alpha g^\{\(k\)\}
13:

λ\(k\+1\)←λ⋆​\(C\(k\+1\)\)\\lambda^\{\(k\+1\)\}\\leftarrow\\lambda^\{\\star\}\(C^\{\(k\+1\)\}\)⊳\\trianglerightre\-equilibration

14:

η\(k\+1\)←C\(k\+1\)\+A​λ\(k\+1\)\\eta^\{\(k\+1\)\}\\leftarrow C^\{\(k\+1\)\}\+A\\lambda^\{\(k\+1\)\}
15:

μ\(k\+1\)←μ​\(η\(k\+1\)\)\\mu^\{\(k\+1\)\}\\leftarrow\\mu\(\\eta^\{\(k\+1\)\}\)
16:endfor

17:

ℒcost​\(θ\)←⟨D,μ\(K\)⟩\\mathcal\{L\}\_\{\\mathrm\{cost\}\}\(\\theta\)\\leftarrow\\langle D,\\mu^\{\(K\)\}\\rangle
18:

θ←θ−η​∇θℒcost​\(θ\)\\theta\\leftarrow\\theta\-\\eta\\nabla\_\{\\theta\}\\mathcal\{L\}\_\{\\mathrm\{cost\}\}\(\\theta\)
19:return

θ\\theta

### B\.3Structured MAP decoding

The structured MAP decoder converts the final rooted11\-tree distribution into feasible tours for evaluation\. Given the final sharpened costC\(T\)C^\{\(T\)\}and marginalμ\(T\)\\mu^\{\(T\)\}, the decoder repeatedly extracts MAP rooted11\-trees, repairs them into Hamiltonian tours, and returns the candidate with the lowest true metric cost\. Unlike local\-search\-based post\-processing, this decoder directly uses the connected rooted11\-tree structure and only applies a repair step to enforce the global connectivity constraint\.

For each decode drawk=0,…,K−1k=0,\\ldots,K\-1, we form a perturbed cost

C\(k\)=C\(T\)\+σ​Δ​C\(k\),C^\{\(k\)\}=C^\{\(T\)\}\+\\sigma\\Delta C^\{\(k\)\},whereΔ​C\(0\)=0\\Delta C^\{\(0\)\}=0gives the deterministic candidate and the remaining draws use small graph\-structured perturbations\. The perturbation is used only to diversify the MAP rooted11\-tree candidates\. GivenC\(k\)C^\{\(k\)\}, the decoder computes

𝒯\(k\)=MAPRootedOneTree​\(C\(k\),r\),\\mathcal\{T\}^\{\(k\)\}=\\mathrm\{MAPRootedOneTree\}\(C^\{\(k\)\},r\),which consists of a minimum spanning tree on the non\-root nodes together with the two cheapest root edges\. Since𝒯\(k\)\\mathcal\{T\}^\{\(k\)\}is connected but not necessarily a tour, it is repaired into a feasible Hamiltonian cycle:

π\(k\)=Repair​\(𝒯\(k\),μ\(T\),C\(k\),D\)\.\\pi^\{\(k\)\}=\\mathrm\{Repair\}\(\\mathcal\{T\}^\{\(k\)\},\\mu^\{\(T\)\},C^\{\(k\)\},D\)\.The repair step use the learned marginals, the perturbed cost, and the true metric distance matrix\. Each candidate is evaluated by its true metric tour cost, and the decoder returns the best one:

π^=argminπ\(k\)TourCost​\(π\(k\),D\)\.\\widehat\{\\pi\}=\\mathop\{\\mathrm\{argmin\}\}\_\{\\pi^\{\(k\)\}\}\\mathrm\{TourCost\}\(\\pi^\{\(k\)\},D\)\.
Algorithm 2Structured MAP decoding1:Final cost

C\(T\)C^\{\(T\)\}, final marginal

μ\(T\)\\mu^\{\(T\)\}, distance matrix

DD, root

rr, decode draws

KK, perturbation scale

σ\\sigma
2:Decoded tour

π^\\widehat\{\\pi\}
3:for

k=0,…,K−1k=0,\\ldots,K\-1do

4:Generate a small perturbation

Δ​C\(k\)\\Delta C^\{\(k\)\}with

Δ​C\(0\)=0\\Delta C^\{\(0\)\}=0
5:

C\(k\)←C\(T\)\+σ​Δ​C\(k\)C^\{\(k\)\}\\leftarrow C^\{\(T\)\}\+\\sigma\\Delta C^\{\(k\)\}
6:

𝒯\(k\)←MAPRootedOneTree​\(C\(k\),r\)\\mathcal\{T\}^\{\(k\)\}\\leftarrow\\mathrm\{MAPRootedOneTree\}\(C^\{\(k\)\},r\)
7:

π\(k\)←Repair​\(𝒯\(k\),μ\(T\),C\(k\),D\)\\pi^\{\(k\)\}\\leftarrow\\mathrm\{Repair\}\(\\mathcal\{T\}^\{\(k\)\},\\mu^\{\(T\)\},C^\{\(k\)\},D\)
8:

c\(k\)←TourCost​\(π\(k\),D\)c^\{\(k\)\}\\leftarrow\\mathrm\{TourCost\}\(\\pi^\{\(k\)\},D\)
9:endfor

10:

π^←argminπ\(k\)c\(k\)\\widehat\{\\pi\}\\leftarrow\\mathop\{\\mathrm\{argmin\}\}\_\{\\pi^\{\(k\)\}\}c^\{\(k\)\}
11:return

π^\\widehat\{\\pi\}