{"id":"159dd01e-45e3-4848-9f42-4c2efe47de4a","arxiv_id":"2507.08945","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"GraphRunner improves graph-based retrieval by generating and validating a complete traversal plan before executing high-level multi-hop actions, outperforming Graph-CoT on GRBENCH with 10 to 50 percent higher accuracy and 3 to 13 times lower inference cost.","lead":"GraphRunner is a three-stage system that plans a graph traversal with an LLM, checks the plan against the graph structure, and then executes it to answer questions over knowledge graphs. It reports higher accuracy and much lower cost and latency than previous graph RAG methods on the GRBENCH benchmark.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Figure 2 contradicts Section 4.2: GraphRunner is below Graph-CoT on easy E-Commerce (60.5 vs 62.4), easy Healthcare (69.0 vs 76.2), medium E-Commerce (19.0 vs 20.4), and medium Legal (30.7 vs 51.2), undermining the claimed outperformance across all difficulty levels.","rationale":"Stress-test of arXiv:2507.08945. The reader's verdict is CONDITIONAL with the weakest assumption about Find_Node's unreported theta and schema dependency. While that is a valid reproducibility concern, I find a more direct threat to the central claim. Section 4.2 explicitly claims that GraphRunner outperforms Graph-CoT across all difficulty levels. The paper's own Figure 2 displays numeric scores that contradict this claim: GraphRunner is lower than Graph-CoT in Easy E-Commerce and Easy Healthcare, and in Medium E-Commerce and Medium Legal. These are not small differences (up to 20 points in Legal Medium). The text characterizes easy questions as 'marginal improvements' but at least two easy cells are regressions. This internal inconsistency means the reported evidence does not support the 'consistent' language used in the abstract and Section 4.2. It is the single most load-bearing concern because it attacks the reliability of the evaluation, which is the basis for the claimed 10-50% improvement. If the figure is correct, the claim is overstated; if the figure is wrong, the paper contains an unaddressed data error. Either way, the reader cannot trust the results. The reader's Find_Node concern, while legitimate, is about generality and parameter choice, not an outright contradiction. I recommend keeping the CONDITIONAL verdict (UNCHANGED) but adding a condition that the authors provide per-difficulty data and resolve the inconsistency. The concrete test is to reconcile Figure 2 with Table 1.","tokens_in":12008,"tokens_out":16458,"duration_ms":177207,"concrete_test":"Request the per-domain, per-difficulty raw question-level scores for GraphRunner and Graph-CoT. Recompute the domain-level GPT4Score in Table 1 as a weighted average of the easy/medium/hard cell scores from Figure 2, using the actual number of questions per split in GRBENCH (healthcare has no hard questions). If the Figure 2 numbers are accurate, the weighted averages should match Table 1; if they do not, either the figure or the table is wrong. Additionally, ask the authors to reconcile the Section 4.2 text with the observed regressions. This single check settles whether the 'consistent outperformance' claim is supported by the data.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that GraphRunner 'consistently outperforms' Graph-CoT with 10-50% GPT4Score gains is load-bearing on the accuracy of the reported evaluation. Section 4.2 states 'GraphRunner outperforms GRAPH-COT across all difficulty levels', but Figure 2 shows the opposite in four domain-difficulty cells: Easy E-Commerce (60.5 vs 62.4), Easy Healthcare (69.0 vs 76.2), Medium E-Commerce (19.0 vs 20.4), and Medium Legal (30.7 vs 51.2) — all GraphRunner lower. The paper gives no explanation for these regressions; instead it claims marginal improvements for easy questions and significant improvements for medium questions. If the figure is accurate, the 'consistent' narrative in the abstract and Section 4.2 is false, and the 10-50% range does not hold per difficulty level. Even if Table 1's domain aggregates are correct, the unacknowledged per-difficulty regressions suggest selective reporting or an error in the data pipeline, making the headline result unreliable. This is more directly damaging to the central claim than the unspecified theta in Find_Node, which is a reproducibility issue rather than an internal contradiction.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes GraphRunner, a three-stage graph-based retrieval framework that separates traversal planning, plan verification, and execution. The planner uses LLMs to produce a holistic traversal plan from high-level actions (Find_Node, Fetch_Neighbors, Find_Common_Nodes), the verifier checks the plan against the graph schema and action definitions before execution, and the executor runs the plan to retrieve context for answer generation. The authors evaluate on GRBENCH with GPT-4, reporting GPT4Score and ROUGE-L across five domains, and claim consistent 10–50% improvements over Graph-CoT together with 3.0–12.9x inference cost reduction and 2.5–7.1x speedup.","tokens_in":12326,"tokens_out":3941,"duration_ms":47623,"significance":"If the reported results hold, GraphRunner would offer a meaningful advance over iterative graph traversal methods by reducing token usage and pre-execution hallucinations, and the high-level action design is a clean idea that others could adopt. The paper is transparent about its limitations (proprietary GPT-4 only, GRBENCH-only evaluation), and the efficiency analysis is a useful contribution. However, the central 'consistent outperformance' claim is weakened by internal contradictions between the text and Figure 2, and by the absence of statistical rigor and ablations. The contribution is therefore plausible but not yet fully substantiated.","major_comments":[{"comment":"The claim that 'GraphRunner outperforms GRAPH-COT across all difficulty levels' is directly contradicted by Figure 2, which shows GraphRunner below Graph-CoT in four domain-difficulty cells: Easy E-Commerce (60.5 vs 62.4), Easy Healthcare (69.0 vs 76.2), Medium E-Commerce (19.0 vs 20.4), and Medium Legal (30.7 vs 51.2). The text also states a 44% improvement in easy Healthcare, but the figure shows GraphRunner lower there. This discrepancy undermines the abstract and Section 4.2's central claim of consistent improvement and the 10–50% range per difficulty level. The authors must correct the figure or the narrative, and provide per-difficulty results that reconcile with the domain-level aggregates in Table 1.","section":"Section 4.2 / Figure 2"},{"comment":"The primary metric GPT4Score is computed by GPT-4 judging whether the answer is correct, while the same GPT-4 model generates the answers. This risks favoring the model's own style rather than ground-truth correctness. The paper reports only point estimates: no standard errors, confidence intervals, or significance tests, and no indication that multiple runs were performed. Given the central quantitative claims, the authors should report variance across repeated runs and validate GPT4Score against a human-annotated subset, especially for the cells where GraphRunner underperforms.","section":"Section 4.1 (Evaluation Metrics)"},{"comment":"The framework's two key mechanisms, the verification stage and the high-level traversal actions, are never isolated in an ablation study. The paper attributes performance gains to 'reducing reasoning errors' and 'detecting hallucinations' (Section 4.2), but without ablations that disable verification or replace high-level actions with 1-hop steps, these attributions are not supported. Table 2's manual error classification also lacks inter-annotator agreement measures or confidence intervals, so the claimed reductions in error probabilities (e.g., 50% of hallucination errors) are not established beyond the authors' subjective coding.","section":"Section 3.3 / Section 4.4"},{"comment":"The Find_Node action is load-bearing because it seeds every traversal, yet its implementation depends on an unreported similarity threshold θ, an unspecified semantic embedding model, and unspecified few-shot example selection. The paper also does not report the number of verification retries or the LLM sampling parameters. These unspecified components make the results difficult to reproduce and prevent assessment of how sensitive the framework is to the threshold; the authors should release these details or include a sensitivity analysis.","section":"Section 3.1.1 / Section 3.2"}],"minor_comments":[{"comment":"The figure contains the typo 'Genarated' and uses inconsistent spacing in action names; please proofread the figure and ensure action names match the notation in Section 3.1.","section":"Figure 4"},{"comment":"The metric is written as 'Rogue-L' in Table 1 and Section 4.1; use the standard spelling 'ROUGE-L'.","section":"Section 4.1"},{"comment":"The notation defines Find_Node(h, t) using attr(v) and similarity but does not formally define the embedding/similarity function or the domain of hints H; adding a one-line definition would improve clarity.","section":"Section 3.1.1"},{"comment":"Table 2 reports error probabilities as single scalars without sample sizes or confidence intervals; please state how many questions were manually classified and whether one annotator or multiple annotators performed the classification.","section":"Section 4.4"}],"recommendation":"major_revision","confidential_remarks":"The paper is currently an arXiv preprint with no code or data release. Given that the central quantitative claim depends on GRBENCH numbers and a proprietary model, I would urge the editor to require the authors to share their evaluation scripts and, if possible, the exact Figure 2 numbers, so the contradiction with Section 4.2 can be resolved definitively. The scientific contribution is salvageable, but the current presentation is not reliable enough for publication without these fixes."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nYou should know two things about GraphRunner. The framework is genuinely different from the iterative single-hop traversal line: planning a whole traversal up front, verifying it against the schema, then executing with high-level actions is a clean departure from Graph-CoT and StructGPT. The efficiency story is also plausible, since you replace many LLM calls with one or two. That part deserves attention.\n\nThe second thing is more worrying. The paper claims GraphRunner 'outperforms GRAPH-COT across all difficulty levels,' but Figure 2 shows the opposite in at least four cells: Easy E-Commerce (60.5 vs 62.4), Easy Healthcare (69.0 vs 76.2), Medium E-Commerce (19.0 vs 20.4), and Medium Legal (30.7 vs 51.2). Those are not marginal; Medium Legal is a 40-point regression. The text explains easy/medium/hard trends but never acknowledges these losses. So the 'consistent' and '10-50%' claims are not supported by the paper's own figure. That is a load-bearing empirical contradiction, and it needs to be reconciled before the headline result is treated as true.\n\nOther soft spots are more familiar. No code or prompts, no error bars or significance tests, no ablations isolating the verification module or the high-level actions. The Find_Node similarity threshold theta is undefined. GPT-4 is both answer generator and judge via GPT4Score, which risks style bias. The manual error classification lacks inter-annotator reliability. These are fixable in revision.\n\nWhat the paper does well: the problem is real, the design is clearly described, the formal definitions of the three actions are useful, and the efficiency gains (3-13x cost reduction) are in the right direction and consistent with the architecture. The limitations section is honest about the narrow dataset and lack of open-source models.\n\nI would send this to a serious referee. The central idea is sound enough to warrant reproduction, but the paper needs major revision: fix the discrepancy between the figure and text, add ablations and variance, and release the code and prompts. As it stands, I would not cite the quantitative claims.\n\nNet: worth engaging, but treat the empirical claims with suspicion until the authors clean this up.","headline":"A sensible planning-verification-execution framework for graph retrieval, but the experimental write-up overclaims: Figure 2 shows GraphRunner losing to Graph-CoT in several cells, so the headline 10-50% claim needs reconciliation.","tokens_in":12849,"tokens_out":3232,"would_cite":false,"duration_ms":35240,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"GraphRunner claims that separating graph traversal planning from execution, with a verification step in between, beats iterative LLM traversal by 10-50% in accuracy while cutting inference cost by 3.0-12.9x.","keywords":["graph-based retrieval","retrieval-augmented generation","knowledge graph traversal","LLM planning","plan verification","hallucination detection","multi-hop traversal","GRBENCH"],"falsifier":"Run GraphRunner on GRBENCH with an open-source LLM replacing GPT-4 and compare the GPT4Score gap to Graph-CoT; if the 10-50% advantage disappears, the three-stage design's reported benefit depends on the planner's reasoning strength, not on verification alone.","tokens_in":11848,"feed_emoji":"🧭","tokens_out":7942,"duration_ms":76709,"temperature":0.7,"pith_summary":"The paper is trying to establish that graph-based retrieval for question answering does not need to be iterative: an LLM can write a complete traversal plan in one pass, a structural checker can reject impossible or hallucinated steps before they run, and then a deterministic agent can execute the plan using high-level actions that jump multiple hops at once. If true, the practical consequence is that knowledge-graph question answering becomes both more accurate and substantially cheaper than the leading step-by-step traversal baseline, because the LLM reasons once instead of at every hop. The claim matters because existing graph RAG approaches either drown the model in noisy subgraph context or let an unverified LLM steer each traversal step, and both failure modes are what GraphRunner targets. The paper backs the claim with GRBENCH results across five domains, showing consistent GPT4Score gains and large reductions in token cost, response time, and error rates.","feed_headline":"Plan, verify, then traverse: GraphRunner beats Graph-CoT by 10-50%","feed_subtitle":"Separating planning from execution cuts LLM costs 3-12.9x and speeds responses 2.5-7.1x on graph QA.","key_machinery":"The load-bearing mechanism is the verified holistic traversal plan: a single LLM inference produces the entire sequence of traversal actions, and a separate verification module checks each action against the graph's node types, edge types, and the allowed action vocabulary before the GraphRunner Agent executes it. The plan is what lets complex operations like multi-hop traversal or shared-neighbor intersection happen in one step rather than through repeated LLM reasoning, and the verification is what catches hallucinated actions, nonexistent types, and impossible edge connections before they waste tokens. The three high-level actions (Find_Node, Fetch_Neighbors, Find_Common_Nodes) are the vocabulary the plan is written in, and the verification module's structural checks are what make the plan safe to execute deterministically.","core_discovery":"GraphRunner's central claim is that separating traversal planning from execution, plus verifying the plan against the known graph schema before running it, removes most of the errors and token waste of LLM-guided graph traversal. The framework defines three actions — Find_Node (semantic match on node attributes), Fetch_Neighbors (single-hop by edge type or multi-hop by node type), and Find_Common_Nodes (shared neighbors across several start nodes) — and asks the LLM to produce one holistic sequence of these actions. A verification module then checks that every action is in the supported set, that node and edge types exist in the schema, and that each proposed edge connection is actually possible; invalid plans are sent back for revision. On the GRBENCH benchmark with GPT-4, GraphRunner reports 10-50% higher GPT4Score than Graph-CoT across all five domains, with inference costs lower by 3.0-12.9x and response times faster by 2.5-7.1x, and its error analysis attributes roughly half of Graph-CoT's hallucination errors and about 80% of its context-window errors to the verification stage.","pith_inferences":["Going beyond the paper: the same plan-verify-execute pattern should transfer to other structured tool-use settings, such as SQL or API calls, where a schema check can reject invalid operations before an LLM's tool call executes.","The Find_Node similarity threshold is not reported or swept; a natural testable extension is to measure how retrieval accuracy varies with that threshold, since a too-high threshold would make the whole plan fail before verification can help.","Because verification checks structural validity rather than semantic intent, the remaining reasoning errors (still nearly 30% of responses) are unlikely to disappear without a semantic or commonsense validation pass, which the paper itself does not propose.","The efficiency numbers are reported for GPT-4 only; an open-source model with weaker instruction following might produce more invalid plans, so the cost savings could shrink if retries become frequent."],"forward_implications":["Graph-based retrieval can be made non-iterative: a single planning inference plus deterministic execution can replace repeated LLM reasoning steps, cutting token use per query by a factor of 3 to 12.9 on the domains tested.","Complex traversals that iterative methods handle in many steps, such as finding nodes shared by two paths, can be compressed into one high-level action, which is the main source of the accuracy gains on medium-difficulty questions.","Pre-execution verification roughly halves hallucination errors and removes about 80% of context-window failures relative to Graph-CoT, so structural validation is a workable mechanism for catching LLM mistakes before they become retrieval failures.","Because the plan is verified against the schema, the approach transfers to any knowledge graph whose node and edge types are known, without fine-tuning or changing the LLM.","Hard questions remain the weak spot: the paper reports only modest gains there, consistent with questions where the answer is not determined by a single traversal path."],"supporting_citations":[{"why":"Supplies the GRBENCH benchmark and the Graph-CoT baseline; the paper's accuracy and efficiency claims are measured against it.","marker":"(Jin et al., 2024)"},{"why":"Defines the Graph-based RAG baseline whose 2-hop subgraph expansion GraphRunner is compared with.","marker":"(Ye et al., 2024)"},{"why":"Provides the Text-based RAG baseline that retrieves individual nodes without graph structure.","marker":"(Lewis et al., 2021)"},{"why":"Defines GPT4Score, the primary accuracy metric used for the headline gains.","marker":"(Fu et al., 2023)"},{"why":"Defines ROUGE-L, the secondary lexical-overlap metric.","marker":"(Lin, 2004)"},{"why":"Introduces StructGPT, the iterative rule-based traversal approach whose single-hop step-by-step design GraphRunner contrasts with.","marker":"(Jiang et al., 2023a)"},{"why":"Underpins the claim that latency grows with output-token length, which justifies the reported response-time speedup.","marker":"(Chen et al., 2024c)"},{"why":"Supplies the token-pricing formula used to compute the reported inference cost reductions.","marker":"(OpenAI, 2025)"}],"fun_headline_variants":["GraphRunner: plan, verify, execute — cuts graph RAG errors and costs","Three-step GraphRunner outperforms Graph-CoT by 10-50% on graph QA","Pre-verification stops LLM hallucinations in graph retrieval: GraphRunner","Multi-hop graph retrieval done right: plan, verify, then execute","GraphRunner: 3-12.9x cheaper, 2.5-7.1x faster than Graph-CoT"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The approach assumes the graph's node and edge types are fully known and that Find_Node's semantic similarity search, with an unreported threshold $\\theta$, reliably locates the intended start nodes; if the schema description is incomplete or the search picks the wrong node, the whole plan is built on the wrong foundation and verification cannot repair it.","fun_headline_variants_meta":{"raw":{"variants":["GraphRunner: plan, verify, execute — cuts graph RAG errors and costs","Three-step GraphRunner outperforms Graph-CoT by 10-50% on graph QA","Pre-verification stops LLM hallucinations in graph retrieval: GraphRunner","Multi-hop graph retrieval done right: plan, verify, then execute","GraphRunner: 3-12.9x cheaper, 2.5-7.1x faster than Graph-CoT"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001456,"raw_usage":{"total_tokens":5901,"prompt_tokens":1029,"completion_tokens":4872,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":645,"completion_tokens_details":{"reasoning_tokens":4759}},"tokens_in":645,"tokens_out":4872,"duration_ms":38682,"temperature":1.0,"reasoning_tokens":4759,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T18:08:09.030853+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run GraphRunner on GRBENCH with an open-source LLM replacing GPT-4 and compare the GPT4Score gap to Graph-CoT; if the 10-50% advantage disappears, the three-stage design's reported benefit depends on the planner's reasoning strength, not on verification alone.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the token-pricing formula used to compute the reported inference cost reductions."}],"review_version":1}