betaFeedback

WorksComputer Science

Interactive Structured Environment Scaling for Large Language Model Agentic Reasoning

Abstract

Reinforcement learning via environmental interaction is a cornerstone post-training paradigm for evolving large language models into autonomous agents capable of multi-turn tool use and exploration. Because the environment defines what the policy observes and how actions are verified, its structure directly bounds the capabilities an agent can acquire. Yet existing structured and retrieval environments rely on upstream pre-filtering—extracting a compact subgraph around the gold answer or retrieving fixed passages before the policy acts. We show that such pre-filtering introduces a fundamental measurement confound: because per-question subgraphs enclose ground-truth paths, they compress the candidate space by orders of magnitude and leak answer locations via local topology, allowing a question-blind degree heuristic to surface gold answers far above chance. To restore path selection, candidate pruning, and optimal stopping as genuine policy decisions, we propose RISE (Interactive Structured Environment), which transitions structured reinforcement learning from static subgraphs to full-scale interactive databases along two coupled axes. First, Decision-Space Scaling exposes the unpruned knowledge graph via a five-stage graph-agnostic typed intent adapter under a bounded call budget and a multiplicative grounding reward gate. Second, Learning-Frontier Scaling overcomes within-group variance collapse under group-normalized objectives by uniting model-independent structural tier progression with a self-evolving competence-frontier bandit. Across nineteen benchmarks and three model backbones, RISE substantially advances in-domain and unseen-schema knowledge-graph reasoning, transfers zero-shot to open-domain passage retrieval, and significantly enhances out-of-domain mathematical and logical deduction.

Introduction

Fine-tuning large language models (LLMs) with reinforcement learning (RL) and verifiable feedback has driven a paradigm shift in post-training, eliciting deliberative capabilities such as hypothesis testing, self-reflection, backtracking, and multi-step planning ([26, 19, 29, 15]). By optimizing policies directly against outcome verifiers, RL enables models to internalize reasoning strategies that are difficult to instill through passive imitation alone ([43, 66, 25]). While early breakthroughs centered on symbolic domains such as mathematics, logic, and code generation ([13, 34, 56, 10]), this paradigm is rapidly expanding to interactive agentic settings, empowering LLMs to query search engines, navigate databases, and orchestrate external tools over multi-turn horizons ([61, 41, 27, 69, 33, 39, 58]).

Despite rapid progress in RL optimization algorithms ([42, 43, 24, 65, 68]), the foundational role of the training environment itself has been comparatively overlooked ([16, 64]). In interactive RL, the environment governs what the policy observes, which actions are admissible, and when an episode terminates, directly bounding what decision-making capabilities a policy can acquire (see Appendix A for a detailed review of related work). Existing environments face a persistent trade-off across these dimensions. Internalized-rule environments (e.g., mathematics and code) provide clean verifiability, but rely on costly expert annotations and do not train agents to gather missing evidence under partial observability [21, 34]. Conversely, externalized-rule game and embodied environments support multi-turn exploration [6, 50, 54, 67], yet the learned skills often overfit to specialized mechanics and fail to transfer to general reasoning. Large-scale structured knowledge bases offer an ideal foundation to bridge this gap [14, 4, 32, 63 b] (Wang et al. 2025): their expansive schemas support automated scaling, their multi-hop paths mirror compositional deduction, and their explicit facts enable exact rule-based verification.

However, for a structured environment to genuinely incentivize transferable agentic search and reasoning rather than localized reading comprehension, it must simultaneously satisfy three core criteria (formalized in Appendix § 8): (1) Open Decision Space, where sequential path selection, candidate pruning, and optimal stopping governance remain open decisions for the policy; (2) Tool-Agnostic Action Interface, where query formulation is decoupled from backend-specific query syntax so that learned search habits transfer across heterogeneous tools; and (3) Active Learning Frontier, where the training schedule sustains non-zero policy-gradient variance as the decision space scales. Yet existing structured and retrieval environments—whether injecting serialized subgraphs into the prompt [36, 20, 63 b], walking pre-extracted question-specific subgraphs [48, 7, 35, 57], or retrieving fixed top-kk passages [27, 8, 45, 47]—violate the first criterion by design: they pre-filter the candidate space before the policy takes a single step.

Treating such pre-filtered contexts as search environments introduces a severe measurement confound before it imposes any capability ceiling. We quantify this confound on the per-question WebQSP subgraphs released by a widely used RL knowledge-graph agent [35], auditing them exactly as published (Appendix § 8). Three findings stand out. First, the candidate space is compressed by five orders of magnitude, with the median subgraph holding only 4,415 triples over 1,638 entities (2.16×1052.16 \times10^5 times smaller than full Freebase). Second, 94.6% of gold answers reside within two hops of a topic entity (65.5% within one hop), allowing naive breadth-first enumeration to substitute for selective planning. Third, and most critically, because each subgraph is extracted to enclose the ground-truth path, its local connectivity directly leaks the answer’s location: a question-blind heuristic that never reads the question and simply ranks nodes by in-subgraph degree surfaces a gold answer in the top-10 for 33.27% of questions, against 0.19% for a uniform random baseline (Figure 1A). When pre-extracted topology already points at the answer and guarantees reachability by construction (ρ=1\rho= 1), accuracy differences cannot be reliably attributed to a learned search policy.

Figure 1. Motivation and the two scaling axes of RISE. (A) Pre-filtered subgraph environments compress the candidate space by 2.16×105×2.16 \times10^{5}\times and leak answer locations through node degree (33.27% question-blind Hit@10 vs. 0.19% uniform random). (B) Decision-Space Scaling exposes the full 9.5×1089.5 \times10^{8}-triple store through a five-stage graph-agnostic typed intent adapter ΦG\Phi_G under a bounded call budget (Cmax⁡=16C_{\max}=16) and rolling context (28,672 tokens). (C) Learning-Frontier Scaling overcomes the 64% zero-variance bottleneck of full-graph group-normalized RL (G=8G=8) by uniting SPARQL structural tiers 1–4 with the Self-Evolving Curriculum (SEC) bandit (pq≈0.5p_q \approx0.5; see Appendix § 8).

To transform reachability from a construction artifact into a learnable policy outcome, we transition the training environment from static pre-extracted subgraphs to full-scale interactive databases and propose RISE (InteRactIve Structured Environment). As illustrated in Figure 1, RISE scales agentic RL along two coupled dimensions. First, Decision-Space Scaling (Figure 1B) exposes the un-pruned Freebase store (9.5×1089.5 \times10^8 triples, where a model-free breadth-first probe establishes a reachability floor of βBFS≥0.5219\beta_{\mathrm{BFS}} \ge0.5219) under a finite call budget (Cmax⁡=16C_{\max} = 16) and a rolling context window (28,672 tokens), restoring candidate pruning and stopping control as authentic, turn-attributable policy decisions. Rather than binding actions to raw SPARQL syntax [11, 46] or schema-specific primitives [35, 17], RISE interposes a deterministic five-stage graph-aware intent adapter Pg\mathcal{P}_g that executes natural-language queries symmetrically across outgoing and incoming edges (48.6% of candidate relations exist solely as incoming edges), paired with a multiplicative grounding reward gate and an isomorphic protocol cold start (Figure 2). Because the policy interacts strictly through natural-language intents and structured receipts, it transfers zero-shot to unseen schemas, temporal knowledge graphs [12, 17], and unstructured passage retrievers [59], evaluated unconditionally on full official splits.

Figure 2. Overview of the RISE framework. Top: Decision-Space Scaling interposes a five-stage graph-agnostic typed intent adapter ΦG\Phi_{\mathcal{G}} over the full unpruned graph (9.5×1089.5 \times10^{8} triples), translating natural-language <search> intents into bidirectional traversals and structured <information> receipts under a bounded call budget (Cmax⁡=16C_{\max}=16) and rolling context (28,672 tokens). Bottom Left: Stage 1 filters teacher rollouts on a strictly disjoint pool QcoldQ_{\mathrm{cold}} using the exact grounded outcome criterion of the RL reward (Eq. (6)). Bottom Right: Stage 2 performs Learning-Frontier Scaling by coupling observation-masked multi-turn GRPO (Eq. (7)) with the Self-Evolving Curriculum (SEC) bandit across four structural tiers (Eq. (9)).

Second, Learning-Frontier Scaling (Figure 1C) addresses the optimization bottleneck that decision-space enlargement exposes: within-group variance collapse under group-normalized RL [43]. When advantages are standardized across G=8G = 8 rollouts sampled for the same question, any question on which all rollouts earn identical rewards—occurring both when an easy question is already mastered (pq→1p_q \to1) and when full-graph exploration fails completely on a hard or unreachable question (pq→0p_q \to0)—yields zero within-group variance (σ^=0\hat{\sigma} = 0) and contributes zero gradient (Proposition 1; affecting 64% of our training pool). Because zero variance is a per-question property, mixing mastered and unreachable questions in a batch still yields zero gradient even when the batch mean pass rate is 0.5. We resolve this bottleneck across four deterministic structural tiers (d(q)∈{1,2,3,4}d(q) \in\{1,2,3,4\} parsed from gold SPARQL topology) at two levels: macroscopically, progressing from single-hop lookups to multi-constraint compositions aligns training direction with the outward expansion of the policy’s reachable horizon ([2, 30]); microscopically, we adapt the self-evolving curriculum (SEC) scheduler of Chen et al. [9]—in the spirit of prioritized replay and bandit scheduling ([40, 1])—by anchoring its return on the group-level Bernoulli standard deviation 2pq(1−pq)2\sqrt{p_q(1-p_q)} to dynamically concentrate batches on the moving competence frontier (pq≈0.5p_q \approx0.5).

We instantiate RISE on Freebase (Bollacker et al., [4]) and evaluate it across nineteen benchmarks spanning three capability families and three model backbones, making three main contributions:

  • We empirically diagnose the topological leakage confound of pre-filtered subgraph environments (33.27% question-blind Hit@10), and formalize RISE over an unpruned knowledge base so that path selection, candidate pruning, and optimal stopping become turn-attributable decisions.

  • We design a five-stage graph-agnostic typed intent adapter with a multiplicative grounding gate, prove within-group variance collapse under group normalization (Proposition 1), and operationalize Learning-Frontier Scaling by uniting SPARQL structural tiering with an online variance bandit (SEC).

  • Across nineteen benchmarks on Qwen2.5-7B, Qwen2.5-14B, and Llama-3.1-8B, we show that RISE outperforms specialized baselines on in-domain and unseen-schema KG reasoning, transfers zero-shot to passage retrieval above domain-trained models, and generalizes to tool-free mathematical and logical deduction, while isolating the effects of cold start, curriculum direction, and batch composition.

The RISE Framework

This section presents the RISE framework (Figure 2), comprising three components: Decision-Space Scaling, realized by a budgeted interactive POMDP formulation and a five-stage graph-agnostic typed intent adapter (§ 2.1–§ 2.2); a two-stage training pipeline combining a protocolpreserving cold start with observation-masked multi-turn GRPO under a multiplicative grounding gate (§ 2.3); and Learning-Frontier Scaling, realized by structural tier progression and a self-evolving variance bandit derived from group-normalized policy gradients (§ 2.4).

Budgeted Interactive Search over a Structured Environment

Learning to search is learning a sequence of decisions, not learning a query format. An environment carries that signal only if sequential path selection, candidate pruning, and stopping governance are genuinely open: once candidates are pre-enumerated and the answer enclosed upstream, the only task left is local evidence stitching.

We formulate multi-turn question answering over a knowledge graph C=(E,R,T)\mathcal{C}=(\mathcal{E},\mathcal{R},\mathcal{T}) as a budget-constrained Partially Observable Markov Decision Process (POMDP), defined by the tuple M=(Q,H,A,O,ΦG,R,Cmax⁡)\mathcal{M}=(\mathcal{Q},\mathcal{H},\mathcal{A},\mathcal{O},\Phi_{\mathcal{G}},R,C_{\max}). Given an input question q∈Qq \in\mathcal{Q} (accompanied by surface-form topic entities when provided by the benchmark), an episode unfolds over T≤Cmax⁡+1T \leq C_{\max}+1 discrete interaction turns. At turn tt, conditioned on the interaction history ht−1=(z1,a1,o1,…,zt−1,at−1,ot−1)∈Hh_{t-1}=(z_1,a_1,o_1,\ldots,z_{t-1},a_{t-1},o_{t-1}) \in\mathcal{H} (with h0=∅h_0=\emptyset), the policy πθ\pi_\theta first generates an internal reasoning trace ztz_t enclosed in <think>...</think> tags, followed by a discrete action at∈Aa_t \in\mathcal{A}. The action space is the disjoint union A=Asearch∪Aanswer\mathcal{A}=\mathcal{A}_{\mathrm{search}}\cup\mathcal{A}_{\mathrm{answer}}, where at∈Asearcha_t \in\mathcal{A}_{\mathrm{search}} emits a natural-language query inside <search>...</search> and at∈Aanswera_t \in\mathcal{A}_{\mathrm{answer}} emits a final prediction A^(τ)\hat{A}(\tau) inside <answer>...</answer> (with an empty tag denoting explicit abstention).

Whenever at∈Asearcha_t \in\mathcal{A}_{\mathrm{search}}, the environment executes the deterministic adapter ΦG\Phi_{\mathcal{G}} and appends a structured receipt ot=ΦG(at,ht−1)∈Oo_t=\Phi_{\mathcal{G}}(a_t,h_{t-1}) \in\mathcal{O} enclosed in <information>...</information> as a separate user turn, so environmental text never enters the policy’s own generation stream. The probability of a trajectory τ=(z1,a1,o1,…,zT,aT,oT)\tau=(z_1,a_1,o_1,\ldots,z_T,a_T,o_T) factorizes autoregressively over the policy’s own tokens subject to a hard call budget Cmax⁡=16C_{\max}=16, while a rolling window of 28,672 tokens is maintained by left-truncating the oldest turns:

πθ(τ∣q)=∏t=1Tπθ(zt,at∣q,ht−1),subject toC(τ)=∑t=1TI[at∈Asearch]≤Cmax⁡.(1)\pi_\theta(\tau\mid q)=\prod_{t=1}^{T}\pi_\theta(z_t,a_t \mid q,h_{t-1}),\qquad\text{subject to}\qquad C(\tau)=\sum_{t=1}^{T}\mathbb{I}[a_t\in\mathcal{A}_{\mathrm{search}}]\leq C_{\max}. \tag*{(1)}

