Scoring Agents Against State Evolution: Inference Benchmarks with Known Difficulty Curves

Procedural benchmarks for language models solve contamination by generating fresh problems on demand. They still cannot say how hard a given problem is. Difficulty is set with a rough knob, such as more disks in Tower of Hanoi or a bigger Sudoku grid, and accuracy then collapses at a point nobody predicted. Approximate message passing (AMP) is a fast iterative algorithm for recovering a hidden vector from noisy random measurements. For random high-dimensional problems of this kind, AMP comes with a companion theory called state evolution, a short scalar recursion that predicts in advance the error the best known efficient algorithm will reach at every noise level and sample size. The same theory also marks where recovery becomes impossible in principle, and where it is possible in principle but believed out of reach for any efficient method.

We propose a benchmark of randomly generated statistical inference problems, given to tool-using language model agents. Every instance comes with an analytically predicted optimal error curve. The difficulty knob is continuous and calibrated before any model is run. Agent performance is reported as distance from a theoretical frontier, not as raw accuracy. Because different classical estimators fail at different, known thresholds, the location of an agent's failure also shows which kind of algorithm it is effectively running.

Core Claim

Consider an inverse problem $y = Ax + w$, where $x \in \mathbb{R}^N$ is a hidden sparse signal, $A \in \mathbb{R}^{M \times N}$ is a random measurement matrix, $w$ is Gaussian noise, and $\alpha = M/N$ is the sampling ratio. State evolution predicts the per-coordinate error of Bayes-optimal AMP through the recursion

$$\sigma_{t+1}^2 = \sigma_w^2 + \frac{1}{\alpha}\,\mathrm{mmse}(\sigma_t^2),$$

where $\sigma_t^2$ is the effective noise level at iteration $t$ and $\mathrm{mmse}(\sigma^2)$ is the minimum error of denoising one prior-distributed scalar observed through Gaussian noise of variance $\sigma^2$. This comes from the decoupling result described by Tourneret et al., in which the vector problem reduces to independent scalar problems. The fixed point gives a predicted error curve $E_{\mathrm{AMP}}(\alpha, \mathrm{SNR})$ at negligible cost. The same machinery gives closed-form thresholds for simpler estimators, and a separate information-theoretic threshold below which no method succeeds.

Our claim is that these curves turn a pile of random instances into a calibrated measuring instrument. An agent's empirical error curve can be placed on a phase diagram that has four landmarks. The first is trivial failure, where the agent does no better than guessing the prior mean. The second is least-squares or ridge behaviour. The third is the sparse-regression (LASSO) threshold. The fourth is the AMP frontier. We hypothesize that current agents with code execution sit at one of the classical thresholds, most plausibly ridge or LASSO, rather than at the AMP frontier. We also hypothesize that the failure location is a sharper summary of reasoning quality than accuracy at any single difficulty. Nothing in the file does this. BeyondBench (Srivastava et al.) observes cliffs without predicting them. The physics papers use AMP-tractable models as synthetic benchmarks only for gradient descent and idealized networks (Troiani et al.; Defilippis et al.).

Research Program

The generator has three task families. Each is chosen because its phase diagram is already worked out in the file's sources.

The first family is sparse linear recovery with Bernoulli-Gaussian priors. Here Bayes-AMP, LASSO and ridge have separate, computable thresholds in $(\alpha, \mathrm{SNR})$.

The second is sparse principal component analysis (PCA), meaning recovery of a sparse direction hidden in a noisy matrix. Lesieur et al. showed this problem has discontinuous transitions and a wide "hard" region: the signal is identifiable in principle, but AMP and, conjecturally, all efficient algorithms fail.

The third is compressive phase retrieval, where only the magnitudes of the measurements are observed. PR-GAMP (Compressive Phase Retrieval via GAMP) serves as the reference solver, with its reported $M \ge 2K\log_2(N/K)$ success boundary.

A multi-index family built on the 2-sparse parity threshold $\alpha_c = \pi^2/4 \approx 2.46$ from Troiani et al. is a stretch goal. Its stated guarantee covers first-order methods, and agents need not be first-order.

Each instance is delivered to the agent as data files plus a plain-language description. We use two framings, applied to disjoint instances. One is a bare statistical statement. The other is a disguised scientific scenario, for example a sensor array with a few active sources. The disguised framing tests whether the agent recognizes the structure of the problem, not just whether it can code a solver. Instances are drawn fresh from a seeded generator, so memorizing a test set is impossible. We still audit the framing text with TS-Guessing (Deng et al.).

