AoG: Uncertainty-Guided Adaptive Reasoning Agent on Knowledge Graphs

The strong reasoning capabilities of large language models (LLMs) enable LLM-based agents to solve complex reasoning tasks through interactions with external tools and knowledge base. These interactions incur token and latency costs, but their benefits vary across decisions. In knowledge graph reasoning under a limited action budget, uniform exploration effort can waste actions on clear relation choices while leaving ambiguous ones insufficiently inspected. Reusing exploration feedback poses another challenge: agents must avoid repeating failed actions without excluding those that may be valid in a different context. To address these challenges, we introduce AoG, a training-free reasoning agent over knowledge graphs that couples on-demand evidence acquisition with context-specific failure reuse. It uses uncertainty to switch relation exploration policy and bounded graph inspection. Verified local failures are retained across retries as action-conditioned memory, which excludes candidate actions only when the recorded context matches and the supporting evidence remains applicable. Evaluation across three KGQA benchmarks shows that AoG achieves a favorable balance of answer quality and inference cost when compared with training-free agents under same action budgets.