acceptodds
Under review as a conference paper at ICLR 2027

Progress Rates Can't Tell Shortcuts from Progress: Landmark Properties for Scoring Agents

Abstract

Declaring a step done is not doing it, yet agent benchmarks often score the two alike. Benchmarks give failing agents partial credit for checkpoints reached, but no rule in use asks how each checkpoint was reached. To our knowledge, no prior work states what such a score must satisfy. We supply that standard. From automated planning we take the order a task imposes on its milestones and state four properties a progress score needs. No score that reads only a run and its checkpoints can reliably detect skipped steps. The limit lies in the checkpoint list itself, not in the rule, and adding the milestone order removes it. We audit nine scoring rules, score every legal run in six task families, and test seven language models. The rules in use either ignore skipped steps or reward them. AgentBoard's published progress rate can rank a run that skips steps above a flawless one. Reanalyzing TheAgentCompany's released runs, we find that its final-checkpoint bonus alone produces 55 of 525 perfect scores. When an unlabeled shortcut appears among shuffled options, all seven models take it, and the published rate largely ranks them by how often they do. Our metric, weighted support, reverses that ranking. Given the milestone order and what each action required, it satisfies all four properties in one pass. Under weighted support, work that skips a prerequisite earns no credit, and neither does any work built on it.

Primary area:
datasets and benchmarks
Keywords:
agent evaluation, progress metrics, planning landmarks, axiomatic evaluation, shortcut behavior, reward hacking, LLM agents, benchmark auditing, partial credit, Simpson's paradox

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_mXaqOpenReview ↗
Rating
2
Confidence
2
Informativeness
3(+1)
Presentation
3(+1)
Soundness
3(+1)
Read review
Paper summary

The paper asks what a partial-credit progress score for LLM agents should satisfy. It borrows landmarks and greedy-necessary orderings from automated planning, and calls a landmark supported when the step that first achieved it required the landmark's immediate predecessors and those predecessors were themselves supported. It states four properties (monotone, order-invariant, order-sensitive, normalized) and proves that no metric reading only the trajectory, its operators, the landmark set and the goal can be order-sensitive on every task (Theorem 1). Weighted support, the weighted share of supported landmarks, satisfies all four in linear time (Theorem 2). An audit of nine scoring rules finds that only weighted support passes. The published AgentBoard progress rate also fails normalization and, when shortcuts exist, is maximized by runs that skip prerequisites. Exhaustive enumeration of synthetic job-chain tasks shows that, at a fixed budget, the rate falls as goal completion rises. In the agent studies, six 1-1.7B models and Qwen2.5-7B pick actions from a list that includes an unlabeled "mark job complete" option; the rate rises with marking while weighted support falls. A reanalysis of TheAgentCompany attributes 55 of 525 full scores to its final-checkpoint bonus.

Critical strengths

S1: The paper turns a real concern in agent evaluation into a checkable standard: partial-credit scores can reward a test that passes because its expected values were rewritten (line 165). P1–P4 give a common yardstick. Auditing nine scoring rules used by benchmarks against it shows that only weighted support separates skipped prerequisites from real work (Table 1).

S2: The audit of released benchmark code is concrete and immediately actionable. AgentBoard's AlfWorld and ScienceWorld code computes landmarks achieved rather than its published per-step formula (K.2), TheAgentCompany's final-checkpoint bonus fires on 54 of 175 tasks (B.6), and pooling reverses the within-instance correlation (−0.439 vs +0.064, Figure 4). Maintainers can fix these without changing any task.

S3: The formal results are sharp and correct. The published per-step formula can score a complete, correct run below 1 (Proposition 1). When shortcuts exist, only runs that skip prerequisites reach its maximum (Proposition 4). Weighted support runs in linear time and satisfies P1–P4 (Theorem 2). I checked every proof and brute-forced Theorem 1 and Proposition 4 on small cases.

Critical weaknesses

