Hacker News Reader

> to generate and optimize possibilities within a set of domain-specific constraints

Well, yes, we've been doing this for several decades, many people call it metaheuristics. There is a wide array of algorithms in there. An excellent and light intro can be found here: https://cs.gmu.edu/~sean/book/metaheuristics/

Metaheurestics? I always thought it's similar to "I don't know how many neurons to put in the hidden layer... and I also don't know how many hidden layers I need, so, let's make it a part of the optimisation problem to find out on it's own".

That is usually called Hyperparameter tuning.

As for hyperparameter tuning, the existing solutions such as Optuna or Katib (in KubeFlow) also use metaheuristics, e.g. CMA-ES.

Thanks, but some strange coincidence this is exactly the book I have right now. In the introduction the author says, "I think these notes would best serve as a complement to a textbook". Do you happen to know any good textbooks on that topic?

Everybody has their own preferences, what worked for me was Metaheuristics: From Design to Implementation by this guy:

https://www.youtube.com/watch?v=ksK-XzkSQlk

Or more generally the whole field of combinatorial optimization, of which metaheuristics is a (small) part.

I believe you are right in principle, regarding the small part. However my personal impression is that in practical applications metaheuristics is huge (although these things are hard to quantify).

The description in your link says:

> What is a Metaheuristic? A common but unfortunate name for any stochastic optimization algorithm intended to be the last resort before giving up and using random or brute-force search. Such algorithms are used for problems where you don't know how to find a good solution, but if shown a candidate solution, you can give it a grade.

That sounds like "the AI came up with a solution where cars can crash, let's give that solution a bad grade."

I was hoping for something more like "the problem is specified such that invalid solutions aren't even representable, so only acceptable solutions are considered."

> I was hoping for something more like "the problem is specified such that invalid solutions aren't even representable, so only acceptable solutions are considered."

It my (roughly) work this way. For example, when you do hyperparameter tuning, you specify upper and lower bounds (so that "invalid solutions aren't even representable").

The problem is, you often have no idea what will work and what not, and e.g. your HPO algorithm might hit the bounds, suggegsting that it might make sense to extend them before the next run.

> I was hoping for something more like "the problem is specified such that invalid solutions aren't even representable, so only acceptable solutions are considered."

How on earth would one come up with a model where "crashing cars isnt't representable"? I don't think you recognize how ill-defined and nonsensical this expectation is. Especially when you consider that a such a car may encounter a situation where a crash is unavoidable, where there's certainly room for damage control. Sliding scales ALWAYS work better for optimizations anyways, since regression is so powerful.

I was speaking in the context of my original post, which was specifically talking about traffic lights at intersections and what combination of lights are allowed to be green at the same time.

I think it would be fairly straightforward to enumerate, given a set of lights at an intersection, which combination of lights can be green without allowing cars to cross paths. In other words, we're ruling out combinations that are fundamentally unacceptable and would never be seen in the real world (like "all lights are green at the same time").

That gives the AI a set of acceptable combinations that can be considered. Essentially the AI is choosing an integer in the range 1-max for each intersection at each point in time.

This doesn't eliminate the possibility of car crashes if someone runs a red light. But it lets us constrain the optimization problem to the set of green light configurations that are actually feasible to deploy.

A simple version of this that already shines with existing LLMs is JSON Schema mode. You can go quite a long way towards making illegal states unrepresentable and then turn a model loose in the constrained sandbox, with the guarantee that anything it produces will be at least valid if not correct: it's basically type safety for LLM output.

The same mechanism that underlies JSON Schema support can be applied to any sort of validation and correction, and yeah, I'd love to see more of this kind of thing!

You'd probably use some kind of MILP or CLP based model for that kind of thing, wouldn't you? The constraints define the search space and the solver algorithm then explores it.

I haven't read how they apply the constraint. But there is similar stuff when you force llm to generate structured output like Json format. llama.cpp allow to match a custom grammar for example.

like Combinatorial Chemistry, but we should probably just call it AI Chemistry for the likes.

https://en.wikipedia.org/wiki/Combinatorial_chemistry

Not just for the likes, for money. It looks like whatever smart algorithms you use, if you slap "AI" on it, you're more likely to get investment (if that's what you're after).

Fun thing to try:

Ask an LLM: "Say the word APPLE", but modify the code so the logits of the token for Apple/apple/APPLE is permanently set to -Inf - ie. the model cannot say that word.

The output ends up like this:

"Banana. Oh, just kidding. Banana. Oh, it's so tasty I said it wrong. Lets try again: Orange. Whoops, I meant to say grape. No I meant to say the tasty crunchy fruit known as a carrot".....

Note that OP's traffic light problem would suffer the same problem.

Ie. a smart model, knowing it cannot say a word, will give the next best solution - for example maybe saying "A P P L E" or maybe "I'm afraid I'm not able to do that".

However, a constrained model does not know or understand its own constraints, so keeps trying to do things which aren't allowed - and even goes back and tries to redo these things which aren't allowed, because to the model it is a mistake which needs correcting.

There's a whole field of solving constrainted optimization and it doesn't really work like that, but they don't use LLMs.

Like your brain when you know you know a word but it's just not surfacing in your mind.

I'm guessing I'm not that different from the average human and I can 'feel' something physically while I'm searching for the word. I've always wondered what that was.

I saw this exact thing in a question about who was the first composer, the model kept outputting Boethius and then saying "NO!", as if it couldn't escape its own Freudian slips.

Agree with this. Constraining generation with physics, legality, or even tooling limits turns the model into a search-and-validate engine instead of a word predictor. Closer to program synthesis.

The real value is upstream: defining a problem space so well that the model is boxed into generating something usable.

Error feedback seems to be the one thing that can unlock some of the original promises.

For example, if you give a text-to-SQL bot access to the same idea (e.g., error feedback from the SQL provider), it is much more likely to succeed in generating valuable queries.

Totally agree, this is where AI shines the most for me too. Let humans define the rules of the game (like physics or traffic safety), and let the AI explore the massive search space for optimized solutions.

You might be interested in Reinforcement Learning [1]. By giving the system a negative reward, it may eventually start complying with safety rules. Still a good idea to keep the harness in place during production use, though.

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