You have to do the following steps:

1. Run defrag in the guest (Windows only)

Nullify free space: With a Linux Guest run this:

sudo dd if=/dev/zero of=/bigemptyfile bs=4096k
sudo rm -rf /bigemptyfile

Or:

telinit 1
mount -o remount,ro /dev/sda1
zerofree -v /dev/sda1

Or

sudo apt-get install secure-delete
sfill -f -z -l -l -I -v /

With a Windows Guest, download SDelete from Sysinternals and run this:

sdelete –z

2. Shutdown the guest VM

3. Now run VBoxManage’s modifyhd command with the –compact option:

With a Linux Host run this:

vboxmanage modifyhd /path/to/thedisk.vdi --compact

With a Windows Host run this:

VBoxManage.exe modifyhd c:\path\to\thedisk.vdi --compact

With a Mac Host run this:

VBoxManage modifyhd /path/to/thedisk.vdi --compact

This reduces the vdi size.

Src:

http://superuser.com/questions/529149/how-to-compact-virtualboxs-vdi-file-size

http://marianposaceanu.com/articles/how-to-reduce-the-size-of-your-vms