acceptodds
Under review as a conference paper at ICLR 2027

ASTER: Closing the Control Gap via the Agent-state Transactional Execution Runtime

Abstract

Agent systems accumulate increasingly rich structure across model calls—memories, plans, resources, observations, and execution histories—only to flatten it into context when the next decision arrives. Once flattened, that structure can tell the model what is connected, but it cannot make those connections operational: every new event again relies on model inference to determine which consequences follow, how far they propagate, and what prior state should survive. We call this gap between represented structure and executable state change the control gap. Starting from this observation, ASTER (Agent-State Transactional Execution Runtime) takes a different path: rather than treating structured relations only as context for model inference, it makes them executable at runtime. ASTER represents committed state as a versioned typed hypergraph whose relation contracts derive the scope of change and successor conditions for each event. The model proposes a transition, while ASTER certifies its realized effects before atomic commit. Across nine external benchmarks spanning single-agent, multi-agent and visually grounded embodied tasks, interactive service and web environments, and code generation, outperforms popular baselines in all settings. ASTER can also plug into an existing agent harness as its planning-state runtime, showing that its transition semantics are not tied to a particular actor loop.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM agents, embodied agents, typed hypergraph, agent runtime

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_ZwGPOpenReview ↗
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.

1 comment
AuthorsOpenReview ↗

Rebuttal by the authors

W5: 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.

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.

Benchmark (n)ALFWorld (134)ScienceWorld (144)WebShop (300)AsgardBench (54)PARTNR (100)ParaCook (72)τ2-bench (266)AutomationBench (60)SWE-Amend (100)
ASTER70.1549.3136.0074.0785.0079.1786.8426.6761.00
95% CI[61.9, 77.2][41.3, 57.4][30.8, 41.6][61.1, 83.9][76.7, 90.7][68.4, 86.9][82.3, 90.4][17.1, 39.0][51.2, 70.0]

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.

Benchmark (n)vs. GraSP: wins / losses, p (Holm)vs. FlatReplan: wins / losses, p (Holm)
ALFWorld (134)25 / 9, p = .009 (.036)14 / 8, p = .29 (.29)
ScienceWorld (144)32 / 15, p = .019 (.056)32 / 18, p = .065 (.13)
WebShop (300)45 / 20, p = .0026 (.013)42 / 16, p = .0009 (.0052)

Table S4. Success rate over three runs (the Table 1 run and two further runs), mean ± sample SD.

Benchmark (n)ASTERGraSPFlatReplanUnmodified Codex
ALFWorld (134)69.9 ± 0.458.5 ± 0.464.9 ± 0.7—
τ2-bench (266)87.5 ± 0.883.2 ± 0.982.0 ± 1.4—
SWE-Amend (100)63.3 ± 2.552.7 ± 3.560.0 ± 2.648.7 ± 2.5

Our findings are:

  • The advantage is significant in paired tests. ASTER is highest on all nine benchmarks (sign test p = .004). Pooled over the three single-agent text benchmarks, the exact paired tests give p = 1.8e-6 against GraSP and p = 6.7e-5 against FlatReplan.
  • ASTER has the highest mean over three runs. This holds on ALFWorld, τ2-bench and SWE-Amend (Table S4).
  • On SWE-Amend, ASTER improves Codex itself. As the planning runtime inside Codex, it raises Codex's success in Table 1 and on average over the three runs, and its mean is above FlatReplan's (Table S4).
Reviewer_BhBjOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how an LLM agent should update the structured state it maintains (plans, memory, resources) when a new event occurs during execution. Whereas prior work has focused on the context gap, i.e., giving the model the information it needs, the paper identifies a control gap: the information is available, but it does not properly control how the state is actually changed (Sec. 1). A good update is formalized as transition integrity: the successor state reflects what the event requires (incorporation), and nothing outside the region that may be revised is changed (preservation) (Def. 2.1). The proposed runtime, ASTER, stores the state as a versioned typed hypergraph whose relation types are bound to five contract families. For each event, the runtime follows these relation contracts to compute the writable region and the obligations the successor must satisfy; the LLM proposes a patch inside that region, and the runtime checks the patch and commits it atomically only if it passes (Sec. 3). Appendix B shows that a certified commit satisfies transition integrity when the derived region and obligations are consistent with the ideal ones (Cor. B.11). On nine benchmarks covering embodied tasks, multi-agent coordination, service and web tasks, and code, ASTER reaches the highest task success against GraSP, FlatReplan and Codex, with margins over the strongest baseline from 3.0 points (SWE-Amend) to 23.6 points (ParaCook) (Table 1). GraSP and FlatReplan share ASTER's ReAct actor, backbone and budget, and on SWE-Amend all three run as planning plugins inside Codex (Sec. 4.1). The authors also report that ASTER uses fewer model calls than both planning baselines on seven of the eight benchmarks (Fig. 4), and Appendix F analyzes individual mechanisms under single events, repeated events and concurrent writes.

