# Adaptive REST API Testing with
Reinforcement Learning

Myeongsoo Kim  Georgia Institute of Technology
Atlanta, Georgia, USA
<EMAIL_ADDRESS>Saurabh Sinha  IBM Research
Yorktown Heights, New York, USA
<EMAIL_ADDRESS>Alessandro Orso  Georgia Institute of Technology
Atlanta, Georgia, USA
<EMAIL_ADDRESS>
###### Abstract

Modern web services increasingly rely on REST APIs. Effectively testing these
APIs poses challenges due to the vast search space to explore, which involves
selecting API operations for sequence creation, choosing parameters for each
operation from a potentially large set, and sampling values from the often
infinite parameter input space. Current testing tools lack efficient
exploration mechanisms, treating all operations and parameters equally without
considering their importance or complexity and lacking prioritization
strategies. Furthermore, these tools struggle when response schemas are absent
in the specification or exhibit variants. To address these limitations, we
present an adaptive REST API testing technique that incorporates reinforcement
learning to prioritize operations and parameters for exploration. Our approach
dynamically analyzes request and response data to inform dependent parameters
and adopts a sampling-based strategy for efficient processing of dynamic API
feedback. We evaluate our technique on ten RESTful services, comparing it
against state-of-the-art tools with respect to code coverage achieved and the
number of generated requests, operations covered, and service failures
triggered. Additionally, we perform an ablation study on prioritization,
dynamic feedback analysis, and sampling to assess their individual effects.
Our findings demonstrate that our approach significantly outperforms existing
REST API testing tools in terms of effectiveness, efficiency, and fault-
finding ability.

###### Index Terms:

Reinforcement Learning for Testing, Automated REST API Testing

##  I Introduction

The increasing adoption of modern web services has led to a growing reliance
on REpresentational State Transfer (REST) APIs for communication and data
exchange [richardson2013restful, patni2017pro]. REST APIs adhere to a set of
architectural principles that enable scalable, flexible, and efficient
interactions between various software components through the use of standard
HTTP methods and a stateless client-server model [fielding2000architectural].
To facilitate their discovery and use by clients, REST APIs are often
documented using specification languages [openapi, swagger, raml,
apiblueprint], which let developers describe the APIs in a structured format
and provide essential information, such as the available endpoints, input
parameters and their schemas, response schemas, etc. Platforms such as APIs
Guru [apis_guru] and Rapid [rapidapi] host thousands of RESTful API documents,
emphasizing the significance of these standardized API specifications in
industry.

Standardized documentation formats, such as the OpenAPI specification
[openapi], not only facilitate the development of APIs and their use by
clients, but also provide a foundation for the development of automated
testing techniques for REST APIs, and numerous such techniques and tools have
emerged in recent years (e.g., [arcuri2019restful, Corradini2022,
atlidakis2019restler, martin2020restest, karlsson2020automatic,
karlsson2020quickrest, liu2022morest, wu2022combinatorial][arcuri2019restful,
Corradini2022, atlidakis2019restler, karlsson2020quickrest, martin2021restest,
karlsson2020automatic, zac2022schemathesis, wu2022combinatorial]). In spite of
this, effectively testing REST APIs continues to be a challenge, with high
code coverage remaining an elusive goal for tools [kim2022automated].

Testing REST APIs can be challenging because of the large search space for
exploration, arising from numerous operations, potential execution orders,
inter-parameter dependencies, and associated input parameter value constraints
[martin2019catalogue][kim2022automated, martin2019catalogue]. Current
techniques often struggle to explore this space due to the lack effective
exploration strategies for operations and their parameters. Existing testing
tools tend to treat all operations and parameters equally, disregarding their
importance or complexity, leading to suboptimal testing strategies and
insufficient coverage of crucial operation and parameter combinations.
Moreover, these tools rely on discovering producer-consumer relationships
between response schemas and request parameters, which works well when the
parameter and response schemas are described in detail in the specification.
However, if the schemas are incomplete or imprecise, the tools can become less
effective in their exploration.

In this paper, we present adaptive REST API testing with reinforcement
learning (arat-rl), an advanced black-box testing approach that addresses
these limitations of existing tools. Our technique incorporates several
innovative features, such as leveraging reinforcement learning to prioritize
operations and parameters for exploration, dynamically constructing key-value
pairs from both response and request data, analyzing these pairs to inform
dependent operations and parameters, and utilizing a sampling-based strategy
for efficient processing of dynamic API feedback. The primary objective of our
approach is to increase code coverage and improve fault-detection capability.

The core of novelty in arat-rl is an adaptive testing strategy, driven by a
reinforcement-learning-based prioritization algorithm for exploring the space
of operations and parameters. The algorithm initially determines an
operation’s importance based on the parameters used and their frequencies
across other operations. This targeted exploration enables efficient coverage
of critical operations and parameters, thereby optimizing code coverage. The
technique employs reinforcement learning to adjust the priority weights
associated with operations and parameters based on feedback, by decreasing
importance for successful responses and increasing it for failed responses.
The technique also assigns weights to parameter-value mappings based on
various sources of input values (e.g., random, specified values, response
values, request values, and default values), which lets it adapt the testing
strategy and concentrate on areas more likely to contain faults, ultimately
enhancing fault-detection capability. The adaptive nature of arat-rl gives
precedence to yet-to-be-explored or previously error-prone operations, paired
with suitable value mappings, optimizing the efficiency of API exploration.

Another innovative feature of arat-rl is dynamic construction of key-value
pairs. In contrast to existing approaches that rely heavily on resource
schemas provided in the specification, our technique dynamically constructs
key-value pairs by analyzing POST operations (i.e., resource creation HTTP
method) and examining both response and request data. For instance, support
that an operation takes book title and price as request parameters and, as
response, produces a success status code along with a string message (e.g.,
“Successfully created”). Our technique leverages this information to create
key-value pairs for book title and price, upon receiving a successful
response, even without such data being present in the response. It takes into
account the input parameters used in the request, as they correspond to the
created resource. Moreover, if the service returns incomplete resources, our
technique still processes the information available in key-value pairs. This
dynamic approach enables our tool to identify resources from the API responses
and requests and discover hidden dependencies that are not evident from the
specification alone.

Finally, arat-rl employs a simple yet effective sampling-based approach that
allows it to process dynamic API feedback efficiently and adapt its
exploration based on the gathered information. By randomly sampling key-value
pairs from responses, our tool reduces the overhead of processing every
response for each pair, resulting in more efficient testing and optimized
utilization of testing resources.

To evaluate the technique, we conducted empirical studies using 10 RESTful
services and compared it against three state-of-the-art REST API testing
tools: RESTler [atlidakis2019restler], EvoMaster [arcuri2019restful], and
Morest [liu2022morest]. We assessed the effectiveness of arat-rl in terms of
coverage achieved and service failures triggered, and its efficiency in terms
of valid and fault-inducing requests generated and operations covered within a
given time budget. Our results show that arat-rl outperforms the competing
tools in all the metrics considered—it achieved the highest method, branch,
and line coverage rates, along with better fault-detection ability.
Specifically, arat-rl covered 119.17%, 59.83%, and 52.42% more branches,
lines, and methods than RESTler; 37.03%, 20.87%, and 14.13% more branches,
lines, and methods than EvoMaster; and 23.69%, 11.87%, and 9.55% more
branches, lines, and methods than Morest. arat-rl also uncovered 9.2x, 2.5x,
and 2.4x more bugs than RESTler, EvoMaster, and Morest, respectively. In terms
of efficiency, arat-rl generated 52.01%, 40.79%, and 1222% more valid and
fault-inducing requests and covered 15.38%, 24.14%, and 282.98% more
operations than Morest, EvoMaster, and RESTler, respectively, in a one-hour
testing time budget. We also conducted an ablation study to assess the
individual effects of prioritization, dynamic feedback analysis, and sampling
on the overall effectiveness of arat-rl. Our results indicate that
reinforcement-learning-based prioritization contributes the most to arat-rl’s
effectiveness, followed by dynamic feedback analysis and sampling in that
order.

⬇

/products/{productName}/configurations/{configurationName}/features/{featureName}:

post:

operationId: addFeatureToConfiguration

produces:

- application/json

parameters:

- name: productName

in: path

required: true

type: string

- name: configurationName

in: path

required: true

type: string

- name: featureName

in: path

required: true

type: string

responses:

default:

description: successful operation

/products/{productName}/configurations/{configurationName}/features:

get:

operationId: getConfigurationActivedFeatures

produces:

- application/json

parameters:

- name: productName

in: path

required: true

type: string

- name: configurationName

in: path

required: true

type: string

responses:

’200’:

description: successful operation

schema:

type: array

items:

type: string

Figure 1: A Part of Features-Service’s OpenAPI Specification.

The main contributions of this work are:

  * •

A novel approach for adaptive REST API testing that incorporates (1)
reinforcement learning to prioritize exploration of operations and parameters,
(2) dynamic analysis of request and response data to inform dependent
parameters, and (3) a sampling-based strategy for efficient processing of
dynamic API feedback.

  * •

Empirical results demonstrating that arat-rl outperforms state-of-the-art show
that our tool, arat-rl, surpasses other leading REST API testing toolsin terms
of requestsgenerated, code coverage achieved, and service failures triggered.
Specifically, it excels in generating valid and fault-inducing requests,
covering a greater number of operations, achieving higher code coverage, and
triggering more service failures.

  * •

An artifact [artifact] containing the tool, the benchmark services, and the
empirical data.

The remainder of this paper is organized as follows: Section II presents the
background and a motivating example, illustrating the challenges in current
REST API testing; Section III describes our innovative ARAT-RL approach;
Section IV delves into the evaluation process and results, providing
comprehensive data and comparative analyses to bolster our findings; Section V
reviews related work; and finally, Section VI offers our conclusions and
highlights potential avenues for future work.

##  II Background and Motivating Example

We provide a brief introduction to REST APIs, the OpenAPI specification, and
reinforcement learning, and then illustrate the novel features of our approach
using a running example.

###  II-A REST APIs

REST APIs are web APIs that adhere to the RESTful architectural style
[fielding2000architectural]. REST APIs facilitate communication between
clients and servers by exchanging data through standardized protocols, such as
HTTP [rodriguez2008restful]. Key principles of REST include statelessness,
cacheability, and a uniform interface, which simplify client-server
interactions and promote loose coupling [tilkov2007brief]. Clients communicate
with web services by sending HTTP requests. These requests access and/or
manipulate resources managed by the service, where a resource represents data
that a client may want to create, delete, update, or access. Requests are sent
to an API endpoint, identified by a resource path and an HTTP method
specifying the action to be performed on the resource. The most commonly used
methods are POST, GET, PUT, and DELETE, for creating, reading, updating, and
deleting a resource, respectively. The combination of an endpoint and an HTTP
method is called an operation. Besides specifying an operation, a request can
also optionally include HTTP headers containing metadata and a body with the
request’s payload. Upon receiving and processing a request, the web service
returns a response containing headers, possibly a body, and an HTTP status
code—a three-digit number indicating the request’s outcome. Specifically,
status codes in the range of 2xx denote successful responses, while codes in
the 4xx range indicate client errors, and a status of 500 suggests a server
error.

