# Mercury: An Efficiency Benchmark for LLM Code Synthesis

Mingzhe Du1,2, Anh Tuan Luu1, Bin Ji2, See-Kiong Ng2
1Nanyang Technological University
2National University of Singapore
{mingzhe001<EMAIL_ADDRESS>{jibin<EMAIL_ADDRESS>
###### Abstract

Despite advancements in evaluating Large Language Models (LLMs) for code
synthesis, benchmarks have predominantly focused on functional correctness,
overlooking the importance of code efficiency. We present _Mercury_ , the
first benchmark designated for assessing the code efficiency of LLM code
synthesis tasks. Mercury consists of 1,889 programming tasks covering diverse
difficulty levels alongside test case generators generating unlimited cases
for comprehensive evaluation. Unlike existing benchmarks, Mercury integrates a
novel metric _$Beyond@K$_ to measure normalized code efficiency based on
historical submissions, leading to a new evaluation indicator for code
synthesis, which encourages generating functionally correct and
computationally efficient code, mirroring the real-world software development
standard. Our findings reveal that while LLMs demonstrate the remarkable
capability to generate functionally correct code, there still exists a
substantial gap in their efficiency output, underscoring a new frontier for
LLM research and development111Our code and date are available at
https://github.com/Elfsong/Mercury..

Mercury: An Efficiency Benchmark for LLM Code Synthesis

Mingzhe Du1,2, Anh Tuan Luu1, Bin Ji2, See-Kiong Ng2 1Nanyang Technological
University 2National University of Singapore {mingzhe001,
<EMAIL_ADDRESS>{jibin<EMAIL_ADDRESS>

##  1 Introduction

Figure 1: Mercury Dataset Overview. Each _Mercury_ task includes a task
description, a test case generator, a prompt & entry point, and corresponding
solutions. Notably, while all solutions meet the functional correctness, they
exhibit a wide array of runtimes. To evaluate code efficiency in a
standardized manner across tasks, we introduce the runtime percentile metric
_Beyond_.

Recent advances in Large Language Models (LLMs) have significantly propelled
research in software development Min et al. (2023). A surge of work
initiatives has been devoted to investigating LLMs to translate natural
language descriptions into executable code (NL2Code) Zan et al. (2023).

As a pioneer of code synthesis, CodeT5 Wang et al. (2021) leverages an
encoder-decoder framework Alom et al. (2019) to encode semantics and decode
executable code. Subsequently, strides have been made with the decoder-only
framework illustrating remarkable zero-shot code generation capabilities,
catalyzing subsequent research efforts OpenAI (2023); Shinn et al. (2023);
Zelikman et al. (2022). Meanwhile, Code-Llama Roziere et al. (2023) emerges as
a progeny of the fundamental Llama models, with derivatives specialized across
varied domains Touvron et al. (2023a, b). Parallel to model developments,
NL2code benchmarks such as HumanEval Chen et al. (2021), MBPP Austin et al.
(2021), and APPS Hendrycks et al. (2021) meticulously curate programming tasks
to gauge the functional correctness of synthesized code. To prevent data
leakage from existing pre-training datasets, HumanEval and MBPP encompassed a
small but high-quality set of handcrafted tasks, and EvalPlus further
consolidates these two benchmarks by standardizing the scope and stringency of
test cases Liu et al. (2023). On the contrary, APPS widely collected over
5,000 public coding tasks from online platforms Hendrycks et al. (2021).

Figure 2: Solutions with Distinct Runtime. Although these two solutions are
both functionally correct, their code efficiency is significantly different.

Current NL2Code benchmarks focus on code correctness but often neglect code
efficiency, which is critical for real-world applicability Xu and Zhu (2022);
Zan et al. (2023). As depicted in Figure 2, in reference to the task outlined
in Figure 1, the fast solution only requires 95 ms, whereas the slow one needs
3,402 ms. The frequent invocation of sub-optimal core functions may lead to a
compounding “Butterfly Effect” on the efficiency of the entire system,
severely impairing its practicality Lowry and Medlock (1969). Moreover, for
most programming tasks, handcrafting comprehensive test cases for all possible
scenarios is an ambitious but impractical endeavor due to the significant time
effort involved Liu et al. (2023). As a result, existing NL2Code benchmarks
default to a limited set of test cases for assessing functional correctness,
which potentially overlooks edge cases and nuanced code behaviors Chen et al.
(2021); Austin et al. (2021). Additionally, many benchmarks lack diversity and
complexity in their tasks, resulting in a performance ceiling where different
models yield similar outcomes Chen et al. (2021); Austin et al. (2021).
Recognizing these shortcomings, we have pinpointed several critical
limitations in existing NL2Code benchmarks:

Lack of Code Efficiency Evaluation. The majority of existing NL2Code
benchmarks primarily focus on functional correctness but overlook code
efficiency Xu and Zhu (2022); Zan et al. (2023). To address this problem, we
proposed the first NL2Code efficiency benchmark _Mercury_. Since the primary
obstacle to benchmark code efficiency stems from how to normalize the Runtime
of disparate tasks, we have collected actual historical submissions on
Leetcode and constructed a uniform Runtime distribution for each task. Based
on the distribution, we designed a new metric _$Beyond@K$_ to evaluate code
efficiency, where K represents the number of code synthesis samples.

Benchmarks | Tasks | Sources | Cases | Solutions | Difficulty
---|---|---|---|---|---
HumanEval | 164 | Crowd Source | 8.08 | 1 | 1
MBPP | 257 | Crowd Source | 3.01 | 1 | 1
APPS | 5,000 | Online | 21.2 | 23.04 | 3
Mercury | 256 | Online | $\infty$ | 18.4 | 3

Table 1: A comparison of the Mercury benchmark to existing benchmarks for the
NL2Code task. Mercury distinguishes itself by including a dedicated test case
generator for each task, empowering the automatic production of unlimited test
cases.

Insufficient Case Coverage. Existing benchmarks, on average, comprise less
than 10 test cases per task (see Table 1), which are insufficient to explore
the completeness of code synthesis thoroughly. As illustrated in Figure 3, the
example of HumanEval #55 contains only 3 test cases, testing up to the 10th
Fibonacci number. However, assuming that the LLM generates a recursive
algorithm that resembles the canonical solution, a stack overflow will quickly
occur when computing large Fibonacci numbers due to the recursion depth
limitation. Therefore, despite the possibility of the generated code
satisfying all crafted cases, such success does not necessarily equate to
assurance of functional correctness. To remedy this shortfall, we crafted a
dedicated test case generator for each task, which can generate infinite test
cases for comprehensive correctness and efficiency evaluation.

Lack of Divergence. Contemporary benchmarks exhibit a noticeable deficit of
diversity and complexity in their constituent tasks, rendering them
insufficiently challenging for current LLMs. Consequently, these benchmarks
fail to effectively differentiate between models, often yielding
indistinguishably similar results from models of varying capacity and size Zan
et al. (2023). To address this issue, our benchmark incorporates a tiered task
difficulty system comprising three levels. This stratification allows for a
more nuanced assessment and a clearer understanding of the proficiency of
NL2code models across varying degrees of task complexity.

Figure 3: _Mercury_ adheres to the conventional benchmark format, which is
presented as ⟨  _input_ , _output_ , _expectation_ ⟩. Within this figure,
_input_ is denoted by red chunks, _output_ is denoted by blue chunks, and
_expectation_ is denoted by green chunks. The _expectation_ signifies the
anticipated result based on the “input” provided. The test case is passed if
the output aligns with the expected result. The components encapsulated within
the dotted box come from HumanEval #55, whereas the remaining components
pertain to _Mercury_.

In this paper, we summarize our contributions as follows:

  * (1)

Dataset We introduce Mercury, a novel dataset created for fine-tuning and
assessing code efficiency in NL2Code endeavors, accompanied by an extensible
open-source collection framework for enriching Mercury with more tasks and
languages.

  * (2)

Metric We establish the first efficiency-focused metric $Beyond@K$, and
evaluated leading Code-LLMs using this criterion.

  * (3)

Optimization We conduct a comparative analysis of two baselines aimed at
enhancing code efficiency while maintaining functional correctness. The result
demonstrates that despite LLMs excelling in functional correctness, there is
still significant potential to elevate code efficiency.

##  2 The Mercury Dataset

We initiate this work by collecting all the programming questions publicly
available on Leetcode222https://leetcode.com/problemset/algorithms/.
Subjecting these questions to a series of filters, we distilled them down to
1,889 NL2Code tasks. As listed in Table 2, a difficulty-balanced subset of 256
tasks was randomly chosen to formulate the Mercury-eval benchmark, which
boasts an average of 18.4 manually verified solutions for each problem. The
remaining tasks have been designated as the Mercury-train dataset for baseline
training. To maintain clarity within this paper, our discussion centers on
Mercury-eval in this paper.

Splits | Easy | Medium | Hard | Sum
---|---|---|---|---
Training | 446 | 968 | 219 | 1,633
Evaluation | 88 | 81 | 87 | 256
Table 2: Task distributions of various difficulty levels across training and
evaluation splits in the Mercury dataset.

#### Data Schema

As illustrated in Figure 1, Mercury offers a unified data schema designed to
streamline the task evaluation procedure and bolster further development
endeavors. The data scheme encompasses these principal components: (1) _Task
Description_ contains the task statement interpreted into a plain text format,
along with illustrative examples and constraints of inputs and outputs. (2)
_Test Case Generator_ refers to a snippet of Python code designed to
automatically produce a comprehensive set of test cases in accordance with the
specifications laid out in the task description. The Mercury evaluation
framework aggregates the Runtime of all corresponding test cases to calculate
the code efficiency. (3) _Solutions_ are sampled from Leetcode historical
submissions. Each solution within Mercury has undergone rigorous testing, and
Locality-Sensitive Hashing Jafari et al. (2021) is employed to prevent the
inclusion of any identical solutions. (4) _Prompts and Entry Points_ where
prompts act as the initiating prefixes for LLM code synthesis and entry points
denote the start point for code execution. Table 6 delineates the definition
of each Mercury field.

#### Task Filters

Mercury comprises only those questions that are publicly available on
Leetcode. To assure the integrity and uniformity of the dataset, we refined
the gathered tasks based on the following conditions:

Number of Solutions. To orchestrate the running time distribution of task
solutions, we eliminated all tasks with fewer than two solutions. As
illustrated in Figure 4, Mercury evaluation tasks possess 18.4 distinctive
solutions on average.

Figure 4: Distribution of _Mercury_ Solution Count. Each task possesses 18.4
distinctive solutions on average.

Restricted Data Structure. Beyond the inherent Python data types, Mercury also
incorporates two custom data types: Binary Tree and Linked List (the specific
structure definitions can be found in Figure 5), which augments the diversity
of Mercury and escalates its challenge level. Tasks that contain other data
structures will be removed.

Unique Outputs. Certain Leetcode tasks may permit non-unique answers. For
example, a result list can be returned in any order. Evaluating all possible
answers can drastically complicate the test case verification process. To
mitigate this issue, we harnessed a test case generator to generate $N$ test
cases $T_{i}=\langle Input_{i},Output_{i}\rangle\ s.t.\
i\in\\{0,1,\cdots,N\\}$ and feed into $M$ different solutions $S_{m}\ s.t.\
m\in\\{0,1,\cdots,M\\}$ to observe if all outputs
$Output_{i}=S_{m}(Input_{i})$ remain identical. Any tasks that potentially
yield non-unique answers were subsequently excluded to facilitate the
evaluation process.

#### Task Difficulty

Most existing NL2Code benchmarks predominantly comprise simplistic tasks,
culminating in a situation where LLMs of varied sizes and capabilities yield
indistinguishable results Zan et al. (2023). To mitigate this issue, Mercury
inherits the difficulty definition from Leetcode, i.e., Easy, Medium, and
Hard, designed to probe the upper bounds of LLM performance, providing a more
evident differentiation between the capabilities of various models.

#### Test Case Generator

Case construction is time-consuming. To accumulate sufficient test cases to
conduct a comprehensive assessment, we assign a test case generator tailored
to each task, which automates the composition of diverse test cases to
thoroughly evaluate the functional correctness and efficiency of the LLM-
generated task solutions.

Specifically, we transformed the task description into a structured text
format (see $pretty\\_content$ in Table 6) and used GPT-4 OpenAI (2023) to
draft a preliminary version of the test case generator. With the drafted
generator, we created 100 distinct test cases and submitted them to the
Leetcode for online assessment. This step confirms the generator could create
test cases aligned with Leetcode standards. If the generator failed to produce
valid test cases, we revised it manually until the Leetcode evaluator accepted
all cases generated. Finally, we inspected each test case generator manually.

##  3 Code Efficiency Metric

We define absolute code efficiency as the code runtime for executing a given
test case set. Nevertheless, the primary obstacle encountered when
benchmarking code efficiency stems from how to normalize the runtime
measurements of disparate tasks. Since different tasks have diverse
computational complexities, normalization requires task-specific intervals.
For instance, an optimal algorithm tackling a complex problem might require
upwards of 1000 ms, whereas a straightforward algorithm addressing a less
demanding problem might only need 10 ms. Therefore, absolute Runtime fails as
a reliable metric to assess code efficiency across different tasks.

To address this issue, an intuitive approach involves modeling a devoted
runtime distribution for each task and calculating the runtime percentiles of
the LLM-generated solution over the historical submission. With this idea in
mind, we proposed a standardized code efficiency metric:

where $R_{A}$ represents the runtime array corresponding to the collected
solutions, $R_{k}$ is the _Runtime_ of the k-th LLM-generated solution, and
$K$ denotes the LLM solution sampling size. _Runtime_ is defined as the period
from the solution instantiation to the evaluation across all test cases,
culminating with a successful termination. Given the definition of $Beyond@K$,
any case failure of synthesized solution results in a $Beyond@K$ score of
zero, which makes $Beyond@K$ reflect the functional correctness as well. More
detail can be found in Appendix A.3.

#### Online v.s. Onsite Evaluation

As for _online evaluation_ , we can submit the synthesized solution to the
Leetcode online judge, which enables us to acquire the solution runtime
percentiles effortlessly. However, given the submission limits imposed by the
platform and the inevitability of relinquishing some degree of evaluation
process control, online evaluation is impractical for most applications. In
contrast, _onsite evaluation_ demands the implementation of an evaluation
framework as well as bespoke test case generators. However, this approach has
the distinct advantage of granting full autonomy over the assessment
procedure. In light of this control and independence, our experiments have
been conducted exclusively via onsite evaluation.

#### Untrusted Code Execution

Since most Code-LLMs are trained on an extensive code corpus from unverified
sources, there is an intrinsic risk that these models may produce malicious
code when driven by specific meticulous prompts Chen et al. (2021). The direct
execution of synthesized code raises significant security concerns. To
alleviate the risks of running untrusted code, we design a robust sandbox to
execute code in an isolation environment. Sandbox details are deliberated in
Appendix A.3

#### Limitation

In this work, we measure code efficiency under the assumption that the code
runtime is uniformly distributed, a simplification to enable code efficiency
evaluation under limited solution samples. However, the distribution of code
runtime in the real world is clearly more intricate, which may need more
solution samples to support more precise modeling. To facilitate future
research on this point, we have open-sourced our code for data collection,
thus laying the groundwork for more detailed investigations in subsequent
studies.

##  4 Experiments

In this section, we present a series of baseline experiments to improve code
efficiency using the _Mercury-train_ dataset and assess via the _Mercury-eval_
benchmark. Our empirical study encompasses five open-source LLMs a broad
parameter spectrum from 6.7 to 34 billion. For each LLM, we compare the
performance of two optimization strategies: Supervised Fine-Tuning and Direct
Preference Optimization, for their potential in optimizing LLM to generate
functionally correct and computationally efficient code. Finally, we also
analyzed the underlying factors contributing to the failure of various models
when evaluated against the Mercury benchmark.

###  4.1 Baselines

Supervised Fine-Tunning Within the Supervised Fine-Tuning (SFT) Bakker et al.
(2022) method, the model undergoes additional training on a smaller dataset,
which aims to specialize the model to perform better on tasks correlated to
the dataset. To optimize the code efficiency performance of NL2Code models,
the most intuitive strategy is to fine-tune the models on the optimal runtime
solution. In our experimental setup, we adhered to the original prompt
structure of Code-LLMs Roziere et al. (2023); Deepseek-Ai (2023) and selected
the most time-efficient solutions as the label for the supervised fine-tuning
process. Table 7 lists model prompts for code generation.

Direct Preference Optimization Although SFT exemplifies a straightforward
approach, it is susceptible to the issue of catastrophic forgetting
Kirkpatrick et al. (2017). To ensure that the model continues to align with
human preferences while preserving its functional capabilities, existing
methodologies apply reinforcement learning from human feedback (RLHF), which
involves utilizing human-crafted labels. However, RLHF introduces complexities
and potential instabilities, necessitating significant computational resources
and additional reward models Ziegler et al. (2019); Bai et al. (2022);
Stiennon et al. (2020). Direct Preference Optimization (DPO) Rafailov et al.
(2023) bypasses these challenges by explicitly mapping reward functions and
the optimal objective. This connection demonstrates that maximizing rewards
under specific constraints can be effectively addressed through a singular
training phase based on data reflecting human preferences. Consequently, DPO
provides a stable, efficient, and computation-friendly alternative, removing
the necessity for separate reward modeling. More details can be found in
Appendix A.4.

###  4.2 Functional Correctness Benchmarks

HumanEval primarily assesses functional correctness for synthesized code
derived from docstrings. It contains 164 distinct programming problems that
cover several areas, such as language comprehension, algorithm development,
and simple mathematics Chen et al. (2021).

MBPP has a sanitized collection of 257 entry-level Python programming
problems. Each problem in this dataset consists of three components: a task
description, an associated code solution, and three automated test cases to
validate the code functionality Austin et al. (2021).

###  4.3 Experimental Setups

#### Configuration

We employ LoRA Hu et al. (2021) for both SFT and DPO experiments. We set
$lora\\_alpha=16$, $lora\\_dropout=0.05$, and $lora\\_r=8$. The optimizer is
_Adamw_ Loshchilov and Hutter (2017), the batch size is $4$, and the learning
rate is 1$e$-4 and 5$e$-4 for SFT and DPO, respectively. Regarding the DPO
experiment, we set $\beta=0.1$.

#### Training Data

For the SFT process, we nominate the fastest solution as the supervised label,
then format the training data as $\langle
pretty\\_content,solution\\_optimal\rangle$. Regarding the DPO procedure, we
select the top $N$ pairs of solutions that exhibit the most significant
discrepancy in Runtime. The format for the training data is $\langle
pretty\\_content,solution\\_fast,solution\\_slow\rangle$. We set $N$ to 5 in
our experiments.

#### Environment

All experiments are conducted on two A100-80G GPUs. We employed Accelerate
Gugger et al. (2022) for distributed GPU training, Deepspeed Aminabadi et al.
(2022) for gradient partitioning, and BitsandBytes Dettmers et al. (2022) for
4-bit model quantization.

###  4.4 Empirical Results

Functional correctness is the prerequisite for evaluating code efficiency for
the code synthesis task. Our primary objective is to enhance the code
efficiency without compromising the functional correctness. To this end, we
first introduced the existing metric $Pass@1$ to gauge the functional
correctness Chen et al. (2021) and then leveraged $Beyond@K$ to provide a
holistic evaluation, encompassing both code efficiency and functional
correctness.

These experiments aim to scrutinize the innate capabilities of cutting-edge
code-LLMs and their performance after baseline fine-tuning. To deliver a
comprehensive evaluation, we have further integrated the HumanEval and MBPP
benchmarks as supplementary measures for appraising functional correctness
Chen et al. (2021); Austin et al. (2021).

#### Functional Correctness

Table 3 details the functional correctness of various models, showing that
larger models tend to provide better functional correctness. When comparing
DPO and SFT approaches, DPO consistently enhances Pass@1 scores across most
benchmarks, notably increasing model ‘deepseek-coder-33b’ from 79.30 to 85.16,
and model ‘CodeLlama-34b’ from 57.81 to 73.83 in the Mercury Benchmark. While
SFT diminishes functional correctness in larger models, it appears to benefit
smaller models. These results highlight the potential of DPO in bolstering
functional correctness on larger Code-LLMs.

Model Name | HumanEval | MBPP | Mercury
---|---|---|---
deepseek-coder-6.7b |  73.33 | 70.81 | 65.63
\+ SFT | 67.07 | 58.75 |  68.36
\+ DPO | 73.17 |  73.93 | 67.19
CodeLlama-7b |  38.41 | 38.20 | 37.50
\+ SFT | 30.49 | 29.41 |  42.19
\+ DPO | 37.20 |  39.42 | 37.89
CodeLlama-13b | 42.68 |  43.20 | 39.45
\+ SFT | 31.71 | 39.91 |  49.61
\+ DPO |  43.29 | 42.58 | 48.83
CodeLlama-34b |  44.51 | 41.65 | 57.81
\+ SFT | 39.63 | 42.39 | 67.58
\+ DPO | 43.29 |  44.57 |  73.83
deepseek-coder-33b | 75.89 |  77.82 | 79.30
\+ SFT | 71.95 | 66.93 | 81.25
\+ DPO |  76.83 | 77.04 |  85.16

Table 3: Functional correctness (Pass@1) evaluation results over LLMs. The
underlined values denote the top-performed approaches among the original model
and the established baselines.

#### Code Efficiency

Model Name | Mercury-easy | Mercury-medium | Mercury-hard | Mercury-Average
---|---|---|---|---
B@1 | B@3 | B@5 | B@1 | B@3 | B@5 | B@1 | B@3 | B@5 | B@1 | B@3 | B@5
deepseek-coder-6.7b | 63.55 | 72.55 |  75.19 |  58.80 | 65.70 | 67.28 |  45.72 | 48.52 | 50.58 |  55.99 | 62.22 | 64.33
\+ SFT | 57.70 | 72.57 | 75.18 | 54.87 | 65.24 | 66.77 | 41.87 | 47.54 | 49.62 | 51.42 | 61.74 | 63.83
\+ DPO |  58.29 |  73.03 | 75.65 | 55.86 |  66.15 |  67.77 | 43.70 |  49.52 |  51.54 | 52.56 |  62.87 |  64.96
CodeLlama-7b |  46.49 | 55.33 | 56.37 | 36.08 | 46.02 | 49.05 | 6.83 | 9.46 | 9.48 | 29.72 | 36.79 | 38.12
\+ SFT | 42.57 | 52.48 | 54.54 | 37.48 | 40.54 | 45.48 | 5.11 | 3.97 | 4.86 | 28.23 | 32.22 | 34.79
\+ DPO | 45.90 |  55.87 |  56.83 |  40.58 |  46.54 |  49.57 |  8.32 |  10.41 |  10.47 |  31.45 |  37.47 |  38.78
CodeLlama-13b |  42.30 | 48.47 | 52.79 | 39.95 | 53.32 | 55.60 | 7.94 | 14.61 | 15.75 | 29.88 | 38.50 | 41.09
\+ SFT | 42.21 | 54.90 | 56.36 | 35.54 | 44.47 | 47.71 | 3.10 | 8.78 | 9.68 | 26.81 | 35.92 | 37.76
\+ DPO | 40.08 |  54.50 |  59.67 |  40.99 |  59.19 |  61.18 |  13.70 |  19.16 |  20.54 |  31.40 |  43.97 |  46.85
CodeLlama-34b | 62.50 | 74.35 | 77.58 | 54.02 | 65.84 | 67.17 | 23.17 | 24.02 | 28.51 | 46.45 | 54.55 | 57.61
\+ SFT | 64.49 | 78.51 | 83.99 | 53.88 | 69.47 | 71.00 | 15.17 | 22.09 | 27.52 | 44.37 | 56.48 | 60.69
\+ DPO |  71.62 |  84.24 |  87.89 |  63.15 |  74.81 |  76.14 |  27.30 |  32.19 |  36.41 |  53.88 |  63.57 |  66.68
deepseek-coder-33b | 67.92 | 76.61 | 78.78 | 67.18 | 73.34 | 76.27 | 52.36 | 58.79 | 59.43 | 62.40 | 69.52 | 71.41
\+ SFT | 68.58 | 79.85 | 83.04 | 67.16 | 76.10 | 79.38 | 45.09 | 55.55 | 57.87 | 60.15 | 70.41 | 73.33
\+ DPO |  77.83 |  86.06 |  88.83 |  75.15 |  83.08 |  85.20 |  60.52 |  66.70 |  67.64 |  71.10 |  78.53 |  80.48

Table 4: Code Efficiency Evaluation Results Categorized by Difficulty Levels.
The notation $B@K$ represents the $Beyond@K$ score with $K$ generated
solutions. The bolded value indicates the top performance for each metric,
while the underlined values denote the most effective approaches among the
original model and the baselines.

Regarding the NL2Code task, once functional correctness has been assured,
attention naturally pivots to enhancing code efficiency. As depicted in Table
4, we investigate code efficiency metrics across a spectrum of LLMs and
varying task difficulty. Our findings indicate that DPO yields a more stable
enhancement in code efficiency, particularly for larger models. Notably, the
model ‘deepseek-coder-33b’ emerged the state-of-the-art results over all
difficulties using DPO. Moreover, we found there is a clear inverse
relationship between task difficulty and code efficiency metrics, consistent
across models of different sizes.

###  4.5 Failure Analysis

Model Name | Generation | Execution | Cases
---|---|---|---
E | M | H | E | M | H | E | M | H
deepseek-coder-6.7b | 16 | 16 | 9 | 2 | 4 | 9 | 6 | 5 | 21
\+ SFT | 4 | 2 | 5 | 3 | 3 | 10 | 12 | 12 | 30
\+ DPO | 2 | 1 | 4 | 1 | 0 | 4 | 18 | 14 | 40
CodeLlama-7b | 4 | 3 | 3 | 3 | 8 | 12 | 28 | 35 | 64
\+ SFT | 1 | 2 | 0 | 8 | 12 | 19 | 30 | 28 | 48
\+ DPO | 1 | 0 | 1 | 4 | 6 | 10 | 30 | 40 | 67
CodeLlama-13b | 2 | 2 | 1 | 4 | 8 | 16 | 31 | 32 | 59
\+ SFT | 1 | 0 | 6 | 4 | 7 | 12 | 22 | 29 | 48
\+ DPO | 1 | 1 | 0 | 3 | 9 | 10 | 28 | 36 | 43
CodeLlama-34b | 1 | 0 | 0 | 2 | 10 | 16 | 14 | 17 | 48
\+ SFT | 1 | 2 | 1 | 8 | 5 | 18 | 12 | 10 | 26
\+ DPO | 4 | 0 | 1 | 0 | 1 | 8 | 10 | 13 | 30
deepseek-coder-33b | 7 | 5 | 4 | 0 | 1 | 6 | 4 | 8 | 18
\+ SFT | 3 | 1 | 8 | 2 | 0 | 4 | 3 | 7 | 20
\+ DPO | 2 | 1 | 7 | 1 | 1 | 3 | 2 | 4 | 17

Table 5: The distribution of failure cases across Generation, Execution, and
Test Case error categories. E/M/H indicates Easy/Medium/Hard levels,
respectively.

Table 5 provides a quantitative breakdown of where Code-LLMs have misstepped
during the evaluation against the Mercury benchmark. These failures were
systematically classified into the following three distinct types:

#### Generation Errors

These errors arise from syntactical inaccuracies in the code produced by LLMs,
which result in unsuccessful instantiation. Common manifestations of
generation errors include improper indentation, mismatched parentheses, or the
unexpected truncation of the code, particularly when the output extends beyond
a predefined length limit. Fine-tuning introduces additional knowledge for
LLMs to adapt the Mercury convention, emphasizing standard indentation,
concise code, and minimal comments. Therefore, both SFT and DPO generally
reduced generation errors across most original models.

#### Execution Errors

Execution Errors differ from Generation Errors because they occur after the
synthesized code has been successfully instantiated. During the test case
execution phase, these errors emerge as exceptions, which could stem from
various issues, such as flawed logic within the code, execution timeouts,
memory leakage, or operations deemed unsafe by the sandboxing environment. We
observe that SFT tends to elevate the occurrence of execution errors across
most models. This implies that, although SFT may aid LLMs in producing
syntactically sound code, it potentially induces catastrophic forgetting,
undermining the proficiency of models in crafting logically correct code. In
contrast, DPO not only boosts code efficiency but also maintains logical code
generation more reliably.

#### Test Case Errors

The most prevalent error category encountered is Test Case Errors. In this
scenario, although the code is instantiated without issue and executes without
triggering exceptions, the output yielded by the test case execution fails to
align with the expected results. Analyzing the data in Table 5, we observed
that increased task difficulty correlates with higher failure rates of the
test cases for the same model. While comparing tasks of equivalent difficulty,
models with larger capacities demonstrate superior performance. Furthermore,
we noted a nuanced contrast between optimization techniques: while SFT appears
marginally more effective for smaller models, DPO exhibits significant
benefits when applied to larger models.

##  5 Related Work

#### NL2Code Synthesis

Code synthesis is the task of generating a computer program that satisfies
given specifications. Initial approaches to converting natural language to
code relied on rigid methods like probabilistic grammars and domain-specific
languages, having limited flexibility and scalability Joshi and Rambow (2003);
De Moura and Bjørner (2008). The advent of statistical models, such as n-grams
and Hidden Markov models, attempted to overcome these limitations but
struggled with modeling complexity and dependencies Nguyen et al. (2013);
Sutskever et al. (2008). The transformational impact of the Transformer model
Vaswani et al. (2017) and its subsequent application to NL2Code Mastropaolo et
al. (2021) led to the development of LLMs like Codex, which significantly
improved the task’s feasibility by utilizing extensive unlabelled data sets
Chen et al. (2021). Follow-up LLMs such as AlphaCode Li et al. (2022), CodeGen
Nijkamp et al. (2022), PaLM-Coder Chowdhery et al. (2022), and StarCoder Li et
al. (2023) continued to advance the field, exhibiting emergent abilities in
coding and debugging that mirrored human programmers.

#### NL2Code Evaluation

Most existing NL2Code benchmarks focus on gauging the functional correctness
of generated code. As a pioneer, CodeBLEU Ren et al. (2020) adapts the BLEU
Papineni et al. (2002) metric into code generation. However, given the
inherently abstract nature of programming languages, distinct code fragments
can express the equivalent semantics, prompting subsequent benchmarks to
harness test cases instead of conventional similarity measurements routinely.
For example, HumanEval Chen et al. (2021) and MBPP Austin et al. (2021)
consist of hand-written Python programming tasks and corresponding test cases.
On the note of enhancing linguistic inclusiveness, ODEX Wang et al. (2022)
integrates multiple natural languages, while MBXP Athiwaratkun et al. (2022)
extends the benchmarks to cater to a variety of programming languages,
promoting polyglot code generation evaluation. Recent benchmarks have also
begun to consider more specific beyond functional correctness. Within the
realm of data science, the benchmark DS-100 Lai et al. (2023) addresses the
need to generate code in data analysis scenarios, while CodeGen Nijkamp et al.
(2022) contributes a benchmark for multi-turn code synthesis. For security-
oriented code generation, SecurityEval Siddiq and Santos (2022) has offered a
focused benchmark on code security.

##  6 Conclusion

In this work, we introduced Mercury, the first code efficiency benchmark for
NL2Code evaluation. Unlike prior work that focused on functional correctness,
our benchmark highlights the importance of code efficiency. By crafting
dedicated test case generators and sampling ground-truth solutions across
different difficulty levels from Leetcode, we have developed a comprehensive
and rigorous Code-LLM evaluation frame. We evaluated the state-of-the-art
Code-LLMs against benchmarks and found that even though these models are
proficient in generating functionally correct code, there is still
considerable space for code efficiency improvement. As Code-LLMs become more
widely used, code efficiency determines factual productivity, where Mercury
can gauge the vital metric. As a commitment to ongoing research and to foster
further innovation in this area, we have open-sourced the Mercury dataset
collection framework, laying the groundwork for future advancements in the
field.

## References

  * Alom et al. (2019) Md Zahangir Alom, Tarek M Taha, Chris Yakopcic, Stefan Westberg, Paheding Sidike, Mst Shamima Nasrin, Mahmudul Hasan, Brian C Van Essen, Abdul AS Awwal, and Vijayan K Asari. 2019.  A state-of-the-art survey on deep learning theory and architectures.  _electronics_ , 8(3):292.
  * Aminabadi et al. (2022) Reza Yazdani Aminabadi, Samyam Rajbhandari, Ammar Ahmad Awan, Cheng Li, Du Li, Elton Zheng, Olatunji Ruwase, Shaden Smith, Minjia Zhang, Jeff Rasley, et al. 2022.  Deepspeed-inference: enabling efficient inference of transformer models at unprecedented scale.  In _SC22: International Conference for High Performance Computing, Networking, Storage and Analysis_ , pages 1–15. IEEE.
  * Athiwaratkun et al. (2022) Ben Athiwaratkun, Sanjay Krishna Gouda, Zijian Wang, Xiaopeng Li, Yuchen Tian, Ming Tan, Wasi Uddin Ahmad, Shiqi Wang, Qing Sun, Mingyue Shang, et al. 2022.  Multi-lingual evaluation of code generation models.  _arXiv preprint arXiv:2210.14868_.
  * Austin et al. (2021) Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al. 2021.  Program synthesis with large language models.  _arXiv preprint arXiv:2108.07732_.
  * Bai et al. (2022) Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. 2022.  Training a helpful and harmless assistant with reinforcement learning from human feedback.  _arXiv preprint arXiv:2204.05862_.
  * Bakker et al. (2022) Michiel Bakker, Martin Chadwick, Hannah Sheahan, Michael Tessler, Lucy Campbell-Gillingham, Jan Balaguer, Nat McAleese, Amelia Glaese, John Aslanides, Matt Botvinick, et al. 2022.  Fine-tuning language models to find agreement among humans with diverse preferences.  _Advances in Neural Information Processing Systems_ , 35:38176–38189.
  * Chen et al. (2021) Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. 2021.  Evaluating large language models trained on code.  _arXiv preprint arXiv:2107.03374_.
  * Chowdhery et al. (2022) A Chowdhery, S Narang, J Devlin, M Bosma, G Mishra, A Roberts, P Barham, HW Chung, C Sutton, S Gehrmann, et al. 2022.  Palm: Scaling language modeling with pathways (no. arxiv: 2204.02311). arxiv.
  * De Moura and Bjørner (2008) Leonardo De Moura and Nikolaj Bjørner. 2008.  Z3: An efficient smt solver.  In _International conference on Tools and Algorithms for the Construction and Analysis of Systems_ , pages 337–340. Springer.
  * Deepseek-Ai (2023) Deepseek-Ai. 2023.  Deepseek-ai/deepseek-coder: Deepseek coder: Let the code write itself.
  * Dettmers et al. (2022) Tim Dettmers, Mike Lewis, Younes Belkada, and Luke Zettlemoyer. 2022.  Llm.int8(): 8-bit matrix multiplication for transformers at scale.  _arXiv preprint arXiv:2208.07339_.
  * Gugger et al. (2022) Sylvain Gugger, Lysandre Debut, Thomas Wolf, Philipp Schmid, Zachary Mueller, Sourab Mangrulkar, Marc Sun, and Benjamin Bossan. 2022.  Accelerate: Training and inference at scale made simple, efficient and adaptable.  https://github.com/huggingface/accelerate.
  * Hendrycks et al. (2021) Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, et al. 2021.  Measuring coding challenge competence with apps.  _arXiv preprint arXiv:2105.09938_.
  * Hu et al. (2021) Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. 2021.  Lora: Low-rank adaptation of large language models.  _arXiv preprint arXiv:2106.09685_.
  * Jafari et al. (2021) Omid Jafari, Preeti Maurya, Parth Nagarkar, Khandker Mushfiqul Islam, and Chidambaram Crushev. 2021.  A survey on locality sensitive hashing algorithms and their applications.  _arXiv preprint arXiv:2102.08942_.
  * Joshi and Rambow (2003) Aravind Joshi and Owen Rambow. 2003.  A formalism for dependency grammar based on tree adjoining grammar.  In _Proceedings of the Conference on Meaning-text Theory_ , pages 207–216. MTT Paris, France.
  * Kirkpatrick et al. (2017) James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A. Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinska, Demis Hassabis, Claudia Clopath, Dharshan Kumaran, and Raia Hadsell. 2017.  Overcoming catastrophic forgetting in neural networks.  _Proceedings of the National Academy of Sciences - PNAS_ , 114(13):3521–3526.
  * Lai et al. (2023) Yuhang Lai, Chengxi Li, Yiming Wang, Tianyi Zhang, Ruiqi Zhong, Luke Zettlemoyer, Wen-tau Yih, Daniel Fried, Sida Wang, and Tao Yu. 2023.  Ds-1000: A natural and reliable benchmark for data science code generation.  In _International Conference on Machine Learning_ , pages 18319–18345. PMLR.
  * Li et al. (2023) Raymond Li, Loubna Ben Allal, Yangtian Zi, Niklas Muennighoff, Denis Kocetkov, Chenghao Mou, Marc Marone, Christopher Akiki, Jia Li, Jenny Chim, et al. 2023.  Starcoder: may the source be with you!  _arXiv preprint arXiv:2305.06161_.
  * Li et al. (2022) Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. 2022.  Competition-level code generation with alphacode.  _Science_ , 378(6624):1092–1097.
  * Liu et al. (2023) Jiawei Liu, Chunqiu Steven Xia, Yuyao Wang, and Lingming Zhang. 2023.  Is your code generated by chatgpt really correct?  _arXiv_.
  * Loshchilov and Hutter (2017) Ilya Loshchilov and Frank Hutter. 2017.  Decoupled weight decay regularization.  _arXiv preprint arXiv:1711.05101_.
  * Lowry and Medlock (1969) Edward S Lowry and Cleburne W Medlock. 1969.  Object code optimization.  _Communications of the ACM_ , 12(1):13–22.
  * Mastropaolo et al. (2021) Antonio Mastropaolo, Simone Scalabrino, Nathan Cooper, David Nader Palacio, Denys Poshyvanyk, Rocco Oliveto, and Gabriele Bavota. 2021.  Studying the usage of text-to-text transfer transformer to support code-related tasks.  In _2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE)_ , pages 336–347. IEEE.
  * Min et al. (2023) Bonan Min, Hayley Ross, Elior Sulem, Amir Pouran Ben Veyseh, Thien Huu Nguyen, Oscar Sainz, Eneko Agirre, Ilana Heintz, and Dan Roth. 2023.  Recent advances in natural language processing via large pre-trained language models: A survey.  _ACM Computing Surveys_ , 56(2):1–40.
  * Nguyen et al. (2013) Tung Thanh Nguyen, Anh Tuan Nguyen, Hoan Anh Nguyen, and Tien N Nguyen. 2013.  A statistical semantic language model for source code.  In _Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering_ , pages 532–542.
  * Nijkamp et al. (2022) Erik Nijkamp, Bo Pang, Hiroaki Hayashi, Lifu Tu, Huan Wang, Yingbo Zhou, Silvio Savarese, and Caiming Xiong. 2022.  Codegen: An open large language model for code with multi-turn program synthesis.  _arXiv preprint arXiv:2203.13474_.
  * OpenAI (2023) R OpenAI. 2023.  Gpt-4 technical report.  _arXiv_ , pages 2303–08774.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  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.
  * Rafailov et al. (2023) Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D Manning, and Chelsea Finn. 2023.  Direct preference optimization: Your language model is secretly a reward model.  _arXiv preprint arXiv:2305.18290_.
  * Ren et al. (2020) Shuo Ren, Daya Guo, Shuai Lu, Long Zhou, Shujie Liu, Duyu Tang, Neel Sundaresan, Ming Zhou, Ambrosio Blanco, and Shuai Ma. 2020.  Codebleu: a method for automatic evaluation of code synthesis.  _arXiv preprint arXiv:2009.10297_.
  * Roziere et al. (2023) Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, et al. 2023.  Code llama: Open foundation models for code.  _arXiv preprint arXiv:2308.12950_.
  * Shinn et al. (2023) Noah Shinn, Beck Labash, and Ashwin Gopinath. 2023.  Reflexion: an autonomous agent with dynamic memory and self-reflection.  _arXiv preprint arXiv:2303.11366_.
  * Siddiq and Santos (2022) Mohammed Latif Siddiq and Joanna CS Santos. 2022.  Securityeval dataset: mining vulnerability examples to evaluate machine learning-based code generation techniques.  In _Proceedings of the 1st International Workshop on Mining Software Repositories Applications for Privacy and Security_ , pages 29–33.
  * Stiennon et al. (2020) Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. 2020.  Learning to summarize with human feedback.  _Advances in Neural Information Processing Systems_ , 33:3008–3021.
  * Sutskever et al. (2008) Ilya Sutskever, Geoffrey E Hinton, and Graham W Taylor. 2008.  The recurrent temporal restricted boltzmann machine.  _Advances in neural information processing systems_ , 21.
  * Touvron et al. (2023a) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. 2023a.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_.
  * Touvron et al. (2023b) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. 2023b.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _Advances in neural information processing systems_ , 30.
  * Wang et al. (2021) Yue Wang, Weishi Wang, Shafiq Joty, and Steven CH Hoi. 2021.  Codet5: Identifier-aware unified pre-trained encoder-decoder models for code understanding and generation.  _arXiv preprint arXiv:2109.00859_.
  * Wang et al. (2022) Zhiruo Wang, Shuyan Zhou, Daniel Fried, and Graham Neubig. 2022.  Execution-based evaluation for open-domain code generation.  _arXiv preprint arXiv:2212.10481_.
  * Xu and Zhu (2022) Yichen Xu and Yanqiao Zhu. 2022.  A survey on pretrained language models for neural code intelligence.  _arXiv preprint arXiv:2212.10079_.
  * Zan et al. (2023) Daoguang Zan, Bei Chen, Fengji Zhang, Dianjie Lu, Bingchao Wu, Bei Guan, Wang Yongji, and Jian-Guang Lou. 2023.  Large language models meet nl2code: A survey.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 7443–7464.
  * Zelikman et al. (2022) Eric Zelikman, Qian Huang, Gabriel Poesia, Noah D Goodman, and Nick Haber. 2022.  Parsel: A unified natural language framework for algorithmic reasoning.  _arXiv preprint arXiv:2212.10561_.
  * Ziegler et al. (2019) Daniel M Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. 2019.  Fine-tuning language models from human preferences.  _arXiv preprint arXiv:1909.08593_.

##  Appendix A Appendix

###  A.1 Definition of Mercury Fields

Field Name | Definition
---|---
id | Task ID.
slug_name | Task name.
meta_info | The field accommodating the task description and submission statistics.
difficulty | The difficulty level of the task.
pretty_content | The field introduces the task description, examples, and constraints in pure text.
solutions | Samples of solutions extracted from actual past submissions.
prompt | The prompt of the solution.
entry_point | The nominative entry point of the solution.
generator_code | A function to generate test cases.
test_cases | A collection of generated test cases.
convert_online | A function to format test cases for online evaluation.
convert_offline | A function to format test cases for offline evaluation.
evaluate_offline | A function designed to evaluate solutions in an offline setting.
Table 6: Definitions of the fields within the Mercury dataset.

###  A.2 Customized Data Structures in Mercury

Except for all built-in Python data structures, Mercury imports another two
structures to enhance the diversity and complexity as shown in Figure 5.

Figure 5: Mercury supports two customized data structures: TreeNode and
ListNode.

###  A.3 Sandbox Details

#### Time and Memory Limitation

Each executed code within the sandbox is subject to certain constraints to
ensure fair utilization of resources and to prevent any single program from
monopolizing the system. Specifically, there are two primary constraints: a
time limit and a memory limit. The time limit restricts how long the code can
execute before being forcibly terminated, thereby ensuring that no infinite
loops or excessively long computations negatively impact the availability of
the sandbox. The memory limit caps the amount of RAM that a process can
consume. This measure prevents a single program from exhausting the server’s
memory resources, which could lead to a denial of service for other users or
processes sharing the same infrastructure.

#### IO Restriction

To mitigate harmful activities such as unauthorized data access or data
exfiltration, the sandbox imposes strict input/output (IO) restrictions. These
restrictions can include limitations on the size and type of files that can be
read from or written to the disk and restrictions on the use of network
sockets for sending or receiving data. By controlling the IO operations, the
sandbox can prevent many common exploits and ensure that the code running
within it cannot interfere with other processes or the host system.

#### Isolated File System

The sandbox employs an isolated file system to provide a safe execution
environment for the code. This means that the process running in the sandbox
has its virtual file system, which is separated from the host’s file system.
The isolated nature of this file system ensures that even if a process within
the sandbox attempts to modify or delete files, these changes will not affect
the host system or other sandboxes. It acts as a layer of security, protecting
the host from potential threats and maintaining the integrity of the overall
system.

#### System Libraries Redirection

To maintain a consistent and controlled environment, the sandbox redirects
calls to system libraries to sandbox-specific versions. This is done to
prevent code from using certain functions directly from the host’s system
libraries, which could result in unpredictable behavior or security
vulnerabilities. The redirected libraries are often limited to a subset of
functionalities deemed safe and necessary for executing programs within the
sandbox, thus enforcing the security policies and ensuring that the running
programs behave as expected.

#### Single-threaded Evaluation

In the context of the sandbox environment, single-threaded evaluation is the
process of executing code using only one thread of execution. This approach
simplifies resource management and timing measurements, avoiding the
complexities associated with multi-threaded execution, such as
synchronization, race conditions, and deadlocks. Single-threading can be
particularly important in educational or testing settings where
reproducibility and fairness are critical, ensuring that every student or
user’s code is evaluated with the same computational resources.

#### Code Efficiency Measurement

Figure 6 shows the overview of the code execution pipeline. We gauge the
_Solution Instantiation_ and _Test Ease Evaluation_ time spans as the
execution runtime.

Figure 6:  Sandbox Execution Pipeline. 1) Test Case Generation. We first
employ the corresponding test case generator for each task to produce a
comprehensive set of test cases for the subsequent evaluation. 2) Context
Initialization. To prevent any unexpected code behavior, the sandbox
environment is meticulously reinitialized for each new task. This phase
ensures that all the common libraries required for executing the solution are
loaded. 3) Solution Instantiation. The solution under evaluation will be
encapsulated as a _solution_ class. 4) Test Case Evaluation. Each test case
the generator provides will be rigorously executed against the solution. A
solution must successfully pass all the test cases to be deemed valid. 5)
Clean up. The final stage involves the sandbox dutifully clearing the
namespace environment and the temporary directory. Mercury records the time
consumed during the stage of Solution instantiation and Test Ease Evaluation
as the primary metric for assessing code efficiency.

