# SciCap+: A Knowledge Augmented Dataset to
Study the Challenges of Scientific Figure Captioning

Zhishen Yang1, Raj Dabre2, Hideki Tanaka2, Naoaki Okazaki1

###### Abstract

In scholarly documents, figures provide a straightforward way of communicating
scientific findings to readers. Automating figure caption generation helps
move model understandings of scientific documents beyond text and will help
authors write informative captions that facilitate communicating scientific
findings. Unlike previous studies, we reframe scientific figure captioning as
a knowledge-augmented image captioning task that models need to utilize
knowledge embedded across modalities for caption generation. To this end, we
extended the large-scale SciCap dataset (Hsu, Giles, and Huang 2021) to
SciCap+ which includes mention-paragraphs (paragraphs mentioning figures) and
OCR tokens. Then, we conduct experiments with the M4C-Captioner (a multimodal
transformer-based model with a pointer network) as a baseline for our study.
Our results indicate that mention-paragraphs serves as additional context
knowledge, which significantly boosts the automatic standard image caption
evaluation scores compared to the figure-only baselines. Human evaluations
further reveal the challenges of generating figure captions that are
informative to readers. The code and SciCap+ dataset will be publicly
available:111https://github.com/ZhishenYang/scientific˙figure˙captioning˙dataset

## Introduction

Scholarly documents are the primary source for sharing scientific knowledge.
These documents are available in various formats, such as journal articles,
book chapters, and conference proceedings. A significant portion of these
documents is text and together with figures and tables, they help communicate
knowledge to readers. Using figures provides visual representations of complex
information that facilitate the sharing of scientific findings with readers
efficiently and straightforwardly. The standard practice for scientific
writing is to write a caption for each figure, accompanied by paragraphs with
detailed explanations. Figures and captions should be standalone, and readers
should be able to understand the figures without referring to the main text.
Helping authors write appropriate and informative captions for figures will
improve the quality of scientific documents, thereby enhancing the speed and
quality of scientific communication. In this study, we focus on automating the
generation of captions for figures in scientific papers.

Scientific figure captioning is a variant of the image captioning task.
However, with the same goal of generating a caption, it has two unique
challenges: 1. Figures are not natural images: In contrast to natural images,
visual objects are texts and data points in scientific figures. 2. The
captions of the figures should explain: Instead of simply identifying objects
and texts in the figures, the caption should contain an analysis that the
authors intend to present and highlight findings.

A previous study (Hsu, Giles, and Huang 2021), SciCap, defines the scientific
figure captioning task as a figure-to-caption task: A model generates captions
only referring to figures. Their work reported relatively lower scores as
measured by automatic evaluation metrics, indicating that there is
considerable room for improvement. Intuitively, writing appropriate figure
captions without sufficient background knowledge is difficult, since even
humans will struggle to interpret a figure and write a caption unless some
background knowledge is available. On the basis of this observation, we think
that generating appropriate captions is infeasible without adding context
knowledge to the caption generation model. This context comes in two forms:
background knowledge from the running text and the OCR tokens in the figure,
both of which should help reduce the burden on the captioning model. To this
end, we augment the existing large-scale scientific figure captioning dataset:
SciCap with mention-paragraphs and OCR tokens and call the resultant dataset
as SciCap+. We then pose scientific figure captioning as a multimodal
summarization task and use the M4C captioner model (Sidorov et al. 2020a)(a
model that utilizes multimodal knowledge to generate captions) as a baseline
to study the scientific figure captioning task. The experimental result of
automatic evaluation demonstrates that using knowledge embedded in different
modalities, especially in the form of mention-paragraphs and OCR tokens,
significantly boosts performance.

In addition to experiments using automatic evaluation metrics, we also
performed human generation and evaluation tasks in order to establish the
inherent difficulty of scientific figure captioning. The results of the human
evaluation reveal three findings: 1. Multimodal knowledge helps models
outperform humans in caption generation tasks. 2. Model-generated captions are
almost as informative as ground-truth captions: Human evaluators do not prefer
either type of caption. 3. Even referring to mention-paragraphs, it is still
challenging for humans to write captions that are close to ground truth. To
the best of our knowledge, we are the first to pose scientific figure
captioning as a multimodel summarization task and show that mention-paragraphs
and OCR tokens as context substantially enhance the quality of generated
captions.

## Preliminary Study

Figure 1: An example figure (Zhang et al. 2019) with its captions and mention-
paragraph and the text tokens recognized via OCR. Without referring to the
mention-paragraph and the OCR tokens to tie the figure and the mention, we
cannot have a proper interpretation of the data presented in the figure, which
is communication cost comparison and speed up of CHEETAH over GAZELLE.

In the traditional image captioning task, captioning an image aims at
describing the appearances or natures of recognized objects and illustrating
the relationships between recognized objects. Unlike the usual image
captioning tasks, figures do not contain visual scenes. Instead, the captions
provide interpretations of data presented in figures to highlight scientific
findings that authors want to present to readers. With this unique
characteristic, without referring to mention-paragraphs, which usually refer
to the figure, it is extremely challenging for a human to have proper
interpretations of figures. This is because they may lack background knowledge
of the domain or context of the figure. As figure 1 shows, by only looking at
the figure, we do not know what ”comm.(KB)” stands for; therefore lacking the
knowledge to write informative captions is challenging. However, the mention-
paragraph contains ”communication cost” and this is also present in the
caption, indicating that such background knowledge should help in writing
accurate captions.

## Problem Formulation

The previous study (Hsu, Giles, and Huang 2021) defined this task as an image
captioning task as: Given a figure $I$, the model generates a caption
$C=[c_{0},c_{1},...,c_{N}]$. However, we reframe the scientific figure
captioning task as a knowledge-augmented image captioning task requiring
knowledge extracted from text and vision modalities. For a figure, we define a
paragraph that mentions it (mention-paragraph) and text within the figure,
extracted via OCR, as text modalities. The figure itself and visual
appearances of OCR texts are visual modalities. Given a scientific figure $I$
and knowledge extracted from text and vision modality: $K_{text}$ and
$K_{vision}$, we define figure caption generation task as
$P(C|I,K_{text},K_{vision})$

## SciCap+ Dataset

SciCap is a large-scale figure-caption dataset comprising graph plots
extracted from 10 years of collections of arXiv computer science papers. We
used around 414k figures from SciCap and augment each figure with its mention-
paragraphs and OCR tokens with metadata. This section details the data set
creation and data augmentation processes. Figure 2 shows the overall workflow
behind the creation of SciCap+.

Figure 2: The overall workflow of the data augmentation for creating SciCap+
dataset. For each figure in SciCap+, we extracted its mention-paragraphs and
OCR tokens (OCR texts and bounding boxes).

### Mention-paragraph Extraction

We first obtained papers in PDF format from Kaggle arXiv dastaset
222https://www.kaggle.com/datasets/Cornell-University/arxiv. The reason for
using PDFs is that not all papers have source files and some are complicated
to parse. After obtaining PDFs, we used PDFFigures 2.0 (Clark and Divvala
2016) 333https://github.com/allenai/pdffigures2 to extract the body text of
each paper. PDFFigure 2.0 is a tool that extracts figures, captions, tables,
and text from scholarly PDFs in computer science. In scholarly documents,
authors label figures with numbers (e.g. Figure 1. Fig. 1). For a figure, we
used its figure number in a regular expression to locate a paragraph that
mentions it.

### OCR Extraction

The SciCap dataset also provides texts extracted from figures as metadata, but
does not provide location information for each text. To include location
information for each text in a figure, we used Google Vision OCR API to
extract text tokens from each figure with its coordinates of bounding boxes.

### Data Statistics

The splitting of the SciCap dataset is at the figure level. Therefore, figures
from the same paper may appear in different splits. This will lead to unfair
evaluation, since the information of one figure in one split may
coincidentally overlap with the information of another figure. We thus re-
split figures at the document level to eliminate this overlapping problem.
Hsu, Giles, and Huang (2021) show that text normalization and figure filtering
do not improve model performance. Hence, we keep original captions and all
figures (with/without sub-figures) in the SciCap+ dataset. For a figure, we
kept only the first paragraph that mentions it in the body text. Table1 shows
statistics of the SciCap+ dataset. In all three splits, around 90% of the
captions are less than 66 words. All figures are graph plots.

Split | Figures | Words
---|---|---
Training | 394,005 | 12,336,511
Test | 10,336 | 323,382
Validation | 10,468 | 329,072
Table 1: Statistics of the SciCap+ dataset.

### Dataset Quality Evaluation

Before conducting experiments, we conducted human evaluation of SciCap+ where
we checked the mention-paragraphs and OCR tokens extraction quality. The aim
was to establish whether the mention-paragraphs and OCR tokens were extracted
correctly and relevant to the figure and its caption. To this end, we randomly
selected 200 figures from the training set and for each figure, we asked two
human evaluators to give scores of 1-5 (1 represents no relevance and 5 is
highly relevant) for relevance between a caption of a figure and its mention-
paragraphs and OCR tokens.

Compared to natural image captioning, human evaluation tasks for the figure
captioning domain requires expert knowledge. We recruited two colleagues to
carry out this evaluation task. Both of them have Ph.D. degrees in computer
science and work as researchers. Their experience implies that they have
adequate experience writing figure captions.

Figure 3 shows the distributions of the relevance scores. We can observe that
two evaluators gave most of the figures (evaluator 1: 64% and evaluator 2:
79.5%) with relevance scores greater than 3 and a cohen kappa score of 0.28.
This evaluation result indicates that the mention-paragraphs and OCR tokens
have a satisfactory extraction quality and that the annotators considered most
of them as relevant to the figure and its caption. However, the two annotators
seem to have a relatively lower agreement (0.28) regarding which figures and
captions are relevant to their mention-paragraphs and OCR tokens. We attribute
this to the fact that evaluations of figure captions are highly subjective.

Figure 3: Score distribution on correlations between mention-paragraph, OCR
tokens and figure captions. Both evaluators judged most of the figures with at
least moderate correlations with captions.

## Experiments

We conduct experiments using SciCap+ to empirically prove that scientific
figure captioning is inherently a knowledge-augmented task and benefits from
knowledge coming from both text and vision modalities.

### Figure Captioning Model

We used M4C-Captioner (Sidorov et al. 2020a) as the baseline model to study
the scientific figure captioning task. The M4C-Captioner is based on
Multimodal Multi-Copy Mesh (M4C) (Hu et al. 2020) that jointly learns
representations across input modalities. To solve the out-of-vocabulary
problem during caption generation, it is equipped with a pointer network that
picks up text from OCR tokens or a predefined fixed dictionary. In this work,
3 input features are used, figure, mention-paragraphs and OCR tokens fed to
encoders, the output representations of which are fed to the M4C-Captioner.

### Implementation and Training

Our implementation of M4C-Captioner is based on the MMF framework (Singh et
al. 2020) and Pytorch. The implementation allows users to specify diverse pre-
trained encoders for each modality, which can be fine-tuned or frozen during
training. The M4C-captioner itself has $D=768$ hidden dimension size, $K=4$
transformer layers and 12 attention heads. We used sentencepiece (Kudo and
Richardson 2018) to obtain a dictionary of 32000 subwords built from both
mention-paragraphs and OCR tokens. This is used as the M4C-captioner’s
vocabulary. We followed the BERT-BASE hyperparameter setting and trained from
scratch.

Regarding the encoders that feed features to M4C-captioner, we used pre-
trained Resnet-152 as the figure’s vision encoder. For each figure, we applied
a 2D adaptive average pooling over outputs from layer 5 to obtain a global
visual feature vector with a dimension of 2048. Layers 2, 3 and 4 layers were
fine-tuned during training. For mention-paragraph features, SciBERT (Beltagy,
Lo, and Cohan 2019) was used to encode444We only used the first 3 layers of
SciBERT for lightweightness. it into 758-dimensional feature vectors. The
number of vectors equals the number of sub-word tokens in the mention-
paragraph, which we limit to 192. The mention-paragraph encoder is also fine-
tuned during training. Finally, for OCR tokens, we use both text and visual
features. We selected FastText (Almazán et al. 2014) as the word encoder and
Pyramidal Histogram of Characters (PHOC) (Bojanowski et al. 2017a) as the
character encoder. Regarding the visual feature encoder of OCR tokens, we
first extracted Faster R-CNN fc6 features and then applied fc7 weights to it
to obtain 2048-dimensional appearance features for bounding boxes of OCR
tokens. The fc7 weights were fine-tuned during training. We kept a maximum of
95 OCR tokens per figure.

