TOAST: Fast and scalable auto-partitioning based on principled static analysis

Sami Alabed, Dominik Grewe, Norman A. Rink, Masha Samsikova, Timur Sitdikov, Agnieszka Swietlik, Dimitrios Vytiniotis, Daniel Belov · 2025

Read TOAST: Fast and scalable auto-partitioning based on principled static analysis by Sami Alabed, Dominik Grewe, Norman A. Rink, Masha Samsikova, Timur Sitdikov, Agnieszka Swietlik, Dimitrios Vytiniotis, Daniel Belov (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-15010.txt.

Introduction

Alabed and a large team built a fast tool in twenty twenty-five to split large smart models across many chips. Split calls are tied in knots, and past tools can run out of room or take too long to search. Some past tools cut the search and then give splits that break chip room caps.

Their tool, TOAST, pairs a code read with a tree search that tries splits by chance and score. The read finds which parts must share the same split and where clashes need a call. It beat top trade tools on many chip types and model forms. New best splits came up in the search.

Catalog record

CREATORSami Alabed, Dominik Grewe, Norman A. Rink, Masha Samsikova, Timur Sitdikov, Agnieszka Swietlik, Dimitrios Vytiniotis, Daniel Belov
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-15010

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

TOAST: Fast and scalable auto-partitioning based on principled static analysis Sami Alabed, Dominik Grewe, Norman A. Rink, Masha Samsikova, Timur Sitdikov, Agnieszka Swietlik, Dimitrios Vytiniotis, Daniel Belov Abstract . Partitioning large machine learning models across distributed accelerator systems is a complex process, requiring a series of interdependent decisions that are further complicated by internal sharding ambiguities. Consequently, existing auto-partitioners often suffer from out-of-memory errors or are prohibitively slow when exploring the exponentially large space of possible partitionings. To mitigate this, they artificially restrict the search space, but this approach frequently yields infeasible solutions that violate device memory constraints or lead to sub-optimal performance. We propose a system that combines a novel static compiler analysis with a Monte Carlo Tree Search. Our analysis constructs an efficient decision space by identifying (i) tensor dimensions requiring identical sharding, and (ii) partitioning “conflicts” that require resolution. Our system significantly outperforms state-of-the-art industrial methods across diverse hardware platforms and model architectures, discovering previously unknown, superior solutions, and the process is fully automated even for complex and large models. 1. Introduction The increasing size of machine learning (ML) models necessitates training on distributed systems of accelerator devices (e.g., GPUs, TPUs ( Jouppi et al. 2017 ; Jouppi et al. 2021 ; Developers 2023 ) ). This distributed approach is required because the memory footprints of model parameters and input data routinely exceed the capacity of a single device. Consequently, ML engineers face the significant challenge of adapting their model code for execution on these distributed systems. Manually converting code that defines the mathematics of a model to semantically equivalent code that executes on a distributed system is time-consuming, highly error prone and simply does not scale with model size and complexity. To assist with this challenge, a number of partitioning tools ( Lepikhin et al. 2020 ; Xu et al. 2021 ; Shazeer et al. 2018 ; Alabed et al. 2024 ) have emerged. These tools typically take in ML code in a domain-specific language (e.g. TensorFlow ( Abadi et al. 2016 ) , JAX ( Bradbury et al. 2018 ) , PyTorch ( Paszke et al. 2019 ) ) and, usually at the level of an intermediate representation (IR), rewrite code for local device execution, inserting cross-device communication. This local code operates on partitioned tensors, specifically the shards of inputs and model parameters residing on each device. While these tools automate the mechanics of partitioning a model, users are still responsible for determining the optimal sharding strategy. This requires deciding which tensors to partition based on the model architecture, tensor dimensions, and device topology. Developing optimal partitioning strategies requires significant engineering effort ( Shoeybi et al. 2019 ; Rajbhandari et al. 2019 ; Zhao et al. 2023 ; He et al. 2022 ; Korthikanti et al. 2023 ; Pope et al. 2023 ) . Consequently, many new model architectures lack well-established partitioning strategies. Automatic partitioning tools ( Schaarschmidt et al. 2021 ; Zheng et al. 2022 ) have emerged to discover partitioning strategies for ML models. These tools operate by exploring the search space of possible model partitionings, guided by a performance model that estimates the runtime of each configuration. This search space is exponential in the number of model operations as it comprises all possible sharding combinations for every tensor. Even for models represented in a high-level intermediate representation (IR) like StableHLO ( OpenXLA 2023b ) , this involves tens of thousands of operations, making exhaustive exploration intractable. For instance, Alpa ( Zheng et al. 2022 ) considers every tensor as a candidate for sharding, creating a large search space, which leads to slow compilation times and yields sub-optimal solutions. AutoMap ( Schaarschmidt et al. 2021 ; Alabed et al. 2022 ) addresses this challenge by combining explicit sharding decisions, exposed in the search space, with implicit compiler-driven propagation of those decisions to the rest of the model. However, this approach relies on the user to manually specify key locations in the model where resharding might be beneficial (e.g., for collective communication in transformer sequence parallelism ( Korthikanti et al. 2023 ) ). Therefore, auto-partitioners must aggressively prune the search space without discarding good solutions. In this paper, we address the challenge of automatically expanding the search space to include interesting sharding strategies for intermediate tensors, without making this space intractably large. Our contributions are as follows: • A novel static analysis that operates ahead of the partitioning search to identify tensor dimensions that must be sharded identically. • A method for identifying and leveraging sharding conflicts —situations where an operation’s sharding is ambiguous based on its operands. We demonstrate that these conflicts precisely define the search space for beneficial internal resharding strategies ( Section 3.3 ). • T he o ther a uto- s harding t ool (TOAST). An automatic partitioning tool that integrates our analysis with a Monte-Carlo Tree Search (MCTS) agent ( Browne et al. 2012 ) . The analysis guides the agent by (1) augmenting the search space with conflict resolution actions and (2) pruning the space by identifying dimensions that must be sharded together. This design enables the efficient discovery of complex resharding strategies ( Section 4 ). • A comprehensive evaluation ( Section 5 ) demonstrating that TOAST consistently outperforms state-of-the-art automated and expert partitioning strategies across various ML models and hardware platforms. 2. Background 2.1. Partitioning of ML models When scaling ML models, it is a common abstraction to organize available accelerator devices (e.g., GPUs, TPUs) into a logical mesh . This mesh is an n -dimensional lattice spanned by n device axes ( Lepikhin et al. 2020 ; Xu et al. 2021 ; Shazeer et al. 2018 ; Alabed et al. 2024 ) . In this section, we assume that devices are organized in a 2-dim. mesh, spanned by axes b and m . If there are b devices along axis b and m devices along m , then the whole mesh consists of b\cdot m devices. Partitioning a ML model is the process of preparing it for execution on a mesh of devices. It involves distributing the model’s tensors across the devices as smaller chunks, known as shards . A shard is created by slicing a tensor along one of its dimensions and assigning it to devices along a corresponding axis of the device mesh, as illustrated in Figure 1 . Figure 1 . Shards of a 3-dim. tensor on a 2-dim. mesh (axes b and m ). Blocks correspond to different devices, colors correspond to different shards (i.e. different data). Left: sharding along axis b . Right: sharding along axes b and m . ⬇ def mlp ( x : [ 256 , 32], w1 : [32, 64 ], w2 : [ 64 , 16]) { y : [ 256 , 64 ] = matmul ( x , w1 ) z : [ 256 , 64 ] = ReLU ( y ) w : [ 256 , 16] = matmul ( z , w2 ) return w } (a) Simple ML model: two linear layers. ⬇ def mlp ( x : [256{ b }, 32], w1 : [32, 64 ], w2 : [ 64 , 16]) { y : [256{ b }, 64 ]

Read the complete text