# Positional Diffusion: Ordering Unordered Sets
with Diffusion Probabilistic Models

Francesco Giuliari∗ 1,2 Gianluca Scarpellini∗ 1,2 Stuart James1 Yiming Wang1,3
Alessio Del Bue1
1 Istituto Italiano di Tecnologia (IIT) 2 University of Genoa
3 Fondazione Bruno Kessler (FBK)
∗ equal contribution

###### Abstract

Positional reasoning is the process of ordering unsorted parts contained in a
set into a consistent structure. We present Positional Diffusion, a plug-and-
play graph formulation with Diffusion Probabilistic Models to address
positional reasoning. We use the forward process to map elements’ positions in
a set to random positions in a continuous space. Positional Diffusion learns
to reverse the noising process and recover the original positions through an
Attention-based Graph Neural Network. We conduct extensive experiments with
benchmark datasets including two puzzle datasets, three sentence ordering
datasets, and one visual storytelling dataset, demonstrating that our method
outperforms long-lasting research on puzzle solving with up to $+18\%$
compared to the second-best deep learning method, and performs on par against
the state-of-the-art methods on sentence ordering and visual storytelling. Our
work highlights the suitability of diffusion models for ordering problems and
proposes a novel formulation and method for solving various ordering tasks.
Project website at https://iit-pavis.github.io/Positional_Diffusion/

##  1 Introduction

Figure 1: Positional Diffusion is a unified architecture based on Diffusion
Probabilistic Models following a graph formulation. It can solve several
ordering problems with different dimensionality and multi-modal data such as
Jigsaw puzzles, sentence ordering and coherent visual storytelling.

The ability to arrange elements is a fundamental human skill that is acquired
during the early stages of development and is essential for carrying out daily
tasks. Such ability is general across different tasks and researchers suggest
that childhood games, such as Jigsaw puzzles, Lego© blocks, and crosswords
play a critical role in building the foundations of reasoning over the correct
arrangement of things [22, 39]. While each of these tasks is tackling a very
specific problem, humans have remarkable skills in “putting an element in the
correct place” regardless of the dimensionality and the information modality
of the problems, such as 1-dimensional (1D) for arranging texts or 2D for
solving puzzles. We refer to this ability as positional reasoning, and
formulate it as an ordering problem, i.e., assigning a correct discrete
position to each element of an unordered set.

The difficulty lies in the combinatorial nature of ordering a set of elements
into a coherent (given) structure. A robust ordering method has to be
invariant to random permutations of the input sets, while consistently
providing the correct output. Previous solutions have been designed to be
problem-specific. For example, methods addressing Jigsaw puzzle operates on a
2D grid by jointly optimizing similarities and permutations [45] or by
learning first an image representation complaint with the set of image tiles
and then solving a standard Hungarian approach for matching the pieces [35].
Sentence ordering is another relevant 1D ordering NLP problem where a
paragraph is formed from a set of unordered sentences by exploiting pairwise
similarities and attention mechanisms [11, 25, 6, 43, 42]. Although all these
positional reasoning problems involve finding a correct ordering of a set,
their solutions are mostly customized to the data structure, position
dimensionality, and contextual information.

We propose a unified model for positional reasoning, which does not require a
re-design of the architecture given different input modalities or the
dimensionality of the positional problem. We solve the ordering problem by
regressing the position of each element in the set in a bounded continuous
space. We then use the continuous position to retrieve the element’s ordering
in the set. Our approach is based on Diffusion Probabilistic Models (DPM) to
estimate the position (and thus ordering) of each element in the set. We
achieve permutation invariance by representing elements in the set as nodes of
a fully connected graph. Using a diffusion formulation at training, we inject
noise to the node positions and train an Attention-based Graph Neural Network
(GNN) to learn the reverse process that recovers the correct positions. The
attention mechanism aggregates relevant information from neighboring nodes
given the current node features and positions. At inference, we initialize the
graph with sampled positions and iteratively retrieve the correct ordinal
positions by conditioning on nodes’ features.

Our proposed method, named Positional Diffusion, can address various problems
that require ordering an arbitrary set in a plug-and-play manner. In this
paper, we demonstrate the effectiveness of our formulation and method with
three fundamental tasks: i) puzzle solving, where we compare Positional
Diffusion to both optimization-based and deep-learning-based methods, scoring
the new state-of-the-art (SOTA) performance among all methods with a margin up
to $+18\%$ compared to the second-best deep-learning method; ii) sentence
ordering, where we obtain the SOTA performance in a subset of the test
datasets, including NeurIPs Abstract [25] and Wikipedia Plots [5]; and iii)
visual storytelling, where Positional Diffusion is on par with the SOTA
methods on the VIST dataset [17] without relying on an ensemble of methods or
any matching algorithms.

To summarize, our main contributions are the following:

  * •

We propose a novel graph formulation with DPMs to address positional
reasoning. The graph formulation addresses the invariance to input set
permutations while the DPMs learn to restore the positions via the noising and
de-noising processes;

  * •

We propose a task-agnostic method, Positional Diffusion, that implements an
Attention-based GNN following a DPM formulation to address positional
reasoning in various tasks in a plug-and-play manner;

  * •

We show without any task-specific customization, Positional Diffusion can
generalize and achieve SOTA or on-par performance among existing methods that
are specifically designed for the tasks.

Figure 2: For each task, the input initial set (i) is a permuted version of
the solution. Each element of the set is correlated with an initial sample
location (ii) $\textbf{x}^{i}_{T}$ (in 1D or 2D) and an encoding
$\textbf{h}^{i}$ from a task-specific backbone (iii). During Training of the
diffusion steps (iv) we apply a noising process to each element position
$\textbf{x}^{i}$ to obtain a noisy position $\textbf{x}_{t}^{i}$. We
concatenate $\textbf{h}^{i}$ with the noisy positions $x_{t}^{i}$ to create
the features and encode them as node features in a fully connected graph. We
use a Graph Neural Network with Attention-based message passing to generate
the less noisy positions $\textbf{x}_{t-1}^{i}$. During inference, for each
element, we sample an initial position $\textbf{x}_{T}^{i}$ from
$\mathcal{N}(0,1)$ or set it to $[0,0]$, and use Positional Diffusion for the
full reverse process to obtain the estimated positions
$\hat{\textbf{x}}^{i}_{0}$.

##  2 Related works

We consider related works on recent developments of Diffusion Probabilistic
Models and the SOTA methods of the three representative tasks for positional
reasoning, including puzzle solving, sentence ordering, and visual
storytelling.

Diffusion Probabilistic Models. Diffusion Probabilistic Models (DPMs) solve
the inverse problem of removing noise from a noisy data distribution [32].
They gained popularity thanks to their impressive results on image synthesis
[15, 8] and their elegant probabilistic interpretation [34]. Recent literature
showed that DPMs’ capabilities extend to the 3D space [26] and unveiled
promising applications for molecule generation [16]. We propose a novel
formulation of the forward and reverse diffusion process for coherently
sorting a shuffled input by treating the problem as either $n$-dimensional
vectors sampled from a Gaussian distribution.We are unaware of previous works
proposing an extensive study on positional reasoning with diffusion models.

Positional reasoning. Literature on positional reasoning is vast and assumes
different connotations depending on the task and modalities involved. Our
study focuses on positional reasoning as an ordering task, i.e., sorting
shuffled elements into a coherent output.

i) Jigsaw Puzzles [4] interested the optimization community with puzzles as a
benchmark for studying image ordering with intrinsic combinatorial complexity.
The most successful strategies are related to greedy approaches using hand-
crafted features [10, 29] with robustness to noise and missing pieces [28] and
solving thousands of pieces. For deep learning, puzzles have also been
addressed as a permutation problem. Zhang et al. [45] optimizes both the cost
matrix assessing pairwise relationships between pieces and the correct
permutation in a bi-level optimization scheme, retaining the iterative
elements of optimization methods. Alternatively, [46] used puzzles as a self-
supervised representation learning task, where concatenation fixed the number
of solvable pieces without optimization. Talon et al. [35] overcame this by
exploiting a GAN [12] and reframing the problem as an assignment problem
against the generated image.

ii) Sentence ordering involves positional reasoning on textual contents, which
aims to order sentences into a coherent narration. Early works solved the task
by modeling local coherence using language-based features [20, 2, 9, 14].
Recent works leverage deep learning to encode sentences and retrieve the final
order using pointer networks, which compare sentences in a pairwise fashion
[40, 11, 25, 6, 43, 42]. Several proposed approaches utilize attention-based
pointer networks [40], topological sorting [30, 27], deep relational modules
[7], and constraint graphs to enhance sentence representations [41, 47]. Other
works also reframed the problem as a ranking problem [3], while Chowdhury et
al. [5] formulated sentence ordering as a conditional text generation task
using a sequence-to-sequence model [23].

iii) Visual storytelling  is an extension of sentence ordering with both
textual and visual inputs to form a coherent visual stories [1]. In this
multi-modal task formulation, the input is a shuffled set of sentences and
their visual representation. VIST dataset [17] is the benchmark for this task.
While Zellers et al. [44] constrained this task to visual ordering, where the
sentences are presented in order, we maintain the original formulation for
this task [1] to study the capabilities of diffusion models in a multi-modal
setting.

Differently from previous literature in computer vision, natural language
processing, and multimodal learning, we interpret data shuffling as the noise
injection of DPMs’ forward process and exploit the reverse process of a DPM to
retrieve the final position of each element, that being a sentence, a puzzle
piece, or a sentence-image pair. To the best of our knowledge, our Positional
Diffusion is the first DPM-based solution for positional reasoning that can
work with different modalities.

