Barnes-Hut Attention over Lifelong User Histories

A recommender that has watched a user for years holds tens of thousands of past interactions. The user's tastes have drifted over that time. Some old interests are dead, and some come back. Full attention, the Transformer mechanism in which the current prediction looks at every past item, costs time and memory that grow with history length and is too expensive at this scale. Deployed systems therefore keep only the most similar past items, or squeeze the history into a fixed codebook. Both choices decide ahead of time which parts of the past will be seen at full resolution.

Computational physics faced the same problem decades ago with gravity. A distant galaxy can be treated as one point mass at its center, while nearby stars must be summed one by one. We propose to treat a user's history the same way. We organize past interactions into a tree ordered by time, in which each node caches the count, mean and covariance of the keys it covers. When a new query arrives, the tree is opened adaptively: a node is expanded into its children only when the query is sensitive to the spread inside it, and is otherwise summarized in closed form. The result is attention whose resolution follows the query. A recent burst of activity, or an old interest that the current query revives, is seen item by item, while stale and irrelevant eras collapse to a few summaries. Because the tree is ordered by time, new interactions only append to it, so it never has to be rebuilt as preferences drift.

Core Claim

Under a fixed compute budget, query-adaptive hierarchical summarization of a lifelong history keeps more of the attention mass that matters under preference drift than either retrieval truncation or query-independent quantization. The advantage should be concentrated on "revived" interests, meaning items whose category last appeared long ago. Both competitors are known to fail on that slice by construction: truncation drops the old evidence, and fixed codebooks merge it into codes that a later query cannot separate again.

The mechanism rests on one approximation. For a node $S$ with $n_S$ keys whose mean is $\mu_S$ and covariance is $\Sigma_S$, and a query vector $q$, the summed unnormalized attention weight is approximated by a second-order cluster summary:

$$\sum_{k \in S} e^{q^\top k} \approx n_S \, e^{q^\top \mu_S + \frac{1}{2} q^\top \Sigma_S q}.$$

This is exact when the keys in the node are Gaussian, and it reduces to the Barnes-Hut point-mass rule when $\Sigma_S = 0$. The node's value contribution is approximated by its cached mean value, with a first-order correction from the cached key-value cross-covariance. The opening criterion expands $S$ when $q^\top \Sigma_S q$ exceeds a tolerance $\tau$, because this term controls the next-order error of the expansion. Temporal drift enters as a learned bias $b(\Delta t_S)$ added to each node's log-weight, where $\Delta t_S$ is the node's age. This bias is a continuous-time decay in the spirit of SS4Rec, which ties a state-space model's step size to elapsed time. Here, however, the decay is applied per node rather than as a single recurrence, so an old node that is semantically close to the query can still be opened.

Relation to Prior Work

The method draws on the hierarchical-approximation line. Moore et al. introduced multiresolution k-d trees, whose nodes cache counts, centroids and covariances, and used them to prune all-pairs computations. They also document that such trees degrade badly once the space has more than 10 to 20 dimensions. That negative result constrains our design. Attention keys are typically 32 to 64 dimensional, so we do not partition key space. We partition the one-dimensional time axis, which never suffers from dimensionality, and we use key-space statistics only inside the opening test. Tree-Independent Dual-Tree Algorithms separates the tree, the traversal, the leaf computation and the pruning score into independent pieces. We adopt that separation directly: our pruning score is $q^\top \Sigma_S q$ plus the age bias, and the leaf computation is exact attention. When many queries are scored at once, for example over a candidate set, they can share traversal work in the dual-tree style. Barnes-Hut-SNE is the closest machine-learning precedent for using Barnes-Hut summarization inside a learned objective. It accelerates a fixed gradient in two or three dimensions; we accelerate a learned, high-dimensional softmax.

At the intersection itself, Raykar et al. cast pairwise ranking gradients as an N-body sum and reached linear time. Their preferences are static and their clustering is in input space, so they do not address drift or attention. VQL is the closest existing system. It quantizes keys into a learned codebook, keeps values uncompressed, adds a separable temporal kernel, and so achieves latency that does not depend on history length. Its compression is query-independent and fixed offline. Ours chooses resolution per query and carries an explicit error control, at the price of latency that depends on $\tau$. On the drift side, NS-DPO shows that exponential recency discounting rescues preference learning when preferences invert. It also exposes a limitation we target: every sample of the same age receives the same weight, so an enduring core value and a passing curiosity decay at the same rate. Our age bias is likewise uniform, but the opening test is not. An old node that the query strongly matches is kept at full resolution regardless of its age.

Research Program

We will build a time-ordered segment tree per user. Leaves hold blocks of 16 to 64 consecutive interactions, and internal nodes store mergeable statistics: count, key sum, key second moment, value sum, and key-value cross moment. Appending an interaction updates the $O(\log L)$ ancestors of its leaf, where $L$ is the history length, so the static-topology limitation noted for trees is avoided.