W1: The main limitation is applicability. The decisive input is each executed action's preconditions, not the ordering: DevAI, LAMA and ToolSandbox read the order and still fail P3 (Table 1). For rewritten tests (K.3), judging the achiever unsound is itself the detection problem. Real environments rarely expose preconditions (lines 468–469), and weighted support is not yet computed on an existing benchmark.

W2: The synthetic experiments mainly illustrate the theory. I tried to enumerated all 6,014,400 legal runs: the rate correlates 1.000 with jobs started (Proposition 1b), so its negative link to goal completion follows from the budget. In study B, marks are half the options (H.5) and uniform choice marks in 99.9% of episodes (line 398), so the shortcut-taking result reflects this base rate.

W3: The theory is modest in depth. Theorem 1 follows directly from defining P3 through an ordering the metric cannot see ("elementary", line 206). P1–P4 also admit metrics that pay for shortcuts: the paper's own average of landmarks achieved and weighted support scores a shortcut-only run above a supported one (K.4). Only P3+, which characterizes weighted support (A.9), excludes this.

Questions for authors
  1. Computing weighted support, or the timing-only rule, on trajectories from an existing benchmark would most raise my assessment. Where would the specification-level preconditions of an action such as "run tests" come from?
  2. TheAgentCompany's task README says its bonus strategies are meant for tasks with more than one approach or with trajectory-based checkpoints, and by your argument at line 237 a checkpoint list records one route. Could you check whether any of the 55 full scores skipped a true prerequisite rather than took another route?
  3. Qwen2.5-7B marks at 0.22 against a listed share of 0.50 (H.5). A control where marks are a minority of the options, or where the prompt says the stages must actually be done, would show whether any model seeks the shortcut beyond chance.
5 comments
AuthorsOpenReview ↗

Response to Reviewer mXaq: Benchmark Validation, Shortcut Controls, and Theory

Thank you for the careful review, particularly for checking the proofs and reproducing the small cases. Your main concerns are practical applicability, the shortcut-option baseline, and what the axioms establish. We address these together with your three questions.

W1/Q1: Weighted support is now computed on existing benchmarks.

We added native ALFWorld and IPC planning experiments using executable operator schemas and checked landmark dependencies. The specification is shared across agents and valid routes; it does not require a separate prescribed path for each trajectory.

The ordering and achiever checks serve different purposes: the ordering identifies necessary dependencies, while the achiever check determines whether the executed step required them. Reading the ordering alone is therefore insufficient, as our audit demonstrates. Conversely, Theorem 1 holds executed operators and their preconditions fixed across the two specifications, showing why those inputs alone cannot determine the required ranking either.

For “run tests,” evidence that the authorized suite was executed must come from protected tests or verified suite identity and execution records. Weighted support does not infer this from “tests passed.” It converts such local verification into a consistent score and propagates unsupported status through dependencies. Verification is needed at landmark first-achievers.

The new results establish implementation beyond constructed domains. Among 16 selected successful native oracle trajectories satisfying the initial-goal assumption, 13 receive less than full credit under the published progress-rate formula. Weighted support also has stronger goal-completion correlation in 39/39 matched compatible task/horizon cells. These are dependent descriptive comparisons, and the rate itself is positive in 37/39 cells. We retain unavailable preconditions in open-ended environments as a limitation rather than claim universal automatic verification.

Q2: Seven cases lack a genuine prerequisite, after distinguishing alternative routes.

Human review with adjudication classifies the 55 cases as 7 skipped prerequisites, 24 valid alternatives, 12 grader false negatives, 4 independent unmet requirements, and 8 unknowns.

The seven prerequisite cases concern one backlog-update workflow. Its instructions require genuine chat confirmation before acknowledging completion and updating status. These trajectories receive 5/5 without that confirmation; some explicitly simulate or author it themselves. The finding concerns this required component, while uncertainty about the compound checkpoint is retained.

