# An Adaptive Event-based Data Converter for Always-on Biomedical Applications
at the Edge

Mohammadali Sharifshazileh 1 2, Giacomo Indiveri1 2 1Institute of
Neuroinformatics, University of Zurich and ETH Zurich;  2Zentrum für
Neurowissenschaften Zürich.

###### Abstract

Typical bio-signal processing front-ends are designed to maximize the quality
of the recorded data, to allow faithful reproduction of the signal for
monitoring and off-line processing. This leads to designs that have relatively
large area and power consumption figures. However, wearable devices for
always-on biomedical applications do not necessarily require to reproduce
highly accurate recordings of bio-signals, provided their end-to-end
classification or anomaly detection performance is not compromised. Within
this context, we propose an adaptive Asynchronous Delta Modulator (ADM)
circuit designed to encode signals with an event-based representation
optimally suited for low-power on-line spiking neural network processors. The
novel aspect of this work is the adaptive thresholding feature of the ADM,
which allows the circuit to modulate and minimize the rate of events produced
with the amplitude and noise characteristics of the signal. We describe the
circuit’s basic mode of operation, we validate it with experimental results,
and characterize the new circuits that endow it with its adaptive thresholding
properties.

###### Index Terms:

Bio-signal, Asynchronous Delta Modulator, Spiking Neural Network, Neuromorphic

##  I Introduction

Electrophysiological recordings are the basis for a large number of diagnostic
tools in medicine [1]. Most common are recordings of cardiac function, muscle
function, nerve transmission, and brain function. To achieve high reliability
in off-line data analysis, or to provide medical experts with accurate bio-
signal recordings, classical bio-medical devices are designed to produce very
high signal quality recordings. This is directly related to the performance of
signal acquisition and digitization, which is evaluated in terms of signal-to-
noise ratio, linearity, resolution and sampling rate. State-of-the-art
biomedical recording systems employ the most advanced integrated analog and
digital signal processing methods to address those challenges using data
compression, hardware sharing and time interleaving [2, 3, 4]. For these
systems, digital filtering and heavy post processing introduce extensive
power/bandwidth overhead that often leads to large area and high power
consumption.

However, bio-medical applications at the edge, i.e., applications that use
wearable devices for always-on monitoring and on-chip classification of bio-
signals, typically do not need such high signal-to-noise ratios in their
front-end processing stages. Rather than reproducing the recorded signal as
faithfully as possible, the goal of these devices is to operate continuously
throughout the day, and detect events of interest, such as heart beat
anomalies [5, 6] or High Frequency Oscillations, which have been identified as
relevant bio-markers of the epileptogenic zone in epilepsy patients [7, 8].
Therefore, for these use-cases, the most stringent requirements are low power
and area. A promising approach to satisfy these requirements, is to employ
Spiking Neural Networks implemented using analog/digital circuits with
dynamics that are well matched to those of the signals they are designed to
process [9, 10]. As these neuromorphic processors expect spikes as the input,
it is important to develop bio-signal acquisition front-ends that pre-process
and convert the biomedical sensory signals into streams of events. A typical
front-end of this type would comprise a Low-Noise Amplifier (LNA) [11, 12],
followed by one or more filtering stages, and then by an Asynchronous Delta
Modulator (ADM) [13] and a low-power SNN processing module [14, 15, 16].

Figure 1: ADM circuit. The analog input voltage $V_{in}$ is converted into UP
and DN pulses (spikes) for further processing by SNN circuits. The ADM spike
rate depends on the comparator thresholds $\mathtt{V_{thu}}$ and
$\mathtt{V_{thd}}$.

Several examples of applications that follow this approach have already been
demonstrated using pre-recorded data-sets with fixed parameter settings [13,
5, 6, 17, 8]. However, in real-world applications, the amplitude of the
signals being measured may change over time (e.g., if the subject sweats,
changes temperature, or if the wearable device shifts and moves), and the
parameters of the system may need to be adjusted at run-time. In this work we
focus on the ADM block, analyzing how the circuit parameters affect the
encoding of the signal, and we extend it by proposing a novel circuit that
adjusts the ADM parameters continuously, adapting to the changes in the
average background activity, while preserving the sensitivity to large
changes, or anomalies in the signal. We propose analog circuits that that
calculate on-line the best parameters and demonstrate the adaptive ADM
features on HFO signals, for which it is important to produce events only for
signals with amplitudes higher than the average background, and reduce, as
much as possible, the generation of events for the background activity [8].

##  II The Asynchronous Delta Modulator (ADM)

(a)

(b)

Figure 2: Experimental results. (a) Measured response of a LNA circuit that
receives in input a sine-wave attenuated to micro-Volt levels compatible with
real bio-signals; (b) Response of the ADM to the waveform of (a), producing
the encoded UP and DN events. The dashed line represents the signal
reconstructed in software using these events (with arbitrary units).

A circuit diagram of the ADM, originally proposed in [13], is shown in Fig. 1.
This circuit belongs to the family of delta modulation encoders first proposed
in the 1960s for communication [18] and recently adapted for event-based
communication systems [19]. It consists of an input Operational
Transconductance Amplifier (OTA) with a capacitive divider gain stage, two
comparators, and additional inverters that produce the UP or DN digital
voltages when the change in the amplified version of the input signal,
($\mathtt{E_{in}}$), either increases above the reference voltage,
$\mathtt{V_{ref}}$, by $\mathtt{V_{thu}}$ or decreases below
$\mathtt{V_{ref}}$ by $\mathtt{V_{thd}}$. When either of these digital signals
switch, additional logic (not shown) asserts an active-high Ack signal, which
in turn resets the OTA output to $\mathtt{V_{ref}}$ and resets the UP and DN
pulses, which are transmitted to further processing stages implemented using
SNN neuromorphic processors. This reset state will be held for a “refractory
period” determined by the values of the capacitor $\mathtt{C_{3}}$ and the
bias voltage $\mathtt{V_{rfr}}$. The number of the UP and DN pulses depends
both on the features of the input signal (amplitude and frequency) and on the
ADM parameters: the comparator thresholds and the refractory period.

The maximum rate of pulses is hard-limited by the circuit’s refractory period.
If we consider a sine-wave as the input signal, then the impact of signal
related parameters and the circuit parameters on the rate of spikes generated
by the ADM can be expressed as:

$R_{s}\propto\frac{A\cdot f}{T_{rfr}\cdot V_{th}}$ (1)

where $R_{s}$ represents the ADM spike rate for a sine wave of amplitude
$\mathtt{A}$ and frequency $\mathtt{f}$; the parameter $\mathtt{T_{rfr}}$
represents the refractory period, and $\mathtt{V_{th}\vcentcolon=}$
$\mathtt{V_{thu}-V_{ref}=}$ $\mathtt{V_{ref}-V_{thd}}$ is the comparator
threshold (assuming UP and DN thresholds are equal).

Figure 2 shows experimental results measured from the ADM fabricated using a
standard 180 nm Complementary Metal-Oxide-Semiconductor (CMOS) process [8].
The input signal was a sine-wave that was attenuated down to a peak-to-peak
range of 100 $\mu$V, off-chip and passed through an LNA with gain set to 38
dB. The resulting input sine for the ADM is depicted in Fig. 2a. For this
control experiment the threshold parameters for UP and DN spikes are kept
constant and symmetric. The events produced by the ADM are plotted in Fig. 2b.

Accumulative addition/subtraction of the $\mathtt{V_{th}}$ value at the
respective UP and DN spike times would result in a reconstruction of the input
from the output spikes (e.g., see dashed line in Fig. 2b). The reconstructed
trace drifts away from the baseline due to the asynchronous and open-loop
nature of delta-encoding, so to remove this drift effect, a high-pass filter
is often applied to the staircase reconstructed signal.

The accuracy of the data conversion can be quantified by calculating the Root
Mean Squared-Error (RMSE) between the original signal and the reconstructed
one. Figure 3 shows the effect of the two circuit parameters (refractory
period and comparator threshold) on the reconstruction and the corresponding
RMSE. This analysis also shows that ADM hyperparameters, $\mathtt{V_{th}}$ and
$\mathtt{T_{rfr}}$, can be tuned to minimize the RMSE. The fact that RMSE has
a non-zero minimum is due to the bounded spiking rate of the ADM, limited by
the refractory period.

Figure 3: Root-mean-square of the ADM spikes reconstruction error Vs. $V_{th}$
for various values of $t_{ref}$

##  III Adaptive ADM

To ensure autonomous long-time operation of bio-signal processing devices in
real-world embedded applications, the ADMs should include variable gain and an
automatic threshold adjusting mechanisms to compensate for changes that might
occur in the signal (e.g., due to electrode movement or changing conditions of
the subject). To this end, we have improved the ADM in Fig.1 in two
directions. First, we implemented a variable capacitor (2-bit switch, four
capacitance values) in the feedback of the ADM amplifier ($\mathtt{C_{2}}$ in
Fig. 1) to add an extra degree of freedom on the gain of the front-end. This
can help improving the dynamic range of bio-signal acquisition system, for
capturing information in both high amplitude low-frequency signals and low-
amplitude high-frequency ones. The second and more important improvement comes
in the form of the adaptive threshold detection module we present in Fig. 4.

The block diagram of this circuit is depicted in Fig. 4a. It operates by
tracking the envelope of the signal through a source follower integrator (Fig.
4b); the envelope is then fed into two Low Pass Filters implemented using
current-mode Differential Pair Integrator (DPI) circuits [20] (see Fig.4c),
which are then used to produce a digital voltage to enable and disable a
track-and-hold, depending on the changes in amplitude of the original signal.

(a)

(b)

(c)

(d)

Figure 4: Adaptive ADM threshold-detection. (a) block diagram of the non-
linear adaptive scheme adopted; (b) source follower integrator used to produce
the signal representing the envelope of the input; (c) DPI low-pass filter
circuit with tunable cut-off frequency and controllable “hold” switch. The DPI
1 and DPI 2 blocks do not have this gating switch, while the DPI 3 block has
it, controlled by the $\mathtt{V_{sw}}$ voltage; (d) WTA circuit used to
compare the output currents of DPI 1 and DPI 2 and produces an active high
pulse when $\mathtt{I_{out1}<I_{out2}}$. This pulse gets extended to produce
$\mathtt{V_{SW}}$.

For sufficiently larger input signals, it has been shown that the output
current of the DPI circuit can be described with the following equation [9]
similar to a first-order low-pass filter:

$\tau\frac{\mathrm{d}I_{out}}{\mathrm{d}t}+I_{out}=I_{in}$ (2)

where $\mathtt{\tau=\frac{CU_{T}}{\kappa I_{\tau}}}$

The DPI1 and DPI2 filters are configured with different time constant ($\tau$)
parameters, such that their output currents $\mathtt{I_{out1}}$ and
$\mathtt{I_{out2}}$ exhibit different step-response rise-times. This
differentiating behavior in the presence of high-amplitude-frequency activity,
alongside with properly adjusted DC component of these currents, results in
output traces that cross each other when sudden changes in the envelope of the
input signal occur.

