Hybrid-Balance GFlowNet for Solving Vehicle Routing Problems
Authors: Ni Zhang
Zhiguang Cao
Venue: NeurIPS 2025 spotlight ()
Keywords: GFlowNet
Vehicle Routing Problem
Primary area: optimization
TL;DR: we introduce the Hybrid-Balance GFlowNet framework which uniquely integrates TB and DB in a principled and adaptive manner to acheive Local-Global Optimization.

Abstract: Existing GFlowNet-based methods for vehicle routing problems (VRPs) typically employ Trajectory Balance (TB) to achieve global optimization but often neglect important aspects of local optimization. While Detailed Balance (DB) addresses local optimization more effectively, it alone falls short in solving VRPs, which inherently require holistic trajectory optimization. To address these limitations, we introduce the Hybrid-Balance GFlowNet (HBG) framework, which uniquely integrates TB and DB in a principled and adaptive manner by aligning their intrinsically complementary strengths. Additionally, we propose a specialized inference strategy for depot-centric scenarios like the Capacitated Vehicle Routing Problem (CVRP), leveraging the depot node's greater flexibility in selecting successors. Despite this specialization, HBG maintains broad applicability, extending effectively to problems without explicit depots, such as the Traveling Salesman Problem (TSP). We evaluate HBG by integrating it into two established GFlowNet-based solvers, i.e., AGFN and GFACS, and demonstrate consistent and significant improvements across both CVRP and TSP, underscoring the enhanced solution quality and generalization afforded by our approach.

