- 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
- 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?
- 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?
- 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
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.
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.
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.