LMask: Learn to Solve Constrained Routing Problems with Lazy Masking
Authors: Tianyou Li
Haijun Zou
JIAYUAN WU
Zaiwen Wen
Venue: ICLR 2026 Poster (2026)
Keywords: Neural Combinatorial Optimization
Routing Problem
Deep Learning
Primary area: optimization

Abstract: Routing problems are canonical combinatorial optimization tasks with wide-ranging applications in logistics, transportation, and supply chain management. However, solving these problems becomes significantly more challenging when complex constraints are involved. In this paper, we propose LMask, a novel learning framework that utilizes dynamic masking to generate high-quality feasible solutions for constrained routing problems. LMask introduces the LazyMask decoding method, which lazily refines feasibility masks with the backtracking mechanism. In addition, it employs the refinement intensity embedding to encode the search trace into the model, mitigating representation ambiguities induced by backtracking. To further reduce sampling cost, LMask sets a backtracking budget during decoding, while constraint violations are penalized in the loss function during training to counteract infeasibility caused by this budget. We provide theoretical guarantees for the validity and probabilistic optimality of our approach. Extensive experiments on the traveling salesman problem with time windows (TSPTW) and TSP with draft limits (TSPDL) demonstrate that LMask achieves state-of-the-art feasibility rates and solution quality, outperforming existing neural methods.

Published as a conference paper at ICLR 2026
LMASK: LEARN TO SOLVE CONSTRAINED ROUTING PROBLEMS
Tianyou Li Haijun Zou
Jiayuan Wu Zaiwen Wen
1 Beijing International Center for Mathematical Research, Peking University, China 2 PAcademy of Mathematics and Systems Science, Chinese Academy of Sciences, China 3 *Deaarmeent of Statistics and Data Science, University of Pennsylvania, United States
ABSTRACT
Routing problems are canonical combinatorial optimization tasks with wide- ranging applications in logistics, transportation, and supply chain management. However, solving these problems becomes significantly more challenging when complex constraints are involved. In this paper, we propose LMask, novel learning framework that utilizes dynamic masking to generate high-quality feasible solu- tions for constrained routing problems. LMask introduces the LazyMask decoding method, which lazily refines feasibility masks with the backtracking mechanism. In addition, it employs the refinement intensity embedding to encode the search trace into the model, mitigating representation ambiguities induced by backtracking. To further reduce sampling cost, I.Mask sets a backtracking budget during decoding, while constraint violations are penalized in the loss function during training counteract infeasibility caused by this budget. We provide theoretical guarantees for the validity and probabilistic optimality of our approach. Extensive experiments on the traveling salesman problem with time windows (TSPTW) and TSP with draft limits (TSPDL) demonstrate that LMask achieves late-of-theean feasibility rates and solution quality, outperforming existing neural methods.
INTRODUCTION
Routing problems form fundamental class of combinatorial optimization (CO) problems, encom- passing the traveling salesman problem (TSP), vehicle routing problem (VRP), and their numerous variants. These problems frequently arise in practical domains such logistics (Konstantakopoulos et al., 2022), transportation (Díaz- et al., 2014), and supply chain management Duan et al. (2020), where the objective is to determine optimal routes while satisfying a variety of constraints, such as vehicle capacities, draft limits, time windows, or precedence requirements. The presence of these constraints significantly increases the problem complexity, as they must all be considered when optimizing the distance, time, or transport cost. Integer linear programming (ILP) provides rigorous framework for modeling routing problems while incorporating constraints explicitly (Dantzig et al., 1954; Dantzig & Ramser, 1959). It guarantees optimal solutions under feasible conditions; however, as the number and complexity of constraints grow, the computational cost of solving ILP models in- creases exponentially. This makes ILP computationally intractable especially for large-scale instances with complex constraints (Cook, 2015).
To address the computational challenges posed by complex constraints, heuristic methods monly adopted. These methods efficiently generate high-quality solutions using approximations and relaxation strategies handle constraints. Prominent heuristic approaches, such the Lin-Keengghan- Helsgaun (LKH) heuristic (Helsgaun, 2017), fast iterated local optimization (Accorsi & Vigo, 2021), 1), and hybrid genetic search (Vidal, 2022; Wouda et al., 2024), have demonstrated effectiveness across various constrained routing problem variants. Nonetheless, applying these heuristics often requires significant attention constraint modeling, algorithm customization, and parameter tuning. This
"Equal contribution, alphabetical order Corresponding author (email: wenzw@pku.edu.com

---

Published as a conference paper at ICLR 2026
highlights the necessity for expert knowledge to adapt methods for specific problem settings, as well as the complexity of constraint handling in CO problems.
In recent years, machine learning for CO approaches have been developed to tackle the difficulty in solving CO problems. Neural constructive solvers are learning- based methods designed to construct complete route by adding node to the current partial route sequentially. Early works introduce the pointer network to generate the optimal solution to TSP (Vinyals et al., 2015; Bello et al., 2017) and VRP (Nazari et al., 2018) in an auto-regressive way. The attention-based model (AM) (Kool et al., 2018) is a fundamental work in this line of research, which adopts a transformer-based model architecture. Building on AM, many subsequent innovations, including dynamic embedding (Peng et al., 2020; Luo et al., 2023), symmetry utilization (Kwon et al., 2020; Kim et al., 2022) and posterior search (Hottung et al., 2022; Choo al., 2022), have been proposed to facilitate the performance. Their decoders, utilizing attention mechanisms, generate the solution incrementally by selecting nodes in an auto-regressive manner. Masking techniques are adopted to exclude nodes that do not satisfy the constraints. Additionally, there are several works studying foundation models for VRPs, such as MVMoE (Zhou et al., 2024), Routefinder (Berto et al., 2024) and CaDA (Li et al., 2024).
Most neural methods for routing problems handle constraints by employing the masking mechanism, which excludes actions directly leading to infeasible solutions during construction (Kool et al., 2018; Huang et al., 2025; Kwon et al., 2020; Joshi et al., 2019; Luo et al., 2023). This sequential construction is valid due to the property of tail recursion: after applying series of construction steps, the remaining tail subproblem becomes a smaller instance of the original CO problem, as discussed in (Drakulic et al., 2023). The construction process implicitly assumes that the tail subproblem is always feasible. This property is present in ordinary routing problems, allowing feasible solutions to be generated node by node. However, for route problems with complex constraints, feasibility issues pose a major challenge during the sequential generation process. To tackle the feasibility difficulty, recent neural approaches have developed diverse strategies. Kool et al. (2022) propose DPDP, which combines learned neural heuristics with dynamic programming algorithms to handle hard constraints. Ma et al. (2023) present the neural k-opt solver for TSP and CVRP, which learns the search process with feasibility-relatee develop multi-step look-ahead method tailored for TSPTW, incorporating problem-specifii features and a large supervised learning dataset. Bi et al. (2024) propose a proactive infeasibility prevention (PIP) framework based preventative infeasibility (PI) masking, learnable decoders, and adaptive strategies to advance neural methods.
features and guided infcasible region exploration scheme. Chen et al. (2024)
In the previous learning methods, the one-pass forward sequence construction framework (Kool et al., 2018; Kwon et al., 2020; Luo et al., 2023; Bi et al., 2024) limits the model's ss ability to handle complex constraints. This auto-regressive approach builds a solution step-by-step in irreversible manner, where each action is based solely on the partial solution generated so far. Although lookahead strategies attempt mitigate the inflexibility by exploring the following feasible actions, they are computationally expensive with no guarantee of finding feasible solution. Furthermore, to enforce these constraints during generation, such methods heavily rely on a masking mechanism that lacks systematic mathematical explanation. This motivates us to develop more effective constructive framework with distinct decoding method, enabling learning over more general constraints in routing problems. Therefore, we develop a novel learning framework, called LMMsk, to handle the feasibility issue in solving routing problems with complex constraints. It explains how machine learning can solve NP-hard problems in an end-to-end manner, offering theoretically guaranteed approach to generating feasible solutions. The name LMask on one hand represents the "LazyMask" decoding algorithm, and on the other hand signifies using the "mask" refinement mechanism to "leam" the routing problems with complex constraints. The overall LMask framework is illustrated in Figure I at the end of Section 3. Our main contributions are summarized as follows.
1) Mechanism innovation. We propose the Lasy decoding algorithm, which lazily updates feasibility masks through the backtracking mechanism, enabling efficient generation of feasible solutions with theoretical guarantees. To mitigate representation ambiguities, the refinement intensity embedding is further employed to integrate information about the search trace into our model.
2) Theoretical guarantee. We present systematic explanation of the masking mechanism's 's role in routing problems, which fundamentally guides the design of the LMask framework. Based on our mathematical derivation, rigorous theoretical guarantees demonstrate the validity of the LazyMask algorithm and the effectivity of MMskk's probabilistic model with entropy regularization.
2

---

