Under “Examples that moderately increase NLS depth”, you mention looped transformers, with a link to the Huginn paper, stating:
If the entire forward pass is repeated k times between each token, this increases the NLS depth by a factor of k compared to one forward pass.
That is true for the default configuration with separate KV-caches, but not for the `i mod k` KV-cache sharing scheme proposed in that same paper, which allows early recurrences to attend to opaque KV data generated by later recurrences of earlier tokens, creating a path whose NLS depth scales with token count, rather than just loop count. I tried to point this out here since this detail seems to be underappreciated. Perhaps you want to make that more explicit?
This is exactly the challenge I ran into. To prevent speculative evaluation strategies, the function should have a large output space, such that guessing becomes ineffective. At the same time, the function should not be tree-reducible (so e.g. not just addition/subtraction). There are many mathematical operations that fit these requirements, but they aren’t simple enough to be easily answered by an LLM. My swap-N and bitwise-N tests are compromises that try to balance those tradeoffs.