$\displaystyle=\frac{1}{2}\binom{\binom{m/2}{2}}{\frac{t}{n/m}}^{n/m}\geq\frac{1}{2}\binom{\frac{m^{2}}{16}}{\frac{t}{n/m}}^{n/m}\geq\frac{1}{2}\left(\frac{\frac{m^{2}}{16}}{\frac{t}{n/m}}\right)^{\frac{t}{n/m}\cdot
n/m}=\frac{1}{2}\left(\frac{nm}{16t}\right)^{t}\,.$ (7.14)

Next, we rewrite

$\displaystyle\textup{{H}}\left(M_{G^{\prime}}\,\middle|\,G^{\prime}\in\mathcal{I}_{t}^{(1)}\right)$
$\displaystyle\geq\textup{{I}}\left(G^{\prime};M_{G^{\prime}}\,\middle|\,G^{\prime}\in\mathcal{I}_{t}^{(1)}\right)$
$\displaystyle=\textup{{H}}\left(G^{\prime}\,\middle|\,G^{\prime}\in\mathcal{I}_{t}^{(1)}\right)-\textup{{H}}\left(G^{\prime}\,\middle|\,M_{G^{\prime}},G^{\prime}\in\mathcal{I}_{t}^{(1)}\right)\,.$

Now, observing that all the graphs with same number of edges have the same
probability of being sampled, one can employ the upper and lower bounds
derived above:

$\displaystyle\hphantom{=}\textup{{H}}\left(G^{\prime}\,\middle|\,G^{\prime}\in\mathcal{I}_{t}^{(1)}\right)-\textup{{H}}\left(G^{\prime}\,\middle|\,M_{G^{\prime}},{G^{\prime}\in\mathcal{I}_{t}^{(1)}}\right)$
$\displaystyle\geq\log\left(\left|\mathcal{I}^{(1)}_{t}\right|\right)-\log\left(\max_{M\in\\{0,1\\}^{\leq
nm}}\left|\left\\{H\in\mathcal{I}^{(1)}_{t}:\,M_{H}=M_{G^{\prime}}\right\\}\right|\right)$
by (7.14) and (7.11) $\displaystyle\geq
t\log\left(\frac{\frac{1}{2}\frac{nm}{16t}}{\mathrm{e}^{(1+1/\mathrm{e})}\cdot\frac{nm}{8t}\cdot{(t)}^{1/t}\cdot\left(500\cdot\frac{\epsilon
t}{n}\right)^{1/10}}\right)\,.$

Then, we finish using $9/10\cdot dn/2\leq t\leq 11/10\cdot dn/2$ and
$\epsilon\leq{10^{-33}}/{d}$:

$\displaystyle\textup{{H}}\left(M_{G^{\prime}}\,\middle|\,G^{\prime}\in\mathcal{I}_{t}^{(1)}\right)\geq
t\log\left(\frac{1/120}{\left(500\cdot\frac{\epsilon
11dn}{20n}\right)^{1/10}}\right)\geq t\log
6\geq\frac{9}{10}\frac{dn}{2}\geq\frac{dn}{3}\,.$

∎

######  Claim 7.22.

One has

$\Pr_{G^{\prime}=(S,E^{\prime})\sim\mathcal{G}^{\prime}}\left[|E^{\prime}|\in\left[\frac{9}{20}dn,\,\frac{11}{20}dn\right]\,\mathrm{and}\,\frac{\left|\mathcal{I}_{|E^{\prime}|}^{(1)}\right|}{\left|\mathcal{I}_{|E^{\prime}|}\right|}\geq\frac{1}{2}\right]\geq\frac{1}{10}\,.$

###### Proof.

We begin by defining for convenience

$x=\Pr_{G^{\prime}=(S,E^{\prime})\sim\mathcal{G}^{\prime}}\left[\frac{\left|\mathcal{I}_{|E^{\prime}|}^{(1)}\right|}{\left|\mathcal{I}_{|E^{\prime}|}\right|}<\frac{1}{2}\right]\,.$

Then, by Lemma 7.9 (which applies by our assumption on $m$ and $d$), one has

$\Pr_{G^{\prime}=(S,E^{\prime})\sim\mathcal{G}^{\prime}}\left[|E^{\prime}|\in\left[\frac{9}{20}dn,\,\frac{11}{20}dn\right]\,\mathrm{and}\,\frac{\left|\mathcal{I}_{|E^{\prime}|}^{(1)}\right|}{\left|\mathcal{I}_{|E^{\prime}|}\right|}\geq\frac{1}{2}\right]\geq
1-\frac{1}{n}-x\,.$ (7.15)

We are left with the task of upper-bounding the probability $x$. Letting
$\mathcal{T}=\\{0,\dots,\binom{m/2}{2}\frac{n}{m}\\}$ be the set of possible
numbers of edges in $G^{\prime}\sim\mathcal{G}^{\prime}$, we have

$\displaystyle\hphantom{=}\Pr_{G^{\prime}=(S,E^{\prime})\sim\mathcal{G}^{\prime}}\left[\mathcal{Q}\text{
outputs correctly on input }G^{\prime}\right]$
$\displaystyle=\Pr_{G^{\prime}=(S,E^{\prime})\sim\mathcal{G}^{\prime}}\left[G^{\prime}\in\mathcal{I}^{(1)}\right]$
$\displaystyle=\sum_{t\in\mathcal{T}}\Pr_{G^{\prime}=(S,E^{\prime})\sim\mathcal{G}^{\prime}}[|E^{\prime}|=t]\Pr_{G^{\prime}=(S,E^{\prime})\sim\mathcal{G}^{\prime}}[G^{\prime}\in\mathcal{I}^{(1)}\,|\,|E^{\prime}|=t]$
$\displaystyle=\sum_{t\in\mathcal{T}}\Pr_{G^{\prime}=(S,E^{\prime})\sim\mathcal{G}^{\prime}}[|E^{\prime}|=t]\cdot\frac{\left|\mathcal{I}_{t}^{(1)}\right|}{\left|\mathcal{I}_{t}\right|}\,,$

where the last equality holds because all the graphs with $t$ edges have the
same probability of being sampled. Hence, splitting the sum one has

$\displaystyle\hphantom{=}\Pr_{G^{\prime}=(S,E^{\prime})\sim\mathcal{G}^{\prime}}\left[\mathcal{Q}\text{
outputs correctly on input }G^{\prime}\right]$
$\displaystyle\leq\sum_{\begin{subarray}{c}t\in\mathcal{T}:\\\
|\mathcal{I}_{t}^{(}1)|<\frac{1}{2}|\mathcal{I}_{t}^{(}1)|\end{subarray}}\Pr_{G^{\prime}=(S,E^{\prime})\sim\mathcal{G}^{\prime}}[|E^{\prime}|=t]\cdot\frac{1}{2}+\sum_{\begin{subarray}{c}t\in\mathcal{T}:\\\
|\mathcal{I}_{t}^{(}1)|\geq\frac{1}{2}|\mathcal{I}_{t}^{(}1)|\end{subarray}}\Pr_{G^{\prime}=(S,E^{\prime})\sim\mathcal{G}^{\prime}}[|E^{\prime}|=t]\cdot
1$
$\displaystyle=\Pr_{G^{\prime}=(S,E^{\prime})\sim\mathcal{G}^{\prime}}\left[\frac{\left|\mathcal{I}_{|E^{\prime}|}^{(1)}\right|}{\left|\mathcal{I}_{|E^{\prime}|}\right|}<\frac{1}{2}\right]\cdot\frac{1}{2}+\Pr_{G^{\prime}=(S,E^{\prime})\sim\mathcal{G}^{\prime}}\left[\frac{\left|\mathcal{I}_{|E^{\prime}|}^{(1)}\right|}{\left|\mathcal{I}_{|E^{\prime}|}\right|}\geq\frac{1}{2}\right]\cdot
1$ $\displaystyle=x\cdot\frac{1}{2}+(1-x)\cdot 1=1-\frac{x}{2}\,.$

If we suppose for the sake of a contradiction that $x\geq 449/500$, then

$\Pr_{G^{\prime}=(S,E^{\prime})\sim\mathcal{G}^{\prime}}\left[\mathcal{Q}\text{
outputs correctly on input
}G^{\prime}\right]\leq\frac{551}{1000}<\frac{3}{5}\,,$

which contradicts our assumption on $\mathcal{Q}$. Therefore, we plug
$x<449/500$ into (7.15) together with the assumption $n>m\geq 500$, thus
getting the claim. ∎

Let now $\mathcal{C}$ be the event that $|E^{\prime}|\in[9/10\cdot
dn/2,\,11/10\cdot dn/2]$ and
$|\mathcal{I}^{(1)}_{|E^{\prime}|}|\geq{1}/{2}\cdot|\mathcal{I}_{|E^{\prime}|}|$.
The size of Alice’s message on input
$G^{\prime}=(S,E^{\prime})\sim\mathcal{G}^{\prime}$ is lower bounded by

$\displaystyle\textup{{H}}\left(M_{G^{\prime}}\right)$
$\displaystyle\geq\textup{{H}}\left(M_{G^{\prime}}\,\middle|\,\operatorname{\mathbbm{1}}_{\mathcal{C}},|E^{\prime}|\right)$
$\displaystyle\geq\Pr\left[\mathcal{C}\right]\sum_{\begin{subarray}{c}t\in\left[\frac{9}{20}dn,\,\frac{11}{20}dn\right]\cap\mathbb{N}:\\\
\left|\mathcal{I}^{(1)}_{t}\right|\geq{1}/{2}\cdot\left|\mathcal{I}_{t}\right|\end{subarray}}\Pr\left[|E^{\prime}|=t\,\middle|\,\mathcal{C}\right]\cdot\textup{{H}}\left(M_{G^{\prime}}\,\middle|\,{\mathcal{C}},|E^{\prime}|=t\right)\,,$

and because conditioning does not increase entropy we rewrite

$\displaystyle\textup{{H}}\left(M_{G^{\prime}}\right)$
$\displaystyle\geq\Pr\left[\mathcal{C}\right]\sum_{\begin{subarray}{c}\frac{9}{20}dn\leq
t\leq\frac{11}{20}dn:\\\
|\mathcal{I}^{(1)}_{t}|\geq{1}/{2}\cdot|\mathcal{I}_{t}|\end{subarray}}\Pr\left[|E^{\prime}|=t\,\middle|\,\mathcal{C}\right]\cdot\textup{{H}}\left(M_{G^{\prime}}\,\middle|\,\operatorname{\mathbbm{1}}_{G^{\prime}\in\mathcal{I}^{(1)}},{\mathcal{C}},|E^{\prime}|=t\right)$
$\displaystyle\geq\Pr\left[\mathcal{C}\right]\sum_{\begin{subarray}{c}\frac{9}{20}dn\leq
t\leq\frac{11}{20}dn:\\\
|\mathcal{I}^{(1)}_{t}|\geq{1}/{2}\cdot|\mathcal{I}_{t}|\end{subarray}}\Pr\left[|E^{\prime}|=t\,\middle|\,\mathcal{C}\right]\cdot\Pr\left[G^{\prime}\in\mathcal{I}^{(1)}\,\middle|\,|E^{\prime}|=t\right]\cdot\textup{{H}}\left(M_{G^{\prime}}\,\middle|\,{G^{\prime}\in\mathcal{I}_{t}^{(1)}}\right)\,.$

