# DeepMerge: Learning to Merge Programs

Elizabeth Dinella, Todd Mytkowicz, Alexey Svyatkovskiy, Christian Bird, Mayur
Naik, Shuvendu Lahiri Elizabeth Dinella is with the University of
Pennsylvania, Philadelphia, Pennsylvania, USA. E-mail<EMAIL_ADDRESS>Elizabeth Dinella performed this work while employed at Microsoft Research.
Todd Mytkowicz is with Microsoft Research, Redmond, Washington, USA. E-mail:
<EMAIL_ADDRESS>Alexey Svyatkovskiy is with Microsoft, Redmond,
Washington, USA. E-mail<EMAIL_ADDRESS>Christian Bird is with
Microsoft Research, Redmond, Washington, USA. E-mail<EMAIL_ADDRESS>Mayur Naik is with the University of Pennsylvania, Philadelphia, Pennsylvania,
USA. E-mail<EMAIL_ADDRESS>Shuvendu Lahiri is with Microsoft Research,
Redmond, Washington, USA. E-mail<EMAIL_ADDRESS>
###### Abstract

In collaborative software development, program merging is the mechanism to
integrate changes from multiple programmers. Merge algorithms in modern
version control systems report a conflict when changes interfere textually.
Merge conflicts require manual intervention and frequently stall modern
continuous integration pipelines. Prior work found that, although costly, a
large majority of resolutions involve re-arranging text without writing any
new code. Inspired by this observation we propose the first data-driven
approach to resolve merge conflicts with a machine learning model. We realize
our approach in a tool DeepMerge that uses a novel combination of (i) an edit-
aware embedding of merge inputs and (ii) a variation of pointer networks, to
construct resolutions from input segments. We also propose an algorithm to
localize manual resolutions in a resolved file and employ it to curate a
ground-truth dataset comprising 8,719 non-trivial resolutions in JavaScript
programs. Our evaluation shows that, on a held out test set, DeepMerge can
predict correct resolutions for 37% of non-trivial merges, compared to only 4%
by a state-of-the-art semistructured merge technique. Furthermore, on the
subset of merges with upto 3 lines (comprising 24% of the total dataset),
DeepMerge can predict correct resolutions with 78% accuracy.

##  1 Introduction

In collaborative software development settings, version control systems such
as “git” are commonplace. Such version control systems allow developers to
simultaneously edit code through features called branches. Branches are a
growing trend in version control as they allow developers to work in their own
isolated workspace, making changes independently, and only integrating their
work into the main line of development when it is complete. Integrating these
changes frequently involves merging multiple copies of the source code. In
fact, according to a large-scale empirical study of Java projects on GitHub
[11], nearly 12% of all commits are related to a merge.

To integrate changes by multiple developers across branches, version control
systems utilize merge algorithms. Textual three-way file merge (e.g. present
in “git merge”) is the prevailing merge algorithm. As the name suggests,
three-way merge takes three files as input: the common base file
$\mathcal{O}$, and its corresponding modified files, $\mathcal{A}$ and
$\mathcal{B}$. The algorithm either:

  1. 1.

declares a “conflict” if the two changes interfere with each other, or

  2. 2.

provides a merged file $\mathcal{M}$ that incorporates changes made in
$\mathcal{A}$ and $\mathcal{B}$.

Under the hood, three-way merge typically employs the diff3 algorithm, which
performs an unstructured (line-based) merge [27]. Intuitively, the algorithm
aligns the two-way diffs of $\mathcal{A}$ (resp. $\mathcal{B}$) over the
common base $\mathcal{O}$ into a sequence of diff slots. At each slot, a
change from either $\mathcal{A}$ or $\mathcal{B}$ is incorporated. If both
programs change a common slot, a merge conflict is produced, and requires
manual resolution of the conflicting modifications.

|  Base $\mathcal{O}$ |  Variant $\mathcal{A}$ |  Variant $\mathcal{B}$ | Resolution? |
---|---|---|---|---|---
| (base.js) | (a.js) | (b.js) | (m.js) |
(1). |  y = 42; |  x = 1; |  y = 42; |  x = 1; |
|  y = 42; |  z = 43; |  y = 42; |
|  |  |  z = 43; |
(2). |  y = 42; |  x = 1; |  z = 43; |  CONFLICT |
|  y = 42; |  y = 42; |  |
Figure 1: Two examples of unstructured merges.

Figure 1 shows two simple code snippets to illustrate examples of three-way
merge inputs and outputs. The figure shows the base program file $\mathcal{O}$
along with the two variants $\mathcal{A}$ and $\mathcal{B}$. Example (1) shows
a case where diff3 successfully provides a merged file $\mathcal{M}$
incorporating changes made in both $\mathcal{A}$ and $\mathcal{B}$. On the
other hand, Example (2) shows a case where diff3 declares a conflict because
two independent changes (updates to x and z) occur in the same diff slot.

When diff3 declares a conflict, a developer must intervene. Consequently,
merge conflicts are consistently ranked as one of the most taxing issues in
collaborative, open-source software development, ”especially for seemingly
less experienced developers” [13]. Merge conflicts impact developer
productivity, resulting in costly broken builds that stall the continuous
integration (CI) pipelines for several hours to days. The fraction of merge
conflicts as a percentage of merges range from 10% — 20% for most
collaborative projects. In several large projects, merge conflicts account for
up to 50% of merges (see [11] for details of prior studies).

Merge conflicts often arise due to the unstructured diff3 algorithm that
simply checks if two changes occur in the same diff slot. For instance, the
changes in Example (2), although textually conflicting, do not interfere
semantically. This insight has inspired research to incorporate program
structure and semantics while performing a merge. Structured merge approaches
[3, 21, 32] and their variants treat merge inputs as abstract syntax trees
(ASTs), and use tree-structured merge algorithms. However, such approaches
still yield a conflict on merges such as Example (2) above, as they do not
model program semantics and cannot safely reorder statements that have side
effects.111We ran jdime [21] in structured mode on this example after
translating the code snippet to Java. To make matters worse, the gains from
structured approaches hardly transfer to dynamic languages, namely JavaScript
[32], due to the absence of static types. Semantics-based approaches [37, 28]
can, in theory, employ program analysis and verifiers to detect and synthesize
the resolutions. However, there are no semantics-based tools for synthesizing
merges for any real-world programming language, reflecting the intractable
nature of the problem. Current automatic approaches fall short, suggesting
that merge conflict resolution is a non-trivial problem.

This paper takes a fresh data-driven approach to the problem of resolving
unstructured merge conflicts. Inspired by the abundance of data in open-source
projects, the paper demonstrates how to collect a dataset of merge conflicts
and resolutions.

This dataset drives the paper’s key insight: a vast majority (80%) of
resolutions do not introduce new lines. Instead, they consist of (potentially
rearranged) lines from the conflicting region. This observation is confirmed
by a prior independent large-scale study of Java projects from GitHub [13], in
which 87% of resolutions are comprised exclusively from lines in the input. In
other words, a typical resolution consists of re-arranging conflicting lines
without writing any new code. Our observation naturally begs the question: Are
there latent patterns of rearrangement? Can these patterns be learned?

This paper investigates the potential for learning latent patterns of
rearrangement. Effectively, this boils down to the question:

> Can we learn to synthesize merge conflict resolutions?

Specifically, the paper frames merging as a sequence-to-sequence task akin to
machine translation.

{ unchanged lines (prefix) }
---
<<<<<<
{ lines edited by $\mathcal{A}$ }
|||||||
{ affected lines of base $\mathcal{O}$ }
=======
{ lines edited by $\mathcal{B}$ }
>>>>>>
{ unchanged lines (suffix) }
(a) Format of a conflict.

      <<<<<< a.js
      x = 1;
      |||||| base.js
      =======
      z = 43;
      >>>>>> b.js
      y = 42;

(b) Instance of a conflict.

Figure 2: Conflict format and an instance reported by diff3 on Example (2)
from Figure 1.

To formulate program merging as a sequence-to-sequence problem, the paper
considers the text of programs $\mathcal{A}$, $\mathcal{B}$, and $\mathcal{O}$
as the input sequence, and the text of the resolved program $\mathcal{M}$ as
the output sequence. However, this seemingly simple formulation does not come
without challenges. Section 5 demonstrates an out of the box sequence-to-
sequence model trained on merge conflicts yields very low accuracy. In order
to effectively learn a merge algorithm, one must:

  1. 1.

represent merge inputs in a concise yet sufficiently expressive sequence;

  2. 2.

create a mechanism to output tokens at the line granularity; and

  3. 3.

localize the merge conflicts and the resolutions in a given file.

To represent the input in a concise yet expressive embedding, the paper shows
how to construct an edit aware sequence to be consumed by DeepMerge. These
edits are provided in the format of diff3 which is depicted in Figure 2(a) in
the portion between markers “`<<<<<<<`“ and “`>>>>>>>`“. The input embedding
is extracted from parsing the conflicting markers and represents
$\mathcal{A}$’s and $\mathcal{B}$’s edits over the common base $\mathcal{O}$.

To represent the output at the line granularity, DeepMerge’s design is a form
of a pointer network [34]. As such, DeepMerge constructs resolutions by
copying input lines, rather than learning to generate them token by token.
Guided by our key insight that a large majority of resolutions are entirely
comprised of lines from the input, such an output vocabulary is sufficiently
expressive.

Lastly, the paper shows how to localize merge conflicts and the corresponding
user resolutions in a given file. This is necessary as our approach
exclusively aims to resolve locations in which diff3 has declared a conflict.
As such, our algorithm only needs to generate the conflict resolution and not
the entire merged file. Thus, to extract ground truth, we must localize the
resolution for a given conflict in a resolved file. Localizing such a
resolution region unambiguously is a non-trivial task. The presence of
extraneous changes unrelated to conflict resolution makes resolution
localization challenging. The paper presents the first algorithm to localize
the resolution region for a conflict. This ground truth is essential for
training such a deep learning model.

The paper demonstrates an instance of DeepMerge trained to resolve
unstructured merge conflicts in JavaScript programs. Besides its popularity,
JavaScript is notorious for its rich dynamic features, and lacks tooling
support. Existing structured approaches struggle with JavaScript [32],
providing a strong motivation for a technique suitable for dynamic languages.
The paper contributes a real-world dataset of 8,719 merge tuples that require
non-trivial resolutions from nearly twenty thousand repositories in GitHub.
Our evaluation shows that, on a held out test set, DeepMerge can predict
correct resolutions for 37% of non-trivial merges. DeepMerge’s accuracy is a
9x improvement over a recent semistructured approach [32], evaluated on the
same dataset. Furthermore, on the subset of merges with upto 3 lines
(comprising 24% of the total dataset), DeepMerge can predict correct
resolutions with 78% accuracy.

_Contributions._ In summary, this paper:

  1. 1.

is the first to define merge conflict resolution as a machine learning problem
and identify a set of challenges for encoding it as a sequence-to-sequence
supervised learning problem (§ 2).

  2. 2.

presents a data-driven merge tool DeepMerge that uses edit-aware embedding to
represent merge inputs and a variation of pointer networks to construct the
resolved program (§ 3).

  3. 3.

derives a real-world merge datasetfor supervised learning by proposing an
algorithm for localizing resolution regions (§ 4).

  4. 4.

performs an extensive evaluation of DeepMerge on merge conflicts in real-world
JavaScript programs. And, demonstrates that it can correctly resolve a
significant fraction of unstructured merge conflicts with high precision and
9x higher accuracy than a structured approach.

##  2 Data-Driven Merge

We formulate program merging as a sequence-to-sequence supervised learning
problem and discuss the challenges we must address in solving the resulting
formulation.

###  2.1 Problem Formulation

