#  CERT: Continual Pre-Training on Sketches for Library-Oriented Code
Generation

Daoguang Zan1,2∗ Bei Chen3 Dejian Yang3 Zeqi Lin3 Minsu Kim4 Work done during
the internship at Microsoft Research Asia.
Bei Guan2,5 Yongji Wang2,5,6 Weizhu Chen7 Jian-Guang Lou3 1Cooperative
Innovation Center, Institute of Software, Chinese Academy of Sciences
2University of Chinese Academy of Sciences
3Microsoft Research Asia
4Korea University
5Integrative Innovation Center, Institute of Software, Chinese Academy of
Sciences
6State Key Laboratory of Computer Science, Institute of Software, Chinese
Academy of Sciences
7Microsoft Azure AI {daoguang@, guanbei<EMAIL_ADDRESS><EMAIL_ADDRESS>
{beichen, deyang, zeqi.lin, wzchen<EMAIL_ADDRESS>
###### Abstract

Code generation is a longstanding challenge, aiming to generate a code snippet
based on a natural language description. Usually, expensive text-code paired
data is essential for training a code generation model. Recently, thanks to
the success of pre-training techniques, large language models are trained on
large-scale unlabelled code corpora and perform well in code generation. In
this paper, we investigate how to leverage an unlabelled code corpus to train
a model for library-oriented code generation. Since it is a common practice
for programmers to reuse third-party libraries, in which case the text-code
paired data are harder to obtain due to the huge number of libraries. We
observe that library-oriented code snippets are more likely to share similar
code sketches. Hence, we present CERT with two steps: a sketcher generates the
sketch, then a generator fills the details in the sketch. Both the sketcher
and the generator are continually pre-trained upon a base model using
unlabelled data. Furthermore, we craft two benchmarks named PandasEval and
NumpyEval to evaluate library-oriented code generation. Experimental results
demonstrate the impressive performance of CERT. For example, it surpasses the
base model by an absolute $15.67\%$ improvement in terms of pass$@1$ on
PandasEval. Our work is available at https://github.com/microsoft/PyCodeGPT.

Figure 1:  An example in Python: multiple code snippets using Pandas may have
the same sketch after anonymizing user-defined terms.

##  1 Introduction

Code generation, aiming to generate a code snippet for a given natural
language description, is a longstanding challenge in the artificial
intelligence community. Usually, to train a code generation model with good
performance, the massive amount of code snippets paired with natural language
descriptions are indispensable Sun et al. (2019); Lu et al. (2021). However,
it is costly and time-consuming to annotate such a dataset. To alleviate this
problem, inspired by GPT-3’s powerful zero-shot natural language generation
ability Brown et al. (2021), recent years have witnessed a trend to train
large language models using large-scale code corpora (e.g., GitHub), and
expect these models to work well directly on code generation tasks, without
fine-tuning on expensive text-code pairs. For example, Codex shows that a
$12$B parameters language model can solve $28.8\%$ of standalone Python
programming problems111It is measured on HumanEval Chen et al. (2021a) with
<EMAIL_ADDRESS>
In this paper, we focus on investigating whether and how language models pre-
trained on code corpora (without fine-tuned on pairwise labelled data) can
generate library-oriented code snippets rather than standalone ones. During
software development, it is a common practice for programmers to reuse third-
party libraries (e.g., Pandas and NumPy) to implement needed functionalities.
It is not easy for programmers to learn how to use these libraries properly.
For example, according to our statistics, more than $40\%$ of StackOverflow
questions with “Python” tag also have at least one library tag. Moreover, for
library-oriented code generation, the necessity of training the model without
pairwise labelled data is raised, as programmers usually need to reuse
different libraries in different scenarios, and it is extremely costly to
label sufficient text-code pairs that cover most of these libraries.

Compared to standalone code snippets, library-oriented code snippets are more
likely to share similar sketches. _Sketch_ is the code structure after
anonymizing the user-defined terms in the code, such as variable names, method
names, constants, etc., which has also been identified as an API usage pattern
in previous research litterateurs on software data mining Zhong et al. (2009);
Wang et al. (2013); Niu et al. (2017). An example is shown in Figure 1. After
anonymizing variables and constants, multiple code snippets using the Pandas
APIs may have the same (or similar) sketch. Based on this observation, a
natural idea to improve library-oriented code generation is to decompose this
task into two subtasks: generating the sketch and then filling in the details.
Many methods based on this idea have been proposed in different code
generation tasks (e.g., Coarse-to-Fine Dong and Lapata (2018) and PlotCoder
Chen et al. (2021b)) and have shown that this idea can effectively improve the
quality of generated code snippets. However, these methods are proposed for
the fine-tuning process, in which high-quality text-code pairs are required to
derive supervision signals for the two-step generation. Therefore, in our
scenario that no pairwise labelled data is provided, a research question
arises: how to leverage the insight of sketching to enhance the language model
pre-training on unlabelled code corpora, thus improving the quality of
generated library-oriented code snippets?

To meet the challenge, we propose CERT (for sketCher and gEneRaTor), a
continual pre-training approach on sketches for library-oriented code
generation. In CERT, a sketcher firstly focuses on predicting a sketch, which
omits user-defined details; then, a generator uses the sketch as a prompt to
generate the complete code. Both the sketcher and the generator are
continually pre-trained based on a base language model for code, using
unlabelled code corpora rather than pairwise labelled data. In addition, we
craft two evaluation benchmarks for Python libraries, called PandasEval and
NumpyEval, each including $101$ programming problems using Pandas and NumPy,
respectively. We perform extensive experiments on CERT. Results indicate that
CERT has superior performance on library-oriented code generation. We further
draw several insights via thorough analysis.

Figure 2: Two examples of programming problems from the PandasEval and
NumpyEval benchmarks. Context is shown with a white background and the target
code with a gray background.

##  2 Task Formulation

Before diving into the details of our proposed approach, we start with a
formal description of the task. Code generation is to solve a programming
problem: generate _target code_ based on _context_. Context contains natural
language problem description in the form of code comments, and a code snippet
that includes statements such as import, function header and variable
definition; target code is a code snippet that solves the programming problem
described in the context. Formally, let
$\mathbf{x}=(x_{1},x_{2},{\cdots},x_{N})$ denote the context, where each
$x_{n}$ can be either a code token or a natural language token. Given
$\mathbf{x}$, the code generation model can be formulated as
$\mathbf{y}=\mathcal{M}(\mathbf{x})$, where
$\mathbf{y}=(y_{1},y_{2},{\cdots},y_{M})$ denotes the target code and each
$y_{m}$ is a code token.

For standalone code generation, the programming problem is expected to be
solved by a code snippet without using third-party libraries; conversely, for
library-oriented code generation, the target code $\mathbf{y}$ contains
library API calls. Two examples of library-oriented programming problems can
be found in Figure 2. Note that carefully labelled context and target code
pairs are indispensable for model fine-tuning, while our proposed approach
only requires continual pre-training on unlabelled code corpora.

##  3 Methodology

In this section, we introduce our base models, followed by the details of our
proposed approach CERT.

###  3.1 Base Models

Codex Chen et al. (2021a) is a milestone pre-trained model that can generate
decent code, but it is not publicly available. Several attempts have been made
to reproduce Codex’s powerful code generation capability, e.g.,
CodeClippy222https://github.com/CodedotAl/gpt-code-clippy and
CodeParrot333https://huggingface.co/transformersbook/codeparrot, but their
performance in Python are not satisfactory. To this end, we present PyCodeGPT
444More details about PyCodeGPT are in Appendix., a pre-trained language
model, which has the ability to generate pretty good standalone Python code,
for example, achieving $8.33\%$ pass$@1$ on HumanEval Chen et al. (2021a).
Specially, PyCodeGPT is a $110$M parameters model based on GPT-Neo Black et
al. (2021). We collected $60.6$M raw python files with a total size of
$330$GB. After a series of data pre-processing strategies, such as de-
duplicating python files, cleaning and formatting the contents, etc., the
final pre-training corpus contains about $13.0$M high-quality python files
with the size of $96$GB. PyCodeGPT is pre-trained for $200$K steps and $100$B
tokens on a cluster of $16$ NVIDIA V$100$ GPUs with $32$GB memory. The pre-
training time is about $2$ days. We summarize the three key points that make
PyCodeGPT powerful: 1) a large amount of carefully cleaned data for pre-
training; 2) a newly trained tokenizer, which is specialized in python; and 3)
a resampling strategy that prioritizes high-quality data. Besides PyCodeGPT,
we also regard CodeGen (Mono $350$M) Nijkamp et al. (2022) as one of our base
models, which is by far the best performing publicly available model on
HumanEval555CodeGen was released during the review period of this paper..

Figure 3: Overview of CERT: a sketcher and a generator.

###  3.2 CERT

