Tree-of-Experience: Hierarchical Experience Management for Self-Evolving Agents

Tree-of-Experience (ToE) is a structured experience-management framework proposed to address the limitations of existing methods for continual self-evolution in LLM agents. The paper identifies four essential properties of an effective experience-abstraction mechanism: Attributability, Transferability, Evolvability, and Efficiency. Existing methods, categorized as intra-trajectory transformation (e.g., Reflexion, MemRL, ReMe) and inter-trajectory induction (e.g., FLEX, SkillGen, SkillRL), often fall short on these dimensions, particularly in low-repetition tasks with outcome-level feedback.

ToE organizes experience into a shared tree of analytical perspectives and reasoning paths, aligning experience organization with the hierarchical reasoning process of LLM agents. The experience pool E is denoted as a set of tuples, each containing a depth-L analytical path, a feedback-derived reliability state, and maintenance metadata. The root of the tree represents the problem category or task objective, while non-root nodes represent critical reasoning perspectives, with parent nodes capturing general analytical dimensions and child nodes refining them.

The framework addresses three key questions: reasoning granularity, reasoning-path selection and expansion, and experience-tree evolution. For granularity, the hierarchy's semantics are jointly determined by problem structure, task objective, and required information, with rules for node construction including clear semantic subsumption, discriminative value, and balanced granularity. For path selection, ToE retrieves candidate nodes by reranking child nodes using a prompt-based LLM reranker, and if no suitable candidate exists, a proposer generates new analytical perspectives. For evolution, ToE uses environmental feedback to update experience reliability through either a formula-based update or an LLM-based update, and includes maintenance mechanisms for merging semantically similar nodes.

The experimental results demonstrate ToE's effectiveness on two benchmarks. On Game of 24, ToE achieves 85.3% accuracy, outperforming the experience-free ToT baseline by 20.4 percentage points while reducing LLM calls by 78.7% (from 51.7 to 11.0 calls per puzzle). On FinEvolveBench, a low-repetition benchmark with delayed, implicit, outcome-level feedback, ToE improves tsIC by an average of 41.24% across 12 evaluation settings, with a 59.57% improvement during the Exploitation phase and 22.92% over the Overall period. The improvements are consistent across backbone models, with increases of 48.61% under DeepSeek-V4-Flash and 33.88% under Qwen3-35B-A3B.

The paper also reveals a critical limitation of conventional experience-management methods: their inability to accurately attribute outcome feedback can reinforce unreliable experience and degrade performance relative to experience-free baselines. On FinEvolveBench, Mem0 and MemRL perform substantially worse than the experience-free baseline. An ablation study on reliability update mechanisms shows that the formula-based strategy outperforms direct LLM-based updating on both tsIC and csIC.

Improvements to AI Systems:

1. Hierarchical Experience Memory with Reliability-Weighted Retrieval

• Implement a tree-structured memory where each node stores an analytical perspective (e.g., check divisibility rules for math tasks) and a reliability score updated from outcome feedback.

• During inference, the system retrieves the most reliable child node per level via a lightweight reranker, avoiding exhaustive search.

• Resulting capability: The AI can solve novel, low-repetition tasks (e.g., financial reasoning, puzzle-solving) by reusing abstract reasoning patterns without needing identical past examples, while ignoring unreliable or misleading memories.

2. Attributable Feedback Attribution for Delayed/Outcome-Only Rewards

• Replace monolithic reward assignment with a two-stage update: first, use a formula-based credit assignment (e.g., exponential decay along the reasoning path) to update each node’s reliability; second, only merge or prune nodes when their reliability diverges significantly.

• Avoid LLM-based direct updates when feedback is sparse or noisy, as they amplify attribution errors.

• Resulting capability: The AI can learn from tasks where feedback arrives only at the end (e.g., investment decisions, multi-step planning) without reinforcing wrong intermediate steps, preventing performance collapse seen in baselines like MemRL.

3. Dynamic Reasoning-Path Expansion via Prompt-Based Proposer-Reranker Loop

• When no existing node matches the current problem state, the system generates new analytical perspectives (proposer) and ranks them against existing siblings using an LLM reranker that scores semantic relevance and discriminative power.

• New nodes are added only if they pass a threshold, ensuring balanced granularity and avoiding over-fragmentation.

• Resulting capability: The AI can autonomously discover and memorize new reasoning strategies for unseen problem types, adapting its experience tree over time—enabling continuous self-evolution without manual skill engineering.

4. Efficiency-Aware Experience Maintenance

• Use metadata (e.g., access frequency, last-update timestamp) to periodically merge semantically similar nodes and prune low-reliability, rarely-used branches.

• This reduces memory footprint and retrieval latency while preserving high-value abstractions.

• Resulting capability: The AI can operate under strict computational budgets (e.g., 11 LLM calls per puzzle vs. 51.7 for baseline) while maintaining or improving accuracy, making it deployable in real-time or cost-sensitive applications.

5. Task-Structure-Aware Node Granularity Control

• Automatically adjust tree depth (L) and node semantics based on problem type (e.g., shallow trees for simple arithmetic, deeper trees for multi-step financial analysis) using rules derived from task objective and information requirements.

• Resulting capability: The AI can generalize across domains with varying complexity, avoiding both over-general (too shallow) and over-specific (too deep) memories, leading to robust performance on both high-repetition (Game of 24) and low-repetition (FinEvolveBench) benchmarks.