acceptodds
Under review as a conference paper at ICLR 2027

Which Steps Matter? Graph-Guided Selection for Single-Step Reinforcement Learning

Abstract

Reinforcement learning for long-horizon agents often requires generating complete interaction trajectories before obtaining a training signal. Repeated reasoning, tool calls, and environment responses make this process expensive, even when the decision of interest occurs much earlier. We propose KStep, a framework that concentrates policy optimization at structurally important decision contexts. From existing trajectories, KStep constructs local state-transition graphs and scores intermediate landmarks by the relative loss of connectivity after their removal. Selected steps become single-step reinforcement learning tasks: the policy receives the full recorded prefix, samples a group of next-turn responses, and updates using group-relative advantages from a reference-action matching reward. Unlike ATLaS, which applies supervised fine-tuning to selected steps, this procedure optimizes newly sampled actions without completing the remaining trajectory. The framework accommodates mathematical reasoning and ALFWorld through domain-specific state adapters. On AIME, KStep exceeds an ATLaS-selection-plus-single-step-RL baseline on two backbones by 3.06 and 1.60 macro-average percentage points. On ALFWorld’s seen split, the corresponding success-rate gains are 6.43 and 3.58 points. Full-rollout GRPO achieves higher final-task performance on both domains. The resulting formulation separates where an agent practices from how its sampled decisions are optimized.

Primary area:
reinforcement learning
Keywords:
large language model

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_bmBGOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes a graph-based approach for identifying critical decision points within a dataset of sequential-decision-making trajectories, and proposes to apply “single-step reinforcement learning” to train a policy only at these points, which is more data and compute-efficient than standard RL because the policy does not need to be rolled out for complete trajectories. The paper describes a method for defining “local rewards” based on sampling multiple potential responses from the policy. It evaluates its approach on AlfWorld and AIME, which are appropriate LLM decision-making benchmarks. The main baseline, “ATLaS + Single Step RL” is in essence an ablation of their step selection mechanism; swapping in a different mechanism proposed in a prior work that treats a different problem setup. All approaches perform worse than standard GRPO (GRPO is not single-step RL, so it may be more data/compute intensive).

Critical strengths

The paper reports evaluation results on well-known benchmarks, and includes comparison against GRPO, a well-known approach to training language models.

Critical weaknesses

1.The most important part of the paper is the graph-based method to determine the key decision points, but the graph construction process (e.g. how to determine the set of vertices given a dataset of trajectories) is not described in the main paper. Near the start of section 3.2 the paper says “Abstract states form nodes of G_q=(V_q,E_q)” and the end of section 3.1 says “The selector uses abstract states x_t = phi(h_t)” but this mapping phi, which I assume quotients the trajectories into abstract states, is not described in the paper. Understanding how the graph is constructed is crucial to understanding the method.

  1. The utility of the method is not well motivated. It does outperform the so-called baseline “ATLaS + Single Step RL”, but “ATLaS + Single Step RL” is introduced in this paper. GRPO outperforms all approaches. The authors need to motivate their method by either 1. citing a previous “single step RL” paper (if one exists) and showing that their approach is better 2. exceeding the performance of orthodox approaches (like GRPO) or 3. coming close to the performance of orthodox approaches (like GRPO) with much less data or computation.

  2. The paper’s presentation is weak. For example, the start of section 3 does not start with a clean succinct problem setup, instead it builds up the method bit by bit, with minimal signposting, making it hard to follow (especially since some parts, like how the graph nodes are determined, are not explained). Also, the “Baselines” section 4.3 mentions ReAct and Reflexion but these are not compared against empirically. The authors should move these to “Related Work” if they are not going to provide an empirical baseline.

Questions for authors
  1. How are the nodes of the graph determined? What is the mapping phi?
  2. Why is the “local reward” scheme well-motivated? It seems to give high rewards to syntactically correct generations that are similar to those that would be emitted by the “old” policy. But is there anything that encourages them to lead to desirable behavior in future steps?
  3. Are there previous works that treat “single-timestep RL” as you have set it up? How do they define their reward functions? If there do not exist any, can you provide evidence that this paradigm is useful?
Reviewer_ML9zOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes KStep which is a graph-guided framework designed for improving long-horizon LLM agents through single-step RL. By using a landmark-deletion importance score that measures their contribution to successful task completion, KStep constructs local state-transition graphs from recorded trajectories and identifies critical decisions. At selected key steps, to avoid expensive full-trajectory rollouts, the policy samples alternative responses and is optimized using reference-action matching rewards and Group Relative Policy Optimization (GRPO). Experiments on AIME and ALFWorld demonstrate consistent improvements over an ATLaS-based single-step RL baseline across two Qwen models. The results suggest that graph-guided step selection enables targeted policy optimization, but its computational efficiency and generalization benefits remain insufficiently validated.

Critical strengths
  1. The paper's major strength is its interpretable graph-guided selection mechanism integrated with a practical single-step RL framework. The approach addresses an important computational challenge in training long-horizon LLM agents and demonstrates consistent improvements over a relevant selection baseline.

  2. KStep introduces a single-step RL framework that optimizes decisions at selected historical contexts without regenerating complete trajectories. This is particularly interesting for LLM agents involving expensive tool calls and lengthy reasoning processes.

  3. The paper constructs an ATLaS-based baseline that uses the same single-step RL optimization procedure as KStep, rather than comparing only against the original ATLaS selective-SFT method. This comparison helps isolate the contribution of the graph-based selection mechanism from the effects of changing the training objective.