We trained a model on a GPU server with 8 Nvidia Tesla V100 GPUs. Training a
model with a complete set of features took 13 hours. During training, we used
a batch size of 128. We selected CIDEr as the evaluation metric. The
evaluation interval is every 2000 iterations, we stop training if CIDEr score
does not improve for 4 evaluation intervals. The optimizer is Adam with a
learning rate of $0.001$ and $\epsilon=1.0\mathrm{E}{-08}$. We also used a
multistep learning rate schedule with warmup iterations of 1000 and a warmup
factor of 0.2. We kept the maximum number of decoding steps at the decoding
time as 67. For evaluation, we used five standard metrics for evaluating image
captions: BLEU-4 (Papineni et al. 2002), METEOR (Banerjee and Lavie 2005),
ROUGE-L (Lin 2004), CIDEr (Vedantam, Lawrence Zitnick, and Parikh 2015) and
SPICE (Anderson et al. 2016). Since figure captions contain scientific terms
which can be seen as uncommon words, among all five metrics, we are
particularly interested in CIDEr since it emphasizes them.

Model | BLEU-4 | METEOR | ROUGE-L | SPICE | CIDEr
---|---|---|---|---|---
1\. M4C-Captioner (Figure Only ) | 1.5 | 5.6 | 15.4 | 4.3 | 4.6
2\. M4C-Captioner (Mention Only) | 5.3 | 11.0 | 27.4 | 14.3 | 49.0
3\. M4C-Captioner (Figure and OCR features) | 2.6 | 7.6 | 20.5 | 10.1 | 22.2
4\. M4C-Captioner (Mention, Figure and OCR features) | 6.3 | 12.0 | 29.2 | 15.8 | 55.8
Ablation Study on Figures |  |  |  |  |
5\. M4C-Captioner (Mention and OCR features) | 6.3 | 12.0 | 29.3 | 16.1 | 56.4
Ablation Study on OCR features |  |  |  |  |
6\. M4C-Captioner (Mention, Figure and w/o OCR features ) | 6.4 | 11.5 | 27.9 | 14.6 | 50.5
7\. M4C-Captioner (Mention, Figure and OCR spatial features) | 5.8 | 11.1 | 27.3 | 14.1 | 48.0
8\. M4C-Captioner (Mention, Figure and OCR (w/o spatial features) features ) | 6.4 | 12.0 | 29.1 | 15.7 | 54.6
9\. M4C-Captioner (Mention, Figure and OCR (w/o visual features) features ) | 6.2 | 11.9 | 28.9 | 15.6 | 54.1

Table 2: Automatic evaluation scores of M4C-captioning on SciCap dataset.
Aggregate knowledge from text and vision modalities significantly boosts the
model performance compared to the figure-only baseline.

## Results

### Main Result

The experimental results in table 2 demonstrate that using the mention-
paragraph and OCR tokens significantly improves scores on all five metrics
compared to the figure-only baseline. The experimental results align with our
hypothesis and preliminary study that scientific figure captioning is a
knowledge-augmented image captioning task, OCR tokens and knowledge embedded
in mention-paragraphs help in composing informative captions.

We established a baseline M4C-Captioner (Figure only) with figures as the only
input modality to the M4C-Captioner model in row #1. This baseline is in the
non-knowledge setting. Therefore, low scores in all metrics show that the
model needs knowledge of other modalities. Using the mention only in row #2
shows that the mention certainly contains a lot of useful information, as
evidenced by the increase in performance. When OCR features are added to the
figure input in row #3, scores for all metrics have significant gains compared
to the figure-only baseline, but are still weaker than when only mentions are
used. This motivates the combination of mentions and OCR features and in row
#4, compared to the figure-only baseline and figure-OCR-only baseline, the
performance further improves. Perhaps the most interesting result is in row #5
where we only use the mentions and OCR features but not the figure and get the
best performance, particularly for SPICE and CIDEr, albeit comparable to when
the figure is included in row #4. All these results indicate that explicitly
extracted multimodal knowledge helps to compose informative captions.

### Ablation Studies

We first performed an ablation study on figures by removing visual feature
vectors, the CIDEr score increases slightly, indicating that the visual
feature is more like noise for the model. This is likely because the
Resnet-152 visual encoder we used was not trained on figures.

We enriched the representations of the OCR features by adding text, visual,
and spatial features. Ablation studies aim to reveal impacts of each OCR token
feature. All comparisons are with row #4 even though row #5 gives slightly
better scores. With OCR features completely removed in row #6, the CIDEr
scores decrease by 5.3. Using only OCR spatial features in row #7, the CIDEr
score dropped by 7.8. Removing OCR spatial features in row #8, the CIDEr
scores dropped by 1.2. Upon removal of OCR visual features in row #9, the
CIDEr score is close to removing spatial features.

The above ablation study indicates that the enriched OCR contributes to the
informativeness of generated captions. Unlike OCR features, where appearance
features are helpful to the model, removing visual features of figures
increases CIDEr scores, further indicating that we need a specific vision
encoder for figures to provide meaningful features.

## Human Evaluation

Having established that knowledge helps a model perform figure captioning, we
conducted some human evaluation activities to determine their subjective
quality. We conducted human caption generation and evaluation tasks. The human
generation task is to examine whether humans can write better captions than
models. The evaluation task is the appropriateness evaluation task, which
consists of evaluating how appropriate the model-generated captions are versus
ground-truth captions. Both tasks were performed by the same human subjects
for the quality assessment of the data set.

### Figure Caption Generation Task

Annotator | Inputs | BLEU-4 | METEOR | ROUGE-L | SPICE | CIDEr
---|---|---|---|---|---|---
1\. Annotator 1 | Figure-only | 2.4 | 8.3 | 13.2 | 9.4 | 14.6
2\. Annotator 2 | Figure-only | 3.8 | 10.1 | 21.5 | 8.9 | 23.8
3\. M4C-Captioner | Image and OCR features | 3.6 | 7.6 | 20.5 | 11.5 | 18.7
4\. Annotator 1 | Figure-Mention | 7.7 | 13.4 | 19.1 | 15.9 | 11.3
5\. Annotator 2 | Figure-Mention | 7.5 | 14.8 | 24.8 | 14.3 | 18.8
6\. M4C-Captioner | Mention, Figure and OCR features | 5.5 | 11.6 | 28.1 | 16.1 | 47.7
Table 3: Automatic evaluation scores on human-generated captions. The model has similar performances when the figure is the only available source. Using knowledge from vision and text modality, the model has a larger gain on CIDEr scores.  Model | Average Scores | Average Scores | Cohen-Kappa Scores
---|---|---|---
| Evaluator 1 | Evaluator 2 |
1\. M4C-Captioner (Mention, Figure and OCR features) | 1.8 | 2.13 | 0.27
2\. M4C-Captioner (Mention and OCR features) | 2.03 | 2.35 | 0.23
3\. M4C-Captioner (Mention Only) | 1.8 | 2.22 | 0.31
4\. M4C-Captioner (Figure and OCR features) | 1.91 | 2.08 | 0.36
5\. Ground truth | 1.95 | 2.07 | 0.32
Table 4: Average appropriateness score on model-generated and ground truth
captions. Two evaluators gave low scores on both model-generated and ground
truth captions, with the fair inter-annotator agreement.

The figure caption generation task is to generate captions under two
conditions separately: 1. Figure-only: Human annotators write captions given
only figures. This is to compare with captions generated by M4C-Captioner that
only has access to figures and OCR features. 2. Figure-Mention: Human
annotators write captions given both figures and their mention-paragraphs. We
randomly selected 100 figures from the test set and to compare human-generated
captions with captions generated by M4C-Captioner.

