#  NTN-based 6G Localization:
Vision, Role of LEOs, and Open Problems

Harish K. Dureppagari, Chiranjib Saha, Harpreet S. Dhillon, R. Michael Buehrer
H. K. Dureppagari, H. S. Dhillon, and R. M. Buehrer are with Wireless@VT,
Department of ECE, Virginia Tech, Blacksburg, VA. Email: {harishkumard,
hdhillon<EMAIL_ADDRESS>C. Saha is with the Qualcomm Standards and
Industry Organization, Qualcomm Technologies Inc., San Diego, CA 92121 USA.
Email<EMAIL_ADDRESS>The support of the US NSF (Grants 1923807 and
CNS-2107276) is gratefully acknowledged.

###### Abstract

Since the introduction of 5G Release 18, non-terrestrial networks (NTNs) based
positioning has garnered significant interest due to its numerous
applications, including emergency services, lawful intercept, and charging and
tariff services. This release considers single low-earth-orbit (LEO)
positioning explicitly for location verification purposes, which requires a
fairly coarse location estimate. To understand the future trajectory of NTN-
based localization in 6G, we first provide a comprehensive overview of the
evolution of 3rd Generation Partnership Project (3GPP) localization
techniques, with specific emphasis on the current activities in 5G related to
NTN location verification. In order to provide support for more accurate
positioning in 6G using LEOs, we identify two NTN positioning systems that are
likely study items for 6G: (i) multi-LEO positioning, and (ii) augmenting
single-LEO based location verification setup with Global Navigation Satellite
System (GNSS), especially when an insufficient number of GNSS satellites (such
as 2) are visible. We evaluate the accuracy of both systems through a 3GPP-
compliant simulation study using a Cramér-Rao lower bound (CRLB) analysis. Our
findings suggest that NTN technology has significant potential to provide
accurate positioning of UEs in scenarios where GNSS signals may be weak or
unavailable, but there are technical challenges in accommodating these
solutions in 3GPP. We conclude with a discussion on the research landscape and
key open problems related to NTN-based positioning.

###### Index Terms:

NTN-based localization, location verification, 6G positioning, LEO-based
localization.

##  I Introduction

Satellite communication networks have been largely inaccessible for mass-
market usage because of limited scale, cost, proprietary technology, and
specialized equipment. However, the emergence of the 5G ecosystem has
attracted the attention of the satellite community, leading to investigations
in the 3rd Generation Partnership Project (3GPP) related to the use of
satellites in public safety applications, fixed wireless access, and narrow-
band internet-of-things (NB-IoT) connections. Despite this progress,
significant challenges remain in order to utilize satellite communications as
a core feature in 5G. 5G satellite communications, also termed non-terrestrial
networks (NTNs) in 3GPP, have the potential of enabling truly global coverage,
extending from emergency texting capabilities to delivering true mobile
broadband. Positioning in 5G is crucial in many industries such as emergency
services, logistics, and autonomous driving [1]. While cellular positioning
has evolved significantly, NTN-based positioning in Release 18 is still in the
early stages and is limited to user equipment (UE) location verification [2].
We believe that future releases of 5G and 6G will consider NTN positioning
with low-earth-orbit (LEO), medium-earth-orbit (MEO), and geostationary-earth-
orbit (GEO) satellites. This paper provides a vision of the extension of
cellular positioning procedures, currently designed for terrestrial networks
(TNs), to NTN, which could be considered in future releases of 5G and 6G. Note
that the terms LEO and LEO satellites are interchangeably used in the paper.

Not surprisingly, there have been some recent efforts in exploring the use of
NTNs for positioning. In [3], the authors propose a method using a point-
solution approach for LEO-based positioning that was originally developed for
the Doppler-shift-based Global Navigation Satellite System (GNSS). However,
this technique requires at least eight LEOs to be visible in order to perform
a 3D location estimation. In [4], the authors propose a method for estimating
the position and speed of a target using distributed Doppler information from
the Iridium LEO constellation, employing nonlinear least squares and filtering
algorithms for search and rescue services. In [5], the authors proposed using
UAVs as a means of realizing NTN-based accurate localization of emergency
response personnel. In [6], the authors presented experimental results and
receiver designs for navigation using multi-constellation LEO signals of
opportunity. While these works provide several useful insights, they are
largely disconnected from the standardization activities. We fill this gap by
discussing current 3GPP efforts related to NTN positioning and sharing our
vision on the evolution of this area as we prepare to enter the beyond 5G and
6G era.

Figure 1: The evolution of positioning support pre and post-formation of the
3GPP standardization body.

In order to provide a comprehensive understanding of the current and future
landscape of positioning systems in cellular networks, we begin by providing a
detailed overview of the evolution of positioning systems across different
cellular standards, with specific emphasis on the current 5G activities on
NTN-based location verification that requires a coarse location estimate. To
extend NTN support for accurate positioning, we identify and investigate two
prospective positioning frameworks that are likely study items for 6G: Multi-
LEO positioning and augmenting single LEO positioning with GNSS. To evaluate
the performance of these systems in comparison to 5G location verification, we
conduct an extensive simulation study using a Cramér-Rao lower bound (CRLB)
analysis. Additionally, we discuss some of the challenges specific to 3GPP
standards that need to be addressed in order to enable these technologies in
6G. Finally, we highlight open problems that arise when LEOs are utilized for
positioning, as they were originally deployed for communication purposes.

##  II Positioning in Cellular Networks

To put the contribution of this article into perspective, it will be useful to
discuss the evolution of positioning methods from 1G to 5G, incorporating
various advancements in technology and positioning methods as shown in Fig. 1.
For a detailed survey, please refer to [7]. In 1G, positioning was used
primarily for intelligent vehicle highway systems and emergency services,
relying on proprietary solutions using joint time-difference-of-arrival (TDOA)
and angle-of-arrival (AOA), and uplink TDOA (UTDOA).

The initial 2G networks lacked support for positioning services. However,
positioning became increasingly important for emergency services with the
Federal Communications Commission (FCC) of the United States approving
location requirements on 911 emergency calls. As a result, terminal-based
positioning techniques such as Global Positioning System (GPS) were supported
in handsets. Additionally, SnapTrack introduced assisted GPS (A-GPS), which
leverages the cellular network to aid GPS with navigation messages and
differential corrections. In 1999, the European Telecommunications Standards
Institute (ETSI) and T1P1, the American standardization group, collaborated to
develop a functional description of location services (LCS) for 2G and 3G
networks. To implement LCS, positioning schemes such as cell-ID (CID), timing
advance (TA), uplink time-of-arrival (UL TOA), and enhanced observed time
difference (E-OTD) were specified. In 2000, 3GPP emerged as a global
standardization body to unify standards for 3G networks worldwide. 3GPP
consolidated the positioning standards that had evolved separately in
different regional specifications. Later in 3G, UTDOA was added to the
supported methods in Release 7, while RF pattern matching (RFPM) was included
in Release 10 to improve the CID positioning performance.

Although 5G cellular positioning methods retain some fundamental elements from
the past generations, from the architecture and protocol standpoint, the
evolution really started from 4G. In particular, 4G started the development of
standalone RAT-dependent positioning as an alternative to assisted GNSS
(A-GNSS). This led to the design of a dedicated positioning reference signals
(PRS) with serving cell muting, and different positioning methods like
enhanced CID (E-CID), observed TDOA (OTDOA), and LTE positioning protocol
(LPP) [8]. In later releases, UTDOA support was added, which is realized using
UL reference signals such as sounding reference signals (SRS). In 4G, the
location services (LCS) signaling in the core network (CN) was also
standardized. A dedicated location management function (LMF) was introduced to
interact with external clients (i.e. application, UE, or other CN nodes) with
location request/response, and exchange related to positioning assistance
information and measurements with eNBs and UE.

The LCS signaling and LMF continue to be the central theme of the 5G
positioning architecture, which added further enhancements (see Fig 2). An LCS
session may be initiated upon a location request from a UE or external client
via the gateway mobile location center (GMLC), or CN node e.g. access and
mobility management function (AMF) [9]. The LMF interacts with the UE using
the LTE Positioning Protocol (LPP), and gNBs using New Radio Positioning
Protocol Annex (NRPPa). The UE receives the required radio configuration from
the next-generation radio access network (NG-RAN) over radio resource control
(RRC) via the NR-Uu interface. Leveraging the centralized unit (CU) and
distributed unit (DU) split introduced in 5G NR, both LPP and NRPPa protocols
are transported over the control plane of the NG interface (NG-C) via AMF. The
gNB CU is connected to a gNB DU over the F1 interface. The transmission
receive point (TRP) in 5G-RAN, a central part of a gNB DU, is an abstract node
that can transmit PRS in downlink (DL) and perform SRS measurements in UL.
Using the DL and UL measurements from the UE and TRPs, the LMF may compute the
UE location using RAT-dependent positioning methods like TDOA, multi-RTT, DL
AOA, UL AOA, and E-CID.

In Release 18, 3GPP continues NR positioning evolution studying solutions for
side-link positioning, extending positioning support for reduced capability
UEs, and investigating solutions to improve further accuracy. While the
positioning evolution is still focused on TNs, positioning using satellites
operating in LEO, MEO, and GEO is still not within the direct scope of 5G. In
the next section, we will discuss in detail how NTN-based positioning will
likely become an essential component of satellite access.

Figure 2: (a) 5G positioning architecture with our envisioned future
extensions to NTN. (b) A location verification solution discussed in 3GPP
system architecture (SA) working group (WG) using the 5G positioning
architecture.

##  III From 5G to 6G NTN:
New Frontiers for Positioning

###  III-A NTN Framework in 5G

NTN is becoming an integral part of the 5G ecosystem due to its potential of
extending the reach of 5G TNs, thereby improving the reliability and
resiliency of the network. NTN refers to a range of satellite and airborne
vehicle networks, including LEOs, MEOs, GEOs, High Altitude Platform Systems,
and air-to-ground networks. LEOs are particularly attractive due to their
reduced latency and the possibility of deploying mega-constellations with
reusable technologies. Starting from 3GPP Release 15, the integration of
satellite networks into the 5G ecosystem was initiated through the engagement
of the satellite industry in the 3GPP standardization process. Key uses for
NTN in 5G include: 1) ubiquitous 5G services by extending the reach of 5G TNs
to under-served areas, 2) improved reliability and resiliency of NTN compared
to TNs to physical attacks and natural disasters, 3) 5G services to users
onboard airborne vehicles such as flight passengers and drones, other moving
platforms like ships, and trains, 4) enabling wide-area IoT services, and 5)
relaying emergency and public safety messages.