Hybrid-Balance GFlowNet for Solving Vehicle Routing Problems
Ni Zhang, Zhiguang Cao"
School of Computing and Information Systems, Singapore Management University, Singapore zhang. 2025@phdcs smu. smu.edu. sg, zgcao@smu. edu.
Abstract
Existing GFlowNeet-bsedd methods for vehicle routing problems (VRPs) typically employ Trajectory Balance (TB) to achieve global optimization but often neglect important aspects of local optimization. While Detailed Balance (DB) addresses local optimization more effectively, it alone falls short solving VRPs, which inherently require holistic trajectory optimization. To address these limitations, we introduce the Hybrid-Balance GFlowNet (HBG) framework, which uniquely integrates TB and DB in principled and adaptive manner by aligning their intrin- sically complementary strengths. Additionally, we propose specialized inference strategy for depot-centric scenarios like the Capacitated Vehicle Routing Problem (CVRP), leveraging the depot node's greater flexibility in selecting successors. Despite this specialization, HBG maintains broad applicability, extending effec- tively to problems without explicit depots, such as the Traveling Salesman Problem (TSP). We evaluate HBG by integrating it into two established GFlow based solvers, i.e., AGFN and GFACS, and demonstrate consistent and significant im- provements across both CVRP and TSP, underscoring the enhanced solution quality and generalization afforded by our approach.
Introduction
Vehicle Routing Problems (VRPs) are fundamental to real-world operations, including e-commerce logistics [54 12
39,. urban delivery [56] 7 21), supply chain management [[ [5 8) and ride- Efficient VRP solutions directly affect cost reduction, service quality, and overall performance in transportation and supply chain networks. Over the past decades, nu- merous heuristic and meta-heuristic algorithms, such as the Lin Kerninengghan- Heemighhn--Helggunn Helsgaun algorithm 119, ant colony optimization (ACO) B hybrid genetic search [46), tabu search [2. and simulated annealing (36), have been developed to address the combinatorial complexity of VRPs. However, these approaches often depend on handcrafted rules and problem-speeific heuristics, which limit their adaptability and scalability across diverse VRP instances. More recently, reinforcement learning and deep learning methods have emerged as promising alternatives [38] 5 52, 20). Models such as
sharing systems 1 30
POMO 25), NeuOpt [31], and DEITSP 47 show potential in reducing dependence on handcrafted components. Yet. these methods still struggle to consistently achieve desirable performance, often becoming trapped in local optima due to the limited exploration capacity.
To improve exploration, recent work has explored the use of Generative Flow Network (GFlownet) [4, which generate diverse and high-quality solutions through probabilistic, generative process. Unlike traditional learning based approaches that focus on optimizing a single a few trajectories, GFlowNet aims to learn a distribution over the solution space, making them well-suited for combinatorial problems like VRPs. However, current GFlowNet-based methods for VRPs such as GFACS (2) and AGFN (53, rely exclusively on global optimization during training. Particularly, they both adopt the
"coreepponiin author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Trajectory Balance (TB) objective [3]]. which effectively aligns with global metrics like minimizing total travel distance. However, this exclusive focus on global optimization can lead to the neglect of important local optimization signals. For instance, these methods may overlook reward dependencies between a current state and its successor, due to the lack of localized training objectives. As result, they often struggle to capture fine-grained local structures in the solution space, limiting their ability to generate high-quality routes. On the other hand, Detailed Balance (DB) [4] offers a mechanism better suited for local optimization. Nevertheless, using DB alone is equally inadequate, VRPs fundamentally require global perspective to achieve optimal solutions. These limitations highlight the need for broader approach that balances both local and global optimization. We propose that Hybrid- SybrridBBllance principle, combining TB and DB in a unified and extensible manner, can significantly methods for VRPs.
enhance GFlowNet-
Guided by this Hybrid-Balance principle, we introduce the Hybrid- Mariid-alance GFlowNet (HBG) framework for solving VRPs. First, HBG unifies DB, which promotes local optimization, with TB, which captures global optimization. To fully exploit their complementary strengths, we formulate a VRP-specific version of DB that effectively facilitates local optimization through localized objectives. We also design an adaptive integration mechanism that combines DB and TB in a way that respects their theoretical underpinnings, such as forward and backward transition probability, while leveraging their complementary benefits. Second, motivated by the insight that depot nodes in depot-centric VRPs, such as the Capacitated Vehicle Routing Problem (CVRP), have greater flexibility in selecting successor nodes, we propose a sepot-guided inference strategy inspired by the Hybrid- -alanBee principle. Notably, even in depot-free scenarios like the Traveling Salesman Problem (TSP), our framework remains effective, as the Hybrid-Balance demonstrate the broad applicability of HBG, we integrate it into two existing GFlloWettbbssee solvers, ie., AGFN and GFACS, and observe consistent improvements in routing performance across both CVRP and TSP benchmarks. In summary, our main contributions are outlined as follows:
Balance formulation is inherently general. Third, to
We propose the Hlyrid-Balance GFlowNet (HBG) framework for solving VRPs, which, for the first time, introduces and formalizes the concept of DB within the VRP context. Meanwhile, it unifies the principles of TB and DB through principled and coherent integration to process both local and global optimizations.
We design depot-guided inference strategy to efficiently generate and explore high-quality trajectories, specifically tailored for problems involving a designated depot like the CVRP.
We incorporate the HBG framework into existing GFlowNet-barn methods for solving VRPs, i.e., AGFN and GFACS, and evaluate it on both synthetic and real-world datasets. The results demonstrate that our method significantly improves the performance of GFlowNet- based solvers for CVRP and TSP.
2 Related Works
2.1 Learning-Basse Based Solvers for Vehicle Routing Problems
Learning-basee approaches for VRPs can generally be divided into two categories: construction- based and improvement-basee methods. Construction-basee solvers generate complete solution trajectories in an end-to-end manner. A seminal example is the Attention Model (AM) (23.. which first applied Transformer architecture to solve VRPs. Building on AM. Policy Optimization with Multiple Optima (POMO) extends this approach by leveraging multiple optimal policies during training and inference improve both solution quality and robustness. This line of work has since inspired series of end-to-end construction-basee methods [43 improve performance. Improvement based methods, on the other hand, enhance initial solutions through iterative refinements. These methods often integrate neural networks into classical heuristic frameworks. Notable examples include NeuroLKH [4], DeepACO [51, and NeuOpt (3I] which demonstrate strong performance through Sarning-augmmntin the generality of our proposed framework, we apply it to enhance both construction-bast solver (AGFN) and an improvement-bass solver (GFACS).
26
13
47 14] that further
optimization strategies. To showcase

---

2.2 GFlowNet for Combinatorial Optimization Problems
GFlowNet has been applied across wide range of structured generation and Decision-makinn tasks. In molecular and drug discovery [57] 34 24 41 16, 40], they are used to sample diverse, high-reward
molecules from complex solution spaces. causal structure learning [28 9]. GFlowNet facilitates
exploration over multiple plausible directed acyelic graphs (DAGs), while in Bayesian inference
they serve as alternative samplers discrete posteriors. Additional applications include symbolic reasoning 45 27] robotics planning [29] 33 and solving maximum independent set (MIS)
10 42
[53] where modeling solution diversity is essential. Recently, GFlowNet has also been applied to
VRPs [55 [2]. including TSP and CVRP. In this context, learning distribution over feasible routes offers a flexible and effective alternative to deterministic solvers. Two representative models are AGEN and GFACS. AGFN incorporates adversarial training improve trajectory construction in an end-to-end fashion, making it the first to apply GFlowNet to VRPs directly. In contrast, GFACS integrates GelowNet with ant colony optimization, marking the first attempt to augment heuristic search with GFlowNet-be learning. this paper, we further enhance both AGFN and GFACS for solving VRPs using our proposed SyyrridBBllane GFlowNet framework.
3 Hybrid-Balance GFlowNet
Trajectory geneaation
TB T'aalninng
GEACS
GRACS Energy Reshaging
TB Loss
Cummnnt
AGEN
Trojectory
AGEN Genemboo
TH Loss
HBG
Disotminator
LosS
Maemmon
Dettiaaion
Prosaclitty
Noda Embedding
I Inner Layer
DB Loss
RCS
PboS,..)
DB Tralning
Neat State
Figure 1: The Overall Framework of Our Hybrid-Balance GFlowNet for Solving VRPs.
As illustrated in Fig I the Hybrid-Balance GFlowNet (HBG) begins with trajectory generation using either AGFN or GFACS, during which state transition information is recorded at each step. The generated next state then treated as the current state the following step, and this process repeats until complete trajectory is constructed. The blue region in Fig corresponds to the original components from AGEN and GFACS, responsible for the processing of the complete trajectory and the computation of the TB loss, which captures global optimization signals. However, relying solely on the TB loss can cause the model overlook important relationships between individual states. To bridge this gap, our proposed HBG introduces additional components, highlighted in purple, where the loss is computed each individual state transition enhance local optimization. The final training objective is combination of two loss, which together guide the optimization of the model.
To better illustrate the motivation for introducing DB, consider long vehicle routing trajectory that is incrementally constructed as A + B C D + E + + U + V W + X + - Z. Assume this complete route yields high total (bad performance), primarily due to suboptimal decisions made in the early stages, such as traversing a high-cost edge from node C to node D. In contrast, the latter portion of the tour (e.g.. from node Z) may follow more cost-effective and well- structurdd pattern. Under Trajectory Balance (TB), the final reward is determined by the overall trajectory cost, and proportionally assigned to transitions. Consequently, even high-quality local transitions, such as W - X Y, may receive weak or misleading training signals simply because they are embedded in a globally suboptimal trajectory. This would hinder the model's ability to learn and reinforce desirable local patterns. On the other hand, Detailed Balance (DB) operates at

---

step-wise granularity, evaluating the expected outcomes of individual transitions. For instance, at node W, DB can assess whether transitioning to X leads better outcomes compared to alternative choices like 7,, regardless of earlier suboptimal steps. This localized and reward-sensitiv feedback enables the model to more accurately learn local quality from global performance, and promotes stronger learning signals for valuable decisions even within imperfect trajectories.
This example illustrates core limitation of Trajectory Balance (TB) in long-horizon combinatorial tasks like VRP: when the overall trajectory is suboptimal, TB lacks the ability to identify and preserve well-structured local segments within it. As a result, valuable local patterns may be overlooked or penalized. By incorporating Detailed Balance (DB) into the training objective, we address this limitation by providing fine-grat grained, step-level singal that helps isolate and reinforce high-quality local decisions, even when the global trajectory does not show good performance.
3.1 Modeling Basics
Problem Definition. For a CVRP instance, G denotes the input graph, which includes the coordinates and demands of customers, as well as the depot location. Formally, the instance is represented as complete graph G = (V,24 22) where V {vo, vi.... : U, } denotes the set of nodes, with as the depot and the remaining nodes representing customers, and 2/ is the set of edges. Each customer node 2 (i 2 1) is associated with a demand d, and a location in Euclidean space. Each edge (e,, 2ÿ) E U has an associated cost Ciy. typically defined as the Euclidean distance between U; and vy. The goal of CVRP is to determine set of vehicle routes that start and end at the depot, such that each customer is visited exactly once, the total demand on each route does not exceed the vehicle's 's capacity, and the total routing cost is minimized.
State s: In a trajectory set T [TI, ......; ]. the state s² denotes the sequence of nodes visited in trajectory т₁. At decision step in T., the state is defined as st {aj æf æz .'....., æ1) where zj is the most recently visited node, and zi represents the depot which serves as both the starting and ending point of the route.
Action a: An action of transitions the system from state s/ to 41 Given s {a .i..... #f}, the action selects the next node r/41 from the set of unvisited nodes, adhering to feasibility constraints such as vehicle capacity. Once all customers are visited, the route terminates in final state, forming a complete trajectory T; = "'",,,".....
Reward R: The reward R((T;) is determined by the quality of the generated trajectory т. We define two types of rewards: I((TT)) and R(s)). The former, R(T:), evaluates the entire trajectory, while the latter, R(s)), reflects local reward signals at individual state transitions. These are defined as: R(TT) = k= d(rk. .1++1) R(s{)= = m/)) where d( af 1 denotes the Euclidean distance between consecutive nodes.
Graph Neural Network (GNN). We integrate a GNN module 48 into the GelowNet framework to more effectively capture the complex relational structures inherent in VRP instances. The detailed architecture and formulation are provided in Appendix A. Following the designs of AGFN and GFACS, we sparsify the fully connected graph into k --eeerrst-eeihhbor graph G to improve scalabil- ity and reduce computational cost. The graph G is embedded into high-dimensional feature space, encoding node coordinates and edge distances as node and edge features, respectively. The GNN, parameterized by 0, processes these features through multiple layers to produce rich representations. The resulting edge embeddings are passed through a multi-layer perceptron (MLP) to generate edge probability distribution n)(r", 0) for decision making by GFlowNet, while the node embeddings Q {प) .2.............................. are retained for computing state flows
3.2
Hybrid-Balanee GFlowNet
3.2.1 Global Optimization via TB
In VRPs, the objective is to determine the shortest route while satisfying various operational con- straints, which necessitates evaluating solutions from a global perspective. Both AGFN and GFACS adopt the Trajectory Balance (TB) objective to address this requirement, as it enables the GFlowNet to be trained over entire trajectories, naturally aligning with global optimization goals.

---

As illustrated in Fig. AGFN generates an edge probability distribution n/9", O gonerator) using GFlowNet, which is then used sample the next node the route. discriminator, trained with false labels from GFlow Net-generatee trajectories and true labels from near-optimal trajectories, evaluates the quality of sampled trajectory set T (TI, T2,.... Th. It assigns a quality score to each trajectory, which is then combined with the raw trajectory length R(T) to compute the final AGFN reward ((()). These rewards R(T), along with the source flow Z Z yenerrator,, forward probability (T; O ge and backward probability (B(T) obtained from the GFlowNet, are used to compute the AGFN TB loss PAG
defined as:
h Σ k=
Z gonerator) PF (TK: O generator)
2
AG
(T: generator) TB
log
R(Tx) PB(TK)
For GFACS, the GFlowNet is used to generate a heuristic matrix 7 , 0), which is subsequently transformed into a pheromone map to guide the ant colony optimization (ACO) in trajectory con- struction. Once the trajectories are generated, a local search is applied for refinement, followed by an energy reshaping step. The TB loss for GFACS, denoted 'TB then computed similar form to AGFN, as both approaches adopt the TB loss formulation to optimize their models.
3.2.2 Local-Global Optimization through Hybrid-Baland -Balance
While global optimization is essential for solving VRPs, local optimization is also important as helps the model to capture fine-grained patterns, such transitions between neighboring nodes. However, local information alone is insufficient for modeling global objective and constraints like total cost and capacity. To address this, we propose unify both global and local objectives within Hybrid-Balance GFlowNet framework. Specifically, we integrate the DB mechanism into the original TB framework of the GFACS and AGFN models to further enhance the modeling of local transitions, particularly the relationship between the current state st and the next state 8/+1-
As shown in Fig. 1 the model records relevant information at each step, including the current state's reward R(s{) and flow (s); 0), the next state's ' reward R(s ) and flow F (5 1i 0), as well as the forward and backward transition probability (s 1s); 0) and Po(s)lo/41): Once a trajectory is completed, apply forward-looking technique 37 to compute the DB loss LDS between two successive states as:
( :1)0)) (10g
(5 1s: 0) F(s 0) exp(E(()+ Po(s) s1 F(s exp(E(st))
(2)
Here, Pr(si-1 |s;: 0) denotes the forward transition probability derived from the edge probability distribution 7("",00 0) in AGFN or the pheromone map in GFACS. The relationship between the trajectory-level forward probability PF(n; 0) used in TB loss and the step-wise forward probability Py Py(44111e (8;; 0) used in DB loss given by:
PF (T; 0) = II P
(3)
To ensure consistency with the trajectory-level backward probability PB(T)) used in TB loss, we design the step-wise backward probability Po(s((si41) reflect the structure of sub-trajectories within Specifically, we assume that each complete trajectory т; consists of a multi-node sub- trajectories and j single-node sub-trajectories, and parameter P5 accordingly determined by the varied transition structures.
Definition 1 (Trajectory Composition and Ordering Count), We define A, as the set of a multi- node trajectories, and Jy as the set of j single-node trajectories. Together, these sequences are combined to form a complete trajectory T₁. Let B(A,, denote the number of distinct orderings of sub-trajectories in A, and J, that result in the same complete trajectory T₁.
We next present the following statement, which describes the recurrence relation for B(A,. JT).
5

---

Statement 1 (Trajectory Orders' Count Recurrence), The number of distinct trajectories composed of mulli-node trajectories and j single-node trajectories arranged in different orders, denoted by B(A Jz), satisfies the following recurrence relation:
BBAa, 2a B(Aa-1. + B(Ass JJ-1).
This recurrence arises from the backward destruction of CVRP trajectories, where we consider how (Aa: Jz) reached its predecessors. Suppose the current state corresponds to B(A., In), where there are a remaining multi-node trajectories and j remaining single-node trajectories to be disconnected. There are two possible types of backward transitions from this state to reach its predecessor 3() or B(Aa:
(1) Multi-node trajectory: If multi-node trajectory is selected for backward destruction from the depot, either of its two nodes can serve as the immediate predecessor to the depot. Therefore, each of the multi-node trajectories contributes two valid backward transitions, resulting in a total contribution of 2a B(Au-11 J,), where the recursion proceeds with remaining multi-node trajectories and unchanged single-node trajectories.
(2) Single-node trajectory: If a single-node trajectory is chosen, it contains only one node, which uniquely determines the depot's predecessor. Thus, each of the j single-node trajectories contributes one backward transition, resulting JBB(A.. where the recursion continues with a multi-node trajectories and j hingle-node trajectories.
We combine both types of transitions to derive the recurrence relation presented in Eq. Subse- quently, we deduce the closed- form expression of (.Aa: Tj) from Eq. 4 The proof is provided in Appendix Sec. A.2 and the corresponding formulation is presented below:
B(Aa, JJ) = (a + j)! 2", for a. 2 0.
(5)
Physically, the term (a + j)! accounts for all possible orderings of the a + sub- -ub-trajectories, where each of them is treated as an atomic step the destruction process. Each multi-node trajectory has 2 possible directions for destruction, contributing an additional 2 multiplicative factor. In contrast, single-node trajectories allow only one valid direction. Therefore, the total number of reward-equivalent permutations is the product of these two factors.
Statement 2 (TB Backward Probability). We denote Pa( (T) as the backward policy probability of complete trajectory T; in the GFlowNet framework under TB, formulated as:
1
PB(T:) (a + j)!
(6)
where the denominator reflects the total number of distinguishable trajectory permutations given multi-node and single-node trajectories to achieve complete trajectory
Statement (DB Backward Probability).. We denote Po(s; si+1) as the probability of a single backward transition from state s to its predecessor st, and under the DB formulation, the backward probability is defined conditionally:
if the current node is the depot, otherwise.
Po(()
2a+3
This probability formulation originates from Eq. 4 which defines the total number of sub-trajectory
backward destruction orderings. Physically, each multi-node trajectory offers two possible predeces- sor nodes for backward disconnection from the depot, thereby contributing the 2a term, while each single-node trajectory provides one such option, contributing the term. The resulting probability 20+j reflects a uniform selection over all valid backward transitions at the current decision step. In contrast, for all other nodes in the trajectory, only a single predecessor is feasible, and thus the backward transition becomes fully deterministic with probability 1.
Meanwhile, F(s]: 0) in Eq. 2 represents the flow of current state, and is derived from the node embedding q at state of. which is calculated as follow:
F(s): 0) = Σ (W2 ReLUU(, - a6 + by) + bz),
(8)
Est

---

where W1. W2, by and by are learnable parameters and ReLU [6] is the activation function. To handle the local objective associated with state transitions. we define the reward of the predecessor state st as zero. Consequently, the energy term {s;) in Eq. i also set to zero. The successor state 8/+1, in contrast, receives a non-zero transition reward. Accordingly, the energy term E($+1) represents the local reward signal, and its negative is defined as follow:
E($)) R(s))
Σ R(s)).
As training progresses, the quality of each trajectory steadily improves, resulting in smaller values of R(s{) as the generated routes become shorter. In Eq. [ we compute the energy {(s)) for state of by subtracting the average reward of other trajectories at the same decision step. This formulation effectively captures the relative advantage of a given state compared to its peers, encouraging the states. As the variance across rewards decreases
model assign higher energy to better-performen during training, the energy values naturally increase.
Then, the DB loss of the completed trajectory T, fai 21, mm can be calculated as:
&D (Ti; 0)
Σ DA 16 0)
(10)
where (D (s), of 1 O) is derived from Eq. 2 The overall loss for the Hybrid-Balane GelowNet,
denoted by li (T; O), computed by aggregating both the TB loss (TB(T: (T: 0) and the DB loss (D;(T; 0) over all trajectories:
h E 0)
LN (T: 0) Σ (T: 0)
LD 0))
(11)
This unified objective enables the model to simultaneously capture global trajectory-leve structure and fine-grained local transitions, leading to more effective and robust optimization in VRPs.
3.2.3 Depot-Guided Inference
Discrete Node
Current Discrete Node
Next Discrete Node Candidate
Other Node
Current Destruction Trajectory
Current Node is Depot
Current Node is Customer
Future Destruction Trajectory
Figure 2: Illustration for Depot-Guide Inference.
The design of Hybrid-Balance Balance GFlowNet's backward policy reveals a key insight: as illustrated in Fig. 2 only the depot node retains flexibility in choosing among multiple predecessor candidates during trajectory destruction. This flexibility stems from the construction of sub-trajectories, each of which begins and ends the depot. In contrast, for all customer nodes, the backward transition path uniquely defined by the trajectory structure, i.e., once a customer node is reached, its predecessor is deterministically identified. This determinism also holds during forward trajectory construction. To leverage this structural characteristic, we propose a depot-guided inference mechanism defined as:
I if the current node I, is depot, x= if the current node I, is customer,
C++1
(12)
where x Pf(0141 84; 0) denotes sampling from the forward transition probability, and xt arg max (5 Sei 0) corresponds to greedy selection. Here, Py (s(411 s;; 0) is derived from
7

---

Table 1: Comparison CVRP datasets of different sizes: Objective (Obj-) values and inference times (in seconds) are shown, and Gap(%) is computed with respect to LKH.
Method
200
500
1000
Time(s)
Gap(
4
Time(s)
Gap(%)
Time(s)
Gap(%) !
LKH
28.04
59.81
63.32
233.72
120.53
433,90
ACO
189.79
371.30
POMO (*8)
29.22
0.29
4.21
79.86
0,84
26.12
192.18
3.06
59,45
29.45
5.03
82.92
0.59
231.88
1.48
GANCO
29.01
0.46
3.57
71.30
148.91
12.60
145.84
4.02
21.00
NeuOpt
AGEN
31,26
0.14
11.48
71.05
0.40
12.21
133.97
0.65
11.15
HBG-AGFN
30.83
0.15
9.95
69.93
0.42
10.44
131.78
9.34
GPACS
34.52.
4.65
23.11
78.41
12.76
23.83
149.24
26.32
23.82
HBG-GFACS
32.66
4.67
16.48
71.89
12.77
13.53
133.32
26.33
10.61
GPACS (local search)
28.63
12.18
2.10
65,24
34,19
3.03
124.15
80.52
3.00
HBG-GFACS (local search)
the edge probability distribution 1)(9", 0) in AGFN or the pheromone map in GFACS. Under this strategy, exploration through sampling is applied only at the depot, while customer nodes follow deterministic, greedy policy.
It is important to note that depot-guides inference is specifically designed for problems featuring designated depot node, such as the CVRP. For problems lacking a depot or node-role differentiation, such as the TSP, retain their original inference procedures, including hybrid decoding strategy (55) for AGFN and the ant clony search 22 for GFACS.
Experiment
We conduct experiments to validate the effectiveness of the Hybrid-Bale Maarid-Ballnceeeee GFlowNet (HBG) in enhancing two representative GFlowNet-based solvers, i.e., AGFN and GFACS, on CVRP. We first present comparison results, followed by ablation studies analyze the contribution of individual components. Lastly, we extend the evaluation to other vehicle routing problem.
Dataset: We adopt synthetic CVRP datasets following standard settings used in prior work [22 25 [5] 49]. Each instance features a single depot and multiple customers served by a vehicle with fixed capacity C. The depot and customer coordinates sampled uniformly from the unit square [0, 1]2, and customer demands follow a uniform distribution U/a, b] with a = and = 9. The vehicle capacity is fixed at C 50 across all problem sizes: 100, 200, 500, and 1,000 nodes. For testing, we generate 128 synthetic instances for each of the 200- 500-, and 1, 1,000-node settings, aligned with evaluation rules established in AGFN and GFACS, The code is available at hhtps //github. hostthu..coom//// Cat.tai.c.c////AAGIIAAAAA ZHANGG
We adopt the model configurations and training settings AGFN and GFACS, including network architecture, batch size, learning rate, optimizer, and other hyperpa- rameters. Training is conducted using sampling-based decoding with V 20 routes per instance. During inference, AGFN uses depot- sepod-guided inference, and GFACS applies an ant colony search with depot-guided node selection. All models are trained 100-node instances. The experiments conducted on a server equipped with an NVIDIA A100 GPU and an Intel Xeon 6342 CPU.
Hyperparameters:
4.1 Performance on Synthetic CVRP Instances
We compare HBG-enhanced models. i.e., HBG-AGFN and HBG-GFACS, with their original TB- based countcrparts, AGFN (53] and GFACS [22]. AGFN constructs routes in an end-to-end manner, while GFACS scarches for solutions by combining GFlowNet with ant colony optimization. We also include classical heuristics (LKH [9), ACO 33) and learning- based baselines (POMO [25], GANCO [50]. NeuOpt (3I) for comparison. All methods are trained on 100-node instances and evaluated on CVRP200, CVRP500, and CVRP1000 datasets, following AGFN and GFACS evaluation protocols. Additional experiments on the public benchmark CVRPLib reported in Appendix B.I
Table shows that HBG consistently improves performance across all problem sizes for AGFN, GFACS, and GFACS with local search. The performance gains are significant, with gap reductions of up to 16.23% 55.46%, and 8.33%, respectively. Improvements become more pronounced as instance size increases, indicating strong scalability. Inference incurs only minor overhead (0.01-0.04

---

Table 2: Ablation Study on AGFN and GFACS: Gap(%) is computed with respect to LKH.
(a) AGFN
(b) GFACS
Methed
290
Dn)...
590
(ape5))
[M)_1
1000
Gapc%)
<NN-
2001
(
20
ON)...
1960
LKH
18044
63.32
133.55
TKH
14
63.50
170.5
71,05
132.0)
13:08
10:81
6838
1853
131 W
4.7
HB
34.01
2120
75
21.8
144.8
1937
Deput-Giske Infoumee
Ceste Irleenace
12.66
10.46
70.00
13.55
1961
Table 3: Comparison of DB, TB, and HB: Gap(%) is computed with respect to LKH.
(a) AGFN
(b) GFACS
Method
Obj-
200
Gap(%)
Obj-
500
Gapt
Obj-
1000
Gapt
Method
Obj-
200
Gap(
Obj. L Gapt
500
Obj
1000
Gap(5))
LKH
28,04
120.53
28.04
63.32
34,41
22.72
76.78
21.26
143.25
18.85
DB
43.28
54.36
94,20
48.77
181.87
50.89
TB
31.26
11.48
71.05
12:21
133.97
11.15
TB
34,52
23.11
78.41
23.83
149.24
23,82
EIB
31,08
10.84
69.99
10.53
131.94
9.47
HR
34,01
21.29
76.67
21,08
144,48
19.87
seconds) due to temporary loading of flow parameters, which does not impact overall runtime or scalability. Compared to other heuristic and learning-based methods, HBG-AGFN and HBG-GFACS achieve competitive or superior solution quality across all scales. On CVRP200, both methods outperform ACO and NeuOpt. On CVRP500 and CVRP1000, they continue to generalize effectively, outperforming ACO, POMO, GANCO, and NeuOpt. These results highlight the robustness, efficiency, and strong generalization capabilities of the proposed HBG framework.
4.2 Ablation Study
Comparison of Component Contributions. We evaluate the contribution of each component in the HBG framework for both AGFN and GFACS. First, we incorporate the Slybrid-Bllane (HB) module into the original models. Then, we add the depot-guided inference mechanism on top of the HB-enhanced variants. As shown in Table[]] each component contributes significantly to performance. Incorporating the HB module alone reduces the optimality gap by up to 15.07% in AGFN and 16.58% in GFACS. Adding depot-guided inference provides further gains, especially for larger instances. These results confirm that the HB module offers consistent improvements and depot-guided inference delivers additional benefits in depot-centric tasks.
Comparison of Balance Strategies. To further validate the effectiveness Hybrid Balance (HB), we conduct comparison against Trajectory Balance (TB) and Detailed Balance (DB) under identical training settings on 100-node instances, evaluated on CVRP200, CVRP500, and CVRP1000. As shown in Table 3 the HB module consistently outperforms both TBB and DB across all instance sizes for both AGFN and GFACS. Notably, HB achieves up to a 15.07% improvement over TB in AGFN and up to 16.58% in GFACS. These results highlight the superior effectiveness of Hybrid Balance as a unifying optimization strategy.
Depot-Guided Inference Variants. We assess four variants of the depot- inference strategy by applying either sampling or greedy decoding at the depot and customer nodes. Tests are conducted using both AGFN and GFACS on CVRP200, CVRP500, and CVRP1000. As shown in Table 4 the combination of sampling at the depot and greedy decoding at customers yields the best performance. This setting consistently outperforms all other variants, including depot greedy + customer sampling, depot greedy customer greedy, and depot sampling + customer sampling. These results validate the effectness our depot-guided inference mechanism.
4.3 Generalization to Other Vehicle Routing Problem
We further evaluate our framework on the Traveling Salesman Problem (TSP), a key VRP variant.
Baselines include GFlowNet-based solvers (AGFN 155, GFACS 22 ), classical heuristics (LKH
19), ACO 3) and learning-based models (POMO 255, GANCO (50) NeuOpt (31). All models
are trained on 100-node instances and evaluated on 200- 500- and 1,000-node settings. Since
TSP lacks a depot node, depot-guided inference is not used. Table 5 shows that HBG-AGFN
consistently outperforms AGEN, reducing the gap by up to 17.64%. HBG-GFACS also achieves

---

Table Ablation Study on Depot- Inference. Gap(%) computed with respect the LKH. DG represents depot greedy, DS represents depot sampling, CG represents customer greedy, CS represents customer sampling.
(a) AGFN
200)
500
1000
Method
Obj. J
Time(s)
Gap( %))
Obj.
Time(s)
Gap (6)
Obj.
Time(s)
Gap %)
LKH
28.04
59.81
63.32
233.72
120.53
433.90
DG and CS
32.78
0.16
16.90
76.42
0.41
20.69
146.14
0.65
21.25
CG
31.96
0.16
71.35
0.41
133.32
0.65
10.61
DS and CS
31.88
0.16
13.69
74.49
0,41
17.64
144.74
0.65
20.09
DS and CG
30.83
0.16
9.95
69.93
0.41
10.44
131.78
0.65
9.34
(b) GFACS
20H)
500
1000
Method
Obj. 4
Time(s)
Gap( %)
Obj.
Time(s)
Gap %)
Obj.
Time(s)
Gap(
LKH
28.04
59.81
63.32
233.72
120.53
433,90
34.87
4.67
24.36
75.99
12.78
20.01
148.53
26.33
23.23
and CG
34.58
4.67
23.32
74.12
12.78
17.06
135.33
26.33
12.28
DS and CS
33.38
4.67
19.04
75.79
12.78
19.69
143.46
26.33
19.02
DS and CG 32.66
4.67
16.48
71.89
12.78
13.53
133.32
26.33
10.61
Table 5: Comparison of performance and runtime TSP with 200, 500, and 1000 nodes. Gap( (%) is computed relative to LKH (10000).
200
500
1000
Method
Time(s)
Gap(%)
Obj.
Time(s)
Gap(%)
Obj-
Time(s)
Gap %c)
LKH
10.62
38,80
16.30
75.29
22.68
149.36
ACO
5.87
817.91
315.42
POMO
10.97
0.12
3.30
20.85
0.39
27.91
33.94
0.59
49.65
POMO (*8)
10.90
0.20
2.64
20.44 44
0.55
25.40
32.
3.42
43,74
NeuOpt
13.22
6.39
24.48
138.15
14.54
747.55
325.28
27.84
1334.22
GANCO
11.30
0.11
6.40
19.69
0.36
20.80
29.97
0.85
32.14
AGEN
0.08
11.58
19.08
0.26
17.06
27.15
Our-AGHN
11.73
0.11
10.45
18.59
0.27
14.05
26.87
0.71
18.47
GFACS
1.64
22.79
9.42
49.76
41.86
Our- Our-GHACSS
12.68
1.66
19.40
24.19
9.43
488.41
39.90
20.81
75.93
GFACS (local scarch)
10.78
6.67
1.51
27.76
4,91
24.45
7,80
Our-GFACS (local search)
10.78
6.08
1.50
17.05
27.78
4.60
24.42
58.42
7.67
notable improvements, with the gap on 200-node instances reduced from 22.79% to 19.40%. With
local search, HBG-GFACS achieves further improvements, with the best gap reduction reaching 6.31%. %. Compared to classical heuristics and learning-basee methods such as ACO, POMO, NeuOpt, and GANCO, both HBG-AGFN and HBG-GFACS achieve competitive results on TSP tasks. These results confirm the generalizability and strong performance of HBG on TSP tasks.
Conclusion
In this paper, we introduced the Hybrid-Balame GFlowNet (HBG) framework to enhance the performance of GFlowNet-based solvers for vehicle routing problems. HBG unifies Trajectory Balance and Detailed Balance in prineipled and adaptive manner to jointly optimize local and global objectives. We also proposed a depot-guided inference strategy aligned with the Hybrid-Balance principle, specifically tailored for depot-centric problems. Extensive experiments on both CVRP and TSP benchmarks demonstrate that HBG significantly improves the performance of two representative GFlow/Net-based solvers, i.e., AGFN and GFACS, showcasing improved solution quality, scalability, and generalization. A current limitation of HBG is its reliance existing GFlowNet-baa based models, as its performance depends in part on the underlying solver, which might be inferior to others. In future work, we plan to integrate it with altermative stronger generative policies and solvers.
Acknowledgments and Disclosure of Funding
This research is supported by the National Research Foundation, Singapore under its Al Singapore Programme (AISG Award No: AISG3-RP-2022-031. AISC3-RRP-2025--0---SSSST and the Lee Kong Chian Fellowship awarded to CAO Zhiguang by Singapore Management University.
10

---

References
[1] Florian Amold, Michel Gendreau, and Kenneth Sörensen. Efficiently solving very large-seale routing problems. Computers & operations research, 107:32 42, 2019.
[2] Gulay Barbarosoglu and Demet Ozgur. A tabu search algorithm for the vehicle routing problem. Computers & Operations Research, 26(3):255-270, 1999.
[3] John E Bell and Patrick R McMullen. Ant colony optimization techniques for the vehicle routing problem. Advanced engineering informatics, 18(1):41-48, 2004.
[4] Emmanuel Bengio, Moksh Jain, Maksym Korablyov, Doina Precup, and Yoshua Bengio. Flow network based generative models for non-iterative diverse candidate generation. Advances in Neural Information Processing Systems, 34:27381-27394, 2021.
[5] Jieyi Bi, Yining Ma, Jiahai Wang, Zhiguang Cao, Jinbiao Chen, Yuan Sun, and Yeow Meng Chee. Learning generalizable models for vehicle routing problems via knowledge distillation. Advances in Neural Information Processing Systems, 11331226-31238 2022.
[6] Yinpeng Chen, Xiyang Dai, Mengchen Liu, Dongdong Chen, Lu Yuan, and Zicheng Liu. Dynamic relu. In European conference on computer vision, pages 351-367. Springer, 2020.
[7] Younghoon Choi, Bradford Robertson, Youngjun Choi, and Dimitri Mavris. multi-trip vehicle routing problem for small unmanned aircraft systems- bbased urban delivery. Journal of Aircraft, 56(6):2309-233) 2019.
[8] Zeynel Abidin Çil. Hande Öztop, Zülal Diri Kenger, and Damla Kizilay. Integrating distributed disassembly line balancing and vehicle routing problem supply chain: Integer program- ming, constraint programming, and heuristic algorithms. International Journal of Production Economics, 109014 2023.
[9] Tiago da Silva, Fliezer Silva, António Góis, Dominik Heider, Samuel Kaski, Diego Mesquita, and Adèle Ribeiro. Human-in-the-loww causal discovery under latent confounding using ancestral gflownets. arXiv preprint arXiv:2309.12.32 2023.
[10] Tristan Deleu, António Góis, Chris Emezue, Mansi Rankawat, Simon Lacoste-Julien, Stefan Bauer, and Yoshua Bengio. Bayesian structure learning with generative flow networks. In Uncertainty in Artificial Intelligence, pages 518 318-528. PMLR, 2022.
[11] Rodolfo Dondo, Carlos A Méndez, and Jaime Cerdá. The multi multi-echeeln vehicle routing problem with cross docking supply chain management. Computers Chemical Engineering, 35(12):3002-3024 2011.
[12] Verena Ch Ehrler, Dustin Schöder, and Saskia Seidel. Challenges and perspectives for the use of electric vehicles for last mile logistics of grocery e-commerce -oommerce-findings from case studies in germany. Research in Transportation Economics. 87:100757, 2021.
[13] Han Fang, Zhihao Song, Paul Weng, and Yutong Ban. Invit: a generalizable routing prob- lem solver with invariant nested view transformer. In Proceedings of the 41st International Conference on Machine Learning, pages 12973-12992, 2024.
[14] Chengrui Gao, Haopu Shang, Ke Xue, Dong Li, and Chao Qian. Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy. In International Joint Conference on Artificial Intelligence, 2024.
[15] Antonio Giallanza and Gabriella Li Puma. Fuzzy green vehicle routing problem for designing a three echelons supply chain. Journal of Cleaner Production, 129:74,774 2020.
[16] Akshat Santhana Gopalan and Sowmya Ramaswamy Krishnan. Generative flow networks for lead optimization in drug design (student abstract). In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 29484-29486, 2025.
[17] Ronald I. Graham. Concrete mathematics: a foundation for computer science. Pearson Education India, 1994.

---

[18] Jiaqi Guo, Jiancheng Long, Xiaoming Xu, Miao Yu, and Kai Yuan. The vehicle routing problem of intercity ride- aha-sharing between two cities. Transportation Research Part B: Methodological. 158:1 13-319,, 2022.
[19] Keld Helsgaun. An effective implementation of the lin ken-kgnn traveling salesman heuristic. European journal of operational research, 126(1): 10:10606330, 2000.
[20] Ziwei Huang, Jianan Zhou, Zhiguang Cao, and Yixin Xu. Rethinking light decoder-based solvers for vehicle routing problems. The Thirteenth International Conference on Learning Representations, 2025.
[21] Gitae Kim, Yew-Soon Ong, Chen Kim Heng. Puay Siew Tan, and Nengsheng Allan Zhang. City vehicle routing problem (city vrp): A review. IEEE Transactions on Intelligent Transportation Systems, 16(4):155411666 2015.
[22] Minsu Kim, Sanghyeok Choi, Hyeonah Kim, Jiwoo Son, Jinkyoo Park, and Yoshua Bengio. Ant colony sampling with gflownets for combinatorial optimization. In The 28th International Conference on Artificial Intelligence and Statistics.
[23] Wouter Kool, Herke van Hoof, and Max Welling, Attention, learn to solve routing problems! In International Conference on Learning Representations.
[24] Michal Koziarski, Andrei Rekesh, Dmytro Shevchuk, Almer van der Sloot, Piotr Gaiński, Yoshua Bengio, Chenghao Liu, Mike Tyers, and Robert Batey. Rgfn: Synthesizable molecular generation using gflownets. Advances in Neural Information Processing Systems, 37:46908- 46955, 2024.
[25] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iijoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21 188 21 198, 2020.
[26] Yeo Kwon, Jinho Choo, Iljoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. Advances in Neural Informa- lion Processing Systems, 34:5138-5144 2021.
[27] Sida Li, Ioana Marinescu, and Sebastian Musslick. Gfn-sr: Symbolic regression with generative flow networks. In NewrlPS 2023 for Science Workshop.
[28] Wengian Li, Yinchuan Li, Shengyu Zhu, Yunfeng Shao, Jianye Hao. and Yan Pang. Gflowcausal: Generative flow networks for causal discovery. arXiv preprint arXiv:2210.08185, 2022.
[29] Yinchuan Li, Shuang Luo, Haozhi Wang, and HAO Jianye. Cflownets: Continuous con- trol with generative flow networks. In The Eleventh International Conference on Learning Representations.
[30] Yeqian Lin, Wenquan Li, Feng Qiu, and He Xu. Research optimization of vehicle routing problem for ride-sharing taxi. Procedia-Socia and Behavioral Sciences, 43:494-502. 2012.
[31] Yining Ma, Zhiguang Cao, and Yeow Meng Chee. Learning to search feasible and infeasible regions of routing problems with flcxible neural k-opt. Advances in Neural Information Processing Systems, 36, 2024.
[32] Nikolay Malkin, Moksh Jain, Emmanuel Bengio, Chen Sun, and Yoshua Bengio. Trajectory balance: Improved credit assignment in gflownets. Advances in Neural Information Processing Systems, 35:5955-5967, 2022.
[33] Kishan Reddy Nagiredla, Arun Kumar AV, Thommen George Karimpanal, and Santu Rana. Robonet: A sample-efficient robot co-design generator. In /CoRI. 2024] Morphology-Aware Policy and Design Learning Workshop (MAPoDel.).
[34] Andrei Cristian Nica, Moksh Jain, Emmanuel Bengio, Cheng-Hao Liu, Maksym Korablyov, Michael M Bronstein, and Yoshua Bengio. Exaluating generalization in gflownets for molecule design. In /CLR2022 Machine Learning for Drug Discovery, 2022.
12

