Step 8: tool results

read_arxiv_source

{
  "file": "intro3.tex",
  "arxiv_id": "2506.13609"
}

{"ok":true,"arxiv_id":"2506.13609","file":"intro3.tex","kind":"text","text":"\\section{Introduction}\n\nModern machine learning (ML) is fundamentally driven by, and further enables, fast and complex computations. We leverage AI precisely because it allows us to automate and optimize tasks with an efficiency that surpasses human capabilities. This rapid computation, permeating increasingly high-complexity and intelligence tasks, is the engine of progress in countless domains. However, this very strength creates a fundamental tension: the speed and complexity of these computations make exhaustive inspection impossible. Understanding and verifying the internal workings of these powerful AI systems---what's going on ``behind the scenes''---becomes increasingly intractable. This tension directly leads to the critical problem of \\emph{scalable oversight}: how to provide accurate training supervision, such that these powerful, yet opaque, AI systems behave as intended, even when their tasks are too complex for direct human understanding and verification?\n\nEnsuring the reliable and safe operation of advanced AI systems is a central challenge for the field. The potential for unintended consequences arising from misaligned or poorly understood AI behavior requires the development of robust oversight mechanisms in order to provide a training reward signal that accurately reflects human values and intentions. Effective scalable oversight is not merely a desirable feature; it is a foundational requirement for building trustworthy AI that aligns with human intentions and avoids producing systematically undesirable outcomes. Progress in this area is crucial for realizing the full potential of AI while mitigating potential risks.\n\nVarious approaches to scalable oversight have been proposed, including amplification \\citep{christiano2018supervising}, recursive reward modeling \\citep{leike2018scalable}, and AI debate \\citep{irving2018ai}. All of these approaches are based on the intuition that it is possible to amplify the reward signal coming from human judgment by leveraging improving AI capabilities. For the case of AI debate, \\cite{irving2018ai} formalized this intuition in the language of computational complexity theory: they proved that a computationally limited human can accurately judge the correct solution to problems of much larger computational complexity by observing a specifically structured debate between two computationally powerful AIs.\nThe main idea is that the two powerful AI debaters recursively break down a complex problem into simpler sub-problems, eventually terminating in subproblems that are simple enough for the computationally limited human to judge directly.\n\nAs an example, consider the case of training a software-engineering AI system to produce large, complex pull requests. Rather than have a human expert carefully review each pull request during training, one could train the AI system via debate, where the first debater produces the pull request, and the second debater acts as a code reviewer attempting to point out flaws in the produced code. For example, the code-reviewing debater might claim that a particular function returns an incorrect value on a certain input. The coding debater could defend their code by tracing through the function on that input and arguing that the correct value is returned. The code-reviewing debater might then zero-in on a single step of the trace calling a library function, and claim that the library function does not behave as the coding debater has claimed.\nThe coding debater might appeal to the library's documentation to justify their claim, and the code-reviewing debater might respond by claiming that the version of the library in the production environment differs from that documentation.\nAt this point, a human judge can quickly check which of the two debaters is correct about the production library version, without having to read and fully understand the complex pull request.\nHence, the human judge only has to understand a specific, narrow claim about one piece of the code to provide an accurate reward signal.\n\nHowever, a significant vulnerability exists in many recursive approaches, including recursive debate: the \\emph{obfuscated arguments problem} \\citep{barnes2020obfuscated}. In recursive debate, a dishonest debater can \\emph{strategically} decompose an easy problem into difficult, even intractable, subproblems. This renders an honest debater unable to find a flaw in their opponent’s argument even if both debaters know that a flaw exists somewhere. The debate will thus fail to identify the correct answer.   Obfuscation in recursive debate is not merely a theoretical concern; it emerged naturally in prior empirical work \\citep{barnes2020obfuscated}, suggesting obfuscation is a likely \\emph{attractor state} in some settings. \n\n\\cite{brown-cohen24scalable} avoid the issue of obfuscation in debate by doing away with recursion entirely. In this case, an efficient honest debater can always win, but debaters are required to write-out the full human-judgeable argument for the correctness of their claims. To return to the software engineering example, this would mean that the coding debater has to provide complete, detailed documentation of how and why every single piece of the code works, such that any plausible critique by the code-reviewing debater is already answered by the documentation. This is a significant sacrifice relative to recursive debate, which allows the debaters to efficiently and adaptively zoom-in on a small fraction of the full, detailed human-judgeable argument.\n\n\\paragraph{Our Approach.} We introduce \\emph{prover-estimator debate}, a protocol for AI debate that mitigates the obfuscated arguments problem while retaining the efficiency of recursive debate. In prover-estimator debate, the prover (Alice) decomposes a problem into subclaims. The estimator (Bob) has the \\emph{sole} task of assigning probabilities to the prover's subclaims. The prover uses these probabilities to decide which subclaim to recursively debate further. This departs from previous debate protocols, where the opponent selects which subclaim to challenge. We show that Bob can always produce probabilities that are \\emph{indistinguishable from the truth by Alice}, while expending computational effort not too much greater than Alice. Alice cannot therefore (on average) select a subproblem where Bob is non-trivially wrong. However, prover-estimator debate has limitations. Alice’s task becomes harder because Bob can defeat an argument by assigning low probabilities to many subclaims. This rules out certain delicate, yet correct arguments that are highly sensitive to the probabilities assigned to subproblems. We formalize this condition by introducing a \\emph{stability} requirement, \n\\emph{$\\rho$-stability}, which demands that the validity of arguments cannot hinge on arbitrarily small changes in subclaim probabilities\\footnote{An earlier preprint had an error in the main theorem due to an issue with the way stability was defined. At a high level, the corrected definition bounds changes in  marginal probabilities of subclaims, while the original mistaken definition used conditional probabilities. This error was found and fixed by the last three authors.}. We require stability only for usefulness, not safety: even if stability does not hold, an honest estimator can still win against any incorrect argument by a dishonest prover.\n\nTo gain intuition for how prover-estimator debate works, let us return to the pull request example.\nAnyone who has undertaken code review knows that reading code and directly identifying bugs is a difficult task. However, it is often possible to estimate where bugs are likely to occur from the structure of the code, and then to request additional evidence in the form of tests that demonstrate the desired behavior.\nProver-estimator debate in this setting requires Alice to provide reliable test coverage, so that even when Bob is uncertain that any single test provides sufficient evidence that the code is correct, taken together it is still likely that Alice's code exhibits the desired behavior.\nOn the other hand, if Alice has engaged in obfuscation by producing code that fails in a way neither Alice nor Bob can readily identify, then Bob can output low probabilities for Alice's claims, and Alice will not be able to reliably identify any probability as being unreasonable.\n\n\\paragraph{Our Results.} We provide rigorous theoretical guarantees demonstrating that prover-estimator debate, \\emph{combined with the stability requirement}, mitigates the obfuscated arguments problem. Specifically, under reasonable assumptions about the structure of the problems being debated (formalized as \\emph{recursively decomposable problems} and the $\\rho$-stability condition), we show:\n\n\\begin{enumerate}\n    \\item \\textbf{Completeness:} An honest prover, who correctly provides a stable decomposition into solvable subproblems, can always win the debate against any dishonest estimator.\n    \\item \\textbf{Soundness:} An honest estimator can win on average against a dishonest prover, \\emph{even if stability is violated and the subproblems are obfuscated}, using computational effort comparable to their dishonest opponent. \n\\end{enumerate}\n\nThe requirement that it is possible for the prover to provide a stable decomposition is the primary restriction on the class of problems that can be accurately judged by our protocol. That is, there can be problems where the prover can efficiently decompose the original problem into solvable subproblems, but all such efficient decompositions are unstable. In this case, our protocol errs on the side of safety, and rejects the prover's argument. This is necessary for the protocol to succeed, because it cannot distinguish between true and false arguments made via unstable decompositions. Note that all that is required is that the prover is able to find a \\emph{single} stable decomposition to use in the debate. Even if other, unstable decompositions exist, the prover will lose on average when using them, and thus will be incentivized via debate training to select the winning, stable decomposition. Intuitively, the stability condition can be seen as requiring that small changes to marginal probabilities of subclaims should not have large effects on the truth of the original claim. We argue that this is a natural requirement when dealing with fuzzy human judgments, where one should be fundamentally suspicious of arguments that depend very precisely on the composition of many inherently imprecise subclaims.\n\nProver-estimator debate provides a step towards building robust and trustworthy AI systems capable of tackling complex tasks beyond direct human oversight. Our formal notion of argument stability, in particular, clarifies the conditions required to avoid the obfuscated arguments problem and enables more targeted research on overcoming this problem. Our approach also suggests general lessons for designing future debate protocols, including the value of asymmetric debate protocols and explicit uncertainty estimates. This work opens up new avenues for research, both theoretical and empirical, in the pursuit of safe and aligned AI.\n","chars":11215,"total_chars":11215,"offset":0,"truncated":false,"next_offset":null}