To compare the traces $\mathtt{I_{out1}}$ and $\mathtt{I_{out2}}$ and detect
when they cross over we used a current-mode Winner-Take-All (WTA) circuit,
shown in Fig.4d [21]. When the cross-over occurs the WTA generates a pulse,
which, for stability reasons, is extended using a pulse extender (PEX) circuit
of the type presented in [14]. This extended pulse is used to open the switch
of DPI 3 and keep the circuit in hold-mode. In this way the DPI 3 capacitor
only stores the values of the envelope computed on the average background
activity of the signal, and ignores the large changes in the signal. The
result of this chain of operations is the setting of the ADM spiking threshold
parameter, $\mathtt{V_{th}}$, to a value proportional to the average
background activity of the bio-signal for small fluctuations, and holding this
value for periods of the signal that exhibit large fluctuations. This leads to
an ADM setting that produces a large number of spikes to faithfully encode
signals of interests, and zero or few spikes in response to the noisy
background activity.

Circuit simulation results of the proposed adaptive threshold detection
circuit are shown in Fig. 5. The input is a snippet of an Intracranial EEG
(iEEG) signal recorded with 2 KHz sampling rate that is filtered in the 80-250
Hz frequency band [22]. This signal contains HFOs, characterized by high
fluctuations from the average background activity. The envelope of this
signal, extracted by the source follower, is very stable during background
activity and increases in response to the high-amplitude changes (see the
orange trace in the top plot of Fig. 5). The output currents of the DPIs 1 and
2 in response to the envelope signal are depicted in the second row of Fig. 5.
Note that the output current of DPI 2 is always smaller than the DPI 1 output
current, when the envelope is constant. However as the envelope increases
rapidly, the DPI 2 filter follows it more quickly than the DPI 1 filter, and
its output current crosses the DPI 1 output current. This cross-over is
detected by a WTA circuit that continuously compares the two currents and
produces a digital voltage pulse when the cross-over occurs. This output pulse
however is typically shorter than the full length of the event (it stays high
only while $\mathtt{I_{out2}>I_{out1}}$). So to ensure a stable
$\mathtt{V_{th}}$, the pulse is extended to cover the full time-window of
typical high-amplitude events, which depends on the nature of the bio-signal,
the time-constant of the envelope detector circuit, and time-constant of the
DPI 3 filter. The result is a smooth and stable spiking threshold produced by
the DPI 3 circuit (see dashed green line in the top row of Fig. 5). The bottom
row of Fig. 5 shows how the output spikes generated by the ADM only encode the
relevant events and ignore the background activity, thanks to the adaptive
thresholding module.

Figure 5: Adaptive ADM simulation results. The top row shows a trace of pre-
recorded iEEG, it’s envelope, and the $V_{th}$ parameter automatically
detected. The middle row shows the output of the two DPI filters used to
detect outlier regions which do not belong to the average background activity.
The dashed represents the digital voltage that gates the updates to the
$V_{th}$ signal in these regions. The bottom row shows the UP and DN spikes
generated by the ADM circuit with the $V_{th}$ computed in this way. Note how
the average background regions do not produce events. The inset in the plot
shows the spikes produced for the first falling-rising-falling phases of the
high-frequency oscillation.

##  IV Discussion

The major bottleneck holding back analog front-ends from being used with SNN
devices in low-power bio-signal processing edge applications is the data
conversion block. Optimizing the performance of conventional data converters
is often performed by changing the design towards minimizing quantization
error. Indeed, knowing the characteristics of the input signal, one could
optimize the hyperparameters of the ADM to minimize the reconstruction error
as shown in Fig.3. However, as the goal of the SNN processing pipeline is to
classify or recognize features of interest in the input, rather than
reconstructing the original signal faithfully, it is important to optimize
resource usage (including area and power budget of the front-end) considering
the end-to-end performance of the full system. Mixed-signal SNNs heavily rely
on analog front-ends that provide input spikes that encode frequency- and
amplitude-specific information present in analog input signal. While most
clinically relevant bio-signals tend to have sparse high-amplitude events,
some such as Local Field Potentials are slow and gradual. So adding
flexibility and adaptability to the analog front-ends is of critical
importance.

##  V Conclusions

In this article, we discussed about the benefits of using ADM circuits in bio-
signal acquisition front-ends. We demonstrated with experimental data their
characteristics, and proposed a set of circuits for improving their
performance, by endowing them with non-linear filtering properties that would
allow them to change their parameters on-line, adapting to changes in their
operating conditions or changes in the input signals. We provided circuit
simulation results, and validated them using clinically relevant bio-signals
that contain long traces of average background activity, for which it is
desirable to produce sparse spiking activity, if any, and short high frequency
and high amplitude pulses, for which it is important to have ADM parameters
that can encode the signal with high accuracy. Future developments will
include integrating these circuits on a new design and testing them on
Electroencephalography (EEG), Electrocardiogram (ECG), and electromygraphy
(EMG) signals.

## References

  * [1] L. Peeples, “Core concept: The rise of bioelectric medicine sparks interest among researchers, patients, and industry,” _Proceedings of the National Academy of Sciences_ , vol. 116, no. 49, pp. 24 379–24 382, 2019. [Online]. Available: https://www.pnas.org/content/116/49/24379
  * [2] M. Chae, W. Liu, Z. Yang, T. Chen, J. Kim, M. Sivaprakasam, and M. Yuce, “A 128-channel 6mw wireless neural recording ic with on-the-fly spike sorting and uwb tansmitter,” in _Solid-State Circuits Conference Digest of Technical Papers (ISSCC), 2008 IEEE International_ , Feb. 2008, pp. 143–603.
  * [3] H. Hosseiniejad, A. Jannesari, and A. Sodagar, “Data compression in brain-machine/computer interfaces based on the walsh-hadamard transform,” _IEEE transactions on biomedical circuits and systems_ , vol. 8, no. 1, pp. 129–137, 2014.
  * [4] A. Sodagar, K. Wise, and K. Najafi, “A fully integrated mixed-signal neural processor for implantable multichannel cortical recording,” _IEEE Transactions on Biomedical Engineering_ , vol. 54, no. 6, pp. 1075–1088, 2007\.
  * [5] F. Bauer, D. Muir, and G. Indiveri, “Real-time ultra-low power ECG anomaly detection using an event-driven neuromorphic processor,” _Biomedical Circuits and Systems, IEEE Transactions on_ , vol. 13, no. 6, pp. 1575–1582, Dec. 2019.
  * [6] F. Corradi, S. Pande, J. Stuijt, N. Qiao, S. Schaafsma, G. Indiveri, and F. Catthoor, “ECG-based heartbeat classification in neuromorphic hardware,” in _International Joint Conference on Neural Networks (IJCNN)_. IEEE, 2019, pp. 1–8.
  * [7] T. Fedele, S. Burnos, E. Boran, N. Krayenbühl, P. Hilfiker, T. Grunwald, and J. Sarnthein, “High frequency oscillations detected in the intracranial EEG of epilepsy patients during interictal sleep, patients’ electrode location and outcome of epilepsy surgery,” _Collaborative Research in Computational Neuroscience_ , 2017.
  * [8] M. Sharifshazileh, K. Burelo, J. Sarnthein, and G. Indiveri, “An electronic neuromorphic system for real-time detection of high frequency oscillations (HFOs) in intracranial EEG,” _Nature Communications_ , vol. 12, no. 1, pp. 1–14, 2021.
  * [9] E. Chicca, F. Stefanini, C. Bartolozzi, and G. Indiveri, “Neuromorphic electronic circuits for building autonomous cognitive systems,” _Proceedings of the IEEE_ , vol. 102, no. 9, pp. 1367–1388, Sep. 2014.
  * [10] G. Indiveri and Y. Sandamirskaya, “The importance of space and time for signal processing in neuromorphic agents,” _IEEE Signal Processing Magazine_ , vol. 36, no. 6, pp. 16–28, 2019.
  * [11] G. Atzeni, J. Guichemerre, A. Novello, and T. Jang, “A 1.01 NEF low-noise amplifier using complementary parametric amplification,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 69, no. 3, pp. 1065–1076, 2022.
  * [12] L. Liu, D. Gao, Y. Tian, Y. Yu, and Z. Qin, “A low mismatch and high input impedance multi-channel time-division multiplexing analog front end for bio-sensors,” _IEEE Sensors Journal_ , vol. 22, no. 7, pp. 6755–6763, 2022\.
  * [13] F. Corradi and G. Indiveri, “A neuromorphic event-based neural recording system for smart brain-machine-interfaces,” _Biomedical Circuits and Systems, IEEE Transactions on_ , vol. 9, no. 5, pp. 699–709, 2015.
  * [14] S. Moradi, N. Qiao, F. Stefanini, and G. Indiveri, “A scalable multicore architecture with heterogeneous memory structures for dynamic neuromorphic asynchronous processors (DYNAPs),” _Biomedical Circuits and Systems, IEEE Transactions on_ , vol. 12, no. 1, pp. 106–122, Feb. 2018.
  * [15] C. Frenkel and G. Indiveri, “ReckOn: A 28 nm sub-mm2 task-agnostic spiking recurrent neural network processor enabling on-chip learning over second-long timescales,” in _2022 IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC)_. IEEE, 2022, pp. 468–470.
  * [16] C. Frenkel, M. Lefebvre, J.-D. Legat, and D. Bol, “A 0.086-mm2 12.7-pj/SOP 64k-synapse 256-neuron online-learning digital spiking neuromorphic processor in 28-nm CMOS,” _IEEE Transactions on Biomedical Circuits and Systems_ , vol. 13, no. 1, pp. 145–158, 2019.
  * [17] Y. Ma, B. Chen, P. Ren, N. Zheng, G. Indiveri, and E. Donati, “EMG-based gestures classification using a mixed-signal neuromorphic processing system,” _IEEE Journal on Emerging and Selected Topics in Circuits and Systems_ , vol. 10, no. 4, pp. 578–587, 2020.
  * [18] R. Steele, _Delta modulation systems_. Pentech Press & Halsted Press, 1975.
  * [19] M. Yang, S.-C. Liu, and T. Delbruck, “Comparison of spike encoding schemes in asynchronous vision sensors: Modeling and design,” in _IEEE International Symposium on Circuits and Systems (ISCAS)_. IEEE, 2014, pp. 2632–2635.
  * [20] C. Bartolozzi, S. Mitra, and G. Indiveri, “An ultra low power current–mode filter for neuromorphic systems and biomedical signal processing,” in _Biomedical Circuits and Systems Conference, (BioCAS), 2006_. IEEE, 2006, pp. 130–133.
  * [21] J. Lazzaro, S. Ryckebusch, M. Mahowald, and C. Mead, “Winner-take-all networks of ${o}(n)$ complexity,” in _Advances in neural information processing systems (NIPS)_ , D. Touretzky, Ed., vol. 2. San Mateo - CA: Morgan Kaufmann, 1989, pp. 703–711.
  * [22] T. Fedele, S. Burnos, E. Boran, N. Krayenbühl, P. Hilfiker, T. Grunwald, and J. Sarnthein, “Resection of high frequency oscillations predicts seizure outcome in the individual patient,” _Scientific Reports_ , vol. 7, p. 13836, Oct. 2017.

  *[LNA]: Low-Noise Amplifier
  *[ADM]: Asynchronous Delta Modulator
  *[SNN]: Spiking Neural Network
  *[HFO]: High Frequency Oscillation
  *[OTA]: Operational Transconductance Amplifier
  *[CMOS]: Complementary Metal-Oxide-Semiconductor
  *[RMSE]: Root Mean Squared-Error
  *[ADMs]: Asynchronous Delta Modulator
  *[DPI]: Differential Pair Integrator
  *[WTA]: Winner-Take-All
  *[iEEG]: Intracranial EEG
  *[HFOs]: High Frequency Oscillation
  *[DPIs]: Differential Pair Integrator
  *[SNNs]: Spiking Neural Network
  *[EEG]: Electroencephalography
  *[ECG]: Electrocardiogram
  *[EMG]: electromygraphy


