Topology Survives Shuffling: Robust Long-Context Memory Access Prediction for Graph Analytics

Dongyan Sun, Neelesh Gupta, Rajgopal Kannan, Viktor K. PrasannaarXiv 2026 · arXiv

TL;DR

LoCoMAP is a new framework that uses long-context Transformer models to predict memory access patterns in graph analytics. By looking back at up to 128 previous accesses, it learns the underlying topology of a graph rather than just memorizing a specific memory layout, making it significantly more robust and accurate for data prefetching than existing short-context models.

What Problem Does This Paper Address?

Graph analytics (like PageRank or finding the shortest path) are notoriously "memory-bound." They spend most of their time waiting for data to arrive from RAM because their memory access patterns are irregular and "pointer-chasing" in nature (e.g., row[col[i]]).

Traditional hardware prefetchers, which look for simple linear strides, fail here. Recent Machine Learning (ML) prefetchers try to help, but they typically use very short history windows (fewer than 10 previous accesses). The authors argue that these short-context models don't actually learn the "graph-ness" of the data; instead, they just memorize the specific IDs of neighboring nodes in a particular trace. If you shuffle the node IDs or change the memory layout, these models collapse. LoCoMAP aims to fix this by using long-context representations to capture structural patterns like hubs, communities, and clusters that persist even when the layout changes.

Methods

The authors propose LoCoMAP (Long-Context Memory Access Prediction), a Transformer-based architecture designed to decouple three key parameters:

  1. Look-back length ($L$): How much history the model observes.
  2. Look-forward window ($W$): How far into the future it predicts.
  3. Delta range ($D$): The spatial scope of the address offsets it can predict.
Fig. 1. Graph Topologies of Synthetic Network Models.

Unlike standard models, LoCoMAP treats memory addresses as segmented features and uses self-attention to relate every access in a long history (up to $L=128$) to every other access. It outputs a "multi-hot" bitmap, meaning a single inference can predict multiple future addresses simultaneously, which is ideal for the branching nature of graph traversals.

Datasets

The study uses a rigorous two-pronged evaluation:

  • Synthetic Graphs: Six families that represent different structural extremes, from purely random (Erdős–Rényi) and scale-free (Barabási–Albert) to highly regular spatial grids.
  • Real-World Graphs: Six diverse datasets, including the FlyWire connectome, Google web graph, and road networks (roadCA).

These were tested across three standard workloads from the GAP benchmark suite: Connected Components (CC), PageRank (PR), and Single-Source Shortest Paths (SSSP).

Visualization of the six synthetic graph topologies used to test structural learning.

Key Insights and Ideas

  • Topology Survives Shuffling: The core "aha!" moment is that while shuffling node IDs destroys memory locality, it preserves the graph's connectivity (topology). A model that remains accurate after a 100% node shuffle has successfully learned the graph's structural "prior."
  • The Long-Context Advantage: Short-context models ($L=8$) are "layout-bound"—they fail when the neighborhood mapping changes. Long-context models ($L=128$) are "topology-bound"—they can see enough of the history to recognize structural patterns (like a burst of accesses within a community) regardless of the specific IDs.
  • Workload Sensitivity: Not all algorithms benefit equally. PageRank is highly predictable because it's a systematic sweep. SSSP is much harder because its access order is determined by data-dependent distances, which change drastically when nodes are relabeled.
  • The Horizon Matters More: While increasing history ($L$) helps, increasing the prediction horizon ($W$) provides a massive boost to the F1 score (up to 88.3%), as it allows the model to convert long-range predictive signals into actual cache hits.

Key Results

  • Accuracy Gains: Increasing history from 8 to 128 accesses improved F1 scores by 7.8% on average, while extending the prediction horizon to 512 accesses improved F1 by 88.3%.
  • Robustness: On fully shuffled Stochastic Block Model (SBM) graphs, LoCoMAP achieved a 2.06× improvement in F1 score over short-context baselines.
  • Real-World Performance: On six real-world graphs under full shuffle, the long-context model outperformed short-context models in every case, with a 10.2% mean improvement.
  • Cost-Benefit: While $L=128$ is computationally expensive ($21\times$ more FLOPs), the authors found that $L=64$ often captures most of the accuracy benefits at a significantly lower cost.
The computational cost (latency and FLOPs) increases quadratically with look-back length L.

Limitations and Future Work

The primary limitation is the inference latency of Transformers. In the world of hardware prefetching, decisions must be made in nanoseconds. While LoCoMAP proves that long context is valuable, the current quadratic cost of self-attention is a hurdle for on-chip implementation.

The authors suggest that future work should explore subquadratic architectures (like linear attention or state-space models like Mamba) and model compression techniques to bring these long-context benefits into real-time hardware prefetchers. Additionally, SSSP remains a challenge, suggesting a need for models that can better handle highly dynamic, data-dependent traversal orders.

Summary updated

Abstract

Graph analytics generates irregular, topology-dependent memory-access streams via indirect traversals, limiting data prefetching. Accurate prediction enables timely prefetches that hide memory latency. However, ML predictors couple short histories with fixed horizons, fitting the training trace's node layout rather than learning transferable graph patterns. We propose LoCoMAP, a long-context representation-learning framework for memory-access prediction with independently controlled observation history and prediction horizon. We evaluate Connected Components (CC), PageRank (PR), and Single-Source Shortest Paths (SSSP) on six synthetic graph families, with Erdos-Renyi (ER) and Grid as random and deterministic controls. We test two interventions: same-family regeneration changes connectivity, while node shuffling disrupts layout but preserves connectivity. Across 18 graph-workload pairs, extending history from 8 to 128 accesses improves F1 by 7.8%, while extending prediction horizon from 8 to 512 improves F1 by 88.3%. For CC, regeneration is less disruptive than shuffling: without retraining, long context retains 95.4% of original F1 and outperforms short context in six families. Under full shuffle, long context improves CC F1 by 33.6% across ER, Barabasi-Albert, Copying Model, and Stochastic Block Model (SBM), with a 2.06x gain on SBM, but not on Watts-Strogatz or Grid, where near-zero delta mass shifts into heavy tails beyond the predictor's range. Long context outperforms short context on six real-world CC graphs. At full shuffle, long-context PR retains 57.6% of original F1 and averages 11.0% above short context. Both SSSP models retain about 30% of original F1 under full shuffle as distance updates access vertex data in a new order. Within these bounds, long-context predictors are robust across related graphs and layouts without retraining, enabling a generalizable graph prefetcher.
BibTeX
@misc{sun2026topology,
  author = {Dongyan Sun and Neelesh Gupta and Rajgopal Kannan and Viktor K. Prasanna},
  title = {{Topology Survives Shuffling: Robust Long-Context Memory Access Prediction for Graph Analytics}},
  year = {2026},
  eprint = {2610.39477},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.39477},
}
Figure