NTN access typically features an NTN terminal (either 3GPP UE or terminal
specific to the satellite system), one or several sat-gateways that connect
NTN to a public data network, and a service or radio link between the UE and
the satellite. A satellite may implement either a bent pipe payload (having
radio frequency filtering, frequency conversion, and amplification on board
the satellite) or a regenerative payload (having all or part of gNB functions
on board the satellite such as demodulation/decoding, switch and routing, and
coding/modulation, as well as bent pipe payload capabilities). In releases 15
and 16, the RAN identified several technical challenges related to the
deployment of NTN, such as propagation delays in NTN being longer compared to
TNs. This led to new designs maintaining large timing advances (TAs),
enhancing random access (RA) procedures, and hybrid automatic repeat request
(HARQ) processes. See [10] for more details on the radio aspects of satellite
access.

An important aspect of NTN design is reliance on the GNSS capabilities in a
UE. To close a radio link with a satellite, a UE must calculate the relative
speed and RTT of the service link, for timing and Doppler resolution. This can
be done by acquiring the satellite ephemeris at the gNB and broadcasting it as
system information, and the estimate of UE location. It is evident from this
discussion, unlike TN, UE location resolution is a central component of NTN
access. Hence, GNSS capability is mandatory for NTN access, and UEs without
GNSS are out of the scope of 5G NTN. As we will discuss in the sequel, this
sets the stage for a new set of design problems where UEs without GNSS can be
localized using standalone RAT-dependent methods and hence can connect to NTN.

###  III-B NTN-Based Location Verification

Although NTN positioning is not in the direct scope of 5G, the requirement for
designing RAT-dependent positioning solutions for NTN is motivated by the
requirement of UE location verification. Location verification is a key step
performed in cellular networks for various reasons, such as public land mobile
network (PLMN) selection, emergency calls, subscription and billing, and
lawful intercepts. For most such purposes, it is enough to use CID-based
positioning since a cellular cell may cover only a few kilometers (e.g. 2km)
and this accuracy may be enough for these purposes. For NTNs, however, each
cell may cover hundreds of kilometers, rendering this approach inappropriate.
We illustrate some example scenarios as follows.

CN Selection. After a UE connects with the RAN (i.e. moves to the
RRC_Connected state), the network selects the appropriate CN for the UE,
taking into account various factors including the selected PLMN ID and
location information such as the serving cell of the UE [11]. For NTN, the
cells can be moving and significantly larger than those of TNs, spanning vast
areas that may even cover multiple countries with different CNs connected to
the same NTN RAN. This can make it challenging to determine the appropriate CN
for a connected UE, particularly when the UE is located close to a country
border and the serving cell does not provide sufficient granularity.
Additionally, malicious UEs may attempt to fake their selected PLMN and GNSS
measurements to connect to a different CN. Hence, it is crucial for TNs to
have the necessary infrastructure to verify UE location without relying solely
on UE-reported information. The same motivation drove 3GPP to introduce NTN-
based location verification in 5G.

Regulatory Aspects. 5G systems with satellite access must be able to determine
the location of a UE in order to provide services that comply with the
governing national or regional regulatory requirements applicable to the UE,
such as routing traffic or supporting emergency calls. Therefore, even when
providing services across all continents using NTN, there is no globally
harmonized set of requirements that overrules local regulations, and the same
required granularity for UE location information estimated via GNSS should be
considered as for TNs. Furthermore, network operators must reliably know the
location information of a UE for services like public warning systems,
charging and billing, emergency calls, lawful intercept, and data retention
policy in cross-border scenarios and international regions.

As UE-reported location can be easily tampered with, 3GPP is working on
designing a RAT-dependent network-based UE location verification system that
provides a horizontal accuracy of 10 km [2]. The network verification
procedure is illustrated in Fig. 2(b). The AMF, based on the assistance
information provided by the satellite (NG-RAN) decides whether to trigger a
location verification process (step 4). The AMF might take different actions
based on the status of UE location verification, for instance, rejected CN
access or denied service request for call or data (step 5). Once the LMF
triggers a network-induced location request (NI-LR), the UE positioning is
initiated by the LMF (step 6). During this step, the LMF does not rely on the
location information provided by the UE. Based on the outcome of step 6, the
AMF may decide to deregister the UE from CN (step 7). In step 6, the network
may leverage any RAT-dependent positioning method. Since the RAT has moving
TRPs (i.e. satellites) in this case, the positioning methods could be
significantly different from the usual ones used for TN cellular positioning.
In the next section, we will discuss further details.

###  III-C Perspective of Positioning Methods in NTN

In this section, we discuss how positioning methods in TN may differ in the
case of NTN in the context of cellular networks. Although satellite-based
positioning has been studied extensively in the past, it is to be noted that
fitting these solutions in the 5G NTN framework which is primarily designed
for communication is not straightforward. For the rest of this paper, we will
primarily focus on LEOs in the context of NTN (given their practical
relevance). In the literature, various positioning methods based on delay and
Doppler measurements, e.g. TOA, TDOA, RTT or two-way TOA, and frequency-
difference-of-arrival (FDOA) have been discussed. The choice of positioning
method depends on the specific requirements of the system and the available
resources. For instance, delay-based methods, such as TOA and RTT, require
high bandwidth to achieve high resolution. Furthermore, RTT requires two-way
signaling while TDOA requires DL signaling, but has a worse dilution of
precision (DOP). On the other hand, Doppler-based methods, such as FDOA, are
preferred when the signal bandwidth is narrow. It is important to note that
for Doppler-based methods to provide the necessary accuracy, the receiver and
transmitter are required to maintain phase synchronization during the time of
measurement. Note that 5G positioning has the capability and signaling support
to accommodate most of the delay-based positioning methods, but not for any
Doppler-based positioning methods such as FDOA.

When it comes to using NTN for positioning, there are several factors to
consider. For instance, in TDOA, the geometric DOP (GDOP) plays a critical
role in minimizing position errors. However, given that early NTN deployments
are primarily coverage-centric, only single LEO-based positioning techniques
are prioritized in 5G Release 18 [12]. Multi-satellite techniques require
denser constellations and satellites with overlapping coverage, which will be
in the second phase of NTN to enhance capacity. Therefore, to perform TDOA
with a single LEO, the LEO must move significantly in its trajectory between
TDOA measurements, which requires high measurement time. During this time, it
can be challenging to maintain a stable clock (i.e. a clock with constant
offset) at the UE. Although FDOA has been considered for LEO-based
positioning, e.g., see [3], there are several challenges associated with its
implementation. First, it requires at least 8 visible LEOs to perform accurate
3D estimation which is not always guaranteed. Second, the need for a
significant redesign of the existing PRS to provide sufficient Doppler
resolution for accurate FDOA measurements. To address these concerns, RTT-
based positioning for NTN is being discussed in the 3GPP RAN WGs [2]. This
method involves DL TOA measurements using PRS transmitted from LEO and UL TOA
measurements using SRS transmitted from the UE. By taking several two-way TOA
measurements as the LEO moves in its orbit, the position of the UE can be
calculated.

Figure 3: System model figures illustrating potential NTN enhancements from 5G
to 6G: a) Single LEO Positioning: Positioning with a single LEO satellite with
an earth-fixed beam. The coverage area corresponds to the 3dB beam-width of
the satellite antenna pattern. As LEO moves in its orbit, 10 virtual anchors
are specified where independent RTT measurements are collected. b) Multi-LEO
Positioning: Positioning with LEOs. Seven LEOs form a hexagonal grid. UEs in
the central beam of LEO 2 are considered for evaluation. The link budget of
neighboring LEOs is considered to be 6 dB worse than the serving LEO. c) GNSS
+ Single LEO Positioning: Positioning with 2 GNSS + single LEO. Two GNSS
satellites provide one TDOA measurement while a single LEO provides RTT
measurements over the measurement time. The coverage area under consideration
corresponds to the 3dB beam-width of the LEO satellite.

Although RTT-based positioning serves as a baseline for single LEO-based
positioning in 5G, when it comes to multi-RTT for more than one LEO there are
certain drawbacks that need to be considered. In order to use two-way TOA, we
need to calculate the propagation delay for multiple LEOs and compensate for
these delays using TA. However, due to the significant propagation delay
differences among multiple LEOs, we cannot guarantee that these differences
will be within the maximum tolerable delay spread in 5G systems. Therefore,
simply compensating for propagation delay for only the serving satellite, as
done in TNs, is not sufficient to obtain TOA measurements from multiple LEOs.
Furthermore, GNSS is also necessary to enable both single LEO-based
positioning and multi-RTT for multiple LEOs to compute RTT between LEOs and
UE. While it may be questioned whether LEO-based positioning is necessary when
UE is already equipped with GNSS support, it is important to note that the
LEO-based positioning framework in 5G is primarily intended for positioning
verification purposes, rather than for explicit positioning. Besides, as we
will discuss in Section V, it is natural to wonder whether a standalone
cellular positioning solution using LEOs can serve as an alternative to GNSS
or enhancement of GNSS, especially indoors.

##  IV NTN-based Positioning Case Studies for 6G

In this section, we evaluate the NTN positioning performance achieved by LEOs.
In addition to the NTN-based location verification use case currently being
studied in 3GPP RAN WG, we study two important use cases that have been
identified in this article as two likely work items beyond 5G and 6G, namely,
multi-LEO positioning, and augmenting single-LEO setup with GNSS, which is
especially relevant when a sufficient number of GNSS satellites are not
visible to provide an unambiguous position fix. From the system design
perspective, our simulation results pave the way for a full-blown NTN-based
positioning system to be built into cellular systems. For the evaluation of
positioning performance, we use CRLB which provides a position error bound
(PEB) that can be obtained using these methods. For positioning methods, we
consider both TDOA and RTT-based under realistic propagation assumptions. The
large-scale parameters of the radio channel between UE and LEO were derived
from the agreed channel model for 3GPP evaluations [13], and LEO link budget
numbers and multi-LEO constellation were derived from [14].

###  IV-A Single LEO Positioning

Fig. 3(a) presents the system model for single LEO-based positioning, where a
LEO is positioned at a 600 km orbit. The UEs are distributed within the 3dB
beam-width of the LEO antenna pattern which is referred to as the coverage
area. For simulation, we only consider the center beam of the satellite, i.e.,
when the beam center is at (or near) the nadir of the satellite. The line-of-
sight (LOS) probability, shadowing, and path loss for each link are determined
by link distance and LEO elevation angle. A UE located at the center of the
coverage area corresponds to an elevation angle of $90^{\circ}$ and a bore-
sight angle of the beam pattern which is $0^{\circ}$. We define measurement
time as the length of the time window to collect RTT measurements for a single
UE at different LEO positions which serve as virtual anchors. The mean PEB is
obtained by averaging PEB across all the UEs dropped inside the satellite
coverage. For simulation, we considered the orbital velocity of $\sim 7.6$km/s
and the S-band (2GHz carrier frequency) with 10MHz DL and UL bandwidth.