The table 3 shows automatic evaluation results for human caption generation
tasks. Given only figures (rows #1, 2), both annotators got low scores across
all metrics, among those, annotator 2 led all metrics except SPICE. Since
humans perform OCR naturally with their eyes we compare with M4C-captioner
(Figure and OCR features). It has the best SPICE score, although it
outperformed annotator 1 in 4 of 5 evaluation metrics, it achieved similar
performance compared with annotator 2. This shows that without additional
knowledge, humans aren’t that better than machines.

However, given mention-paragraphs and figures (rows #4, 5), compared to the
figure-only condition, both annotators got improved scores in BLEU-4, METEOR,
ROUGE-L, and SPICE but lower scores in CIDEr. Previous studies have shown that
CIDEr is more reliable as an evaluation metric for caption generation, and the
lowered CIDEr scores indicates that humans are likely to struggle with
additional knowledge. On the other hand, having access to full features,
M4C-captioner gained a significantly better CIDEr score compared to human
annotators. The automatic evaluation results of the human generation tasks
show the steep difficulty in writing figure captions close to ground truth.

Even given mention-paragraphs, our annotator wrote captions with low scores
across all standard image captioning evaluation metrics. We ascribe it as
figure captions are highly subjective and require in-domain knowledge to
write. Although our annotators are researchers, they cannot be professional in
all knowledge existing in the computer science domain. Granted mention-
paragraphs and OCR tokens as external knowledge sources, and with large-amount
data training, the model can significantly outperform humans.

### Appropriateness Evaluation

This task evaluates the appropriateness of model-generated and ground-truth
captions. We used the same set of 100 figures as in the figure caption
generation task, and placed ground-truth captions and model-generated captions
in random order. Then, human evaluators rank each caption to give
appropriateness scores (1-4) to each caption. The evaluation scale: 1.
Inappropriate: a caption does not match the figure, is not a sentence, is
wrong, or is misleading. 2. Not sure: It is impossible to judge
appropriateness solely from the figure. 3. Possible: A possible candidate that
is incomplete but not wrong. 4. Appropriate: An informative caption that
interprets the figure well. Since an appropriate figure caption should stand
alone and readers should understand the messages the figure wants to represent
without referring to the body text, we do not show mention-paragraphs to
evaluators.

Table 4 shows the results of the evaluations. Two evaluators gave low average
scores to both model-generated captions and ground-truth captions. In
addition, evaluators only reached fair agreements on scoring (0.23-0.36).
Using the mention and OCR features (row #2), gets the best human evaluation
scores and this is in line with the corresponding score in Table 2 where it
also achieves the best CIDEr performance, indicating that human evaluation is
reliable despite the fair agreements. The evaluation results indicate that the
model-generated and ground-truth captions are not always informative to both
evaluators, which reveals the need to improve caption writing quality and
model performance. We observed that captions tend to be written without
following specific rules, and this may contribute to lack of agreement. With
low inter-rater agreements, we found how informative a figure caption is
highly subjective and depends on in-domain background knowledge evaluators
have.

## Related Work

Unlike natural image captioning, figure captioning has been scarcely studied
in history. SciCap (Hsu, Giles, and Huang 2021) is the most recent work on
scientific figure captioning, they released a large-scale scientific figure
captioning dataset that includes figures from academic papers in arXiv
dataset. Before SciCap, FigCAP (Chen et al. 2019) (Chen et al. 2020) and
FigureQA (Kahou et al. 2017) are two figure captioning datasets, but their
figures are synthesized. We decided to extend and study on SciCap dataset,
since its figures are from real-world scientific papers. In this paper, we
also have leveraged multimodal knowledge using pre-trained models.

Multimodal machine learning is to model knowledge across various modalities.
The closest multimodal task to figure captioning is image captioning, a
popular architecture is encode-decoder, where the decoder learns to generate
captions conditioned on visual features extracted from the encoder. Recent
works on integrating texts in natural images for visual question answering and
image captioning tasks are based on transformer architecture augmented with a
pointer network (Hu et al. 2020; Sidorov et al. 2020b). The transformer
enriches representations by integrating knowledge from both text and visual
modality. The pointer network dynamically selects words from the fixed
dictionary or OCR tokens during generation.

Using knowledge embedded in pre-trained models is a common practice in solving
multimodal tasks. In this work, we used SciBert (Beltagy, Lo, and Cohan 2019),
a BERT model (Devlin et al. 2019) that was pre-trained in scientific papers,
to obtain informative representations for the texts extracted from computer
science papers. Since terms that exist in the figures may be uncommon words,
we also used FastText (Bojanowski et al. 2017b) to obtain word embeddings with
subword information. For visual modality, we used Renst152 (He et al. 2016)
and Faster R-CNN (Ren et al. 2015) used in extract features from images and
bounding boxes.

## Conclusion

In this paper, we study the challenges of the scientific figure captioning
task. Extending from the previous study (Hsu, Giles, and Huang 2021), we
reframe this task as a knowledge-augmented image captioning task, that is, a
model needs to use knowledge extracted across modalities to generate captions.
To this end, we released a new version of the SciCap dataset: SciCap+ by
augmenting figures with their mention-paragraphs and OCR tokens. We used
M4C-Captioner model as the baseline model to utilize knowledge across three
modalities: mention-paragraphs, figures, and OCR tokens. The automatic
evaluation experiments further reveal that using knowledge significantly
improves evaluation metric scores. Compared with human-generated captions, we
found models can generate better captions than humans regarding the automatic
evaluation metrics. However, human evaluations demonstrated that writing
scientific figure captioning is challenging even for humans, and the model-
generated figure captions, despite their reasonable automatic evaluation
quality, are still far from achieving a level appropriate for humans. The
release of the SciCap+ dataset is to promote the further development of
scientific figure captioning. For future work, we are interested in how to use
multimodal pretraining strategies in this task.

## Acknowledgment

These research results were partly obtained from the commissioned research
(No. 225) by National Institute of Information and Communications Technology
(NICT), Japan, and partly obtained from the first author’s internship research
under NICT.

## References

  * Almazán et al. (2014) Almazán, J.; Gordo, A.; Fornés, A.; and Valveny, E. 2014.  Word spotting and recognition with embedded attributes.  _IEEE transactions on pattern analysis and machine intelligence_ , 36(12): 2552–2566.
  * Anderson et al. (2016) Anderson, P.; Fernando, B.; Johnson, M.; and Gould, S. 2016.  Spice: Semantic propositional image caption evaluation.  In _European conference on computer vision_ , 382–398. Springer.
  * Banerjee and Lavie (2005) Banerjee, S.; and Lavie, A. 2005.  METEOR: An automatic metric for MT evaluation with improved correlation with human judgments.  In _Proceedings of the acl workshop on intrinsic and extrinsic evaluation measures for machine translation and/or summarization_ , 65–72.
  * Beltagy, Lo, and Cohan (2019) Beltagy, I.; Lo, K.; and Cohan, A. 2019.  SciBERT: A Pretrained Language Model for Scientific Text.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , 3615–3620. Hong Kong, China: Association for Computational Linguistics.
  * Bojanowski et al. (2017a) Bojanowski, P.; Grave, E.; Joulin, A.; and Mikolov, T. 2017a.  Enriching Word Vectors with Subword Information.  _TACL_ , 5: 135–146.
  * Bojanowski et al. (2017b) Bojanowski, P.; Grave, E.; Joulin, A.; and Mikolov, T. 2017b.  Enriching Word Vectors with Subword Information.  _Transactions of the Association for Computational Linguistics_ , 5: 135–146.
  * Chen et al. (2020) Chen, C.; Zhang, R.; Koh, E.; Kim, S.; Cohen, S.; and Rossi, R. 2020.  Figure Captioning with Relation Maps for Reasoning.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV)_.
  * Chen et al. (2019) Chen, C.; Zhang, R.; Koh, E.; Kim, S.; Cohen, S.; Yu, T.; Rossi, R.; and Bunescu, R. 2019.  Figure captioning with reasoning and sequence-level training.  _arXiv preprint arXiv:1906.02850_.
  * Clark and Divvala (2016) Clark, C.; and Divvala, S. 2016.  Pdffigures 2.0: Mining figures from research papers.  In _2016 IEEE/ACM Joint Conference on Digital Libraries (JCDL)_ , 143–152. IEEE.
  * Devlin et al. (2019) Devlin, J.; Chang, M.-W.; Lee, K.; and Toutanova, K. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , 4171–4186. Minneapolis, Minnesota: Association for Computational Linguistics.
  * He et al. (2016) He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 770–778.
  * Hsu, Giles, and Huang (2021) Hsu, T.-Y.; Giles, C. L.; and Huang, T.-H. 2021.  SciCap: Generating Captions for Scientific Figures.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , 3258–3264. Punta Cana, Dominican Republic: Association for Computational Linguistics.
  * Hu et al. (2020) Hu, R.; Singh, A.; Darrell, T.; and Rohrbach, M. 2020.  Iterative Answer Prediction with Pointer-Augmented Multimodal Transformers for TextVQA.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_.
  * Kahou et al. (2017) Kahou, S. E.; Michalski, V.; Atkinson, A.; Kádár, Á.; Trischler, A.; and Bengio, Y. 2017.  Figureqa: An annotated figure dataset for visual reasoning.  _arXiv preprint arXiv:1710.07300_.
  * Kudo and Richardson (2018) Kudo, T.; and Richardson, J. 2018.  SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , 66–71. Brussels, Belgium: Association for Computational Linguistics.
  * Lin (2004) Lin, C.-Y. 2004.  Rouge: A package for automatic evaluation of summaries.  In _Text summarization branches out_ , 74–81.
  * Papineni et al. (2002) Papineni, K.; Roukos, S.; Ward, T.; and Zhu, W.-J. 2002.  Bleu: a Method for Automatic Evaluation of Machine Translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , 311–318. Philadelphia, Pennsylvania, USA: Association for Computational Linguistics.
  * Ren et al. (2015) Ren, S.; He, K.; Girshick, R.; and Sun, J. 2015.  Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks.  In Cortes, C.; Lawrence, N.; Lee, D.; Sugiyama, M.; and Garnett, R., eds., _Advances in Neural Information Processing Systems_ , volume 28. Curran Associates, Inc.
  * Sidorov et al. (2020a) Sidorov, O.; Hu, R.; Rohrbach, M.; and Singh, A. 2020a.  Textcaps: a dataset for image captioning with reading comprehension.  In _European conference on computer vision_ , 742–758. Springer.
  * Sidorov et al. (2020b) Sidorov, O.; Hu, R.; Rohrbach, M.; and Singh, A. 2020b.  TextCaps: a Dataset for Image Captioningwith Reading Comprehension.
  * Singh et al. (2020) Singh, A.; Goswami, V.; Natarajan, V.; Jiang, Y.; Chen, X.; Shah, M.; Rohrbach, M.; Batra, D.; and Parikh, D. 2020.  MMF: A multimodal framework for vision and language research.  https://github.com/facebookresearch/mmf.
  * Vedantam, Lawrence Zitnick, and Parikh (2015) Vedantam, R.; Lawrence Zitnick, C.; and Parikh, D. 2015.  Cider: Consensus-based image description evaluation.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 4566–4575.
  * Zhang et al. (2019) Zhang, Q.; Wang, C.; Xin, C.; and Wu, H. 2019.  Cheetah: An ultra-fast, approximation-free, and privacy-preserved neural network framework based on joint obscure linear and nonlinear computations.  _arXiv preprint arXiv:1911.05184_.


# Abstract Huffman Coding and
PIFO Tree Embeddings

Keri D’Angelo∗ Dexter Kozen†
Cornell University Computer Science Department Ithaca, New York 14853-7501,
USA<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Algorithms for deriving Huffman codes and the recently developed algorithm for
compiling PIFO trees to trees of fixed shape [1] are similar, but work with
different underlying algebraic operations. In this paper, we exploit the
monadic structure of prefix codes to create a generalized Huffman algorithm
that has these two applications as special cases.

##  1 Introduction

_Huffman codes_ translate letters from a fixed alphabet to $d$-ary codewords,
achieving optimal compression for a given frequency distribution of letters.
There is a well-known greedy algorithm for producing Huffman codes from a
given distribution (see [2]).

A new data structure called a _PIFO tree_ (priority-in first-out) has recently
been proposed for implementing a wide range of packet scheduling algorithms in
programmable network routers [3, 4]. A PIFO tree is a tree of priority queues.
Currently, most routers support just a few scheduling algorithms such as
strict priority or weighted fair queueing, which are baked into the hardware.
The schedulers can be configured to some extent, but it is generally not
possible to implement more sophisticated scheduling algorithms that require
reordering of already queued packets. This is exactly what PIFO trees permit.
It seems likely that PIFOs will be supported on network devices in the near
future.

Some researchers have already begun to explore how the PIFO abstraction can be
emulated on conventional routers [4]. In very recent work [1], it was shown
how to translate an algorithm designed for a PIFO tree of arbitrary shape to
one that uses a PIFO tree of fixed shape, perhaps a complete $d$-ary tree that
might be implemented in hardware, with negligible performance degradation.

The embedding algorithm is greedy and very similar to the Huffman algorithm,
except that it is based on different algebraic operations. For Huffman coding,
one wishes to choose a $d$-ary prefix code $C$ so as to minimize the value of
$\sum_{x\in C}|x|\cdot r(x)$, where $r(x)$ is the frequency of the letter
assigned to the codeword $x$. This minimizes the entropy of the resulting
code. For PIFO trees, one wishes to minimize $\max_{x\in C}|x|+r(x)$, where
$r(x)$ is the height of a subtree. This minimizes the height of the resulting
$d$-ary tree and determines whether an embedding is at all possible.

This similarity leads us to seek a unified axiomatic treatment that is
parametric in the algebraic operations and that can be instantiated to produce
both applications as special cases. Our treatment exploits the monadic
structure of prefix codes to obtain an abstract formulation of the problem and
its solution. We identify sufficient conditions for our abstract algorithm to
produce optimal solutions, where the meaning of _optimal_ is also parametric
in the instantiation.

We state axioms that are sufficient for optimality in §3. The algorithm is
presented in §4 and its correctness proved in §5. The two applications of
Huffman codes and PIFO trees are derived in §6.

##  2 Background

We assume familiarity with the basic category-theoretic concepts of category,
functor, and natural transformation. Our exposition is based on the concepts
of _monad_ and _Eilenberg-Moore algebra_ ; we briefly review the definitions
here. For a more thorough introduction, we refer the reader to [5, 6, 7, 8].

_Monads_ are heavily used in functional programming to model the augmentation
of a computation with extra structure [9, 10, 11]. Formally, a _monad_ on a
category $\mathsf{C}$ is a triple $({\cal T},\eta,\mu)$, where ${\cal
T}:\mathsf{C}\to\mathsf{C}$ is an endofunctor on $\mathsf{C}$ and
$\eta:I\to{\cal T}$ and $\mu:{\cal T}^{2}\to{\cal T}$ are natural
transformations, called the _unit_ and _multiplication_ respectively, such
that for all objects $X$, the following diagrams commute:

Typical examples of monads are

  * •

the _list monad_ , in which $\eta_{X}(a)=\text{\rm{[}}a\text{\rm{]}}$, the
singleton list containing $a$, and

$\displaystyle\mu_{X}(\text{\rm{[}}\text{\rm{[}}a_{11},\ldots,a_{1k_{1}}\text{\rm{]}},\ldots,\text{\rm{[}}a_{n1},\ldots,a_{nk_{n}}\text{\rm{]}}\text{\rm{]}})$
$\displaystyle=\text{\rm{[}}a_{11},\ldots,a_{1k_{1}},\ldots,a_{n1},\ldots,a_{nk_{n}}\text{\rm{]}},$

the list flattening operation;

  * •

the _powerset monad_ , in which $\eta_{X}(a)=\\{a\\}$, the singleton set
containing $a$, and $\mu_{X}({\cal A})=\bigcup{\cal A}$, the operation that
takes a set of subsets of $X$ to its union.

Given a monad $({\cal T},\eta,\mu)$ on a category $\mathsf{C}$, an _Eilenberg-
Moore algebra_ for $({\cal T},\eta,\mu)$ is a pair $(X,\gamma)$, where $X$ is
an object of $\mathsf{C}$ and $\gamma:{\cal T}X\to X$ is a morphism of
$\mathsf{C}$, called the _structure map_ of the algebra, such that the
following diagrams commute:

A _morphism of Eilenberg-Moore algebras_ is a morphism of $\mathsf{C}$ that
commutes with the structure maps. That is, if $(X,\gamma)$ and $(Y,\delta)$
are two algebras and $h:X\to Y$ is a morphism of $\mathsf{C}$, then $h$ is a
morphism of algebras $h:(X,\gamma)\to(Y,\delta)$ if the following diagram
commutes:

The Eilenberg-Moore algebras for $({\cal T},\eta,\mu)$ and their morphisms
form the _Eilenberg-Moore_ category over the monad ${\cal T}$. The Eilenberg-
Moore category for the list monad is the category of monoids and monoid
homomorphisms. The Eilenberg-Moore category for the powerset monad is the
category of complete upper semilattices and semilattice homomorphisms.

In our application, we will focus on the monad of _$d$ -ary prefix codes_ on
the category $\mathsf{Set}$ of sets and set functions.

##  3 Axioms

In this section, we state the axioms that are sufficient for the optimality of
our generalized Huffman algorithm.

Recall that a _prefix code_ over a fixed $d$-ary alphabet $\Sigma$ is a set of
finite-length words over $\Sigma$ whose elements are pairwise incomparable
with respect to the prefix relation. A prefix code $C$ is _exhaustive_ if
every infinite $d$-ary string has a prefix in $C$. As a consequence of König’s
lemma, every exhaustive prefix code over a finite alphabet is finite, but not
every finite prefix code is exhaustive.

Let $\mathcal{C}:\mathsf{Set}\to\mathsf{Set}$ be an endofunctor in which

  * •

$\mathcal{C}X$ is the set of pairs $(C,r)$ such that $C$ is a prefix code over
a $d$-ary alphabet for some arbitrary but fixed $d\geq 2$ and $r:C\to X$, and

  * •

for $h:X\to Y$, $\mathcal{C}h:\mathcal{C}X\to\mathcal{C}Y$ with
$\mathcal{C}h(C,r)=(C,h\circ r)$.

The functor $\mathcal{C}$ carries a natural monad structure with unit
$\eta:I\to\mathcal{C}$ and multiplication $\mu:\mathcal{C}^{2}\to\mathcal{C}$
defined by: for $a\in X$ and $(C,r)\in\mathcal{C}^{2}X$ with
$r(x)=(C_{x},r_{x})$,

$\displaystyle\eta_{X}(a)$
$\displaystyle=(\\{\varepsilon\\},\varepsilon\mapsto a)$
$\displaystyle\mu_{X}(C,r)$ $\displaystyle=(\\{xy\mid x\in C,\ y\in
C_{x}\\},xy\mapsto r_{x}(y)).$

The map $xy\mapsto r_{x}(y)$ is well defined, as the string $xy$ can be
uniquely split into $x\in C$ and $y\in C_{x}$ because $C$ is a prefix code.

For example, consider the prefix codes $C=\\{0,10,110,111\\}$ and
$C_{0}=C_{10}=C_{110}=C_{111}=\\{00,11\\}$ over the binary alphabet
$\\{0,1\\}$. The code $C$ is exhaustive but the others are not. Let

$\displaystyle r_{0}(00)=2$ $\displaystyle r_{10}(00)=4$ $\displaystyle
r_{110}(00)=6$ $\displaystyle r_{111}(00)=8$ $\displaystyle r_{0}(11)=3$
$\displaystyle r_{10}(11)=5$ $\displaystyle r_{110}(11)=7$ $\displaystyle
r_{111}(11)=9$ $\displaystyle r(0)=(C_{0},r_{0})$ $\displaystyle
r(10)=(C_{10},r_{10})$ $\displaystyle r(110)=(C_{110},r_{110})$ $\displaystyle
r(111)=(C_{111},r_{111}).$

Then
$(C_{0},r_{0}),(C_{10},r_{10}),(C_{110},r_{110}),(C_{111},r_{111})\in\mathcal{C}{\mathbb{N}}$
and $(C,r)\in\mathcal{C}^{2}{\mathbb{N}}$, and
$\mu_{\mathbb{N}}(C,r)=(C^{\prime},r^{\prime})\in\mathcal{C}{\mathbb{N}}$,
where

$\displaystyle C^{\prime}=\\{000,011,1000,1011,11000,11011,11100,11111\\}$
$\displaystyle r^{\prime}(000)=2,\ r^{\prime}(011)=3,\ r^{\prime}(1000)=4,\
r^{\prime}(1011)=5,$ $\displaystyle r^{\prime}(11000)=6,\
r^{\prime}(11011)=7,\ r^{\prime}(11100)=8,\ r^{\prime}(11111)=9.$

Suppose there is a fixed Eilenberg-Moore algebra $(W,w)$ with
$w:\mathcal{C}W\to W$. We call the elements of $W$ _weights_ and $(W,w)$ a
_weighting_. If $(C,r)\in\mathcal{C}W$, then thinking of the elements of $C$
as a tree, the map $r:C\to W$ assigns a weight to each leaf of the tree, and
the map $w$ tells how to assign a weight to the object $(C,r)$ based on the
leaf weights $r$.

To define a notion of optimality, we assume that $W$ is totally preordered by
$\leq$; that is, $\leq$ is reflexive and transitive, and for all $x,y\in W$,
either $x\leq y$ or $y\leq x$ (or both). Smaller values of $W$ in the order
$\leq$ are considered better. We write $x\equiv y$ if both $x\leq y$ and
$y\leq x$. Suppose further that we have a preorder on $\mathcal{C}W$, also
denoted $\leq$, satisfying the following properties.

  1. (i)

If $f:C\to D$ is bijective and length-nondecreasing, and if $r\leq s\circ f$
pointwise, then $(C,r)\leq(D,s)$. This says that longer codewords or larger
leaf values cannot cause a decrease in the order $\leq$.

  2. (ii)

(Exchange property) If $r(x)\leq r(y)$, $|x|\leq|y|$, and

$\displaystyle s(z)$ $\displaystyle=\begin{cases}r(x),&\text{if $z=y$},\\\
r(y),&\text{if $z=x$},\\\ r(z),&\text{if $z\in
C\setminus\\{x,y\\}$},\end{cases}$

then $(C,s)\leq(C,r)$. That is, it never hurts to swap a larger element deeper
in the tree with a smaller element higher in the tree.

  3. (iii)

The monad structure maps $\eta_{W}:W\to\mathcal{C}W$ and
$\mu_{W}:\mathcal{C}^{2}W\to\mathcal{C}W$ are monotone with respect to $\leq$,
where $\leq$ on $\mathcal{C}^{2}W$ is defined by:

$\displaystyle(C,r)\leq(D,s)\ \Leftrightarrow\
\mathcal{C}w(C,r)\leq\mathcal{C}w(D,s).$

Some special cases of (i) are

  * •

If $f:C\to D$ is bijective and length-nondecreasing, then $(C,s\circ
f)\leq(D,s)$. Thus lengthening codewords cannot cause $\leq$ to decrease.

  * •

If $f:C\to D$ is bijective and length-preserving, then $(C,s\circ
f)\equiv(D,s)$. This says that the order $\leq$ on trees depends only on the
lengths of the codewords in $C$, not on the actual codewords themselves.

  * •

If $r,s:C\to W$ and $r\leq s$ pointwise, then $(C,r)\leq(C,s)$. Thus larger
leaf values cannot cause $\leq$ to decrease.

We assume these properties hold for the algorithm described in the next
section.

For $(C,r),(D,s)\in\mathcal{C}W$, let us write $(C,r)\sim(D,s)$ if the
multisets of weights represented by the two objects are the same; that is,
there is a bijective function $f:C\to D$ such that $r=s\circ f$. A tree
$(C,r)\in\mathcal{C}W$ is defined to be _optimal_ (for its multiset of
weights) if $(C,r)$ is $\leq$-minimum in its $\sim$-class; that is,
$(C,r)\leq(D,s)$ for all $(D,s)$ such that $(C,r)\sim(D,s)$.

We will give two detailed examples in §6.

##  4 Algorithm

Suppose we are given a multiset $M$ of weights in $W$, $|M|\geq 2$. We would
like to find an optimal tree for this multiset of weights. The following is a
recursive algorithm to find such an optimal tree.

  1. 1.

Say there are $n\geq 2$ elements in $M$. Let $k\in\\{2,\ldots,d\\}$ such that
$n\equiv k\bmod(d-1)$. Let $a_{0},\ldots,a_{k-1}$ be the $k$ elements of least
weight. Form the object

$\displaystyle(\\{0,1,\ldots,k-1\\},i\mapsto a_{i})\in\mathcal{C}W.$

If there are no other elements of $M$, return that object.

  2. 2.

Otherwise, let

$\displaystyle M^{\prime}$ $\displaystyle=\\{(\\{0,1,\ldots,k-1\\},i\mapsto
a_{i})\\}\cup\\{\eta_{W}(a)\mid a\in M\setminus\\{a_{0},\ldots,a_{k-1}\\}\\},$

a multiset of $n-k+1<n$ elements of $\mathcal{C}W$.

  3. 3.

Recursively call the algorithm at step 1 with
$M^{\prime\prime}=\\{w(E,t)\mid(E,t)\in M^{\prime}\\}$, a multiset of elements
of $W$. This returns a tree $(D,s)$ of type $\mathcal{C}W$ that is optimal for
$M^{\prime\prime}$. The bijective map $s:D\to M^{\prime\prime}$ factors as
$w\circ s^{\prime}$ for some bijective $s^{\prime}:D\to M^{\prime}$, and
$(D,s^{\prime})\in\mathcal{C}^{2}W$ with $\mathcal{C}w(D,s^{\prime})=(D,w\circ
s^{\prime})=(D,s)$. Flatten this to $\mu_{W}(D,s^{\prime})\in\mathcal{C}W$ and
return that value.

Note that the number of items combined in step 1 will be $d$ in all recursive
calls except possibly the first. This is because in every step, if
$k\in\\{2,3,\ldots,d\\}$, then after that step the number of remaining
elements will be $(c(d-1)+k)-k+1=c(d-1)+1$, which is congruent to $d$ mod
$d-1$, so $d$ elements will be taken in the next step. But from that point on,
it is an invariant of the recursion that the number of elements remaining is
$1$ mod $d-1$, since in each step we remove $d$ elements and add one back,
decreasing the number by $d-1$.

##  5 Correctness

In this section, we prove the correctness of the algorithm, making use of the
following lemma.

######  Lemma 1.

Let $k\in\\{2,3,\ldots,d\\}$ and $k\equiv|M|\bmod(d-1)$. Let
$a_{0},\ldots,a_{k-1}$ be the $k$ elements of $M$ of least weight, listed in
nondecreasing order of weight. There is an optimal tree in $\mathcal{C}W$ in
which $a_{0},\ldots,a_{k-1}$ are sibling leaves at the deepest level and have
no other siblings.

###### Proof.

Let $(C,r)\in\mathcal{C}W$ be optimal. Axiom (i) allows us to transform
$(C,r)$ so that there are no deficient nodes (nodes with fewer than $d$
children) at any level except the deepest, and only one deficient node at the
deepest level. Thus we can assume without loss of generality that there are
$k$ elements $x_{0},\ldots,x_{k-1}\in C$ of maximum length $n$ in $C$ with a
common prefix of length $n-1$, and no other $y\in C$ has that prefix. Say the
$x_{0},\ldots,x_{k-1}$ are listed in nondecreasing order of $r(x_{i})$; that
is, $r(x_{i})\leq r(x_{j})$ for all $0\leq i\leq j\leq k-1$. Let
$y_{0},\ldots,y_{k-1}\in C$ such that $r(y_{i})=a_{i}$. Since the $a_{i}$ are
minimal, $r(y_{i})\leq r(x_{i})$. Because the $|x_{i}|$ are of maximum length,
$|y_{i}|\leq|x_{i}|$. Now we can swap using axiom (ii). Let

$\displaystyle s(z)$ $\displaystyle=\begin{cases}r(x_{i}),&\text{if
$z=y_{i}$},\\\ r(y_{i}),&\text{if $z=x_{i}$},\\\
r(z),&\text{otherwise}.\end{cases}$

Then $(C,s)\leq(C,r)$. But since $(C,r)$ was optimal, $(C,r)\equiv(C,s)$ and
$(C,s)$ is also optimal. ∎

######  Theorem 2.

The algorithm of §4 produces an optimal tree.

###### Proof.

By induction on $n$. The basis is $n\leq d$, in which case the result is
straightforward.

Suppose that we have a multiset $M$ of $n>d$ elements of $W$. Let $(C,r)$ be
an optimal tree for $M$. Let $k\in\\{2,3,\ldots,d\\}$ be congruent mod $d-1$
to $|M|$. Let $a_{0},\ldots,a_{k-1}$ be the $k$ smallest elements of $M$. By
Lemma 1, we can assume without loss of generality that $a_{0},\ldots,a_{k-1}$
are siblings and occur at maximum depth in $(C,r)$, so there exist strings
$x\kern 1.0pt0,x\kern 1.0pt1,\ldots,x\kern 1.0pt(k-1)\in C$ of maximum length
with a common prefix $x$ and $r(x\kern 1.0pti)=a_{i}$. Remove the strings
$x\kern 1.0pti$ from $C$ and replace them with $x$. Call the resulting set
$C^{\prime}$. For $z\in C^{\prime}$, let

$\displaystyle r^{\prime}(z)$
$\displaystyle=\begin{cases}(\\{0,1,\ldots,k-1\\},i\mapsto a_{i}),&\text{if
$z=x$},\\\ \eta_{W}(r(z)),&\text{otherwise}.\end{cases}$

Then $(C^{\prime},r^{\prime})\in\mathcal{C}^{2}W$ and
$(C,r)=\mu_{W}(C^{\prime},r^{\prime})$. The multiset of values of $r^{\prime}$
is just the $M^{\prime}$ of step 2 of the algorithm.

The algorithm will form the multiset

$\displaystyle M^{\prime\prime}=\\{w(E,t)\mid(E,t)\in
M^{\prime}\\}=\\{w(r^{\prime}(z))\mid z\in C^{\prime}\\}$

and recursively call with these weights. By the induction hypothesis, the
return value will be a tree $(D,s)\in\mathcal{C}W$ that is optimal for
$M^{\prime\prime}$, thus $(D,s)\leq(C^{\prime},w\circ r^{\prime})$, and the
bijective map $s:D\to M^{\prime\prime}$ factors as $s=w\circ r^{\prime}\circ
f$ for some bijective $f:D\to C^{\prime}$. Let $s^{\prime}=r^{\prime}\circ f$.
By axiom (iii),

$\displaystyle\mathcal{C}w(D,s^{\prime})=(D,w\circ
s^{\prime})=(D,s)\leq(C^{\prime},w\circ
r^{\prime})=\mathcal{C}w(C^{\prime},r^{\prime}),$

therefore $(D,s^{\prime})\leq(C^{\prime},r^{\prime})$, and since $\mu_{W}$ is
monotone,

$\displaystyle\mu_{W}(D,s^{\prime})\leq\mu_{W}(C^{\prime},r^{\prime})=(C,r).$

As $(C,r)$ was optimal, so is $\mu_{W}(D,s^{\prime})$, and this is the value
returned by the algorithm. ∎

##  6 Applications

By choosing two specific weightings $(W,w)$ and defining the ordering
relations $\leq$ appropriately, we can recover two special cases of this
algorithm.

###  6.1 Huffman coding

Our first application is Huffman codes. Here we wish to minimize the expected
length of variable-length codewords, given frequencies of the letters to be
coded. For this application, we take
$W={\mathbb{R}}_{+}=\\{a\in{\mathbb{R}}\mid a\geq 0\\}$ with weighting

$\displaystyle w(C,r)$ $\displaystyle=\sum_{x\in C}r(x).$

Recall that for $a\in W$ and $(C,r)\in\mathcal{C}^{2}W$ with
$r(x)=(C_{x},r_{x})$,

$\displaystyle\eta_{W}(a)$
$\displaystyle=(\\{\varepsilon\\},\varepsilon\mapsto a)$
$\displaystyle\mu_{W}(C,r)$ $\displaystyle=(\\{xy\mid x\in C,\ y\in
C_{x}\\},xy\mapsto r_{x}(y)).$

Then $(W,w)$ is an Eilenberg-Moore algebra for the monad
$(\mathcal{C},\mu,\eta)$, as

$\displaystyle w(\eta_{W}(a))$
$\displaystyle=w(\\{\varepsilon\\},\varepsilon\mapsto
a)=\sum_{x\in\\{\varepsilon\\}}(\varepsilon\mapsto a)(x)=a,$ $\displaystyle
w(\mu_{W}(C,r))$ $\displaystyle=\sum_{x\in C}\sum_{y\in
C_{x}}r_{x}(y)=\sum_{x\in C}w(C_{x},r_{x})$ $\displaystyle=\sum_{x\in
C}w(r(x))=w(C,w\circ r)=w(\mathcal{C}w(C,r)).$

In addition, let us define $\alpha:\mathcal{C}W\to W$ by

$\displaystyle\alpha(C,r)$ $\displaystyle=\sum_{x\in C}|x|\cdot r(x).$

######  Lemma 3.

$\displaystyle\alpha(\eta_{W}(a))$ $\displaystyle=0$
$\displaystyle\alpha(\mu_{W}(C,r))$ $\displaystyle=\alpha(C,w\circ
r)+w(C,\alpha\circ r).$

###### Proof.

$\displaystyle\alpha(\eta_{W}(a))$
$\displaystyle=\alpha(\\{\varepsilon\\},\varepsilon\mapsto
a)=\sum_{x\in\\{\varepsilon\\}}|x|\cdot(\varepsilon\mapsto
a)(x)=|\varepsilon|\cdot a=0,$ $\displaystyle\alpha(\mu_{W}(C,r))$
$\displaystyle=\alpha(\\{xy\mid x\in C,\ y\in C_{x}\\},xy\mapsto r_{x}(y))$
$\displaystyle=\sum_{x\in C}\sum_{y\in C_{x}}|xy|\cdot r_{x}(y)=\sum_{x\in
C}|x|\sum_{y\in C_{x}}r_{x}(y)+\sum_{x\in C}\sum_{y\in C_{x}}|y|\cdot
r_{x}(y)$ $\displaystyle=\sum_{x\in C}|x|\cdot w(C_{x},r_{x})+\sum_{x\in
C}\alpha(C_{x},r_{x})=\sum_{x\in C}|x|\cdot w(r(x))+\sum_{x\in C}\alpha(r(x))$
$\displaystyle=\alpha(C,w\circ r)+w(C,\alpha\circ r).\qed$

Note that $\alpha$ and $w$ agree on trees of depth one:

$\displaystyle w(\\{0,1,\ldots,k-1\\},i\mapsto a_{i})$
$\displaystyle=\sum_{i=0}^{k-1}a_{i},$
$\displaystyle\alpha(\\{0,1,\ldots,k-1\\},i\mapsto a_{i})$
$\displaystyle=\sum_{i=0}^{k-1}|i|\cdot a_{i}=\sum_{i=0}^{k-1}a_{i},$

where $|i|$ refers to the length of $i$ as a string, which in this case is 1.

The map $\alpha$ is related to the Shannon entropy $H$. If $r(x)=d^{-|x|}$,
the probability of a $d$-ary codeword $x$ under the uniform distribution on a
$d$-ary alphabet, then

$\displaystyle H(C,r)$ $\displaystyle=\sum_{x\in C}-d^{-|x|}\log
d^{-|x|}=\sum_{x\in C}|x|\cdot d^{-|x|}\log d=\alpha(C,r)\log d,$

so $\alpha(C,r)=H(C,r)/\log d$.

To use the algorithm in §4, we need an order $\leq$ on $\mathcal{C}W$. Define
$(C,r)\leq(D,s)$ if $(C,r)\sim(D,s)$, that is, there is a bijective map
$f:C\to D$ such that $r=s\circ f$, and

$\displaystyle\alpha(C,r)\leq\alpha(D,s).$

Note that if $(C,r)\leq(D,s)$, then

$\displaystyle w(C,r)$ $\displaystyle=\sum_{x\in C}r(x)=\sum_{x\in
C}s(f(x))=\sum_{y\in D}s(y)=w(D,s).$

According to axiom (iii), for $(C,r),(D,s)\in\mathcal{C}^{2}W$,

$\displaystyle(C,r)\leq(D,s)\ $ $\displaystyle\Leftrightarrow\
\mathcal{C}w(C,r)\leq\mathcal{C}w(D,s)$ $\displaystyle\Leftrightarrow\
\alpha(\mathcal{C}w(C,r))\leq\alpha(\mathcal{C}w(D,s))$
$\displaystyle\Leftrightarrow\ \alpha(C,w\circ r)\leq\alpha(D,w\circ s).$ (1)

Also, if $(C,r)\leq(D,s)$ in $\mathcal{C}^{2}W$, then

$\displaystyle w(C,\alpha\circ r)$ $\displaystyle=\sum_{x\in
C}\alpha(r(x))=\sum_{x\in C}\alpha(s(f(x)))=\sum_{y\in
D}\alpha(s(y))=w(D,\alpha\circ s).$ (2)

######  Lemma 4.

$\mu_{W}:\mathcal{C}^{2}W\to\mathcal{C}W$ and $\eta_{W}:W\to\mathcal{C}W$ are
monotone with respect to $\leq$.

###### Proof.

For $\eta_{W}$, suppose $a,b\in W$ and $a\leq b$. By Lemma 3,

$\displaystyle\alpha(\eta_{W}(a))$ $\displaystyle=0=\alpha(\eta_{W}(b))$
$\displaystyle w(\eta_{W}(a))$ $\displaystyle=a\leq b=w(\eta_{W}(b)).$

For $\mu_{W}$, suppose $(C,r),(D,s)\in\mathcal{C}^{2}W$ and $(C,r)\leq(D,s)$.
By Lemma 3, (1), and (2),

$\displaystyle\alpha(\mu_{W}(C,r))$ $\displaystyle=\alpha(C,w\circ
r)+w(C,\alpha\circ r)$ $\displaystyle\leq\alpha(D,w\circ s)+w(D,\alpha\circ
s)=\alpha(\mu_{W}(D,s)).\qed$

######  Theorem 5.

The algorithm in §4 for the algebra $({\mathbb{R}}_{+},w)$ and ordering
relation $\leq$ defined by $\alpha$ is equivalent to Huffman’s algorithm and
produces an optimal Huffman code for a given multiset of weights.

###### Proof.

Take $X\subset{\mathbb{R}}_{+}$ to be a finite multiset and sort the set $X$
in increasing order. For the binary case of Huffman codes (the $d$-ary version
follows the same way), we always choose $k=2$. For the first step, let
$a_{0},a_{1}\in X$ be the two smallest elements in the list. Form the object
$(\\{0,1\\},i\mapsto a_{i})\in\mathcal{C}X$. In the case $n=2$, this is the
only remaining object in the list. Otherwise, we combined them into one
element with the sum of the weights of $a_{0}$ and $a_{1}$ as the weight of
the new element, exactly as the Huffman coding does.

For the case $n>2$, there are remaining elements in the set $X$. Take all
remaining $a\in X\backslash\\{a_{0},a_{1}\\}$ and replace $a$ by
$\eta_{X}(a)\in\mathcal{C}X$. We are left with $n-1$ elements of type
$\mathcal{C}X$. If we recursively call the algorithm in step 1, we are
continually combining the least two elements in the remaining set with the
elements weighted by $w$. Note by the weighting $w$, $w(\eta_{X}(a))=a$ and on
elements in $\mathcal{C}X$, $w$ takes the sum of $r(x)^{\prime}s$, exactly as
Huffman coding does. Finally, this leaves us with a tree in $\mathcal{C}^{2}X$
where leaves have weights of the form $\eta_{X}(a_{i})$. Denote this tree by
$(D,s)$. Taking $\mu_{X}(D,S)$ gives our desired tree in $\mathcal{C}X$. ∎

###  6.2 PIFO trees

PIFO trees were introduced in [3] as a model for programmable packet
schedulers. In the recent work of [1], further work was done on PIFO trees
giving a semantics that allows for certain embedding algorithms. The notion of
a _homomorphic embedding_ was defined for the purpose determining when a PIFO
tree could be represented by another PIFO tree and for finding an embedding if
so. The embedding algorithm we consider takes an arbitrary PIFO tree and
embeds it into a $d$-ary tree. This becomes a special case of the algorithm of
§4, where we choose $w$ in the weighting $(W,w)$ to minimize the height of the
target $d$-ary tree into which the source tree can embed.

For this application, we take $W={\mathbb{N}}$ with weighting

$\displaystyle w(C,r)$ $\displaystyle=\max_{x\in C}|x|+r(x).$

This gives an Eilenberg-Moore algebra $(W,w)$ for the monad
$(\mathcal{C},\mu,\eta)$. For $a\in W$ and $(C,r)\in\mathcal{C}^{2}W$ with
$r(x)=(C_{x},r_{x})$, as before we have

$\displaystyle\eta_{W}(a)$
$\displaystyle=(\\{\varepsilon\\},\varepsilon\mapsto a)$
$\displaystyle\mu_{W}(C,r)$ $\displaystyle=(\\{xy\mid x\in C,\ y\in
C_{x}\\},xy\mapsto r_{x}(y)),$

so

$\displaystyle w(\eta_{W}(a))$
$\displaystyle=w(\\{\varepsilon\\},\varepsilon\mapsto
a)=\max_{x\in\\{\varepsilon\\}}|x|+(\varepsilon\mapsto
a)(x)=|\varepsilon|+a=a,$ $\displaystyle w(\mu_{W}(C,r))$
$\displaystyle=w(\\{xy\mid x\in C,\ y\in C_{x}\\},xy\mapsto
r_{x}(y))=\max_{x\in C}\max_{y\in C_{x}}|xy|+r_{x}(y)$
$\displaystyle=\max_{x\in C}\max_{y\in C_{x}}|x|+|y|+r_{x}(y)=\max_{x\in
C}|x|+\max_{y\in C_{x}}|y|+r_{x}(y)$ $\displaystyle=\max_{x\in
C}|x|+w(C_{x},r_{x})=\max_{x\in C}|x|+w(r(x))$ $\displaystyle=w(C,w\circ
r)=w(\mathcal{C}w(C,r)).$

For $(C,r),(D,s)\in\mathcal{C}W$, let us define $(C,r)\leq(D,s)$ if there is a
bijective function $f:C\to D$ such that $r=s\circ f$ and

$\displaystyle w(C,r)\leq w(D,s).$

######  Lemma 6.

$\mu_{W}:\mathcal{C}^{2}W\to\mathcal{C}W$ and $\eta_{W}:W\to\mathcal{C}W$ are
monotone with respect to $\leq$.

###### Proof.

For $\eta_{W}$, if $a\leq b$, then $w(\eta_{W}(a))=a\leq b=w(\eta_{W}(b))$.

For $\mu_{W}$, suppose $(C,r),(D,s)\in\mathcal{C}^{2}W$ and $(C,r)\leq(D,s)$.
According to axiom (iii),

$\displaystyle(C,r)\leq(D,s)\ $ $\displaystyle\Leftrightarrow\
\mathcal{C}w(C,r)\leq\mathcal{C}w(D,s)$ $\displaystyle\Leftrightarrow\
w(\mathcal{C}w(C,r))\leq w(\mathcal{C}w(D,s)).$

Then

$\displaystyle w(\mu_{W}(C,r))$ $\displaystyle=w(\mathcal{C}w(C,r))\leq
w(\mathcal{C}w(D,s))=w(\mu_{W}(D,s)).\qed$

######  Theorem 7.

The algorithm of §4 for the algebra $({\mathbb{N}},w)$ and ordering relation
$\leq$ defined by $w$ is equivalent to determining whether an embedding of a
PIFO tree in a bounded $d$-ary tree exists and finding the embedding if so.

##  7 Conclusion

We have presented a generalized Huffman algorithm and shown that two known
algorithms, Huffman codes and embedding of PIFOs trees, can be derived as
special cases. The PIFO embedding algorithm was introduced in [1] and observed
to be very similar to the usual combinatorial algorithm for optimal Huffman
codes, albeit based on a different algebraic structure. This suggested the
common generalization presented in this paper.

Our generalized algorithm exploits the monadic structure of prefix codes,
which allows a more algebraic treatment of the Huffman algorithm than the
usual combinatorial approaches. The two applications fit naturally in the
categorical setting by choosing specific Eilenberg-Moore algebras for each
one. It is possible that other greedy algorithms might fit into this framework
as well.

## References

  * [1] Anshuman Mohan, Yunhe Liu, Nate Foster, Tobias Kappé, and Dexter Kozen,  “Formal abstractions for packet scheduling,”  Tech. Rep. http://arxiv.org/abs/2211.11659, Cornell University, November 2022.
  * [2] Thomas M. Cover and Joy A. Thomas,  Elements of Information Theory,  Wiley, second edition, 2006.
  * [3] Anirudh Sivaraman, Suvinay Subramanian, Mohammad Alizadeh, Sharad Chole, Shang-Tse Chuang, Anurag Agrawal, Hari Balakrishnan, Tom Edsall, Sachin Katti, and Nick McKeown,  “Programmable packet scheduling at line rate,”  in SIGCOMM, 2016.
  * [4] Albert Gran Alcoz, Alexander Dietmüller, and Laurent Vanbever,  “SP-PIFO: Approximating push-in first-out behaviors using strict-priority queues,”  in NSDI, 2020.
  * [5] Andrea Asperti and Giuseppe Longo,  Categories, Types and Structures: An introduction to category theory for the working computer scientist,  Foundations of Computing. MIT Press, 1991.
  * [6] Michael Barr and Charles Wells,  Toposes, Triples and Theories, vol. 278 of Grundlehren der mathematischen Wissenschaften,  Springer, 2013.
  * [7] Michael Barr and Charles Wells,  Category Theory for Computing Science,  Prentice Hall, 1990.
  * [8] Jiří Adámek, Horst Herrlich, and George E. Strecker,  Abstract and concrete categories,  Dover Publications, 2009.
  * [9] Eugenio Moggi,  “Notions of computation and monads,”  Inf. and Comp., vol. 93, no. 1, pp. 55–92, 1991.
  * [10] Philip Wadler,  “Comprehending monads,”  Mathematical Structures in Computer Science, vol. 2, pp. 461–493, 1992.
  * [11] Philip Wadler,  “Monads for functional programming,”  in Advanced Functional Programming: 1st Int. School on Advanced Functional Programming Techniques, Johan Jeuring and Erik Meijer, Eds., vol. 925 of Lecture Notes in Computer Science, pp. 24–52. Springer-Verlag, 1995\.


# Local mirror symmetry via SYZ

Benjamin Gammage

###### Abstract.

In this note, we explain how mirror symmetry for basic local models in the
Gross-Siebert program can be understood through the non-toric blowup
construction described by Gross-Hacking-Keel. This is part of a program to
understand the symplectic geometry of affine cluster varieties through their
SYZ fibrations.

##  1\. Introduction

In the Gross-Siebert program, a pair of dual spaces is described by the
combinatorial data of an integral affine manifold with singularities, which is
supposed to be understood as the base of a Lagrangian torus fibration with
singularities. Locally near a smooth point of the base, the total space looks
like the cotangent bundle of a torus, projecting to its cotangent fibers.

Near singular points in the base, the behavior of a torus fibration can become
more complicated as torus fibers acquire singularities. However, in each
dimension $N$, there is a finite list of such singularities
$\mathfrak{s}_{n,m}$ (with $n+m=N$) which are known to serve as building
blocks for a wide class of integral affine manifolds. Above the singularity
$\mathfrak{s}_{n,m},$ the symplectic manifold is described by the local model

$X_{n,m}:=\\{z_{0}\cdots z_{n}=1+u_{1}+\cdots u_{m}\mid
z_{i}\in\mathbb{C},u_{j}\in\mathbb{C}^{\times}\\},$

equipped with singular Lagrangian torus fibration $X_{n,m}\to\mathbb{R}^{n+m}$
by

(1.1)
$(z_{0},\ldots,z_{n},u_{1},\ldots,u_{m})\mapsto(|z_{0}|^{2}-|z_{1}|^{2},\ldots,|z_{0}|^{2}-|z_{n}|^{2},\log|u_{1}|,\ldots,\log|u_{m}|).$

In the case $n=1,$ this SYZ fibration on the conic bundle $X_{1,m}$ was
studied extensively in [2].

In this paper, we will show (in Section 3) that the spaces $X_{n,m}$ may be
described using a generalization of the non-toric blowup construction of [17,
18]. The mirror to that construction was described in detail in [11]
(following earlier works [30, 22, 26]); by generalizing that mirror
construction to the case of $X_{n,m},$ we can deduce a mirror symmetry
equivalence between these spaces:

######  Theorem 1.2.

There is an equivalence of categories
$\textup{Fuk}(X_{m,n})\cong\textup{Coh}(X_{n,m}).$

######  Remark 1.3.

Theorem 1.2 as formulated has long been expected; a proof of this theorem from
a more traditional Fukaya-categorical perspective, providing a more detailed
correspondence between homological mirror symmetry and SYZ geometry, will
appear in [3]. Many special cases of Theorem 1.2 appear in the literature,
including the case $m=-1$ (the $(n-1)$-dimensional pants, studied in [20] and
from the perspective of Lagrangian skeleta in [23]), and the case $n=1$ (the
substrate of the basic “generalized cluster transformation,” studied in [22,
26]) – indeed, in some sense the content of this paper consists in combining
those two calculations. (Other special cases of this theorem can be found in
[6, 27].)

But the broader novelty in this work is in relating the Lagrangian skeleton of
$\textup{Fuk}(X_{m,n})$ to the geometry of its SYZ fibration (1.1). This is
part of a larger program, to be discussed in Section 3, to understand
Lagrangian skeleta and mirror symmetry for affine cluster varieties via their
SYZ fibrations.

On the A-side, the main input to this theorem is a calculation of the
Lagrangian skeleton $\mathbb{L}_{m,n}$ of the Weinstein manifold $X_{m,n}.$
Let $\Sigma_{\mathbb{C}^{n}\times(\mathbb{C}^{\times})^{m}}$ be the fan of
cones in $\mathbb{R}^{n+m}$ spanned by subsets of the first $n$ basis vectors
$e_{1},\ldots,e_{n},$ identifying each cone $\sigma$ with the corresponding
subset of $[n].$ Introduce the conic Lagrangian

(1.4)
$\mathbb{L}_{\mathbb{C}^{n}\times(\mathbb{C}^{\times})^{m}}:=\bigcup_{\sigma\subset[n]}\sigma^{\perp}\times\sigma\subset\mathbb{R}^{n+m}/\left(\mathbb{Z}+\frac{1}{2}\right)^{n+m}\times\mathbb{R}^{n+m}=\mathrm{T}^{*}T^{n+m},$

where in the first factor we write $\sigma^{\perp}$ for the image of the
subspace orthogonal to $\sigma$ under the projection $\mathbb{R}^{n+m}\to
T^{n+m}.$ This Lagrangian, studied in [8, 7, 9], following earlier work [5],
is known [13, 32] to be the skeleton of the Liouville-sectorial mirror to the
toric variety $\mathbb{C}^{n}\times(\mathbb{C}^{\times})^{m}$ [19, 31, 29],
and its boundary

$\partial\mathbb{L}_{\mathbb{C}^{n}\times(\mathbb{C}^{\times})^{m}}=\bigcup_{\emptyset\neq\sigma\subset[n]}\sigma^{\perp}\times\partial^{\infty}\sigma\subset\mathrm{S}^{*}T^{n+m}$

is mirror to the toric boundary
$\partial\mathbb{C}^{n}\times(\mathbb{C}^{\times})^{m}$ [23, 13].

######  Remark 1.5.

In [13], we avoided the translation $\mathbb{Z}\mapsto\mathbb{Z}+\frac{1}{2}$
appearing in the definition of the quotient torus $T^{n+m}$ in (1.4) by
changing the sign of the constant coefficient in $1+u_{1}+\cdots+u_{m}.$ In
this paper we prefer the more symmetrical convention for this polynomial.

Observe that $\mathbb{L}_{\mathbb{C}^{n}\times(\mathbb{C}^{\times})^{m}}$ is
globally a product

$\mathbb{L}_{\mathbb{C}^{n}\times(\mathbb{C}^{\times})^{m}}=\mathbb{L}_{\mathbb{C}^{n}}\times
T^{m}\subset\mathrm{T}^{*}T^{n}\times\mathrm{T}^{*}T^{m}.$

We will be interested in a second Lagrangian which involves the degeneration
of the $T^{m}$ factor in that product. Let
$\mathbb{L}^{m}_{\operatorname{deg}}\subset\mathbb{C}^{m+1}$ be the
“Lagrangian $m$-torus degeneration,”

$\mathbb{L}^{m}_{\operatorname{deg}}:=\\{(z_{0},\ldots,z_{m})\mid|z_{0}|=\cdots=|z_{m}|,\prod_{i=0}^{m}z_{i}\in\mathbb{R}_{\geq
0}\\},$

studied in [24, 10] as the skeleton of a mirror to a general linear
hypersurface in $(\mathbb{C}^{\times})^{m},$ and in [22, 26] as part of
higher-dimensional cluster theory.

Our main result on the symplectic geometry of symplectic manifold $X_{m,n}$ is
a calculation of its Lagrangian skeleton $\mathbb{L}_{m,n}.$

######  Theorem 1.6.

The Lagrangian skeleton $\mathbb{L}_{m,n}$ of $X_{m,n}$ has a cover

$\mathbb{L}_{m,n}=\mathcal{L}_{1}\cup_{\mathcal{L}}\mathcal{L}_{2},$

where
$\mathcal{L}_{1}\cong\mathbb{L}_{\mathbb{C}^{n}\times(\mathbb{C}^{\times})^{m}},$
$\mathcal{L}_{2}\cong(\partial\mathbb{L}_{\mathbb{C}^{n}})\times\mathbb{L}^{m}_{\operatorname{deg}},$
and their intersection is
$\mathcal{L}\cong(\partial\mathbb{L}_{\mathbb{C}^{n}})\times\mathbb{R}\times
T^{m}.$

The proof of Theorem 1.6, essentially a combination of the calculations in
[23, 26], will be given in Section 2.

###### Proof of Theorem 1.2.

Given Theorem 1.6, the proof of Theorem 1.2 is only a slight generalization of
the proof of [11, Example 4.13] (which in turn is just a recapitulation of
[30, Proposition 4.10]). The codescent result of [14] – which we can reframe
as a descent result by passing to presentable categories – says that
$\textup{Fuk}(X_{m,n})$ can be calculated as the pullback of a diagram of
categories associated to the Lagrangians $\mathcal{L}_{1},\mathcal{L}_{2},$
and $\mathcal{L}.$

These categories are computed in [19, 23, 13]: Let
$R=\mathbb{C}[z_{1},\ldots,z_{m},u_{1}^{\pm},\ldots,u_{n}^{\pm}].$ Then the
(Ind-completed) Fukaya category of $X_{m,n}$ is equivalent to the pullback

(1.7) $\varprojlim\left(R\operatorname{-mod}\to R/(z_{1}\cdots
z_{m})\operatorname{-mod}\leftarrow R/(z_{1}\cdots z_{m},1+u_{1}+\cdots
u_{n})\operatorname{-mod}\right),$

where the functors are the evident ones.

As explained in [11, 30], an object of the limit (1.7) is given by an
$R$-module $M$, an $R/(z_{1}\cdots z_{m},1+u_{1}+\cdots+u_{n})$-module $N$,
and an isomorphism of the images of these modules in $R/(z_{1}\cdots
z_{m})\operatorname{-mod},$ or in other words of an isomorphism

(1.8) $\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern
21.4514pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\operatorname{Cone}(M\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
21.4967pt\raise 6.15pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\hbox{\hbox{\kern 0.0pt\raise-1.75pt\hbox{$\scriptstyle{z_{1}\cdots
z_{m}}$}}}\kern 3.0pt}}}}}}\ignorespaces{\hbox{\kern 45.4514pt\raise
0.0pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
45.4514pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{M)\cong
N}$}}}}}}}\ignorespaces}}}}\ignorespaces.$