###  A.4 DPO Experiment Details

#### Dataset Construction

For every task problem $T^{i}$ in Mercury, we randomly selected two solutions
from the task solution set $\\{s^{i}_{w},s^{i}_{l}\\}\sim T^{i}_{solution}$,
to construct the preference dataset $D=\\{P^{i},s^{i}_{w},s^{i}_{l}\\}$, where
$p^{i}$ is the prompt, $s^{i}_{w}$ has a faster runtime than $s^{i}_{l}$.

#### Model Initialization

RLHF Ziegler et al. (2019) typically begins with a reference LLM $\pi_{ref}$.
Here, we initialize $\pi_{ref}$ by maximizing the likelihood of faster code
completions $(p,s_{w})\sim D$, so that
$\pi_{ref}=\arg\max_{\pi}E_{(p,s_{w})\sim D}\left[\log\pi(s_{w}|p)\right]$.
This procedure helps mitigate the distribution shift between the _true
reference distribution_ and $\pi_{ref}$.

#### Optimization

We optimize the target LLM $\pi_{\theta}$ to minimize $\mathcal{L}_{DPO}$ for
the given $\pi_{ref}$ and $D$ and desired hyperparameter $\beta$. The gradient
with respect to the parameters $\theta$ can be written as
$\nabla_{\theta}\mathcal{L}_{DPO}(\pi_{\theta};\pi_{ref})$.

