# DAG-based Scheduling with Resource Sharing for Multi-task Applications in a
Polyglot GPU Runtime

Alberto Parravicini  Politecnico di Milano
Milan, Italy
<EMAIL_ADDRESS>Arnaud Delamare  Oracle Labs
Zürich, Switzerland
<EMAIL_ADDRESS>Marco Arnaboldi  Oracle Labs
Zürich, Switzerland
<EMAIL_ADDRESS>Marco D. Santambrogio  Politecnico di Milano
Milan, Italy
<EMAIL_ADDRESS>
###### Abstract

GPUs are readily available in cloud computing and personal devices, but their
use for data processing acceleration has been slowed down by their limited
integration with common programming languages such as Python or Java.
Moreover, using GPUs to their full capabilities requires expert knowledge of
asynchronous programming. In this work, we present a novel GPU run time
scheduler for multi-task GPU computations that transparently provides
asynchronous execution, space-sharing, and transfer-computation overlap
without requiring in advance any information about the program dependency
structure. We leverage the GrCUDA polyglot API to integrate our scheduler with
multiple high-level languages and provide a platform for fast prototyping and
easy GPU acceleration. We validate our work on 6 benchmarks created to
evaluate task-parallelism and show an average of 44% speedup against
synchronous execution, with no execution time slowdown compared to hand-
optimized host code written using the C++ CUDA Graphs API.

###### Index Terms:

GPU, Scheduling, Software Runtime, Hardware Acceleration

##  I Introduction

Graphics Processing Units (GPUs) are often heralded as the optimal solution to
achieve extremely high throughputs in domains such as Deep Learning, financial
simulations, and graph analytics. Even if GPUs are made available by most
cloud providers and are commonly found in personal devices, using GPUs for
data processing acceleration has been hampered by their limited integration
with high-level programming languages such as Python or Java. Fully exploiting
the hardware resources of GPUs requires a deep understanding of their
architecture and creates a steep learning curve that takes a long time for
programmers to overcome. As a consequence, the adoption of GPUs is often
limited to specific domains for which libraries or Domain-Specific Languages
(DSLs) that abstract and mask the GPU computation are available.

On the other hand, APIs offering complete control over the GPU still require
efforts to unleash the full hardware potential, e.g. to overlap and
synchronize multiple computations, or to overlap computation with data
transfer from and to the GPU. In this work, we present a novel GPU runtime
scheduler that transparently provides all these optimizations without
requiring in advance any information about the structure of the computation.
We leverage the Graal polyglot Virtual Machine (VM) [1, 2, 3], and the GrCUDA
environment [4], to run GPU kernels from languages such as Python, Java, and
Ruby and obtain full control over the GPU runtime to optimize scheduling, data
transfer, and execution. We target the CUDA platform, but similar
considerations would work for OpenCL [5], given the availability of a managed
execution environment.

###  I-A Motivation

Modern GPUs allow multiple computations to run asynchronously and concurrently
to leverage task-level parallelism: experienced programmers accelerate their
programs by prefetching and overlapping data transfers with computations on
different data or even take advantage of hardware space-sharing by overlapping
multiple independent computations.

Figure 1: Achievable speedup in C++ CUDA with hand-tuned GPU data transfer and
execution overlap. Fine-tuned space-sharing and execution-transfer overlaps
can accelerate GPU computations by more than 50%.

Figure 1 shows how much speedup can be extracted in different CUDA benchmarks
(presented in section V-B) by hand-crafting these optimizations. Computations
with opportunities for task-level parallelism are common: even the simple
machine learning pipeline in Figure 2 has two independent branches whose
results are combined at the end. Instead of executing computations
sequentially, a skilled programmer schedules independent tasks on separate
execution streams. However, achieving full utilization of the GPU often
requires extensive debugging and profiling, even by experienced users [6];
performance may also depend on the data available at run time, and it cannot
be perfectly fine-tuned by the programmers.

Our work aims to provide a low-profile runtime that can automatically leverage
untapped GPU resources in multi-task computations to provide speedups
identical to what a skilled programmer can achieve by hand, lowering the
barrier of access to GPUs with no performance compromises.

###  I-B Contributions

In this work, we present a novel low-profile run time scheduler for multi-task
and asynchronous GPU computations.

Our scheduler automatically infers data dependencies between GPU kernels,
models them using a Directed Acyclic Graph (DAG), and enable asynchronous CPU
and GPU execution without users having to define any synchronization event or
dependencies manually. More importantly, dependencies and scheduling are
computed entirely at run time, without defining the computation structure in
advance, and without constraints on the host language control flow.

This work is implemented as an extension of GrCUDA, a polyglot CUDA API based
on GraalVM[1]. GrCUDA is implemented as a Truffle DSL [2] and provides access
to GPU acceleration to languages supported by GraalVM, such as Java, Scala,
JavaScript, R, and Python. Our scheduler is available in all these languages;
moreover, any new feature or optimization to our scheduler will be available
without language-specific modifications. Our scheduler enables GrCUDA to
become a valid solution for general-purpose GPU acceleration, focusing on fast
prototyping and integration with high-level languages that do not currently
have a strong GPU support.

We evaluate our scheduler on 6 benchmarks from different domains that exhibit
opportunities for task-level parallelism and show an average of 44% speedup
against the serial GrCUDA scheduler and no significant slowdown against hand-
optimized scheduling written using the C++ CUDA Graphs API; finally, we
analyze hardware utilization to understand how well each benchmark can exploit
data transfer-computation overlap and untapped GPU resources. The source code
for our scheduler and benchmarks is openly
available111github.com/AlbertoParravicini/grcuda.

In summary, we make the following contributions:

  * •

A run time scheduler based on GrCUDA that automatically infers dependencies
between GPU computations and dynamically schedules them to maximize transfer-
computation overlap and space-sharing (section IV).

  * •

A suite of 6 benchmarks to evaluate GPU asynchronous computations, task-
parallelism, and space-sharing hardware utilization (sections V-B and V-F).

  * •

An evaluation of how our scheduler provides an average of 44% speedup against
the serial GrCUDA scheduler and no slowdown against hand-optimized scheduling
based on the CUDA Graphs API (sections V-C and V-D).

Figure 2: The two branches in this computation are independent, and can be
scheduled and executed in parallel. Edges are labeled with the argument that
cause a data dependency.

##  II Related Work

Expressing a multi-task computation as a DAG that can be used to estimate an
effective scheduling and to optimize execution is a concept that has already
been explored with a great degree of success: well-known work that covers GPU
computations includes Nvidia’s CUDA Graphs[7] and Google’s Tensorflow [8];
academic research has also shown interest in domains such as distributed and
heterogeneous computing [9, 10, 11], and presented valuable theoretical
results [12, 13]. CUDA Graphs are a programming model recently released by
Nvidia used to define a DAG of inter-dependent computations and execute them
asynchronously. Computations between dependencies must be specified manually
using CUDA events, or with a fairly complex custom API [7]. CUDA Graphs also
present initialization overheads due to graph creation [14]. Instead,
TensorFlow allows users to express a DAG of computations through a DSL
embedded in languages such as Python. TensorFlow is mostly intended for Deep
Learning (DL); expressing custom kernels for other domains, while supported,
is not straightforward and requires significant manual integration effort. We
do not deem a direct comparison with our work to be meaningful, as TensorFlow
presents design choices specifically targeted towards DL.

Indeed, the most common approach to DAG-based scheduling, as seen in CUDA
Graphs and TensorFlow, is to specify the program flow in advance: this choice
simplifies the computation of an optimal scheduling and amortizes overheads in
case of repeated computations, and is certainly suitable for specific domains
such as DL. On the other hand, the approach presented in this work is to
capture GPU computations through a low-profile runtime, without the need to
specify dependencies manually. As such, we do not impose any limitation over
the host program control-flow (e.g. conditional statements, function calls,
recursion, library calls) so that the program flow can change over time. In
the simplest scenario, a programmer might use multiple kernel implementations
optimized for different input sizes or use different pre-processing procedures
based on the input data language; selecting the appropriate kernel is done
simply through conditional statements in the host language (e.g. a switch-case
in Python), without requiring custom APIs or defining multiple DAGs in
advance.

Computing dependencies at runtime on heterogeneous architectures has been
explored by the XKaapi runtime [15]. Contrary to our approach, XKaapi uses a
work-stealing strategy that computes dependencies every time an idle thread
looks for a task to execute. It handles GPU memory as a queue of blocks
instead of leveraging the fine-grained flexibility of Unified Memory (UM), and
its complex API is limited to C++.

Many techniques to virtualize GPUs usage have emerged recently, although
space-sharing is still considered an open challenge [16]. Ravi et al. [17]
consolidate kernels from different VMs to increase utilization. TornadoVM
[18], which is also compatible with GraalVM, translates annotated Java code
for heterogeneous hardware; it profiles the code to understand the most
suitable backend, and infers automatically data-dependencies and data-transfer
through a task graph obtained from the computations specified in advance by
the user [19].

Today, most programming languages have ways to achieve GPU acceleration,
including Python (PyCUDA, PyOpenCL [20]), Java (Jcuda222Jcuda: www.jcuda.org,
GPU.js: https://gpu.rocks) and JavaScript (GPU.js). However, none of these
libraries can automatically handle asynchronous computations and space-
sharing. Moreover, each library has different APIs, supported features, and
update cycles, greatly limiting code portability and interoperability;
instead, the unified GrCUDA runtime and API immediately provides each new
feature (such as our scheduler) to all languages supported by GraalVM without
any change in the host code.

Recent research on GPU space-sharing includes the work of Wen et al. [21], who
showed how concurrent execution of some GPU kernels without data dependencies
delivers up to 1.5x speedup; Qiao et al. [22] uses concurrent kernel execution
to achieve 2.5x speedup over serial execution on multiresolution image
filters. Baymax [23] focuses on multi-application space sharing. DCUDA [24]
provides scheduling for different applications on multiple GPUs, and shows how
CUDA UM causes an average slowdown below 1%. We focus on single-application
space-sharing, i.e. applications composed of many kernels that can run in
parallel, but considerations on hardware utilization are valid in both single
and multi-application space-sharing. As GrCUDA seamlessly integrates with
CUDA, our work directly benefits from improvements on the CUDA API and
drivers. For example, we could leverage alternative UM implementations
optimized to overlap data transfer with computations, such as HUM [25].

##  III Background

GPUs allow the execution of multiple kernels at the same time. If enough
resources are available - e.g. free Stream Multiprocessor (SM), the main GPU
computation units - the GPU will perform space-sharing and run kernels in
parallel. Modern GPUs often have enough resources to perform space-sharing
without significantly degrading the performance of individual kernels [22]:
space-sharing can improve the occupancy of SMs and exploit under-utilized
hardware resources. Kernels run in parallel and asynchronously thanks to CUDA
streams: kernels are executed in issue-order on a stream, but different
streams proceed independently. Space-sharing is key for better GPU resource
usage, but requires even greater care to ensure that programs run correctly.
Synchronizing a single stream through the cudaStreamSynchronize function
blocks the host execution and is generally acceptable only if the host
requires the output of a GPU kernel. A more flexible approach is the use of
CUDA events333docs.nvidia.com/cuda/cuda-runtime-api/group__CUDART__EVENT.html,
which allow streams to synchronize with each other without blocking the host
execution. Using CUDA events to efficiently synchronize multiple complex
streams by hand can be cumbersome: instead, our solution masks CUDA events and
greatly simplifies the optimal scheduling of asynchronous computations
(section IV).

Figure 3: Dependency computations with read-only arguments. Updates to the DAG
and to dependency sets are highlighted.

In CUDA, computations are divided in blocks, each composed of an equal number
of threads (from 32 to 1024). Bigger blocks imply fewer blocks running
concurrently, but more possibilities of sharing data through fast block-wide
shared-memory. Users can choose the number of threads per block; depending on
the kernel implementation, users can also choose the number of blocks. While a
small number of blocks increases space-sharing, achieving a performance
improvement depends on the characteristics of the kernels. These
considerations also apply to OpenCL: streams are called command queues,
threads are work items, and the event model is similar to CUDA. Streams can
also improve performance by overlapping asynchronous data transfer (from CPU
to GPU or vice-versa) and computations: in Figure 2 the transfer of array r1
(required by kernel NB) can be overlapped with execution of kernel NO. This
approach is fruitful with repeated execution of simple kernels on different
data batches, as the data transfer takes a significant amount of the total
execution time. When using UM on GPUs that offer page migration, it is
beneficial to prefetch data instead of relying on migrations caused by page
faults: our scheduler can prefetch data automatically, reducing the burden of
GPU optimization.

We leverage GraalVM, a Java VM able to run and combine languages that compile
to Java bytecode (e.g. Scala) and custom implementations of other languages
such as JavaScript, R, and Python [1]. This interoperability is possible
thanks to the Truffle Abstract Syntax Tree interpreter [2], which guarantees
high-performance through partial evaluation of repeated portions of code. Our
work is an extension of GrCUDA, a CUDA language binding implemented as a
Truffle DSL. GrCUDA can be seen as a polyglot API, as it provides GPU
acceleration to all languages supported by GraalVM.

##  IV Scheduler Design Methodology

This section details the design and implementation of our scheduler. We
provide a definition of our computation DAG (section IV-A). Then, we define
our scheduler’s architecture and its integration with the CUDA runtime
(sections IV-B and IV-C). Finally, we show how to leverage the language design
of GrCUDA to provide asynchronous GPU computation without any detriment to
accessibility (section IV-D).

###  IV-A Computation DAG and Dependency Sets

The cornerstone of our scheduler is a Computation DAG that represents
relationships between computations that involve the GPU. Vertices of the DAG
are computational elements: GPU kernels, memory accesses by the CPU host
program to GrCUDA UM-backed arrays, and pre-registered or user-defined library
functions such as RAPIDS444developer.nvidia.com/rapids. Using GrCUDA and
GraalVM, each element can be encapsulated through an object to keep track of
its state. In the case of kernels, the object tracks its configuration (e.g.
the number of blocks), its input arguments, and if the computation is active.

Edges of the DAG are data dependencies between computational elements.
Dependencies are inferred automatically instead of being manually specified by
the user through handles or other APIs. Inferring data dependencies is
possible as GrCUDA uses a managed execution environment that allows object
encapsulation of inputs, removing the risk of pointer aliasing typical of
native languages (e.g. having multiple pointers referring to the same memory
area). The scheduler employs data dependencies modeled through the DAG to
associate computational elements to CUDA streams and introduces
synchronization events if required. To compute dependencies, we associate with
each computational element a dependency set. This set initially contains all
arguments of the computational element. An argument in the set is removed when
a subsequent computation uses and modifies the same argument, defining a data
dependency on it; once a set is empty, the corresponding computational element
can no longer introduce dependencies. Read-only kernel arguments (specified as
in section IV-D) can be treated with special rules to avoid adding unnecessary
dependencies to the DAG. If possible, they will be ignored in the dependency
computations: for example, if two kernels use the same read-only input array,
they will be executed concurrently on different streams. Figure 3 shows a
kernel that modifies an argument and is followed by another kernel that uses
the same argument as read-only A. If a third kernel with the same input is
added, it will depend on the second kernel if it modifies the argument (a
write-after-read anti-dependency) B, and it will depend on the first kernel if
it uses the argument as read-only C; it will not, however, depend on both
kernels. In case C, the read-only argument adds a new dependency through X,
but the dependency set of the parent kernel K1 is not updated: if a new kernel
requires X as read-only argument, it will depend on K1, otherwise it will
depend on both K2 and K3, and all dependency sets will be updated.

Figure 4: Example of scheduling for the VEC benchmark. We show both the GrCUDA
code and the resulting DAG.

The DAG is built at run time, not at compile-time or eagerly. Users do not
have to worry about their host program’s control flow, as we dynamically add
and schedule new computations as users provide them. Our scheduler is unaware
of the full logical DAG structure of a given program, although we usually show
complete DAGs for clarity (e.g. Figures 2 and 6). Instead, the scheduler
updates the current graph frontier, i.e. the computations that are currently
active. This choice is key to enable the dynamic creation of the DAG and does
not introduce limitations on the optimizations that our scheduler could
perform. We track each kernel’s historical performance and scheduling to allow
the creation of heuristics that guide future scheduling of the same kernel.

In GrCUDA, arrays are backed by UM, which simplifies data movement and
accesses from the CPU without large performance penalties [24]. As the CPU can
schedule accesses to these arrays at any point (even while the GPU is
running), we model these accesses as computational elements. If the access
introduces a data dependency on a GPU computation, the scheduler ensures that
the CPU waits for that computation to end. To keep overheads as low as
possible, array accesses that do not introduce data dependencies with respect
to GPU kernels are executed immediately, without modeling them as DAG
elements: this is the case of consecutive accesses or accesses performed while
no GPU computation is active. Pre-registered libraries can also take advantage
of our scheduler if they expose the choice of execution stream in their API.
If not, they are scheduled synchronously to guarantee correctness.

Figure 4 shows the GrCUDA code (with Python as host) of the VEC benchmark
(section V-B). For each kernel invocation in the host, the scheduler adds a
computational element to the DAG, updates the dependency sets of active
computations, and provides a CUDA stream for execution. Executing K2 (Figure
4, C) requires a CUDA event to ensure that K1 is completed. Accessing Z on the
CPU ensures that all computations are completed: they will no longer
contribute to new dependencies. The host code does not need to care about the
scheduling, and it can be written as if it were run sequentially, with no
explicit mention of synchronization points or streams.

###  IV-B System Architecture

Figure 5 shows the main components of our scheduler and their integration with
the existing GrCUDA architecture. The GPU execution context tracks
declarations and invocations of GPU computational elements 1. When a new
computation is created or called, it notifies the execution context 2 so that
it updates the DAG with data dependencies of the new computation 3. The GPU
execution context uses the DAG to understand if the new computation can start
immediately or if it must wait for other computations to finish. Computations
are overlapped using different CUDA streams, assigned by the stream manager
based on dependencies and free resources (section IV-C) 4. The stream manager
5 and the execution context 6 interact with the GPU through an intermediate
layer that exposes the CUDA API to GrCUDA.

GPU computations are asynchronous and do not require synchronization against
previous computations on the stream where they are executed, as CUDA
guarantees sequential execution of computations scheduled on a stream. We
synchronize streams with CUDA events without blocking the host CPU. Each
computation is associated with an event to provide a precise synchronization
point instead of blocking the entire stream. If the CPU requires data for a
computation, we synchronize only the streams that are currently operating on
this data. The scheduler considers GPU computations as active until the CPU
requires their result or one of their children. We use active computations to
identify dependencies (unless their dependency set is empty) and empty
streams.

Figure 5: Our scheduler integrates with the existing GrCUDA architecture. New
components are highlighted in red.

###  IV-C Scheduling Policies and Stream Management

A scheduler is serial if computations are executed one after the other in the
order defined by the user, and their execution or data transfer do not
overlap. A parallel scheduler allows overlaps to happen, and data dependencies
determine the order in which computations are executed. In a synchronous
scheduler the CPU host program waits for GPU computations to finish, while an
asynchronous scheduler allows the CPU to perform other computations while the
GPU is active. The original GrCUDA scheduler is serial and synchronous, while
our scheduler is parallel and asynchronous.

CUDA streams are key to enable parallel and asynchronous computation. In our
scheduler, the allocation and management of streams are performed
transparently by a stream manager. The stream manager also tracks what
computations are currently active in each stream and handles events used for
synchronization. Users can specify different policies to create new streams
and to associate them with computations. Existing streams are managed in FIFO
order, and new streams are created only if no currently empty stream is
available to schedule a given computation. If a computation has multiple
children (i.e. computations that depend on it), the first child is scheduled
on the parent’s stream to minimize synchronization events, while following
children are scheduled on other streams to guarantee concurrency. Simpler
policies (e.g. schedule all children on a single stream) further reduce the
scheduling costs; that said, our experiments always use the more general
policies and show negligible scheduling overheads (section V-D). The stream
manager is architecture-aware: on GPU architectures older than Pascal, the CPU
cannot access UM if a kernel is active in the GPU. The stream manager
restricts each array’s visibility to the stream where it is used until the CPU
needs to access the array. The CPU is made temporarily unaware of the
existence of arrays being used by the GPU, and can access currently unused
arrays even if the GPU is active. While this optimization is not required on
architectures since Pascal (thanks to its page fault mechanism), our scheduler
can automatically prefetch data to optimize transfers.

Figure 6: Computation structure of each benchmark, expressed as a DAG of GPU
kernel computations (denoted as circles). Colors denote CUDA streams, and
kernels whose incoming arrows have different colors will require a
synchronization event.

###  IV-D Language Design and Integration

Our scheduler leverages the GrCUDA language’s existing features and does not
introduce any user-facing modification to the language. Kernel signatures are
specified using Native Interface Definition Language (NIDL) or Truffle Native
Function Interface (NFI), simple typing systems that support basic data types
and pointers. Optional argument annotations such as input, output or const are
used by the scheduler to optimize computations that contain read-only
arguments (input or const). For arguments without annotations, the scheduler
treats them as modifiable by the kernel; not specifying arguments as read-only
does not affect correctness, but might limit the scheduler from performing
further optimizations.

##  V Experimental Evaluation

In this section, we evaluate the performance of our GrCUDA GPU scheduler
against multiple benchmarks that exhibit task-level parallelism and
opportunities to leverage space-sharing and transfer-computation overlap to
achieve lower execution time than a serial scheduler (section V-B). First, we
compare against the serial GrCUDA scheduler (section V-C) and show how our
scheduler can exploit untapped GPU resources to deliver better performance
than a naïve serial scheduler.

Then, we compare the performance of the GrCUDA against the C++ CUDA API,
measure how the GrCUDA scheduling is identical to the best hand-tuned
scheduling possible, and how GrCUDA does not add any significant slowdown in
the benchmark execution times (section V-D).

Finally, we investigate, for each benchmark, the nature of the achieved
speedup. First, we measure the amount of resource contention introduced by
hardware space-sharing (section V-E); second, we measure what overlaps are
present (transfer-computation or space-sharing), and we analyze how well each
benchmark is using hardware resources such as device memory and L2 cache to
understand which workloads are more suitable for asynchronous execution
(section V-F).

###  V-A Evaluation Setup

Tests are performed on 3 different Nvidia GPUs with different architectures: a
Tesla P100 (Pascal, 12 GB of device memory), a GTX 1660 Super (Turing, 6 GB),
and a GTX 960 (Maxwell, 2 GB). GPUs are connected to their respective host
machines through PCI Express (PCIe) 3.0. Testing consumer-grade GPUs such as
the GTX 1660 Super and the GTX 960 shows how our scheduler does not demand
high-end data-center hardware to provide benefits, and it is useful for quick
prototyping on commodity GPUs and to accelerate desktop applications.
Benchmarks are executed 30 times on random data. We select the input sizes in
each benchmark to use between 10% and 90% of the available memory on each GPU,
up to the largest size that fits in device memory. Execution time is the total
amount of time spent by GPU execution, from the first kernel scheduling until
the end of execution. Parameters (e.g. the number of blocks) are optimized for
best performance in serial execution to provide a worst-case comparison. The
x-axes in Figures 7, 8 and 9 report the benchmark scale, a value proportional
to the benchmark’s memory footprint (e.g. the number of pixels in each input
image).

TABLE I: Amount of device memory for different input sizes in each benchmark.
GPUs are tested with different input sizes up to the largest size that fits in
GPU memory.

| Memory footprint (GB)
---|---
Benchmark name |  GTX 960 |  GTX 1660 Super |  Tesla P100
Vector Squares (VEC) | 0.4 GB - 1.9 GB | 0.4 GB - 3.1 GB | 0.4 GB - 11 GB
Black & Scholes (B&S) | 0.4 GB - 1.9 GB | 0.4 GB - 3.1 GB | 0.4 GB - 11 GB
Images (IMG) | 0.2 GB - 1.0 GB | 0.2 GB - 5.1 GB | 0.2 GB - 9.1 GB
ML Ensemble (ML) | 0.4 GB - 1.9 GB | 0.4 GB - 3.3 GB | 0.4 GB - 9.9 GB
HITS | 0.4 GB - 1.5 GB | 0.4 GB - 4.2 GB | 0.4 GB - 9.9 GB
Deep Learning (DL) | 0.3 GB - 1.4 GB | 0.3 GB - 4.9 GB | 0.3 GB - 6.5 GB
GPU device memory | 2 GB | 6 GB | 12.2 GB

###  V-B Benchmark Suite

We tested our scheduler on 6 benchmarks and a total of 33 different kernels
representing common GPU workloads (image processing, machine learning, etc.)
and containing opportunities for task-level parallelism through space-sharing
and computation-transfer overlap. To the best of our knowledge, no existing
GPU benchmark suite has the goal of evaluating intra-application task-level
parallelism, as most benchmark suites (e.g. Rodinia [26]) focus on single
kernels and sequential execution. Still, we take or derive the CUDA kernels in
our benchmarks from open-source implementations.

We scale the input size linearly to visualize more clearly if any hardware
bottleneck impacts performance as input size exceeds a threshold. For
instance, we change the number of rows for the matrix multiplications in the
ML benchmark, but keep fixed the number of features and output classes.

Figure 6 presents each benchmark’s task dependency structure and highlights
the optimal stream assignment for each kernel. Table I summarizes each
benchmark. The chosen input sizes guarantee that the memory footprint covers
both small and large computations compared to the total memory of each GPU.
For each benchmark, we present a brief description.

  * •

Vector Squares (VEC): a simple benchmark that measures a basic case of task-
level parallelism and computes the sum of differences of 2 squared vectors.
Each iteration has new input data, simulating a streaming computation that
requires transfer from CPU to GPU. Inspired by [27].

  * •

Black & Scholes (B&S): Black & Scholes equation for European call options, for
10 underlying stocks, and 10 vectors of prices. Adapted from [28] to simulate
a computationally intensive streaming benchmark with double-precision
arithmetic and many independent kernels that can be overlapped with no
dependencies.

  * •

Image Processing (IMG): an image processing pipeline that combines a sharpened
picture with copies blurred at low and medium frequencies [29], to sharpen the
edges, soften everything else, and enhance the subject. The benchmark has
complex dependencies on 4 streams.

  * •

Machine Learning Ensemble (ML): an ML pipeline that combines Categorical Naïve
Bayes and Ridge Regression classifiers by applying softmax normalization and
averaging scores. The input matrix has 200 features. This benchmark contains
branch imbalance (the Naïve Bayes classifiers takes longer) and read-only
arguments.

  * •

HITS: it computes the HITS algorithm on a graph [30] using repeated Sparse
matrix-vector multiplication (SpMV) on a matrix and its transpose, and is
implemented with LightSpMV [31]. It contains complex cross-synchronizations
and multiple iterations.

  * •

Deep Learning (DL): a convolutional neural network that projects 2 input
images to low dimensional embeddings and combines the embeddings using a dense
layer. Similar neural networks can be used, for example, to classify if 2
images contain the same subject.

###  V-C Performance against Serial GrCUDA Scheduling

We compare the performance of our parallel scheduler against the GrCUDA serial
scheduler (Figure 7). Automatic data prefetching is enabled on the Tesla P100
and the GTX 1660 Super, while on the GTX 960, data is necessarily transferred
ahead of the computation as it does not have a page fault mechanism. We always
deliver better performance over the serial scheduler, with a geomean speedup
of 44% on the 3 GPUs. The GTX 960 is 25% faster, while the P100 performs the
best, with a geomean speedup of 61%. More hardware resources, together with
automatic prefetching, results in better parallelization, and we show how our
approach works out-of-the-box on data-center GPUs. While still faster than the
serial baseline, disabling automatic prefetching is not recommended:
concurrent kernel execution turns the page fault controller into the main
bottleneck, limiting the benefits of overlapping data transfer with
computation. When using serial scheduling, GrCUDA does not compute
dependencies, making overheads even smaller. We average results for block
sizes (the number of threads in each 1D block) from 32 to 1024. In benchmarks
with 2D and 3D blocks (e.g. IMG and DL), we keep 2D blocks with size 8x8 and
3D blocks with size 4x4x4, as bigger blocks resulted in longer execution times
in every case.

Speedups are mostly independent of the input data size, as we sweep through
inputs with size from less than 10% to almost 100% of the available GPU
memory. Even if kernels fill the GPU resources, it is still possible to
achieve a speedup by overlapping data transfer with other kernels’ execution.

Figure 7: Parallel scheduler speedup over serial schedugler. Our parallel
scheduler provides a geomean speedup of 44% over the original GrCUDA serial
scheduler. We highlight block sizes giving the best/worst speedup (when
significant).

DAG scheduling appears to be more robust to different kernel configurations:
in many cases (such as VEC and HITS), using block_size=32 results in higher
speedup, but similar execution time as with larger block size. With serial
scheduling, small blocks result in under-utilization of GPU resources such as
shared memory, while DAG scheduling provides better utilization by having
multiple kernels run in parallel. Thanks to DAG scheduling, programmers have
to spend less time profiling their code to find the optimal kernel
configuration.

Figure 8: Speedup of our GrCUDA scheduling against hand-optimized CUDA Graphs
(higher is better). We are always faster, and the GrCUDA runtime overheads are
negligible for computations lasting more than a few milliseconds.

###  V-D Performance against CUDA Graphs

To understand how our GrCUDA scheduler performs against existing solutions, we
re-implemented our benchmarks using the C++ CUDA Graphs API. The kernel code
and the setup (e.g. input and block sizes) are the same as GrCUDA, but the
host code is written using the C++ CUDA Graphs API. We test CUDA Graphs using
stream-capture to wrap hand-optimized multi-stream scheduling synchronized
with CUDA events and using the Graph API to specify dependencies between
computations manually. These CUDA Graphs are built only once per execution,
and overheads are completely amortized over many iterations. Finally, we
provide a hand-optimized implementation purely based on CUDA events to have
full control over data movement and simulate CUDA Graph’s performance if it
supported data prefetching.

Our GrCUDA scheduler, in addition to being fully automated, is never
significantly slower than any of the CUDA Graphs baselines and is often faster
(Figure 8). The large performance gaps compared to CUDA Graphs seen on the GTX
1660 Super and the P100 are mostly explained by our automatic prefetching,
which the CUDA Graphs API seems unable to perform. Even when enabling
prefetching in the CUDA baseline, our parallel scheduler achieves equal
performance to the hand-optimized baseline. Execution time speedups are hardly
affected by input size, with minor differences only in computations lasting a
few milliseconds and containing many dependencies (such as IMG).

###  V-E Impact of Space-Sharing Resource Contention

By looking at dependencies between kernels and measuring their execution time
with serial scheduling so that each kernel has full access to the GPU
resources, we estimate the resource contention on the GPU hardware and the
PCIe bandwidth introduced by space-sharing. Figure 9 shows how far each
benchmark is from its theoretical contention-free peak performance. Results
are mostly consistent between GPUs, with a relative execution time that is
often around 70% of the contention-free performance bound; while resource
contention is present, it is small enough to make space-sharing worthwhile.
Unsurprisingly, B&S, which is composed of 10 independent computations,
achieves around 15-20% of its contention-free peak performance due to
limitations on PCIe bandwidth and double-precision arithmetic units
availability.

Figure 9:  Slowdown compared to execution without hardware resource
contention. Space-sharing introduces a performance loss of around 30-40% due
to hardware space-sharing.

###  V-F Analysis of Hardware Utilization

It is fascinating to understand, for each benchmark, the nature of the speedup
achieved through resource sharing, i.e., if the speedup is caused by
overlapping computation with data transfer or if the speedup is explained by
higher utilization of GPU resources such as device memory bandwidth through
space-sharing. First, we measure how much overlap is present in each
benchmark. We measure 4 different types of overlap:

  * •

CT, computation against transfer: percentage of GPU kernel computation that
overlaps with any data transfer

  * •

TC, transfer against computation: percentage of data transfer that overlaps
with any kernel computation(s)

  * •

CC, percentage of GPU computation overlapped with other GPU computation

  * •

TOT, any type of overlap: here we consider any type of overlap between data-
transfer and/or computations. If a computation/data-transfer overlaps more
than one computation/data-transfer, the overlap is counted only once (we
consider the union of the overlap intervals)

Figure 10 shows how we compute these overlaps starting from the execution
timeline. Although the TOT overlap can be a good proxy of the achieved
speedup, it is sometimes inflated by high CC overlap, as overlapping
computations does not always translate to faster execution. In VEC, the
speedup comes only from transfer and computation overlap, while the overlap of
kernels that leave a large amount of shared memory unused if executed serially
explains the speedup in IMG.

Computation time and transfer time do not increase with the same
proportionality factor as the input size; small input data do not use the PCIe
bandwidth fully, and a 10x increase in data size might translate into a
transfer time increase below 10x, up to the available bandwidth. On faster
GPUs the computation time is lower, while the transfer time is roughly
identical to less powerful hardware (assuming the same transfer interface):
more computation is overlapped to data transfer, leading to better speedups.
For example, in the B&S benchmark, the CT overlap increases on faster GPUs,
and so does the speedup.

Figure 10: Example of a possible execution timeline for the ML benchmark. We
highlight different types of overlap between transfer and computation, as
defined in section V-F.
Figure 11:  Amount of transfer and computation overlap for each benchmark, for
serial and parallel scheduling. We report below each plot the speedup obtained
in the benchmark.
Figure 12:  Hardware metrics for each benchmark and execution policy, as
measured on the GTX 1660 Super. All benchmarks in which different kernels
overlap their execution show an increase in hardware utilization.

We then analyze how our parallel scheduler affects hardware-level metrics such
as device memory throughput, L2 cache throughput, Instructions per cycle
(IPC), and GFLOPS. We use nvprof and
ncu555https://docs.nvidia.com/cuda/profiler-users-guide/index.html,
https://docs.nvidia.com/nsight-compute/NsightComputeCli/index.html to measure
the number of bytes read/written by each kernel from/to device memory and L2
cache, and the total number of instructions executed. As collecting these
metrics introduces high execution time overhead and prevents the execution of
concurrent kernels, we combine the execution timeline without metric
collection with hardware metrics collected in separate runs (variance in these
metrics between different runs is insignificant). Metrics are collected only
on the GTX 1660 Super as we did not have root-level access to the Tesla P100.
The amount of bytes read/written and the total number of instructions executed
by each kernel mostly depends on the kernel itself and is not significantly
impacted by space-sharing; as such, this evaluation is useful to estimate the
global GPU behavior when space-sharing is performed. GFLOPS is estimated from
the total number of floating-point operations (single and double precision).

Figure 12 shows how in kernels with computation overlap (e.g. ML and IMG), the
increase in memory throughput is significant and in-line with the total
speedup observed for these benchmarks. VEC does not have any increase in
memory throughput, as its speedup comes exclusively from transfer overlap.
Benchmarks that operate on dense matrices make heavier use of L2 cache, whose
throughput increases with parallel scheduling. The low IPC in ML is caused by
a slow kernel that operates on tall matrices and does not use the GPU
parallelism to its full extent: running multiple kernels in parallel hides its
latency and provides the speedup in Figure 7.

From these analyses, we understand what limits performance in each benchmark.
For example, B&S performs complex mathematical operations on independent
values, with a very high GFLOPS count (Figure 12) and almost no cache
utilization. On the GTX 1660, B&S has high TC and low CT (Figure 11); the
computation lasts longer than the data transfer, and part of the computation
is not overlapped; on the other hand, the Tesla P100, which has 20x higher
double-precision performance than the 1660, completely masks the computation
with transfer (high CT), and indeed we observe a better speedup. Improving
performance even further requires lowering the transfer time, for example,
through PCIe 4.0.

##  VI Conclusion and future work

We presented a novel scheduler for GPU computations that can automatically
infer data dependencies to build a computation DAG at run time. The scheduler
allows computations to execute in parallel through GPU space-sharing and
overlaps data-transfer and execution whenever possible.

We validate our scheduler on 6 benchmarks and a total of 33 GPU kernels. Our
scheduler provides a geomean speedup of 44% (up to 270%) over serial
synchronous scheduling, and is always faster. It automatically achieves the
same scheduling as hand-optimized CUDA Graphs code, without any slowdown.

Our scheduler seamlessly integrates with the GrCUDA environment, a polyglot
CUDA API based on GraalVM that provides easy access to GPU acceleration to
languages such as Java, Python, JavaScript, and R. Users can leverage our work
without knowledge of the underlying scheduler, and without changing their
code. It is not required to specify in advance the code structure or control
flow, as our scheduler dynamically executes computations as provided by the
host program. Our work simplifies GPU code prototyping and acceleration by
giving easy access to untapped GPU resources at no cost, while masking the
complexity of asynchronous GPU computations.

As future work, we plan to extend our technique to multiple GPUs: the problem
is significantly harder, as it requires to compute data location and migration
costs at run time to identify the optimal scheduling. We will also leverage
run time information for additional optimizations, such as estimating the
ideal block size based on data size and previous executions.

## Acknowledgments

We thank Oracle Labs for its support and contributions to this work. The
authors from Politecnico di Milano are funded in part by a research grant from
Oracle. We also thank Rene Mueller and Lukas Stadler, the original authors of
GrCUDA, for their valuable feedback and opinions. Oracle and Java are
registered trademarks of Oracle and/or its affiliates.

## References

  * [1] T. Würthinger, C. Wimmer, A. Wöß, L. Stadler, G. Duboscq, C. Humer, G. Richards, D. Simon, and M. Wolczko, “One vm to rule them all,” in _Proceedings of the 2013 ACM international symposium on New ideas, new paradigms, and reflections on programming & software_, 2013.
  * [2] C. Wimmer and T. Würthinger, “Truffle: a self-optimizing runtime system,” in _Proceedings of the 3rd annual conference on Systems, programming, and applications: software for humanity_. ACM, 2012.
  * [3] G. Duboscq, L. Stadler, T. Würthinger, D. Simon, C. Wimmer, and H. Mössenböck, “Graal ir: An extensible declarative intermediate representation,” in _Proceedings of the Asia-Pacific Programming Languages and Compilers Workshop_ , 2013.
  * [4] R. Mueller and L. Stadler, “Grcuda,” github.com/NVIDIA/grcuda.
  * [5] J. E. Stone, D. Gohara, and G. Shi, “Opencl: A parallel programming standard for heterogeneous computing systems,” _Computing in science & engineering_, vol. 12, no. 3, p. 66, 2010.
  * [6] J. Luitjens, “Cuda streams: Best practices and common pitfalls,” in _GPU Techonology Conference_ , 2015.
  * [7] “Cuda graphs,” https://docs.nvidia.com/cuda/cuda-runtime-api/group__CUDART__GRAPH.html, retrieved on 2020-10-12.
  * [8] M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard _et al._ , “Tensorflow: A system for large-scale machine learning,” in _12th $\\{$USENIX$\\}$ Symposium on Operating Systems Design and Implementation ($\\{$OSDI$\\}$ 16)_, 2016, pp. 265–283.
  * [9] L. Marchal, H. Nagy, B. Simon, and F. Vivien, “Parallel scheduling of dags under memory constraints,” in _2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS)_. IEEE, 2018.
  * [10] Y. Xu, L. Liu, and Z. Ding, “Dag-aware joint task scheduling and cache management in spark clusters,” in _2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS)_. IEEE, 2020, pp. 378–387.
  * [11] M. Y. Özkaya, A. Benoit, B. Uçar, J. Herrmann, and Ü. V. Çatalyürek, “A scalable clustering-based task scheduler for homogeneous processors using dag partitioning,” in _2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS)_. IEEE, 2019, pp. 155–165.
  * [12] R. Mayer, C. Mayer, and L. Laich, “The tensorflow partitioning and scheduling problem: it’s the critical path!” in _Proceedings of the 1st Workshop on Distributed Infrastructures for Deep Learning_ , 2017.
  * [13] A. Marchetti-Spaccamela, N. Megow, J. Schlöter, M. Skutella, and L. Stougie, “On the complexity of conditional dag scheduling in multiprocessor systems,” in _2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS)_. IEEE, 2020, pp. 1061–1070.
  * [14] A. Gray, “Getting started with cuda graphs,” developer.nvidia.com/blog/cuda-graphs, 2019-09-05, retrieved on 2020-10-12.
  * [15] T. Gautier, J. V. Lima, N. Maillard, and B. Raffin, “Xkaapi: A runtime system for data-flow task programming on heterogeneous architectures,” in _2013 IEEE 27th International Symposium on Parallel and Distributed Processing_. IEEE, 2013, pp. 1299–1308.
  * [16] C.-H. Hong, I. Spence, and D. S. Nikolopoulos, “Gpu virtualization and scheduling methods: A comprehensive survey,” _ACM Computing Surveys (CSUR)_ , vol. 50, no. 3, pp. 1–37, 2017.
  * [17] V. T. Ravi, M. Becchi, G. Agrawal, and S. Chakradhar, “Supporting gpu sharing in cloud environments with a transparent runtime consolidation framework,” in _Proceedings of the 20th international symposium on High performance distributed computing_ , 2011, pp. 217–228.
  * [18] J. Fumero, M. Papadimitriou, F. S. Zakkak, M. Xekalaki, J. Clarkson, and C. Kotselidis, “Dynamic application reconfiguration on heterogeneous hardware,” in _Proceedings of the 15th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments_ , 2019.
  * [19] J. Clarkson, J. Fumero, M. Papadimitriou, F. S. Zakkak, M. Xekalaki, C. Kotselidis, and M. Luján, “Exploiting high-performance heterogeneous hardware for java programs using graal,” in _Proceedings of the 15th International Conference on Managed Languages & Runtimes_, 2018, pp. 1–13.
  * [20] A. Klöckner, N. Pinto, Y. Lee, B. Catanzaro, P. Ivanov, and A. Fasih, “PyCUDA and PyOpenCL: A Scripting-Based Approach to GPU Run-Time Code Generation,” _Parallel Computing_ , vol. 38, 2012.
  * [21] Y. Wen and M. F. O’Boyle, “Merge or separate? multi-job scheduling for opencl kernels on cpu/gpu platforms,” in _Proceedings of the general purpose GPUs_ , 2017, pp. 22–31.
  * [22] B. Qiao, O. Reiche, J. Teich, and F. Hannig, “Unveiling kernel concurrency in multiresolution filters on gpus with an image processing dsl,” in _Proceedings of the 13th Annual Workshop on General Purpose Processing using Graphics Processing Unit_ , 2020, pp. 11–20.
  * [23] Q. Chen, H. Yang, J. Mars, and L. Tang, “Baymax: Qos awareness and increased utilization for non-preemptive accelerators in warehouse scale computers,” _ACM SIGPLAN Notices_ , vol. 51, no. 4, pp. 681–696, 2016.
  * [24] F. Guo, Y. Li, J. C. Lui, and Y. Xu, “Dcuda: Dynamic gpu scheduling with live migration support,” in _Proceedings of the ACM Symposium on Cloud Computing_ , 2019, pp. 114–125.
  * [25] J. Jung, D. Park, Y. Do, J. Park, and J. Lee, “Overlapping host-to-device copy and computation using hidden unified memory,” in _Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming_ , 2020, pp. 321–335.
  * [26] S. Che, M. Boyer, J. Meng, D. Tarjan, J. W. Sheaffer, S.-H. Lee, and K. Skadron, “Rodinia: A benchmark suite for heterogeneous computing,” in _2009 IEEE international symposium on workload characterization (IISWC)_. Ieee, 2009, pp. 44–54.
  * [27] J. Luitjens, “Faster parallel reductions on kepler,” developer.nvidia.com/blog/faster-parallel-reductions-kepler, 2014-02-14.
  * [28] “Black & scholes option pricing,” docs.nvidia.com/cuda/cuda-samples/index.html#black-scholes-option-pricing, retrieved on 2020-10-12.
  * [29] “Cuda gaussian blur,” github.com/harrytang/cuda-gaussian-blur.
  * [30] J. M. Kleinberg, “Authoritative sources in a hyperlinked environment,” _Journal of the ACM (JACM)_ , vol. 46, no. 5, pp. 604–632, 1999.
  * [31] Y. Liu and B. Schmidt, “Lightspmv: Faster csr-based sparse matrix-vector multiplication on cuda-enabled gpus,” in _2015 IEEE 26th International Conference on Application-specific Systems, Architectures and Processors (ASAP)_. IEEE, 2015, pp. 82–89.