Finally, we use 7.20 and 7.22 and get

$\displaystyle\textup{{H}}\left(M_{G^{\prime}}\right)$
$\displaystyle\geq\Pr\left[\mathcal{C}\right]\sum_{\begin{subarray}{c}\frac{9}{20}dn\leq
t\leq\frac{11}{20}dn:\\\
|\mathcal{I}^{(1)}_{t}|\geq{1}/{2}\cdot|\mathcal{I}_{t}|\end{subarray}}\Pr\left[|E^{\prime}|=t\,\middle|\,\mathcal{C}\right]\cdot\frac{1}{2}\cdot\frac{dn}{3}$
$\displaystyle=\frac{dn}{6}\Pr_{G^{\prime}=(S,E^{\prime})\sim\mathcal{G}^{\prime}}\left[|E^{\prime}|\in\left[\frac{9}{20}dn,\,\frac{11}{20}dn\right]\,\mathrm{and}\,\frac{\left|\mathcal{I}_{|E^{\prime}|}^{(1)}\right|}{\left|\mathcal{I}_{|E^{\prime}|}\right|}\geq\frac{1}{2}\right]$
$\displaystyle\geq\frac{dn}{60}\,.$

∎

###  7.4 Proving the lower bound

Finally, we set $d$ and $m$ depending on $\epsilon,\phi,n$ so as to combine
Lemma 7.15 and Lemma 7.19 and conclude our streaming lower bound. See 3

###### Proof.

We recall that for any $\epsilon=1-\Omega(1)$, computing an
$(\epsilon,\phi)$-ED with constant probability requires $\Omega(n\log n)$ bits
for all $\phi\in(0,\epsilon]$. To see why, consider an input graph that is a
matching of size $n/10$, and notice that an ED is a $1-\epsilon$ fraction the
edges. Therefore, we now consider the case $\epsilon=O(1/\log n)$ and prove an
$\Omega(n/\epsilon)$ lower bound.

Let $\epsilon,\phi\in(0,1)$ be any ED parameters and define $c=\psi\cdot
10^{-40}$. Note that $c$ is a constant since $\psi=\Omega(1)$ is the fixed
sparsity from Definition 7.2. In order to apply Lemma 7.15 and Lemma 7.19, we
use distributions $\mathcal{G}$ and $\mathcal{G}^{\prime}$ from Definition 7.2
with $d$ and $m$ set as follows:

$d=\frac{\epsilon}{2c^{3}\phi}+\frac{c}{2\epsilon}\quad\text{and}\quad
m=\frac{11}{c\phi}\,.$ (7.16)

We verify that these values meet the preconditions set by Lemma 7.15 and Lemma
7.19, i.e. we show that $d$ and $m$ satisfy

$\epsilon\leq\min\left\\{10^{-5}\psi\frac{d}{m},\,\frac{1}{30\sqrt{m}},\,\frac{10^{-33}}{d}\right\\}\,,\quad\phi\geq\frac{11}{m}\,,\quad
500\leq m\leq\frac{n}{100}\,,\quad 600\log n\leq d<m\,,$ (7.17)

for all $\epsilon,\phi$ such that

$\epsilon\leq\frac{c^{2}}{\log
n}\,,\quad\phi\geq\frac{1}{c^{2}n}\,,\quad\text{and}\quad\frac{\epsilon^{2}}{c^{4}}\leq\phi\leq\epsilon\,.$
(7.18)

Substituting $d$ and $m$ as defined in (7.16) into (7.17) we get

$10^{-5}\psi\frac{d}{m}=10^{-5}\psi\left(\frac{\epsilon}{2c^{3}\phi}+\frac{c}{2\epsilon}\right)\cdot\frac{c\phi}{11}\geq
10^{-5}\psi\frac{\epsilon}{2c^{2}11}=10^{75}\frac{\epsilon}{2\psi
11}\geq\epsilon\,,$
$\frac{1}{30\sqrt{m}}=\frac{\sqrt{c}\sqrt{\phi}}{30\sqrt{11}}\geq\frac{\sqrt{c}\epsilon}{30\sqrt{11}c^{2}}\geq\epsilon\,,$
$\frac{10^{-33}}{d}=10^{-33}\frac{4c^{3}\epsilon\phi}{2\epsilon^{2}+2c^{4}\phi}=10^{-33}\frac{4c^{3}\epsilon}{2\epsilon^{2}/\phi+2c^{4}}\geq
10^{-33}\frac{4c^{3}\epsilon}{2c^{4}+2c^{4}}=10^{-33}\frac{\epsilon}{c}\geq\epsilon\,,$
$\frac{11}{m}=c{\phi}\leq\phi\,,$
$m=\frac{11}{c\phi}\geq\frac{11}{c\epsilon}\geq\log n\geq 500\,,$
$m=\frac{11}{c\phi}\leq 11cn\leq\frac{n}{100}\,,$
$d=\frac{\epsilon}{2c^{3}\phi}+\frac{c}{2\epsilon}\geq\frac{c}{2\epsilon}\geq\frac{\log
n}{2c}\geq 600\log n\,,$
$d=\frac{\epsilon}{2c^{3}\phi}+\frac{c}{2\epsilon}\leq\frac{\epsilon}{2c^{3}\phi}+\frac{c}{2\phi}\leq\frac{1}{2c\log
n\phi}+\frac{c}{2\phi}<\frac{11}{c\phi}=m\,,$

so all the conditions (7.17) are verified.

With any $\epsilon,\phi$ as in (7.18) and for our choice of $d,m$ as in
(7.17), Lemma 7.15 gives that if there is an $L$-bit space deterministic
streaming algorithm $\mathcal{A}$ that outputs an $(\epsilon,\phi,2)$-RED of
$G\sim\mathcal{G}_{n,d,m}$ with probability at least $9/10$, then there is a
deterministic protocol $\mathcal{Q}$ that solves
$\operatorname*{\textsc{recover}}_{\epsilon m}$ with probability at least
$3/5$ over inputs $G^{\prime}\sim\mathcal{G}^{\prime}$ with communication
complexity $L$. On the other hand, by Lemma 7.19 we know that, in the
parameter regime of (7.17), the complexity of $\mathcal{Q}$ over
$\mathcal{G}^{\prime}$ is at least $\Omega(dn)$. Hence,

$L=\Omega(dn)=\Omega\left(\left(\frac{\epsilon}{\phi}+\frac{1}{\epsilon}\right)\cdot
n\right)=\Omega\left(\frac{n}{\epsilon}\right)\,.$

By Yao’s minimax principle, the theorem statement is proved with $C=c^{-4}$.

∎

## References

  * [AALG18] Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan.  Graph Clustering using Effective Resistance.  In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 41:1–41:16, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [AG09] Kook Jin Ahn and Sudipto Guha.  Graph sparsification in the semi-streaming model.  In Proceedings of the 36th Internatilonal Collogquium on Automata, Languages and Programming: Part II, ICALP ’09, page 328–338, Berlin, Heidelberg, 2009. Springer-Verlag.
  * [AGM12a] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Analyzing graph structure via linear measurements.  In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 459–467, 2012.
  * [AGM12b] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Graph sketches: Sparsification, spanners, and subgraphs.  In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS ’12, page 5–14, New York, NY, USA, 2012\. Association for Computing Machinery.
  * [AKLP22] Arpit Agarwal, Sanjeev Khanna, Huan Li, and Prathamesh Patil.  Sublinear algorithms for hierarchical clustering.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 3417–3430. Curran Associates, Inc., 2022.
  * [APP+23] A. Ahmadinejad, J. Peebles, E. Pyne, A. Sidford, and S. Vadhan.  Singular value approximation and sparsifying random walks on directed graphs.  In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 846–854, Los Alamitos, CA, USA, nov 2023. IEEE Computer Society.
  * [BK15] András A. Benczúr and David R. Karger.  Randomized approximation schemes for cuts and flows in capacitated graphs.  SIAM Journal on Computing, 44(2):290–319, 2015.
  * [CGL+20] Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak.  A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1158–1167, 2020.
  * [CGP+18] Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, and Junxing Wang.  Graph sparsification, spectral sketches, and faster resistance computation, via short cycle decompositions.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 361–372, 2018.
  * [CKK+06] Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D. Sivakumar.  On the hardness of approximating multicut and sparsest-cut.  Computational Complexity, 1506:94–114, 06 2006.
  * [CKL+22a] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva.  Maximum flow and minimum-cost flow in almost-linear time.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 612–623, 2022.
  * [CKL22b] Yu Chen, Sanjeev Khanna, and Huan Li.  On weighted graph sparsification by linear sketching.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 474–485, 2022.
  * [CPSZ21] Yi-Jun Chang, Seth Pettie, Thatchaphol Saranurak, and Hengjie Zhang.  Near-optimal distributed triangle enumeration via expander decompositions.  J. ACM, 68(3):21:1–21:36, 2021.
  * [CS19] Yi-Jun Chang and Thatchaphol Saranurak.  Improved distributed expander decomposition and nearly optimal triangle enumeration.  In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC ’19, page 66–73, New York, NY, USA, 2019. Association for Computing Machinery.
  * [FHHP11] Wai Shing Fung, Ramesh Hariharan, Nicholas J.A. Harvey, and Debmalya Panigrahi.  A general framework for graph sparsification.  In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11, page 71–80, New York, NY, USA, 2011. Association for Computing Machinery.
  * [FKM23] Arnold Filtser, Michael Kapralov, and Mikhail Makarov.  Expander Decomposition in Dynamic Streams.  In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (LIPIcs), pages 50:1–50:13, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [GHKM23] V. Guruswami, J. Hsieh, P. K. Kothari, and P. Manohar.  Efficient algorithms for semirandom planted csps at the refutation threshold.  In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 307–327, Los Alamitos, CA, USA, nov 2023. IEEE Computer Society.
  * [GHN+23] Gramoz Goranci, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak, Mikkel Thorup, and Christian Wulff-Nilsen.  Fully dynamic exact edge connectivity in sublinear time.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 70–86, 2023.
  * [GRST21] Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, and Zihan Tan.  The expander hierarchy and its applications to dynamic graph algorithms.  In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), page 2212–2228, 2021.
  * [HKGW23] Yiding Hua, Rasmus Kyng, Maximilian Probst Gutenberg, and Zihang Wu.  Maintaining expander decompositions via sparse cuts.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 48–69, 2023.
  * [Ind06] Piotr Indyk.  Stable distributions, pseudorandom generators, embeddings, and data stream computation.  J. ACM, 53(3):307–323, may 2006.
  * [Kar93] David R. Karger.  Global min-cuts in rnc, and other ramifications of a simple min-cut algorithm.  In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’93, page 21–30, USA, 1993. Society for Industrial and Applied Mathematics.
  * [Kar94] David R Karger.  Random sampling in cut, flow, and network design problems.  In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pages 648–657, 1994.
  * [KKTY21] Michael Kapralov, Robert Krauthgamer, Jakab Tardos, and Yuichi Yoshida.  Towards tight bounds for spectral sparsification of hypergraphs.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 598–611, New York, NY, USA, 2021. Association for Computing Machinery.
  * [KLM+14] Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford.  Single pass spectral sparsification in dynamic streams.  In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 561–570, 2014.
  * [KMM+20] Michael Kapralov, Aida Mousavifar, Cameron Musco, Christopher Musco, Navid Nouri, Aaron Sidford, and Jakab Tardos.  Fast and space efficient spectral sparsification in dynamic streams.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1814–1833, 2020.
  * [KVV00] Ravi Kannan, Santosh Vempala, and Adrian Vetta.  On clusterings-good, bad and spectral.  In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 367–377, 2000.
  * [Li21] Jason Li.  Deterministic mincut in almost-linear time.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 384–395, New York, NY, USA, 2021. Association for Computing Machinery.
  * [LNPS23] Jason Li, Danupon Nanongkai, Debmalya Panigrahi, and Thatchaphol Saranurak.  Near-linear time approximations for cut problems via fair cuts.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 240–275, 2023.
  * [Nis92] Noam Nisan.  Pseudorandom generators for space-bounded computation.  Combinatorica, 12:449–461, 1992.
  * [ST04] Daniel A. Spielman and Shang-Hua Teng.  Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems.  In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’04, page 81–90, New York, NY, USA, 2004. Association for Computing Machinery.
  * [ST11] Daniel A. Spielman and Shang-Hua Teng.  Spectral sparsification of graphs.  SIAM Journal on Computing, 40(4):981–1025, 2011.
  * [SW19] Thatchaphol Saranurak and Di Wang.  Expander decomposition and pruning: Faster, stronger, and simpler.  In Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2616–2635, 2019.
  * [Tre08] Luca Trevisan.  Approximation algorithms for unique games.  Theory Comput., 4(1):111–128, 2008.
  * [Tro15] Joel A. Tropp.  An introduction to matrix concentration inequalities.  Foundations and Trends in Machine Learning, 8(1-2):1–230, 2015\.

