Eve library

@nous/tree-search-reasoning

Other

Revision 1

On this page

Reasoning & search substrate for the Phase-178 autonomous-research stack (TODOS/phase-178 §178.2). A domain-agnostic tree/graph-search toolkit that every Phase-178 agent — the ML engineer, the self-play loop, the paper-studio experiment designer — reuses through one small surface.

Everything here is written against the protocols in types.py (Policy, WorldModel, ValueFunction, ProcessRewardModel, Reflector), so the search is fully decoupled from the domain: the same MCTS core drives code search, math reasoning, and planning. Language models, executors and simulators plug in behind those protocols.

What's implemented#

Kernel Module Summary
MCTS mcts.py PUCT selection Q + c·P·√N/(1+n), mean or optimistic-max value backup, optional Dirichlet root noise, value-fn or random-rollout leaf evaluation, process-reward shaping.
LATS lats.py Language Agent Tree Search — MCTS + LM value + in-search reflection threaded from failed leaves back into re-expansion (§178.2.1.1).
ToT / GoT tot.py Tree-of-Thoughts (BFS/DFS beam) and Graph-of-Thoughts (generate / aggregate / refine over a DAG) — lightweight patterns for cheap queries (§178.2.1.2).
rStar-Math rstar.py Code-augmented MCTS with a Bradley–Terry Process Preference Model (numpy SGD) and a four-round self-evolution loop that mines preference pairs from sibling Q-values and retrains the PPM (§178.2.1.3).
RAP rap.py Reasoning-via-Planning with RAP reward shaping (world-model reward + action self-evaluation) and a SimulatorWorldModel adapter that plugs a MuZero/RSSM latent dynamics function (Phase 176) in as the transition model (§178.2.1.4).
SearchKernel kernel.py One SearchKernel[State, Action] façade over all of the above with pluggable value fn / process-reward / expansion policy (§178.2.1.5).
Reward models reward.py OutcomeRewardModel (executor-grounded code/math verification), LinearProcessRewardModel + MCTSRolloutLabeler (ridge PRM trained on MCTS-rollout labels), RewardDriftMonitor (mean-shift / rank-collapse / tail-divergence alarms) (§178.2.2).

Design notes#

  • Max backup keeps value_sum == max_q · visits so a single verified leaf makes its whole branch attractive — the right default for reasoning search where you want to exploit a discovered solution, not average it away.
  • Reflection is attached to the parent of a failed leaf and gathered from the whole ancestor chain at expansion time; a reflection-aware policy (propose_with_reflections) receives it, a plain policy is called normally.
  • The PPM trains on preference pairs, not absolute step labels — a step on a higher-Q branch is preferred over its lower-Q sibling — exactly the rStar-Math signal, fit with a deterministic Bradley–Terry logistic objective.

Scope of local verification#

The published headline numbers (LATS 94.4% HumanEval, rStar-Math 90.0% MATH) are backbone-and-benchmark results requiring the specific models, datasets and GPU budget. What the test suite verifies locally is algorithmic correctness: on controllable domains with known optima the searches provably find the solution, PUCT trades exploration for exploitation as c_puct varies, the PPM learns a known ranking, the ridge PRM recovers a known linear target, and the drift monitor alarms on mean-shift and re-ordering. Plug an LM policy/value behind the protocols to run the published benchmarks.

Testing#

bash
python3 -m pytest tests/ -q     # 37 tests
python3 -m ruff check .