Research map / Architectures and efficiency / RNNs and normalization
Determinant Estimation under Memory Constraints and Neural Scaling Laws
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MEMDET, an out-of-core block LDL/LU log-determinant algorithm, and FLODANCE, which extrapolates NTK log-determinants from small subsamples using neural scaling laws for successive determinant ratios.
Problem
Computing log-determinants of huge, ill-conditioned dense kernel matrices (e.g., empirical NTK Gram matrices) is cubic in cost and memory-prohibitive, so exact baselines are unavailable and approximations like SLQ are inaccurate.
Approach
A memory-constrained hierarchical block LU/LDL/Cholesky algorithm (MEMDET) gives exact log-determinants out-of-core; and the ratio of successive pseudo-determinants is assumed to follow a power law tied to GP prediction error, so log-determinants can be extrapolated from a small subsample via linear regression (FLODANCE).
Key results
- FLODANCE with n_s=5000 and q=4 estimates the 500000x500000 ResNet50 NTK log-determinant with 0.02% relative error, roughly 1000x less computation than exact.
- In the 1000-point CIFAR-10 setting, FLODANCE with burn-in (n0=300, n_s=500) achieves 1.34% error for ResNet9 versus 3.67% for 32-bit direct computation and 81.51% for SLQ.
- SLQ yields 55% relative error on the full 500000x500000 ResNet50 NTK, at about $83 cost versus $601 for exact MEMDET.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FLODANCE with n_s=5000 and q=4 instead of SLQ | ResNet50 NTK log-determinant estimation · CIFAR-10, n=50000 | relative error: 55% -> 0.02% | Helped |
| Increase FLODANCE sample size and correction order from n_s=500, q=0 to n_s=5000, q=4 (ablation) | FLODANCE · CIFAR-10 ResNet50 NTK, n=50000 | relative error: 4% -> 0.02% | Helped |
| Use a burn-in and larger fitting interval (n_0=300, n_s=500) instead of n_0=1, n_s=100 (ablation) | FLODANCE · CIFAR-10 ResNet9 NTK, n=1000 and n=2500 | relative error: 5.61% (0.32) -> 1.34% (0.11); 8.54% (0.63) -> 1.37% (0.14) | Helped |
| Use a burn-in and larger fitting interval (n_0=300, n_s=500) instead of n_0=1, n_s=100 (ablation) | FLODANCE · CIFAR-10 ResNet18 NTK, n=1000 | relative error: 8.09% (0.68) -> 2.9% (0.81) | Helped |
| Use a burn-in and larger fitting interval (n_0=300, n_s=500) instead of n_0=1, n_s=100 (ablation) | FLODANCE · MNIST MobileNet NTK, n=2500 | relative error: 35.51% (1.46) -> 23.19% (1.76) | Helped |
| Increase the FLODANCE fitting sample size from n_s=50 to n_s=100 without burn-in (ablation) | FLODANCE · CIFAR-10 ResNet9 NTK, n=1000 and n=2500 | relative error: 7.75% (0.77) -> 5.61% (0.32); 11.27% (1.10) -> 8.54% (0.63) | Helped |
| Increase the FLODANCE fitting sample size from n_s=50 to n_s=100 without burn-in (ablation) | FLODANCE · CIFAR-10 ResNet18 NTK, n=1000 | relative error: 12.19% (0.30) -> 8.09% (0.68) | Helped |
| Increase the FLODANCE fitting sample size from n_s=50 to n_s=100 without burn-in (ablation) | FLODANCE · MNIST MobileNet NTK, n=2500 | relative error: 36.41% (2.53) -> 35.51% (1.46) | Helped |
| Use FLODANCE instead of direct 32-bit computation | NTK log-determinant estimation · CIFAR-10 ResNet9, n=1000 and n=2500; ResNet18, n=1000 | relative error: 3.67% -> 1.34%; 6.77% -> 1.37%; 5.25% -> 2.9% | Helped |
| Use FLODANCE instead of direct 32-bit computation | NTK log-determinant estimation · MNIST MobileNet, n=2500 | relative error: 14.27% -> 23.19% | Hurt |
Surprising findings
- Extrapolating from a small subsample via scaling laws was more accurate than 32-bit mixed-precision direct computation at the tested scales.
- Forming the NTK in low precision (16/32-bit) and computing the determinant can incur large errors because the Gram matrix is near-singular (condition number above 1e12).
Limitations
- Burn-in period needed for accurate fits, with an unexplained sudden emergence of small eigenvalues.
- Relies on an assumed power-law scaling of successive determinant ratios; the error in this assumption is not fully characterized theoretically.
- Exact baseline for the largest matrices required 244 hours on a GH200 GPU, making verification expensive.
Experimental setup
Datasets: CIFAR-10 MNIST
Benchmarks: CIFAR-10 NTK log-determinant MNIST NTK log-determinant
Metrics: relative error of log-determinant wall time estimated cost
Baselines: stochastic Lanczos quadrature block-diagonal NTK approximation pseudo-NTK 16-bit direct computation 32-bit direct computation
Builds on: neural tangent kernel stochastic Lanczos quadrature Gaussian process error curves
Closest papers by meaning
- Spectral Estimation with Free Decompression (NeurIPS 2025 · similarity 0.86)
- Convergence Analysis of Newton's Method for Neural Networks in the Overparameterized Limit (NeurIPS 2026 · similarity 0.84)
- Free Decompression with Algebraic Spectral Curves (NeurIPS 2026 · similarity 0.84)
- The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks (NeurIPS 2025 · similarity 0.84)
- Analyzing Neural Scaling Laws in Two-Layer Networks with Power-Law Data Spectra (ICLR 2025 · similarity 0.84)
- Learning from higher-order correlations, efficiently: hypothesis tests, random features, and neural networks (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.