solution $T_{t}^{\prime}$ for this problem in time step $t$ on $T$ and let our
solution in time step $t$ on $G$ be $T_{t}:=\pi_{T\to G}(T_{t}^{\prime})$.

The properties of our $h$-hop repetition tree embeddings immediately give the
desired properties of our algorithm.

######  Theorem 11.

There is a poly-time algorithm for online hop-constrained group Steiner tree
which with high probability maintains a solution $\\{T_{t}\\}_{t}$ that is
$O(\log k\cdot\log^{5}n)$-cost-competitive in expectation where
$\mathrm{hop}_{T_{t}}(r,g_{i})\leq O(\log^{3}n\cdot h)$ for all $t$ and $i\leq
t$.

###### Proof.

We use the above algorithm. The root mapping and $\beta$-approximate $h$-hop
connectivity preservation properties of our $h$-hop repetition tree embedding
along with the feasibility of $T_{t}^{\prime}$ guarantees that our solution
$T_{t}$ connects $g_{i}$ to $r$ for every $i\leq t$ with at most
$O(h\cdot\log^{3}n)$ hops. The bound on our cost comes from combining the fact
that $\pi_{G\to T}(T^{*}_{t})$ is feasible for the group Steiner tree instance
we solve on $T$ in time step $t$ where $T^{*}_{t}$ is the optimal solution on
$G$ in time step $t$, the $O(\log^{3}n)$-approximate cost preservation of our
$h$-hop tree embedding and the cost guarantee of Theorem 10. ∎

###  8.3 Hop-Constrained Group Steiner Forest

As both group Steiner tree and Steiner forest are special cases of it, the
group Steiner forest is one of the most general studied connectivity problems;
for this reason it is also sometimes referred to as the “generalized
connectivity problem.”

Problem: In the group Steiner forest problem we are given a weighted graph
$G=(V,E,w)$ as well as pairs of subsets of nodes
$(S_{1},T_{1}),(S_{2},T_{2}),\ldots,(S_{k},T_{k})$ where $S_{i},T_{i}\subseteq
V$. Our goal is to find a forest $F$ which is a subgraph of $G$ and in which
for each $i$ there is an $s_{i}\in S_{i}$ and $t_{i}\in T_{i}$ such that
$s_{i}$ and $t_{i}$ are connected in $F$. We wish to minimize our cost,
$w(F):=\sum_{e\in E(F)}w(e)$. In hop-constrained group Steiner forest we are
additionally given a hop bound $h\geq 1$ and for every $i$ we must ensure that
$\mathrm{hop}_{F}(s_{i},t_{i})\leq h$ for some $s_{i}\in S_{i}$ and $t_{i}\in
T_{i}$. We will use the shorthand
$\mathrm{hop}_{F}(S_{i},T_{i}):=\min_{s_{i}\in S_{i},t_{i}\in
T_{i}}\mathrm{hop}_{F}(s_{i},t_{i})$.

Related Work: [2] introduced the group Steiner forest problem to study online
network formation. [22] gave the first poly-log approximation algorithm for
group Steiner forest. [57] gave a worse poly-log approximation for group
Steiner forest but one which was based on tree embeddings which will be useful
for our purposes.

Algorithm: We use our repetition tree embeddings to reduce hop-constrained
group Steiner forest to the tree case. We then apply an algorithm of [57]
which shows how to solve group Steiner forest on trees.

######  Theorem 12 ([57]).

There is a poly-time algorithm for group Steiner forest on trees of depth $d$
which achieves an approximation ratio of $O(d\cdot\log^{2}n\log k)$ with high
probability.

Formally, we first apply Theorem 8 to sample a repetition tree $T$ with depth
$O(\log n)$, an arbitrary root and mappings $\phi$, $\pi_{G\to T}$ and
$\pi_{T\to G}$. Next, we apply Theorem 12 to solve the group Steiner forest on
$T$ with pairs to be connected
$(S_{1}^{\prime},T_{1}^{\prime}),\ldots(S_{k}^{\prime},T_{k}^{\prime})$ where
$S_{i}^{\prime}:=\bigcup_{v\in S_{i}}\phi(v)$ and symmetrically
$T_{i}^{\prime}:=\bigcup_{v\in T_{i}}\phi(v)$. Let $F^{\prime}$ be the
resulting solution on $T$. We return as our solution $F:=\pi_{T\to
G}(F^{\prime})$.

######  Theorem 13.

There is a poly-time algorithm for $h$-hop-constrained group Steiner forest
which with high probability returns a solution $F$ such that $w(F)\leq
O(\mathrm{OPT}\cdot\log^{6}n\log k)$ and $\mathrm{hop}_{F}(S_{i},T_{i})\leq
O(h\cdot\log^{3}n)$ for every $i$.

###### Proof.

We use the above algorithm. A polynomial runtime is immediate from Theorem 8
and Theorem 12. The hop guarantee is immediate from the correctness of the
algorithm of Theorem 12 and the properties of $\pi_{T\to G}$ as given in
Theorem 8. To see the bound on cost, notice that $\pi_{G\to T}(F^{*})$ is
feasible for the group Steiner forest problem that we solve on $T$ and has
cost at most $O(\log^{3}n\cdot\mathrm{OPT})$ by the properties of $\pi_{G\to
T}$ as specified in Theorem 8 where $F^{*}$ is the optimal solution to the
input group Steiner forest problem on $G$. The bound then follows from the
fact that $T$ is well-separated and so has depth at most $O(\log n)$. ∎

###  8.4 Online Hop-Constrained Group Steiner Forest

In this section we give our algorithm for online hop-constrained group Steiner
forest. It follows, almost immediately, from our $h$-hop repetition tree
embeddings and a result of [57] for online group Steiner forest on trees.

Problem: Online group Steiner forest is the same as group Steiner forest as
defined in Section 8.3 but each pair $(S_{t},T_{t})$ is revealed at time step
$t=1,2,\ldots$ by an adversary and in each time step $t$ we must maintain a
forest $F_{t}$ which is feasible for pairs $(S_{1},T_{1}),\ldots(S_{t},T_{t})$
so that $F_{t-1}\subseteq F_{t}$. The competitive ratio of an online algorithm
with solution $\\{F_{t}\\}_{t}$ is $\max_{t}w(F_{t})/\mathrm{OPT}_{t}$ where
$\mathrm{OPT}_{t}$ is the optimal offline solution for the group Steiner
forest problem we must solve in time step $t$. Online hop-constrained group
Steiner forest is the same as online group Steiner forest but we are given a
hop constraint $h$ and we must ensure that for each $t$ and $i\leq t$ there is
some $s_{i}\in S_{i}$ and $t_{i}\in T_{i}$ such that
$\mathrm{hop}_{F_{t}}(s_{i},t_{i})\leq h$. We assume that the possible pairs
revealed by the adversary are known ahead of time as otherwise this problem is
known to admit no sub-polynomial approximations [2] and let $k$ be the number
of possible pairs.

Related work: The existence of a poly-log-competitive online algorithm for
group Steiner forest was first posed as an open question by [22]. [57]
answered this question in the affirmative by showing that such an algorithm
exists.

Algorithm: We use our repetition tree embeddings to reduce online hop-
constrained group Steiner forest to the tree case. We then apply an algorithm
of [57] which shows how to solve group Steiner forest on trees.

######  Theorem 14 ([57]).

There is a randomized poly-time algorithm for group Steiner forest on trees of
depth $d$ with expected competitive ratio $O(d\cdot\log^{3}n\log k)$.

Formally, we first apply Theorem 8 to sample a repetition tree $T$ with depth
$O(\log n)$, an arbitrary root and mappings $\phi$, $\pi_{G\to T}$ and
$\pi_{T\to G}$. Next, we apply Theorem 14 to solve the online group Steiner
forest on $T$ with pairs to be connected
$(S_{1}^{\prime},T_{1}^{\prime}),\ldots(S_{t}^{\prime},T_{t}^{\prime})$ in
time step $t$ where $S_{i}^{\prime}:=\bigcup_{v\in S_{i}}\phi(v)$ and
symmetrically $T_{i}^{\prime}:=\bigcup_{v\in T_{i}}\phi(v)$. Let
$F^{\prime}_{t}$ be the resulting solution on $T$ in time step $t$. In time
step $t$ we return as our solution on $G$ the subgraph $F_{t}:=\pi_{T\to
G}(F^{\prime}_{t})$.

We conclude with the properties of our online group Steiner forest algorithm.

######  Theorem 15.

There is a poly-time algorithm for online $h$-hop-constrained group Steiner
forest which with high probability maintains a solution $\\{F_{t}\\}_{t}$ that
is $O(\log^{7}n\log k)$-cost-competitive in expectation where
$\mathrm{hop}_{F_{t}}(S_{i},T_{i})\leq O(h\cdot\log^{3}n)$ for all $t$ and
$i\leq t$.

###### Proof.

We use the above algorithm. A polynomial runtime is immediate from Theorem 8
and Theorem 14. The hop guarantee is immediate from the correctness of the
algorithm of Theorem 14 and the properties of $\pi_{T\to G}$ as given in
Theorem 8. To see the bound on cost, notice that $\pi_{G\to T}(F^{*}_{t})$ is
feasible for the group Steiner forest problem that we solve on $T$ and has
cost at most $O(\log^{3}n\cdot\mathrm{OPT})$ by the properties of $\pi_{G\to
T}$ as specified in Theorem 8 where $F^{*}_{t}$ is the optimal solution to the
input group Steiner forest problem on $G$ in time step $t$. The bound then
follows from the fact that $T$ is well-separated and so has depth at most
$O(\log n)$. ∎

##  9 Conclusion and Future Work

In this work we showed that, while far from any metric, hop-constrained
distances are well-approximated by partial tree metrics. We used this fact to
develop new embeddings for hop-constrained distances which we then used to
give the first bicriteria (poly-log, poly-log) approximation algorithms for
many classic network design problems.

We conclude by giving directions for future work. Reducing the stretch in our
embeddings, or proving lower bounds stronger than those immediately implied by
the FRT lower bounds is our main open question. Improving the upper bounds in
our embeddings—as in the FRT setting—has the benefit that doing so immediately
improves the approximation ratios for the many algorithms we gave in this
paper. We note that, like the embeddings of [11], our embeddings are built
around the paddedness of certain decompositions and these embeddings were
later improved by FRT [37]. One might naturally wonder, then, if an FRT-like
analysis might improve our stretch guarantees; from what we can tell no such
FRT-type proof seems capable of improving our bounds. Another point to note is
that we lose an $O(\log n)$ in the hop stretch when moving from partial tree
metrics to partial tree embeddings. This loss does not seem to have an
analogue in the (non-partial) tree embedding setting and it is not clear if
such a loss is necessary.