Critical strengths

S1. Treating state updates as a problem of controlling state transitions, not of replanning The paper separates two problems: giving the model the information it needs (the context gap), and making that information actually control how the state changes (the control gap) (Sec. 1). I find this framing meaningful. In long-horizon and multi-agent settings in particular, when a new event occurs, the agent needs to keep the work it has already finished and revise only what is necessary. What I find interesting is that ASTER treats this as keeping state transitions consistent rather than as simple replanning (Def. 2.1). The system design built on this view is also interesting: it uses a typed hypergraph and executable relation contracts to derive the revision scope and to check revisions against it (Sec. 3).

S2. Consistent gains on nine benchmarks, and analysis of each mechanism under repeated events and concurrent writes The paper reports consistent improvements for ASTER on nine different benchmarks (Table 1) and experimentally analyzes the effect of individual mechanisms under repeated events and concurrent writes (App. F.4). For example, across 240 episodes with two concurrent writers, the full runtime commits no conflicting write, while removing the version guard lets conflicting writes through in 16 episodes. I view both the benchmark results and these concurrency diagnostics positively.

Critical weaknesses

Reading the paper, I had three main concerns:

  1. It is unclear whether ASTER's gains come from the proposed runtime mechanisms or from the structured domain knowledge provided in advance.
  2. The paper emphasizes certification and transactions, but the experimental evidence that they actually improve transition integrity is mixed.
  3. The reproducibility of the main baseline and the statistical reliability of the results are not sufficiently established.

W1. How the initial hypergraph, domain schemas and verifiers are built is unclear My biggest concern is that it is unclear how the initial hypergraph, domain schemas and registered verifiers used by ASTER were built. At its core, ASTER propagates the effect of an event along relation contracts and checks whether a revision made inside the permitted region meets the requirements. The correctness of the predefined graph and contracts therefore inevitably has a large effect on the performance of the whole system. However, the paper does not sufficiently explain how the initial hypergraph is created for each benchmark, how domain-specific relations are mapped to the five contract families, or whether the registered verifiers are written by hand. Sec. 3.1 and App. C.1 only say that a domain schema binds the relation vocabulary to the contract families, Sec. 3.3 only says that obligations are checked with registered verifiers, and App. D gives only the grounding and patch-proposal prompts. This leads to two problems.

  • Fairness of the comparison. If ASTER alone received hand-written domain-specific preconditions or invariants, the performance gap to the baselines may come not only from the runtime design but also from this extra domain knowledge. Using the same LLM, ReAct actor and execution budget (Sec. 4.1) does not by itself mean that the methods had the same information.
  • Applicability to new domains. If schemas and verifiers have to be written by hand for every new environment, ASTER's performance may rely on rules designed for specific domains. Being able to plug ASTER into another agent harness is therefore a different claim from generalizing to new domains without extra design work.

The paper should describe this implementation concretely and disclose the settings for each benchmark. If possible, a comparison in which the baselines receive the same domain information is also needed. Specifically, for each benchmark, were the initial hypergraph, domain schema and verifiers written by hand, generated by an LLM, or taken from information the benchmark provides? Did the baselines receive the same domain knowledge? Finally, no code link is provided. Since the system relies heavily on schemas and verifiers, releasing them is necessary for reproduction.

W2. What certification and transactions actually contribute is unclear One of the paper's main contributions is to check the patch the LLM proposes before committing it atomically. However, the diagnostics in Appendix F show an interesting result. In Table F.2(a), when the writable region derived by typed closure is given to the proposer (Codex CLI) only as guidance, with no checks at commit time, the transition-integrity rate (TIR) is 93.8%. In Table F.2(b), by contrast, full ASTER with the complete transaction reaches 76.0%, and the Codex-host setting, which uses Codex CLI as the proposer, reaches 71.8%. Much of this gap is related to transitions where no valid patch is committed: full ASTER installs no revision on 94 of the 450 transitions. Of course, the two panels do not use exactly the same controlled conditions, so this difference cannot be read as a negative effect of certification alone. The repeated-event and concurrent-write experiments also show effects of the version guard and other runtime mechanisms (App. F.4). Still, the paper does not sufficiently explain what net benefit the full transaction adds over typed boundary guidance, which already reaches high transition integrity with a single event. Preventing incorrect state changes is important, but if certification also blocks changes that are needed, that cost has to be evaluated too. The paper needs an experiment that adds or removes only certification while keeping the proposer, inputs, writable region, and inference and retry budgets the same. This comparison should also be extended to repeated events and concurrent writes.

