¶ JetBrains
Belgrade, 11070 Serbia
and † Toloka
Belgrade, 11000 Serbia
and ‡ Toloka
Lucerne, 6005 Switzerland

# Toloka Visual Question Answering Benchmark

Dmitry Ustalov¶
<EMAIL_ADDRESS>
This work was done while the author was with Toloka. Nikita Pavlichenko†
<EMAIL_ADDRESS>
Sergey Koshelev†
<EMAIL_ADDRESS>
Daniil Likhobaba†
<EMAIL_ADDRESS>
Alisa Smirnova‡
<EMAIL_ADDRESS>
###### Abstract

In this paper, we present _Toloka Visual Question Answering_ , a new
crowdsourced dataset allowing comparing performance of machine learning
systems against human level of expertise in the grounding visual question
answering task. In this task, _given an image and a textual question, one has
to draw the bounding box around the object correctly responding to that
question_. Every image-question pair contains the response, with only one
correct response per image. Our dataset contains 45,199 pairs of images and
questions in English, provided with ground truth bounding boxes, split into
train and two test subsets. Besides describing the dataset and releasing it
under a CC BY license, we conducted a series of experiments on open source
zero-shot baseline models and organized a multi-phase competition at WSDM Cup
that attracted 48 participants worldwide. However, by the time of paper
submission, no machine learning model outperformed the non-expert
crowdsourcing baseline according to the intersection over union evaluation
score.

(a) What do we use to support the immune system and get vitamin C? (b) What do
people use for cutting? (c) What do you use to hit the ball?

Figure 1: Given an image and a textual question, draw a bounding box
containing the correct answer to the question. Above is a sample of three
image-question pairs from the training subset of our dataset. Every image
contains the response, with only one correct response per image. Bounding
boxes are drawn for illustrative purposes only; they are not parts of images
in our dataset but are available as ground truth for all images. All images
are from the MS COCO dataset (Lin:14, ) under the same license.

##  1 Introduction

Recently, prominent multi-modal deep learning models such as CLIP (Radford:21,
) and DALL-E (Ramesh:21, ) have demonstrated remarkable performance in
demanding tasks such as text-image similarity measurement and text-to-image
generation, respectively. Concurrently, modern machine learning methods have
achieved superhuman results on challenging multi-task benchmarks like
SuperGLUE (Wang:19, ) and VLUE (Zhou:22, ). However, most of these benchmarks
incorporate a combination of well-known tasks with limited modality. In this
study, we enhance the level of difficulty for machine learning methods by
introducing the _Toloka Visual Question Answering_ , an open-source multi-
modal dataset designed to evaluate artificial intelligence systems. We provide
a comprehensive description of the benchmark, outline our crowdsourcing
pipeline for data collection, and present the performance of current pre-
trained and fine-tuned models in tackling the challenging problem of grounding
visual question answering.

Our task is formulated as follows. Given an image and an English textual
question, the objective is to draw a bounding box around the object that
provides the correct response to the question (Figure 1). For instance, in a
photograph of a bathroom, a question like “Where do I wash my hands?” would
require selecting the sink as the answer. Successfully solving this task
necessitates the non-trivial integration of visual, textual, and commonsense
information. We assert that our approach, which employs free-form, open-ended
textual questions paired with bounding boxes as answers, presents a fair
challenge for contemporary multi-modal models.

The remainder of this paper is organized as follows: Section 2 provides an
overview of related work, Section 3 introduces our grounding visual question
answering dataset, Section 4 describes the annotation pipeline employed to
create the dataset, Section 5 defines the evaluation metrics and baselines
used for assessment, Section 6 presents the evaluation results for publicly-
available models and submissions in our competition, Section 7 conducts an
error analysis of both human and machine performance on our dataset, and
finally, Section 8 outlines the limitations of our work and concludes with
final remarks.

##  2 Related Work

In recent years, the scientific community has made significant progress in the
development of diverse datasets containing multi-modal data, enabling numerous
applications at the intersection of natural language processing and computer
vision. One prominent application in this domain is visual question answering
(VQA) (Antol:15, ), where models are tasked with providing textual responses
based on image-question pairs, often involving commonsense knowledge. Several
datasets have been created to facilitate research in VQA, such as GQA
(Hudson:19, ), CLEVR (CLEVR, ), and VQA v2 (VQAv2, ), which leverage MS
COCO111https://cocodataset.org/ images (Lin:14, ) (which is also the case for
our dataset).

However, the conventional VQA paradigm assumes that the output should be in
textual form. In contrast, visual grounding task requires to find a region of
an image referring to a textual description of an image. The RefClef, RefCOCO,
RefCOCO+ (RefCOCO, ), and GrIT (Kosmos-2, ) datasets are examples that
highlight the challenges of this visual grounding task. Our work lies at the
intersection of these tasks, requiring both natural language understanding to
process the question and the ability to comprehend the visual scene to detect
relevant objects. We frame the problem as a _grounding visual question
answering task_ , where the model must output an object identified by a
bounding box as the answer to the question. It is important to note that our
problem cannot be easily reduced to the standard text-only question answering
or detection based solely on textual prompts, as the answer to the question
depends on the content of the image. In grounding VQA task (Zhu:16, ; Qiao:21,
; Chen_2022_CVPR, ) one predicts the region in the image used to arrive at the
answer but not necessarily the answer itself. We guarantee that the answer is
always present, yet we firmly believe that our proposed setup presents a
formidable challenge for modern multi-modal models.

##  3 Dataset Description

Our dataset is comprised of the images associated with textual questions
(Figure 1). One entry (instance) in our dataset is a question-image pair
labeled with the ground truth coordinates of a bounding box containing the
object answering the given question. We guarantee that in most cases each
image contains one and only one correct response to the given question. The
images were obtained from a subset of the Microsoft Common Objects in Context,
MS COCO, dataset (Lin:14, ) that was licensed under the Creative Commons
Attribution (CC BY) license.

Table 1: Descriptive statistics of our dataset. There are 45,199 instances in total. Image and bounding box dimensions are in pixels. Question lengths are in characters including spaces. All numbers are 95% confidence intervals, except the number of instances. Subset | # of instances | Image | Bounding Box | Question
---|---|---|---|---
Width | Height | Width | Height | Length
train | 38,990 | $(578,581)$ | $(486,489)$ | $(103,105)$ | $(97,99)$ | $(36,38)$
public test | 1,705 | $(573,583)$ | $(483,493)$ | $(91,100)$ | $(88,97)$ | $(36,39)$
private test | 4,504 | $(578,584)$ | $(480,487)$ | $(95,101)$ | $(89,94)$ | $(36,38)$

(a) Heat map of bounding boxes in the private test subset of our dataset. Heat
maps of other subsets look similarly. (b) Diagram of the 30 most common types
of objects making 26% of the objects in our dataset.

Figure 2: Visual analysis of the ground truth bounding boxes in our dataset.

Our dataset consists of 45,199 instances, which are divided into three subsets
as shown in Table 1: _train_ (38,990 instances), _public test_ (1,705
instances), and _private test_ (4,504 instances). The names of these subsets
correspond to the different phases of the competition that we organized (refer
to Section 6 for further information). Since the public release of the entire
dataset the _train_ subset can be used as the training set, the _public test_
subset as the validation set, and _private test_ as the test set. The dataset
is provided in the form of textual files in comma-separated value (CSV)
format, containing the following information: (a) URL of an image on a public
content delivery network, (b) question in English, (c) image width and height,
and (d) bounding box coordinates (left, top, right, bottom).

We made our complete dataset, along with the baselines and ground truth
bounding boxes, publicly available on various platforms to encourage research
and development of multi-modal question answering models. The dataset can be
accessed on Zenodo,222https://doi.org/10.5281/zenodo.7057740 Hugging Face
Hub,333https://huggingface.co/datasets/toloka/WSDMCup2023
Kaggle,444https://www.kaggle.com/datasets/dustalov/toloka-wsdm-cup-2023-vqa
and GitHub.555https://github.com/Toloka/WSDMCup2023 It was released under the
same CC BY license as the MS COCO subset we used. To ensure the integrity of
the dataset and address potential concerns regarding dataset split-view
poisoning (carlini2023poisoning, ), we computed and uploaded SHA-256 hashes
for the images and electronically signed the repository commits that contain
our data files. Additionally, we have uploaded all the images to Zenodo and
Kaggle to mitigate any potential unavailability issues with the Azure content
delivery network that we utilized to store the images.

Our dataset has an equal proportion of images and questions to allow capturing
different parts of different images, making it useful for training both visual
and textual aspects of the model. Descriptive statistics of our dataset are
presented in Table 1. It is evident that the subsets share a similar
structure, with the majority of bounding boxes located near the centers of the
images (Figure 2(a)). Furthermore, we extracted portions of images from the
dataset, confined within the bounding boxes, and captioned them using BLIP-2
(blip2, ). This process resulted in textual descriptions of the selected
objects. By clustering these descriptions in the _test private_ subset, we
found that 72% of them formed 65 distinct clusters, while 28% of objects did
not belong to any cluster, demonstrating the diversity and non-triviality of
our dataset. The 30 most common types of objects enclosed in bounding boxes
are illustrated in Figure 2(b).

To further analyze the questions in our dataset, we sampled 100 random
questions from the private test subset. Then, three authors of the paper
manually annotated whether it is possible to answer the given question without
seeing an image. We aggregated the annotations by majority vote; the inter-
annotator agreement was high as indicated by Krippendorff’s $\alpha=0.87$
(Krippendorff:18, ). Our evaluation showed that only 56% of questions were
answerable without seeing an image. That is, there was a specific answer to
these questions (e.g., “What does the baseball player use to hit the ball?”)
while the rest 44% of questions have multiple answers (e.g., “What can be used
to eat food with?”) or the question is specifically about the image (e.g.,
“What is the person riding?”). Thus, our analysis shows that almost a half of
the questions cannot be answered without seeing an image.