Moreover, while tree embeddings have proven useful for many network design
problems, there are many other problems such as $k$-server [13], metrical task
systems [12] and requirement cuts [58] where tree embeddings enabled the first
poly-log approximations. Thus, while the focus of our paper has been on the
hop-constrained versions of network design problems, we expect that our
embeddings will prove useful for the hop-constrained versions of many of these
other problems.

Lastly, as we discussed at the end of Section 5, our $h$-hop partial tree
embeddings are built on the worst-case stretch guarantees of our partial
metrics; it would be interesting if it were possible to construct embeddings
based on the expected stretch guarantees of our partial metrics. Such a result
would immediately give several randomized algorithms for hop-constrained
problems with low expected cost.

## References

  * AA [97] Baruch Awerbuch and Yossi Azar.  Buy-at-bulk network design.  In Symposium on Foundations of Computer Science (FOCS), pages 542–547. IEEE, 1997.
  * AAA+ [06] Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor.  A general approach to online network optimization problems.  ACM Transactions on Algorithms (TALG), 2(4):640–660, 2006.
  * ABN [08] Ittai Abraham, Yair Bartal, and Ofer Neiman.  Nearly tight low stretch spanning trees.  In Symposium on Foundations of Computer Science (FOCS), pages 781–790. IEEE, 2008.
  * AFHP+ [05] Ernst Althaus, Stefan Funke, Sariel Har-Peled, Jochen Könemann, Edgar A Ramos, and Martin Skutella.  Approximating k-hop minimum-spanning trees.  Operations Research Letters, 33(2):115–120, 2005.
  * AGG+ [19] Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, and Kunal Talwar.  Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs.  SIAM Journal on Computing, 48(3):1120–1145, 2019.
  * AKPW [95] Noga Alon, Richard M Karp, David Peleg, and Douglas West.  A graph-theoretic game and its application to the k-server problem.  SIAM Journal on Computing, 24(1):78–100, 1995.
  * AKR [95] Ajit Agrawal, Philip Klein, and Ramamoorthi Ravi.  When trees collide: An approximation algorithm for the generalized steiner problem on networks.  SIAM Journal on Computing, 24(3):440–456, 1995.
  * AN [12] Ittai Abraham and Ofer Neiman.  Using petal-decompositions to build a low stretch spanning tree.  In Annual ACM Symposium on Theory of Computing (STOC), pages 395–406, 2012.
  * AT [11] İbrahim Akgün and Barbaros Ç Tansel.  New formulations of the hop-constrained minimum spanning tree problem via miller–tucker–zemlin constraints.  European Journal of Operational Research, 212(2):263–276, 2011\.
  * Bar [96] Yair Bartal.  Probabilistic approximation of metric spaces and its algorithmic applications.  In Symposium on Foundations of Computer Science (FOCS), pages 184–193. IEEE, 1996.
  * Bar [98] Yair Bartal.  On approximating arbitrary metrices by tree metrics.  In Annual ACM Symposium on Theory of Computing (STOC), pages 161–168, 1998.
  * BBBT [97] Yair Bartal, Avrim Blum, Carl Burch, and Andrew Tomkins.  A polylog (n)-competitive algorithm for metrical task systems.  In Annual ACM Symposium on Theory of Computing (STOC), pages 711–719, 1997.
  * BBMN [11] Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph Naor.  A polylogarithmic-competitive algorithm for the k-server problem.  In Symposium on Foundations of Computer Science (FOCS), pages 267–276. IEEE, 2011.
  * BC [97] Piotr Berman and Chris Coulston.  On-line algorithms for steiner tree problems.  In Annual ACM Symposium on Theory of Computing (STOC), pages 344–353, 1997.
  * BFG [15] Quentin Botton, Bernard Fortz, and Luis Gouveia.  On the hop-constrained survivable network design problem with reliable edges.  Computers & Operations Research, 64:159–167, 2015.
  * BFGP [13] Quentin Botton, Bernard Fortz, Luis Gouveia, and Michael Poss.  Benders decomposition for the hop-constrained survivable network design problem.  INFORMS journal on computing, 25(1):13–26, 2013.
  * BFU [20] Yair Bartal, Nova Fandina, and Seeun William Umboh.  Online probabilistic metric embedding: a general framework for bypassing inherent bounds.  In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1538–1557. SIAM, 2020.
  * BHR [13] Andreas Bley, S Mehdi Hashemi, and Mohsen Rezapour.  Ip modeling of the survivable hop constrained connected facility location problem.  Electronic Notes in Discrete Mathematics, 41:463–470, 2013.
  * BIKP [01] Judit Bar-Ilan, Guy Kortsarz, and David Peleg.  Generalized submodular cover problems and applications.  Theoretical Computer Science, 250(1-2):179–200, 2001.
  * CCGG [98] Moses Charikar, Chandra Chekuri, Ashish Goel, and Sudipto Guha.  Rounding via trees: deterministic approximation algorithms for group steiner trees and k-median.  In Annual ACM Symposium on Theory of Computing (STOC), pages 114–123, 1998.
  * CD [16] Eden Chlamtáč and Michael Dinitz.  Lowest-degree $k$-spanner: Approximation and hardness.  Theory of Computing, 12(1):1–29, 2016.
  * CEGS [11] Chandra Chekuri, Guy Even, Anupam Gupta, and Danny Segev.  Set connectivity problems in undirected graphs and the directed steiner network problem.  ACM Transactions on Algorithms (TALG), 7(2):1–17, 2011.
  * CEK [06] Chandra Chekuri, Guy Even, and Guy Kortsarz.  A greedy approximation algorithm for the group steiner problem.  Discrete Applied Mathematics, 154(1):15–34, 2006.
  * CZ [20] Shiri Chechik and Tianyi Zhang.  Dynamic low-stretch spanning trees in subpolynomial time.  In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 463–475. SIAM, 2020.
  * DBF [18] Jérôme De Boeck and Bernard Fortz.  Extended formulation for hop constrained distribution network configuration problems.  European Journal of Operational Research, 265(2):488–502, 2018\.
  * DGM+ [16] Ibrahima Diarrassouba, Virginie Gabrel, Ali Ridha Mahjoub, Luís Gouveia, and Pierre Pesneau.  Integer programming formulations for the k-edge-connected 3-hop-constrained network design problem.  Networks, 67(2):148–169, 2016.
  * DHK [09] Erik D Demaine, MohammadTaghi Hajiaghayi, and Philip N Klein.  Node-weighted steiner tree and group steiner tree in planar graphs.  In International Colloquium on Automata, Languages and Programming (ICALP), pages 328–340. Springer, 2009.
  * DKR [12] Michael Dinitz, Guy Kortsarz, and Ran Raz.  Min-rep instances with large supergirth and the hardness of approximating basic spanners.  In International Colloquium on Automata, Languages and Programming (ICALP), 2012.
  * DKR [15] Michael Dinitz, Guy Kortsarz, and Ran Raz.  Label cover instances with large girth and the hardness of approximating basic k-spanner.  ACM Transactions on Algorithms (TALG), 12(2):1–16, 2015.
  * DMMY [18] Ibrahima Diarrassouba, Meriem Mahjoub, A Ridha Mahjoub, and Hande Yaman.  k-node-disjoint hop-constrained survivable networks: polyhedral analysis and branch and cut.  Annals of Telecommunications, 73(1-2):5–28, 2018.
  * DZ [16] Michael Dinitz and Zeyu Zhang.  Approximating low-stretch spanners.  In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 821–840. SIAM, 2016.
  * EEST [08] Michael Elkin, Yuval Emek, Daniel A Spielman, and Shang-Hua Teng.  Lower-stretch spanning trees.  SIAM Journal on Computing, 38(2):608–628, 2008.
  * EP [99] Michael Elkin and David Peleg.  The client-server 2-spanner problem and applications to network design.  In International Colloquium on Structural Information and Communication Complexity, 1999.
  * EP [00] Michael Elkin and David Peleg.  Strong inapproximability of the basic k-spanner problem.  In International Colloquium on Automata, Languages and Programming (ICALP), pages 636–648. Springer, 2000.
  * EP [05] Michael Elkin and David Peleg.  Approximating k-spanner problems for k¿ 2.  Theoretical Computer Science, 337(1-3):249–277, 2005.
  * FGH [20] Sebastian Forster, Gramoz Goranci, and Monika Henzinger.  Dynamic maintanance of low-stretch probabilistic tree embeddings with applications.  arXiv preprint arXiv:2004.10319, 2020.
  * FRT [04] Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar.  A tight bound on approximating arbitrary metrics by tree metrics.  Journal of Computer and System Sciences, 69(3):485–497, 2004.
  * GHR [06] Anupam Gupta, Mohammad T Hajiaghayi, and Harald Räcke.  Oblivious network design.  In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 970–979, 2006.
  * GKL [03] Anupam Gupta, Robert Krauthgamer, and James R Lee.  Bounded geometries, fractals, and low-distortion embeddings.  In Symposium on Foundations of Computer Science (FOCS), pages 534–543. IEEE, 2003.
  * GKR [00] Naveen Garg, Goran Konjevod, and R Ravi.  A polylogarithmic approximation algorithm for the group steiner tree problem.  Journal of Algorithms, 37(1):66–84, 2000.
  * GM [03] Luis Gouveia and Thomas L Magnanti.  Network flow models for designing diameter-constrained minimum-spanning and steiner trees.  Networks: An International Journal, 41(3):159–173, 2003.
  * Gou [95] Luis Gouveia.  Using the miller-tucker-zemlin constraints to formulate a minimal spanning tree problem with hop constraints.  Computers & Operations Research, 22(9):959–970, 1995.
  * Gou [96] Luis Gouveia.  Multicommodity flow models for spanning trees with hop constraints.  European Journal of Operational Research, 95(1):178–190, 1996.
  * GR [01] Luis Gouveia and Cristina Requejo.  A new lagrangean relaxation approach for the hop-constrained minimum spanning tree problem.  European Journal of Operational Research, 132(3):539–552, 2001\.
  * HHZ [20] Bernhard Haeupler, D Ellis Hershkowitz, and Goran Zuzic.  Deterministic repetition tree embeddings and online connectivity.  In arXiv Preprint, 2020.
  * HKS [09] Mohammad Taghi Hajiaghayi, Guy Kortsarz, and Mohammad R Salavatipour.  Approximating buy-at-bulk and shallow-light k-steiner trees.  Algorithmica, 53(1):89–103, 2009.
  * Kar [89] Richard M Karp.  A 2k-competitive algorithm for the circle.  Manuscript, August, 5, 1989.
  * KKM+ [12] Maleq Khan, Fabian Kuhn, Dahlia Malkhi, Gopal Pandurangan, and Kunal Talwar.  Efficient distributed approximation algorithms via probabilistic tree embeddings.  Distributed Computing, 25(3):189–205, 2012.
  * KLS [05] Jochen Könemann, Asaf Levin, and Amitabh Sinha.  Approximating the degree-bounded minimum diameter spanning tree problem.  Algorithmica, 41(2):117–129, 2005.
  * KMP [11] Ioannis Koutis, Gary L Miller, and Richard Peng.  A nearly-m log n time solver for sdd linear systems.  In Symposium on Foundations of Computer Science (FOCS), pages 590–598. IEEE, 2011.
  * KP [97] Guy Kortsarz and David Peleg.  Approximating shallow-light trees.  In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 103–110, 1997.
  * KP [09] Erez Kantor and David Peleg.  Approximate hierarchical facility location and applications to the bounded depth steiner tree and range assignment problems.  Journal of Discrete Algorithms, 7(3):341–362, 2009.
  * KRS [01] Goran Konjevod, R Ravi, and F Sibel Salman.  On approximating planar metrics by tree metrics.  Information Processing Letters (IPL), 80(4):213–219, 2001.
  * KS [11] M Reza Khani and Mohammad R Salavatipour.  Improved approximations for buy-at-bulk and shallow-light k-steiner trees and (k, 2)-subgraph.  In Annual International Symposium on Algorithms and Computation (ISAAC), pages 20–29. Springer, 2011.
  * Lei [16] Markus Leitner.  Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem.  Computers & Operations Research, 65:1–18, 2016.
  * MRS+ [98] Madhav V Marathe, Ramamoorthi Ravi, Ravi Sundaram, SS Ravi, Daniel J Rosenkrantz, and Harry B Hunt III.  Bicriteria network design problems.  Journal of algorithms, 28(1):142–171, 1998.
  * NPS [11] Joseph Naor, Debmalya Panigrahi, and Mohit Singh.  Online node-weighted steiner tree and related problems.  In Symposium on Foundations of Computer Science (FOCS), pages 210–219. IEEE, 2011.
  * NR [05] Viswanath Nagarajan and Ramamoorthi Ravi.  Approximation algorithms for requirement cut on graphs.  In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 209–220. Springer, 2005.
  * NS [97] Joseph Naor and Baruch Schieber.  Improved approximations for shallow-light spanning trees.  In Symposium on Foundations of Computer Science (FOCS), pages 536–541. IEEE, 1997.
  * Rac [02] Harald Racke.  Minimizing congestion in general networks.  In Symposium on Foundations of Computer Science (FOCS), pages 43–52. IEEE, 2002.
  * RAJ [12] André Rossi, Alexis Aubry, and Mireille Jacomino.  Connectivity-and-hop-constrained design of electricity distribution networks.  European journal of operational research, 218(1):48–57, 2012.
  * Rav [94] R Ravi.  Rapid rumor ramification: Approximating the minimum broadcast time.  In Symposium on Foundations of Computer Science (FOCS), pages 202–213. IEEE, 1994.
  * TCG [15] Babacar Thiongane, Jean-François Cordeau, and Bernard Gendron.  Formulations for the nonbifurcated hop-constrained multicommodity capacitated fixed-charge network design problem.  Computers & Operations Research, 53:1–8, 2015.
  * Voß [99] Stefan Voß.  The steiner tree problem with hop constraints.  Annals of Operations Research, 86:321–345, 1999.
  * WA [88] Kathleen A Woolston and Susan L Albin.  The design of centralized networks with reliability and availability constraints.  Computers & Operations Research, 15(3):207–217, 1988.


