acceptodds
Under review as a conference paper at ICLR 2027

Re:Zero: Learning from Failed Trajectories through Verified Behavioral Recomposition

Abstract

Failure-only rollout groups represent a supervision dead end for group-based agentic RL: they offer no successful demonstrations, and under binary rewards their group-relative advantages vanish. Yet these failed trajectories often harbor complementary, useful sub-behaviors. We introduce Re:Zero, a framework that converts all-fail groups into verifiable supervision without additional policy decoding. Given an all-fail group, Re:Zero replays and simplifies failed trajectories, then forms bounded prefix–fragment recompositions by splicing a source prefix with a contiguous donor fragment across different positions. A completion-aware search evaluates candidates within a fixed interaction budget, retaining solely executions that reproduce native environment success (or satisfy a strict score threshold). The policy then learns continuation actions grounded in the replayed observation history, masking the shared prefix to prevent credit confusion. Experiments across ALFWorld, WebShop, ScienceWorld, and Visual Sokoban with models from 1.7B to 27B demonstrate that Re:Zero consistently improves base group-RL algorithms at zero extra policy decoding cost during training, preserving the base deployment pipeline.

Primary area:
reinforcement learning
Keywords:
agentic rl

Reviews

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

This paper proposes Re:Zero, a framework for learning from all-fail rollout groups in agentic reinforcement learning. To address the lack of effective learning signals from unsuccessful trajectories, Re:Zero recomposes action fragments from different failed rollouts and verifies the resulting trajectories through environment replay. The verified trajectories are subsequently used for continuation-only supervised learning, while preserving the original reinforcement learning objective.

Experiments are conducted across ALFWorld, WebShop, ScienceWorld, and Visual Sokoban, using models ranging from 1.7B to 27B parameters. The results demonstrate that Re:Zero consistently improves GRPO and GiGPO without requiring additional policy decoding.

Critical strengths
  1. Effective supervision recovery from failed trajectories. Re:Zero introduces a practical approach to exploiting complementary behaviors across all-fail rollout groups. By recomposing action fragments and verifying them through environment replay, the method constructs additional training supervision without requiring extra policy decoding. The continuation-only learning objective also provides a reasonable mechanism for avoiding incorrect credit assignment to unsuccessful prefixes.

  2. Extensive experimental evaluation and ablation studies. The paper evaluates Re:Zero across multiple benchmarks, model scales, and reinforcement learning algorithms, demonstrating consistent performance improvements. The ablation studies on trajectory recomposition, verification, continuation learning, and search strategies provide meaningful evidence supporting the effectiveness of the proposed components.

Critical weaknesses
  1. Ambiguity in verification criteria and implementation details. Although Re:Zero emphasizes learning from environment-verified successful trajectories, WebShop and ScienceWorld accept recomposed trajectories with scores above a threshold of 0.8, which does not necessarily correspond to full task completion. In WebShop, the original binary RL reward requires a task score of 1.0. Therefore, some accepted trajectories may not represent genuine successes under the original task objective. Additionally, the completion-queue construction described in Appendix C is insufficiently explained in the all-fail setting, particularly regarding how goal-completing actions can be identified from unsuccessful donor trajectories.

  2. Limited generalization evidence and statistical validation. The experiments are conducted entirely in deterministic, resettable environments, leaving the applicability of Re:Zero to stochastic or more complex interactive environments insufficiently explored. Moreover, the paper does not report performance variations across multiple independent training seeds or provide confidence intervals. Some improvements are relatively modest, such as the increase from 42.2% to 44.5% on Visual Sokoban, making their statistical significance unclear. Although Re:Zero avoids additional policy decoding, it introduces substantial environment replay overhead, which may limit its efficiency in computationally expensive environments.

Questions for authors
  1. Motivation for Joint RL and SFT Optimization. Figure 1 shows that all-fail rollout groups are particularly prevalent during the early stages of training, which may reflect limitations in sparse reward signals or the initial policy's capabilities. Why do the authors choose to address this issue by introducing an auxiliary SFT objective during RL, rather than exploring more informative reward designs or stronger SFT initialization?More importantly, since the verified recomposed trajectories are used exclusively for continuation-only SFT and do not directly contribute to the RL policy loss, the necessity of integrating this mechanism into the RL training process remains unclear. Could the authors compare the proposed joint optimization approach with an alternative that constructs verified trajectories offline, performs SFT, and subsequently conducts standard RL? Such a comparison would help clarify whether the improvements arise from the online integration with RL or simply from additional high-quality supervised data.

  2. Verification Criteria. In WebShop and ScienceWorld, Re:Zero accepts recomposed trajectories with scores above 0.8. What proportion of these trajectories actually satisfy the original task success criteria? Could the authors provide additional results using strict task completion as the verification condition?

  3. Completion Queue Construction. Appendix C describes the completion queue as containing fragments whose final actions satisfy task goals. However, these fragments originate from all-fail rollout groups. Could the authors clarify how such completion actions are identified and how the completion queue is constructed in practice?

  4. Generalization and Computational Efficiency. How would Re:Zero extend to stochastic environments where exact trajectory replay is unavailable? Furthermore, although the paper provides matched environment-step comparisons, could the authors evaluate the method under matched total training time or computational budgets to better demonstrate its overall efficiency?

If the aforementioned Questions are all resolved, I will consider raising my rating.

5 comments
AuthorsOpenReview ↗

Response to Reviewer Kpgb (Part A)

We thank Reviewer Kpgb for the constructive feedback. Below, we address every question across Parts A, B, and C. In the revised PDF, verification and multi-seed updates are highlighted in purple, queue specifications in teal, and scaling analyses in blue.