##  3 Positional Diffusion

We introduce positional reasoning as a restoring process from a shuffled,
unstructured data distribution in a Euclidean space $\mathbb{R}^{n}$, where
$n$=1 for 1D problems such as sentence ordering, $n$=2 for 2D tasks such as
puzzle pieces arrangement and so on. Given an unordered set of $K$ elements
with some task-specific features
$\textbf{H}=\\{\textbf{h}^{1},\dots,\textbf{h}^{K}\\},\textbf{h}^{i}\in\mathbb{R}^{d}$,
where $d$ is the dimension of the features, and with ground truth positions
$\textbf{X}~{}=~{}\\{\textbf{x}^{1},\dots,\textbf{x}^{K}\\},\textbf{x}^{i}~{}\in~{}\mathbb{R}^{n}$,
our network outputs an estimate set of positions
$\hat{\textbf{X}}~{}=~{}\\{\hat{\textbf{x}}^{1},\dots,\hat{\textbf{x}}^{K}\\},\hat{\textbf{x}}^{i}~{}\in~{}\mathbb{R}^{n}$,
that matches the real position of each element. We encode each data point as a
node in a fully connected graph, allowing each node to influence the others.
Graph representations have the advantage to admit a variable number of input
data in a permutation-invariant way.

Our proposed Positional Diffusion uses the DPMs formulation to iteratively
restore the position of the unordered data from a randomly sampled position,
combined with GNNs to work with our graph-structured data.

###  3.1 Network architecture

To solve the reverse process, we train a neural network that given noisy
positions $\textbf{X}_{t}$, features H and a time step $t$, it outputs the
noise $\epsilon_{t}$ that is used to calculate $\textbf{X}_{t-1}$. Our network
operates with element features $\textbf{h}^{i}$ that can be extracted from any
pre-trained task-specific backbone. We create a graph structure $G$ where each
node represents an input point and assign
$[\textbf{x}_{t}^{i};\textbf{h}^{i}]^{\top}$ as node features. We input this
graph to our Attention-based GNN backbone, which comprises a stack of four
Graph Transformers layers [31]. Such Graph Transformers use the attention
mechanism on top of a graph structure to control the amount of information
that is gathered from neighboring nodes. The attention is indeed what allows
the network to learn to perform positional reasoning. Fig. 2 summarizes our
architecture.

###  3.2 Forward and reverse process

Figure 3: Visualization of the reverse process for solving puzzles of size 6x6
with both standard and zero-centered initialization. The top part shows a
sample from PuzzleCelebA while the bottom part shows the results with a sample
from PuzzleWikiArt.

Building upon [15], we define the forward process as a fixed Markov chain that
adds Gaussian noise to each input’s starting position
$\textbf{x}_{0}^{k}=\textbf{x}^{k}$ according to a Gaussian distribution. At
timestep $t\in[0,T]$, we adopt the variance $\beta_{t}$ according to a linear
scheduler and define $q(\textbf{x}_{t}|\textbf{x}_{0})$ as:

$q(\textbf{x}_{t}^{i}|\textbf{x}_{0}^{i})=\mathcal{N}(\textbf{x}_{t}^{i};\sqrt{\overline{\alpha}_{t}}\textbf{x}_{0}^{i},(1-\overline{\alpha}_{t})\textbf{I}),$
(1)

where $\alpha_{t}=1-\beta_{t}$,
$\overline{\alpha}_{t}=\prod_{s=1}^{t}\alpha_{s}$. Using this formulation, we
can obtain a noisy position $\textbf{x}_{t}^{k}$ from $\textbf{x}_{0}^{k}$.
The reverse process retrieves the correct position for each data point using
the noisy positions $\textbf{x}_{t}^{i}$, and element features
$\textbf{h}^{i}$.We adopt DDIM [33] algorithm and sample
$\hat{\textbf{x}}_{t-1}$ as:

$\displaystyle\hat{\textbf{x}}_{t-1}=$
$\displaystyle\sqrt{\overline{\alpha}_{t-1}}\left(\frac{\textbf{x}_{t}-\sqrt{1-\overline{\alpha}_{t}}\epsilon_{\theta}(\textbf{x}_{t},\textbf{t},\textbf{h})}{\sqrt{\overline{\alpha}_{t}}}\right)$
$\displaystyle+\sqrt{1-\overline{\alpha}_{t-1}-\sigma_{t}^{2}}\cdot\epsilon_{\theta}(\textbf{x}_{t},\textbf{t},\textbf{h})+\sigma_{t}\epsilon,$

where $\epsilon_{\theta}(\textbf{x}_{t},\textbf{t},\textbf{h})$ is the
estimated noise that has to be removed from $\textbf{x}_{t}$ to recover
$\hat{\textbf{x}}_{t-1}$ and t is a learned vector embedding for timestep $t$.
In the formula, we omit the superscripts $i$ as the network operates on all
elements simultaneously as a graph. DDIM introduces the parameter $\sigma$ to
control the stochastic sampling. As the ordering tasks have only one correct
arrangement, we set $\sigma=0$ to make the sampling deterministic.

Our method is trained using the simple loss for diffusion models introduced in
[15]:

$L_{\text{simple}}(\theta)=\mathbb{E}_{t,\textbf{x}_{0},\epsilon}[\|\epsilon-\epsilon_{\theta}(\underbrace{\sqrt{\overline{\alpha}_{t}}\textbf{x}_{0}+\sqrt{1-\overline{\alpha}_{t}}\epsilon}_{\textbf{x}_{t}},\textbf{t},\textbf{h})\|].$

We calculate $\textbf{x}_{t}$ in closed form from $\textbf{x}_{0}$, using the
reparametrization trick with the noise vector $\epsilon$. The network learns
to minimize the Mean Squared Error between $\epsilon$ and the output
$\hat{\epsilon}=\epsilon_{\theta}(\textbf{x}_{t},\textbf{t},\textbf{h})$.

###  3.3 Zero-centered initialization

In generative diffusion models, the initial $\textbf{X}_{T}$ used during the
reverse process is sampled from $\mathcal{N}(0,1)$. In standard image
generation tasks, this noise introduces stochasticity to synthesize different
images. Differently, the solution in positional reasoning is the true final
arrangement, thus such arrangement should only be influenced by the input
features H and not by the initial $\textbf{X}_{T}$. We found that by setting
$\textbf{x}_{T}=\textbf{0}$, which is the mean of normal distribution, the
network achieves more stable results as verified in the experimental section.
The effect of different sampling on the final position can be observed in Fig.
3. The rearrangement is more precise when $\textbf{x}_{T}=\textbf{0}$. A
quantitative comparison is reported for puzzles, in Tab. 2. We use zero-
centered initialization throughout the experiments.

Task | Position | Data | Feature | Trainable Parameters
---|---|---|---|---
Dim. | Modality | Backbone(s) | Backbone | GNN
Puzzle solving | 2D | RGB | EfficientNet [36] | 6.8 M | 3.2 M
Sentences ordering | 1D | Text | BART [23] | 28.2 M†
Visual storytelling | 1D | RGB | EfficientNet [36] | 31.8 M†
& Text | & BART [23]
2.7 |  |  |  |  |

Table 1: We show the different dimensionality, modality, and number of parameters for each of our downstream tasks. Our Positional Diffusion shares the same structure across tasks. †We report the parameters of the trainable Transformer built on top of the frozen BART model (425 M). Dataset | PuzzleCelebA | PuzzleWikiArts
---|---|---
|  6x6 |  8x8 |  10x10 | 12x12 |  6x6 |  8x8 |  10x10 | 12x12
Paikin and Tal [28] | 99.12 |  98.67 | 98.39 | 96.51 | 98.03 | 97.35 | 95.31 | 90.52
Pomeranz et al. [29] | 84.59 | 79.43 | 74.80 | 66.43 | 79.23 | 72.64 | 67.70 | 62.13
Gallagher [10] | 98.55 | 97.04 | 95.49 | 93.13 | 88.77 | 82.28 | 77.17 | 73.40
PO-LA [46]† | 71.96 | 50.12 | 38.05 | - | 12.19 | 5.77 | 3.28 | -
Ganzzle [35] | 72.18 | 53.26 | 32.84 | 12.94 | 13.48 | 6.93 | 4.10 | 2.58
Transformer [38] | 99.60 | 95.20 | 98.62 | 96.55 | 98.52 | 95.30 | 88.76 | 75.84
Positional Diffusion \- $\mathcal{N}(0,1)$ sampling | 99.72 | 96.78 | 99.28 | 98.55 | 98.52 | 97.15 | 94.34 | 90.26
Positional Diffusion \- Zero-centered initialization |  99.77 | 97.53 |  99.37 | 98.88 |  99.12 |  98.27 |  96.28 | 93.26
2.7 |  |  |  |  |  |  |  |
Table 2: Results on puzzle solving in terms of the _Direct Comparison Metric_
, evaluated with PuzzleCelebA and PuzzleWikiArts. Best. †Trained on individual
puzzle sizes.

##  4 Experiment

We evaluate Positional Diffusion on three tasks that require positional
reasoning with input data of different modalities: i) puzzle solving operates
with visual data to order the shuffled image patches into a complete image;
ii) sentence ordering operates with textual data that aims to order the
shuffled sentences to form a complete and reasonable paragraph; and iii)
visual storytelling operates with textual and visual data and requires to
order sentence-image pairs into a coherent story. Tab. 1 summarizes the
experimental settings. The following sections introduce the detailed
experimental setup for each task regarding the evaluation protocols,
performance metrics, and comparisons. We present more qualitative results in
the Supplementary Materials.