Published as a conference paper at ICLR 2026
3) Experimental outperformance. Comprehensive experiments TSPTW and TSPDL demonstrate that LMask achieves significantly higher solution feasibility and smaller objective gaps than other neural constructive methods with comparable runtime, showing state-of-the-art performance. Notably, a nearly 0.0% infeasibility rate observed for LMask on synthetic TSPTW datasets, highlighting its effectiveness in handling complex constraints.
PRELIMINARIES FOR ROUTING PROBLEMS
2.1 UNIFIED FORMULATION
In the context of end-to-end learning, we typically do not use mixed-integer programming for modeling routing problems due to its high computational complexity. Instead, we consider a unified formulation of routing problems. Let := {0, 1,...,,)), denote the set of nodes and == VT represent the sequence space containing all possible routes of length T. The length T is always n + 1 when a routing problem requires each node be visited exactly once. A wide range of routing problems can be expressed using the following formulation:
min =en
f(T: s.t. c(TT; P) S d(TT; P) 0,
(1)
where P represents the problem instance, <(T;; P) and d(:;; P)) represent the hard constraints imposed on the route x. d(T;; P) can be the visit constraints that each node exactly visited once. c(T;; P) < 0 can represent time window constraints, draft limit constraints, etc. More details of the formulation are shown Appendix
2.2 A DISTRIBUTION APPROXIMATION VIEW
In this section, we provide a novel view from the perspective of distribution approximation to solve problem (1). Let II be the optimal solution set and f* be the optimal objective value for a given instance P. The search for optimal solutions can be framed as identifying the target distribution:
π E
g" (m; P) = I (T)
E TT*
Since the optimal solutions cannot be determined in advance, the target distribution is computationally inaccessible. However, can be approximated by a family of constrained Gibbs distributions:
[(T; (*) 1c(#),
cx(=; P) = Zx
exp
A
where C ;= f ci P) < 0, 0,d(T::P) 0} is the feasible set of problem (1) and Z^ == fr Erec exp (f (P))/A). is also known an energy-basee based model and has profound impact in deep learning (LeCun et al., 2006; Song & Kingma, 2021). It can be readily verified that (x P) > 4 (<; P) + 0, which means optimal solutions can be identified by sampling from constrained Gibbs distribution ęΛ with sufficiently small X.
As an alternative to directly sampling from the Gibbs distribution, constructing a parameterized distribution Pa is often considered more efficient to sample feasible route. This approach is adopted variational annealing methods (Hibat-Allah et al., 2021; Sanokowski et al., 2023; Chen al., 2023). We can construct auto-regressive distribution that generates route in node-by-node manner. Given a problem instance P, the policy for generating a solution π of length can be decomposed as:
T
pa( P)
II po(Teti|TT:: P),
(2)
where Po represents an auto-regressive neural network (Sutskever et al., 2014; Bahdanau et al., 2015; Vaswani et al., 2017) predict the next element based on all preceding elements.
Let P(x) and Qxx) represent two probability distributions such that their supports satisfy supp(P) S
Sup The Kullback-Leibler (KI.) divergence from Q to P is defined as KT[(P (Q)
3

---

Published as a conference paper at ICLR 2026
In our framework, to reduce the discrepancy between the policy distribution ps and the Gibbs distribution qx minimize their KL divergence
P(ar) Eg-r(() log Q(x))
1 KL(polle qx) = Eps [log Pol + X - [f(T; P)] - log Z1 (P).
(3)
Then, eliminating 0-independent terms (log Zx (P)) and A-scaling in (3) yields the loss function
L(e; P) = pp (=; P)] + po (og (o P)],
which contains the expectation of f(T;; P) over ps for concentration on lower function values and an entropy regularizer for encouraging exploration.
METHODOLOOGY
3.1
CONSTRAINED AUTO-REGRESSIVE MODEL
Due to the complex constraints of the routing problem, infeasible solutions need to be excluded in the auto-regressive model. Transformer-based models for routing problems (Kool al., 2018; Luo et al., 2023; Kwon et al., 2020) utilize masking techniques avoid infeasible solutions. However, the effec- tiveness of these techniques relies on the routing problem's 's constraint structure. For problems with highly complex constraints, generating feasible solutions is challenging, detailed in Appendix A.
To address this, we leverage the constraint structure of problem (I). Specifically, when constructing po, must ensure that the probability of any solution æ violating the constraints is zero. This can be achieved by incorporating the indicator function 1 for the feasible set C. The conditional probability po( m P). represented by the neural network, should explicitly exclude infeasible actions. To formalize this, we introduce the potential set ((T1a), defined as:
S(Taa) {m++1: BT41I E V [TId, Te41.1 E C),
which further induces the mask function 1 ss) (Te+1). Based this formulation, the conditional probability in (2) parameterized by the neural network takes the form:
(do(se-1(m:si))) ( Po 1 P) Σx e (k))
where do P) is produced by all intermediate layers. The rego-segeessvve model pe can produce feasible solutions step-by-step, forming the foundation for solving general routing problems.
3.2 LAZYMASK ALGORITIIM
Most neural methods for routing problems involve handling constraints through masking mechanisms, which dynamically excludes actions that would lead to infeasible solutions during the construction. However, S(T..z) is sometimes computationally inaccessible for complex constraints since it may require exhaustive lookahead until complete solution is constructed. To circumvent this, propose the Lazy algorithm which works with an overestimation set (((1=) representing the currently known complementary set of actions that are deemed impossible. LazyMask adaptively establishes this set via lookahead initialization strategies and incrementally refining it through backtracking. The interaction between lookahead and backtracking enables efficient generation of feasible solutions under complex constraints. The detailed procedure is described in Algorithm 1.
Backtrack. Lask employs an adaptive backtracking mechanism to ensure solution feasibil- ity while reducing unnecessary computation. At each step t, the algorithm examines the current overestimation ((T.:)) If this set non- non-empty, the algorithm extends the partial route by sampling the next node Tz+1 according to the masked policy Pe, and then advances to step t + 1 to initialize the new overestimation set. Otherwise, if the set is empty, the algorithm's decision depends on the backtracking budget. If the budget is unreached, the algorithm backtracks to step & - and refines ((T)+1)) by removing the invalid node However, if the budget has been reached, it instead relaxes (TT))) to the set of all unvisited nodes ensure complete route be generated.
4

---

Published as a conference paper at ICLR 2026
For NP-hard combinatorial optimization problems with complex constraints, it is precisely due to the inherent complexity of the search space that generating a solution via a single forward pass is insufficient. The backtracking mechanism addresses this limitation by transforming it from conventional one-pass forward model to a dynamic paradigm g capable of both forward and backward operations. As core role in decoding algorithm, it significantly enhances the flexibility of route decoding and constitutes the most fundamental difference from previous neural solvers.
Lookahead. LazyMask offers great flexibility for initializing the overestimation set as long as ((T::) contains the potential set ((T:)). In this paper, we resort to lookahead strategies for this initialization. Single-step lookahead (SSL) is a common approach for ordinary routing problems that examines unvisited nodes for immediate constraint violations. Two-step lookahead (TSL. performs an additional step of lookahead to filter nodes that appear feasible under SSL but could lead to infeasible routes, which adopted in (Bi et al., 2024) and termed as one-step PI masking. The specific implementations of these two strategies for TSPTW and TSPDL are provided in Appendix E.
Algorithm 1 LazyMask algorithm
1: Input: routing problem instance P, neural network pe. backtracking budget R.
2: Initialize == 0, = 1, := 0 and the overestimation set S(T1 either by SSL or TSL. do
3: while $
4: if ((1aa) = 0 and < R then
5: Update ((m)-1) = (m
6: Set t := 1, := = + 1.
7:
else
8:
if (TTI) = 0 then
9:
S(T):) V (m mt).
end if
11:
Calculate the probability pa(-TTra; P) using ((
12: Sample me+1 ~ Po (1(Ti::; P).
13: Set == + and initialize ((T))) either by SSL or TSL.
end if
15:
end while
Output: route I..
3.3 REFINEMENT INTENSITY EMBEDDING
While our LazyMask algorithm is model-agnostic, standard dynamic features in existing auto- regressive models (Kool et al., 2018; Kwon et al., 2020) incompatible with backtracking. These features typically only reflect aggregated information from the partial route, such as the current time in TSPTW, implicitly assuming a one-pass forward construction. However, when backtracking occurs, this design renders the model state invariant to its search trace, leading to representation ambiguities that can hinder the model's learning ability. For instance, the model cannot distinguish whether the current partial route emerges from forward construction or backward correction.
To address this, we propose the refinement intensity embedding (RIE), designed enrich the decoder's input with essential context about the search trace via the refinement intensity of overestimation sets. RIE is derived from two distinct refinement intensity features. The local feature quantifies the refinement count e of the current $(T::)) represented as a capped N N-dimensional one-hot vector with its non-zero entry at index min(c; + 1, N). The global feature signals whether the total number of backtracks has reached the budget R, encoded as 2-dimensional one-hot vector. These features are concatenated and then projected to form the final RIE. The resulting RIE enhances the model's awareness of the search trace, resolving the representation ambiguities caused by backtracking.
3.4 TRAINING
For routing problems where identifying feasible solutions can be intractable (Savelsbergh, 1985), LazyMask with a large backtracking budget R is inefficient during the early training stage. We therefore adopt a smaller R during training to enhance computational efficiency. This practical choice, however, lead infeasible solutions, requiring method to guide po towards the feasible set. Thus,
5

---

Published as a conference paper at ICLR 2026
LMMss
Instence fosture
repularter
O
Nade enbhddiligg
Lack deceding
Trajetheto
RL bos
Partial sortion
Liisk
Hind elats
inteadly cubbolding
Palky ar aliicat
LMak loss
deset
Masy decoding
petennial
Routing
Neateed
Exist
Refine the oecroliiniiinn
Patcalnalodk Masked male
Propeealasis mads
Lurilyy spdare
Figure An illustrative overview of LMask: Up the overall LMask framework. Down the LazyMask decoding algorithm.
we employ the & penalty function, a well-established technique in constrained optimization (Nocedal Wright, 2006). This function specifically penalizes violations of complex constraints, such as time windows in TSPTW and draft limits in TSPDL, while simpler constraints like node visits are inherently satisfied by the design of po- The training objective is then formulated as
min
E Em-po(:P) M p P) + Ao P)),
where =
P= S<; + + max (r; P), is the penalty function, p > is given penalty parameter and e, (T; P) quantifies the violation the j-th complex constraint. While previous studies (Tang et al., 2022; Ma et al., 2023) have explored l penalty soft constraints, innovatively combine hard and soft constraints during training. It starts with hard constraints through backtracking and then turns to soft constraints for flexible optimization reached. The policy po is trained using a standard policy gradient algorithm (Silver et al., 2014; Sutton & Barto, 2018) with further details provided in Appendix B. The overall LMask framework is illustrated in Figure 1.
the budget threshold
THEORETICAL RESULTS
4.1 VALIDITY OF LAZYMASK ALGORITHM
To ensure the effectiveness of Algorithm in solving constrained routing problems, first prove that it always generates feasible solutions and has non-zero probability of generating all feasible solutions. The following proposition shows the validity of the algorithm.
Proposition 4.1. Suppose that the problem (1) is feasible, and that the backtracking budget in Algorithm is set to R +o. Then, i) any solution generated by Algorithm is feasible; ii) Algorithm assigns a non-zero probability to generate any feasible solution π.
This proposition demonstrates that Algorithm never generates infeasible solutions and no feasible solution is excluded. This ensures that the algorithm explores the entire feasible solution space with the distribution Pg. which acts as the foundation for further analysis of the algorithm's 's behavior in finding optimal solutions.

---

Published as a conference paper at ICLR 2026
4.2 VALIDITY OF PROBABILISTIC MODEL
We further analyze the theoretical validity of the probabilistic model for the original routing problem by providing rigorous performance guarantees. Before delving into the formal theorem, it essential to clarify a fundamental assumption supporting the analysis.
Assumption 4.2. We assume that the auto-regressive neural network pe has sufficient expressive power to approximate the target distribution yx. Specifically, the approximation error 8()) defined as follows satisfies:
8(A) mjn max (Lop ll P)) c/A,, A= 0, PED
where is a small constant. Let (a) be the corresponding optimal distribution.
Assumption 4.2 ensures that the auto-regressive neural network po effectively parameterizes Gibbs distributions gx. with o(A) quantifying their approximation error. It is worth noting that as À is approaching zero, the target distribution yA converges toward a point mass distribution, which is hard to approximate. Hence, we do not assume a uniform upper bound. We further give the following theorem to formalize the performance guarantees of the probabilistic model.
Theorem 4.3. Suppose that Assumption 4.2 holds. We define A(P) == min P(
Then, for any e >> and (P) 2 X > 0, the following inequality holds:
|C| CCA(())-AAP)) A(P)AA
IP PRy (f(T;P) 2 (PP)
A(P)) + 2X
C
Theorem 4.3 provides probabilistic bound for the event that the solution πT ~ (A) (: (:) is sampled with an objective value [(T; P) significantly larger than the optimal value (*)P). The suboptimality gap (P)) serves as a measure of separation between optimal and suboptimal solutions in the fcasible set C, while Ả controls the trade-off between exploration and concentration in the Gibbs distribution Ωx- A smaller À enhances concentration and suppresses suboptimal solutions more effectively but increases the approximation error v 2 while larger À reduces approximation error and improves
computational fcasibility but weakens the probability guarantee in the term of e -A(P)/, This trade- off of the entropy regularization coefficient À is intrinsic to the probabilistic model and underscores the interplay between concentration, exploration, and approximation quality.
5 EXPERIMENTS
We conduct experiments on two representative hard-constrained routing problems: TSPTW and TSPDL, using synthetic datasets of sizes n 50, 100 across different hardness levels and a real-world TSPTW benchmark. All experiments are conducted on a server with NVIDIA Tesla A800 GPUs (80GB) and Intel Xeon Gold 6326 CPUs (256GB) 2.90GHz. The data generation mechanism, implementation details, and additional results are available in Appendix E. The code of the proposed LMask framework is available https: / / thub. com/ opt.su i t /MMas..
Setup. To evaluate the effectiveness of LMask, we compare it against several baselines. For tradi- tional solvers, we adopt PYVRP (Wouda et al., 2024), LKH3 (Helsgaun, 2017) and OR-Tools (Furnon & Perron, 2024). For neural solvers, we consider PIP and PIP-D (Bi et al., 2024), which proactively mask actions that could lead future infeasibility, and VSR-LKH (Zheng et al., 2023), which incorporates reinforcement learning into the local search process of LKH3. Additionally, we include two simple constructive heuristics with backtracking, Random-L and Random-C. We use greedy rollout with 8x symmetric dihedral augmentation for all neural solvers as done in (Kwon et al., 2020), resulting in 8 solutions per instance. LMssk adopts TSI. as its default initialization strategy.
Evaluation metrics. We evaluate both the ability to handle complex constraints and the quality of feasible solutions. The instance infeasibility rate (Ins.) is the fraction of instances for which no feasible solution is found, and the solution infeasibility rate (Sol.) is the fraction of generated solutions that are infeasible. To assess solution quality, we report the average route length over the best feasible solutions, excluding instances for which no feasible solution is available. Additionally, the gap is computed with respect to VRP for TSPTW and LKH3 for TSPDL, and is averaged over instances where both the evaluated method and the reference solver find feasible solutions. Note that
7

---

Published as a conference paper at ICLR 2026
the gap is computed a different subset of instances from those used for the average route length, and serves as the primary metric for solution quality, as done in (Bi et al., 2024). Finally, we report the total inference time required to solve all instances in the dataset.
Table I: Results on synthetic TSPTW datasets. Bold indicates the best among constructive methods.
Nodes
50
100
Infeasible
Infeasible
Method
Sol.
Inst.
Obj.
Gap
Time
Sol.
Inst.
Obj-
Gap
Time
PyVRP
0.00%
7.31
1.7h
0.00%
10.19
4.3h
LKH3
0.00%
7.31
0.00%
1.9h
0.00%
10.21
0.29%
7.2h
VSR-LKH
0.00%
7.31
0.00%
4.3h
0.00%
10.19
0.08%
16.4h
OR-Tools
0.00%
7.32
0.21%
1.7h
0.00%
10.33
1.43%
4.3h
Easy
Random-L
56.02%
0.04%
14.55
99.23%
1.3m
95.17%
9.37%
30,66
201%
6.1m
Random-C
62.31%
0.03%
19.12
162.03%
1.4m
98.179
27.30%
44,20
333.74%
6.1m
PIP
0.28%
0.01%
7.51
2.73%
9%
0.16%
0.00%
10.57
3.78%
29s
PIP-D
0.28%
0.00%
7.50
2.60%
10s
0.05%
0.00%
10.66
4.62%
31s
LMask
0.06%
0.00%
7.45
2.02%
7s
0.01 %
0.00%
10,50
3.11%
17s
PyVRP
0.00%
13.03
1.7h
0.00%
18.72
4.3h
I.K3
0.00%
13.02
0.00%
2.9h
0.01%
18.74
0.16%
10.3h
VSR-LKII
0.00%
13.03
0.01%
8.2h
0.00%
18.72
0.00%
8.7h
Medium
OR-Tools
15.12%
13.01
0.12%
1.5h
0.52%
18.98
1.40%
4.3h
Random-L
98.31%
32.18%
18.91
47.04%
1.6m
100.00%
100.00%
5.8m
Random-C
91.17%
8.18%
21.04
61.91%
1.6m
100.00%
100.00%
5.9m
PIP
4.82%
1.07%
13.41
2.93%
10s
4.35%
0.39%
19.61
4.79%
29s
PIP-D
4.14%
0.90%
13.46
3.31%
9s
3.40%
0.03%
19,80
5.76%
31s
LMask
0.04%
0.00%
13.25
1.68%
0.05
0.00%
19.51
4.23%
18s
PRPRP
0.00%
25.61
1.7h
0.01%
$1.27
4.3h
LKII3
0.52%
25.61
0.00%
2.3h
0.95%
$1.27
0.00%
1d8h
VSR-LKH
0.52%
25 68
0.00%
4,4h
0.91%
$1.27
0.00%
8.9h
OR Tools
65.11%
25.92
0.00%
0.6h
89.25%
51.72
0.00%
0.5h
Hard
Random-L
100.00%
100.00%
1.6m
100.00%
100.00%
5.6m
Random-C
100.00%
99.829
25.98
1,22%
1.6m
100.00%
100.00%
5.8m
PIP
5.65%
2.85%
25.73
0.18%
9%
31.74%
16.68%
$1.48
0.37%
28s
PIP-D 6.44%
3.03%
25.75
0,27%
9s
13.59%
6.60%
51.43
0.32%
31s
I.Mask
0.00%
0.00%
25.71
0.10%
0.00%
0.00%
51.38
0.21%
18s
Table 2: Results synthetic TSPDL datasets. Bold indicates the best among constructive methods.
Nodes
50
100
Infeasible
Infeasible
Method
Sol.
Inst.
Obj.
Gap
Time
Inst.
Obj.
Gap
Time
LKH3
0.00%
10.85
2.3h
0.00%
16.36
10.2h
VSR-LKH
0.00%
10.85
0.08%
3.8h
0.00%
16.35
0.07%
11.0h
Medium
OR-Tools
100.00%
10.9s
100.00%
56.9s
Random-L
99.96%
97.28%
21.02
138.56%
38s
100.00%
100.00%
2.0m
Random-C
96.89%
47.39%
24.71
145.85%
37s
100.00%
99.98%
50.48
319.97%
2.0m
PIP
1.75%
0.17%
11.23
3.59%
8s
2.50%
0.16%
17.68
8. 8.10%
21s
PIP-D
2.29%
0.22%
11.26
3.96%
8s
1.83%
0.23%
17.80
8.84%
23s
LMask
0.03%
0.01%
11.14
2.75%
6s
0.20%
0.05%
17.04
4.24%
15s
LKH3
0.00%
13.25
2.6h
0.00%
0.00%
20.76
15.8h
VSR-I.HH
0.00%
13.25
0.05%
6.0h
0.00%
20.75
0.05%
17.2h
Hard
OR-Tools
100.00%
10.6s
100.00%
56.8s
Random-L.
100.00%
99.96%
22.2
132.40%
37s
100.00%
100.00%
2.0m
Random-C
99 90%
94.05%
25.55
135.68%
37%
100.00%
100.00%
2.0m
PIP
4.83%
2.39%
13.63
3.42%
8s
29.34%
21.65%
22.35
12.87%
20s
PIP-D 4.16%
0.82%
13.79
4.28%
8s
13.51%
8.43%
22.90
12.53%
23s
LMask 0.19%
0.04% %
13.57
2.52%
6s
0.80%
0.26 %
21.63
4.34%
15s
5.1
PERFORMANCE ON SYNTHETIC DATASETS
The results on synthetic TSPTW and TSPDL datasets are presented Tables and 2. On TSPTW datasets, LMask consistently achieves near-zero infeasibility rates, significantly surpassing OR-Tools,
8

---

Published as a conference paper at ICLR 2026
PIP, PIP-D and heuristics across different hardness levels. Compared to the traditional solvers PyVRP and LKH3, LMask is substantially efficient due to fast network inference. Although VSR-LKH also learning based, it is implemented on top of the computationally intensive LKH3 pipeline and therefore inherits its runtime profile, remaining orders of magnitude slower than LMakk. Regarding solution quality, we observe that while PIP-D can improve feasibility over PIP, this sometimes comes the cost of larger gaps. In contrast, LMask delivers improved feasibility and lower optimality gaps than PIP and PIP-D across all settings, while maintaining competitive inference times. The advantages of LMask become even more pronounced on TSPDL datasets, showing significant improvements in both feasibility and solution quality. These results highlight that LMask can effectively generate higher-quality solutions while significantly reducing the occurrence of infeasible solutions.
5.2 GENERALIZATION AND SCALABILITY
In Table 3, we further assess the generalization ability of LMask on the well-known TSPTW bench- mark (Dumas et al., 1995). Across all problem sizes, LMask surpasses neural baselines in both solution feasibility and quality. Notably, as the problem size increases, the performance of PIP and PIP-D degrades significantly, whereas LMask remains robust, demonstrating strong generalization across problem sizes. Additional experiments with varying maximum time window widths in Ap- pendix E further confirm the generalization ability of LMask. Beyond generalization, LMask also exhibits notable scalability. Results on hard TSPTW-500 in Appendix E validate its scalability.
Table 3: Results on the TSPTW benchmark.
Nodes
20
40
60
80
Method
Infeas.
Obj.
Gap
Infeas.
Obj.
Gap
Infeas.
Obj.
Gap
Infeas.
Obj.
Gap
PIP
5.0%
337.00
5,2%
45.0%
428.09
4.6%
20.0%
580.25
11.5%
22.2%
644.43
8.7%
PIP-D
5.0%
336.63
5.2%
25.0%
460.27
6.3%
40.0%
608.67
13.1%
66.7%
662.67
12.0%
LMask
0.0%
326.55
0.7%
0.0%
445.50
1.0%
0.0%
530.60
4.3%
0.0%
615.11
3.5%
(a)
(b)
(c)
15
18
Mauk dell
Precsing (83)
Ie. beles. 291
Tree bot
Time Prrecting (83)
10
-B- Toe
17
Sal. Infran (1))
80-
LMbue (TSL)
40
40
Backirusking Budget
Rackiracking
Bodgel
Figure 2: Empirical evaluation of the backtracking mechanism on hard TSPTW-100. (a)-(b) Impact of the backtracking budget R under SSL and TSL initializations, respectively. (c) Solution infeasibility versus inference time for LMask with different overestimation initial strategies and baseline methods.
5.3 EMPIRICAL ANALYSIS ON BACKTRACKING
Effeet of the backtracking budget. Here we investigate how the backtracking budget It influences the performance of L.Mask under both SSL and TSL initialization strategies on the hard TSPTW-100 dataset. As shown in Figure 2 (a)(b), for both strategies, inference time exhibits nearly linear growth with respect to R, with an increase of approximately 2 seconds per 100 additional backtracking budget, demonstrating manageable computational overhead. On the other hand, infeasibility rates decrease sharply at small values of R, indicating substantial carly-stage gains in feasibility. These results highlight that larger backtracking budgets substantially improve solution feasibility with modest increases in runtime.
Backtracking vs. lookahead. The reduction in solution infeasibility as the inference budget increases for different methods is illustrated in Figure 2 (c). The inference budget is scaled by increasing the backtracking budget R for LMask, whereas for PIP and PIP-D. is adjusted by increasing the lookahead depth from to three. With TSL. LMakk attains zero solution infeasibility rate within

