AI for optimization?

While there seem to be many papers on using LLMs for automatic programming and
the like, and I am sceptical of that because LLMs have problems with
understanding correctness AFAICT.


Another way to use the advances in machine learning that looks promising to me
would be to direct optimization, similar to how AlphaZero directs the search for
a good move in games.


We can understand optimization as a sequence of transformations, and each
transformation is selected among a large number of transformations that are
possible for the given program, and that's how humans tend to optimize.


The traditional approach to optimization is to do optimization phases that
analyse a program for the applicability of a few particular transformations and
then apply all that fall out of the analysis (and typically being somewhat
conservative in applying transformations where it is not clear that they improve
the program). Then have another optimization phase for a few more
transformations. This approach has some advantages, but it means that phase
ordering is important, and that has lead to papers (maybe two decades ago) about
trying different phase orders.


The advantages of this analysis-driven approach are that you don't need good
knowledge of which parts of the program are executed a lot of times (you just
apply the transformations to all the code where they are applicable), and the
cost of analysis per transformation is lower.


One way to use the advances in machine learning would be to learn how to do
phase ordering.


Another way would be to use an approach that's more in the way humans work: take
a look at the program (with knowledge or good guesses at what's executed how
often) and then select the most promising among a number of transformations,
analyse the program to find out whether it can be applied and maybe what
preliminary transformations are necessary to do so, then apply the preliminaries
and the transformation, then repeat until no promising transformation can be
found. Backtrack to find alternatives (so you don't have to guess right all the
time), until the time budget is exhausted.


The transformations and their analyses would be done with traditional methods
and we would have a good confidence that they are correct. The directing would
be done by the machine learning; if it's wrong, the result would just be a slow,
but still correct program.


An advantage of this approach is that the training data is not limited by input
produced by humans. One probably wants to train on existing programs, but can
assume any plausible profile for such programs and optimize for that profile,
try out many different transformation paths, evaluate the result, and use that
as feedback for the machine learning algorithm.


Admittedly, with this scenario the resulting optimizer will only work well in
profile-guided optimization; one might also try to predict the profile of a
given program with machine-learning techniques, but given that humans are
notoriously bad at that, I am not optimistic that machine learning will fare
better.


I expect that I am not the first one with this idea, and that there are papers
about it already, but I have not kept up with optimization literature, so I am
not aware of that. Maybe someone knows of such work?


I am just surprised that I read and hear so much about work based on LLMs, which
seems to be a dubious technology for doing things where correctness is
important. What am I missing?


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

Return to the comp.compilers page.
Search the comp.compilers archives again.