aicad 1.0.0-rc.1

A library to solve Constraint satisfaction problems with Multi-valued decision diagrams and, optionnaly, neural networks
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
//! The layers of ConsFormer, the transformer that reads an assignment and proposes new values.
//!
//! Each variable of a problem is a token. The network embeds the current value of every variable,
//! marks the variables it must re-predict, optionally tells the variables apart by their position
//! in the problem, lets the variables that share a constraint exchange information, and outputs
//! one logit per value of the domain for every variable ([`ConsFormer`]). The same network is used
//! for every problem that has the same variables; the problem enters through the attention mask
//! that [`ConsFormerInputs`] provides.
//!
//! # How it works
//!
//! 1. [`AssignmentEmbedding`] maps each value to a vector, [`StructuredPositionalEmbedding`] maps
//!    the position of each variable to a vector (when positions are used), and a learned vector
//!    marks the variables to re-predict. [`EmbeddingMixer`] adds the three, each scaled by a
//!    learned weight.
//! 2. A stack of [`TransformerBlock`]s follows. Each block normalises its input, applies
//!    [`MultiHeadAttention`] restricted to the variables that share a constraint (and the variable
//!    itself), adds the result to its input, then does the same with a [`FeedForward`] layer.
//! 3. A linear layer maps each variable to one logit per value, divided by the temperature `tau`.
//!
//! # Design notes
//!
//! - **The hidden size equals the embedding size.** The blocks add their output to their input
//!   (residual connections), so both must have the same size. This restrictions is inherited from
//!   the original ConsFormer design.
//! - **Attention follows the constraints.** A variable only attends to the variables it shares a
//!   constraint with, so the network sees the structure of the problem without reading the
//!   constraints themselves. [`MaskingKind`] chooses between forbidding the other pairs outright
//!   and learning how strongly to suppress them.
//! - **Positions are summed, not concatenated.** A variable can have any number of coordinates
//!   (row and column of a Sudoku cell, nurse, day and shift of a roster): each coordinate is
//!   embedded on its own and the embeddings are added. This is a shift from the original
//!   ConsFormer code; however, we see no difference in performance.

use burn::config::Config;
use burn::module::{Module, Param};
use burn::nn::{
    Dropout, DropoutConfig, EmbeddingConfig, Gelu, LayerNorm, LayerNormConfig, Linear, LinearConfig,
};
use burn::tensor::{Bool, Int, Tensor, backend::Backend};

use super::ConsFormerInputs;
use crate::neural::*;

// --- Embedding --- //

/// Embeds a discrete assignment to the variables into the embedding space
#[derive(Module, Debug)]
pub struct AssignmentEmbedding<B: Backend> {
    /// The embedding table, with one row per value of the domain.
    embedding: burn::nn::Embedding<B>,
}

/// Parameters of the embedding module
#[derive(Config, Debug)]
pub(crate) struct AssignmentEmbeddingConfig {
    /// Domain size of the variables
    pub domain_size: usize,
    /// Embedding size
    pub embedding_size: usize,
}

impl AssignmentEmbeddingConfig {
    /// Creates the embedding with randomly initialised rows.
    pub(crate) fn init<B: Backend>(&self, device: &B::Device) -> AssignmentEmbedding<B> {
        AssignmentEmbedding {
            embedding: EmbeddingConfig::new(self.domain_size, self.embedding_size).init(device),
        }
    }
}

impl<B: Backend> AssignmentEmbedding<B> {
    /// x: Input assignments (batch_size, number_variables)
    /// returns:             (batch_size, number_variables, embedding_size)
    pub fn forward(&self, x: Tensor<B, 2, Int>) -> Tensor<B, 3> {
        self.embedding.forward(x)
    }
}

/// Positional embedding used for identify variables in the attention masks.
#[derive(Module, Debug)]
pub struct FixedPositionalEmbedding<B: Backend> {
    /// table: pre-computed table to map variable index to position. Tensor of shape (16384, embedding_size)
    table: Tensor<B, 2>,
}

impl<B: Backend> FixedPositionalEmbedding<B> {
    /// Creates a new positional embedding for the variables. Pre-compute the table for each
    /// possible variable id (0, ..., max_len - 1) computes its (sin, cos) position.
    pub fn new(embedding_size: usize, device: &B::Device) -> Self {
        let half = embedding_size / 2;

        let inv_freq: Vec<f32> = (0..half)
            .map(|i| 1.0f32 / 10000f32.powf((2 * i) as f32 / embedding_size as f32))
            .collect();
        let inv_freq: Tensor<B, 2> =
            Tensor::<B, 1>::from_floats(inv_freq.as_slice(), device).reshape([1, half]);

        let t: Tensor<B, 2> = Tensor::<B, 1, Int>::arange(0..16384, device)
            .float()
            .reshape([16384, 1]);

        let sinusoid_inp = t.matmul(inv_freq);

        let table = Tensor::cat(vec![sinusoid_inp.clone().sin(), sinusoid_inp.cos()], 1);

        FixedPositionalEmbedding { table }
    }

    /// x: Input variable ids (batch_size, number_variables)
    /// returns:              (batch_size, number_variables, embedding_size)
    pub fn forward(&self, x: Tensor<B, 2, Int>) -> Tensor<B, 3> {
        let [batch_size, number_variables] = x.dims();
        let embedding_size = self.table.dims()[1];

        let flat_ids: Tensor<B, 1, Int> = x.reshape([batch_size * number_variables]);
        // (batch_size * number_variables, embedding_size)
        let gathered = self.table.clone().select(0, flat_ids);

        gathered.reshape([batch_size, number_variables, embedding_size])
    }
}

/// Sums a `FixedPositionalEmbedding` per positional axis (e.g. Sudoku: row
/// axis + column axis; nurse rostering: nurse/day/shift axes), built from a
/// `PositionalStructure`. Each axis is looked up independently and the
/// results are summed (rather than concatenated, the way the original
/// ConsFormer's hardcoded 2-axis case does) -- summing composes to any
/// number of axes without needing `embedding_size` to be divisible by the
/// axis count, and matches how the rest of the embedding mix (assignment,
/// mask, position) is already combined by `EmbeddingMixer`.
#[derive(Module, Debug)]
pub struct StructuredPositionalEmbedding<B: Backend> {
    /// One table per axis.
    axes: Vec<FixedPositionalEmbedding<B>>,
    /// `axis_ids[a][v]` is the coordinate of variable `v` on axis `a`.
    #[module(skip)]
    axis_ids: Vec<Vec<usize>>,
}

impl<B: Backend> StructuredPositionalEmbedding<B> {
    /// Creates a new structural positional embedding
    pub fn new(
        embedding_size: usize,
        num_axes: usize,
        positions: Vec<Vec<usize>>,
        device: &B::Device,
    ) -> Self {
        let axes = vec![FixedPositionalEmbedding::new(embedding_size, device); num_axes];

        let axis_ids: Vec<Vec<usize>> = (0..num_axes)
            .map(|a| positions.iter().map(|coords| coords[a]).collect())
            .collect();

        StructuredPositionalEmbedding { axes, axis_ids }
    }

    /// batch_size: number of parallel assignments in this forward call.
    /// returns: (batch_size, number_vars, embedding_size), summed across
    /// axes.
    pub fn forward(&self, batch_size: usize, device: &B::Device) -> Tensor<B, 3> {
        let mut acc: Option<Tensor<B, 3>> = None;
        for (axis_embed, ids) in self.axes.iter().zip(self.axis_ids.iter()) {
            let number_vars = ids.len();
            let ids_flat: Vec<i64> = ids.iter().map(|&v| v as i64).collect();
            let ids_2d: Tensor<B, 2, Int> =
                Tensor::<B, 1, Int>::from_data(ids_flat.as_slice(), device)
                    .reshape([1, number_vars])
                    .repeat_dim(0, batch_size);
            let embed = axis_embed.forward(ids_2d);
            acc = Some(match acc {
                None => embed,
                Some(prev) => prev + embed,
            });
        }
        acc.expect("PositionalStructure must have at least one axis")
    }
}