##  Appendix A Technical facts

###  A.1 Fast balanced sparse cut algorithm

In this section, we prove the following fast BSCA, used for our polynomial
time BLD construction.

See 6.2

###### Proof.

Hereafter we use $n$ and $m$ to denote the number of vertices and edges
respectively. An algorithm was recently given that, for $n$-vertex $m$-edge
input graphs with polynomially bounded edge weights, produces a
$(O(\phi\log^{3}n),\phi)$-ED555In this case, the definition of ED uses the
weight of edges across cuts, and weighted volumes, including self-loops. with
high probability in $\widetilde{O}(m)$ time, for any $\phi\in(0,1)$ [LNPS23].
One can then use this ED algorithm to efficiently compute a an approximate
balanced $\psi$-sparse cut for all $\psi\in(0,1)$: as it was observed in
[SW19], given access to a graph and its $(O(\psi\log^{3}n),\psi)$-ED, one can
easily obtain a $(\psi,c^{\prime}\cdot\log^{3}n,C^{\prime},0)$-BSCW for some
constants $c^{\prime},C^{\prime}\geq 1$. This gives a
$(c^{\prime}\cdot\log^{3}n,C^{\prime})$-BSCA that runs in $\widetilde{O}(m)$
time for all input sparsity parameters $\psi\in(0,1)$. However, these results
were not stated for graphs with arbitrary self-loops, which is what we need.
Hence, we give a simple reduction from the self-loop case to the self-loop
free one, without increasing the size of the graph by more than constant
factors, so as to fit our setting.

Let $G=(V,E,w)$ be a weighted undirected graph with one weighted self-loop per
vertex, where $w:E\cup V\rightarrow\mathbb{R}_{\geq 0}$ and
$E\subseteq\binom{V}{2}$. The idea is to construct a graph with two copies of
every vertex, where the surplus vertices are solely connected to their
corresponding vertex with weight equal to half the weight of the self-loop. If
a vertex has no self-loops then we make only one copy for it. Formally, let
$A=\\{u\in V:w(u)>0\\}$ be the set of vertices with self-loops. Then let $B$
be a copy of $A$ representing the self-loops of vertices in $A$, and let
$s:A\rightarrow B$ be a bijection mapping $u\in A$ to its corresponding self-
loop vertex $s(u)\in B$. We define the self-loop free graph to be
$\widehat{G}=(\widehat{V},\widehat{E},\widehat{w})$, where $\widehat{V}=V\cup
s(A)$, $\widehat{E}=E\cup(\cup_{u\in A}\\{\\{u,s(u)\\}\\})$, and
$\widehat{w}(e)=w(e)$ for every $e\in E$ and
$\widehat{w}(\\{u,s(u)\\})=\frac{1}{2}w(u)$ for all $u\in A$. This is
illustrated in Figure 6. We highlight that $\widehat{G}$ has the same number
of vertices and edges as $G$, up to constants.

Figure 6: On the left: the original graph with self-loops $G$. On the right:
its self-loop free version $\widehat{G}$. The weights of the internal edges of
$G$ are copied verbatim (not shown in the figure), while the weights of self-
loops are halved.

We run a BSCA for self-loop free graphs on $\widehat{G}$, and if it asserts
$\widehat{G}$ to be an expander we conclude the same for $G$, whereas if it
returns a cut then we tweak it to get a solution for $G$. This is summarised
in Algorithm 5. The following claim gives the correctness of the reduction.
The idea is that the subgraphs given by $\\{u,s(u)\\}$ for $u\in A$ are
expanders, so there is no good reason for a sparse cut to cross them. Hence,
$u$ and $s(u)$ should be on the same side of the sparse cuts.

Algorithm 5 SelfLoopBalSparseCut: reduction to self-loop free BSCA

1: $\triangleright$ _$G=(V,E,w)$ is a weighted undirected graph_

2: $\triangleright$ _$\phi\in(0,1)$ is the sparsity parameter_
SelfLoopBalSparseCut$(G,\phi)$

3:$\widehat{\omega}\leftarrow\textsc{BalSparseCut}_{\alpha,\lambda}(\widehat{G},\phi)$
$\triangleright$ $\widehat{G}$ is the self-loop free version of $G$ as
described above $\widehat{\omega}=\bot$

4:$\omega\leftarrow\bot$

5:$(R,\nu)\leftarrow\widehat{\omega}$

6:$X\leftarrow R\cap V$

7:$X^{*}\leftarrow\operatorname*{argmin}\\{\operatorname{vol}_{G}(X),\operatorname{vol}_{G}(V\setminus
X)\\}$

8:$\omega\leftarrow(X^{*},\operatorname{vol}_{G}(X^{*}))$

9:$\omega$

######  Claim A.1.

Let $\textsc{BalSparseCut}_{\alpha,\lambda}$ be an $(\alpha,\lambda)$-BSCA.
Then SelfLoopBalSparseCut is a $(2\alpha,4\lambda)$-BSCA, provided that the
input sparsity parameter $\phi\in(0,1)$ satisfies
$\phi\leq\frac{1}{10\alpha}$.

###### Proof.

For any cut $\emptyset\neq X\subsetneq V$, let us define for convenience
$\partial_{G}X=w(X,V\setminus X)$ to be the total weight of the edges crossing
the cut $X$ in $G$, and for any cut $\emptyset\neq R\subsetneq\widehat{V}$
define $\partial_{\widehat{G}}R=\widehat{w}(R,\widehat{V}\setminus R)$ to be
the total weight of edges crossing $R$ in $\widehat{G}$. A preliminary
observation is that for any cut $\emptyset\neq X\subsetneq V$ we have that
$\operatorname{vol}_{\widehat{G}}(X\cup s(X\cap
A))=\operatorname{vol}_{G}(X)$, $\partial_{\widehat{G}}(X\cup s(X\cap
A))=\partial_{G}X$, and consequently $\Phi_{\widehat{G}}(X\cup s(X\cap
A))=\Phi_{G}(X)$. By definition of $\textsc{BalSparseCut}_{\alpha,\lambda}$,
we know that $\widehat{\omega}$ is a $(\phi,\alpha,\lambda,0)$-BSCW of
$\widehat{G}$, i.e.

  1. 1.

if $\widehat{\omega}=\bot$, then $\widehat{G}$ is a $\phi$-expander;

  2. 2.

if $\widehat{\omega}=(R,\nu)$, then:

    1. (a)

$\Phi_{\widehat{G}}(R)<\alpha\cdot\phi$,

    2. (b)

$\operatorname{vol}_{\widehat{G}}(R)\leq\operatorname{vol}_{\widehat{G}}(\widehat{V}\setminus
R)$,

    3. (c)

for every other cut $\emptyset\neq T\subsetneq\widehat{V}$ with
$\Phi_{\widehat{G}}(T)<\phi$ and
$\operatorname{vol}_{\widehat{G}}(T)\leq\operatorname{vol}_{\widehat{G}}(\widehat{V}\setminus
T)$ one has
$\operatorname{vol}_{\widehat{G}}(T)\leq\lambda\operatorname{vol}_{\widehat{G}}(R)$:

    4. (d)

$\nu=\operatorname{vol}_{\widehat{G}}(R)$.

Our goal is to translate these properties to $G$ by showing that $\omega$, as
constructed in SelfLoopBalSparseCut, is a $(\phi,2\alpha,4\lambda,0)$-BSCW of
$G$, i.e.

  1. 1.

if $\omega=\bot$, then ${G}$ is a $\phi$-expander;

  2. 2.

if $\omega=(X^{*},\nu)$, then:

    1. (a)

$\Phi_{{G}}(X^{*})<\alpha\cdot\phi$,

    2. (b)

$\operatorname{vol}_{{G}}(X^{*})\leq\operatorname{vol}_{{G}}({V}\setminus
X^{*})$,

    3. (c)

for every other cut $\emptyset\neq T\subsetneq{V}$ with $\Phi_{{G}}(T)<\phi$
and $\operatorname{vol}_{{G}}(T)\leq\operatorname{vol}_{{G}}({V}\setminus T)$
one has
$\operatorname{vol}_{{G}}(T)\leq\lambda\operatorname{vol}_{{G}}(X^{*})$:

    4. (d)

$\nu=\operatorname{vol}_{{G}}(X^{*})$.

##### Correctness of the case $\widehat{\omega}=\bot$.

This means that for every cut $\emptyset\neq R\subsetneq\widehat{V}$ one has
$\Phi_{\widehat{G}}(R)\geq\phi$. This in particular holds for cuts of the form
$X\cup s(X\cap A)$ with $\emptyset\neq X\subsetneq V$. As we observed that
$\Phi_{\widehat{G}}(X\cup s(X\cap A))=\Phi_{G}(X)$, we conclude that $G$ is
also a $\phi$-expander.

##### Correctness of the case $\widehat{\omega}=(R,\nu)$.

The idea is that adding missing self-loops and removing dangling self-loops
makes $R$ a solution for $G$. This is illustrated in Figure 7.

