acceptodds
Under review as a conference paper at ICLR 2027

Evolving Belief Memory for Continual Learning Agents

Abstract

Continual learning agents operating in environments with shared latent structure may need to carry forward reusable propositions whose evidential support remains incomplete at task boundaries. Most existing non-parametric approaches preserve raw interaction histories or compress experience into persistent solutions, strategies, or memories, leaving the evolving belief status of environment-level propositions largely implicit. We introduce Evolving Belief Memory (EBM), a non-parametric continual-learning framework that couples task-directed proposition proposal and evidence-based validation with a persistent belief state. EBM represents each belief as an environment-level proposition together with its current status and associated interaction evidence. We evaluate EBM on adapted continual Database and Poker environments across three backbone models. EBM achieves the highest mean Database reward among the compared non-oracle methods across all evaluated backbones, while remaining competitive on Poker, where performance exhibits substantially greater run-to-run variability. Persistent-state replay shows that the learned belief state benefits a fresh memoryless solver even without raw cross-task interaction history. Analyses on a controlled Database stream further show that reusable beliefs accumulate across tasks and support later task solving, while ablations support the utility of persistent belief storage and evidence-based validation. These results suggest that explicitly maintaining revisable, evidence-grounded beliefs offers a useful way to represent and carry forward learning state in continual language agents.

Primary area:
transfer learning, meta learning, and lifelong learning
Keywords:
continual learning, LLM agents

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_UzP4OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces Evolving Belief Memory (EBM), a non-parametric continual-learning framework for language agents solving successive tasks in environments with shared latent structure. EBM stores reusable environmental propositions together with their supporting evidence and current status, including hypothesized, supported, and contradicted. Before each task, a proposer suggests additions or revisions, a validator assesses the associated evidence, and a solver uses the updated memory and interaction history to perform the task. The evaluation covers adapted Database and Poker environments across three backbone models, supplemented by persistent-state replay, frozen-checkpoint experiments, and component ablations. EBM achieves the highest mean Database reward among the compared non-oracle methods, while Poker results exhibit greater variability.

Critical strengths

The replay experiments provide meaningful evidence that the accumulated memory captures reusable knowledge.

The evaluation examines the usefulness of the retained state beyond aggregate task performance. In the persistent-state replay experiment, previously learned memory is supplied to a fresh solver without raw cross-task interaction history. The frozen-checkpoint experiment further evaluates later tasks without additional belief updates (Section 4.2, Figures 3–4). These experiments support the claim that information acquired from earlier tasks can be retained and reused to improve subsequent task solving. This is a relevant strength for the paper’s continual-learning setting and provides concrete evidence for the practical value of maintaining persistent environmental knowledge.

Critical weaknesses

The distinctive research contribution of evolving belief states is not sufficiently established beyond the effectiveness of the overall framework.

The paper presents a coherent system design combining proposition generation, evidence validation, and persistent memory. Its most distinctive motivation is that unresolved propositions should be retained across tasks and revisited as further evidence becomes available. However, the experiments do not directly establish the independent value of this mechanism. Removing the entire belief state or validator (Figure 5a) does not isolate the effects of retaining unresolved propositions, exposing status labels, or applying the proposed update rules. Likewise, the replay experiments demonstrate that the retained information is useful, but do not establish which benefits specifically require an evolving belief representation. The manuscript acknowledges that these analyses do not isolate the contribution of status labels and that the history-window results cannot distinguish belief-state tracking from other forms of history compression (Section 4.2; Appendix A.4, Figure 7).

Additional inference computation also remains an unresolved factor, as the comparisons are not compute-matched (Section 4.2; Appendix A.4.1). Consequently, the results remain compatible with explanations based on effective information consolidation and additional reasoning or verification. The framework appears practically useful, but the current evidence provides limited insight into when or why explicit belief-state evolution is needed for continual learning. This gap between the distinctive motivation and its experimental validation limits the demonstrated significance of the contribution and is the primary reason for my recommendation.

Questions for authors
  1. Request for targeted experimental evidence: the role of unresolved propositions and status labels.

On the existing Database setting, how does performance change when HYPOTHESIZED propositions are not retained across tasks, while the remaining proposal and validation process is preserved? Separately, how does replay performance change when the same saved propositions and evidence are supplied without their status labels? These controls would help distinguish the value of preserving unresolved knowledge from the solver’s use of explicit status information.

  1. Request for targeted experimental evidence: the contribution under comparable budgets.

