acceptodds
Under review as a conference paper at ICLR 2027

Learning Before the First Success: Bidirectional Progress-Guided Training from Failed Cyber Interactions

Abstract

Training large language model (LLM) agents on difficult interactive tasks faces a bootstrapping barrier: when no rollout succeeds, terminal rewards make distinct failures indistinguishable. We study how failed interactions can still drive learning before the first complete solution. We introduce Bi-PGSD, a bidirectional progress-guided framework that pairs execution-verified forward effects with backward goal reasoning to construct locally checkable objectives. These objectives provide environment-anchored rewards for policy updates; target-side validation enables cross-task reuse; and, after a complete path is independently reproduced, retrieval and intermediate guidance are progressively withdrawn to consolidate autonomous behavior. Under a fixed computation budget, Qwen3.5-9B on Cybench strict zero-success (Z) improves first-success discovery from 50.0% with strong-summary retrieval to 62.5%. On scaffold-free Cybench family-held-out tasks, the trained policy improves complete-task success by 10.3 percentage points over the initial policy. Across mechanism and transfer controls, the results show that failed trajectories become useful training signals when local effects are both verified and directed toward the terminal goal.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
cyber+agent

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_bB8HOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates how LLM-based cybersecurity agents can learn from failed interactions before discovering their first complete solution. It proposes Bi-PGSD, a framework combining execution-verified forward effects, backward goal reasoning, local reward-based policy updates, cross-task experience reuse, and progressive scaffold withdrawal. Experiments across several cybersecurity benchmarks demonstrate improvements in first-success discovery, experience transfer, and scaffold-free task completion.

Critical strengths
  1. The paper addresses an important practical challenge in training LLM agents under sparse terminal rewards. Extracting verifiable local progress from unsuccessful trajectories is a meaningful direction.

  2. The evaluation spans multiple cybersecurity benchmarks and model families, with extensive mechanism ablations and cost accounting. The results provide useful evidence that verified local experience and goal-directed exploration can improve agent performance.

Critical weaknesses
  1. The proposed framework mainly integrates established techniques, including hindsight-style goal relabeling, verified experience memory, backward planning, local policy optimization with RLOO, and curriculum-based self-training. While their integration is reasonable, the paper offers limited methodological innovation beyond combining these existing components.

  2. On Cybench, filtered local SFT already achieves 41.4% success, compared with 44.7% for the full framework. This relatively small additional gain raises questions about whether the proposed local RL machinery is necessary, particularly given the additional training and verification complexity.

  3. Although the paper highlights a 62.5% versus 50.0% first-success result on Cybench-Z, it also reports that the average improvement across six trainable-policy candidates on CTF tasks is only 1.4 percentage points under matched end-to-end budgets. Maintenance accounts for 55.2% of the total cost, and the method performs worse at smaller budgets. The practical cost-effectiveness of the full framework therefore remains uncertain.

  4. The method improves performance on several tasks, but the gains are not uniform. In particular, success-assisted InterCode-CTF results are consistently worse than strong-summary retrieval for multiple models. These negative results suggest that the framework is not universally beneficial, and the conditions under which its additional complexity is worthwhile require clearer characterization.

Questions for authors
  1. Can the authors provide a more direct comparison against a simpler framework combining verified failed-fragment retrieval, local SFT or RLOO, and standard task scheduling, under identical computational budgets?

  2. Given the relatively small improvement over filtered local SFT, what evidence establishes that local RL is essential rather than merely an incremental addition?

  3. How do the authors explain the consistent performance degradation on success-assisted InterCode-CTF, and can they characterize when Bi-PGSD is expected to outperform simpler retrieval-based methods?

  4. How robust is the framework when reliable local checkers, environment resets, or reproducible intermediate states are unavailable?

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

This paper addresses the cold-start problem that LLM agents face on difficult cyber tasks: when all rollouts fail, the terminal reward cannot distinguish among failures of different quality, leaving the policy unable to learn from them. It proposes Bi-PGSD (Bidirectional Progress-Guided Subgoal Discovery). The core idea has three layers: (1) forward effect verification, extracting execution-verified local transition records from failed trajectories into a scoped knowledge base; (2) backward goal reasoning, regressing from the terminal goal to local candidate conditions, combined with forward verification evidence to form a local reward signal; (3) progressive scaffold withdrawal, after an independent reproduction of a complete path, gradually removing retrieval and prompts to transfer scaffold-assisted success into an autonomous policy. Training combines a KL-regularized RLOO gradient estimator with SFT. Experiments across six cyber benchmarks show that under the strict zero-success (Z) condition, first-success discovery rises from 50.0% to 62.5%, and scaffold-free held-out task success improves by 10.3% points.