Your question also exposed an attribution error, which we corrected: 45 tasks, not 54, use the final-checkpoint strategy. It accounts for 47/55 bonus-only perfect scores; other strategies account for the remaining eight.

W2/Q3: The controls show behavior beyond displayed option frequency for some models.

With minority shortcut options, SmolLM2 selects marks at 1.65× [1.12, 2.14] the conditional menu baseline and granite at 1.94× [1.35, 2.48]. With minority options plus explicit instructions, granite remains above baseline at 2.92× [2.43, 3.38]. These simultaneous task-instance bootstrap intervals exclude one. Thus, displayed option frequency alone does not explain these outcomes.

We do not extend that conclusion to every model. Qwen2.5-7B does not show above-baseline preference, and free-command use is rare. The conditional menu baseline is also distinct from an independent random-policy rollout. Our scoring conclusions concern how unsupported achievements are credited, regardless of which models produce them.

The exhaustive synthetic study quantifies the mechanism across the bounded run space. The native experiments now test its relevance beyond that construction, without claiming universal negative correlation.

W3: The stronger characterization is already part of the theoretical contribution.

P1–P4 are necessary conditions, and the paper explicitly constructs their insufficiency counterexample. Appendix A.9 then characterizes weighted support using P3+, normalization and additivity under the stated realizability assumption. Thus, the gap you identify is analyzed within the contribution.

Theorem 1 provides the information requirement; the characterization, linear-time construction and benchmark audit establish the broader result. We have made that progression more prominent.

Revisions. Sections 6–7 report the controls and native evaluation; Appendices B.6, L and M provide adjudication and complete results. Section 4 highlights P3+, and Section 9 states the applicability limits. The original metric and formal results are unchanged.

Thank you again for the specific questions, which led to stronger validation. We welcome further questions about the implementation, controls or adjudicated cases.

Thank you for the detailed response and the new experiments!

W1/Q1: The native ALFWorld and IPC results show that weighted support can be computed on existing benchmarks. However, both environments define preconditions in their operator schemas and enforce them during execution, so they leave little room for the skipped-prerequisite shortcuts the paper targets. For actions such as “run tests”, detection still rests on external verification, so my concern about applicability remains.

Q2: Thank you for the adjudication and the correction from 54 to 45 tasks. Only 7 of the 55 full scores skip a genuine prerequisite, all in one workflow, so the real-benchmark evidence for rewarded shortcuts is narrower than the submitted version suggested.

W2/Q3: The minority-option controls answer Q3: SmolLM2 and granite take the shortcut beyond chance, while Qwen2.5-7B does not.

W3: Highlighting P3+ in Section 4 helps. My point concerned the depth of Theorem 1 and P1–P4, and I have no further question here.

AuthorsOpenReview ↗

Follow-up to Reviewer mXaq on prerequisite verification and benchmark evidence

Thank you for the follow-up. The native results show that weighted support can use benchmark-provided preconditions. Our audit of TheAgentCompany addresses your concern about what evidence a grader needs to verify how an outcome was achieved.

W1/Q1. Applicability and prerequisite verification

In native ALFWorld and IPC, the published progress rate awarded less than full credit to 13 of 16 successful oracle trajectories satisfying the initial-goal assumption. Weighted support aligned more closely with goal completion in 39 of 39 matched task–horizon comparisons. These comparisons are descriptive and share tasks across horizons.

We examined prerequisite bypass using deliberately relaxed IPC executors. Under these conditions, 29 of 56 runs contained an unsupported achievement, including 13 of 40 in the subset satisfying the initial-goal assumption. This controlled experiment shows that weighted support can distinguish an achieved landmark from a supported one when bypass is possible.

For “run tests,” the task specification identifies the authorized suite, and a protected runner can record which suite actually ran and its result. Weighted support uses that evidence to assess the step that first achieves the landmark. In two released TheAgentCompany traces, an apparent confirmation preceded the issue update, and the action log showed that the agent itself had typed and submitted it. Because the task required confirmation from another participant, checking authorship was essential. Broader applicability depends on whether benchmarks can capture trustworthy evidence for their task-specific prerequisites.

