Accelerating Non-Maximum Suppression: A Graph Theory Perspective
Authors: King-Siong Si
Lu Sun
Weizhan Zhang
Tieliang Gong
Jiahao Wang
Jiang Liu
Hao Sun
Venue: NeurIPS 2024 poster (2024)
Keywords: non-maximum suppression
object detection
graph theory
Primary area: optimization

Abstract: Non-maximum suppression (NMS) is an indispensable post-processing step in object detection. With the continuous optimization of network models, NMS has become the ``last mile'' to enhance the efficiency of object detection. This paper systematically analyzes NMS from a graph theory perspective for the first time, revealing its intrinsic structure. Consequently, we propose two optimization methods, namely QSI-NMS and BOE-NMS. The former is a fast recursive divide-and-conquer algorithm with negligible mAP loss, and its extended version (eQSI-NMS) achieves optimal complexity of $\mathcal{O}(n\log n)$. The latter, concentrating on the locality of NMS, achieves an optimization at a constant level without an mAP loss penalty. Moreover, to facilitate rapid evaluation of NMS methods for researchers, we introduce NMS-Bench, the first benchmark designed to comprehensively assess various NMS methods. Taking the YOLOv8-N model on MS COCO 2017 as the benchmark setup, our method QSI-NMS provides $6.2\times$ speed of original NMS on the benchmark, with a $0.1\%$ decrease in mAP. The optimal eQSI-NMS, with only a $0.3\%$ mAP decrease, achieves $10.7\times$ speed. Meanwhile, BOE-NMS exhibits $5.1\times$ speed with no compromise in mAP.

Accelerating Non-Maximum Suppression: A Graph Theory Perspective
King-Siong Si""
Lu Sun Jiahao Wang
Weizhan Zhang Jiang Liu' Hao Sun
Tieliang Gong"
School Computer Science and Technology, MOEKLINNS Lab, Xi'an Jiaotong University
School of Computer Science and Technology, BDKE Lab, Xi'an an Jiaotong University
IInstitute of Artificial Intelligence (TeleAD), China Telecom {sjsinx, sunlu. esw.uusssssst...scoe...oo xu, edu.cn, [zhangwzh, gongt1]@xjia edu. uguisu@stu. xjtu. edu. cn, Jolack_liu_Be 1025, sun. sum.010)@11 010] com
Abstract
Non-maximum suppression (NMS) is an indispensable post-processing step in object detection. With the continuous optimization of network models, NMS has become the "last mile" to enhance the efficiency of object detection. This paper systematically analyzes NMS from graph theory perspective for the first time, revealing its intrinsic structure. Consequently, we propose two optimization methods, namely QSI-NMS and BOE-NMS. The former a fast recursive divide- and-conquer algorithm with negligible mAP loss, and its extended version (eQSI- NMS) achieves optimal complexity of (n log n). The latter, concentrating on the locality of NMS, achieves optimization at constant level without an mAP loss penalty. Moreover, facilitate rapid evaluation of NMS methods for researchers, we introduce MMS-Bench, the first benchmark designed to comprehensively assess various NMS methods. Taking the YOLOv8-N model on MS COCO 2017 as the benchmark setup, our method QSI-NMS provides 6.2x speed of original NMS on the benchmark, with a 0.1% decrease in mAP. The optimal eQSI-NMS, with only a 0.3% mAP decrease, achieves 10.7 7 x speed. Meanwhile, BOE-NMS exhibits 5.1x speed with no compromise mAP.
Introduction
Object detection is highly significant and popular topic in computer vision, widely applied in
various domains, c.g., multiple object tracking [27, 41, 14], medical imaging analysis [42, 36], multimodal object detection [6, 44], and autonomous driving [30, 9, 11]. In recent years, there has been significant attention on the real-time performance of object detection, with notable successes achieved in several research endeavors [34, 31, 26]. non-maximum suppression (NMS) [7] is post-pros post-processing technique used to eliminate duplicate detection boxes and obtain final detections. Some research NMS has indeed enhanced the mean average precision (mAP) of object detection, but they have also introduced additional computational overhead.
Currently, most CNN-based object detection models (such as the R-CNN family [13, 12, 34] and the YOLO series [31, 32, 33, 2]) consist of two parts in the testing phase: model inference and post-processing. In recent years, with the continuous emergence of model lightweighting techniques [17, 39, 8], the time cost model inference has been significantly reduced. As a result, NMS gradually becomes bottleneck in the pipeline of object detection [45]. To address this, some
Equal contribution 'Correspondigg author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

