traverse(query, store, policy) — pluggable graph traversal with operator-enforced safety

[thorwhalen]

Problem

With edges in place (#46), ir needs the query-time traversal operator. Report 12's central claim: recursive retrieval, routing, RAPTOR collapsed-tree, PPR/spreading-activation, and beam walks are one operator — "score frontier → select → expand → test stop" — parameterized by a pluggable policy; and the engineering substance is termination: safety ("will it stop?" — structural, enforced by the operator) vs sufficiency ("should it stop?" — injected, fallible). Graphs here may contain directed cycles (citations, cross-refs), so safety cannot be a policy's responsibility.

Scope (report 12 §5 contract, adapted to ir idioms)

• traverse(query, store, *, policy, max_depth=..., node_budget=..., k=...) -> list[SearchHit] with a WalkPolicy protocol: seed / score / select / expand / stop. Safety primitives (visited-set on (source, artifact_id), depth cap, node budget) are non-optional and enforced by traverse itself — report 12 calls this "the single highest-leverage robustness decision". stop() is the injected sufficiency check; safe default is None (run to budget).
• First policy, pure-vector (no LLM in the query loop): summary-routing / collapsed-tree — seed on summary/description surfaces, expand down to the artifact's chunks (the document-summary-index pattern; ir's Skill/Package corpora already index description surfaces). RAPTOR's own ablation: collapsed-tree ≥ tree-traversal.
• Deferred to follow-ups (record, don't build): PPRPolicy (HippoRAG-2 style; the best multi-hop/cost trade-off), router/recursive policies, anything LLM-in-the-loop (cost-gated; the when-to-traverse decision is the agent layer's — raglab).
• Flat stays the default: traverse is opt-in; promotion of any policy requires beating flat+rerank on our eval set (report 12: flat wins simple lookup decisively; GraphRAG-global ≈57×/≈210× cost). Wire an eval harness case before promoting (ir.eval has the machinery).
• Returned hits carry provenance of the walk (e.g. metadata["walk_depth"], seed id) — JSON-clean, additive.

Acceptance criteria

• A cyclic edge set terminates: visited-set + depth + budget enforced by the operator regardless of policy behavior (test with an adversarial policy that never stops).
• Collapsed-tree policy routes a synopsis/description match down to that artifact's chunks on a hermetic corpus, and beats flat top-k on a constructed routing case.
• PPR expressible as a degenerate policy (closed-form in score(), stop() immediately true) — shape-tested, not implemented.
• select/disclose compose downstream unchanged; flat search paths untouched.

Size: L. Depends on #46; synergizes with #48 (synopsis surfaces). Capability 1 (ir). Refs ADR #43, report 12, epic #38 (boundary revision recorded there).

[thorwhalen]

Design decisions (pre-implementation) — resolving the contract against ir's idioms:

1. The operator is node-granularity-agnostic; the visited-set keys on the policy's node id. The issue names (source, artifact_id) — that is the artifact-level form (the CorpusGraph/PPR case, via canonical_node_id). But the collapsed-tree policy routes a description match down to that artifact's chunks, and in ir a description and its chunks are surfaces of one artifact (same artifact_id) — so a strict (source, artifact_id) visited-set would mark the whole artifact visited at the seed and block descent to its own chunks. Resolution: traverse keys its visited-set on whatever hashable node id the policy yields (policy.node_id(node)) — the record id at surface granularity, (source, artifact_id) at artifact granularity. Strictly more general, and it still is (source, artifact_id) for the artifact-link policies.

2. Safety is the operator's, enforced regardless of policy (report 12's "single highest-leverage robustness decision"). A WalkState owned by traverse holds visited / depth / node_budget / query / results; the visited-set, depth cap, and node budget are checked by traverse itself, so a buggy or adversarial policy (one whose expand cycles forever and whose stop never fires) still terminates. stop() is the injected sufficiency check — safe default None = run to budget.

3. WalkPolicy protocol (report 12's seed / score / select / expand / stop, plus the two ir needs): seed(state, store) → nodes, score(state, node, store) → float, select(scored) → subset (beam/greedy; default = all), expand(state, node, store) → nodes, stop(state) → bool, node_id(node) → Hashable (the visited-set key), to_hit(node, score, depth) → SearchHit | None (None = a router-only node, e.g. a summary that routes but isn't itself a result).

4. store is passed to the policy verbatim — traverse never interprets it. Collapsed-tree takes a Corpus (search to seed on summaries, records_for_artifact to expand to chunks); an artifact-link policy takes a CorpusGraph (neighbors). That's what keeps the operator graph-agnostic.

5. First policy — collapsed_tree_policy (pure-vector, no LLM in the loop): seed on the top summary/description surfaces (summary_kinds=("description","synopsis","capability")), route-only (to_hit → None); expand to the artifact's leaf chunks (leaf_kinds=("chunk","readme_chunk")), which are the emitted results, scored by cosine to the query. So a query that matches an artifact's summary surfaces that artifact's best chunk — beating flat top-k on a constructed routing case where the gold chunk is buried under distractor surfaces flat ranks higher (verified via ir.eval on a hermetic corpus, per the acceptance).

6. PPR stays a shape — expressible as a degenerate policy (closed-form score, stop immediately true, expand via CorpusGraph.neighbors); shape-tested, not implemented or promoted. Router / recursive / LLM-in-loop policies are recorded, not built (cost-gated; when to traverse is raglab's call).

7. Flat stays the default. traverse is opt-in; promotion of any policy requires beating flat+rerank on the eval set. Returned SearchHits carry additive, JSON-clean provenance — metadata["walk_depth"] and metadata["seed"] (the routing node) — and compose with select/disclose unchanged. New module ir/traverse.py (one-seam-one-module).

Implementation starting on this basis.

[thorwhalen]

Shipped in ir 0.1.21 (squash-merge 509e9ff, PR #54).

Post-merge follow-up beyond the original scope: an adversarial multi-dimension review surfaced a footgun in the shipped collapsed_tree_policy defaults — DFLT_SUMMARY_KINDS includes document/capability, so on a WholeText- or Skill-only corpus (one summary-kind surface per artifact, no leaf kinds) every surface was classified as a router (to_hit→None, expand finds no leaves) and traverse() silently returned [].

Fix (commit 979794a): the router/leaf split is now structural, not kind-based — a summary surface routes (and is suppressed from results) only when its artifact actually has leaf surfaces to descend to. A leaf-less summary is emitted directly, so a single-surface corpus degrades to flat-over-summaries instead of returning nothing. The broad summary_kinds defaults are kept on purpose: that is what lets such corpora seed at all.

Tests (commit aaa5de3, from confirmed review findings): a mixed-corpus test pins the per-artifact has_leaves decision (a corpus-global flag would pass all prior tests — caught by mutation); completeness assertions on the WholeText/Skill tests pin the "emit all leaf-less seeds" contract; and the Chunked-only boundary (no summary surface → [], use ir.search) is pinned as a documented characterization test. 348 tests green.