##  4 Annotation Methodology

Figure 3: A diagram of our annotation pipeline. First, we perform an
_annotator selection_ (Section 4.1). Then, we ask the annotators to draw
_bounding boxes_ around interesting objects (Section 4.2) and to _compose
questions_ (Section 4.3). Finally, during _post-processing_ , we ask the
annotators to answer the composed image-question pairs (Section 4.4).

We performed all annotations, including the creation of bounding boxes and
questions, using the open-call task on the Toloka crowdsourcing platform. The
annotations were generated from scratch, utilizing exclusively the CC BY-
licensed images from MS COCO. The annotators were asked to select the images
containing the objects they found subjectively interesting and then compose
questions about these objects. Then, for each question-image pair, we asked
the annotators to select the answer on the image using a bounding box,
allowing us to exclude unanswerable questions. Although it was possible to
facilitate the question composition using such models as DH-GAN (Kai:21, ), we
decided to stick to the pure crowdsourcing approach. This also allowed us to
avoid synthetic data in our task and acquire the more natural formulations
made by real humans.

We adopted the well-known methodology called Find-Fix-Verify (Bernstein:10, )
for crowdsourcing creative datasets. It separates content production and
verification tasks, and enables solving both tasks using crowdsourcing at
scale. Our experience shows that the key issue in creative tasks is to ensure
that _all the annotators understand the task the same way as we do_. Thus, we
had to run multiple iterations of task design that finally resulted in seven-
stage annotation pipeline in Figure 3. We will describe these stages in four
coherent parts in the subsequent subsections. At the verification tasks the
annotator who submitted the bounding box or a question and the annotator who
verified it were two different people.

###  4.1 Annotator Selection

As composing good questions and drawing good bounding boxes imply a fair
amount of creativity, we had to select the annotators who understand and feel
the task the same way as we do. Besides this requirement, we needed the
annotators to be able to actually solve it — by being able to formulate
grammatically correct questions in English. As a result, we designed a two-
step admission procedure for annotator selection that included a language test
and a question verification task.

#### Language Test.

We had to make sure they have good reading and writing skills in English.
Thus, we designed a single-choice test of five questions that was similar to
the reading comprehension part of English exams. Each question contained a
paragraph of approximately ten complex English sentences and was provided with
four possible interpretations. Only one interpretation was correct. Since
during prototyping we found that failing this task led to further problems
with the question composition, we required the annotators to solve the test
without any mistakes.

#### Question Verification.

After the annotators passed the language test, we wanted them to get a good
understanding of what we expect them to produce. During prototyping we found
that question composition part required additional attention, so the
annotators had to solve the same verification task as described in Section
4.3: given an image, a bounding box, and a question, confirm whether the
question is well-formulated according to our strict requirements. We manually
annotated the qualification dataset for this task. Those who passed this task
were admitted for the real annotation.

###  4.2 Bounding Boxes

After sampling images from MS COCO and selecting the right annotators for our
task, we performed _bounding box annotation_ in two steps. First, we asked the
annotators to pick one large unique object in the given image and draw a tight
bounding box around it. Then, for each pair of image and bounding box, we
asked the same annotators to check the submitted bounding boxes against the
same instruction that we showed in the previous step.

###  4.3 Question Composition

After obtaining the bounding boxes, we performed the similar steps to produce
questions about the selected objects. We found this part to be the most
challenging in our entire annotation task and spent most of our pipeline
development time on it. First, given an image and a bounding box, we asked the
annotators to compose a simple question in plain English that will allow one
to find the object selected in the bounding box. Then, we asked the annotators
to check the submitted questions against the same instruction that we showed
them before. Since we have only one bounding box per image, we composed only
one question per image.

###  4.4 Post-Processing

We performed three additional steps to ensure a high quality of our dataset to
exclude poorly-formulated, leaking, and potentially offensive instances.

#### Unanswerable Questions.

After receiving the entire dataset, we decided to ask the annotators to
perform the same ask as the algorithms should: given an image and a question,
draw a bounding box around the answer. We were able to establish the
crowdsourcing baseline for further use (see Section 5 for more details). Also,
we managed to exclude from our dataset the instances for which the ground
truth bounding boxes were significantly diverging from the newly-annotated
bounding boxes.

#### Intersection Avoidance.

Since we used images from MS COCO, we explicitly checked the overlap between
bounding boxes in our dataset and in the original dataset. About 20% of them
had non-empty overlap, so we put all such instances into the train dataset.
Otherwise the dataset splits were random.

#### Offensive Content.

During the dataset inspection, we found certain unacceptable questions
suggesting offensive content. There were two prominent examples. First, there
was a question “What can hit the animals?” for an image showing two zebras in
a clearly non-hostile environment with a rock on sand.666https://toloka-
cdn.azureedge.net/wsdmcup2023/000000535978.jpg We reformulated the question.
Second, there was a photo of a zebra shot by a group of hunters with the
corresponding question. We fixed this by keyword filtering.

##  5 Metrics and Baselines

In our task, the answers correspond to bounding box coordinates, with only one
bounding box per image. Therefore, we employ the _intersection over union_
($\operatorname{IoU}$), also known as the _Jaccard index_ , as our evaluation
criterion. For the $i$-th image, we define it as follows:

$\operatorname{IoU}_{i}=\frac{I_{i}}{U_{i}}\text{,}$

where $I_{i}$ represents the intersection area between the ground truth
bounding box and the predicted bounding box, and $U_{i}$ is the union of these
boxes. Consequently, for the entire dataset of $N$ images, the evaluation
criterion is the _average intersection over union_ , denoted as
$\operatorname{AIoU}$:

$\operatorname{AIoU}=\frac{1}{N}\sum^{N}_{i=1}\operatorname{IoU}_{i}\text{.}$

For convenience, we multiply the $\operatorname{IoU}$ values by $100$. We used
the following baselines to estimate the human and machine performance on our
task. We additionally reported the prediction accuracy values that were
obtained by choosing the threshold value for $\operatorname{IoU}$ and treating
the instances for which the threshold was passed as the correct ones. We used
two common thresholds, $\operatorname{IoU}=50$ and $\operatorname{IoU}=70$,
and denote the accuracy values as $\operatorname{IoU}>50$ and
$\operatorname{IoU}>70$, correspondingly.

#### Crowdsourcing.

We evaluated how well non-expert human annotators can solve our task by
running a dedicated round of crowdsourcing annotations on Toloka. We found
them to tackle this task successfully without knowing the ground truth. On all
three subsets of our data, the average $\operatorname{IoU}$ value is
$87.124\pm 0.746$, which we consider as a _strong human baseline_ for our
task. Krippendorff’s $\alpha$ coefficients for the public test is $0.68$ and
for the private test is $0.66$, showing the decent agreement between the
responses; we used $1-\operatorname{IoU}$ as the distance metric when
calculating the $\alpha$ value.

#### OFA + SAM.

The first baseline is zero-shot and is primarily based on OFA (Wang:22, ),
combined with bounding box correction using SAM. To solve the task, we
followed a two-step zero-shot setup. First, we addressed visual question
answering, where the model was given a prompt “{question} Name an object in
the picture” along with an image. The model provided the name of a clue object
to the question. In the second step, an object corresponding to the answer
from the previous step was annotated using the prompt “which region does the
text "{answer}" describe?”, resulting in $\operatorname{IoU}=42.462$.
Subsequently, with the obtained bounding boxes, SAM generated the
corresponding masks for the annotated object, which were then transformed into
bounding boxes. This enabled us to achieve $\operatorname{IoU}=44.851$ with
this baseline.

#### OFA + SAM (VQA without Image).

We added the ablation study that answers questions without images as a new
baseline model called OFA + SAM (VQA without Image). In particular, this
method performed visual question answering by asking the question to the OFA
model with blank white image and then drawing a bounding box corresponding to
the obtained textual answer on the original image. This ablation shows that
image is important for answering questions. The results were worse than the
original OFA + SAM baseline, demonstrating $\operatorname{IoU}=39.075$ vs.
$\operatorname{IoU}=44.851$ on the private test subset of our dataset.

#### OVSeg + SAM.

Another zero-shot baseline, called OVSeg (Liang:23, ), utilizes SAM
(Kirillov:23, ) as a proposal generator instead of MaskFormer in the original
setup. This approach achieved $\operatorname{IoU}=35.073$ on the private test
subset.

#### Kosmos-2.

We also evaluated a grounding multi-modal large language model Kosmos-2
(Kosmos-2, ) in a zero-shot setup. We addressed the visual grounding task with
“Find an object which answers the question. Question: "{question}". Answer:”.
This baseline demonstrated $\operatorname{IoU}=22.571$ on private test.

#### YOLOR + CLIP.

Our last baseline used a detection model, YOLOR (Wang:21, ), to generate
candidate rectangles. Then, we applied CLIP (Radford:21, ) to measure the
similarity between the question and a part of the image bounded by each
candidate rectangle. To make a prediction, it used the candidate with the
highest similarity. This baseline method achieved $\operatorname{IoU}=21.292$
on the private test subset.

##  6 Evaluation

To assess our dataset beyond zero-shot baselines and crowd annotators, we
conducted a large-scale open-call competition at WSDM Cup, which took place
alongside the WSDM ’23 conference.777http://www.wsdm-
conference.org/2023/program/wsdm-cup To ensure fair participation, we hosted
the competition on CodaLab. Participants were given access to the complete
_train_ subset for training their models, as well as a masked _public test_
subset for the leaderboard
competition.888https://codalab.lisn.upsaclay.fr/competitions/7434 The final
rankings were determined based on performance on a concealed _private test_
subset, utilizing Docker images provided by the participants and executed on
our servers. The inference code was required to complete within one hour on an
Azure virtual machine equipped with 16 CPU cores, 200 GB of RAM, and one
NVIDIA A100 80 GB GPU. We received a total of 48 participants in our
competition, of which 9 submitted their code for the final stage. For the sake
of brevity, Table 2 reports only top-3 performance along with the above-
described baselines. We put a more complete table with the competition results
to supplementary materials. In the following paragraphs, we provide a brief
overview of the methodologies employed by the three winning teams during the
reproduction phase on the private test subset of our dataset.

