PaperlayerView exact revision on arXiv

Source-linked AI summary

PersonalAI 2.0: Enhancing knowledge graph traversal/retrieval with planning mechanism for Personalized LLM Agents

Mikhail Menschikov, Matvey Iskornev, Alexander Kharitonov, Alina Bogdanova, Mikhail Belkin, Ekaterina Lisitsyna, Artyom Sosedka, Victoria Dochkina, Ruslan Kostoev, Ilia Perepechkin, Evgeny Burnaev

arXiv:2605.13481v1cs.CL

TL;DR

PAI-2 addresses limitations of GraphRAG systems in scalable, precise, and adaptive retrieval for fact-rich, multi-hop question answering. It combines graph-based external memory with dynamic, multistage planning, entity and vertex matching, clue-query generation, and iterative traversal. Across six benchmarks, it reports higher performance than several baselines, with gains from plan enhancement and graph traversal, while its memory construction remains limited by implicit temporal representation and simplified ontology structure.

  • Problem

    GraphRAG systems face scalability, retrieval-precision, and dynamic multi-hop reasoning challenges, while LLMs require external knowledge for fact-rich domains.

  • Method

    PAI-2 integrates graph-based external memory with a multistage pipeline that plans iterative searches using extracted entities, matched vertices, clue-queries, and subgraph traversal.

  • Results

    PAI-2 shows a 4% average gain by LLM-as-a-Judge on 4 out of 6 benchmarks versus LightRAG, RAPTOR, and HippoRAG 2.

  • Takeaways & Limitations

    Search-plan enhancement gives an 18% boost and advanced graph traversal gives a 6% boost compared with their respective alternatives across six datasets.

  • Takeaways & Limitations

    PAI-2 has limited temporal representation and a simplified ontology structure, which can compromise search accuracy and query performance.

Abstract

from arXiv · show

We introduce PersonalAI 2.0 (PAI-2), a novel framework, designed to enhance large language model (LLM) based systems through integration of external knowledge graphs (KG). The proposed approach addresses key limitations of existing Graph Retrieval-Augmented Generation (GraphRAG) methods by incorporating a dynamic, multistage query processing pipeline. The central point of PAI-2 design is its ability to perform adaptive, iterative information search, guided by extracted entities, matched graph vertices and generated clue-queries. Conducted evaluation over six benchmarks (Natural Questions, TriviaQA, HotpotQA, 2WikiMultihopQA, MuSiQue and DiaASQ) demonstrates improvement in factual correctness of generating answers compared to analogues methods (LightRAG, RAPTOR, and HippoRAG 2). PAI-2 achieves 4% average gain by LLM-as-a-Judge across four benchmarks, reflecting its effectiveness in reducing hallucination rates and increasing precision. We show that use of graph traversal algorithms (e.g. BeamSearch, WaterCircles) gain superior results compared to standard flatten retriever on average 6%, while enabled search plan enhancement mechanism gain 18% boost compared to disabled one by LLM-as-a-Judge across six datasets. In addition, ablation study reveals that PAI-2 achieves the SOTA result on MINE-1 benchmark, achieving 89% information-retention score, using LLMs from 7-14B tiers. Collectively, these findings underscore the potential of PAI-2 to serve as a foundational model for next-generation personalized AI applications, requiring scalable, context-aware knowledge representation and reasoning capabilities.

I. INTRODUCTION

