Title: Algorithmic Thinking Theory for Foundation Models
Abstract: The last few months have witnessed tremendous advances on Large Language Model (LLM) reasoning capabilities with Gemini and GPT winning a gold medal at the International Mathematical Olympiad (IMO) [1] and International Collegiate Programming Contest (ICPC) [2], and more recently to prove new theoretical computer science results [3]. Several papers have shown that inference scaling techniques significantly improve the reasoning performances of the LLM, in particular for the IMO [4]. We will discuss these results and how one can frame the problem as an optimization problem, relate it to empirical results shown in [4], and derive optimal (algorithmic) thinking strategies. We will also discuss avenues for refining the model and improving inference scaling methods.