A merge consists of a 4-tuple of programs
$(\mathcal{A},\mathcal{B},\mathcal{O},\mathcal{M})$ where $\mathcal{A}$ and
$\mathcal{B}$ are both derived from a common $\mathcal{O}$, and $\mathcal{M}$
is the developer resolved program.

A merge may consist of one or more regions. We define a merge tuple
(($A,B,O$), $R$) such that $A$, $B$, $O$ are (sub) programs that correspond to
regions in $\mathcal{A}$, $\mathcal{B}$, and $\mathcal{O}$, respectively, and
$R$ denotes the result of merging those regions. Although we refer to
$(A,B,O,R)$ as a merge tuple, we assume that the tuples also implicitly
contain the programs that they came from as additional contexts (namely
$\mathcal{A},\mathcal{B},\mathcal{O},\mathcal{M}$).

######  Definition 1 (Data-driven Merge)

Given a dataset of $M$ merge tuples,

$D=\\{(A^{i},B^{i},O^{i},R^{i})\\}_{i=1}^{M}$

a data-driven merge algorithm merge is a function that maximizes:

$\sum_{i=1}^{M}\textit{merge}(A^{i},B^{i},O^{i})=R^{i}$

treating Boolean outcomes of the equality comparison as integer constants 1
(for ${\tt true}$) and 0 (for ${\tt false}$).

In other words, merge aims to maximize the number of merges from $D$. Rather
than constraining merge to exactly satisfy all merge tuples in $D$, we relax
the objective to maximization. A perfectly satisfying merge function may not
exist in the presence of a real-world noisy dataset $D$. For instance, there
may be $(A^{i},B^{i},O^{i},R^{i})\in D$ and $(A^{j},B^{j},O^{j},R^{j})\in D$
for $i\neq j$, $A^{i}=A^{j}$, $B^{i}=B^{j}$, $O^{i}=O^{j}$ but $R^{i}\neq
R^{j}$. In other words, two merge tuples consist of the same edits but
different resolutions.

Example 1. Figure 3(a)(a) shows a merge instance that we will use as our
running example throughout. This instance is formulated in our setting as the
merge tuple $(A,B,O,R)$ depicted in Figure 3(a)(b). $R$ contains only lines
occurring in the input. The two lines in $R$ correspond to the first line of
$B$ and the third line of $A$. For this example, the $R$ also incorporates the
intents from both $A$ and $B$ intuitively, assuming b does not appear in the
rest of the programs. $\Box$

<<<<<< a.js

    let b = x + 5.7
    var y = floor(b)
    console.log(y)

|||||| base.js

    var b = 5.7
    var y = floor(b)

======

    var y = floor(x + 5.7)

>>>>>> b.js

(a) A merge instance. $A$ = |  | let b = x + 5.7
---
var y = floor(b)
console.log(y)
$O$ = |  | var b = 5.7
---
var y = floor(b)
$B$ = |  | var y = floor(x + 5.7)
---
$R$ = |  | var y = floor(x + 5.7)
---
console.log(y)
(b) Corresponding merge tuple. Figure 3: Formulation of a merge instance in
our setting.

One possible way to learn a merge algorithm is by modeling the conditional
probability

$p(R|A,B,O)$ (1)

In other words, a model that generates the output program $R$ given the three
input programs.

Because programs are sequences, we further decompose Eq 1 by applying the
chain rule [29]:

$p(R|A,B,O)=\prod_{j=1}^{N}{p(R_{j}|R_{<j},A,B,O)}$

This models the probability of generating the $j-$th element of the program,
given the elements generated so far. There are many possible ways to model a
three-way merge. However, the above formulation suggests one obvious approach
is to use a maximum likelihood estimate of a sequence-to-sequence model.

###  2.2 Challenges

Applying a sequence-to-sequence (Seq2seq) model to merge conflict resolution
poses unique challenges. We discuss three key challenges, concerning input
representation, output construction, and dataset extraction.

####  2.2.1 Representing the Merge Inputs as a Sequence.

In a traditional sequence-to-sequence task such as machine translation, there
is a single input sequence that maps to a single output sequence. However, in
our case, we have three input sequences of varying sizes, corresponding to the
three versions of a program involved in a merge conflict. It is not
immediately evident how to determine a suitable token granularity and encode
these sequences in a manner that is amenable to learning. One obvious solution
is to concatenate the tokens of the three sequences to obtain a single
sequence. However, the order of concatenation is unclear. Furthermore, as we
show in Section 3.2, such a naive representation not only suffers from
information loss and truncation, but also poor precision by being unaware of
$A$ and $B$’s edits over common base $O$. In summary, we have:

  * CH1: Encode programs $A$, $B$, and $O$ as the input to a Seq2Seq model.

####  2.2.2 Constructing the Output Resolution

Our key insight that a majority of resolutions do not introduce new lines
leads us to construct the output resolution directly from lines in the
conflicting region. This naturally suggests the use of pointer networks [34],
an encoder-decoder architecture capable of producing outputs explicitly
pointing to tokens in the input sequence. However, a pointer network
formulation suggests an equivalent input and output granularity. In Section
3.2, we show that the input is best represented at a granularity far smaller
than lines.

Thus, the challenge is:

  * CH2: Output $R$ at the line granularity given a non-line granularity input.

####  2.2.3 Extracting Ground Truth from Raw Merge Data.

Finally, to learn a data-driven merge algorithm, we need real-world data that
serves as ground truth. Creating this dataset poses non-trivial challenges.
First, we need to localize the resolution region and corresponding conflicting
region. In some cases, developers performing a manual merge resolution made
changes unrelated to the merge. Localizing resolution regions unambiguously
from input programs is challenging due to the presence of these unrelated
changes. Second, we need to be able to recognize and subsequently filter merge
resolutions that do not incorporate both the changes. In summary, we have:

  * CH3: Identify merge tuples $\\{(A^{i},B^{i},O^{i},R^{i})\\}_{i=1}^{M}$ given $(\mathcal{A},\mathcal{B},\mathcal{O},\mathcal{M})$.

##  3 The DeepMerge Architecture

Figure 4: Overall DeepMerge framework. The dotted box represents repetition of
decode until $m=M$ i.e. the $\langle{\tt STOP}\rangle$ token is predicted. In
this example, we have omitted $m=2$ in which the call to decode outputs
$y_{2}=\langle 3,A\rangle.$

Section 2 suggested one way to learn a three-way merge is through a maximum
likelihood estimate of a sequence-to-sequence model. In this section we
describe DeepMerge, the first data-driven merge framework, and discuss how it
addresses challenges CH1 and CH2. We motivate the design of DeepMerge by
comparing it to a standard sequence-to-sequence model, the encoder-decoder
architecture.

###  3.1 Encoder Decoder Architectures

Sequence-to-sequence models aim to map a fixed-length input
($(X_{N})_{N\in\mathbb{N}}$), to a fixed-length output,
($(Y_{M})_{M\in\mathbb{N}}$). 222Note that $M$ is not necessary equal to $N$.
The standard sequence-to-sequence model consists of three components: an input
embedding, an encoder, and a decoder.

Input embedding: An embedding maps a discrete input from an input vocabulary
$V$ ($x_{n}\in\mathbb{N}^{|V|}$), to a continuous $D$ dimensional vector space
representation ($\overline{x}_{n}\in\mathbb{R}^{D}$). Such a mapping is
obtained by multiplication over an embedding matrix
$E\in\mathbb{R}^{D\times|V|}$. Applying this for each element of $X_{N}$ gives
$\overline{X}_{N}$.

Encoder: An encoder encode, processes each $\overline{x}_{n}$ and produces a
hidden state, $z_{n}$ which summarizes the sequence upto the $n$-th element.
At each iteration, the encoder takes as input the current sequence element
$x_{n}$, and the previous hidden state $z_{n-1}$. After processing the entire
input sequence, the final hidden state, $z_{N}$, is passed to the decoder.

Decoder: A decoder decode, produces the output sequence $Y_{M}$ from an
encoder hidden state $Z_{n}$. Similar to encoders, decoders work in an
iterative fashion. At each iteration, the decoder produces a single output
token $y_{m}$ along with a hidden summarization state $h_{m}$. The current
hidden state and the previous predicted token $y_{m}$ are then used in the
following iteration to produce $y_{m+1}$ and $h_{m+1}$. Each $y_{m}$ the model
predicts is selected through a softmax over the hidden state:

$p(y_{m}|y_{1},...,y_{m-1},X)=\textit{softmax}(h_{m})$

DeepMerge is based on this encoder-decoder architecture with two significant
differences.

First, rather than a standard embedding followed by encoder, we introduce a
novel embedding method called Merge2Matrix. Merge2Matrix addresses CH1 by
summarizing input programs ($A,B,O$) into a single embedding fed to the
encoder. We discuss our Merge2Matrix solution as well as less effective
alternatives in Section 3.2.

Second, rather than using a standard decoder to generate output tokens in some
output token vocabulary, we augment the decoder to function as a variant of
pointer networks. The decoder outputs line tuples ($i$, $W$) where
$W\in\\{A,B\\}$ and $i$ is the $i$-th line in $W$. We discuss this in detail
in Section 3.4.

Example 2. Figure 4 illustrates the flow of DeepMerge as it processes the
inputs of a merge tuple. First, the raw text of $A,B,$ and $O$ is fed to
Merge2Matrix. As the name suggests, Merge2Matrix summarizes the tokenized
inputs as a matrix. That matrix is then fed to an encoder which computes the
encoder hidden state $z_{N}$. Along with the start token for the decoder
hidden state, the decoder takes $z_{N}$ and iteratively (denoted by the
$\cdots$) generates as output the lines to copy from $A$ and $B$. The final
resolution is shown in the green box. $\Box$

###  3.2 Merge2Matrix

An encoder takes a single sequence as input. As discussed in Section 2.2, a
merge tuple consists of three sequences. This section introduces Merge2Matrix,
an input representation that expresses the tuple as a single sequence. It
consists of embedding, transformations to summarize embeddings, and finally,
edit-aware alignment.

####  3.2.1 Tokenization and Embedding

This section discusses our relatively straightforward application of both
tokenization and embedding.

_Tokenization._ Working with textual data requires tokenization whereby we
split a sequence of text into smaller units referred to as tokens. Tokens can
be defined at varying granularities such as characters, words, or sub-words.
These units form a vocabulary which maps input tokens to integer indices.
Thus, a vocabulary is a mapping from a sequence of text to a sequence of
integers. This paper uses byte-pair encoding (BPE) as it has been shown to
work well with source code, where tokens can be formed by combining different
words via casing conventions (e.g. snake_case or camelCase) causing a blowup
in vocabulary size [18]. Byte-pair encoding is an unsupervised sub-word
tokenization that draws inspiration from information theory and data
compression wherein frequently occurring sub-word pairs are recursively merged
and stored in the vocabulary. We found that the performance of BPE was
empirically superior to other tokenization schemes.

_Embedding._ Given an input sequence $X_{N}$, and a hyperparameter (embedding
dimension) $D$, an embedding transformation creates $\overline{X}_{N}$. As
described in Section 3.1, the output of this embedding is then fed to an
encoder. Because a merge tuple consists of three inputs ($A$, $B$, and $O$),
the following sections introduce novel transformations that _summarize_ these
three inputs into a format suitable for the encoder.

####  3.2.2 Merge Tuple Summarization

In this section, we describe summarization techniques that are employed after
embedding. Before we delve into details, we first introduce two functions used
in summarization.

Suppose a function that concatenates embedded representations:

$concat_{s}:(\mathbb{R}^{D\times N}\times\cdots\times\mathbb{R}^{D\times
N})\rightarrow\mathbb{R}^{D\times sN}$

that takes $s$ similarly shaped tensors as arguments and concatenates them
along their last dimension. Concatenating these $s$ embeddings increases the
size of the encoder’s input by a factor of $s$.