Fig. 4 presents the box plot of the PEB or position error values, obtained
using single LEO RTT measurements for various measurement times. The trend in
PEB suggests that longer measurement times result in more accurate position
estimates because of more LEO position diversity. This result illustrates that
a single satellite RTT is enough to satisfy the requirement of 10 km
positioning accuracy for network location verification. It is important to
note that there is a significant difference between the mean and median PEB
values. This indicates that for certain users, the positioning accuracy is far
worse than the central tendency. These users are located near the satellite
orbit and observe worse GDOP. Although it is not clear how to handle such
users if single LEO positioning is used in step 6 (Fig. 2(b)), this makes a
strong case for multi-LEO positioning, which we discuss next.

Figure 4: Box plot presents the PEB values obtained using single LEO (altitude
of 600km) RTT measurements for various measurement times. The measurement
times, in seconds, are [2 3 4 5 6 7 8 9 10], and the corresponding mean PEB
values in meters are [2220.19, 1692.03, 1440.50, 1300.16, 1214.39, 1158.84,
1121.87, 1096.73, 1078.49].

###  IV-B Multi-LEO Positioning

Fig. 3(b) depicts a system model setup consisting of multiple LEOs. For the
simplicity of simulation, all LEO satellites are positioned at the same
altitude ($780$ km, similar to Iridium). The coverage area corresponds to the
3dB beam-width of the center satellite. We assumed a longitude gap of
$13^{\circ}$ and a latitude gap of $6.9^{\circ}$ between any two satellites
which results in the inter-satellite distance of $\sim$1633.4km. The number of
active satellites is 3 or 4. The satellite selection was performed to maximize
GDOP. The center satellite is assumed to be the reference or serving
satellite, while others are neighboring satellites. Moreover, it is assumed
that the beam patterns of the neighboring satellites are off by 6dB compared
to the center satellite.

Figure 5: Box plot presents PEB values for 4 different scenarios with multiple
LEOs (altitude of 780km): 3 LEOs with 2 TDOA measurements, 3 LEOs with 2 TDOA
measurements + RTT measurements from the reference LEO, 4 LEOs with 3 TDOA
measurements, 4 LEOs with 3 TDOA measurements + RTT measurements from the
reference LEO. The corresponding mean PEB in meters for these scenarios are
[187.68 96.25 53.75 33.64].

Figure 6: Box plot presents PEB performance comparing two GNSS (altitude of
20200km) satellites and a single LEO (altitude of 600km) satellite with three
GNSS satellites. Two GNSS satellites provide one TDOA measurement and RTT
measurements are collected from the single LEO over measurement time while
three GNSS satellites provide two TDOA measurements. Considered measurement
times [2 5 7 10] seconds and the corresponding mean PEB in meters for these
scenarios are [184.04 118.37 88.85 60.88] while three GNSS satellites provide
an accuracy of 11.93m.

The presented box plot in Fig. 5 showcases the PEB for four distinct
scenarios: 1) three LEOs with two TDOA measurements, 2) three LEOs with two
TDOA measurements and RTT measurements from the reference LEO, 3) four LEOs
with three TDOA measurements, and 4) four LEOs with three TDOA measurements
and RTT measurements from the reference LEO. It can be observed that multiple
LEO positioning is instantaneous whereas we need to consider measurement time
to collect RTT measurements for a single LEO. Looking at the mean PEB, we can
conclude that utilizing multiple LEOs can significantly improve the position
estimation accuracy over a single LEO. Specifically, we observe that with the
fourth scenario, we are able to achieve a mean PEB as low as 33.64 meters.
This value is one order of magnitude lower than the PEB with a single LEO,
even with a measurement time of 10 seconds. Moreover, the number of outliers
is significantly reduced compared to the single LEO. Our simulation clearly
indicates that multiple LEOs can not only resolve the location verification
problem currently discussed in 3GPP, but can also be a reasonable baseline for
standalone NTN positioning.

###  IV-C GNSS + Single LEO Positioning

In this section, we study localization using both GNSS and LEOs which is
relevant when only a few GNSS satellites (such as two) are visible as shown in
Fig.3(c). Specifically, GNSS satellites provide one TDOA measurement and a
single LEO provides RTT measurements over a certain measurement time. For the
LEO, the simulation assumptions are the same as those given in Section IV-A.
For GNSS, we considered an altitude of 20200 km, an operating frequency of
1575.42MHz, a bandwidth of 15.345MHz, and link budget numbers as given in
[15]. Fig. 6 shows the box plot of PEB values obtained using two GNSS
satellites and a single LEO satellite for different measurement times. Adding
RTT measurements from a single LEO for a few seconds to GNSS measurements can
improve positioning accuracy to below 100 m. Positioning accuracy can be
further improved by adding RTT/TDOA measurements from multiple LEOs. Note that
three GNSS satellites provide better accuracy than two GNSS satellites and a
single LEO because LEOs (with narrow beams) are primarily designed for
communication which is not ideal for positioning. This is further discussed in
Section V.

##  V Research Landscape and Open Problems

Many of the open research problems stem from the fundamental fact that, unlike
GNSS networks, the emerging mega-constellation LEO networks such as Starlink,
Kuiper, and OneWeb, are designed for communications and not geolocation. To
this end, the satellites have multiple beams, and the adjacent beams are
typically assigned different frequencies to reduce inter-beam (or inter-cell)
interference. To maximize area spectral efficiency, the antenna beam-widths
are kept relatively small. This design principle is contradictory to an NTN
deployment for primarily positioning purposes, where it is beneficial to keep
wide beam coverage and overlap beam coverages of multiple satellites. That
being said, there are certain aspects that need to be studied to maximize the
localization capabilities of 6G NTN.

Spare Beams. Since PRS is designed to be decoded at very low SNR, the
satellites may use spare beams to transmit PRS to locations outside its beam
coverage. These spare beams can be turned on opportunistically if the
satellite has less area to cover on the ground (e.g. the LEO is hovering over
the boundary of land and ocean).

New Reference Signal Design. Another shortcoming of the current positioning
procedure is that the UE needs to search for a wideband PRS within a certain
search window in time. Given the distances between the UE and TRPs in TN, this
search window is less than a subframe duration. However, large relative
distances between the reference and neighboring TRPs in NTN will lead to
larger search windows spanning over multiple subframes. For UE, it may be
power-consuming to search for a wideband signal for a sufficiently long time.
Hence, it might be useful to design narrow-band synchronization signals like
synchronization signal blocks which are quasi-co-located with PRS in a
deterministic manner. For enabling Doppler measurements, 3GPP needs to
standardize new narrowband PRS where the PRS resources will be defined over
multiple slots. The TRP and the UE need to maintain phase coherence over the
transmission of this signal. While 3GPP RAN is looking into single satellite
RTT, extending it to multi-RTT has some fundamental limitations. For instance,
the UE needs to change the timing and frequency compensation of SRS for it to
be received by multiple satellites. To this end, the specification needs to
allow the UE to change its UL timing and frequency momentarily for the SRS
transmission while it maintains closed-loop timing and frequency compensation
with the serving satellite.

More Dynamic Signaling. Since satellite locations are constantly changing, the
nature of positioning assistance information sent by the LMF to UE should also
change over time. For instance, the assistance information related to the
configuration of neighboring satellites signaled at one-time instance may not
be valid for a future time instance. Another example is the PRS muting pattern
which is static for TN. In order to receive the PRS from a far satellite, the
transmission of PRS from a near satellite needs to be muted. However, since
the satellites are moving, the muting patterns must also be dynamic in nature.
In such scenarios, assuming that the PRSs instances of multiple satellites
overlap on the network side, the serving satellite may need to mute some
adjacent symbols/slots of the PRS instances in order to compensate for the
larger propagation delay of the PRS of the far satellite.

LEO and GNSS. The above discussion assumes the use of LEO networks in
isolation for positioning and navigation purposes. Another direction of
research that NTNs provide in this regard is the improvement in navigation
through orbital diversity. For example, as our preliminary simulations
demonstrate, LEOs provide augmentation or enhancement to existing GNSS. This
can be extremely useful for localization in dense urban canyons where GNSS
failure may occur with high probability. From the cellular system design
perspective, for UE-assisted positioning, the LMF needs to jointly process the
GNSS and LEO measurements. Alternately, for UE-based positioning, the cellular
modem needs to accumulate GNSS measurements and 5G NR radio measurements from
LEO and process them jointly.

In conclusion, NTN positioning is a practically relevant research topic with
many fundamental open problems. We hope that this article will put a spotlight
on some of these as we start entering the beyond 5G and 6G era.

## References

  * [1] “Technical Specification Group Services and System Aspects; Location Services (LCS); Service description; Stage 1,” _3GPP TS 22.071, version 17.0.0_.
  * [2] “TSG RAN; Study on requirements and use cases for network verified UE location for Non-Terrestrial-Networks (NTN) in NR (Release 18) ,” _3GPP TR 38.882, version 18.0.0_.
  * [3] M. L. Psiaki, “Navigation using carrier Doppler shift from a LEO constellation: TRANSIT on steroids,” _Navig. J. Inst. Navig._ , vol. 68, no. 3, pp. 621 – 641, Sep. 2021.
  * [4] H. Benzerrouk, Q. Nguyen, F. Xiaoxing, A. Amrhar, H. Rasaee, and R. J. Landry, “LEO satellites Based Doppler Positioning Using Distributed nonlinear Estimation,” _IFAC-PapersOnLine_ , vol. 52, no. 12, pp. 496–501, 2019.
  * [5] H. K. Dureppagari, D.-R. Emenonye, H. S. Dhillon, and R. M. Buehrer, “UAV-Aided Indoor Localization of Emergency Response Personnel,” in _Proc. IEEE/ION PLANS, Monterey, CA_ , Apr. 2023.
  * [6] Z. M. Kassas, S. Kozhaya, H. Kanj, J. Saroufim, S. W. Hayek, M. Neinavaie, N. Khairallah, and J. Khalife, “Navigation with Multi-Constellation LEO Satellite Signals of Opportunity: Starlink, OneWeb, Orbcomm, and Iridium,” in _Proc. IEEE/ION PLANS, Monterey, CA_ , Apr. 2023.
  * [7] J. A. del Peral-Rosado, R. Raulefs, J. A. López-Salcedo, and G. Seco-Granados, “Survey of cellular mobile radio localization methods: From 1G to 5G,” _IEEE Commun. Surv. Tutor._ , vol. 20, no. 2, pp. 1124–1148, 2017.
  * [8] “Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access (E-UTRA); LTE Positioning Protocol (LPP) (Release 9),” _3GPP TS 36.355, version 9.14.0_.
  * [9] “3rd Generation Partnership Project; Technical Specification Group Services and System Aspects; 5G System (5GS) Location Services (LCS), Stage 2, (Release 17),” _3GPP TS 23.273, version 17.7.0_.
  * [10] M. M. Azari, S. Solanki, S. Chatzinotas, O. Kodheli, H. Sallouha, A. Colpaert, J. F. Mendoza Montoya, S. Pollin, A. Haqiqatnejad, A. Mostaani, E. Lagunas, and B. Ottersten, “Evolution of non-terrestrial networks from 5G to 6G: A survey,” _IEEE Commun. Surv. Tutor._ , vol. 24, no. 4, pp. 2633–2672, 2022.
  * [11] “Technical Specification Group Radio Access Network; NR; NR and NG-RAN Overall Description;Stage 2 (Release 17),” _3GPP TS 38.300, version 17.4.0_.
  * [12] X. Lin, “An Overview of 5G Advanced Evolution in 3GPP Release 18,” _IEEE Commun. Stand. Mag._ , vol. 6, no. 3, pp. 77 – 83, Sep. 2022.
  * [13] “Technical Specification Group Radio Access Network; Study on New Radio (NR) to support non-terrestrial networks (Release 15),” _3GPP TR 38.811, version 15.4.0_.
  * [14] “Technical Specification Group Radio Access Network; Solutions for NR to support non-terrestrial networks (NTN) (Release 16),” _3GPP TR 38.821, version 16.1.0_.
  * [15] E. D. Kaplan and C. J. Hegarty, _Understanding GPS Principles and Applications, Second Edition_. Artech, 2005.