# Image Segmentation with Topological Priors

Shakir Showkat Sofi  CDISE,
Skolkovo Institute of Science and Technology
Moscow, Russia
<EMAIL_ADDRESS>Nadezhda Alsahanova  CDISE,
Skolkovo Institute of Science and Technology
Moscow, Russia
<EMAIL_ADDRESS>
###### Abstract

Solving segmentation tasks with topological priors proved to make fewer errors
in fine-scale structures. In this work, we use topological priors both before
and during the deep neural network training procedure. We compared the results
of the two approaches with simple segmentation on various accuracy metrics and
the Betti number error, which is directly related to topological correctness,
and discovered that incorporating topological information into the classical
UNet model performed significantly better. We conducted experiments on the
ISBI EM segmentation dataset.

###### Index Terms:

Segmentation, Topological loss, Persistent homology, UNet.

##  I Introduction

The important task in computer vision is to know the location and shape of
objects in the image or in general, which pixel belongs to which object. This
task is accomplished through image segmentation, which involves assigning
labels to all input image pixels. The use of an end-to-end trained deep
network to segment images aids in achieving acceptable per-pixel accuracy.
However, in applications involving fine-scale structures, such as thin
connections in neuron membranes and vessels, satisfactory accuracy is
insufficient because it could lead to catastrophic mistakes. A segmentation
error in the thin cell membrane, for example, could result in the union of two
distinct cells. Thus, segmentation algorithms can still make mistakes on fine-
scale structures. To solve this problem, we incorporate topological prior
knowledge into the segmentation model.

In this work, we investigate two approaches to introducing topological priors.
The first is to add topological loss to cross-entropy loss, which is commonly
used in segmentation tasks. Topological loss measures a difference between
persistence diagrams for true and predicted masks. The second method is to use
topological image processing prior to training the neural network. Both
strategies improve segmentation performance without sacrificing pixel-wise
accuracy.

In section II we present a short review of existing solutions for the
implementation of topological priors in segmentation tasks. Then in section
III we present a short theoretical basis of persistence homology inIII-A,
topological loss and its differentiability is discussed in III-B and the
overview of topological input image processing is presented in III-C. Finally,
we present details of the training process and result of experiments in
section IV.

##  II Related Work

Topologically aware networks have already shown significant improvement in
results, especially for segmentation and classification problems. One such
earlier attempt was in [1], which uses topological awareness in the loss
function based on the response of selected filters from a pre-trained VGG19
network. It was successful in capturing some topological features, such as the
connectedness of small components. It constructs the topologically aware
losses, but it is a bit difficult to generalize for complex settings. The
interpretation and relevance of these captured features were even more
difficult. A similar scheme was proposed by researchers in [2], where the
output of the second network was used to define a loss function for
identifying global structural features, to enforce anatomical constraints.
Some researchers, like in [3], uses topological regularizers for
classification problems with considerations of stability of connected
components within imposed topological constraints on the shape of
classification boundary. Different ideas have been proposed so far for
capturing fine details, some based on deconvolution and upsampling, some using
Persistent Homology (PH), and some have used topological processing of inputs
for simple geometries for unsupervised tasks like in [4] before applying the
Chan-Vese, ISODATA, Edge-detections etc for segmenting the processed image.
For further see [5]; [6]; [7]; [8], etc. Most of the methods are problem-
specific. Our method is closest to one proposed in [9], which also poses
topological priors in the training phase. Apart from that, our scheme looks at
different possible stages of feeding topological priors with their
effectiveness and efficiency for supervised learning task.

##  III Theory

We know from recent years that the volume of data is increasing exponentially,
but it is also complex, noisy, multidimensional, and sometimes incomplete,
necessitating the development of efficient and robust data analysis methods.
The existing methods, which are based on statistics, machine learning,
uncertainty quantification, and so on, work well, but when it comes to making
sense of vast, multidimensional, and noisy data, the analysis process becomes
more challenging. However, developments in modern mathematics have yielded a
wealth of insights into the study and application of data in an entirely new
set of directions. Topological Data Analysis (TDA) is one such technique that
combines computational geometry, algebraic topology, data analysis,
statistics, etc. TDA is more involved in the geometric side of data, like
computing topological features of data. Furthermore, the prime focus is on
Persistent Homology (PH). We provide a brief overview of PH here, but the
reader is directed to [10]; [11] for a more in-depth discussion.

###  III-A Persistent homology and Persistent diagrams

A persistent homology is an important tool of algebraic topological used in
TDA to analyze qualitative data features across multiple scales. PH is robust,
dimension and coordinate independent, and provides compact summaries of the
underlying data. To compute PH, we need two things: a simplicial complex $K$
and the filtration $\mathcal{F}$ defined on $K$. A simplicial complex is a
generalisation of a graph that includes 0-simplices (nodes), 1-simplices
(edges), 2-simplices (triangles), and so on up to $k$-simplices, where
$k\in\mathbb{N}$ denotes the dimensionality of the complex. It is formally a
space that is built from a union of these nodes, edges, triangles, and/or
higher-dimensional polytopes [11]. A simplicial complex $K$ is closed under
inclusion, which means that if $\sigma^{\prime}\subseteq\sigma\in K$ then
$\sigma^{\prime}\in K.$ A nested sequence of $K_{0}\subseteq
K_{1}\subseteq\ldots\subseteq K_{N}=K$ of subcomplexes of $K$ is then defined
as the filtration $\mathcal{F}$ on $K$, please refer to [4] for details.

Due to the grid-like structure of images, it became easy to use TDA
techniques. Considering an image $I$ of size $M\times N$, the simplicial
complex can be obtained from pixel configurations of this image. Technically,
the simplicial complex (1-dim simplicial) is defined by connecting each pixel
to 8 neighbouring pixels. After that, by filling the triangular shapes of this
complex, a 2-dimensional simplicial complex can be obtained. Assuming that
images have a uniform grid structure, we may prefer the cubical
complex111Space formed by the union of vertex, edges, squares, cubes, and so
on.

PH measures lifetimes of topological features through the birth and death of
holes across the filtration [4]. For example, if any hole persists for long
consecutive values of the varying parameter(e.g., diameter $\tau$ of data-
point), then that depicts an important object in an image, and small
persistent components are noise. For each complex $K_{i}$, we compute its
topology using Homology group $\mathcal{H}_{n}$222We don’t need all details of
computations of Homology groups, as it is already implemented in Gudhi
Library, the rank of which is $k^{th}$ Betti number ($\beta_{k}$), represents
a $k$-dimensional hole. $\beta_{0}$ is the number of connected components,
$\beta_{1}$ is the number of loops, $\beta_{2}$ is the number of hallow-
cavities, and so on [6]. In the case of image data sets, however, we only go
up to 1-dimensional holes. There is a pretty good method for visualising and
interpreting births and deaths of these holes using Persistent Diagram (PD).
PD is simply a multiset that contains a point $(b,d)$ for every hole that was
born at data point diameter $\tau=b$ and died at data point diameter $\tau=d$.
It is a plot between the birth and death of these holes for different values
of data point diameter $\tau$.

###  III-B Topological Loss and Differentiability

It has been demonstrated that training a deep neural network, typically a
TopoNet, according to the methodology proposed in [9] can achieve both per-
pixel accuracy and topological correctness. Lets likewise define $\mathbf{f},$
the likelihood map predicted by the network, and $\mathbf{g}$ the ground
truth. The overall loss function can be expressed in mathematical terms as the
weighted sum of the cross-entropy loss and the topological loss:

$\mathbf{L(f,g)=L_{BCE}(f,g)+\lambda\cdot L_{topo}(f,g)}$ (1)

A binary segmentation task is assumed. Consequently, there is a single
likelihood function $\mathbf{f}$, whose value ranges from 0 to 1.

We use information from persistent diagrams of $\mathbf{f}$ and $\mathbf{g}$,
$\mathbf{D(f),D(g)}$, to formalise topological loss, which measures the
topological similarity between the likelihood $\mathbf{f}$ and the ground
truth $\mathbf{g}$. Mathematically we can write topological loss as:

$\begin{split}\mathbf{L_{topo}(f,g)}=\sum_{(p,p^{\prime})\in\mathbf{D(f),D(g)}}&\Big{[}(\texttt{birth}(p)-\texttt{birth}(p^{\prime}))^{2}+\\\
&+(\texttt{death}(p)-\texttt{death}(p^{\prime}))^{2}\Big{]}\end{split}$ (2)

Where $p$ and $p^{\prime}$ are the points from persistence diagrams
$\mathbf{D(f),D(g)}$ sorted by their ’lifetimes’:

death($p$) - birth($p$)

So, in equation (2), this loss measures the difference between persistent
diagrams. It is dependent on the critical thresholds at which topological
changes take place, such as the birth and death times of the various dots
depicted in the diagram $\mathbf{D(f)}$ [9]. And if $\mathbf{f}$ is
differentiable, these vital thresholds are critical points where the
derivative of $\mathbf{f}$ equals zero. As a consequence of this, it is
possible to represent $\mathbf{f}$ as a piecewise-linear function that has a
gradient equal to zero on critical points. So, $\mathbf{f}$ is differentiable.
Differentiability of loss function in equation (2) follows from
differentiability of $\mathbf{f}$. So, gradient of loss function
$\mathbf{\nabla_{w}L_{topo}(f,g)}$ can be written as follows:

$\begin{split}\sum_{(p,p^{\prime})\in\mathbf{D(f),D(g)}}\Big{[}&2(\texttt{birth}(p)-\texttt{birth}(p^{\prime}))\frac{\partial\mathbf{f}(c_{b}(p))}{\partial
w}+\\\
&+2(\texttt{death}(p)-\texttt{death}(p^{\prime}))\frac{\partial\mathbf{f}(c_{d}(p))}{\partial
w}\Big{]}\end{split}$ (3)

Where, for each dot $p\in\mathbf{D(f)}$ , we designate the birth and death
critical points of the related topological structure by the notation
$c_{b}(p)$ and $c_{d}(p)$, respectively [9]. Therefore, the gradient can be
straightforwardly computed based on the chain rule.

###  III-C Topological input image processing

As previously stated, topological priors can be fed into the segmentation
process at many stages, such as the input stage, the training stage, or
others. In the above section, we have seen that when we are posing topological
priors during the training phase, the process becomes sluggish and
computationally expensive. To address this issue, we use a new technique (in
UNet architecture) that processes the image using topological information
before applying the actual segmentation algorithm, removing irrelevant objects
and noise and ensuring that the modified image has well-defined topological
characteristics. The primary benefit of utilising this method is that it
enables us to perform training with a simple cross-entropy loss function, and
it also enables us to perform pre-processing on images whenever we like prior
to solving the actual segmentation problem. Therefore, it should come as no
surprise that the method is effective from a computational standpoint. In
addition to this, it is simple to apply to unsupervised segmentation problems
such as those found in [4], which would not have been achievable if we had
used priors during the training phase. The purpose of this work is to
incorporate topological image processing into supervised learning.

Figure 1: Topological input image processing for segmentation

