# L2MAC: Large Language Model Automatic Computer for Unbounded Code Generation

Samuel Holt
University of Cambridge
<EMAIL_ADDRESS>
&Max Ruiz Luyten
University of Cambridge
<EMAIL_ADDRESS>
&Mihaela van der Schaar
University of Cambridge
The Alan Turing Institute
<EMAIL_ADDRESS>

###### Abstract

Transformer-based large language models (LLMs) are constrained by the fixed
context window of the underlying transformer architecture, hindering their
ability to produce long and logically consistent code. Memory-augmented LLMs
are a promising solution, but current approaches cannot handle long code
generation tasks since they (1) only focus on reading memory and reduce its
evolution to the concatenation of new memories or (2) use very specialized
memories that cannot adapt to other domains. This paper presents L2MAC, the
first practical LLM-based stored-program automatic computer for long and
consistent code generation. Its memory has two components: the instruction
registry, which is populated with a prompt program to solve the user-given
task, and a file store, which will contain the final and intermediate outputs.
Each instruction is executed by a separate LLM instance, whose context is
managed by a control unit capable of precise memory reading and writing to
ensure effective interaction with the file store. These components enable
L2MAC to generate virtually unbounded code structures, bypassing the
constraints of the finite context window while producing code that fulfills
complex user-specified requirements. We empirically show that L2MAC succeeds
in generating large code bases for system design tasks where other coding
methods fall short in implementing user requirements and provide insight into
the reasons for this performance gap.

###  1 Introduction

Transformer-based Large Language Models (LLMs), such as GPT-3 (Brown et al.,
2020), Instruct GPT (Ouyang et al., 2022), and the most recent GPT-4 (OpenAI,
2023), have achieved unprecedented success in generating high-quality user-
directed text. Despite their impressive capabilities, these models are
inherently restricted by a fixed context window of size $c$, which limits the
number of tokens and, consequently, the characters they can process. This
limitation manifests itself critically in tasks that require the synthesis of
extensive and logically coherent structures, such as the generation of large
code bases. Therefore, although existing LLMs excel in generating short
isolated code snippets (Chen et al., 2021), they struggle to produce code
bases that are both extensive and internally consistent due to the information
loss and contextual truncation imposed by the finite context window. But
practical code is rarely a short snippet, so this limitation undermines the
applicability of LLMs to solving real-world tasks that require the dynamic
integration of multiple components and attendance to distant information.

A natural solution is to extend the LLM agent with an external memory.
However, existing methods primarily serve to extend the implicit knowledge of
LLMs through an external corpus (Zhong et al., 2022b), to facilitate long
conversational or document summarization tasks (Liang et al., 2023), or to
maintain precise values for variables (Hu et al., 2023). In the latter case,
the approaches simply interface the LLM with a dictionary or a database, which
does not adjust to other tasks. In other settings, current approaches adopt
simplistic memory management strategies that append new information
sequentially without any provision for in-place modification. This makes any
error essentially irreversible, a critical limitation when generating code
bases, and restricts the possibility of adapting previously generated code as
the task progresses. Compounding these shortcomings, these methods do not
include mechanisms for maintaining syntactic or semantic consistency within
the external memory, a vital requirement for the generation of coherent and
interdependent code structures. Thus, existing methods are ill-suited for
extended code generation tasks.

A robust and effective method for extended code generation requires the
following three core properties:

(P1) Task-Oriented Context Management: At each computational step, the context
for the LLM should contain the information required to complete the current
instruction. The context is dynamically managed to prevent exceeding the fixed
context window size.
(P2) Precise Read/Write Tools for Entire Memory: The LLM should be endowed
with read/write operations that can interact precisely with the memory to
fetch and update relevant code blocks.
(P3) Checking the generated output: The outputs of the LLM are checked for
both mistakes and when the current instruction has been completed. When
mistakes are detected, such as syntactically invalid code, or failing self-
generated functional unit tests, they can attempt to be fixed by iterating the
discovered errors with the LLM.

With these considerations, we introduce L2MAC, the first practical LLM-based
stored-program computer framework, and instantiate it for long code generation
tasks. A Control Unit (CU) orchestrates the execution of the LLM and its
interaction with the external memory, thus satisfying the three stipulated
properties. As outlined in Figure 1, the LLM first generates a task-oriented
instruction list $\mathcal{I}$ from user-specified requirements. The CU
tailors the LLM’s context (P1), so that it always includes the next unresolved
instruction in $\mathcal{I}$ and information about the execution of past
iterations, and declutters the context when approaching its limit. It also
endows the LLM with the ability to read and update any existing region of the
memory or extend it with new code (P2). Furthermore, the CU plays a crucial
role in checking the generated output (P3). It feeds the LLM with syntactical
checker errors and requests the LLM to generate unit tests alongside generated
code, which are verified at each update of the code base to trigger corrective
actions if needed, thereby ensuring that the generated code is both
syntactically and functionally consistent.

Contributions: \raisebox{-0.9pt}{1}⃝ We introduce the L2MAC framework, the
first practical LLM-based stored-program automatic computer framework, for
long code generation tasks. \raisebox{-0.9pt}{2}⃝ We provide a practical
implementation of this framework for code generation tasks called Code-L2MAC.
This uses a Control Unit to control the input and output of the LLM and the
use of entire memory read/write tools and highlights that code checks are key
to correcting generated code that has syntactic and functional errors within
whilst conditioning on and integrating with the existing code base.
\raisebox{-0.9pt}{3}⃝ Empirically, we verify Code-L2MAC by generating large
code bases to solve for the first time high-level system design tasks of
creating entire applications and observe that it is state-of-the-art. We gain
insight and understanding of how Code-LLMatic can leverage tools to execute
and verify code by self-generating its own unit tests and use these to correct
for generation errors whilst generating large interrelated code structures
that fulfill detailed complex user-specified feature requirements.

###  2 Background

Large Language Models (LLMs). Essentially, an LLM is a probabilistic function
$l:\Sigma^{c}\rightarrow\mathcal{P}(\Sigma)$, ingesting a list of elements of
the alphabet $\Sigma$ of lengths $c$ and outputting a distribution over the
elements from which one is drawn (Vaswani et al., 2017). We refer to $c$ as
the length of the context. For example, GPT-4 and GPT-3 have fixed context
windows of $8,192$ and $4,097$, respectively.

Consequently, as discussed in Schuurmans (2023), an LLM at inference time can
be formalized as a finite-state machine (Dolfing & Hetherington, 2001). Given
the well-known and exceptional extension from finite-state machines to Turing
machines Turing et al. (1936) that leads to the practical framework of stored-
program computers, it is natural to envision a parallel extension for LLMs.

Stored-program computer (SPC). First proposed by Von Neumann (1945) as a
combination of a processor (arithmetic and logic unit), a Control Unit (CU),
and a memory capable of storing both instructions and data, SPCs set the
foundation for modern computer design. Where the control unit manages the
interaction between the processor and the data. A fundamental property of an
SPC is that it can be reprogrammed to automatically execute a program (ideally
to solve a specified task) without manual intervention111As a side note, the
Church-Turing Thesis posits that both Universal Turing Machines (UTMs) and
SPCs are capable of simulating each other and, therefore, are models of the
same class of computational processes Von Neumann (1945) (section A.1).
Recently, it has been shown that augmenting an LLM with external read-and-
write memory allows it to simulate a UTM (Schuurmans, 2023). However, we do
not aim to reproduce the capabilities of the current hardware SPC in
arithmetic and logic operations but rather explore the powerful abilities of
LLM-SPCs as automatic computers.. In more detail, the CU extracts from memory
data and instructions and correspondingly sets the input and state of the
processor (P1) and finally overwrites some memory registry with the output
(appendix A). Thus, the SPC extends the processor’s arithmetic and logic
abilities with the ability to manipulate memory (P2). An often overlooked but
vital function of the CU is error-checking of the processor’s output (P3).
“Stochastic” effects of temperature, voltage change, or radiation can cause
errors in a processor (Nicolaidis, 2010), as well as misspecified inputs can
induce overflows. Therefore, CUs implement output checks such as parity bit
checks and usually the corresponding error-correcting mechanisms (Harris &
Harris, 2010).

###  3 L2MAC Framework

Now we outline the L2MAC framework for the first practical LLM-based SPC as
illustrated in fig. 1. L2MAC consists of three main components: the LLM
processor, the memory store, and the Control Unit (CU) that controls the flow
of the execution, thus endowing the LLM with read-and-write capabilities,
among other capacities—this is illustrated in fig. 2. Some choices are
deliberately left open to differentiate the key functionalities needed from
how we tackle them in our implementation for code generation, which we detail
in the next section.

Figure 1:  Code-L2MAC Overview. Code-L2MAC is an instantiation of the LLM
automatic computer (L2MAC) for extensive code generation. First, it breaks
down the coding task into sequential instructions $\mathcal{I}$. The Control
Unit (CU) manages the LLM’s context window $C_{t}$ for each instruction and
interacts with the file store $\mathcal{D}$ through read, write, and evaluate
tools. It identifies and reads relevant code files in memory to generate or
update code per instruction (P2). This ensures proper conditioning of existing
files without losing vital context (P1). Automatic checks evaluate the LLM’s
outputs for correctness and completion (P3), with iterative error corrections
involving both code syntactical checks and running unit tests that have been
generated. Overall, this produces a complete large codebase that fulfills user
requirements in the file store $\mathcal{D}$.

####  3.1 LLM-based Processor

An inherent element of L2MAC is the Large Language Model (LLM), which is
responsible for the actual generation of the output for the task. An LLM can
be visualized as a more complex atomic unit of computation
$f:\Sigma^{c}\to\mathcal{P}(\Sigma)$, where, for instance, $|\Sigma|=50,257$
tokens (Radford et al., 2019)222The token vocabulary size is an implementation
detail of the underlying LLM used.; rather than being restricted to only
deterministic arithmetic and logical operations on binary sequences, that is,
$f:\\{0,1\\}^{64}\times\\{0,1\\}^{64}\to\\{0,1\\}^{64}$, e.g., for a standard
64-bit processor (Hennessy & Patterson, 2011). This allows for a more flexible
and powerful (yet more expensive) computation unit, which can be used to solve
a different range of tasks.

Leveraging a Large Language Model (LLM) within the L2MAC framework offers
distinct advantages to exploit and challenges to overcome, which can be
categorized according to the core properties P1, P2, and P3. On the beneficial
front, L2MAC benefits from the LLM’s awareness of external tools with which it
can interact with assisted by the Control Unit. This capability enables
requests for memory reads/writes (P2) and additional output checks (P3).

In contrast, the use of an LLM also imposes constraints that need to be
addressed. We need to address the impediments of a limited context window to
prevent incongruencies caused by the lack of attention to distant information;
that is, we have to handle context correctly (P1). Furthermore, the stochastic
nature of LLM’s output ($\mathcal{P}(\Sigma)$) is a significant risk in
situations where precision and correctness are key. Thus, crucial to
effectively updating a potentially interrelated memory is the ability to
enforce periodic checks on its output to ensure a level of correctness and
consistency (P3) (Liventsev et al., 2023).

####  3.2 Memory

Following an SPC, we distinguish between two types of memory, that of the
instruction registry $\mathcal{I}$ and the file store $\mathcal{D}$. On the
one hand, the instruction registry $\mathcal{I}$ contains the prompt program
that will be used to determine the state of the processor. In L2MAC, given the
LLM processor, this corresponds mainly to the strings that will be
incorporated into the context of the LLM at each execution. In a basic
implementation, $\mathcal{I}$ lists the sequential steps needed to complete
the task, either specified by the user or automatically generated. On the
other hand, the file store $\mathcal{D}$ stores the rest of the information
relevant for the processor to read, write, and evaluate, with the final output
ultimately stored in $\mathcal{D}$.

####  3.3 Control Unit

The control unit (CU, cf. fig. 2) is responsible for managing the context
window for the LLM, encompassing both its inputs and outputs, executing the
LLM, checking its outputs for errors, and enabling it to call functions
(tools)—including reading and writing. We further detail the CU, including a
block diagram figure and pseudocode for its operation in appendix B. First, we
start with how the CU interacts with the LLM.

#####  3.3.1 Task-Oriented Context Management (P1)

Context formalism. The CU uses the LLM as a multi-turn dialog system, filling
its context window $C$ with a combination of messages $m$ which can come from
the user $M_{u}$, an LLM response $M_{r}$, a function (tool) output $M_{f}$,
or the CU $M_{c}$, so that $m\in\\{M_{u},M_{r},M_{f},M_{c}\\}$. Consequently,
at turn $t$ then the context window333Given a set $A$, let
$\text{List}(A)=\\{(a^{i})_{i=1}^{n},a^{i}\in A\,\forall
i\in[n],\,n\in\mathbb{N}\\}$ denote the set of lists of arbitrary length
composed of elements in $A$. $C_{t}\in\text{List}(M)$ is of the form
$C_{t}=(m^{1},m^{2},\dots,m^{n_{t}})$.

To make L2MAC an automatic computer444We define what we mean by an ‘automatic’
computer in section A.2., the CU prompts the LLM to fill the initially empty
instruction registry $\mathcal{I}$ with a list of instructions
$\\{\mathcal{I}^{(1)},\dots,\mathcal{I}^{(K)}\\}$ where each will be executed
in the LLM processor555We consider the simplest case of sequential
instructions of a prompt program and discuss more complicated control flow
paradigms in appendix I.. L2MAC then loads an empty context window with the
first instruction $C^{0}\leftarrow\\{\mathcal{I}^{(0)}\\}$ and iterates the CU
control flow loop (fig. 2) until all instructions have been achieved. The LLM
can signal when the current instruction $\mathcal{I}^{(i)}$ has been completed
through calling a special function ‘step_complete’ at which point the CU
evaluates the file store $\mathcal{D}$ using its evaluator module
$\mathcal{E}$ (discussed in section 3.3.3) to check for any introduced errors.
If none are found, it asks the LLM to summarize the generated output in the
current context window $C^{t}$ as a message $M_{rs}$ and resets the context
window as $C^{t+1}\leftarrow\\{\mathcal{I}^{(k+1)},M_{rs}\\}$.

