1. Choose the first token. If well-trained you have a 75% chance of choosing "a" and a 25% chance of choosing "b". Both are valid for that grammar.
2. Choose the second token. Regardless of your first token there is exactly once choice of grammar-adhering completion. You're now at a 75% chance of "ab" and a 25% chance of "ba" (mirroring the first-token chance).
For a toy example like this you obviously wouldn't use an LLM, but techniques like you're suggesting don't work because it's infeasible to enumerate all the valid outputs and re-weight and because greedy and semi-greedy strategies aren't anywhere near sufficient to side-step the issue. At the point in time you select the "a" token at a 75% probability it's game-over unless you re-run the LLM. You can't beam search either (doing so just changes which token you'll mis-predict, and even then only for very local grammar mistakes).
Looking at my JSON example from earlier, a beam search to avoid that re-weighting requires a depth of at least 4 (going as far as the ellipsis plus the stop token), and it won't suffice to just consider locally high-weight paths (you can probably hack something together for that one issue in particular which searches high weight paths and backtracks if they're found to be low-weight due to grammar mismatches, but that has its own bias unless you fan out to all 1e19 length-4 paths, and it won't solve the general problem regardless).
Phrased slightly differently, you don't have a compute_future_grammar_adhering_weight(token) function which is tractably computable, so you can't actually redistribute the 8.3% probability from the "a" branch to the "b" branch.
Oh now I understand. I thought your ab and ba were single tokens (even though that doesn't make sense in context). Once you point out they're separate tokens, I follow you. Thank you!
Edit: that's a great example
Edit 2: even more fun: training data is [ab, ab, ba, bb, bb, bb]. Then constrained sampling flips your likelihood from 1:2 to 2:1
Thanks :) My example is minimal, which is a little nice since I wind up re-deriving it in a hurry every time I need it. I do like the 1:2 to 2:1 symmetry though. Very elegant.
1. Choose the first token. If well-trained you have a 75% chance of choosing "a" and a 25% chance of choosing "b". Both are valid for that grammar.
2. Choose the second token. Regardless of your first token there is exactly once choice of grammar-adhering completion. You're now at a 75% chance of "ab" and a 25% chance of "ba" (mirroring the first-token chance).
For a toy example like this you obviously wouldn't use an LLM, but techniques like you're suggesting don't work because it's infeasible to enumerate all the valid outputs and re-weight and because greedy and semi-greedy strategies aren't anywhere near sufficient to side-step the issue. At the point in time you select the "a" token at a 75% probability it's game-over unless you re-run the LLM. You can't beam search either (doing so just changes which token you'll mis-predict, and even then only for very local grammar mistakes).
Looking at my JSON example from earlier, a beam search to avoid that re-weighting requires a depth of at least 4 (going as far as the ellipsis plus the stop token), and it won't suffice to just consider locally high-weight paths (you can probably hack something together for that one issue in particular which searches high weight paths and backtracks if they're found to be low-weight due to grammar mismatches, but that has its own bias unless you fan out to all 1e19 length-4 paths, and it won't solve the general problem regardless).
Phrased slightly differently, you don't have a compute_future_grammar_adhering_weight(token) function which is tractably computable, so you can't actually redistribute the 8.3% probability from the "a" branch to the "b" branch.