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 · visitsso 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#
python3 -m pytest tests/ -q # 37 tests
python3 -m ruff check .