---

[35] Mizu Nishikawa- Nishikawa-Toomey, Tristan Deleu, Jithendaraa Subramanian, Yoshua Bengio, and Laurent Charlin. Bayesian learning of causal structure and mechanisms with gflownets and variational bayes. arXiv preprint arXiv:221 1.02663, 2022.
[36] Ibrahim Hassan Osman. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of operations research, 41:421-451, 1993.
[37] Ling Pan, Nikolay Malkin, Dinghuai Zhang, and Yoshua Bengio. Better training of gflownets with local credit and incomplete trajectories. In International Conference on Machine Learning, pages 26878-2222 26890. PMLR, 2023.
[38] Xuanhao Pan, Yan Jin, Yuandong Ding, Mingxiao Feng. Li Zhao, Lei Song, and Jiang Bian. H-tsp: Hierarchically solving the large-scale traveling salesman problem. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 37, pages 3345-9353,, 2023.
[39] MID Ranathunga, AN Wijayanayake, and DHH Niwunhella. Solution approaches for combining first-mile pickup and last-mile delivery in e-commerce logistic network: A systematic literature review. In 202/ International Research Conference on Smart Computing and Systems Engineering (SCSE), volume 4, pages 267-275. IEEE, 2021.
[40] Seonghwan Seo, Minsu Kim, Tony Shen, Martin Ester, Jinkyoo Park, Sungsoo Ahn, and Woo Youn Kim. Generative flows synthetic pathway for drug design. In NeurlPS 2024 Workshop on Al for New Drug Modalities.
[41] Tony Shen, Mohit Pandey, Jason R Smith, Artem Cherkasov, and Martin Ester. Tacogfn: Target conditioned gflownet for structure-based drug design. CoRR, 2023.
[42] Tiago Silva, Daniel Augusto de Souza, and Diego Mesquita. Streaming bayes gflownets. Advances in Neural Information Processing Systems, 37:27153-2711 2024.
[43] Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimization. Advances in neural information processing systems,
2023.
[44] Amirmahdi Tafreshian, Neda Masoud, and Yafeng Yin. Frontiers in service science: Ride matching for peer-to-peer ride sharing: A review and future directions. Service Science, 12(2-3):44-60, 2020.
[45] Christo Kurisummoottil Thomas and Walid Saad. Neuro-symbolic causal reasoning meets signaling game for emergent semantic communications. IEEE Transactions Wireless Com- munications, 2355):554-4456, 2023.
[46] Thibaut Vidal. Hybrid genetic search for the evrp: Open- implementation and swap* neighborhood. Computers Operations Research, 146433 2022.
[47] Mingzhao Wang, You Zhou, Zhiguang Cao, Yubin Xiao, Xuan Wu, Wei Pang, Yuan Jiang, Hui Yang, Peng Zhao, and Yuanshu Li. An efficient diffusion-based non-autoregressive solver for traveling salesman problem. In Proceedings of the 31th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2025.
[48] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1): (2(1):4-24 3:422,,222 2020.
[49] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Neurolkh: Combining deep learning model with kee.---eii-a-nelggeeaeaee heuristic for solving the traveling salesman problem. Advances in Neural Information Processing Systems, 34:7472 74832, 2021.
[50] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Generative adversarial training for neural combinatorial optimization models. 2022.
[51] Haoran Ye, Jiarui Wang, Zhiguang Cao, Helan Liang, and Yong Li. Deepaco: Neural-enhanced ant systems for combinatorial optimization. Advances neural information processing systems, 06:4370-433728 2023.
13

---

[52] Haoran Ye, Jiarui Wang. Helan Liang, Zhiguang Cao. Yong Li, and Fanzhang Li. Glop: Learning global partition and local construction for solving large-scale routing problems in real-time. In Proceedings of the AAAI conference artificial intelligence, volume 38, pages 20284-20292, 2024.
[53] Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron Courville, Yoshua Bengio, and Ling Pan. Let the flows tell: Solving graph combinatorial problems with gflownets. Advances in neural information processing systems, 36:1 191111922199199 11969, 2023.
[54] Mengdi Zhang. Saurabh Pratap. Zhiheng Zhao, Dhirendra Prajapati, and George Q Huang. Forward and reverse logistics vehicle routing problems with time horizons in b2c e-commerce logistics. International Journal of Production Research, 59(20))6291-6310 2021.
[55] Ni Zhang, Jingfeng Yang. Zhiguang Cao, and Xu Chi. Adversarial generative flow network for solving vehicle routing problems. The Thirteenth International Conference on Learning Representations, 2025.
[56] Changjiang Zheng, Yuhang Gu, Jinxing Shen, and Muging Du. Urban logistics delivery route planning based on single metro line. IEEE Access, 1:50819-50830, 2021.
[57] Yiheng Zhu, Jialu Wu, Chaowen Hu, Jiahuan Yan, Tingjun Hou, Jian Wu, et al. Sample- efficient multi-objeccive molecular optimization with gflownets. Advances in Neural Information Processing Systems, 36:79667-79684, 2023.
14

