acceptodds
Under review as a conference paper at ICLR 2027

AoG: Uncertainty-Guided Adaptive Reasoning Agent on Knowledge Graphs

Abstract

The strong reasoning capabilities of large language models (LLMs) enable LLM-based agents to solve complex reasoning tasks through interactions with external tools and knowledge base. These interactions incur token and latency costs, but their benefits vary across decisions. In knowledge graph reasoning under a limited action budget, uniform exploration effort can waste actions on clear relation choices while leaving ambiguous ones insufficiently inspected. Reusing exploration feedback poses another challenge: agents must avoid repeating failed actions without excluding those that may be valid in a different context. To address these challenges, we introduce AoG, a training-free reasoning agent over knowledge graphs that couples on-demand evidence acquisition with context-specific failure reuse. It uses uncertainty to switch relation exploration policy and bounded graph inspection. Verified local failures are retained across retries as action-conditioned memory, which excludes candidate actions only when the recorded context matches and the supporting evidence remains applicable. Evaluation across three KGQA benchmarks shows that AoG achieves a favorable balance of answer quality and inference cost when compared with training-free agents under same action budgets.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Adaptive Reasoning, LLM-based Agent, KGQA

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_F6HkOpenReview ↗
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
  1. The "uncertainty" in equation (7) is computed from independent LLM relevance weights normalised into a distribution and from a temperature-0.1 (τ\tau) 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 ρt\rho_t actually predicts error, for example by reporting the accuracy of Policy 1 decisions as a function of rho_t or the AUROC of ρt\rho_t for wrong top-1 relations.

  2. All training-free baselines are forced into AoG's action-accounting scheme with Tmax=15T_{\text{max}} = 15, 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 γ0\gamma_0, wHw_H, and KK, are they selected by the results on the test sets? -- It is said in Section 5.4 that "γ0=0.35\gamma_0 = 0.35 because it "gives the highest F1".

3 comments
AuthorsOpenReview ↗

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.

BackboneDatasetρ AUROCH AUROCJ AUROC
gpt-5.6-lunaCWQ0.699 ± 0.0210.655 ± 0.0280.581 ± 0.022
gpt-5.6-lunaWebQSP0.762 ± 0.0130.717 ± 0.0180.562 ± 0.016
gpt-5.6-lunaGrailQA0.833 ± 0.0230.774 ± 0.0440.650 ± 0.044
deepseek-v4-flashCWQ0.629 ± 0.0290.638 ± 0.0360.572 ± 0.045
deepseek-v4-flashWebQSP0.724 ± 0.0570.687 ± 0.0890.548 ± 0.050
deepseek-v4-flashGrailQA0.805 ± 0.0140.755 ± 0.0500.644 ± 0.056

ρ 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.

AuthorsOpenReview ↗

First Response to Reviewer F6Hk (Continuing)

Table R5. Answer quality and cost under the reported action budget protocol on CWQ.

Action BudgetMethodHits@1 (%)Macro F1 (%)Budget stops (%)k Tokens/questionSeconds/question
10AoG78.94±1.1268.11±0.8520.62±0.445.20±0.7329.42±1.53
10DoG59.63±1.3447.93±0.6839.21±1.0510.26±1.3858.67±2.92
10SoG69.92±0.5662.82±1.1128.47±0.7937.45±0.6439.02±2.18
10VoG75.24±0.9264.26±0.7323.86±0.518.05±0.89108.91±3.74
15AoG80.42±0.2970.96±0.5215.38±0.2312.14±0.3337.19±1.46
15DoG71.63±1.4859.47±0.9127.73±1.2211.95±1.5563.35±1.67
15SoG78.92±0.7371.15±1.1617.15±0.3539.53±1.4241.63±1.81
15VoG75.24±1.0864.26±1.3722.68±0.669.73±0.41123.24±2.85
20AoG82.87±1.5272.33±0.8912.29±0.4714.76±1.2859.15±1.72
20DoG78.26±0.8165.68±1.2421.57±0.9317.00±2.7269.96±2.49
20SoG81.58±1.6773.43±0.5415.46±0.3842.61±0.9546.70±2.82
20VoG75.24±1.1964.26±0.8819.34±0.7610.75±1.49138.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 configurationBudget stops (%)Budget stops in the first relation query, before a routing decision (%)Hits@1 (%)Macro F1 (%)
Lookahead and automatic expansion on12.31 ± 1.062.24 ± 3.6186.69 ± 1.6577.16 ± 1.89
Lookahead and automatic expansion off10.27 ± 0.650.29 ± 0.2387.73 ± 2.0880.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.

AuthorsOpenReview ↗

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.

Reviewer_9A7ZOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

