# Graph Integrated Language Transformers for Next Action Prediction in Complex
Phone Calls

Amin Hosseiny Marani and Ulrike Schnaithmann and Youngseo Son and
Akil Iyer and Manas Paldhe and Arushi Raghuvanshi
Infinitus Systems, Inc.
{amin.hosseiny, ulie.schnaithmann, youngseo.son, akil.iyer,
manas.paldhe<EMAIL_ADDRESS>

###### Abstract

Current Conversational AI systems employ different machine learning pipelines,
as well as external knowledge sources and business logic to predict the next
action. Maintaining various components in dialogue managers’ pipeline adds
complexity in expansion and updates, increases processing time, and causes
additive noise through the pipeline that can lead to incorrect next action
prediction. This paper investigates graph integration into language
transformers to improve understanding the relationships between humans’
utterances, previous, and next actions without the dependency on external
sources or components.

Experimental analyses on real calls indicate that the proposed Graph
Integrated Language Transformer models can achieve higher performance compared
to other production level conversational AI systems in driving interactive
calls with human users in real-world settings.

##  1 Introduction

Building and maintaining complex production quality conversational systems has
been an ongoing challenge in industry. One approach to solve complex
conversational tasks such as outbound call automation, is to use a dialogue
manager Paek and Pieraccini (2008); Teixeira et al. (2021) to encode business
logic. Conversational systems which use dialogue managers have multiple
components which consist of Natural Language Understanding (NLU) Bocklisch et
al. (2017), dialogue state tracking Mannekote (2023), next action prediction
Mannekote (2023), and response generation Weston et al. (2022); He et al.
(2018). Figure 1 describes the process of call automation systems with the
aforementioned components.

Figure 1: A schematic visualization of dialogue managers’ components which
utilize an NLU pipeline of models to extract intents and fill slots from human
utterances, and predict the next action based on the current and previous
state. Finally, the system generates an utterance to respond to the human
users (e.g., using LLMs or predefined templates).

Handling next action prediction is one of the critical tasks dialogue managers
take care of, as it affects the response generation directly David (2017).
Next action prediction is the process of analyzing human utterance, current
and previous state of the conversation (i.e., dialogue state tracking) and
deciding which action to take, which in many industry settings is returning a
specific response template. Figure 2 demonstrates an example of a dialogue
manager based conversation automation as a visual navigation assistant for
multiple dialogue turns.

Recently, there has been significant progress in the field of Generative AI
and Large Language Models (LLMs) for end-to-end conversational systems which
alleviate the need for manually engineered dialogue managers Mannekote (2023);
Snell et al. (2022). However, they sometimes have issues with hallucinations
and can underperform in domain specific, targeted conversations such as those
that require knowledge graph retrieval Dziri et al. (2021); Ji et al. (2023).

In most industry settings, templates are used with action prediction to
generate the response. By predicting an action, we are determining which
response template(s) to return to the user Mannekote (2023); Qiu et al.
(2022); Urbanek et al. (2019). Action prediction using response templates
instead of language generation helps prevent hallucinations, adds necessary
guardrails for some industry settings, and keeps latency low.

Figure 2: An example of Visual Navigation Assistant as a dialogue manager. At
each time-step $t$, the dialogue manager extracts the entities such as slots
and intents from human utterance $u_{t}$ (i.e.,  green rectangles on the left
side) and predicts the next action $a_{t}$ (i.e.,  red rectangles). Using the
predicted action (i.e.,  blue rectangles) the dialogue manager generates a
system response (i.e.,  green rectangles on the right side).

To solve the next action prediction problem, different NLP methods from
traditional symbolic AI techniques such as Knowledge Graph models He et al.
(2017); de Vries et al. (2018), to more modern transformer based techniques
(e.g., Zhou et al., 2023) have been introduced; however, two main challenges
still persist. 1) a majority of prior work depends on Slot-Filling (SF) and
Intent-Classification (IC) techniques to extract dependencies and relies on
external sources (i.e., knowledge or rule based approaches) to find the
relationship between the extracted information and actions Mannekote (2023);
David (2017). Instability in detecting SF and IC causes incorrect next action
prediction. 2) many conversational systems handle grounding poorly David
(2017); Weston et al. (2018); Sutskever et al. (2014); this is when users’
responses differ from expected inputs (e.g., referring to a previous point in
the conversation, moving backwards to change a previous response, or no
action-related slots being detected). For example, in Figure 2, the human user
sets a new ground by mentioning the elevator instead of the their location.
This information may be slightly different than what a next action prediction
model expects and can respond to. Lack of grounding in a conversation and more
specifically in a model may result in misunderstanding David (2017) and can
damage the conversation.

This paper introduces an approach to predict the next action without any
dependency on information extraction (i.e., SF and IC) or external resources
111The proposed model is trained using external resources but does not need
any external resources after training. such as ontology (e.g., Altinok, 2018)
or knowledge-base (e.g., Vizcarra and Jokinen, 2022) approaches. The proposed
models, Graph Integrated Language Transformers, learns co-occurrences of
actions and human utterances through a graph component (i.e., Graph Neural
Network or a graph embedding layer) and combines it with language transformers
to add language understanding in production settings. The model is trained on
conversations that followed a Standard Operating Procedure (SOP) 222SOP is a
document which defines a set of guideline instructions for diverse situations
during the conversations. without the need for explicit encoding. The proposed
model can be trained on any similar dataset that has an inherent action-to-
action relationships. The list below summarizes the contribution of this
paper.

  * •

Integrating graph information and combining with language transformers to
remove dependency on NLU pipelines.

  * •

Adding a graph component (i.e., history of action co-occurrence) to language
transformers to predict the next action as one atomic task while also
overcoming the token limit by removing the need to keep prior dialogue
history.

  * •

Evaluating the proposed next action prediction model in a production setting
against a system that relies on an NLU pipeline with an explicitly defined
dialogue manager (DM system) in Appendix A.

To examine the performance and robustness of the proposed models in real-world
settings with noisy input, the evaluation is done in a production setting and
goes beyond classification metrics; the evaluation includes industry critical
factors such as human experience using the conversational system and considers
real-time constraints such as latency of output generation.

##  2 Related Work

Next action prediction approaches can be categorized in three chief groups.
First, structured-based approaches that consider sequential relationships
between previous actions, other actions, and their requirements. These
approaches assume that the current state (i.e., the previous action) is known
Henderson (2015). On the one hand, local structure-based approaches such as
Question & Answer systems Reshmi and Balakrishnan (2016) consider local
adjacency of the actions, utterance features, and next potential actions.

On the other hand, global structured-based approaches define problem space
using dialogue-grammars or finite-state networks David (2017); Wollny et al.
(2021). However, none of structured-based approaches provide the ability to
train a model and they require expert to design them Henderson (2015).

The second group of next action prediction approaches are principle-based.
These techniques choose next actions based on the filled information rather
than sequential order between actions, thus behaving both locally and globally
David (2017).

Slot-filling (SF) and Intent-classification (IC) based techniques (i.e.,
joined or separate components) are common principle based approaches Louvan
and Magnini (2020).

Recently, neural models including RNNs and Language Transformers which act
solely on input are receiving more attention for SF-IC based techniques Goo et
al. (2018); Chen et al. (2019); Zhang and Wang (2022). These methods are
mainly using dialogue history alongside additional information such as schema
of the task (e.g., “hotel booking” or “scheduling a doctor’s appointment”)
e.g., using embedding layers with or without attention layers fused with a
language transformer (e.g., Mosig et al., 2020; Mehri and Eskenazi, 2021;
Zhang et al., 2021).

However, most of these language transformer based techniques were only
evaluated on datasets with low number of actions, 10 or less Mosig et al.
(2020); Rastogi et al. (2020), or perform poorly on larger number of actions
(i.e., 30 actions) for one top output selection Chen et al. (2021).

##  3 Methodology

This section discusses the problem definition of the next action prediction
task (i.e., Section 3.1), and introduces the proposed models (i.e., Section
3.2).

###  3.1 Problem Definition

A next action prediction model chooses an action $a_{t}$ given $U_{k:t}$ and
$Z_{k:t-1}$ at time $t$ in which $U$ is the set of all utterances from time
$k$ (i.e., $k\geq 0$) to time $t$, and $Z$ is the set of all previously
predicted acts. Equation 1 formulates the process of next action prediction.
In this equation, $f$ denotes any function (e.g., machine learning model or a
probabilistic matching technique) that can map thereof inputs to the next
action.

$a_{t}=f([U_{k:t},Z_{k:t-1}])~{}~{}~{}s.t.~{}~{}~{}0\leq k\leq t-1$ (1)

Different techniques approach next action prediction differently. Some
techniques rely on feature extraction from utterances (i.e., $U_{k:t}$) using
NLU techniques (e.g., intents or slots in NLU pipeline of Figure 1); in those
cases $U_{t}$ in Equation 1 becomes utterance and all those extracted features
at time $t$. However, this paper proposes a method that relies only on the
very last human utterance and previous actions in Section 3.2.

###  3.2 Graph Integrated Language Transformers

This paper proposes a graph integrated approach to employ the rich information
of graph-like structures, discussed in Section 2 (e.g., SOP, graphs, or rule
knowledge bases) and combine it with language transformers. Two different
techniques are proposed in this section that each combine language
transformers with 1) Graph Neural Networks (GNN) to explicitly encode the
graph of actions and other features (GNN-LT), and 2) a graph embedding layer
to learn co-occurrences of action history, Graph-aware Language Transformer
(GaLT).

Both models additionally use language transformers such as BERT Devlin et al.
(2018), DistilBERT Sanh et al. (2019), or RoBERTa Liu et al. (2019) to add
language understanding Devlin et al. (2018) to the next action prediction. The
GNN-LT models is fed past actions as nodes and features of nodes’ connections
as edges (i.e., order of the connections, slots, and embedding of the
utterance) using a Graph Attention Network Yun et al. (2019). Thus, GNN-LT
explicitly integrates the graph knowledge including the order of the actions
and their connections. GaLT employs a graph embedding layer that encodes past
actions as node labels directly without the past action names or utterances;
therefore implicitly adds the ability to learn the co-occurring utterances and
actions without the need to explicitly enforce graph constraints (i.e.,
actions as nodes, filled slots or other features as edges). Additionally, GaLT
acquires fewer training parameters (e.g., $66M$ Distilbert + $1M$ fusion and
fully connected layer = $67M$ in total) in comparison to GNN-LT (e.g., $66M$
Distilbert + $12M$ Graphormer small Yun et al. (2019) \+ $1M$ fusion and fully
connected layer = $79M$ in total); therefore, GaLT requires less training time
and performs much faster in inference.

The language transformer is fed the human utterance alongside the history of
actions to implicitly learn the co-occurrence between human responses and
follow-up actions taken by the system. Additionally, the language transformer
is pre-trained on a much larger dataset of full dialogue turns to learn the
context of the utterances and their co-occurring actions. As the dialogue
history is removed from the graph integrated language transformer training
process, the model is incentivised to focus on action co-occurrence and
sequences as graph nodes rather than the dialogue history surrounding them.

Keeping only actions as the history of the dialogues (i.e., both in language
transformer and graph components) removes dependency to the NLU pipeline
(i.e., discussed in Section 1 and 2) and the need to keep the dialogue turns’
utterances; thus improving speed of prediction and satisfying the language
transformer token limit; e.g., 512 for DistilBERT Sanh et al. (2019); Devlin
et al. (2018). Due to the simplicity of the model, real time inference time
requirements are still being met. Figure 3 shows a schematic of the proposed
models.

Figure 3: The architecture of the GaLT model (i.e., left figure) and GNN-LT
(i.e., right figure). GaLT is fed action history as graph embedding and GNN-LT
is fed actions as nodes as well as utterance features as edges; each models
then is fused with a language transformer. $L1$ denotes the number of layers
in GNN and $L_{2}$ denotes the layers of the language transformer.

A fusion layer combines both language transformer and graph component features
using Equations 2-4. First, Equation 2 computes mean of the hidden features
from the language transformer and Equation 3 computes the features of the
graph component. Here, $W$ and $b$ are trainable parameters, $O$ is the output
of a layer, $l$ and $g$ denote the language transformer and graph component.
Then, the fused features will be fed into a fully connected layer to predict
the next action. Equation 4 fuses the hidden features of both layers and
generates the probability using the $Softmax$ activation layer. The next
action will be picked from the list of all actions with respect to their
probability of the computed Softmax output. While there are variety of fusion
techniques (e.g., concatenation, dot product techniques, or summation
techniques), Equation 4 uses $\otimes$; since GaLT and GNN-LT reach to the
highest performance via pairwise dot product fusuion.

$H_{l}=GELU(W_{l}~{}~{}mean(O_{l})+b_{l})$ (2)

$H_{g}=GELU(W_{g}O_{g}+b_{g})$ (3)

