Reconfigurable intelligent surface (RIS) is an emerging technology allowing to control the propagation environment in wireless communications. Recently, beyond diagonal RIS (BD-RIS) has been proposed to reach higher performance than conventional RIS, at the expense of higher circuit complexity. Multiple BD-RIS architectures have been developed with the goal of reaching a favorable trade-off between performance and circuit complexity. However, the fundamental limits of this trade-off are still unexplored. In this paper, we fill this gap by deriving the expression of the Pareto frontier for the performance-complexity trade-off in BD-RIS. Additionally, we characterize the optimal BD-RIS architectures reaching this Pareto frontier.