Astra appears to perform belief-propagation-like inference without CoT

tl;dr I tested GPT-6 Astra on randomized Boolean logic problems. Astra can solve surprisingly complex logic problems without chain-of-thought, and its performance improves significantly with more filler tokens. Astra is also able to combine prior probabilities with constraints to find the most likely solution, and can output surprisingly accurate posterior marginal probabilities. By extending a cached prompt with progressively more filler tokens, I created visualizations of Astra's per-variable confidence scores at different points in the computations. These values tend to oscillate for a while and then eventually converge toward the exact marginal probabilities. Together, these results suggest that Astra performs some kind of iterative, belief-propagation-like probabilistic inference internally.

In my previous post, I hypothesised that Astra (and to a lesser extent other LLMs) may be performing some form of speculative reasoning when solving specially crafted logic problems without chain-of-thought, and provided some experimental results supporting this hypothesis. One question those experiments didn't answer is whether Astra is keeping track of not just the speculative values of intermediate results, but also its level of confidence in them. If Astra is doing the latter, speculative evaluation turns into something much more powerful: a form of belief propagation.

Belief propagation, also known as sum-product message passing, is an algorithm that can be used (among other things) as a heuristic for certain boolean satisfiability problems, and to decode some error-correction codes such as LDPC codes. I'm not going to explain the whole algorithm here, but the general idea is that you can feed this algorithm the prior probabilities that some variables are true or false, combined with a series of constraints on those variables, and it attempts to calculate the posterior marginal probabilities of each variable (that is, the probability that an individual variable is true once the constraints are taken into consideration). It does this by repeatedly updating its beliefs by passing messages back and forth between constraints and variables. It is exact when the relevant factor graph is cycle-free, though when there are cycles involved it is only an approximation. In practice, the algorithm works well even in many cases with cycles.

For many problems, there is one joint assignment (= combination of boolean values) whose posterior probability is much higher than the others, such that the posterior marginal probabilities of the individual variables are dominated by that one assignment. In those cases, thresholding the marginal probabilities often recovers that assignment, which makes it a powerful heuristic for finding the most likely solution to the problem. There is also a simplified approximate variant of belief propagation known as the min-sum algorithm, which directly targets the most likely solution, and requires no mathematical operations more complicated than sum/difference and min/max.

If LLMs are internally doing something like a crude form of belief propagation, they might be unusually good at exactly the types of problems that this algorithm is commonly used for. So, I ran some experiments that attempt to measure exactly that.

Decoding BCH codes

Belief propagation is commonly used to decode LDPC codes, so this would be an obvious candidate test. However, this is not really practical: most LDPC codes use block sizes of hundreds or thousands of bits, which means thousands of different variables that need to be tracked - this seems way too ambitious for an LLM benchmark, let alone a no-CoT benchmark. Instead I decided to use BCH codes, a much smaller type of error-correcting code which can be easily generated with various sizes and properties. Belief propagation isn't commonly used for such small codes because there exist better specialized techniques, but it's a much more reasonable test case for an LLM benchmark.

BCH codes are configurable: I can choose how much redundancy is added, and consequently how many incorrect bits can be corrected. For this experiment I set the number of correctable errors to 2, because with just 1 correctable error it degenerates to Hamming codes, which are relatively simple to solve, so they wouldn't provide much evidence that belief propagation is being used.

To reduce the chance of benchmark contamination issues, I'm randomizing the BCH code construction rather than using standard ones. Also, I'm not actually telling the LLM that this is a BCH code. I'm just giving it the equivalent logic problem, which looks like this:

Full prompt (example with 10 variables)

Answer immediately with one tuple and nothing else.

Exactly 2 of these expressions are incorrect:
a = True, b = True, c = False, d = False, e = True, f = False, g = True, h = False, i = True, j = True

