10 ms·
Diffusion on syntax trees for program synthesis
- remexre 2y ago[flagged]
- almostgotcaught 2y ago[dead]
- deleted 2y ago[deleted]
- sakras 2y agoThis is very cool! My first thought is: can this be applied to converting raster graphics to vector graphics (eg PNG to SVG)? Seems like a very similar problem, though probably much more computationally expensive.
- szvsw 2y ago> We apply our approach to inverse graphics tasks, where our model learns to convert images into programs that produce those images. I would argue that at least on a philosophical level, this is, definitionally, the process of converting raster graphics to vector graphics, as long as you by the premise that the difference between the two is simply that vector gfx is a programmatic/imperative representation of image generation, while raster is a data structure/declarative representation of images. In other words, simply put, raster images are just arrays, vector images are sequences of instructions. Raster images are naturally much closer to the “raw” data needed by the output mechanism, while vector images require a much more complex interpreter.
- adrianmonk 2y agoOr, raster and vector images are philosophically the same thing. The only difference is that vector has more operations than raster. Raster just has "draw unit square at integer coordinates".
- szvsw 2y agoYep, I agree with this - tried to hint at that when I said “vector images require a much more complex interpreter”.
- DougBTX 2y agoOn the other hand, A Pixel Is Not A Little Square[0] would disagree, a raster is a grid sample of a continuous function. [0] http://alvyray.com/Memos/CG/Microsoft/6_pixel.pdf http://alvyray.com/Memos/CG/Microsoft/6_pixel.pdf
- code_biologist 2y agoThough I agree with the point that paper makes (it makes a good case that the little square mental model of a pixel is mostly inappropriate) it does seem focused on imaging and does not mention places where the little square mental model is appropriate. Pictures of cats, subpixel rendered text, or company logo SVGs as displayed on a web page are point samples and not little squares. User interfaces are good examples of often being little squares. Calling HN's beige background a point sampled discrete representation of an underlying continuous function seems pretty tortured — to me it seems like a bunch of beige little squares.
- andybak 2y ago> vector gfx is a programmatic/imperative representation of image generation, while raster is a data structure/declarative representation of images. This seems a bit off to me. Aside from oddities such as Postscript, most vector formats are canonical examples of declarative code. The distinction is more about what is being represented rather than how it is represented.
- pmayrgundter 2y ago[dupe]
- pmayrgundter 2y agoIt's funny, this kind of subtree mutation was looked at pretty deeply by Koza and Adamı in the 90s under the rubric of Genetic Algorithms, but with a slightly different optimization function One ref in the paper to 2000 for GAs for fast generation of program trees, but that's missing the main show Hope they're reading this and dig into those guys work
- 29athrowaway 2y agoYou can also say backpropagation is the chain rule from centuries ago.
- elijahbenizzy 2y agoBackpropogration is just an application of the chain rule -- cool that we all learned it in high school!
- telotortium 2y agoIt is a computationally clever application of the chain rule to minimize the amount of computation needed to compute gradients for all parameters in the network.
- om8 2y ago> to minimize the amount of computation IMO backprop is the most trivial implementation of differentiation in neural networks. Do you know an easier way to compute gradients with larger overhead? If so, please share it.
- QuadmasterXLII 2y agoMy first forays into making neural networks used replacement rules to modify an expression tree until all the “D” operators went away, but that takes exponential complexity in network depth if you aren’t careful. Finite differences is linear in number of parameters, as is differentiation by Dual Numbers
- 2y ago
- pamelafox 2y agoI would love to see them try this with the Processing/P5Js libraries. Thats what the ASTs reminded me of. It could potentially be used to help students trying to figure out how to fix their programs. I used AST-based hints for my ProcessingJS courses on Khan Academy, but I handwrote the AST patterns for those hints.
- dwlg00 2y agoI'm failing to see how this is novel. It looks like they're doing diffusion on a representation system for 2D graphics, which is very different than an actual program (they do address this limitation to be fair)
- revalo 2y agoYeah, this is true! These are more like expressions rather than programs. We were mostly following the language used by previous work, https://arxiv.org/abs/1906.04604 https://arxiv.org/abs/1906.04604
- hobofan 2y agoCouldn't this be used to do HTML generation from designs? Especially when combined with multiple viewport sizes at the same time, generating a fluid HTML layout would be pretty awesome.
- dinobones 2y agoI don't understand the "magic" here. In a traditional approach, you would generate random images, calculate some distance metric, then use some optimization method like simulated annealing to minimize the distance. I get that the difference between the image representations is being optimzied here, but how is it possible that changing tokens in a program is differentiable?
- revalo 2y agoChanging tokens in a program is not differentiable. For me, the key idea is that you can train a neural model to suggest edits to programs by randomly mutating nodes. And when you run this neural model, you get to make edits that are syntactically correct (i.e., a number will only replace a number etc.) according to a context-free grammar.
- montyanderson 2y agoThis is fascinating. I've been trying to envisage how the new language models will have deeper or lower-level role in software production than simple code generation.
- passion__desire 2y agoI think browsers could be the next iteration. Website backend will have premade flows. e.g. a transfer money from my account to another account, etc. And through fluidic UIs, the website will collect info need, necessary approvals before flow submission. AI-based browser DOM manipulation.
- artninja1988 2y agoSurprised to see Stuart Russells name on this as I thought he was fully consumed by the doomsday cult. Although he's last author so he's probably only on it because he's the head of the lab
- samatman 2y agoA lot of doomers work on AI. While frowning, and shaking their heads very gravely, so you know they don't approve.
- optimalsolver 2y agoIf we don't get to AGI first, the bad guys will.
- sgt101 2y agohang on, what if... we're the bad guys?
- ngruhn 2y agoI haven’t heard anyone make sane case against the doomsday argument. Only attacks.
- ImHereToVote 2y agoYou can't be scared while you laugh at someone. So laughing is a good thing to do to stave of fear.
- robxorb 2y agoWhat's with the last author/first author thing in science papers? I've read several times that the author listed last is usually the most significant contributor, and the first author the least significant, due to some kind of tradition around modesty plus favourably introducing new names. (Which then of course doesn't work, if everyone knows it's happening...) Here, you've interpreted it as the reverse, and by that I mean in the sensible way - did you not know about the tradition, or are you wrong? And how can we know either way for sure?
- behnamoh 2y agoHow is it different from genetic algorithms that mutate the syntax tree until the target output is achieved?
- Karellen 2y agoIt's different in the same way that using an LLM instead of a traditional Markov chain is a different way of generating text. You're still predicting the next word at a time to hopefully end up with plausible sentences/paragraphs, but the difference is in how you model the training dataset, and how you use that model to make each next choice in your live application.
- jmugan 2y ago[flagged]
- baq 2y agoS-expressions are basically an AST with minimal parsing. It’s very convenient to work with.
- jmugan 2y agoYeah, that's basically my objection. The convenience seems to hide something important. I know you can write any program with LISP, but using LISP for this kind of thing seems to be a symptom of limited applicability.
- baq 2y agoI don't share this concern. You can easily write Python, Typescript and C++ in S-expression format since you're basically writing an AST, that's the whole point. Conversion between one and the other is... maybe not trivial, but certainly not rocket science. E.g. https://hylang.org/ https://hylang.org/
- koito17 2y agoNot to mention, there are languages with the same expressiveness as most Lisp-like languages. Dylan and Julia immediately come to mind. Julia in particular makes it easy to convert between code and syntax tree data, so you have arguably the same capabilities as Lisp macros, in a syntax that would appease GP's preferences. I think another big thing that makes Lisp-like languages (Common Lisp, Clojure, Racket, ...) convenient for this kind of work is the fact that everything is an expression. Having "statements" and "expressions" separate makes writing some programs awkward. I use Clojure at my day job, and the way I write code takes for granted that I can simply bind `foo` to the result of a `case` or an `if` without ad-hoc operators that have completely different syntax from their statement-equivalents.
- ipsum2 2y ago
- gastonmorixe 2y agocould diffusion work at binary level? I mean, could we train a diffusion model to generate a final binary of a program given a prompt? probably AST may be better but the binary I feel is extremely easy to at least test fast if it works or not. Though there may be a lot of drawbacks, if this is possible I can't wait until we ask "give me an app that does that" and the diffusion model starts generating all te bytes the app to do the job. Just wondering
- dcreater 2y agoThat would be mind blowing. Why go through all the lost intermediary steps, especially through Python and JS, when you can generate machine code directly
- eternauta3k 2y agoIf your model is error-prone, having control structures, types and other compile-time checks is very valuable. It's harder to constrain arbitrary machine code to make something sensible.
- mejutoco 2y agoIntuitively it makes sense, but I am not fully convinced about this. You could give it only a few register and discard invalid operations for certain registers or plain known invalid operations.
- 2y ago
- zelphirkalt 2y agoThis sounds more similar to what people have done with Racket and hint generation for MOOCs. Not sure which university it is again, but I saw a presentation about how they generate hints for students by mutating the syntax tree and analyzing how they had to modify it, to get to a target solution. It was presented at some RacketCon, maybe a decade ago already. Perhaps that knowledge how to do it can be combined with newer machine learning approaches? EDIT: I found the talk: https://invidious.baczek.me/watch?v=ijyFC36kVis https://invidious.baczek.me/watch?v=ijyFC36kVis
- aquarius0 2y agoThe application to inverse graphics tasks reminds me of this paper which was released one week earlier: https://arxiv.org/abs/2405.15306 https://arxiv.org/abs/2405.15306
- flakiness 2y agoThe PDF is super slow to render, I guess because it contains commands from programmatically generated figures. It gives it a kind of an academic-paper-feel I miss these days. https://arxiv.org/pdf/2405.20519 https://arxiv.org/pdf/2405.20519
- lwansbrough 2y agoI’d like to see it with SDFs!
- grondilu 2y agoPlease elaborate. Are you thinking of approximating the distance function with an algebraic expression, with algebra itself being the "programming language"?
- Philpax 2y agoYou can represent arbitrary shapes through the composition of SDFs: https://iquilezles.org/articles/distfunctions/ https://iquilezles.org/articles/distfunctions/ These can be treated as parameterised nodes in a tree, similar to what's happening here. It follows that there may be a possible adaptation of this to SDF composition, such that you can give it a shape and have it produce the SDF nodes + composition required to produce that shape. Most existing approaches to SDFs with NNs have the NN itself take on the role of the SDF (i.e. given a point, it predicts the distance), so there's a compelling opportunity here to build a system that can produce spatial representations from existing imagery without NN inference at render-time. I imagine adding the third dimension to the problem makes it much harder, though! I'll have to give the paper a read to determine how coupled to 2D their current approach is.
- grondilu 2y agoThe application to graphics is interesting. It seems to me that current image generation models struggle with stylized pictures ("ligne claire" in comics, geometric shapes and so on). After all this kinds of pictures should be easy to encode in vectoriel formats (like SVG), which are basically programming languages.
- machiaweliczny 2y agoI had idea about doing something similar based on DifussER paper. One would need to model code edits as algebra similar to add char, replace char or delete char but something like define func, remove func, define var etc. I am undereducated to do it myself but have a feeling it could work.
- machiaweliczny 2y agoI will have to dig into this paper as it looks like exactly this. I wonder if they use closures to limit valid operations space. The only thing I didn’t understand to make it happen was how to connect it well to description of desired program or edit. BTW my idea was to train it by destructing programs available on github (so adding noise via some random valid ops and then removing it to retrieve original program). Probably best done in N-1 commit is treated as noise and moving back to commit 0
- can16358p 2y agoI wonder how this would apply to compiler/interpreter optimizations. Is it possible that it can "disect" some parts of the execution, perhaps at assembly level, and come up with optimizations specific to the compiled code without changing the output (I mean expected program output, not emitted binary), that modern compilers have not deterministically come up with?
- bastawhiz 2y agoI expect the answer is "no". I wouldn't expect a tool like this to "discover" assembly without being trained on the compiled output. The model has no notion of how or where the code runs. After decades of compiler research and super compilers chugging away, we're sort of at a point where discovering novel optimizations with results that are more than a smidge of improvement is almost impossibly unlikely. Compilers today are really good. That said, I think the value that something like this might have is being able to optimize the intent of the code. If it can determine that I'm sorting some numbers, it can rewrite my code to use a faster sorting algorithm that has the same functional properties. If I'm storing data that never gets used, it can stop storing it. It has a view of the code at a level above what the compiler sees, with an understanding not just of what is being done, but why.
- xavxav 2y ago> After decades of compiler research and super compilers chugging away, we're sort of at a point where discovering novel optimizations with results that are more than a smidge of improvement is almost impossibly unlikely. Compilers today are really good. I agree when it comes to peephole optimizations, but there's still a lot of juice left in exploiting language guarantees (immutability, non-aliasing, data-parallelism), however most compiler developer energy is spent propping up C/C++ and consequently optimizations are developed with those languages in mind.
- gergo_barany 2y agoThis is called superoptimization: https://en.wikipedia.org/wiki/Superoptimization https://en.wikipedia.org/wiki/Superoptimization There are people applying synthesis techniques to superoptimization. So something like this would possibly apply.
- whereismyacc 2y agoThere's been talk in the past about github adding integrations with common build tools (automatically?). What if you could compile every llvm-compiled project on github and run a diffusion model over the intermediate representations?
- daralthus 2y agowhat's the output?
- whereismyacc 2y agoI guess the output would be an llvm intermediate representation that you can compile down and run, right? I'm stretching pretty far past my knowledge here.
- Philpax 2y agoI think the question - at least, for me - is "what do you expect to do with this system?" What will you output with your diffusion model?
- randcraw 2y agoAn AST or any intermediate representation of an input language isn't strictly necessary for a translation task. But if you want a human to understand the translation, an IR can go a long way to illustrate the translation process into a human comprehensible form. The transformations of the tree can also provide insight into the various translation activities and alternatives, like translation from one human spoken language into another (text or voice), from one musical style into another (in notation or audio), or source code into executable with multiple optimization steps. Without the AST (IR), the human must remain out of the loop, relegated to being a bystander mystified by the inexplicable magic taking place inside the automated translator.
- JHonaker 2y agoMarkov Chain Monte Carlo for program synthesis isn't exactly novel. The most immediate reference I thought of is Josh Tenenbaum's [1]. There's also a lot of demos in WebPPL (web probabilistic programming language)[2] like [3] for the synthesis of 3D space-ships. I highly recommend their associated books on The Design and Implementation of Probabilistic Programming Languages [4] and Probabilistic Models of Cognition [5]. I also highly recommend taking a look at the publications of the MIT Probabilistic Computing Project [6]. [1] Human-level concept learning through probabilistic program induction. https://www.cs.cmu.edu/~rsalakhu/papers/LakeEtAl2015Science.pdf https://www.cs.cmu.edu/~rsalakhu/papers/LakeEtAl2015Science.... [2] http://webppl.org/ http://webppl.org/ [3] https://dritchie.github.io/web-procmod/ https://dritchie.github.io/web-procmod/ [4] https://dippl.org/ https://dippl.org/ [5] http://probmods.org/ http://probmods.org/ [6] http://probcomp.csail.mit.edu/ http://probcomp.csail.mit.edu/
- marcelroed 2y agoIt’s worth noting that Shreyas (the first author) was a student with Tenenbaum at MIT before he went to Berkeley
- ofou 2y agoHere's a GPTo summary of the paper https://www.emergentmind.com/papers/2405.20519 https://www.emergentmind.com/papers/2405.20519
- goexploration 2y agoThe beam search idea is interesting. Curious to know if beam search for reverse diffusion has been done before. Could anyone clarify how they integrate beam search with the reverse diffusion- do they sample m > k nodes from a reverse diffusion step and expand only the top k nodes?