---

Published as a conference paper at ICLR 2026
2.31%
Win RIE Without RIE
7.38%
0.18
Sol. Infeas. (%)
0.14%
Gap (5)
2.1
0.14
Gup
1.9
0.10
4
3.67%
3.33%
3.11%
1.7
1.68%
0.05%
0.06
1.5
0.02
Gap
Sol. Infeas.
0
0.005
0.01
0.05
Figure 3: Effect RIE.
Figure 4: Effect of entropy term.
30 seconds. Even under the less accurate SSL, LMask drives the infeasibility rate down to the second lowest level by allocating a larger backtracking budget. However, PIP and PIP-D exhibit unacceptably high infeasibility rates under SSL. Increasing the lookahead step from 2 to 3 induces an order magnitude rise in inference time while yielding only marginal gains and the outcomes remain inferior LMMssk under SSL with significantly less inference time. These results demonstrate that backtracking combined with a lightweight lookahead initialization is more efficient than methods that rely exclusively on deeper lookaheads.
Additional results. To thoroughly analyze the interaction of backtracking and the overestimation set initialization strategy, we present results on medium TSPTW-50 for all combinations of their usage at training and inference in Figure 5 of Appendix E.3. We also visualize the decoding process of LMask in Figures and 7 of Appendix E.4, which provides an in-depth analysis of the cireumstances under which backtracking is efficient and those in which it is not.
5.4 ABLATION STUDY
Refinement intensity embedding. In Figure 3, we present the results on medium TSPTW-50 with and without RIE. The results confirm that the inclusion of RIE leads to substantial reduction in optimality gap. Concurrently, it also fosters a tangible improvement in solution feasibility.
Entropy term. In Figure 4, report the results easy TSPTW- 100 for models trained with different entropy coefficients X. The optimality gap exhibits a non-monotonic patter.. It decreases as increases from 0 to 0.01, achieving the best performance À 0.01, but then rises significantly at X = 0.05. This reflects the intrinsic trade-off between exploration and concentration in the probabilistic model, and suggests that choosing an appropriate entropy coefficient can improve solution optimality. This observation also aligns with our theoretical analysis in Section 4.2.
6 CONCLUSION
In this paper, we propose a novel framework, LMask, for solving hard-constrained routing problems by introducing innovative masking mechanisms. By addressing feasibility through lazy masking, our approach can generate feasible solutions efficiently through the transformer-base model with RIE. We provide theoretical guarantees demonstrating that our approach preserves both feasibility and optimality. Extensive experiments on TSPTW and TSPDL reveal that LMask achieves state-of-the-art feasibility rates and solution quality. Although our current framework is only applied to limited problem types, future work may explore its extension more general combinatorial optimization problem with simultaneously reduced infeasibility and the solution gap.
ACKNOWLEDGMENTS
The computational resources were supported by the Center for Intelligent Computing and Song- Shan Lake HPC Center (SSL-HPC) in Great Bay University, Dongguan, China. This research was supported in part by National Key Research and Development Program of China under the grant number 104YFA1012990
the National Natural Science Foundation of China under the grant numbers 12331010 and 12288 101, and the Natural Science Foundation Beijing, China under the grant number 7230002. We also thank the anonymous reviewers for their valuable feedback.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Luca Accorsi and Daniele Vigo. fast and scalable heuristic for the solution of large-scale capacitated vehicle routing problems. Transportation Science, 55(4))832-866, 2021.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In International Conference on Learning Representations, 2015.
Irwan Bello, Hieu Pham, Quoc V Le. Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. In International Conference on Machine Learning (Workshop), 2017.
Federico Berto, Chuanbo Hua, Junyoung Park, Laurin Luttmann, Yining Ma, Fanchen Bu, Jiarui Wang, Haoran Ye, Minsu Kim, Sanghyeok Choi, et al. RL4CO: an extensive reinforcement learning for combinatorial optimization benchmark. arXiv preprint arXiv:2306. /7/00, 2023.
Federico Berto, Chuanbo Hua, Nayeli Gast Zepeda, André Hottung, Niels Wouda, Leon Lan, Kevin Tiemnyy and Jinkyoo Park. RouteFinder: Towards foundation models for vehicle routing problems. In ICML 2024 Workshop on Foundation Models in the Wild (Oral), 2024.
Jieyi Bi, Yining Ma, Jianan Zhou, Wen Song, Zhiguang Cao, Yaoxin Wu, and Jie Zhang, Learning to handle complex constraints for vehicle routing problems. In Advances in Neural Information Processing Systems, 2024.
Cheng Chen, Ruitao Chen, Tianyou Li, Ruichen Ao, and Zaiwen Wen. Monte Carlo policy gradient method for binary optimization. arXiv preprint urXiv:2307.00783, 2023.
Jingxiao Chen, Ziqin Gong, Minghuan Liu, Jun Wang, Yong Yu, and Weinan Zhang. Looking ahead to avoid being late: Solving fard-constrained traveling salesman problem. arXiv preprint arXiv:2403.053/8 2024.
Jinho Choo, Yeong-Dae Kwon, Jihoon Kim, Jeongwoo Jae, André Hottung, Kevin Tiemny, and Youngjune Gwon. Simulation-guided beam search for neural combinatorial optimization. In Advances in Neural Information Processing Systems, 2022.
William Cook. In pursuit of the traveling salesman: mathematics at the limits of computation.
Princcton university press, 2015.
Rodrigo Ferreira Da Silva and Sebastián Urrutia. A general VNS heuristic for the traveling salesman problem with time windows. Discrete Optimization, 7(4):203-211, 2010.
George Dantzig, Ray Fulkerson, and Selmer Johnson. Solution of large-scale saveling-salesmeen problem. Journal of the operations research society of America, 2(4):393-410, 1954.
George B Dantzig and John H Ramser. The truck dispatching problem. Management science, 6(1): 80-91, 1959.
Ocotlán Díaz- Parra, Jorge A Ruiz-Vanoyy Beatriz Bernábe Loranca, Alejandro Fuentes-Penne and Ricardo A Barrera-Cámare A survey of transportation problems. Journal of Applied Mathematics, 2014(1):84812) 129, 2014.
Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Mare Andreoli. BQ-NCO: Bisimulation quotienting for generalizable neural combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
Lu Duan, Yang Zhan, Haoyuan Hu, Yu Gong, Jiangwen Wei, Xiaodong Zhang, and Yinghui Xu. Efficiently solving the practical vehicle routing problem: A novel joint learning approach. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 3054 3063, 2020.
Yvan Dumas, Jacques Desrosiers, Eric Gelinas, and Marius M Solomon. An optimal algorithm for the traveling salesman problem with time windows. Operations research, 43(2):367-371, 1995.
Vincent Furnon and Laurent Perron. Or-tools routing library, 2024. URL httpttt//t/eeeeeeeeeeeeee //wee//eeeeel...eee googl 1 le www.coooooooooo opt wwtimiiii...............i......m zat on on/routing!
11

---