/// Combines the embedding of the assignment, the embedding of the position and the embedding that
/// marks the variables to re-predict into one input for the transformer blocks. Each of the three is
/// scaled by its own learned weight.
#[derive(Module, Debug)]
pub struct EmbeddingMixer<B: Backend> {
    /// Weight the assignment embedding for mixing. Learnable float parameter.
    assignment_weight: Param<Tensor<B, 3>>,
    /// Weight the mask (i.e., which variable is being modified) embedding for mixing. Learnable float parameter.
    mask_weight: Param<Tensor<B, 3>>,
    /// Weight the positional embedding for mixing. Learnable float parameter.
    position_weight: Param<Tensor<B, 3>>,
}

/// Parameters of the [`EmbeddingMixer`].
#[derive(Config, Debug)]
pub(crate) struct EmbeddingMixerConfig {
    /// Size of the embeddings that are mixed.
    pub embedding_size: usize,
}

impl EmbeddingMixerConfig {
    /// Creates the mixer with all three weights set to 1.
    pub(crate) fn init<B: Backend>(&self, device: &B::Device) -> EmbeddingMixer<B> {
        EmbeddingMixer {
            assignment_weight: Param::from_tensor(Tensor::ones([1, 1, 1], device)),
            mask_weight: Param::from_tensor(Tensor::ones([1, 1, 1], device)),
            position_weight: Param::from_tensor(Tensor::ones([1, 1, 1], device)),
        }
    }
}

impl<B: Backend> EmbeddingMixer<B> {
    /// Returns the weighted sum of the embeddings, where the mask embedding only counts at the
    /// variables to re-predict.
    ///
    /// assignment_embeddings: Embeddings of the current assignment. Tensor of shape (batch_size, number_var, embedding_size)
    /// mask_embedding: Learned mask for the embeddings.             Tensor of shape (embedding_size,)
    /// position_embeddings: Positional embeddings                   Tensor of shape (batch_size, number_var, embedding_size)
    /// mask_vars: Mask indicating which variable to change.         Tensor of shape (bathc_size, number_var)
    pub fn forward(
        &self,
        assignment_embeddings: Tensor<B, 3>,
        mask_embedding: Tensor<B, 1>,
        position_embeddings: Option<Tensor<B, 3>>,
        mask_vars: Tensor<B, 2, Bool>,
    ) -> Tensor<B, 3> {
        let [batch, seq_len, embed_dim] = assignment_embeddings.dims();
        // Reshaping the tensors so that they have the right dimensions
        let mask_inds_3d = mask_vars.reshape([batch, seq_len, 1]);
        let mask_embed_bc = mask_embedding.reshape([1, 1, embed_dim]);
        // Combine the mask as a linear combination of the embeddings
        let combined = match position_embeddings {
            None => assignment_embeddings * self.assignment_weight.val(),
            Some(pos) => {
                assignment_embeddings * self.assignment_weight.val()
                    + pos * self.position_weight.val()
            }
        };

        // Computing the mask contribution to the embedding
        let masked_component = mask_embed_bc * self.mask_weight.val();
        let mask_inds_f = mask_inds_3d.float();

        combined + masked_component * mask_inds_f
    }
}

// --- Feed forward block --- //

/// Feed-forward layer of a transformer block: it transforms each variable on its own, without
/// looking at the others.
#[derive(Module, Debug)]
pub struct FeedForward<B: Backend> {
    /// Expands each variable from the hidden size to the expanded size.
    fc1: Linear<B>,
    /// Non-linearity between the two linear layers.
    act: Gelu,
    /// Brings each variable back from the expanded size to the hidden size.
    fc2: Linear<B>,
    /// Dropout applied to the output, during training.
    drop: Dropout,
}

