Term extraction is a crucial workload in \texttt{egg} for determining the desired terms to be extracted. Some prior works have formulated term extraction as integer linear programming (ILP) problems in order to cope with common sub-expressions for optimality that could not be handled by greedy algorithms. Although ILP-based extraction algorithms ensure optimality, these formulations offload a topological sorting problem to the ILP solver to avoid extracting cyclic terms, which does not scale well with the complexity of cycles in the e-graph. Instead of enforcing topological orders with constraints, we propose to explicitly identify the cycles and encode them to \textit{Acyclic constraints}. This approach enables us to formulate term extraction problems in terms of Weighted Partial MAXSAT problems and improve the solving speed of the current ILP formulation. Our evaluation of term extraction for equality saturation on real-world Deep Learning (DL) workloads shows that using the improved formulation yields up to $\sim$3x speed-up on the total extraction time compared with using the state-of-the-art ILP encoding.