# Towards Self-Adaptive Machine Learning-Enabled Systems Through QoS-Aware
Model Switching

Shubham Kulkarni, Arya Marda, Karthik Vaidhyanathan  Software Engineering
Research Center, IIIT Hyderabad, India
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Machine Learning (ML), particularly deep learning, has seen vast advancements,
leading to the rise of Machine Learning-Enabled Systems (MLS). However,
numerous software engineering challenges persist in propelling these MLS into
production, largely due to various run-time uncertainties that impact the
overall Quality of Service (QoS). These uncertainties emanate from ML models,
software components, and environmental factors. Self-adaptation techniques
present potential in managing run-time uncertainties, but their application in
MLS remains largely unexplored. As a solution, we propose the concept of a
Machine Learning Model Balancer, focusing on managing uncertainties related to
ML models by using multiple models. Subsequently, we introduce AdaMLS, a novel
self-adaptation approach that leverages this concept and extends the
traditional MAPE-K loop for continuous MLS adaptation. AdaMLS employs
lightweight unsupervised learning for dynamic model switching, thereby
ensuring consistent QoS. Through a self-adaptive object detection system
prototype, we demonstrate AdaMLS’s effectiveness in balancing system and model
performance. Preliminary results suggest AdaMLS surpasses naive and single
state-of-the-art models in QoS guarantees, heralding the advancement towards
self-adaptive MLS with optimal QoS in dynamic environments.

###### Index Terms:

Self Adaptation, Self-adaptive systems, Software Architecture, ML-Enabled
Systems, ML4SA, Unsupervised Learning, Object Detection

##  I Introduction

Recent advancements in machine learning, especially deep learning, have
spurred the growth of Machine Learning-Enabled Systems (MLS) like ChatGPT [1],
Google Bard [2], and DALLE-2 [3]. However, engineering MLS presents
multifaceted software engineering challenges, from the development and
integration of ML components to model versioning and data quality [4, 5, 6].
Gartner’s report notes that almost half of MLS projects don’t make it to
production, mainly because of unpredictable run-time challenges like varying
model performance and unstable software components [7]. Additionally,
environmental factors like infrastructure (cost, energy) and system usage
(arrival rate etc.) significantly influence the system QoS. Over the years,
self-adaptation techniques have emerged as promising solutions for managing
run-time uncertainties [8, 9]. They enable systems to continuously adapt their
structure and/or behaviour to satisfy different goals (in terms of QoS,
functionalities, etc.). While effective in domains like CPS, IoT, and service-
oriented systems [10, 11, 12], their application in MLS is largely unexplored
[13]. In MLS, ML model performance can vary significantly due to factors like
model architecture—layer count and algorithm type. Given identical input-
output specifications, developers can devise a spectrum of models, each with
its speed and accuracy trade-offs. Recognizing this variability, we introduce
the concept of an ML Model Balancer. This notion encapsulates the idea of
dynamically evaluating and switching between models to optimize QoS. For
instance, high-traffic situations might favor a faster model, while quieter
periods prioritize accuracy. AdaMLS, our novel self-adaptive approach,
operationalizes this concept of the ML Model Balancer. Nevertheless, AdaMLS
consistently excels in navigating the intricacies of online ML deployments,
ensuring superior QoS. This includes: i) monitoring model and system
parameters; ii) analyzing model and system quality for QoS violations; iii)
using knowledge from lightweight unsupervised learning to dynamically switch
models, ensuring QoS; and iv) executing system adaptation. Prioritizing ML
model adaptability, AdaMLS shifts from conventional load balancing to QoS-
aware dynamic ML model switching. By continuously tuning model selections in
response to environmental cues and system demands, AdaMLS guarantees MLS QoS,
promoting consistent MLS operation in live settings. This represents a stride
towards future-ready self-adaptive MLS, designed to maintain an optimal
performance equilibrium amidst changing data and user demands. We evaluate
AdaMLS using an object detection use case through utility (refer section II)
showcasing a self-adaptive prototype. Our preliminary findings indicate that
the runtime model switching, facilitated by lightweight unsupervised learning,
effectively manages both system and model performance. This enables AdaMLS to
surpass both naive strategies and individual models in terms of Quality of
Service (QoS). Our work innovatively adapts the MAPE-K loop to address the
uncertainties inherent in MLS, emphasizing dynamic model-switching approach.
Through AdaMLS’s real-world application, we highlight our move toward self-
adaptive MLS that can deftly switch between models based on data shifts and
user demands, always maintaining optimal QoS. The paper is structured as
follows: Section 2 provides motivation with a running example. Section 3
introduces the AdaMLS approach. Results from its application are in Section 4.
Related work is discussed in Section 5, and Section 6 concludes.

TABLE I: Reducing Uncertainty in Self-adaptive Systems Uncertainty Source |  Uncertainty Explanation |  Mitigation Strategy |  Implemented In
---|---|---|---
ML Models in MLS |  Abstraction of ML model |  Evaluate all models on test set; abstract performance with statistics |  Learning Engine
Resources |  Dynamicity in the system |  Preload ML Models; reduce latency and adaptation action costs |  MLS
Environment |  Incoming requests Unpredictability |  Monitor request rate and produced results continuously |  Monitor
Adaptation Function |  Impact of tactic |  Utilize confidence intervals for adaptation rules, ensuring assurance |  Learning Engine
Goal |  Conflicting or dependent goals |  Prioritize most accurate model among eligible models for requests |  Planner
Data Drift |  Untrained or rare data |  Map performance for past ’n’ requests to nearest cluster for insight |  Analyzer
Model Drift |  Model performance decay |  Rank models per goal; auto-remove degraded models |  Planner

##  II Running Example

Our AdaMLS111unless specified otherwise by model we imply ML model in this
paper approach is showcased via an object detection system, a culmination of
ML advancements over decades [14]. The system consists a web service with a
REST API, model_repo as the repository, message_broker for image streaming,
and obj_model using YOLO [15]. These components mirror services like Google
Cloud Vision or Amazon Rekognition, emphasizing real world applicability. In
the example, we define a set $M$ of available models. Each model $m_{j}$,
where $j$ ranges from 1 to $n$, is part of $M$. Here this set includes YOLOv5
models (YOLOv5n, YOLOv5s, YOLOv5m, YOLOv5l, YOLOv5x) provided by Ultralytics
[16], pretrained on the COCO 2017 training dataset [17]. Models in $M$ are
quantified as mAP - model’s effectiveness in detecting objects, symbolized by
$c$, and performance. Performance is assessed using $\tau^{\prime}$, $\tau$,
and $r$. Here, $\tau^{\prime}$ denotes the processing time per image by system
(i.e., individual processing without network or queuing delay), $\tau$ is the
model’s processing time, and $r$ is the system response time in real-world
operations, encompassing network, queuing, and processing delays. For
instance, YOLOv5n has 1.9M parameters, an mAP of 28, and a 45-ms $\tau$, while
YOLOv5x has 86M parameters, mAP 50.7, and 766 ms $\tau$ [16]. Different models
vary in response time and confidence scores, with none achieving an optimal
balance between both. Given this context, and given a set of thresholds
including $C_{\max}$ and $C_{\min}$, denoting the maximum & minimum confidence
score; $R_{\max}$ and $R_{\min}$, the maximum & minimum allowed response time;
the goal is to maximize the utility function $U$. This function evaluates the
confidence score $c_{i}$ and response time $r_{i}$ for each image $i$. Herein,
$p_{ev}$ and $p_{dv}$ represent the penalties for violations relative to these
thresholds. The total utility $U$ of the system for all $k$ unique image ID
processed, is given by $U=\sum_{i=1}^{k}U_{i}$. For the $i^{th}$ image the
utility $U_{i}$ is defined as $U_{i}=w_{e}E_{\tau_{i}}+w_{d}T_{\tau_{i}}$,
where $w_{e}$ and $w_{d}$ are weights, $E_{\tau_{i}}$ and $T_{\tau_{i}}$ are
piece-wise functions that represent the $c$ and $r$ respectively, defined as:

$E_{\tau_{i}}=\begin{cases}c_{i}&\text{if }C_{\min}\leq c_{i}\leq C_{\max}\\\
(c_{i}-C_{\max})\cdot p_{ev}&\text{if }c_{i}>C_{\max}\\\ (C_{\min}-c_{i})\cdot
p_{ev}&\text{if }c_{i}<C_{\min}\end{cases}$

$T_{\tau_{i}}=\begin{cases}r_{i}&\text{if }R_{\min}\leq r_{i}\leq R_{\max}\\\
(R_{\max}-r_{i})\cdot p_{dv}&\text{if }r_{i}>R_{\max}\\\ (r_{i}-R_{\min})\cdot
p_{dv}&\text{if }r_{i}<R_{\min}\end{cases}$

Given the thresholds and constraints, our approach aims to maximize utility
function thereby improving the overall QoS.

##  III AdaMLS Approach

AdaMLS provides a robust solution to two pivotal learning problems[18]:
adaptation policy development and resource usage analysis.Leveraging
unsupervised learning to identify unknown patterns in MLS’s runtime
performance, the Learning Engine (LE) provides adaptation rules. As outlined
in Table I and defined in [19] and [13], these rules, when executed by MAPE-K,
effectively mitigate uncertainties.

Figure 1: AdaMLS Approach

###  III-A Learning Engine

