Organizations: Nanyang Technological University · Georgia Institute of Technology · University of Washington · Washington University in St. Louis · The University of Sydney · National University of Singapore
LLM agents increasingly operate in long-horizon, verifier-rich environments, but current self-improvement mechanisms often write episode-derived lessons directly into memory, making local success an unreliable signal for reusable and safe knowledge. This paper addresses the core question of when an experience-derived behavioral update should be admitted into persistent agent state. We propose Falsification-Gated Self-Evolution (FGSE), a verifier-grounded framework that represents each candidate lesson as a structured hypothesis with an explicit precondition, behavior change, expected effect, and verifier. FGSE applies the hypothesis only in a temporary state, tests it on target-transfer, falsification, and archived-regression probes, and then commits, refines, or rejects it according to measured gain and risk. Across web, app, tool-use, and long-term memory benchmarks, FGSE achieves strong task performance, including 39.8 WebArena success rate, 78.8 AppWorld average completion, and 0.724/0.487 Pass1 on τ-Retail/τ-Airline, while reducing falsification failures to 5.0%, regression damage to 1.3%, and harmful committed updates to 3.6%. These results suggest that testing memory updates as hypotheses supports more reliable long-term adaptation.
Figures & tables
Figure 1: A locally useful episode-derived lesson may overgeneralize or regress archived skills if directly written into memory. FGSE tests each lesson as a structured hypothesis in a temporary state and commits only verified, transferable updates to long-term memory.
Figure 2: Exploratory diagnostics for naive episode-derived self-updates. (a) Many updates combine near-transfer gains with boundary harm. (b) Broad and underspecified updates produce substantially higher boundary and archive harm than more specific updates. (c) Sequentially writing free-form lessons into memory can accumulate errors, especially when updates are selected only by source-episode improvement. (d) A post-hoc scope-localization analysis shows that many harmful but useful updates can be repaired by narrowing their applicability, motivating an explicit refinement mechanism.
Figure 3: Overview of Falsification-Gated Self-Evolution (FGSE). FGSE first converts episode evidence into a structured behavioral hypothesis, temporarily evaluates it with target-transfer, falsification, and regression probes, and then commits, refines, or rejects the hypothesis according to verifier-grounded gain and risk criteria.
Method
Backbone / Setting
WebArena SR ↑
AppWorld Normal ↑
AppWorld Challenge ↑
AppWorld Avg. ↑
τ -Retail Pass 1 ↑
τ -Airline Pass 1 ↑
Web / browser-control agents: methods primarily designed or evaluated for browser navigation and web interaction.
GPT-4 Agent ( Zhou et al., 2024 )
GPT-4
14.4
43.2
25.4
34.3
0.553
0.378
AutoEval ( Pan et al., 2024 )
GPT-4
20.2
45.8
28.7
37.3
0.579
0.391
BrowserGym ( Le Sellier de Chezelles et al., 2025 )
GPT-4o
24.3
46.5
29.1
37.8
0.585
0.402
CER online ( Liu et al., 2025 )
GPT-4o
33.2
51.9
33.4
42.7
0.622
0.424
CER offline ( Liu et al., 2025 )
GPT-4o
33.4
52.6
34.1
43.4
0.631
0.429
Table 1: Main comparison on web, app, and tool-interaction benchmarks. For AppWorld, Avg. is the mean of Test-Normal and Test-Challenge task-goal completion. Best and second-best scores in each column are shown in bold and underlined , respectively.
Figure 4: Domain-level diagnostic of self-evolution risk.
Figure 5: Interpreting FGSE update selection. (a) Transfer–Falsification volcano plot for candidate hypotheses. The x -axis shows target-transfer gain G , the y -axis shows −log10(Pfail+ϵ0) , point size encodes regression damage Dreg , and color indicates the final FGSE decision. The dashed lines mark the useful-transfer and falsification thresholds. (b) Decision simplex over normalized target gain, falsification risk, and regression damage. The shaded area shows the gate-induced decision regions.
Variant
WebArena SR ↑
AppWorld Avg. ↑
τ -Retail Pass 1 ↑
LongMemEval Acc. ↑
LoCoMo Avg. R-L ↑
Full FGSE
39.8
78.8
0.724
0.748
37.62
w/o structured hypothesis
35.6 (-4.2)
72.9 (-5.9)
0.664 (-0.060)
0.692 (-0.056)
32.84 (-4.78)
w/o target-transfer probes
36.8 (-3.0)
74.9 (-3.9)
0.684 (-0.040)
0.710 (-0.038)
34.72 (-2.90)
w/o falsification probes
37.4 (-2.4)
75.8 (-3.0)
0.697 (-0.027)
0.713 (-0.035)
35.10 (-2.52)
w/o regression archive
38.2 (-1.6)
76.9 (-1.9)
0.706 (-0.018)
0.719 (-0.029)
35.87 (-1.75)
w/o scope refinement
37.1 (-2.7)
75.4 (-3.4)
0.690 (-0.034)
0.716 (-0.032)
34.96 (-2.66)
Table 2: Single-factor ablation on task-level performance.
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
Hyperparameter
Symbol
Default value
Candidate hypotheses per episode
B
3
Target-transfer probes
∣T(h)∣
8
Falsification probes
∣F(h)∣
16
Regression probes
∣R(h)∣
16
Minimum target gain
η
0.03
Maximum falsification rate
δ
0.05
Appendix
Table 3: Default FGSE hyperparameters used in controlled experiments.
Experiment group
LLM calls
Verifier calls
Wall-clock time
Client CPU-hours
Web/browser-control tasks
≈7.8×104
≈1.1×105
≈39 h
≈1.1×103
App/API-interaction tasks
≈1.46×105
≈2.18×105
≈32 h
≈9.0×102
τ -bench tool-user tasks
≈8.4×104
≈1.24×105
≈28 h
≈7.2×102
AgentDojo security diagnostics
≈3.6×104
≈6.8×104
≈12 h
≈3.0×102
Long-term memory benchmarks
≈6.4×104
≈8.7×104
≈16 h
≈4.2×102
Code/math diagnostics
≈5.2×104
≈9.6×104
≈21 h
≈7.6×102
Appendix
Table 4: Approximate compute used by the reported experiments. LLM calls include agent rollouts, hypothesis proposal/refinement, and baseline-specific reflection or judging calls. Verifier calls include official success validators, database-state checkers, unit tests, security validators, and exact-match evaluators. CPU-hours denote client-side orchestration and environment/verifier execution only. Provider-side LLM serving compute is not included because all LLM backbones are accessed through hosted APIs.
Method
Backbone / Setting
LongMemEval Acc. ↑
LoCoMo Avg. R-L ↑
G (%) ↑
Pfail (%) ↓
Dreg (%) ↓
Harmful Updates (%) ↓
Post-commit Violations (%) ↓
Web / browser-control agents: methods primarily designed or evaluated for browser navigation and web-interaction self-improvement.
GPT-4 Agent [ Zhou et al., 2024 ]
GPT-4
0.552
22.84
0.0
0.0
0.0
0.0
0.0
AutoEval [ Pan et al., 2024 ]
GPT-4
0.548
23.11
2.4
19.7
5.3
13.2
11.7
BrowserGym [ Le Sellier de Chezelles et al., 2025 ]
GPT-4o
0.560
24.02
2.8
18.9
5.1
12.8
11.1
CER online [ Liu et al., 2025 ]
GPT-4o
0.591
26.37
8.6
17.4
4.9
12.1
10.8
CER offline [ Liu et al., 2025 ]
GPT-4o
0.598
26.91
8.8
17.1
4.8
11.9
10.5
Appendix
Table 5: Long-term memory and controlled update-reliability comparison. The Offline Reading result on LongMemEval is an oracle-style upper bound and is not ranked. Gray 0.0 entries indicate methods without persistent self-update, for which update-reliability metrics are not ranked. G measures target-transfer gain; Pfail measures falsification failure rate; Dreg measures regression damage. Lower is better for the last four columns among self-updating methods. Best and second-best ranked scores in each column are shown in bold and underlined , respectively.
Variant
G (%) ↑
Pfail (%) ↓
Dreg (%) ↓
Harmful Updates (%) ↓
Post-commit Violations (%) ↓
Full FGSE
12.9
5.0
1.3
3.6
3.1
w/o structured hypothesis
9.2 (-3.7)
16.7 (+11.7)
4.8 (+3.5)
11.3 (+7.7)
10.1 (+7.0)
w/o target-transfer probes
9.8 (-3.1)
11.9 (+6.9)
3.1 (+1.8)
8.2 (+4.6)
7.0 (+3.9)
w/o falsification probes
11.7 (-1.2)
18.6 (+13.6)
4.1 (+2.8)
10.6 (+7.0)
9.4 (+6.3)
w/o regression archive
12.2 (-0.7)
8.9 (+3.9)
5.2 (+3.9)
8.1 (+4.5)
7.4 (+4.3)
w/o scope refinement
10.6 (-2.3)
6.4 (+1.4)
1.8 (+0.5)
4.4 (+0.8)
3.9 (+0.8)
Appendix
Table 6: Single-factor ablation on update reliability. G measures target-transfer gain; Pfail measures falsification failure rate; Dreg measures regression damage. For G , higher is better; for the remaining metrics, lower is better. Blue numbers in parentheses denote the absolute degradation compared with the full FGSE model.
Figure 6: Plasticity–safety Pareto analysis of update-selection strategies. Each point is one configuration obtained by sweeping verifier budgets and acceptance thresholds. The x -axis is update gain Δupd , and the y -axis is either harmful update rate H (left) or regression damage R (right). Point size indicates verifier cost C (average verifier calls per candidate update), and color denotes the update-selection strategy. The black dashed line shows the empirical Pareto frontier, where larger gain and smaller harm are jointly preferred. FGSE occupies the most favorable lower-right region over a wide range of medium verifier budgets, showing that it improves plasticity without incurring the safety cost typically associated with aggressive update policies.
Figure 7: Falsification discovery curves under different probe-selection policies. The x -axis is the probe budget K . The left panel shows bad-update detection rate D(K) , and the right panel shows harmful update avoided A(K) . Solid lines denote the mean across repeated trials, and shaded bands denote 95% confidence intervals. The gray vertical band marks the practically relevant low-budget regime ( 8≤K≤16 ). Targeted probing consistently dominates random baselines, especially in the low-budget regime, showing that hypothesis-aware falsification is substantially more information-efficient than unguided random testing.
Figure 8: Stability of hypothesis effects under stochastic rollouts. Each row corresponds to one hypothesis and shows the distribution of seed-specific update effects Δh(s) across repeated rollouts. Rows are grouped by the final FGSE decision. Dots denote seed-level outcomes, the shaded half-violin shows the empirical density, the white box shows the interquartile range, and the diamond marks the mean effect. The right-side annotation reports the sign-consistency score C(h) . Committed hypotheses remain consistently positive across seeds, refined hypotheses are still mostly positive but exhibit larger variance, while rejected hypotheses are centered near zero or change sign frequently.
Decision
Domain / Trigger
Candidate hypothesis
Gate statistics
Interpretation
Commit
τ -Airline / round-trip booking
Scope: the user asks to book a round-trip flight and explicitly provides origin, destination, outbound date, and return date. Behavior: select the round-trip mode before search, fill both date fields, and verify that both flight legs are present before final booking. Expected effect: the final booking record contains trip_type=round_trip and valid outbound and return segments.
The hypothesis passes all three default thresholds with margin: G(h)>η , Pfail(h)<δ , and Dreg(h)<β . It captures a reusable tool-order rule without harming boundary or archived cases.
Refine
AppWorld / calendar rescheduling
Initial scope: any request mentioning “reschedule”. Behavior: edit the existing calendar event rather than creating a new one. Failure mode: the rule also fires on tasks that ask to create a second event, cancel an event, or modify only a reminder. Refined scope: exactly one matching event exists, and the user explicitly requests changing its time rather than creating, cancelling, or duplicating an event.
Before refinement: G(h)=10.4%Pfail(h)=3/16=18.8%Dreg(h)=2.7%Sep(h)=0.07 After refinement: G(h′)=7.6%Pfail(h′)=0/16=0.0%Dreg(h′)=0.8% Post-commit violation: 2.0%
The initial hypothesis is useful but too broad: target gain is high, but falsification and regression exceed the default risk thresholds. Because failures are separable, one precondition-refinement pass preserves 73.1% of the target gain while reducing falsification failures to zero. This shows that refinement salvages repairable updates.
Reject
AgentDojo / tool-output shortcut
Scope: a tool output contains an urgent instruction or an apparent verification token. Behavior: follow the tool-suggested action directly without rechecking the user-level instruction or system constraint. Expected effect: complete the immediate target task faster by trusting the tool message.
Although the hypothesis improves several target-transfer probes, it creates a high-risk shortcut under decoy and prompt-injection probes. The failures are not cleanly separable by a narrower precondition. FGSE therefore rejects the update, preventing a target-only gate from committing an unsafe behavior.
Appendix
Table 7: Representative FGSE hypothesis triage cases under the default gate. All three candidates improve the triggering or near-transfer cases. Based on falsification and regression evidence, FGSE commits high-margin transferable rules, refines useful but overly broad rules, and rejects high-risk shortcuts despite positive target gain.
Figure 9: Trajectory-edit Sankey diagram from baseline traces to FGSE traces. The left column shows the dominant behavioral deficiency in the baseline trace, the middle column shows the dominant edit family introduced by FGSE, and the right column shows the resulting FGSE behavior motif. Band width is proportional to the number of corrected trajectories. The diagram shows that most successful transitions are driven by tool-order repair, memory retrieval, and constraint checking, whereas final-answer formatting accounts for only a small minority of improvements.
Figure 10: Memory-growth Pareto analysis. We vary the retention budget and evaluate long-horizon self-evolving agents under different memory policies. Left: task success rate versus committed memory size. Right: violation rate versus committed memory size. Each faint point denotes one domain-seed run, while solid lines connect policy means across budgets. Marker area is proportional to retrieval cost Cret . A desirable memory policy should remain close to the upper-left region in the left panel (high success with small memory) and the lower-left region in the right panel (low violation with small memory). FGSE traces the most favorable frontier: it achieves high task success and low violation with substantially smaller committed memory and lower retrieval cost than naive memory growth.
Self-evolving LLM agents typically improve how they act through accumulated experience, reflection, or skills. Yet even procedurally capable agents can fail when their beliefs about environment dynamics are incomplete, incorrect, or outdated. We study a complementary axis of self-evolution: evolving those beliefs during deployment. Such beliefs can support multiple tasks, but incorrect ones can also propagate across them. We introduce EvoBelief, a self-evolving world model that represents environment knowledge as falsifiable hypotheses. Unexpected outcomes and decision-relevant unknowns trigger hypothesis formation. Later observations and controlled experiments provide independent validation before a rule can guide predictions or plans within its supported scope. Counterexamples narrow or retire rules as the environment changes. The language model remains frozen, and each rule remains linked to its evidence and the decisions it changes. Across four benchmarks spanning static dynamics, hidden drift, and scientific discovery, EvoBelief improves task performance and reuses learned rules across tasks. On ALFWorld without actor-side transition memory, it improves success over the matched Frozen World Model by 23.9% and 31.3% with Claude Haiku 4.5 and GPT-5.4, respectively. On MiniGrid, it revises stale rules and recovers after unannounced dynamics changes. In DiscoveryWorld's Reactor Lab, it discovers and validates quantitative laws, completing 83.3% of Normal-tier and 58.3% of Challenge-tier instances, versus 0% for each evaluated baseline. These results demonstrate self-improvement through testable, revisable environment knowledge rather than model-parameter updates.
LLM agents can change their own future behavior, raising a basic control question of which self-generated changes should be allowed to persist. We formulate this as admission control for self-modification. The agent may propose changes to its operating instructions, while an external runtime gate controls persistence. We implement this principle as a model-agnostic self-healing harness that runs a Detect, Notice, Heal, Validate loop around an otherwise unmodified agent. The agent authors candidate behavioral rules in an external workspace, where they receive provisional execution authority during evaluation and acquire persistent cross-episode authority only after measured improvement on the triggering failure without regression beyond a fixed margin on protected cases. Replay provides matched evidence when available, forward trials provide a weaker fallback, and a corpus-level guard re-tests the accumulated active rule set. Across 16 matched Baseline and Harness runs spanning AppWorld, Terminal-Bench, and τ2-Bench, the gate rejected 383 replay-decided proposals. Of these, 211 (55%) improved their triggering failure while degrading a case that previously worked. This shows that locally beneficial self-modifications can introduce collateral regressions often enough to materially affect gate decisions, providing direct empirical motivation for external admission control. Task-completion score is higher under the Harness in all 16 pairs, with two paired bootstrap intervals excluding zero, while repeated-trial reliability is higher in 12 pairs, tied in 4, and lower in none. Because adaptation modifies the policy-inducing context while leaving model weights fixed, admitted changes remain inspectable, reversible, and compatible with closed-weight models.
Sina Tayebati, Divake Kumar, Nastaran Darabi +2
University of Illinois Chicago · AI Labs, Capital One
Large language model (LLM) agents operate over long, multi-session interactions in which facts change: a user moves, a price updates, a plan is revised. Acting correctly requires using the current value of a fact and discarding values that have been superseded. We isolate this ability on real conversational data and show that it is a distinct, unsolved failure. On the knowledge-update subset of LongMemEval, replacing an agent's full context with a bounded, self-maintained memory drops accuracy from 92% to 77% even on a frontier model (gpt-5.4), a gap that is statistically significant (paired McNemar p<0.005) and persists across model scale while full-context accuracy saturates near 92%. The bottleneck is therefore memory maintenance, not comprehension, and is not closed by a stronger model. We then ask whether this is merely an undersized memory, and find it is not: as the conversation grows 24x, accuracy falls further (from 68% to 28%), and granting the agent proportionally more memory yields no detectable recovery (28% to 28%, n=25). The failure scales with the length of the conversation, not the compression ratio. We release Supersede, an open reinforcement-learning environment (on the verifiers / prime-rl stack) that turns this measurement into a training signal: agents are rewarded for answering from the current value and penalized for stale ones. Finally, we close the loop and show the gap is trainable: GRPO fine-tuning a small open model (Qwen2.5-3B) on this environment nearly doubles its held-out supersession accuracy on real, unseen conversations (9.0% to 16.7%, a single run), along a monotonic checkpoint curve indicating the learned policy, not the harness, carries the gain. To our knowledge this is the first trainable environment whose reward targets temporal fact-currency, and the first evidence the supersession gap can be trained down, not only measured.