/// Parameters of the [`FeedForward`] layer.
#[derive(Config, Debug)]
pub(crate) struct FeedForwardConfig {
    /// Size of the input and of the output of the layer
    pub hidden_size: usize,
    /// Size of the internal layer
    pub expand_size: usize,
    /// Dropout of the output during training
    #[config(default = 0.1)]
    pub drop: f64,
    /// Insert bias in the linear layers
    #[config(default = true)]
    pub bias: bool,
}

impl FeedForwardConfig {
    /// Creates the layer with randomly initialised weights.
    pub(crate) fn init<B: Backend>(&self, device: &B::Device) -> FeedForward<B> {
        FeedForward {
            fc1: LinearConfig::new(self.hidden_size, self.expand_size)
                .with_bias(self.bias)
                .init(device),
            act: Gelu::new(),
            fc2: LinearConfig::new(self.expand_size, self.hidden_size)
                .with_bias(self.bias)
                .init(device),
            drop: DropoutConfig::new(self.drop).init(),
        }
    }
}

impl<B: Backend> FeedForward<B> {
    /// x: (batch_size, number_vars, hidden_size)
    /// returns: the same shape.
    pub fn forward(&self, x: Tensor<B, 3>) -> Tensor<B, 3> {
        let x = self.fc1.forward(x);
        let x = self.act.forward(x);
        let x = self.fc2.forward(x);
        self.drop.forward(x)
    }
}

// --- Multi-head attention --- //

/// Two biases (per head) added to attention energy in place of hard masking: `connected` for
/// primal-graph-linked (or self) pairs, `unconnected` for everything else. `unconnected` is
/// initialised strongly negative (`UNCONNECTED_BIAS_INIT`) so the network starts out close to
/// the hard-masked behaviour -- but, being a learned `Param` rather than a literal
/// `f32::NEG_INFINITY`, gradients still flow through it and the model can learn to attend
/// beyond the primal graph where that helps.
#[derive(Module, Debug)]
pub struct LearnedMaskBias<B: Backend> {
    /// Bias, per head, of the pairs that are linked. Starts at 0.
    connected: Param<Tensor<B, 1>>,
    /// Bias, per head, of the pairs that are not linked. Starts at `UNCONNECTED_BIAS_INIT`.
    unconnected: Param<Tensor<B, 1>>,
}

/// Starting value for the "unconnected" bias: negative enough that softmax over a row with
/// many connected entries still puts negligible weight on unconnected ones at initialisation
/// (unlike literal `-inf`, this is finite so its gradient isn't always exactly zero).
const UNCONNECTED_BIAS_INIT: f32 = -1.0;

impl<B: Backend> LearnedMaskBias<B> {
    /// Creates the biases for `head_count` heads, at their initial values.
    fn new(head_count: usize, device: &B::Device) -> Self {
        LearnedMaskBias {
            connected: Param::from_tensor(Tensor::zeros([head_count], device)),
            unconnected: Param::from_tensor(
                Tensor::ones([head_count], device).mul_scalar(UNCONNECTED_BIAS_INIT),
            ),
        }
    }

    /// mask: (batch, 1, number_vars, number_vars), true where connected.
    /// returns: (batch, head_count, number_vars, number_vars) additive bias to add to energy.
    fn bias_for(&self, mask: Tensor<B, 4, Bool>) -> Tensor<B, 4> {
        let head_count = self.connected.val().dims()[0];
        let mask_f = mask.float();
        let connected = self.connected.val().reshape([1, head_count, 1, 1]);
        let unconnected = self.unconnected.val().reshape([1, head_count, 1, 1]);
        mask_f.clone() * connected + (mask_f.neg().add_scalar(1.0)) * unconnected
    }
}

/// How `MultiHeadAttention` incorporates the primal-graph attention mask into the attention
/// energy before softmax.
#[derive(Debug, Clone, Copy, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub enum MaskingKind {
    /// Non-linked pairs get `f32::NEG_INFINITY` added to their energy (`Tensor::mask_fill`),
    /// giving them exactly zero softmax weight and zero gradient.
    Hard,
    /// Each entry in the attention mask is learned instead of masking unconnected entries. This is
    /// useful for problems with large global constraint, leading to almost all-connected
    /// attention.
    Learned,
}