As mentioned in Section 2, code generation is to generate target code
$\mathbf{y}$ based on context $\mathbf{x}$. Since we observe that library-
oriented code snippets are more likely to share similar sketches, we present a
novel approach CERT and decompose the code generation model $\mathcal{M}$ into
two modules: a sketcher $\mathcal{M}_{\rm{S}}$ and a generator
$\mathcal{M}_{\rm{G}}$. Figure 3 shows the overview of CERT with a concrete
example in Pandas. Given $\mathbf{x}$ as the input, the sketcher predicts
$\mathbf{s}$, which is the sketch of the target code $\mathbf{y}$. The
sketcher generates multiple candidate sketches ($200$ in our experiments) and
we choose the one that appears the most. Then, the input of the generator is
the concatenation of $\mathbf{s}$ and $\mathbf{x}$. Formally, the process of
CERT can be written as $\mathbf{s}=\mathcal{M}_{\rm{S}}(\mathbf{x})$ and
$\mathbf{y}=\mathcal{M}_{\rm{G}}([\mathbf{s};\mathbf{x}])$. Note that if the
sketch $\mathbf{s}$ is already a complete code snippet without anonymous
symbols, we directly take it as the final prediction instead of using the
generator; and if the sketch $\mathbf{s}$ is an empty sequence, we directly
feed $\mathbf{x}$ into the generator.

We build the sketcher and generator on the top of the base model (PyCodeGPT or
CodeGen) by continual pre-training. At first, we extract the python files that
use a specific library (e.g., Pandas) from the whole pre-training corpus
($13.0$M files mentioned in Section 3.1), and obtain the sub-corpus denoted by
$\mathcal{D}$. Then, we will detail the continual pre-training process of the
sketcher and generator for this library.

#### Sketcher.

Given the library-oriented sub-corpus $\mathcal{D}$, we perform the sketching
operation on each file $\mathbf{d}\in\mathcal{D}$. An example is shown in the
upper part of Figure 5. The sketching operation is used to anonymize the user-
defined terms in the code file with our pre-defined symbols. The file after
sketching is denoted as $\bar{\mathbf{d}}$. We design three different types of
sketching operations: 1) only anonymizing the user-defined constants (Default
CERT); 2) only anonymizing the user-defined names, including function names,
class names, and variable names (CERT-N); and 3) anonymizing both the user-
defined constants and names (CERT-NC). For example, in Figure 5, the constant
‘user_1’ is anonymized with the pre-defined symbol ‘string’. The details of
pre-defined symbols are shown in Figure 4. Then, we continually pre-train the
base model on the library-oriented corpus after sketching, and we obtain the
sketcher model. The pre-training objective is the same as that of the base
model. We pre-train the model for $100$K steps on a cluster of $8$ NVIDIA
V$100$ GPUs with $32$GB memory.

Figure 4: The pre-defined symbols in sketcher. Figure 5: Training data
preparation for sketcher and generator with an example in Pandas.

#### Generator.

In order to prepare the pre-trained corpus for the generator, we firstly split
the original file $\mathbf{d}$ and the sketching file $\bar{\mathbf{d}}$ into
$K$ blocks666We use pip-tools: autopep8, docformatter and redbaron., and
obtain $\mathbf{d}=(d_{1},d_{2},{\cdots},d_{K})$ and
$\bar{\mathbf{d}}=(\bar{d}_{1},\bar{d}_{2},{\cdots},\bar{d}_{K})$. Each block
is a relatively complete code snippet, such as a function or a class. Note
that before splitting, we remove the natural language code comments from the
sketching file $\bar{\mathbf{d}}$. Then, the two files are cross-merged to
give a merged file
$\hat{\mathbf{d}}=(\bar{d}_{1},d_{1},\bar{d}_{2},d_{2},{\cdots},\bar{d}_{K},d_{K})$.
This is to mimic the process of having a sketch as a prompt for each block. An
example is shown in the lower part of Figure 5. Then, the base model is
continually pre-trained on all the merged files $\hat{\mathbf{d}}$ and we
obtain the generator model. As with the sketcher model, we continually pre-
train for $100$K steps.

##  4 Benchmark Construction

Third-party libraries are widely used in reality, while little work has been
done to evaluate library-oriented code generation. To meet this challenge, we
craft PandasEval and NumpyEval, two benchmarks for library-oriented code
generation in Python. Each sample in the benchmarks is a programming problem
consisting of context and target code. The programming problems are solved
using libraries, where Pandas is for PandasEval, and NumPy is for NumpyEval.
The benchmarks are expected to be diverse, authentic, high quality, moderately
difficult, and unseen during pre-training.

In order to craft programming problems using libraries, we refer to
StackOverflow777https://stackoverflow.com, a Q&A website for programmers.
There are plenty of real-world programming problems posted by real users,
which helps us to improve the authenticity of our data. Specifically, we
search for posts using the library tag on StackOverflow, and select those with
high votes. To ensure quality, we only refer to posts with accepted answers.
We go through a post’s question and its accepted answer, then manually
organize them into the form needed for our benchmarks, containing both context
and target code. We also polish all programming problems so that the problem
descriptions are clear and the codes are correct. Note that we keep the
intentions and the descriptions of the programming problems consistent with
the posts to the maximum extent. Finally, two programmers with more than three
years of coding experience in the library are invited to act as code
generation models and check the quality of the data.

As a result, we craft $101$ programming problems for PandasEval and NumpyEval,
respectively. Each programming problem is equipped with test cases for
evaluation. For the programming problems in the form of a function, such as
the bottom one in Figure 2, we create $20$ test cases for each of them. For
the others that contain no functions, such as the top one in the Figure 2, we
provide $1$ test case to check the correctness of predicted variable (e.g.,
out in Figure 2). In total, $64\%$ programming problems in PandasEval and
$30\%$ in NumpyEval are equipped with $20$ test cases. In addition, we craft
programming problems that refer to StackOverflow rather than GitHub, and also
carefully organize and polish the problems, so that we can ensure they are
unseen by the pre-trained models.

##  5 Experiments

In this section, we evaluate CERT on PandasEval and NumpyEval to verify its
effectiveness.

#### Evaluation Metrics.

We use pass$@k$ as the metrics. When $k$ code samples are generated per
problem, pass$@k$ indicates the fraction of correct ones. But computing
pass$@k$ in this way may have high variance. Hence, we follow Chen et al.
(2021a) to generate $n\geq k$ code samples per problem ($n=200$ in our
experiments) and count the number of correct samples $c$. If $n-c<k$, then
pass$@k=1$; otherwise, ${\rm{pass}}@k=1-\prod\nolimits_{i=n-c+1}^{n}(1-k/i)$.
Note that a predicted code is correct if it can pass all the test cases.

#### Implementation Details.

We implement our approach using PyTorch Paszke et al. (2019), HuggingFace’s
transformers library Wolf et al. (2019), and
DeepSpeed888https://github.com/microsoft/DeepSpeed. In the training phase of
PyCodeGPT, we set the batch size to $10$, the window size to $1024$, the
learning rate to $5$e-$4$, the gradient accumulation steps to $4$ and the
weight decay to $0.1$. The settings of sketcher and generator are the same as
PyCodeGPT. We use the mixed-precision of FP$16$ to accelerate the pre-
training. In inference phase, we set the temperature to one of
$[0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0]$. The best performance is reported
across the above hyper-parameters.

Model | pass$@1$ | Model | pass$@1$
---|---|---|---
GPT-Neo $125$M | $0.75$ | GPT-Neo $1.3$B | $4.79$
AlphaCode $89$M | $4.30$ | CodeParrot $110$M | $3.80$
Codex $42$M | $5.06$ | Codex $85$M | $8.22$
Codex $2.5$B | $21.36$ | Codex $12$B | $28.81$
PyCodeGPT $110$M | $8.33$ |  CodeGen-Mono 350M | $12.76$

Table 1: The pass$@1$ ($\%$) results on HumanEval benchmark. We omit CodeT5
($220$M), CodeGPT-Adapted ($124$M), and CodeClippy ($125$M) as their
pass$@1=0$.

###  5.1 Main Results

Before evaluating CERT, we would like to evaluate our base model PyCodeGPT on
HumanEval Chen et al. (2021a) compared to several advanced pre-trained models.
As shown in Table 1, PyCodeGPT ($110$M) achieves competitive $8.33\%$
pass$@1$. It largely exceeds other models with comparable parameters, e.g.,
AlphaCode ($89$M) Li et al. (2022), CodeClippy ($125$M), and CodeParrot
($110$M), and also is better than the larger model GPT-Neo ($1.3$B).

