All trajectories lead to knowledge gaps: Learning what to ask LLMs via knowledge graph traversal

As Large Language Models (LLMs) are increasingly deployed across diverse applications, both their abilities and size continue to grow. However, regardless of their size, LLMs remain imperfect, suffering from knowledge gaps and difficulties in understanding semantic meaning. While larger LLMs demonstrate enhanced capabilities, they also require more computation, and deploying these large-scale models can be time-consuming. Furthermore, some of the best models are not open-source and involve usage costs, making unproductive queries financially burdensome and creating a need to learn how to effectively query LLMs. To address these issues, this paper presents a novel black-box learning framework called POLYGRAPH , designed to adaptively and efficiently learn on what to train in order to detect falsehood patterns in LLMs. Our core idea is to train an agent to dynamically traverse a Knowledge Graph (KG) while interacting with an LLM by
asking questions, effectively learning what to ask the LLM that it likely doesn’t know. We formulate this as a Markov Decision Process (MDP), where the reward is the number of falsehoods identified, and use a Reinforcement Learning (RL) agent to maximize this reward. Experiments conducted with several popular LLMs of varying sizes and KGs demonstrate that POLYGRAPH is significantly more effective in selecting questions the LLM doesn’t know, achieving up to a 40% improvement over baselines in identifying gaps in LLMs’ knowledge.

Ofir is an  Master student from IDF’s elite program”Barket”, under the joint supervision of Haggai Maron and Shie Mannor.