Kernels: reference numbers, verification runs and design history

Dated record of what was measured and decided while building the three store modes (descriptor-backed, kernel-only, item-backed), the offline tools and the verification harnesses. CLAUDE.md keeps only what changes how to work here and points at the section below; the header comments carry the contracts. Numbers refer to the ETH table_3 sequence of VSLAM-LAB-Benchmark unless stated otherwise. Append, do not rewrite: a later measurement gets its own dated paragraph.

MegaLoc descriptors (2026-09-02 … 09-05)

Expected numbers on real sequence frames: self ≈1.0, consecutive frames ≈0.9+, unrelated places ≈0.35–0.4 (MegaLoc's common-mode floor — the reason the kernel is centred); TensorRT-vs-PyTorch cosine ≈0.99+ (worst seen 0.994, fp16 backbone / fp32 aggregator, ~4 ms/image).

TensorRT 10.3 gotcha encoded in tools/export_megaloc.py: the upstream attention qkv.reshape(...).permute(...)[0..2] pattern is miscompiled by TensorRT's Myelin fuser (descriptor cosine 0.05 vs ONNX Runtime, while every isolated sub-graph looks fine); the export slices q/k/v from the projection output instead. Uniform fp16 was a separate loss (cos 0.93), fixed by pinning the aggregator to fp32.

Standalone build outside pixi (as done for the first verification): system g++ 11 + /usr/include/eigen3 work for the core; the viz module linked against a conda OpenCV needs the env's libstdc++ (-DCMAKE_EXE_LINKER_FLAGS="-L<env>/lib -Wl,-rpath,<env>/lib"), otherwise __cxa_call_terminate@CXXABI_1.3.15 is undefined at link time.

Kernel-only stores from VPR-LAB D.npy (2026-09-07)

Scope decision: issue #2's add_row / row-based query were deliberately not added (decided 2026-09-07: loader only), so a kernel-only store cannot grow or answer insertion queries — the AllFeature host therefore has no vpr: matrix backend; that is the follow-up. The default-options set_kernel overload exists because GCC cannot use a nested struct's member initialisers as a default argument of the enclosing class.

What D.npy is. VSLAM-LAB's <sequence>/vpr-lab/D.npy is squared_euclidean: faiss.pairwise_distances (squared L2) on MegaLoc descriptors, then np.minimum.reduce over four image rotations — so it is asymmetric (D_0.npy is the symmetric unrotated one) and S = 1 − D/2. Verified on ETH table_3: only this transform reproduces MegaLoc's statistics (floor 0.37, consecutive 0.91) and makes D_0 PSD. Rows/cols index the rgb.csv the matrix was computed on (= Frame::frame_id when the host consumes the full csv; VSLAM-LAB's rgb_idx/rgb_step subsetting is the caller's job via Eigen indexing).

Reference kernel_demo run on VSLAM-LAB-Benchmark/ETH/table_3/vpr-lab/D.npy (1180 frames, default --kind squared-euclidean): similarity min 0.156 / median 0.368 / consecutive 0.909, max asymmetry 0.082 (the rotation-min), 3 negative eigenvalues (smallest −0.014) → both WARNs fire, set_kernel 155 ms, whole run 0.65 s.

On this indefinite kernel the culler is broken, not just degraded (found 2026-09-07 when tau 0.7 kept 970 frames and tau 0.3 kept 969): the alive unique-information scores 1/M_ii run up to 39.7 (must be ≤ 1), the history "price" is no longer a valid bound, so history rows cross tau and the greedy loop jams after ~210 culls whatever tau is. Sweep on D.npy, survivors of 1180 at tau 0.1 / 0.3 / 0.5 / 0.7 / 0.9:

variant	0.1	0.3	0.5	0.7	0.9
unclipped, centred	1015	969	970	970	967
unclipped, --raw	958	955	951	949	947
--clip (centred)	879	212	84	39	17
--raw --clip	529	91	31	11	5

The PSD D_0.npy (centred, no clip) gives 214 at 0.3 and 39 at 0.7, i.e. the same as clipped D.npy. So for a rotation-min matrix always pass --clip (the demo prints a WARNING block when it sees negative eigenvalues without clipping); clip_to_psd costs the eigenvectors (set_kernel 155 → 810 ms at n = 1180). This is issue #3 made concrete — a host-supplied kernel needs the PSD check, not just the unit-diagonal one. The centred first-cull degeneracy of issue #5 also applies here in full (every view alive, no history), which is why a centred run logs "1-2 culled views are above tau" afterwards; --raw avoids that part.

Count-driven culling and the rgb_placecell consumer (2026-09-10)

CullParameters::target_alive > 0 runs the same greedy order with tau = +inf (no v_i bound, no history price test) and stops when that many views are alive in scope, never below min_keyframes. synthetic_demo/kernel_demo only exercise the tau path; the count-driven path is covered by VSLAM-LAB's rgb_placecell smoke test (configs/test_exp_placecell.yaml) and a standalone Python check (1180 → 100 on ETH table_3: unique information at removal rises monotonically 0 → 0.45, first/last frame kept, a second call with the same target culls nothing).

First production consumer: VSLAM-LAB's rgb_placecell: <n> experiment parameter (Capabilities/placecell.py in the VSLAM-LAB repo, pixi env placecell, task placecell-select) loads <sequence>/vpr-lab/D.npy → similarity_from_distance("squared-euclidean") → set_kernel(S, frame_indices, clip_to_psd) → count-driven cull_keyframes and keeps the n surviving frames in the experiment's rgb_exp.csv; on ETH table_3 the whole selection (1180 → 100, centred, clipped) takes ~4 s. The clip matters there: the full D.npy has 3 negative eigenvalues, while the every-other-frame submatrix (590) is already PSD (min eigenvalue 0.021).

COLMAP shared-information kernel (2026-09-07)

tools/colmap_information_kernel.py — numpy only (no pycolmap exists in any pixi env here; own reader for COLMAP .bin/.txt models, verified identical): the pairwise shared-information kernel of a COLMAP reconstruction, consumed through load_npy/set_kernel/kernel_demo --kind similarity --ids.

Model. For images (i, j) the variables are x = (pose_i, pose_j, every point seen by either image); Gauss-Newton information from the pinhole reprojection Jacobians (σ_pix = 1; left perturbation [δθ, δt] of cam_from_world; non-pinhole models approximated by f, c with a warning); isotropic prior Λ₀ (σ_t = median consecutive baseline in sequence order, σ_rot = 1 rad, σ_point = median distance to the cloud centroid; --prior-scale, --sigma-*) fixes the 7-DoF gauge. I_ij = ½[logdet(Λ₀+H_i) + logdet(Λ₀+H_j) − logdet(Λ₀) − logdet(Λ₀+H_i+H_j)] and the kernel is the normalised MI K_ij = I_ij / sqrt(G_i G_j), G_i = I_ii (data processing ⇒ K ∈ [0,1], unit diagonal). Every logdet is a Schur complement of the independent 3×3 point blocks onto the pose block; ImageInfo precomputes the single-image reduction (per-point logdet P_k and Schur term T_k, reduced pose information A_full) so a pair costs O(#shared points) — 53 images / 946 overlapping pairs in 0.1 s. --check N re-evaluates N random pairs on the dense (12 + 3m)-dim system (slow: 200 pairs ≈ 6 min; worst relative error seen 2e-10).

Gotcha that bit: COLMAP maps two keypoints of one image to the same 3D point occasionally, so observations ≠ unique points; the per-image blocks are aggregated per unique point (np.unique + np.add.at) and the dense check uses one column per unique point — before that, single images matched the dense formula and pairs were off by 40–100 nats.

Ids: data-row index of --rgb-csv (the sequence's rgb.csv / rgb_raw.csv, matched by image file name against path_rgb_0 = frame_id = D.npy numbering); without it the tool falls back to rgb_exp.csv next to the model folder with a warning (the experiment list's numbering), then to COLMAP image ids; unregistered images get no row. Pass the best sub-model (<colmap_dir>/best_model names it — after a re-run of the ETH demo it was 1, and 0 held a 2-image fragment; the tool warns when given a folder with sub-models). Output kernel.npy (float32 NMI), mutual_information.npy (I_ij in nats, G_i on the diagonal), ids.csv (internal_id, external_id, image_id, name, information_gain, observations).

Reference on ETH table_3 (53-image model): G_i median 1973 nats, I_ij median 33 / max 1690 nats, K over overlapping pairs 0–0.60 (consecutive frames 0.40), PSD (min eigenvalue 0.38, so no --clip needed). tau lives on a different scale than on the MegaLoc kernel: each image's unique information 1/(K⁻¹)_ii on the raw kernel is 0.54–0.90 (an image's own gain is dominated by points and pose the pair does not share, and its best partner explains a median 0.46 of it), so survivors of 53 at tau 0.3 / 0.5 / 0.7 / 0.9 / 0.95 are 52 / 50 / 47 / 16 / 13 centred and 53 / 53 / 41 / 19 / 13 --raw — the useful range is tau ≈ 0.7–0.95, and the centred first cull is again the issue-#5 degenerate one.

Design decisions and rejected alternatives (settled 2026-09-07 before implementation): the correlation analogue saturates at 0.99+ with 26 negative eigenvalues; prior scale ×0.1/×10 moves K by ≤ 0.08; shared-only points differ ≤ 0.004; info-weighted covisibility cosine correlates 0.985.

tools/colmap_kernel_demo.py (pixi run colmap-demo), the counterpart of kernel_demo <D.npy> for the geometric kernel: runs colmap_information_kernel.py, then kernel_demo --kind similarity --ids into <out>/selection_tau<T>[_raw]/ (dump + rgb.csv of the survivors), then checks: survivors are registered images by name, alive + culled = the registered set, the first frame is kept, counts agree with kernel_demo's report; exit 1 on any failure (also when a step fails, e.g. a downsampled rgb.csv that cannot index the ids). ETH table_3, 53 images: tau 0.9 centred keeps 16 (0, 145, 197, 254, 333, 405, 423, 495, 533, 641, 771, 869, 948, 1026, 1142, 1179 — spread along the sequence), tau 0.7 --raw keeps 41; the whole chain runs in ~1 s.

tools/compare_kernels.py (pixi run compare-kernels): the appearance kernel (VPR-LAB D.npy → 1 − D/2, symmetrised) and the COLMAP information kernel over the images the reconstruction registered (selected from D.npy through ids.csv), both min-max normalised to [0,1] off the diagonal (the VPR cosine floors at ~0.37, the information kernel lives in 0–0.6), as two heatmaps in sequence order, their difference (diverging), a scatter of paired entries and Pearson/Spearman on stdout. ETH table_3, 53 images: raw Pearson 0.72 / Spearman 0.46, centred 0.81 / 0.58; the two agree on the diagonal band and the loop closure (first ↔ last frames), while MegaLoc gives 0.3–0.6 to pairs COLMAP finds share nothing — appearance similarity without co-observed structure (mean VPR − COLMAP = +0.24 raw, +0.14 centred). Figures for that run are next to the model in colmap_00000/1/information_kernel/.

Item-backed stores (covisibility kernel, 2026-09-24)

Designed for the covisibility kernel of AllFeature-VSLAM (docs/plans/covisibility_kernel.md in the parent). Implementation: the first set_items call for an id appends a row (the internal id), later calls for an alive id replace its set and the diff (std::set_difference both ways) flows through an inverted index item_index_: item → views into an n × n integer matrix of shared counts (item_counts_) at O(Σ posting-list lengths); item_norms_[i] = |P_i|. The float kernel and the centring row/total sums are rebuilt from the counts lazily (materialise_kernel_locked, O(n²), kernel_dirty_) by every kernel reader — kernel(), snapshot()/centred_kernel(), cull_keyframes, dump, the item query — so a burst of set_items calls costs one rebuild. The item query's dots with every stored view are its shared counts read off the inverted index, k_i = hits_i / sqrt(|Q| |P_i|), k_xx = 1. Both queries share explainers_locked → query_system_locked (raw or centred K_AA, k_xA) → solve_information (jitter + LDLT). An empty set's row sum is NaN and query_system_locked averages the centring over the m ≤ n finite rows. Profiler rows set_items (sizes: stored views, items) and unexplained_information_items; on_set_items narrates at DEBUG; dump's views.csv gained an items column (|P_i|, 0 in the other modes).

usable_rows change (same day): before, any NaN in a row disqualified it, so one bad view disqualified every view (its column touches all rows) and cull_keyframes silently did nothing; now only the culprit row (all off-diagonal entries NaN) is ignored.

Verified 2026-09-24 with a scratch parity harness against a descriptor store of normalised indicator vectors (system g++ 11 + /usr/include/eigen3, core only): raw/centred kernels agree to 2e-7, insertion query and culler alive_unique_information to 6e-7 raw and centred, the Schur identity holds (query v = unique information right after insertion, 1e-6), an incremental refresh equals a fresh store bit-for-bit, the culled set stays frozen, an empty view leaves the other 29 rows equal to a 29-view descriptor store, and 5 injected exact duplicates are culled at tau 0.3. synthetic_demo and kernel_demo (YOUTUBE acinipo D.npy, --clip --tau 0.7) still pass. The bindings pass the same parity/refusal/frozen-set checks from Python (pixi run build in the default env, Python 3.14). No SLAM run yet: the host side is the parent's docs/plans/covisibility_kernel.md, steps 3+.

COLMAP kernel: sign fix and a ground-truth model (2026-09-30)

pairwise_mutual_information, the batched version that replaced the per-pair loop on 2026-09-10 (7d39dc4), added the prior term of every shared point with the wrong sign (−3 log λ_p instead of +3 log λ_p), so every I_ij was off by 3 |shared| log λ_p nats, zero only when σ_point = 1. Found while building a ground-truth REPLICA office0 model (σ_point 1.78 m), where the batched value disagreed with the single-pair reduction by up to 93 % and the dense formula sided with the single pair; after the fix batched vs single-pair agree to 8.6e-13 on 200 pairs and batched vs dense to 4e-8. On ETH table_3 (σ_point 1.36 m) the fix moves K by up to 0.12 (mean 0.013), the consecutive-frame median 0.39 → 0.50, max 0.475 → 0.596, and removes the 16 negative entries. The tau-scale numbers above (unique information 0.54–0.90, tau 0.9 keeping 16 / 19 of 53) date from 2026-09-07, with the original per-pair code, and are unaffected; kernels built between 2026-09-10 and this fix are biased and should be rebuilt.

New tools/colmap_gt_model.py builds a COLMAP text model from a database's verified matches and a synthetic sequence's ground-truth poses and depths. On REPLICA office0: world-from-camera poses and z-depth confirmed (0.33 px median transfer error; camera-from-world gives 231 px, ray depth 6.7 px), pixel offset 0 fits better than COLMAP's 0.5 (0.33 vs 0.45 px), 89.5 % of 7.7 M verified matches confirmed, 22,060 points at 0.23 px median reprojection. Filtering the matches before the union-find is required: without it the first build merged 416 k keypoints into 12 k tracks and failed its own check at 203 px. The resulting kernel (400 images) is PSD (min eigenvalue 0.22), with a consecutive-frame median of 0.62 and a maximum of 0.755.