Research map / Architectures and efficiency / Attention and transformers
Proxyformer: Nyström-Based Linear Transformer with Trainable Proxy Tokens
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Proxyformer, a Nyström-based linear-complexity transformer that replaces sampled landmarks with trainable proxy tokens, trained with a contrastive landmark loss, an input injection module, and a column-wise dropout on the decomposed attention matrix.
Problem
Self-attention is quadratic in sequence length; Nyström-based efficient transformers (Nyströmformer) pick redundant landmarks by pooling input tokens and need costly pseudo-inverse computation.
Approach
Use trainable proxy tokens as Nyström landmarks, pass proxy outputs to the next layer, enforce landmark diversity with a contrastive loss (which makes the landmark matrix near identity so no pseudo-inverse is needed), inject input context via a Patch-Merger-style cross-attention, and apply column dropout on the K2 factor.
Key results
- Proxyformer-128 reaches 59.43 average LRA accuracy, versus 58.63 for Nyströmformer-128 and 58.77 for the standard Transformer.
- At sequence length 4096, Proxyformer reduces memory by 92% and increases throughput 3.8x relative to the standard Transformer.
- Contrastive loss and decomposed dropout together raise average test accuracy by about 0.6 points in the ablation (58.7 to 59.4).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use trainable proxy tokens with contrastive loss and input injection instead of sampled landmarks | Nyström-based self-attention · LRA average | accuracy: 58.63 -> 59.43 | Helped |
| use trainable proxy tokens with contrastive loss and input injection instead of sampled landmarks | Nyström-based self-attention · LRA 4096 sequence length | throughput | No clear effect |
| add contrastive loss to proxy-token training (ablation) | Proxyformer · LRA average | accuracy: 58.7 -> 58.9 | Helped |
| use decomposed dropout instead of no dropout (ablation) | Proxyformer · LRA average | accuracy: 58.7 -> 59.2 | Helped |
| replace decomposed dropout with normal dropout on K1 (ablation) | Proxyformer · LRA average | accuracy: 58.7 -> 58.8 | No clear effect |
| replace decomposed dropout with normal dropout on K2 (ablation) | Proxyformer · LRA average | accuracy: 58.7 -> 58.4 | Hurt |
| add contrastive loss to decomposed dropout (ablation) | Proxyformer · LRA average | accuracy: 59.2 -> 59.3 | Helped |
| add the input injection module (ablation) | Proxyformer with decomposed dropout and contrastive loss · LRA average | accuracy: 59.3 -> 59.4 | Helped |
Surprising findings
- Orthoformer's orthogonal landmark selection gives higher accuracy than Nyströmformer but has runtime overhead that makes its throughput fall below the standard Transformer.
Limitations
- Evaluated only on LRA with a small two-layer model; no pretraining or large-scale experiments.
- Proxy-token initialization for fine-tuning pretrained models is left unresolved.
Experimental setup
Datasets: Long Range Arena
Benchmarks: Long Range Arena
Metrics: classification accuracy memory footprint throughput (samples/sec) average cosine similarity between landmarks
Baselines: Standard Transformer Reformer Linformer Performer Nyströmformer Set Transformer BigBird Orthoformer Luna
Builds on: Nyströmformer Orthoformer Set Transformer Luna SupContrast Patch Merger
Closest papers by meaning
- MemoryFormer : Minimize Transformer Computation by Removing Fully-Connected Layers (NeurIPS 2024 · similarity 0.84)
- Linear Transformers Implicitly Discover Unified Numerical Algorithms (NeurIPS 2025 · similarity 0.84)
- XAttention: Block Sparse Attention with Antidiagonal Scoring (ICML 2025 · similarity 0.84)
- RelFlexformer: Efficient Attention Transformers for Integrable Relative Positional Encodings (NeurIPS 2026 · similarity 0.84)
- Token Statistics Transformer: Linear-Time Attention via Variational Rate Reduction (ICLR 2025 · similarity 0.84)
- PolySketchFormer: Fast Transformers via Sketching Polynomial Kernels (ICML 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.