Questions for authors

Clarifications

Q1. How were the initial hypergraph, domain schemas and verifiers built for each benchmark? (W1) For each benchmark, were the initial hypergraph, domain schema and registered verifiers written by hand, generated by an LLM, or taken from information the benchmark provides? Did the baselines receive the same domain knowledge? Also, no code link is provided. Since the system relies heavily on schemas and verifiers, releasing them is necessary for reproduction.

Q2. Does the guarantee cover ideal transition integrity, or only the rules the runtime computes? The paper presents a theoretical result that certified commits satisfy transition integrity (Sec. 3.3, App. B.4). However, what the runtime actually checks is not the ideal writable region and obligations, but the region and obligations it computes itself. Corollary B.11 also states that ideal integrity is guaranteed only under additional inclusion and entailment conditions (Eq. 13). In practice, in Appendix F.1 the computed region matches the ideal region exactly in only 37 of 150 cases and is larger in the rest. This does not necessarily mean that incorrect commits occurred, but it also does not mean that ideal transition integrity is theoretically guaranteed for every commit. The authors should therefore clearly separate certification against the runtime's computed rules from a guarantee of ideal transition integrity. My point is not that the theory is wrong, but that the scope of the guarantee and the description of the contribution should be stated more precisely.

Q3. What exactly is removed in w/o contracts? One of ASTER's core elements is using relation contracts as executable semantics. Yet in the ablation in Figure 5, full ASTER solves 28 of 38 tasks and the version without contracts solves 27. That is a difference of one task, and it is not clear what exactly was removed in w/o contracts (Sec. 4.3). There are differences in the cost and execution-error metrics (Fig. 5b), and Appendix F.4 also shows effects of some structural mechanisms. So I do not conclude that the contracts have no effect, but more direct evidence is needed (R4).

Q4. Is the new contribution the control gap itself, or adapting existing ideas to LLM agents? The ideas of the control gap, transition integrity and a transactional runtime are interesting, but their individual elements are closely related to prior work. Incorporating new information while preserving existing information connects to AGM belief revision, and propagating changes along dependencies resembles truth maintenance systems. Version checking and atomic commit are related to optimistic concurrency control. Work such as SagaLLM also addresses state consistency and transactions in LLM-based multi-agent systems. None of these are cited in the paper (Sec. 5, App. A). This does not mean that they solve exactly the same problem as ASTER. But the paper should make clear whether its new contribution is identifying the control gap itself as a problem, or integrating existing state-management and verification ideas and adapting them to the execution state of LLM agents. Using typed relation contracts to derive revision permissions and obligations looks like the most important difference. The citations and the technical comparison with this related work should therefore be strengthened.

Q5. How was GraSP implemented, and which of its components were kept or adjusted? GraSP is the paper's main structured plan-repair baseline. In this paper, however, GraSP does worse than FlatReplan on ALFWorld (58.21% vs. 65.67%) and ScienceWorld (37.50% vs. 39.58%) (Table 1), whereas the original GraSP paper reports substantial gains over ReAct across several backbones (Table 1 of Xia et al., 2026). Of course, the two papers differ in models, evaluation metrics, execution budgets and environment settings, so the numbers cannot be compared directly, and ReAct and FlatReplan are not the same method. Still, it is important to confirm that GraSP, the main point of comparison, was implemented properly. In particular, the paper should explain how the components of the original GraSP system, such as skill retrieval, memory, graph compilation and local repair, were kept or adjusted (App. D.2, E.2).

Requested experiments

R1. Comparison with baselines given the same domain information (W1) If possible, give the baselines the same domain information that ASTER receives, such as hand-written preconditions and invariants, and compare again. This separates the effect of the runtime design from the effect of the extra domain knowledge.

R2. Adding or removing only certification (W2) Keep the proposer, inputs, writable region, and inference and retry budgets the same, and add or remove only certification. Run this comparison in the single-event setting and extend it to repeated events and concurrent writes, so that both the incorrect changes certification prevents and the necessary changes it blocks are measured.