# Different Tastes of Entities:
Investigating Human Label Variation in Named Entity Annotations

Siyao Peng U missing Zihang Sun Umissing Sebastian Loftus Umissing Barbara
Plank U missing
Umissing MaiNLP, Center for Information and Language Processing, LMU Munich,
Germany
missing Munich Center for Machine Learning (MCML), Munich, Germany
{siyaopeng<EMAIL_ADDRESS>{zihang.sun<EMAIL_ADDRESS>
###### Abstract

Named Entity Recognition (NER) is a key information extraction task with a
long-standing tradition. While recent studies address and aim to correct
annotation errors via re-labeling efforts, little is known about the sources
of human label variation, such as text ambiguity, annotation error, or
guideline divergence. This is especially the case for high-quality datasets
and beyond English CoNLL03. This paper studies disagreements in expert-
annotated named entity datasets for three languages: English, Danish, and
Bavarian. We show that text ambiguity and artificial guideline changes are
dominant factors for diverse annotations among high-quality revisions. We
survey student annotations on a subset of difficult entities and substantiate
the feasibility and necessity of manifold annotations for understanding named
entity ambiguities from a distributional perspective.

Different Tastes of Entities:
Investigating Human Label Variation in Named Entity Annotations

Siyao Peng U missing Zihang Sun Umissing Sebastian Loftus Umissing Barbara
Plank U missing Umissing MaiNLP, Center for Information and Language
Processing, LMU Munich, Germany missing Munich Center for Machine Learning
(MCML), Munich, Germany {siyaopeng<EMAIL_ADDRESS>{zihang.sun,
<EMAIL_ADDRESS>Anonymous ACL submission

##  1 Introduction

Named Entity Recognition (NER) is a fundamental task in Natural Language
Processing (NLP) (Yadav and Bethard, 2018). The task involves identifying
named entities (NEs), such as Justin Bieber, UNESCO, and Costa Rica, and
classifying them into semantic types, per(son), org(anization), and
loc(ation), etc. Despite recent successes in achieving 93%+ strict F1 (Rücker
and Akbik, 2023) on the English CoNLL03 benchmark (Tjong Kim Sang and De
Meulder, 2003), recent research has observed that the percentage of noise in
the data, particularly in the test partition, is comparable or even exceeding
the error rates of state-of-the-art (SOTA) models (Wang et al., 2019; Reiss et
al., 2020; Rücker and Akbik, 2023). They each conducted manual corrections or
re-annotations, and model performances on their revised versions were higher
than on the original. However, label variation in NEs, as shown in Table 1,
remains an issue and hinders model performance.

Human label variation (i.e., disagreement) refers to linguistically debatable
cases where multiple labels are acceptable or appropriate in context (Plank et
al., 2014; Jiang and de Marneffe, 2022). Recent studies that examine and
benefit from disagreements among annotators challenge the conventional
assumption of a single gold label. Learning from disagreements provides
further insights into label distributions and preferences among human
annotators (Uma et al., 2021a; Plank, 2022; Fetahu et al., 2023). However,
there remains a gap for disagreement analyses on expert-labeled manifold NEs.

Sentence |  per |  loc |  org |  misc |  o
---|---|---|---|---|---
a. | UK bookmakers [William Hill] … |  |  |  |  |
b. | [ALPINE] SKIING … |  |  |  |  |
c. | … that there is no [God] . |  |  |  |  |

Table 1: Distribution of qualified student annotations on disagreed named
entities in CoNLL03.

This paper presents quantitative and qualitative analyses of annotators’
disagreements on labeling NEs in three Germanic variants: English, Danish, and
Bavarian, in which multiple annotation efforts exist on the same documents.
Unlike earlier studies that look at crowd-sourced data of unreliable quality
(Rodrigues et al., 2014; Lu et al., 2023), we examine disagreements among
expert annotations that went through iterations of published revisions and
contrast them with the usual setting of independent annotators. §2 presents
related work in disagreements and §3 demonstrates our setups. We analyze
entity and label disagreements in §4, sources of disagreements in §5, and a
student-surveyed annotation study in §6. §7 summarizes our work. We release
our annotations and analyses on Github.111https://github.com/mainlp/NER-
disagreements/

##  2 Related Work

Despite disagreements between human judgments in subjective tasks (Prabhakaran
et al., 2021; Davani et al., 2022; Fetahu et al., 2023; Leonardelli et al.,
2023), annotation variation studies in NLP are recently on the rise (Uma et
al., 2021a; Plank, 2022; Fetahu et al., 2023). These include part-of-speech
tagging (Plank et al., 2014), anaphora and pronoun resolution (Poesio and
Artstein, 2005; Poesio et al., 2019; Haber and Poesio, 2020), discourse
relation labeling (Marchal et al., 2022; Pyatkin et al., 2023), word sense
disambiguation (Passonneau et al., 2012; Navigli et al., 2013; Martínez Alonso
et al., 2015), natural language inference (Nie et al., 2020; Jiang and de
Marneffe, 2022; Liu et al., 2023), question answering (Min et al., 2020;
Ferracane et al., 2021), to name a few.

In NER, Rodrigues et al. (2014) crowd-sourced problematic annotations from 47
Turkers on CoNLL03, scoring F1 of 17.60% the lowest and 60% on average against
CoNLL03 annotations, considerably under-performing the 90%+ inter-annotator
agreement among expert annotators and SOTA model performances (Lu et al.,
2023). Recently, Rücker and Akbik (2023) brought forward the newest CoNLL03
correction and thoroughly compared it with previous versions (Tjong Kim Sang
and De Meulder, 2003; Wang et al., 2019; Reiss et al., 2020). However, many
corrections are due to project-dependent guideline alternations and 2.34% of
entities remain unresolved due to ambiguities. Thus, an onlooker assessment of
NE disagreements and label variations is missing, particularly for expert
annotations.

##  3 Datasets & Preprocessing

We analyze label variations in CoNLL03-styled per/loc/org/misc NE annotations
in three Germanic languages: English, Danish, and Bavarian (a Germanic dialect
without standard orthography), where multiple annotation efforts on the same
text documents are (or will be) available. Since the English CoNLL03 (Tjong
Kim Sang and De Meulder, 2003) and Danish DDT (Plank, 2019) texts underwent
iteration(s) of re-annotations or corrections by subsequent scholars, we
conduct a diachronic comparison of the revisions for English and Danish. We
also analyze disagreements on an in-house NE dataset for Bavarian German to
distinguish disagreements among full-fledged corpora from independent
unadjudicated annotations.

### English

The seminal English CoNLL03 dataset (henceforth original, Tjong Kim Sang and
De Meulder 2003) presents the renowned NLP task to label flat and named entity
spans into four major semantic types (per, loc, org, misc) using (B)IO-
encoding. The dataset includes 14.04K, 3.25K, and 3.45K sentences in its
train, dev, and test partitions sourced from Reuters News between 1996-1997.
Despite achieving 93%+ F1 score of the best systems on original, CoNLL03
annotations underwent several revisions (Wang et al., 2019; Reiss et al.,
2020; Rücker and Akbik, 2023).

Wang et al. (2019) (conllpp) manually corrected 186 (5.38%) test sentences.
Reiss et al. (2020) (reiss) used a semi-automatic approach to flag a larger
quantity of error-prone labels (3.18K) in the entire dataset, and manually
corrected 1.32K, including 421 in the test, as well as fixing tokenization and
sentence splitting. They categorize these errors into six types: Tag, Span,
Both, Wrong, Sentence, and Token. Rücker and Akbik (2023) (clean) present the
most comprehensive relabeling effort by correcting 7.0% of all labels and
adding a novel layer for entity linking. Though 5%+ of annotation errors were
fixed compared to original, 2.34% of entities in clean remain ambiguous.

To establish fair comparisons, we manually align tokenization in the test
partitions of original, conllpp, reiss, and clean. These include removing
redundant line breaks, splitting hyphenized compounds, etc. Our alignment
results in 46,738 test tokens across the four versions and 5,629, 5,683,
5,636, 5,725 annotated entities respectively.

### Danish

Plank (2019) annotates NEs on the dev and test partitions of the Danish
Universal Dependencies (DDT, Johannsen et al. 2015). Plank et al. (2020)
(plank) revise annotations, expand to more data and genres, and add
-part/deriv suffixed labels and second-level nesting. Hvingelby et al. (2020)
(hvingelby) re-annotate the dev and test sets of Plank (2019) by adding POS-
marked proper nouns as NEs, resulting in 0.75 and 3.0 times more org and misc
NEs, such as nationalities and derived adjectives. We focus on the test
partition (10,023 tokens) and compare hvingelby to the more recent plank,
removing nesting and -part/deriv entities for cross-lingual analogy, leading
to 564 and 531 NEs in hvingelby and plank.

### Bavarian

We additionally analyze the test partition of an in-house Bavarian NE dataset
with 12K tokens and 400 entities on Wikipedia and Twitter (X) annotated in
2023. Compared to the more established and iteratively revised English and
Danish datasets, our Bavarian corpus represents the more common scenario of
disagreements between two independent and unadjudicated annotations.

##  4 Entity-level Disagreements

Given our manually aligned tokenization across datasets, we modify Reiss et
al. (2020)’s six error types into four entity-level disagreement types:

  * •

Tag: same span selection, but different assigned tags, e.g., [a b]loc vs. [a
b]org;

  * •

Span: different overlapping spans but the same tag, e.g., [a b]loc vs. [a]loc
b;

  * •

Both: overlapping spans with different tags, e.g., [a b]loc vs. [a]org b;

  * •

Missing: one annotator misses the entity completely, e.g., [a b]loc vs. a b.

Figure 1: Proportions of entity-level disagreements in English original-clean,
conllpp-clean, reiss-clean, Danish plank-hvingelby, and Bavarian.

Figure 1 presents the frequencies and proportions of entity-level
disagreements in five paired comparisons: English original-clean, conllpp-
clean, reiss-clean, Danish plank-hvingelby, and between two Bavarian
annotators. Tag disagreements contribute to most cases among repeatedly
developed English corpora. On the other hand, Danish and Bavarian contain more
Missing disagreements. Nevertheless, combining Tag and Missing accounts for
85%+ of disagreements in all comparisons across three languages. That is,
entity tagging remains a bigger issue compared to span selection.

Tag and Missing disagreements are comparable in that both concern tagging the
same entity span with different labels: the former with two different entity
types (i.e., two non-o labels), and the latter with one entity type (a non-o
label) and an o. Figure 2 displays the proportions of the top 5 disagreed
label pairs in Tag and Missing disagreements across the five comparison
scenarios (see Appendix 0.A for a full list of label pairs). loc-org, o-misc
and org-misc are the most frequently disagreed label pairs in English
comparisons, totaling 70%+ label disagreements. On the other hand, most (80%+)
of Danish label disagreements concern misc, whereas o-related (i.e., Missing)
disagreements donate the majority (70%+) to Bavarian. To understand which
factors trigger these label disagreements, §5 qualitatively analyzes the
sources of human label variations in three languages.

Figure 2: Proportions of top 5 label pairs in Tag and Missing disagreements in
English, Danish, and Bavarian.

##  5 Sources of Disagreements

### Taxonomy

We attribute NE label variations to three sources (Aroyo and Welty, 2015;
Jiang and de Marneffe, 2022): 1) text ambiguity for uncertainties in the
sentence meaning, 2) guideline update where NE type definitions vary across
different guideline versions, and 3) annotator error. Text ambiguity could be
caused by different interpretations with or without enough context that
hinders pinpointing a definitive reference. Guideline update occurs when one
annotation version is incoherent with another guideline. This is dominant in
our analyses since annotation projects consist of iterations of guidelines and
annotation revisions. For instance, whether proper noun-derived adjectives,
e.g., [ALPINE] in Table 1, should be loc, misc, or not an entity (i.e., o);
whether polysemous loc/org entities are labeled loc or org depending on
context, or always as misc. The last category, annotator error, refers to
annotations that differ from a single deterministic ground truth. Closer
inspections could fix annotators’ attention slip errors, whereas special
cultural knowledge is needed for resolving knowledge gap disagreements. We
manually annotate a small sample of disagreements in three languages using
these source categories to separate guideline changes and textual ambiguities
from annotators’ mistakes.

### Setup

For English, we sample 200 disagreed test entities between the original and
the most recent clean annotation. Since the Danish plank- hvingelby
comparisons and the Bavarian double annotations have much smaller test sets,
we sample all test disagreements in the two languages, 118 entities in Danish
and 64 in Bavarian. Each language sample is assessed by one computational
linguist who speaks that language. Table 2 presents the source of disagreement
results.

Additionally, we measure inter-annotator agreement (IAA) on source classes
between two assessors222We use “assessors” to refer to our source of
disagreement coders and differentiate from “annotators” of the NE datasets. on
50 ambiguous English original-clean test entities and achieve 61.73% Cohen’s
kappa. Assessors find the hardest differentiating whether the lack of
contextual information resulted from annotators’ personal knowledge
backgrounds (annotator error) or the settings behind text segments (text
ambiguity). Even though surrounding sentences are provided, NE annotators tend
to focus on the nearer context for NE tagging.

Source types | English | Danish | Bavarian
---|---|---|---
text ambiguity | 19 $|$ 9.5% | 7 $|$ 6.0% | 10 $|$ 15.6%
guideline update | 160 $|$ 80.0% | 62 $|$ 52.5% | 11 $|$ 17.2%
annotator error | 21 $|$ 10.5% | 49 $|$ 41.5% | 43 $|$ 67.2%
Total | 200 $|$ 100.0% | 118 $|$ 100.0% | 64 $|$ 100.0%

Table 2: Sources of label disagreements and their distributions in English,
Danish, and Bavarian samples.

### English

In the original-clean comparison, most (80.0%) of disagreements stem from
differences in guideline update. To disambiguate inconsistent cases in
original, clean updated the guideline to be less context-dependent: 1) org
instead of loc for national sports teams as well as public facilities, even
for the flight to [Atlanta]org; 2) misc is used for more abstract institutions
and adjectival affiliations e.g., [Czech]misc politics; 3) instead of further
correcting tokenizations and splitting hyphenated compounds, they assign
labels that are relevant to part of the compound to the entirety, e.g.,
[German-born]misc. Aside from guideline update, ambiguities occur for
religious deities, such as whether [Allah] or [God] should be per, misc or o
(see Table 1). Previous automatic conversions from IO-encodings in original to
BIO in clean also caused disagreements since it is hard to tell apart if a
sequence of i-tags is one entity or multiple, e.g., [Spanish]misc [Super
Cup]misc or [Spanish Super Cup]misc.