If we think of the isomorphism (1.8) as enforcing the fact that
$1+u_{1}+\cdots+u_{n}$ should act trivially on the cone, then we can
understand it as the data of a map $z_{0}:M\to M$ satisfying
$z_{0}(z_{1}\cdots z_{m})=1+u_{1}+\cdots+u_{n}.$

We conclude that the Ind-completed Fukaya category of $X_{m,n},$ as computed
by the pullback (1.7), is equivalent to the category

$\mathbb{C}[z_{1},\ldots,z_{m},u_{1}^{\pm},\ldots,u_{n}^{\pm},z_{0}]/(z_{0}z_{1}\cdots
z_{m}=1+u_{1}+\cdots+u_{n})\operatorname{-mod}\cong\textup{QCoh}(X_{n,m}).$

By passing to compact objects, we conclude that
$\textup{Fuk}(X_{m,n})\cong\textup{Perf}(X_{n,m})\cong\textup{Coh}(X_{n,m})$
(with the last equivalence coming from smoothness of $X_{n,m}$) as desired. ∎

Further discussion on the meaning of the above result, and its relations to
cluster theory and a generalization of [11], will be postponed to Section 3,
after the computation of the skeleton $\mathbb{L}_{m,n}$ in Section 2. We
conclude the introduction with an example recalling how our construction
recovers the geometry of the “cluster local model” $X_{1,1}.$