Figure 2:  Control Unit—control flow diagram for one dialog turn $t$. Here
this executes one current instruction $\mathcal{I}^{(k)}$. It starts by
loading the first instruction into the context window
$C^{0}\leftarrow\\{\mathcal{I}^{(0)}\\}$ and iterates it automatically until
all instructions in $\mathcal{I}$ have been executed. First, $C^{t}$ is
processed by the LLM Processor $\mathcal{P}_{\text{LLM}}(C^{t})$ to output
$M_{r}$. The CU stores this in a buffer
$\Delta_{C^{t+1}}\leftarrow\\{M_{r}\\}$, and checks if $M_{r}$ has called a
tool, and if so, it executes the tool with the specified input in $M_{r}$,
which includes reading, writing and evaluating $\mathcal{E}(D)$ the file store
$\mathcal{D}$—outputting $M_{f}$, which is appended to the buffer
$\Delta_{C^{t+1}}$. The CU performs additional control flow as detailed in
section 3.3, for checking if an instruction has been completed, continuing an
instruction beyond the context window (P1), and continuing executing the
current instruction.

Overcoming the fixed context window constraint. The input to the LLM cannot
exceed the context window $c$: the combined length of the initial context
$C^{t}$ and the additional messages buffer
$\Delta_{C^{t+1}}=\\{m^{0},\dots,m^{n}\\}$ must fit in the context window,
that is666We use
$\oplus:\text{List}(A)\times\text{List}(A)\rightarrow\text{List}(A)$ as the
concatenation of two lists on the set $A$. We abuse notation by considering
any $a\in A$ as a singleton $\\{a\\}$., $|C^{t}\oplus\Delta_{C^{t+1}}|\leq c$.
However, the length of $\Delta_{C^{t+1}}$ is not known a priori, so the CU
should have a way of handling the cases where $\Delta_{C^{t+1}}$ exceeds the
context margin $c-|C^{t}|$. This can be achieved through a combination of
three different strategies: (1) minimize the occurrence by promoting the task
at each time step to be small enough and economizing the filling of the
context $C$; and if the situation occurs, (2) store in the file store
$\mathcal{D}$ as much relevant output as possible from the current $C^{t}$ and
(3) update or include a new summary message with $\mathcal{I}^{(k)}$ as in-
context tuning for the next iteration.

Regarding (1), through appropriate crafting $C^{t}$, the CU can prompt the LLM
to plan sub-steps for the current instruction (most likely the original task
prompt given by the user) and then target each sub-step in the following
iterations.

For illustration, in a coding setting, (2) can be achieved by storing the
generated code so far to avoid rewriting it in the next iteration, and (3) by
initializing a new prompt with a summary $M_{rs}$ of the current progress and
helpful information to complete the current instruction, e.g., which files
should be read or modified, or the current progress made fixing errors—(3) is
further detailed at the bottom right of fig. 2.

#####  3.3.2 Precise Read/Write tools for entire memory (P2)

The need for a reading mechanism that retrieves the relevant information at
each iteration is evident and has been reasonably explored in previous
literature. In contrast, previous work on memory (as shown in section 5) has
paid little attention to the writing component, which gets mostly reduced to
the appending of new prompts and LLM outputs (Liang et al., 2023; Zhong et
al., 2022a; Cheng et al., 2023; Wu et al., 2022) or updating the values of
very structured and thus restrictive forms of memory (Modarressi et al.,
2023), e.g., variables or tables (Hu et al., 2023).

These approaches make sense for summarization, dialogs, and database
manipulation tasks but are not suitable for long interconnected output, such
as large code bases for system design tasks. Indeed, in such settings, the
possibility of downstream subtasks $\mathcal{I}^{(j)}$ demanding extensions of
previous outputs (such as modules in a code base) due to imperfect planning,
plus the non-determinism and common hallucination of LLMs, make it probable to
require modifications of previously stored memories $\mathcal{D}$ to rectify
these defects, as shown in section 6.2.

In L2MAC it is thus key to implement read/write interactions with any part of
the memory. We want the agent to be able to scan on demand $\mathcal{D}$,
retrieve parts of the memory that it considers relevant, and potentially
update them. In the next section 4, we detail our implementation of an LLM
with a write component that allows it not only to add new information to
$\mathcal{D}$ but also to delete and update any of its contents, which is an
essential element that allows the method to succeed in coding tasks.

#####  3.3.3 Checking the generated output (P3)

As discussed in section 3.1 and 3.3.2, the intrinsic stochasticity of LLMs and
the well-known phenomenon of hallucination (OpenAI, 2023) make it likely that
incoherent or erroneous outputs occur during long interactions, which can be
fatal, for example, in coding. More profoundly, changes (e.g., to a function)
to satisfy a given $\mathcal{I}^{(j)}$ can hamper the solution to formerly
completed instructions $\mathcal{I}^{(i)}$, $i<j$. Therefore, it is essential
to incorporate two key checks, one to check the generated outputs for errors
using a given evaluator module $\mathcal{E}$, and the other to check when the
current instruction has been completed in the current context $C^{t}$ (as seen
in the top and center rhombus in fig. 2).

Error checking and error correction. Using a given evaluator module
$\mathcal{E}$, which can process the existing file store $\mathcal{D}$, i.e.,
$\mathcal{E}(D)$, allows when run, errors to be detected and returned to the
LLM as an evaluator message $M_{fe}$. The evaluator is domain-specific; for
example, in coding tasks, this can correspond to syntactical code checkers or
self-generated unit tests that verify the correctness of the output for an
instruction $\mathcal{I}^{(i)}$. Crucially, these self-generated unit tests
also help test the existing functionality of previously generated instructions
$\mathcal{I}^{(j)}$. Naturally, evaluation checks should be enforced in the
file store $\mathcal{D}$ after each writing operation to ensure that new
additions are correct and consistent with previous files. These result in
messages $M_{fe}$ that are provided for in-context learning so that the LLM
can correct the errors, $\Delta_{C^{t+1}}\leftarrow\Delta_{C^{t+1}}\oplus
M_{fe}$, and iterate by rewriting $\mathcal{D}$ until the evaluator checks
pass.

Checking current instruction completion. To ensure continued execution in a
multi-turn dialogue LLM system until completion, we can request the LLM about
the next step to take or tool (function) to execute (Wang et al., 2023). This
is achieved through a cycle prompt message $M_{cc}$ that also asks the LLM if
the instruction has been completed. Cycle prompting is necessary to account
for different instructions requiring variable number of turns, and to protect
against hallucinations where the LLM agent only discusses $\mathcal{I}^{(i)}$
but does not generate a solution or store it in memory. Overall, this insists
that the LLM provides a solution for the given instruction within the current
context (P3).

###  4 Code-L2MAC

Now, we use our LLM automatic computer (L2MAC) framework and instantiate it to
complete large code generation tasks, which we call Code-L2MAC. We distinguish
the framework from the instantiation to detach the core components from
decisions that could be refined in future iterations of the method. We provide
the full details of the implementation in appendix C; yet here we highlight
some notable design decisions on the memory layout (in particular,
$\mathcal{D}$) and the read logic. There are different potentially valid
alternatives for the read component in L2MAC (e.g., Wu et al. (2022)).
However, to promote a transparent read component, we make the following
choices.

We specify $\mathcal{D}$ to be composed solely of files, each shorter than the
residual margin of the context window after accounting for preliminary
messages in any iteration777More precisely, no longer than half such margin to
ensure the LLM can rewrite any file within its context and instruct the LLM to
assign each file a semantically descriptive path. For example, a file name
models/user.py suggests that it contains the data model for the user class.
This choice is not only valuable for a human reader but also crucial for our
Read-and-Write implementation, as it allows the LLM to infer the content of
existing files $\mathcal{D}$ and prioritize those that it might need to read
to complete its current instruction. Given the list of paths, the LLM can
request that the contents of any be appended to its context window $C_{t}$.
Although the path-to-content link is not absolute, empirically, this read
implementation can perform well (section 6), when coupled with the context
management logic of the CU. Specifically, if the LLM reads the content of
certain files and reaches the context window limit, it can include in its
subsequent iteration summary indications of which files should be read and
which should be excluded in order to generate the code necessary to complete
the current instruction. This approach thereby enables the LLM to
systematically scan all memory, with the scanning order guided by priorities
previously established from the path names.

###  5 Related Work

In the following, we review the existing memory-augmented LLM-based
approaches, focusing on approaches applicable to completing large-generation
coding tasks—and summarize their main differences in Table 1. We provide an
extended discussion of additional related works, including those of other
single-turn code generation methods and memory-augmented LLMs in appendix D.

Single LLMs. Although basically limited to outputs of the order of the context
window, are widely used for coding and suit as a baseline. Notable examples
include Codex (Chen et al., 2021), GPT4 (OpenAI, 2023), GPT-Engineer (Osika,
2023) and Code LLama (Rozière et al., 2023).

Reflecting LLMs enhance the performance of LLMs by having the LLM reflect
retrospectively on the output of an evaluator and the actions taken (Shinn et
al., 2023; Madaan et al., 2023). These verbal reflections are used as in-
context learning (Dong et al., 2022) to improve performance when attempting
the task again. By using a validator, such as self-generated unit tests, this
simple idea has provided state-of-the-art small code snippet generation
performance (Shinn et al., 2023). Still, the output of these approaches is
also confined to the context window, whereas L2MAC uses an evaluator not only
for in-context learning but also for consistency of the code base and can
generate large code bases that are virtually unbounded.

Memory-augmented LLMs. Most work on this topic focuses on long
conversational/text summarization tasks (Liang et al., 2023; Zhong et al.,
2022a; Cheng et al., 2023), or mathematical/database reasoning (Hu et al.,
2023). Methods in the first group usually focus exclusively on the read
component of memory. The same happens with (Wu et al., 2022), which, through
$k$-NN retrieval for next-token predictions, enhances perplexity for multiple
tasks, including coding. However, read-only implementations are sensitive to
the inconsistency and “stochasticity” of LLMs, which might break code, and the
method cannot be then fixed. Modarressi et al. (2023) contemplates updating
memories, but they use tuples with two subjects and their relation, so they
have no clear application to coding tasks. Similarly, the memory of
mathematical/database reasoning methods is a dictionary of values or a
structured database, which again is not applicable to different settings
(e.g., coding).

Table 1: Comparison of related works. Columns: Context Management (P1)—can it
generate a larger output than $c$, and if so, can it access the necessary
files to generate the next file correctly without knowledge of the file
falling out of context? Precise Read/Write for entire memory (P2)—can it write
to the full external memory and update it in any order? Can it check the LLMs
generated output for mistakes (P3)? References:[1](Richards, 2023)[2](Shrestha
& Watkins, 2023)[3](Nakajima, 2023)[4](Chen et al., 2021)[5](Osika,
2023)[6](Shinn et al., 2023)[7](Madaan et al., 2023).

Approach | Methods | Context handling (P1)? | Precise Read/Write to Entire | Checking the generated
---|---|---|---|---
|  |  | External Memory (P2)? | output (P3)?
Autonomous Agent LLMs with memory | [1,2,3] | ✗– forgets which files were generated | ✓ | ✗No checks
Single LLMs | [4,5] | ✗– limited to $c$ | ✗ | ✗
Reflecting LLMs | [6,7] | ✗ |  | ✗– limited to append-only
---
read always memory
✓
Code-L2MAC | This work | ✓ | ✓ | ✓

Autnomous Agent LLMs with memory. (Richards, 2023; Shrestha & Watkins, 2023;
Nakajima, 2023) formulate the LLM as a fully autonomous agent in a
reinforcement learning environment, persisting until the task is completed
(Wang et al., 2023). They build and update their own plans from a few user-
given high-level goals. When coding, these agents reprogram and reformulate
their step plan at runtime, resulting in frequent deviations from the task and
stalls in infinite loops (Wang et al., 2023; Sato et al., 2023). In
comparison, L2MAC is designed to be automatic, i.e., it fulfills the user-
specified requirements without altering or forgetting them. The only existing
autonomous agent LLM with applicable memory capable of writing, reading, and
executing code is AutoGPT (Richards, 2023). It tackles the constraint of the
context window by iteratively summarizing previous actions completed every
$k$-th turn and only keeping such summary in context. Like other agents, the
first step of AutoGPT is to summarize the user-specified task into a name,
role, and five one-sentence goals for the agent to complete; this summary is
kept in context throughout execution. AutoGPT and associated methods have two
key limitations compared to L2MAC (cf. fig. 4): (1) they compress the initial
detailed user-specified task into a six-sentence description, and (2) they
compress the previous action history, thus usually losing critical information
in the process. In code generation tasks, (2) indicates forgetting which files
exist and their content, which is compounded by continual re-planning.

###  6 Experiments and Evaluation

In this section, we evaluate the Code-L2MAC framework and verify that it
significantly outperforms state-of-the-art methods in long system design code
generation tasks. Due to the absence of an existing benchmark for long code
generation tasks, we present one to enable comparison with other methods.
Furthermore, there are also no automated tools to validate the output of
system design tasks either; we propose evaluation metrics to compare the
output of different methods.

Benchmark tasks. We evaluate against three standard system design code base
generation tasks whose prompt questions are taken from real-world system
design interview questions (Xu & Lam, 2020; Martin, 2023). We detail all
benchmark tasks in appendix F.