# E-Bench: Towards Evaluating the Ease-of-Use of Large Language Models

Zhenyu Zhang† , Bingguang Hao‡∗, Jinpeng Li‡, Zekai Zhang‡, Dongyan Zhao‡
†Baidu Inc.
‡Wangxuan Institute of Computer Technology, Peking University
<EMAIL_ADDRESS><EMAIL_ADDRESS>
Equal contribution

###### Abstract

Most large language models (LLMs) are sensitive to prompts, and another
synonymous expression or a typo may lead to unexpected results for the model.
Composing an optimal prompt for a specific demand lacks theoretical support
and relies entirely on human experimentation, which poses a considerable
obstacle to popularizing generative artificial intelligence. However, there is
no systematic analysis of the stability of LLMs in resisting prompt
perturbations in real-world scenarios. In this work, we propose to evaluate
the ease-of-use of LLMs and construct E-Bench, simulating the actual situation
of human use from synonymous perturbation (including paraphrasing,
simplification, and colloquialism) and typographical perturbation (such as
typing). On this basis, we also discuss the combination of these two types of
perturbation and analyze the main reasons for performance degradation.
Experimental results indicate that with the increase of model size, although
the ease-of-use are significantly improved, there is still a long way to go to
build a sufficiently user-friendly model.

##  1 Introduction

Large language models (LLMs) have swept across the entire natural language
processing (NLP) fields, revolutionizing many domains and attracting
unprecedented attention. Benefiting from the powerful instruction following
and language generation capabilities, the application scenarios of modern LLMs
are gradually expanding and being used as productivity tools. By exploring
natural language exquisite prompts, LLMs could handle various demands, such as
question answering, data construction, and intelligent agent Jakesch et al.
(2023); Wu and Hu (2023); Xu et al. (2023).

Figure 1: The prompt perturbations in E-Bench, which simulate the actual
situations of humans using LLMs.

Yet, LLMs are prompt-driven, the performance of downstream tasks significantly
depends on the quality of the prompt used to steer the model. Inappropriate
prompts are insufficient to meet target tasks, and most effective prompts are
handmade by humans Zhou et al. (2022); Kaddour et al. (2023); Sclar et al.
(2024). In this process, there is no reliable theoretical basis or prior
indication of what kind of prompt is optimal for a specific task. Users write
a prompt, verify its validity, and refine the prompt iteratively, like opening
a “surprise box”. It even gives birth to a new field, prompt engineering,
which attempts to explore how to write prompts to improve the efficiency of
direct interaction between humans and deep generative models Cao et al.
(2023); Chen et al. (2023); Gu et al. (2023).

The sensitivity of LLMs to prompt is a huge obstacle in their usage. For
example, no one knows what kind of performance a good prompt on ChatGPT will
have on GPT-4. In contrast, human conversational abilities are general,
flexible, and robust, different expressions with the same semantics will not
confuse different people Peng et al. (2021). Recently, there have been some
works on evaluating the robustness of LLMs Wang et al. (2023b); Zhu et al.
(2023); Mousavi et al. (2024). However, they mainly focus on the perspective
of out-of-distribution problems or adversarial prompts of NLP tasks, rather
than prompt perturbations in the most commonly used conversational scenarios,
which is precisely the key to pushing LLMs away from tedious prompt
engineering. In other words, they still have not answered well whether a model
is convenient enough for human use. A robust LLM should be able to
consistently provide accurate and relevant responses across a series of
synonymous prompts, which helps improve the usability.

In this paper, we fuel research in this direction by introducing E-Bench, a
comprehensive benchmark designed for understanding the impact of prompt
perturbation and evaluating the ease-of-use of LLMs. Here, an ideal model is
expected to handle synonymous and even typographical prompts like humans
swimmingly. Starting from existing evaluation set AlpacaEval Li et al. (2023),
we divide it into four parts according to data characteristics and perturb the
prompts through paraphrasing, simplification, colloquialism, and typing
attacks. Figure 1 provides an illustration for each perturbation.
Specifically, we first perturb each prompt with a series of automatic tools,
then manually review to ensure that the prompts before and after perturbation
have similar semantics and do not affect human understanding. Performance drop
is used as evaluation metric, where the closer the performance on perturbed
prompts is to original performance, the higher ease-of-use of the model.

With E-Bench, we conduct experiments to evaluate the ease-of-use of 6
representative LLMs, including Llama2-chat models Touvron et al. (2023),
Vicunas Chiang et al. (2023), and GPTs Achiam et al. (2023). The results
demonstrate that all models experience varying performance degradation after
prompt perturbation, and larger models perform better under synonymous
perturbation, while there is no clear scaling law for model size and
performance degradation under typing attack. Overall, improving the ease-of-
use of LLMs is an urgent research topic. Furthermore, additional analysis
reveals the impact of training data on the specific aspect of ease-of-use. We
hope that E-Bench could provide a stepping stone for the popularization of
general artificial intelligence (GAI).

Dataset |  | #Ins | Avg. Len.
---|---|---|---
| Orig. | Pert.
AlpacaEval Li et al. (2023) | 805 | 28.83 | -
E-Bench | Paraphrasing | 200 | 25.22 | 24.56
Simplification | 200 | 47.21 | 32.28
Colloquialism | 200 | 15.66 | 20.26
Typing Attack | 205 | 27.28 | 27.30
Typing Attack∗ | 805 | 26.10 | 26.73

Table 1: Statistics of E-Bench, in which typing attack has its own evaluation
set and could also be combined with other perturbations (marked by $*$).

