🤖 AI

Can We Trust a Black-box LLM? LLM Untrustworthy Boundary Detection via Bias-Diffusion and Multi-Agent Reinforcement Learning

This paper introduces GMRL-BD, a novel black-box algorithm that leverages a Wikipedia-derived knowledge graph and multi-agent reinforcement learning to efficiently detect the untrustworthy boundaries of large language models by identifying topics prone to biased responses, accompanied by the release of a new dataset covering popular models like Llama2 and Vicuna.

Original authors: Xiaotian Zhou, Di Tang, Xiaofeng Wang, Xiaozhong Liu

Published 2026-04-08

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Xiaotian Zhou, Di Tang, Xiaofeng Wang, Xiaozhong Liu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very smart, well-read robot friend (a Large Language Model, or LLM) who can answer almost any question you ask. You love asking it about history, science, and movies. But sometimes, when you ask about sensitive topics like politics, immigration, or religion, the robot starts giving you answers that are slanted, unfair, or just plain wrong. It's like the robot has a hidden "blind spot" where its judgment gets clouded.

The big problem? You don't know where those blind spots are. And since the robot is a "black box" (you can't look inside its brain to see how it thinks), you can't just ask it, "Hey, are you biased about X?" It might lie or not even realize it's biased.

This paper introduces a clever new way to map out these blind spots without needing to open the robot's brain. Here is the breakdown using simple analogies:

1. The Map: The Knowledge Graph

Imagine all the topics in the world are connected like a giant subway map.

The Stations: Each station is a topic (e.g., "Immigration," "Economy," "AI").
The Tracks: The tracks connect related topics. If you are at "Immigration," the tracks lead you to "Refugees," "Border Policy," and "Human Rights."

The researchers used a map based on Wikipedia's categories. It's a huge, organized map where everything is connected to something else.

2. The Theory: The "Contagion" of Bias

The researchers noticed something interesting: Bias is contagious.
If the robot gives a biased answer about "Immigration," it is highly likely to give a biased answer about "Refugees" or "Border Policy" because those topics are right next to each other on the map.

Analogy: Think of it like a cold. If one person in a room has a cold, the people sitting right next to them are the most likely to catch it next. You don't need to check every single person in the building; if you find the first sick person, you know to be careful with their neighbors.

3. The Solution: The "Scout Team" (Multi-Agent Reinforcement Learning)

Instead of asking the robot one question at a time (which is slow and expensive), the researchers sent out a team of digital scouts (called Agents).

How they work:
- The scouts start at different points on the subway map.
- They ask the robot a few questions about a topic.
- If the robot seems biased, the scouts shout to the rest of the team: "Hey, this area is dangerous! Don't waste time here, but check the stations right next to it!"
- If the robot seems fine, the scouts move on to a different part of the map.
The Magic: The scouts share information instantly. If Scout A finds a bias in "Politics," Scout B (who is exploring "Economy") knows to be extra careful because those topics are connected. This allows them to find all the "danger zones" (untrustworthy boundaries) with very few questions.

4. The Result: A "Trust Map"

By using this team of scouts, the system can quickly draw a map that says:

✅ Green Zone: "Safe to ask about Science and History."
⚠️ Red Zone: "Be careful! The robot gets biased here (e.g., Immigration and Reproductive Rights)."

Why is this a big deal?

Efficiency: Previously, to find out where a robot is biased, you might have to ask it 10,000 questions. This new method might only need 100 questions because the scouts learn from each other.
No "X-Ray Vision" Needed: It works even if you don't know how the robot was built or what code it runs. It treats the robot as a mystery box and just watches its behavior.
New Data: The researchers also created a massive new dataset (a library of questions and answers) covering many popular robots (like Llama, Falcon, and Vicuna) to help other scientists test their own bias-detection tools.

In a Nutshell