### Danish

Akin to the English analysis, we found that large parts (52.5%) of the
ambiguous cases in Danish stem from guideline updates, e.g., frequently
mentioned ferry routes are labeled loc in hvingelby but misc in plank.
Besides, we found 41.5% of disagreements are annotator errors, and the
majority are org-misc disagreements and concern a single hyphen-joint token
with two sports clubs, e.g., [Vejle-Ikast]. This points out a disadvantage of
the current cross-lingual comparable analysis — compounding morphology
prevails in Danish and Bavarian, and removing -part/deriv labels leads to
information loss.

### Bavarian

We present the less developed but more common scenario of disagreements
between two unadjudicated annotations in Bavarian. Though achieving 85%+ Span
IAA, annotator error (67.2%) remains the highest source of disagreements.
Apart from local entities, e.g., [Feucht]loc (a small town in Bavaria), that
require geographical knowledge or detailed search, many of these annotator
errors classified based on the Bavarian guideline are indeed acceptable under
certain versions of the English CoNLL guidelines. For example, when [Edeka] (a
supermarket chain) functions as a destination, the disagreement between loc-
org is classified as annotator error in Bavarian, but would rather be a
guideline update in English.

##  6 Surveying Student Annotations

Though NE guidelines can be meticulously different from each other, the
underlying concepts of per, loc, org are cognitively straightforward. To
inspect the distribution of multiple interpretations, we follow Liu et al.
(2023) to survey annotations from 27 bachelor and master students in
computational linguistics at LMU Munich. We gave them a 7-minute introduction
to NEs, walked through the CoNLL03
guideline333www.cnts.ua.ac.be/conll2003/ner/annotation.txt, and showed some
examples of type ambiguities in NE annotations. Students were instructed in
the classroom to annotate entity types in English and Bavarian selected from
difficult examples in §5.444Students acknowledge that their annotations could
be used for research purposes. We further sample 10 representative English
CoNLL entities for the qualitative evaluation below.555The full English and
Bavarian student-surveyed annotations are available on GitHub. To ensure the
quality of student-surveyed annotations, we only keep an annotation if 80%+ of
entity labels match any of the four CoNLL annotations. Table 1 demonstrates
the distribution of 14 qualified student annotations on three examples (see
Appendix 0.B for the ten representative English CoNLL entities).