$\mathcal{L}_{DPO}(\pi_{\theta};\pi_{ref})=-E_{(x,s_{w},s_{l})\sim
D}\left[\log\alpha(\beta\log\frac{\pi_{\theta}(s_{w}|p)}{\pi_{ref}(s_{w}|p)})-\log\frac{\pi_{\theta}(s_{l}|p)}{\pi_{ref}(s_{l}|p)})\right]$
(1)

$\nabla_{\theta}\mathcal{L}_{DPO}(\pi_{\theta};\pi_{ref})=\\\ -\beta
E_{(p,s_{w},s_{l})\sim
D}\left[\underbrace{\alpha(\hat{r}_{\theta}(p,s_{l})-\hat{r}_{\theta}(p,s_{w}))}_{\textit{higher
weight for wrong
estimate}}\left[\underbrace{\nabla_{\theta}\log\pi(s_{w}|p)}_{\textit{increase
likelihood of
$s_{w}$}}-\underbrace{\nabla_{\theta}\log\pi(s_{l}|p)}_{\textit{decrease
likelihood of $s_{l}$}}\right]\right]$ (2)

Intuitively, the gradient of the loss function $\mathcal{L}_{DPO}$ increases
the likelihood of the preferred completions $s_{w}$ and decreases the
likelihood of dis-preferred completions $s_{l}$, which are weighed by how much
higher the implicit reward model $\hat{r}_{\theta}$ rates the dis-preferred
completions, scaled by $\beta$, i.e., how incorrectly the implicit reward
model orders the completions, accounting for the strength of the KL
constraint.

