acceptodds
Under review as a conference paper at ICLR 2027

HiRUB: Hierarchical Rubric Rewards for Long-Horizon Large Language Model Agents

Abstract

Long-horizon agent reinforcement learning (RL) relies on informative trajectory-level rewards that indicate how a complete interaction advances the requested outcome. Success in these tasks can depend on a chain of interdependent decisions, with different actions contributing unequally to the eventual result. Consequently, terminal feedback alone is often too coarse to distinguish useful progress from ineffective behavior. LLM judges can provide richer trajectory assessments, yet placing them inside the RL loop requires repeated inference for every rollout and becomes costly as trajectories and rollout groups grow. To make rubric-style feedback practical without retaining this online expense, we present , a hierarchical rubric reward that uses an LLM to generate task-aware criteria before training and applies them through executable checks during RL. These criteria are related to a task schema, allowing each complete rollout to receive a task-aware score that combines partial progress, semantic constraints, successful completion, and penalties. This design keeps the reward computation lightweight and compatible with different RL backbones while avoiding online LLM judging. Experiments across ALFWorld and WebShop with 1.5B and 7B parameters show consistent gains over the evaluated RL baselines. In a matched ALFWorld comparison against an online LLM-judge reward, HiRUB improves validation success from 90.1% to 92.2% and reduces total training time from 31.1 to 19.6 hours. Together, these results show that task-aware trajectory scoring can improve agent learning without placing judge inference in the training loop.

Primary area:
reinforcement learning
Keywords:
Reinforcement learning, Reward shaping, Rubric-based rewards

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 3 reviews, above 27% of the others.
Reviewer_F5ErOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper addresses the cost and quality of trajectory-level rewards for long-horizon LLM agent RL. Its starting observation is that terminal success signals are too coarse to distinguish useful progress from wasted steps, while LLM-judge rewards provide richer assessments but require an inference call for every sampled rollout, which becomes a bottleneck for group-relative methods that compare many rollouts per update. HiRUB's proposal is to remove the judge from the training loop: an LLM (GPT-5.2) generates a hierarchical rubric once, before training, for a task family; the rubric is grounded in a task schema derived from the instruction and environment interface and compiled into deterministic, schema-conditioned checks over observations, actions and environment feedback. A lightweight scorer then evaluates every complete rollout with those checks and produces a scalar reward combining a progress component (first-hit milestone evidence such as target discovery, directed navigation, required interaction and verification), a semantic component (workflow-family and instance-level target or attribute constraints, with per-type counts capped so repeats cannot inflate credit), a terminal success component, and bounded repetition and length penalties, passed through a clip at zero so penalties cannot make a trajectory negative.

The reward is trajectory-level and is intended to be optimizer-agnostic; the paper plugs it into GRPO and GiGPO by replacing only the reward signal inside group-normalized advantage estimation. Evaluation is on ALFWorld (six task families, success rate by family and overall) and WebShop (dense score and success rate) with Qwen2.5-Instruct at 1.5B and 7B, comparing prompting baselines, PPO, RLOO, GRPO and GiGPO against their HiRUB variants. The headline numbers are ALFWorld overall success rising from 86.5 to 92.2 for GiGPO at 1.5B and from 90.8 to 94.0 at 7B, plus WebShop gains, and a matched comparison against an online LLM-judge reward in which validation success rises from 90.1 to 92.2 while total training time falls from 31.1 to 19.6 hours and per-step reward computation falls from 238.1 to 1.0 seconds. Supporting evidence includes a rubric-conditioned judge benchmark (Table C.1), an ablation over hierarchy levels and reward design, a reward-coefficient sensitivity study, a repeated-judge stability study, and failure and trajectory diagnostics.