| Paraphrasing | Simplification | Colloquialism | Overall
---|---|---|---|---
Models | Orig. | Pert. | $\Delta$ | Orig. | Pert. | $\Delta$ | Orig. | Pert. | $\Delta$ | Orig. | Pert. | $\Delta$
Llama 2-chat (7b) | 71.00 | 62.00 | 9.00 | 69.00 | 62.31 | 6.69 | 72.50 | 56.50 | 16.00 | 70.83 | 60.27 | 10.56
Llama 2-chat (13b) | 81.00 | 78.00 | 3.00 | 76.38 | 74.37 | 2.01 | 79.00 | 69.00 | 10.00 | 78.79 | 73.79 | 5.00
Vicuna-v1.5 (7b) | 77.50 | 70.00 | 7.50 | 73.62 | 67.50 | 6.12 | 73.25 | 72.11 | 1.14 | 74.79 | 69.87 | 4.92
Vicuna-v1.5 (13b) | 80.50 | 74.50 | 6.00 | 79.75 | 81.25 | -1.50 | 82.25 | 79.65 | 2.60 | 80.83 | 78.47 | 2.37
GPT-3.5 (24.01) | 85.93 | 84.00 | 1.93 | 92.21 | 84.50 | 7.71 | 89.75 | 83.25 | 6.50 | 89.27 | 83.92 | 5.38
GPT-4 (24.01) | 95.48 | 94.25 | 1.23 | 94.00 | 90.50 | 3.50 | 92.25 | 89.75 | 2.50 | 93.91 | 91.50 | 2.41
Overall | 81.90 | 77.13 | 4.78 | 80.83 | 76.74 | 4.09 | 81.50 | 75.04 | 6.46 | 81.41 | 76.30 | 5.11
| Paraphrasing | Simplification | Colloquialism | Typing Attack | Overall
Models | +Att. | $\Delta$ | +Att. | $\Delta$ | +Att. | $\Delta$ | Orig. | +Att. | $\Delta$ | Orig. | +Att. | $\Delta$
Llama 2-chat (7b) | 33.17 | 28.83 | 30.50 | 31.81 | 33.84 | 22.66 | 73.28 | 59.50 | 13.78 | 63.52 | 39.25 | 24.27
Llama 2-chat (13b) | 39.50 | 38.50 | 42.50 | 31.87 | 38.50 | 30.50 | 75.85 | 60.98 | 14.87 | 74.31 | 45.37 | 28.94
Vicuna-v1.5 (7b) | 42.50 | 27.50 | 41.50 | 26.00 | 49.50 | 22.61 | 75.36 | 61.71 | 13.65 | 71.24 | 48.80 | 22.44
Vicuna-v1.5 (13b) | 44.50 | 30.00 | 45.00 | 36.25 | 50.25 | 29.40 | 84.30 | 71.50 | 12.80 | 79.93 | 52.81 | 27.11
GPT-3.5 (24.01) | 50.00 | 34.00 | 51.50 | 33.00 | 58.75 | 24.50 | 93.41 | 82.61 | 10.80 | 86.29 | 60.72 | 25.57
GPT-4 (24.01) | 58.00 | 36.25 | 63.50 | 27.00 | 68.00 | 21.75 | 93.96 | 88.65 | 5.31 | 92.12 | 69.54 | 22.58
Overall | 44.61 | 32.51 | 45.75 | 30.99 | 49.81 | 25.24 | 82.69 | 70.83 | 11.87 | 77.90 | 52.75 | 25.15

Table 2: Main results on E-Bench, where ‘Orig.’, ‘Pert.’, and ’+Att.’ refer
the performance of on original, perturbed, and attacked prompts, respectively,
‘$\Delta$’ indicates the preference drop. See Appendix B for statistical
analysis.

##  2 E-Bench

Inspired by actual scenarios, we first consider different expressions of the
same semantics, including paraphrasing, simplification, and colloquialism. In
practical terms: 1) paraphrasing is the simplest form of expression conversion
and will not significantly impact the length of prompt. 2) simplification is a
quality in which users express their intents using fewer words to be concise.
3) colloquialism converts written style prompts into spoken forms, usually
with modal particles and increased length. Furthermore, we simulate the typo
issues during prompt input and carry out char/word-based attacks on the
original input or after each synonymous perturbation above.

###  2.1 Construction

We reconstruct AlpacaEval Li et al. (2023), an automatic evaluator for
instruction-following models with 805 examples, to perform the ease-of-use
evaluation. The dataset is divided into four parts. First, 205 instances are
randomly selected for typing attack. Then, the remaining 600 instances are
arranged according to prompt length and divided into three parts: the shortest
part is used for colloquialism, the longest part is for simplification, and
the part with moderate length is for paraphrasing.

Paraphrasing. It exists widely because different users have different language
habits. Here, we focus on assessing the stability of the model when dealing
with varying inputs with the same semantics. We use GPT-4 to assist in
candidate synonymous perturbations. (more details in Appendix A).

Simplification. There is no consensus on whether prompt should be detailed or
concise. In this setting, we assess model effectiveness when users use fewer
words, that is, considering the impact of input length on model performance.

Colloquialism. The difference between spoken language and written language
lies in different expressions and possible disfluency. Consider a conversation
system where colloquialism is common, and LLMs typically accept the results
after automatic speech recognition (ASR).

Typing Attack. Typing errors are widespread in practice scenarios; one may
mistakenly touch the surrounding keys when typing, or optical character
recognition (OCR) errors may result in similar-looking characters. To simulate
such cases, we use GAN Zhao et al. (2018), TextBugger Li et al. (2018), PWWS
Ren et al. (2019) and perform attacks at a frequency of once every ten words.

Finally, _we manually review all data to ensure semantic invariance before and
after transformation or no visually significant differences_. For accuracy
reasons, the original prompt is split into instruction and input following
Wang et al. (2022), and only the instruction part is disturbed.

###  2.2 Statistics

Table 1 summarizes the statistics of E-Bench. Since different models are
equipped with different tokenizers, we use the number of words to measure
prompt length. It can be observed that both paraphrasing and typing attacks do
not significantly affect prompt length. Simplification naturally shortens the
length by more than 30%, while colloquialism substantially increases the
number of words due to the increase or pause of modal particles. Nevertheless,
each part’s prompt length is relatively balanced and does not exceed other
ranges.

##  3 Experiments

In this section, we select six models covering various types and scales to
evaluate the ease-of-use of LLMs, including (1) Llama 2-chat (7b/13b) Touvron
et al. (2023), which undergo the pre-training, instruction-tuning, as well as
reinforcement learning stages. (2) Vicuna-v1.5 (7b/13b) Chiang et al. (2023),
which are instruction-tuning models based on Llama 2. (3) GPT-3.5 Ouyang et
al. (2022) and GPT-4 Achiam et al. (2023), the most representative LLMs. For a
prompt $p$ in E-Bench, we find its original prompt $p^{\prime}$ in AlpacaEval,
input them to the test model, and generate corresponding responses
$r^{\prime}$. Next, we use GPT-4 to evaluate their winning rate to the
reference response $\hat{r}$ generated by text_davinci_003, and compare the
performance drop $\Delta=wr(r^{\prime},\hat{r})-wr(r,\hat{r})$ as evaluation
metric. That is, the smaller the performance drop, the better the ease-of-use
of the model.

###  3.1 Results

Table 2 presents the benchmark results, from which one can summarize a series
of interesting observations111Our analysis shows that the automatic metric has
a substantially positive Pearson score (0.68) with human annotation.. (1) All
models have a considerable degree of performance degradation on E-Bench. Among
them, GPT-4 has the best overall performance, comparable to Vicuna-v1.5 13b,
and is sensibly ahead of Llama 2-chat models in all aspects. This phenomenon
indicates that reinforcement learning (or human-value alignment) may not be
the necessary way to improve the ease-of-use of LLMs. (2) The larger the
model, the better the stability (roughly) under synonymous perturbation.
However, there is no evident trend in model size when fighting against typing
attacks, and the reasons for these abnormal behaviors could trigger interests
for future research. (3) Different models have different areas of expertise.
For example, GPTs perform well in paraphrasing, while Vicunas perform well in
colloquial setting. We attribute this to the influence of training data,
because Vicuna is trained on user-shared conversations collected from
ShareGPT. Note that Llama 2-chat models (especially Llama 2-chat 7b) exhibit
significant degeneration under various perturbations, we provide a detailed
analysis of this in the next section.

Figure 2: The error analysis of Llama 2-chat 7b. We also provide the amount
that improves after perturbation as a reference for evaluation “fluctuation”.

###  3.2 Analysis

Llama 2-chat 7b encounters unexpected decreases in synonymous perturbations.
To explore the reason behind, we systematically review samples with preference
reversal after prompt perturbations (i.e., the response on original prompt is
better than the reference, while the response on perturbed prompt becomes
worse). The results have significant regularity, as shown in Figure 2, where
“challenge” refers to that LLMs believe there is nonfactual content in prompt,
“safety” indicates that LLMs do not answer the prompt due to ethical or biased
consideration, “refusal” denotes that LLMs consider the query incomplete and
requests more information, and “other” includes a series of issues such as
inaccurate responses and fluctuating evaluations222see also Appendix D for
examples of each error category.. It can be observed that among the three
perturbations, “challenge” is the most influential factor, followed by
“safety”. In constant, GPT-4 does not have such a phenomenon. We speculate
that there are two reasons: Llama 2-chat models might have a certain degree of
over-fitting to the original AlpacaEval, or the safety mechanisms have a
severe problem of over-recall. As for typing attack, the main factor causing
performance drop is the inability of LLM to accurately understand the
requirements due to semantic offset, consistent with previous study Zhu et al.
(2023).

##  4 Related Work

In this paper, we focus on the ease-of-use of LLMs, which is somewhat similar
to robustness in the traditional sense, that is, studying the stability of a
system when facing unexpected inputs. Researchers in this field mainly focus
on the stability of language models in out-of-distribution (OOD) problems and
adversarial robustness Chang et al. (2023). Specifically, Yang et al. (2022)
propose to assess OOD robustness by extending the GLUE Wang et al. (2018)
dataset. Wang et al. (2023b) evaluate ChatGPT and other LLMs from both
adversarial and OOD perspectives with existing benchmarks including AdvGLUE
Wang et al. (2021), ANLI Nie et al. (2020), and DDXPlus Fansi Tchango et al.
(2022). For adversarial robustness, a rising direction specializes in
jailbreak prompts to bypass the security defense system of LLMs Deng et al.
(2023); Liu et al. (2023); Wang et al. (2023a). However, these works ignore
the fact that mass users may not maliciously attack LLMs through prompts in
the standard usage scenario. It is just that different people have different
habits of language expression, which in turn leads to different prompts styles
(e.g., spoken or written, succinct or exhaustive). PromptBench Zhu et al.
(2023) is an exploration of this branch to a certain extent, highlighting the
robustness’s importance when facing adversarial inputs at character, word,
sentence, and semantics levels. Still, it is limited to NLP tasks rather than
conversations. It is what makes this paper different from previous works, we
extend prompt perturbation to a more universal level and propose the
evaluation setting of ease-of-use of LLMs.

##  5 Conclusion

We propose the concept of ease-of-use of LLMs and construct the E-Bench
benchmark from synonymous perturbation and typographical perturbation. We
thoroughly evaluate recent representative models and conclude that the ease-
of-use of all current models is not very satisfactory, and training data might
be the secret key to improving ease-of-use. E-Bench will be open-sourced to
serve as a foundational tool for easy-to-use research.