Then, our proposed CERT is evaluated on PandasEval and NumpyEval. We train
CERT on two base models, including PyCodeGPT and CodeGen, named PyCodeGPT-CERT
and CodeGen-CERT, respectively. For each benchmark, we extract corresponding
library-oriented files to train CERT. The file numbers are about $0.61$M for
Pandas and $2.62$M for NumPy. Baselines include our base models PyCodeGPT and
CodeGen; PyCodeGPT-XL and CodeGen-XL, which are continual pre-trained
PyCodeGPT and CodeGen on the extracted library-oriented files; and advanced
pre-trained models for code, like CodeT5 Wang et al. (2021), CodeGPT Lu et al.
(2021), CodeClippy and CodeParrot. Table 2 summarizes the performance. CERT
consistently outperforms all the baselines by a large margin. The absolute
improvements over PyCodeGPT and CodeGen are shown in red, which are
significant, for example, $12.69\%$ pass$@1$ for CodeGen-CERT and $13.43\%$
pass$@1$ for PyCodeGPT-CERT on NumpyEval. The results demonstrate the
effectiveness of CERT with the idea of leveraging sketches for library-
oriented code generation.

Additionally, we would like to investigate the performance of CERT with
respect to the number of API calls involved in the target code. We divided the
programming problems in each benchmark into four parts based on the number of
APIs. As shown in Figure 6, compared to PyCodeGPT, PyCodeGPT-CERT has a steady
improvement on each part. It indicates that CERT can improve the performance
of library-oriented code generation of varying difficulties.

Benchmark | Model | pass$@1$ | pass$@10$ | pass$@100$
---|---|---|---|---
Pandas Eval | CodeT5 ($220$M) | $0.00$ | $0.00$ | $0.00$
CodeGPT-Adapted ($124$M) | $0.62$ | $2.65$ | $4.95$
CodeClippy ($125$M) | $0.14$ | $0.92$ | $1.92$
CodeParrot ($110$M) | $3.21$ | $13.62$ | $33.27$
CodeGen ($350$M) | $14.24$ | $30.71$ | $46.04$
CodeGen-XL | $21.07$ | $37.67$ | $49.07$
CodeGen-CERT |  $26.40$$\blacktriangle 12.16$ |  $46.49$$\blacktriangle 15.78$ |  $58.16$$\blacktriangle 12.12$
PyCodeGPT ($110$M) | $12.75$ | $37.80$ | $59.65$
PyCodeGPT-XL | $19.80$ | $46.80$ | $60.04$
PyCodeGPT-CERT |  $28.42$$\blacktriangle 15.67$ |  $48.04$$\blacktriangle 10.24$ |  $60.96$$\blacktriangle 1.31$
\- PyCodeGPT-CERT-N | $23.66$ | $41.73$ | $55.08$
\- PyCodeGPT-CERT-NC | $19.07$ | $41.50$ | $54.82$
\- PyCodeGPT-CERTg | $20.58$ | $42.61$ | $56.00$
Numpy Eval | CodeT5 ($220$M) | $0.00$ | $0.10$ | $0.74$
CodeGPT-Adapted ($124$M) | $1.59$ | $4.17$ | $8.54$
CodeClippy ($125$M) | $0.08$ | $0.59$ | $1.24$
CodeParrot ($110$M) | $8.42$ | $21.46$ | $45.94$
CodeGen ($350$M) | $19.31$ | $40.89$ | $60.58$
CodeGen-XL | $27.33$ | $44.75$ | $63.39$
CodeGen-CERT |  $32.00$$\blacktriangle 12.69$ |  $49.45$$\blacktriangle 8.56$ |  $67.82$$\blacktriangle 7.24$
PyCodeGPT ($110$M) | $18.04$ | $38.13$ | $63.37$
PyCodeGPT-XL | $20.50$ | $43.40$ | $56.06$
PyCodeGPT-CERT |  $31.47$$\blacktriangle 13.43$ |  $46.42$$\blacktriangle 8.29$ |  $66.41$$\blacktriangle 3.04$
\- PyCodeGPT-CERT-N | $24.91$ | $42.88$ | $54.02$
\- PyCodeGPT-CERT-NC | $19.88$ | $41.64$ | $55.82$
\- PyCodeGPT-CERTg | $16.55$ | $44.07$ | $56.80$

Table 2: The pass$@k$ ($\%$) results on PandasEval and NumpyEval. The absolute
improvements of CERT over the base model are highlighted in red. Also, we
report the performance of different sketching operations (CERT-N and CERT-NC)
and the performance of CERTg trained for general code generation.  Figure 6:
The pass$@1$ result with respect to the number of APIs.

###  5.2 Closer Analysis

We conduct some closer analyses to provide more insights.

#### Different Types of Sketching.

As mentioned in Section 3.2, we propose three types of sketching operations.
By default, CERT only anonymizes user-defined constants. The other two types
include CERT-N, which anonymizes only user-defined names, and CERT-NC, which
anonymizes both user-defined constants and names. As shown in Table 2, CERT
with default setting achieves the best performance. This observation may be
related to the inherent characteristics of Pandas and NumPy. They are commonly
used in data statistics and analysis, often involving manipulation of the data
constants. Thus, it is necessary to anonymize user-defined constants.
Anonymizing both user-defined constants and names would probably make the
sketches too abstract.

#### Quality of Generated Sketches.

Intuitively, it is easier to generate a sketch than a complete code. Thus, we
would like to evaluate the quality of sketches generated by the sketcher of
CERT. We use exact match accuracy as the metric and include PyCodeGPT and
PyCodeGPT-XL for comparison. For PyCodeGPT and PyCodeGPT-XL, we anonymize the
user-defined constants in the predicted code to obtain the sketch. As shown in
Figure 7, our sketcher surpasses baselines by $15.20\%$ and $14.21\%$ on
PandasEval and NumpyEval, respectively. It indicates that the sketcher can
generate high-quality sketches, and such sketches further benefit the
generator. Additionally, the generator does not necessarily require an exactly
correct sketch, as the sketch is just a prompt (A case will be discussed in
Section 5.3).

Figure 7: The exact match accuracy of sketches. The sketcher refers to the one
in PyCodeGPT-CERT.

Model | pass$@1$ | pass$@10$ | pass$@100$
---|---|---|---
PyCodeGPT | $8.33$ | $13.36$ | $19.13$
PyCodeGPT-CERTg | $8.25$ | $14.12$ | $20.41$

Table 3: The pass$@k$ ($\%$) results of PyCodeGPT and PyCodeGPT-CERTg on
HumanEval.

Benchmark | Model | Size | pass$@1$ | pass$@10$ | pass$@100$
---|---|---|---|---|---
Pandas Eval |  PyCodeGPT-CERT |  $110$M | $28.42$ | $48.04$ | $60.96$
CodeGen-CERT |  $350$M | $26.40$ | $46.49$ | $58.16$
GPT-3 |  $175$B | $12.97$ | $20.54$ | $25.43$
Codex |  $12$B | $18.88$ | $43.05$ | $\mathbf{64.37}$
Numpy Eval |  PyCodeGPT-CERT |  $110$M | $31.47$ | $46.42$ | $66.41$
CodeGen-CERT |  $350$M | $32.00$ | $49.45$ | $67.82$
GPT-3 |  $175$B | $16.25$ | $22.15$ | $27.38$
Codex |  $12$B | $\mathbf{34.42}$ | $\mathbf{55.75}$ | $\mathbf{71.74}$

Table 4: GPT-3 and Codex on PandasEval and NumpyEval. Figure 8: Three library-
oriented code generation cases.

####  CERT for General Code Generation.

Technically speaking, CERT can also be used for general code generation tasks,
not just the library-oriented ones. Concretely, following the procedure in
Figure 5, we can continually pre-train PyCodeGPT using the whole $13.0$M
python corpus instead of the extracted library-oriented files, and obtain the
model we called CERTg. We evaluate CERTg for general code generation on
HumanEval compared to the base model PyCodeGPT. As shown in Table 3, they have
similar pass$@k$ results. This observation verifies our assumption that
library-oriented code snippets are more likely to share similar sketches, so
it is beneficial to use sketches as prompts in this situation. But in the
general case, it is not useful. Meanwhile the results of CERTg on PandasEval
and NumpyEval are in Table 2. CERTg is inferior to CERT, suggesting that
extracting library-oriented files is essential for CERT to learn the knowledge
of library-oriented sketches.

#### Evaluation of GPT-3 and Codex.

We evaluate GPT-3 and Codex to see how these extremely large models perform on
PandasEval and NumpyEval. As shown in Table 4, CERT is competitive with only
$110$M parameters. Such observation proves CERT’s powerful code generation
capability in library-oriented programming problems.

###  5.3 Case Study

For a more comprehensive comparison, we show three cases in Figure 8. We show
in turn the context, the golden target code, the predicted code of PyCodeGPT
and PyCodeGPT-XL, the sketch generated by PyCodeGPT-CERT and the predicted
code of PyCodeGPT-CERT. Case $1$ is from PandasEval, both PyCodeGPT-CERT’s
sketcher and generator reach the correct results, while the baselines do not.
It reveals that sketcher and generator can work well together. Case $2$ is
from NumpyEval, the sketcher predicts the correct sketch, which has no
anonymous symbols, then this sketch is the final predicted code. It indicates
that the sketcher has the ability to predict code without user-defined
constants. At last, in Case $3$, the sketcher makes a wrong prediction
pd.Series([[number*$2$]*$3$]), while the correct sketch is
pd.Series([[number*$2$], number, [[number*$2$], number]*$2$]). But PyCodeGPT-
CERT’s generator rectifies it and finally generates the correct code. Since
the sketch acts only as a prompt, it is not necessarily to be perfectly
correct, which endows the generator with solid robustness.