Critical Weakness 1 & Question 2 (Verification Criteria: Threshold 0.8 vs. Strict Completion 1.0)

1. Distinguishing Auxiliary Acceptance (0.8) from Native Task Success (§3.4 & App. C)

Across all benchmarks, reported test success rates require native task completion (score=1.0\text{score}=1.0), while WebShop and ScienceWorld additionally report normalized task scores. On WebShop, the base RL reward remains binary (1010 if score=1.0\text{score}=1.0, else 00; ScienceWorld retains its native shaped RL return). The threshold τ(rescue)=0.8\tau(\text{rescue})=0.8 governs only which replayed continuations enter the auxiliary continuation loss L(cont)\mathcal{L}(\text{cont}). In Section 3.4 and Appendix C, we strictly reserve "verified strict successes" for native 1.01.0 completions and refer to accepted episodes scoring in [0.8,1.0)[0.8, 1.0) as "environment-validated high-score continuations."

2. Proportion of Strict (1.0) vs. High-Score ([0.8, 1.0)) Trajectories & Concrete Case (§4.3 & App. C)

Auditing the 150-step Qwen3-1.7B runs on WebShop (883 eligible all-fail pools, 319 rescued pools [36.1%] yielding 345 accepted episodes) and ScienceWorld (H=30H=30; 1,120 pools, 324 rescued pools [28.9%] yielding 348 accepted episodes) confirms that the majority of accepted episodes achieve native strict completion (score=1.0\text{score}=1.0):

Source of Accepted Episodes (Qwen3-1.7B Audit)Accepted EpisodesStrict (1.0)High-Score [0.8, 1.0)Strict Share
WebShop: Single-Parent Cleanup (40 pools, 4.5%)400400.0% (0/40)
WebShop: Cross-Parent Recomposition3052168970.8% (216/305)
WebShop Total (from 319/883 rescued pools, 36.1%)34521612962.6% (216/345)
ScienceWorld Total (from 324/1,120 rescued pools, 28.9%)34818915954.3% (189/348)
  • 70.8% of Recompositions Are Native Strict Successes (Score=1.0\text{Score}=1.0): None of the 40 cleanup-only episodes reached 1.01.0, whereas 70.8% (216/305) of cross-trajectory recomposed episodes on WebShop and 54.3% (189/348) on ScienceWorld achieved exact 1.01.0 completion.
  • Concrete Strict-Success Trace (Score 0.6 + 0.8 →\to Strict 1.0): On "Buy women's pumps in leopard color, size 9, priced under USD 80", Failed Parent A opened valid pumps under USD 80 but clicked checkout without selecting options (score=0.6\text{score}=0.6, reward =0=0). Failed Parent B visited a wrong shoe page, executed click[leopard], click[9], and click[buy now] (score=0.8\text{score}=0.8, reward =0=0). Splicing Parent B's option-selection and checkout fragment onto Parent A's prefix produced a native strict success (score=1.0\text{score}=1.0) under replay.

3. Full 150-Step Training: Strict Completion Only (1.0) vs. Threshold (0.8) (§4.3)

We trained Qwen3-1.7B for 150 steps across 3 independent seeds on WebShop and ScienceWorld (128 held-out test tasks):

Condition (Qwen3-1.7B, 3 Seeds, /128)WS Score (%)WS Strict Succ (%)SW Score (%)SW Strict Succ (%)
Base GiGPO79.9±0.979.9\pm0.962.76±1.1962.76\pm1.19 (79,82,80)34.1±0.934.1\pm0.919.27±1.1919.27\pm1.19 (23,26,25)
Re:Zero (Gate = 1.0, Strict Only)82.5±0.882.5\pm0.867.71±1.1967.71\pm1.19 (85,88,87; +4.95 pp)37.8±0.837.8\pm0.824.74±1.1924.74\pm1.19 (30,33,32; +5.47 pp)
Re:Zero (Gate = 0.8, Default)83.3±0.983.3\pm0.969.53±1.5669.53\pm1.56 (87,91,89; +6.77 pp)39.4±0.939.4\pm0.926.56±1.5626.56\pm1.56 (32,36,34; +7.29 pp)
  1. Strict Completions Alone (Gate = 1.0) Retain >73% of the Downstream Gain: Accepting solely score=1.0\text{score}=1.0 targets improves strict test completion by +4.95 pp on WebShop (62.76%→67.71%62.76\%\to 67.71\%) and +5.47 pp on ScienceWorld (19.27%→24.74%19.27\%\to 24.74\%).
  2. Role of [0.8, 1.0) Continuations (+1.82 pp): On harder tasks where no single splice satisfies every attribute simultaneously, [0.8,1.0)[0.8, 1.0) trajectories capture verified high-progress sub-behaviors (reaching target categories, selecting required attributes, executing checkout), while the base RL reward (1010 iff score=1.0\text{score}=1.0) reinforces only strict 1.01.0 completions during on-policy rollouts.
AuthorsOpenReview ↗

Response to Reviewer Kpgb (Part B)

Critical Weakness 1 & Question 3 (Completion Queue Construction, §3.3 & App. C, in teal)

