# Generating Unseen Code Tests In Infinitum

Marcel Zalmanovici  Orna Raz  Eitan Farchi  Iftach Freund
IBM Research AI
{marcel, ornar<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Large Language Models (LLMs) are used for many tasks, including those related
to coding. An important aspect of being able to utilize LLMs is the ability to
assess their fitness for specific usages. The common practice is to evaluate
LLMs against a set of benchmarks. While benchmarks provide a sound foundation
for evaluation and comparison of alternatives, they suffer from the well known
weakness of leaking into the training data Xu et al. (2024). We present a
method for creating benchmark variations that generalize across coding tasks
and programming languages, and may also be applied to in-house code bases. Our
approach enables ongoing generation of test-data thus mitigating the leaking
into the training data issue. We implement one benchmark, called auto-
regression, for the task of text-to-code generation in Python. Auto-regression
is specifically created to aid in debugging and in tracking model generation
changes as part of the LLM regression testing process.

Generating Unseen Code Tests In Infinitum

Marcel Zalmanovici and Orna Raz and Eitan Farchi and Iftach Freund IBM
Research AI {marcel, ornar<EMAIL_ADDRESS><EMAIL_ADDRESS>

##  1 Introduction

Many benchmarks exist for evaluating LLM generation that is related to
software development and coding tasks Zhang et al. (2023). Two well
acknowledged challenges related to utilizing benchmarks for evaluation are (1)
data leakage, where the training data of the LLM under evaluation eventually
includes benchmarks’ data, and (2) debugging or the ability to understand what
the underlying issues highlighted by benchmark failures are so that they can
be mitigated.

We introduce an approach for generating benchmarks for code related tasks that
relies on a commonly used intermediate code representation in the form of an
Abstract Syntax Tree. ASTs are often used in program analysis. In the context
of LLMs they are sometimes used to create metrics that may better fit code-
related tasks, including robustness related assessment Palacio et al. (2024);
Kumar et al. (2024). We are unaware of work that utilizes ASTs to automate the
generation of benchmarks and ease the debugging process. Our approach makes it
feasible to create new benchmarks in order to ensure that the evaluation can
generalize as we can be confident that the LLM has not trained on this newly
generated benchmark data. Our approach supports the creation of a debugging
dictionary that includes programming language constructs that have been
identified as challenging for the LLM to correctly generate. Once manually
populated, this dictionary can be used to easily debug new LLM output.

We introduce our AST-based approach for generating code related benchmarks.
Figure 1 depicts the process of generating a benchmark and testing it. The
process begins by _selecting source code_ to test the LLM with. The code
should have unit-tests, allowing to verify model output more accurately. It
would also preferably include code that was unseen during training. The chosen
source code may be in a different programming language than the task
destination code. The next step is to generate the AST. Our suggestion is to
use a tool like tree-sitter Brunsfeld and contributors (2023).

Figure 1: The process of generating custom benchmarks and running them

We demonstrate the approach depicted in Figure 1 by generating a new
benchmark, the _auto-regression benchmark_. The starting point for auto-
regression is the NAPS dataset Zavershynskyi et al. (2018) and the AST
representation that it provides (termed universal AST or uAST).

Auto-regression is a text to code benchmark where each output set of
instructions, termed problem, includes test cases as input-output tuples. The
text is generated deterministically from the NAPS AST to ensure its
correctness. Auto-regression can be viewed as following the paradigm of IFEval
Zhou et al. (2023a) and extending it with a low-level textual instructions
benchmark for code tasks. It is intended as a basis for regression testing and
eliminates the need to debug algorithmic related issues as it provides the
correct algorithm to implement. We demonstrate the notion of a debugging
dictionary for auto-regression and how we utilize it to easily debug LLM
generation issues. Having a single dictionary helps in creating regression
tests as it makes it possible to track changes in LLM versions. We see cases
where newer LLM versions improve in some categories yet introduce other
categories of problems.

To summarize, this paper’s contributions are:

  1. 1.

A method for creating benchmarks in a way that generalizes across tasks and
programming languages; the benchmark can be created from any existing code,
including in-house proprietary code. It is recommended that the code has unit
tests.

  2. 2.

A low-level text-instructions to code benchmark, the auto-regression
benchmark. 111To be released along with the publication We tested Python
generation from the benchmark.

  3. 3.

A method for creating a debugging dictionary that becomes part of the auto-
regression benchmark; this dictionary enables regression testing of
deterioration or improvement in implementing the dictionary constructs.

##  2 AST-based benchmark generation

Generating English instructions from an AST can be done by walking the tree
nodes and outputting a description from the leaves toward the root. An example
of the generated list of instructions is in Figure 1. To keep the generation
simple we limited ourselves to a single pass over the tree. This means, for
example, that we add redundant parenthesis in mathematical expressions to make
sure they are not ambiguous. We also leave calls like $f(g(h()))$ untouched
even though, for a human, expanding the calls would be clearer. For example,
concat_string(a, concat_string(b, c)) would be clearer to a human if expanded
to concatenate string a with b and c. It is possible to adjust the detail
level and expressiveness of the English generated output depending on how well
the model performs and what we are trying to test.

To get the model generated code we pass the model a set of generic
instructions and the text generated in the previous step. The generic
instructions are lists of "do" and "don’t" clarifications that help improve
performance. For example, "Do not ask for user input!" was very important
mainly to llama-family models as they tend to add unrequested code asking for
user input in the global scope, i.e. outside any Python method. This code is
executed upon import and, as a result, automated tests would get stuck at this
stage. Another example is: "Replace all array_* methods with Python list
operations" which models (except GPT) often left unimplemented even though
another instruction explicitly requests the implementation to cover all
aspects of the provided pseudo-code.

Finally, the running the code stage uses unit-test assertions to score the
performance of the model. We run the models using a greedy setting, when
possible, to get the best solution the model can come up with. We grade the
model performance using a school-like grading method where each test is a sub-
problem that earns equal points. For example, if a problem has 8 tests and the
model passes 6 it gets a grade of 0.75. We prefer this over the commonly used
pass@k Chen et al. (2021) because (1) we want a best-effort attempt, not the
probability to get at least one correct solution from $k$ attempts, and (2) to
save inference time (and cost) of running the model $k$ times.

From the AST we also generate ground-truth run-able code in the target
language. This code can be used to generate prompts for the fill-in-the-middle
(FIM) task, for running model metrics which compare code text Papineni et al.
(2002); Lin (2004) or build their own code representation Ren et al. (2020);
Zhou et al. (2023b), and for debugging the model code since due to the low-
level instructions we expect little variation in outputs.

Lastly, we also generate AST statistics. We use this to identify programming
language constructs where the model under evaluation is more likely to err. We
also count how many times each construct appears in each problem. The
statistic includes basic constructs like if/if-else conditions and loops with
and without continue or break keywords. It also includes nesting levels for
loops, whether there are operations on data structures such as
list/dictionary/set. Finally, motivated by manual analysis of model errors we
added statistics about things like ASCII operation.

###  2.1 Data

We used the NAPS dataset Zavershynskyi et al. (2018) which is generated from
solutions for competition problems posted on CodeForces. This dataset was
appealing because it represented real-world problems for which there is a
high-level description; it has multiple examples of working code; there exist
test cases and each problem has tens to hundreds of low-level instructions
created by humans. Unfortunately, the human low-level instructions proved to
contain too many errors, therefore we decided to use the AST it provided and
write an AST to English translator. The advantage of translation using code is
the consistency in description of the same operation. The downside is a lack
of variation which might catch more model issues.

We created our auto-regression datasets in two sizes: a tiny one consisting of
135 problems and a small one with 460 problems. The available data allows
generation of a dataset with a few thousand problems. However, this doesn’t
provide much additional benefit. On the small dataset we saw that models had a
higher success rate than on the tiny one. We did not see new categories of
errors, thus concluded that most instructions are easy enough to follow,
therefore there is no need to add more tests of the same construct.

Example 1 shows the instructions generated from the AST of a simple
programming problem. More examples can be found in Appendix A where we show
how common errors look like.

⬇

Define a function called __main__ getting as parameters var0 as integer, var1
as integer and returns string.

Declare var2 as integer, var3 as integer, var4 as integer.

Assign (var0 divided by func0(var0, var1)) multiplied by var1 to var2.

Assign var2 divided by var0 to var3.

Assign var2 divided by var1 to var4.

If var0 is greater than var1 then assign var3 plus 1 to var3.

Otherwise assign var4 plus 1 to var4.

If var3 is greater than var4 then return "Dasha"

Otherwise if var3 is less than var4 then return "Masha"

Otherwise return "Equal"

Figure 1: Example instructions generated from an AST.

###  2.2 Metrics

Since we have tests cases, we decided to calculate partial and whole test
pass/fail scores. The whole test pass/fail is the same as the popular pass@k
where $k=1$. The partial score treats the tests/asserts as test questions;
getting all questions right gives a full mark, getting $m$ out of $n$ correct
gives a score of $m/n$.

Not all problems in the dataset have the same number of tests. In the tiny
dataset most problems have 10 tests, but several have less, usually 7 or 5. In
the small dataset there are some problems that have 100 or more tests.

###  2.3 Debugging dictionary

Auto-regression is created such that the prompts it generates are an exact
description of the desired implementation. This enables to create a dictionary
of low level coding constructs that assists in debugging generated code that
fails to correctly pass the given tests. This dictionary can be repeatedly
used over the benchmark execution results as part of a test regression
analysis.

##  3 Benchmark results

We ran the dataset on GPT, LLama, Mixtral, Granite and Deepseek. For most we
also tried more than one version of the model for comparison. The models size
varies between 8b and 70b.

Table 2 summarizes the results of running the tiny version of the auto-
regression dataset on several models. The table is sorted by W (Whole) test
results. The clear winner is gpt-4o which failed on only 9 programs, followed
by llama-3-70b and deepseek. Since all models did sometimes pass part of the
tests (in some cases 7-9 of 10) the P (Partial) score is higher for all
models.

It is interesting to note that gpt-3.5-turbo had many issues with compilation
– all due to unmatched parenthesis, issue completely solved in gpt-4o. Also,
the older version, 1106, has less programs that fail to compile – a
regression. The overall score of the newest version, 0125, is slightly better
(partial score), meaning the model performed better when the generated program
compiled.

The infinite loop issue was mainly caused by "forgetting" to update the loop
variable either at the end of the loop or at a continue keyword.

Model |  W |  P |  Static Err |  Inf Err
---|---|---|---|---
gpt_4o |  0.93 |  0.95 |  0 |  0
llama_3_70b_instruct |  0.83 |  0.87 |  0 |  0
deepseek_coder_33b_instruct |  0.70 |  0.75 |  0 |  5
gpt_3.5_turbo_0125 |  0.67 |  0.73 |  11 |  5
gpt_3.5_turbo_1106 |  0.67 |  0.72 |  6 |  5
granite_34b_code_instruct |  0.54 |  0.62 |  2 |  7
granite_8b_code_instruct |  0.50 |  0.62 |  1 |  7
codellama_34b_instruct |  0.45 |  0.51 |  10 |  9
mixtral_8x7b_instruct_v01 |  0.43 |  0.52 |  3 |  5
llama_3_8b_instruct |  0.41 |  0.49 |  6 |  11
Table 2: Comparison of different models on the tiny version (135 programs) of
the auto-regression dataset. The W (Whole) column is the percent of programs
which passed all tests; the P (Partial) the percent of tests passed (not all
programs have the same number of tests); Static Err are programs that didn’t
parse; Inf Err are programs stuck in infinite loops

Table 3 summarizes the errors in most of the models we analyzed and
categorizes them. Note that:

  * •

Each program may have multiple issues. Therefore, summing the row may be
different than the overall error rate.

  * •

Some issues could have been assigned to more than one category, e.g. ignoring
string split could be both ignored (chosen label) or split.

  * •

It is possible that not all issues in a program were logged, especially for
programs that didn’t compile or when one or more instructions were missing.

  * •

Some programs passed several or even most tests even though they contained
errors.

There are two generic errors, ignored – the model didn’t implement some
instruction or implemented only part of it, and wrong – the model implemented
something other than what was asked of it, a hallucination. There are several
errors which were repeated often enough and across models that they received
their own category. More details on the meaning of the error labels are in
Appendix C. To test the model generated code we ran it on the tests. We
manually analyzed the failures and identified the problem. To facilitate the
analysis we used the statistics to focus on potential issues. For example,
after discovering that the models had a recurring issue with updating the loop
variable when the continue keyword should be used, if a test failed and the
stats mentioned continue as a construct we first checked whether that was the
issue.

The results show that the performance of GPT increased significantly between
the 3.5 turbo and 4o versions. The 3.5 had a major issue with closing
parenthesis, mainly when there were a lot of them in the instructions.
Anecdotally, a previous, deprecated, version of 3.5 didn’t suffer from that
issue and we measured a performance around 0.8.

For Granite the small 8b model couldn’t implement string split correctly, an
issue that was mostly solved by the newer and larger 34b model. The latter
also improved in handling of loops and ASCII. Interestingly, it "replaced" the
wrong implementation with ignoring part/whole instructions. We need to verify
whether the errors are on the same constructs/instructions in both versions.

| Granite | GPT | Deepseek | Llama
---|---|---|---|---
|  8b |  34b |  3.5 |  4o |  |  v3 70b |  code 34b
ignored |  14 |  22 |  9 |  0 |  8 |  2 |  12
wrong |  39 |  11 |  15 |  8 |  22 |  5 |  23
loop |  13 |  6 |  5 |  0 |  18 |  1 |  10
ASCII |  13 |  9 |  3 |  0 |  3 |  3 |  15
unbalanced |  0 |  1 |  11 |  0 |  0 |  0 |  3
division |  2 |  8 |  3 |  1 |  3 |  2 |  4
indent |  8 |  8 |  1 |  0 |  1 |  1 |  5
split |  15 |  5 |  0 |  0 |  0 |  7 |  4
global |  2 |  2 |  2 |  0 |  3 |  2 |  2
other |  0 |  2 |  0 |  0 |  0 |  0 |  9
Table 3: The distribution of the errors on the dataset. The first two rows
represent instructions that were partially or completely ignored (not
implemented) or "misunderstood" (hallucinations); some errors could be placed
in either. All other rows – our dictionary of issues, represent specific
errors repeated often, usually across models.

##  4 Conclusions

We introduced an AST-based methodology for automatically generating benchmarks
for LLM code related tasks. We utilized this approach to generate the auto-
regression benchmark, a low level instructions text to Python code benchmark.
Relying on ASTs also allowed us to include a dictionary of Python constructs
to ease the debugging task. Our results provide an anecdotal indication for
the usefulness of our approach and benchmark in overcoming two well
acknowledged challenges related to benchmarks – data leakage and debugging.

##  5 Limitations

We believe our methodology could apply to multiple tasks and programming
languages (PLs). However, in the paper we present only a single task and
programming language. We need to implement more benchmarks from a variety of
code repos, for a variety of tasks and PLs.

The ability to create a debugging dictionary may depend on the task and LLMs
tested. It might also depend on the level of details provided in the prompts.
We need to test our approach when implementing benchmarks with varying levels
of detail.

In the work presented here we relied solely on dynamic code execution metrics.
Relying on such metrics may be too strong a requirement and it would be good
to add static metrics.

## References

  * Brunsfeld and contributors (2023) Max Brunsfeld and contributors. 2023.  Tree-sitter: An incremental parsing system for programming tools.  GitHub repository.
  * Chen et al. (2021) Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, et al. 2021.  Evaluating large language models trained on code.  _arXiv preprint arXiv:2107.03374_.
  * Kumar et al. (2024) Anil Kumar et al. 2024.  Ast-based dataset generation for robust code models.  In _Proceedings of the 2024 International Conference on Software Engineering_.
  * Lin (2004) Chin-Yew Lin. 2004.  Rouge: A package for automatic evaluation of summaries.  In _Annual Meeting of the Association for Computational Linguistics_.
  * Palacio et al. (2024) David N Palacio, Alejandro Velasco, Daniel Rodriguez-Cardenas, Kevin Moran, and Denys Poshyvanyk. 2024.  Evaluating and explaining large language models for code using astxplainer.  _arXiv preprint arXiv:2308.03873_.
  * 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 _Annual Meeting of the Association for Computational Linguistics_.
  * 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.  _Preprint_ , arXiv:2009.10297.
  * Xu et al. (2024) Ruijie Xu, Zengzhi Wang, Run-Ze Fan, and Pengfei Liu. 2024.  Benchmarking benchmark leakage in large language models.  _arXiv preprint arXiv:2404.18824_.
  * Zavershynskyi et al. (2018) Maksym Zavershynskyi, Alexander Skidanov, and Illia Polosukhin. 2018.  NAPS: natural program synthesis dataset.  _CoRR_ , abs/1807.03168.
  * Zhang et al. (2023) Ziyin Zhang, Chaoyu Chen, Bingchang Liu, Cong Liao, Zi Gong, Hang Yu, Jianguo Li, and Rui Wang. 2023.  Unifying the perspectives of nlp and software engineering: A survey on language models for code.  _CoRR_ , abs/2311.07989.
  * Zhou et al. (2023a) Jeffrey Zhou, Tianjian Lu, Swaroop Mishra, Siddhartha Brahma, Sujoy Basu, Yi Luan, Denny Zhou, and Le Hou. 2023a.  Instruction-following evaluation for large language models.  _Preprint_ , arXiv:2311.07911.
  * Zhou et al. (2023b) Shuyan Zhou, Uri Alon, Sumit Agarwal, and Graham Neubig. 2023b.  CodeBERTScore: Evaluating code generation with pretrained models of code.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_ , pages 13921–13937, Singapore. Association for Computational Linguistics.

##  Appendix A Appendix A: Code Examples

Below is an example of the full list of the low-level instructions the models
were asked to implement. The instructions always start with the function name
and parameters, followed by the list of local variables (remnant of C/C++ in
the AST) and then the instructions themselves.

The model was asked to take a C-style while loop, which is uncommon in Python
where for-each is prevalent, and implement it in Python. The loop updates
$var7$; it also has a condition which $continues$ to the next iteration.

⬇

Define a function called __main__ getting as parameters var0 as integer, var1
as list and returns integer.

Declare var2 as integer, var3 as integer, var4 as integer, var5 as list of
strings, var6 as integer, var7 as integer, var8 as integer, var9 as integer,
var10 as integer, var11 as integer, var12 as integer.

Assign len(var1) to var2.

Assign var0 to var3.

Assign 0 to var4.

While var4 is less than var2 do:

1. Assign var4 plus 1 to var4.

Assign a new list with dimensions of sizes var2, var3 to var5.

Assign 0 to var6.

Assign var2 minus 1 to var7.

While var7 is greater than or equal to 0 do the following and decrement var7:

1. Assign var3 minus 1 to var8.

2. While var8 is greater than or equal to 0 do the following and decrement var8:

1. Assign (1 if array_index(array_index(var1, var7), var8) is equal to 87 else 0 minus 1) to var9.

2. Assign var9 minus array_index(array_index(var5, var7), var8) to var10.

3\. If var10 is equal to 0 then continue to the next iteration.

4. Assign var6 plus 1 to var6.

5. Assign 0 to var11.

6. While var11 is less than or equal to var7 do the following and increment var11:

1. Assign 0 to var12.

2. While var12 is less than or equal to var8 do the following and increment var12:

1. Assign array_index(array_index(var5, var11), var12) plus var10 to array_index(array_index(var5, var11), var12).

Return var6

In this case, the model correctly implemented the update for the loop itself,
but forgot to do the same before the continue keyword. This type of error
happened with most models. It is interesting to note that although there are 7
programs in the data-set with the continue keyword, the models got this wrong
1-3 times and correct the rest of the times.

⬇

def __main__(var0, var1):

var2 = len(var1)

var3 = var0

var4 = 0

var5 = [[0 for i in range(var3)] for j in range(var2)]

var6 = 0

var7 = var2 - 1

while var7 >= 0:

var8 = var3 - 1

while var8 >= 0:

var9 = (1 if var1[var7][var8] == 87 else 0) - 1

var10 = var9 - var5[var7][var8]

if var10 == 0:

continue

var6 += 1

var11 = 0

while var11 <= var7:

var12 = 0

while var12 <= var8:

var5[var11][var12] += var10

var12 += 1

var11 += 1

var8 -= 1

var7 -= 1

return var6

To save space, for the rest of the examples we will show partial snippets of
both instructions and resulting code.

Another common error source is ASCII handling. Here the model is asked to
implement a function which operates on the integer representation of ASCII
chars. It is asked to create a utility method that add/subtracts from a char
returning the new char and then use it.

⬇

Define a function called func0 getting as parameters var0 as character and
returns character.

Return (var0 plus -48 if (var0 is greater than or equal to 48) and (var0 is
less than or equal to 57) …

Define a function called __main__ getting as parameters var1 as string and
returns string.

…

While var6 is less than var2 do the following and increment var6:

1. If array_index(var1, var6) is not equal to 61 then assign var3 plus (func0(array_index(var1, var6)) multiplied by var5) to var3.

2. Assign var5 minus 1 to var5.

The model correctly implemented the utility method calling $ord$ and $chr$
where needed, but failed to do so in the main function.

⬇

def func0(var0):

if 48 <= ord(var0) <= 57:

return chr(ord(var0) - 48)

…

def __main__(var1):

…

while var6 < var2:

if var1[var6]! != 61:

var3 += func0(var1[var6]) * var5

var5 -= 1

var6 += 1

And here is an example where the model misinterpreted a simple assignment, one
out of more then 10 in the same program.

⬇

Define a function …

…

Assign len(var0) to var2.

…

Assign 0 to var8.

While var8 is less than var2 do the following and increment var8:

1\. Assign var9 to var7.

…

The assignment was inverse than the requirement. It is clear that the model
understand the sentence assign x to y as y = x since it does so correctly most
of the time in this and other programs, however, there are a few cases where
this goes wrong.

⬇

def __main__(var0, var1):

…

var2 = len(var0)

…

var8 = 0

while var8 < var2:

var9 = var7

…

A different kind of error, ignoring part of or the whole instruction, is also
common. Below is an example which might be explained by the model training
data. The model skips implementing the update of var6.

⬇

Define a function called func0 …

…

Assign var2 to var5.

Assign a new list of integers to var6.

array_push
(var6, -1
)

Assign 0 to var7.

If the instructions changing the value of the same variable are separated by a
few other instructions, e.g. in this case the new $var6$ initialization pushed
up a couple of instructions, then the model correctly implements the whole
sequence. This might be caused by the fact that typically programmers do not
define a variable and immediately on the next row update it.

⬇

def func0(var0, var1, var2):

…

var5 = var2

var6 = []

var7 = 0

Sometimes models are trying so "hard" to be helpful that they insert parts of
instructions, instructions or even whole pieces of code that they weren’t
asked to or even specifically told not to. For example, llama models have a
tendency to add code asking for user input.

Below is an example where a model was asked to generate a new list of strings.

⬇

Define a function …

…

Assign a new list of strings to var7.

Assign 0 to var6.

The result code was this:

⬇

def __main__(var0):

var7 = []

var7 = ["Hello", "World"]

var6 = 0

…

A final example, an error that was quite common a few months ago, but seems to
have mostly been solved recently, is mismatched parenthesis. This error is
trivial to notice since the code won’t parse/compile. Our dataset has many
redundant parenthesis because instructions are generated in a single pass and
we want to ensure correct operator order. Here is an example were many
parenthesis caused the model to err:

⬇

Define a function …

…

While var8 is less than var2 do the following and increment var8:

1. Assign min(var9, (var7 minus 1)) to var9.

2. While ((var9 plus 1) is less than var7) and ((array_index(var5, array_index(var6, (var9 plus 1))) plus (array_index(var1, array_index(var6, (var9 plus 1))) multiplied by array_index(var0, var8))) is less than or equal to (array_index(var5, array_index(var6, var9)) plus (array_index(var1, array_index(var6, var9)) multiplied by array_index(var0, var8)))) do:

…

As can be seen, there are a lot of parenthesis and clearly some are redundant,
for example around (var9 plus 1).

⬇

def __main__(var0, var1):

…

while var8 < var2:

var9 = min(var9, (var7 - 1))

while (var9 + 1 < var7) and
((var5[var6[var9 + 1]] + (var1[var6[var9 + 1]] * var0[var8])) <=
(var5[var6[var9]] + (var1[var6[var9]] * var0[var8])):

…

The marked parenthesis does not have a matching closing one.

##  Appendix B Appendix B: The Prompt

The general instructions to the models started from the simplest possible
instruction, where LANGUAGE was Python.

Implement the following pseudocode in LANGUAGE.

However, that was not enough for any of the models. They would not implement
most of the function calls most of the time, with the exception of GPT which
frequently implemented them, or at least said they should be implemented.
Therefore, this was added:

The implementation should cover all aspects of the provided pseudocode,
leaving no functions or functionality unimplemented.

This was enough for gpt, but all other models required more detailed
instructions. Since they all seem to understand * as any text we defined
these:

Replace all array_* methods with LANGUAGE list operations
Replace all string_* methods, substring* and concat with LANGUAGE string
operations.

Some instructions are very specific to a certain issue that was common:
Reminding the model to update loop variable reduced those errors by half.
Telling it to leave containers empty unless specifically requested reduced
some of the hallucinations. The instruction to declare global variables
outside the function helped granite models and llama-2, but hurt llama-3
badly. Llama-3 would randomly choose a declared variable and place it in
global scope without properly declaring it. Removing that instruction almost
completely solved the issue.

Update loop variable before issuing the "continue" keyword.
Global variables must be outside the function.
Unless specifically requested, initialization is to an empty container.

The end result is this set of instructions. These were part of the prompt with
which we ran the tests. Additional model-specific template related text had to
be added for llama and granite.

Implement the following pseudocode in LANGUAGE.
The implementation should cover all aspects of the provided pseudocode,
leaving no functions or functionality unimplemented.
Do NOT ask for user input.
Always define the requested function!
Replace all array_* methods with LANGUAGE list operations
Replace all string_* methods, substring* and concat with LANGUAGE string
operations.
Update loop variable before issuing the "continue" keyword.
Do NOT add any additional text. Wrap the code in triple back-quotes.
Global variables must be outside the function.
Unless specifically requested, initialization is to an empty container.

##  Appendix C Appendix C: Common Errors

The explanation of the errors is as follows:

  * •

loop: Usually missing loop variable update, mostly resulting in infinite loops
(or array OOB); sometimes misplaced loop variable update

  * •

ignored: Some instruction, or part of, was not implemented

  * •

wrong: The implementation is different than required, e.g. reversed
assignment, used wrong variable. Could also call this one hallucinations.

  * •

ASCII: Errors interpreting strings as ints as done in C/C++, mostly missing
ord() or chr() in some of the program instructions

  * •

unbalanced: The most common parsing/compilation error, unbalanced parenthesis

  * •

division: Several tests require integer results from division requiring a
special operator

  * •

indent: Using the wrong indentation for the line of code

  * •

split: Many tests require splitting a string (by whitespace) into an array
often misinterpreted by the model. Often split is actually redundant.

  * •

global: If modifying a global variable it needs to be declared; this is
sometimes missing

  * •

other: Any error that doesn’t fit the common categories, e.g. running out of
tokens


Department of Geographical and Sustainability Sciences, The University of
Iowa, USA and https://geo-social.com caglar-
koylu@uiowa.eduhttps://orcid.org/0000-0001-6619-6366This work is in part
supported by The National Science Foundation (NSF) Grant No. 2215568 titled
“Population-scale kinship networks and migration”Department of Geographical
and Sustainability Sciences, The University of Iowa, USAmaryam-
torkashvand@uiowa.eduhttps://orcid.org/0000-0003-4318-8085 Caglar Koylu and
Maryam Torkashvand <ccs2012> <concept>
<concept_id>10002951.10003227.10003236.10003237</concept_id>
<concept_desc>Information systems Geographic information
systems</concept_desc> <concept_significance>500</concept_significance>
</concept> </ccs2012> [500]Information systems Geographic information systems
J. Long, S. Dodge, U. Demsar, R. Weibel 4 GIScience 2023 Workshop on
Disruptive Movement Analysis (DMA) GIScience 2023 GIScience 2023 DMA’23 2023
September 12, 2023 Leeds, United Kingdom 1

# The effect of disruptive events on spatial and social interactions: An
assessment of structural changes in pre-and post-COVID-19 pandemic networks

Caglar Koylu111Corresponding author Maryam Torkashvand

###### Abstract

Disruptive events significantly alter spatial and social interactions among
people and places. To examine the structural changes in spatial and social
interaction networks in pre- and post-periods of the COVID-19 pandemic, we
employ the Louvain method to algorithmically detect regions (communities)
within the county-to-county networks of the SafeGraph mobility and Facebook
social connectedness. We then utilize a range of partition similarity metrics,
including adjusted Rand, z-Rand, Normalized Mutual Information (NMI), and
Jaccard indices, to quantitatively measure the similarity of regions between
the pre- and post-periods partitions of each network. Our findings reveal that
in the post-pandemic period, spatial interactions led to the formation of
localized geographic communities or regions characterized by higher modular
activity within each region. In contrast, online social interactions shifted
towards longer distance connections, resulting in the emergence of larger
regions marked by strong friendship ties that often encompassed multiple
states. By understanding these changes, we contribute to a better
comprehension of the pandemic’s impact on our interconnected physical-virtual
world, providing valuable insights for future research and informing
strategies to adapt to the evolving dynamics of human interactions.

###### keywords:

Disruptive events, Spatial and social interactions, Network comparison

###### category:

##  1 Introduction

Disruptive events substantially change the spatial and social interactions of
both humans and animals. While existing studies have extensively examined the
volumetric, temporal and spatial impact of such events on human activities,
the changes in structural patterns of human movement and communication
networks remain largely unexplored. For example, the COVID-19 pandemic
drastically changed how people move, communicate and form connections in real-
world and virtual settings. The pandemic has resulted in a reduction in the
frequency of human movement, leading to more localized and sparser
interactions in physical spaces [18, 7]. Simultaneously, online interactions
have become denser as individuals spent more time at home, shifting their
social interactions from the physical world to the virtual realm due to
lockdown measures [13]. Despite these observed trends, the implementation of a
national and uniform set of non-pharmaceutical interventions (NPIs) has proven
to be ineffective [2]. This is because both the incidence of the disease and
human interactions exhibit spatiotemporal heterogeneity. The impact of the
pandemic and the effectiveness of interventions vary across different
geographical locations and evolve over time. Considering the spatial and
temporal variations, only a limited number of studies implemented community-
detection algorithms to construct geographic regions that could accurately
reflect natural human movement and relationships [1, 5, 8]. These constructed
regions can serve as a foundation for implementing targeted containment
measures at a regional level, thereby enabling more effective disease control
strategies. However, despite these endeavors, there remains a lack of
systematic comparative analysis regarding the changes in structural patterns
(regions) within spatial networks before and after a disruptive event.

In this study, we introduce a network comparison workflow to assess the
structural changes in spatial and social networks during the pre- and post-
periods of the COVID-19 pandemic, utilizing two datasets: the SafeGraph
mobility [17] and Facebook’s Social Connectedness Index [3]. Specifically, we
derive county-to-county SafeGraph mobility data spanning from March 2019 to
March 2020, representing the pre-pandemic period, and from April 2020 to April
2021, representing the post-pandemic period. SafeGraph mobility data is
originally at census block groups such that each flow is from one block group
to another. We simply aggregate block group-level flow data to county-level
flow data. To explore the evolving structure of social interactions in virtual
space, we use the Facebook Social Connectedness Index (SCI) at the county
level in 2015, representing the pre-pandemic, and in 2021, representing the
post-pandemic period. SCI represents the number of Facebook friends between
user accounts in two counties divided by the product of the numbers of
accounts in those counties.

##  2 Methodology

There are two main methods for comparing networks: Unknown Node-Correspondence
(UNC) and Known Node-Correspondence (KNC) [19]. UNC methods allow for the
comparison of any pair of networks, even if they differ in size, density, or
domain. In contrast, KNC methods specifically compare two networks where the
pairwise correspondence between nodes is known. This means that the two
networks being compared using KNC should either have the same set of nodes or
at least a common subset of nodes. For our analysis, we utilize a KNC workflow
to examine the changes in community structures in pre- and post-event
networks.

To identify the community structures (regions), we first employ the Louvain
algorithm [4] on the county-to-county Facebook and SafeGraph networks of both
pre- and post-pandemic periods across the continental US. The Louvain
algorithm evaluates the strength of the partitioning of a network into modules
using a measure of modularity. A network with dense connections between nodes
within modules but sparse connections between nodes in different modules
generates high modularity. The Louvain algorithm does not enforce spatial
contiguity, thus, allows communities to be geographically distant and disjoint
from one another.

Although the similarity of communities between two partitions could be
revealed visually, it is essential to quantitatively compare the agreement
between the detected communities. We use a series of partition (or cluster)
similarity metrics including adjusted Rand, z-Rand, Normalized Mutual
Information (NMI), and Jaccard indices to quantify the similarity of the
community structures (regions) between partitions of pre- and post-periods of
each network. The most common measure is the Rand coefficient, which is the
count of pairs that clustered in the same way (either in the same or different
partitions across both networks) over the total pairs [15]. The Rand
coefficient is biased toward random partitions. To address this issue, the
Adjusted Rand Index subtracts the expected value due to randomly constructed
partitions and normalizes the result regarding the maximum threshold and mean
value [10]. In other words, the Adjusted Rand index method mitigates high
values for two randomly related partitions using a maximum bound. The z-Rand
or z-score of the Rand coefficient [16] computes the number of node pairs that
belong to the same community in two different partitions. The z-Rand score
provides statistical inference by comparing the pair-count captured by the
Rand coefficient to its expected value under a null model with the same size
communities. The Normalized Mutual Information (NMI) is an entropy measure
that evaluates the amount of shared information on two partitions [6]. A value
of 0 denotes that there is no mutual information between partitions and that
two partitions are completely different, while a value of 1 shows identical
partitions. Jaccard coefficient assesses the extent of overlap between two
partitions by calculating the ratio of the intersection of the partitions to
their union. Similar to NMI, a Jaccard coefficient of 0 indicates no overlap
or similarity between two partitions, whereas a value of 1 means a perfect
match between two partitions.

To gain insights into the geographical characteristics of regions during the
pre- and post-periods, we compute two spatial metrics. First, we calculate the
average border length per region by dividing the shared border length between
regions by the number of regions. Second, we compute compactness [14] of each
region in each partition. We then compute the mean and median compactness
measures for each partition, which offer insights into the change in the
overall shape and dispersion of regions.

##  3 Results

We algorithmically detect the regions (communities) from county-to-county
networks of Safegraph mobility and Facebook social connectedness for pre- and
post-pandemic periods using the Louvain method of modularity maximization [4].
The hypothesis that online social connections were intensified after the
pandemic can be observed by the comparison of region partitions of pre- and
post-Facebook connectedness networks. Modularity significantly decreased from
0.87 in pre-period to 0.82 of the post-period partition as a result of smaller
number of regions with larger areas in the post-pandemic period. Most notably,
the West expanded to contain parts of Utah, and Arizona whereas Mid-Atlantic
region in the East expanded to include Carolinas, Virginia, Maryland and
Southern Pennsylvania. From many smaller regions across the country reconciled
into larger regions, which include but are not limited to: (1) Wisconsin,
Minnesota, Northern Chicago, and Iowa; (2) Illinois and Indiana; (3)
Louisiana, Mississippi, and Alabama (4) West and East Texas; (5) Kansas and
Colorado; (6) Nebraska and Wyoming.

On the other hand, the hypothesis about the decrease in non-essential and
long-distance travels due to lockdowns are also observed by the comparison of
pre- and post-period partitions derived from SafeGraph data. Decrease in long-
distance flows resulted in a slight increase in the number of regions from 53
in pre- to 57 in the post-period with also a slight increase in modularity.
Most notably, regions that approximately matched state borders in the pre-
period such as Georgia, South Carolina, Illinois, and Tennessee shrunk in size
by splitting into multiple small regions. Meanwhile some regions increased in
size such as North Carolina taking northern counties of South Carolina.

When comparing the regions of online social connections and the human
mobility, there are interesting differences. For example, Upper Peninsula of
Michigan (north of Wisconsin) remain to be in the same region with the
mainland Michigan in both pre- and post-pandemic regions of Facebook. In
contrast, the western part of Upper Peninsula resides within Wisconsin region
for both pre- and post-pandemic mobility networks. This suggests that Upper
Peninsula is virtually more connected to Michigan (stronger friendships with
mainland Michigan), whereas it is more physically connected to Wisconsin
(stronger mobility flows or spatial interactions with Wisconsin).

For each partition, we compute the average shared border length per region by
dividing the total length of borders among regions by the number of regions.
In the pre-period, the network of Facebook connectedness consisted of 32
regions, with an average border length of 1055 km. In the post-period, there
were 25 regions with an average border length of 1057 km. Although the total
shared border length increases in partitions with larger number of regions,
the average border length remained similar in Facebook partitions possibly due
to the large western regions in the post-period partition. On the other hand,
SafeGraph mobility regions exhibit a reduction of 37 Km in the post-period
partition mainly because the increase in the number of regions are due to the
addition of small regions in the East, which did not affect border lengths
significantly.

Additionally, we examined the mean and median measures of compactness within
each network. A noticeable decrease in compactness values is observed for the
Facebook regions from the pre-pandemic to the post-pandemic period.
Conversely, the SafeGraph mobility regions exhibit consistent compactness
values, even as the number of regions increases from 53 to 57.

Figure 1: We apply the Louvain algorithm to detect regions for the county-to-
county networks of (A) Facebook Social Connectedness Index of 2015 (Pre-
Pandemic) (B) Facebook Social Connectedness index of 2021 (Post-Pandemic) (C)
SafeGraph Mobility: March 2019 - March 2020 (Pre-Pandemic) (D) SafeGraph
Mobility: April 2020 - April 2021 (Post-Pandemic)

Table 1 presents partition similarities of the pre- and post-pandemic Facebook
and SafeGraph networks using various metrics: z-scores of the Rand
coefficient, Adjusted Rand index, NMI, and Jaccard coefficient. Although each
of these measures reveal different aspects of the overlap between pre- and
post-period partitions, the SafeGraph mobility networks exhibit greater
regional similarity compared to the Facebook networks across all measures. The
high z-Rand scores reveal that the SafeGraph and Facebook regions of pre- and
post-periods highlight significant correlations between the post and pre
networks than should be expected at random. The Facebook regions produce 0.67
and 0.52 for the Adjusted Rand index and Jaccard index, respectively,
indicating a slightly higher level of change as compared to the Adjusted Rand
index of 0.82 and Jaccard index of 0.70 for the SafeGraph regions. These
trends are further supported by the NMI index, which indicates higher shared
information between regions in the pre- and post-pandemic SafeGraph networks
compared to the Facebook networks. Collectively, these structural comparison
measures, along with our visual comparison with the maps in Figure 1, confirm
both similarities and changes in human mobility and connections in both
physical and virtual environments following the pandemic.

Table 1: Partition similarity for pre-and post event networks Network |  | Pre-Period
---
| Post-Period
---
| z-Rand
---
| Adj. Rand
---
| Jaccard
---
| NMI
---
SafeGraph | 2019/3-2020/3 | 2020/4-2021-4 | 1656.75 | 0.82 | 0.70 | 0.93
Facebook | 2015 | 2021 | 1105.38 | 0.67 | 0.52 | 0.83

##  4 Conclusion

This study presents the preliminary results of a comparative evaluation of the
structural changes in two spatial and social interaction networks for pre- and
post-COVID-19 pandemic periods: the SafeGraph mobility network, and Facebook’s
social connectedness. Our findings highlight that the effect of the pandemic
on online social interactions and spatial interactions are very distinct.
While spatial interactions resulted in more localized geographic communities
or regions with higher modular activity within regions, online social
interactions switched to longer distance connections and thus, larger regions
of strong friendship ties that often aggregate multiple states.

Impacts of disruptive events on human movement and social interactions can
vary widely depending on the nature of the event and the context. However, our
approach to analyzing the structural changes in spatial and social interaction
networks is not unique for studying the COVID-19 pandemic and can be applied
to study the effect of disruptive events at larger or smaller geographic and
temporal scales in different domains. In future work, we plan to (1) expand
our workflow to include more comprehensive set of network comparison methods;
and (2) study the effect of another disruptive event in the U.S. history, the
Civil War, on the migration networks, which we derive from population-scale
family tree [11, 12] and linked census data [9].

## References

  * [1] Clio Andris, Caglar Koylu, Mason A Porter, et al.  Human-network regions as effective geographic units for disease mitigation.  2021\.
  * [2] Milad Baghersad, Mohsen Emadikhiav, C Derrick Huang, and Ravi S Behara.  Modularity maximization to design contiguous policy zones for pandemic response.  European journal of operational research, 304(1):99–112, 2023.
  * [3] Michael Bailey, Rachel Cao, Theresa Kuchler, Johannes Stroebel, and Arlene Wong.  Social connectedness: Measurement, determinants, and effects.  Journal of Economic Perspectives, 32(3):259–280, 2018.
  * [4] Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre.  Fast unfolding of communities in large networks.  Journal of statistical mechanics: theory and experiment, 2008(10):P10008, 2008.
  * [5] Olha Buchel, Anton Ninkov, Danise Cathel, Yaneer Bar-Yam, and Leila Hedayatifar.  Strategizing covid-19 lockdowns using mobility patterns.  Royal Society Open Science, 8(12):210865, 2021.
  * [6] Pablo A Estévez, Michel Tesmer, Claudio A Perez, and Jacek M Zurada.  Normalized mutual information feature selection.  IEEE Transactions on neural networks, 20(2):189–201, 2009.
  * [7] Song Gao, Jinmeng Rao, Yuhao Kang, Yunlei Liang, and Jake Kruse.  Mapping county-level mobility pattern changes in the United States in response to COVID-19.  SIGSpatial Special, 12(1):16–26, 2020.
  * [8] Hamish Gibbs, Emily Nightingale, Yang Liu, James Cheshire, Leon Danon, Liam Smeeth, Carl AB Pearson, Chris Grundy, LSHTM CMMID COVID-19 working group, Adam J Kucharski, et al.  Detecting behavioural changes in human movement to inform the spatial scale of interventions against covid-19.  PLoS computational biology, 17(7):e1009162, 2021.
  * [9] Jonas Helgertz, Joseph Price, Jacob Wellington, Kelly J Thompson, Steven Ruggles, and Catherine A Fitch.  A new strategy for linking us historical censuses: A case study for the ipums multigenerational longitudinal panel.  Historical Methods: A Journal of Quantitative and Interdisciplinary History, 55(1):12–29, 2022.
  * [10] Lawrence Hubert and Phipps Arabie.  Comparing partitions.  Journal of classification, 2:193–218, 1985.
  * [11] Caglar Koylu, Diansheng Guo, Yuan Huang, Alice Kasakoff, and Jack Grieve.  Connecting family trees to construct a population-scale and longitudinal geo-social network for the us.  International Journal of Geographical Information Science, 35(12):2380–2423, 2021.
  * [12] Caglar Koylu and Alice Kasakoff.  Measuring and mapping long-term changes in migration flows using population-scale family tree data.  Cartography and Geographic Information Science, 49(2):154–170, 2022.
  * [13] Apurvakumar Pandya and Pragya Lodha.  Social connectedness, excessive screen time during covid-19 and mental health: a review of current evidence.  Frontiers in Human Dynamics, 3:684137, 2021.
  * [14] Daniel D Polsby and Robert D Popper.  The third criterion: Compactness as a procedural safeguard against partisan gerrymandering.  Yale L. & Pol’y Rev., 9:301, 1991.
  * [15] William M Rand.  Objective criteria for the evaluation of clustering methods.  Journal of the American Statistical association, 66(336):846–850, 1971.
  * [16] Veronica Red, Eric D Kelsic, Peter J Mucha, and Mason A Porter.  Comparing community structure to characteristics in online collegiate social networks.  SIAM review, 53(3):526–543, 2011.
  * [17] SafeGraph.  COVID-19 Data Consortium, 2020.  Available at https://www.safegraph.com/academics (accessed 5 May 2021).  URL: https://www.safegraph.com/academics.
  * [18] Frank Schlosser, Benjamin F Maier, Olivia Jack, David Hinrichs, Adrian Zachariae, and Dirk Brockmann.  COVID-19 lockdown induces disease-mitigating structural changes in mobility networks.  Proceedings of the National Academy of Sciences of the United States of America, 117(52):32883–32890, 2020.
  * [19] Mattia Tantardini, Francesca Ieva, Lucia Tajoli, and Carlo Piccardi.  Comparing methods for comparing networks.  Scientific reports, 9(1):1–19, 2019.