The updated supplementary material includes the native and relaxed-executor experiments and the released-trace audit (R9–R11).

Q2. Scope of the TheAgentCompany evidence

Among the 55 bonus-only full scores, the adjudication identified seven cases of prerequisite bypass in one workflow and 24 valid alternative routes, underscoring the importance of distinguishing a missed checkpoint from a skipped prerequisite. The follow-up audit traced two apparent confirmations to the agents themselves. The updated supplement provides the exact event references.

These cases establish that TheAgentCompany’s bonus rule can award full credit after a required step is bypassed. Because the seven cases come from one workflow, they leave open how widespread this behavior is across the benchmark. The native ALFWorld and IPC results broaden the paper’s empirical evidence by showing that the published progress rate can also undercredit successful executions.

W2/Q3. Thank you for confirming that the minority-option controls answer Q3. We agree that the conclusion is model-specific.

W3. Thank you for clarifying your concern about the depth of Theorem 1 and P1–P4. We appreciate your feedback on making P3+ more prominent.

Reviewer_yfaAOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper investigates whether existing agent progress metrics can distinguish legitimate task progress from shortcuts that bypass required steps. It formalizes four properties for progress scoring and introduces weighted support, which uses landmark dependencies and action preconditions to determine whether a milestone has been properly achieved. Through theoretical analysis, exhaustive trajectory enumeration, audits of existing scoring rules, and experiments with seven language models, the authors demonstrate that common progress metrics can reward shortcuts and even rank them above correct executions.

Critical strengths
  • I find the central observation both simple and important: reaching a milestone is not the same as earning it. The paper exposes a fundamental weakness in how agent benchmarks assign partial credit. This becomes especially consequential when progress scores are reused as training rewards rather than just evaluation metrics.
  • I quite like the combination of formal analysis and concrete empirical counterexamples. The exhaustive enumeration shows that higher progress rates can systematically correspond to fewer completed goals, while the audit of TheAgentCompany identifies real scoring discrepancies. These findings make the issue more compelling than a purely theoretical objection.
Critical weaknesses
  • I'm still concerned that weighted support permanently penalizes an early mistake, even after the agent corrects it. Because support depends on the first achievement of a landmark, an agent that initially skips a prerequisite but later completes the missing work may never receive credit for its recovery. For long-horizon agents, detecting and correcting mistakes is itself an important capability, and I am not sure the proposed metric properly captures it.
  • The approach relies on a fairly strong notion of what constitutes a required step. Weighted support assumes that landmark orderings and action preconditions are available and correctly specify the task. In realistic agent workflows, however, these dependencies are often implicit or incomplete. More importantly, a seemingly skipped intermediate step might sometimes represent a legitimate alternative solution rather than an invalid shortcut. This makes the boundary between procedural compliance and actual task progress important to clarify.
Questions for authors
  • Suppose an agent initially reaches a landmark through an invalid shortcut, then completes the missing prerequisites and correctly re-establishes the landmark. Should this eventually receive full credit? How could weighted support accommodate such recovery without rewarding the original shortcut?
  • How should the metric handle a valid alternative procedure that achieves the task goal without following the originally specified intermediate milestones? What guarantees that the landmark ordering captures necessary dependencies rather than one preferred workflow?
1 comment
AuthorsOpenReview ↗

Response to Reviewer yfaA: Recovery Credit and Valid Alternative Procedures

Thank you for emphasizing the distinction between reaching a milestone and earning its credit, particularly when progress scores become training rewards. Your concerns help clarify how the metric credits work during repair and distinguishes necessary requirements from a preferred workflow. We address the weaknesses and questions separately.

Weakness 1: An early shortcut does not freeze the trajectory’s score.