Does EBM retain an advantage over a conventional summary or proposition-list memory when both use the same proposal and validation procedure with comparable inference and memory budgets? Such a comparison would help determine whether the proposed belief representation and update mechanism provide benefits beyond additional reasoning and information consolidation. Evidence addressing this question would materially affect my assessment of the contribution.

2 comments

We thank the reviewer for recognizing that “The replay experiments provide meaningful evidence that the accumulated memory captures reusable knowledge.” We conducted additional targeted experiments addressing the reviewer's central concern about the distinctive contribution of evolving belief maintenance.

W1/Q1. Hypothesis Retention and Status-Label Ablations

We conducted both requested controls on Database using Qwen3.8-27B.

Hypothesis retention. Removing HYPOTHESIZED propositions across task boundaries reduces reward from 0.6290 to 0.5170 and accuracy from 73.0% to 60.50% percentage points, while average queries increase from 2.090 to 2.230. These correspond to decreases of 0.1120 in reward and 12.5 percentage points in accuracy. Separately, trajectory analysis of the original EBM runs reported in the paper shows that 29 of 39 initially hypothesized propositions (74.4%) subsequently reached definite statuses through revalidation, revision, or contradiction.

Status-label replay. Removing solver-visible status labels from identical saved checkpoints does not reduce average reward (0.6217 with labels vs. 0.6450 without).

These results highlight two distinct roles of belief status. The condition without solver-visible status labels achieved a higher observed mean replay reward, offering no evidence that exposing these labels improves performance in this replay setting. By contrast, retaining unresolved propositions for future revision in light of new evidence remains an important part of EBM's learning process.

See General Response, Sec. 1, for the complete ablations, four replay configurations, and proposition trajectories.

W2/Q2. Proposition Consolidation Under Comparable Budgets

We introduce a proposition-list baseline sharing EBM's proposer–validator–solver architecture, with the validator adapted to the plain-proposition representation as described in General Response, Sec. 1. Optimized EBM and proposition-list use the same raw-history window.

Optimized EBM achieves 0.5880 reward and 69.0% accuracy using 4.164M tokens, versus 0.4673 and 55.5% using 3.902M tokens for proposition-list. Thus, EBM achieves 25.8% higher relative reward with only 6.7% more total inference tokens.

For completeness, average stored memory sizes are:

MethodAvg. Memory TokensAvg. Propositions
Proposition-list1,80715.78
EBM (optimized)3,29423.12

The larger memory reflects EBM’s retention of unresolved hypotheses, evidence, and status information.

Our preliminary optimizations further reduce total inference consumption by 50.8% on Database and 70.8% on Poker, while preserving strong observed performance.

Together, the architecture-matched comparison and the hypothesis-retention ablation support EBM's central contribution: a belief-maintenance process that goes beyond conventional proposition consolidation by retaining unresolved hypotheses, while achieving these benefits without requiring the substantial inference overhead of the original implementation.

See General Response, Secs. 1–2, for the full performance tables and component-level token breakdown.

Dear Reviewer,

Thank you for your thoughtful review. As the discussion period is approaching its end, we would appreciate any further feedback if you have time, particularly regarding whether our response has addressed your main concerns.

Thank you again for your time and consideration!

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

This paper proposes Evolving Belief Memory (EBM), a continual-learning framework in which a proposer suggests environment-level propositions, a validator assesses them against interaction evidence, and a solver uses the resulting status-tracked beliefs to complete tasks. EBM is evaluated on multiple datasets and models.

Critical strengths

The authors motivate the need for agents to maintain explicit, revisable beliefs about the environment across tasks, an important and underexplored aspect of continual learning. They evaluate their approach against a broad set of baselines across multiple backbone models and two environments, and report the results with appropriate caveats.

Critical weaknesses
  1. EBM uses substantially more tokens than baselines: ~1.3-4.4× on Database with Opus and up to ~9× on Poker (Sonnet, vs. Tycho). Its reward margins are small by comparison, so it is unclear whether the performance gain justifies the added overhead.
  2. The authors acknowledge that neither the replay experiments nor Figure 7 separate the belief-status design from generic history compression. An ablation that keeps the proposer/validator pipeline but stores plain notes without status and evidence is needed to show the gains over DC, ACE, and Mem0 come from the belief representation. Novelty relative to Mem0's similar update operations and to BeliefMem, which is not compared, also needs sharper positioning.
  3. The method is largely prompt-driven, yet there is no prompt-sensitivity analysis and no study of mixing models across roles.