PAI-2 addresses GraphRAG limitations in scalability, retrieval precision, and dynamic multi-hop reasoning by combining graph-based external memory with planned, iterative search. Its pipeline decomposes questions, refines retrieval, and traverses targeted subgraphs to improve factual answer generation.

  • Motivation: Existing GraphRAG methods struggle with scalable, precise retrieval and dynamic search for multi-hop questions.Static ontologies and node-level retrieval patterns limit adaptability to varied domains and user intents.
  • Method: PAI-2 performs dynamic, iterative searches guided by entity extraction, vertex matching, clue-query generation, and query refinement.Complex questions are decomposed into subqueries so retrieval can focus on relevant graph segments.
  • Implications: PAI-2 is positioned as a framework for personalized applications requiring contextual awareness, precision, and structured external memory.The paper names personalized education and customer-service chatbots as example application areas.
  • Contribution: PAI-2 integrates graph-based external memory with LLM reasoning to plan and manage knowledge-graph traversal.The framework stores unstructured textual knowledge externally while using LLM capabilities to plan information search.
  • Pipeline: The QA pipeline begins with a natural-language question, generates independent subquestions and search plans, and processes subquestions independently, optionally in parallel.The workflow is described as a thirteen-stage pipeline for memory-graph information search.
  • Pipeline: Graph traversal results are filtered and summarized into subanswers, with unfinished search-plan steps refined before subanswers are aggregated into a final response.If the exploration limit is reached without sufficient knowledge, the pipeline returns a No Answer stub.

A. QUESTION PREPROCESSING

PAI-2 preprocesses questions into cleaner, enhanced, and independent subquestions, then converts each search step into targeted graph queries. Retrieved graph evidence is filtered, summarized, and used to decide whether answers or further plan refinement are needed.

  • Question preprocessing: PAI-2 denoises and enhances each question before decomposing composite questions into independently answerable subquestions.Preprocessing removes syntactic and unnecessary-word noise, improves terminology, and expands meaning before decomposition.
  • Search planning: For each subquestion, PAI-2 generates an initial plan containing natural-language search steps.The plan is represented as P = [s1, s2, ..., sM].
  • Entity-to-graph matching: Named entities from each search step are matched to memory-graph object vertices using dense and sparse retrieval models.The maximum number of vertices linked to one entity is controlled by the hyperparameter Vm.
  • Graph exploration: PAI-2 generates clue-queries from search steps and selected vertex groups, then uses them to control independent graph traversals.The matched vertices serve as traversal starting points, and the method combines dense and sparse retrieval for vertex matching.
  • Evidence synthesis: Retrieved triples are filtered by relevance and summarized through clue answers into knowledge for the current search step.The aggregation first summarizes each filtered triple set and then combines the clue answers for the search step.
  • Adaptive planning: After each exploration step, PAI-2 checks whether sufficient knowledge supports an answer and enhances the remaining plan when necessary.If the search limit is exceeded without sufficient evidence, the pipeline generates a No Answer stub.

C. ANSWERS AGGREGATION

PAI-2 aggregates independently generated subanswers into a final answer while evaluating baseline performance, traversal choices, language-model backbones, and configuration settings. The experiments compare planned graph retrieval against flattened retrieval across multiple benchmarks and models.

  • Answer aggregation: PAI-2 combines answers to independently processed subquestions into a final answer to the original question.The aggregation operation receives the initial question, subquestions, and their subanswers.
  • Research questions: The experiments ask whether PAI-2 outperforms baselines and whether graph traversal improves efficiency over a naive flattened retriever.These questions are formalized as RQ1 and RQ2.
  • Research questions: The study evaluates how efficiency varies with the number of clue-queries generated for each search-plan step.This is formalized as RQ3.
  • Model selection: Qwen2.5 7B was selected as the LLM backbone after few-shot HotpotQA evaluation because it performed best on four metrics.The comparison included Qwen2.5 7B, Llama3.1 7B, Granite3.3 8B, and Gemma2 9B.
  • Traversal configurations: PAI-2 uses BeamSearch and WaterCircles combinations, including BS + WC and BS + NR, for knowledge-graph traversal.The selected combinations were based on superior and comparative performance in prior research.

B. SUMMARY OF EVALUATED CONFIGURATIONS