Suppose a function $linearize$ that linearly combines $s$ embedded
representations. We parameterize this function with learnable parameters
$\theta\in\mathbb{R}^{s+1}$. As input, $linearize$ takes an embedding
$\overline{x}_{i}\in\mathbb{R}^{D}$ for $i\in 1..S$. Thus, we define

$linearize_{\theta}(\overline{x}_{1},\dots,\overline{x}_{s})=\theta_{1}\cdot\overline{x}_{1}+\cdots+\theta_{s}\cdot\overline{x}_{s}+\theta_{s+1}$

where all operations on the inputs $\overline{x}_{1},\dots,\overline{x}_{s}$
are pointwise. $linearize$ reduces the size of the embeddings fed to the
encoder by a factor of $s$.

Now that we have defined two helper functions, we describe two summarization
methods.

_Naïve._ Given a merge tuple’s inputs ($A,B,O$), a naïve implementation of
Merge2Matrix is to simply concatenate the embedded representations (i.e.,
$concat_{3}(\overline{A},\overline{B},\overline{O})$) Traditional sequence-to-
sequence models often suffer from information forgetting; as the input grows
longer, it becomes harder for encode to capture long-range correlations in
that input. A solution that addresses CH1, must be concise while retaining the
information in the input programs.

Linearized. As an attempt at a more concise representation, we introduce a
summarization we call _linearized_. This method linearly combines each of the
embeddings through our helper function:
$linearize_{\theta}(\overline{A},\overline{B},\overline{O})$. In Section 5 we
empirically demonstrate better model accuracy when we summarize with
$linearize_{\theta}$ rather than $concat_{s}$.

####  3.2.3 Edit-Aware Alignment

Figure 5: Merge2Matrix: implemented with the Aligned Linearized input
representation used in DeepMerge.

In addition to input length, CH1 also alludes that an effective input
representation needs to be “edit aware”. The aforementioned representations do
not provide any indication that $A$ and $B$ are edits from $O$.

Prior work, Learning to Represent Edits (LTRE) [38] introduces a
representation to succinctly encode 2 two-way diffs. The method uses a
standard deterministic diffing algorithm and represents the resulting pair-
wise alignment as an auto-encoded fixed dimension vector.

A two-way alignment produces an “edit sequence”. This series of edits, if
applied to the second sequence, would produce the first. An edit sequence,
$\Delta_{AO}$, is comprised of the following editing actions: $\mathbb{=}$
representing equivalent tokens, $\mathbb{+}$ representing insertions,
$\mathbb{-}$ representing deletions, $\mathbb{\leftrightarrow}$ representing a
replacement. Two special tokens $\mathbb{\emptyset}$ and $\mathbb{|}$ are used
as a padding token and a newline marker, respectively. Note that these
$\Delta$s only capture information about the kinds of edits and _ignore_ the
the tokens that make up the edit itself (with the exception of the newline
token). Prior to the creation of $\Delta$, a preprocessing step adds padding
tokens such that equivalent tokens in A (resp. B) and O are in the same
position. These sequences, shown in Figure 5 are denoted as $A^{\prime}$ and
$AO^{\prime}$ (resp. $B^{\prime}$ and $BO^{\prime}$).

Example 3. Consider $B$’s edit to $O$ in Figure 5 via its preprocessed
sequences $B^{\prime}$, $BO^{\prime}$, and its edit sequence $\Delta_{BO}$.
One intuitive view of $\Delta_{BO}$ is that it is a set of instructions that
describe how to turn $B^{\prime}$ into $BO^{\prime}$ with the aforementioned
semantics. Note the padding token $\emptyset$ introduced into $\Delta_{BO}$
represents padding out to the length of the longer edit sequence
$\Delta_{AO}$. $\Box$

We now describe two edit-aware summarization methods based on this edit-aware
representation. However, our setting differs from the original LTRE setting as
we assume three input sequences and a three-way diff. In the following
summarization methods, we assume that $A,B,O$ are tokenized, but not embedded
before invoking Merge2Matrix.

Aligned _naïve_. Given $\Delta_{AO}$ and $\Delta_{BO}$, we embed each to
produce $\overline{\Delta_{AO}}$ and $\overline{\Delta_{BO}}$, respectively.
Then we combine these embeddings through concatenation and thus
$concat_{2}(\overline{\Delta_{AO}},\overline{\Delta_{BO}})$ is fed to the
encoder.

Aligned linearized. This summarization method is depicted in Figure 5,
invoking $linearize$ to construct an input representation over edit sequences.
First, we apply alignment to create $\Delta_{AO}$ and $\Delta_{BO}$. This is
portrayed through the $\bigoplus$ operator. Following construction of the
$\Delta$s, we apply embedding and subsequently apply our edit-aware linearize
operation via the $\bigotimes$ operator. Thus, we summarize embeddings with
$linearize_{\theta}(\overline{\Delta_{AO}},\overline{\Delta_{BO}})$ and feed
its output to the encoder. As we demonstrate in Section 5, this edit-aware
input representation significantly increases the model’s accuracy.

_LTRE._ Finally, for completeness, we also include the original LTRE
representation. We modify this to our setting by creating two 2-way diffs. The
original LTRE has a second key difference from our summarization methods. LTRE
includes all tokens from from the input sequences in addition to the edit
sequences That is, LTRE summarizes $A^{\prime}$ $AO^{\prime}$, $\Delta_{AO}$,
$B^{\prime}$, $BO^{\prime}$, and $\Delta_{BO}$. Let $\overline{A^{\prime}}$,
$\overline{AO^{\prime}}$ and $\overline{\Delta_{AO}}$, (resp
$\overline{B^{\prime}}$, $\overline{BO^{\prime}}$, and
$\overline{\Delta_{BO}}$) be the embedding of a two-way diff. Then, the
following summarization combines all embeddings:

$concat_{6}(\overline{\Delta_{AO}},\overline{A^{\prime}},\overline{AO^{\prime}},\overline{\Delta_{BO}},\overline{B^{\prime}},\overline{BO^{\prime}})$

###  3.3 The Encoder

The prior sections described Merge2Matrix which embeds a merge into a
continuous space which is then summarized by an encoder. DeepMerge uses a bi-
directional gated recurrent unit[7] (GRU) to summarize the embedded input
sequence. We empirically found that a bi-directional GRU was more effective
than a uni-directional GRU.

###  3.4 Synthesizing Merge Resolutions

This section summarizes DeepMerge’s approach to solving CH2. Given a sequence
of hidden vectors $Z_{N}$ produced by an encoder, a decoder generates output
sequence $Y_{M}$. We introduce an extension of a traditional decoder to copy
lines of code from those input programs.

Denote the number of lines in $A$ and $B$ as $Li_{A}$ and $Li_{B}$,
respectively. Suppose that $L=1..(Li_{A}+Li_{B})$; then, a value $i\in L$
corresponds to the $i$-th line from $A$ if $i<=Li_{A}$, and the $i-Li_{A}$-th
line from $B$, otherwise.

Given merge inputs ($A$, $B$, $O$), DeepMerge’s decoder computes a sequence of
hidden states $H_{M}$, and models the conditional probability of _lines_
copied from the input programs $A$, $B$, and $O$ by predicting a value in
$y_{m}\in Y_{M}$:

$p(y_{m}|y_{1},...,y_{m-1},A,B,O)=\textit{softmax}(h_{m})$

where $h_{m}\in H_{M}$ is the decoder hidden state at the $m$-th element of
the output sequence and the $\textit{argmax}(y_{m})$ yields an index into $L$.

In practice, we add an additional $\langle{\tt STOP}\rangle$ token to $L$. The
$\langle{\tt STOP}\rangle$ token signifies that the decoder has completed the
sequence. The $\langle{\tt STOP}\rangle$ token is necessary as the decoder may
output a variable number of lines conditioned on the inputs.

This formulation is inspired by pointer networks [34], an encoder-decoder
architecture that outputs an index that explicitly points to an input token.
Such networks are designed to solve combinatorial problems like sorting.
Because the size of the output varies as a function of the input, a pointer
network requires a novel attention mechanism that applies attention weights
directly to the input sequence. This differs from traditional attention
networks which are applied to the outputs of the encoder $Z_{N}$. In contrast,
DeepMerge requires no change to attention. Our architecture outputs an index
that points to the abstract concept of a line, rather than an explicit token
in the input. Thus, attention applied to $Z_{N}$, a summarization of the
input, is sufficient.

###  3.5 Training and Inference with DeepMerge

The prior sections discussed the overall model architecture of DeepMerge. This
section describes hyperparameters that control model size and how we trained
the model. We use a embedding dimension $D=1024$ and 1024 hidden units in the
single layer GRU encoder. Assume the model parameters are contained in
$\theta$; training seeks to find the values of $\theta$ that maximize the log-
likelihood

$\operatorname*{arg\,max}_{\theta}\log p_{\theta}(R|A,B,O)$

over all merge tuples (($A,B,O$), $R$) in its training dataset. We use
standard cross-entropy loss with the Adam optimizer. Training takes roughly 18
hours on a NVIDIA P100 GPU and we pick the model with the highest validation
accuracy, which occurred after 29 epochs.

Finally, during inference time, we augment DeepMerge to use standard beam
search methods during decoding to produce the most likely $k$ top merge
resolutions. DeepMerge predicts merge resolutions up to $C$ lines. We set
$C=30$ to tackle implementation constraints and because most resolutions are
less than 30 lines long. However, we evaluate DeepMerge on a full test dataset
including samples where the number of lines in $M$ is $\geq C$.

##  4 Real-World Labeled Dataset

This section describes our solution to CH3: localizing merge instances
$(A,B,O,R)_{i}$ from $(\mathcal{A},\mathcal{B},\mathcal{O},\mathcal{M})$.
Since a program may have several merge conflicts, we decompose the overall
merge problem into merging individual instances. As shown in Figure 3(a), $A$,
$B$, and $O$ regions can be easily extracted given the diff3 conflict markers.
However, reliably localizing a resolution $R$ involves two sub-challenges:

  1. 1.

How do we localize individual regions $R$ unambiguously?

  2. 2.

How do we deal with trivial resolutions?

In this section, we elaborate on each of these sub-challenges and discuss our
solutions. We conclude with a discussion of our final dataset and its
characteristics.

Algorithm 1 Localizing Merge Tuples from Files for Dataset

1:procedure LocalizeMergeTuples($\mathcal{C}$, $\mathcal{M}$)

2: $\it MT\leftarrow\emptyset$ $\triangleright$ Merge Tuples

3: for $i\in$ [1, NumConflicts$(\mathcal{C})$] do

4: $R\leftarrow$ LocalizeResRegion$(\mathcal{C},\mathcal{M},i)$

5: if $R=={\tt nil}$ then

6: continue $\triangleright$ Could not find resolution

7: end if

8: $(A,B,O)\leftarrow$GetConflictComponents$(\mathcal{C},i)$

9: if $R\in\\{A,B,O\\}$ then

10: continue $\triangleright$ Filter trivial resolutions

11: end if

12: if $\textsc{Lines}(R)\subseteq\textsc{Lines}(A)\cup\textsc{Lines}(B)$ then

13: $\it MT\leftarrow\it MT\cup\\{(A,B,O,R)\\}$

14: end if

15: end for

16: return $\it MT$

17:end procedure

18:procedure LocalizeResRegion($\mathcal{C}$, $\mathcal{M}$, $i$)

19: $n\leftarrow\it Length(\mathcal{M})$ $\triangleright$ Length of
$\mathcal{M}$ in chars

20: $m\leftarrow\it Length(\mathcal{C})$ $\triangleright$ Length of
$\mathcal{C}$ in chars

21: $({\it spos},{\it epos})\leftarrow$ GetConflictStartEnd($\mathcal{C},i$)

