Last sample takes long

[sss441803]

Hi, the HyperOptimizer spends all the time on the final sample. These final samples are usually not that good either. This is the case for whatever max_time I choose. The code is

opt = cotengra.HyperOptimizer(max_time=300, parallel=False, minimize='size')
tree = cotengra.einsum_tree(expression, *shapes, optimize=opt)
trials = opt.to_df()
print(trials)

The output is

    run        time   method        size      flops      write  random_strength      score
1     1    2.820905   greedy   94.000000  30.091469  29.883870         0.001638  30.236778
5     5    2.685730   greedy   98.000000  31.516169  31.307798         0.009983  31.196973
6     6    3.739313   greedy  158.944363  48.876881  48.664446         0.247844  44.832937
10   10    4.482864   greedy  177.000000  54.368049  54.197964         0.074571  48.600749
0     0    9.361168  kahypar  116.000000  36.182904  35.907268         0.936363  35.400977
2     2    0.834924  kahypar   74.000000  31.006096  22.303347         5.342249  25.275650
3     3    8.497548  kahypar  125.000000  39.176925  38.740089         0.039599  37.441762
4     4    9.098444  kahypar  127.000000  40.446661  39.092039         0.013544  37.890447
7     7    1.225425  kahypar   64.000000  25.082400  19.266198         0.024546  22.666470
8     8   15.659235  kahypar  130.000000  40.607423  40.312252         0.018321  38.559404
9     9   10.691554  kahypar  128.000000  39.623429  39.281826         1.686497  38.113059
11   11    0.756743  kahypar   63.000000  25.083760  18.975068         4.941972  22.400681
12   12  363.831671  kahypar   65.000000  22.798676  19.813977         9.801763  22.929448

[jcmgray]

Yes I have noticed this occasionally but not looked deeply into it, I presume its do with some bad combination of hyper-parameters supplied to the kahypar driver that makes it slow to partition but I'm not sure. If you can it would be very helpful to:

1. identify the hyper-parameters supplied for the slow run (you can seen these with opt.param_choices)
2. profile[1] a single run with those exact settings with the same tensor network (I think you should be able to call cotengra.pathfinders.path_kahypar.kahypar_to_tree.trial_fn(...) directly with the parameters)

As a side note, yes the max_time is only checked after each trial completes (so after trial 11 all is still fine, then its not checked again til after trial 12), that could maybe be changed but only in the parallel setting.

[1] pyinstrument and py-spy are both useful profilers

[sss441803]

Thank you for the suggestion! I will try to update if I find something useful.

[sss441803]

I think I found the problem. The kahypar optimizer seems to be performing subtree_reconfigure no matter what reconf_opts is supplied. A new tree is created using PartitionTreeBuilder and build_divide uses optimize=sub_optimize which is "auto", which give {'subtree_size': 4, 'maxiter': 100} by default for reconf_opts.

[sss441803]

I created a fork cotengra_lite and this is fixed in the main branch here. Let me know if you think it should be done any differently.

[jcmgray]

I would be a bit surprised if this was the source of the slow-down, since subtree reconfiguration with tree size 4 is very quick.

If I recall some investigations I did, the issue was particularly bad when the super_optimize was set to auto-hq and ~16 highly connected (almost all-to-all) partitions were attempted to be optimally contracted.

The newer auto-hq routines (especially if using faster cotengrust versions) should avoid this issue mostly as the switch-over between optimal->random-greedy happens based on both tensor count and index count.

However I'm sure there are still edge cases where a single optimizer run is slower for some reason. Have you tried with cotengrust installed yet?

[sss441803]

I am using circuit_n53_m20_s0_e0_pABCDCDAB.qsim and I have now been using cotengrust. I think there is definitely an improvement from when the discussion first started, but when I remove reconfiguration, it further improves. In 100 seconds using a single thread, I improved from 19 samples to 55 samples, and the found size improved from 55 to 53.

