MemDTree: Fact-Anchored Memory--Decision Trees for Long-Horizon Agents

Long-horizon agents must preserve persistent facts and unfinished objectives without replaying an ever-growing interaction history. We introduce MemDTree, a training-free memory--decision controller that organizes extracted information by update behavior: reusable knowledge accumulates, whereas mutable state is updated by key. Each new goal branch cites live memory under a protected task objective, while raw trajectory spans remain available for explicit recall. We compare MemDTree with Long Context and No Memory on three AgentOdyssey games using matched seeds and the same language-model endpoint. MemDTree matches or exceeds Long Context's mean main-quest progress on all three games (overall mean $14.56$ vs. $11.33$ stages) at roughly $1/4$ of Long Context's total token cost. Its typed store retains nearly all of Long Context's world-knowledge QA performance and most of its episodic QA performance; No Memory is substantially cheaper but makes little main-quest progress. On a preliminary single-run-per-method two-day StuLife prefix under our adapter, MemDTree achieves 79.4\% exact-state task accuracy versus 71.4\% for Long Context while consuming roughly $1/8$ as many tokens. The comparison evaluates MemDTree as an integrated memory--goal--plan controller, not individual components. Trajectory analyses show that retaining relevant evidence does not ensure its timely use. Together, these findings suggest that coupling fact-anchored memory to an explicit decision structure can match or exceed the task performance of full-history replay while using substantially fewer tokens.