This paper is like hiring a team of detectives to find the "bad neighborhoods" in a city (the AI's knowledge base) without having to walk every single street. They use a map of connected streets and a system where detectives share intel, allowing them to quickly identify which areas are unsafe for the public (users) to trust, saving time and money in the process.

1. Problem Statement

Large Language Models (LLMs) are powerful but prone to generating biased, ideologized, or incorrect responses. While prior research has focused on measuring bias on pre-defined topics, a critical gap exists in detecting the "untrustworthy boundaries" of black-box LLMs (models where internal weights and gradients are inaccessible).

The Challenge: Exhaustively testing an LLM across all possible topics to find where it fails is resource-prohibitive and cost-ineffective.
The Goal: To efficiently identify the specific topics (nodes) within a Knowledge Graph (KG) where a black-box LLM is likely to produce biased responses, using a minimal number of queries.
Key Assumption: Bias is not isolated; if an LLM is biased on a specific topic, it is likely to exhibit similar biases on topologically related or neighboring topics within a Knowledge Graph (the "Bias-Diffusion" hypothesis).

2. Methodology: GMRL-BD

The authors propose GMRL-BD (Graph Multi-Agent Reinforcement Learning for LLM-untrustworthy Boundary Detection), a model-agnostic framework that combines Knowledge Graphs, Reinforcement Learning (RL), and Multi-Agent collaboration.

A. Knowledge Graph Foundation

Source: A general KG derived from the Wikipedia category tree.
Structure: Topics are nodes ( $V$ ), and hierarchical/semantic relationships are edges ( $E$ ).
Advantage: This structure allows the system to infer bias on untested nodes based on the bias status of connected neighbors, significantly reducing the search space.

B. Core Components

Node Embedding & Representation:
- For each topic node, the system generates an initial embedding ( $h_0$ ) by summarizing the LLM's responses to questions about that topic.
- A Graph Attention Network (GAT) mechanism aggregates embeddings from neighboring nodes to incorporate topological information, creating a final state representation ( $h(v)$ ) that captures both semantic content and structural context.
Reinforcement Learning (RL) Formulation:
- State ( $s_t$ ): The set of embeddings for currently tested nodes and their neighbors.
- Action ( $a_t$ ): Selecting a neighbor node to query next.
- Reward Function ( $R$ ): Designed to maximize the discovery of bias nodes while minimizing query costs. It includes:
  - Bias Reward: Positive reward for finding a biased node ( $y(v)=1$ ).
  - Cost Penalty: Negative reward proportional to the number of nodes tested.
  - Distance Term: Encourages the agent to take the shortest path to the nearest untested bias node (calculated during training using ground truth).
Multi-Agent Planning (Inference Phase):
- To further optimize efficiency, the system deploys multiple RL agents simultaneously.
- AgentLinkHub: A coordination module that manages agent movements. It uses a Priority Queue to select the agent with the highest Q-value to move next.
- Conflict Avoidance: If an agent's optimal move is already taken by another, the hub switches to the next most efficient agent. This minimizes redundant queries and overlapping exploration paths.

3. Key Contributions

Novel Problem Formulation: Formalized the detection of "untrustworthy boundaries" in black-box LLMs as a graph exploration problem, moving beyond static metric-based bias assessment.
GMRL-BD Algorithm: Introduced a model-agnostic framework using Multi-Agent RL and Bias-Diffusion hypotheses to detect biases with minimal queries. It does not require access to model internals or retraining.
LLM Bias Identification Dataset (LBID): Created a new benchmark dataset containing:
- 6 LLMs: Llama2, Vicuna, Falcon, Qwen2, Gemma2, and Yi-1.5.
- Scope: 22,608 topics mapped to the Wikipedia category graph.
- Data: 113,040 QA pairs with injected biases across six domains (AI, Culture, Economy, Politics, Education, Immigration).
- Labels: Ground truth trust labels for each topic.
Efficiency Validation: Demonstrated that leveraging inter-topic relationships allows for accurate boundary detection with significantly fewer queries compared to random or static exploration.

4. Experimental Results

The authors evaluated GMRL-BD on the LBID dataset across six domains (Economy, Education, Immigration, Politics, AI, Culture).

Bias Diffusion Validation: Experiments confirmed that injecting bias into a specific topic (e.g., "Economy") caused the LLM to generate biased responses for neighboring topics, validating the core hypothesis.
Query Efficiency:
- GMRL-BD successfully identified untrustworthy boundaries with 10–30 query interactions per task, whereas traditional methods would require exhaustive testing.
- Convergence was achieved within 200–400 episodes for most models.
Performance Metrics (Bias Node Cover Rate - BNCR):
- Llama-2 and Falcon showed the highest performance (e.g., ~90% BNCR in Immigration and Economy tasks).
- Vicuna showed lower performance, likely due to inherent debiasing mechanisms in its training.
Ablation Studies:
- Removing the SAGE layer or Attention layer significantly reduced performance.
- The full GMRL-BD model (0.895–0.96 success rate) vastly outperformed baselines like Depth First Search (DFS) (0.08–0.11) and uniform exploration.
Multi-Agent Impact: Increasing the number of agents led to a significant decrease in step loss (faster convergence) and an increase in win rate, proving the efficacy of collaborative exploration.

5. Significance and Future Work

Practical Impact: This framework provides a scalable, cost-effective tool for organizations to audit black-box LLMs before deployment in sensitive domains (e.g., elections, education, healthcare). It answers the question "Can we trust this LLM?" by defining exactly where it cannot be trusted.
Resource Efficiency: By reducing the number of required queries, it makes trustworthiness evaluation feasible for large-scale models.
Future Directions: The authors suggest extending the framework from topic-based detection to query-based detection, treating individual user queries as multinomial distributions over topics to handle dynamic, real-time interactions.

In summary, the paper presents a robust, graph-based approach to mapping the "blind spots" of LLMs, leveraging the structural relationships of knowledge to efficiently predict and locate bias without needing to open the black box.