studies [4, 46, 40] have proposed parallelization methods to enhance NMS efficiency. However, these methods do not reduce computational overhead; they rely heavily on efficient parallel computing to reduce overall time costs. The degree of parallelism depends on the hardware environment (such as processor type, quantity, and number of cores) and architecture, leading to significant variations in efficiency when models are deployed across different platforms. Additionally, NMS research lacks a unified evaluation framework for two main reasons. First, existing NMS methods require a complete model inference for each test, consuming significant amount of unnecessary computational resources. Second, different NMS methods are tested on different platforms using various models, making comparisons between different NMS algorithms challenging.
To reduce the computational overhead of NMS, we first map the set of bounding boxes obtained from model inference to a graph G. We then conduct a comprehensive and systematic analysis of the intrinsic structure of NMS from a graph theory perspective. Each box is considered a node in the graph, and the suppression relationships are represented as arcs. We discovered that this forms a directed acyclic graph (DAG), allowing us to solve NMS using dynamic programming. This indicates that long the graph G can be quickly constructed, NMS can be efficiently performed. Through the analysis of G. we find that it contains many weakly connected components (WCCs), and most of them are small. Based on these two characteristics, we propose two optimization strategies. First, due to the nature of dynamic programming, different WCCs are independent. We can use a divide- and-conquer algorithm to break down the problem into smaller subproblems corresponding to these WCCs and solve them recursively. Inspired by quicksort, we propose quicksort induced NMS (QSI- NMS), which provides 6.18x x speed with negligible 0.1% decrease in mAP compared to original NMS in YOLOvv-N [21] on MS COCO 2017 [24]. Furthermore, by analyzing the structure of QSI-NMS, we propose extended QSI-NMS (eQSI-NMS) with complexity of O log n), achieving state-of-the-art performance. Second, leveraging the locality suppression characteristic of NMS, where most weakly connected components are small, we exclude boxes that cannot have suppression relationships through geometric analysis. This led to the development of boxes outside excluded NMS (BOE-NMS), which provides 5.12x speed with no compromise in mAp compared original NMS in YOLOv8-N on MS COCO 2017.
To facilitate the evaluation and comparison of NMS algorithms, introduce NMS-Bench, the first end-to-end benchmark for rapid NMS validation. By decoupling model inference and post- processing, we save substantial computational resources, enabling NMS validation to be completed within minutes. Moreover, by implementing NMS algorithms fairly within this framework, different NMS algorithms can be compared on equal footing. Thus, we integrate data, benchmarking methods, and evaluation metrics into a single framework, enabling end-to-end rapid validation and simplifying NMS research for researchers.
In summary, our contributions are as follows:
We present the first comprehensive analysis of the NMS algorithm from graph theory perspective, uncovering the intrinsic structure of NMS;
We propose two efficient NMS algorithms based the properties of the NMS-induced graph;
We introduce NMS-Bench, the first end-to-end benchmark for rapid NMS validation.
2 Problem Definition
Original NMS, employs the intersection over union (IOU) between bounding boxes the criterion for mutual suppression. Specifically, Given a set of candidate bounding boxes B, original NMS selects the box 6* with the highest confidence score from B, removes it from B, and adds it to the final output set D. Then, it computes IOUs between 5" and all other boxes in B. If the IOU with a certain box b is greater than a given threshold Nr, then b is removed from B. This process is repeated until B is empty.
In general, NMS during prst-procssiig is an algorithm, which takes a list of detection bounding boxes B with corresponding confidence scores S as input, and outputs subset of B. And for convenience, we denote the cardinality of B by n, i.c., = [B. Formally, the NMS algorithm takes

---

(B,S) as input, and outputs sequence K = (k1, .2, ........).. where
K if E D;
4 = otherwise.
And an evaluation function is a mapping e {0, 13" + R. where larger value of e indicates a better NMS. The goal of our research is enhance algorithm efficiency under the condition that
e e(Korigèn) e(K) E,
where represents the tolerance factor and K Kriggin is the output of original NMS algorithm. In the object detection tasks of this paper, we use mAP as the evaluation function e, and we set & to 1%.
Figure I: Dynamic programming in topological sorting. The color of the node represents the d value, ie.. black represents 1, and white represents O. Before suppression, each node black. In topological sorting, traversed arcs are represented by dashed lines, showing they have been removed from the graph. After the topological sorting is completed, we can find that nodes 1, 6, and 8 are all black, that is, the last boxes retained are b,, bg. and bg.
Graph Theory Perspective
The bottleneck of NMS algorithms lies in the extensive computation of IOUs. In practice, many IOUs are smaller than a given threshold N, and will not have any suppressive effect. aim to consider only those IOUs that will affect the final result, thereby reducing the number of computations and improving efficiency. An IOU greater than N, indicates that two boxes have a suppressive effect on each other; otherwise, they are independent. We can treat this relationship as edge in graph, with each box as a node. This graph reflects the intrinsic structure of NMS, representing the connections between all boxes. By this transformation, we can directly analyze the NMS algorithm through the graph. Compared to a set boxes in a two-dimensional plane, the structure the graph is clearer and has more properties that can be utilized.
Specifically, we can regard the input B, S, NMS algorithms as a directed graph G (V.E). That's 's because we can think of every box in B as node in a graph and draw an are from to if box e can suppress box u. Here, we give formal definition.
Definition 1. Given 3-tuple (B, S, Nt) consisting of the bounding boxes, confidence scores and an IOU threshold, a graph G = (V, E) induced by NMS described as follows, there is an injective mapping of B into V that maps each bounding box by in B to node V, and for any ordered pair (v, u),
are (v,u) E E = > 8n A IOU(b, b.) N,
Proposition G is a directed acyclic graph (DAG).
We prove Proposition in the Appendix. Since G is a DAG, we can use dynamic programming to get the answer to NMS, i.e., K. Specifically, let 8(e) be the result of node v, i.e., v is retained if 5(v) = 1, otherwise it's not. In original NMS, if there is a node e that can suppress the current node u, then will not be retained. Therefore, have the dynamic programming equation follows,
1 (V We 8(v))
if d (u) O; otherwise,
8(u)
3

---

where d' (u) denotes the in-degree of u. Ykg Korigin [i], we have
Theorem 1.
h; 8(1)
Theorem shows that we can actually obtain the result through dynamic programming in topological sorting, shown in Figure I. Because result DP depends only on valid topological sorts, which indicates that we do not need to sort confidence scores in descending order like original NMS to get same answer, as long as the topological sort is valid. Additionally, we can observe that there no path from node to node u, then does not influence From this, derive Corollary 1. Corollary 1. If and u are in two different weakly connected components (WCCs) of G, then 8(v) and 8(u) are independent.
14000
|M]
[4]
deg
12000
10000
sketeboard
6000
apple
2000
bus
1000
2000
3000
4000
5000
20
30
40
50
60
70
80
Size WCC
(a)
(b)
Figure 2: Statistical characteristics of graph G MS COCO 2017 validation. 2(a) The scatter plot of 5000 Gs on MS COCO 2017. It indicates that the number of arcs |8| and the number WCCs [WI exhibit an approximately linear relationship with the number of nodes [V. respectively. 2(b) The violin plot of the sizes WCCs across different categories on MS COCO 2017. It reveals the distributional characteristies of the sizes of the WCCs. It shows that over 50% of the WCCs have size less than 5, and more than 75% have a size less than 10.
We find that completing dynamic programming in topological sorting requires O(D) + [E]) time. In real-world data, |&| appears to have a linear relationship to |V] (see Figure 2(a)), once G is determined, NMS can be highly efficient via DP. However, quickly determining G is not simple task. This is because, given bounding box b, it is difficult to quickly determine which boxes in 8 have an IOU > N₂ with A related problem is improving the efficiency of the k-nearest neighbors algorithm (kNN), where [22, 10, 19, 1] have made significant progress. However, IOU is the distance defined by norms, and we can only approximate G through related algorithms. We tried the latest research [10], but it provided little help in acceleration due its large constant.
complex than
Fortunately, The NMS task quite special, as input comes from well-trained models, meaning that bounding boxes will cluster around many possible object locations, and bounding boxes predicted as different objects are independent of each other. This implies that G is a sparse graph with many WCCs, as shown in Figure 2(a). Additionally, we find that most of the WCCs are quite small, as shown in Figure 2(b). These two observations respectively suggest two optimization strategies (see Figure 3). Firstly, because WCCs are independent of each other, algorithm to break down many WCCs into fewer WCCs, continuously reducing the problem size to improve computational efficiency. Thus. we design QSI-NMS. Secondly, because most WCCs quite small in size, we can reduce the cost of constructing ares by geometric knowledge, leading to the design of BOE-NMS.
wovide-and-conueee
4 Methodology
Following the graph-theoretic analysis of NMS Section 3, we propose two optimization methods based on two distinct characteristics of graph G. Our approach is to design algorithms through the

---

analysis of these characteristics to quickly construct & or an approximate graph 9 = (V. = g.
enabling the use of dynamic programming in topological sorting obtain NMS results.
QSI-NMS
BOB-NMS
The key ideas behind QSI-NMS (left) and BOE-NMS (right). 9 (middle) contains many small weakly connected components (WCCs). QSI-NMS considers the global structure of the graph G, where there are many WCCs. It selects pivot (the red node on the left) and computes IOUs (orange edges) with all current subproblem nodes using a divide-and and-conquer algorithm. BOE-NMS focuses on the local structure (the red dashed box) of G. where most WCCs are quite small in size. It selects a node (the red node on the right) and only computes IOUs (orange edges) with its nearby nodes (solid arrows), which is derived from 2D plane geometric analysis (dashed arrows).
Figure 3:
4.1 QSI-NMS
We observe that graph G contains many WCCs, and according to Corollary 1, these components do not affect each other. This implies that, unlike the original NMS, which processes bounding boxes sequentially after sorting by confidence scores and is therefore very slow, we can solve the problem more efficiently using a divide-and-on -oonque algorithm, breaking it down into independent subproblems that can be solved recursively. Inspired by quicksort, we design quicksort induced NMS (QSI-NMS).
In each subproblem on B, we can similarly select pivot and calculate IOUs between the pivot and all the other boxes in B, thereby constructing some arcs in G. Next, devise partitioning criterion to split B {pivot} into two disjoint sets, Bi and B,,, which are then solved recursively. Since IOUs are calculated between boxes in By and B,, some ares in the original might be missed. Therefore. need to carefully choose the pivot and partitioning criterion ensure that the constructed 9 is as similar to G as possible.
For the pivot selection, need to define a priority to choose the best pivot in B. We find that selecting nodes with an in in-degree of 0 in & is optimal for two main reasons. First, node to with an in-degree of 0 belongs some WCCs, and since most nodes in WCC predict the same object, vo with the maximum confidence score will suppress most nodes, meaning has many outgoing arcs. Choosing other nodes in the WCC might allocate vp successors different subsets, leading to significant discrepancies between & and g'. Second, according to De Morgan's laws, the value of 5()) is essentially the conjunction of the negations of the predecessors? 8 values, formally described as follows:
8(1)
A
-(())
This implies that missing an are (Vo, v) could result in 5(v) being incorrectly computed as 1, causing chain reaction that significantly deviates K from Korigin According to Definition 1, the node
5

---

2" E V corresponding to the box d' E B with the highest confidence score has an in-degree of O. Hence, we select the box b' with the highest confidence score as the pivot.
For the partitioning criterion, we need to consider the spatial characteristics of different WCCs. Different WCCs are relatively dispersed in 2D space, on the positions of the boxes. We represent the position of box by its centroid, as it is intuitive and representative. Since the centroid is an ordered pair (æz, y). we can compare directly like real numbers. We need to define preorder in IR². We find that different preorders have negligible effects on mAP. See Appendix C.4 for details. We finally adopt the Manhattan distance to the origin O(0, 0). ie., the L' norm, as the comparison standard. Formally, we define a homogeneous relation 3M on R
define the partitioning criterion based
(z), v1) Zas (22, 122 + |x1] + 18 S |22 + 1uz/
Finally, we partition the set \ {b" } as follows:
{ B = (belbe IM ABEEBY {b*}}:
B, [bolbe AM by ABAEB {b*}}.
where be and ,y, denote the centroid of and b", respectively. Since we always choose the box with the highest confidence score, this creates a valid topological sort of G. Thus, we can avoid explicitly constructing G. further reducing computational overhead. The pseudo-code for QSI-NMS can be found in the Appendix.
eQSI-MMS Taking (n Time Though QSI-NMS performs very well in the real world, is not an (n log n) algorithm for the simple reason that the pivot is not chosen randomly. By analyzing the structure of QSI-NMS, we further optimize it and propose extended QSI-NMS (eQSI-NMS), which only takes On log n) time. Since in carrying out QSI-NMS we always split the problem into two subproblems, we can thus construct binary tree.
Definition 2. Given 3-tuple S, N:), QSI-tree for B denoted by QB(B) is a binary tree defined recursively as follow:
Its root is a node corresponding to the box by E B with maximum confidence 8
Its left subtree is QB((;,), where B₁ is the left subset of in QSI-NMS.
Its right subtree is (B,)., where B, is the right subset of B in QSI-NMS.
The basic case is that if B is empty, then QSI-tree is also empty, i.e., QT(0) 0.
An example of QSI-tree is shown in Figure 4. QSI-tree reveals the inherent structure of QSI- NMS, allowing us consider QSI-NMS from high-level perspective. More generally. in QSI- NMS, tag each box with an ordered pair (p. c). where E P represents the priority and E C is the key used for partitioning. We define preorder relations Ipp on 'P and Ic on C. This indicates that the QSI-tree is essentially binary search tree that satisfies the max-heap property: the priority of the parent node not less than that of the child nodes, the keys in the left sub- tree are all less than or equal to the parent node, and the keys in the right subtree are all greater than the parent node. Furthermore, we have the following Theorem 2.
centroid
Figure 4: A Cartesian tree for B. The x-axis rep- resents the centroid, where the node on the left Ze the one on the right. The y-axis represents the confidence score, where the node below Ep the one above. The values of the sequence below the x-axis are the confidence scores B.
We sort all the elements of in ascending order of boxes' centroids according to the preorder Zc into a sequence:
Theorem 2.
B (bi big...., bt.)):
then QSI-tree is a Cartesian tree for B in which each key is the confidence score of the corresponding box.

---

According to the dynamic programming, if a node can affect the result 6(u) of node u, there must exist a path between v and u. In QSI-NMS, this manifests node u only being able to influence nodes within its subtrees in QSI-tree. Theorem 2 states that QSI-tree is a Cartesian tree, indicating that the subtree of corresponds
contiguous interval B, as shown in Figure 4.
Specifically, the subtree of corresponds to the contiguous interval B +1 : 1] in B, where 4 the last position before v that greater than Sy, and r. is the first position after v that is greater than Sy. Finding (1,, rv) for all is known as the all nearest greater values problem, which can be solved (n) time by maintaining a stack. Similarly QSI-NMS, we can complete the suppression during the algorithm. Therefore, we obtain the following time complexity:
On log + n) On n..
According to our best knowledge, this algorithm is the most optimal in terms of complexity. The pseudo-code can also be found in the Appendix.
4.2 BOE-NMS
We find that the vast majority of WCCs in G are very small, as shown in Figure 2(b). This is because there are many bounding boxes predicting the same object, and NMS a form of local suppression. We hope to consider the locality of box distributions, so that the currently selected box only computes IOUs with boxes corresponding to nodes in the same WCC, rather than computing IOUs with all boxes as in original NMS.
We focus the spatial locality of boxes. We found that box is likely to have large IOUs only with neighbors that are relatively close to in 2D space, which also indicates that G is a sparse graph. Formally, have the following theorem:
Theorem 3. Given a bounding box by E B, vb E B, we have 1OU(b", ,)) S 2 if the centroid of does not lie within b*. Formally,
< D/t =1(1))) v (v.") yrb v ve < yu ( x > xxb x
(b')
(6*)) denote the coordinates of the centroid of b, the left-top and the right-bou fightboottom corners of b², respectively.
where (xee Vc (m/e Vhe ,
(1)),
(b7)
(6-))
and
(1)) (x .rb
Since N, is usually greater than 0.5, e.g.. 0.7 for YOLOv8 and Faster R-CNN. By Theorem 3 we can check IOUs only for those boxes whose centorids lie within the current box. Based on this, we propose boxes outside excluded NMS (BOE-NMS), a method devoid of mAP loss.
In BOE-NMS, We first sort the boxes by their centroids according lexicographic order 36 on R which is defined as follows:
(I,,3) 31) 5r. (I2, v2) <> (x) < x2) V (x1 = 12 A S 32).
Then for the current box 6", we can find all the boxes whose centroids may lie in 6* in Ollog n) time, and we just need to check one by one whether the IOUs between and these boxes are greater than Nr. The pseudo-code for BOE-NMS is described in Algorithm 3 which can be found in the Appendix. Let's set aside Theorem 3 for now. A more intuitive but weaker conclusion is that if two boxes do not intersect, their IOU must be O. However, this is not conducive to efficient implementation because of the high cost of maintaining the corresponding data structure. We discuss this issue in the Appendix.
N₂ is typically set to 0.7, and the method based on Theorem does not introduce errors. We also provide tighter bound to further optimize BOE-NMS. Based Theorem which a generalization of Theorem 3, we can handle cases where N, is any real number E (0, 1).
Theorem 4. We use denote a scaling factor, and then we can use a s) to represent the new box b' obtained by scaling b. Formally,
(b')
(b)
(b)
Ttt x6
x
Fig
(b') (8)
+ x (6)
x Frb = Ir.
Ic.
(8') = ye s x lvte
(6)
(b)
Dic
ya
Urb ye + (b)
ye (b)
Given any N2 E (0, 1), the centroid of 6 does not lie within a(b", 1/N. 1), then IOU(b, b*) S No.
7

---

Since BOE-NMS only excludes boxes with IOU < N₁, the graph constructed by the BOE-NMS is the same as G. In other words, the results of BOE-NMS are identical to original NMS. However, unlike original NMS, BOE-NMS does not need to compute IOUs with all remaining boxes but rather determines the boxes that could potentially be suppressed in Oloo n) time. Next, inspect each of these t (t z size of the corresponding WCC) boxes one by one in (tt) time. As shown in Figure 2(b), the sizes of weakly connected components are almost all less than a constant, say 10. This means that the actual performance of BOE-NMS approaches linear time complexity, but strictly speaking, the complexity still O(n²).
5 Experiments
In this section, we first introduce NMS-Bende the first end-to-end benchmark for rapid validation of NMS algorithms. Next, we validate our algorithms on NMS-Bench and compare them with classical algorithms: original NMS [7], Fast NMS [4], and Cluster-NMS [46]. We conduct tests on MS COCO 2017 [24] and Open Images V7 [23] using YOLOv5 [20], YOLOv8 [21], and Faster R-CNN [12] as validation models. More experimental details can be found in the Appendix.
5.1 NMS-Bench
is robust framework that allows researchers to evaluate various NMS methods over different models and datasets in few minutes. MMS-Bench primarily consists of three components: original bounding box data without NMS applied, implementations of various NMS algorithms as benchmarking methods, and evaluation metrics. The code for NMS-Bench is available on GitHubl,
For the original boxes, we extracted non-NMS boxes using different models (YOLO series [31, 21J and Faster R-CNN [12]) on various datasets [24, 23] to create the MMS-Bench dataset, thereby decou- pling the model inference and post- poss-processing stages. This approach saves significant computational resources during inference. We provide a large amount of data for testing, including original boxes from total of 273,100 images. More detailed information can be found in the Appendix.
implements classical algorithms such as original NMS [7]. Fast NMS [4], Cluster-NMS [46], and PSRR-Mann and BOE-NMS are also included in MARR-MaxpoolNMS [43]. QSI-NMS (including eQSI-NMS) These methods enable researchers to reproduce and study NMS algorithms. All algorithms are implemented fairly. Researchers can also quickly implement and validate their own NMS algorithms, as NMS-Bench a plug-and-play end-to-end benchmark.
For benchmarking methods,
For evaluation metrics, we use COCO-style mAP as the accuracy metric and average processing latency per image as the efficiency metric. The latency calculation begins from the input of bounding boxes and ends when the retained bounding boxes are output. For dataset containing N images, latency is measured by using the bounding boxes generated per image as input, and the total latency for the N images averaged. To mitigate random errors, this measurement is repeated times, and the average of these measurements is used as the final average latency.
5.2 Results
In Table 1, we compare our methods with some mainstream work MS COCO 2017. We observe that our methods, particularly EQSI-NMS, demonstrate substantial performance enhancements in processing speed across different models on MS COCO 2017. eQSI-NMS stands out by offering up to 16.9x speed of original NMS, 4.3x speed of Fast NMS, and 8.9x speed of Cluster-NMS with mAP decrease of about 0.5%. Similarly, QSI-NMS provides 8.8x speed of original NMS, 2.2x speed of Fast NMS, and 4.6x speed of Cluster-NMS with a marginal mAP decrease of about 0.2%. BOE-NMS also shows significant enhancements, being 9.1 x as fast original NMS, 2.3x fast as Fast NMS, and 4.8x as fast as Cluster- with no mAP decrease.
Table 2 shows that on Open Images V7, eQSI-NMS provides approximately 10.2x speed of original NMS, 3.7 speed of Fast NMS, and 7.0x speed of Cluster-NMS. QSI-NMS is about 5.6x as fast as original NMS, 2.0x as fast as Fast NMS, and 3.9x as fast as Cluster-NMS. Similarly, BOE-NMS
8

---

achieves 5.4x speed of original NMS, 2.0x speed of Fast NMS, and 3.8x speed of Cluster-NMS. On Open Images V7, QSI-NMS and eQSI-NMS perferm well in mAP with about 0.2% mAP decreasing.
Table 1: NMS Methods Performance MS COCO 2017
Model
Size
Target
original NMS
Fast NMS
Cluster-NMS
BOE-NMS
QSI-NMSS
eQSI-NMS
Average I Latency (2s)
906-9
321.4
600.8
176.8
146.8
85.0
AP5.0:0.95
Average Latency (as)
531.2
232.5
421.5
126.1
109.4
63.4
AP 0.5::9995 (%)
44,8
44,6
44.8
44.8
44.6
44.5
YOL.0v8
Latency
202.6
348.5
AP 0.5-0.95 (%)
50.2
50.0
50.2
50.2
50.0
49.9
Average Latency (2s)
196.5
51.3
90.7
82.1
67.1
39,0
AP 0.50099
52.8
Average Latency (as)
183.0
148.6
262.2
69.2
66.8
39,6
AP 0.5:0.98 (%)
53,9
53.7
53.9
53.9
53.8
53.6
Latency
10034.2
1724.2
339.0
AP 0.5:0.95 (%)
27.8
27.6
27.8
27.8
27.5
27.4
Average L Latency (2s)
4441.4
996.4
2152.5
438.1
449.2
226.5
AP A.0.00099 95
37.2
36.6
YOLOv5
Average Latency (2s)
AP 0.5.000.95 (%)
3351.6
45.1
874.1
44.8
1851,2
45.1
350.5
45.1
108.3
44,9
204.9
44,5
Average Latency
2531.2
732.8
1484.2
28653
178.4
0,5:0.95 (%)
48.8
48.4
48.8
48.8
48.6
48.2
Average Latency (2s)
1959.1
630.8
1273.9
248.5
314.7
160.3
AP A.5000995
50.5
50.1
50.5
50.5
50.3
Paster R-CNN R50-PPN
Average Latency (2s)
AP 0.5:0.99 (%)
39.8
57.2
112.0
39.9
184.4
39.8
41.1
39.8
36.6
39.5
25.7
39.1
Average Latency
175.8
23.9
0,5.0.95 (%)
41.8
41.7
41.8
41.8
41.5
41,4
Average Latency (2s)
39.7
95.8
169.7
31.9
30.1
21.4
Faster R-CNN XIGI-FUN
AP 0.5:0.9
43.0
42.8
43.0
43.0
42.7
42.5
Table 2: NMS Methods Performance on Open Images V7
Model
Size
Target
original NMS
Fast NMS
Cluster-NMS
BOE-NMS
QSI-NMS
eQSI-NMS
Average Latency (us)
1627.9
498.1
952.4
260.2
231.8
132.3
N
AP 0.5:0.9. (%)
18.1
18.2
18.1
18.1
18.1
18.0
S
Average Latency (jus)
1212.1
412.8
781.6
214.7
199.5
111.2
0.5:0.95 (%)
27.3
27.3
27.3
27.1
27.1
Average Latency (ju)
1003.3
371.6
744.0
191.9
189.0
100.6
YOLOv8
0.5:0.95 (8)
33.1
33.1
33.1
32.9
Average Latency (uu)
853.1
350.5
665.6
175.0
180.3
100.8
0.5:0.0000 95 (%)
34.4
344
34.4
34.4
34.3
34.2
Average Latency (jo8)
80134
342.0
648.8
168.5
173.2
95.1
AP 0,5:0.95 (%)
35.9
35.8
35.9
35.9
35.8
35.7
Table 3: Comparisons of Our Methods and PSRR-MaxpooINNA
Target
original
PSSRR-MaxpooNNMS
BOE-NMS
QSI-NMS
N Average Latency (28)
8568.5
599.6
906.2
628.0)
325.6
0.5:0.9 (8)
27.8
26.5
27.8
27.5
27.4
YOLOv5
$
Average Latency (ps)
3858.2
409.4
547.7
408.2
217.5
AP 0.5:0.95 (%)
37.2
35.6
37.2
36.9
36.6
Average Latency (px)
371.3
AP 0.5:0.95 (%)
45.1
43.1
45.1
44,9
4-,55
R50-FPN
Average Latency (2s)
AP 0.5:0.95 (%)
39.8
37.5
39.8
39.5
39.3
Faster R-CNN RIOL-PPN
Average Lasency (as)
45.5
86.4
38.6
31.9
23,0
Faster R-CNN XI01-FPN
Average Latency (2s)
AP 0.5:0.99
43.0
37.0
40.5
86.9
43.0
33.4
42.7
28.6
42.5
211.6
MaxpoolNMS [5] and ASAP-NMS [38] are only applicable the first stage of two-stage detectors, while the problem we are discussing is more general, so we do not include them in our comparison. MERR-MaxpooINMS [43], which is applicable to anchor-based models. We conduct experiments on anchor- based models (Faster R-CNN and YOLOv5) using MS COCO 2017, and the results shown in Table 3. As
We compare methods with PSRR-Maxpond wettooooaaoooooaaaaaa
see, eQSI-NMS achieves the lowest latency while maintaining a favorable trade-off with mAP. However, PSRR BORR-MaxpoolNMSS experiences 1 2% mAP loss in the Faster R-CNN and YOLOv5 models.
In the case of Faster R-CNN, the latency performance MERR-MaxpooNNMS is not competitive. This because PSRR- MERR-MaxpoolNMS requires max-pooling operations, which, although not affecting the

---

algorithm's complexity, introduces a large constant factor that hampers efficiency when the number of bounding boxes is small (e.g.. the average number of bounding boxes the three Faster R-CNN models is less than 300). However, it performs well when the number of bounding boxes is large (e.g., YOLOv5-$ has an average of 2898 bounding boxes). This demonstrates that the speedup of ISRR-MaxpooINMS is highly dependent on the degree of parallelism, whereas our methods directly reduce computational overhead (see Figure 5 in Appendix D.3), making it hardware-agnostic and suitable for resource-constraine edge devices.
6 Related Work
NMS algorithm is widely used in object detection tasks [35, 31, 34], Original NMS [7] operates on greedy principle, suppressing bounding boxes with an Intersection over Union (IOU) higher than a given threshold, starting from the ones with the highest confidence scores. On one hand, numerous improvements have been made to NMS to achieve higher mAP in certain scenarios [3, 29, 16, 25, 47, 18, 37J. On the other hand, some research focuses on enhancing speed. Fast NMS [4] improves NMS efficiency by avoiding the sequential processing of bounding boxes that need to be suppressed, making it more conducive to parallel computing and thus speeding up the process, though may slightly reduce accuracy compared to original NMS. Cluster-NMS [46], employs matrix operations and iterative processing, running the Fast NMS algorithm in each iteration to accelerate the original NMS without compromising accuracy. MaxpooINMS [5] and ASAP-NMS [38] take into account the setting of "anchors" in the region proposal network (RPN) of two-stage detectors. MaxpoolNMS maps anchors of different sizes onto several score maps and performs spatial max- max-pooling these score maps to avoid calculating IOUs, thereby improving the speed of NMS. ASAP-NMS eliminates some boxes with relatively small IOUs by precomputing the IOUs between the current box and neighboring anchors. PSRR- MRRR-MaxXOlINMS [43] improves upon MaxpooINMS by introducing Relationship Recovery, which addresses the issue of score map mismatch that may arise in MaX, enabling PSRR-MaxpoolNN
to be used in the second stage of two-stage detectors. CUDA NMS by torchvision [28] is a CUDA implementation of the original NMS, leveraging a GPU to accelerate computation-inteesiiee tasks, though it cannot be used in scenarios without GPU.
7 Conclusion
In this paper, systematically analyze the NMS algorithm from graph theory perspective and discover strong connections between NMS, directed graph topological sorting, dynamic programming. and weak connected components. Through these analyses, we first propose QSI-NMS, a fast divide- and-conquer algorithm with negligible loss, and its extended version, eQSI-NMS, achieves the state-of-the-arr complexity O(n log n). Additionally, starting from the sparsity of graphs, design BOF-NMS, which considers the locality suppression feature of NMS, optimizes the NMS algorithm constant level, and maintains precision. Furthermore, we introduce NMS-Bench the first end-to- end benchmark integrating bounding box datasets, NMS benchmarking methods, and evaluations, facilitating NMS research for researchers. Finally, we conducted experiments on NMS-Bench, and the experimental results validated our theory, demonstrating the superiority of our algorithms.
A Acknowledgements This work was supported in part by the National Natural Science Foundation of China under Grant 62192781, Grant 62172326 and Grant 62137002, and in part by the Project of China Knowledge Centre for Engineering Science and Technology.
References
[1] Alina Beygelzimer, Sham Kakade, and John Langford. Cover trees for nearest neighbor. In Proceedings of the 23rd International Conference on Machine Learning, pages 97-104, 2006.
[2] Alexey Bochkovskiy, Chien-Yao Wang, and Hong-Yuan Mark Liao. Yolov4: Optimal speed and accuracy of object detection. arXiv preprint arXiv:2004. 10934, 2020.
[3] Navaneeth Bodla, Bharat Singh, Rama Chellappa, and I Larry S Davis. Soft-nms - -improving object detection with one line of code. In Proceedings of the IEFE/CVF International Conference on Computer Vision, pages 5561-5569, 2017.
10

---

[4] Daniel Bolya, Chong Zhou, Fanyi Xiao, and Yong Jae Lee. Yolact: Real-time instance segmentation. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9157-9166, 2019.
[5] Lile Cai, Bin Zhao, Zhe Wang, Jie Lin, Chuan Sheng Foo, Mohamed Sabry Aly, and Vijay Chandrasekhar, Maxpoolnms: Getting rid of nms bottlenecks in two-stage object detectors. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9348-9356, 2019.
[6] Yue Cao, Junchi Bin, Jozsef Hamari, Erik Blasch, and Zheng Liu. Multimodal object detection by channel switching and spatial attention. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 403-411, 20233.
[7] Navneet Dalal and Bill Triggs. Histograms of oriented gradients for human detection. In Proceedings of the IEEE Computer Society Conference Computer Vision and Patter Recog- nition, volume 1, pages 886-893, 2005.
[8] Xiaohan Ding, Xiangyu Zhang, Ningning Ma, Jungong Han, Guiguang Ding, and Jian Sun. Repvgg: Making vgg-style convnets great again. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 13733-1378 2021.
[9] Piotr Dollár, Christian Wojek, Bernt Schiele, and Pietro Perona. Pedestrian detection: A bench- mark. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 304-311, 2009.
[10] Yury Elkin and Vitaliy Kurlin. new near-linear time algorithm for k-nearest neighbor search using compressed cover tree. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pages 9267-9311, 2023.
[11] Andreas Geiger, Philip Lenz, Christoph Stiller, and Raquel Urtasun. Vision meets robotics: The kitti dataset. The International Journal of Robotics Research, 32(11):121--123) 2013.
[12] Ross Girshick. Fast r-cnn. In Proceedings of the IEEE International Conference on Computer Vision, pages 1440-1444 1408, 2015.
[13] Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik. Rich feature hierarchies for accurate object detection and semantic segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 580-587, 2014.
[14] Mei Han, Amit Sethi, Wei Hua, and Yihong Gong. A detection-based multiple object tracking method. In Proceedings of the International Conference on Image Processing, volume 5, pages 3065-3080 2004.
[15] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick. Mask r-cnn. In Proceedings of the IEEE International Conference on Computer Vision, pages 2961-2969, 2017.
[16] Yihui He, Chenchen Zhu, Jianren Wang, Marios Savvides, and Xiangyu Zhang. Bounding box regression with uncertainty for accurate object detection. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2883 2892, 2019.
[17] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. arXiv preprint 10Xiv:1503.02531, 2015.
[18] Jan Hosang, Rodrigo Benenson, and Bernt Schiele. Learning non-maximum suppression. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4507-4515, 2017.
[19] Mike Izbicki and Christian Shelton. Faster cover trees. In Proceedings of the 32nd International Conference on Machine Learning, volume 37, pages 1172-1170, 2015.
[20] Glenn Jocher. YOLOv5 by Ultralytics, May 2020.
[21] Glenn Jocher, Ayush Chaurasia, and Jing Qiu. Ultralytics YOLO, January 2023.

---

[22] Thomas Kollar. Fast nearest neighbors. Technical report, Computer Science and Artificial Intelligence Lab, 2006.
[23] Alina Kuznetsova, Hassan Rom, Neil Alldrin, Jasper Uijlings, Ivan Krasin, Jordi Pont-Tused Shahab Kamali, Stefan Popov, Matteo Malloci, Alexander Kolesnikov, Tom Duerig, and Vittorio Ferrari. The open images dataset v4: Unified image classification, object detection, and visual relationship detection at scale. International Journal of Computer Vision, 2020.
[24] Tsung-Yi Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. Microsoft coco: Common objects in context. In Proceedings of the European Conference on Computer Vision, pages 740-755, 2014.
[25] Songtao Liu, Di Huang, and Yunhong Wang. Adaptive nms: Refining pedestrian detection in a crowd. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 6459-6468, 2019.
[26] Wei Liu, Dragomir Anguelov, Dumitru Erhan, Christian Szegedy, Scott Reed, Cheng-Yane Fu, and Alexander Berg. Ssd: Single shot multibox detector. In Proceedings of the European Conference Computer Vision, pages 21-37, 2016.
[27] Wenhan Luo, Junliang Xing, Anton Milan, Xiaoqin Zhang, Wei Liu, and Tae-Kyun Kim. Multiple object tracking: A literature review. Artificial Intelligence, 293:103448, 2021.
[28] Torch Vision maintainers and contributors. VorchVision: PyTorch's Computer Vision library, November 2016.
[29] Chengcheng Ning, Huajun Zhou, Yan Song, and Jinhui Tang. Inception single shot multibox de- tector for object detection. In Proceedings of the IEEE International Conference on Multimedia Expo Workshops, pages 549-554, 2017.
[30] Rui Qian, Xin Lai, and Xirong Li. 3d object detection for autonomous driving: A survey. Puttern Recognition, 130: 130:10 2022.
[31] Joseph Redmon, Santosh Divvala, Ross Girshick, and Ali Farhadi. You only look once: Unified, real-time object detection. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pages 779-788, 2016.
[32] Joseph Redmon and Ali Farhadi. Yolo9000: Better, faster, stronger. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 7263-7271, 2017.
[33] Joseph Redmon and Ali Farhadi. Yolov3: An incremental improvement. arXiv preprint 1044v:1804.02267, 2018.
[34] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun. Faster r-cnn: Towards real-time object detection with region proposal networks. In Advances in Neural Information Processing Systems, volume 28, 2015.
[35] A. Rosenfeld and M. Thurston. Edge and curve detection for visual scene analysis. IEEE Transactions on Computers, C-20(5):562-566) 569, 1971.
[36] Dinggang Shen, Guorong Wu, and Heung-Il Il Suk. Deep learning in medical image analysis. Annual Review of Biomedical Engineering, 19:221-248, 2017.
[37] Charalampos Symeonidis, Ioannis Mademlis, Ioannis Pitas, and Nikos Nikolaidis. Efficient feature extraction for non-maximum suppression in visual person detection. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, pages 1-5, 2023.
[38] Rohun Tripathi, Vasu Singla, Mahyar Najibi, Bharat Singh, Abhishek Sharma, and Larry Davis. Asap-nms: Accelerating non-maximum suppression using spatially aware priors. arXiv preprint arXiv:2007.09785. 2020.
12

---

[39] Chien- Yao Wang, Hong- Yuan Mark Liao, Yueh-Hua Wu, Ping- Yang Chen, Jun-Wei Hsieh, and I-Hau Yeh. Cspnet: A new backbone that can enhance learning capability of enn. In Proceedings of the IEFE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 390-391, 2020.
[40] Xinlong Wang, Rufeng Zhang, Tao Kong, Lei Li, and Chunhua Shen. Solov2: fast instance segmentation. In Advances in Neural Information Processing Systems, volume 33, pages 17721-17732, 2020.
Dynamic and
[41] Yingkun Xu, Xiaolong Zhou, Shengyong Chen, and Fenfen Li. Deep learning for multiple object tracking: survey. IET Computer Vision, 13(4):355-368, 2019.
[42] Ruixin Yang and Yingyan Yu. Artificial convolutional neural network in object detection and semantic segmentation for medical imaging analysis. Frontiers in Oncology, 11:638182, 2021.
[43] Tianyi Zhang, Jie Lin, Peng Hu, Bin Zhao, and Mohamed M. Sabry Aly. Psrr-maxpoolnms: Pyramid shifted maxpoolnms with relationship recovery. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 15840-15848, 2021.
[44] Zhihao Zhang, Shengcao Cao, and Yu- Xiong Wang. Tamm: Triadapter multi-modal learning for shape understanding. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 21413-21423, 2024.
[45] Yian Zhao, Wenyu Lv, Shangliang Xu, Jinman Wei, Guanzhong Wang, Qingqing Dang, Yi Liu, and Jie Chen. Detrs beat yolos on real-time object detection. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 16965-16974, 2024.
[46] Zhaohui Zheng, Ping Wang, Dongwei Ren, Wei Liu, Rongguang Ye, Qinghua Hu, and Wang- meng Zuo. Enhancing geometric factors in model learning and inference for object detection and instance segmentation. IFFE Transactions on Cybernetics, 5288:8857-888 2021.
[47] Penghao Zhou, Chong Zhou, Pai Peng, Junlong Du, Xing Sun, Xiaowei Guo, and Feiyue Huang. Noh-nms: Improving pedestrian detection by nearby objects hallucination. In Proceedings of the 28th ACM International Conference on Multimedia, pages 1967-1975, 2020.
13

---

Appendix
Table of Contents
A Preliminaries
15
A.1 Graph Theory
15
A.2 Cartesian Tree
15
Proofs
16
B.1 Proof of Proposition
16
B.2 Proof of Theorem
16
B.3 Proof of Theorem 2
16
B.4 Proof of Theorem
16
B.5 Proof of Theorem
17
B.6 Proof of Proposition 3
19
Discussion
20
C.1 Discussion of Fast NMS and Cluster-NMS
20
C.2 Discussion of MaxpoolNMS, ASAP-NMS, and PSRR PSRR-MaxpoolIn MaxpoolNMS
21
C,3 Discussion on mAP loss of QSI-NMS
22
C,4 Further Discussion of QSI-NMS and eQSI-NMS
24
C.5 Further Discussion of BOE-NMS
24
Experimental Details
26
D.1 More Information about WMS-Bench
26
D.2
Experimental Environment and Settings
26
D.3 More Results
27
Pscudo-Codes
29
E.1 Pseudo-Code for QSI-NMS
29
E.2 Pseudo-Code for eQSI-NMS
30
E,3 Pseudo-Code for BOE-NMS
31
14

---

Notations and Terminology A directed graph g. also called a digraph, is an ordered pair (V. consisting of nonempty set of nodes, set of arcs, An arc, also called an arrow, an ordered pair (u, u) of nodes, where v. u E V. and u are the head and tail of the are (v, u), respectively, We say Iwo nodes v, are adjacent if there exists an are E & such that e = (v, u) Ve= (u, v). A direct predecessor of node v is the head of an are whose tail is and a direct successor is the tail of an are whose head is v. The in-degree d' (v) of node v E V is the number of ares with tail while the out-degree d' (e) is the number of ares with head v. A walk (Vo. .i..... 22.) in directed A Preliminaries
A.1 Graph Theory
path in a directed graph is walk in which all vertices are distinct. A cycle is path (vo, ",,...,0 v&) together with the are (uz vo). We say graph G is simple if there are no multi-edges or self-loops in 9 (V.
graph a sequence of nodes satisfying (Us, U3-1) ) E for all = 0, 1,......
contains a graph g¹ = (V. 8') if V CVE'' C &, we then say G' is a subgraph of g and denote g' C g.
We next introduce several key concepts.
Definition 3 (Directed acyclic graph). A directed acyclic graph (DAG) a directed graph without cycles.
Definition 4 (Strongly connected). A directed graph g = (V,E) is called strongly connected if it contains a path between v, and path between u, e, for every pair v, u E
Definition 5 (Weakly connected). A directed graph G = (V.E) is weakly connected if the symmetric graph G' = (V,E') with 0' E [(u, u)](v, u) E } is strongly connected.
Definition (Strongly connected component). For directed graph, an inclusion- inclusion-maximal maximal strongly connected subgraph is called strongly connected component (SCC).
Definition 7 (Weakly connected component). For directed graph, an ceatusion-maxinee weakly connected subgraph is called weakly connected component (WCC).
A.2 Cartesian Tree
Definition 8. A Cartesian tree for sequence is binary tree constructed as follows,
The root of the tree is the maximum element of the sequence.
Its left and right subtrees are formed by recursively constructing Cartesian tree for the subsequences the left and right.
The basic case is that if the sequence is empty, then the Cartesian tree is also empty.
During the construction process of Cartesian tree, the maximum value is selected from the current sequence as the root each time. Thus, the Cartesian tree obeys the max-heap property whose inorder traversal returns the original sequence. The complexity of constructing a Cartesian tree according to Definition 8 is O(n²) in the worst-case which is too slow. Fortunately, we have the following proposition:
Proposition 2. Given sequence S of length Cartesian tree for S can be constructed in O(n) time.
Here, we provide an informal proof. We can establish Proposition 2 by designing an algorithm with (n) complexity. We consider adding elements from S one by one construct the Cartesian tree. Assume that we have already constructed the Cartesian tree for S[1 k - 1]. Now, when adding S[k), we observe that Sik] will be the rightmost node of the tree. Furthermore, since Cartesian trees are max max-heaps. this implies that the parent of S[k] must be greater than equal to S(ke). Therefore, we need find the rightmost node in the Cartesian tree that is greater than or equal to S(k),, and assign its right child as the left child of S[k], updating the right child of u to be S(k].. We can implement this algorithm efficiently by maintaining stack: pop the stack until the stack top is not less than S[k], and then update the tree structure accordingly. After this, push S[k] onto the stack. When A: is iterated from to n, the construction the Cartesian tree is also completed. Since each element pushed onto and popped from the stack at most once, the overall complexity is (n))
15

---

B Proofs
B.1 Proof of Proposition
Proof. Assume that there is cycle in the directed graph 9 with length kt i.e., there exists a sequence
(vo, UI, U2, U,, Uk),
where Up = Uk and vi = 0, 1,...,,. (v;, U;+1) E & By definition, we know that if (u, u) E E, then by > by- Therefore, buo > byr > b > > bux = b
which demonstrates that
Dyo > beg This is contradictory to the fact that bno is real number.
B.2
Proof of Theorem
Proof. We first sort the scores in S in descending order into sequence S (8t Si...... St.)). To prove Theorem 1, we prove that statement 5(4,) = k; holds for all 1.2...., ., n by mathematical induction.
For t 1, k, 1, that's because box suppress b,, with the maximum score Si,, 5(61) 1 ki, since the in-degree of i is O. Therefore, the statement is true for 1.
Assume it is true for integers 1,2,....44 4- 1, 2 2, then we turn our attention to L. If Ki = 1, it implies that there does not exist a p < such that retained b; can suppress b, i.e, IOU(b, b,,)) S
Nr V k O. Therefore, if there an are from ip to it then 8(1p) kip = which indicates 5(i)) = 1. Similarly, we can prove that d(E.) 0 if k; O.
By mathematical induction, the statement above true for 1, .,2,....? n.
B.3 Proof of Theorem
Proof. We denote [B] by prove Theorem by mathematical induction.
For 1, the statement is true since there only one node in both binary trees.
Suppose that the statement holds for all sets with size 1,2,..., Consider any set with n = (t + 1) elements.
The root of QT(B) corresponds by with maximum 8, B (QT(0) = 0). And the root of the Cartesian tree corresponds the maximum element of the sequence B, which implies it's also by indexed by m. i.e., im U.
According to Definition 2, the left child of QT(B)'s root is Br's root which satisfies
cu Ze G, for all by E B,,
where each c, the centroid of the corresponding box bu. and c, the centroid of by.
Notice that B is sorted in ascending order of centroids according to the order Ze. which demonstrates that the elements in the B are the same to that in the sequence B m m- 1]. Formally, |B m and vb, Bi, there exists one and only one E 21, m 1} such that dz i.c., b. = bi_.
According the hypothesis, (T(B:) is Cartesian tree for B(1 m 1]. Similarly, we can prove QT(B,) is a Cartesian tree for B (m + 1 t ++11. 1]. Hence, the statement is true for (t + 1), which completes the proof.
L
B.4 Proof of Theorem 3
Proof. We can take b as the frame of reference. As illustrated in Figure 5, the blue box is b, and the green one is b* which is respectively positioned to the left (Figure 5(a)) right (Figure 5(b)) of the
16

---

Left
(b) Right
(c) Above
(d) Below
Figure 5: Four positions of b" relative to b.
vertical dashed line, or above (Figure 5(c)) or below (Figure 5(d)) the horizontal dashed line. The intersections filled with red north east lines. Hence, we have
IOU(b" b) IOU(b, b*)
Area(red) Union(b, (b, b*)
1/2Area(b)
Area(b)
2
B.5
Proof of Theorem 4
We prove Theorem by demonstrating the inequalities in the following two lemmas.
Lemma 1. Given positive real numbers 0 and B. for any 3i, I2, 31, 1/2 R. the following inequality holds:
0(22 x1) + B(32 y1) 2 (0 + B) (min (I2, y2 max(#1, v1 Lemma 2. Given a positive real number 7, for any 21, .22 U1 U2 R such that
( 1)22 + (1 7) ) I + 3/2
the following inequality holds:
322 + 1/2 I1
2 (2 7) [min 22 V23 - max (x1, 8/ }).
Proof of Lemma 1. Notice that min( V2} 22 and min { 82)
U2. have:
0
B
min(x2, U2) v
22 +
0+ 3 U2.
0+
For max( }. we have:
0
B
max(x1,213
x1 +
0 3+3" 91
0 3
Therefore,
RHS = (0 + (min (22, 82) max (xxx(11,111)
3
8
< (0 + 8)(
+ 22 +
+ 3
1/2
8 B
9 + 3 v1)
3
(0 + ()( 0 + (02 x1) +
112 v1)
0
=0(0 x1) + 3(12 - vn)
LHS.
17

---

Proof of Lemma 2. Similar to the approach used in the proof above, for max V1 we have
x1 + 2
max(a1, vn 2 2+7 7
2+ V1-
Notice that min (22, 82) S 22, then we have
LHS = 22 - 21 + (y1 + 82) 2y1
02 21 + (T + 1) + (1 7)) 2y1
12+,)a2 - -21 - 2y11
(2 +z)(222
7
2
y1
2+7
+ ?
2 (2 + (mmn))mmnnn))) 823 - max E1, 31
RHS.
We next use these two inequalities to prove Theorem 4.
Proof of Theorem 4. For convenience, we denote a bounding box b by a 4-tupee (ii
(0( Vie Urb (
(b) (b) where (=it , and (b) (b)) represent the left-top and right- nigttbottom corners of b, respectively. This says
Mrrb
(b)
(b) cb
Fit
Vi
S
4rb
Given bounding boxes 6* and b, their intersection can be calculated as follows:
Inter(b", b) max min (b") (b)) max
Frb max(= (b") (8)
(Tie " }}
x max(0, min Mrb
(b") (8) max (8")
(8") (b)
Mhe }}.
Here, 6" is represented by (2 I Wit Urb and b by (1 F Hit Meb Let
(b") (b") (b")
(b) (b)
1 = minf x rb x rb ] max 2 14
(b*)
(b') (b)
lt
I, = (yn (b*) (0)
Ueb max (3 Vi }.
(8"
(6)
We observe that T, S or ly S O, then Inter(b" b) = 0. resulting in IOU 0. This a trivial
case, and Theorem 4 holds. Therefore, we only need to consider the case where 7 >> 0 and l, > 0. In this case,
Inter(b", b) Laty.
Then the union can be expressed as:
Union(b", b) Area(b") + Area (b) Inter(b", b)
! I.(6") (16b) I.(b))
I
where
L (b*) (b*)
(b") Vrb
(8"
Vie
L x,h
(b)
(b).
Jit
T V.b
(b)
Vt
represent the width and height of b* and b, respectively. We then have the following inequality holds:
(b' L
(b")
L
(6)
L
(6) 1
+1.
La
N
Let 0 = =T,(6" [T(²') 0, -.
0. according to Lemma and 7, > 0. then we have
(b)) 1(4²) + L (b)
I (b)
(2)
I
18

---

Furthermore, according to the proof of Theorem 3, a(b", 1/N,, - 1) is respectively positioned to the left or right the vertical dashed line, or above or below the horizontal dashed line (see Figure 5). Without loss of generality, we can assume that a(b", l/N, 1) is to the left of vertical dashed line passing through the centroid of This means:
(b) (t + Irb
(b)
xC (b") + 12 (6*) 2
=(x/t) + 11 1/2 //2 (1/N, 1) (x/6)
(8')
(b")
I/te 2/221)/2
(1/N)) (2 1/N (6-)
(b²)
2
let y be I/N, according to Lemma and I > 0, then we have
[0' + (b)
1
2
N₂ 1)
No +1.
(3)
L2
Combining inequalities (2) and (3), inequality (1) is proven.
Finally, according to the calculation method of IOU, we have:
IOU(b*,b) = Inter(b (b" b)
Union (b* ())
(b Li (b-) + L2
Lig
(6)
Lstg
1
by
Lahy
1
N. + +1 11
N₁.
B.6 Proof of Proposition
Proof. Since a point can be considered as an interval of length O, we can construct the set M' in
(nn) time:
M' {[, m:]
m, E M).
Suppose there an algorithm A that can solve problem X. This means:
Qx A(I,[1,r))
Then, spend O(1) time to call A once, using M' and [1, its inputs. Therefore:
Qr = A(M', [4r]).
Therefore, problem can be reduced to in polynomial time, i.e., Y Sp X.
19

---

in Subsection C.3, we explain C Discussion
From a graph theory perspective, we revisited the NMS algorithm and discovered statistical properties of the weakly connected components in graph G: they are numerous overall but small in size locally, Leveraging these two characteristics, we proposed QSI-NMS and BOE-NMS. We then validated the efficiency and accuracy of QSI-NMS and BOE-NMS on NMS-Bench, showing significant improvements over the original NMS, parallelized Fast NMS, and Cluster-NMS, However, there are several areas for improvement in our work.
First, NMS algorithms can be combined with other accuracy-enhancing NMS methods, such as Soft-NMS [3], to address the negligible accuracy loss introduced by QSI-NMS and eQSI-NMS. Since our algorithms serve as general frameworks, allowing other methods to be implemented by modifying the dynamic programming equation. Second, our algorithms can be further parallelized to improve efficiency. QSI-NMS uses a divide-and-conquer recursive strategy, enabling parallel processing of different subproblems, while BOE-NMS can adopt the approach of Fast NMS, where each box computes local IOUs in parallel. Third, the distribution characteristics of bounding boxes can be further studied to obtain more detailed information about graph G. aiding in the analysis of accuracy loss in Fast NMS, QSI-NMS, and eQSI-NMS. These can be explored in future work.
In the latter part of this section, we delve deeper into our work. In Subsection C.I, we conduct a thorough graph theory analysis of Fast NMS and Cluster-NMS; in Subsection C.2, we compare our methods with MaX,oolNMS, ASAP-NMS, and PSRR-Maxpoolie and analyze the reasons behind the slight mAp drop of QSI-NMS; in Subsection C.4, we explore some implementation details of QSI-NMS; and in Subsection C.5, we discuss the advantages of the BOE-NMS implementation.
C.1 Discussion of Fast NMS and Cluster-NMS
Discussion of Fast NMS In Fast NMS [4], the computation of IOU is parallelized, and when the IOU exceeds threshold N₁, the bounding box with the higher confidence score always suppresses the one with the lower confidence score. This allows the results for all bounding boxes to be computed in parallel without depending on the results of previous boxes. Formally, in Fast NMS, the set B is first sorted into B by confidence scores in descending order, and then an n x n matrix Y is defined as follows:
(OU(b, b,)
i <;
yi.j
0
otherwise.
For bounding box bj. if there exists a bounding box b, with higher confidence (i < j) such that Vi.j > N₁, then by is not retained; otherwise, it is retained. Since N; effectively classifies all IOUs into two categories, for ease of analysis, we define a matrix X where:
Ii.s {
if < and Vis > No;
0
otherwise.
Thus, we have
V Fig
hg =
We observe that X is the adjacency matrix of G. Fast NMS can also obtain the same result using dynamic programming, but the dynamic programming equation is as follows:
8(u) - {
if (u) > 0;
otherwise.
It is evident that Fast NMS suppresses more bounding boxes compared to original NMS, which explains the loss in mAP observed with Fast NMS. Additionally, this demonstrates that Fast NMS can achieve its results without the need for topological sorting, explaining why Fast NMS is parallelizable. However, the actual implementation of Fast NMS has a time complexity ((n²), which is, in fact, greater than that of original NMS. In original NMS, suppressed boxes are not used in subsequent IOU calculations, whereas in Fast NMS, every box calculates IOUs with all preceding boxes. This highlights the heavy reliance of Fast NMS on efficient parallel computing.
20

---

Discussion of Cluster-NMS In Cluster-NMS [46], the issue of accuracy loss is addressed by iterating Fast NMS multiple times. We use a binary vector r to represent the result of applying Fast NMS to X, denoted as r F(X), where:
V Vaas ) (cj
rJ
The iterative process of Cluster-NMS is as follows:
1. ( X;
2. (()) = ()), for t 2 0;
3. ( diag(r(0) x X;
4. Iterate until (+) converges to r", at which point || - r" = 0.
In step 3, the iterative method for ((+1) involves left-multiplying X by diagonal 01 matrix, meaning rows corresponding are retained and those corresponding are discarded. Formally expressed as follows:
11+1)
Daf if 0
1
otherwise.
This shows that only boxes not suppressed in the current iteration can cause a suppression effect in the next iteration. Thus, bounding boxes incorrectly suppressed in this round will be re-evaluated with truly retained boxes in the next iteration to determine if they should indeed be suppressed.
[46] proves that its results equivalent original NMS and usually requires only a few iterations. To discuss the number of iterations, [46] defines a cluster:
Definition 9 (cluster in Cluster-NMS [46]). A subset U = {bi bia....,, 3 } of B is a cluster if and only for all b,, E U, there exists E f...J2....,. Jun( \ {ir} such that IOU(b,, by) > N₂ and for all b E B X u, IOU(bj,, b) S N₂-
[46] proves that the number of iterations does not exceed the size the largest cluster.
Analyzing Cluster-NMS from the perspective of graph 9, each iteration essentially determines whether all current nodes with an in-degree of 0 should be retained, i.e., the value of 5()); then it traverses all outgoing ares of some node u with in-degree to decide a successor node u should be suppressed, updating ō(u) as follows:
8(u) 5(u) -5(v).
Finally, all outgoing are deleted, and the next iteration begins. Hence, the essence of Cluster- NMS is parallel topological sorting within each WCC. fact, we can see that the boxes a cluster correspond to WCC in G. This explains why the number of iterations until convergence does not is
exceed the size of the largest cluster: in each iteration, at least one node with an in-degree expanded and added to the topological sort within each WCC, reducing its size by at least one per iteration. Although Cluster-NMS is correct, the matrix obtained by parallel IOU computation already encodes all the information of G, which indicates single dynamic programming can quickly produce results identical to original NMS.
C.2 Discussion of MaxpoolNMS, ASAP-NMS, and PSRR-MaxpooINMS
Discussion of MaxpoolNMS and ASAP-NMS MaxpooINMS [5] and ASAP-NMS [38] take into account the information of pre-defined "anchors" in the RPN and leverage the locality suppression characteristics of NMS achieve impressive performance improvements. However, they have the following limitations:
MaxpoolNMS and ASAP-NMS can only be used in the first stage of two-stage detectors. Our methods, however, can be used in any stage of any detector because we address the most general case (see Section 2).
21

---

The complexity of MaXpoolNMS is L 1 1 lgg where n, and n, represent the number of anchor box scales and ratios, respectively. The complexity of ASAP-NMS is (n²). Neither of these methods are more efficient than eQSI-NMS.
These methods involve many manually defined hyperparameters and are complex to imple- ment, which limits their generalization across different models and datasets. In contrast, methods require no additional parameters beyond those in original NMS and are easy to implement.
These methods are not rigorous and can lead a certain degree of mAP degradation, whereas BOE-NMS is rigorously proven to cause no mAP loss.
Discussion of PSRR-MaxpooLNMS PSRR- MARR-MMxpoolNMSS [43] introduces Relationship Recovery address the issue of regression box and score map mismatch MaxpoolNMSS, allowing it to be used at any stage of all mechor-based detectors, and claims to achieve time complexity of (n)). However, we do not believe that ISRR-MaxpooINMS outperforms our methods for the following two reasons:
First, we implement PSRR-MAR MARR-MMaSOOINMS and conduct efficiency comparisons. To better illustrate the impact of bounding box count on runtime, we perform experiments on YOLOv5-N, which has the highest number of bounding boxes, shown in Figure 6(a). Original NMS has the highest time cost due to its quadratic growth. For clearer comparison between our methods and PSRR-M Maad-MaxpoolNMMS we exclude original NMS, as shown in Figure 6(b). As the number of boxes increases, PSRR- MaxpoolNMS is faster than BOE-NMS and QSI-NMS but consistently slower than eQSI-NMS.
Second, strictly speaking, the complexity of PSRR- MSRR-MMxpooINMSS is not O(n). PSRR-MaxpooINMS requires prior knowledge of the input image size and generates confidence score maps related to the size of the image. This aspect is not considered in the complexity analysis (whereas our methods are designed and analyzed independently of the image size). During the Channel Recovery stage of PSRR-MaxpooINMS. the complexity of computing the nearest distances for channel mapping
Onn x n, X n2 where nt, and n,, represent the number of anchor box scales and ratios, respectively, These quantities vary with different datasets and detectors and increase as image size and object count increase. The remaining stages: Spatial Recovery. Pyramid MaxpoolNMS, and Shifted Max- poolNMS can all be completed in (n) time. Thus, the overall complexity of PSRR MARdRRoxx On, W1 H1 n))
3
60000
Ofiginal NMS
1400
BOEAMS MMS
00000
BOE NMS
1200
KOSI NMS
1000
soundrr bouds
PSRR-MMsppolNNW
40000
9000
33000
800
Iitency
600
2000
20000
10000
1000
# bourdinng bobres
# bounding basks
(a)
(b)
Figure 6: The line plot of the runtime of different methods as the number of bounding boxes varies in YOLOv5-N. 6(a) The histogram with bin width of 1000 representing the number of bounding boxes in each interval. The input images are divided into 10 intervals based on the number of bounding boxes: (0, 1000), (1000, 2000).... ..., (9000, 10000]. The line plot is drawn with the average number of boxes per interval as the x-coordinate and the average time cost of the NMS algorithms as the y-coordinate. 6(b) The line plot of the runtime of different methods without original NMS.
C.3 Discussion on mAP loss of QSI-NMS
In QSI-NMS, we use divide-and-come andie--and-conquer strategy, which means that bounding boxes in different subproblems do not affect each other. In some special cases, QSI-NMS may assign nodes from
22

---

the same WCC to different subproblems, potentially causing some nodes that should have been suppressed be retained.
We provide a case study with results from the YOLOv8-M model on MS COCO 2017. In Figure 7(a), the blue boxes represent the outputs of original NMS/BOE-NMS, while Figure 7(b) shows the outputs of QSI-NMS, with red boxes indicating additional boxes retained by QSI-NMS. It can be seen that QSI-NMS retains four additional boxes.
For example, consider the box/node numbered 188. The WCC containing this node is shown in Figure 8(a). All other nodes in the WCC would suppress node 188, but when we use 3M define the partitioning criterion, node 188 ends up in a different subproblem than other nodes, as shown in Figure 8(b). The figure shows partial structure of the QSI-tree: solid lines indicate parent-chill relationships, and dashed lines indicate ancestor-descendam relationships. The red nodes are nodes from the WCC, while the black node 148 is the lowest common ancestor (LCA) of nodes 188 and 201; node 156 is the LCA of nodes 194 and 193. Since each node in this WCC can only be suppressed by its red ancestor nodes, node 188 is not suppressed. However, node 194 is still suppressed because node 201 is its ancestor.
This example highlights the core of QSI-NMS design: the pivot selection and the partitioning criterion. If we choose these two appropriately, the accuracy loss of QSI-NMS can be negligible. In our algorithm design: pivot selection chooses the most representative nodes (with the highest confidence scores), so node 194 is correctly suppressed by node 201 even after being placed in a different subproblem from node 193. The partitioning criterion aims assign nodes from the same WCC to the same subproblem as much as possible, which helps reduce cases like node 188 being incorrectly retained. We also discuss other partitioning criteria in Appendix C.4.
100
100
150
150
200
250
250
300
350
350
150
102
200
300
400
500
600
100
200
300
400
500
600
(a)
(b)
Figure 7: The output bounding boxes of original NMS (7()) and QSI-NMS (7(b) in YOLOv88M on the MS COCO 2017 image "D00000057027.jpp"
148
192
193
2003
1BR
201
188
194
201
194
195
192
(a)
(b)
Figure 8: WCC in graph G contains node 188 (8(a),, along with partial structure of the QSI-tree (8(b).
23

---

C.4 Further Discussion of QSI-NMS and eQSI-NMS
Algorithm and Algorithm 2 describe QSI-NMS and eQSI-NMS respectively, which we use C++ to implement in NMS-Bench.
In the QSI-NMS and eQSI-NMS, we define the order <c. where C represents the set of centroids of the original boxes. The preorder Zc is defined on IR2. Different preorders result in slight variations in the final graph G. which in turn cause minor differences in the NMS results. Therefore, we conduct comparative experiments on different orders.
We explore three classical orders (Σz, MM, 3e), defined as follows:
(I1, v1) 3z (Ø2, 1/22 + (01
x22 V (x) =
22
A11
S 12)
(I1, 91) 3M (22, v2)
+ a
1/
22
1/2
(I1, 91) 3 (22, U2)
+
S
23 + 3z
We conduct tests on the MS COCO 2017 using different weights of YOLOv8, with the results shown in Table 4. We find orders 3M and z outperform 5..
Table 4: AP 0.5:0.95 (%) of QSI-NMS and eQSI-NMS under Different Orders on MS COCO 2017
Model
Size
Methods
16
IM
3
QSI-NMS
37.0
37.1
37.1
N
eQSI-NMS
36.8
36.9
36.9
QSI-NMS
44.5
44.6
44.6
S
eQSI-NMS
44.4
44.5
44.5
QSI-NMS
49.9
50.0
50.0
YOLOv8
M
eQSI-NMS
49.7
49.9
49.9
QSI-NMS
52.5
52.7
52.7
L
eQSI-NMS
52.3
52.5
52.5
QSI-NMS
53.6
53.8
53,8
X
&QSI-NMS
53.4
53.6
53.6
In the case where weakly connected components are independent of each other, 3M and 3e can better maintain the neighborhood consistency between the boxes. In contrast, <s. may order the boxes of different weakly connected components closer together, thereby disrupting the hierarchical nature of QSI-NMS and resulting in more accuracy loss. Therefore, when selecting the order, it is necessary to consider whether the construction of the order can retain the positional information of the original boxes much as possible.
C.5 Further Discussion of BOE-NMS
An intuitive conclusion is that two bounding boxes do not overlap at all, their IOU is necessarily 0. This is weaker conclusion than Theorems 3 and 4, but it actually more challenging implement.
Without loss of generality, we consider the one-dimensional case. Given a set n intervals [/2, r1,,
r2)rr,.... T.)). where 5 r; for i = 1,2.....
We define the following two problems:
Definition 10 (Problem X). Given I and an arbitrary interval [t, where S r, find all intervals in I that intersect with [1, rl, iee, determine the set Qx:
Definition 11 (Problem Y). Given I and an arbitrary interval [L, r] where S r. find all intervals in I whose midpoints lie within [t. r), i.e., determine the set Qy:
Qy Ssisinnsss +r; <r)
24

---

In problem X, we need to find all intervals in I that intersect with the current interval, while in problem Y, we need to find all intervals whose midpoints lie within the current interval. In Problem Y, we only need to consider the set of midpoints, which can be represented as:
4 + ri M = {m; m,
Vi = 1..........,n?
2
r.] intersects with [1, r]. then we have For problem X, if E Qx meaning that interval [4,r,]
4 rrAn22
For problem Y, if i E Qy, then we have
1 1 m 1r.
Therefore, find that problem X is more complex than problem Y because, in problem X, need to maintain the partial order of both endpoints, whereas in Problem Y, we only need to maintain the partial order the midpoints. Formally, we have the following proposition:
Proposition 3. Y Sp X.
We prove Proposition Appendix B.6. Proposition 3 indicates that problem can be reduced problem X. Therefore, X is at least hard as problem Y. Through the above analysis, can see that although this intuitive conclusion seems straightforward. it is more difficult problem than determining whether point lies within bounding box. Actually, problem X can essentially be equivalent to a 2D plane point filtering problem. Some algorithms can solve this problem by maintaining data structures with large constants, such as persistent segment trees. However, these methods are complex and offer limited optimization. For BOE-NMS, the comparison between points and segments is quite special. We can use sorting and preprocessing of the point set, and then use binary search based on monotonicity to determine the point set corresponding to the query interval. If the size of the point set corresponding the query interval is k. it requires O + log(n)) time complexity to obtain the result, avoiding redundant traversal of invalid points. In the other word, our proposed method BOE-NMS more profoundly exploits the properties of weakly connected components.
25

---

D Experimental Details
D.1 More Information about NMS-Bench
Table 5 and Table 6 respectively present the number of original bounding boxes after inferences of different models on the MS COCO 2017 and Open Images V7 datasets. A larger number of bounding boxes indicates weaker filtering capabilities of the model, leading longer post- pest-processing times required for NMS.
Table 5: Number of Bounding Boxes MS COCO 2017
Model
Size
Number of Bounding Boxes
N
4,040,118
S
3,052,794
YOLOv8
M
2.627,361
2,058,360 L
X
1,955,594
N
14,489,236
S
9,871,207
YOLOv5
M
9,051,451
L
7,986,223
X
7,227,635
Faster R-CNN R50-FPN
1,256,090
Faster R-CNN RI01-FPN
1,181,563
Faster R-CNN X101-FPN
1,068,974
Table 6: Number of Bounding Boxes on Open Images V7
Model
Size
Number of Bounding Boxes
N
50,389,365 43,062,828
YOLOv8
M
39,894,713
38, 38,126,739
X
37,113,747
D.2 Experimental Environment and Settings
Our experimental environment is shown as the Table 7.
Table 7: Experimental Environment
Component
Specification
CPU
Model
Intel Xeon Gold 6226
Total Cores
12
Total Threads
24
Max Turbo Frequency
3.70 GHz
GPU
Model
NVIDIA RTX 4090 x1
VRAM
24 GB GDDR6X
For the hyperparameter settings, set the NMS threshold N, to 0.7 in our experiments.
26

---

D.3 More Results
Experiments in Torchvision Library To compare with the CUDA NMS from torchvision [28]. we implement our methods as C++ operators under the torchvision library. We then fairly replace the different NMS operator modules for testing. We test on the MS COCO 2017 using different weights of YOLOv8. The experimental setup is the same as previously described, and we set bench size as 20. The experimental results are shown the Table This demonstrates that our methods provide performance improvements even when compared to highly optimized parallel implementations.
Table 8: NMS Methods Performance under Torchvision Implementation
Model
Size
Target
CUDA NMS
BOE-NMS
QSI-NMS
eQSI-NMS
Average Latency (ps)
343.4
204.2
185.2
136.3
N
AP 0.5:0.95 (%)
37.4
37.4
37.3
37.1
Average Latency (ps)
302.1
158.3
160.1
109.4
S
AP 0.5:0.95 (%)
45.0
45.0
44.8
44.7
Average Latency (ns)
301.0
136.7
141.4
101.3
YOLOv8
M
AP 0.5:0.95 (%)
50.3
50.3
50.2
50.1
Average Latency ((S)
284.4
109.1
111.7
85.2
L
AP 0.5:0.95 (%)
53.0
53.0
52.8
52.7
Average Latency (ws)
284.1
109,9
106.5
83.5
X
AP 0.5:0.95 (%)
54.0
54.0
53.9
53.8
Statisties IOU Calculations During the NMS algorithm process, the computational cost of numerous IOU calculations is performance bottleneck. We compare the number of IOU calculations between our methods and the original NMS. Figure 9 shows the relationship between the number of boxes and the number of IOU calculations for different methods. It can be observed that our methods significantly reduce the number of IOU calculations compared original NMS, demonstrating the superiority.
x10
x10
BQSI
DSI-NMS DriginalNMS
QSI-NMS OrigiwiNNM
Number of YOU Calculations
Number of YOU Calculations
0.8
0.4
5.00
1000
1500
2000
2500
0.0
200
400
600
800
|
(a)
(b)
Figure 9: Stackplots of IOU calculations for different methods. 9()) shows the results of YOLOv8-N on MS COCO 2017, while 9(b) shows the results of Faster R-CNN X101-FPN on MS COCO 2017.
27

---

Results of Instance Segmentation Tasks We also evaluate our methods on instance segmentation tasks using Mask R-CNN [15] and YOLOv8, where they demonstrate significant superiority over other methods. Please refer to Table 9 for details.
Table 9: NMS Methods on Instance Segmentation Tasks
Model
Size
Target
original NMS
Fast NMS
Choster-NMS
BOE-NMS
QSI-NMBS
eQSI-NMS
Latency (J8)
222.8
30.3
21.6
Mask R-CNN R50-FEN
Aplis 0.5:0.95 (%)
41.0
40.4
40.9
41.0
40.3
Ap 0.5.095 (5)
37.2
36,9
37.1
57.2
36.9
36.7
Average Latency (ja)
205.0
Mask R-CNN RI0J-FPN
Aplli 0.5:0.95 (%)
42.9
42.2
42,9
42.9
42.7
42.3
Apaaak 0.5:0.95 (%)
38.6
38.4
38.6
38.5
38.4
38.2
Average Latency (ja)
Mask R-CNN XIOI-IPN
Apli 0.5 (9)
44.3
43.6
44,2
44.5
44.1
43.7
Apa 0.5:0.95 (8)
39.5
39.3
39,5
39.5
39.3
39.1
Average Latency (ja)
N-SEG
Apli 0.5:0.95 (%)
36.7
36.5
36.7
36.7
36.6
36.4
YOLOv8
Ap 9.5:0.95
30.4
30.4
30.3
30.2
Average Latency (1a)
740.0
269.2
736.2
158.6
115.8
8-88
Aplii 0.5:0.95 (%)
44.7
44.5
44.7
44.7
44.6
44.4
Ap (8)
28

---

E
Pseudo-Codes
E.1 Pseudo-Code for QSI-NMS
Algorithm 1: QSI-NMS
Input :B = bi.... bn, C CI,... Cny S S1, 8n, No.
B is the list of initial detection boxes, C contains the centroids of the boxes in B, S contains corresponding detection scores, N₂ is the NMS threshold. Output: DD boxes to be retained.
Function Partition() (1,
Procedure QSI-NMS (1, r)
S' + Strri
if 2 r then return
m - arg max S"; swap(bm: b,); swaplsm. s,); swap(Cm; C:);
end
p 1-6 l;
p Partition (l,r); ((b,)) then
for i [rr 1] do
if Ie G then swap(b,. b));
for i E [1 r {p} do
if IO bi) > N₂ then
swap(sp, 8:);
5(bp) False;
swap(c,, G))
end
p + 1;
end D DUbpp end
end end
swap(bp. pp b,); swap(sp sr); swap(ep, Cr); return p
QSI-NMS (1, p- - 1,8); QSI-NMS (p 1,r,0);
begin
D < 0]:5 + (True)":
(1,-NMS(1,11) m, 5);
return
end
29

---

E.2 Pseudo-Code for eQSI-NMS
Algorithm 2: eQSI-NMS
Input :B = b1. ... Dn = C1, Cn. S = $1,". 8n bny N₂
is the list of initial detection boxes, C contains the centroids of the boxes B, contains corresponding detection scores, Ne is the NMS threshold.
Output: boxes to retained.
Procedure Solve (I)
Stack - +- [ L + D3
for m 1, n
b* bim:
while L is not empty A L is not empty do TOP(L)) < 8m then
IOU T))( > Nr then S(TOP(C") t- False; end
POP(C))POP(43):
end
else
Break: end
end
PUSH(C b"); PUSH(L*, sm);
end
begin
D 0 < {True)";
C + the sorted C in ascending order according to ic;
T (i,, ,2, in)
where C (Ci,: Cigs... ,., C..)
Colve());
reverse(T);
Solve (I);
b do
if ((b) then - DUb;
end
end
return D
end
30

---

E.3 Pseudo-Code for BOE-NMS
Algorithm 3: BOE-NMS
Input :B bi: ... bus . my,... .m, 81," ... Sn; I = . Li,
3 is the list of initial detection boxes, M contains the x-coordinates of the centroids of
the boxes B, S contains corresponding detection scores, I contains the ranks of all boxes in B which is sorted by x-coordinate of the centroids of the boxes in ascending order, N₂ is the NMS threshold.
Output:D. boxes to be retained.
begin
(): while # do
D
arg max S:
< bmi
D D B S + 8mi
f left x-coordinate(bb)] + right x-coordinate (6*);
[ lowerbound (I, z));
Find the rank of the first item in s.t.m, 27
r + upperbound (Z, xy);
Find the rank of the first item in I, s.t.m, > Iy
I' I1
for i E I' do
if IOU b,) N; then
B B b;; S t S -
end
end
end
return
end
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Please refer to Section 1, Paragraph 3, 4, and 5.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Please refer to Appendix C, Paragraph 2.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
32

---

Justification:
Please refer to Appendix A and B.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: For algorithm implementation details, please refer to Section and Appendix And for experimental details, please refer to Section 5 and Appendix D.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
33

---

Answer: [Yes]
Justification: We have included the code, related documentation, and licenses in the supple- mentary material. We will open-source code and data after acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
public/guides/Ce http://oooSSuuuiiionoooeeee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https: CCodeSubmis /nipp..ccocc wttpccccpppccg.....ec.ce.. / ssion ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Please refer Section and Appendix D. More details can be found in our source code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Please refer Table 1, Table 2, Table 8, and Figure
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
34

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please refer to Table 7 for the CPU/GPU details.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https /tt:://nnuuuppe hwtpppbbicccccccccccuieeeeeeeeee
Answer: [Yes]
Justification: Ethics.
The research conducted in this article fully complies with the NeurIPS Code
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification; Our research on NMS is foundational work in the field of object detection, and does not have any societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
35

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: This paper does not present any such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cite the relevant models and datasets. Additionally, we provide the corresponding copyrights and licenses in the supplementary material.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
36

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide the corresponding instructional documentation and the license in the supplementary material.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
37


Reviews:
[{"review_id": "ufUB24c840", "reviewer": "Reviewer_pEVt", "summary": "This work focuses on improving the latency of Non-Maximum Suppression (NMS), a crucial step for nearly all object detectors.  The work analyzes NMS, as a directed acyclic graph (DAG) treating bounding boxes as nodes, and suppression relationships as arcs allowing NMS solutions based on dynamic programming. Based on this graph interpreation, the work proposes two new approximate versions of NMS, named QSI-NMS, and BOE-NMS with different precision v/s latency tradeoffs. Finally, the proposed NMS approaches are evaluated on a new benchmark NMS-bench, showing improved latency with little to no mAP loss.", "questions": "1.  The worst case complexity of the proposed approaches is still O(n log n), while other approaches, stated above claim O(n) complexity. Does this imply the other approaches scale better?", "limitations": "The work does an adequate job of discussing the limitations of the proposed work.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper is written adequately, and offers a new graph theory perspective for non-maximum suppression, further exploring avenues for new research in the area.\n2. The proposed approaches show improved latency compared to other NMS approaches including original (greedy NMS), Fast NMS and Cluster NMS, while maintaining mAP. This is achieved without fine-tuning the underlying model.", "weaknesses": "1. The paper does not compare against (or even cite) other approximations to NMS proposed in the literature such as MaxPoolNMS[1],  PSRR-MaxpoolNMS [2] or ASAP-NMS [3]. It's unclear how the contribution, and performance of proposed approximations differs from the literature. For example, the idea behind BOE-NMS, using locality b/w suppression relationships is already explored in the above works.\n2. Can this approach be utilized for two-stage object detectors as well for both stages of NMS? The proposed benchmark only applies the methods this for single-stage object detectors, it's unclear how the method performs on single stage detectors. \n\n[1] Cai, Lile, et al. \"Maxpoolnms: getting rid of nms bottlenecks in two-stage object detectors.\" _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 2019.\n[2] Zhang, Tianyi, et al. \"Psrr-maxpoolnms: Pyramid shifted maxpoolnms with relationship recovery.\" _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 2021.\n[3] Tripathi, Rohun, et al. \"Asap-nms: Accelerating non-maximum suppression using spatially aware priors.\" _arXiv preprint arXiv:2007.09785_ (2020).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback and for recognizing the value of our new graph theory perspective on non-maximum suppression. We will address your concerns in the following responses.\n\n---\n> **Q1**: The worst case complexity of the proposed approaches is still $\\mathcal{O}(n \\log n)$, while other approaches, stated above claim $\\mathcal{O}(n)$ complexity. Does this imply the other approaches scale better?\n\n**A1**: Among the papers you mentioned, only PSRR-MaxpoolNMS claims to achieve $\\mathcal{O}(n)$ complexity. However, we do not believe that PSRR-MaxpoolNMS has better scalability compared to our methods for two reasons:\n\nFirst, we implemented PSRR-MaxpoolNMS and conducted efficiency comparisons. To better illustrate the impact of bounding box count on runtime, we performed experiments on YOLOv5-N, which has the highest number of bounding boxes, as shown in Figure 3 (a) of the global rebuttal PDF. Original NMS has the highest time cost due to its quadratic growth. For a clearer comparison between our methods and PSRR-MaxpoolNMS, we excluded Original NMS, as shown in Figure 3 (b). As the number of boxes increases, PSRR-MaxpoolNMS is faster than BOE-NMS and QSI-NMS but consistently slower than eQSI-NMS.\n\nSecond, strictly speaking, the complexity of PSRR-MaxpoolNMS is not $\\mathcal{O}(n)$. PSRR-MaxpoolNMS requires prior knowledge of the input image size and generates confidence score maps related to the size of the image. This aspect is not considered in the complexity analysis (whereas our methods are designed and analyzed independently of the image size). During the Channel Recovery stage of PSRR-MaxpoolNMS, the complexity of computing the nearest distances for channel mapping is $\\mathcal{O}(n_sn_rn)$, where $n_s$ and $n_r$ represent the number of anchor box scales and ratios, respectively. These quantities vary with different datasets and detectors and increase as image size and object count increase. The remaining stages: Spatial Recovery, Pyramid MaxpoolNMS, and Shifted MaxpoolNMS can all be completed in $\\mathcal{O}(n)$ time. Thus, the overall complexity of PSRR-MaxpoolNMS is $\\mathcal{O}(n_s n_r\\lfloor \\frac{W}{\\beta} \\rceil \\lfloor \\frac{H}{\\beta} \\rceil + n_s n_r n)$.\n\n---\n> **Q2**: The paper does not compare against (or even cite) other approximations to NMS proposed in the literature such as MaxPoolNMS, PSRR-MaxpoolNMS or ASAP-NMS. It's unclear how the contribution, and performance of proposed approximations differs from the literature.\n\n**A2**: Our research focuses on NMS methods applicable to general cases, so we inadvertently missed these important papers. Thank you very much for pointing this out. We will cite these papers in our revised version. Next, we will illustrate how our contributions differ from these papers through the following comparisons:\n\nMaxpool NMS and ASAP-NMS can only be used in the first stage of two-stage detectors, while PSRR-MaxpoolNMS, although applicable to various stages, is limited to anchor-based models. Our methods, however, can be used in any stage of any detector because we address general cases (see Section 2).\n\nThe complexity of Maxpool NMS is $\\mathcal{O}(n_sn_r\\lfloor\\frac{W}{\\beta}\\rceil\\lfloor\\frac{H}{\\beta}\\rceil+n\\log n)$, ASAP-NMS is $\\mathcal{O}(n^2)$, and the complexity of PSRR-MaxpoolNMS has been analyzed in **A1**. None of these methods are more efficient than eQSI-NMS.\n\nThese methods involve many manually defined hyperparameters and are complex to implement, which limits their generalization across different models and datasets. In contrast, our methods require no additional parameters beyond those in Original NMS and are easy to implement.\n\n---\n> **Q3**: The idea behind BOE-NMS, using locality suppression relationships is already explored in the above works. What is the difference between BOE-NMS and these methods?\n\n**A3**: Although these methods also consider locality, BOE-NMS employs a fundamentally different approach and analysis. Not suppressing non-overlapping boxes is a very intuitive idea, but the key is how to locate these boxes. We discuss this issue in Appendix C.3 and prove that directly determining non-overlapping boxes is a more difficult problem than checking whether the centroid of one box falls within another box (the basic idea of BOE-NMS), as shown in Appendix B.6. Therefore, BOE-NMS can be efficiently implemented. In contrast, methods in the literature use complex techniques to find approximate solutions to this problem. Additionally, BOE-NMS is rigorously proven not to cause any loss of accuracy (Theorem 4), whereas the methods in the literature are not as rigorous and exhibit some degree of accuracy degradation.\n\n---\n> **Q4**: Can this approach be utilized for two-stage object detectors as well for both stages of NMS? The proposed benchmark only applies the methods this for single-stage object detectors, it's unclear how the method performs on two-stage detectors.\n\n**A4**: Yes, our methods are applicable to various stages of various detectors. We tested not only one-stage detectors but also two-stage detectors (Faster R-CNN). Please refer to Table 1 in Section 5.2. We have also added experiments for the first stage in Faster R-CNN. The results demonstrate that our methods still exhibit strong performance advantages, with QSI-NMS and eQSI-NMS even surpassing Original NMS in terms of accuracy. Please see the tables below.\n\nTable 1:R50-FPN\n||Original NMS|Fast NMS|Cluster-NMS|BOE-NMS|QSI-NMS|eQSI-NMS|\n|---|---|---|---|---|---|---|\n|mAP(%)|40.2|39.6|40.2|40.2|40.3|40.3|\n|latency($\\mu s$)|14768|2469|4501|2341|950|457|\n\nTable 2:R101-FPN\n||Original NMS|Fast NMS|Cluster-NMS|BOE-NMS|QSI-NMS|eQSI-NMS|\n|---|---|---|---|---|---|---|\n|mAP(%)|42.0|41.3|42.0|42.0|42.1|42.0|\n|latency($\\mu s$)|13089|2411|4477|2325|995|464|\n\nTable 3:X101-FPN\n||Original NMS|Fast NMS|Cluster-NMS|BOE-NMS|QSI-NMS|eQSI-NMS|\n|---|---|---|---|---|---|---|\n|mAP(%)|43.0|42.4|42.9|43.0|43.1|43.1|\n|latency($\\mu s$)|12583|2383|4463|2265|984|457|\n\n---", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rVbuH8FULu", "reviewer": "Reviewer_snSe", "summary": "This paper presents a method from a new perspective to enhance the efficiency of the Non-Maximum Suppression (NMS) algorithm with affordable accuracy decrease. \n\nThe authors introduce a novel perspective by analyzing NMS through the lens of graph theory, revealing its intrinsic structure as a directed acyclic graph. \n\nThis insight leads to the development of two NMS optimization methods: QSI-NMS and BOE-NMS. \n\nFurthermore, the authors also introduce NMS-Bench, an end-to-end benchmark that facilitates rapid and comprehensive validation of various NMS algorithms.", "questions": "(1) How was the average latency calculated, more information if preferred. Please report the time of graph construction and the time of NMS, respectively.\n(2) How is the performance of the proposed algorithm on the Yolo V10 and mask RCNN.", "limitations": "The effectiveness of the proposed should be evaluated on more real world cases.\n\nMore detailed analysis of which kinds of samples are miss detected by the algorithm is missing.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1)The paper innovatively applies graph theory to NMS, offering a detailed theoretical basis for the proposed QSI-NMS and BOE-NMS algorithms, which excel in enhancing speed while preserving accuracy.\n(2)The experimental results does support the effectiveness of the efficiency of the proposed algorithm.\n(3)The construction of the benchmark is a solid contribution to the community.\n(4)The paper offers a new perspective and tool for understanding and optimizing the NMS step in object detection.", "weaknesses": "(1)A case study that illustrate the overly suppressed samples is welcomed.\n(2) How was the average latency calculated, more information if preferred. This is not clear.\n(3) How is the performance of the proposed algorithm on the Yolo V10 and mask RCNN.\n(4) Although the proposed method is tested on the proposed NMS-Bench, experimental results in detection bench-mark algorithms are still prefered.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback and for acknowledging the value of our work. We will address your questions and concerns in the following responses.\n\n---\n> **Q1**: A case study that illustrates the overly suppressed samples is welcomed.\n\n**A1**: This question is fundamental and others are also interested in this issue. The proof of Theorem 4 demonstrates that BOE-NMS does not overly suppress boxes compared to Original NMS, leading to the same results. In QSI-NMS, however, in some special cases, nodes within the same WCC might be incorrectly assigned to different subproblems, resulting in retaining some boxes that should have been suppressed. To provide a comprehensive and clear explanation, we have included our response in the global rebuttal. We kindly ask you to review our response in **A1** of the global rebuttal.\n\n---\n> **Q2**: How was the average latency calculated, more information if preferred. This is not clear. Please report the time of graph construction and the time of NMS, respectively.\n\n**A2**: The latency calculation begins from the input of bounding boxes and ends when the retained bounding boxes are output. For a dataset containing $N$ images, latency is measured by using the bounding boxes generated per image as input, and the total latency for the $N$ images is averaged. To mitigate random errors, this measurement is repeated 5 times, and the average of these measurements is used as the final average latency. Thus, the average latency is the average time taken to execute NMS.\n\nWe do not need any additional time to construct the graph. Constructing the graph and topological sorting incurs an additional $\\mathcal{O}(\\vert \\mathcal{V}\\vert + \\vert \\mathcal{E}\\vert)$ computational overhead. Although this does not affect the complexity of our methods, it can slow down their practical performance. To address this issue, we design our algorithm such that the order of the nodes we iterate over follows a valid topological sort. Therefore, dynamic programming can be completed without explicitly constructing the graph. As a result, our algorithm does not incur the extra overhead of graph construction. \n\nFor QSI-NMS, lines 174-177 explain why explicit graph construction is unnecessary. The same applies to BOE-NMS, where sorting the boxes by confidence scores from high to low already provides a valid topological sort. We can also quickly locate the mutually suppressing boxes without sorting, thereby obtaining $\\mathcal{G}$, and performing dynamic programming yields the same results.\n\nHowever, In BOE-NMS, not sorting in advance would introduce additional computational overhead of constructing the graph and topological sorting. Please check the table below:\n\n| method                            | average latency ($\\mu s$) | AP 0.5:0.95 (%) |\n| --------------------------------- | ------------------------- | --------------- |\n| Original NMS | 936.9 | 37.2            |\n| BOE-NMS  | 201.8 | 37.2            |\n| BOE-NMS (with graph construction) | 558.0  | 37.2            |\n\n---\n> **Q3**: How is the performance of the proposed algorithm on the Yolo V10 and mask RCNN. \n\n**A3**: At the time of conducting this research, YOLOv10 had not yet been open-sourced, and we currently do not have sufficient time to include experiments with it. However, we tested our methods on the Instance segmentation task using Mask R-CNN and YOLOv8, where our methods also demonstrated significant superiority over others. Please refer to the tables below.\n\nTable 1: Latency ($\\mu s$) of various methods\n\n|| Original NMS | Fast NMS | Cluster-NMS | BOE-NMS | QSI-NMS | eQSI-NMS |\n| -------------------- | ------------ | -------- | ----------- | ------- | ------- | -------- |\n| Mask R-CNN(R50-FPN)  | 48.8         | 105.7    | 222.8       | 31.9    | 30.3    | **21.6** |\n| Mask R-CNN(R101-FPN) | 45.3         | 113.1    | 205.0       | 32.3    | 29.8    | **21.5** |\n| Mask R-CNN(X101-FPN) | 40.3         | 105.6    | 189.2       | 26.7    | 26.6    | **19.3** |\n| YOLOv8n-seg          | 1265.3       | 366.4    | 859.4       | 219.5   | 153.4   | **85.4** |\n| YOLOv8s-seg          | 740.0        | 269.2    | 736.2       | 158.6   | 115.8   | **61.9** |\n\nTable 2: Box mAP(%) of various methods\n\n|                      | Original NMS | Fast NMS | Cluster-NMS | BOE-NMS | QSI-NMS | eQSI-NMS |\n| -------------------- | ------------ | -------- | ----------- | ------- | ------- | -------- |\n| Mask R-CNN(R50-FPN)  | 41.0         | 40.4     | 40.9        | 41.0    | 40.8    | 40.4     |\n| Mask R-CNN(R101-FPN) | 42.9         | 42.2     | 42.9        | 42.9    | 42.7    | 42.3     |\n| Mask R-CNN(X101-FPN) | 44.3         | 43.6     | 44.2        | 44.3    | 44.1    | 43.7     |\n| YOLOv8n-seg          | 36.7         | 36.5     | 36.7        | 36.7    | 36.6    | 36.4     |\n| YOLOv8s-seg          | 44.7         | 44.5     | 44.7        | 44.7    | 44.6    | 44.4     |\n\nTable 3: Mask mAP(%) of various methods\n\n| | Original NMS | Fast NMS | Cluster-NMS | BOE-NMS | QSI-NMS | eQSI-NMS |\n| -------------------- | ------------ | -------- | ----------- | ------- | ------- | -------- |\n| Mask R-CNN(R50-FPN)  | 37.2| 36.9     | 37.1        | 37.2    | 36.9    | 36.7|\n| Mask R-CNN(R101-FPN) | 38.6| 38.4     | 38.6        | 38.6    | 38.4    | 38.2|\n| Mask R-CNN(X101-FPN) | 39.5 | 39.3| 39.5| 39.5| 39.3| 39.1|\n| YOLOv8n-seg| 30.4| 30.4| 30.4| 30.4| 30.3| 30.2|\n| YOLOv8s-seg| 36.7 | 36.6| 36.7| 36.7| 36.5| 36.5 |\n\n---\n> **Q4**: Although the proposed method is tested on the proposed NMS-Bench, experimental results in detection bench-mark algorithms are still preferred.\n\n**A4**: To demonstrate the practical value of our methods, we not only tested them on NMS-Bench but also implemented them in torchvision. The results show that our methods are more efficient than the highly parallel CUDA NMS, which is the currently used program for NMS. For detailed information and experimental results, please refer to Appendix D.3.\n\n---", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ShdCAdBoKA", "reviewer": "Reviewer_kDQX", "summary": "The paper, \"Accelerating Non-Maximum Suppression: A Graph Theory Perspective,\" presents a novel approach to enhancing the efficiency of the Non-Maximum Suppression (NMS) algorithm used in object detection. By analyzing NMS through graph theory, it introduces two new optimization methods: Quicksort Induced NMS (QSI-NMS) and Boxes Outside Excluded NMS (BOE-NMS). These methods leverage the structure of weakly connected components in a graph to reduce computational complexity and speed up the process, with minimal impact on the mean Average Precision (mAP). The paper also introduces NMS-Bench, a benchmarking framework to evaluate NMS methods rapidly.", "questions": "1. Details on Graph Construction (Line 99-104): The paper mentions the construction of graph G using bounding boxes and suppression relationships. Could you elaborate on the computational overhead of this graph construction process and its impact on the overall efficiency of NMS?\n\n2. Experimental Setup (Line 260-265): The results presented are impressive; however, could more information be provided on how the different configurations of bounding boxes were handled during the experiments, especially concerning their distribution and density?\n\n3. Proof of Theorem 1 (Line 510-520): Could you clarify how the dynamic programming approach adapts to variations in graph structure, particularly for non-standard configurations of bounding boxes?", "limitations": "Complexity for Non-Specialists: The application of graph theory to optimize the Non-Maximum Suppression (NMS) process introduces complex mathematical concepts and proofs that might not be easily accessible or understandable for practitioners or researchers without a background in graph theory. This complexity could limit the broader application and adaptation of the proposed methods in the field.\n\nDependence on Data Characteristics: The effectiveness of the proposed QSI-NMS and BOE-NMS methods is highly dependent on the specific characteristics of the data, such as the distribution and density of bounding boxes. This dependency might restrict the generalizability of the methods across different object detection tasks and datasets where these characteristics vary significantly.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Innovative Approach: The paper applies graph theory to optimize NMS, a critical post-processing step in object detection, demonstrating significant improvements in computational efficiency.\n\n2. Comprehensive Evaluation: It includes a robust evaluation using the newly developed NMS-Bench, providing detailed comparisons of performance improvements over traditional methods.\n\n3. Practical Impact: The proposed methods, particularly eQSI-NMS, offer substantial speed increases with minimal loss in accuracy, which is highly beneficial for real-time object detection applications.", "weaknesses": "1. Complexity of Graph-Theoretical Analysis: The paper's reliance on graph theory might limit its accessibility to those without a background in this area. The proofs and theoretical explanations are dense and could be challenging to follow for non-specialists.\n\n2. Limited Discussion on Scalability: While the paper shows efficiency improvements, it does not extensively discuss the scalability of the proposed methods across different hardware or larger datasets beyond those tested.\n\n3. Dependency on Specific Conditions: The effectiveness of the proposed methods may depend heavily on the characteristics of the data and the specific architectures of the detection systems used, which may not generalize well to all types of object detection tasks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and valuable feedback. We appreciate your recognition of our innovative approach, comprehensive evaluation, and practical impact. Below, we will address each of your concerns one by one.\n\n---\n> **Q1**: Details on Graph Construction (Line 99-104): The paper mentions the construction of graph G using bounding boxes and suppression relationships. Could you elaborate on the computational overhead of this graph construction process and its impact on the overall efficiency of NMS?\n\n**A1**: The computational overhead of constructing the graph in our algorithms is zero. Constructing the graph and topological sorting incurs an additional $\\mathcal{O}(\\vert \\mathcal{V}\\vert + \\vert \\mathcal{E}\\vert)$ computational overhead. Although this does not affect the complexity of our methods, it can slow down their practical performance. To address this issue, we design our algorithm such that the order of the nodes we iterate over follows a valid topological sort. Therefore, dynamic programming can be completed without explicitly constructing the graph. As a result, our algorithm does not incur the extra overhead of graph construction. \n\nFor QSI-NMS, lines174-177 explain why explicit graph construction is unnecessary. The same applies to BOE-NMS, where sorting the boxes by confidence scores from high to low already provides a valid topological sort. We can also quickly locate the mutually suppressing boxes withoud sorting, thereby obtaining $\\mathcal{G}$, and performing dynamic programming yields the same results.\n\nHowever, In BOE-NMS, not sorting in advance would introduce additional computational overhead of constructing the graph and topological sorting. We conducted an experiment to support our analysis. We did not sort by confidence but performed dynamic programming at the end while keeping everything else unchanged. The results on YOLOv8-N are shown in the table below:\n\n| method                            | average latency ($\\mu s$) | AP 0.5:0.95 (%) |\n| --------------------------------- | ------------------------- | --------------- |\n| Original NMS                      | 936.9                     | 37.2            |\n| BOE-NMS                           | 201.8                     | 37.2            |\n| BOE-NMS (with graph construction) | 558.0                     | 37.2            |\n\n---\n> **Q2**: Experimental Setup (Line 260-265): The results presented are impressive; however, could more information be provided on how the different configurations of bounding boxes were handled during the experiments, especially concerning their distribution and density?\n\n**A2**: Our experimental data is derived from the actual outputs of commonly used models on public datasets, as described in Section 5.1. Each bounding box is represented by $x, y, w, h$ to denote its position and size, along with a confidence score $score$, as defined in Section 2. For detailed statistics related to the bounding boxes, please refer to Appendix D.\n\n---\n> **Q3**: Proof of Theorem 1 (Line 510-520): Could you clarify how the dynamic programming approach adapts to variations in graph structure, particularly for non-standard configurations of bounding boxes?\n\n**A3**: As proven in Theorem 1, variations in the graph structure do not affect the correctness of the results obtained through dynamic programming. However, the structure of the graph can influence the efficiency of dynamic programming since its complexity is $\\mathcal{O}(\\vert\\mathcal{V}\\vert +\\vert\\mathcal{E}\\vert)$. By pre-sorting, the complexity can be reduced to $\\mathcal{O}(\\vert\\mathcal{V}\\vert\\log\\vert\\mathcal{V}\\vert+\\vert\\mathcal{V}\\vert)$. Therefore, when the graph has many nodes or edges, the efficiency of dynamic programming decreases, especially in cases where all bounding boxes are very dense (which are rare in real-world data).\n\n---\n\n> **Q4**: Complexity of Graph-Theoretical Analysis: The paper's reliance on graph theory might limit its accessibility to those without a background in this area. The proofs and theoretical explanations are dense and could be challenging to follow for non-specialists.\n\n**A4**: We understand that the graph-theoretical aspects may be complex. To address this, we've included detailed explanations and supplementary materials to clarify the key points(see Appendix A). Additionally, we emphasize the practical applications to highlight the relevance of our work.\n\n---\n\n> **Q5**: Limited Discussion on Scalability: While the paper shows efficiency improvements, it does not extensively discuss the scalability of the proposed methods across different hardware or larger datasets beyond those tested.\n\n**A5**: We did not have enough time to test on different hardware environments, but our methods indeed reduce computational overhead (see Appendix D.3, Figure 6). Moreover, we implemented our methods in the torchvision library, and their performance surpasses that of highly parallel CUDA NMS (see Appendix D.3), demonstrating that the efficiency of our methods does not rely on specific hardware and can be applied to low-power edge devices.\n\nAdditionally, we tested on a larger and more robust dataset, Open Images V7. Please refer to Section 5.2, Table 2 for details.\n\n---\n\n> **Q6**: Dependency on Specific Conditions: The effectiveness of the proposed methods may depend heavily on the characteristics of the data and the specific architectures of the detection systems used, which may not generalize well to all types of object detection tasks.\n\n**A6**: We believe that our analysis of the characteristics of $\\mathcal{G}$ is widely applicable (Lines 126-135).\n\n---", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lai7zoQt7i", "reviewer": "Reviewer_HR1f", "summary": "The article \"Accelerating Non-Maximum Suppression: A Graph Theory Perspective\" explores a novel way to optimize Non-Maximum Suppression (NMS) in object detection using graph theory. The authors present two new methods, QSI-NMS and BOE-NMS, which greatly enhance the efficiency of NMS while maintaining mean Average Precision (mAP). They also introduce NMS-Bench, a benchmarking framework designed to evaluate different NMS methods effectively.", "questions": "see weakness part for details", "limitations": "delineate the constraints of their proposed method in the paper.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- This article brings an interesting and fresh perspective to NMS by applying graph theory.\n- The proposed QSI-NMS and BOE-NMS algorithms show impressive improvements in computational efficiency, with QSI-NMS achieving up to 10.7× speedup and BOE-NMS achieving 5.1× speedup, all without sacrificing mean Average Precision (mAP).\n- One of the standout contributions is NMS-Bench, a benchmarking framework that standardizes the evaluation of NMS algorithms, potentially driving further advancements in the field.\n- Additionally, the paper provides a detailed analysis of the intrinsic structure of NMS through the lens of graph theory, offering valuable insights into its computational bottlenecks and optimization strategies.", "weaknesses": "1. In section 5.2 Results, we can find QSI-NMS operates with some performance decrease, and the paper doesn't thoroughly discuss what aspects of the algorithm might be causing this decline (maybe missing some data but exactly what is missed).\n2. The connection between the proposed methods and graph theory appears weak. QSI-NMS is essentially a quicksort-based algorithm, and the size of the weakly connected components (WCC) or their independence doesn't seem to significantly impact its performance. BOE-NMS, on the other hand, introduces a heuristic for the search space, which doesn't strongly tie into graph theory principles either.\n3. Regarding eQSI-NMS, there are questions about the clarity and effectiveness of the methods. The pseudo-code in Appendix E.2 is difficult to understand, and there might be an issue with the line \"for s ∈ S do s ← −s;\" in eQSI-NMS. It’s unclear how this part of the code functions and whether it introduces any problems.\n4. The evaluation is primarily limited to the YOLOv8-N model on the MS COCO 2017 dataset. To gain a more comprehensive understanding of the algorithms' generalizability, broader evaluations across various models and datasets would be beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate Reviewer HR1f's thoughtful review of our work and the insightful questions you have raised. Your feedback is invaluable in helping us improve and refine our research. We will address each of your concerns in detail. \n\n---\n> **Q1**: The connection between the proposed methods and graph theory appears weak. \n\n**A1**: In fact, our methods are closely linked to graph theory for the following two reasons:\n\nThe first reason is that the goal of the algorithms is to construct the graph $\\mathcal{G}$ or its approximate graph $\\tilde{\\mathcal{G}}$ more quickly and efficiently (see Section 4). However, due to the highly skillful design of our algorithm, there is no need to explicitly construct the graph in implementation. \n\nWe explained in Section 4.1 (Lines 174-177) that QSI-NMS does not require explicit construction of the graph $\\tilde{\\mathcal{G}}$. If we use different pivot selection methods or partitioning criteria, graph construction becomes unavoidable. The situation is similar in BOE-NMS. If we do not sort by confidence scores, we can still obtain $\\mathcal{G}$, and the result after dynamic programming will be the same. However, this approach would incur additional space and time overhead. We conducted an experiment to support our analysis, where we did not sort by confidence but performed dynamic programming at the end, keeping everything else unchanged. The results tested on YOLOv8-N are as follows:\n\n| method                            | latency ($\\mu s$) | AP 0. 5:0. 95 (%) |\n| --------------------------------- | ------------------------- | --------------- |\n| Original NMS                      | 936. 9                    | 37. 2           |\n| BOE-NMS                           | 201. 8                    | 37. 2           |\n| BOE-NMS (with graph construction) | 558. 0                    | 37. 2           |\n\nThe second reason is that the algorithms' design is based on the analysis of WCCs in the graph $\\mathcal{G}$, ensuring the algorithm's effectiveness. In the analysis in Section 3(Lines126-135 and Figure 2), we identified two crucial characteristics of $\\mathcal{G}$: the number of WCCs is large, and their sizes are generally small. The first characteristic inspired the design of QSI-NMS, and the second characteristic inspired BOE-NMS(Lines 131-135). \n\nSpecifically, QSI-NMS is based on the divide-and-conquer strategy, where subproblems do not interfere with each other. If there are few WCCs, the divide-and-conquer process will repeatedly split the same WCC, leading to accuracy issues. BOE-NMS must traverse each WCC, and the smaller the WCCs, the faster BOE-NMS will be. Assuming there are $w$ WCCs and the size of the $i$-th WCC is $n_i$, we can perform a formal analysis using the following inequality:\n$$\n\\frac{\\left(\\sum_{i=1}^{w}n_i\\right)^2}{w}\\leq \\sum_{i=1}^{w}n_i^2\\leq \\left(\\sum_{i=1}^{w}n_i\\right)^2\n$$\nThe right half of the inequality shows that BOE-NMS is always better than Original NMS, while the left half shows the lower bound of BOE-NMS optimization. Therefore, the more WCCs there are, the greater the optimization space for BOE-NMS, and when each $n_i$ is as small as possible, it will be closer to this lower bound. \n\nIn summary, both the number and size of WCCs affect our two methods. The main reason is that the more WCCs there are, the better the accuracy performance of QSI-NMS; the smaller the WCCs, the higher the efficiency of BOE-NMS. \n\n---\n\n> **Q2**: In section 5. 2 Results, we can find QSI-NMS operates with some performance decrease, and the paper doesn't thoroughly discuss what aspects of the algorithm might be causing this decline (maybe missing some data but exactly what is missed). \n\n**A2**: Your question is very insightful, and other reviewers are also interested in this issue. Therefore, we have included the response to this question in the global rebuttal. Please refer to **Q1** of the global rebuttal for the details.\n\n---\n> **Q3**: Regarding eQSI-NMS, there are questions about the clarity and effectiveness of the methods. The pseudo-code in Appendix E. 2 is difficult to understand, and there might be an issue with the line \"for $s\\in\\mathcal{S}$ do $s\\leftarrow -s$;\" in eQSI-NMS. It’s unclear how this part of the code functions and whether it introduces any problems. \n\n**A3**: There was indeed a mistake here, and we appreciate your feedback. What we intended to express is \"for $c \\in \\mathcal{C}$ do $c \\leftarrow -c$\" This is because we should first sort $\\mathcal{C}$ in ascending order. Next, by maintaining a stack, we can find the position of the last element greater than the current confidence score before it in $\\mathcal{O}(n)$ time; let’s call this algorithm $A$. Additionally, we need to find the first element greater than the current confidence score after it, which can be done by sorting $-\\mathcal{C}$ in ascending order and then performing algorithm $A$. This explanation is indeed prone to misunderstanding, and we will rewrite this part of the pseudo-code in our revised version. We will first sort $\\mathcal{C}$ in ascending order, then process it from front to back and back to front once each. However, our implementation is correct, and we suggest you refer to eQSINMS.hpp in the supplementary material. Our code is easy to understand. \n\n---\n> **Q4**: The evaluation is primarily limited to the YOLOv8-N model on the MS COCO 2017 dataset. To gain a more comprehensive understanding of the algorithms' generalizability, broader evaluations across various models and datasets would be beneficial. \n\n**A4**: We evaluated our methods on various datasets and models. On COCO 2017, we tested YOLOv8 models (one-stage, anchor-free model), YOLOv5 models (one-stage, anchor-based model), and Faster R-CNN models (two-stage, anchor-based model), as detailed in Table 1 of Section 5.2. We also tested the YOLOv8 models on the more mature and robust Open Images V7 dataset, as shown in Table 2.\n\n---", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We appreciate the reviewers' thoughtful feedback on our work. We are grateful for the reviewers' recognition of the following strengths:

1. **Innovative Application of Graph Theory**:
   - Reviewer pEVt highlighted that our paper introduces a new graph theory perspective for non-maximum suppression (NMS), which explores new research avenues in this area.
   - Reviewer snSe praised our innovative application of graph theory in the QSI-NMS and BOE-NMS algorithms, noting that it provides a detailed theoretical basis and offers a new perspective for understanding and optimizing NMS.

2. **Significant Performance Improvements**:
   - Reviewer HR1f noted the impressive speedups achieved by our algorithms, with QSI-NMS providing up to a $10.7\times $ speedup and BOE-NMS achieving $5.1\times$, all while maintaining mean Average Precision (mAP).
   - Reviewer kDQX recognized the substantial speed increases of eQSI-NMS with minimal loss in accuracy, which is highly beneficial for real-time object detection applications.
   - Reviewer pEVt also acknowledged the improved latency of our proposed approaches compared to traditional NMS methods, including greedy NMS, Fast NMS, and Cluster NMS, without the need for fine-tuning the underlying model.

3. **Comprehensive and Robust Evaluation**:
   - Reviewer kDQX appreciated our comprehensive evaluation using the newly developed NMS-Bench, which offers detailed comparisons of performance improvements over traditional methods and enhances the robustness of our results.
   - Reviewer snSe commended the construction of the benchmark, highlighting its solid contribution to the community by standardizing the evaluation of NMS algorithms and supporting further research.

4. **Valuable Theoretical Insights and Practical Contributions**:
   - Reviewer HR1f emphasized the detailed analysis of the intrinsic structure of NMS through graph theory, which offers valuable insights into its computational bottlenecks and optimization strategies.
   - Reviewer snSe acknowledged that our work provides a new perspective and tool for understanding and optimizing the NMS step in object detection, which contributes both theoretically and practically to the field.
   - Reviewer kDQX highlighted the practical impact of our proposed methods, particularly eQSI-NMS, in offering substantial speed increases with minimal loss in accuracy, which is crucial for real-time applications.

We would also like to express our gratitude to the reviewers for their thoughtful questions and valuable suggestions. These have been instrumental in guiding the refinement of our work. We will address the reviewers' concerns by clarifying concepts, providing additional experiments, and offering further explanations within the scope of the feedback provided.

---

Both Reviewer snSe and Reviewer HR1f have expressed concerns about the slight decrease in accuracy with QSI-NMS, so we address this common concern here.

> **Q1**: Why does QSI-NMS have a negligible mAP loss? What conditions can lead to accuracy loss?

**A1**: In QSI-NMS, we use a divide-and-conquer strategy, which means that bounding boxes in different subproblems do not affect each other. In some special cases, QSI-NMS may assign nodes from the same Weakly Connected Component (WCC) to different subproblems, potentially causing some nodes that should have been suppressed to be retained.

We provide a case study in the PDF with results from the YOLOv8-M model on the COCO dataset. In Figure 1 (a), the blue boxes represent the outputs of Original NMS/BOE-NMS, while Figure 1 (b) shows the outputs of QSI-NMS, with red boxes indicating additional boxes retained by QSI-NMS. It can be seen that QSI-NMS retains four additional boxes.

For example, consider the box/node numbered 188. The WCC containing this node is shown in Figure 2 (a). All other nodes in the WCC would suppress node 188, but when we use $\preceq_{M}$ to define the partitioning criterion, node 188 ends up in a different subproblem than other nodes, as shown in Figure 2 (b). The figure shows a partial structure of the QSI-tree: solid lines indicate parent-child relationships, and dashed lines indicate ancestor-descendant relationships. The red nodes are nodes from the WCC, while the black node 148 is the Lowest Common Ancestor (LCA) of nodes 188 and 201; node 156 is the LCA of nodes 194 and 193. Since each node in this WCC can only be suppressed by its red ancestor nodes (Lines 201-208), node 188 is not suppressed. However, node 194 is still suppressed because node 201 is its ancestor.

This example highlights the core of QSI-NMS design: the pivot selection and the partitioning criterion. If we choose these two appropriately, the accuracy loss of QSI-NMS can be negligible. In our algorithm design: pivot selection chooses the most representative nodes (with the highest confidence scores), so node 194 is correctly suppressed by node 201 even after being placed in a different subproblem from node 193. The partitioning criterion aims to assign nodes from the same WCC to the same subproblem as much as possible, which helps reduce cases like node 188 being incorrectly retained. We also discuss other partitioning criteria in Appendix C.2.

---

Meta-review: The reviewers unanimously recommend acceptance of the paper with varying degrees of strength. I agree with their assessment and am happy to accept this paper for publication at the NeurIPS conference. 

The reviews and the rebuttal have given rise to several interesting points and results that I encourage the authors to include in the camera-ready version. In particular, the complexity and computation time in practice of your methods and their baselines were much discussed and should be clarified in the paper.
Decision: Accept (poster)