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:
- Look-back length ($L$): How much history the model observes.
- Look-forward window ($W$): How far into the future it predicts.
- Delta range ($D$): The spatial scope of the address offsets it can predict.
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).
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.
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