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

Researchers introduce LoRe, a training-free optimization method that dynamically routes computational resources to high-priority interactions in iterative graph solvers, achieving 8× speedup and 12× memory reduction on combinatorial optimization problems while maintaining solution quality.

LoRe addresses a critical scalability bottleneck in diffusion-based neural solvers for combinatorial optimization problems. These solvers traditionally evaluate dense interaction matrices at every iteration, creating computational and memory constraints that limit their practical application to larger problem instances. By implementing per-step interaction budgeting inspired by many-body physics, LoRe selectively evaluates only the most computationally relevant interactions—those exhibiting high conflict or uncertainty—rather than applying static sparsification patterns.

The advancement reflects the broader push to make neural optimization methods production-ready. As combinatorial optimization increasingly relies on learned solvers rather than traditional heuristics, efficiency becomes paramount. Prior approaches used fixed sparsification (static kNN graphs or masks), which lack adaptability. LoRe's dynamic routing fundamentally improves this by adjusting focus based on problem state at inference time, creating a more intelligent allocation of computational budget.

The performance gains are substantial: extending Maximum Independent Set (MIS) inference 3× beyond baseline out-of-memory limits while delivering 8× speedup demonstrates genuine practical value. The 12× peak memory reduction is particularly significant for resource-constrained deployments. Critically, these improvements maintain solution quality, eliminating the typical speed-accuracy tradeoff. Cross-task validation on Traveling Salesperson Problem instances and zero-shot robustness to topology shifts suggest the method generalizes effectively across problem classes.

For practitioners implementing neural solvers, LoRe represents a training-free drop-in wrapper—requiring no model retraining—making adoption frictionless. The approach opens pathways for scaling neural optimization to previously intractable problem sizes, potentially expanding the competitive domain where learned solvers outperform classical algorithms.

• →LoRe achieves 8× speedup and 12× memory reduction on combinatorial optimization while preserving solution quality
• →Dynamic interaction routing based on conflict and uncertainty outperforms static sparsification approaches
• →Training-free implementation enables immediate deployment as an inference-time wrapper without model retraining
• →Method demonstrates cross-task generality on MIS and TSP problems with zero-shot robustness to topology variations
• →Extends feasible problem scales 3× beyond baseline capacity limits, enabling previously infeasible larger instances