Critical strengths
  1. Clear problem definition and motivation. The paper articulates the GRPO defect that "all-failure groups yield zero reward advantage," and quantifies the severity of this issue with controlled experiments in Section 3 (sampling, random action, terminal-RL comparison), where terminal-RL achieves only 4.2% first-success. This is more convincing than a verbal claim that "sparse reward is hard."

  2. Sound three-stage controlled design (Section 3) Section 3 decomposes the problem into three independently falsifiable sub-questions: whether failed trajectories contain reusable information (3.1), whether experience reuse equates to goal progress (3.2), and whether backward reasoning needs execution verification (3.3). Each step has its own control group, forming an empirical foundation for the method.

  3. Clean separation of local objectives from the terminal verifier. The paper consistently maintains the distinction between local success (Vp) and terminal success (Vi), avoiding the reward leakage common in hindsight relabeling. Target-side validation, which reverifies applicability before cross-task sharing, is a substantive improvement over HER and Voyager.

  4. Multi-stage evaluation protocol aligned with the framework's goals The three-stage evaluation (first-success discovery → cross-task transfer → scaffold-free held-out) directly corresponds to Bi-PGSD's three design goals. The evaluation follows the method's logic rather than reporting numbers in isolation.

Critical weaknesses

W1. Low absolute numbers and insufficient statistical significance. The core result, 62.5% vs 50.0% (Z condition), is a 12.5pp improvement, but on a benchmark like Cybench this may correspond to only a handful of samples (the public Cybench has roughly 40 tasks). The paper reports no standard errors, confidence intervals, or statistical tests, so it is impossible to judge whether this gain exceeds random fluctuation. The 10.3pp held-out improvement likewise lacks error estimates. This is the most serious concern.

  1. Opaque computation cost Bi-PGSD introduces substantial additional overhead over the baselines: backward goal reasoning, local task sampling, target-side validation replay, and the progressive schedule. The paper claims comparison "under a fixed computation budget" but does not specify the budget magnitude, the actual token/GPU allocation across components, or how much the baseline would improve given the same extra budget. This makes efficiency impossible to assess.

  2. Insufficient evaluation of backward reasoning reliability Section 3.3 and Appendix A.5 note that deeper backward chains accumulate more error, but the main text reports neither the average backward depth used in practice nor the fraction of the backlog occupied by erroneous conditions. There is no quantitative analysis of quality control for LLM-generated backward hypotheses, resulting in the most fragile component of the framework.

  3. Limited model selection All core experiments run on Qwen3.5-9B. Cyber tasks have high demands on context length and tool-calling ability, and a 9B model is comparatively weak in this domain and not directly comparable to the larger models (GPT-4 family, Claude 3, etc.) used by related work. There is no validation on a stronger backbone.

  4. Writing clarity could be improved Section 4 has high symbol density. Equations (2)–(5) introduce many custom symbols (ξ, P, ω, E, VE, L, µb, Hb, Vp, etc.) and immediately move into technical detail, which is not reader-friendly. Figure 2, the framework's central diagram, has too brief a caption and lacks data-flow explanation. Some key design choices (such as the exact target-side validation procedure) are scattered across the appendix with insufficient description in the main text. Additionally, I highly suspect that the font of the article differs from the official template, and I am concerned about whether this violates the formatting constraints.

  5. Incomplete related work The paper cites HER, Reflexion, Voyager, etc., but misses several recently relevant directions: (a) systematic work on process reward models (PRMs) and dense reward shaping in LLM training; (b) LLM-agent skill/tool learning (e.g., ToolBench, MetaGPT); (c) whether analogous bidirectional search has been studied in goal-conditioned RL outside the cyber domain (e.g., backward induction in model-based RL). These gaps weaken the precision of the contribution's positioning.

Questions for authors
  1. In the Z-condition experiment (62.5% vs 50.0%), what is the task sample size? Can you provide bootstrap confidence intervals or a McNemar test? If it is 40 tasks, is a difference of 8/40 vs 10/40 statistically significant?

  2. Which model performs the backward goal regression? The same Qwen3.5-9B as the actor, or a separate model? What is the prompt format for generating candidate conditions, and what is the average number of candidates? What does the distribution of backward-reasoning depth used in the experiments look like?

  3. What is the cost of target-side validation? When an effect record from task A is used in task B, the re-execution must replay in task B's environment, which itself consumes exploration budget. How is this overhead accounted for in the "fixed computation budget" comparison?

  4. What is the substantive difference between the progressive scaffold withdrawal (Section 4.4) and the Ross et al. 2011? What is the criterion for when to withdraw? Does training diverge if withdrawal happens too early?

  5. Are results for all six benchmarks reported in the main text? The main text currently shows mostly Cybench numbers. Where are the complete results for the other five benchmarks?

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

This paper proposes a method to handle sparse reward in LLM post-training by generating subtasks which are relatively easier than the original problems. This resolves the problem of zero-advantage in popular post-training algorithms like GRPO.

Critical strengths

None

Critical weaknesses
  • The core method is missing, it is not clear how these intermediate goals are extracted and set up.
  • Many of the relevant works such as process reward models are not cited.
  • Paper does not comply with ICLR formatting, it uses incorrect font, and title's boldness etc.
  • Many figures/tables are low quality.
  • Paper is hard to read, paragraphs are dense and often disconnected from each other.
Questions for authors

None

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.