###  II-B OpenAPI Specification

The OpenAPI Specification (OAS) [openapi] is a widely adopted API description
format for RESTful APIs, providing a standardized and human-readable way to
describe the structure, functionality, and expected behavior of an API. Figure
1 illustrates an example OAS file describing a part of a Features-Service API.
This example shows two API operations. The first operation, a POST request, is
designed to add a feature name to a product’s configuration. It requires three
parameters: the product name, configuration name, and feature name, all of
which are specified in the path. Upon successful execution, the API responds
with a JSON object, signaling that the feature has been added to the
configuration. The second operation, a GET request, retrieves the active
features of a product’s configuration. Similar to the first operation, it
requires the product name and configuration name as path parameters. The API
responds with a 200 status code and an array of strings representing the
active features in the specified configuration.

###  II-C Reinforcement Learning and Q-Learning

Reinforcement learning (RL) is a type of machine learning where an agent
learns to make decisions by interacting with an environment
[sutton2018reinforcement]. The agent selects actions in various situations
(states), observes the consequences (rewards), and learns to choose the best
actions to maximize the cumulative reward over time. The learning process in
RL is trial-and-error based, meaning the agent discovers the best actions by
trying out different options and refining its strategy based on the observed
rewards.

Q-learning is a widely used model-free reinforcement learning algorithm that
estimates the optimal action-value function, $Q(s,a)$ [watkins1992q]. The
Q-function represents the expected cumulative reward the agent can obtain by
taking action $a$ in state $s$ and then following the optimal policy.
Q-learning uses a table to store Q-values and updates them iteratively based
on the agent’s experiences. The learning process consists of the agent
performing actions, receiving rewards, and updating the Q-values according to
the following update rule:

$Q(s,a)\leftarrow
Q(s,a)+\alpha[r+\gamma\max_{a^{\prime}}Q(s^{\prime},a^{\prime})-Q(s,a)]$ (1)

where $\alpha$ is the learning rate, $\gamma$ is the discount factor,
$s^{\prime}$ is the new state after taking action $a$, and $r$ is the
immediate reward received. The agent updates the Q-values to converge to their
optimal values, which represent the expected long-term reward of taking each
action in each state.

###  II-D Motivating Example

Next, we illustrate the salient features of arat-rl using the Feature-Service
specification as an example.

3pt 5pt RL-based adaptive exploration.: For the example in Figure 1, to
perform the operation addFeatureToConfiguration, we must first create a
product using a separate operation and establish a configuration for it using
another operation. The sequence of operations should, therefore, be: create
product, create configuration, and create feature name for the product with
the specified configuration name. This example emphasizes the importance of
determining the operation sequence. Our technique initially assigns weights to
operations and parameters based on their usage frequency in the specification.
In this case, productName is the most frequently used parameter across all
operations; therefore, our technique assigns higher weights to operations
involving productName. Specifically, the operation for creating a product gets
the highest priority.

Moreover, once an operation is executed, its priority must be adjusted so that
it is not explored repeatedly, creating new product instances unnecessarily.
After processing a prioritized operation, our technique employs RL to adjust
the weights in response to the API response received. If a successful response
is obtained, negative rewards are assigned to the processed parameters, as our
objective is to explore other uncovered operations. This method naturally
leads to the selection of the next priority operation and parameter,
facilitating efficient adjustments to the call sequence.

Inter-parameter dependencies [martin2019catalogue] can increase the complexity
of the testing process, as some parameters might have mutual exclusivity or
other constraints associated with them (e.g., only one of the parameters needs
to be specified). RL-based exploration based in feedback received can also
help with dealing with this complexity.

3pt 5pt Dynamic construction of key-value pairs.One of the key steps in recent
: Contemporary REST API testing techniquesstrategies, as documented in recent
studies [Corradini2022, atlidakis2019restler, liu2022morest]is identification
of , emphasize the importance of discerning producer-consumer relations
relationships between response schemas and request parameters. However,
current tools face limitations when operations produce unstructured output
(e.g., plain text) or have incomplete response schemas in their
specifications. For instance, the addFeatureToConfiguration operation lacks
structured response data (e.g., JSON format). Despite this, our approach
processes and generates key-value data {productName: value, configurationName:
value, featureName: value} from the request data, as the POST HTTP method
indicates that a resource is created using the provided inputs.

By analyzing and storing key-value pairs identified from request and response
data, even when the response schema is not explicitly provided or is
incomplete, our dynamic key-value pair construction method proves especially
beneficial in cases of responses with plain-text descriptions or incomplete
response schemas. The technique can effectively uncover hidden dependencies
not evident from the specification.

3pt 5pt Sampling for efficient dynamic key-value pair construction.: API
response data can sometimes be quite large and processing every response for
each key-value pair can be computationally expensive. To address this issue,
we have incorporated a sampling-based strategy into our dynamic key-value pair
construction method. This strategy efficiently processes the dynamic API
feedback and adapts its exploration based on the gathered information while
minimizing the overhead of processing every response.

Figure 2: Overview of our approach.

##  III Our Approach

In this section, we introduce our Q-Learning-based REST API testing approach,
which intelligently prioritizes and selects the operations, parameters, and
value mapping sources while dynamically constructing key-value pairs. Figure 2
provides a high-level overview of our approach. Initially, the Q-Learning
Initialization module sets up the necessary variables and tables for the
Q-learning process. The Q-Learning Updater subsequently receives these
variables and tables and passes them to the Prioritization module, which is
responsible for selecting operations, parameters, and value mapping sources.

Afterward, arat-rl sends a request to the System Under Test (SUT) and receives
a response. It also supplies the request, response, selected operation,
parameters, mapped value source, $\alpha$, $\gamma$, and $\epsilon$ to the
Q-Learning Updater. The feedback is analyzed with the request and response,
storing key-value pairs extracted from them for future use. The Updater
component then adjusts the Q-values based on the outcomes, enabling the
approach to adapt and refine its decision-making process over time. arat-rl
iterates through this procedure until the specified time limit is reached. In
the rest of this section, we present the details of the algorithm.

###  III-A Q-Learning Table Initialization

The Q-Learning Table Initialization component, shown in Algorithm 1, is
responsible for setting up the initial Q-table and Q-value data structures
that guide the decision-making process throughout API testing. Crucially, this
process happens without making any API calls.

The algorithm begins by setting the learning rate ($\alpha$) to 0.1, the
discount factor ($\gamma$) to 0.99, and the exploration rate ($\epsilon$) to
0.1 (lines 2–4). These parameters control the learning and exploration process
of the Q-Learning algorithm. The algorithm then initializes empty dictionaries
for the Q-table and Q-value (lines 5–6). These parameters control the
Q-Learning process, and the chosen values are those commonly recommended and
used (e.g., [qlearningex1, qlearningex2, masadeh2018reinforcement]).

Algorithm 1 Q-Learning Table Initialization

1:procedure InitializeQLearning(operations)

2: Set learning rate ($\alpha$) to 0.1

3: Set discount factor ($\gamma$) to 0.99

4: Set discount factor ($\epsilon$) to 0.1

5: Initialize empty dictionary $q\\_table$

6: Initialize empty dictionary $q\\_value$

7: for operation in operations do

8: operation_id $\leftarrow$ operation[’operationId’]

9: $q\\_value[\text{operation\\_id}]\leftarrow$ new dictionary

10: for source in [1, 2, 3, 4, 5] do

11: $q\\_value[\text{operation\\_id}][\text{source}]\leftarrow$ 0

12: end for

13: for parameter in operation[’parameters’] do

14: param_name $\leftarrow$ parameter[’name’]

15: $q\\_table[\text{param\\_name}]=q\\_table[\text{param\\_name}]+1$

16: end for

17: for response_data in operation_data.get(’responses’) do

18: for key in response_data.keys() do

19: if key in $q\\_table$ then

20: $q\\_table[\text{key}]=q\\_table[\text{key}]+1$

21: end if

22: end for

23: end for

24: end for

25: return $\alpha$, $\gamma$, $\epsilon$, $q\\_table$, $q\\_value$

26:end procedure

The algorithm iterates through each operation in the API (lines 7–24). For
each operation, it extracts the operation’s unique identifier (operation_id)
and initializes a new dictionary in the Q-value dictionary for the
operation_id (lines 8–9). Next, it initializes the Q-values for each value
mapping source (1 to 5) to 0 (lines 10–12).

The algorithm proceeds to iterate through each parameter in the operation
(lines 13–16). It extracts the parameter’s name (param_name) and, if
param_name already exists in the Q-table, it increments the corresponding
entry by one. If it does not exist, it initializes this entry to one. This
step builds the Q-table with a count of occurrences for each parameter.

Subsequently, the algorithm iterates through the response data of each
operation (lines 17–23). It extracts keys from the response data and checks if
the key is present in the Q-table for the operation_id (line 18). If the key
is present in the Q-table for the operation_id, it increments the
corresponding entry in the Q-table by 1 (lines 19–21). This step populates the
Q-table with the frequency of occurrences for each response key as well.

Finally, the algorithm returns the learning rate ($\alpha$), discount factor
($\gamma$), exploration rate ($\epsilon$), Q-table, and Q-value dictionaries
(line 25). This initial setup provides the Q-Learning algorithm with a
foundational understanding of the API operations and their relationships,
which is further refined during the testing process.

Algorithm 2 Q-Learning-based Prioritization

1:procedure SelectOperation

2: Initialize $\text{max\\_avg\\_q\\_value}\leftarrow-\infty$

3: Initialize $\text{best\\_operation}\leftarrow\text{None}$

4: for operation in operations do

5: operation_id $\leftarrow$ operation[’operationId’]

6: Initialize $\text{sum\\_q\\_value}\leftarrow 0$

7: Initialize
$\text{num\\_params}\leftarrow\text{len(operation['parameters'])}$

8: for parameter in operation[’parameters’] do

9: param_name $\leftarrow$ parameter[’name’]

10:
$\text{sum\\_q\\_value}\leftarrow\text{sum\\_q\\_value}+q\\_table[\text{param\\_name}]$

11: end for

12:
$\text{avg\\_q\\_value}\leftarrow\text{sum\\_q\\_value}/\text{num\\_params}$

