We develop a framework for a sequential multi-class classification under budget constraints. For each instance, a sensor is first chosen and then based on the acquired measurements one decides (rejects) to seek more measurements from a new modality or to terminate by classifying based on the available information. Different sensors have varying costs that account for delay, throughput or monetary value. Consequently, we seek to maximize performance of the system subject to a budget. We formulate a multi-stage empirical risk objective and learn sequential decision functions from training data. We show that reject decision at each stage can be posed as supervised binary classification. We analyze the complexity of our approach and compare it to alternative strategies on several datasets.