This paper proposes AOG, a training-free agent for knowledge-graph question answering under a limited action budget. AOG first decomposes a question into subgoals with explicit execution requirements. At each relation-selection step, it combines the entropy of an LLM ranker with the disagreement between the LLM and a local embedding ranker to estimate uncertainty. Low-uncertainty decisions use a fast top-1 policy, whereas high-uncertainty decisions trigger bounded graph inspection and reciprocal-rank fusion. AOG also stores tool-verified failures as action-conditioned memory and excludes previously failed actions only when the subgoal, execution prefix, inputs, and requirements still match. Experiments on CWQ, WebQSP, and GrailQA with two frozen LLM backbones show a favorable trade-off between answer quality, token use, and latency compared with other training-free KG agents.

Critical strengths

The paper addresses a practically important problem: allocating limited exploration resources across KG reasoning decisions with different levels of ambiguity. The combination of uncertainty-guided exploration and context-specific failure reuse is intuitive and well motivated. Failure memory is connected to executable action filtering rather than being retained only as free-form reflection. The paper provides useful sensitivity analyses for the uncertainty threshold, entropy weight, action budget, candidate count, and local embedding ranker.

Critical weaknesses

1.AOG is described as training-free, but it relies on substantial task-specific system engineering, including query decomposition, constraint schemas, graph inspection tools, checkpoint recovery, action serialization, and programmatic validation. Its portability to a new KG or task schema is therefore unclear. 2.The framework is complex and combines several established components—entropy, ranker disagreement, RRF, lookahead, validation, memory, and checkpoint retry—making the methodological novelty of individual components relatively incremental.

Questions for authors

1.What are the realized Policy 2 usage rates for the random-routing ablation? Do they match those of the full AOG after mandatory escalations and retries are included?

2 comments
AuthorsOpenReview ↗

First Response to Reviewer 9A7Z

We thank the reviewer for the feedback and for noting the practical importance of allocating a limited exploration budget in KG reasoning.

W1: We designed AoG to adapt exploration and reuse verified failures during inference with frozen models. This avoids the need to collect supervised reasoning trajectories or train a task-specific controller. A new graph would still require changes to how AoG retrieves entities and relations, and checks the requirements of each step. These changes supply evidence from the new graph, and the same rules can use that evidence to decide when to explore and which actions to exclude (Section 4.2).

Our experiments use the same procedure and shared settings across CWQ, WebQSP, and GrailQA. We selected the settings using Hits@1 and macro F1 on the complete training sets (Section 5.4). These datasets all use Freebase, so they do not establish transfer to another graph. The ablations show that AoG improves answer quality by using verified failures to guide later decisions while keeping the models frozen (Section 5.3).

W2: Entropy, ranker disagreement, and RRF are established tools. AoG contributes a procedure that connects verified failures to exploration decisions (Section 4.2): it excludes an action only when its execution context matches the stored record and the failure remains applicable, then computes uncertainty over the remaining relation candidates. Failure memory thus determines both action admissibility and whether further exploration is needed.

The mechanism controls in Section 5.3 (manuscript Tables 2 and 3) test these design choices. Context-agnostic Exclusion retains concrete actions and inputs but omits the subgoal, prefix, and requirement-applicability checks. Its mean Hits@1 is lower on all three datasets than w/o Failure Exclusion, which retains failure feedback without excluding actions.

Unfiltered Routing retains context-matched action exclusion but computes the routing score and threshold before filtering. Relative to full AoG, mean Hits@1 decreases by 6.09, 6.82, and 10.22 percentage points on CWQ, WebQSP, and GrailQA, respectively, while token use increases on all three datasets.

Q1: The realized Policy 2 usage rates are close on CWQ and WebQSP, with differences below one percentage point after including mandatory escalations and retries. On GrailQA, Random's rate is 4.50 percentage points higher than Guided's (Table R3).

In this supplementary comparison, Random's fixed probability p applies only at the optional routing gate and is calibrated for token cost. The reported usage rates are measured from actual Policy 2 executions divided by all recorded routing decisions. Recorded early returns that do not enter Policy 2 remain in the denominator.

Table R3. Realized Policy 2 usage in the supplementary comparison. Each method is evaluated on 1,000 test questions per dataset using deepseek-v4-flash and BGE-M3. Counts are pooled across three runs per method. Differences are Random minus Guided, in percentage points (pp), computed before rounding.

DatasetRandom pGuided: Policy 2 usage (%)Random: Policy 2 usage (%)Random − Guided (pp)
CWQ0.656961.91%62.58%+0.68
WebQSP0.573845.84%45.74%−0.11
GrailQA0.493450.50%55.00%+4.50
AuthorsOpenReview ↗

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.

Reviewer_HMaxOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

AoG is a training-free knowledge-graph question-answering agent that combines adaptive relation exploration with context-conditioned failure memory. An LLM planner produces executable subgoals; entropy of relation scores and disagreement with a local embedding ranker determine whether to take a fast step or perform additional structural inspection. Verified failures exclude actions only when their execution context and applicable requirements match. Evaluation covers CWQ, WebQSP, and a GrailQA development subset with two frozen LLM backbones, shared action accounting for training-free agents, and ablations of routing and memory. The results indicate a useful answer-quality/inference-cost trade-off.