Results demonstrate that label variation across annotation projects are also
prevalent in the student-surveyed annotations. On one side, even with a brief
training, students were able to disambiguate the contextual interpretations
between [the away team]org and [the home team]loc in [LA CLIPPERS]org AT [NEW
YORK]loc. Our participants also recognize the collectiveness of [White
House]org, [Australia]org, etc., and the fixedness of [EST]misc (Eastern
Standard Time). On the other hand, knowledge gap or insufficient context
contribute to the high variance of [William Hill], whether it refers to [the
businessman]per or [the gambling bookstore he created]org. Annotators also
diverge in marginal cases: whether [God] is per or misc and whether nominal
derivatives ALPINE and Fascist are NEs.

##  7 Conclusion

This paper examines named entity disagreements across expert annotations and
contrasts them with the more common setting of individual annotations. We
demonstrate that human label variation, e.g., loc-org and org-misc, contribute
to most English, Danish, and Bavarian disagreements. We also discover that
guideline updates and text ambiguities are leading sources of disagreements in
established English and German datasets, whereas annotator errors remain the
dominant cause for the new Bavarian corpus. Lastly, we survey student
annotations and encourage more researchers to explore NE label variations to
narrow the gap to model performance.

Though modeling NER from label variation is out of the scope of this paper, we
embrace the prospect of learning from disagreements (Uma et al., 2021b).
Particularly, we look forward to conducting annotations on a much larger scale
in terms of both the number of participants and annotated instances to provide
more statistically meaningful NE distributions for NER models. Future work
also includes separating valid label variations from true annotation mistakes
by leveraging Automatic Error Detection (AED) methods (Klie et al., 2023;
Weber and Plank, 2023). We hope tackling NER through label variations can
remedy the conflicts among versions of annotation guidelines.

