Repository navigation
traverse(query, store, policy) — pluggable graph traversal with operator-enforced safety #47
Description
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 aWalkPolicyprotocol:seed / score / select / expand / stop. Safety primitives (visited-set on(source, artifact_id), depth cap, node budget) are non-optional and enforced bytraverseitself — 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:
traverseis 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/disclosecompose 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).
Activity
fix(review): PEP 508 URL deps, case-insensitive self-edge, node-id ca…
links: typed-edge view on CorpusStore + GraphStore protocol (#46) (#53)
thorwhalen commentedon Jun 13, 2026
Design decisions (pre-implementation) — resolving the contract against ir's idioms:
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 (theCorpusGraph/PPR case, viacanonical_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 (sameartifact_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:traversekeys 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.Safety is the operator's, enforced regardless of policy (report 12's "single highest-leverage robustness decision"). A
WalkStateowned bytraverseholdsvisited/depth/node_budget/query/ results; the visited-set, depth cap, and node budget are checked bytraverseitself, so a buggy or adversarial policy (one whoseexpandcycles forever and whosestopnever fires) still terminates.stop()is the injected sufficiency check — safe defaultNone= run to budget.WalkPolicyprotocol (report 12'sseed / 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).storeis passed to the policy verbatim —traversenever interprets it. Collapsed-tree takes aCorpus(search to seed on summaries,records_for_artifactto expand to chunks); an artifact-link policy takes aCorpusGraph(neighbors). That's what keeps the operator graph-agnostic.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 viair.evalon a hermetic corpus, per the acceptance).PPR stays a shape — expressible as a degenerate policy (closed-form
score,stopimmediately true,expandviaCorpusGraph.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).Flat stays the default.
traverseis opt-in; promotion of any policy requires beating flat+rerank on the eval set. ReturnedSearchHits carry additive, JSON-clean provenance —metadata["walk_depth"]andmetadata["seed"](the routing node) — and compose withselect/discloseunchanged. New moduleir/traverse.py(one-seam-one-module).Implementation starting on this basis.
traverse(query, store, policy) — query-time graph traversal with oper…
thorwhalen commentedon Jun 13, 2026
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_policydefaults —DFLT_SUMMARY_KINDSincludesdocument/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,expandfinds no leaves) andtraverse()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_kindsdefaults 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_leavesdecision (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 →[], useir.search) is pinned as a documented characterization test. 348 tests green.