Skip to content

Cognition on Graph: Navigating Massive Knowledge Space via Cognitive Cycles and Bidirectional Graph-Text Synergy

Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/zhougengxian/CoG
Area: LLM Reasoning
Keywords: Knowledge Graph, Retrieval-Augmented Generation, Cognitive Cycle, Bidirectional Graph-Text Synergy, Multi-Hop Question Answering

TL;DR

Addressing the structural sparsity of knowledge graphs and the severe noise of global corpus retrieval, this paper introduces CoG (Cognition on Graph), a training-free cognitive framework that performs continuous plan-explore-synthesis-reflect cycles and establishes bidirectional graph-text synergy, achieving state-of-the-art performance across seven multi-hop QA benchmarks while reducing accessed documents by 12.4×.

Background & Motivation

Retrieval-Augmented Generation (RAG) has emerged as an indispensable paradigm to mitigate static parametric hallucinations in Large Language Models (LLMs) and enhance traceability across knowledge-intensive domains. However, conventional VectorRAG and GraphRAG methodologies predominantly operate in oversimplified, local environments restricted to pre-filtered oracle paragraphs or small, task-specific graph partitions. This constraint inherently conceals the massive ambiguity, lexical distraction, and noise encountered in real-world open-domain information discovery. When scaling up to realistic global knowledge repositories—such as the complete Wikidata graph comprising tens of millions of entities alongside billions of triples and the complete unstructured Wikipedia corpus—the core problem fundamentally escalates from simple passage retrieval into complex, long-horizon knowledge exploration.

Under this realistic global setting, existing exploration paradigms suffer from two critical architectural deficiencies. First, exploration mechanisms remain rigidly dependent on Knowledge Graph (KG) topologies with insufficient utilization of unstructured text. Mainstream graph-driven agents such as ToG, StructGPT, and DoG navigate purely across pre-existing relational triples; even hybrid approaches like ToG-2 merely incorporate textual passages as passive auxiliary context for relevance scoring, failing to harness novel entities extracted from text to actively steer and bridge graph traversals. Consequently, when the underlying KG suffers from factual omissions or structural sparsity, these systems inevitably stall. Second, existing exploration strategies are inherently brittle and non-adaptive. Relying strictly on pre-annotated question entities as rigid starting points, they lack systemic mechanisms for failure diagnosis, proactive planning, and dynamic backtracking, rendering them highly prone to getting stranded in dead ends or overwhelmed by explosive distractor subgraphs.

Facing complex multi-hop challenges, human researchers do not execute blind, unidirectional graph traversals; instead, they engage in a dynamic, self-correcting cognitive loop of formulating hypotheses, gathering multi-source evidence, reflecting upon intermediate findings, and strategically adjusting course. Inspired by human problem-solving, this paper develops CoG, natively unifying cognitive closed loops with bidirectional graph-text synergy. Core idea: instantiate an autonomous cognitive loop of proactive planning, dual-source progressive exploration, multi-evidence synthesis, and global reflection, where entities dynamically extracted from unstructured text actively guide graph traversal to bridge structural knowledge gaps in massive heterogeneous knowledge spaces.

Method

Overall Architecture

CoG operates over an open global knowledge base \(\mathcal{K} = \{\mathcal{G}, \mathcal{D}\}\), consisting of the full Wikidata graph \(\mathcal{G} = (\mathcal{E}, \mathcal{R}, \mathcal{T})\) (89.3 million entities, 823.7 million relational triples, and 562.0 million attribute triples) and the full English Wikipedia text corpus \(\mathcal{D}\) (7.1 million entity articles totaling over 5 billion words). The architecture operates in four tightly integrated phases: Proactive Adaptive Planning, Dual-Source Progressive Exploration, Bidirectional Evidence Synthesis, and Global Reflection & Strategic Recovery. Across multiple exploration turns, the framework maintains three long-term memory structures: a Notebook \(\mathcal{N}\) accumulating verified facts, a Candidate Entity Pool \(\mathcal{P}\) managing deferred yet promising search leads, and an Interaction History \(\mathcal{H}\) logging turn-by-turn plans and retrieval summaries to guide global retrospection.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400, 'subGraphTitleMargin': {'top': 8, 'bottom': 16}}}}%%
flowchart TD
    Q["Input Question q + Global Knowledge Base"] --> P["Proactive Adaptive Planning<br/>Query analysis + decomposition + anchor identification"]

    subgraph DUAL["Dual-Source Progressive Exploration"]
        direction TB
        KG["Three-Stage KG Exploration<br/>Context-aware linking → relation discovery → fact pruning"]
        TXT["Hierarchical Text Exploration<br/>Adaptive page selection → global skimming → detailed reading"]
        KG <-->|Text-extracted entities bridge KG gaps / KG anchors guide text retrieval| TXT
    end

    P --> DUAL
    DUAL --> S["Bidirectional Evidence Synthesis<br/>Multi-source distillation + sufficiency judgment J_t"]

    S -->|SUFFICIENT| ANS["Final Reasoning Chain Generation<br/>Synthesize notebook N into faithful answer"]
    S -->|INSUFFICIENT_USEFUL| C_EXP["Deepening Forward Reflection<br/>Update notebook N and candidate pool P to refine sub-queries"]
    S -->|INSUFFICIENT_USELESS| C_ADJ["Global Retrospection & Recovery<br/>Diagnose strategic error via H and pivot to candidate pool P"]

    C_EXP -->|P_t+1| DUAL
    C_ADJ -->|P_t+1| DUAL