The first type of processing of the input image is image smoothening since
this method has previously shown the advantages with persistent homology [12].
Smoothening can be used to reduce noise, remove pixel-wise focus, to improves
quality. It can be performed by spatial or frequency filters, here in our
case, we use a uniform filter from the standard scipy library, which moves the
filter mask of size, say $k\times k$, and replaces each pixel value by the
average of its neighbors, including itself. We know the real world images;
some images may or may not have borders or other irrelevant objects. So, in
general, it becomes difficult to guarantee that most persistent components are
important features in the image. The idea of border modification was proposed
in [4], in which we suppose that the objects of interest in many real-world
images do not link with borders, or, in a weaker sense, that most images have
objects of interest near the centre. The border processing, in technical
terms, constructs an image $I_{b}$ from an original image by ensuring that
each pixel within a distance $d$ of the $I_{b}$ border reaches the minimum
value, while the rest values remain fixed. From elder rule333The elder rule
asserts that when constructing a persistence diagram, if two components or
holes are merged, the youngest component or hole dies. This rule is also known
as the old survive rule[4], this assures that every object that connects to
this border will be born through it. In the PD of $I_{b}$, all irrelevant
portions correspond to a single point with infinite persistence, while
features have finite persistence.

Topological input image processing is simply processing the images using the
geometric information we have. Here, we will use these as processing steps,
but there can be plenty of such modifiers.

After the first step, which is to determine the number of components shown by
the input image, using lifetime distribution. Border modification may restrict
to finite lifetimes. We may also use any outlier detector for threshold
selections. According to the method described in [13], pertinent peaks can be
retrieved from the persistence diagram if the diagram includes a band of a
certain width that does not include any points. In this work, we apply this
method. In a more technical sense, it is the largest empty region parallel to
the diagonal. We are able to draw it into the persistence diagram by simply
iterating through lifetimes in decreasing order in order to track the
difference between consecutive lifetimes [4]. Finally, that threshold is
selected, which gives the largest difference between two lifetimes. After
selecting the threshold, we increase the contrast between the objects in the
image with a lifetime above that threshold and background. For, marking
objects in image $I$, we use the below algorithm, for details please see
[13];[4]

Conceptually, after obtaining the lifetime of components directly from the
persistent diagram, we identifying the diagram point having a significant
finite lifetime using threshold, then sorting these identified points by
decreasing death times. For all sorted point, we first identify the image
pixel that corresponds to this diagram point and store the image pixel
corresponding to the death time of this diagram point, then in ’C’ put all
pixels connected to ’b’ before its death, ensuring that ’C’ doesn’t have
overlap with previous components, finally mark the component for this diagram
point in output, and iterate for all points like-wise.

In the end, we use multi-variate interpolation to fill in the background
pixels in order to get an image with a smooth transition between the
background and the objects in the image, likewise proposed in [4], but here we
have supervised mechanism for training.

##  IV Experiments

###  IV-A Dataset

The first challenge on 2D segmentation of neuronal processes in EM images
begun in May 2012. They have provided training data consisting of 30 image
stacks. These images represent a set of consecutive slices within one 3D
volume, basically which contains a set of 30 sequential sections from a serial
section Transmission Electron Microscopy (ssTEM) data set of the Drosophila
first instar larva ventral nerve cord (VNC). They have provided the ground-
truth images as well. Below there is the sample of the image and corresponding
mask. It can be easily seen the complexity of the geometry of this dataset.
Each training image is of size $512\times 512$ in grayscale, with
corresponding ground truth. The first pre-processing was to divide the dataset
into training and evaluation sets into an 80:20 ratio. Then, we saved the
final dataset for which we did all our analysis. Choosing this dataset was a
great idea because of its complex geometry, so it was challenging to use the
topological priors in this data.

(a)

(b)

Figure 2: Image and corresponding Mask

###  IV-B Evaluation metrics

As the segmentation task is already well developed in deep learning
literature, it gave us much room for using already proposed metrics as well;
we use a variety of evaluating metrics in our research expository, some of
them follows from [14], where they were used for a similar problem. In
addition, average accuracy, correctness, quality, dice, many more, we have
used the topological relevant metric, i.e., Betti number error, which is
directly comparing the topology of prediction and ground-truth. Below we can
see the basic definitions,

  * •

Accuracy: This is the most used metric for binary segmentation problems, which
simply tells us the percentage of correctly classified pixels.

$Accuracy=\frac{TP+TN}{TP+TN+FP+FN},\in[0;1]$

  * •

Sørensen-Dice Coefficient: This metric is the statistical assessment for
similarity of two given samples.

$Dice=\frac{2TP}{2TP+FP+FN},\in[0;1]$

  * •

Completeness/lnclusion score/Recall: Assessing how well the predicted
encompasses the ground-truth.

$Completeness=\frac{TP}{TP+FN},\in[0;1]$

  * •

Correctness/Precision:  The correctness represents the percentage of correctly
extracted pixels

$Correctness=\frac{TP}{TP+FP},\in[0;1]$

  * •

Quality : Quality combines completeness and correctness into a single measure,
so it is more general and is defined as:

$Quality=\frac{TP}{TP+FP+FN},\in[0;1]$

All the above metrics have optimal value 1

  * •

Betti number-Error: This metric is more important in our case as our main
focus is about topological segmentation, the betti-number error is more
topology-relevant. In this, we randomly sample the small patches of ground-
truth and prediction, then compute the average absolute difference of their
betti-numbers $\beta_{k}$ (give us a measure of the number of handles, closed
loops etc in that patch), this reveals how much the geometry of prediction is
different from ground-truth. The smaller the betti-number error, the better is
segmentation, ideal value is zero, which means the prediction map has exactly
the same topology as that of ground-truth, sometimes called topologically
correct.

###  IV-C Details of training procedure

Many deep neural networks are used for the segmentation problem. However, for
the task of biomedical segmentation, the best results are shown by U-Net
(Fig.3).

Figure 3: Architecture of U-Net

We trained U-Net on augmented small patches from images ($64\times 64$) as
computing topological priors on small patches is faster. Augmentation was used
because we have a small dataset, and random choice of patches and their random
flipping helps to enlarge the dataset for training. Because of computational
complexity, we also take batch size equal to 1. On such a small batch size
U-Net with and without topological priors gave better results.

For the realization of topological loss, we used LevelSetLayer2D function from
TopologyLayer 444TopologyLayer is a library where by using of PyTorch library
and C++ the differentiable persistence diagram was implemented., which
calculate persistence diagrams. We added topological loss to CrossEntropy loss
1 with $\lambda=\frac{1}{12000}$ to make this losses have the same order.
Also, for visualization of diagrams, we used Ripser library.

We trained U-Net with and without topological priors on 100 epochs using Adam
optimizer. Examples of changing persistence diagrams for prediction during
training with topological loss are on Fig. 4. We can see that number of points
decreased.

(a)

(b)

Figure 4: Persistence diagrams for 5 (left) and 95 (right) epochs

###  IV-D Results

After training on small patches, we plotted predictions on whole images. The
comparison of predictions of U-Net trained without any topological priors with
trained with a topological loss on Fig. 5.

Figure 5: Predictions without topological priors (middle row) and with
topoloss (bottom row)

Also, the comparison of predictions of U-Net trained without any topological
priors with trained with a topological input image processing on Fig. 6. We
can see that using topological priors make a prediction with a smaller amount
of holes in cells.

Figure 6: Predictions without topological priors (middle row) and with
topological image processing (bottom row)

Finally, we compute all metrics for various techniques and summarise the
findings in table I. From metrics, it can be seen that topological priors give
better results than classical segmentation (Simple UNet) in terms of accuracy,
quality, and correctness, as well as topological metric (Betti-error).

Metric | Simple UNet |  UNet with topological priors in training |  UNet with topological image processing
---|---|---|---
Accuracy | 0.899 | 0.910 | 0.909
Completeness | 0.975 | 0.951 | 0.971
Correctness | 0.907 | 0.938 | 0.92
Quality | 0.886 | 0.894 | 0.895
Dice | 0.939 | 0.944 | 0.945
Betti error | 1.16 | 1.02 | 1.1

TABLE I: Results for different strategies.

##  V Conclusion

We have shown that incorporating the topological priors into deep neural
networks (UNet) is a worthwhile idea, especially for problems whose solutions
are primarily dependent upon the geometry of the underlying data. We have also
shown the usefulness of posing topological information at different stages in
the architecture for supervised learning problems. The results of the
experiments themselves demonstrate the superiority of the concept that was
presented and should be able to discover a variety of applications in data
analysis and other prospective domains that are linked. Despite the fact that
our findings were encouraging, the training process is somewhat slow, which
limits its applicability to datasets that contain multiple variables. So, the
plan for the future is to improve the computational efficiency of this method
and apply it to multi-dimensional datasets like 3D segmentation tasks. This
project’s source code is also accessible
555https://github.com/ShakirSofi/TopoSeg.git

## References

  * [1] A. Mosinska, P. Marquez-Neila, M. Kozinski, and P. Fua, “Beyond the pixel-wise loss for topology-aware delineation,” 2017.
  * [2] O. Oktay, E. Ferrante, K. Kamnitsas, M. Heinrich, W. Bai, J. Caballero, S. A. Cook, A. de Marvao, T. Dawes, D. P. O’Regan, and et al., “Anatomically constrained neural networks (acnns): Application to cardiac image enhancement and segmentation,” _IEEE Transactions on Medical Imaging_ , vol. 37, no. 2, p. 384–395, Feb 2018. [Online]. Available: http://dx.doi.org/10.1109/TMI.2017.2743464
  * [3] C. Chen, X. Ni, Q. Bai, and Y. Wang, “A topological regularizer for classifiers via persistent homology,” in _Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics_ , ser. Proceedings of Machine Learning Research, K. Chaudhuri and M. Sugiyama, Eds., vol. 89. PMLR, 16–18 Apr 2019, pp. 2573–2582. [Online]. Available: https://proceedings.mlr.press/v89/chen19g.html
  * [4] N. G. Robin Vandaele and O. Gevaert, “Topological image modification for object detection and topological image processing of skin lesions,” in _Scientific Reports, nature 10:21061_ , 2020. [Online]. Available: https://doi.org/10.1038/S41598-020-77933-Y
  * [5] R. Assaf, A. Goupil, V. Vrabie, and M. Kacim, “Homology Functionality for Grayscale Image Segmentation,” in _CRIMSTIC_ , ser. Current Research in Information Technology, Mathematical Sciences, vol. 8, Melaka, Malaysia, 2016, pp. 281–286. [Online]. Available: https://hal.archives-ouvertes.fr/hal-02108426
  * [6] J. R. Clough, I. Oksuz, N. Byrne, J. A. Schnabel, and A. P. King, “Explicit topological priors for deep-learning based image segmentation using persistent homology,” 2019.
  * [7] J. Clough, N. Byrne, I. Oksuz, V. A. Zimmer, J. A. Schnabel, and A. King, “A topological loss function for deep-learning based image segmentation using persistent homology,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , pp. 1–1, 2020.
  * [8] Y.-J. Xin and Y.-H. Zhou, “Topology on image processing,” in _Proceedings of ICSIPNN ’94. International Conference on Speech, Image Processing and Neural Networks_ , 1994, pp. 764–767 vol.2.
  * [9] X. Hu, L. Fuxin, D. Samaras, and C. Chen, “Topology-preserving deep image segmentation,” 2019.
  * [10] H. Edelsbrunner and J. Harer, “Persistent homology — a survey.”
  * [11] N. Otter, M. A. Porter, U. Tillmann, P. Grindrod, and H. A. Harrington, “A roadmap for the computation of persistent homology,” _EPJ Data Science_ , vol. 6, no. 1, Aug 2017. [Online]. Available: http://dx.doi.org/10.1140/epjds/s13688-017-0109-5
  * [12] R. Assaf, A. Goupil, V. Vrabie, T. Boudier, and M. Kacim, “Persistent homology for object segmentation in multidimensional grayscale images,” _Pattern Recognition Letters_ , vol. 112, pp. 277–284, 09 2018.
  * [13] B. Rieck and H. Leitte, “Agreement analysis of quality measures for dimensionality reduction,” in _Topological Methods in Data Analysis and Visualization IV: Theory, Algorithms, and Applications_. Springer International Publishing, 2017, pp. 103–117.
  * [14] C. Heipke, H. Mayer, C. Wiedemann, and O. Jamet, “Empirical evaluation of automatically extracted road axes,” 1998.