The evaluation used controlled PAI-2 configurations across six benchmarks, with memory graphs combining graph and vector components and experiments constrained to manageable dataset subsets.

  • Evaluation setup: 90 QA configurations were evaluated across six benchmarks, using 100 question-answer pairs per benchmark configuration.Each dataset produced 15 distinct QA configurations, with an additional 44 configurations in a HotpotQA LLM few-shot ablation.
  • Memory graph configuration: PAI-2 memory graphs combine a Neo4j graph component with dense and sparse vector representations for semantic similarity during question answering.The graph stores textual vertices, properties, and relationships, while vector storage uses Qdrant and OpenSearch.
  • Datasets: Evaluation covered Natural Questions, TriviaQA, HotpotQA, 2WikiMultihopQA, MuSiQue, and DiaASQ to vary domains, structural complexity, and reasoning requirements.The benchmark selection was intended to mitigate bias associated with limited domain diversity.
  • LLM ablation: Table 1 compares PAI-1 and PAI-2 across four LLMs using Context Relevance, Faithfulness, LLM-as-a-Judge, and Groundedness scores.The comparison identifies the LLM selected for the main experiments.
  • Dataset preparation: The constructed memory graphs used manageable representative subsets because large-graph construction and traversal required substantial computational and engineering resources.The subsets enabled iterative tuning of retrieval algorithms and LLM configurations within practical resource constraints.

B. METRICS

PAI-2 is evaluated with LLM-as-a-Judge and complementary RAGAS metrics across benchmark comparisons, ablations, and efficiency measurements. Results indicate gains from adaptive planning, graph traversal, and clue-query expansion, alongside higher processing cost and an 89% MINE information-retention score.

  • Evaluation metrics: LLM-as-a-Judge labels generated answers as correct or incorrect and uses accuracy as the main metric.Qwen2.5 7B evaluates question-answer pairs containing the question, ground truth, and generated answer.
  • Evaluation metrics: Context Relevance, Faithfulness, and Groundedness provide additional measures of retrieval pertinence and answer support.These RAGAS metrics assess whether retrieved context matches the query and whether answer claims are supported by that context.
  • Benchmark results: 4% average LLM-as-a-Judge gain was achieved by PAI-2 on TriviaQA, 2WikiMultihopQA, and MuSiQue compared with the evaluated alternatives.On HotpotQA and DiaASQ, PAI-2 was comparable to HippoRAG and PAI-1, while NaturalQuestions showed an 11% difference from HippoRAG 2.
  • Ablation results: 18% LLM-as-a-Judge degradation occurred when the search plan enhancement mechanism was disabled.The reported example shows that modifying later queries using information from earlier searches can provide sufficient evidence for the final answer.
  • Comparison with PAI-1: 27%, 26%, and 10% average increases were reported for Context Relevance, Faithfulness, and LLM-as-a-Judge, respectively, versus PAI-1.The paper associates these gains with planning, search-step enhancement, detailed clue-queries, and graph traversal.
  • Clue-query ablation: 4% average LLM-as-a-Judge gain resulted from increasing the maximum clue-queries per search step from 1 to 8.The paper attributes this to traversing and aggregating knowledge distributed across subgraphs associated with multiple vertices.
  • Efficiency: PAI-2 requires approximately twice PAI-1’s time per question because its retrieval iterations vary with question complexity.The identified bottlenecks are LLM inference, vector search, and knowledge graph traversal.
  • Memory-graph construction: 89% information-retention score was achieved on the MINE benchmark by the Memorize plain-text-to-knowledge-graph extraction pipeline.This result is reported as state of the art for evaluating factual completeness in PAI memory-graph construction.

VII. CONCLUSION

PAI-2 combines LLMs with graph-based external memory to improve knowledge retrieval and reasoning. Across benchmarks and ablations, dynamic query planning and subgraph traversal produced gains over existing methods.

  • PAI-2 integrates LLM capabilities with graph-based external memory for knowledge retrieval and reasoning.
  • PAI-2 uses systematic query decomposition and dynamic planning of subgraph traversal and retrieval.
  • 4% average LLM-as-a-Judge improvement was achieved on 4 of 6 benchmarks against LightRAG, RAPTOR, and HippoRAG 2.
  • 18% LLM-as-a-Judge boost came from enabling search-plan enhancement, while advanced graph traversal produced a 6% retrieval-precision boost over flat retrieval.
  • PAI-2 achieved an 89% information-retention score on MINE-1 and showed greater memory-construction stability than KGGen and Wikontic with 7-14B LLMs.
  • PAI-2 combines LLM expressiveness with knowledge-graph structure to support nuanced responses and reliable factual outputs.

