Snapshots, rollbacks, or efficiently re-writing past states (re: MCTS et al.)

[tucnak]

From what I could gather from the documentation and APIs, it would seem that the generation process is exclusively sequential, or should I say, linear. This is unfortunate, as my initial intuition didn't hold; that is, to use AICI as easily implementing Monte Carlo tree search, function-calling with rewrites, and some more advanced sampling strategies (re: GBNF grammar-guided sampling.)

I think, the project's ambition to more tightly control the model's output is really well-placed, however without some means of bi-directional movement, re-writes, I struggle to see what I would use it for. You seem to have identified the primary challenges pertaining to controlling model output correctly, mostly the API mis-match in the various backends, the exact means of controlling the sampler, etc, however without some notion of going back in time, or re-writing past states, it really falls short. MCTS is all the rage these days, & I believe AICI could facilite all kinds of MCTS-like implementations.

Does this relate in any way to what you guys are trying to accomplish?

P.S. Great job!

[emrekiciman]

Hi @tucnak thanks! We do support backtracking KV-cache to a previous state as one of the key primitives exposed by AICI (*). And backtracking, together with fast-forwarding of new text together enable arbitrary editing of past text. Agreed that this is critical functionality.

We think this does need to be improved to handle things like state space models and sliding window attention. Could you share more about your thoughts about what's missing to enable a better MCTS, for example? I'm sure there's room to make common cases more efficient.

(*) See the backtracking section in the pyctrl README for an example: https://github.com/microsoft/aici/tree/main/controllers/pyctrl )