[Xx_crazy420_xX]

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]

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.

[Xx_crazy420_xX]

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.

[dragonwriter]

> 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

[Nesco]

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]

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/

[gnfargbl]

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?

[lmeyerov]

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?

[pilooch]

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

[otabdeveloper4]

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

[dragonwriter]

> 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]

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.)

[lucianbr]

> That's what makes them feel "alive" and "intelligent" to us.

What is the basis for this claim? Seems like "A" (chatbots output text sequentially) is true, and "B" (they feel intelligent to us) is true, and you're claiming "A causes B" without any support at all. Just because they happen to both be true and you personally feel there is a causal relationship, which proves nothing.

[dragonwriter]

> 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.

Yes, I got that that was the original claim. I still disagree with us. What makes them feel alive and intelligent is that they produce human-like language output, not that the process by which they construct that output is sequential. Non-autoregressive LLMs of equal output quality would (do) appear just as alive and intelligent as autoregressive LLMs. An autoregressive LLM behind a non-streaming request/response interface where the token-by-token sequencing of the response is not exposed to the user still seems just as intelligent as one where the output is streamed to the user.

[rowanG077]

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]

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.)

[mike_hearn]

Not fully.

The point of transformer attention is cross-wise processing of tokens that computes their relationship to each other at multiple levels of abstraction. That's why LLMs can read so fast: they're processing all the input tokens in parallel.

LLMs emit tokens in a sequential manner at the level of the outer loop, but clearly inside the activations is a non-sequential map of the entire planned output, otherwise they wouldn't be able to make coherent sentences or speak German (which puts verbs at the end).