---

A Methodology Details
A.1 Graph Neural Network
Our GNN architecture follows the same design as those used in AGEN and GFACS to ensure fair comparison, which uses a custom GNN architecture designed specifically for the VRP task, and employs a custom message-passing GNN that jointl updates node and edge representations over multiple layers. At each layer node embedding hy of the i-th node and edge embedding et, between the i-th and j-th nodes are updated via the following formulations:
h, = k4 + ACT (N + A(a(ely O Wikh)))
(13)
5) = c/ + ACT ( + Win! + W)
(14)
where W1. W2, W3, W1, W are learnable parameters, A(-) denotes the aggregation function (mean pooling in our case), (-) the sigmoid activation that modulates attention over neighbors, and ACT denotes the SiLU activation. Batch normalization (BN) is applied at each step for stability. The number of layers is set to 12 for HBG-GFACS and 16 for HBG-AGFN, with hidden dimensions of 32 and 64, respectively.
A.2 Proof Process of Hlybrid-Balance
To solve Eq. 4 We begin by establishing the boundary conditions. When either or j 0, the recurrence simplifies accordingly. For instance, when a = O, we obtain:
BBA,, Jj) = ((Ao,,J-1))
(15)
When a = 0 and j = O, there are no sub-trajectories in тG, and r; contains only the depot node. Therefore, the base case becomes B(Ag: To) 1, and is equivalent to:
Jo) = (0 + 0)!
for = O. 0! 0!
(16)
Using Eq. 15 recursively and applying the base case ((Au, To) = 1, we derive:
B(Ao. J,) = jj.
(17)
Similarly, when j 0, we can deduce that:
B(A., [o] = 2n .a!
(18)
We now normalize Eq. by dividing both sides by 2a a. fl, resulting in:
B(Aa,JT) B B(An-1,J9)
B(Aa, Jy-1)
(19)
2a a jj
2a-1 (a (a-11) 1)! 1).- j! 2a - (j-1)!"
Based on this, we define normalized function:
c(A,, J,), 2 B(A, J,)
(20)
2a a! j!
Substituting Eq. 20 into Eq. 19 we obtain the recurrence:
c(Au, JJ) c(Au-1, JT) + c(Au, Jy-1).
(21)
We analyze the recurrence in Eq. 21 under the boundary conditions, and derive results from Eqs.
18 and
20
c(Au, J,) = 1, To) To)= =1 for all a. 2
These boundary conditions are equivalent to:
(0 + j)!
c(Ao. TT) =
for a = 0,j > 0,
(22)
0! 0!.
c(An,To) =1 (a + 0)!
for a 0,j 0.
(23)
a! 0f
15

---

