5 ms·

For LLMs to solve code I think they should be AST-native. Code is a tree, not a sequence — yet we feed it to models linearly, with no explicit structure. Todays

For LLMs to solve code I think they should be AST-native. Code is a tree, not a sequence — yet we feed it to models linearly, with no explicit structure. Todays models lack recurrence or true memory, so they can’t reason over hierarchical structures effectively.

Nesco 2y ago
LLMs are autoregressive models. However, the notion of order in ASTs might be nonexistent, especially for parallel branches of computation/control flow. You could attempt to untangle each branch into N sequences, but this would erase control-flow information. Even when there is an objective ordering of the children of every node, you still have four traversal options: {preorder, postorder} × {BF, DF}. Note: For children lacking an objective ordering, you might apply generic rules to define a traversal order, but you’d end up with as many depth-first traversals as there are possible orders—essentially a crude heuristic. If you want the evaluation order to be dynamic at each step (e.g., using RL), the complexity grows geometrically worse. That’s been my experience tinkering with a custom AST DSL for ARC-AGI.
- dragonwriter 2y ago
  > LLMs are autoregressive models. Most LLMs are autoregressive models, but exceptions exist, e.g., Mercury [0] is a diffusion LLM. [0] https://www.inceptionlabs.ai/news https://www.inceptionlabs.ai/news
  - Nesco 2y ago
    Well, from my very limited comprehension of diffusion models, they apply to fixed length structure, mostly from a continuous space. Maybe a way to make them work with tree structures could be found - that's no trivial task
    - dragonwriter 2y ago
      Autoregressive LLMs don't usually work on tree structures, they work on capped-length linear token sequences, which are isomorphic to fixed-length sequences. I'm not sure why you think working on tree structures rather than fixed length sequences would be necessary for diffusion language models—which, again, actually exist; aside from Mercury which is proprietary, there is also LLaDA: https://ml-gsai.github.io/LLaDA-demo/ https://ml-gsai.github.io/LLaDA-demo/
- Xx_crazy420_xX 2y ago
  Cool to hear you've worked on ARC-AGI — I poked with it too. You’re totally right about the messy traversal space, especially with parallel branches. What feels ambiguous at the token level becomes structured ambiguity in the AST — and that’s progress. My hunch is that LLMs don’t need to solve the whole traversal space — they just need a clean, abstract interface. Even parallel branches can be normalized into a schema that the model can reason over consistently. And in practice, you rarely need full recursion or a complete tree walk to understand a node — but having that option unlocks deeper comprehension when it counts. This kind of structural understanding would also massively improve Copilot-style tools, especially for less popular libraries where token-level familiarity breaks down. If models could reason over types and structure instead of guessing based on frequency, completions would be a lot more reliable outside the top 1% of APIs.
otabdeveloper4 2y ago
LLMs process information in a strictly sequential manner. It's their core capability and what makes them feel so anthropomorphic.
- dragonwriter 2y ago
  > LLMs process information in a strictly sequential manner. "LLMs" as a class do not. Most LLMs, because most LLMs are autoregressive models, but diffusion LLMs exist and are not sequential in the way that autoregressive models are. > It's their core capability Being sequential is not a capability at all, much less a core one defining Large Language Models. > and what makes them feel so anthropomorphic. I disagree with this, too; I think what makes LLMs "feel so anthropomorphic" is the fact that most humans are very focused on language in perceiving other humans as human, and LLMs' output (as their name suggests) models human use of language, directly targeting a key feature used to identify something as human-like.
  - otabdeveloper4 2y ago
    The gimmick of the LLM is that it outputs text sequentially, as if it is talking to us. That's what makes them feel "alive" and "intelligent" to us. (And yes, ironically it's this sequential nature that actually limits their intelligence in practice, but whatever. The AI hype is about appearances, not facts.)
    - rowanG077 2y ago
      Are you saying that if visually LLMs would not output text sequentially but at once they would not be as successful as they are?
      - otabdeveloper4 2y ago
        Yes. Human speech is sequential (we make sounds one by one), and when LLMs mimic this with token-by-token autocomplete they seem more anthropomorphic to us. (I take issue with the word "successful", though. Selling LLMs as a human-like intelligence is a gimmick and a borderline scam.)
gnfargbl 2y ago
Has there been much work on reversing binaries into an AST form? It seems like something that somebody would have thought of researching, but I've not come across any efforts. Is it something you can do generically, or do you need to know the specific compiler? Do you need to know the specific language, even, or could you perhaps create some other hypothetical AST in a different language that would have led to the same binary?
pilooch 2y ago
Or just we could forget about code and have model act directly :) That's my bet.
lmeyerov 2y ago
The graph part , more so than the ast part, makes sense to me. We reason over programs as hairy dataflow/controlflow/etc dependency graphs that happen to originally be encoded as some sort of text->ast. GNNs went down some roads here, but never felt like a path to reasoning. So how to get an RL reasoner flow to do what is easy for datalog, natively and/or as a tool?