Published as a conference paper at ICLR 2026
Keld Helsgaun. An extension of the Lin- Keenighnn-Helsseeeeee TSP solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12:966-999 980669980-00 2017.
Mohamed Hibat-Allah, Estelle M Inack, Roeland Wiersema, Roger G Melko, and Juan Carrasquilla. Variational neural annealing. Nature Machine Intelligence, 31155996,,,,,, 2021.
André Hottung, Yeong-Dae Kwon, and Kevin Tiemny. Efficient active search for combinatorial optimization problems. In International Conference on Learning Representations, 2022.
Ziwei Huang, Jianan Zhou, Zhiguang Cao, and Yixin XU. Rethinking light decoder-based solvers for vehicle routing problems. In The Thirteenth International Conference on Learning Representations, 2025.
Chaitanya Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227 2019.
Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-NCO: Leveraging symmetricity for neural combinatorial optimization. In Advances Neural Information Processing Systems, 2022.
Grigorios D Konstantakopoulos, Sotiris P Gayialis, and Evripidis P Kechagias. Vehicle routing
problem and related algorithms for logisties distribution: A literature review and classification. Operational research, 22(3):2033-262,, 2022.
Wouter Kool, Herke Van Hoof, and Max Welling, Attention, learn to solve routing problems! In International Conference on Learning Representations, 2018.
Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic pro- gramming for vehicle routing problems. In International conference integration of constraint programming, artificial intelligence, and operations research. Springer, 2022.
Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. POMO: Policy optimization with multiple optima for reinforcement learning. In Advances in Neural Information Processing Systems, 2020.
Yann LeCun, Sumit Chopra, Raia Hadsell, M Ranzato, Fujie Huang, et al. A tutorial on energy-basce learning. Predicting structured data, 1(0), 2006.
Han Li, Fei Liu, Zhi Zheng, Yu Zhang, and Zhenkun Wang. CaDA: Cross-problem routing solver with constraint-aware dual-attention. arXiv preprint arXiv:2412.003: 2024.
Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Advances in Neural Information Processing Systems, 2023.
Yining Ma, Zhiguang Cao, and Yeow Meng Chee. Learning to search feasible and infeasible regions of routing problems with flexible neural k-opt. In Thirty-sevnnth Conference Neural Information Processing Systems, 2023.
Reza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takac. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, 2018
Jorge Nocedal and Stephen J Wright. Numerical optimization. Springer, 2006.
Bo Peng. Jiahai Wang, and Zizhen Zhang. A deep reinforcement learning algorithm using dynamic attention model for vehicle routing problems. In Artificial Intelligence Algorithms and Applications: 11th International Symposium, ISICA 2019, Guangzhou, China, November 16-17, 2019, Revised Selected Papers 11, pp. 636-650, Springer, 2020.
Mark S Pinsker. Information and information stability of random variables and processes. Holden- Day, 1964.
Jørgen Glomvik Rakke, Marielle Christiansen, Kjetil Fagerholt, and Gilbert Laporte. The traveling salesman problem with draft limits. Computers & Operations Research, 3919)221112116,, 2012.
12

---

Published as a conference paper at ICLR 2026
Sebastian Sanokowski, Wilhelm Berghammer, Sepp Hochreiter, and Sebastian Lehner. Variational annealing on graphs for combinatorial optimization. In Advances in Neural Information Processing Systems, volume 36, pp. 63907-63930, 2023.
Martin WP Savelsbergh. Local search in routing problems with time windows. Annals of Operations research, 4:285-305, 1985.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In International conference on machine learning, 2014.
Yang Song and Diederik P Kingma. How to train your energy-based models. arXiv preprint
10000220 2021.
Iyya Sutskever, Oriol Vinyals, and Quoe V Le. Sequence sequence learning with neural networks. In Advances in Neural Information Processing Systems, 2014.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Qiaoyue Tang, Yangzhe Kong, Lemeng Pan, and Choonmeng Lee. Learning to solve soft-constrained vehicle routing problems with lagrangian relaxation. arXiv preprint arXiv:2207. 099600, 2022.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, t. ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, 2017.
Thibaut Vidal. Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. Computers Operations Research, 140:105643, 2022.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly, Pointer networks. In C. Cortes, Lawrence, D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems, 2015.
Niels A Wouda, Leon Lan, and Wouter Kool. PyVRP: A high-performance VRP solver package. INFORMS Journal Computing, 2024.
Jiongzii Zheng, Kun He, Jianrong Zhou, Yan Jin, and Chu-Min Li. Reinforced lin kerighan- helsgaun algorithms for the traveling salesman problems. Knowledge-Basee Systems, 260:1 10144, 2023.
Jianan Zhou, Zhiguang Cao, Yaoxin Wu, Wen Song, Yining Ma, Jie Zhang, and Chi Xu. MVMoE: Multi-task vehicle routing solver with mixture-offer -feee-erts...s.....o.o In International Conference on Machine Learning, 2024.
13

---

