# sakanaai/treequest architecture

> Architecture diagram of the GitHub repository sakanaai/treequest, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2025-07-11). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/sakanaai/treequest
- Repository: https://github.com/sakanaai/treequest

## Overview

##### 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

## Diagram (Mermaid)

```mermaid
flowchart TD
    %% Client Layer
    Client["Client Code"]:::external

    %% API Layer
    subgraph "TreeQuest API Layer"
        Init["__init__.py"]:::core
        Imports["imports.py"]:::core
    end

    %% Core Data Structures
    subgraph "Core Data Structures"
        Types["types.py"]:::core
        TreeDS["Search Tree"]:::core
    end

    %% Algorithm Interface
    Interface["Algorithm Interface\n(base.py)"]:::algo

    %% Algorithm Modules
    subgraph "Algorithm Modules"
        ABMCTSA["AB-MCTS-A\n(algo.py)"]:::algo
        ABMCTSA_PS["Probabilistic State\n(prob_state.py)"]:::algo
        ABMCTSM["AB-MCTS-M\n(algo.py)"]:::algo
        ABMCTSM_PMC["PyMC Interface\n(pymc_interface.py)"]:::external
        ABMCTSM_IMP["_ab_mcts_m_imports.py"]:::algo
        StandardMCTS["Standard MCTS\n(standard_mcts.py)"]:::algo
        BestFS["Best-First Search\n(best_first_search.py)"]:::algo
        MABUCB["Multi-Armed Bandit UCB\n(multi_armed_bandit_ucb.py)"]:::algo
        TOTBFS["Tree-of-Thought BFS\n(tree_of_thought_bfs.py)"]:::algo
    end

    %% Utilities
    subgraph "Utilities"
        Ranker["ranker.py"]:::util
        Visualization["visualization.py"]:::util
    end

    %% External Services
    subgraph "External Services"
        LLM["LLM APIs\n(openai, litellm, vllm)"]:::external
        PyMC["PyMC"]:::external
    end

    %% Flows
    Client -->|"init_tree()"| Init
    Init --> Imports
    Imports --> Types
    Imports --> TreeDS
    Client -->|"step(tree, action_fns)"| Imports
    Imports --> Interface
    Interface --> ABMCTSA
    Interface --> ABMCTSM
    Interface --> StandardMCTS
    Interface --> BestFS
    Interface --> MABUCB
    Interface --> TOTBFS
    ABMCTSA --> ABMCTSA_PS
    ABMCTSM --> ABMCTSM_IMP
    ABMCTSM --> ABMCTSM_PMC
    ABMCTSM_PMC --> PyMC
    %% Node generation flow
    ABMCTSA -->|"invoke action_fns"| LLM
    ABMCTSM -->|"invoke action_fns"| LLM
    StandardMCTS -->|"invoke action_fns"| LLM
    BestFS -->|"invoke action_fns"| LLM
    MABUCB -->|"invoke action_fns"| LLM
    TOTBFS -->|"invoke action_fns"| LLM
    LLM --> ABMCTSA
    LLM --> ABMCTSM
    LLM --> StandardMCTS
    LLM --> BestFS
    LLM --> MABUCB
    LLM --> TOTBFS

    %% Tree update and ranking
    ABMCTSA -->|"update tree"| TreeDS
    ABMCTSM -->|"update tree"| TreeDS
    StandardMCTS -->|"update tree"| TreeDS
    BestFS -->|"update tree"| TreeDS
    MABUCB -->|"update tree"| TreeDS
    TOTBFS -->|"update tree"| TreeDS
    Client -->|"top_k(tree, algo, k)"| Ranker
    Ranker --> TreeDS
    Ranker --> Client

    %% Visualization
    Client -->|"export()"| Visualization
    Visualization --> TreeDS

    %% Click Events
    click Interface "https://github.com/sakanaai/treequest/blob/main/src/treequest/algos/base.py"
    click ABMCTSA "https://github.com/sakanaai/treequest/blob/main/src/treequest/algos/ab_mcts_a/algo.py"
    click ABMCTSA_PS "https://github.com/sakanaai/treequest/blob/main/src/treequest/algos/ab_mcts_a/prob_state.py"
    click ABMCTSM "https://github.com/sakanaai/treequest/blob/main/src/treequest/algos/ab_mcts_m/algo.py"
    click ABMCTSM_PMC "https://github.com/sakanaai/treequest/blob/main/src/treequest/algos/ab_mcts_m/pymc_interface.py"
    click ABMCTSM_IMP "https://github.com/sakanaai/treequest/blob/main/src/treequest/algos/ab_mcts_m/_ab_mcts_m_imports.py"
    click StandardMCTS "https://github.com/sakanaai/treequest/blob/main/src/treequest/algos/standard_mcts.py"
    click BestFS "https://github.com/sakanaai/treequest/blob/main/src/treequest/algos/best_first_search.py"
    click MABUCB "https://github.com/sakanaai/treequest/blob/main/src/treequest/algos/multi_armed_bandit_ucb.py"
    click TOTBFS "https://github.com/sakanaai/treequest/blob/main/src/treequest/algos/tree_of_thought_bfs.py"
    click TreeDS "https://github.com/sakanaai/treequest/blob/main/src/treequest/algos/tree.py"
    click Types "https://github.com/sakanaai/treequest/blob/main/src/treequest/types.py"
    click Imports "https://github.com/sakanaai/treequest/blob/main/src/treequest/imports.py"
    click Init "https://github.com/sakanaai/treequest/blob/main/src/treequest/__init__.py"
    click Ranker "https://github.com/sakanaai/treequest/blob/main/src/treequest/ranker.py"
    click Visualization "https://github.com/sakanaai/treequest/blob/main/src/treequest/visualization.py"
    click Types "https://github.com/sakanaai/treequest/blob/main/src/treequest/py.typed"

    %% Styles
    classDef core fill:#cce5ff,stroke:#004085,color:#004085;
    classDef algo fill:#d4edda,stroke:#155724,color:#155724;
    classDef util fill:#e2e3e5,stroke:#383d41,color:#383d41;
    classDef external fill:#fff3cd,stroke:#856404,color:#856404;
```