13: if $\text{avg\\_q\\_value}>\text{max\\_avg\\_q\\_value}$ then

14: $\text{max\\_avg\\_q\\_value}\leftarrow\text{avg\\_q\\_value}$

15: $\text{best\\_operation}\leftarrow\text{operation}$

16: end if

17: end for

18: return best_operation

19:end procedure

20:procedure SelectParameters(operation, $\epsilon$)

21: Set $n$ randomly ($0\leq n\leq\text{length of operation['parameters']}$)

22: Initialize empty list $selected\\_parameters$

23: if $\text{random.random()}>\epsilon$ then

24: Sort operation[’parameters’] by Q-values in descending order

25: for $i\leftarrow 0$ to $n-1$ do

26: Append operation[’parameters’][i] to $selected\\_parameters$

27: end for

28: else

29: for param in
$\text{random.sample}(operation[^{\prime}parameters^{\prime}],n)$ do

30: Append param to $selected\\_parameters$

31: end for

32: end if

33: return $selected\\_parameters$

34:end procedure

35:procedure SelectValueMappingSource(operation, $\epsilon$)

Source1:

Example values in specification

Source2:

Random value generated by the parameter’s type and format

Source3:

Dynamically constructed key-value pairs from request

Source4:

Dynamically constructed key-value pairs from response

Source5:

Default values (string: string, number: 1.1, integer: 1, array: [], object:
{})

36: operation_id $\leftarrow$ operation[’operationId’]

37: $sources\leftarrow[1,2,3,4,5]$

38: if $\text{random.random()}>\epsilon$ then

39: $max\\_q\leftarrow\arg\max_{\text{source}\in
sources}q\\_value[\text{operation\\_id}][\text{source}]$

40: return $max\\_q$

41: else

42: return random.randint(1, 5)

43: end if

44:end procedure

Algorithm 3 Q-Learning-based API Testing

1:procedure QLearningUpdater(response, $q\\_table$, $q\\_value$, selected_op,
selected_params, $\alpha$, $\gamma$)

2: operation_id $\leftarrow$ selected_operationop[’operation_id’]

3: if response.status_code is 2xx (successful) then

4: Extract key-value pairs from request and response

5: reward $\leftarrow-1$

6: Update $q\\_value$ negatively

7: else if response.status_code is 4xx or 500 (unsuccessful) then

8: reward $\leftarrow 1$

9: Update $q\\_value$ positively

10: end if

11: for $eachparaminselected\\_params$ do

12: for $eachparam\\_name,param\\_valueinparam.items()$ do

13: old_q_value $\leftarrow q\\_table$[operation_id][param_name]

14: max_q_value_next_state $\leftarrow$
max($q\\_table$[operation_id].values())

15: $q\\_table$[operation_id][param_name] $\leftarrow$ old_q_value + $\alpha$
* (reward + $\gamma$ * (max_q_value_next_state - old_q_value))

16: end for

17: end for

18: return $q\\_table$, $q\\_value$

19:end procedure

20:procedure Main

21: Initialize $\epsilon_{max}\leftarrow 1$

22: Initialize $\epsilon_{adapt}\leftarrow 1.1$

23: Initialize $time_{l}imit\leftarrow$ desired time limit in seconds

24: operations $\leftarrow$ Load API specification

25: $\alpha$, $\gamma$, $\epsilon$, $q\\_table$, $q\\_value$ $\leftarrow$
InitializeQLearning(operations)

26: while Time Limit do

27: best_operation $\leftarrow$ SelectOperation()

28: selected_parameters $\leftarrow$ SelectParameters(best_operation,
$\epsilon$)

29: selected_source $\leftarrow$ SelectValueMappingSource(best_operation,
$\epsilon$)

30: response $\leftarrow$ Execute best_operation with selected_parameters and
selected_source

31: $q\\_table$, $q\\_value$ $\leftarrow$ QLearningUpdater(response,
$q\\_table$, $q\\_value$, selected_operation, selected_parameters, $\alpha$,
$\gamma$)

32: $\epsilon\leftarrow\min(\epsilon_{max},\epsilon_{adapt}*\epsilon)$

33: end while

34:end procedure

###  III-B Q-Learning-based Prioritization

In this step, we prioritize API operations and select the best parameters and
value mapping sources based on their Q-values. We present Algorithm 2
(SelectOperation, SelectParameters, and SelectValueMappingSource) to describe
the prioritization process.

The SelectOperation procedure (lines 1–19) is responsible for selecting the
best API operation to test. The algorithm initializes variables to store the
maximum average Q-value and the best operation (lines 2–3). It iterates
through each operation, calculating the average Q-value for the operation’s
parameters (lines 4–17). The operation with the highest average Q-value is
selected as the best operation (line 15).

The SelectParameters procedure (lines 20–34) is responsible for selecting a
subset of parameters for the chosen API operation. This selection is guided by
the exploration rate ($\epsilon$). If a random value is greater than
$\epsilon$, the algorithm selects the top $n$ parameters sorted by their
Q-values in descending order (lines 23–27). Otherwise, the algorithm randomly
selects $n$ parameters from the operation’s parameters (lines 28–31). The
selected parameters are then returned (line 33).

The SelectValueMappingSource procedure (lines 35–44) is responsible for
selecting the value mapping source for the chosen API operation. The technique
leverages five types of value mapping sources.

  * •

Source 1 (example values in specification): These values are provided in the
API documentation as examples for a parameter. We consider three types of
OpenAPI keywords that can specify example values: enum, example, and
description [openapi]. Although the The OpenAPI website mentions that users
can specify example values in the description field, these and a recent study
also underscores the importance of these example values in descriptions
[kim2023enhancing]. However, these examples are often not provided in a
structured format but rather as natural language text. To extract example
values from the description field, we create a list containing every word in
the text, as well as every quoted phrase.

  * •

Source 2 (random value generated by the parameter’s type, format, and
constraints): This source generates random values for each parameter based on
its type, format, and constraints. To generate random values, we utilize
Python’s built-in random library. For date and date-time formats, we employ
the datetime library to randomly select dates and times. If the parameter has
a regular expression pattern specified in the API documentation, we generate
the value randomly using the rstr library [rstr]. When a minimum or maximum
constraint is present, we pass it to the random library to ensure that the
generated values adhere to the specified constraints. This approach allows us
to explore a broader range of values compared to the example values provided
in the API specification.

  * •

Source 3 (dynamically constructed key-value pairs from request): This source
extracts key-value pairs from the dynamically constructed request key-value
pairs. We employ Gestalt pattern matching [difflib] to identify the key most
similar to the parameter name. This technique aids in discovering producer-
consumer relationships.

  * •

Source 4 (dynamically constructed key-value pairs from response): Similar to
Source 3, this source obtains key-value pairs from dynamically constructed
response key-value pairs. We use the same Gestalt pattern matching approach to
identify the key, further assisting in the identification of producer-consumer
relationships.

  * •

Source 5 (default values): This source uses predefined default values for each
data type (string: string, number: 1.1, integer: 1, array: [], object: {}).
These default values can be useful for testing how the API behaves when it
receives the simplest or most common input values.

Similar to the SelectParameters procedure, the selection of the value mapping
source is guided by the exploration rate ($\epsilon$). If a random value is
greater than $\epsilon$, the algorithm selects the mapping source with the
highest Q-value for the chosen operation (lines 38–40). This helps the
algorithm focus on the most promising mapping sources based on prior
experience. Otherwise, the algorithm randomly selects a mapping source from
the available sources (line 42). This randomness ensures that the algorithm
occasionally explores less promising mapping sources to avoid getting stuck in
a suboptimal solution.

###  III-C Q-Learning-based API Testing

In this step, we execute the selected API operations with the selected
parameters and value mapping sources, and update the Q-values based on the
response status codes. Algorithm 3 (QLearningUpdater and Main) describes the
API testing process and the update of Q-values using the learning rate
($\alpha$) and discount factor ($\gamma$).

The QLearningUpdater procedure (lines 1–19) is responsible for updating the
Q-values based on the response status codes. It first extracts the operation
ID from the selected operation (line 2). If the response status code indicates
a successful request (2xx), the algorithm extracts key-value pairs from the
request and response, assigns a reward of $-1$, and updates the Q-values
negatively (lines 3–6). If the response status code indicates an unsuccessful
request (4xx or 500), the algorithm assigns a reward of 1 and updates the
Q-values positively (lines 7–10). The Q-values are updated for each parameter
in the selected parameters using the Bellman equation (lines 11–16), and the
updated Q-values are returned (line 18).

The Main procedure (lines 20–34) orchestrates the Q-Learning-based API testing
process. It initializes the exploration rate ($\epsilon$), its maximum value
($\epsilon_{max}$), its adaptation factor ($\epsilon_{adapt}$), and the
desired time limit for testing (lines 21–23). The API specification is loaded
and the Q-Learning table is initialized (lines 24–25). The algorithm then
enters a loop that continues until the time limit is reached (line 26). In
each iteration, the best operation, selected parameters, and selected mapping
source are determined (lines 27–29). The API operation is executed with the
selected parameters and mapping source, and the response is obtained (line
30). The Q-values are then updated based on the response (line 31), and the
exploration rate ($\epsilon$) is updated (line 32).

By continuously updating the Q-values based on the response status codes and
adapting the exploration rate, the Q-Learning-based API testing process aims
to effectively explore the API operations and parameters, identifying
potential issues in the API implementation.

##  IV Evaluation

Figure 3: Branch, line, and method coverage achieved by the tools on the
benchmark services.

In this section, we present the results of empirical studies conducted to
assess arat-rl. Our evaluation aims to address the following research
questions:

  1. 1.

RQ1: How does arat-rl compare with state-of-the-art tools for REST API testing
in terms of code coverage?

  2. 2.

RQ2: How does the efficiency of arat-rl, measured in terms of valid and fault-
inducing requests generated and operations covered within a given time budget,
compare to that of other REST API testing tools?

  3. 3.

RQ3: In terms of error detection, how does our approach perform at identifying
500 responses in REST APIs when compared to state-of-the-art REST API testing
tools?

  4. 4.

RQ4: How do the main components of arat-rl—prioritization, dynamic key-value
pair construction, and sampling—contribute to its overall performance?

###  IV-A Experimental Setup

We performed our experiments using Google Cloud E2 machines, each equipped
with 24-core CPU and 96 GB of RAM. We created a machine image containing all
the services and tools in our benchmark. For each experiment, we deleted and
recreated the machines using this image to minimize potential dependency
issues. Each machine hosted all the services and tools under test, but we ran
one tool at a time during the experiments. We monitored CPU and memory usage
throughout the testing process to ensure that the testing tools were not
affected by a lack of memory or CPU resources.