$H_{f}=Softmax(W_{f}(H_{l}\otimes H_{g})+b_{f})$ (4)

##  4 Experimental Setup and Results

This section describes the process of collecting data for training the models,
comparing the trained models regarding classification metrics (i.e., $F1$),
and evaluating the proposed models as well as the DM system333The current
production system that is handling the call automation at the time is called
DM system throughout this paper., explained in detail in Appendix A, using a
human-centered approach.

###  4.1 Data, Configurations, and Training

To integrate the graph information into GNN-LT and GaLT models, this work
utilizes conversational data which follows a Standard Operating Procedure
(SOP). These conversations were guided by a human expert or the DM system
which employs a human defined SOP. The SOP is a graph like structure with
actions as nodes and their connections to next actions based on filled slots,
which has been carefully translated into dialogue manager logic. Appendix B
discuss the SOP in more details. However, the proposed Graph Integrated
Language Transformers were not trained on the SOP explicitly. GaLT and GNN-LT
were trained on the data human experts and the DM system collected and
generated from the SOP.

To evaluate the proposed models, dialogue turns of phone calls between human-
AI and human-human were collected from June to August 2023.

The next action for each human dialogue turn was decided and labeled by the DM
system with human in the loop supervision. Human domain experts intervened in
calls that might fail. The intervention varied from correcting the collected
data (e.g., spelling mistakes) to driving the calls in severe cases. To
generate a reliable dataset, a team of human experts classified each
conversation as successful or unsuccessful on a call level, rather than
labeling and reviewing each dialogue turn, due to financial reasons and
limited human resources. For the same reason, all of dialogue turns for each
call are added to the dataset if it was considered successful 444If the model
managed to prompt the human user to give all information required or was
dropped otherwise. That resulted in $\sim 1M$ records each including one human
utterance and one system response. In addition to selecting successful calls,
a pre-processing step (described in Appendix C), is devised to remove
undesirable dialogue turns, calls, or actions; e.g., actions that are
deprecated and the rest of the call to avoid incorrect connection between
actions. This process led to $\sim 600K$ remaining dialogue turns.

Despite filtering out $\sim 400k$ dialogue turns, the language transformers
were initially pre-trained on all dialogue turns (i.e., $\sim 1M$) using
Masked Language Modeling (MLM) Devlin et al. (2018) and then fine-tuned on
$\sim 600K$ selected dataset for the next action prediction task. The dataset
was randomly split to 80%-10%-10% for training, validation, and test. Section
D summarizes the details of the dataset. Additionally, Section E and Section F
lists the system configurations and proposed models’ hyper-parameters for
training and testing the models.

###  4.2 Classification Performance Comparison

This section evaluates the proposed models and other techniques using an
offline classification evaluation. The process evaluates each technique’s
performance on the turn-level; next action given a human user’s utterance and
the previous actions or dialogue history. To measure the performance for each
model, F1 Score was computed on the test-set described in Section 4.1.

Table 1 compares the proposed models with other techniques. The dataset,
described in Appendix D, consists of 80 next actions (i.e., classes) of
imbalanced frequency; thus $F1_{Macro}$ was calculated alongside
$F1_{weighted}$. The results suggest that stand-alone models (i.e., language
transformers or GNNs) and prompt-based large language models 555This paper
also evaluates a prompting only approach using Llama2
(https://ai.meta.com/llama) on the same task and dataset; however, the results
are not reported due to poor results in comparisons with other models. The
prompt that is used to generate outputs as well as the results are discussed
in Appendix G. are not able to predict the next action with high performance
(i.e., lower $F1_{macro}$). Moreover, this table shows adding the graph
embedding of actions in GaLT can improve $F1$ for next action prediction more
than combining complex GNN models. GaLT also can reach to its high performance
with as little as $60K$ dialogue turns(i.e., 10% data size) as described in
Appendix H.

###  4.3 Human-Centered Evaluation

Model | $F1_{Weighted}$ | $F1_{Macro}$
---|---|---
BERT w/ dialogue history Mosig et al. (2020) | 0.58 | 0.38
BERT w/ SF Zhang et al. (2021) | 0.79 | 0.44
BERT w/ action history | 0.80 | 0.63
DistilBERT w/ action history | 0.82 | 0.69
RoBERTa w/ action history | 0.78 | 0.60
GNN Yun et al. (2019) | 0.72 | 0.52
(sub)*GNN Yun et al. (2019) | 0.72 | 0.51
GNN-LT(DistilBERT) | 0.84 | 0.72
(sub)*GNN-LT(DistilBERT) | 0.84 | 0.72
GaLT | 0.84 | 0.75
*sub-GNN models are fed only recent actions
(e.g., last 5 or 10).
Table 1: Summary of offline classification evaluation across different
techniques regarding $F1$. Four categories of models were listed in this
table; language transformers (e.g., BERT) with dialogue history or detected
filled slots, language transformers with last utterance and recent history of
actions (e.g., 5 or 10 last actions), GNN model, and Graph Integrated language
transformers (e.g., GNN or graph embedding). The underscore values show the
best performance regarding each metric (i.e., columns).

This section evaluates the best performing model, GaLT, with the DM system
using a human-centered approach since the desired outcome of a call can be
achieved through various paths and does not need to be strictly tied to one
correct next action (i.e., what was done in Section 4.2). Put precisely, more
than one next action can be considered as a correct prediction given the
recent actions and the current utterance. To compare GaLT with the DM system,
human assessors acted the “role” of the agent receiving outbound calls. They
were familiar with the call structure and expected outcome of calls. Two
different approaches were designed to compare and evaluate the models;
objective product-level and human subjective. Additionally to test the
generalizability and robustness of the compared models three call difficulty
levels were defined; easy, medium, and hard (i.e., Table 7). As the call
difficulty level increases human utterances and provided information get more
complex (e.g., mumbling or updating a piece of information). The experimental
setup and metrics are described in more detail in Appendix I.

#### Production Level Metrics

Table 2 shows that the proposed models outperforms the DM system regarding
both field number (i.e., how much information the call collected) and panel
number 666Panel number indicates the progress a model is made into finishing a
call. Panel 0,1,2,3,4, and E2E indicate 0%, 20%, 40%, 60%, 80%, and 100%
progress of a call respectively. (i.e., how far to the end of the call model
reached). T-test statistics analysis suggests that the comparisons were
significant for medium level as well as all levels combined (i.e., ‘.’ and ‘*’
symbols for each pair in Table 2). In addition to the panel number, finishing
a call successfully (e.g., collecting all information or without human user
hanging up) is another important metric (i.e., E2E metric). GaLT also improved
the E2E or number of successfully finished calls by +31.92% (Appendix J shows
an extensive comparison).

Difficulty | #Fields Mean (std) | #Panels Mean(std)
---|---|---
Level |  DM system |  Proposed |  DM system |  Proposed
Easy |  23.1(6.59) |  25.35(6.19) |  3.85(0.65) |  4.0(0.0)
Medium |  18.36(9.23). |  23.3(4.45). |  3.05(1.39)** |  (4.0)0.0**
Hard |  18.25(5.49) |  21.44(5.98) |  3.63(0.99) |  3.66(0.94)
Total |  20.36(7.97)* |  23.79(5.70)* |  3.48(1.13)* |  3.93(0.42)*
Note: .p<0.1, *p<0.05, **p<0.01, ***P<0.001
Table 2: Comparing the DM system and proposed models performance regarding
product-level metrics, number of fields and panels, across different
difficulty levels. The results of t-test are shown as stars (‘*’) or dots
(‘.’)

#### Subjective Human Evaluation

Additionally, Human agents (i.e., human users who interacted with the models)
and reviewers rated each call after finishing that call as described in
Appendix I using a 5-point Likert scale rating. The GaLT model received a
higher rating average of 2.91 ($std=1.15$) in comparison to rating average of
2.78 ($std=1.42$) for the DM system. Comparing the number of positive and
negative ratings for each model shows that both models received almost same
number of positive ratings but the DM system received higher number of
negative ratings. In other words, human assessors rated the proposed models to
be more robust. A deeper investigation regarding difficulty levels is done and
discussed in Section K.

##  5 Conclusion

This paper proposes Graph Integrated Language Transformers technique to
improve next action prediction performance to resolve the dependency on Slot-
Filling and Intent-Classification techniques and grounding issue Mannekote
(2023). The analyses indicate that keeping the action history with order of
the actions using a graph embedding layer and combining with language
transformers generates higher quality of outputs in comparison to more complex
models that include connection details of actions (i.e, GNNs including the
connection details through edges). The proposed model(s) improve the next
action prediction regarding $F1$ as well as product-level metrics and human-
centered evaluation. They can improve the robustness regarding next action
prediction (e.g., less unexpected results or being stuck in a loop) in
comparison to other techniques and handle complex tasks better in comparison
to the DM system in long noisy phone calls. Additionally, the proposed models
can reach to a high performance level with as low as $60K$ dialogue turns. We
hope future research can employ a similar method combined with generative AI
models to extract the information from human utterances as well as generating
custom responses to automate calls without dependency on other components.

## Limitations

Although the proposed models can reach to a high performance with as little as
$60K$ dialogue turns, it needs re-training or fine-tuning for any new
application in a new domain or even with slightest changes; e.g., adding or
removing even one action. Moreover, similar to other neural models, graph
integrated language transformers, lack interpretability and may show
instability (e.g., predict an action that does not have any relationship to
dialogue history).

In addition to these limitations, the evaluation can benefit from further
investigation. This paper recruits human agents and employees who were
familiar with the DM system. That can lead to a biased assessment and perhaps
is the source of inconsistency between human subjective rating and product-
level metrics.

Finally, there are next steps to further evaluate graph injection with
additional third party GenAI prompt based models. The ability to use certain
third party systems was limited at the time of evaluation due to the
requirement for this healthcare dataset to stay HIPAA compliant.

## References

  * Altinok (2018) Duygu Altinok. 2018.  An ontology-based dialogue management system for banking and finance dialogue systems.  _arXiv preprint arXiv:1804.04838_.
  * Bocklisch et al. (2017) Tom Bocklisch, Joey Faulkner, Nick Pawlowski, and Alan Nichol. 2017.  Rasa: Open source language understanding and dialogue management.
  * Chen et al. (2021) Derek Chen, Howard Chen, Yi Yang, Alexander Lin, and Zhou Yu. 2021.  Action-based conversations dataset: A corpus for building more in-depth task-oriented dialogue systems.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 3002–3017.
  * Chen et al. (2019) Qian Chen, Zhu Zhuo, and Wen Wang. 2019.  Bert for joint intent classification and slot filling.  _arXiv preprint arXiv:1902.10909_.
  * David (2017) Traum David. 2017.  Computational approaches to dialogue.  In _The Routledge Handbook of Language and Dialogue_ , pages 143–161. Routledge.
  * de Vries et al. (2018) Harm de Vries, Kurt Shuster, Dhruv Batra, Devi Parikh, Jason Weston, and Douwe Kiela. 2018.  Talk the walk: Navigating grids in new york city through grounded dialogue.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Dziri et al. (2021) Nouha Dziri, Andrea Madotto, Osmar R Zaiane, and Avishek Joey Bose. 2021.  Neural path hunter: Reducing hallucination in dialogue systems via path grounding.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 2197–2214.
  * Goo et al. (2018) Chih-Wen Goo, Guang Gao, Yun-Kai Hsu, Chih-Li Huo, Tsung-Chieh Chen, Keng-Wei Hsu, and Yun-Nung Chen. 2018.  Slot-gated modeling for joint slot filling and intent prediction.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 753–757.
  * He et al. (2017) He He, Anusha Balakrishnan, Mihail Eric, and Percy Liang. 2017.  Learning symmetric collaborative dialogue agents with dynamic knowledge graph embeddings.  _arXiv preprint arXiv:1704.07130_.
  * He et al. (2018) He He, Derek Chen, Anusha Balakrishnan, and Percy Liang. 2018.  Decoupling strategy and generation in negotiation dialogues.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 2333–2343, Brussels, Belgium. Association for Computational Linguistics.
  * Henderson (2015) Matthew S Henderson. 2015.  _Discriminative methods for statistical spoken dialogue systems_.  Ph.D. thesis, University of Cambridge.
  * Ji et al. (2023) Ziwei Ji, Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Ye Jin Bang, Andrea Madotto, and Pascale Fung. 2023.  Survey of hallucination in natural language generation.  _ACM Computing Surveys_ , 55(12):1–38.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Louvan and Magnini (2020) Samuel Louvan and Bernardo Magnini. 2020.  Recent neural methods on slot filling and intent classification for task-oriented dialogue systems: A survey.  _arXiv preprint arXiv:2011.00564_.
  * Mannekote (2023) Amogh Mannekote. 2023.  Towards a neural era in dialogue management for collaboration: A literature survey.  _arXiv preprint arXiv:2307.09021_.
  * Mehri and Eskenazi (2021) Shikib Mehri and Maxine Eskenazi. 2021.  Schema-guided paradigm for zero-shot dialog.  In _Proceedings of the 22nd Annual Meeting of the Special Interest Group on Discourse and Dialogue_ , pages 499–508.
  * Mosig et al. (2020) Johannes EM Mosig, Shikib Mehri, and Thomas Kober. 2020.  Star: A schema-guided dialog dataset for transfer learning.  _arXiv preprint arXiv:2010.11853_.
  * Paek and Pieraccini (2008) Tim Paek and Roberto Pieraccini. 2008.  Automating spoken dialogue management design using machine learning: An industry perspective.  _Speech communication_ , 50(8-9):716–729.
  * Qiu et al. (2022) Liang Qiu, Yizhou Zhao, Yuan Liang, Pan Lu, Weiyan Shi, Zhou Yu, and Song-Chun Zhu. 2022.  Towards socially intelligent agents with mental state transition and human value.  In _Proceedings of the 23rd Annual Meeting of the Special Interest Group on Discourse and Dialogue_ , pages 146–158.
  * Raghuvanshi et al. (2018) Arushi Raghuvanshi, Lucien Carroll, and Karthik Raghunathan. 2018.  Developing production-level conversational interfaces with shallow semantic parsing.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 157–162.
  * Rastogi et al. (2020) Abhinav Rastogi, Xiaoxue Zang, Srinivas Sunkara, Raghav Gupta, and Pranav Khaitan. 2020.  Towards scalable multi-domain conversational agents: The schema-guided dialogue dataset.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 34, pages 8689–8696.
  * Reshmi and Balakrishnan (2016) S Reshmi and Kannan Balakrishnan. 2016.  Implementation of an inquisitive chatbot for database supported knowledge bases.  _sādhanā_ , 41:1173–1178.
  * Sanh et al. (2019) Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. 2019.  Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter.  _arXiv preprint arXiv:1910.01108_.
  * Snell et al. (2022) Charlie Snell, Sherry Yang, Justin Fu, Yi Su, and Sergey Levine. 2022.  Context-aware language modeling for goal-oriented dialogue systems.  In _Findings of the Association for Computational Linguistics: NAACL 2022_ , pages 2351–2366, Seattle, United States. Association for Computational Linguistics.
  * Sutskever et al. (2014) Ilya Sutskever, Oriol Vinyals, and Quoc V Le. 2014.  Sequence to sequence learning with neural networks.  _Advances in neural information processing systems_ , 27.
  * Teixeira et al. (2021) Milene Santos Teixeira, Vinícius Maran, and Mauro Dragoni. 2021.  The interplay of a conversational ontology and ai planning for health dialogue management.  In _Proceedings of the 36th annual ACM symposium on applied computing_ , pages 611–619.
  * Urbanek et al. (2019) Jack Urbanek, Angela Fan, Siddharth Karamcheti, Saachi Jain, Samuel Humeau, Emily Dinan, Tim Rocktäschel, Douwe Kiela, Arthur Szlam, and Jason Weston. 2019.  Learning to speak and act in a fantasy text adventure game.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 673–683, Hong Kong, China. Association for Computational Linguistics.
  * Vizcarra and Jokinen (2022) Julio Vizcarra and Kristiina Jokinen. 2022.  Knowledge-based dialogue system for the ageing support on daily activities.  In _International Conference on Human-Computer Interaction_ , pages 122–133. Springer.
  * Weston et al. (2022) Jack Weston, Raphael Lenain, Udeepa Meepegama, and Emil Fristed. 2022.  Generative pretraining for paraphrase evaluation.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 4052–4073, Dublin, Ireland. Association for Computational Linguistics.
  * Weston et al. (2018) Jason Weston, Emily Dinan, and Alexander H Miller. 2018.  Retrieve and refine: Improved sequence generation models for dialogue.  _arXiv preprint arXiv:1808.04776_.
  * Wollny et al. (2021) Sebastian Wollny, Jan Schneider, Daniele Di Mitri, Joshua Weidlich, Marc Rittberger, and Hendrik Drachsler. 2021.  Are we there yet?-a systematic literature review on chatbots in education.  _Frontiers in artificial intelligence_ , 4:654924.
  * Yun et al. (2019) Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J Kim. 2019.  Graph transformer networks.  _Advances in neural information processing systems_ , 32.
  * Zhang and Wang (2022) Jing Zhang and Yujin Wang. 2022.  SRCB at SemEval-2022 task 5: Pretraining based image to text late sequential fusion system for multimodal misogynous meme identification.  In _Proceedings of the 16th International Workshop on Semantic Evaluation (SemEval-2022)_ , pages 585–596, Seattle, United States. Association for Computational Linguistics.
  * Zhang et al. (2021) Yang Zhang, Vahid Noroozi, Evelina Bakhturina, and Boris Ginsburg. 2021.  Sgd-qa: Fast schema-guided dialogue state tracking for unseen services.  _arXiv preprint arXiv:2105.08049_.
  * Zhou et al. (2023) Pei Zhou, Andrew Zhu, Jennifer Hu, Jay Pujara, Xiang Ren, Chris Callison-Burch, Yejin Choi, and Prithviraj Ammanabrolu. 2023.  I cast detect thoughts: Learning to converse and guide with intents and theory-of-mind in dungeons and dragons.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 11136–11155.

##  Appendix A Conversational Systems’ Next Action Prediction Process

Figure 4: Overview of next action prediction process in a conversational AI
system. The dialogue manager logic is generated using previous dialogues and
via NLU pipeline (e.g., SF and IC). The model predicts next action using
incoming utterances, NLU pipeline, and the generated knowledge. The arrows in
the image show the connections between data, NLU pipeline, and dialogue
manager logic during training (i.e., straight lines) or prediction during
production (dotted lines).

Figure 4 shows a schematic overview of how a next action prediction model is
employed in conversational AI systems. Although different conversational AI
systems may use different approaches for NLU analysis or dialogue manager
logic, most of the current approaches still use similar mechanism (e.g.,
Mannekote, 2023; Bocklisch et al., 2017; Raghuvanshi et al., 2018).

##  Appendix B Standard Operating Procedure

The DM system described in Appendix A employs a human defined Standard
Operating Procedure (SOP) to guide the conversation based on the last action
and conversational context of past slots filled. For example, one of the
questions asked by the AI system is "Is this a commercial or government plan?"
Depending on the type of plan different paths have to be followed. If it is a
government plan, the AI system should ask "Is this Medicare, Medicaid, or
Tricare?". If it is a commercial plan, the AI system should next ask about the
Rx Number. If the Rx number is the same as a previously provided policy
number, the AI system should push back to clarify "Just to confirm, the RX
group number and the policy number are the same?". Similarly, throughout the
conversation these types of guidelines are defined which are necessary for
collecting accurate information in these healthcare calls. Depending on the
information provided so far on the call, the SOP may require different
confirmations and followup loops similar to the above example.

##  Appendix C Data Preprocessing

The data preprocessing resulted in $>593K$ records each including one human
utterance, the previous and next action as well as the system response.
Through preprocessing, three types of records were removed from the dataset:

  * •

records with rare or obsolete 777No longer has been used in the DM system next
actions and the rest of the call: A low number of next actions, $N~{}10$, only
appeared less than 50 times across the dataset due to different reasons (e.g.,
getting merged or updated). While the preprocessing kept the dialogue history
up to that moment, the rest of dialogue was dropped since lack of prior
information (i.e., deleted records) can be misleading for a next action
prediction model.

  * •

records with filler actions such as wait, just a moment, or repeat last
sentence : The preprocessing also dropped these records and actions because,
filler actions 1) do not add any meaningful instructions to the graph
structure and 2) do not need dialogue history or previous actions to be
detected.