VIII. LIMITATIONS

PAI-2 has limitations involving latency, temporal representation, ontology, entity definitions, and semantic deduplication. The authors identify these constraints as priorities for improving scalability and robustness.

  • Representation limitations: Explicitly converting timestamps into plain text can lose critical contextual data because of the “Lost in the Middle” problem.The resulting loss may compromise overall search accuracy.
  • Representation limitations: The simplified ontology provides limited indexing and filtering characteristics, resulting in suboptimal query performance and less effective QA algorithms.
  • Representation limitations: Object vertices lack formal entity definitions, making polysemous searches require extensive traversal and potentially producing incomplete responses or false positives.
  • Representation limitations: Exact-string duplicate detection can replicate synonymous triplets, increasing storage demands, slowing retrieval, and complicating graph updates.The issue is especially relevant when pruning obsolete vertices and edges.
  • Future direction: The authors frame these issues as future research priorities for improving the scalability and robustness of personalized KG-based QA systems.

APPENDIX A LLM PROMPTS USED IN QUERY PREPROCESSING STAGE

The appendix catalogs LLM prompts used to preprocess questions, generate and enhance search plans, extract entities, create clue-queries, and aggregate answers. These prompts cover the QA pipeline from question decomposition through final response generation.

  • Query preprocessing: Question preprocessing prompts check grammatical and punctuation errors, remove unnecessary wording, edit grammar, rephrase terminology, and clarify text for search engines.
  • Query preprocessing: Prompts determine whether a question contains independent subquestions and decompose complex questions into independently answerable components.
  • Memory-graph exploration: Search-plan prompts generate an initial plan, extract named entities, and create clue-questions from plan steps and matched object vertices.
  • Memory-graph exploration: Memory-graph prompts generate clue answers from filtered triples and summarize the answers associated with clue-queries.
  • Plan enhancement and aggregation: Additional prompts assess answer sufficiency, generate final answers, decide whether plans need enhancement, and refine incomplete plan steps.
  • Plan enhancement and aggregation: The appendix also includes prompts for generating answers from subanswers and documents the prompt sets used across preprocessing and answer aggregation stages.

APPENDIX C PSEUDOCODE

The PAI-2 pseudocode decomposes each user question, plans and iteratively executes subquestion searches, traverses the memory graph for clue-queries, and aggregates subanswers into a final response.

  • Inputs and preprocessing: The pipeline accepts a user question and bounds search-plan steps, clue-queries, matched vertices, and filtered triples before returning an answer.
  • Inputs and preprocessing: Each question is decomposed into subquestions, and an initial search plan is generated independently for every subquestion.
  • Graph retrieval: For each plan step, PAI-2 extracts entities, matches them to graph vertices, combines accepted vertices, and generates clue-queries.
  • Graph retrieval: Each clue-query triggers graph traversal, relevance filtering of retrieved triples, and clue-answer generation.
  • Iteration and planning: Clue answers are summarized and tested for sufficiency; insufficient evidence causes the search plan to be enhanced before another iteration.
  • Iteration and planning: The pipeline finalizes a subanswer when sufficient evidence is found, otherwise generates a no-answer stub, then aggregates all subanswers.

APPENDIX D DATASETS PREPROCESSING OPERATIONS FOR PROPOSED QA PIPELINE EVALUATION

