Selective Expansion Tree (SETree)

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 tree cover through that tree: greedily expanding, from a global best-first heap, the child whose parent is least capable in the direction the prompt cares about, until the context budget is reached.

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 over their leaf-centroids (exact kNN + Leiden), with all summaries generated in a single deferred pass, 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 from a single global best-first heap. Each step pops the child with the highest per-child capability score (the direction in which its parent is least capable) and selects it. The result is a tree cover — every leaf covered at least once, with carried nodes (all their children selected) hidden from output — 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: maintenance is event-driven and strictly per-mutation. The cadence is TS-owned: after each accepted mutation the orchestrator coalesces a 500 ms burst, then a Bun Worker issues one atomic maintenance_run engine op (the sole writer to the tree). Each pass runs a two-phase incremental rebuild — a level-0 clean skip by exact member-id comparison against the persisted oracle; otherwise a per-level dirty loop (a level is dirty iff its member set changed or any member's clustering centroid differs component-wise by exact !=), G1-patching the kNN graph at every dirty level, rerunning natural_subcluster per affected community with parent preservation (an unchanged community keeps its old parent node — zero LLM work), and stopping early at the first clean level; an empty or unusable oracle delegates to the full cluster_hierarchy rebuild. The fidelity DP runs inside the rebuild and subtree_depth is set at parent creation. The oracle is persisted atomically as PerLevelHierarchyState (per-level member_ids/member_centroids/parent_ids/leiden_assignment + kNN adjacency) alongside the tree via save_tree_with_hierarchy — then a whole-tree faithfulness re-summarization (faithfulness < threshold or unknown, default 60). Baselines (loss_baseline/fidelity_baseline/refresh_baselines/save_calibration_baselines) are retired by ADR-0023; capability is β·per_level_loss raw (see ADR-0023).

Quickstart

Dependencies

• CMake ≥ 3.20, a C++20 compiler
• ONNX Runtime (CPU build is fine), SQLite 3, libcurl, nlohmann-json — on Arch: pacman -S onnxruntime-cpu sqlite curl nlohmann-json

Build and test

# 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          # 19 targets; the ONNX-dependent and benchmark smokes skip (exit 77) if the model is absent
./build/apps/playground/setr-playground

Benchmark quickstart

# 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/setr-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 for the full reference.

MCP server quickstart

The MCP server is the merged app's default role (bun apps/server/src/index.ts --db <path>; the positional mcp is the explicit spelling): the stdio JSON-RPC surface is pure TypeScript (src/mcp/), and the compute engine is the C++ shared lib embedded in-process via bun:ffi — build it first:

cmake --build build-release --target setr_engine   # -> build-release/apps/server/native/libsetr-engine.so

The engine lib resolves from the repo build trees (build-release/ first, then build/); SETR_ENGINE_LIB overrides the path. Debug-tree libs are ASan-instrumented and NOT supported under bun — even with the sanitizer runtimes preloaded they crash at the C++ exception boundary (ADR-0026 §8), so use the Release lib:

export SETR_ENGINE_LIB="$PWD/build-release/apps/server/native/libsetr-engine.so"

# Serve the seven v0 MCP tools over JSON-RPC 2.0 / stdio (retrieve, trigger_maintain,
# insert, build, stats, plus the dev-facing admin tools reset and setr_switch).
# 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 SETree","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"}}}' \
  | bun apps/server/src/index.ts --db kb.db --llm-base-url http://localhost:8080/v1 mcp

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.

Async modifications: insert, build, and trigger_maintain are asynchronous — they enqueue work to the engine's maintenance queue and return an ack immediately ("insert queued" / "build queued" / "maintenance requested") rather than a synchronous result. The TS orchestrator drains the queue with one atomic maintenance_run engine op (run on a Bun Worker, the sole writer) after a 500 ms quiescence window. retrieve and stats remain synchronous.

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):

{
  "calibration": {
    "beta": 1.0,
    "tau": 0.5,
    "epsilon": 1.0,
    "faithfulness_threshold": 60
  },
  "default_budget": 4096,
  "max_concurrency": 0,
  "context_window": 8192
}

• 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. See apps/server/native/config.hpp for canonical defaults.
• --config <path> selects the file; without it the server falls back to the SETR_CONFIG env var. An empty env value counts as "not given"; --config "" is a usage error.
• beta/tau/epsilon/faithfulness_threshold must be finite; epsilon >= 0, faithfulness_threshold is an int in [-100,100] default 60; default_budget ≥ 1. epsilon is absolute per-child fidelity floor (no baseline scaling); faithfulness_threshold is the bottom-up re-summarization gate. Capability is β·per_level_loss raw (no loss_baseline normalization — ADR-0023).
• The dynamic baseline is retired by ADR-0023 — the store no longer has a calibration table; PerLevelHierarchyState (per-Clustering-Level HIT-oracle state — per-level member_ids/member_centroids/parent_ids/leiden_assignment + kNN adjacency) is persisted atomically with save_tree_with_hierarchy as the HIT oracle. Historical loss_baseline (median per-level loss) and save_calibration_baselines/refresh_baselines are retired.
• --beta / --tau / --default-budget override the file; the file overrides the built-in defaults.
• faithfulness_threshold may be temporarily changed to 0 by the user. See the code for more. If not then remove this line.