The preprocessing also dropped these for the same reasons stated for waiting
actions above.

In addition to these steps, utterances split into fragments (i.e., multiple
dialogue turns with one same next action) were merged to form one record with
one desired next action.

Although, it is important to handle edge cases such as incomplete sentences
for a conversational AI system in call automation, managing those are less
relevant to the next action prediction models. Moreover, the proposed models
handled incomplete sentences well during evaluation.

##  Appendix D Dataset Details

This section summarizes the details of the dataset regarding number of calls
and dialogue turns in Table 3 as well as actions and panels in Table 4.

Calls | 21,220
---|---
Dialogue Turns | 593,156
Average Turns per call | 27.95
Average Tokens per Call | 544.16
Average Tokens per Turn | 19.47
Table 3: Summary of the dataset regarding number of calls, human utterances (i.e., dialogue turns), and tokens. Panel | Progress | Actions | Dialogue Turns (%)
---|---|---|---
0* | 0% | 17 | 313214(53%)
1 | 20% | 39 | 43,095(7%)
2 | 40% | 4 | 135,52(2%)
3 | 60% | 4 | 166,068(28%)
4 | 80% | 20 | 57,227(10%)
Total | - | 80 | 593,156(100%)
*Panel 0: Authentication; finishing a call at this panel
means the call has failed.
Table 4: Summary of actions and dialogue turns per panels.

##  Appendix E System Configurations

The experiments in this paper including training and testing phases were done
by two Computing Engines of the Google Cloud Platform; One including two
“NVIDIA T4 16 GB Memory” GPUs and the other including a “NVIDIA A100 40 GB
Memory” GPU. “T4” GPUs were used to train the MLM and GaLT models as well as
other language transform approaches while the “A100” unit was used for GNN
based approaches as they needed more memory.

##  Appendix F Models’ Hyper-parameteres

Table 5 lists the parameters and their values for training the proposed model.

Parameter | Value (GaLT/MLM)
---|---
Epochs | 3/30
Batch Size | 256/512
Optimizer | AdamW/AdamW
Max. Learning Rate | 5e-5/5e-5
Learning Rate Policy | linear/linear
Warmup steps | 250/250
Max. Input Sequence Length | NA/128
Masking Probability | NA/15%
Table 5: List of hyper-parameters the proposed models was trained on. Figure
5: A sample snippet of the prompt input that is fed to the Llama2. Each Action
has a name and a description that includes a Golang code on how the
requirements of a next action is met. The prompt follows by the dialogue
history and the task to generate response for.

##  Appendix G Prompting Llama2

To evaluate the performance of Prompt Engineering on Large Language Models,
Llama 2 was chosen as it was one of the few available ones at the time of
experiments that had the proper HIPAA compliance requirements in place which
is a requirement for this healthcare dataset to stay PHI compliant
888https://www.hhs.gov/answers/hipaa/what-is-phi/index.html. The prompt
included basic instructions on the task and the dialogue history between user
(i.e., agent) and system (i.e., user). The model was evaluated on the same
dataset and achieved an $F1$ score of 0.09. Figure 5 shows a sample snippet of
the prompt; it is customized for each request. The contextual information
supplied in the prompt included basic instructions, the last actions of
dialogue history (i.e., up to 10 turns), a list of next actions and their
descriptions. To reduce prompt size and restrict the action search space, the
prompt included only a subset of potential next actions. This list was
determined by their observed co-occurrence in the dataset. All next actions
were included if there were up to 10 co-occurring actions. For cases where
there were more than 10, as many actions as required to add up to a cumulative
sum of 50% were added to the set.

##  Appendix H Data Size Effect

Table 6 shows the effect of training size on the proposed models performance.
It suggests having $60K$ training data is almost enough to train GaLT to
perform close to its best.

Train Size (%) | $F1_{Weighted}$ | $F1_{Macro}$
---|---|---
5,930 (1%) | 0.52 | 0.29
11,860 (2%) | 0.75 | 0.59
59,300 (10%) | 0.82 | 0.69
296,500 (50%) | 0.84 | 0.72
593,156 (100%) | 0.84 | 0.75
Table 6: Effect of training size on the proposed model, GaLT, performance.

Figure 6: Percentage of calls reaching to each panel for the DM system (i.e.,
left figure) and the proposed models (i.e., right figure). There were 4 panels
and end of a call (i.e., E2E) during a call and each model managed to finish
only at panel 1, 4, or E2E due to lower number of actions in panel 2 and 3.

##  Appendix I Human-centered Evaluation Setup

A call is considered successful if the conversational AI system was able to
prompt the recipient of the call to provide all information fields required
for completion of the task. Therefore, the number of fields gathered by the
system is a direct measure of call success. The outbound call is structured
into panels (i.e., panel number) which indicate how far into the conversation
the system was able to navigate before call breakdown or completion.
Therefore, both of these objective metrics indicate better performance the
higher they are. This paper computes both of these metrics as objective
metrics.

Additionally, after finishing a call, the human agent is asked to rate the
call from 1-5 (i.e., 1 being extremely dissatisfied and 5 extremely satisfied)
using a Likert scale. In addition to that, two additional human experts review
both the objective and subjective assessment. Both the human agent and the
reviewers answer an open-ended question of how they describe their experience
with the system at the end of the process.

