This paper deals with the analysis of small overflow probabilities in single-server queues with batch arrivals. First, for the class of GI X /G/1 queues we give analytical expressions for the decay rate (in the buffer size) of these probabilities. In case of Poisson arrivals, effective bandwidth results are deduced. Furthermore, we propose a change of measure which enables the execution of importance sampling in an asymptotically optimal way. Simulation results for a specific application show large speed-ups.