The two budgets are deliberately orthogonal: the call budget counts external searches and the per-turn limit (2,048 tokens) counts internal reasoning tokens, so a policy can neither buy extra hops by thinking less nor lose hops by thinking more.

When the call budget is exhausted at turn tt, the environment appends a notice to oto_t and grants one final answer-only turn restricted to Aanswer\mathcal{A}_{\mathrm{answer}}, keeping “ran out of search budget” and “failed to emit an answer” strictly separable at evaluation time. The decision process follows the directed interaction flow

q→πθ(z1,a1search)→ΦGo1→πθ⋯→ΦGoT−1→πθ(zT,aTanswer)⟹A^(τ),(2)q \xrightarrow{\pi_\theta} (z_1, a_1^{\mathrm{search}}) \xrightarrow{\Phi_G} o_1 \xrightarrow{\pi_\theta} \cdots\xrightarrow{\Phi_G} o_{T-1} \xrightarrow{\pi_\theta} (z_T, a_T^{\mathrm{answer}}) \Longrightarrow\hat{A}(\tau), \tag*{(2)}

in which every transition through ΦG\Phi_G is an opportunity for the policy to revise its hypothesis or prune unpromising branches rather than follow a pre-extracted path.

Three structural consequences separate this formulation from pre-filtered environments. First, budget-bounded reachability ρ(q;Cmax⁡)\rho(q; C_{\max}) (formalized in Appendix § 8) is identically one by construction inside an answer-enclosed subgraph, whereas over the full graph it becomes an empirical quantity governed by the policy’s own path selections. Second, candidate pruning becomes mandatory, since the policy must select which relation to traverse among all edges incident to an entity. Third, evaluation is conducted unconditionally over full official splits rather than reachable subsets, preserving a fixed denominator across checkpoints.

Graph-Agnostic Typed Intent Adapter and Environment Contract

Section 2.1 defines the sequential decisions a search policy must make, but if the action space directly encodes a database’s native query syntax (such as SPARQL), the decision space becomes bound to that schema and cannot transfer across tools. We therefore restrict the policy’s action vocabulary to natural language plus bracketed entity mentions, placing all schema-specific translation behind a deterministic adapter ΦG\Phi_G so that the exact same policy weights can drive a static knowledge graph, a temporal graph, or a text passage retriever without retraining.

RISE implements this decoupling via a four-layer architecture: (1) a full-scale Virtuoso SPARQL backend hosting Freebase; (2) a deterministic five-stage typed intent adapter ΦG\Phi_G; (3) a strict environment contract governing turn grammar, receipt schemas, and error codes; and (4) a trainer-facing multi-turn conversation interface shared identically between structured graph search and unstructured passage retrieval. Because the top conversation layer is invariant across backends, swapping the adapter is the only change required to evaluate a graph-trained policy on a passage retriever.

Given a search action at=⟨search⟩q~t⟨/search⟩a_t = \langle\texttt{search}\rangle\tilde{q}_t \langle/\texttt{search}\rangle containing query q~t\tilde{q}_t and bracketed mentions [[mt]][[m_t]], the adapter composes five stages, ΦG=Ftrunc∘Frank∘Fexec∘Fintent∘Fres\Phi_G = \mathcal{F}_{\mathrm{trunc}} \circ\mathcal{F}_{\mathrm{rank}} \circ\mathcal{F}_{\mathrm{exec}} \circ\mathcal{F}_{\mathrm{intent}} \circ\mathcal{F}_{\mathrm{res}}:

  1. Entity Resolution (Fres\mathcal{F}_{\mathrm{res}}). Maps each surface form mtm_t to a node et∈Ee_t \in\mathcal{E} through the episode’s entity-binding table, seeded with the benchmark’s topic entities and extended by every previously returned receipt; a form unseen in the table falls back to exact label matching in G\mathcal{G}. Because the table is maintained per episode, homonymous labels are disambiguated by entities the episode has already grounded rather than by a static global prior.

  1. Intent Classification (Fintent\mathcal{F}_{\mathrm{intent}}). Maps q~t\tilde{q}_t to one of three closed-vocabulary structural tags, ιt∈{relation_hop,relation_list,entity_info}\iota_t \in\{\texttt{relation\_hop}, \texttt{relation\_list}, \texttt{entity\_info}\}, via deterministic surface cues (returning relational triples, deduplicated incident relation names, or entity descriptions and types).

  1. Direction-Symmetric Execution (Fexec\mathcal{F}_{\mathrm{exec}}). Auditing Freebase reveals that 48.6% of candidate relations around topic entities exist only as incoming edges (Appendix § 8). An adapter that traversed outgoing edges alone would list such a relation during inspection and return empty results when queried, penalizing a valid reasoning step. Execution therefore retrieves the bidirectional one-hop neighborhood of ete_t, inverting incoming edges into canonical ete_t-centric candidates:

Fexec(et)={(et,r,e′)∣(et,r,e′)∈T}∪{(et,r−1,e′)∣(e′,r,et)∈T}.(3)\mathcal{F}_{\mathrm{exec}}(e_t) = \{(e_t,r,e') \mid(e_t,r,e') \in\mathcal{T}\} \cup\{(e_t,r^{-1},e') \mid(e',r,e_t) \in\mathcal{T}\}. \tag*{(3)}
  1. Semantic Ranking (Frank\mathcal{F}_{\mathrm{rank}}). Scores candidate triples in Fexec(et)\mathcal{F}_{\mathrm{exec}}(e_t) by dense cosine similarity (E5-base-v2) against q~t\tilde{q}_t and retains those above a fixed similarity threshold, falling back to the entity’s relation list when none qualifies.

  1. Bounded Truncation and Receipt Formatting (FtruncF_{\mathrm{trunc}}). Emits the top kk of NN matching rows behind an explicit Results (k of N) header—keeping “fact does not exist” (N=0N = 0) distinguishable from “fact truncated by row cap” (k<Nk < N)—and closes with Calls remaining, capping rows at k=100k = 100 and relations at 50 (Appendix § 11).

Three contract rules guarantee that training and evaluation share identical environment semantics. First, the call budget Cmax⁡C_{\max} is accounted independently of the per-turn generation limit (2,048 tokens). Second, all execution anomalies map to a closed seven-element error vocabulary—E_NO_ENTITY, E_ENTITY_NOT_FOUND, E_INTENT_UNSUPPORTED, E_NO_RESULTS, E_QUERY_FAILED, E_BUDGET_EXCEEDED, and E_MALFORMED (Appendix § 9)—where transient backend timeouts (E_QUERY_FAILED) are never penalized as policy errors. Third, observation independence holds end to end: cold-start collection, on-policy GRPO rollouts, and benchmark evaluation invoke the exact same adapter binary and receipt template.

Grounded Outcome Verification and Two-Stage Training

Both training stages ask the same question of a trajectory—did it reach a correct answer via evidence the environment can vouch for—preventing the RL phase from having to unlearn shortcuts accepted during warm-up.

Grounded Outcome Verification. Rewarding a completed trajectory τ\tau with predicted answer A^(τ)\hat{A}(\tau) against ground truth A∗(q)A^*(q) combines a gated outcome term with an additive format term:

r(τ)=g(τ)⋅I[[A^(τ)]=[A∗(q)]]+φ(τ),(4)r(\tau) = g(\tau) \cdot\mathbb{I}\left[\left[\hat{A}(\tau)\right] = \left[A^*(q)\right]\right] + \varphi(\tau), \tag*{(4)}

where [⋅]\left[\cdot\right] normalizes aliases and whitespace at set level, φ(τ)∈{1.0,0.8,0.2,0.1,0.0}\varphi(\tau) \in\{1.0, 0.8, 0.2, 0.1, 0.0\} is the five-tier structural format score of Search-R1 [27], and g(τ)∈{0,1}g(\tau) \in\{0, 1\} is a multiplicative grounding gate requiring every predicted entity to appear in a receipt retrieved during the episode:

g(τ)=I[∀a^∈[A^(τ)], a^∈⋃t=1T−1[E(ot)]].(5)g(\tau) = \mathbb{I}\left[\forall\hat{a} \in\left[\hat{A}(\tau)\right],\ \hat{a} \in\bigcup_{t=1}^{T-1}\left[\mathcal{E}(o_t)\right]\right]. \tag*{(5)}

The structural asymmetry between a multiplicative gate g(τ)g(\tau) and an additive format term φ(τ)\varphi(\tau) is deliberate. Grounding must be multiplicative because an ungrounded correct answer on an unreachable question is a parametric guess, and rewarding it incentivizes the policy to bypass search and enumerate plausible entities instead. Format compliance, by contrast, must be additive: a multiplicative format gate would zero out the gradient whenever the final answer is wrong, depriving the policy of syntactic feedback during early exploration when accuracy is low and degenerate repetition loops ([23]) must be suppressed. Intermediate process rewards are excluded because under within-question group normalization, a bonus for visiting an intermediate hop alters the advantage scale asymmetrically across question difficulties.

Protocol-Preserving Cold Start. All training questions originate from the combined official training splits of WebQSP and CWQ (34,215 questions in total), which we partition via stratified sampling by dataset and difficulty tier into two strictly disjoint pools: a cold-start pool Qcold\mathcal{Q}_{\mathrm{cold}} of 6,000 questions and an online RL pool QRL\mathcal{Q}_{\mathrm{RL}} of 28,215 questions (enforced by a run-level split flag). Stage 1 fine-tunes the base model exclusively on teacher trajectories collected using the same RISE server over Qcold\mathcal{Q}_{\mathrm{cold}}. Using Gemini-2.5-pro at temperature 0.7 with at most two attempts per question, 4,006 questions (66.8%) yielded trajectories passing our two filtering invariants, giving ∣DSFT∣=4,006|\mathcal{D}_{\mathrm{SFT}}| = 4,006: (1) reward-criterion isomorphism, requiring g(τ)⋅I[[A^(τ)]=[A∗(q)]]=1g(\tau)\cdot\mathbb{I}\left[\left[\hat{A}(\tau)\right] = \left[A^*(q)\right]\right] = 1 and φ(τ)=1.0\varphi(\tau) = 1.0; and (2) per-turn reasoning completeness, requiring a non-empty <think> block (zt≠∅z_t \ne\varnothing) at every turn:

DSFT={(q,τ)∣q∈Qcold, τ∼πteacher(⋅∣q),\mathcal{D}_{\mathrm{SFT}} = \{(q,\tau)\mid q \in\mathcal{Q}_{\mathrm{cold}},\ \tau\sim\pi_{\mathrm{teacher}}(\cdot\mid q),
g(τ)⋅I[[A^(τ)]=[A∗(q)]]=1, φ(τ)=1.0, ∏t=1TI[zt≠∅]=1}.(6)g(\tau)\cdot\mathbb{I}[[\hat{A}(\tau)] = [A^*(q)]] = 1,\ \varphi(\tau)=1.0,\ \prod_{t=1}^{T}\mathbb{I}[z_t \ne\varnothing] = 1\}. \tag*{(6)}

Observation-Masked Multi-Turn GRPO. Stage 2 operates over the disjoint RL pool QRL\mathcal{Q}_{\mathrm{RL}} (28,215 questions). At each step, we sample G≤8G \le8 trajectories per question from πθold\pi_{\theta_{\mathrm{old}}} and compute the group-normalized advantage A^i=(r(τi)−rˉ)/σ^\hat{A}_i = (r(\tau_i) - \bar{r})/\hat{\sigma}, setting A^i=0\hat{A}_i = 0 whenever σ^=0\hat{\sigma} = 0. Let Li\mathcal{L}_i index the tokens of τi\tau_i generated by the policy—all of {(zt,at)}t=1Ti\{(z_t, a_t)\}_{t=1}^{T_i} but none of the environment receipts {ot}\{o_t\}—so that observation tokens contribute zero gradient:

JRISE(θ)=Eq∼Psched,{τi}i=1G∼πθold(⋅∣q)[1G∑i=1G1∣Ii∣∑m∈Ii(min⁡(ρi,m(θ)A^i,clip⁡(ρi,m(θ),1−ϵ,1+ϵ)A^i)−βDKL(πθ∥πref))](7)\mathcal{J}_{\mathrm{RISE}}(\theta)=\mathbb{E}_{q\sim P_{\mathrm{sched}},\{\tau_i\}_{i=1}^{G}\sim\pi_{\theta_{\mathrm{old}}}(\cdot\mid q)}\left[\frac{1}{G}\sum_{i=1}^{G}\frac{1}{\lvert\mathcal{I}_i\rvert}\sum_{m\in\mathcal{I}_i}\left(\min\left(\rho_{i,m}(\theta)\widehat{A}_i,\operatorname{clip}\left(\rho_{i,m}(\theta),1-\epsilon,1+\epsilon\right)\widehat{A}_i\right)-\beta D_{\mathrm{KL}}(\pi_{\theta}\Vert\pi_{\mathrm{ref}})\right)\right] \tag*{(7)}

where ρi,m(θ)=πθ(τi,m∣q,τi,<m)πθold(τi,m∣q,τi,<m)\rho_{i,m}(\theta)=\frac{\pi_{\theta}(\tau_{i,m}\mid q,\tau_{i,<m})}{\pi_{\theta_{\mathrm{old}}}(\tau_{i,m}\mid q,\tau_{i,<m})} is the token-level importance ratio and πref\pi_{\mathrm{ref}} is the cold-start checkpoint [42, 43, 44].

Learning-Frontier Scaling via Structural Tiering and Competence-Frontier Bandit

The objective in Equation (7) normalizes advantages within each question’s rollout group. That normalization has a direct mathematical consequence governing how the sampling distribution PschedP_{\mathrm{sched}} over QRLQ_{\mathrm{RL}} must be designed when the decision space is enlarged: a question contributes a policy gradient if and only if the GG rollouts sampled for it disagree.

Proposition 1 (Variance Collapse under Group Normalization). Let A^i=(r(τi)−rˉ)/σ^\widehat{A}_i=(r(\tau_i)-\bar{r})/\hat{\sigma} be the group-normalized advantage in Equation (7) over GG rollouts {τi}i=1G∼i.i.d.πθ(⋅∣q)\{\tau_i\}_{i=1}^{G}\overset{\mathrm{i.i.d.}}{\sim}\pi_{\theta}(\cdot\mid q). Whenever the reward r(τ)r(\tau) is constant on the sampled support of πθ(⋅∣q)\pi_{\theta}(\cdot\mid q) (i.e., r(τ1)=⋯=r(τG)=cr(\tau_1)=\cdots=r(\tau_G)=c), the within-group variance vanishes (σ^=0\hat{\sigma}=0) and the policy-gradient contribution of question qq is identically zero (∇θJq(θ)≡0\nabla_{\theta}J_q(\theta)\equiv0). Furthermore, when format compliance has converged (φ(τ)=1.0\varphi(\tau)=1.0) so that r(τ)−1∼Bernoulli⁡(p(q;θ))r(\tau)-1\sim\operatorname{Bernoulli}(p(q;\theta)) with success probability p(q;θ)∈[0,1]p(q;\theta)\in[0,1], the probability that question qq yields a non-zero gradient update across GG rollouts is

