Adapting to Non-Stationary Environments: Multi-Armed Bandit Enhanced Retrieval-Augmented Generation on Knowledge Graphs

Xiaqiang Tang, Jian Li, Nan Du, Sihong Xie

Abstract

Despite the superior performance of Large language models on many NLP tasks, they still face significant limitations in memorizing extensive world knowledge. Recent studies have demonstrated that leveraging the Retrieval-Augmented Generation (RAG) framework, combined with Knowledge Graphs that encapsulate extensive factual data in a structured format, robustly enhances the reasoning capabilities of LLMs. However, deploying such systems in real-world scenarios presents challenges: the continuous evolution of non-stationary environments may lead to performance degradation and user satisfaction requires a careful balance of performance and responsiveness. To address these challenges, we introduce a Multi-objective Multi-Armed Bandit enhanced RAG framework, supported by multiple retrieval methods with diverse capabilities under rich and evolving retrieval contexts in practice. Within this framework, each retrieval method is treated as a distinct "arm''. The system utilizes real-time user feedback to adapt to dynamic environments, by selecting the appropriate retrieval method based on input queries and the historical multi-objective performance of each arm. Extensive experiments conducted on two benchmark KGQA datasets demonstrate that our method significantly outperforms baseline methods in non-stationary settings while achieving state-of-the-art performance in station environments.

Introduction

Retrieval-Augmented Generation (RAG) has become a cornerstone for reducing hallucinations in Large Language Models (LLMs). When integrated with Knowledge Graphs (KGs), these systems can perform complex, structured reasoning. However, real-world deployment faces two major hurdles: Non-Stationarity and the Multi-Objective Trade-off.

Environments are rarely static; user interests shift rapidly (e.g., during a natural disaster), and backend retrieval models are frequently updated. Static routing mechanisms often fail to adapt without expensive retraining. Furthermore, different retrieval methods—such as vector similarity, SPARQL generation, or LLM agents—offer varying balances of efficiency, coverage, and reasoning power.

Overview of challenges in KG-based RAG systems, including non-stationarity (C1) and multi-objective balancing (C2).

Methodology: The GGI-MAB Framework

To address these challenges, we propose GGI-MAB (Generalized Gini Index Multi-Armed Bandit). This framework treats different retrieval strategies as distinct "arms" in a Multi-Armed Bandit setup, allowing for dynamic selection based on the specific context of a user query.

System Architecture

The system employs a multi-stage pipeline designed for online adaptation:

  1. Feature Extraction: A lightweight DistilBERT (PLM) model encodes the user's natural language query to provide context for the bandit.
  2. Multi-objective Bandit Algorithm: The bandit selects an "action" (a retrieval method) based on the query context and historical performance metrics. It uses an $\epsilon$-greedy strategy to balance exploration and exploitation.
  3. Action Space: The available methods include Vector Similarity, KG Query Language (SPARQL), and Search with LLMs.
  4. Retrieval and Generation: The selected method retrieves data from the Knowledge Graph, which is then processed by an LLM generator to produce a response.
  5. Reward Signal: Real-time user feedback (thumbs up/down) and system metrics like latency are used to update the bandit's parameters on-the-fly.
Detailed architecture of the GGI-MAB framework showing the flow from user query to feedback-driven parameter updates.

Balancing Objectives with GGI

A core innovation is the use of the Generalized Gini Index (GGI) to aggregate multiple rewards—Hit Rate, Recall, and Latency—into a single loss function. This prevents any single objective from dominating, ensuring the system remains both accurate and responsive. By penalizing longer delays exponentially, the system is forced to value the user's time as much as the answer's correctness.

Experimental Evaluation

We evaluated GGI-MAB on two gold-standard Knowledge Graph Question Answering (KGQA) datasets: WebQSP (1-2 hop reasoning) and ComplexWebQuestions (CWQ) (multi-hop reasoning).

Key Results

  • Accuracy: In stationary environments, GGI-MAB achieved a 79.35% Hit Rate on CWQ, outperforming state-of-the-art baselines.
  • Efficiency: Compared to "Ensemble" methods that run all retrievers simultaneously, GGI-MAB reduced latency from 15 seconds to 5.88 seconds per query while maintaining superior accuracy.
  • Adaptability: In simulations of "Retriever Upgrades," the MAB naturally identified and prioritized superior new models through exploration without manual intervention. When facing domain shifts, it maintained a 76.35% Hit Rate, significantly higher than static neural routers.

Discussion and Future Work

GGI-MAB demonstrates that treating user feedback as a first-class reward signal allows RAG systems to self-correct in production. While the system shows strong results, future research will focus on making the bandit more robust to noisy or sparse user feedback and addressing the "cold start" problem in entirely new domains. Additionally, we aim to scale the framework to support a larger ecosystem of specialized RAG agents.

Summary updated

Abstract

Despite the superior performance of Large language models on many NLP tasks, they still face significant limitations in memorizing extensive world knowledge. Recent studies have demonstrated that leveraging the Retrieval-Augmented Generation (RAG) framework, combined with Knowledge Graphs that encapsulate extensive factual data in a structured format, robustly enhances the reasoning capabilities of LLMs. However, deploying such systems in real-world scenarios presents challenges: the continuous evolution of non-stationary environments may lead to performance degradation and user satisfaction requires a careful balance of performance and responsiveness. To address these challenges, we introduce a Multi-objective Multi-Armed Bandit enhanced RAG framework, supported by multiple retrieval methods with diverse capabilities under rich and evolving retrieval contexts in practice. Within this framework, each retrieval method is treated as a distinct "arm''. The system utilizes real-time user feedback to adapt to dynamic environments, by selecting the appropriate retrieval method based on input queries and the historical multi-objective performance of each arm. Extensive experiments conducted on two benchmark KGQA datasets demonstrate that our method significantly outperforms baseline methods in non-stationary settings while achieving state-of-the-art performance in station environments.
BibTeX
@inproceedings{tang2025adapting,
  author = {Xiaqiang Tang and Jian Li and Nan Du and Sihong Xie},
  title = {{Adapting to Non-Stationary Environments: Multi-Armed Bandit Enhanced Retrieval-Augmented Generation on Knowledge Graphs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  url = {https://openreview.net/forum?id=gT62hgldUz},
}
Figure