Questions for authors
  1. Which model serves as proposer, validator, and solver in each experiment? Is it always the backbone model? Have you tried different or stronger models for the validator, or mixed configurations?
  2. How are STALE beliefs handled after drift? Can they return to SUPPORTED, and through which operation? Does the solver see them, and with what instructions? Are they revalidated, and at what cost?
  3. What exactly do CONSTRUCTVERIFICATION and EXECUTEANDOBSERVE do? Is there a limit on probes per task, how are they charged against the query budget, and what happens when acquisition fails?
  4. Why are ACE and Mem0 results not reported for Opus4.8?
  5. How was the 20-instance raw-history window chosen? Do beliefs still help with larger or full-history windows, given that their marginal benefit shrinks as the window grows (Figure 7)?
3 comments

We thank the reviewer for the detailed feedback and for recognizing explicit, revisable environmental beliefs as “an important and underexplored aspect of continual learning.”

W1. Inference Overhead and Efficiency

We substantially reduced inference overhead without modifying EBM's belief-update mechanism.

On Database, optimized EBM achieves 25.8% higher relative reward than architecture-matched proposition-list with only 6.7% more tokens. Further pruning reduces EBM's total inference usage by 50.8%, while preserving nearly the same original reward. Poker optimization reduces tokens by 70.8% without an observed performance loss.

These results show that a substantial fraction of the original inference overhead can be reduced while retaining EBM's belief-update mechanism. See General Response, Sec. 2, for full results.

W2. Plain-Notes Baseline and Novelty

Plain-notes baseline. We introduce a proposition-list baseline preserving the proposer–validator–solver architecture but replacing evolving belief maintenance with conventional proposition consolidation. The validator is adapted to operate on plain propositions because its original status-transition rules require the belief representation being removed; all other experimental configurations remain identical to original EBM. It achieves 0.4673 reward and 55.5% accuracy, compared with 0.6290 and 73.0% for EBM.

Separately, removing HYPOTHESIZED propositions alone reduces EBM reward to 0.5170 and accuracy to 60.50% percentage points. These experiments demonstrate the importance of retaining unresolved hypotheses in the belief-maintenance process, allowing them to be reconsidered when new evidence becomes available. See General Response, Sec. 1.

Novelty relative to Mem0 and BeliefMem. Our contribution is a task-directed, evidence-governed mechanism for maintaining environmental beliefs as a persistent learning state across continual tasks. EBM couples task-conditioned proposition acquisition with evidence-governed belief updates that retain unresolved hypotheses across task boundaries, allowing subsequent interactions to support, revise, or contradict them (original draft, Sec. 3; Appendices B–C).

Relative to Mem0, EBM explicitly retains unresolved environmental hypotheses across tasks for subsequent evidence-guided validation and revision. The proposition-list control and hypothesis-retention ablation support the value of this mechanism beyond generic memory consolidation.

Relative to BeliefMem, we recognize it as concurrent work sharing an interest in revisable, uncertainty-aware memory. BeliefMem maintains competing conclusions and updates their confidence through evidence merging (original draft, Sec. 2.2). EBM focuses on acquiring and revising environmental knowledge during an online stream of distinct but related tasks. In Database, this additionally includes task-conditioned active verification under a shared query budget. The reported evaluation protocols reflect this distinction: BeliefMem's ALFWorld evaluation constructs memory from training expert trajectories before test-time retrieval, whereas EBM continuously acquires and revises beliefs throughout the evaluation task stream.

W3. Prompt Sensitivity

We evaluated a paraphrased version of EBM's prompts, rewritten using GPT-6 Astra while preserving the original workflow, decision rules, and output constraints. The paraphrased prompts were evaluated over three independent Database runs with Qwen3.8-27B. For EBM with the original prompts, we directly reuse the results reported in the original paper:

MethodAvg. Reward ↑Accuracy ↑Avg. Queries ↓
EBM (original prompts)0.629073.00%2.090
Paraphrased prompts0.605670.83%2.150