To evaluate the effectiveness and efficiency of our approach, we compared its
against three state-of-the-art tools: EvoMaster [arcuri2019restful], RESTler
[atlidakis2019restler], and Morest [liu2022morest]. We selected 10 RESTful
services from a recent REST API testing study as our benchmark. We explain the
selection process of these tools and services next.

#### Testing Tools Selection

As a preliminary note, because arat-rl is a black-box approach, we only
considered black-box tools in our comparison. We believe that adding to the
comparison white-box tools would result in an unfair comparison, as these
tools leverage information about the code, rather than just information in the
specification, to generate test inputs.

We identified an initial set of 10 tools based on a recent study
[kim2022automated]. From this list, we chose (the black-box version of)
EvoMaster [arcuri2019restful] and RESTler [atlidakis2019restler]. EvoMaster
employs an evolutionary algorithm for automated test case generation and was
the best-performing tool in that study and in another recent comparison
[zhang2022open]. Its strong performance makes it an appropriate candidate for
comparison. RESTler adopts a grammar-based fuzzing approach to explore APIs.
It is a well-established tool in the field and, in fact, the most popular REST
API testing tool in terms of GitHub stars.

Recently, two new tools have been published. Morest [liu2022morest] has been
shown to have superior results compared to EvoMaster. We, therefore, included
Morest in our set of tools for comparison, as it could potentially outperform
the other tools. The other recent tool, RestCT, was also considered for
inclusion in our evaluation. However, we encountered failures while running
it. We contacted the authors, who confirmed the issues and said they will work
on resolving them.

#### RESTful Services Selection

As benchmarks for our evaluation, we selected 10 out of 20 RESTful services
from a recent study by Kim et al. [kim2022automated]. We had to exclude 10
services for various reasons. Specifically, we omitted the News service,
developed by the author of our baseline EvoMaster, to avoid possible bias.
Problem Controller and Spring Batch REST were excluded because they require
specific domain knowledge to generate any meaningful test, so using them
provides limited information about the tools. We excluded Erc20-rest-service
and Spring Boot Actuator because some APIs in these services did not provide
valid responses due to external dependencies being updated without
corresponding updates in the service code. We also excluded Proxyprint, OCVN,
and Scout API due to authentication issues that prevented them from generating
meaningful responses. Finally, we excluded CatWatch and Cwa-verification
because of their restrictive rate limits, which slowed down the testing
process and made it impossible to collect results in a reasonable amount of
time.

Our final set of services consisted of Features Service, LanguageTool, NCS,
REST Countries, SCS, Genome Nexus, Person Controller, User Management
Microservice, Simple Internet-Market, and Project Tracking System.

TABLE I: Comparison of operations covered and requests (2xx and 500 status
codes) by arat-rl, Morest, EvoMaster, and RESTler.

ARAT-RL Morest EvoMaster RESTler #operations #requests #operations #requests
#operations #requests #operations #requests service covered 2xx&500 2xx 500
covered 2xx&500 2xx 500 covered 2xx&500 2xx 500 covered 2xx&500 2xx 500
Features Service 18 95,479 43,460 52,019 18 103,475 4,920 98,555 18 113,136
33,271 79,865 17 4,671 1,820 2,851 Language Tool 2 77,221 67,681 9,540 1 1,273
1,273 0 2 22,006 17,838 4,168 1 32,796 32,796 0 NCS 6 62,618 62,618 0 5 18,389
18,389 0 2 61,282 61,282 0 2 140 140 0 REST Countries 22 36,297 35,486 811 22
8,431 7,810 621 16 9,842 9,658 184 6 259 255 4 SCS 11 115,328 115,328 0 11
110,147 110,147 0 10 66,313 66,313 0 10 5,858 5,857 1 Genome Nexus 23 15,819
14,010 1,809 23 32,598 10,661 21,937 19 8,374 8,374 0 1 182 182 0 Person
Controller 12 101,083 47,737 53,346 11 104,226 10,036 94,190 12 91,316 37,544
53,772 1 167 102 65 User Management 21 44,121 13,356 30,765 17 1,111 948 163
18 29,064 13,003 16,061 4 79 64 15 Market Service 12 29,393 6,295 23,098 6
1,399 394 1,005 5 10,697 4,302 6,395 2 1,278 0 1,278 Project Tracking 53
23,958 21,858 2,100 42 14,906 12,904 2,002 43 15,073 13,470 1,603 3 72 65 7
Average 18 60,132 42,783 17,349 15.6 39,595 17,748 21,847 14.5 42,710 26,505
16,205 4.7 4,550 4,128 422

#### Result Collection

We ran each testing tool with a time budget of one hour per execution, as a
previous study [kim2022automated] indicated that code coverage achieved by
these tools tends to plateau within this duration. To accommodate for
variability, we replicated the experiments ten times and calculated the
average metrics across these runs.

Data collection for code coverage and status codes was performed using JaCoCo
[jacoco] and Mitmproxy [mitmproxy], respectively. We focused on identifying
unique instances of 500 errors, which generally signal server-side faults. The
methodology was as follows:

  1. 1.

Stack Trace Collection: For services that provided stack traces accompanying
500 errors, we collected these traces, treating each unique trace as a
separate fault. In the majority of cases, the errors we collected fall into
this category.

  2. 2.

Response Text Analysis: In the absence of stack traces, we analyzed the
response text. After removing unrelated components (e.g., timestamps), we
classified unique instances of response text linked to 500 status codes as
individual faults.

This systematic approach allowed us to compile a comprehensive and unique
tally of faults for our analysis.

###  IV-B RQ1: Effectiveness

To answer RQ1, we compared the tools in terms of branch, line, and method
coverage achieved. Figure 3 presents the results of the study. The bar charts
represent the coverage achieved by each tool for each RESTful service, whereas
the boxplot at the bottom summarizes of each tool’s performance on the three
coverage metrics across all the services.

As demonstrated in Figure 3, arat-rl consistently outperforms the other tools
in all three coverage metrics across the selected RESTful services. Our tool
performed better, benefiting from operation, parameter, and value mapping
prioritization, as seen in the motivating example. arat-rl is especially
effective when there is operation dependency, parameter dependency, and value-
mapping dependency. For example, the greatest coverage gains occurred for
Language-tool, as shown in the figure, which has a complex set of inter-
parameter dependencies and value-mapping dependencies. Meanwhile, arat-rl
struggles with semantic parameters. For instance, it performed the worst for
Market-service. The reason for this is that it requires input data, such as
address, email, name, password, and phone number in specific formats, but
arat-rl failed to generate valid values for these. Consequently, it was unable
to create market users and use the user information for other operations in
producer-consumer relationships.

On average, arat-rl attained 36.25% branch coverage, 58.47% line coverage, and
59.42% method coverage. In comparison, Morest, which exhibited the second-best
performance, reached an average of 29.31% branch coverage, 52.27% line
coverage, and 54.24% method coverage. Thus, the coverage gain of arat-rl over
Morest is 23.69% for branch coverage, 11.87% for line coverage, and 9.55% for
method coverage. EvoMaster and RESTler yield lower average coverage rates on
all three metrics, with respective results of 26.45%, 48.37%, and 52.07% for
EvoMaster and 16.54%, 36.58%, and 38.99% for RESTler for branch, line, and
method coverage. The coverage gains of arat-rl compared to EvoMaster is 37.03%
for branch coverage, 20.87% for line coverage, and 14.13% for method coverage,
whereas compared to RESTler, it is 119.17% for branch coverage, 59.83% for
line coverage, and 52.42% for method coverage.

These results provide evidence that our technique can effectively explore
RESTful services, achieving superior code coverage compared to existing tools,
and demonstrate its potential in addressing the challenges in REST API testing
and enhancing the overall quality of software applications that rely on
RESTful services.

arat-rl consistently outperforms RESTler, EvoMaster, and Morest in terms of
branch, line, and method coverage across the selected RESTful services.
However, arat-rl can struggle with parameters that require inputs in specific
formats.

TABLE II: Faults Total faults detected by the tools in over 10 runs.

| RESTler | EvoMaster | Morest | ARAT-RL
---|---|---|---|---
Features-Service |  010 |  010 |  010 |  010
Language-Tool |  000 |  048 |  000 | 122
NCS |  000 |  000 |  000 |  000
REST-Countries |  009 |  010 |  010 |  010
SCS |  003 |  000 |  000 |  000
Genome-Nexus |  000 |  000 |  005 |  010
Person-Controller |  058 | 221 | 274 | 943
User-Management |  010 |  010 |  008 |  010
Market-Service |  010 |  010 |  010 |  010
Project-Tracking |  010 |  010 |  010 |  010
Total | 110 | 319 | 327 | 1125

###  IV-C RQ2: Efficiency

To address RQ2, we compared arat-rl to Morest, EvoMaster, and RESTler in terms
of the number of (1) valid and fault-inducing requests generated (as indicated
by HTTP status codes 2xx and 500) and (2) operations covered within a given
time budget. Although efficiency is not only dependent on these metrics, due
to factors such as API response time, we feel that they still represent
meaningful proxies because they indicate the extent to which the tools are
exploring the API and successfully identifying faults.

Table I shows these metrics for ten different services: Features Service,
Language Tool, NCS, REST Countries, SCS, Genome Nexus, Person Controller, User
Management, Market Service, and Project Tracking. For each service, the table
lists the number of operations covered and the number of requests made under
the categories 2xx&500 (sum of 2xx code and 500 status code), 2xx, and 500,
for each of the four tools. In the final row, the table presents the average
number of operations covered and requests made by each tool across all the
tested services.

In a given testing time budget of one hour, arat-rl generated more valid and
fault-inducing requests, resulting in more exploration of the testing search
space. Specifically, arat-rl generated 60,132 valid and fault-inducing
requests on average, which is 52.01% more than Morest (39,595 requests),
40.79% more than EvoMaster (42,710 requests), and 1222% more than RESTler
(4,550 requests).

This difference in the number of requests can be attributed to arat-rl’s
approach of processing only a sample of key-value pairs from the response,
rather than the entire response. By focusing on sampling key-value pairs,
arat-rl efficiently identifies potential areas of improvement, contributing to
a more effective REST API testing process.

Moreover, arat-rl covered more operations on average (18 operations) compared
to Morest (15.6 operations), EvoMaster (14.5 operations), and RESTler (4.7
operations). This indicates that arat-rl efficiently generates more requests
in a given time budget, which leads to covering more operations within the
API, contributing to a more comprehensive testing process.

In Given a one-hour testing time budget, arat-rl outperforms Morest,
EvoMaster, and RESTler by generating generates 52.01%, 40.79%, and 1222% more
valid and fault-inducing requests respectively, and covering than Morest,
EvoMaster, and RESTler, respectively. Additionally, it covers 15.38%, 24.14%,
and 282.98% more operations . than these tools.