The Learning Engine (LE) initializes with the ML Models Executor, operating
all models $m_{j}\in M$ on an evaluation dataset (e.g., COCO Test 2017) from
the Data Store. It saves detection outcomes in dataset $d_{j}$ for each model.
Outputs include KPIs like $c$, $\tau$, $r$, and $s$; where $s$ signifies CPU
Consumption(%), aiding in uncertainty mitigation as said in Table I.The
Unsupervised Model builder uses K-Means clustering on each $d_{j}$ based on
$\tau^{\prime}$, grouping models by performance attributes, thereby hastening
model selection during runtime adjustments. Clustering with $\tau^{\prime}$ is
strategic, given our hierarchical approach where response time is paramount.
$\tau^{\prime}$ isn’t arbitrary but marks our primary metric. This ensures
models first align with the vital response-time criteria before secondary
metrics such as accuracy. This clustering navigates model spectrum
effectively, grouping models with akin performance, facilitating dynamic
switches to select from relevant QoS subsets. Each image $i$ of model $m_{j}$
gets a cluster label $l$.

The Performance Evaluator constructs a performance matrix for each model
$m_{j}\in M$, by collating KPIs across models ($m_{q}\in M$ where $q\neq j$)
for the same request. Let’s consider model $m_{j}$, known as ’nano’ (Yolov5n).
For each image $i$, KPIs are collated across all models using the Image ID,
resulting in a comprehensive matrix for ’nano’. Each row in this matrix
represents an image, while columns correspond to KPIs from all models and the
assigned cluster number from ’nano’.

The Adaptation Rule Creator calculates the 90% confidence intervals (CI) for
each cluster $l$ of every model $m_{j}$. These upper and lower limit intervals
provide a statistically likely range for KPIs, thereby reducing uncertainty in
system adaptations as per Table I. To illustrate, consider model ’nano’ as
$m_{j}$. For each cluster $l$ in ’nano’, CIs are calculated for all data
points, using only those images within the same cluster. Simultaneously, the
CIs for the same images are calculated from the performance metrics of all
other models $m_{k}$. This process results in a CI matrix for ’nano’,
encapsulating potential performance variations across models. Repeating this
for all models, LE produces a set of CI matrices. Each matrix maps out
performance variations within each cluster of the respective model $m_{j}$.
Through LE, executed periodically in batches, AdaMLS develops a holistic
understanding of potential model performance shifts, enabling statistical
predictions of system KPIs impacts due to model switching.

###  III-B MAPE-K Loop

####  III-B1 Knowledge

As per the structure depicted in Figure 1, the Knowledge (K) base in our
system is primarily a repository divided into three sections: the Log
Repository, the Adaptation Rule Repository, and the System Metrics Repository.
The Log Repository stores system logs, including vital KPIs. For instance, in
our running example, this would mean processing time per image by the system
$\tau$, the system response time $r$, model confidence $c$, and CPU
consumption $s$ for all processed requests $k$, as recorded by the MLS. The
Adaptation Rule Repository houses the CI matrix generated by the LE, acting as
a set of adaptation rules for the Planning phase. Lastly, the System Metrics
Repository keeps track of various system metrics such as real-time incoming
request rate per second denoted as $v$ and system logs if any.

####  III-B2 Monitor

The ML Metric Monitor component continuously tracks system QoS and KPIs. In
our use case, this includes the avg. number of detection boxes in processed
image $b$,$\tau$,$r$,$c$ and $s$ from the last $i$ processed requests denoted
as $k^{\prime}$, and for System QoS Monitor component, it is the current model
in use denoted as $m^{\prime}$ and $v$ to mitigate environmental uncertainty
as per Table I. The system also tracks the number of pending requests $i_{w}$,
which provides insight into the workload. The monitored data is sent to the
Analyze function for potential adaptations maintaining system self-awareness
also logged in Knowledge appropriately.

####  III-B3 Analyzer

In Analyzer phase, the Planner Initiator utilizes the System Evaluator to
analyze the data from the Monitor, to determine if a system adaptation is
necessary. The System Evaluator identifies the closest cluster, $l$, from the
CI matrix for $m^{\prime}$, to the current system state. This state is defined
as the mean of the most recent $k^{\prime}$ (e.g. 50) results for
$m^{\prime}$. This identification process is grounded in the two KPIs
exhibiting the highest variance. Process mitigates data drift uncertainty as
outlined in Table I. Upon identifying cluster $l$, a feasible request rate
range [$v_{min},v_{max}$] is determined from CI matrix of $m^{\prime}$ and is
computed using the inverse of the upper and lower confidence interval bounds
for $\tau$ for $m^{\prime}$. Subsequently, the Load Calculator computes the
adjusted request rate $v_{adj}$ by adding $i_{w}$ (those exceeding $v_{max}$)
to $v$.

If $v_{adj}$ not in [$v_{min}$, $v_{max}$], the Planner Initiator waits for a
brief period $t_{wait}$ (e.g. 0.25 sec) to avoid unnecessary system
adaptations and then initiates Planner with $v_{adj}$, $m^{\prime}$, and $l$.

####  III-B4 Planner

During the Planning phase, the Strategy Formulator uses the output from the
Analyzer and Knowledge base to devise an adaptation strategy. The strategy
identifies potential models from $M$ that can accommodate $v_{adj}$ and belong
to cluster $l$. The compatibility of a model is determined by comparing
$v_{adj}$ with the inverse of lower value of CI bound for $\tau$; for the
current model $m^{\prime}$, the most recent $n$ results are used, whereas for
other models in $M$, the CI matrix of $m^{\prime}$ is referenced. The Model
Selector then picks $m_{best}$, the model with the highest lower confidence
interval value for $c$, thereby mitigating goal and model drift uncertainties
as per Table I. If $m^{\prime}=m_{best}$, the Planner refrains from taking
further action. Otherwise, the Planner signals a model switch to the Execution
phase. The system persists with $m^{\prime}$ if no suitable model is
identified.

####  III-B5 Executor

In the Execution phase, the Adaptation Executor carries out the plan. If the
Planner signals a model switch, i.e., $m_{best}\neq m^{\prime}$, the system
transitions to $m_{best}$. If no switch is signaled, the system persists with
the current model. Both situations guarantee system autonomy, adaptability to
changing conditions, and enhanced learning through updates logged in the
Knowledge base.

##  IV Preliminary Results

We implement AdaMLS on an object detection system (refer section II) using
YOLOv5 variants alongside FastAPI. For testing, we emulate a FIFA98 situation
[20], with up to 28 parallel requests/sec and a total of 25,000 requests. We
employ the COCO 2017 unlabelled dataset [17] as our testing dataset, with the
COCO 2017 test dataset as evaluation dataset. Our data clustering is
facilitated through Python and PySpark’s MLlib [21], with the optimal clusters
being defined by the elbow method [22]. The complete specifics of our
implementation, parameters and the ensuing results are detailed in [23]. In
our evaluation, AdaMLS is evaluated against both the naive approach and
individual YOLOv5 models. The naive approach transitions between models based
on preset $v$ thresholds. Referring to the data in Table II, it is clear that
AdaMLS effectively decreases the average response time $r$ while
simultaneously reducing the occurrence of penalties associated with response
time and confidence. Parameters used for utility are: $p_{ev}$ = 1,$p_{dv}$ =
1,$C_{\max}$ = 1,$C_{\min}$ = 0.5, $R_{\max}$ = 1s, $R_{\min}$ = 0.1s,
$t_{wait}$ = 0.25s and $k^{\prime}$ = 50. A key aspect of our results is the
utility metric, detailed in Table III. While utility, a measure quantifying
the effectiveness and efficiency of a model in various operational contexts
(as detailed in Section II), offers an effective measure, it’s not the sole
criterion for evaluating QoS in ML systems. Although AdaMLS does not
consistently lead in all individual metrics, it demonstrates unparalleled
efficacy in terms of utility. Specifically, AdaMLS achieves an overall
increased utility, particularly when equal emphasis is placed on response time
and confidence score, surpassing the Yolov5n model by as much as 39%. This
remarkable performance in utility, even when not consistently leading in every
individual metric, is significant. It underscores our method’s ability to
integrate these metrics effectively for optimal outcomes. Therefore, utility
acts as a measure of our system’s proficiency in addressing challenges and
maintaining high-quality performance. Moreover, our refined architecture
reduces the time required for model transitions, ensuring it remains below the
crucial threshold of 0.01 seconds, further solidifying AdaMLS’s contribution
to improving the QoS of ML-driven systems.

TABLE II: Performance Comparison Parameter | Yolov5n | Naive | AdaMLS
---|---|---|---
Model Switch Instances | N/A | 49 | 308
Avg. Confidence Score (c) | 0.535 | 0.606 | 0.6
Avg. Response time (r) | 0.28 | 1.94 | 0.47
Avg. CPU Consumption | 42.94 | 66.42 | 65.27
Penalty Instances for r | 365 | 7731 | 927
Penalty Instances for c | 9770 | 5843 | 6137
TABLE III: Utility Comparison $w_{e}$ | $w_{d}$ | Yolov5n | Yolov5s | Yolov5m | Yolov5l | Yolov5x | Naive | AdaMLS
---|---|---|---|---|---|---|---|---
0 | 1 | 5817 | $-7.9\times 10^{5}$ | $-10\times 10^{6}$ | $-39\times 10^{6}$ | $-81\times 10^{6}$ | -27313 | 9978
0.25 | 0.75 | 6487 | $-5.9\times 10^{5}$ | $-7.8\times 10^{6}$ | $-29\times 10^{5}$ | $-61\times 10^{6}$ | -17427 | 8992
0.5 | 0.5 | 7157 | $-3.9\times 10^{5}$ | $-5.2\times 10^{6}$ | $-19\times 10^{6}$ | $-40\times 10^{6}$ | -7541 | 9978
0.75 | 0.25 | 7827 | $-1.8\times 10^{5}$ | $-2.5\times 10^{6}$ | $-9.9\times 10^{6}$ | $-20\times 10^{6}$ | 2345 | 10964
1 | 0 | 8498 | 12566 | 14612 | 15270 | 16264 | 12231 | 11949

Figure 2: Model Switching: Naive Vs. AdaMLS

Figure 3: Utility Function Over Requests processed

##  V Related Work

The inception of self-adaptive systems dates back to IBM’s autonomic computing
vision [24]. The principle’s application to ML Systems (MLS) is commenced by
seminal work [13], which doesn’t consider model switching as an adaptive
tactic despite studies on retraining ML components’ cost-benefit trade-offs
[25]. In addition, the concept of self-adaptation of ML was introduced as a
primer in [5]. However, it wasn’t realized or elaborated in detail. While
Convolutional Neural Networks (CNNs) have enhanced object detection [26], the
optimal architectural selection remains a real-world challenge. Recent
advancements have primarily concentrated on enhancing individual models [27,
28, 29, 30, 31], neglecting system-wide adaptability. A recent survey
summarizes the use of ML for engineering self-adaptive systems and it also
highlights the underutilization of unsupervised learning [18]. AdaMLS, our
solution, fills this gap by combining unsupervised learning and model
switching to boost MLS adaptability. and echoes the need for robust
architectural practices for ML systems [32].