To make sure the evaluation is not handled in error-free, lab settings but
more similar to real-world settings, different levels of difficulties were
defined and considered for each call (e.g., background noise or repeated
expressions). Three difficulty levels were defined (i.e., hard, medium, and
easy) and each level consisted of a minimum-maximum number of scenarios
challenges described in Table 7.

Scenario | Level
---|---
| Easy | Medium | Hard
Agent | 0-1 | 2-3 | 4-5
Flow | 0-1 | 2-3 | 4-5
Table 7: Summary of how each difficulty level is made from agent and flow
scenarios for calls. Human agents were assigned a difficulty level and could
pick a number in the given range of the available scenarios to act out for
their call. For each call difficulty level both agent and flow scenarios were
picked from the same level.

Two types of scenarios were defined; agent and flow scenarios. The agent
scenarios (i.e., 5 conditions) are challenges regarding human users’
performance during a call such as mumbling, background noise or repeated
expressions. The flow scenarios (i.e., 6 conditions) are specific conditions
and edge cases which increase the complexity of the conversation and the
information required to be collected to complete the task. For each level,
both agent and flow scenarios are selected from the same difficulty level.

##  Appendix J Extended Results of Product-level Metrics

E2E metrics shows the proportion of calls a model can finish successfully. Put
differently, reaching to panel 4 alone is not the desired goal but reaching to
E2E is the main goal of the call automation task. A comparison between the “DM
sytem” and the proposed models in Figure 6 shows that the proposed models are
perfect (i.e., 100% E2E reach) in easy and medium difficulties. However, the
DM system was only able to finish 90% of the easy and 70% of medium calls. The
proposed models also managed to finish $78\%$ of calls successfully with hard
difficulty whereas the DM system were able to finish $62\%$ of calls.

##  Appendix K Extended Results of Subjective Human Evaluation

Figure 7 shows the distribution of the ratings regarding each model. The ”DM
system“ received negative ratings (i.e., strongly negative) twice as much as
the proposed model.

Figure 7: Distribution of human evaluation ratings for calls managed by the DM
system and proposed model.  Figure 8: Violin plot of distribution for human
evaluation rating regarding difficulty levels.

Figure 8 shows the distribution of the models regarding the human ratings
using a violin plot. The DM system performed better regarding human assessment
across easy difficulty
($M_{Current}=3.48>M_{Proposed}=3.2;STD_{Current}=1.08<STD_{proposed}=1.11$).
The DM system also performed slightly better for calls with hard difficulty on
average but with a much larger standard deviation
($M_{Current}=2.00>M_{Proposed}=1.93;STD_{Current}=1.41>STD_{proposed}=0.58$).
Higher standard variation for hard difficulty indicates that the proposed
models will generate less unexpected actions or outputs. Moreover, the
proposed models outperformed the DM system across medium difficulty
($M_{Current}=2.37<M_{Proposed}=3.07;STD_{Current}=1.41>STD_{proposed}=1.14$).

However, t-test statistics of human ratings across different difficulties as
well as all levels combined were not significant ($p>0.1$). These findings
suggests, a careful consideration when interpreting these results and perhaps
the need for a larger sample to compare ratings for both models.


any value between $0$ and $4$, corresponding to the five cases above
respectively.

######  Remark 6.4.

It is worth noting that:

  * •

The lemma only states upper bounds, in contrast with Lemma 5.2.

  * •

The same observations made in Remark 5.3 are in place here, with the
manipulation of the $A$ term being pertinent to all types of buffer deletions.

  * •

In the case of buffer deletions, $B$ includes a factor of the form
$e^{Kf(qa)}$, where $K$ always corresponds to the number of buffers being
deleted.

  * •

The first three cases of Lemma 6.3 were considered in Lemma 5.2 as well.
However, the error estimates differ because in this section we deal with more
skewed aspect ratios and only provide upper bounds.

###### Proof.

For concreteness, consider the case $s=3$, $s^{\prime}=1^{\prime\prime}$,
$\alpha=\beta=\gamma=1$ and $\delta=0$, which is a 2-buffer deletion. In this
case, by Table 1, we have

$\displaystyle\mathcal{T}(F,F^{\prime})$
$\displaystyle{}=p^{2}e^{-f(q(k-i))-2q}\leqslant
e^{-2f(q(l-j))-f(q(k-i+2))}p^{2}e^{2f(qa)}$
$\displaystyle{}=e^{-(\alpha+\gamma)f(q(l-j))-(\beta+\delta)f(q(k-i+\alpha+\gamma))}p^{2}e^{2f(qa)}e^{O(q(a-\operatorname{short}(S))|f^{\prime}(q\operatorname{short}(S))|)}$
$\displaystyle{}=e^{-(\alpha+\gamma)f(q(l-j))-(\beta+\delta)f(q(k-i+\alpha+\gamma))}p^{2}e^{2f(qa)}e^{O(C_{2}a^{1/3})},$

where in the first inequality we used that $f$ is non-increasing and in the
second one we recalled that $|f^{\prime}(z)|\leqslant O(1/z)$. The other
transitions are treated analogously. ∎

We are now in position to prove Proposition 6.1.

###### Proof of Proposition 6.1.

With Lemma 6.3, we can return to Eq. 105 and fix any trajectory
$F_{1},\dots,F_{J}$ from $S$ to $T$. This trajectory naturally induces a path
$\gamma$ on $\mathbb{Z}^{2}$ going from $(a_{S},b_{S})$ to $(a_{T},b_{T})$
(the dimensions of $S$ and $T$ respectively). This path only makes unitary
jumps to the north of east directions and it is obtained as in Fig. 6 by
replacing any transitions involving a buffer deletion by multiple unitary
jumps. Further let $K_{0}+4,K_{1},K_{2},K_{3},K_{4}$ be the number of buffer
creations, loops, single, double and triple buffer deletions in the trajectory
$F_{1},\dots,F_{J}$ respectively. Observe that

$\displaystyle K_{0}$ $\displaystyle{}=K_{2}+2K_{3}+3K_{4},$
$\displaystyle\sum_{i=0}^{4}iK_{i}$ $\displaystyle{}=\phi(T)-\phi(S)$ (106)

(recall Table 1). Recalling Eqs. 30 and 6.3, we obtain

$\displaystyle\prod_{i=1}^{J}{\mathbb{P}}_{p}\left(\mathcal{T}(F_{i-1},F_{i})\right)$
$\displaystyle=e^{-W^{F}_{p}(\gamma)}\times
p^{K_{0}}e^{K_{0}(-qa+f(qa))}\times
e^{-4qa+O(K_{0}+1)C_{2}(qa^{2/3}+a^{-1/3})},$ $\displaystyle\leqslant
e^{-W^{F}_{p}(\gamma_{S,T})}\times p^{K_{0}}e^{K_{0}(-qa+f(qa))}\times
e^{O(K_{0}+1)C_{2}(qa^{2/3}+a^{-1/3})},$ (107)

using Eq. 106 and Lemma 2.10. Moreover, the total number of transitions is
$J=4+\sum_{i=0}^{4}K_{i}=4+\phi(T)-\phi(S)$. Hence, summing Eq. 107 over all
trajectories gives

$\sum_{F_{1},\dots,F_{J}}\prod_{i=1}^{J}{\mathbb{P}}_{p}\left(\mathcal{T}(F_{i-1},F_{i})\right)\leqslant
e^{-W_{p}^{\mathrm{F}}(\gamma_{S,T})}p^{-3}(\mathcal{I}+\mathcal{M}(P^{\prime}))^{J-1}(0,3),$
(108)

where $\mathcal{I}$ is the identity matrix and

$\displaystyle\mathcal{M}(x)$ $\displaystyle{}=\begin{pmatrix}0&x&0&0&0&0\\\
1&0&x&0&0&0\\\ 1&1&0&x&0&0\\\ 1&2&1&0&1&1\\\ 1&0&0&x&0&1\\\
1&0&0&0&x&0\end{pmatrix}$ $\displaystyle P^{\prime}$
$\displaystyle{}=pe^{-aq+f(aq)+O(C_{2})(qa^{2/3}+a^{-1/3})},$

recall Fig. 4.

Note that the matrix $\mathcal{M}(x)$ does not include the $1^{\prime\prime}$
state, like in Eq. 81. However, since we are now looking for an upper bound on
the probability, we had to compensate for this removal by doubling the entry
corresponding to the $3\to 1$ transition. In order to see why this is enough,
note first that the weights going out of $1$ and $1^{\prime\prime}$ are the
same. Therefore, since we are evaluating $(\mathcal{I}+\mathcal{M})^{J-1}$ at
$(0,3)$, we can join together the transitions $3\to 1\to s$ with those of type
$3\to 1^{\prime\prime}\to s$.

Clearly, setting $P=pe^{-aq+f(aq)}$, we have
$\mathcal{M}(P^{\prime})\leqslant\mathcal{M}(P)e^{O(C_{2})(qa^{2/3}+a^{-1/3})}$
entry-wise. Note that since $a=\operatorname{short}(T)\geqslant C_{2}$, we
have $P\leqslant pe^{f(aq)}\leqslant C^{-2}_{1}$. We next seek to bound the
spectral radius $\rho(\mathcal{M}(P))$, viewing it as a perturbation of the
same matrix without the double and triple buffer deletions, which amounts to
the matrix we already considered in Eq. 81.

The characteristic polynomial of $\mathcal{M}(P)/\sqrt{P}$ reads

$(X-1)(X+1)\left(X^{4}-4X^{2}+2-4X\sqrt{P}-P\right).$

Setting
$(\lambda_{i})_{i=1}^{6}=(\sqrt{2+\sqrt{2}},1,\sqrt{2-\sqrt{2}},-\sqrt{2-\sqrt{2}},-1,-\sqrt{2+\sqrt{2}})$,
we have

$X^{4}-4X^{2}+2=(X-\lambda_{1})(X-\lambda_{3})(X-\lambda_{4})(X-\lambda_{6}).$

Yet, for some constant $C>0$ and any $y\in\\{\lambda_{i}+\xi
C\sqrt{P}:i\in\\{1,\dots,6\\},\xi\in\\{-1,1\\}\\}$, we have

$\left|4y\sqrt{P}+P\right|<\left|y^{4}-4y^{2}+2\right|.$

Hence, the sign of the characteristic polynomial at $\lambda_{i}\pm C\sqrt{P}$
remains unchanged by the perturbation. Since $\sqrt{P}<1/C_{1}$, the
intermediate value theorem allows us to conclude that
$\mathcal{M}(P)/\sqrt{P}$ has eigenvalues $(\lambda^{\prime}_{i})_{i=1}^{6}$
with $|\lambda_{i}-\lambda^{\prime}_{i}|\leqslant C\sqrt{P}$ for
$i\in\\{1,\dots,6\\}$.111111Note that if the non-perturbed matrix had complex
eigenvalues, we would have used Rouché’s theorem instead. In particular,

$\rho(\mathcal{M}(P))\leqslant\sqrt{2+\sqrt{2}}\sqrt{P}e^{O(\sqrt{P})}.$

However, in Eq. 108, we need a particular coefficient of a power of
$\mathcal{I}+\mathcal{M}(P)$, so we also need some control on the norm of
$\mathcal{M}(P)$ and not only its spectral radius (because the matrix is not
symmetric). The following linear algebra result can be deduced from the
surprisingly recent bound of Jiang and Lam [Jiang97]. For the reader’s
convenience we produce a simpler proof.

######  Lemma 6.5.

Fix a dimension $d\geqslant 1$ and a submultiplicative norm
$\vvvert\cdot\vvvert$ on the space ${\mathbb{M}}_{d}({\mathbb{C}})$ of
$d\times d$ complex matrices.121212For instance, the operator norm, but recall
that in finite dimension all norms are equivalent. Let
$(\lambda_{i})_{i=1}^{d}$ be the eigenvalues of
$\mathcal{M}\in{\mathbb{M}}_{d}({\mathbb{C}})$. Assume that
$\varepsilon=\min_{i\neq j}|\lambda_{i}-\lambda_{j}|>0$. Then for every
$n\geqslant 0$ we have

$\vvvert\mathcal{M}^{n}\vvvert\leqslant
d\left(\frac{(1+\vvvert\mathcal{I}\vvvert)\vvvert\mathcal{M}\vvvert}{\varepsilon}\right)^{d-1}\rho(\mathcal{M})^{n}.$

###### Proof.

This proof is due to Quentin Moulard.

Consider the Lagrange interpolation polynomials

$L_{i}(X)=\frac{\prod_{j\neq i}(X-\lambda_{j})}{\prod_{j\neq
i}(\lambda_{j}-\lambda_{i})}.$

Note that $\mathcal{M}^{n}=\sum_{i=1}^{d}\lambda_{i}^{n}L_{i}(\mathcal{M})$,
so