Figure 7: There is a straightforward correspondence between the shaded cuts in
$G$ and $\widehat{G}$, since they have same volume and same number of crossing
edges. The dashed cut has missing self-loops and dangling self-loops (think of
it as the cut $R$). The dotted cut adds the missing self-loops (think of it as
the cut $Q$). The shaded cut in $\widehat{G}$ removes the dangling self-loops
(think of it as the cut $P$), and corresponds to the shaded cut in $G$ (think
of it as the cut $X$).

We know from (2a) that

$\frac{\partial_{\widehat{G}}R}{\operatorname{vol}_{\widehat{G}}(R)}<\alpha\phi\,.$

Consider the cut $Q=R\cup s(R\cap A)$, i.e. a version of $R$ where we have
added the self-loops of all the vertices in $R$ that have one. Then
$Q\subsetneq\widehat{V}$, as otherwise $V\subseteq R$, which would imply that
$R$ contains more than half the volume of
$\operatorname{vol}_{\widehat{G}}(\widehat{V})$, contradicting (2b). Next, we
remark that the volume of $Q$ cannot decrease compared to $R$, since we added
vertices, i.e.

$\operatorname{vol}_{\widehat{G}}(Q)=\operatorname{vol}_{\widehat{G}}(R)+\partial_{\widehat{G}}(s(R\cap
A)\setminus(R\cap B))\geq\operatorname{vol}_{\widehat{G}}(R)\,.$ (A.1)

At the same time, we do not increase the number of crossing edges since we
move the self-loop edges inside the cut, so

$\frac{\partial_{\widehat{G}}Q}{\operatorname{vol}_{\widehat{G}}(Q)}=\frac{\partial_{\widehat{G}}R-\partial_{\widehat{G}}(s(R\cap
A)\setminus(R\cap
B))}{\operatorname{vol}_{\widehat{G}}(R)+\partial_{\widehat{G}}(s(R\cap
A)\setminus(R\cap
B))}\leq\frac{\partial_{\widehat{G}}R}{\operatorname{vol}_{\widehat{G}}(R)}\,.$

Thus, we have added self-loops to $R$ without increasing its sparsity nor
decreasing its volume. Now we remove the dangling self-loops from $Q$, i.e. we
remove the set $D=(Q\cap B)\setminus s(Q\cap A)$, and consider the cut
$P=Q\setminus D$. We remark that $P\neq\emptyset$, as otherwise $R$ is solely
made of vertices from $s(A)$, which contradicts $\Phi_{H}(R)<\alpha\phi\leq
1/10<1$. Since we removed an equal amount of mass from both the crossing edges
and the volume, we get

$\frac{\partial_{\widehat{G}}P}{\operatorname{vol}_{\widehat{G}}(P)}\leq\min\left\\{\frac{\partial_{\widehat{G}}P}{\operatorname{vol}_{\widehat{G}}(P)},1\right\\}\leq\frac{\partial_{\widehat{G}}P+\partial_{\widehat{G}}D}{\operatorname{vol}_{\widehat{G}}(P)+\partial_{\widehat{G}}D}=\frac{\partial_{\widehat{G}}Q}{\operatorname{vol}_{\widehat{G}}(Q)}\,.$

Thus, removing the dangling self-loops does not increase sparsity. However we
may have decreased the volume, which threatens the balancedness property of
the cut. We then bound the decrease: because we proved before
${\partial_{\widehat{G}}Q}/{\operatorname{vol}_{\widehat{G}}(Q)}<\alpha\phi$,
we know

$\partial_{\widehat{G}}D<\frac{\alpha\phi}{1-\alpha\phi}\operatorname{vol}_{\widehat{G}}(P)\,,$

so

$\operatorname{vol}_{\widehat{G}}(Q)=\operatorname{vol}_{\widehat{G}}(P)+\partial_{\widehat{G}}D<2\operatorname{vol}_{\widehat{G}}(P)\,.$
(A.2)

Now one can see that $P$ is identical to $(R\cap V)\cup s(R\cap A)$, and $X$
as defined in Algorithm 5 equals $R\cap V$. Hence
$\partial_{G}X=\partial_{\widehat{G}}P$ and
$\operatorname{vol}_{G}(X)=\operatorname{vol}_{\widehat{G}}(P)$. Therefore,

$\frac{\partial_{G}X}{\operatorname{vol}_{G}(X)}<\alpha\phi\,.$ (A.3)

To handle the case where $X$ is the larger volume side of the cut, Algorithm 5
takes $X^{*}$ to be the side of $(X,V\setminus X)$ with smaller volume. We
show that the volume of $V\setminus X$ is within a small constant factor of
the volume of $X$. To do so, recall that $\Phi_{\widehat{G}}(R)<\alpha\phi$,
so

$\frac{\partial_{\widehat{G}}Q+\partial_{\widehat{G}}(s(R\cap
A)\setminus(R\cap
B))}{\operatorname{vol}_{\widehat{G}}(Q)-\partial_{\widehat{G}}(s(R\cap
A)\setminus(R\cap B))}<\alpha\phi\,,$

which implies

$\partial_{\widehat{G}}(s(R\cap A)\setminus(R\cap
B))<\alpha\phi\operatorname{vol}_{\widehat{G}}(Q)\,.$

Hence, by property (2b) of $R$, we have

$\operatorname{vol}_{G}(X)\leq\operatorname{vol}_{\widehat{G}}(Q)<\frac{1}{1-\alpha\phi}\operatorname{vol}_{\widehat{G}}(R)\leq\frac{1}{2}\cdot\frac{1}{1-\alpha\phi}\operatorname{vol}_{\widehat{G}}(\widehat{V})=\frac{1}{2}\cdot\frac{1}{1-\alpha\phi}\operatorname{vol}_{G}(V)\,.$

Therefore, we have that
$X^{*}=\operatorname*{argmin}\\{\operatorname{vol}_{G}(X),\operatorname{vol}_{G}(V\setminus
X)\\}$ satisfies

$(1-2\alpha\phi)\operatorname{vol}_{G}(X)\leq\operatorname{vol}_{G}(X^{*})\leq\operatorname{vol}_{G}(V\setminus
X^{*})\,,$ (A.4)

and

$\operatorname{vol}_{\widehat{G}}(R)<\frac{2}{1-2\alpha\phi}\operatorname{vol}_{G}(X^{*})\,,$
(A.5)

by (A.1), (A.2). We now conclude by verifying properties (2a), (2b), (2c),
(2d).

  * •

Property (2a). From (A.3) and (A.4), we get
$\Phi_{G}(X^{*})<\alpha\phi/({1-2\alpha\phi})\leq 2\alpha\phi$.

  * •

Property (2b). This property follows by definition of $X^{*}$ in Algorithm 5.

  * •

Property (2c). Consider any cut $\emptyset\neq T\subsetneq V$ such that
$\Phi_{G}(T)<\phi$ and
$\operatorname{vol}_{G}(T)\leq\operatorname{vol}_{G}(V\setminus T)$. Then we
know that

$\Phi_{G}(T)=\Phi_{\widehat{G}}(T\cup s(T\cap A))<\phi\,,$

and