The differences are modest (−0.0234 reward and −2.17 percentage points in accuracy), suggesting broadly comparable performance under the tested paraphrasing variation.

Q1. Role Assignment and Mixed-Model Configurations

In the original experiments, proposer, validator, and solver all use the same backbone model. We additionally evaluated mixed-role configurations on Database using Qwen3.5-9B and Qwen3.8-27B, with three independent runs per configuration.

Proposer / Validator / SolverAvg. Reward ↑Std. Dev.
9B / 9B / 9B0.13670.0667
9B / 27B / 9B0.23720.1524
27B / 27B / 9B0.36780.0963

With the solver fixed at 9B, replacing the validator with 27B increases mean reward from 0.1367 to 0.2372. Subsequently replacing the proposer with 27B further increases it to 0.3678. These preliminary results suggest that stronger belief acquisition and validation can improve downstream task performance without increasing solver capacity.

Q2. STALE Belief Handling

As described in the original draft (Appendix A.4.2), after database drift, existing beliefs are marked STALE and remain visible to the solver, which is instructed to treat them as potentially outdated.

STALE beliefs can return to SUPPORTED through two operations. Under REVISE/revalidate, SUPPORT → SUPPORTED, REFUTE → CONTRADICTED, and INCONCLUSIVE preserves STALE. Under REVISE/replace, a supported replacement becomes SUPPORTED; an inconclusive replacement becomes HYPOTHESIZED; a refuted replacement is rejected, preserving the original belief.

These transitions follow the standard validation process (original paper, Appendix C) and incur LLM inference costs. Newly executed SQL verification also consumes the shared Database query budget.

Thus, STALE preserves previously acquired knowledge while explicitly marking it for reassessment after environmental change.

Q3. Evidence Acquisition and Verification Budget

As described in the original paper (Appendix B), Database supports both retrieval of previously observed evidence and active SQL verification.

CONSTRUCTVERIFICATION generates a SQL query testing a proposed environmental proposition. Construction incurs LLM inference cost but no environment-query cost. EXECUTEANDOBSERVE executes the query and returns its observation. Each execution consumes one query from the shared budget of 15 SQL queries. We allow at most one active verification probe per task. Retrieving prior evidence does not consume additional SQL queries.

Every returned observation is passed to the validator as evidence, including empty results and SQL execution errors. An execution error does not trigger a separate evidence-acquisition failure path: the error feedback itself is the observation to be assessed. Failed SQL executions still consume the shared query budget. The validator determines whether the returned evidence provides SUPPORT, REFUTE, or INCONCLUSIVE grounds for the proposition.

Thus, active verification is not free exploration: it trades an immediate query cost against the potential future value of improved environmental knowledge.

Q4. Missing ACE and Mem0 Results on Opus4.8

Due to time and computational resource constraints, ACE and Mem0 were not included under Opus4.8 in the original submission. We have now completed both evaluations on Database and Poker. The results below report the mean ± standard deviation of cumulative reward under the stateful setting and cumulative gain, defined as the paired difference between the cumulative rewards of the stateful and memoryless settings, over three independent runs.

TaskMethodAvg. Reward ↑Avg. Gain ↑
Database ExplorationACE20.4443 ± 2.8607+2.7111 ± 2.8607
Database ExplorationMem021.2889 ± 2.5892+6.6222 ± 2.5892
PokerACE89.9000 ± 23.8162+2.0000 ± 23.8162
PokerMem098.9667 ± 14.4410+31.3667 ± 14.4410

Including ACE and Mem0 leaves EBM ranked first in mean cumulative reward among the compared non-oracle methods on both Opus4.8 environments: EBM achieves 28.61 on Database and 159.12 BB on Poker (submission draft, Table 1). We will include the additional baseline results in the revised manuscript.

Q5. Raw-History Window and Full-History Comparison

The 20-instance raw-history window was selected as a fixed experimental setting, not through hyperparameter optimization.

Importantly, the original paper (Appendix A.4.3, Fig. 7) already includes a full-history comparison within its 20-task no-drift evaluation. Because this experiment contains only the first 20 Database tasks, a history window of 20 includes all preceding interactions at every evaluation step. We use the 20-task no-drift setting for this comparison because, in the 40-task drift stream, shorter windows may gain an additional advantage by naturally dropping outdated pre-drift information. Comparing history windows across drift would therefore mix the benefit of access to prior interactions with the benefit of forgetting obsolete information. The no-drift setting isolates the former more directly.