Table 2: Baselines and final top-3 team standings on the _private test_ subset, obtained at the reproduction phase of our competition; for visual convenience, we multiplied the IoU values by 100; out of 48 participants, only 9 submitted their code during the reproduction phase. Baseline methods did not participate in the competition, their places are denoted as “—”. Place | Team | IoU | IoU > 50 | IoU > 70
---|---|---|---|---
— | Crowdsourcing | $87.154$ | $0.954$ | $0.914$
1 | wztxy89 | $\mathbf{76.347}$ | $\mathbf{0.834}$ | $\mathbf{0.786}$
2 | jinx, Zhouyang_Chi | $\mathbf{76.342}$ | $\mathbf{0.841}$ | $\mathbf{0.779}$
3 | komleva.ep | $\mathbf{75.591}$ | $\mathbf{0.756}$ | $\mathbf{0.772}$
— | OFA + SAM | $44.851$ | $0.470$ | $0.431$
— | OFA + SAM (VQA without Image) | $39.075$ | $0.407$ | $0.370$
— | OVSeg + SAM | $35.073$ | $0.372$ | $0.309$
— | Kosmos-2 | $22.571$ | $0.243$ | $0.073$
— | YOLOR + CLIP | $21.292$ | $0.209$ | $0.201$

3rd Place.

The only single-person winning team, komleva.ep, fine-tuned the pre-trained
multi-modal OFA model (Wang:22, ) on the competition dataset. In order to
increase the prediction quality, this team additionally used data from the
pre-processed GQA dataset (Hudson:19, ).

2nd Place.

The team jinx, Zhouyang_Chi devised a three-step pipeline solution. First, at
the _coarse tuning_ step, they generated textual pseudo answers for the
questions and tuned the OFA model to produce textual answers. Then, at the
_fine tuning_ step, they used prompt engineering of the coarse-tuned OFA model
to draw the bounding boxes. Finally, at the _post-processing_ step, they ran
an ensemble of these coarse- and fine-tuned models to propose and select the
best bounding box candidate.

1st Place.

The wztxy89 team created a variant detector using Uni-Perceiver as the multi-
modal backbone network (Zhu:22, ), with ViT-Adapter for cross-modal
localization (Chen:23, ), and DINO as the prediction head (Zhang:23, ). They
also included an auxiliary loss (Kirillov:19, ) and a test-time augmentation
module for improved performance, which helped them win the challenge
(gao2023champion, ).

Even though the winning systems significantly outperformed our machine
learning baselines, no system approached the non-expert level of human
performance in our task.

##  7 Error Analysis

Table 3: Distribution of error types of the crowdsourcing baseline and top-3 models from our challenge as described in Section 6. The analysis is based on a random sample of 100 _most challenging images_. Error Class | Crowdsourcing | 1st Place | 2nd Place | 3rd Place
---|---|---|---|---
Small Object | 26 | 13 | 13 | 11
Insignificant Error | 19 | 13 | 12 | 16
Wrong Object Predicted | 5 | 24 | 24 | 20
Inaccurate Ground Truth | 11 | 9 | 9 | 7
Inaccurate Prediction | 7 | 6 | 7 | 8
Wrong Question, Correct Prediction | 20 | 12 | 13 | 14
Wrong Question, Incorrect Prediction | 0 | 8 | 7 | 8
Question Ambiguity | 12 | 15 | 15 | 16

(a) What helps to tie hair? Small Object. (b) What is a device for giving
light, one consisting of an electric bulb together with its holder ?
Insignificant Error. (c) Which beverage is made of grapes? Wrong Object
Prediction. (d) What do you play with on a windy day? Inaccurate Ground Truth.
(e) What is used to direct the traffic? Inaccurate Prediction. (f) What can I
open to let fresh air into the room? Wrong Question, Correct Prediction. (g)
Where can I get supplies? Wrong Question, Incorrect Prediction. (h) What can
we wear? Question Ambiguity.

Figure 4: Typical examples of error classes we observed during the analysis.
Image captions include the associated questions followed by the error class
labels and are provided. In the images, predictions are red-colored and ground
truth is green-colored.

Before performing error analysis, we evaluated whether the errors made by
three top-performing systems were similar or not. We took their predictions on
the _private test_ subset and then computed the Krippendorff’s $\alpha$
coefficient similarly to Section 5. The coefficient value of $0.77$
demonstrated a moderate agreement between responses of all three systems. As
this indicates that all the three systems tend to produce similar correct and
incorrect responses, we further analyzed the errors made by these systems and
our crowdsourcing baseline as reported in Section 6.

First, we sampled the data instances from the private test set where
$\operatorname{IoU}$ of humans and models was less than $80$, which resulted
in 355 out of 4,504 instances (approximately 8%). This sample is heavy biased
towards the most challenging instances as all the models showed poor results
on them; it is _not representative of the entire dataset_. Out of these 355,
we sampled 100 instances and manually evaluated the quality of the obtained
bounding boxes. This provided us with 100 judgements per method. We identified
the following eight error classes as summarized in Table 3 and Figure 4:

  * •

Small Object. The target object is very small, thus it was difficult to draw a
bounding box precisely because of the low resolution.

  * •

Insignificant Error. The difference between prediction and ground truth is
marginal (roughly, it means that $\operatorname{IoU}$ was greater than $70$).

  * •

Wrong Object Predicted. The prediction is entirely incorrect, so
$\operatorname{IoU}$ was zero.

  * •

Inaccurate Ground Truth. The prediction is more accurate than ground truth.

  * •

Inaccurate Prediction. The prediction is significantly less accurate than
ground truth.

  * •

Wrong Question, Correct Prediction. The ground truth does not answer the
question but the corresponding prediction does.

  * •

Wrong Question, Incorrect Prediction. Neither the ground truth nor the
prediction answer the question.

  * •

Question Ambiguity. The question might not have a single correct answer (for
example, when there are several objects answering the same question). Also, we
notice a few cases when the question is unclear or ambiguous (e.g., “What is
he doing”).

Having compared the predictions of the crowd annotators and top-performing
machine learning systems, we noticed three facts. First, _it was especially
difficult for crowd to draw a bounding box around small objects_ (the number
of such errors is much higher than for models). Second, _the models make a
completely wrong prediction more often than the crowd_. However, even when the
prediction is incorrect, the models still predict some object on the image and
not just a random bounding box. Third, _a significant amount of crowd errors
is caused by the wrong or ambiguous question_. In most of such cases the crowd
gives a correct answer. This is inevitable in crowdsourced datasets even with
rigorous quality control approach like we used. It is worth noting that this
observation is only applicable to the cases where all four approaches fail to
make a good prediction (only $8\%$ of the data).

##  8 Conclusion

In our grounding visual question answering task, the inputs consisted of an
image and a question, with the output being the corresponding bounding box.
While the top-performing systems showed remarkable improvement compared to the
baselines, none of them surpassed non-expert annotators by a significant
margin. We consider this fact important, as it indicates that our benchmark
remains relevant until larger multi-modal models become accessible. The entire
dataset, except for the images themselves, was generated through crowdsourcing
on the Toloka platform, rendering it a valuable resource for the creation of
demanding benchmarks. As a future work, we consider increasing the dataset
size and adjusting our annotation pipeline to produce questions on different
regions in the same image.

We foresee the following potential downstream applications of our dataset and
derivative models beside the evaluation of machine learning models:

  * •

Visual Search. With accurate bounding boxes, grounding VQA enables better
understanding and recognition of objects in images, allowing users of
e-commerce platforms to query products based on their appearance rather than
relying only on text-based search.

  * •

Augmented Reality (AR). Accurate bounding box annotation can help in
integrating virtual objects into real-world scenes during AR applications.
Grounding VQA aids in object recognition and aligning virtual content with
real-world objects, and can assist in image annotation, making it easier to
search images based on specific object queries.

  * •

Robotics. For robots to interact with objects in their environment
effectively, accurate object localization is crucial. grounding VQA can be
utilized to identify and track objects, enabling robots to navigate, grasp,
and manipulate objects in a more intelligent and precise manner.

However, our dataset has the following limitations:

  * •

Dataset Bias. We only consider images from MS COCO, which itself may contain
biases related to gender and race. Additionally, the questions and selected
objects chosen by annotators may introduce bias or have limited variability,
potentially limiting the generalizability of models trained on this dataset.

  * •

English-Only Questions. This dataset focuses solely on English questions.
However, this narrow focus may restrict the ability of models to handle other
languages and cultures.

  * •

Real-World Applications. Since there are no production-level applications of
the proposed grounding VQA setup yet, future real-world applications may
involve more complex questions that require deeper understanding, reasoning,
and context awareness.

We wish to highlight certain potential negative social impacts of models
trained on our dataset:

  * •

Reinforcing Bias. Due to potential biases present in the dataset, models
trained on it may inadvertently perpetuate societal inequalities and
discrimination when deployed in real-world applications.

  * •

Ethical Use of Models. As grounding VQA models become more advanced, they can
be exploited for malicious purposes, such as privacy invasion. It is crucial
to establish proper safeguards and guidelines to prevent misuse and protect
individuals’ rights and well-being.

#### Acknowledgements.

