Interactive Structured Environment Scaling for Large Language Model Agentic Reasoning
Organizations: Department of Computer Science and Engineering, Shanghai Jiao Tong University · School of Artificial Intelligence and John Hopcroft Center, Shanghai Jiao Tong University
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.
Figures & tables
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
| Input: base policy ; full graph with typed adapter ; disjoint pools ( questions) and ( questions); call budget ; group size . | |
|---|---|
| Stage 1: Protocol-Preserving Cold Start | |
| 1: | Collect teacher rollouts inside on and accept by Eq. ( 6 ), i.e. , set-equality EM, , and for every turn. |
| 2: | Fine-tune on to obtain the protocol-aligned checkpoint ; set and for all . |
| Stage 2: On-Policy Multi-Turn GRPO with Learning-Frontier Scheduling | |
| 3: | for step ( steps) do |
| 4: | Sample arm probabilities by Eq. ( 9 ) and draw batch of questions from . |
RL for Language Model Reasoning
Reinforcement learning for language model reasoning uses reward-driven training to improve multi-step problem solving, tool use, and reliable answers.
See all 1,164 papers