Even with full history, adding learned beliefs improves average reward from 0.593 to 0.659 (+0.066).

Dear Reviewer,

Thank you for your thoughtful review. As the discussion period is approaching its end, we would appreciate any further feedback if you have time, particularly regarding whether our response has addressed your main concerns.

Thank you again for your time and consideration!

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

This paper proposes Evolving Belief Memory (EBM), a framework for continual learning agents. EBM stores beliefs about the environment, tracks their supporting evidence, and updates their status as new evidence arrives. It uses a proposer, a validator, and a solver to support learning across tasks. Experiments on Database and Poker with three backbone models show strong results on Database and competitive results on Poker. Replay experiments and ablations further support the value of persistent beliefs and evidence-based validation.

Critical strengths
  1. The paper presents a useful view of agent memory by tracking beliefs, evidence, and changes in belief status, rather than only storing past experiences or solutions.

  2. EBM achieves the highest mean reward on Database across three backbone models, showing consistent benefits in the tested setting.

  3. The replay experiments and ablations provide useful evidence that persistent beliefs can help future tasks and that validation improves performance.

Critical weaknesses
  1. The experiments do not clearly show whether explicit belief status tracking is better than storing structured knowledge without status labels.

  2. EBM uses substantially more tokens than several baselines. Without a compute-matched comparison, it is difficult to separate the benefits of the method from those of additional computation.

  3. Poker results have high variance, and the evaluation covers only two environments. This limits the strength of the broader claims.

Questions for authors
  1. Can you compare EBM with a version that stores the same beliefs and evidence but does not track belief status?

  2. How does EBM perform when compared with baselines under similar token budgets?

  3. Can you provide stronger statistical evidence for the performance differences, especially on Poker where the variance is high?

2 comments

We thank the reviewer for recognizing the value of EBM's evidence-tracked beliefs and persistent-memory replay experiments.

W1/Q1. Belief Status Tracking

Because status tracking governs belief updates during learning, removing it does not generally preserve the same beliefs and evidence; we therefore distinguish learning-time belief maintenance from solver-visible status labels.

In the label ablation, removing solver-visible status labels yields a higher observed mean replay score (0.6450 without labels vs. 0.6217 with labels). Thus, this experiment provides no evidence that explicitly displaying status labels improves solver performance.

In the belief-maintenance ablations, replacing EBM's evolving belief maintenance with conventional proposition consolidation reduces mean reward from 0.6290 to 0.4673, while removing hypothesis retention alone reduces it to 0.5170.

These results support the value of EBM's belief-maintenance process, including hypothesis retention, rather than a performance benefit from displaying status labels to the solver. We will revise the manuscript to clarify this distinction. See General Response, Sec. 1, for the experimental settings and scope.

W2/Q2. Inference Cost and Similar Token Budgets

With the same three-role architecture and raw-history window, optimized EBM achieves 0.5880 reward and 69.0% accuracy using 4.164M tokens, compared with 0.4673 and 55.5% using 3.902M tokens for proposition-list.

This represents 25.8% higher relative reward with only 6.7% more inference tokens. Further solver-history pruning reduces EBM's consumption to 2.694M tokens while maintaining strong performance.

See General Response, Sec. 2, for component-level costs and full baseline comparisons.

W3/Q3. Statistical Analysis of Poker Results

We compare EBM (optimized) with the baseline results reported in our draft, using five independent runs per method. The table reports unadjusted 95% Welch confidence intervals for cumulative reward differences, treating each complete run as the unit of analysis.

BaselineΔ Reward (BB) ↑95% Confidence Interval
ICL+118.50[−6.37, 243.38]
ReAct+136.70[51.90, 221.50]
ACE+120.56[25.69, 215.43]
DC+184.50[105.48, 263.53]
Mem0+140.92[61.90, 219.95]
Tycho (adapted)−94.00[−524.83, 336.84]

Δ Reward = EBM (optimized) − baseline. Intervals are not adjusted for multiple comparisons.

The 95% confidence intervals for reward differences are entirely above zero against ReAct, ACE, DC, and Mem0, while those for ICL and Tycho (adapted) include zero.

Dear Reviewer,

Thank you for your thoughtful review. As the discussion period is approaching its end, we would appreciate any further feedback if you have time, particularly regarding whether our response has addressed your main concerns.