Published as a conference paper at ICLR 2026
LMask: Learn to Solve Constrained Routing Problems with Lazy Masking (Appendix)
A COMBINATORIAL OPTIMIZATION FORMULATION OF ROUTING PROBLEMS
A.I TSPTW AND TSPDL FORMULATION
The traveling salesman problem with time windows (TSPTW) is a well-known combinatorial opti- mization problem that extends the classic traveling salesman problem (TSP) by introducing additional time window constraints. The objective of TSPTW is find the shortest route for salesman, starting and ending at a designated depot, and visiting a given set of customers exactly once. Let node O represent the depot and Ve (1. ...] represent the of customer nodes. Each customer i E V. has an associated time window (e,, 1:] during which it must be served. Early arrivals are
allowed, meaning that the salesman can arrive at node before the ready time e;. However, this
case the salesman has to wait until service can begin at node i. This problem can be formulated as:
min [(T;P) Σ [Tz.
Exctall
|| Fxall
s.t. c(m;P) Ti-1 -
$ i 1,...,
n+1
d<
1 1 0, i I...., n Σ
where Ti+1 represents the time to begin service at node THt1 in route This time is derived recursively: Ti+1 max (T: + W7, CT41) i= I...., n. with 71 Here Wn, is the total duration from to TT411 which includes both the service time ग. and the travel time from Ti to .T
The traveling salesman problem with draft limits (TSPDL) frequently arises in marine transportation scenarios, where the load-carrying limits of vessels must respected. this problem, node 0 serves the depot, and V. {1, .., n} represents the set of port nodes. Each port i V. is associated with a demand q: > and a draft limit D,. The draft limit D; at port i specifies the maximum cumulative load a vessel carry after visiting that port. The depot at node 0 is assumed to have zero demand, meaning qo = O. This problem can be formulated as:
min f(T:P) Σ
| Txetzal + +||aal++++xxaa Fzlll
1=1
s.t. G(T;P) = 8:41 D Dr..: 50, i= I,...,
n+1
(<
Σ
1
1m 1= 0, i 1,
t=1
where 6:41 denotes the accumulated load after visiting node क,Ş1 in route π. The accumulated load can be calculated as 8,41
E 1+1
1t=1 Ix..
A.2 FEASIBILITY DILEMMA IN TSPTW
Bi et al. (2024) point out that the core of feasibility masking in neural constructive solvers is to filter out invalid actions that violate constraints, based on the assumption that the global feasibility can be decomposed into the feasibility of each node selection step, and that ground truth masks obtainable for each step. We describe this issue more formally using the notation defined in Section 3.1. For simple constraints in other routing problems, there always exists a feasible action for each step. For example, at each step in CVRP, it is possible to return to the depot to perform
14

---

Published as a conference paper at ICLR 2026
action that satisfies the capacity constraints. This indicates that the potential set S can be precisely determined, enabling an efficient masking technique to ensure the feasibility. Since * at each step, valid action is always available. This characteristic ensures that the solution space remains connected, avoiding situations where no valid action can be performed due to capacity violations.
However, not all constraints can precisely determine the potential set S, which may be empty certain decision steps. In TSPTW, nodes are masked out if they have been visited or cannot be visited before their time windows close. The feasibility of selecting a node at particular step impacts the current time, thereby affecting all subsequent selections due to the interdependence imposed by time windows constraints. Therefore, focusing solely on the local feasibility does not guarantee overall feasibility. Once node is selected, the decision becomes irreversible, potentially leading to infeasible situations after several steps. Nevertheless, it impractical to compute full global feasibility obtain the exact potential set S, which is typically considered an NP-hard problem. There is dilemma between solution feasibility and computational costs under these complex constraints.
B TRAINING DETAILS
In this section, elaborate the formulation of the penalty function (p(T;; and the policy gradient algorithm used for training Pa.
B.1 PENALTY FUNCTION FORMULATION
The penalty function (T; P) is designed to guide the policy towards feasible solutions by penalizing constraint violations. It combines the primary objective function f(1r; PP) with terms representing the severity of constraint violations.
For TSPTW, given complete route ग = (πı = 0, T2...., RT), ), let denote the time to begin service node मं the route and 4r, denote the due time of ne. for 1.2.... T. The penalty function is defined as
(T; f(;; Σ max(7: 1, 0).
Here, the term EtS max(Fi - -,, 0) quantifies the total amount by which time windows are violated.
Let 8n represent the accumu- Similarly, for TSPDL, we consider route (T1 0, ......, R.). lated load after visiting node n, and Dr, denote the draft limit node ne, for = 1,2,.... T. The penalty function for TSPDL is formulated
V = P)
+ Σ max D 0)-
Here Σ max(6, - Dr.; 0) represents the total excess load beyond the specified draft limits.
B.2 TRAINING ALGORITHM
The training objective, introduced the main text, is formulated as
min (x--p(:P) [ (T; P) A Alog (T;;;; P)],
(6)
which is expressed in the form of an expectation. Hence we can minimize it by various stochastic policy gradient methods. It is well known that the policy gradient of (6) is given by
E (t
[A(m (T; P) Vo log (TT; P)],
where A(T; P) := 1e (T: P) b(P) + log (T(
(T; P) denotes the advantage function and b(P) is a constant with respect to the parameter 6, referred to the baseline. We then utilize the Monte Carlo method to estimate the policy gradient. Specifically, we sample routes [ and then estimate the expectation with sample average
N Σ
((0PP) = N
A(T:P)V lo
==1
15

---

Published as a conference paper at ICLR 2026
In routing problems, empirically, shared baseline has the desirable effect of reducing variance in the sample estimate for the policy gradient, as demonstrated Kwon et al. (2020). This shared baseline writes 6(P) * W
So far, we have described how to train the policy Pg on a given instance P. The training can be extended to dataset of instances, shown in Algorithm 2.
Algorithm 2 LMask training procedure
Input: data distribution D, neural network pe. number of training steps K, backtracking budget R. for k = .................. K do
Sample a batch of instances (P:) from the data distribution D. Employ the LazyMask algorithm with backtracking budget R to sample N routes { 1 from Pon for each instance P., where i = I,..., B.
Compute the stochastic gradient:
g(0*)
ΣΣ
E
A log lo=os.
BN i=
Update g using 0(t)) with SGD or ADAM optimizer. end for
C MODEL ARCHITECTURE
LMask adopts an encoder-decoder architecture inherited from POMO (Kwon et al., 2020). The encoder transforms static features of problem instance into node embeddings through atffaattetionn mechanism. Based on node embeddings, dynamic features the current partial route and the refine- ment intensity embedding, the decoder then auto-regressively generates the conditional probability through the cross-attention mechanism.
C.I MULTI-HEAD ATTENTION
An attention function takes of queries and separate of keys and values input, and outputs a weighted sum of values for each query. Self-attention means that the query set and the key-value come from the same sequence, while cross-attention means the query set and the key-value set comes from two different sequences. These queries, keys and values are packed into matrices Q E Rn K E R V E 222 for implementation efficiency, where nı is the number of queries, n2 is the number of key-value pairs and d is the hidden dimension. Firstly, attention weights are computed by scaled dot-product between the queries and keys, followed by softmax function
QKT
Softmax
M MM:
Vd
where the softmax function should be understood in row-wise manner with Softmax(2)); exp(es) Σge, exp(xy) for an dimensional vector æ, and M is an optional attention mask that prevents attending to certain positions, which can be done by setting elements to -cc. Then, the attention output is calculated as the sum of the values, weighted by the attention weights: Z = AV. The whole attention function is defined by
QKT Vd
Autention (Q, K, M) = Sofumax
+ M +)
Multi-head attention further takes information from different representation subspaces into considera- tion. starts by lincarly projecting the queries, keys, and values onto H subspaces. Subsequently, each subspace in parallel. Lastly, these attention outputs
the attention function is performed are concatenated and projected back to the original embedding space. In summary, the multi-head attention operation can be formulated
MHA(Q, K, V; M) [Z,, Zz,
Zu] W
16

---

Published as a conference paper at ICLR 2026
where
Z Attention(QW, kW: VWw; M), i=
and Wo, W.P, W W.V. are learnable projection matrices. The general formulation includes the mask M to support masked attention scenarios. In cases where no masking is applied (i.e., M is ef- fectively a zero matrix or conceptually omitted), the operation is often simplified as MHA(Q, K, V.
C.2 ENCODER
The encoder produces embeddings of all input nodes. Static features of the problem instance first projected to the embedding space to obtain initial embeddings (0) E [nn=-)xdd These static features vary depending on the specific problem considered. For TSPTW, they include node coordinates and time windows, while for TSPDL, they include node coordinates, demands, and draft limits. Then the embeddings are updated through a stack of attention layers, each consisting of two sublayers, one multi-head attention sublayer and one weed-fo sublayer. Furthermore, residual connections and instance normalization are employed. A single attention layer can be formulated as
h IN h MH (e,, e= e= h+ = IN (h' (h'+ + +FFN l e=0....,L.
where IN represents the instance normalization, MHA is the multi-head attention, as given by (7), and the fully-connected feed forward network FEN is applied in row-wise manner with FEN (x) = max (xWf + b9, 0) W + by for row vector æ.
C.3 DECODER
The decoder regressegyss generates the conditional probability over available nodes based on the node embeddings and the current partial route. At decision step f, 1 s t s T 1, a partial route Tie assumed have been constructed.
Previous works (Kwon et al., 2020; Berto et al., 2024) begin by constructing a query through a projection of the current node embedding hr, and dynamic features 8, into the embedding space: = hr W + sy W? This is represented as the sum the node embedding and the state embedding. The dynamic features s; typically aggregate information accumulated up to the current decision step t. For instance, in TSPTW, St represents the current time, and in TSPDL, represents the current load. However, in the presence of backtracking, relying solely on such features can lead to representation ambiguities. The model state, defined only by hn, and st, becomes invariant to the specific search trace, potentially hindering the model's ability to learn meaningful distinctions.
To address this limitation, we introduce the refinement intensity embedding (RIE). The RIE enhances the model's awareness of the search trace by explicitly encoding information about refinement intensity. The refinement intensity is captured by set of dedicated features, denoted by G.. which are subsequently projected to form the RIE Ç. W.W. G. is conceptualized from two distinct perspectives. First, the local feature, represented by (Pr. quantifies c, the number of refinements applied to the overestimation set $(11:) corresponding the current partial route Tı.. This count c, is transformed into a capped one-hot vector y E (0.1)- of predefined length N: of so is 1; otherwise, the N-th element is 1, with all other elements being O. Second, the global refinement status, captured by &., is a binary feature indicating whether ut, the total backtracking count accumulated during the decoding process, has reached the backtracking budget R. This is defined as & [1, O if < R, and & [0. 1] if > R. These two types of features are concatenated to yield the overall refinement intensity features Ç. [pp. & IR N+2 The query qe then constructed by incorporating the RIE: ht., W 8, W + G.W..
if < N, the (ca+1) 11th element
To ensure that the subsequent attention mechanism and probability calculation only consider valid next nodes, we define mask Mr (0, (0,-o))*+] This mask vector is derived from S(1 such that (t) = 0 node belongs to ((1z)), ). and (i) = - oo otherwise. Using this mask, a context embedding, hG, is subsequently obtained via masked multi-head cross-attention layer. This layer
17

---

Published as a conference paper at ICLR 2026
employs qe the query, with static node embeddings h' projected by W and wy to serve keys and values respectively, and incorporating the mask Mc:
h (HH( h w , M,).
Next, the logits are computed with single attention head:
(h W
vd
Finally, the logits are transformed into a conditional probability distribution over available nodes
Pe Ti:t: P) = Softmax(C tanh( (2+ + M)),
where C' > 0 is a clipping constant for the tanh function.
D PROOF OF THEORETICAL RESULTS
D. PROOF OF PROPOSITION 4.1
For clarity, we restate Proposition 4.1 here before providing the proof.
Proposition 4.1. Suppose that problem (1) is feasible, and that the backtracking budget Algorithm I is set to R = +oc. Then, i) any solution generated by Algorithm is feasible; ïi Algorithm I assigns non-zero probability to generate any feasible solution n.
Proof. i) Let the route π be generated by Algorithm 1. Since S(11T--1) only needs to validate the feasibility of the last node тy. the estimation ((11TT-1 is exact, that is, ((T:T--) = S(T1TT-1). It follows that Ty ( By the definition of (T1:r-1)) this implies that a feasible route.
ii) Let be feasible route. For t = 1,..., T - 1, the definition of 5(T1a) yields T S((T:))
Since S(T1.)) ((T1:)). it follows that TT11 E ((T..)) *f 0 for t l,.... ... , 1. Therefore, the Algorithm assigns probability p P)) > to generate T++1. The total probability of generating the complete route π is strictly positive, i.c., (T) = II route πT can be generated by Algorithm
P) > 0. Thus,
This completes the proof.
D.2 PROOF THEOREM 4.3
For clarity, we restate Theorem 4.3 here before providing the proof.
Theorem 4.3. Suppose that Assumption 4.2 holds. We define A(P) == min [(T;
Then, for any e and ((P) 2 X 0, the following inequality holds:
C A(P)/X
P P (f(T:P) (P) +
II max e, A(P))
+1 2X
Proof. For convenience, we omit all notations P in this proof. Let π denote a random variable drawn from the distribution (A), (A) and define the event A = (f(TT) > ʃ" + +). We aim to bound the probability of the event A. To this end, let us first bound the difference in probabilities of the A under the distribution (a-(A) and yΛ using the KI. divergence. Then, we apply Markov's inequality derive a tail bound on the event probability under qx. Finally, using properties of the Gibbs distribution, we derive a convergence bound that characterizes how this probability behaves decreases.
1) We begin by introducing Pinsker's s inequality (Pinsker, 1964), which bounds the total variation (TV) distance in terms of the KL divergence. Given distributions P and over finite domain
D, the TV distance is defined as
TV(P.Q) == max P(E) Q(E)
ECD
18

---

Published as a conference paper at ICLR 2026
where E _ D represents any measurable event of the domain D. Pinsker's inequality states that the TV distance and KL divergence satisfy the following inequality:
1
Q)) S \22 1L Q)..
Using Pinsker's incquality, we can bound the probability difference for the given event A under two given distributions Po- and gx:
8(2)
(x) (x(1)) & (P (A): (A): 22) S V22 (L)ll()))) S
1
(8)
2X
where the first inequality follows from the definition of the TV distance, the second uses Pinsker's inequality and the last is based on the Assumption 4.2. This result provides way to control the discrepancy in the probability event under the two distributions pg- and qx, terms of the approximation error (A)..
2) Then, we analyze the tail probability of qλ using Markov's inequality. If X is nonnegative random variable and c 0, then the probability that is at least is at most the expectation of X divided by c:
EX E
P(X
Using Markov's 's inequality, we can give the following tail bound:
+e) E22 ((T)
P (f(T)
(9)
As / is defined over discrete domain, it has finitely many function values and suboptimality gap > It can be observed that (f(((T) 2 f +) = qx 2 A when 0 < < A. We
can conclude the following incquality from (9):
P 2 +6) [ - max A}
(10)
3) Since yΛ converges to the target distribution g" A - O. we analyze the asymptotic behavior of the expected suboptimality gap E2g, [f(T) [*] as decreases. Specifically, we write the expectation:
Eng (TT) - f1] Σ a (=)((((()) 1- Enece Emece-((NAA(())) ((MDA(()))((())) - J
(11)
Enece f(m)/A
FEC
The summations over C' in the numerator and the denominator can be split into two parts. Observing that f(T) f = for æ E II",, we factor out e -f" from both the numerator and denominator in (11) and obtain that
Eng (f() 1- ExEu-
5 + Execrm- --66)--)(((())) S*] Exen- --(())))))/ +
+/03///*EEvnni Exerm (1(m))111
ETECAT E (VA)))))((((T -1
111 + E ((7)-111/
(12)
Reviewing that := min f(T) f represents the smallest gap between the objective values f
of suboptimal solutions and the optimal value, we have f(z) f 2
> for all क E C. Given that the derivative of ze -e--r Ar is (1 x/A)e==73 it follows that De z/A non-increasing for xf 2 X. Consequently, when A 2 À > 0. the condition f(x) - f" > A > X implies that (f(() (1)())))))(((T))) -f -
4/A for all C.r The numerator in ( (12) is bounded as
-(())) - IC (ce A/> <ICIAe- A/2 for A >>>00 0. (13)
IT"
Meanwhile, the denominator in (12) has the lower bound |IT*| + Execue -(())-MA/ > [mT]) follows from (12) that
|C| Ae
A/A
E [f(T) f*] <
for A >>00.
(14)
11
19

---

Published as a conference paper at ICLR 2026
4) Finally, combining these inequalities (8), (10) and (14), we derive that
C Ae A/A
P (ay (f(T) -)) <
c
for
A
2
A
0.
(15)
11 max
2X
This completes the proof.
E EXPERIMENTS
E.1 DATA GENERATION
E.I.I TSPTW
The difficulty of a TSPTW instance largely depends on the availability of feasible solutions. Instances are more challenging when they allow very few feasible tours, making it harder for algorithms find valid solutions, while overly feasible instances may lead the policy to overemphasize optimization and neglect feasibility. key determinant of difficulty is the width of the time windows assigned to customer nodes. Narrower time windows reduce the overlap between customer service intervals, significantly limiting the number of feasible tours and increasing problem complexity.
To address these challenges, we adopt a data generation mechanism capable of producing TSPTW in- stances with easy, medium, and hard levels of difficulty. These levels are determined by systematically controlling the time window width and other instance-specific parameters, as detailed below:
Easy and medium TSPTW instances. An expected distance Tn is predefined, which varies depending the number of nodes, The ready times e; are sampled from uniform distribution U[0,T, Time window widths h4 are sampled from scaled uniform distribution 2djo, 3] -Tn, where 0 a B < 1 are hyperparameters. The due times 4, are then calculated as e; + h4. By adjusting the hyperparameters a, B, and T, TSPTW instances with varying levels time window tightness be generated. Specifically, to generate easy TSPTW instances,
set 0.5 and
B 0.75. For medium TSPTW instances, we use a = 0.1 and / = 0.2. In all cases, customer nodes are sampled uniformly within the region [0, 100)a, and T,, is
55 + 1).
Hard TSPTW instances. Consistent with prior works (Kool et al., 2022; Bi et al., 2024), we adopt a generation mechanism inspired by benchmark datasets (Dumas al., 1995; Da Silva & Urrutia, 2010) for hard TSPTW instances. This approach ensures the existence of at least one feasible tour. The core data generation procedure begins by sampling customer locations and constructing random tour. Time windows are then defined centered around the arrival times within this random tour. Specifically, customer coordinates are uniformly sampled from [0, 50]2, followed by the generation of a random permutation π over customers (including the depot) to define directed route. For each customer node n, in this sequence, the cumulative travel distance dz, from the depot to ne along the random tour is calculated. Time windows are then constructed around dz, with pre-specified maximum width w. In benchmark datasets (Dumas et al., 1995; Da Silva & Urrutia, 2010), the maximum time window width typically ranges from 20 100. In this study, we select
100 The ready time 6,, is sampled from d', (0 w/2] and clamped to ensure non-negativity. The due time 4,, is similarly sampled from dx, [0, w/2
For the depot, the ready time is conventionally set to zero, while the due time is left unconstrained since it does not affect the feasibility of the TSPTW solution, provided the depot remains reachable from all customer nodes.
Normalization. To standardize the input and ensure consistency across instances, node coordinates are scaled to the range [0, 1] by dividing them by the maximum sample range. Time windows are proportionally scaled following this transformation maintain consistency with the adjusted spatial coordinates.
1.2 TSPDL
Node coordinates are uniformly sampled from [0. Following (Rakke et al., 2012), we assign a demand of gu 0 to the depot and demand of 9: = each port node. Given percentage o%, randomly select (n + 1) o% nodes with restricting draft limits strictly less than the total demand En 4- Specifically, the draft limits of these selected nodes are randomly generated between 1 and
20

---

Published as a conference paper at ICLR 2026
1. The remaining nodes assigned draft limit equal the total demand Σi=o Its so that their draft limits impose no effective constraints.
To check whether the generated instance admits a feasible solution, employ the following proposition from (Rakke et al., 2012) as a sufficient and necessary condition. If the condition is not satisfied, the instance is rejected and regenerated until feasible one is obtained.
Proposition E.1. (Rakke et al., 2012) Let (I 0, R2, ....... Tn+1) be a solution ordering the port nodes [1.....n} in ascending order of draft limits: Da I D=a= S...Dr... TSPDL instance admits a feasible solution if and only x is feasible.
Dr.-I- Then the
A larger percentage 5% results in more nodes with restricting draft limits, thereby increasing the difficulty of balancing feasibility and optimality. Following (Bi et al., 2024), we set a% to 75% for medium TSPDL datasets and 90% for hard ones.
E.2 IMPLEMENTATION DETAILS
Baseline details. For search- based solvers, including PyVRP, LKH3, VSR-LKH and OR-Tools, run them with 32 CPU cores in parallel as done in (Kool et al., 2018; Zhou et al., 2024). For PIP, PIP-D and LMask, we them single GPU with batch size of 2500 inference time. Below we provide implementation details for each baseline.
PyVRP, a state-of-the-ar VRP solver built on top of HGS. We use the default hyperparame- ters and set time limit of 20 seconds per instance for 50, and 50 seconds for n 100. Note that VRP does not support draft limits and is therefore inapplicable to TSPDL.
LKH3, a strong solver that implements the Lin- hennihenn heuristic for a wide range of routing problems. For each instance, we run LKH with 10000 trials and I run.
OR-Tools, more versatile solver than PRP and LKH3. For TSPTW, cheapest insertion as the first solution strategy and the guided local search as the local search strategy. As PYR we set the time limit to 20 seconds for n = 50, and 50 seconds for n = 100. Despite exhaustive testing across all initial solution strategies, OR- Oo-Tools fails to find any feasible solution for TSPDI. within the time limit, consistent with findings in (Bi et al., 2024).
use the local
PIP and PIP-D, state-of-the-arr neural solvers for TSPTW and TSPDL. To maintain consis- tency with our proposed method and facilitate fair comparison, we specifically utilize their implementations based on POMO. We evaluate PIP and PIP-D using the pretrained models and default hyperparameters as provided in their official source code repositories.
VSR-LKH, a method combining reinforcement learning with LKH3 to solve TSP variants. We compile the official source code using its default settings, including the a-measure for candidate selection.
Random heuristics, two simple random heuristics with backtracking implemented to demon- strate the importance of the policy parameterized by a neural network. Random-L constructs a probability distribution by normalizing the inverse distances from the current node to candidate nodes. Random-C constructs a probability distribution by normalizing the inverse of due times in TSPTW or draft limits in TSPDL. The sample size is set to 64 and the batch size is accordingly set 1024 for n 50 and 512 for n 100 due to memory limit.
Overestimation initialization details. As mentioned in the main text, we initialize the overestimation sets using problem-dependeed lookahead strategies, namely single-step lookahead (SSL) and two-step lookahead (TSL). For TSPTW, according to the triangle inequality property of travel times, if an unvisited node violates the time window constraint at the current step, it will remain infeasible in subsequent steps without backtracking. Hence, SSI. checks whether any unvisited node exhibits a time window violation. If such a node exists, (TT.)) ) is initialized as empty, triggering backtracking; otherwise, it contains all unvisited nodes. TSL enhances this by tentatively extending the route with each candidate node and checking for time window violations among the remaining nodes. Nodes whose selection would make some remaining nodes infeasible are excluded, resulting in more accurate initialization and a notable decrease in backtracking steps. The TSPDL exhibits a similar monotonic property. Since the cumulative load increases along route, any node violating its draft
21

---

Published as a conference paper at ICLR 2026
limit at given step will also be infeasible thereafter. Consequently, SSL and TSL for TSPDL implemented analogously by checking for immediate and future draft limit violations, respectively.
Hy Hyperaarameter details. To ensure a fair comparison, set the backtracking budget R of LMask such that its runtime is comparable to that of neural baselines. The specific backtracking budgets used for experiments in Tables and are summarized in Table 4 Our implementation is built upon the RL4CO library (Berto et al., 2023). Details model and training hyperparameters of our main experiments are reported in Table 5, Note that the total number of gradient updates is comparable that of neural baselines.
Table 4: Backtracking budget settings across different datasets.
TSPTW
TSPDL
Hardness
50
M
100
= 50
100
Easy
100
150
Medium
100
200
150
150
Hard
200
300
150
150
Table 5: Experiment hyperparameters. Values with "y" indicate different choices depending on the
problem size, i.e., the left are values for 50 and the right values for 100.
Hyperparameter
Value
Model
Embedding dimension
128
Number of attention heads
Number of encoder layers
Normalization
Instance
Feedforward hidden dimension
512
Feedforward structure
MLP
Feedforward activation
ReLU
Tanh clipping
10.0
Refinement intensity feature dimension
Training
Train decode type
Multi-sampling with free starts
Number of samples per instance
50 100
Batch size
512/ 64 256,000 100,000
Training instances per epoch
Penalty parameter p
Optimization
Optimizer
Adam W
Learning rate
3e-4/ le-4
Weight decay
1e-6 MultiStepL.R
LR scheduler
LR milestones
1900, 950]
LR gamma
0.1
Gradient clip value
1.0
Max epochs
1000
22

---

Published as a conference paper at ICLR 2026
E.3 DISCUSSION ON BACKTRACKING AND OVERESTIMATIOE SET INITIALIZATION
To thoroughly analyze the individual roles of backtracking and the overestimation set initialization strategy, as well their interaction, we present results on medium TSPTW-50 for all 16 combinations of their usage at training and inference in Figure 5. Note that RIE is disabled in this experiment to ensure fair comparison. We observe that, under TSL, enabling backtracking during training consistently reduces the optimality gap across inference settings. While training with backtracking can affect the model's s inherent constraint awareness, this is effectively compensated by using backtracking during inference. As shown in Figure 5, when applying backtracking with the TSL. strategy at inference, enabling backtracking during training leads to a notable reduction the optimality gap (from 2.69% 2.31% 9) with only negligible increase in the solution infeasibility rate (from 0.05% to 0.14%). Moreover, this slight trade-off is mitigated by our proposed refinement intensity embedding, which further reduces the solution infeasibility rate to 0.05% and the optimality gap to 1.68%. We further observe that enabling backtracking at inference consistently yields substantial reductions in infeasibility and modest improvements in solution quality, regardless of the training configuration. Remarkably, using backtracking with less accurate SSL. outperforms using TSL without backtracking, highlighting the critical role of inference-time backtracking.
Triining Setting N-BTTTSSL.
Training Setting
NoBT-SSL
3.88%
4.69%
N/A
4. 4.10%
NeBT-SSL,
12.62%
57.92%
100.00%
86.92%
17.5
15.0
Inforence Settnn
Inforeaa Seting
NoBTTTTL
5.42%
2.72%
24.70%
2.38%
NoBT-TSL
2.84%
4.01%
15.07%
12.57%
Ga
BT-SSL
3.86%
4.03%
3.58%
3.49%
BT+SSL
0.55%
0.55%
0.37%
1.86%
7.5
5.391
2.69%
24.43%%
2.31%
0.08%
0.055
0.65%
0.14%
(a) Gap
(b) Solution infcasibility rate
Figure Effect of backtracking and overestimation set initialization strategy combinations. BT/NoBT denotes with/without backtracking and SSL/TSL denotes single/two-step lookahead.
E.4 ANALYSIS OF THE EFFICIENCY AND FAILURE MODES OF LMASK
In this subsection, we provide an in-depth analysis of the circumstances under which LMask is efficient and those in which is not. Recall that precisely obtaining the potential set S is sometimes computationally intractable. Fortunately, our goal is solely to construct feasible solutions, and we use a pretrained policy to guide the node selection. Since this policy is trained with an l penalty and its distribution is expected to approximate the feasible region well, we do not require the exact potential set S. Our approach is establish an overestimation set Š and refine it via backtracking when necessary. With the greedy decoding strategy, feasible solution can be constructed as long as the node with the highest probability in the distribution P- TI:)) induced by ((T1:)), falls within the true potential set 5( If at some step the policy incorrectly selects a node i E S( 1 at subsequent construction step, the algorithm will discover that the overestimation set for the corresponding extended route is empty, halting further progress. At this point, our backtracking mechanism is triggered. Through this repeated process of extension and backtracking, the algorithm eventually corrects the incorrect selection at step and removes node from ((T=)
Based this analysis, two key factors influence the efficiency of the LMask algorithm can be identified. The first is the correspondence between the high-probability nodes in the distribution po(- | =i induced by (TT).)) and the true potential set S(m..) at each decoding step l. The second is the cost of correcting an incorrect selection i E $(m::) \ (((m)))) at decoding step t. This cost is related to both the magnitude of t and the initial overestimation set S((mL. il) corresponding to the extended route [ d]. The former determines the backtracking depth, while the latter determines the number of exploration attempts.
23

---

Published as a conference paper at ICLR 2026
To illustrate these factors, visualize the LazyMask decoding process two representative small- scale TSPDL instances (n = 19). In the first example (Figure 6), LMask efficiently constructs a feasible solution with relatively small backtracking budget. Although the gap between the true potential sets and the overestimation sets is large in the early decoding steps, has no impact hecause the policy accurately identifies nodes within the potential set. In later decoding step (t 14), the policy incorrectly selects a node outside the true potential set. However, because this error occurs late, the backtracking depth route is small. Therefore, backtracking budget of only R = 100 is sufficient to correct this error and ultimately construct feasible solution. the second example (Figure 7), LMask requires huge backtracking budget to successfully construct a feasible solution. Here, the initial overestimation set at each step is very close to the true potential set, differing by only one node. However, the policy selects this single incorrect node at early step (1 9), and the overestimation set for the corresponding extended route is large. Consequently, a significant backtracking budget is spent attempting correct this early error (even R 10k insufficient). By increasing the budget to R = 11k, LMask able to correct this selection and finally constructs feasible solution.
large, and the number of nodes in the potential of the extended
Potential Sets und the Overestimation
R=0
Decoding Probability Distribution
0.8
Node Index (
Node Index (1)
15
-02
0.0
Decoding Step (f)
Decoding Step
100
Node Index i
Node Index i
0.6
10.
10
0.4
Decoding Step (f)
Decoding Step (r)
i ((x)))
((m))) ((m)))
i S(T)))
Selected action
Figure 6: Visualization of the LazyMask decoding process on a TSPDL instance where feasible solution is efficiently found with small backtracking budget. The rows depict two decoding trials with varying backtracking budgets: R (Top) and R = 100 (Bottom). The trial with R fails to find feasible solution, whereas the trial with R 100 successfully identifies complete, feasible route. Left: The left column visualizes the relationship between the true potential set ((T1:)) and its overestimation ((m).)) At each decoding step t (x-axis), each node (y-axis) is color-coded based on its set membership. Dark blue indicates ş (1T::) teal green indicates i $(T1:)) ((m))) ((m1a)) The node selected by the policy at each step indicated by red bounding box. The visualization for any failed trial is truncated at the decoding step where ((m):) becomes empty and the backtracking budget is depleted. Right: The right column displays the corresponding decoding probability distribution po(: T1:) generated by the LMask at each step.
and bright yellow indicates
24