$\operatorname{vol}_{\widehat{G}}(T\cup s(T\cap
A))=\operatorname{vol}_{G}(T)\leq\operatorname{vol}_{G}(V\setminus
T)=\operatorname{vol}_{\widehat{G}}(\widehat{V}\setminus(T\cup s(T\cap A))\,,$

as well as

$\operatorname{vol}_{G}(T)=\operatorname{vol}_{\widehat{G}}(T\cup s(T\cap
A))\leq\lambda\cdot\operatorname{vol}_{\widehat{G}}(R)<\frac{2\lambda}{1-2\alpha\phi}\operatorname{vol}_{G}(X^{*})\leq
4\lambda\operatorname{vol}_{G}(X^{*})\,,$

by an application of (2c) to the cut $T\cup s(T\cap A)$ and (A.5).

  * •

Property (2d). Follows directly by definition of $\omega$ in Algorithm 5.

∎ We use A.1 with $\alpha=c^{\prime}\log^{3}n$ and $\lambda=C^{\prime}$ (where
$c^{\prime},C^{\prime}\geq 1$ are the constants one gets from the self-loop
free BSCA of [SW19, LNPS23]). Then, we get a
$(c_{\operatorname*{\textsc{bsc}}}\log^{3}n,C_{\operatorname*{\textsc{bsc}}})$-BSCA
where $c_{\operatorname*{\textsc{bsc}}}=2c^{\prime}$ and
$C_{\operatorname*{\textsc{bsc}}}=4C^{\prime}$, provided that
$\phi\leq\frac{1}{10\alpha}$. Using $\phi=\psi$ and since we impose
$\psi\leq\frac{1}{10c_{\operatorname*{\textsc{bsc}}}\log^{3}n}$, we get
$\phi\leq\frac{1}{10\alpha}$. This concludes the proof of Theorem 6.2. ∎

###  A.2 Expansion and regularity of random graphs

See 7.10

###### Proof.

Let $H=(U,F)$ be a sample from $\operatorname*{ER}(N,p)$, so that $|U|=N$.
Also let $L=D-A$ be the Laplacian matrix of $H$, where $D$ denotes its degree
diagonal matrix and $A$ denotes its adjacency matrix. We use the following
matrix Bernstein concentration bound on $L$ to lower bound its second
eigenvalue, and then lower bound the expansion of $H$ using Cheeger’s
inequality.

######  Theorem A.2 (Theorem 1.6.2 in [Tro15]).

Let $S_{1},\dots,S_{\kappa}\in\mathbb{R}^{N\times N}$ be independent symmetric
random matrices such that $\operatorname{\mathbb{E}}[S_{\iota}]=0$ and
$\left\|S_{\iota}\right\|\leq\lambda$ for every $\iota\in[\kappa]$, and let
$S=\sum_{\iota=1}^{\kappa}S_{\iota}$. Then, for all $\theta\geq 0$

$\Pr[\left\|S\right\|\geq\theta]\leq
2N\cdot\exp\left(-\frac{\theta^{2}/2}{\left\|\sum_{\iota=1}^{\kappa}\operatorname{\mathbb{E}}[S_{\iota}^{2}]\right\|+\lambda\theta/3}\right)\,.$

We start by rewriting $L$ so that we can apply the above result. For each
$e=\\{u,v\\}\in\binom{V}{2}$ let $z_{e}\sim\operatorname*{Ber}(p)$ be an
independent Bernoulli random variable with bias $p$, and also let $L_{e}$ be
the Laplacian matrix of the graph $(U,\\{e\\})$, i.e. $(L_{e})_{ab}=1$ if
$a=b=u$ or $a=b=v$, $(L_{e})_{ab}=-1$ if $\\{a,b\\}=e$, and $(L_{e})_{ab}=0$
otherwise. Define $S_{e}=z_{e}L_{e}-\operatorname{\mathbb{E}}[z_{e}L_{e}]$ and
$S=\sum_{e\in\binom{V}{2}}S_{e}$. One can now note that

$\operatorname{\mathbb{E}}[S_{e}]=0\quad\text{and}\quad\left\|S_{e}\right\|\leq\max\left\\{\left\|(1-p)L_{e}\right\|,\left\|-pL_{e}\right\|\right\\}\leq
2\quad\text{for all $e\in\binom{V}{2}$.}$

Letting $J$ be the all-ones $N\times N$ matrix we also have

$S=\sum_{e\in\binom{V}{2}}z_{e}L_{e}-\sum_{e\in\binom{V}{2}}\operatorname{\mathbb{E}}[z_{e}L_{e}]=L-p\cdot(N\cdot
I-J)\,.$

Hence, Theorem A.2 with $\lambda=2$ gives

$\Pr[\left\|L-p\cdot(N\cdot I-J)\right\|\geq\theta]\leq
2N\cdot\exp\left(-\frac{\theta^{2}/2}{\left\|\sum_{e\in\binom{V}{2}}\operatorname{\mathbb{E}}[(z_{e}L_{e}-\operatorname{\mathbb{E}}[z_{e}L_{e}])^{2}]\right\|+2\theta/3}\right)\,.$
(A.6)

Now we observe that the first term in the denominator can be rewritten as

$\displaystyle\left\|\sum_{e\in\binom{V}{2}}\operatorname{\mathbb{E}}\left[(z_{e}L_{e}-\operatorname{\mathbb{E}}[z_{e}L_{e}])^{2}\right]\right\|$
$\displaystyle=\left\|\sum_{e\in\binom{V}{2}}2L_{e}\operatorname{\mathbb{E}}\left[(z_{e}-z_{e}\cdot
p+p^{2})\right]\right\|$
$\displaystyle=\left\|\sum_{e\in\binom{V}{2}}2pL_{e}\right\|$
$\displaystyle=2p\left\|N\cdot I-J\right\|$ $\displaystyle=2pN\,,$

where the last equality holds because $K\coloneqq N\cdot I-J$ is the Laplacian
matrix of the complete graph on $N$ vertices. If we now set $\theta=pN/10$ in
(A.6), we get

$\Pr\left[\left\|L-p\cdot K\right\|\geq\frac{1}{10}pN\right]\leq
2N\cdot\exp\left(-\frac{pN}{600}\right)\,.$ (A.7)

Now, in order to use a Cheeger type of inequality, it is convenient to view
$H$ as a regular graph, so that its normalized Laplacian matrix is simply a
scalar multiple of $L$. If we denote with $\deg(u)$ the degree of $u\in U$ in
$H$, we get by a Chernoff bound that

$\Pr\left[\text{$\exists u\in U$,
}\left|\deg(u)-p\cdot(N-1)\right|>\frac{1}{14}p\cdot(N-1)\right]\leq
2N\cdot\exp\left(-\frac{p\cdot(N-1)}{600}\right)\,.$ (A.8)

From (A.7) and (A.8), we then have

$\Pr\left[\left(\left\|L-pK\right\|\geq\frac{1}{10}pN\right)\text{ or
}\left(\exists u\in
U:\left|\deg_{H}(u)-\bar{d}\right|>\frac{1}{14}\bar{d}\right)\right]\leq
4N\cdot\exp\left(-\frac{pN}{600}\right)\,.$ (A.9)

We conclude by showing that if the event in the above probability does not
occur, then the event argument of the probability in the statement of 7.10
does not occur either. To see this, let $\lambda_{2}$ be the second smallest
eigenvalue of $1/\bar{d}\cdot L$, and $\mu_{2}$ be the second smallest
eigenvalue of $1/(N-1)\cdot K$. Hence, $\left\|L-pK\right\|<\frac{1}{10}pN$
implies $\lambda_{2}\geq\mu_{2}-1/9$ by Weyl’s inequality. Moreover, we know
that $\mu_{2}=N/(N-1)$, so $\lambda_{2}\geq 9/10$. Finally, let $\emptyset\neq
S\subsetneq U$ be a cut with
$\operatorname{vol}(S)\leq\operatorname{vol}(U\setminus S)$ such that
$\Phi_{H}(S)=\Phi_{H}$. Assuming
$\left|\deg_{H}(u)-\bar{d}\right|\leq\frac{1}{14}\bar{d}$ for all $u\in U$, we
have that $\operatorname{vol}(S)\in[(1-1/14)\bar{d}|S|,(1+1/14)\bar{d}|S|]$.
Let $\mathbf{y}\in\mathbb{R}^{U}$ be defined as $y_{u}=1/|S|$ if $u\in S$ and
$y_{u}=-1/|U\setminus S|$ otherwise. By Courant-Fischer we then have

$\displaystyle\lambda_{2}=\min_{\begin{subarray}{c}\mathbf{x}\in\mathbb{R}^{U}\setminus\\{\mathbf{0}\\}:\\\
\langle\mathbf{x},\operatorname{\mathbbm{1}}\rangle=0\end{subarray}}\,\frac{1}{\bar{d}}\cdot\frac{\mathbf{x}^{\top}L\mathbf{x}}{\mathbf{x}^{\top}\mathbf{x}}\leq\frac{1}{\bar{d}}\cdot\frac{\mathbf{y}^{\top}L\mathbf{y}}{\mathbf{y}^{\top}\mathbf{y}}=\frac{{\partial}_{U}S}{\bar{d}|S|}\cdot\frac{|U|}{|U\setminus
S|}\leq\left(1+\frac{1}{14}\right)\Phi_{H}\cdot\frac{|U|}{|U\setminus S|}\,.$
(A.10)

Again assuming $\left|\deg_{H}(u)-\bar{d}\right|\leq\frac{1}{14}\bar{d}$ for
all $u\in U$, one can check that
$\operatorname{vol}(S)\leq\operatorname{vol}(U\setminus S)$ implies
$|U\setminus S|\geq 6/7\cdot|S|$. Thus, (A.10) gives

$\lambda_{2}\leq\left(1+\frac{1}{14}\right)\cdot\left(1+\frac{7}{6}\right)\Phi_{H}\leq\frac{27}{10}\Phi_{H}\,,$

so $\Phi_{H}\geq 1/3$. ∎

###  A.3 A useful inequality

See 7.21

###### Proof.

Write $x=y\cdot\mathrm{e}^{\rho-1}$ for some $\rho\leq 1$. Then
$(y/x)^{x}\leq\mathrm{e}^{y/\mathrm{e}}$ if and only if
$(1-\rho)e^{\rho-1}\leq 1/\mathrm{e}$. Define
$f(\rho)=(1-\rho)\mathrm{e}^{\rho}$. We prove the claim by showing that
$f(\rho)\leq 1$ for all $\rho\in(-\infty,1]$.

We begin by noting that $f$ is continuous over $(-\infty,1]$. Then, we take
the derivative of $f$, and we get $f^{\prime}(\rho)=-\rho\mathrm{e}^{\rho}$.
We observe that $f^{\prime}(\rho)>0$ for $\rho<0$, and $f^{\prime}(\rho)>0$
for $\rho>0$. We further observe that $f(0)=1$, $f(1)=0$, and
$\lim_{\rho\rightarrow-\infty}f(\rho)=0$. Hence, $f(\rho)$ is upper-bounded by
$1$ for all $\rho\in(-\infty,1]$. ∎


# Accessing GPT-4 level Mathematical Olympiad Solutions via Monte Carlo Tree
Self-refine with LLaMa-3 8B: A Technical Report

Di Zhang
Fudan University
Shanghai Artificial Intelligence Laboratory
<EMAIL_ADDRESS>
Xiaoshui Huang
Shanghai Artificial Intelligence Laboratory
<EMAIL_ADDRESS>
Dongzhan Zhou
Shanghai Artificial Intelligence Laboratory
<EMAIL_ADDRESS>
Yuqiang Li
Shanghai Artificial Intelligence Laboratory
<EMAIL_ADDRESS>
Wanli Ouyang
Shanghai Artificial Intelligence Laboratory
<EMAIL_ADDRESS>

###### Abstract

This paper introduces the MCT Self-Refine (MCTSr) algorithm, an innovative
integration of Large Language Models (LLMs) with Monte Carlo Tree Search
(MCTS), designed to enhance performance in complex mathematical reasoning
tasks. Addressing the challenges of accuracy and reliability in LLMs,
particularly in strategic and mathematical reasoning, MCTSr leverages
systematic exploration and heuristic self-refine mechanisms to improve
decision-making frameworks within LLMs. The algorithm constructs a Monte Carlo
search tree through iterative processes of Selection, self-refine, self-
evaluation, and Backpropagation, utilizing an improved Upper Confidence Bound
(UCB) formula to optimize the exploration-exploitation balance. Extensive
experiments demonstrate MCTSr’s efficacy in solving Olympiad-level
mathematical problems, significantly improving success rates across multiple
datasets, including GSM8K, GSM Hard, MATH, and Olympiad-level benchmarks,
including Math Odyssey, AIME, and OlympiadBench. The study advances the
application of LLMs in complex reasoning tasks and sets a foundation for
future AI integration, enhancing decision-making accuracy and reliability in
LLM-driven applications. Codes publicly accessible at
github.com/trotsky1997/MathBlackBox.

##  1 Introduction

Figure 1: Agents can learn decision-making and reasoning from the trial-and-
error as humans do.

With the rapid evolution of artificial intelligence, large language models
(LLMs) such as GPT-4 (Achiam et al.,, 2023) and LLaMA (Touvron et al.,, 2023)
have become fundamental in advancing natural language processing (NLP)
capabilities. These models, characterized by their multi-billion parameter
architectures, exhibit remarkable language comprehension and generation
abilities. Their emergent properties, including reasoning and in-context
learning, have opened new avenues for addressing complex NLP tasks beyond
traditional domains, encompassing mathematical problem-solving (Yu et al.,,
2023; Yuan et al.,, 2023), recommendation systems (Lyu et al.,, 2023), and
even molecule generation (Liang et al.,, 2023). However, despite these
advancements, LLMs face notable challenges in areas demanding strategic and
logical reasoning.

One significant hurdle is the accuracy and trustworthiness of the outputs.
Especially in mathematical contexts, where precision is paramount, the
reasoning capabilities of LLM always suffer from prone to producing
hallucinations—outputs (Huang et al.,, 2023) that, while superficially
plausible, but irrelevant or factually incorrect, are finally harmful to
rational processes. Though rewriting techniques like Self-Refine (Madaan et
al.,, 2023) can help relieve, this tendency can still lead to misleading or
wrong outcomes in real-world complex mathematical problems.

To address these challenges, this paper proposes MCT Self-Refine (MCTSr), an
integration of LLMs with a Monte Carlo Tree Search (MCTS) algorithm (Chaslot
et al.,, 2008), focusing on enhancing LLMs’ performance in complex
mathematical reasoning tasks, such as those encountered in mathematical
Olympiads. MCTS, a decision-making tool widely used in AI for scenarios
requiring strategic planning, is typically employed in gaming and complex
problem-solving environments. By combining MCTS’s systematic exploration
capabilities with LLMs’ capabilities of Self-Refine and Self-Evaluation, we
aim to create a more robust framework for tackling intricate reasoning tasks
that current LLMs struggle with.

Several technical challenges exist in adapting MCTS for LLM integration.
Traditional MCTS strategies may not align well with the stochastic and
generative nature of LLM outputs, which often involve an infinite, continuous
space of potential actions. This misalignment necessitates a tailored approach
to expectation calculation and Backpropagation within the MCTS framework to
better suit the unique characteristics of LLMs. Furthermore, we introduce a
dynamic pruning strategy incorporating an improved upper confidence bound
(Srinivas et al.,, 2009) (UCB) formula to optimize the exploration-
exploitation balance essential for effective decision-making in high-stakes
tasks.

Our primary contributions are as follows:

We develop and validate a novel reasoning algorithm by integrating LLMs with
UCT-MCTS. We enhance the algorithm’s key components to accommodate the
integration with LLMs better and demonstrate its effectiveness on Olympic-
level mathematical problems.

We propose a dynamic pruning module that refines decision-making processes
within the MCTS framework, facilitating more efficient and accurate problem-
solving capabilities.

Through extensive experimentation, we provide insights into the synergistic
potential of LLMs and MCTS, showcasing improved performance in complex
reasoning tasks.

This research advances the application of LLMs in sophisticated reasoning
challenges. It sets the stage for future innovations in integrating AI
technologies for enhanced decision-making, reasoning accuracy, and reliability
of LLM-driven applications.

##  2 Preliminary

This section introduces the preliminary and notations used in this work. We
will first detail the mechanism of Monte Carlo Tree Search (MCTS) and,
essential for understanding the novel dynamic Monte Carlo Tree Self-refine

Monte Carlo Tree Search (MCTS) is a decision-making algorithm widely used in
games and complex decision processes, which operates by building a search tree
and simulating outcomes to estimate the value of actions. It involves four key
phases (Browne et al.,, 2012): Selection, based on the UCT strategy to
maximize the potential; expansion, where new nodes are added; simulation, to
foresee possible outcomes; and Backpropagation, updating the node values based
on simulation results. Typically, the MCTS algorithm comprises four distinct
phases:

  * •

Selection: Starting from the root, the algorithm navigates through promising
child nodes based on specific strategies (e.g., UCT), continuing until a leaf
node is reached.

  * •

Expansion: At the leaf node, unless it represents a terminal state of the
game, one or more feasible new child nodes are added to illustrate potential
future moves.

  * •

Simulation or Evaluation: From the newly added node, the algorithm conducts
random simulations—often termed "rollouts"—by selecting moves arbitrarily
until a game’s conclusion is reached, thereby evaluating the node’s potential.

  * •

Backpropagation: Post-simulation, the outcome (win, loss, or draw) is
propagated back to the root, updating the statistical data (e.g., wins,
losses) of each traversed node to inform future decisions.

Repeatedly iterating through these stages, MCTS incrementally constructs a
decision tree, refining strategies for optimal decision-making in scenarios
where direct calculation of the best strategy is infeasible due to the
vastness of the state space.

Upper Confidence Bound applied on Trees Algorithm is crucial for the selection
phase in MCTS, balancing exploration and exploitation by choosing actions that
maximize:

$UCT_{j}=\bar{X}_{j}+C\sqrt{\frac{2\ln N_{C}}{N_{j}}}$ (1)

Where $\bar{X}_{j}$ is the average reward of action $j$, $N_{C}$ is the total
visited times of the father node, and $n_{j}$ is the number of times node $j$
has been visited for simulation, C is a constant to balancing exploitation and
exploration.

MCT Self-Refine algorithm represents an integration of Monte Carlo Tree Search
(MCTS) with large language models, abstracting the iterative refinement
process of mathematical problem solutions into a search tree structure. Nodes
on this tree represent different versions of answers, while edges denote
attempts at improvement. This algorithm’s operational workflow adheres to the
MCTS algorithm’s general pattern. Detailly, We employ self-reflective driven
self-improvement for refining answers; rewards for different answer versions
are sampled using the model’s self-reward capability.

To facilitate understanding of the MCTSr algorithm, the following symbols and
functions are defined:

  * •

$P$: The problem instance being addressed.

  * •

$A$: The set of nodes, each representing a potential answer to $P$.

  * •

$M$: The set of actions available at each node, representing possible self-
refine modifications to an answer.

  * •

$R$: A function that samples self-rewards for nodes based on the quality and
effectiveness of the modifications.

  * •

$R_{a}$: A Set that stores all self-rewards sampling results of node $a$ with
self-rewards function $R$.

  * •

$T$: A function determining the termination of the search process based on
criteria such as reaching a maximum number of iterations or achieving
satisfactory answer quality.

  * •

$Q(a)$: A value function estimating the worth of an answer node $a$, derived
from accumulated rewards $R_{a}$ and backpropagations from children nodes.

  * •

$U(a)$: The Upper Confidence Bound for the $Q$ value of node $a$ to balance
between exploitation and exploration.

  * •

$\text{Father}(a)$: A function returning the parent node of a given node $a$.
If $a$ is a root node, this function returns null or a specific identifier.

  * •

$\text{Children}(a)$: A function returning the set of all child nodes for a
given node $a$, representing all possible states derived from $a$ by executing
actions $m\in M$.

  * •

$N(a)$: The total number of visits to node $a$, used to calculate its UCB
value and assess exploration and exploitation status. Since we will sample a
reward for each visit, this value equals $|R_{a}|$.

##  3 Methodology

In this section, we will first demonstrate the main structure of MCTSr, shown
in Figure 1. Then, we will detail each component The main workflow of MCTSr is
structured as follows:

  * •

Initialization: A root node is established using either a naive model-
generated answer and a dummy response (e.g., ’I don’t know.’) to minimize
model overfitting tendencies.

  * •

Selection: The algorithm employs a value function $Q$ to rank all answers that
were not fully expanded and selects the highest-valued node for further
exploration and refinement using a greedy strategy.

  * •

Self-Refine: The selected answer $a$ undergoes optimization using the Self-
Refine framework (Madaan et al.,, 2023). Initially, the model generates a
feedback $m$, guiding the refining process to produce an enhanced answer
$a^{\prime}$.

  * •

Self-Evaluation: The refined answer is scored to sample a reward value and
compute its $Q$ value. This involves model self-reward feedback and
constraints such as strict scoring standards and suppression of perfect scores
to ensure reliability and fairness in scoring.

  * •

Backpropagation: The value of the refined answer is propagated backward to its
parent node and other related nodes to update the tree’s value information. If
the $Q$ value of any child node changes, the parent node’s $Q$ is updated.

  * •

UCT update: After the $Q$ values of all nodes are updated, we identify a
collection $\mathbf{C}$ of candidate nodes for further expansion or Selection,
then use the $UCT$ update formula to update the $UCT$ values of all nodes for
the next Selection stage.

The algorithm iterates through these stages until a termination condition $T$
is met, including rollout constraints or maximum exploration depth,
continuously refining the quality of answers, and exploring new possibilities.

###  3.1 Self-Refine

In the self-refine process, the model is guided by a multi-turn dialogue
refine prompt to optimize an answer $a$ to problem $P$. Initially, the model
generates a reflective or critical comment $m$ regarding $a$. Subsequently,
guided by $m$, the model modifies $a$ to produce an improved version
$a^{\prime}$. This iterative refinement enhances the quality of the response,
leveraging structured feedback to drive the evolution of the answer.

###  3.2 Self-Evaluation

In the refining process for mathematical problem $P$, the $Q$ value of an
answer $a$ is defined as the expected quality of further refining $a$ into a
superior answer, owing to the Markovian nature of the transition from $a$ to
its rewritten forms. Unlike traditional MCTS where $Q(s,a)$ estimates the
value of action $a$ in state $s$, $Q(a)$ here derives from multiple samplings
of the reward function values attributed to $a$.

The model utilizes a self-reward method to estimate rewards for $a$, where it
is required to provide a reward score ranging from -100 to 100. We find that
without constraints, the model’s reward tendency is overly smooth, leading to
a lack of comparative distinction between answers in practice. To address
this, three constraints are designed:

  * •

Prompt Constraint: The model must adhere to the strictest standards during
reward scoring.

  * •

Full Score Suppression: The model is instructed not to provide full feedback
scores; any reward above 95 is reduced by a constant amount to curb excessive
scores.

  * •

Repeated Sampling: Each visit to a search tree node involves the repeated
sampling of the node’s rewards to enhance the reliability of the Self-
Evaluation. It should be noted that when reward sampling is performed on the
child nodes of a node, we will also perform reward sampling on its parent node
to increase the sample size of reward sampling.

Post sampling, the $Q$ value of $a$ is calculated. To counteract the smoothing
tendency of the self-reward function, a minimum value constraint is added to
the expected reward, further refining the estimation of answer quality,

$Q(a)=\frac{1}{2}\left(\min{R_{a}}+\frac{1}{|R_{a}|}\Sigma^{|R_{a}|}_{i=1}{R_{a}^{i}}\right)$
(2)

where $Q(a)$ is the quality value of answer $a$, $R_{a}$ is the set of reward
samples for $a$, $\min{R_{a}}$ is the minimum reward in $R_{a}$, $|R_{a}|$ is
the number of samples, and $\Sigma^{|R_{a}|}_{i=1}{R_{a}^{i}}$ is the sum of
all rewards in $R_{a}$. This formula calculates $Q(a)$ by averaging the
rewards’ minimum and mean, balancing worst-case and average outcomes.

###  3.3 Backpropagation

After all leaf nodes’ reward value sampling and Q value update are completed,
we will propagate this change to its parent and ancestor nodes. During this
update process, if the $Q$ function value of any element in the child node set
$\text{Children}(a)$ of a node $a$ changes, the $Q$ function value of the node
is updated to

$Q^{\prime}(a)=\frac{1}{2}\left(Q(a)+\max_{i\in\text{Children}(a)}Q(i)\right)$
(3)

Where $Q^{\prime}(a)$ is the updated quality value of answer $a$ that consider
the impact from its children nodes, $Q(a)$ is the naive quality value only
consider its reward samplings, and $\max_{i\in\text{Children}(a)}Q(i)$
represents the highest quality value among the children of $a$. This formula
refines $Q(a)$ by averaging the current value and the best possible outcome
from its subsequent Children nodes.

###  3.4 Update UCT and Selection

After updating the $Q$ values across all nodes in the tree, we proceed to the
selection phase for the next round of choices. This process includes the
following steps:

Candidate Node Selection: Leveraging the Markovian nature of the mathematical
problem refine process, we focus on selecting all leaf nodes and those that
are not fully expanded, disregarding the history of refine paths is feasible.
This path-independent property helps simplify our problem. We no longer need
to start from the root node when selecting nodes but traverse the nodes in the
tree in hierarchical order.

But given that Large Language Models (LLMs), which play as policy in this
task, can generate an infinite number of refine actions $m$ for any answer
state $a$, each node potentially faces an unbounded set of actions for
expansion. Thus, drawing from the concept of Expectation Improvement in
Bayesian optimization, we propose two criteria for determining "full
expansion":

  * •

The node’s children count reaches a predefined limit. And,

  * •

At least one child node’s $Q$ value exceeds the node’s.

We identify a collection $\mathbf{C}$ of candidate nodes based on these
criteria for further expansion or Selection. This strategy helps accurately
define which nodes might yield higher-value answers in subsequent searches,
enhancing overall search efficiency and outcome quality.

UCT Update: Drawing from AlphaGo, we use UCT with the UCB-1 method to balance
the exploration and exploitation of nodes; for node $a$ in the candidate set
$\mathbf{C}$, its $UCT_{a}$ value is,

$UCT_{a}=Q(a)+c\sqrt{\frac{\ln{N(\text{Father}(a))+1}}{N(a)+\epsilon}}$ (4)

where $Q(a)$ is the $Q$ value of answer $a$, $N(\cdot)$ is the total visited
times of given nodes, $c$ is a constant to balancing exploitation and
exploration, $\epsilon$ is a small constant for avoid devided-by-zero.

Sorting and Selection: According to the UCT value of the candidate set
$\mathbf{C}$, we can select an optimal node to explore the refining process
through greedy sampling or importance sampling.

###  3.5 Termination Function

In MCTSr algorithms, search termination function criteria $T$ can derive from
several conditions:

Early Stopping: Termination occurs when improvements in search results
diminish or when consecutive searches yield repetitive outcomes.

Search Constraints: The search terminates once the number of rollouts reaches
a predetermined limit or when one or more nodes in the tree satisfy the
maximum depth constraint.

Advanced Criteria Based on Language Model Logits: The search concludes based
on predefined metrics derived from the language model’s logits.

Once the Termination Function condition $T$ is satisfied, we can gather the
best answers from tree nodes according to $Q$ values or other conditions.

##  4 Evaluation

###  4.1 Experiment Settings

To assess the MCTSr algorithm’s effectiveness in solving mathematical
problems, we employed LLaMA3-8B (Meta AI,, 2024) as the foundational model,
enhanced with MCTSr. Detailed prompt settings are provided in the appendix. We
compared LLaMA3-8 B’s performance across several configurations—Zero-Shot CoT
(Wei et al.,, 2022), Self-Refine, 4-rollouts MCTSr, and 8-rollouts
MCTSr—against the performances of GPT-4 (Achiam et al.,, 2023), Claude 3
(Anthropic,, 2024) and Gemini 1.5-Pro (Reid et al.,, 2024), which are the
latest state-of-the-art closed-source models. These comparisons were conducted
on various datasets, including GSM8K (Cobbe et al.,, 2021), GSM Hard (Gao et
al.,, 2022), MATH (Hendrycks et al.,, 2021), AIME (AIME,, 2024), Math Odyssey
(AGI Odyssey,, 2024), and OlympiadBench(pure-text subset) (He et al.,, 2024).

###  4.2 GSM Benchmarks

We evaluated the above methods on the test sets of GSM8K and GSM-hard, which
involved typical and challenging mathematical problems, respectively. The
results are shown in Table 1.

We can find that results reveal a direct correlation between the number of
MCTSr rollouts and success rates, significantly improving as iterations
increase, especially in the less complex GSM8K. However, the more intricate
GSM-Hard set showcased a performance ceiling even at higher rollouts,
indicating the limits of current strategies against complex problems.

These insights underscore the MCT-Self-refine algorithm’s robustness and
potential boundaries, highlighting the necessity for ongoing enhancements to
tackle more complex challenges effectively. This work demonstrates the
algorithm’s capacity to enhance problem-solving performance and its varying
efficacy across problem complexities, suggesting areas for future refinement
in educational technology and automated reasoning.

Datasets | Zero-Shot | One-turn | 4-rollouts | 8-rollouts | Example
---|---|---|---|---|---
CoT | Self-refine | MCTSr | MCTSr | Nums
GSM8K | 977 | 1147 | 1227 | 1275 | 1319
74.07% | 86.96% | 93.03% | 96.66%
GSM-Hard | 336 | 440 | 526 | 600 | 1319
25.47% | 33.36% | 39.88% | 45.49%

Table 1: Performance of MCTSr on the GSM Dataset

###  4.3 MATH Benchamark

This section presents the outcomes of applying the MCT-Self-refine (MCTSr)
algorithm across various complexity levels on the MATH dataset. The dataset is
stratified into five levels of difficulty, ranging from level 1 (easiest) to
level 5 (most challenging). The algorithm’s performance is evaluated using
four distinct configurations: Zero-Shot CoT, One-turn Self-refine, 4-rollouts
MCTSr, and 8-rollouts MCTSr. Each configuration’s efficacy is measured by the
number of successfully solved problems and the corresponding success rates,
with a total of 5000 examples across all levels.

Level-1 results demonstrate the highest success rates, with the 8-rollouts
MCTSr achieving a remarkable 90.16% success rate, solving 394 out of 437
problems. This level shows a clear progression in success rates as rollouts
increase.

At the most challenging level-5 part, the 8-rollouts MCTSr configuration
yields a 34.06% success rate, solving 451 out of 1324 problems. This
illustrates the increasing difficulty and the algorithm’s strained performance
in highly complex scenarios.

Overall performance across all levels shows a cumulative success rate of
58.24% with the 8-rollouts MCTSr, solving 2912 out of 5000 problems. This rate
demonstrates a substantial enhancement from the Zero-Shot CoT’s initial rate
of 24.36%. The data indicates a consistent trend where the increase in
rollouts correlates with improved success rates, underlining the efficacy of
the MCT-Self-refine algorithm in enhancing problem-solving capabilities across
varying levels of mathematical complexity.

These results validate the MCT-Self-refine algorithm’s potential in academic
and problem-solving contexts and highlight its scalability and adaptability to
different levels of problem complexity within the MATH dataset.

Level | Zero-Shot | One-turn | 4-rollouts | 8-rollouts | Example
---|---|---|---|---|---
CoT | Self-refine | MCTSr | MCTSr | Nums
level-1 | 250 | 314 | 365 | 394 | 437
| 57.21% | 71.85% | 83.52% | 90.16%
level-2 | 363 | 474 | 594 | 692 | 894
40.60% | 53.02% | 66.44% | 77.40%
level-3 | 309 | 454 | 585 | 719 | 1131
27.32% | 40.14% | 51.72% | 63.57%
level-4 | 202 | 368 | 523 | 656 | 1214
16.64% | 30.31% | 43.08% | 54.04%
level-5 | 94 | 177 | 290 | 451 | 1324
7.10% | 13.37% | 21.90% | 34.06%
Overall | 1218 | 1787 | 2357 | 2912 | 5000
24.36% | 35.74% | 47.14% | 58.24%

Table 2: Performance of MCTSr on the MATH Dataset

###  4.4 Olympiad-level Benchmarks

The efficacy of the MCT-Self-refine (MCTSr) algorithm was tested on three
datasets from mathematical Olympiad competitions: AIME, GAIC Math Odyssey, and
OlympiadBench. The GAIC Math Odyssey dataset, released in April 2024, is
notable for its minimal overlap with the pre-training corpus of the LLaMa3-8B
model, providing a robust test of the algorithm’s ability to generalize.

AIME: From Zero-Shot CoT’s 2.36% (22 problems solved) to 8-rollouts MCTSr’s
11.79% (110 problems solved).

GAIC Math Odyssey: Showed substantial improvement, starting at 17.22% (67
problems solved) and reaching up to 49.36% (192 problems solved) with
8-rollouts MCTSr.

OlympiadBench: Improved from 1.25% (16 problems solved) in Zero-Shot CoT to
7.76% (99 problems solved) in 8-rollouts MCTSr.

The results demonstrate a clear trend where increased rollouts correlate with
higher success rates, highlighting the algorithm’s potential to improve
performance through iterative refinement. The GAIC Math Odyssey results mainly
reflect the MCTSr’s generalization capabilities in new environments.

These findings affirm the MCT-Self-refine algorithm’s robustness and its
utility in tackling complex, unseen mathematical problems, suggesting its
applicability in educational technologies aimed at competitive academic
settings like Olympiads.

Datasets |  | Zero-Shot
---
CoT
| One-turn
---
Self-refine
| 4-rollouts
---
MCTSr
| 8-rollouts
---
MCTSr
| Example
---
Nums
AIME | 22 | 41 | 70 | 110 | 933
2.36% | 4.39% | 7.50% | 11.79%
Math Odyssey | 67 | 118 | 156 | 192 | 389
17.22% | 30.33% | 40.10% | 49.36%
OlympiadBench | 16 | 39 | 67 | 99 | 1275
1.25% | 3.06% | 5.25% | 7.76%

Table 3: Performance of MCTSr on Olympiad-level Datasets

###  4.5 Disscussion

We investigated the reported values of the current state-of-the-art closed-
source large model SOTA performance on the above test benchmarks, as shown in
the table 4.

|  | Gemini
---
1.5-Pro
| Claude
---
3 Opus
| GPT-4
---
Turbo
MATH (Reid et al.,, 2024) | 67.7 | 60.1 | 73.4
Math Odyssey (Reid et al.,, 2024) | 45.0 | 40. | 49.1
GSM8K (Papers with Code,, 2024) | 94.4 | 95 | 97.1
Table 4: closed-source LLM performance on mathematical datasets

Comparing the performance of current closed-source large models, MCTSr can
effectively enhance the mathematical reasoning capabilities of small-parameter
open-source models, like LLaMa-3, to a comparable level.

##  5 Related works

Monte Carlo Tree Search (MCTS) has been widely utilized in various fields to
solve complex problems efficiently. Pitanov et al., (2023) explored the
application of MCTS in Multi-agent Pathfinding, demonstrating its superiority
over heuristic search algorithms like A*. Additionally, Yang, (2023)
integrated MCTS with heuristic, unsupervised, and supervised learning methods
to efficiently solve the Train Timetabling Problem (TTP). Furthermore, Li et
al., (2023) introduced a general method for solving various types of SAT
problems using a unified framework incorporating MCTS. Vagadia et al., (2024)
developed PhyPlan, a physics-informed planning framework that combines
physics-informed neural networks with modified MCTS to enable robots to
perform dynamic physical tasks effectively. In conclusion, MCTS has proven to
be a versatile and effective mathematical solution for solving various complex
problems in different domains, including robotics, game solving, and
optimization. Researchers continue to explore and enhance the capabilities of
MCTS by integrating it with other algorithms and frameworks to tackle
increasingly challenging tasks.

Recent research has made notable strides in enhancing mathematical reasoning
in large language models (LLMs). Du et al., (2023) introduced a method where
multiple LLMs discuss and refine answers collectively, significantly boosting
reasoning and factual accuracy. Luo et al., (2023) developed WizardMath, which
leverages Reinforcement Learning from Evol-Instruct Feedback to surpass
existing LLMs in mathematical benchmarks. Meanwhile, Lu et al., (2023) created
MathVista, a visual, mathematical benchmark, with GPT-4V achieving a 49.9%
accuracy, highlighting gaps that persist relative to human performance. Yu et
al., (2023) introduced MetaMath, a fine-tuned model that excels in
mathematical challenges, and Yuan et al., (2023) demonstrated that pre-
training loss and Rejection sampling Fine-Tuning can optimize LLM performance,
particularly in less advanced models. These studies suggest significant
progress yet underline the necessity for ongoing research in LLM mathematical
reasoning.

Recent advancements in large language models (LLMs) have significantly
improved their mathematical reasoning abilities. Yet, they still face complex
problems that require multiple reasoning steps, leading to logical or
numerical errors. To address this limitation, Chen et al., (2024) proposed
incorporating Monte Carlo Tree Search (MCTS) to enhance the mathematical
reasoning capabilities of fine-tuned LLMs without additional fine-tuning steps
. Xu, (2023) utilized MCTS and a lightweight energy function, the models can
rank decision steps and enable immediate reaction and precise reasoning,
leading to improved performance on mathematical reasoning benchmarks. However,
it still lacks a framework that combines the self-refine capabilities and
self-reward evaluation method of LLMs to refine the model’s response
iteratively with the Monte Carlo Tree Search Algorithm.

##  6 Limitations

Although the MCTSr algorithm has demonstrated certain advantages in
mathematical tasks, our research is still in its preliminary stages. As a
general decision-making framework, the potential applications of MCTSr in
various scenarios remain to be explored further, such as in black-box
optimization problems and self-driven alignment for large language models.
Additionally, the components of MCTSr are highly scalable, necessitating
ongoing development to identify and compare a broader range of component
algorithms, thereby enhancing the practical potential and effectiveness of the
MCTSr algorithm.

##  7 Conclusion

This paper demonstrates the effectiveness of the MCT Self-Refine (MCTSr)
algorithm in enhancing the capability of Large Language Models (LLMs) to solve
complex mathematical problems. By integrating Monte Carlo Tree Search (MCTS)
with LLMs, MCTSr addresses critical challenges in accuracy and reliability,
particularly within mathematical reasoning tasks. Experimental results confirm
significant improvements in problem-solving success rates across multiple
datasets, including notable performance in Olympic-level mathematical
challenges.

Moreover, the research advances the application of LLMs in sophisticated
reasoning tasks and lays the groundwork for future integration of AI
technologies to enhance decision-making and reasoning accuracy. Despite
MCMCTSr’semonstrated potential in mathematical problem-solving, its
applicability in broader contexts, such as black-box optimization and self-
driven alignment, remains to be explored. Future work will optimize
algorithmic components and test their performance across various problems and
settings to achieve broader practicality and effectiveness.

## References

  * Achiam et al., (2023) Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., et al. (2023).  Gpt-4 technical report.  arXiv preprint arXiv:2303.08774.
  * AGI Odyssey, (2024) AGI Odyssey (2024).  AGI odyssey.
  * AIME, (2024) AIME (2024).  AIME problem set: 1983-2024.
  * Anthropic, (2024) Anthropic, A. (2024).  The claude 3 model family: Opus, sonnet, haiku.  Claude-3 Model Card.
  * Browne et al., (2012) Browne, C., Powley, E. J., Whitehouse, D., Lucas, S. M. M., Cowling, P. I., Rohlfshagen, P., Tavener, S., Liebana, D. P., Samothrakis, S., and Colton, S. (2012).  A survey of monte carlo tree search methods.  IEEE Transactions on Computational Intelligence and AI in Games, 4:1–43.
  * Chaslot et al., (2008) Chaslot, G., Bakkes, S. C. J., Szita, I., and Spronck, P. (2008).  Monte-carlo tree search: A new framework for game ai.  Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment.
  * Chen et al., (2024) Chen, G., Liao, M., Li, C., and Fan, K. (2024).  Alphamath almost zero: process supervision without process.  arXiv preprint arXiv:2405.03553.
  * Cobbe et al., (2021) Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., et al. (2021).  Training verifiers to solve math word problems.  arXiv preprint arXiv:2110.14168.
  * Du et al., (2023) Du, Y., Li, S., Torralba, A., Tenenbaum, J. B., and Mordatch, I. (2023).  Improving factuality and reasoning in language models through multiagent debate.  arXiv preprint arXiv:2305.14325.
  * Gao et al., (2022) Gao, L., Madaan, A., Zhou, S., Alon, U., Liu, P., Yang, Y., Callan, J., and Neubig, G. (2022).  Pal: Program-aided language models.  arXiv preprint arXiv:2211.10435.
  * He et al., (2024) He, C., Luo, R., Bai, Y., Hu, S., Thai, Z. L., Shen, J., Hu, J., Han, X., Huang, Y., Zhang, Y., Liu, J., Qi, L., Liu, Z., and Sun, M. (2024).  Olympiadbench: A challenging benchmark for promoting agi with olympiad-level bilingual multimodal scientific problems.
  * Hendrycks et al., (2021) Hendrycks, D., Burns, C., Kadavath, S., Arora, A., Basart, S., Tang, E., Song, D., and Steinhardt, J. (2021).  Measuring mathematical problem solving with the MATH dataset.  CoRR, abs/2103.03874.
  * Huang et al., (2023) Huang, L., Yu, W., Ma, W., Zhong, W., Feng, Z., Wang, H., Chen, Q., Peng, W., Feng, X., Qin, B., and Liu, T. (2023).  A survey on hallucination in large language models: Principles, taxonomy, challenges, and open questions.  ArXiv, abs/2311.05232.
  * Li et al., (2023) Li, A., Han, C., Guo, T., Li, H., and Li, B. (2023).  General method for solving four types of sat problems.  arXiv preprint arXiv:2312.16423.
  * Liang et al., (2023) Liang, Y., Zhang, R., Zhang, L., and Xie, P. (2023).  Drugchat: Towards enabling chatgpt-like capabilities on drug molecule graphs.  ArXiv, abs/2309.03907.
  * Lu et al., (2023) Lu, P., Bansal, H., Xia, T., Liu, J., Li, C., Hajishirzi, H., Cheng, H., Chang, K.-W., Galley, M., and Gao, J. (2023).  Mathvista: Evaluating mathematical reasoning of foundation models in visual contexts.  arXiv preprint arXiv:2310.02255.
  * Luo et al., (2023) Luo, H., Sun, Q., Xu, C., Zhao, P., Lou, J., Tao, C., Geng, X., Lin, Q., Chen, S., and Zhang, D. (2023).  Wizardmath: Empowering mathematical reasoning for large language models via reinforced evol-instruct.  arXiv preprint arXiv:2308.09583.
  * Lyu et al., (2023) Lyu, H., Jiang, S., Zeng, H., Xia, Y., and Luo, J. (2023).  Llm-rec: Personalized recommendation via prompting large language models.  ArXiv, abs/2307.15780.
  * Madaan et al., (2023) Madaan, A., Tandon, N., Gupta, P., Hallinan, S., Gao, L., Wiegreffe, S., Alon, U., Dziri, N., Prabhumoye, S., Yang, Y., Welleck, S., Majumder, B. P., Gupta, S., Yazdanbakhsh, A., and Clark, P. (2023).  Self-refine: Iterative refinement with self-feedback.  ArXiv, abs/2303.17651.
  * Meta AI, (2024) Meta AI (2024).  Introducing meta llama 3: The most capable openly available LLM to date.
  * Papers with Code, (2024) Papers with Code (2024).  Papers with code - GSM8k benchmark (arithmetic reasoning).
  * Pitanov et al., (2023) Pitanov, Y., Skrynnik, A., Andreychuk, A., Yakovlev, K., and Panov, A. (2023).  Monte-carlo tree search for multi-agent pathfinding: Preliminary results.  In International Conference on Hybrid Artificial Intelligence Systems, pages 649–660. Springer.
  * Reid et al., (2024) Reid, M., Savinov, N., Teplyashin, D., Lepikhin, D., Lillicrap, T., Alayrac, J.-b., Soricut, R., Lazaridou, A., Firat, O., Schrittwieser, J., et al. (2024).  Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context.  arXiv preprint arXiv:2403.05530.
  * Srinivas et al., (2009) Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. W. (2009).  Information-theoretic regret bounds for gaussian process optimization in the bandit setting.  IEEE Transactions on Information Theory, 58:3250–3265.
  * Touvron et al., (2023) Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., et al. (2023).  Llama: Open and efficient foundation language models.  arXiv preprint arXiv:2302.13971.
  * Vagadia et al., (2024) Vagadia, H., Chopra, M., Barnawal, A., Banerjee, T., Tuli, S., Chakraborty, S., and Paul, R. (2024).  Phyplan: Compositional and adaptive physical task reasoning with physics-informed skill networks for robot manipulators.  arXiv preprint arXiv:2402.15767.
  * Wei et al., (2022) Wei, J., Wang, X., Schuurmans, D., Bosma, M., hsin Chi, E. H., Xia, F., Le, Q., and Zhou, D. (2022).  Chain of thought prompting elicits reasoning in large language models.  ArXiv, abs/2201.11903.
  * Xu, (2023) Xu, H. (2023).  No train still gain. unleash mathematical reasoning of large language models with monte carlo tree search guided by energy function.  arXiv preprint arXiv:2309.03224.
  * Yang, (2023) Yang, F. (2023).  An integrated framework integrating monte carlo tree search and supervised learning for train timetabling problem.  arXiv preprint arXiv:2311.00971.
  * Yu et al., (2023) Yu, L., Jiang, W., Shi, H., Yu, J., Liu, Z., Zhang, Y., Kwok, J. T., Li, Z., Weller, A., and Liu, W. (2023).  Metamath: Bootstrap your own mathematical questions for large language models.  arXiv preprint arXiv:2309.12284.
  * Yuan et al., (2023) Yuan, Z., Yuan, H., Li, C., Dong, G., Tan, C., and Zhou, C. (2023).  Scaling relationship on learning mathematical reasoning with large language models.  arXiv preprint arXiv:2308.01825.

##  Appendix A Prompts in Experiment

###  A.1 Self-Refine

Get Feedback: color=purple!20, inline, author=USERcolor=purple!20, inline,
author=USERtodo: color=purple!20, inline, author=USERSince we have a weak
Answer, could you provide me with a relection or feedback to correct this
answer better? Analyze this Answer Strictly and Critic, point out every flaw
for ervery possible imperfect to minus every possible score! Let’s think step
by step.

Get Refined Answer: color=purple!20, inline, author=USERcolor=purple!20,
inline, author=USERtodo: color=purple!20, inline, author=USER Please refine
the your answer according to your Reflection or Feedback. The response should
begin with [reasoning process]…[Verification]… and end with end with ”[Final
Answer] The answer is [answer formula]” Let’s think step by step.

###  A.2 Self-Reward

color=purple!20, inline, author=USERcolor=purple!20, inline, author=USERtodo:
color=purple!20, inline, author=USERQuestion: question Answer: ans Analyze
this Answer Strictly and Critic, and point out every flaw for every possible
imperfect to minus every possible score! You need to be very harsh and mean in
calculating grades, and never give full marks to ensure that the marks are
authoritative. Output a score between [-100,+100], ig. from -100 to +100.
Response format: [Analyst]…[Score]…

###  A.3 Dummy Answers

color=purple!20, inline, author=USERcolor=purple!20, inline, author=USERtodo:
color=purple!20, inline, author=USER[”I Don’t Know”,”I can’t understand this
question.”,”I can’t help with this question.”,”I don’t know how to solve this
question.”,”I don’t know the answer to this question.”,”I don’t know the
answer to this question, sorry.”]