Pr⁡(σ^(q)>0∣θ)=1−p(q;θ)G−(1−p(q;θ))G,(8)\Pr\left(\hat{\sigma}(q)>0\mid\theta\right)=1-p(q;\theta)^{G}-(1-p(q;\theta))^{G}, \tag*{(8)}

which vanishes at both extremes p(q;θ)∈{0,1}p(q;\theta)\in\{0,1\}, attains its unique global maximum at the competence frontier p∗(q;θ)=0.5p^*(q;\theta)=0.5, and is strictly monotonically increasing in the Bernoulli standard deviation σBern(q;θ)=p(q;θ)(1−p(q;θ))\sigma_{\mathrm{Bern}}(q;\theta)=\sqrt{p(q;\theta)(1-p(q;\theta))}.

The proof is in Appendix § 14. Proposition 1 explains why 64% of our full-graph training pool yields zero gradient under uniform sampling at G=8G=8 (following pG+(1−p)Gp^G+(1-p)^G scaling from an empirical 73% zero-variance rate observed at G=4G=4): mastered questions (pq→1p_q\to1) and questions that are unreachable or currently beyond the policy’s horizon (pq→0p_q\to0) both collapse to σ^=0\hat{\sigma}=0. Because σ^(q)\hat{\sigma}(q) is a per-question property, a batch mixing half pq=1p_q=1 and half pq=0p_q=0 questions still produces zero gradient despite a mean pass rate of 0.5. Sustaining active gradients therefore requires aligning both the macro progression direction and the micro batch composition PschedP_{\mathrm{sched}} with the policy’s evolving competence frontier (pq≈0.5p_q\approx0.5).

Model-Independent Structural Tiers and Macro Frontier Direction. To partition QRLQ_{\mathrm{RL}} without circular model-based perplexity, we assign each question a deterministic structural tier d(q)∈{1,2,3,4}d(q)\in\{1,2,3,4\} parsed directly from its gold SPARQL topology and official structural annotations: Tier 1 comprises single-hop relation lookups and simple chains, Tier 2 comprises multi-hop composition chains, Tier 3 comprises multi-constraint conjunction intersections, and Tier 4 comprises comparative and superlative aggregation queries. At the start of RL, the policy’s competence frontier (pq≈0.5p_q\approx0.5) resides in simpler lookups and short chains while harder multi-constraint tiers sit near pq≈0p_q\approx0. Presenting tiers in progressive order (d=1→2→3→4d=1\to2\to3\to4, Easy-to-Hard, E2H) provides an open-loop approximation to the expanding frontier, whereas reversing the exact same 28,215-question multiset (d=4→3→2→1d=4\to3\to2\to1, Hard-to-Easy, H2E) front-loads zero-variance hard tiers when the policy cannot solve them and defers easy tiers until they are already mastered.

Micro Frontier Adaptation via Self-Evolving Curriculum (SEC) Bandit. While static E2H ordering captures the macro directional progression of multi-hop learning, fixed step boundaries cannot adapt to the exact rate at which a policy masters each tier or retreat when the hardest tier remains largely unsolvable. Following Chen et al. [9], we treat the four structural tiers k∈k\in {1,2,3,4}\{1, 2, 3, 4\} over the same QRL\mathcal{Q}_{\mathrm{RL}} pool as bandit arms. Let Bs,k\mathcal{B}_{s,k} denote the subset of questions drawn from arm kk at step ss, and let pq=1G∑i=1GI[g(τi)⋅I[[[A^(τi)]]=[[A(q)∗]]]=1]p_q = \frac{1}{G}\sum_{i=1}^{G}\mathbb{I}[g(\tau_i)\cdot\mathbb{I}[[[\hat{A}(\tau_i)]] = [[A^*_{(q)}]]] = 1] be the grounded group pass rate of question qq. Note that while GRPO computes advantages on total reward r(τ)r(\tau), the scheduler tracks variance strictly on the grounded outcome pqp_q so that bandit allocation is never misled by formatting noise. SEC updates each arm’s EMA frontier value Qk(s)Q_k(s) and samples arms via a Boltzmann distribution:

Qk(s)=(1−α)Qk(s−1)+αvˉk(s),vˉk(s)=1∣Bs,k∣∑q∈Bs,k2pq(1−pq),Ps+1(k)=exp⁡(Qk(s)/η)∑j=14exp⁡(Qj(s)/η).(9)\begin{aligned} Q_k(s) &= (1-\alpha)Q_k(s-1) + \alpha\bar{v}_k(s), \qquad\bar{v}_k(s) = \frac{1}{|\mathcal{B}_{s,k}|}\sum_{q\in\mathcal{B}_{s,k}} 2\sqrt{p_q(1-p_q)},\\ P_{s+1}(k) &= \frac{\exp(Q_k(s)/\eta)}{\sum_{j=1}^{4}\exp(Q_j(s)/\eta)}. \tag*{(9)} \end{aligned}

with EMA rate α=0.5\alpha= 0.5, temperature η=0.4\eta= 0.4, and initialization Qk(0)=0.5Q_k(0) = 0.5 (questions within each arm are drawn without replacement per pass and reshuffled upon depletion). Because 2pq(1−pq)2\sqrt{p_q(1-p_q)} decays as an easier tier is mastered (pq→1p_q \to1) and rises as a harder tier enters the solvable band (pq→0.5p_q \to0.5), Ps(k)P_s(k) autonomously tracks the moving competence frontier (Algorithm 1, Appendix § 14).

Experiments

To systematically evaluate RISE and dissect the contribution of each component in its training recipe, we conduct comprehensive experiments across nineteen benchmarks spanning three capability families to answer four research questions (RQs): (1) RQ1: Can effective multi-hop search policies be learned directly over an unpruned, full-scale structured environment, and how well do they generalize to unseen schemas and across model scales? (2) RQ2: Can a search policy trained exclusively on a structured knowledge graph transfer zero-shot to unstructured open-domain passage retrieval? (3) RQ3: Do the hypothesis-testing, pruning, and verification habits acquired through interactive structured exploration generalize out-of-domain to enhance tool-free mathematical and logical reasoning? (4) RQ4: How do the protocol-preserving cold start, progressive frontier ordering, and online variance-driven batch composition (SEC) distinctively contribute to agentic learning?

Experimental Setup

Datasets and Metrics

We evaluate on nineteen benchmarks under greedy decoding (T=0T = 0), grouped into three capability families: (1) structured knowledge (6 sets)—WebQSP [62] and CWQ [49] in-domain, GrailQA (Gu et al., 2021), SimpleQuestions [5], and WebQuestions [3] for unseen-schema transfer, and MultiTQ [12] for temporal reasoning; (2) cross-tool passage retrieval (7 sets)—the single-hop sets NQ [31], TriviaQA [28], and PopQA [37], and the multi-hop sets HotpotQA [60], 2WikiMultiHopQA [22], MuSiQue [51], and Bamboogle [38]; and (3) tool-free general reasoning (6 sets)—GSM8K [13], MATH500 [21], AIME24, AMC23, and Knights and Knaves Easy and Hard [55, 56]. Metrics follow standard conventions per family and are never pooled across families: set-equality EM for WebQSP, CWQ, and GrailQA; any-item hit (†) for SimpleQuestions and WebQuestions; Hits@1 for MultiTQ; alias EM for passage retrieval; and exact accuracy for general reasoning, with Avg. reporting the within-table mean.

Baselines

We instantiate every arm on three instruction-tuned backbones—Qwen2.5-7B-Instruct, Qwen2.5-14B-Instruct, and Llama-3.1-8B-Instruct—and compare each capability family against strong specialized baselines reproduced on the exact same backbones and evaluated under identical greedy decoding, prompts (Appendix § 10), and answer normalization: Plan-on-Graph (PoG) [7] and KG-R1 [35] for structured knowledge; Search-R1 [27] and ZeroSearch [47] for passage retrieval; and GraphWalker [57] and SIE [64] for general reasoning. One deliberate asymmetry should be noted: in Table 2 and 3, RISE is evaluated strictly zero-shot (trained solely on Freebase), whereas Search-R1 and ZeroSearch are trained in-domain on passage retrieval, making any margin there a conservative lower bound on transfer efficacy. For RQ4 (Table 4), we compare seven controlled recipe arms within the exact same environment: Base model, RISE w/o RL (cold start only on QcoldQ_{\mathrm{cold}}), RISE w/o SFT (RL from base on QRLQ_{\mathrm{RL}}), and full two-stage RISE where all four curriculum schedules—uniform (UNI), hard-to-easy (H2E), easy-to-hard (E2H), and SEC bandit—train on the exact same 28,215-question pool QRLQ_{\mathrm{RL}}.

Table 2: Zero-shot cross-tool transfer to Wikipedia passage retrieval (RQ2), % (alias EM). RISE is evaluated strictly zero-shot (trained only on Freebase); Search-R1 and ZeroSearch are trained in-domain on passage retrieval. RISE surpasses domain-trained retrieval baselines on all three backbones, with the largest margins on multi-hop synthesis.

Backbone / ArmNQTriviaQAPopQAHotpotQA2WikiMuSiQueBamboogleAvg.
Qwen2.5-7B-Instruct
Base model12.835.613.816.222.66.624.018.8
+ Search-R142.463.451.632.833.217.426.438.2
+ ZeroSearch43.665.248.834.635.218.438.440.6
+ RISE (ours)43.963.849.739.439.318.945.642.9
Qwen2.5-14B-Instruct
Base model23.752.933.428.132.218.436.032.1
+ Search-R148.868.755.239.247.931.446.448.2
+ ZeroSearch58.374.362.943.148.333.650.453.0
+ RISE (ours)65.476.364.654.357.332.562.459.0
Llama-3.1-8B-Instruct
Base model18.536.624.315.424.915.426.423.1
+ Search-R141.662.550.242.939.823.740.042.9
+ ZeroSearch46.363.052.845.340.524.945.645.5
+ RISE (ours)50.362.753.648.644.824.651.248.0

Table 2.

ArmWebQSPCWQPopQA2WikiGSM8KMATH500Avg.
Base model42.329.413.822.630.242.630.1
RISE w/o RL59.657.137.336.258.549.849.7
RISE w/o SFT78.463.342.435.578.258.459.4
RISE w/ UNI84.179.447.637.684.465.666.4
RISE w/ H2E82.275.046.836.285.364.064.9
RISE w/ E2H90.783.251.839.887.970.670.7
RISE w/ SEC92.485.449.739.388.273.471.4

Table 4. Recipe attribution on Qwen2.5-7B-Instruct (RQ4), %. Six representative benchmarks spanning the three families (this six-column mean is not comparable to the per-family averages in Appendix F). Cold start and on-policy RL are complementary, progressive frontier alignment (E2H vs. H2E) prevents early zero-variance starvation, and closed-loop SEC achieves the best overall score.

Implementation Details

All RL arms use on-policy multi-turn GRPO on VeRL ([44]) with vLLM rollouts, group size G=8G = 8, batch size 64 questions per step, constant learning rate 1×10−61 \times10^{-6}, KL penalty β=0.01\beta= 0.01, per-turn cap 2,048 tokens, rolling context window 28,672 tokens, and call budget Cmax⁡=16C_{\max} = 16 for one epoch (440 steps, matching 28,215/64≈44028{,}215/64 \approx440) on 8×8 \times A100 GPUs. Passage retrieval uses the Wiki-18 dump (21,015,324 passages) indexed with E5-base-v2 and FAISS flat, returning top-3 passages per call, while the KG adapter returns at most 50 relations and 100 rows (Appendix § 11).

Main Results

RISE substantially outperforms subgraph-trained and prompting-based KG agents across all three backbones, winning 17 of 18 benchmark comparisons with the largest gains on multi-hop composition and unseen schemas (RQ1). Table 1 reports results on the structured-knowledge family. On Qwen2.5-7B, RISE elevates the six-benchmark average from 43.2% (Base) to 73.0%, outperforming the subgraph-RL baseline KG-R1 (62.8%) by +10.2 points and PoG (46.8%) by +26.2 points. The advantage is largest precisely where genuine path pruning is required: 92.4% vs. 82.4% on WebQSP (+10.0), 85.4% vs. 65.6% on CWQ (+19.8), and 86.2% vs. 62.4% on GrailQA (+23.8). The same superiority holds on Qwen2.5-14B (78.3% vs. 72.1% for KG-R1) and Llama-3.1-8B (74.0% vs. 69.3%). Across datasets, multi-hop compositional queries (CWQ) and zero-shot unseen schemas (GrailQA) exhibit far larger gains than single-hop lookup (SimpleQuestions), confirming that RISE learns transferable multi-step pruning rather than superficial query formatting.

Policies trained exclusively on Freebase transfer zero-shot to Wikipedia passage retrieval, winning 16 of 21 comparisons and surpassing domain-trained text-RL baselines in overall average across all three backbones (RQ2). Table 2 evaluates zero-shot cross-tool transfer when replacing the KG adapter at test time with the Wikipedia dense passage retriever. Without any modification to the policy weights or turn protocol, RISE achieves a seven-benchmark average of 42.9% on Qwen2.5-7B (outperforming in-domain trained ZeroSearch at 40.6% and Search-R1 at 38.2%), 59.0% on Qwen2.5-14B (vs. 53.0% for ZeroSearch), and 48.0% on Llama-3.1-8B (vs. 45.5%). While multi-hop retrieval benchmarks exhibit the largest gains—lifting HotpotQA from 43.1% to 54.3% (+11.2) and Bamboogle from 50.4% to 62.4% (+12.0) at 14B—the single-fact benchmarks (NQ, TriviaQA, PopQA) also improve substantially over the base model (18.8% → 42.9% average at 7B), confirming that what transfers across tools is the fundamental habit of query reformulation and evidence verification.