Table 6: Test the CVRPLIB-XXS benchmark. Gap(%) is computed with respect the optimal
solution.
4
L1 (3k)
1.2 (4k)
A1 (6k)
A2 (7k)
G1 (10k)
G2 (11k)
B1 (15k)
B2 (16k)
AGFN
1145.18
27.87
29.62
24.59
142.62
27.24
20.65
120.69
HBG-AGFN
97.15
25.09
25.36
20.96
113.89
20.47
109.80
46.97
GFACS
119.24
1788.57
112.08
236.79
281.34
2207.71
352.69
2537.29
HBG-GFACS
52.25
33.96
21.58
39.19
78.88
31.60
179.70
37.43
Moreover, motivated by Pascal's rule [77. which states:
(K)
n n2 - =
h - + n- ) for all integers 2 1 and S k S n,
and by setting n = a + j, k = o, we obtain:
a (at)) aa+
a (a+-1)) 1) + (a+ ( for a. 1,
which is equivalent to:
a ( = (aa-1)
+
a (j - "
+
-
This is similar with the function of c(Aa: Jj] in Eq. 21 Therefore, the closed-form expression of c(Aa; Jj) is:
c(Aa, = + = (a j)!
for a.j 2 1.
(24)
a.-j!
By extending Eqs. 16 as:
and 24 the generalized closed-form solution for all a. 2 0 is given
a + a
(a + j)!
c(Aa, JT)
(25)
a! j!
Finally, substituting Eq. 25 into Eq. 20 we obtain the closed-form expression for the total number of distinct sub-trajectory orderings resulting in the same complete trajectory:
B(A.. (a + j)!- for a, 2
(26)
B More Experiments
B.1 Test on Real world dataset
To evaluate our model's performance on real-world data, we conduct experiments on the CVRPLIB- XXL [1, which designed to test model's performance on large-scale real-world instances. As shown in T HBG-AGFN achieves up to 91.51% reduction in gap compared to AGFN, while HBG-GFACS achieves up to 98.52% improvement over GFACS. These results demonstrate that our framework significantly enhances the performance of GFlowNet-based solvers on real-world datasets.
Table 7: Comparison of Hyperparameter Settings CVRP
(a) Sparsity Parameter
(b) Learning Rate
(c) Optimizer Type
CVRP (G
2001
500
1000
CVRPP-ap''
200
500
[193]
CVRP (Gag())
200
500
1000
HBG GRACS_2
Scorgin))
10.25
16:27
12.09
HBQ LEACS
13.53
14.57
11.50
HBG CEACS Mar
1133
14.75
11:11
HBQ OEACCE
foeiaia)
18:45
13.59
18.43
LEGASS AsbroWieeisst
HBG GEMCS
HBG AAGEL
HBG CalSCSllechh
HBG GIAC Selecll 10
12:62
1.67
1.56
13.48
3.43
17.52
4.57
HBQ DEMCS Mondl batt
HIN Sihooa (podpoi
133
1.30
1,65
1.45
1.50
HBKL ALEN Ades
H800 Thaatl Adam
SCD
1016
283
13:00
2.70
11:77
2:73
HIG AGEN Scrigie)
9.50
IIN. ARSIN Sw10
11/11
1167
MaleWarign
HBG_AGEENS
HBC. AMINN 1x10e
1535
17:77
10:2
18.34
9:31
16

---

B.2 Hyperparameter Sensitivity Analysis on CVRP
The introduction of a new loss component (LDB) could potentially alter the optimization landscape. and that the original hyperparameter settings used in AGFN and GFACS may not be optimal for the proposed HBG variants. We further conduct additional experiments in which we re-tuned key hyperparameters for the HBG models, including the sparsity parameter, learning rate, and optimizer settings. The updated results (Table 7cp will be incorporated into the Appendix of the revised version. HBG-GFACS refers to the HBBG-FAAS model evaluated with a sparsity parameter /V/2 the interpretation analogous for the other entries. The term origin denotes the original hyperparameter configuration used in our main experiments. HBG-GFACS 5x10 SUNG-GFFCSS510011 refers to the HBG-GFACS model evaluated with learning rate x 10 10-3, 3; the interpretation is analogous for the other entries. HBG-GFACS_SEE SGD refers the HBG-GFACS model evaluated using the SGD optimizer; the interpretation analogous for the other entries.
As the sparsity parameter results shown in Table 7a the optimal sparsity setting yields the best performance for both HBG-GFACS and HBG-AGFN. Regarding the learning rate comparisons in Table 7b] for HBG-GFACS, the original value of 5 x 10-1 performs best without local search, while a value of 10-3 achieves the best results when local search is enabled. For HBG-AGFN, learning rate of 1 x 10 shows superior performance on the 200- and 500-node instances, whereas the original value performs best on the 1000-node instances. As for the optimizer comparison in Table 7cl the original AdamW setting provides the best performance in most cases. An exception is observed on the 500- and 1000-node instance with local search, where Adam slightly outperforms AdamW for HBG-GFACS.
B.3 Weight À of DB and TB
Table Weights Analysis HBG-AGEN on CVRP
Size (G)
0.5++0
1->0
2-+0
0.5->0.5
1 1-50.5
2-+0.5
0,5++1
1-+1 (origin)
2-+2
200
11.09
10.80
10.94
11.41
11.98
11.20
9.98
9.95
10.44
500
11.27
12.04
11.18
12.15
11.66
11.80
11.63
10.44
11.98
1000
10.89
10.61
9.89
11.03
10.84
10.98
10.87
9.34
10.08
Table 9: Weights Analysis of HBG-AGFN on TSP
Size (Gap %)
0.5-+0
1-+0
2-+0
0.5-+0.5
1-+0.5
2-+0.5
0.5++1
1-+1 (origin)
2-+2
200
10.26
10.42
10.49
11.48
11.26
10.66
10.08
10.45
10.36
500
15.15
15.40
16.13
16.87
16.09
15.79
14.91
14.05
15.64
1000
18.80
18.55
19.00
19.26
21.87
22.00
18.52
18.47
18.81
Table 10: Weights Analysis of HBGG-FACS on CVRP
Size / Gap( /
0.5++0
1-+0
2-+0
0-0.5
0-+1
0-+2
0.5
1-1 1 (origin)
2-+2
200
14.05
19.29
17.37
17.72
18.47
19.08
16.42
16.48
18.87
500
11.78
17.66
15.38
15.28
16.35
15.71
13.57
13.53
15.49
1000
11.29
15.80
12.71
12.88
13.47
12.80
10.91
10.61
12.80
200 (local search)
2.39
1.78
2.03
2.07
2.14
1.96
1.96
1.96
1.78
500 (local search)
3.02
2.51
2.91
3.41
3.44
2.99
3.17
2.81
2.62
1000 (local search)
2.82
2.27
2.82
3.31
3.53
3.22
2.75
2.75
2.40
We have conducted additional experiments on the weighted combination (i.c., CHB CTB + >LDB) assess the sensitivity of our method to different values of X, which are gathered Tables 8 The results include both adaptive weights (i.e., A: 0.5-0. 1 1-+0, 2-+0 and so on) and fixed weights (i.e.. 0.5-00.5, 1-,1, 2-22). where 0.5 denotes changing the TB:DB loss weight ratio from 1:0.5 1:0 during training, with TB weight fixed at 1. The interpretation for other entries follows analogously. The term origin denotes the original hyperparameter setting used our main experiments. find that, for HBG-AGFN, fixed 1:1 weight between TB and DB consistently yields the best performance. Similarly, for HBG-GFACS, this ratio offers the most favorable trade-off between performance and stability with and without local search.
17

---

Table 11: Weights Analysis of HBG-GFACS TSP
Size / Gap( /
0.5-+0
1-x0
2-+0
0-+0.5
0-+1
0-+2
0.5
1 1-11 (origin)
2-+2
200
19.13
20.61
23.06
22,21
20.56
24.02
21.64
19.40
22.82
500
49.51
49.61
50.80
49,48
48.47
56.13
49.62
48.41
50.37
1000
72.30
80.19
90.50
79.37
80.39
96.36
77.45
75.93
87.23
200 (local search)
1.57
1.49
1.59
1.59
1.62
1.82
1.54
500 (local search)
4.81
4.65
5.02
4.88
4.73
5.18
4.73
4.68
5.12
1000 (local search)
7.73
7.68
7.86
7.83
8.02
8.20
7.70
7.67
7.99
B.4
Statistical Significance of Experiment
HBG-AGFN
HBG-GFACS
20
8.3
18
8.2
16
Ob
8.1
14
7.9
2000
4000
6000
8000
10000
200
400
6.00
800
1000
Training Step
Training Step
Figure 3: Training Process of HBG-AGFN and HBG-GFACS.
As shown in Fig. both HBG-AGFN and HBG-GFACS exhibit clear and steady decline in objective values throughout the training process, indicating stable convergence. The narrow shaded areas-reep areas-neprssenting standard deviation across five random seeds-suggest low variance among runs. These results collectively highlight the effectiveness of the training process and the statistical reliability of the observed performance gains.
NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], , [No] or [NA]
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist one of the factors their evaluation. While "[Yes] is generally preferable to "[No] ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased binary way, we acknowledge that the true answer often more nuanced, please just use your best judgment and
18

---

write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, the main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope, and are supported by the methodology and results presented in the main body.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The paper discusses the limitations of the work in the Conclusion section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they seale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
19

---

While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Yes, the paper provides the full set of assumptions and corresponding proof' for each theoretical result in the Methodology section and the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems. The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Yes, the paper provides all necessary implementation and experimental details required reproduce the main results, as described in the Method and Experiment sections. The code will be made publicly available upon publication.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
20

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [No]
Justification:
We will also release the code upon publication.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
The training and test details are shown in experiment section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
21

---

Description about the statistical significance of the experiments are provided in Ap- pendix B.4
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We report compute resources in experiment section.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
22

---

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
This paper first time unify Detailed Balance and Trajectory Balance for solving vehicle routing problems, and the Hybrid-balance handle well with global-local optimization. This work has potential to have good impact in both GFlowNet and VRPs research community.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologics that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e-g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: For all models and datasets used, cite its original papers.
23

---

Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com camdsatasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We do not introduce any new assets at this stage. Upon publication, all code and datasets used in this work will be made publicly available. The methodology and experimental settings are thoroughly documented paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cooe/mmodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?

---

Answer:
[NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not non non- stanstandard components.
involve LLMs as any important, original,
Please refer to our LLM policy for what should or should not be described.
25


Reviews:
[{"review_id": "fUEPmJZXIW", "reviewer": "Reviewer_4QUb", "summary": "The paper introduces Hybrid-Balance GFlowNet (HBG), a framework that unifies Trajectory Balance (TB) and Detailed Balance (DB) objectives for solving Vehicle Routing Problems. The authors argue that existing GFlowNet-based VRP solvers like AGFN and GFACS rely exclusively on TB, which captures global optimization but neglects local optimization signals. Their key insight is that DB can address local optimization while TB handles global objectives. The framework includes a depot-guided inference strategy that exploits the structural property that depot nodes have greater flexibility in successor selection compared to customer nodes. Experimental results on CVRP and TSP show consistent improvements when HBG is integrated into existing solvers.", "questions": "The paper's treatment of the Graph Neural Network component lacks crucial implementation details and theoretical motivation. While Section 2.1 mentions incorporating a GNN module to 'effectively model complex relational structures of VRP instances,' several important aspects remain unclear:\n\n1. The paper cites a general GNN survey [45] but does not specify which GNN variant is employed (e.g., GCN, GraphSAGE, GAT, or a custom architecture). This omission makes reproduction difficult.\n\n2. How exactly does information propagate between nodes? What are the specific update functions for node and edge representations? The paper mentions processing features 'through multiple layers' but provides no details about the aggregation and update schemes.\n\n3.  While k-nearest-neighbor sparsification is mentioned for scalability, what value of k is used? How is this parameter selected, and how does it affect performance across different problem sizes?\n\n4. The experiments section lacks any GNN-specific hyperparameters (number of layers, hidden dimensions, activation functions, normalization schemes). These details are essential for reproducibility and understanding the method's sensitivity to architectural choices.\n\nAlso, the combination of TB and DB losses through simple summation (Equation 11), have the authors considered adaptive weights?", "limitations": "yes", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "__Strengths:__\n\nThe observation that existing GFlowNet VRP solvers focus exclusively on global optimization through TB while ignoring local patterns is valid and represents a genuine limitation. \n\nThe observation that depot nodes have multiple valid predecessor options during backward trajectory destruction, while customer nodes have deterministic predecessors is well-exploited.\n\nThe experimental evaluation covered multiple problem instances and baseline comparisons. The consistent improvements across both AGFN and GFACS demonstrate the generality of the approach. \n\n \n\n__Weaknesses:__\n\nThe paper essentially combines two existing GFlowNet objectives (TB and DB). While the combination is sensible, the theoretical contribution is limited.\n\nThe relationship between the step-wise and trajectory-level probabilities could be better explained, particularly how the DB formulation maintains consistency with the overall GFlowNet framework.", "was_revised": true, "final_justification": "Authors have well provided answers for my questions, and I tend to increase my score.", "rebuttal": "We sincerely thank the reviewer for the insightful feedback, particularly kind comments of our **well-motivated, depot-aware design and effective experimental validation**.\n### W1 W2: Theoretical Contribution: the Consistency of DB and Overall GFlowNet Framework\nWhile TB and DB have been individually explored in prior work, our work presents the **first attempt to unify them within one consistent theoretical framework, which is non-trivial and challenging**.\n\nSpecifically, the **DB objective has never been applied to VRP before**, and **no prior work has explored the combination of TB and DB in GFlowNets**. Formulating the DB objective in the VRP setting and achieving a coherent integration with the TB objective requires reconciling two fundamentally different types of training signals and carefully designing forward and backward dynamics that remain consistent throughout the training process. \n\n**Backward Probability**. Leveraging the hybrid structure of VRP whose solution is comprised of multi-node and single-node sub-tours, we derive a general recurrence formulation of trajectory orders’ count (Eq. (4)). And this formulation serves as the foundation for unifying TB and DB under a consistent probabilistic framework. From this unifying recurrence, we analytically derive a set of twelve equations (Eq. (13)–(24)) in the Appendix, leading to the trajectory-level backward probability of TB (Eq. (6)) and step-wise backward probability of DB (Eq. (7)). These two backward formulations are inherently consistent, as they are both derived from the same recurrence relation in Eq. (4). \n\n**Forward Probability**. We define the relationship between the step-wise (DB) and trajectory-level (TB) forward probabilities in Eq. (3), where the step-wise forward probability serves as the building block of the trajectory-level forward probability. This formulation ensures that the two are mathematically consistent within the unified framework.\n\n**Flow**. We further clarify the definition of flow under joint training: the DB flow is computed from the embedding of the current state's node, while the TB flow is computed from the embedding of the final trajectory's nodes. In essence, the DB flow can be seen as an intermediate form of the TB flow, capturing the flow dynamics at each decision step. This perspective reinforces consistency of our unified GFlowNet framework.\n\nMoreover, motivated by the structure of the hybrid balance, we derive an important structural property: only the depot node retains multiple feasible predecessors during reverse sampling. This insight leads us to design the Depot-Guided Inference, which plays a key role in guiding trajectories generation.\n\n**Placing most of derivations in the Appendix may have made our theoretical contribution less clear. To improve clarity, we will move the key parts to the main text in the revised version.**\n\nOverall, we believe our framework provides **a novel and principled theoretical foundation** for **combining TB and DB objectives in GFlowNets in a consistent manner**, particularly adapted to complex routing problems, and opens up new possibilities for general-purpose generative models in structured combinatorial domains.\n### Q1 Q2 Q4: GNN\nAs our GNN architecture **follows the same design as those used in AGFN and GFACS to ensures a fair comparison**, we initially omitted its detailed description due to space limitation. However, as the reviewer suggested, We **include the GNN specifications below and will incorporate them into the revised version of the paper**. \n\nOur model uses a custom GNN architecture designed specifically for the VRP task, which is widely used in VRP domain, and employs a custom message-passing GNN that jointly updates node and edge representations over multiple layers. At each layer 𝑙, node embedding $ℎ_𝑖^𝑙$ of the 𝑖-th node and and edge embeddings $𝑒^{𝑖𝑗}_l$ between the 𝑖-th and j-th node are updated via the following formulations: \n\n$\\mathbf{h}^{l+1}_i$ = $\\mathbf{h}^l_i$ + $\\mathrm{ACT}$ (  $\\mathrm{BN}$ ( $\\mathbf{W}^l_1$ $\\mathbf{h}^l_i$ + $\\mathcal{A}$ ( $\\sigma$ ( $\\mathbf{e}_l^{ij}$ ) $\\odot$  $\\mathbf{W}^l_2 \\mathbf{h}^l_j) )$\n\n$\\mathbf{e}_{l+1}^{ij}$ = $\\mathbf{e}_l^{ij}$ + $\\mathrm{ACT}$ ( $\\mathrm{BN}$ ( $\\mathbf{W}^l_3$ $\\mathbf{e}_l^{ij}$ + $\\mathbf{W}^l_4 \\mathbf{h}^l_i$ + $\\mathbf{W}^l_5 \\mathbf{h}^l_j$ ))\n\nHere, $W_1^l, W_2^l, W_3^l, W_4^l$ are learnable parameters, 𝐴(⋅) is the aggregation function (mean pooling in our case), 𝜎(⋅) is the sigmoid activation that modulates attention over neighbors, and ACT denotes the SiLU activation. Graph normalization (BN) is applied at each step for stability. And the number of layers is set to 12 for HBG-GFACS and 16 for HBG-AGFN, with hidden dimensions of 32 and 64, respectively.\n### Q3: Sparsification Value\nWe follow AGFN and GFACS in setting the value of k for fair comparison: **k = |V|/5 for both HBG-GFACS and HBG-AGFN on CVRP, k = |V|/10 for HBG-GFACS on TSP, and k = |V|/5 for HBG-AGFN on TSP**, where ∣V∣ denotes the number of nodes in the instance. Inspired by the reviewer’s comment, we further conducted an ablation study to evaluate how different choices of k affect model performance across various problem sizes to provide a more comprehensive assessment of our model. \n**The results are presented in Table A1 and A2 below.** On CVRP, the original k setting consistently outperforms other configurations. For TSP, HBG-GFACS achieves the best performance with its original k setting. Although HBG-AGFN with the original k slightly underperforms compared to k = |V|/2 on 200-node TSP instances instances, it demonstrates superior results on the 500- and 1000-node TSP instances and CVRP instances of all scales. Overall, the results suggest that the best performance is typically achieved at the original k setting.\n\n### Table A1. Comparison of Various Sparse Parameter k on CVRP\nHBG-GFACS_2 refers to the HBG-GFACS model evaluated with k=|V|/2; the interpretation is analogous for the other entries. The term \"origin\" denotes the original hyperparameter setting used in our main experiments.\n|CVRP(Gap%)|200|500|1000|\n|:-:|:-:|:-:|:-:|\n|HBG-GFACS_2|19.26|16.27|12.69|\n|HBG-GFACS_5(origin)|**16.48**|**13.53**|**10.61**|\n|HBG-GFACS_8|17.90|13.83|11.02|\n|HBG-GFACS_10|20.43|17.88|14.9|\n|HBG-GFACS(local search)_2|2.13|3.41|3.46|\n|HBG-GFACS(local search)_5(origin)|**1.96**|**2.81**|**2.75**|\n|HBG-GFACS(local search)_8|2.13|3.36|3.51|\n|HBG-GFACS(local search)_10|3.07|4.03|4.77|\n|HBG-AGFN_2|12.62|13.36|14.78|\n|HBG-AGFN_5(origin)|**9.95**|**10.44**|**9.34**|\n|HBG-AGFN_8|11.55|13.27|12.69|\n|HBG-AGFN_10|12.98|14.5|14.06|\n### Table A2. Comparison of Various Sparse Parameter k on TSP\n|TSP(Gap%)|200|500|1000|\n|:-:|:-:|:-:|:-:|\n|HBG-GFACS_5|24.91|64.91|108.11|\n|HBG-GFACS_10(origin)|**19.40**|**48.41**|**75.93**|\n|HBG-GFACS_15|23.11|58.22|94.53|\n|HBG-GFACS_20|31.61|66.91|107.35|\n|HBG-GFACS(local search)_5|2.39|7.61|10.92|\n|HBG-GFACS(local search)_10(origin)|**1.50**|**4.60**|**7.67**|\n|HBG-GFACS(local search)_15|1.72|5.36|10.53|\n|HBG-GFACS(local search)_20|3.01|6.87|11.58|\n|HBG-AGFN_2|**11.11**|19.33|29.54|\n|HBG-AGFN_5(origin)|11.45|**14.05**|**18.47**|\n|HBG-AGFN_8|10.55|16.07|24.57|\n|HBG-AGFN_10|10.83|17.85|30.29|\n### Q5: Adaptive Weights\nWe sincerely thank the reviewer for the thoughtful suggestion regarding the use of adaptive weights in combining TB and DB losses. Motivated by this, we conducted additional experiments exploring the effect of different weighting strategies (i.e., $𝐿_{HB} = 𝐿_{TB}+ 𝜆⋅𝐿_{DB}$), including adaptive weights (i.e., 𝜆: 0.5->0, 1->0, 2->0 and so on) and fixed weights (i.e., 𝜆: 0.5->0.5, 1->1, 2->2). **The results are presented in Tables B1–B4 below.** The findings suggest that for HBG-AGFN, a fixed 1:1 weighting between TB and DB yields the best performance, while for HBG-GFACS, this fixed ratio also provides the best balance between performance with and without local search.\n### Table B1. Weights Analysis of HBG-AGFN on CVRP\n\"𝜆: 0.5→0\" refers to changing the TB:DB loss weight ratio from 1:0.5 to 1:0 during training, with the TB weight fixed at 1. The interpretation for other entries follows analogously.\n|Size/Gap%/𝜆|0.5->0|1->0|2->0|0->0.5|0->1|0->2|0.5->0.5|1->1(origin)|2->2|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|200|11.09|10.80|10.94|11.41|11.98|11.20|9.98|**9.95**|10.44|\n|500|11.27|12.04|11.18|12.15|11.66|11.80|11.63|**10.44**|11.98|\n|1000|10.89|10.61|9.89|11.03|10.84|10.98|10.87|**9.34**|10.08|\n### Table B2. Weights Analysis of HBG-AGFN on TSP\n|Size/Gap%/𝜆|0.5->0|1->0|2->0|0->0.5|0->1|0->2|0.5->0.5|1->1(origin)|2->2|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|200|10.26|10.42|10.49|11.48|11.26|10.66|**10.08**|10.45|10.36|\n|500|15.15|15.40|16.13|16.87|16.09|15.79|14.91|**14.05**|15.64|\n|1000|18.80|18.55|19.00|19.26|21.87|22.00|18.52|**18.47**|18.81|\n### Table B3. Weights Analysis of HBG-GFACS on CVRP\n|Size/Gap%/𝜆|0.5->0|1->0|2->0|0->0.5|0->1|0->2|0.5->0.5|1->1(origin)|2->2|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|200|**14.05**|19.29|17.37|17.72|18.47|19.08|16.42|16.48|18.87|\n|500|**11.78**|17.66|15.38|15.28|16.35|15.71|13.57|13.53|15.49|\n|1000|11.29|15.80|12.71|12.88 |13.47|12.80|10.91|**10.61**|12.80|\n|200(local search)|2.39|**1.78**|2.03|2.07|2.14|1.96|1.96|1.96|1.78|\n|500(local search)|3.02|**2.51**|2.91|3.41|3.44|2.99|3.17|2.81|2.62|\n|1000(local search)|2.82|**2.27**|2.82|3.31|3.53|2.75|2.45|2.75|2.40|\n### Table B4. Weights Analysis of HBG-GFACS on TSP\n|Size/Gap%/𝜆|0.5->0|1->0|2->0|0->0.5 |0->1|0->2|0.5->0.5|1->1(origin)|2->2|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|200|**19.13**|20.61|23.06|22.21|20.56|24.02|21.64|19.40|22.82|\n|500|49.51|49.61|50.80|49.48|48.47|56.13|49.62|**48.41**|50.37|\n|1000|**72.30**|80.19|90.50|79.37|80.39|96.36|77.45|75.93|87.23|\n|200(local search)|1.57|**1.49**|1.59|1.59|1.62|1.82|1.54|1.50|1.62|\n|500(local search)|4.81|**4.65**|5.02|4.88|4.73|5.18|4.73|4.68|5.12|\n|1000(local search)|7.73|7.68|7.86|7.78|7.83|8.02|7.70|**7.67**|7.99|"}, {"review_id": "AMUoijIeH7", "reviewer": "Reviewer_7ReE", "summary": "The paper proposes a novel learning-based approach for Solving Vehicle Routing problems and builds on GFlowNet based methods for finding a distribution over potential solutions. While existing approaches usually optimize towards a global trajectory constraint (Trajectory Balance), the paper extends this formulation with a local inter-state constraint called Detailed Balance. The authors claim that solely TB often shows limiting capabilities in local optimization and DB on the other hand fails on global optimization, which is an integral part of Vehicle Routing Problems. The authors propose a method that includes both optimization objectives and show improved results on standard benchmarks.", "questions": "Please comment on the weaknesses.", "limitations": "Please discuss limitation in more detail in the Appendix.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n- The overall presentation of the methodology is technical sound and the authors provide the many details of the proposed methodology.\n- The results in Table 1 indicate an improvement over the previous approaches (AGFN, GFACS).\n- The authors provide an insightful ablation study for the balancing strategies and the component contributions.\n\nWeaknesses\n\n- The Detailed Balance constraint needs to be better motivated. It is unclear why there is a problem with TB and  the local optimization objective should help for this global optimization problem. Usually an insightful example from the test data can help with that and further strengthen the story of the paper since the DB is the main contribution of the paper.\n- The authors decided to have the Related Works section in the Appendix. As a reader who is not entirely aware of this branch of research, needs to directly jump to the appendix before reading the full paper. I’d suggest shortening the introduction and the method section to have the related work section in the main paper.\n- Some in the methodology section of the paper are hard to understand, e.g. In equation 2, there is an energy term which is discussed two pages later for the first time. According to equation 9 the energy can be negative if R is larger than the average R. Is this an intended behaviour?\n- Most of the approach is adapted from previous works (Trajectory Generation, TB training) and the contribution is mainly to extend to the objective with the local DB constraint for this specific vehicle routing task. I believe that this approach could also serve for other combinatorial optimization problems.", "was_revised": true, "final_justification": "All in all, the rebuttal addressed some of my concerns and I’d increase my rating to borderline accept. I hesitate to increase the rating to accept due to W4.", "rebuttal": "We sincerely thank the reviewer for the thoughtful and constructive feedback. We are grateful for the reviewer’s kind comments on the **technical soundness** of our methodology, the **clarity and thoroughness of our presentation**, the **performance improvements** shown in Table 1 over strong baselines such as AGFN and GFACS, and the **usefulness of our ablation studies** in analyzing the effects of balancing strategies and individual components.\n\nBelow, we provide detailed responses to the questions and concerns raised.\n\n### W1: DB Motivation\n**To provide a concrete illustration**, consider a long vehicle routing trajectory constructed incrementally as\nA → B → C → D → E → ... → U → V → W → X → Y → Z.\n\nAssume this complete route yields a high total cost (bad performance), primarily due to suboptimal decisions made in the early stages, such as traversing a high-cost edge from node C to node D. In contrast, the latter portion of the tour (e.g., from node U to Z) may follow a more cost-effective and well-structured pattern.\n\nUnder Trajectory Balance (TB), the final reward is determined by the overall trajectory cost, and is proportionally assigned to all transitions. Consequently, even high-quality local transitions, such as W → X → Y, may receive weak or misleading training signals simply because they are embedded in a globally suboptimal trajectory. This would hinder the model's ability to learn and reinforce desirable local patterns.\n\nOn the other hand, Detailed Balance (DB) operates at a step-wise granularity, evaluating the expected outcomes of individual transitions. For instance, at node W, DB can assess whether transitioning to X leads to better outcomes compared to alternative choices like Z, regardless of earlier suboptimal steps. This localized and reward-sensitive feedback enables the model to more accurately learn local quality from global performance, and promotes stronger learning signals for valuable decisions even within imperfect trajectories.\n\nThis example illustrates a core limitation of Trajectory Balance (TB) in long-horizon combinatorial tasks like VRP: when the overall trajectory is suboptimal, TB lacks the ability to identify and preserve well-structured local segments within it. As a result, valuable local patterns may be overlooked or penalized. By incorporating Detailed Balance (DB) into the training objective, we address this limitation by providing fine-grained, step-level singal that helps isolate and reinforce high-quality local decisions, even when the global trajectory doesn't show good performance.\n\nWe sincerely thank the reviewer for raising this important point. **Motivated by your suggestion, we will include this example and discussion in the revised paper** to better illustrate the motivation behind integrating TB and DB. Furthermore, **as shown in Section 3.2 and Table 3, our ablation study confirms that combining TB with DB (i.e., Hybrid Balance) consistently leads to improved performance**, validating the complementary strengths of Hybrid Balance objectives.\n### W2: Related Work\nWe fully acknowledge the reviewer’s concern regarding the placement of the Related Work section in the Appendix. In the original submission, this decision was made due to strict space constraints, i.e., we prioritized providing a thorough and transparent explanation of our methodology, which we felt was critical for understanding the technical contributions. However, **we are open to the suggestion and sincerely thank the reviewer for raising this point**, i.e., having the Related Work in the main body could greatly benefit readers, especially those less familiar with the research area.\n### W3: Equation\nWe sincerely thank the reviewer for this helpful comment. We hadn’t realized that the explanation of the energy term appears nearly two pages after its introduction in Equation 2, and we truly appreciate the reviewer for pointing this out. In the revised version, we will move the explanation closer to Equation 2 to improve clarity and make the flow of the methodology easier to follow.\n\nRegarding the second point about whether the energy can be negative, we appreciate the opportunity to clarify this. Yes, this is indeed intended behavior. As is common in VRP literature such as POMO, GFACS, and AGFN, the energy is defined relative to a baseline (e.g., average reward) and can take negative values. Moreover, the energy in Equation 9 appears in the denominator of the loss function (Equation 2), and a negative energy results in a smaller exponentiated value in the denominator, which leads to a higher loss, which penalizes relatively poor trajectories. We will clarify this behavior of the energy term more explicitly in the revised manuscript.\n### W4: Contribution and Extention\nWe thank the reviewer for the thoughtful comment. To the best of our knowledge, **this work is the first to introduce the DB objective into vehicle routing problem (VRP), and the first to integrate TB and DB objectives within a unified GFlowNet framework**. Achieving this integration is non-trivial, as it requires reconciling two fundamentally different types of training signals: global trajectory-level feedback from TB and localized stepwise credit assignment from DB. At the same time, it is necessary to ensure that the forward and backward dynamics remain consistent throughout training. This carefully unified design allows our method to effectively leverage both global and local learning signals, leading to improved training stability and performance across various VRP settings. To achieve this integration: \n* Leveraging the hybrid structure of VRP whose solution is comprised of multi-node and single-node sub-tours, we derive a general recurrence formulation (Eq. 4) for counting trajectory orders. This formulation serves as the mathematical foundation for integrating TB and DB in a consistent manner.\n* From this recurrence, we analytically derive a set of twelve equations (Eq. 13–24 in Appendix), which lead to the expressions for the backward probability of TB (Eq. 6) and DB (Eq. 7) within a consistent framework.\n* We also define forward probability composition (Eq. 3), where DB serves as the building block for TB, maintaining coherence throughout trajectory construction.\n* To unify flow representations, we compute DB flow from state embeddings and TB flow from final trajectories, interpreting DB flow as an intermediate form of TB flow.\n* Finally, based on hybrid balance, we derive an important structural property: only the depot node has multiple feasible predecessors, while customer nodes have unique ones. This motivates our Depot-Guided Inference, a targeted module that strengthens backward modeling and trajectory quality.\n\nRegarding the **potential for generalization to other combinatorial optimization (CO) problems**, we agree that our approach holds strong promise beyond VRP. In fact, many existing neural methods in the CO literature such as AGFN, begin with a focus on VRP, precisely because VRP presents a particularly challenging testbed due to its complex structure and rich constraints. Successfully addressing VRP often serves as a strong indication of a method’s scalability and robustness. Building on this foundation, we plan to extend our GED framework to other CO problems such as the Maximum Independent Set (MIS), the Knapsack Problem (KP) and Graph Coloring, which generally involve simpler or fewer constraints compared to VRP. Given the modularity of our framework and its basis in general GFlowNet principles, we are confident in its adaptability and effectiveness across a broader class of combinatorial optimization tasks."}, {"review_id": "wqKbJWjxQQ", "reviewer": "Reviewer_hUYS", "summary": "This paper introduces the Hybrid-Balance GFlowNet (HBG) framework aimed at improving GFlowNet-based solvers for vehicle routing problems (VRPs). HBG combines trajectory balance (TB) and detailed balance (DB) objectives in a principled, adaptive manner to unify global and local optimization perspectives. The authors design a depot-guided inference scheme tailored for VRPs with a depot structure (e.g., CVRP), and rigorously evaluate the framework by integrating HBG into two state-of-the-art GFlowNet-based solvers: AGFN and GFACS. Experimental results demonstrate significant and consistent improvements in solution quality and generalizability.", "questions": "see my comments in the Strengths And Weaknesses section", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strength\n- The integration of TB and DB provides a unified approach bridging the gap between local and global optimization for GFlowNets in combinatorial domains. The formalization of DB within VRP, particularly the explicit recurrence  and probability derivation, is a notable theoretical advancement.\n- The main development, including Algorithmic design, mathematical derivations, and the final composite loss function, is clearly presented.\n- Empirical improvements are substantial and consistent, with ablation studies confirming the contribution of each module. The improvements persist for TSP, underlining generalizability. The evaluation of depot-guided inference variants is carefully done and matches the method’s claimed benefits.\n\n## Weakness\n- The necessity of considering  local optimization signals is not well-motivated. In particular, why we also need to pursue local optimization given a global optimization objective? Will the local optimization signals bias the pursuit of global optimum? What does \"fine-grained local structure\" refer to?\n- It is noteworthy that the depot-guided inference strategy only applies to depot-centric problems like CVRP. For problems without clear depot structures (like TSP), the method falls back to original approaches.\n- The performance could be constrained by the quality of the base GFlowNet solvers.", "was_revised": true, "final_justification": "The authors' rebuttal addressed my concerns. I therefore maintained my score.", "rebuttal": "We sincerely thank the reviewer for the thoughtful and encouraging feedback. We truly appreciate your kind comment of our **theoretical contributions**, including the formalization of DB in VRP and the unified integration of TB and DB. We're also grateful for your positive comments on the **clarity of our design and analysis**, as well as the **empirical improvements and careful ablation studies**.\n\nBelow, we provide detailed responses to the questions and suggestions you kindly raised.\n\n### W1: DB Motivation and Term Explanation\nWe sincerely thank the reviewer for raising this important question. The necessity of incorporating local optimization signals arises from a core limitation of relying solely on global feedback. Trajectory Balance (TB), while effective in guiding overall optimization, assigns credit based on the full trajectory. This can misrepresent the contribution of locally good decisions when the overall solution is not good.\n\nTo illustrate this concretely, consider a long vehicle routing trajectory constructed incrementally as\nA → B → C → D → E → ... → U → V → W → X → Y → Z.\nAssume the overall route has a high cost (bad performance) due to early suboptimal choices like traversing a high-cost edge from C to D. However, the later segment (e.g., U to Z) may be well-structured and efficient. Under TB, the reward signal derived from the final cost is spread across the entire trajectory. As a result, good transitions like W → X → Y may receive low or misleading credit as the overall result is not good, hindering the model from reinforcing these useful local patterns.\n\nIn contrast, Detailed Balance (DB) operates at a step-wise level, comparing local alternatives directly. For example, at node W, DB can determine that choosing X instead of alternative choices like Z leads to better outcomes, which is independent of early errors. This enables the model to recognize and reinforce high-quality decisions even within imperfect global solutions.\n\nImportantly, adding DB does not bias the model away from global optimization—rather, it complements TB by supplying more granular learning signals. As validated in our ablation study (Section 3.2, Table 3), the hybrid use of TB and DB consistently improves performance over using either objective alone.\n\nMoreover, the term “**fine-grained local structure**” refers to the localized reward relationships between a given state and its immediate successor, which captures beneficial sub-patterns within a trajectory, such as short, efficient sub-routes or cost-effective transitions. These local structures often contribute meaningfully to overall solution quality but may be overlooked or undervalued when using a purely trajectory-level objective like TB. By introducing DB, the model gains the capability to identify and reinforce these fine-grained decisions during training. While the concept of “fine-grained local structure” is implicitely mentioned in Lines 40–41 of the paper, we will revise the text to make it more explicit and accessible.\n\nMotivated by your insightful suggestion, we will incorporate this example and discussion into the main paper to better clarify the motivation behind our hybrid design.\n\n### W2: Depot-Guided Inference\n\nThe reviewer is correct on this point, the Depot-Guided Inference strategy is specifically tailored for depot-centric problems such as CVRP. While we briefly acknowledged this in Lines 54–58, 66–67, and 233–236 of the manuscript, we appreciate the opportunity to clarify further. In practice, a large number of VRP variants including capacitated VRP, multi-depot VRP, and VRP with time windows, are inherently structured around depots. Therefore, despite its limited applicability to non-depot problems like TSP, we believe the proposed strategy remains broadly relevant and useful for a wide range of real-world routing scenarios. And the results in Table 5 shows that even in the depot-free scenatios like TSP, our overall hybrid balance framework without Depot-Guided Inference can still improve the performance.\n\n### W3: Constrains of GFlowNet Solvers\n\nAs acknowledged by the reviewer, the performance of our framework could indeed be constrained by the quality of the underlying GFlowNet solvers. This limitation is explicitly noted in the Conclusion (Lines 316–317) of our manuscript. However, our method is designed to be general and has demonstrated its ability to enhance different types of GFlowNet-based backbones, such as GFACS (which learns to search) and AGFN (which learns to construct). We believe it remain applicable for improving future stronger GFlowNet backbone as well."}, {"review_id": "UcFG1Mtypb", "reviewer": "Reviewer_3uAQ", "summary": "The paper discusses 2 different methods for gflownet that are limited, Trajectory Balance (TB) objective effectively aligns with global metrics of VRP and TSP like minimizing total travel distance. However, this exclusive focus on global optimization can lead to the neglect of important local optimization signals.  On the other hand, Detailed Balance (DB) [4] offers a mechanism better suited for local optimization. Nevertheless, using DB alone is equally inadequate, as VRPs fundamentally require a global perspective to achieve optimal solutions. For this reason they propose Hybrid-Balance principle, combining TB and DB in a unified and extensible manner, can significantly enhance GFlowNet-based methods for VRPs.", "questions": "1. The term \"adaptive\" is used to describe the integration of TB and DB, yet Equation 11 shows a fixed, unweighted sum. Could you clarify what aspect of the integration is adaptive? Have you experimented with a weighted sum, lTB​+λ⋅lDB​, and if so, how sensitive is the performance to the hyperparameter λ?\n\n2. The energy in Equation 9 is based on the reward relative to the batch average. What is the intuition behind this choice versus a more direct energy function", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. Conceptually Sound and Well-Motivated: The central premise of the paper—that VRPs benefit from both global and local optimization—is highly intuitive and well-articulated. The authors clearly explain the complementary strengths and individual weaknesses of Trajectory Balance (global) and Detailed Balance (local), providing a strong motivation for their hybrid approach. \n\n2. Novel Theoretical Contribution: The paper's most significant strength lies in its formalization of Detailed Balance for VRPs. The derivation of the backward transition probability,  is non-trivial. The authors provide a combinatorial argument (Statements 1, 2, and 3) to derive a closed-form expression for the number of trajectory orderings, which then informs the backward probability at the depot.\n\n3. Comprehensive and Rigorous Evaluation: The experimental setup is thorough. By integrating HBG into two distinct GFlowNet-based solvers—an end-to-end construction method (AGFN) and a hybrid heuristic search method (GFACS)—the authors demonstrate the general applicability of their framework. The evaluation across two different problems (CVRP and TSP) and multiple scales (up to 1000 nodes) further strengthens the claims of robustness and scalability.\n\nWeaknesses\n\nMy main concerns with this paper are the claimed \"adaptiveness\" of the hybrid balance, the practical significance of some of the performance gains, and the potential overstatement of novelty regarding the inference strategy.\n\n1. \"Hybrid-Balance\" is a Simple, Static Summation: The paper claims to integrate TB and DB in a \"principled and adaptive manner\". However, the final loss function in Equation 11 is a simple, unweighted sum: LossHB​=LossTB​+LossDB​. This is the most straightforward, non-adaptive way to combine two losses. There is no adaptive mechanism described that would, for example, change the weighting between LossTB​ and LossDB​ during training or based on the problem instance. This makes the term \"adaptive\" misleading. A simple summation might not be optimal, and this lack of exploration into the balance mechanism is a significant weakness.\n\n2. Marginal Performance Gains in Some Key Scenarios: While the improvements are consistent, their magnitude is questionable in some cases. For the end-to-end AGFN model on CVRP1000, the objective value improves from 133.97 to 131.78, a gain of only ~1.6%.\n\n3. Fairness of Hyperparameter Tuning: The authors state they \"adopt the same model configurations and training settings as AGFN and GFACS\". However, the introduction of a new loss component (lDB​) fundamentally changes the optimization landscape. It is highly likely that the optimal hyperparameters (e.g., learning rate, optimizer settings) for the HBG models would be different from the original models. Without re-tuning, the comparison might unfairly handicap the proposed HBG models, or conversely, the original models might have been better tuned for their specific loss. The paper provides no information on whether such re-tuning was performed.", "was_revised": true, "final_justification": "I maintain my evaluation that the paper should be accepted.", "rebuttal": "We sincerely thank the reviewer for the thoughtful and encouraging feedback. We greatly appreciate the kind comment of the **conceptual motivation**, the **theoretical contribution** of Detailed Balance in VRP, and the **thoroughness of our experimental design** across diverse solvers and problem scales. Below, we respond to the concerns you raised.\n### W1 Q1: Weight 𝜆\nWe sincerely thank the reviewer for this insightful comment and for pointing out the potential ambiguity in our use of the term \"adaptive\". **Our original intention was to emphasize the unified and structurally integration of TB and DB within a consistent probabilistic framework.** We appreciate the reviewer’s suggestion and will revise the manuscript accordingly to clarify this point and avoid any possible misunderstanding.\n\nWe also appreciate the reviewer’s concern regarding a weighted combination (i.e., 𝐿_{HB} = 𝐿_{TB}+ 𝜆⋅𝐿_{DB}). In response, **we have conducted additional experiments to assess the sensitivity of our method to different values of 𝜆, which are gathered in Tables B1–B4 below.** The results include adaptive weights (i.e., 𝜆: 0.5->0, 1->0, 2->0 and so on) and fixed weights (i.e., 𝜆: 0.5->0.5, 1->1, 2->2). We find that, for HBG-AGFN, a fixed 1:1 weight between TB and DB consistently yields the best performance. Similarly, for HBG-GFACS, this ratio offers the most favorable trade-off between performance with and without local search.\n### Table B1. Weights Analysis of HBG-AGFN on CVRP\n\"𝜆: 0.5→0\" refers to changing the TB:DB loss weight ratio from 1:0.5 to 1:0 during training, with the TB weight fixed at 1. The interpretation for other entries follows analogously. The term \"origin\" denotes the original hyperparameter setting used in our main experiments.\n|Size/Gap%/𝜆|0.5->0|1->0|2->0|0->0.5|0->1|0->2|0.5->0.5|1->1(origin)|2->2|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|200|11.09|10.80|10.94|11.41|11.98|11.20|9.98|**9.95**|10.44|\n|500|11.27|12.04|11.18|12.15|11.66|11.80|11.63|**10.44**|11.98|\n|1000|10.89|10.61|9.89|11.03|10.84|10.98|10.87|**9.34**|10.08|\n### Table B2. Weights Analysis of HBG-AGFN on TSP\n|Size/Gap%/𝜆|0.5->0|1->0|2->0|0->0.5|0->1|0->2|0.5->0.5|1->1(origin)|2->2|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|200|10.26|10.42|10.49|11.48|11.26|10.66|**10.08**|10.45|10.36|\n|500|15.15|15.40|16.13|16.87|16.09|15.79|14.91|**14.05**|15.64|\n|1000|18.80|18.55|19.00|19.26|21.87|22.00|18.52|**18.47**|18.81|\n### Table B3. Weights Analysis of HBG-GFACS on CVRP\n|Size/Gap%/𝜆|0.5->0|1->0|2->0|0->0.5|0->1|0->2|0.5->0.5|1->1(origin)|2->2|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|200|**14.05**|19.29|17.37|17.72|18.47|19.08|16.42|16.48|18.87|\n|500|**11.78**|17.66|15.38|15.28|16.35|15.71|13.57|13.53|15.49|\n|1000|11.29|15.80|12.71|12.88 |13.47|12.80|10.91|**10.61**|12.80|\n|200(local search)|2.39|**1.78**|2.03|2.07|2.14|1.96|1.96|1.96|1.78|\n|500(local search)|3.02|**2.51**|2.91|3.41|3.44|2.99|3.17|2.81|2.62|\n|1000(local search)|2.82|**2.27**|2.82|3.31|3.53|2.75|2.45|2.75|2.40|\n### Table B4. Weights Analysis of HBG-GFACS on TSP\n|Size/Gap%/𝜆|0.5->0|1->0|2->0|0->0.5 |0->1|0->2|0.5->0.5|1->1(origin)|2->2|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|200|**19.13**|20.61|23.06|22.21|20.56|24.02|21.64|19.40|22.82|\n|500|49.51|49.61|50.80|49.48|48.47|56.13|49.62|**48.41**|50.37|\n|1000|**72.30**|80.19|90.50|79.37|80.39|96.36|77.45|75.93|87.23|\n|200(local search)|1.57|**1.49**|1.59|1.59|1.62|1.82|1.54|1.50|1.62|\n|500(local search)|4.81|**4.65**|5.02|4.88|4.73|5.18|4.73|4.68|5.12|\n|1000(local search)|7.73|7.68|7.86|7.78|7.83|8.02|7.70|**7.67**|7.99|\n### W2: Improvement on 1000 Node CVRP Instances\nWe sincerely thank the reviewer for raising the concern. While the improvement on CVRP1000 under AGFN may appear modest (~1.6%) in absolute terms, we would like to note that this result is obtained on the challenging large-scale instance involving 1000 nodes, where even small percentage gains are non-trivial due to the high combinatorial complexity of the problem. More importantly, we observe consistent improvements across a wide range of problem sizes, solver backbones (AGFN and GFACS), and problem types (CVRP and TSP). We believe this consistency highlights the robustness and broad applicability of our proposed approach.\n### W3: Re-tuning\nWe sincerely thank the reviewer for this valuable suggestion. The reviewer is absolutely right that the introduction of a new loss component (𝐿_{DB}) could potentially alter the optimization landscape, and that the original hyperparameter settings used in AGFN and GFACS may not be optimal for the proposed HBG variants.\n\nOur initial motivation for adopting the same configurations was to ensure a fair comparison under consistent settings. However, **inspired by the reviewer’s insightful comment, we have conducted additional experiments in which we re-tuned key hyperparameters for the HBG models**, including the sparsity parameter, learning rate, and optimizer settings. The updated results (Table A1, C, D) will be incorporated into the Appendix of the revised version. \n\nAs the sparsity parameter results shown in Table A1, the original sparsity setting yields the best performance for both HBG-GFACS and HBG-AGFN. Regarding the learning rate comparisons in Table C, for HBG-GFACS, the original value of $5×10^{−4}$ performs best without local search, while a value of $1×10^{−3}$ achieves the best results when local search is enabled. For HBG-AGFN, a learning rate of $1×10^{−4}$ shows superior performance on the 200- and 500-node instances, whereas the original value performs best on the 1000-node instances. As for the optimizer comparison in Table D, the original AdamW setting provides the best performance in most cases. An exception is observed on the 500- and 1000-node instance with local search, where Adam slightly outperforms AdamW for HBG-GFACS.\n### Table A1. Comparison of Various Sparse Parameter k on CVRP\nHBG-GFACS_2 refers to the HBG-GFACS model evaluated with k=|V|/2; the interpretation is analogous for the other entries. The term \"origin\" denotes the original hyperparameter setting used in our main experiments.\n|CVRP(Gap%)|200|500|1000|\n|:-:|:-:|:-:|:-:|\n|HBG-GFACS_2|19.26|16.27|12.69|\n|HBG-GFACS_5(origin)|**16.48**|**13.53**|**10.61**|\n|HBG-GFACS_8|17.90|13.83|11.02|\n|HBG-GFACS_10|20.43|17.88|14.9|\n|HBG-GFACS(local search)_2|2.13|3.41|3.46|\n|HBG-GFACS(local search)_5(origin)|**1.96**|**2.81**|**2.75**|\n|HBG-GFACS(local search)_8|2.13|3.36|3.51|\n|HBG-GFACS(local search)_10|3.07|4.03|4.77|\n|HBG-AGFN_2|12.62|13.36|14.78|\n|HBG-AGFN_5(origin)|**9.95**|**10.44**|**9.34**|\n|HBG-AGFN_8|11.55|13.27|12.69|\n|HBG-AGFN_10|12.98|14.5|14.06|\n### Table C. Comparison of Various Learning Rate on CVRP\nHBG-GFACS_$5×10^{-3}$ refers to the HBG-GFACS model evaluated with learning rate of $5×10^{-3}$; the interpretation is analogous for the other entries.\n|CVRP(Gap%)|200|500|1000|\n|:-:|:-:|:-:|:-:|\n|HBG_GFACS_$5×10^{-3}$|17.15|14.48|11.77|\n|HBG_GFACS_$1×10^{-3}$|17.04|14.37|11.50|\n|HBG_GFACS_$5×10^{-4}$(origin)|**16.48**|**13.53**|**10.61**|\n|HBG_GFACS_$1×10^{-4}$|18.22|14.19| 11.30|\n|HBG_GFACS(local search)_$5×10^{-3}$|1.71|2.77|2.63|\n|HBG_GFACS(local search)_$1×10^{-3}$|**1.70**|**2.65**|**2.51**|\n|HBG_GFACS(local search)_$5×10^{-4}$(origin)|1.96|2.81|2.75|\n|HBG_GFACS(local search)_$1×10^{-4}$|4.53|6.49|6.50|\n|HBG_AGFN_$5×10^{-3}$|11.41|14.46|12.00|\n|HBG_AGFN_$1×10^{-3}$|10.48|11.92|10.62|\n|HBG_AGFN_$5×10^{-4}$ (origin)|9.95|10.44|**9.34**|\n|HBG_AGFN_$1×10^{-4}$|**9.37**|**10.27**|9.59|\n### Table D. Comparison of Various Optimizer on CVRP\nHBG-GFACS_SGD refers to the HBG-GFACS model evaluated with SGD optimizer; the interpretation is analogous for the other entries.\n|CVRP(Gap%)|200|500|1000|\n|:-:|:-:|:-:|:-:|\n|HBG_GFACS_SGD|17.80|15.19|12.45|\n|HBG_GFACS_Adam|17.33|14.28|11.11|\n|HBG_GFACS_Adamw(origin)|**16.48**|**13.53**|**10.61**|\n|HBG_GFACS(local search)_SGD|3.03|4.26|4.55|\n|HBG_GFACS(local search)_Adam|2.03|**2.70**| **2.73**|\n| HBG_GFACS(local search)_Adamw(origin) | **1.96**  |   2.81    | 2.75|\n|HBG_AGFN_SGD|14.66|13.00|10.84|\n|HBG_AGFN_Adam|10.12|12.86|11.17|\n|HBG_AGFN_Adamw(origin)|**9.95**|**10.44**|**9.34**|\n\n### Q2: Reward Function\nWe sincerely thank the reviewer for this thoughtful question. The use of reward relative to the batch average in Equation 9 is a common practice in the VRP literature, particularly in learning-based methods like POMO, AGFN, and GFACS. The key motivation behind this choice is to mitigate the effect of node distance discrepancies across different instances, thereby promoting training stability.\n\nFor example, different instances often exhibit varying step-wise reward magnitudes due to differences in route length, customer density, or total demand. As a result, the average reward per decision step can differ between instances. If we directly use these raw per-step rewards to compute energy values, instances with smaller average step-wise rewards would inherently yield more favorable energy values, even for suboptimal decisions. In contrast, instances with larger average per-step rewards might assign worse energy values even to relatively good decisions within that instance. This imbalance can distort the learning signal, causing the model to undervalue high-quality decisions in instances with larger average per-step rewards, while overvaluing mediocre decisions in smaller ones.\n\nBy using reward values relative to the batch average, we normalize this effect and encourage the model to compare solutions fairly within the context of each instance. This stabilizes training and helps the model focus on learning to generate relatively good solutions across diverse instances, instead of simply favoring small step-wise rewards in absolute terms."}]

Author rebuttal:

Meta-review: This paper proposes Hybrid-Balance GFlowNet (HBG), which unifies Trajectory Balance (TB) and Detailed Balance (DB) into a single framework to jointly address global and local optimization in VRPs. While prior methods relied heavily on TB and often failed to capture local structural signals, this work introduces DB into the VRP domain for the first time and integrates it consistently with TB. The framework also incorporates a depot-guided inference strategy, which proves effective in depot-centric problems such as CVRP, while still yielding improvements for TSP.

The empirical evaluation is thorough: HBG is integrated into two distinct solvers, AGFN and GFACS, and demonstrates consistent performance improvements across multiple benchmarks. Detailed ablation studies and comparisons of weighting strategies further validate the effectiveness of the approach. While some reviewers raised concerns about the use of the term “adaptive” and the generality of the method, the authors provided substantial clarifications and additional experiments, which resolved the main issues.

Overall, the paper offers both theoretical novelty and practical performance gains. It makes a solid and well-validated contribution that is suitable for NeurIPS.
Decision: Accept (spotlight)