##  VI Conclusion

To conclude, we introduced AdaMLS, an innovative solution that engineers self-
adaptive Machine Learning Systems (MLS) by employing unsupervised learning for
dynamic model switching. Preliminary evaluations, based on an object detection
system example indicate that AdaMLS can effectively mitigate run-time
uncertainties and outperforms both traditional and standalone models. Thereby,
offering significant QoS improvements. AdaMLS stands as a significant
advancement, showcasing the potential of engineering MLS with self-adaptation
capabilities. Importantly, it paves the way for MLS to execute seamless model
switching to maintain optimal QoS under varying run-time uncertainties.
Looking forward, we intend to explore a diverse range of learning techniques
and model-switching strategies to further enhance the adaptability of AdaMLS.
Emphasis will also be laid on broadening its applications to different
domains, and on improving the environmental and economic sustainability of
MLS, thereby revolutionizing the future of MLS implementation and design.

## References

  * [1] OpenAI, “Chatgpt,” https://openai.com/research/chatgpt, 2021.
  * [2] G. AI, “Google bard,” 2023. [Online]. Available: https://bard.google.com/
  * [3] OpenAI, “Dall-e-2,” https://openai.com/product/dall-e-2, 2021.
  * [4] G. A. Lewis, I. Ozkaya, and X. Xu, “Software architecture challenges for ml systems,” in _2021 IEEE International Conference on Software Maintenance and Evolution (ICSME)_. IEEE, 2021, pp. 634–638.
  * [5] H. Muccini and K. Vaidhyanathan, “Software architecture for ml-based systems: What exists and what lies ahead,” in _2021 IEEE/ACM 1st Workshop on AI Engineering-Software Engineering for AI (WAIN)_. IEEE, 2021, pp. 121–128.
  * [6] S. Amershi, A. Begel, C. Bird, R. DeLine, H. Gall, E. Kamar, N. Nagappan, B. Nushi, and T. Zimmermann, “Software engineering for machine learning: A case study,” in _2019 IEEE/ACM 41st International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP)_. IEEE, 2019, pp. 291–300.
  * [7] “Trend,” https://tinyurl.com/2abwwdx7.
  * [8] D. Weyns, _An Introduction to Self-adaptive Systems: A Contemporary Software Engineering Perspective_. John Wiley & Sons, 2020.
  * [9] ——, “Software engineering of self-adaptive systems: an organised tour and future challenges,” _Chapter in Handbook of Software Engineering_ , p. 2, 2017.
  * [10] J. Cámara, B. Schmerl, and D. Garlan, “Software architecture and task plan co-adaptation for mobile service robots,” in _2020 IEEE/ACM 15th International Symposium on Software Engineering for Adaptive and Self-Managing Systems (SEAMS)_ , ser. SEAMS ’20. New York, NY, USA: Association for Computing Machinery, 2020, p. 125–136. [Online]. Available: https://doi.org/10.1145/3387939.3391591
  * [11] J. Cámara, H. Muccini, and K. Vaidhyanathan, “Quantitative verification-aided machine learning: A tandem approach for architecting self-adaptive iot systems,” in _2020 IEEE International Conference on Software Architecture (ICSA)_ , 2020, pp. 11–22.
  * [12] D. Weyns and R. Calinescu, “Tele assistance: A self-adaptive service-based system exemplar,” in _2015 IEEE/ACM 10th International Symposium on Software Engineering for Adaptive and Self-Managing Systems_ , 2015, pp. 88–92.
  * [13] M. Casimiro, P. Romano, D. Garlan, G. A. Moreno, E. Kang, and M. Klein, “Self-adaptation for machine learning based systems.” in _ECSA (Companion)_ , 2021.
  * [14] Z. Zou, K. Chen, Z. Shi, Y. Guo, and J. Ye, “Object detection in 20 years: A survey,” _Proceedings of the IEEE_ , 2023.
  * [15] J. Redmon, S. Divvala, R. Girshick, and A. Farhadi, “You only look once: Unified, real-time object detection,” in _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016, pp. 779–788.
  * [16] G. Jocher, “YOLOv5 by ultralytics,” may 2020. [Online]. Available: https://github.com/ultralytics/yolov5
  * [17] T. Lin, M. Maire, S. J. Belongie, L. D. Bourdev, R. B. Girshick, J. Hays, P. Perona, D. Ramanan, P. Doll’a r, and C. L. Zitnick, “Microsoft COCO: common objects in context,” _CoRR_ , vol. abs/1405.0312, 2014. [Online]. Available: http://arxiv.org/abs/1405.0312
  * [18] O. Gheibi, D. Weyns, and F. Quin, “Applying machine learning in self-adaptive systems: A systematic literature review,” _ACM Trans. Auton. Adapt. Syst._ , vol. 15, no. 3, aug 2021. [Online]. Available: https://doi.org/10.1145/3469440
  * [19] J. Cámara, J. Troya, A. Vallecillo, N. Bencomo, R. Calinescu, B. H. C. Cheng, D. Garlan, and B. Schmerl, “The uncertainty interaction problem in self-adaptive systems,” _Softw. Syst. Model._ , vol. 21, no. 4, p. 1277–1294, aug 2022. [Online]. Available: https://doi.org/10.1007/s10270-022-01037-6
  * [20] P. Rodriguez, C. Spanner, and E. Biersack, “Analysis of web caching architectures: hierarchical and distributed caching,” _Networking, IEEE/ACM Transactions on_ , vol. 9, pp. 404 – 418, 09 2001.
  * [21] M. Zaharia, R. S. Xin, P. Wendell, T. Das, M. Armbrust, A. Dave, X. Meng, J. Rosen, S. Venkataraman, M. J. Franklin, A. Ghodsi, J. Gonzalez, S. Shenker, and I. Stoica, “Apache Spark: A unified engine for big data processing,” 2016. [Online]. Available: https://spark.apache.org/
  * [22] E. Umargono, J. E. Suseno, and S. Gunawan, “K-means clustering optimization using the elbow method and early centroid determination based-on mean and median,” in _Proceedings of the International Conferences on Information System and Technology_. SCITEPRESS—Science and Technology Publications Setubal, Portugal, 2019, pp. 234–240.
  * [23] Shubham Kulkarni, Arya Marda, and Karthik Vaidhyanathan, “AdaMLs - Towards Self-Adaptive Machine Learning-Enabled Systems Through QoS-Aware Model Switching,” 2023, GitHub repository. [Online]. Available: https://github.com/sa4s-serc/AdaMLS
  * [24] T. Wong, M. Wagner, and C. Treude, “Self-adaptive systems: A systematic literature review across categories and domains,” _Information and Software Technology_ , vol. 148, p. 106934, 2022. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0950584922000854
  * [25] M. Casimiro, P. Romano, D. Garlan, and L. Rodrigues, “Towards a framework for adapting machine learning components,” in _2022 IEEE International Conference on Autonomic Computing and Self-Organizing Systems (ACSOS)_ , 2022, pp. 131–140.
  * [26] J. Huang, V. Rathod, C. Sun, M. Zhu, A. Korattikara, A. Fathi, I. Fischer, Z. Wojna, Y. Song, S. Guadarrama, and K. Murphy, “Speed/accuracy trade-offs for modern convolutional object detectors,” in _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_. Los Alamitos, CA, USA: IEEE Computer Society, jul 2017, pp. 3296–3297. [Online]. Available: https://doi.ieeecomputersociety.org/10.1109/CVPR.2017.351
  * [27] K. Kotar and R. Mottaghi, “Interactron: Embodied adaptive object detection,” in _2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_. Los Alamitos, CA, USA: IEEE Computer Society, jun 2022, pp. 14 840–14 849. [Online]. Available: https://doi.ieeecomputersociety.org/10.1109/CVPR52688.2022.01444
  * [28] J.-B. Hou, X. Zhu, and X.-C. Yin, “Self-adaptive aspect ratio anchor for oriented object detection in remote sensing images,” _Remote Sensing_ , vol. 13, no. 7, 2021. [Online]. Available: https://www.mdpi.com/2072-4292/13/7/1318
  * [29] C. Zhang, Z. Li, J. Liu, P. Peng, Q. Ye, S. Lu, T. Huang, and Y. Tian, “Self-guided adaptation: Progressive representation alignment for domain adaptive object detection,” _IEEE Transactions on Multimedia_ , vol. PP, pp. 1–1, 05 2021.
  * [30] K. Goyal and J. Singhai, “Texture-based self-adaptive moving object detection technique for complex scenes,” _Computers & Electrical Engineering_, vol. 70, pp. 275–283, 2018. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0045790616301501
  * [31] S. Deng, S. Li, K. Xie, W. Song, X. Liao, A. Hao, and H. Qin, “A global-local self-adaptive network for drone-view object detection,” _IEEE Transactions on Image Processing_ , vol. 30, pp. 1556–1569, 2021.
  * [32] J. Leest, I. Gerostathopoulos, and C. Raibulet, “Evolvability of machine learning-based systems: An architectural design decision framework,” in _2023 IEEE 20th International Conference on Software Architecture Companion (ICSA-C)_ , 2023, pp. 106–110.


# Particle-level Compression for New Physics Searches

Yifeng Huang
Department of Physics and Astronomy
University of California, Irvine
<EMAIL_ADDRESS>&Jack Collins
SLAC National Accelerator Laboratory
<EMAIL_ADDRESS>&Simon Knapen
Physics Division
Lawrence Berkeley National Laboratory, Berkeley
Berkeley Center for Theoretical Physics
University of California, Berkeley<EMAIL_ADDRESS>&Daniel Whiteson
Department of Physics and Astronomy
University of California, Irvine
<EMAIL_ADDRESS>&Benjamin Nachman
Physics Division
Lawrence Berkeley National Laboratory, Berkeley
Berkeley Institute for Data Science
University of California, Berkeley
<EMAIL_ADDRESS>
###### Abstract

In collider-based particle and nuclear physics experiments, data are produced
at such extreme rates that only a subset can be recorded for later analysis.
Typically, algorithms select individual collision events for preservation and
store the complete experimental response. A relatively new alternative
strategy is to additionally save a partial record for a subset of events,
allowing for later specific analysis of a larger fraction of events. We
propose a strategy that bridges these paradigms by compressing entire events
for generic offline analysis but at a lower fidelity. An optimal-transport-
based $\beta$ Variational Autoencoder (VAE) is used to automate the
compression and the hyperparameter $\beta$ controls the compression fidelity.
We introduce a new approach for multi-objective learning functions by
simultaneously learning a VAE appropriate for all values of $\beta$ through
parameterization. We present an example use case, a di-muon resonance search
at the Large Hadron Collider (LHC), where we show that simulated data
compressed by our $\beta$ VAE has enough fidelity to distinguish distinct
signal morphologies.

