> What kind of models are you including here?

The truth tables? Predict zeroth bit in enwik9 from, say, bits of 64 previous bytes. Or multiply two 16 bit numbers and predict bit 16 of the multiplication result.

  > doesn't that mean we're approaching optimality?

Transformers are Markov chains [1]. Somewhere around this fascinating site [2] I read that stateful models have an advantage. Author provided an example, a state machine with two states A and B, where at state A transitions are to state A (output 0) and to state B (output 1) with equal probability and at state B the transition is always to state A and output is always 1.

For this state machine just one bit of memory can make an optimal prediction that ones always go in pairs, whereas Markov chain will approximate this prediction and never reach optimality.

  [1] https://arxiv.org/abs/2410.02724
  [2] https://bactra.org/

Authors used LTL (linear temporal logic) to express, basically, non-reduced non-ordered binary decision diagrams. Or just binary decision diagrams, BDDs.

BDDs are almost guaranteed to have exponential size because they do not employ reduction (sharing of common expressions). Reduced BDDs are more succinct and reduced ordered BDDs are even more succinct.

Also, transformers in the paper are constructed, not trained. Training any model to express some truth table is very hard. They also did not perform comparison with, say, Kolmogorov-Arnold representation, which is also universal approximator.

So this paper is not as deep as one may think it is.

This necessitates some state, most probably, persisted one. Hence, imperativeness.

The most frequently used kind of join is a general relation.

[1] https://github.com/agirish/tpcds/blob/master/query1.sql

Query 1 from TPC-DS creates a multi-column relation by using GROUP BY. Which relation is then partially constrained by different columns from different tables.

Compilers are free to rearrange these accesses if the final result is same as if executed by these ordered microtransactions.

Consider loop fusion, loop splitting and/or loop skewing.

E.g., 6^2 = (223)3 = 2(233).

One of ~22 (ln(2^32)) perfect squares will be a square of perfect prime. Most won't.

  > gradient descent isn't good at combinatorial optimisation.

[1] https://en.wikipedia.org/wiki/Natural_evolution_strategy#Nat...

It requires O(N^4) evaluations to compute Fisher Information Matrix for N-dimensional parameterization of the problem in original formulation. But there are closed form solutions and more economical representations of covariance matrix (LoRA, hehe).

And last, but not least, you need only one hidden layer kept in RAM for inference, but you need all of them (61 for Deepseek models) kept in RAM for computing gradient for one sample.

Training is also done over batches, which increase memory requirements by several orders of magnitude. This is why training needs costly compute.

One of the ways out of this unfortunate situation is to use something like Stochastic Average Gradient Descent [1]. Examples there are mostly concerned with regularized logistic regression, which makes problem more or less convex. Neural networks are inherently non-convex. Still, maybe some ideas from there can be utilized in the context of neural networks, like use of estimated Lipshitz constant to derive curvature and appropriate learning step.

  [1] https://www.cs.ubc.ca/~schmidtm/Courses/540-W19/L12.pdf

PSP/TSP (Personal and Team Software Processes) and RUP (Rational's Uniform Process, to a lesser extent) are very valuable approaches to software engineering. Please, read about them, they are very interesting.

  [1] https://arxiv.org/abs/2410.02724
  [2] https://arxiv.org/abs/2304.15004

  > central concept or software engineering is architecture patterns.

Architecture patterns can be of help in that regard and they also can be very error-prone, as right now I am in the process of removing a bug introduced through misunderstanding of one rather old singleton.

  > As long as the tests pass and the performance doesn't regress...

Agentic vibe coding is not an application of ACL2 theorem prover to anything. Agentic vibe coding is an opposite of it, it will make its way to pass the tests with any means necessary, be it patching the code, the tests, or expected results.

   > it's secure

I have experience where completely unmotivated (due to then ongoing very bad divorce) former Java programmer took a description of CPU for model code generation in Haskell's eDSL and successfully extended it in a month. The model had tricky (at the time) type level programming and type classes with associated types.

  [1] https://github.com/augustss/djinn
  [2] http://lambda-the-ultimate.org/node/1178

  > LLMs have a temperature parameter. At zero temperature they are deterministic: they always choose the most likely next token at each step based on what came before and the model weights, and they will always generate the same output given the same input.

"A value proportional to the reciprocal of β is sometimes referred to as the temperature: β = 1/kT, where k is typically 1 or the Boltzmann constant and T is the temperature. A higher temperature results in a more uniform output distribution (i.e. with higher entropy; it is "more random"), while a lower temperature results in a sharper output distribution, with one value dominating."

"Temperature" in the context of softmax does not change a "winning" token, it changes how much probable (in the sense of softmax distribution) winning token will be. If the winning token is "New York", it will be a winner with temperature close to 0 and with temperature of 1e9.

The actual selection of the random token is done separately by using inputs outside of the softmax distribution, for example, by using random number generator. I believe most of LLM configs have a seed for the random number generator.

More than that, generation of code in most programming languages is done with the more guardrails such as beam search guided by schema, syntax and semantics.

I read that BSV source code is about three times shorter than similar design in Verilog and also has three times smaller defect density (defects per significant line of code). So just by changing the HDL from Verilog to BSV one can have nine (9) times less defects in the design.