# Who Wrote this Code? Watermarking for Code Generation

Taehyun Lee⋆,1 Seokhee Hong⋆,1 Jaewoo Ahn1 Ilgee Hong1,♯
Hwaran Lee2,3 Sangdoo Yun2,3 Jamin Shin†,2,3 Gunhee Kim†,1
1Seoul National University 2NAVER AI Lab 3NAVER Cloud
{taehyun.lee, seokhee.hong<EMAIL_ADDRESS>
<EMAIL_ADDRESS>{hwaran.lee<EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

Large language models for code have recently shown remarkable performance in
generating executable code. However, this rapid advancement has been
accompanied by many legal and ethical concerns, such as code licensing issues,
code plagiarism, and malware generation, making watermarking machine-generated
code a very timely problem. Despite such imminent needs, we discover that
existing watermarking and machine-generated text detection methods for LLMs
fail to function with code generation tasks properly. Hence, in this work, we
propose a new watermarking method, SWEET, that significantly improves upon
previous approaches when watermarking machine-generated code. Our proposed
method selectively applies watermarking to the tokens with high enough
entropy, surpassing a defined threshold. The experiments on code generation
benchmarks show that our watermarked code has superior quality compared to
code produced by the previous state-of-the-art LLM watermarking method.
Furthermore, our watermark method also outperforms DetectGPT for the task of
machine-generated code detection.

††footnotetext: $\star$ Authors equally contributed.††footnotetext: $\sharp$
Work done during Ilgee’s internship at SNU VL Lab.††footnotetext: $\dagger$
Corresponding authors. Figure 1: Illustrated comparison of two watermarking
methods, a vanilla watermarking (Kirchenbauer et al., 2023) and SWEET (ours),
applied to code generation example of HumanEval. Two failure modes of the
vanilla watermarking method are presented in (a) and (b). (a) By watermarking,
the answer was changed to False, which is incorrect. (b) Even watermarked, the
answer was not changed, which thus is not detectable. (c) SWEET resolves both
problems by not applying a watermark to a token with low entropy. Only
modifying logit of high-entropy tokens resolves (a). Excluding low-entropy
tokens, which are prone to fail in watermarking during detection resolves (b).

##  1 Introduction

Despite the highly strict syntax of programming languages, large language
models for code generation (namely, Code LLMs), such as Codex, have rapidly
advanced toward expert-like proficiency in understanding and generating
software programs (Li et al., 2023; Nijkamp et al., 2023; Zheng et al., 2023;
Chen et al., 2021). Moreover, even general-purpose LLMs like ChatGPT have
recently shown impressive performance in generating functional code (Touvron
et al., 2023; Chowdhery et al., 2022; OpenAI, 2022, 2023b). This breakthrough
in the automation of the coding process not only improves the productivity and
efficiency of software engineers but also lowers the barriers to creating
programs for non-experts (Vaithilingam et al., 2022).

However, this comes with significant legal, ethical, and security concerns,
including code licensing issues, code plagiarism, code vulnerability, and
malware generation He and Vechev (2023); Sandoval et al. (2023); Pearce et al.
(2022); Carlini et al. (2021); Mirsky et al. (2023); Hazell (2023). For
example, there is an ongoing class-action copyright lawsuit between a group of
individuals and Microsoft, Github, and OpenAI, arising from allegations of
unlawful utilization and reproduction of the source code111Code
plagiarism222Code licensing issue. Furthermore, shortly after the launch of
ChatGPT, numerous malicious actors on the dark web were observed sharing
machine-generated malware and spear phishing tutorials333Malware generation.
Therefore, the development of reliable tools for detecting machine-generated
code is a very timely matter and is of utmost importance for fairly deploying
LLMs with coding capabilities.

Despite the need for immediate treatment of the code detection problem (i.e.,
identifying whether a given code is machine-generated or not), few efforts
have been made to address it. Instead, many works still prioritize a text
detection problem (Solaiman et al., 2019; Gehrmann et al., 2019; Ippolito et
al., 2020; Mitchell et al., 2023). DetectGPT, one of the most powerful methods
of this kind, tackled the problem based on the likelihood of a given text
being sampled from the given language model using perturbations of the sample.

Recently, Kirchenbauer et al. (2023) proposed a watermark technique —which we
refer to as vanilla watermarking— that embeds watermarks into tokens when they
are generated from a language model. For a generated token at each step, the
method randomly divides the entire vocabulary into two groups (e.g., the red
groups for tokens we want to avoid and green groups for tokens we favor). The
green group tokens get an increase in the logit values by a fixed scalar
amount. This way, the model often favors generating tokens from the green
group for each timestep. In the detection stage, the method counts the number
of green group tokens and checks whether this number is statistically
significant to conclude that the model output is generated without knowledge
of the green-red rule. While the aforementioned methods have demonstrated
powerful performance in the field of text detection, their application to the
task of code detection remains unexplored.

We conduct extensive experiments on the code detection problem for those
methods and observe that they suffer from significant degradation. In
particular, we identify two failure modes of Kirchenbauer et al. (2023) that
are caused by the nature of extremely low entropy444We calculate entropy over
the probability of the next token prediction. As expressed in Kirchenbauer et
al. (2023), if a sequence has low entropy, the first few tokens strongly
determine the following tokens. Please refer to Eq. 3 for the exact equation.
in generating code. That is, it is common that the previously generated code
tokens are so familiar to the model that it generates the next token almost
deterministically. If these one-and-only “gold" tokens fall into the red
group, either (i) the quality of the model output can be severely impaired if
other tokens in the green group are sampled (see Figure 1 (a)) or (ii)
detecting machine-generated code becomes problematic if the logit values for
the gold tokens are still higher than the ones in the green group (see Figure
1 (b)).

To address these failure modes, we propose an Selective WatErmarking via
Entropy Thresholding (SWEET) for Code LLMs (and LLMs). Instead of applying the
green-red rule to every single token in the code output, we only apply the
rule to tokens with higher entropy than a given threshold. This selective
watermarking method does not apply the green-red rule to the gold tokens,
preventing them from falling into the red group; hence, the above failure
modes would not occur.

Based on our experiments with LLaMA-13B (Touvron et al., 2023) on code
completion benchmarks HumanEval (Chen et al., 2021) and MBPP (Austin et al.,
2021), we can summarize our contributions as such:

  * •

We are the first to identify and formulate the LLM-generated code watermarking
problem.

  * •

We propose a simple, yet effective method called selective watermarking which
significantly improves code execution pass rate compared to the previous
vanilla watermarking method Kirchenbauer et al. (2023).

  * •

Our method also shows superior machine-generated code detection accuracy
compared to existing baselines.

Figure 2: The watermarked source code example on a HumanEval/59 problem (Chen
et al., 2021). We sampled 200 examples with temperature=0.8 for all methods
and chose a right answer if possible. If not, an example is chosen randomly.
Right answer existed in entropy threshold=1.2, 1.8, but there were no right
answer in Kirchenbauer et al. (2023) and entropy threshold=0.6 setting.
Whitespaces are deliberately added to show the watermarking of each token in
source code. Note that fewer tokens get involved in watermarking method when
the entropy threshold increases, and z score is calculated only with those
tokens.

##  2 Related Work

#### Detecting Synthetic Text.

Several methods have been developed for the task of detecting synthetic text
(Zellers et al., 2019; OpenAI, 2023a). Ippolito et al. (2020) used fine-tuned
BERT (Devlin et al., 2019) as a classifier for detecting synthetic text. Being
a zero-shot method (Tian, 2023), other works tackled the detection problem by
analyzing the relationship between a given text and the underlying sampling
distribution of LLMs. Gehrmann et al. (2019) focused on a token-level and
proposed a set of tests which checks whether each token in a given text is
generated from the head of the model distribution by comparing its density or
rank to those of all possible tokens. Mitchell et al. (2023) introduced
DetectGPT that focuses on passage-level. The authors observed that the
machine-generated passages tend to lie at the local maximum of the log
probability of LLMs. With this observation, they argued that one can detect
synthetic passages by generating multiple perturbed versions of a given
passage and seeing whether the log probability of a given passage is higher
than that of perturbed passages. While DetectGPT outperforms other methods
using LLM’s distribution in several text completion tasks, it relies on highly
repeated access to the distribution of the language models, which causes huge
computational costs.

#### Text Watermarking.

The majority of watermarking methods for text are based on the modification of
the original text via a predefined set of rules (Atallah et al., 2001, 2002;
Kim et al., 2003; Topkara et al., 2006; Jalil and Mirza, 2009; Meral et al.,
2009) or transformer-based network (Abdelnabi and Fritz, 2021; Yang et al.,
2022; Yoo et al., 2023). However, there are only a few watermarking methods
for LLMs that embed watermarks into tokens during the sampling process of
LLMs. When the model samples each sentence, Venugopal et al. (2011) proposed
to generate a fixed number of candidates. A hash function is then applied to
each candidate and generates a bit sequence from a binomial distribution with
$p=0.5$ (i.e., the ratio of 0s and 1s is expected to be equal). The watermarks
are embedded by choosing candidates that are mapped to the bit sequences with
the highest ratio of 1s. The difference in the ratio of 1s in the whole output
is used to detect whether the output is watermarked or not. On the contrary,
Kirchenbauer et al. (2023) considers applying a hash function to the
previously generated token, and uses the hash value as a seed for a random
number generator to randomly divide candidate tokens into two groups. As the
method induces sampling only from tokens belonging to one of the two groups,
one with knowledge of this rule can detect the watermark if the output is
generated by the model. We adopt the watermarking rule from ‘soft watermark’
method in Kirchenbauer et al. (2023); however, our method differs from it in
that we do not apply the rule to every single token when it is generated from
a language model.

#### Software Watermarking.

One of the major streams of literature regarding watermarking code is software
watermarking, which embeds a unique identifier within the code to protect the
intellectual property of a software program. Based on the stage at which the
watermarks are embedded, the methods are divided into static software
watermarking (Hamilton and Danicic, 2011; Li and Liu, 2010; Myles et al.,
2005), which imprints watermarks in the codes of a software program, usually
by code replacement and code re-ordering, and dynamic software watermarking
(Dey et al., 2018; Wang et al., 2018; Ma et al., 2019), which injects
watermarks in the compiling/execution stage of a program. These existing
software watermarking methods not only differ from SWEET, but are not directly
applicable to Code LLMs that are supposed to embed watermarks into the code
during the generation process.

##  3 Method

We address problems that the previous vanilla watermarking method Kirchenbauer
et al. (2023) arises during embedding and detecting watermarks, especially in
the case of code generation. We propose a new watermarking method, SWEET, that
selectively watermarks tokens with high enough entropy.

###  3.1 Preliminaries

For a given language model $f_{\text{LM}}$ with vocabulary $\mathcal{V}$, the
likelihood probability of a token $c^{(t)}$ at $t$ following a token sequence
$(c^{-N_{p}},...,c^{(t-1)})$ is calculated as follow:

$\bm{l}^{(t)}=f_{\text{LM}}(c^{-N_{p}},\dots,c^{(t-1)}),$ (1)
$p_{i}^{(t)}=\frac{l_{i}^{(t)}}{\sum_{i=1}^{|\mathcal{V}|}l_{i}^{(t)}},$ (2)

where $(c^{-N_{p}},...,c^{-1})$ and $(c^{0},...,c^{(t-1)})$ are a
$N_{p}$-length prompt and the generated sequence, respectively, and
$\bm{l}^{(t)}\in\mathbb{R}^{|\mathcal{V}|}$ is the logit vector. The LM
generates $c^{(t)}$ based on $\bm{p}^{(t)}$ using various decoding techniques
such as top-p and top-k sampling, greedy decoding, and beam search. The
entropy of $\bm{p}^{(t)}$ is computed by

$H^{(t)}=-\sum_{i=1}^{|\mathcal{V}|}p^{(t)}_{i}\log p^{(t)}_{i}.$ (3)

#### Watermarking in LM-generated Text.

In the vanilla watermarking (Kirchenbauer et al., 2023), the entire tokens in
$\mathcal{V}$ at each time-step are randomly binned into the green
$\mathcal{G}^{(t)}$ and red groups $\mathcal{R}^{(t)}$ in proportions of
$\gamma$ and $1-\gamma$ $(\gamma\in(0,1))$, respectively. The method increases
the logits of green group tokens by adding a fixed scalar $\delta$, promoting
them to be sampled at each position. Thus, watermarked LM-generated text is
more likely than $\gamma$ to contain the green group tokens. On the other
hand, since humans have no knowledge of the hidden green-red rule, the
proportion of green group tokens in human-written text is expected to be close
to $\gamma$.

The watermarked text is detected through a one-sided $z$-test by testing the
null hypothesis where the text is not watermarked. The $z$-score is calculated
using the number of recognized green tokens in the text. Then, the testing
text is considered as watermarked if the $z$-score is greater than
$z_{\text{threshold}}$. Note that the detection algorithm with the higher
$z_{\text{threshold}}$ can result the lower false positive rate (FPR) and
reduce Type I errors.

###  3.2 Motivation

Although the vanilla watermarking has shown the possibility of detecting LLM-
generated text, we address that the algorithm might be vulnerable to text —
especially, code — that contains low entropy tokens from two perspectives: 1)
the performance of detecting the watermarked text, 2) the quality of the
generated text.