R3. Statistical analysis of the main results (Table 1) ASTER has the highest success rate on all nine benchmarks, which is a positive result. On some benchmarks, however, the gap is small: 61% vs. 58% on the 100 tasks of SWE-Amend, and about 6 of 134 tasks on ALFWorld (70.15% vs. 65.67%, Table 1). For differences this small, repeated runs, per-seed variation, confidence intervals or per-task paired tests are important. Table 1, however, gives a single success rate per benchmark, so variability and statistical significance are hard to judge. Since Appendix F.4 already uses McNemar tests with Holm correction, a comparable analysis for the main benchmark comparisons would be welcome.

R4. Direct evidence for the contribution of relation contracts (Q3) Beyond the one-task difference in Figure 5, more evidence is needed that directly shows how much the executable relational semantics, the paper's core contribution, actually matter.

R5. Validating the GraSP implementation (Q5) If the authors reproduce a representative setting from the original GraSP paper, or show that their modified implementation is valid, confidence in ASTER's relative advantage would increase.

If the questions above are resolved and the requested experiments are carried out well, I will raise my score.

Reviewer_4tegOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper argues that giving an agent its structured state as context does not make that structure control how the state changes, which it calls the control gap. ASTER stores agent state as a versioned typed hypergraph whose relation types define how a change propagates. When an event arrives, the runtime derives which state may change and what the result must satisfy, the LLM proposes an edit within that scope, and the runtime checks the actual edit on a copy before committing it atomically. On nine agent benchmarks with gpt-5.4-mini, ASTER beats FlatReplan, GraSP and Codex by 3~24 points while using fewer model calls.

Critical strengths
  1. The evaluation is broad. Embodied, multi-agent, web/service and coding settings use a shared actor, backbone and budgets, and cost is reported.

  2. Consistent gains across different environments, with fewer calls.

Critical weaknesses
  1. The major concern is where the domain knowledge comes from. ASTER needs a per-domain schema, registered verifiers and invariants, but the paper does not provide who writes these for each benchmark, how much work it takes, or whether the verifiers see environment state the baselines cannot.

  2. The evidence is weaker than the framing. Table 1 is single-run, and several gaps are small for the task counts. The ablations use 38 ALFWorld tasks. The oracle diagnostic is built by the authors around the same typed semantics, so good results there are partly by construction.

Questions for authors
  1. For each benchmark, who prvoides the schema, verifiers and invariants, how large are they, and do the verifiers access hidden environment state?

  2. Can you run a control where GraSP or FlatReplan gets the same schema and verifiers as a check-and-retry layer, but no typed closure or transactional commit? This would separate the runtime's contribution from the domain knowledge.

  3. Can you report multiple seeds or bootstrap CIs for Table 1 and the ablations?

3 comments
AuthorsOpenReview ↗

Rebuttal by the authors

Q2: Can you run a control where GraSP or FlatReplan gets the same schema and verifiers as a check-and-retry layer, but no typed closure or transactional commit? This would separate the runtime's contribution from the domain knowledge.

Thank you for the suggestion. We ran this control, and ASTER still outperforms the baselines. GraSP and FlatReplan received the same schema and verifiers that ASTER uses, applied as check-and-retry with the same retry budget, with no typed closure or transactional commit. We ran three runs per arm on ALFWorld (134 tasks) and ParaCook (72 tasks).

Table S1. Baselines with ASTER's schema and verifiers as check-and-retry, mean ± sample SD over three runs. On ParaCook, the Baseline column gives the Table 1 values.

BenchmarkMethodBaseline+ ASTER's schema and verifiers (check-and-retry)ASTER
ALFWorldGraSP58.5 ± 0.464.2 ± 1.369.9 ± 0.4
ALFWorldFlatReplan64.9 ± 0.766.9 ± 1.669.9 ± 0.4
ParaCookGraSP55.6 (Table 1)57.9 ± 3.581.0 ± 2.1
ParaCookFlatReplan26.4 (Table 1)37.5 ± 2.481.0 ± 2.1

The results show that the schema and verifiers help the baselines, and ASTER remains ahead of them on both benchmarks. The remaining gap is the contribution of the runtime, namely typed closure and transactional commit.

AuthorsOpenReview ↗

Does our response address your concerns?

Thank you so much for your time and effort in reviewing our work and providing insightful feedback. As the review discussion phase concludes in two days, we kindly request you review our response and confirm if it addresses your concerns. We welcome any further discussions and value the opportunity for continued improvement of our work.

Thank you for the detailed response and the additional experiments. The repeated runs and ablations strengthen the proposed approach, therefore I raise the score from 2 to 3.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.