###  4.1 Puzzle solving

(a)

(b)

(c)

Figure 4: Results of 12x12 puzzles solved with Positional Diffusion on
_PuzzleWikiArt_. The predicted positions of patches are visualized next to the
resulting puzzles. The positions are color-coded based on the patch position
in the original image, from the top-left red to the bottom-right green. (a)
The network predicts the positions of all elements correctly. (b) The network
predicts the positions of the patches with slight noises. In this case, the
assignment process maps the noisy positions to their correct slot. (c) The
network wrongly predicts the positions of some patches in a local region.
These positions cannot be recovered by the assignment process.

We follow the experimental setup in Ganzzle [35] and report the results of
Positional Diffusion in comparison to optimization-based and deep learning-
based methods on PuzzleCelebA and PuzzleWikiArts. These two datasets feature a
large number of images which allows for method training with deep learning,
while other puzzle datasets typically only contain $\leq 100$ images.

  * •

PuzzleCelebA is based on CelebA-HQ [21] which contains 30K images of
celebrities in High Definition (HD). The images are cropped and positioned to
show only centered faces. This is an easier dataset for puzzle solving as the
images share a consistent global structure.

  * •

PuzzleWikiArts is based on WikiArts [37], and contains 63K images of paintings
in HD. This dataset contains paintings with very different content and
artistic styles. It represents a more challenging dataset for puzzle solving
as the paintings do not have a common pattern as in PuzzleCelebA (i.e.
portraits).

For both datasets, we test with puzzles of sizes 6x6, 8x8, 10x10, and 12x12.
As the puzzle size increases, the problem becomes more difficult, as the
permutations increase and each piece contains less discriminative information.

Evaluation Metrics. We evaluate the performance of Positional Diffusion using
the _Direct Comparison Metric_ [4], a percentage that indicates the number of
correctly ordered pieces over the full test set. A higher score indicates
better performance.

Implementation Details. We divide an image in $\emph{n}\times\emph{n}$
patches, resulting a total of $\mathit{K}=n^{2}$ elements. We divide a 2D
space with a range of (-1,-1), (1,1) into a grid of $\emph{n}\times\emph{n}$
cells. We use the centers of the cells as starting positions X for the
patches. The input data for puzzle solving are the pixel values for each
patch, resized to 32x32. We use EfficientNet [36] as the task-specific
backbone to extract the patch visual features $\textbf{h}^{i}$ and we train
the diffusion model with $T=300$ and sample it with inference ratio $r=10$. We
train a single model with all puzzle sizes simultaneously.

At inference, we arrange the patches by mapping each estimated patch position
$\hat{\textbf{x}}^{i}$ to a cell in the grid. We measure the distance between
each patch position and cells’ centers, and assign each patch to its closest
cell, mapping each cell to at most one patch. By using a greedy approach that
prioritizes the assignment between cells-patch pairs starting from those with
the lowest distance, we ensure that the most confident prediction will be
assigned first, increasing the prediction robustness to noise.
Comparisons. We compared Positional Diffusion against a set of SOTA methods
for puzzle solving.

  * •

Optimization methods [28, 29, 10] are handcrafted methods for puzzle solving.
They involve computing a compatibility score between all pairs of pieces, to
predict which pieces are neighbors.

  * •

PO-LA [46] uses a neural network to learn a differentiable permutation
invariant ordering cost between a set of patches. The learned cost function is
then used to order the pieces and form the full image.

  * •

Ganzzle [35] employs a GAN to generate a hallucinated version of the full
image from the set of pieces. Then, Ganzzle solves the puzzle as an assignment
problem by matching the patch features with the features extracted from the
generated image at specific locations.

  * •

Transformer is a standard Transformer-based architecture [38] that predicts
the positions of each piece. This method uses the self-attention mechanism to
propagate relevant information between patches.

We present two variants of Positional Diffusion, where one uses the standard
DPM random sampling from $\mathcal{N}(0,1)$, and the other uses the proposed
zero-centered initialization for sampling.

Tab. 2 presents the results of all methods for solving puzzles of various
sizes with the two datasets. On PuzzleCelebA, both the Transformer baseline
and our Positional Diffusion outperform the previous SOTA methods on almost
all puzzle sizes. In particular, Positional Diffusion scores the new SOTA
performance among deep-learning methods on all puzzle sizes, with a
significant improvement against the previous best-performing method Ganzzle
[35], even outperforming classical optimization approaches. Moreover, we
observe that the performance of previous deep learning methods degrades
significantly with the puzzle sizes, while Positional Diffusion only presents
a minor degradation. On 12x12 puzzles, Positional Diffusion achieves
$98.88\%$, $+2\%$ higher than the Transformer baseline, $+86\%$ higher than
Ganzzle, and $+2\%$ higher than the best optimization method. In general,
PuzzleCelebA is an easier dataset for puzzle solving compared to
PuzzleWikiArts as it contains well-centered faces with common global patterns.
Our method can exploit the shared pattern to solve the puzzle, e.g., eyes
position relative to the image. The top part in Fig. 3 clearly shows that
Positional Diffusion can correctly position the eyes, mouth, and hair patches.

On PuzzleWikiArts, we observe that all previous methods achieve worse
performance on all puzzle sizes, among which the deep-learning approaches
almost fail to solve the puzzles. PuzzleWikiArts contains puzzles that are
harder to solve, as they come from paintings with different pictorial styles
and subjects, with little common patterns. Nevertheless, Positional Diffusion
consistently obtains the best performance among all methods, overshooting deep
learning methods by a large margin on all puzzle sizes, i.e., $+1\%$ on 6x6,
$+3\%$ on 8x8, $+8\%$ on 10x10, and $+18\%$ on 12x12 compared to the
Transformer baseline. In particular, Positional Diffusion also outperforms the
optimization-based methods, which require hand-crafted features and greedy
solutions, on all puzzle sizes. Moreover, using the same trained model,
Positional Diffusion with the zero-centered initialization consistently
obtains better performance than using the standard DPM random sampling from
$\mathcal{N}(0,1)$. The advantages can be observed from both datasets on all
puzzle sizes, as shown in Fig. 3. Finally, we show in Fig. 4, three examples
of the puzzles solved with Positional Diffusion on _PuzzleWikiArt_. When the
predicted positions are noisy but still close to their ground-truth positions,
we can recover their correct ordering by the assignment procedure. However,
when the errors are large and systematic, e.g., such as when there is a local
collapse in the prediction, the assignment procedure fails to fix the
positions.

It’s important to note that the Direct Comparison Metric does not reflect the
performance in terms of solving a puzzle as a whole, as it is computed at the
patch level. For example, the Transformer positioned $75.84\%$ patches
correctly on PuzzleWikiArt 12x12, but it only solved $6.64\%$ of the puzzles,
while Positional Diffusion with $93.26\%$ correctly positioned patches solved
$69.32\%$ of puzzles.

###  4.2 Sentence ordering

Method | NeurIPS Abstract | Wikipedia Movie Plots | ROCStories
---|---|---|---
Acc | PMR | $\tau$ | Acc | PMR | $\tau$ | Acc | PMR | $\tau$
TGCM [27] | 59.43 | 31.44 | 0.75 | - | - | - | - | - | -
RankTxNet‡ [19] | - | 24.13 | 0.75 | - | - | - | - | 38.02 | 0.76
B-TSort‡ [30] | 61.48 | 32.59 | 0.81 | - | - | - | - | - | -
BERSON‡ [7] | 73.87 | 48.01 | 0.85 | - | - | - | 82.86 | 68.23 | 0.88
Bart (seq2seq)† [5] | 64.35 | 33.69 | 0.78 | 30.01 | 18.88 | 0.59 | 80.42 | 63.50 | 0.85
Re-BART† [5] | 77.41 | 57.03 | 0.89 | 42.04 | 25.76 | 0.77 | 90.78 | 81.88 | 0.94
BART+Transformer | 70.31 | 36.58 | 0.84 | 48.31 | 22.51 | 0.61 | 71.78 | 44.59 | 0.80
Positional Diffusion | 74.44 | 45.24 | 0.85 | 50.41 | 25.00 | 0.63 | 75.12 | 54.80 | 0.82
2.7 |  |  |  |  |  |  |  |  |
Table 3: Comparison of accuracy, PMR, and tau for various methods on NeurIPS
abstract, Wikipedia Movie Plots, and ROCStories. Best / second best / third
best. $\dagger$ requires fine-tuning BART. $\ddagger$ requires fine-tuning
BERT.

Dataset | Split |  | Length |  | Tokens / sentence
---|---|---|---|---|---
Train | Dev | Test |  | Max | Avg |  | Max | Avg
NeurIPS Abstract | 2.4K | 0.4K | 0.4K |  | 15 | 6 |  | 158 | 24.4
Wikipedia M. P. | 27.9K | 3.5K | 3.5K |  | 20 | 13.5 |  | 319 | 20.4
ROCStories | 78K | 9.8k | 9.8k |  | 5 | 5 |  | 21 | 9.1
2.7 |  |  |  |  |  |  |  |  |

Table 4: Dataset statistics of NeurIPS Abstract, Wikipedia Movie Plots and
ROCStories for sentence ordering.