read_arxiv_source

{
  "file": "conclusion.tex",
  "arxiv_id": "2506.13609"
}

{"ok":true,"arxiv_id":"2506.13609","file":"conclusion.tex","kind":"text","text":"\\section{Discussion and Open Problems}\n\\input{zoo_diagram.tex}\n\nOur paper presents debate protocols which circumvent the obfuscated arguments problem in recursive debate. Intuitively, this demonstrates that it is possible to design the rules of a debate such that training to win at debate leads to correct behavior of the final trained models in most cases.\nThese theoretical results lead to qualitative recommendations for empirical debate research, which present interesting avenues for future research in both of these directions.\n\n\\paragraph{Theoretical.} \n\\Znote{This part needs to be revised}\\Jnote{Done. What do you think?}\nOur results identify stability as a critical requirement for debate training to succeed, and hence we need to better understand when stability can be achieved, either in theory for interesting classes of problems, or in practice for debates in messy, unformalized settings. On the theoretical side, \\pref{thm:cut-and-choose} requires stability for completeness but not soundness, and thus is safe to use even if one is not confident in stability. \nHowever, it can still be the case that the prover only knows how to produce an unstable decomposition into solvable subproblems, implying that certain problems cannot be accurately judged via our protocol even when both debaters know the correct answer. Thus, an interesting direction for future work is to understand whether the stability condition is necessary in this setting. An optimistic hope might be that all relevant problems can be divided into two classes: those that require very precise dependence on individual subclaims (e.g. mathematical proofs) and those that do not (e.g. scientific knowledge obtained by noisy empirical evidence). If this were the case, future debate protocols might attempt to handle each type of claim separately. For example, one could require the debaters to produce machine-verifiable proofs in Lean for all  mathematical subclaims, and use prover-estimator debate to verify fuzzier subclaims. Theoretical progress in this direction depends on precisely characterizing the structure of problems that admit stable decompositions.\n\nAnother limitation is that our results hold in an average-case rather than a worst-case sense: we do not prove the judge is always able to tell which debater is correct on every question. Rather, we show that the payoffs given by the judge incentivize the debaters to converge to answering correctly. \nThus, the  payoff assigned by the judge is a random variable that is correlated with correctness, but imperfectly so. \nWe believe such an average-case analysis is necessary, and formalizing this is an interesting open question. We are also curious whether there are corresponding lower bounds to $B$'s circuit size if the stability parameter $\\rho$ is held constant, in either the oracle or fine-grained complexity settings.\n\n\\paragraph{Empirical.}\nThe central empirical question raised by our paper is how to incorporate the qualitative recommendations from our theoretical results into practical debate training experiments with LLMs.\nSuch experiments may require additional flexibility for training to succeed, so we enumerate the key qualitative properties of prover-estimator debate that could guide practical debate experiments:\n\\begin{enumerate}\n\\item The prover $A$ both decomposes problems and chooses where to recurse given $B$'s estimates. The estimator $B$ only needs to express reasonable uncertainty about where a mistake might lie.\n\\item There is a per-round reward based on a consistency check between $B$’s estimate from the last round for the current main claim, and estimates for claims in the current round. $A$ can only collect this reward by accurately predicting the direction of $B$'s error between rounds.\n\\item In the last round, the judge directly decides if $B$’s estimates are correct.\n\\item The debaters should be trained to converge to an $A$-leading Stackelberg equilibrium.\n\\end{enumerate}\n\n\\paragraph{Zooming out.}\nThe broad question is whether some variant of debate works as a component of an overall alignment strategy. \\cite{buhl2025alignment} sketches what an overall safety case using debate might look like, combining both theoretical and empirical evidence. We believe prover-estimator debate is a useful contribution on the theory side, but hope that future work finds improved protocols that combine the advantages of other scalable oversight methods (\\pref{fig:improved-protocols}). In particular, we are interested in protocols which mitigate systematic errors in human input~\\citep{irving2025systematic} and the potential for debaters to hide information in the subclaims $y_k$~\\citep{pfau2025search}. These are just two areas for improvement: the full safety case sketch has a lot more holes to fill.","chars":4801,"total_chars":4801,"offset":0,"truncated":false,"next_offset":null}