Key Designs

1. Proactive Adaptive Planning: Decoupling Gold Annotations via Intent-Driven Decomposition

Prior GraphRAG approaches heavily rely on gold-annotated topic entities provided by curated benchmarks, rendering them brittle when exposed to uncurated, free-form natural language questions. To confer genuine problem-solving autonomy, CoG's planning module performs direct semantic deconstruction on the raw input question \(q\). The LLM conducts global query analysis to infer underlying information dependencies \(A_0\), decomposes compound constraints into up to 5 focused, parallelizable sub-queries \(Q_0 = \{q_1^{(0)}, \dots, q_B^{(0)}\}\), and identifies a strictly corresponding list of core anchor entities \(E_0 = \{e_1^{(0)}, \dots, e_B^{(0)}\}\). This formulation is represented as:

\[P_0 = (A_0, Q_0, E_0) = \text{Prompt}_{init}(q, \text{LLM})\]

By transforming a composite question into modular, anchor-grounded exploration tasks, this design eliminates reliance on external entity pre-annotations and prevents initial combinatorial explosion across the global graph.

2. Dual-Source Progressive Exploration: Cross-Modal Pruning and Text-Guided Traversal

Navigating 90 million entities and 7 million full-text documents demands rigorous noise filtering. On the structured KG side, CoG executes a three-stage funnel: First, context-aware coarse-to-fine Entity Linking retrieves top-20 candidate nodes via Qwen3-Embedding-4B vector similarity over FAISS, followed by LLM-based disambiguation evaluating candidate profiles (aliases, descriptions, and graph degree) against the query context to determine \(e^*\). Second, Relation Discovery queries all incoming and outgoing relations of \(e^*\) via Redis, pruning high-degree hubs using global relation frequency statistics and semantic alignment to yield a compact schema subset \(R_{sel}\). Third, Fact Pruning filters retrieved relational and attribute triples, retaining only facts \(F^{KG}\) that directly answer the sub-query or serve as promising intermediate stepping stones.

Concurrently, the unstructured text module employs hierarchical reading: Adaptive Page Selection handles disambiguation pages and search misses via Wikipedia API feedback and phonetic/spelling suggestions; Global Skimming evaluates article summaries, infoboxes, and table-of-contents structures to identify high-potential sections \(S_{sel}\); Detailed Reading segments selected sections, applies dense retrieval via bge-m3 to fetch top-3 relevant chunks, serializes embedded tables into structured markdown, and jointly reasons over them to extract fine-grained facts \(F^{text}\). Crucially, newly identified entities and numeric stats extracted from textual narratives and tabular records are fed back as novel anchor entities for subsequent KG traversal, creating an active bidirectional bridge that resolves KG sparsity.

3. Bidirectional Evidence Synthesis: Unified Information Distillation and Three-Way Decision Routing

Heterogeneous evidence from relational triples and unstructured passages differs fundamentally in schema and density. The synthesis module employs structured prompts instructing the LLM to execute verbatim, high-fidelity information extraction without lossy paraphrasing, organizing verified facts alongside promising leads into a unified summary \(M_t\). Concurrently, the module cross-references the cumulative Notebook \(\mathcal{N}\) and current plan \(P_t\) to emit a discrete three-way progress judgment \(J_t\):

\[(J_t, M_t) = \text{Prompt}_{syn}(q, P_t, K_t, \mathcal{N}, \text{LLM})\]

The judgment explicitly selects among three operational states: SUFFICIENT (evidence fully resolves the question, triggering final answer generation), INSUFFICIENT_USEFUL (valuable progress made, motivating forward search refinement), and INSUFFICIENT_USELESS (retrieved evidence is off-target or stuck in a dead end, triggering strategic recovery).

4. Global Retrospection & Recovery: Dead-End Diagnosis and Dynamic Memory Management

