# Cognitive Modeling of Semantic Fluency Using Transformers

Animesh Nighojkar, Anna Khlyzova, John Licato
Advancing Machine and Human Reasoning (AMHR) Lab
Department of Computer Science and Engineering
University of South Florida, Tampa, USA
(anighojkar, annakhlyzova<EMAIL_ADDRESS>
###### Abstract

Can deep language models be explanatory models of human cognition? If so, what
are their limits? In order to explore this question, we propose an approach
called hyperparameter hypothesization that uses predictive hyperparameter
tuning in order to find individuating descriptors of cognitive-behavioral
profiles. We take the first step in this approach by predicting human
performance in the semantic fluency task (SFT), a well-studied task in
cognitive science that has never before been modeled using transformer-based
language models (TLMs). In our task setup, we compare several approaches to
predicting which word an individual performing SFT will utter next. We report
preliminary evidence suggesting that, despite obvious implementational
differences in how people and TLMs learn and use language, TLMs can be used to
identify individual differences in human fluency task behaviors better than
existing computational models, and may offer insights into human memory
retrieval strategies—cognitive process not typically considered to be the
kinds of things TLMs can model. Finally, we discuss the implications of this
work for cognitive modeling of knowledge representations.

##  1 Introduction

Two of the most important ideas underpinning contemporary cognitive
science–and the closely related AI subfield of computational cognitive
modeling–are the suppositions that the human mind uses cognitive structures
and that progress in understanding the mind can come from modeling those
structures and the algorithms which operate on them. The semantic fluency task
(SFT), sometimes called the verbal fluency task Welsh et al. (1991), is
commonly employed in service of those goals. In SFT, participants name as many
items belonging to a particular semantic category (animals, fruits, etc.) as
they can in a fixed amount of time (typically 40-180 seconds). Despite this
task’s simplicity, the lists generated by participants (which we call semantic
fluency lists or SFLs) offer insights into the structure of human knowledge
and the heuristics used for memory retrieval. For example, words sharing
semantic features tend to group in clusters, and there is often a temporal
delay before a participant switches from one cluster to another.

Multiple approaches to computationally modeling behaviors in SFT have been
proposed Hills et al. (2012); Abbott et al. (2015); Zemla et al. (2016); Zemla
and Austerweil (2017); Avery and Jones (2018), most relying on graph-based
representations in which words are represented as nodes, and edges correspond
to some meaningful semantic relationship between the nodes. However, to date,
no work has explored whether transformer-based language models (TLMs) can be
any better at modeling the generation of SFLs. And there are multiple reasons,
at least from an exploratory perspective, to suspect TLMs might do well in
this regard, e.g.: (1) a large body of literature demonstrates why semantic
memory can not be sufficiently represented purely by fixed associative links
between lexical nodes—at minimum, representations must allow for dynamic role
binding, hierarchical (or otherwise unidirectional) activations, and enough
richness to carry out structure-sensitive similarity assessments Holyoak and
Hummel (2000); Sun (2002); (2) TLMs perform unexpectedly well on human-
oriented linguistic benchmarks Wang et al. (2019), and they are typically pre-
trained using a lengthy process designed to embed deep semantic knowledge,
resulting in a dense encoding of semantic relationships Cui et al. (2020); (3)
The pre-training process often proceeds by optimizing LMs to perform well on
the MLM (masked language modeling) task, which shares more than a passing
resemblance to the kind of word prediction that some researchers believe
children are performing Gambi et al. (2020); and (4) TLMs tend to outperform
other approaches in recent work modeling human reading times, eye-tracking
data, and others Schrimpf et al. (2020).

Considered altogether, these reasons are sufficient to motivate an initial
exploration into TLM-based semantic fluency modeling. Our novel contributions
include:

  * •

We are the first, to our knowledge, to generate and model SFLs using TLMs; we
use RoBERTa-Large, DistilBERT, and miniBERTa-med-small in this paper to
further the state-of-the-art on modeling SFLs. Generally, our models
significantly outperform more traditional, semantic network-based approaches.

  * •

We design two adaptive approaches that predict the next SFL item as they learn
from the previous items and turn out to be superior to other non-adaptive
approaches. These adaptive approaches, we believe, can serve as baselines
against which to compare future computational cognitive models.

  * •

In a broader sense, we argue and demonstrate that TLMs, despite being pre-
trained using techniques and datasets very different than those human beings
use, can be powerful tools for studying human cognition, knowledge
representation, and memory retrieval. This is a first step in a computational
cognitive modeling strategy that we call hyperparameter hypothesization
(§1.1).

Any performance on modeling SFLs discussed in this paper is for a pre-trained
model with no fine-tuning on the SFT. We do this because the objective of this
work is not to learn how to perform the SFT in the most precise way; it is to
model human SFLs in an attempt to use the best performing hyperparameters to
learn something about human cognitive traits.

###  1.1 Deep Learning as Cognitive Model

Cognitive Science has long benefited from computational cognitive models
(CMs), which are computational implementations of cognitive processes, at
various levels of abstraction, created typically in order to test theoretical
claims Sun (2008). Furthermore, because carrying out empirical studies with
people can involve difficult logistics, the existence of myriad confounding
variables, and prohibitive costs, the use of well-designed CMs can save
psychologists an immense amount of time and resources, e.g. by making it
easier to test hypotheses about cognitive processes with CMs prior to
empirical work. However, there are fundamental hardware and implementational
differences between human brains and silicon-based electronics, raising the
question: to what extent can a CM support or refute a theory of human
cognition? Although there is a longstanding debate about to which degree the
algorithms used by a CM commits it to certain claims about the cognitive
phenomena it purports to model (e.g., see Jones and Love (2011); Marcus and
Davis (2012, 2015)), most agree that the level of abstraction the CM
represents does entail some ontological commitment Bricker (2016); Floridi
(2011),111A model that is ontologically committed tells us something about the
real-world object or process that it is meant to model, rather than simply to
match the data that the object or process outputs. much like any other
scientific theory can be said to model and explain something about the natural
world. In other words, if we want a CM to be able to teach us something about
the human mind, its design choices cannot be made arbitrarily because the way
the model works must have some correspondence to the cognitive process it
purports to model. How then can massive transformer-based language models,
that are trained on large datasets using algorithms and data structures that
appear fundamentally different from those used by people, tell us something
about human minds?

Our answer to this important question is brief: We propose a technique we call
hyperparameter hypothesization, the form of which goes as follows: If, for
certain values of hyperparameters $\mathcal{H}$: (1) a CM matches large
amounts of human data significantly better than other models; (2) the human
data matched ranges across a variety of tasks given values of $\mathcal{H}$;
and (3) all $h\in\mathcal{H}$ have functional roles in the CM that reasonably
align with functional roles known to exist in human cognition; then we can
reasonably use it to form a hypothesis about human cognition. For example,
suppose we have a TLM with a hyperparameter $w$, which restricts the amount of
information that the CM can consider simultaneously. We then find that certain
values of $w$ allow the CM to match human data on a cognitive task much better
than existing models (e.g., SFT). We may then find that a similar range of
values for $w$ allows the CM to match human data on other cognitive tasks as
well. This can allow us to reasonably hypothesize (but not yet definitively
conclude) that this range of values for $w$ corresponds to a similar range in
people—we might predict that it corresponds to the amount of working memory
that people typically have. This hypothesis can then be tested: we can observe
how our CM performs on values of $w$ lower than the optimal range and see
whether its resulting behaviors align with those of humans who are known to
have lower working memory sizes.

Although the above is only one example of how hyperparameter hypothesization
may work, its first step involves demonstrating that a certain type of CM can
indeed match human data significantly better than others. The remainder of
this paper restricts its focus to that, specifically on the semantic fluency
task.

##  2 Related Work

Prior attempts to model semantic fluency have largely been based on semantic
networks, or graph representations where words are nodes and relationships
between those nodes are edges. At least since Collins and Quillian (1969),
semantic networks have been a common tool in computational modeling Hills et
al. (2015); Avery and Jones (2018), typically using graph representations
drawing from large-scale databases such as WordNet Miller (1998), text corpora
MacWhinney (2000), and the USF free association norms Nelson et al. (2004).
The U-INVITE model Zemla et al. (2016) reconstructs individuals’ semantic
networks using a combination of large-scale databases and semantic fluency
data.

Information obtained from analyzing semantic fluency lists (SFLs) can be used
to construct portions of semantic networks. But since the amount of data in
SFLs is very small, it is more common to instead obtain word association data
from larger semantic datasets. For instance, the USF Free Association Norms
Nelson et al. (2004) is a free association dataset collected from more than
6,000 participants who were asked to write the first word $w$ that came to
their mind given a “cue word” $C$. This dataset offers more than 72,000 word
pairs ($C$, $w$) along with the percentage of participants who wrote $w$ given
$C$. Zemla and Austerweil (2017) used the USF norms to construct a semantic
network and simulate a variety of memory search processes, including censored
random walk, whose simulations are compared to the results of the previously
collected human data in an SFT Zemla et al. (2016). Small World of Words
(SWOW) De Deyne et al. (2019) is a more recent word association dataset
offering more than 1.3M ($C$, $w$) pairs. SNAFU Zemla et al. (2020) is a tool
for estimating semantic networks and analyzing fluency data (including random
walk); the authors provide a sample dataset of an SFT called “SNAFU
Sample”.222https://github.com/AusterweilLab/snafu-
py/blob/master/fluency_data/snafu_sample.csv gathered from 82 participants
that contains 796 lists spanning across 6 categories.333The number of items in
each category are fruits (60), vegetables (60), animals (296), supermarket
items (81), tools (149), foods (150). The median list lengths are fruits (18),
vegetables (17.5), animals (34), supermarket items (35), tools (16), foods
(36.5) In this paper, we try to model the SFLs from this dataset.

Hills et al. (2012) compare the memory search process to the strategies
animals use when searching for food (optimal foraging). This includes a
dynamic process of switching from local search of a cluster of semantically
similar items, to a global search when the difficulty of finding an item
nearby reaches a certain point. This process is called “patch switching”. To
replicate the dynamic process of switching between patches, the authors
implemented a dynamic model that used the previous item recalled and frequency
to perform the switching. The model produced a log-likelihood fit, which was
then compared to the static models that ignored the patchy structure of the
network. The dynamic model showed better results, suggesting that humans
perform memory search using patch switching too.

Kajic et al. (2017) proposed a biologically-constrained spiking neural network
model to produce human-like SFLs. Three different sources of associative data,
including the USF norms, were used to construct association matrices for a
neural network. To compare the results with the human data, the authors
recorded word responses as decoded vector representations and inter-item
response times between the adjacent retrieved words. The locality shown in
Hills et al. (2012) is supported by the results of these experiments: the
preceding word is the most similar to the current word in a patch.

A related task is Entity Set Expansion (ESE) Zhang et al. (2017) that takes a
set of entities as input (and not a category word like SFT) and tries to add
new entities to that set after predicting a category all those entities belong
to (this additional step is absent in SFT). The fundamental difference between
ESE and the work presented in this paper is that we are trying to model human
SFLs instead of just generating SFLs. Some work has also been done to explore
the information language models capture Ettinger (2020); Laverghetta Jr. et
al. (2021), but we note that at present, the ability of TLMs to model semantic
fluency has not been explored.

##  3 Experiments

To understand the extent to which TLMs can improve the modeling of SFLs, we
set out to establish baselines based on semantic networks, using word
association data similar to the approaches cited earlier, and comparing their
performance to TLMs’. We use the SNAFU Sample dataset, cleaning it to correct
suspected data entry errors (like autocorrecting typos).

###  3.1 Experimental Setup

Assume participant $u$ generates an SFL $L=\\{w_{1},...,w_{|L|}\\}$ in
response to category cue $C$ (animals, fruits, etc.). Given a function $f$
based on an approach (described below) which takes a context $\mathbf{D_{n}}$
(a list $[C,w_{1},...,w_{n-1}]$ such that $n\leq|L|$), applies some pre-
processing to it, and uses the underlying approach, can $f$ predict $w_{n}$?
We use two methods to describe and score $f$:

  1. 1.

$\textit{Coverage}=|L\cap W_{f}|/|L|$ where $W_{f}$ is the set of words
considered by $f$ while making its predictions. We also define scaled log-
likelihood within coverage as the log-likelihood of each in-coverage item in
$L$ according to $f$. In other words, the scaled log-likelihood reflects how
likely the list $L$ is to be generated by the function $f$. Since this is
defined only in coverage, it depends largely on coverage, and a better scaled
log-likelihood does not necessarily mean that a function is better.

  2. 2.

Top-$k$ accuracy is the percentage of times $w_{n}$ is present in $f$’s top-k
predictions. Top-k accuracy is independent of coverage and thus, we can
compare different functions based just on their top-k scores.

For both metrics, function $f_{1}$ is said to model human performance better
than $f_{2}$ if it has a higher score. We create multiple functions based on
each of the following approaches differing in hyperparameter values. We
lemmatize the predictions and only keep nouns (due to the category words
given) for these approaches. For simplicity, we also assume that a word will
never occur twice in the same SFL.

####  3.1.1 Baseline Approaches (Non-TLM based)

We use five non-TLM based approaches as baselines:

  1. 1.

Random Baseline: We use a dataset of $1/3$M most frequent unigrams (single
words) on the internet444https://www.kaggle.com/datasets/rtatman/english-word-
frequency to find the frequency with which unigrams and bigrams occur. The
most likely predictions are chosen from this weighted distribution of unigrams
and bigrams with the top-k predictions being the top-k most common words.

  2. 2.

Random Walk on USF Norms: We approximate the censored random walk algorithm
Abbott et al. (2015) on the USF Free Association Norms Nelson et al. (2004).
$p(w_{n}|C)$ is the number of times $C$ was the cue word and $w_{n}$ was the
response divided by the total number of times $C$ was the cue word. Coverage
is determined by words that were responses to $C$ in the USF Norms.

  3. 3.

Random Walk on SWOW: Small World of Words (SWOW) De Deyne et al. (2019) is a
word association dataset similar to the USF Norms, so the process is the same
as that for USF Norms.

  4. 4.

Word2Vec: We use the Google News 300-dimensional word embeddings model Mikolov
et al. (2013) to get the cosine similarity score of a word $w_{n}$ with all
the words in $\mathbf{D_{n}}$. The average of all these scores becomes
$\textit{sc}(w_{n}|\mathbf{D_{n}})$. Functions based on Word2Vec take a
hyperparameter context size ($ct$) which is the maximum number of words
preceding $w_{n}$ in the SFL to consider. These context words are included in
order to encourage clustering and switching behaviors (§2), in the hope that
higher probability will be assigned to words related to those in close
proximity. We test four different values for ct (0, 1, 3, 5) because our
experiments did not show a noticeable difference between $\textit{ct}=5$ and
$\textit{ct}>5$. To save runtime, $ct=2,4$ were eliminated too, giving us four
Word2Vec based functions.

  5. 5.

GloVe: Just like Word2Vec, we use a GloVe based word embeddings model
glove.6B.300d pre-trained on Wikipedia 2014 + Gigaword 5 Parker et al. (2011).
We use the same context size values for GloVe based functions as used for
Word2Vec based functions.

####  3.1.2 TLM-based approaches

We discussed several reasons behind the intuition to use TLMs to model human
SFLs in §1. We perform the MLM task (§1) on pre-trained TLMs using empirically
generated prompts for a category $C$ and a context size $ct$:

  1. 1.

The $w_{n-1-ct}$, …, the $w_{n-1}$, and the [MASK] are examples of Cs.

  2. 2.

Examples of Cs are the $w_{n-1-ct}$, …, the $w_{n-1}$, and the [MASK].

  3. 3.

The $w_{n-1-ct}$, …, the $w_{n-1}$, and the [MASK] are the first Cs that come
to my mind.

  4. 4.

The first Cs that come to my mind are the $w_{n-1-ct}$, …, the $w_{n-1}$, and
the [MASK].

Most of these prompts have the word ‘the’ preceding all the SFL items because,
without it, TLMs tended to predict stopwords much more often in our
preliminary experiments. Context sizes $\textit{ct}=0,1,3,5$ are tested, as
with Word2Vec and GloVe. Each TLM-based function differs in ct \- prompt pair,
giving us 56 functions for each TLM.

Each of these TLMs split the input prompts into tokens such that more than one
token is required to encode some words (for example, ‘blueberry’ is encoded by
RoBERTa using two tokens). We use a greedy strategy to allow our functions to
predict such words. Since one mask is insufficient to predict some words, we
also use two consecutive masks for the TLM to allow subwords for each of those
masks. A prompt with $ct=1$ would look like “Examples of fruits are the
strawberry and the [MASK][MASK].” We take the top 100 predictions the TLM made
for the first mask and pass a new prompt with each of those predictions
replacing the first mask to get 15 predictions for the second mask. Each TLM
outputs a softmax distribution over all its tokens corresponding to the mask
token. After choosing the top 15 predictions, we scale their probability to
add up to 1. These probabilities are multiplied by the previous prediction’s
probabilities to get a valid probability distribution for the two-mask
sequence. Since our function does not know the word we are trying to predict,
we generate 3000 one-mask, 1500 two-mask, 400 three-mask, and 100 four-mask
predictions for each function (these values were chosen to balance search
space size and computation time based on preliminary tests; their effect on
performance was minimal because we report top-1 and top-5 scores and these
values are well over that range). Since the cumulative probabilities of these
four sets of predictions add up to 4, we scale them based on how frequently
these words occur in the dataset of 1/3M most frequent words on the internet
(note that this is an estimate used to weigh the predictions).

The TLMs we use in this paper are DistilBERT-base-uncased Sanh et al. (2019),
RoBERTa-Large Liu et al. (2019), and RoBERTa-Med-Small-1M-2 (commonly known as
the smallest miniBERTa) Warstadt et al. (2020). The models differ in
architecture, size, and perhaps most importantly, pre-training data amounts.
The smallest miniBERTa is pre-trained on just 1M words, DistilBERT-base-
uncased is a smaller version of BERT Vaswani et al. (2017) pre-trained on
about 3.4B words, and RoBERTa-Large is pre-trained on approximately 34B words.
Since pre-training is the only training these models get before using them in
our functions, we can hypothesize that lesser pre-training data (miniBERTa)
might lead to poorer performance.

###  3.2 Experiment 1: Which approach is the best at modeling SFLs?

$\displaystyle\mathit{Avg}=\frac{1}{|\mathbf{L}||\mathbf{F}|}\underset{L\in\mathbf{L}}{\sum}\underset{f\in\mathbf{F}}{\sum}S(f,L)$
(1)

$\displaystyle\mathit{BO}=\frac{1}{|\mathbf{L}|}\underset{f}{\max}\underset{L\in\mathbf{L}}{\sum}S(f,L)$
(2)

$\displaystyle\mathit{BI}=\frac{1}{|\mathbf{L}|}\underset{L\in\mathbf{L}}{\sum}\underset{f}{\max}\;S(f,L)$
(3)

How well do our TLM-based approaches model human SFLs, compared to non-TLM-
based approaches? And do the different hyperparameters make the approaches
better? Furthermore, if certain approaches and hyperparameter values
effectively model human SFLs, do they tell us anything about human cognitive
traits? Our experimental setup is designed to be a comparative study: we
record the performance (coverage, scaled log-likelihoods, and top-$k$
accuracies) of each of our functions (from all approaches) for each SFL in
SNAFU Sample (§2). Let $\mathbf{L}$ be the set of SFLs in SNAFU Sample, and
let $S(f,L)$ denote the score (any metric) of function $f$ on SFL $L$. Let
$\mathbf{F}$ be the set of all functions for an approach. Since we tested a
wide range of hyperparameter value settings (functions) for each approach, we
define and report the approach average (Avg), best overall (BO), and best
individual (BI) scores as defined by Equations 1, 2, and 3.

Approach | Coverage (%) | Scaled LL | top-1 accuracy (%) | top-5 accuracy (%)
---|---|---|---|---
| Avg | BO | BI | Avg | BO | BI | Avg | BO | BI | Avg | BO | BI
Random | 96.4 | 96.4 | 96.4 |  $-$12.9 |  $-$12.9 |  $-$12.9 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
USF | 46.2 | 46.2 | 46.2 |  $-$6.2 |  $-$6.2 |  $-$6.2 | 2.9 | 2.9 | 2.9 | 11.6 | 11.6 | 11.6
SWOW | 71.2 | 71.2 | 71.2 |  $-$7.7 |  $-$7.7 |  $-$7.7 | 4.6 | 4.6 | 4.6 | 16.2 | 16.2 | 16.2
Word2Vec | 59.6 | 65.1 | 67.5 |  $-$5.5 |  $-$5.5 |  $-$5.5 | 2.2 | 3.0 | 4.3 | 8.4 | 10.4 | 12.8
GloVe | 53.6 | 62.8 | 64.1 |  $-$5.2 |  $-$4.8 |  $-$4.7 | 2.0 | 2.9 | 3.8 | 7.8 | 10.8 | 12.6
miniBERTa | 19.7 | 23.9 | 29.4 |  $-$9.3 |  $-$8.8 |  $-$6.8 | 0.0 | 0.1 | 0.2 | 0.1 | 0.3 | 0.7
DistilBERT | 57.8 | 58.9 | 60.5 |  $-$6.6 |  $-$6.2 |  $-$5.3 | 3.5 | 4.9 | 8.6 | 11.6 | 14.7 | 19.8
RoBERTa | 76.2 | 80.1 | 82.6 |  $-$6.0 |  $-$5.5 |  $-$4.9 | 4.9 | 6.9 | 10.3 | 16.1 | 20.3 | 25.1
ATC | - | - | - | - | - | - | 7.0 | 9.5 | 20.8 | 19.1 | 23.6 | 47.5
CA | - | - | - | - | - | - | 9.1 | 11.0 | 21.4 | 24.4 | 27.0 | 49.0
Table 1: Performance comparisons of all approaches. The scores for the best static approaches are in bold and the overall best scores are underlined and in bold. Note that larger scaled log-likelihoods and larger accuracies are better. Approach | Coverage (%) | top-5 accuracy (%)
---|---|---
| Fruits | Veg | Ani | Sup | Tools | Foods | Fruits | Veg | Ani | Sup | Tools | Foods
USF | 63.9 | 58.3 | 56.2 | 1.8 | 41.1 | 43.5 | 35.5 | 22.8 | 4.1 | 0.0 | 30.7 | 0.0
SWOW | 90.6 | 81.5 | 82.2 | 13.0 | 64.2 | 76.0 | 48.2 | 22.9 | 12.3 | 0.0 | 33.3 | 0.0
Word2Vec | 90.0 | 83.9 | 74.0 | 0.0 | 59.1 | 72.5 | 15.3 | 17.6 | 13.1 | 0.0 | 10.8 | 7.9
GloVe | 86.9 | 79.0 | 77.5 | 0.0 | 44.8 | 70.7 | 16.9 | 19.3 | 14.3 | 0.0 | 7.5 | 8.1
miniBERTa | 25.6 | 18.2 | 27.3 | 31.4 | 16.2 | 29.0 | 1.3 | 0.1 | 0.1 | 0.6 | 0.1 | 0.6
DistilBERT | 67.7 | 45.5 | 69.8 | 50.6 | 45.3 | 59.7 | 29.5 | 24.1 | 20.5 | 7.3 | 12.0 | 12.9
RoBERTa | 87.9 | 86.4 | 82.5 | 68.3 | 75.4 | 81.9 | 30.6 | 26.7 | 21.7 | 12.7 | 22.8 | 17.7
Table 2: Best Overall (BO) coverage and top-5 accuracy (%) on SFL categories.
The scores for the best performing approach on each category are in bold.

####  3.2.1 Results

The top part of Table 1 shows the performance comparison of all approaches.
Random baseline has a high coverage because the search space is 1/3M most
common words on the internet. RoBERTa-Large555To avoid confusion, TLM names
are in regular font and approach names are in italics proves to be the best
performing approach when generalized across all users, closely followed by
DistilBERT. miniBERTa is outstandingly poor, performing worse than all
baselines, proving our hypothesis about more pre-training data leading to
better performance.

On an aggregate level, TLM-based approaches outperform non-TLM-based
approaches. Best Overall (BO) reports the average scores of the function
(approach - hyperparameters combination) that performed the best across all
lists. Best Individual (BI) picks the best function for each SFL and reports
the average scores of this group of functions. BO and BI show the performance
of an approach if we were able to choose the best hyperparameter setting for
those approaches. Avg, BO, and BI are the same for approaches which do not
have different hyperparameter values (multiple functions). Note that best
individual (BI) is just a theoretical upper limit, as it assumes that we
choose the function which is the best for a particular SFL without any means
of knowing which one that might be. Thus, practical comparisons must be made
with BO instead of BI.

In order to get a deeper understanding of the strengths (and weaknesses) of
TLM-based approaches, we look at how they perform on each individual category
(Table 2). We report coverage and top-$5$ accuracy, which is a common metric
for cases where the number of classes is either large or not strictly defined
(each SFL category can have many items belonging to it) Luo et al. (2017);
Ravuri and Vinyals (2019) and more lenient than top-$1$ accuracy. We can see
from Table 2 that SWOW has a much better performance on ‘fruits’ and ‘tools’,
possibly because the smaller and higher quality search space SWOW has as a
semantic network is suited for categories that have fewer items belonging to
them in general (‘fruits’ and ‘tools’ have median list lengths of 18 and 16
respectively). However, smaller search space is a double-edged sword and hurts
performance on uncommon and wider categories like ‘supermarket items’ and
‘foods’ (median list lengths 35 and 36.5 respectively). The most significant
performance gain by TLM-based approaches is on these uncommon categories.
Possible reasons for this are larger vocabulary (coverage), better context-
awareness (all these TLMs have attention heads), and higher processing
capabilities. Note that we never fine-tuned these TLMs, and we are using just
the pre-trained versions, so any performance reflected here is due to learning
during pre-training.

###  3.3 Experiment 2: Can TLMs identify individual differences?

Table 1 clearly shows that large TLMs outperform the other language model
types we considered (except miniBERTa, which is significantly smaller than the
other TLMs listed). However, such aggregate evaluations can sometimes hide
interesting information. For example, is it the case that certain functions
better model individual SFLs? If so, this might suggest further ways of
generating exploratory hypotheses, in line with the idea of hyperparameter
hypothesization (§1.1)—e.g., if one prompt type seems to model lists generated
by one person best, whereas a different prompt type best models lists
generated by another, then this may suggest that there is a qualitative
difference in how those two individuals “query” their memories when performing
this task which is captured by the different prompt styles.

Experiment 2, therefore, aims to take first steps in exploring the
plausibility of these ideas. We start by examining the extent to which
specific functions (each of which, recall, consist of a model + hyperparameter
values) can adapt to individuals. Our task is conceptualized as follows: Given
an individual who is performing the SFT, and a machine that is observing the
list being generated one item at a time, how quickly can the machine adapt to
that individual and predict what items the individual will list next?

We refer to the functions compared in Experiment 1 as static, as they each
have fixed hyperparameter values. They are compared to two adaptive functions:

  * •

Adapt-Then-Change (ATC): Chooses the static function performing the best on
the first $x$ items of the SFL, and applies that chosen function to the rest
of the SFL. Performance is averaged across all the items in the latter part of
the list.

  * •

Continuous Adaptation (CA): Uses a sliding window of size $x$ and chooses the
best performing function for all the items in this window. It then applies
that chosen function to the next item. After this, the window slides one item
to the right. Whereas ATC only makes one decision about which function to use
per list, CA makes that decision for each list item (starting from the
$x^{th}$ item).

We do not calculate coverage and scaled log-likelihoods in coverage for
adaptive approaches because they are not new approaches, just strategies to
choose one hyperparameter setting for one of the existing approaches.

####  3.3.1 Results

Figure 1: Top-$5$ accuracy comparison of adaptive and static approaches.

From Table 1, adaptive approaches clearly outperform the static approaches,
indicating that a smart way to choose hyperparameters can drastically improve
prediction accuracy. Essentially, this means that based on just
$w_{1},...,w_{n-1}$ and without knowing $w_{n}$, we are able to find a set of
hyperparameters that can be used to predict the next word with about $27\%$
accuracy. Considering that this is across all categories and across all
individuals, and that the search space for this task is not strictly bounded,
these results exceed expectations. The adaptive approaches do not have
hyperparameters of their own so BO and BI in Table 1 are calculated based on
different values of $x$.

| USF | SWOW | Word2Vec | GloVe | miniBERTa | DistilBERT | RoBERTa
---|---|---|---|---|---|---|---
ATC | 9.5 | 10.4 | 7.9 | 2.3 | 0.1 | 29.0 | 40.8
CA | 12.9 | 15.9 | 8.9 | 2.7 | 0.4 | 28.2 | 31.0
Table 3: Percentage of times each static approach was chosen by an adaptive
approach.

The comparison of top-$5$ accuracies between the adaptive approaches and the
best static approach (RoBERTa-Large) is shown in Figure 1. ATC outperforms BO
static for certain values of $x$, and CA outperforms BO static almost always.
This is expected because CA adapts to the SFL items continuously while ATC
adapts just once. As discussed in §3.2.1, BI is more of a theoretical maximum,
due to the fact that it is selected from all functions for each SFL after we
already know it does best on that SFL. Nonetheless, CA still impressively
outperforms BI static for certain values of $x$.

##  4 Conclusion, Limitations, and Future Work

To our knowledge, we are the first to use transformer-based LMs to model
semantic fluency lists. We do so in the hopes of advancing the computational
modeling of human semantic knowledge and memory retrieval processes. To that
end, we used RoBERTa-Large, DistilBERT-base, and miniBERTa-med-small to model
semantic fluency lists and found that RoBERTa-Large and DistilBERT-base
consistently outperformed other non-transformer based approaches. We
hypothesize that miniBERTa-med-small’s poor performance is due to its smaller
pre-training corpus. DistilBERT-base’s performance suggests that the
associative semantic information needed to model human SFLs starts getting
imparted as the size of the training corpus increases from 1M words to about
3.4B. Future work can attempt to estimate the size of training corpus in this
range where TLMs start outperforming baseline approaches and whether larger
training corpora would hurt performance. Hopefully, using upcoming TLMs with a
wider variety of prompts inspired by this paper, perhaps using a technique
closer to prompt fine-tuning Fichtel et al. (2021) will give better results.

Furthermore, we took a first step in exploring the ability of TLMs to
determine individual differences in retrieval behaviors in the SFT. Our
results suggest that an adaptive approach works best, in some cases even
outperforming an oracular baseline. However, we do not yet know if the
function and hyperparameter choices that our adaptive approaches make reflect
stable individual cognitive traits or behaviors. Answering this question will
be the focus of future work, for which the present work has laid an important
foundation.

It is possible that fine-tuning on some subset of the SNAFU Sample dataset may
yield better likelihoods or top-k scores. Likewise, it may be trivial to fine-
tune RoBERTa to output all instances of a given category, or to train a LM to
simply enumerate all known hyponyms of a category word. But the goal of this
work, as described in §1.1, is primarily to match and then produce hypotheses
for cognitive processes. As such, it was not our goal to simply create an
exhaustive item list generator; rather, we want to emulate how people generate
SFLs.

In using transformer-based LMs to model human response patterns, it should be
noted that we are not taking into account how many other psychological and
cognitive constructs factor in to the complex retrieval processes involved in
SFT. Although the method we describe here is designed to compare individual
linguistic retrieval strategies, it is unclear what exactly it tells us about
how performance on semantic fluency tasks relates to individuals’ executive
functioning and self-regulation skills, which fluency tasks are often employed
to study Whiteside et al. (2016); Aita et al. (2019). Rather, the work here is
the first step in our proposed hyperparameter hypothesization strategy (§1.1),
which we propose here for the first time and believe contributes to the
present symposium’s goals.

##  5 Acknowledgements

Part of this research was sponsored by the DEVCOM Analysis Center and was
accomplished under Cooperative Agreement Number W911NF-22-2-0001. The views
and conclusions contained in this document are those of the authors and should
not be interpreted as representing the official policies, either expressed or
implied, of the Army Research Office or the U.S. Government. The U.S.
Government is authorized to reproduce and distribute reprints for Government
purposes notwithstanding any copyright notation herein.

## References

  * Welsh et al. [1991] Marilyn C Welsh, Bruce F Pennington, and Dena B Groisser.  A normative-developmental study of executive function: A window on prefrontal function in children.  _Developmental neuropsychology_ , 7(2):131–149, 1991.
  * Hills et al. [2012] Thomas T Hills, Michael N Jones, and Peter M Todd.  Optimal foraging in semantic memory.  _Psychological review_ , 119(2):431, 2012.
  * Abbott et al. [2015] Joshua T Abbott, Joseph L Austerweil, and Thomas L Griffiths.  Random walks on semantic networks can resemble optimal foraging.  In _Neural Information Processing Systems Conference; A preliminary version of this work was presented at the aforementined conference._ , volume 122, page 558. American Psychological Association, 2015.
  * Zemla et al. [2016] Jeffrey C Zemla, Yoed N Kenett, Kwang-Sung Jun, and Joseph L Austerweil.  U-invite: Estimating individual semantic networks from fluency data.  In _Proceedings of the 38th Annual Meeting of the Cognitive Science Society_ , pages 1907–1912, Austin, TX, 2016. Cognitive Science Society.
  * Zemla and Austerweil [2017] Jeffrey C Zemla and Joseph L Austerweil.  Modeling semantic fluency data as search on a semantic network.  In _CogSci… Annual Conference of the Cognitive Science Society. Cognitive Science Society (US). Conference_ , volume 2017, pages 3646–3651, 2017.
  * Avery and Jones [2018] Johnathan Avery and Michael N Jones.  Comparing models of semantic fluency: Do humans forage optimally, or walk randomly?  In _CogSci_ , 2018.
  * Holyoak and Hummel [2000] Keith J. Holyoak and John E. Hummel.  The Proper Treatment of Symbols in a Connectionist Architecture.  In E. Deitrich and A. Markman, editors, _Cognitive Dynamics: Conceptual Change in Humans and Machines_. MIT Press, Cambridge, MA, 2000.
  * Sun [2002] Ron Sun.  _Duality of the Mind: A Bottom Up Approach Toward Cognition_.  Lawrence Erlbaum Associates, Mahwah, NJ, 2002.
  * Wang et al. [2019] Alex Wang, Yada Pruksachatkun, Nikita Nangia, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman.  Superglue: A stickier benchmark for general-purpose language understanding systems.  In _Proceedings of NeurIPS_ , 2019.
  * Cui et al. [2020] Leyang Cui, Sijie Cheng, Yu Wu, and Yue Zhang.  Does bert solve commonsense task via commonsense knowledge?, 2020.
  * Gambi et al. [2020] Chiara Gambi, Priya Jindal, Sophie Sharpe, Martin J. Pickering, and Hugh Rabagliati.  The relation between preschoolers’ vocabulary development and their ability to predict and recognize words.  _Child Development_ , n/a(n/a), 2020.  ISSN 0009-3920.  doi:10.1111/cdev.13465.  URL https://srcd.onlinelibrary.wiley.com/doi/abs/10.1111/cdev.13465.
  * Schrimpf et al. [2020] Martin Schrimpf, Idan Blank, Greta Tuckute, Carina Kauf, Eghbal A. Hosseini, Nancy Kanwisher, Joshua Tenenbaum, and Evelina Fedorenko.  The neural architecture of language: Integrative reverse-engineering converges on a model for predictive processing.  _bioRxiv_ , 2020.  doi:10.1101/2020.06.26.174482.  URL https://www.biorxiv.org/content/early/2020/10/09/2020.06.26.174482.
  * Sun [2008] Ron Sun.  Introduction to computational cognitive modeling.  In _The Cambridge Handbook of Computational Psychology_. Cambridge University Press, 2008.
  * Jones and Love [2011] Matt Jones and Bradley C. Love.  Bayesian Fundamentalism or Enlightenment? On the Explanatory Status and Theoretical Contributions of Bayesian Models of Cognition.  _Behavioral and Brain Sciences_ , 34:169–231, 2011.
  * Marcus and Davis [2012] Gary Marcus and Ernest Davis.  How Robust Are Probabilistic Models of Higher-Level Cognition?  _Psychological Science_ , 24(12):2351–2360, 2012\.
  * Marcus and Davis [2015] Gary Marcus and Ernest Davis.  Still Searching for Principles: A Response to Goodman et al. (2015).  _Psychological Science_ , 26(4):542–544, 2015\.
  * Bricker [2016] Phillip Bricker.  Ontological Commitment.  In Edward N. Zalta, editor, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, winter 2016 edition, 2016.
  * Floridi [2011] Luciano Floridi.  _The Philosophy of Information_.  Oxford University Press, 2011.
  * Collins and Quillian [1969] Allan M Collins and M Ross Quillian.  Retrieval time from semantic memory.  _Journal of verbal learning and verbal behavior_ , 8(2):240–247, 1969.
  * Hills et al. [2015] Thomas T Hills, Peter M Todd, and Michael N Jones.  Foraging in semantic fields: How we search through memory.  _Topics in cognitive science_ , 7(3):513–534, 2015.
  * Miller [1998] George A Miller.  _WordNet: An electronic lexical database_.  MIT press, 1998.
  * MacWhinney [2000] Brian MacWhinney.  _The CHILDES project: The database_ , volume 2.  Psychology Press, 2000.
  * Nelson et al. [2004] Douglas L. Nelson, Cathy L. McEvoy, and T.A. Schreiber.  The university of south florida free association, rhyme, and word fragment norms.  _Behavior Research Methods, Instruments, and Computers_ , 36:402–407, 2004.
  * De Deyne et al. [2019] Simon De Deyne, Danielle Navarro, Andrew Perfors, Marc Brysbaert, and Gert Storms.  The small world of words: English word association norms for over 12,000 cue words, Aug 2019.  URL psyarxiv.com/mb93p.
  * Zemla et al. [2020] Jeffrey C Zemla, Kesong Cao, Kimberly D Mueller, and Joseph L Austerweil.  Snafu: The semantic network and fluency utility.  _Behavior research methods_ , 52(4):1681–1699, 2020.
  * Kajic et al. [2017] Ivana Kajic, Jan Gosmann, Brent Komer, Ryan W Orr, Terrence C Stewart, and Chris Eliasmith.  A biologically constrained model of semantic memory search.  In _CogSci_ , 2017.
  * Zhang et al. [2017] Xiangling Zhang, Yueguo Chen, Jun Chen, Xiaoyong Du, Ke Wang, and Ji-Rong Wen.  Entity set expansion via knowledge graphs.  In _Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’17, page 1101–1104, New York, NY, USA, 2017. Association for Computing Machinery.  ISBN 9781450350228.  doi:10.1145/3077136.3080732.  URL https://doi.org/10.1145/3077136.3080732.
  * Ettinger [2020] Allyson Ettinger.  What BERT is not: Lessons from a new suite of psycholinguistic diagnostics for language models.  _Transactions of the Association for Computational Linguistics_ , 8:34–48, 2020.  doi:10.1162/tacl_a_00298.  URL https://aclanthology.org/2020.tacl-1.3.
  * Laverghetta Jr. et al. [2021] Antonio Laverghetta Jr., Animesh Nighojkar, Jamshidbek Mirzakhalov, and John Licato.  Can Transformer Language Models Predict Psychometric Properties?  In _Proceedings of the 10th Joint Conference on Lexical and Computational Semantics (*SEM 2021)_ , Bangkok, Thailand, 2021. Association for Computational Linguistics.
  * Mikolov et al. [2013] Tomas Mikolov, Wen-tau Yih, and Geoffrey Zweig.  Linguistic regularities in continuous space word representations.  In _Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 746–751. Association for Computational Linguistics, 2013\.  URL http://aclweb.org/anthology/N13-1090.
  * Parker et al. [2011] Robert Parker, David Graff, Junbo Kong, Ke Chen, and Kazuaki Maeda.  English gigaword fifth edition.  _Linguistic Data Consortium_ , 2011.  doi:10.35111/wk4f-qt80.
  * Sanh et al. [2019] Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf.  Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter, 2019.  URL https://arxiv.org/abs/1910.01108.
  * Liu et al. [2019] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_ , 2019.
  * Warstadt et al. [2020] Alex Warstadt, Yian Zhang, Haau-Sing Li, Haokun Liu, and Samuel R. Bowman.  Learning which features matter: Roberta acquires a preference for linguistic generalizations (eventually), 2020.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Plosukhin.  Attention is all you need.  In _Proceedings of the 31st Conference on Neural Information Processing Systems (NIPS 2017)_ , Long Beach, CA, USA, 2017.
  * Luo et al. [2017] Jian-Hao Luo, Jianxin Wu, and Weiyao Lin.  Thinet: A filter level pruning method for deep neural network compression.  In _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , Oct 2017.
  * Ravuri and Vinyals [2019] Suman Ravuri and Oriol Vinyals.  Classification accuracy score for conditional generative models, 2019\.
  * Fichtel et al. [2021] Leandra Fichtel, Jan-Christoph Kalo, and Wolf-Tilo Balke.  Prompt tuning or fine-tuning - investigating relational knowledge in pre-trained language models.  In _3rd Conference on Automated Knowledge Base Construction_ , 2021\.  URL https://openreview.net/forum?id=o7sMlpr9yBW.
  * Whiteside et al. [2016] Douglas M. Whiteside, Tammy Kealey, Matthew Semla, Hien Luu, Linda Rice, Michael R. Basso, and Brad Roper.  Verbal fluency: Language or executive function measure?  _Applied Neuropsychology: Adult_ , 23(1):29–34, 2016.  doi:10.1080/23279095.2015.1004574.  URL https://doi.org/10.1080/23279095.2015.1004574.  PMID: 26111011.
  * Aita et al. [2019] Stephen L. Aita, Jameson D. Beach, Sarah E. Taylor, Nicholas C. Borgogna, Murphy N. Harrell, and Benjamin D. Hill.  Executive, language, or both? an examination of the construct validity of verbal fluency measures.  _Applied Neuropsychology: Adult_ , 26(5):441–451, 2019.  doi:10.1080/23279095.2018.1439830.  URL https://doi.org/10.1080/23279095.2018.1439830.  PMID: 29513079.


+m#1

# Benchmarking for Integrating Logic Rules with Everything Else

Yanhong A. Liu Scott D. Stoller Yi Tong K. Tuncay Tekle  Computer Science
Department, Stony Brook University, Stony Brook, New York, USA
<EMAIL_ADDRESS>
###### Abstract

Integrating logic rules with other language features is increasingly sought
after for advanced applications that require knowledge-base capabilities. To
address this demand, increasingly more languages and extensions for such
integration have been developed. How to evaluate such languages?

This paper describes a set of programming and performance benchmarks for
evaluating languages supporting integrated use of rules and other features,
and the results of evaluating such an integrated language together with logic
languages and languages not supporting logic rules.

##  1 Introduction

As knowledge-base capabilities are increasingly needed for advanced
applications, especially applications that require sophisticated reasoning,
logic rules are increasingly needed together with other language features.
This leads to increasingly more languages and extensions that provide such
programming support, for using rules through libraries or directly as built-
ins, in many different ways. To evaluate such language support for integrated
uses of rules with other language features, a set of benchmarking problems is
needed.

Many benchmarking suites have been developed for evaluating logic languages
and rule engines, and even drastically more for imperative and other
languages. In contrast, benchmarks and evaluation for languages that support
integrated use of rules together with other language features have been
lacking.

This paper describes a set of programming and performance benchmarks for such
evaluation, and the uses of these benchmarks in evaluating an integrated
language together with logic languages and languages not supporting logic
rules. The benchmarks are developed and organized into three sets:

OpenRuleBench—for problems focused on using rules and evaluating rule systems,
including all problems from OpenRuleBench [16], but modified and organized to
use more appropriate language features for the benchmarking itself, especially
imperative scripts for running and taking measurements.

RBAC—for problems that require (1) frequent imperative updates interleaved
with expensive queries and (2) objects and classes with inheritance to
organize system components, subsuming full Role-Based Access Control (RBAC)
[2, 18], with queries expressed in different ways of using rules and not using
rules.

PA—for problems expressed using rules together with set queries and aggregate
queries and recursive functions, from problems in program analysis (PA),
because aggregate queries are particularly important for many database, data
mining, and machine learning applications, but are not in OpenRuleBench [16].

The input data and workload for these benchmarks are designed for runs with
different problem scales—(1) large input data for queries using rules, (2)
large query results from inference using rules, (3) large number of rules, (4)
frequent switches between using rules and using other features, and (5)
frequent invocations of inference using rules.

The evaluation is for benchmark problems written in (1) Alda, (2) XSB, (3)
Python, and (4) DistAlgo. XSB [29, 33] is a top logic rule engine for queries
using rules, selected for reasons stated in Section 3.1. Python [28] is most
used for its rich features including high-level queries but lacks logic rules.
DistAlgo [21, 17] extends Python for distributed programming with higher-level
and faster queries but still lacks logic rules. Alda [22] is an integrated
language that supports logic rules as built-ins by building on DistAlgo and
employing XSB. The evaluation yields the following main results:

  * •

Queries using rules in Alda and XSB are similar, and are (1) simpler than
using while loops in Python and DistAlgo, even when these loops use high-level
set queries, and (2) drastically, asymptotically faster than while loops with
high-level set queries in Python and DistAlgo.

  * •

Benchmarking using more generic imperative scripts in Alda is drastically
simpler than using rules in XSB in OpenRuleBench; and integrated use of rules
with other features for RBAC and PA problems yields simpler programs than not
using rules or only using rules.

  * •

The performance of Alda programs is the accumulated performance of queries in
XSB, other features in Python and DistAlgo, and interface between XSB and
Python. Thus it is expected to increase accordingly when any part used is
improved, including reducing the current interface overhead to 1% of it.

  * •

Even with the current interface overhead, Alda programs are faster or even
drastically faster than half or more of the rule engines tested in
OpenRuleBench [16] for all but one benchmark, because the overhead is only
linear in sizes of data and results and number of queries, and thanks to the
XSB query performance.

Our analysis supports that similar results can be obtained by using other
efficient rule engines, including ASP systems, and other languages not
supporting logic rules, including lower-level languages. Our implementation
has been available by request and will be made public pending improved
documentation.

##  2 Language

XSB and Python are well established, and DistAlgo is subsumed by Alda. So we
first introduce Alda, an integrated language that supports rules with all of
sets, functions, updates, and objects, all as built-ins, seamlessly integrated
without extra interface code. Figure 1 shows an example program in Alda.

⬇

1class CoreRBAC: # class for Core RBAC component/object

2 def setup(): # method to set up the object, with no arguments

3 self.USERS, self.ROLES, self.UR := {},{},{}

4 # set users, roles, user-role pairs to empty sets

5 def AddRole(role): # method to add a role

6 ROLES.add(role) # add the role to ROLES

7 def AssignedUsers(role): # method to return assigned users of a role

8 return {u: u in USERS | (u,role) in UR} # return set of users having the role

⬇

...

⬇

9class HierRBAC extends CoreRBAC: # Hierarchical RBAC extending Core RBAC

10 def setup():

11 super().setup() # call setup of CoreRBAC, to set sets as in there

12 self.RH := {} # set ascendant-descendant role pairs to empty set

13 def AddInheritance(a,d): # to add inherit. of an ascendant by a descendant

14 RH.add((a,d)) # add pair (a,d) to RH

15 rules trans_rs: # rule set defining transitive closure

16 path(x,y) if edge(x,y) # path holds for (x,y) if edge holds for (x,y)

17 path(x,y) if edge(x,z), path(z,y) # ... if edge holds for (x,z) and for
(z,y)

18 def transRH(): # to return transitive RH and reflexive role pairs

19 return infer(path, edge=RH, rules=trans_rs) + {(r,r): r in ROLES}

20 def AuthorizedUsers(role): # to return users having a role transitively

21 return {u: u in USERS, r in ROLES | (u,r) in UR and (r,role) in transRH()}

⬇

...

⬇

22h = new(HierRBAC, []) # create HierRBAC object h, with no args to setup

23h.AddRole(’chair’) # call AddRole of h with role ’chair’

⬇

...

⬇

24h.AuthorizedUsers(’chair’) # call AuthorizedUsers of h with role ‘chair’

⬇

...

Figure 1: An example program in Alda, for Role-Based Access Control (RBAC),
demonstrating logic rules used with sets, functions, updates, and objects.

Rules are defined using rule sets (e.g. lines 15–17, with rule set name
trans_rs), and queried using calls to an inference function, infer (e.g. on
line 19, using rule set trans_rs). The two rules in trans_rs (lines 16–17)
define predicate path using predicate edge, where the first rule is the base
case, and the second rule is the recursive case. The call to infer (line 19)
returns the result of querying path, i.e., the set of pairs for which path
holds, given that edge equals RH, i.e., edge holds for the set of pairs in RH.

In a rule set, predicates not in any conclusion are called base predicates;
the other predicates are called derived predicates. The key idea is that
predicates are simply set-valued variables and vice versa. So predicates can
be defined and used directly as other variables, in any scope—global, object
field, or local to a rule set. The only exception is that derived predicates
can only be updated by infer, and are automatically maintained by an implicit
call to infer when any non-local base predicates are updated. The exception
ensures the declarative semantics of rules.

All other features—class, inheritance, method (function and procedure),
update, and set query—are the same as in object-oriented languages. We mostly
use Python syntax except for a few conventions from Java (extends for
inheritance, new for object creation, and omission of self when there is no
ambiguity) for ease of reading, and a few ideal syntax (:= for assignment, {}
for empty set, and \+ for set union), and pattern matching in queries (in
examples explained later).

For the example in Figure 1 but without using rules, computing the transitive
closure (i.e., result of infer in function transRH) in a variable T, by adding
a parameter E to function transRH and passing the value of RH to E when
calling transRH, can use a while loop in Python, as used for [18]:

⬇

T = E.copy()

W = {(x,y) for (x,z) in T for (z2,y) in E if z2==z} - T

while W:

T.add(W.pop())

W = {(x,y) for (x,z) in T for (z2,y) in E if z2==z} - T

or a while loop with higher-level set queries in DistAlgo:

⬇

T := E.copy()

while some (x,z) in T, (z,y) in E | (x,y) not in T:

T.add((x,y))

Using rules is clearly simpler, both conceptually and in the amount of code.

Alda is implemented by extending the DistAlgo compiler [21, 17] and invoking
XSB [29, 33] for inference. DistAlgo is compiled to Python. Function infer
translates data from Python to Prolog facts, translates results back, and
invokes XSB in between using command line and file passing. The obvious
overhead of this external interface can be removed with an in-memory interface
between Python to XSB, which is actively being developed by the XSB team.111A
version working for Unix, not yet Windows, has been released, and passing
lists of length 100 million in memory took about 30 nanoseconds per element
[33, release notes]. So even for the largest data in our experiments, of size
a few millions, it would take 0.1-0.2 seconds to pass in memory, instead of
10-20 seconds with the current external interface. However, this has not
affected Alda programs from having generally good performance, thanks to the
XSB query performance.

##  3 Programming and performance benchmarks

This section presents three sets of benchmarks that we developed. They are
written to express each given problem in the most direct way we can think of.
This helps make the benchmarks clear and easy to read. This also avoids being
unfair to any particular language or system being compared with.

###  3.1 OpenRuleBench—a wide variety of rule-based applications

OpenRuleBench [16] contains a wide variety of database, knowledge base, and
semantic web application problems, written using rules in 11 well-known rule
systems from 5 different categories, as well as large data sets and a large
number of test scripts for running and measuring the performance. Among 14
benchmarks described in [16], we consider all except for one that tests
interfaces of rule systems with databases (which is a non-issue for Python and
its extensions DistAlgo and Alda, because Python has standard and widely-used
database interfaces).

Table 1 summarizes the benchmarks. We compare with the benchmark programs in
XSB, for three reasons: (1) XSB has been the most advanced rule system
supporting well-founded semantics for non-stratified negation and tabling
techniques for efficient query evaluation, and has been actively developed for
over three decades, to this day; (2) among all systems reported in [16], XSB
was one of the fastest, if not the fastest, and the single most consistent
across all benchmarks; and (3) among all measurements reported, only XSB,
OntoBroker, and DLV could run all benchmarks, but OntoBroker went bankrupt,
and measurements for DLV were almost all slower, often by orders of magnitude.

We easily translated all 13 benchmarks into Alda, automatically for all except
for three cases where the original rules used features beyond Datalog, which
became two cases after we added support for negation. In all cases, it was
straightforward to express the desired functionality in Alda, producing a
program that is very similar to XSB or even simpler. Additionally, the code
for reading data, running tests, timing, and writing results is drastically
simpler in Alda than in XSB, because Alda extends Python. The three exception
cases and additional findings are described below.

Name |  Description | Prog size | Data size
---|---|---|---
Join1 |  non-recursive tree of binary joins as inference rules | 225 | *
Join2 |  join from IRIS system producing large intermediate result | 41 | *
JoinDup |  join of separate results of five copies of Join1 | 163 | *
LUBM |  university database adapted from LUBM benchmark | 377 | *
Mondial |  geographical database derived from CIA Factbook | 36 | 59,733
DBLP |  well-known bibliography database on the Web | 20 | 2,437,867
TC |  classical transitive closure of a binary relation | 75 | *
SG |  well-known same-generation siblings problem | 90 | *
WordNet |  natural language processing queries based on WordNet | 298 | 465,703
Wine |  well-known OWL wine ontology as rules | 1103 | 654
ModSG |  modified SG to exclude ancestor-descendant relationships | 38 | *
Win |  well-known win-not-win game with non-stratified negation | 24 | *
MagicSet |  non-stratified rules from magic-set transformation | 34 | *

The three groups (of 6, 4, 3) in order are called large join tests, Datalog
recursion, and default negation, respectively. Prog size is the XSB program
size in lines of code without comments and empty lines. Data size is the input
data size in number of facts; * means that scripts are used to generate input
data of desired sizes.
---

Table 1: Benchmarks from OpenRuleBench.

#### Result set.

In most logic languages, including Prolog and many variants, a query returns
only the first result that matches the query. To return the set of all
results, some well-known tricks are used. The LUBM benchmark includes the
following extra rules to return all answers of query9_1:

      query9 :- query9_1(X,Y,Z), fail.
      query9 :- writeln(’========query9.======’).

The first rule first queries query9_1 to find an answer (a triple of values
for X,Y,Z) and then uses fail to trick the inference into thinking that it
failed to find an answer and so continuing to search for an answer; and it
does this repeatedly, until query9_1 does fail to find an answer after
exhausting all answers. The second rule is necessary, even if with an empty
right side, to trick the inference into thinking that it succeeded, because
the first rule always ends in failing; this is so that the execution can
continue to do the remaining work instead of stopping from failing.

In fact, this trick is used in all benchmarks, but other uses are buried
inside the code for running, timing, etc., specialized for each benchmark, not
as part of the rules for the application logic.

In Alda, such rules and tricks are never needed. A call to infer with query
query9_1 returns the set of all query results as desired.

#### Function symbols.

Logic rules may use function symbols to form structured data that can be used
as arguments to predicates. Uses of function symbols can be translated away.
The Mondial benchmark uses a function symbol prov in several intermediate
conclusions and hypotheses of the form isa(prov(Y,X),provi) or
att(prov(Y,X),number,A). They can simply be translated to
isa(’prov’,Y,X,provi) andatt(’prov’,Y,X,number,A), respectively.

#### Negation.

Logic languages may use negation applied to hypotheses in rules. Most logic
languages only support stratified negation, where there is no negation
involved in cyclic dependencies among predicates. Such negation can be done by
set differences. The ModSG benchmark has such a negation, as follows, where sg
is defined by the rules in the SG benchmark, and nonsg is defined by two new
rules.

      sg2(X,Y) :- sg(X,Y), not nonsg(X,Y).

In Alda, this can be written as

      sg2 = infer(sg, rules=sg_rs) - infer(nonsg, rules=nonsg_rs)

where sg_rs and nonsg_rs are the rule sets defining sg and nonsg,
respectively.

Alda also supports negation in rules. Its current implementation translates
negation to tabled negation tnot in XSB. This handles even non-stratified
negation by computing well-founded semantics using XSB [4], contrasting
Prolog’s negation as failure. The Win and MagicSet benchmarks have non-
stratified negation. Both of them, as well as ModSG, can be expressed directly
in Alda rule sets by using not for negation.

#### Benchmarking and organization.

In OpenRuleBench benchmarks, even though the rules to be benchmarked are
declarative and succinct, the benchmarking code for reading input, running
tests, timing, and writing results are generally much larger. For example, the
Join1 benchmark has 4 small rules and 9 small queries similar in size to those
in the transitive closure example, plus a manually added tabling directive for
optimization. However, for each of the 9 queries, 19 more lines for an import
and two much larger rules are used to do the reading, running, timing, and
writing.

In general, because benchmarking executes a bundle of commands, scripting
those directly is simplest. Furthermore, organizing benchmarking code using
procedures, objects, etc., allows easy reuse without duplicated code. These
features are much better supported in languages like Python than rule systems,
for both ease of programming and performance,

In fact, OpenRuleBench uses a large number of many different files, in several
languages (language of the system being tested, XSB, shell script, Python,
makefile) for such scripting. For example for Join1, the 4 rules, tabling
directive, and benchmarking code are also duplicated in each of the 9 XSB
files, one for each query; a 46-line shell script and a 9-line makefile are
also used.

In contrast, our benchmarking code is in Alda, which uses Python functions for
scripting. A single 45-line Alda program is used for timing any of the
benchmarks, and for pickling (i.e., object serialization in Python, for fast
data reading after the first reading) and timing of pickling.

#### Aggregation.

Despite the wide variety of benchmarks in OpenRuleBench, no benchmark uses
aggregate queries. Aggregate queries are essential for many database, data
mining, and machine learning applications. We discuss them and compare with
aggregate queries in a rule language like XSB in Section 3.3.

###  3.2 RBAC—rules with objects, updates, and set queries

The ANSI standard for Role-Based Access Control (RBAC [8, 2] involves many
sets and query and update functions in a total of 9 components. To program the
transitive role hierarchy at a high level, a complex and inefficient while
loop was used before [18], because an efficient algorithm would be drastically
even more complex.

With support for rules, the entire RBAC standard is easily written in Alda,
similar as in Python [18], except with rules for computing the transitive role
hierarchy, as shown in Figure 1, yielding a simpler yet more efficient
program.

Below, we specify more ways of using rules to compute the transitive role
hierarchy and function AuthorizedUsers(role) in Figure 1. All these ways are
declarative and differ in size by only 1-2 lines. Table 2 summarizes the
benchmarks for RBAC that include all RBAC classes with their inheritance
relationships and perform update operations and these query functions in
different ways.

In particular, in the first way below, a field, transRH, is used and
maintained automatically; it avoids calling transRH() repeatedly, as desired
in the RBAC standard, and it does so without the extra maintenance code in the
RBAC standard for handling updates.

Name |  Features used for computing transitive role hierarchy
---|---
RBACnonloc |  rule set transRH_rs with implicit infer, without transRH(), Sec. 3.2
RBACallloc |  rule set trans_role_rs and transRH() that has only infer, Sec. 3.2
RBACunion |  rule set trans_rs and transRH() that has infer and union, Sec. 2
RBACda |  while loop and high-level set queries in DistAlgo, Sec. 2
RBACpy |  while loop and high-level set comprehensions in Python, Sec. 2

Each benchmark performs a combination of updates to sets and relations USERS,
ROLES, UR, and RH and queries with function AuthorizedUsers(role), where the
transitive role hierarchy is computed with a different way of using rules, or
not using rules. In AuthorizedUsers(role) of all five programs, the call to
transRH(), or reference to field transRH, is lifted out of the set query, by
assigning its value to a local variable and using that variable in the query.
---

Table 2: Benchmarks for RBAC updates and queries.

#### Rules with only non-local predicates.

Using rules with only non-local predicates, one can add a field transRH, and
use transRH in place of calls to transRH(), e.g., in function
AuthorizedUsers(role), and use the following rule set instead of trans_rs in
class HierRBAC:222The first rule could actually be omitted, because the second
argument of RH is always in ROLES and thus the second rule when joining RH
with reflexive pairs in transRH from the third rule subsumes the first rule.

⬇

rules transRH_rs: # no need to use infer explicitly

transRH(x,y) if RH(x,y)

transRH(x,y) if RH(x,z), transRH(z,y)

transRH(x,x) if ROLES(x)

Field transRH is automatically maintained at updates to RH and ROLES by
implicit calls to infer; no explicit calls to infer are needed. This
eliminates the need of function transRH() and repeated expensive calls to it
even when its result is not changed most of the time. Overall, this simplifies
the program, ensures correctness, and improves efficiency.

#### Rules with only local predicates.

Using rules with only local predicates, infer must be called explicitly. One
can simply use the function transRH() in Figure 1, which calls infer using
rule set trans_rs in the running example and then unions with reflexive role
pairs. Alternatively, one can use the rules in trans_rs plus a rule that uses
a local predicate role to infer reflexive role pairs:

⬇

rules trans_role_rs: # as trans_rs plus the added last rule

path(x,y) if edge(x,y)

path(x,y) if edge(x,z), path(z,y)

path(x,x) if role(x)

def transRH(): # use infer only, pass in also ROLES

return infer(path, edge=RH, role=ROLES, rules=trans_role_rs)

Both ways show the ease of using rules by simply calling infer. Despite
possible inefficiency in some cases, using only local predicates has the
advantage of full reusability of rules and full control of calls to infer.

###  3.3 Program analysis—rules with aggregate queries and recursive functions

We designed a benchmark for program analysis (PA) problems, especially to show
integrated use of rules with aggregate queries and recursive functions.
Aggregate queries help quantify and characterize the analysis results, and
recursive functions help do these on recursive structures. We describe
programs written in Alda and then in XSB.

The benchmark is for analysis of class hierarchy of Python programs. It uses
logic rules to extract class names and construct the class extension relation;
aggregate queries and set queries to characterize the results and find special
cases of interest; recursive functions as well as aggregate and set queries to
analyze the special cases; and more logic rules, functions, and set and
aggregate queries to further analyze the special cases.

Table 3 summarizes different parts of this benchmark, called PA. A variant,
called PAopt, is the same as PA except that, in the recursive rule for
defining transitive descendant relationship, the two hypotheses are reversed,
following previously studied optimizations [19, 34].

Part |  |  Analysis |  Features used
---|---|---|---
1 | Ext |  classes, extension relation |  rules (recursive if refined name analysis is used)
2 | Stat |  statistics, roots |  aggregate and set queries
3 | Hgt |  max height, roots of max height |  recursive functions, aggregate and set queries
4 | Desc |  max desc, roots of max desc |  recursive rules, functions, aggregate and set queries

In Parts 1 and 4 that use rules, not using rules (esp. for recursive analysis,
with tabling) would be drastically worse (i.e., harder to program and less
efficient). In Parts 2-4 that use aggregate and set queries, using rules or
recursive functions would be clearly worse. In Parts 3 and 4 that use
functions, not using functions (with tabling, also called caching) would be
much worse.
---

Table 3:  Benchmark PA for program analysis, integrating different kinds.

Because the focus is on evaluating the integrated use of different features,
each part that uses a single feature, such as rules, is designed to be small.
Compared with making each part larger, which exercises individual features
more, this design highlights the overhead of connecting different parts, in
terms of both ease of use and efficiency of execution.

The benchmark program takes as input the abstract syntax tree (AST) of a
Python program (a module or an entire package), represented as a set of facts.
Each AST node of type $\it T$ with $\it k$ children corresponds to a fact for
predicate $\it T$ with $\it k$+1 arguments: id of the node, and ids of the
$\it k$ children. Lists are represented using Member facts. A Member($\it
lst$,$\it elem$,$\it i$) fact denotes that list $\it lst$ has element $\it
elem$ at the $\it i$th position.

#### Part 1: Classes and class extension relation.

This part examines all ClassDef nodes in the AST. A ClassDef node has 5
children: class name, list of base-class expressions, and three nodes not used
for this analysis. The following rules can be used to find all defined class
names and build a class extension relation using base-class expressions that
are Name nodes. A Name node has two children: name and context.

⬇

rules class_extends_rs:

defined(c) if ClassDef(_,c,_, _,_,_)

extending(c,b) if ClassDef(_,c,baselist, _,_,_),

Member(baselist,base,_), Name(base,b,_)

For a dynamic language like Python, analysis involving names can be refined in
many ways to give more precise results, e.g., [10]. We do not do those here,
but Datalog rules are particularly good for such analysis of bindings and
aliases for names, e.g., [31].

#### Part 2: Characterizing results and finding special cases.

This part computes statistics for defined classes and the class extension
relation and finds root classes (class with subclass but not super class).
These use aggregate queries and set queries, where (_,c) and (=c,_) are tuple
patterns, _ matches anything, c is bound to the matched value, and =c matches
the value of c.

⬇

num_defined := count(defined)

num_extending := count(extending)

avg_extending := num_extending/num_defined

roots := {c: (_,c) in extending, not some (=c,_) in extending}

Similar queries can compute many other statistics and cases: maximum number of
classes that any class extends, leaf classes, histograms, etc.

#### Part 3: Analysis of special cases.

This part computes the maximum height of the extension relation, which is the
maximum height of the root classes, and finds root classes of the maximum
height. These use a recursive function as well as aggregate and set queries.

⬇

def height(c):

return 0 if not some (_,=c) in extending

else 1 + max{height(d): (d,=c) in extending}

max_height := max{height(r): r in roots}

roots_max_height := {r: r in roots, height(r) = max_height}

For efficiency when a subclass can extend multiple base classes, caching of
results of function calls is used. In Python, one can simply add import
functools to import module functools, and add @functools.cache just above the
definition of height to cache the results of that function.

#### Part 4: Further analysis of special cases.

This part computes the maximum number of descendant classes following the
extension relation from a root class, and finds root classes of the maximum
number. Recursive functions and aggregate queries similar to finding maximum
height do not suffice here, due to shared subclasses that may be at any depth.
Instead, the following rules can infer all desc(c,r) facts where class c is a
descendant following the extension relation from root class r, and aggregate
and set queries with function num_desc then compute the desired results.

⬇

rules desc_rs:

desc(c,r) if roots(r), extending(c,r)

desc(c,r) if desc(b,r), extending(c,b)

⬇

def num_desc(r):

return count{c: (c,=r) in desc}

max_desc := max{num_desc(r): r in roots}

roots_max_desc := {r: r in roots, num_desc(r) = max_desc}

For efficiency of the last query, caching is also used for function num_desc.
If the last query is omitted, function num_desc can also be inlined in the
max_desc query.

#### Comparing with aggregate queries and functions in rule languages.

While rules in Alda correspond directly to rules in rule languages, expressing
aggregate queries and functions using rules require translations that
formulate computations as hypotheses and introduce additional variables to
relate these hypotheses.

Aggregate queries are used extensively in database and machine learning
applications, and are essential for analyzing large data or uncertain
information. These queries are easy to express directly in database languages
and scripting languages, but are less so in rule languages like Prolog; most
rule languages also do not support general aggregation with recursion due to
their subtle semantics [20]. For example, the simple query num_defined :=
count(defined) in Alda, when written in XSB, becomes:

      num_defined(N) :- setof(C, defined(C), S), length(S, N).

Recursive functions are used extensively in list and tree processing and in
solving divide-and-conquer problems. They are natural for computing certain
information about parse trees, nested scopes, etc. However, in rule languages,
they are expressed in a way that mixes function arguments and return values,
and require sophisticated mode analysis to differentiate arguments from
returns. For example, the height query, when written in XSB, becomes:

      height(C,0) :- not(extending(_,C)).
      height(C,H) :- findall(H1, (extending(D,C), height(D,H1)), L),
                     max_list(L,H2), H is H2+1.

##  4 Experimental results

We present results about running times, program sizes, and data sizes. All
measurements were taken on a machine with an Intel Xeon X5690 3.47 GHz CPU, 94
GB RAM, running 64-bit Ubuntu 16.04.7, Python 3.9.9, and XSB 4.0.0. For each
experiment, the reported running times are CPU times averaged over 10 runs.
Garbage collection in Python was disabled for smoother running times when
calling XSB. Program sizes are numbers of lines excluding comments and empty
lines. Data sizes are number of facts.

#### Compilation times and program sizes.

Benchmark | Original | Alda | Compilation | Generated | Generated
---|---|---|---|---|---
name | XSB size | size | time (ms) | Python size | XSB size
Join1 | 225 | 23 | 33.0 | 32 | 5
Join2 | 41 | 11 | 18.5 | 16 | 9
JoinDup | 163 | 42 | 45.6 | 20 | 36
LUBM | 377 | 125 | 116.4 | 29 | 110
Mondial | 36 | 8 | 16.2 | 16 | 6
DBLP | 20 | 4 | 16.3 | 16 | 2
TC | 75 | 5 | 7.9 | 16 | 3
TCrev | *75 | 5 | 7.7 | 16 | 3
TCda | – | 5 | 4.9 | 18 | -
TCpy | – | 7 | 6.5 | 11 | -
SG | 90 | 13 | 17.9 | 20 | 7
WordNet | 298 | 58 | 76.2 | 44 | 28
Wine | 1103 | 970 | 605.6 | 16 | 968
ModSG | 38 | 14 | 14.8 | 16 | 12
Win | 24 | 4 | 9.5 | 16 | 2
MagicSet | 34 | 9 | 18.2 | 16 | 7
ORBtimer | – | 45 | 35.2 | 56 | -
RBACnonloc | – | 423 | 346.4 | 538 | 4
RBACallloc | – | 387 | 318.4 | 481 | 4
RBACunion | – | 386 | 316.6 | 481 | 3
RBACda | – | 385 | 312.8 | 483 | -
RBACpy | – | 387 | 314.6 | 476 | -
RBACtimer | – | 44 | 43.3 | 67 | -
PA | *55 | 33 | 49.7 | 93 | 6
PAopt | *55 | 33 | 40.8 | 93 | 6
PAtimer | – | 40 | 32.6 | 56 | -

For Original XSB size, entries without * are from OpenRuleBench, as in Table
1; * indicates XSB programs we added; – means there is no corresponding XSB
program. For Generated XSB size, - means no XSB code is generated.
---

Table 4: Compilation times and program sizes before and after compilation.

Table 4 shows Alda compilation times and related XSB, Alda, DistAlgo, and
Python program sizes before and after compilation. They are for all benchmarks
described in Section 3, plus three variants of TC, explained below in the
paragraph on performance of classical queries using rules. The Alda programs
are 4–970 lines for OpenRuleBench benchmarks, 385–423 lines for RBAC
benchmarks, and 33 lines for PA benchmarks. For each group of benchmarks,
there is a single shared Alda file of benchmarking code, shown in the last row
of each group.

The compilation times for all programs are 0.6 seconds or less, and for all
but RBAC benchmarks and Wine in OpenRuleBench are about 0.1 seconds or less.

For Alda programs that have corresponding XSB programs (OpenRuleBench in Table
1 and PA), Alda programs are all much smaller, almost all by dozens or even
hundreds of lines, and by an order of magnitude for Join1 and TC in
OpenRuleBench, because we have all the benchmarking code in the shared
benchmarking file.

#### Performance of classical queries using rules.

We experimented with four programs for computing transitive closure: TC, the
TC benchmark from OpenRuleBench, which is the same as trans_rs except with
renamed predicates; TCrev, a well-known variant with the two predicates
reversed in the recursive rule; and TCpy and TCda, which use the Python and
DistAlgo while loops, respectively, in Section 2. For comparison, we also
directly run the XSB program for TC from OpenRuleBench, and its corresponding
version for TCrev, except we change load_dyn to load_dync, for much faster
reading of facts in XSB’s canonical form; we call these programs TCXSB and
TCrevXSB, respectively. The same data generation as OpenRuleBench is used to
return large query results—almost complete graphs.

$10$$20$$30$$40$$50$$60$$70$$80$$90$$100$$0$$10$$20$$30$$40$$50$Number of
edges (in thousands)CPU time (in
seconds)TCTCrevTCrevXSBTCXSBTC_extraTCrev_extrarawRpickleW

$10$$20$$30$$40$$50$$60$$70$$80$$90$$100$$0$$10$$20$$30$$40$$50$Number of
edges (in thousands)CPU time (in
seconds)TCTCrevTCrevXSBTCXSBTC_extraTCrev_extrarawRpickleW

TCpy and TCda are not in the charts because they are asymptotically slower and
took drastically longer: on 100 vertices, with cyclic data of 200 edges (2% of
smallest data point in the charts), TCpy took 624.6 seconds, and TCda took
249.9 seconds; and with acyclic data of 600 edges, TCpy took 160.4 seconds,
and TCda took 65.2 seconds.
---

Figure 2: Running times of TC benchmarks on cyclic (left) and acyclic (right)
graphs.

Figure 2 shows the running times of the TC benchmarks. RawR and PickleW are
times for reading facts in XSB/Prolog form as used in OpenRuleBench and
writing them in pickled form for use in Alda, respectively. Pickling is done
only once; the pickled data is read in all repeated runs and all of TC, TCrev,
TCda, and TCpy. The running time of Alda programs includes not only (1)
reading data, (2) executing queries, and (3) returning results, but also
(2pre) preparing data, queries, and commands and writing data to files for XSB
before (2), and (2post) reading results from files written by XSB after (2).
TC_extra and TCrev_extra are the part of TC and TCrev, respectively, for extra
work interfacing with XSB, i.e., for 2pre and 2post and for XSB to read data
(xsbRdata) and write results (xsbWres). A breakdown showing the time needed
for each step in the extra work is in [23].

The results are as expected: the two Alda programs that use rules are
asymptotically, drastically faster than Python and DistAlgo while loops, and
they exhibit known notable performance differences [34, 35]. Most notably but
as expected, passing the query results back from XSB has a high overhead, up
to 5.9 seconds, out of 29.2 seconds total, for graphs of 100K edges, but this
overhead is expected to be reduced to 1% of it when the in-memory Python-XSB
interface is used. Note that reversing the two predicates in the recursive
rule does give a linear-factor asymptotically different running time, but that
barely shows because OpenRuleBench uses almost complete graphs.

#### Integrating with objects, updates, and set queries.

We use RBAC benchmarks in Table 2, Section 3.2, for this evaluation,
especially with frequent queries and updates and intensively frequent restart
of XSB for queries randomly mixed with updates of the queried data: 5000
users, 500 roles, 5000 UR relation, 550 RH relation, up to 500 queries, and
230 updates of various kinds.

Figure 3 shows the running times of the RBAC benchmarks, all scaling linearly
in the number of queries, as expected. Labels with suffix _extra indicate the
part of the running time of the corresponding program for extra work
interfacing with XSB. A breakdown of the time for extra work is in [23].

The results are as expected as well: RBACunion and RBACalloc are very close,
and are much slower than RBACnonloc—up to 331.7 and 333.9 seconds,
respectively, vs. 97.9 seconds. Most notably but as expected, the overhead of
repeated queries using XSB is high for RBACunion and RBACalloc, but low for
RBACnonloc, up to 134.5 and 145.9 seconds, respectively, vs. 2.8 seconds. The
highest overhead is from restarting XSB 500 times, which will be totally
eliminated when in-memory interface is used.

50100150200250300350400450500$0$$100$$200$$300$$400$Number of AuthorizedUsers
queriesCPU time (in
seconds)RBACalllocRBACunionRBACallloc_extraRBACunion_extraRBACnonlocRBACnonloc_extra

| RBACpy |
---|---
#queries | time (s)
50 | 688.7
100 | 1381.5
150 | > 30 min
RBACda |
#queries | time (s)
50 | 384.6
100 | 768.1
150 | 1141.7
200 | 1517.5
250 | > 30 min
|  RBACpy and RBACda are not in the chart because they are drastically slower.
---

Figure 3: Running times of RBAC benchmarks, for a workload of updates and
queries over 5000 users, 500 roles, 5500 user-role assignments, and 550 role
hierarchy pairs.

#### Integrating with aggregate queries and recursive functions.

We use PA and PAopt benchmarks and their corresponding programs in XSB, as
described in Section 3.3, for this evaluation, and we focus on applying the
analysis to large programs as input data. The programs analyzed include 9
widely-used open-source Python packages for a wide range of application
domains: NumPy, SciPy, MatPlotLib, Pandas, SymPy, Blender, Django, Scikit-
learn, and PyTorch—with 641K–5.1M input facts total and 252K–2.2M facts used
by the analysis.

Table 5 shows data sizes, analysis results, and running times of the analysis.
The columns are sorted by the total number of facts used. A breakdown of the
running time into steps interfacing with XSB as well as the remainder of the
running time is in [23].

The results are not as expected: we found the corresponding XSB programs to be
highly inefficient, being all slower and even drastically slower than Alda
programs, even 120 times slower for PyTorch. Significant effort was spent on
performance debugging and manual optimization, and we eventually created a
version that is faster than Alda—5.1 seconds vs. 15.2 seconds on the largest
input, SymPy—by using additional directives for targeted tabling that also
subsumes some indexing.

As expected, the Alda programs here have a high overhead of passing the data
to XSB, up to 13.1 seconds on SymPy, which again is expected to be reduced to
1% of it with in-memory Python-XSB interface. This means that the resulting
Alda programs would be faster than even the manually optimized XSB, showing
that computations not using rules, e.g., aggregations and functions, are not
only simpler and easier in Alda/Python than in XSB but also faster.

Measure | Item/Name | numpy | django | sklearn | blender | pandas | matplot | scipy | pytorch | sympy
---|---|---|---|---|---|---|---|---|---|---
Data | Total | 640,715 | 815,551 | 862,031 | 909,600 | 942,315 | 1,064,859 | 1,092,466 | 5,142,905 | 5,115,105
size |  ClassDef | 587 | 1,835 | 535 | 2,146 | 849 | 994 | 898 | 6,467 | 1,830
|  Name | 96,076 | 119,077 | 137,066 | 107,638 | 153,664 | 152,357 | 178,754 | 797,072 | 1,063,842
|  Member | 155,207 | 199,416 | 210,410 | 242,531 | 227,766 | 268,736 | 260,848 | 1,270,917 | 1,112,296
| Total used | 251,870 | 320,328 | 348,011 | 352,315 | 382,279 | 422,087 | 440,500 | 2,074,456 | 2,177,968
Ratio | Used/Total | 39.3% | 39.3% | 40.4% | 38.7% | 40.6% | 39.6% | 40.3% | 40.3% | 42.6%
Result |  #defined | 519 | 1610 | 533 | 2118 | 804 | 935 | 882 | 4323 | 1786
size |  #extending | 419 | 1457 | 710 | 2951 | 407 | 610 | 719 | 2207 | 1816
|  #roots | 79 | 225 | 51 | 133 | 88 | 104 | 60 | 137 | 92
|  max_height | 8 | 7 | 5 | 4 | 7 | 5 | 3 | 5 | 12
|  #roots_max_h | 1 | 2 | 2 | 1 | 2 | 1 | 4 | 1 | 1
|  #desc | 427 | 2329 | 822 | 4376 | 436 | 605 | 721 | 2174 | 2413
|  max_desc | 84 | 309 | 256 | 1,638 | 65 | 47 | 353 | 1,045 | 1,078
|  #roots_max_d | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1
Running | PA | 2.542 | 3.573 | 3.263 | 5.134 | 3.342 | 3.733 | 3.646 | 14.652 | 15.243
time | PAopt | 2.631 | 3.520 | 3.235 | 4.661 | 3.341 | 3.676 | 3.633 | 14.706 | 15.132
(in | PAXSB | 6.297 | 112.091 | 10.795 | 243.765 | 6.378 | 14.400 | 22.221 | 969.228 | 65.382
seconds) | PAoptXSB | 13.170 | 343.428 | 17.066 | 326.629 | 18.863 | 40.871 | 29.675 | 1773.374 | 181.961
| PAXSBopt | 0.804 | 1.499 | 1.071 | 2.149 | 1.118 | 1.317 | 1.300 | 5.158 | 5.051
Ratio | PAopt | 103.5% | 98.5% | 99.1% | 90.8% | 100.0% | 98.5% | 99.6% | 100.4% | 99.3%
over | PAXSB | 247.7% | 3137.2% | 330.8% | 4748.0% | 190.8% | 385.7% | 609.5% | 6615.0% | 428.9%
PA | PAoptXSB | 518.1% | 9611.7% | 523.0% | 6362.1% | 564.4% | 1094.9% | 813.9% | 12103.3% | 1193.7%
| PAXSBopt | 31.6% | 42.0% | 32.8% | 41.9% | 33.5% | 35.3% | 35.6% | 35.2% | 33.1%

Total is the total number of facts about each package. Total used is the sum
of numbers of ClassDef, Name, and Member facts.
---

Table 5: Data size, analysis results, and running times for program analysis
benchmarks.

#### Scaling with data and rules.

We use the two largest benchmarks from OpenRuleBench: DBLP, with over 2.4
million facts, the largest real-world data set among all in OpenRuleBench; and
Wine, with 961 rules, the largest rule set among all. Table 6 shows the
running times for both benchmarks, for both the Alda programs and the XSB
programs. _extra is the part of the total time on 2pre, 2post, xsbRdata, and
xsbWres. OrigTotal is the Total time for the original program from
OpenRuleBench, which uses load_dyn instead of load_dync.

The results are again as expected. For DBLP, XSB is more than three times as
fast as Alda, 9.5 seconds vs. 30.6 seconds, but as for PA benchmarks, the
overhead of passing the large data to XSB is large, here 26.9 seconds, and is
expected to be reduced to 1% of that; note that the Alda program has faster
reading from pickled data.

For Wine, XSB is more than eight times as fast as Alda, 3.8 seconds vs. 31.0
seconds. This is due to the use of auto_table in Alda generated code, which
does variant tabling, whereas this program, through manual debugging and
optimization, was found to need subsumptive tabling [35]. Optimizations [19,
34, 35] can be added to the Alda compiler to match this efficiency
automatically. Note that this slowest Alda program is still faster than half
of the systems tested in OpenRuleBench, which took up to 140 seconds and three
systems gave errors, and where XSB was the fastest at 4.47 seconds [16].

| Alda | XSB
---|---|---
Name | RawR | PickleW | 2pre | xsbRdata | xsbWres | 2post | _extra | Total | Total | OrigTotal
DBLP | 12.187 | 3.131 | 15.722 | 11.197 | 0.054 | 0.020 | 26.993 | 30.573 | 9.492 | 63.494
Wine | 0.008 | 0.000 | 0.037 | 0.219 | 0.000 | 0.001 | 0.257 | 30.960 | 3.754 | 3.826
Table 6: Running times (in seconds) of DBLP and Wine benchmarks.

##  5 Related work and conclusion

Many benchmarking suites have been developed for evaluating the performance of
queries in logic languages and rule engines, including the carefully
constructed OpenRuleBench for comprehensively evaluating a diverse set of
problems in a wide range of systems [16]. In particular, Prolog has had
benchmarks for comparing performance of different implementations [6, 5]. Some
are focused on a special class of problems, e.g., interpreters written in
Prolog [14]. Some are for evaluating the performance of a particular
implementation, e.g., SWI Prolog [32]. There are also works that evaluate
queries in more general rule engines and database systems, e.g., the LUBM
benchmark [12] and its extensions [25, 30] for OWL on a range of systems, and
evaluations including SQL with rules [13, 3]. There are also works focused on
evaluating interfaces, e.g., Java Prolog Interface [24]. These works study
only queries.

Even drastically more benchmarking suites were developed for evaluating other
systems. Works range from systematic studies, e.g., [15, 11, 26], to a large
variety of specific benchmarks, e.g., the SPEC benchmarks for computer systems
in general [26], the TPC benchmarks for transaction processing [27], the
LINPACK benchmarks [7] on solving linear equations, and many more. These
benchmarks exercise updates and many other language features but not logic
rules.

In contrast, our work develops benchmarks that exercise integrated use of
rules together with other language features. We improve OpenRuleBench
benchmarks with significantly simplified benchmarking code, and design new
benchmarks that exercise tightly integrated uses of different features on
problems that test different problem scales in different ways. We also compare
different ways of using rules vs. not using rules.

In conclusion, this work presents a set of programming and performance
benchmarks for evaluating languages supporting integrated use of rules and
other features, and the results of using these benchmarks in an evaluation.
Future work can perform evaluations with additional languages and systems,
especially efficient ASP systems such as Clingo [9].

#### Acknowledgments.

We thank Bo Lin for his robust DistAlgo compiler implementation, and his
initial help in implementing the Alda compiler, and we thank David S. Warren
for his initial help in implementing an interface to XSB. We also thank Thang
Bui for additional applications in program analysis and optimization, and
students in undergraduate and graduate courses for using Alda and its earlier
versions, called DA-rules. This work was supported in part by NSF under grants
CCF-1954837, CCF-1414078, and IIS-1447549 and ONR under grants
N00014-21-1-2719, N00014-20-1-2751, and N00014-15-1-2208.

## References

  * [1]
  * [2] ANSI INCITS (2004): _Role-Based Access Control_.  ANSI INCITS 359-2004, American National Standards Institute, International Committee for Information Technology Standards.
  * [3] Stefan Brass & Mario Wenzel (2019): _Performance Analysis and Comparison of Deductive Systems and SQL Databases_.  In: Proceedings of the 3rd International Workshop on the Resurgence of Datalog in Academia and Industry, CEUR-WS.org, pp. 27–38.
  * [4] Weidong Chen & David S. Warren (1996): _Tabled Evaluation with Delaying for General Logic Programs_.  Journal of the ACM 43(1), pp. 20–74, 10.1145/227595.227597.
  * [5] (2001): _The CHINA Benchmark Suite_.  http://www.cs.unipr.it/China/Benchmarks.  Accessed Feb. 1, 2023.
  * [6] (1985): _Prolog Benchmarking Suites_.  http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/prolog/code/bench/0.html.  Accessed Feb. 1, 2023.
  * [7] Jack J Dongarra, Piotr Luszczek & Antoine Petitet (2003): _The LINPACK benchmark: past, present and future_.  Concurrency and Computation: practice and experience 15(9), pp. 803–820, 10.1002/cpe.728.
  * [8] David F. Ferraiolo, Ravi Sandhu, Serban Gavrila, D. Richard Kuhn & Ramaswamy Chandramouli (2001): _Proposed NIST Standard for Role-Based Access Control_.  ACM Transactions on Information and Systems Security 4(3), pp. 224–274, 10.1145/501978.501980.
  * [9] Martin Gebser, Roland Kaminski, Benjamin Kaufmann & Torsten Schaub (2019): _Multi-shot ASP solving with clingo_.  Theory and Practice of Logic Programming 19(1), pp. 27–82, 10.1017/S1471068418000054.
  * [10] Michael Gorbovitski, Yanhong A. Liu, Scott D. Stoller, Tom Rothamel & Tuncay Tekle (2010): _Alias Analysis for Optimization of Dynamic Languages_.  In: Proceedings of the 6th Symposium on Dynamic Languages, ACM Press, pp. 27–42, 10.1145/1869631.1869635.
  * [11] Jim Gray, editor (1993): _The Benchmark Handbook for Database and Transaction Processing Systems_ , 2nd edition.  Morgan Kaufmann Publishers.
  * [12] Yuanbo Guo, Zhengxiang Pan & Jeff Heflin (2005): _LUBM: A benchmark for OWL knowledge base systems_.  Journal of Web Semantics 3(2-3), pp. 158–182, 10.1016/j.websem.2005.06.005.
  * [13] Ulrich John, Petra Hofstedt, Armin Wolf et al. (2019): _A New Benchmark Database and An Analysis of Transitive Closure Runtimes_.  Deklarative Ansätze zur Künstlichen Intelligenz–punktuelle Beiträge, p. 3.
  * [14] Philipp Körner, David Schneider & Michael Leuschel (2020): _On the performance of bytecode interpreters in Prolog_.  In: International Workshop on Functional and Constraint Logic Programming, Springer, pp. 41–56, 10.1007/978-3-030-75333-7_3.
  * [15] Byron C. Lewis & Albert E. Crews (1985): _The evolution of benchmarking as a computer performance evaluation technique_.  MIS Quarterly, pp. 7–16, 10.2307/249270.
  * [16] Senlin Liang, Paul Fodor, Hui Wan & Michael Kifer (2009): _OpenRuleBench: An Analysis of the Performance of Rule Engines_.  In: Proceedings of the 18th International Conference on World Wide Web, ACM Press, pp. 601–610, 10.1145/1526709.1526790.
  * [17] Bo Lin & Yanhong A. Liu (2014 (Latest update January 30, 2022)): _DistAlgo: A Language for Distributed Algorithms_.  http://github.com/DistAlgo.  Accessed May 25, 2023.
  * [18] Yanhong A. Liu & Scott D. Stoller (2007): _Role-Based Access Control: A Corrected and Simplified Specification_.  In: Department of Defense Sponsored Information Security Research: New Methods for Protecting Against Cyber Threats, Wiley, pp. 425–439.
  * [19] Yanhong A. Liu & Scott D. Stoller (2009): _From Datalog Rules to Efficient Programs with Time and Space Guarantees_.  ACM Transactions on Programming Languages and Systems 31(6), pp. 1–38, 10.1145/1552309.1552311.
  * [20] Yanhong A. Liu & Scott D. Stoller (2022): _Recursive Rules with Aggregation: A Simple Unified Semantics_.  Journal of Logic and Computation 32(8), pp. 1659–1693, 10.1093/logcom/exac072.  Also http://arxiv.org/abs/2007.13053.
  * [21] Yanhong A. Liu, Scott D. Stoller & Bo Lin (2017): _From Clarity to Efficiency for Distributed Algorithms_.  ACM Transactions on Programming Languages and Systems 39(3), pp. 12:1–12:41, 10.1145/2994595.  Also http://arxiv.org/abs/1412.8461.
  * [22] Yanhong A. Liu, Scott D. Stoller, Yi Tong & Bo Lin (2023): _Integrating logic rules with everything else, seamlessly_.  Theory and Practice of Logic Programming.  Special issue for selected papers from ICLP 2023. To appear. Also http://arXiv.org/abs/2305.19202.
  * [23] Yanhong A. Liu, Scott D. Stoller, Yi Tong, Bo Lin & K. Tuncay Tekle (2022): _Programming with Rules and Everything Else, Seamlessly_.  Computing Research Repository arXiv:2205.15204 [cs.PL], 10.48550/arXiv.2205.15204.
  * [24] Jose E Zalacain Llanes (2022): _Java Prolog Interface_.  arXiv preprint arXiv:2203.17134, 10.48550/arXiv.2203.17134.
  * [25] Li Ma, Yang Yang, Zhaoming Qiu, Guotong Xie, Yue Pan & Shengping Liu (2006): _Towards a complete OWL ontology benchmark_.  In: European Semantic Web Conference, Springer, pp. 125–139, 10.1007/11762256_12.
  * [26] Raghunath Nambiar & Meikel Poess, editors (2009): _Performance Evaluation and Benchmarking_.  Springer, 10.1007/978-3-642-10424-4.
  * [27] Raghunath Nambiar, Nicholas Wakou, Forrest Carman & Michael Majdalany (2010): _Transaction Processing Performance Council (TPC): State of the council 2010_.  In: Technology Conference on Performance Evaluation and Benchmarking, Springer, pp. 1–9, 10.1007/978-3-642-18206-8_1.
  * [28] Python Software Foundation (2023): _Python_.  http://python.org/.  Accessed Jun 7, 2023.
  * [29] Konstantinos Sagonas, Terrance Swift & David S. Warren (1994): _XSB as an Efficient Deductive Database Engine_.  In: Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, ACM Press, pp. 442–453, 10.1145/191839.191927.
  * [30] Gunjan Singh, Sumit Bhatia & Raghava Mutharaju (2020): _OWL2Bench: a benchmark for OWL 2 reasoners_.  In: International semantic web conference, Springer, pp. 81–96, 10.1007/978-3-030-62466-8_6.
  * [31] Yannis Smaragdakis & George Balatsouras (2015): _Pointer Analysis_.  Foundations and Trends in Programming Languages 2(1), pp. 1–69, 10.1561/2500000014.
  * [32] (2022): _SWI-Prolog benchmark suite_.  https://github.com/SWI-Prolog/bench.  Accessed Feb. 1, 2023.
  * [33] Theresa Swift, David S. Warren, Konstantinos Sagonas, Juliana Freire, Prasad Rao, Baoqiu Cui, Ernie Johnson, Luis de Castro, Rui F. Marques, Diptikalyan Saha, Steve Dawson & Michael Kifer (2022): _The XSB System Version 5.0,x_.  http://xsb.sourceforge.net. Latest release May 12, 2022.
  * [34] K. Tuncay Tekle & Yanhong A. Liu (2010): _Precise Complexity Analysis for Efficient Datalog Queries_.  In: Proceedings of the 12th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming, pp. 35–44, 10.1145/1836089.1836094.
  * [35] K. Tuncay Tekle & Yanhong A. Liu (2011): _More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets_.  In: Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, pp. 661–672, 10.1145/1989323.1989393.