Performing usage-based software library decomposition is disclosed herein. In some examples, a processor device generates a first library graph representing a first software library including multiple functions. The first library graph comprises a plurality of nodes that each correspond to a function of the first software library. The processor device identifies a function within the first software library (“invoked function”) that is directly invoked by an application that depends on the first software library, then generates a call graph including nodes within the first library graph (“dependency nodes”) corresponding to either the invoked function or another function invoked by the invoked function during application execution. Using the call graph, the processor device generates a second software library including only functions of the first software library corresponding to dependency nodes of the call graph.