##  6 Related Work

The most related work is the line of large pre-trained models for code. As for
the encoder-style pre-trained models, they cannot be employed directly to
generate code, such as CuBERT Kanade et al. (2020), CodeBERT Feng et al.
(2020), and GraphCodeBERT Guo et al. (2020). As for the decoder-style or
encoder-decoder-style ones, they are trained on large unlabelled code corpora
and can work directly on code generation task, such as CodeT5 Wang et al.
(2021), CodeGPT Lu et al. (2021), PLBART Ahmad et al. (2021), PolyCoder Xu et
al. (2022), CodeGen Nijkamp et al. (2022), AlphaCode Li et al. (2022), and
Codex Chen et al. (2021a). All of them focus on generating standalone code,
while we investigate library-oriented code generation. Also, similar to our
idea, there are several works leveraging code sketches, for example, Coarse-
to-Fine Dong and Lapata (2018), Bayou Murali et al. (2018), SketchAdapt Nye et
al. (2019), and PlotCoder Chen et al. (2021b). However, they require labelled
text-code paired data for fine-tuning, while our models continually pre-train
on unlabelled code corpora. For code generation benchmarks, there are few
works, including APPS Hendrycks et al. (2021), HumanEval Chen et al. (2021a),
and PlotCoder’s dataset Chen et al. (2021b). The former two ones focus on
evaluating the capability of generating standalone code, and the last one is
primarily devoted to generating plotting APIs and visualization code.
PandasEval and NumpyEval are dedicated to evaluating the performance of
library-oriented code generation.

##  7 Conclusion

In this paper, we propose a novel approach CERT for library-oriented code
generation. It leverages the code sketches and consists of a sketcher and a
generator. The sketcher and generator are continually pre-trained upon a base
model using unlabelled code corpora. Also, we carefully craft two benchmarks
to evaluate library-oriented code generation, namely PandasEval and NumpyEval.
Experimental results and thorough analysis show the effectiveness of CERT. In
future work, we are interested in code generation for private libraries with
fewer data.

## Acknowledgements

We thank all reviewers and our colleagues, Qian Liu, Yanlin Wang and Shi Han,
for their constructive comments.

## References

  * Ahmad et al. [2021] Wasi Ahmad, Saikat Chakraborty, Baishakhi Ray, and Kai-Wei Chang.  Unified pre-training for program understanding and generation.  In North American Chapter of the Association for Computational Linguistics, pages 2655–2668, 2021.
  * Black et al. [2021] Sid Black, Gao Leo, Phil Wang, Connor Leahy, and Stella Biderman.  GPT-Neo: Large Scale Autoregressive Language Modeling with Mesh-Tensorflow.  In Zenodo, March 2021.
  * Brown et al. [2021] Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  In Neural Information Processing Systems, 2021.
  * Chen et al. [2021a] 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.  Evaluating large language models trained on code.  arXiv preprint arXiv:2107.03374, 2021.
  * Chen et al. [2021b] Xinyun Chen, Linyuan Gong, Alvin Cheung, and Dawn Song.  Plotcoder: Hierarchical decoding for synthesizing visualization code in programmatic context.  In Association for Computational Linguistics, pages 2169–2181, 2021\.
  * Dong and Lapata [2018] Li Dong and Mirella Lapata.  Coarse-to-fine decoding for neural semantic parsing.  In Association for Computational Linguistics, pages 731–742, 2018\.
  * Feng et al. [2020] Zhangyin Feng, Daya Guo, Duyu Tang, Nan Duan, Xiaocheng Feng, Ming Gong, Linjun Shou, Bing Qin, Ting Liu, Daxin Jiang, et al.  CodeBERT: A pre-trained model for programming and natural languages.  In Findings of the Conference on Empirical Methods in Natural Language Processing, pages 1536–1547, 2020.
  * Gao et al. [2020] Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, et al.  The pile: An 800gb dataset of diverse text for language modeling.  arXiv preprint arXiv:2101.00027, 2020.
  * Guo et al. [2020] Daya Guo, Shuo Ren, Shuai Lu, Zhangyin Feng, Duyu Tang, et al.  GraphCodeBERT: Pre-training code representations with data flow.  In International Conference on Learning Representations, 2020.
  * Hendrycks et al. [2021] Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, et al.  Measuring coding challenge competence with apps.  In Neural Information Processing Systems Datasets and Benchmarks Track, 2021.
  * Kanade et al. [2020] Aditya Kanade, Petros Maniatis, Gogul Balakrishnan, and Kensen Shi.  Learning and evaluating contextual embedding of source code.  In International Conference on Machine Learning, pages 5110–5121, 2020.
  * 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.  Competition-level code generation with alphacode.  arXiv preprint arXiv:2203.07814, 2022.
  * Lu et al. [2021] Shuai Lu, Daya Guo, Shuo Ren, Junjie Huang, Alexey Svyatkovskiy, Ambrosio Blanco, Colin Clement, et al.  CodeXGLUE: A machine learning benchmark dataset for code understanding and generation.  arXiv preprint arXiv:2102.04664, 2021.
  * Murali et al. [2018] Vijayaraghavan Murali, Letao Qi, et al.  Neural sketch learning for conditional program generation.  In International Conference on Learning Representations, 2018.
  * Nijkamp et al. [2022] Erik Nijkamp, Bo Pang, Hiroaki Hayashi, Lifu Tu, Huan Wang, Yingbo Zhou, et al.  A conversational paradigm for program synthesis.  arXiv preprint arXiv:2203.13474, 2022.
  * Niu et al. [2017] Haoran Niu, Iman Keivanloo, and Ying Zou.  API usage pattern recommendation for software development.  Journal of Systems and Software, 129:127–139, 2017.
  * Nye et al. [2019] Maxwell Nye, Luke Hewitt, Joshua Tenenbaum, and Armando Solar-Lezama.  Learning to infer program sketches.  In International Conference on Machine Learning, pages 4861–4870, 2019.
  * Paszke et al. [2019] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, et al.  PyTorch: An imperative style, high-performance deep learning library.  In Neural Information Processing Systems. 2019.
  * Radford et al. [2019] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al.  Language models are unsupervised multitask learners.  OpenAI blog, 1(8):9, 2019.
  * Sennrich et al. [2016] Rico Sennrich, Barry Haddow, and Alexandra Birch.  Neural machine translation of rare words with subword units.  In Association for Computational Linguistics, pages 1715–1725, 2016\.
  * Sun et al. [2019] Zeyu Sun, Qihao Zhu, Lili Mou, Yingfei Xiong, Ge Li, and Lu Zhang.  A grammar-based structural cnn decoder for code generation.  In Association for the Advancement of Artificial Intelligence, number 01, pages 7055–7062, 2019.
  * Wang and Komatsuzaki [2021] Ben Wang and Aran Komatsuzaki.  GPT-J-6B: A 6 Billion Parameter Autoregressive Language Model.  https://github.com/kingoflolz/mesh-transformer-jax, May 2021.
  * Wang et al. [2013] Jue Wang, Yingnong Dang, Hongyu Zhang, Kai Chen, Tao Xie, and Dongmei Zhang.  Mining succinct and high-coverage API usage patterns from source code.  In Mining Software Repositories, pages 319–328, 2013.
  * Wang et al. [2021] Yue Wang, Weishi Wang, Shafiq Joty, and Steven CH Hoi.  CodeT5: Identifier-aware unified pre-trained encoder-decoder models for code understanding and generation.  In Empirical Methods in Natural Language Processing, pages 8696–8708, 2021.
  * Wolf et al. [2019] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al.  Huggingface’s transformers: State-of-the-art natural language processing.  arXiv preprint arXiv:1910.03771, 2019.
  * Xu et al. [2022] Frank F Xu, Uri Alon, Graham Neubig, and Vincent Josua Hellendoorn.  A systematic evaluation of large language models of code.  In Deep Learning for Code Workshop, 2022.
  * Zhong et al. [2009] Hao Zhong, Tao Xie, Lu Zhang, Jian Pei, and Hong Mei.  MAPO: Mining and recommending API usage patterns.  In European Conference on Object-Oriented Programming, pages 318–343. Springer, 2009.

##  Appendix A PyCodeGPT: A Democratizing Code Generation Model in Python

Large pre-trained language models, e.g., Codex Chen et al. [2021a] and
AlphaCode Li et al. [2022], have recently achieved surprisingly promising
results on modeling source code in several programming languages. However,
most of the state-of-the-art models are not publicly available, hindering the
progress of related research topics and applications. To this end, we propose
a publicly available code pre-trained model for Python, named PyCodeGPT, to
reproduce Codex with medium size.

###  A.1 Data Construction