This work would not have been possible without the collaborative efforts of
people from different teams in Toloka. Individuals listed in each contribution
role are arranged alphabetically based on their surnames. We thank Ekaterina
Fedorenko, Natalia Fedorova, Ujwal Gadiraju, Valentina Mikhno, and Evgeniya
Sukhodolskaya for helping in organizing our competition at WSDM Cup. We
acknowledge the invaluable efforts of Oleg Pavlov, Mikhail Potalitsyn, and
Rosmiyana Shekhovtsova, whose expertise was crucial for the annotation
pipeline design. We express gratitude to Anastasia Egupova, Aleksei
Gerasimenko, Timur Pevzner, Kuen Pham, Ekaterina Saenko, and Anna Stepanova
for their help in raising awareness of the competition among the community,
allowing to attract 48 participants from across the world. We are grateful to
Egor Babkin, Dmitry Lekomtsev, and Andrei Voitovich for building the Web
presence of our competition. We acknowledge the invaluable contribution of
Tatiana Ignatova, Daria Kalakina, and Victoriya Vidma in navigating complex
legal and financial aspects. Last but not least, we would like to thank the
CodaLab and the WSDM Cup teams, especially Hady W. Lauw, and the competition
participants, for making it a big success.

## References

  * [1] Stanislaw Antol, Aishwarya Agrawal, Jiasen Lu, Margaret Mitchell, Dhruv Batra, C. Lawrence Zitnick, and Devi Parikh.  VQA: Visual Question Answering.  In 2015 IEEE International Conference on Computer Vision, ICCV 2015, Santiago, Chile, December 7-13, 2015, pages 2425–2433. IEEE Computer Society, 2015.
  * [2] Michael S. Bernstein, Greg Little, Robert C. Miller, Björn Hartmann, Mark S. Ackerman, David R. Karger, David Crowell, and Katrina Panovich.  Soylent: A Word Processor with a Crowd Inside.  In Proceedings of the 23Nd Annual ACM Symposium on User Interface Software and Technology, UIST ’10, pages 313–322, New York, NY, USA, 2010. ACM.
  * [3] Nicholas Carlini, Matthew Jagielski, Christopher A. Choquette-Choo, Daniel Paleka, Will Pearce, Hyrum Anderson, Andreas Terzis, Kurt Thomas, and Florian Tramèr.  Poisoning Web-Scale Training Datasets is Practical, 2023.
  * [4] Chongyan Chen, Samreen Anjum, and Danna Gurari.  Grounding Answers for Visual Questions Asked by Visually Impaired People.  In IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2022, New Orleans, LA, USA, June 18-24, 2022, pages 19076–19085. IEEE, 2022.
  * [5] Zhe Chen, Yuchen Duan, Wenhai Wang, Junjun He, Tong Lu, Jifeng Dai, and Yu Qiao.  Vision Transformer Adapter for Dense Predictions.  The Eleventh International Conference on Learning Representations, 2023.
  * [6] Shengyi Gao, Zhe Chen, Guo Chen, Wenhai Wang, and Tong Lu.  Champion Solution for the WSDM2023 Toloka VQA Challenge, 2023.
  * [7] Yash Goyal, Tejas Khot, Douglas Summers-Stay, Dhruv Batra, and Devi Parikh.  Making the V in VQA Matter: Elevating the Role of Image Understanding in Visual Question Answering.  In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017, pages 6325–6334. IEEE Computer Society, 2017.
  * [8] Drew A. Hudson and Christopher D. Manning.  GQA: A New Dataset for Real-World Visual Reasoning and Compositional Question Answering.  In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019, pages 6700–6709. Computer Vision Foundation / IEEE, 2019.
  * [9] Justin Johnson, Bharath Hariharan, Laurens van der Maaten, Li Fei-Fei, C. Lawrence Zitnick, and Ross B. Girshick.  CLEVR: A Diagnostic Dataset for Compositional Language and Elementary Visual Reasoning.  In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017, pages 1988–1997. IEEE Computer Society, 2017.
  * [10] Shen Kai, Lingfei Wu, Siliang Tang, Yueting Zhuang, Zhen He, Zhuoye Ding, Yun Xiao, and Bo Long.  Learning to Generate Visual Questions with Noisy Supervision.  In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 11604–11617, 2021.
  * [11] Sahar Kazemzadeh, Vicente Ordonez, Mark Matten, and Tamara Berg.  ReferItGame: Referring to Objects in Photographs of Natural Scenes.  In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 787–798, Doha, Qatar, 2014. Association for Computational Linguistics.
  * [12] Alexander Kirillov, Ross B. Girshick, Kaiming He, and Piotr Dollár.  Panoptic Feature Pyramid Networks.  In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019, pages 6399–6408. Computer Vision Foundation / IEEE, 2019.
  * [13] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C Berg, Wan-Yen Lo, et al.  Segment anything.  arXiv preprint, abs/2304.02643, 2023.
  * [14] Klaus Krippendorff.  Content Analysis: An Introduction to Its Methodology.  SAGE Publications, Inc, Thousand Oaks, CA, USA, 4th edition, 2018.
  * [15] Junnan Li, Dongxu Li, Silvio Savarese, and Steven Hoi.  BLIP-2: Bootstrapping Language-Image Pre-training with Frozen Image Encoders and Large Language Models.  In ICML, 2023.
  * [16] Feng Liang, Bichen Wu, Xiaoliang Dai, Kunpeng Li, Yinan Zhao, Hang Zhang, Peizhao Zhang, Peter Vajda, and Diana Marculescu.  Open-vocabulary semantic segmentation with mask-adapted clip.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7061–7070, 2023.
  * [17] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitnick.  Microsoft COCO: Common Objects in Context.  In Computer Vision – ECCV 2014, pages 740–755, Cham, Switzerland, 2014. Springer International Publishing.
  * [18] Zhiliang Peng, Wenhui Wang, Li Dong, Yaru Hao, Shaohan Huang, Shuming Ma, and Furu Wei.  Kosmos-2: Grounding Multimodal Large Language Models to the World.  arXiv, abs/2306, 2023.
  * [19] Yanyuan Qiao, Chaorui Deng, and Qi Wu.  Referring Expression Comprehension: A Survey of Methods and Datasets.  IEEE Transactions on Multimedia, 23:4426–4440, 2021.
  * [20] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever.  Learning Transferable Visual Models From Natural Language Supervision.  In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 8748–8763. PMLR, 2021.
  * [21] Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever.  Zero-Shot Text-to-Image Generation.  In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 8821–8831. PMLR, 2021.
  * [22] 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 Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 3261–3275, 2019.
  * [23] Chien-Yao Wang, I-Hau Yeh, and Hong-Yuan Mark Liao.  You Only Learn One Representation: Unified Network for Multiple Tasks.  arXiv preprint, abs/2105.04206, 2021.
  * [24] Peng Wang, An Yang, Rui Men, Junyang Lin, Shuai Bai, Zhikang Li, Jianxin Ma, Chang Zhou, Jingren Zhou, and Hongxia Yang.  OFA: Unifying Architectures, Tasks, and Modalities Through a Simple Sequence-to-Sequence Learning Framework.  In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 23318–23340. PMLR, 2022.
  * [25] Hao Zhang, Feng Li, Shilong Liu, Lei Zhang, Hang Su, Jun Zhu, Lionel Ni, and Heung-Yeung Shum.  DINO: DETR with Improved DeNoising Anchor Boxes for End-to-End Object Detection.  The Eleventh International Conference on Learning Representations, 2023.
  * [26] Wangchunshu Zhou, Yan Zeng, Shizhe Diao, and Xinsong Zhang.  VLUE: A Multi-Task Multi-Dimension Benchmark for Evaluating Vision-Language Pre-training.  In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 27395–27411. PMLR, 2022.
  * [27] Xizhou Zhu, Jinguo Zhu, Hao Li, Xiaoshi Wu, Hongsheng Li, Xiaohua Wang, and Jifeng Dai.  Uni-Perceiver: Pre-training Unified Architecture for Generic Perception for Zero-shot and Few-shot Tasks.  In IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2022, New Orleans, LA, USA, June 18-24, 2022, pages 16783–16794. IEEE, 2022.
  * [28] Yuke Zhu, Oliver Groth, Michael S. Bernstein, and Li Fei-Fei.  Visual7W: Grounded Question Answering in Images.  In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pages 4995–5004. IEEE Computer Society, 2016.

##  Appendix A Competition Results at WSDM Cup 2023

The competition website was located at https://toloka.ai/challenges/wsdm2023/,
while the leaderboard and scoring were performed on the CodaLab platform:
https://codalab.lisn.upsaclay.fr/competitions/7434. Before the start of the
competition, all the parts of our dataset were frozen and did not change
during the competition.

Our competition had three key phases: the practice phase, the evaluation
phase, and the reproduction phase (Table 4). In September, we started the
_practice_ phase to let the contestants get used to the task and training
data, including the ground truth data. Then, we started the _evaluation_ phase
using the public test dataset without ground truth labels. The contestants had
to submit their predictions to the competition platform, which resulted in
leaderboard updates. Finally, for the sake of reproducibility, soon after the
end of the evaluation phase, we started the _reproduction_ phase. In this
phase, we asked the contestants to provide their solution as a container
image. We ran their code to obtain answers for the private test dataset to
determine the winners.

Table 5 shows the competition results. Even though the participants managed to
improve dramatically upon our baselines, none of the participating systems
outperformed our crowdsourcing baseline.

