How do I install the Log Linear Sparse Attention skill?

Run npx skillmds@latest add adu2021/log-linear-sparse-attention in your terminal (requires Node.js), paste this page's agent-chat prompt into Claude, Cursor, or any MCP-connected agent, or download the SKILL.md file and copy it into your agent's skills directory.

Is Log Linear Sparse Attention safe to use?

This skill has not completed SkillMD's automated safety review yet. SkillMD never runs a skill's scripts for you; review the SKILL.md before installing.

Which AI agents work with Log Linear Sparse Attention?

This skill is tagged as working with Claude Code, Claude.ai, OpenAI Codex. SKILL.md is an open format, so most agents that read a skills directory can load it too.

Is Log Linear Sparse Attention free to use?

Yes. Installing skills from SkillMD is free. This skill is licensed under MIT.

Who published Log Linear Sparse Attention?

adu2021 (@adu2021) published this skill. Their other Agent Skills are listed on their SkillMD profile.

Log Linear Sparse Attention by adu2021

Name: Log Linear Sparse Attention
Author: adu2021

Log Linear Sparse Attention

Reduce self-attention complexity from O(N²) to O(N log N) through hierarchical token selection and enrichment. Perform hierarchical Top-K selection progressively adopting sparse Top-K at each level. Implement sparse index transpose algorithm avoiding dense mask construction. Achieve 28.27× faster inference and 6.09× faster training.

adu2021 f446d91 3.3 KB Updated Sep 17, 2026

File contents

Skill Summary

This work introduces Log-linear Sparse Attention (LLSA), a trainable mechanism that reduces self-attention complexity from quadratic O(N²) to log-linear O(N log N) for Diffusion Transformers. The approach performs hierarchical compression through progressive Top-K selection, adopts sparse indices at each hierarchy level, and incorporates coarse representations from multiple levels. An efficient GPU implementation develops a sparse index transpose algorithm operating directly on sparse indices for both forward and backward passes, eliminating expensive dense mask construction. Results show 28.27× faster inference and 6.09× faster training on 256×256 pixel sequences while maintaining generation quality.

When To Use

Accelerating diffusion transformer inference for image/video generation
Scenarios where sequence length creates O(N²) attention bottleneck
Projects with limited compute budget for generation
Research on sparse attention mechanisms for transformers

When NOT To Use

Short sequences already efficient with full attention
Applications where sparse approximation introduces artifacts
Domains requiring full attention interactions between all tokens
Scenarios where sparse overhead isn't justified by sequence length

Core Technique

Two key components enable log-linear attention:

1. Hierarchical Compression and Selection Rather than single-level token selection, perform "hierarchical Top-K selection, progressively adopting sparse Top-K selection with the indices found at the previous level." This multi-scale approach enables:

Efficient long-range token selection
Reduced total selected tokens while maintaining context
Progressive refinement across hierarchy levels

2. Hierarchical KV Enrichment "Preserve global context while using fewer tokens of different granularity during attention computation" by incorporating coarse representations from multiple hierarchy levels. This enables modeling tokens at different levels of abstraction simultaneously.

3. Efficient GPU Implementation Develop sparse index transpose algorithm "operating directly on sparse indices" for both forward and backward passes. This eliminates expensive dense mask construction that would negate sparsity benefits.

Practical Results

256×256 pixel sequences:
- Inference speedup: 28.27×
- Training speedup: 6.09×
Smaller K values than competing methods
Generation quality maintained comparable to full attention

Implementation Notes

Implement hierarchical Top-K selection operating progressively across hierarchy levels. Add hierarchical KV enrichment incorporating multi-scale context. Implement efficient GPU kernel for sparse index operations avoiding dense masks. Validate inference and training speedups on your sequence lengths.

References

Original paper: Trainable Log-linear Sparse Attention (Dec 2025)
Sparse attention mechanisms
Diffusion transformer architectures

---name: log-linear-sparse-attentiondescription: Reduce self-attention complexity from O(N²) to O(N log N) through hierarchical token selection and enrichment. Perform hierarchical Top-K selection progressively adopting sparse Top-K at each level. Implement sparse index transpose algorithm avoiding dense mask construction. Achieve 28.27× faster inference and 6.09× faster training.license: MIT---## Skill SummaryThis work introduces Log-linear Sparse Attention (LLSA), a trainable mechanism that reduces self-attention complexity from quadratic O(N²) to log-linear O(N log N) for Diffusion Transformers. The approach performs hierarchical compression through progressive Top-K selection, adopts sparse indices at each hierarchy level, and incorporates coarse representations from multiple levels. An efficient GPU implementation develops a sparse index transpose algorithm operating directly on sparse indices for both forward and backward passes, eliminating expensive dense mask construction. Results show 28.27× faster inference and 6.09× faster training on 256×256 pixel sequences while maintaining generation quality.## When To Use- Accelerating diffusion transformer inference for image/video generation- Scenarios where sequence length creates O(N²) attention bottleneck- Projects with limited compute budget for generation- Research on sparse attention mechanisms for transformers## When NOT To Use- Short sequences already efficient with full attention- Applications where sparse approximation introduces artifacts- Domains requiring full attention interactions between all tokens- Scenarios where sparse overhead isn't justified by sequence length## Core TechniqueTwo key components enable log-linear attention:**1. Hierarchical Compression and Selection**Rather than single-level token selection, perform "hierarchical Top-K selection, progressively adopting sparse Top-K selection with the indices found at the previous level." This multi-scale approach enables:- Efficient long-range token selection- Reduced total selected tokens while maintaining context- Progressive refinement across hierarchy levels**2. Hierarchical KV Enrichment**"Preserve global context while using fewer tokens of different granularity during attention computation" by incorporating coarse representations from multiple hierarchy levels. This enables modeling tokens at different levels of abstraction simultaneously.**3. Efficient GPU Implementation**Develop sparse index transpose algorithm "operating directly on sparse indices" for both forward and backward passes. This eliminates expensive dense mask construction that would negate sparsity benefits.## Practical Results- 256×256 pixel sequences: - Inference speedup: 28.27× - Training speedup: 6.09×- Smaller K values than competing methods- Generation quality maintained comparable to full attention## Implementation NotesImplement hierarchical Top-K selection operating progressively across hierarchy levels. Add hierarchical KV enrichment incorporating multi-scale context. Implement efficient GPU kernel for sparse index operations avoiding dense masks. Validate inference and training speedups on your sequence lengths.## References- Original paper: Trainable Log-linear Sparse Attention (Dec 2025)- Sparse attention mechanisms- Diffusion transformer architectures

Frequently asked questions