Critical weaknesses
  1. The framework primarily integrates existing techniques: "critical-step selection" (derived from ATLaS), "graph-based landmark identification" (drawn from classical planning and reinforcement learning), and the GRPO algorithm for policy optimization. While the "landmark-deletion score" proposed in the paper offers a concrete metric for structural importance, the core concept of "identifying bottleneck states" is already well-established. The paper fails to clearly articulate how its graph-based metric outperforms existing alternatives, nor does it demonstrate that it represents a substantive advancement.

  2. The "landmark importance" metric proposed in the paper aims to quantify the extent to which the "probability mass of successful paths" relies on a given intermediate state. However, structural importance is not synonymous with importance for training. Certain critical states may already be reliably covered (i.e., consistently reached) by the current policy, whereas other states—though structurally less significant—might present greater decision-making challenges and, consequently, offer more room for improvement. The paper provides neither theoretical guarantees nor empirical evidence to establish a link between "landmark importance" and the "expected gains from policy optimization." Therefore, equating "landmark importance" directly with "policy optimization gains" is unjustified.

  3. In the experimental evaluation, KStep is compared only against an ATLaS-based selection method within the same single-step reinforcement learning framework. Several significant baselines—such as random step selection, graph-cut-based selection, and uncertainty-based selection—are omitted. Without these comparisons, it is difficult to determine whether the proposed "landmark-deletion" metric is truly effective, or if similar improvements could be achieved through simpler selection strategies.

  4. The experiments are limited to only two benchmarks, AIME and ALFWorld; furthermore, the evaluation on ALFWorld is restricted to just 140 "seen tasks." Given that these two benchmarks are often regarded in academia as simple, "toy-level" tasks, it is necessary for the authors to evaluate their proposed method on more challenging benchmarks.

  5. One of the primary motivations for KStep is to reduce the computational cost of full-trajectory reinforcement learning (RL). However, the paper fails to provide a comprehensive comparison regarding metrics such as training time, GPU utilization, or token consumption. Furthermore, processes like graph construction, trajectory retrieval, state abstraction, and milestone scoring inherently introduce additional computational overhead. In the absence of more thorough data on these costs, the claim of "computational efficiency" remains unsubstantiated.

  6. The quality of the writing requires significant improvement. Several concepts and terms are not clearly defined at the outset, which hinders comprehension; moreover, the presentation of the content lacks effective pedagogical guidance.

Questions for authors
  1. The proposed landmark-deletion score measures the contribution of an intermediate state to successful-path connectivity. What theoretical or empirical evidence supports the assumption that states with higher structural importance offer greater potential for policy improvement?

  2. The single-step reward measures structural similarity to recorded reference actions rather than actual task outcomes. So, if there are alternative actions that differ from the reference but are equally or more effective, how does KStep handle this kind of actions? What evidence shows that the reward encourages meaningful policy improvement rather than primarily reinforcing imitation?

  3. What are the end-to-end computational costs of KStep compared with full-trajectory GRPO, including trajectory retrieval, graph construction, state abstraction, landmark scoring, and policy optimization?

  4. How sensitive is KStep to the quality of state abstraction, the completeness of retrieved successful trajectories, and graph-construction hyperparameters?

  5. The local graphs are constructed exclusively from successful trajectory support. Could this introduce survivorship bias by overlooking decisions associated with unsuccessful trajectories, which may be particularly valuable for policy improvement?

Reviewer_zTAsOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes KStep, which selects training steps from a bank of recorded trajectories and trains on them one turn at a time. It builds local state-transition graphs from successful trajectories of other tasks. Each intermediate "landmark" is scored by the fraction of successful path mass that disappears when it is deleted. Top-scoring steps become single-step RL tasks. Given the full recorded prefix, the policy samples m next-turn responses, scored by similarity to the recorded reference action, and is updated with GRPO.

The method is evaluated on AIME 24/25/26 and ALFWorld, showing performance gain over another single-step RL method ATLaS.

Critical strengths
  • The idea of selecting key steps from the graph connectivity between trajectories makes sense and the selection score is well-defined and analyzed.
  • The motivation of replacing expensive multi-turn RL with carefully selected single-turn RL is sound.
Critical weaknesses
  • The experiment setup is unclear and cannot be reproduced or interpreted. No training set is reported for the math reasoning setting, and all 90 problems from AIME 24/25/26 seem to be used for evaluation. It is also unclear whether the math task is single-turn or tool-integrated, whether a sandbox executes code, where the trajectory bank comes from, and how traces are segmented and compiled into graph states. The scoring hyperparameters (k, H_s, H, ζ, B, r) have no values.
Questions for authors
  • Please clarify how the experiments are ran, what is the training set, what is the environment and what are the hyperparameters.
  • Where do the trajectories for selection come from?
  • How is the graph for the math reasoning setting built?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.