Technical Summary: Joint Consistency (JC)

Problem Definition

The paper addresses Test-Time Aggregation (TTA), the problem of selecting a single, reliable answer from a set of $N$ candidate reasoning traces generated for a specific query. While existing Test-Time Scaling (TTS) methods effectively generate multiple traces, their aggregation strategies often suffer from two limitations:

1. Isolation: Most methods (e.g., Self-Consistency, Weighted Self-Consistency) evaluate traces independently, relying on absolute quality scores or answer frequencies. This ignores comparative information between candidates.
2. Calibration Difficulty: Independent evaluation requires the evaluator to produce well-calibrated absolute scores, which is often difficult to achieve, especially across heterogeneous model generators.
3. Scalability of Comparisons: While comparative judgments (e.g., "Trace A is better than Trace B") are often more reliable than absolute scores, naively incorporating all pairwise comparisons incurs an $O(N^2)$ computational cost, which is prohibitive for large trace budgets.

The authors pose the question: How can pairwise comparative judgments be incorporated into test-time aggregation in a principled, computationally efficient manner?

Methodology: Joint Consistency (JC)

The authors propose Joint Consistency (JC), a unified framework formulated as a constrained Ising-type energy minimization problem.

1. The Energy Function

The aggregation goal is to find an indicator vector $x \in \{0, 1\}^N$ (where $x_i=1$ if trace $i$ is selected) that minimizes the energy function $H(x)$:
$$\min_{x \in \{1_{I_k} | k \in [K]\}} H(x) := -\mu \langle h, x \rangle - x^\top J x$$
Where:

• $K$ is the number of distinct candidate answers.
• Constraint: The feasible set restricts $x$ to select exactly one answer group (all traces yielding the same answer).
• $h$ (External Field): A vector encoding independent evaluation signals (e.g., LLM-as-a-judge scores for individual traces).
• $J$ (Interaction Matrix): A matrix encoding pairwise comparative signals (e.g., probabilities that trace $i$ is preferred over trace $j$).
• $\mu$ (Hyperparameter): Controls the trade-off between independent evaluation and pairwise interactions.

2. Construction of the Interaction Matrix ($J$)

The matrix $J$ is constructed using LLM-as-a-judge comparisons.

• Pairwise Probabilities: For traces $y_i$ and $y_j$, the judge estimates $p_\theta(y_i \succeq y_j)$, the probability that $y_i$ is better than $y_j$.
• Positive Semi-Definite Construction: To ensure stability and interpretability, $J$ is defined as $J = CC^\top$, where the entry $C_{ij}$ is a normalized version of the preference probability:
  $$C_{ij} := \sqrt{\frac{p_\theta(y_i \succeq y_j)}{n_i^2 n_j}}$$
  Here, $n_i$ is the number of traces sharing the same answer as $y_i$. This construction implies that two traces have a strong interaction if they are both preferred over similar sets of competing traces.

3. Theoretical Interpretation

Under an answer-level homogeneity assumption (where all traces for a given answer $a^{(k)}$ have identical pairwise preference probabilities against traces of another answer $a^{(k')}$), the quadratic term $x^\top J x$ simplifies to a sum of answer-level preferences. This provides a theoretical justification for converting trace-level comparisons into an answer-level aggregation rule.

4. Efficient Approximation Strategy

To address the $O(N^2)$ cost of computing $J$ for all trace pairs, the authors propose a Top-$\kappa$ approximation:

• Instead of comparing all $N$ traces, interactions are estimated only between the top-$\kappa$ most frequent answer groups.
• This reduces the complexity from $O(N^2)$ to $O(\kappa^2)$, where $\kappa$ is a small consistency budget (e.g., $\kappa=4$).
• The optimization of the energy function itself is tractable ($O(K)$ or $O(\kappa)$) because the feasible set is restricted to $K$ (or $\kappa$) candidate answer groups, avoiding the NP-hard nature of general quadratic unconstrained binary optimization (QUBO).

Key Contributions

1. Incorporation of Comparative Signals: JC introduces a constrained energy minimization model that integrates pairwise comparative signals via an interaction matrix $J$, alongside independent signals via an external field $h$.
2. Unifying Framework: The formulation subsumes existing methods as special cases:
   • Self-Consistency (SC): $J=0, \mu=0$ (or specific $h$).
   • Weighted Self-Consistency (WSC): $J=0, \mu > 0$.
   • Interaction-only: $\mu=0$.
   • By varying $\mu$, JC interpolates between these strategies.
3. Scalability: The proposed Top-$\kappa$ approximation makes interaction modeling practical for large-scale aggregation, retaining the benefits of pairwise comparisons with costs comparable to standard weighted voting.

Experimental Results

The authors evaluated JC on math reasoning (MathArena: AIME, HMMT, Brumo) and code reasoning (CruxEval-O) benchmarks.

• Crowdsourced Settings (Heterogeneous Traces):
  • JC consistently outperformed baselines (SC, WSC, Best-of-N, Knockout Tournament) across diverse judge models (Qwen, DeepSeek, GPT variants) and trace budgets.
  • On MathArena-C (challenging subset), JC with a small $\kappa=4$ achieved accuracy gains of over 20% compared to WSC.
  • JC remained robust even when traces were generated by lower-tier models, where independent scores were unreliable but comparative coherence remained effective.
• Homogeneous Settings (Intrinsic Signals):
  • In settings where token-level log-probabilities were available (e.g., DeepSeek-R1, Qwen3), JC still outperformed intrinsic-evaluation baselines like Self-Certainty and DeepConf.
  • The performance gain of JC over the strongest baseline increased as the number of traces ($N$) increased, indicating better scaling properties.
• Cost Efficiency:
  • The cost of the JC evaluation phase (querying the judge for $h$ and $J$) was found to be less than 1% of the cost of generating the reasoning traces.
  • The method is robust to the choice of $\mu$ (optimal range typically $[0.5, 1]$) and does not require fine-tuning for specific judge models.

Significance and Claims

The paper claims that Joint Consistency provides a principled, unified approach to test-time aggregation that bridges the gap between independent evaluation and pairwise comparison.

• Theoretical Insight: It frames aggregation as an energy minimization problem, offering a theoretical interpretation of how pairwise comparisons aggregate at the answer level.
• Practical Impact: It demonstrates that leveraging comparative signals via an efficient approximation strategy yields consistent gains over state-of-the-art baselines without prohibitive computational overhead.
• Limitations: The authors modestly note that the current work focuses on final-answer aggregation in reasoning tasks; generalization to open-ended reasoning or research-level problem solving is unproven. Additionally, the specific construction of the interaction matrix $J$ may not be optimal, and the method inherits the limitations of the underlying generation and judge models.