Knowledge Is Not Static: Order-Aware Hypergraph RAG for Language Models

1. Problem Statement

Current Retrieval-Augmented Generation (RAG) systems, including those utilizing Graphs and Hypergraphs, fundamentally treat retrieved evidence as an unordered set. They assume permutation invariance, meaning the order in which facts are presented does not affect the reasoning outcome.

However, the authors argue this assumption is flawed for many real-world reasoning tasks (e.g., disaster response, medical diagnosis, legal causality) where outcomes depend not just on which interactions occur, but on the sequence in which they unfold.

• Limitation of Graphs: Standard Knowledge Graphs (KGs) only model binary relations, failing to capture higher-order interactions involving multiple entities simultaneously.
• Limitation of Static Hypergraphs: While Hypergraphs can model $n$-ary relations, existing Hypergraph-RAG methods still treat hyperedges as static, timeless facts. They fail to capture the temporal evolution, causality, and precedence required for process-based reasoning.

Core Hypothesis: Effective reasoning requires retrieving evidence not as a set, but as an ordered trajectory that reflects the underlying dynamic process.

2. Methodology: OKH-RAG

The proposed framework, Order-Aware Knowledge Hypergraph RAG (OKH-RAG), models knowledge as higher-order interactions with explicit precedence structures. It operates in three stages:

A. Knowledge Hypergraph Construction & Order Learning

1. Hypergraph Representation ($H$):

   • Entities ($V$): Represent objects, states, or temporal anchors (e.g., "Port of Houston," "Cyclone State at T-48").
   • Hyperedges ($E$): Connect arbitrary subsets of entities ($|V_e| \ge 2$) to model $n$-ary interactions. Each hyperedge includes a natural language description, relation type, and attributes.
   • Order-Aware Augmentation ($H^\prec$): The system introduces a discrete sequence index $\ell$ and a learned precedence relation $\prec$. This transforms the static hypergraph into a sequence of states, where $e_i \prec e_j$ implies $e_i$ must precede $e_j$.

2. Learning Precedence:

   • Since explicit temporal annotations are often unavailable, OKH-RAG learns a parametric transition model $P_\theta(e_j | e_i)$.
   • Architecture: A bilinear model using dense hyperedge embeddings ($h_e$) and a low-rank weight matrix $W$. The model is inherently asymmetric ($P_\theta(e_j | e_i) \neq P_\theta(e_i | e_j)$), capturing directionality without explicit timestamps.
   • Training: Uses a contrastive objective with three self-supervised signals:
     1. Document Order: Positional adjacency in source text.
     2. Entity-Overlap Consistency: Shared entities in canonical reasoning chains.
     3. Retrieval-Induced Preference: Reinforcing transitions found in successful retrieval trajectories (self-training).

B. Order-Aware Hypergraph Retrieval

Instead of ranking independent facts, retrieval is reformulated as trajectory inference. The goal is to find the optimal ordered sequence of hyperedges $\gamma = (e^{(1)}, \dots, e^{(L)})$ that maximizes a composite score:

$$\text{Score}(\gamma) = \underbrace{\sum \text{Rel}(e, q)}_{\text{Relevance}} + \lambda \underbrace{\sum \log P_\theta(e^{(k+1)}|e^{(k)})}_{\text{Order Coherence}} + \mu \underbrace{\text{Prec}(\gamma)}_{\text{Precedence}} + \nu \underbrace{\text{Ovlp}(\gamma)}_{\text{Entity Continuity}} + \rho \underbrace{\text{Cov}(\gamma)}_{\text{Phase Coverage}}$$

• Relevance: Cosine similarity between query and hyperedge.
• Order Coherence: Probability of transition between consecutive hyperedges.
• Precedence Consistency: Alignment with the structural partial order $\prec$.
• Entity Continuity: Rewards chains where consecutive steps share entities (ensuring logical flow).
• Phase Coverage: Ensures the trajectory spans distinct reasoning stages (e.g., Forecast $\to$ Warning $\to$ Impact $\to$ Recovery).
• Inference: Uses Beam Search (primary) or Viterbi DP (for smaller sets) to search the candidate space efficiently.

C. Retrieval-Augmented Generation

The retrieved ordered trajectories are presented to the LLM as numbered evidence chains with structural annotations (step index, horizon, phase). This allows the generator to:

• Recognize preconditions and downstream consequences.
• Track escalation across time horizons.
• Synthesize answers based on the process rather than just isolated facts.

3. Key Contributions

1. Order-Aware Representation: Introduces a knowledge hypergraph representation that explicitly encodes precedence structure, treating order as a first-class structural property rather than an afterthought.
2. Trajectory-Based Retrieval: Reformulates RAG retrieval from selecting a permutation-invariant set of facts to inferring an ordered sequence (trajectory) of interactions.
3. Learned Transition Model: Develops a self-supervised method to learn interaction order directly from data without requiring explicit temporal labels.
4. Theoretical Justification: Provides a formal proposition proving that for order-sensitive queries, permutation-invariant retrieval is mathematically insufficient ($P(y|k_a, k_b, q) \neq P(y|k_b, k_a, q)$).

4. Experimental Results

The framework was evaluated on CyPortQA, a benchmark for tropical cyclone and port operation scenarios (2,917 real-world disruption scenarios).

• Baselines: Compared against Text-RAG (unstructured), GraphRAG (binary graphs), and HyperGraphRAG (unordered hypergraphs).
• Performance: OKH-RAG achieved the highest overall accuracy (53.4%) across all question types (True/False, Multiple Choice, Short Answer, Text Description), outperforming the best baseline (HyperGraphRAG at 51.1%).
• Ablation Studies:
  • Shuffling Test: When the order of retrieved hyperedges in OKH-RAG was shuffled, accuracy dropped significantly (from 53.4% to 48.7%), proving that order is the primary driver of performance gains, not just the hypergraph structure.
  • Component Analysis: Removing "Precedence Consistency" or "Phase Coverage" caused the largest performance degradation, highlighting the necessity of both correct ordering and comprehensive reasoning coverage.
  • Transition Model: The learned transition model outperformed heuristic ordering rules, demonstrating the value of learning soft ordering preferences from data.

5. Significance and Impact

• Paradigm Shift: The paper challenges the "set-based" retrieval assumption in RAG, advocating for a shift toward trajectory-based retrieval.
• Process Reasoning: It enables LLMs to reason over dynamic processes, causal chains, and evolving systems, which is critical for domains like scientific discovery, emergency management, and complex system analysis.
• Generalizability: While tested on cyclone scenarios, the framework is applicable to any domain where the sequence of events determines the outcome (e.g., legal case progression, medical treatment pathways, software debugging).

In conclusion, OKH-RAG demonstrates that how evidence is organized is as critical as what evidence is retrieved. By integrating higher-order interactions with explicit order modeling, it significantly enhances the fidelity and consistency of reasoning in large language models.