Research map / Learning theory and algorithms / Matrix and tensor methods
Metric Transforms and Low Rank Representations of Kernels for Fast Attention
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.
Uses representation theory of the hyperrectangle to classify which entrywise functions preserve low rank (only polynomials among piecewise continuous functions), classify positive definite Manhattan kernels, and classify Manhattan-to-Manhattan metric transforms.
Problem
Which functions f, applied entrywise to low-rank matrices (e.g., QK^T in attention), keep them low rank; and which kernels and metric transforms involving Manhattan (l1) distance can be characterized fully?
Approach
A new linear-algebraic tool: the kernel matrix of hyperrectangle vertices under Manhattan distance has Hadamard eigenvectors for any entrywise f, so eigenvalues have closed forms in terms of f's finite differences. This yields converses to the polynomial method, full classification of Manhattan positive definite kernels (completely monotone), and of Manhattan-to-Manhattan transforms (Bernstein fun
Key results
- Theorem 2.5: any piecewise continuous f preserving low-rank n x n matrices is a polynomial of degree at most ceil(log2 n).
- Theorem 4.4: f transforms Manhattan to Manhattan iff f is Bernstein, equivalently Manhattan to squared Euclidean.
- Positive definite Manhattan kernels are exactly the completely monotone functions f(x) (no square root, unlike the Euclidean case f(sqrt x)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace a low-degree polynomial with a non-polynomial function without essential discontinuities of the first kind | entry-wise transforms of low-rank matrices · low-rank n × n matrices | low-rank preservation | Hurt |
Surprising findings
- Functions like x^c for non-integer c do not preserve low rank but do preserve stable rank for matrices with entries in [1, O(log n)].
Limitations
- Constant-factor gap between polynomial degree sufficient (about log2(n)/2) and necessary (log2(n))
- Stable-rank results not yet usable for sublinear-time attention algorithms
- Analysis focuses on theory for LLMs, kernels, and metric transforms without experiments
Experimental setup
Metrics: rank preservation positive definiteness stable rank bounds
Baselines: Guillot, Khare, and Rajaratnam 2017 (GKR17) Assouad 1980
Builds on: polynomial method in algorithm design Schoenberg classification Guillot-Khare-Rajaratnam converse
Closest papers by meaning
- How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation (ICLR 2024 · similarity 0.85)
- Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions (ICLR 2025 · similarity 0.85)
- Random features for Grassmannian kernel approximation with bounded rank-one projections (NeurIPS 2026 · similarity 0.84)
- LevAttention: Time, Space and Streaming Efficient Algorithm for Heavy Attentions (ICLR 2025 · similarity 0.84)
- Sparse Attention as Compact Kernel Regression (NeurIPS 2026 · similarity 0.84)
- Mind the Gap: a Spectral Analysis of Rank Collapse and Signal Propagation in Attention Layers (ICML 2025 · similarity 0.83)
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.