###  IV-D RQ3: Fault-Detection Capability

Table II shows the presents the total number of faults found detected by each
tool in the selected RESTful services . As shown in Table II, across 10 runs
for the ten RESTful services in our benchmark. For clarity in discussion, we
provide the average faults detected per run in the text below. As indicated,
arat-rl has the highest exhibits the most remarkable fault detection
capability, with a total uncovering an average of 112.5 faults found across
the selected RESTful over the services. In comparison, Morest and EvoMaster
found detected an average of 32.7 and 31.9 faults, respectively, while RESTler
detected the lowest number of faults, with a total found the least, with an
average of 11.0 faults. arat-rl uncovered 9.2x, 2.5x, and 2.4x more bugs than
RESTler, EvoMaster, and Morest, respectively.

Comparing this data against the data on 500 response codes from Table I, we
can see that, although arat-rl generated 20.59% fewer 500 responses, it found
250% more faults than Morest. Compared to EvoMaster, arat-rl generated 7.06%
more 500 responses, but also detected 240% more faults. This indicates that
arat-rl is more efficient at discovering faults via the exploration of diverse
API states, whereas those tools tend to trigger the same failures more
frequently.

arat-rl’s superior fault detection capability is particularly evident in the
Language-Tool and Person-Controller services, where it detected 12.2 and 94.3
faults, respectively. These What makes this significant is that these services
have larger sets of parameters. Our strategy excelled in efficiently
prioritizing and testing various combinations of these parameters to reveal
faults. For example, Language-Tool’s main operation /check, which checks text
grammar, has 11 parameters. Similarly, Person-Controller’s main operation
/api/person, which creates/modifies person instances, has 8 parameters. In
contrast, the other services’ operations usually have three or fewer
parameters.

arat-rl intelligently tries various parameter combinations with a reward
system in Q-learning because we give negative rewards for the parameters in
the successfully requested ones. This ability to explore various parameter
combinations is a significant factor in revealing more bugs, especially in
services with a larger number of parameters. These results indicate that arat-
rl’s reinforcement-learning-based approach can effectively discover faults in
RESTful services, providing valuable feedback to developers for improving
software quality.

arat-rl exhibits a superior fault-detection capability, uncovering 9.2x, 2.5x,
and 2.4x more bugs than RESTler, EvoMaster, and Morest, respectively. This is
mainly attributed to its intelligent RL-based exploration of various parameter
combinations in services with a larger number of parameters.

TABLE III: Results of the ablation Study.

Branch Line Method Faults Detected ARAT-RL 36.25 58.47 59.42 112.10 ARAT-RL
(no prioritization) 28.70 (+26.3%) 53.27 (+9.8%) 55.51 0(+7%) 100.10 (+12%)
ARAT-RL (no feedback) 32.69 (+10.9%) 54.80 (+6.9%) 56.09 (+5.9%) 110.80
(+1.2%) ARAT-RL (no sampling) 34.10 0(+6.3%) 56.39 (+3.7%) 57.20 (+3.9%)
112.50 (-0.4%)

###  IV-E RQ4: Ablation Study

To address RQ4, we conducted an ablation study to assess the impact of the
main novel components of arat-rl on its performance. We compared the
performance of arat-rl to three variants: (1) arat-rl without prioritization,
(2) arat-rl without dynamic key-value construction from feedback, and (3)
arat-rl without sampling. The results are presented in Table III.

As illustrated in Table III, the removal of any component results in reduction
branch, line, and method coverage, as well as the number of found detected.
Eliminating the prioritization component leads to the most substantial decline
in performance, with branch, line, and method coverage decreasing to 28.70%,
53.27%, and 55.51%, respectively, and the number of found faults dropping to
100. This evidence highlights the critical role of the prioritization
mechanism in arat-rl’s effectiveness.

The absence of feedback and sampling components also negatively affects
performance. Without feedback, arat-rl’s branch, line, and method coverage
decreases to 32.69%, 54.80%, and 56.09%, respectively, and the number of found
faults is reduced to 110.80. Likewise, without sampling, branch, line, and
method coverage drops to 34.10%, 56.39%, and 57.20%, respectively, while the
number of found faults experiences a slight increase to 112.50, which may be
attributed to random variations.

These findings emphasize that each component of arat-rl is essential for its
overall effectiveness. The prioritization mechanism, feedback loop, and
sampling strategy work together to optimize the tool’s performance in terms of
code coverage and fault detection capabilities.

Each component of arat-rl–prioritization, feedback, and sampling—contributes
to arat-rl’s overall effectiveness. The prioritization mechanism, in
particular, plays a significant role in enhancing arat-rl’s performance in
code coverage achieved and faults detected.

###  IV-F Threats to Validity

In this section, we address potential threats to our study’s validity and the
steps taken to mitigate them. The internal validity is influenced by tool
implementations and configurations, as well as the selected RESTful services.
To minimize these threats, we used the latest tool versions, used default
options, and chose a diverse set of 10 services for a fair comparison against
state-of-the-art tools. Some testing tools might have randomness, but we
addressed this issue by running each tool 10 times and computing the average
results.

Our data collection process hinges on an automated script. Despite thorough
testing, there remains a possibility that the script could contain errors,
potentially affecting our results. To mitigate this risk, we conducted several
rounds of pilot testing on a representative subset of our services before
applying the script to the full study.

The external validity is affected by the limited number of RESTful services
tested, impacting the generalizability of our findings. We tried to ensure a
fair evaluation by selecting a diverse set of services, but future work should
test a larger and more diverse set. Construct validity concerns the metrics
and tool comparisons used. Metrics such as branch, line, and method coverage,
number of requests, and 500 status codes as faults, although commonly, may not
capture the test tools’ full quality. Additional metrics, such as mutation
scores, could provide a better understanding. Including more tools or
approaches in future studies would allow a more comprehensive evaluation of
our technique’s performance.

In addition, we measured efficiency by considering the number of meaningful
requests generated by the tools, including valid and fault-inducing ones, as
well as the number of operations each tool covered within a given time budget.
While these metrics give us some perspective on a tool’s performance, they do
not consider all possible factors. Other aspects, such as the response times
from the services, may also significantly impact overall efficiency.

##  V Related Work

In this section, we provide an overview of related work in automated REST API
testing, requirements based test case generation, and reinforcement learning
based test case generation.

Automated REST API testing: EvoMaster [arcuri2019restful] is a white-box
technique using technique that offers both white-box mode and black-box mode.
It uses evolutionary algorithms for test case generation, refining tests based
on fitness its fitness function and checking for 500 status codes. In
contrast, Other black-box techniques include various tools with different
strategies. RESTler [atlidakis2019restler] generates stateful test cases by
inferring producer-consumer dependencies and targets 500 internal server
failures. RestTestGen [Corradini2022] exploits data dependencies and uses
oracles for status codes and schema compliance. QuickREST
[karlsson2020quickrest] is a property-based technique with stateful testing,
checking non-500 status codes and schema compliance. RESTest
[martin2020restest] Schemathesis [zac2022schemathesis] is a tool designed for
detecting five types of oracles to check response compliance in OpenAPI or
GraphQL web APIs using property-based testing. RESTest [martin2021restest]
accounts for inter-parameter dependencies, producing nominal and faulty tests
with five types of oracles. Morest [liu2022morest] uses a dynamically updating
RESTful-service Property Graph for meaningful test case generation. RestCT
[wu2022combinatorial] employs Combinatorial Testing for RESTful API testing,
generating test cases based on Swagger specifications.

Open-source black-box tools like Schemathesis [Zac2021schemathesis], Dredd
[dredd], fuzz-lightyear [fuzz-lightyear], and Tcases [tcases] offer various
testing capabilities. Schemathesis generates requests from input
specifications, providing five types of oracles to check response compliance.
Dredd tests REST APIs by comparing responses with expected results, validating
status codes, headers, and body content. Using Swagger for stateful fuzzing,
fuzz-lightyear detects vulnerabilities in micro-service ecosystems, offers
customized test sequences, and alerts on unexpected successful attacks. Tcases
is a model-based tool that constructs an input space model from OpenAPI
specifications, generating test cases covering valid input dimensions and
checking response status codes for validation.

Requirements based test case generation: In requirements based testing,
notable works include ucsCNL [barros2011ucscnl], which uses controlled natural
language for use case specifications, and UML Collaboration Diagrams
[badri2004use]. Requirements by Contracts [nebut2003requirements] proposed a
custom language for functional requirements, while SCENT-Method
[ryser1999scenario] employed a scenario-based approach with statecharts. SDL-
based Test Generation [tahat2001requirement] transformed SDL requirements into
EFSMs, and RTCM [yue2015rtcm] introduced a natural language-based framework
with templates, rules, and keywords. These approaches typically deal with less
formal requirements with the goal of generating test cases as accurately as
possible according to the intended requirements. In contrast, arat-rl focuses
on more formally specified REST APIs, which provide a structured basis for
testing and effectively explore and adapt during the testing process to find
faults.

Reinforcement learning based test case generation: Several recent studies have
investigated the use of reinforcement learning in software testing, focusing
primarily on web applications and mobile apps. These challenges often arise
from hidden states, whereas in our approach, we have access to all states
through the API specification but face more constraints on operations,
parameters, and mapping values. Zheng et al.[zheng2021webrl] proposed an
automatic web client testing approach utilizing curiosity-driven reinforcement
learning. Pan et al.[pan2020androidrl] introduced a similar curiosity-driven
approach for testing Android applications. Koroglu et al.[koroglu2018qbe]
presented QBE, a Q-learning-based exploration method for Android apps. Mariani
et al.[mariani2021autoblacktest] proposed AutoBlackTest, an automatic black-
box testing approach for interactive applications. Adamo et
al.[adamo2018androidrl] developed a reinforcement learning-based technique
specifically for Android GUI testing. Vuong and Takada[vuong2018androidrl]
also applied reinforcement learning to automated testing of Android apps.
Köroğlu and Sen [koroglu2020androidrl] presented a method for generating
functional tests from UI test scenarios using reinforcement learning for
Android applications.

##  VI Conclusion and Future Work

In this paper, we introduced arat-rl, a reinforcement learning-based approach
for the automated testing of REST APIs. We assessed its effectiveness,
efficiency, and fault-detection capability in comparison to state-of-the-art
tools such as Morest, EvoMaster, and RESTler. Our experiments demonstrated
arat-rl’s superior performance in terms of branch, line, and method coverage
achieved, requests generated, and faults detected. We also conducted an
ablation study, which highlighted the importance of arat-rl’s novel
features—prioritization, dynamic key-value construction based on response
data, and sampling from response data to speed up key-value construction—in
enhancing arat-rl’s performance.

