# @nous/tree-search-reasoning

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 .
```