Standard multi-hop retrieval pipelines lack rollback mechanisms, allowing early disambiguation errors to irreversibly cascade into catastrophic failure. When \(J_t\) signals INSUFFICIENT_USEFUL, the forward reflection path updates Notebook \(\mathcal{N}\), archives promising yet unexpanded leads into Candidate Pool \(\mathcal{P}\), and formulates refined sub-queries \(P_{t+1}\). Conversely, when \(J_t\) evaluates to INSUFFICIENT_USELESS, the recovery module activates global retrospection over the entire Interaction History \(\mathcal{H} = \bigcup_{i} \{(P_i, M_i)\}\). By diagnosing the root strategic error (e.g., overly narrow criteria or misidentified entity categories), CoG discards the dead-end branch, pops high-priority alternative entities from \(\mathcal{P}\), or reformulates orthogonal investigation angles, ensuring exceptional fault tolerance and resilience.

Benchmark & Evaluation Protocol

CoG is comprehensively benchmarked under an open global knowledge setting without oracle document restrictions, integrating the full Wikidata dump (May 2024; 89.3M entities, 1.38B triples) and full English Wikipedia (7.1M articles, >5B words). The primary backbone LLM is standardized to Qwen3-32B (non-thinking mode) across CoG and all baselines to ensure equitable comparison. Text chunk dense retrieval uses bge-m3, while KG entity linking leverages Qwen3-Embedding-4B. Exploration limits are configured to a maximum depth of 4 and an exploration width of up to 5 concurrent sub-queries per turn, with top-20 candidates for entity linking and top-3 chunks per section.

Evaluations span seven multi-hop QA benchmarks: four KG-centric tasks requiring multi-hop structural traversals (KGQAGen 1,079 test queries, CWQ 1,024 queries, QALD10-en 333 queries, and WebQSP 1,430 queries) and three text-centric tasks demanding cross-document semantic synthesis (2WikiMQA 500 queries, MusiQue 500 queries, and AdvHotpotQA 308 queries with adversarial distractor passages). Exact Match (EM, %) is reported as the primary metric (median of three independent runs), complemented by token-level F1 and reference-based LLM-as-judge scoring.

Key Experimental Results

Main Results

Under identical Qwen3-32B model capacities, CoG substantially outperforms representative LLM-only, Text-based RAG, KG-based RAG, and Hybrid RAG baselines across all seven benchmarks:

Dataset Category Prev. SOTA (ToG-2) Strongest Agent Baseline CoG (Ours) Relative Gain over ToG-2
KGQAGen KG-based 55.61% 54.77% (DoG) 74.70% +34.3%
CWQ KG-based 41.41% 34.18% (ReAct) 42.87% +3.5%
QALD10-en KG-based 53.45% 55.86% (DoG) 55.26% Competitive
WebQSP KG-based 81.89% 82.38% (DoG) 81.75% Competitive
2WikiMQA Text-based 73.00% 71.60% (IRCoT) 85.20% +16.7%
AdvHotpotQA Text-based 35.71% 47.08% (IRCoT) 51.95% +45.5%
MusiQue Text-based 16.20% 20.60% (IRCoT) 27.80% +71.6%

CoG achieves an overall average EM of 56.30% across all tasks. Furthermore, under LLM-as-judge evaluation, CoG achieves an average CORRECT rate of 61.63% (surpassing the top baseline IRCoT by +12.10 points), and a token-level F1 of 49.87% (+4.49 points over ToG-2), demonstrating consistent superiority under both lexical and semantic evaluation.

Ablation Study

Ablation investigations systematically isolate knowledge sources, bidirectional feedback mechanisms, and cognitive strategies across all seven benchmarks:

Ablation Setting KG Tasks Avg. Text Tasks Avg. Overall Avg. EM (%) Delta Mechanistic Analysis
CoG (Full) 63.65% 54.98% 56.30% - Full cognitive cycle with bidirectional graph-text synergy
w/o Text 60.67% 31.22% 48.38% -7.92% Text corpus removed; severe degradation on text-heavy tasks
w/o KG 48.60% 50.09% 49.38% -6.92% Knowledge graph removed; structural multi-hop grounding lost
w/o T-guide 62.83% 46.20% 51.36% -4.94% Text-to-KG entity feedback disabled; KG path breaks unbridged
w/o Synthesis 61.13% 50.54% 52.67% -3.63% Dual-source unified distillation module removed
w/o Reflect 62.39% 52.95% 54.44% -1.86% Reflection and retrospection-based recovery disabled
w/o Plan 64.06% 51.38% 54.59% -1.71% Proactive query decomposition and analysis removed
w/o Adap.EL 62.48% 52.38% 54.21% -2.09% Context-aware coarse-to-fine entity linking disabled