######  Example 1.9.

Let $m=n=1,$ so that $\mathfrak{s}_{1,1}$ is the focus-focus singularity,
whose local model

$X_{1,1}=\\{z_{0}z_{1}=1+u\\}=\mathbb{C}^{2}\setminus\\{z_{0}z_{1}=1\\}$

was first studied from the perspective of mirror symmetry in [4, Section 5].
The Weinstein manifold $X_{1,1}$ admits a Lagrangian skeleton $\mathbb{L}$
which is the union of a torus $T=T^{2}$ and a disk whose boundary is glued
along a primitive homology class of $T$. In line with Theorem 1.6, we can
think of this as a union of two open pieces: a torus with a cylinder attached
(the mirror to $\mathbb{C}\times\mathbb{C}^{\times}$) and a disk collapsing
the boundary circle of that cylinder to a point.

##  2\. Calculating the skeleton

Let $\varphi:X_{m,n}\to\mathbb{R}$ be a Morse-Bott Kähler potential for the
Stein manifold $X_{m,n},$ so that its Stein Kähler form is
$\omega=dd^{c}\varphi,$ which has primitive $\lambda=d^{c}\varphi.$ Morse
theory gives a handle presentation of the manifold $X_{m,n},$ where only
critical points of index up to $m+n$ occur, and the union of stable manifolds
for the critical points is a singular Lagrangian subset $\mathbb{L}\subset
X_{m,n},$ the skeleton of $X_{m,n}.$ These Lagrangian skeleta are of great
interest thanks to the fact that the Fukaya category $\textup{Fuk}(X)$ of a
Stein manifold $X$ may be computed locally over its Lagrangian skeleton
$\mathbb{L}$ [16, 15, 14, 25].