It is well-known that large language models require extremely large amounts of
data to exhibit its performance well. In this section, we present the process
of data collection and the data pre-processing strategies to ensure data
quality.

#### Data Collection

We first crawl $7.6$M repository pages hosted on GitHub. Then we consider the
language distribution tags in each page to filter the repositories without
Python files. As a result, we obtain $1.2$M Python-related repository URLs.
With the filtered repository URLs, we download all the contents of each
repository from GitHub. Following Codex, we remove files over $1$MB, as
experienced developers usually avoid creating large source code files to
maintain good readability. As a result, we get $60.6$M raw Python files under
$1$MB, with a total size of $330$GB. Among these files, we further filter out
duplicated files, which has been recognized as an important step by
CodeParrot. Finally, the number of unique files is reduced to $13.0$M, with a
total size of $96$GB.

#### Data Pre-processing

The data pre-processing strategies are summarized in three aspects.

  * •

According to the strategies applied to Codex and CodeParrot, we consider each
source code as text and focus on line length limit and alphanumeric rate999It
makes our model only target the English version.. In detail, we filter the
files which do not meet the four conditions: lines of code $\geq 5$, average
line length $\leq 100$, maximum line length $\leq 1000$, and alphanumeric rate
$\geq 0.98$. Note that, the fourth condition is applied after removing
comments with alphanumeric rate $<0.5$, which is one of the following
strategies.

  * •

We also remove the automatically generated or meaningless files, for example,
files with the name __init__.py, setup.py or _pb2.py, because these files can
mislead the model during training. In addition, we remove some useless
contexts from the Python files. Specifically, we remove the contexts of
license description and comments with alphanumeric rate $<$ $0.5$, where
license description appears as a comment in the head of the code.

  * •

To ensure the training quality, we design two methods to perform Python syntax
checking. The first method is to use Python’s built-in module `ast` to check
the correctness of the syntax. This strategy filter out non-Python files
largely, even if the file name ends with .py. The second method applies
pattern matching to leave files containing more than two typical Python
keywords (e.g., `def`, `if`, `return`, and `for`).

Hyper-parameter | Value
---|---
Learning Rate | $5\times 10^{-4}$
Optimizer | ${\rm AdamW}$
Adam $\beta$ |  $0.9$, $0.95$
Adam $\epsilon$ | $10^{-8}$
Weight Decay | $0.1$
Warmup Steps | $100K$
Learning Rate Decay | ${\rm Cosine}$
Batch Size (tokens) | $480K$
Training Steps | $200K~{}{\rm steps},100B~{}{\rm tokens}$
Context Window | $1024$

Table 5: Hyper-parameters in pre-training.

###  A.2 Model Training

We use GPT-Neo Black et al. [2021] as our base model, which is comparable to
GPT-3 Brown et al. [2021] and has already been pre-trained on the Pile dataset
Gao et al. [2020]. In this section, we present the details of model training,
including tokenization, resampling, and hyper-parameters.

#### Tokenization

The tokenizer of GPT-Neo models is based on GPT-2 Radford et al. [2019]
tokenizer, which applies the byte-level version of Byte Pair Encoding (BPE)
Sennrich et al. [2016].The tokenizer is trained on the Pile dataset with a
vocabulary of $50$K. Since the distribution of source code words differ from
that of natural text, the original GPT-Neo tokenizer is not very effective for
encoding Python source code. Thus, we follow CodeParrot to train a new byte-
level BPE tokenizer from scratch on our collected code data. Finally, we set
the vocabulary size to $32$K, which allows us to encode code using
approximately 40% fewer tokens.

#### Resampling

Since different files have different importance for training, we design a data
resampling strategy to make high-quality files appear more often, while
keeping a balance to make each file appear at least once throughout the
training process. In detail, we evaluate the quality of a Python file in two
aspects: repository star count and unit test function rate. The repository
star count is determined by GitHub users and is the main factor in measuring
repository quality. We do not use the star count directly for filtering data
because most files have very few stars. The unit test function rate is the
number of unit test functions divided by the number of functions. We introduce
it to reduce the weight of files used for testing, because test files often
contain a lot of user-defined numeric constants or string constants.

#### Hyper-parameters

PyCodeGPT shares the same configurations with original GPT-Neo 125M model
except for the vocabulary size. It is trained on $16$ V$100$ ($32$GB) GPUs for
about $2$ days. Table 5 lists the hyper-parameters.

Model | Params | pass$@k$
---|---|---
k=$1$ | k=$10$ | k=$100$
Parameter Scale: ${\sim}100$M
TabNine | – |  $2.58$% |  $4.35$% |  $7.59$%
GPT-Neo |  $125$M |  $0.75$% |  $1.88$% |  $2.97$%
CodeParrot |  $110$M |  $3.80$% |  $6.57$% |  $12.78$%
PolyCoder |  $160$M |  $2.13$% |  $3.35$% |  $4.88$%
Codex |  $85$M |  $8.22$% |  $12.81$% |  $\mathbf{22.40}$%
AlphaCode |  $89$M |  $4.3$% |  $12.2$% |  $20.0$%
PyCodeGPT (Ours) |  $110$M |  $\mathbf{8.33}$% |  $\mathbf{13.36}$% |  $19.13$%
Parameter Scale: ${\sim}500$M
PolyCoder |  $400$M |  $2.96$% |  $5.29$% |  $11.59$%
Codex |  $300$M |  $13.17$% |  $20.37$% |  $36.27$%
Codex |  $679$M |  $\mathbf{16.22}$% |  $\mathbf{25.7}$% |  $\mathbf{40.95}$%
AlphaCode |  $302$M |  $11.6$% |  $18.8$% |  $31.8$%
AlphaCode |  $685$M |  $14.2$% |  $24.4$% |  $38.8$%
CodeGen-Mono |  $350$M |  $12.76$% |  $23.11$% |  $35.19$%
Parameter Scale: ${\sim}1$B
GPT-Neo |  $1.3$B |  $4.97$% |  $7.47$% |  $16.30$%
CodeParrot |  $1.5$B |  $3.58$% |  $8.03$% |  $14.96$%
AlphaCode |  $1.1$B |  $\mathbf{17.1}$% |  $\mathbf{28.2}$% |  $\mathbf{45.3}$%
Parameter Scale: ${\sim}2$B
GPT-Neo |  $2.7$B |  $6.41$% |  $11.27$% |  $21.37$%
PolyCoder |  $2.7$B |  $5.59$% |  $9.84$% |  $17.68$%
Codex |  $2.5$B |  $21.36$% |  $35.42$% |  $\mathbf{59.50}$%
CodeGen-Mono |  $2.7$B |  $\mathbf{23.70}$% |  $\mathbf{36.64}$% |  $57.01$%
Parameter Scale: ${\sim}6$B
GPT-J |  $6$B |  $11.62$% |  $15.74$% |  $27.74$%
CodeGen-Mono |  $6.1$B |  $\mathbf{26.13}$% |  $\mathbf{42.29}$% |  $\mathbf{65.82}$%
Parameter Scale: >$10$B
Codex |  $12$B |  $28.81$% |  $46.81$% |  $72.31$%
CodeGen-Mono |  $16.1$B |  $\mathbf{29.28}$% |  $\mathbf{49.86}$% |  $\mathbf{75.00}$%

Table 6: Experimental results of models under different parameter scales on
the HumanEval Dataset. For AlphaCode, we report the pre-trained decoder-only
results from their paper. For TabNine, we do know the parameter scale, so we
put it to the first scale group.

###  A.3 Experiments

We conduct experiments on HumanEval and CodeXGLUE to show the effectiveness of
PyCodeGPT.

#### Results on HumanEval

HumanEval Chen et al. [2021a] contains $164$ hand-written code generation
problems. As mentioned in Section 5, the evaluation metric is pass$@k$. We use
the same parameters as those used by Codex, except for the stop sequences. The
stop sequences include `\nclass`, `\ndef`, `\n#`, `\n@`, `\nprint`, and
`\nif`. We generate $200$ programs and apply nucleus sampling using $p=0.95$.
As in previous work, we try various temperatures (from $0.1$ to $1.0$ with the
interval of $0.1$) and report the best result for each $k$.

Table 6 shows the experimental results. Even though the original GPT-Neo
models ($125$M, $1.3$B and $2.7$B) and GPT-J $6$B Wang and Komatsuzaki [2021]
are trained on the dataset containing GitHub files, they do not achieve
satisfactory performance on HumanEval compared to Codex. For the open-source
CodeParrot models ($110$M and $1.5$B), as we mentioned before, they outperform
the corresponding ones of GPT-Neo but still not enough to compare with Codex.
AlphaCode Li et al. [2022] also evaluates their decoder-only model on
HumanEval, and the performance is slightly worse than Codex. PolyCoder Xu et
al. [2022] is pre-trained on several programming languages, and it shows even
worse performance than CodeParrot. However, our pre-trained $110$M model can
obtain comparable performance to Codex $85$M and outperform CodeParrot $110$M
by $4.53$% on pass$@1$, $6.79$% on pass$@10$ and $6.35$% on pass$@100$. During
our paper review, CodeGen Nijkamp et al. [2022] also provided code generation
models of various sizes from $350$M to $16.1$B and obtained good performance.
We omit CodeT5, CodeGPT, and CodeClippy, since they all get $0\%$ on pass$@1$,
pass$@10$, and pass$@100$.