Key Findings

  • Text Bridges Structural Graph Gaps: Disabling text-to-graph guidance (w/o T-guide) degrades overall EM by 4.94 points, with catastrophic drops on AdvHotpotQA (51.95% → 39.61%) and MusiQue (27.80% → 22.80%). This highlights that extracting candidate entities from text to dynamically seed subsequent graph traversals is vital to overcome incomplete graph schemata.
  • Order-of-Magnitude Exploration Efficiency: Compared to ToG-2's exhaustive beam search, CoG's goal-oriented planning accesses an average of only 2.6 unique entity documents per query versus 32.5 documents for ToG-2, representing a 12.4× efficiency improvement.
  • Empowering Lightweight Open Models: Deployed on a compact Qwen3-8B backbone, CoG achieves a massive +113.2% relative gain (EM jumping from 23.91% to 50.97%). Remarkably, CoG-8B (50.97%) outperforms all evaluated 32B baselines (including IRCoT 32B at 44.58% and ToG-2 32B at 45.90%), offering an extraordinarily cost-effective deployment profile.
  • High Reasoning Faithfulness: Expert manual evaluation reveals that among EM-correct predictions, CoG attains 89.1% True Positives with fully verified reasoning chains, yielding only 3.6% severe false positives (Weak FP + FP), compared to 29.1% for Self-Consistency and 12.7% for ToG-2.

Highlights & Insights

  • Bidirectional Graph-Text Synergy: Unlike previous hybrid RAG pipelines that treat unstructured text as a passive auxiliary validation set, CoG establishes an active bidirectional loop where textual entities actively spawn new graph exploration paths, seamlessly bridging symbolic relation gaps.
  • Cognitive Self-Correction and Recovery: By integrating a multi-turn Interaction History \(\mathcal{H}\) with a Candidate Entity Pool \(\mathcal{P}\), CoG successfully diagnoses dead ends (e.g., pivoting away from generic team stats toward historical seasonal receiving leaders) and backtracks to deferred leads, mimicking human expert persistence.
  • Democratizing Reasoning for Small LLMs: CoG's structured cognitive cycle imposes robust trajectory constraints that prevent smaller language models (8B) from derailing into parametric hallucinations, demonstrating that cognitive architecture can effectively substitute for raw parameter scale.

Limitations & Future Work

  • Inference Latency Overhead: The sequential nature of the multi-stage cognitive cycle involves multiple LLM inferences per turn (planning, linking, pruning, reading, synthesis, and reflection), leading to average latencies of 150–280 seconds per query on complex benchmarks like MusiQue and KGQAGen.
  • Sensitivity to Backbone Instruction Following: The framework relies on structured JSON outputs and disciplined in-context extraction; weaker sub-7B models occasionally struggle with strict schema adherence or hallucinate table indices during detailed reading.
  • Future Directions: Opportunities exist to parallelize dual-source retrieval pipelines asynchronously, distill specialized lightweight routing agents to handle planning and reflection, and pre-cache frequent global meta-paths to drastically reduce per-round wall-clock latency.
  • vs ToG & ToG-2 (Sun et al., 2024; Ma et al., 2025b): ToG operates solely on knowledge graphs and suffers from incompleteness; ToG-2 adds textual retrieval but remains a passive, unidirectional beam search that accesses 12.4× more documents and lacks recovery mechanisms. CoG introduces bidirectional text-to-graph guidance and closed-loop reflection to actively bypass dead ends.
  • vs DoG & PoG (Ma et al., 2025a; Chen et al., 2024b): While PoG implements graph backtracking and DoG uses multi-agent debate, both remain restricted to clean, single-source knowledge graphs. CoG scales to open-world, heterogeneous knowledge spaces, robustly handling real-world textual noise and billion-scale graph exploration.

Rating

  • Novelty: ⭐⭐⭐⭐⭐ The closed-loop cognitive architecture and bidirectional text-guided graph exploration represent a significant conceptual leap over static, graph-bound RAG.
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ Evaluated on seven diverse benchmarks under full Wikidata and Wikipedia scales, featuring multi-model backbones, ablation breakdowns, depth curves, and rigorous manual faithfulness audits.
  • Writing Quality: ⭐⭐⭐⭐⭐ Exceptionally clear framing, rigorous mathematical task formulation, and comprehensive prompt and trajectory documentation.
  • Value: ⭐⭐⭐⭐⭐ Highly valuable, training-free open-source contribution for robust, hallucination-resistant complex reasoning over realistic global knowledge repositories.