#### Low Entropy Tokens Avoid Being Watermarked.

When we consider Figure 1 (b), the top-1 token True (which is red-listed)
holds most of the probability mass. In this case, watermarking fails to
properly function becasue the red-listed True will be almost deterministically
generate, instead of the green-listed token False. Hence, in most cases, code
gets watermarked much less than plain text, making it harder to detect.

#### Watermarking causes performance degradation.

On the other hand, when we consider Figure 1 (a), which describes a case of
successfully emitting the green-listed token, False, we can see that the code
will immediately fail to execute properly. Although this case is a rather
extreme example, this is still the major reason we see significant code
performance degradation once a code is watermarked.

Algorithm 1 Generation Algorithm of SWEET

1: Input: prompt $c^{-N_{p}},\dots,c^{-1}$; entropy threshold
$H\in[0,\log|\mathcal{V}|]$, $\gamma\in(0,1)$, $\delta>0$;

2: for $t=0,1,2,\dots$ do

3: Compute a logit vector $\bm{l}^{(t)}$ by (1);

4: Compute a probability vector $\bm{p}^{(t)}$ by (2);

5: Compute an entropy $H^{(t)}$ by (3);

6: if $H^{(t)}>H$ then

7: Compute a hash of token $c^{(t-1)}$, and use it as a seed for a random
number generator;

8: Randomly divide $\mathcal{V}$ into $\mathcal{G}^{(t)}$ of size
$\gamma|\mathcal{V}|$ and $\mathcal{R}^{(t)}$ of size
$(1-\gamma)|\mathcal{V}|$;

9: Add $\delta$ to the logits of tokens in $\mathcal{G}^{(t)}$;

10: end if

11: Sample $c^{(t)}$;

12: end for

Algorithm 2 Detection Algorithm of SWEET

1: Input: testing text $s$; entropy threshold $H\in[0,\log|\mathcal{V}|]$,
$\gamma\in(0,1)$, $z_{\text{threshold}}>0$;

2: Set $\mathcal{S}=\emptyset$ and $|s|_{G}=0$;

3: Tokenize sequences in $s$ by (3.3);

4: for $t=0,1,2,\dots N_{b}-1$ do

5: Compute a logit vector $\bm{l}^{(t)}$ by (1);

6: Compute a probability vector $\bm{p}^{(t)}$ by (2);

7: Compute an entropy $H^{(t)}$ by (3);

8: if $H^{(t)}>H$ then

9: Set $\mathcal{S}\leftarrow\mathcal{S}\cup\\{c^{(t)}\\}$;

10: Compute a hash of token $c^{(t-1)}$, and use it as a seed for a random
number generator;

11: Recover $\mathcal{G}^{(t)}$ and $\mathcal{R}^{(t)}$;

12: if $c^{(t)}\in\mathcal{G}^{(t)}$ then

13: $|s|_{G}\leftarrow|s|_{G}+1$;

14: end if

15: end if

16: end for

17: Compute $z$-score by (5);

18: if $z>z_{\text{threshold}}$ then

19: return True; (i.e., $s$ is watermarked)

20: else

21: return False;

22: end if

###  3.3 Selective Watermarking with Entropy Threshold (SWEET)

As described in the above motivation subsection, blindly applying vanilla
Watermarking for Code LLMs will either cause an issue with the
imperceptibility Tao et al. (2014) (code execution performance) or detection
ability of the code. While reducing $\delta$ in vanilla watermarking also
raises imperceptibility, this will also decrease the detection ability, hence
a trade-off. SWEETcan improve this trade-off by detecting more interchangeable
tokens and replacing them with watermarks.

#### Generation.

The generation step of our method is in Algorithm 1. As stated above, we only
apply the watermarking when a token $c^{(t)}$ has higher entropy than a
threshold (i.e., $H^{(t)}>H$).

#### Detection.

We outline our detection process in Algorithm 2. Let $s$ be a given source
code. If there is some part $s_{0}$ where we know it is not generated by that
LLM (e.g., a skeleton code in a computer science assignment), $s$ can be
divided into two parts: $s=(s_{0},s_{1})$. We want to detect whether $s_{1}$
contains a watermark or not. We first apply a tokenizer to $s_{0}$ and
$s_{1}$, and obtain

$\displaystyle\text{Tokenizer}(s_{0})$
$\displaystyle=\\{c^{-N_{p}},\dots,c^{-1}\\}=:c_{0}$
$\displaystyle\text{Tokenizer}(s_{1})$
$\displaystyle=\\{c^{0},\dots,c^{N_{b}-1}\\}=:c_{1},$ (4)

where $N_{b}$ is the length of the code to be detected. We then compute a
sequence of logit vectors $\\{\bm{l}^{0},\dots,\bm{l}^{N_{b}-1}\\}$ by feeding
LLM the previous token sequence. Let $\mathcal{S}$ denote the subset of
$c_{1}$ whose elements have higher entropy $H$ than the threshold and let
$|s_{1}|_{G}$ denote a number of green tokens in $\mathcal{S}$. Finally, we
compute a $z$-score under the null hypothesis where that the text is not
watermarked by

$z=\frac{|s_{1}|_{G}-\gamma|\mathcal{S}|}{\sqrt{|\mathcal{S}|\gamma(1-\gamma)}}.$
(5)

Using prespecified $z_{\text{threshold}}$, if $z>z_{\text{threshold}}$ holds,
we decide that the watermark is embedded in $s_{1}$ and thus generated by the
LLM.

Method |  | HumanEval |  | MBPP |  |  Compute Cost
---|---|---|---|---|---|---
| pass@100 | AUROC | TPR | FPR |  | pass@80 | AUROC | TPR | FPR |
Non-watermarked |  | 52.8 | - | - | - |  | 57.7 | - | - | - |  | -
Detection | log p(x) |  | 52.8 | 0.597 | 0.104 | < 0.01 |  | 57.7 | 0.552 | 0.016 | < 0.01 |  | $N_{b}$
LogRank |  | 0.618 | 0.098 | < 0.01 |  | 0.543 | 0.018 | < 0.01 |  | $N_{b}$
DetectGPT (T5-3B) |  | 0.563 | 0.012 | < 0.01 |  | 0.531 | 0.004 | < 0.01 |  | 100$N_{b}$
DetectGPT (SantaCoder) |  | 0.498 | 0.024 | < 0.01 |  | 0.551 | 0.028 | < 0.01 |  | 100$N_{b}$
Watermark | Vanilla Watermarking |  | 36.2 | 0.921 | 0.439 | < 0.01 |  | 52.5 | 0.870 | 0.364 | < 0.01 |  | 0
SWEET(entropy=0.9) |  | 40.2 | 0.963 | 0.780 | < 0.01 |  | 53.6 | 0.916 | 0.526 | < 0.01 |  | $N_{b}$
SWEET(entropy=1.8) |  | 46.4 | 0.926 | 0.598 | < 0.01 |  | 58.0 | 0.880 | 0.442 | < 0.01 |  | $N_{b}$

Table 1: Main results. We use 3 detection-based baselines and one watermark-
based baseline. A base LLM, LLaMA-13B here, generates a source code of a
function given function description. Both groups of methods detect machine-
generated code from human-written code, but watermark-based methods, including
SWEET, detect watermark-embedded code, especially. pass@k metric is for
evaluating code generation ability, and AUROC/TPR/FPR are for machine-
generated code detection. Note that we report TPR when FPR remains under 1%.
Compute Cost represents the number of forward pass of LLM required in
detection process. $N_{b}$ is the length of the text to be detected.

##  4 Experiments

We conduct a series of experiments to evaluate our watermarking method’s
imperceptibility and detection ability when applied to the base LLM. We use
LLaMA-13B (Touvron et al., 2023) as our base LLM for all experiments. Two
datasets are used for the code generation testbeds: HumanEval Chen et al.
(2021) and MBPP Austin et al. (2021). Both tasks test whether a language model
generates a complete code of the function given a function name and an
instruction. The LLM with or without watermarking generates a code, and we aim
to discriminate it from human-written code.

###  4.1 Baselines

We compare our selective watermarking method with various machine-generated
text detection baselines categorized into detection-based and watermarking-
based methods. Detection-based methods detect synthetic text without
watermarking it. Among the four baselines to compare the machine-generated
code detection performance, three are detection-based, and one is
watermarking-based. Detection-based baselines identify the characteristics of
LLM-generated outputs to determine the source LM for the candidate text, while
watermarking-based ones detect the existence of hidden watermarks through
statistical t-tests.

  * •

logp(x): Gehrmann et al. (2019) assumes that the model-generated text has a
high average log probability regarding the source LM.

  * •

LogRank: Ippolito et al. (2020) measures the average log-rank of the tokens in
the text and classifies it as model-generated if the log-rank is small.

  * •

DetectGPT (Mitchell et al., 2023) makes use of log likelihood discrepancy
which is a drop in log probability when the candidate text is perturbed.

  * •

Vanilla Watermarking (Kirchenbauer et al., 2023) embeds hidden watermarks into
the code text by splitting the tokens into green/red lists.