Critical strengths
  1. Removing the online judge by compiling rubric criteria into deterministic, schema-grounded checks is a real and well-targeted contribution. Placing an LLM judge inside the RL loop is the dominant cost in rubric-based agent RL, and it is paid once per rollout, which is exactly the worst case for group-relative methods that sample many rollouts per update. HiRUB attacks the problem at its source rather than by optimizing the judge call, and it does so in a way that keeps the reward interpretable and inspectable: every returned reward can be traced to named checks with listed coefficients, and the reward is a scalar, so it drops into different optimizers without changes (Section 4.6 and Algorithm G.1). The supporting evidence is concrete rather than rhetorical, namely the per-step decomposition showing reward computation dropping from 238.1 to 1.0 seconds and total wall-clock from 31.1 to 19.6 hours, together with roughly 0.7 top-5 pairwise agreement against a rubric-conditioned judge. This is the part of the paper that makes it worth accepting.

  2. The empirical study is unusually thorough for its claim, and it tests the right alternatives. Beyond the main table, the paper runs a matched head-to-head against a rubric-conditioned online LLM judge (Figure 4), a reward-judge benchmark that motivates the two-stage rubric generation setup (Table C.1), ablations that separately remove the progress hierarchy, the semantic hierarchy, and the full design in favor of a minimal-rubric, step-slot, or no-repeat variant (Figure 5), a coefficient study that perturbs and rescales the shaping weights including a random-perturbation sweep (Table 2 and Table I.2), and a repeated-judge stability study that is careful to state what it does not establish (Appendix F). The coefficient study is the most convincing part, because the default setting is not a brittle optimum: uniform, inverted-hierarchy and randomly perturbed weights remain competitive, which is evidence that the gains come from the structure of the reward rather than from one lucky numeric choice. Reporting three-seed means with standard deviations at 1.5B also raises my confidence relative to the norm in this literature.

Critical weaknesses
  1. The reward is non-potential-based shaping whose optimal policy is not characterized, and the reported superiority over a binary outcome baseline cannot be disentangled from reward specification. The trajectory score is a positive, non-telescoping sum of first-hit milestone indicators and constraint bonuses, clipped at zero against penalties, with coefficients that the paper states are the rubric-generating LLM's original suggestions and were not manually adjusted (Section 4.5, Appendix H, and the note in Appendix E). Shaping of this form need not preserve the optimal policy of the underlying task, and the paper never states whether it does, never verifies it empirically, and never bounds the shaping magnitude relative to the terminal success bonus of 4.0. This matters directly for how the main results should be read. The comparison HiRUB is sold on is against GiGPO with a binary sparse outcome, so a large part of any measured success gain may come from the reward having been specified rather than from better credit assignment per se. The paper's own weaker variants in Table 2 are consistent with this reading: equalized or reordered weights still reach 82.8 and 85.7 overall ALFWorld success, well above the 86.5 the binary GiGPO baseline obtains at 1.5B, which suggests that a substantial share of the gain is attributable to the mere presence of dense shaping rather than to the hierarchy the paper highlights. Since the paper's central claim is that task-aware rubric structure improves agent learning, not merely that dense shaping helps, this ambiguity is consequential.

  2. The headline gains are not statistically robust, and family-level results contradict the claimed consistency. The abstract and introduction state that HiRUB achieves consistent gains over the evaluated RL baselines, and the strongest evidence offered for the 7B scale is a comparison of 90.8 against 94.0 that carries no uncertainty at all: Table 1 reports three-seed standard deviations only for the rows that have them, and in the 7B block the RLOO, GRPO and GiGPO comparisons, including the HiRUB variant, are reported as bare numbers. This is the wrong place to economize, because the 1.5B rows that do carry error bars show that the measurement noise in this setting is very large: RLOO at 1.5B reports 52.8 plus or minus 8.6 on Look, GRPO reports 33.3 plus or minus 19.1 on the same family, and HiRUB's own WebShop success gain of 4.3 points carries plus or minus 2.8. Against that background a 3.2 point gap with no interval is not interpretable. The per-family numbers also do not support consistency: at 7B, HiRUB moves Look from 82.7 to 75.0, a 7.7 point regression, and at 1.5B it moves Clean from 94.9 to 87.5 while carrying plus or minus 7.8, which means the claim of a 5.7 point overall improvement at 1.5B is partly an average over family-level movement in the opposite direction. Because acceptance here hinges on whether the reward reliably improves learning rather than reshuffling performance across families, this combination of unpreserved uncertainty and family-level regressions is the main obstacle to a stronger recommendation.

Questions for authors

Optimality of the shaped objective. Is the HiRUB trajectory reward potential-based or otherwise optimality-preserving with respect to the environment success signal, or is it intended as a heuristic shaping term? If it is not optimality-preserving, please give the empirical test: how does final success change as the terminal success bonus is swept relative to the sum of the shaping coefficients (for example bonus multiplied by 0.5, 1, 2, 4 with shaping fixed)? This bears directly on whether the reported gains reflect better optimization of the same objective or a different objective.