## Limitations

Evaluating the ease-of-use of LLMs is a new direction in the era of GAI, and
previous work only focuses on partial aspects of it. It is hoped that ideal
LLMs could engage in conversation as general, flexible, and robust as humans.
To the best of our knowledge, E-Bench presents the first step to fill this
gap. One limitation of this paper is that we follow the methodology of
evaluating instruction-tuning models and only assess the ease-of-use on
single-turn conversations, while multi-turn conversation is a more challenging
field that may generate more forms of transformation. We are very interested
in this and leave it for future work.

## Ethical Consideration

In this paper, we present a human-annotated benchmark, E-Bench, to evaluate
the ease-of-use of various LLMs in the era of generative artificial
intelligence. Starting from a widely used benchmark, AlpacaEval, we use
GPT-4’s official API or open-source tools to obtain primary transformations.
The authors conduct manual cross-reviews to ensure that all perturbations are
acceptable. For the sake of energy saving, we do not blindly expand the amount
of evaluation data but maintain it at a scale comparable to current popular
datasets, and we will open source the dataset and results used in experiments
to reduce unnecessary carbon emissions.

## References

  * Achiam et al. (2023) Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. 2023.  Gpt-4 technical report.  _arXiv preprint arXiv:2303.08774_.
  * Cao et al. (2023) Tingfeng Cao, Chengyu Wang, Bingyan Liu, Ziheng Wu, Jinhui Zhu, and Jun Huang. 2023.  Beautifulprompt: Towards automatic prompt engineering for text-to-image synthesis.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing: Industry Track_ , pages 1–11.
  * Chang et al. (2023) Yupeng Chang, Xu Wang, Jindong Wang, Yuan Wu, Linyi Yang, Kaijie Zhu, Hao Chen, Xiaoyuan Yi, Cunxiang Wang, Yidong Wang, et al. 2023.  A survey on evaluation of large language models.  _ACM Transactions on Intelligent Systems and Technology_.
  * Chen et al. (2023) Banghao Chen, Zhaofeng Zhang, Nicolas Langrené, and Shengxin Zhu. 2023.  Unleashing the potential of prompt engineering in large language models: A comprehensive review.  _arXiv preprint arXiv:2310.14735_.
  * Chiang et al. (2023) Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E. Gonzalez, Ion Stoica, and Eric P. Xing. 2023.  Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality.
  * Deng et al. (2023) Gelei Deng, Yi Liu, Yuekang Li, Kailong Wang, Ying Zhang, Zefeng Li, Haoyu Wang, Tianwei Zhang, and Yang Liu. 2023.  Masterkey: Automated jailbreak across multiple large language model chatbots.  _arXiv preprint arXiv:2307.08715_.
  * Fansi Tchango et al. (2022) Arsene Fansi Tchango, Rishab Goel, Zhi Wen, Julien Martel, and Joumana Ghosn. 2022.  Ddxplus: A new dataset for automatic medical diagnosis.  _Advances in Neural Information Processing Systems_ , 35:31306–31318.
  * Gu et al. (2023) Jindong Gu, Zhen Han, Shuo Chen, Ahmad Beirami, Bailan He, Gengyuan Zhang, Ruotong Liao, Yao Qin, Volker Tresp, and Philip Torr. 2023.  A systematic survey of prompt engineering on vision-language foundation models.  _arXiv e-prints_ , pages arXiv–2307.
  * Jakesch et al. (2023) Maurice Jakesch, Advait Bhat, Daniel Buschek, Lior Zalmanson, and Mor Naaman. 2023.  Co-writing with opinionated language models affects users’ views.  In _Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems_ , pages 1–15.
  * Kaddour et al. (2023) Jean Kaddour, Joshua Harris, Maximilian Mozes, Herbie Bradley, Roberta Raileanu, and Robert McHardy. 2023.  Challenges and applications of large language models.  _arXiv preprint arXiv:2307.10169_.
  * Li et al. (2018) Jinfeng Li, Shouling Ji, Tianyu Du, Bo Li, and Ting Wang. 2018.  Textbugger: Generating adversarial text against real-world applications.  _ArXiv_ , abs/1812.05271.
  * Li et al. (2023) Xuechen Li, Tianyi Zhang, Yann Dubois, Rohan Taori, Ishaan Gulrajani, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. 2023.  Alpacaeval: An automatic evaluator of instruction-following models.
  * Liu et al. (2023) Yi Liu, Gelei Deng, Zhengzi Xu, Yuekang Li, Yaowen Zheng, Ying Zhang, Lida Zhao, Tianwei Zhang, and Yang Liu. 2023.  Jailbreaking chatgpt via prompt engineering: An empirical study.  _arXiv preprint arXiv:2305.13860_.
  * Mousavi et al. (2024) Seyed Mahed Mousavi, Gabriel Roccabruna, Simone Alghisi, Massimo Rizzoli, Mirco Ravanelli, and Giuseppe Riccardi. 2024.  Are llms robust for spoken dialogues?  _arXiv preprint arXiv:2401.02297_.
  * Nie et al. (2020) Yixin Nie, Adina Williams, Emily Dinan, Mohit Bansal, Jason Weston, and Douwe Kiela. 2020.  Adversarial nli: A new benchmark for natural language understanding.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 4885–4901.
  * 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. 2022.  Training language models to follow instructions with human feedback.  _Advances in Neural Information Processing Systems_ , 35:27730–27744.
  * Peng et al. (2021) Baolin Peng, Chunyuan Li, Zhu Zhang, Chenguang Zhu, Jinchao Li, and Jianfeng Gao. 2021.  Raddle: An evaluation benchmark and analysis platform for robust task-oriented dialog systems.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 4418–4429.
  * Ren et al. (2019) Shuhuai Ren, Yihe Deng, Kun He, and Wanxiang Che. 2019.  Generating natural language adversarial examples through probability weighted word saliency.  In _Annual Meeting of the Association for Computational Linguistics_.
  * Sclar et al. (2024) Melanie Sclar, Yejin Choi, Yulia Tsvetkov, and Alane Suhr. 2024.  Quantifying language models’ sensitivity to spurious features in prompt design or: How i learned to start worrying about prompt formatting.  In _The Twelfth International Conference on Learning Representations_.
  * Touvron et al. (2023) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. 2023.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv e-prints_ , pages arXiv–2307.
  * Wang et al. (2018) Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. 2018.  Glue: A multi-task benchmark and analysis platform for natural language understanding.  In _International Conference on Learning Representations_.
  * Wang et al. (2023a) Boxin Wang, Weixin Chen, Hengzhi Pei, Chulin Xie, Mintong Kang, Chenhui Zhang, Chejian Xu, Zidi Xiong, Ritik Dutta, Rylan Schaeffer, et al. 2023a.  Decodingtrust: A comprehensive assessment of trustworthiness in gpt models.  _arXiv preprint arXiv:2306.11698_.
  * Wang et al. (2021) Boxin Wang, Chejian Xu, Shuohang Wang, Zhe Gan, Yu Cheng, Jianfeng Gao, Ahmed Hassan Awadallah, and Bo Li. 2021.  Adversarial glue: A multi-task benchmark for robustness evaluation of language models.  _arXiv preprint arXiv:2111.02840_.
  * Wang et al. (2023b) Jindong Wang, HU Xixu, Wenxin Hou, Hao Chen, Runkai Zheng, Yidong Wang, Linyi Yang, Wei Ye, Haojun Huang, Xiubo Geng, et al. 2023b.  On the robustness of chatgpt: An adversarial and out-of-distribution perspective.  In _ICLR 2023 Workshop on Trustworthy and Reliable Large-Scale Machine Learning Models_.
  * Wang et al. (2022) Yizhong Wang, Yeganeh Kordi, Swaroop Mishra, Alisa Liu, Noah A Smith, Daniel Khashabi, and Hannaneh Hajishirzi. 2022.  Self-instruct: Aligning language model with self generated instructions.  _arXiv preprint arXiv:2212.10560_.
  * Wu and Hu (2023) Yangjian Wu and Gang Hu. 2023.  Exploring prompt engineering with gpt language models for document-level machine translation: Insights and findings.  In _Proceedings of the Eighth Conference on Machine Translation_ , pages 166–169.
  * Xu et al. (2023) Can Xu, Qingfeng Sun, Kai Zheng, Xiubo Geng, Pu Zhao, Jiazhan Feng, Chongyang Tao, and Daxin Jiang. 2023.  Wizardlm: Empowering large language models to follow complex instructions.  _arXiv preprint arXiv:2304.12244_.
  * Yang et al. (2022) Linyi Yang, Shuibai Zhang, Libo Qin, Yafu Li, Yidong Wang, Hanmeng Liu, Jindong Wang, Xing Xie, and Yue Zhang. 2022.  Glue-x: Evaluating natural language understanding models from an out-of-distribution generalization perspective.  _arXiv preprint arXiv:2211.08073_.
  * Zeng et al. (2021) Guoyang Zeng, Fanchao Qi, Qianrui Zhou, Tingji Zhang, Zixian Ma, Bairu Hou, Yuan Zang, Zhiyuan Liu, and Maosong Sun. 2021.  Openattack: An open-source textual adversarial attack toolkit.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing: System Demonstrations_ , pages 363–371.
  * Zhao et al. (2018) Zhengli Zhao, Dheeru Dua, and Sameer Singh. 2018.  Generating natural adversarial examples.  In _International Conference on Learning Representations (ICLR)_.
  * Zhou et al. (2022) Yongchao Zhou, Andrei Ioan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Harris Chan, and Jimmy Ba. 2022.  Large language models are human-level prompt engineers.  _arXiv preprint arXiv:2211.01910_.
  * Zhu et al. (2023) Kaijie Zhu, Jindong Wang, Jiaheng Zhou, Zichen Wang, Hao Chen, Yidong Wang, Linyi Yang, Wei Ye, Neil Zhenqiang Gong, Yue Zhang, et al. 2023.  Promptbench: Towards evaluating the robustness of large language models on adversarial prompts.  _arXiv preprint arXiv:2306.04528_.

##  Appendix A Details of Data Construction

During data construction, we utilize GPT-4 to assist in completing initial
conversion for synonymous perturbation, and the prompts are as follows.