The evaluation datasets were selected from multiple source subsets and transformed through filtering, chunking, sampling, or no preprocessing. The resulting sets are summarized by dataset characteristics for QA-pipeline evaluation.

  • Dataset construction: Natural Questions used 100231 QA pairs, filtered answer lengths, and combined the first 2000 pairs with 2000 randomly selected answers to form 4000 documents.
  • Dataset construction: TriviaQA used 7993 validation QA pairs, with long documents chunked using LangChain’s RecursiveCharacterTextSplitter.
  • Dataset construction: HotpotQA used 7405 validation QA pairs and 13781 documents, filtered documents to 64–1024 characters, and selected the first 2000 QA pairs.
  • Dataset construction: 2WikiMultihopQA used 12576 development QA pairs and 56687 documents, filtered documents to 64–1024 characters, and selected the first 2000 QA pairs.
  • Dataset construction: MuSiQue used 2417 validation QA pairs and 21100 documents, filtered contexts to 64–1024 characters, and selected the first 2000 QA pairs before expansion.
  • Dataset construction: DiaASQ used a modified dataset containing 5698 QA pairs and 3483 documents without additional preprocessing or filtering.
  • Dataset characteristics: Table 24 reports dataset characteristics, including average question, answer, relevant-document lengths, and document counts across the six evaluation subsets.

APPENDIX E RETRIEVAL HYPERPARAMETERS

The appendix specifies retrieval and evaluation settings, then reports the characteristics, construction costs, and parsing quality of PAI-2 memory graphs. These details document both experimental reproducibility and the practical resource requirements of graph construction.

  • Retrieval hyperparameters: Retrieval configurations set graph depth, path counts, filtering, reranking, and vertex-selection parameters across the evaluated setups.The configurations include max_depth 5, max_paths 10, strict filtering, and dense-triplet reranking with threshold 0.5.
  • Evaluation settings: Deterministic LLM-as-a-Judge evaluation used Qwen2.5 7B with seed 42, temperature 0.0, top_k 1, and num_predict 2048.The prompts used for assessment are provided in Table 25.
  • Memory-graph construction: PAI-2 evaluation constructs six memory graphs from the selected datasets using Qwen2.5 7B.The structural characteristics of these graphs are reported in Table 26.
  • Memory-graph construction: Parsing errors caused minor graph incompleteness, with average error rates of 0.08% for TriviaQA, 0.02% for MuSiQue, 0.05% for DiaASQ, and 0.0% for the other three datasets.The other zero-error datasets were Natural Questions, HotpotQA, and 2WikiMultihopQA.
  • Construction cost: ≈7.5 M tokens, ≈46.5 hours, and ≈2 GB of disk space were required to store 4182 documents averaging 519 characters in the memory graph.These measurements cover token use, construction time, and storage requirements.

APPENDIX H NON AGGREGATED RESULTS FOR CLUE QUERIES NUMBER ABLATION STUDY

The appendix examines how clue-query counts and retrieval choices affect QA results, then reports information-retention and evaluation-comparison analyses. It also includes MINE-1 comparisons across systems and PAI-2 configurations.

  • Clue-query ablation study: The clue-query ablation study evaluates QA performance as the generated number of clue queries varies across search-plan steps.Reported metrics are Context Relevance, Faithfulness, and LLM-as-a-Judge scores.
  • Clue-query ablation study: The ablations compare BeamSearch combined with WaterCircles or NaiveRetriever, both with unrestricted traversal and with episodic vertices excluded.The tables separately report these retrieval mixtures and traversal conditions.
  • MINE-1 evaluation: 89% average MINE-1 information-retention was achieved by PAI-2, compared with 28% for Wikontic and 39% for KGGen.Figure 2 shows the score distributions across 100 articles.
  • MINE-1 evaluation: PAI-2’s MINE-1 results are reported against KGGen, Wikontic, and GraphRAG across different LLM backbones.Table 33 describes PAI-2 as achieving the highest retention performance across all evaluated LLMs under its specified vertex-retrieval setting.
  • MINE-1 ablation: The accepted-vertex ablation compares configurations across six LLMs, including all vertex types and episodic-only retrieval.The reported comparison examines how vertex-type selection relates to MINE-1 information-retention scores.
  • Evaluation comparison: HumanEval agreement and correlation with LLM-as-a-Judge are reported for best PAI-2 and HippoRAG 2 configurations across six datasets.The appendix provides Krippendorff’s alpha, Pearson correlation, and paired HumanEval and LLM-as-a-Judge scores; annotation involved three experienced authors.
Loading 2605.13481v1…