Is the LLM-generated rubric necessary? The checks are grounded in the task schema, and for ALFWorld the paper notes that the scorer actually inverts the environment's fixed goal-template library and fixed action space (Section 4.2). Could a hand-written dense reward with the same milestone and constraint features, but no LLM-generated rubric, match HiRUB? An instruction-to-checks ablation that bypasses the LLM rubric would isolate whether the rubric contributes anything beyond the shape of the reward. This is the same question as the equalized-weights result in Table 2, which already performs above the binary baseline.

Seeds and uncertainty for the 7B comparisons. How many seeds underlie each 7B entry in Table 1, and can you add standard deviations? Given that the 1.5B entries reach plus or minus 8.6, plus or minus 13.9, and plus or minus 19.1 on individual families, what is the confidence interval on the 90.8 to 94.0 and 72.8 to 73.7 comparisons?

The family-level regressions. The 7B Look family drops from 82.7 to 75.0 and the 1.5B Clean family drops from 94.9 to 87.5. Do these reflect systematic interference from the shaping terms, for example the family-condition, light-task inspect, or two-object coefficients interacting with the length and repetition penalties, or are they within seed noise? Please support the claim of consistent gains with a per-family test rather than an aggregate.

What is the right reading of the cost claim? The 31.1 versus 19.6 hour comparison issues judge requests at API concurrency two, and the per-step reward computation is 238.1 seconds for the judge against 1.0 second for HiRUB. Judge calls are asynchronous, so in a typical implementation they would overlap with GPU work rather than block it. What were GPU idle time and GPU utilization in the online-judge run, and what happens to the comparison at a realistic concurrency or with a locally served judge model? Please also report end-to-end API cost, and separate wall-clock savings from monetary savings.

Trajectory-level versus per-step accumulation. Section 4.6 and the related-work discussion describe credit as assigned once at the trajectory level tied to the task schema, but the progress and semantic terms are first-hit indicators over the whole rollout, so at step t the running reward already contains evidence satisfied at earlier steps. How is the reward consumed by the group-relative update in the actual implementation, as a terminal return or as a per-turn signal, and does the milestone evidence accumulate into a reward that grows with episode length in a way that interacts with the length penalty?

Alternative explanations for the gradient signal. The gain could reflect reduced variance from group normalization when rewards take many distinct values, rather than the task semantics of the checks. Did you compare against a dense but semantically uninformative reward with a comparable spread, for example a random or frequency-based milestone counter? This would separate the value of the rubric content from the value of reward diversity.

Generalization beyond templated environments. Appendix J notes the dependence on a task schema and on stable instruction, action and observation structure. For an environment in the spirit of ALFWorld but with an open-ended instruction set, what is the expected failure mode of the deterministic parser, and which component would need to change first?

Exploitation of the deterministic scorer. The reward is computed by a parser over text, and parsing and matching decisions are deterministic rather than sampled. Did you observe reward-hacking behavior, for example action sequences that satisfy target-aware checks without advancing the task, or degenerate placements that hit the two-object terms incrementally? Since the paper calls this a reward rather than a critic, a short negative-result statement would be useful.

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

The paper tackles sparse terminal rewards in long-horizon LLM-agent RL. Before training, an LLM generates hierarchical, task-aware rubrics. These are mapped to a task schema (workflow family, targets, constraints, milestones) and turned into deterministic checks over complete rollouts, so no LLM judge is needed during RL. Each trajectory’s score combines a progress hierarchy (discovery → navigation → interaction → verification), a semantic hierarchy (generic → workflow-family → target-instance constraints), a terminal-success bonus, and penalties for repetition and length. The score plugs into group-relative optimizers such as GRPO and GiGPO. Experiments on ALFWorld and WebShop use Qwen2.5-1.5B/7B-Instruct. Results include gains over RL baselines (e.g., GiGPO on ALFWorld from 86.5% to 92.2% at 1.5B), a matched comparison against an online rubric-conditioned LLM judge (92.2% vs 90.1% validation success, 19.6 vs 31.1 hours of training), and ablations on the hierarchies and reward coefficients.

Critical strengths

S1. Clear motivation and well-identified research gaps. The paper states the gap in existing approaches to sparse-reward RL for LLM post-training on long-horizon tasks clearly. Online LLM judges give rich feedback but are expensive to call for every rollout, especially with group-relative methods. Credit-assignment and reward-densification methods improve how a reward is used, but they still depend on the reward being well defined. Fig. 1 gives a clear overview of how the method works and what it looks like in practice, from rollouts through rubric generation to the two hierarchies and the final trajectory score.