Critical strengths
  1. The treatment of failure memory is careful. Appendices A.5–A.6 distinguish a disproved requirement from insufficient evidence and retain the action inputs and requirements when reusing a failure. This matters: an overly broad exclusion rule can remove a valid path, as the context-agnostic control illustrates.

  2. The cost-quality trade-off is the strongest empirical result. With the GPT backbone, CWQ Hits@1 increases from 78.92 for SoG to 80.42 while token use drops from 42.250k to 12.140k (Table 1). GrailQA also improves in both Hits@1 and F1. The factorial and memory controls provide useful evidence beyond the main benchmark comparison.

Critical weaknesses
  1. The evaluation protocol leaves two important details unresolved. Appendix A.8 uses 5,609 of the 6,763 GrailQA development questions without explaining the inclusion rule there. Section 5.4 identifies a best-performing default threshold, but does not clearly state which data were used to choose it. These details should be specified before interpreting the reported margins, particularly the 0.11-point WebQSP advantage over SoG. I do not infer leakage from the omission, but the selection procedure needs to be reproducible.

  2. The random-routing ablation is not a matched-resource comparison. Appendix C.2 derives its probabilities from historical Policy-2 rates, including a CWQ configuration with w_H=0.75 rather than the final default of 0.50. As the appendix notes, realized escalation rates and costs can differ. The ablation therefore supports the complete routing design, but does not cleanly establish that uncertainty is a better way to allocate a fixed inspection budget. A random gate calibrated under the final configuration would be a more useful control.

Questions for authors
  1. How were the 5,609 GrailQA questions selected, and what data were used to choose the default hyperparameters? Please identify the frozen question sets and configurations used in the main results and ablations.

  2. Does the routing advantage hold against a random gate calibrated under the final configuration to match realized escalation or inference cost? If existing logs permit this comparison, it would address the main ambiguity in the ablation.

  3. Can the small main-table differences be accompanied by question-paired uncertainty, in addition to variation across API runs? I would not interpret the 0.11-point WebQSP margin as an established accuracy advantage without this.

2 comments
AuthorsOpenReview ↗

First Response to Reviewer HMax

We thank the reviewer for the feedback and for noting the practical importance of allocating a limited exploration budget in KG reasoning.

W1: We designed AoG to adapt exploration and reuse verified failures during inference with frozen models. This avoids the need to collect supervised reasoning trajectories or train a task-specific controller. A new graph would still require changes to how AoG retrieves entities and relations, and checks the requirements of each step. With these adaptations, the same rules use evidence from the new graph to decide when to explore and which actions to exclude (Section 4.2).

Our experiments use the same procedure and shared settings across CWQ, WebQSP, and GrailQA. We selected the settings using Hits@1 and macro F1 on the complete training sets (Section 5.4). These datasets all use Freebase, so they do not establish transfer to another graph. The ablations show that AoG improves answer quality by using verified failures to guide later decisions while keeping the models frozen (Section 5.3).

W2: Entropy, ranker disagreement, and RRF are established tools. AoG contributes a procedure that connects verified failures to exploration decisions (Section 4.2). It excludes an action only when the current execution context matches the stored record and the failure still applies. It then computes uncertainty over the remaining relation candidates. Failure memory thus determines both which actions remain available and whether further exploration is needed.

The mechanism controls in Section 5.3 (manuscript Tables 2 and 3) test these design choices. Context-agnostic Exclusion retains concrete actions and inputs but ignores the subgoal, execution prefix, and whether the recorded requirements still apply. Its mean Hits@1 is lower on all three datasets than w/o Failure Exclusion, which keeps failure feedback but leaves actions available. Thus, excluding actions without checking their context can be worse than leaving them available.

Unfiltered Routing retains context-matched action exclusion but computes the routing score and threshold before filtering. Relative to full AoG, mean Hits@1 decreases by 6.09, 6.82, and 10.22 percentage points on CWQ, WebQSP, and GrailQA, respectively, while token use increases on all three datasets.

Q1: The realized Policy 2 usage rates are close on CWQ and WebQSP, with differences below one percentage point after including mandatory escalations and retries. On GrailQA, Random's rate is 4.50 percentage points higher than Guided's (Table R3).

In this supplementary comparison, Random's fixed probability p applies only at the optional routing gate and is calibrated for token cost. The reported usage rates are measured from actual Policy 2 executions divided by all recorded routing decisions. Recorded early returns that do not enter Policy 2 remain in the denominator.

Table R3. Realized Policy 2 usage in the supplementary comparison. Each method is evaluated on 1,000 test questions per dataset using deepseek-v4-flash and BGE-M3. Counts are pooled across three runs per method. Differences are Random minus Guided, in percentage points (pp), computed before rounding.

DatasetRandom pGuided: Policy 2 usage (%)Random: Policy 2 usage (%)Random − Guided (pp)
CWQ0.656961.91%62.58%+0.68
WebQSP0.573845.84%45.74%−0.11
GrailQA0.493450.50%55.00%+4.50
AuthorsOpenReview ↗

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.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.