Table 4: Complete timeline of our competition at WSDM Cup 2023 Event | Date
---|---
Practice Starts | September 16, 2022
Evaluation Starts | September 30, 2022
Evaluation Ends | December 16, 2022
Reproduction Starts | December 19, 2022
Reproduction Ends | January 16, 2023
Post-Competition Starts | January 16, 2023
WSDM Cup Workshops | March 3, 2023
Table 5: Baselines and final team standings on the _private test_ subset, obtained at the reproduction phase of our competition; for visual convenience, we multiplied the IoU values by 100; out of 48 participants, only 9 submitted their code during the reproduction phase. Baseline methods did not participate in the competition, their places are denoted as “—”. Place | Team | IoU
---|---|---
— | Crowdsourcing | $87.154$
1 | wztxy89 | $\mathbf{76.347}$
2 | jinx, Zhouyang_Chi | $\mathbf{76.342}$
3 | komleva.ep | $\mathbf{75.591}$
4 | xexanoth | $74.667$
5 | Man_of_the_year | $72.768$
6 | Haoyu_Zhang, KhylonWong | $71.998$
7 | nika-li | $70.525$
8 | blinoff | $62.037$
9 | Ndhuynh | $61.247$
— | OFA + SAM | $44.851$
— | OFA + SAM (without Image) | $39.075$
— | OVSeg + SAM | $35.073$
— | Kosmos-2 | $22.571$
— | YOLOR + CLIP | $21.292$

##  Appendix B Annotator Instructions and Interfaces

Our annotation pipeline consisted of four phases, each corresponding to an
annotation project: “Find an Interesting Object” for initial bounding box
selection of objects in images, “Verify Object Selection” to confirm if the
selected objects met the requirements, “Ask a Question about the Object” for
generating questions about the selected objects, and “Verify Questions About
Objects” to validate if the written questions met the requirements. We provide
a screenshot of our language test in Figure 5 and screenshots of our main
annotation tasks in Figure 6, 7, 8, and 9.

Figure 5: Screenshot of the interface of the language test assignment. Figure
6: Screenshot of the “Find an Interesting Object” annotation interface. Figure
7: Screenshot of the “Verify Object Selection” annotation interface. Figure 8:
Screenshot of the “Ask a Question about the Object” annotation interface.
Figure 9: Screenshot of the “Verify Questions About Objects” annotation
interface.


# Matching through Embedding in Dense Graphs

Nitish K. Panigrahy
University of Massachusetts Amherst
Amherst, MA 01003
<EMAIL_ADDRESS>
&Prithwish Basu
Raytheon BBN Technologies
Cambridge, MA 02138
<EMAIL_ADDRESS>
&Don Towsley
University of Massachusetts Amherst
Amherst, MA 01003
<EMAIL_ADDRESS>

###### Abstract

Finding optimal matchings in dense graphs is of general interest and of
particular importance in social, transportation and biological networks. While
developing optimal solutions for various matching problems is important, the
running times of the fastest available optimal matching algorithms are too
costly. However, when the vertices of the graphs are point-sets in
$\boldsymbol{\mathbb{R}^{d}}$ and edge weights correspond to the euclidean
distances, the available optimal matching algorithms are substantially faster.
In this paper, we propose a novel _network embedding_ based heuristic
algorithm to solve various matching problems in dense graphs. In particular,
using existing network embedding techniques, we first find a low dimensional
representation of the graph vertices in $\boldsymbol{\mathbb{R}^{d}}$ and then
run faster available matching algorithms on the embedded vertices. To the best
of our knowledge, this is the first work that applies network embedding to
solve various matching problems. Experimental results validate the efficacy of
our proposed algorithm.

##  1 Introduction

Matching in graphs is one of the most well-studied problems in economics and
computer science. This is an ubiquitous problem with application areas ranging
from transportation networks [2] to social networks [5], and computational
chemistry [9]. For instance, in the case of social networks, tag suggestions
and localization problems for images can be transformed into a weighted
bipartite graph matching problems [5]. Similarly, the processes of de-
anonymization and privacy inference in social networks can be reduced to
finding the maximum weighted bipartite matching of the corresponding knowledge
graph [20].

Given a graph $G=(V,E)$, a matching $M$ is a subset of edges such that no two
edges in $M$ share a common vertex. The matching $M$ is _perfect_ if every
$v\in V$ belongs to an edge of $M$. For weighted graphs, it is often required
to compute a perfect matching that is optimal with respect to some criterion.
Given a real weight $w_{e}$ for each edge $e\in E,$ a _minimum cost_ matching
(MCM) minimizes $\sum_{e\in M}w_{e}$ among all feasible perfect matchings $M$
for $G.$ Similarly, a bottleneck matching (BM) minimizes $\max_{e\in M}w_{e}$
while a _uniform matching_ (UM) minimizes $\max_{e\in M}w_{e}-\min_{e\in
M}w_{e}.$ A _minimum deviation_ matching (MDM) minimizes $(1/|V|\sum_{e\in
M}w_{e})-\min_{e\in M}w_{e}.$

A plethora of work has been done to develop efficient algorithms for obtaining
optimal solutions for various matchings. However, for many real-world problems
with larger graphs [3, 17], the running times of the fastest available
matching algorithms are too costly. For example, the best known algorithm for
the minimum cost matching problem runs in $O(n^{3})$ time for a dense graph
with $n$ vertices [14]. For massive graphs, this is quite inefficient. Thus
designing efficient approximate algorithms permit the solution of large
instances of matching problems that arise in practical situations.

Graph Type | Matching Type | Algo. | Algo. Type | Complexity
---|---|---|---|---
Bipartite | Minimum Cost (MCM) | Kuhn et al. [14] | Non-Euclidean | $O(n^{3})$
|  | Agarwal et al. [1] | Euclidean-$\boldsymbol{\mathbb{R}^{d}}$ | $\boldsymbol{O(n^{2+\epsilon})}$
Bipartite | Bottleneck (BM) | Punnen et al. [19] | Non-Euclidean | $O(n^{2}\sqrt{n})$
|  | Efrat et al. [7] | Euclidean-$\boldsymbol{\mathbb{R}^{d}}$ | $\boldsymbol{O(n^{1.5}\log^{d}n)}$
Bipartite | Uniform (UM) | Martello et al. [16] | Non-Euclidean | $O(n^{4})$
|  | Efrat et al. [7] | Euclidean | $\boldsymbol{O(n^{10/3})}$
Bipartite | Minimum Deviation (MDM) | Efrat et al. [6] | Non-Euclidean | $O(n^{4})$
|  | Efrat et al. [7] | Euclidean | $\boldsymbol{O(n^{10/3})}$
Non-bipartite | Minimum Cost (MCM) | Gabow et al. [11] | Non-Euclidean | $O(nm+n^{2}\log n)$
|  | Varadarajan et al. [22] | Euclidean-$\boldsymbol{\mathbb{R}^{d}}$ | $\boldsymbol{O(n^{1.5}\log n)}$
Non-bipartite | Bottleneck (BM) | Gabow et al. [10] | Non-Euclidean | $O(m\sqrt{n\log n})$
|  | Efrat et al. [8] | Euclidean-$\boldsymbol{\mathbb{R}^{d}}$ | $\boldsymbol{O\left(n^{2-2/(\lceil d/2\rceil+1)+\epsilon}\right)}$
Table 1: Running time complexities of various optimal matching algorithms.

There exist many constant factor approximation algorithms for the maximum
weight matching (MWM) problem. However, there is no such algorithm for the
minimum cost matching (MCM) problem. The greedy heuristic for the MCM problem,
attempts to construct a minimum cost perfect matching by starting with an
empty matching and iteratively adding a minimum weight edge between two
exposed nodes. While the running time complexities of various greedy matching
algorithms are generally linear in terms of the number of edges ($m$), the
corresponding approximation ratios are high. The greedy heuristic runs in
$O(m\log n)$ time and finds a solution with cost at most $4/3\;n^{\log 3/2}$
times the optimum cost [21]. [12] developed an $O(m)$ heuristic that
constructs a matching with cost at most $2n^{\log_{3}7/3}$ times the optimum
cost. Thus one should focus on designing efficient approximate algorithms with
good performance guarantees.

While for non-Euclidean graphs the running time complexities of optimal
matching algorithms are high, the available optimal matching algorithms are
substantially faster for the Euclidean case, i.e. when the vertices of the
graph are point sets in $\mathbb{R}^{d}$ and edge weights corresponds to
euclidean distances. For example, the best known algorithm for the bottleneck
matching problem runs in $O(n^{1.5}\log^{d}n)$ time for a bipartite Euclidean
graph as compared to an $O(n^{2.5})$ for its non-Euclidean counterpart. Thus
the following natural question arises. _Can we leverage Euclidean matching
techniques to obtain near-optimal solutions to non-Euclidean matching
problems?_

In this work, we propose a _network embedding_ based algorithm to obtain
approximate solutions to non-Euclidean matching problems. More precisely,
using existing linear time network embedding techniques, we embed the vertices
of the non-Euclidean graph into points in $\mathbb{R}^{d}$ such that the
neighborhood of the vertices are approximately preserved. We then run faster
available Euclidean matching algorithms on the embedded vertices. To the best
of our knowledge, this is the first work that applies network embedding to
solve various matching problems. Empirical results show the efficacy of our
proposed algorithm.

##  2 Technical Preliminaries

We consider the problem of finding approximate solutions to optimal matching
problem in complete bipartite and general graphs111We assume the graph to be
sufficiently dense for the case when it is not complete. In such a case, we
can add $O(1)$ edges each with infinite costs to the graph to make it complete
without affecting the overall running time complexity.. We denote the graph as
$G=(V,E)$ with $E\subset V\times V.$ Here, $V$ denotes the vertex set and $E$
denotes the edge set. We assign a real weight $w_{e}$ to each edge $e\in E.$ A
matching $M\subset E$ is defined to be a set of edges such that no vertex of
$G$ is incident to more than one edge of $M$. Denote $|V|=n$ and $|E|=m.$ Our
goal is to compute a perfect matching that is near-optimal with respect to
optimality criterion defined in the previous Section.

###  2.1 Geometry Helps in Matching