S2. Informative training and rollout diagnostics (Sec. 5.2, Fig. 3). The diagnostics in Fig. 3 are informative, and I learned something new from this kind of analysis.

Critical weaknesses

W1. Unstated assumption that the rubric-generating LLM already knows the task, which makes the approach domain-dependent. This is my biggest concern. The method assumes, without saying so, that the LLM queried for task-aware criteria before RL already has substantial knowledge of the task (or is given the knowledge by the human expert via the rubric prompt). Only then can it produce suitable criteria. ALFWorld and WebShop are well-known benchmarks, so GPT-5.2 has very likely seen them, which may be why the approach works here. It is not clear at all whether, or how well, it transfers to tasks where the generated criteria may be wrong or noisy.

Some details in the paper support this concern:

A. The prompt already supplies task knowledge. The rubric prompt (Prompt Box A) takes the success condition and “known distractors or failure modes” as inputs, so human-supplied knowledge enters before the LLM does any work.

B. The checks depend on ALFWorld’s fixed templates. Sec. 4.2 says the compiled scorer “inverts” ALFWorld’s fixed goal-template grammar. That only seems to be possible because the environment’s instructions come from templates.

Questions for authors
  1. (W1) How does HiRUB perform when the rubric comes from a weaker or open-source generator (e.g., a Qwen2.5-7B-class model), or when criteria are deliberately corrupted (dropped milestones, wrong targets, overly broad criteria)? Does downstream success fall below the GiGPO baseline?

  2. (W1) Can you evaluate on an environment that’s less templated, or one the generator is unlikely to have seen (e.g., ScienceWorld, WebArena, or a newly built task)?

  3. (W1, clarification) In Sec. 4.2, who turns the rubric into executable checks, and how? Is this automatic, LLM-written code, or hand-written per environment? How much human engineering does a new environment need? Who supplies the {success condition} and {failure modes} fields in Prompt Box A?

  4. How does HiRUB compare with milestone-based credit assignment such as BEACON (see below), which also uses environment-defined milestones on ALFWorld/WebShop and reports gains over GRPO and GiGPO?

References:

BEACON: Milestone-Guided Policy Learning for Long-Horizon Language Agents (https://arxiv.org/abs/2605.06078)

Reviewer_sUnmOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies coarse outcome rewards and the cost of online LLM judging in long-horizon agent training. The proposed HiRUB generates hierarchical rubrics offline and uses environment-specific checks to score complete trajectories based on task progress, semantic constraints, success, and penalties. These scores can be used with existing RL optimizers. Experiments report success-rate gains on ALFWorld and WebShop, while a matched ALFWorld comparison shows lower training time than online LLM judging.

Critical strengths

HiRUB is a practical and low-cost reward design, where it uses executable checks to evaluate task-relevant progress without calling an LLM judge for every rollout.

Critical weaknesses
  1. Generalization beyond structured environments remains uncertain. The method relies on task schemas, fixed grammars, and environment-specific checks. Since both evaluated benchmarks have stable structures, the experiments do not establish how much engineering is needed or how well the method works in less templated environments.

  2. The specific benefit of LLM-generated rubrics is not fully isolated. The ablations support the reward components, but do not establish an advantage over a carefully designed human-authored reward using the same task information. It remains unclear how much of the gain comes from LLM generation versus task knowledge and executable checks.

Questions for authors
  1. How are generated rubrics turned into executable checks, which steps require manual work, and how much additional work is needed for a new environment?

  2. Could a human-authored rubric achieve similar gains using the same task information, check library, and RL settings?

  3. How do first-hit checks handle milestones that are later undone or reached in a logically invalid order, and can the authors provide relevant failure-case analysis?

Comments on the paper

1 comment
Reviewer_vwrUOpenReview ↗

Response to rebuttal

Thanks for your responses to the raised questions. For Q1, as was my concern, poorer rubrics lead to poorer downstream success. Similarly, for Q3, it seems very obvious the level of intensive effort required will be to design these rubrics for another task. I could anticipate these having worked on AlfWorld and similar datasets/research directions in a great depth. I acknowledge the responses for Q2 and Q4, and my concerns are addressed for those.

Since my primary concerns are with respect to the assumptions made behind the approach, and the rebuttal responses indeed verify those details - I recommend the authors to revise these assumptions to make this work stronger in subsequent submissions. I will maintain my score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.