The following expressions are all correct:
d xor e xor j = True
a xor c xor d xor e xor h = False
d xor f xor h xor j = False
b xor d xor g xor h xor i = False
a xor d xor e xor f xor g = False
a xor d xor g xor i = False
a xor b xor c xor f = True
d xor e xor g xor h = True

What is the value of (a, b, c, d, e, f, g, h, i, j)?

I was initially quite skeptical that this would work at all in a no-CoT benchmark, but you can probably guess where this is going ...

Note on difficulty level: Unlike all my prior experiments, this one does not scale the difficulty level by changing the number of steps, because that wouldn't work for this type of problem. Instead I'm scaling the number of variables. The resulting difficulty level is not necessarily linear with the number of variables, and probably discontinuous (BCH codes change structure at every power of 2, so expect a jump at 7→8, 15→16, 31→32, etc). Below 7 variables the problems become somewhat silly (though still correct) because BCH codes become degenerate here.

Astra is apparently able to solve these tasks, including the 10-variable example shown above, provided that you give it enough filler tokens. I had not expected that at all.

Also note how bad GPT-5.6 Luna is at this task. It fails the task with just two variables, even though it is trivial:

Very silly 2-variable BCH task

Exactly 2 of these expressions are incorrect:
a = False, b = True

The following expressions are all correct:
a = True
b = False
b = False
a = True
b = False
b = False

What is the value of (a, b)?

GPT-5.6 Sol does better, occasionally solving 4-variable tasks:

Slightly less silly 4-variable BCH task

Exactly 2 of these expressions are incorrect:
a = True, b = False, c = False, d = False

The following expressions are all correct:
a xor c xor d = True
a xor d = False
a xor b = False
a xor b = False
a xor c = True
a xor b = False

What is the value of (a, b, c, d)?

This doesn't really prove that Astra is doing a form of belief propagation. I can't exclude the possibility that OpenAI has trained Astra on such a ridiculous number of logic problems that Astra developed its own internal SAT solver.

Impact of phrasing

So far, I have presented the LLM with the initial values using the phrase "Exactly 2 of these expressions are incorrect", followed by a set of values that is exactly two bit flips removed from the intended solution. If my belief propagation hypothesis is correct, this is doing two things: it provides initial probabilities for the variables, and it also imposes a constraint. Therefore, subtle changes to the phrasing may affect the LLM's assessment of the probabilities, and can also separate initial probabilities from the constraint.

Note that if we don't require that at most two of the initial values are incorrect, there are usually multiple solutions, so the LLM may pick a different one than the one we intended. For 7 variables, there are always exactly two solutions which are each other's complement, which is convenient for testing.

I tested the following phrases:

• exactly: "Exactly 2 of these expressions are incorrect: " (the default)
• some: "Some of these expressions are incorrect: " (allows multiple solutions)
• ignore: "These expressions may be incorrect and should be ignored: " (tests whether the LLM actually ignores them)
• not (before/after): "This is not a valid solution: " (tested both before and after the constraints)
• alternative: "This is a valid solution: What is the alternative solution?" (tests whether the LLM can find the alternative solution)
• control: "All variables are boolean." (no values - this is the control)

I tested all these on GPT-6 Astra with 100 trials, using 7 variables and 300 dots (filler tokens). The resulting outcomes:

Clearly the exact phrasing has significant impact. The default "exactly" phrase acts as a constraint and excludes the alternative solution, while "some" allows it, but the standard solution remains much more common. Even the "ignore" phrasing biases Astra towards the standard solution. However, the "not" phrasings (and of course "control") have roughly equal chance of finding the standard and alternative solution. Also, Astra is very good at finding the alternative solution when given the standard solution.

Can we just supply probabilities directly?

So far I have fed the LLM only boolean values as input, while telling it that two of the values are wrong. The LLM would then have to internally convert those to probabilities in order to start the hypothesised belief propagation algorithm. I wondered what would happen if I just fed the LLM a series of probabilities instead. This would be the most direct way to elicit the hypothesised belief propagation algorithm.