$\vvvert\mathcal{M}^{n}\vvvert\leqslant d\rho(\mathcal{M})^{n}\max_{i}\vvvert
L_{i}(\mathcal{M})\vvvert.$

Yet, by submultiplicativity, for any $i\in\\{1,\dots,d\\}$, we get

$\vvvert L_{i}(\mathcal{M})\vvvert\leqslant\frac{\prod_{j\neq
i}\vvvert\mathcal{M}-\lambda_{j}\mathcal{I}\vvvert}{\prod_{j\neq
i}|\lambda_{j}-\lambda_{i}|}\leqslant\left(\frac{\vvvert\mathcal{M}\vvvert+\rho(\mathcal{M})\vvvert\mathcal{I}\vvvert}{\varepsilon}\right)^{d-1},$

which concludes the proof since
$\rho(\mathcal{M})=\lim_{m\to\infty}\vvvert\mathcal{M}^{m}\vvvert^{1/m}\leqslant\vvvert\mathcal{M}\vvvert$.
∎

We are now ready to conclude the proof of Proposition 6.1. Assembling Lemmas
6.5, 108, 105 and 104, we obtain

${\mathbb{P}}_{p}\left(\mathcal{C}^{\mathrm{F}}(S,T)\right)\\\ \leqslant
e^{-W_{p}^{\mathrm{F}}(\gamma_{S,T})}p^{-6C_{1}}\left(1+\sqrt{2+\sqrt{2}}\sqrt{P}\exp\left(O\left(\sqrt{P}+C_{2}\left(qa^{2/3}+a^{-1/3}\right)\right)\right)\right)^{\phi(T)-\phi(S)}.$

Recalling that $h(aq)=\sqrt{2+\sqrt{2}}\sqrt{P/p}$ (see Eqs. 67 and 22) and
Eq. 28, we get

$\displaystyle{\mathbb{P}}_{p}\left(\mathcal{C}^{\mathrm{F}}(S,T)\right)\leqslant{}$
$\displaystyle
e^{-W_{p}^{\mathrm{F}}(\gamma_{S,T})}p^{-6C_{1}}e^{(\phi(T)-\phi(S))\sqrt{p}h(aq)(1+O(\sqrt{P}+C_{2}(qa^{2/3}+a^{-1/3})))}$
$\displaystyle\leqslant{}$ $\displaystyle
e^{-W_{p}^{\mathrm{F}}(\gamma_{S,T})+(\phi(T)-\phi(S))\sqrt{q}h(aq)}p^{-6C_{1}}e^{C_{2}^{3}a^{2/3}\sqrt{P}(\sqrt{P}+qa^{2/3}+a^{-1/3})}$
$\displaystyle\leqslant$
$\displaystyle{}e^{-W_{p}^{\mathrm{F}}(\gamma_{S,T})+(\phi(T)-\phi(S))\sqrt{q}h(aq)}p^{-6C_{1}}e^{C_{2}^{4}},$

where in the last inequality we observed that $\sqrt{P}=pe^{-aq+f(aq)}=O(1/a)$
by Eqs. 28 and 25 and $a^{-1/6}+qa^{5/6}\leqslant 1$, since $1\leqslant
a\leqslant\Lambda$. This concludes the proof of Proposition 6.1. ∎

##  7 The bootstrap percolation paradox

Having completed the proof of Theorem 1.2, we may return to the bootstrap
percolation paradox. We focus on the Froböse model, but one can proceed
analogously for the two-neighbour and modified two-neighbour models (see Fig.
8(b)).

Recalling Corollary 3.6, estimating $\tau$ is equivalent to computing

$\widetilde{\Pi}(p)=\left({\mathbb{P}}_{p}\left(\mathcal{I}_{\mathrm{loc}}^{\mathrm{F}}(R(\Lambda,\Lambda))\right)\right)^{-1/2}.$

Also recalling Eqs. 85, 2.3 and 4.3, we obtain that

$\widetilde{\Pi}(p)=p^{O(C_{1})}\max_{x\in
R(\Lambda,\Lambda)}\left({\mathbb{P}}_{p}\left(\exists t\geqslant
0:\mathcal{F}^{\\{x\\}}(t)=R(\Lambda,\Lambda)\right)\right)^{-1/2}.$

Proceeding in a very similar way, it is possible to show the more convenient
result (recall that $\phi(R)$ denotes the semi-perimeter of the rectangle $R$)

$\Pi(p):=\left({\mathbb{P}}_{p}\left(\exists t\geqslant
0:\phi\left(\mathcal{F}^{\\{0\\}}(t)\right)=\left\lceil\frac{2\log(1/p)}{p}\right\rceil\right)\right)^{-1/2}=\widetilde{\Pi}(p)p^{O(C_{1})}.$
(109)

In order to compute $\Pi(p)$ more efficiently, we project the Markov chain
$\mathcal{F}^{\\{0\\}}$ to a process on
${\mathbb{N}}^{2}\times\\{0,1,1^{\prime},1^{\prime\prime},2,2^{\prime},3,4\\}$
via the mapping $F(a,b;c,d;s)\mapsto(c-a,d-b,s)$. We denote this process
$(\mathcal{R}(t))_{t\geqslant 0}$ with $\mathcal{R}(0)=(1,1,0)$. Using
translation invariance, it is not hard to check that this process is also a
Markov chain, whose transition probabilities can be obtained by summing the
appropriate transition probabilities of the original chain listed in Table 1
(the corresponding expressions can be found in the supplementary material Rust
code131313Implementations in C, Rust and Python-Taichi can be found in
https://github.com/augustoteixeira/bootstrap or as part of the arxiv
submission source.). Since $\phi(\mathcal{F}^{\\{0\\}}(t))$ increases by at
most 4 at each step and the chain $\mathcal{R}$ has no cycles except the
absorbing states, we can compute the probability of reaching each possible
state of $\mathcal{R}$ recursively via dynamic programming. This way, for any
fixed $p$, we can compute $\Pi(p)$ exactly.

$\log_{2}\frac{1}{p}$ | $\log\Pi(p)$ | $\log_{2}\frac{1}{p}$ | $\log\Pi(p)$ | $\log_{2}\frac{1}{p}$ | $\log\Pi(p)$ | $\log_{2}\frac{1}{p}$ | $\log\Pi(p)$
---|---|---|---|---|---|---|---
2 | 1.8231469544522168 | 6 | 71.22104704459092 | 10 | 1519.9177238798902 | 14 | 26243.443273103207
3 | 4.742671577932995 | 7 | 159.10494055779233 | 11 | 3130.360634994818 | 15 | 52891.342141028406
4 | 12.392931032600497 | 8 | 344.5259389380065 | 12 | 6393.748024566681 | 16 | 106363.14234086743
5 | 30.54732365348029 | 9 | 729.489374480061 | 13 | 12981.361913134877 | 17 | 213556.78508818566
Table 2: The numerical results for $\Pi(p)$ of Eq. 109 for (local) Froböse
bootstrap percolation.

The main practical issue with the above algorithm is that the probabilities we
compute are of order $\exp(-\lambda_{1}^{\mathrm{F}}/p)$, which quickly
becomes too small for conventional data types (IEEE 754). In order to
substantially increase the precision, we store the logarithms of each
probability $a=\log(r)$, using the expression
$\log(r+s)=\log(e^{a}+e^{b})=\max\\{a,b\\}+\log(1+e^{-|a-b|})$ in order to
obtain the log of the sum or two probabilities without losing precision. Other
optimisations have also been implemented, such as restricting calculations to
only regions where the probabilities are non-zero. But most importantly, we
have made use of a Graphical Processing Unit (GPU) in order to take advantage
of the parallelism built into our algorithm, which was responsible for large
speed benefits.

Our implementation of the algorithm can be found in the supplementary
material,${}^{\ref{footnote:supplementary}}$ but we emphasise that it still
has a lot of room for further optimisations (hand-written CUDA code, optimal
scheduling, extra and more powerful GPU’s…). We ran this code on a Intel Xeon
E3-1240 v3, with a single NVIDIA GeForce RTX 4060 8GB during 24 hours. The
resulting data is plotted in Fig. 1 and given in Table 2. In Fig. 7 we use it
to successively estimate $\alpha$, $\lambda_{1}^{\mathrm{F}}$, $\beta<\alpha$
and $\lambda_{2}^{\mathrm{F}}$, given the exact values of the previous ones,
so that

$\log\Pi(p)\approx\frac{\lambda_{1}^{\mathrm{F}}}{p^{\alpha}}-\frac{\lambda_{2}^{\mathrm{F}}}{p^{\beta}}.$
(110)

Since there the numerical results are exact up to computation precision and we
are interested in asymptotics, we use a simple linear regression based on the
last three data points. This somewhat arbitrary choice was made before the
data was generated, in order to avoid overfitting. The results are in
excellent agreement with the rigorous result Eq. 7. Moreover, directly fitting
all four parameters in Eq. 110 based on the last four data points in Table 2
yields

$\displaystyle\alpha$ $\displaystyle{}\approx 0.99978,$
$\displaystyle\lambda_{1}^{\mathrm{F}}$ $\displaystyle{}\approx 1.6507,$
$\displaystyle\beta$ $\displaystyle{}\approx 0.53239,$
$\displaystyle\lambda_{2}^{\mathrm{F}}$ $\displaystyle{}\approx 4.2518,$ (111)

which is also in good agreement with Theorem 1.2, see code for fitting and
plotting in the tagged repository. Note that the data points in Figs. 7 and 1
are simply reparametrisations of the ones given in Table 2).

$\log\frac{1}{p}$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$\log\log\Pi(p)$$2$$4$$6$$8$$10$$12$$1.00676\log\frac{1}{p}+\log
1.50499$ (a) Simultaneously estimating $\alpha\approx 1.007$ and
$\lambda_{1}^{\mathrm{F}}\approx 1.505$.

$\frac{1}{10^{4}p}$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$10^{-4}\log\Pi(p)$$0$$3$$6$$9$$12$$15$$18$$21$$\frac{1.634555}{10^{4}p}+C$
(b) Estimating $\lambda_{1}^{\mathrm{F}}\approx 1.635$, given $\alpha=1$.

$\log\frac{1}{p}$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$\log\left(\frac{\pi^{2}}{6p}-\log\Pi(p)\right)$$1.5$$2.5$$3.5$$4.5$$5.5$$6.5$$7.5$$0.510037\log\frac{1}{p}+\log
5.027234$ (c) Simultaneously estimating $\beta\approx 0.5100$ and
$\lambda_{2}^{\mathrm{F}}\approx 5.027$, given $\alpha=1$ and
$\lambda_{1}^{\mathrm{F}}=\pi^{2}/6$.

$\frac{1}{10^{2}\sqrt{p}}$$0$$0.5$$1$$1.5$$2$$2.5$$3$$3.5$$\frac{1}{10^{2}}\left(\frac{\pi^{2}}{6}-\log\Pi(p)\right)$$0$$3$$6$$9$$12$$15$$18$$21$$\frac{5.735441}{10^{2}\sqrt{p}}+C$
(d) Estimating $\lambda_{2}^{\mathrm{F}}\approx 5.735$, given $\alpha=1$,
$\lambda_{1}^{\mathrm{F}}=\pi^{2}/6$ and $\beta=1/2$.

Figure 7: Estimating the asymptotic expansion Eq. 110, using the numerical
estimates of $\Pi(p)$ from Eq. 109 for Froböse bootstrap percolation. In
Theorem 1.2 we showed that in fact $\alpha=1$,
$\lambda_{1}^{\mathrm{F}}=\pi^{2}/6\approx 1.6449$, $\beta=1/2$,
$\lambda_{2}^{\mathrm{F}}=\pi\sqrt{2+\sqrt{2}}\approx 5.8049$.

##  8 Outlook

###  8.1 Froböse and two-neighbour bootstrap percolation

Naturally, one may want to improve the bounds in Theorems 1.2 and 1.3. In view
of Theorem 1.1, this problem only concerns the corresponding local models.
Such sharper results can be obtained along lines of our proof, but, as the
precision increases, additional technical issues arise.

The main problem is the fact that we artificially cut trajectories into coarse
steps, imposing their endpoints to be squares in Section 5.1. Similarly, in
Section 6.1, we take a union bound on coarse sequences. In order to go beyond
the error term $q^{-1/3}$, one would need to cut trajectories into larger
pieces (or, preferably, not at all). Yet, this entails problems, when applying
Lemma 5.4. Therefore, one would like to restrict attention to paths $\gamma$
not deviating too much form the diagonal. Taking this into account and despite
Fig. 8(a), we do _not_ believe that the third order exponent equals $1/5$, but
heuristic computations rather suggest it to be $1/4$ (recall that in Theorem
1.2 we showed that it is at most $1/3$, which is certainly compatible with
Fig. 8(a)).