We have formalized the queue construction rules in Section 3.3 and Appendix C: a donor rollout in an all-fail group never completed the full task, and completion-queue (Q(comp)\mathcal{Q}(\text{comp})) membership never assumes donor success. Rather, with probability 1−ϵ=0.81-\epsilon = 0.8, search prioritizes Q(comp)\mathcal{Q}(\text{comp}) using syntactic terminal or goal-delivery action patterns:

  • WebShop (click[buy now]): A donor rollout fails when it purchases an item with mismatched attributes, yet its final command is still click[buy now] (79.3% of failed parent rollouts in our audit terminate with click[buy now]). Donor fragments ending in click[buy now] populate Q(comp)\mathcal{Q}(\text{comp}) so the spliced candidate ends with a purchase attempt, which is then verified from scratch by environment replay (§3.4).
  • ALFWorld & ScienceWorld (Goal-Delivery Suffixes): Where no single checkout keyword exists, Q(comp)\mathcal{Q}(\text{comp}) prioritizes donor suffixes whose final action applies a goal-delivery or manipulation verb to the target object/receptacle/substance named in the task instruction (e.g., put <target_obj> in/on <target_receptacle> in ALFWorld, or actions triggering a positive sub-goal progress increment Δscore>0\Delta\text{score}>0 in ScienceWorld), while remaining fragments enter the general queue Q(gen)\mathcal{Q}(\text{gen}) ranked by goal-word overlap.

Question 1 (Motivation for Joint RL and SFT Optimization & Offline vs. Online Comparison)

  1. Why Auxiliary Continuation SFT Rather Than Direct RL Loss or Reward Shaping: Donor log-probabilities were computed under the donor's original history hdonor(t)h^{\text{donor}}(t) rather than the replayed history h~(t)\tilde{h}(t), so they do not represent valid behavior probabilities for on-policy PPO importance ratios, whereas the continuation loss L(cont)\mathcal{L}(\text{cont}) cleanly supervises verified continuations conditioned on h~(t)\tilde{h}(t). Moreover, on ScienceWorld and Visual Sokoban—which already use native shaped rewards—Re:Zero still adds +7.29 pp and +2.34 pp over GiGPO by supplying verified goal-reaching demonstrations.
  2. Comparison with Offline Re:Zero →\to SFT →\to Standard RL (Qwen3-1.7B, 3 Seeds): Following your proposed experimental design, we compared (i) Offline Re:Zero →\to SFT →\to Standard GiGPO (constructing verified trajectories offline from initial policy rollouts, performing SFT, and subsequently running 150 updates of standard GiGPO), (ii) Fixed Offline Verified Corpus + Interleaved GiGPO, and (iii) Online Re:Zero + GiGPO:
Training Paradigm (Qwen3-1.7B, 3 Seeds)ALFWorld Seen /128 (%)WebShop Succ /128 (%)SciWorld Succ /128 (%)
Base GiGPO (Standard RL Reference)87.50±1.3587.50 \pm 1.35 (110,113,113)62.76±1.1962.76 \pm 1.19 (79,82,80)19.27±1.1919.27 \pm 1.19 (23,26,25)
(i) Offline Re:Zero →\to SFT →\to Standard GiGPO90.36±1.1990.36 \pm 1.19 (114,117,116)65.89±1.1965.89 \pm 1.19 (83,86,84)22.66±1.3522.66 \pm 1.35 (28,31,28)
(ii) Fixed Verified Corpus + Interleaved GiGPO91.15±1.1991.15 \pm 1.19 (115,118,117)67.19±1.3567.19 \pm 1.35 (85,88,85)23.70±1.1923.70 \pm 1.19 (29,32,30)
(iii) Online Re:Zero + GiGPO (Joint Online, Ours)93.75±1.3593.75 \pm 1.35 (118,121,121)69.53±1.5669.53 \pm 1.56 (87,91,89)26.56±1.5626.56 \pm 1.56 (32,36,34)

All three augmented conditions use matched collection/verification budgets, auxiliary sample caps (N=16N=16), and 150 RL updates. Online integration continuously refreshes verified continuations as the policy evolves during RL, outperforming Offline SFT →\to RL by +3.39 to +3.91 pp and Fixed-Corpus Interleaving (which retains joint optimization but removes online refresh) by +2.34 to +2.86 pp.

AuthorsOpenReview ↗

Response to Reviewer Kpgb (Part C)

Critical Weakness 2 & Question 4 (Stochastic Regimes, Multi-Seed Statistics & Matched Wall-Clock Efficiency)

1. Extension to Stochastic (3-Pass Consensus) & Non-Replayable (Critic-Filtered) Regimes

We evaluated Re:Zero under 15% transition stochasticity (action-slip noise in ALFWorld; stochastic search/action noise in WebShop). Relaxing single-pass audit to 3-Pass Consensus Verification (re-executing candidates across 3 independent seeds and accepting those succeeding in ≥2/3\ge 2/3 executions) or using a Zero-Replay Surrogate (a replay-free baseline that filters candidate splices via an offline LLM rubric critic and trains on Donor context with 0 environment replay steps) both preserve clear gains over the 128 evaluation tasks:

Environment & Regime (Qwen3-1.7B, 3 Seeds, /128)Base GiGPO (%)+ Zero-Replay Surrogate (%)+ Consensus Re:Zero (3-Pass, %)
Stochastic ALFWorld (15% Transition Noise)79.43±1.1979.43 \pm 1.19 (100,103,102)83.33±1.1983.33 \pm 1.19 (105,108,107; +3.91 pp)85.68±1.1985.68 \pm 1.19 (108,111,110; +6.25 pp)
Stochastic WebShop (15% Search/Action Noise)56.25±1.3556.25 \pm 1.35 (70,73,73)59.90±1.1959.90 \pm 1.19 (75,78,77; +3.65 pp)61.98±1.1961.98 \pm 1.19 (78,81,79; +5.73 pp)