##  1 Introduction

The rate and size of interaction events at modern particle and nuclear physics
experiments typically prohibit storage of the complete experimental dataset
and require that many interaction events be discarded in real time by a
trigger system. For example, at the Large Hadron Collider (LHC), collisions
occur at a rate of 40 MHz, but the ATLAS and CMS experiments recording rates
are typically $\mathcal{O}(\text{kHz})$ ATLAS:2016wtr; CMS:2016ngn. For
selected events, the complete experimental response is preserved for later
analysis. When the scientific goals only require identifying events which
contain rare and easy-to-identify objects, such as high energy photons, the
trigger system is highly efficient. However, this strategy leaves unexamined
the vast majority of the events, including many with complex features that are
hard to quickly identify online and/or may not be rare.

An alternative approach to fully recording a small fraction of the events is
to preserve a partial record of a larger fraction Aaij:2016rxn; CMS:2016ltu;
ATLAS:2018qto. This strategy has allowed access to lower energy phenomena
which occur at higher rates, but the utility of these partial data records is
limited. For example, a recent partial-event analysis targets di-muon
resonances CMS:2019buh, only recording the four-momenta of the two muons and a
small number of additional event properties for low-mass events that would
otherwise be too high rate for the full-event trigger system. This approach
has the potential to make a major discovery, but the lack of a full event
record makes it nearly impossible to _diagnose_ such a discovery. To
distinguish between several competing hypotheses which might generate a peak
in the di-muon spectrum would require recording new data with a dedicated
trigger, which is both time consuming and expensive.

We propose an approach that bridges the full and partial event paradigms
automatically with machine learning. This is accomplished by training a neural
network to learn a lossy event compression with a tunable resolution
parameter. An extreme version of this approach would be to save every event at
the highest resolution allowable by hardware (see e.g. Ref.
DiGuglielmo:2021ide for autoencoders in hardware). We present a more modest
version in which we envision full event compression which could run alongside
partial event triggers to expand their utility for a larger range of offline
analyses. Our approach uses a optimal transport-based Variational Autoencoder
(VAE) following Ref. Collins:2021pld.

In a proof-of-concept study, we compress and record a sample of simulated
interactions which are similar to those analyzed in Ref CMS:2019buh,
preserving information which would otherwise be lost. We show that this
additional information can be used to effectively discriminate between two
signal models which are difficult to distinguish with only the muon
kinematics. The overall structure of the proposal is that first, a signal is
discovered in a trigger-level analysis such as this dimuon resonance search.
Subsequently, a compressed version of the hadronic event data, which has been
stored alongside the muons, can be used to rule out or favour candidate signal
models.

##  2 Related Work

An alternative to compressing individual events is compressing the entire
dataset online Butter:2022lkf, which is methodologically and practically more
challenging. An alternative to saving events for offline analysis is to look
for new particles automatically with online anomaly detection Cerri:2018anq;
Knapp:2020dde; Govorkova:2021hqu; Mikuni:2021nwn. While we build our VAE on
the setup from Ref. Collins:2021pld using the Sinkhorn approximation sinkhorn;
sinkhorn1967 to the Earth Movers Distance, other possibilities have been
explored, such as using graph neural networks Tsan:2021brw. We leave a
comparison of the power of different approaches to future work.

##  3 $\beta$-parameterized Variational Autoencoder

We represent each collider event $x$ as a point cloud of 3-vectors
$\\{p_{\textrm{T}}/H_{\textrm{T}},\eta,\phi\\}$, where $\eta$ and $\phi$ are
the geometric coordinates of particles in the detector, and $p_{\textrm{T}}$
their transverse momenta which correspond to the weights in the point cloud.
These are normalized for each event using
$H_{\textrm{T}}=\sum_{i}p_{\textrm{T},i}$. We build an EMD-VAE
Collins:2021pld; Fraser:2021lxm; Kingma2014AutoEncodingVB trained to minimize
a reconstruction error given by an approximation to the 2-Wasserstein distance
between collider events $x$ and reconstructed examples $x^{\prime}$, with loss
function

$L=\left<S(x,x^{\prime}(z))/\beta+D_{\text{KL}}(q(z|x)||p(z))\right>_{p(x)}.$
(1)

An encoder network maps the input $x$ to a Gaussian-parameterized distribution
$q(z|x)$ on 256-dimensional latent coordinates $z$. This network is built as a
Deepsets/Particle Flow Network (PFN) zaheer2017deep; Komiske:2018cqr. A
decoder $x^{\prime}(z)$ maps latent codes $z$ to jets $x^{\prime}$,
parameterizing a posterior probability $\log p(x|z)\propto
S(x,x^{\prime}(z))/\beta$, where $S(x,x^{\prime}(z))$ is a sharp Sinkhorn
sinkhorn1967; Cuturi2013SinkhornDL; luise2018differential; patrini2020sinkhorn
approximation to the 2-Wasserstein distance between event $x$ and its decoded
$x^{\prime}$ with ground distance given by $M_{ij}=\Delta
R^{2}_{ij}\equiv(\eta_{i}-\eta_{j})^{2}+(\phi_{i}-\phi_{j})^{2}$, and
calculated using the same algorithm and parameters as in Ref Collins:2021pld.
This decoder network is built as a dense neural network.
$D_{\text{KL}}(q(z|x)||p(z))$ is the KL divergence between the encoder
probability $q(z|x)$ and the prior $p(z)$, which we take to be a standard
Gaussian. This KL divergence can be expressed as a sum of contributions from
each of the 256 latent space directions. The details of the architecture setup
is described in the Appendix.

The quantity $\beta$ is typically taken to be a fixed hyperparameter of the
network Higgins2017betaVAELB which controls the balance between reconstruction
fidelity and degree of compression in the latent space. In this work, we make
a novel contribution by elevating $\beta$ from a fixed hyperparameter to an
input of both the encoder and decoder networks. Training events are each
accompanied by a value for $\beta$ generated from some arbitrary distribution
which is provided as an additional input to both the encoder and decoder, and
included in the loss calculation for each event. The encoder and decoder then
become dependent on the input value for $\beta$, and can be written as
$q(z|x;\beta)$ and $x^{\prime}(z;\beta)$, respectively. During testing, events
can be input with whatever value for $\beta$ is deemed useful for a particular
application. In this work we take advantage of this property purely for its
usefulness in prototyping. However, it is conceivable that the ability to vary
$\beta$ on the fly could prove valuable for an online application that has
time-varying constraints on data transmission rates or requirements on
reconstruction fidelity. Furthermore, we have found that $\beta$-annealing is
neither required nor helpful in improving our VAE performance, significantly
reducing the complexity and time required for training and experiments.

##  4 Numerical Results

In this section we will illustrate how a VAE trained to compress the full
event at trigger level might be used to augment a trigger-level dimuon
resonance search and allow physicists to distinguish between different
potential hypothetical signal models without having to record new data using
the full-event trigger system.

We train our $\beta$-parameterized VAE using simulated Standard Model events,
specifically an inclusive $b$-quark jet sample ($p_{\textrm{T}}\gtrsim 4$
GeV/c), weighted as $\sim 1/p_{\textrm{T}}^{-3}$. We then consider two
potential signals which might be found in a trigger-level dimuon resonance
search: first, a light scalar decaying to muons ($S\to 2\mu$) produced in an
exotic $B$-meson decay ($B\to KS$) and secondly, a dimuon resonance produced
in a hidden valley model Strassler:2006im, from an example in Ref.
Knapen:2021eip. The latter model has more hadronic activity than the former,
as well as a small amount of invisible momentum, but has otherwise very
similar muon kinematics. More details can be found in the Appendix. All signal
and background events were generated with the Pythia event generator
Sjostrand:2014zea. A simple binary classifier (see Appendix) trained on only
the two highest-$p_{\textrm{T}}$ muons taken from the two signal event samples
achieves an AUC of 0.71. The dimuon spectra are different but not convincingly
so, and any attempt to distinguish the two signals based on the dimuons alone
would be additionally complicated by the uncertainties on details of the
showering model for the hidden valley scenario. However, the hadronic activity
in the two signal classes is very distinctive, and even a relatively low-
fidelity VAE reconstruction may tell them apart.

The structure that is learnt by the VAE as a function of $\beta$ is
qualitatively illustrated in Figs. 1 and 2. In Fig. 1, the red points
represent an event from the $b\bar{b}$ test sample, and the blue its maximum
likelihood estimate (MLE) reconstruction (defined using the the maximum
likelihood latent code for reconstruction rather than a random sample) at
various values for $\beta$. Each point represents a particle in the event,
with area proportional to the momentum $p_{\textrm{T}}$ of the corresponding
particle. We see that for large $\beta$, the VAE learns an uninformative
average over all training events, but for smaller values of $\beta$ it begins
to learn a more precise reconstruction.

Figure 1: Reconstruction of an SM event as a function of $\log_{10}\beta$. Red
points: Example test event. Blue points: MLE reconstruction of the same test
event. Each point represents a particle in the event, with area proportional
to the particle’s $p_{\textrm{T}}$. The number of active latent dimensions
(defined as those with $D_{\text{KL},i}>0.1$) is 0, 9, and 48 at each of these
$\beta$ values respectively, and the compression rates $D_{\text{KL}}$ are 0,
12, and 145 bits, respectively.

Some properties of the information content of the learnt representations are
reflected in Fig. 2. In the left plot, we show the individual KL divergences
associated with each of the 256 latent space directions as a function of
$\beta$. We see that for $\beta>1$, all latent space directions are
uninformative. Latent directions start to become sequentially informative with
$D_{KL}>0$, for $\beta<1$. For any value of $\beta$, there is a clear
hierarchy of information content in different latent directions, which can be
utilized for an efficient encoding: those values which are encoded with low
resolution (large variance for $q(z|x)$) can safely be represented with lower
precision numbers than those having higher resolution. Note that the
$\left<D_{\text{KL}}(q(z|x)||p(z))\right>_{p(x)}>\mathcal{I}(x;z)$, with
$\mathcal{I}$ being the mutual information, and therefore the KL divergence
places an upper bound on the minimum number of bits required for the lossy
compression algorithm with average distortion $\left<S(x,x^{\prime})\right>$.

The overall structure of the left plot is summarized by the two heat
capacities in the right plot, defined in analogy with the thermodynamic heat
capacity alemi2018therml; rezende2018taming; Collins:2021pld by