In future work, we will improve arat-rl’s performance by addressing its
limitations in recognizing semantic constraints and generating inputs with
specific formatting requirements, such as email, address, or phone number, as
observed in our benchmark. We also plan to investigate ways to emulate complex
dependency relationships such as those we observed for Morest. We will also
study the impact of RL prioritization over time and investigate the effect of
using different pattern-matching approaches. Additionally, we plan to extend
our approach to support other types of web APIs, such as GraphQL or gRPC, by
adapting our algorithms and testing framework to accommodate their specific
requirements. Lastly, incorporating additional metrics and evaluation
techniques, such as mutation testing, will enable a more comprehensive
assessment of test case quality.

## Acknowledgments

We extend our gratitude to all our anonymous reviewers for their invaluable
feedback and to the developers of the testing tools we employed in our
empirical evaluation, namely EvoMasterBB, Morest, and RESTler, for making
their tools accessible. This research was partially supported by NSF, under
grant CCF-0725202, DARPA, under contract N66001-21-C-4024, DOE, under contract
DE-FOA-0002460, and gifts from Facebook, Google, IBM Research, and Microsoft
Research. This publication reflects the views only of the authors; the
sponsoring agencies cannot be held responsible for such views and any use
which may be made of the information contained therein.

## Data availability

The artifact associated with this submission, which includes code, datasets,
and other relevant material, is available in our GitHub repository [artifact].
It can be used for reproducing has been designed to reproduce the experiments
presented in the paper and facilitating to aid in further research in this
areadomain. While we have archived the submission version of our artifact on
Zenodo [zenodo], we strongly recommend visiting our GitHub repository for the
most recent updates, as we continually enhance and refine our tool.


# Language Modeling using LMUs:
10x Better Data Efficiency or Improved
Scaling Compared to Transformers

Narsimha Chilkuri, Eric Hunsberger, Aaron Voelker, Gurshaant Malik & Chris
Eliasmith
Applied Brain Research
Waterloo, Canada
<EMAIL_ADDRESS>

###### Abstract

Recent studies have demonstrated that the performance of transformers on the
task of language modeling obeys a power-law relationship with model size over
six orders of magnitude. While transformers exhibit impressive scaling, their
performance hinges on processing large amounts of data, and their
computational and memory requirements grow quadratically with sequence length.
Motivated by these considerations, we construct a Legendre Memory Unit based
model that introduces a general prior for sequence processing and exhibits an
$O(n)$ and $O(n\ln n)$ (or better) dependency for memory and computation
respectively. Over three orders of magnitude, we show that our new
architecture attains the same accuracy as transformers with 10x fewer tokens.
We also show that for the same amount of training our model improves the loss
over transformers about as much as transformers improve over LSTMs.
Additionally, we demonstrate that adding global self-attention complements our
architecture and the augmented model improves performance even further.

##  1 Introduction

Self-attention architectures such as the transformer (Vaswani et al., 2017)
have been extremely successful in dealing with sequential data and have come
to replace LSTMs and other RNN-based methods, especially in the domain of
Natural Language Processing (Radford et al., 2018; 2019; Devlin et al., 2018).
Transformers facilitate parallelization within training examples, and this
allows them to fully leverage hardware accelerators such as GPUs, making
training on datasets as large as 750GB feasible (Raffel et al., 2019; Gao et
al., 2020). In addition to parallelizing training, self-attention
architectures are much better at handling long-range dependencies relative to
traditional RNNs, and this allows them to take advantage of context much
longer than the $\sim 100$-$1000$ tokens typical of RNNs, like the LSTM
(Voelker & Eliasmith, 2018; Kaplan et al., 2020).

Transformers are general-purpose architectures that can be applied to a wide
variety of problems and modalities. One of the drawbacks of such generality is
the lack of _a priori_ structure, which makes them heavily reliant on large
quantities of data to achieve good results. Another limiting factor is that
self-attention involves the computation of the attention matrix,
${\bm{Q}}{\bm{K}}^{T}$, which is of shape $n\times n$, with $n$ being the
sequence length. Thus, transformer’s compute and memory requirements grow
quadratically with respect to the sequence length.

In this work, we explore a way of addressing these limitations. We base our
approach on the non-parametric Linear Time-Invariant (LTI) component of the
Legendre Memory Unit (Voelker et al., 2019). This LTI system, which we refer
to it here as the LMU,111We refer to the LTI system as the LMU as it is the
distinguishing layer of our architectures. The original LMU was defined to
include the LTI system as well as a subsequent nonlinear layer. We have
essentially expanded this nonlinear layer to include a variety of familiar
layers. projects a sliding window of the input sequence onto Legendre
polynomials to provide a temporal representation and compression of the input
signal. Although the LTI system is an RNN, it has been shown to support both
sequential and parallel processing of sequences (Chilkuri & Eliasmith, 2021).
Another crucial component of our model is a modified attention mechanism that
operates only on the output of the LMU at each time step, and not _across_
time steps. The LMU state at each step captures information about the past
tokens, and hence we call this attention mechanism implicit self-attention.

Recent work (Kaplan et al., 2020; Gao et al., 2020) has explored the scaling
properties of transformers in the context of autoregressive language
modelling. They show that the performance of transformers scales as a power-
law with model size (excluding embedding parameters), dataset size and the
amount of compute used for training, when not bottlenecked by the other two.
Inspired by these results, we validate our method by studying the scaling
properties of our models. To that end, we start by reviewing some necessary
background in Section 2, and then present the architectural details of our
model in Section 4. In Section 5, we present our experiments with models
containing up to 10 million parameters (or 1 million non-embedding
parameters), which demonstrate a smooth power-law relationship with respect to
the model size, and a loss that scales better than transformers. When the loss
is matched to that of transformers, 10x fewer tokens are required.

##  2 Background: The Legendre Memory Unit

Figure 1: (left) Illustration of the standard sequential implementation for
computing the hidden state ${\bm{m}}_{4}$. The input $x_{1}$ is fed into the
linear recurrent unit to compute the hidden state ${\bm{m}}_{1}$, which, along
with $x_{2}$, is then used to compute the next hidden state, and so on.
(right) Illustration of the time-domain parallel implementation for computing
the hidden state ${\bm{m}}_{4}$. The inputs $x_{1}$-$x_{4}$ are used to
compute the intermediate multiplies, which are then added together to compute
the hidden state ${\bm{m}}_{4}$, all without the need for any sequential
operations.

The non-parametric LTI component of the LMU (Voelker & Eliasmith, 2018) is the
focus of our study. This LTI system is mathematically derived to project a
sliding window of length $\theta$ of the input sequence onto $q$ Legendre
polynomials. Thus, the two main hyper-parameters to choose when using it are
$\theta$ and $q$. Naturally, if we desire to capture the fine-grained details
of the input sequence, a large $\theta$, which sets the length of the sliding
window, should be accompanied by a large $q$, the number of Legendre
polynomials used in approximating the input. We present the state-update
equations of the LTI component of the LMU below,222Focusing on one-dimensional
inputs for now.

$\displaystyle{\bm{m}}_{t}=\bar{{\bm{A}}}{\bm{m}}_{t-1}+\bar{{\bm{B}}}x_{t},$
(1)

where the $\bar{{\bm{A}}}=e^{{\bm{A}}}\in\mathbb{R}^{q\times q}$ and
$\bar{{\bm{B}}}={\bm{A}}^{-1}(e^{{\bm{A}}}-{\bm{I}}){\bm{B}}\in\mathbb{R}^{q\times
1}$ matrices are frozen during training, with ${\bm{A}}$ and ${\bm{B}}$
defined as follows:

$\displaystyle A_{i,j}=\frac{(2i+1)}{\theta}\begin{cases}-1\qquad i<j\\\
(-1)^{i-j+1}\quad i\geq j\end{cases},$ (2) $\displaystyle
B_{i}=\frac{(2i+1)(-1)^{i}}{\theta}.$ (3)

Crucially, when needed, the LTI equation (1) above can be evaluated as a
convolution, in parallel, as shown below (Chilkuri & Eliasmith, 2021):

$\displaystyle{\bm{m}}_{t}=\sum_{j=1}^{t}\bar{{\bm{A}}}^{t-j}\bar{{\bm{B}}}x_{j},$
(4)

or equivalently, defining

$\displaystyle{\bm{H}}$
$\displaystyle=\begin{bmatrix}\bar{{\bm{A}}}^{0}\bar{{\bm{B}}}&\bar{{\bm{A}}}\bar{{\bm{B}}}&\ldots\end{bmatrix}\in\mathbb{R}^{q\times
n},$ (5) $\displaystyle{\bm{x}}$
$\displaystyle=\begin{bmatrix}x_{n}&x_{n-1}&x_{n-2}&\ldots&x_{1}\end{bmatrix}^{T}\in\mathbb{R}^{n\times
1},$ (6)

the above convolution equation can be written as an element-wise
multiplication in the Fourier space as follows:

$\displaystyle{\bm{m}}_{1:n}=\mathcal{F}^{-1}\\{\mathcal{F}\\{{\bm{H}}\\}\cdot\mathcal{F}\\{{\bm{x}}\\}\\}.$
(7)

##  3 Related Work

Our work falls under the broad category of combining convolution with self-
attention. Recent work has demonstrated that combining these two modules can
be beneficial for language modeling, speech and other NLP applications (Yang
et al., 2019; Wu et al., 2020; Gulati et al., 2020). For instance, Wu et al.
(2020) introduce the Long-short Range Attention module that features a two-
branch design, with the self-attention branch learning global interactions and
the convolutional branch learning local interactions. Gulati et al. (2020) on
the other hand propose a model that uses a single branch architecture, with
the convolutional block connected directly to the attention block, and
demonstrate improved performance on the task of speech recognition.

While our work is mathematically related to the models mentioned above, it
differs from the previous approaches in three crucial ways: first, we do not
learn the convolutional weights, but instead work with the analytically
defined weights of the LMU; second, we introduce the novel implicit self-
attention module that works on the hidden states of the LMU at each time-step;
finally, we systematically study the scaling properties of our model in the
context of language modeling.

Our model is also related to the many studies on reducing the quadratic
computational and memory complexity of self-attention (Tay et al., 2020). Out
of the several ways of improving efficiency, our work shares some similarity
with the sliding window attention approach (Beltagy et al., 2020; Zaheer et
al., 2020). While these methods use a form of masking of the full self-
attention matrix to constraint attention to the $k$-nearest tokens, our
technique relies on the LMU to compute optimal compressed representations of
sliding windows of input vectors, each of which is then used as input to the
implicit attention module.