2. Multi-Seed Statistics & Matched Wall-Clock Time Comparison (§4.2 & Appendix G, in purple)

Tables 9–10 in Appendix G report 3 independent training seeds across the fixed evaluation suites (the 128 Seen and 134 Unseen ALFWorld splits, and the 128 fixed held-out tasks on WebShop, ScienceWorld, and Visual Sokoban). Additionally, on WebShop we compare under an equal 21.6-hour wall-clock budget on identical hardware (where Base GiGPO completes 174 RL updates vs. 150 for Re:Zero):

Benchmark / Comparison (3 Independent Seeds)Base GRPO (%)GRPO + Re:Zero (%)Base GiGPO (%)GiGPO + Re:Zero (%)
ALFWorld Fixed Seen (/128, 1.7B)75.00±2.3475.00 \pm 2.34 (93,99,96)82.81±1.5682.81 \pm 1.56 (104,108,106)87.50±1.3587.50 \pm 1.35 (110,113,113)93.75±1.3593.75 \pm 1.35 (118,121,121)
ALFWorld Full Unseen (/134, 1.7B)68.41±3.0268.41 \pm 3.02 (91,96,88)77.61±1.4977.61 \pm 1.49 (102,106,104)83.33±1.8883.33 \pm 1.88 (109,114,112)90.80±1.5590.80 \pm 1.55 (120,124,121)
WebShop Fixed (/128, 1.7B, 150 updates)57.03±1.5657.03 \pm 1.56 (71,75,73)66.41±1.3566.41 \pm 1.35 (84,87,84)62.76±1.1962.76 \pm 1.19 (79,82,80)69.53±1.5669.53 \pm 1.56 (87,91,89)
WebShop Matched Wall-Clock (21.6h, 1.7B)----64.06±1.3564.06 \pm 1.35 (81,84,81; 174 updates)69.53±1.5669.53 \pm 1.56 (87,91,89; +5.47 pp)
ScienceWorld Fixed (/128, 1.7B)16.41±1.5616.41 \pm 1.56 (19,23,21)21.09±1.3521.09 \pm 1.35 (26,29,26)19.27±1.1919.27 \pm 1.19 (23,26,25)26.56±1.5626.56 \pm 1.56 (32,36,34)
Visual Sokoban Fixed (/128, 4B)----42.19±0.7842.19 \pm 0.78 (53,55,54)44.53±1.3544.53 \pm 1.35 (56,59,56)
Reviewer_4yHdOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a method to recombine sampled trajectories to form high-reward trajectories, providing useful supervisory signals for model training. This approach is plug-and-play and requires no modification to the model's training objective.

Critical strengths
  1. The method is plug-and-play, requiring no changes to the model's training objective.
  2. The method is simple.
  3. The authors conducted extensive experiments.
Critical weaknesses
  1. Personally, I think this work merely involves simple recombination of trajectories. It might be effective for certain simple tasks with limited trajectory lengths, but may not be effective for tasks involving very long trajectories. For short trajectories, the space for resegmenting and combining is relatively small; however, for long trajectories, the solution space becomes extremely large, making it difficult to find effective trajectories through simple resegmentation and recombination.
  2. The method only performs basic resegmentation and recombination of trajectories. Given that it may not be useful for long-trajectory tasks, I believe the contribution of this work is quite limited.
  3. There are some terms that should be clarified further. For example, the author should clearly define what exe_x in Equation 2 specifically represents, and explain exactly what "parents" refers to in line 150. These undefined terms significantly hinder readers' understanding of the overall work.
Questions for authors
  1. Is this work capable of handling long-term trajectory tasks?
  2. Besides resegmenting and recombining trajectories, does this work have any other novel aspects?
4 comments
AuthorsOpenReview ↗

Response to Reviewer 4yHd (Part A)

We thank Reviewer 4yHd for recognizing that Re:Zero is plug-and-play, simple, and supported by extensive experiments. Below, we address Weakness 1, followed by Weaknesses 2–3 in Part B. In the revised PDF, long-horizon analyses are highlighted in blue, method/novelty clarifications in purple, and notation definitions in teal.

Weakness 1 & Question 1: "Personally, I think this work merely involves simple recombination of trajectories. It might be effective for certain simple tasks with limited trajectory lengths, but may not be effective for tasks involving very long trajectories... Is this work capable of handling long-term trajectory tasks?"

Response to Weakness 1 & Question 1: Yes. Handling long-trajectory tasks involves two distinct questions: (1) whether the O(G2H3)O(G^2 H^3) cut space causes prohibitive indexing or search cost as horizon HH grows, and (2) whether Re:Zero recovers valid supervision and improves downstream success on longer multi-stage tasks. We evaluate both below (Section 4.3 and Appendix E, in blue):

1. Computational Scaling up to H=150H=150: Lazy Descriptor Indexing & Bounded Replay

While G=8G=8 parent rollouts of length HH span 13G(G−1)H(H−1)(H+1)=O(G2H3)\frac{1}{3}G(G-1)H(H-1)(H+1) = O(G^2 H^3) raw cut-index tuples (s,d,i,j,k)(s, d, i, j, k), Re:Zero does not materialize or execute all candidate sequences (Appendix E):

  • O(G2H2)O(G^2 H^2) Lazy Endpoint Descriptors (CPU Indexing up to H=150H=150): Candidate cuts are indexed via O(G2H2)O(G^2 H^2) endpoint descriptors and materialized lazily only when drawn for replay. Timing CPU index initialization on 8-rollout parent pools scaled from H=25H=25 to H=150H=150 steps (median over 5 runs after warmup) shows sub-second index construction even when raw cut combinations exceed 6.2×1076.2 \times 10^7:
Horizon (HH, G=8G=8)Raw Cut Combinations O(G2H3)O(G^2 H^3)Lazy Descriptors O(G2H2)O(G^2 H^2)Median CPU Index Init Time
H=25H = 25291,200291{,}20033,60033{,}60023.4 ms
H=50H = 502,332,4002{,}332{,}400137,200137{,}20089.9 ms
H=100H = 10018,664,80018{,}664{,}800554,400554{,}400353.7 ms
H=150H = 15062,997,20062{,}997{,}2001,251,6001{,}251{,}600767.3 ms
  • Bounded Simulator Execution & Zero Policy Decoding: Simulator steps (audit, prefix replay, candidate execution, and verification) are strictly capped per pool by BGHBGH and globally by αE(base)\alpha E(\text{base}) (α=3.0\alpha=3.0, Appendix D), requiring zero additional LLM decoding (1.00×1.00\times) at any horizon HH.

2. Empirical Efficacy Across Trajectory Lengths and Multi-Stage Tasks

  1. Multi-Stage Task Breakdown (Table 1): Under ALFWorld's 50-step horizon (Qwen3-1.7B), Re:Zero achieves its largest gains on long multi-stage task types requiring chained sub-goals—such as Heat (+13.4 pp on GRPO [71.4% →\to 84.8%]; +25.9 pp on GiGPO [68.8% →\to 94.7%]) and Pick2 (+14.1 pp on GRPO [60.9% →\to 75.0%]; +2.1 pp on GiGPO [91.7% →\to 93.8%])—whereas short single-stage tasks (Pick +0.8 pp, Look +0.6 pp on GRPO) are already near saturation.
  2. Length-Stratified Rescue and Root Success (Qwen3-1.7B, §4.3): Stratifying the ALFWorld (H=50H=50, 128 evaluation tasks, 210 frozen all-fail pools in Table 5) suite by reference trajectory length confirms consistent gains on the longest 31–50 step bin:
Reference Length BinUniform Draw RescueRe:Zero Ranked RescueBase GiGPO Root SRGiGPO + Re:Zero Root SRNet Gain (Δ\Delta)
Short (1–15 steps)55.8% (29/52)61.5% (32/52)92.9% (39/42)97.6% (41/42)+4.8 pp
Medium (16–30 steps)47.4% (45/95)53.7% (51/95)88.9% (48/54)94.4% (51/54)+5.6 pp
Long (31–50 steps)31.7% (20/63)42.9% (27/63)78.1% (25/32)87.5% (28/32)+9.4 pp
ALFWorld Total (Tables 1 & 5)44.8% (94/210)52.4% (110/210)87.5% (112/128)93.8% (120/128)+6.3 pp

While pool rescue rates naturally taper from 61.5% (1–15 steps) to 42.9% (31–50 steps) as the cut space expands, Re:Zero's completion-aware ranking widens its margin over Uniform Draw on the longest 31–50 step bin (+11.1 pp rescue gap vs. +5.8 pp on short tasks), accompanied by a +9.4 pp downstream root-success gain on 31–50 step tasks (78.1%→87.5%78.1\% \to 87.5\%).

AuthorsOpenReview ↗

Response to Reviewer 4yHd (Part B)

Weakness 2 & Question 2: "The method only performs basic resegmentation and recombination of trajectories. Given that it may not be useful for long-trajectory tasks, I believe the contribution of this work is quite limited. Besides resegmenting and recombining trajectories, does this work have any other novel aspects?"