Weighted support continues to credit supported work after an early mistake. When the agent completes missing prerequisites through supported actions, those landmarks receive credit and the score increases. Other subsequently supported landmarks also contribute.

What remains unchanged is the support status of the landmark first reached through the shortcut. The metric therefore records supported work throughout the execution while preserving whether the initial achievement was justified. Final task success separately records eventual completion.

Our original agent records contain 42 sound final-stage re-achievements across 39 episodes, making this distinction empirically relevant. We clarify that supported progress during repair and credit for re-establishing an initially unsupported landmark are different quantities.

Weakness 2: Task requirements can be specified once in the benchmark harness.

The added ALFWorld and IPC experiments demonstrate implementation using executable operator schemas and checked dependencies supplied at the benchmark-harness level and reused across agents. Agents may choose different valid procedures under this shared specification.

Our TheAgentCompany adjudication directly examines whether omitted checkpoints reflect valid alternatives. It distinguishes 24 valid alternative routes and 12 grader false negatives from 7 full-score executions missing required confirmation in one workflow. The positive finding concerns that required confirmation component, with uncertainty about the compound checkpoint retained. This separates necessary task requirements from reference-workflow compliance.

Question 1: Should a repaired execution eventually receive full credit, and how could recovery be accommodated?

For eventual task completion, a genuinely repaired execution can receive full success credit. Under the current weighted-support definition, however, its score can remain below one because support is determined at first achievement. Completing the missing prerequisites earns their supported credit; re-establishing the initially unsupported landmark does not change its first-achievement status.

A recovery-aware extension could grant support at a later verified achievement event, once the required predecessors are supported and the new achiever satisfies the specification. The original shortcut earns nothing; credit begins at the verified repair. Full credit would require every scored landmark to become supported. This extension would require separate formal analysis. The current definition preserves its interpretation as supported first-achievement progress.

Question 2: How are valid alternatives handled, and what establishes that dependencies are necessary?

A landmark must be necessary across valid solutions, and an ordering must express a necessary dependency under the task specification. A step belonging only to one preferred procedure should not be imposed universally. Where appropriate, alternative procedures can be represented by a disjunctive landmark.

Necessity must be justified through domain semantics, sound landmark extraction, or specification review. Weighted support evaluates achievement against these justified inputs. If a valid solution bypasses a purported landmark, that is evidence to revise the specification rather than reject the solution.

Our benchmark implementations show how executable schemas and dependency checks can provide this justification in shared evaluation infrastructure. The adjudicated alternative routes demonstrate why a reference trajectory alone is insufficient.

Revisions. The revised discussion distinguishes supported repair work, first-achievement history, and final task success. Sections 6–7 and Appendices B.6, L and M provide the additional benchmark evaluation and adjudication. The original metric and formal results are unchanged.

Thank you again for these questions. We welcome further discussion of recovery-aware scoring and the benchmark specifications.

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

This paper borrows landmarks and their orderings from automated planning to propose four properties that partial-credit metrics for agents should satisfy. It proves that metrics reading only checkpoints cannot detect skipped prerequisites, and introduces weighted support, which satisfies all four properties. It then audits nine existing scoring rules and tests them on synthetic job-chain tasks with small open models.

Critical strengths
  1. The audit of deployed benchmarks is concrete and verifiable, with file and line references. AgentBoard’s released code computes landmarks achieved rather than its published progress rate: under the published formula, 92 of 134 AlfWorld tasks cannot reach full credit, yet all 174 successful tasks score 1.000 under the code.

  2. The analysis clearly exposes problems with the published progress-rate formula. When subgoals are consumed, a complete and correct run cannot reach full credit, and the score rewards starting many jobs over finishing them.