###  A.5 External Libraries Utilized in Mercury

Raw LeetCode solutions typically commence without importing shared libraries.
To avoid solution failure due to absent libraries, we proactively import the
libraries listed in Figure 7 during the sandbox _Context Initialization_
phase. Note that all these libraries are imported in a temporary namespace of
which the sandbox controls code behaviors.

Figure 7: External Libraries Imported in Mercury Evaluate Framework.

###  A.6 Prompts for Code Generation

To ensure the preservation of the pre-trained proficiency of each model, we
adhere strictly to the original prompts listed in Table 7 during both the
inference phase and the fine-tuning procedure. The _code_prompt_ is essential
in steering the model toward producing valid code completions.

Model Name | Prompt
---|---
DeepSeek | Complete python3 code to solve the following coding problem:\n{content}\n{code_prompt}
Code-Llama | Complete python3 code to solve the following coding problem.\n{content}\n{code_prompt}
OpenAI |  | Complete python3 code to solve the following coding problem in the JSON format:
---
{{’completion’: ’<completion_starts_with_prompt>’
}}\nProblem:\n{content}\nPrompt:\n{code_prompt}

Table 7: Code Generation Prompts. In Mercury experiments, we feed the
_pretty_content_ field to the placeholder _content_ , and the _prompt_ field
to the placeholder _code_prompt_.

