1use scirs2_core::Array2; use 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
51struct 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 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 fn next_open_unit(&mut self) -> f32 {
82 let bits = (self.next_u64() >> 40) as f32; (bits + 0.5) / 16_777_216.0
86 }
87
88 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#[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#[derive(Debug, Clone)]
168pub enum SparsePattern {
169 Local { window_size: usize },
171 Strided { stride: usize, window_size: usize },
173 Dilated {
175 max_dilation: usize,
176 window_size: usize,
177 },
178 Random { sparsity_ratio: f32 },
180 BlockSparse {
182 block_size: usize,
183 global_blocks: usize,
184 random_blocks: usize,
185 },
186 Longformer {
188 window_size: usize,
189 global_tokens: Vec<usize>,
190 },
191 Linformer { projection_dim: usize },
193 Reformer {
195 num_hashes: usize,
196 bucket_size: usize,
197 },
198 Custom { mask: SparseAttentionMask },
200}
201
202#[derive(Debug, Clone)]
204pub struct SparseAttentionMask {
205 pub indices: Vec<(usize, usize)>, pub values: Vec<f32>, pub shape: (usize, usize), }
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#[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 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 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 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 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 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 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 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 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 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 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 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 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 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 let n_buckets = seq_len.div_ceil(bucket_size).max(2);
648 let half_buckets = n_buckets.div_ceil(2);
649
650 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 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 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 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 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 let context_start = start.saturating_sub(bucket_size);
700 for &i in &order[start..end] {
701 for &j in &order[context_start..end] {
702 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 #[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 masked_scores.fill(f32::NEG_INFINITY);
741
742 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 fn compute_sparse_attention(
760 &self,
761 query: &Tensor,
762 key: &Tensor,
763 value: &Tensor,
764 mask: &SparseAttentionMask,
765 ) -> Result<Tensor> {
766 let attention_scores = self.compute_sparse_scores(query, key, mask)?;
772
773 let attention_weights = attention_scores.softmax(-1)?;
775
776 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 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 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 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 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 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 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 let attention_output = self.compute_sparse_attention(&query, &key, &value, &mask)?;
905
906 self.output_projection.forward(attention_output)
908 }
909}
910
911pub mod utils {
913 use super::*;
914
915 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 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 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 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 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) }
1016
1017 #[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 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"); assert_eq!(mask.shape, (32, 32));
1058 assert!(mask.sparsity() >= 0.0); }
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 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 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 #[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 #[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 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 #[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 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 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 #[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 #[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 #[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 #[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}