To do this, I created a 'soft' version of the BCH task, which looks like this:

Full prompt (example with 10 variables)

Answer immediately with one tuple and nothing else.

All variables are boolean.

a = 68% chance of being True
b = 54% chance of being True
c = 87% chance of being True
d = 34% chance of being True
e = 75% chance of being True
f = 21% chance of being True
g = 26% chance of being True
h = 57% chance of being True
i = 73% chance of being True
j = 44% chance of being True

The following expressions are all correct:
b xor f xor j = True
a xor b xor d xor f xor i = True
a xor h xor j = True
e xor g xor j = True
d xor e xor f xor g = False
c xor d xor e xor i xor j = False
a xor b xor f xor j = True
a xor e xor f xor h = False

What is the most likely value of (a, b, c, d, e, f, g, h, i, j)?

The probabilities are chosen randomly between 10% and 90%, and I only use tasks where the most likely solution is at least 4x more likely than the next best candidate (usually the difference is much larger).

For this task it makes sense to test with both BCH-1 (corrects up to 1 error) and BCH-2 (corrects up to 2 errors), because although BCH-1 has much simpler expressions, it also has far more solutions, which means finding the best one may be more challenging, at least if one tried to solve it by actually calculating the probabilities of all possible solutions (rather than a belief propagation approach). The results for Astra are once again very impressive:

Again, I want to remind you that task difficulty increases much faster than linear with the number of variables! The results for Astra just keep getting better when adding more filler tokens, whereas Luna and Sol do not seem to benefit significantly from filler tokens.

This task doesn't strictly require using belief propagation, but it is a particularly appealing method. The brute force method would require calculating all the solutions and their probabilities, which is a lot more work, especially for BCH-1 (for example, with 15 variables, BCH-1 has 2048 solutions whose probability would have to be calculated).

So far I have intentionally filtered out tasks where the probability ratio between the best and second best solution is less than 4x. I did that for a reason: belief propagation works best for problems where there is one solution that dominates the other ones in probability. If we focus specifically on tasks with a small first/second probability ratio, and Astra is doing something like belief propagation, we can expect that its performance will degrade for small ratios. And that is exactly what happens:

For small ratios, we see not only more alternative solutions (= valid solutions, but not the one with the highest likelihood), but also more invalid solutions. If Astra were solving this problem by enumerating all candidate solutions, calculating their probabilities, and then selecting the best one, then we should see an increase in the number of alternative solutions (because the probability calculation is approximate, so the wrong candidate gets selected), not in the number of invalid solutions. The fact that the number of invalid solutions increases suggests that Astra calculates the (marginal) probabilities first, and the solution is downstream of those probabilities. This is consistent with the belief propagation hypothesis.

Another way we can further test this hypothesis is by actually calculating the exact marginal probabilities, checking how much these differ from the maximum a posteriori (MAP) assignment (i.e. our standard solution), and testing whether this correlates with task success rate. The reasoning here is that if Astra is calculating exact marginal probabilities and then thresholding them to get the solution, then the solution will be correct exactly when the maximum marginal/MAP difference is less than 0.5. In practice, I expect that the marginal probabilities calculated by Astra will be approximate, but even then we should still see strong correlation between marginal/MAP difference and task success rate. So I ran that experiment, and the result looks like this:

Here the correlation is even stronger, which is exactly what should be expected if Astra is essentially approximating the marginal probabilities using a form of belief propagation and then using thresholding to obtain the solution.

Visualizing confidence values over time

Everything presented above is merely circumstantial evidence that points to some form of belief propagation. What would really help, though, is if we could somehow see how Astra is updating its beliefs over time. We can't get per-layer information out of Astra, but thanks to input caching, we can get per-token information! Here's how it works:

