- Rating
- 2
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper considers the task of KGQA under limited action-budget, especially by reusing the failure information from the previous action steps. AoG first decomposes a question into subgoals with executable requirements. For each subgoal, it performs several memory-based execution steps with relation filtering. Failures verified by tool-based checks are stored under keys of subgoal, execution prefix and action, and the action is excluded when that context recurs.
Critical strengths
The paper seems well-written, and the evaluation (e.g., Table 1) is extensive with multiple baselines and SOTA LLMs.
Critical weaknesses
-
The "uncertainty" in equation (7) is computed from independent LLM relevance weights normalised into a distribution and from a temperature-0.1 () softmax over cosine similarities, so it is a heuristic disagreement score rather than a calibrated uncertainty, and the threshold in equation (8) is ad hoc. The authors should show that actually predicts error, for example by reporting the accuracy of Policy 1 decisions as a function of rho_t or the AUROC of for wrong top-1 relations.
-
All training-free baselines are forced into AoG's action-accounting scheme with , which may affect the performance of other methods designed for different budgets (e.g., multi-agent debate in DoG), and only AoG receives a budget sweep (Table 9). This seems unfair to the baselines. Besides, the paper does not report how often AoG runs out the budget, given that Policy 2 probing can consume much of a 15-action budget.
Questions for authors
For the hyperparameters , , and , are they selected by the results on the test sets? -- It is said in Section 5.4 that " because it "gives the highest F1".
3 comments
First Response to Reviewer F6Hk (Continuing)
Table R5. Answer quality and cost under the reported action budget protocol on CWQ.
| Action Budget | Method | Hits@1 (%) | Macro F1 (%) | Budget stops (%) | k Tokens/question | Seconds/question |
|---|---|---|---|---|---|---|
| 10 | AoG | 78.94±1.12 | 68.11±0.85 | 20.62±0.44 | 5.20±0.73 | 29.42±1.53 |
| 10 | DoG | 59.63±1.34 | 47.93±0.68 | 39.21±1.05 | 10.26±1.38 | 58.67±2.92 |
| 10 | SoG | 69.92±0.56 | 62.82±1.11 | 28.47±0.79 | 37.45±0.64 | 39.02±2.18 |
| 10 | VoG | 75.24±0.92 | 64.26±0.73 | 23.86±0.51 | 8.05±0.89 | 108.91±3.74 |
| 15 | AoG | 80.42±0.29 | 70.96±0.52 | 15.38±0.23 | 12.14±0.33 | 37.19±1.46 |
| 15 | DoG | 71.63±1.48 | 59.47±0.91 | 27.73±1.22 | 11.95±1.55 | 63.35±1.67 |
| 15 | SoG | 78.92±0.73 | 71.15±1.16 | 17.15±0.35 | 39.53±1.42 | 41.63±1.81 |
| 15 | VoG | 75.24±1.08 | 64.26±1.37 | 22.68±0.66 | 9.73±0.41 | 123.24±2.85 |
| 20 | AoG | 82.87±1.52 | 72.33±0.89 | 12.29±0.47 | 14.76±1.28 | 59.15±1.72 |
| 20 | DoG | 78.26±0.81 | 65.68±1.24 | 21.57±0.93 | 17.00±2.72 | 69.96±2.49 |
| 20 | SoG | 81.58±1.67 | 73.43±0.54 | 15.46±0.38 | 42.61±0.95 | 46.70±2.82 |
| 20 | VoG | 75.24±1.19 | 64.26±0.88 | 19.34±0.76 | 10.75±1.49 | 138.64±3.45 |
W2 (b): Policy 2 probing shares the action budget of 15 with the rest of execution (Appendices A.1 and A.7). We do not reserve actions for the final steps. We count a budget stop only if the system exhausts the action budget and still needs another call to answer the question. In that case, it returns an empty answer. The denominator is all question-runs.
The supplementary WebQSP comparison in Table R6 reports fewer budget stops with lookahead and automatic expansion disabled.
Table R6. Effect of lookahead and automatic expansion on WebQSP.
| Guided configuration | Budget stops (%) | Budget stops in the first relation query, before a routing decision (%) | Hits@1 (%) | Macro F1 (%) |
|---|---|---|---|---|
| Lookahead and automatic expansion on | 12.31 ± 1.06 | 2.24 ± 3.61 | 86.69 ± 1.65 | 77.16 ± 1.89 |
| Lookahead and automatic expansion off | 10.27 ± 0.65 | 0.29 ± 0.23 | 87.73 ± 2.08 | 80.05 ± 1.54 |
The comparison changes both settings together, so it does not isolate their individual effects. The reported rates apply to this comparison; they are not budget-stop rates for the runs in manuscript Table 1.
Q1: We selected the hyperparameters using Hits@1 and macro F1 on the complete training sets and froze them before final evaluation. Section 5.4 reports the sensitivity sweep, and we did not use its evaluation results to select the defaults.
Follow-up on Our Response
Dear Reviewer,
Thank you again for your thoughtful review. We would like to follow up on our response. As the discussion period is nearing its end, we would appreciate your feedback on whether our response addresses your main concerns and whether any points need further clarification.
We would be happy to discuss any remaining questions. Thank you for your time and consideration.
First Response to Reviewer F6Hk
We thank the reviewer for the feedback and for recognizing the clarity of the presentation and the breadth of the evaluation.
W1: On replayed annotated prefixes, the mean AUROC of ρ exceeds 0.5, the random-ranking benchmark, in all six settings. We labeled a Policy 1 top-1 choice as a mismatch when it differed from the verified annotated next relation. These results support using ρ to distinguish matches from mismatches in the replayed states. A mismatch can still correspond to an alternative valid reasoning path. The results do not establish calibrated error probabilities or show that ρ predicts errors during online execution or in final answers.
Table R4 reports mean ± sample standard deviation over three runs per setting. We include normalized entropy (H) and ranker disagreement (J) for reference.
Table R4. AUROC of ρ, H, and J across three runs.
ρ has the highest mean AUROC in five of the six settings. H has the highest mean in the remaining setting.
Routing threshold (Section 5.4). The training-selected default γ₀ = 0.35 gave the highest F1 among the thresholds tested on all three datasets. On WebQSP, lowering γ₀ to 0.20 saved 24.7% of tokens and reduced F1 by 0.13 percentage points.
W2 (a): Our independent baseline implementations retain the methods' core workflows: 1) iterative LLM-directed search in SoG, 2) relation filtering, answer attempts, 3) three-role debate in DoG, 4) and planning, verification, and UCB-guided plan revision in VoG. Each method's iteration and debate limits remain additional stopping conditions within the imposed per-question action budget.
For these baseline implementations, each actual LLM or SPARQL request counts as one action, including requests within debate, verification, and retrieval, as well as request retries. Thus, each of DoG's three debate roles incurs its own LLM call. Wrappers add no extra actions beyond their underlying requests, and local formatting, ranking, and memory operations consume no actions.
Table R5 compares AoG, SoG, DoG, and VoG on CWQ under action budgets of 10, 15, and 20. AoG has the highest Hits@1 under all three budgets. For macro F1, AoG leads at 10 and SoG leads at 15 and 20. These comparisons cover the tested action budgets and do not establish each baseline's best performance under its original resource settings. Equal action budgets do not ensure equal computational cost, so we also report tokens and latency.