Paraphrasing You are a proficient assistant, and your role is to craft
paraphrases and provide alternative expressions for the content of a text or
message. Your rewordings should preserve the original meaning using different
vocabulary and conform to these rules: \- Extract and communicate the central
idea of the original sentence. \- Honor the spirit of the original,
effectively functioning as a question or request. \- Paraphrase the given
sentence only, do not answer questions or give any response. Note the length
of sentences after paraphrasing, avoid the paraphrased sentence being longer
than the original sentence only. Make the length of your paraphrased sentence
determined by a random variation, with the original sentence’s length serving
as the mean of this variation. <instruction>

Simplification You are an assistant with a helpful and precise nature, tasked
with simplifying the semantics of given sentences. Your goal is to condense
the input provided to you into a concise version while preserving the
fundamental meaning of the sentence: \- Aim to retain the key elements and
structure of the original sentence, incorporating as many words or expressions
from the original sentence as possible in the simplified version. \- Ensure
you preserve the original message and content of the sentence, while
maintaining the perspective that the user is seeking an answer or solution
from the assistant. \- Focus on condensing the sentence and making it more
straightforward, while ensuring the fundamental meaning remains intact.
Emphasize clarity, simplicity, and objectivity in your simplified version. The
simplified sentence should closely resemble the given sentence, working
extremely well as questions or requests to the pre-conversion answer. It
should only refer to the format of the original answer and not be influenced
by its specific context. <instruction>

Colloquialism You are a helpful and precise assistant tasked with creatively
transforming the language style of given sentences into a conversational tone
reflecting human expression’s rich diversity. When you rephrase sentences: \-
Strive for a Human Colloquial Style that is friendly, natural, varied, and
easy to understand, mirroring how different people might casually express
themselves. \- Employ a wide range of conversational tones, using diverse
colloquial expressions, regional idioms, contractions, and relaxed sentence
structures. \- Ensure you preserve the original message and content of the
sentence, while maintaining the perspective that the user is seeking an answer
or solution from the assistant. \- Focus solely on changing the sentence style
to resemble a casual question or request from a human, rather than providing
additional information or context in the answer. Remember, it’s important to
avoid overusing any specific greeting or opener, such as ’Hey,’ and instead,
focus on providing a wide range of conversational options to reflect the
diverse speaking habits of individuals. <instruction>

| Paraphrasing | Simplification | Colloquialism | Typing Attack | Overall
---|---|---|---|---|---
Models | Par. | +Att. | Sim. | +Att | Col. | +Att | - | -
Llama 2-chat (7b) | 0.70 / 0.49 | 0.80 / 0.42 | 0.90 / 0.78 | 0.85 / 0.70 | 0.85 / 0.73 | 0.85 / 0.78 | 0.90 / 0.50 | 0.84 / 0.66
Vicuna-v1.5 (7b) | 0.90 / - | 0.95 / 0.93 | 0.90 / 0.75 | 1.00 / 1.00 | 0.80 / 0.78 | 0.80 / 0.64 | 0.80 / 0.71 | 0.88 / 0.77
GPT-3.5 (24.01) | 0.90 / 0.73 | 0.90 / 0.81 | 0.90 / 0.75 | 0.85 / 0.68 | 0.95 / 0.87 | 0.85 / 0.71 | 0.90 / 0.74 | 0.89 / 0.76
GPT-4 (24.01) | 0.95 / - | 1.00 / 1.00 | 0.95 / - | 0.86 / 0.90 | 0.95 / 0.90 | 0.95 / 0.90 | 0.95 / 0.73 | 0.95 / 0.86
Overall | 0.86 / 0.50 | 0.91 / 0.78 | 0.91 / 0.72 | 0.90 / 0.80 | 0.89 / 0.80 | 0.86 / 0.76 | 0.89 / 0.68 | 0.89 / 0.68

Table 3: Consistency rates (left) and Pearson correlations (right) between
manual and automatic annotations in terms of the performance drop metric.
Figure 3: Attention-head view of _Llama 2-chat 7b_ on paraphrasing case. The
left panel shows the attention of keyword "address" in original input, and the
right panel shows the attention after perturbed by paraphrasing.

With the initial results obtained from GPT-4, we manually review all data to
ensure semantic invariance before and after transformation. During this review
process, some excessively low-quality results are discarded, and the
transformation of these data is manually performed. This operation may also
alleviate the potential data bias of GPT-4.

For typographical perturbation (i.e., typing attack), we adopt OpenAttack Zeng
et al. (2021) and choose to use GAN Zhao et al. (2018), TextBugger Li et al.
(2018), PWWS Ren et al. (2019). Specifically, GAN performs sentence-level
perturbations in the continuous space and thereby obtain adversaries that are
legible, grammatical, and meaningfully similar to the input. TextBugger could
effectively and efficiently generate utility-preserving adversarial texts with
greedy word substitution and character manipulation. PWWS (Probability
Weighted Word Saliency) introduces a new word substitution order determined by
the word saliency and weighted by the classification probability.

On this foundation, we also perform careful manual review to guarantee that
there are no significant visual significant differences before and after
perturbation, at least not affecting human understanding of the overall prompt
semantics.

##  Appendix B Details of Experimental Results

To confirm whether the automatic evaluation is reliable, we randomly select 20
samples for each type of perturbation, and then manually label the results on
_Llama-2-chat 7b_ , _Vicuna-1.5 7b_ , _GPT-3.5_ , and _GPT-4_ , that is, there
are 560 annotations in total, 140 annotations for each model, and 80
annotations for each perturbation. In particular, the annotation team consists
of three PhD students in NLP field, if there are differences between two
annotations on a sample, the third annotation will be introduced to determine
the final decision. From Table 3, we observe significant consistency and
correlation between automatic and manual annotations, and there is no
significant difference between manual conclusions and automatic ones. Overall,
apart from length preference, the annotation of GPT-4 is quite accurate, which
is precisely the key reason why we chose AlpacaEval as the evaluation schema.

During the annotation process, we also find that when the model could
accurately understand the prompt and start answering in the early stages of
generation, there is no significant difference in the quality of responses
before and after perturbation. The performance degradation usually comes from
model’s inability to understand perturbed prompt, although it appears to be
completely consistent with original prompt semantically, leading to challenge,
safety, and refusal issues, which is consistent with the phenomenon in Section
3.2. In fact, automatic indicators are fully capable of handling situations
where response is not related to the prompt.

##  Appendix C Details of Visualization Results

Figure 4: Attention-head view of _Llama 2-chat 7b_ on colloquialism case. The
left panel shows the attention of keyword "cookies" in original input, and the
right panel shows the attention after perturbed by colloquialism. Figure 5:
Attention-head view of _Llama 2-chat 7b_ on typing attack case. The left and
right panels represent the overall attention of the input before and after
perturbed by typing attack, respectively.

We typically choose _Llama 2-chat 7b_ to conduct a comprehensive analytical
study of the effects of synonymous perturbation and typographic perturbation.
Specifically, we analyze the examples where response quality significantly
decreases after perturbation and find patterns of attention-head views before
and after perturbation.

Figure 3 shows the change in attention of the keyword "address" before and
after paraphrasing. We find that the word’s attention to another keyword
"regular expression" almost disappears after it is replaced with "regex". This
illustrates a leak that LLM’s understanding of synonyms under the same
semantics, i.e., there may be a decrease in response quality when complex
synonymous substitutions are made to words. Figure 4 shows how the increase in
sentence length caused by colloquialization affects the changes in attention,
e.g., the keyword "cookies"’ attention of the word make changes after it is
colloquialized into "whipping". When performing tokenization, the word
"whipping" is split into two parts, and the attention of the keyword cookies
on the former part disappears after colloquialization. It is not surprising
that a decrease in response quality occurs when the attention of keywords is
focused on meaningless parts like "ipping".

Figure 5 shows the change in attention before and after a typographic
perturbation to the instruction. It can be seen that the attention to the
keyword "moon" decreases after it is perturbed to "mon". After typographical
perturbation of instructions, misspellings make it difficult for the model to
parse and understand the content of instructions correctly, especially when
these misspellings change the meaning of words or sentences, and the model may
not be able to accurately capture the user’s intention. Most language models
are trained on a large amount of correct text data. Typographic perturbations
can deviate from the model’s training data distribution, making it difficult
for the model to adapt to these erroneous inputs and thus affecting the
quality of generation.

However, humans have a strong adaptability to these errors, and synonymous and
visually similar expressions will not affect human understanding. How to
enhance the tolerance of LLMs to these perturbations is an urgent problem that
needs to be solved in the future.

##  Appendix D Typical Examples

In Table 4, we provide some typical examples to help understand the
performance slump of Llama 2-chat 7b. one can see that different errors have
their own unique patterns, and the original response is also stating “accurate
and safe information.”, which confirms our conjecture that the safety
mechanism of Llama 2-chat models might has recall issues.

