but it is deterministically lazy according to a traversal of attribute names

Yeah, I guess it's a matter of perspective. Probably "spooky action at a distance" would be a better description. Otherwise it's hard to explain evaluation rules that explains why these two differ in result without involving symbol table for the whole interpreter session:

$ nix-instantiate --eval -E 'let a = 1; in { a = 1; b = throw "bad"; } == { a = 2; b = throw "bad as well"; }'
false
$ nix-instantiate --eval -E 'let b = 1; in { a = 1; b = throw "bad"; } == { a = 2; b = throw "bad as well"; }'
error:
       error: bad

Or even this:

$ nix repl
nix-repl> let a = 1; in { a = 1; b = throw "bad"; } == { a = 2; b = throw "bad as well"; }
false

vs

$ nix repl
nix-repl> b = 1

nix-repl> let a = 1; in { a = 1; b = throw "bad"; } == { a = 2; b = throw "bad as well"; }
error:
       error: bad

I would say it's not a deterministic evaluation.

I wonder what would be the performance impact of actually making this deterministic. If you want to go fast you shouldn't do too many deep comparisons anyway...
What if we sorted the attributes that need to be compared?

1. figure out the value pairs that may be unequal, using the pointer equality hack
2. sort these attribute pairs by name string (alphabetically, not symbol id)
3. compare recursively in sorted order with cutoff

The pointer equality hack has its own problems, but those could be alleviated by forcing the value. I don't think we need to consider that now.

these two differ in result without involving symbol table for the whole interpreter session:

I apologize, I overlooked that part. Yes the fact that unused entries in the lexical scope affect the results is completely nuts.

What if we sorted the attributes that need to be compared?

I think cppnix already does. Tvix does, and had to do so in order to match cppnix's behavior (and pass its test suite).

Speaking of which, tvix does not emulate the scope-sensitive cppnix behavior described here. Paging @sternenseemann ...

What if we sorted the attributes that need to be compared?

Pretty sure that all implementations already do this. Not by sorting the attributes on comparison, but by always having a sorted representation of the attribute set in memory already (in cppnix this is a sorted vector of pairs, in tvix this is a B-tree map).

Our implementation sorts using a string interning id rather than lexicographically, so the sort order is non-deterministic.
Haven't heard of cppnix.

cppnix = c++ nix, this here project.

Our implementation sorts using a string interning id rather than lexicographically, so the sort order is non-deterministic.

Seems like this has changed since 2.3, where the interned strings were compared by the interned string, not the interning ID. Not sure how the whole machinery (esp. attribute lookups) works here at the moment then.

Note that you can trigger this behavior without using throw at all:

nix-instantiate --eval -E 'let a=1; in { a=1; b=rec { f=f; }.f; } == { a=2; b=rec { f=f; }.f; }'   # false
nix-instantiate --eval -E 'let b=1; in { a=1; b=rec { f=f; }.f; } == { a=2; b=rec { f=f; }.f; }'   # infinite recursion