- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper introduces a method ASTER that maintains a hypergraph for representing agent state. It proposes executable relations that check if one state changes what else needed to be change in the agent's context, for the agent's next step proposals (or, committed state, as the authors call it).
Its contributions mainly lie in the results part. The method shows strong performance against different previous methods trying to address control gap, and seems to work well with Codex.
Critical strengths
I understand the problem that the authors aim to tackle, which is the control gap (as opposed to context gap) in LLM/VLM based agents. The authors address this issue with a verification method at test time that is formalized as (Incorporation ^ Preservation). This formulation is intuitive and well-motivated, and it could inspire future research on building agents with stronger correctness guarantees.
Critical weaknesses
I find the paper hard to follow. Although the authors provide some qualitative examples, I would appreciate a more detailed, step-by-step example (including every component) showing how ASTER works in practice, instead of highlighting the final results. It would significantly help readers understand the method.
On generalizability.
To my knowledge, the paper does not clearly explain how the executable relations and verification rules are obtained for each benchmark. I know ASTER defines five general relation contract families but it remains unclear how these contracts are generated in different environments. Does this process require heavy manual engineering? This is also important for the generalizability of the method, e.g., how easily this method can be adapted to a new environment without too much manual efforts.
On experiment validity.
While the result numbers look great and promising, they are mainly achieved with only one model, gpt-5.4-mini with a low reasoning effort. This means that the observed gains might not persist with stronger models. The authors did conduct an experiment to vary reasoning effort and backbones. But when I was checking relevant baselines (to better understand this paper), I found that the reported performance of GraSP in the original paper is a lot better than the GraSP results reported in this paper, with ~84% on ALFWorld and ~80% on ScienceWorld with GPT-4.1. Although backbone models are different, I wonder if the implementation follows the original GraSP , and what caused such performance differences.
Also, I know that AI may also say this but experimenting with multiple seeds and statistical analysis are indeed helpful for validating the main results. Especially for SWE-Amend, ASTER outperforms FlatReplan by only 3% which is hard to tell whether it's meaningful statistically.
Questions for authors
For the method, how is the initial hypergraph constructed?
For the results, I noticed a different datapoint in the budget-success rate plot in Figure 4. While on other benchmarks ASTRA has both lower cost and better performance, on ScienceWorld it has a higher cost (and a better performance). Could you analyze where that higher cost might come from?
Also, please address the concerns in my previous review sections if you'd like to.
Rebuttal by the authors
Thank you for the suggestion. Table 1 reports a single run per benchmark because of evaluation cost. Per the reviewer's suggestion, we have now added further runs and statistical tests.
Table S2. Success rate of ASTER in Table 1 with Wilson 95% intervals.
Table S3. Exact paired tests on the three single-agent text benchmarks: wins / losses on discordant tasks and the two-sided exact McNemar p-value, with the Holm-adjusted value in parentheses.
Table S4. Success rate over three runs (the Table 1 run and two further runs), mean ± sample SD.
Our findings are: