Determinant Estimation under Memory Constraints and Neural Scaling Laws

Siavash Ameli, Chris van der Heide, Liam Hodgkinson, Fred Roosta, Michael W. Mahoney

Calculating the log-determinant of a massive matrix is one of those notoriously "ugly" problems in machine learning. It is computationally expensive ($O(n^3)$), but more importantly, it hits the "memory wall." If you were working with a dataset like ImageNet-1k, the resulting Neural Tangent Kernel (NTK) matrix would require roughly 13 exabytes of storage—more than the total capacity of CERN’s data centers.

A new paper, "Determinant Estimation under Memory Constraints and Neural Scaling Laws," presents a clever two-pronged solution to this problem, combining high-performance systems engineering with the theoretical elegance of neural scaling laws.

TL;DR

The authors introduce MEMDET, an out-of-core algorithm that computes exact log-determinants by intelligently swapping matrix blocks between RAM and disk, and FLODANCE, an extrapolation method that uses neural scaling laws to estimate determinants with a 100,000x speedup. Together, these tools allowed the researchers to compute the first-ever exact log-determinant for a full-scale empirical NTK on 50,000 datapoints.

What Problem Does This Paper Address?

Log-determinants are essential for training Gaussian Processes (GPs), performing Bayesian model selection, and understanding the generalization of deep neural networks. However, as datasets grow, we face two major hurdles:

  1. The Memory Wall: Dense matrices for modern datasets simply do not fit in RAM.
  2. Ill-Conditioning: These matrices (especially NTKs) are often "pathological"—they have extremely small eigenvalues that make standard approximation methods, like stochastic Lanczos quadrature (SLQ), highly inaccurate.

Previously, researchers often avoided these calculations entirely or relied on small subsets of data, which introduces significant bias.

Methods

The authors tackle the problem from two distinct directions: brute-force engineering and elegant extrapolation.

1. MEMDET (The "Brute Force" Engineer)

To establish a ground-truth baseline, the authors developed MEMDET. It is a hierarchical, block-wise algorithm for LU, LDL, and Cholesky decompositions.

Block-wise matrix traversal in MEMDET
  • How it works: It partitions a massive matrix into small blocks. It only keeps a few blocks in RAM at a time, performing computations and then writing results back to disk (out-of-core processing).
  • The Innovation: It uses a specific processing order (based on Hamiltonian paths in a line graph) to minimize the number of times data must be read from or written to disk, significantly reducing I/O overhead.

2. FLODANCE (The "Elegant" Extrapolator)

While MEMDET is exact, it is still slow for massive scales. FLODANCE (Factorial-based Log-Determinant Analysis and Numerical Curve Estimation) changes the game.

Power-law scaling of determinant ratios
  • The Insight: The authors proved a link between the error curves of Gaussian Processes and the ratio of successive determinants. Since GP errors follow "power laws" (scaling laws), the log-determinant should too.
  • The Algorithm: By calculating the log-determinants of a tiny fraction of the data (using MEMDET), FLODANCE fits a Laurent series to the scaling curve and extrapolates the value for the full dataset.

Datasets

The researchers evaluated their methods on:

  • CIFAR-10: Using ResNet9, ResNet18, and ResNet50 architectures.
  • MNIST: Using MobileNet.
  • Synthetic Data: Multi-output Gaussian Processes with Matérn kernels.
  • Scale: They successfully processed dense matrices up to 500,000 x 500,000, a size previously considered intractable for exact computation.

Key Insights and Ideas

  • The Power Law Connection: The most striking "aha moment" is that the ratio of pseudo-determinants satisfies a power-law relationship. This means the geometry of the data manifold is reflected in how the determinant grows as you add more points.
  • Accuracy vs. Precision: Surprisingly, the authors found that extrapolating via FLODANCE can be more accurate than performing an exact computation in lower numerical precision (like 16-bit or 32-bit floats). In highly ill-conditioned matrices, rounding errors in low-precision arithmetic accumulate so badly that a scaling-law estimate is more reliable.
  • Memory is the Real Bottleneck: While much research focuses on reducing $O(n^3)$ time complexity, this paper argues that for modern ML, the storage of the matrix itself is the primary barrier to entry.

Key Results

  • Massive Speedup: FLODANCE achieved a ~100,000x speedup compared to exact methods while maintaining a relative error of just 0.02% for a ResNet50 NTK.
  • Superior Accuracy: Compared to the current state-of-the-art approximation (SLQ), which had a relative error of 55% on certain tasks, FLODANCE remained consistently accurate.
  • New Benchmarks: Using an NVIDIA Grace Hopper GH200, the authors ran MEMDET for 244 hours to provide the first-ever exact log-determinant for a full NTK on CIFAR-10, providing a vital benchmark for the community.

Limitations and Future Work

  • Burn-in Period: The scaling laws only become stable after a certain number of datapoints (the "burn-in" phase). For very small datasets or specific architectures, the extrapolation might be less reliable.
  • Kernel Specificity: While the paper demonstrates success on NTKs and Matérn kernels, further work is needed to see how these scaling laws hold up for more exotic or non-stationary kernels.
  • Spectral Information: The authors suggest that future work could extend these techniques to extrapolate more than just the determinant—potentially the entire eigenvalue spectrum of the matrix.

The authors have released their work as a high-performance Python package called detkit, making these "impenetrable" calculations accessible to the broader research community.

Summary updated

Abstract

Calculating or accurately estimating log-determinants of large positive definite matrices is of fundamental importance in many machine learning tasks. While its cubic computational complexity can already be prohibitive, in modern applications, even storing the matrices themselves can pose a memory bottleneck. To address this, we derive a novel hierarchical algorithm based on block-wise computation of the LDL decomposition for large-scale log-determinant calculation in memory-constrained settings. In extreme cases where matrices are highly ill-conditioned, accurately computing the full matrix itself may be infeasible. This is particularly relevant when considering kernel matrices at scale, including the empirical Neural Tangent Kernel (NTK) of neural networks trained on large datasets. Under the assumption of neural scaling laws in the test error, we show that the ratio of pseudo-determinants satisfies a power-law relationship, allowing us to derive corresponding scaling laws. This enables accurate estimation of NTK log-determinants from a tiny fraction of the full dataset; in our experiments, this results in a $\sim$100,000$\times$ speedup with improved accuracy over competing approximations. Using these techniques, we successfully estimate log-determinants for dense matrices of extreme sizes, which were previously deemed intractable and inaccessible due to their enormous scale and computational demands.
BibTeX
@inproceedings{ameli2025determinant,
  author = {Siavash Ameli and Chris van der Heide and Liam Hodgkinson and Fred Roosta and Michael W. Mahoney},
  title = {{Determinant Estimation under Memory Constraints and Neural Scaling Laws}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=nkV9PPp8R8},
}
Figure