  We introduce the Fusion algorithm for local refinement type inference,
yielding a new SMT-based method for verifying programs with polymorphic data
types and higher-order functions. Fusion is concise as the programmer need only
write signatures for (externally exported) top-level functions and places with
cyclic (recursive) dependencies, after which Fusion can predictably synthesize
the most precise refinement types for all intermediate terms (expressible in
the decidable refinement logic), thereby checking the program without false
alarms. We have implemented Fusion and evaluated it on the benchmarks from the
LiquidHaskell suite totalling about 12KLOC. Fusion checks an existing safety
benchmark suite using about half as many templates as previously required and
nearly 2x faster. In a new set of theorem proving benchmarks Fusion is both 10
- 50x faster and, by synthesizing the most precise types, avoids false alarms
to make verification possible.
