# Zero-shot Conversational Summarization Evaluations with small Large Language
Models

Ramesh Manuvinakurike
Intel labs, USA

&Saurav Sahay
Intel labs, USA

Sangeeta Manepalli
Intel, USA

&Lama Nachman
Intel labs, USA

###### Abstract

Large Language Models (LLMs) exhibit powerful summarization abilities.
However, their capabilities on conversational summarization remains under
explored. In this work we evaluate LLMs ($\sim$10 billion parameters) on
conversational summarization and showcase their performance on various
prompts. We show that the summaries generated by models depend on the
instructions and the performance of LLMs vary with different instructions
sometimes resulting steep drop in ROUGE scores if prompts are not selected
carefully. We also evaluate the models with human evaluations and discuss the
limitations of the models on conversational summarization.

##  1 Introduction

Large Language Models (LLMs) have been shown to exhibit impressive
multitasking abilities including summarization [28]. These LLMs show great
promise for automatic summarization and achieve impressive zero-shot
performance [56, 48]. LLMs are ‘prompted’ to solve a task such as
summarization by issuing an instruction (e.g., Generate a summary for this
dialogue, Summarize: etc.) and an input (conversation, news article2, queries
etc.). These instructions are rather simple natural language phrases appended
as a prefix or postfix to the input to assist the LLMs in carrying out the
task. Generating such instructions and prompting can be challenging for
novices [53]. The brittleness of the LLMs in processing the prompts
consistently is one such reason that causes a challenge [57, 51, 33, 26]. A
minor variation in the prompt syntax can result in vastly different results.
Prompt engineering has thus evolved to design approaches for the LLMs to
produce the desired results consistently. Several resources exist for prompt
engineering. Promptsource is one such popular repository consisting of 2000+
prompts for natural language prompts for various natural language tasks
including summarization. [4]. In spite of these advances, the brittleness
exist and more so in smaller open-sourced LLMs. One possible solution to
tackle the brittleness could be to further finetune the models using the
instructions for a task coupled with data points from a dataset at the
developer’s disposal. This however could result in loss of generalization
abilities of the LLMs even within a task (for instance, finetuning on
conversational summarization from a technical design meeting dataset could
result in drop in summarization capabilities on chit-chat data). In this work,
we finetune the LLMs on a technical council meetings dataset and evaluate the
performance on a chit-chat dataset and discuss the results.

This paper arises from a need for evaluating open-sourced LLMs [26] (within
$\sim$ 11 billion parameters) for conversation summarization and their
robustness to different prompts (The rationale for selecting models within
$\sim$11b parameters is discussed in detail in Sec 4.1). These specific sized
LLMs provide the capability run at the edge on PCs or mobile systems
preserving the privacy of the user data while benefiting the user with
productivity gains. These models need to be benchmarked against the existing
conversational summarization datasets by measuring their abilities on
different prompts. We motivate this work with the following research
questions:
1) How important is prompt selection for conversational summarization task?
How do LLMs less than $\sim$11 billion parameters fare on different prompts
varying slightly in syntactic structure? How do these models fare in human
evaluation?
2) Can finetuning the LLMs for conversational summarization a task but on a
different domain improve zero shot summarization capabilities?
We also discuss some limitations of the models specially focusing on
hallucinations and role attributions in the summaries.

##  2 Related work

Recent work on benchmarking the LLM abilities for news articles summarization
[56] is the most related our work. The authors highlight there exists a
fundamental limitation with the existing news articles summarization datasets
and found that the target/gold-truth summaries were sub par for comparative
evaluations. To overcome the problem the authors hired freelance writers to
generate target summariesand pitch the summaries generated by the models are
pitched against those written by expert freelancers. The authors found that
the summaries generated by the models were on-par with the summaries generated
by the experts [56] which in turn is better than the target summaries. It is
important to note that the LLMs used in this work range in parameter count
from 350M to 175 billion [7, 16, 36, 54, 5]. In this work, we’re focused on
benchmarking the LLMs on the task of conversational summarization.

