Content
# TreeSE RAG
**Tree Selective Expansion** — a retrieval algorithm for LLMs that organizes a user's knowledge base into a hierarchical summary tree and, at query time, produces a coherent context by selecting a **cut** through that tree: deciding at each visited node whether its summary is capable enough to use directly, or whether the system must descend into the subtree for more detail.
The goal is an **overall view of the user while not disregarding details**: a prompt about a niche corner of the knowledge base resolves to the specific facts it needs — nothing is silently dropped, and nothing generic is padded in.
## How it works
- **Index time:** leaf facts (atomic assertions) are embedded and clustered bottom-up (exact kNN + Leiden) into a hierarchy of summaries. Every internal node carries its **fidelity** — an embedding-vector measure of how far its summary drifts from its subtree leaves — plus a scalar **loss**. A parent summary's token size is constrained to be no larger than its children's total, making the hierarchy budget-monotone.
- **Query time:** the prompt is embedded once and the tree is walked greedily. A node's **capability score** (`dot(prompt, fidelity) + β·loss/baseline`) decides whether its summary suffices or whether all children must be expanded. The result is a **tree cut** — an antichain where every root-to-leaf path has exactly one selected node — assembled within a per-call token budget. Query path: P50 ≤ 100ms, hard cap 1000ms; the target LLM is never called at query time.
- **Maintenance time:** an AI maintainer re-summarizes and re-clusters driven by metric gates (depth anomalies, arity breaches, sibling-loss anomalies, re-summary floors), while a periodic walk keeps the calibration baselines fresh. New facts are inserted deterministically and conflict-blind; conflicts are reconciled during maintenance.
## Quickstart
### Dependencies
- CMake ≥ 3.20, a C++20 compiler
- [ONNX Runtime](https://onnxruntime.ai) (CPU build is fine), SQLite 3, libcurl, nlohmann-json — on Arch: `pacman -S onnxruntime-cpu sqlite curl nlohmann-json`
### Build and test
```sh
# fetch the embedding model asset (~90MB, not committed)
./scripts/fetch_all_minilm_l6_v2.sh
cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build
ctest --test-dir build # 17 targets; the ONNX and benchmark smokes skip (exit 77) if the model is absent
./build/apps/playground/tree-rag-playground
```
### Benchmark quickstart
```sh
# fetch the benchmark corpus (Leipzig eng_news_2025_100K, ~11.4 MB — not committed)
./scripts/fetch_benchmark_corpus.sh
# benchmarks are timing measurements — build Release; Debug builds distort timings
cmake -S . -B build-release -DCMAKE_BUILD_TYPE=Release
cmake --build build-release
# the default run: full ladder 100 → 50,000 sentences, results into bench-out/
./build-release/apps/benchmark/tree-rag-benchmark
```
The run prints a per-rung table plus the HNSW-mandatory decision line and writes `bench-out/results.csv` (one row per rung) next to one `tree_<n>.db` per size. Debug builds distort timings (sanitizers, no optimization) — measure on Release only. See [docs/benchmarks.md](docs/benchmarks.md) for the full reference.
### MCP server quickstart
```sh
# Serve the five MCP tools over JSON-RPC 2.0 / stdio.
# build (like trigger_maintain) requires the Target LLM — pass --llm-base-url:
printf '%s\n' \
'{"jsonrpc":"2.0","id":1,"method":"initialize","params":{"protocolVersion":"2025-06-18","capabilities":{}}}' \
'{"jsonrpc":"2.0","id":2,"method":"tools/list"}' \
'{"jsonrpc":"2.0","id":3,"method":"tools/call","params":{"name":"build","arguments":{"assertions":["the user works on TreeSE RAG","the user writes C++20"]}}}' \
'{"jsonrpc":"2.0","id":4,"method":"tools/call","params":{"name":"stats"}}' \
'{"jsonrpc":"2.0","id":5,"method":"tools/call","params":{"name":"retrieve","arguments":{"prompt":"what does the user work on?","budget":512}}}' \
'{"jsonrpc":"2.0","id":6,"method":"tools/call","params":{"name":"insert","arguments":{"assertion":"the user reads Hacker News"}}}' \
| ./build/apps/mcp-server/tree-rag-mcp-server --db kb.db --llm-base-url http://localhost:8080/v1
```
Note: `kb.db` need not hold a pre-existing tree — a fresh database is populated via the `build` tool (which requires at least 2 assertions; a single-assertion `build` is refused, since such a tree could never grow) or via the first `insert`, which creates an internal root — further `insert` calls succeed. Until it holds a tree, `retrieve` returns an empty context.
`--llm-base-url` must point at a live OpenAI-compatible chat-completions endpoint (e.g. llama-server, Ollama, vLLM, or a tiny local stub) — otherwise `build` (and `trigger_maintain`) return an `isError` tool result.
### Server config file (optional)
Startup calibration comes from a JSON config file, the CLI, or built-in defaults — in that order of precedence (CLI wins):
```json
{
"calibration": { "beta": 1.0, "tau": 0.5, "alpha_1": 1.0 },
"default_budget": 4096
}
```
- Every key is optional; the schema is **strict** — an unknown key anywhere (top level or inside `calibration`) fails the boot, naming the key. A typo must not silently degrade every request.
- `--config <path>` selects the file; without it the server falls back to the `TREE_RAG_CONFIG` env var. An **empty** env value counts as "not given"; `--config ""` is a usage error.
- `beta`/`tau`/`alpha_1` must be finite numbers and `alpha_1 >= 0`; `default_budget` is an integer >= 1. `alpha_1` sets the summarizer's ε floor: ε = α₁ · fidelity_baseline.
- The dynamic baselines (`loss_baseline`, `fidelity_baseline`) are **not** config — they live in the store's calibration table, refreshed by the maintenance walk.
- `--beta` / `--tau` / `--default-budget` override the file; the file overrides the built-in defaults.
## Repository layout
```
apps/playground/ demo executable
apps/mcp-server/ stdio MCP server: wires the v0 tools (retrieve, trigger_maintain, insert, build, stats) to the concrete stack
apps/benchmark/ benchmark harness: corpus reader + scaling ladder + latency proof (stub LLM by default, optional --llm-base-url)
apps/inspect/ read-only DB inspector: dumps tree shape, per-node properties, calibration baselines, health diagnostics (never writes)
libs/core/ dependency-free core: domain types, interfaces, capability, tree cut, query surface
libs/embed/ all-MiniLM-L6-v2 embedder (ONNX Runtime, hand-rolled WordPiece tokenizer)
libs/store/ SQLite TreeStore (schema, serialization, calibration table)
libs/maintain/ offline: insert_leaf, summarizer, RC4 state machine, maintenance passes, Leiden, build_tree
libs/mcp/ protocol-pure MCP layer: JSON-RPC 2.0 over stdio, tools injected as handlers
docs/adr/ decision records 0001–0014
docs/algorithm.md the algorithm top to bottom, with every debated decision
architecture.md module topology, contracts, data flow
CONTEXT.md glossary (canonical terminology)
scripts/ asset fetch script
tests/ zero-dependency test harnesses per target
```
## Documentation
- **CONTEXT.md** — canonical glossary (Tree Cut, Capable, Fidelity, Loss, Context Budget, Offset-Aware Summarization, …).
- **docs/algorithm.md** — the full algorithm, top to bottom, including every decision where there was room for debate.
- **architecture.md** — module topology, contracts, data flow, latency budget.
- **docs/benchmarks.md** — the E15/E14 benchmark harness: corpus, CLI reference, ladder semantics, outputs, memory.
- **docs/adr/0001–0014** — the decision records (fidelity formulation, capability approach, leaf granularity, maintenance model, calibration, module structure, embedder stack, node model, persistence, client contract, summarizer delivery, Leiden contract, build orchestration).
- [Future work](docs/future-work.md) — roadmap of everything remaining (calibration, HNSW scale-up, v1 capability-predictor slots)
## Status
v0 core complete: build, insert, maintain, retrieve, persistence, embedder, tests, and the stdio MCP server (v0 tools `retrieve`, `trigger_maintain`, `insert`, `build`, `stats`). Three calibration placeholders (τ, β, α₁) await an empirical tuning pass on a real knowledge base. The HNSW scale-up (documented contract) remains the planned next step.
