CLAUSE: Agentic Neuro-Symbolic Knowledge Graph Reasoning via Dynamic Learnable Context Engineering
Authors: Yang Zhao
Chengxiao Dai
Wei Zhuo
Yue Xiu
Dusit Niyato
Venue: ICLR 2026 Poster (2026)
Keywords: Multi-hop KGQA
Neuro-symbolic reasoning
Agentic system
Context engineering
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)

Abstract: Knowledge graphs provide structured context for multi‑hop question answering, but deployed systems must balance answer accuracy with strict latency and cost targets while preserving provenance. Static $k$‑hop expansions and ``think‑longer'' prompting often over‑retrieve, inflate context, and yield unpredictable runtime. Thus, we introduce CLAUSE, an agentic three-agent neuro‑symbolic framework that treats context construction as a sequential decision process over knowledge graphs, deciding what to expand, which paths to follow or backtrack, what evidence to keep and when to stop. Latency (interaction steps) and prompt cost (selected tokens) are exposed as user‑specified budgets or prices, allowing per‑query adaptation to trade‑offs among accuracy, latency, and cost without retraining. CLAUSE employs the proposed Lagrangian‑Constrained Multi‑Agent Proximal Policy Optimization (LC‑MAPPO) algorithm to coordinate three agents: Subgraph Architect, Path Navigator, and Context Curator, so that subgraph construction, reasoning paths discovery, and evidence selection are jointly optimized under per‑query's resource budgets on edge edits, interaction steps, and selected tokens. Across HotpotQA, MetaQA, and FactKG, CLAUSE yields higher EM@1 while reducing subgraph growth and end-to-end latency at equal or lower token budgets. On MetaQA-2-hop, relative to the strongest RAG baseline (GraphRAG), CLAUSE achieves $+39.3$ EM@1 with 18.6% lower latency, and 40.9% lower edge growth. The resulting contexts are compact, provenance‑preserving, and deliver predictable performance under deployment constraints.