Interactive structured exploration substantially enhances out-of-domain mathematical and logical reasoning, winning 13 of 18 comparisons (with 1 tie) and surpassing both static in-context RL (SIE) and subgraph RL (GraphWalker) across all three backbones (RQ3). Table 3 evaluates zero-shot transfer to six tool-free mathematical and logical reasoning benchmarks. Training in RISE elevates the six-benchmark reasoning average from 28.9% to 51.8% on Qwen2.5-7B (surpassing SIE at 47.5% and GraphWalker at 41.0%), from 50.5% to 68.5% on Qwen2.5-14B (SIE: 60.4%), and from 25.7% to 37.0% on Llama-3.1-8B (SIE: 35.2%). The gains are particularly pronounced on multi-step symbolic and logical deduction: on Qwen2.5-7B, RISE boosts MATH500 accuracy to 73.4% (+11.8 points over SIE), while on Qwen2.5-14B it lifts Knights & Knaves Easy and Hard to 79.0% and 65.0% (+13.0 and +19.5 points over SIE, respectively). Because full-graph interaction requires the policy to formulate explicit hypotheses inside <think>, prune invalid branches upon receiving empty or truncated receipts, and verify constraints before answering, these deliberative habits internalize as stronger step-by-step deduction even without external tools.

Backbone / ArmGSM8KMATH500AIME24AMC23EasyHardAvg.
Qwen2.5-7B-Instruct
Base model30.242.63.337.541.518.528.9
+ GraphWalker74.361.46.740.040.023.541.0
+ SIE87.461.610.047.549.529.047.5
+ RISE (ours)88.273.416.752.548.531.551.8
Qwen2.5-14B-Instruct
Base model71.662.016.757.560.534.550.5
+ GraphWalker74.872.816.757.564.046.555.4
+ SIE91.175.020.065.066.045.560.4
+ RISE (ours)90.478.830.067.579.065.068.5
Llama-3.1-8B-Instruct
Base model66.838.86.715.020.07.025.7
+ GraphWalker79.248.86.717.534.014.033.4
+ SIE82.647.06.722.537.015.535.2
+ RISE (ours)87.848.410.022.538.515.037.0

Table 3. Zero-shot transfer to tool-free general reasoning (RQ3), % (exact accuracy; AIME24 has 30 items and AMC23 has 40, where ties count as neither a win nor a loss). All arms are trained on structured KG environments and evaluated zero-shot without tools. Interactive exploration in RISE internalizes hypothesis testing and branch pruning, outperforming static in-context RL (SIE) across all three backbones.

**Protocol cold start and on-policy RL are strongly complementary, while progressive frontier alignment (E2H) and closed-loop variance tracking (SEC) jointly overcome zero-variance stagnation (RQ4). Table 4 ablates each stage and scheduling mechanism across six representative benchmarks on Qwen2.5-7B (full nineteen-benchmark grids are in Appendix § 12, Table 8–Table 10). First, the two stages are mutually reinforcing: supervised cold start alone (RISE w/o RL) raises the average from 30.1% to 49.7% and direct RL from the base model (RISE w/o SFT) reaches 59.4%, whereas combining them under uniform sampling (RISE w/ UNI) jumps to 66.4% (+16.7 over SFT alone and +7.0 over RL alone). Notably, while RISE w/o SFT reaches 78.4% on in-domain WebQSP—proving that full-graph tool use is learnable from scratch under our grounded reward—it drops to 59.2% on unseen-schema GrailQA (Appendix Table 8), 27.0 points behind full RISE (86.2%), confirming that the cold-start prior is critical for anchoring multi-turn protocol generalization. Second, comparing the curriculum arms over the exact same 28,215-question pool QRLQ_{\mathrm{RL}} directly validates Proposition 1. Because Tier 3 and Tier 4 questions exhibit near-zero pass rates @page 10/30 starts_mid=0 ends_mid=1

ArmWebQSPCWQGrailQASimpleQ†WebQ†MultiTQAvg.
Base model42.329.446.261.452.327.343.2
+ PoG47.532.154.364.252.730.246.8
+ KG-R182.465.662.468.864.533.062.8
RISE w/o RL59.657.162.268.358.528.455.7
RISE w/o SFT78.463.359.265.563.033.360.4
RISE w/ UNI84.179.464.670.465.633.666.3
RISE w/ H2E82.275.067.769.965.932.865.6
RISE w/ E2H90.783.284.872.667.534.372.2
RISE w/ SEC92.485.486.272.267.134.573.0

Table 8. Complete structured-knowledge grid for all recipe arms on Qwen2.5-7B-Instruct (RQ4), %. Set-equality EM except SimpleQuestions and WebQuestions (any-item hit, †) and MultiTQ (Hits@1). Bold marks the best arm of each column and underline the second; the RISE w/ SEC row is shaded.

ArmGSM8KMATH500AIME24AMC23K&K EasyK&K HardAvg.
Base model30.242.63.337.541.518.528.9
+ GraphWalker74.361.46.740.040.023.541.0
+ SIE87.461.610.047.549.529.047.5
RISE w/o RL58.549.810.040.042.019.036.5
RISE w/o SFT78.258.410.040.046.527.543.4
RISE w/ UNI84.465.610.045.047.028.046.7
RISE w/ H2E85.364.010.045.047.027.546.5
RISE w/ E2H87.970.616.747.548.530.550.3
RISE w/ SEC88.273.416.752.548.531.551.8

Table 10. Complete tool-free general reasoning grid for all recipe arms on Qwen2.5-7B-Instruct (RQ4), % (exact accuracy). Bold marks the best arm of each column and underline the second.

Table 1: Structured-knowledge results (RQ1), %. Set-equality EM except SimpleQuestions/WebQuestions (any-item hit, †) and MultiTQ (Hits@1). Within each block, bold marks the best result and underline the runner-up; RISE is shaded. RISE wins 17 of 18 comparisons, with the largest margins on compositional (CWQ) and unseen-schema (GrailQA) sets.

Backbone / ArmWebQSPCWQGrailQASimpleQ†WebQ†MultiTQAvg.
Qwen2.5-7B-Instruct
Base model42.329.446.261.452.327.343.2
+ PoG47.532.154.364.252.730.246.8
+ KG-R182.465.662.468.864.533.062.8
+ RISE (ours)92.485.486.272.267.134.573.0
Qwen2.5-14B-Instruct
Base model50.254.468.566.258.336.455.7
+ PoG63.467.672.367.458.937.261.1
+ KG-R188.378.479.274.570.042.572.1
+ RISE (ours)94.689.588.380.871.245.378.3
Llama-3.1-8B-Instruct
Base model46.332.545.663.351.826.844.4
+ PoG56.956.851.365.854.429.152.4
+ KG-R186.276.177.974.268.432.869.3
+ RISE (ours)93.288.985.474.368.234.074.0

Table 1.

Table 1: Structured-knowledge results (RQ1), %. Set-equality EM except SimpleQuestions/WebQuestions (any-item hit, †) and MultiTQ (Hits@1). Within each block, bold marks the best result and underline the runner-up; RISE is shaded. RISE wins 17 of 18 comparisons, with the largest margins on compositional (CWQ) and unseen-schema (GrailQA) sets.

Backbone / ArmWebQSPCWQGrailQASimpleQ†WebQ†MultiTQAvg.
Qwen2.5-7B-Instruct
Base model42.329.446.261.452.327.343.2
+ PoG47.532.154.364.252.730.246.8
+ KG-R182.465.662.468.864.533.062.8
+ RISE (ours)92.485.486.272.267.134.573.0
Qwen2.5-14B-Instruct
Base model50.254.468.566.258.336.455.7
+ PoG63.467.672.367.458.937.261.1
+ KG-R188.378.479.274.570.042.572.1
+ RISE (ours)94.689.588.380.871.245.378.3
Llama-3.1-8B-Instruct
Base model46.332.545.663.351.826.844.4
+ PoG56.956.851.365.854.429.152.4
+ KG-R186.276.177.974.268.432.869.3
+ RISE (ours)93.288.985.474.368.234.074.0

Table 1 (PDF p. 10).

Table 2: Zero-shot cross-tool transfer to Wikipedia passage retrieval (RQ2), % (alias EM). RISE is evaluated strictly zero-shot (trained only on Freebase); Search-R1 and ZeroSearch are trained in-domain on passage retrieval. RISE surpasses domain-trained retrieval baselines on all three backbones, with the largest margins on multi-hop synthesis.

Backbone / ArmNQTriviaQAPopQAHotpotQA2WikiMuSiQueBamboogleAvg.
Qwen2.5-7B-Instruct
Base model12.835.613.816.222.66.624.018.8
+ Search-R142.463.451.632.833.217.426.438.2
+ ZeroSearch43.665.248.834.635.218.438.440.6
+ RISE (ours)43.963.849.739.439.318.945.642.9
Qwen2.5-14B-Instruct
Base model23.752.933.428.132.218.436.032.1
+ Search-R148.868.755.239.247.931.446.448.2
+ ZeroSearch58.374.362.943.148.333.650.453.0
+ RISE (ours)65.476.364.654.357.332.562.459.0
Llama-3.1-8B-Instruct
Base model18.536.624.315.424.915.426.423.1
+ Search-R141.662.550.242.939.823.740.042.9
+ ZeroSearch46.363.052.845.340.524.945.645.5
+ RISE (ours)50.362.753.648.644.824.651.248.0

Table 2 (PDF p. 10).

stagnation (RQ4). Table 4 ablates each stage and scheduling mechanism across six representative benchmarks on Qwen2.5-7B (full nineteen-benchmark grids are in Appendix § 12, Table 8–Table 10). First, the two stages are mutually reinforcing: supervised cold start alone (RISE w/o RL) raises the average from 30.1% to 49.7% and direct RL from the base model (RISE w/o SFT) reaches 59.4%, whereas combining them under uniform sampling (RISE w/ UNI) jumps to 66.4% (+16.7 over SFT alone and +7.0 over RL alone). Notably, while RISE w/o SFT reaches 78.4% on in-domain WebQSP—proving that full-graph tool use is learnable from scratch under our grounded reward—it drops to 59.2% on unseen-schema GrailQA (Appendix Table 8), 27.0 points behind full RISE (86.2%), confirming that the cold-start prior is critical for anchoring multi-turn protocol generalization. Second, comparing the curriculum arms over the exact same 28,215-question pool QRLQ_{\mathrm{RL}} directly validates Proposition 1. Because Tier 3 and Tier 4 questions exhibit near-zero pass rates

(pq→0p_q \to0, σ^=0\hat{\sigma} = 0) at the start of RL, presenting hard tiers first (RISE w/ H2E, 64.9%) starves early training of active gradients and underperforms even uniform sampling (66.4%). Conversely, presenting tiers in progressive order (RISE w/ E2H, 70.7%) acts as an open-loop approximation to the expanding competence frontier, yielding +4.3 points over Uniform and +5.8 over H2E. Third, replacing fixed tier transitions with closed-loop variance feedback (RISE w/ SEC, 71.4%) further refines learning on compositionally demanding benchmarks, advancing CWQ from 83.2% to 85.4% (+2.2), WebQSP from 90.7% to 92.4% (+1.7), GrailQA from 84.8% to 86.2% (+1.4, Table 8), MATH500 from 70.6% to 73.4% (+2.8), and AMC23 from 47.5% to 52.5% (+5.0, Table 10).

Analysis

Frontier-aligned scheduling concentrates its gains on multi-step compositional and unseen-schema bottlenecks. Inspecting the full nineteen-benchmark ablation grids in Appendix F (Table 8–Table 10) reveals where Learning-Frontier Scaling (RISE w/ SEC) extracts its advantage over uniform sampling (RISE w/ UNI). On single-hop lookup tasks where uniform sampling already encounters frequent non-zero variance early in training, the margin between SEC and UNI is modest (+1.8 points on SimpleQuestions and +1.5 on WebQuestions). In contrast, on tasks requiring multi-hop relational composition, zero-shot schema generalization, or deep symbolic chains—where uniform rollouts frequently collapse to all-zero rewards early on—the margin expands dramatically: +8.3 points on WebQSP (92.4% vs. 84.1%), +6.0 on CWQ (85.4% vs. 79.4%), +21.6 on GrailQA (86.2% vs. 64.6%), +7.8 on MATH500 (73.4% vs. 65.6%), and +7.5 on AMC23 (52.5% vs. 45.0%).

Co-evolution of search depth, episode deliberation, and sample efficiency. Figure 3 tracks the training dynamics of SEC versus uniform sampling (UNI) across the 440 optimizer steps of one epoch (see Appendix § 13 for a qualitative trajectory comparison). In Figure 3a, both schedules begin at an average of 4.6 search calls per episode; however, while UNI plateaus early around 5.4 calls, SEC progressively expands its interaction horizon to 8.3 search calls per episode as bandit mass migrates from single-hop lookups (Tier 1) toward multi-hop chains and conjunctive intersections (Tiers 2–3). Correspondingly, Figure 3b shows that cumulative reasoning tokens per episode grow from ∼2,600\sim2{,}600 to ∼7,400\sim7{,}400 under SEC (versus plateauing at ∼4,200\sim4{,}200 under UNI), confirming that decoupling the call budget (Cmax⁡=16C_{\max} = 16) from the per-turn token cap (2,048 tokens) enables deeper multi-turn verification without per-turn truncation. Finally, Figure 3c plots validation accuracy on the held-out WebQSP + CWQ test pool (5,156 questions): although UNI rises slightly faster in the first 100 steps by harvesting easy lookups, it saturates near 81.8% by step 180. By contrast, SEC overtakes UNI at step ∼145\sim145, matches UNI’s full-epoch accuracy within 38% of the training budget (∼165\sim165 steps), and continues climbing to ∼89.0\sim89.0% across the epoch.

Figure 3. Training dynamics and sample efficiency comparing competence-frontier scheduling (SEC) against uniform sampling (UNI) across one epoch (440 steps): (a) mean search calls per episode; (b) mean cumulative reasoning tokens per episode; and (c) validation accuracy (%) on the held-out pool.

Conclusion

What defines an autonomous retrieval agent is the sequence of decisions it makes: which path to explore, which candidates to prune, and when to stop searching. All three decisions vanish when the training environment pre-extracts a local subgraph or lets an upstream index decide what is reachable in advance. RISE transitions structured RL environments to full-scale interactive databases along two coupled axes: Decision-Space Scaling exposes the unpruned knowledge graph through a five-stage graph-agnostic typed intent adapter under a bounded call budget, restoring pruning and stopping as turn-attributable policy decisions; and Learning-Frontier Scaling overcomes the 64% within-group variance collapse of full-graph exploration by aligning progressive tier ordering and closed-loop SEC batch composition with the policy’s evolving competence frontier. Across nineteen benchmarks and three model backbones, RISE substantially outperforms specialized baselines in structured KG reasoning, transfers zero-shot to Wikipedia passage retrieval, and generalizes out-of-domain to enhance tool-free mathematical and logical deduction.