Repository layout

apps/playground/     demo executable
apps/server/         merged Bun+TS app (setr-server): default (or explicit `mcp`) =
                     stdio MCP server over the embedded engine; `inspect` = read-only
                     DB inspector (dumps, flat/top/json views); `host` = loopback web UI + chat
apps/server/native/  C++ engine shared lib (setr_engine -> libsetr-engine.so): the
                     former mcp-server wiring (ops, config seam, the passive
                     MaintenanceState behind the single maintenance_run op)
                     behind the extern-C setr_engine_{create,call,destroy,free} API
apps/benchmark/      benchmark harness: corpus reader + scaling ladder + latency proof (stub LLM by default, optional --llm-base-url)
apps/bench-insert/   insertion-only HIT benchmark (no LLM): insert_leaf + incremental_rebuild timing + G1 patch microbench
libs/core/           dependency-free core: domain types, interfaces, capability, tree cover, query surface
libs/embed/          all-MiniLM-L6-v2 embedder (ONNX Runtime, hand-rolled WordPiece tokenizer)
libs/store/          SQLite TreeStore (schema, serialization, PerLevelHierarchyState per-level persistence)
libs/maintain/       offline: insert_leaf, summarizer, incremental rebuild (incremental_rebuild/cluster_hierarchy with HIT oracle + G1 patching), maintenance passes, Leiden, build_tree
docs/adr/            decision records 0001–0027
architecture.md      module topology, contracts, data flow
CONTEXT.md           glossary (canonical terminology)
scripts/             asset fetch scripts (minilm model, benchmark corpus) + locomo/
tests/               zero-dependency test harnesses per target

The app (stdio MCP server, one-shot inspector, loopback web UI + chat) runs on Bun from apps/server/ and is documented in its own guide: apps/server/README.md.

Documentation

• CONTEXT.md — canonical glossary (Tree Cover, Carried, Capability Score, Fidelity, Loss, Context Budget, Offset-Aware Summarization, …).
• architecture.md — module topology, contracts, data flow, latency budget.
• docs/adr/0001–0027 — the decision records, one per number: 0001 fidelity formulation (per-node PCA), 0002 capability decision (semantic embedding approach), 0003 fidelity restate (ambient vector, loss scalar, capability score) with the spherical fidelity recurrence, 0004 leaf granularity / clustering / maintenance model, 0005 maintenance state machine and latency budget, 0006 v0 calibration lockdown, 0007 module structure and library topology, 0008 embedder stack (all-MiniLM-L6-v2, WordPiece, CPU ONNX), 0009 node model (own-embedding, whole-tree DP), 0010 persistence (SQLite replace-all), 0011 TargetLLM client contract, 0012 summarizer delivery contract (E4), 0013 Leiden community-detection contract, 0014 initial build orchestration (build_tree), 0015 concurrent summarization, 0016 web inspect host, 0017 hard arity cap removal, 0018 layer invariant and absolute-space descent for insert (superseded), 0019 centroid-based clustering + deferred summarization, 0020 singleton carry-forward, 0021 event-driven component-rebuild maintenance, 0022 constrained full-dissolution rebuild, 0023 incremental HIT-oracle rebuild, 0024 lock-free readers + MPSC mutation queue + leaf-root wrap, 0025 inspect chat mode, 0026 merge MCP server into apps/server, 0027 TS-owned maintenance cadence over one atomic maintenance_run.

Acknowledgements

• HIT-Leiden — the maintenance path (per-level dirty tracking against a persisted hierarchy oracle, G1 kNN graph patching, affected-community recomputation) follows the algorithm of Chunxu Lin, Yumao Xie, Yixiang Fang, Yongmin Hu, Yingqian Hu, and Cheng Chen, Maintaining Leiden Communities in Large Dynamic Graphs (arXiv:2601.08554, 2026). See ADR-0023 for how it maps onto this repo.
• hit-leiden (MIT OR Apache-2.0) — the persisted PerLevelHierarchyState oracle is modeled on its CommunityState (partition_state + hierarchy_levels + per-level kNN adjacency for G1 patching). License texts in THIRD_PARTY_NOTICES.md.

Status

v0 core complete: build, insert, maintain, retrieve, persistence, embedder, tests, and the merged app (apps/server — the stdio MCP server with the seven tools retrieve, trigger_maintain, insert, build, stats, reset, setr_switch, a one-shot inspector, and the loopback web UI + in-process chat; ADR-0026). Four calibration placeholders (τ, β, epsilon, faithfulness_threshold) await an empirical tuning pass on a real knowledge base. The HNSW scale-up (documented contract) remains the planned next step.