Figure 2: The LMU and implicit self-attention architecture along with output
dimensions. In the illustration, $n$ refers to the sequence length, $q$ is the
order and $q^{\prime}$ is the reduced order, and $d$ is the embedding
dimension. Normalization layers and skip connections are not shown. One
variant uses the FFN component right after the input, and the other variant
uses global attention.

##  4 Architecture

In this paper, we modify the architecture presented in Chilkuri & Eliasmith
(2021) to better deal with the task of language modelling, especially when the
sequences are long and high-dimensional. Starting with the base LMU model, we
describe the major components of our model below. An illustration of our
architecture is presented in Figure 2.

#### Memory Matrix

Consider an input sequence
$\\{{\bm{x}}_{1},{\bm{x}}_{2},\ldots,{\bm{x}}_{n}\\}$ of length $n$ where the
individual elements are of dimension ${\bm{x}}_{i}\in\mathbb{R}^{d}$. The most
natural way of using an LMU-based model on such sequences is to set $\theta=n$
and use an appropriately large $q$. The downside of using the LMU in such a
manner, however, is that the hidden state of the LMU scales with input
dimension and order: ${\bm{m}}\in\mathbb{R}^{dq}$. For example, in Section 5,
we deal with $n=1024$ and $d$ that is as large as $204$. Even when using a
small $q$ of 100, we may end up with hidden states that are as large as
$\mathbb{R}^{20k}$, which is highly undesirable.

One way around this issue is to take inspiration from standard convolutional
network architectures (CNNs) and work with a smaller sliding window,
$\theta\approx 10$, which in turn allows us to use a small LMU order,
$q\approx 5$, thus taming the hidden state dimension (see Chilkuri & Eliasmith
(2021) for more details). However, enforcing a small sliding window prompts
the use of many stacked LMU layers in order to increase the ‘receptive field’
(or the effective $\theta$) of the model, very similar to how CNNs often use
small kernels with many convolutional layers. Unsurprisingly, such an approach
results in very deep models, which can be problematic to train.

Here, we choose to follow the middle path, i.e, $0\ll q\ll n$, but instead of
working directly with the potentially high-dimensional hidden state
${\bm{m}}$, we disentangle the input dimensions from the order. In other
words, we perform our operations on the matrix ${\bm{M}}\in\mathbb{R}^{d\times
q}$ and not on the vector ${\bm{m}}\in\mathbb{R}^{dq}$. This is beneficial
because while a fully-connected layer needs $d^{2}\cdot q^{2}$ parameters to
process the ${\bm{m}}$ vector, processing the matrix ${\bm{M}}$ with the help
of two fully connected layers, one for the rows and one for the columns,
requires only $d^{2}+q^{2}$ parameters.

#### Implicit Self-Attention

The main feature distinguishing our architecture from past work is the LMU. As
mentioned above, the output of the LMU layer compresses past history at each
time-step, which is captured by the ${\bm{M}}\in\mathbb{R}^{q\times d}$
matrix. Our modified self-attention acts on this matrix to combine temporal
information. As a result, self-attention does not act directly on the input
sequence, but rather on a compressed version of the input, which is available
at each moment in time and covers a window, determined by $\theta$. Ignoring
the bias vectors, normalization layers, and skip-connections, we first execute
the following sets of operations simultaneously:

$\displaystyle{\bm{Q}}$ $\displaystyle=\sigma({\bm{L}}_{1}{\bm{M}})$
$\displaystyle{\bm{K}}$ $\displaystyle=\sigma({\bm{L}}_{2}{\bm{M}})$
$\displaystyle{\bm{V}}$ $\displaystyle=\sigma({\bm{L}}_{3}{\bm{M}}),$ (8)

where ${\bm{L}}_{i}\in\mathbb{R}^{q^{\prime}\times q}$, $\sigma$ is a non-
linearity such as gelu, and the matrices ${\bm{Q}}$, ${\bm{K}}$, ${\bm{V}}$
are all in $\mathbb{R}^{q^{\prime}\times q}$. In our experiments, we have
found the setting $q^{\prime}=q/10$ to work well, and thus our attention
matrices contain far fewer elements than $n^{2}$. For example, in our largest
model we set $q=250$, resulting in $q^{\prime}=25$.

Following the computation of ${\bm{Q}}$, ${\bm{K}}$, and ${\bm{V}}$ two
additional computations result in a $d$-dimensional vector ${\bm{m}}$:

$\displaystyle{\bm{M}}^{\prime}=\text{softmax}({\bm{Q}}{\bm{K}}^{T}){\bm{V}},$
(9) $\displaystyle{\bm{m}}={\bm{p}}{\bm{M}}^{\prime},$ (10)

where ${\bm{p}}\in\mathbb{R}^{1\times q^{\prime}}$.

In practice, equation (8) can be made far more efficient computationally,
especially during inference, by following the recipe outlined in Section A.1.

#### Feedforward Network

We have also found it beneficial to include a feedforward network (FFN)
(Vaswani et al., 2017) before the LMU and after the implicit self-attention
block. The FFN component is defined below:

$\displaystyle{\bm{y}}({\bm{x}})=\sigma({\bm{x}}{\bm{W}}_{1}+{\bm{b}}_{1}){\bm{W}}_{2}+{\bm{b}}_{2},$
(11)

where ${\bm{W}}_{1}\in\mathbb{R}^{d\times d^{\prime}}$,
${\bm{W}}_{2}\in\mathbb{R}^{d^{\prime}\times d}$,
${\bm{b}}_{1}\in\mathbb{R}^{d^{\prime}}$ and ${\bm{b}}_{2}\in\mathbb{R}^{d}$.

#### Global Self-Attention

We also explore the use of a global self-attention block in place of the FFN
component before the LMU. We find that introducing this layer, while
computationally expensive, further improves the cross-entropy score. We
believe that the improvement comes from the fact the LMU and self-attention
are complementary: the LMU’s implicit self-attention is good at prediction
with limited context, and the traditional self-attention captures long-range
dependencies. We wish to explore the use of efficient self-attention blocks –
which scale better than $O(n^{2})$ – in the future.

Table 1: Memory and computation scaling with sequence length during training and inference. Layer | Memory | Compute
---|---|---
Full Attention | $O(n^{2})$ | $O(n^{2})$
LMU (Parallel) | $O(n)$ | $O(n\ln n)$
LMU (Recurrent) | $O(1)$ | $O(n)$

#### Complexity

As shown in Table 1, our architecture employing the parallel LMU along with
implicit self-attention has memory requirements that are linear with respect
to the sequence length, and it has computational requirements that also grow
as $n\ln n$. When we use the recurrent version of the LMU, the memory and
compute requirements scale as $O(1)$ and $O(n)$ respectively. Recurrent
implementations, while not as efficient on GPU architectures for large batch
sizes, are ideally suited to edge applications, especially with efficient
hardware support. Notably, if we add global attention to our model, then both
compute and memory become quadratic, just like the original transformer.

Table 2: Parameter counts and compute (forward pass) for one layer of the network, per token. The first row indicates the number of FLOPs when following the implementation in Section A.1. Additional background information regarding various implementations of the LMU is provided in Appendix A.2. Operation | Parameters | FLOPs per Token
---|---|---
LMU + ${\bm{Q}}$ \+ ${\bm{K}}$ \+ ${\bm{V}}$ | $3qq^{\prime}$ | $3d\left[5(q^{\prime}+1)(\log_{2}n+1)+6q^{\prime}\right]+6qq^{\prime}$
${\bm{Q}}{\bm{K}}^{T}$ | – | $2dq^{\prime 2}$
${\bm{M}}^{\prime}$ | – | $2dq^{\prime 2}+dq^{\prime}$
${\bm{m}}$ | $q^{\prime}$ | $2dq^{\prime}$
FFN | $2dd^{\prime}$ | $4dd^{\prime}$

We also list the number of floating point operations per-token for the
(parallel) LMU model in Table 2.

##  5 Experiments

#### Dataset

We train our models on the publicly available internet text dataset called
OpenWebText2 (OWT2).333https://www.eleuther.ai/projects/open-web-text2/
Similar to the WebText2 dataset (Radford et al., 2019), OWT2 was created using
URLs extracted from Reddit submissions with a minimum score of 3 as a proxy
for quality, and it consists of Reddit submissions from 2005 up until April
2020. After additional filtering, applying the pre-trained GPT2 tokenizer
containing 50257 tokens (Radford et al., 2019) results in approximately 8
billion tokens in total. We use a train/validation/test split of 96/3/1%.

#### Training Details

We train our models in an autoregressive manner using the Adam optimizer with
all the default settings. We use sequences containing 1024 tokens, and in
cases where the documents have fewer than 1024 tokens, we pack multiple
documents into the same sequence, separated by the <|endofsequence|> token. We
use a learning rate schedule with a linear warmup and cosine decay to zero,
while also reducing the learning rate on plateau. We chose to train our models
to process a maximum of $13$ billion tokens; at a batch size of $512$, this
amounts to training for $25000$ steps. Additionally, one of the important
considerations when doing NLP experiments is the size of the embedding
vectors, $d$. In this work, in order to facilitate a fair comparison to the
transformer models (Kaplan et al., 2020), we use the following rule to
determine $d$:

$d=\sqrt{\frac{N}{24}},\\\ $

where $N$ represents the number of non-embedding (and trainable) parameters.

Figure 3: Cross-entropy scores in nats, averaged across all the tokens in the
sequence. Transformers and LSTMs fits are from Kaplan et al. (2020). Our
models perform better than Transformers and LSTM models up to 1 million non-
embedding parameters.

#### Results

Here we present the results of our experiments that use the LMU architecture
described above with the non-embedding (and trainable) parameters ranging from
55k to 1M (i.e., from 2.5M to 10M, if we include all parameters). The cross-
entropy results are presented in Figure 3. For the transformer models, we list
the scores obtained by using the following power-law fit,

$\displaystyle\text{Transformer}(N,S)=\left(\frac{N}{6.5\cdot
10^{13}}\right)^{-0.077}+\left(\frac{S}{S_{min}(S)}\right)^{-0.76},$ (12)

where $N$ refers to the number of non-embedding parameters and $S$ is the
total number of training steps (set to $25000$ at batch size of 512, or
equivalent). The power-law is obtained from Kaplan et al. (2020); the fits
were generated by training several transformer models, ranging in size from
768 to 1.5 billion non-embedding parameters, on OpenAI’s WebText2 dataset. In
addition, we compare against the power-law for LSTM models, also from Kaplan
et al. (2020), that use 10x more training steps than the transformer and LMU
models:

$\text{LSTM}(N)=\left(\frac{N}{7.45\cdot 10^{14}}\right)^{-0.071}.$

Similar to the transformer and LSTM models, we notice that the performance of
our models depends strongly on scale, with the loss of the LMU model
exhibiting the following power-law relationship with respect to $N$:

