Technical Summary: Decision Potential Surface (DPS)

Problem Statement

Analyzing the decision boundaries of Large Language Models (LLMs) is critical for understanding their core properties, including reasoning, in-context learning, hallucination, and memorization. However, constructing these boundaries for mainstream LLMs is currently computationally infeasible. Unlike traditional deep neural networks with limited output classes, LLMs operate over expansive vocabularies (often >100,000 tokens) and generate sequences autoregressively. For a sequence of length $N_r$ and vocabulary size $V$, the output space size is $V^{N_r}$, leading to an exponential explosion of decision regions (e.g., $\approx 10^{169,790}$ for a Qwen-3 model). Existing approaches either simplify the problem to toy binary classification scenarios or use the concept of decision boundaries metaphorically without actual construction, leaving the question of how to efficiently and rigorously construct LLM decision boundaries unanswered.

Methodology

The paper proposes a new framework centered on the Decision Potential Surface (DPS) and its practical approximation, K-DPS.

1. Decision Potential Surface (DPS)

The authors define the DPS as a landscape over the input manifold where each point encodes the "competition potential" among candidate outputs.

• Decision Potential Function (DPF): For a given input $x$, the DPF $\Phi^\infty_f(x)$ is defined as the squared difference in log-likelihoods between the top-two generated sequences ($y_{1*}$ and $y_{2*}$):
  $$\Phi^\infty_f(x) = (\log P_f(y_{1*}|x) - \log P_f(y_{2*}|x))^2$$
• Theoretical Equivalence: The authors prove that the zero-height isohypse (contour line where $\Phi^\infty_f(x) = 0$) of the DPS is mathematically equivalent to the formal decision boundary of the LLM (the set of inputs where two distinct sequences have equal and maximal generation probabilities). Regions separated by this boundary correspond to Voronoi cells in the sequence space.
• Confidence Hierarchy: Non-zero isohypses ($\epsilon$-isohypses) represent contours of constant confidence margins ($\sqrt{\epsilon}$ nats) between the top two candidates, partitioning the input space into confident regions, uncertain regions, and the boundary itself.

2. K-Grained Decision Potential Surface (K-DPS)

Since computing the exact DPF requires enumerating the entire output space (intractable), the authors propose K-DPS, an approximation using finite sampling.

• Sampling Mechanism: Instead of exhaustive search, K-DPS estimates the DPF by sampling $K$ independent and identically distributed (i.i.d.) sequences from the model's output distribution for a given input. The top-two sequences within this sample set ($y^K_{1*}, y^K_{2*}$) are used to compute the approximate potential $\Phi^K_f(x)$.
• Complexity Reduction: This reduces the computational complexity from $O(V^{2N_r})$ to $O(K^2)$, making the analysis feasible for industrial-scale models.

3. Theoretical Error Bounds

The paper provides rigorous theoretical guarantees for the approximation error between K-DPS and the ideal DPS:

• Absolute Error Bound: The error $|\Phi^K_f(x) - \Phi^\infty_f(x)|$ is bounded with high probability, scaling with $1/\sqrt{K}$.
• Expected Error and Concentration: The expected error and tail probabilities are derived, showing that the error concentrates rapidly as $K$ increases.
• Local Candidate-Set Bound: The authors introduce a bound dependent on the probability mass of "near-second" candidates, demonstrating that if the sample set captures the true top-1 and a candidate close to the true top-2, the error is negligible.

Key Contributions

1. Formal Definition of DPS: Introduction of the Decision Potential Function and Surface, proving that the zero-height isohypse is equivalent to the LLM decision boundary.
2. K-DPS Algorithm: Proposal of a practical, finite-sampling approximation algorithm that requires only $K$ samples to approximate the decision boundary with provably small error.
3. Theoretical Guarantees: Derivation of absolute error bounds, expected error bounds, and concentration inequalities, establishing a trade-off between sampling budget ($K$) and approximation accuracy.
4. Empirical Validation: Extensive experiments on open-source LLMs (e.g., Llama-3, Mistral, Tulu) demonstrating that K-DPS converges rapidly with practical sampling budgets (e.g., $K \approx 2,500$) and reveals interpretable geometric changes in model behavior.

Results and Case Studies

The authors apply K-DPS to two critical areas to demonstrate its interpretability:

• Alignment Analysis: Visualizing decision boundaries of models before and after alignment (using AdvBench prompts) reveals that aligned models exhibit significantly smoother and flatter decision surfaces. High-confidence "vulnerability spikes" present in unaligned models are eliminated, explaining why alignment mitigates jailbreaks by removing narrow regions where harmful outputs are probable.
• Machine Unlearning: The method visualizes the side effects of unlearning algorithms (e.g., Gradient Ascent vs. Negative Preference Optimization). It reveals that naive unlearning can cause a "catastrophic collapse" of the decision manifold, creating jagged, fragmented regions unrelated to the forget corpus. In contrast, methods with retention training preserve the smoothness of the decision surface.

Significance and Claims

The paper claims to be the first study to construct decision boundaries for LLMs with both theoretical guarantees and computational feasibility.

• Practicality: It bridges the gap between the theoretical concept of decision boundaries and the practical constraints of autoregressive generation, moving beyond toy scenarios.
• Interpretability: By visualizing the "height" of the decision potential surface, the method offers a geometric lens to understand phenomena like robustness, alignment, and unlearning damage that were previously difficult to observe directly.
• Theoretical Rigor: Unlike heuristic uncertainty quantification methods, K-DPS provides a principled, boundary-aware certification with explicit error bounds, shifting the paradigm from post-hoc scoring to geometric boundary analysis.

The authors maintain modesty regarding long, high-entropy generation, noting that while K-DPS works well for bounded-length responses, exact sequence-level boundary construction for very long outputs (e.g., 8K tokens) faces inherent challenges due to vanishing joint probabilities, suggesting token-level or prefix-conditioned variants for such regimes.