As a TODO?

What do you mean here? I'm guessing this should be "level", but I'm not sure what you mean by "favor(ing) constant levels"

since you added a parameter, you also need to update this comment

That's the wrong bound to assert; you should instead compare against levelToDependentIdx[t].size() or maxLvlRank.

For correctness you should also assert(i < numLoops && t < numTensors).

If you rebase over D146684 to get the assertion helpers, then the full assertion would be assert(isValidLevel(t, lvl) && isValidLoopId(i) && !loopToDependencies[i][t].has_value()). The nice thing about those assertion helpers is that it gives the correct bound for the level (rather than falling back to maxLvlRank), and also guards against the case where i == kInvalidId.

Isn't it redundant to store the level-type in loopToDependencies, since it's already stored in lvlTypes? That is, afaict the following code snippet should always return successfully (assuming i and t are valid):

if (const auto dep = loopToDependencies[i][t]) {
  const Level depLvl = (*dep).first;
  const auto depOptLoop = lvlToLoop[t][depLvl];
  assert(depOptLoop);
  const LoopId depLoop = *depOptLoop;
  assert(lvlTypes[t][depLoop] == (*dep).second);
}

Assuming that's correct, then you shouldn't store the level-type in loopToDependencies because it's redundant information. Or if you absolutely must store the redundant copy for some reason, then you need to verify that the level-type agrees with the one in lvlTypes (or if the one in lvlTypes is undefined, then you need to store the dlt parameter there too; and conversely you need to adjust the setLevelAndType method to also verify consistency with loopToDependencies).

I agree that it's rather convoluted to need to say lvlTypes[t][*(lvlToLoop[t][*(loopToDependencies[i][t])])], but the only solution to that is to reconsider the design of all the fields of the Merger class. For example, if we had lvlTypes : (TensorId, Level) -> LevelType instead of the current lvlTypes : (TensorId, LoopId) -> LevelType, then you wouldn't need to use lvlToLoop there. Of course, you'd have to redo the rest of the Merger code to make that work (which may end up inserting more loopToLevel uses than however many levelToLoop uses it removes). Or a different design would be to combine lvlToLoop and lvlTypes into a single lvlInfo : (TensorId, Level) -> (LevelType, optional<LoopId>); of course that would require making different changes to the rest of the Merger code. In any case, I think it would be wise to wait for D146693 to land before trying to make any of these changes, since the newtypes of that CL will greatly simplify the process of rearranging all these vectors.

Top level comments usually apply to the block of code, I find e.g.

assert(!loopToDependencies[i][t].has_value()); // must be first definition

a lot more readable, since you follow it direclty with the make pair/pushback

can we make this lvl < .... part also a helper method
(that way, all our asserts read almost like english ;-)

Why do you need this extra assertion? The isValidLevel assertion already ensures that the lvl is valid for the tensor t. Therefore, rather than checking the lvl twice, the rest of the code should instead maintain the invariant that levelToDependentLoop[t].size() == lvlTypes[t].size().

tensor level with index expression on it, reads awkward

how about

must be a tensor level that contains a non-trivial index expression

This should have been named levelToDependentLoop, since we don't use "idx" in this file anymore because it causes too much confusion. I mentioned this in the previous CL that introduced this field, but you landed the CL without fixing it