###  A.7 A Mercury Example

Figure 8: This case is drawn from the _Mercury-eval_ benchmark. The upper
block presents the problem statement with its example, while the subsequent
portion exhibits the corresponding solutions. Although all solutions provided
are functionally correct, they exhibit significant differences in runtimes.


# Linking disjoint segments into a simple polygon is hard

Rain Jiang  Kai Jiang  Minghui Jiang
Home School, USA  dr.minghui.jiang at gmail.com

###### Abstract

Deciding whether a family of disjoint line segments in the plane can be linked
into a simple polygon (or a simple polygonal chain) by adding segments between
their endpoints is NP-hard.

##  1 Introduction

Given a family $\mathcal{S}$ of $n$ closed line segments in the plane, Simple
Circuit (respectively, Simple Path) is the problem of deciding whether these
segments can be linked into a simple polygon (respectively, a simple polygonal
chain) by adding segments between their endpoints.

Rappaport [4] proved that Simple Circuit is NP-hard if the segments in
$\mathcal{S}$ are allowed to intersect at their common endpoints, and asked
whether the problem remains NP-hard when the segments are disjoint. Later,
Bose, Houle, and Toussaint [3] asked whether the related problem Simple Path
is NP-hard when the segments in $\mathcal{S}$ are disjoint. More recently,
Tóth [6] asked about the complexity of Simple Path again, with a special
interest in the case when the segments in $\mathcal{S}$ are both disjoint and
axis-parallel.