/// Lets each variable gather information from the variables it shares a constraint with: for each
/// head, a variable weighs its neighbours by how well what it looks for matches what they offer, and
/// takes the weighted sum of what they offer. The heads are then concatenated and projected back.
#[derive(Module, Debug)]
pub struct MultiHeadAttention<B: Backend> {
    /// Computes the queries: what each variable looks for.
    q_proj: Linear<B>,
    /// Computes the keys: what each variable advertises about itself.
    k_proj: Linear<B>,
    /// Computes the values: what each variable offers to the variables that attend to it.
    v_proj: Linear<B>,
    /// Dropout applied to the attention weights, during training.
    drop_out: Dropout,
    /// Brings the concatenated heads back to the hidden size.
    projection: Linear<B>,
    /// Size of the representation of a variable in one head.
    hidden_size: usize,
    /// Number of heads.
    head_count: usize,
    /// `Some` iff `masking_kind == MaskingKind::Learned`.
    learned_bias: Option<LearnedMaskBias<B>>,
}

/// Parameters of the [`MultiHeadAttention`] layer.
#[derive(Config, Debug)]
pub(crate) struct MultiHeadAttentionConfig {
    /// Size of the embedding of the assignments
    pub embedding_size: usize,
    /// Size of the hidden representation of the multi-head attention block
    pub hidden_size: usize,
    /// Number of heads
    #[config(default = 8)]
    pub head_count: usize,
    /// Drop-out used during training
    #[config(default = 0.1)]
    pub dropout: f64,
    /// How the primal-graph attention mask is applied -- see `MaskingKind`.
    #[config(default = "MaskingKind::Hard")]
    pub masking_kind: MaskingKind,
}

impl MultiHeadAttentionConfig {
    /// Creates the attention layer with randomly initialised weights.
    pub(crate) fn init<B: Backend>(&self, device: &B::Device) -> MultiHeadAttention<B> {
        MultiHeadAttention {
            q_proj: LinearConfig::new(self.embedding_size, self.hidden_size * self.head_count)
                .init(device),
            k_proj: LinearConfig::new(self.embedding_size, self.hidden_size * self.head_count)
                .init(device),
            v_proj: LinearConfig::new(self.embedding_size, self.hidden_size * self.head_count)
                .init(device),
            drop_out: DropoutConfig::new(self.dropout).init(),
            projection: LinearConfig::new(self.hidden_size * self.head_count, self.hidden_size)
                .init(device),
            hidden_size: self.hidden_size,
            head_count: self.head_count,
            learned_bias: match self.masking_kind {
                MaskingKind::Hard => None,
                MaskingKind::Learned => Some(LearnedMaskBias::new(self.head_count, device)),
            },
        }
    }
}

