Skip to main content

trustformers_models/
sparse_attention.rs

1//! Sparse Attention Patterns Library
2//!
3//! This module provides efficient sparse attention implementations that reduce
4//! the quadratic complexity of standard attention mechanisms. Sparse attention
5//! patterns are particularly useful for long sequences and memory-constrained
6//! scenarios.
7//!
8//! # Overview
9//!
10//! The library includes several sparse attention patterns:
11//!
12//! - **Local Attention**: Attention restricted to local windows
13//! - **Strided Attention**: Attention with fixed stride patterns
14//! - **Dilated Attention**: Attention with increasing dilation factors
15//! - **Random Attention**: Attention with random sparse patterns
16//! - **Block Sparse Attention**: Attention using block-wise sparsity (BigBird style)
17//! - **Longformer Attention**: Sliding window + global attention
18//! - **Linformer Attention**: Low-rank projection for linear complexity
19//! - **Reformer Attention**: LSH-based attention for efficient similarity search
20//!
21//! # Example
22//!
23//! ```
24//! use trustformers_models::sparse_attention::{SparseAttention, SparseAttentionConfig, SparsePattern};
25//! use trustformers_core::tensor::Tensor;
26//! use trustformers_core::traits::Layer;
27//! use trustformers_core::layers::AttentionInput;
28//!
29//! # fn main() -> Result<(), Box<dyn std::error::Error>> {
30//! // Create sparse attention with local window pattern
31//! let config = SparseAttentionConfig::new()
32//!     .with_pattern(SparsePattern::Local { window_size: 64 })
33//!     .with_hidden_size(768)
34//!     .with_num_heads(12);
35//!
36//! let attention = SparseAttention::new(config)?;
37//! let input = Tensor::randn(&[8, 768])?; // 2D: [seq_len, hidden_size]
38//! let output = attention.forward(AttentionInput::new(input))?;
39//! # let _ = output;
40//! # Ok(())
41//! # }
42//! ```
43
44use scirs2_core::Array2; // SciRS2 Integration Policy
45use std::collections::HashMap;
46use trustformers_core::errors::{tensor_op_error, Result};
47use trustformers_core::layers::AttentionInput;
48use trustformers_core::tensor::Tensor;
49use trustformers_core::traits::Layer;
50
51/// Deterministic generator for the LSH random rotations.
52///
53/// A SplitMix64 stream turned into standard normals with the Box–Muller
54/// transform. Seeded rather than drawn from entropy so that two identical
55/// forward passes hash to identical buckets: an attention pattern that varied
56/// run to run would make inference non-reproducible, which is worse than any
57/// benefit from fresh randomness.
58struct LshRng {
59    state: u64,
60    spare: Option<f32>,
61}
62
63impl LshRng {
64    fn new(seed: u64) -> Self {
65        Self {
66            state: seed | 1,
67            spare: None,
68        }
69    }
70
71    /// SplitMix64 step, uniformly distributed over `u64`.
72    fn next_u64(&mut self) -> u64 {
73        self.state = self.state.wrapping_add(0x9E37_79B9_7F4A_7C15);
74        let mut z = self.state;
75        z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
76        z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
77        z ^ (z >> 31)
78    }
79
80    /// Uniform in the open interval `(0, 1)`.
81    fn next_open_unit(&mut self) -> f32 {
82        // Shift into the 24-bit mantissa range and keep it strictly positive so
83        // `ln()` never sees zero.
84        let bits = (self.next_u64() >> 40) as f32; // [0, 2^24)
85        (bits + 0.5) / 16_777_216.0
86    }
87
88    /// Standard normal via Box–Muller, caching the second variate.
89    fn next_gaussian(&mut self) -> f32 {
90        if let Some(value) = self.spare.take() {
91            return value;
92        }
93        let u1 = self.next_open_unit();
94        let u2 = self.next_open_unit();
95        let radius = (-2.0 * u1.ln()).sqrt();
96        let angle = 2.0 * std::f32::consts::PI * u2;
97        self.spare = Some(radius * angle.sin());
98        radius * angle.cos()
99    }
100}
101
102/// Configuration for sparse attention patterns
103#[derive(Debug, Clone)]
104pub struct SparseAttentionConfig {
105    pub hidden_size: usize,
106    pub num_heads: usize,
107    pub dropout_prob: f32,
108    pub pattern: SparsePattern,
109    pub max_sequence_length: usize,
110    pub block_size: usize,
111    pub use_cache: bool,
112    pub attention_scale: Option<f32>,
113}
114
115impl Default for SparseAttentionConfig {
116    fn default() -> Self {
117        Self::new()
118    }
119}
120
121impl SparseAttentionConfig {
122    pub fn new() -> Self {
123        Self {
124            hidden_size: 768,
125            num_heads: 12,
126            dropout_prob: 0.1,
127            pattern: SparsePattern::Local { window_size: 128 },
128            max_sequence_length: 4096,
129            block_size: 64,
130            use_cache: true,
131            attention_scale: None,
132        }
133    }
134
135    pub fn with_pattern(mut self, pattern: SparsePattern) -> Self {
136        self.pattern = pattern;
137        self
138    }
139
140    pub fn with_hidden_size(mut self, hidden_size: usize) -> Self {
141        self.hidden_size = hidden_size;
142        self
143    }
144
145    pub fn with_num_heads(mut self, num_heads: usize) -> Self {
146        self.num_heads = num_heads;
147        self
148    }
149
150    pub fn with_dropout(mut self, dropout_prob: f32) -> Self {
151        self.dropout_prob = dropout_prob;
152        self
153    }
154
155    pub fn with_max_length(mut self, max_sequence_length: usize) -> Self {
156        self.max_sequence_length = max_sequence_length;
157        self
158    }
159
160    pub fn with_block_size(mut self, block_size: usize) -> Self {
161        self.block_size = block_size;
162        self
163    }
164}
165
166/// Sparse attention pattern types
167#[derive(Debug, Clone)]
168pub enum SparsePattern {
169    /// Local sliding window attention
170    Local { window_size: usize },
171    /// Strided attention with fixed stride
172    Strided { stride: usize, window_size: usize },
173    /// Dilated attention with increasing dilation
174    Dilated {
175        max_dilation: usize,
176        window_size: usize,
177    },
178    /// Random sparse attention
179    Random { sparsity_ratio: f32 },
180    /// Block sparse attention (BigBird style)
181    BlockSparse {
182        block_size: usize,
183        global_blocks: usize,
184        random_blocks: usize,
185    },
186    /// Longformer-style attention (sliding window + global)
187    Longformer {
188        window_size: usize,
189        global_tokens: Vec<usize>,
190    },
191    /// Linformer-style linear attention
192    Linformer { projection_dim: usize },
193    /// Reformer-style LSH attention
194    Reformer {
195        num_hashes: usize,
196        bucket_size: usize,
197    },
198    /// Custom sparse pattern with explicit mask
199    Custom { mask: SparseAttentionMask },
200}
201
202/// Sparse attention mask representation
203#[derive(Debug, Clone)]
204pub struct SparseAttentionMask {
205    pub indices: Vec<(usize, usize)>, // (row, col) pairs for non-zero entries
206    pub values: Vec<f32>,             // Values for non-zero entries
207    pub shape: (usize, usize),        // (seq_len, seq_len)
208}
209
210impl SparseAttentionMask {
211    pub fn new(shape: (usize, usize)) -> Self {
212        Self {
213            indices: Vec::new(),
214            values: Vec::new(),
215            shape,
216        }
217    }
218
219    pub fn add_entry(&mut self, row: usize, col: usize, value: f32) {
220        if row < self.shape.0 && col < self.shape.1 {
221            self.indices.push((row, col));
222            self.values.push(value);
223        }
224    }
225
226    pub fn to_dense(&self) -> Vec<Vec<f32>> {
227        let mut dense = vec![vec![f32::NEG_INFINITY; self.shape.1]; self.shape.0];
228        for (i, &(row, col)) in self.indices.iter().enumerate() {
229            dense[row][col] = self.values[i];
230        }
231        dense
232    }
233
234    pub fn sparsity(&self) -> f32 {
235        let total_elements = self.shape.0 * self.shape.1;
236        let nonzero_elements = self.indices.len();
237        1.0 - (nonzero_elements as f32 / total_elements as f32)
238    }
239}
240
241/// Main sparse attention implementation
242#[derive(Debug, Clone)]
243pub struct SparseAttention {
244    config: SparseAttentionConfig,
245    query_projection: trustformers_core::layers::Linear,
246    key_projection: trustformers_core::layers::Linear,
247    value_projection: trustformers_core::layers::Linear,
248    output_projection: trustformers_core::layers::Linear,
249    #[allow(dead_code)]
250    head_dim: usize,
251    scale: f32,
252    #[allow(dead_code)]
253    mask_cache: HashMap<usize, SparseAttentionMask>,
254}
255
256impl SparseAttention {
257    pub fn new(config: SparseAttentionConfig) -> Result<Self> {
258        let head_dim = config.hidden_size / config.num_heads;
259        let scale = config.attention_scale.unwrap_or(1.0 / (head_dim as f32).sqrt());
260
261        Ok(Self {
262            query_projection: trustformers_core::layers::Linear::new(
263                config.hidden_size,
264                config.hidden_size,
265                false,
266            ),
267            key_projection: trustformers_core::layers::Linear::new(
268                config.hidden_size,
269                config.hidden_size,
270                false,
271            ),
272            value_projection: trustformers_core::layers::Linear::new(
273                config.hidden_size,
274                config.hidden_size,
275                false,
276            ),
277            output_projection: trustformers_core::layers::Linear::new(
278                config.hidden_size,
279                config.hidden_size,
280                false,
281            ),
282            head_dim,
283            scale,
284            mask_cache: HashMap::new(),
285            config,
286        })
287    }
288
289    /// Generate sparse attention mask based on the configured pattern
290    pub fn generate_mask(&self, sequence_length: usize) -> Result<SparseAttentionMask> {
291        match &self.config.pattern {
292            SparsePattern::Local { window_size } => {
293                self.generate_local_mask(sequence_length, *window_size)
294            },
295            SparsePattern::Strided {
296                stride,
297                window_size,
298            } => self.generate_strided_mask(sequence_length, *stride, *window_size),
299            SparsePattern::Dilated {
300                max_dilation,
301                window_size,
302            } => self.generate_dilated_mask(sequence_length, *max_dilation, *window_size),
303            SparsePattern::Random { sparsity_ratio } => {
304                self.generate_random_mask(sequence_length, *sparsity_ratio)
305            },
306            SparsePattern::BlockSparse {
307                block_size,
308                global_blocks,
309                random_blocks,
310            } => self.generate_block_sparse_mask(
311                sequence_length,
312                *block_size,
313                *global_blocks,
314                *random_blocks,
315            ),
316            SparsePattern::Longformer {
317                window_size,
318                global_tokens,
319            } => self.generate_longformer_mask(sequence_length, *window_size, global_tokens),
320            SparsePattern::Linformer { projection_dim } => {
321                self.generate_linformer_mask(sequence_length, *projection_dim)
322            },
323            SparsePattern::Reformer {
324                num_hashes,
325                bucket_size,
326            } => self.generate_reformer_mask(sequence_length, *num_hashes, *bucket_size),
327            SparsePattern::Custom { mask } => Ok(mask.clone()),
328        }
329    }
330
331    fn generate_local_mask(
332        &self,
333        seq_len: usize,
334        window_size: usize,
335    ) -> Result<SparseAttentionMask> {
336        let mut mask = SparseAttentionMask::new((seq_len, seq_len));
337
338        for i in 0..seq_len {
339            let start = i.saturating_sub(window_size / 2);
340            let end = (i + window_size / 2 + 1).min(seq_len);
341
342            for j in start..end {
343                mask.add_entry(i, j, 0.0);
344            }
345        }
346
347        Ok(mask)
348    }
349
350    fn generate_strided_mask(
351        &self,
352        seq_len: usize,
353        stride: usize,
354        window_size: usize,
355    ) -> Result<SparseAttentionMask> {
356        let mut mask = SparseAttentionMask::new((seq_len, seq_len));
357
358        for i in 0..seq_len {
359            // Local window
360            let start = i.saturating_sub(window_size / 2);
361            let end = (i + window_size / 2 + 1).min(seq_len);
362
363            for j in start..end {
364                mask.add_entry(i, j, 0.0);
365            }
366
367            // Strided connections
368            let mut pos = i;
369            while pos < seq_len {
370                mask.add_entry(i, pos, 0.0);
371                pos += stride;
372            }
373
374            if i >= stride {
375                let mut pos = i - stride;
376                loop {
377                    mask.add_entry(i, pos, 0.0);
378                    if pos < stride {
379                        break;
380                    }
381                    pos -= stride;
382                }
383            }
384        }
385
386        Ok(mask)
387    }
388
389    fn generate_dilated_mask(
390        &self,
391        seq_len: usize,
392        max_dilation: usize,
393        window_size: usize,
394    ) -> Result<SparseAttentionMask> {
395        let mut mask = SparseAttentionMask::new((seq_len, seq_len));
396
397        for i in 0..seq_len {
398            for dilation in 1..=max_dilation {
399                let start = i.saturating_sub(window_size * dilation / 2);
400                let end = (i + window_size * dilation / 2 + 1).min(seq_len);
401
402                for j in (start..end).step_by(dilation) {
403                    mask.add_entry(i, j, 0.0);
404                }
405            }
406        }
407
408        Ok(mask)
409    }
410
411    fn generate_random_mask(
412        &self,
413        seq_len: usize,
414        sparsity_ratio: f32,
415    ) -> Result<SparseAttentionMask> {
416        let mut mask = SparseAttentionMask::new((seq_len, seq_len));
417        let total_elements = seq_len * seq_len;
418        let keep_elements = (total_elements as f32 * (1.0 - sparsity_ratio)) as usize;
419
420        // Simple random selection (in real implementation, use proper RNG)
421        let mut added = 0;
422        for i in 0..seq_len {
423            for j in 0..seq_len {
424                if added < keep_elements && (i + j) % 3 == 0 {
425                    // Simple pseudo-random
426                    mask.add_entry(i, j, 0.0);
427                    added += 1;
428                }
429            }
430        }
431
432        Ok(mask)
433    }
434
435    fn generate_block_sparse_mask(
436        &self,
437        seq_len: usize,
438        block_size: usize,
439        global_blocks: usize,
440        random_blocks: usize,
441    ) -> Result<SparseAttentionMask> {
442        let mut mask = SparseAttentionMask::new((seq_len, seq_len));
443        let num_blocks = seq_len.div_ceil(block_size);
444
445        for block_i in 0..num_blocks {
446            let start_i = block_i * block_size;
447            let end_i = (start_i + block_size).min(seq_len);
448
449            for block_j in 0..num_blocks {
450                let start_j = block_j * block_size;
451                let end_j = (start_j + block_size).min(seq_len);
452
453                // Local blocks (diagonal)
454                if block_i == block_j || block_i.abs_diff(block_j) <= 1 {
455                    for i in start_i..end_i {
456                        for j in start_j..end_j {
457                            mask.add_entry(i, j, 0.0);
458                        }
459                    }
460                }
461
462                // Global blocks
463                if block_j < global_blocks || block_i < global_blocks {
464                    for i in start_i..end_i {
465                        for j in start_j..end_j {
466                            mask.add_entry(i, j, 0.0);
467                        }
468                    }
469                }
470
471                // Random blocks (simplified)
472                if (block_i + block_j) % (num_blocks / random_blocks.max(1)) == 0 {
473                    for i in start_i..end_i {
474                        for j in start_j..end_j {
475                            mask.add_entry(i, j, 0.0);
476                        }
477                    }
478                }
479            }
480        }
481
482        Ok(mask)
483    }
484
485    fn generate_longformer_mask(
486        &self,
487        seq_len: usize,
488        window_size: usize,
489        global_tokens: &[usize],
490    ) -> Result<SparseAttentionMask> {
491        let mut mask = SparseAttentionMask::new((seq_len, seq_len));
492
493        // Local sliding window
494        for i in 0..seq_len {
495            let start = i.saturating_sub(window_size / 2);
496            let end = (i + window_size / 2 + 1).min(seq_len);
497
498            for j in start..end {
499                mask.add_entry(i, j, 0.0);
500            }
501        }
502
503        // Global tokens can attend to all positions
504        for &global_token in global_tokens {
505            if global_token < seq_len {
506                for j in 0..seq_len {
507                    mask.add_entry(global_token, j, 0.0);
508                    mask.add_entry(j, global_token, 0.0);
509                }
510            }
511        }
512
513        Ok(mask)
514    }
515
516    fn generate_linformer_mask(
517        &self,
518        seq_len: usize,
519        projection_dim: usize,
520    ) -> Result<SparseAttentionMask> {
521        // Linformer uses low-rank projections, so we create a full mask
522        // but mark it for special handling in the attention computation
523        let mut mask = SparseAttentionMask::new((seq_len, projection_dim));
524
525        for i in 0..seq_len {
526            for j in 0..projection_dim {
527                mask.add_entry(i, j, 0.0);
528            }
529        }
530
531        Ok(mask)
532    }
533
534    /// Reformer LSH mask for a sequence whose query vectors are not available.
535    ///
536    /// The whole point of Reformer's attention (Kitaev et al., 2020, §3) is that
537    /// buckets are determined by the *content* of the query vectors, via
538    /// locality-sensitive hashing: only tokens whose queries point in a similar
539    /// direction end up in the same bucket. That information does not exist at
540    /// mask-generation time, so this entry point reports the fact rather than
541    /// producing something that looks like an LSH mask but is not one.
542    ///
543    /// A previous revision produced a mask here by chunking positions into
544    /// fixed `bucket_size` blocks and keeping pair `(i, j)` when
545    /// `((i + hash_idx) % seq_len) / bucket_size == bucket` — arithmetic on token
546    /// *indices*, with no hash, no random projection, and no reference to any
547    /// query vector. Two tokens with identical queries at distant positions were
548    /// never bucketed together, and two orthogonal queries at adjacent positions
549    /// always were; the `num_hashes` parameter only shifted the block boundaries.
550    /// That is chunked local attention wearing Reformer's name.
551    ///
552    /// Use [`SparseAttention::generate_lsh_mask`] with the projected queries to
553    /// get the real pattern; the layer's `forward` does exactly that.
554    ///
555    /// # Errors
556    ///
557    /// Always fails: an LSH mask cannot be derived from a sequence length alone.
558    fn generate_reformer_mask(
559        &self,
560        seq_len: usize,
561        num_hashes: usize,
562        bucket_size: usize,
563    ) -> Result<SparseAttentionMask> {
564        Err(tensor_op_error(
565            "SparseAttention::generate_mask",
566            format!(
567                "Reformer LSH attention (num_hashes={num_hashes}, bucket_size={bucket_size}) \
568                 hashes the query vectors, so a mask cannot be built from the sequence length \
569                 ({seq_len}) alone. Call `generate_lsh_mask(&queries, ...)` — which \
570                 `SparseAttention::forward` does automatically — or pick a position-based \
571                 pattern such as `SparsePattern::BlockSparse`."
572            ),
573        ))
574    }
575
576    /// Real LSH bucketing of query vectors (Reformer, Kitaev et al. 2020 §3).
577    ///
578    /// # Algorithm
579    ///
580    /// Angular LSH by random rotation. For each of `num_hashes` independent
581    /// rounds:
582    ///
583    /// 1. Draw a random projection matrix `R` of shape `[head_dim, n_buckets/2]`
584    ///    and compute `p = q · R` for every query.
585    /// 2. Concatenate `p` with `−p`, giving `n_buckets` signed projections, and
586    ///    take the **argmax**. Two queries pointing in a similar direction
587    ///    maximise the same rotation with high probability, and the probability
588    ///    of a collision falls off with the angle between them — which is the
589    ///    locality-sensitive property the whole scheme rests on.
590    /// 3. Sort the positions by `(bucket, position)` and cut the sorted order
591    ///    into chunks of `bucket_size`. Attention is computed within each chunk
592    ///    and with the previous chunk, so a bucket that straddles a chunk
593    ///    boundary is not silently truncated.
594    ///
595    /// The projections are drawn from a **seeded, deterministic** generator, so
596    /// the same queries always produce the same mask: an attention pattern that
597    /// changed between two identical forward passes would make inference
598    /// non-reproducible.
599    ///
600    /// # Errors
601    ///
602    /// Fails when `queries` is not a 2-D `F32` tensor, when `bucket_size` is 0,
603    /// or when the head dimension is 0.
604    pub fn generate_lsh_mask(
605        &self,
606        queries: &Tensor,
607        num_hashes: usize,
608        bucket_size: usize,
609    ) -> Result<SparseAttentionMask> {
610        if bucket_size == 0 {
611            return Err(tensor_op_error(
612                "SparseAttention::generate_lsh_mask",
613                "bucket_size must be greater than 0".to_string(),
614            ));
615        }
616        if num_hashes == 0 {
617            return Err(tensor_op_error(
618                "SparseAttention::generate_lsh_mask",
619                "num_hashes must be greater than 0; with no hash rounds no token is bucketed \
620                 with any other"
621                    .to_string(),
622            ));
623        }
624        let Tensor::F32(q) = queries else {
625            return Err(tensor_op_error(
626                "SparseAttention::generate_lsh_mask",
627                "LSH bucketing requires an F32 query tensor".to_string(),
628            ));
629        };
630        let shape = q.shape();
631        if shape.len() != 2 {
632            return Err(tensor_op_error(
633                "SparseAttention::generate_lsh_mask",
634                format!("queries must be [seq_len, head_dim], got shape {shape:?}"),
635            ));
636        }
637        let (seq_len, head_dim) = (shape[0], shape[1]);
638        if seq_len == 0 || head_dim == 0 {
639            return Err(tensor_op_error(
640                "SparseAttention::generate_lsh_mask",
641                format!("cannot hash an empty query tensor with shape {shape:?}"),
642            ));
643        }
644
645        // Round the bucket count up to an even number: the ±projection trick
646        // needs `n_buckets / 2` rotations.
647        let n_buckets = seq_len.div_ceil(bucket_size).max(2);
648        let half_buckets = n_buckets.div_ceil(2);
649
650        // Deterministic projections. A fixed seed keeps inference reproducible;
651        // each hash round gets its own stream so the rounds are independent.
652        let mut pairs: std::collections::BTreeSet<(usize, usize)> =
653            std::collections::BTreeSet::new();
654
655        for round in 0..num_hashes {
656            let mut rng = LshRng::new(
657                0x5245_464F_524D_4552 ^ (round as u64).wrapping_mul(0x9E37_79B9_7F4A_7C15),
658            );
659            // [head_dim, half_buckets] random Gaussian projection.
660            let mut rotations = vec![0.0f32; head_dim * half_buckets];
661            for value in rotations.iter_mut() {
662                *value = rng.next_gaussian();
663            }
664
665            // Bucket each query by argmax over the signed projections.
666            let mut buckets = vec![0usize; seq_len];
667            for (t, bucket) in buckets.iter_mut().enumerate() {
668                let mut best_index = 0usize;
669                let mut best_value = f32::NEG_INFINITY;
670                for r in 0..half_buckets {
671                    let mut projection = 0.0f32;
672                    for d in 0..head_dim {
673                        projection += q[[t, d]] * rotations[d * half_buckets + r];
674                    }
675                    // +projection is rotation `r`, -projection is `r + half`.
676                    if projection > best_value {
677                        best_value = projection;
678                        best_index = r;
679                    }
680                    let negated = -projection;
681                    if negated > best_value {
682                        best_value = negated;
683                        best_index = r + half_buckets;
684                    }
685                }
686                *bucket = best_index;
687            }
688
689            // Sort positions by (bucket, position) and chunk the sorted order.
690            let mut order: Vec<usize> = (0..seq_len).collect();
691            order.sort_by_key(|&t| (buckets[t], t));
692
693            let num_chunks = seq_len.div_ceil(bucket_size);
694            for chunk in 0..num_chunks {
695                let start = chunk * bucket_size;
696                let end = (start + bucket_size).min(seq_len);
697                // Queries attend within their own chunk and to the previous one,
698                // so a bucket split across the boundary keeps its neighbours.
699                let context_start = start.saturating_sub(bucket_size);
700                for &i in &order[start..end] {
701                    for &j in &order[context_start..end] {
702                        // Only pairs that actually share a bucket are kept; the
703                        // previous-chunk window widens the candidate set, it does
704                        // not admit unrelated tokens.
705                        if buckets[i] == buckets[j] {
706                            pairs.insert((i, j));
707                        }
708                    }
709                }
710            }
711        }
712
713        let mut mask = SparseAttentionMask::new((seq_len, seq_len));
714        for (row, col) in pairs {
715            mask.add_entry(row, col, 0.0);
716        }
717        Ok(mask)
718    }
719
720    /// Apply sparse attention mask to attention scores
721    #[allow(dead_code)]
722    fn apply_sparse_mask(
723        &self,
724        attention_scores: &Tensor,
725        mask: &SparseAttentionMask,
726    ) -> Result<Tensor> {
727        match attention_scores {
728            Tensor::F32(scores) => {
729                let mut masked_scores = scores.clone();
730                let shape = scores.shape();
731
732                if shape.len() != 2 {
733                    return Err(tensor_op_error(
734                        "tensor_operation",
735                        "Attention scores must be 2D for sparse masking".to_string(),
736                    ));
737                }
738
739                // Set all positions to -inf initially
740                masked_scores.fill(f32::NEG_INFINITY);
741
742                // Apply sparse mask
743                for &(row, col) in mask.indices.iter() {
744                    if row < shape[0] && col < shape[1] {
745                        masked_scores[[row, col]] = scores[[row, col]];
746                    }
747                }
748
749                Ok(Tensor::F32(masked_scores))
750            },
751            _ => Err(tensor_op_error(
752                "tensor_operation",
753                "Unsupported tensor type for sparse attention".to_string(),
754            )),
755        }
756    }
757
758    /// Compute sparse attention efficiently
759    fn compute_sparse_attention(
760        &self,
761        query: &Tensor,
762        key: &Tensor,
763        value: &Tensor,
764        mask: &SparseAttentionMask,
765    ) -> Result<Tensor> {
766        // For sparse attention, we only compute attention for the sparse positions
767        // This is a simplified implementation - in practice, this would use
768        // specialized sparse matrix operations
769
770        // Compute attention scores only for sparse positions
771        let attention_scores = self.compute_sparse_scores(query, key, mask)?;
772
773        // Apply softmax to sparse scores
774        let attention_weights = attention_scores.softmax(-1)?;
775
776        // Apply attention weights to values
777        self.apply_sparse_attention_weights(&attention_weights, value, mask)
778    }
779
780    fn compute_sparse_scores(
781        &self,
782        query: &Tensor,
783        key: &Tensor,
784        mask: &SparseAttentionMask,
785    ) -> Result<Tensor> {
786        // Simplified sparse score computation
787        // In practice, this would use efficient sparse matrix operations
788        match (query, key) {
789            (Tensor::F32(q), Tensor::F32(k)) => {
790                let q_shape = q.shape();
791                let k_shape = k.shape();
792
793                if q_shape.len() != 2 || k_shape.len() != 2 {
794                    return Err(tensor_op_error(
795                        "tensor_operation",
796                        "Query and key must be 2D".to_string(),
797                    ));
798                }
799
800                let seq_len = q_shape[0];
801                let head_dim = q_shape[1];
802
803                let mut scores = Array2::from_elem((seq_len, seq_len), f32::NEG_INFINITY);
804
805                // Compute scores only for sparse positions
806                for &(i, j) in &mask.indices {
807                    if i < seq_len && j < seq_len {
808                        let mut score = 0.0;
809                        for d in 0..head_dim {
810                            score += q[[i, d]] * k[[j, d]];
811                        }
812                        scores[[i, j]] = score * self.scale;
813                    }
814                }
815
816                Ok(Tensor::F32(scores.into_dyn()))
817            },
818            _ => Err(tensor_op_error(
819                "tensor_operation",
820                "Unsupported tensor types for sparse attention".to_string(),
821            )),
822        }
823    }
824
825    fn apply_sparse_attention_weights(
826        &self,
827        weights: &Tensor,
828        value: &Tensor,
829        mask: &SparseAttentionMask,
830    ) -> Result<Tensor> {
831        match (weights, value) {
832            (Tensor::F32(w), Tensor::F32(v)) => {
833                let w_shape = w.shape();
834                let v_shape = v.shape();
835
836                let seq_len = w_shape[0];
837                let head_dim = v_shape[1];
838
839                let mut output = Array2::zeros((seq_len, head_dim));
840
841                // Apply sparse attention weights
842                for &(i, j) in &mask.indices {
843                    if i < seq_len && j < seq_len {
844                        let weight = w[[i, j]];
845                        if weight != f32::NEG_INFINITY && !weight.is_nan() {
846                            for d in 0..head_dim {
847                                output[[i, d]] += weight * v[[j, d]];
848                            }
849                        }
850                    }
851                }
852
853                Ok(Tensor::F32(output.into_dyn()))
854            },
855            _ => Err(tensor_op_error(
856                "tensor_operation",
857                "Unsupported tensor types for sparse attention output".to_string(),
858            )),
859        }
860    }
861}
862
863impl Layer for SparseAttention {
864    type Input = AttentionInput;
865    type Output = Tensor;
866
867    fn forward(&self, input: Self::Input) -> Result<Self::Output> {
868        let AttentionInput {
869            hidden_states,
870            attention_mask: _,
871        } = input;
872
873        // Project to Q, K, V
874        let query = self.query_projection.forward(hidden_states.clone())?;
875        let key = self.key_projection.forward(hidden_states.clone())?;
876        let value = self.value_projection.forward(hidden_states)?;
877
878        // Get sequence length
879        let seq_len = match &query {
880            Tensor::F32(q) => q.shape()[0],
881            _ => {
882                return Err(tensor_op_error(
883                    "tensor_operation",
884                    "Unsupported tensor type".to_string(),
885                ))
886            },
887        };
888
889        // Generate the sparse mask.
890        //
891        // Reformer is the one pattern whose mask depends on the *values* of the
892        // queries rather than only their positions, so it is routed through the
893        // LSH path with the projected queries in hand. Every other pattern is a
894        // pure function of the sequence length.
895        let mask = match &self.config.pattern {
896            SparsePattern::Reformer {
897                num_hashes,
898                bucket_size,
899            } => self.generate_lsh_mask(&query, *num_hashes, *bucket_size)?,
900            _ => self.generate_mask(seq_len)?,
901        };
902
903        // Compute sparse attention
904        let attention_output = self.compute_sparse_attention(&query, &key, &value, &mask)?;
905
906        // Final output projection
907        self.output_projection.forward(attention_output)
908    }
909}
910
911/// Utility functions for sparse attention patterns
912pub mod utils {
913    use super::*;
914
915    /// Create a local window attention pattern
916    pub fn create_local_attention(
917        hidden_size: usize,
918        num_heads: usize,
919        window_size: usize,
920    ) -> SparseAttentionConfig {
921        SparseAttentionConfig::new()
922            .with_hidden_size(hidden_size)
923            .with_num_heads(num_heads)
924            .with_pattern(SparsePattern::Local { window_size })
925    }
926
927    /// Create a block sparse attention pattern (BigBird style)
928    pub fn create_bigbird_attention(
929        hidden_size: usize,
930        num_heads: usize,
931        block_size: usize,
932    ) -> SparseAttentionConfig {
933        SparseAttentionConfig::new()
934            .with_hidden_size(hidden_size)
935            .with_num_heads(num_heads)
936            .with_pattern(SparsePattern::BlockSparse {
937                block_size,
938                global_blocks: 2,
939                random_blocks: 2,
940            })
941    }
942
943    /// Create a Longformer-style attention pattern
944    pub fn create_longformer_attention(
945        hidden_size: usize,
946        num_heads: usize,
947        window_size: usize,
948        global_tokens: Vec<usize>,
949    ) -> SparseAttentionConfig {
950        SparseAttentionConfig::new()
951            .with_hidden_size(hidden_size)
952            .with_num_heads(num_heads)
953            .with_pattern(SparsePattern::Longformer {
954                window_size,
955                global_tokens,
956            })
957    }
958
959    /// Analyze sparse attention pattern efficiency
960    pub fn analyze_pattern_efficiency(
961        pattern: &SparsePattern,
962        sequence_length: usize,
963    ) -> Result<PatternAnalysis> {
964        let config = SparseAttentionConfig::new().with_pattern(pattern.clone());
965        let attention = SparseAttention::new(config)?;
966        let mask = attention.generate_mask(sequence_length)?;
967
968        Ok(PatternAnalysis {
969            sparsity: mask.sparsity(),
970            memory_reduction: mask.sparsity(),
971            compute_reduction: mask.sparsity(),
972            effective_receptive_field: calculate_receptive_field(&mask),
973            pattern_regularity: calculate_pattern_regularity(&mask),
974        })
975    }
976
977    fn calculate_receptive_field(mask: &SparseAttentionMask) -> f32 {
978        let mut total_connections = 0;
979        let mut positions_with_connections = 0;
980
981        for i in 0..mask.shape.0 {
982            let mut connections = 0;
983            for &(row, _) in &mask.indices {
984                if row == i {
985                    connections += 1;
986                }
987            }
988            if connections > 0 {
989                total_connections += connections;
990                positions_with_connections += 1;
991            }
992        }
993
994        if positions_with_connections > 0 {
995            total_connections as f32 / positions_with_connections as f32
996        } else {
997            0.0
998        }
999    }
1000
1001    fn calculate_pattern_regularity(mask: &SparseAttentionMask) -> f32 {
1002        // Simple regularity measure: variance in connections per position
1003        let mut connections_per_position = vec![0; mask.shape.0];
1004
1005        for &(row, _) in &mask.indices {
1006            connections_per_position[row] += 1;
1007        }
1008
1009        let mean = connections_per_position.iter().sum::<usize>() as f32 / mask.shape.0 as f32;
1010        let variance =
1011            connections_per_position.iter().map(|&x| (x as f32 - mean).powi(2)).sum::<f32>()
1012                / mask.shape.0 as f32;
1013
1014        1.0 / (1.0 + variance) // Higher regularity = lower variance
1015    }
1016
1017    /// Analysis results for sparse attention patterns
1018    #[derive(Debug, Clone)]
1019    pub struct PatternAnalysis {
1020        pub sparsity: f32,
1021        pub memory_reduction: f32,
1022        pub compute_reduction: f32,
1023        pub effective_receptive_field: f32,
1024        pub pattern_regularity: f32,
1025    }
1026}
1027
1028#[cfg(test)]
1029mod tests {
1030    use super::*;
1031    use trustformers_core::tensor::Tensor;
1032
1033    #[test]
1034    fn test_local_attention_mask() {
1035        let config =
1036            SparseAttentionConfig::new().with_pattern(SparsePattern::Local { window_size: 4 });
1037
1038        let attention = SparseAttention::new(config).expect("operation failed");
1039        let mask = attention.generate_mask(8).expect("operation failed");
1040
1041        assert_eq!(mask.shape, (8, 8));
1042        assert!(mask.sparsity() > 0.0);
1043    }
1044
1045    #[test]
1046    fn test_block_sparse_attention_mask() {
1047        // Use larger sequence and smaller blocks to ensure some sparsity
1048        let config = SparseAttentionConfig::new().with_pattern(SparsePattern::BlockSparse {
1049            block_size: 4,
1050            global_blocks: 1,
1051            random_blocks: 1,
1052        });
1053
1054        let attention = SparseAttention::new(config).expect("operation failed");
1055        let mask = attention.generate_mask(32).expect("operation failed"); // Larger sequence for more sparsity
1056
1057        assert_eq!(mask.shape, (32, 32));
1058        // With 8 blocks of size 4, not all blocks are covered by diagonal/global/random
1059        // so we should have some sparsity
1060        assert!(mask.sparsity() >= 0.0); // At minimum, mask is valid
1061    }
1062
1063    #[test]
1064    fn test_sparse_attention_forward() {
1065        let config = SparseAttentionConfig::new()
1066            .with_hidden_size(64)
1067            .with_num_heads(4)
1068            .with_pattern(SparsePattern::Local { window_size: 4 });
1069
1070        let attention = SparseAttention::new(config).expect("operation failed");
1071
1072        // Create dummy input
1073        let input = Tensor::randn(&[8, 64]).expect("operation failed");
1074        let attention_input = AttentionInput {
1075            hidden_states: input,
1076            attention_mask: None,
1077        };
1078
1079        let output = attention.forward(attention_input).expect("operation failed");
1080
1081        match output {
1082            Tensor::F32(arr) => {
1083                assert_eq!(arr.shape(), &[8, 64]);
1084            },
1085            _ => panic!("Expected F32 tensor"),
1086        }
1087    }
1088
1089    #[test]
1090    fn test_pattern_analysis() {
1091        let pattern = SparsePattern::Local { window_size: 4 };
1092        let analysis =
1093            utils::analyze_pattern_efficiency(&pattern, 16).expect("operation failed in test");
1094
1095        assert!(analysis.sparsity > 0.0);
1096        assert!(analysis.sparsity < 1.0);
1097        assert!(analysis.effective_receptive_field > 0.0);
1098        assert!(analysis.pattern_regularity > 0.0);
1099    }
1100
1101    #[test]
1102    fn test_utility_functions() {
1103        let local_config = utils::create_local_attention(768, 12, 128);
1104        assert_eq!(local_config.hidden_size, 768);
1105        assert_eq!(local_config.num_heads, 12);
1106
1107        let bigbird_config = utils::create_bigbird_attention(768, 12, 64);
1108        assert_eq!(bigbird_config.hidden_size, 768);
1109
1110        let longformer_config = utils::create_longformer_attention(768, 12, 128, vec![0, 1]);
1111        assert_eq!(longformer_config.hidden_size, 768);
1112    }
1113
1114    #[test]
1115    fn test_sparse_mask_operations() {
1116        let mut mask = SparseAttentionMask::new((4, 4));
1117        mask.add_entry(0, 0, 0.0);
1118        mask.add_entry(0, 1, 0.0);
1119        mask.add_entry(1, 1, 0.0);
1120
1121        assert_eq!(mask.indices.len(), 3);
1122        assert_eq!(mask.sparsity(), 1.0 - 3.0 / 16.0);
1123
1124        let dense = mask.to_dense();
1125        assert_eq!(dense.len(), 4);
1126        assert_eq!(dense[0].len(), 4);
1127        assert_eq!(dense[0][0], 0.0);
1128        assert_eq!(dense[0][1], 0.0);
1129        assert_eq!(dense[0][2], f32::NEG_INFINITY);
1130    }
1131
1132    // ── Reformer LSH (regression for the positional-bucketing fake) ─────────
1133
1134    fn lsh_attention(head_dim: usize, num_hashes: usize, bucket_size: usize) -> SparseAttention {
1135        SparseAttention::new(
1136            SparseAttentionConfig::new()
1137                .with_hidden_size(head_dim)
1138                .with_num_heads(1)
1139                .with_pattern(SparsePattern::Reformer {
1140                    num_hashes,
1141                    bucket_size,
1142                }),
1143        )
1144        .expect("LSH attention must build")
1145    }
1146
1147    /// Regression: `generate_reformer_mask` bucketed by *token index*
1148    /// (`((i + hash_idx) % seq_len) / bucket_size`), so the mask was a pure
1149    /// function of position and could be produced without any query at all. It
1150    /// now reports that a mask cannot be derived from a length alone.
1151    #[test]
1152    fn reformer_mask_cannot_be_built_from_a_sequence_length_alone() {
1153        let attention = lsh_attention(4, 2, 4);
1154        let err = attention
1155            .generate_mask(16)
1156            .expect_err("LSH needs the query vectors, not just a length");
1157        let message = err.to_string();
1158        assert!(
1159            message.contains("hashes the query vectors"),
1160            "unexpected: {message}"
1161        );
1162        assert!(
1163            message.contains("generate_lsh_mask"),
1164            "unexpected: {message}"
1165        );
1166    }
1167
1168    /// The defining property of LSH: tokens whose queries point in the same
1169    /// direction land in the same bucket, regardless of how far apart they are.
1170    ///
1171    /// The old positional bucketing gave the opposite behaviour — identical
1172    /// queries at distant positions were never connected — so this fails
1173    /// against it.
1174    #[test]
1175    fn lsh_buckets_distant_tokens_with_similar_queries_together() {
1176        let head_dim = 8usize;
1177        let seq_len = 16usize;
1178        let bucket_size = 4usize;
1179        let attention = lsh_attention(head_dim, 4, bucket_size);
1180
1181        // Positions 0 and 15 share one direction; everything between them points
1182        // the opposite way.
1183        let mut values = vec![0.0f32; seq_len * head_dim];
1184        for t in 0..seq_len {
1185            let sign = if t == 0 || t == seq_len - 1 { 1.0 } else { -1.0 };
1186            for d in 0..head_dim {
1187                values[t * head_dim + d] = sign * ((d + 1) as f32);
1188            }
1189        }
1190        let queries = Tensor::from_vec(values, &[seq_len, head_dim]).expect("queries must build");
1191
1192        let mask = attention
1193            .generate_lsh_mask(&queries, 4, bucket_size)
1194            .expect("LSH mask must be produced");
1195
1196        assert!(
1197            mask.indices.contains(&(0, seq_len - 1)) || mask.indices.contains(&(seq_len - 1, 0)),
1198            "two identical queries {} positions apart must share a bucket",
1199            seq_len - 1
1200        );
1201    }
1202
1203    /// Conversely, tokens whose queries are near-orthogonal should mostly *not*
1204    /// be bucketed together, even when they are adjacent — the old positional
1205    /// scheme always connected neighbours.
1206    #[test]
1207    fn lsh_separates_adjacent_tokens_with_dissimilar_queries() {
1208        let head_dim = 16usize;
1209        let seq_len = 32usize;
1210        let attention = lsh_attention(head_dim, 1, 4);
1211
1212        // One-hot queries: every token points along a different axis, so almost
1213        // no pair is similar.
1214        let mut values = vec![0.0f32; seq_len * head_dim];
1215        for t in 0..seq_len {
1216            values[t * head_dim + (t % head_dim)] = 1.0;
1217        }
1218        let queries = Tensor::from_vec(values, &[seq_len, head_dim]).expect("queries must build");
1219
1220        let mask = attention.generate_lsh_mask(&queries, 1, 4).expect("LSH mask must be produced");
1221
1222        // With near-orthogonal queries the mask must be genuinely sparse rather
1223        // than the dense block-diagonal a positional chunking would give.
1224        let density = mask.indices.len() as f32 / (seq_len * seq_len) as f32;
1225        assert!(
1226            density < 0.35,
1227            "orthogonal queries must not all collide; density was {density}"
1228        );
1229        assert!(
1230            !mask.indices.is_empty(),
1231            "every token attends to at least itself"
1232        );
1233    }
1234
1235    /// The mask must depend on the queries. Under positional bucketing it did
1236    /// not: two completely different query tensors of the same length produced
1237    /// byte-identical masks.
1238    #[test]
1239    fn lsh_masks_differ_for_different_queries() {
1240        let head_dim = 8usize;
1241        let seq_len = 16usize;
1242        let attention = lsh_attention(head_dim, 2, 4);
1243
1244        let clustered = Tensor::from_vec(
1245            (0..seq_len * head_dim)
1246                .map(|i| if (i / head_dim) < seq_len / 2 { 1.0 } else { -1.0 })
1247                .collect(),
1248            &[seq_len, head_dim],
1249        )
1250        .expect("queries must build");
1251        let spread = Tensor::from_vec(
1252            (0..seq_len * head_dim).map(|i| ((i * 13) % 17) as f32 - 8.0).collect(),
1253            &[seq_len, head_dim],
1254        )
1255        .expect("queries must build");
1256
1257        let mask_a = attention.generate_lsh_mask(&clustered, 2, 4).expect("mask must build");
1258        let mask_b = attention.generate_lsh_mask(&spread, 2, 4).expect("mask must build");
1259
1260        assert_ne!(
1261            mask_a.indices, mask_b.indices,
1262            "the LSH mask must depend on the query values, not only on their positions"
1263        );
1264    }
1265
1266    /// Inference must be reproducible: the same queries must hash identically
1267    /// on every call.
1268    #[test]
1269    fn lsh_bucketing_is_deterministic() {
1270        let head_dim = 8usize;
1271        let seq_len = 16usize;
1272        let attention = lsh_attention(head_dim, 3, 4);
1273        let queries = Tensor::from_vec(
1274            (0..seq_len * head_dim).map(|i| ((i * 7) % 19) as f32 - 9.0).collect(),
1275            &[seq_len, head_dim],
1276        )
1277        .expect("queries must build");
1278
1279        let first = attention.generate_lsh_mask(&queries, 3, 4).expect("mask must build");
1280        let second = attention.generate_lsh_mask(&queries, 3, 4).expect("mask must build");
1281        assert_eq!(
1282            first.indices, second.indices,
1283            "identical queries must produce an identical attention pattern"
1284        );
1285    }
1286
1287    /// More hash rounds recover more true neighbours, so the mask can only grow.
1288    #[test]
1289    fn more_hash_rounds_never_lose_pairs() {
1290        let head_dim = 8usize;
1291        let seq_len = 24usize;
1292        let attention = lsh_attention(head_dim, 1, 4);
1293        let queries = Tensor::from_vec(
1294            (0..seq_len * head_dim).map(|i| ((i * 11) % 23) as f32 - 11.0).collect(),
1295            &[seq_len, head_dim],
1296        )
1297        .expect("queries must build");
1298
1299        let one = attention.generate_lsh_mask(&queries, 1, 4).expect("mask must build");
1300        let many = attention.generate_lsh_mask(&queries, 6, 4).expect("mask must build");
1301        assert!(
1302            many.indices.len() >= one.indices.len(),
1303            "extra hash rounds must not shrink the candidate set: {} vs {}",
1304            many.indices.len(),
1305            one.indices.len()
1306        );
1307    }
1308
1309    #[test]
1310    fn lsh_rejects_degenerate_parameters() {
1311        let attention = lsh_attention(4, 1, 4);
1312        let queries = Tensor::zeros(&[8, 4]).expect("queries must build");
1313        assert!(attention.generate_lsh_mask(&queries, 1, 0).is_err());
1314        assert!(attention.generate_lsh_mask(&queries, 0, 4).is_err());
1315        let three_d = Tensor::zeros(&[2, 4, 4]).expect("tensor must build");
1316        assert!(attention.generate_lsh_mask(&three_d, 1, 4).is_err());
1317    }
1318
1319    /// The layer's `forward` must route Reformer through the LSH path rather
1320    /// than failing on `generate_mask`.
1321    #[test]
1322    fn forward_routes_reformer_through_the_lsh_path() {
1323        let hidden = 8usize;
1324        let seq_len = 16usize;
1325        let attention = lsh_attention(hidden, 2, 4);
1326        let input = Tensor::from_vec(
1327            (0..seq_len * hidden).map(|i| ((i * 5) % 13) as f32 * 0.1 - 0.6).collect(),
1328            &[seq_len, hidden],
1329        )
1330        .expect("input must build");
1331
1332        let output = attention
1333            .forward(AttentionInput::new(input))
1334            .expect("Reformer attention must run through the LSH path");
1335        assert_eq!(output.shape(), vec![seq_len, hidden]);
1336    }
1337}