LoRe: Adaptive Interaction-Evaluation Routing with Per-step Interaction Budgets for Iterative Graph Solvers

Diffusion-based neural solvers for combinatorial optimization repeatedly re-evaluate dense edge/factor interactions, making inference expensive in wall-clock time and often memory-bound at scale. Inspired by the computational methodologies of many-body physics, we introduce LoRe, a training-free, inference-time drop-in wrapper that enforces per-step interaction-evaluation budgeting: at each iteration, it evaluates only a fixed fraction of interactions by dynamically routing computation to high-conflict or high-uncertainty interactions, instead of using a fixed sparsification (e.g., static kNN graphs or static masks). Under fully inclusive end-to-end wall-clock accounting, LoRe substantially improves scalability on the Maximum Independent Set (MIS) problem, extending feasible inference more than $3\times$ beyond the baseline's out-of-memory limit, delivering a ${\sim}8\times$ speedup and a ${\sim}12\times$ peak-memory reduction, with solution quality preserved in this regime. Demonstrating cross-task generality on the large-scale Traveling Salesperson Problem (TSP) and zero-shot robustness to topology shifts, LoRe achieves a ${\sim}15\times$ speedup at $n=1000$ with a $44\times$ memory reduction and competitive tour quality.

Artificial Intelligence is increasingly used to solve complex logistical challenges, like routing delivery vehicles or scheduling datacenter jobs. However, as these networks grow larger, AI models often run out of memory or become unacceptably slow. This happens because they attempt to re-evaluate every single connection in the network at every step of their thought process, which demands massive computational power. Inspired by how physicists calculate interactions within strongly correlated many-body systems by focusing computing power only on highly active regions while treating the rest as a simplified background, we developed a method called LoRe. Think of LoRe as a dynamic spotlight for AI. Instead of calculating the entire map at once, LoRe constantly tracks the most critical, unresolved conflicts in a problem and routes all the heavy computing power exclusively to those "hotspots". The rest of the network is maintained as a lightweight background so the AI doesn't lose the big picture. By enforcing this strict computing budget, LoRe allows standard AI solvers to tackle problems over three times larger than their previous limits before crashing. It drastically accelerates the decision-making process by making it up to 15 times faster and using 44 times less memory, all while consistently delivering high-quality solutions for real-world tasks.