For the two-neighbour model additional problems arise due to parity, somewhat
like in Case 4.3 of the proof of Proposition 3.4. More precisely, the error
term on the right-hand side of Lemma A.1 eventually becomes large. This
translates the fact that, at small scales, the amount of consecutive loop
transitions we typically want to use is insufficient for the two-term
recurrence Eq. 117 to stabilise. Consequently, the factor $\alpha(aq)$ in
Lemma A.7 becomes essentially equal to 2 for even $\ell$ and $0$ for odd
$\ell$. This needs to be taken into account when counting trajectories.

###  8.2 Modified two-neighbour bootstrap percolation

A much more challenging model to tackle is modified two-neighbour bootstrap
percolation. Much of the treatment carried out here can also be done for its
local version. This leads to the function

$h_{2^{\prime}}(z)=\sqrt{(2+\sqrt{2})e^{-z}e^{2f(z)}}=\frac{\sqrt{2+\sqrt{2}}}{2\sinh(z/2)},$
(112)

which is not integrable at 0. The logarithmic divergence of the primitive of
$h_{2^{\prime}}$ led to the discovery of [Hartarsky23mod-2n]. Thus, in order
to obtain the second term, one needs to integrate $h_{2^{\prime}}$ down to
scale $1/\sqrt{p}$, at which point it stops being valid. Indeed, below that
scale one would use essentially no loop transitions.

However, a more serious problem arises for the modified model. Namely,
locality in the strong form of Theorem 1.1 does _not_ hold. To see this,
observe that at small scales, configurations with minimal number of infections
dominate. But a minimal configuration of infections internally filling a
square is an object known under the name _separable permutation_ (this was
observed in some form already in [Shapiro91]; also see [Dukes23] for a recent
account of extremal problems in bootstrap percolation). The latter are counted
by Schröder numbers, which grow exponentially faster than the number of local
internally filling configurations. Indeed, typical separable permutations
admit a scaling limit called the _Browninan separable permuton_ [Bassino18],
which is far from corresponding to a local decomposition. Moreover, non-local
decompositions arise naturally on scale $1/\sqrt{p}$ from successive single
buffer deletion, buffer creation, single buffer deletion, which can be
replaced by finding a $1\times 1$ internally filled square at the corner of
the current rectangle. Thus, we expect that the second term of the asymptotic
expansion of $\log\tau$ will coincide with its its local analogue, but will be
followed by a subsequent correction only $\log(1/p)$ away reflecting non-
locality.

In view of the above discussion, we ask the following.

######  Question 1.

For modified two-neighbour bootstrap percolation on ${\mathbb{Z}}^{2}$ and any
$\varepsilon>0$, do we have

$\lim_{p\to
0}{\mathbb{P}}_{p}\Bigg{(}\exp\left(\frac{\pi^{2}}{6p}-\frac{(\sqrt{2+\sqrt{2}}+\varepsilon)\log(1/p)}{2\sqrt{p}}\right)\leqslant\tau^{\mathrm{mod}}\\\
\leqslant\exp\left(\frac{\pi^{2}}{6p}-\frac{(\sqrt{2+\sqrt{2}}-\varepsilon)\log(1/p)}{2\sqrt{p}}\right)\Bigg{)}=1?$

We supply a numerical estimate along the lines discussed in Section 7 in Fig.
8(b) supporting an affirmative answer to Question 1 in the case of the local
modified model. Note that $\sqrt{2+\sqrt{2}}/2\approx 0.924$ is indeed only
$4\%$ away from the estimated value for the second order constant.

$\log\frac{1}{p}$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$\log\left(\log\Pi(p)-\frac{\pi^{2}}{6p}+\frac{\pi\sqrt{2+\sqrt{2}}}{\sqrt{p}}\right)$$1.75$$2$$2.25$$2.5$$2.75$$3$$3.25$$3.5$$3.75$$0.19414\log\frac{1}{p}+C$
(a) Estimating the third order exponent $0.194$ for Froböse bootstrap
percolation. Examining the discrete derivatives suggests that it is not yet
close to its limiting value.

$\log\frac{1}{p}$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$\frac{\pi^{2}}{6\sqrt{p}}-\sqrt{p}\log\Pi(p)$$2$$4$$6$$8$$10$$12$$14$$0.960305\log\frac{1}{p}+C$
(b) Estimating the second order constant $\lambda^{\prime}_{2}\approx 0.960$
for modified two-neighbour bootstrap percolation on ${\mathbb{Z}}^{2}$. In
Question 1 we ask whether $\lambda^{\prime}_{2}=\sqrt{2+\sqrt{2}}/2\approx
0.924$.

Figure 8: Estimating the asymptotics, using the numerical estimates of
$\Pi(p)$ from Eq. 109.

###  8.3 Generalisations

Recall that [Duminil-Copin23] provides sharp thresholds analogous to Eq. 2 for
a range of well-behaved models. It is then natural to investigate when
locality holds for them. Roughly speaking, we expect this to be the case,
whenever “corner growth is not more advantageous than side growth”. If, on the
contrary, “corner growth is more advantageous than side growth”, then we
expect the phenomenology of modified two-neighbour model to arise and the
model to deviate from its local counterpart at some polynomial scale (smaller
than the critical one).

It is also natural to consider higher dimensional models, starting with two-
neighbour bootstrap percolation in 3 dimensions (or its variants), but
eventually also the $r$-neighbour model (see [Balogh12] for the analogue of
Eq. 2). It is also unclear whether locality can be useful for studying
bootstrap percolation beyond $\mathbb{Z}^{d}$ (also see e.g. [Kolesnik22]).

Independently of establishing locality, our work provides motivation for
studying local models in their own right. One could define a general local
model as a polygon with prescribed side directions and finite number of
possible frame states which grows in each direction with a certain size-
dependent probability in a Markovian way (recall Section 4.2). Can one
quantify their probability of never being absorbed?

###  8.4 Bootstrap percolation paradox

Finally, we end with a note of optimism regarding numerical work. While
simulations have previously proved highly unreliable for studying bootstrap
percolation, locality has allowed us to obtain very accurate results at par
with rigorous results. Can this new viewpoint enable numerical works to go
beyond theoretical ones and provide reliable predictions for the behaviour of
bootstrap percolation models? One interesting specific direction of research
along this line is the following. In [Duminil-Copin23], the sharp threshold
constant $\lambda_{1}$ is determined implicitly as the solution of an
infinite-dimensional optimisation problem with a cost functional which is
itself implicitly defined. It is therefore not clear how one could determine
this constant in practice. The numerical approach discussed in Section 7 may
allow to numerically estimate these constants.

## Acknowledgements

I.H. was supported by the Austrian Science Fund (FWF): P35428-N and ERC
Starting Grant 680275 “MALIG.” A.T. was supported by grants “Projeto
Universal” (406250/2016-2) and “Produtividade em Pesquisa” (304437/2018-2)
from CNPq and “Jovem Cientista do Nosso Estado”, (202.716/2018) from FAPERJ.
We thank Quentin Moulard and Jana Reker for enlightening discussions and
Instituto Superior Técnico of the University of Lisbon and IMPA, where part of
the work was done, for their hospitality.

##  Appendix A Local two-neighbour bootstrap percolation

In this appendix we discuss the additional technicalities needed for the proof
of Theorem 1.3 as compared to Theorem 1.2. We will not dwell on trivial
changes such as replacing $f$ by $g$, $W^{\mathrm{F}}$ by $W$, etc. In view of
Corollary 3.6, Theorem 1.3 is proved as soon as we establish

$\exp\left(-\frac{2\lambda_{1}}{q}+\frac{2\lambda_{2}}{\sqrt{q}}-\frac{\log^{2}(1/q)}{\sqrt[3]{q}}\right)\leqslant{\mathbb{P}}_{p}(\mathcal{I}_{\mathrm{loc}}(R))\leqslant\exp\left(-\frac{2\lambda_{1}}{q}+\frac{2\lambda_{2}}{\sqrt{q}}+\frac{\log^{2}(1/q)}{\sqrt[3]{q}}\right),$
(113)

where $R=R(\Lambda,\Lambda)$ (recall Eqs. 28, 27 and 40) and
$\lambda_{2}=\int_{0}^{\infty}h_{2}$ with $h_{2}$ defined in Eq. 119 below.

###  A.1 Preliminaries

####  A.1.1 Refined traversability

We first need the auxiliary function $\alpha$ for the following refinement of
Lemma 2.9. Recall $f,\beta,g,q$ from Eqs. 28, 23, 22 and 24 and set

$\displaystyle\alpha:(0,\infty)\to(1,2):z\mapsto\frac{2\beta(e^{-f(z)})}{\sqrt{e^{-f(z)}(4-3e^{-f(z)})}},$
(114)
$\displaystyle\bar{\beta}:(0,1)\to[-1/3,0):u\mapsto\frac{u-\sqrt{u(4-3u)}}{2}.$
(115)

######  Lemma A.1 (Refined traversability probability).

Let $R=R(a,b)$ be a rectangle. Set $u=1-e^{-bq}=e^{-f(bq)}$. Then

$\left|\frac{{\mathbb{P}}_{p}(\mathcal{T}_{\rightarrow}(R))}{\alpha(bq)\exp(-ag(bq))}-1\right|\leqslant\left(\frac{|\bar{\beta}(u)|}{\beta(u)}\right)^{a+1}.$

###### Proof.

Let $x_{n}={\mathbb{P}}_{p}(\mathcal{T}_{\rightarrow}(R(n,b)))$ for any non-
negative integer $n$. We first claim that

$x_{n}=\frac{(\beta(u))^{n+1}-(\bar{\beta}(u))^{n+1}}{\beta(u)-\bar{\beta}(u)}.$
(116)

This is verified directly for $n\in\\{0,1\\}$. Moreover,

$x_{n+2}=x_{n+1}u+x_{n}(1-u)u.$ (117)

Solving this recurrence relation, we obtain Eq. 116. Finally, we use that

$\alpha(bq)e^{-ag(bq)}=\frac{(\beta(u))^{a+1}}{\beta(u)-\bar{\beta}(u)}.\qed$

####  A.1.2 The entropy function

With Eq. 114 at hand, we are ready to define $h$. Recalling Eqs. 22, 24 and
114, define the following functions from $(0,\infty)$ to itself

$\displaystyle\mathcal{M}_{2,1}(z)$ $\displaystyle{}=pe^{-f(z)+3g(z)},$
$\displaystyle\mathcal{M}_{3,1}(z)$ $\displaystyle{}=pe^{-f(z)+4g(z)},$
$\displaystyle\mathcal{M}_{2,2}(z)$ $\displaystyle{}=2pe^{-f(z)+4g(z)-z},$
$\displaystyle\mathcal{M}_{3,2}(z)$ $\displaystyle{}=pe^{-2f(z)+5g(z)-z},$
$\displaystyle\mathcal{M}_{0,0}(z)$ $\displaystyle{}=e^{-2z},$ (118)
$h_{2}(z)=\alpha(z)\sqrt{\left(2+\sqrt{2}\right)\mathcal{M}_{0,0}(z)\frac{\mathcal{M}_{2,1}(z)+\mathcal{M}_{3,1}(z)+\mathcal{M}_{2,2}(z)+\mathcal{M}_{3,2}(z)}{p}}.$
(119)

We will need the following properties of the above functions, whose elementary
proofs are left to the reader (or to a computation software). The functions
$\alpha$ and $h$ are analytic,

$\displaystyle\alpha(z)$
$\displaystyle{}=\begin{cases}1+\frac{\sqrt{z}}{2}+O(z)&z\to 0,\\\
2-2e^{-z}+O(e^{-2z})&z\to\infty,\end{cases}$ $\displaystyle h_{2}(z)$
$\displaystyle{}=\begin{cases}\sqrt{\frac{3(2+\sqrt{2})}{z}}\left(1-\frac{\sqrt{z}}{6}+O(z)\right)&z\to
0,\\\ \frac{2\sqrt{2(2+\sqrt{2})}}{e^{z}}(1+O(e^{-z}))&z\to\infty.\end{cases}$
(120)

In particular, Eq. 68 implies that $h_{2}$ is integrable, so
$\lambda_{2}=\int_{0}^{\infty}h_{2}\in(0,\infty)$ and one can numerically
compute that $\lambda_{2}\approx 7.054547$.

####  A.1.3 Frames

We first need to change Eq. 65 into

$\begin{split}&B^{r}(R)=R(c,b;c+2,d),\qquad B^{u}(R)=R(a,d;c,d+2)\\\
&B^{l}(R)=R(a-2,b;a,d),\qquad B^{d}(R)=R(a,b-2;c,b).\end{split}$ (121)

Then Definition 4.1 is replaced by the following. In words, each buffer now
has thickness 2 and whenever two adjacent ones are present, we also add the
corner site between them.

######  Definition A.2.

