Posted by jonluca 10 hours ago
The Exponential Time Hypothesis Is False [pdf] - https://news.ycombinator.com/item?id=50251661
My guess is that in formally verifiable domains you can use RL-esque processes to get lots of good high-quality training data with reward signals (does it verify?), but the same does not apply to "scruffier" work. I would also imagine that the data volume of high-quality scientific work in "scruffy" domains is too low for the large language models to have a good manifold for "high-quality biology research". Would love to be proven wrong if anyone knows of anyone doing great scientific work with large language models in non-verifiable domains though.
Many of the harnesses used to search for solutions rely on quick/cheap correctness checks to discard incorrect hypotheses. With something like biology, you might need to run a wet lab experiment to reject an idea. This can add days per iteration, slowing progress down by a factor of 100 or more.
The sad reality is that many computational approximations for biological phenomenon are relatively weak and lack the predictive power we need.
In an area I am more familiar with though still not my domain: when the stiffness matrix and computational linear algebra methods collide, it unlocks a world of computational structural design and analysis by commoditizing the underlying mathematics. This is a simple example, but you get the idea.
Obviously with CFD, mechanics, etc there is always massive work being done to try to unlock new computational methods, faster/parallelizable computational methods, differentiable ones, etc etc, but the general feeling is that the core physics are well modeled (NS millennium problem not withstanding) and are not lacking in predictive power for useful applications. I would have assumed that the same would be generally true for computational biology etc, so just curious to hear you elaborate more. It seems plausible to me that turning the brute force of “the models” (as in, swarms of AI compute) to work on/develop/solve/address whatever representational problems there are in the computational approximations/numerical methods you mention, particularly if that is a bottleneck to performing more extensive methodological/experimental exploration in silico to enable better exploitation/use of limited resources in wet lab.
Again, I know nothing about computational biology, just stating my intuition and curious what your take is. Probably the limits of my knowledge can be demonstrated by the fact that the only modeling methods that come to mind as being vaguely relevant would be, like,… molecular dynamics, maybe discrete element method in a weird way but doubtful, and various pop science understandings of protein folding etc.
1. Biology has a very nasty habit of not cleanly abstracting. It's not like we can treat every protein as a "diffuse mass" without losing a ton of important interactions. This is unlike something like CFD where you can treat a mass of water molecules with certain constants. Think of something like cancer: a small mutation to a DNA strand can cascade into a tumor. You have to deal with the mutation happening at an atomic level while scaling to a whole organism (yes I know there's models that can approximate this, but they can't capture all the interactions).
2. This brings us to modelling at the atomic level. To model a system of atoms with the Schrödinger equation, it naively scales O(6^n) per particle. Note that means every nucleus and electron, so if you have say 10 carbon atoms and 22 hydrogen you're already at 10^127 operations. We can cut corners a bit and end up with something like CCSD which scales O(n^7), or cut more corners and scale O(n^3) for DFT. DFT is pretty much the last method where bond forming and breaking is modelled, so after more corner cutting you lose losing reactions, which are important for understanding why something is happening. Most protein folding simulations (moreso prior to alphafold) run a very crude approximation that models atoms as balls on springs (things like AMBER and CHARMM), which obviously can't handle reactions.
3. If this wasn't bad enough, you also can only move through time at about 1 femtosecond (10^-15), so it takes a ton of simulation steps to get even a nanosecond in. Forget millisecond or second lengths where things start to happen.
So, while the math of the physics exists, computationally it's practically intractible. There's some exciting work with something called Machine Learning Interatomic Potentials (MLIP) which approximate DFT using a neural network which are about 1000x faster than DFT, and iirc scale much more linearly (look at things like MACE and orbmol if you're curious). So we're making progress, but we've gone from so ridiculously impossible to pretty much impossible for large systems.
I have a couple ideas about developing custom microchips to make this faster, which is why I'm pursuing this, but there's still a massive way to go!
Systems sciences are ones where each scale has lots of things with unique properties. If you think of “biological things between 2-4m” the amount of unique objects with unique properties and unique interactions is absolutely mind boggling. These sciences generally do not lend themselves to clean highly parsimonious models. The best you can do is coarse-grain a thing as a system (some very roughly defined set of interactions between different things) with certain behavior while accepting that you are losing enormous amounts of predictive power.
I suspect AI will remain worse at systems sciences for a long time because the “possible space” of models for a particular system is much larger than in the reductionist sciences and navigating it takes a human taste and instinct that LLMs don’t seem to have (yet).
I don't think LLMs will just magically be able to connect all the dots, because "garbage in, garbage out" still applies. And there's just too many invisible intermediate states, there is literally just not enough information to fully constrain a model. Hence my interest in scaling computational chemistry to get these intermediates :)
Is there anything like a getting-started for working with MACE or orbmol, a 'hello world'? Like maybe simulating Allolactose binding to lac1 ?
1. The first thing you need to do is start with some atomic structure. You can often find pre-existing pieces (through websites like pubchem), but you need to cobble them together. I use chemcraft and gaussview for this, but those are paid options. I've heard good things about the FOSS program Avogadro though.
2. Once you've built the structure of interest, you want to calculate properties of it. Note that we only infrequently simulate the atom's movement, since that's quite expensive. There's a lot of techniques that let us get the most bang for buck, like calculating transition states, or states of lowest energy which we call intermediates, or running something called an IRC, which follows the molecule to its lowest energy point (note we pretty much always think about these things in terms of energy). The traditional programs I use for this are Gaussian and ORCA (ORCA is free but you do have to create an account on their forum). Newer methods include MACE and orbmol, which are pretty much only used for trajectories (e.g. running through time) as far as I know. This newer crop of programs are much more FOSS, but they aren't as rigorous so my lab uses them only as a "rough draft". I pulled in one of my current notebooks if you're curious to try it out: https://github.com/smj-edison/qc-tools/blob/main/examples/ml...
3. Interpreting results/debugging problems. This is currently done in my workflow using a python script to extract values from the job runfiles (oh yeah, did I mention the terrible DX? A lot of this stuff is done by hand-writing a job text file and then using regex to parse the logfile). We do a lot of analysis based on relative energies (this is something called transition state theory of reactions).
I definitely glossed over a lot of details, but this is long enough as is. Definitely let me know if you have questions! If you do want a "hello world" though, I'd definitely check out the notebook I linked to. You'll have to create a file called "start.xyz" with some sort of chemistry program (or use AI to pull one for you), and then you can run the system through time. I would use a system I'm researching right now, but I'm not sure what our lab's policy is on broadcasting things to the world.
With that said part of the reason some domains may not have robust cheap verifiers is because they’re difficult to produce already, so it may be a bigger lift.
You've got to procure, use and dispose of a ton of equipment. And it all costs a good amount of money.
AI has dominion over the digital world, when it can verify things in Lean it's able to crush problems like they're a game of Go.
But when the real world and digital world don't quite connect AI is bottlenecked.
Obviously it's easy to understand why having strong abilities in maths and coding can help with solving problems in physics. But it's also true of knowledge and mental models more broadly.
For example, say somehow you managed to train a frontier model without any data about elephants. If you did this it would be relatively easy to later train elephants into the weights. You'd basically just need to train it about elephants at a very superficial level. After all, it it already knows what a mammal is. It knows what legs are. It knows what eyes are. It understands how it's digestive system works. All the things that makes the biology of elephants difficult doesn't need to be learnt from scratch.
I assure you people on HN will be surprised at how quickly frontier models will become competent in domains that are harder to RL. They won't need anywhere near as much data as people currently believe.
>We give a deterministic algorithm for exactly counting the satisfying assignments of an arbitrary k-CNF formula [in superpolynomial but subexponential time]
I've got some reading to do it seems...
The actual exponent OpenAI found was x/sqrt(x).
> The Exponential Time Hypothesis is false
The outside implication for what is going on is that OpenAI has very clearly demonstrated insane capability in coming up with clever algorithms. You cannot deny some real level of super human like abstract reasoning here.
K-sat is the hard theoretical computer science problem. Nothing else is close in terms of how much it has been studied. There are journals and conferences for SAT.
It is really hard to come up with faster ways to solve it. So much so that people were convinced that you really can't go faster than exponential time. OpenAI has just shown a breakthrough construction better then decades of research by elite specialists was able to come up with.
Proof is at https://github.com/openai/math/tree/main/lean/OAI/Algorithms...
looks like the real proof is in this file
>Our models produced a natural language proof for Yang–Mills existence on September 9th, 2026
And presumably they are just missing the "mass gap" part of it.
Very clearly these were the results of taking big swings at all millenium prize problems.
Nicolas Le Roux, a Lagrange Prize winner / prof / strong mathematician, turned me onto that around the time I finished my PhD in ML last year. I have been thinking about it a lot, lately, for obvious reasons.
At first, it felt silly to grapple with what science is only after finishing a PhD. This publication from OpenAI finally pushed me over the line to publishing an essay about this struggle between AI science and human science: https://news.ycombinator.com/item?id=50253759
(Never would mean AI will be used in future labs like a fancy calculator, but not much more changes)
Also, fwiw I have a personal test problem I give to every frontier model on release, which is to ask it to final a realatively obvious solution (in hindsight) to a minorly important open problem in my field. I know the answer, but havent gotten around to writing it up yet (it's really not that important). Every frontier model (so far) just regurgitates existing solutions.
Edit: to be clear, I completely believe your experience - just pointing out that it might be interesting for you to actually “try” to solve it thoroughly with the tools, though it is obviously hard to do that in a fair way when you know the solution.
I think the solution is easy enough that any competent colleague would come up with it. Some variant on it has probably even been published (hence why I'm not chomping at the bit to publish). I think it comes down to the models being extremely spiky, and the problems they're trying to solve being easily verifiable in code.
However current frontier models got good enough at websearch and thinking through the problem, that they can finally piece together the answer from my own public writing (eg on stackoverflow). And recently someone wrote up an answer to the problem and put it on Arxiv.
Fission hasn't exactly taken the world by storm.
There are a few nice advantages fusion has, but they are more important once we want to reach the stars as far as I can tell; not this century on this planet.
But I'm just an armchair analyst. You probably have a much better understanding.
I just find it to be an interesting problem! My hope is it happens before I die. My rule of thumb is anyone who says energy on the grid in < 10 years is a blatant liar.
So effectively, you would spend the first 1000 experiments inside a computer simulation and move to the physical world only when you had enough confidence.
But agents are really useful for doing some of the really boring stuff, like convergence checks or setting up meshes or whatever.
..or can we?
Humour me for a moment. Maybe simulating to the degree that was necessary for cutting edge work was not possible earlier, when humans had to program each and every thing in the system that could affect the result. But with current gen petaflop-on-your-desk level compute + swarms of agents that can work tirelessly to account for every known thing to humanity, maybe the threshold has been pushed far enough to produce some more meaningful discovery work in simulation?
I wonder how many of those founder at the "paper" to formalization step, or at earlier or later steps (e.g., proof doesn't turn out to prove what the paper said, hits a bug in the kernel, etc.).
Also, goes without saying, but put Sam Altman in jail, obviously.
I'm kinda hoping they are investing just as much into that type of research. Its their money but man... I'd say 999/1000 people are unaffected by all these breakthroughs. They probably have no idea tons of legendary math/CS conjectures were proven true/false. If a breakthrough in cancer research were to be made, it would very quickly start effecting everyone on earth.
I use these latest available public models daily in max effort modes, and they barely seem to work and need extreme guidance and as much context and constraints as possible.
I find that unless the outcome I'm looking for from the model is almost binary and easily verifiable, it is basically faster to do the work myself.
Assumptions made by the models multiply and by the non-deterministic nature (dbf, similar to work by humans) I'll have something end up light years away from where it should be. During a normal workflow, I have to contend with every line I write forcing a very tight feedback loop... I suppose I could also sit there and spend 9 hours writing out a "perfect spec" but we've already tried that with waterfall development!
So, not sure if its the models, rather the class of problems I'm applying them to... but it is a bit ironic they are allegedly able to solve these conjectures but not stop to ask about assumptions.
2. We dont have the actual frontier models
It feels a bit like having "visited" a place because you had a layover there.
We should remember that math exists primarily to serve a purpose and that purpose is not being a fun puzzle hobby for a select few mathematicians.
Imagine a programmer telling their boss it’s not about working software it’s about the journey of writing the code. Good luck getting hired.
I think if pro mathematicians don’t change their tune quickly they will soon see their funding approach zero.
We chase open problems for the sake of it, and others sometimes support us in doing so because the paths we pave along the way end up being useful for them for adjacent purposes. If you get the answer for free, you might have scratched the itch, but nothing was built for others to use, no fodder was found for the next great question.
Nobody pays mathematicians for solving famous problems. Famous problems are how mathematicians orient themselves while they do the other things that they're paid for (maintaining a useful community, mostly). All this does is deprive them of a navigational tool.
Your formulation is a little bit exaggerated, but I (and many, though far from all, programmers) would agree with the following more "tame" formulation:
Getting software to solve a business problem in an elegant and maintainable way means that we got the abstractions right. Similarly, if a software can easily and elegantly be modified to cope with new business problems, it is also a strong sign that we got the abstractions right. In this sense, the business problems that the software solves are indeed just waypoints on the journey of finding the proper elegant abstractions for putting the business problems into code.
Turning these novel insights about "good" abstractions into code and programming languages enables the team to iterate faster and generate business value faster. So, appreciating that it indeed all about the journey means a commitment towards an approach to accelerate the rate with which the team can turn business insights into code and code into business value.
I know that many managers do hate such a formulation, but I stand behind it.
Often a problem is important because we have no idea how to solve it, which means we need to develop new machinery to solve it. That new machinery can then be used to do things we couldn't do before. Stimulating the development of that machinery is the most important part of the problem.
You should remember that mathematicians and programmers working for a company have different jobs with very different goals.
Thinking in such a utilitarian way feels like a flavor of Meditations on Moloch.[1] Just look at how short-term, quarter-to-quarter thinking is affecting the economy and the lived experience of every human on earth. It’s horrible.
[1] https://slatestarcodex.com/2014/07/30/meditations-on-moloch/
If you refer to RSA or Diffie-Hellman: the number theory that it is based on is from 17th to at most 19th century, i.e. it precedes modern number theory.
I do consider modern number theory to be fascinating and do claim that many results from it could have huge applications in society, but the argument that parts of modern asymmetric cryptography is based on number theory is rather an argument that we don't need any number theory research anymore because these insanely old results that are used in cryptography have already been known for centuries - so no new research is necessary. :-(
Honestly I can't believe I even need to state this. Its literally how science works..
Many of the OpenAI results can be made human-understandable, so it's better than the four-color theorem example.
But to give a brief answer to your question directly: In my view, and I think many if they really thought about it, the point of life is to overcome. If there is an AI that spits out the answer to questions that don’t directly impact human wellbeing instead of letting humans explore the answer at our own pace, we should question whether that AI is worth keeping around or at least relying on too much.
Obviously the question is more nuanced when it comes to math, because even pure math can have applications to understanding reality and improving human wellbeing.
So the question then becomes what do we do with the AI when it can both improve our wellbeing and remove meaning from our lives? Is a life without struggle worth a life without meaning? Personally I don’t think so, so I think we have to optimize all of the benefits of AI while essentially taking a harsh stance against all the harms. Currently the main harm is to education, and that’s why I think we should question and probably even disallow its use by students still working to demonstrate their skills.
Let's say it's possible to know an alien civilization exists 100 million light years away from their waste heat. But that's all we know and it's unlikely we'll ever interact with them.
Was the question of whether we're alone still "valuable"? Wouldn't a lot of philosophy and even some physics fail to meet your definition of valuable?
Imagine the next version of Claude Code or Codex no longer hands you source code and instead turns a natural language prompt directly into a compiled binary that passes the test suite. Would this programmer's boss ship the binary straight to production and dispense with the company's git repo altogether? After all, the goal at the end of the day is shipped software that produces value, not human-readable source code.
Turn this loose on LHC data ASAP.
(Elliot Glazer seems in general to be a pretty good source to follow, however he does that...)
> I occasionally talk to experts on all the MP's. Their rough summaries on what is needed to solve them usually go:
> Hodge: not a clue
> BSD: not a clue
> RH: not a clue
> P vs NP: not a clue
> Yang-Mills: "Well..."