22: $\it prfx\leftarrow\ {\it\langle BOF\rangle}\ +\ \mathcal{C}[0:{\it
spos}]$

23: $\it sffx\leftarrow\mathcal{C}[{\it epos}:m]+{\it\langle EOF\rangle}$

24: s $\leftarrow$ MinimalUniquePrefix(${\it reverse}(\it prfx),{\it
reverse}(\mathcal{M})$)

25: e $\leftarrow$ MinimalUniquePrefix($\it sffx,\mathcal{M}$)

26: if $s\geq 0$ and $e\geq 0$ then

27: return $\mathcal{M}[n-s:e]$

28: else

29: return ${\tt nil}$

30: end if

31:end procedure

32:procedure MinimalUniquePrefix($x$, $y$)

33: Output:Returns the start position of the minimal non-empty prefix of $x$
that appears uniquely in $y$, else -1

34:end procedure

35:procedure lines($p$)

36: Output:Returns the set of lines comprising the program $p$

37:end procedure

Algorithm 1 denotes a method to localize merge tuples from a corpus of merge
conflict and resolution files. The top-level procedure ExtractMergeTuples
takes $\mathcal{C}$, the diff3 conflict file with markers, along with
$\mathcal{M}$, the resolved file. From those inputs, it extracts merge tuples
into $\it MT$. The algorithm loops over each of the conflicted regions in
$\mathcal{C}$, and identifies the input $(A,B,O)$ and output ($R$) of the
tuple using GetConflictComponents and LocalizeResRegion respectively. Finally,
it applies a filter on the extracted tuple (lines 5 – 14). We explain each of
these components in the next few subsections.

###  4.1 Localization of Resolution Regions

    <BOF>
    ...
    var time = new Date();
    print_time(time);
    <<<<<<< a.js
    x = foo();
    ||||||| base.js
    =======
    x = bar();
    >>>>>>> b.js
    print_time(time);
    <EOF>

(a) A merge instance.

    <BOF>
    ...
    let time = new Date();
    print_time(time);
    baz();
    print_time(time);
    <EOF>

(b) Resolution. Figure 6: Challenging example for localizing resolution.

Creating a real-world merge conflict labeled dataset requires identifying the
“exact” code region that constitutes a resolution. However, doing so can be
challenging; Figure 6(a) demonstrates an example. The developer chooses to
perform a resolution baz(); that does not correspond to anything from the $A$
or $B$ edits, and the surrounding context also undergoes changes (e.g.
changing var with let which restricts the scope in the prefix). To the best of
our knowledge, there is no known algorithm to localize $R$ for such cases.

LocalizeResRegion is our method that tries to localize the $i^{th}$ resolution
region $R$, or returns ${\tt nil}$ when unsuccessful. Intuitively, we find a
prefix and suffix in a merge instance and use this prefix and suffix to
bookend a resolution. If we cannot uniquely find those bookends, we say the
resolution is _ambiguous_.

The method first obtains the prefix $\it prfx$ (resp. suffix $\it sffx$) of
the $i^{th}$ conflict region in $\mathcal{C}$ in line 22 (resp. line 23). We
add the start of file ${\it\langle BOF\rangle}$ and end of file ${\it\langle
EOF\rangle}$ tokens to the prefix and suffix respectively. The next few lines
try to match the prefix $\it prfx$ (resp. suffix $\it sffx$) in the resolved
file $\mathcal{M}$ unambiguously. Let us first focus on finding the suffix of
the resolution region in $\mathcal{M}$ in line 25. The procedure
MinimalUniquePrefix takes two strings $x$ and $y$ and finds the start position
of the minimal non-empty prefix of $x$ that appears uniquely in $y$, or
returns -1. For example, MinimalUniquePrefix(“abc”, “acdabacc”) is 3 since
“ab” is the minimal prefix of $x$ that appears uniquely in $y$ starting in
position 3 (0-based indexing).

To find the prefix of the resolution, we reverse the $\it prfx$ string and
search for matches in reversed $\mathcal{M}$, and then finally find the offset
from the start of $\mathcal{M}$ by subtracting $s$ from the length $n$ of
$\mathcal{M}$. The unique occurrence of both the prefix and suffix in
$\mathcal{M}$ allows us to map the conflicted region to the resolved region.

For our example, even though the line “print_time(time);” that encloses the
conflicted region appears twice in $\mathcal{M}$, extending it by “time = new
Date();” in the prefix and ${\it\langle EOF\rangle}$ in the suffix provides a
unique match in $\mathcal{M}$. Thus, the algorithm successfully localizes the
desired region “baz();” as the resolution region.

After localizing the resolution regions, we have a set of merge instances of
the form $(A,B,O,R)$. We can use our definition from Section 2 to label a
merge tuple $(A,B,O,R)$.

###  4.2 Filtering Trivial Resolutions

Upon examining our dataset, we found a large set of merges in which $A$ was
taken as the resolution and $B$ was entirely ignored (or vice versa). These
trivial samples, in large, were the product of running git merge with “ours”
or “theirs” command-line options. Using these merge options indicates that the
developer did not resolve the conflict after careful consideration of both
branches, but instead relied on the git interface to completely drop one set
of changes. The aforementioned command-line merge options are typically used
the commit is the first of many fix-up commits to perform the full resolution.

We appeal to the notion of a “valid merge” that tries to incorporate both the
syntactic and semantic changes from both $A$ and $B$. Thus, these samples are
not valid as they disregard the changes from $B$ (resp. $A$) entirely.
Furthermore, these trivial samples comprised 70% of our “pre-filtering”
dataset. Previous work confirmed our observation that a majority of merge
resolutions in GitHub Java projects (75% in Table 13 [11]) correspond to
taking just $A$ or $B$. To avoid polluting our dataset, we filter such merges
$(A,B,O,R)$ where $R\in\\{A,B,O\\}$ (line 9 in Algorithm 1). Our motivation to
filter the dataset of trivial labels is based on both dataset bias and the
notion of a valid merge.

###  4.3 Final Dataset

We crawled repositories in GitHub containing primarily JavaScript files,
looking at merge commits. To avoid noise and bias, we select projects that
were active in the past one year (at the time of writing), and received at
least 100 stars (positive sentiment). We also verified that the dataset did
not contain duplicate merges. We ignore minified JavaScript files that
compress an entire JavaScript file to a few long lines. Finally, note that
Algorithm 1 filters away any resolution that consists of new segments (lines)
outside of $A$ and $B$ as our technique targets resolutions that do not
involve writing any new code. After applying filters, we obtained 8,719 merge
tuples. We divided these into a 80/10/10 percent training/validation/test
split. Our dataset contains the following distribution in terms of total
number of lines in $A$ and $B$: 45.08% ([0,5]), 20.57% ([6,10]), 26.42%
([11,50]), 4.22% ([51,100]) and 3.70% (100+).

##  5 Evaluation

In this section, we empirically evaluate DeepMerge to answer the following
questions:

  1. RQ1

How effective is DeepMerge at synthesizing resolutions?

  2. RQ2

How effective is DeepMerge at suppressing incorrect resolutions?

  3. RQ3

On which samples is DeepMerge most effective?

  4. RQ4

How do different choices of input representation impact the performance of
DeepMerge?

###  5.1 RQ1: Effectiveness of Resolution Synthesis

In this section, we perform an evaluation to assess DeepMerge’s effectiveness
of synthesizing resolutions. Our prediction, $\hat{R}$, is considered correct
if it is an exact (line for line, token for token) match with $R$.

_Evaluation metrics._ DeepMerge produces a ranked list of predictions; we
define top-1 (resp. top-3) accuracy if the $R$ is present in first (resp. top
3) predictions. This is a lower bound, as multiple resolutions may be
“correct” with respect to the semantics of the changes being merged (e.g., in
some cases, switching two declarations or unrelated statements has no impact
on semantics).

_Quantitative Results._ Table I shows the performance of DeepMerge on a held
out test set. DeepMerge has an overall top-1 accuracy of 36.5%, correctly
generating more than one in three resolutions as its first ranked choice. When
we consider the top-3 ranked resolutions, DeepMerge achieves a slightly
improved accuracy of 43.23%.

| Top-1 | Top-3
---|---|---
DeepMerge | 36.50% | 43.23%
ScanMerge | 4.20% | 7.43%
Seq2Seq | 2.3% | 3.3%
jsFSTMerge | 3.7% | N/A

Table I: Evaluation of DeepMerge and baselines: resolution synthesis accuracy
(%).

_Baselines._ Table I also includes a comparison of DeepMerge to three
baselines. We compare to a heuristic based approach (ScanMerge), an off-the-
shelf sequence-to-sequence model (Seq2Seq), and a structured AST based
approach (jsFSTMerge).

Our first baseline ScanMerge, is a heuristic based approach designed by
manually observing patterns in our dataset. ScanMerge randomly samples from
the space of sub-sequences over lines from $A$ and $B$ that are: (i)
syntactically valid and parse, (ii) include each line from $A$ and $B$, and
(iii) preserve the order of lines within $A$ and $B$. These heuristic
restrictions are based on manual observations that a large fraction of
resolutions satisfy these conditions.

Table I shows ScanMerge’s performance averaged over 10 trials. DeepMerge
performs significantly better in terms of top-1 resolution accuracy (36.50% vs
4.20%). ScanMerge only synthesizes one in 20 resolutions correctly. In
contrast, DeepMerge correctly predicts one in 3 resolutions. On inputs of 3
lines or less, ScanMerge only achieves 12% accuracy suggesting that the
problem space is large even for small merges.

We also compared DeepMerge to an out of the box sequence-to-sequence encoder-
decoder model [30] (Seq2Seq) implemented with Fairseq
333https://github.com/pytorch/fairseq natural language processing library.
Using a naïve input (i.e., $concat_{3}(A,B,O)$), tokenized with a standard
byte-pair encoding, and Fairseq’s default parameters, we trained on the same
dataset as DeepMerge. DeepMerge outperforms the sequence-to-sequence model in
terms of both top-1 (36.5% vs. 2.3%) and top-3 accuracy (43.2% vs. 3.3%). This
is perhaps not surprising given the precise notion of accuracy that does not
tolerate even a single token mismatch. We therefore also considered a more
relaxed measure, the BLEU-4 score [26], a metric that compares two sentences
for “closeness” using an n-gram model. The sequence-to-sequence model achieves
a respectable score of 27%, however DeepMerge still outperforms with a BLEU-4
score of 50%. This demonstrates that our novel embedding of the merge inputs
and pointer network style output technique aid DeepMerge significantly and
outperform a state of the art sequence-to-sequence baseline model.

Lastly, we compared DeepMerge to jsFSTMerge[32], a recent semistructured AST
based approach. jsFSTMerge leverages syntactic information by representing
input programs as ASTs. With this format, algorithms are invoked to safely
merge nodes and subtrees. Structured approaches do not model semantics and can
only safely merge program elements that do not have side effects. Structured
approaches have been proven to work well for statically typed languages such
as Java [3, 21]. However, the benefits of semistructured merge hardly
translate to dynamic languages such as JavaScript. JavaScript provides less
static information than Java and allows statements (with potential side
effects) at the same syntactic level as commutative elements such as function
declarations.

As a baseline to compare to DeepMerge, we ran jsFSTMerge with a timeout of 5
minutes. Since jsFSTMerge is a semistructured approach we apply a looser
evaluation metric. A resolution is considered correct if it is an exact
syntactic match with $R$ or if it is semantically equivalent. We determine
semantic equivalence manually. jsFSTMerge produces a correct resolution on
3.7% of samples which is significantly lower than DeepMerge. Furthermore,
jsFSTMerge does not have support for predicting Top-k resolutions and only
outputs a single resolution. The remaining 96.3% of cases failed as follows.
In 92.1% of samples, jsFSTMerge was not able to produce a resolution and
reported a conflict. In 3.3% of samples, jsFSTMerge took greater than 5
minutes to execute and was terminated. In the remaining 0.8% jsFSTMerge
produced a resolution that was both syntactically and semantically different
than the user’s resolution. In addition to effectiveness, DeepMerge is
superior to jsFSTMerge in terms of execution time. Performing inference with
deep neural approaches is much quicker than (semi) structured approaches. In
our experiments, jsFSTMerge had an average execution time of 18 seconds per
sample. In contrast, sequence-to-sequence models such as DeepMerge perform
inference in under a second.

