fix(analytics): O(block×N) correlation snapshot — tiled corr build + screened lead-lag (#75) #76

Merged

gertjan merged 2 commits from fix/correlation-tiled-memory into main 2026-07-07 10:02:18 +00:00

Conversation 0 Commits 2 Files changed 6 +644 -135

gertjan commented 2026-07-07 08:48:43 +00:00

Owner

Copy link

Full durable fix for #75, in two reviewable commits.

Commit 1 — tiled correlation build + load hygiene (Phases 1+3)

• compute_corr_matrix fills one preallocated N×N float32 corr + int16 overlap in row-block stripes (mirrored upper-triangle blocks → exactly symmetric by construction); per-block masked-BLAS temporaries are O(block × N) instead of ~6 simultaneous N×N float32 (~13 GB at N≈24k)
• in-place masking in the lagged kernel; per-row abs + argpartition in top_k_neighbors; in-place distance transform + blockwise symmetrization in hierarchical_clusters
• correlation_refresh pivots asyncpg records straight into the float32 matrix on a worker thread (the old path held ~8M intermediate Python tuples, multi-GB, for the whole compute); fixes an accidental O(N²) symbols.index() loop

Commit 2 — screened lead-lag scan + stopgap reverts (Phases 2+4)

• find_lead_lag_pairs no longer materialises any N×N matrix: a tiled screen sweeps each lag's improvement surface (|lagged_corr| − |sync_corr|) in row-blocks keeping per-lag row/column top-k improvements, then rescans the surviving ~10·k·N pairs exactly across all lags with chunked elementwise correlation and a vectorised group-by selection (replacing the O(N²) Python double loop — ~40 min of interpreter time at N=24k)
• provably output-identical to the full N² scan (any pair in a seed's final top-k must rank top-k in its row/column at its best lag). The issue's proposed sync-correlation candidate screen was measured first and rejected: it lost 13/20 injected genuine pure-lag pairs — precisely the interesting signal
• drops the dead lag_zero_overlap parameter; frees the overlap matrix before the scipy clustering peak
• reverts stopgaps per acceptance criteria: correlation_refresh timeout 14400 → 5400 s; analytics mem_limit 48g → 24g (contained container kill instead of host-level OOM victim selection)

Verification

• Old (main) vs new, N=300 synthetic factor universe with ragged listings and injected pure lead-lag structure: identical top-k buckets (900/900), identical cluster partition, identical ordered lead-lag lists (6497/6497 pairs, 20/20 injected pairs), values within 8e-7
• Full-pipeline benchmark at N=6000, T=350: peak RSS 1.95 → 1.23 GB, lead-lag stage 215 → 112 s; new temporaries no longer scale with N²
• Projected peak at N=24k ≈ 10–11 GB (scipy clustering is now the ceiling), staying under the 20 GB target through N≈35k
• New tests: tiled-vs-brute-force reference, block-size invariance, exact symmetry, per-pair lagged kernel vs full matrix, pure-lag detection, full brute-force lead-lag reference parity, record-pivot filtering. ruff/mypy/1034 unit tests green

Remaining #75 acceptance items (ops, post-merge)

• sample RSS on a real nightly run (docker stats / /proc) and confirm ≤ 90 min in RAM
• consider moving momentum_refresh back adjacent to correlation once confirmed

🤖 Generated with Claude Code

https://claude.ai/code/session_01JRnthdVhGGt5FeSQ8m3aUA

Full durable fix for #75, in two reviewable commits. ## Commit 1 — tiled correlation build + load hygiene (Phases 1+3) - `compute_corr_matrix` fills one preallocated N×N float32 `corr` + int16 `overlap` in row-block stripes (mirrored upper-triangle blocks → exactly symmetric by construction); per-block masked-BLAS temporaries are O(block × N) instead of ~6 simultaneous N×N float32 (~13 GB at N≈24k) - in-place masking in the lagged kernel; per-row abs + argpartition in `top_k_neighbors`; in-place distance transform + blockwise symmetrization in `hierarchical_clusters` - `correlation_refresh` pivots asyncpg records straight into the float32 matrix on a worker thread (the old path held ~8M intermediate Python tuples, multi-GB, for the whole compute); fixes an accidental O(N²) `symbols.index()` loop ## Commit 2 — screened lead-lag scan + stopgap reverts (Phases 2+4) - `find_lead_lag_pairs` no longer materialises any N×N matrix: a tiled screen sweeps each lag's improvement surface (`|lagged_corr| − |sync_corr|`) in row-blocks keeping per-lag row/column top-k improvements, then rescans the surviving ~10·k·N pairs exactly across all lags with chunked elementwise correlation and a vectorised group-by selection (replacing the O(N²) Python double loop — ~40 min of interpreter time at N=24k) - **provably output-identical to the full N² scan** (any pair in a seed's final top-k must rank top-k in its row/column at its best lag). The issue's proposed sync-correlation candidate screen was measured first and **rejected**: it lost 13/20 injected genuine pure-lag pairs — precisely the interesting signal - drops the dead `lag_zero_overlap` parameter; frees the overlap matrix before the scipy clustering peak - reverts stopgaps per acceptance criteria: `correlation_refresh` timeout 14400 → 5400 s; analytics `mem_limit` 48g → 24g (contained container kill instead of host-level OOM victim selection) ## Verification - Old (`main`) vs new, N=300 synthetic factor universe with ragged listings **and injected pure lead-lag structure**: identical top-k buckets (900/900), identical cluster partition, **identical ordered lead-lag lists (6497/6497 pairs, 20/20 injected pairs)**, values within 8e-7 - Full-pipeline benchmark at N=6000, T=350: peak RSS **1.95 → 1.23 GB**, lead-lag stage **215 → 112 s**; new temporaries no longer scale with N² - Projected peak at N=24k ≈ **10–11 GB** (scipy clustering is now the ceiling), staying under the 20 GB target through N≈35k - New tests: tiled-vs-brute-force reference, block-size invariance, exact symmetry, per-pair lagged kernel vs full matrix, pure-lag detection, full brute-force lead-lag reference parity, record-pivot filtering. ruff/mypy/1034 unit tests green ## Remaining #75 acceptance items (ops, post-merge) - sample RSS on a real nightly run (`docker stats` / `/proc`) and confirm ≤ 90 min in RAM - consider moving `momentum_refresh` back adjacent to correlation once confirmed 🤖 Generated with [Claude Code](https://claude.com/claude-code) https://claude.ai/code/session_01JRnthdVhGGt5FeSQ8m3aUA

gertjan added 1 commit 2026-07-07 08:48:43 +00:00

fix(analytics): tile correlation build to cut O(N²) peak memory (#75) ... 5b72e52c37

Phase 1+3 of #75: the nightly correlation snapshot's peak RSS grew
quadratically with universe size and no longer fits in host RAM.

- compute_corr_matrix now fills one preallocated N×N float32 corr matrix
  (plus an int16 overlap matrix) in row-block stripes: per-block masked-BLAS
  temporaries are O(block × N) instead of ~6 simultaneous N×N float32
  intermediates. Upper-triangle blocks are mirrored, so the result is
  exactly symmetric by construction (replacing the 0.5*(C + C.T) temp pass).
- overlap counts use the smallest dtype that fits T (int16 for daily
  lookbacks), halving the second output matrix.
- _corr_two_windows (lead-lag path) masks in place instead of allocating
  np.where + astype copies; shares the masked-BLAS core with the tiled path.
- top_k_neighbors: per-row abs instead of a full N×N |corr| copy, and
  argpartition instead of three full argsorts per row.
- hierarchical_clusters: distance transform in place + blockwise
  symmetrization (drops four full-size temporaries).
- correlation_refresh: pivots asyncpg records straight into the float32
  matrix on a worker thread and filters min_history_days on the matrix —
  the old long-form path materialised millions of intermediate Python
  tuples (multi-GB) and held them for the whole compute. Also fixes the
  accidental O(N²) symbols.index() loop when building PeerSet docs.

Verified old-vs-new on a synthetic 300-symbol universe: identical top-k
buckets, cluster partition and lead-lag sets; corr diff ≤ 2.4e-07.
Peak RSS at N=6000: 0.98 GB → 0.44 GB above baseline for the corr build;
new block temporaries no longer scale with N².

Lead-lag still materialises N×N per lag — candidate-pair restriction is
the follow-up PR.

Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01JRnthdVhGGt5FeSQ8m3aUA

gertjan added 1 commit 2026-07-07 09:16:36 +00:00

fix(analytics): screened lead-lag scan in O(block×N) memory + retire #75 stopgaps ... ddb3e6cb68

Phase 2+4 of #75. find_lead_lag_pairs no longer materialises any N×N
matrix (the old scan held ~5 persistent + ~8 transient at peak):

- A tiled screen sweeps each lag's improvement surface
  (|lagged_corr| − |sync_corr|) in row-blocks, keeping per-lag row/column
  top-k improvements. Any pair that can rank in a seed's final top
  k_leaders/k_laggers necessarily survives this screen, so the output is
  provably identical to the full N² scan (modulo rank-boundary ties,
  absorbed by a +8 screen margin) — verified exactly: 6497/6497 pairs,
  identical ordered lists, on a 300-symbol universe with injected
  pure-lag structure (20/20 recovered; a sync-correlation candidate
  screen was measured first and lost 13/20 — rejected).
- Surviving pairs (~10·k·N, not N²) are rescanned exactly across all
  lags with chunked elementwise correlation, and selection is a
  vectorised group-by — replacing the O(N²) Python double loop that
  alone cost ~40 min at N=24k.
- The dead lag_zero_overlap parameter is dropped; the int16 overlap
  matrix is now freed before the scipy clustering peak.

Benchmarked at N=6000 (full pipeline): peak RSS 1.95 → 1.23 GB,
lead-lag 215 → 112 s. Projected peak at N=24k ≈ 10–11 GB (clustering is
now the ceiling), within #75's <20 GB target through N≈35k.

Stopgap reverts per #75 acceptance criteria:
- correlation_refresh timeout 14400 → 5400 s
- analytics container mem_limit 48g → 24g, so a regression OOM-kills
  the container instead of the host kernel picking a victim

Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01JRnthdVhGGt5FeSQ8m3aUA

gertjan changed title from fix(analytics): tile correlation build to cut O(N²) peak memory (#75) to fix(analytics): O(block×N) correlation snapshot — tiled corr build + screened lead-lag (#75) 2026-07-07 09:17:12 +00:00

gertjan merged commit 197cc0f59f into main 2026-07-07 10:02:18 +00:00

gertjan deleted branch fix/correlation-tiled-memory 2026-07-07 10:02:19 +00:00

gertjan referenced this pull request from a commit 2026-07-07 10:02:21 +00:00

fix(analytics): O(block×N) correlation snapshot — tiled corr build + screened lead-lag (#75) (#76)

gertjan referenced this pull request 2026-07-07 10:02:41 +00:00

correlation_refresh: O(N²) peak memory exceeds host RAM at current universe size (~24k symbols) #75

gertjan referenced this pull request 2026-07-09 07:43:14 +00:00

correlation_refresh: O(N²) peak memory exceeds host RAM at current universe size (~24k symbols) #75

Sign in to join this conversation.

Reviewers

No reviewers

Labels

Clear labels   

bug

  

documentation

  

duplicate

  

enhancement

  

wontfix

No labels

bug

documentation

duplicate

enhancement

wontfix

Milestone

Clear milestone

No items

No milestone

Projects

Clear projects

No items

No project

Assignees

Clear assignees

No assignees

1 participant

Notifications

Subscribe

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference

gertjan/bodega!76

No description provided.