Called-arity analysis can be quite slow

While looking into #18787, I noticed that called-arity analysis sometimes takes significantly longer than the surrounding simplifier runs: For instance, when compiling Cubix.Transformations.Hoist.Custom (in the library component) we have:

...
!!! Simplifier [Cubix.Transformations.Hoist.Custom]: finished in 5165.03 milliseconds, allocated 3856.175 megabytes                  
Simplifier [Cubix.Transformations.Hoist.Custom]: alloc=4043492976 time=5165.031
*** Simplifier [Cubix.Transformations.Hoist.Custom]:
Result size of Simplifier iteration=1
  = {terms: 125,012,
     types: 1,879,379,
     coercions: 653,833,
     joins: 11/64}
Result size of Simplifier iteration=2
  = {terms: 124,937,
     types: 1,874,464,
     coercions: 653,810,
     joins: 12/60}
Result size of Simplifier
  = {terms: 124,937,
     types: 1,874,464,
     coercions: 653,810,
     joins: 12/60}
!!! Simplifier [Cubix.Transformations.Hoist.Custom]: finished in 8663.68 milliseconds, allocated 2890.067 megabytes
Simplifier [Cubix.Transformations.Hoist.Custom]: alloc=3030454976 time=8663.675
*** Float inwards [Cubix.Transformations.Hoist.Custom]:
Result size of Float inwards
  = {terms: 124,937,
     types: 1,874,464,
     coercions: 653,810,
     joins: 12/60}
!!! Float inwards [Cubix.Transformations.Hoist.Custom]: finished in 121.60 milliseconds, allocated 94.945 megabytes
Float inwards [Cubix.Transformations.Hoist.Custom]: alloc=99557424 time=121.605
*** Called arity analysis [Cubix.Transformations.Hoist.Custom]:
Result size of Called arity analysis
  = {terms: 124,937,
     types: 1,874,464,
     coercions: 653,810,
     joins: 12/60}
!!! Called arity analysis [Cubix.Transformations.Hoist.Custom]: finished in 111594.82 milliseconds, allocated 77722.139 megabytes
Called arity analysis [Cubix.Transformations.Hoist.Custom]: alloc=81497569472 time=111594.817
*** Simplifier [Cubix.Transformations.Hoist.Custom]:
Result size of Simplifier iteration=1
  = {terms: 124,925,
     types: 1,872,004,
     coercions: 653,805,                                                                                                             
     joins: 13/60}                                                                                                                   
Result size of Simplifier                                                                                                            
  = {terms: 124,925,                                                                                                                 
     types: 1,872,004,                                                                                                               
     coercions: 653,805,                                                                                                             
     joins: 13/60}                                                                                                                   
!!! Simplifier [Cubix.Transformations.Hoist.Custom]: finished in 2271.06 milliseconds, allocated 1926.801 megabytes                  
...

That is called arity analysis takes over two minutes where the simplifier takes less than 10 seconds on what is likely a very similar Core program.

It sounds to me like there may be something quadratic lurking here.