Note that DetectGPT needs a mask-filling model for perturbing text, and the
authors use T5-3B (Raffel et al., 2020). To reproduce their methods, we used
T5-3B, but it showed poor code generation performance, so we also added the
results of SantaCoder (Allal et al., 2023). For the watermarking-based
baseline, we include only Kirchenbauer et al. (2023) method since it is the
recent watermarking method that can be applied to both LLM and code generation
tasks.

###  4.2 Metrics

#### Functionality of Generated Code.

To evaluate the code generation, we use pass@k Chen et al. (2021) by
generating $n$ ( > $k$) samples for each instance. By comparing pass@k scores
of watermarked code with the ones of non-watermarked code generated by base
LM, we can evaluate the imperceptibility of a watermarking method. Note that
we don’t need to evaluate the imperceptibility of detection-based baselines
since they do not watermark code; they use the original code instead.

#### Performance of Machine-Generated Code Detection.

For the detection ability, we calculate AUROC (i.e., Area Under ROC),
TPR(i.e., True Positive Rate), and FPR(i.e., False Positive Rate) to measure
performance on correctly detecting the machine-generated code. We report TPR
scores at FPR levels below 1% to minimize misclassification of human-written
code as machine-generated, which is considered undesirable (i.e., Type I
Error).

###  4.3 Hyperparameters

We mainly follow hyperparameters in LLaMA for generating source code. We
generate $n=200$ samples in HumanEval but $n=100$ in MBPP due to expensive
computational resources. We use top-$p$ (Holtzman et al., 2020) sampling with
$p$=0.95 and temperature 0.8. When T5-3B is used for DetectGPT, we follow
original hyperparameters from DetectGPT, such as 2-word spans and 15% of
masks. However, when utilizing SantaCoder, we simulate the single-line fill-
in-the-middle task scenario by masking only one line of code per perturbation,
which allows SantaCoder to perform well (Fried et al., 2023; Bavarian et al.,
2022). For watermarking methods, we fix the green list size parameter $\gamma$
to 0.25, and $\delta=2$, which is added to green list logits.

Figure 3: Plots of pass@k and detection AUROC when calibrating the entropy
threshold of our methods, SWEET, on two code generation benchmarks. We
generates 200 samples to calculate pass@k and randomly pick one of them for
AUROC. While code generation performance increases as higher entropy threshold
is applied in both tasks, detection AUROC scores make curves.

##  5 Results and Analysis

###  5.1 Main Results

#### Preserving Code Functionality.

One of the main issues we identified with vanilla Watermarking (Kirchenbauer
et al., 2023) was the significant deterioration of code functionality. In
Table 1, we show that the pass@100 of Watermark-LLM for HumanEval decreases
from 52.8 to 36.2, which is a 31.4% loss in the code execution pass rate.
Similarly, for the MBPP data, the drop in performance is less severe but still
around 9%. On the other hand, our approach – selective watermarking
(entropy=1.8) – loses only 10% in HumanEval, which is 61.5% less than that of
vanilla Watermarking.

#### Detection Performance.

Meanwhile, Table 1 also shows that overall, our selective watermarking method
significantly outperforms all baselines in terms of detecting machine-
generated code. With an entropy threshold of 0.9, our method can detect 78%
(TPR) of machine-generated code while maintaining a false positive rate (FPR)
under 1%. Notably, this is a 77% improvement in TPR compared to vanilla
Watermarking. Furthermore, DetectGPT breaks down in terms of the code
generation detection performance making the comparison meaningless. We analyze
this breakdown later in section 5.3.

#### Computational Costs.

Vanilla Watermarking Kirchenbauer et al. (2023) does not require any
additional computation during the detection process. On the other hand, our
method needs a white-box setting where the source LLM is required in order to
calculate the entropy with a single forward pass. Meanwhile, DetectGPT needs
to run forward passes as much as the number of perturbations for increased
accuracy (the original paper used 100 perturbations, so we did the same).

###  5.2 Further Analysis

#### Analyzing Impact of Entropy Thresholds.

Figure 3 presents how code generation performance and detecting ability change
when calibrating the entropy threshold in our method. As the entropy threshold
increases, the ratio of watermarked tokens decreases, so the code generation
performance converges to a non-watermarked base model. This indicates that our
method always lies between vanilla Watermarking and a non-watermarked base
model. On the other hand, the detection ability demonstrates a distinct curve:
as the entropy threshold increases, it reaches a local maximum but eventually
declines. We believe this point as a Pareto frontier, representing a trade-off
between code generation performance and detection ability.

#### Analyzing Well-Functioning Code.

Method | AUROC | TPR | FPR | n
---|---|---|---|---
logp(x) | 0.560 | 0.068 | <0.01 | 103
LogRank | 0.589 | 0.068 | <0.01 | 103
DetectGPT(T5-3B) | 0.585 | 0.068 | <0.01 | 103
DetectGPT(SantaCoder) | 0.512 | 0.019 | <0.01 | 103
vanilla Watermarking | 0.817 | 0.127 | <0.01 | 71
SWEET(entropy=0.9) | 0.883 | 0.192 | <0.01 | 78
SWEET(entropy=1.8) | 0.823 | 0.159 | <0.01 | 88

Table 2: Machine-generated code detection results of the $passed$ pairs in the
HumanEval dataset. Since each method generated different outputs, the number
of passed pairs $n$ are vary.

To see how hard to distinguish machine-generated code from human-written code
when both represent the same functionality, we measure the detection
performance only with the code pairs passing the execution test. In Table 2,
watermarking-based methods, including ours, suffer a colossal performance
drop; 71%, 75%, and 73% for vanilla watermarking and our two methods,
respectively, in terms of TPR. These results demonstrate that generating code
with a watermark embedded, which performs well as if human-written, is far
more challenging than other text generation tasks. On the one hand, detection-
based methods’ performance variations are marginal, considering the small size
of the example set.

#### Ablation Study.

Figure 4: We plot pass@10 scores of HumanEval task by generating 50 examples.
To see how much the text watermarked impact the code generation performance,
we adjust the watermarking portion. For ours, we adjust it by changing entropy
threshold. Since there is no control knob in the vanilla watermarking for
watermarking portion, we decide whether the token is generated under
watermarked setting at every time steps.

We ran an ablation study to assess the contribution regarding the use of
entropy thresholding. In Figure 2, we can clearly see that the number of
watermarked tokens (green tokens) reduces as the entropy threshold increases.
This naturally raises the question: was it actually the decrease in the
proportion of watermarked sections that mattered the most?

To address this question, we experimented with a modified version of the
vanilla watermarking algorithm by reducing the watermarked proportions from
100% (vanilla) to 0% (canonical solution - no watermark), gradually. We did so
by randomly deciding to exclude or not for watermarking each token with the
target proportion. In Figure 4, we also plot the pass@10 results of SWEET with
varying entropy thresholds (since by increasing threshold, the watermark
proportion drops).

Here, we can observe that as we decrease the watermarking proportion, the
pass@10 of vanilla watermarking follows a convex curvature with a significant
dip around 60% proportion. On the other hand, our method shows an (almost)
monotonically increasing curvature. The noticeable spike in pass@10 – for both
methods – as we increase from 20% to 0% is an obvious result as almost no
modification has been made to the canonical solution. Interestingly, for
SWEET, just before the performance starts to spike ($\sim$25%) the entropy
threshold is 0.9 which is also when it obtains the highest AUROC as shown in
Figure 3. As shown in the figure, this is also the point where the detection
AUROC starts to drop. This also has a straightforward answer because fewer
tokens to watermark means that the confidence of detection becomes weaker.
Hence, we can safely conclude that by using entropy thresholding – SWEET – we
were able to find the sweet spot of the trade-off between pass@k and detection
AUROC.

###  5.3 Case Study: Breakdown of DetectGPT

While DetectGPT has shown remarkable detection performance in plain text
generation tasks such as XSum, SQuAD or Wikipassage (Mitchell et al., 2023),
it performs worst in code generation task. We hypothesize that the detection
ability of DetectGPT is dependent on the performance of the underlying LLM. It
excels in tasks where the LLM’s performance closely resembles human-level,
while its performance is significantly lower in code generation tasks where no
LLM has achieved human-level performance. We provide evidence to support our
hypothesis in the following.

#### Plain Text vs. Code Generation.

We empirically analyze the breakdown of DetectGPT using the LLaMA-13B backbone
model by comparing performance on two different tasks: plain text generation
(i.e., XSum) and code generation tasks (i.e., HumanEval and MBPP).

From Table 3, we can first see that AUROC significantly drops in HumanEval and
MBPP. It demonstrates that DetectGPT performs significantly worse in the code
generation task. Secondly, the gap between the log-likelihood of machine-
generated and human-generated text is significantly larger than that of XSum
than the others.

Here’s how we interpret these two observations. In tasks like XSum, where the
backbone model performs well, the machine-generated text has an overall low
entropy (a sharp token distribution), resulting in a significant difference
between the two log-likelihood values (i.e., 0.346). In code generation tasks,
where the backbone model performs rather poorly, the machine-generated text
has higher entropy (a relatively more random token distribution), resulting in
a minimal difference between the two log-likelihood values (i.e., 0.093 in
HumanEval and 0.022 in MBPP). Since DetectGPT performs well when there is a
clear difference between these two log-likelihood values, the detection
performance deteriorates when the backbone model struggles. Therefore, we can
consider code generation as a challenging domain for DetectGPT unless we use
very strong Code LLMs.

Task | AUROC | Log Likelihood
---|---|---
|  | Human | Model
XSum | 0.800 |  | -1.967 (0.301)
---
| -1.621 (0.436)
---
HumanEval | 0.563 |  | -1.070 (0.246)
---
| -0.977 (0.264)
---
MBPP | 0.531 |  | -0.932 (0.138)
---
| -0.910 (0.139)
---
Table 3: AUROC and log likelihood of DetectGPT using the LLaMA-13B backbone
model on three different datasets. We wrote the log likelihood using the mean
value and included the standard deviation in parentheses. Note that we use
only original samples without perturbations to compute log likelihood.

##  6 Limitations

We mainly identify to limitations of this work and suggest ways to mitigate
them. We want to particularly note that these limitations are not “weaknesses”
of our work as they are not strictly limited to our proposed method, but
rather a limitation of the status quo of this field.

The first one is about the manual process of selecting the entropy threshold.
Changing this threshold drastically changes the code and detection performance
so it’s a very important hyperparameter that varies upon the backbone model we
use for generation and the benchmark dataset. However, according to our
observations, holding the entropy threshold around the mean entropy of the
corpus usually resulted near the pareto-optimal results between detection
accuracy and pass@k, suggesting possibilities of optimization.

Furthermore, as we mention in the discussion of the experiment results, during
detection time, we also need the source Code LLM, hence this method works only
in a completely white-box setting, just like DetectGPT. This can be a
computational burden for some users who want to apply our work.

##  7 Conclusion

In this paper, we identify and emphasize the need for Code LLM watermarking,
and formalize it for the first time. Despite the rapid advance of coding
capability of Large Language Models, the necessary measures to encourage the
safe usage of such models have not been implemented yet. Our experiments show
that existing watermarking and detection techniques fail to properly operate
under the code generation setting. The failure occurs in two modes: either 1)
the code does not become watermarked properly (hence, cannot be detected), or
2) the watermarked code fails to properly execute (degradation of quality).
Our proposed method (SWEET), on the other hand, solves both of these failure
modes to a certain extent by introducing selective entropy thresholding which
filters tokens that are least relevant to execution quality. Indeed, the
experiment results with SWEET do not fully recover the original non-
watermarked performance; however, we believe it is an important step towards
achieving this ambitious goal.