$\text{LMU}(N)=\left(\frac{N}{1.95\cdot 10^{14}}\right)^{-0.072}.$

The LMU model with global self-attention scales as follows:

$\text{LMU}_{G}(N)=\left(\frac{N}{3.80\cdot 10^{14}}\right)^{-0.069}.$

It remains to be seen whether our models retain this performance advantage
when $N\gg 10^{6}$.

The utility of adding global attention becomes clear when we observe the per-
token loss plots of the three models. In Figure 4 (right), we notice that
although the LMU’s per-token loss is better overall than the transformer’s, it
flattens relatively early, around 100 tokens, suggesting that implicit
attention alone does not capture long context. The LMU and Attention model, on
the other hand, continues improving with increasing context, similar to the
transformer.

Figure 4: (left) Comparison of per-token loss of an LMU model (with global
attention) and a transformer model. (right) Per-token loss of an LMU model
(without global attention) alongside the transformer’s loss.

It is also interesting to note that we can compare LMUs and transformers by
determining approximately how much training is required for a transformer to
match LMU loss. Figure 5 demonstrates that our models, trained on $13$ billion
tokens, have similar scaling to transformers trained on $130$ billion tokens.
Consequently, the LMU architecture is 10x more data efficient. In addition,
our LMU models with global attention continue to outperform transformer models
trained on 10x more tokens (or with 10x more training steps) by a significant
margin.

##  6 Discussion

Semi-supervised learning has proven to be a very effective technique in
Natural Language Processing. General purpose language models pre-trained on a
large corpus of text in an unsupervised manner and fine-tuned on tasks such as
sentiment analysis and question answering often outperform highly task-
specific architectures that receive no pre-training. The performance of models
on the task of language modelling is thus a crucial metric that is indicative
of the downstream performance of such models on a slew of tasks involving
natural language.

While the performance of our models on the task of language modelling suggests
an interesting trend, due to the scale of our experiments however, we do not
consider this to be definitive evidence for the superiority of our LMU
architecture. As a result, a core objective for future research is to show
that the observed trends hold over 6 orders of magnitude, as demonstrated by
Kaplan et al. (2020) for transformers.

Figure 5: Approximately matching the loss between transformers and LMUs
requires 10x more training for the transformer. The LMU and Attention model
continues to significantly outperform transformers with 10x less training.

##  7 Conclusion

In this work, we employ the Legendre Memory to construct a model that is well-
suited to handling long sequences with high-dimensional elements. We apply our
architectures to model natural language in the infinite data limit,
demonstrating that: (1) like the established architectures such as
transformers and LSTMS, our models also exhibit a power-law relationship
between the cross-entropy loss and model size; and (2) at the small-medium
scale, our models have better scaling properties than other approaches.

## References

  * Beltagy et al. (2020) Iz Beltagy, Matthew E Peters, and Arman Cohan.  Longformer: The long-document transformer.  _arXiv preprint arXiv:2004.05150_ , 2020.
  * Chilkuri & Eliasmith (2021) Narsimha Reddy Chilkuri and Chris Eliasmith.  Parallelizing legendre memory unit training.  In Marina Meila and Tong Zhang (eds.), _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pp. 1898–1907. PMLR, 18–24 Jul 2021.  URL http://proceedings.mlr.press/v139/chilkuri21a.html.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Gao et al. (2020) Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, et al.  The pile: An 800gb dataset of diverse text for language modeling.  _arXiv preprint arXiv:2101.00027_ , 2020.
  * Gulati et al. (2020) Anmol Gulati, James Qin, Chung-Cheng Chiu, Niki Parmar, Yu Zhang, Jiahui Yu, Wei Han, Shibo Wang, Zhengdong Zhang, Yonghui Wu, et al.  Conformer: Convolution-augmented transformer for speech recognition.  _arXiv preprint arXiv:2005.08100_ , 2020.
  * Johnson & Frigo (2012) Steven G. Johnson and Matteo Frigo.  Implementing FFTs in Practice.  In C. Sidney Burrus (ed.), _Fast Fourier Transforms_. 2012.  URL https://cnx.org/contents/ulXtQbN7@15/Implementing-FFTs-in-Practice.
  * Kaplan et al. (2020) Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei.  Scaling laws for neural language models.  _arXiv preprint arXiv:2001.08361_ , 2020.
  * Radford et al. (2018) Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever.  Improving language understanding by generative pre-training.  2018\.
  * 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.
  * Raffel et al. (2019) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _arXiv preprint arXiv:1910.10683_ , 2019.
  * Tay et al. (2020) Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler.  Efficient transformers: A survey.  _arXiv preprint arXiv:2009.06732_ , 2020.
  * 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.  In _Advances in neural information processing systems_ , pp. 5998–6008, 2017.
  * Voelker et al. (2019) Aaron Voelker, Ivana Kajić, and Chris Eliasmith.  Legendre memory units: Continuous-time representation in recurrent neural networks.  In _Advances in Neural Information Processing Systems_ , pp. 15544–15553, 2019.
  * Voelker & Eliasmith (2018) Aaron R Voelker and Chris Eliasmith.  Improving spiking dynamical networks: Accurate delays, higher-order synapses, and time cells.  _Neural computation_ , 30(3):569–609, 2018.
  * Wu et al. (2020) Zhanghao Wu, Zhijian Liu, Ji Lin, Yujun Lin, and Song Han.  Lite transformer with long-short range attention.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=ByeMPlHKPH.
  * Yang et al. (2019) Baosong Yang, Longyue Wang, Derek Wong, Lidia S Chao, and Zhaopeng Tu.  Convolutional self-attention networks.  _arXiv preprint arXiv:1904.03107_ , 2019.
  * Zaheer et al. (2020) Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al.  Big bird: Transformers for longer sequences.  In _NeurIPS_ , 2020.

##  Appendix A Appendix

###  A.1 Reduced-order LMU

When implementing the LMU in these models, we use a parallelizable approach
that computes the impulse responses of the LMU (which are essentially the
Legendre polynomials), and convolve those with the input sequences (either
using raw convolution or FFT-based convolution). Specifically, given the
$q$-dimensional impulse response ${\bm{H}}$, we compute the LMU memory state
${\bm{M}}\in\mathbb{R}^{d\times q}$ at the current time as

$\displaystyle{\bm{M}}={\bm{X}}\ast{\bm{H}}$ (13)

where ${\bm{X}}\in\mathbb{R}^{n\times d}$ is the time-series of previous
inputs to the LMU, ${\bm{H}}\in\mathbb{R}^{q\times n}$ is the LMU impulse
response, and $\ast$ is the convolution operator.

We have found that our models are most expressive when using a value of $q$
that is significantly larger than $q^{\prime}$, as this allows the LMU to
”remember” the time history with high fidelity, but only use the parts of the
history that are most relevant. Rather than explicitly computing the full LMU
output ${\bm{M}}$ and then reducing this with the ${\bm{L}}_{i}$
transformations as per equation (8), we propose applying the ${\bm{L}}_{i}$
transformations directly to the impulse responses

$\displaystyle\tilde{\bm{H}}_{i}={\bm{L}}_{i}{\bm{H}}$ (14)

and then applying these individually to directly compute ${\bm{Q}}$,
${\bm{K}}$, and ${\bm{V}}$:

$\displaystyle{\bm{Q}}$ $\displaystyle=\sigma({\bm{X}}\ast\tilde{\bm{H}}_{1})$
$\displaystyle{\bm{K}}$ $\displaystyle=\sigma({\bm{X}}\ast\tilde{\bm{H}}_{2})$
$\displaystyle{\bm{V}}$ $\displaystyle=\sigma({\bm{X}}\ast\tilde{\bm{H}}_{3})$
(15)

This is mathematically equivalent to the formulation expressed previously, but
uses significantly fewer operations per token, particularly when $q$ is large
or the ratio of $q^{\prime}$ to $q$ is small:

$\mathfrak{L}_{\mathrm{LMU+Q+K+V}}=3[d\mathfrak{L}_{\mathrm{FFT}}(q^{\prime})+2qq^{\prime}]$
(16)

where $\mathfrak{L}_{\mathrm{FFT}}(q^{\prime})$ is given by Equation 19 with
$q\to q^{\prime}$.

###  A.2 LMU Implementation Trade-offs

The LMU itself is a LTI dynamical system, with a number of options for
implementation. One implementation is to perform the update each timestep in
state-space, using state-space matrices discretized using the zero-order hold
(ZOH) method for high accuracy. The operations required (per LMU layer and per
token) are the multiplications by the $\bar{{\bm{A}}}$ and $\bar{{\bm{B}}}$
matrices (with number of elements $q^{2}$ and $q$, respectively):

$\mathfrak{L}_{\mathrm{SS}}=2d(q^{2}+q).$ (17)

Another option is to use an explicit Runge-Kutta method to update the LMU
states. By taking advantage of the unique structure of the ${\bm{A}}$ and
${\bm{B}}$ matrices (Equations 2 and 3), this implementation is able to reduce
the complexity from $O(q^{2})$ to $O(q)$, requiring the following approximate
number of operations:

$\mathfrak{L}_{\mathrm{RK}}=6rdq.$ (18)

where $r$ is the order of the Runge-Kutta method. The disadvantage to this
option is that it does not implement the exact same dynamics as the ideal
system discretized with ZOH, and is less numerically stable particularly for
higher values of $q$.

A disadvantage to both these options is that they must update LMU states
sequentially, which is particularly ill-suited when using highly parallel
hardware (e.g. GPU) with a long sequence of inputs available. In this case, we
can take the impulse response of the LMU system (discretized with ZOH), and
convolve it with an input in the FFT domain. This implements the exact same
dynamics as the ZOH state-space system, but with a complexity that is $O(q)$
rather than $O(q^{2})$:

$\displaystyle\mathfrak{L}_{\mathrm{FFT}}$
$\displaystyle=\frac{d}{n}\left[C(2n)+c_{m}qn+qC(2n)\right]$
$\displaystyle=d\left[5(\log_{2}n+1)(q+1)+6q\right].$ (19)

Here, $C(n)$ is the number of FLOPs for a radix-2 Cooley-Tukey FFT
implementation (Johnson & Frigo, 2012):

$\displaystyle C(n)$
$\displaystyle=2C\left(\frac{n}{2}\right)+\frac{n}{2}(c_{m}+2c_{a})$ (20)
$\displaystyle=5n\log_{2}n$ (21)

where $c_{m}=6$ is the number of FLOPs per complex multiply, and $c_{a}$ is
the number of FLOPs per complex addition. For our standard sequence length of
$n=1024$, this results in:

$\mathfrak{L}_{\mathrm{FFT-1024}}=d(61q+55).$ (22)