impl<B: Backend> MultiHeadAttention<B> {
    /// x: Embedding of the current assignment. Tensor of shape (batch_size, number_vars, embedding_size)
    /// attention_mask: Mask the attention of variables not neighbors in the primal graph of the
    /// problem.                                Tensor of shape (batch_size, number_vars, number_vars)
    /// Returns: A tensor of [batch_size, number_variables, domain_size] with one logit per
    ///          variable-value pair for each sample.
    pub fn forward(&self, x: Tensor<B, 3>, attention_mask: Tensor<B, 3, Bool>) -> Tensor<B, 3> {
        let [batch_size, number_vars, _] = x.dims();

        // What information each variable is looking from other
        let queries = self.reshape_qkv(self.q_proj.forward(x.clone()), batch_size, number_vars);
        // What information each variable advertise about itself
        let keys = self.reshape_qkv(self.k_proj.forward(x.clone()), batch_size, number_vars);
        // What content this variable offers
        let values = self.reshape_qkv(self.v_proj.forward(x), batch_size, number_vars);

        // Energy between to variables i, j: energy[i,j] = (Q[i] x K[j]) / sqrt(hidden_size)
        // The energy between variables i compared to j measure how the query for i (what variable
        // i looks for) is aligned with what information j offers.
        // The higher the dot product, the more the two variables must be taken into account when
        // generating a new assignment.
        // The dot product is normalised to avoid explosion when dimensionality of the hidden size
        // grows.
        let mut energy = queries.matmul(keys.transpose()) / (self.hidden_size as f64).sqrt();

        // Applies the attention mask. `attention_mask` is `true` where attention IS allowed
        // (self, or linked in the primal graph -- see `consformer_mask_data`'s doc).
        let mask_4d: Tensor<B, 4, Bool> =
            attention_mask.reshape([batch_size, 1, number_vars, number_vars]);
        energy = match &self.learned_bias {
            // Hard masking: non-linked pairs get exactly -inf, i.e. exactly zero softmax
            // weight and zero gradient
            None => energy.mask_fill(mask_4d.bool_not(), f32::NEG_INFINITY),
            // Learned masking: non-linked pairs get a learned per-head additive bias instead
            // (see `LearnedMaskBias`), so the network can adjust how strongly it suppresses
            // attention outside the primal graph rather than having it fixed at -inf.
            Some(bias) => energy + bias.bias_for(mask_4d),
        };

        // Create a probability distribution from the energy mask
        let attention = burn::tensor::activation::softmax(energy, 3);
        // Drop some attention during training for generalisation
        let attention = self.drop_out.forward(attention);

        // At this point, the attention combined, for each variable, a weighted sum of its
        // neighbors (in the primal graph) learned representation and normalised into a probability
        // distribution (with random drop-out during training). Hence, attention[i,j] represents
        // how much the value of variable j impact variable i

        // attention: (batch_size, head, number_vars, number_var)
        // values:    (batch_size, head, number_vars, hidden_size)
        //
        // out:       (batch_size, number_heads, number_vars, hidden_size)
        let out = attention.matmul(values);
        //            (batch_size, number_vars, number_heads hidden_size)
        let out = out.swap_dims(1, 2);
        //            (batch_size, number_vars, number_heads*hidden_size)
        let out = out.reshape([batch_size, number_vars, self.head_count * self.hidden_size]);

        // Project back to (batch_size, number_vars, hidden_size)
        self.projection.forward(out)
    }

    /// x: Input tensor for attention mechanism, either the queries (q), the keys (k), or the
    ///    values (v). Tensors of shape (batch_size, number_vars, number_heads*hidden_size)
    /// batch_size: usize
    /// number_var: usize
    ///
    /// Returns a reshaped vector of shape (batch_size, number_vars, number_heads, hidden_size)
    /// further swapped to (batch_size, number_heads, number_vars, hidden_size)
    fn reshape_qkv(&self, x: Tensor<B, 3>, batch_size: usize, number_vars: usize) -> Tensor<B, 4> {
        x.reshape([batch_size, number_vars, self.head_count, self.hidden_size])
            .swap_dims(1, 2)
    }
}

// --- Transformer --- //

/// One block of the transformer: an attention layer then a feed-forward layer, each preceded by a
/// normalisation and added to its input.
#[derive(Module, Debug)]
pub struct TransformerBlock<B: Backend> {
    /// Normalisation of the input of the attention layer.
    norm1: LayerNorm<B>,
    /// Exchange of information between the variables that share a constraint.
    attn: MultiHeadAttention<B>,
    /// Normalisation of the input of the feed-forward layer.
    norm2: LayerNorm<B>,
    /// Transformation of each variable on its own.
    ffn: FeedForward<B>,
}

/// Parameters of the [`TransformerBlock`].
#[derive(Config, Debug)]
pub(crate) struct TransformerBlockConfig {
    /// Size of the embedding of the assignments
    pub embedding_size: usize,
    /// Size of the hidden representation of the multi-head attention block
    pub hidden_size: usize,
    /// Number of heads in the multi-head attention block
    pub num_heads: usize,
    /// Size of the internal layer of the feed-forward block
    pub expand_size: usize,
    /// Dropout of the multi-head attention block during training
    #[config(default = 0.1)]
    pub attn_drop: f64,
    /// Dropout of the feed-forward block during training
    #[config(default = 0.1)]
    pub ffn_drop: f64,
    /// If present, include bias in the feed-forward block
    #[config(default = true)]
    pub bias: bool,
    /// How the multi-head attention block applies the primal-graph attention mask -- see
    /// `MaskingKind`.
    #[config(default = "MaskingKind::Hard")]
    pub masking_kind: MaskingKind,
}

