perf(exec): parallelize exact cosine KNN by canonical source

[DecisionNerd]

Problem

Exact cosine KNN and similarity evaluate each source vector against its candidates serially even though source rows are independent. This leaves available embedded CPU capacity unused on one of GraphForge's clearest compute-bound O(N²D) workloads. Naive parallelization could change dot-product order, top-k ties, output order, cancellation, or resource-limit behavior.

Objective

Parallelize exact and filtered cosine work by canonical source partition through GraphForge's bounded private CPU pool while keeping each numeric reduction and final result bit-for-bit identical to serial execution.

Debt / regime

• Debt type: development and test/proof
• Quality regime: A compute

Requirements

1. Consume feat(api): define a bounded embedded execution resource policy #337's instance-owned bounded CPU pool and automatic crossover policy; never use Rayon's process-global pool.
2. Partition work only by canonical source ordinal. Preserve the existing serial coordinate order for vector validation, norm calculation, every dot product, score clamping, candidate ordering, and top-k tie breaks.
3. Cover exact KNN, all-score cosine similarity, and filtered KNN without duplicating complete vector or candidate inputs per worker.
4. Merge worker outputs in canonical source order and retain target/score ordering exactly. Batch boundaries from the columnar output work must not affect results.
5. Preserve shared work/output limits, structured numeric errors, cancellation, and no-partial-result behavior under concurrent workers.
6. Retain a serial path below a measured crossover threshold or when the resource policy provides one compute thread.
7. Use the CSR/dense projection from the CSR-native issue and bounded Arrow output from the shaping issue; do not introduce a parallel-only graph representation.
8. Keep Rust authoritative with unchanged thin-binding behavior.

Acceptance Criteria

• Exact, all-score, and filtered cosine outputs have identical schemas, row ordering, scores, tie resolution, and fingerprints at 1/2/4/8/automatic configurations.
• Dot products retain canonical serial coordinate order; no parallel floating reduction or approximate similarity path is introduced.
• Cancellation, invalid vectors, non-finite arithmetic, work limits, output limits, and worker failure return deterministic structured outcomes without partial results.
• Automatic mode selects the serial path below a documented measured crossover and parallel execution above it without regressing accepted small fixtures.
• test(performance): establish the M4 embedded baseline and entry gate #334 before/after evidence records source/candidate/dimension work, threads, peak RSS, output rows, fingerprint, and hardware-specific timing.
• Relevant Rust, public facade, Python/Node parity, and exact-head CI remain green.

BDD Completion Scenarios

Scenario: Independent source rows execute in parallel

Given an exact cosine workload above the measured crossover and a multi-thread policy
When GraphForge evaluates source rows
Then sources execute through the bounded local CPU pool
And merged rows and scores are bit-for-bit identical to the one-thread result.

Scenario: Small work avoids parallel overhead

Given a cosine workload below the accepted crossover or a one-thread policy
When the same invocation runs
Then GraphForge uses the serial path
And no worker-pool setup becomes a universal latency tax.

Scenario: Cancellation remains atomic

Given an in-flight parallel cosine invocation
When cancellation or a shared resource limit is observed
Then all workers quiesce and return the established structured outcome
And no partial or out-of-order result escapes.

Implementation Notes

Likely surfaces include algorithm_similar_knn.rs, algorithm_similar.rs, algorithm controls, the #337 CPU pool adapter, bounded output sinks, similarity tests, and #334 benchmarks.

Worker-local candidate/top-k buffers should remain bounded and results should carry source ordinals for deterministic merge. Avoid parallelizing the inner floating-point dot product.

Observability

Record aggregate source rows, candidate comparisons, dimensions, selected thread/path, worker chunks, peak RSS, cancellation, output rows, and result fingerprint. Do not record vectors, scores tied to UUIDs, graph data, or local paths.

Security And Privacy

No new security or network surface is added. Worker panics/errors must be converted through the existing structured boundary and must not expose vector contents.

Testing

• Unit-test chunk boundaries, canonical merge, ties, negative zero, non-finite values, filtered duplicates, cancellation, and worker errors.
• Run the complete thread matrix against deterministic random and adversarial vector fixtures with exact fingerprint equality.
• Map Scenario 1 to thread-parity integration and manual performance evidence, Scenario 2 to crossover tests, and Scenario 3 to cancellation/resource tests.
• Run formatting, targeted clippy/tests, and repository-required exact-head CI.

Documentation

Document exactness, thread selection/crossover, resource policy, performance methodology, and the absence of approximate or GPU behavior.

Non-Goals

• Approximate nearest-neighbor indexing.
• Parallel floating-point reduction within a dot product.
• GPU, SIMD-specific public semantics, distributed execution, or foreign vector engines.
• Changing cosine schemas, tie rules, or numeric precision.

Related Issues

• test(performance): establish the M4 embedded baseline and entry gate #334 — entry and thread evidence; blocks this issue.
• epic(performance): close M4 embedded performance and scale #335 — M4 close tracker; this issue blocks it.
• feat(api): define a bounded embedded execution resource policy #337 — bounded CPU policy; blocks this issue.
• perf(exec): consume persisted CSR without edge-scale hash-map expansion #340 — CSR-native graph projection; blocks this issue.
• perf(exec): shape analyst outputs directly into bounded Arrow batches #341 — bounded Arrow result shaping; blocks this issue.

[coderabbitai]

🔗 Related PRs

#217 - feat(api): add embedded write modes [merged]

---

📝 Issue Planner

_{Check the box below or use the @coderabbitai plan command to generate an implementation plan and prompts that you can use with your favorite coding assistant.}

• Create Plan

---

🧪 Issue enrichment is currently in open beta.

You can configure auto-planning by selecting labels in the issue_enrichment configuration.

To disable automatic issue enrichment, add the following to your .coderabbit.yaml:

issue_enrichment:
  auto_enrich:
    enabled: false

💬 Have feedback or questions? Drop into our discord!