How sakanaai/treequest works
Project Type and Purpose
• Type: Open-source Python library for answer‐tree search algorithms (AB-MCTS-A, AB-MCTS-M, Standard MCTS, BFS, Multi-Armed Bandit UCB, Tree-of-Thought BFS).
• Purpose: Provide a flexible, extensible framework to build and run adaptive branching tree searches, with pluggable node‐generation functions (often LLM API calls) and customizable scoring.
File Structure
• Top-level modules:
– src/treequest/algos: Each subfolder (ab_mcts_a, ab_mcts_m, best_first_search, multi_armed_bandit_ucb, standard_mcts, tree_of_thought_bfs) implements one algorithm, all inheriting from base.py.
– src/treequest/ranker.py: Ranks and selects top‐k nodes.
– src/treequest/visualization.py: Exports search trees for plotting.
– src/treequest/types.py & imports.py: Core type definitions (State, Node, Tree) and exports.
• Utility/config: pyproject.toml, pytest.ini, GitHub Actions workflows for CI and releases.
• Tests: One test file per algorithm + integration tests for interface & visualization.
README for Additional Insights
• Core API methods: init_tree(), step(tree, action_fns), top_k(tree, algo, k).
• Extension points: action_fns dict mapping labels to generator functions (e.g., LLM calls).
• Optional dependencies: PyMC for AB-MCTS-M, third-party LLM libraries (litellm, vllm) used externally via generate_fns.
• Checkpoint & resume functionality (implied).
Main Components and Their Relationships
a. Components:
1. Client Code / User Script
2. TreeQuest API Layer
3. Algorithm Modules (Strategy Pattern):
– ABMCTSA
– ABMCTSM
– StandardMCTS
– BestFirstSearch
– MultiArmedBanditUCB
– TreeOfThoughtBFS
4. Core Data Structures:
– Search Tree (nodes, edges)
– Node States & Scores
5. Node Generator (User-provided action_fns):
– LLM API Calls or Custom Functions
6. Scoring / Ranking Engine (ranker.py)
7. Visualization Export (visualization.py)
8. External Services / Dependencies:
– Language Model APIs (openai, litellm, vllm, etc.)
– PyMC (for mixed modeling in AB-MCTS-M)
b. Relationships & Data Flow:
1. Client calls TreeQuest.API.init_tree() → obtains empty Search Tree.
2. For each iteration:
• Client passes action_fns to TreeQuest.API.step(tree, action_fns).
• Algorithm Module selects node(s) to expand (selection).
• Node Generator functions are invoked (calls out to LLM or user logic).
• New nodes returned with (state, score).
• Algorithm backpropagates scores, updates tree.
3. Client invokes TreeQuest.API.top_k(...) to retrieve best node(s).
4. Visualization can be triggered to export the tree for plotting.
c. Architectural Patterns & Design Principles:
• Strategy Pattern for interchangeable algorithms (AB-MCTS, Standard MCTS, etc.).
• Plugin/Factory Pattern for user-defined generators (action_fns dict).
• Separation of concerns: Algorithms vs. Data structures vs. Visualization vs. Ranking.
• Dependency injection: External services (LLMs, PyMC) are injected via function arguments or extra dependencies.
• Typing & Static Analysis: py.typed, imports.py centralizes exports.
d. Key Technologies:
• Python 3.11
• PyMC (probabilistic modeling)
• pytest & pytest.ini for testing
• GitHub Actions (.github/workflows/*.yml) for CI/CD
• uv / pip packaging (pyproject.toml)
• Optional LLM libraries upstream of action_fns