Pointer: Linear-Complexity Long-Range Modeling without Pre-training

Authors: Zixi Li, Noesis Lab · Sun Yat-sen University
Date: 5 August 2025
Paper: arXiv:2508.02631v1

---

Abstract

We introduce Pointer, a novel sequence model that attains linear $O(NK)O(NK)$ complexity by replacing quadratic self-attention with layer-wise pointer chains. Pointer reaches 2–10× speed-ups on long sequences, keeps >95% accuracy on copy tasks up to 2,048 tokens, and learns interpretable long-range patterns – all without any large-scale pre-training.

---

Key Contributions

• Linear complexity: $O(NK)O(NK)$ runtime yields 2–10× faster training/inference
• No pre-training required: Effective from scratch on modest hardware
• Explicit long-range modeling: Pointer chains create $2^K+2^K+$ token dependency paths
• Interpretability: Each token points to exactly one other token

---

Method in a Nutshell

Pointer Selection

For position $ii$ at layer $\mathrm{\ell }\backslash ell$, choose a single target:
$$p_i^{(\mathrm{\ell })}=\arg \underset{j}{\max }{s}_{ij}^{(\mathrm{\ell })}p\_i^\{(\backslash ell)\}\; =\; \backslash arg\backslash max\_j\; s\_\{ij\}^\{(\backslash ell)\}$$
where $ss$ are learned pointer logits.

Pointer Chaining

Re-embed previous layer's pointer index into token representations. Deeper layers form multi-hop chains spanning longer ranges.

Complexity

• Compute cost: $O(Nd)O(Nd)$ per layer
• Memory: $O(N)O(N)$ (vs. $O(N^2)O(N^2)$ for attention)

---

Experiments

Throughput (tokens/sec):

→ Speed-up grows from 0.48× (256 tokens) to 2.45× (2,048 tokens)

Copy-Task Accuracy:

→ Maintains >95% accuracy at 2,048 tokens

---

Interpretability

Heatmaps reveal layer specialization:

• Early layers: Local (\(\sim\)47–58 tokens)
• Deep layers: Long-range jumps (\(\leq\)483 tokens)

---

Limitations & Future Work

• Hardware constraints for Longformer comparisons
• Currently language-only; cross-domain tests planned
• Future: Multi-head pointers, hierarchical chains

---

TL;DR

Pointer replaces quadratic attention with layer-wise pointer chains—achieving:

• $O(NK)O(NK)$ linear complexity
• 2–10× speed-up on long sequences
• Interpretable dependency paths
• No pre-training required
  Try it for long-context tasks on modest hardware!