deleting rows with foreign keys

Here's my table:

                                         Table "public.tokens"
   Column   |            Type             |                          
Modifiers
-----------+----------------------------- 
+------------------------------------------------------------
token_idx | bigint                      | not null default nextval 
('tokens_token_idx_seq'::regclass)
token     | character varying(140)      | not null
last_seen | timestamp without time zone | default now()
Indexes:
     "tokens_pkey" PRIMARY KEY, btree (token_idx)
     "tokens_token_key" UNIQUE, btree (token)

I have ~250K rows in this table.
the token_idx is referenced in two other tables, both of whom have a
foreign key constraint to ON DELETE CASCADE.
Of the other two tables, one has ~1M rows and the other ~350K rows.
So they are both one to many relationships with many of the token
table rows appearing in the other two.

Problem:
Deleting one row can take 2 seconds.

Is there something I can do to improve the speed. Locking the tables
is an option as this is a maintenance procedure and not regular
business. But I don't know that this will be useful or practical.