Surprising non-determinism example

[axch]

@pgmoren gives us the enclosed test program, which is not deterministic (but should be). Specifically, the values reported by global_log_joint and global_log_likelihood after the infer command vary (in both backends!). The ones before are stable. test_seed.py.txt

Update: Lite is deterministic as of June 6 (PR #579)

[axch]

On further investigation:

• Puma and Lite are both unstable
• Even without the resample
• Sampling values (as opposed to computing log score) is also unstable, but again only after inference.

[axch]

One candidate explanation (at least for Lite): All the node collections used in scaffold construction are sets. Not only that, but keyed by the object identities of the nodes, which are of course unstable from run to run.

How does this leak to sampling different values after inference? Not completely clear, but

• Scaffold element traversal order is unstable.
• Therefore, the order of principal nodes is unstable (but should not be a problem in this example because all proposals are single-site).
• Also, the order of border nodes (starting points for the regen recursion) is unstable.
• Therefore, the order in which nodes are (removed from and) added to the scope maps in unstable.
• Therefore, which node gets selected by a (mh default one 1) proposal is unstable, because they are chosen by a stable index into an unstable-order list.
• And that leaks all over everything.

Why does Puma also exhibit instability? Not sure, but probably has a similar bug (perhaps in a less severe fashion, if the structures indexed by node identities are, e.g., binary search trees rather than hash tables).

[axch]

Candidate solutions:

• Index the scaffold structures by node address instead
  • Con: May not port to Puma
  • Con: May impose a performance hit (see #403)
• Maintain a global node creation order field and index the scaffold structures by that
  • Con: Global state = contention, problems with parallelism
  • Con: Only applies to structures keyed by nodes (which I think is all those currently present, but...)
• Index the scaffold structures by insertion order
  • Mild con: Presumably need to write that library structure
  • Does smap.py already do that job?
  • Mild con: Order ought to be stable, but brittle to either code changes or leaks from instability elsewhere

[riastradh-probcomp]

Indexing the scaffold structures by insertion order can be done by dropping in collections.OrderedDict where we use dict.

[axch]

For the record: the uploaded program hardcodes a backend (Puma, I believe), but is a valid test program for either backend by editing that hardcode point.

[axch]

For the record, confirmed (again?) that this issue does not affect Lite anymore.