Response to Weakness 2 & Question 2: Beyond the long-horizon gains shown in Part A, our ablations demonstrate that unverified trajectory resegmentation and recombination alone fails and reduces performance below the base RL policy: in Table 3 (w/o verification), directly training on unverified spliced trajectories drops root-start success rates to 85.9% vs. 87.5% (Base GiGPO) on ALFWorld and 61.7% vs. 62.8% on WebShop. Turning failed rollouts into effective supervision requires three core technical contributions beyond trajectory splicing (Sections 1 & 3, in purple):

  1. Decode-Free Environment Verification for All-Fail Groups (Figure 1c & §3.4): In group-based RL (GRPO, GiGPO), all-fail groups yield zero relative outcome advantage under binary rewards. Whereas generating new mid-episode continuations requires costly LLM autoregressive decoding (2.38×2.38\times decoding volume in Table 7's step-matched Fresh branches control), Re:Zero introduces a decode-free (1.00×1.00\times) verification paradigm: it treats all-fail groups as latent action repositories and validates candidate splices via native environment replay from the saved initial state (x,ξ)(x, \xi). Removing this verification gate degrades root success by -7.9 pp on ALFWorld and -7.8 pp on WebShop (Table 3).

  2. Replayed Observation-History Grounding Under Altered States (§3.5): In interactive environments, actions cannot be stitched offline like static text. Transplanting a donor action fragment onto a different source prefix places the agent in a new environment state, producing new subsequent observations that differ from what the donor trajectory originally observed. Training the policy on the donor's original observation history (Donor context in Table 4) supervises actions under mismatched contexts and degrades root-start transfer (92.8% vs. 93.8% on ALFWorld; 67.9% vs. 69.5% on WebShop). Re:Zero solves this by conditioning the policy on the exact replayed observation history h~(t)\tilde{h}(t) generated during verified execution.

  3. Prefix-Masked Continuation Objective to Focus Updates on Novel Continuations (§3.5, Eq. 4): Even on a verified recomposed trajectory, supervising the entire sequence (Full trajectory, ℓ=0\ell=0 in Table 4) applies auxiliary cross-entropy to the shared source prefix, dividing auxiliary gradient capacity away from the newly discovered donor continuation. By masking the shared prefix (mask=0\text{mask}=0) as conditioning context and computing loss solely on verified continuation tokens (t>ℓt > \ell), Re:Zero improves root-start success by +1.2 pp on ALFWorld (93.8% vs. 92.6%) and +2.0 pp on WebShop (69.5% vs. 67.5%).


Weakness 3: "There are some terms that should be clarified further. For example, the author should clearly define what 1{⋅}\mathbb{1}\{\cdot\} in Equation 2 specifically represents, and explain exactly what 'parents' refers to in line 150. These undefined terms significantly hinder readers' understanding of the overall work."

Response to Weakness 3: We have explicitly defined both terms at their first appearance in Section 3.1 and Section 3.2 (highlighted in teal):

  1. 1{⋅}\mathbb{1}\{\cdot\} in Eq. (2): Denotes the binary indicator function, which equals 11 when the condition inside the braces holds—namely, when all rollouts in group G(x)G(x) fail (S(τ)=0S(\tau) = 0 for all GG members)—and 00 otherwise.
  2. "Parents" (§3.2): Refers to the GG original failed rollouts {τ(1),…,τ(G)}\{\tau(1), \dots, \tau(G)\} (and their cleaned action sequences {b(1),…,b(G)}\{b(1), \dots, b(G)\}) within an eligible all-fail group, from which a source parent contributes the prefix and a distinct donor parent contributes the continuation fragment.
AuthorsOpenReview ↗

Gentle Follow-up on Our Response and Revised Manuscript

Dear Reviewer 4yHd,

We hope this message finds you well, and we sincerely appreciate the time and effort you have dedicated to reviewing our work.

As the discussion period progresses, we wanted to gently follow up to see if you have had a chance to review our detailed responses (Parts A and B) and the revised manuscript. To briefly recap, we have directly addressed each of your questions and concerns:

  1. Long-Horizon & Multi-Stage Task Capability (Part A, §4.3 & Appendix E): We provided exact CPU lazy-indexing measurements scaling up to H=150H=150 steps (sub-second initialization at 767.3 ms for 6.30×1076.30 \times 10^7 raw cut combinations at zero extra LLM decoding) alongside length-stratified ALFWorld results showing a +9.4 pp root-success gain (78.1%→87.5%78.1\% \to 87.5\%) on the longest 31–50 step tasks and up to +25.9 pp on multi-stage Heat tasks.
  2. Core Technical Contributions Beyond Basic Splicing (Part B, §1 & §3): We highlighted how unverified splicing alone degrades performance below the base RL policy (w/o verification in Table 3), and detailed our three core contributions: decode-free environment verification (+7.9 pp / +7.8 pp), replayed observation-history grounding (Continuation vs. Donor context in Table 4), and prefix-masked continuation learning (+1.2 pp / +2.0 pp over Full trajectory).
  3. Notation & Terminology Clarifications (Part B, §3.1 & §3.2): We explicitly defined the indicator function 1{⋅}\mathbb{1}\{\cdot\} in Eq. (2) and the term "parents" at their first appearances in the revised PDF.

Please let us know if our responses and revisions have addressed your concerns, or if there are any further questions or analyses we can provide during the discussion period. Thank you again for your valuable feedback!

Best regards, The Authors

Dear Reviewer 4yHd, as the discussion period is coming to an end, we wanted to briefly check if our responses and long-horizon analyses have addressed your concerns. If they have resolved your questions, we would be deeply grateful if you could consider updating your score, or let us know if any final clarification is needed.

Comments on the paper

4 comments
AuthorsOpenReview ↗

Response to Reviewer 6irx (Part A)

Thank you for the constructive review. Part A addresses verification, reward definitions, multi-seed statistics, and unseen generalization; Part B addresses cost regime, branching controls, prefix masking, and coverage limits.

Weakness 1 (Strict Completion vs. Thresholded Acceptance 0.8, §3.4, §4.3 & App. C)

In Section 3.4, Section 4.3, and Appendix C (in purple), we strictly reserve "verified strict successes" for native task completions (score=1.0\text{score}=1.0) and refer to episodes scoring in [0.8,1.0)[0.8, 1.0) as "environment-validated high-score continuations." Auditing all 345 accepted episodes from the 319 rescued WebShop pools (out of 883 eligible all-fail pools: 40 episodes from single-parent cleanup and 305 from cross-parent recomposition; full breakdown in Response to Reviewer Kpgb Part A and Section 4.3) shows that 62.6% (216/345) overall—and 70.8% (216/305) of recompositions—achieve strict completion (score=1.0\text{score}=1.0), alongside 54.3% (189/348) on ScienceWorld. Retraining Qwen3-1.7B across 3 seeds under a Strict-Completion-Only gate (1.0) improves strict completion over Base GiGPO by +4.95 pp on WebShop (62.76±1.19%→67.71±1.19%62.76\pm1.19\%\to 67.71\pm1.19\%) and +5.47 pp on ScienceWorld (19.27±1.19%→24.74±1.19%19.27\pm1.19\%\to 24.74\pm1.19\%), retaining >73% of the full gain, while admitting [0.8,1.0)[0.8, 1.0) continuations (0.8 gate) adds +1.82 pp (69.53±1.56%69.53\pm1.56\% and 26.56±1.56%26.56\pm1.56\%) by supervising verified high-progress sub-behaviors on harder tasks.

Weakness 2 (Distinguishing RL Returns, Eligibility & Verification Predicates, §3.1 & App. A)

In Section 3.1 and Appendix A (in purple), we explicitly separate (1) the base RL return R(τ)R(\tau), (2) group eligibility (Eq. 2), and (3) the auxiliary verification predicate:

Benchmark(1) Base RL Return R(τ)R(\tau)(2) Group Eligibility(3) Verification PredicateAll-Fail Group Advantage
ALFWorldBinary terminal (R=S∈{0,1}R = S \in \{0,1\})All rollouts fail (S=0S=0)Binary completion (S=1S=1)Identically 00 (σ=0\sigma=0)
WebShopBinary (1010 if score=1.0\text{score}=1.0, else 00)All rollouts fail (S=0S=0)Graded score≥0.8\text{score} \ge 0.8Identically 00 (σ=0\sigma=0)
ScienceWorldNative shaped progress + completionAll rollouts fail (S=0S=0)Graded score≥0.8\text{score} \ge 0.8Non-zero if returns differ (00 if tied); 00 solved demos
Visual SokobanNative shaped (−0.1-0.1/step, ±1\pm 1 box, +10+10 solve)All rollouts fail (S=0S=0)Binary won flag (S=1S=1)00 when failed rollouts tie (e.g., R=−1.5R=-1.5); 00 solved demos

Visual Sokoban retains native Gym-Sokoban shaped per-step rewards for RL (RR), whereas group eligibility and candidate verification use its binary won predicate (S∈{0,1}S\in\{0,1\}), so the 0.80.8 gate accepts if and only if the level is solved (S=1S=1). Under shaped rewards (ScienceWorld, Sokoban), all-fail groups retain non-zero outcome advantages when partial returns differ, but still yield zero outcome advantage whenever failed rollouts tie in total return (e.g., exhausting 15 steps in single-box Sokoban at −0.1-0.1/step, giving R=−1.5R=-1.5 for all 8 rollouts), and in all cases contain no solved demonstration.

Weaknesses 3 & 4 (Multi-Seed Statistics, Fixed ALFWorld Protocol & Unseen Generalization, §4.1, §4.2 & App. G)

To ensure all methods and seeds are evaluated on identical task instances alongside out-of-distribution generalization, Section 4.2 and Appendix G (Tables 9–10, in purple) evaluate 3 independent training seeds on a single fixed 128-game ALFWorld Seen subset, all 134 Unseen OOD games (novel room layouts), and fixed 128-task held-out suites across WebShop, ScienceWorld, and Visual Sokoban:

Method (Qwen3-1.7B)Seen Solved /128ALFWorld Seen (%)Unseen Solved /134ALFWorld Unseen (%)
HGPO / Gated-BEPO114,117,117 / 116,120,11890.63±1.3590.63\pm1.35 / 92.19±1.5692.19\pm1.56114,120,116 / 115,118,12187.06±2.2887.06\pm2.28 / 88.06±2.2488.06\pm2.24
GRPO / + Re:Zero93,99,96 / 104,108,10675.00±2.34→75.00\pm2.34 \to 82.81±1.5682.81\pm1.56 (+7.81 pp)91,96,88 / 102,106,10468.41±3.02→68.41\pm3.02 \to 77.61±1.4977.61\pm1.49 (+9.20 pp)
GiGPO / + Re:Zero110,113,113 / 118,121,12187.50±1.35→87.50\pm1.35 \to 93.75±1.3593.75\pm1.35 (+6.25 pp)109,114,112 / 120,124,12183.33±1.88→83.33\pm1.88 \to 90.80±1.5590.80\pm1.55 (+7.46 pp)

Consistent 3-seed gains also hold on WebShop (62.76±1.19%→69.53±1.56%62.76\pm1.19\%\to 69.53\pm1.56\% [87,91,89 vs. 79,82,80]), ScienceWorld (19.27±1.19%→26.56±1.56%19.27\pm1.19\%\to 26.56\pm1.56\% [32,36,34 vs. 23,26,25]), and Visual Sokoban (4B) (42.19±0.78%→44.53±1.35%42.19\pm0.78\%\to 44.53\pm1.35\% [solving 56,59,56 vs. 53,55,54 of the same 128 levels; seed-wise gains of +3,+4,+2+3,+4,+2 solved levels]).

AuthorsOpenReview ↗

Response to Reviewer 6irx (Part B)

Weakness 5: "Efficiency benefits depend on the cost regime. Environment steps increase by 203%, although wall-clock time rises by only 16.2% in the reported setup. The method is attractive when simulator interactions are cheap relative to decoding, but this should not be generalized to environments with expensive resets or interactions."

Weakness 6: "The matched-budget branching control has limited scope. 'Fresh branches' simulates a branching strategy; it does not necessarily reproduce a fully tuned BPO or SPARK implementation. The manuscript should distinguish this control from direct comparisons with those algorithms."

Response to Weaknesses 5 & 6:

  1. Scoping the Cost Regime (§4.3, Table 6 & §5): We agree and have explicitly scoped this claim in Section 4.3 and Section 5 (in purple): the favorable wall-clock trade-off (+203%+203\% simulator steps translating to only +16.2%+16.2\% wall-clock time) applies to regimes where environment resets and transitions are lightweight relative to autoregressive LLM decoding. Moreover, under an equal 21.6-hour wall-clock budget on WebShop (where Base GiGPO completes 174 RL updates vs. 150 for Re:Zero on identical hardware), GiGPO + Re:Zero still outperforms Base GiGPO by +5.47 pp (69.53±1.56%69.53 \pm 1.56\% vs. 64.06±1.35%64.06 \pm 1.35\%).
  2. Distinguishing Fresh branches from SPARK (§4.3): We revised Section 4.3 to state explicitly that Fresh branches in Table 7 is a step-matched diagnostic control isolating mid-episode branching under an equal 2,736-step interaction budget rather than a full reproduction of BPO or SPARK, while referencing Table 1 for our direct comparison against the SPARK baseline (where GiGPO + Re:Zero exceeds SPARK by +4.0 pp on ALFWorld and +6.7 pp on WebShop).

Weakness 7: "Some mechanistic explanations are too strong. A prefix from a failed trajectory is not necessarily a bad prefix. The empirical benefit of masking does not establish that prefix supervision reinforces erroneous decisions or causes entropy collapse."

Response to Weakness 7: We agree—indeed, a rescued trajectory succeeds by building upon that valid source prefix. We have removed all claims that prefix supervision "reinforces erroneous decisions" or causes "entropy collapse" from the Abstract, Section 4.3, and Appendix E (in purple), framing prefix masking strictly around its measured ablation effect (+1.2 pp on ALFWorld / +2.0 pp on WebShop over Full trajectory in Table 4): retaining the shared prefix as conditioning context (mask=0\text{mask}=0) while concentrating auxiliary gradient updates on the newly discovered donor continuation tokens (t>ℓt > \ell).

Weakness 8: "Applicability is restricted by replayability and action coverage. The method depends on reproducible environments and cannot discover successful behaviors absent from the available action fragments. These limitations deserve quantitative characterization."

Response to Weakness 8: We audited the frozen all-fail pools from our ablation runs across ALFWorld (210 pools, Qwen3-1.7B), WebShop (883 pools, Qwen3-1.7B), and Visual Sokoban (520 pools, Qwen3.5-4B), running extended single-splice search on unrescued pools to quantify each limitation within the single-splice candidate family (discussed in Appendix C & E):

Pool Outcome / Limitation Category (% of Eligible Pools)ALFWorld (/210)WebShop (/883)Visual Sokoban (/520)Quantitative Interpretation
1. Rescued within Budget BB (α=3.0\alpha=3.0)52.4% (110)36.1% (319)14.2% (74)Captured within the bounded training replay budget.
2. Additional Rescues under Extended Search6.2% (13)4.8% (42)2.3% (12)Valid single-splice exists in O(G2H3)O(G^2 H^3) but missed under budget BB (bounded search captures 89.4%, 88.4%, and 86.0% of recoverable pools).
3. Replay Audit Mismatch0.5% (1)0.6% (5)0.0% (0)Failed trace-reproducibility audit (≥99.4%\ge 99.4\% pass rate; retained in all denominators).
4. Missing Target Interaction / Reachability31.4% (66)49.3% (435)28.5% (148)Action-Coverage Bound: No parent in G=8G=8 ever interacted with the required target object/item (ALF/WS) or reached the box-to-goal pushing corridor (Sokoban).
5. State-Coupling / Single-Splice Incompatibility9.5% (20)9.3% (82)55.0% (286)Target sub-behaviors appear in parents, but no single-splice succeeds under altered states (dominant bottleneck in tightly coupled grid puzzles).
AuthorsOpenReview ↗

Gentle Follow-up on Our Revisions and Additional Analyses

Dear Reviewer 6irx,

We hope this message finds you well, and we sincerely thank you for your supportive assessment and insightful suggestions.

We wanted to gently follow up to see if you have had a chance to look over our responses (Parts A and B) and the corresponding updates in the revised manuscript. To briefly summarize how we addressed each of your points:

  1. Terminology, Strict-Gate Ablation & Reward/Predicate Reconciliation (Part A, §3.1, §3.4, §4.3 & App. A/C): We unified our terminology to distinguish verified strict successes (score=1.0\text{score}=1.0) from environment-validated high-score continuations ([0.8,1.0)[0.8, 1.0)), added 3-seed Strict-Completion-Only (1.01.0) training results, and explicitly separated base RL returns R(τ)R(\tau), group eligibility, and verification predicates across all four benchmarks (clarifying Visual Sokoban's shaped RL return vs. binary won verification).
  2. Multi-Seed Statistics, Fixed Seen Protocol & Unseen OOD Generalization (Part A, §4.1, §4.2 & App. G): We clarified the fixed 128-game Seen evaluation protocol and added 3-seed evaluations (Tables 9–10) across the fixed Seen split, the full 134-game ALFWorld Unseen OOD split (+9.20 pp on GRPO, +7.46 pp on GiGPO), WebShop, ScienceWorld, and Visual Sokoban.
  3. Cost Regime Scope, Branching Control, Prefix Masking & Pool Limitation Audit (Part B, §4.3, §5 & App. C/E): We explicitly scoped the wall-clock efficiency claim (and added a matched 21.6-hour wall-clock comparison), distinguished the diagnostic Fresh branches control from the SPARK baseline in Table 1, refined the prefix-masking discussion to focus strictly on measured ablation gains, and provided a quantitative 5-category audit of all unrescued failure pools across ALFWorld, WebShop, and Visual Sokoban.

Please let us know if our revisions and new analyses satisfactorily resolve your points, or if we can clarify anything further. Thank you once again for your constructive feedback!

Best regards, The Authors

Dear Reviewer 6irx, as the discussion phase wraps up soon, we wanted to briefly check if our multi-seed Unseen OOD results, reward reconciliations, and pool audits have satisfactorily addressed your points. Please let us know if you have any remaining questions, and thank you again for your valuable support and feedback!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.