Threshold | [1,3] lines | [4,5] lines | [6,7] lines | [8,10] lines | [$>$10] lines
---|---|---|---|---|---
0 | 78.40% | 56.50% | 37.04% | 10.87% | 2.93%

Table II: Evaluation of DeepMerge: accuracy vs input size (%).  Figure 7:
DeepMerge’s performance vs merge input size. Cumulative distribution of merge
sizes in red.

_Sensitivity to Input Merge Conflict Size._ We observe that there is a diverse
range in the size of merge conflicts (lines in $A$ plus lines in $B$).
However, as shown in Figure 7, most (58% of our test set) merges are small,
consisting of 7 or less lines. As a product of the dataset distribution and
problem space size, DeepMerge performs better for smaller merges. We present
aggregate Top-1 accuracy for the input ranges in Table II. DeepMerge achieves
over 78% synthesis accuracy on merge inputs consisting of 3 lines or less. On
merge inputs consisting of 7 lines or less (58% of our test set) DeepMerge
achieves over 61% synthesis accuracy.

###  5.2 RQ2: Effectiveness of Suppressing Incorrect Resolutions

The probabilistic nature of DeepMerge allows for accommodating a spectrum of
users with different tolerance for incorrect suggestions. “Confidence” metrics
can be associated with each output sequence to suppress unlikely suggestions.
In this section, we study the effectiveness of DeepMerge’s confidence
intervals.

In the scenario where DeepMerge cannot confidently synthesize a resolution, it
declares a conflict and remains silent without reporting a resolution. This
enables DeepMerge to provide a higher percentage of correct resolutions
(higher precision) at the cost of not providing a resolution for every merge
(lower recall). This is critical for practical use, as prior work has shown
that tools with a high false positive rate are unlikely to be used by
developers [17]. Figure 8 depicts the precision, recall, and F1 score values,
for various confidence thresholds (with 95% confidence intervals). We aim to
find a threshold that achieves high precision without sacrificing too much
recall. In Figure 8, the highest F1-Score of 0.46 is achieved at 0.4 and 0.5.
At threshold of 0.5, DeepMerge’s top-1 precision is 0.72 with a recall of
0.34. Thus, while DeepMerge only produces a resolution one third of the time,
that resolution is correct three out of four times. Compared to DeepMerge with
no thresholding, at a threshold of .5 DeepMerge achieves a 2x improvement in
precision while only sacrificing a 10% drop in recall. Thresholds of 0.4 and
0.5 were identified as best performing on a held out validation set. We then
confirmed that these thresholds were optimal on the held out test set reported
in Figure 8.

Figure 8: Top-1 precision and recall by confidence threshold.

###  5.3 RQ3: Categorical Analysis of Effectiveness

We now provide an analysis of DeepMerge’s performance. To understand which
samples DeepMerge is most effective at resolving, we classify the dataset into
two classes: CONCAT and OTHER. The classes are defined as follows:

  1. 1.

CONCAT \- resolutions of the form $AB$ or $BA$. Specifically:

     * •

$R$ contains all lines in $A$ and all lines in $B$.

     * •

There is no interleaving between $A$’s lines and $B$’s lines.

     * •

The order of lines within $A$ and $B$ is preserved.

  2. 2.

OTHER \- resolutions not classified as CONCAT.
OTHER samples can be any interleaving of any subset of lines.

Class | Top-1 Accuracy | Percent of Dataset
---|---|---
CONCAT | 44.40% | 26.88%
OTHER | 29.03% | 73.12%

Table III: Accuracy and Distribution of classes.

Table III shows the performance of DeepMerge on each class. DeepMerge performs
comparably well on each category suggesting that DeepMerge is effective at
resolving conflicts beyond concatenation.

###  5.4 RQ4: Impact of Input Representation

We now evaluate the use of Merge2Matrix and show the benefit of the Aligned
Linearized implementation used in DeepMerge.

We evaluate DeepMerge on each combination of summarization and edit aware
alignment described in Section 3.2: _Naïve_ , _Linearized_ , _LTRE_ , _Aligned
naïve_ , and _Aligned Linearized_. Table IV shows the performance of each
input representation on detection and synthesis. The edit-aware input formats:
_LTRE_ , _Aligned Naïve_ , and _Aligned Linearized_ attain an improvement over
the edit-unaware formats. Our _Aligned_ representations are more succinct and
contribute to a large increase in accuracy over the edit-unaware formats.
_Aligned Naïve_ increases accuracy over our best edit-unaware format by 12.16%
for top-1 and 12.27% for top-3. We believe this is due to the verbosity of
including the underlying tokens as well as the $\Delta$ edit sequence. The
combination of our edit-aware and summarization insights (_Aligned
Linearized_) yields the highest accuracy.

| Top-1 | Top-3
---|---|---
Naïve | 9.62% | 14.09%
Linearized | 15.25% | 19.95%
LTRE | 23.37% | 29.21%
Aligned Naïve | 27.41% | 32.22%
Aligned Linearized | 36.50% | 43.23%

Table IV: Accuracy of different input representation choices.

###  5.5 Summary of Results

Our evaluation and baselines indicate that the problem of synthesizing
resolutions is a non-trivial task, even when restricted to resolutions that
rearrange lines from the conflict. DeepMerge not only can synthesize
resolutions for more than a third of times, but can also use its internal
confidence to achieve high precision (72%). DeepMerge can synthesize
resolutions significantly more accurately than heuristic based, neural, and
structured approaches. We also illustrate the need for edit-aware aligned
encoding of merge inputs to help deep learning be more effective synthesizing
non-trivial resolutions.

##  6 Related Work

Our technique is related to several existing works in both program merging and
deep learning for code.

###  6.1 Source Code Merging

The most widely used method for merging changes is diff3, the default for most
version control systems. One reason for its popularity is that diff3 is purely
text based and therefore language agnostic. However, its behavior has been
formalized and Khanna _et al._ showed that the trust developers have in it may
be misplaced [20], including the examples in Figure 1.

There have been many attempts to improve merge algorithms by taking language
specific analyses into account (see the work of Mens for a broad survey [23]).
Westfechtel _et al._ use the structure of the source code to reduce merge
conflicts [36]. Apel _et al._ noted that structured and unstructured merge
each has strengths and weaknesses. They developed jsFSTMerge, a _semi-
structured merge_ , that alternates between approaches [4]. They later
introduced JDime, an approach that automatically tunes a mixture of structured
and unstructured merge based conflict locations [2]. Sousa _et al._ introduced
a verification approach, SafeMerge that examines the base program, both
changed programs, and the merge resolution to verify that the resolution
preserves semantic conflict freedom [28].

The key difference between DeepMerge and these structured or semi-structured
merge approaches is that they require a priori knowledge of the language of
the merged code in the form of a parser or annotated grammar (or more advanced
program verification tools). Further, structured merge tools cannot
conservatively merge changes made within method bodies. Finally, Pan et al.
[24] explore the use of program synthesis for learning repeated resolutions in
a large project. The approach requires the design of a domain-specific
languages inspired by a small class of resolutions (around imports and macros
in C++). In contrast to both these approaches, DeepMerge only requires a
corpus of merge resolutions in the target language, and can apply to all merge
conflicts. However, we believe that both these approaches are complementary
and can be incorporated into DeepMerge.

###  6.2 Deep Learning on Source Code

We leverage deep neural network based natural language processing methods to
address the challenge of three way merge resolution. We discuss related works
in sequence-to-sequence learning that inspired our model and applications of
deep learning for the software engineering domain.

Pointer networks [34] use attention to constrain general sequence-to-sequence
models [30, 6]. Recent works incorporate a copy mechanism in sequence-to-
sequence models by combining copying and token generation [14], adding a
copying module in the decoder [39], and incorporating it into the beam search
[25]. In contrast to DeepMerge, none of these approaches address the
challenges described in Section 2 in a three-way merge.

Deep learning has been successfully used on source code to improve myriad
software engineering tasks. These include code completion and code generation
[31, 8], code search [15], software testing [12], defect prediction [35], and
code summarization [1]. Deep learning has been used in program repair using
neural machine translation [33, 5], sequence-editing approaches [25], and
learning graph transformations [9]. For a deeper review of deep learning
methods applied to software engineering tasks, see the literature reviews[22,
10].

While neural sequence-to-sequence models are utilized in most of those
applications, they consume only one input sequence, mapping it to a single
output sequence. Edit aware embeddings [38] introduced LTRE method to encode
two program variants to model source code edits. As we demonstrate, our edit-
aware encoding Aligned Linearized is inspired by this approach but
significantly outperforms LTRE in the context of data-driven merge.

##  7 Conclusion

We motivated the problem of data-driven merge and highlighted the main
challenges in applying machine learning. We proposed DeepMerge, a data-driven
merge framework, and demonstrated its effectiveness in resolving unstructured
merge conflicts in JavaScript. We chose JavaScript as the language of focus in
this paper due to its importance and growing popularity and the fact that
analysis of JavaScript is challenging due at least in part to its weak,
dynamic type system and permissive nature [16, 19]. We believe that DeepMerge
can be easily extended to other languages and perhaps to any list-structured
data format such as JSON and configuration files. We plan to combine program
analysis techniques (e.g., parsing, typechecking, or static verifiers for
merges) to prune the space of resolutions, and combine structured merge
algorithms with machine learning to gain the best of both techniques.
Furthermore, we plan to generalize our approach beyond line level output
granularity.

