5 ms·

Hacking Diffusion into Qwen3 for the Arc Challenge

126 points by mattnewton 1y ago

gen3 1y ago
Incredibly cool work, and a great primer on diffusion
- ProofHouse 1y ago
  Are you aware of more in depth material outside research papers which I’ve mostly read already?
mNovak 1y ago
Really interesting to see the diffusion model solve the puzzles in an iterative way, which feels more similar to how I (and probably most humans) solve them. Outwardly, it seems to be limited by unmasking too few tokens per round, even when the heatmap shows many more high-confidence guesses available. On some of the larger puzzles it looks like it's wasting many rounds filling in the 'obvious' shapes, and then gets the interesting bit in the last round. It also doesn't seem to have learned the idea of "the background is blue with shapes drawn on top," where background is often 50% of the solution in these puzzles.
- namibj 1y ago
  You need a retraction/correction mechanism so the diffusion isn't locked in on a bad choice in order to really reduce iteration count, sadly.
twotwotwo 1y ago
It is kind of wild that most coding tasks are editing tasks, and we humans care a lot about code editing tools, but automated tools use code generation for editing where a valid block must be generated top-to-bottom in one go. Fixing a mistake requires re-generating the file or block of code. Or, if something generated later has implications for earlier code--a new import or function parameter's required, something like that--the only option is to go back and re-generate a big chunk. That'd be inefficient for humans, not implausible it's wrong for other code generators too. I don't know if diffusion specifically will be the approach. (Maybe there's something to generating edit sequences?) This post's note that diffusion kills KV caching is something I hadn't even considered. It does seem right to experiment with things other than strict start-to-end generation.
- imtringued 1y ago
  A massive problem with current generation llms is that they have a single globally ordered context and that the model is only allowed to append to the context. This is like having a single tape Turing machine. They can simulate a multi tape machine, but at O(n^2) complexity. The computation budget of an LLM is finite, so this has a massive practical impact.
  - cubefox 1y ago
    The article explains that this is not a problem but an advantage.
    - Sabinus 1y ago
      Apart from execution speedup due to caching, how does the article explain this is an advantage?
    - mattnewton 1y ago
      I wouldn't agree it's an advantage per se, just that the caching workaround works better than you would expect! It's still quite slow to generate each token at a time versus diffusing batches, it's just hard to cache all the work you do in each encoder step.
- namibj 1y ago
  You can still cache prompts; this just affects the cache for during generation produced tokens. And that's fairly harmless relatively speaking.
  - yorwba 1y ago
    If you completely do away with autoregression, prompt tokens can pay attention to generated tokens, so even the prompt tokens' KV vectors change at every step and you cannot cache anything. For this reason, models that generate text using diffusion typically generate blocks of tokens at a time, where tokens within a block freely attend to each other, but across blocks there's causal masking so that each block only depends on the preceding ones and we're back to autoregression again. That makes caching possible, but also means you still can't have diffusion change the beginning of a long text to match the end.
radarsat1 1y ago
Regarding the typewriter approach, I've wondered for a while if anyone has explored simple backtracking with LLMs? Like, have the LLM be able to generate a backspace/delete token that lets it "undo" previously generated tokens in an append-only fashion. Not sure how this would work with teacher forcing but seems feasible with RL.
- _diyar 1y ago
  With current LLMs, is meaningless because the current state is stored in the "context" (system prompt, user prompt, chat output so far). So if you apply a backspace token, you just end up where you started a second ago. I.e. At state A, you have decided to append token i to move to state B. Removing token i just sets you back to state A, where you would again just pick token i. (Note that this is ignoring the fact that there's a small probabilistic component to next token selection). In the RL/reasoning world of LLMs, you can instead just reward correct final output without policing the reasoning steps, and a strong model should learn to backtrack on their "thoughts" as appropriate (without removing it from the context). Edit: wording.
  - saurik 1y ago
    I think the idea is that the backspace would be a token, indelibly in the history, as it is something that happened: if you record on editor traces, the premise that I previously typed something and chose to delete it matters for my current state.
    - radarsat1 1y ago
      Exactly what I had in mind. After generating a few wrong tokens perhaps the model could realize it leads to a low probability path and have a way to "go back", while staying in context. Parent is right though that thinking models can kind of do that without some special token, I hadn't thought about that, nice observation.
      - namibj 1y ago

126 points by mattnewton 1y ago

gen3 1y ago

Incredibly cool work, and a great primer on diffusion

ProofHouse 1y ago
Are you aware of more in depth material outside research papers which I’ve mostly read already?

mNovak 1y ago

Really interesting to see the diffusion model solve the puzzles in an iterative way, which feels more similar to how I (and probably most humans) solve them. Outwardly, it seems to be limited by unmasking too few tokens per round, even when the heatmap shows many more high-confidence guesses available. On some of the larger puzzles it looks like it's wasting many rounds filling in the 'obvious' shapes, and then gets the interesting bit in the last round. It also doesn't seem to have learned the idea of "the background is blue with shapes drawn on top," where background is often 50% of the solution in these puzzles.

namibj 1y ago
You need a retraction/correction mechanism so the diffusion isn't locked in on a bad choice in order to really reduce iteration count, sadly.

twotwotwo 1y ago

It is kind of wild that most coding tasks are editing tasks, and we humans care a lot about code editing tools, but automated tools use code generation for editing where a valid block must be generated top-to-bottom in one go. Fixing a mistake requires re-generating the file or block of code. Or, if something generated later has implications for earlier code--a new import or function parameter's required, something like that--the only option is to go back and re-generate a big chunk. That'd be inefficient for humans, not implausible it's wrong for other code generators too. I don't know if diffusion specifically will be the approach. (Maybe there's something to generating edit sequences?) This post's note that diffusion kills KV caching is something I hadn't even considered. It does seem right to experiment with things other than strict start-to-end generation.

imtringued 1y ago
A massive problem with current generation llms is that they have a single globally ordered context and that the model is only allowed to append to the context. This is like having a single tape Turing machine. They can simulate a multi tape machine, but at O(n^2) complexity. The computation budget of an LLM is finite, so this has a massive practical impact.
- cubefox 1y ago
  The article explains that this is not a problem but an advantage.
  - Sabinus 1y ago
    Apart from execution speedup due to caching, how does the article explain this is an advantage?
  - mattnewton 1y ago
    I wouldn't agree it's an advantage per se, just that the caching workaround works better than you would expect! It's still quite slow to generate each token at a time versus diffusing batches, it's just hard to cache all the work you do in each encoder step.
namibj 1y ago
You can still cache prompts; this just affects the cache for during generation produced tokens. And that's fairly harmless relatively speaking.
- yorwba 1y ago
  If you completely do away with autoregression, prompt tokens can pay attention to generated tokens, so even the prompt tokens' KV vectors change at every step and you cannot cache anything. For this reason, models that generate text using diffusion typically generate blocks of tokens at a time, where tokens within a block freely attend to each other, but across blocks there's causal masking so that each block only depends on the preceding ones and we're back to autoregression again. That makes caching possible, but also means you still can't have diffusion change the beginning of a long text to match the end.

radarsat1 1y ago

Regarding the typewriter approach, I've wondered for a while if anyone has explored simple backtracking with LLMs? Like, have the LLM be able to generate a backspace/delete token that lets it "undo" previously generated tokens in an append-only fashion. Not sure how this would work with teacher forcing but seems feasible with RL.

_diyar 1y ago
With current LLMs, is meaningless because the current state is stored in the "context" (system prompt, user prompt, chat output so far). So if you apply a backspace token, you just end up where you started a second ago. I.e. At state A, you have decided to append token i to move to state B. Removing token i just sets you back to state A, where you would again just pick token i. (Note that this is ignoring the fact that there's a small probabilistic component to next token selection). In the RL/reasoning world of LLMs, you can instead just reward correct final output without policing the reasoning steps, and a strong model should learn to backtrack on their "thoughts" as appropriate (without removing it from the context). Edit: wording.
- saurik 1y ago
  I think the idea is that the backspace would be a token, indelibly in the history, as it is something that happened: if you record on editor traces, the premise that I previously typed something and chose to delete it matters for my current state.
  - radarsat1 1y ago
    Exactly what I had in mind. After generating a few wrong tokens perhaps the model could realize it leads to a low probability path and have a way to "go back", while staying in context. Parent is right though that thinking models can kind of do that without some special token, I hadn't thought about that, nice observation.
    - namibj 1y ago