Qualify structured-embedding graph/router locality at the V1 quarter-probe budget

[snissn]

Parent: #4012

Evidence source: #4015 and #4023

Blocks: #4019 and the final #4012 production-readiness decision

Related non-blocking lane: #4030

Goal

Reach recall@10 >= 0.90 while probing at most 4 of 16 partitions for the declared structured-embedding V1 workload, with graph overlap 0.20, without weakening the frozen #4013 exact-result contract, balance, storage, resource, identity, or failure-honesty gates.

This is the acceptance umbrella for the structured-embedding lane. It is not a universal claim over high-entropy distributions.

Authoritative Scope Decision

The held-out evidence separates two workload regimes:

• Structured embedding mixtures remain on the no-waiver four-partition path in this issue.
• High-entropy distributions move to Qualify high-entropy vector search with an eight-partition safe profile #4030, which qualifies an explicit eight-partition safe profile with exhaustive sixteen-partition fallback and retains p4 as non-blocking research.
• Qualify high-entropy vector search with an eight-partition safe profile #4030 does not block this issue, Qualify structured quarter-probe graph search at 100k and 250k #4027, or Qualify graph-partitioned vector search on one host against Milvus and pgvector #4019.
• Closing this issue must never be described as universal four-partition qualification.

This is an explicit contract split, not an evidence waiver. The structured p4 recall target remains 0.90; the high-entropy negative result remains visible and authoritative.

Current Evidence

Retained structured 100k embedding mixture: 100,000 unique normalized vectors, 1,000 independently generated held-out queries, 128 dimensions, 16 partitions.

Stage	p4 recall/coverage	Meaning
reference primary oracle	0.8303	old placement cannot support the target
KaHIP primary oracle	1.0000	selected #4024 candidate makes structured p4 feasible
reference exact-router/local	0.7291	remaining membership/router work is real
all-partition exact union	1.0000	exact data/result path is sound

The selected KaHIP artifact has zero directed cut on this corpus, 6,283 maximum load under a 6,563 cap, and no held-out-query leakage.

Held-out high-entropy evidence is owned by #4030: the strongest measured p4 primary oracle is 0.6838, while p8 reaches 0.9873. Exact 0.20 overlap raises the measured p4 final-membership oracle only to 0.7042. Those results explain the split and forbid a universal p4 claim.

Child Graph and Gate Ownership

Node	Owner	Depends on	Authoritative exit
#4023	attribution	completed #4015 evidence	staged placement, membership, router, local, and end-to-end ceilings are executable
#4024	structured graph placement	#4023	bounded deterministic placement passes the structured p4 primary oracle
#4025	structured final membership	#4023 and #4024	overlap utility is honest and final membership is router-visible
#4026	structured kRt	#4023, #4024, and #4025	exact router is close to membership oracle; approximate regret is bounded
#4027	structured final evidence	#4023-#4026	repeated 100k and committed 250k structured gates pass
#4030	high-entropy safe profile/R&D	#4023	separate non-blocking p8/p16 qualification and p4 research
this issue	structured acceptance	#4027	#4019 handoff with no universal claim

#4015 -> #4023 -> #4024 -> #4025 -> #4026
#4023 + #4024 + #4025 + #4026 -> #4027
#4027 -> #4022 structured acceptance
#4018 + #4022 -> #4019
#4023 -> #4030 (non-blocking for the structured lane)

Gates

Gate	Target	Owner
structured primary-home p4 oracle	>=0.90, or a measured gap closed by final membership	#4024/#4025
structured exact kRt p4	within 0.02 of final-membership oracle	#4026
approximate-router regret	<=0.01 absolute versus exact kRt	#4026
structured p4 end-to-end recall@10	>=0.90	#4027
matched-recall QPS	>=1.15x exhaustive p16	#4027
matched-recall p95	no worse than exhaustive, or explicit #4012 acceptance	#4027
overlap storage	<1.35x graph/disjoint	#4025/#4027
exact parity, balance, resources, failure honesty	pass	all children

Boundaries

• Do not relax the structured 0.90 recall or 4/16 probe targets.
• Do not use held-out query labels to build partitions, overlap, or routing.
• Do not substitute edge cut, storage utilization, or larger EF for staged recall attribution.
• Do not import experimental research code as an online/runtime dependency.
• Do not claim Qualify high-entropy vector search with an eight-partition safe profile #4030 is complete or that high-entropy p4 is qualified when this issue closes.
• Product service wiring and Milvus/pgvector comparison remain Qualify graph-partitioned vector search on one host against Milvus and pgvector #4019; multi-host qualification remains TreeDB vector partition continuation D: qualify multi-host network and failure behavior #3983.
• V1 stays experimental/off until Qualify structured quarter-probe graph search at 100k and 250k #4027 and this acceptance issue close.

Test, Performance, Branch, Review, and CI Policy

Use clean issue-scoped worktrees from current merged predecessors. Performance-changing candidates require identical before/after corpus, query, oracle, topology, timing, resource, and artifact identities. Require focused plus affected normal/race/reopen/fault tests, latest-head CI, mature Codex/Copilot/CodeRabbit review, and zero unresolved threads. Merge in dependency order.

Completion Criteria

• Decompose V1 quarter-probe locality into placement, overlap, router, and local-search ceilings #4023 reports the causal attribution ladder.
• Select balanced graph placement for structured embeddings #4024 lands the selected bounded structured-placement correction.
• Make structured overlap utility-ordered and visible to routing #4025 lands honest exact-budget overlap and final-membership router input.
• Implement and tune bounded kRt routing for structured embeddings #4026 lands the bounded structured kRt model and closes router regret.
• Qualify structured quarter-probe graph search at 100k and 250k #4027 passes repeated retained 100k and committed 250k structured gates.
• Exact semantics, failure honesty, balance, storage, and resources remain green.
• Land graph-partitioned vector search V1 contract and production readiness #4012, Qualify vector-partition V1 on diverse corpora and held-out queries #4015, and Qualify graph-partitioned vector search on one host against Milvus and pgvector #4019 receive one final structured-scope disposition.
• The final disposition links Qualify high-entropy vector search with an eight-partition safe profile #4030 and explicitly declines a universal four-probe claim.

[snissn]

Predecessor handoff complete: #4015 closed via merged PR #4021 at 765616d3d20e5fa612376711fd9628e3d8f7c9ee. The exact reviewed head was 2fc0dd06972ec5e3dbc79af85fa3b4451acca525; Codex found no major issues, all 21 review threads were resolved, and all 34 latest-head checks passed. #4012 and #4019 now make this issue authoritative for the quarter-probe routing/locality correction, matched-recall gates, and canonical retained 1M rerun. The accepted interim disposition remains experimental/off.