This paper introduces a cutting-plane method for training structural support vector machines (SVMs) that achieves linear time complexity in the number of training examples. The method is applicable to both margin-rescaling and slack-rescaling formulations of structural SVMs. The key idea is to reformulate the training problem using a "1-slack" approach, which reduces the number of constraints from O(n|Y|) to a single constraint per training example. This allows for efficient computation using a cutting-plane algorithm that iteratively adds violated constraints to a working set and solves a quadratic program (QP) over the current set of constraints. The algorithm's time complexity is linear in the number of training examples and the desired precision, making it significantly faster than conventional decomposition methods and cutting-plane methods on large datasets. The method is shown to be effective for various structured prediction tasks, including binary classification, multi-class classification, HMM sequence tagging, and CFG parsing. The algorithm's efficiency is demonstrated through extensive empirical evaluations, showing that it is several orders of magnitude faster than traditional methods on large-scale problems. The paper also provides theoretical analysis of the algorithm's correctness, convergence rate, and scalability for structured prediction.This paper introduces a cutting-plane method for training structural support vector machines (SVMs) that achieves linear time complexity in the number of training examples. The method is applicable to both margin-rescaling and slack-rescaling formulations of structural SVMs. The key idea is to reformulate the training problem using a "1-slack" approach, which reduces the number of constraints from O(n|Y|) to a single constraint per training example. This allows for efficient computation using a cutting-plane algorithm that iteratively adds violated constraints to a working set and solves a quadratic program (QP) over the current set of constraints. The algorithm's time complexity is linear in the number of training examples and the desired precision, making it significantly faster than conventional decomposition methods and cutting-plane methods on large datasets. The method is shown to be effective for various structured prediction tasks, including binary classification, multi-class classification, HMM sequence tagging, and CFG parsing. The algorithm's efficiency is demonstrated through extensive empirical evaluations, showing that it is several orders of magnitude faster than traditional methods on large-scale problems. The paper also provides theoretical analysis of the algorithm's correctness, convergence rate, and scalability for structured prediction.