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

• URL: http://arxiv.org/abs/2605.29005v1
• Date: Wed, 27 May 2026 19:00:57 GMT
• Title: LoRe: Adaptive Interaction-Evaluation Routing with Per-Step Interaction Budgets for Iterative Graph Solvers
• Abstract summary: We introduce LoRe, a training-free, inference-time drop-in wrapper that enforces per-step interaction-evaluation budgeting.<n>Under fully inclusive end-to-end wall-clock accounting, LoRe substantially improves scalability on the Maximum Independent Set (MIS) problem.<n>LoRe achieves a $sim 15times$ speedup at $n=1000$ with a $44times$ memory reduction and competitive tour quality.
• Score: 13.286251127911719
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• An Embedded RISC-V Evaluation of Kolmogorov--Arnold Networks in Hard-Constrained Recurrent Physics-Informed Models [0.0]
  Kolmogorov--Arnold Networks (KANs) have been proposed as efficient replacements for multilayer perceptrons (MLPs)<n>This paper asks whether that parameter efficiency survives deployment.
  arXiv  Detail & Related papers  (2026-08-01T16:20:24Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• Scaling Laws for Agent Harnesses via Effective Feedback Compute [53.68149869349268]
  emphEffective Feedback Compute (EFC) is a trace-level scaling coordinate that credits feedback only when it is informative, valid, non-redundant, and retained for subsequent decisions.<n>EFC-based coordinates consistently predict failure rates better than raw-compute baselines.
  arXiv  Detail & Related papers  (2026-05-28T09:45:47Z)
• Dimensionality Reduction for Robust Federated Learning: A Theoretical Analysis and Convergence Guarantee [14.954293251332894]
  Federated Learning (FL) enables clients to collaboratively train models without sharing raw data, but it is highly vulnerable to Byzantine attacks.<n>Existing robust approaches can neutralize these threats but incur substantial computational overhead.<n>We propose a universal acceleration framework for vector-level distance-based robust aggregators.
  arXiv  Detail & Related papers  (2026-05-27T11:39:47Z)
• Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts [19.540758462427878]
  We propose a learning-augmented framework that accelerates exact assignment solvers while maintaining optimality and worst-case guarantees.<n>We introduce RowDualNet, a lightweight row-independent architecture that avoids the $mathcalO(N2)$ memory bottleneck of graph-based models.
  arXiv  Detail & Related papers  (2026-05-10T07:15:49Z)
• A Quantifier-Reversal Approximation Paradigm for Recurrent Neural Networks [1.096028999747108]
  This paper introduces a fundamentally different approximation paradigm that reverses the quantifier order.<n>For each target function $f$, we construct a single recurrent neural network (RNN) with fixed topology and fixed weights that approximates $f$ to within any prescribed tolerance $> 0$ when run for sufficiently many time steps.<n>Our RNN constructions emulate the structural underlying deep feed-forward ReLU network approximation theory.
  arXiv  Detail & Related papers  (2025-11-19T10:43:48Z)
• INC: An Indirect Neural Corrector for Auto-Regressive Hybrid PDE Solvers [61.84396402100827]
  We propose the Indirect Neural Corrector ($mathrmINC$), which integrates learned corrections into the governing equations.<n>$mathrmINC$ reduces the error amplification on the order of $t-1 + L$, where $t$ is the timestep and $L$ the Lipschitz constant.<n>We test $mathrmINC$ in extensive benchmarks, covering numerous differentiable solvers, neural backbones, and test cases ranging from a 1D chaotic system to 3D turbulence.
  arXiv  Detail & Related papers  (2025-11-16T20:14:28Z)
• Hierarchical Federated Graph Attention Networks for Scalable and Resilient UAV Collision Avoidance [0.5505634045241287]
  Real-time performance, adversarial resiliency, and privacy preservation are the most important metrics that need to be balanced to practice collision avoidance.<n>We have proposed an adaptive differential privacy mechanism, wherein the noise level $(in [0.1, 1.0])$ is dynamically reduced based on an evaluation of the measured real-time threat.<n>This architecture provides a scalable scenario of 500 UAVs with a collision rate of $ 2.0%$ and the Byzantine fault tolerance of $f n/3$.
  arXiv  Detail & Related papers  (2025-11-05T12:01:00Z)
• Beyond Isotonization: Scalable Non-Crossing Quantile Estimation via Neural Networks for Student Growth Percentiles [0.0]
  Student Growth Percentiles (SGPs), widely adopted across U.S. state assessment systems, employ independent quantile regression followed by post-hoc correction.<n>We demonstrate this approach contains a fundamental methodological inconsistency: between independently-estimated, potentially crossed quantiles requires monotonicity.<n>We propose neural network-based multi-quantile regression (NNQR) with shared hidden layers as a practical alternative.
  arXiv  Detail & Related papers  (2025-10-25T19:39:07Z)
• R-Stitch: Dynamic Trajectory Stitching for Efficient Reasoning [80.104336426172]
  Chain-of-thought (CoT) enhances problem-solving ability of large language models.<n>CoT incurs substantial inference cost due to long autoregressive trajectories.<n>We introduce R-Stitch, a training-free hybrid decoding framework.
  arXiv  Detail & Related papers  (2025-07-23T08:14:36Z)
• Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum [78.27945336558987]
  Decentralized server (DFL) eliminates reliance on client-client architecture.<n>Non-smooth regularization is often incorporated into machine learning tasks.<n>We propose a novel novel DNCFL algorithm to solve these problems.
  arXiv  Detail & Related papers  (2025-04-17T08:32:25Z)
• Scalable 3D Registration via Truncated Entry-wise Absolute Residuals [65.04922801371363]
  A $3$D registration approach can process more than ten million ($107$) point pairs with over $99%$ random outliers. We call our method TEAR, as it involves minimizing an outlier-robust loss that computes Truncated Entry-wise Absolute Residuals.
  arXiv  Detail & Related papers  (2024-04-01T04:43:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.