Model | Params | Token Level | Line Level
---|---|---|---
Accuracy | EM | ES
LSTM | – |  $58.00$% |  $17.93$% |  $50.05$%
Transformer | – |  $73.26$% |  $36.65$% |  $67.51$%
GPT-2 |  $117$M |  $74.22$% |  $38.55$% |  $68.94$%
CodeGPT |  $124$M |  $74.93$% |  $39.11$% |  $69.69$%
CodeGPT-Adapted |  $124$M |  $75.11$% |  $39.65$% |  $69.84$%
CodeParrot |  $110$M |  $77.22$% |  $42.10$% |  $71.07$%
PyCodeGPT (Ours) |  $110$M |  ${\mathbf{80.24}}$% |  $\mathbf{44.77}$% |  $\mathbf{73.09}$%

Table 7: Experimental results on CodeXGLUE Code Completion task dataset PY150.
Results of LSTM, Transformer, GPT-2, CodeGPT and CodeGPT-Adapted are from Lu
et al. [2021]. Exact match and edit similarity are abbreviated as EM and ES.

#### Results on CodeXGLUE

CodeXGLUE Lu et al. [2021] is a benchmark for programming language
understanding and generation tasks. In total, CodeXGLUE provides datasets for
14 tasks, in which the dataset PY150 is for code completion task. Table 7
shows the experimental results. Note that we fine-tuned PyCodeGPT and
CodeParrot on PY150 training dataset. The results show that CodeGPT is worse
than the fine-tuned CodeParrot. However PyCodeGPT wins the CodeParrot with
$3.02$% higher score on token level completion accuracy. On line level
completion, PyCodeGPT also achieves $2.67$% and $2.02$% higher accuracy on
exact match and edit similarity, respectively.


# PDCCH Scheduling via Maximum Independent Set