Ethics Statement

This work trains and evaluates retrieval-augmented language models exclusively over publicly released benchmarks and knowledge bases (Freebase, MultiTQ, and Wikipedia), involving no human subjects or private user data. While our multiplicative grounding gate g(τ)g(\tau) substantially suppresses ungrounded fabrication, a grounded policy can still misinterpret retrieved facts; we report unconditional full-split metrics and cross-family evaluations transparently to support safe deployment.

Reproducibility Statement

To ensure full reproducibility, Appendix § 7 reviews related work, Appendix § 8 details our preliminary subgraph measurements and design requirements, Appendix § 9 specifies the formal environment contract and closed error vocabulary, Appendix § 10 reproduces verbatim prompt templates for all five task families, Appendix § 11 lists all training, data-split, and retrieval hyperparameters, Appendix § 12 reports the complete nineteen-benchmark attribution grids, Appendix § 13 provides a side-by-side multi-turn interaction case study, Appendix § 14 gives the proof of Proposition 1 and Algorithm 1, Appendix § 15 and Appendix § 16 discuss broader methodological principles and limitations, and Appendix § 17 documents our 23-item silent-failure audit taxonomy. Source code and environment adapters will be released upon publication.

Related Work

Table 5 summarizes how representative systems sit relative to RISE along the three core environmental properties established in § 1.

MethodAction interfaceFull-graph interactionGraph-agnostic intentVariance-driven curriculum
Think-on-Graph [48]Beam search over edges✓◦–
Plan-on-Graph [7]LLM-guided expansion◦◦–
KG-R1 [35]Four symbolic one-hop ops–◦–
GraphWalker [57]Relation / triple lookup◦◦–
Search-R1 [27]Passage query–✓–
ZeroSearch [47]Passage query–✓◦
SIE [64]Static in-context subgraph–––
RISE (ours)Natural-language intent✓✓✓

Table 5. Positioning of representative methods along the three environmental properties argued in this paper. A filled checkmark shows that the property holds by construction; an open circle shows that it holds only partially (e.g., operating on restricted or synthetic subgraphs, or annealing an exogenous noise knob rather than tracking policy variance).