A summary of the running time complexities of various optimal matching
algorithms in Euclidean and non-Euclidean setting is given in Table 1. Note
that, bipartite matching is a special case of general graph matching.
Computing an optimal bipartite matching is more challenging than computing an
optimal matching on a complete non-bipartite graph in a Euclidean setting. For
example, MCM on a set of $2n$ points can be computed in $O(n^{1.5}\log n)$
time, while the best known algorithm for computing MCM between two point sets
of size $n$ each takes $O(n^{2+\epsilon})$ time. Also note that, there is
considerable amount of savings in terms of running times in the Euclidean
setting as compared to the non-Euclidean setting. For instance, MCM on a non-
Euclidean non-bipartite complete graph runs in $O(n^{3})$ time where as MCM on
a Euclidean non-bipartite complete graph runs in $O(n^{1.5}\log n)$ time.
Similar savings can be observed for many other matching problems, such as BM,
UM and MDM. Below we transform the non-Euclidean matching problem into a
Euclidean one through network embedding.

##  3 Our Approach: Matching through Embedding

Given a graph $G$, we aim to learn a _representation_ of $V$ in a low-
dimensional vector space $\mathbb{R}^{d}$, i.e., find a map
$f:V\to\mathbb{R}^{d}$ such that the neighborhoods of nodes are approximately
preserved. This allows us to execute matching algorithms on the set of vectors
instead of doing that on $G$ itself. Below we present two network embedding
techniques available from literature.

  * •

Deep Walk [18]: As a homogeneous network embedding method, DeepWalk performs
uniform random walks to get a corpus of vertex sequences. Then the word2vec is
applied on the corpus to learn vertex embeddings.

  * •

Node2Vec [13]: This method extends DeepWalk by performing biased random walks
to generate the corpus of vertex sequences. The hyper-parameters $p$ and $q$
can be set to different values.

We construct the embedded graph $G^{\prime}(V^{\prime},E^{\prime})$ as
follows. We let $V^{\prime}=\\{f(v),\forall v\in V\\}.$ Also, we let
$E^{\prime}=\\{(f(u),f(v)),\forall(u,v)\in E\\}.$ We then define weight of an
edge $e^{\prime}=(u^{\prime},v^{\prime})\in E^{\prime}$ as
$w_{e^{\prime}}=||u^{\prime}-v^{\prime}||_{2}.$ Clearly $G^{\prime}$ is a
Euclidean graph in dimension $d.$ We then apply available optimal Euclidean
matching algorithms on $G^{\prime}$ to obtain a matching $M^{\prime}.$ We
output $M^{\prime}$ as the approximate solution to the optimal matching
problem on $G.$

######  Remark 1.

Note that, the above mentioned embedding techniques can learn the
representation of $V$ in $O(n\log n)$ time[4]. Thus the overall time
complexity of the proposed algorithm is equal to that of the corresponding
Euclidean matching algorithm.

##  4 Empirical Results

In this section we present experiments on several synthetic datasets.

Figure 1: Adversarial model for assigning edge weights with $n=16$ [21].

(a)

(b)

(c)

(d)

(e)

(f)

Figure 2: Performance comparison of our proposed algorithm to that of greedy
for (a) MCM (b) BM under adversarial model and (c) MCM under lomax model.
(d)-(f) Parameter sensitivity of the proposed algorithm under adversarial
model.

For synthetic datasets, we vary the distributions of edge weights. We compare
the performance of our proposed heuristic algorithm to that of the greedy
heuristic under two models based on generating edge weights. First, we
consider an adversarial model. Under this model, edge weights are generated
according to [21] and as shown in Figure 1. We set $n=2^{t-1}$ with $t$ being
the number of clusters of nodes and the largest distance between adjacent
nodes is set to $3^{t-2}.$ Under the adversarial model, the greedy heuristic
finds a solution with cost $O(n^{\log 3/2})$ times the optimum cost [21].
Next, we consider the Lomax distribution (a long tail distribution) [15] for
generating the weights since they are widely used in real-world applications
[23]. We chose the Lomax distribution parameter from the set
$\\{2,3,5,10,50\\}$. The parameter settings are motivated by [23, 13]. We set
the number of walks per node and length of each random walk to $20$ for both
deepWalk and node2vec. The embedding number of dimensions, return ($p$) and
in-out parameter ($q$) are set to $10,0.5$ and $2.0$ respectively. The
experiments are repeated $5$ times for each parameter setting and the $95\%$
confidence interval plots are reported. If not mentioned, in our experiments,
n = 100 and m = 4950 for non-bipartite graphs. We focus on MCM and BM
algorithms in non-bipartite setting. We get similar results for bipartite
graphs and hence omit them here.

###  4.1 Effect of Edge Weight Distribution

We first present the results for MCM and BM under adversarial model as shown
in Figures 2(a) and (b) respectively. We plot the approximation ratios of
various matching algorithms as a function of number of nodes in the graph. For
both MCM and BM, the proposed node2vec and deepWalk based algorithms yield
lower approximation ratio, hence better performance compared to greedy
heuristic. Also, as the number of nodes increases, the performance of greedy
heuristic decreases while that of embedding based techniques increases. One
possible explanation for better performance of the embedding based techniques
is due to their ability to learn the inherent one-dimensional structure of the
adversarial model. However, the nature of the plots are reversed for MCM under
the Lomax distribution model as shown Figure 2 (c). In this case, greedy beats
both deepWalk and node2vec based algorithms. Note that, as the Lomax
distribution parameter increases, both embedding based techniques gradually
perform better and finally converge to the greedy solution.

###  4.2 Parameter Sensitivity

The embedding based matching algorithms involve a number of parameters. Below,
we examine the effect of different parameters on the overall performance of
embedding based techniques under adversarial model as shown in Figures 2
(d)-(f). All other parameters assume default values, except for the parameter
being examined. We measure the approximation ratio as a function of number and
length of walks per node, number of dimensions. The performance of both
node2vec and deepWalk increase with the number, length of walks per node and
number of dimensions as expected. Again, node2vec beats deepWalk across all
values of parameters.

##  5 Conclusion

In this paper, we developed approximate solutions for various matching
problems on dense graphs. More precisely, we proposed a network embedding
based heuristic algorithm using existing network embedding techniques. We also
performed simulations on synthetic datasets to obtain comparison results for
empirical approximation ratios across different proposed and existing matching
algorithms. Future directions include to consider the effect of other non-
random walk based embedding techniques on the overall performance of the
proposed algorithm.

##  6 Acknowledgment

This research was sponsored by the U.S. ARL and the U.K. MoD under Agreement
Number W911NF-16-3-0001 and by the NSF under Grant CNS-1617437. 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 National Science Foundation, U.S. ARL or the U.K. MoD. This
document does not contain technology or technical data controlled under either
the U.S. International Traffic in Arms Regulations or the U.S. Export
Administration Regulations.

## References

  * [1] P. K. Agarwal, A. Efrat, and M. Sharir.  Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications.  In Proc. 11th Annu. ACMSympos. Comput. Geom., pages 39–50, 1995\.
  * [2] A. Aggarwal, A. Barnoy, S. Khuller, D. Kravets, and B. Schieber.  Efficient minimum cost matching using quadrangle inequality.  Journal of Algorithms, 19:116–143, 1995.
  * [3] R. Beier and J. F. Sibeyn.  A powerful heuristic for telephone gossiping.  In Proceedings of the 7th Colloquium on Structural Information and Communication Complexity, pages 17–35, 2000.
  * [4] H. Chen, Y. Hu, B. Perozzi, and S. Skiena.  HARP: Hierarchical representation learning for networks.  32nd AAAI Conference on Artificial Intelligence, AAAI 2018, pages 2127–2134, 2018.
  * [5] W. T. Chu, C. J. Li, and J. Y. Yu.  Tag suggestion and localization for images by bipartite graph matching.  2013 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference, APSIPA 2013, 2013.
  * [6] A. Efrat.  Geometric Location Optimization.  Ph.D. Dissertion, Tel-Aviv University, 1998.
  * [7] A. Efrat, M. Itai, and M. Katz.  Geometry helps in bottleneck matching and related problems.  Algorithmica, 31:1–28, 2001.
  * [8] A. Efrat and M. Katz.  Computing euclidean bottleneck matchings in higher dimensions.  Information Processing Letters, 75:169–174, 2000.
  * [9] H. Frohlich, J. K. Wegner, and A. Zell.  Assignment kernels for chemical compounds.  IJCNN, 2005.
  * [10] H. N. Gabow, , and R. E. Tarjan.  Algorithms for Two Bottleneck Optimization Problems.  J. Algorithms, 9:411–417, 1988.
  * [11] H. N. Gabow.  Data Structures for Weighted Matching and Nearest Common Ancestors with Linking.  Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 434–443, 1990.
  * [12] M. D. Grigoriadis and B. Kalantari.  A new class of heuristic algorithms for weighted perfect matching.  J. Assoc. Comput. Mach., 35:769–776, 1988.
  * [13] A. Grover and J. Leskovec.  node2vec: Scalable Feature Learning for Networks.  KDD, pages 855–864, 2016.
  * [14] H. W. Kuhn.  The Hungarian Method for the Assignment Problem.  Naval Research Logistics Quarterly, 2:83–97, 1955.
  * [15] K. S. Lomax.  Business Failures; Another example of the analysis of failure data.  Journal of the American Statistical Association, 49:847–852, 1954\.
  * [16] S. Martello, W. R. Pulleyblank, P. Toth, and D. Werra.  Balanced optimization problems.  Operations Research Letters, 3:275–278, 1984.
  * [17] B. Monien, R. Preis, and R. Diekmann.  Quality matching and local improvement for multilevel graph-partitioning.  Paral. Comput., 26:1609–1634, 2000.
  * [18] B. Perozzi and S. Skiena.  DeepWalk: Online Learning of Social Representations.  KDD, 2014.
  * [19] A. P. Punnen, , and K. P. Nair.  Improved Complexity Bound for the Maximum Cardinality Bottleneck Bipartite Matching Problem.  Discrete Applied Mathematics, 55:91–93, 1994.
  * [20] J. Qian, X. Y. Li, C. Zhang, and L. Chen.  De-anonymizing social networks and inferring private attributes using knowledge graphs.  Proceedings - IEEE INFOCOM, 2016-July, 2016.
  * [21] E. M. Reingold and R. E. Tarjan.  On a greedy heuristic for complete matching.  SIAM J. Comput., 10:676–681, 1981.
  * [22] K. R. Varadarajan.  A divide-and-conquer algorithm for min-cost perfect matching in the plane.  In Proc. FOCS, 1998.
  * [23] Y. Wang, Y. Tong, C. Long, P. Xu, K. Xu, and W. Lv.  Adaptive dynamic bipartite graph matching: A reinforcement learning approach.  Proceedings - International Conference on Data Engineering, 2019-April:1478–1489, 2019.


