UGID: Unified Graph Isomorphism for Debiasing Large Language Models

1. Problem Statement

Large Language Models (LLMs) exhibit profound social biases embedded not just in their outputs, but deep within their internal representations and computational processes. Existing debiasing methods face two primary limitations:

• External/Output-level methods: Approaches that adjust data or filter outputs (e.g., Self-Debias) fail to address the root cause, making them vulnerable to prompt rephrasing and out-of-distribution (OOD) scenarios.
• Internal/Component-level methods: Previous works focusing solely on specific components (like attention heads) are insufficient. The authors' investigation reveals a scale-dependence of bias: constraining only attention mechanisms reduces bias in small models (e.g., GPT-2) but fails in billion-parameter models (e.g., LLaMA-3-8B) because bias migrates into Feed-Forward Networks (FFNs) and hidden states.

The core challenge is to eliminate bias across the entire computational graph (both routing and storage) without degrading the model's general utility or erasing definitional concepts (e.g., distinguishing "King" from "Queen").

2. Methodology: UGID Framework

The authors propose UGID (Unified Graph Isomorphism for Debiasing), which reformulates debiasing as a computational graph isomorphism problem. The Transformer is modeled as a dynamic graph $G=(V, E)$, where tokens are nodes ($V$) and attention mechanisms define edges ($E$). The goal is to enforce invariance in the graph structure across counterfactual inputs (e.g., "he" vs. "she"), allowing differences only in sensitive attributes.

The framework consists of four key designs:

Design I: Aligning Routing Topology (Edges)

• Goal: Prevent "routing bias" where attention heads form fixed bottlenecks around sensitive tokens.
• Mechanism: Instead of matching raw attention weights, UGID aligns the spectral features of the attention graphs using a Combinatorial Laplacian operator ($L = D - A$).
• Optimization: It computes eigenvalues directly from diagonal elements to reduce complexity to $O(T)$. It employs an Attention Sink Mask ($M_{sink}$) to filter the first token (an artifact of Softmax) and an Adaptive Saliency Weight to focus on bias hubs.
• Loss: Minimizes the squared difference between spectral signatures of counterfactual pairs.

Design II: Preventing Bias Migration (Nodes)

• Goal: Stop bias from migrating into hidden states (FFNs) when attention is constrained.
• Mechanism: Enforces node isomorphism by constraining hidden representations ($H$) to remain consistent across counterfactual contexts.
• Loss: Aggregates saliency weights to minimize the $L_2$ distance between hidden states of counterfactual inputs, ensuring bias is not stored in value vectors.

Design III: Preserving Model Utility

• Goal: Prevent catastrophic forgetting and maintain syntactic correctness.
• Mechanism: A composite stability objective:
  1. Log-Space Guidance: Penalizes divergence in log-probabilities for sensitive attributes to prevent gradient vanishing.
  2. Top-K Stability: Anchors the student model's attention patterns to a frozen teacher model to preserve syntax.
  3. Semantic Preservation: Uses a masked KL-divergence to retain general knowledge while allowing changes only on sensitive tokens.

Design IV: Handling Definitional Bias

• Goal: Avoid "Concept Erasure" (e.g., the model losing the ability to distinguish gender in factual definitions like "King/Queen").
• Mechanism: A Selective Alignment Strategy. The training dataset is a mixture of:
  • Target Pairs: Stereotypical counterfactuals (where debiasing is applied).
  • Anchor Pairs: Definitional pairs (where strict preservation is enforced).
• Loss: Dynamically switches between the debiasing loss and a standard KL-divergence loss for anchor data to lock fundamental semantic anchors.

3. Key Contributions

1. Unified Graph Isomorphism Framework: The first framework to treat debiasing as a structural alignment problem, jointly constraining attention routing (edges) and hidden representations (nodes) to sever bias migration pathways.
2. Mechanistic Interpretability: Provides physical-level explanations for bias governance using Spectral Diagnostics, Logit Lens, and Activation Patching, visualizing how bias is eliminated at the topological level.
3. Superior Trade-off: Demonstrates a better balance between debiasing effectiveness and utility preservation compared to state-of-the-art methods, with robustness across different model sizes and OOD scenarios.

4. Experimental Results

Experiments were conducted on LLaMA-3-8B, Qwen-2, and Gemma-2 using datasets like BBQ, CrowS-Pairs, and BOLD.

• Debiasing Effectiveness: UGID reduced bias scores to near-ideal neutral levels ($\approx 1.06\times$) in In-Distribution (ID) settings and showed significantly lower bias in Out-of-Distribution (OOD) settings compared to inference-time baselines like Self-Debias.
• Structural Stability:
  • $\Delta$Spec (Spectral Divergence): Reduced from 0.211 (Original) to 0.007.
  • $\Delta$Hidden (Hidden State Drift): Reduced from 5.198 (Original) to 0.058, preventing "hidden state collapse."
• Utility Preservation:
  • Maintained 100% accuracy on Safety/Definitional Anchors (e.g., King/Queen), whereas methods like KLAAD dropped to 50%.
  • Perplexity (PPL) remained near 1.0, indicating no loss in linguistic fluency.
• Robustness: UGID exhibited the lowest variance (0.0044) under prompt perturbations, proving its stability against adversarial linguistic variations.
• Efficiency: The method incurs zero inference overhead (latency remains $1.0\times$) and reduces peak memory requirements during optimization by integrating constraints into frozen parameters.

5. Significance

UGID represents a paradigm shift from surface-level debiasing to structural intervention. By treating the Transformer as a computational graph and enforcing isomorphism, it addresses the root cause of bias migration across architectural layers.

• Scalability: It solves the scale-dependence issue, working effectively on billion-parameter models where previous attention-only methods failed.
• Safety & Alignment: It offers a mechanism to decouple harmful stereotypes from reasoning topologies without erasing factual knowledge, providing a robust foundation for safer, more equitable AI systems.
• Generalizability: The structural approach is domain-agnostic, suggesting applicability beyond social bias to other forms of internal misalignment in large neural systems.