## References

  * [1] U. Alon, O. Levy, and E. Yahav.  code2seq: Generating sequences from structured representations of code.  In International Conference on Learning Representations, 2019.
  * [2] S. Apel, O. Leßenich, and C. Lengauer.  Structured merge with auto-tuning: balancing precision and performance.  In Proceedings of the 27th IEEE/ACM International Conference on Automated Software Engineering, pages 120–129, 2012.
  * [3] S. Apel, J. Liebig, B. Brandl, C. Lengauer, and C. Kästner.  Semistructured merge: Rethinking merge in revision control systems.  In ACM SIGSOFT Symposium on Foundations of Software Engineering, pages 190–200, 2011.
  * [4] S. Apel, J. Liebig, C. Lengauer, C. Kästner, and W. R. Cook.  Semistructured merge in revision control systems.  In VaMoS, pages 13–19, 2010.
  * [5] S. Chakraborty, M. Allamanis, and B. Ray.  Tree2tree neural translation model for learning source code changes.  CoRR, abs/1810.00314, 2018.
  * [6] K. Cho, B. van Merriënboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio.  Learning phrase representations using RNN encoder–decoder for statistical machine translation.  In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1724–1734, Doha, Qatar, Oct. 2014\. Association for Computational Linguistics.
  * [7] K. Cho, B. van Merrienboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio.  Learning phrase representations using rnn encoder-decoder for statistical machine translation, 2014.
  * [8] C. Clement, D. Drain, J. Timcheck, A. Svyatkovskiy, and N. Sundaresan.  Pymt5: Multi-mode translation of natural language and python code with transformers.  In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 9052–9065, 2020.
  * [9] E. Dinella, H. Dai, Z. Li, M. Naik, L. Song, and K. Wang.  Hoppity: Learning graph transformations to detect and fix bugs in programs.  In International Conference on Learning Representations, 2020.
  * [10] F. Ferreira, L. L. Silva, and M. T. Valente.  Software engineering meets deep learning: A literature review.  arXiv preprint arXiv:1909.11436, 2019.
  * [11] G. Ghiotto, L. Murta, M. de Oliveira Barros, and A. van der Hoek.  On the nature of merge conflicts: A study of 2, 731 open source java projects hosted by github.  IEEE Trans. Software Eng., 46(8):892–915, 2020.
  * [12] P. Godefroid, H. Peleg, and R. Singh.  Learn&fuzz: Machine learning for input fuzzing.  In 2017 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 50–59. IEEE, 2017.
  * [13] G. Gousios, M. D. Storey, and A. Bacchelli.  Work practices and challenges in pull-based development: the contributor’s perspective.  In Proceedings of the 38th International Conference on Software Engineering, ICSE 2016, Austin, TX, USA, May 14-22, 2016, pages 285–296. ACM, 2016.
  * [14] J. Gu, Z. Lu, H. Li, and V. O. Li.  Incorporating copying mechanism in sequence-to-sequence learning.  In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1631–1640, Berlin, Germany, Aug. 2016. Association for Computational Linguistics.
  * [15] X. Gu, H. Zhang, and S. Kim.  Deep code search.  In Proceedings of the 40th International Conference on Software Engineering, ICSE ’18, page 933–944, New York, NY, USA, 2018. Association for Computing Machinery.
  * [16] S. H. Jensen, A. Møller, and P. Thiemann.  Type analysis for javascript.  In International Static Analysis Symposium, pages 238–255. Springer, 2009.
  * [17] B. Johnson, Y. Song, E. Murphy-Hill, and R. Bowdidge.  Why don’t software developers use static analysis tools to find bugs?  In 2013 35th International Conference on Software Engineering (ICSE), pages 672–681. IEEE, 2013.
  * [18] R.-M. Karampatsis, H. Babii, R. Robbes, C. Sutton, and A. Janes.  Big code != big vocabulary: Open-vocabulary models for source code.  In Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering, ICSE ’20, pages 1073 — 1085, New York, NY, USA, 2020\. Association for Computing Machinery.
  * [19] V. Kashyap, K. Dewey, E. A. Kuefner, J. Wagner, K. Gibbons, J. Sarracino, B. Wiedermann, and B. Hardekopf.  Jsai: a static analysis platform for javascript.  In Proceedings of the 22nd ACM SIGSOFT international symposium on Foundations of Software Engineering, pages 121–132, 2014.
  * [20] S. Khanna, K. Kunal, and B. C. Pierce.  A formal investigation of diff3.  In International Conference on Foundations of Software Technology and Theoretical Computer Science, pages 485–496. Springer, 2007.
  * [21] O. Leßenich, S. Apel, and C. Lengauer.  Balancing precision and performance in structured merge.  Automated Software Engineering, 22(3):367–397, 2015.
  * [22] X. Li, H. Jiang, Z. Ren, G. Li, and J. Zhang.  Deep learning in software engineering.  arXiv preprint arXiv:1805.04825, 2018.
  * [23] T. Mens.  A state-of-the-art survey on software merging.  IEEE transactions on software engineering, 28(5):449–462, 2002\.
  * [24] R. Pan, V. Le, N. Nagappan, S. Gulwani, S. K. Lahiri, and M. Kaufman.  Can program synthesis be used to learn merge conflict resolutions? an empirical analysis.  In 43rd IEEE/ACM International Conference on Software Engineering, ICSE 2021, Madrid, Spain, 22-30 May 2021, pages 785–796. IEEE, 2021.
  * [25] S. Panthaplackel, M. Allamanis, and M. Brockschmidt.  Copy that! editing sequences by copying spans, 2020.
  * [26] K. Papineni, S. Roukos, T. Ward, and W.-J. Zhu.  Bleu: a method for automatic evaluation of machine translation.  In Proceedings of the 40th annual meeting of the Association for Computational Linguistics, pages 311–318, 2002.
  * [27] R. Smith.  Gnu diff3.  distributed with GNU diffutils package, April 1998.
  * [28] M. Sousa, I. Dillig, and S. K. Lahiri.  Verified three-way program merge.  Proc. ACM Program. Lang., 2:165:1–165:29, 2018.
  * [29] I. Sutskever, O. Vinyals, and Q. V. Le.  Sequence to sequence learning with neural networks.  In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27, pages 3104–3112. Curran Associates, Inc., 2014.
  * [30] I. Sutskever, O. Vinyals, and Q. V. Le.  Sequence to sequence learning with neural networks.  In Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2, NIPS’14, page 3104–3112, Cambridge, MA, USA, 2014. MIT Press.
  * [31] A. Svyatkovskiy, Y. Zhao, S. Fu, and N. Sundaresan.  Pythia: Ai-assisted code completion system.  In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’19, page 2727–2735, New York, NY, USA, 2019. Association for Computing Machinery.
  * [32] A. T. Tavares, P. Borba, G. Cavalcanti, and S. Soares.  Semistructured Merge in JavaScript Systems, page 1014–1025.  IEEE Press, 2019.
  * [33] M. Tufano, C. Watson, G. Bavota, M. D. Penta, M. White, and D. Poshyvanyk.  An empirical study on learning bug-fixing patches in the wild via neural machine translation.  ACM Trans. Softw. Eng. Methodol., 28(4), Sept. 2019.
  * [34] O. Vinyals, M. Fortunato, and N. Jaitly.  Pointer networks.  In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28, pages 2692–2700. Curran Associates, Inc., 2015.
  * [35] S. Wang, T. Liu, and L. Tan.  Automatically learning semantic features for defect prediction.  In 2016 IEEE/ACM 38th International Conference on Software Engineering (ICSE), pages 297–308. IEEE, 2016.
  * [36] B. Westfechtel.  Structure-oriented merging of revisions of software documents.  In Proceedings of the 3rd international workshop on Software configuration management, pages 68–79, 1991.
  * [37] W. Yang, S. Horwitz, and T. Reps.  A program integration algorithm that accommodates semantics-preserving transformations.  ACM Trans. Softw. Eng. Methodol., 1(3):310–354, 1992.
  * [38] P. Yin, G. Neubig, M. Allamanis, M. Brockschmidt, and A. L. Gaunt.  Learning to represent edits.  In International Conference on Learning Representations, 2019.
  * [39] Q. Zhou, N. Yang, F. Wei, and M. Zhou.  Sequential copying networks.  In AAAI, 2018.


††thanks: These authors contributed equally to this work.††thanks: These
authors contributed equally to this work.††thanks: These authors contributed
equally to this work.

# Unconditional and robust quantum metrological advantage beyond NOON states

Jian Qin  Yu-Hao Deng  Han-Sen Zhong  Li-Chao Peng  Hao Su  Yi-Han Luo  Jia-
Min Xu  Dian Wu  Si-Qiu Gong  Hua-Liang Liu  Hui Wang  Ming-Cheng Chen  Li Li
Nai-Le Liu  Chao-Yang Lu  Jian-Wei Pan  Hefei National Research Center for
Physical Sciences at the Microscale and School of Physical Sciences,
University of Science and Technology of China, Hefei, Anhui 230026, China  CAS
Center for Excellence and Synergetic Innovation Center in Quantum Information
and Quantum Physics, University of Science and Technology of China, Shanghai
201315, China  Hefei National Laboratory, University of Science and Technology
of China, Hefei 230088, China

###### Abstract

Quantum metrology employs quantum resources to enhance the measurement
sensitivity beyond that can be achieved classically. While multi-photon
entangled NOON states can in principle beat the shot-noise limit and reach the
Heisenberg limit, high NOON states are difficult to prepare and fragile to
photon loss which hinders it from reaching unconditional quantum metrological
advantages. Here, we combine the idea of unconventional nonlinear
interferometers and stimulated emission of squeezed light, previously
developed for photonic quantum computer Jiuzhang, to propose and realize a new
scheme that achieves a scalable, unconditional, and robust quantum
metrological advantage. We observe a 5.8(1)-fold enhancement above the shot-
noise limit in the Fisher information extracted per photon, without
discounting for photon loss and imperfections, which outperforms ideal 5-NOON
states. The Heisenberg-limited scaling, the robustness to external photon
loss, and the ease-of-use of our method make it applicable in practical
quantum metrology at low photon flux regime.

In optical phase measurements, especially at regimes with low photon flux, it
is of fundamental interest to maximize the Fisher information Helstrom (1969)
that can be extracted per photon. Given finite resources, that is, the total
number of photons that traverse the sample, it has been shown that the phase
sensitivity is bound to shot-noise limit (SNL) using classical light
Giovannetti  _et al._ (2004); Polino  _et al._ (2020); Braunstein (1992).
Quantum resources can be employed to achieve phase sensitivity beyond the SNL
Giovannetti  _et al._ (2004), which is called supersensitivity. In 1981, Caves
proposed the first phase supersensitive measurement protocol using squeezed
light Caves (1981), which were demonstrated experimentally Xiao  _et al._
(1987); Grangier  _et al._ (1987) later and used in GEO600 The LIGO Scientific
Collaboration (2011) and the Advanced Laser Interferometer Gravitational-Wave
Observatory Tse  _et al._ (2019); Acernese  _et al._ (2019) recently.

In quantum mechanics, the Heisenberg uncertainty principle places a
fundamental limit for sensitivity Giovannetti  _et al._ (2004); Polino  _et
al._ (2020). It has been shown that a multi-photon path-entangled state, so
called NOON state Lee  _et al._ (2002), can achieve the Heisenberg limit in
principle. The interference fringes of the N-photon NOON states have a period
N times shorter than using single photons Mitchell  _et al._ (2004); Walther
_et al._ (2004), a phenomena called super-resolution. The phase super-
resolution has been demonstrated using probabilistic and post-selected NOON
states with up to 5 photons Mitchell  _et al._ (2004); Nagata  _et al._
(2007); Afek  _et al._ (2010); Matthews  _et al._ (2009); Rozema  _et al._
(2014) and multi-photon entangled states Polino  _et al._ (2020); Walther  _et
al._ (2004); Resch  _et al._ (2007); Okamoto  _et al._ (2008); Xiang  _et al._
(2011); Wang  _et al._ (2018); Zhong  _et al._ (2018).

However, it should be noted that the super-resolution is not equivalent to the
super-sensitivity Resch  _et al._ (2007). An unconditional quantum
metrological advantage is achieved if the measured sensitivity per resource
beats the SNL when all the used quantum resources are taken into account. For
example, the total number of photons effectively employed in the experiment
should not be corrected by imperfections such as photon loss, state fidelity,
detection, and post-selection. The only unconditional violation of SNL at the
low photon flux regime Slussarenko  _et al._ (2017) was demonstrated in 2017
but that scheme was limited for a 2-photon NOON state.

Unconditional quantum metrological advantages beyond the 2-photon NOON-states
remained challenging. One reason is that the multi-photon NOON-state based
super-sensitivity is very fragile to the photon loss. Even a small amount of
photon loss will balance out the quantum-gained sensitivity Demkowicz-
Dobrzanski  _et al._ (2009). However, high-efficiency preparations of high-
NOON states without post-selection, as well as high-efficiency output photon
projection and detection, have been long-standing challenges in the field over
decades Resch  _et al._ (2007); Datta  _et al._ (2011).

In a different path, Yurke et al. proposed an unconventional interferometer to
achieve the Heisenberg scaling employing cascaded optical parametric
amplifiers, instead of the passive beam splitters Yurke  _et al._ (1986). Such
nonlinear interferometers, also referred to as SU(1,1) interferometers, have
been implemented using atomic four-wave mixing Jing  _et al._ (2011); Hudelist
_et al._ (2014); Gupta  _et al._ (2018), and bulk nonlinear medium Manceau
_et al._ (2017); Frascella  _et al._ (2019). However, these demonstrations
haven’t reached the unconditional advantage.