Critical weaknesses
  1. Evaluation is toy. All experiments use generated job-chain domains with landmarks known by construction, and the agents are 1~7B models that copy one line from an option list. No agent is run on a real benchmark.

  2. The problem only exists when the evaluation itself is flawed. I think fixing the checker (e.g., hidden or read-only tests) is the more direct remedy. Weighted support also needs action preconditions and orderings that real benchmarks rarely expose. In tasks with many valid routes (e.g, math proving), landmarks become sparse, so the metric degenerates to binary success.

  3. The axioms describe progress, not value or safety. Under P1 and P4, destructive or malicious actions taken after the task is done cannot lower the score, and a run that only takes shortcuts scores 0, the same as doing nothing.

Questions for authors

See weaknesses.

1 comment
AuthorsOpenReview ↗

Response to Reviewer pdSw: Benchmark Evaluation, Practical Applicability, and Metric Scope

We appreciate your close examination of the benchmark audit and progress-rate analysis. Your review asks whether the approach works beyond synthetic tasks, whether its specification requirements are practical, and what its guarantees mean for safety. The added experiments and revised discussion address these concerns directly.

1. Evaluation beyond synthetic job chains.

We have added ALFWorld and IPC Blocksworld and Gripper experiments with Qwen2.5-7B and 14B, including 68 native-environment episodes using executable benchmark action schemas. We also evaluate successful native oracle trajectories: 13 of 16 assumption-compatible trajectories receive less than full credit under the published progress rate. Weighted support correlates more strongly with final goal completion in all 39 matched, assumption-compatible bounded task/horizon cells. These cells are dependent descriptive comparisons; the published rate itself has positive correlation in 37/39 cells.

We distinguish these native results from 56 episodes in deliberately permissive planning variants, where 29 contain unsupported landmark achievement. These variants provide controlled prerequisite-bypass tests, rather than evidence of native benchmark exploits. The additions extend the evaluation beyond constructed job chains and small option-list agents, without changing the paper’s core conclusions.

2. Checker repair, specification requirements, and alternative routes.

Protecting tests directly addresses test manipulation. Weighted support answers an additional question: how much partial credit is justified when milestones are reached without their required support? A correct final-success checker does not itself supply that answer. Our native oracle results demonstrate a scoring failure even on successful executions, without requiring a compromised checker.

In TheAgentCompany, author review with adjudication identifies 7 full-score executions missing required confirmation in one workflow, while distinguishing 24 valid alternative routes and 12 grader false negatives. This separates genuine prerequisite violations from differences in execution route.

The specification work can be handled at the benchmark-harness level and reused across agents, as our ALFWorld and IPC implementation demonstrates. The harness supplies verified dependencies and first-achiever checks; weighted support converts this evidence into consistent partial credit across valid routes. This concentrates specification work in shared evaluation infrastructure.

The achievable resolution follows the available task structure. Our benchmark results establish useful intermediate scoring where dependencies are exposed. For open-ended tasks such as theorem proving, verified necessary subgoals offer a direction for extending partial-credit resolution, provided they accommodate alternative valid proofs. The framework specifies what evidence such extensions must supply.

3. Progress versus value and safety.

The axioms measure accumulated supported progress. Monotonicity preserves credit for completed supported work, while a separate final-success or safety measure captures subsequent destruction. A shortcut-only run and an idle run both receive zero because neither establishes supported progress; their costs and harms can differ.

If used for training or selection, weighted support could discourage prerequisite bypass by withholding credit for unsupported achievements. When prerequisites encode safety-relevant checks, such as authorization or confirmation, this offers a potential route to safer behavior. Our TheAgentCompany adjudication illustrates the relevance: seven full-score executions lacked required confirmation in one workflow.

Our results establish the difference in credit assignment; whether training produces safer agents remains to be tested. Weighted support therefore contributes a specific incentive mechanism alongside final-success checks and safety measures.

Revisions. Sections 6–7 report the controls and native benchmark evaluation; Appendices B.6, L and M provide adjudication and detailed results. Section 9 clarifies specification requirements and metric scope. The original metric and formal results are unchanged.

Thank you for prompting these additional tests and clarifications. We welcome further questions about the implementation, adjudicated cases, or guarantees.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.