Recently, the Intelligent Quantum Computing and Simulation Group at the Beijing Academy of Quantum Information Sciences (BAQIS), in collaboration with the Institute of Physics, Chinese Academy of Sciences, made significant progress in AI-based solvers for large-scale combinatorial optimization problems. The research group, for the first time, directly incorporated an approximation strategy developed in condensed-matter many-body physics for strongly correlated systems into the low-level architecture of artificial intelligence models, and proposed LoRe, short for Local Recompute, a training-free and plug-and-play acceleration framework that can be applied at the inference stage. The related results, titled “LoRe: Adaptive Interaction-Evaluation Routing with Per-Step Interaction Budgets for Iterative Graph Solvers,” have been accepted by the 2026 International Conference on Machine Learning (ICML 2026), a top-tier international conference in artificial intelligence, and will be presented at the main conference.

The International Conference on Machine Learning (ICML) is one of the most influential top-tier international conferences in the field of machine learning. It focuses on machine learning theory, algorithms, and their applications across artificial intelligence, and enjoys broad academic influence worldwide. Together with NeurIPS and ICLR, ICML is widely regarded as one of the three leading conferences in artificial intelligence. ICML 2026 will be held in Seoul, South Korea, from July 6 to 11, 2026.

Combinatorial optimization is a core problem in operations research and artificial intelligence, and is widely encountered in decision-making systems such as real-time scheduling and network resource allocation. In recent years, AI solvers based on diffusion models and graph neural networks have demonstrated excellent performance on classical tasks such as the maximum independent set (MIS) problem and the traveling salesperson problem (TSP). However, on large-scale complex networks, AI solvers face a severe computational bottleneck: at each step of iterative evolution, the model needs to perform dense evaluation over all edges in the entire graph to resolve system conflicts. This full-scale evaluation causes both computational cost and peak GPU memory consumption to increase sharply and approximately linearly with graph size. For large-scale graphs, this often leads to out-of-memory (OOM) failures, greatly limiting practical applications.

The research group pointed out that, at the underlying logic level, this AI computational challenge is highly similar to the challenge encountered in condensed-matter physics when dealing with strongly correlated many-body systems. In strongly correlated systems such as the Hubbard model, a large number of electrons are strongly coupled with one another through Coulomb interactions. Attempting to exactly solve all interactions over an almost infinite macroscopic lattice is computationally infeasible.

To address this quantum many-body problem, physicists developed dynamical mean-field theory (DMFT) and its spatial extension, cluster dynamical mean-field theory (C-DMFT). The core physical idea is to divide a large and complex system into two parts: a cluster that contains the key local strongly correlated interactions, and a bath that represents the remaining lattice environment. In this way, physicists can accurately treat complex many-body interactions inside the cluster, while describing the bath approximately through a self-consistent effective field. Through the dynamical coupling between the cluster and the bath, this theory greatly reduces computational complexity while effectively capturing local dynamics and finite-range spatial correlations, and maintains consistency with the overall lattice environment through self-consistency conditions.

The research group found that this physical picture has a rigorous correspondence with the working mechanism of AI-based graph solvers. In combinatorial optimization graphs, variables are tightly coupled by task constraints. For example, in MIS, adjacent vertices cannot be selected at the same time. This is essentially equivalent to a complex spin or particle interaction model. During the solving process, these constraints form conflict hotspots whose locations evolve dynamically. From a physical perspective, they can be viewed as strongly correlated degrees of freedom that require high-precision treatment in many-body systems. Previous static sparsification methods process only a fixed subset of interactions, making it difficult for them to capture the spatiotemporal evolution of these correlation hotspots in time. As a result, many critical conflicts may be missed, leading to a significant degradation in solution quality.

At the low-level operator layer of graph neural networks, the LoRe framework reproduces the cluster-bath approximation strategy inspired by C-DMFT. At each step of the evolution process, LoRe dynamically assigns a small subset of interactions with the highest current conflict level and uncertainty to the cluster, where accurate forward propagation computation is performed. The remaining interactions are assigned to the bath and represented collectively by a lightweight global approximate signal. This cluster is not fixed in advance. Instead, it is adaptively reselected as the system state evolves dynamically, ensuring that computational resources are always focused on the most critical correlation hotspots in the system (Figure 1). Under this mechanism, the entire evolution process operates completely at the inference stage, without requiring retraining or modification of the weights of the pretrained model. By introducing this physics-inspired methodology, LoRe becomes an efficient acceleration module that is plug-and-play and supported by a rigorous theoretical foundation.

Figure 1. Dynamic architecture of LoRe based on the low-level mapping of the many-body physics computational method C-DMFT.

On a hardware platform equipped with a 96 GB GPU, the physics-inspired LoRe framework demonstrated remarkable scalability advantages:

Breaking the system-size limit: On the MIS task, the original algorithm can process systems with up to approximately 15,000 nodes, while LoRe successfully extends this upper limit to around 50,000 nodes, more than three times the original scale, effectively overcoming the memory wall.

Substantial performance boost: At the largest scale where the original method can still run, LoRe achieves about an 8-fold end-to-end speedup, while reducing peak GPU memory consumption from 86.7 GB to 7.3 GB, corresponding to an approximately 12-fold reduction, with solution quality largely preserved.

Strong generality: As a general framework, LoRe is also applicable to other tasks and network architectures. On the 1,000-node TSP problem, it achieves about a 15-fold speedup and reduces peak GPU memory consumption by approximately 44-fold (Figure 2). The framework has currently been validated on multiple advanced models, including DIFUSCO, T2TCO, and COExpander. 

Figure 2. LoRe demonstrates outstanding scalability and performance improvements on MIS (a) and TSP (b) tasks.

This work marks a successful transfer of physical computational methods into artificial intelligence algorithm design. By creatively introducing mature computational methods for treating strongly correlated quantum systems into machine learning frameworks, the research group successfully alleviated the computational bottleneck in solving large-scale complex networks without adding any training cost. This not only demonstrates the profound value of fundamental physics in addressing modern AI engineering bottlenecks, but also provides an inspiring example for interdisciplinary frontier exploration in “Quantum for AI.” It further points to a new direction for future large-scale intelligent decision-making systems under resource-constrained scenarios.

The first author of the paper is Jintao Li (BAQIS). The corresponding authors are Prof. Heng Fan (BAQIS /IOP CAS), and  Zheng-An Wang (BAQIS). The collaborators also include Yong-Yi Wang (BAQIS). This work was supported by the MOST, the National Natural Science Foundation of China, the China Postdoctoral Science Foundation, and other programs.

Article link: https://arxiv.org/abs/2605.29005

Conference poster: https://icml.cc/virtual/2026/poster/65284