Figure 1: Principle of the stimulated squeezing nonlinear interferometer. (a)
An input vacuum state is squeezed by a pair of two-mode squeezers ($S_{TM}$)
with a relative phase $\phi$ which is to be measured. The output two-mode
squeezed state is detected at single-photon level. (b) A comparison of
theoretically predicted phase sensitivity for various measurement schemes
assuming perfect visibility and efficiency. (c) A comparison of efficiency
threshold to surpass the shot-noise limit (SNL) between our scheme and NOON-
state at different mean photon number.

In this Letter, for the first time, we combine the idea of nonlinear
interferometer with stimulated emission of squeezed light Zhong  _et al._
(2021); Lamas-Linares  _et al._ (2001), to demonstrate a scalable,
unconditional, and robust quantum metrological advantage. A record-high Fisher
information per photon, 11.6(1) $\rm{rad}^{-2}$, is directly observed, without
discounting for any experimental imperfection. This not only unconditionally
beats the SNL, but also surpass the limit that can be achieved using even
ideal 5-NOON states. Using our method, we further demonstrate a case study for
practical, real-time quantum-enhanced phase measurement at the low photon flux
regime.

Figure 1 illustrates the working principle of the stimulated squeezing
nonlinear interferometer which consists of a pair of two-mode squeezer
($S_{TM}$). The first $S_{TM}$ transforms an input vacuum state into a two-
mode squeezed state (TMSS), which then acquires a to-be-measured phase $\phi$.
The TMSS is sent to the second $S_{TM}$ and detected by two threshold single-
photon detectors. The output state can be written as:

$|\psi(\phi)\rangle=S_{TM}(r)U(\phi)S_{TM}(r)|0\rangle,$ (1)

where
$S_{TM}(r)=e^{r\left(\hat{a}\hat{b}-\hat{a}^{\dagger}\hat{b}^{\dagger}\right)}$
is the $S_{TM}$ operator, $r$ is the squeezing parameter, and
$U(\phi)=e^{i\left(\hat{a}^{\dagger}\hat{a}+\hat{b}^{\hat{\dagger}}\hat{b}\right)\phi}$
is the phase shift operator.

In the output, there are four possible outcomes: $p_{00}$, which refers to no
click on both detectors, $p_{01}$($p_{10}$), which refers to click on the
upper (lower) detector and no click on the other detector, and $p_{11}$ ,
which refers to coincident click on both detectors. We can calculate these
probabilities and analyze the phase sensitivity as Fisher information per
trial:

$F=\sum_{i,j=0,1}{\left(\frac{\partial\ln
p_{ij}}{\partial\phi}\right)^{2}}p_{ij}.$ (2)

The Fisher information has a maximum of $F_{\max}=4\sinh^{2}\left(2r\right)$.
The mean photon number passing through by the phase sensor is
$\bar{n}=2\sinh^{2}r$. Therefore, the phase sensitivity could be expressed as:

$\Delta\phi=\frac{1}{\sqrt{F_{\max}}}=\frac{1}{2\sqrt{\bar{n}\left(\bar{n}+2\right)}}.$
(3)

This equation confirms that the phase sensitivity of our scheme saturate the
Heisenberg scaling.

Figure 1b shows a comparison of the phase measurement sensitivity using Fig.
1a with the SNL and the protocol using NOON states ideally (assuming a unity
state fidelity and unity efficiencies in the generation, propagation and
detection). The sensitivity scaling of our scheme is similar to the NOON
state, which agrees with Eq. 2, and clearly beats the SNL. Note that as a
conservative comparison, we only count for the photons actually passing though
the sample, which, for the case of an N-photon NOON states in a Mach-Zehnder
interferometer configuration, the average photon number is $N/2$.

As Fig. 1b consider the theoretical sensitivity only under perfect conditions,
it is necessary to further analyze the performance under the most relevant
realistic noise: the photon loss. For the N-photon NOON states to surpass the
SNL, the threshold of the single-photon system efficiency is
$\eta_{N00N}=\sqrt[N]{1/N}$, which asymptotically tends to 100% and thus sets
an unrealistically demanding experimental challenge (see the blue line in Fig.
1c). The threshold detection efficiency of our scheme to surpass the SNL is
$\eta_{TM}=1-\sqrt{1-1/2\left(\bar{n}+2\right)}$ (see Supplemental Materials
sup  for a detailed derivation). As shown in the green line of Fig. 1c, this
is significantly lower than that of the NOON states Manceau  _et al._ (2017);
Plick  _et al._ (2010); Marino  _et al._ (2012). Moreover, in contrast to the
NOON states, our threshold curve decrease as a function of the mean photon
number, making it experimentally feasible and robust to the most sensitive
noise in optical systems, the external photon loss (photon loss after the
interferometer).

Figure 2: Experimental setup. A femtosecond pulsed laser is used to pump the
periodically poled potassium titanyl phosphate (PPKTP) crystal as the
squeezer. The concave mirror and reflection mirror form a compact 4-f optics
to mode-match between both the pumping laser and squeezed photons of the first
squeezing process to the second squeezing process. The relative phase between
the two squeezing operation is tuned by a wedge plate. The quarter-wave plate
(QWP) is used to exchange the polarization of the two-mode squeezed light for
compensation of the birefringence walk-off. The two-mode squeezed photons are
collected into single-mode fiber and detected by two superconducting nanowire
single photon detectors. A dichromatic mirror (DM) and silicon plate are used
to filter out the pumping laser from the squeezed photons.

In our experiment, we use stimulated emission of TMSS, previously developed
for photonic quantum computer, Jiuzhang Zhong  _et al._ (2021), to implement
the nonlinear interferometer. The setup is shown in Fig. 2. First, transform-
limited laser pulses at a central wavelength of 775 nm are focused on a 4-mm-
thickness periodically poled potassium titanyl phosphate (PPKTP) crystal to
generate the TMSS at 1550 nm. The PPKTP is carefully designed to fulfill a
collinear frequency-uncorrelated and degenerate type-II phase matching Zhong
_et al._ (2020). After the first pass, the pump laser and the collinear TMSS
photons are reflected back and re-focused by a concave mirror, which are then
used as seeds to stimulate the second parametric down-conversion process. Note
that our experimental set-up naturally integrates the double-pass metrology
protocol Higgins  _et al._ (2007).

After filtering out the pump laser using a dichroic mirror and a silicon
plate, the stimulated TMSS is collected into a single-mode fiber, projecting
the two modes into the same spatial mode. The output is split by a polarizing
beam splitter and detected by two superconducting nanowire single-photon
detectors with a detection efficiency of $\sim$93%. The PPKTP and the final
planar mirror are placed at the focal points of the middle concave mirror to
form a 4f optical system, which ensures the two parametric down-conversion
processes have an optimal spatial matching. The birefringent walk-off between
the horizontally and vertically polarization is compensated using a quarter-
wave plate. The to-be-measured relative phase $\phi$ is added using an anti-
reflection-coated wedge plate, where, due to material dispersion, the pumping
laser and TMSS accumulate different phases. The $\phi$ can be tuned by a
motorized translation stage.

In the first experiment, we choose a squeezing parameter of the TMSS to be
0.59(1) by tuning the power of the pumping laser, corresponding to a mean
photon number of 0.78(1). The total system efficiency of the horizontal and
vertical modes is 0.744(4) and 0.751(4), respectively. The squeezing
parameters and the system efficiencies are carefully calibrated from the
directly measured data, which is crucial for unconditional metrology
advantage. The detailed calibration method is presented in Supplementary
Materials sup . To measure the phase sensitivity, we tune the wedge plate to
scan the phase from 0 to $\pi$, and record the four possible output signals
$p_{00}$, $p_{01}$, $p_{10}$ and $p_{11}$. The interference fringes of
$p_{11}$ has a high visibility of 96.6(2)% (Fig. 3a), which reflect the degree
of mode matching between the seed and the stimulated TMSS.

Figure 3: Experimentally measured output detection probability and the
corresponding Fisher information. (a) The green (blue) points correspond to
experimentally measured {1(0), 0(1))} coincidence events, the purple (red)
points correspond to {1(0), 1(0)} coincidence events. Solid curves are fitted
based on theoretical model (see Supplementary Materials sup ). The error bar
is smaller than the plot dot size. (b) The Fisher information per photon as a
function of the phase. The cyan curve corresponds to the experimental results,
while the red lines correspond to SNL. The shaded areas indicate 95%
confidence region. (c) The measured Fisher information per photon for various
squeezing parameter and its comparison with SNL. Figure 4: Phase sensitivity
in a real-time measurement. (a) Dynamical tracing of the phase. The phase
$\phi$ is tuned in steps with a motor-driven wedge plate for 150 seconds, and
measured in real time with a sampling time of 0.2 second for each setting. The
orange (blue) dots are measured (set) phases. (b) Experimentally measured
phase uncertainty. Dots are the standard deviation of the measured phase
corresponding to the data in (a), whose uncertainty is obtained by
bootstrapping technique. The solid curve is the minimal standard deviation
estimated from Fisher information. Red line corresponds to the SNL. Shaded
areas correspond to 95% confidence region.

We use Fisher information per photon that traverse the sample to quantify the
quantum metrological advantage at low photon flux regime. Following Eq. 2,
based on the interference fringes in Fig. 3a, we extract the Fisher
information per photon, which is shown in Fig. 3b as a function of phase. The
optimal Fisher information per photon reaches 11.6(1) $\rm{rad}^{-2}$ at the
most sensitive phase points of 0.67 and 0.90. This is well above the SNL (red
dash line), as shown in Fig. 3b. It also exceeds the predicted value using an
ideal 5-photon NOON state and perfect detectors, and arbitrary number of NOON
states if using detectors with the same efficiency as in our work. Under
different squeezing parameters at a range of 0.11(1) to 0.59(1), the Fisher
information per photon is measured and plotted in Fig. 3c where all data
points exceed the SNL and 5-photon NOON states. In addition, the data shows a
slight increase as a function of mean photon number, pointing a way to further
improve the measurement sensitivity. With realistic improvements of the mode
overlapping to 0.995 and the squeezing parameter to 1.5, a Fisher information
per photon of 31.5 $\rm{rad}^{-2}$ can be achieved in the near future (see
Fig. S1 in sup ).

Finally, exploiting its unconditional and robust quantum-enhance metrological
performance, we apply our scheme in a real-time phase measurement
demonstration. The to-be-measured phase is set to periodically oscillate in
steps between eleven $\phi_{i}$ settings, controlled by a motor-driven
positioner. At each phase, we collect 0.2 s data to obtain an estimation of
$\phi_{i}$, denoted as $\phi_{i}^{est}$, which is optimized by minimizing the
squared difference between the measured probabilities and their corresponding
calibration curves ($p_{ij}(\phi)$ in Fig. 3a). The estimated phases and the
preset phases are plotted together in Fig. 4a for a comparison. The phase
measurement process is repeated 200 times to calculate the phase sensitivity
$\Delta\phi$, which is the standard deviation of $\phi_{i}^{est}$. The
experimentally measured phase sensitivity $\Delta\phi$ are shown in Fig. 4b,
which are in a good agreement with the theoretical phase sensitivity (cyan
line) calculated from the Fisher information plotted in Fig. 3a. The squeezing
parameter in this test is set at 0.43(1). The best phase sensitivity of
$\Delta\phi=0.002(1)$ rad is obtained at the phase setting of 0.58, which is
well beyond the SNL by 3.56 dB, and the ideal 5-NOON state interferometry.
Although phase super-sensitivity is achieved only within a specific range, the
entire phase range could be included by using adaptive feedback measurement
Wiseman (1995); Berni  _et al._ (2015); Yonezawa  _et al._ (2012).