Evaluation metrics. Large-scale code generation is unique in that the
generated code can satisfy the high-level user feature requirements specified
in the input through various possible implementation approaches. To quantify
the degree to which user-specified features in the initial prompt are
effectively implemented in the generated code, we introduce a performance
metric named Features %. This metric numerically represents the proportion of
input features that are fully and functionally implemented in the output code
base. The Features % is obtained by using a separate GPT-4 API call, which
iteratively examines the entire generated code to verify the functional
implementation of all input features, counting the number of fully implemented
features. We quote this as a percentage of the features implemented over the
total features specified by the user. A detailed description and a motivating
example of this implementation are provided in appendix G. We also incorporate
standard code generation evaluation metrics (Hasemer, 2018), such as the
number of lines of code generated LOC and the number of errors # Errors in the
code base determined by a code syntactical analyzer (Thénault, 2023).
Furthermore, the methods are instructed to generate unit tests to check that
the generated code is valid; therefore, we quote how many self-generated unit
tests pass that the method generated as Tests Passed. We give each metric with
their 95$\%$ confidence intervals throughout. Moreover, we detail these
metrics and the experimental setup in more detail in appendix G.

Benchmark methods. To assess whether Code-L2MAC is state-of-the-art, we
compare it with the most competitive and popular autonomous agent LLMs with
memory AutoGPT (Richards, 2023), based on GPT4 and capable of reading,
writing, and persisting, using a vector embedding memory to complete given
tasks autonomously. We also compare with the single GPT4 LLM (GPT4) (OpenAI,
2023), which we adapt to make it competitive by providing it with the same
tools that Code–L2MAC uses, forming an ablation of just using an LLM processor
without the control unit. We provide the method implementation details,
hyperparameters, and experimental details in appendix F.

####  6.1 Main results

We evaluated all the benchmark methods across all our system design tasks with
results tabulated in Table 2. Code-L2MAC fully implements the highest
percentage of user-specified feature requirements across all tasks by
generating fully functional code that has minimal syntactical errors and a
high number of passing self-generated unit tests—therefore, Code-L2MAC is
state-of-the-art for completing these system design large code generation
benchmark tasks.

####  6.2 Insight experiments

This section provides an in-depth empirical analysis of the efficacy of
Code-L2MAC compared to its benchmark counterparts, AutoGPT and GPT-4.
Specifically, we examine the core properties we suggested a robust extended
code generation framework should possess: task-oriented Context Management
(P1), precise read/write tools (P2), and output error checking and correcting
(P3).

Table 2:  Codebase generation system design task results showing the
percentage of functional features specified that are fully implemented
(Features %), the number of syntactical errors in the generated code (#
Errors), the number of lines of code (LOC), and number of passing tests (Tests
Passed). Code-L2MAC fully implements the highest percentage of user-specified
feature requirements across all tasks by generating fully functional code that
has minimal syntactical errors and a high number of passing self-generated
unit tests. The results are averaged over 10 random seeds, with $\pm$
indicating 95$\%$ confidence intervals.

| URL Shortener App | Online Microblogging App | Online Chat App
---|---|---|---
Method | Features % | # Errors | LOC | Tests Passed | Features % | # Errors | LOC | Tests Passed | Features % | # Errors | LOC | Tests Passed
| $\uparrow$ | $\downarrow$ |  | $\uparrow$ | $\uparrow$ | $\downarrow$ |  | $\uparrow$ | $\uparrow$ | $\downarrow$ |  | $\uparrow$
GPT4 | 48.2$\pm$15.2 | 0$\pm$0 | 107$\pm$32.7 | 2.3$\pm$1.01 | 17.9$\pm$8.27 | 3.75$\pm$3.09 | 106$\pm$35.4 | 0.75$\pm$0.723 | 11$\pm$2.26 | 0.3$\pm$0.346 | 127$\pm$24.1 | 1.2$\pm$1
AutoGPT | 25.3$\pm$19.6 | 0$\pm$0 | 136$\pm$41.9 | 3.3$\pm$1.91 | 33.3$\pm$18 | 0.6$\pm$0.369 | 148$\pm$35.5 | 3$\pm$2.86 | 23.1$\pm$11.8 | 1.85$\pm$2.47 | 220$\pm$65.8 | 3.08$\pm$3.34
LLMatic | 91.6$\pm$8.22 | 0$\pm$0 | 330$\pm$47.6 | 14$\pm$6.71 | 82.4$\pm$14.6 | 0$\pm$0 | 395$\pm$52.9 | 18.3$\pm$6.8 | 59.4$\pm$25.9 | 0$\pm$0 | 374$\pm$123 | 18.8$\pm$9.11

Can Code-L2MAC correctly perform task-oriented context management? (P1).

Figure 3: Heatmap of file access. Indicating reading, writing, and when files
are created at each write operation step during one episode for the Online
Chat App task.

To explore if the benchmarked methods during operation contain the information
within their context to complete the task directly, we adapted our Features %
metric to count the number of user-specified feature requirements that are
retained within the methods task instructions instead, i.e., those
instructions that are eventually fed into its context window during its
operation, as shown in fig. 4 (a). Empirically, we observe that Code-L2MAC is
able to retain a high number of user-specified feature requirements within its
instructions $\mathcal{I}$ and perform instruction-oriented long-running
tasks. We note that AutoGPT also initially translates the user-specified
feature requirements into task instructions; however, it does so with higher
compression—condensing the information into a mere six-sentence description.
This process results in the loss of crucial task information necessary for
completing the overall task correctly, such that it aligns with user
requirements.

Can Code-L2MAC perform precise read/write operations for the entire file store
(P2)? We wish to understand, during the operation of executing a task
instruction, if Code-L2MAC can understand the existing generated code files
within the code base—which could have been created many instructions ago, and
through its understanding, create new files that interrelate with the existing
files, and most importantly update existing code files as new features are
implemented. To derive insight, we plot a heatmap of the reading, writing, and
when files are created at each write operation step during one episode in fig.
3. We observe that Code-L2MAC has an understanding of the existing generated
code that allows it to update existing code files, even those originally
created many instruction steps ago, and can view the files when it is not
certain and update the files through writing to the files. In contrast,
AutoGPT often only writes to files once, when initially creating them, and can
only update files that it knows about that are retained within its current
context window. Although it also has a read file tool, it often forgets about
the files that it created many iterations ago due to its context window
handling approach of summarizing the oldest dialog messages in its context
window, i.e., a continual lossy compression of the previous progress made
during operation of completing the task.

Can Code-L2MAC check the generated output and error correct (P3)? When using a
probabilistic model (LLM) as a generator to output code, errors can naturally
occur in its outputs. Therefore, we wish to verify if, when errors do appear,
the respective benchmark methods can error-correct the code base. We plot the
number of syntactical errors in the code base during a run where errors are
made in fig. 4 (b). We observe that Code-L2MAC can correctly error correct the
previously generated code base that has errors contained within, which could
arise from syntactical errors from the last file written or other files that
depend on the most recent file written, which now contain errors. It does this
by being presented with the error output when it does arise and modifying the
code base to resolve the error whilst still completing the current
instruction. In contrast, AutoGPT cannot detect when an error in the code base
has been made and continues operating, which can compound the number of errors
forming within the code base.

Moreover, Code-L2MAC generates unit tests alongside the functional code and
uses these as an error checker to inspect the functionalities of the code base
as it is generated and can use these errors to fix the code base to pass unit
tests that now fail after updating part of an existing file. We show this in
fig. 4 (c) and observe that AutoGPT, whilst prompted to also write unit tests
for all code generated, is unable to use these tests as an integrity error
check, and they fail, which could be compounded by the observation that
AutoGPT forgets which files it has previously created and hence unable to
modify the existing forgotten code files as new modifications are made,
leading to incompatible code files.

Figure 4: Experimental Insight during operation—of generating a code base for
an Online Chat app task. (a) Percentage of user-specified feature requirements
that are retained within the methods task instructions and used in context.
(b) Number of syntactical errors within the code base. (c) Histogram of self-
generated unit tests that are passing and failing.

###  7 Conclusion and Future work

In this paper, we present L2MAC, the first LLM-based SPC framework that
effectively and scalably augments LLMs with memory for tasks where this was
not previously successfully achieved. Specifically, Code-L2MAC, an application
for long code generation, surpasses existing solutions—and is an immensely
useful tool for rapid development. This work is not without limitations.
L2MAC’s performance is inherently bounded by its underlying LLM across various
tasks, from planning to function calling. While there is no strict assurance
of task completion within a finite iteration count, this can be mitigated
through thresholding. Further, the current design imposes an implicit
constraint on the scale of the code base by listing all file names, which
could readily be improved. These, and among many other aspects such as complex
instruction flows, re-programming the instructions, and interpretable prompt
programs pose exciting open directions for future work, appendix I.

Ethics statement. This paper proposes the first practical framework for an
LLM-based SPC and instantiates a version to generate large code bases,
Code-L2MAC. However, misuse or use of such a tool with an incorrectly
specified task could lead to undesirable outputs. Furthermore, due to the use
of an LLM, such a tool is prone to hallucinations, and hence, such results
should always have a content filter on the final output.

Reproducibility statement. All code will be released upon acceptance. Seeking
full reproducibility, we include an extensive appendix with all implementation
and experimental details to re-create the benchmark tasks and baseline
methods. These are detailed in the following: for benchmark task environment
details, see appendix E; for benchmark method implementation details, see
appendix F; regarding Code-L2MAC implementation details, for high-level
details, see appendix C, and for low-level details, see section F.1; and for
evaluation metric details, see appendix G.