$C_{S}=\frac{d\left<S(x,x^{\prime})\right>}{d\beta},~{}~{}~{}~{}~{}C_{\mathrm{KL}}=-\frac{d\left<D_{\text{KL}}(q(z|x)||p(z))\right>}{d\log\beta}.$
(2)

Because the lines in the left plot have gradient close to $-0.5$, the heat
capacities are related to the effective number of degrees of the system by
$\text{dim}\;\simeq 2C$, similarly to a thermodynamic system with quadratic
Hamiltonian. There is a plateau for $\beta\lesssim 10^{-2}$, indicating that
the VAE is unable to learn additional informative structure at smaller scales
than this. For $\beta\lesssim 10^{-4}$, the VAE begins to overfit the data and
the two heat capacities diverge.

Figure 2: Left: KL divergences of the 256 individual latent space directions
as a function of $\beta$, averaged over the test SM data. Right: Heat
capacities on same data, defined in the text. Figure 3: AUC for classification
between the two signal models as a function of $\beta$, the parameter that
controls the compression fidelity.

Having trained a VAE on SM data, we want to explore the distinguishability of
our signal models after being compressed and reconstructed. To do this we
trained a PFN classifier on the $H_{\textrm{T}}$-normalized VAE
reconstructions of the two signal categories. The details of this architecture
and training parameters are described in the Appendix.

In Fig. 3, we see the AUC for classification between reconstructed signal
events as a function of $\beta$. For $\beta>1.$ the VAE reconstruction is
uninformative for signal classification, but it contains increasingly useful
information for classification for $10^{-2}<\beta<1$, before a plateau is
reached for $\beta<10^{-2}$. This corresponds with the features in Fig. 2
right, which shows a plateau in the effective number of degrees of freedom of
the learnt representation below $10^{-2}$. These features could be combined
with the dimuon resonance information (which alone provides an AUC of 0.71),
and the overall $H_{\textrm{T}}$ of the events (which alone provides an AUC of
0.84) to further improve separation between the signals.

##  5 Conclusions and Outlook

Particle and nuclear physics experiments produce data at such volumes that
analysis is impossible without some kind of sacrifice. The traditional
approach is to keep full records of a small subset of the data, while newer
strategies store partial information about a larger fraction. In some cases,
however, neither strategy is sufficient to discover and characterize the
physics behind evidence of a new kind of particle or interaction. We propose
an alternative approach to address this limitation by automatically
compressing the full experimental information, relying on an optimal-
transport-based Variational Autoencoder with a parameter $\beta$ that controls
the bandwidth. In a benchmark test, we are able to distinguish between new
physics scenarios at a level significantly beyond what is available from the
partial event system. We expect in the coming run of the Large Hadron
Collider, such a system may be able to help discover and diagnose new physics.

## Acknowledgments and Disclosure of Funding

We thank Jesse Thaler for suggesting the parameterized loss function as an
alternative to annealing. DW/EH, BN/SK, JC were supported by the U.S.
Department of Energy, Office of Science under grant DE-SC0009920 and contracts
DE-AC02-05CH11231 and DE-AC02-76SF00515, respectively. Part of this work was
performed at the Aspen Center for Physics, which is supported by National
Science Foundation grant PHY-1607611. This research made use of the Matplotlib
Hunter:2007, Jupyter Kluyver2016jupyter, NumPy harris2020array, and SciPy
2020SciPy-NMeth software packages.

## Appendix

### Simulation details

Our first signal benchmark is that of single, real scalar field ($S$) which
mixes with the SM Higgs boson. As as result of this mixing, there exist a
penguin diagram which induces an exotic decay mode of $B$-mesons to $S$ plus a
strangeness-carrying final state Willey:1982ti; CHIVUKULA198886;
Grinstein:1988yu. Despite the loop-suppression of this partial width, the
branching ratio may nevertheless be appreciable due to the very small total
width of the $B$-meson. The branching ratio for $S\to 2\mu$ is rather
uncertain, but is thought to be between 10% and 1% for most of the mass range
where $2m_{\mu}<m_{S}<m_{B}-m_{K}$ Winkler:2018qyg. Phenomenologically, the
main signature of the model is a low mass (displaced) dimuon resonance, which
often sits inside a b-jet. For the purpose of our study, we set $m_{S}=0.4$
GeV and work with a leading order inclusive unweighted $b$-$\bar{b}$ sample
subject to $p_{\textrm{T}}>10$ GeV at the parton-level.

Our second signal benchmark is a hidden valley model Strassler:2006im, in
which the SM Higgs decays to a dark sector with some confining dynamics. This
includes a parton shower in the dark sector, followed by a hadronization into
dark mesons. Some of these dark mesons are taken to be stable and therefore
invisible, while others can decay to a pair of dark photons through a dark
sector chiral anomaly. These dark photons may subsequently decay to SM final
states, among which dimuons. (See Knapen:2021eip for a detailed description
and definition of the model.) We take the dark photon mass to be 0.4 GeV, to
match the dimuon invariant mass chosen for our first benchmark. The signature
of this model is a low mass dimuon resonance, surrounded by hadronic activity
plus a small amount of missing energy. The kinematics of the muon pair is very
similar in both models, but the pattern of hadronic activity and missing
energy in the event can differ substantially.

While analysis in CMS:2019buh is able to record hadronic activity in a coarse-
grained manner, by recording anti-$k_{\textrm{T}}$ jets Cacciari:2008gp, our
approach is able to retain more fine-grained substructure information, which
may ultimately be needed to distinguish similarly looking signatures.

### VAE architecture and training details

In our experiments, the encoder network consists of four 1D convolution layers
with filter size 1024, kernel size 1, and stride 1, followed by a sum layer,
followed by four dense layers of size 1024. $\beta$ is also provided as an
input to these dense layers, in parallel with the sum layer. Unless otherwise
specified, all layers have activation function Leaky ReLU with negative slope
coefficient of 0.1. 256 latent space $\mu,\log\sigma^{2}$ are encoded with
linear activation. Sampled codes $z$ are used as input for a decoder,
alongside $\beta$. The decoder consists of five layers with size 1024,
followed by a linear dense layer which outputs fifty particles represented as
$\\{(p_{\textrm{T}}/H_{\textrm{T}},\eta,\sin\phi,\cos\phi)\\}$, and then an
$\arctan$ function reduces this to
$\\{(p_{\textrm{T}}/H_{\textrm{T}},\eta,\phi)\\}$. The explicit $\arctan$
allows the network to avoid learning a discontinuity in $\phi$, which is also
the motivation for the trigonometric form of the inputs.

In order to reduce the number of particles to less than 50 for computational
speed, events that have more than 50 particles are reclustered using the
exclusive-$k_{T}$ algorithm Catani:1993hr with radius parameter $R=1.0$ and
terminating when there are exactly 50 particles left in the event. The VAE
works with $p_{\textrm{T}}$-normalized inputs, and so the $p_{\textrm{T}}$ for
each event is rescaled by $H_{\textrm{T}}=\sum_{i}p_{T,i}$ before being input
into the encoder. This $H_{\textrm{T}}$ is recorded separately for each event,
and can be used to rescale the event reconstructions.

We trained the VAE on the $b\bar{b}$ background events. Each batch of training
data consists of an array of shape $(n_{\text{batch}},50,4)$, with
$n_{\text{batch}}=100$, which is input to the VAE encoder, and an array of
shape $(n_{\text{batch}})$ samples for $\beta$, which is an auxiliary input to
the encoder and decoder. These samples are drawn from a log-uniform
distribution in the range $\log_{10}\beta\in[-6,1]$. The loss for each
training example is also calculated using this $\beta$. Training is performed
using the Adam optimizer kingma2014adam with learning rate initialized at
$3\times 10^{-5}$. Each epoch consists of 1000 batches (as opposed to the
entire training dataset), and the learning rate is decreased in factors of
$\sqrt{10}$ each time the validation loss has not improved in 10 epochs.
Training is stopped after validation loss has not improved in 20 epochs. This
entire cycle is repeated 10 times.

The code for this paper can be found at
https://github.com/erichuangyf/EMD_VAE/tree/neurips_ml4ps.

### Classifier architecture and training details

The PFN model used to classify reconstructed signals consists of three time-
distributed dense layers of size 128 followed by a sum layer followed by three
dense layers of size 128. Each PFN was trained on events with shape
$(n_{\text{batch}},50,3)$, with the batch size $n_{\text{batch}}=1000$.
Training is performed using the Adam optimizer with learning rate initialized
at $10^{-3}$. The learning rate is decreased in factors of $10^{1/4}$ each
time the validation loss has not improved in 5 epochs. Training is stopped
after 200 epochs or the validation loss has not improved in 10 epochs.

We also trained the PFN classifier on the hardest two muons taken from the two
signal event samples. The training procedure is similar to the PFN on full
signal events, except the input shape for each event was truncated to
$(n_{\text{batch}},2,3)$, with the batch size $n_{\text{batch}}=1000$. The
muon-only PFN model consists of three time-distributed dense layers of size
128 followed by a sum layer followed by three dense layers of size 128.
Training is performed using the Adam optimizer with learning rate initialized
at $10^{-3}$. The learning rate is decreased in factors of $10^{1/4}$ each
time the validation loss has not improved in 5 epochs. Training is stopped
after 200 epochs or the validation loss has not improved in 10 epochs.

All training was performed on NVidia Quadro RTX 6000 with CUDA version 11.2
using TensorFlow version 2.4.1. The training time for the VAE model was about
24 hours and the training time for each PFN model was about 5 minutes based on
this setup.

## Potential Broader Impacts

Compression is used throughout science and industry and so our observations
may be useful to setups beyond collider physics.

## Checklist

The checklist follows the references. Please read the checklist guidelines
carefully for information on how to answer these questions. For each question,
change the default [TODO] to [Yes] , [No] , or [N/A] . You are strongly
encouraged to include a justification to your answer, either by referencing
the appropriate section of your paper or providing a brief inline description.
For example:

  * •

Did you include the license to the code and datasets? [Yes] See Section VAE
architecture and training details.

  * •

Did you include the license to the code and datasets? [N/A] The code and the
data are proprietary.

  * •

Did you include the license to the code and datasets? [N/A]

Please do not modify the questions and only use the provided macros for your
answers. Note that the Checklist section does not count towards the page
limit. In your paper, please delete this instructions block and only keep the
Checklist section heading above along with the questions/answers below.

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [Yes]

    3. (c)

Did you discuss any potential negative societal impacts of your work? [Yes]

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [Yes]

    2. (b)

Did you include complete proofs of all theoretical results? [N/A]

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [Yes]

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [Yes]

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [N/A]

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [N/A]

    2. (b)

Did you mention the license of the assets? [N/A]

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [N/A]

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A]

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [N/A]

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]