Random Neural Insertions

• 2026-10-27
• Research blogpost
• TSP & NCO

This is a joint work with my supervisors Emanuele Natale and Frédéric Giroire.

The world of autoregressive constructive neural TSP solvers is dominated by next-visit predictions: starting from an initial city, the model predicts the next cities one by one in the sequence. This constructs the final tour, and we make sure at every step that only unvisited cities can be selected to ensure a valid solution. In comparison, a neural insertion model maintains a tour over all currently visited cities and inserts unvisited cities into its edges.

Inserting cities is more flexible and makes it possible to predict multiple insertions in parallel. Also, insertion heuristics generally perform better than the greedy next-visit heuristic, motivating my curiosity to compare their neural counterparts.

So far, only one neural insertion model has been proposed by Luo et al., 2025. In their work, they select the next city to insert as the unvisited city closest to the current tour. This limits inference flexibility. In this work we instead randomly select the cities to insert.

Highlights:

• We propose a new neural insertion TSP solver. Compared to its predecessor, it randomly selects the cities to insert in the tour.
• We design a dedicated neural architecture that is simple and effective.
• We improve training efficiency by sampling difficult samples more often.
• We exploit its flexibility to expose a time-quality trade-off. We can insert multiple cities at once to cut the total inference time, at the cost of solution quality.
• We show how using 2-OPT unlocks a divide-and-conquer solver that makes our solver scalable.
• We achieve state-of-the-art performance among constructive neural solvers and remain competitive with other types of solvers.

The Traveling Salesman Problem

The Euclidean TSP is an NP-hard problem defined by a set of N cities \{x_i\}_{i = 1}^N in the 2D Euclidean plane. The goal is to find the shortest cycle that visits all cities exactly once. City coordinates are represented by a matrix X \in \mathbb{R}^{N \times 2}. Random instances are generated by sampling cities uniformly in the unit square. Solutions are evaluated using the optimality gap:

\text{gap}(\%) = 100 * \frac{\text{cost}_{\text{pred}} - \text{cost}_{\text{opt}}}{\text{cost}_{\text{opt}}},

where \text{cost}_{\text{pred}} is the length of the predicted solution and \text{cost}_{\text{opt}} is the length of the optimal solution.

Training algorithm

Training uses supervised learning on a set of 1M random TSP instances solved to optimality with Concorde (Applegate et al., 2006). Starting from the optimal tour, we remove some random nodes while keeping track of the edge into which each should be reinserted. We ask the model to retrieve that edge for any random node we select. The node to insert is marked (see the model architecture), and the loss is computed only for this specific node. The loss is the cross-entropy over the set of edges in the tour.

Model architecture

The neural architecture needs four things:

• Represent the current tour.
• Know which city is to be inserted.
• Let information flow between cities easily (even between those that are not connected).
• Output a probability for each edge of the tour.

Another constraint is that I don't want to use GNNs. I prefer the ease of use of Transformers and their reliability. Using a GNN would open too many options.

We note the current tour of length T as the sequence of cities (t_1, t_2, \dots, t_T). Since it is a cycle, we define t_{-1} = t_T and t_{T + 1} = t_1.

Tour representation. I started with custom attention operations that, for example, allowed only currently unvisited cities to attend to visited ones. But that led to complex attention schemes, which were generally sparse and less efficient (with attention biases here and there). Instead, I propose to encode the tour simply by concatenating neighboring cities' embeddings:

\hat{x}_{t_i} = x_{t_i} \parallel (x_{t_{i - 1}} + x_{t_{i + 1}}),

where x_i \in \mathbb{R}^h is the embedding of city i. The new representation \hat{x}_{t_i} \in \mathbb{R}^{2 h} is then projected back to \mathbb{R}^h with an MLP. We consider unvisited nodes to be their own neighbors. Note that summing the neighbors' embeddings loses the tour's orientation, making the model invariant to it. We then use classical self-attention so that all nodes (visited and unvisited) can freely exchange information without wasting FLOPs.

