CosinePair::with_top_k construction is Theta(n^2) distance evaluations with per-pair allocations; measured ~n^3.48 end-to-end on square inputs

[Mec-iS]

Summary

CosinePair::with_top_k (src/algorithm/neighbour/cosinepair.rs:85, tag v0.6.10) builds its structure with an all-pairs double loop. The top_k parameter limits only the per-row candidate heap, not the scan, so construction costs Theta(n^2) cosine-distance evaluations regardless of top_k. Each evaluation allocates two fresh Vecs and recomputes both vector norms. Downstream consumers document this stage as O(n d log n) (arrowspace-rs src/laplacian.rs:14), but no tree or sub-quadratic structure exists in the implementation - the fastpair citation at cosinepair.rs:59-62 is inspiration-only.

Measured evidence

Stage-level profile of the A0 graph build through arrowspace-rs build_laplacian_matrix (generated latent matrices, release profile, Apple silicon / 12 cores, smartcore 0.6.10 from crates.io):

stage	2048x2048	4096x4096	exponent/doubling
StandardScaler normalise	12.571 s	99.538 s	~n^2.99
CosinePair::with_top_k (build)	90.055 s	1004.957 s	~n^3.48
degree scan (n queries)	0.057 s	0.320 s	~n^2.49
weighted kNN over all n rows	0.056 s	0.304 s	~n^2.44

The build carries 88-91% of end-to-end wall time. Query stages are cheap because query_row_top_k never scores most of the dataset (root cause 4 below). Harness, methodology, raw artifact: https://github.com/tuned-org-uk/smartcore-swarm (examples/m31_stage_profile/, benches/output/m31_stage_profile.md).

Root cause

1. All-pairs scan - init() (cosinepair.rs:147-171) evaluates every ordered pair (i, j) with i != j, even when top_k is set: n*(n-1) distance evaluations.
2. Per-pair allocations - cosinepair.rs:152-161: every distance call materialises two Vec<T> through Vec::from_iterator over get_row. That is ~n^2 short-lived allocations plus loss of contiguity.
3. Norm recomputation - Cosine::new().distance(...) recomputes both row norms for every pair; precomputed unit norms would cost O(n d) once.
4. Undocumented approximate queries - query_row_top_k (cosinepair.rs:211-222) strides candidates by step = n / top_k and scores only top_k of n rows. Queries are therefore approximate; nothing in the docs states this.

Relation to the sibling FastPair module

We considered algorithm::neighbour::fastpair (fastpair.rs) as the alternative before reporting:

• its init() (fastpair.rs:105-141) is likewise an all-pairs Theta(n^2 d) scan with the same per-pair Vec::from_iterator allocation pattern;
• it additionally materialises a dense n x n connectivity matrix during build (M::zeros(len, len), fastpair.rs:148) - 134 MiB at n = 4096 f64;
• it computes Euclidean squared distances only, and offers closest_pair() / ordered_pairs() for the dynamic closest-pair problem, with no per-row top-k query API that graph-Laplacian pipelines need.

So FastPair is not a drop-in replacement here today; the report above concerns the CosinePair path itself.

Impact

Any workload building a kNN-graph Laplacian through this path pays a quadratic construction with poor constants that dominates everything else once feature count scales. On our square doubling curve the measured exponent (~n^3.48).

Suggested directions

1. Constant-factor repair, large win first: precompute row norms at fit time, remove per-pair Vec allocations (operate on row slices), evaluate blocked/vectorised similarity computation.
2. Document query_row_top_k's stride sampling as approximate, or gate it behind an explicit flag.
3. Longer term: a genuine sub-quadratic neighbour structure (tree, LSH, or graph-based ANN) for both build and query phases.

Environment

smartcore 0.6.10 (crates.io), Rust 1.87 (edition 2024 workspace), macOS arm64, release profile. Downstream reproducer: https://github.com/tuned-org-uk/smartcore-swarm

[Mec-iS]

Verified downstream (smartcore-swarm, arrowspace A0 workload): 0.6.11 halves end-to-end graph-build wall time at 2048x2048 (102.7 s -> 52.0 s staged pipeline; baseline build_laplacian_matrix 101.4 s -> 52.5 s). Exact-by-default queries change results as expected - laplacian nnz rises 15374 -> 27766 at fixed params vs the stride-sampled 0.6.10 behaviour. All parity gates green with both consumers resolving 0.6.11. Thank you for the fast turnaround.