Probing Neural Combinatorial Optimization Models

Zhiqin Zhang, Yining Ma, Zhiguang Cao, Hoong Chuin Lau · 2025

Read Probing Neural Combinatorial Optimization Models by Zhiqin Zhang, Yining Ma, Zhiguang Cao, Hoong Chuin Lau (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-22131.txt.

Introduction

Zhiqin Zhang, Yining Ma, Zhiguang Cao, and Hoong Chuin Lau open the black box of neural combinatorial optimization, models that learn to solve routing and scheduling puzzles. These models perform impressively, yet what their internal representations actually encode, and why they choose as they do, has stayed murky, which worries both researchers and users.

The team probes the representations with diagnostic tasks, and adds a tool that checks not just whether information is present but whether the probing coefficients are statistically meaningful. The models turn out to store low-level details needed to build solutions step by step alongside high-level knowledge that guides better global choices. Different popular architectures stamp different biases on what they learn, and the probes surface direct evidence about which representations generalize. The study is a first step toward models whose reasoning can be audited.

Catalog record

CREATORZhiqin Zhang, Yining Ma, Zhiguang Cao, Hoong Chuin Lau
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE125 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-22131

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Probing Neural Combinatorial Optimization Models Zhiqin Zhang, Yining Ma, Zhiguang Cao, Hoong Chuin Lau Abstract Neural combinatorial optimization (NCO) has achieved remarkable performance, yet its learned model representations and decision rationale remain a black box. This impedes both academic research and practical deployment, since researchers and stakeholders require deeper insights into NCO models. In this paper, we take the first critical step towards interpreting NCO models by investigating their representations through various probing tasks. Moreover, we introduce a novel probing tool named Coefficient Significance Probing (CS-Probing) to enable deeper analysis of NCO representations by examining the coefficients and statistical significance during probing. Extensive experiments and analysis reveal that NCO models encode low-level information essential for solution construction, while capturing high-level knowledge to facilitate better decisions. Using CS-Probing, we find that prevalent NCO models impose varying inductive biases on their learned representations, uncover direct evidence related to model generalization, and identify key embedding dimensions associated with specific knowledge. These insights can be potentially translated into practice, for example, with minor code modifications, we improve the generalization of the analyzed model. Our work represents a first systematic attempt to interpret black-box NCO models, showcasing probing as a promising tool for analyzing their internal mechanisms and revealing insights for the NCO community. The source code is publicly available 1 1 1 Source Code: https://github.com/123zhangzq/NeurIPS2025_probing/ . 1 Introduction Neural combinatorial optimization (NCO) has demonstrated remarkable performance in solving classic combinatorial optimization problems, such as vehicle routing, achieving results comparable to, or even surpassing, specialized heuristic algorithms such as Concorde [ 1 ] , ACO [ 2 ] , LKH3 [ 3 ] , HGS [ 4 ] . However, the underlying reasons behind these impressive results, particularly the nature of the knowledge learned by these neural models, remain largely unexplored and unclear. In this paper, we take the first step towards interpreting NCO models by probing [ 5 , 6 , 7 ] , a powerful tool that has proven successful in computer vision (CV) and natural language processing (NLP). We pioneer the first study that directly investigates the learned embeddings in deep NCO models, aiming to explore the internal mechanisms of these black-box models. In this work, we aim to address two fundamental questions regarding the representations learned by NCO models: (i) What decision-related knowledge do they acquire? (ii) How do they learn and utilize this knowledge? Addressing the First Question: Probing involves training auxiliary prediction tasks using the embeddings learned by a trained deep learning model. In the context of NLP, for instance, if a simple model (particularly a linear model) can be trained to predict linguistic information about a word (e.g., its part-of-speech tag) or a pair of words (e.g., their semantic relation) from the embeddings, we can reasonably conclude that the embeddings successfully encode this information (see [ 8 ] for more details). However, unlike NLP tasks, which naturally involve intuitive subtasks that are well-suited for probing, combinatorial optimization (CO) problems typically lack such directly applicable subtasks. To address this gap, we systematically design a set of probing tasks specifically aimed at exploring both low- and high-level decision-related knowledge within NCO models. Addressing the Second Question: Understanding how deep learning (DL) models learn and utilize decision-related knowledge remains a challenging problem. Different approaches have been proposed, such as using probing to explore decision boundaries [ 9 ] to understand in-context learning in large language models (LLMs), or identifying individual neurons whose input or output weights have high cosine similarity with the learned probe direction to detect specific neurons that encode particular knowledge [ 10 ] . In this paper, we propose a novel method called Coefficient Significance Probing (CS-Probing) to investigate the representations of deep models. CS-Probing not only identifies the most informative embedding dimensions but also quantitatively assesses their statistical significance, providing deeper insights into the model’s decision-making process. Contributions. Our main contributions are as follows: (1) We systematically design probing tasks for NCO models and demonstrate that their representations capture both low-level decision-related information (e.g., perceiving Euclidean distances) and high-level knowledge (e.g., avoiding myopic decisions based solely on distance) for decision-making. (2) Through our proposed CS-Probing, we discover that different NCO models introduce diverse inductive biases into the learned representations, resulting in varied decision-making patterns. (3) By applying CS-Probing, we identify the key embedding dimensions that encode specific knowledge within the model representations. (4) Leveraging these key dimensions, we provide evidence of the generalization capabilities of NCO models: models with superior generalization consistently utilize the same embedding dimensions across different tasks. In contrast, models whose knowledge becomes disorganized across dimensions during generalization tend to experience performance degradation. Finally, based on probing insights, we show that modifying only a few lines of code in an NCO model holds the potential to improve its generalization performance, illustrating the practical value of our proposed probing analysis. 2 Preliminaries NCO model. NCO models are a class of learning-based solvers for CO problems, with more details provided in Appendix A.1 . This paper studies the most representative transformer-based architectures (as illustrated in Figure 1 ) as examples to demonstrate how probing can explore their internal mechanisms. Taking the Traveling Salesman Problem (TSP) as an example, the raw features of nodes (e.g., xy coordinates in the Euclidean space) are first fed as inputs. These raw features are projected into a high-dimensional space through a linear projection layer. Subsequently, multiple attention mechanism layers are employed to integrate abstract features from different nodes, yielding the final representations for each node. These representations are then processed either through a compatibility calculation or directly projected to a scalar via a linear transformation, followed by a softmax operation to obtain the selection probability of the next node. Recursively, this process connects all nodes to generate the complete TSP solution. In this paper, we utilize probing to investigate the representations of three models: AM [ 11 ] , POMO [ 12 ] , and LEHD [ 13 ] . Figure 1: Two groups of NCO model architectures: (a) represents the HELD structure, as seen in AM and POMO, while (b) represents the LEHD structure. The red arrows in the figure indicate the positions where we probe the model, extracting the embeddings. Probing. We use a linear probing [ 5 , 14 , 8 , 15 , 16 , 17 ] to explore the representations of NCO models. If this linear model can accurately predict the probing tasks based on the embeddings from the NCO models, it indicates that the knowledge relevant to the probing tasks can be easily extracted from the embeddings [ 5 , 8 ] . This also suggests that the pre-trained NCO model, from which the embeddings for the probing tasks are derived, has the ability to encode this knowledge in its representations. Other interpretability approaches, including gradient-based attribution, visualization, and neuron ablation, lack the explanatory power of probing. For example, the first method reveals output sensitivity to input features but neither shows where or whether knowledge is encoded in hidden representations nor provides structural insight into how the model organizes the solution space. In contrast, probing offers a systematic interpretability framework by assessing the linear decodability of target properties from intermediate representations. For a comprehensive discussion

Read the complete text