## References

  * Abdelnabi and Fritz (2021) Sahar Abdelnabi and Mario Fritz. 2021.  Adversarial watermarking transformer: Towards tracing text provenance with data hiding.  In _2021 IEEE Symposium on Security and Privacy (SP)_ , pages 121–140. IEEE, IEEE.
  * Allal et al. (2023) Loubna Ben Allal, Raymond Li, Denis Kocetkov, Chenghao Mou, Christopher Akiki, Carlos Munoz Ferrandis, Niklas Muennighoff, Mayank Mishra, Alex Gu, Manan Dey, et al. 2023.  Santacoder: don’t reach for the stars! _arXiv preprint arXiv:2301.03988_.
  * Atallah et al. (2001) Mikhail J. Atallah, Victor Raskin, Michael Crogan, Christian Hempelmann, Florian Kerschbaum, Dina Mohamed, and Sanket Naik. 2001.  Natural language watermarking: Design, analysis, and a proof-of-concept implementation.  In _Information Hiding_ , pages 185–200. Springer, Springer Berlin Heidelberg.
  * Atallah et al. (2002) Mikhail J. Atallah, Victor Raskin, Christian F. Hempelmann, Mercan Karahan, Radu Sion, Umut Topkara, and Katrina E. Triezenberg. 2002.  Natural language watermarking and tamperproofing.  In _Information Hiding_ , pages 196–212. Springer, Springer Berlin Heidelberg.
  * Austin et al. (2021) Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al. 2021.  Program synthesis with large language models.  _arXiv preprint arXiv:2108.07732_.
  * Bavarian et al. (2022) Mohammad Bavarian, Heewoo Jun, Nikolas Tezak, John Schulman, Christine McLeavey, Jerry Tworek, and Mark Chen. 2022.  Efficient training of language models to fill in the middle.  _arXiv preprint arXiv:2207.14255_.
  * Carlini et al. (2021) Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom B Brown, Dawn Song, Ulfar Erlingsson, et al. 2021.  Extracting training data from large language models. In _USENIX Security Symposium_ , volume 6.
  * Chen et al. (2021) Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. 2021.  Evaluating large language models trained on code.  _arXiv preprint arXiv:2107.03374_.
  * Chowdhery et al. (2022) Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. 2022.  Palm: Scaling language modeling with pathways.  _arXiv preprint arXiv:2204.02311_.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Dey et al. (2018) Ayan Dey, Sukriti Bhattacharya, and Nabendu Chaki. 2018.  Software watermarking: Progress and challenges.  _INAE Letters_ , 4(1):65–75.
  * Fried et al. (2023) Daniel Fried, Armen Aghajanyan, Jessy Lin, Sida Wang, Eric Wallace, Freda Shi, Ruiqi Zhong, Wen-tau Yih, Luke Zettlemoyer, and Mike Lewis. 2023.  Incoder: A generative model for code infilling and synthesis.  In _International Conference on Learning Representations_.
  * Gehrmann et al. (2019) Sebastian Gehrmann, Hendrik Strobelt, and Alexander Rush. 2019.  GLTR: Statistical detection and visualization of generated text.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics: System Demonstrations_ , pages 111–116, Florence, Italy. Association for Computational Linguistics.
  * Hamilton and Danicic (2011) James Hamilton and Sebastian Danicic. 2011.  A survey of static software watermarking.  In _2011 World Congress on Internet Security (WorldCIS-2011)_ , pages 100–107. IEEE, IEEE.
  * Hazell (2023) Julian Hazell. 2023.  Large language models can be used to effectively scale spear phishing campaigns.  _arXiv preprint arXiv:2305.06972_.
  * He and Vechev (2023) Jingxuan He and Martin Vechev. 2023.  Controlling large language models to generate secure and vulnerable code.  _arXiv preprint arXiv:2302.05319_.
  * Holtzman et al. (2020) Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. 2020.  The curious case of neural text degeneration.  In _International Conference on Learning Representations_.
  * Ippolito et al. (2020) Daphne Ippolito, Daniel Duckworth, Chris Callison-Burch, and Douglas Eck. 2020.  Automatic detection of generated text is easiest when humans are fooled.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 1808–1822, Online. Association for Computational Linguistics.
  * Jalil and Mirza (2009) Zunera Jalil and Anwar M. Mirza. 2009.  A review of digital watermarking techniques for text documents.  In _2009 International Conference on Information and Multimedia Technology_ , pages 230–234. IEEE, IEEE.
  * Kim et al. (2003) Young-Won Kim, Kyung-Ae Moon, and Il-Seok Oh. 2003.  A text watermarking algorithm based on word classification and inter-word space statistics.  In _Seventh International Conference on Document Analysis and Recognition, 2003. Proceedings._ , pages 775–779. Citeseer, IEEE Comput. Soc.
  * Kirchenbauer et al. (2023) John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. 2023.  A watermark for large language models.  _arXiv preprint arXiv:2301.10226_.
  * Li and Liu (2010) Jun Li and Quan Liu. 2010.  Design of a software watermarking algorithm based on register allocation.  In _2010 2nd International Conference on E-business and Information System Security_ , pages 1–4. IEEE, IEEE.
  * Li et al. (2023) Raymond Li, Loubna Ben Allal, Yangtian Zi, Niklas Muennighoff, Denis Kocetkov, Chenghao Mou, Marc Marone, Christopher Akiki, Jia Li, Jenny Chim, et al. 2023\.  Starcoder: may the source be with you! _arXiv preprint arXiv:2305.06161_.
  * Ma et al. (2019) Haoyu Ma, Chunfu Jia, Shijia Li, Wantong Zheng, and Dinghao Wu. 2019.  Xmark: Dynamic software watermarking using collatz conjecture.  _IEEE Transactions on Information Forensics and Security_ , 14(11):2859–2874.
  * Meral et al. (2009) Hasan Mesut Meral, Bülent Sankur, A. Sumru Özsoy, Tunga Güngör, and Emre Sevinç. 2009.  Natural language watermarking via morphosyntactic alterations.  _Computer Speech & Language_, 23(1):107–125.
  * Mirsky et al. (2023) Yisroel Mirsky, Ambra Demontis, Jaidip Kotak, Ram Shankar, Deng Gelei, Liu Yang, Xiangyu Zhang, Maura Pintor, Wenke Lee, Yuval Elovici, and Battista Biggio. 2023.  The threat of offensive AI to organizations.  _Computers & Security_, 124:103006.
  * Mitchell et al. (2023) Eric Mitchell, Yoonho Lee, Alexander Khazatsky, Christopher D Manning, and Chelsea Finn. 2023.  Detectgpt: Zero-shot machine-generated text detection using probability curvature.  _arXiv preprint arXiv:2301.11305_.
  * Myles et al. (2005) Ginger Myles, Christian Collberg, Zachary Heidepriem, and Armand Navabi. 2005.  The evaluation of two software watermarking algorithms.  _Software: Practice and Experience_ , 35(10):923–938.
  * Nijkamp et al. (2023) Erik Nijkamp, Bo Pang, Hiroaki Hayashi, Lifu Tu, Huan Wang, Yingbo Zhou, Silvio Savarese, and Caiming Xiong. 2023.  Codegen: An open large language model for code with multi-turn program synthesis.  In _The Eleventh International Conference on Learning Representations_.
  * OpenAI (2022) OpenAI. 2022.  Chatgpt: Optimizing language models for dialogue.  _OpenAI Blog_.
  * OpenAI (2023a) OpenAI. 2023a.  Ai text classifier. _OpenAI API Docs_.
  * OpenAI (2023b) OpenAI. 2023b.  Gpt-4 technical report.  _OpenAI Blog_.
  * Pearce et al. (2022) Hammond Pearce, Baleegh Ahmad, Benjamin Tan, Brendan Dolan-Gavitt, and Ramesh Karri. 2022.  Asleep at the keyboard? assessing the security of GitHub copilot’s code contributions.  In _2022 IEEE Symposium on Security and Privacy (SP)_ , pages 754–768. IEEE, IEEE.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _The Journal of Machine Learning Research_ , 21(1):5485–5551.
  * Sandoval et al. (2023) Gustavo Sandoval, Hammond Pearce, Teo Nys, Ramesh Karri, Siddharth Garg, and Brendan Dolan-Gavitt. 2023.  Lost at c: A user study on the security implications of large language model code assistants.  _arXiv preprint arXiv:2208.09727_.
  * Solaiman et al. (2019) Irene Solaiman, Miles Brundage, Jack Clark, Amanda Askell, Ariel Herbert-Voss, Jeff Wu, Alec Radford, Gretchen Krueger, Jong Wook Kim, Sarah Kreps, et al. 2019\.  Release strategies and the social impacts of language models.  _arXiv preprint arXiv:1908.09203_.
  * Tao et al. (2014) Hai Tao, Li Chongmin, Jasni Mohamad Zain, and Ahmed N Abdalla. 2014.  Robust image watermarking theories and techniques: A review.  _Journal of applied research and technology_ , 12(1):122–138.
  * Tian (2023) Edward Tian. 2023.  Gptzero: An ai text detector. _GPTZero Website_.
  * Topkara et al. (2006) Umut Topkara, Mercan Topkara, and Mikhail J. Atallah. 2006.  The hiding virtues of ambiguity.  In _Proceedings of the 8th workshop on Multimedia and security_ , pages 164–174. ACM.
  * Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. 2023.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_.
  * Vaithilingam et al. (2022) Priyan Vaithilingam, Tianyi Zhang, and Elena L Glassman. 2022.  Expectation vs. experience: Evaluating the usability of code generation tools powered by large language models.  In _Chi conference on human factors in computing systems extended abstracts_ , pages 1–7.
  * Venugopal et al. (2011) Ashish Venugopal, Jakob Uszkoreit, David Talbot, Franz Och, and Juri Ganitkevitch. 2011.  Watermarking the outputs of structured prediction with an application in statistical machine translation. In _Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing_ , pages 1363–1372, Edinburgh, Scotland, UK. Association for Computational Linguistics.
  * Wang et al. (2018) Yilong Wang, Daofu Gong, Bin Lu, Fei Xiang, and Fenlin Liu. 2018.  Exception handling-based dynamic software watermarking.  _IEEE Access_ , 6:8882–8889.
  * Yang et al. (2022) Xi Yang, Jie Zhang, Kejiang Chen, Weiming Zhang, Zehua Ma, Feng Wang, and Nenghai Yu. 2022.  Tracing text provenance via context-aware lexical substitution.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, pages 11613–11621. Association for the Advancement of Artificial Intelligence (AAAI).
  * Yoo et al. (2023) KiYoon Yoo, Wonhyuk Ahn, Jiho Jang, and Nojun Kwak. 2023.  Robust natural language watermarking through invariant features.  _arXiv preprint arXiv:2305.01904_.
  * Zellers et al. (2019) Rowan Zellers, Ari Holtzman, Hannah Rashkin, Yonatan Bisk, Ali Farhadi, Franziska Roesner, and Yejin Choi. 2019.  Defending against neural fake news.  In _Advances in Neural Information Processing Systems_.
  * Zheng et al. (2023) Qinkai Zheng, Xiao Xia, Xu Zou, Yuxiao Dong, Shan Wang, Yufei Xue, Zihan Wang, Lei Shen, Andi Wang, Yang Li, et al. 2023.  Codegeex: A pre-trained model for code generation with multilingual evaluations on humaneval-x.  _arXiv preprint arXiv:2303.17568_.