For sentence ordering, we follow the experimental setup in [5] and report the
results of all compared methods on three common textual datasets (dataset
statistics are in Tab. 4):

  * •

NeurIPS Abstract is obtained from the abstracts of scientific articles
featured at NeurIPS;

  * •

Wikipedia Movie Plots is a collection of plots of popular movies that are
available on Wikipedia;

  * •

ROCStories is a collection of 5 sentences stories regarding everyday events.

Evaluation metrics. We quantify the sentence ordering performances with three
metrics as in [5]:

  * •

Accuracy (Acc.) is the percentage of correctly predicted sentence positions in
an input text.

  * •

Perfect Match Ratio (PMR) is the percentage of the number of correctly ordered
texts over the total number of texts in the test set. Differently from Acc.
which is calculated over individual sentences, PMR measures if the full input
text is ordered correctly.

  * •

Kendall’s Tau ($\tau$) measures the correlation between the ground-truth
orders of sentences and the predicted ones, defined as:
$\tau=1-(2(\\#\text{Inversions}){\binom{K}{2}}^{-1})$, where $K$ is the number
of sentences in an input text, and $\\#\text{Inversions}$ is the number of
discordant pairs.

We report the metrics averaged over the test set. The higher values of the
three metrics indicate better performance of the sentence ordering methods.

Implementation Details. We divide a text into a variable number $K$ sentences
with shuffled orders as the input. To assign the correct positions
$\textbf{x}_{0}$ to each sentence, we evenly sample $K$ positions over the
interval (-1,1), and assigned them to the divided sentences based on their
position in the text. The starting sentence will have the smallest position,
while the ending sentence will have the largest position. We use a frozen pre-
trained BART [23] language model for our task-specific feature backbone, to
which we added a learnable transformer encoder layer at the end. For each
sentence, we prepend a $\langle bos\rangle$ token and pass the sentence to
BART to obtain the token feature as the task-specific feature $\textbf{h}^{i}$
in Positional Diffusion. We train our method with $T=300$ and sample with
inference ratio $r=10$.

Comparisons. We conducted a comprehensive evaluation of Positional Diffusion
against the current best-performing methods BERSON [7], Re-BART [5], and BART
for seq2seq generation as proposed in [5], as well as other baselines
including B-TSort [30], RankTxNet [19], TGCM [27]. We also provide a baseline
that is composed of pretrained BART backbone with a Transformer head.

We report the results of all methods in Tab. 3. Wikipedia Movie Plots has the
largest average number of sentences in a text, which is more than double
compared to that of NeurIPS Abstract and On ROCStories. Positional Diffusion
scores the best Accuracy on Wikipedia Movie Plots, with an improvement of
$+8\%$ over the current SOTA method Re-BART, with on par performance in terms
of PMR and $\tau$. With NeurIPS Abstract, Positional Diffusion is the second-
best performing method in Accuracy and $\tau$, while Re-BART remains the best-
performing method. Finally, on ROCStories, Positional Diffusion performs worse
than BEARSON and Re-BART. Compared to the well-structured texts in NeurIPS
Abstract and Wikipedia Movie Plots, the logical connection among sentences in
ROCStories can be weak in some cases (as shown in Tab. 5). This could be the
main reason why Positional Diffusion struggles to learn positional reasoning.

Moreover, it is important to note that we use the frozen language model BART
to extract features to train our GNN model for positional reasoning. Instead,
Re-BART [5] fine-tunes BART with all sentences simultaneously to predict the
sequence order. In fact, the trainable parameters of Positional Diffusion is
32M parameters for text ordering, which is negligible compared to Re-BART’s
425M.

Sentence | Predicted Pos. | GT Pos.
---|---|---
Tom was driving to work. | (1) | (1)
He got pulled over by a cop. | (2) | (2)
The cop mentioned a busted tail light. | (3) | (4)
Tom asked why. | (4) | (3)
Tom agreed to fix it and only got a warning. | (5) | (5)
2.7 |  |

Table 5: Result of five sentences from ROCStories ordered based on the
positions predicted by Positional Diffusion. On the right is the ground-truth
position in the full text. We highlight in red the wrongly predicted
positions.

###  4.3 Visual storytelling

We finally evaluate Positional Diffusion on a multi-modal task: visual
storytelling, which is harder than text reasoning, as it requires
understanding and relating visual and text inputs. We follow the evaluation
protocol in [1] using the visual storytelling dataset VIST [17]. The dataset
contains stories of sentence-image pairs with each story describing everyday
events, as shown in Fig. 5.
Evaluation metrics. We adopt three complementary metrics for the evaluation as
in [1]:

  * •

Spearman’s rank correlation (Sp.) evaluates the monotonic relationship between
predicted and ground-truth rankings. A higher score indicates better
performance.

  * •

Pairwise accuracy (Pairw.) measures the percentage of pairs of elements with
identical predicted and true ordering. A higher score indicates better
performance.

  * •

Average Distance (Dist.) measures the average displacement of all predicted
elements to the ground truth order. A lower value indicates better
performance.

Figure 5: Successful (top) and failure (bottom) cases for ordering of a visual
story from VIST [17]. The image-sentence pairs are ordered from left to right
as predicted by Positional Diffusion. The numbers indicate the ground-truth
positions of the image-caption in the story.

Implementation Details. In this task, we are given five images with their
related caption that have to be arranged correctly to form a visual story.
Similarly to Sentence Ordering, we divide a 1D space of range (-1,1) into five
segments and assign to each image/text pair the center of its corresponding
segment as the ground-truth position. The images/text at the beginning of the
sequence have a lower position, while those at the end of the sequence have a
larger position. For this task, we extract the image feature using
EfficientNet and extract a text summary for the phrase using BART as done for
the Sentence ordering task. We then concatenate the output of these two models
to obtain the features $\textbf{h}^{i}$. We train Positional Diffusion with
$T=100$ and sample it with inference ratio $r=10$.
Comparisons. We compare Positional Diffusion with Sort Story as proposed by
Agrawal et al. [1]. Sort Story is a combination of Skip-Thought [18] with
pairwise ranking [24], a custom CNN, and Neural Position Embedding module with
LSTM [13]. Agrawal et al. proposed two versions of their approach: an ensemble
that adopts the Hungarian algorithm to find the permutation that maximizes the
ensemble’s voting and a standalone module. We also compare against a
Transformer-based baseline with BART [23] and EfficientNet [36] for the
textual and visual encoding, respectively.

Tab. 6 shows that Positional Diffusion outperforms all the baselines in terms
of the average distance (Dist.). Our approach builds coherent stories with
fewer wrong displacements compared to the ground truth. Positional Diffusion
also performs close to Sort Story [1] in terms of pairwise distance (pairw.)
and correlation (sp.), which measure the global coherence, with only a slight
difference. Note that Sort Story adopts specific design choices including the
pairwise distance between each visual-text pair, an ensemble of modules, and
Hungarian matching algorithm, while our method is solely data-driven and
relies on the reversing diffusion process. Fig. 5 shows some qualitative
results. Our approach produces a coherent story even where the story’s
structure is loose (Fig. 5 top). These results confirm the advantage of our
GNN formulation which enables each node to be coherent with others. In the
failure case in Fig. 5 (bottom), Positional Diffusion correctly predicts (1)
as first and (3)-(4)-(5) in order, while misplaces (2) as the last element of
the story. As a plug-and-play method, Positional Diffusion demonstrates
competitive performance in building a coherent narration with multi-modal
data.

Method |  Sp. $\uparrow$ |  Pairw. $\uparrow$ |  Dist. $\downarrow$
---|---|---|---
Sort Story‡ [1] | 0.67 | 0.79 | 0.72
Skip-Thought + pairwise [1] | 0.56 | 0.74 | 0.89
Transformer [38] | 0.54 | 0.75 | 0.56
Positional Diffusion | 0.63 | 0.77 | 0.51
2.7 |  |  |

Table 6: Performance of different methods on the visual storytelling task.
Best / Second best. $\ddagger$ Ensemble of multiple methods.

##  5 Conclusion

In this work, we proposed Positional Diffusion, a graph-based DPM for
positional reasoning on unordered sets. Positional Diffusion represents the
set as a fully connected graph where each element is a node of the graph. By
using an Attention-based GNN, we update the node features to estimate the node
position. The diffusion formulation allows us to learn the underlying patterns
and iteratively refine the element positions. Positional Diffusion is generic
and applicable to multiple tasks that require positional reasoning regardless
of the data modality and positional dimension, as demonstrated in the
experimental section. We experimented with three ordering tasks: puzzle
solving, sentence ordering, and visual storytelling. Positional Diffusion
reaches SOTA on puzzle solving and comparable results with sentence ordering
and visual storytelling when compared to methods that are specifically
designed for each task.

Acknowledgments We would like to thank Pietro Morerio, Davide Talon, and
Theodore Tsesmelis for helping improving the manuscript and for the useful
discussions.

## References

  * [1] Harsh Agrawal, Arjun Chandrasekaran, Dhruv Batra, Devi Parikh, and Mohit Bansal.  Sort story: Sorting jumbled images and captions into stories.  arXiv preprint arXiv:1606.07493, 2016.
  * [2] Regina Barzilay and Mirella Lapata.  Modeling local coherence: An entity-based approach.  In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05), pages 141–148, Ann Arbor, Michigan, 2005\. Association for Computational Linguistics.
  * [3] Xinchi Chen, Xipeng Qiu, and Xuanjing Huang.  Neural sentence ordering.  arXiv preprint arXiv:1607.06952, 2016.
  * [4] T. S. Cho, S. Avidan, and W. T. Freeman.  A probabilistic image jigsaw puzzle solver.  In IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 183–190, 2010.
  * [5] Somnath Basu Roy Chowdhury, Faeze Brahman, and Snigdha Chaturvedi.  Is everything in order? a simple way to order sentences.  arXiv preprint arXiv:2104.07064, 2021.
  * [6] Baiyun Cui, Yingming Li, Ming Chen, and Zhongfei Zhang.  Deep attentive sentence ordering network.  In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 4340–4349, Brussels, Belgium, 2018. Association for Computational Linguistics.
  * [7] Baiyun Cui, Yingming Li, and Zhongfei Zhang.  BERT-enhanced relational sentence ordering network.  In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 6310–6320, Online, 2020. Association for Computational Linguistics.
  * [8] Prafulla Dhariwal and Alexander Nichol.  Diffusion models beat gans on image synthesis.  Advances in Neural Information Processing Systems, 34, 2021.
  * [9] Micha Elsner and Eugene Charniak.  Extending the entity grid with entity-specific features.  In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 125–129, 2011\.
  * [10] Andrew C Gallagher.  Jigsaw puzzles with pieces of unknown orientation.  In 2012 IEEE Conference on computer vision and pattern recognition, pages 382–389. IEEE, 2012.
  * [11] Jingjing Gong, Xinchi Chen, Xipeng Qiu, and Xuanjing Huang.  End-to-end neural sentence ordering using pointer network.  arXiv preprint arXiv:1611.04953, 2016.
  * [12] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial networks.  Communications of the ACM, 63(11):139–144, 2020.
  * [13] Alex Graves and Alex Graves.  Long short-term memory.  Supervised sequence labelling with recurrent neural networks, pages 37–45, 2012.
  * [14] Camille Guinaudeau and Michael Strube.  Graph-based local coherence modeling.  In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 93–103, 2013.
  * [15] Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  Advances in Neural Information Processing Systems, 33:6840–6851, 2020.
  * [16] Emiel Hoogeboom, Vıctor Garcia Satorras, Clément Vignac, and Max Welling.  Equivariant diffusion for molecule generation in 3d.  In International Conference on Machine Learning, pages 8867–8887. PMLR, 2022.
  * [17] Ting-Hao Kenneth Huang, Francis Ferraro, Nasrin Mostafazadeh, Ishan Misra, Aishwarya Agrawal, Jacob Devlin, Ross Girshick, Xiaodong He, Pushmeet Kohli, Dhruv Batra, C. Lawrence Zitnick, Devi Parikh, Lucy Vanderwende, Michel Galley, and Margaret Mitchell.  Visual storytelling.  In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 1233–1239, San Diego, California, 2016. Association for Computational Linguistics.
  * [18] Ryan Kiros, Yukun Zhu, Russ R Salakhutdinov, Richard Zemel, Raquel Urtasun, Antonio Torralba, and Sanja Fidler.  Skip-thought vectors.  Advances in neural information processing systems, 28, 2015.
  * [19] Pawan Kumar, Dhanajit Brahma, Harish Karnick, and Piyush Rai.  Deep attentive ranking networks for learning to order sentences.  In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 8115–8122. AAAI Press, 2020.
  * [20] Mirella Lapata and Regina Barzilay.  Automatic evaluation of text coherence: Models and representations.  In Leslie Pack Kaelbling and Alessandro Saffiotti, editors, IJCAI-05, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, July 30 - August 5, 2005, pages 1085–1090. Professional Book Center, 2005.
  * [21] Cheng-Han Lee, Ziwei Liu, Lingyun Wu, and Ping Luo.  Maskgan: Towards diverse and interactive facial image manipulation.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
  * [22] Susan C Levine, Kristin R Ratliff, Janellen Huttenlocher, and Joanna Cannon.  Early puzzle play: a predictor of preschoolers’ spatial transformation skill.  Developmental psychology, 48(2):530, 2012.
  * [23] Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer.  BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 7871–7880, Online, 2020. Association for Computational Linguistics.
  * [24] Hang Li.  A short introduction to learning to rank.  IEICE TRANSACTIONS on Information and Systems, 94(10):1854–1862, 2011.
  * [25] Lajanugen Logeswaran, Honglak Lee, and Dragomir R. Radev.  Sentence ordering and coherence modeling using recurrent neural networks.  In Sheila A. McIlraith and Kilian Q. Weinberger, editors, Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 5285–5292. AAAI Press, 2018.
  * [26] Shitong Luo and Wei Hu.  Diffusion probabilistic models for 3d point cloud generation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2837–2845, 2021.
  * [27] Byungkook Oh, Seungmin Seo, Cheolheon Shin, Eunju Jo, and Kyong-Ho Lee.  Topic-guided coherence modeling for sentence ordering by preserving global and local information.  In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 2273–2283, Hong Kong, China, 2019. Association for Computational Linguistics.
  * [28] Genady Paikin and Ayellet Tal.  Solving multiple square jigsaw puzzles with missing pieces.  IEEE CVPR, pages 4832–4839, 2015.
  * [29] D. Pomeranz, M. Shemesh, and O. Ben-Shahar.  A fully automated greedy square jigsaw puzzle solver.  In CVPR 2011, pages 9–16, 2011.
  * [30] Shrimai Prabhumoye, Ruslan Salakhutdinov, and Alan W Black.  Topological sort for sentence ordering.  In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 2783–2792, Online, 2020. Association for Computational Linguistics.
  * [31] Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjing Wang, and Yu Sun.  Masked label prediction: Unified message passing model for semi-supervised classification.  In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2021.
  * [32] Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli.  Deep unsupervised learning using nonequilibrium thermodynamics.  In International Conference on Machine Learning, pages 2256–2265. PMLR, 2015.
  * [33] Jiaming Song, Chenlin Meng, and Stefano Ermon.  Denoising diffusion implicit models.  arXiv preprint arXiv:2010.02502, 2020.
  * [34] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole.  Score-based generative modeling through stochastic differential equations.  arXiv preprint arXiv:2011.13456, 2020.
  * [35] Davide Talon, Alessio Del Bue, and Stuart James.  Ganzzle: Reframing jigsaw puzzle solving as a retrieval task using a generative mental image.  In 2022 IEEE International Conference on Image Processing (ICIP), pages 4083–4087. IEEE, 2022.
  * [36] Mingxing Tan and Quoc Le.  Efficientnet: Rethinking model scaling for convolutional neural networks.  In International conference on machine learning, pages 6105–6114. PMLR, 2019.
  * [37] Wei Ren Tan, Chee Seng Chan, Hernan Aguirre, and Kiyoshi Tanaka.  Improved artgan for conditional synthesis of natural image and artwork.  IEEE Transactions on Image Processing, 28(1):394–409, 2019.
  * [38] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  Advances in neural information processing systems, 30, 2017.
  * [39] Brian N Verdine, Roberta M Golinkoff, Kathryn Hirsh-Pasek, Nora S Newcombe, Andrew T Filipowicz, and Alicia Chang.  Deconstructing building blocks: Preschoolers’ spatial assembly performance relates to early mathematical skills.  Child development, 85(3):1062–1076, 2014.
  * [40] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly.  Pointer networks.  In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 2692–2700, 2015.
  * [41] Tianming Wang and Xiaojun Wan.  Hierarchical attention networks for sentence ordering.  In Proceedings of the AAAI Conference on Artificial Intelligence, number 01, pages 7184–7191. AAAI Press, 2019.
  * [42] Yongjing Yin, Fandong Meng, Jinsong Su, Yubin Ge, Lingeng Song, Jie Zhou, and Jiebo Luo.  Enhancing pointer network for sentence ordering with pairwise ordering predictions.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 9482–9489. AAAI Press, 2020.
  * [43] Yongjing Yin, Linfeng Song, Jinsong Su, Jiali Zeng, Chulun Zhou, and Jiebo Luo.  Graph-based neural sentence ordering.  In Sarit Kraus, editor, Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pages 5387–5393. ijcai.org, 2019.
  * [44] Rowan Zellers, Ximing Lu, Jack Hessel, Youngjae Yu, Jae Sung Park, Jize Cao, Ali Farhadi, and Yejin Choi.  Merlot: Multimodal neural script knowledge models.  Advances in Neural Information Processing Systems, 34:23634–23651, 2021.
  * [45] Yan Zhang, Jonathon Hare, and Adam Prügel-Bennett.  Learning representations of sets through optimized permutations.  In International Conference on Learning Representations, 2019.
  * [46] Yan Zhang, Jonathon Hare, and Adam Prügel-Bennett.  Learning representations of sets through optimized permutations.  In ICLR, 2019.
  * [47] Yutao Zhu, Kun Zhou, Jian-Yun Nie, Shengchao Liu, and Zhicheng Dou.  Neural sentence ordering based on constraint graphs.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 14656–14664, 2021.


# Non-linear inhibitory responses enhance performance in collective decision-
making

David March-Pons<EMAIL_ADDRESS>Departament de Física, Universitat
Politècnica de Catalunya, Campus Nord B4, 08034 Barcelona, Spain  Departament
de Física de la Matèria Condensada, Universitat de Barcelona, Martí i Franquès
1, 08028 Barcelona, Spain.  Romualdo Pastor-Satorras  Departament de Física,
Universitat Politècnica de Catalunya, Campus Nord B4, 08034 Barcelona, Spain
M. Carmen Miguel  Departament de Física de la Matèria Condensada, Universitat
de Barcelona, Martí i Franquès 1, 08028 Barcelona, Spain.  Institute of
Complex Systems (UBICS), Universitat de Barcelona, 08028 Barcelona, Spain

###### Abstract

The precise modulation of activity through inhibitory signals ensures that
both insect colonies and neural circuits operate efficiently and adaptively,
highlighting the fundamental importance of inhibition in biological systems.
Modulatory signals are produced in various contexts and are known for subtly
shifting the probability of receiver behaviors based on response thresholds.
Here we propose a non-linear function to introduce inhibitory responsiveness
in collective decision-making inspired by honeybee house-hunting. We show
that, compared with usual linear functions, non-linear responses enhance final
consensus and reduce deliberation time. This improvement comes at the cost of
reduced accuracy in identifying the best option. Nonetheless, for value-based
tasks, the benefits of faster consensus and enhanced decision-making might
outweigh this drawback.

The behavioral and signaling patterns of social animal groups [1, 2] have
sparked extensive research into collective behavior and decision-making,
primarily to understand the underlying mechanisms that drive these emergent
properties [3]. Inhibitory signals, in particular, play an essential role in
social insects, fine-tuning collective decision-making and coordinating
critical tasks such as house-hunting and foraging [4, 5, 6, 7, 8]. These
inhibitory signals, often communicated through vibrations or tactile
interactions, allow colonies to efficiently allocate resources and labor. For
instance, in honeybees, stop signals can prevent the recruitment of additional
foragers to poor or perilous food sources, thereby optimizing foraging efforts
[4, 5, 6, 7]. Similarly, during nest site selection, bees use stop signals to
halt the promotion of less suitable sites, ensuring that the colony converges
on the best available option [8]. By integrating these stop signals, social
insects enhance their ability to make adaptive and robust decisions,
ultimately supporting the survival and success of the colony. The fascinating
social behavior of honeybees, including their intricate recruiting signaling
patterns such as the waggle dance [9], has inspired the design of
decentralized decision-making algorithms [10, 11, 12, 13, 14], and their
application to robotic systems [15].

According to Nieh [4, 7] and Pastor et al. [5], during foraging tasks,
honeybees’ stop signals can alter the probability of waggle dancers ceasing
their dance and leaving the nest, thereby reducing recruitment. However,
dancers do not exhibit an immediate response to these signals. This feature is
characteristic of modulatory signals, which are known for subtly shifting the
probability of receiver behaviors based on their response thresholds. Lau et
al. [6] further suggested that, depending on receiver response thresholds,
stop signals do not exert a strong colony-wide effect until signaling levels
are sufficiently elevated. A similar mechanism has for long also been observed
in brain neuronal activity [16], where balance between excitation and
inhibition is critical for processes such as sensory perception, motor control
or cognitive functions. Recent efforts have been made in establishing the
similarities between individual decision-making in primate brains and
collective decision-making in social insect colonies [17, 18, 19].

Field experiments on honeybee house-hunting [8] introduced the term cross-
inhibition, as it was demonstrated that stop signals were predominantly
exchanged between agents promoting competing options. Cross-inhibition has
proven essential for resolving deadlocks in decisions between very similar
alternatives [8, 10, 20, 21, 22]. However, as argued in Ref. [22], cross-
inhibition trades accuracy for stability. This means the system can
confidently make a decision for any option, regardless of whether it is the
highest quality one or not. In value-based tasks, this trade-off may not
necessarily be detrimental, as the system prioritizes making a choice that
yields a sufficiently high reward within a limited time, thus balancing the
speed-value trade-off [23, 24, 25, 22]. Furthermore, depending on the
intensity of cross-inhibition, this mechanism may pause the decision-making
process if the qualities of the available options are not deemed high enough,
allowing the system to wait for a potentially better option to appear [10,
12]. Such a system transitions from indecision to decision through pitchfork
or saddle-node bifurcations [26, 14], controlled by the model parameters.

In honeybee-inspired collective decision-making models, the cross-inhibition
rate has usually been considered a linear function of the population sending
the stop signals. This choice represents the simplest modeling assumption,
where the abandonment of one’s opinion is linearly proportional to the
accumulation of stop signals received from peers with opposing options.
However, similar to the foraging behavior of bees discussed earlier, Seeley et
al. also suggested that nest-site scout waggle dances are likely terminated
when stop-signal inhibition surpasses a certain threshold [8]. Motivated by
this experimental evidence, here we investigate the impact of non-linear
inhibitory responsiveness [27, 26, 14] within honeybee-inspired decision-
making models. The response depends on the amount of stop signals received and
diminishes or becomes negligible when stop signals are sparse, see Fig. 1(a).
This approach also aligns with the concept of complex social contagion models
[28, 29], which posits that multiple exposures to a given opinion are required
to trigger a shift in belief. Similarly, our model assumes that a minimum
threshold of stop signals must be reached before cross-inhibition acts.

Focusing on binary decision tasks, we demonstrate that our approach enhances
the consensus formation capabilities of decentralized systems compared to
linear cross-inhibition models, particularly when dealing with options of
similar qualities. The benefits are twofold: first, the final decision is
achieved with virtually no bees committed to the less favored option; second,
the time to reach a stationary state is significantly reduced.

Model – We use a simplified version of the honeybee inspired LES model [30],
which features the typical transition rates of collective decision making
models [10, 11, 12, 13]. In the LES model, a swarm of $N$ scout bees evaluates
$k$ potential nest sites, indexed by $\alpha=1,\ldots,k$. Each site $\alpha$
is characterized by an intrinsic quality $q_{\alpha}\geq 0$ and a spontaneous
discovery probability $\pi_{\alpha}\geq 0$.

Bees can be in any of $k+1$ states: uncommitted or committed to one of the $k$
available sites. The transitions from uncommitted to committed state are
governed by discovery and recruitment rates, representing individual and
social behavior, and balanced by the interdependence parameter, $\lambda$.
Likewise, the transitions from committed to uncommitted states are governed by
abandonment and cross-inhibition rates, which reflect individual and socially
motivated behaviors, respectively.

The model’s mean-field rate equations for the fractions of agents committed to
each site, $f_{\alpha}(t)$, can be derived using the master equation formalism
[31]. Including cross-inhibition, these equations are:

$\displaystyle\dot{f}_{\alpha}(t)$ $\displaystyle=$ $\displaystyle
f_{0}(t)\left[(1-\lambda)\pi_{\alpha}+\lambda f_{\alpha}(t)\right]$
$\displaystyle-$ $\displaystyle
r_{\alpha}f_{\alpha}(t)-\lambda^{\prime}f_{\alpha}(t)\sum_{\beta\neq\alpha}\sigma(f_{\beta}),\
\ \alpha=1,\ldots,k$

where $f_{0}(t)=1-\sum_{\alpha=1}^{k}f_{\alpha}(t)$ is the fraction of
uncommitted bees. The discovery rate, $(1-\lambda)\pi_{\alpha}$, refers to the
rate at which uncommitted bees discover and commit to site $\alpha$, and the
recruitment rate $\lambda f_{\alpha}$ represents the rate at which uncommitted
bees are recruited by peers already committed to option $\alpha$. The rate
$r_{\alpha}$ at which bees stop advertising a site is inversely proportional
to its quality, $r_{\alpha}=1/q_{\alpha}$. Finally, the cross-inhibition rate,
$\lambda^{\prime}f_{\alpha}\sigma(f_{\beta})$ ($\beta\neq\alpha$), is the rate
at which bees abandon their options after receiving stop signals from those
advocating for competing options. Here, $\lambda^{\prime}$ regulates the
intensity of cross-inhibition interactions. For the purposes of this study, we
will set $\lambda^{\prime}=1$ in the following.

The stationary points of the system can be determined by numerically solving
the equations obtained by setting $\dot{f}_{\alpha}(t)=0$ [32]. Without cross-
inhibition ($\lambda^{\prime}=0$), the system simplifies to the expressions
derived in [31], thoroughly analyzed in [33, 32].

Figure 1: (a): Examples of inhibitory responses (see Eq. 2). (b): Bifurcation
diagrams on increasing interdependence $\lambda$ for linear (black circles),
sharp sigmoid $\sigma_{1}(f_{\beta};0.3,500)$ (blue squares), and smooth
bounded sigmoid $\sigma_{2}(f_{\beta};0.3,10)$ (red triangles) cross-
inhibition responses. The case $\lambda^{\prime}=0$ is included as a
continuous line for comparison. Other model parameters are
$\pi_{1}=\pi_{2}=0.1$, $q_{1}=9$, $q_{2}=10$.

Cross-inhibition response – The function $\sigma(f_{\beta})$ determines the
actual strength of the cross-inhibition based on the fraction of bees
$f_{\beta}$ sending stop signals. Traditionally, cross-inhibition, similarly
to recruitment interactions, has been modeled as a proportional response to
the fraction of adversary population, i.e. $\sigma(f_{\beta})=f_{\beta}$. Here
we consider a non-linear cross-inhibition response. Specifically, we propose
two sigmoid-like test functions, where the cross-inhibition strength remains
weak for small values of the inhibiting population:

$\begin{split}\sigma_{1}(f_{\beta};x_{0},a)=\frac{1}{1+e^{-a(f_{\beta}-x_{0})}},\\\
\sigma_{2}(f_{\beta};x_{0},a)=\frac{f_{\beta}}{1+e^{-a(f_{\beta}-x_{0})}}.\end{split}$
(2)

The parameter $a$ controls the steepness of these functions, and $x_{0}$ is a
threshold controlling the sigmoid’s ascent position. Some instances of these
functions are depicted in Fig. 1(a). The function $\sigma_{1}$ captures the
scenario where the cross-inhibition strength increases sharply, similar to a
step function, once the threshold population $x_{0}$ is approached. On the
other hand, $\sigma_{2}$ assumes that the cross-inhibition strength grows sub-
linearly below this threshold and transitions to a limiting linear regime
above it.

Figure 2: Linear vs. non-linear cross-inhibition results in (a binary)
decision scenario. (a): Occupation fraction for the best-quality site,
$f_{2}^{*}$. (b): Probability of reaching the best option, $P(f_{2}^{*})$.
(c): Time to settle into the stationary state, $t_{ss}$. Other parameters are
$\pi_{1}=\pi_{2}=0.1$, $q_{1}=9$, $q_{2}=10$.

In the following, we will focus on the simplest case of a binary decision
between two sites that differ in quality ($q_{1}<q_{2}$). The system’s
dynamics display a different number of stable points for different values of
the model’s parameters. For instance, increasing the strength of the social
interactions leads to an (unfolded) pitchfork bifurcation [34]. This behavior
is shown in Fig. 1(b) for linear cross-inhibition (black-circles), and has
been previously observed in similar models [10, 11, 12]. When switching to non
linear cross-inhibition, a bifurcation still occurs, but its position depends
on the particular response choice. Two examples of this are also shown in Fig.
1(b). The curves with blue squares and red triangles represent results for a
sharp sigmoid function $\sigma_{1}(f_{\beta};0.3,500)$ and a smooth linearly-
bounded sigmoid function $\sigma_{2}(f_{\beta};0.3,10)$, respectively. Results
obtained for other non-linear functions displayed in Fig 1(a) are shown in
Supplemental Figure SF1 [35]. Reducing the strength of cross-inhibition, or
slightly varying the threshold parameter $x_{0}$, produces qualitatively
similar results, though the positions of the bifurcations are shifted. For
bifurcation plots at $\lambda^{\prime}=0.5$, see Supplemental Figure SF2 [35].

Performance measure – To assess the model’s performance with non-linear cross-
inhibition interactions, we numerically evaluate the stationary fixed point
values, focusing on the occupation fraction for the best-quality site,
$f_{2}^{*}$. This quantity represents the decision accuracy of the system.
However, as previously discussed, decision accuracy alone is not the only
relevant variable a system seeks to maximize, especially in value-based
decisions [36, 22, 24]. In scenarios where the available sites are similar in
quality, it may be preferable to make a quick decision rather than spending a
large amount of time to choose a slightly better site. Therefore, in addition
to accuracy, we use agent-based stochastic simulations to measure two
additional performance metrics: (i) the probability $P(f_{2}^{*})$ of reaching
the best option; and (ii) the time $t_{ss}$ required to settle into this
stationary state. These complementary quantities provide a comprehensive
evaluation of the system’s decision accuracy and speed performance.

Figure 2 represents the behavior of these three quantities as a function of
the interdependence $\lambda$ for close values of the sites’ qualities,
$q_{1}=9$ and $q_{2}=10$, for the different cross-inhibition responses. In the
non-linear case, we use the same parameters as in Fig. 1. We can observe that
all non-linear cross-inhibition functions tested outperform the linear cross-
inhibition in terms of pure consensus accuracy. However, the linear approach
provides a higher probability of selecting the better option. These
differences are particularly relevant for small to moderate values of the
interdependence. In this regime, not triggering cross-inhibition unless an
option has gained some representation allows the system to build a stronger
consensus, albeit at the risk of less reliably choosing the better option.
Nonetheless, this comes with the benefit of making a decision in a much
shorter time, as shown in Fig. 2(c). This can be a significant advantage when
choosing between similarly valued options. As reported in [27, 37], quicker
consensus can be achieved by allowing the system to first build sub-
populations of comparable sizes before triggering competition between them. In
those works, this is achieved by time-varying social interaction rates,
including recruitment and cross-inhibition. In contrast, we propose a simpler
time-invariant mechanism that weakens the perception of cross-inhibition
signals unless they are received from a significant portion of the population.
This approach allows both populations to grow without interference from stop
signals. Once the populations reach substantial sizes, cross-inhibition is
triggered, and a faster decision is made.

Each type of sigmoid function is tested with both a sharp response (high
$a=500$ value), where the cross-inhibition rapidly shifts from no effect to
maximum or linear bound, and a smooth response (low $a\in[10,20]$ value),
where the transition to the final bound is more gradual. Interestingly, our
results for the best-quality site occupation fraction show a remarkable
insensitivity to the specific details of the sigmoid functions (see Fig.
2(a)). Moreover, these results are significantly higher for low and moderate
interdependence compared to those of the linear cross-inhibition model. On the
other hand, the probability of reaching the best option is considerably
reduced for sharper cross-inhibitory responsiveness, independently of the
function selected, Fig. 2(b). This is due to the indiscriminate action of
inhibition on the option that first reaches the activation threshold $x_{0}$,
irrespective of its quality. While the smooth sigmoid also yields
probabilities similar to the sharp functions, due to the over-representation
of the inhibiting population when the threshold is trespassed, approaching
smoothly the linear bound grants an intermediate result.

Figure 3: Performance ratio $\chi$ of non-linear cross-inhibitory responses on
increasing interdependence $\lambda$. Other parameters are
$(q_{1}=9.0,q_{2}=10)$ and $\pi_{1}=\pi_{2}=0.1$.

In order to encapsulate the effect of these three measures in a single
quantity we define the objective performance,

$\psi_{\sigma}=\frac{f_{2}^{*}\ P(f_{2}^{*})}{t_{ss}},$ (3)

weighting the three quantities at stake. To assess how non-linear cross-
inhibition compares to linear cross-inhibition, we also introduce the
performance ratio $\chi=\psi_{\sigma}/\psi_{lin}$. Fig. 3 depicts this
performance ratio for the same quality pair as in Fig. 2. We observe a
performance ratio $\chi>1$ for nearly all values of $\lambda$. Moreover, as
depicted in Supplemental Figure SF3 [35] this ratio increases as the site
qualities become closer, indicating a more significant performance improvement
when using non-linear cross-inhibition.

The performance improvement peaks around $\lambda\sim 0.2$, corresponding to
the point where the difference in decision times between linear and nonlinear
models is the greatest. The subsequent performance decrease, on increasing
$\lambda$, is due to the combined effect of interdependence and cross-
inhibition driving the losing population to very low fractions, while the
winning population dominates. In this scenario, the cross-inhibition strength
exerted by the winning population on its adversary becomes similar to that in
the linear model, regardless of the specific non-linear response chosen. The
advantage of the non-linear response is mainly due to the weaker effect of the
losing population’s cross-inhibition. Furthermore, as noted in [32], when
$\lambda\rightarrow 1$, the system can make a strong decision without cross-
inhibition, although incorporating it significantly reduces decision time.

Comparing different non-linear cross-inhibition functions, we find that their
performances are relatively close, with the smooth, linearly bounded sigmoid
being the only one that underperforms. The effectiveness of a strong, sudden
activation of cross-inhibition was previously reported by Talamali et al.
[27], mainly for the choosing accuracy. In contrast, our approach demonstrates
a comprehensive enhancement in both overall consensus accuracy and decision
time.

Figure 4: Performance ratio $\chi$ of non-linear cross-inhibition responses on
increasing the discovery probabilities $\pi_{1}=\pi_{2}\equiv\pi_{1,2}$. Other
parameters are $q_{1}=9$, $q_{2}=10$ and $\lambda=0.6$.

So far, we have tested consensus dynamics by fixing the discovery
probabilities and varying the interdependence. Increasing interdependence
reduces the amount of individual exploration by prioritizing peers’ options.
This strategy has been shown to optimize consensus accuracy, even in the
absence of cross-inhibition [30, 32], although it may extend decision time
[32]. When the discovery probabilities increase (with fixed $\lambda$), the
system more readily incorporates environmental information. This reduces
decision time but leads to poorer final consensus, especially when options are
of similar quality [32]. Thus, $\pi_{\alpha}$ can also be viewed as a noise
parameter. In such scenarios, cross-inhibition is crucial to avoid deadlocks,
as reported in various case studies [10, 11, 20, 22].

Fig. 4 shows the performance ratio of non-linear cross-inhibition responses as
discovery probabilities increase. The corresponding performance variables are
plotted in Supplemental Figure SF4 [35]. As the noise in the system increases,
non-linear cross-inhibition yields better performance. Interestingly,
examining the individual quantities $f_{2}^{*}$ and $t_{ss}$ on increasing
$\pi_{1}=\pi_{2}=\pi_{1,2}$, we observe opposing trends for the linear and
non-linear model. The linear response yields decreasing $f_{2}^{*}$ while
increasing $t_{ss}$; in contrast, non-linear responses reverse this trend.
Consequently, weakening the stop signals from the losing population becomes
essential in this context. Comparing the different non-linear responses, we
observe that the performance is consistently higher for the standard sigmoid
functions than for the linearly bounded sigmoids. In each case, the sharp
response also grants better performance.

Conclusions – In this letter, we investigate non-linear cross-inhibition
interactions in decentralized decision making models inspired by house-hunting
honeybees. The primary design goal is to weaken an individual’s response to
stop signals when they are received from a small fraction of the population.
We model this behavior using two non-linear functions, tested with different
parameters (Fig. 1). Focusing on binary decision tasks, we demonstrate that
non-linear cross-inhibition results in higher consensus (the fraction of the
population committed to the chosen option) and quicker decisions. These two
benefits come at the cost of reducing accuracy in reliably choosing the best
quality option. Nonetheless, in decisions made among options with close
qualities, a stronger and quicker decision for a ”good enough” option may be
more beneficial than a weaker consensus or a slower decision process that
yields the absolute best option [24, 36, 22]. Our results thereby open
promising avenues for future research in decentralized collective decision-
making and practical applications in swarm robotics.

###### Acknowledgements.

We acknowledge financial support from projects PID2022-137505NB-C21 and
PID2022-137505NB-C22 funded by MICIU/AEI/10.13039/501100011033, and by “ERDF A
way of making Europe”.

## References

  * Sumpter [2010] D. J. T. Sumpter,  _Collective Animal Behavior_ (Princeton University Press, 2010).
  * Smith and Harper [2003] J. Smith and D. Harper,  _Animal Signals_ (Oxford University Press, 2003).
  * Bose  _et al._ [2017] T. Bose, A. Reina, and J. A. Marshall, Collective decision-making, Current Opinion in Behavioral Sciences 16, 30 (2017).
  * Nieh [1993] J. C. Nieh, The stop signal of honey bees: reconsidering its message, Behavioral Ecology and Sociobiology 33, 51 (1993).
  * Pastor and Seeley [2005] K. A. Pastor and T. D. Seeley, The brief piping signal of the honey bee: Begging call or stop signal?, Ethology 111, 775 (2005).
  * Lau and Nieh [2010] C. W. Lau and J. C. Nieh, Honey bee stop-signal production: temporal distribution and effect of feeder crowding, Apidologie 41, 87 (2010).
  * Nieh [2010] J. C. Nieh, A Negative Feedback Signal That Is Triggered by Peril Curbs Honey Bee Recruitment, Current Biology 20, 310 (2010).
  * Seeley  _et al._ [2012] T. D. Seeley, P. K. Visscher, T. Schlegel, P. M. Hogan, N. R. Franks, and J. A. R. Marshall, Stop signals provide cross inhibition in collective decision-making by honeybee swarms, Science 335, 108 (2012).
  * Seeley  _et al._ [2006] T. D. Seeley, K. Passino, and K. Visscher, Group decision making in honey bee swarms, American Scientist 94, 220 (2006).
  * Pais  _et al._ [2013] D. Pais, P. M. Hogan, T. Schlegel, N. R. Franks, N. E. Leonard, and J. A. R. Marshall, A mechanism for value-sensitive decision-making, PLOS ONE 8, 1 (2013).
  * Reina  _et al._ [2015] A. Reina, G. Valentini, C. Fernandez-Oto, M. Dorigo, and V. Trianni, A design pattern for decentralised decision making, PloS one 10, e0140950 (2015).
  * Reina  _et al._ [2017] A. Reina, J. A. R. Marshall, V. Trianni, and T. Bose, Model of the best-of-$n$ nest-site selection process in honeybees, Phys. Rev. E 95, 052411 (2017).
  * Gray  _et al._ [2018] R. Gray, A. Franci, V. Srivastava, and N. E. Leonard, Multiagent Decision-Making Dynamics Inspired by Honeybees, IEEE Transactions on Control of Network Systems 5, 793 (2018).
  * Leonard  _et al._ [2024] N. E. Leonard, A. Bizyaeva, and A. Franci, Fast and flexible multiagent decision-making, Annual Review of Control, Robotics, and Autonomous Systems 7, null (2024).
  * Valentini  _et al._ [2017] G. Valentini, E. Ferrante, and M. Dorigo, The best-of-n problem in robot swarms: Formalization, state of the art, and novel perspectives, Frontiers in Robotics and AI 4 (2017).
  * Wilson and Cowan [1972] H. R. Wilson and J. D. Cowan, Excitatory and inhibitory interactions in localized populations of model neurons, Biophys. J. 12, 1 (1972).
  * Passino  _et al._ [2008] K. Passino, T. Seeley, and P. Visscher, Swarm cognition in honey bees, Behavioral Ecology and Sociobiology 62, 401 (2008).
  * Marshall  _et al._ [2009] J. A. R. Marshall, R. Bogacz, A. Dornhaus, R. Planqué, T. Kovacs, and N. R. Franks, On optimal decision-making in brains and social insect colonies, Journal of the Royal Society Interface 6, 1065 (2009).
  * Borofsky  _et al._ [2020] T. Borofsky, V. J. Barranca, R. Zhou, D. von Trentini, R. L. Broadrup, and C. Mayack, Hive minded: like neurons, honey bees collectively integrate negative feedback to regulate decisions, Animal Behaviour 168, 33 (2020).
  * Zakir  _et al._ [2022] R. Zakir, M. Dorigo, and A. Reina, Robot Swarms Break Decision Deadlocks in Collective Perception Through Cross-Inhibition, in  _Swarm Intelligence: 13th International Conference, ANTS 2022, Málaga, Spain_ (Springer-Verlag, Berlin, Heidelberg, 2022) pp. 209–221.
  * Aust  _et al._ [2022] T. Aust, M. S. Talamali, M. Dorigo, H. Hamann, and A. Reina, The Hidden Benefits of Limited Communication and Slow Sensing in Collective Monitoring of Dynamic Environments, in  _Swarm Intelligence_, Lecture Notes in Computer Science, edited by M. Dorigo, H. Hamann, M. López-Ibáñez, J. García-Nieto, A. Engelbrecht, C. Pinciroli, V. Strobel, and C. Camacho-Villalón (Springer International Publishing, Cham, 2022) pp. 234–247.
  * Reina  _et al._ [2023] A. Reina, R. Zakir, G. De Masi, and E. Ferrante, Cross-inhibition leads to group consensus despite the presence of strongly opinionated minorities and asocial behaviour, Communications Physics 6, 1 (2023).
  * Passino and Seeley [2006] K. M. Passino and T. D. Seeley, Modeling and analysis of nest-site selection by honeybee swarms: the speed and accuracy trade-off, Behavioral Ecology and Sociobiology 59, 427 (2006).
  * Pirrone  _et al._ [2014] A. Pirrone, T. Stafford, and J. A. R. Marshall, When natural selection should optimize speed-accuracy trade-offs, Frontiers in Neuroscience 8, 73 (2014).
  * Valentini  _et al._ [2015] G. Valentini, H. Hamann, and M. Dorigo, Efficient decision-making in a self-organizing robot swarm: On the speed versus accuracy trade-off, in  _Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems_ , AAMAS ’15 (IFAAMAS, Richland, SC, 2015) p. 1305–1314.
  * Bizyaeva  _et al._ [2023] A. Bizyaeva, A. Franci, and N. E. Leonard, Nonlinear Opinion Dynamics With Tunable Sensitivity, IEEE Transactions on Automatic Control 68, 1415 (2023).
  * Talamali  _et al._ [2019] M. S. Talamali, J. A. R. Marshall, T. Bose, and A. Reina, Improving collective decision accuracy via time-varying cross-inhibition, in  _2019 International Conference on Robotics and Automation (ICRA)_ (IEEE Press, Montreal, QC, Canada, 2019) pp. 9652–9659.
  * Centola and Macy [2007] D. Centola and M. Macy, Complex contagions and the weakness of long ties, American Journal of Sociology 113, 702 (2007).
  * Watts [2002] D. J. Watts, A simple model of global cascades on random networks, Proceedings of the National Academy of Sciences 99, 5766 (2002).
  * List  _et al._ [2009] C. List, C. Elsholtz, and T. D. Seeley, Independence and interdependence in collective decision making: an agent-based model of nest-site choice by honeybee swarms, Philosophical Transactions of the Royal Society B: Biological Sciences 364, 755 (2009).
  * Galla [2010] T. Galla, Independence and interdependence in the nest-site choice by honeybee swarms: Agent-based models, analytical approaches and pattern formation, Journal of Theoretical Biology 262, 186 (2010).
  * March-Pons  _et al._ [2024] D. March-Pons, E. E. Ferrero, and M. C. Miguel, Consensus formation in quality-sensitive interdependent agent systems (2024), arXiv:2403.14856 [cond-mat.dis-nn] .
  * March  _et al._ [2024] D. March, J. Múgica, E. E. Ferrero, and M. C. Miguel, Honeybee-like collective decision making in a kilobot swarm (2024), [Physical Review Research (in press)], arXiv:2310.15592 [cond-mat.dis-nn] .
  * Gloubitsky and Schaeffer [1985] M. Gloubitsky and D. G. Schaeffer,  _Singularities and Groups in Bifurcation Theory_, Vol. 1 (Springer New York, NY, 1985).
  * [35] Supplementary material for ”Non-linear inhibitory responses enhance performance in collective decision-making”, URL.
  * Pirrone  _et al._ [2022] A. Pirrone, A. Reina, T. Stafford, J. A. R. Marshall, and F. Gobet, Magnitude-sensitivity: rethinking decision-making, Trends in Cognitive Sciences 26, 66 (2022).
  * Talamali  _et al._ [2021] M. S. Talamali, A. Saha, J. A. R. Marshall, and A. Reina, When less is more: Robot swarms adapt better to changes with constrained communication, Science Robotics 6, eabf1416 (2021).