The Morse-Bott Kähler potential with which we equip $X_{m,n}$ will be a
deformation of the function

(2.1)
$\varphi(z,u):=\sum_{i=1}^{m}(|z_{0}|^{2}-|z_{i}|^{2})^{2}+\sum_{j=1}^{n}(\log|u_{i}|+\ell)^{2},$

where we have fixed some $\ell\ll 0.$

The function $\varphi$ is natural from the perspective of the SYZ fibration
$\pi:X_{m,n}\to\mathbb{R}^{m+n}$ defined by

(2.2)
$\pi(z,u):=(|z_{0}|^{2}-|z_{1}|^{2},\ldots,|z_{0}|^{2}-|z_{m}|^{2},\log|u_{1}|,\ldots,\log|u_{m}|),$

so that $\varphi$ can be written as
$\varphi(z,u)=d(\pi(z,u),(\vec{0},\vec{\ell})),$ where $d$ is the distance
function on $\mathbb{R}^{n+m}.$ In what follows, we will write
$(\eta_{1},\ldots,\eta_{m},\xi_{1},\ldots,\xi_{m})$ for the natural
coordinates on this SYZ base $\mathbb{R}^{n+m}.$ Note that the general fiber
of this fibration is an $(n+m)$-torus, and it degenerates where $\xi$ is in
the image of the map