In conclusion, by implementing a nonlinear interferometer Yurke  _et al._
(1986), proposed more than 30 years ago, in a double-pass configuration of
stimulated squeezed-photon emission as used in Jiuzhang Zhong  _et al._
(2021), we have demonstrated unconditional quantum metrological advantage in
phase sensing. Our method has a clear pathway to scale up, and is robust to
external photon loss, thus opens a promising way to practical quantum
metrology applications in the ultralow photon flux regime, such as measurement
of light-sensitive materials Wolfgramm  _et al._ (2013); Taylor  _et al._
(2013); Ono  _et al._ (2013); Israel  _et al._ (2014); Wäldchen  _et al._
(2015); Taylor and Bowen (2016); Perarnau-Llobet  _et al._ (2021); You  _et
al._ (2021); Casacio  _et al._ (2021).

Note: After completing our experiment, we became aware of a related work based
on direct homodyne detection of squeezed states posted on arXiv:2111.09756.

###### Acknowledgements.

This work was supported by the National Natural Science Foundation of China,
the National Key R&D Program of China (2019YFA0308700), the Chinese Academy of
Sciences, the Anhui Initiative in Quantum Information Technologies and the
Science and Technology Commission of Shanghai Municipality.

## References

  * Helstrom (1969) C. W. Helstrom, Journal of Statistical Physics 1, 231 (1969).
  * Giovannetti  _et al._ (2004) V. Giovannetti, S. Lloyd, and L. Maccone, Science 306, 1330 (2004).
  * Polino  _et al._ (2020) E. Polino, M. Valeri, N. Spagnolo, and F. Sciarrino, AVS Quantum Science 2, 024703 (2020).
  * Braunstein (1992) S. L. Braunstein, Physical Review Letters 69, 3598 (1992).
  * Caves (1981) C. M. Caves, Physical Review D 23, 1693 (1981).
  * Xiao  _et al._ (1987) M. Xiao, L.-A. Wu, and H. J. Kimble, Physical Review Letters 59, 278 (1987).
  * Grangier  _et al._ (1987) P. Grangier, R. E. Slusher, B. Yurke, and A. LaPorta, Physical Review Letters 59, 2153 (1987).
  * The LIGO Scientific Collaboration (2011) The LIGO Scientific Collaboration, Nature Physics 7, 962 (2011).
  * Tse  _et al._ (2019) M. e. Tse, H. Yu, N. Kijbunchoo, A. Fernandez-Galiana, P. Dupej, L. Barsotti, C. Blair, D. Brown, S. Dwyer, A. Effler, _et al._ , Physical Review Letters 123, 231107 (2019).
  * Acernese  _et al._ (2019) F. Acernese, M. Agathos, L. Aiello, A. Allocca, A. Amato, S. Ansoldi, S. Antier, M. Arène, N. Arnaud, S. Ascenzi, _et al._ , Physical Review Letters 123, 231108 (2019).
  * Lee  _et al._ (2002) H. Lee, P. Kok, and J. P. Dowling, Journal of Modern Optics 49, 2325 (2002).
  * Mitchell  _et al._ (2004) M. W. Mitchell, J. S. Lundeen, and A. M. Steinberg, Nature 429, 161 (2004).
  * Walther  _et al._ (2004) P. Walther, J.-W. Pan, M. Aspelmeyer, R. Ursin, S. Gasparoni, and A. Zeilinger, Nature 429, 158 (2004).
  * Nagata  _et al._ (2007) T. Nagata, R. Okamoto, J. L. O’Brien, K. Sasaki, and S. Takeuchi, Science 316, 726 (2007).
  * Afek  _et al._ (2010) I. Afek, O. Ambar, and Y. Silberberg, Science 328, 879 (2010).
  * Matthews  _et al._ (2009) J. C. Matthews, A. Politi, A. Stefanov, and J. L. O’brien, Nature Photonics 3, 346 (2009).
  * Rozema  _et al._ (2014) L. A. Rozema, J. D. Bateman, D. H. Mahler, R. Okamoto, A. Feizpour, A. Hayat, and A. M. Steinberg, Physical review letters 112, 223602 (2014).
  * Resch  _et al._ (2007) K. J. Resch, K. L. Pregnell, R. Prevedel, A. Gilchrist, G. J. Pryde, J. L. O’Brien, and A. G. White, Physical Review Letters 98, 223601 (2007).
  * Okamoto  _et al._ (2008) R. Okamoto, H. F. Hofmann, T. Nagata, J. L. O’Brien, K. Sasaki, and S. Takeuchi, New Journal of Physics 10, 073033 (2008).
  * Xiang  _et al._ (2011) G.-Y. Xiang, B. L. Higgins, D. Berry, H. M. Wiseman, and G. Pryde, Nature Photonics 5, 43 (2011).
  * Wang  _et al._ (2018) X.-L. Wang, Y.-H. Luo, H.-L. Huang, M.-C. Chen, Z.-E. Su, C. Liu, C. Chen, W. Li, Y.-Q. Fang, X. Jiang, _et al._ , Physical review letters 120, 260502 (2018).
  * Zhong  _et al._ (2018) H.-S. Zhong, Y. Li, W. Li, L.-C. Peng, Z.-E. Su, Y. Hu, Y.-M. He, X. Ding, W. Zhang, H. Li, L. Zhang, Z. Wang, L. You, X.-L. Wang, X. Jiang, L. Li, Y.-A. Chen, N.-L. Liu, C.-Y. Lu, and J.-W. Pan, Physical Review Letters 121, 250505 (2018).
  * Slussarenko  _et al._ (2017) S. Slussarenko, M. M. Weston, H. M. Chrzanowski, L. K. Shalm, V. B. Verma, S. W. Nam, and G. J. Pryde, Nature Photonics 11, 700 (2017).
  * Demkowicz-Dobrzanski  _et al._ (2009) R. Demkowicz-Dobrzanski, U. Dorner, B. J. Smith, J. S. Lundeen, W. Wasilewski, K. Banaszek, and I. A. Walmsley, Physical Review A 80, 013825 (2009).
  * Datta  _et al._ (2011) A. Datta, L. Zhang, N. Thomas-Peter, U. Dorner, B. J. Smith, and I. A. Walmsley, Physical Review A 83, 063836 (2011).
  * Yurke  _et al._ (1986) B. Yurke, S. L. McCall, and J. R. Klauder, Physical Review A 33, 4033 (1986).
  * Jing  _et al._ (2011) J. Jing, C. Liu, Z. Zhou, Z. Y. Ou, and W. Zhang, Applied Physics Letters 99, 011110 (2011).
  * Hudelist  _et al._ (2014) F. Hudelist, J. Kong, C. Liu, J. Jing, Z. Ou, and W. Zhang, Nature Communications 5, 3049 (2014).
  * Gupta  _et al._ (2018) P. Gupta, B. L. Schmittberger, B. E. Anderson, K. M. Jones, and P. D. Lett, Optics Express 26, 391 (2018).
  * Manceau  _et al._ (2017) M. Manceau, G. Leuchs, F. Khalili, and M. Chekhova, Physical Review Letters 119, 223604 (2017).
  * Frascella  _et al._ (2019) G. Frascella, E. Mikhailov, N. Takanashi, R. Zakharov, O. Tikhonova, and M. Chekhova, Optica 6, 1233 (2019).
  * Zhong  _et al._ (2021) H.-S. Zhong, Y.-H. Deng, J. Qin, H. Wang, M.-C. Chen, L.-C. Peng, Y.-H. Luo, D. Wu, S.-Q. Gong, H. Su, Y. Hu, P. Hu, X.-Y. Yang, W.-J. Zhang, H. Li, Y. Li, X. Jiang, L. Gan, G. Yang, L. You, Z. Wang, L. Li, N.-L. Liu, J. J. Renema, C.-Y. Lu, and J.-W. Pan, Physical Review Letters 127, 180502 (2021).
  * Lamas-Linares  _et al._ (2001) A. Lamas-Linares, J. C. Howell, and D. Bouwmeester, Nature 412, 887 (2001).
  * (34) See Supplemental Materials at [url] for detailed descriptions of phase sensitivity under photon loss; calibration method for resource counting; estimating the phase sensitivity with near-term feasible parameters, which includes Refs. Resch  _et al._ (2007); Marino  _et al._ (2012); Quesada  _et al._ (2018).
  * Plick  _et al._ (2010) W. N. Plick, J. P. Dowling, and G. S. Agarwal, New Journal of Physics 12, 083014 (2010).
  * Marino  _et al._ (2012) A. M. Marino, N. V. Corzo Trejo, and P. D. Lett, Physical Review A 86, 023844 (2012).
  * Zhong  _et al._ (2020) H.-S. Zhong, H. Wang, Y.-H. Deng, M.-C. Chen, L.-C. Peng, Y.-H. Luo, J. Qin, D. Wu, X. Ding, Y. Hu, P. Hu, X.-Y. Yang, W.-J. Zhang, H. Li, Y. Li, X. Jiang, L. Gan, G. Yang, L. You, Z. Wang, L. Li, N.-L. Liu, C.-Y. Lu, and J.-W. Pan, Science 370, 1460 (2020).
  * Higgins  _et al._ (2007) B. L. Higgins, D. W. Berry, S. D. Bartlett, H. M. Wiseman, and G. J. Pryde, Nature 450, 393 (2007).
  * Wiseman (1995) H. M. Wiseman, Physical Review Letters 75, 4587 (1995).
  * Berni  _et al._ (2015) A. A. Berni, T. Gehring, B. M. Nielsen, V. Händchen, M. G. A. Paris, and U. L. Andersen, Nature Photonics 9, 577 (2015).
  * Yonezawa  _et al._ (2012) H. Yonezawa, D. Nakane, T. A. Wheatley, K. Iwasawa, S. Takeda, H. Arao, K. Ohki, K. Tsumura, D. W. Berry, T. C. Ralph, _et al._ , Science 337, 1514 (2012).
  * Wolfgramm  _et al._ (2013) F. Wolfgramm, C. Vitelli, F. A. Beduini, N. Godbout, and M. W. Mitchell, Nature Photonics 7, 28 (2013).
  * Taylor  _et al._ (2013) M. A. Taylor, J. Janousek, V. Daria, J. Knittel, B. Hage, H.-A. Bachor, and W. P. Bowen, Nature Photonics 7, 229 (2013).
  * Ono  _et al._ (2013) T. Ono, R. Okamoto, and S. Takeuchi, Nature Communications 4, 2426 (2013).
  * Israel  _et al._ (2014) Y. Israel, S. Rosen, and Y. Silberberg, Physical Review Letters 112, 103604 (2014).
  * Wäldchen  _et al._ (2015) S. Wäldchen, J. Lehmann, T. Klein, S. van de Linde, and M. Sauer, Scientific Reports 5, 15348 (2015).
  * Taylor and Bowen (2016) M. A. Taylor and W. P. Bowen, Physics Reports Quantum Metrology and Its Application in Biology, 615, 1 (2016).
  * Perarnau-Llobet  _et al._ (2021) M. Perarnau-Llobet, D. Malz, and J. I. Cirac, Quantum 5, 446 (2021).
  * You  _et al._ (2021) C. You, M. Hong, P. Bierhorst, A. E. Lita, S. Glancy, S. Kolthammer, E. Knill, S. W. Nam, R. P. Mirin, O. S. Magaña-Loaiza, and T. Gerrits, Applied Physics Reviews 8, 041406 (2021).
  * Casacio  _et al._ (2021) C. A. Casacio, L. S. Madsen, A. Terrasson, M. Waleed, K. Barnscheidt, B. Hage, M. A. Taylor, and W. P. Bowen, Nature 594, 201 (2021).
  * Quesada  _et al._ (2018) N. Quesada, J. M. Arrazola, and N. Killoran, Physical Review A 98, 062322 (2018).