---

Published as conference paper at ICLR 2026
Potential and the Overestimation
R=
Decoding Probability Distribution
08
Node Index (
Node Index f
10
10
15
15
0.2
Decoding Step (f)
R 10k
Decoding Step (f)
1.0
Node Index (
Node Index (
0.6
18
15
0.0
Decoding Step
R= 11k
Decoding Step
1.0
Node Index (0
Node Index (0
10
10
0.4
16
Decoding Step (f)
Decoding Step (r)
i ((m)))
e ((m.)) \ (((ma)
E S(m)))
Selected action
Figure 7: Visualization of the LazyMask decoding process challenging TSPDL instance requiring extensive backtracking. The rows depict three decoding trials with varying backtracking budgets: R (Top), R 10k (Middle), and R 11k (Bottom). The first two trials (R 0. R 10k)
fail to find a feasible solution, whereas the R = 11k trial successfully identifies complete, feasible route. Left: The left column visualizes the relationship between the true potential set ((T..)) and its overestimation $(m1:)). each decoding step (x-axis), each node (y-axis) is color-coded based on its set membership. Dark blue indicates & $(T1:)). teal green indicates E ((T1e) ((T..)) and bright yellow indicates i S(T1a). The node selected by the policy at each step is indicated by a red bounding box. The visualization for any failed trial is truncated at the decoding step where ((m:) becomes empty and the backtracking budget is depleted. Right: The right column displays the corresponding decoding probability distribution pe T1a) generated by the LMask at each step.
25

---

Published as a conference paper at ICLR 2026
E.5 EFFECT OF THE PENALTY PARAMETER.
We amalyze the sensitivity of LMask's performance to the & penalty parameter p. The results on the hard TSPDL-50 dataset are presented in Table 6. In our experiments, we tested several fixed values for p and scheduled approach, denoted as pt. For the scheduled approach, the penalty parameter is increased exponentially over the training epochs according to the schedule pt = min(>" Po, Pinax), Our results show that
with the hyperparameters set 7 1.01, Po 0.5, and Pmax small, fixed penalty (o 0.5) leads to training instability, resulting in high infeasibility and a large optimality gap. Conversely, large fixed penalty values (e.g.. P 1.5, P 2) reduce infeasibility but at the cost of an increased optimality gap. The scheduled approach (pt) provides better training stability and strikes an effective balance, achieving low infeasibility rates and small optimality gap that slightly outperform our default setting of =
Table 6: Results on the hard TSPDL-50 dataset with different p during training.
Sol. Infeas.
Ins. Infeas.
Obj.
Gap
0.5
7.10%
2.45%
13.71
3.97%
0.19%
0.04%
13.57
2.52%
1.5
0.07%
0.03%
13.58
2.64%
2
0.02%
0.01%
13.60
2.78%
p
0.18%
0.00%
13.56
2.48%
E.6 GENERALIZATION AND SCALABILITY
E. GENERALIZZTION ACROSS TIME WINDOW WIDTHS
We assess the generalization ability of L.Mask on hard TSP datasets, by evaluating performance on test instances with varying maximum time window widths w = 20, 60, 200, while keeping the training distribution fixed
100. As shown in Table 7, both neural baselines, PIP and PIP- D, exhibit large performance fluctuations as w deviates from 100. In particular, although their performance improves w = 20, their infeasibility rates and optimality gaps increase significantly at w = 60 and to 200, compared to their performance on w 100 reported in Table of the main paper. This indicates limited generalization when the maximum time width changes. In contrast, ..ask remains consistently robust across different values of showing zero infeasibility rates in all cases, even outperforming the strong traditional solver Py in fcasibility. While its optimality gap increases at 200, it remains lower than those of PIP and PIP-D. These results demonstrate the strong generalization ability of LMask to variations in the maximum time window width.
E.6.2 SCALABILITY TO LARGE-SCALE PROBLEM INSTANCES
To assess the scalability of LMask, we conduct experiments on the hard TSPTW-500 dataset, which contains 128 hard TSPTW instances with
500. We do not include PIP and PIP-D in this evaluation as their official source code repository does not offer pretrained models specifically for the hard TSPTW-500 dataset. Due to the substantial computational cost per instance at this scale, traditional solvers such as PyPR LKH3, and OR-Tools are no longer able to process multiple instances in parallel using multi-core CPUs as done in the main experiments. Instead, each instance is solved sequentially using all available 32 CPU cores. Therefore, we report the average runtime per instance for a fair comparison. As for the size-specific hyperparameters, we set the time limit of VRP and OR-Tools for solving each instance 4 minutes. LKH3 is run with maximum of 10000 trials and 10 runs. L.Mas''s 's inference is performed with a backtracking budget of R = 600.
As shown in Table 8, OR-Tools and both greedy heuristics fail to produce any feasible solutions at this scale, with instance infeasibility rates reaching 100%. In contrast, traditional solvers such as VRP and LKH still manage find feasible solutions for the majority of instances, achieving low
26

---

Published as a conference paper at ICLR 2026
infeasibility rates of 3.12% and 2.33%, respectively. Notably, LMask achieves zero infeasibility rates and maintains a low optimality gap of 0.53%, demonstrating superior scalability.
Table Results on datasets with varying maximum time window widths w. All models are trained on hard TSPTW instances with 50 and 100.
Width
W
20
w 60
200 1
Infeasible
Infeasible
Infeasible
Method
Gap
Gap
Gap
Sol.
Ins.
Sol.
Ins.
Sol.
Ins.
PyVRP
12.6%
2.71% %
0.03%
PIP
3.75%
2.54%
0.08%
6.54%
3.64%
0.04%
10.49%
5.69%
3.57%
PIP-D
3.08%
1.82%
0.08%
8.72%
4.67%
0.08%
18.15%
10.35%
6.58%
LMask
0.00%
0.00%
0.00%
0.00%
0.00 %
0.01 %
0.00 %
0.00%
2.99 %
Table 8: Results on hard TSPTW-500
Method
Sol. Infeas.
Ins. Infeas.
Obj.
Gap
Avg. Time
PyVRP LKH
3.12%
256.59
4m
2.33%
256.65
0.00%
13m
OR-Tools
100.00%
17s
Greedy-L
100.00%
100.00%
1s
Greedy-C 100.00%
100.00%
1s
LMask 0.00%
0.00%
257.92
0.53%
16s
E.7 PERFORMANCE OF LMASK USING DIFFERENT BACKBONE MODELS
LMask is model-agnostic and can combined with any auto-regressive backbone model. The default backbone model used in main experiments POMO (Kwon et al., 2020). Here we replace with the recent ReLD model (Huang et al., 2025), which enhances the POMO decoder by adding residual connections and a two-layer feed-forward network. The performance comparison of different backbone models on various datasets is presented in Table 9, The results show that a stronger backbone model further boosts the performance of LMask.
Table 9: Performance comparison of LMask using different backbone models.
Nodes
50
Infeasible
Infeasible
Dataset
Hardness
Model
Sol.
Inst.
Obj.
Gap
Time
Sol.
Inst.
Obj.
Gap
Time
POMO
0.06%
0.00%
7.45
2.02%
0.01 % 0.02%
0.00%
10.50
3.11%
17s
Easy
ReLD
0.01% %
0.00%
7.43
1.66%
7s
0.00%
10.48
2.85 %
218
TSPTW
Medium
POMO
0.04%
0.00%
13.25
1.68%
6s
0.05%
0.00%
19.51
4.23%
18s
ReLD
0.03%
0.00%
13.23
1.58
7s
0.03%
0.00%
19.31
3.13%
22s
Hard
POMO
0.00%
0.00%
25.71
0. 10%
0.00%
0.00%
51.38
0.21%
18%
ReLD
0.00%
0.00%
25.70
0.06%
0.00%
0.00%
51.36
0.16%
22s
POMO
0.03%
0.01%
11.14
2.75%
0.20%
0.05%
17.04
4.24%
15s
Medium
TSPDL
RcLD
0.03%
0.00%
11.06
2.00%
7s
0.18%
0.03%
16.91
3.42%
15s
Hard
POMO
0.19%
0.04%
13.57
2.52%
6s
0.80%
0.26%
21.63
4.34%
15s
ReLD
0.13%
0.02%
13.47
1.80%
7s
0.52% %
0.11
21.53
3.84 %
16s
E.8 SAMPLING PERFORMANCE
We evaluate the performance of neural methods under sampling decoding. Each method samples solutions per augmentation, where S is varied 3, 10, and 30. The 8x dihedral augmentation is
27

---

Published as a conference paper at ICLR 2026
retained, resulting in 8 x S solutions per instance. Due to memory limitations, the batch sizes adjusted accordingly. For an intuitive comparison, we also include the results under greedy decoding reported in the main paper. The results summarized in Tables 10 and 11.
Compared to greedy decoding, all methods exhibit lower instance infeasibility rates and optimality gaps under sampling decoding. Meanwhile, the solution infeasibility rates increase under sampling decoding, as the larger number of sampled solutions naturally leads to a higher proportion of infeasible ones. Remarkably, even though PIP and PIP-D generate ten times as many solutions the greedy version of LMask, they still yield higher instance infeasibility rates. In addition, their optimality gaps are generally higher than those of greedy LMask on most datasets, highlighting LMask's 's strong ability to consistently generate high-quality feasible solutions even with smaller number of samples.
Table 10: Sampling results on synthetic TSPTW datasets.
Nodes
50
100
Infeasible
Infeasible
Method
Sol.
Inst.
Obj.
Gap
Time
Sol.
Inst.
Obj.
Gap
Time
PIP
0.28%
0.01%
7.51
2.73%
0.16%
0.00%
10.57
3.78%
29s
PIP (S=
0.29%
0.01%
7.49
2.45%
19s
0.17%
0.00%
10.55
3.56%
1.3m
PIP (S- 10)
0.29%
0.01%
7.47
2.20%
57s
0.17%
0.00%
10.52
3.24%
4.6m
PIP (S- 30)
0.29%
0.01%
7.45
2.03%
3.0m
0.18%
0.00%
10.50
3.04%
12.8m
PIP-D
0.28%
0.00%
7.50
2.60%
0.05%
0.00%
10.66
4.62%
31s
Easy
PIP-D (S
0.31%
0.00%
7.48
2.33%
20s
0.07%
0.00%
10.64
4.40%
1.5m
PIP-D (S 10)
0.29%
0.00%
7.46
2.06%
1.1m
0.06%
0.00%
10.60
4.05%
5.0m
PIP-D (5 30)
0.30%
0.00%
7.44
1.89%
3.3m
0.06%
0.00%
10.58
3.82%
14.0m
LMask
0.06%
0.00%
7.45
2.02%
0.01%
0.00%
10,50
3.11%
LMask (S- 3)
0.06%
0.00%
7.44
1.85%
11s
0.02%
0.00%
10.53
3.31%
35s
L.Mask (S- 10)
0.07%
0.00%
7.42
1.51%
17s
0.02%
0.00%
10.48
2.89%
1.2m
LMask (S- 30)
0.06%
0.00%
7.40
1.30%
33s
0.02%
0.00%
10.45
2.61%
3.
PIP PIP ($ = 3)
4.82%
1.07%
13.41
2.93%
10s
4.35%
0.39%
19.61
4.79%
29s
4.98%
0.68%
13.36
2.55%
19s
4.55%
0.19%
19.54
4.37%
1.3m
PIP (S 10)
4.96%
0.46%
13.32
2.26%
58s
4.52%
0.10%
19.45
3.93%
4.5m
PIP 30)
4.98%
0.25%
13.30
2.06%
2.9m
4.50%
0.06%
19.39
3.60%
12.7m
Medium
PIP-D PIP-D (5 3)
4.14%
0.90%
13.46
3.31%
9s
3.46%
0.03%
19.80
5.76%
31s
4.30%
0.54%
13.41
2.95%
20s
3.87%
0.00%
19.73
5.41%
1.5m
PIP-D ($ 10)
4.32%
0.36%
13.37
2.66%
1.1m
3.80%
0.00%
19.63
4.86%
5.0m
PIP-D (S 30)
4.31%
0.27%
13.34
2.44%
3.3m
3.82%
0.00%
19.55
4.47%
14.0m
LMask
0.06%
0.00%
13.25
1.73%
6s
0.05%
0.00%
19.51
4.23%
18s
LMask (S 3)
0.08%
0.00%
13.30
2.1%%
14s
0.10%
0.00%
19.48
4.05%
40s
LMask (S 10)
0.07%
0.00%
13.23
1.60%
24s
0.10%
0.00%
19.40
3.64%
1.3m
LMask (S= 30)
0.07%
0.00%
13.19
1.25%
55s
0.11%
0.00%
19.34
3.33%
3.2m
PIP PIP (S = 3)
5.65%
2.85%
25.73
0.18%
9s
31.74%
16.68%
51.48
0.37%
28s
5.81%
2.28%
25.72
0.16%
19s
32.47%
11.83%
51.44
0.33%
1.3m
PIP (S- = 10)
5.80%
1.89%
25.72
0.15%
58s
32.59%
9.66%
51.43
0.30%
4.5m
PIP (S 30)
5.79%
1.68%
25.72
0.14%
2. 2.9m
32,58%
7.97%
51.42
0,27%
12.7m
PIP-D D
6.44%
3.03%
25.75
0.27%
9s
13.59%
6.60%
51.43
0.32%
31s
Hard
PIP-D (5- 3)
6.59%
2.40%
25.75
0.25%
20s
13.99%
5.32%
51.41
0.29%
1.5m
PIP-D (S- = 10)
6.56%
10%
25.74
0.24%
1.1m
13.93%
4.54%
51.41
0.27%
5.0m
PIP-D (S- 30)
6.58%
1.88%
25.74
0.23%
3.3m
13.92%
4.05%
51.40
0.26%
14.0m
LMask
0.00%
0.00%
25.71
0.10%
6s
0.00%
0.00%
51.38
0.21%
18s
LMask (S- -3 3)
0.00%
0.00%
25.70
0.09%
10s
0.00%
0.00%
51.37
0.19%
40s
LMask (S- 10)
0.00%
0.00%
25.70
0.08%
17s
0.00%
0.00%
51.36
0.18%
1.3m
LMask (S- =30 =30)
0.00%
0.00%
25.70
0.08%
33s
0.00%
0.00%
51.36
0.16%
3.2m
E.9 STABILITY ANALYSIS
We investigate the stability of LMask under sampling decoding at inference. In Figure 8, we present box plots of the optimality gaps and solution infeasibility rates across 10 different random seeds on medium TSPTW-50 and TSPDL-50 datasets. Across both datasets and all tested random seeds, both metries remain highly stable, with total variations staying below 0.02%. These results demonstrate
28

---

Published as a conference paper at ICLR 2026
Table 11: Sampling results on synthetic TSPDL datasets.
Nodes
50
1 100
Infeasible
Infeasible
Method
Sol.
Inst.
Obj.
Gap
Time
Sol.
Inst.
Obj.
Gap
Time
PIP
1.75%
0.17%
11.23
3.59%
2.50%
0.16%
17.68
8.10%
21s
PIP (S 3)
L.87%
0.13%
11.19
3.23%
15s
2.68%
0.10%
17.62
7.68%
52s
PTP (5 10)
1.84%
0.11%
11.16
2.93%
45s
2.68%
0.08%
17.53
7.14%
2.9m
PIP (S 30)
1.84%
0.11%
11.14
2.73%
2.5m
2.70%
0.06%
17.46
6.74%
8.8m
Medium
PIP-D
2.29%
0.22%
11.26
3.96%
1.83%
0.23%
17.80
8.84%
23s
PIP-D (S 3)
2.42%
0.10%
11.22
3.56%
17s
1.98%
0.14%
17.73
8.40%
59s
PIP-D (S 10)
2.44%
0.07%
11.19
3.19%
50s
1.95%
0.09%
17.63
7.78%
3.4m
PIP-D (S 30)
2.45%
0.07%
11.16
2.94%
2.8m
1.96%
0.07%
17.56
7.36%
10.0m
LMask
0.03%
0.01%
11.14
2.75%
0.20%
0.05%
17.04
4.24%
15s
LMask (5 3)
0.04%
0.01% %
11.10
2.43%
13s
0.21%
0.04%
16.99
3.88%
28s
LMask (S 10)
0.04 %
0.01 %
11.07
2.15%
17s
0.21 %
0.04%
16.91
3.43%
51s
LMask (S- 30)
0.04%
0.01%
11.05
1.97%
29s
0.21%
0.04%
16.86
3.13%
2.0m
PIP
4.83%
2.39%
13.63
3.42%
29.34%
21.65%
22.35
12.87%
20s
PIP (S = 3)
5.06%
2.14%
13.59
3.09%
15s
29.60 60%
20.30%
22.30
12.37%
52s
PIP (S 10)
5.07%
2.00%
13.56
2.83%
44s
29.52%
19.53%
22.18
11.59%
3.0m
PIP (S 30)
5.07%
1.90%
13.54
2.64%
2.5m
29.52%
18.92%
22.08
11.00%
8.8m
PIP-D
4.16%
0.82%
13.79
4.28%
13.51%
8.43%
22.90
12.53%
23s
Hard
PIP-D (S-
4.43%
0.59%
13.74
3.89%
17s
13.76%
7.49%
22.82
11.99%
1.0m
PIP-D (S- 10)
4.47%
0.40%
13.70
3.55%
51s
13.77%
6.82%
22.71
11 11.00%
3.4m
PIP-D (S- 30)
4.43%
0.38%
13.67
3.32%
2.8m
13.75%
6.55%
22.63
10,80%
10.0m
LMask
0.19%
0.04%
13.57
2.52%
0,80%
0.26%
21.63
4.34%
15s
L.ask (5
0.22%
0.04%
13.53
2.22%
13s
0.87%
0.22%
21.56
3.99%
29%
LMask =10)
0.22%
0.03%
13.50
1.98%
18s
0.87%
0.21%
21.48
3.61%
52s
LMask (S 30)
0.22%
0.03%
13.48
1.82%
29s
0.87%
0.18%
21.42
3.32%
2.0m
that LMask yields highly consistent performance when using sampling decoding at inference, despite the inherent randomness in solution generation.
1.610
0.075
2.156
0.044
1.605
0.074
Solution Infensibliity
2.154
0.042
Infeusibiin Mussiibiitt
Gap (5%)
1.600
0.073
Gap
2.152
0..40
1.595
0.072
2.150
0.038
1.590
0.071
2.148
0.036
Gap
Sol. Infeas.
Gap
Sol. Infeas.
(a) Medium T5PTW-50
(b) Medium TSPDL-50
Figure 8: Box plots of optimality gaps and solution infeasibility rates of LMask under sampling decoding across 10 random seeds. Each box shows the interquartile range (25th-75th percentile). the horizontal line indicates the median, and the whiskers extend to the minimum and maximum within 1.5 times the interquartile range.
E. PERFORMANCE ON THE TSPTW BENCHMARK
We evaluate LMask framework on the TSPTW benchmark (Dumas et al., 1995) to validate our innovation. Although comprehensive tests are conducted on TSPTW benchmark instances, decide directly reference the original test results from Appendix D.7 in the article (Bi et al., 2024) due to inaccurate replication attempts of PIP and PIP-D. Additionally, to ensure consistency in research comparisons, the benchmark instance
selected remains fully aligned with those
29

---

Published as a conference paper at ICLR 2026
used in the original study. Results show that compared to the neural baselines, LMask framework significantly reduces the infeasibility rate and improves solution quality.
Table 12: Model performance the benchmark datasets (Dumas et al., 1995).
PIP
PIP-D
LMMask
PIP
PIP-D
L.Mask
Instance
Opt.
Obj.
Gap
Obj.
Cap
Ohj.
Gap
Instance
Opt.
Obj.
Gap
Obj.
Gap
Ohj.
Gap
n20w20.000
389
2.91%
2.91%
378
n4Dx400003
4966
4.64%
497
4.85%
0.00%
n20w 20.022
286
292
2.10%
292
2. 2.10%
286
010095
440440:0014
452
460)
1.77%
n20w 20.003
394
194
0.00%
n40w400.00
453
470
3.75%
471
3.97%
458
1.10%
n20w20.000 004
396
2.27%
2.27%
n40w60
220020.005
352
360
2.27%
2.27%
352
0.00%
640w60.007
470
502
6.81%
493
4.89%
n20w10.001
251
276
8.66%
279
9.84%%
257
1,88%
e00w600003
408
414
1.47%
n20w40.002
333
347
4. 1.00%
139
1.80%
333
0.00%
n40w60.004
382
406
6.25 6.28%
420
9.95%
343
2,88%
a20w10.000
4.73%
4.73%
0.00%
342
4.27%
344
4.88%
n20w-10.004
388
10]
3.35%
401
3.35%
389
0.26%
n/00800.001
107
3.01%
107
3.041
395
0.00/%
n20w4000005
288
204
2.08%
302
4.86%
289
0.35%
n40w80.002
431
44%
3.94%
452
4.87%
433
0.46%
n20w60,001
335
349
1.18%
353
5.37%
336
0.30%
n10w80.000
412
144
7.77%
454
10.19%
416
0.97%
n20w60.00
3.28%
6.56%
0.82%
n10w
430
3.12%
n20w60.003
352
358
L.70%
358
L.70%
352
0.00%
n40m80,005
344
362
5.23%
379
10.17%
344
0.00%
a20w60.001
260
298
6.13%
289
3.21%
282
0.71%
n60w
4.8
461
0.66%
n20w60.000 .00
338
385
13.91%
6.80%
340
0.59%
n60m 002
498
540
8.4356
548
10.04%
522
4.82%
a20w80.000
5.47%
5.47%
n60w
646
17.45%
7.64%
n20w80.002
353
347
2. 6666
360
6.51%
338
0.00K
860
566
611
7.949
632
11,66%
587
3.71%
a20w80.003
320
128
2 2.50%
328
2.50%%
320
0.00%
n60m80.000
468
535
14.32%6
491
4.91%
n20w80.004
304
341
12.17%
339
11.51%
324
6.58%
n80w60.000
554
582
5.05%
563
1.62%
020080.005
264
14.39%
14.39%
272
n80a000.02
678
2.21%
a40w20.001
500
500
0.00%
n80m60.004
619
678
9.53%
642
3.72%
2402200002
552
610
10.511
152
0.00%
n80w600005
575
600
4.35%
20,00.
478
507
6.07%
478
0.00%
n80m800000
624
3.04%
#40w 20.004
-044
419
3.71%
418
3,47%
407
0.74%
n80w800007
592
624
5.41%
638
7.77%
614
3.72%
n40w 20.055
299
501
01.40%
080
589
64%
10.02%
674
14.43%
623
5.77%
n10w-10.001
-65
165
0.00%
n80w80.000
594
674
13.47%
676
13,80%
619
4.21%
o40w40.002
4.77%
1.95%
n80w80
2.63%
Average Gap
5.2%
5.3%
0.6%
Average Gap
7.4%
8.5%
2.6%
Infeusible Rate
22.2%
14.8%
0.0%
Infeusible %
25.9%
37.9%
0.0%
F RUNTIME DISCUSSION
F.1 INFERENCE-TING EVALUATION PROTOCOL AND CPU-ONLY RESULTS
It is hard to achieve absolutely fair comparison of the time between CPU-based traditional solvers and GPU-based solvers due to hardware difference. As a widely adopted convention in the neural combinatorial optimization community, we have run traditional solvers with 32 CPUs in parallel to mitigate this unfairness. To provide further clarification, we have also run LMask using only CPUs. The results. presented in Table 13, demonstrate that LMask remains substantially faster than the traditional solvers.
F.2 BACKTRACKING OVERHEAD
The runtime of LMaask can be decomposed into four components: (1) network forward pass; (2) lookahead; (3) backtracking; and (4) miscellaneous operations such as distance matrix precomputation and tour length evaluation. We then elaborate on the overhead induced by backtracking. The main source of cost comes from reduced parallelization due to instance heterogeneity and from increased forward passes in the decoder. The backtracking operation itself is lightweight, as it only rolls back via a stack. To mitigate the cost from heterogeneity, one can selectively process only the instances still in forward construction. In fact, this approach used during the inference phase with greedy decoding. As shown in Figure 2(b), on the hard TSPTW- 100 dataset, increasing the backtracking budget from 0 to 100 adds only about seconds to the inference time, which is a marginal increase. However, during the training phase, which employs a multi multi-sampling decoding scheme. this selective processing would impair the computational efficiency of the cross- attention mechanism in the decoder. We believe that more efficient implementations could further reduce this training overhead.
To clearly demonstrate the computational overhead from backtracking and compare training times with other methods, we provide training time comparison in Table R5. Note that we have optimized the implementation of lookahead from the original PIP source code by reducing the use of indexing operations, which are very time-consuming on GPUs. This optimization significantly improves
30

---

Published as a conference paper at ICLR 2026
efficiency. As result, with the addition of backtracking, the total training time for LMask remains shorter than that PIP.
Table 13: Inference time using 32 CPUs. Time is reported in minutes (m), hours (h), and days (d).
Hardness
Method
50
100
PyVRP
1.7h
4.3h
Easy
LKH3
1,9h
7.2h
LMask
3.2m
11.4m
PyVRP
1.7h
4.3h
Medium
LKH3
2.9h
10.3h
LMask
3.8m
11.7m
PyVRP
1.7h
4.3h
Hard
LKH3
2.3h
1.3d
LMask
5.6m
12.4m
Table 14: Training time (days).
Method
100
LMask
4.2d
7.8d
PIP
4.7d
28.4d
PIP-D
3.6d
12.2d
G LICENSES FOR EXISTING ASSETS
The used assets in this work are listed in Table 15, which are all open-source for academic research. We will release our source code with the MIT License.
Table 15: Used assets, licenses, and their usage.
Type
Asset
License
Usage
LKH3 (Helsgaun, 2017)
Available for academic use
Evaluation
OR-Tools (Furnon & Perron, 2024)
Apache-2.0 license
Evaluation
VRP (Furnon & Perron, 2024)
MIT License
Evaluation
Code
RL4CO (Furnon Perron, 2024)
MIT License
Revision
PIP (Furnon & Perron, 2024)
MIT License
Revision
Datasets
Dumas al. (Dumas et al., 1995)
Available for academic
Evaluation
H
THE USE OF LARGE LANGUAGE MODELS
Large language models are used only for writing.
31


Reviews:
[{"review_id": "4Of3q2rqos", "reviewer": "Reviewer_nv24", "summary": "The paper aims to address the challenge of constrained routing problems. It introduces the LazyMask decoding method, which lazily refines feasibility masks with the backtracking mechanism. In addition, it employs the refinement intensity embedding to encode the search trace into the model. The proposed method is tested on TSPTW and TSPDL.", "questions": "-  Is TSL initialization the same as PIP?\n- What are Greedy-C and Greedy-C in Table 9?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper aims to address the challenging constrained routing problems in neural methods.\n- The idea of using lazy masks to correct the decoding errors on the nonlinear routing problems is interesting.\n- The performance on the complex TSPTW and TSPDL is good, with low infeasibility and competitive solution quality. The experiments are thorough.", "weaknesses": "- The backtracking mechanism introduces additional computational overhead. \n- The idea is not that impressive. PIP adopts a lookahead mask, whereas LMask uses backtracking. Also, it would be better to theoretically and empirically analyse the computational complexity of these two methods. Why is LMask, with a two-step lookahead and backtracking, reported to be faster than PIP, which also uses a two-step lookahead but without backtracking?\n- The selection criteria for the backtracking budget on each problem are unclear.\n- The theoretical guarantee provided for LMask relies on the assumption of an infinite computational budget, which is impractical in real-world scenarios.\n- The proposed method appears to be specifically tailored for constrained nonlinear problems. Can it also be applied to constrained linear problems?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3KhSPy6IAh", "reviewer": "Reviewer_jBMF", "summary": "The paper proposes LMask, a learning framework for constrained routing that decodes with a LazyMask mechanism combining lightweight lookahead with adaptive backtracking. It introduces refinement intensity embedding (RIE) to encode the backtracking trace into the decoder. Theoretical guarantees are also provided: with unbounded backtracking, LazyMask generates only feasible solutions and assigns non-zero probability to all feasible ones, and a probabilistic optimality bound is analyzed.", "questions": "Could the proposed backtracking mechanism be extended to large language model (LLM)-based solvers? While LLMs do not share the same MDP formalism, they are also autoregressive. I am curious about whether LazyMask-style backtracking, and RIE-like signals might transfer to general sequential models. This is only for discussion; no additional experiments are requested.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe proposed LMask contributes significantly to the current masking mechanism, which excludes the infeasible actions perfectly and efficiently via a smart backtracking design. \n\n2.\tProposition 4.1 provides a strong feasibility guarantee, lending theoretical grounding to masking-based constraint handling.\n\n3.\tThe method achieves notable improvements on the TSPTW and TSPDL benchmarks, while maintaining competitive inference times and demonstrating robustness across instance scales and distributions", "weaknesses": "The theoretical contribution of Theorem 4.3 appears limited for practice. Its bound relies on an approximation assumption and does not directly inform the backtracking design or concrete hyperparameter choices, thus offering limited guidance for algorithmic tuning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "m03Hh1NDLQ", "reviewer": "Reviewer_V3Tu", "summary": "This paper proposes LMask, a novel method for enhancing auto-regressive neural solvers on constrained routing problems. Specifically, it integrates a backtracking mechanism during decoding to prevent from infeasible solutions, and designs a refinement intensity embedding method to mitigate representation ambiguity induced by backtracking. The validity of the proposed method is theoretically analyzed under specific assumptions. Experiments on two typical constrained routing problems, TSPTW and TSPDL, demonstrate its superior performance over existing methods.", "questions": "1. How does LMask perform when paired with other architectures, such as LEHD?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed method is well-motivated. The paper is well-written and easy to follow.\n2. On the two benchmark problems TSPTW and TSPDL, the results clearly demonstrate the superiority of LMask against competitors. \n3. The authors provide extensive ablation and hyperparameter studies, with clear analysis.", "weaknesses": "1. The meaning of the theoretical parts is limited, since the conditions and assumptions seems much too strict.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SXpsbNKn69", "reviewer": "Reviewer_KHo7", "summary": "This paper presents LazyMask (LMask), a new decoding mechanism coupled with refinement intensity embedding (RIE) that augments model state with search-trace information for solving hard-constrained routing problems, specifically TSPTW and TSPDL. The key design is integrating a backtracking-based masking strategy that enables neural constructive methods to generate feasible solutions more effectively. Results on TSPTW and TSPDL show that LMask achieves lower infeasibility rates and improved solution quality compared to baselines.", "questions": "Please see my comments above.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is generally well-written with clear presentation and logical structure. \n- The proposed LMask represents a meaningful advancement for neural constructive methods applied to TSPTW and TSPDL.\n- The inclusion of theoretical analysis provides valuable insights.\n- The experimental evaluation is extensive and the results are promising.", "weaknesses": "- The applicability of the Lmask seems limited. The discussions and experiments focus almost entirely on TSPTW and TSPDL, both of which involve temporal constraints. It is uncertain whether the backtracking-based masking strategy and RIE mechanism can be effectively extended to other complex constrained VRPs with different constraints.\n- The paper lacks an in-depth analysis of the gap between the true potential set $S$ and its estimation $\\hat{S}$. There is no empirical or theoretical investigation of how well such approximations work under different conditions.\n- The selection of the backtracking budget $R$ appears empirical without principled guidelines.\n- Infeasibility rates in Tables 1 and 2 are still not 0.00%, while classical methods like LKH3 achieve perfect feasibility. The paper should investigate why the Lmask still fails in those cases and what additional methods may be needed to fully close this gap.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)