## Acknowledgements

We would like to thank Verena Blaschke for giving feedback on earlier drafts
of this paper. This project is supported by ERC Consolidator Grant DIALECT
101043235.

## References

  * Aroyo and Welty (2015) Lora Aroyo and Chris Welty. 2015.  Truth Is a Lie: Crowd Truth and the Seven Myths of Human Annotation.  _AI Magazine_ , 36(1):15–24.  Number: 1.
  * Davani et al. (2022) Aida Mostafazadeh Davani, Mark Díaz, and Vinodkumar Prabhakaran. 2022.  Dealing with Disagreements: Looking Beyond the Majority Vote in Subjective Annotations.  _Transactions of the Association for Computational Linguistics_ , 10:92–110.
  * Ferracane et al. (2021) Elisa Ferracane, Greg Durrett, Junyi Jessy Li, and Katrin Erk. 2021.  Did they answer? Subjective acts and intents in conversational discourse.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 1626–1644, Online. Association for Computational Linguistics.
  * Fetahu et al. (2023) Besnik Fetahu, Sudipta Kar, Zhiyu Chen, Oleg Rokhlenko, and Shervin Malmasi. 2023.  SemEval-2023 Task 2: Fine-grained Multilingual Named Entity Recognition (MultiCoNER 2).  In _Proceedings of the 17th International Workshop on Semantic Evaluation (SemEval-2023)_ , pages 2247–2265, Toronto, Canada. Association for Computational Linguistics.
  * Haber and Poesio (2020) Janosch Haber and Massimo Poesio. 2020.  Classification of low-agreement Pronouns through Collaborative Dialogue: A Proof of Concept.
  * Hvingelby et al. (2020) Rasmus Hvingelby, Amalie Brogaard Pauli, Maria Barrett, Christina Rosted, Lasse Malm Lidegaard, and Anders Søgaard. 2020.  DaNE: A Named Entity Resource for Danish.  In _Proceedings of the Twelfth Language Resources and Evaluation Conference_ , pages 4597–4604, Marseille, France. European Language Resources Association.
  * Jiang and de Marneffe (2022) Nan-Jiang Jiang and Marie-Catherine de Marneffe. 2022.  Investigating Reasons for Disagreement in Natural Language Inference.  _Transactions of the Association for Computational Linguistics_ , 10:1357–1374.  Place: Cambridge, MA Publisher: MIT Press.
  * Johannsen et al. (2015) Anders Johannsen, Héctor Martínez Alonso, and Barbara Plank. 2015.  Universal dependencies for danish.  In _International Workshop on Treebanks and Linguistic Theories (TLT14)_ , pages 157–167.
  * Klie et al. (2023) Jan-Christoph Klie, Bonnie Webber, and Iryna Gurevych. 2023.  Annotation Error Detection: Analyzing the Past and Present for a More Coherent Future.  _Computational Linguistics_ , 49(1):157–198.
  * Leonardelli et al. (2023) Elisa Leonardelli, Gavin Abercrombie, Dina Almanea, Valerio Basile, Tommaso Fornaciari, Barbara Plank, Verena Rieser, Alexandra Uma, and Massimo Poesio. 2023.  SemEval-2023 Task 11: Learning with Disagreements (LeWiDi).  In _Proceedings of the 17th International Workshop on Semantic Evaluation (SemEval-2023)_ , pages 2304–2318, Toronto, Canada. Association for Computational Linguistics.
  * Liu et al. (2023) Alisa Liu, Zhaofeng Wu, Julian Michael, Alane Suhr, Peter West, Alexander Koller, Swabha Swayamdipta, Noah Smith, and Yejin Choi. 2023.  We’re Afraid Language Models Aren’t Modeling Ambiguity.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_ , pages 790–807, Singapore. Association for Computational Linguistics.
  * Lu et al. (2023) Sheng Lu, Irina Bigoulaeva, Rachneet Sachdeva, Harish Tayyar Madabushi, and Iryna Gurevych. 2023.  Are Emergent Abilities in Large Language Models just In-Context Learning? ArXiv:2309.01809 [cs].
  * Marchal et al. (2022) Marian Marchal, Merel Scholman, Frances Yung, and Vera Demberg. 2022.  Establishing Annotation Quality in Multi-label Annotations.  In _Proceedings of the 29th International Conference on Computational Linguistics_ , pages 3659–3668, Gyeongju, Republic of Korea. International Committee on Computational Linguistics.
  * Martínez Alonso et al. (2015) Héctor Martínez Alonso, Anders Johannsen, Oier Lopez de Lacalle, and Eneko Agirre. 2015.  Predicting word sense annotation agreement.  In _Proceedings of the First Workshop on Linking Computational Models of Lexical, Sentential and Discourse-level Semantics_ , pages 89–94, Lisbon, Portugal. Association for Computational Linguistics.
  * Min et al. (2020) Sewon Min, Julian Michael, Hannaneh Hajishirzi, and Luke Zettlemoyer. 2020.  AmbigQA: Answering Ambiguous Open-domain Questions.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 5783–5797, Online. Association for Computational Linguistics.
  * Navigli et al. (2013) Roberto Navigli, David Jurgens, and Daniele Vannella. 2013.  SemEval-2013 Task 12: Multilingual Word Sense Disambiguation.  In _Second Joint Conference on Lexical and Computational Semantics (*SEM), Volume 2: Proceedings of the Seventh International Workshop on Semantic Evaluation (SemEval 2013)_ , pages 222–231, Atlanta, Georgia, USA. Association for Computational Linguistics.
  * Nie et al. (2020) Yixin Nie, Xiang Zhou, and Mohit Bansal. 2020.  What Can We Learn from Collective Human Opinions on Natural Language Inference Data? In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 9131–9143, Online. Association for Computational Linguistics.
  * Passonneau et al. (2012) Rebecca J. Passonneau, Vikas Bhardwaj, Ansaf Salleb-Aouissi, and Nancy Ide. 2012.  Multiplicity and word sense: evaluating and learning from multiply labeled word sense annotations.  _Language Resources and Evaluation_ , 46(2):219–252.
  * Plank (2019) Barbara Plank. 2019.  Neural Cross-Lingual Transfer and Limited Annotated Data for Named Entity Recognition in Danish.  In _Proceedings of the 22nd Nordic Conference on Computational Linguistics_ , pages 370–375, Turku, Finland. Linköping University Electronic Press.
  * Plank (2022) Barbara Plank. 2022.  The “Problem” of Human Label Variation: On Ground Truth in Data, Modeling and Evaluation.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 10671–10682, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Plank et al. (2014) Barbara Plank, Dirk Hovy, and Anders Søgaard. 2014.  Linguistically debatable or just plain wrong? In _Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 507–511, Baltimore, Maryland. Association for Computational Linguistics.
  * Plank et al. (2020) Barbara Plank, Kristian Nørgaard Jensen, and Rob van der Goot. 2020.  DaN+: Danish Nested Named Entities and Lexical Normalization.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 6649–6662, Barcelona, Spain (Online). International Committee on Computational Linguistics.
  * Poesio and Artstein (2005) Massimo Poesio and Ron Artstein. 2005.  The Reliability of Anaphoric Annotation, Reconsidered: Taking Ambiguity into Account.  In _Proceedings of the Workshop on Frontiers in Corpus Annotations II: Pie in the Sky_ , pages 76–83, Ann Arbor, Michigan. Association for Computational Linguistics.
  * Poesio et al. (2019) Massimo Poesio, Jon Chamberlain, Silviu Paun, Juntao Yu, Alexandra Uma, and Udo Kruschwitz. 2019.  A Crowdsourced Corpus of Multiple Judgments and Disagreement on Anaphoric Interpretation.  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 1778–1789, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Prabhakaran et al. (2021) Vinodkumar Prabhakaran, Aida Mostafazadeh Davani, and Mark Diaz. 2021.  On Releasing Annotator-Level Labels and Information in Datasets.  In _Proceedings of the Joint 15th Linguistic Annotation Workshop (LAW) and 3rd Designing Meaning Representations (DMR) Workshop_ , pages 133–138, Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Pyatkin et al. (2023) Valentina Pyatkin, Frances Yung, Merel C. J. Scholman, Reut Tsarfaty, Ido Dagan, and Vera Demberg. 2023.  Design Choices for Crowdsourcing Implicit Discourse Relations: Revealing the Biases Introduced by Task Design.  ArXiv:2304.00815 [cs].
  * Reiss et al. (2020) Frederick Reiss, Hong Xu, Bryan Cutler, Karthik Muthuraman, and Zachary Eichenberger. 2020.  Identifying Incorrect Labels in the CoNLL-2003 Corpus.  In _Proceedings of the 24th Conference on Computational Natural Language Learning_ , pages 215–226, Online. Association for Computational Linguistics.
  * Rodrigues et al. (2014) Filipe Rodrigues, Francisco Pereira, and Bernardete Ribeiro. 2014.  Sequence labeling with multiple annotators.  _Machine Learning_ , 95(2):165–181.
  * Rücker and Akbik (2023) Susanna Rücker and Alan Akbik. 2023.  CleanCoNLL: A Nearly Noise-Free Named Entity Recognition Dataset.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_ , pages 8628–8645, Singapore. Association for Computational Linguistics.
  * Tjong Kim Sang and De Meulder (2003) Erik F. Tjong Kim Sang and Fien De Meulder. 2003.  Introduction to the CoNLL-2003 Shared Task: Language-Independent Named Entity Recognition.  In _Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL 2003_ , pages 142–147.
  * Uma et al. (2021a) Alexandra Uma, Tommaso Fornaciari, Anca Dumitrache, Tristan Miller, Jon Chamberlain, Barbara Plank, Edwin Simpson, and Massimo Poesio. 2021a.  SemEval-2021 Task 12: Learning with Disagreements.  In _Proceedings of the 15th International Workshop on Semantic Evaluation (SemEval-2021)_ , pages 338–347, Online. Association for Computational Linguistics.
  * Uma et al. (2021b) Alexandra N. Uma, Tommaso Fornaciari, Dirk Hovy, Silviu Paun, Barbara Plank, and Massimo Poesio. 2021b.  Learning from Disagreement: A Survey.  _Journal of Artificial Intelligence Research_ , 72:1385–1470.
  * Wang et al. (2019) Zihan Wang, Jingbo Shang, Liyuan Liu, Lihao Lu, Jiacheng Liu, and Jiawei Han. 2019.  CrossWeigh: Training Named Entity Tagger from Imperfect Annotations.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 5154–5163, Hong Kong, China. Association for Computational Linguistics.
  * Weber and Plank (2023) Leon Weber and Barbara Plank. 2023.  ActiveAED: A Human in the Loop Improves Annotation Error Detection.  In _Findings of the Association for Computational Linguistics: ACL 2023_ , pages 8834–8845, Toronto, Canada. Association for Computational Linguistics.
  * Yadav and Bethard (2018) Vikas Yadav and Steven Bethard. 2018.  A Survey on Recent Advances in Named Entity Recognition from Deep Learning models.  In _Proceedings of the 27th International Conference on Computational Linguistics_ , pages 2145–2158, Santa Fe, New Mexico, USA. Association for Computational Linguistics.