A _framed rectangle_ is a rectangle $R(a,b;c,d)$ equipped with a label
$s\in\\{0,1,1^{\prime},1^{\prime\prime},2,2^{\prime},2^{\prime\prime},3,4\\}$.
We denote it by $F(a,b;c,d;s)$. We refer to $(c-a,d-b)$ as its _dimensions_
and to $s$ as its _frame state_. For a framed rectangle $F=F(a,b;c,d;s)$ we
set $F_{\circ}=R(a,b;c,d)$ and define the _frame_ of $F$ by

$F_{\square}=\begin{cases}\varnothing&s=0,\\\ B^{r}(F_{\circ})&s=1,\\\
B^{r}(F_{\circ})\cup\\{(c,d)\\}\cup B^{u}(F_{\circ})&s=2,\\\
B^{r}(F_{\circ})\cup\\{(c,d)\\}\cup B^{u}(F_{\circ})\cup\\{(a-1,d)\\}\cup
B^{l}(F_{\circ})&s=3,\\\
\phantom{B^{r}(F_{\circ})\cup\\{(c,d)\\}\cup{}}B^{u}(F_{\circ})\cup\\{(a-1,d)\\}\cup
B^{l}(F_{\circ})&s=2^{\prime},\\\ \phantom{B^{r}(F_{\circ})\cup\\{(c,d)\\}\cup
B^{u}(F_{\circ})\cup\\{(a-1,d)\\}\cup{}}B^{l}(F_{\circ})&s=1^{\prime},\\\
\phantom{B^{r}(F_{\circ})\cup\\{(c,d)\\}\cup{}}B^{u}(F_{\circ})&s=1^{\prime\prime},\\\
B^{r}(F_{\circ})\cup\phantom{\\{(c,d)\\}\cup
B^{u}(F_{\circ})\cup\\{(a-1,d)\\}\cup{}}B^{l}(F_{\circ})&s=2^{\prime\prime},\\\
\begin{aligned} &{}B^{r}(F_{\circ})\cup\\{(c,d)\\}\cup
B^{u}(F_{\circ})\cup\\{(a-1,d)\\}\cup B^{l}(F_{\circ})\\\
&{}\cup\\{(a-1,b-1)\\}\cup
B^{d}(F_{\circ})\cup\\{(c,b-1)\\}\end{aligned}&x=4,\end{cases}$

see [Hartarsky19]*Fig. 1. We denote $F_{\blacksquare}=F_{\circ}\cup
F_{\square}$.

Note that an additional frame state $2^{\prime\prime}$ appeared with respect
to Definition 4.1.

####  A.1.4 The framed rectangle Markov chain

It is possible to construct a Markov chain along the lines of Section 4.2.
Unfortunately, doing so requires an extensive amount of casework, which we
have not been able to condense into a reasonable amount of space. We therefore
restrict our attention to proving the lower bound of Eq. 113. We nevertheless
mention that for the upper bound of Eq. 113 the changes only affect Section
6.2 and go along the same lines as the ones for the lower bound.

For the purposes of the lower bound of Eq. 113, it is sufficient to construct
a sub-Markovian process by only considering the relevant transitions, which
are nonetheless rather numerous. We thus replace Table 1 by Table 3.

In order to keep transition events $\mathcal{T}(F,F^{\prime})$ disjoint for
distinct choices of $F^{\prime}$ we need a finer choice of events as compared
to Eq. 66. Since they are completely analogous, we only provide the
definitions (and associated verifications in the sequel) for transitions from
framed rectangles with frame state $1$ (for other frame states the only
difference, except symmetry, is that we also need to enforce a bounded number
of additional sites in $F^{\prime}_{\square}\setminus F_{\square}$ to be
healthy). For $F=F(0,0;a,b;1)$ and
$F^{\prime}=F(0,0;a+\gamma,b+\delta;s^{\prime})$ we define

$\mathcal{T}(F,F^{\prime})=\begin{cases}\mathcal{O}^{c}(R(0,b;a,b+2))\cap\mathcal{O}^{c}(\\{(a,b)\\})&(s^{\prime},\gamma,\delta)=(2,0,0)\\\
\mathcal{O}^{c}(R(a,b;a+2,b+1))\cap\mathcal{O}(R(0,b;a,b+1))&(s^{\prime},\gamma,\delta)=(1,0,1)\\\
\begin{aligned}
&\mathcal{O}^{c}(R(a,b;a+2,b+2))\cap\mathcal{O}^{c}(R(0,b;a,b+1))\\\
&{}\cap\mathcal{O}(R(0,b+1;a,b+2))\end{aligned}&(s^{\prime},\gamma,\delta)=(1,0,2)\\\
\mathcal{O}(R(0,b;a+1,b+1))\cap\mathcal{O}(\\{(a+1,b)\\})&(s^{\prime},\gamma,\delta)=(0,2,1)\\\
\begin{aligned} &\mathcal{O}(\\{(a,b)\\})\cap\mathcal{O}^{c}(\\{(a+1,b)\\})\\\
&{}\cap\mathcal{O}(R(a+1,0;a+2,b+1))\end{aligned}&(s^{\prime},\gamma,\delta)=(0,3,1)\\\
\begin{aligned}
&\mathcal{O}^{c}(R(0,b;a+1,b+1))\cap\mathcal{O}(R(0,b+1;a,b+2))\\\
&{}\cap\mathcal{O}(R(a+1,b;a+2,b+2))\end{aligned}&(s^{\prime},\gamma,\delta)=(0,2,2)\\\
\begin{aligned}
&\mathcal{O}^{c}(R(0,b;a+1,b+1))\cap\mathcal{O}(R(0,b+1;a,b+2))\\\
&{}\cap\mathcal{O}^{c}(R(a+1,b;a+2,b+2))\cap\mathcal{O}(\\{(a,b+1)\\})\\\
&{}\cap\mathcal{O}(R(a+1,0;a+2,b+2))\end{aligned}&(s^{\prime},\gamma,\delta)=(0,3,2)\end{cases}$
(122)

We note that for $F$ with frame state $1$ the only transitions we are omitting
(as they are not required for the upper bound) correspond to
$(s^{\prime},\gamma,\delta)\in\\{(1,1,1),(1,1,2)\\}$, but for frame states
$2,2^{\prime}$ there are tens of them and for frame state $3$ almost a
hundred.

As in Observation 4.2, we have the following.

######  Observation A.3.