Thank you again for your time and consideration!

Comments on the paper

2 comments

We thank the reviewers for recognizing EBM’s belief/evidence/status tracking (dWBF), explicit, revisable environmental beliefs as an important and underexplored aspect of continual learning (Txmh), and replay evidence of reusable knowledge (UzP4).

Our additional experiments address two central concerns: the contribution of evolving belief maintenance beyond conventional consolidation, and its benefits under comparable inference budgets.

1. Isolating the Contribution of Evolving Belief Memory

Our contribution is maintaining an evolving learning state across tasks, preserving unresolved environmental propositions for later support, revision, or contradiction. Statuses govern memory updates, beyond annotating consolidated notes for the solver (original paper, Sec. 3; Appendix C).

We conducted three targeted experiments on Database using Qwen3.8-27B.

(a) Proposition-list baseline. We retain the proposer–validator–solver architecture. Given the task, raw history, and accumulated propositions, the proposer generates evidence-backed proposals; the validator accepts, modifies, or discards them. Only validated proposition texts persist, without statuses or accumulated evidence; the solver receives them with the task and raw history. Removing the belief representation necessarily requires adapting the validator’s status-transition instructions to plain propositions. All other configurations match the original EBM. This control compares the representations and their corresponding update procedures within the same architecture.

(b) Removing hypothesis retention. We preserve EBM's proposal, validation, and belief-update mechanisms but discard HYPOTHESIZED propositions across task boundaries.

Both variants are evaluated over five independent runs under the same 40-task Database setting as EBM.

MethodAvg. Reward ↑Accuracy ↑Avg. Queries ↓
EBM0.6290 ± 0.077073.0% ± 8.2%2.090 ± 0.160
Proposition-list0.4673 ± 0.076355.5% ± 8.37%2.370 ± 0.082
No-Hypothesis-Retention0.5170 ± 0.081760.50% ± 9.08%2.230 ± 0.089

Proposition-list lowers reward by 0.1617 and accuracy by 17.5 pp. Removing hypothesis retention lowers them by 0.1120 and 12.5 pp, while increasing queries from 2.090 to 2.230.

We further check five EBM runs. Across them, 29 of 39 initially HYPOTHESIZED propositions (74.4%) were later resolved: 18 directly revalidated as SUPPORTED, 9 SUPPORTED after revision, and 2 CONTRADICTED; 10 remained unresolved.

An example: in Run 1, a hypothesis about items_g2.img_ct introduced at task 21 became SUPPORTED at task 25; the solver subsequently used the field to answer correctly with one SQL query. This illustrates cross-task reassessment and reuse, without establishing that the transition caused success.

These results support retaining unresolved knowledge for later validation, refinement, or rejection, and the combined value of evolving belief maintenance beyond the shared three-role architecture.

(c) Removing solver-visible status labels. Following the replay procedure described in Sec. 4.2 (RQ2), we use checkpoints from one original EBM run on 40 Database tasks, with three replays per configuration. We aim to evaluate whether the solver can benefit from receiving the belief status labels in addition to the propositional claims. Therefore, we compare the solver's performance by feeding it with and without belief status labels. In draft, we only provide SUPPORTED and HYPOTHESIZED propositions to the solver. For CONTRADICTED propositions, we also compare the solver's performance by keeping the original proposition contents or negating the contents. As in original EBM, evidence serves validation and revision; the solver receives proposition texts and labels, without underlying evidence.

Replay ConfigurationAvg. Reward ↑Accuracy ↑Avg. Queries ↓
With status labels0.6217 ± 0.029372.50% ± 4.33%2.192 ± 0.072
Without status labels0.6450 ± 0.004475.00% ± 0.00%2.192 ± 0.072
Without labels + negated CONTRADICTED propositions0.6472 ± 0.012075.83% ± 1.44%2.134 ± 0.191
With labels + original CONTRADICTED propositions0.6567 ± 0.010176.67% ± 1.44%2.083 ± 0.138

Removing explicit labels does not reduce mean reward (0.6217 vs. 0.6450), while mean queries remain identical. Including CONTRADICTED propositions yields comparable or slightly higher performance. Overall, we find no clear benefit from exposing explicit belief status labels to the solver during replay. However, since labels are removed only at the replay stage, these results do not rule out their potential role in the original proposer–solver interaction.

