{"id":"17c26f90-2de8-400e-913a-8e0780214d4a","arxiv_id":"2505.12476","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"RTSoG combines question decomposition, LLM-reward-guided Monte Carlo Tree Search with a self-critic stop signal, and weighted path stacking to achieve new state-of-the-art KGQA accuracy, though without code or error bars.","lead":"A training-free framework that uses Monte Carlo Tree Search guided by an LLM's own reward and self-critic signals to retrieve knowledge-graph paths and answer questions. It reports state-of-the-art exact-match gains of up to 8.7% on GrailQA and 7.0% on WebQSP, but releases no code and no run-to-run statistics.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Reported SOTA margins are not yet supported: hyperparameters are tuned on the test sets and the GrailQA/WebQuestions subsets are unreleased, so baseline comparability is unverified.","rationale":"The method is coherent and the ablations are consistent with the proposed components being useful, but the paper's headline depends on empirical numbers that cannot currently be checked without code, data, or seeds. The reader's weakest assumption identified the same core issue: the GrailQA/WebQuestions subsets may not match those of the cited baselines, and single-run, nondeterministic evaluations with test-set-tuned hyperparameters do not support strong SOTA claims. My concern is not an allegation of misconduct; it is that the evidence as presented does not rule out test-set selection effects and mismatched evaluation subsets. A CONDITIONAL verdict requiring release of sample identifiers and validation-based tuning is appropriate, so the reader's CONDITIONAL verdict should remain unchanged.","tokens_in":17326,"tokens_out":8494,"duration_ms":80317,"concrete_test":"Release the exact sample identifiers for the GrailQA 1,000-subset and WebQuestions 1,500-subset, then independently rerun PoG w/GPT-4 and ToG w/GPT-4 on those identical subsets with the same prompts and decoding settings, and compare reproduced scores with the cited baselines in Table IV; if baselines shift by more than about 2 EM points, or if RTSoG's score drops by more than about 2 points when hyperparameters are selected on a held-out validation split instead of the test set, the claimed SOTA margins are not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"RTSoG's central claim is empirical: it reports exact-match gains of 5.5-16.4 points over prior methods on four KGQA datasets (Tables III-IV). The most load-bearing weakness is that the evaluation protocol does not establish fair comparability. In Section V-C, hyperparameters (n, H, b, K, alpha) are selected by sweeping on the WebQSP and GrailQA test sets, and the same test sets are then used to produce the final numbers in Tables III and IV. No validation split is used, so reported scores are selected on the test data; the baselines were not given a similar selection step. For GrailQA and WebQuestions, the paper states it uses the same 1,000/1,500 test samples as previous works (Table II footnote), but no sample identifiers are released, making it impossible to verify that the cited ToG/PoG numbers were computed on the same instances. With temperature 0.7 for at least one policy model and no seeds or confidence intervals, single-run EM scores could be lucky draws. There is also a reporting inconsistency: on WebQSP the table's parenthetical gains are relative to EPREM (88.8) while the text claims a 7.0-point gain over PoG (87.3); these differ by 1.5 points. None of this proves the method is wrong, but it means the headline SOTA claim is not yet supported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Reward-guided Tree Search on Graph (RTSoG), a training-free framework for knowledge graph question answering (KGQA). RTSoG decomposes the input question into sub-questions, performs a Self-Critic Monte Carlo Tree Search (SC-MCTS) over the knowledge graph using the same LLM as policy model and value model, selects the top-K weighted reasoning paths, and pushes them through a reasoning-path stack before generating the final answer. The authors report exact-match accuracy on WebQSP, CWQ, GrailQA, and WebQuestions, claiming state-of-the-art results with RTSoG and, for example, 8.7% and 7.0% improvements on GrailQA and WebQSP, respectively.","tokens_in":17603,"tokens_out":5399,"duration_ms":49065,"significance":"If the empirical claims hold, RTSoG would be a strong training-free GraphRAG baseline, showing that MCTS-style exploration/exploitation combined with path weighting and a self-critic mechanism can improve LLM KGQA performance across multiple datasets and policy models. The algorithmic description is reasonably clear, the ablations for the self-critic mechanism and the reasoning-path stack are informative, and the efficiency analysis is a useful addition. However, the central claim is entirely empirical, and the evaluation as presented does not currently support the claimed state-of-the-art margins: no code, data, sample identifiers, seeds, or multiple-run statistics are provided, and hyperparameters are selected on the same test sets used for the final numbers. The paper's strengths are its clear method formulation and the internal ablations, but the missing evaluation infrastructure is a major obstacle to verification.","major_comments":[{"comment":"The GrailQA and WebQuestions results are reported on 1,000- and 1,500-sample subsets that the paper says were 'randomly selected ... as previous works,' but no sample identifiers or release are provided, so there is no way to verify that the cited ToG and PoG numbers were computed on the same questions. Because every headline gain is an absolute EM difference on exactly these subsets, the claimed state-of-the-art margins are unsupported unless the exact sample sets are released and the baselines are rerun on them, or sample IDs are provided for independent verification.","section":"§V-A, Table II and Tables III–IV"},{"comment":"The sensitivity analysis selects n, H, b, and K by sweeping one parameter at a time on the WebQSP and GrailQA test sets, and alpha is fixed after those same experiments; the final Tables III and IV are then produced on those same test sets. This is test-set tuning, and the prompting baselines ToG and PoG were not given an equivalent selection step. Please introduce a validation split for hyperparameter selection, or report the results across the full sweep to show that the SOTA margins are not an artifact of choosing the best test-set point.","section":"§V-C, Fig. 2, Tables III–IV"},{"comment":"The evaluation is a single run per configuration under nondeterministic LLM APIs: Qwen2.5-14b is run at temperature 0.7, the OpenAI models are called through APIs with no seeds, and no confidence intervals or multiple-run statistics are reported. EM differences of 5–8 points can easily fall within run-to-run variance of LLM prompting and search. Please report means and standard deviations over at least three runs and a significance test for the main comparisons.","section":"§V-A Implementation Details, Tables III–IV"},{"comment":"The text states that RTSoG with GPT-4 shows 'an increases of 7.0% and 7.8% on WebQSP and CWQ' over PoG with GPT-4, but Table III reports WebQSP 94.3 vs 87.3, a difference of 5.5 points, while the '+7.0' figure appears only in the abstract and conclusion. The comparison basis (PoG vs EPREM vs absolute vs relative) needs to be stated consistently and the table and text reconciled.","section":"§V-B vs Table III"},{"comment":"The same LLM serves as question decomposer, policy model, value model, self-critic, and final answer generator, so the reward signals and EoS signals come from the same system being evaluated. This does not invalidate the method, but it makes the contribution of graph-grounded search to the reported gains unclear; the ablation in Fig 3(b) removes the whole SC-MCTS stage, not the reward model, and the path-stack ablation in Table V keeps the same LLM in both arms. An additional control that uses the same policy LLM with an alternative context-selection method (e.g., PoG or random paths) would more cleanly isolate the benefit of reward-guided search.","section":"§IV-B, §V-D"}],"minor_comments":[{"comment":"The heading 'RELATED WROK' contains a typo and should read 'RELATED WORK'.","section":"§II heading"},{"comment":"Equation (11) is described as a weighted average, but the displayed formula is the average of children's values; please define the initial Q and N for leaf nodes and clarify whether Q(s_i) in Eq. (2) is a cumulative score or an average score.","section":"§IV-B, Eq. (11)"},{"comment":"The condition 'if πθ(S,q,subq,P_rng,m)' should state explicitly what output of the LLM counts as acceptance, since the pseudocode otherwise leaves the behavior of the stack ambiguous.","section":"Algorithm 1, line 24"},{"comment":"Table VI uses the variable 'k' for the tree width, but the paper uses 'b' for width and 'K' for the number of paths; please rename to avoid confusion.","section":"Table VI"},{"comment":"In the paragraph varying the number of iterations H, the text says 'when k is fixed' but H is the parameter being varied; this should be corrected to refer to the actual fixed hyperparameters.","section":"§V-C"},{"comment":"Equation (8) writes EoS(s_j) = πθ(subq, s_j), but the preceding text says the self-critic receives the currently expanded historical reasoning path; the equation should include the reasoning path to match the description.","section":"§IV-B, Eq. (8)"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a timely topic and the method is plausible, but the empirical verification is currently insufficient: no code, no released sample identifiers, no seeds, and test-set hyperparameter selection. I would treat the following as conditions for acceptance: release the exact GrailQA/WebQuestions sample sets or IDs, add a validation-based hyperparameter selection procedure, provide multi-run statistics, and reconcile the WebQSP gain discrepancy between text and table. These are substantive but fixable within the manuscript's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: RTSoG is a sensible synthesis of MCTS, self-critic termination, question decomposition, and weighted path stacking for KGQA. The ablations actually support the components: removing the self-critic costs 7-10 points, removing the search costs 27-52 points, removing the path stack costs 5-7 points. Those are real internal checks, and the idea that a small open-weights model with deliberate search beats a larger closed model is interesting. I believe the method is real.\n\nThe problem is that the headline empirical claim is not yet evidenced. The hyperparameters (n, H, b, K, alpha) are chosen by sweeping on the WebQSP and GrailQA test sets, then the same test sets produce the final tables. Baselines got no such selection step. For GrailQA and WebQuestions the paper says it uses the same 1,000/1,500 samples as prior work, but no sample identifiers are released, so baseline comparability is unverifiable. There are no seeds, no confidence intervals, and at least one policy model runs at temperature 0.7 with a single run reported. The parenthetical percentage gains in the tables are also not clearly defined—on WebQSP the +5.5% is relative to EPREM while the text says 7.0 points over PoG, which are both true but the presentation invites confusion.\n\nNone of this says the method is wrong. The relative internal ordering of the ablations is consistent, and the gains over PoG are plausible for an inference-time search that uses more deliberate exploration. But the paper asks us to take a SOTA claim on faith, and the missing code and data make that hard.\n\nWho is this for? Researchers working on training-free GraphRAG and inference-time search for KGQA will read it with interest, but mainly as a method paper. With code and a proper evaluation protocol it could be a strong contribution. As submitted, I would not cite the numbers, and I would not give it a clean acceptance without requiring the code, seeds, multiple runs, and a validation-based hyperparameter selection—or at least an explicit statement of what was tuned and a sensitivity analysis across seeds.\n\nMy recommendation: send it to peer review, but flag the evaluation protocol as the main blocker. The method deserves a serious referee; the current evidence does not support the headline margins yet.","headline":"A coherent training-free KGQA method with plausible gains, but the SOTA claim rests on unreleased subsets, test-set-tuned hyperparameters, and single-run scores.","tokens_in":18178,"tokens_out":2097,"would_cite":false,"duration_ms":21013,"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":"A training-free tree-search framework is claimed to make LLMs retrieve better reasoning paths from knowledge graphs than prior search strategies.","keywords":["knowledge graph question answering","large language models","graph retrieval-augmented generation","Monte Carlo tree search","self-critic mechanism","question decomposition","reasoning path retrieval","Freebase"],"falsifier":"Run RTSoG and the strongest prior baseline several times on the exact same publicly released test subsets with matched hyperparameters and fixed seeds; if the exact-match margins on WebQSP and GrailQA shrink below about two points or overlap across runs, the claimed state-of-the-art improvement does not hold.","tokens_in":17109,"feed_emoji":"🌳","tokens_out":8431,"duration_ms":79782,"temperature":0.7,"pith_summary":"The paper sets out to show that a training-free, reward-guided tree search over a knowledge graph retrieves better reasoning paths than the beam search, greedy search, or best-of-N planning used by earlier LLM-based KGQA methods. It argues that previous approaches explore new paths without exploiting paths already found, and that complex compositional questions need to be broken into sub-questions before retrieval. Its proposed framework, RTSoG, decomposes each question, runs a self-critic Monte Carlo tree search that scores paths with a reward model, and feeds the highest-weight paths into the LLM in a stack. According to the reported experiments, RTSoG achieves the best exact-match accuracy on WebQSP, ComplexWebQuestions, GrailQA, and WebQuestions with every LLM tested, with gains of roughly 7 to 16 points over the strongest prior method. If those numbers hold, the practical payoff is a way to ground LLM answers in a knowledge graph without any fine-tuning.","feed_headline":"Reward-guided tree search beats prior question-answering methods","feed_subtitle":"On four knowledge-graph benchmarks, exact-match accuracy rises by 7 to 16 points over the previous best.","key_machinery":"The load-bearing mechanism is the Self-Critic Monte Carlo Tree Search (SC-MCTS). Starting from the question's linked topic entity, it repeatedly selects a node by UCT, expands by asking the LLM to filter the entity's adjacent relations and then pick the highest-reward tail entity for each surviving relation, and evaluates the new node with an LLM value model that combines a local relation reward and a global path reward as $Q = \\alpha S^r_{filt} + (1-\\alpha) S^P_{cand}$. The novel step is the self-critic: after each expansion the same LLM is asked whether the accumulated path already answers the question, and an affirmative answer emits an End-of-Search signal that makes the node a leaf. After $H$ iterations the top-$K$ nodes by $Q$ supply weighted reasoning paths, which are sorted descending and passed through a reasoning-path stack; earlier high-weight paths act as historical evidence when judging later ones, and the surviving paths condition the final answer.","core_discovery":"The paper's central discovery, on its own terms, is that a self-critic Monte Carlo tree search guided by an LLM reward model is a better graph-retrieval engine than the search strategies in prior LLM-based GraphRAG systems. In the reported experiments RTSoG reaches exact-match 94.3 on WebQSP, 82.8 on ComplexWebQuestions, 93.4 on GrailQA, and 83.5 on the WebQuestions sample, outperforming the strongest prior method by 7.0, 7.8, 8.7, and 16.4 points respectively, and outperforming it with all four tested policy models. The attribution is specific: question decomposition helps the search focus; the value-model reward combines a local relation filter score with a global path score; the self-critic End-of-Search signal stops expansion at the correct node; and the weighted path stack removes noisy paths before final generation. Ablations reported in the paper attribute 7.4 and 9.8 point losses on WebQSP and CWQ to removing the self-critic, and 5.2 and 7.2 point losses to removing the path stack.","pith_inferences":["Not tested here but directly suggested: the same decomposition-plus-SC-MCTS loop should transfer to other knowledge graphs and to structured sources beyond graphs, since no component in the search is specific to Freebase.","A useful follow-up is to separate how much of the gain comes from the search structure versus the LLM's self-evaluation, by pairing a weak policy model with a strong value model and vice versa; the paper uses one LLM for both roles.","The self-critic signal amounts to an early-stopping rule learned by prompting, so an interesting extension is to make the stop decision trainable or calibrated, especially for low-resource domains where the policy model's self-assessment is unreliable.","Because the headline margins depend on a single run over test subsets, a variance-controlled replication across repeated API calls would reveal whether the 7-16 point leads are stable enough for deployment decisions."],"forward_implications":["A training-free LLM pipeline can outperform fine-tuned semantic parsers on GrailQA and WebQuestions, not just other prompting methods, when retrieval is guided by a reward-modeled tree search.","Question decomposition before graph search is a large contributor: removing it drops performance substantially on both WebQSP and GrailQA in the paper's sensitivity analysis.","The self-critic stop signal is a core component: replacing SC-MCTS with plain MCTS loses 7.4 EM points on WebQSP and 9.8 on CWQ in the reported ablations.","Weighted use of retrieved paths matters: the reasoning-path stack adds 5.2 points on WebQSP and 7.2 on GrailQA over feeding the paths in without the stack.","Retrieval quality can compensate for model scale: RTSoG with a smaller open LLM matches or exceeds larger closed LLMs used with earlier retrieval strategies."],"supporting_citations":[{"why":"Supplies the strongest prior baseline (Plan-on-Graph) and the best-of-N planning strategy that RTSoG is compared against and outperforms on all four datasets.","marker":"[12]"},{"why":"Supplies the beam-search baseline (Think-on-Graph) and the shared protocol of using 1,000/1,500 test samples for GrailQA and WebQuestions.","marker":"[13]"},{"why":"Supplies the greedy tree-of-traversals baseline, representative of exploration without the exploitation mechanism RTSoG adds.","marker":"[10]"},{"why":"Supplies the GrailQA dataset and its I.I.D., compositional, and zero-shot splits used for the detailed accuracy comparison.","marker":"[47]"},{"why":"Supplies the WebQuestions dataset from which the 1,500-sample test subset is drawn.","marker":"[48]"},{"why":"Supplies the ComplexWebQuestions dataset used to test complex compositional questions.","marker":"[45]"},{"why":"Supplies the WebQSP dataset used for the main WebQSP comparison.","marker":"[46]"},{"why":"Supplies Freebase, the knowledge graph on which all four datasets and RTSoG's graph queries rely.","marker":"[1]"},{"why":"Supplies the UCT formula used for node selection in SC-MCTS.","marker":"[40]"},{"why":"Supplies the idea of using an LLM as a step-wise verifier, the basis for the value model's reward scoring.","marker":"[44]"}],"fun_headline_variants":["Self-critic tree search lifts KGQA accuracy by up to 16 points","Training-free reward-guided search improves knowledge graph QA","RTSoG: Monte Carlo tree search with self-critic for better KGQA","Question decomposition plus tree search sharpens LLM QA","Reward-guided tree search outdoes prior GraphRAG methods"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The reported margins rest on the assumption that the 1,000- and 1,500-question test subsets are the same slices used by the cited baselines and that one roll of the nondeterministic model API is a fair comparison.","fun_headline_variants_meta":{"raw":{"variants":["Self-critic tree search lifts KGQA accuracy by up to 16 points","Training-free reward-guided search improves knowledge graph QA","RTSoG: Monte Carlo tree search with self-critic for better KGQA","Question decomposition plus tree search sharpens LLM QA","Reward-guided tree search outdoes prior GraphRAG methods"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000254,"raw_usage":{"total_tokens":1623,"prompt_tokens":1056,"completion_tokens":567,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":672,"completion_tokens_details":{"reasoning_tokens":479}},"tokens_in":672,"tokens_out":567,"duration_ms":5581,"temperature":1.0,"reasoning_tokens":479,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:32:41.519725+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run RTSoG and the strongest prior baseline several times on the exact same publicly released test subsets with matched hyperparameters and fixed seeds; if the exact-match margins on WebQSP and GrailQA shrink below about two points or overlap across runs, the claimed state-of-the-art improvement does not hold.","supporting_citations":[{"cited_title":"The value of semantic parse labeling for knowledge base question answer- ing,","cited_arxiv_id":null,"evidence_quote":"Supplies the WebQSP dataset used for the main WebQSP comparison."}],"review_version":1}