Table 3 defines a sub-stochastic matrix $\mathcal{T}$. For any framed
rectangle $F$, the events $\mathcal{T}(F,F^{\prime})$ (see Eq. 122
corresponding to transitions present in $\mathcal{T}$ are disjoint for
different choices of $F^{\prime}$. For each transition
$\mathcal{T}(F,F^{\prime})$ we have $F_{\circ}\subset F^{\prime}_{\circ}$ and
$F_{\blacksquare}\subsetneq F^{\prime}_{\blacksquare}$, unless $F$ has buffer
state 4. If $F=F(a,b;c,d;s)$ and
$F^{\prime}=F(a^{\prime},b^{\prime};c^{\prime},d^{\prime};s)$, then

$\mathcal{T}(F,F^{\prime})\subset\left\\{A:(A\setminus
F_{\blacksquare})\in\left(\mathcal{C}^{\mathrm{F}}(R(a,b;c,d),R(a^{\prime},b^{\prime};c^{\prime},d^{\prime}))\cap\mathcal{O}^{c}(F^{\prime}_{\square})\right)\right\\}.$

The transition events $\mathcal{T}(F,F^{\prime})$ define a sub-Markovian
process $(\mathcal{F}(t))_{t\in{\mathbb{N}}}$ with transition matrix
$\mathcal{T}$, whose state $\mathcal{F}(t)$ is measurable with respect to
$A\cap\mathcal{F}(t)_{\blacksquare}$.141414For the reader’s convenience, we
recall that such a sub-Markovian process may be viewed simply as a Markov
chain with an additional absorbing cemetery state.

Given a rectangle $S$, we denote by $(\mathcal{F}^{S}(t))_{t\in{\mathbb{N}}}$
this process with initial state $S$ with frame state 0. If
$\mathcal{I}_{\mathrm{loc}}(S)$ occurs, then for all $t\geqslant 0$,
$\mathcal{I}_{\mathrm{loc}}(\mathcal{F}^{S}_{\circ}(t))\cap\mathcal{O}^{c}(\mathcal{F}^{S}_{\square}(t))$
occurs. We denote $\mathcal{F}^{S}(\infty)=\bigcup_{t\geqslant
0}\mathcal{F}_{\circ}^{S}(t)$. Then for any $x\in{\mathbb{Z}}^{2}$, either
$\mathcal{F}^{\\{x\\}}(\infty)=[A]^{x}$, in case $[A]^{x}$ is finite, or both
$[A]^{x}$ and $\mathcal{F}^{\\{x\\}}(\infty)$ are infinite (although not
necessarily equal).

Similarly, Corollary 4.3 becomes the following.

######  Corollary A.4.

Given nested rectangles $S\subset R=R(a,b)$, we have

${\mathbb{P}}_{p}\left(\mathcal{C}(S,R)\right)\geqslant\frac{{\mathbb{P}}_{p}(\mathcal{F}^{S}(\infty)=R)}{e^{-4(a+b+1)q}}.$

$s$ | $s^{\prime}$ | $\alpha$ | $\beta$ | $\gamma$ | $\delta$ | $-\log{\mathbb{P}}_{p}(\mathcal{T}(F(0,0;a,b;s),F(-\alpha,-\beta;a+\gamma,b+\delta;s^{\prime})))$
---|---|---|---|---|---|---
0 | 1 | 0 | 0 | 0 | 0 | $2qb$
1 | 2 | 0 | 0 | 0 | 0 | $q(2a+1)$
2 | 3 | 0 | 0 | 0 | 0 | $q(2b+1)$
3 | 4 | 0 | 0 | 0 | 0 | $q(2a+2)$
2’ | 3 | 0 | 0 | 0 | 0 | $q(2b+1)$
1’ | 2’ | 0 | 0 | 0 | 0 | $q(2a+1)$
0 | 0 | 0 | 0 | 1 | 0 | $f(qb)$
0 | 0 | 0 | 0 | 2 | 0 | $f(qb)+qb$
1 | 1 | 0 | 0 | 0 | 1 | $f(qa)+2q$
1 | 1 | 0 | 0 | 0 | 2 | $f(qa)+4q+qa$
2 | 2 | 1 | 0 | 0 | 0 | $f(qb)+2q$
2 | 2 | 2 | 0 | 0 | 0 | $f(qb)+4q+qb$
3 | 3 | 0 | 1 | 0 | 0 | $f(qa)+4q$
3 | 3 | 0 | 2 | 0 | 0 | $f(qa)+8q+qa$
2’ | 2’ | 0 | 0 | 1 | 0 | $f(qb)+2q$
2’ | 2’ | 0 | 0 | 2 | 0 | $f(qb)+4q+qb$
1’ | 1’ | 0 | 0 | 0 | 1 | $f(qa)+4q$
1’ | 1’ | 0 | 0 | 0 | 2 | $f(qa)+8q+qa$
4 | 4 | 0 | 0 | 0 | 0 | 0
1 | 0 | 0 | 0 | 2 | 1 | $\log(1/p)+f(q(a+1))$
1 | 0 | 0 | 0 | 3 | 1 | $\log(1/p)+f(q(b+1))+q$
1 | 0 | 0 | 0 | 2 | 2 | $f(2q)+f(qa)+q(a+1)$
1 | 0 | 0 | 0 | 3 | 2 | $\log(1/p)+f(qa)+f(q(b+2))+q(a+3)$
1’ | 0 | 2 | 0 | 0 | 1 | $\log(1/p)+f(q(a+1))$
1’ | 0 | 3 | 0 | 0 | 1 | $\log(1/p)+f(q(b+1))+q$
1’ | 0 | 2 | 0 | 0 | 2 | $f(2q)+f(qa)+q(a+1)$
1’ | 0 | 3 | 0 | 0 | 2 | $\log(1/p)+f(qa)+f(q(b+2))+q(a+3)$
2 | 1 | 1 | 0 | 0 | 2 | $\log(1/p)+f(q(b+1))+3q$
2 | 1 | 1 | 0 | 0 | 3 | $\log(1/p)+f(q(a+1))+6q$
2 | 1 | 2 | 0 | 0 | 2 | $f(2q)+f(qb)+q(b+4)$
2 | 1 | 2 | 0 | 0 | 3 | $\log(1/p)+f(qb)+f(q(a+2))+q(b+8)$
2’ | 1’ | 0 | 0 | 1 | 2 | $\log(1/p)+f(q(b+1))+3q$
2’ | 1’ | 0 | 0 | 1 | 3 | $\log(1/p)+f(q(a+1))+6q$
2’ | 1’ | 0 | 0 | 2 | 2 | $f(2q)+f(qb)+q(b+4)$
2’ | 1’ | 0 | 0 | 2 | 3 | $\log(1/p)+f(qb)+f(q(a+2))+q(b+8)$
3 | 2’ | 0 | 1 | 2 | 0 | $\log(1/p)+f(q(a+1))+5q$
3 | 2’ | 0 | 1 | 3 | 0 | $\log(1/p)+f(q(b+1))+8q$
3 | 2’ | 0 | 2 | 2 | 0 | $f(2q)+f(qa)+q(a+8)$
3 | 2’ | 0 | 2 | 3 | 0 | $\log(1/p)+f(qa)+f(q(b+2))+q(a+12)$
3 | 2 | 2 | 1 | 0 | 0 | $\log(1/p)+f(q(a+1))+5q$
3 | 2 | 3 | 1 | 0 | 0 | $\log(1/p)+f(q(b+1))+8q$
3 | 2 | 2 | 2 | 0 | 0 | $f(2q)+f(qa)+q(a+8)$
3 | 2 | 3 | 2 | 0 | 0 | $\log(1/p)+f(qa)+f(q(b+2))+q(a+12)$
Table 3: Transition probabilities for the framed rectangle (sub-)Markov chain
for local two-neighbour bootstrap percolation. The table only features the
transitions which actually contribute to the final result—Theorem 1.3.

###  A.2 Lower bound of (113)

We are now ready to proceed to proving the lower bound of Eq. 113, which gives
the upper bound of Theorem 1.3. Section 5.1 requires essentially no change.
The only difference is that we start our sequence with $a^{(0)}=q^{-2/3}$,
while $a^{(M)}=\Lambda$ remains unchanged (once again, we assume for
simplicity that these are both integers and that an integer $M$ is compatible
with the recurrence relation $a^{(i+1)}-a^{(i)}=\lceil(a^{(i)})^{2/3}\rceil$).
This makes the error term in Eq. 75 of order $\sqrt[6]{q}$ instead, but does
not impact the final result. Furthermore, Eq. 71 is replaced by

${\mathbb{P}}_{p}\left(\mathcal{I}_{\mathrm{loc}}\left(R^{(0)}\right)\right)\geqslant
p^{3}\exp\left(-W_{p}\left(\gamma_{R^{(0)}}\right)\right),$

as provided by Proposition 2.11. It therefore remains to prove the following
analogue of Proposition 5.1 by applying the method of Section 5.2.

######  Proposition A.5 (Coarse step lower bound).

Let $a\geqslant a^{(0)}$ and $b=a+\lceil a^{2/3}\rceil\leqslant\Lambda$. Then

$\frac{{\mathbb{P}}_{p}(\mathcal{I}_{\mathrm{loc}}(R(b,b)))}{{\mathbb{P}}_{p}(\mathcal{I}_{\mathrm{loc}}(R(a,a)))}\geqslant\exp\left(-\frac{2}{q}\int_{aq}^{bq}g+2h_{2}(aq)(b-a)\sqrt{q}-C_{1}^{2}\log(1/q)\right).$

###### Proof.

Fix $a\geqslant a^{(0)}$ and $b=a+\lceil a^{2/3}\rceil\leqslant\Lambda$ and
recall Eq. 118. Since we have already restricted $\mathcal{T}$ to the relevant
transitions, we may directly proceed to the analogue of Lemma 5.2.

######  Lemma A.6 (Probability of a single transition).

Let $(F,F^{\prime})$ be a transition in Table 3 with $F=F(i,j;c,d;s)$ and
$F^{\prime}=F(i-\alpha,j-\beta;c+\gamma,d+\delta;s^{\prime})$, such that
$\\{c-i,d-j\\}\subset[a,b]$. If $s=1\neq s^{\prime}$ and $\alpha=\beta=0$,
then

${\mathbb{P}}_{p}\left(\mathcal{T}(F,F^{\prime})\right)=e^{-\gamma
g(q(d-j))-\delta
g(q(c-i+\gamma))}\times\mathcal{M}_{\gamma,\delta}(aq)\times\begin{cases}e^{O(a^{-1/3})}&s^{\prime}=0,\\\
e^{O(qa^{2/3})}&s^{\prime}=2.\end{cases}$

The same expressions apply for $s\in\\{0,1^{\prime},2,2^{\prime},3\\}$ up to
symmetry.

The proof of Lemma A.6 is analogous to the one of Lemma 5.2 and therefore
omitted. However, note that loops were left out. Indeed we need to pay special
attention to sequences of loops, since there are now two loops per frame state
rather than a single one. This is dealt with by the following lemma.

######  Lemma A.7 (Loop sequences).

Let $F=F(0,0;c,d;1)$ and $F^{\prime}=F(0,0;c,d+\ell;1)$ be framed rectangles
with $\ell\geqslant C_{1}\log(1/q)\max(1,1/\sqrt{cq})$ and $c\in[a,b]$. Then

$\mathcal{T}(F,F^{\prime}):={\mathbb{P}}_{p}\left(\exists t\geqslant
1,\mathcal{F}(t)=F^{\prime}|\mathcal{F}(0)=F\right)\geqslant e^{-\ell
g(cq)}\times\alpha(aq)\times e^{-O(q\ell+\sqrt{q}a^{1/6})}.$

Analogous statements hold for other buffer states.

###### Proof.

Recalling Observations 2.3 and 122, we obtain

$\displaystyle{\mathbb{P}}_{p}\left(\exists t\geqslant
1,\mathcal{F}(t)=F^{\prime}|\mathcal{F}(0)=F\right)$
$\displaystyle{}={\mathbb{P}}_{p}\left(\mathcal{O}^{c}(F^{\prime}_{\square}\setminus
F_{\square})\right){\mathbb{P}}_{p}\left(\mathcal{T}_{\uparrow}(R(c,\ell))\right)$
$\displaystyle{}\geqslant\alpha(cq)e^{-\ell
g(cq)}\left(1-\left(\frac{|\bar{\beta}(e^{-f(cq)})|}{\beta(e^{-f(cq)})}\right)^{\ell+1}\right)e^{-O(q\ell)}$
$\displaystyle{}\geqslant\alpha(cq)e^{-\ell g(cq)}e^{-O(q\ell)},$

using Lemma A.1 in the first inequality and $\ell\geqslant
C_{1}\log(1/q)\max(1,1/\sqrt{cq})$ and the fact that
$|\bar{\beta}(u)|/\beta(u)\leqslant 1-\sqrt{u}/2$ for any $u\in[0,1]$ in the
second one (recall Eqs. 115 and 23). Moreover,

$\displaystyle\alpha(cq)$
$\displaystyle{}\geqslant\alpha(aq)\exp\left(-qO(b-a)\max_{z\in[aq,bq]}\left|(\log\alpha)^{\prime}(z)\right|\right)$
$\displaystyle{}=\alpha(aq)\exp\left(-qO(b-a)/\sqrt{aq}\right)=\alpha(aq)\exp\left(-O\left(\sqrt{q}a^{1/6}\right)\right).\qed$

Consider a possible trajectory $(F(t))_{t\geqslant 0}$ of the (sub-Markovian)
chain $(\mathcal{F}^{R(a,a)}(t))_{t\geqslant 0}$. Let $(F^{(t)})_{t\geqslant
0}$ be the sequence obtained by omitting any $F(t)$ such that the previous and
next transitions are both loops. We call this sequence a _reduced trajectory_.
Similarly, we denote the (random) reduced trajectory associated to
$(\mathcal{F}^{R(a,a)}(t))_{t\geqslant 0}$ by $(\mathcal{F}^{(t)})_{t\geqslant
0}$. Note that the reduced trajectory becomes finite, if
$\mathcal{F}^{R(a,a)}(\infty)$ is finite.

######  Definition A.8 (Good reduced trajectory).

We say that a finite reduced trajectory $(F^{(t)})_{t=0}^{4K+8}$ is _good_ if
it satisfies the following conditions. For each $t\in[0,2K+3]$,

  * •

$F^{(2t)}$ and $F^{(2t+1)}$ have the same frame state,

  * •

$F^{(2t+1)}$ and $F^{(2t+2)}$ have distinct frame states,

  * •

$\phi(F^{(2t+1)})-\phi(F^{(2t)})\geqslant C_{1}\log(1/q)\max(1,1/\sqrt{aq})$.

Assembling Lemmas A.7 and A.6, we obtain that for any fixed good finite
reduced trajectory $(F^{(t)})_{t=0}^{4K+8}$ with $F^{(4K+8)}$ of frame state
$4$, we have151515Note that we use the notation $\mathcal{T}$ from Table 3 and
Lemma A.6 for even and odd $t$ respectively.

${\mathbb{P}}_{p}\left(\forall t\leqslant
4K+8,\mathcal{F}^{(t)}=F^{(t)}\right)=\prod_{t=1}^{4K+8}{\mathbb{P}}_{p}\left(\mathcal{T}\left(F^{(t-1)},F^{(t)}\right)\right)\\\
\geqslant
e^{-W_{p}(\gamma)}\times\prod_{t=0}^{2K+3}(\alpha(aq)\mathcal{M}_{\gamma_{t},\delta_{t}}(aq))\times
e^{-O(q(b-a)+(K+1)(qa^{2/3}+a^{-1/3}+\sqrt{q}a^{1/6}))}$

where $\gamma$ is the piecewise linear path from $(a,a)$ to $(b,b)$
corresponding to the first order terms in Lemmas A.7 and A.6 and
$\gamma_{t},\delta_{t}$ are $\gamma,\delta$ in Lemma A.6 for
$F=F^{(2t+1)},F^{\prime}=F^{(2t+2)}$. Furthermore, Lemma 5.4 applies without
change to $W_{p}$ and $g$. Thus,

${\mathbb{P}}_{p}\left(\forall t\leqslant
4K+8,\mathcal{F}^{(t)}=F^{(t)}\right)\\\
\geqslant\exp\left(-\frac{2}{q}\int_{aq}^{bq}g\right)\times\prod_{t=0}^{2K+3}\left(\alpha(aq)\mathcal{M}_{\gamma_{t},\delta_{t}}(aq)\right)\times
e^{-O(1+(K+1)(qa^{2/3}+a^{-1/3}))}.$

We now set $K$ to be given by Eq. 79 with $h_{2}$ instead of $h$ (recall Eq.
119). The last ingredient we need is an analogue of Eq. 80. Namely, we seek to
bound the number $N(\Gamma)$ of good finite reduced trajectories
$(F^{(t)})_{t=0}^{4K+8}$ with $F^{(0)}=F(0,0;a,a;0)$,
$F^{(4K+8)}=F(-x,-y;b-x,b-y;4)$ for any $(x,y)\in{\mathbb{Z}}^{2}$ featuring a
given sequence $\Gamma=(\gamma_{t},\delta_{t})_{t=0}^{2K+3}$. Note that
$\gamma_{t}$ for odd $t$ and $\delta_{t}$ for even $t$ correspond to extending
rectangles in the horizontal directions, while the remaining $\gamma_{t}$ and
$\delta_{t}$ are vertical extensions. Let

$\displaystyle\alpha$
$\displaystyle{}=\sum_{t=0}^{K+1}\delta_{2t}+\gamma_{2t+1},$
$\displaystyle\beta$
$\displaystyle{}=\sum_{t=0}^{K+1}\gamma_{2t}+\delta_{2t+1}$

and $m=\lceil C_{1}\log(1/q)\max(1,1/\sqrt{aq})\rceil\leqslant
2C_{1}\log(1/q)a^{-1/4}$ (since $a\geqslant a^{(0)}$). Then

$\displaystyle N(\Gamma)$
$\displaystyle{}=\binom{b-a-\alpha-m(K+2)+(K+1)}{K+1}\binom{b-a-\beta-m(K+2)+(K+1)}{K+1}$
$\displaystyle{}\geqslant\binom{b-a-2mK}{K}^{2}.$

Proceeding as in Eqs. 76, 82 and 83 we conclude that

$\frac{{\mathbb{P}}_{p}(\mathcal{I}_{\mathrm{loc}}(R(a,a)))}{{\mathbb{P}}_{p}(\mathcal{I}_{\mathrm{loc}}(R(b,b)))}\\\
\geqslant\exp\left(-\frac{2}{q}\int_{aq}^{bq}g\right)\times
e^{2h_{2}(aq)(b-a)\sqrt{q}}\times
e^{-O(C_{1})\log(1/q)}\left(1-\frac{O(mK)}{b-a}\right)^{O(K)}.$

This concludes the proof of Proposition A.5, since, recalling Eq. 79 gives

$\frac{mK^{2}}{b-a}\leqslant\frac{O(C_{1})\log(1/q)a^{-1/4+2/6}}{a^{2/3}}\leqslant
a^{-1/13}\leqslant q^{1/20},$

so that

$\left(1-\frac{O(mK)}{b-a}\right)^{O(K)}\geqslant 1/2.\qed$

## References