A user with several interleaved interests will have high key variance in every time node, and the tree would then open almost everywhere. To handle this, each node optionally stores a small mixture of $c$ key-space subclusters, with $c$ between 2 and 8, maintained by incremental merging. The opening test is then applied per subcluster. Whether $c>1$ is needed is an empirical question that we will measure directly.

Training is end to end. The summaries are differentiable functions of the keys, and $\tau$ is annealed from 0, which gives exact attention on truncated histories, up to the target budget. We will also analyze how the number of opened nodes grows with $L$ for users with stationary versus drifting interests. Our expectation is roughly logarithmic growth for stationary users, because far-past eras pass the test at high tree levels, and growth tied to the number of distinct revived interests for drifting users.

Baselines

The naive reference point is SASRec-style full attention over the most recent $n$ interactions, with $n$ set so that its compute matches our median per-query cost. This answers whether any long-range history helps at all.

The strongest existing method is VQL. It is designed for exactly this regime of histories longer than 5,000 items, and it already includes temporal decay. We will reimplement it with codebook sizes chosen so that its key storage and FLOPs match ours, using the same encoder, the same data splits and the same hyperparameter search budget. No VQL numbers on our benchmarks were present in the file, so we cannot quote a reported target: no reported result found on Lacuna for VQL on KuaiRand-1K, TMALL, or Amazon. We will treat our own matched reimplementation as the bar.

The second strong competitor is retrieval truncation in the style of SIM or TWIN: attend exactly to the top-$k$ past items by key similarity. This is the industrial default, and it is query-adaptive, which makes it the most direct test of whether summarizing the remainder adds anything. SS4Rec serves as the linear-cost continuous-time baseline. Its paper reports gains over SASRec, BERT4Rec and Mamba4Rec on HR@10, but the file gives no numerical values (no reported result found on Lacuna for SS4Rec HR@10 values).

Three ablations isolate the key ingredient. The first is a first-order version with $\Sigma_S$ dropped, which is plain Barnes-Hut. The second uses a fixed tree cut at a level chosen to match compute, which removes query adaptivity and is essentially a hierarchical analogue of VQL. The third removes the age bias, leaving geometry alone to handle drift. Beating a baseline means a statistically significant gain in NDCG@10 at matched FLOPs across five seeds, together with a larger gain on the revived-interest slice than on the overall test set.

Why not just…?

Why not just use top-$k$ retrieval over the history? Retrieval is query-adaptive and cheap, so it is the real threat. Its failure mode is that the softmax mass outside the top-$k$ is discarded entirely, and for diffuse interests that mass is large. Our proposal keeps that mass in summarized form. The experiment that settles the question compares, on histories short enough for exact attention, the fraction of exact attention output recovered by top-$k$ and by our tree at equal FLOPs. If top-$k$ matches us on both this fidelity measure and NDCG, the summaries are not worth their cost and we will report that.

Why not just use VQL's codebook? A codebook is shared and fixed, so two old interests that map to the same code cannot be separated by a later query. The tree can open a node and separate them. The fixed-cut ablation directly tests whether adaptivity, rather than hierarchy alone, produces the gain.

Why not just use a linear-time state-space model or exponential decay? SS4Rec and the NS-DPO-style discount compress the past into a recurrence or a uniform age weight. An interest that went dormant two years ago has then decayed regardless of what the current query is. We expect these methods to do well on overall metrics but poorly on the revived-interest slice. If they do not underperform there, the drift motivation for our design fails.

Proposed Experiments

We will use KuaiRand-1K and TMALL, which have long histories, and Amazon Sports and Video-Games, which have shorter histories and serve as a check that the method does no harm where history is short. The tasks are next-item prediction with HR@10 and NDCG@10, and click-through AUC on KuaiRand. We will also run a calibration check on KuaiRec's fully observed small matrix (KuaiRec). Its forced-exposure design removes the selection bias that, as that paper shows, makes model rankings unstable; we use it to confirm that orderings among the methods hold without exposure bias.

There are three decisive checks. The first is approximation fidelity: on histories with $L \le 2048$, measure the relative error of the attention output against exact attention as a function of $\tau$, and verify that the second-order summary dominates the first-order one at equal opened-node counts. The second is the drift slice: define revived-interest test events as targets whose category has been absent for more than a set fraction of the user's history, and compare all methods on those events. The third is scaling: report latency and opened-node count as $L$ grows from $10^3$ to $10^5$, in both stationary-user and drifting-user strata.

The proposal succeeds if it matches VQL overall, clearly beats it and top-$k$ retrieval on the revived-interest slice, and shows sublinear growth in opened nodes for stationary users. It fails if the variance test opens most nodes even with subclusters. That outcome would show that real interaction keys are too spread out for far-field summarization, and it would be informative in its own right.