💻 computer science

Structured Inference with Large Language Gibbs

The paper proposes "Large Language Gibbs," an iterative probabilistic inference method that leverages an LLM's conditional distributions as transition operators to resample variables, thereby overcoming the order-dependent biases of single-pass autoregressive generation to achieve coherent structured reasoning.

Original authors: Sanghyeok Choi, Henry Gouk, Esmeralda S. Whitammer

Published 2026-06-19

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Sanghyeok Choi, Henry Gouk, Esmeralda S. Whitammer

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very smart, well-read librarian (the Large Language Model, or LLM) who knows a huge amount about the world. You ask this librarian to create a list of facts about a complex situation, like describing a cat's breed, coat, age, and sleep habits all at once.

The Problem: The "One-Shot" Mistake
Usually, when we ask an LLM to do this, we ask it to write the whole list from left to right in one go. The paper argues this is like asking a chef to cook a whole meal without tasting anything until the very end. Because the chef has to decide the first dish before knowing the last, they might make a choice early on that forces the rest of the meal to be weird just to fit. In the paper's terms, this creates "order-dependent biases." If you ask the librarian to list the cat's age first, then breed, the answer for the breed might be subtly skewed by how the age was written, even if age and breed shouldn't really affect each other.

The Solution: "Large Language Gibbs" (The "Edit-and-Refine" Method)
The authors propose a new way to use the librarian called Large Language Gibbs. Instead of asking for the whole list at once, they treat the list like a group of friends sitting around a table, and they take turns asking each friend to rethink their answer based on what everyone else just said.

Here is how it works, using a simple analogy:

