SANSA approximates a linear recommender with sparse factors. After fitting, those factors map a user’s interaction history to item scores.

I moved some of SANSA’s sorting work to a smaller set of entries and cached residual columns that had not changed. Together with changes to temporary storage, this made fitting about 2× faster on the two datasets I measured, with less peak memory and the same weights, bit for bit.

The two changes have different traps. Sorting fewer entries is safe only if discarded candidates still contribute to the diagonal update. Reusing a residual column is safe only while its input column stays unchanged.

Sort what survives

In SANSA’s incomplete Cholesky factorization, a column can produce more candidates than the fill budget allows it to keep. The budget limits the entries stored in the factor; it does not mean every intermediate candidate can be ignored.

Only the retained entries need to be sorted before they are written into the factor, so I moved the sorting work to that smaller set.

Discarded candidates still contribute to the diagonal update. I kept that contribution while moving the sort. The retained entries arrive in the order the factor needs, and the diagonal still accounts for the candidates that were dropped.

Remember what changed

UMR, which refines a sparse approximate inverse, repeatedly needs a residual:

R = I - A @ M

A is the fixed matrix being approximately inverted; M is its current sparse approximate inverse. With A fixed, each column of A @ M depends on just the corresponding column of M:

R[:, j] = I[:, j] - A @ M[:, j]

If column j of M changes, column j of R needs refreshing. An unchanged column of M still gives the same residual. There is no reason to repeat its matrix product.

I added a cache scoped to a single fit. It tracks changes from substitution and pruning, then recomputes dirty columns using fresh matrix products. In the toy six-column example below, changing two columns leaves four available for reuse.

residual / six columns2 refreshed
two changed columns refreshed; four unchanged columns reused.

Reusing an unchanged column is different from incrementally updating a changed one. The cache does not accumulate residual updates: it calculates each dirty column again. A residual_cache=False switch allows comparison with full recomputation. The UMR commit has the implementation.

Use less temporary storage

Scaling a sparse matrix used to create a temporary coefficient buffer as large as its nonzero entries. A direct pass through its compressed storage avoids that allocation.

Prescaling needs exact Gram-column norms, but collecting them does not require holding the full sparse Gram at once. It now computes the norms in panels of 256 columns. The full sparse Gram still gets built when factorization needs it; the change removes the need to hold it just for the earlier norm calculation. The ICF commit describes that change.

What I measured

These are the fit results reported in the PR, using the full datasets, matched parameters, and 16 CPU threads:

Dataset Fit speedup Peak RAM reduction
Amazon Books · L3AE release 2.04× 18%
Yambda-50M Like 2.04× 17%

The resulting weights matched bitwise in both runs. The PR also includes checks for cached versus uncached fits, index widths, empty rows, and tied recommendation scores.

There are other changes in the branch: an explicit SciPy/MKL backend, sparse top-k selection, and the scikit-sparse 0.5 API migration. The larger scoring speedups reported in the PR combine execution paths, including a backend change; they are separate from the fit results above.

The work is in a draft PR on my SANSA fork.