read_arxiv_source

{
  "file": "intro.tex",
  "arxiv_id": "2610.02557",
  "max_chars": 15000
}

{"ok":true,"arxiv_id":"2610.02557","file":"intro.tex","kind":"text","text":"\\section{Introduction}\nModern AI systems are trained to perform complex reasoning tasks including autonomous software engineering \\citep{anthropic2026opus46}, novel mathematical research \\citep{abouzaid2026proof}, and general economically valuable tasks across a wide range of occupations \\citep{Patwardhan2025GDPvalEA}. One of the core drivers of this progress is the ability to design training environments with verifiable reward signals, e.g., numerical solutions or automatically verifiable proofs for mathematics or automated test cases for code. As the scope of tasks performed by AI systems broadens and increases in complexity, it becomes increasingly difficult to provide automatically verifiable rewards that capture all relevant aspects of the task. Furthermore, many tasks of interest have inherently subjective or fuzzy descriptions, so that human verification of AI outputs is necessary. These difficulties lead to the problem of \\emph{scalable oversight} --- the design of training protocols that leverage the power of rapidly improving AI systems in order to augment human abilities to provide accurate training supervision to these same systems \\citep{leike2018scalable}.\n\nAs a motivating example, consider the case of an autonomous AI agent tasked with completing a research project in the quantitative social sciences. The description of the task will likely be high-level and somewhat open-ended, possibly including relevant data sources and the question the analysis is trying to answer. However, in any such project there will be many individual decisions with multiple plausible choices, along with requirements that are not explicitly mentioned, e.g., don't calculate hundreds of different subpopulation statistics from the data, and then choose to analyze the most surprising one post hoc.\nHence, directly evaluating the full output of an autonomous AI agent would both require human judgment to some degree and be very difficult even for an expert human to judge directly. Furthermore, the cost of failing to provide accurate supervision in such settings can be quite high. For example, even in slightly misconfigured training environments for software engineering, AI systems often find cheating solutions, such as editing test cases to always pass, rather than actually solving the problem. Worse still, in some such cases AI systems have learned to generalize this negative behavior, resulting in dishonest and harmful actions across many other settings unrelated to coding \\citep{macdiarmid2025naturalemergentmisalignmentreward}.\n\nOne of the primary approaches to addressing the scalable oversight question is \\emph{AI debate}, where two powerful AI systems argue about the correctness of an AI output, and a human judges the outcome \\citep{irving2018ai}. Intuitively, the idea is that each debater will be able to recursively zoom in on individual flaws in specific pieces of their opponent's arguments, until the original problem has been broken down to a level that is simple enough for a human to judge directly. Critically, there are complexity-theoretic formalizations of this setup that can allow for rigorous definitions and evaluations of what it means for limited human judges to verify the outputs of AI systems that are much too complex to judge.\n\nPrior theoretical research has focused on the design of provably-correct debate protocols, i.e., rules of the game that constrain the AI debaters and specify how the human judge should evaluate their arguments. This prior work encountered a major obstacle known as the \\emph{obfuscated arguments problem}, where one debater can efficiently produce a dishonest argument which cannot be efficiently refuted by their opponent \\citep{barnes2020obfuscated}. While it was shown to be possible to obtain provably-correct protocols for certain limited classes of problems \\citep{brown-cohen24scalable}, the initial promise of debate for recursively decomposing highly complex problems remained in doubt.\nSubsequent progress on the obfuscated argument problem was made via the prover-estimator debate protocol of \\cite{browncohen2025avoiding}, which avoids obfuscated arguments for a class of problems that admit \\emph{sufficiently stable} decompositions into subproblems. Despite this progress on expanding the class of problems that can be handled by debate, the prover-estimator protocol has additional limitations when compared to prior work: it provides average-case guarantees that hold for a weaker equilibrium concept than previously studied.\n\nIn this paper we design a new debate protocol that provides worst-case guarantees for the original, stronger dominant-strategy equilibrium concept. The protocol handles exactly the same class of sufficiently stable problems as prover-estimator debate, while also being simpler to execute and analyze. We further prove that this protocol is instance optimal unless further structural assumptions are made on the human judgments used to verify debates.\n\n\\subsection{Our Results}\nOur new protocol is simple to describe. The first debater, Alice, decomposes the original claim into sub-claims. The second debater, Bob, then has two choices: either (1) demonstrate that Alice's decomposition is too \\emph{sensitive} to small errors in the sub-claims, or (2) choose a sub-claim on which to continue the debate recursively.\nThe key to the analysis is the equivalence between the notion of stable decompositions required for prover-estimator debate and bounds on \\emph{fractional block sensitivity}, a quantity defined in the query complexity literature which is tightly connected to the number of queries a randomized verifier must make to check an untrusted proof~\\citep{KulkarniTal2016fbs}.\nIn particular, an upper bound on the fractional block sensitivity of Alice's decomposition implies an efficiently computable strategy for Bob to select a sub-claim that has a non-trivial chance of being incorrect.\n\nThe equivalence to fractional block sensitivity further enables us to prove that the performance of our protocol is \\emph{instance optimal} assuming black-box access to human judgments. That is, if the particular problem instance admits a decomposition with fractional block sensitivity $\\rho$, then \\emph{any protocol} which correctly decides the outcome on this instance cannot have asymptotically lower complexity for the debaters.\nAll prior theoretical work on debate has modeled human judgment as a black-box oracle, so this result can be interpreted as demonstrating the necessity of going beyond this model in order to further expand the class of problems solvable via debate.\n\n\\subsection{Technical Overview}\nWe next give an informal mathematical overview of our protocol and proof techniques. We will begin by describing how the protocol works in our running example of an autonomous AI agent Alice performing quantitative social science research.\n\n\\paragraph{The protocol in action.} In order to efficiently evaluate the correctness of the final research paper and codebase produced by the quantitative social science agent, we use a debate between Alice, who defends her work, and another AI Bob who attempts to find flaws. To determine the validity of a claim in the paper, we ask Alice to decompose the original claim $x$ into sub-claims $y_1,\\dots,y_q$. One can view these sub-claims as pieces of supporting evidence. For example, the claim $x$ might be that a certain statistical modeling assumption is justified. Suppose that we would believe this claim if a majority of correct, published papers in the existing literature supported it. In this case, the sub-claims $y_i$ are of the form: this particular paper from the existing literature is both correct and supports the original claim. Furthermore, the truth of the original claim $x$ is the majority vote of the truth values of the sub-claims $y_i$.\n\nNext, suppose that Alice claims that in fact $2/3$ of the published papers $y_i$ support the claim. We view this as an assignment by Alice of alleged truth values $z_i$ to each sub-claim $y_i$. In this case, the key insight is that Bob need not check every single paper for correctness in order to verify the overall claim. Instead, Bob can just randomly sample a paper among the $2/3$ that Alice says support the original claim, i.e., those where $z_i = 1$. If Alice is lying about the original claim $x$, then at least $1/6$ of the sub-claims must also be lies. Hence, by sampling randomly among the $2/3$ where $z_i = 1$, Bob will have a $\\frac{1/6}{2/3} = 1/4$ chance of catching Alice in a lie. Thus, just by sampling a few research papers from the entire area to check, Bob can be confident of catching Alice in a lie.\n\nOn the other hand, suppose that Alice claims that 50 out of a total of 99 papers $y_i$ support the original claim $x$. In this case, Bob has no recourse but to check every single one of the 50 papers, as even a single incorrect paper would flip the majority vote and overturn the truth of the original claim. The key to our protocol is that Bob is allowed to demonstrate that Alice has made an unreasonably sensitive claim of this form, in which case Alice will lose the debate. This in turn requires Alice to only decompose her claims in a way that is not too sensitive to errors in individual sub-claims. We view this as a very natural restriction when arguing about claims that inherently involve fuzzy human judgment. Indeed, one should be very suspicious of any argument that is highly sensitive to changes in individual pieces of evidence, and yet relies on fuzzy human judgments in each step.\n\n\\paragraph{Formalization via fractional block sensitivity.}\nOur protocol follows the same outline as described in the example: Alice decomposes a claim $x$ into sub-claims $y_i$, Bob either objects that Alice's decomposition is too sensitive, or instead selects a sub-claim to debate further. The key technical component is the notion of \\emph{fractional block sensitivity} which generalizes the intuition above about the majority function to all possible aggregation functions Alice might choose. In particular, the fractional block sensitivity $\\rho$ is defined as the optimum of a linear program that depends on the aggregation function and Alice's alleged truth values $z_i$ for the sub-claims $y_i$. In the case of the majority vote function with $2/3$ of the truth values $z_i$ set to 1, the optimum of the linear program is $\\rho = 4$, which corresponds to Bob's chance of $1/4$ of catching Alice in a lie if he samples a random $y_i$ among the $2/3$ claimed true. This correspondence is not a coincidence--it generalizes to any aggregation function.\nMore formally, the dual solution of the fractional block sensitivity linear program directly yields probabilities $p_i$ for Bob to sample sub-claims. When sampling sub-claims with these probabilities, Bob has at least a chance of $1/\\rho$ of catching Alice in a lie. See \\Cref{sec:fbs-def} for the precise formal definition.\n\nThe protocol runs recursively on the sub-claim sampled by Bob, until it reaches a depth of $d$, whereupon a human judge directly evaluates the final selected sub-claim. Unless Alice wants to lose immediately, she must ensure that in each round the decomposition into sub-claims that she makes has fractional block sensitivity bounded by $\\rho$. Thus, we conclude that if Bob follows the sampling scheme provided above, he will catch Alice in a lie with probability at least $\\rho^{-d}$. Hence, by running the protocol $O(\\rho^d \\log n)$ times, Bob will catch Alice in a lie with probability at least $1 - O(1/\\poly(n))$. See \\Cref{sec:protocol} for details. To make sense of this result, recall that Alice decomposes each original claim into $q$ sub-claims. So exploring the full tree of sub-claims would require time $q^d$. As shown in the example of the majority vote aggregation function, one can have $q=99$, while $\\rho =4$, implying that $\\rho^d$ can be significantly smaller. In the standard setting, the debate has depth $d=O(\\log n)$, implying that our protocol allows for a polynomial in $n$ speed-up beyond exhaustive search of Alice's decomposition.\n\n\\paragraph{Honesty and correctness are dominant strategies.}\nOur protocol for fractional block sensitivity (FBS) debate satisfies the key properties of \\emph{completeness} and \\emph{soundness}. Completeness requires that if the original claim $x$ is correct, then no matter what strategy Bob employs, Alice can always win by honestly and correctly decomposing every claim. Similarly, soundness requires that if the original claim $x$ is incorrect, then no matter what strategy Alice employs, Bob can win with overwhelming probability by honestly following the prescribed protocol. In other words, honestly and correctly following the prescribed protocol is a \\emph{dominant strategy} for each player in the debate game. This is in contrast to the prior prover-estimator debate protocol, which only guarantees soundness under the following Stackelberg equilibrium condition: for any dishonest strategy selected by Alice, there exists a winning strategy by Bob, which in general depends on Alice's strategy in a potentially complicated way. This is a technically much weaker condition, and in practice training for dominant strategy equilibria is much more stable and tractable than Stackelberg equilibria.\n\nFurthermore, our protocol applies on a worst-case basis: if an individual claim $x$ is incorrect, our protocol will allow Bob to efficiently identify a flawed sub-claim for the human judge. In contrast, the prover-estimator protocol only satisfies soundness on average over a distribution on inputs. This is sufficient to guarantee that training the debaters to maximize their expected win rates leads to a debate equilibrium where the debaters are honest on all but a small fraction of questions. However, our protocol for FBS debate goes further by guaranteeing that on each individual question, honesty is the best policy.\n\n\\paragraph{Instance-wise optimality.}\nFinally, we show in \\Cref{sec:lower-bound} that any protocol with only black-box access to human judgments must make at least $\\Omega(\\rho^d)$ queries to find a flawed sub-claim with constant probability, matching the cost of our FBS debate protocol. This lower bound holds instance-wise: if the best decomposition of an original claim $x$ into a tree of sub-claims has fractional block sensitivity $\\rho$ in each step, then $\\rho^d$ queries are required on that particular instance $x$. The assumption of black-box access to human judgments is critical for the lower bound to hold. One can view this instance-wise optimality as demonstrating that the black-box judgment assumption, which is common to all prior theoretical work on debate, must be relaxed in order to make further progress on debate protocols.\n","chars":14812,"total_chars":14812,"offset":0,"truncated":false,"next_offset":null}