Marking the city to insert. To specify which city is to be inserted, I use a dedicated learned embedding added to the city or cities to insert. This teaches the model to focus its predictions on the marked cities.

Visited and unvisited cities are marked with additional dedicated learnable markers.

Probability of insertion. Finally, we take the output of the last transformer layer and represent each edge by the sum of its endpoint cities' embeddings:

e_{u v} = x_u + x_v \in \mathbb{R}^h,

where u and v are two consecutive cities in the current tour. The logit for inserting an unvisited city m between cities u and v is computed using the dot product:

l_{m, u v} = \frac{x_m e_{u v}^T}{\sqrt{h}}.

Comparison with L2C (Luo et al., 2025). L2C uses a classical encoder-decoder Transformer. The encoder processes the cities' Euclidean coordinates, and the decoder generates insertion probabilities given a tour and a city to be inserted. Their model is very similar to ours and differs only slightly in the following ways:

• Tokens in their decoder are both edges (by combining nodes embeddings) and unvisited nodes.
• Each decoding iteration uses the same shared representation from the encoder.

In comparison, our tokens always represent nodes, and edges are constructed only at the very end of the model to generate the output probabilities. Also, each decoding iteration starts from a blank representation, and the Euclidean information is processed on the fly depending on the current state of the tour.

Parallel insertions

Since any unvisited node can be inserted at any time, we can ask the model to predict insertion edges for multiple unvisited nodes at the same time. As long as the predicted edges are distinct, we can safely insert those nodes in one go.

Such model is trained with multiple randomly selected unvisited cities marked during training. The loss is computed only for the marked cities.

Difficulty-based step sampling

Early steps are the hardest for the model: many cities remain unvisited, and the model must decide which edge to use for inserting a city. Therefore, we replace uniform sampling of the construction step with sampling biased toward earlier steps. This trains the model more often on harder cases and wastes less computation on simpler ones.

We sample the construction step from a \text{Beta}(1, 4) distribution, which is skewed toward the beginning of the construction process.

Greedy results

We trained 4 models, covering the following:

• Uniform step sampling (U) vs difficulty-based step sampling (D).
• Single insertion training (S) vs multiple insertions training (M).

Models are trained on 1 million TSP-256 instances for approximately 6 hours on a single RTX-5090. Multi-insertion models are trained with up to 10 insertions at the same time. We compute the cost gap relative to the optimal solution (in \%). Generation is greedy: we mark one city at a time and always select the most probable insertion.

Both difficulty-based step sampling and multi-insertion training improve training efficiency. The model wastes less training time on easy samples and is trained on many targets at the same time. However, for large-scale generalization, the model that learns most slowly (U-S) achieves the best results.

The remaining results use the D-M model. We exploit its multi-insertion capability and rely on a divide-and-conquer approach to tackle large TSP-10,000 instances.

Multi-insertion analysis

Multi-insertion models can solve an instance faster by sampling multiple unvisited cities to insert concurrently. This allows them to trade solution quality for computation time:

We can verify that the model struggles when multiple cities are marked at the same time by comparing solutions obtained by marking cities in parallel with those obtained by marking them sequentially but inserting them all at once.

The difference is more pronounced on harder instances, which makes sense because the model needs more brain juice there.

Sparse solver

Most neural TSP solvers admit a sparse version that allows large-scale instances to be solved in a manageable amount of time. It is not obvious how to apply the usual approach of giving a reduced set of cities to our model. We propose a simple divide-and-conquer approach in which sub-instances are sampled from the original large instance, solved independently, and then combined. Partial solutions are appended and we use 2-OPT to repair the resulting global solution.

Using sub-instances avoids giving all 10,000 cities to the model. The sparse solution followed by 2-OPT repair takes 0.3 minutes with sub-instances of size 500.

Sparse Random-Reconstruct (RRC). We can improve the solution further with RRC, at the cost of a longer total runtime. RRC iteratively destroys the best solution and resolves the resulting sub-instance for a fixed number of iterations. In our implementation, we select a random city and its kNN neighbors. We remove those cities from the solution to form a new sub-instance. Our model generates a solution for this sub-instance, which we then recombine with the original solution using 2-OPT. We keep the resulting solution if it is better than the previous one.

