Timing speculation is a 'better-than-worst-case' design methodology that tunes a digital circuit to its common-case delay. The average throughput of a speculation-based circuit can be estimated using the probability with which input patterns result in timing errors. In this paper, we present a scalable approach to compute the exact probabilities of the occurrence of timing errors at the gate level. We use Timed Characteristic Functions (TCFs) to compute the exact values of the probabilities. In order to improve the scalability, we decompose large circuits into smaller sub-circuits and restrict the TCF computation to these sub-circuits. Instead of substituting the expression for TCF of one sub-circuit into another, we propagate only the computed error probabilities. We demonstrate our technique on gate level combinational circuits from MCNC benchmarks.