Two technical pieces must be built and validated first. The first is finite-size calibration. State evolution is asymptotic, so for each family we run AMP at the benchmark sizes, roughly $N$ from 500 to 4000 so that data fits in an agent sandbox. We measure how far the empirical AMP error scatters around the predicted curve and report that band as the frontier's uncertainty. The second is ensemble robustness. We vary how badly conditioned $A$ is, using Vector AMP (Vector Approximate Message Passing) as the reference where plain AMP diverges. This creates instances where the obvious textbook AMP breaks, which separates agents that copy an algorithm from agents that check its assumptions.

Baselines

The naive reference is the estimator that outputs the prior mean. Its normalized error equals the prior variance, and any agent at or near this level on a cell of the phase diagram is scored as failing that cell.

The classical references are ridge regression and LASSO with a cross-validated penalty. For PCA we use a plain spectral estimator, the top eigenvector of the data matrix. All are run on exactly the instances the agents see. These matter most because they are what a competent agent would most likely write. If agents match them, the fingerprinting claim is confirmed. If agents beat them, the benchmark has shown something classical code does not explain.

The strongest existing method is Bayes-optimal AMP or GAMP with the true prior, plus PR-GAMP for phase retrieval. It defines the frontier. PR-GAMP reports an output signal-to-noise ratio of at least 28 dB in all 100 trials on a 65k-pixel image at 30 dB measurement SNR, in 7.3 seconds median (Compressive Phase Retrieval via GAMP). We reproduce this before trusting our own implementation.

For the agents themselves, there is no reported result on Lacuna for LLM agents on AMP-type inference tasks. The nearest reference is BeyondBench Hard Suite accuracy: 71.68% for GPT-5 with tools and 59.41% for GPT-OSS-120B (BeyondBench). We also run a subset of BeyondBench tasks with our agents so rankings on the two benchmarks can be compared.

All agents get the same sandbox, the same token budget, the same wall-clock limit per instance, and identical prompts within a framing.

Beating the design question means showing two things. First, the calibrated difficulty axis predicts an agent's failure location on held-out instance distributions better than raw knobs do. Second, it separates models that tie on BeyondBench accuracy.

The key ablation removes state evolution. We report the identical agent runs against an uncalibrated knob: sparsity count and sample size, set BeyondBench-style, with difficulty ordered heuristically. We ask whether ranking stability across seeds, and the ability to explain failures, degrade.

Why not just…?

Why not just use SAT and constraint-solver generators like BeyondBench? They verify correctness exactly, but they offer no smooth theory of where hardness sits. BeyondBench's cliffs, such as Tower of Hanoi failing beyond 5 disks, are found only after the fact (BeyondBench). They also do not cover noisy, continuous estimation, which is what much scientific analysis actually is. We treat BeyondBench as complementary. The rank-comparison experiment will show whether our benchmark adds information or merely reproduces its ordering. If rankings agree perfectly, our contribution reduces to interpretability.

Why not just score against ground truth and compare to an empirical solver, with no theory? This is the real threat. Running LASSO and AMP numerically on each instance gives most of the reference curve without state evolution. The theory buys three things empirical runs cannot. It certifies the hard region, where no efficient algorithm is expected to succeed, which a solver failing there cannot establish. It provides pre-registered thresholds for predicting failure locations. It turns an agent beating AMP inside that region into a diagnostic: either the agent has found leaked ground truth or seed information, or it has contradicted a conjecture. We will measure how much the analytic curves add beyond empirical AMP runs. If the difference is negligible outside the hard region, we will say so and present the hard-region results as the main contribution.

Why not just have an LLM examiner generate adaptive questions? TreeEval reaches 0.83 Spearman correlation with AlpacaEval 2.0 using about 45 questions (Li et al.). But it depends on LLM judging. On research-level work, judges agree with human experts only 67–83% of the time (LemmaBench). Our scoring is a numerical error against a known signal, so no judge is involved.

Why not just let the agent call an AMP library? We allow it. Knowing that AMP applies, choosing the right prior, estimating noise, and noticing when the matrix breaks AMP's assumptions is exactly the skill being tested. The ill-conditioned-matrix family punishes blind use of a library.

Decisive Checks

The benchmark is validated if four things hold. Empirical AMP errors fall within the finite-size band around the state-evolution curve. Agent failure locations cluster at identifiable classical thresholds, with the fitted threshold stable across seeds. Calibrated-difficulty scores predict agent error on fresh instance distributions with lower error than the heuristic-knob ablation. No agent beats the AMP frontier inside the sparse-PCA hard region by more than finite-size fluctuations. If an agent does beat it there, we audit for leakage before claiming anything else.

It fails if agents' curves are too noisy to locate a threshold, or if the disguised framing collapses all agents to the naive baseline. Either outcome would itself be a finding: even strong agents do not recognize standard inference structure in scientific language.