##  Appendix 0.A Proportions of Disagreed Label Pairs

Figure 3: Proportions of label pairs (full) in Tag and Missing disagreements
in English, Danish, and Bavarian.

##  Appendix 0.B Student Surveyed NE Annotations

Sentence | per | loc | org | misc | o | abstained
---|---|---|---|---|---|---
[ALPINE] SKIING |  |  | 6
---
clean
| 3 |  | 4
---
original
conllpp
reiss
1
[LA CLIPPERS] AT NEW YORK |  |  |  | 13
---
original
conllpp
reiss
clean
|  | 1
LA CLIPPERS AT [NEW YORK] |  |  | 14
---
original
conllpp
reiss
| 0
---
clean
|  |
|  [White House] spokesman Mike McCurry said Clinton plans
---
to have regular news conferences during his second term .
|  | 2
---
original
conllpp
reiss
| 11
---
clean
1 |  |
|  UK bookmakers [William Hill]666William Hill is a British gambling company
said on Friday they
---
have lengthened the odds of a Conservative victory .
| 5
---
original
conllpp
reiss
|  | 9
---
clean
|  |
| The man who kicked [Australia] to defeat with a last-ditch
---
drop-goal in the World Cup quarter-final in Cape Town .
|  | 5
---
original
conllpp
reiss
| 9
---
clean
|  |
| The years I spent as (soccer team) manager of
---
the [Republic of Ireland] were the best years of my life .
|  | 4
---
original
conllpp
reiss
| 9
---
clean
1 |  |
I bear witness that there is no [God] . |  | 10
---
original
conllpp
reiss
|  |  | 4
---
clean
|
|  The granddaughter of Italy’s [Fascist]777Fascism is a far-right,
authoritarian, ultranationalist political ideology and movement dictator
Benito Mussolini
---
|  | 3 |  | 3
---
clean
| 8
---
original
conllpp
reiss
| at about 3 A.M. local time / 1:30 A.M. [EST]
---
|  |  |  | 10
---
clean
| 2
---
original
conllpp
reiss
2

Table 3: 14 classroom surveyed and qualified annotations on difficult
disagreement cases in CoNLL03 test.