A wide class of machine learning algorithms can be reduced to variableelimination on factor graphs. While factor graphs provide a unifying notationfor these algorithms, they do not provide a compact way to express repeatedstructure when compared to plate diagrams for directed graphical models. Toexploit efficient tensor algebra in graphs with plates of variables, wegeneralize undirected factor graphs to plated factor graphs and variableelimination to a tensor variable elimination algorithm that operates directlyon plated factor graphs. Moreover, we generalize complexity bounds based ontreewidth and characterize the class of plated factor graphs for whichinference is tractable. As an application, we integrate tensor variableelimination into the Pyro probabilistic programming language to enable exactinference in discrete latent variable models with repeated structure. Wevalidate our methods with experiments on both directed and undirected graphicalmodels, including applications to polyphonic music modeling, animal movementmodeling, and latent sentiment analysis.