# Hierarchical Polynomial Kernel Attention

- ID: 2583
- Canonical URL: https://synthcore.org/idea/2583/hierarchical-polynomial-kernel-attention
- API JSON: https://synthcore.org/api/idea/2583.json
- API Markdown: https://synthcore.org/api/idea/2583.md
- Verification status: unverified
- Source: [arXiv:2608.19702](https://arxiv.org/abs/2608.19702)
- Category: attention
- Solves: speedup, memory, scalability
- ML areas: attention, graph-nn, inference-speedup, memory
- Math tags: approximation-theory, linear-algebra, numerical-analysis, graph-theory
- Ratings: usefulness 6/10; difficulty 6/10; novelty 6/10

## Idea description

Construct a sparse attention variant whose positional interaction kernel is piecewise polynomial rather than an arbitrary softmax score. Store key-value content in exact monomial moments within a spatial or learned-coordinate box hierarchy, then evaluate all queries from those moments without materializing the query-by-key matrix.

## Mathematical statement

The construction uses the paper's local polynomial closure. Let $K(q,k)$ be a compactly supported positional kernel, and assume that on every box pair selected by the hierarchy it has the finite expansion $K(q,k)=\sum_{\boldsymbol{i},\boldsymbol{j}}c_{\boldsymbol{i},\boldsymbol{j}}(\omega_q,\omega_k)q^{\boldsymbol{i}}k^{\boldsymbol{j}}$, where $q,k\in\mathbb{R}^d$, $q^{\boldsymbol{i}}=\prod_rq_r^{i_r}$, and $0\le i_r,j_r\le p$. For value vectors $v_s\in\mathbb{R}^C$, aggregate key moments $S_{\boldsymbol{j},c}(\omega)=\sum_{s:k_s\in\omega}k_s^{\boldsymbol{j}}v_{s,c}$ and normalization moments $Z_{\boldsymbol{j}}(\omega)=\sum_{s:k_s\in\omega}k_s^{\boldsymbol{j}}$. The unnormalized output is $u_c(q)=\sum_{\boldsymbol{i},\boldsymbol{j}}q^{\boldsymbol{i}}c_{\boldsymbol{i},\boldsymbol{j}}S_{\boldsymbol{j},c}$, and normalized attention is $u_c(q)/(\sum_{\boldsymbol{i},\boldsymbol{j}}q^{\boldsymbol{i}}c_{\boldsymbol{i},\boldsymbol{j}}Z_{\boldsymbol{j}}+\epsilon)$. This is exact for the selected polynomial kernel and replaces explicit pairwise interactions by moment accumulation and polynomial evaluation. A sparse hierarchy restricts each query to boxes intersecting the kernel support, while parent moments allow a larger support without visiting every key.

## Key formulas

- $$K(q,k)=\sum_{\boldsymbol{i},\boldsymbol{j}\in\{0,\ldots,p\}^{d}}c_{\boldsymbol{i},\boldsymbol{j}}(\omega_q,\omega_k)q^{\boldsymbol{i}}k^{\boldsymbol{j}},\qquad q^{\boldsymbol{i}}=\prod_{r=1}^{d}q_r^{i_r}.$$
- $$S_{\boldsymbol{j},c}(\omega)=\sum_{s:k_s\in\omega}k_s^{\boldsymbol{j}}v_{s,c},\qquad Z_{\boldsymbol{j}}(\omega)=\sum_{s:k_s\in\omega}k_s^{\boldsymbol{j}}.$$
- $$u_c(q)=\sum_{\boldsymbol{i},\boldsymbol{j}}q^{\boldsymbol{i}}c_{\boldsymbol{i},\boldsymbol{j}}S_{\boldsymbol{j},c},\qquad y_c(q)=\frac{u_c(q)}{\displaystyle\sum_{\boldsymbol{i},\boldsymbol{j}}q^{\boldsymbol{i}}c_{\boldsymbol{i},\boldsymbol{j}}Z_{\boldsymbol{j}}+\epsilon}.$$
- $$\mathcal{O}(p^d(N+Q))\quad\text{instead of}\quad\mathcal{O}(NQ).$$

## Implementation notes

Modify a local-attention block in a point-cloud transformer, neural operator, or spatial world model. First map each key and query coordinate to normalized box coordinates and use a compact-support piecewise-polynomial kernel such as a tensor-product linear or quadratic B-spline. Do not initially learn arbitrary coefficients: precompute the kernel expansion coefficients $c_{\boldsymbol{i},\boldsymbol{j}}$ for each relative box configuration. For each occupied key box, accumulate $S_{\boldsymbol{j},c}$ from key coordinates and value vectors, and accumulate scalar $Z_{\boldsymbol{j}}$; build parent-box moments by summing children. For each query, traverse only boxes intersecting the kernel support, evaluate $q^{\boldsymbol{i}}$, contract with the stored moments, and divide by the corresponding normalization plus $\epsilon$. Add a learned channel projection before moment accumulation and after evaluation, so the block retains trainable content mixing. The formulas provide the exact finite contraction; determine empirically the box depth, support radius, polynomial degree, and whether direct key iteration is cheaper for boxes below a threshold. Begin with a 2D sparse-image or point-cloud classification task using 4,096 keys and 4,096 queries, comparing against radius attention and linear attention at equal hidden width. First verify numerical equivalence to direct polynomial-kernel attention, then measure GPU memory, throughput, and accuracy. Test uniform and highly clustered keys. The target signal is at least 2x lower attention memory and 1.5x higher throughput with no accuracy loss; clustered inputs should particularly favor the hierarchy because aggregation cost depends on occupied boxes and moments rather than all query-key pairs.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.