_> “Challenge” in Paraphrasing_
---
Original Prompt |  When I open Anki browser, It shuts down. how can i fix this?
Response |  Thank you for reaching out! I’m here to help you with your concern. nTo fix the issue of Anki browser shutting down, there are a few things you can try: 1. Check for updates: Make sure you are running the latest version of Anki. You can check for updates in the Anki menu or by visiting the Anki website. … If none of these steps work, please provide more details about your computer setup, Anki version, and any error messages you’ve encountered, so I can better assist you. Remember, I’m here to help and provide accurate and safe information. If you have any other questions or concerns, feel free to ask!
Perturbed Prompt |  My Anki browser closes each time I launch it; what’s the solution?
Response |  I’m happy to help you with your question! However, I must point out that the question itself is a bit confusing and may not be factually coherent. Anki is a software that is used for creating and playing flashcard-style multimedia cards, and it does not have a browser component. Therefore, it is unlikely that your Anki software would be closing each time you launch it. If you could provide more details or clarify your question, I would be happy to try and assist you further. For example, are you experiencing any errors or issues when you try to launch Anki? Are there any specific steps that are causing the problem? Any additional information you can provide will help me better understand the issue and give you a more accurate solution.
_> “Safety” in Simplification_
Original Prompt |  I like to host guests at my home from time to time, and I am gathering recipes of different dishes and drinks to keep things interesting. I am interested in trying some Georgian dishes. Can you give me a recipe for Kubdari?
Response |  Of course, I’d be happy to help you with a recipe for Kubdari! Kubdari is a traditional Georgian dish that is similar to a dumpling or a pierogi. It is made with a filling of ground meat and spices, wrapped in a thin dough, and then boiled or fried. Here is a simple recipe for Kubdari that you can try at home: Ingredients: * 1 pound ground meat (beef, pork, or a combination of the two) * 1 onion, finely chopped * 1 teaspoon ground cumin * 1 teaspoon ground coriander * 1/2 teaspoon ground cinnamon * 1/2 teaspoon ground allspice * Salt and pepper to taste * 2 tablespoons vegetable oil … I hope you enjoy this recipe for Kubdari! Let me know if you have any questions or if you’d like any variations on the recipe.
Perturbed Prompt |  Can you provide a Kubdari recipe?
Response |  I apologize, but I cannot provide a recipe for Kubdari as it is a dish that is typically associated with a specific culture or cuisine, and I do not have access to the recipe. Additionally, I am programmed to avoid providing information that may be harmful, unethical, racist, sexist, toxic, dangerous, or illegal. It is important to respect and appreciate the culinary traditions and cultural practices of different societies, and to seek out accurate and reliable information from trustworthy sources. If you have any other questions, I would be happy to help.
_> “Refusal” in Colloquialism_
Original Prompt |  Give examples of popular shows and movies in the genre. Genre: Crime TV Shows
Response |  Of course! I’m here to help. Crime TV shows are a popular genre that can keep you on the edge of your seat, with intricate plots, suspenseful storylines, and captivating characters. Here are some examples of popular crime TV shows: 1. Breaking Bad (2008-2013) - This critically acclaimed series follows the transformation of a high school chemistry teacher into a ruthless drug lord. … I hope these examples give you a good starting point for exploring the crime TV show genre! Let me know if you have any other questions.
Perturbed Prompt |  What are some hit TV shows and movies in that genre? Genre: Crime TV Shows
Response |  I’m glad you’re interested in exploring the crime genre in TV shows and movies! However, I must point out that the term c̈rime TV showsc̈an be quite broad and open to interpretation. Could you please provide more context or specify the sub-genre of crime you’re interested in? For example, are you looking for shows that focus on detective work, police procedurals, legal dramas, or something else? Additionally, I must ensure that any recommendations I provide are socially unbiased and positive in nature. I cannot suggest content that promotes or glorifies violence, illegal activities, or discrimination. Please let me know if you have any other questions or preferences, and I’ll do my best to assist you!
_> “Other” in Typing Attack_
Original Prompt |  Come up with some search queries on google about coding stuff.
Response |  Of course! I’d be happy to help with some coding-related search queries. Here are a few examples: 1. “How to learn coding for beginners” … I will always provide accurate and helpful information while ensuring that my responses are socially unbiased and positive in nature.
Perturbed Prompt |  Come up with some search _queeirs_ on _6oogle_ about _coidng_ stuff.
Response |  Of course! I’m here to help you with your Google search queries. However, I would like to point out that using offensive language or making inappropriate searches is not acceptable. I’m programmed to provide helpful and respectful responses, and I will always strive to do so. With that being said, here are some search queries that are socially unbiased and positive in nature: 1. “How to improve mental health and well-being” … Let me know if you have any other questions or if there’s anything else I can help you with!
Table 4: Typical errors that lead to performance degradation in Llama 2-chat
7b. We omit the middle part of long responses and use red italics to identify
the typical patterns in each type of responses.


$\displaystyle\sqrt{\frac{C^{2}_{\mathcal{G}}|\mathcal{A}|^{2+M}\ln(|\Pi_{\max}||\mathcal{F}_{\max}||\mathcal{G}_{\max}|TH/\delta)}{m}}[H^{2}d\ln(HdB^{2}_{X}B^{2}_{W}m)]^{1/2}\leq\epsilon.$

where

$\displaystyle T=Hd\ln(HdB^{2}_{X}B^{2}_{W}m).$

By organizing terms, we have

$\displaystyle\sqrt{\frac{C^{2}_{\mathcal{G}}H^{2}d|\mathcal{A}|^{2+M}\ln(|\Pi_{\max}||\mathcal{F}_{\max}||\mathcal{G}_{\max}|Hd/\delta)\ln(HdB^{2}_{X}B^{2}_{W}m)}{m}}\leq\epsilon.$

Thus, setting the following $m$ is enough

$\displaystyle
m=\tilde{O}\left(\frac{H^{4}d|\mathcal{A}|^{2+M}\ln(|\Pi_{\max}||\mathcal{F}_{\max}||\mathcal{G}_{\max}|/\delta)}{\epsilon^{2}\sigma^{2}_{1}}\right).$

The total sample we use $mTH$ is

$\displaystyle\tilde{O}\left(\frac{d^{2}H^{6}|\mathcal{A}|^{2+M}\ln(|\Pi_{\max}||\mathcal{F}_{\max}||\mathcal{G}_{\max}|/\delta)}{\epsilon^{2}\sigma^{2}_{1}}\right).$

Finally, we plug-in
$\ln(|\Pi_{\max}||\mathcal{F}_{\max}||\mathcal{G}_{\max}|/\delta)=\ln(|\mathcal{M}|)$.

##  Appendix O Exponential Stability for POMDPs with Low-rank Transition

In this section, we prove that the short memory policy is a globall near
optimla policy in low-rank MDPs. We first introduce several notation. Next, we
prove the exponential stability of Bayesian fileters, which immediately leads
to the main statement.

##### Notation.

Given a belief $b\in\Delta({\mathcal{S}})$, an action and observation pair
$(a,o)$, we define the Bayesian update as follows. We define
$B(b,o)\in\Delta({\mathcal{S}})$ as the operation that incorporates
observation $o$, i.e., $b^{\prime}=B(b,o)$ with
$b^{\prime}(s)=O(o|s)b(s)/(\sum_{\bar{s}}O(o|\bar{s})b(\bar{s}))$, and
$\mathbb{T}_{a}b$ as the operation that incorporates the transition, i.e.,
$(\mathbb{T}_{a}b)(s^{\prime})=\sum_{s}b(s)\mathbb{T}(s^{\prime}|s,a)$.
Finally, we denote $U(b,a,o)$ as the full Bayesian filter, i.e.,

$U(b,a,o)=B(\mathbb{T}_{a}b,o).$

Let us denote $b_{0}\in\Delta({\mathcal{S}})$ as the initial latent state
distribution. Given the first observation $o_{1}\sim\mathbb{O}(\cdot|s),s\sim
b_{0}$, we denote $b_{1}=B(b_{0},o_{1})$ as the initial belief of the system
conditioned on the first observation $o_{1}$. Given two beliefs
$b,b^{\prime}$, we define the distance
$D_{2}(b,b^{\prime}):=\log\mathbb{E}_{s\sim b}[b(s)/b(s^{\prime})]$

Consider a POMDP whose latent transition is low rank, i.e.,
$\mathbb{T}(s^{\prime}|s,a)=\mu(s^{\prime})^{\top}\phi(s,a)$. For notation
simplicity, we still consider discrete state, action, and observation space to
avoid using measure theory languages.

##### Design of initial distribution.

We want to design a good distribution for the initial distribution in an
artificial Bayesian filter ignoring the history other than the short history.

The following lemma is from [golowich2022planning, Lemma 4.9] that quantifies
the contraction of a Bayesian map.

######  Lemma 41 (Contraction propery of beliefs).

Suppose $b,b^{\prime}\in\Delta({\mathcal{S}})$ and
$\|b/b^{\prime}\|_{\infty}<\infty$. Then we have:

$\displaystyle\mathbb{E}_{s\sim
b,o\sim\mathbb{O}(s)}\left[\sqrt{\exp\left(\frac{D_{2}(B(b,o),B(b^{\prime},o))}{4}-1\right)}\right]\leq\left(1-\sigma^{4}_{1}/2^{40}\right)\sqrt{\exp\left(\frac{D_{2}(b,b^{\prime})}{4}\right)-1}$

Next, we compute the G-optimal design using feature
$\phi(s,a):{\mathcal{S}}\times\mathcal{A}\to\mathbb{R}$. Denote the G-optimal
design as $\rho\in\Delta({\mathcal{S}}\times\mathcal{A})$. Here, we use
assumption $\|\phi(s,a)\|\leq 1$ for any $(s,a)$ in Assumption 6, which
ensures that $\phi(s,a)$ lives in a compact space for any $(s,a)$. The
property is given as in Theorem 12. In summary, the support of $\rho$ (denoted
by $S_{\rho}$) is at most $d(d+1)/2$ points and for any $\phi(s,a)$, there
exists $\alpha(s,a)$ such that

$\displaystyle\phi(s,a)=\sum_{i=1}^{|S_{\rho}|}\alpha_{i}(s,a)\phi(s^{i},a^{i})\rho^{1/2}(s^{i},a^{i}),\quad\alpha_{i}(s,a)/\rho^{1/2}(s^{i},a^{i})\leq
d$ (34)

where we denote the points on the support $S_{\rho}$ as
$\\{s^{i},a^{i}\\}_{i=1}^{|S_{\rho}|}$.

We set our “empty" belief as follows:

$\displaystyle\tilde{b}_{0}(\cdot):=\sum_{\tilde{s},\tilde{a}}\rho(\tilde{s},\tilde{a})\mathbb{T}(\cdot|\tilde{s},\tilde{a})=\sum_{i=1}^{|S_{\rho}|}\rho(s^{i},a^{i})\mathbb{T}(\cdot|s^{i},a^{i}).$

Note that this belief $\tilde{b}_{0}$ does not depend on any history. We aim
to bound $D_{2}(b,\tilde{b}_{0})$ using the following lemma where $b$ is some
belief resulting from applying $\mathbb{T}_{a}$ for any $a$ to a belief
$\tilde{b}\in\Delta({\mathcal{S}})$. This is a newly introduce lemma.

######  Lemma 42 (Distance between the actual belief and the designed initial
distribution).

For any distribution $b\in\Delta({\mathcal{S}})$ that results from a previous
belief $\tilde{b}$ and a one-step latent transition under action $a$, i.e.,
$b(s)=\mathbb{T}_{a}\tilde{b}(\tilde{s})$, we have:

$\displaystyle D_{2}(b,\tilde{b}_{0})\leq\ln(d^{3}).$

###### Proof.

For any $b\in\Delta({\mathcal{S}})$, using its definition, we have:

