Effective Inference on Dynamic Graphs via Entropy Driven Routing

摘要

Large Language Models (LLMs) have shown promise in reasoning over dynamic graphs, yet practical deployment is hindered by a fundamental trade-off between inference cost and reliability. Existing adaptive approaches typically rely on heuristic switching rules, such as graph size or density thresholds, which often fail to generalize across diverse dynamic settings. In this work, we propose \emph{DualDyg}, an uncertainty-aware framework for adaptive dynamic graph reasoning that dynamically allocates computational effort based on instance difficulty. \emph{DualDyg} integrates a calibration-based routing mechanism grounded in structural entropy and predictive uncertainty to select between fast and slow inference paths, and incorporates uncertainty-guided latent feature masking during deep reasoning to improve robustness. In addition, the framework performs a closed-loop analysis of predictive uncertainty to characterize the effect of additional reasoning steps. Experiments with Llama-3.1 and Qwen3 on a suite of dynamic graph reasoning tasks show that \emph{DualDyg} consistently outperforms static inference baselines while substantially reducing inference cost, suggesting that uncertainty-aware adaptation can effectively balance reasoning quality and efficiency.