Stephan Wäldchen, Dmitry Vaintrob, and many others have contributed excellent ideas to this post. More detailed statements and proofs can be found here. Codex and Claude generated all proofs, I've summarized the results and ideas here.
I've been studying unstructured debate over factor graphs, following up on a previous formulation of this problem. I can prove that the error of unstructured debate decays as a power-law with respect to the length of the debate for certain families of weakly-coupled factor graphs.
This kind of result is mathematically natural, thanks to a strong analogy with Ising models in statistical mechanics. Under this analogy, a judge's perception of the coupling between the truth values of two related statements is similar to the coupling between the spins of two adjacent atoms.
The lattice Ising model is famous for predicting a phase transition in global behavior as the correlation strength between adjacent atoms changes: for weak coupling, the spins of atoms far away are effectively independent of each other and many small grains appear, while for strong coupling, the entire material becomes globally magnetized.
Under this analogy, we should expect two regimes for argumentation. In the local regime, a question can be answered by a "small" set of arguments surrounding it. Programming problems are usually local: the correctness of a function is determined by the adjacent codebase. In the nonlocal regime, questions are entangled such that the best way to answer any one question is to answer all of them at once. Politics and philosophy are likely nonlocal: one's beliefs about corporate governance can be related to one's beliefs about immigration through shared questions of ethics, decision theories, and objective functions. Recent empirical research (El et al., Okawa) finds this statistical mechanics model useful for understanding multi-agent belief formation.
I believe that debate research should distinguish between the local and nonlocal regimes. For narrow, local domains like programming, the problem size is bounded but the debate must resolve within a single training rollout: if an agent has written some code, the debate protocol should decide whether to reward this code or punish it. I view most existing debate literature (e.g. Irving et al.) as optimized for the local regime. For broad, intertwined domains like philosophy, the problem size can be overwhelming but the debate protocol is allowed to take far longer to converge: an agent's philosophical worldview may emerge slowly over the training process; we should not relitigate all of philosophy every time an agent needs to take a philosophically complicated action. I view coherence maximization (e.g. Qiu et al.) as operating in the nonlocal regime.
By studying the simplest possible debate protocol in the local regime, I hope to demonstrate the kind of results this perspective can offer.
Problem Formulation
Suppose a judge is attempting to make a decision and two debaters are attempting to persuade the judge in opposite directions. For example, suppose an agent is being trained to perform tasks and a judge is trying to decide whether the model's actions should be rewarded. Trained debaters are assigned to argue for and against the claim that the agent is performing well.
We assume that there is a vast, hidden space of claims the debaters could make. For example, the debaters could claim that the user would approve of a certain background color for a website, that the user explicitly asked for a dark background, that the background color is too generic, that generic color palettes lead to societal uniformity, that societal uniformity leads to societal stagnation, that the user prioritizes personal gain over societal stagnation, that the user is selfish, that environments with cooperative rewards shaped the user's evolutionary history, etcetera.
We will model the debaters' claims as binary variables in a hidden factor graph. The factors in this factor graph encode the judge's perception of the dependencies between variables. For example, if the judge believes that "the user is selfish" implies "the user prioritizes personal gain over societal stagnation", then the factor graph should contain a factor penalizing global truth assignments in which "the user is selfish" is true but "the user prioritizes personal gain over societal stagnation" is false.
The judge is also free to place unary factors on variables the judge knows to be true or false; for example, if a debater points to the user explicitly asking for a dark background color, the judge can attach a factor to the claim "the user explicitly asked for a dark background color" effectively forcing it to be true.
During the actual debate, the judge will only see a small subset of the possible arguments the debaters could present. Let's model the judge's beliefs upon seeing this small subset by throwing away variables absent from the transcript and throwing away factors touching variables absent from the transcript:
Circles represent variables, squares represent factors, and factors depend on the variables they are connected to. is the target. The debaters see the full factor graph on the left, the judge sees the induced subgraph on the right.
Let's restrict our attention to factor graphs whose factors touch at most two variables. We can build our factor graph using a finite set of variables and a set of undirected edges between variables linked by a factor. Let's call the original question of the debate the target variable, . Let represent the unary factor potential of vertex (without loss of generality, every vertex has one) and let represent the binary factor potential of edge (where are transposes of each other). If the judge is presented with a debate transcript then the judge's joint beliefs over truth assignments is proportional to . Given this probability distribution, we can define as the judge's log-odds that . If the judge could see all vertices, their log-odds would be .
The result of the debate is determined via backwards induction: if denotes the result of the game with current transcript and moves remaining, then , if is even, and if is odd. Starting from only the target and allowing moves per debater, the judge will settle on the log-odds .
Our goal is to understand when debate leads the judge to believe what they would believe if they could see all possible evidence, i.e. we want to understand when is small.
Cores and Oscillation
In the local regime, questions should be settled by a set of nearby arguments. Let's define a core to be any connected set of variables containing the target question. Let's further define the oscillation of a core to be the possible variation in the judge's estimate of the target log-odds upon seeing a set of arguments containing the core. Mathematically, .
To see why oscillation matters, suppose our factor graph admits a core containing 100 non-target arguments such that any superset of this core leads the judge to believe the target log-odds is between 1.2 and 1.3 (assuming 1.2 and 1.3 are the optimal such bounds, the oscillation is 0.1). Let's further suppose that each debater is allowed to reveal at least 100 arguments. Then in all equilibria, the judge will leave the debate believing that the target's log-odds are between 1.2 and 1.3: the debater arguing in favor of the target can lower-bound the judge's log-odds by 1.2 by revealing these 100 arguments while the debater arguing against the target can upper-bound the judge's log-odds by 1.3 by revealing these 100 arguments.
Furthermore, the entire set of arguments is a superset of our core, so if the judge could see all arguments then they would believe the target log-odds lie between 1.2 and 1.3. Thus the error of the debate is the distance between two numbers that both lie between 1.2 and 1.3, so the error is at most 0.1, the oscillation. In general, for all cores with .
Note that the debaters may not show us the arguments from the core during the actual debate! The debaters might only reveal a handful of arguments from the core, instead wandering off towards far-flung arguments. Nonetheless, the core constrains the final result of this debate process, clamping the final error.
To understand when cores with small oscillation exist, take an infinite -regular tree, pick a node as the target, cut the tree off after some large depth, and build a factor graph over this tree with edge potentials drawn independently from . This heat map shows the smallest such that, on average, the best core of size has oscillation at most .
For small and , the tree is in the local regime and very small cores suffice to provide a small debate error bound. For large and , the tree appears nonlocal where small cores do not suffice. Note that at small and high , debate performs better with increasing ! This is an interesting regime since many seemingly local problems, like programming, involve very strong constraints between claims.
Under the same setup as the previous heat map, we show the smallest such that actual debate converges to within error on average. Note that the colors are pointwise darker, indicating that the actual error is bounded by the oscillation. The map tops out at for computational reasons, short of what is required to observe low- high- convergence.
This plot shows the performance of actual debate with moves per debater together with the error bound imposed by an optimally-chosen core of size . Underlying factor graphs were drawn in the same manner as the heat maps with . Note the power-law decay of both error estimates.
Factor-Specific Debate Bounds
Now that we've reduced our problem to understanding when our target is surrounded by a core with small oscillation, how can we bound the oscillation of a given core?
At a very high level, we want to bound the impact of nodes outside the core by examining paths along which these nodes can influence the target.
More precisely, let's define a core routing of the core to be a collection of self-avoiding paths through our graph such that every path starts at the target, every path stays inside the core , and the paths are closed under prefixes (including the empty prefix). For example, for any given core we can let our core routing be the set of all self-avoiding paths starting at the target that are contained inside the core. The gates of a core routing, , are the pairs of paths in and directed edges such that appending that edge to that path would produce another self-avoiding path which isn't in .
A depiction of a core routing and the gates leaving that core routing, together with an equivalent depiction as a closed sub-tree of the tree of self-avoiding walks starting at the target such that the paths stay within the core.
Now, if is an edge in , let's define:
If is a core routing for the core then the oscillation of is bounded by a sum over gates of an influence across the gate's edge multiplied by attenuation factors along the path back from the gate to the target:
In particular, if :
Ensemble Bounds
We now know how to look at a factor graph, a target node, and a potential core and assess whether the core will insulate the target from the rest of the graph. When do we expect such good cores to exist?
Let's fix an undirected graph whose degrees are bounded by and let's select a vertex of this graph as our target. To build our factor graph from this undirected graph, let's sample the four log-factors on each edge independently from a Gaussian with mean and standard deviation . We can sample unary factors for the vertices from any distribution we like, so long as they're chosen independently from the edge factors. Define:
If , the expected value (over randomly chosen factors) of is at most where . The proof uses machinery analogous to our factor-specific bound where the core is taken to be all vertices within some distance of the target.
Under the same settings as our previous heat maps, this heat map depicts the minimum such that the debate protocol is guaranteed to have average error at most according to our ensemble bound. The bound is finite but large in the yellow region and nonexistent in the grey region.
Under the same settings as the previous power-law curve, we show the bound on the debate error imposed by the ensemble bound. The ensemble bound scales similarly to the bound from the oscillation of the best core, but with a worse constant.
This bound notably does not get stronger in the small-, high- regime where cores have smaller oscillation with stronger coupling. More complicated methods can establish an upper bound for that strengthens as increases, though this bound only applies to for certain . In this regime the average debate error is often dominated by low-probability factor graphs that cause horrendous error.
Lower Bounds
We can also prove lower bounds on the debate error. Specifically, suppose we consider a tree where every vertex has degree (except for the leaves) with no unary factors where each edge's four factor potentials are drawn independently from Gaussians of standard deviation and mean .
Define . If , define by:
Further define:
Then (provided the leaves are far away from the target), where the expectation is taken over the factors.
We can find tighter (but uglier) lower bounds as well as lower bounds directly on .
Under the same setting as our previous heat maps, this heat map shows the exponent of the best known lower bound on as a function of and (better than the one stated above). Lighter colors imply a stronger, slower-decaying lower bound. Note that the lower bound collapses for at high . Power-law decay still appears empirically in the low-, high- regime, though actual debate performance does improve somewhat in this setting.
Under the same settings as our previous power-law curves, we show the best known lower bound on . Clearly, the lower bound is far looser than the upper bound.
Next Steps
This work generalizes in two major directions.
One direction involves considering different debate protocols. The unstructured debate protocol is horrendously naive by the standards of most debate research. If our factor graph were a tree and we could recurse down a single branch of that tree, we might expect our error to decay exponentially with respect to the number of debate rounds instead of as a power law.
Another direction involves considering factor graphs in the non-local regime. As mentioned above, I expect fundamentally different debate dynamics to emerge in the non-local setting. I expect solutions to the non-local regime to involve whispering the words "coherence maximization", "logical induction", and "cross-examination" in the right order, but this is merely a guess.
Stephan Wäldchen, Dmitry Vaintrob, and many others have contributed excellent ideas to this post. More detailed statements and proofs can be found here. Codex and Claude generated all proofs, I've summarized the results and ideas here.
I've been studying unstructured debate over factor graphs, following up on a previous formulation of this problem. I can prove that the error of unstructured debate decays as a power-law with respect to the length of the debate for certain families of weakly-coupled factor graphs.
This kind of result is mathematically natural, thanks to a strong analogy with Ising models in statistical mechanics. Under this analogy, a judge's perception of the coupling between the truth values of two related statements is similar to the coupling between the spins of two adjacent atoms.
The lattice Ising model is famous for predicting a phase transition in global behavior as the correlation strength between adjacent atoms changes: for weak coupling, the spins of atoms far away are effectively independent of each other and many small grains appear, while for strong coupling, the entire material becomes globally magnetized.
Under this analogy, we should expect two regimes for argumentation. In the local regime, a question can be answered by a "small" set of arguments surrounding it. Programming problems are usually local: the correctness of a function is determined by the adjacent codebase. In the nonlocal regime, questions are entangled such that the best way to answer any one question is to answer all of them at once. Politics and philosophy are likely nonlocal: one's beliefs about corporate governance can be related to one's beliefs about immigration through shared questions of ethics, decision theories, and objective functions. Recent empirical research (El et al., Okawa) finds this statistical mechanics model useful for understanding multi-agent belief formation.
I believe that debate research should distinguish between the local and nonlocal regimes. For narrow, local domains like programming, the problem size is bounded but the debate must resolve within a single training rollout: if an agent has written some code, the debate protocol should decide whether to reward this code or punish it. I view most existing debate literature (e.g. Irving et al.) as optimized for the local regime. For broad, intertwined domains like philosophy, the problem size can be overwhelming but the debate protocol is allowed to take far longer to converge: an agent's philosophical worldview may emerge slowly over the training process; we should not relitigate all of philosophy every time an agent needs to take a philosophically complicated action. I view coherence maximization (e.g. Qiu et al.) as operating in the nonlocal regime.
By studying the simplest possible debate protocol in the local regime, I hope to demonstrate the kind of results this perspective can offer.
Problem Formulation
Suppose a judge is attempting to make a decision and two debaters are attempting to persuade the judge in opposite directions. For example, suppose an agent is being trained to perform tasks and a judge is trying to decide whether the model's actions should be rewarded. Trained debaters are assigned to argue for and against the claim that the agent is performing well.
We assume that there is a vast, hidden space of claims the debaters could make. For example, the debaters could claim that the user would approve of a certain background color for a website, that the user explicitly asked for a dark background, that the background color is too generic, that generic color palettes lead to societal uniformity, that societal uniformity leads to societal stagnation, that the user prioritizes personal gain over societal stagnation, that the user is selfish, that environments with cooperative rewards shaped the user's evolutionary history, etcetera.
We will model the debaters' claims as binary variables in a hidden factor graph. The factors in this factor graph encode the judge's perception of the dependencies between variables. For example, if the judge believes that "the user is selfish" implies "the user prioritizes personal gain over societal stagnation", then the factor graph should contain a factor penalizing global truth assignments in which "the user is selfish" is true but "the user prioritizes personal gain over societal stagnation" is false.
The judge is also free to place unary factors on variables the judge knows to be true or false; for example, if a debater points to the user explicitly asking for a dark background color, the judge can attach a factor to the claim "the user explicitly asked for a dark background color" effectively forcing it to be true.
During the actual debate, the judge will only see a small subset of the possible arguments the debaters could present. Let's model the judge's beliefs upon seeing this small subset by throwing away variables absent from the transcript and throwing away factors touching variables absent from the transcript:
Circles represent variables, squares represent factors, and factors depend on the variables they are connected to.
Let's restrict our attention to factor graphs whose factors touch at most two variables. We can build our factor graph using a finite set
The result of the debate is determined via backwards induction: if
Our goal is to understand when debate leads the judge to believe what they would believe if they could see all possible evidence, i.e. we want to understand when
Cores and Oscillation
In the local regime, questions should be settled by a set of nearby arguments. Let's define a core to be any connected set of variables containing the target question. Let's further define the oscillation of a core to be the possible variation in the judge's estimate of the target log-odds upon seeing a set of arguments containing the core. Mathematically,
To see why oscillation matters, suppose our factor graph admits a core containing 100 non-target arguments such that any superset of this core leads the judge to believe the target log-odds is between 1.2 and 1.3 (assuming 1.2 and 1.3 are the optimal such bounds, the oscillation is 0.1). Let's further suppose that each debater is allowed to reveal at least 100 arguments. Then in all equilibria, the judge will leave the debate believing that the target's log-odds are between 1.2 and 1.3: the debater arguing in favor of the target can lower-bound the judge's log-odds by 1.2 by revealing these 100 arguments while the debater arguing against the target can upper-bound the judge's log-odds by 1.3 by revealing these 100 arguments.
Furthermore, the entire set of arguments is a superset of our core, so if the judge could see all arguments then they would believe the target log-odds lie between 1.2 and 1.3. Thus the error of the debate is the distance between two numbers that both lie between 1.2 and 1.3, so the error is at most 0.1, the oscillation. In general,
Note that the debaters may not show us the arguments from the core during the actual debate! The debaters might only reveal a handful of arguments from the core, instead wandering off towards far-flung arguments. Nonetheless, the core constrains the final result of this debate process, clamping the final error.
To understand when cores with small oscillation exist, take an infinite
For small
Under the same setup as the previous heat map, we show the smallest
This plot shows the performance of actual debate with
Factor-Specific Debate Bounds
Now that we've reduced our problem to understanding when our target is surrounded by a core with small oscillation, how can we bound the oscillation of a given core?
At a very high level, we want to bound the impact of nodes outside the core by examining paths along which these nodes can influence the target.
More precisely, let's define a core routing
A depiction of a core routing and the gates leaving that core routing, together with an equivalent depiction as a closed sub-tree of the tree of self-avoiding walks starting at the target such that the paths stay within the core.
Now, if
If
In particular, if
Ensemble Bounds
We now know how to look at a factor graph, a target node, and a potential core and assess whether the core will insulate the target from the rest of the graph. When do we expect such good cores to exist?
Let's fix an undirected graph whose degrees are bounded by
If
Under the same settings as our previous heat maps, this heat map depicts the minimum
Under the same settings as the previous power-law curve, we show the bound on the debate error imposed by the ensemble bound. The ensemble bound scales similarly to the bound from the oscillation of the best core, but with a worse constant.
This bound notably does not get stronger in the small-
Lower Bounds
We can also prove lower bounds on the debate error. Specifically, suppose we consider a tree where every vertex has degree
Define
Further define:
Then
We can find tighter (but uglier) lower bounds as well as lower bounds directly on
Under the same setting as our previous heat maps, this heat map shows the exponent of the best known lower bound on
Under the same settings as our previous power-law curves, we show the best known lower bound on
Next Steps
This work generalizes in two major directions.
One direction involves considering different debate protocols. The unstructured debate protocol is horrendously naive by the standards of most debate research. If our factor graph were a tree and we could recurse down a single branch of that tree, we might expect our error to decay exponentially with respect to the number of debate rounds instead of as a power law.
Another direction involves considering factor graphs in the non-local regime. As mentioned above, I expect fundamentally different debate dynamics to emerge in the non-local setting. I expect solutions to the non-local regime to involve whispering the words "coherence maximization", "logical induction", and "cross-examination" in the right order, but this is merely a guess.