### References

  * Beltagy et al. (2020) Iz Beltagy, Matthew E. Peters, and Arman Cohan.  Longformer: The long-document transformer, 2020.
  * Borgeaud et al. (2022) Sebastian Borgeaud, Arthur Mensch, Jordan Hoffmann, Trevor Cai, Eliza Rutherford, Katie Millican, George van den Driessche, Jean-Baptiste Lespiau, Bogdan Damoc, Aidan Clark, Diego de Las Casas, Aurelia Guy, Jacob Menick, Roman Ring, Tom Hennigan, Saffron Huang, Loren Maggiore, Chris Jones, Albin Cassirer, Andy Brock, Michela Paganini, Geoffrey Irving, Oriol Vinyals, Simon Osindero, Karen Simonyan, Jack W. Rae, Erich Elsen, and Laurent Sifre.  Improving language models by retrieving from trillions of tokens, 2022.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Bulatov et al. (2022) Aydar Bulatov, Yury Kuratov, and Mikhail Burtsev.  Recurrent memory transformer.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), _Advances in Neural Information Processing Systems_ , volume 35, pp. 11079–11091. Curran Associates, Inc., 2022.  URL https://proceedings.neurips.cc/paper_files/paper/2022/file/47e288629a6996a17ce50b90a056a0e1-Paper-Conference.pdf.
  * Chen et al. (2021) Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al.  Evaluating large language models trained on code.  _arXiv preprint arXiv:2107.03374_ , 2021.
  * Cheng et al. (2023) Xin Cheng, Yankai Lin, Xiuying Chen, Dongyan Zhao, and Rui Yan.  Decouple knowledge from paramters for plug-and-play language modeling.  In _Findings of the Association for Computational Linguistics: ACL 2023_ , pp. 14288–14308, Toronto, Canada, July 2023. Association for Computational Linguistics.  doi: 10.18653/v1/2023.findings-acl.901.  URL https://aclanthology.org/2023.findings-acl.901.
  * Child et al. (2019) Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever.  Generating long sequences with sparse transformers, 2019.
  * Choromanski et al. (2022) Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, David Belanger, Lucy Colwell, and Adrian Weller.  Rethinking attention with performers, 2022.
  * Dohan et al. (2022) David Dohan, Winnie Xu, Aitor Lewkowycz, Jacob Austin, David Bieber, Raphael Gontijo Lopes, Yuhuai Wu, Henryk Michalewski, Rif A Saurous, Jascha Sohl-Dickstein, et al.  Language model cascades.  _arXiv preprint arXiv:2207.10342_ , 2022.
  * Dolfing & Hetherington (2001) Hans JGA Dolfing and I Lee Hetherington.  Incremental language models for speech recognition using finite-state transducers.  In _IEEE Workshop on Automatic Speech Recognition and Understanding, 2001. ASRU’01._ , pp. 194–197. IEEE, 2001.
  * Dong et al. (2022) Qingxiu Dong, Lei Li, Damai Dai, Ce Zheng, Zhiyong Wu, Baobao Chang, Xu Sun, Jingjing Xu, and Zhifang Sui.  A survey for in-context learning.  _arXiv preprint arXiv:2301.00234_ , 2022.
  * Giannou et al. (2023) Angeliki Giannou, Shashank Rajput, Jy yong Sohn, Kangwook Lee, Jason D. Lee, and Dimitris Papailiopoulos.  Looped transformers as programmable computers, 2023.
  * Graves et al. (2014) Alex Graves, Greg Wayne, and Ivo Danihelka.  Neural turing machines, 2014.
  * Guo et al. (2022) Mandy Guo, Joshua Ainslie, David Uthus, Santiago Ontanon, Jianmo Ni, Yun-Hsuan Sung, and Yinfei Yang.  LongT5: Efficient text-to-text transformer for long sequences.  In _Findings of the Association for Computational Linguistics: NAACL 2022_ , pp. 724–736, Seattle, United States, July 2022. Association for Computational Linguistics.  doi: 10.18653/v1/2022.findings-naacl.55.  URL https://aclanthology.org/2022.findings-naacl.55.
  * Harris & Harris (2010) David Harris and Sarah Harris.  _Digital design and computer architecture_.  Morgan Kaufmann, 2010.
  * Hasemer (2018) Tony Hasemer.  Syntactic debugging of procedural programs.  In _Novice Programming Environments_ , pp. 227–241. Routledge, 2018.
  * Hennessy & Patterson (2011) John L Hennessy and David A Patterson.  _Computer architecture: a quantitative approach_.  Elsevier, 2011.
  * Hu et al. (2023) Chenxu Hu, Jie Fu, Chenzhuang Du, Simian Luo, Junbo Zhao, and Hang Zhao.  Chatdb: Augmenting llms with databases as their symbolic memory.  _arXiv preprint arXiv:2306.03901_ , 2023.
  * Liang et al. (2023) Xinnian Liang, Bing Wang, Hui Huang, Shuangzhi Wu, Peihao Wu, Lu Lu, Zejun Ma, and Zhoujun Li.  Unleashing infinite-length input capacity for large-scale language models with self-controlled memory system.  _arXiv preprint arXiv:2304.13343_ , 2023.
  * Liu et al. (2023) Nelson F Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang.  Lost in the middle: How language models use long contexts.  _arXiv preprint arXiv:2307.03172_ , 2023.
  * Liventsev et al. (2023) Vadim Liventsev, Anastasiia Grishina, Aki Härmä, and Leon Moonen.  Fully autonomous programming with large language models.  _arXiv preprint arXiv:2304.10423_ , 2023.
  * Madaan et al. (2023) Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al.  Self-refine: Iterative refinement with self-feedback.  _arXiv preprint arXiv:2303.17651_ , 2023.
  * Martin (2023) Donne Martin.  System design primer.  https://github.com/donnemartin/system-design-primer, 2023.
  * Modarressi et al. (2023) Ali Modarressi, Ayyoob Imani, Mohsen Fayyaz, and Hinrich Schütze.  Ret-llm: Towards a general read-write memory for large language models, 2023.
  * Nakajima (2023) Yohei Nakajima.  Babyagi.  https://github.com/yoheinakajima/babyagi, 2023.
  * Nicolaidis (2010) Michael Nicolaidis.  _Soft errors in modern electronic systems_ , volume 41.  Springer Science & Business Media, 2010.
  * Okken (2022) Brian Okken.  _Python Testing with pytest_.  Pragmatic Bookshelf, 2022.
  * OpenAI (2023) OpenAI.  Gpt-4 technical report, 2023.
  * Osika (2023) Anton Osika.  Gpt-engineer.  https://github.com/AntonOsika/gpt-engineer, 2023.
  * Ouyang et al. (2022) Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al.  Training language models to follow instructions with human feedback.  _Advances in Neural Information Processing Systems_ , 35:27730–27744, 2022.
  * Peng et al. (2021) Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah A. Smith, and Lingpeng Kong.  Random feature attention, 2021.
  * Phang et al. (2022) Jason Phang, Yao Zhao, and Peter J. Liu.  Investigating efficiently extending transformers for long input summarization, 2022.
  * Press et al. (2022) Ofir Press, Noah Smith, and Mike Lewis.  Train short, test long: Attention with linear biases enables input length extrapolation.  In _International Conference on Learning Representations_ , 2022.  URL https://openreview.net/forum?id=R8sQPpGCv0.
  * 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.
  * Richards (2023) Toran Bruce Richards.  Autogpt.  https://github.com/Significant-Gravitas/Auto-GPT, 2023.
  * Rozière et al. (2023) Baptiste Rozière, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, et al.  Code llama: Open foundation models for code.  _arXiv preprint arXiv:2308.12950_ , 2023.
  * Sato et al. (2023) Megan Kinniment Lucas Jun Koba Sato, Haoxing Du, Brian Goodrich, Max Hasin, Lawrence Chan, Luke Harold Miles, Tao R Lin, Hjalmar Wijk, Joel Burget, Aaron Ho, et al.  Evaluating language-model agents on realistic autonomous tasks.  https://evals.alignment.org/Evaluating_LMAs_Realistic_Tasks.pdf, 2023.
  * Schick et al. (2023) Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom.  Toolformer: Language models can teach themselves to use tools, 2023.
  * Schuurmans (2023) Dale Schuurmans.  Memory augmented large language models are computationally universal.  _arXiv preprint arXiv:2301.04589_ , 2023.
  * Shinn et al. (2023) Noah Shinn, Beck Labash, and Ashwin Gopinath.  Reflexion: an autonomous agent with dynamic memory and self-reflection.  _arXiv preprint arXiv:2303.11366_ , 2023.
  * Shrestha & Watkins (2023) Asim Shrestha and Adam Watkins.  Agentgpt.  https://github.com/reworkd/AgentGPT, 2023.
  * Tassiulas & Ephremides (1990) Leandros Tassiulas and Anthony Ephremides.  Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks.  In _29th IEEE Conference on Decision and Control_ , pp. 2130–2132. IEEE, 1990.
  * Tay et al. (2022) Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler.  Efficient transformers: A survey, 2022.
  * Thénault (2023) Sylvain Thénault.  Pylint, 2023.  URL https://pylint.readthedocs.io/en/stable/.  Available at: http://pylint.pycqa.org/.
  * Turing et al. (1936) Alan Mathison Turing et al.  On computable numbers, with an application to the entscheidungsproblem.  _J. of Math_ , 58(345-363):5, 1936.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Von Neumann (1945) John Von Neumann.  First draft of a report on the edvac, 30 june 1945.  _Moore School of Electrical Engineering, University of Pennsylvania, Philadelphia, PA, USA. Available online: https://library. si. edu/digital-library/book/firstdraftofrepo00vonn (accessed on 1 October 2022)_ , 1945.
  * Wang et al. (2023) Lei Wang, Chen Ma, Xueyang Feng, Zeyu Zhang, Hao Yang, Jingsen Zhang, Zhiyuan Chen, Jiakai Tang, Xu Chen, Yankai Lin, et al.  A survey on large language model based autonomous agents.  _arXiv preprint arXiv:2308.11432_ , 2023.
  * Wang et al. (2020) Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma.  Linformer: Self-attention with linear complexity, 2020.
  * Wu et al. (2021) Jeff Wu, Long Ouyang, Daniel M. Ziegler, Nisan Stiennon, Ryan Lowe, Jan Leike, and Paul Christiano.  Recursively summarizing books with human feedback, 2021.
  * Wu et al. (2022) Yuhuai Wu, Markus N. Rabe, DeLesley Hutchins, and Christian Szegedy.  Memorizing transformers, 2022.
  * Xu & Lam (2020) Alex Xu and Sahn Lam.  _System Design Interview: An Insider’s Guide_ , volume 1.  Byte Code LLC, 2020.
  * Yao et al. (2022) Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao.  React: Synergizing reasoning and acting in language models.  _arXiv preprint arXiv:2210.03629_ , 2022.
  * Yogatama et al. (2021) Dani Yogatama, Cyprien de Masson d’Autume, and Lingpeng Kong.  Adaptive semiparametric language models, 2021.
  * Zaheer et al. (2021) Manzil Zaheer, Guru Guruganesh, Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and Amr Ahmed.  Big bird: Transformers for longer sequences, 2021.
  * Zhang et al. (2022) Yusen Zhang, Ansong Ni, Ziming Mao, Chen Henry Wu, Chenguang Zhu, Budhaditya Deb, Ahmed Awadallah, Dragomir Radev, and Rui Zhang.  Summn: A multi-stage summarization framework for long input dialogues and documents.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 1592–1604, Dublin, Ireland, May 2022. Association for Computational Linguistics.  doi: 10.18653/v1/2022.acl-long.112.  URL https://aclanthology.org/2022.acl-long.112.
  * Zhong et al. (2022a) Zexuan Zhong, Tao Lei, and Danqi Chen.  Training language models with memory augmentation.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pp. 5657–5673, Abu Dhabi, United Arab Emirates, December 2022a. Association for Computational Linguistics.  doi: 10.18653/v1/2022.emnlp-main.382.  URL https://aclanthology.org/2022.emnlp-main.382.
  * Zhong et al. (2022b) Zexuan Zhong, Tao Lei, and Danqi Chen.  Training language models with memory augmentation, 2022b.

##  Appendix

All code will be released upon acceptance.

###  Appendix A Stored-program computers (SPC)