Lorenzo Maggi, Alvaro Valcarce Rial, _Senior IEEE member_ , Aloïs Herzog,
Suresh Kalyanasundaram, Rakshak Agrawal Lorenzo Maggi and Alvaro Valcarce Rial
are with Nokia Networks France, Bell Labs, 91377 Massy Palaiseau (France).
Aloïs Herzog is with Nokia Networks France, Mobile Networks, 91377 Massy
Palaiseau (France). Suresh Kalyanasundaram and Rakshak Agrawal are with Nokia
India Private Limited, Mobile Networks, 560045 Bangalore (India). Emails:
{lorenzo.maggi<EMAIL_ADDRESS>{alois.herzog,
suresh.kalyanasundaram<EMAIL_ADDRESS>
###### Abstract

In 5G, the Physical Downlink Control CHannel (PDCCH) carries crucial
information enabling the User Equipment (UE) to connect in UL and DL. UEs are
unaware of the frequency location at which PDCCH is encoded, hence they need
to perform blind decoding over a limited set of possible candidates. We
address the problem faced by the gNodeB of selecting PDCCH candidates for each
UE to optimize data transmission. We formulate it as a Maximum Weighted
Independent Set (MWIS) problem, that is known to be an NP-hard problem and
cannot even be approximated. A solution method called Weight-to-Degree Ratio
(WDR) Greedy emerges as a strong contender for practical implementations due
to its favorable performance-to-complexity trade-off and theoretical
performance guarantees.

###### Index Terms:

PDCCH, DCI, Independent Set, NP-hard, performance guarantees, Greedy

##  I Introduction

In 5G wireless communication systems, the Physical Downlink Control CHannel
(PDCCH) comprises the set of time/frequency resources carrying Downlink
Control Information (DCI). Each DCI, specific to either downlink (DL) or
uplink (UL), enables UEs to establish communication in the upcoming slot, and
conveys information on scheduling assignments, slot format indication, power
control, precoding, modulation and coding schemes. A UE is unaware of the
specific sub-carriers where its DCI has been encoded, thus it performs blind
decoding. To ease this process, the UE searches within a restricted set of
candidate frequency locations, known as Search Space (SS). However, this
complicates the gNodeB’s task of selecting PDCCH candidates and maximizing the
resource allocation fairness across UEs.

To define more precisely a SS we need to introduce some terminology compliant
with the 3GPP specifications [1].

_Preliminaries._ A RE denotes one subcarrier and 1 Orthogonal Frequency
Division Multiplexing (OFDM) symbol time, carrying 1 OFDM symbol. A Resource
Element Group (REG) is a set of 12 REs contiguous in frequency, being
equivalent to a Physical Resource Block (PRB) over one OFDM symbol time. REGs
can be grouped over one or two consecutive symbol times into REG _bundles_.
The latter notion finally allows us to introduce the smallest logical building
block of a SS, called Control Channel Element (CCE) and consisting of 6 REGs.
If REGs are bundled in two slots, then a CCE is a set of 3 REG bundles, each
of which is interleaved in frequency. The set of PRBs and OFDM symbols on
which CCEs are allocated is called COntrol REsource SET (CORESET), see Figure
1. The code rate used for DCI transmission depends on the channel conditions
experienced by the UE: the worse the channel conditions, the lower code rate.
Thus, a variable number of CCEs, called Aggregation Level (AL), is used to
encode a single DCI. Possible values of AL are $\\{1,2,4,8,16\\}$.

Figure 1: Example of interleaved CCE-to-REG mapping in a CORESET, where
CORESET spans 2 OFDM symbol times.

_Search Space (SS)._ A DCI is encoded at consecutive CCE indexes within a
CORESET. The SS defines the _starting_ CCE index of all PDCCH _candidate_
locations carrying the DCI (UL or DL) for a specific UE for a given AL and at
a given slot. Such indexes are generated via a hashing function that both the
gNodeB and the UEs know and can compute. The gNodeB selects only one candidate
to encode the DCI addressed to a UE in UL or DL, that the UE is unaware of.
Hence, the UE performs _blind decoding_ , i.e., it scans all available
candidate locations for all possible ALs (since the UE also ignores its AL)
until the DCI is successfully decoded. To alleviate the complexity of blind
decoding, the number $N_{AL}$ of candidates is limited and can be defined as a
function of the AL. We remark that several CORESETs and SSs can be configured
in each slot for each UE.

_Related works._ PDCCH 3GPP specifications are detailed in [1] and
disseminated by [2]. The design of an efficient hashing function is
investigated in [3]. The control channel scheduling has recently garnered
attention for narrow-band Internet of Things (IoT) and RedCap devices. There,
the device energy consumption is a major bottleneck that can be mitigated by
minimizing blind decoding [4] or by designing the SS [5] and the control
period [6]. The problem of PDCCH candidate selection has already been
formulated as a set packing problem, known to be equivalent to the independent
set problem, in [7] and a heuristic was proposed.

In this paper we solve the PDCCH candidate selection via efficient
combinatorial optimization techniques with performance guarantees. We
demonstrate the superiority of our approach, based on combinatorial
optimization theory, in terms of computational complexity and performance.

##  II Problem formulation

We address the problem of selecting the PDCCH candidate on which the gNodeB
transmits a DCI (for UL or DL) for each UE. Here we focus on a specific slot
and we denote by $\mathcal{U}$ the set of UEs eligible for data transmission.
We denote by $\mathcal{C}_{u}^{\mathrm{UL}},\mathcal{C}_{u}^{\mathrm{DL}}$ be
the set of PDCCH candidates for UE $u\in\mathcal{U}$ across all active SSs and
CORESETs, for UL and DL, respectively. For UE $u\in\mathcal{U}$, the gNodeB
aims to select at most one candidate among $\mathcal{C}_{u}^{\mathrm{UL}}$ and
at most one among $\mathcal{C}_{u}^{\mathrm{DL}}$. Importantly, each CCE must
only carry the DCI of a single UE. Equivalently, any two selected PDCCH
candidates cannot overlap on any CCE.

Our goal is to schedule as many DCIs as possible while avoiding overlaps.
Moreover, we want to prioritize the allocation of UEs with higher scheduling
priority. We formalize these goals by assigning priority _weights_
$w_{u}^{\mathrm{UL}},w_{u}^{\mathrm{DL}}$ to UE $u\in\mathcal{U}$ in UL and
DL, respectively, and by maximizing the sum of the weights of UEs with one
selected candidate.

To define the optimization problem we introduce the auxiliary binary variable
$x_{c}$ indicating whether ($x_{c}=1$) or not ($x_{c}=0$) a DCI is transmitted
on candidate $c\in\mathcal{C}$. Note that $\mathcal{C}$ is the set of all
possible candidates, i.e.,
$\mathcal{C}=\cup_{u\in\mathcal{U}}(\mathcal{C}_{u}^{\mathrm{UL}}\cup\mathcal{C}_{u}^{\mathrm{DL}})$.
We then formulate our problem as:

$\displaystyle\max_{x\in\\{0,1\\}}$
$\displaystyle\,\sum_{u\in\mathcal{U}}w_{u}^{\mathrm{UL}}\sum_{c\in\mathcal{C}_{u}^{\mathrm{UL}}}x_{c}+\sum_{u\in\mathcal{U}}w_{u}^{\mathrm{DL}}\sum_{c\in\mathcal{C}_{u}^{\mathrm{DL}}}x_{c}$
(1) $\displaystyle\mathrm{s.t.}$ $\displaystyle\ x_{c}+x_{c^{\prime}}\leq
1\qquad\forall\,\mathrm{overlapping}\ (c,c^{\prime})$ (2) $\displaystyle\
\sum_{c\in\mathcal{C}^{i}_{u}}x_{c}\leq 1,\quad\forall\,u\in\mathcal{U},\
i\in\\{\mathrm{UL},\mathrm{DL}\\}.$ (3)

Constraint (2) states that if two candidates overlap, then at most one of them
can be selected, i.e., no pair of selected candidates can overlap. According
to (3), for each UE at most one candidates can be used in UL and DL,
respectively.

The optimization problem (1-3) is a binary integer program. Specialized
algorithms can be used to solve or approximate it by recognizing that it can
be reformulated as a _Maximum Weighted Independent Set_ (MWIS) problem, as
shown next.

The MWIS formulation of the PDCCH scheduling problem hinges on the definition
of an auxiliary undirected weighted graph $G=(\mathcal{C},E,W)$ that we call
_incompatibility graph_. Its vertices $\mathcal{C}$ are the set of PDCCH
candidates. There is an edge $(c,c^{\prime})\in E$ if candidates
$c,c^{\prime}$ cannot be selected concurrently, i.e., if they overlap or are
associated to the same UE in UL or DL, as shown in Figure 2. Formally, the set
of edges is

$\displaystyle E=\Big{\\{}(c,c^{\prime}):\,$
$\displaystyle\big{[}\exists\,(u,i):c\in\mathcal{C}^{i}_{u}\land
c^{\prime}\in\mathcal{C}^{i}_{u}\big{]}\lor\big{[}(c,c^{\prime})\
\mathrm{overlap}\big{]}\Big{\\}}$

where $i\in\\{\mathrm{UL},\mathrm{DL}\\}$. Each node $c$ has weight $w_{c}\in
W$ which, with some abuse of notation, is defined as $w_{c}=w_{u}^{i}$ if
candidate $c$ belongs to UE $u$ and mode $i\in\\{\mathrm{UL},\mathrm{DL}\\}$.

Figure 2: Incompatibility graph $G$ and an independent set for a given Search
Spaces (SS), considering for simplicity exclusively DL or UL. There is no edge
between any pair of vertices in the independent set. Equivalently, only non-
overlapping candidates are chosen, and at most one per UE.

We now rewrite the PDCCH scheduling problem (1-3) as a MWIS on the
incompatibility graph $G$. Here we aim to find the set of nodes with maximum
weight and such that they form an _independent set_ , i.e., no pair of nodes
shares an edge:

$\displaystyle\max_{x\in\\{0,1\\}}$
$\displaystyle\,\sum_{c\in\mathcal{C}}w_{v}x_{v}$ (4)
$\displaystyle\mathrm{s.t.}$ $\displaystyle\,x_{c}+x_{c^{\prime}}\leq
1,\qquad\forall\,(c,c^{\prime})\in E.$ (5)

##  III Algorithms for PDCCH scheduling

The MWIS problem is known to be NP-hard, i.e., there exists no polynomial time
algorithm that solves it exactly (unless P=NP). Unfortunately, MWIS is also
hard to approximate. In fact, there exists no polynomial time algorithm able
to approximate it within a factor
$\mathcal{O}(\mathrm{\\#nodes^{\epsilon-1}})$ away from the optimal value, for
$\epsilon>0$ [8]. However, several algorithms with performance guarantees have
been proposed in the literature. We select two methods from the MWIS
literature that we deem suitable for PDCCH scheduling where the latency
constraint is tight. Then, we outline a procedure for computing the optimal
solution without exhaustively enumerating all possibilities, although it
remains impractical for our application. Finally, we describe the heuristic
introduced in [7], requiring to compute the optimal solution on a small subset
of users.

###  III-A Greedy algorithm

The most computationally efficient algorithm studied in the literature for
MWIS is a greedy one that iteratively selects the node (i.e., candidate) with
the highest metric. Once a node is selected, all of its neighbors are
subsequently removed from the graph, since selected nodes cannot share an
edge.

1Set $\mathcal{C}^{\mathrm{sel}}=\emptyset$ as the set of selected PDCCH
candidates;

2 while  _$\mathcal{C}\neq\emptyset$_ do

3 Select candidate $c^{*}\in\mathcal{C}$ with highest metric $m_{c^{*}}$;

4 Add $c^{*}$ to $\mathcal{C}^{\mathrm{sel}}$;

5 Remove $c^{*}$ from incompatibility graph $G$ (and from $\mathcal{C}$) along
with all of its neighbors;

6

Algorithm 1 Greedy algorithm

Different definitions of metric $m$ lead to different variants of the greedy
algorithm above. A popular one, studied in [9], is one where $m$ is the
Weight-to-Degree Ratio (WDR):

$m_{c}:=\frac{w_{c}}{\mathrm{deg}(c)+1},\quad\forall\,c\in\mathcal{C}$ (6)

where $\mathrm{deg}(c)$ is the degree, i.e., the number of neighbors, of node
$c$. This metric prioritizes the selection of candidates with higher weight
and lower degree, thus blocking fewer other candidates. Note that the WDR
metric is recomputed after each iteration, since the graph is updated upon a
node selection.

_Performance guarantees._ Under the WDR metric $m$ defined as in (6), the
greedy algorithm produces a set of candidates with total weight of at least
$\sum_{c\in\mathcal{C}}\frac{w_{c}}{\mathrm{deg}(c)+1}$, as shown in [9].

###  III-B Feige-Reichmann (FR) algorithm

The second algorithm for MWIS we present is named after its inventors Feige
and Reichman [10]. It builds on the fact that computing the optimal solution
for MWIS is easy for undirected _forests_. (We recall that a forest is a
collection of trees, and a tree is a graph with no cycle.) One can proceed
iteratively from leaf to root nodes. At each iteration the optimum values
$V^{Y}(c),V^{N}(c)$ are available for lower subtrees rooted at $c$, whether
$c$ is included ($V^{Y}(c)$) or not ($V^{N}(c)$) in the subtree optimal
solution. Then, such values are computed for the parent nodes, knowing that
either the parent or the children, but not both, can be included in the
optimal solution. The complexity of the resulting procedure is _linear_ in the
number of candidates.

1 _Require_ : Input graph $\underline{G}$ is an undirected forest;

2 Compute the value $V^{Y}(c)=w_{\ell}$ and $V^{N}(c)=0$ for all leaf nodes
$c$;

Until roots are reached, compute values for nodes $p$ as:  $\displaystyle
V^{Y}(p)=$ $\displaystyle\,w_{p}+\sum_{c\in\mathrm{children}(p)}V^{N}(c)$ (7)
$\displaystyle V^{N}(p)=$
$\displaystyle\,\sum_{c\in\mathrm{children}(p)}\max\\{V^{N}(c),V^{Y}(c)\\}$
(8) return optimal value
$\sum_{r\in\mathrm{roots}}\max\left\\{V^{N}\\!(r),\,V^{Y}\\!(r)\right\\}$

Algorithm 2 Optimal MWIS for forests

Note that the optimal subtree _solution_ can be computed iteratively using the
same approach as for calculating the value.

The Feige-Reichmann (FR) algorithm first extracts a forest as a subgraph of
the incompatibility graph $G$ and then uses Algorithm 2 as a subroutine. The
forest is produced by iterating over all nodes in a certain order and adding a
node only if at most one neighbor was encountered previously. The resulting
subgraph cannot contains cycles: in fact, if a cycle were to exist, its last
added node would have at least two neighbors among the previous nodes, leading
to a contradiction.

_Performance guarantees._ The FR procedure always produces a feasible
solution; yet, its quality depends on the node sorting criterion used in line
2, Algorithm 3. If the candidates are sorted via a uniformly random
permutation, then the _expected_ sum of weights of the produced solution is at
least $2\sum_{c\in\mathcal{C}^{*}}\frac{w_{c}}{\mathrm{deg}(c)+1}$, where
$\mathcal{C}^{*}$ is the optimal solution [10]. Yet, the _variance_ in the
solution quality can be an issue in practical PDCCH applications.

A safer approach would be to sort candidates by first including those produced
by the greedy algorithm. The resulting solution shall be at least as good as
the greedy one: indeed, the forest shall include the greedy solution since it
forms an independent set, i.e., no edges are present among those nodes.

1Initialize $\underline{G}$ as the empty graph;

2 Sort nodes $\mathcal{C}$ according to a certain criterion;

3 for  _candidate $c$ in the sorting order_ do

4 If at most one neighbor $c^{\prime}$ of $c$ was already seen, then add $c$
to $\underline{G}$ along with edge $(c,c^{\prime})$, if any;

5

Solve MWIS optimally on $\underline{G}$ via Algorithm 2

Algorithm 3 Feige-Reichmann (FR) algorithm [10]

###  III-C Exact solution via recursion

To compute the optimal MWIS solution, a naive procedure requiring
$\mathcal{O}(2^{|V|})$ steps would enumerate all subsets of nodes and check if
they form an independent set. A better procedure reported below exploits a
similar recursive property used by the FR algorithm and runs in
$\mathcal{O}(1.38^{|V|})$ steps [11].

1If $G$ is empty then return 0

2 else

3 Choose a node $p$ ;

4 Compute $V^{N}(p)=\text{Optimal-Recursion}(G\setminus\\{p\\})$;

5 Compute $V^{Y}(p)=w_{p}+\text{Optimal-
Recursion}(G\setminus\\{p\\}\setminus\mathrm{neighbors}(p))$;

6 return $\max\left\\{V^{Y}(p),V^{N}(p)\right\\}$

Algorithm 4 Optimal-Recursion($G$)

###  III-D Optimal-then-Greedy (OtG) heuristic [7]

The exponential complexity of the optimal solution is prohibitive for our
applications. For this reason, [7] proposes a heuristic that first sorts UEs
in descending order of metric $w/AL$. Then, the optimal solution is computed
_only_ on the top $M$ UEs. Finally, the remaining candidates are selected via
a greedy procedure using the same metric. The complexity of the overall
procedure is exponential in $M$. We found that only values $M\leq 4$ are
feasible in our latency-constrained scenario.

TABLE I: Performance of PDCCH candidate selection methods | inter-tx $\\#$slots
---|---
Method |  $\\#$UE/slot |  geomean thpt |  runtime |  AL=1 |  AL=2 |  AL=4 |  AL=8
W-Greedy |  11.79 |  0.94 |  0.43 |  1.36 |  2.34 |  4.18 |  6.52
OtG |  13.15 |  0.84 |  13.52 |  1.03 |  1.97 |  5.91 |  12.19
WDR-Greedy |  13.55 |  1.00 |  1.00 |  1.12 |  1.94 |  4.03 |  8.07
FR |  13.74 |  1.01 |  3.32 |  1.10 |  1.89 |  4.08 |  8.27

##  IV Numerical evaluations

We evaluated the performance of different options for PDCCH candidate
selection under the following settings. The number of candidates per AL,
$N_{AL}$, is set to $N_{AL=1}=5$, $N_{AL=2}=4$, $N_{AL=4}=3$, $N_{AL=8}=2$.
The same CORESET composed of 32 CCEs is used for all UEs. The UE-specific SS
are generated according to the hashing function defined by 3GPP in [1].
Weights $w$ are defined as the classic Proportional Fairness (PF) metric,
which is the ratio of the currently achievable rate to the average achieved
throughput in the past. For simplicity we assume that each UE has only one
DCI, in DL. We ran our experiments on 100 independent scenarios. In each
scenario, 30 UEs have a different AL randomly drawn from $\\{1,2,4,8\\}$
according to a uniform distribution. The AL remains unchanged across all 300
slots. Traffic requests are generated via a Poisson distribution, while
spectral efficiency is inversely proportional to the AL. In each slot, the
PDSCH resources are distributed in round robin fashion across the UEs whose
DCI has been assigned to a PDCCH candidate.

_Tested algorithms._ We compared four different algorithms for PDCCH candidate
selection. The first one, called _W-Greedy_ , corresponds to the greedy
Algorithm 1 with a simple _w_ eight node metric $m:=w$. Although easy to
implement as it does not rely on the incompatibility graph, W-Greedy is myopic
since it fails to consider how a candidate selection may subsequently block
other UEs. The second option is Optimal-then-Greedy (_OtG_), proposed in [7]
and described in Section III-D, where $M=4$. Higher values of $M$ proved
computationally prohibitive. The third method, _WDR-Greedy_ , is greedy
Algorithm 1 under WDR metric $m$ defined in (6) and studied in [9]. The fourth
solution is Feige-Reichmann (_FR_) Algorithm 3 that uses WDR-Greedy as a sub-
routine. In fact, the candidates produced by WDR-Greedy are placed on top of
the list; then, the remaining candidates are sorted according to the WDR
metric. In this setting, FR will always performs at least as well as WDR-
Greedy, but with higher complexity.

_Results._ We present the outcome of our numerical evaluations in Table I,
including the number of scheduled UEs per slot, the geometric mean of DL
throughput across all UEs and the running time (both normalized with respect
to WDR-Greedy) as well as the number of slots between consecutive
transmissions for UEs with different AL values. These values are averaged
across the 100 simulated scenarios.

As anticipated, the FR algorithm emerges as the top-performing method, capable
of scheduling the highest number of UEs per slot and achieving the largest
geometric mean throughput. WDR-Greedy algorithm closely follows on both
metrics, trailing FR by only 1%. In contrast, W-Greedy is myopic and leads to
a low number of scheduled UEs and, consequently, low throughput fairness. The
OtG method presented in [7] schedules a reasonable number of UEs per slot but
exhibits low performance in terms of throughput fairness. Specifically, UEs
with high AL are less frequently scheduled, as evidenced by the large inter-
transmission number of slots for AL$=4,8$. We attribute this discrepancy to
the node ranking metric, which is calculated as the ratio of weight to AL and
excessively penalizes candidates with high AL. Rectifying this issue would
require a substantial increase in $M$, which becomes impractical due to
complexity constraints.

When also examining execution times reported in Table I, WDR-Greedy stands out
as offering the most favorable performance-to-complexity trade-off. In fact,
WDR-Greedy is three times faster than the top-performing FR with only a 1%
performance degradation, as mentioned earlier. W-Greedy is the lightest option
as it does not leverage the incompatibility graph, while OtG is the most
complex method as it involves calling the Optimal-Recursion Algorithm 4.

##  V Conclusions

To ease the burden of blind decoding at the UE side, the gNodeB encodes the
DCIs over a limited number of candidate frequency locations. The resulting
PDCCH candidate selection problem faced by the gNodeB is NP-hard and even
impossible to approximate. We addressed the PDCCH candidate selection problem
via techniques rooted in combinatorial optimization theory. One of them,
called WDR-Greedy, stands out as offering an excellent performance-vs-
complexity trade-off, making it suitable for implementation in 5G NR
schedulers.

## References

  * [1] 3GPP, “NR Physical channels and modulation,” 3GPP, Tech. Rep. TS38.211, 2018\.
  * [2] K. Takeda, H. Xu, T. Kim, K. Schober, and X. Lin, “Understanding the heart of the 5G air interface: An overview of physical downlink control channel for 5G new radio,” _IEEE Communications Standards Magazine_ , vol. 4, no. 3, pp. 22–29, 2020.
  * [3] V. Braun, K. Schober, and E. Tiirola, “5G NR physical downlink control channel: Design, performance and enhancements,” in _2019 IEEE Wireless Communications and Networking Conference (WCNC)_. IEEE, 2019, pp. 1–6.
  * [4] Y.-J. Yu and C.-L. Wu, “Energy-Efficient Scheduling for Search-Space Periods in NB-IoT Networks,” _IEEE Systems Journal_ , 2023.
  * [5] P. R. Manne, S. Ganji, A. Kumar, and K. Kuchi, “Scheduling and decoding of downlink control channel in 3GPP narrowband-IoT,” _IEEE Access_ , vol. 8, pp. 175 612–175 624, 2020.
  * [6] Y.-J. Yu, Y.-C. Wang, and C.-H. Fan, “Control period adaptation and resource allocation for joint uplink and downlink in nb-iot networks,” _IEEE Internet of Things Journal_ , 2024.
  * [7] Balamurali, “Optimal downlink control channel resource allocation for LTE systems,” in _2010 International Conference on Signal Processing and Communications (SPCOM)_. IEEE, 2010, pp. 1–5.
  * [8] D. P. Williamson and D. B. Shmoys, _The design of approximation algorithms_. Cambridge university press, 2011.
  * [9] S. Sakai, M. Togasaki, and K. Yamazaki, “A note on greedy algorithms for the maximum weighted independent set problem,” _Discrete applied mathematics_ , vol. 126, no. 2-3, pp. 313–322, 2003.
  * [10] U. Feige and D. Reichman, “Recoverable values for independent sets,” _Random Structures & Algorithms_, vol. 46, no. 1, pp. 142–159, 2015.
  * [11] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, _Introduction to Algorithms_. MIT press, 2009.