In this note, we prove the following theorem:

######  Theorem 1.

Simple Circuit and Simple Path are both NP-hard even if the segments in
$\mathcal{S}$ are disjoint and have only four distinct orientations.

We prove the theorem in two steps. First, we modify the construction in
Rappaport’s proof of NP-hardness of Simple Circuit on not necessarily disjoint
segments [4] to show that the problem remains NP-hard on disjoint segments.
Next, we modify the construction further to prove that Simple Path is also NP-
hard on disjoint segments. In the following, we briefly review Rappaport’s
proof, which is based on a polynomial reduction from the NP-hard problem
Hamiltonian Path in planar cubic graphs.

For any family $\mathcal{S}$ of closed segments in the plane, denote by
$V(\mathcal{S})$ the set of endpoints of the segments in $\mathcal{S}$. For
any two endpoints $p$ and $q$ in $V(\mathcal{S})$, we call the open segment
$pq$ a _visibility edge_ if it does not intersect any closed segment in
$\mathcal{S}$.

Given a planar cubic graph $G$ with $n\geq 4$ vertices, the reduction [4]
first obtains a rectilinear planar layout of the planar graph using an
algorithm of Rosenstiehl and Tarjan [5], then constructs a family
$\mathcal{S}$ of $O(n)$ segments following the rectilinear planar layout, such
that $G$ admits a Hamiltonian path if and only if $\mathcal{S}$ can be linked
into a simple polygon by adding visibility edges between points in
$V(\mathcal{S})$. The segments in $\mathcal{S}$ are axis-parallel and
interior-disjoint, but may intersect at common endpoints. Each endpoint in
$V(\mathcal{S})$ is incident to at most one horizontal segment and at most one
vertical segment in $\mathcal{S}$. Since the rectilinear planar layout is of
width at most $2n-4$ and of height at most $n$ [5], all coordinates of
endpoints in $V(\mathcal{S})$ are integers of magnitude $O(n^{2})$; indeed a
closer look at the construction [4, Figure 8] shows that
$V(\mathcal{S})\subseteq[1,22n^{2}]\times[1,11n]$. The reduction is hence
strongly polynomial. Consequently, Simple Circuit is strongly NP-hard, on not
necessarily disjoint segments.