Stored-program computer (SPC). First proposed by Von Neumann (1945), it
corresponds to a combination of a processor (arithmetic and logic unit) and a
memory capable of storing both instructions and data. SPCs set the foundation
for modern computer design. With a control unit (CU) managing the interaction
between both components, this design is capable of being reprogrammed to solve
various tasks without manual intervention 888As a side note, the Church-Turing
Thesis posits that both Universal Turing Machines (UTMs) and SPCs are capable
of simulating each other and, therefore, are models of the same class of
computational processes Von Neumann (1945) (section A.1). Recently, it has
been shown that augmenting an LLM with external read-and-write memory allows
it to simulate a UTM (Schuurmans, 2023). However, we do not aim to reproduce
the capabilities of the current CPU-SPC in arithmetic and logic operations but
instead explore the powerful abilities of LLM-SPCs as automatic computers.. In
more detail, the CU uses instructions from the memory to set the processor to
a specific state (e.g., load two numbers into the processor’s (arithmetic
logic unit) input registers and then execute addition and store the result in
memory. The computer is not only able to perform arithmetic and logic
operations, but it can also manipulate the memory. One unique aspect often
overlooked in this paradigm that is crucial to the reliable operation of the
processor is error-checking of the processor’s outputs. Errors can arise in a
typical processor from hardware influences such as temperature, voltage
variations, or radiation (e.g., cosmic rays) (Nicolaidis, 2010), or from miss-
specified inputs leading to overflows (e.g., divide by zero errors).
Therefore, typical processors involve output checks, the simplest being parity
bit checks, and can combine these with error-correcting mechanisms (Harris &
Harris, 2010).

####  A.1 SPC is a Universal Turing Machine

Stored-program computer (SPC) and Automata Theory. We can consider an SPC as a
specific type of Turing machine $T$. Formally, a Turing machine is defined by
the 7-tuple $T=(Q,\Sigma,\Gamma,\delta,q_{0},b,F)$, where:

  * •

$Q$ is a finite set of states.

  * •

$\Sigma$ is the finite input alphabet not containing the special blank symbol
$b$.

  * •

$\Gamma$ is the finite tape alphabet, where $b\in\Gamma$ and
$\Sigma\subseteq\Gamma$.

  * •

$\delta:Q\times\Gamma\rightarrow Q\times\Gamma\times\\{L,R\\}$ is the
transition function. Given a state and a tape symbol, it specifies the next
state, the symbol to write on the tape, and the direction in which the machine
should move its head (Left or Right).

  * •

$q_{0}\in Q$ is the start state.

  * •

$F\subseteq Q$ is the set of accepting states.

In the context of a stored-program computer, the memory holds both the
instructions (akin to the transition function $\delta$) and the data (akin to
the input sequence from $\Sigma$). The program counter, which determines the
next instruction to execute, can be represented by the machine’s current state
in $Q$. The execution of a program on an SPC is then analogous to the
computation performed by a Turing machine when transitioning from one state to
another based on the input read and the defined transition function $\delta$.

The universality of an SPC, similar to a universal Turing machine, means that
given the appropriate transition function (or set of program instructions) in
its memory, it can simulate any other Turing machine and perform any
computable task (Turing et al., 1936).

####  A.2 What is an automatic computer?

The term ‘automatic computer,’ as used in this paper, comes from the original
conception presented by Turing et al. (1936), where Turing introduced the
concept of an automatic-machine—commonly known today as a Turing machine. In
this context, ‘automatic’ refers to a system capable of executing a pre-
defined set of instructions without human intervention (Turing et al., 1936;
Von Neumann, 1945).

In the realm of LLMs, there are indeed methods whereby LLMs can autonomously
execute tasks, as reviewed by Wang et al. (2023). However, it’s crucial to
differentiate between the concepts of ‘autonomous’ and ‘automatic’. Autonomous
agents are characterized by their ability to independently devise and adapt
plans, implying a level of self-determination and initiative in executing
instructions. In contrast, our focus with L2MAC is on developing a system that
meticulously and automatically executes pre-defined instructions contained in
the prompt program $\mathcal{I}$. This execution requires no human
intervention during the process until all instructions have been successfully
executed. In this regard, L2MAC aligns more with the traditional concept of an
automatic computer. It functions as a general-purpose, instruction-following
LLM-based computer (Von Neumann, 1945) dedicated to efficiently executing the
provided instructions, thereby ensuring adherence to the completion of the
originally specified prompt program. The term ‘general-purpose’ here implies
that L2MAC can accommodate any prompt program as input and execute it without
necessitating system redesign for each new prompt-program introduced.

###  Appendix B Control Unit Operation

The Control Unit, manages the entire context of the LLM and is itself a finite
state machine. Here we expand on section 3.3, and provide pseudocode in
algorithm 1 and a data flow diagram in fig. 5.

Figure 5: Data flow of L2MAC executing one prompt instruction
$\mathcal{I}^{(k)}$ from a self-programmed prompt-program $\mathcal{I}$. The
first practical LLM-based stored-program automatic computer (L2MAC) framework.
The L2MAC consists of a file store $\mathcal{D}$, an entire memory write
component $\mathcal{W}$, an entire memory read component $\mathcal{R}$, and a
program control flow mechanism that of a Control Unit $CU$ (c.f., fig. 2) to
manage the LLM’s context window—encompassing both its inputs and outputs.
Here, the context window $C^{t}$ (dashed gray box) consists of a sequence of
messages, where each message has one of the following message types: control
$M_{c}$, user $M_{u}$, LLM response $M_{r}$ and function response $M_{f}$.
Algorithm 1 Control Unit Pseudocode for L2MAC

1:Input: Initial user input prompt $p_{\text{in}}$; file store $\mathcal{D}$;
Domain Evaluator unit $\mathcal{E}$; Domain system message $M_{s}$; Domain
bootstrap message $M_{cb}$; Context window constraint $c$; Unwind token marign
$b$

2:Output: External memory store $\mathcal{D}$.

3:$\mathcal{I}\leftarrow\emptyset,M_{rs}\leftarrow\emptyset$

4:$M_{u}\leftarrow p_{\text{in}}$

5:$M_{r}\leftarrow LLM(\\{M_{s},M_{cb},p_{\text{in}}\\})$ $\triangleright$
Self-program $\mathcal{I}$, by bootstrap instruction

6:$(\mathcal{I},\mathcal{D})\leftarrow\text{process\\_into\\_prompt\\_program}(M_{r},\mathcal{D})$

7:while $\mathcal{I}$ is not empty do

8: $C^{t}\leftarrow\\{M_{s},M_{rs}\\}$ $\triangleright$ Clear Context Window:
It always contains the system and summary message

9: $(\mathcal{I}^{(k)},\mathcal{D})\leftarrow$
pop_front_of_$\mathcal{I}$$(\mathcal{I},\mathcal{D})$ $\triangleright$ Fetch:
next instruction from external memory $\mathcal{D}$

10: $C^{t}\leftarrow C^{t}\oplus\mathcal{I}^{(k)}$

11: has_instruction_completed $\leftarrow$ False

12: while has_instruction_completed is False do

13: $M_{r}\leftarrow\mathcal{P}_{\text{LLM}}(C^{t})$

14: $\Delta_{C^{t+1}}\leftarrow\\{M_{r}\\}$

15: if ‘function_call’ in $M_{r}$ then

16: $(M_{f},\mathcal{D})\leftarrow$ execute_function($M_{r},\mathcal{D}$)

17: $\triangleright$ Invoke tool: Includes functions (tools) to read/write and
evaluate the file store $\mathcal{D}$

18: $\Delta_{C^{t+1}}\leftarrow\Delta_{C^{t+1}}\oplus M_{f}$

19: if ‘step_completed’ in $M_{r}$ then

20: $M_{fe}\leftarrow\mathcal{E}(\mathcal{D})$ $\triangleright$ Run evaluator
module on file store

21: if $M_{fe}$ is $\emptyset$ then $\triangleright$ If evaluator checks pass

22: while $|C^{t}\oplus\Delta_{C^{(t+1)}}|>b$ do $\triangleright$ Summarize
instruction output to $M_{rs}$. Unwind oldest messages to make room for
summary control message $M_{cs}$ and summary response $M_{rs}$

23: $(\\_,C^{t})\leftarrow$ pop_back_of_$C^{t}(C^{t})$

24:
$M_{rs}\leftarrow\mathcal{P}_{\text{LLM}}(C^{t}\oplus\Delta_{C^{(t+1)}}\oplus
M_{cs})$

25: has_instruction_completed $\leftarrow$ True

26: $\Delta_{C^{t+1}}\leftarrow\Delta_{C^{t+1}}\oplus M_{fe}$

27: $\Delta_{C^{t+1}}\leftarrow\Delta_{C^{t+1}}\oplus M_{cc}$ $\triangleright$
Append the cycle message

28: if $|C^{t}\oplus\Delta_{C^{(t+1)}}|>c$ then $\triangleright$ Would exceed
context check

29: while $|C^{t}\oplus\Delta_{C^{(t+1)}}|>b$ do $\triangleright$ Summarize
progress to $M_{rs}$. Unwind oldest messages to make room for summary control
message $M_{cs}$ and summary response $M_{rs}$

30: $(\\_,C^{t})\leftarrow$ pop_back_of_$C^{t}(C^{t})$

31:
$M_{rs}\leftarrow\mathcal{P}_{\text{LLM}}(C^{t}\oplus\Delta_{C^{(t+1)}}\oplus
M_{cs})$

32: $C^{t+1}\leftarrow\\{M_{s},M_{rs},\mathcal{I}^{(k)}\\}$

33: else

34: $C^{t+1}\leftarrow C^{t}\oplus\Delta_{C^{t+1}}$ $\triangleright$ Append
Messages

35:return $\mathcal{D}$

###  Appendix C Code-L2MAC High Level Implementation Details

In the following we describe the high-level implementation details of
Code-L2MAC, and we provide the verbose low level implementation details, such
as the function JSON definitions in section F.1. We follow the same structure
as the L2MAC outline and focus on the specific design choices we made for each
item. For the LLM Processor, we use GPT-4-0613 OpenAI (2023), which trains
GPT-4 to receive in-context descriptions of functions (tools) and call them as
needed, where the descriptions follow a JSON format (OpenAI, 2023).

The functions we provide are the following:

  1. 1.

‘provide_detailed_sub_task_steps_for_sub_agents‘. For producing a step-by-step
plan, where each step paragraph is a detailed sub-task step for a separate
sub-agent LLM to complete.

  2. 2.

‘sub_task_step_complete‘. For the LLM to call when the user specified sub task
step has been completed.

  3. 3.

‘view_files‘. Prints out all the file contents into the response to view.

  4. 4.

‘run_python_file‘. Runs a python file and returns the output to the response
to view.

  5. 5.

‘write_files‘. Writes out multiple files that will be combined into the
existing code base.

  6. 6.

‘delete_files‘. Deletes files, where their names are specified.

Next, we discuss specific choices to develop a method based on our LLM
Automatic Computer (L2MAC) framework specifically designed for large code
generation tasks, which we call Code-L2MAC.

For the LLM Processor, we use GPT-4-0613 OpenAI (2023), which trains GPT-4 to
receive in-context descriptions of functions and call them as needed following
a JSON format (OpenAI, 2023). See section F.1 for a low-level JSON definition
of the functions that we provide to the LLM, most of which we also mention
below.

In terms of the instructions, we initialize it999Rigorously, $\mathcal{I}$ is
initialized with a set of pre-defined messages for the LLM to be effective as
part of Code-LLM (including the functions the CU provides to the LLM). with
$\mathcal{I}^{0}=\emptyset$, and the CU queries the LLM only in the first
iteration with the user-specified feature requirements (task description) and
requests the LLM to define a sequential prompt program
$\mathcal{I}=(\mathcal{I}^{(0)},\dots,\mathcal{I}^{(K)})$.

Regarding the data $\mathcal{D}$, we determine that it encompasses only the
code generated so far so that upon termination of Code-L2MAC, $\mathcal{D}$
corresponds to its output. However, we impose the code base $\mathcal{D}$ to
be partitioned into files no longer than the context window101010More
precisely, no longer than half the margin left in the context after the
initial messages are provided in any iteration in the execution. This is to
ensure that the LLM can read and rewrite any given file inside its context.,
and we name the files with a path from a root directory/where the name of
folders and files suggests its content. This choice is not only useful for a
human reader but will be crucial for our Read-and-Write implementations.

The remaining details are in the arguably richest component of the method, the
control unit.

Execution flow of the LLM. In Code-L2MAC, we can describe the execution flow
as the following iteration. For each instruction
$\mathcal{I}^{(k)}\in\mathcal{I}$, while $\mathcal{I}^{(k)}$ is not satisfied,
do the following—following the CU pseudocode algorithm 1. First, load the
fixed messages that provide in-context learning to the LLM, the description of
the current instruction $\mathcal{I}^{(k)}$, and the summary of the last
execution $M_{rs}$. We let the LLM iterate (work on completing the
instruction) while in context, and if approaching out of context, summarize
its current context and iterate.

Interfacing with tools. During execution, the LLM might request reading and
writing operations. After each write (which possibly introduces a new test), a
syntactical checker and all existing tests in $\mathcal{D}$ are run, and the
output is provided to the LLM—through $M_{fe}$. If, after receiving this
feedback, the LLM considers the task completed, it can signal it to the CU
through calling a special function ‘step_complete‘, which summarizes the
current context output into $M_{rs}$ and continues executing the next
instruction with this summary $M_{rs}$. After all $K$ instructions are
completed, the process halts (stops), and $\mathcal{D}$ is returned.

We are only left to detail the process of reading and writing. Given the
instruction $\mathcal{I}^{(k)}$, the LLM must be able to know what modules in
$\mathcal{D}$ it can call, how to call them, and where in the directory to
write new code. However, the size of $\mathcal{D}$ might exceed the context
window.

Due to the restrictions mentioned on the files in $\mathcal{D}$, the LLM can
read and write any single full file as desired and, if necessary for context
preservation, summarize this information for the next iteration. However, the
decision regarding which files are read can be heuristically based on the
semantic information provided by the path and name of the file, which encodes
its role in $\mathcal{D}$.

Specifically, we enable the read component $\mathcal{R}$ of Code-L2MAC by
implementing the two functions. list_files(), which lists the file paths in
breadth-first search order. This could be refined to only list a subset of
files within a subdirectory, but for simplicity, in our implementation, we
automatically list all file paths in $\mathcal{D}$ for the LLM as contexts to
enable it to be aware of existing code and help it determine where to include
newly generated files. And view_files(files), which takes a list of file paths
and returns strings with their content—appending this to the context window.

We also provide the LLM at all times with a system message $M_{s}$ to inform
it that it is to complete a coding task, that it must act without human input,
and a few details about the coding environment that exists within—for example,
that it can use the python test framework Pytest, and can only mock in-memory
databases as none are installed in the local environment. Although this could
be resolved by installing and providing a clean, fresh version for most common
database providers, we leave this extension as a future work to explore.

We also provide the LLM with a pre-prompt message that it uses with the user-
specified requirements, to construct the initial plan, we also detail this and
the system message in section F.1.

###  Appendix D Extended Related Work

####  D.1 Vanilla LLMs

The usage of only a single LLM without a memory augmentation approach is
limited to only producing an output that can be maximally as long as the
underlying LLM’s context window constraint $c$. Although not directly
applicable, they are still related since the main focus of all coding tasks to
date in the literature focuses on using an LLM to solve a code generation task
within the context window constraint $c$. Notable examples include Codex (Chen
et al., 2021), GPT4 (OpenAI, 2023), GPT-Engineer (Osika, 2023) and Code LLama
(Rozière et al., 2023).

Vanilla LLMs with longer context windows. One might try to directly extend the
context window. However, such an approach scales quadratically in
computational complexity (Vaswani et al., 2017), an impracticality worsened by
the observation that LLMs with long context windows attend information from
the middle of the window poorly, substantially decreasing their task
performance as the length increases (Liu et al., 2023). Another naive approach
would be to fine-tune the LLM in the environment at hand so that it implicitly
memorizes it in its weights, but this should be done recurrently as the state
evolves, which is also too computationally expensive to be practical (Brown et
al., 2020).

####  D.2 Transformers for long inputs

There are architectural approaches to directly allow LLMs to ingest larger
windows. Tay et al. (2022) offers a comprehensive review on this topic of
“efficiency-flavored” transformers.

Child et al. (2019); Beltagy et al. (2020); Zaheer et al. (2021) present
sparse attention mechanisms that scale subquadratically with the length of the
sequence, Guo et al. (2022); Phang et al. (2022) draw on local/global
attention mechanisms to scale to longer inputs, Wang et al. (2020) approximate
the attention mechanism with a low-rank matrix to achieve linear complexity,
Choromanski et al. (2022) provide an unbiased estimator of the attention that
converges uniformly, Peng et al. (2021) use random features to approximate
soft-max attention with a decreased computational burden. Although this list
is not exhaustive, the precise impact of these optimizations on the
performance of LLM is not yet fully understood, and the adoption of these
approaches in practice is not widespread.

In Press et al. (2022), the authors discuss biasing attention scores with a
penalty proportional to their distance instead of using positional embeddings,
which allows them to extrapolate to longer sequences in inference time
effectively. Consequently, they achieve significantly more efficient training.
However, this does not address the challenges of long context windows at
inference time.

####  D.3 Memory augmented LLMs

#####  D.3.1 LLMs with built-in memory

These are works that expose the LLM to memory at training time. Yogatama et
al. (2021) extend the usual attention architecture in two ways. First, they
extend the context window without much burden at training time by omitting the
backward step for distant tokens. Second, they update the next token
probability distribution by incorporating information about the next token for
historical data for the nearest neighbors in latent space. Borgeaud et al.
(2022) essentially incorporates for each training example the k-NN (based on
an embedding fixed through training) from an external corpus. Zhong et al.
(2022b) propose a boost to the next token probability distribution based on
the similarity of the current embedding to the previous embeddings where this
token appeared. These enable the LLM to be trained with this memory component
but can essentially be thought of in the same spirit as embedding NN lookup
memory. However, none of these methods enables the memory to be updated.

Finally, (Bulatov et al., 2022) embeds into a sequence of tokens memory for
the next inference. This approach, however, has a low-interpretable, non-
symbolic, and limited memory, thereby not fully addressing arbitrarily long
tasks.

#####  D.3.2 Inference-time memory-augmented LLMs

The plainness of the limitations imposed by a limited context window has
motivated several efforts to overcome it, which has inevitably led to the
concept of memory. However, most of such works focus on long conversational /
text summarization tasks (Liang et al., 2023; Modarressi et al., 2023; Zhong
et al., 2022a; Cheng et al., 2023), or mathematical/database reasoning (Hu et
al., 2023). The methods from the first group, due to the domain, focus
exclusively on the read component of memory. The same happens with (Wu et al.,
2022), which explores the $k$-NN lookup to retrieve memory for next-token
predictions and observes improvements in perplexity for multiple tasks,
including coding. However, such read-only implementations are more sensitive
to the erratic fallibility and the “stochastic” nature of LLMs to break code
and cannot interact with memory in any other way. An exception to this is
Modarressi et al., 2023, but its memory (and thus update capabilities) is
composed of tuples of the form (Subject 1, Subject 2, Relationship), for which
there is no apparent application to coding tasks. Similarly, mathematical /
database reasoning methods such as (Hu et al., 2023) reduce memory to a
dictionary of values or a structured database, which again are not applicable
to different settings (e.g., coding).

#####  D.3.3 Autnomous Agent LLMs with memory

These works formulate the LLM as an agent in a reinforcement learning
environment, where it observes a state and then takes an action, often calling
a particular tool with an argument and interacting with the environment until
the task is solved (Wang et al., 2023). Unique to these works is they act
fully autonomously, where they are often given a few high-level goals and
construct their own plans, which are continuously updated to have self-guided
operation without external input, to complete their goals or run continuously
(Richards, 2023; Shrestha & Watkins, 2023; Nakajima, 2023). Regarding code
generation tasks, this implies that these agents can re-program and re-
formulate their step plan at run-time; however, this can often lead to the
agents going off-topic instead of completing the specified given task and
getting stuck in infinite loops (Wang et al., 2023; Sato et al., 2023).
However, in L2MAC we specify that it is automatic rather than fully autonomous
so that the specified user input commands can be performed without manual
intervention whilst achieving the input specified given task by the user.
Furthermore, of the existing Autonomous Agent LLMs with memory, the only
directly applicable method capable of writing, reading, and executing code of
files is AutoGPT (Richards, 2023). This overcomes the context window
constraint to complete long-running tasks iteratively lossly summarizing the
previous actions completed after a given number of turns and only keeping the
running summary in the context window. Prevalent with AutoGPT and others is
that they contain a first step of taking the user-specified task, and lossly
summarizing it into a name, role, and five one-sentence goals for the agent to
complete; this goal message also is always in the agent’s context window. At
each dialog step, the LLM is prompted with a ReACT (Yao et al., 2022) message
template to reason, plan, and act by selecting the next tool to call until the
goals have been achieved, then stops. Overall, these methods, such as AutoGPT
have two key limitations: (1) they lossily compress the initial detailed user-
specified task into a six-sentence description (a sentence role and five goal
sentences), and (2) they lossily compress the previous action history, which
for code generation tasks equates to forgetting which files were created and
their use, which is further compounded by re-planning with a separate new plan
at dialog step. Whereas our proposed LLM automatic computer (L2MAC) can (1)
create a detailed plan initially and use that single plan throughout to align
to complete the original user-specified task, and (2) L2MAC is aware of the
existing files generated, which encapsulates all the previous actions up to
the current state (where the files track the current memory state), allowing
it to know and integrate new code with the existing files already generated.

####  D.4 Tool augmented LLMs

Schick et al. (2023) teach LLMs to use external tools through API calls, for
example, to use a calculator, a search engine, or a translation system to
cover LLM weaknesses or reduce computation cost. The methods by which the LLM
chooses when to read from memory (instead of automatically receiving the
information obtained from memory) can basically be regarded as providing a new
tool to the LLM (e.g., Hu et al. (2023); Modarressi et al. (2023)). This is
the case for the L2MAC implementation of reading and writing, but not all the
functionalities of the control unit can be seen under this lens, as is the
case with the monitoring of the context window or the automatic evaluation of
the file store, unless we stretch it excessively. In any case, as argued in
Modarressi et al. (2023), this similarity with Schick et al. (2023) does not
undermine the relevance of the development of new and influential tools.

####  D.5 Multi-step reasoning & Reflecting LLMs

Reflecting LLMs. These methods can improve the task performance of existing
single LLMs by having access to an evaluator and using the LLM to reflect on
the actions taken (current trajectory part) to derive actionable verbal
feedback that is persisted in an append-only memory (Shinn et al., 2023;
Madaan et al., 2023). These verbal reflection learnings are a form of in-
context learning (Dong et al., 2022) that are then used to improve the task or
sub-task performance when the task or sub-task is restarted anew. This simple,
and practical reflection idea, when having access to a possible external
validator, such as self-generated unit tests for code generation, have
demonstrated improving single LLMs for small code snippet generation tasks
performance to be state-of-the-art (Shinn et al., 2023). Although impressive,
these are still limited by the fixed context window constraint $c$ and can
only output code for tasks that can fit within this constraint, whereas our
proposed L2MAC also integrates this simple reflection idea to be competitive,
using an external evaluator of code checks and self-generated unit tests, it
can generate large code bases that are unbounded and unrestricted by the
single LLMs constraint $c$.

Multi-step reasoning. Methods that leverage a hierarchical flow of information
between LLMs can also handle information that does not fit the context length,
thanks to the distribution of information. For example, (Zhang et al., 2022;
Wu et al., 2021) iteratively and hierarchically perform the summarization of
long documents. We refer to (Dohan et al., 2022) for a unification of such
methods under a common formalism. Code-L2MAC uses simple instantiations of
this family to populate $\mathcal{I}$ from the initial prompt or to summarize
the execution when cleaning the context window, but future iterations could
build on more complex cascades to improve our implementation of L2MAC.
Multistep reasoning is only a small part of L2MAC, and we envision L2MAC
enhancing multistep reasoning methods through the CU and memory (c.f. appendix
I).

####  D.6 Turing Machines, Stored program computers and Machine Learning

There are instantiations of Universal Turing Machines and Stored-Program
Computers with LLMs (Schuurmans, 2023; Giannou et al., 2023), respectively,
which are theoretically insightful. However, in both cases, their method with
a transformer at the core only aims to simulate a UTM or SPC, thereby not
achieving a method functionally superior to either a UTM or SPC (and none of
them new), which can be implemented much more cheaply. In contrast, we
capitalize on the SPC framework to boost the LLM’s unique capabilities as a
stochastic NLP to automatically solve potentially long tasks from a single
user prompt, which is altogether a different focus.

Although (Graves et al., 2014) does not use LLMs, and the focus is also
completely different to ours (since it aims to reproduce algorithms by
supervised learning), it is worth mentioning that they extend a Recursive
Neural Network with memory to achieve a Turing Machine or von Neumann
architecture capable of inferring simple algorithms when trained to reproduce
them.

###  Appendix E Benchmark Task Environment Details

Given the absence of pre-existing benchmark task environments suitable for
evaluating long code generation tasks, we have introduced a new benchmark
tailored for standard system design tasks, which are typically assigned to
humans. Traditional system design tasks often require high-level
conceptualization, such as devising the architecture, modules, components,
interfaces, and data structures needed for an online application to meet
specific user feature requirements (Xu & Lam, 2020). Unlike these conventional
tasks that predominantly focus on high-level system outlines, our benchmark
mandates the implementation of fully functional code. This code aims to
instantiate a minimal system satisfying the user-specified requirements in a
practical manner.

For meaningful and realistic evaluation, our benchmark encompasses three
standard system design code base generation tasks. The prompt questions for
these tasks are derived from actual system design interview questions,
providing a realistic basis for assessment (Xu & Lam, 2020; Martin, 2023). The
tasks included in the benchmark are as follows:

  1. 1.

URL Shortener App: This task necessitates the implementation of a
comprehensive online URL shortening service, a utility that enables users to
submit lengthy URLs and subsequently receive a shortened variant for
simplified sharing. The user-specified feature requirements for this task are
extensive. The envisaged system should facilitate URL shortening services,
allowing users to input, validate, and, if desired, customize their URLs. The
shortened URLs should redirect users to the original addresses. Users should
have access to analytics, revealing data such as click counts, timestamps, and
geographical locations linked to each URL. The platform should also support
user account creation and management, enabling users to edit, delete, or view
analytics related to their URLs. An administrative dashboard for monitoring
user activity, user accounts, and overall system performance should be in
place. Furthermore, users should have the ability to set expiration parameters
for their shortened URLs.

  2. 2.

Online Microblogging App: The task entails the implementation of a web-based
microblogging service where registered users can post short textual messages,
follow or unfollow others, and interact with the posts. Each user can create,
edit, and manage their profile with options to set it as private or public.
Users can post text messages limited to 280 characters, optionally include
images in the posts, and have the ability to delete their posts. The platform
will support interactions with posts, such as liking, retweeting, and
replying, with a nested structure for the comments. Users can also search and
filter posts or other users using keywords, hashtags, mentions, or view
trending topics. Furthermore, users can follow and unfollow others, with a
timeline view displaying posts from the users they follow and receiving
notifications for new followers, likes, retweets, replies, and mentions. The
service will also facilitate private messaging between users, with options to
block or unblock users. Finally, the platform will offer user recommendations
for following based on interests, activity, and mutual followers and showcase
trending topics, which can be viewed globally or sorted by location.

  3. 3.

Online Chat App: This task involves implementing a real-time online chat
application. The GCS must support user registration and authentication
functionalities, including email sign-up and forgotten password recovery.
Users should be able to set profile pictures and status messages, with privacy
settings to control visibility. The application should provide options for
contact management (block/unblock contacts and group management), real-time
text messaging with read receipts, end-to-end encryption, image sharing, and
support for emojis, GIFs, and stickers. Group chat functionality should allow
the creation of group chats with assigned names and pictures, participant
management, and admin role assignments and permissions. Users should be able
to post image statuses that are visible for a limited duration, with the
ability to control viewer access. The service should be accessible as a web
application and support offline messaging, with queued messages sent upon
connectivity restoration and visible online/offline user statuses.

Each method receives the same user-specified feature requirements, which are
given below for each environment task, and produces a code base output, which
we then evaluate using our evaluation methodology, which is fully detailed in
appendix G. The following user-specified input prompts for each task are:

URL Shortener App, user-specified feature requirements input prompt:

⬇

### **Online URL Shortening Service**

**Overview**:

A service that allows users to submit long URLs and then receive a shortened
version of that URL for ease of sharing.

**Functional Requirements to implement**:

1. **URL Shortening**:

- [ ] 1.1. Users can input a URL to be shortened.

- [ ] 1.2. The system validates that the URL is active and legitimate.

- [ ] 1.3. The system generates a unique shortened URL.

- [ ] 1.4. Users can choose custom short links (subject to availability).

2. **Redirection**:

- [ ] 2.1. Accessing the shortened URL redirects to the original URL.

3. **Analytics**:

- [ ] 3.1. Users can view statistics about their shortened URLs.

- [ ] 3.2. View number of clicks.

- [ ] 3.3. View date/time of each click.

- [ ] 3.4. View geographical location of the clicker.

4. **User Accounts**:

- [ ] 4.1. Users can create accounts.

- [ ] 4.2. Account holders can view all their shortened URLs.

- [ ] 4.3. Account holders can edit or delete their shortened URLs.

- [ ] 4.4. Account holders can view analytics for all their shortened URLs.

5. **Admin Dashboard**:

- [ ] 5.1. Administrators can view all shortened URLs.

- [ ] 5.2. Administrators can delete any URL or user account.

- [ ] 5.3. Administrators can monitor system performance and analytics.

6. **Expiration**:

- [ ] 6.1. Users can set an expiration date/time for the shortened URL.

Online Microblogging App, user-specified feature requirements input prompt:

⬇

**Online Microblogging Service (OMS) - Description & Requirements**

*Description:*

A web-based platform where registered users can post short text-based
messages, view messages from others, follow/unfollow other users, and interact
with posts. The platform provides features for both individual users and
administrative management.

**Functional Requirements to implement**:

1. **User Management:**

1. **Registration & Authentication:**

- [ ] Allow users to register using email, username, and password.

- [ ] Option to reset forgotten passwords.

- [ ] Secure authentication using JWT or similar protocols.

2. **Profile Management:**

- [ ] Users can edit their profile information: profile picture, bio, website link, and location.

- [ ] Option to make profile private or public.

2. **Posting & Content Management:**

1. **Creating Posts (Tweets):**

- [ ] Allow users to create text-based posts with a limit of 280 characters.

- [ ] Option to include images in posts.

- [ ] Users can delete their own posts.

2. **Interacting with Posts:**

- [ ] Users can like, retweet, and reply to posts.

- [ ] Nested comment structure for post replies.

3. **Content Filtering & Search:**

- [ ] Users can search for specific posts or users using keywords.

- [ ] Filter option based on hashtags, user mentions, or trending topics.

3. **Social Interaction:**

1. **Following & Followers:**

- [ ] Users can follow/unfollow other users.

- [ ] A timeline view displays posts from followed users.

- [ ] Users receive notifications for new followers.

2. **Direct Messaging:**

- [ ] Private conversation threads between users.

- [ ] Option to block/unblock users from messaging.

3. **Notifications:**

- [ ] Users are notified of likes, retweets, replies, and mentions.

4. **Trending & Discovery:**

1. **Trending Topics:**

- [ ] System identifies and displays trending hashtags or topics based on volume and velocity of mentions.

- [ ] Trending topics can be sorted based on location or globally.

2. **User Recommendations:**

- [ ] Recommend users to follow based on interests, activity, and mutual followers.

Online Chat App, user-specified feature requirements input prompt:

⬇

**Global Chat Service (GCS)**

**Overview**:

A real-time online chat application allowing users to send text messages,
images, and create group chats.

**Functional Requirements to implement**:

User Registration and Authentication:

- [ ] 1.1. Sign up using email.

- [ ] 1.2. Forgotten password recovery.

User Profile:

- [ ] 2.1. Allow users to set profile pictures and status messages.

- [ ] 2.2. Privacy settings for who can see user details or last seen status.

Contact Management:

- [ ] 3.1. Block/unblock contacts.

- [ ] 3.2. Create, edit, and manage groups.

Messaging:

- [ ] 4.1. Send and receive real-time text messages.

- [ ] 4.2. Message read receipts (blue ticks or equivalent).

- [ ] 4.3. End-to-end encryption for security.

- [ ] 4.4. Image sharing.

- [ ] 4.5. Emojis, GIFs, and stickers support.

Group Chats:

- [ ] 5.1. Create group chats with a name and picture.

- [ ] 5.2. Add or remove participants.

- [ ] 5.3. Admin roles and permissions.

Status/Story Feature:

- [ ] 6.1. Allow users to post image statuses visible for a limited time.

- [ ] 6.2. Control who can see the status.

Web Application:

- [ ] 7.1. Web-based version accessible from browsers.

Connectivity and Offline Mode:

- [ ] 8.1. Message queuing for when the user is offline; messages are sent once connectivity is restored.

- [ ] 8.2. Display online/offline status.

###  Appendix F Benchmark Method Implementation Details

In the following, we detail all implementation details of our benchmark
methods, including that of the full low-level implementation details of
Code-L2MAC in section F.1.

AutoGPT. We chose to compare against the most competitive and popular
autonomous agent LLM with memory method, that of AutoGPT (Richards, 2023).
This uses GPT4 as the underlying LLM. Like other autonomous agents, the first
step of AutoGPT is to summarize the user-specified task into a name, role, and
five one-sentence goals for the agent to complete; this summary is kept in
context throughout execution. At each step, until the goals have been
achieved, the underlying LLM receives a ReACT (Yao et al., 2022) message
template to reason, plan, and act by selecting the next tool to call.
Specifically, we used the latest stable version of AutoGPT, 0.4.7, enabled
local tool execution, and disabled searching the web for answers to ensure a
fair comparison. It is interesting to note that AutoGPT also has tool
functionality and has tools to read, write, and list files in a local file
store—making it the most competitive and applicable baseline to compare
against. Although other autonomous agent LLM methods exist, they do not
possess the ability to read or write to an external file store in the same
manner as AutoGPT. Importantly, AutoGPT, when running, would sometimes have
runs where it would fail to complete the task, i.e., fail to output any code
or get stuck in an infinite loop. When such failures occurred, we classified
these runs failures and excluded them from the results. This method defaults
to use the LLM with a temperature of 0.

GPT4. We also chose to compare with the single GPT4 LLM (GPT4) (OpenAI, 2023),
which we adapt to make it competitive by providing it with the same tools that
Code–L2MAC uses, forming an ablation of just using an LLM processor without
the control unit. Specifically, we provide it with exactly the same messages
and experimental setup as Code-L2MAC, including the same system message and
prompt format message; however, it is limited to only respond with one long
single response that can fill up the entire context window $C^{t}$.

Code-L2MAC. Our proposed method uses the message and function definitions
defined in section F.1. Using these, it then follows the pseudocode for the
control unit, as outlined in algorithm 1, and generates a prompt program of
instructions $\mathcal{I}$ and iterates each dialog turn of the control unit
control flow loop until all instructions are complete. There are a few other
minor implementation details, which we also detail here. We impose a maximum
number of times an instruction can be re-tried $r_{\text{Max}}$, with a new
context window when, during the execution of that instruction, it attempts to
exceed the context window, forcing the context window to restart the
instruction with the summary of the current progress made—we empirically set
$r_{\text{Max}}=30$. When the current number of retries exceeds
$r_{\text{Max}}$, we class this run as a failure and exclude its results.
Importantly, at such a failure, the method could ideally either await human
input for correction or continue with an errored state. We used the LLM of
GPT4-0613, and when using it throughout, set the temperature to 0.01.
Additionally, another implementation detail is that when the CU detects that
it is stuck in a loop repeating the same two messages over again by comparing
the most recent two messages in the context window, it increases the
temperature of the LLM by 0.1 and continues until the temperature caps at 1.0,
and then after it exits the loop reducing the temperature back to 0.01. This
is to have a form of simulated annealing of introducing randomness to escape
the local minima. In the following, section F.1, we detail special message
templates exactly.

####  F.1 Code-L2MAC Low Level Implementation Details

We follow the same setup as outlined in appendix C, and in the following, we
provide exact low-level implementation details. We use GPT-4-0613, which has
fine-tuned support for function calls, and use the function definition file of
the following.

Function definitions:

⬇

{

"name": "provide_detailed_sub_task_steps_for_sub_agents",

"description": "For producing a step-by-step plan, where each step paragraph
is a detailed sub-task step for a separate sub-agent (large language model
agent) to complete. Within each detailed step paragraph, always include a last
sentence to create and run tests when implementing or writing code in that
same step.",

"parameters": {

"type": "object",

"properties": {

"steps": {

"type": "array",

"description": "List of strings, where each string is a separate step sub-task
paragraph for a separate sub-agent to complete. Within each detailed step
paragraph, always include a last sentence to create and run tests when
implementing or writing code in that same step.",

"items": {

"type": "string",

}

},

},

"required": ["steps"],

},

},

{

"name": "sub_task_step_complete",

"description": "Call this function when the user specified sub task step has
been completed.",

"parameters": {

"type": "object",

"properties": {},

},

},

{

"name": "view_files",

"description": "Print out the file contents into the response to view.",

"parameters": {

"type": "object",

"properties": {

"files": {

"type": "array",

"description": "list of the files to view",

"items": {

"type": "string" # assuming each file is represented as a string

}

},

},

"required": ["files"],

},

},

{

"name": "run_python_file",

"description": "Run python file and return the output to the response to view.
That is with ’python3 file_name_to_run’.",

"parameters": {

"type": "object",

"properties": {

"file_name_to_run": {

"type": "string",

"description": "file name to run",

},

"arguments": {

"type": "array",

"description": "optional run arguments",

"items": {

"type": "string"

}

},

},

"required": ["file_name_to_run"],

},

},

{

"name": "pytest_files",

"description": "Run pytest on the input file names and print out the results
to the response to view. If no file names are provided, pytest runs on all
files.",

"parameters": {

"type": "object",

"properties": {

"files_to_test": {

"type": "array",

"description": "file names to run pytest on",

"items": {

"type": "string"

}

},

},

},

},

{

"name": "write_files",

"description": "Write out multiple files and it will be combined into the
existing code base. Always output the whole file. You always indent code with
tabs.",

"parameters": {

"type": "object",

"properties": {

"files_and_contents": {

"type": "array",

"description": ’list of files and their contents.’,

"items": {

"type": "object",

"properties": {

"file_path": {

"type": "string",

"description": "Path to the file"

},

"file_contents": {

"type": "string",

"description": "Contents of the file"

}

},

"required": ["file_path", "file_contents"]

}

}

},

"required": ["files_and_contents"],

},

},

{

"name": "delete_files",

"description": "Delete files. Specify the file names, and these files will be
deleted. If you specify the file name ’-1’ all files in the folder will be
deleted.",

"parameters": {

"type": "object",

"properties": {

"files": {

"type": "array",

"description": "list of the files to delete. If you provide a file name of
’-1’ all files in the folder will be deleted.",

"items": {

"type": "string"

}

},

},

"required": ["files"],

},

}

With Code-L2MAC we use the following system message (OpenAI, 2023) $M_{s}$,
and include it all context windows $C^{t}$, which is standard to do so
(OpenAI, 2023).

System message $M_{s}$:

⬇

Objective: Write code for a large system design task.

Please note that the code should be fully functional. No placeholders.

Only use the functions you have been provided with.

Only use the ‘write_files‘ to output code.

You must act autonomously and you will receive no human input at any stage.
You have to return as output the complete code for completing this task, and
correctly incorporate it into the existing code base.

You always write out the whole file contents. You always indent code with
tabs.

Please always view the files before writing to them, to make sure you are
writing to the correct files.

When writing a test, make the filename start with the prefix ’test_’.

Provide the minimal code necessary to achieve the task conditioned on the
existing generated code—including changing the existing generated code.

You cannot visualize any graphical output. You exist within a Actor Model
machine, and when you list out steps, each step will be taken by a new
separate sub-ChatGPT model. When you list out a sub-task steps, you can
optionally specify the sub-task validation to check that it has been completed
successfully.

You cannot use any databases as none are setup in the local environment,
instead mock a database with an in memory dictionary to store data. No data
saved to disk will persist between steps or write operations.

If a test is failing the error could be the code, or the test is incorrect, so
feel free to overwrite and change the tests when they are incorrect, to make
all tests pass.

Use the functions provided. When calling functions only provide a RFC8259
compliant JSON request following this format without deviation.

When Code-L2MAC self-programs its instructions initially, we provide it with
the following prompt template to do so, which encapsulates the user message
$M_{u}$, as ‘user_specified_feature_requirements’.

$M_{cb}$ bootstrap instruction:

⬇

You will get instructions for code to write.

First lay out the names of the core classes, functions, methods that will be
necessary, As well as a quick comment on their purpose.

Do not comment on what every file does. Please note that the code should be
fully functional. No placeholders.

You will start with the "entrypoint" file, then go to the ones that are
imported by that file, and so on.

Please note that the code should be fully functional. No placeholders.

Follow a language and framework appropriate best practice file naming
convention.

Make sure that files contain all imports, types etc. The code should be fully
functional. Make sure that code in different files are compatible with each
other.

When writing code if you are unsure, write a plausible implementation.

Include module dependency or package manager dependency definition file.

Useful to know:

For Python, you always create an appropriate requirements.txt file.

Always add a comment briefly describing the purpose of the function
definition.

Add comments explaining very complex bits of logic.

Always follow the best practices for the requested languages for folder/file
structure and how to package the project.

You can use any package and any other packages you wish to install.

You cannot use any databases as none are setup in the local environment,
instead mock a database with an in memory dictionary to store data. No data
saved to disk will persis between steps or write operations.

When writing a test, make the filename start with the prefix ’test_’.

Python toolbelt preferences:

- pytest

- dataclasses

- flask

Objective:“‘

{user_specified_feature_requirements}

“‘

Understand the problem, by creating an extremely detailed step-by-step plan,
where each step is long (multiple sentences) and in total includes every
single feature requirement specified above, feel free to copy directly from
it. Use no more than 10 steps in the plan. Create additional tests, checks and
evaluation at each step when applicable to help make an excellent code
implementation, where all the code is fully functional. Use best software
design practices, and you can output large amounts of code at once. Please
include a last sentence to create and run tests when implementing or writing
code in that same step. You will receive no human input at any stage, so you
cannot use a human to test. Only create a detailed plan to begin with, which
includes designing and running tests to check that they all pass. Please be
sure to include all of the specified feature requirements in the following
plan.

Code-L2MAC also involves control messages of the following form.

$M_{cc}$ Control cycle message of starting the instruction:

⬇

Objective: Execute sub task step: {instruction}.\n\n Note: Condition any new
code files on the existing code files: {list_files()}. Fully implement these
features in the code, no placeholders. You can now optionally view the
existing files if you need to view them to complete the current task step. You
have a limited context window so be selective about which files you view, only
view the files you think you might need to view.\n\nSummary output of previous
step: ""{previous_instruction_output_summary}""\n\nRespond now only with a
function call of one of the following functions provided: {function_names()},
and if you want to output code only use the ‘write_files‘ function to output
code.

Here instruction is the current instruction of operation, ‘list_files()’ a
list files tool function, previous_instruction_output_summary is the summary
message $M_{rs}$, and ‘function_names()’ lists the current function names that
the LLM can request.

$M_{cc}$ Control cycle message of continuing the instruction:

⬇

Has the sub task step been completed of: “‘

{instruction}

“‘ \n\n If yes, call the function ‘sub_task_step_complete‘, otherwise reflect
and correct the full code to complete the task. Only use the functions you
have been provided with, and if you want to output code only use the
‘write_files‘ function to output code. Condition it on existing code:
{list_files()} Fully implement these features in the code, no placeholders. If
you have not viewed the files before writing to them, please view them, to
make sure you are writing to the correct files.\nRespond now only with a
function call of one of the following functions provided: {function_names()},
and if you want to output code only use the ‘write_files‘ function to output
code.

Here instruction is the current instruction of operation,
‘sub_task_step_complete’ is the function the LLM calls to indicate that it has
completed the current instruction, ‘list_files()’ a list files tool function,
and ‘function_names()’ lists the current function names that the LLM can
request.

$M_{cs}$ Control summarization message for restarting the same instruction:

⬇

Please provide a one or two sentence summary of the output of this step, which
is useful for the next step. Your response will be used when starting the next
step without any of the previous messages.

$M_{cs}$ Control summarization message, for summarizing the instruction
output—which is used when continuing the next instruction.

⬇

You have exhausted your context window. Reflect on your progress. Provide a
short concise response, of two sentences maximum, this will be used to restart
this step from the beginning without the previous messages.

###  Appendix G Evaluation Metrics

There are no automated tools to validate the output of system design tasks, so
we propose evaluation metrics to compare the output of different methods.
Large-scale code generation is unique in that the generated code can satisfy
the high-level user feature requirements specified in the input through
various possible implementation approaches.

To quantify the degree to which user-specified features in the initial prompt
are effectively implemented in the generated code, we introduce a performance
metric named Features %. This metric numerically represents the proportion of
input features that are fully and functionally implemented in the output code
base. The Features % is obtained by using a separate GPT-4 API call, which
iteratively examines the entire generated code to verify the functional
implementation of all input features, counting the number of fully implemented
features. We quote this as a percentage of the features implemented over the
total features specified by the user. Specifically, we implement this metric
by first collecting all the generated code files from a method’s generated
output and outputting all the code files as named strings of the format file
name, followed by the file contents, and pass it into the prompt template
below for the GPT-4 API to count the number of fully implemented features. We
then use a regex parser to extract the final number from the LLM response
message. We now provide this prompt template and then provide an example of it
in action.

Features % prompt template

⬇

Objective: Based on the numbered features given, you are to evaluate the
following code and return a numeric value for how many (a count) of those
numbered features are implemented in the provided code. Give the numeric
answer as "FEATURES_FUNCTIONAL=num_features_functional" in the final line.

Numbered Features Specified:“‘

{user_specified_feature_requirements}

“‘

Code to evaluate for the amount of features fully implemented:"""

{code_files}

"""

Here ‘user_specified_feature_requirements’ is the user-specified task
description, which are provided in full in appendix E, and ‘code_files’ is the
entire contents of the code base printed out with filenames and the contents.

A worked example, can be seen in the following, for example Code-L2MAC for one
of the runs for the environment task URL Shortener App, with the complete
user-specified feature requirements is given, including the GPT4 call’s
response.

GPT4 API call.

⬇

To evaluate the provided code based on the requirements for the "Online URL
Shortening Service", you can use the following numbered checklist. For each
feature present in the code, you can increment a numeric value:

“‘

**Evaluation Checklist for Online URL Shortening Service**:

1. **URL Shortening**:

- [ ] 1.1. Users can input a URL to be shortened.

- [ ] 1.2. The system validates that the URL is active and legitimate.

- [ ] 1.3. The system generates a unique shortened URL.

- [ ] 1.4. Users can choose custom short links (subject to availability).

2. **Redirection**:

- [ ] 2.1. Accessing the shortened URL redirects to the original URL.

3. **Analytics**:

- [ ] 3.1. Users can view statistics about their shortened URLs.

- [ ] 3.2. View number of clicks.

- [ ] 3.3. View date/time of each click.

- [ ] 3.4. View geographical location of the clicker.

4. **User Accounts**:

- [ ] 4.1. Users can create accounts.

- [ ] 4.2. Account holders can view all their shortened URLs.

- [ ] 4.3. Account holders can edit or delete their shortened URLs.

- [ ] 4.4. Account holders can view analytics for all their shortened URLs.

5. **Admin Dashboard**:

- [ ] 5.1. Administrators can view all shortened URLs.

- [ ] 5.2. Administrators can delete any URL or user account.

- [ ] 5.3. Administrators can monitor system performance and analytics.

6. **Expiration**:

- [ ] 6.1. Users can set an expiration date/time for the shortened URL.

**Total Implemented Features**: [Count the checked boxes to get the numeric
value]

“‘

You can go through the provided code and check off each item that has been
implemented. At the end, count the checked boxes to get the numeric value for
the number of features implemented.

“‘

Code to evaluate for the amount of features fully implemented:"""

test_analytics.py

“‘python

import analytics

import datetime

def test_track_click():

"""Test that click events are tracked correctly."""

analytics.track_click(’abc123’, ’8.8.8.8’)

data = analytics.get_analytics(’abc123’)

assert len(data) == 1

assert isinstance(data[0][’time’], datetime.datetime)

assert data[0][’ip_address’] == ’8.8.8.8’

def test_get_analytics():

"""Test that analytics data is retrieved correctly."""

data = analytics.get_analytics(’abc123’)

assert len(data) == 1

assert isinstance(data[0][’time’], datetime.datetime)

assert data[0][’ip_address’] == ’8.8.8.8’

“‘

analytics.py

“‘python

import datetime

# Mock database

analytics_data = {}

def track_click(short_url, ip_address):

"""Track a click event."""

if short_url not in analytics_data:

analytics_data[short_url] = []

# Record the click event

click_event = {

’time’: datetime.datetime.now(),

’ip_address’: ip_address

}

analytics_data[short_url].append(click_event)

def get_analytics(short_url):

"""Retrieve analytics data for a short URL."""

return analytics_data.get(short_url, [])

def get_system_performance():

"""Retrieve system performance data.

Returns:

dict: A dictionary containing system performance data.

"""

# For simplicity, we’ll just return the number of URLs and the number of click
events.

return {

’num_urls’: len(analytics_data),

’num_clicks’: sum(len(events) for events in analytics_data.values())

}

“‘

test_user_accounts.py

“‘python

import pytest

from user_accounts import UserAccount

def test_create_account():

user_account = UserAccount()

assert user_account.create_account(’test’, ’password’) == ’Account created
successfully.’

assert user_account.create_account(’test’, ’password’) == ’Username already
exists.’

def test_view_urls():

user_account = UserAccount()

user_account.create_account(’test’, ’password’)

assert user_account.view_urls(’test’) == []

assert user_account.view_urls(’nonexistent’) == ’Username does not exist.’

def test_add_url():

user_account = UserAccount()

user_account.create_account(’test’, ’password’)

assert user_account.add_url(’test’, ’http://example.com’) == ’URL added
successfully.’

assert user_account.add_url(’nonexistent’, ’http://example.com’) == ’Username
does not exist.’

def test_delete_url():

user_account = UserAccount()

user_account.create_account(’test’, ’password’)

user_account.add_url(’test’, ’http://example.com’)

assert user_account.delete_url(’test’, ’http://example.com’) == ’URL removed
successfully.’

assert user_account.delete_url(’test’, ’http://nonexistent.com’) == ’URL does
not exist.’

assert user_account.delete_url(’nonexistent’, ’http://example.com’) ==
’Username does not exist.’

“‘

url_shortener.py

“‘python

import hashlib

import requests

from datetime import datetime, timedelta

# Mock database to store the mapping between the shortened URLs and the
original URLs.

url_mapping = {}

def generate_short_url(url, expiration_minutes=15):

"""Generate a unique shortened URL.

Args:

url (str): The original URL.

expiration_minutes (int): The number of minutes until the URL expires.

Returns:

str: The shortened URL.

"""

hash_object = hashlib.md5(url.encode())

short_url = hash_object.hexdigest()[:10]

# Store the mapping between the shortened URL and the original URL.

url_mapping[short_url] = {

’url’: url,

’expiration’: datetime.now() + timedelta(minutes=expiration_minutes)

}

return short_url

def validate_url(url):

"""Validate a URL.

Args:

url (str): The URL to validate.

Returns:

bool: True if the URL is valid, False otherwise.

"""

try:

response = requests.get(url)

return response.status_code == 200

except requests.exceptions.RequestException:

return False

def get_original_url(short_url):

"""Get the original URL associated with the shortened URL.

Args:

short_url (str): The shortened URL.

Returns:

str: The original URL, or None if the shortened URL does not exist or has
expired.

"""

url_data = url_mapping.get(short_url)

if url_data and url_data[’expiration’] > datetime.now():

return url_data[’url’]

def delete_url(short_url):

"""Delete a shortened URL.

Args:

short_url (str): The shortened URL.

"""

if short_url in url_mapping:

del url_mapping[short_url]

def get_all_urls():

"""Get all shortened URLs.

Returns:

list: A list of all shortened URLs.

"""

return list(url_mapping.keys())

“‘

test_url_shortener.py

“‘python

import url_shortener

from datetime import datetime, timedelta

import time

def test_generate_short_url():

"""Test the generate_short_url function."""

url = ’https://www.example.com’

short_url = url_shortener.generate_short_url(url)

assert len(short_url) == 10

assert isinstance(short_url, str)

def test_validate_url():

"""Test the validate_url function."""

valid_url = ’https://www.example.com’

invalid_url = ’https://www.invalidurl.com’

assert url_shortener.validate_url(valid_url) is True

assert url_shortener.validate_url(invalid_url) is False

def test_url_expiration():

"""Test that URLs expire correctly."""

url = ’https://www.example.com’

short_url = url_shortener.generate_short_url(url, expiration_minutes=0)

assert url_shortener.get_original_url(short_url) is None

short_url = url_shortener.generate_short_url(url, expiration_minutes=1)

assert url_shortener.get_original_url(short_url) == url

# Wait for the URL to expire

time.sleep(61)

assert url_shortener.get_original_url(short_url) is None

“‘

user_accounts.py

“‘python

class UserAccount:

def __init__(self):

self.accounts = {}

def create_account(self, username, password):

if username in self.accounts:

return ’Username already exists.’

self.accounts[username] = {’password’: password, ’urls’: []}

return ’Account created successfully.’

def view_urls(self, username):

if username not in self.accounts:

return ’Username does not exist.’

return self.accounts[username][’urls’]

def add_url(self, username, url):

if username not in self.accounts:

return ’Username does not exist.’

self.accounts[username][’urls’].append(url)

return ’URL added successfully.’

def delete_url(self, username, url):

if username not in self.accounts:

return ’Username does not exist.’

if url not in self.accounts[username][’urls’]:

return ’URL does not exist.’

self.accounts[username][’urls’].remove(url)

return ’URL removed successfully.’

def delete_account(self, username):

if username in self.accounts:

del self.accounts[username]

return ’Account deleted successfully.’

else:

return ’Username does not exist.’

def get_all_users(self):

return list(self.accounts.keys())

“‘

requirements.txt

“‘text

flask

pytest

maxminddb-geolite2

“‘

test_app.py

“‘python

import pytest

from app import app

@pytest.fixture

def client():

app.config[’TESTING’] = True

with app.test_client() as client:

yield client

def test_home_page(client):

response = client.get(’/’)

assert response.status_code == 200

assert response.data == b’Hello, World!’

def test_redirect_to_original_url(client):

response = client.get(’/abc123’)

assert response.status_code == 404

def test_shorten_url(client):

response = client.post(’/shorten’, data={’url’: ’https://www.google.com’})

assert response.status_code == 200

assert ’short_url’ in response.get_json()

def test_view_analytics(client):

response = client.get(’/analytics/abc123’)

assert response.status_code == 200

assert ’analytics’ in response.get_json()

def test_manage_account(client):

response = client.post(’/account’, data={’action’: ’create’, ’username’:
’testuser’, ’password’: ’testpass’})

assert response.status_code == 200

assert response.get_json()[’message’] == ’Account created successfully.’

response = client.post(’/account’, data={’action’: ’view_urls’, ’username’:
’testuser’})

assert response.status_code == 200

assert ’urls’ in response.get_json()

response = client.post(’/account’, data={’action’: ’delete’, ’username’:
’testuser’})

assert response.status_code == 200

assert response.get_json()[’message’] == ’Account deleted successfully.’

def test_admin_dashboard(client):

response = client.get(’/admin’)

assert response.status_code == 200

assert ’urls’ in response.get_json()

assert ’users’ in response.get_json()

assert ’performance’ in response.get_json()

def test_delete_url(client):

client.post(’/admin’, data={’action’: ’delete_url’, ’short_url’: ’abc123’})

response = client.get(’/abc123’)

assert response.status_code == 404

def test_delete_user(client):

client.post(’/admin’, data={’action’: ’delete_user’, ’username’: ’testuser’})

response = client.get(’/admin’)

assert ’testuser’ not in response.get_json()[’users’]

“‘

app.py

“‘python

from flask import Flask, redirect, url_for, request

from url_shortener import get_original_url, delete_url, get_all_urls,
generate_short_url, validate_url

from user_accounts import UserAccount

from analytics import get_system_performance, get_analytics, track_click

app = Flask(__name__)

user_account = UserAccount()

@app.route(’/’)

def home():

return ’Hello, World!’

@app.route(’/<short_url>’)

def redirect_to_original_url(short_url):

original_url = get_original_url(short_url)

if original_url is None:

return ’URL not found’, 404

else:

track_click(short_url, request.remote_addr)

return redirect(original_url)

@app.route(’/shorten’, methods=[’POST’])

def shorten_url():

url = request.form.get(’url’)

if not validate_url(url):

return ’Invalid URL’, 400

short_url = generate_short_url(url)

username = request.form.get(’username’)

if username:

user_account.add_url(username, short_url)

return {’short_url’: short_url}

@app.route(’/analytics/<short_url>’)

def view_analytics(short_url):

return {’analytics’: get_analytics(short_url)}

@app.route(’/account’, methods=[’POST’])

def manage_account():

action = request.form.get(’action’)

username = request.form.get(’username’)

if action == ’create’:

password = request.form.get(’password’)

return {’message’: user_account.create_account(username, password)}

elif action == ’view_urls’:

return {’urls’: user_account.view_urls(username)}

elif action == ’delete’:

return {’message’: user_account.delete_account(username)}

@app.route(’/admin’, methods=[’GET’, ’POST’])

def admin_dashboard():

if request.method == ’POST’:

action = request.form.get(’action’)

if action == ’delete_url’:

short_url = request.form.get(’short_url’)

delete_url(short_url)

elif action == ’delete_user’:

username = request.form.get(’username’)

user_account.delete_account(username)

return redirect(url_for(’admin_dashboard’))

else:

all_urls = get_all_urls()

all_users = user_account.get_all_users()

performance_data = get_system_performance()

return {’urls’: all_urls, ’users’: all_users, ’performance’: performance_data}

if __name__ == ’__main__’:

app.run(debug=True)

“‘

GPT4 API response

⬇

The provided code implements the following features:

1. **URL Shortening**:

- [x] 1.1. Users can input a URL to be shortened.

- [x] 1.2. The system validates that the URL is active and legitimate.

- [x] 1.3. The system generates a unique shortened URL.

- [ ] 1.4. Users can choose custom short links (subject to availability).

2. **Redirection**:

- [x] 2.1. Accessing the shortened URL redirects to the original URL.

3. **Analytics**:

- [x] 3.1. Users can view statistics about their shortened URLs.

- [x] 3.2. View number of clicks.

- [x] 3.3. View date/time of each click.

- [ ] 3.4. View geographical location of the clicker.

4. **User Accounts**:

- [x] 4.1. Users can create accounts.

- [x] 4.2. Account holders can view all their shortened URLs.

- [x] 4.3. Account holders can edit or delete their shortened URLs.

- [x] 4.4. Account holders can view analytics for all their shortened URLs.

5. **Admin Dashboard**:

- [x] 5.1. Administrators can view all shortened URLs.

- [x] 5.2. Administrators can delete any URL or user account.

- [x] 5.3. Administrators can monitor system performance and analytics.

6. **Expiration**:

- [x] 6.1. Users can set an expiration date/time for the shortened URL.

Counting the checked boxes, we get a total of 15 features implemented.

FEATURES_FUNCTIONAL=15

The final line of the response, ‘FEATURES_FUNCTIONAL’ is then extracted by a
regex parser. We note that the use of the feature requirements specified as a
checklist helps the LLM check which features are fully implemented and which
features are not and aids in counting the number of features that have been
fulfilled in the generated code base according to the user-specified input
feature requirements.

Furthermore, we also incorporate standard code generation evaluation metrics
(Hasemer, 2018), such as the number of lines of code generated LOC and the
number of errors # Errors in the code base determined by a code syntactical
analyzer (Thénault, 2023). Specifically, we use PyLint, a well-known Python
syntactical analyzer, and configure it to only detect and count the number of
errors in the code, which becomes static syntax errors that arise from the
generated outputs. We configure it with the following options of ‘–disable=all
–enable=E’.

Moreover, as the methods are instructed to generate unit tests to check that
the generated code is valid, we also quote how many self-generated unit tests
pass with the method as Tests Passed. We compute this metric by running a
Python test tool, that of PyTest (Okken, 2022). This is configured to
automatically find all relevant python tests (default configuration), and the
LLM can call this separately as a function on only code path input.

Experimental setup. We complete 10 random seed runs for each task environment
for each benchmark method. We then compute each metric alongside its 95%
confidence intervals throughout.

###  Appendix H Additional Results

####  H.1 Additional main results

In the following, we provide a more detailed main results table, including
additional test metrics to show the number of failed and tests that passed,
tabulated in table 3. We also provide a code base output example from each of
the methods and observe that they illustrate the difference in quality between
the respective approaches. Notably all methods were given the exact same user-
specified feature requirements for the given long code generation task,
appendix E.

Table 3:  Codebase generation system design task results showing the
percentage of functional features specified that are fully implemented
(Features %), the number of syntactical errors in the generated code (#
Errors), the number of lines of code (LOC), number of failing tests (Tests
Failed), and number of passing tests (Tests Passed). Code-L2MAC fully
implements the highest percentage of user-specified feature requirements
across all tasks by generating fully functional code that has minimal