Backjump-on-Graph: Empowering Large Language Models with Reinforced Retrospective Exploration for Agentic Knowledge Graph Reasoning

Grounding Large Language Models (LLMs) in Knowledge Graphs (KGs) has shown significant promise for complex Question Answering (QA) tasks. Since LLMs' limited context window cannot accommodate the sheer volume of large-scale KGs, existing work usually utilizes agents to reason on real-world KGs, which follows reasoning paths derived from the queries step by step. However, the mismatch between query-derived paths and the KG's structure, stemming from users' lack of schema knowledge, usually leads the agents into dead ends. To address this problem, in this paper, we propose Backjump-on-Graph (BoG), a novel framework that empowers LLMs to retrospectively explore alternative reasoning paths at dead ends. We first propose to formalize each reasoning step with four atomic operations to create a structural scaffold that allows LLMs to revert to historical status. Next, we fine-tune the LLM with synthetic data containing the above atomic operations to instill basic backjump abilities. Finally, we leverage reinforcement learning and propose a hybrid reward function, which penalizes redundant transitions and promotes correct answers, to optimize the timing and landing nodes of backjumping. Extensive experiments on several KGQA benchmark datasets demonstrate the effectiveness of our BoG method.

How do artificial intelligence models find answers in massive databases when human questions do not perfectly match the database's strict structure? We wanted to address this challenge by creating a navigation framework called Backjump-on-Graph (BoG) to help large language models effectively search through complex information networks. Our paper presents a method allowing AI to recognize when it has hit a "dead end" and intelligently retrace its steps to explore alternative paths. This is crucial, as AI agents traditionally fail when their search diverges from how the data is organized—akin to someone getting hopelessly lost in a maze because they cannot remember their way back after making a wrong turn. We achieved this by teaching the AI basic "backjumping" skills and using a reward-based learning system. This system penalizes the AI for walking in circles and rewards it for finding correct answers, optimizing exactly when and where it should backtrack. Our findings demonstrate that giving AI the ability to recover from its navigation mistakes significantly improves its performance on complex questioning tasks. This suggests new ways to build highly reliable AI assistants capable of seamlessly connecting everyday human queries with vast, real-world knowledge.