I do wonder if recursion is particularly hard for LLMs, given that they have a hard limit on how much they can loop for a given token. (Absent beam search, reasoning models, and other trickery.)
Given a prolog (not problog, but the non-stochastic one) source is a parametric grammar, we can perhaps* argue the inference on the programming logic level can be unfolded by using a pen and pencil. think L-systems, they are self-similar, and recursively defined. The catch is that the whole sequence gets rewritten on each step. If you can get the LLM to do this as it progresses with generation - you get recursion. Question is whether you can get the LLM rewrite the context window, and my bet would be someone is already working on it.
* I say perhaps, because PROLOG engines normally don't rewrite strings like crazy while doing inference, so my statement may be somewhat off.
Comments
I do wonder if recursion is particularly hard for LLMs, given that they have a hard limit on how much they can loop for a given token. (Absent beam search, reasoning models, and other trickery.)
Given a prolog (not problog, but the non-stochastic one) source is a parametric grammar, we can perhaps* argue the inference on the programming logic level can be unfolded by using a pen and pencil. think L-systems, they are self-similar, and recursively defined. The catch is that the whole sequence gets rewritten on each step. If you can get the LLM to do this as it progresses with generation - you get recursion. Question is whether you can get the LLM rewrite the context window, and my bet would be someone is already working on it.
* I say perhaps, because PROLOG engines normally don't rewrite strings like crazy while doing inference, so my statement may be somewhat off.