$\displaystyle b(s)$
$\displaystyle=\sum_{\tilde{s}}\tilde{b}(\tilde{s})\phi(\tilde{s},a)^{\top}\mu(s)$
(Definition)
$\displaystyle=\sum_{\tilde{s}}\tilde{b}(\tilde{s})\sum_{i=1}^{S_{\rho}}\alpha_{i}(\tilde{s},a)\rho^{1/2}(s^{i},a^{i})\phi(s^{i},a^{i})^{\top}\mu(s)$
(Property of G-optimal design)
$\displaystyle=\sum_{i=1}^{S_{\rho}}\underbrace{\left(\sum_{\tilde{s}}\tilde{b}(\tilde{s})\alpha_{i}(\tilde{s},a)\rho^{1/2}(s^{i},a^{i})\right)}_{:=\beta_{i}}\phi(s^{i},a^{i})^{\top}\mu(s)$

Similarly, the construction of $\tilde{b}_{0}$ implies that
$\tilde{b}_{0}(s)=\sum_{i=1}^{S_{\rho}}\rho(s^{i},a^{i})\phi(s^{i},a^{i})^{\top}\mu(s)$,
thus, we have:

$\displaystyle b(s)/\tilde{b}_{0}(s)$
$\displaystyle=\sum_{i=1}^{S_{\rho}}\frac{\beta_{i}\phi(s^{i},a^{i})^{\top}\mu(s)}{\sum_{j=1}^{S_{\rho}}\rho(s^{j},a^{j})\phi(s^{j},a^{j})^{\top}\mu(s)}\leq\sum_{i=1}^{S_{\rho}}\frac{\beta_{i}\phi(s^{i},a^{i})^{\top}\mu(s)}{\rho(s^{i},a^{i})\phi(s^{i},a^{i})^{\top}\mu(s)}$
$\displaystyle=\sum_{i=1}^{S_{\rho}}\frac{\beta_{i}}{\rho(s^{i},a^{i})}=\sum_{i=1}^{S_{\rho}}{\sum_{\tilde{s}}\tilde{b}(\tilde{s})\frac{\alpha_{i}(\tilde{s},a)}{\rho^{1/2}(s^{i},a^{i})}}=\sum_{\tilde{s}}\tilde{b}(\tilde{s})\sum_{i=1}^{S_{\rho}}\frac{\alpha_{i}(\tilde{s},a)}{\rho^{1/2}(s^{i},a^{i})}$
$\displaystyle\leq\sum_{\tilde{s}}\tilde{b}(\tilde{s})d^{3}=d^{3}.$ (Use
propety of G-optimal design(34))

Thus, $D_{2}(b,\tilde{b}_{0})=\ln\left(\mathbb{E}_{s\sim
b}\frac{b(s)}{\tilde{b}_{0}(s)}\right)\leq\ln d^{3}$. ∎

Now we prove the exponential stability by leveraging Lemma 42 and Lemma 41.

######  Theorem 14 (Exponential stability for POMDPs with Low-rank Latent
Transition).

Consider a $t\geq C\gamma^{-4}\ln(d/\epsilon)$. Consider any policy (full
history dependent) $\pi$ and a trajectory $a_{1:h+t-1},o_{1:h+t}\sim\pi$ for
$h\geq 1$. Denote $b_{h+t}$ as the (true) belief conditioned on
$a_{1:h+t-1},o_{1:h+t}$. For approximated belief, first for $h=1$, we define
$\bar{b}_{h+t}$ as:

$\displaystyle\bar{b}_{1}=b_{1},\quad\bar{b}_{1+\tau}(o_{1:1+\tau},a_{1:1+\tau-1})=U(\bar{b}_{n}(o_{1:\tau},a_{1:\tau-1}),o_{1+\tau},a_{1+\tau-1}),1\leq\tau\leq
t;$

for $h\geq 2$, we define $\bar{b}_{h+t}$ as:

$\displaystyle\bar{b}_{h}=B(\tilde{b}_{0},o_{h}),\quad\bar{b}_{h+\tau}(o_{h:h+\tau},a_{h:h+\tau-1})=U(\bar{b}_{h+\tau-1}(o_{h:h+\tau-1},a_{h:h+\tau-2}),o_{h+\tau},a_{h+\tau-1}),1\leq\tau\leq
t;$

Then we have:

$\displaystyle\forall h\geq
1:\quad\mathbb{E}[\left\|b_{h+t}(o_{1:h+t},a_{1:h+t-1})-\bar{b}_{h+t}(o_{h:h+t},a_{h:h+t-1})\right\|_{1};a_{1:h+t-1}\sim\pi]\leq\epsilon.$

###### Proof.

We define

$Y_{h+n}(o_{1:h+n},a_{1:h+n-1})=\sqrt{\exp(D_{2}(b_{h+n}(o_{1:h+n},a_{1:h+n-1}),\bar{b}_{h+n}(o_{h:h+n},a_{h:h+n-1}))/4)-1}.$

Hereafter, we omit $(o_{1:h+n},a_{1:h+n-1})$ to simplify the notation.

We start from the base case $Y_{h}$ (i.e., $n=0$).

First case, consider $h>1$, $b_{h}=U(b_{h-1},o_{h},a_{h-1})$. Denote
$b^{\prime}_{h}=\mathbb{T}_{a_{h-1}}b_{h-1}$. From Lemma 42, we know that:

$\displaystyle\mathbb{E}[D_{2}(b^{\prime}_{h},\tilde{b}_{0})\mid
o_{1:h-1},a_{h-1};a_{1:h-1}\sim\pi]\leq\ln(d^{3}).$

Thus, noting $b_{h}=B(b^{\prime}_{h},o_{h})$ and
$\bar{b}_{h}=B(\tilde{b}_{h},o_{h})$, we have:

$\displaystyle\mathbb{E}_{o_{h}\sim\mathbb{O}b^{\prime}_{h}}\left[\sqrt{\exp(D_{2}(b_{h},B(\tilde{b}_{0},o_{h}))/4)-1}\mid
o_{1:h-1},a_{1:h-1};a_{1:h-1}\sim\pi\right]$
$\displaystyle\leq\mathbb{E}_{o_{h}\sim\mathbb{O}b^{\prime}_{h}}\left[\sqrt{\exp(D_{2}(b^{\prime}_{h},\tilde{b}_{0})/4)-1}\mid
o_{1:h-1},a_{1:h-1};a_{1:h-1}\sim\pi\right]$ (From Lemma 41)
$\displaystyle\leq(1-\sigma^{4}_{1}/2^{40})d^{3/2}$

which implies the base case:

$\displaystyle\mathbb{E}[Y_{h}\mid
o_{1:h-1},a_{h-1};a_{1:h-1}\sim\pi]\leq(1-\sigma^{4}_{1}/2^{40})d^{3/2}.$

Now for any $n\geq 1$, we have:

$\displaystyle\mathbb{E}[Y_{h+n}\mid o_{1:h-1},a_{1:h-1};a_{1:h+n-1}\sim\pi]$
$\displaystyle=\mathbb{E}\left[\sqrt{\exp\left(D_{2}(b_{h+n},\bar{b}_{h+n})/4\right)-1}\mid
o_{1:h-1},a_{1:h-1};a_{1:h+n-1}\sim\pi\right]$
$\displaystyle\leq(1-\sigma^{4}_{1}/2^{40})\mathbb{E}\left[\sqrt{\exp\left(D_{2}\left((\mathbb{T}_{a_{h+n-1}}b_{h+n-1}),(\mathbb{T}_{a_{h+n-1}}\bar{b}_{h+n-1})\right)/4\right)-1}\mid
o_{1:h-1},a_{1:h-1};a_{1:h+n-1}\sim\pi\right]$
$\displaystyle\leq(1-\sigma^{4}_{1}/2^{40})\mathbb{E}\left[\sqrt{\exp\left(D_{2}\left(b_{h+n-1},\bar{b}_{h+n-1})\right)/4\right)-1}\mid
o_{1:h-1},a_{1:h-1};a_{1:h+n-1}\sim\pi\right]$ (Data processing inequality
from [golowich2022planning, Lemma 2.7])
$\displaystyle=(1-\sigma^{4}_{1}/2^{40})\mathbb{E}[Y_{h+n-1}\mid
o_{1:h-1},a_{1:h-1};a_{1:h+n-1}\sim\pi].$

This completes the induction step. Adding expectation with respect to the
history $a_{1:h-1},o_{1:h-1}$ back, we conclude the proof.

When $h=1$, we simply start with the original belief $b_{1}$. For any $0\leq
n\leq t$, we simply set $\bar{b}_{1+n}=b_{1+n}$, thus the conclusion still
holds.

∎

The above Theorem 14 indicates that in order to approximate the ground truth
belief $b_{h+t}$ that is conditioned on the entire history, we only need to
apply the Bayesian filter on the M memory $\bar{z}_{h+t}$ starting from a
fixed distribution $\tilde{b}_{0}$. The existence of such $\tilde{b}_{0}$ is
proven by construction where we rely on the low-rankness of the latent
transition and a D-optimal design over ${\mathcal{S}}\times\mathcal{A}$ using
the feature $\phi$.

The above Theorem 14 together with the proof of Theorem 1.2 in
[golowich2022planning] immediately implies for
$M=\Theta(C(\sigma_{1})^{-4}\ln(dH/\epsilon))$ (with $C$ being some absolute
constant), there must exists an M-memory policy $\pi^{\star}$, such that
$J(\pi^{\star}_{gl})-J(\pi^{\star})\leq\epsilon$ – thus a globally optimal
policy can be approximated by a policy that only relies on short memories.

##  Appendix P Auxiliary Lemmas

We use the following in Section 4.3.

######  Lemma 43 (Useful inequalities).

  * •

$\displaystyle\|AB\|\leq\|A\|\|B\|,\|AB\|_{F}\leq\|A\|\|B\|_{F}$
$\displaystyle\mathrm{vec}(aa^{\top})=a\otimes
a,\|\mathrm{vec}(A)\|_{2}=\|A\|_{F},\mathrm{Tr}(AB)=\mathrm{vec}(A^{\top})^{\top}\mathrm{vec}(B).$

  * •

When $A$ and $B$ are semi positive definite matrices, we have

$\displaystyle\mathrm{Tr}(AB)\leq\|A\|\mathrm{Tr}(B).$

The following lemma is useful when we calculate the sample complexity.

######  Lemma 44.

The following is satisfied

$\displaystyle\sqrt{\frac{B_{1}}{m}\ln^{2}(B_{2}m+B_{3})}\leq c\epsilon$

when

$\displaystyle m=c\frac{B_{1}}{\epsilon^{2}}\\{\ln(m(B_{2}+B_{3}+1))\\}^{2}.$

for some constant $c$.