read_arxiv_source

{
  "file": "conclusion.tex",
  "arxiv_id": "2610.02557"
}

{"ok":true,"arxiv_id":"2610.02557","file":"conclusion.tex","kind":"text","text":"\\section{Discussion and Open Problems}\nOur protocol and matching lower bound show that fractional block sensitivity precisely characterizes the set of problems that can be efficiently solved by debate within this recursive-decomposition framework. Notably, the protocol does not require Bob to determine whether or not Alice's answers to subproblems are correct, but only to understand the structure of the argument well enough to sample subproblems to which the outcome is sufficiently sensitive. This stands in contrast to the original $\\text{Debate}=\\text{PSPACE}$ result of \\cite{irving2018ai}, which requires Bob to actually directly determine which of Alice's subproblems are flawed. Of course, this comes with the limitation that the identification of flawed subproblems might actually have much greater computational complexity than creating the subproblems. This is not an issue if we assume that both Alice and Bob have the power to solve any problem in PSPACE, but is a serious obstacle if the debaters are assumed to be computationally bounded (as they will be in practice).\n\nGiven this discussion, the question remains: is it possible to design a protocol that goes beyond the fractional block sensitivity barrier we identify? One might hope that utilizing Bob's ability to solve the same problems as Alice could help with this issue, perhaps by allowing Bob to take advantage of Alice's computational limitations in some way. Alternatively, our lower bounds only apply when human judgment is modeled as a black box, accessible only via queries. Classical results in interactive proofs like $\\text{IP}=\\text{PSPACE}$ show that opening up the black box yields much stronger protocols. It seems implausible that these methods can be adapted to the case of human judgment---one would need to essentially be able to ``read the code'' that implements the human judgment. However, it is still possible that some other relaxation of the black-box oracle assumption could lead to better debate protocols.\n","chars":2010,"total_chars":2010,"offset":0,"truncated":false,"next_offset":null}