Putting it all together

We can finally compare our model with other state-of-the-art neural TSP solvers. Every solver is evaluated with a batch size of 1 on my RTX-5090 and on the same set of instances. We report the total solving time. There are 128 random instances for each size from TSP-100 to TSP-1000, solved to optimality using Concorde. There are also 10 random TSP-10,000 instances, solved to near-optimality with LKH.

For instances with fewer than 1,000 cities, we take the best solution out of 128 generated ones. For the TSP-10,000 instances, we use the sparse-RRC decoding algorithm with 1,000 RRC iterations and sub-instances of size 500. All solutions are generated with 10 insertions in parallel. We obtain different solutions for the same instance by shuffling the insertion order.

We call our solver Random Neural Insertions (RNI).

BQ-NCO (Drakulic et al., 2023), DGL (Xiao et al., 2025), SIL (Luo et al., 2024), PENS-AR (Pereira et al., 2026) and L2C (Luo et al., 2025) are other constructive neural solvers, with L2C being the only other insertion model. They are evaluated with their own best decoding algorithms.

COExpander (Ma et al., 2025), FastT2T (Li et al., 2024), and MaskCO (Chen et al., 2026) are discrete diffusion solvers. UDC (Zheng et al., 2024) is a divide-and-conquer solver similar to our sparse approach.

Note that BQ-NCO, PENS-AR, DGL, and L2C are trained on TSP-100 instances, while the other approaches are trained at the same scale at which they are evaluated. Our solver is trained on TSP-256 instances (training on TSP-100 showed overfitting behaviour).

Overall, performance is highly competitive. RNI comes out first among the other constructive solvers and is quite comparable to non-constructive approaches.

Extra

Tour encoding variants. We initially played with multiple attention ideas:

• Dedicated MHA layer with attention bias relative to the tour distance (only the visited nodes would participate).
• Dedicated MHA layer with attention bias relative to the insertion cost (only unvisited nodes would attend to visited nodes).
• Mixing both attentions at the same time.

Overall, these approaches added a lot of complexity for little gain, so we dropped them and used our simpler tour encoding. The most promising results were obtained with three dedicated MHAs: one for unvisited nodes over insertion edges, one for visited nodes over themselves, and one global MHA without any bias. But the three attention operations required per layer made this approach too expensive.

Architecture details. Coordinates are encoded using 2D RoPE, similar to PENS-R. The markers (insertion, visited, and unvisited) are added at the beginning of every layer during tour encoding.

Marker schedules. We can vary the number of insertions m(t) during solution generation:

\begin{aligned} m_\text{fixed}(t) &= m_\text{max} \\ m_\text{linear}(t) &= \lfloor t \times m_\text{max} + (1 - t) \times 1 \rceil \\ m_\text{reversed linear} &= \lfloor t \times 1 + (1 - t) \times m_\text{max} \rceil, \end{aligned}

where t = \frac{N_\text{visited}}{N} \in [0, 1] is the current progress of the solution generation. Up until now, we've been using the fixed schedule.

It is unclear why the reversed linear schedule works so well on TSP-1000. We expect the linear schedule to consistently outperform the fixed schedule, with only a small increase in computation.

Entropy-based insertion order. Instead of randomly selecting the unvisited cities to insert, we use the model's insertion confidence scores to decide which city to insert next.

At each step, we sample 10 unvisited cities, and the model predicts an insertion distribution over the current tour edges for each city. For a city m, we compute the normalized entropy of its predicted distribution p_m:

H(m) = -\frac{1}{\log T}\sum_{e=1}^T p_m(e)\log p_m(e),

where T is the number of edges in the current tour.

Compared to the single-insertion baseline, using an entropy-based insertion priority leads to better solutions. Compared with 10 parallel marks and best-of-10, it performs worse on TSP-100 to TSP-500, but is slightly better on TSP-1000. A promising next step would be to predict insertion order directly rather than using this entropy heuristic.