2. Inference Efficiency and Comparable Budgets

In the original submission, we focused on how agents can acquire, revise, and reuse environmental knowledge across tasks by maintaining a persistent, evidence-grounded belief state (original paper, Sec. 1). We gave less attention to inference efficiency: although we reported token usage, we had not systematically analyzed or optimized the implementation's inference costs.

To address this gap, we broke down the original implementation's token consumption across the proposer, validator, and solver. The proposer and solver accounted for most of the usage: 3.800M and 9.566M tokens on Poker, and 2.009M and 3.122M on Database, respectively. Inspecting their contexts revealed overhead from repeatedly including historical proposer plans: mutations, rationales, evidence references, and verification SQL, including rejected or superseded proposals. Based on this analysis, we implemented two optimized variants:

  • EBM (optimized): Removes historical proposer plans from proposer/solver contexts, retaining raw interaction history, beliefs, and associated evidence.
  • EBM (optimized + solver-history pruning): Additionally removes solver raw history on Database.

Both preserve belief memory and its original evidence-based updates.

Component-level token consumption (M):

EnvironmentMethodProposerValidatorSolverTotal
PokerEBM (original)3.8000.2809.56613.646
PokerEBM (optimized)1.4910.2762.2123.979
DatabaseEBM (original)2.0090.3413.1225.473
DatabaseProposition-list1.4090.1372.3563.902
DatabaseEBM (optimized)1.5440.3512.2684.164
DatabaseEBM (optimized + solver-history pruning)1.7830.3440.5672.694

Performance and Inference Costs

Database (cumulative reward over 40 tasks):

MethodReward ↑Acc. (%) ↑Tokens (M) ↓
ICL16.79 ± 1.7150.0 ± 4.74.206
ReAct20.83 ± 6.4361.0 ± 18.84.544
ACE13.69 ± 2.2759.5 ± 8.42.382
DC21.76 ± 1.3466.5 ± 2.91.323
Mem017.17 ± 2.2460.0 ± 6.44.004
Tycho (adapted)19.53 ± 0.5278.5 ± 2.25.149
Proposition-list18.69 ± 3.0555.5 ± 8.373.902
EBM (original)25.16 ± 3.0873.0 ± 8.185.473
EBM (optimized)23.52 ± 1.7569.0 ± 4.874.164
EBM (optimized + solver-history pruning)24.44 ± 1.8574.5 ± 4.812.694

Poker (cumulative reward in BB over 60 hands):

MethodReward (BB) ↑Tokens (M) ↓
ICL78.40 ± 98.413.276
ReAct60.20 ± 48.963.800
ACE76.34 ± 65.350.993
DC12.40 ± 25.631.150
Mem055.98 ± 22.322.784
Tycho (adapted)290.90 ± 349.857.702
EBM (original)141.06 ± 101.0813.646
EBM (optimized)196.90 ± 64.743.979

Note: Qwen3.8-27B, five independent runs; reward/accuracy are mean ± SD (accuracy SD in pp). Tokens are mean input + output usage.

Database. With the same architecture and raw-history window, optimized EBM uses 6.7% more tokens than proposition-list (4.164M vs. 3.902M) for 25.8% higher reward and +13.5 pp accuracy. Solver-history pruning uses 31.0% fewer tokens (2.694M) for 30.8% higher reward and +19.0 pp accuracy, also using fewer tokens than ICL, ReAct, Mem0, and Tycho.

Poker. Optimization cuts tokens by 70.8% (proposer: 60.8%; solver: 76.9%) while mean reward rises 39.6%. Token usage approaches ReAct (3.979M vs. 3.800M), with substantially higher observed mean reward.

EBM’s original overhead is not inherent to belief evolution: Database tokens fall 50.8%, with nearly unchanged reward (24.44 vs. 25.16) and slightly higher accuracy (74.5% vs. 73.0%); Poker tokens fall 70.8% with higher observed mean reward. Redundant or outdated proposer plans may potentially distract from maintained beliefs.

These initial optimizations substantially reduce EBM's token consumption while preserving strong task performance, highlighting considerable room to improve token efficiency without changing the underlying belief-update mechanism. Together with the advantage over proposition-list at comparable or lower token usage, these results indicate that EBM's performance gains are not solely driven by greater token consumption.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.