##  2 Modification for Simple Circuit

To show that Simple Circuit remains strongly NP-hard on disjoint segments, we
will transform the family $\mathcal{S}$ of interior-disjoint axis-parallel
segments, which Rappaport constructed, into a family $\mathcal{S}^{\prime}$ of
disjoint segments with four distinct orientations, in polynomial time, such
that $\mathcal{S}$ can be linked into a simple polygon if and only if
$\mathcal{S}^{\prime}$ can be linked into a simple polygon. This
transformation can be viewed as a reduction from Simple Circuit on one type of
input to the same problem on another type of input.

Figure 1: Gadgets for intersections of four different orientations.

To obtain $\mathcal{S}^{\prime}$ from $\mathcal{S}$, we first scale the
integer coordinates of all segment endpoints by a factor of $40$, then locally
modify each intersection between a horizontal segment and a vertical segment
into a gadget. The gadgets come in four variants, one for each possible
orientation of an intersection; see Figure 1. For a global picture of these
modifications on a rectilinear simple polygon with intersections of all four
different orientations, refer to Figure 2.

Figure 2: Local modifications of the intersections a rectilinear simple
polygon into gadgets of disjoint segments.

Figure 3: The gadget for the intersection $o$ between a horizontal segment
$oa$ and a vertical segment $ob$. Left: The coordinates of the segment
endpoints relative to $o$ are $o=(0,0)$, $o^{\prime}=(-4,0)$,
$o^{\prime\prime}=(0,1)$, $a^{\prime}=(16,1)$, $b^{\prime}=(1,16)$,
$A_{1}=8\times[3,7]$, $B_{1}=9\times[4,5]$, $A_{2}=[3,7]\times 8$,
$B_{2}=[4,5]\times 9$. The lower endpoint $a_{1}$ of $A_{1}$ is collinear with
the two points $o^{\prime}$ and $o^{\prime\prime}$. Right: An alternating path
of segments and visibility edges in the gadget after extending $A_{1}$ to
$A^{\prime}_{1}$. The lower endpoint $a^{\prime}_{1}$ of $A^{\prime}_{1}$ can
see the segment $o^{\prime}a$ at the endpoint $o^{\prime}$.

By symmetry, it suffices to describe in detail only one variant of the gadget.
Refer to Figure 3. For the intersection $o$ between a horizontal segment $oa$
and a vertical segment $ob$, where $o$ is the left endpoint of $oa$ and the
lower endpoint of $ob$, the corresponding gadget is constructed as follows.
First, separate the two segments $oa$ and $ob$ into two disjoint segments
$o^{\prime}a$ and $o^{\prime\prime}b$, by splitting their common endpoint $o$,
then moving one to $o^{\prime}$ and the other to $o^{\prime\prime}$. Next, add
five disjoint segments $A_{1}$, $B_{1}$, $A_{2}$, $B_{2}$, and
$a^{\prime}b^{\prime}$. Finally, extend the segment $A_{1}$ to a slightly
longer segment $A^{\prime}_{1}$ by moving its lower endpoint down for a
distance of $\delta=\frac{1}{800n^{2}}$, from $a_{1}=(8,3)$ to
$a^{\prime}_{1}=(8,3-\delta)$.

In the presence of $\mathcal{S}^{\prime}$, we say that two points $p$ and $q$
can _see_ each other if the open segment $pq$ is disjoint from all closed
segments in $\mathcal{S}^{\prime}$, and we say that two segments $A$ and $B$
in $\mathcal{S}^{\prime}$ can _see_ each other if at least one of the four
pairs of endpoints, one of $A$ and one of $B$, can see each other. The gadgets
we constructed have the following property of mutual invisibility:

######  Lemma 1.

The four segments $A^{\prime}_{1}$, $B_{1}$, $A_{2}$, and $B_{2}$ in each
gadget cannot see any segments in other gadgets. Moreover, in each gadget,
$B_{1}$ can only see $A^{\prime}_{1}$ and $a^{\prime}b^{\prime}$, $B_{2}$ can
only see $A_{2}$ and $a^{\prime}b^{\prime}$, $A_{2}$ cannot see $o^{\prime}a$
and can see $o^{\prime\prime}b$ only at $o^{\prime\prime}$, and
$A^{\prime}_{1}$ can see $o^{\prime}a$ only at $o^{\prime}$.

Figure 4: The narrow viewing angle from $a^{\prime}_{1}$ between $o^{\prime}$
and $o^{\prime\prime}$.

###### Proof.

Clearly none of the eight endpoints of $A_{1},B_{1},A_{2},B_{2}$ in any gadget
can see any endpoint outside the gadget. After extending $A_{1}$ to
$A^{\prime}_{1}$ by moving its lower endpoint from $a_{1}$ to
$a^{\prime}_{1}$, the endpoint $a^{\prime}_{1}$ may see outside the gadget
only through the gap between $o^{\prime}$ and $o^{\prime\prime}$. Refer to
Figure 4.

We next show that $a^{\prime}_{1}$ still cannot see any integer endpoints from
other gadgets. Note that $|a_{1}a^{\prime}_{1}|=\delta$,
$|o^{\prime\prime}a^{\prime}_{1}|>8$, and $\angle
o^{\prime\prime}a^{\prime}_{1}a_{1}>\pi/2$. Thus

$\angle a_{1}o^{\prime\prime}a^{\prime}_{1}<\tan\angle
a_{1}o^{\prime\prime}a^{\prime}_{1}<\frac{|a_{1}a^{\prime}_{1}|}{|o^{\prime\prime}a^{\prime}_{1}|}<\delta/8.$

Consider the ray that starts from $o^{\prime\prime}$ and goes through
$o^{\prime}$. Rotate this ray clockwise about $o^{\prime\prime}$ for a
positive angle till it goes through another integer point $p$ in
$V(\mathcal{S}^{\prime})$. The area of the triangle
$o^{\prime}o^{\prime\prime}p$ is at least $1/2$ since all three endpoints have
integer coordinates. Recall that the endpoints of all segments in
$\mathcal{S}$ are in the range $[1,22n^{2}]\times[1,11n]$, and is scaled by a
factor of $40$ by the transformation from $\mathcal{S}$ to
$\mathcal{S}^{\prime}$. Thus we have
$|po^{\prime\prime}|<40\cdot(22n^{2}+11n)<40\cdot 32n^{2}$ for $n\geq 2$. Also
note that $|o^{\prime}o^{\prime\prime}|<5$. Thus

$\angle o^{\prime}o^{\prime\prime}p>\sin\angle
o^{\prime}o^{\prime\prime}p=\frac{2\cdot\mathrm{area}(o^{\prime}o^{\prime\prime}p)}{|o^{\prime}o^{\prime\prime}|\cdot|po^{\prime\prime}|}>\frac{1}{5\cdot
40\cdot 32n^{2}}=\frac{1}{8\cdot 800n^{2}}=\delta/8.$ (1)

Therefore we have $\angle a_{1}o^{\prime\prime}a^{\prime}_{1}<\angle
o^{\prime}o^{\prime\prime}p$. Since the three points $o^{\prime}$,
$o^{\prime\prime}$, and $a_{1}$ are collinear, this inequality implies that
the line through $a^{\prime}_{1}$ and $o^{\prime\prime}$ splits the angle
$\angle o^{\prime}o^{\prime\prime}p$. Thus the cone with the angle $\angle
o^{\prime}a^{\prime}_{1}o^{\prime\prime}$ does not contain in its interior any
integer endpoints in $V(\mathcal{S}^{\prime})$. Thus $a^{\prime}_{1}$ cannot
see any integer endpoints from other gadgets.

Moreover, no two endpoints $a^{\prime}_{1}$ from two different gadgets can see
each other, because the narrow ranges of slopes of viewing lines through
$a^{\prime}_{1}$, as illustrated by the dotted lines in Figure 1, are disjoint
for intersections of different orientations.

The remaining claims of the lemma are easy to verify. ∎

The following lemma shows that our local transformation preserves linkability:

######  Lemma 2.

$\mathcal{S}$ can be linked into a simple polygon if and only if
$\mathcal{S}^{\prime}$ can be linked into a simple polygon.

###### Proof.