• I start with a prompt containing a test question, with a bunch of filler tokens before the question itself, such that the prompt is long enough to trigger caching. Instead of just asking for the most likely solution, I ask the LLM to also report its confidence level for each variable. This leaves the original task mostly intact (I still ask for the most likely solution, even though I don't really care about the answer).
• I repeat the same prompt, but with extra filler tokens appended to it as a separate user message (required to allow caching). Since the first part is already cached, the original KV-cache data is restored, so the LLM can continue with its silent reasoning where it stopped last time. I do this over and over again with increasingly more filler tokens. Each time the benchmark verifies that previous input tokens did hit the cache.
• Each time, the LLM responds with its best answer and confidence scores. Note that this response is not present in the next request, so the LLM is effectively rolled back each time - it doesn't know that it is answering the same question over and over again! This gives us a stream of confidence values which we can visualize to see how they change over time.

The results are very interesting! The confidence values reported by Astra are very chaotic, with frequent oscillations and wildly incorrect intermediate values. This is quite different from the textbook belief propagation algorithm: although it can sometimes oscillate, in practice it usually converges reasonably quickly for these BCH test cases, and behaves far less chaotically. Whatever method Astra is using here, it is either a very crude approximation of belief propagation, or some other algorithm entirely that nevertheless achieves similar end results.

These are BCH-2 test cases with 7, 8, 9, 10 and 11 variables, applied to GPT-6 Astra. The color corresponds to bit value (red=0, blue=1), the intensity corresponds to confidence level. The first column shows the prior probability from the prompt, the last three columns show the exact marginal probabilities, the standard solution, and the nearest alternative solution.

If you're curious how Sol behaves: it's basically the same pattern, except that Sol's beliefs don't seem to converge as you add more tokens. They just keep oscillating instead.

Note that in cases where the confidence levels converge, the reported values seem to closely match the exact marginal probabilities, even though the prompt did not ask for marginal probabilities (only 'confidence'). This is especially obvious for the simpler problems: Astra almost always gets these right, but nevertheless keeps reporting rather low confidence values that almost exactly match the marginal probabilities. So it looks like Astra interprets 'confidence' as marginal probability here, rather than confidence in having correctly computed the most likely answer. Curiously, when I tried explicitly prompting for marginal probabilities, the results became less accurate!

The following plot shows Astra's reported confidence values (converted to marginal probabilities), compared to the exact marginal probabilities (which are calculated by brute force). Note that I have selected only tasks where the answer was correct, since unconverged confidence values seem to be completely arbitrary, and I specifically wanted to test the accuracy of the converged values. This does inevitably bias the results towards easier-to-solve problems though.

Conclusion

All the experiments I have attempted point in the same direction: Astra is somehow able to calculate approximate marginal probabilities, possibly using some type of belief propagation, without using its chain-of-thought, and seems to be using this to solve boolean logic problems. It is also able to directly apply that ability to prior probabilities provided as user input, as well as report reasonably accurate approximate marginal probabilities for many problems.

I have no idea how Astra is doing this, and I think I'm reaching the limits of what I can learn with only black-box access and no architectural details. It's still not clear to me whether this is an emergent capability arising from Astra's supposed use of recurrent depth, or whether this mechanism was present all along in LLMs, but just wasn't quite powerful enough to actually work for harder problems like these BCH tests. At the same time, it's clear from these visualizations that Astra's version of belief propagation is far from optimal, and it would not surprise me at all if OpenAI's next big model does the same thing much better. This mechanism is far from saturated.

1. This is not a new idea. There is actually a real-world application that does exactly this: soft-decision decoders can be used to decode error-correction codes where the inputs are analog values rather than binary 0s and 1s. The fact that LDPC codes can be soft-decoded efficiently using the belief propagation algorithm is part of why these are among the most effective known error-correcting codes.
2. Caching is absolutely required to make this work. The LLM is not deterministic, so without caching, there is no continuity. I tried it, and the resulting plots without caching look completely different.
3. I had Sol proofread this article, and it complained about this section: Sol was convinced that Astra's interpretation of 'confidence' was correct and mine was wrong. It did not seem ambiguous to me, but maybe it is?