impl TransformerBlockConfig {
    /// Initialise the transformer block. It consist of the following steps:
    ///    1. Normalisation of the input (shift to 0 mean, unit variance). Useful to avoid value
    ///       explosion when stacking layers
    ///    2. Multi-head attention block. Computes the interaction between each variable and
    ///       project back to the embedding size. After this block, each variable has gather
    ///       information about its neighbors (in the primal graph) to guide its own distribution
    ///       generation
    ///    3. A new normalisation layer
    ///    4. A feed-forward block that allows each variable to look at its internal weight
    pub(crate) fn init<B: Backend>(&self, device: &B::Device) -> TransformerBlock<B> {
        TransformerBlock {
            norm1: LayerNormConfig::new(self.hidden_size).init(device),
            attn: MultiHeadAttentionConfig::new(self.embedding_size, self.hidden_size)
                .with_head_count(self.num_heads)
                .with_dropout(self.attn_drop)
                .with_masking_kind(self.masking_kind)
                .init(device),
            norm2: LayerNormConfig::new(self.hidden_size).init(device),
            ffn: FeedForwardConfig::new(self.hidden_size, self.expand_size)
                .with_drop(self.ffn_drop)
                .with_bias(self.bias)
                .init(device),
        }
    }
}

impl<B: Backend> TransformerBlock<B> {
    /// x: (batch_size, number_vars, embedding_size)
    /// attention_mask: (batch_size, number_vars, number_vars), true where attention is allowed.
    /// returns: the same shape as `x`.
    pub fn forward(&self, x: Tensor<B, 3>, attention_mask: Tensor<B, 3, Bool>) -> Tensor<B, 3> {
        // Applies the first normaliation block and the multi-head attention block
        let x = x.clone() + self.attn.forward(self.norm1.forward(x), attention_mask);
        // Applies the second normalisation block and the feed-forward block
        x.clone() + self.ffn.forward(self.norm2.forward(x))
    }
}

// --- Consformer architecture, embedding the transformer blocks --- //

/// The ConsFormer network: reads an assignment and returns, for every variable, one logit per value
/// of the domain. See the [module documentation](crate::neural::consformer).
#[derive(Module, Debug)]
pub struct ConsFormer<B: Backend> {
    /// Learned embedding for the masked variables
    pub mask_embedding: Param<Tensor<B, 1>>,
    /// Module to map assignments to their embedding
    pub assignment_embedding: AssignmentEmbedding<B>,
    /// Embedding mixer
    pub embedding_mixer: EmbeddingMixer<B>,
    /// All transformer blocks
    pub transformer_blocks: Vec<TransformerBlock<B>>,
    /// Linear layer at the end to re-combine the output of the last multi-head transformer block
    pub head: Linear<B>,
    /// Positional structure, built from the config's `PositionalEncoding`
    /// (see `ConsFormerConfig::init`). `None` means the network gets no
    /// positional signal at all and relies purely on attention
    pub position_embedding: Option<StructuredPositionalEmbedding<B>>,
    /// Logit scaling factor (`ConsFormerConfig::tau`).
    #[module(skip)]
    pub tau: f64,
}