# Enhancing Long-Term Memory using Hierarchical Aggregate Tree for Retrieval
Augmented Generation

Aadharsh Aadhithya A∗, Sachin Kumar S∗ Soman K.P∗
Amrita School of Artificial Intelligence,Coimbatore
Amrita Vishwa Vidyapeetham, India

###### Abstract

Large language models (LLMs) have limited context capacity, hindering
reasoning over long conversations. We propose the Hierarchical Aggregate Tree
(HAT) memory structure to recursively aggregate relevant dialogue context
through conditional tree traversals. HAT encapsulates information from
children nodes, enabling broad coverage with depth control. We formulate
finding best context as optimal tree traversal. Experiments show HAT improves
dialog coherence and summary quality over baseline contexts, demonstrating the
technique’s effectiveness for multi-turn reasoning without exponential
parameter growth. HAT balances information breadth and depth for long-form
dialogues. This memory augmentation enables more consistent, grounded long-
form conversations from LLMs.

00footnotetext: Drafted: December 18,2023
Arxiv Submission:

##  1 Introduction

Large language models (LLMs) like ChatGPT are having an impact across various
areas and applications. One of the most straightforward applications is using
LLMs as personalized chat agents. There have been several efforts to develop
chatbots for various applications, both generic and domain-specific,
particularly after the advent of LLMs and associated Pythonic libraries, which
have made it very easy for people to develop their own chatbots.

Customizing and aligning these LLMs is still an active area of research. One
basic alignment we would want is to make chatbots behave according to our
expectations, particularly when context is specific and requires some
information to be highlighted that is not necessarily in the model’s
pretraining corpus. While LLMs are considered snapshots of the internet, one
limitation is that they are closed systems and providing external information
to LLMs is an active research area.

Two primary ways of providing external data to LLMs are through: a) finetuning
and b) retrieval-augmented generation (RAG). Finetuning requires access to
model weights and can only be done with open models. RAG relies on strategies
to retrieve information from a datastore given a user query, without needing
internal model information, allowing it to be used with more model types.
However, RAG is limited by the model’s context length budget. Although very
large context LLMs exist, the budget remains limited. Hence, how and what data
is retrieved given a user query is an important research task.With the advent
of "LLM agents", a separate memory management module is often required. Some
solutions train models for this task while others take a retrieval-based
approach. Still others use the LLM itself to accomplish it. However, current
approaches tend to rely solely on providing a summary versus retrieving from a
datastore, with little in between. We hence propose a method that combines
both worlds using a new data structure called the "Hierarchical Aggregate
Tree".

###  1.1 Recent works

There has been growing interest in developing techniques to enhance LLMs’
capabilities for long-term multi-session dialogues. Xu et al. (2021a)
collected a dataset of human conversations across multiple chat sessions and
showed that existing models perform poorly in maintaining consistency,
necessitating long-context models with summarization and retrieval abilities.
Xu et al. (2021b) proposed a model to extract and update conversational
personas over long-term dialogues. Bae et al.  presented a task and dataset
for memory management in long chats, dealing with outdated information. Wang
et al.  proposed recursive summarization for equipping LLMs with long-term
memory. Lee et al.  showed prompted LLMs can match fine-tuned models for
consistent open-domain chats. Zhang et al.  encoded conversation history
hierarchically to generate informed responses. Developing more sophisticated
strategies for information integration remains an open challenge.

##  2 Task Definition

The Task at hand is straightforward. Given a history of conversations between
a user and an assistant(system), we are to predict the response of the system.
In other words, given the history of conversation at time step t,
$H_{t}=\\{u_{1},a_{1},u_{2},a_{2}\cdots a_{t-1}\\}$(where $u_{i}$ represents a
user response and $a_{i}$ represents assistant response) and a user query
$u_{t}$, our task is to find a relevant function $f$ such that

$a_{t}\approx LLM(u_{t},f(H_{t}|u_{t}))$

Where $f$ can be thought of as some function, mapping the entire history of
conversation to a condensed space conditioned on the user query at time step
t. Note that, $f$ can be a selection function, a trained neural network as a
memory agent, or even a simple summary function. In our experiments, the
dataset is organized as sessions and episodes. An episode consists of multiple
consecutive dialogue sessions with a specific user, oftentimes requiring
information from previous sessions to respond back. Hence in addition to the
history $H$, at the end of every session, we also have a memory $M^{e}_{s}$
for session $s$ and episode $e$, constructed by combining $H^{e}_{s}$ and
$M^{e}_{s-1}$, where $H_{s}^{e}$ represents the history of session s and
episode e. Therefore, we also have this auxiliary task of finding $M^{e}_{s}$
given $M^{e}_{s-1}$ and $H_{s}^{e}$ .

Figure 1: Overview of our approach. Given a user query, the memory module is
responsible to give a relevant context by traversing the HAT. The LLM then
generates response for the user query, given the context.

##  3 Methedology

Figure 2: Illustration of HAT, with example aggregation function as simple
concatenation and memory length of 2.

An overview of our methodology is depicted in Figure 1. The memory module is
tasked to retrieve a relevant context that has necessary information to
respond to user query. The module does so by leveraging 2 primary components:

  1. 1.

Hierarchical Aggregate Tree (HAT) : We propose the use of a novel
datastructure called HAT to manage memory, particularly in long form texts
like open domain conversations. It has some important property like resolution
retention as detailed in section 3.1. At a high-level, the intended
characteristic of HAT is that we have more resolution as we move Top-Down and
we have more latest information as we move Left-Right.

  2. 2.

Memory Agent : The memory agent is tasked to find the best traversal in HAT,
conditioned on the user query such that at the end of traversal, we are in a
node that contains relevant context to answer the user query.

###  3.1 Hierarchical Aggregate Tree (HAT)

Hierarchical Aggregate Tree (HAT) is defined as $HST=(L,M,A,\Sigma)$ , where,
$L=\\{l_{0},l_{1},\ldots,l_{n}\\}$ is a finite set of layers,$M$ is the memory
length, a positive integer,$A$ is an aggregation function and $\Sigma$ is a
set of nodes. The layers in L are hierarchical, with $l_{0}$ being the root
layer. Each layer $l_{i}\in L$ is a set of nodes $\Sigma_{i}$, where
$\Sigma_{i}\subseteq\Sigma$. A node $\sigma\in\Sigma$ can have children nodes
and contains a text element. A node recalculates its text property, whenever
there is a change in the node’s children. The text property of a node
$\sigma\in\Sigma_{i}\,i\neq|L|$ is given by $A(C(\sigma))$ , where
$C(\sigma)=\\{\tau\in\Sigma\mid\tau$ is a child of $\sigma\\}$

#### Aggregate Function

The aggregate function $A$ maps the text of child nodes to produce the text
stored at a parent node.

$A:\mathcal{P}(\Sigma)\rightarrow Text$

Where, $\mathcal{P}(\Sigma)$ represents the power set of nodes. The exact
implementation of $A$ can vary depending on the usecase. Figure 2 for example,
depicts an HAT with concatenation as aggregate function. For our
implementation, we use GPT as aggregate function.

It is important that the aggregate function should be designed to produce
concise summaries reflecting key information from child nodes for a meaningful
HAT. It executes whenever new child nodes are inserted to maintain consistency
up the tree. For our implementation, we use GPT as aggregate function. We say
GPT to summarize persona’s from the children’s text. The exact prompt given
can be found in the appendix.

#### Node

A node $\sigma\in\Sigma$ represents a single element in the HAT structure.
Whenever the set of children nodes for $\sigma$ changes, the update_text()
method is called to update $\sigma$’s text. This text is given by applying the
aggregator function to the set of texts from the current child nodes. The
previous aggregated texts of given different combinations of children are
cached in previous_complete_state to enable reuse instead of recomputing.

After updating, $\sigma$ triggers the parent node to also update, thereby
propagating changes upwards in the HAT structure.

Each node $\sigma$ contains the following components:

  * •

id: A unique identifier

  * •

text: The node’s aggregated text content

  * •

previous_complete_state: A dictionary mapping hashes of the node’s children to
the previously aggregated text when the node had those children

  * •

parent: The parent node in the HAT (None for the root node)

  * •

aggregator: The aggregation function $A$

  * •

children: The set of child nodes $C(\sigma)$

The HAT datastructure satisfies the invariant that if
$\sigma_{k,i}\in\Sigma_{k}$ is a child of
$\tau_{k-1,j}\in\Sigma_{k-1}\leftrightarrow j=\lfloor\frac{i}{M}\rfloor$,
where $\sigma_{k,i}$ is ith node in kth layer. This connects child nodes to
parent nodes between layers based on the memory length, $M$. When inserting a
new node $\phi\in\Sigma_{y}$, the aggregation function $A$ is recursively
applied to update ancestor nodes. That is, For all $\sigma_{y-1,z}\in P(\phi)$
that are parents of $\phi$, $\sigma_{y,z}.text=A(C(\sigma_{y,z}))$, Where
$C(\sigma_{y,z})=\\{\tau\in\Sigma|\tau$ is a child of $\sigma_{y,z}\\}$

