When do STALE arp entries become FAILED when never used?
The neighbor cache in the Linux kernel isn't as simple.
There are subtle differences between an neighbor cache entry actually falling out of the cache entirely or just being marked as stale/invalid. At some point between base_reachable_time/2 and 3* base_reachable_time/2, the entry will still be in the cache, but it will be marked with a state of STALE. You should be able to view the state with "ip -s neighbor show".
When in the STALE state like show above, if I ping 10.64.42.121, it will send the packet to b8:20:00:00:00:00 right away. A second or so later it will usually send an ARP request for who has 10.64.42.121 in order to update it's cache back to a REACHABLE state. BUT, to make matters more confusing, the kernel will sometimes change timeout values based on positive feedback from higher level protocols. What this means is that if I ping 10.64.42.121 and it replies, then the kernel might not bother sending an ARP request because it assumes that the pong meant that it's ARP cache entry is valid. If the entry is in the STALE state, it will also be updated by unsolicited ARP replies that it happens to see.
Now, for the majority of cases, the entry being in the STALE state is all you need to worry about. Why do you need the entry to be removed from the cache entirely? The kernel goes to a lot of effort to not thrash memory by just changing the state of cache entries instead of actually removing and adding them to the cache all the time.
If you really really insist that it not only will be marked as STALE, but will actually be removed from the hashmap used by the neighbor cache, you have to beware of a few things. First, if the entry hasn't been used and is stale for gc_stale_time seconds, it should be eligible to be removed. If gc_stale_time passed and marked the entry as okay to be removed, it will be removed when the garbage collector runs (usually after gc_interval seconds).
Now the problem is that the neighbor entry will not be deleted if it's being referenced. The main thing that you're going to have problems with is the reference from the ipv4 routing table. There's a lot of complicated garbage collection stuff, but the important thing to note is that the garbage collector for the route cache only expires entries every 5 minutes (/proc/sys/net/ipv4/route/gc_timeout seconds) on a lot of kernels. This means the neighbor entry will have to be marked as stale (maybe 30 seconds, depending on base_reachable_time), then 5 minutes will have to go by before the route cache stops referencing the entry (if you're lucky), followed by some combination of gc_stale_time and gc_interval passing before it actually gets cleaned up (so, overall, somewhere between 5-10 minutes will pass).
Summary: you can try decreasing /proc/sys/net/ipv4/route/gc_timeout to a shorter value, but there are a lot of variables and it's difficult to control them all. There's a lot of effort put in to making things perform well by not removing entries in the cache too early (but instead just marking them as STALE or even FAILED).
gc_stale_time is the right parameter to tweak to evict STALE entries from the ARP table. But there is more:
ARP garbage collection is run in the periodic neigh_periodic_work function. The interval can be tweaked via /proc/sys variable gc_interval.
It will then check that there is at least gc_thresh1 entries in the ARP table. This will avoid consuming extra CPU cycles if the table is too small to see any real benefit in terms of memory.
In your case, I suspect gc_thresh1 is the variable you'll want to tweak. lowering it will force the GC to run more frequently. This may have a negative impact on the performance depending on the run interval though.
Note: gc_thresh3 is a hard threshold. The table will never keep more entries than this value. Tweak it with care.