Knowledge-Graph Reasoning Agents. Prompt-driven frameworks traverse a graph by prompting a frozen model to select edges iteratively: Think-on-Graph (Sun et al., [48] performs beam search over relations, and Plan-on-Graph (Chen et al., [7] maintains a decomposed plan with reflection and adaptive beam width. A second line retrieves a question-specific subgraph prior to generation, as in Reasoning-on-Graphs (Luo et al., [36] and G-Retriever (He et al., [20]. A third line trains the policy end to end via RL: KG-R1 (Lin et al., [35] optimizes multi-turn retrieval with four symbolic one-hop primitives over pre-extracted per-question subgraphs; GraphWalker (Xu et al., [57] pretrains on synthetic walking trajectories and applies RL over relation and triple lookups; KnowCoder-A1 (Chen et al., [11] emits executable SPARQL queries assisted by schema-lookup tools; ISP-KGR (Song et al., [46] couples interactive semantic parsing with tree-structured rollouts; and Temp-R1 (Gong et al., [17] applies a reverse curriculum over temporal primitives. Two fundamental differences separate RISE from this line. First, regarding decision-space scale, a median per-question subgraph in the KG-R1 release holds only 4,415 triples, enclosing the gold path in advance; RISE exposes the full 9.5×1089.5 \times10^{8}-triple store under a bounded call budget. Notably, Xu et al. [57] report that evaluating subgraph-trained KG-R1 on the global graph drops WebQSP accuracy from 82.7% (in-subgraph) to 66.8%, directly confirming the magnitude of the subgraph shortcut. Second, regarding interface abstraction, SPARQL generation and graph-specific primitives bind the policy to one database schema, whereas our natural-language intent adapter transfers zero-shot to unstructured passage retrieval.

Reinforcement Learning for Search and Tool Use. Interleaving chain-of-thought reasoning with external tool calls ([61, 41]) via outcome-rewarded RL has been widely studied on text corpora: Search-R1 (Jin et al., [27] formulates multi-turn passage retrieval with observation-token masking, while Research (Chen et al., [8], R1-Searcher (Song et al., [45], WebThinker (Li et al., [33], and DeepResearcher (Zheng et al., [69] extend outcome-driven RL to multi-step web and corpus search. ToolRL (Qian et al., [39] studies reward granularity for general API invocation, SimpleTIR (Xue et al., [58] stabilizes multi-turn tool-integrated training by filtering degenerate turns, Explore-on-Graph (Yan et al., [59] introduces path-refined reward modeling, and ZeroSearch (Sun et al., [47] replaces live search engines with a learned simulator whose noise is annealed over training. While effective on homogeneous text corpora where every query returns a stateless top-kk list with smooth similarity decay, directly applying text-RL recipes to a full-scale structured knowledge base encounters ungrounded guessing on multi-answer queries and severe zero-variance gradient starvation—which RISE resolves via our multiplicative grounding gate g(τ)g(\tau) and competence–frontier scheduling.

Structured Post-Training Environments and Curriculum Learning. A parallel research line constructs post-training environments from structured data ([16, 32] (Wang et al. 2025)). KaLM (Yu et al., [63] aligns internal LLM representations with KG triples via dual-view contrastive learning, embedding structured knowledge into model parameters rather than context. SIE Yu et al. [64] automatically extracts static in-context subgraphs of controlled completeness (ρ≡1\rho\equiv1 at SIE-100%) to incentivize compositional deduction via GRPO. ReMA Wan et al. [52] explores multi-agent meta-thinking under RL, Wen et al. [54] study action decomposition for language agents, and Logic-RL Xie et al. [56] demonstrates reasoning transfer from rule-based logic puzzles. The key distinction lies in what is scaled: SIE scales the completeness of a static context that the model passively reads, whereas RISE scales the decision space of an interactive search environment that the model actively queries, where reachability is governed by the policy’s own sequential decisions under a call budget. On the optimization side, classical curriculum learning orders examples statically by difficulty [2, 30], whereas prioritized replay and bandit schedulers adapt sampling online [40, 1]. Building upon Chen et al. [9], we ground curriculum design in Proposition 1 by uniting SPARQL structural tiers with the group-level standard deviation return 2pq(1−pq)2\sqrt{p_q(1-p_q)}.

Preliminary Measurements and Environment Design Requirements

This appendix provides the complete empirical protocols and measurements underlying the environment design of RISE. Specifically, we formalize three measurable criteria that an interactive environment must satisfy to support authentic search-policy learning, evaluate existing subgraph and query-syntax paradigms against these criteria across four diagnostic measurement sets, and derive the six engineering and methodological requirements summarized in Table 6.

IDDesign RequirementEmpirical SourceArchitectural Instantiation in RISE
D1Unpruned candidate space requiring genuine path pruningCriterion C1, Measurement 1Full-scale Freebase (9.5×1089.5 \times10^{8} triples); zero per-question subgraph pre-filtering
D2Graph- and tool-agnostic policy action interfaceCriterion C2, Measurement 2Natural-language <search> intents translated by deterministic adapter ΦG\Phi_{\mathcal{G}}
D3Outcome-only reward immune to parametric guessingCriterion C3, Section 2.3Set-equality EM gated multiplicatively by evidence grounding g(τ)g(\tau) + additive format φ(τ)\varphi(\tau)
D4Deterministic, answer-blind, direction-symmetric executionMeasurement 3Bidirectional triple traversal Fexec\mathcal{F}_{\mathrm{exec}} with explicit truncation headers (kk of NN)
D5Protocol bootstrapping and active gradient maintenanceMeasurement 3, Proposition 1Isomorphic teacher rejection-sampled cold start + SPARQL tiers & SEC bandit
D6Multi-family evaluation without cross-family poolingMeasurement 4, Appendix KThree capability families across nineteen benchmarks, never pooled across families

Table 6. Summary of environment and training design requirements derived from Measurements 1–4.

Three Measurable Criteria for Agentic Search Environments

Treating multi-turn retrieval as a learnable decision process requires an environment that simultaneously satisfies three foundational conditions:

(C1) Unavoidable Candidate Pruning. If the candidate space is small enough to enumerate within a few steps, sequential path selection requires no strategic pruning. Given any candidate environment, we audit C1 by measuring: (a) the fraction of ground-truth answers reachable within one or two hops from the topic entity, and (b) the top-kk answer hit rate achievable by a question-blind structural heuristic that never reads the input question. If (b) substantially exceeds uniform random chance, the environment’s topology leaks the answer’s location.

(C2) Graph-Agnostic Action Interface. If the policy’s action space is bound to a database-specific query syntax (e.g., SPARQL or specialized atomic graph signatures), the policy conflates strategic search planning with syntax generation, obstructing zero-shot transfer to new graph schemas or unstructured text retrievers. C2 is satisfied when the policy emits natural-language search intents while a deterministic environment adapter handles schema-specific translation.

(C3) Turn- and Outcome-Level Attributability. If the training reward incorporates intermediate process shaping (e.g., bonus credit whenever a gold entity appears anywhere in a retrieved table), score improvements cannot be cleanly attributed to improved decision-making versus shaping exploitation. Attributability requires an outcome-only reward gated by explicit evidence grounding, paired with closed-vocabulary turn receipts.

Measurement 1: Per-Question Subgraphs Compress the Decision Space and Leak Answer Locations

We audited the per-question WebQSP subgraphs released by KG-R1 [35] across all test instances without modification. Hop counts are computed via breadth-first search (BFS) as the shortest path length from any linked topic entity to any gold answer entity inside the extracted subgraph. To test for topological leakage, we evaluate a question-blind degree heuristic that ranks all nodes in the subgraph strictly by their in-subgraph degree (breaking ties deterministically by entity identifier) without accessing the question text, compared against a uniform random node baseline averaged over 1,000 Monte Carlo trials per question.

The empirical findings reveal three severe confounds:

  • Five-Order-of-Magnitude Space Compression: The median per-question subgraph contains only 4,415 triples spanning 1,638 entities (subject to a hard cap of 2,000 entities), which is 216,202× smaller than the full Freebase store (9.5 × 10810^{8} triples).

  • Enumeration Replaces Multi-Hop Planning: Exactly 65.5% of gold answers are reachable within a single hop and 29.1% within two hops. Thus, a naive two-hop expansion covers 94.6% of all test questions, eliminating the need for selective path pruning.

  • Topological Leakage of Answer Entities: The question-blind degree heuristic ranks a gold answer entity at Top-1 in 9.41% of questions, Top-5 in 24.11%, and Top-10 in 33.27%, compared to 0.19% for uniform random selection. Across the dataset, gold answer entities exhibit a median in-subgraph degree of 11, whereas random subgraph nodes exhibit a median degree of 3.

Because upstream subgraph extractors are designed to enclose the ground-truth reasoning path within a small node budget, they inevitably pull in dense local connectivity around the target answer. Consequently, models trained or evaluated on pre-extracted subgraphs can achieve high accuracy by exploiting construction artifacts rather than learning generalizable search policies.

Measurement 2: Database-Specific Action Signatures Obstruct Cross-Tool Transfer

Binding the policy to fixed atomic graph primitives or raw query languages prevents zero-shot generalization across heterogeneous tools. For instance, extending atomic neighborhood actions from static Freebase to temporal knowledge graphs requires altering the action signature to accept timestamp arguments and introducing specialized temporal operators [35, 17]. Conversely, semantic parsing agents such as KnowCoder-A1 (Chen et al., [11] train the policy to emit raw SPARQL syntax supported by schema-lookup tools. While effective within a single database schema, neither action space can be transferred zero-shot to an unstructured Wikipedia passage retriever. By requiring the policy to formulate queries as natural-language intents inside <search>...</search> and delegating execution to a deterministic typed intent adapter ΦG\Phi_{\mathcal{G}}, RISE maintains an identical policy-side protocol across static KGs, temporal KGs, and dense passage retrievers.

Measurement 3: Full-Graph Latency, Partial Observability, and Directional Asymmetry

A common objection to full-graph RL training is that executing live queries against 9.5×1089.5 \times10^{8} triples during on-policy rollouts will bottleneck training throughput. Profiling our Virtuoso backend refutes this concern: on the execution path, a single adapter search call has a median latency of 15.5 ms and a p95 of 65.4 ms (with worst-case single-query latency staying below one second), ensuring that no individual call stalls a rollout turn. At the level of a training step, a warm relation vocabulary of 6,102 entries sustains 29.22 queries per second at a median latency of 0.985 s, meaning that 2,560 queries—the typical load of one GRPO step at 64 questions × 8 rollouts × 5 turns—require only 1.46 minutes of cumulative backend execution time across parallel workers while multi-turn LLM decoding and FSDP parameter updates dominate step wall-clock time.

Operating over the full graph surfaces two structural properties that directly shape our adapter and curriculum design:

  1. Budget-Bounded Reachability Floor and Early Reward Sparsity: Let A∗(q)A^*(q) be the ground-truth answer set for question qq, and E(ot)\mathcal{E}(o_t) the set of surface-form entities and literal values returned in receipt oto_t. For an action sequence a1:k=(a1,…,ak)a_{1:k} = (a_1, \ldots, a_k), the budget-bounded reachability indicator ρ(q;Cmax⁡)∈{0,1}\rho(q; C_{\max}) \in\{0,1\} is defined as

ρ(q;Cmax⁡)=I[∃a1:k∈Asearchk (k≤Cmax⁡) s.t. [A∗(q)]⊆⋃t=1k[E(ΦG(at,ht−1))]].(10)\rho(q; C_{\max}) = \mathbb{I}\left[\exists a_{1:k} \in\mathcal{A}_{\mathrm{search}}^k\ (k \le C_{\max})\ \text{s.t. } [A^*(q)] \subseteq\bigcup_{t=1}^{k} \left[\mathcal{E}\left(\Phi_{\mathcal{G}}(a_t,h_{t-1})\right)\right]\right]. \tag*{(10)}

Unlike pre-extracted subgraphs where ρ(q;Cmax⁡)≡1\rho(q; C_{\max}) \equiv1 by construction, full-graph search under Cmax⁡=16C_{\max} = 16 is subject to partial observability: a model-free outgoing BFS probe without semantic ranking establishes a strict lower bound of ρBFS≥0.5219\rho_{\mathrm{BFS}} \ge0.5219 (leaving up to 0.48 unreachable without semantic ranking). Under G=8G = 8 group sampling, this partial observability causes 64% of training questions to yield zero within-group reward variance (σ^=0\hat{\sigma}=0, corresponding to pG+(1−p)Gp^{G}+(1-p)^{G} scaling from an empirical 73% zero-variance rate at G=4G=4), motivating our SEC bandit scheduler.

  1. Severe Directional Asymmetry of Relations: Auditing candidate Freebase relations around topic entities reveals that 48.6% of valid relations exist exclusively as incoming edges (e′,r,ete^{\prime},r,e_{t}). An environment adapter that traverses only outgoing edges (et,r,e′e_{t},r,e^{\prime}) would list these relations during schema inspection but return empty results when the policy queries them, penalizing valid reasoning steps. Direction-symmetric execution ((3)) is therefore a foundational correctness requirement.

Measurement 4: Silent Failure Modes in Multi-Turn Agentic RL

During the development of RISE, we conducted systematic turn-level trajectory audits and discovered that the most damaging implementation defects in multi-turn agentic RL do not trigger run-time exceptions or degrade standard scalar monitoring curves (e.g., mean reward, KL divergence, or gradient norm). Instead, defects such as mid-row observation truncation, test-split leakage into cold-start pools, reward-gaming on multi-answer sets, or mismatches between trainer and evaluator stop tokens manifest as silent capability regressions where training jobs complete normally (Succeeded) while downstream transfer or reasoning retention degrades. We formalize these into a 23-item audit taxonomy in Appendix K.

Formal Environment Contract and Error Vocabulary

This appendix specifies the formal turn grammar, receipt schema, closed error vocabulary, and budget accounting rules summarized in Section 2.2.

Turn Grammar. At every turn tt, the assistant policy must emit a reasoning block enclosed in <think>...</think> followed by exactly one action tag (either a search query or a terminal answer):

<think>step-by-step reasoning and search planning</think>
<search>natural-language query with [[Entity Mention]]</search>

<think>final evidence synthesis and verification</think>
<answer>entity 1, entity 2</answer>
<answer></answer>  % explicit abstention

Every <search> turn is followed by exactly one user turn containing the environment’s <information>...</information> receipt; retrieved facts are never spliced directly into the assistant’s generation stream.

Structured Receipt Schema. Each valid observation receipt contains four standardized fields: (1) Resolved, reporting the surface form and matched graph node identifier (allowing the policy to verify entity resolution without generating raw MIDs); (2) intent, recording the classified structural intent tag (ιt∈{relation_hop,relation_list,entity_info}\iota_t \in\{\texttt{relation\_hop},\texttt{relation\_list},\texttt{entity\_info}\}); (3) Results (kk of NN), listing the top-kk ranked triples formatted as subject | relation | object alongside total match count NN to distinguish empty results (N=0N = 0) from row-cap truncation (k<Nk < N); and (4) Calls remaining, displaying the remaining search budget Cmax⁡−ctC_{\max} - c_t.

Closed-Vocabulary Error Codes. All execution anomalies are mapped deterministically to seven machine-readable error codes:

  • E_NO_ENTITY: Query contains no bracketed entity mention or no candidate exceeds the resolution threshold.

  • E_ENTITY_NOT_FOUND: Bracketed surface form cannot be resolved in the active binding table or graph index.

  • E_INTENT_UNSUPPORTED: Requested structural operation is inapplicable to the resolved node type.

  • E_NO_RESULTS: Well-formed query executed successfully but returned zero matching triples (N=0N = 0).

  • E_QUERY_FAILED: Transient backend timeout or SPARQL engine exception; never penalized or counted against policy error streaks.

  • E_BUDGET_EXCEEDED: Search call cap Cmax⁡=16C_{\max} = 16 reached; triggers the final answer-only turn.

  • E_MALFORMED: Assistant output violated the turn grammar (<think> followed by <search> or <answer>); permits retry on the next turn if budget remains.

Dual-Budget Accounting and Observation Independence. The search call cap (Cmax⁡=16C_{\max} = 16), per-turn generation limit (2,048 tokens), and rolling context window (28,672 tokens, enforced via left truncation) operate orthogonal to one another. Cold-start trajectory filtering, online GRPO rollouts, and benchmark evaluation invoke the exact same adapter binary and receipt serializer.

Verbatim Prompt Templates

To guarantee full reproducibility of our protocol layer and cross-tool transfer experiments, we reproduce verbatim every system, user, and observation prompt template used across the five task instantiations. All templates share an isomorphic turn structure (<think> → <search>/<answer> → <information>), differing only in tool specification and answer formatting.

Knowledge-Graph Agent (WebQSP, CWQ, GrailQA, SimpleQuestions, WebQuestions)

When a benchmark provides linked topic entities, they are supplied in double square brackets on the second line of the user turn; when no topic entities are provided, the second line is omitted.

System & User Prompt: Knowledge-Graph Agent

You are a question-answering agent with access to a knowledge graph.

In every turn, first reason inside <think>...</think>, then take
    exactly one action:
- <search>query</search> to query the knowledge graph, or
- <answer>final answer</answer> to finish.

After a search, the environment replies inside <information>...</information>; wait for that reply before acting again.

Write a search as a natural-language question about one entity, with every entity name in double square brackets, copied exactly from the question, the topic entities or an earlier <information> block: <search> Who is the head coach of [[Pittsburgh Steelers]]? </search>

A reply starts with a Resolved line naming the matched entity, followed by facts as "subject | relation | object" rows. "Results (k of N)" means only k of N rows are shown; ask a more specific question to narrow them down. If no relation matches your question, the reply lists the entity's relations instead; choose one and ask again. Repeating a search returns the same result. When a reply says your budget is exhausted, give your answer in the next turn.

Answer with names, dates or values exactly as they appear in <information> blocks, and separate multiple answers with commas.

Question: <question, whitespace-normalised>

Topic entities: [[entity 1]], [[entity 2]]

Temporal Knowledge-Graph Modifier (MultiTQ)

For MultiTQ, the following paragraph is appended to the knowledge-graph system prompt above:

System Prompt Modifier: Temporal Knowledge-Graph (MultiTQ)

This knowledge graph is temporal: every fact row ends with the date it happened (YYYY-MM-DD). Answer questions about "before", "after", "first" or "last" by comparing those dates, and give a date at the granularity the question asks for: YYYY for a year, YYYY-MM for a month, YYYY-MM-DD for a day.

Text-Retrieval Agent (Search QA Transfer Family)

For zero-shot evaluation on NQ, TriviaQA, PopQA, HotpotQA, 2WikiMultiHopQA, MuSiQue, and Bamboogle, the KG adapter is replaced by a Wikipedia passage retriever using the following minimally adapted system prompt:

System Prompt: Text-Retrieval Agent (Search QA Family)

You are a question-answering agent with access to a Wikipedia search engine.

In every turn, first reason inside <think>...</think>, then take exactly one action:

  • <search>query</search> to search Wikipedia, or

  • <answer>final answer</answer> to finish. After a search, the environment replies inside <information>...</information>; wait for that reply before acting again.

Write a search as a natural-language question or a keyword query: <search> Who is the head coach of the Pittsburgh Steelers? </search>

A reply lists the most relevant passages, each with its title. If they do not contain what you need, search again with a different query; repeating a search returns the same result. When a reply says your budget is exhausted, give your answer in the next turn.

Answer with a short answer only (a name, date or number), not a sentence.

Single-Turn Mathematical Reasoning (GSM8K, MATH500, AIME24, AMC23)

System & User Prompt: Single-Turn Mathematical Reasoning

You are a careful mathematical problem solver.

First reason step by step inside <think>...</think>, then give the final answer inside <answer>...</answer>. The answer must be the final result only (a number or a simplified expression in LaTeX), with no explanation.

Question: <question>

Logical Reasoning (Knights and Knaves Easy & Hard)

System & User Prompt: Logical Reasoning (Knights and Knaves)

You are a careful logical reasoner.

First reason step by step inside <think>...</think>, then give the final answer inside <answer>...</answer>, stating the identity of every inhabitant on its own numbered line:
<answer>
(1) A is a knight
(2) B is a knave
</answer>
Use the inhabitants' names from the question in place of A and B.

Question: <question>

Environment Observation Receipt Template

Observation Receipt Template

<information>
Resolved: <matched entity> | intent=<closed tag>
Results (k of N):
<subject> | <relation> | <object>
...
Calls remaining: <n>
</information>

Training Configuration and Hyperparameters

All training instances in Stage 1 and Stage 2 are drawn exclusively from the official training splits of WebQSP and CWQ (34,215 questions in total), which are partitioned via stratified sampling by dataset and difficulty tier into the cold-start pool Qcold\mathcal{Q}_{\mathrm{cold}} (6,000 questions) and the RL pool QRL\mathcal{Q}_{\mathrm{RL}} (28,215 questions). The four RL curriculum schedules (UNI, E2H, H2E, and SEC) operate over the exact same 28,215-question pool QRL\mathcal{Q}_{\mathrm{RL}}, differing only in presentation order or dynamic batch composition. Table 7 details the complete training, data-hygiene, and retrieval configuration shared across all experimental arms.

Hyperparameter / SettingValue
Base modelsQwen2.5-7B-Instruct (primary); Llama-3.1-8B-Instruct; Qwen2.5-14B-Instruct
RL optimization frameworkOn-policy multi-turn GRPO on VeRL ([44]) (FSDP + vLLM rollout engine)
Rollout group size GG8 trajectories per question
Batch size ∣Bs∣\lvert B_s\rvert64 questions per step (512 group trajectories per step)
Training horizon SepochS_{\mathrm{epoch}}1 epoch (440 optimizer steps)
Master training corpus34,215 questions from official WebQSP + CWQ train splits, stratified by (dataset, tier) into strictly disjoint QcoldQ_{\mathrm{cold}} (6,000) and QRLQ_{\mathrm{RL}} (28,215)
Cold-start pool QcoldQ_{\mathrm{cold}} & teacher6,000 questions; Gemini-2.5-pro (T=0.7T = 0.7, ≤2\le2 attempts/question; ∣DSFT∣=4,006\lvert D_{\mathrm{SFT}}\rvert= 4{,}006 accepted under Eq. (6))
Cold-start SFT epochs2 epochs
RL question pool QRLQ_{\mathrm{RL}}28,215 questions (shared identically across UNI, E2H, H2E, and SEC; disjoint from QcoldQ_{\mathrm{cold}})
Periodic validation splitOfficial WebQSP + CWQ test splits (1,628 + 3,528 = 5,156 questions, evaluated every 50 steps)
Learning rate1×10−61 \times10^{-6} (constant, AdamW)
KL divergence penalty β\beta0.01 against πref\pi_{\mathrm{ref}}
Clip ratio ϵ\epsilon / Entropy bonusϵ=0.2\epsilon= 0.2 / Entropy bonus = 0.0
Per-turn generation cap2,048 tokens
Rolling context window28,672 tokens (left truncation)
Search call budget Cmax⁡C_{\max}16 calls per episode
KG adapter ranking & capsDense encoder intfloat/e5-base-v2; max 50 relations and k=100k = 100 rows per call
Passage retrieval environmentWiki-18 dump (21,015,324 passages), E5-base-v2 + FAISS flat index, top-3 passages per call
SEC bandit parameters4 structural arms; EMA α=0.5\alpha= 0.5; Boltzmann temperature η=0.4\eta= 0.4; Qk(0)=0.5Q_k(0) = 0.5
Numerical precision & hardwarebf16 on 8 × NVIDIA A100 GPUs
Evaluation decodingGreedy decoding (T=0T = 0) across all nineteen benchmarks

Table 7. Full training, data-split, adapter, and evaluation hyperparameters for RISE.

Complete Attribution Grids Across All Nineteen Benchmarks

Tables 8–10 provide the complete nineteen-benchmark evaluation grids across all nine arms (Base model, two specialized baselines per family, and six controlled recipe variants of RISE on Qwen2.5-7B-Instruct) supporting § 3.2 and § 3.3. Across all three capability families, the full grids confirm three consistent patterns: (1) combining the protocol cold start with on-policy RL (RISE w/ UNI) outperforms either stage in isolation (RISE w/o RL and RISE w/o SFT) on every family average; (2) reversing the curriculum order (RISE w/ H2E) consistently underperforms progressive ordering (RISE w/ E2H); and (3) closed-loop variance tracking (RISE w/ SEC) achieves the highest performance on complex multi-hop composition (WebQSP, CWQ, GrailQA, HotpotQA, MuSiQue, Bamboogle) and multi-step mathematical deduction (GSM8K, MATH500, AIME24, AMC23, K&K Hard).

ArmNQTriviaQAPopQAHotpotQA2WikiMuSiQueBamboogleAvg.
Base model12.835.613.816.222.66.624.018.8
+ Search-R142.463.451.632.833.217.426.438.2
+ ZeroSearch43.665.248.834.635.218.438.440.6
RISE w/o RL32.355.337.337.336.216.338.436.1
RISE w/o SFT38.758.542.437.835.517.437.638.3
RISE w/ UNI40.162.747.638.537.618.042.441.0
RISE w/ H2E39.659.246.838.136.218.043.240.2
RISE w/ E2H42.865.451.839.239.818.844.843.2
RISE w/ SEC43.963.849.739.439.318.945.642.9

Table 9. Complete cross-tool retrieval grid for all recipe arms on Qwen2.5-7B-Instruct (RQ4), % (alias EM). RISE rows are evaluated zero-shot; Search-R1 and ZeroSearch are trained in-domain. Bold marks the best arm of each column and underline the second.

Multi-Turn Interaction Case Study

Table 11 presents a side-by-side multi-turn trajectory comparison between the base model and RISE on a multi-hop CWQ query. The example illustrates how the two policies diverge upon encountering a high-degree relation list and an error receipt: the base model issues a malformed unbracketed query and falls back to an ungrounded parametric guess, whereas RISE reformulates its query, traverses the intermediate entity node, and grounds the exact answer in the retrieved receipt.

Base Model (Qwen2.5-7B-Instruct)RISE w/ SEC (Ours)
Turn 1: <think> I need to find the birthplace of the director of Inception. </think> <search> Where was the director of [[Inception]] born? </search>Turn 1: <think> First, I should find who directed the film [[Inception]]. </think> <search> Who directed [[Inception]]? </search>
Receipt 1†: Resolved: `Inception (m.0661ql3)intent=relation_listNo single relation matched; available relations (12 of 41):film.film.directed_by, film.film.starring, film.film.country`, ... Calls remaining: 15Receipt 1: Resolved: `Inception (m.0661ql3)intent=relation_hopResults (1 of 1):Inceptionfilm.film.directed_byChristopher Nolan`. Calls remaining: 15
Turn 2: <think> The graph did not directly return the city. Let me search for Christopher Nolan’s birth city without brackets. </think> <search> birth city of Christopher Nolan </search>Turn 2: <think> The director is [[Christopher Nolan]]. Now I need to query his place of birth. </think> <search> What is the place of birth of [[Christopher Nolan]]? </search>
Receipt 2†: Error [E_NO_ENTITY]: Query must reference at least one entity in double square brackets [[...]]. Calls remaining: 14Receipt 2: Resolved: `Christopher Nolan (m.0bxtg)intent=relation_hopResults (1 of 1):Christopher Nolanpeople.person.place_of_birthLondon`. Calls remaining: 14
Turn 3: <think> I know Christopher Nolan is British-American and lived in Chicago. </think> <answer> Chicago </answer> (Ungrounded & Wrong)Turn 3: <think> The receipt confirms [[Christopher Nolan]] was born in London. </think> <answer> London </answer> (Grounded & Correct)

Table 11. Side-by-side trajectory comparison on a multi-hop CWQ instance (“Which city was the director of Inception born in?”, Topic entity: [[Inception]]). Rows marked † highlight recovery from relation-list fallback and syntax error receipts.

Proof of Proposition 1 and Two-Stage Training Algorithm

Proof of Proposition 1

Proof. If r(τi)=cr(\tau_i)=c for all i∈{1,…,G}i\in\{1,\ldots,G\}, then rˉ=c\bar{r}=c and σ^=0\hat{\sigma}=0, whence A^i=0\hat{A}_i=0 by definition and every gradient term in Eq. (7) vanishes. Under r(τ)=1−pGr(\tau)=1-p^G, the group rewards are constant if and only if all GG rollouts succeed (probability pGp^G) or all GG fail (probability (1−p)G(1-p)^G), giving Eq. (8). Differentiating f(p)=1−pG−(1−p)Gf(p)=1-p^G-(1-p)^G yields f′(p)=G((1−p)G−1−pG−1)f'(p)=G((1-p)^{G-1}-p^{G-1}), which vanishes on (0,1)(0,1) uniquely at p=0.5p=0.5, with f′′(0.5)<0f''(0.5)<0 for all G≥2G\ge2. Since f(p)f(p) and σBern(p)=p(1−p)\sigma_{\mathrm{Bern}}(p)=\sqrt{p(1-p)} are both symmetric about p=0.5p=0.5 and strictly increasing on [0,0.5][0,0.5], ff is a strictly monotone function of σBern\sigma_{\mathrm{Bern}}.

Two-Stage Training Algorithm

Algorithm 1 summarizes the complete two-stage training pipeline of RISE, combining protocol-preserving cold start on Qcold\mathcal{Q}_{\mathrm{cold}} (Stage 1) with observation-masked multi-turn GRPO and SEC learning-frontier scheduling on QRL\mathcal{Q}_{\mathrm{RL}} (Stage 2).

Algorithm 1 Two-Stage Training Pipeline of RISE with Self-Evolving Curriculum (SEC) Bandit

Input: base policy πθ0\pi_{\theta_0}; full graph G\mathcal{G} with typed adapter ΦG\Phi_{\mathcal{G}}; disjoint pools Qcold\mathcal{Q}_{\mathrm{cold}} (6,000 questions) and QRL=⋃k=14QRL(k)\mathcal{Q}_{\mathrm{RL}} = \bigcup_{k=1}^{4}\mathcal{Q}_{\mathrm{RL}}^{(k)} (28,215 questions); call budget Cmax⁡=16C_{\max} = 16; group size G=8G = 8.

Stage 1: Protocol-Preserving Cold Start

  1. Collect teacher rollouts inside ΦG\Phi_{\mathcal{G}} on Qcold\mathcal{Q}_{\mathrm{cold}} and accept DSFT\mathcal{D}_{\mathrm{SFT}} by Eq. (6), i.e. g(τ)=1g(\tau) = 1, set-equality EM, φ(τ)=1.0\varphi(\tau) = 1.0, and zt≠∅z_t \ne\emptyset for every turn.

  2. Fine-tune πθ0\pi_{\theta_0} on DSFT\mathcal{D}_{\mathrm{SFT}} to obtain the protocol-aligned checkpoint πref\pi_{\mathrm{ref}}; set θ←θref\theta\leftarrow\theta_{\mathrm{ref}} and Qk(0)←0.5Q_k(0) \leftarrow0.5 for all k∈{1,2,3,4}k \in\{1,2,3,4\}.

Stage 2: On-Policy Multi-Turn GRPO with Learning-Frontier Scheduling

  1. for step s=1,…,Sepochs = 1,\ldots,S_{\mathrm{epoch}} (440 steps) do

  2. Sample arm probabilities Ps(k)∝exp⁡(Qk(s−1)/η)P_s(k) \propto\exp(Q_k(s-1)/\eta) by Eq. (9) and draw batch Bs=⋃kBs,k\mathcal{B}_s = \bigcup_k \mathcal{B}_{s,k} of ∣Bs∣=64|\mathcal{B}_s| = 64 questions from QRL\mathcal{Q}_{\mathrm{RL}}.

  3. for each question q∈Bsq \in\mathcal{B}_s in parallel do

  4. Roll out G=8G = 8 trajectories {τi}i=1G∼πθold(⋅∣q)\{\tau_i\}_{i=1}^{G} \sim\pi_{\theta_{\mathrm{old}}}(\cdot\mid q) against ΦG\Phi_{\mathcal{G}} under the call budget Cmax⁡C_{\max}.

  5. Score r(τi)r(\tau_i) by Eq. (4), form the group pass rate pqp_q, and set A^i=(r(τi)−rˉ)/σ^\hat{A}_i = (r(\tau_i) - \bar{r})/\hat{\sigma}, with A^i=0\hat{A}_i = 0 whenever σ^=0\hat{\sigma} = 0.

  6. end for

  7. Update θ\theta by ascending the observation-masked gradient ∇θJRISE(θ)\nabla_\theta J_{\mathrm{RISE}}(\theta) of Eq. (7).

  8. For every active tier kk, compute the frontier return vˉk(s)\bar{v}_k(s) over Bs,k\mathcal{B}_{s,k} and update Qk(s)←(1−α)Qk(s−1)+αvˉk(s)Q_k(s) \leftarrow(1-\alpha)Q_k(s-1) + \alpha\bar{v}_k(s).

  9. end for

Output: interactive reasoning policy πθ∗\pi^*_\theta.

Discussion: Methodological Principles for Agentic RL

Two broader methodological principles emerge from our study. First, reward modifications must be audited alongside answer-shape-invariant diagnostics: any change to the outcome verifier that relaxes set equality or removes grounding gating (g(τ)g(\tau), § 2.3) can produce apparent gains on exact-match metrics simply by altering the length or enumeration behavior of the policy’s output. Enforcing multiplicative evidence grounding alongside strict set-equality verification is therefore essential for separating genuine search improvement from reward hacking.

Second, curriculum scheduling in group-normalized RL is fundamentally policy-indexed: as established in Proposition 1, a question contributes non-zero gradient if and only if its rollout group exhibits positive reward variance (σ^>0\hat{\sigma} > 0). Because the competence frontier (p(q;θ)≈0.5p(q;\theta) \approx0.5) shifts continuously as the policy updates and varies across model capacities, reversing the difficulty order (H2E) starves early updates of gradient, whereas progressive alignment (E2H) and online bandit tracking (SEC) keep batches anchored where the policy can actively learn.

Limitations and Future Work

We highlight three limitations that suggest directions for future work. First, under a finite call budget (Cmax⁡=16C_{\max} = 16), questions whose surfaces fail entity resolution or require complex semantic bridging beyond dense relation ranking remain unreachable; integrating adaptive entity-linking tools or hybrid graph-text retrieval within the same episode is a promising extension. Second, our curriculum experiments hold the training horizon fixed at one epoch (440 steps) to ensure clean, horizon-free attribution across all arms; exploring multi-epoch competence-frontier scheduling on larger heterogeneous tool ecosystems remains open. Third, every comparison here uses a single training run per arm, so scaling multi-seed training across larger model families (>30> 30B parameters) will further strengthen variance estimates.

Implementation Audit and Taxonomy of Silent Failures

During the development of our multi-turn agentic RL pipeline, we conducted systematic turn-level audits that uncovered 23 silent implementation defects across three categories (summarized in Table 12). Unlike traditional software bugs that raise runtime exceptions, silent failures in multi-turn RL permit training jobs to complete normally with smooth scalar reward curves while quietly degrading specific capabilities (such as single-turn termination or multi-answer grounding). Notably, our data-lineage audits also detected and removed 5 test-split leakage items embedded inside upstream community training parquets (including 3 instances carrying explicit WebQTest-* identifiers) and enforced strict train-only stratified partitioning between QcoldQ_{\mathrm{cold}} and QRLQ_{\mathrm{RL}}. We distill these into a reusable checklist to aid future agentic RL research.

Defect CategoryRepresentative Silent Failure Modes
Evaluation Instrument (3)Non-greedy validation decoding (T>0T > 0); tokenizer class mismatch upon checkpoint reload; subtle prompt-template divergence between rollout workers and standalone evaluators.
Data & Cold-Start Lineage (8)Cold-start question leakage from evaluation splits; upstream community training parquets containing test-split questions (WebQTest-*); SFT acceptance criteria looser than the RL reward gate g(τ)g(\tau); accepting teacher turns without preceding <think> blocks.
Rollout & Trainer Config (12)Binding the search call budget to the per-turn token cap; environment receipt tokens not masked in policy-gradient loss; missing stop-token strings in vLLM workers (91% wasted decoding); trainer-side right-truncation slicing <information> blocks mid-row.

Table 12. Taxonomy of 23 silent failure modes identified and resolved during our multi-turn RL pipeline audit.

References

  1. [1]Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2–3):235–256, 2002.DOI
  2. [2]Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In International Conference on Machine Learning (ICML), pp. 41–48, 2009.DOI
  3. [3]Jonathan Berant, Andrew Chou, Roy Frostig, and Percy Liang. Semantic parsing on Freebase from question-answer pairs. In Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1533–1544, 2013.DOI
  4. [4]Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: A collaboratively created graph database for structuring human knowledge. In ACM SIGMOD International Conference on Management of Data, pp. 1247–1250, 2008.
  5. [5]Antoine Bordes, Nicolas Usunier, Sumit Chopra, and Jason Weston. Large-scale simple question answering with memory networks. arXiv preprint arXiv:1506.02075, 2015.arxiv.org/abs/1506.02075
  6. [6]Thomas Carta, Clément Romac, Thomas Wolf, Sylvain Lamprier, Olivier Sigaud, and Pierre-Yves Oudeyer. Grounding large language models in interactive environments with online reinforcement learning. In International Conference on Machine Learning (ICML), pp. 3676–3713, 2023.arxiv.org/abs/2302.02662
  7. [7]Liyi Chen, Panrong Tong, Zhongning Jin, Ying Sun, Jieping Ye, and Hui Xiong. Plan-on-Graph: Self-correcting adaptive planning of large language model on knowledge graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2024.arxiv.org/abs/2410.23875
  8. [8]Mingyang Chen, Linzhuang Sun, Tianpeng Li, Haoze Sun, Yijie Zhou, et al. ReSearch: Learning to reason with search for LLMs via reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2025a.arxiv.org/abs/2503.19470
  9. [9]Xiaoyin Chen, Jiarui Lu, Ehsan Kamalloo, et al. Self-evolving curriculum for LLM reasoning. arXiv preprint arXiv:2505.14970, 2025b.arxiv.org/abs/2505.14970
  10. [10]Yongchao Chen, Yueying Liu, Junwei Zhou, Yilun Hao, Jingquan Wang, Yang Zhang, and Chuchu Fan. R1-Code-Interpreter: Training LLMs to reason with code via supervised and reinforcement learning. arXiv preprint arXiv:2505.21668, 2025c.arxiv.org/abs/2505.21668
  11. [11]Zhuo Chen, Fei Wang, Zixuan Li, Zhao Zhang, Weiwei Ding, Chuangang Yang, Yongjun Xu, Xiaolong Jin, and Jiafeng Guo. KnowCoder-A1: Incentivizing agentic reasoning capability with outcome supervision for KBQA. arXiv preprint arXiv:2510.25101, 2025d.arxiv.org/abs/2510.25101
  12. [12]Ziyang Chen, Jinzhi Liao, and Xiang Zhao. Multi-granularity temporal question answering over knowledge graphs. In Annual Meeting of the Association for Computational Linguistics (ACL), pp. 11378–11392, 2023. doi: 10.18653/v1/2023.acl-long.637.DOI
  13. [13]Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021.arxiv.org/abs/2110.14168
  14. [14]Edgar F. Codd. A relational model of data for large shared data banks. Communications of the ACM, 13(6):377–387, 1970.
  15. [15]Gheorghe Comanici, Eric Bieber, Mike Schaekermann, Ice Pasupat, Noveen Sachdeva, Inderjit Dhillon, Marcel Blistein, Ori Ram, Dan Zhang, Evan Rosen, et al. Gemini 2.5: Pushing the frontier with advanced reasoning, multimodality, long context, and next generation agentic capabilities. arXiv preprint arXiv:2507.06261, 2025.arxiv.org/abs/2507.06261
  16. [16]Runnan Fang, Shihao Cai, Baixuan Li, Jialong Wu, Guangyu Li, Wenbiao Yin, Xinyu Wang, Xiaobin Wang, Liangcai Su, Zhen Zhang, et al. Towards general agentic intelligence via environment scaling. arXiv preprint arXiv:2509.13311, 2025.arxiv.org/abs/2509.13311
  17. [17]Zhaoyan Gong, Zhiqiang Liu, Songze Li, Xiaoke Guo, Yuanxiang Liu, Xinle Deng, Zhizhen Liu, Lei Liang, Huajun Chen, and Wen Zhang. Temp-R1: A unified autonomous agent for complex temporal KGQA via reverse curriculum reinforcement learning. In Annual Meeting of the Association for Computational Linguistics (ACL), pp. 25826–25845, 2026.
  18. [19]Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Peiyi Wang, Qihao Zhu, Runxin Xu, Ruoyu Zhang, Shirong Ma, Xiao Bi, et al. DeepSeek-R1: Incentivizing reasoning capability in LLMs via reinforcement learning. arXiv preprint arXiv:2501.12948, 2025.DOI
  19. [20]Xiaoxin He, Yijun Tian, Yifei Sun, Nitesh V. Chawla, Thomas Laurent, Yann LeCun, Xavier Bresson, and Bryan Hooi. G-Retriever: Retrieval-augmented generation for textual graph understanding and question answering. In Advances in Neural Information Processing Systems (NeurIPS), pp. 132876–132907, 2024.arxiv.org/abs/2402.07630
  20. [21]Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the MATH dataset. arXiv preprint arXiv:2103.03874, 2021.
  21. [22]Xanh Ho, Anh-Khoa Duong Nguyen, Saku Sugawara, and Akiko Aizawa. Constructing a multi-hop QA dataset for comprehensive evaluation of reasoning steps. In International Conference on Computational Linguistics (COLING), pp. 6609–6625, 2020.
  22. [23]Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. In International Conference on Learning Representations (ICLR), 2020.
  23. [24]Jian Hu, Jason Klein Liu, Haotian Xu, and Wei Shen. REINFORCE++: An efficient RLHF algorithm with robustness to both prompt and reward models. arXiv preprint arXiv:2501.03262, 2025a.
  24. [25]Jingcheng Hu, Yinmin Zhang, Qi Han, Daxin Jiang, Xiangyu Zhang, and Heung-Yeung Shum. Open-Reasoner-Zero: An open source approach to scaling up reinforcement learning on the base model. arXiv preprint arXiv:2503.24290, 2025b.arxiv.org/abs/2503.24290
  25. [26]Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, et al. OpenAI o1 system card. arXiv preprint arXiv:2412.16720, 2024.arxiv.org/abs/2412.16720
  26. [27]Bowen Jin, Hansi Zeng, Zhenrui Yue, Jinsung Yoon, Sercan Ö, Arik, Dong Wang, Hamed Zamani, and Jiawei Han. Search-R1: Training LLMs to reason and leverage search engines with reinforcement learning. In Conference on Language Modeling (COLM), 2025.
  27. [28]Mandar Joshi, Eunsol Choi, Daniel S. Weld, and Luke Zettlemoyer. TriviaQA: A large scale distantly supervised challenge dataset for reading comprehension. In Annual Meeting of the Association for Computational Linguistics (ACL), pp. 1601–1611, 2017.arxiv.org/abs/1705.03551
  28. [29]Kimi Team, Angang Du, Bofei Gao, Bowei Xing, Changjiu Jiang, Cheng Chen, Cheng Li, Chenjun Xiao, Chenzhuang Du, Chonghua Liao, et al. Kimi k1.5: Scaling reinforcement learning with LLMs. arXiv preprint arXiv:2501.12599, 2025.arxiv.org/abs/2501.12599
  29. [30]M. Pawan Kumar, Benjamin Packer, and Daphne Koller. Self-paced learning for latent variable models. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1189–1197, 2010.
  30. [31]Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, Kristina Toutanova, Llion Jones, Matthew Kelcey, Ming-Wei Chang, Andrew M. Dai, Jakob Uszkoreit, Quoc Le, and Slav Petrov. Natural Questions: A benchmark for question answering research. Transactions of the Association for Computational Linguistics (TACL), 2019.
  31. [32]Valentin Lacombe, Valentin Quesnel, and Damien Sileo. Reasoning Core: A scalable RL environment for LLM symbolic reasoning. arXiv preprint arXiv:2509.18083, 2025.arxiv.org/abs/2509.18083
  32. [33]Xiaoxi Li, Jiajie Jin, Guanting Dong, Hongjin Qian, Yutao Zhu, Yongkang Wu, Ji-Rong Wen, and Zhicheng Dou. WebThinker: Empowering large reasoning models with deep research capability. arXiv preprint arXiv:2504.21776, 2025.
  33. [34]Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let’s verify step by step. In International Conference on Learning Representations (ICLR), 2024.arxiv.org/abs/2305.20050
  34. [35]Junhong Lin, Shicheng Liu, Jinyeop Song, Song Wang, Julian Shun, and Yada Zhu. Efficient and transferable agentic knowledge graph RAG via reinforcement learning. arXiv preprint arXiv:2509.26383, 2025.
  35. [36]Linhao Luo, Yuan-Fang Li, Gholamreza Haffari, and Shirui Pan. Reasoning on graphs: Faithful and interpretable large language model reasoning. In International Conference on Learning Representations (ICLR), 2024.
  36. [37]Alex Mallen, Akari Asai, Victor Zhong, Rajarshi Das, Daniel Khashabi, and Hannaneh Hajishirzi. When not to trust language models: Investigating effectiveness of parametric and non-parametric memories. In Annual Meeting of the Association for Computational Linguistics (ACL), pp. 9802–9822, 2013.
  37. [38]Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah A. Smith, and Mike Lewis. Measuring and narrowing the compositionality gap in language models. In Findings of the Association for Computational Linguistics: EMNLP, pp. 5687–5711, 2023.
  38. [39]Cheng Qian, Emre Can Akgöz, Qi He, Hongru Wang, Xiusi Chen, Dilek Hakkani-Tür, Gokhan Tur, and Heng Ji. ToolRL: Reward is all tool learning needs. In Advances in Neural Information Processing Systems (NeurIPS), 2025.
  39. [40]Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. In International Conference on Learning Representations (ICLR), 2016.arxiv.org/abs/1511.05952
  40. [41]Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves to use tools. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
  41. [42]John Schulman, Filip Wolksi, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.arxiv.org/abs/1707.06347
  42. [43]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. arXiv preprint arXiv:2402.03300, 2024.arxiv.org/abs/2402.03300
  43. [44]Guangming Sheng, Chi Zhang, Zilingfeng Ye, Xibin Wu, Wang Zhang, Ru Zhang, Yanghua Peng, Haibin Fu, Tao Tang, Ganqu Cui, Boren Zhang, Cheng Zhou, Bingquan Shen, Kai Zhang, Jun Wang, Yuxuan Hu, Yao Lu, Yufeng Cui, Yufei Wang, Zhiyu Wang, Chuyi Xu, Yuzhe Wang, Yijia Wang, Yuchen, Yong Chen, et al. HybridFlow: A flexible and efficient RLHF framework. In European Conference on Computer Systems (EuroSys), 2025.DOI
  44. [45]Huatong Song, Jinhao Jiang, Yingqian Min, Jie Chen, Zhipeng Chen, Wayne Xin Zhao, Lei Fang, and Ji-Rong Wen. R1-Searcher: Incentivizing the search capability in LLMs via reinforcement learning. arXiv preprint arXiv:2503.05592, 2025.arxiv.org/abs/2503.05592
  45. [46]Yurun Song, Xiangqing Shen, Jianfei Yu, and Rui Xia. Interactive semantic parsing with reinforcement learning for knowledge graph reasoning. In Findings of the Association for Computational Linguistics: ACL, pp. 20464–20484, 2026.
  46. [47]Hao Sun, Zile Qiao, Jiayan Guo, Xuanbo Fan, Yingyan Hou, Yong Jiang, Pengjun Xie, Yan Zhang, Fei Huang, and Jingren Zhou. ZeroSearch: Incentivize the search capability of LLMs without searching. arXiv preprint arXiv:2505.04588, 2025.arxiv.org/abs/2505.04588
  47. [48]Jiashuo Sun, Chengjin Xu, Lumingyuan Tang, Saizhuo Wang, Chen Lin, Yeyun Gong, Lionel M. Ni, Heung-Yeung Shum, and Jian Guo. Think-on-Graph: Deep and responsible reasoning of large language model on knowledge graph. In International Conference on Learning Representations (ICLR), 2024.arxiv.org/abs/2307.07697
  48. [49]Alon Talmor and Jonathan Berant. The web as a knowledge-base for answering complex questions. In Conference of the North American Chapter of the Association for Computational Linguistics (NAACL), pp. 641–651, 2018.arxiv.org/abs/1803.06643
  49. [50]Weihao Tan, Wentao Zhang, Shanqi Liu, Longtao Zheng, Xinrun Wang, and Bo An. True knowledge comes from practice: Aligning LLMs with embodied environments via reinforcement learning. arXiv preprint arXiv:2401.14151, 2024.arxiv.org/abs/2401.14151
  50. [51]Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. MuSiQue: Multi-hop questions via single-hop question composition. Transactions of the Association for Computational Linguistics (TACL), 2022.DOI
  51. [52]Ziyu Wang, Yunxiang Li, Xiaoyu Wen, Yan Song, Hanjing Wang, Linyi Yang, Mark Schmidt, Jun Wang, Weinan Zhang, Shuyue Hu, and Ying Wen. ReMA: Learning to meta-think for LLMs with multi-agent reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), pp. 140399–140445, 2025.arxiv.org/abs/2503.09501
  52. [54]Muning Wen, Ziyu Wan, Jun Wang, Weinan Zhang, and Ying Wen. Reinforcing LLM agents via policy optimization with action decomposition. In Advances in Neural Information Processing Systems (NeurIPS), pp. 103774–103805, 2024.DOI
  53. [55]Chulin Xie, Yangsibo Huang, Chiyuan Zhang, Da Yu, Xinyun Chen, Bill Yuchen Lin, Bo Li, Badih Ghazi, and Ravi Kumar. On memorization of large language models in logical reasoning. arXiv preprint arXiv:2410.23123, 2024.arxiv.org/abs/2410.23123
  54. [56]Tian Xie, Zitian Gao, Qingnan Ren, Haoming Luo, Yuqian Hong, Bryan Dai, Joey Zhou, Kai Qiu, Zhirong Wu, and Chong Luo. Logic-RL: Unleashing LLM reasoning with rule-based reinforcement learning. arXiv preprint arXiv:2502.14768, 2025.arxiv.org/abs/2502.14768
  55. [57]Shuwen Xu, Yao Xu, Jiaxiang Liu, Chenhao Yuan, Wenshuo Peng, Jun Zhao, and Kang Liu. Graph-Walker: Agentic knowledge graph question answering via synthetic trajectory curriculum. In Conference on Language Modeling (COLM), 2026.arxiv.org/abs/2603.28533
  56. [58]Zhenghai Xue, Longtao Zheng, Xuefeng Hu, Zheng Liu, Hao Xu, Shuai Zhang, Pengjun Liu, Yaohua Wang, and Xinyu Zhu. SimpleTIR: End-to-end reinforcement learning for multi-turn tool-integrated reasoning. In International Conference on Learning Representations (ICLR), 2026.arxiv.org/abs/2509.02479
  57. [59]Shiqi Yan, Yubo Chen, Ruiqi Zhou, Zhengxi Yao, Shuai Chen, Tianyi Zhang, Shijie Zhang, Wei-Qiang Zhang, Yongfeng Huang, Haixin Duan, and Yunqi Zhang. Explore-on-Graph: Incentivizing autonomous exploration of large language models on knowledge graphs with path-refined reward modeling. In International Conference on Learning Representations (ICLR), 2026.arxiv.org/abs/2602.21728
  58. [60]Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W. Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. HotpotQA: A dataset for diverse, explainable multi-hop question answering. In Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 2369–2380, 2018.arxiv.org/abs/1809.09600
  59. [61]Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. ReAct: Synergizing reasoning and acting in language models. In International Conference on Learning Representations (ICLR), 2023.arxiv.org/abs/2210.03629
  60. [62]Wen-tau Yih, Matthew Richardson, Christopher Meek, Ming-Wei Chang, and Jina Suh. The value of semantic parse labeling for knowledge base question answering. In Annual Meeting of the Association for Computational Linguistics (ACL), pp. 201–206, 2016.DOI
  61. [63]Peng Yu, Cheng Deng, Beiya Dai, Luoyi Fu, Xinbing Wang, Guihai Chen, and Ying Wen. KaLM: Knowledge-aligned autoregressive language modeling via dual-view knowledge graph contrastive learning. Frontiers of Computer Science, 21(2):2102348, 2026a. doi: 10.1007/s11704-026-50906-6.
  62. [64]Peng Yu, Zeyuan Zhao, Shao Zhang, Luoyi Fu, Xinbing Wang, and Ying Wen. Structured in-context environment scaling for large language model reasoning. In International Conference on Learning Representations (ICLR), 2026b.arxiv.org/abs/2509.23330
  63. [65]Qiying Yu, Zheng Zhang, Ruofei Zhu, Yufeng Yuan, Xiaochen Zuo, Yu Yue, Weinan Dai, Tiantian Fan, Gaohong Liu, Lingjun Liu, et al. DAPO: An open-source LLM reinforcement learning system at scale. arXiv preprint arXiv:2503.14476, 2025.arxiv.org/abs/2503.14476
  64. [66]Weihao Zeng, Yuzhen Huang, Qian Liu, Wei Liu, Keqing He, Zejun Ma, and Junxian He. SimpleRL-Zoo: Investigating and taming zero reinforcement learning for open base models in the wild. arXiv preprint arXiv:2503.18892, 2025.arxiv.org/abs/2503.18892
  65. [67]Shao Zhang, Xihui Wang, Wenhao Zhang, Chaoran Li, Junru Song, Tingyu Li, Lin Qiu, Xuezhi Cao, Xunliang Cai, Wen Yao, et al. Leveraging dual process theory in language agent framework for real-time simultaneous human-AI collaboration. arXiv preprint arXiv:2502.11882, 2025.arxiv.org/abs/2502.11882
  66. [68]Chujie Zheng, Shixuan Liu, Mingze Li, Xiong-Hui Chen, Bowen Yu, Chang Gao, Kai Dang, Yuqiong Liu, Rui Men, An Yang, et al. Group sequence policy optimization. arXiv preprint arXiv:2507.18071, 2025a.arxiv.org/abs/2507.18071
  67. [69]Yuxiang Zheng, Dayuan Fu, Xiangkun Hu, Xiaojie Cai, Lyumanshan Ye, Pengrui Lu, and Pengfei Liu. DeepResearcher: Scaling deep research via reinforcement learning in real-world environments. arXiv preprint arXiv:2504.03160, 2025b.arxiv.org/abs/2504.03160

Paper details

vlnc:W_rktnvzjg
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents