Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #3659 > unrolled thread

AI for optimization?

Back to article view | Back to comp.compilers

Contents

  AI for optimization? anton@mips.complang.tuwien.ac.at - 2025-05-24 05:26 +0000
    Re: AI for optimization? arnold@freefriends.org - 2025-05-25 03:52 +0000
      Re: AI for optimization? antispam@fricas.org - 2025-05-25 22:11 +0000
        Re: AI for optimization? Kaz Kylheku <643-408-1753@kylheku.com> - 2025-05-26 03:42 +0000
      Re: AI for optimization? George Neuner <gneuner2@comcast.net> - 2025-05-26 00:28 -0400

#3659 — 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/

[toc] | [next] | [standalone]

#3661

In article <25-05-016@comp.compilers>,
 <anton@mips.complang.tuwien.ac.at> wrote:
>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?

The fact that AI is "hot" right now? "Sexy"? "Good for getting
startup capital"?  Who cares about correctness?

Pardon my cynicism.

Arnold

[toc] | [prev] | [next] | [standalone]

#3663

arnold@freefriends.org wrote:
> In article <25-05-016@comp.compilers>,
>  <anton@mips.complang.tuwien.ac.at> wrote:
>>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?
>
> The fact that AI is "hot" right now? "Sexy"? "Good for getting
> startup capital"?  Who cares about correctness?
>
> Pardon my cynicism.

I samewhat different spirit: LLM folks have a lot of money for research.
They try to apply LLMs to various things, it does not matter if those
trials make senss or not.  In the process they improve their machinery
and may get some possible applications.

Concerning correctness, one possible variation is to treat LLMs as
heuristic search, which may find some gems but also may produce
garbage.  For me it would be natural to combine that with more
reliable technology.  Possible combionations:
- optimization hints for classic compilers (in some cases that
  may involve inventing more precise types), if hints are wrong
  optimization would not fire or would not lead to improvement
  in runtime.
- LLM produced proofs.  Compiler would check the proofs and
  reject wrong ones.

Of course we will see companies applying LLMs techniques with
little checks, but this is due to how companies works, if not
LLMs than something else would be abused.

--
                              Waldek Hebisch
[See the two papers I recently sent out, which use LLMs to do C
to Rust conversion but have feedback to say whether the conversion
was correct. -John]

[toc] | [prev] | [next] | [standalone]

#3664

On 2025-05-25, antispam@fricas.org <antispam@fricas.org> wrote:
> Of course we will see companies applying LLMs techniques with
> little checks, but this is due to how companies works, if not
> LLMs than something else would be abused.

LLM-generated code cannot just be checked, because checking equivalence
of two pieces of code is as hard as the Halting Problem.

At best you can do it for very short program fragments, (like basic
blocks of instructions, or small trees) that can be executed to see if
they have the right effect on all the temporary registers.  (How genetic
programming works, more or less.) If the fragments don't contain any
looping or recursion, you don't have to worry about nontermination.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
[General program equivalence is the halting problem, but there are subsets where
you can say these two programs are equivalent or those two are not. The question
is whether there are enough of those to be useful. I have no idea. -John]

[toc] | [prev] | [next] | [standalone]

#3665

On Sun, 25 May 2025 03:52:17 +0000, arnold@freefriends.org wrote:

>In article <25-05-016@comp.compilers>,
> <anton@mips.complang.tuwien.ac.at> wrote:
>>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?
>
>The fact that AI is "hot" right now? "Sexy"? "Good for getting
>startup capital"?  Who cares about correctness?

ANNs can be made into excellent pattern matchers.  The probem IMO is
that too many "applications" are not simply matching patterns and
acting upon them, but rather are matching pattern /prefixes/ or
subsets of the complete pattern, and then acting /as if/ the complete
pattern exists.

This is what "generative" LLMs are doing: e.g., the AI sees the words
"brown" and "jumped", assumes "The quick brown fox jumped over the
lazy dogs", and bases its responses on that sentence.

If it turns out that, in fact, the user was seeking information on
"Encyclopedia Brown"[1] and the pickup truck rather than on different
species of canines interacting ... well, too bad.


>Pardon my cynicism.

Neural AI has been around since the 1950s ... I've been following it
since the late 1980s. It just wasn't practical to train even small
ANNs until (relatively) low cost SIMD became available.

Now ANNs have grown to scales where, even having cheap SIMD, once
again the computational costs have become an issue for training (and
retraining when relevant).
[The costs can be an issue even for deployment, though less so.]

ANNs are best used as high speed probablistic pattern matchers - which
includes use as associative memories.  The problems are in relevant
scoring/comparison of multiple possible matches [stability], dealing
with low scoring matches [guessing], trusting that the ANN
usually/always will be correct [non-technical users], and how the
responses are being used [again, non-technical users].

I think a rule based logic system using ANN for input matching is a
good combination with a lot of potential.  You don't need to resort to
ANN logic - rule based systems can account for probabilities ["fuzzy"
logic].  I remain unsold on ANN logic because - at least currently -
it neither can be verified, nor easily changed.  Having to retrain
your ANN logic every time some conditional in the problem set changes
is a non-starter for me.

YMMV.

>Arnold
George


[1] https://en.wikipedia.org/wiki/Encyclopedia_Brown

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web