Nesco 2y ago

LLMs are autoregressive models. However, the notion of order in ASTs might be nonexistent, especially for parallel branches of computation/control flow. You could attempt to untangle each branch into N sequences, but this would erase control-flow information. Even when there is an objective ordering of the children of every node, you still have four traversal options: {preorder, postorder} × {BF, DF}. Note: For children lacking an objective ordering, you might apply generic rules to define a traversal order, but you’d end up with as many depth-first traversals as there are possible orders—essentially a crude heuristic. If you want the evaluation order to be dynamic at each step (e.g., using RL), the complexity grows geometrically worse. That’s been my experience tinkering with a custom AST DSL for ARC-AGI.

dragonwriter 2y ago
> LLMs are autoregressive models. Most LLMs are autoregressive models, but exceptions exist, e.g., Mercury [0] is a diffusion LLM. [0] https://www.inceptionlabs.ai/news https://www.inceptionlabs.ai/news
- Nesco 2y ago
  Well, from my very limited comprehension of diffusion models, they apply to fixed length structure, mostly from a continuous space. Maybe a way to make them work with tree structures could be found - that's no trivial task
  - dragonwriter 2y ago
    Autoregressive LLMs don't usually work on tree structures, they work on capped-length linear token sequences, which are isomorphic to fixed-length sequences. I'm not sure why you think working on tree structures rather than fixed length sequences would be necessary for diffusion language models—which, again, actually exist; aside from Mercury which is proprietary, there is also LLaDA: https://ml-gsai.github.io/LLaDA-demo/ https://ml-gsai.github.io/LLaDA-demo/
Xx_crazy420_xX 2y ago
Cool to hear you've worked on ARC-AGI — I poked with it too. You’re totally right about the messy traversal space, especially with parallel branches. What feels ambiguous at the token level becomes structured ambiguity in the AST — and that’s progress. My hunch is that LLMs don’t need to solve the whole traversal space — they just need a clean, abstract interface. Even parallel branches can be normalized into a schema that the model can reason over consistently. And in practice, you rarely need full recursion or a complete tree walk to understand a node — but having that option unlocks deeper comprehension when it counts. This kind of structural understanding would also massively improve Copilot-style tools, especially for less popular libraries where token-level familiarity breaks down. If models could reason over types and structure instead of guessing based on frequency, completions would be a lot more reliable outside the top 1% of APIs.

otabdeveloper4 2y ago

LLMs process information in a strictly sequential manner. It's their core capability and what makes them feel so anthropomorphic.

dragonwriter 2y ago
> LLMs process information in a strictly sequential manner. "LLMs" as a class do not. Most LLMs, because most LLMs are autoregressive models, but diffusion LLMs exist and are not sequential in the way that autoregressive models are. > It's their core capability Being sequential is not a capability at all, much less a core one defining Large Language Models. > and what makes them feel so anthropomorphic. I disagree with this, too; I think what makes LLMs "feel so anthropomorphic" is the fact that most humans are very focused on language in perceiving other humans as human, and LLMs' output (as their name suggests) models human use of language, directly targeting a key feature used to identify something as human-like.
- otabdeveloper4 2y ago
  The gimmick of the LLM is that it outputs text sequentially, as if it is talking to us. That's what makes them feel "alive" and "intelligent" to us. (And yes, ironically it's this sequential nature that actually limits their intelligence in practice, but whatever. The AI hype is about appearances, not facts.)
  - rowanG077 2y ago
    Are you saying that if visually LLMs would not output text sequentially but at once they would not be as successful as they are?
    - otabdeveloper4 2y ago
      Yes. Human speech is sequential (we make sounds one by one), and when LLMs mimic this with token-by-token autocomplete they seem more anthropomorphic to us. (I take issue with the word "successful", though. Selling LLMs as a human-like intelligence is a gimmick and a borderline scam.)

gnfargbl 2y ago

Has there been much work on reversing binaries into an AST form? It seems like something that somebody would have thought of researching, but I've not come across any efforts. Is it something you can do generically, or do you need to know the specific compiler? Do you need to know the specific language, even, or could you perhaps create some other hypothetical AST in a different language that would have led to the same binary?

pilooch 2y ago

Or just we could forget about code and have model act directly :) That's my bet.

lmeyerov 2y ago

The graph part , more so than the ast part, makes sense to me. We reason over programs as hairy dataflow/controlflow/etc dependency graphs that happen to originally be encoded as some sort of text->ast. GNNs went down some roads here, but never felt like a path to reasoning. So how to get an RL reasoner flow to do what is easy for datalog, natively and/or as a tool?