The Setup: Imagine you have a group of variables (like the cat's Breed, Coat, Age, and Sleep). You start with a random guess for all of them.
The Round-Robin: Instead of writing the whole story, you pick one variable at random (say, "Coat"). You tell the librarian: "Everyone else has decided on these values (Breed is 'Shorthair', Age is 3, Sleep is 12 hours). Given these specific facts, what is the most likely coat?"
The Shuffle: Crucially, you don't ask about the variables in the same order every time. Sometimes you ask about Age first, sometimes Coat. This prevents the librarian from getting stuck in a specific "habit" of answering.
The Loop: You repeat this process many times. Every time you update one variable, you use the new information to update the next one.
The Result: Eventually, the whole group of answers settles into a state where everything makes sense together. The paper calls this a "stationary distribution." It's like a group of friends arguing until they all agree on a story that feels perfectly consistent, rather than a story that just happened to start with a specific sentence.

Why is this better?
The paper shows that this "edit-and-refine" method fixes two big problems:

Bias: It stops the model from favoring answers just because they appeared early in the list.
Inconsistency: It helps the model realize that if "Polaris" is the North Star, then "Sirius" cannot be the brightest star at the same time. By shuffling the questions, the model can correct its own mistakes.

Real-World Tests in the Paper
The authors tested this idea in three specific ways:

Random Number Generation: They asked the model to pick random numbers (like rolling a die). The old way (one-shot) was bad at picking numbers evenly. The new "Gibbs" way was much better at picking numbers that looked truly random and independent.
Consistent Reasoning: They gave the model a set of questions where the answers needed to agree with each other (e.g., "Is the North Star the brightest?" and "Is Sirius the brightest?"). The new method helped the model give answers that didn't contradict itself, performing better than just asking the questions one by one.
Learning from Data: They used the model to generate "fake" data to help scientists figure out how different things are connected (like how tuberculosis treatment relates to patient age). By using the "Gibbs" method to generate this fake data, they got better results than just asking the model to write a fake dataset in one go.

The Bottom Line
The paper suggests that instead of treating an LLM like a machine that just writes a story from start to finish, we should treat it like a tool for iterative refinement. By letting the model constantly check and re-check its own answers against each other in a random order, we get a much more reliable, consistent, and "probabilistically correct" result. It turns the model from a one-time storyteller into a collaborative editor that helps find the truth.

Technical Summary: Structured Inference with Large Language Gibbs

Problem Statement

Large Language Models (LLMs) are increasingly utilized to represent distributions over structured objects, such as label assignments, tabular records, and combinatorial objects. However, accessing the knowledge encoded in LLMs for structured probabilistic inference presents a significant challenge. The standard approach of generating structured objects via single-pass autoregressive decoding introduces order-dependent biases, such as recency effects and context ignorance, which distort the intended joint distribution. Furthermore, LLMs often fail to sample correctly from simple distributions (e.g., uniform or Gaussian) when generating samples independently or in batches, exhibiting either high bias or high autocorrelation. The core problem is how to leverage the conditional beliefs of LLMs over individual variables to extract more information and produce coherent joint samples without the artifacts of fixed generation orders.

Methodology: Large Language Gibbs

The authors propose Large Language Gibbs, a framework for structured probabilistic inference that treats an LLM's conditional distributions as transition operators within a Gibbs sampling scheme. Instead of generating a full object in one pass, the method iteratively resamples individual variables conditioned on the current values of all other variables.

Core Mechanism

The approach defines a Markov chain where the state is a set of variables $X = (X_1, \dots, X_n)$ . At each step, a variable $X_i$ is selected and resampled from an approximate conditional distribution $q_i(X_i | X_{-i})$ derived from the LLM.

1. Basic Large Language Gibbs (Section 3.1):
To define the resampling kernel $q^{LM}_i(X_i | X_{-i})$ , the method addresses the fact that autoregressive LLMs only provide next-token probabilities for a specific sequence order. The authors propose defining the kernel as the expectation of autoregressive kernels under random permutations of the remaining variables:
$q^{LM}_i(X_i | X_{-i}) \triangleq \mathbb{E}_{\sigma_{-i}} \left[ p_{LM}(X_i | \text{seq}(X_{-i}, \sigma_{-i}) \oplus [c_i]) \right]$
where $\sigma_{-i}$ is a random bijection shuffling the other variables, and $c_i$ is the natural language context describing $X_i$ . This random shuffling removes order-dependent biases, aiming for a stationary distribution that reflects a compromise among all local conditionals.

2. Discriminative Kernels (Section 3.2):
Recognizing that LLMs may be better at discrimination than generation (especially after reinforcement learning fine-tuning), the authors introduce two variants that use the LLM's discriminative output to accept or reject candidates:

Barker Gibbs: Uses the LLM to choose between the current value and a candidate value. If the LLM is calibrated according to Barker's rule, the stationary distribution is preserved.
Gambling Gibbs: Frames the acceptance decision as a gamble. The LLM is asked whether it would place a bet on the candidate being more plausible than the current value. This allows the use of greedy decoding (deterministic threshold judgment) rather than relying on calibrated probabilities.

3. Practical Variants (Section 3.3):
The framework supports Sweeping Gibbs (cycling through variables in a fixed order) and Block Gibbs (resampling sets of $B > 1$ variables simultaneously) to improve convergence or escape local modes.

Key Contributions

A New Inference Scheme: The paper introduces Large Language Gibbs, a method that transforms LLMs into transition operators for structured probabilistic inference, moving beyond single-pass autoregressive generation.
Theoretical Analysis: The authors provide a theoretical framework establishing the existence of a unique stationary distribution for the Gibbs chain. They identify a sufficient condition (Assumption 3.1) under which the stationary distribution corresponds to a symmetrized joint distribution of the LLM, demonstrating that random shuffling is essential for removing ordering biases.
Algorithmic Variants: The proposal of Barker and Gambling Gibbs kernels offers alternatives for scenarios where generative probabilities are miscalibrated, leveraging the LLM's discriminative capabilities.
Empirical Validation: The method is applied to three distinct domains:
- Synthetic Distributions: Sampling from uniform and Gaussian distributions.
- Consistent Reasoning: Solving sets of related questions (TruthfulQA, GSM8K) to find coherent answers.
- Bayesian Structure Learning: Using LLM-generated synthetic data to inform priors for causal graph discovery.

Results

The experiments demonstrate that Large Language Gibbs effectively mitigates the limitations of standard LLM sampling:

Simple Distributions: On synthetic tasks (uniform and Gaussian), independent sampling showed high bias, and batch sampling showed high autocorrelation. Gibbs sampling substantially corrected both issues, producing samples with lower bias and lower autocorrelation than baseline methods.
Consistent Reasoning: On TruthfulQA and GSM8K-Verification, iterative conditional updates via Gibbs sampling outperformed zero-shot, single-pass autoregressive, and even Internal Coherence Maximization (ICM) baselines. The results suggest that shuffling variables during resampling leads to better consistency across related questions.
Bayesian Structure Learning: When used to generate synthetic data ( $D_{LLM}$ ) to define a world-knowledge-driven prior, Large Language Gibbs improved structure learning performance (measured by Expected Structural Hamming Distance and AUROC) on real datasets compared to uniform priors and direct autoregressive sampling. The method successfully leveraged metadata to disambiguate causal structures.

Significance and Claims

The paper claims that using LLM conditionals within a Markov Chain Monte Carlo (MCMC) framework is a practical alternative to one-pass generation for structured probabilistic inference. The authors argue that this approach allows for the extraction of more information from the model's internal beliefs than autoregressive generation permits.

The significance lies in providing a principled probabilistic framework for handling the "noisy" conditionals of LLMs. By iteratively resampling and averaging over variable orderings, the method produces a stationary distribution that represents a compromise among local conditionals, effectively removing the bias of any fixed generation order. The authors position this as a step toward treating LLMs as priors within probabilistic programs, particularly for tasks requiring consistency across multiple variables or reasoning steps.

The paper remains modest regarding its limitations, noting that the approach requires more computation than single-pass generation and is currently limited to relatively small models (up to 32B parameters) due to computational constraints. It also acknowledges that the quality of the results depends heavily on the informativeness of the metadata provided to the LLM.