(2.3) $\displaystyle\operatorname{Log}:\\{1+u_{1}+\cdots+u_{n}=0\mid
u_{i}\in\mathbb{C}^{\times}\\}\to\mathbb{R}^{n},$
$\displaystyle\vec{u}\mapsto(\log|u_{1}|,\ldots,\log|u_{n}|)$

and at least one of the $\eta_{i}$ is zero.

However, the function $\varphi$ is not actually a Kähler potential on
$X_{m,n},$ since the 2-form $dd^{c}\varphi$ becomes degenerate where two or
more of the $z_{i}$ coordinates become zero. To remedy this, we perturb
$\varphi$ to an actual Kähler potential

(2.4)
$\widetilde{\varphi}(z,u):=\varphi(z,u)+\varepsilon\chi(z_{0},\ldots,z_{m})\sum_{i=0}^{m}|z_{i}|^{2},$

where $\chi$ is a function which is equal to 1 within a neighborhood of the
region where any two of the $z_{i}$ are 0, and equal to 0 outside a
neighborhood of this region. In the region where $\chi$ is 1, this term will
guarantee positivity of $dd^{c}\widetilde{\varphi},$ and in the region where
$\chi$ changes from 1 to 0, its contribution to $dd^{c}\widetilde{\varphi}$ is
bounded, so for $\varepsilon$ sufficiently small, the form
$dd^{c}\widetilde{\varphi}$ will remain positive in this region, ensuring that
$\widetilde{\varphi}$ is indeed a Kähler potential.

Both the original function $\varphi$ and the deformation $\widetilde{\varphi}$
have a Morse-Bott manifold of minima given by the $(n+m)$-torus
$\mathbb{T}:=\\{\eta_{i}=0,\xi_{j}=\ell\\},$ and the remaining critical points
of $\widetilde{\varphi}$ also project under $\pi$ to the subspace
$\mathcal{H}=\\{\eta=0\\}\subset\mathbb{R}^{n+m}.$ To determine these higher-
index critical points, we will imitate [21, 1, 23, 13] in performing a
symplectic isotopy to $X_{m,n}$ by deforming the right-hand side of the
equation $\prod z_{i}=1+\sum u_{j}.$