It has been well established that training the models on instructions improves
the generalization abilities in the LLMs (see for e.g., [52, 34, 39, 7, 36,
21, 59]. Several resources such as Promptsource[4], Natural Instructions [34],
Flan [52] and, Super Natural Instructions [50] have been developed in recent
times to provide researchers and engineers alike with resources to study, find
and leverage instructions for a task of interest. In this work, we choose the
prompts from Promptsource 111 we study Promptsource in this work due it’s high
activity and star ratings (compared to similar resources). .

##  3 Data

Several promising datasets exist for the task of conversational summarization
[35, 58, 8, 25, 11, 23, 20]. In this work we utilize the MeetingBank dataset
[23] for instruction tuning purposes. The MeetingBank dataset is relatively
new and serves as a great resource for evaluating the finetuning impacts on
the models on a specialized domain. The dataset contains transcriptions from
various United States cities or municipality meetings. We then evaluate the
models in a zero-shot manner on Samsum corpus [20] and Dialogsum datasets
[10]. We utilize the validation splits from Huggingface datasets repository
for our study purposes.

For the purpose of finetuning the model we split the Meetingbank dataset into
95% training and 5% validation split and utilize the training set for
instruction tuning. For the purposes of instruction tuning we utilize
Promptsource[4] which is a crowdsourced valuable resource consisting of
thousands of prompts contributed for numerous NLP tasks and datasets. We
utilize the prompts for conversational summarization section (Table 4). We
further instruct-tune the models using a pipeline similar to T0 [39]. For
training & inferencing each transcription input is converted to a prompt for
LMMs by ‘apply’ing the template with the conversations using Langchain [9].

##  4 Models

Conversational summarization has increasingly gained interest in a post-covid
world with the nature of workplace becoming more hybrid [24]. This has
amplified the need for a conversational/meeting summarization systems to run
on machines with limited compute capabilities with democratization
aspirations.

###  4.1 Choice for parameter counts

Our choice of models with $\sim$11 billion parameters is mainly motivated by
the constraint imposed by the cost and, hardware limitations and a motivation
to study less-carbon emitting approach of model development. These model sizes
are also conducive to running on PCs and mobile systems, however there is an
added impact of bigger models and more data needed for inferencing which is
observed in the results noted below in the Hardware Inference section using an
LLM as an example workload. Hardware Training: Fine-tuning a 7 billion
parameter model takes approximately 66 GB of memory (RAM) at 32 bit precision
and a batch size of 1 (sequence length of 2048) (see memory computation in
[29]) which is slightly less than a high end GPU available in the market.
While several optimization approaches exist which significantly reduce the
compute requirements (e.g., Quantization [18]), these are accompanied by often
deteriorated performance or comparable in the best case. Running an inference
locally on client devices (without use of cloud APIs/services) even with
quantization of models is memory intensive
222https://github.com/ggerganov/llama.cpp. While bigger is often better in
LLMs, it is important to study the trade-offs in models whose parameter counts
are still tractable and can be deployed for inferencing (and even train) using
reasonable compute budgets. Hardware Inference: Running inference instances is
also an important consideration. For instance, we consider a GPT
variant333https://github.com/imartinez/privateGPT on a state-of-the-art PC
(Intel Raptor Lake 28W Core i7 system (1380P) configured with 32GB of memory
and 512 GB of storage). For running an inferencing pipeline that includes
document ingestion, encoding, followed by autoregressive decoding with a 7B
parameter model ( [47]) generated a bandwidth of 10 GB/s. First inference with
model loading was significantly slower $\sim$0.5 FPS. About 1/3rd of memory
was consumed by text encoding and LLM operation and reduced the headroom for
other applications. Optimizations to use compressed models with reducing
memory interactions is the key to use these models effectively on PCs and
mobile systems. Models with any greater parameter count would pose additional
inferencing challenges. Carbon emissions: Training a 70B emits 833% more
carbon and 13B parameter model emits 100% more carbon than the 7B parameter
model. While, the developing organization offset the carbon, it might not be
feasible for all[45]. With these experiments & observations we arrived at our
model evaluations to those mentioned below. In the future we plan to extend
the evaluations to models of greater parameter count.

###  4.2 Models selected

Llama  is a foundational language model developed with publicly available
datasets by Gen AI, Meta. Llama 2 [45] is a more recently released open source
class of foundational large language models pretrained & finetuned with more
data and higher context lengths than it’s predecessor Llama 1[44]. Llama 2
models achieve impressive performance on numerous public benchmarks. We choose
Llama 2 as one of the models for our benchmarking purposes. The family also
includes Llama-2-chat model which is developed using supervised finetuning and
then iteratively refined using Reinforcement Learning with Human Feedback
(RLHF) [36]. Falcon [43] is a family of generative LLM by Technology
Innovation Institute which achieves impressive performances on many of the LLM
benchmarks. The models are trained predominantly on RefinedWeb [37] along with
other data from the web. The instruct version of the models are further
finetuned on instructions and conversational data. Alpaca [41] is a
instruction-tuned model based on Llama [44] which is instruction tuned using
the techniques from self-instruct [49] paradigm. The alpaca model was found to
exhibit behavior similar to text-davinci-003 model [1]. Flan-T5 are a class of
language models [12] where encoder-decoder transformer-based model [38] are
finetuned on 1836 tasks using instruction-finetuning and chain-of-thought
finetuning paradigms. The models exhibit state-of-the-art abilities in various
benchmark tasks. We also benchmark the results using GPT3.5 turbo [2] which is
a an improved GPT-3 model with instruction following ability on Natural
language and code. While, the parameter count of the model is in hundreds of
billion, the purpose of including the model is for comparison.

##  5 Experiments

Our goal is compare the model performance on conversational summarization
(Samsum & Dialogsum) and then evaluate the model performance on different
prompts. There are 6 prompts in Promptsource for conversational summarization
(Table 4) that we then apply using Langchain on the each conversation as input
to the models. We then extract the output from these models as summaries. We
additionally finetune existing instruction-tuned models- (Flan &
Lama2-7b-chat) using task specific instructions and the data from Meetingbank
dataset (Models marked as **). While instruction tuning has been shown to
improve the overall performance in the model generalization abilities [34], we
intend to explore if the task performance (conversational summarization)
utilizing the data from a related but different dataset can further provide a
boost.

We report Rouge scores (R1, R2, RL) [32] and BertScore [55] on the summaries
generated by the models comparing against the available ground truth
summaries. We additionally report Length Ratio (LR), Novel uni/bi (N1, N2)
gram metrics which can be evaluated automatically on the Dialogsum and the
Samsum datasets which the models haven’t seen during our training process
444T0pp model however have been exposed to Samsum dataset off-the-shelf. We
cannot however guarantee that the models have not been exposed to these
datasets due to limited information available. . We compute Length Ratio =
length (tokens in summaries generated)/length (tokens in the conversations),
N-gram novelty = length (N-gram tokens in summaries generated $\cap$ tokens in
conversation)/ length(tokens in the conversations).

Target summaries don’t always serve as a reliable ground truth for evaluation
[56]. Summarization task is subjective and also information can be presented
in several different forms (sentences & format). However, the summaries in the
dataset themselves can be relied upon as one of the many possible summaries
for a given conversation. We thus experiment with humans to compare the model
generated summary with the target and report the findings here. We developed a
web-interface (Figure 5) for collecting human preferences between target and
model generated summary. The conversation is displayed to the users along with
two summaries, one model generated and the other reference/target summaries.
The summary orders are jumbled and the raters are not aware of the source of
summaries. The raters were volunteers and employees of anonymous and had
education levels of graduate degree and were aware of the task. Each user was
requested to rate as many summaries as they could. We obtain comparative
ratings for Overall, Novelty, Informativeness and Conciseness of the
summaries. To further understand if the summaries contains hallucinations,
correct role attribution and if the summaries had misrepresented gender
attributes we developed a similar interface, but this time requesting the
human evaluators to rate only the generated summaries if they consist
hallucinations, if the roles are properly attributed in the summaries and if
the genders are properly attributed in the summary (if applicable).

##  6 Results

Figure 1:  Shows the evaluation of the LLMs on various metrics for
conversational summarization with any instruction from Promptsource vs. oracle
selected best instruction.

Do Instruction tuned models perform generate better summaries? We can observe
from Table 1 that when comparing the instruction tuned models (Alpaca-7b vs
Llama-7b, Falcon-7b-instruct vs Falcon-7b) with just pre-trained model, the
instruction tuned models generate summaries with better Rouge-scores,
BertScores, more concise and generate fewer novel 1-gram and 2-gram (due to
fewer hallucinations). We also find that the summaries generated by the
instruction tuned models are significantly better w.r.t Rouge scores and BERT
scores (p ¡ 0.001, Wilcoxon rank-sum test) than the summaries generated by the
non-instruction tuned models. To arrive at this conclusion we compared sample-
wise Rouge & BERT scores in separate experiments between the non-instruction
tuned models and their instruction tuned counterparts. This implies that
instruction tuning helps improve the conversational summarization performance
which is consistent with the literature (on a different task) [34]. Humans
also rated the summaries from instruction tuned model higher than pre-trained
models (Figure 1 ).

Does further task-specific instruction tuning help models perform better? We
find that further

Figure 2: Shows the human evaluations on various metrics comparing instruction
tuned model * and task-specific finetuned model ** demonstrating improvements.

tuning the models for a task (summarization) even on a different dataset
(Meetingbank) slightly improves the performance of the models. In Table 1 we
identify task-specific instruction tuned model with ‘**’ vs available off-the-
shelf instruction tuned checkpoints ‘*’ (Flan-T5-{MODEL_SIZE}* vs
Flan-T5-{MODEL_SIZE}** , Llama-7b-chat* vs Llama-7b-chat**). We do not perform
any experiments to verify if the model’s performance on a more general
abilities since our goal is to leverage LLMs for summarization task alone.
This slight change in the summary quality was also resulted in increase in
preferences over target in human-evaluation overall and even on their factual
and conciseness (Flan-T5-base* vs. Flan-t5-base**, Flan-T5-small* vs.
Flan-T5-small** in Figure 2 ). This is important, since we’re not pitching the
models one against the other, but rather against the target summaries.

Do summary qualities differ across instructions and models? We also find that
the model’s summarizing abilities are highly dependent on the instruction used
and the model itself. For instance, ‘Given the above dialogue write a summary’
as an instruction gives 8% better Rouge-L scores than ‘Generate a summary for
this dialogue’ in Falcon-7b instruct tuned model compared to ‘Llama-7b’ which
gives the best Rouge scores from the prompt ‘Given the above dialogue write a
summary’. We also tested this variable performance using ANOVA test (single
factor, p ¡ 0.0001 (F=34.56, df=6, MS=0.029) and find that the difference in
Rouge scores are significantly different across prompts. Figure 3 shows R-L
box-plots for each prompt on SAMSUM corpus. We further find that the
variability in instruction tuned models is slightly lower compared to non-
instruction tuned models. This result highlights the need for future work to
reduce the gap between the model performance across prompts which could make
it easier for non-experts to query the LLMs. We also find that this
variability reduces with increase in model parameters.

Figure 3: Box plot of Rouge scores of each sample from Samsum dataset showing
variability for each prompt (Table 4). Each color represents different prompt.

If we were to use the best prompt, how do LLMs compare with target summaries?
We selected the prompt yielding the highest Rouge-L scores (oracle selection)
and then compare the human ratings for the best performing prompt for each of
the model. Upon selecting the best prompt we find that all the LLM generated
summaries are rated more novel than the target summaries (Figure 1 under ‘With
best instruction’). All the instruction tuned models (Alpaca, Llama-chat,
Falcon-instruct) were rated more informative and were preferred overall
compared to the target summaries. However, the target summaries are rated most
factually consistent and concise compared to the generated summaries. Lower
rating for the conciseness were more obvious when we compare the LR of the
generated summaries vs the target summaries (Dailogsum target summaries LR =
14.85%, Samsum LR = 17.94%) compared to the summaries length of the model
generated summaries. Lower factual ratings can be explained by presence of
hallucinations and other errors. Table 3 shows best-possible Rouge and BERT
scores on the oracle selected best prompts used once per dataset.

Model Samsum Dialogsum R-1 R-2 R-L B-Score LR N1 N2 R-1 R-2 R-L B-Score LR N1
N2 Llama-7b 0.14 0.02 0.10 0.701 56.58 47.06 85.70 0.16 0.02 0.11 0.736 40.24
31.22 61.87 Falcon-7b 0.14 0.02 0.10 0.703 58.80 48.74 89.68 0.16 0.02 0.11
0.737 36.32 26.61 54.37 Alpaca* 0.18 0.04 0.13 0.721 35.19 27.82 52.80 0.17
0.03 0.13 0.740 21.78 15.06 32.29 Falcon-7b-inst* 0.21 0.05 0.15 0.739 33.96
27.82 52.63 0.22 0.05 0.15 0.761 24.99 18.10 38.80 Flan-T5-small* 0.42 0.19
0.33 0.844 24.38 8.71 27.25 0.22 0.07 0.17 0.742 17.11 5.54 15.62
Flan-T5-small** 0.43 0.20 0.33 0.845 24.45 8.70 27.33 0.23 0.07 0.18 0.741
17.16 5.63 15.86 Flan-T5-base* 0.46 0.23 0.36 0.856 24.29 9.14 28.01 0.31 0.11
0.24 0.785 18.82 4.80 15.93 Flan-T5-base** 0.47 0.23 0.37 0.857 24.23 9.09
27.92 0.32 0.12 0.25 0.787 18.58 4.82 15.97 Flan-T5-large* 0.44 0.19 0.35
0.849 18.38 10.24 25.25 0.29 0.09 0.23 0.793 13.23 7.59 18.75 Flan-T5-large**
0.46 0.20 0.36 0.851 18.38 10.24 24.22 0.30 0.10 0.24 0.793 13.24 7.52 18.72
Flan-T5-xl* 0.48 0.26 0.39 0.862 24.37 9.87 28.21 0.37 0.16 0.29 0.824 18.10
5.71 18.13 Flan-T5-xl** 0.49 0.26 0.40 0.863 24.41 9.92 28.27 0.38 0.17 0.31
0.827 18.17 5.71 18.13 Llama-7b-chat* 0.18 0.04 0.13 0.721 32.41 25.65 48.58
0.21 0.05 0.15 0.765 31.46 22.54 47.39 Llama-7b-chat**± 0.18 0.05 0.14 0.721
31.66 25.03 47.45 0.21 0.06 0.15 0.760 30.54 22.17 46.17 GPT-3.5 turbo 0.14
0.06 0.10 0.746 189.27 80.86 195.89 0.14 0.05 0.11 0.741 140.31 62.33 150.97

Table 1: Evaluation of models on the summarization task. * indicates the
models are instruction tuned, ** means the models were task instructed tuned
for summarization task. Llama-7b-chat was finetuned using LORA[22].

##  7 Discussions & Future work

Do low human ratings for factual ratings correlated to hallucinations and role
attributions? Hallucinations a challenge to be addressed in LLMs. We collected
human ratings to further analyse the cause for lower rating for the factual
ratings in LLMs. We requested human raters to mark (Yes/Now) if the summary
contained irrelevant phrases not related to the input. We sampled 286
summaries across models randomly from the dataset for this small scale study.
We also requested human raters to answer yes/no question if the the summaries
had incorrect role attributions and if there was assign/misrepresented gender
pronouns. We find that the presence of hallucinations is strongly negatively
correlated to the ratings of factual and overall ratings (PCC, $\rho$= -0.77,
$\rho$= -0.71 resp.). The ratings are also weakly/moderately negatively
correlated to incorrect speaker attributions ($\rho$= -0.31). The raters were
more forgiving to incorrect gender attributions (he instead of she) towards
overall summary rating ($\rho$= -0.18). This means that hallucinations and
incorrect role attributions could’ve played a more important role in lower
factual and overall ratings. Since, our sample size was low we cannot conclude
with conviction. This remains an interesting area of exploration.

Are the models with higher overlap with target summaries or input
conversations rated more informative? Rouge (p) between the input and summary
generated measures what fraction of the conversation was covered in the
summary. We measured the Pearson’s correlation co-efficient (PCC) between
these Rouge (p) scores (Table 5) and the human preference ratings to measure
if any correlation exists. We find moderate correlation (PCC, $\rho$ = 0.46)
for the informativeness between the models Rouge scores and the preference
ratings. This implies that the raters tended to mark models with higher input
coverage as more informative. Additionally, we also found that high rouge (p)
scores correlated moderately with Overall and Factual ratings. This was also
true for informativeness. This is however not all that surprising but a
reinforcing indicator that summaries need to be concise while increasing the
overall coverage.

Higher novelty ratings (‘Select the summary which you think is a more novel
way to present the conversation’) was an interesting observation. The LLMs
consistently performed better on novelty preferences compared to the target.
We believe that novel ways of presenting the summaries (e.g., as question
answering exchanges, shorter rephrased conversation versions, alternative
narrations) along with novel phraseology could be contributing towards higher
novelty ratings. We additionally note that the human raters being experts
(have good knowledge of technology and recent advancements) rather than
novices could’ve contributed to this. We intend to explore this in our future
work.

Conversational summarization is an important application area of the LLMs and
remains an interesting area of research. In this work we evaluated various
LLMs on conversational summarization datasets and showed that the instruction
tuning yields better results. Given the parameter sizes of the LLM models
evaluated, this outcome has interesting applications to deployment of ¡11B
parameter LLMs on PC and mobile systems. We also showed that further task-
specific finetuning could yield more promising results. We further analysed
the summaries via human and automatic evaluations and discussed the
limitations including hallucinations and incorrect role attributions.

## References

  * AI [2023a] Open AI.  Openai chatgpt, 2023a.  URL https://openai.com/blog/chatgpt.
  * AI [2023b] Open AI.  Openai gpt-3.5 turbo, 2023b.  URL https://openai.com/blog/gpt-3-5-turbo-fine-tuning-and-api-updates.
  * Andonian et al. [2023] Alex Andonian, Quentin Anthony, Stella Biderman, Sid Black, Preetham Gali, Leo Gao, Eric Hallahan, Josh Levy-Kramer, Connor Leahy, Lucas Nestler, Kip Parker, Michael Pieler, Jason Phang, Shivanshu Purohit, Hailey Schoelkopf, Dashiell Stander, Tri Songz, Curt Tigges, Benjamin Thérien, Phil Wang, and Samuel Weinbach.  GPT-NeoX: Large Scale Autoregressive Language Modeling in PyTorch, 9 2023.  URL https://www.github.com/eleutherai/gpt-neox.
  * Bach et al. [2022] Stephen H Bach, Victor Sanh, Zheng-Xin Yong, Albert Webson, Colin Raffel, Nihal V Nayak, Abheesht Sharma, Taewoon Kim, M Saiful Bari, Thibault Fevry, et al.  Promptsource: An integrated development environment and repository for natural language prompts.  _arXiv preprint arXiv:2202.01279_ , 2022.
  * Bai et al. [2022] Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al.  Training a helpful and harmless assistant with reinforcement learning from human feedback.  _arXiv preprint arXiv:2204.05862_ , 2022.
  * Biderman et al. [2023] Stella Biderman, Hailey Schoelkopf, Quentin Anthony, Herbie Bradley, Kyle O’Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, Aviya Skowron, Lintang Sutawika, and Oskar van der Wal.  Pythia: A suite for analyzing large language models across training and scaling, 2023.
  * Brown et al. [2020] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Carletta et al. [2005] Jean Carletta, Simone Ashby, Sebastien Bourban, Mike Flynn, Mael Guillemot, Thomas Hain, Jaroslav Kadlec, Vasilis Karaiskos, Wessel Kraaij, Melissa Kronenthal, et al.  The ami meeting corpus: A pre-announcement.  In _International workshop on machine learning for multimodal interaction_ , pages 28–39. Springer, 2005.
  * [9] Harrison Chase.  Langchain, 10 2022.  _URL https://github. com/hwchase17/langchain_.
  * Chen et al. [2021a] Yulong Chen, Yang Liu, Liang Chen, and Yue Zhang.  DialogSum: A real-life scenario dialogue summarization dataset.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 5062–5074, Online, August 2021a. Association for Computational Linguistics.  doi: 10.18653/v1/2021.findings-acl.449.  URL https://aclanthology.org/2021.findings-acl.449.
  * Chen et al. [2021b] Yulong Chen, Yang Liu, Liang Chen, and Yue Zhang.  DialogSum: A real-life scenario dialogue summarization dataset.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 5062–5074, Online, August 2021b. Association for Computational Linguistics.  doi: 10.18653/v1/2021.findings-acl.449.  URL https://aclanthology.org/2021.findings-acl.449.
  * Chung et al. [2022] Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, et al.  Scaling instruction-finetuned language models.  _arXiv preprint arXiv:2210.11416_ , 2022.
  * Computer [2023] Together Computer.  Redpajama: An open source recipe to reproduce llama training dataset, 2023\.  URL https://github.com/togethercomputer/RedPajama-Data.
  * Conover et al. [2023] Mike Conover, Matt Hayes, Ankit Mathur, Jianwei Xie, Jun Wan, Sam Shah, Ali Ghodsi, Patrick Wendell, Matei Zaharia, and Reynold Xin.  Free dolly: Introducing the world’s first truly open instruction-tuned llm, 2023.  URL https://www.databricks.com/blog/2023/04/12/dolly-first-open-commercially-viable-instruction-tuned-llm.
  * Databricks [2023] Databricks.  Dolly-hhrlhf dataset.  https://huggingface.co/datasets/mosaicml/dolly_hhrlhf, 2023.
  * Du et al. [2021] Zhengxiao Du, Yujie Qian, Xiao Liu, Ming Ding, Jiezhong Qiu, Zhilin Yang, and Jie Tang.  Glm: General language model pretraining with autoregressive blank infilling.  _arXiv preprint arXiv:2103.10360_ , 2021.
  * Fabbri et al. [2021] Alexander R Fabbri, Wojciech Kryściński, Bryan McCann, Caiming Xiong, Richard Socher, and Dragomir Radev.  Summeval: Re-evaluating summarization evaluation.  _Transactions of the Association for Computational Linguistics_ , 9:391–409, 2021.
  * Frantar et al. [2022] Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh.  Gptq: Accurate post-training quantization for generative pre-trained transformers.  _arXiv preprint arXiv:2210.17323_ , 2022.
  * Gao et al. [2020] Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, et al.  The pile: An 800gb dataset of diverse text for language modeling.  _arXiv preprint arXiv:2101.00027_ , 2020.
  * Gliwa et al. [2019] Bogdan Gliwa, Iwona Mochol, Maciej Biesek, and Aleksander Wawer.  Samsum corpus: A human-annotated dialogue dataset for abstractive summarization.  _arXiv preprint arXiv:1911.12237_ , 2019.
  * Hase and Bansal [2022] Peter Hase and Mohit Bansal.  When can models learn from explanations? a formal framework for understanding the roles of explanation data.  In _ACL Workshop on Learning with Natural Language Supervision_ , 2022\.
  * Hu et al. [2021] Edward J Hu, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, Weizhu Chen, et al.  Lora: Low-rank adaptation of large language models.  In _International Conference on Learning Representations_ , 2021.
  * Hu et al. [2023] Yebowen Hu, Tim Ganter, Hanieh Deilamsalehy, Franck Dernoncourt, Hassan Foroosh, and Fei Liu.  Meetingbank: A benchmark dataset for meeting summarization.  _arXiv preprint arXiv:2305.17529_ , 2023.
  * Institute [2023] McKinsey Global Institute.  How hybrid work has changed the way people work, live, and shop, 2023\.  URL https://www.mckinsey.com/mgi/our-research/empty-spaces-and-hybrid-places-chapter-1.  Accessed: 2023-09-30.
  * Janin et al. [2003] Adam Janin, Don Baron, Jane Edwards, Dan Ellis, David Gelbart, Nelson Morgan, Barbara Peskin, Thilo Pfau, Elizabeth Shriberg, Andreas Stolcke, et al.  The icsi meeting corpus.  In _2003 IEEE International Conference on Acoustics, Speech, and Signal Processing, 2003. Proceedings.(ICASSP’03)._ , volume 1, pages I–I. IEEE, 2003.
  * Kaddour et al. [2023] Jean Kaddour, Joshua Harris, Maximilian Mozes, Herbie Bradley, Roberta Raileanu, and Robert McHardy.  Challenges and applications of large language models.  _arXiv preprint arXiv:2307.10169_ , 2023.
  * Khashabi et al. [2021] Daniel Khashabi, Gabriel Stanovsky, Jonathan Bragg, Nicholas Lourie, Jungo Kasai, Yejin Choi, Noah A Smith, and Daniel S Weld.  Genie: Toward reproducible and standardized human evaluation for text generation.  _arXiv preprint arXiv:2101.06561_ , 2021.
  * Kojima et al. [2022] Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa.  Large language models are zero-shot reasoners.  _Advances in neural information processing systems_ , 35:22199–22213, 2022.
  * Korthikanti et al. [2023] Vijay Anand Korthikanti, Jared Casper, Sangkug Lym, Lawrence McAfee, Michael Andersch, Mohammad Shoeybi, and Bryan Catanzaro.  Reducing activation recomputation in large transformer models.  _Proceedings of Machine Learning and Systems_ , 5, 2023.
  * Kryściński et al. [2019] Wojciech Kryściński, Bryan McCann, Caiming Xiong, and Richard Socher.  Evaluating the factual consistency of abstractive text summarization.  _arXiv preprint arXiv:1910.12840_ , 2019.
  * Liang et al. [2022] Percy Liang, Rishi Bommasani, Tony Lee, Dimitris Tsipras, Dilara Soylu, Michihiro Yasunaga, Yian Zhang, Deepak Narayanan, Yuhuai Wu, Ananya Kumar, et al.  Holistic evaluation of language models.  _arXiv preprint arXiv:2211.09110_ , 2022.
  * Lin [2004] Chin-Yew Lin.  Rouge: A package for automatic evaluation of summaries.  In _Text summarization branches out_ , pages 74–81, 2004.
  * Lu et al. [2022] Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp.  Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 8086–8098, 2022\.
  * Mishra et al. [2022] Swaroop Mishra, Daniel Khashabi, Chitta Baral, and Hannaneh Hajishirzi.  Cross-task generalization via natural language crowdsourcing instructions.  In _60th Annual Meeting of the Association for Computational Linguistics, ACL 2022_ , pages 3470–3487. Association for Computational Linguistics (ACL), 2022.
  * Nedoluzhko et al. [2022] Anna Nedoluzhko, Muskaan Singh, Marie Hledíková, Tirthankar Ghosal, and Ondřej Bojar.  ELITR Minuting Corpus: A novel dataset for automatic minuting from multi-party meetings in English and Czech.  In _Proceedings of the 13th International Conference on Language Resources and Evaluation (LREC-2022)_ , Marseille, France, June 2022. European Language Resources Association (ELRA).  In print.
  * Ouyang et al. [2022] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al.  Training language models to follow instructions with human feedback.  _Advances in Neural Information Processing Systems_ , 35:27730–27744, 2022.
  * Penedo et al. [2023] Guilherme Penedo, Quentin Malartic, Daniel Hesslow, Ruxandra Cojocaru, Alessandro Cappelli, Hamza Alobeidli, Baptiste Pannier, Ebtesam Almazrouei, and Julien Launay.  The refinedweb dataset for falcon llm: outperforming curated corpora with web data, and web data only.  _arXiv preprint arXiv:2306.01116_ , 2023.
  * Raffel et al. [2020] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _The Journal of Machine Learning Research_ , 21(1):5485–5551, 2020.
  * Sanh et al. [2021] Victor Sanh, Albert Webson, Colin Raffel, Stephen H. Bach, Lintang Sutawika, Zaid Alyafeai, Antoine Chaffin, Arnaud Stiegler, Teven Le Scao, Arun Raja, Manan Dey, M Saiful Bari, Canwen Xu, Urmish Thakker, Shanya Sharma Sharma, Eliza Szczechla, Taewoon Kim, Gunjan Chhablani, Nihal Nayak, Debajyoti Datta, Jonathan Chang, Mike Tian-Jian Jiang, Han Wang, Matteo Manica, Sheng Shen, Zheng Xin Yong, Harshit Pandey, Rachel Bawden, Thomas Wang, Trishala Neeraj, Jos Rozen, Abheesht Sharma, Andrea Santilli, Thibault Fevry, Jason Alan Fries, Ryan Teehan, Stella Biderman, Leo Gao, Tali Bers, Thomas Wolf, and Alexander M. Rush.  Multitask prompted training enables zero-shot task generalization, 2021\.
  * Scialom et al. [2019] Thomas Scialom, Sylvain Lamprier, Benjamin Piwowarski, and Jacopo Staiano.  Answers unite! unsupervised metrics for reinforced summarization models.  _arXiv preprint arXiv:1909.01610_ , 2019.
  * Taori et al. [2023] Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto.  Stanford alpaca: An instruction-following llama model.  https://github.com/tatsu-lab/stanford_alpaca, 2023.
  * Team [2023] MosaicML NLP Team.  Introducing mpt-7b: A new standard for open-source, commercially usable llms, 2023.  URL www.mosaicml.com/blog/mpt-7b.  Accessed: 2023-05-05.
  * Technology Innovation Institute [2023] Falcon Team Technology Innovation Institute.  Falcon llm, 2023.  URL https://falconllm.tii.ae/i.  Accessed: 2023-10-01.
  * Touvron et al. [2023a] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_ , 2023a.
  * Touvron et al. [2023b] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_ , 2023b.
  * Vasilyev et al. [2020] Oleg Vasilyev, Vedant Dharnidharka, and John Bohannon.  Fill in the blanc: Human-free quality estimation of document summaries.  _arXiv preprint arXiv:2002.09836_ , 2020.
  * Wang and Komatsuzaki [2021] Ben Wang and Aran Komatsuzaki.  GPT-J-6B: A 6 Billion Parameter Autoregressive Language Model.  https://github.com/kingoflolz/mesh-transformer-jax, May 2021.
  * Wang et al. [2023] Yiming Wang, Zhuosheng Zhang, and Rui Wang.  Element-aware summarization with large language models: Expert-aligned evaluation and chain-of-thought method.  _arXiv preprint arXiv:2305.13412_ , 2023.
  * Wang et al. [2022a] Yizhong Wang, Yeganeh Kordi, Swaroop Mishra, Alisa Liu, Noah A Smith, Daniel Khashabi, and Hannaneh Hajishirzi.  Self-instruct: Aligning language model with self generated instructions.  _arXiv preprint arXiv:2212.10560_ , 2022a.
  * Wang et al. [2022b] Yizhong Wang, Swaroop Mishra, Pegah Alipoormolabashi, Yeganeh Kordi, Amirreza Mirzaei, Anjana Arunkumar, Arjun Ashok, Arut Selvan Dhanasekaran, Atharva Naik, David Stap, et al.  Super-naturalinstructions:generalization via declarative instructions on 1600+ tasks.  In _EMNLP_ , 2022b.
  * Webson and Pavlick [2022] Albert Webson and Ellie Pavlick.  Do prompt-based models really understand the meaning of their prompts?  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 2300–2344, 2022.
  * Wei et al. [2021] Jason Wei, Maarten Bosma, Vincent Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M Dai, and Quoc V Le.  Finetuned language models are zero-shot learners.  In _International Conference on Learning Representations_ , 2021.
  * Zamfirescu-Pereira et al. [2023] JD Zamfirescu-Pereira, Richmond Y Wong, Bjoern Hartmann, and Qian Yang.  Why johnny can’t prompt: how non-ai experts try (and fail) to design llm prompts.  In _Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems_ , pages 1–21, 2023.
  * Zhang et al. [2022] Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al.  Opt: Open pre-trained transformer language models.  _arXiv preprint arXiv:2205.01068_ , 2022.
  * Zhang et al. [2019] Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q Weinberger, and Yoav Artzi.  Bertscore: Evaluating text generation with bert.  _arXiv preprint arXiv:1904.09675_ , 2019.
  * Zhang et al. [2023] Tianyi Zhang, Faisal Ladhak, Esin Durmus, Percy Liang, Kathleen McKeown, and Tatsunori B Hashimoto.  Benchmarking large language models for news summarization.  _arXiv preprint arXiv:2301.13848_ , 2023.
  * Zhao et al. [2021] Zihao Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh.  Calibrate before use: Improving few-shot performance of language models.  In _International Conference on Machine Learning_ , pages 12697–12706. PMLR, 2021.
  * Zhong et al. [2021a] Ming Zhong, Da Yin, Tao Yu, Ahmad Zaidi, Mutethia Mutuma, Rahul Jha, Ahmed Hassan Awadallah, Asli Celikyilmaz, Yang Liu, Xipeng Qiu, et al.  Qmsum: A new benchmark for query-based multi-domain meeting summarization.  _arXiv preprint arXiv:2104.05938_ , 2021a.
  * Zhong et al. [2021b] Ruiqi Zhong, Kristy Lee, Zheng Zhang, and Dan Klein.  Adapting language models for zero-shot learning by meta-tuning on dataset and prompt collections.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , pages 2856–2878, 2021b.

##  Appendix A Appendix

###  A.1 More Related works

Evaluating LLMs remain a challenge. Promising benchmarks such as HELM [31]
have been developed to evaluate the LLM abilities. While news summarization
features in the benchmark, conversational summarization is missed out. In this
we also argue for inclusion of conversational summarization in the benchmark.
Automatic evaluation of summarization remains a challenge [17]. ROUGE [32] and
BERTScore [55] still remain the most commonly reported reports for
benchmarking purposes. Other metrics compute the quality of the summaries
based on Factual consistency [30]. Given, the subjective nature of the summary
and the difficulty of developing a single or even multiple target summaries,
reference free metrics have been developed in recent times to compute the
quality of the summaries [46]. Human evaluations still remain central to
computing the quality of the summaries [27]. Other metrics rely on question-
answering approaches to measure the quality of the summaries [40].

###  A.2 Other LLMs

MPT-7b MPT [42] is a family of generative LLM from MosaicML NLP team trained
on 1T tokens of text and code. The performance of the model is comparable to
Llama [44]. The instruct version of the model is further trained on for
instruction following from a dataset [15] derived from [14] and [5].
StableLM-7b is a decoder only LLM based on GPT-NeoX [3] from Stability AI. The
model is trained partly on RefinedWeb extract [37], RedPajama data [13] and,
The Pile dataset [19].
Dolly Dolly is a class of LLMs based on Pythia [6] trained on Databricks 15k
dolly dataset [14] and The Pile [19] dataset. From the authors claim Dolly is
not a state-of-the-art model, however has good instruction following
capabilities.
T0pp T0 is a class of encoder-decoder models based on T5 [38] trained in a
multi-task prompted setting consisting of various NLP tasks with the goals of
improving zero-shot generalizational abilities [39]. T0pp exhibits strong
generalizational abilities on various tasks including summarization.

Model Samsum Dialogsum R-1 R-2 R-L B-Score LR N1 N2 R-1 R-2 R-L B-Score LR N1
N2 Llama-7b 0.14 0.02 0.10 0.701 56.58 47.06 85.70 0.16 0.02 0.11 0.736 40.24
31.22 61.87 Falcon-7b 0.14 0.02 0.10 0.703 58.80 48.74 89.68 0.16 0.02 0.11
0.737 36.32 26.61 54.37 MPT-7b 0.14 0.02 0.10 0.693 58.30 45.26 83.00 0.16
0.02 0.11 0.734 44.80 34.93 68.13 Stablelm-7b 0.14 0.01 0.10 0.691 56.45 45.86
83.52 0.14 0.02 0.10 0.732 42.77 33.50 66.29 MPT-7b-inst* 0.15 0.03 0.11 0.703
60.57 49.44 88.52 0.16 0.02 0.11 0.729 44.57 40.49 74.74 MPT-7b-chat* 0.17
0.04 0.12 0.713 63.64 49.92 92.34 0.19 0.04 0.13 0.756 45.32 34.38 70.01
Alpaca* 0.18 0.04 0.13 0.721 35.19 27.82 52.80 0.17 0.03 0.13 0.740 21.78
15.06 32.29 Falcon-7b-inst* 0.21 0.05 0.15 0.739 33.96 27.82 52.63 0.22 0.05
0.15 0.761 24.99 18.10 38.80 Flan-T5-xxl* 0.45 0.20 0.36 0.851 17.77 9.69
24.08 0.32 0.10 0.25 0.794 12.82 6.92 18.10 Dolly* 0.17 0.03 0.12 0.723 57.42
42.03 80.99 0.18 0.03 0.13 0.755 44.52 30.14 62.91 Dolly** 0.12 0.01 0.09
0.727 53.59 43.41 79.20 0.14 0.02 0.10 0.740 51.06 35.95 70.97 Flan-T5-small*
0.42 0.19 0.33 0.844 24.38 8.71 27.25 0.22 0.07 0.17 0.742 17.11 5.54 15.62
Flan-T5-small** 0.43 0.20 0.33 0.845 24.45 8.70 27.33 0.23 0.07 0.18 0.741
17.16 5.63 15.86 Flan-T5-base* 0.46 0.23 0.36 0.856 24.29 9.14 28.01 0.31 0.11
0.24 0.785 18.82 4.80 15.93 Flan-T5-base** 0.47 0.23 0.37 0.857 24.23 9.09
27.92 0.32 0.12 0.25 0.787 18.58 4.82 15.97 Flan-T5-large* 0.44 0.19 0.35
0.849 18.38 10.24 25.25 0.29 0.09 0.23 0.793 13.23 7.59 18.75 Flan-T5-large**
0.46 0.20 0.36 0.851 18.38 10.24 24.22 0.30 0.10 0.24 0.793 13.24 7.52 18.72
Flan-T5-xl* 0.48 0.26 0.39 0.862 24.37 9.87 28.21 0.37 0.16 0.29 0.824 18.10
5.71 18.13 Flan-T5-xl** 0.49 0.26 0.40 0.863 24.41 9.92 28.27 0.38 0.17 0.31
0.827 18.17 5.71 18.13 Llama-7b-chat* 0.18 0.04 0.13 0.721 32.41 25.65 48.58
0.21 0.05 0.15 0.765 31.46 22.54 47.39 Llama-7b-chat**± 0.18 0.05 0.14 0.721
31.66 25.03 47.45 0.21 0.06 0.15 0.760 30.54 22.17 46.17 T0pp-11b** 0.46 0.20
0.36 0.853 18.91 10.15 25.69 0.33 0.11 0.26 0.804 15.19 7.58 20.45 GPT-3.5
turbo 0.14 0.06 0.10 0.746 189.27 80.86 195.89 0.14 0.05 0.11 0.741 140.31
62.33 150.97

Table 2: Zero-shot evaluation of models on conversational summarization task
on all the models (including those which were found to be not suitable for
conversational summarization). This table is a superset of Table 1. The *
indicates the models are instruction tuned. ** Indicates that the models were
further instructed tuned for conversational summarization task. ± indicates
that the model was trained using adapters.

Model Samsum Samsum - FT dialogsum dialogsum -FT R1 RL B-Score R1 RL B-Score
R1 RL B-Score R1 RL B-Score Flan-T5-small 0.42 0.33 0.846 0.43 0.34 0.862 0.24
0.20 0.751 0.24 0.20 0.753 Flan-T5-base 0.46 0.37 0.857 0.47 0.38 0.857 0.33
0.26 0.793 0.34 0.26 0.794 Flan-T5-large 0.45 0.36 0.852 0.49 0.40 0.886 0.31
0.25 0.802 0.30 0.25 0.801 Flan-T5-xl 0.49 0.39 0.863 0.49 0.40 0.863 0.39
0.31 0.824 0.39 0.32 0.836 Llama-7b-chat* 0.32 0.24 0.808 0.33 0.24 0.809 0.26
0.21 0.789 0.29 0.21 0.792 GPT-3.5 0.21 0.14 0.748 - - - 0.24 0.20 0.775 - - -

Table 3: Average best performing prompt result.

###  A.3 Dataset resources

1\. Dialogsum: https://huggingface.co/datasets/knkarthick/dialogsum

2\. Samsum: https://huggingface.co/datasets/samsum

3\. Promptsource: https://github.com/bigscience-
workshop/promptsource/tree/main/promptsource/templates/samsum

###  A.4 Model hyper-parameters

We num train epochs=25, train batch size=2, warmup steps=500, weight
decay=0.01, learning rate=5e-10, AdamW optimizer for Flan-T5 models and Dolly
models. We used FP32 for Flan-T5 and Fp16 precision for Dolly model weights.

For Lama-7b-chat finetuning we used LORA [22] adapters for finetuning.

lora_r = 8
lora_alpha = 16
lora_dropout = 0.05
lora_target_modules= [
“q_proj”,
“v_proj”,
] with ,
num_train_epochs=10,
per_device_train_batch_size=2,
per_device_eval_batch_size=2,
warmup_steps=500,
weight_decay=0.01,

When inferencing with GPT3.5 we used temperature=0.2, max tokens=500, top p=1,
frequency penalty=0, presence penalty=0.

Figure 4: Shows human evaluation of summaries generated by the models 1 | Generate a summary for this dialogue | Used
---|---|---
2 | Summarize: | Used
3 | To sum up this dialog | Used
4 | Given the above dialogue write a summary | Used
5 | Summarize this dialogue: | Used
6 | Sum up the following dialogue | Used
7 | Write a dialogue that match this summary | Not Used
Table 4: Prompts from the Promptsource dataset and if they’re used for
generating the summary in this work.

Model Samsum Dialogsum R1(p/r) R2(p/r) RL(p/r) N1 N2 R1(p/r) R2(p/r) RL(p/r)
N1 N2 Flan-T5-small* 0.72/0.30 0.37/0.15 0.58/0.24 9.15 28.41 0.80/0.20
0.50/0.12 0.63/0.16 5.75 16.10 Flan-T5-base* 0.74/0.31 0.37/0.15 0.59/0.25
9.60 29.21 0.84/0.23 0.55/0.15 0.70/0.19 4.97 16.41 Flan-T5-large* 0.68/0.20
0.24/0.07 0.51/0.15 10.75 26.34 0.70/0.13 0.28/0.05 0.53/0.10 7.86 19.32
Llama-7b 0.39/0.21 0.10/0.05 0.28/0.14 49.66 89.49 0.43/0.21 0.11/0.05
0.29/0.13 23.49 48.84 Falcon-7b 0.34/0.27 0.07/0.17 0.20/0.17 51.32 93.59
0.46/0.21 0.11/0.05 0.29/0.12 27.64 56.09 MPT-7b 0.34/0.07 0.10/0.07 0.22/0.17
47.53 86.49 0.42/0.24 0.11/0.07 0.25/0.14 36.22 70.24 Stablelm-7b 0.31/0.24
0.06/0.05 0.19/0.15 48.30 87.20 0.42/0.22 0.11/0.06 0.25/0.13 34.87 68.43
MPT-7b-inst* 0.31/0.26 0.08/0.07 0.19/0.07 51.96 92.31 0.54/0.18 0.14/0.05
0.37/0.12 41.91 76.98 Dolly* 0.38/0.30 0.10/0.08 0.24/0.19 44.26 84.53
0.49/0.27 0.16/0.09 0.29/0.16 31.35 64.89 Alpaca* 0.39/0.21 0.10/0.05
0.28/0.14 29.33 55.03 0.47/0.20 0.14/0.06 0.34/0.14 15.61 33.22
Falcon-7b-inst* 0.41/0.20 0.08/0.05 0.28/0.13 29.27 54.88 0.54/0.18 0.14/0.05
0.37/0.05 18.81 40.02 Flan-T5-xl* 0.73/0.31 0.37/0.15 0.57/0.24 10.36 29.42
0.82/0.22 0.48/0.13 0.67/0.18 5.90 18.68 Flan-T5-xxl* 0.69/0.19 0.25/0.07
0.52/0.15 10.18 25.11 0.74/0.14 0.32/0.06 0.57/0.11 7.01 18.54 MPT-7b-chat*
0.32/0.29 0.09/0.08 0.20/0.19 52.65 96.40 0.45/0.27 0.13/0.08 0.26/0.16 35.80
72.21 Llama-7b-chat* 0.38/0.21 0.09/0.21 0.28/0.06 27.05 50.68 0.50/0.14
0.14/0.06 0.33/0.14 23.49 48.84 Flan-T5-small** 0.72/0.30 0.38/0.15 0.58/0.25
9.13 28.51 0.80/0.20 0.49/0.12 0.62/0.16 5.83 16.35 Flan-T5-base** 0.74/0.30
0.38/0.15 0.58/0.25 9.55 29.12 0.84/0.23 0.54/0.15 0.69/0.19 4.99 16.45
Flan-T5-large** 0.68/0.20 0.24/0.07 0.51/0.15 10.77 26.36 0.70/0.13 0.28/0.05
0.53/0.10 7.79 19.29 Flan-T5-xl** 0.73/0.31 0.37/0.15 0.57/0.24 10.41 29.48
0.82/0.22 0.48/0.13 0.67/0.13 5.90 18.67 Dolly ** 0.31/0.22 0.06/0.04
0.22/0.13 45.58 82.58 0.43/0.23 0.08/0.05 0.24/0.13 33.69 67.67 T0pp-11b **
0.69/0.25 0.25/0.08 0.52/0.16 10.65 26.80 0.74/0.16 0.32/0.07 0.56/0.12 7.84
21.06 Llama-7b-chat**± 0.38/0.21 0.09/0.06 0.28/0.14 26.34 49.43 0.50/0.13
0.13/0.06 0.33/0.13 22.94 47.60

Table 5: Table shows the Rouge and Novel 1-gram and Novel 2-gram scores of the
generated summary compared to the . High Rouge of copying mechanisms in the
summary generated Figure 5: Interface for humans rating the summaries
comparing two summaries.  Figure 6: Box plots with Rouge scores per prompt
from Prompsource dataset and various LLMs. Flan models (instruction tined)
models seem to be more robust to different prompts. ROUGE scores for all the
prompts in Table 4.  Figure 7: Box plots with Rouge scores per prompt from
Prompsource dataset for various LLMs. Instruction tunings seems to improve the
ROUGE scores across prompts, however the performance on different prompts
seems to be an issue. ROUGE scores for all the prompts in Table 4. Table 6:
Example (not handpicked). Chosen randomly from the dataset.

(Conversation) (Ground truth) Person1: Hello, how are you doing today?
Person2: I ’ Ve been having trouble breathing lately. Person1: Have you had
any type of cold lately? Person2: No, I haven ’ t had a cold. I just have a
heavy feeling in my chest when I try to breathe. Person1: Do you have any
allergies that you know of? Person2: No, I don ’ t have any allergies that I
know of. Person1: Does this happen all the time or mostly when you are active?
Person2: It happens a lot when I work out. Person1: I am going to send you to
a pulmonary specialist who can run tests on you for asthma. Person2: Thank you
for your help, doctor. Person2 has trouble breathing. The doctor asks Person2
about it and will send Person2 to a pulmonary specialist. (Flan-T5-small) I am
going to send you to a pulmonary specialist who can run tests on you for
asthma. Do you have any allergies that you know? (Flan-T5-base) Person1 is
going to send Person2 to a pulmonary specialist who can run tests on Person2
for asthma. He will send Person1 and Person2 a message. (Flan-T5-small**)
Person2: Hi, how are you doing today? I ’ve been having problems breathing
lately. I haven ’t had a cold. I just have a heavy feeling in my chest when I
try to breathe Person1: Do you have any allergies that you know?
(Flan-T5-base**) Person2 has been having trouble breathing lately. She has a
heavy feeling in her chest when she try to breathe. Person1 is going to send
her to a pulmonary specialist who can run tests on her for asthma. (Llama-7b)
1\. Describe your dialogue: 2\. How should you greet the patient? (1 Marks)
3\. What should you ask about the lifestyle? (1 Marks) 4\. What symptoms would
you suspect? (1 Marks) 5\. List three diagnostic tests that your friend doctor
would run on a patient suffering from your partner patient disease. (2 Marks)
(Alpaca-7b) The patient has been having difficulty breathing and it is a
recurring issue. The doctor notices that it happens mostly when the patient is
active, so they suggest sending the patient to a pulmonary specialist for
tests to rule out asthma. The patient is thankful for the doctor’s help.
(Llama-7b-chat) Person 1 (doctor) is interacting with Person 2 (patient)
during a consultation. Person 2 has been experiencing difficulty breathing,
and the doctor asks questions to gather more information and determine the
cause. The doctor suspects asthma and recommends a pulmonary specialist for
further tests. (Llama-7b-chat**) Summary: The two people in the dialogue are
discussing symptoms related to breathing difficulties. Person two explains
that they have been experiencing a heavy feeling in their chest when trying to
breathe, but have not had any colds or allergies. The first person suggests
that they may have asthma and sends them to a pulmonary specialist for further
testing. (Falcon-7b) Write a summary of Person1: ‘Person1 has a heavy feeling
in the chest when he/she tries to breathe.’ Person1 goes to the primary care
physician who diagnoses him/her with a lung infections. Person1: and the
doctor sends him/her to another doctor for further tests. The doctor has been
breathing difficulties. The doctor runs tests like a lung disease. A
specialist helps Person2: ’s diagnose (Falcon-7b-instruct) After discussing
symptoms with Person1, an appointment is arranged with a pulmonary specialist
to examine person2 and diagnose any underlying respiratory issues.
(Flan-T5-XL) Person2 has been having trouble breathing lately. Person1 is
going to send him to a pulmonary specialist who can run tests on him for
asthma. (Flan-T5-XXL) Person2 has been having breathing problems lately. They
happen primarily when he exercises, so he might have Asthma.

(Flan-T5-Large) Person2 has trouble breathing. She has not had any cold, and her chest is heavy when she tries to breath. At Person1 she will have tests for asthma. |  (Flan-T5-Large**) Person2 has trouble breathing because of allergies. She may have asthma and a specialist will run tests on her.
---|---
(MPT-7b) Person2: I been having difficulty in breathing lately.Person2: Never, I have just a heavy feeling in my chest when I try to breathe. Person2: I have no allergies that I know of.The D.P.R.I.V.E.R.S. Copyright© コスメを楽しくできるガウ！, 2016 All Rights Reserved.We’re all set for our launch! |  (MPT-7b-chat) Person1 and Person2 are speaking with each other. Person1 is listening to Person2’s concerns about their breathing difficulties and suspects that Person2 may have asthma. Person1 suggests that Person2 should see a pulmonary specialist and arranges an appointment for them. Person1 suspects that Person2 may have asthma because it happens when Person2 is active which is a common symptom of asthma. Person1 also asks about allergies, colds and whether it happens all the time.
(MPT-7b-instruct) A person that has breathing problems should consult a doctor that can perform a pulmonary function test for asthma. The World Economic Forum has created a unique and exclusive partnership with the International Monetary Fund,the World Bank and the United Nations to tackle the main issues and challenges of our time. The U.S. Department of State’s Bureau of East Asian and Pacific Affairs is seeking young professionals for the Regional Internship Program (RIP) at the U.S. Embassy in Beijing. |  (GPT-3.5) I appreciate it. Person 1 is a doctor who is asking Person 2 how they are feeling. Person 2 responds that they have been having trouble breathing lately and a heavy feeling in their chest. Person 1 asks if they have had a cold or any allergies, and Person 2 responds that they have not. Person 1 asks if this happens all the time or mostly when they are active, and Person 2 responds that it happens a lot when they work out. Person 1 decides to send Person 2 to a pulmonary specialist to run tests for asthma. Person 2 thanks Person 1 for their help.

Figure 8: Rouge, Bert novel n-grams and LR on Dialog sum dataset (contd. in
next page) Figure 9: Rouge, Bert novel n-grams and LR on Dialog sum dataset
(contd. in next page) Figure 10: Rouge, Bert novel n-grams and LR on Dialog
sum dataset (contd. in next page) Figure 11: Rouge, Bert novel n-grams and LR
on SAMsum dataset (contd. in next page) Figure 12: Rouge, Bert novel n-grams
and LR on SAMsum dataset (contd. in next page) Figure 13: Rouge, Bert novel
n-grams and LR on SAMsum dataset (contd. in next page) Figure 14: Rouge, Bert
novel n-grams and LR on SAMsum dataset (contd. in next page)


reaches the requested node. Indeed, we know that $i_{0}\geq i$ at this
timestep, so line (9) of the FullUpdate procedure ensures that at least
$\frac{\gamma}{4H\lambda^{i_{0}}}=\frac{\xi_{\tau}}{4Hc_{v_{i}}}$ amount of
server reaches $v_{0}$, where we used that
$\xi_{\tau}=\lambda^{i_{0}-i}\gamma$. Since at most one unit of server reaches
$v_{0}$ when summed over all timesteps corresponding to $q$, we get

$\sum_{\tau\in S(i,i^{\prime})}\xi_{\tau}\leq 4Hc_{v_{i}}.\qed$

###  7.4 Proving the Invariant Conditions

We begin by stating the invariant conditions and show that these are
satisfied. Invariant (I2) statement only changes slightly: we replace $\gamma$
by $\Gamma(v,\tau)$ as given below.

######  Invariant (I5).

At the end of each timestep $\tau\in\mathcal{R}^{ns}(v)$, the objective
function value of the dual variables corresponding to constraints in
${\mathfrak{L}}^{v}(\tau)$ equals $\Gamma(v,\tau)$. I.e., if a generic
constraint $C$ is given by $\langle a^{C}\cdot y^{v}\rangle\geq b^{C}$, then

$\displaystyle\sum_{C\in{\mathfrak{L}}^{v}(\tau)}b^{C}\cdot
z_{C}=\Gamma(v,\tau)\qquad\forall\tau\in\mathcal{R}^{ns}(v).$ (I5)

Furthermore, $b^{C}>0$ for all $C\in\mathfrak{L}^{v}(\tau)$ and
$\tau\in\mathcal{R}(v)$.

(iii) shows that the invariant above is satisfied whenever $\tau$ gets added
to $\mathcal{R}^{ns}(v)$ by SimpleUpdate, and the second statement follows
from the comment after (21). As before, the quantity ${\sf loss}(u,\tau)$ is
defined by (10) whenever $\textsc{FullUpdate}(v,\tau)$ is called, $v$ being
the parent of $u$. The invariant condition (I4) is replaced by the following
which also accounts for the extra transfer which happens during line (9) in
$\textsc{FullUpdate}(v,\tau)$ procedure:

######  Invariant (I6).

Consider a node $v$ and timestep $\tau$ such that
$\textsc{FullUpdate}(v,\tau)$ is called. Let $u$ be the $v$’s principal child
at timestep $\tau$. The server mass entering subtree $T_{u}$ during the
procedure $\textsc{FullUpdate}(v,\tau)$ is at most

$\displaystyle\frac{\gamma-{\sf
loss}(u,\tau)}{\lambda^{h}}+\frac{\gamma}{4H\lambda^{h}}.$ (I6)

We again use the ordering $\prec$ on pairs $(v,\tau)$ and assume that the
above two invariant conditions holds for all
$(v,\tau)\prec({v^{\star}},{\tau^{\star}})$. We now outline the main changes
needed in the analysis done in Section 5.1. Claim 5.5 still holds with the
same proof. We can again define ${\sf
fill}(u,\tau),\tau\in\mathcal{R}^{ns}(u)$ as in (11). Note that
$\tau^{\prime}\in{\sf fill}(u,\tau)$ only if $\textsc{FullUpdate}(v,\tau)$ is
called, where $v$ is the parent of $u$. Claim 5.7 still holds with the same
proof. The statement of Claim 5.8 changes to the following:

######  Claim 7.9.

Let $\tau\in\mathcal{R}(u)$ for some $\tau<{\tau^{\star}}$. The server mass
entering $T_{u}$ at timestep $\tau$ is at most

$\left(1+\frac{1}{\lambda-1}\right)\left(1+\frac{1}{4H}\right)\frac{\Gamma(u,\tau)}{\lambda^{{\textsf{level}}(u)}}-\frac{{\sf
loss}(u,\tau)}{\lambda^{{\textsf{level}}(u)}}.$

###### Proof.

Consider the iteration of the while loop of Algorithm 4 corresponding to
timestep $\tau$. First consider the case when $u$ happens to be $v_{i},i\geq
i_{0}$. In this case, $\Gamma(u,\tau)=\gamma$. The result follows as in the
proof of Claim 5.8, where the extra term of $\frac{\gamma}{4H\lambda^{h}}$
arises because of line (9) in the FullUpdate procedure.

Now consider the case when $u$ is a vertex of the form $v_{i},i<i_{0}$. Note
that $\frac{\gamma}{\lambda^{h_{0}}}=\frac{\Gamma(v_{i},\tau)}{\lambda^{h}}$,
and so the result follows in this case as well by using Invariant (I6), and
the quantity ${\sf loss}(u,\tau)=0$ here. ∎

The classification of $g(w,\tau)$ into
$g^{\mathsf{loc}}(w,\tau),g^{\mathsf{inh}}(w,\tau)$ holds as before. The
statement of Lemma 5.9 changes as given below, and the proof follows the same
lines. We assume that $\textsc{FullUpdate}({v^{\star}},{\tau^{\star}})$ is
called.

######  Lemma 7.10.

Let $u$ be a non-principal child of ${v^{\star}}$ at timestep
${\tau^{\star}}$, and $I:=(\tau_{1},{\tau^{\star}}]$ for some timestep
$\tau_{1}<{\tau^{\star}}$. Let $S$ be the timesteps in
$\mathcal{R}^{ns}(u)\cap(\tau_{1},{\tau^{\star}}]$ that have been removed from
${\sf Awake}(u)$ by the moment when
$\textsc{FullUpdate}({v^{\star}},{\tau^{\star}})$ is called. Then

$\displaystyle
g^{\mathsf{inh}}(u,(\tau_{1},{\tau^{\star}}])\geq\left(1+\frac{1}{2H}\right)\,\frac{\Gamma(u,S)}{\lambda^{{\textsf{level}}(u)}}-\sum_{\tau\in
S}\frac{{\sf loss}(u,\tau)}{\lambda^{{\textsf{level}}(u)}},$

where $\Gamma(u,S)=\sum_{\tau\in S}\Gamma(u,\tau)$.

The statement and proof of Corollary 5.10 remains unchanged. The proof of
Claim 5.11 also remains unchanged, though we now need to use (i) (part (iii)).
We now restate the analogue of Claim 5.12:

######  Claim 7.11 (Inductive Step Part I).

Consider the call $\textsc{FullUpdate}({v^{\star}},{\tau^{\star}})$, and let
$u_{0}$ be the principal child of ${v^{\star}}$ at this timestep. Suppose
${\sf activesib}(u_{0},{\tau^{\star}})\neq\varnothing$. Then the dual
objective value corresponding to the constraints in
${\mathfrak{L}}^{v^{\star}}({\tau^{\star}})$ equals $\gamma$; i.e.,

$\sum_{C\in{\mathfrak{L}}^{v^{\star}}({\tau^{\star}})}z_{C}\,b^{C}=\gamma.$

Moreover, the server mass entering $T_{u_{0}}$ going to the request node in
this call is at most

$\frac{\gamma-{\sf
loss}(u_{0},{\tau^{\star}})}{\lambda^{h}}+\frac{\gamma}{4H\lambda^{h}}.$

Since the update rule for the $y^{v}$ variables in line (9) of the FullUpdate
procedure does not consider the intervals $I_{u}^{\prime}$ (as stated in
(22)), the proof proceeds along the same lines as that of Claim 5.12. The
extra additive term of $\frac{\gamma}{4H\lambda^{h}}$ appears due to line (9)
in FullUpdate procedure. The statement and proof of Claim 5.14 remain
unchanged. This shows that the two invariant conditions (I5) and (I6) are
satisfied. Finally, we state the analogue of Corollary 5.15 which bounds the
parameter $M$.

######  Corollary 7.12.

For node $u$ and timestep $\tau$, let $\tau_{u}:={\sf prev}(u,\tau)$. There
are at most $\frac{5H\lambda^{2H}k}{2\gamma}$ timesteps in
$(\tau_{u},\tau]\cap\mathcal{R}^{ns}(u)$. So we can set $M$ to
$\frac{5H\lambda^{2H}k}{2\gamma}+1$.

###### Proof.

The proof proceeds along the same lines as that of Corollary 5.15, except that
the analogue of (13) now becomes:

$\displaystyle
g^{\mathsf{inh}}(u,I)-r(u,I)\geq\left(\frac{1}{2H}-\frac{1}{\lambda-1}\left(1+\frac{1}{4H}\right)\right)\frac{\Gamma(u,S)}{\lambda^{h}}\geq\frac{2}{5H}\cdot\frac{\gamma|S|}{\lambda^{2H}},$

where the last inequality uses (ii)(i). This implies the desired upper bound
on $|S|$. ∎

This shows that the algorithm FullUpdate is well defined. Next we give
properties of the charging forest, and then show that the dual variables in
each of the local LPs are near-feasible.

###  7.5 Properties of the Charging Forest

Fix a vertex $v$ and consider the charging forest ${{\cal F}^{ch}}(v)$. Recall
the notation from §6.1.1: a node in this forest is a tuple
$a_{i}=(w_{i},q_{i})$, and has a corresponding leaf request
${\mathsf{EarliestLeafReq}}(w_{i},q_{i})=(\ell_{i},R_{i}=[b_{i},e_{i}])$. We
begin with a monotonicity property, which is useful to show that (21) is
properly defined (and the $\boldsymbol{\tau}$ values are “monotone”).

######  Claim 7.13 (Monotonicity I).

Suppose $a_{2}=(w_{2},q_{2})$ is the parent of $a_{1}=(w_{1},q_{1})$ in the
forest ${{\cal F}^{ch}}(v)$. Then, $e_{1}\leq e_{2}$.

###### Proof.

By definition of an edge in ${{\cal F}^{ch}}(v)$, the request interval $R_{2}$
for $a_{2}$ must contain $q_{1}$. At time $q_{1}$, the function
${\textsc{FindLeaves}}(w_{2},q_{1})$ would have returned $w_{1}$ as one of the
vertices in the set $S$ (i.e., $w_{2}$ would have _spawned_ $w_{1}$ at time
$q_{1}$), and $R_{2}$ was also an request below $w_{2}$ at time $q_{1}$, so
$R_{1}$ must end no later than $R_{2}$ does. ∎

######  Corollary 7.14 (Monotonicity II).

Let $a_{i}=(w_{i},q_{i})$ belong to a tree ${\mathcal{T}}$ of ${{\cal
F}^{ch}}(q)$ rooted at $(v,q)$. Then $q_{i}<e_{i}\leq q$.

###### Proof.

The first fact uses that $R_{i}$ is active at time $q_{i}$. The second fact
follows by repeated application of Claim 7.13, and that the earliest leaf
request at the root $(v,q)$ corresponds to the request critical at time $q$,
which ends at $q$. ∎

The next result shows another key low-congestion property of the charging
forest, which we then use to build lower bounds for any single-server
instance.

######  Lemma 7.15 (Low Congestion II).

Consider $u,v$ such that $u\in T_{v}$. Let
${\mathcal{T}}_{1},\ldots,{\mathcal{T}}_{l}$ be distinct charging trees in the
forest ${{\cal F}^{ch}}(v)$, where ${\mathcal{T}}_{j}$ is rooted at
$(v,q_{j})$ and contains a _leaf_ vertex $a_{j}=(u,q_{j}^{\prime})$, with the
corresponding ${\mathsf{EarliestLeafReq}}(a_{j})$ denoted
$(\ell_{j},R_{j}=[b_{j},e_{j}])$. Then (a) the intervals
$\\{(q_{j}^{\prime},q_{j}]\\}_{j\in[l]}$ have congestion at most $H$, and (b)
the set of intervals $\\{(b_{j},q_{j}^{\prime}]\\}_{j\in[l]}$ are mutually
disjoint. Therefore, the set of intervals $\\{(b_{j},q_{j}]\\}_{j\in[l]}$ have
congestion at most $H+1$.

###### Proof.

Consider a timestep $t$, and let $S_{t}\subseteq[l]$ be the set of indices $j$
such that $t\in(q_{j}^{\prime},q_{j}]$. For each $j\in S_{t}$, consider the
path $P_{j}$ from $a_{j}=(u,q_{j}^{\prime})$ to the root $(v,q_{j})$ in
${\mathcal{T}}_{j}$. For sake of concreteness, let this path be
$(u_{j}^{1},q_{j}^{1})=(u,q_{j}^{\prime}),(u_{j}^{2},q_{j}^{2}),\ldots,(u_{j}^{n_{j}},q_{j}^{n_{j}})=(v,q_{j})$.
Since $t\in(q_{j}^{\prime},q_{j}]$, there is an index $i$ such that
$t\in(q_{j}^{i-1},q_{j}^{i}]$—call this index $i(j)$.

######  Subclaim 7.16.

For any two distinct $j,j^{\prime}\in S_{t}$, $u_{j}^{i(j)}\neq
u_{{j^{\prime}}}^{i(j^{\prime})}$.

###### Proof.

Suppose not. For sake of brevity, let $w$ denote
$u_{j}^{i(j)}=u_{{j^{\prime}}}^{i(j^{\prime})}$, $i$ denote $i(j)$ and
$i^{\prime}$ denote $i(j^{\prime})$. Assume wlog that
$q_{j^{\prime}}^{i^{\prime}}<q_{j}^{i}$. So ${\mathcal{T}}_{j}$ and
${\mathcal{T}}_{j^{\prime}}$ have vertices $(w,q_{j}^{i})$ and
$(w^{\prime},q_{j^{\prime}}^{i^{\prime}})$ respectively. Now consider the
child of $(u_{j}^{i-1},q_{j}^{i-1})$ of $(w,q_{j}^{i})$. The rule for adding
edges in ${\mathcal{T}}_{j}$ states that we look at the highest time
$q^{\prime}<q_{j}^{i}$ for which there is a vertex $(w,q^{\prime})$ in the
charging forest, and so $q_{j}^{i-1}=q^{\prime}$. Also $q^{\prime}\geq
q_{j^{\prime}}^{i^{\prime}}$. But then, the intervals
$(q_{j}^{i-1},q_{j}^{i}]$ and
$(q_{j^{\prime}}^{i^{\prime}-1},q_{j^{\prime}}^{i^{\prime}}]$ are disjoint,
which is a contradiction because both of them contain $t$. ∎

Since all these $u_{j}^{i(j)}$ vertices must lie on the path from $u$ to $v$
in $T$, there are only $H$ of them. Since they are distinct by the above
claim, the number of intervals containing $t$ is at most $H$, which proves the
first statement.

To prove the second statement, assume w.l.o.g. that $\\{q_{j}\\}_{j\in[l]}$
are arranged in increasing order. It suffices to show that for any $j\in[l]$,
$(b_{j},q_{j}^{\prime}]$ and $(b_{j+1},q_{j+1}^{\prime}]$ are disjoint.
Suppose not. Since $e_{j+1}\geq q_{j+1}^{\prime}$ (by Corollary 7.14), we have
that $R_{j+1}$ contains $q_{j}^{\prime}$. Since $(u,q_{j+1}^{\prime})$ has no
children ${\mathcal{T}}_{j+1}$, the construction of the charging forest means
${\textsc{FindLeaves}}(u,q_{j}^{\prime})$ should have returned the set
$S=\varnothing$. Now since $v$ is added to the set $Z_{q_{j}^{\prime}}$, all
the active requests—in particular $R_{j+1}$— below $u$ at time
$q_{j}^{\prime}$ would be serviced at time $q_{j}^{\prime}$ due to line (4)).
This contradicts the fact that $R_{j+1}$ is active at time
$q_{j+1}^{\prime}>q_{j}^{\prime}$. ∎

###  7.6 Dual Feasibility of SimpleUpdate

Fix a vertex $v$ and the local LP $\mathfrak{L}^{v}$, which has variables
$y^{v}(u,\tau)$ for $u\in T_{v}$ and timesteps $\tau$. First, consider only
the constraints in $\mathfrak{L}^{v}$ added by the SimpleUpdate procedure,
i.e., using (21).

######  Theorem 7.17.

For a variable $y^{v}({u^{\star}},{\tau^{\star}})$, let ${S^{\star}}$ be the
set of timesteps $\tau$ such that SimpleUpdate is called on $v$, and the
(unique) constraint $C_{\tau}$ (of the form (21)) that it adds to
$\mathfrak{L}^{v}(\tau)$ contains the variable
$y^{v}({u^{\star}},{\tau^{\star}})$ on the LHS. Then:

$\displaystyle\sum_{\tau\in{S^{\star}}}z(C_{\tau})\leq O(H^{4})\cdot
c_{{u^{\star}}}.$ (23)

###### Proof.

In the call to SimpleUpdate, we use the charging tree rooted at a vertex
$v_{i^{\star}}$, where $v_{i^{\star}}$ lies between $v$ and ${u^{\star}}$.
Motivated by this, for a node $v^{\prime}$ on the path between ${u^{\star}}$
and $v$, let ${S^{\star}}(v^{\prime})$ denote the subset of timesteps $\tau$
for which the corresponding vertex $v_{i^{\star}}$ is set to $v^{\prime}$. We
show:

######  Subclaim 7.18.

For any $v^{\prime}$ on the path between ${u^{\star}}$ and $v$,

$\sum_{\tau\in{S^{\star}}(v^{\prime})}z(C_{\tau})\leq O(H^{3})\cdot
c_{{u^{\star}}}.$

###### Proof.

Consider a timestep $\tau\in{S^{\star}}(v^{\prime})$. Let ${\mathcal{T}}_{q}$
be the tree in the charging forest ${{\cal F}^{ch}}(v^{\prime})$ containing
$(v^{\prime},q)$ for $q=\lfloor\tau\rfloor$. As described when defining (21),
let $\mathcal{L}_{s_{\tau}}$ be the leaves of ${\mathcal{T}}_{q}$
corresponding to level $s_{\tau}$. Since the variable involving ${u^{\star}}$
appears in this constraint, we have ${u^{\star}}\in\mathcal{L}_{s_{\tau}}$.
Therefore, each leaf in $\mathcal{L}_{s_{\tau}}$ has cost equal to
$c_{u^{\star}}$, By the choice of level, the total cost of this set is at
least $\frac{c_{v^{\prime}}}{H}$, so

$|\mathcal{L}_{s_{\tau}}|\geq\frac{c_{v^{\prime}}}{Hc_{{u^{\star}}}}.$

Moreover, the tree ${\mathcal{T}}_{q}$ was not a singleton so
$c_{{u^{\star}}}\leq c_{v^{\prime}}/\lambda$, and since $\lambda\geq 10H$, we
get $|\mathcal{L}_{s_{\tau}}|\geq 10$. Recall that we set

$z(C_{\tau})=\frac{\xi_{\tau}}{|\mathcal{L}_{s_{\tau}}|-k_{v^{\prime},\tau_{v^{\prime}}}-2\delta(n-n_{v^{\prime}})}\leq\frac{2\xi_{\tau}}{|\mathcal{L}_{s_{\tau}}|},$

where the inequality uses that all leaves below $v$ (except for the requested
leaf) have at most $\delta$ servers, and so
$k_{v^{\prime},\tau_{v^{\prime}}}+2\delta(n-n_{v^{\prime}})\leq
1+2n\delta\ll|\mathcal{L}_{s_{\tau}}|/2$. Combine the above two facts, for any
time $q$,

$\displaystyle\sum_{\tau:\tau\in{S^{\star}}(v^{\prime}),\lfloor\tau\rfloor=q}z(C_{\tau})\leq\frac{2Hc_{u^{\star}}}{c_{v^{\prime}}}\cdot\sum_{\tau:\tau\in{S^{\star}}(v^{\prime}),\lfloor\tau\rfloor=q}\xi_{\tau}\leq
24H^{2}\;c_{{u^{\star}}},$ (24)

where the last inequality follows from Lemma 7.8.

We need to sum over different values of $q$, so consider
$Q:=\\{\lfloor\tau\rfloor\mid\tau\in{S^{\star}}(v^{\prime})\\}$. For each
value $q_{j}\in Q$, choose $\tau_{j}$ to be one representative timestep in
${S^{\star}}$ (in case there are many). For each $q_{j}\in Q$, there is a
vertex of the form $(u^{\star}_{j},q_{j}^{\prime})$ in the tree in ${{\cal
F}^{ch}}(v^{\prime})$ rooted at $(v^{\prime},q_{j})$. The constraint
$C_{\tau_{j}}$ involves $y^{v}({u^{\star}},(b_{j},\tau_{j}])$, where $b_{j}$
is the left end-point of the leaf request
${\mathsf{EarliestLeafReq}}({u^{\star}},q_{j}^{\prime})$. And ${\tau^{\star}}$
belongs to all of these intervals $(b_{j},\tau_{j}]$. Write $(b_{j},\tau_{j}]$
as $(b_{j},q_{j}]\cup(q_{j},\tau_{j}]$. The intervals $(q_{j},\tau_{j}]$ are
mutually disjoint for all $j$, and the intervals $(b_{j},q_{j}]$ have
congestion at most $H+1$ by Congestion Lemma II (Lemma 7.15). Therefore the
intervals $(b_{j},\tau_{j}]$ have congestion at most $H+2$, and so $|Q|\leq
H+2$. Combining this with (24) completes the proof. ∎

Theorem 7.17 follows from the above claim by summing over all $v^{\prime}$ on
the path from ${u^{\star}}$ to $v$. ∎

###  7.7 Dual Feasibility

In this section, we show approximate dual feasibility of the entire solution
due to both the SimpleUpdate and FullUpdate procedures. The proof is very
similar to the one for $k$-Server (in §5.2) except for two changes: (i) we
need to account for the intervals $I_{u}^{\prime}$ as in (22), and (ii) we
have defined new sets of constraints in SimpleUpdate procedure, so the result
of Theorem 7.17 needs to be combined with the overall dual feasibility result.
Observe that the statements of Claim 5.16 and Claim 5.17 hold without any
changes. We now prove the analogue of Lemma 5.19. First, a simple observation.

######  Claim 7.19.

Consider a time $q$ and vertex $v$ such that a critical request at time $q$
lies below $v$. Then the total objective value of dual variables raised during
FullUpdate procedure at $v$ is at most $4Hc_{v}/\lambda$.

###### Proof.

Let the height of $v$ be $h+1$. During each call of FullUpdate at $v$, we
raise the dual objective by $\gamma$ units (by Claim 7.11), and transfer at
least $\frac{\gamma}{4H\lambda^{h}}=\frac{\gamma\lambda}{4Hc_{v}}$ server mass
to the requested leaf node $\ell_{q}$. Since we transfer at most one unit of
server mass to $\ell_{q}$, the result follows. ∎

######  Theorem 7.20 (Dual Feasibility for Time-Windows).

For a node $v$ at height $h+1$, consider the dual variables $z(C)$ for
constraints added in $\mathfrak{L}^{v}$ during the FullUpdate and the
SimpleUpdate procedure. These dual variables $z_{C}$ are $\beta_{h}$-feasible
for the dual program $\mathfrak{D}^{v}$, where
$\beta_{h}=\left(1+\nicefrac{{1}}{{H}}\right)^{h}O(H^{4}+H(\ln n+\ln
M+\ln(k/\gamma))).$

###### Proof.

We prove the claim by induction on the height of $v$. For a leaf node, this
follows vacuously, since the primal/dual programs are empty. Suppose the claim
is true for all nodes of height at most $h$. For a node $v$ at height $h+1>0$
with children $\chi_{v}$, the variables in ${\mathfrak{L}}^{v}$ are of two
types: (i) $y^{v}(u,t)$ for some timestep $t$ and child $u\in\chi_{v}$, and
(ii) $y^{v}(u^{\prime},t)$ for some timestep $t$ and non-child descendant
$u^{\prime}\in T_{v}\setminus\chi_{v}$.

We consider variables of the first type. Fix a child $u$ and a timestep
$\tau$, and let ${\cal C}^{F}$ be the set of constraints in $\mathfrak{L}^{v}$
added in FullUpdate subroutine that contain the variable $y^{v}(u,\tau)$ in
the LHS. We group ${\cal C}^{F}$ into three classes of constraints (and draw
on the notation in (22)):

  * (i)

The timestep $t$ lies in $I_{u}=(\tau_{u},\tau]$, where $u$ is a non-principal
child of $v$ at the timestep $\tau$ at which this constraint is added: call
this set of constraints ${\cal C}_{1}(t)$. The argument here is identical to
that in the proof of Lemma 5.19, and so we get

$\sum_{C\in{\cal C}_{1}}z_{C}\leq O(\ln n+\ln M+\ln(k/\gamma))c_{u}.$

  * (ii)

The timestep $t$ lies in the interval $I_{u}^{\prime}=(b_{u},\tau_{u}]$, where
$u$ is a non-principal child of $v$ at timestep $\tau_{u}$. Denote the set of
such constraints by ${\cal C}_{2}=\\{C_{1},\ldots,C_{s}\\}$. For sake of
concreteness, let the interval $I_{u}^{\prime}$ in $C_{j}$ be
$I_{j}^{\prime}=(b_{j},\tau_{j}],$ and let $I_{j}$ denote the corresponding
$I_{u}$ interval. Observe that $\tau_{j}$ corresponds to a $\bot$-constraint
in $\mathcal{L}^{u}$, and so always remains in ${\sf Awake}(u)$. Let $q_{j}$
denote $\lfloor\tau_{j}\rfloor$. Note that any constraint in ${\cal C}_{2}$
must contain one of the variables $y^{v}(u,q_{j}+1),j\in[s]$, and each of
these variables belongs to the corresponding $I_{j}$ interval. So if $X$
denotes the set $\\{q_{j}:j\in[s]\\}$, then

$\displaystyle\sum_{C\in{\cal C}_{2}}z(C)\leq\sum_{t^{\prime}\in
X}\sum_{C\in{\cal C}_{1}(t^{\prime}+1)}z(C)\leq O(\ln n+\ln
M+\ln(k/\gamma))\cdot|X|\cdot c_{u},$ (25)

where the last inequality follows from case (i) above. It remains to bound
$|X|.$ We know from the Congestion Lemma I (Lemma 7.3) that the intervals
$(b_{j},q_{j}],q_{j}\in X,$ have congestion at most $H$. Since the intervals
$(q_{j},q_{j}+1],q_{j}\in X,$ are mutually disjoint, it follows that the
intervals $(b_{j},q_{j}+1]$ have congestion at most $H+1$. Since all of them
contain the timestep $t$, it follows that $|X|\leq H+1$. This shows that

$\sum_{C\in{\cal C}_{2}}z(C)\leq O(H(\ln n+\ln M+\ln(k/\gamma)))c_{u}.$

  * (iii)

The timestep $t$ lies in the interval $I_{u}^{\prime}=(b_{u},\tau]$, where
$u^{\prime}$ is the principal child of $u$ at timestep $\tau$: call such
constraints ${\cal C}_{3}$. For a time $q$, let ${\cal C}_{3}(q)$ be the
subset of constraints in ${\cal C}_{3}$ which were added at timesteps $\tau$
for which $\lfloor\tau\rfloor=q$. Claim 7.19 shows that

$\sum_{C\in{\cal C}_{3}(q)}z(C)\leq 4H\frac{c_{v}}{\lambda}=4H\,c_{u}.$

Arguing as in case (ii) above, and again using Congestion Lemma I (Lemma 7.3),
we see that there are at most $O(H)$ distinct time $q$ such that the set
${\cal C}_{3}(q)$ is non-empty. Therefore,

$\sum_{C\in{\cal C}^{F}}z(C)\leq O(H^{2})c_{u}.$

Let ${\cal C}$ be the set of all constraints containing $y^{v}(u,t)$.
Combining the observations above, and using Theorem 7.17 for the constraints
in ${\cal C}$ added due to the SimpleUpdate procedure, we see that

$\sum_{C\in{\cal C}}z(C)\leq\beta_{0}\,c_{u}.$

It remains to consider the variables $y^{v}(u^{\prime},\tau)$ with
$u^{\prime}\in T_{u}$ and $u\in\chi_{v}$. The argument here follows from
induction hypothesis, and is identical to the one in the proof of Lemma 5.19.
∎

###  7.8 The Final Analysis

We can now put the pieces together: this part is also very similar to §5,
except for the cost of the piggybacking trees. Recall that $\lambda\geq 10H$.

  1. 1.

Theorem 7.20 shows that the dual solution for the global LP (which is the same
as the $\mathfrak{L}^{\mathbbm{r}}$) is
$O(H^{4}+H\log\nicefrac{{Mnk}}{{\gamma}})$-feasible. In each iteration of the
while loop in Algorithm 4, we raise the dual objective corresponding to this
LP by $\gamma$ units, as Claim 7.11 shows.

  2. 2.

The total service cost in each call to the FullUpdate procedure is
$O(\gamma)$—again by Claim 7.11, the amount of server mass transferred during
FullUpdate procedure at vertex $v$ at height $h+1$ is at most
$\frac{\gamma}{\lambda^{h}}$, and the cost of moving a unit of server mass
below $T_{v}$ is $O(\lambda^{h})$. Therefore, the cost to service the critical
request in each iteration is $O(\gamma H)$. Therefore, the service cost for
each critical request is $O(H)$ times the dual objective value.

  3. 3.

Now we consider the service cost for piggybacked requests. The cost of all the
trees is dominated by the cost of tree for $v_{{\textsf{logcost}}(q)}$, i.e.,
at most

$O(H^{2}c_{v_{{\textsf{logcost}}(q)}})=O(H^{2}\;\lambda^{{\textsf{logcost}}(q)})\leq
O(H^{2}\lambda\;{\textsf{cost}}(q)).$

Since ${\textsf{cost}}(q)$ is the least cost to move the required amount of
server to the request location, the cost of the trees is at most
$O(H^{2}\lambda)$ times the cost incurred in the previous step.

Hence the competitiveness is

$O(H^{4}+H\log\nicefrac{{Mnk}}{{\gamma}})\cdot O(H)\cdot O(H^{2}\lambda).$

It follows that our fractional algorithm for the $k$-ServerTW problem is
$O(H^{4}\lambda(H^{3}+\log\nicefrac{{Mnk}}{{\gamma}}))$-competitive. This
proves Theorem 1.2.

##  8 Closing Remarks

Our work suggests several interesting directions for future research. Can our
LP extend to variants and generalizations of $k$-Server in the literature? One
natural candidate is the hard version of the $k$-taxi problem. Another
interesting direction is to exploit the fact that our LP easily extends to
time-windows. The special case of $k$-ServerTW where $k=1$ is known as _online
service with delay_. While poly-logarithmic competitive ratios are known for
this problem (and also follow from our current work), no super-constant lower
bound on its competitive ratio bound is known. On the other hand, a sub-
logarithmic competitive ratio is not known even for simple metrics like the
line. Can our LP (or a variant) bridge this gap?

More immediate technical questions concern the $k$-ServerTW problem itself.
For instance, can the competitive ratio of the $k$-ServerTW problem be
improved from $\operatorname{poly}\log(n,\Delta)$ to
$\operatorname{poly}\log(k)$? Another direction is to extend $k$-ServerTW to
general delay penalties. Often, techniques for time-windows extend to general
delay functions by reducing the latter to a prize-collecting version of the
time-windows problem. Exploring this direction for $k$-ServerTW would be a
useful extension of the results presented in this paper.

### Acknowledgments

AG was supported in part by NSF awards CCF-1907820, CCF-1955785, and
CCF-2006953. DP was supported in part by NSF awards CCF-1750140 (CAREER) and
CCF-1955703, and ARO award W911NF2110230.

## References

  * [AAA+09] Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor.  The online set cover problem.  SIAM J. Comput., 39(2):361–370, 2009.
  * [AAC+17] Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul M. Makhijani, Yuyi Wang, and Roger Wattenhofer.  Min-cost bipartite perfect matching with delays.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA, volume 81 of LIPIcs, pages 1:1–1:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
  * [ACK17] Yossi Azar, Ashish Chiplunkar, and Haim Kaplan.  Polylogarithmic bounds on the competitiveness of min-cost perfect matching with delays.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1051–1061, 2017.
  * [ACKT20] Yossi Azar, Ashish Chiplunkar, Shay Kutten, and Noam Touitou.  Set cover with delay - clairvoyance is not required.  In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 8:1–8:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [ACN00] Dimitris Achlioptas, Marek Chrobak, and John Noga.  Competitive analysis of randomized paging algorithms.  Theor. Comput. Sci., 234(1-2):203–218, 2000.
  * [AGGP17] Yossi Azar, Arun Ganesh, Rong Ge, and Debmalya Panigrahi.  Online service with delay.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 551–563. ACM, 2017.
  * [AT19] Yossi Azar and Noam Touitou.  General framework for metric optimization problems with delay or with deadlines.  In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 60–71. IEEE Computer Society, 2019.
  * [AT20] Yossi Azar and Noam Touitou.  Beyond tree embeddings - a deterministic framework for network design with deadlines or delay.  In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1368–1379. IEEE, 2020.
  * [AV16] Yossi Azar and Adi Vardi.  Dynamic traveling repair problem with an arbitrary time window.  In Klaus Jansen and Monaldo Mastrolilli, editors, Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Aarhus, Denmark, August 25-26, 2016, Revised Selected Papers, volume 10138 of Lecture Notes in Computer Science, pages 14–26. Springer, 2016.
  * [BBB+16] Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Lukasz Jez, Jiri Sgall, Nguyen Kim Thang, and Pavel Veselý.  Online algorithms for multi-level aggregation.  In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, pages 12:1–12:17, 2016.
  * [BBMN11] Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph Naor.  A polylogarithmic-competitive algorithm for the $k$-server problem.  In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 267–276, 2011.
  * [BBMN15] Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph Naor.  A polylogarithmic-competitive algorithm for the _k_ -server problem.  J. ACM, 62(5):40, 2015.
  * [BBN10] Nikhil Bansal, Niv Buchbinder, and Joseph Naor.  Metrical task systems and the _k_ -server problem on hsts.  In Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G. Spirakis, editors, Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I, volume 6198 of Lecture Notes in Computer Science, pages 287–298. Springer, 2010.
  * [BBN12a] Nikhil Bansal, Niv Buchbinder, and Joseph Naor.  A primal-dual randomized algorithm for weighted paging.  J. ACM, 59(4):19:1–19:24, 2012.
  * [BBN12b] Nikhil Bansal, Niv Buchbinder, and Joseph Naor.  Randomized competitive algorithms for generalized caching.  SIAM J. Comput., 41(2):391–414, 2012.
  * [BCL+18] Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Madry.  $k$-server via multiscale entropic regularization.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 3–16. ACM, 2018.
  * [BEY98] Allan Borodin and Ran El-Yaniv.  Online Computation and Competitive Analysis.  Cambridge University Press, New York, NY, USA, 1998.
  * [BFNT17] Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor, and Ohad Talmon.  _O_(depth)-competitive algorithm for online multi-level aggregation.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1235–1244, 2017.
  * [BG00] Yair Bartal and Eddie Grove.  The harmonic _k_ -server algorithm is competitive.  J. ACM, 47(1):1–15, 2000.
  * [BGMN19] Niv Buchbinder, Anupam Gupta, Marco Molinaro, and Joseph (Seffi) Naor.  $k$-servers with a smile: Online algorithms via projections.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 98–116. SIAM, 2019.
  * [BN09] Niv Buchbinder and Joseph (Seffi) Naor.  Online primal-dual algorithms for covering and packing.  Math. Oper. Res., 34(2):270–286, 2009.
  * [CKPV91] Marek Chrobak, H Karloof, T Payne, and S Vishwnathan.  New ressults on server problems.  SIAM Journal on Discrete Mathematics, 4(2):172–181, 1991.
  * [CL91] Marek Chrobak and Lawrence L Larmore.  An optimal on-line algorithm for k servers on trees.  SIAM Journal on Computing, 20(1):144–148, 1991.
  * [CL06] Béla Csaba and Sachin Lodha.  A randomized on-line algorithm for the _k_ -server problem on a line.  Random Struct. Algorithms, 29(1):82–104, 2006.
  * [CMP08] Aaron Cote, Adam Meyerson, and Laura J. Poplawski.  Randomized k-server on hierarchical binary trees.  In Cynthia Dwork, editor, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 227–234. ACM, 2008.
  * [EKW16] Yuval Emek, Shay Kutten, and Roger Wattenhofer.  Online matching: haste makes waste!  In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 333–344, 2016.
  * [FKL+91] Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel Dominic Sleator, and Neal E. Young.  Competitive paging algorithms.  J. Algorithms, 12(4):685–699, 1991.
  * [FRR94] Amos Fiat, Yuval Rabani, and Yiftach Ravid.  Competitive k-server algorithms.  J. Comput. Syst. Sci., 48(3):410–428, 1994.
  * [FRT04] Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar.  A tight bound on approximating arbitrary metrics by tree metrics.  J. Comput. Syst. Sci., 69(3):485–497, 2004.
  * [GKP20] Anupam Gupta, Amit Kumar, and Debmalya Panigrahi.  Caching with time windows.  In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1125–1138. ACM, 2020.
  * [GN14] Anupam Gupta and Viswanath Nagarajan.  Approximating sparse covering integer programs online.  Mathematics of Operations Research, 39(4):998–1011, 2014.
  * [Gro91] Edward F. Grove.  The harmonic online k-server algorithm is competitive.  In Cris Koutsougeras and Jeffrey Scott Vitter, editors, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, pages 260–266. ACM, 1991.
  * [KP95] Elias Koutsoupias and Christos H. Papadimitriou.  On the k-server conjecture.  J. ACM, 42(5):971–983, 1995.
  * [Lee18] James R. Lee.  Fusible HSTs and the randomized $k$-server conjecture.  In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 438–449. IEEE Computer Society, 2018.
  * [MMS90] Mark S. Manasse, Lyle A. McGeoch, and Daniel Dominic Sleator.  Competitive algorithms for server problems.  J. Algorithms, 11(2):208–230, 1990.
  * [MS91] Lyle A. McGeoch and Daniel Dominic Sleator.  A strongly competitive randomized paging algorithm.  Algorithmica, 6(6):816–825, 1991.
  * [Sei01] Steven S. Seiden.  A general decomposition theorem for the k-server problem.  In Friedhelm Meyer auf der Heide, editor, Algorithms - ESA 2001, 9th Annual European Symposium, Aarhus, Denmark, August 28-31, 2001, Proceedings, volume 2161 of Lecture Notes in Computer Science, pages 86–97. Springer, 2001.

##  Appendix A Relating $\mathfrak{M}$ to the Min-cost Flow Formulation for
$k$-Server

We show that the constraints (2) of the LP relaxation $\mathfrak{M}$ for
$k$-Server are implied by the standard min-cost flow formulation for
$k$-Server on HSTs.

We first describe the min-cost flow formulation in detail. Consider an
instance of the $k$-Server problem consisting of an HST $T$, and a sequence of
$N$ request times. Recall that the set of timesteps ${\mathcal{T}}$ varies
from $1$ to $N$ in steps of $\eta$. We construct a time-expanded graph $G$
with vertices $V(G):=\\{v_{t}\mid v\in
V(T),t\in{\mathcal{T}}\\}\cup\\{s_{G},t_{G}\\}$. The edges are of three types
(there are no edge-capacities):

  * (i)

cost-$0$ edges $\\{(s_{G},v_{1}),(v_{N},t_{G})\mid v\in V(T)\\}$ connecting
the source and sink to the first and last copies of each node,

  * (ii)

cost-$0$ edges $\\{(v_{t},v_{t+1})\mid v\in V(T),t\in{\mathcal{T}}\\}$ between
consecutive copies of the same vertex, and

  * (iii)

edges $\\{(v_{t},p(v)_{t})\mid v\in V(T),t\in{\mathcal{T}}\\}$ of cost $c_{v}$
between each node and its parent, and $\\{(v_{t},u_{t})\mid v\in
V(T),u\in\chi_{v},t\in{\mathcal{T}}\\}$ of cost zero between a node and its
children. (This captures that moving servers up the tree incurs cost, but
moving down the tree can be done free of charge.)

The source $s_{G}$ has $k$ units of supply, and sink $t_{G}$ has $k$ units of
demand (or equivalently, a supply of $-k$). If the request for time $q$ is at
leaf $\ell$, we require that at least one unit of flow passes through
$\ell_{q}$. To model this, we assign a supply of $-1$ to $\ell_{q}$ and $+1$
to $\ell_{q+1}$. This is consistent with the proof of Claim 2.1 where we
assumed that after servicing $\ell$ at time $q$, the server stays at this leaf
till time $q+1$.

The integrality of the min-cost flow polytope implies that an optimal solution
to this transportation problem captures the optimal $k$-server solution.
Moreover, the max-flow min-cut theorem says that if $x$ is a solution to this
transportation problem, then for all subsets $S\subseteq V(G)$,

$\displaystyle x(\partial^{+}(S))\geq{\mathsf{supply}}(S).$ (26)

We now consider special cases of these constraints. Consider a tuple
$(A,\boldsymbol{\tau})$ corresponding to the LP constraint (2): recall that
$A$ is a subset of leaves, and $\boldsymbol{\tau}$ assigns a timestep
$\tau_{u}$ to each $u\in T^{A}$, with these timesteps satisfying the
“monotonicity” constraints stated before (2). We now define a set
$S_{A,\boldsymbol{\tau}}$ as follows: for each node $v\in T^{A}$, we add the
nodes $v_{t},t>\tau_{v}$ to $S_{A,\boldsymbol{\tau}}$. Finally, add the sink
$t_{G}$ to $S_{A,\boldsymbol{\tau}}$ as well. Since each leaf in $A$
contributes $+1$ to the supply of $S_{A,\boldsymbol{\tau}}$, and $t_{G}$
contributes $-k$, we have ${\mathsf{supply}}(S_{A,\boldsymbol{\tau}})=|A|-k$.
Moreover,

$x(\partial^{+}(S_{A,\boldsymbol{\tau}}))=\sum_{v\neq\mathbbm{r}:v\in
T^{A}}x(v,(q_{v},q_{p(v)}]).$

Thus, constraint (26) for the set $S_{A,\boldsymbol{\tau}}$ is identical to
the covering constraint $\varphi_{A,\boldsymbol{\tau}}$ given by (2).