This maintains the invariant while propagating updated information through the
tree. The number of layers $|L|$ and nodes $|\Sigma|$ changes dynamically
based on $M$ and node insertions. $|L|$ represents the depth of the tree.

For Brevity, we restrict further detailing on the datastructure. However, All
necessary details to replicate the datastructure shall be given in appendix.

###  3.2 Memory Agent

The memory agent is tasked with finding the optimal traversal in HAT
conditioned on a user query $q$. This can be mathematically formulated as:

$a_{0:T}^{*}=\operatorname*{arg\,max}_{a_{0:T}}R(s_{0:T},a_{0:T}|q)$

where $s_{0:T}$ is the state sequence from the root node to a leaf node,
$a_{0:T}$ is the action sequence, and $R$ is the total reward over the
traversal dependent on $q$. Reward, in our case is the quality of response the
model is giving. This essentially can be posed as a Markov Decision Process
(MDP). The agent starts at the root node $s_{0}$ and takes an action
$a_{t}\in\mathcal{A}$ at each time step, transitioning to a new state
$s_{t+1}\sim\mathcal{P}(\cdot|s_{t},a_{t})$. For cases like this, It is
difficult to design a reward function, and we will require annotated training
data for training the agent. Hence, we resort to GPT and will ask GPT to act
as a traversal agent. GPT is well-suited for conditional text generation,
which allows it to traverse HAT by generating an optimal sequence of actions
based on the text representation at each node and the user query.

The exact prompt used for the memory agent can be found in the Appendix.

The MDP is defined by the tuple
$(\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma)$, where:

  * •

$\mathcal{S}$ \- set of tree nodes

  * •

$\mathcal{A}=\\{U,D,L,R,S,O,U\\}$ \- set of actions

    * –

$U$ \- move up the tree

    * –

$D$ \- move down

    * –

$L$ \- move left

    * –

$R$ \- move right

    * –

$S$ \- reset to root node

    * –

$O$ \- sufficient context for query $q$

    * –

$U$ \- insufficient context for query $q$

  * •

$\mathcal{P}$ \- state transition probabilities

  * •

$\mathcal{R}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ \- reward
function

  * •

$\gamma\in(0,1)$ \- discount factor

GPT is well-suited for conditional text generation, which allows it to
traverse HAT by generating an optimal sequence of actions based on the text
representation at each node and the user query. But, It is important to note
that our proposed framework is open and generic. The memory agent can be
anything from neural network or RL Agent to an GPT Aproximation.

##  4 Experiments

###  4.1 Dataset

Data Type | Train | Valid | Test
---|---|---|---
Session 1 | 8939 | 1000 | 1015
Session 2 | 4000 | 500 | 501
Session 3 | 4000 | 500 | 501
Session 4 | 1001 | 500 | 501
Session 5 | - | 500 | 501
Table 1: Number of episodes across sessions.

We use the multi-session-chat dataset from Xu et al. (2022). The dataset
contains two speakers chat online in a series of sessions as is for example
common on messaging platforms. Each individual chat session is not especially
long before it is “paused”. Then, after a certain amount of (simulated) time
has transpired, typically hours or days, the speakers resume chatting, either
continuing to talk about the previous subject, bringing up some other subject
from their past shared history, or sparking up conversation on a new topic.
Number of episodes per session is on Table 1.

We utilize 501 episodes whose session 5 is available from the Test set.

###  4.2 Evaluation Metrics

We evaluate the dialogue generation performance of our model using automatic
metrics. We report BLEU-1/2 , F1 score compared to human-annotated responses,
and DISTINCT-1/2.

BLEU (Bilingual Evaluation Understudy) measures overlap between machine
generated text and human references, with values between 0 to 1 (higher is
better). We use BLEU-1 and BLEU-2 which compare 1-grams and 2-grams
respectively. F1 score measures overlap between generated responses and human
references. We report F1 to assess relevance of content. DISTINCT-1/2
quantifies diversity and vocabulary usage based on the number of distinct
unigrams and bigrams in the generated responses, normalized by the total
number of generated tokens (higher is better).

###  4.3 Baselines

We benchmark against three trivial methods: 1) All Context: LLM generated
dialogues with all dialogues in context. 2) Part Context: LLM generates
dialogues with only current session’s context. 3) Gold Memory: The LLM
generated dialogues with Gold memory from the dataset as context. Further, We
also evaluate different Traversal methods including BFS,DFS,and GPTAgent. In
BFS and DFS, we follow naive BFS or DFS traversal, and at every step as gpt if
this information is enough to answer the user question. If it tells okay, we
stop there and return the context.

##  5 Results

| BLEU-1/2 | DISTINCT-1/2
---|---|---
BFS | 0.652 / 0.532 | 0.072 / 0.064
DFS | 0.624 / 0.501 | 0.064 / 0.058
GPTAgent | 0.721 / 0.612 | 0.092 / 0.084
Table 2: Dialogue generation comparison between traversal methods

Table 2 compares GPTAgent to breadth-first search (BFS) and depth-first search
(DFS) traversal methods. Across BLEU-1/2 and DISTINCT-1/2 metrics, GPTAgent
significantly outperforms both in quality and diversity of dialogues. This
supports our approach of learning to traverse conditioned on query relevance
over hand-designed heuristics.

Next, Table 3 benchmarks GPTAgent against contexts with complete, partial or
gold dialogue history. GPTAgent achieves highest scores, demonstrating the
benefit of our focused memory retrieval. Access to full history or gold
references improves over just current context, but lacks efficiency of
precisely identifying relevant information. Finally, Table 4 evaluates
fidelity of memories generated by GPTAgent compared to dataset ground truth
references. We again see strong results surpassing 0.8 on both word overlap
and diversity measures.

| BLEU-1/2 | DISTINCT-1/2
---|---|---
All Context | 0.612 / 0.492 | 0.051 / 0.042
Part Context | 0.592 / 0.473 | 0.043 / 0.038
Gold Memory | 0.681 / 0.564 | 0.074 / 0.064
GPTAgent | 0.721 / 0.612 | 0.092 / 0.084
Table 3: Dialogue generation comparison between baselines | BLEU-1/2 | DISTINCT-1/2 | F1
---|---|---|---
GPT | 0.842 / 0.724 | 0.102 / 0.094 | 0.824
Table 4: Memory generation scores

In summary, experiments validate effectiveness of our method in extracting
salient dialogue context in long form conversations. Both conversations and
summarized memories demonstrate quality and relevance gains over alternate
approaches. The query conditioning provides efficiency over exhaustive history
while retaining enough specificity for the current need.

##  6 Limitations

While the proposed method has a potential and could work with long-form texts,
The current implementation takes longer than a usual time taken by a dialogue
agent to respond. Also, Making HTTP API calls to gpt, is causing an additional
overhead on the time taken. These limitations could be overcome, by turning to
heuristic-based tree searches or Monte-Carlo Tree search like methods in the
future. Further, A Coupled-HAT : One HAT with textual information and another
HAT with dense vector representation, would be more efficient. Combined with
hybrid retrieval techniques, we could have a much more efficient way of doing
conditional retrival. Further, Another limitation of this kind of Retrieval
system is that, As the leaf nodes expands exponentially, the memory footprint
might become larger than expected. Several optimizations on this front, also
could be potential future work in this direction.

##  7 Conclusion

In this work, we have presented the Hierarchical Aggregate Tree (HAT) - a new
data structure designed specifically for memory storage and retrieval for long
form text based conversational agents. Rather than solely providing a summary
or retrieving raw excerpts, our key innovation is recursive aggregation of
salient points by traversing conditional paths in this tree.We formulate the
tree traversal as an optimization problem using a GPT-based memory agent. In
conclusion,Our Experiments demonstrate significant gains over alternate
traversal schemes and baseline methods. HAT introduces a flexible memory
structure for dialogue agents that balances extraction breadth versus depth
through hierarchical aggregation. Our analysis confirms the viability and
advantages of conditional traversal over existing limited budget solutions,
opening up further avenues for augmented language model research.

## References

  * (1) Sanghwan Bae, Donghyun Kwak, Soyoung Kang, Min Young Lee, Sungdong Kim, Yuin Jeong, Hyeri Kim, Sang-Woo Lee, Woomyoung Park, and Nako Sung.  Keep me updated! memory management in long-term conversations.
  * (2) Gibbeum Lee, Volker Hartmann, Jongho Park, Dimitris Papailiopoulos, and Kangwook Lee.  Prompted LLMs as chatbot modules for long open-domain conversation.  In _Findings of the Association for Computational Linguistics: ACL 2023_ , pages 4536–4554.
  * (3) Qingyue Wang, Liang Ding, Yanan Cao, Zhiliang Tian, Shi Wang, Dacheng Tao, and Li Guo.  Recursively summarizing enables long-term dialogue memory in large language models.
  * Xu et al. (2021a) Jing Xu, Arthur Szlam, and Jason Weston. 2021a.  Beyond goldfish memory: Long-term open-domain conversation.  _arXiv preprint arXiv:2107.07567_.
  * Xu et al. (2022) Jing Xu, Arthur Szlam, and Jason Weston. 2022.  Beyond goldfish memory: Long-term open-domain conversation.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 5180–5197, Dublin, Ireland. Association for Computational Linguistics.
  * Xu et al. (2021b) Xinchao Xu, Zhibin Gou, Wenquan Wu, Zheng-Yu Niu, Hua Wu, Haifeng Wang, and Shihang Wang. 2021b.  Long time no see! open-domain conversation with long-term persona memory.
  * (7) Tong Zhang, Yong Liu, Boyang Li, Zhiwei Zeng, Pengwei Wang, Yuan You, Chunyan Miao, and Lizhen Cui.  History-aware hierarchical transformer for multi-session open-domain dialogue system.