Within $\mathcal{H},$ the singular locus of the fibration $\pi$ coincides with
the amoeba $\mathcal{A},$ defined as the image of the projection (2.3). The
amoeba $\mathcal{A}$ contains within it a spine, the tropical hypersurface
$\Pi$ defined as the corner locus of the function
$\max(0,\xi_{1},\ldots,\xi_{n}).$ Observe that the complement
$\mathcal{H}\setminus\mathcal{A}$ (or equivalently $\mathcal{H}\setminus\Pi$
consists of $n$ components, one of which is the “all-negative” orthant, and
each of the others can be reached from this one by crossing one of the
hyperplanes $\\{\xi_{i}=0\\}.$ The components of this complement may be
equivalently be described as the $\operatorname{Log}$ images of the loci where
one monomial in the function $1+\sum u_{i}$ dominates all the others. We will
write $C_{i}$ for the component where $u_{i}$ dominates, and $C_{0}$ for the
bottom-left orthant, where $1$ dominates.

We will deform the space $X_{m,n}$ by a symplectic isotopy which brings the
amoeba closer to the spine $\Pi,$ making it easier to understand the Liouville
dynamics of $X_{m,n}.$ This trick was first used in [21] and later elaborated
in [1, Section 4], which we follow here. For $0\leq i\leq n,$ we pick a
tailoring function $\psi_{i}$ (which is called $\phi_{\alpha}$ in [1])
satisfying

$\displaystyle\psi_{i}(\xi)=\begin{cases}0&\text{when
}d(\xi,C_{i})\leq\frac{\epsilon}{2}\\\ 1&\text{when
}d(\xi,C_{i})\geq\epsilon,\end{cases}$ and
$\displaystyle\sum_{j=1}^{n}\left|\frac{\partial\psi_{i}}{\partial\xi_{j}}\right|<\frac{4}{\epsilon},$

for some $\epsilon\ll\ell,$ and we define the family of maps
$\\{f_{s}:(\mathbb{C}^{\times})^{n}\to\mathbb{C}\\}_{0\leq s\leq 1},$ by

$f_{s}(u_{1},\ldots,u_{n}):=(1-s\psi_{0}(u))+\sum_{i=1}^{n}(1-s\psi_{i}(u))u_{i}.$

######  Proposition 2.5 ([1, Section 4]).

The family $P^{n-1}_{s}:=\\{f_{s}=0\\}\subset(\mathbb{C}^{\times})^{n}$ is a
family of symplectic hypersurfaces, related by a symplectic isotopy of the
ambient $(\mathbb{C}^{\times})^{n}.$ For $s=0,$ the hypersurface $P^{n-1}_{0}$
is the usual pair of pants $\\{1+\sum_{i=1}^{n}u_{i}=0\\},$ and when $s=1,$
for $\log|u_{i}|\ll 0,$ the coordinate $u_{i}$ does not appear in the defining
equation of $P^{n-1}_{1},$ so that in that region $P^{n-1}_{1}$ is a product
of $\mathbb{C}^{\times}_{u_{i}}$ with $P^{n-2}_{1}.$

######  Definition 2.6.

Following [23], we call the space $P^{n-1}_{1}$ resulting from applying this
isotopy the tailored pants and denote it also by $\widetilde{P}^{n-1}.$ The
regions $\log|u_{i}|\ll 0$ on $\widetilde{P}^{n-1}$ will be called the legs of
the tailored pants, and the projection of $\widetilde{P}^{n-1}$ under the
$\operatorname{Log}$ map will be denoted by $\widetilde{\mathcal{A}}$ and
called the tailored amoeba. Similarly, we denote by $\widetilde{X}_{m,n}$ the
space defined by the equation $\\{z_{0}\cdots
z_{m}=f_{1}(u_{1},\ldots,u_{n})\\}$ and call it the tailored local model.

######  Corollary 2.7.

The tailored local model $\widetilde{X}_{m,n}$ is isomorphic to the local
model $X_{m,n}.$

######  Remark 2.8.

The singularities of the SYZ fibration $\pi$ on $X_{m,n}$ coincide precisely
with the amoeba $\mathcal{A}\subset\mathcal{H},$ and the effect of the
tailoring isotopy is to make that amoeba a better approximation of the
tropical hypersurface $\Pi$. From the perspective of tropical geometry, it
would be desirable to have a more elaborate modification of the SYZ fibration
which makes the discriminant locus agree precisely with $\Pi.$ Such a
modification appears difficult, but some progress can be found in [28].

With the tailored local model $\widetilde{X}_{m,n}$ in hand, we are ready to
study the Liouville geometry of $\widetilde{X}_{m,n}$, equipped with a Stein
structure by the potential $\widetilde{\varphi}$ defined above in (2.4). The
Morse-Bott calculation will imitate that performed in [23, 13], relying
heavily on the inductive structure of the tailored pants
$\widetilde{P}^{n-1}.$

###### Proof of Theorem 1.2.

It will be useful to study the potential $\widetilde{\varphi}$ via the
singular torus fibration (2.2). As we have noted, we may restrict our
attention to the locus
$\mathcal{H}=\\{\eta=0\\}=\mathbb{R}^{n}\subset\mathbb{R}^{m+n}.$ (For the
remainder of this proof, we will always take the coordinates $\eta_{i}$ to be
equal to 0.) We will begin from the index-0 critical locus, which we denote by

$\mathbb{T}_{\emptyset}:=\\{\xi=(-\ell,\ldots,-\ell)\\},$

and attach stable manifolds for the critical points of progressively higher
index.

Fix some $i\in\\{1,\ldots,n\\}$ and consider the region in $\mathcal{H}$ where
$\xi_{i}=0$ and $\xi_{j}\ll 0$ for $j\neq i.$ In this region, the tailored
amoeba $\widetilde{\mathcal{A}}^{n}$ is a hyperplane, and the tailored pants
$\widetilde{P}^{n-1}$ is defined by the equation $\\{u_{i}+1=0\\}.$ It is
clear that in this region, the function $\widetilde{\varphi}$ has an index-1
Morse-Bott critical locus at the $(n-1)$-torus

$\mathbb{T}_{i}:=\\{u_{i}=-1,\log|u_{j}|=-\ell\mid j\neq i\\}.$

The stable set for this critical locus projects to $\mathcal{H}$ along the
interval $\\{0\geq\xi_{i}\geq-\ell,\xi_{j}=-\ell\mid j\neq i\\}$ (or possibly
a small perturbation of this interval, depending on how the bump function
$\chi$ used in defining $\widetilde{\varphi}$ is chosen), and it attaches to
$\mathbb{T}_{\emptyset}$ as the Legendrian whose front projection is the
codimension-1 subtorus obtained by fixing $\operatorname{Arg}(u_{i}).$

The index-$k$ critical manifolds, for $1<k\leq n,$ are computed similarly. We
fix some $I=\\{i_{1},\ldots,i_{k}\\}\subset[n]$ and consider the region where
$\xi_{i}=0$ for $i\in I$ and $\xi_{j}\ll 0$ for $j\notin I.$ In this region,
the tailored pants $\widetilde{P}^{n}$ looks like a product
$(\mathbb{C}^{\times})^{n-k}\times\widetilde{P}^{k-1},$ and the calculation of
[23, Theorem 5.13], repeated in more detail in the proof of [13, Theorem
5.3.4], shows that there is a single critical manifold in this region, lying
over the point in the boundary of the tailored amoeba
$\widetilde{\mathcal{A}}$ where $\xi_{i}=\xi_{j}$ for all $i,j\in I,$ and
$\xi_{j}=-\ell$ for all $j\notin I.$ This critical manifold $\mathbb{T}_{I}$
is a $(n-k)$-torus, obtained by fixing the values of $u_{i}$ for $i\in I$ and
$\log|u_{j}|$ for $j\notin I.$

Moreover, the attachments for these critical points are just as described in
[13, Theorem 5.3.4], giving the FLTZ skeleton of the pants, attaching to
$\mathbb{T}_{\emptyset}$ in the expected way. ∎

######  Example 2.9.

Let $n=2.$ Then the region $\mathcal{H}$ in the SYZ base is a plane, depicted
in Figure 1 together with the tailored amoeba $\widetilde{\mathcal{A}}$
(containing the tropical curve $\Pi$ for reference).

Figure 1. The plane $\mathcal{H},$ which lives inside the SYZ base of
$X_{m,2}.$ The Lagrangian skeleton is the union of the torus fiber over the
red point and a piece projecting to the blue shaded region. The higher-index
critical points are depicted in green.

Near the torus fiber over the red point, the skeleton looks like the product
of the FLTZ skeleton $\mathbb{L}_{\mathbb{C}^{2}}$ with an $m$-torus $T^{m}$
parametrized by $\operatorname{Arg}(z_{1}),\ldots,\operatorname{Arg}(z_{m}).$
This $T^{m}$ factor collapses to a point over points in the base where the
blue region meets the boundary of the amoeba.

##  3\. SYZ geometry and cluster theory

In this section, we connect the results of this paper to the non-toric blowup
construction of Gross-Hacking-Keel, and explain how our results fit into a
program to understand mirror symmetry for a general affine cluster variety.

In [17, 18], it was proposed that a cluster variety $X$ should be studied via
its relation to a toric model: a toric variety $\overline{X}$ containing a
codimension-2 subvariety $H$ inside its toric boundary divisor $D$ such that
$X$ embeds in the blowup $\operatorname{Bl}_{H}\overline{X}$ as the complement
of the proper transform $\widetilde{D}$ of the toric boundary divisor $D.$ The
requirement that the result $X$ of this construction is a cluster variety
imposes strong constraints on $H,$ which must be defined by a character of the
dense torus in its component of $D$.

In the case at hand, we relax this constraint, allowing $H$ to be defined by a
general linear polynomial. We also allow contributions from the places where
$H$ meets the singularities of the boundary divisor $D$. With these
modifications to the above construction, we can produce our spaces $X_{n,m}.$

Let $\overline{X}=\mathbb{C}^{n}\times(\mathbb{C}^{\times})^{m},$ with
coordinates $z_{1},\ldots,z_{n},u_{1},\ldots,u_{m}.$ Write $D:=\\{z_{1}\ldots
z_{n}=0\\}\subset\overline{X}$ for the toric boundary divisor, and consider
the non-toric subvariety $H=\\{z_{1}\ldots z_{n}=0,\sum u_{i}=-1\\}\subset D$.

######  Proposition 3.1.

Let $X=\operatorname{Bl}_{H}\overline{X}\setminus\widetilde{D}$ be the result
of blowing up $H$ and then deleting the proper transform of the boundary
divisor $D$. Then $X\cong X_{n,m}$.

###### Proof.

Let $f=z_{1}\cdots z_{n}$ and $g=1+u_{1}+\cdots+u_{m}.$ The center $H$ is
defined by the equations $f=g=0,$ so that blowing up $H$ involves introducing
$\frac{f}{g},\frac{g}{f}$ into the ring of functions of $\overline{X}.$
Deleting the proper transform of $D$ means it is sufficient to introduce the
function $\frac{g}{f}$ into the coordinate ring. If we denote this new
variable by $z_{0},$ then the coordinate ring of $X$ is
$\mathbb{C}[z_{1},\ldots,z_{n},u_{1}^{\pm},\ldots,u_{m}^{\pm}][z_{0}]/(z_{0}f=g)=\mathbb{C}[X_{n,m}].$
∎

The equation $z_{0}\cdot z_{1}\cdots z_{n}=1+u_{1}+\cdots u_{m}$ should be
understood as a generalization of the usual “cluster transformation equation”
$z_{0}z_{1}=1+u.$ Note that in this simpler case, the variable $z_{1}$ is
obtained from $z_{0}$ by a cluster mutation, whereas in the more general
situation considered in this paper, there are $n+1$ variables $z_{i}$,
corresponding to $n$ possible mutations.

On the symplectic side, this corresponds to the fact that the singular locus
$\mathcal{A}\subset\mathcal{H}$ divides $\mathcal{H}$ into $n$ chambers. In
the constructions of Section 2, we distinguished one of those chambers (the
“all-negative” orthant), but we could equally have begun with a torus fiber in
one of the other chambers instead. The difference between the torus fibers in
the various chambers is a generalization of the familiar “Clifford/Chekanov”
distinction in cluster symplectic geometry.

On the B-side, as we have seen, this new feature is due to the fact that the
center $H$ of the GHK blowup intersects the singular locus of the divisor $D.$
Keeping track of contributions from these intersections is a crucial step in
generalizing the results of [11], which disregarded those contributions.

The results of this paper therefore suggest a strategy for studying mirror
symmetry for an affine cluster variety $X$ via its SYZ fibration. The SYZ base
should have a presentation by gluing together local pieces modeled by the
singularities $\mathfrak{s}_{n,m}$ (or products of these). Each singularity
has a monodromy-invariant space $\mathcal{H},$ and if there is a point in the
intersection of all of these spaces, it should play the rôle of the torus
$\mathbb{T}_{\emptyset}$ in the skeleton $\mathbb{L}$ of $X,$ with the
remainder of the skeleton obtained by attaching and collapsing subtori in a
manner prescribed by the geometry of the base, locally agreeing wih the
construction in this paper (as illustrated in Figure 1). This presentation
should match a presentation of the mirror space $X^{\vee}$ in terms of the
non-toric blowup construction of Proposition 3.1.

Acknowledgements. This work is the direct outgrowth of a continuing project
with Ian Le on cluster varieties, and my understanding of the generalized non-
toric blowup construction of Proposition 3.1 is due to conversations with him.
My interest in the spaces $X_{n,m}$ comes from conversations with Vivek Shende
about the rôle of these spaces in compactifying the large-volume manifolds
described in [12] (to be explained in forthcoming work), and I also thank
Denis Auroux for advice and encouragement on the program sketched in the
preceding paragraphs. I am supported by an NSF Postdoctoral Research
Fellowship, DMS-2001897.

## References

  * [1] Mohammed Abouzaid.  Homogeneous coordinate rings and mirror symmetry for toric varieties.  Geom. Topol., 10:1097–1156, 2006.
  * [2] Mohammed Abouzaid, Denis Auroux, and Ludmil Katzarkov.  Lagrangian fibrations on blowups of toric varieties and mirror symmetry for hypersurfaces.  Publ. math. IHÉS, 123:199–282, 2016.
  * [3] Mohammed Abouzaid and Zack Sylvan.  Homological mirror symmetry for local SYZ singularities.  In preparation.
  * [4] Denis Auroux.  Mirror symmetry and T-duality in the complement of an anticanonical divisor.  J. Gökova Geom. Topol., 1:51–91, 2007.
  * [5] Alexei Bondal.  Derived categories of toric varieties.  In Convex and Algebraic Geometry, Oberwolfach Conference Reports, volume 3, pages 284–286. 2006.
  * [6] Kwokwai Chan, Daniel Pomerleano, and Kazushi Ueda.  Lagrangian torus fibrations and homological mirror symmetry for the conifold.  Commun. Math. Phys., 341:135–178, 2016.
  * [7] Bohan Fang, Chiu-Chu Melissa Liu, David Treumann, and Eric Zaslow.  A categorification of Morelli’s theorem.  Inventiones mathematicae, 186(1):79–114, Oct 2011.
  * [8] Bohan Fang, Chiu-Chu Melissa Liu, David Treumann, and Eric Zaslow.  T-duality and homological mirror symmetry for toric varieties.  Advances in Mathematics, 229(3):1873 – 1911, 2012.
  * [9] Bohan Fang, Chiu-Chu Melissa Liu, David Treumann, and Eric Zaslow.  The Coherent-Constructible Correspondence for Toric Deligne-Mumford Stacks.  International Mathematics Research Notices, 2014(4):914–954, 11 2012.
  * [10] Benjamin Gammage.  Mirror symmetry for Berglund-Hübsch Milnor fibers.  arXiv preprint 2010.15570.
  * [11] Benjamin Gammage and Ian Le.  Mirror symmetry for truncated cluster varieties.  arXiv preprint 2103.12232.
  * [12] Benjamin Gammage and Vivek Shende.  Homological mirror symmetry at large volume.  arXiv preprint 2104.11129.
  * [13] Benjamin Gammage and Vivek Shende.  Mirror symmetry for very affine hypersurfaces.  arXiv preprint 1707.02959.
  * [14] Sheel Ganatra, John Pardon, and Vivek Shende.  Microlocal Morse theory of wrapped Fukaya categories.  arXiv preprint 1809.08807.
  * [15] Sheel Ganatra, John Pardon, and Vivek Shende.  Sectorial descent for wrapped Fukaya categories.  arXiv preprint 1809.03472.
  * [16] Sheel Ganatra, John Pardon, and Vivek Shende.  Covariantly functorial wrapped Floer theory on Liouville sectors.  Publ. Math. IHÉS, 2019.
  * [17] Mark Gross, Paul Hacking, and Sean Keel.  Mirror symmetry for log Calabi-Yau surfaces I.  Publ. Math. IHÉS, 122:65–168, 06 2011.
  * [18] Mark Gross, Paul Hacking, and Sean Keel.  Birational geometry of cluster algebras.  Algebraic Geometry, 2:137–175, 2013.
  * [19] Tatsuki Kuwagaki.  The nonequivariant coherent-constructible correspondence for toric stacks.  Duke Math. J., 169(11):2125–2197, 08 2020.
  * [20] Yankı Lekili and Alexander Polishchuk.  Homological mirror symmetry for higher-dimensional pairs of pants.  Compositio Mathematica, 156(7):1310–1347, 2020.
  * [21] Grigory Mikhalkin.  Decomposition into pairs-of-pants for complex algebraic hypersurfaces.  Topology, 43(5):1035–1065, 2004.
  * [22] David Nadler.  Wall-crossing for toric mutations.  arXiv preprint 1806.01381.
  * [23] David Nadler.  Wrapped microlocal sheaves on pairs of pants.  arXiv preprint 1604.00114.
  * [24] David Nadler.  Mirror symmetry for the Landau-Ginzburg ${A}$ -model ${M}=\mathbb{C}^{n}$ , ${W}=z_{1}\cdots z_{n}$.  Duke Math. J., 168(1):1–84, 01 2019.
  * [25] David Nadler and Vivek Shende.  Sheaf quantization in Weinstein symplectic manifolds.  arXiv preprint 2007.10154.
  * [26] James Pascaleff and Dmitry Tonkonog.  The wall-crossing formula and Lagrangian mutations.  Adv. Math., 361:106850, 67, 2020.
  * [27] Daniel Pomerleano.  Intrinsic mirror symmetry and categorical crepant resolutions.  arXiv preprint 2103.01200.
  * [28] Helge Ruddat and Ilia Zharkov.  Tailoring a pair of pants.  arXiv preprint 2001.08267.
  * [29] Vivek Shende.  Toric mirror symmetry revisited.  arXiv preprint 2103.05386.
  * [30] Vivek Shende, David Treumann, and Harold Williams.  On the combinatorics of exact Lagrangian surfaces.  arXiv preprint 1603.07449.
  * [31] Peng Zhou.  Twisted polytope sheaves and coherent-constructible correspondence for toric varieties.  Sel. Math. New Ser., 25(1), 2019.
  * [32] Peng Zhou.  Lagrangian skeleta of hypersurfaces in $(\mathbb{C}^{\times})^{n}$.  Sel. Math. New Ser., 26(26), 2020.