I also think performing reconfiguration is unexpected behavior independent of potential performance impact. We expect when we put no reconf_opts argument or reconf_opts=None and not using subtree_reconfigure, reconfiguration shouldn't happen.

[jcmgray]

Yes it does seem to have a unintended effect on the average trial runtime here - the auto preset invokes its own HyperOptimizer which has some mild overhead even without reconfing. Moreover, since it uses the max_time="rate:1e9" logic, and the contraction is very expensive, it assumes that spending a lot of time is worth it, even in the small sub-contractions.

My suggestion would be just to change sub_optimize="greedy" however, here is what I get for the three approaches:

• top: sub_optimize="greedy"
• middle: auto with no reconf
• bottom: auto (current)

So its even faster, and probably doesn't change the final quality reachable much, especially if just providing initial guesses to reconfing or simulated annealing.

In a cheaper contraction there is no real difference however (because of the 'rate' logic). And I don't think this will affect the long tail of super slow trials, if they still exist, but could be wrong!

[CSNWEB]

In my experience I often got slow runs with a high parts hyperparameter and high imbalance, so usually trees where the optimal solution is a very "slim" / unbalanced tree, which is the case for the sycamore circuit you mentioned. The hyperoptimizer will converge to those settings on such problems so the later runs can be slower. Might be related to this line of code as well, that is executed when all remaining nodes are in a single partition. I am not entirely sure though.

I found a way that eliminates the need to have many parts or a high imbalance to find good unbalanced contraction trees, you can find my code here: https://github.com/ti2-group/hybrid_contraction_tree_optimizer. It comes with a cotengra hyperoptimizer class so it can be used with cotengra right away, you just need to import this file and use the method hhg. The algorithm is part of a paper that got accepted and will be published soon. Happy to talk about directly integrating it into cotengra. I can also sent you a preprint if you like. Using the new method on the m=20 Sycamore circuit will yield very good results (up to 2 times better than with the current cotengra kahypar algorithm after 1h) after only a few minutes.

[jcmgray]

I will probably change the default for subgraph contraction to 'greedy' as mentioned above, but haven't yet...

And nice work! I would happily take a look at any paper. It looks (?) like you are not using any subtree reconfiguration in the cotengra comparison. While this reasonably represents the performance of original paper, I'd just point out that turning this on is quite important for assessing current cotengra performance these days, and to an extent makes the choice of initial tree less important.

[CSNWEB]

Thanks! Yes I did not consider that in the paper, because I didn’t want to open yet another dimension to the experiments, since they already were quite extensive. Instead the paper solely focuses on the key differences in the kahypar method. I actually did compare the subtree reconfiguration on some networks manually, and you are right, it tends to improve less optimal trees more, so it definitely shrinks the difference and gives cotengra a better optimization times as well. I still have to make some minor revisions, so I don’t want to upload it here yet, I will sent you an email with the current version later.

[jcmgray]

Yes totally understand - it looks like a cool development and that you have been thorough comparison wise! My albeit very minor concern is sometimes other papers benchmarking against 'cotengra' show it in a slightly unfair light by not tweaking anything, (however it's also understandable for various reasons).

Would be nice to incorporate your new approach into cotengra as e.g. a new driver eventually.

[CSNWEB]

Well yes I came across one paper, that only gave 10s of runtime with weird settings and then claimed it was better. We actually spent several weeks to get it working only to see that while it can find paths rather quickly, they are not really good and cotengra easily beats by giving just a bit more time.

If you want to integrate it as a new driver, you could copy over the code right away, may be with some more cleanup on my side. The only problem might be that it currently depends on cotengrust and its own parallelization for the greedy part. Building the contraction tree and calculating the costs is also optimized, since that needs to be done quite often. The normal ctg greedy method could probably benefit from that as well. I don’t remember exactly but I think the Speed up was at least a factor of 2 on larger graphs in terms of greedy iterations per second.