Published as a conference paper at ICLR 2026
CLAUSE: AGENTIC NEURO-SYMBOLIC KNOWLEDGE GRAPH REASONING VIA DYNAMIC LEARNABLE CON- TEXT ENGINEERING
Yang Zhao'; Chengxiao Dai²; Wei Zhuo', Yue Xiu', Dusit Niyato
2 "ndependent Rescarcher.
2 School of Computer Science, The University of Sydney, Australia.
Coolleee of Computing Data Science, Nanyang Technological University, Singapore.
ABSTRACT
Knowledge graphs provide structured context for multi-hop question answering, but deployed systems must balance answer accuracy with strict latency and cost targets while preserving provenance. Static k-hop expansions and "think-longer" prompting often over-retrieve, inflate context, and yield unpredictable runtime. Thus, we introduce CLAUSE, an agentic three-agent neuro-symbolic framework that treats context construction as a sequential decision process over knowledge graphs, deciding what expand, which paths to follow or backtrack, what evidence to keep and when to stop. Latency (interaction steps) and prompt cost (selected tokens) are exposed as user-specified budgets or prices, allowing per-query adapta- tion to trade-off's among accuracy, latency, and cost without retraining. CLAUSE employs the proposed mization (LC-MAPPO) algorithm to coordinate three agents: Subgraph Architect, Path Navigator, and Context Curator, so that subgraph construction, reasoning path discovery, and evidence selection are jointly optimized under per-query resource budgets on edge edits, interaction steps, and selected tokens. Across HotpotQA, MetaQA, and FactKG, CLAUSE yields higher EM @ I while reducing subgraph growth and end-to-end latency at equal or lower token budgets. On MetaQA-2-hop. relative to the strongest RAG baseline (GraphRAG), CLAUSE achieves +339.3 EM@1 1 with 18.6% lower latency, and 40.9% lower edge growth. The resulting contexts are compact, provenance-preservie and deliver predictable performance under deployment constraints.
-onanniiinnnnntrinneeee Multi Aulti-Agent Proximal Policy Opti-
INTRODUCTION
Large language models (LLMs) benefit from external structure for knowledge graph question answer-
ing (KGQA) that require multi-hop reasoning and provenance (Lewis al. 2020 Yang al. 2018
Pan et al., 2023). Knowledge graphs (KGs) are natural substrate: they expose typed entities and relations, support symbolic traversals, and yield auditable context trails (Yasunaga al., 2021 Das
et al. 2018). 8). A common design is to build a query mased local neighborhood in the KG, and then condition a reader language model to produce the answer (Sun et al., 2019 Ding et al., 2024).
How the graph context is assembled often misaligns with both answer quality and runtime constraints. Fixed k--hop expansions serialize many triples, inflating token mass and latency (Zhou et al.. 2024]
Wan et al. 2024) and introducing distractors that depress accuracy (Jiang & Bansal] (019). Extending
chain-of thouugg (Wei et al. 2022 Kojima et al. (022) lengthens per-step reasoning without changing
which evidence is visible and offers little control over end-to-end latency (Zhou al. (0224). In
practice, systems are constrained not only by prompt length but also by the number of interaction steps, how often edit, traverse, and curate, yet most pipelines expose only heuristic knobs (hop
depth, degree caps, top-k).
Our view is to make context construction itself the learning problem: decide which edges add or delete, which paths to pursue or backtrack, which snippets to keep, and when to stop, all under explicit
"qqual contribution. Corresponding author: Yang Zhao (a 8004 98e. attu.edu...

---

Published as a conference paper at ICLR 2026
caps prices interaction steps and selected tokens. This replaces brittle k-hop heuristics with learned, budget-aware controller and makes accuracy-lateney-oo cost trade-offs explicit and tunable. We then propose CLAUSE, agentic neuro-symbolic framework with three Ssents-Subgraaht Architect, Path Navigator, and Context Curator. Decisions unfold sequentially on a symbolic state (nodes, edges, paths) through discrete, auditable actions (edit, traverse, curate), while compact neural scorers prioritize entities, relations, and neighborhoods. In this design, step and token usage enter the training objective directly, so stopping rules and exploration depth are learned rather than hard-coded.
Specifically, three cooperative agents operate on the KG: Subgraph Architect constructs a question-anchored anchored subgraph that preserves suspor-uuppoiing paths while avoiding over-expansion; the Path Navigator discovers and revises reasoning paths while respecting a step budget; and Context Curator assembles a minimal set of textualized snippets sufficient for accurate responses from L.LSs under token budget. We coordinate three agents with LC-MAPPO I aggrangian-constrinned centralized training with decentralized execution (CTDE) variant of PPO that uses a centralized critic and Lagrangian dual variables to learn decentralized policies, which maximize task reward while enforcing per-query budgets on edge edits, interaction steps, and selected tokens (Foerster et al. 2018 Rashid et al. 2020; Schulman al., [017] 7| Yu et al., 2022 Achiam et al., 2017] SSookke et al., 2020 During inference, a single checkpoint runs under hard budgets (caps) or fixed prices (soft trade-offs), adapting per query without retraining.
Empirically, the CLAUSE framework produces compact, targeted contexts and predictable runtime. In HotpotQA, MetaQA, and FactKG, it reduces edge counts and end-to-end latency while improving exact match at the matched token mass, as shown in Section S -aturacy-latency-cos Pareto frontiers: shifting budget from per-step reasoning to interaction im- proves accuracy at fixed tokens, and tightening the step budget reduces latency with little or no loss in accuracy.
Requirement sweeps reveal clear
Contributions. (1) Formulation. We cast multi-hop KGQA as requirements-conniioonn context assembly with per-query budgets/prices on three deployment-relevan resources: (i) subgraph edits, (ii) interaction steps (latency proxy), and (iii) selected tokens (prompt cost). This makes accuracy- efficiency trade-offs explicit and tunable.
(2) Framework. CLAUSE is agentic neuro-symbolic controller that jointly decides what to edit, which paths to follow or backtrack, what textual evidence to keep, and when to STOP. Actions symbolic (auditable) and priorities come from lightweight neural scorers, yielding compact, provenance-preste preserving context.
(3) Training. We adapt constrained RI. to this setting via LC-MAPPO: centralized training with decentralized execution, a multi-head critic that separates task value from edge/step/token costs, and per-budget dual variables that enforce episode-level requirements or enable price-based trade-offs at test time.
(4) Evidence. In HotpotQA, MetaQA, and FactKG, CLAUSE achieves higher or matched EM at equal or lower budgets, with reduced subgraph growth and latency. Ablations show that removing any agent or constraint handling degrades accuracy and/or efficiency, supporting the need for joint control and explicit budgets.
2 PRELIMINARIES AND RELATED WORK
2.1 PRELIMINARIES
Neuro-symbolic definition. We view neuro-symbolic inference as coupling an explicit symbolic calculus (Boolean, first-order, or soft/fuzzy) with a learned scoring/belief module; differentiable logic is unnecessary -only principled linkage between symbols and learned scores is required (Smet) & Raedt 2025). KGQA as neuro-symbolic. KGQA operates on typed entity-relation graphs and commonly targets (i) single-relation queries, (ii) multi-hop path queries, and (iii) compositional-logit queries (e.g..
(Zhang et al. 2021). Surveys group approaches into (1) logic-informed embeddings, (2) embeddings trained with logical constraints, and (3) rule/path learning where a neural controller searches over symbolic paths/rules (DeLong et al. 2025). We adopt (3): dynamic learnable agentic framework edits KG for reasoning.
2

---

Published as a conference paper at ICLR 2026
2.2 RELATED WORK
Existing Multi-hop KGQA Solutions. Multi-hop KGQA must balance accuracy and provenance with strict constraints on lateney and prompt cost. In practice, two resources dominate deployment behavior: the number of interaction steps taken while assembling context and the selected tokens ultimately shown to the reader LLM. Static k-hop expansions often over-retrieve, inflate prompts,
and surface distractors (Zhou et al. 2024 [Wan et al.) 2024; Jiang & Bansal 2019). while typi- cal pipelines expose only heuristic knobs rather than learned, per-query control. A long line of symbolichherro-smmooli KGQA operates directly on entity-relation structure. Path-following and rule-learning systems (e.g., MINERVA, NeuralLP, TensorLog, RNNLogic) traverse the graph to Qu et al. 20 graph-aware readers
derive answers (Das et al. 2018 Yang et al. [017e|Cohen] (e.g., QAGNN) inject KG signals into the encoder (Yasunaga et al. (002]. Question-conditions sub- graph builders such GraftNet and PullNet assemble local neighborhoods for downstream reader (Sun et al. 2019). These approaches typically set expansion depth/degree and filtering thresholds a priori, which makes runtime behavior sensitive to manual tuning and obscures the accuracy accuracy-efficiene efficiency trade-off. Then, work on context engineering shows that prompt composition strongly affects both Wan et al. 2024). Chain-of-thouug prompting can help certain 2022 Han et al. 2025). yet it primarily lengthens the reasoning text without changing which evidence is visible, offering limited leverage over end-to-end latency (Zhou et al. 2024). Moreover, Retrieval-augmenter generation (RAG) conditions generation on external evidence (Lewis et al.) 22200 Karpukhin et al. [0200] Izacard et al., 2023). Recent variants interleave reasoning and retrieval (ReAct) ( Yao et 2003)), incorporate self bef-beee (SELF- RAG)
cost and accuracy (Zhou al. 2024
tasks (Wei et al.) 2022] Kojima et al.
(Asai al. 2024), or adapt retrieval frequency to diffcuuly/confidencee (Jeong et al. 2024 Zhang
et al.] 2022). Graph-guided pipelines (e.g.. GraphR AG; Think-on -rr-p 2.0) leverage entity-relation
structure for multi-hop collection (Edge et al., [025 Ma et al. 2025). These systems often rely on fixed hop limits hand-tuned schedules; optimization of construction, traversal, and selection is rarely carried out jointly under explicit step/token costs. Finally, agentic LLMs plan, call tools, and decide when to act versus reflect (Press et al. 2023 Yao et al. 2023 Shhnn et al. [2023] Schick et al.,
2023 Shen et al., 2023 Liu et al. 2024 Wang et al. 2023). ). Their flexibility comes with multi-step
deliberation that raise interaction cost, and per-episode resource control is implicit.
MARL and constrained optimization. Multi-agent reinforcement learning (MARL) addresses decentralized coordination under partial observability and non-stationarity, where multiple local-view actors must produce joint behavior that optimizes a global objective subject to deployment con- straints (e.g., latency, token budget, graph edits). A widely used recipe centralized training with decentralized execution (CTDE), which stabilizes learning and credit assignment via centralized value while keeping actors decentralized at test time; representative instances include COMA, which introduces a counterfactual baseline for per-agent credit, and QMIX, which learns monotonic mixing network to factorize joint values into per-agent utilities (Foerster et al.) 2018; Rashid et al., 2020). Building PPO (Schulman et al., 2017). MAPPO shows that PPO-style updates with centralized critic are strong, simple baselines on standard cooperative benchmarks (Yu et al.) 2022). Existing methods largely fall into two families: value factorization (e.g., QMIX), which is efficient and scalable but restricted by the monotonic mixing constraint and can misattribute credit when joint action values but aigher-variance/sampll hungry and, in vanilla form, lacks principled mechanisms to enforce Policy per-episode resource constraints. Single-penalty constrained RL such as Reward-Constraiig Optimization (RCPO) TTssler et al. 2019) further conflates heterogeneous costs, making it difficult independently control edge growth, interaction steps, and selected tokens. Preference-oppimizatio methods (GRPÓ/DPO) instead learn from static pairwise/grouu group preferences over complete responses in bandit-like text-only settings without explicit environment state transitions (Rafailov et al.) [023) Shao et al. 2024); they neither decompose multi-agent credit nor estimate shaped values graph states, and they provide no handle for enforcing per-episode constraints.
monotonic; and policy-gradient CTDE (e.g., COMA/MAPPO) which is flexible
Positioning. In summary, we situate CLAUSE among four families: (i) question-condditonell subgraph builders and graph-guided RAG (e.g., GraftNett PullNet, GraphRAG; (Sun et al., 2019 Edge et al. 20255), which rely fixed hop/degree/top-kk rules; (ii) path/rule learners (MINERVA,
NeuralLP, RNNLogic; (Das et al. 2018: Yang et al. 2017 Qu et al. (202T) that optimize task reward -ooo--httttttss, AutoGen; (Yao et al. 2023 Besta et al., 2024; Wu et al.. (023)) that interleave tools but do not enforce per- episode resources; and (iv) constrained RL. (RCPO or fixed-penalty PPO; MAPPO/COMA without
without explicit latency/token control; (ill) agentic LLMs (ReAct,
3

---

Published as a conference paper at ICLR 2026
Table 1: Notation. See Appendix for the extended table.
Symbol
Description
X = (V.
Global knowledge graph: E' S V x R V
G. = (Vi, (v) a
Evolving subgraph at step final subgraph
Fe; Ar
Frontier nodes; candidate pool at step t; typed outgoing candidates (navigator actions)
9: V. pr:
Input question; gold predicted answers
Path prefix at step t; of discovered paths (provenance)
WB, WT, as: dr
T as
Policies and actions for State summary at step E: by: remaining budgets (vector)
= (g. G1, Fi, Pt. bi)
8 (Bedgor Shat Proce)
Episode hudgets: edges, latency (steps), selected tokens
C = (Cotge, Cue, Ciok): (K)
Cumulative costs and per-step increments (& (edge, lat, tok): E. c, Ck) Lagrange multipliers (resource prices)
À (Datge, Ala, )ack)
Raco (T); rt: T
Episode reward; per-step task reward; shaped return r/ = r: En 2o c/
C(T, A)
Lagrangian B[ (T)e(T) X C(T)]
Qunk Qala Qin Qui
Centralized-crittc action-values (task head + three cost heads)
A. A (B,
Counterfactual and Lagrangian-shaped advantages; agent index Ordered curated evidence; token-count operator
D tok())
e = (u, v)
KG triple (head u, relation r, tail v)
H, d, Pdl K
Hop cap; avg local branching factor; pool size; selected list length (K dynamic)
constraints; (Tessler et al. 2019; Schulman et al. 2017 Yu et al., 2022; Foerster et al. 2018)). In
contrast, cast KGQA constrained decision process with three deployment-relevant costs (edges/steps/tokens), learn price-aware edit/raveers/ccrate policies with explicit STOP, and train with separate cost heads and dual variables single checkpoint supports both budget caps and price trade-offs.
PROBLEM FORMULATION
Problem. We study multi-hop KGQA over a typed knowledge graph K. = (V, R, E) with entities relation types Rt and triples E V x R x V. A query q is natural language; the gold answer y² C V can be a single entity or a set (surface strings, when provided, are canonicalized to IDs V). Given 9). the system outputs a prediction ý S V and compact, provenance- preserving context for the reader LLM. An episode corresponds to one question.
State and observations. At round the controller maintains working subgraph
G. Ex), E, C V, R Ve,
frontier F. C V of nodes eligible for expansion, candidate pool P. of textualized units (nodes/edges/paths and optional retrieval hits), and remaining budgets b, (bedge bl"t b( We write 8, (1, Gt, F,, Pt, b.), and each agent acts compact observation of (s())).
Action space. We three action families, E {EDIT, TRAVERSE, CURATE]. Let the current path prefix be Pt. = (uo, 11, Uy u.,.., ue) with tip uy. Define the typed outgoing options A, == ((r,0)) R x V (u,,,,v)) E E Then,
EDIT:
(ADD(E), DELETE(e), STOP),
e= (u.r,)) E E gcand
TRAVERSE: {CONTINUE(r, v'), BACKTRACK, STOP),
(r,v') E Ar,
CURATE: {SELECT(d), STOP).
d Pt.
where E geand are adjacet- edges (defined below).
Costs and budgets. We track episode-level costs for subgraph edits, interaction steps (latency proxy). and selected tokens (prompt cost):
Codge
Σ odge
Ciss
Σ di
Ciok
Σ yo
with increments (at most one edit per round)
edge
1a4 (ADD, DELETE))
Jal 1fat STOP), dek EdEAD, tok(d).
4

---

Published as a conference paper at ICLR 2026
where AD newly selected units at round and tok(-) counts tokens. Per-episode budgets = (Bedge, Sla Pwk). An episode ends when all three agents emit STOP or any budget is exhausted.
Objective (CMDP). Let Race (T) be the episode reward. We solve
max
B Racc (7) s.t. E[Corgee S Bedges
[E[Caa] S Bras, [[[roo]] S Brok-
(I)
The Lagrangian is L(x,, A) = E] Race A XTC] with prices À (Nelge Ala Awk) 2 0.
Frontierized subgraph. A subgraph G, is frontierized if Eqand C ((u,r, E E: u E Fi), i.e., all candidate expansions originate from the frontier. After each accepted edit or traversal, Fr is updated by adding touched endpoints and removing saturated nodes.
4 METHOD
4.1 CLAUSE OVERVIEW
We propose CLAUSE, an agentic neuro-symbolic framework for multi-hop KGQA that learns to edit, traverse, and curate compact, query-specific graph contexts under explicit per-episode budgets. An overview of the CLAUSE architecture is shown in Figure CLAUSE operates over KG symbols (entiiie//ellations/aatss with lightweight neural controllers, yielding auditable traces. Three agents act the evol evolving subgraph G, and are trained jointly with LC-MAPPO (centralized training with a constrained multi-head critic; $4.44: (i) Subgraph Architect for conservative, reversible edits to keep Gz compact; (ii) Path Navigator that decides BEITINNE/BAAKTRACKKCI
along symbolic paths; and (iii) Context Curator that performs budget-aware evidence selection with an explicit STOP. CLAUSE exposes deployable controls via per-query budgets (Bedges Blat, Ptok) equivalent prices X, enabling accuracy ceuurac--fffiiencyy trade-offs without retraining. The algorithms are given in the
Appendix C
LC-MAPPO (centralized critic dual updates)
Dual Ascent
Question
Centralized Critic: galoo
r Astge
cage
Auai
Jot
A
Dok
Audge
Variables:
joint state
advantages cost-shaped returns
Ed0t
Traveise
Subgraph Architect
Path Navigator
Context Curator
Curated context
BACKTRACK
(SELECT, STOP)
(budgetedd)
Reader LLM
Gred Beat. C add delete.stop!
(poths'), epr continue, backtrack. stop?
(selected)) X, (text), seleet.stops
Budget: Bedger Piat Brnk
Answer
Figure 1: The CLAUSE workflow. Three agents (Architect, Navigator, Curator) operate symbolic KG state under per-episode budgets; LC-MAPPO trains task and cost heads jointly and provides deployable dials inference.
4.2 DESIGN PRINCIPLES
Per-episode budgets. Each query carries budgets (Bedger Blat, Brok) (or prices X; see $3 Joint control. Editing, traversal, and curation are optimized together, replacing he-hop/derreettop.kkk heuristics.
Learned stopping. The agents keep going only if another hop or another snippet is worth its cost; otherwise they stop.
5

---

Published as a conference paper at ICLR 2026
Neuro-symbolic transparency. Actions discrete KG edits/moves; neural modules provide the scores; traces are auditable.
4.3 AGENTIC WORKFLOW
At each decision round, CLAUSE executes a three-stage loop-edit + Iruverse + cu- rule- clfedconditooned on (Bedge: Shat, Btok) or A. After every action, counters (Cedge: Clat; Ctok) update, remaining budgets are recomputed, and any agent may issue STOP; the episode ends when all modules stop or budget is exhausted. We train three agents jointly with LC-MAPPO (Section 4.4).
(1) Subgraph Architect (anchoring & edit). From the question q, we extract mention candidates M (q) by matching to entity names/aliases (optionally aided by simple tagger). For mention m and entity v, we compute the anchor score Sanch (m, v). We aggregate to an entity score Sent (v q) (aXXeeM(g) Sauch (m, v), and form seed set So by taking the top-k entities. If alias hits weak or absent, we fall back to a frozen-encoder retrieval over entity textual fields and take the top-k seeds. The initial frontier is Fo So; the initial subgraph Go built around Fo (within budget).
Let (G) be the current subgraph and frontier Fe S V(G.). The architect considers frontier- adjacent candidates Es exand - {(u,, r, E E: E FiJ. Each candidate e (u. r, v) receives fused score
s(e q, G.) = w7/ [TToeen (u, 4), (r; 4), Ontr(u, Gr), Odeg (o)g(())
where dent and chel combine lexical features and cosine similarities from a frozen encoder, and Pubrs Odeg encode neighborhood and degree priors (hub throttling). At step t the agent chooses a, E (ADD, DELETE, ]TOP) and, if applicable, et E Erand to maximize the price-shaped gain
g(a, q, G.) = s(e q, G+) Aedge Gedge (a, e),
subject to remaining edge/latency budgets. An edit applied only g et) > 0 and budget remains; (1++1,e+t) are updated accordingly. All candidates originate from the frontier, avoiding uninformed k-hop expansions. Per round, scoring costs OCCdd) with CB = [gand and encoder width d: applying accepted edits costs O(AE).
(2) Path Navigator (traverse). Given GG, the navigator maintains path prefix pt. and observes (g, ut, Ar, summaryy (p:)), where A, are typed outgoing candidates. A light encoder outputs (i) a termination head over (STOP, CONTINUR) and (ii) candidate logits over A, when continuing: explicit action. Each hop increments Clats so continuation occurs only when expected shaped value exceeds the current step price. We cap the horizon by small H and retain log-prod probabilities for credit assignment. Discovered paths IT (p1...., Pm serve as human-readable provenance.
BACKTRACK is modeled
(3) Context Curator (curate). From pool Pa (textualized nodes/edges/paths and optional retrieval hits), the curator performs listwise selection with an explicit STOP:
max 8
R plask (S)
s.t.
Σ Lok(c) S Brok:
S = Curate Curate(PP, (P3
CES
Beyond independent passage thresholds, we use listwise, redundancy-awarr scoring with a learned STOP head conditioned on the token price (dual \tck), aligning selection with Ctok and producing compact, complementary evidence sets that are both efficient and auditable.
Observations and cost attribution. Agents receive compact summaries of (G,, P,) and the remaining budgets. Costs are attributed at source, edits - Codges steps Clat, curations - Ctok. which simplifies credit assignment and supplies the cost signals used by LC-MAPPO.
4.4 LEARNING: LC-MAPPO
To enforce per-episode budgets in edges, steps, and tokens while preserving accuracy, propose AC-MAPPO, ceerrangian-constrainn CTDE variant of MAPPO that jointly learns task value and multiple cost processes with deployable test-time dials. A centralized critic estimates task head Qtask and three cost heads (Qedge Qlat, Qtok) over joint actions; a monotonic mixer aggregates
(k) per-agent utilities for each head (Rashid et al. 2020 Let Ce denote instantaneous cost increments

---

Published as a conference paper at ICLR 2026
whose episode sums yield C₁ in Eq. I for &e E fedge, lat, tok). The PPO surrogate COMA-style
counterfactual advantages (Foerster et al. 2018 Schulman et al. 2017 Yu et al. 2022) on the shaped return
r ri Aodge C
odge
Alat Ct
lat
Aeak tok
(2)
which instantiates the per-step Lagrangian of the CMDP Eq. At optimum, the duals X equal the partial derivatives of the optimal value w.r.t budgets (shadow-price property), and therefore predict the local slope of the accuracy- wartoyy--aeeeyy-coo frontiers (Appendix(G).
Rather than fixing single penalty, LC-MAPPO maintains separate dual variables Xedge Alats Atok and updates them by projected ascent,
d - [Ax 7/ (B[C)]-Ba)]4r
Bx)] k E {edge, lat, tok).
optionally stabilized with PID control (Achiam et al. 2017: Stooke et al. 2020). This stochastic dual ascent on the Lagrangian of Eq. [ moving À to enforce E[Ca] S. By while actors ascend
the shaped objective. The separation of a task head from cost heads improves credit assignment and exposes explicit accuracy uecuracy-efficiency trade-offs at test time (tune À or B without retraining). Convergence is stated Appendix H.
4.5 INFERENCE AND DEPLOYMENT CONTROLS
At test time, agents act greedily with learned STOP. Operators may in cap mode (set (Bedge: Stat, ))ok) for hard guarantees or in price mode (fix A) for smooth trade-offs- both from a single checkpoint. Symbolic decisions yield step-level traces (what was added, explored, selected, and where we stopped) for audit and ablation.
5 EXPERIMENTS
Dataset. We evaluate on three multi-hop KGQA datasets, including METAQA (Zhang et al. 2018).
HOTPOTQA (Yang et al. 2018 and FACTKG (Kim 2023
Baselines. We compare three families under a shared retriever/reader and decoding (except the
no-retrieval group). Pretrained LLMS (no retrieval): GPT-OSS-I20B LLaMA3.3-70B: Qwen3-
32B. RAG methods (Qwen3-32BB: Vanilla RAG (Lewis et al. 2020); ; Hybrid RAG (Robertson
Zaragoza 2009; Karpukhin et al. 2020 Nogueira & Cho. 2020); LightRAG (Guo al.
2025 ;
GraphRAG (Edge et al. (2025). Agent- based methods (Qwen3-32B): ReAct (aoo et al.
2023);
Sraph-of-Thoughee (GoT) (Besta et al. 2024); AutoGen (Wu et al. (023); KG-Agent (Jiang et al.
2025). Additionally, LC-MAPPO is compared with MAPPO ( Yu et al. 2022). fixed-penalty PPO
(Schulman et al. 2017) and single-multiplier RCPO [Tessler et al. 2019
Metries. Accuracy is reported top-1 exact match (EM@) I). Efficiency is measured by (i) Average latency, normalized so that Vanilla RAG = 1.0x per dataset/hop; and (ii) Average edge budget, i.e., the mean number of graph edges explored, also normalized to Vanilla RAG 1.0x.
5.1 EXPERIMENTAL RESULTS AND ANALYSIS
Exact Match. Table 2 reports EM@ in HotpotQA (distractor), FactKG, and MetaQA. CLAUSE achieves the best accuracy on all datasets and hops (71.7 on HotpotQA, 84.2 on FactKG, and 91.0/87.3/85. on MetaQA 1/2/3-hop), consistently surpassing both RAG baselines (e.g., Hybrid RAG 66.0 on HotpotQA) and agent baselines (e.g., KG-Agent 68.7 on HotpotQA, 87.3/78.0/75.4 on MetaQA). Pure pretrained LLMs perform markedly worse, highlighting the value of budget-aware, neuro-symbolic control over subgraph editing, traversal, and evidence curation.
Latency. Table 3 shows average latency normalized to Vanilla RAG = 1.0x. Among RAG methods, LightRAG is the fastest but sacrifices accuracy; GraphRAG is slowest because of graph construction overheads. Agent baselines incur higher latency than RAG (e.g., AutoGen and GoT are the slowest) because multi-step tool/use deliberations. CLAUSE achieves agent-level accuracy with competitive efficiency: its latency is close to below Hybrid/GraphRAAG and substantially lower than typical agent systems (e.g., 1.48x on HotpotQA vs. 2.43x x for AutoGen), and even dips below Vanilla on MetaQA 1-hop (0.98 x), reflecting effective learned stopping and budgeted context construction;
accuracccy
7

---

Published as a conference paper at ICLR 2026
Table 2: Main QA results: EM@ I HotpotQA, FactKG, and MetaQA.
Family
Method
HotpotQA (Distractor)
FactKG
MetaQA
1-hop
2-hop
3-hop
GPT-OSS-120#
44.5
68.0
62.7
41.5
52.3
Pretrained-LLLMs
L.L.MA33-7708
41.0
57.2
29.0
44.2
Qwen3-32B
37.9
60.1
52.5
22.8
39.0
Vanilla RAG
62.1
77.0
60.2
37.6
33.0
RAG-based
Hybrid RAG
66.0
80.2
63.0
41.5
34.1
(Qwen3-32B)
LightRAG
44.3
64.5
54.0
35.0
32.0
GraphRAG
50.1
72.0
63.5
48.0
44.4
ReAct
63.5
78.2
82.3
52.1
49.4
Agent-based
Graph-of- ofoooghhts
59.2
74.0
79.5
48.4
46.3
(Qwen3-32B)
AutoGen
64.0
85.2
55.7
53.5
KG-Agent
68.7
82.1
87.3
78.0
75.4
Ours
CLAUSE
71.7
84.2
91.0
87.3
85.5
the slight rise at 2/3-hop mirrors increased multi-hop exploration while remaining well under other agentic baselines.
Table Efficiency results: Average latency (normalized to Vanilla RAG = 1.0x).
Family
Method
HotpotQA (Distractor)
FactKG
MetaQA
1-hop
2-hop
3-hop
Vanilla RAG
1.00
1.00
1.00
1.00
1.00
RAG-based
Hybrid RAG
1.18
1.15
1.12
1.20
1.28
(Qwen3-32B)
LightRAG
0.85
0.88
0.80
0.83
0.86
GraphRAG
1.45
1.35
1.25
1.40
1.60
ReAct
1.62
1.40
1,25
1.45
1.70
Agent-based
2.10
1.78
1.65
1.90
2.32
(Qwen3-32B)
AutoGen
2.43
2.20
1.81
2.14
2.62
KG-Agent
1.70
1.54
1.30
1.62
1.90
Ours
CLAUSE
1.48
1.36
0.98
1.14
1.27
Average Edge Budget. Table reports the average edge budget normalized to Vanilla RAG (1.0x),
which reflects how much the working subgraph grows during context construction. Within RAG baselines, LightRAG is the most frugal (0.75-0.82) and GraphRAG the most expansive (1. (1.18-1.55). while Hybrid RAG sits slightly above Vanilla due dual-channel retrieval and re-ranking. Agent systems generally consume more edges than RAG (e.g., AutoGen up to 2.10x on MetaQA-3hop) because multi-step deliberation triggers additional expansions. contrast, CLAUSE achieves the smallest edge budgets across all settings (0.74-0.90) while still delivering the best EM (cf. Table 2 indicating that its budget-aware subgraph editing and learned STOP decisions effectively suppress redundant growth. The modest increase from MetaQA 1-hop to 3-hop matches the expected need to explore deeper paths, yet remains well below other agentic approaches.
Table 4: Efficiency results: Average Edge Budget (normalized to Vanilla RAG 1.0x).
Family
Method
HotpotQA (Distractor)
FactKG
MetaQA
1-hop
2-hop
3-hop
Vanilla RAG
1.00
1.00
1.00
1.00
1.00
RAG-based (Qwen3-32B)
Hybrid RAG
1.12
1.08
1.05
1.12
1.20
LightRAG
0.78
0.80
0.75
0.78
0.82
GraphRAG
1.35
1.30
1.18
1.32
1.55
ReAct
1.20
1.13
1.05
1.18
1.35
Agent-based
Graph-of Thoughhss
1.55
1,40
1.30
1.55
1.85
(Qwen3-32B)
AutoGen
1.84
1.72
1.45
1.75
2.10
KG-Agent
1.30
1.22
1.10
1.32
1.58
Ours
CLAUSE
0.78
0.74
0.77
0.78
0.90
Token Usage. As shown Figure 2 across all three datasets, Qwen3-32B (no RAG) exhibits
the lowest normalized token usage (because retrieved context concatenated), while CLAUSE,
8

---

Published as a conference paper at ICLR 2026
without relying multi-agent expansion, consistently uses fewer tokens than the family averages of RAG-based and Agent- based methods, indicating better token efficiency. (Note: the MetaQA panel reports the average the 1/2/3-hop settings.)
Token Usage (normalized) mean = SD
HotpatQA
FactKG
MetaQA
Normalize Tiken Mass x
2.0
1.01
(aanlss RMG
0.5
Owen 3-320)
HAG-based
Agent-based
ours
Qwen3-320
RAG-based
Agentibased
Dur3
Ow323-3216
HAG-based
Agent-hased
cus
Figure 2: Normalized Token Consumption (Vanilla RAG = 1.0x).
Constraint Satisfaction Performance. We evaluate LC-MAPPO against MAPPO Yu et al. 2022 Fixed-Penalty PPO (Schulman et al. (017)) and RCPO (Tsssler al. 2019) on the MetaQA KGQA task under constrained settings (edge budget = 0.5, latency budget = 0.7). Figure 3 demonstrates LC-MAPPO's superior constraint satisfaction capabilities across multiple metrics. LC-MAPPO achieves a 191 % improvement in feasibility rate compared to standard MAPPO (0.340 vs. 0.117), indicating significantly better constraint adherence. Furthermore, LC-MAPPO reduces latency violations by 34% (0.577 vs. 0.880) and latency costs by 12% (0.738 vs. 0.838), demonstrating effective latency-aware optimization. LC-MAPPO demonstrates the strongest constraint learning with adaptive dual variables of 0.004, outperforming RCPO's 0.001 and surpassing methods without constraint adaptation, confirming that our multi-head centralized critic successfully learns to balance task performance with constraint satisfaction. These results validate LC-MAPPO's design for constraint- aware MARL, where the algorithm substantially improved constraint compliance.
Constroint Peasbilky
Latengy Vilktions
Latency Cast
Constraist Leaming
More
1933
0.7
1910
3335
6.0
66
60
3909
Figure 3: Constraint satisfaction performance comparison. (a) Constraint Feasibility. (b) Latency Violations. (c) Latency Cost. (d) Constraint Learning.
5.2 ABLATIONS
As summarized in Table 5 removing any agent or disabling constraint handling hurts both accuracy and efficiency. The full CLAUSE attains the best EM@ (87.3) the reference latency and edge budget (both x..0 Without the Subgraph Architect (StaticRAG; no-KG), EM drops sharply to 74.8 while latency and edge usage rise 1.32x and 1.44x, indicating severe over-expansion without budget-aware graph editing. Removing the Path Navigator (Greedy-Hop) yields EM 82. with higher latency/edges (1.18 x /1.22x), showing that learned contimue/backtraac/sttoo decisions are important for disciplined exploration. Omitting the Context Curator (Top-k Rerank) reduces EM to 80.6 and raises latency to 1.24x (edges 1.07)), reflecting longer, unpruned contexts when the learned stop is absent. Constraint ablations further confirm the role of LC-MAPPO: MAPPO without duals achieves EM 85.0 but overshoots edges (1.28x x), and fixing À (no updates) reaches EM 84.6 with milder but persistent budget violations (1.06x latency, 1.15x edges). Together, these results demonstrate that all three agents and adaptive dual updates are necessary to jointly optimize EM, latency, and edge growth under requirements.

---

Published as a conference paper at ICLR 2026
Table 5: Core ablations on MetaQA. All runs use the same reader and settings (normalized to CLAUSE 1.0x).
Latency: (avg)
Edge budget
Variant
EM@N 1f
(avg)
CLAUSE (full)
87.3
1.00
1.00
Subgraph Architect (StaticRAG; no-KG)
1.44
w/o Path Navigator (Greedy Hop: traversal policy)
82.1
1.18
1.22
w/o Context Curator (Top-k Rerank; no learned stop)
80.6
1.24
1.07
MAPPO (no duals)
1.28
Fixed (no updates)
84.6
1.06
1.15
5.3
CASE STUDY
Question: Who co-starred with Brian Backer?
(1) Subgraph Architect. Anchors: Brian Backer (actor).
Add (Moving Violations, starred actors, Brian Backer)
Add (...)
Stop (edge budget nearly met)
(2) Path Navigator Path discovered:
Actor_A A
ataroed_actors Movie
starzed_actora,
Actor_B
At hop backtracking is not triggered; STOP fires with high confidence due to saturated utility.
(3) Context Curator. With Bock 512, the curator selects two snippets: "Moving Violations - starred actors: Jennifer Tilly" and "Moving Violations starred actors: John Murray". Token mass is N2 36 (< B,ok), so STOP triggers; latency is 238.6 ms. The reader returns Jennifer Tilly & John Murray, (The complete process illustrated Figure
Brian Backer'
Brion Racker
Brian Backor
Mostng
John Murray
Jennifor Tilly
Ascher Greay Rhespetton
Relasion: virmed aetore
Lecil Suagean
William
Disturb
(a)
Figure 4: End-to-Ene Case Study Overview.
CONCLUSION
This work formulates KGQA dynamic learnable context construction: instead of fixed k-hop neighborhood, the system must decide what context to assemble, how to obtain it, and when to stop under per-query limits edits, interaction steps, and tokens. CLAUSE instantiates this by decomposing context into three components: (i) subgraph structure, (ii) path traces, and (iii) textual evidence, and assigning them to three simple agents (Architect, Navigator, Curator) that make discrete, auditable choices. LC-MAPPO optimizes the overall workflow by pricing resources via a centralized multi-head critic with dual variables, agents continue only when the predicted marginal utility exceeds the current price. This requirement-condiiionnee controller yields compact provenance and predictable latency/cost, and empirically traces stronger accuracy-effcienne frontiers than heuristic expansion unconstrained agent loops.
10

---

Published as a conference paper at ICLR 2026
ETHICS STATEMENT
We comply with the ICLR Code of Ethics. This work uses only publicly available benchmark datasets and does involve human-subject data or personally identifiable information; therefore, IRB approval was not required. The methods are intended for benign research uses and are not designed facilitate privacy violations or discriminatory outcomes. The authors declare no conflict of interest.
ACKNOWLEDGEMENT
This research is supported by Seatrium New Energy Laboratory, Singapore Ministry of Education (MOE) Tier I (RT5/23 and RG24/24), the Nanyang Technological University (NTU) Centre for Com- putational Technologies in Finance (NTU-CCTF), and the Research Innovation and Enterprise (RIE) 2025 Industry Alignment Fund Industry Collaboration Projects (IAF-ICP) (Award 12301E0026), administered by Agency for Science, Technology and Research (A (A*STAR).
REPRODUCIBILITY STATEMENT
We provide an anonymized code archive in the supplementary materials. The model and objective are specified in Section 4 and pseudocode in Appendix C Datasets and preprocessing are described in Section 5 and Appendix DD. Metrics, baseline settings, and normalization are defined in Section 5 seeds, environment details, and run scripts are included in the archive.
REFERENCES
Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML 17, pp. 22-31. Jogg. 2017.
Akari Asai, Zeqiu Wu, Yizhong Wang, Avi Sil, and Hannaneh Hajishirzi. Self-RAG: Learning to Retrieve, Generate, and Critique through Self-Reflection. In International Conference on Learning Representations, 2024.
Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, and Torsten Hoefler. Graph of thoughts: solving elaborate problems with large language models. In Proceedings of the Thirty- Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in A Artificial Intelligence, AAAT224AAAT244AAAPPT AAAI Press, 2024. ISBN URL https::ttt.... /ooi hww.ddo..oorrooooooooooo 1669/1609/60000 wwt.///./............o.
9. doi: http://aaaiv33ii6..222 29720
William W. Cohen. Tensorlog: A differentiable deductive database, 2016. URL hRtpps//:///ax
org/abs/ abs/lbas..5 06523
Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krishna- murthy, Alex Smola, and Andrew McCallum. Go for walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning. In International Conference on Learning Representations, 2018.
Lauren Nicole DeLong, Ramon Fernández Mir, and Jacques D. Fleuriot. Neurosymbolic ai for reasoning over knowledge graphs: A survey. IEEE Transactions on Neural Networks and Learning Systems, (6())))8)))))77288888888 7842, May 2025. ISSN 2162-2388, doi: 10. 1099tmmls.20224442221 URL http::/dx..o doi www./g//...... 1109/TNNIS. 2024. 2024.342021
Wentao Ding, Jinmao Li, Liangchuan Luo, and Yuzhong Qu. Enhancing complex question answering over knowledge graphs through evidence pattern retrieval. In Proceedings of the ACM Web Conference 2024, WWW '24, pp. 1115-2115, New York, NY. USA, 2024. Association for Computing Machinery. ISBN 9798400701719. doi: 11114//358933436655566 URL (tthttps
7/doi aeloi.org/10.11600 11lp://11..15/588888 36443

---

Published as a conference paper at ICLR 2026
Darren Edge. Ha Trinh, Newman Cheng, Joshua Bradley, Alex Chao, Apurva Mody, Steven Truitt, Dasha Metropolitansky, Robert Osazuwa Ness, and Jonathan Larson. From local to global: A graph rag approach to query-focused summarization, 2025. URL https://aaxiiy/ org/ abs/
2404. 66130
Jakob N. Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon White- son. Counterfactual multi-agent policy gradients. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelli- gence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence. AAAI 18/1AAI' 18/EAAI 18, AAAI Press, 2018. ISBN 378-1-57735-800
Zirui Guo. Lianghao Xia, Yanhua Yu, Tu Ao, and Chao Huang. LightRAG: Simple and fast cttreval-augmeent generation. In Christos Christodoulopoulos, Tanmoy Chakraborty. Car- olyn Rose, and Violet Peng (eds.), Findings of the Association for Computational Linguistics: EMNIP 2025, pp. 10746- 10761, Suzhou, China, November 2025. Association for Computa- tional Linguistics. ISBN 979-8-89176-335-- doi: 10. (065:////222....nnnnnnnnoo https://aclanttolooryoooo
URL
findings em..p.5687
Feijiang Han, Hengtao Cui, Licheng Guo, Zelong Wang, and Zhiyuan Lyu. Read before you think: Mitigating I1m comprehension failures with step-by-step reading, 2025. URL https
/ /arxivv org/ h0lpg//b//2554... 09402
Gautier Izacard, Patrick Lewis, Maria Lomeli, Lucas Hosseini, Fabio Petroni, Timo Schick, Jane Dwivedi- Yu, Armand Joulin, Sebastian Riedel, and Edouard Grave. Atlas: Few-shot learning with retrieval augmented language models. Journal of Machine Learning Research, 24(251):1-43, 2023.
URL http:
jm r. www.or/pppp.//eeeeep
0037 .html
Soyeong Jeong, Jinheon Back, Sukmin Cho, Sung Ju Hwang, and Jong Park. Adaptive-RAG RRAG: Learning to adapt retrieval-augmented large language models through question complexity. In Kevin Duh, Helena Gomez, and Steven Bethard (eds.), Proceedings the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Lan- guage Technologies (Volume 1: Long Papers), pp. 7036-7050, Mexico City, Mexico, June 2024. Association for Computational Linguistics. doi: 10. 10.11665/w11220244aaaccoooo attiss:/acclanthologg/ org/204 wtt.rr///222.aaan11ooooo
URL
3897
Jinhao Jiang, Kun Zhou, Wayne Xin Zhao, Yang Song, Chen Zhu, Hengshu Zhu, and Ji-Rong Wen. KG-agent: An efficient autonomous agent framework for complex reasoning over knowledge graph. In Wanxiang Che, Joyce Nabende, Ekaterina Shutova, and Mohammad Taher Pilehvar (eds.), Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 9505-9523, Vienna, Austria, July 2025, Association for Computational Linguistics. ISBN 77779-8-9976-25---1 //aclanthology orq wwtp:///.///22..1111....
doi: 1/265////112225salllloooo 46/
URL https
Yichen Jiang and Mohit Bansal. Avoiding reasoning shortcuts: Adversarial evaluation, training, and model development for multi-hop QA. In Anna Korhonen, David Traum, and Lluís Marquez (eds.), Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 2726-2736. Florence, Italy, July 2019. Association for Computational Linguistics. doi: 10.18653/w1/P19. 1262. URL haattpp://acllanhhloog.y.
Vladimir Karpukhin, Barlas Oguz. Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 6769-6781, Online, November 2020. Association for Computational Linguistics. doi: 18658v/3/v hittps://aclanse
URL
ooyy wwtp:orgg200000 emn p- ma i n. 5507
Jiho Kim, Sungjin Park, Yeonsu Kwon, Yohan Jo, James Thoree, and Edward Choi. FactKG; Fact verification via reasoning on knowledge graphs. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Proceedings of the 61st Annual Meeting of the Association for Toronto, Canada, July
Computational Linguistics (Volume 1: Long Papers), pp. 2023. Association for Computational Linguistics. doi: 10.18653/v h/l//3.acc--..... acl-Iong..95. URL https: / antho ogw.org........... acl long. 8957|
12

---

Published as a conference paper at ICLR 2026
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, Red Hook, NY, USA, 2022. Curran Associates Inc. ISBN 9781713871088
Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel. Sebastian Riedel, and Douwe Kiela. aetrieval-augmentt generation for knowledge-intensiee nlp tasks. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
Xiao Liu, Hao Yu, Hanchen Zhang, Yifan Xu, Xuanyu Lei, Hanyu Lai, Yu Gu, Hangliang Ding, Kaiwen Men, Kejuan Yang, Shudan Zhang, Xiang Deng. Aohan Zeng. Zhengxiao Du, Chenhui Zhang, Sheng Shen, Tianjun Zhang. Yu Su, Huan Sun, Minlie Huang. Yuxiao Dong. and Jie Tang. Agentbench: Evaluating Iims agents. In B. Kim, Y. Yuc. S. Chaudhuri, K. Fragkiadaki, M. Khan, and Y. Sun (eds.). International Conference on Learning Representationss volume 2024, pp. 52989- 53046, 2024. URL http:: http:ttss//pppcceeeiiioee iclr http:n/w........oo.eeeeeeeeeeeee fi
Shengjie Ma, Chengjin Xu, Xuhui Jiang, Muzhi Li, Huaren Qu, Cehao Yang, Jiaxin Mao, and Jian Guo. Think-on-graph 2.0: Deep and faithful large language model reasoning with knowledge- guided retrieval augmented generation. In Yue, A. Garg, N. Peng, F. Sha, and R. Yu (eds.), International Conference Learning Representations, volume 2025, pp. 52782-528888 2025. URL ht: httpttppsp//pp//eeeee/ssesse//// iclr http://pppprr.llleeeeeerer//////
Rodrigo Nogueira and Kyunghyun Cho. Passage re-ranking with bert, 2020. URL https://
arxiv. mexiivorg/abs/19000 04085
Jeff Z. Pan, Simon Razniewski, Chriitrito Kalo, Sneha Singhania, Jiaoyan Chen, Stefan Dietze, Hajira Jabeen, Janna Omeliyanenko, Wen Zhang, Matteo Lissandrini, Russa Biswas, Gerard de Melo, Angela Bonifati, Edlira Vakaj, Mauro Dragoni, and Damien Graux. Large language models and knowledge graphs: Opportunities and challenges, 2023. URL htttss://arx: org/ org/abs/ 2208. 06374
Ofir Press. Muru Zhang, Sewon Min, Ludwig Schmidt, Noah Smith, and Mike Lewis. Measuring and narrowing the compositionality gap in language models. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Findings of the Association for Computational Linguistics: EMNLP 2023, pp. 5687-5711, Singapore, December 2023. Association for Computational Linguistics. doi: 10.18653/v 1/2023, findings-emmlp.378 URL httppss//aclamtholocyyycoo orgp:t//o2oocyo.o.2233033 Findings emn 378/
Meng Qu, Junkun Chen, Louis-Pascal Xhonneux, Yoshua Bengio, and Jian Tang. Rmnlogic: Learning logie rules for reasoning on knowledge graphs, 2021. URL https:: httt:s://arxiv.ogg/// 0010.04022
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly reward model. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.). Advances in Neural Information Processing Systems, volume 36. pp. 53728-53741. Curran Asso- ciates, Inc., 2023. URL htt.htttpp.//prrrceeiigg.gg neur wappr fites_/feeeeeeeee
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Monotonic value function factorisation for deep multi-agent reinforcement learning. J. Mach. Learn. Res., 21(1), January 2020. ISSN 1532-4435.
Stephen Robertson and Hugo Zaragoza. The probabilistic relevance framework: Bm25 and beyond. Found. Trends Inf. Retr, 3(4):333-38)) April 2009. ISSN 1554-0669. doi: 10.1561/1500000011, _ https:::p/.............t // . wtt../////.....11..1001
13

---

Published as a conference paper at ICLR 2026
Timo Schick, Jane Dwivedi-Yor Yu, Roberto Dessi, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models teach themselves to use tools. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural In- formation Processing Systems, volume 36, pp- (8539-68551) Curran Associates, Inc.,
2023. URL (at.242eeeee...99999999922aaaa.. 2e1224254bff/335
pewpeeiiiinnnn..uuuugo newrips cctppppee files/ /ateee/pppr///2333 Paper Conference. Paper-Cnneeerrreeeeeeeeeeeeeee pddf
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang. Y. K. Li, Y. Wu, and Daya Guo. Deepseekmath: Pushing the limits of mathematical reasoning in open language models, 2024. /ttt:::: http://xxxvv.rr..//. wwg.ooog//aao... /bs/
24C2203330
Yongliang Shen, Kaitao Song, Xu Tan, Dongsheng Li, Weiming Lu, and Yueting Zhuang. Hugginggpt: Solving ai tasks with chatgpt and its friends in hugging face. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neu- ral Information Processing Systems, volume 36, pp. 38154-38180. Curran Associates, Inc., neurips wttppppp..cppaaaeeeeeeeeeeeeeeee ww/paperpeeeeccccceeeee.e files//paerr/2223 File/ #1le/7c33e633322222051101f120222
2023. URL https::
Paper Conference. pdf
Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: language agents with verbal reinforcement learning. In A. Oh, T. Nau- mann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neu- ral Information Processing Systems, volume 36, pp. 8634-8652. Curran Associates, Inc., Filess/aperr2023/ pdf
2023. URL
www.:upsseeeuuiiiececc..e.eeee wctpppppppccppppppeeeppeeppppppe http://ceedannss.eeeep..s..caaaa File/1b44b3 8bb 2ttp1//107701222023222222222--00
Lennert De Smet and Luc De Raedt. Defining neurosymbolic ai, 2025. URL httts:://aaaat
org/abs ///g//b//200 2507.
11127
Adam Stooke, Joshua Achiam, and Pieter Abbeel. Responsive Safety in Reinforcement Learning by PID Lagrangian Methods. In International Conference on Machine Learning, pp. 9133-9143, PMLR, 2020.
Haitian Sun, Tania Medrax-Weiss. and William Cohen. PullNet: Open domain question answering with iterative retrieval on knowledge bases and text. In Kentaro Inui, Jing Jiang. Vincent Ng, and Xi- aojun Wan (eds.). Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP. IJCNLP), pp. 2380-2390, Hong Kong, China, November 2019. Association for Computational I Lin- guistics. doi: 10. 1/D1999 /tttttss:://eatt aatannooooooo oont:ollooy..or//11112222
Chen Tessler, Daniel J. Mankowitz, and Shie Mannor. Reward Constrained Policy Optimiza- tion. In International Conference Learning Representations (ICLR), 2019. URL https
//openreview. wwt. wwtp:/ttoooomommmmnmmmmmmm
Zhongwei Wan, Xin Wang, Che Liu, Samiul Alam, Yu Zheng, Jiachen Liu, Zhongnan Qu, Shen Yan, Yi Zhu, Quanlu Zhang, Mosharaf Chowdhury, and Mi Zhang. Efficient large language models: A survey, 2024. URL htttps://aaxttitt org/ abs 2312. 03863
Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Voyager: An open-ended embodied agent with large language models, 2023. URL TRRK//tpps///ext..oor////////
16291
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed Chi, Quoc V Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language mod- els. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Ad- vances in Neural Information Processing Systems, volume 35, pp. 24824 24837. Curran Asso- ciates, Inc., 2022. URL htt.:////w...leeeeoooooccc.....n http://pwooceceinoo..o..r......p
14

---

Published as a conference paper at ICLR 2026
Qingyun Wu, Gagan Bansal, Jieyu Zhang, Yiran Wu, Beibin Li, Erkang Zhu, Li Jiang, Xiaoyun Zhang. Shaokun Zhang. Jiale Liu, Ahmed Hassan Awadallah, Ryen W White, Doug Burger, and Chi Wang. Autogen: Enabling next- next-gen gen Ilm applications via multi-agent conversation, 2023. URL
htttps://erst
org/ abs 2308 . 585
Fan Yang, Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning. In Guyon, U. Von Luxburg, S. Bengio, Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Cur- ran Associates, Inc., 2017. URL http:httttsptttttttt http.tttttpsppppeeeeiinooooo ngs neurips cc/paper files/
Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. HotpotQA: dataset for diverse, explainable multi-hop question answer- ing. In Ellen Riloff, David Chiang. Julia Hockenmaier, and Jun'ichi ichi Tsujii (eds.), Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 2369-2380, Brussels, Belgium. October-November 2018. Association for Computational Linguistics. doi: 1LL18663/11/DI--2255
1259/
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models, 2023. URL htt.t::tt///xttttt
org/abs/ 2210. 03629
Michihiro Yasunaga. Hongyu Ren, Antoine Bosselut, Percy Liang, and Jure Leskovec. QA-GNN:
Reasoning with language models and knowledge graphs for question answering. In Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer, Dilek Hakkani-Tur, Iz Beltagy, Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou (eds.), Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 535-546, Online, June 2021. Association for Computational Linguistics. doi: 10. 18653/v1/2021 htw.:///.2....aallieeaaaaaa mandd-maii......
URL htt.ltpps//aaaaatoooooooooog/
naacl-ma
457
Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness PPO cooperative multi-agent games. Advances in neural information processing systems, 15:24411-22666 2022.
J. Zhang, L. Yao, X. Chen, X. Wang, J. Wang, and B. Benatallah. Neural, symbolic and neural- symbolic reasoning on knowledge graphs. Al Open, 2:14-35, 2021.
Yuyu Zhang, Hanjun Dai, Zornitsa Kozareva, Alexander J. Smola, and Le Song. Variational rea- soning for question answering with knowledge graph. In Proceedings of the Thirty-Secone AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelli- gence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence, AAAI' 18/AAA/ 18/EAAI 18. AAAI Press, 2018. ISBN 978-1-57735-800
Zihan Zhang, Meng Fang, and Ling Chen. RetrievalQA: Assessing adaptive retrieval-augnee -argeeeed generation for short-form open-domain question answering. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Findings of the Association for Computational Linguistics: ACL 2024, pp. 6963-6975, Bangkok, Thailand, August 2024. Association for Computational Linguis- 1i0.0...iningg-acl44115. URL https:://aclatthoollgoo
tics. doi: 10.18653/11
aircings-ac1.4157
Yining Zhou. Self-supervised transfer learning with shared encoders for cross-domain cloud op- timization. In 2025 5th International Conference on Electronic Information Engineering and Computer Science (EIECS), pp. 1435-1439. IEEE, 2025.
Zixuan Zhou, Xuefei Ning, Ke Hong. Tianyu Fu, Jiaming Xu, Shiyao Li, Yuming Lou, Luning Wang, Zhihang Yuan, Xiuhong Li, Shengen Yan, Guohao Dai, Xiao-Ping Zhang, Yuhan Dong, and Yu Wang. A survey on efficient inference for large language models, 2024. URL https // a Tarxiv.cm org/ aba/ 14294
15

---

Published as a conference paper at ICLR 2026
APPENDIX CONTENTS
Large Language Models Usage Disclosure
17
Notation Table
18
Algorithm
19
Implementation Details & Supplementary Experiment
21
Complexity Analysis
22
E,1 Time Complexity
22
Space Complexity
23
Training Cost and Scalability to Large and Noisy KGs
24
Trade-off Analysis
25
Lagrangian shaping: costs as prices, duals as shadow values
25
Proof of Convergence of L.CMMAPPO
26
Assumptions
26
H.2
Primal (Actor) Convergence for Fixed Duals
26
H.3
Dual (Multiplier) Convergence and KKT
27
H.4
Proof Template Mirroring A Smoothness Step
27
16

---

Published as a conference paper at ICLR 2026
A LARGE LANGUAGE MODELS USAGE DISCLOSURE
Scope of use. We used large language models in three defined roles:
1. Writing assistance (polish/clarity only). Micro-edits for grammar, concision, tense/voice consis- tency, LaTeX phrasing, section headings, figure/talle captions, and title/abstract variants.
2. Retrieval & discovery (related work support). Query about recommended papers related my idea.
Research ideation (early brainstorming). Generating alternative task framings, evaluating feasibility of this, naming options for modules.
Author responsibilityy and claims. LLMs supported drafting, search query design, and ideation; they did not generate or select results.
The authors are solely responsible for the methods, experiments, analyses,
17

---

Published as a conference paper at ICLR 2026
B NOTATION TABLE
Table 6: Symbols and notation used throughout the paper.
Symbol
Description
K = (V,
Global knowledge graph with entities V, relations R. and edges
S V R x V
G. Ev)
Query-conditiones subgraph at step t: final subgraph at termination Frontier node set at step
Fe
P.
Candidate pool (textualized nodes/edges/pathhs and optional retrieval
hits) at step
A
Typed outgoing candidates (actions) available to the navigator at step Input question; gold predicted answers Path prefix maintained by the navigator; of discovered paths (provenance)
Ti G.y.
Psi II
{PI...... pml
TB, IT, TT
Policies for EDIT (Subgraph Architect), TRAVERSE (Path Navigator), CURATE (Context Curator)
az ag a
Actions at step for edit traverse curate modules
State summary at step t: (q, Gt, Pt, b,) Remaining budget vector step
bi
(Bedger Blas Book)
Episode budget vector for edge growth, latency (steps), and selected tokens
C
(Cadges Clat, Crok)
Cumulative costs (accepted edits interaction steps / selected tokens)
(k)
Instantaneous cost increment at step t for k E (edge, lat, tok);
E. =C
= (Madge: Ata Avak) Race (T), p000 rt.
Lagrange multipliers (prices) for edge/step/token costs Episode-level task reward, per-step (unshaped) task reward, and shaped
return ry r Σ. Às c
f(T, A) Quick Qudge Qlat, Qtok A. AiAi i {B.
Lagrangian objective E[ Race X C(T)] ] for the CMDP
Centralized-critee vaiuuevalues (task head and three cost heads)
Counterfactual advantage for agent and head h; setrragiin--hhappeee
advantage for PPO
D
Ordered, curated evidence list passed to the reader Token count operator for textual unit KG edge (triple) with head entity u, relation r, tail entity v Frontier-adjacent candidate edges considered by the Architect at step Fused atge-utility score used by the Architect for edit decisions Hop cap; average local branching factor; candidate pool size; selected list length (K dynamic)
tok(.) (u,r,v)
geand
s(e Lg. G1)
H, d, (Pel, K
18

---

Published as a conference paper at ICLR 2026
C ALGORITHM
Algorithm CLAUSE:
Training with a constrained centralized-critic PPO (LC-MAPPO)
Input: dataset D of (question, answer) pairs; budgets [Boogo Slat Book J: learning rates.
2: Initialize: actor params for EDIT/TRAVERSS/CUR...
(f 0r, 0s): centralized critic & with multi-head outputs {Qaskk Qodge, Q Q J: duals À = { {Aedges Atat A 2 O. epoch 1..... E
3: Rollout. Sample a minibatch B D. For each question q B:
4: Reset Go, Fo, Po. budgets bn. buffer + Ø; 1-0. -ERMINNL and Tmaxx
5: af ~ 8:); apply edit (add/delete/stop) to G₁ accrue C odge
6: af ~Tr( ( se): continue STOP exploration; accrue c!at.
7:
af ~Ts(( se); curate context or STOP; accrue ct
T: update state S441 1+ 9: Produce answer ij; compute terminal task reward yd finalize episode T.
8:
Log (st, ar, log Te,
Critic update. Compute targets with GAE/TD for each head using T: update (task & cost heads).
II: Advantages. Form shaped rewards - Aedge odge Aaac Auae compute GAE; for each agent iE (B, S), compute counterfactual advantages
A,(st, ar) = ( (st, ax) Ra; [Quak (8t, (a d())]
12: Actor update. Apply PPO to (0n, 0r, 0s) with clipped ratios, entropy bonus, and using the agent-specific A;- 13: Dual update. For each E {edge, lat, tok}:
A + [Ax + ( ([E[Cc] Bba]]
Algorithm 2 Budgeted Inference (CLAUSE, decentralized execution)
1: Input: question g: global budgets 3 [Pddee Pias Book ); trained agents Th (Subgraph Architect), Ty (Path Navigator). Ty (Context Curator).
2: Initialize Go Ø; frontier Fo anchors(4): pool Po counters c=0, 6=0, 7 E < Am
and not STOPPED
3: a BB~ q, B. (Add//ellet//Stop edits)
4: Apply a update Gr, Fú; t sete-eeedc__ooooeeeeee
Bedge break
5: a" ~ G'~TT((-
B-saeee [Next hop or STOP)
6: Apply a": update traversal traces: push touched edges/nodes into candidate pool Pt
7: a ~T q,
(Select or STOP)
8: Update selected set D and token mass T; if > Buk then prune last add or force STOP
9: L-(+1
10: return reader answer ÿ f- Reader(q, D*) and the trace (G*, paths, D*)
Algorithm 3 Counterfactual Advantage (per head) with Centralized Critic
1: Given: critic heads (Q*) > for h [task, edge, lat, tok); joint action a;; per-agent agents {T)) agent E {B, T, S} head
2: Jil (st, a, f E Ea, (11 (as, a,
3: AAth + Q² (* at) bith (56 a,
4: Lagrangian advantage: A l.las + A.taekk A Lodge -MacA
Arok Aftoo
5: return lRR
19

---

Published as a conference paper at ICLR 2026
Algorithm 4 Context Curator (list-wise, dynamic K) one pass
1: Input: question g, candidate pool with token counts tok(-), budget Boo
2: Initialize D + (), peed_ttkens! T +- 0, remaining R+ P R + Ø
3: Score all d R with list-wise scorer s(d q. R. D*)
4: d' arg maXdeR s(d) T + tok(d*) > Piok break
5: Append d' to
+ tok(d*) ); R \ {d"}
6: With probability (STOP q, R, D 33 usaaee do break
7: return D
20

---

Published as a conference paper at ICLR 2026
D IMPLEMENTATION DETAILS & SUPPLEMENTARY EXPERIMENT
Hardware. All experiments are run on a single NVIDIA L20 (48 GB) GPU with 20 vCPU Intel Xeon Platinum 8457C, 100 GB RAM, and two SSD partitions (system: 128 GB; data: 1024 GB). The OS image is Ubunt 22. 04 with Miniconda (Python 3 3.10).
Software & API. We use PyTorch (CUDA 11.8 build). Retrieval does not use a generative LLM: we produce dense embeddings with sentence-trassfrmeee (thenlper petplperrgtteeeaaaae
and perform lightweight NER with spaCy; sparse recall uses BM25. Vectors are L2-normalized and queried with FAISS I IndexFl aedexFllate a (cosine-equivalent) Unless stated otherwise, the shared reader LLM for all RAG/agent baselines is 3wen 32B.. We also evaluate GPT-OSS-1200 and LLaMA3 3-70B for ablations/cooppriions and final answer generation, invoked via SiliconFlow / Groq APIs. Token budgets and token counting always use the reader's 's tokenizer.
Datasets & Knowledge Graphs (KGs). We test CLAUSE on three large-scale, real-world, noisy KGs, and provide construction details. We not share a single KG across datasets; each bench- mark uses its own canonical KG (Table 7). Our graphs movie/entertaineen--ommee
cross-domain: METAQA relies KB, HOTPOTQA uses a Wikidata-deriver subgraph built from general encyclopedic entities, and FACTKG is grounded in the DBpedia open-domain fact graph. Anchoring links surface mentions to KG entities via NER and an alias dictionary; ties or unresolved mentions fall back to dense nearest neighbors in the alias embedding space. For HOTPOTQA, we first run entity recognition and alias matching over the questions and supporting paragraphs, link mentions to Wikidata entities, and then extract local neighborhood (within fixed hop radius) for these entities from a frozen Wikidata dump, yielding a subgraph with roughly millions of nodes and tens of millions of edges. Table 7 we report the scale of this subgraph using O(10)) notation because the exact node/edge counts can vary slightly with the chosen Wikidata version and neighborhood radius, while the order of magnitude sufficient to convey that the setting is web-scale.
Table 7: Benchmarks and knowledge graphs. We report the KG identity, scale, and the exact anchoring protocol. All RAG/agent baselines share the same reader and tokenizer.
Benchmark
KG source
#Nodes
#Edges
#Relations
METAQA (1/2/3-hop)
Zhang et al.
2018
1.3 10
1.35 x 10
HotpotQA (distractor)
Yang el al.
2018
0(10%)
O(10²)
O(10*)
FACTKG
Kim 2023)
4x 106
1 10
10
Default inference settings. Unless stated otherwise, we adopt the following default configuration: the token budget is set to Buo = 512; the reranker runs for 15 steps with minimum of Kmin 2 picks; the traversal is capped at 4 hops (with an earlier stop if the learned stopping policy fires); and the curator operates on candidate pool of size 128 with a dense-fallback pool of 64 candidates.
Supplementary experiments with alternative LLM backbones. We further report results when using two alternative reader LLM backbones, LLLMAA333-78 and GPT-OSS- 20BB for all RAG/aagent baselines and CLAUSE. The detailed numerical results are given in Tables g and 9 Across all three backbones (Qwen3-32B, ALLAMA3.3-70% and GPT-OSS-120B), CLAUSE consistently achieves the best EM on HotpotQA, FactKG, and MetaQA. At the same time, the absolute gap between different backbones becomes much smaller once they are coupled with our budget-aware neuro-symbolic controller: Swen3-32B+CLAUSE backbones, indicating that CLAUSE can largely close the performance gap between medium and large L.LMs while keeping the reader size flexible.
already matches or nearly matches the performance of larger
21

---

Published as a conference paper at ICLR 2026
Table 8: Main QA results: HM@1 HotpotQA, FactKG, and MetaQA using LLaMA3.3-70B.
Family
Method
HotpotQA (Distractor)
FactKG
MetaQA
1-hop
2-hop
3-hop
Vamilla RAG
63.8
78.3
62.0
38.6
45.4
RAG-based
Hybrid RAG
82.0
64.3
43.0
45.8
(LLaMA3.3-70B)
Lig
48.6
68.2
59.6
36.8
45.0
GraphRAG
51.4
73.4
65.0
49.5
50.3
ReAct
65.0
79.5
83.0
53.3
50.6
Agent-based
Traph-of-Thought
60.3
75.2
81.0
49.0
47.6
(LLaMA3.3-70B)
AutoGen
65.2
77.3
86.2
56.5
55.1
KG-Agent
69.3
83.3
88.0
78.8
76.3
Ours
CLAUSE
73.5
85.0
92.7
87.7
87.2
Table 9: Main QA results: EM@1 HotpotQA, FactKG, and MetaQA using GPT-OSS-1200
Family
Method
HotpotQA (Distractor)
FactKG
MctaQA
1-hop
2-hop
3-hop
Vanilla RAG
65.9
79.2
64.8
44.9
52.5
RAG-based (GPT-OSS-120B)
Hybrid RAG
68.9
67.0
49.2
52.8
LightRAG
50.7
69.2
62.9
43.0
52.4
GraphRAG
53,5
74.3
67.8
55.6
54.3
ReAct
65.5
80.6
84.1
65.5
53.5
Agent-based
Graph-of- Thoughtss
61.0
76.0
81.7
49.3
52.6
(GPT-OSS-120) 120B)
AutoGen
66.6
78.3
87.0
66.0
55.8
KG-Agent
69.8
84.2
88.9
79.4
76,9
Ours
CLAUSE
75.0
85.8
92.2
88.0
87.5
E COMPLEXITY ANALYSIS
E.1 TIME COMPLEXITY
Let V*i, | be the sizes the constructed subgraph, b the average out-degree on active frontiers, // the hop cap, P the candidate-pool size, K the selected context length (dynamic), and d the embedding width of light encoders.
Subgraph Architect (anchoring & edit). Each edit round ranks at most C3 candidate edges (retrieval local expansion). With precomputed entity/relation embeddings and cached neighbor lists, scoring is O(Cæd); applying batched edits is O(AE) where AE is the number of accepted edits. Over T3 rounds,
Tedat O(TB CBd + Σ S OBBa Cgd + Bodge)
Path Navigator (traverse), At each hop, neighborhood scoring is O(bd) (or O(deg()) with simple degree-basee based features). For Tr < hops and small beam Bveam:
T Tinverse O Bream bd) S O bd).
Context Curator (curate). A single- pass pointer/list-wise scorer over P items costs O(Pd) per step; selecting K items without replacement:
Teuntt
O(K Pd) (naive), O(Pd+ K Klgg P)
(with heap/top-K)
Given token budget Boo and average item length F, K < BuokEE.
Reader call. The reader sees only the curated K items with token mass I Book Reader runtime is thus O(3ax) (with fixed decoder).
Training cost (LC-MAPPO). #heads 4 (task/edge/lat/tok)) The critic's forward/backwwar per update is O(MSd #heads); actor updates add (MMS) across the three agents. Because costs are attributed at source, the critic's label construction is linear in S with negligible overhead.
Let be steps per trajectory, M mini-batch size of trajectories, and
22

---

Published as a conference paper at ICLR 2026
E.2 SPACE COMPLEXITY
The dominant terms are (i) subgraph cache O([V* + (E*)), (ii) candidate pool O(P), and (iii) re- play/rollout buffers (MS) during training. Budgets bound [E*] and S by Pedge and Btat respectively.
End-to-end bound under budgets.
With explicit budgets,
TendZend = OOin + Bedge) + ((Qmmbi)
+ O(Pd+ + log + (
odit
traverse
curate
reader
so latency scales linearly in Baa and Book: allowing direct runtime control.
23

---

Published as a conference paper at ICLR 2026
F TRAINING COST AND SCALABILITY TO LARGE AND NOISY KGS
Let m=3 agents (Architect, Navigator, Curator), Hhead= batch (M, and width d. One update decomposes
Tupdate = Tenv (M, Tactor (M, Tectti (M, S) Tilccache.
Teny scales with edge scoring and neighbor expansions (counts Σ, CB and Σ. bt), alias ANN fallbacks, and accepted edits Cedge. Tactor covers MS forward passes per agent with candidate sizes (CB, b, P); Terii uses MS samples with heads and GAE horizon; Tiocache captures FAISS lookups and adjacency fetches. The three-agent CTDE design does not triple cost: encoders are shared for representation reuse across settings (small per-agent MLP heads) (Zhou) (025), action sets are typed and small (Architect: CB < E Navigator: b; Curator: pruned P), and a single centralized critic has Haeads heads. Thus, constants grow with and Hheads while dependence remains linear in and tokens. A per-episode spend model is
Cost R Csym Cpm Sedge + Bmud + Pd + log P) + CLLM Sink
with Boc fixed/small and the symbolic term linear in the budgets, yielding bounded and predictable cost.
For memory and indexing, entity/alias embeddings and FAISS live on CPU; GPU holds the active subgraph G2 and batched activations:
RAM x O(VI d) + O(FAISS) + O(IV"++|E* + ((MS).
Product quantization or 8-bit embeddings reduce ANN footprint by 88. For large KGs, frontier- ization and budgeted pricing make per-step work depend on local branching (b) and (Sedge. Slat Box) rather than |E| we use IVF+HNSW or IVF+PQ for alias lookup, degree/type-aware neighbor sam- pling to cap Cn and b, partitioned/frontier caches, and hub pricing via a degree prior in s(e G.). Noise mitigated via price-aware acceptance s(e) - Cddg: listwise de-duplication, and type/logic constraints. For reproducibility. report per epoch: (M, and total env steps; feasible rate under (Bedge: Btats (rok); seconds/update split (env/actor/critic/OOO)) averages of CB. b, P. K; FAISS ms/query and cache hit rate; peak CPU/GPU RAM; index size; and average reader tokens.
24

---

Published as a conference paper at ICLR 2026
G TRADE-OFF ANALYSIS
G.1 LAGRANGIAN SHAPING: COSTS AS PRICES, DUALS AS SHADOW VALUES
D max, [T) s.t. [[Cx(T)) 3k, ke (edge, lat, tok). Ex (((Ck=BB))) and the actor updates optimize the shaped return R' Race >x C2 (Eq. while dual ascent updates À to enforce the constraints.
Recall the constrained objective (Eq.
The Lagrangian is [T,, X) E Race
Proposition (Shadow-priy interpretation). Let (3) be the optimal value of the CMDP as function of the budgel vector B. Under standard regularity, the optimal duals X satisfy the envelope (8)
property 03g = Xz. Hence, X is the marginal EM gain per unit relaxation of budget l. (edge,
latency, or lokens).
Sketch. This is a standard consequence of the envelope theorem for convex CMDPs and KKT conditions (Appendix H
Practical reading. Asa quantifies the EM increase obtainable by allowing one more interaction step on average; Aok quantifies EM gain per additional token; Xedge quantifies the benefit of expanding the subgraph. Increasing any A acts like raising the price of that resource, biasing policies toward using less of it.
25

---

Published as a conference paper at ICLR 2026
H PROOF OF CONVERGENCE OF LC-MAPPO
This appendix states conditions under which the proposed LC-MAPPO converges to a stationary point of the CMDP Lagrangian and satisfies the KKT conditions. We follow the two/tree-time-scale view in the assumptions (A1)-(A6); the centralized critic tracks action-values (fast), the actor ascends the (penalized) objective (medium), and the dual variables perform projected ascent on constraint violation (slow).
H.1 ASSUMPTIONS
A1 (Bounded Rewards and Costs). There exists C, 0 such that
|r(s,a)) S Cr. [c+(s, S Cr. V(s,a), k.
Thus (0) and Je, (0) are finite and admit stochastic gradients with bounded second moments. A2 (Smoothness). For any fixed dual vector X, the penalized objective
F(0: A) = J,(() Σ
A1 (Ja (0) Bbx)
is smooth in 0:
[VF((0;)) VoF(O'; LF 0'1]-
A3 (Asymptotic Unhiasedness). The stochastic policy gradient estimator ÿ. satisfies
9r FiJ = V F(0r A) +
St. Et -000
A4 (Bounded Variance). There exists C > such that
Ellgel| 1 Cgz
Vt.
A5 (Step-Size and Time-Scale Separation). The actor step-size {ar} satisfies
Σ at 00,
a < 00.
The dual step-size Pt is slower, i.., Pe < ar. All stochastic gradients admit bounded second moments.
A6 (Small Trust-Region Bias), Let 0c+1 0 be the ideal gradient step. The actual PPO/COMA update 4,+1 satisfies
[F(0+11A) F(O++1)2) S Csaz-
H.2 PRIMAL (ACTOR) CONVERGENCE FOR FIXED DUALS
Fix À and define the penalized objective L(O, A) = JR(0) - Ee dn (Jor (0) - -Bx), and its minimiza- tion surrogate
F(0; A) - 2),
Assume F(;:)) X) is Læ-smooth in 0 (from (A2) and bounded rewards/costs (A1)). Denote by g: FoF X) the exact gradient and by 9i the PPOIGAE/COMA-basse stochastic gradient used by LC-MAPPO. The actor step is
O 0, a4 9t.
with {az} satisfying (A5). Let the ideal step be 0,41 & 0, ai gt. By the Lg smoothessss (second-
order Taylor bound),
F(B(+1:2) S F(F(41;)) + (0t+1 - Pe42, VF(041))) + 2 11014 - 0. (5)
26

---

Published as a conference paper at ICLR 2026
Taking expectations conditioned the filtration Fi (all randomness up to t) and using the surrogate's (asymptotic) unbiasedness and small-trust-region bias (A6),
Le E |10++1 - 00t2ll Fi
E E[F(0 A)
Fi - E F(O X)
Fi
+
2
Le a [
F F(0 A) +
9ol1² Fi].
(6)
2
where (a) uses 0c+1 - 0e+1 = - -0 Gg. - ge) and Elee [ = e with | & CTRE + cQ
capturing trust-region and critic-tracking biases (constants from (A3).(A6)). Next, smoothness around 0, gives
F(0++1;A) - 2(0;; + (Pe-1 0s VF(0;;)) + Le 10 0el1? 2
which, using θe①1 0, -ostts yields
Le
A(O++1;A) & F(O,; A) - avllgel
2
2 a991.111?
(8)
Combining Eq. and Eq. and taking the total expectation,
La of IE [19h11]]
Lo
B[F(0++1:A) - (0,; A) v -0, E [119
[|] +
+
[ - gella]
2
02 E 19 + C. at + C2 C2a2 (022(22))0 (DD + 88)
S -
(9)
for bounded second moments (A5) and small enough or so that Le oz t and using E. at
1.2 Summing Eq. over
00, Σ, az (A5), Robbins-Siegmund implies
04 E [1lgd] ?] < 0o =
lim inf V = O. 1
(10)
1=0
Hence any limit point (A) stationary for F(; A), equivalently stationary for L(,A))
H.3
DUAL (MULTIPLIER) CONVERGENCE AND KKT
The dual update is
AR,++1 = [Ae. + Pe (0.) Bc)
(11)
with A satisfying (A5) and A a4 (actor faster than duals). On the slower time scale, the actor tracks 8 (A,) from Part A, so the dual recursion behaves as a projected gradient ascent on the concave dual function D(A) maxę L(,, A). Standard swo-time-scale results then yield convergence of {Ae] to the dual-optimal set A and primal feasibility:
lim (Jc, - Bx)+ = 0, 1-00
lim dist = O. t-000
(12)
Finally, any limit point (0', X²) satisfies the KKT conditions of the CMDP:
VoL(0" Xt) 0, Jc, (0") S BR, 200, O, (ao, (0*) B&) 0, Vk.
(13)
H.4 PROOF TEMPLATE MIRRORING A SMOOTIINES STEP
For completeness, we restate the key inequality in the style of the referenced lemma. Let be as in Eq. 9: = VF(0;; A), and define 0.+1 = 0, - a4g: and 0.+1 = 0z - arg.. By smoooohhssss
F(0.41)= I F ((0+11) + (0r+1 0.+1, VF(0.+1)) + La 110 11.1
(14)
Taking expectations and using E[G. Fi] = + Ec,
E[F(O++1) < E F(O++1) +
Lo at E 11 - -3
(15)
2
Also,
0,, F(O.+1) < F(0:) - VF(0))) 10 0,112 - 1= La a 11 (16)
Combining Eqs. 15 16 and adding/subtraatiing & as in Eq. gives
EF E[F(0.)] V -a, [[l9 || 2 a E |199 [|]]
o
E
[10
ge 11
(17)
which is the MC-MAPPO analogue of the inequality chain in Eqs. summability of (of) and viottim--ccale analysis for {}e).
14 the rest follows by
27


Reviews:
[{"review_id": "YlsyRIkyn4", "reviewer": "Reviewer_2uqG", "summary": "This paper introduces CLAUSE, a novel multi-agent, neuro-symbolic framework for multi-hop Knowledge Graph Question Answering (KGQA). The core contribution is transforming the context-building process as a constrained sequential decision problem. The framework therefore uses three agents (Subgraph Architect, Path Navigator, and Context Curator) and jointly optimize them. Within this process, the cost is explicitly expressed by the Lagrangian-constrained. Experiments on HotpotQA, MetaQA, and FactKG show that CLAUSE outperforms strong RAG and agent-based baselines in accuracy.", "questions": "See weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe idea of creating three agents(Subgraph Architect, Path Navigator, and Context Curator) is intuitive and easy to follow. The paper explains its motivations and methods clearly.\n2.\tThe CLAUSE is interpretable as it is a neural symbolic framework and every step is explicit.\n3.\tThe methodology has very sound theoretical guarantees and the paper has provided the full proof of its convergence. \n4.\tThe empirical results are extensive and impressive as it outperforms all baselines in accuracy while maintaining good efficiency at the same time.", "weaknesses": "1.\tThe methodology part is filled with notations with some not very clearly explained. For example, what does $C_t$ stands for is not explained when it’s firstly introduced in this paper in the top of the 4th page. I strongly suggest that the author to take notice of whether the notation has been explained carefully.\n2.\tThe experiment part is solely conducted with Qwen3-32B, I wonder whether the author has tried as LLM?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kvqC7A6Ix0", "reviewer": "Reviewer_L2iz", "summary": "The paper presents CLAUSE, a neuro-symbolic three-agent framework for efficient multi-hop question answering over knowledge graphs. Unlike static k-hop expansion or overlong prompting, CLAUSE formulates context construction as a sequential decision process, dynamically determining which subgraphs to expand, paths to explore, and evidence to retain under user-specified latency and cost budgets. Powered by the proposed Lagrangian-Constrained Multi-Agent PPO (LC-MAPPO) algorithm, three coordinated agents—Subgraph Architect, Path Navigator, and Context Curator—jointly optimize subgraph growth, reasoning efficiency, and evidence selection. Experiments on HotpotQA, MetaQA, and FactKG show that CLAUSE significantly improves accuracy and efficiency, achieving +39.3 EM@1, 18.6% lower latency, and 40.9% reduced edge growth over GraphRAG, while preserving provenance and ensuring predictable, deployment-friendly performance.", "questions": "Please refer to the weakness part.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The paper proposes CLAUSE, a neuro-symbolic multi-agent framework that dynamically balances accuracy, latency, and cost through user-specified budgets—enabling per-query adaptation without retraining.\n- The authors introduce the Lagrangian-Constrained Multi-Agent PPO (LC-MAPPO) algorithm to jointly optimize subgraph construction, reasoning path navigation, and evidence selection in a unified decision process.\n- The prposed method achieves substantial gains in accuracy (+39.3 EM@1 on MetaQA-2-hop) while reducing latency and subgraph growth, producing compact, provenance-", "weaknesses": "- The contribution in section 1 is somewhat overclaimed. It is suggested to merge the points to highlight the key contribution of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SRA76imhkO", "reviewer": "Reviewer_aDuz", "summary": "This paper proposes  CLAUSE, an agentic three-agent neuro-symbolic framework that treats context construction as a sequential decision process over knowledge graphs, deciding what to expand, which paths to follow or backtrack, what evidence to keep and when to stop. The three agents include subgraph architecture, path navigator and context curator. These agents are trained jointly with Lagrangian Constrained Multi-Agent Proximal Policy Optimization, so that subgraph construction, reasoning paths discovery, and evidence selection are jointly optimized under per-query’s resource budgets on edge edits, interaction steps, and selected tokens", "questions": "How would CLAUSE handle large and real world noisy knowledge graph and if it fails what would be the next step", "limitations": "", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper has novel approach of formulating knowledge graph questions answering (KGQA) as a learnable context construction. CLAUSE demonstrates strong empirical results and achieves the best accuracy on all datasets and hops (71.7 on HotpotQA, 84.2 on FactKG, and 91.0/87.3/85.5 on MetaQA 1/2/3-hop), surpassing both RAG baselines (e.g., HybridRAG 66.0 on HotpotQA) and agent baselines (e.g., KG-Agent 68.7 on HotpotQA, 87.3/78.0/75.4 on MetaQA) maintaining an impressive efficiency.", "weaknesses": "The system involves three agents and MARL training pipeline which may potentially increase the computational complexity. Additional discussion on training cost may be helpful. The framework needs to be tested at scale on large and real world noisy knowledge graph.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ulFkRqilg9", "reviewer": "Reviewer_Aqnr", "summary": "The authors propose a method for question answering (QA) based on retrieval from a knowledge graph. In contrast with heuristics for KG retrieval based on k-hop neighborhoods and their expansion, the authors frame the problem as a constrained reinforcement learning task with tree cost objectives based on minimizing subgraph selection, neighborhood expansion, and token usage. Experiments show that the approach is accurate, while effectively optimizing for their proposed three-way cost.", "questions": "1. Can you please provide a more descriptive definition of the KG, the question q, and the question-conditioned subgraph that does not leave symbols undefined?\n2. What is \"frontierized\" subgraph? What are frontierized candidates?\n3. What is the architecture of the subgraph architect, path navigator, and context curator?\n4. Can you please expand on important experimental details (see W7).", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. The problem is well-motivated: many existing approaches for RAG over KGs are based on heuristics that can result in high costs when applied uniformly for all questions. Optimizing this step is therefore a task is likely to positively impact the cost of deploying such methods.\n2. The work is well-positioned with respect to prior work, ranging from QA over KGs to specific reinforcement learning methods.\n3. The formulation of the problem seems well-motivated, as it frames question answering as a constrained RL problem with QA accuracy as the reward, and constraints related to retrieval cost\n4. The experiments are comprehensive, considering a broad range of baselines, and more importantly, evaluating the methods on the axes of accuracy, latency, and edge budget. In most cases (except latency) they demonstrate the effectiveness of the method.", "weaknesses": "The paper mostly suffers from exposition issues that make it difficult to assess important parts of the paper that are needed to judge its impact and soundness.\n\n1. The contributions (L075) are mostly a description of the proposed method, rather than a description of what the fundamental problem being solved is, how the proposed method differs fundamentally from prior work, and its advantages over prior work. A similar issue appears in the related work section (L130) which seems like a brief survey of different RL methods that is not positioned in the context of the paper.\n2. The problem definition (L159) is imprecise: a knowledge graph is K = (V, R, E), but what are V, R, and E? Similarly a question q is defined. Are there any assumptions on q, e.g. it is always a question that seeks to retrieve an entity from the KG? Is it assumed to be already parsed such that mentions of relations and entities are linked to specific ones in the KG? Or is there an intermediate model that takes care of this? L227 seems to suggest both (\"Anchored by entity/alias mentions in q (with a lightweight dense-retrieval fallback)\"), while still leaving many crucial details out.\n3. The question conditioned subgraph is $G_t = (V_t,E_t)$, now a tuple with two elements (rather than three, as the KG is defined). Does this mean that $G_t$ drop relational information? Furthermore, $\\mathcal{F}_t$ is introduced as a \"traversal frontier\". It is not clear what this means (why traversal? why frontier?). If part of the state is $G_t$, which already contains $V_t$, why does $\\mathcal{F}_t\\subseteq V_t$ need to be made a separate part of the state? Lastly, $\\mathcal{C}_t$ is undefined in the definition of the state (L165).\n4. The description of CLAUSE contains gaps. Some are related to the motivation of the approach: the architect maintains a \"frontierized subgraph\" yet it is not clear what \"frontierized\" is, and what \"frontier candidates\" are. More importantly, while it is clear that there are three agents, each with a specific goal, it is not clear *what* they are. The architect computes question-entity, relation-text matches, etc. but how? Does it rely on neural networks? If so, what is their architecture and their number of parameters? There is a \"light encoder\" in the path navigator, yet it is not clear what it encodes, how, and how light it actually is.\n5. The actual novelty or need of LC-MAPPO is unclear, given that there are several works studying the use of Lagrangian methods in reinforcement learning. Why is LC-MAPPO needed, and what if instead we used one of the existing works in this area?\n6. The EM@1 evaluation metric is unclear. Since it is not known what type of questions the method supports (see weakness 2) it is difficult to infer from context what it actually measures.\n7. Important experimental details are missing: what is the actual shared LLM used for retrieval and reading? And importantly, what is the KG? Is the KG the same for all datasets? What is its scale?\n8. While the experiments are comprehensive, it is not true that CLAUSE is the most effective (as implied by the bolding in Table 2), where LightRAG is actually better.\n9. The proof of convergence (App. G) seems incomplete. It is based on a list of assumptions that does not appear anywhere in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)