We first prove the direct implication. Suppose that $\mathcal{S}$ can be
linked into a simple polygon. For each visibility edge of this polygon between
two endpoints in $V(\mathcal{S})$, we add a visibility edge between the
corresponding endpoints in $V(\mathcal{S}^{\prime})$. For each endpoint $o$
incident to two segments $oa$ and $ob$ in $\mathcal{S}$, we link the segments
in the corresponding gadget in $\mathcal{S}^{\prime}$ following the
alternating path as illustrated in Figure 3 right. Then $\mathcal{S}^{\prime}$
is also linked into a simple polygon.

We next prove the reverse implication. Suppose that $\mathcal{S}^{\prime}$ can
be linked into a simple polygon. Recall Lemma 1. In any gadget, $B_{1}$ can
only see $A^{\prime}_{1}$ and $a^{\prime}b^{\prime}$, and $B_{2}$ can only see
$A_{2}$ and $a^{\prime}b^{\prime}$. Thus $a^{\prime}b^{\prime}$ must be linked
to both $B_{1}$ and $B_{2}$, which are linked to $A^{\prime}_{1}$ and $A_{2}$,
respectively. This chain can extend further only to $o^{\prime}a$ and
$o^{\prime\prime}b$, respectively, since $A_{2}$ cannot see $o^{\prime}a$.
Thus the seven segments in each gadget must be linked consecutively in the
simple polygon along the sequence
$o^{\prime}a,A^{\prime}_{1},B_{1},a^{\prime}b^{\prime},B_{2},A_{2},o^{\prime\prime}b$.
Then, following the other visibility edges of the simple polygon through
$\mathcal{S}^{\prime}$, which are outside and between the gadgets,
$\mathcal{S}$ can be linked into a simple polygon too. ∎

Recall that the coordinates of endpoints in $V(\mathcal{S})$ are integers of
magnitude $O(n^{2})$. After the transformation, all endpoints in
$V(\mathcal{S}^{\prime})$ except $a^{\prime}_{1}$ have integer coordinates
too. We can scale all coordinates by another factor of $1/\delta=800n^{2}$, so
that all endpoints in $V(\mathcal{S}^{\prime})$ including $a^{\prime}_{1}$
have integer coordinates of magnitude $O(n^{4})$, and the reduction remains
strongly polynomial. Thus Simple Circuit is strongly NP-hard, even if the
input segments are disjoint and have only four distinct orientations.

##  3 Modification for Simple Path

To prove that Simple Path is also NP-hard, we use almost the same
transformation from $\mathcal{S}$ to $\mathcal{S}^{\prime}$ as before, except
two changes:

  1. 1.

Increase the initial scaling factor from $40$ to $80$, and correspondingly
decrease the distance $\delta$ between $a_{1}$ and $a^{\prime}_{1}$ from
$\frac{1}{800n^{2}}$ to $\frac{1}{1600n^{2}}$ when constructing the gadgets.

  2. 2.

Select an arbitrary gadget as illustrated in Figure 3, and replace it by an
extended gadget as illustrated in Figure 5.

The purpose of the first change is to make room for additional segments in the
extended gadget. Updating the scaling factor and the distance $\delta$
together ensures that (1) still holds, and hence Lemma 1 remains valid.
Clearly, the reduction remains strongly polynomial.

Figure 5: The extended gadget for the intersection $o$ between a horizontal
segment $oa$ and a vertical segment $ob$. Left: The coordinates of the points
relative to $o$ are $o=(0,0)$, $o^{\prime}=(-4,0)$, $o^{\prime\prime}=(0,1)$,
$a^{\prime}=(16,1)$, $b^{\prime}=(1,16)$, $A_{1}=8\times[3,7]$,
$B_{1}=9\times[4,5]$, $A_{2}=[3,7]\times 8$, $B_{2}=[4,5]\times 9$,
$a^{\prime\prime}=(32,1)$, $b^{\prime\prime}=(1,32)$, $A_{3}=[10,15]\times 9$,
$B_{3}=[12,13]\times 8$, $A_{4}=9\times[10,15]$, $B_{4}=8\times[12,13]$,
$A_{5}=16\times[10,15]$, $B_{5}=17\times[12,13]$, $A_{6}=[10,15]\times 16$,
$B_{6}=[12,13]\times 17$. Right: An alternating path starting and ending in
the extended gadget.

We have the following lemma analogous to Lemma 2:

######  Lemma 3.

$\mathcal{S}$ can be linked into a simple polygon if and only if
$\mathcal{S}^{\prime}$ can be linked into a simple polygonal chain.

###### Proof.

We first prove the direct implication. Suppose that $\mathcal{S}$ can be
linked into a simple polygon. We link the segments in $\mathcal{S}^{\prime}$
as before, except that in the extended gadget we link the segments as
illustrated in Figure 5 right. Then $\mathcal{S}^{\prime}$ is linked into a
simple polygonal chain starting and ending in the extended gadget.

We next prove the reverse implication. Suppose that $\mathcal{S}^{\prime}$ can
be linked into a simple polygonal chain. In the extended gadget, $B_{1}$ can
only see $A^{\prime}_{1}$ and $a^{\prime}b^{\prime}$, $B_{2}$ can only see
$A_{2}$ and $a^{\prime}b^{\prime}$, and moreover for $i\in\\{3,4,5,6\\}$,
$B_{i}$ can only see $A_{i}$, $a^{\prime}b^{\prime}$, and
$a^{\prime\prime}b^{\prime\prime}$. Since $a^{\prime}b^{\prime}$ and
$a^{\prime\prime}b^{\prime\prime}$ together can be linked to at most four
other segments in the polygonal chain, and since the polygonal chain has only
two vertices of degree one, it follows that among the six segments $B_{i}$,
$1\leq i\leq 6$, each of $a^{\prime}b^{\prime}$ and
$a^{\prime\prime}b^{\prime\prime}$ must be linked to two distinct segments,
and the polygonal chain must start and end at the other two segments. Thus the
$12$ segments
$A^{\prime}_{1},B_{1},A_{2},B_{2},A_{3},B_{3},A_{4},B_{4},A_{5},B_{5},A_{6},B_{6}$,
and the two segments $a^{\prime}b^{\prime},a^{\prime\prime}b^{\prime\prime}$,
are all linked locally to each other in the extended gadget, and they are then
linked to $o^{\prime}a$ and $o^{\prime\prime}b$, respectively, at $o^{\prime}$
and $o^{\prime\prime}$. As before, in each gadget other than this extended
gadget, the seven segments must be linked consecutively along the sequence
$o^{\prime}a,A^{\prime}_{1},B_{1},a^{\prime}b^{\prime},B_{2},A_{2},o^{\prime\prime}b$.
Then, following the other visibility edges of the simple polygonal chain
through $\mathcal{S}^{\prime}$, which are outside and between the gadgets,
$\mathcal{S}$ can be linked into a simple polygon. ∎

Thus Simple Path is also NP-hard. This completes the proof of Theorem 1.

### Postscript

In SoCG 2019, Akitaya et al. [1, 2] presented a proof of the NP-hardness of
Simple Circuit using a gadget very similar to ours. We thank Adrian Dumitrescu
for bringing it to our attention.

Compare [1, Figure 13] and [2, Figure 19] with our Figure 3. Note in
particular that their $p_{4}p_{5}$ and $p_{12}p_{13}$ correspond to our
$A_{2}$ and $A_{1}$, their $p^{\prime}_{2}$ and $p_{2}$ correspond to our
$o^{\prime\prime}$ and $o^{\prime}$, and their properties (i) and (ii)
correspond to our Lemma 1. The main idea behind the internal connections of
their gadget is the same as ours. However, to ensure property (ii), they use a
more complicated method to custom-make each gadget individually [2, Figure
20]. Our construction handles all gadgets uniformly by the small distance
$\delta$, the narrow viewing angle in Figure 4, and the disjoint ranges of
slopes for the dotted lines in Figure 1.

To the best of our knowledge, our result on the NP-hardness of Simple Path is
new.

## References

  * [1] H. A. Akitaya, M. Korman, M. Rudoy, D. L. Souvaine, C. D. Tóth. Circumscribing polygons and polygonizations for disjoint line segments. _Proceedings of the 35th International Symposium on Computational Geometry_ , 9:1–9:17, 2019.
  * [2] H. A. Akitaya, M. Korman, M. Rudoy, D. L. Souvaine, C. D. Tóth. Circumscribing polygons and polygonizations for disjoint line segments. arXiv:1903.07019, 2019.
  * [3] P. Bose, M. E. Houle, and G. T. Toussaint. Every set of disjoint line segments admits a binary tree. _Discrete and Computational Geometry_ , 26:387–410, 2001.
  * [4] D. Rappaport. Computing simple circuits from a set of line segments is NP-complete. _SIAM Journal on Computing_ , 18:1128–1139, 1989.
  * [5] P. Rosenstiehl and R. E. Tarjan. Rectilinear planar layouts and bipolar orientations of planar graphs. _Discrete and Computational Geometry_ , 1:343-353, 1986.
  * [6] C. D. Tóth. Alternating paths along axis-parallel segments. _Graphs and Combinatorics_ , 22:527–543, 2006.