impl<B: Backend, Ba: ConsFormerInputs<B>> Network<B, Ba> for ConsFormer<B> {
    fn forward(&self, batch: &Ba) -> Tensor<B, 3> {
        let assignments = batch.assignments();
        let [batch_size, _seq_len] = assignments.dims();
        let device = assignments.device();

        let position_embeds = self
            .position_embedding
            .as_ref()
            .map(|pe| pe.forward(batch_size, &device));

        let x = self.assignment_embedding.forward(assignments);
        let mut x = self.embedding_mixer.forward(
            x,
            self.mask_embedding.val(),
            position_embeds,
            batch.var_masks(),
        );

        for block in &self.transformer_blocks {
            x = block.forward(x, batch.attention_masks());
        }

        self.head.forward(x).div_scalar(self.tau)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use burn::backend::ndarray::{NdArray, NdArrayDevice};

    /// 3 variables: 0 and 1 linked (and self-linked), 2 isolated (self only) -- exercises both
    /// the "has an unconnected neighbour" and the "self-only, would be all -inf without the
    /// diagonal" cases in one small mask.
    fn toy_mask<B: Backend>(device: &B::Device) -> Tensor<B, 3, Bool> {
        let data = vec![
            true, true, false, //
            true, true, false, //
            false, false, true,
        ];
        Tensor::<B, 1, Bool>::from_data(data.as_slice(), device).reshape([1, 3, 3])
    }

    #[test]
    fn learned_mask_bias_starts_near_hard_masking() {
        // At init, `connected` is exactly 0 (no bias) and `unconnected` is a large negative
        // constant -- close to (but, being learnable, not identical to) hard -inf masking.
        let device = NdArrayDevice::default();
        let bias = LearnedMaskBias::<NdArray>::new(4, &device);

        let connected: Vec<f32> = bias.connected.val().into_data().to_vec::<f32>().unwrap();
        let unconnected: Vec<f32> = bias.unconnected.val().into_data().to_vec::<f32>().unwrap();

        assert_eq!(connected, vec![0.0; 4]);
        assert_eq!(unconnected, vec![UNCONNECTED_BIAS_INIT; 4]);
    }

    #[test]
    fn both_masking_kinds_produce_finite_output() {
        // Regression test for the NaN-from-an-all-masked-row failure mode `consformer_mask_data`
        // guards against (see its doc) -- verifies both masking strategies stay finite on a mask
        // that includes an isolated (self-only) variable.
        let device = NdArrayDevice::default();
        let mask = toy_mask::<NdArray>(&device);

        for masking_kind in [MaskingKind::Hard, MaskingKind::Learned] {
            let attn = MultiHeadAttentionConfig::new(8, 8)
                .with_head_count(2)
                .with_dropout(0.0)
                .with_masking_kind(masking_kind)
                .init::<NdArray>(&device);
            let x: Tensor<NdArray, 3> = Tensor::random(
                [1, 3, 8],
                burn::tensor::Distribution::Uniform(-1.0, 1.0),
                &device,
            );
            let out = attn.forward(x, mask.clone());
            let data: Vec<f32> = out.into_data().to_vec::<f32>().unwrap();
            assert!(
                data.iter().all(|v| v.is_finite()),
                "masking_kind={masking_kind:?} produced a non-finite output: {data:?}"
            );
        }
    }

    #[test]
    fn learned_mask_bias_is_trainable() {
        // The whole point of MaskingKind::Learned over hard -inf masking: gradients must flow
        // through both the connected and unconnected biases, not just be fixed constants.
        use burn::backend::Autodiff;

        type ADBackend = Autodiff<NdArray>;
        let device = NdArrayDevice::default();
        let mask = toy_mask::<ADBackend>(&device).reshape([1, 1, 3, 3]);

        let bias = LearnedMaskBias::<ADBackend>::new(2, &device);
        let loss = bias.bias_for(mask).sum();
        let grads = loss.backward();

        let connected_grad = bias
            .connected
            .val()
            .grad(&grads)
            .expect("connected bias should have a gradient after backward()");
        let unconnected_grad = bias
            .unconnected
            .val()
            .grad(&grads)
            .expect("unconnected bias should have a gradient after backward()");

        let connected_grad: Vec<f32> = connected_grad.into_data().to_vec::<f32>().unwrap();
        let unconnected_grad: Vec<f32> = unconnected_grad.into_data().to_vec::<f32>().unwrap();
        assert!(connected_grad.iter().any(|&v| v != 0.0));
        assert!(unconnected_grad.iter().any(|&v| v != 0.0));
    }
}