Parameter-Efficient Orthogonal Finetuning via Butterfly Factorization

ArXiv: 2311.06243

🎯 Pitch

A butterfly-structured product of sparse matrices yields a dense orthogonal transformation with O(d log d) parameters, dramatically compressing Orthogonal Finetuning while outperforming LoRA on vision and language benchmarks. The method’s implicit bias toward classical fast transforms like the FFT means you can interpolate along the orthogonal manifold for free, enabling training-free multi-objective merges.

---

1. Executive Summary

This paper proposes Orthogonal Butterfly (BOFT), a parameter-efficient finetuning method that constructs a dense orthogonal transformation matrix via the product of multiple sparse orthogonal matrices structured as butterfly graphs. Evaluated across large language models (DeBERTaV3, Llama-2), vision foundation models (DINOv2, SAM), and text-to-image diffusion models (Stable Diffusion) on benchmarks including GLUE, MMLU, VTAB-1K, GSM8K, and controllability metrics, BOFT reduces trainable parameters from the quadratic O(d²) of a dense orthogonal matrix to O(d log d) while maintaining expressivity superior to the block-diagonal sparsity pattern used in prior Orthogonal Finetuning (OFT). BOFT achieves consistent accuracy improvements over LoRA and OFT under matched or smaller parameter budgets—for instance, on VTAB-1K with DINOv2-large, BOFT reaches 77.9% average accuracy versus LoRA's 76.6% while using 1.77M versus 1.77M parameters, and on controllable generation it reduces landmark error to 5.667 versus OFT's 6.407 at a similar ~20M parameter scale—while preserving the zero-inference-latency property of multiplicative weight updates. The paper further establishes that the butterfly structure introduces a beneficial inductive bias through its shared structural pattern with classic fast linear transforms (Fourier, Hadamard, discrete cosine), and that the factorized orthogonal representation enables free weight interpolation along the orthogonal manifold without retraining, though performance on the hardest problem tiers remains bounded by base model capability.

2. Context and Motivation

The Core Problem: Parameter-Efficient Adaptation of Foundation Models

The fundamental problem this paper addresses is how to efficiently adapt large pretrained foundation models to downstream tasks without sacrificing the quality of the adaptation or incurring inference-time overhead. This matters because the dominant paradigm in modern machine learning—training enormous models from scratch on massive datasets—has become economically and computationally prohibitive for most researchers and practitioners. Models like GPT-3 (175B parameters), Llama-2 (7B–70B), DINOv2 (300M+), and Stable Diffusion are extraordinarily expensive to train, yet they need to be specialized for particular tasks to be maximally useful. Full finetuning of such models is impractical: it requires storing and updating all parameters, demands substantial GPU memory, and risks catastrophic forgetting of the pretrained knowledge.

The paper identifies three broad families of adaptation methods in Section 1:

• Model finetuning: A subset of the original model's parameters is updated (e.g., BitFit, LoRA, OFT). This preserves the original architecture and introduces no inference latency, since the learned updates can be folded back into the pretrained weights.
• Adapter tuning: Additional trainable modules are inserted into the frozen pretrained model (e.g., Houlsby adapters, Pfeiffer adapters). These add parameters and typically introduce some inference overhead.
• Prompt tuning: Trainable prefix tokens are prepended to the input (e.g., prefix tuning, visual prompt tuning). These are lightweight but can be less expressive.

Among these, model finetuning is particularly attractive because it combines strong performance with zero additional inference cost—a critical requirement for deployed systems where latency budgets are fixed. The paper explicitly positions itself within this category, building on the Orthogonal Finetuning (OFT) framework introduced by Qiu et al. (2023).

The OFT Framework and Its Parameter-Efficiency Bottleneck

OFT operates on a geometrically motivated principle: when adapting a pretrained weight matrix $W^0 \in \mathbb{R}^{d \times n}$, the new weight matrix is reparameterized as $R \cdot W^0$ where $R \in \mathbb{R}^{d \times d}$ is a learnable orthogonal matrix. This multiplicative update preserves the pairwise angles between neuron vectors—the column vectors of $W^0$—a property that has been linked to generalization and training stability in prior work on hyperspherical energy (Liu et al., 2018). By constraining $R$ to be orthogonal (using Cayley parameterization: $R = (I + Q)(I - Q)^{-1}$ where $Q$ is skew-symmetric), OFT ensures that the spectral norm of the pretrained weights is preserved, which prevents the kind of training instability that can arise when weight norms grow unbounded.

The core difficulty is that a full dense orthogonal matrix requires $O(d^2)$ parameters. For a typical transformer layer where $d$ might be 1024 or 4096, this translates to millions of trainable parameters per layer—often more than the original model itself. To address this, the original OFT introduces a block-diagonal structure: $R = \text{diag}(R_1, R_2, \ldots, R_r)$ where each $R_i \in \mathbb{R}^{b \times b}$ is a small orthogonal matrix and $b \cdot r = d$. This reduces the parameter count from $O(d^2)$ to $O(b \cdot d)$. For example, with $b = 16$ and $d = 1024$, the parameter count drops from ~524K to ~8K per matrix.

However, this block-diagonal sparsity pattern introduces three significant limitations that the paper explicitly identifies (Section 3):

1. Arbitrary dimension grouping: The block-diagonal structure arbitrarily partitions the dimensions of a neuron into $r$ groups based purely on their indices. There is no principled reason why dimensions 1–16 should be transformed together while dimensions 17–32 are transformed separately. This introduces an artificial inductive bias that may not align with the structure of the pretrained representations.

2. Reduced expressivity: The block-diagonal matrix represents a severely restricted subset of the orthogonal group. It cannot approximate many common linear transformations, including classic transforms like the discrete Fourier transform, discrete cosine transform, or Hadamard transform—all of which have dense orthogonal matrix representations.

3. Fixed sparsity pattern: The block-diagonal structure forces a predetermined connectivity pattern where each dimension can only interact with $b - 1$ other dimensions within its block, rather than with all $d - 1$ dimensions. This limits the model's ability to learn global feature transformations.

The key tension is: dense orthogonal matrices are desirable for expressivity, but block-diagonal matrices are necessary for parameter efficiency. The paper asks whether this trade-off is fundamental or whether a better factorization exists.

Where Existing PEFT Methods Fall Short

The paper situates BOFT relative to several contemporary approaches, identifying specific limitations in each:

LoRA (Low-Rank Adaptation, Hu et al., 2022) is the most widely used PEFT method and the primary baseline throughout the paper. LoRA parameterizes the weight update as an additive low-rank matrix: $W = W^0 + AB$ where $A \in \mathbb{R}^{d \times r}$ and $B \in \mathbb{R}^{r \times n}$ with $r \ll \min(d, n)$. This is parameter-efficient (using $r(d + n)$ parameters) and introduces no inference latency since $AB$ can be merged into $W^0$. However, the paper identifies several weaknesses:

• Additive updates change the spectral properties of the weight matrix. Adding a low-rank matrix can alter the singular values of $W^0$, potentially destabilizing training or degrading the pretrained representations. OFT and BOFT, being multiplicative orthogonal transforms, perfectly preserve the spectral norm.
• LoRA does not preserve pairwise angles between neurons. The geometric relationships encoded in the pretrained weights—which OFT and BOFT explicitly conserve—are not protected under LoRA's additive updates.
• LoRA's expressivity is limited by the rank $r$. While sufficient for many NLP tasks, fixed-rank adaptation may be suboptimal for complex visual or multimodal tasks where the required adaptation is not naturally low-rank.

Adapter-based methods (Houlsby et al., 2019; Pfeiffer et al., 2020) insert small bottleneck networks between transformer layers. These add inference latency and are architecturally invasive, requiring modifications to the model structure. The paper notes these as alternatives but does not extensively compare against them, focusing instead on methods that preserve the original model architecture and inference speed.

BitFit (Zaken et al., 2022) finetunes only the bias terms, achieving extreme parameter efficiency (0.1M parameters on GLUE) but with limited expressivity. It serves as a lower bound in the paper's comparisons.

Dynamic rank methods (AdaLoRA, DyLoRA, IncreLoRA) improve on LoRA by adaptively allocating rank across layers. While these improve parameter allocation, they still rely on the low-rank additive paradigm and share its fundamental limitations regarding spectral properties and geometric preservation.

Generalized LoRA (GLoRA, Chavan et al., 2023) extends LoRA with additional learnable components (scaling, shifting) but increases parameter count substantially—4.87M parameters for the VTAB-1K experiments in Table 4, versus 1.77M for BOFT—while achieving lower average accuracy (74.5% vs. 77.9%).

The Unexplored Potential of Orthogonal Finetuning

The paper highlights a significant gap in the literature: OFT had previously only been demonstrated on controllable text-to-image generation (Qiu et al., 2023). Whether orthogonal finetuning could serve as a general-purpose PEFT method—competitive with or superior to LoRA across vision, language, and multimodal tasks—was unknown. The paper explicitly states this as a motivation in Section 2:

"Moreover, whether OFT is applicable to a wider spectrum of adaptation tasks (beyond controlling text-to-image diffusion models) is unknown. BOFT improves the parameter efficiency of OFT via butterfly factorization. Thanks to this, we are now able to demonstrate the power of orthogonal finetuning in general adaptation tasks."

This is significant because OFT's theoretical advantages—spectral norm preservation, pairwise angle conservation, training stability—are universal properties of the orthogonal group. If the parameter efficiency bottleneck could be solved, OFT could potentially surpass LoRA across the board. The paper positions BOFT as the key that unlocks this potential.

The Butterfly Structure: Inspiration from Signal Processing

The paper draws a novel connection between parameter-efficient orthogonal matrix construction and the Cooley-Tukey fast Fourier transform (FFT) algorithm (Cooley and Tukey, 1965). The radix-2 FFT recursively decomposes an $N$-point discrete Fourier transform into two $N/2$-point transforms, a process that induces a butterfly graph—a sparse connectivity pattern that efficiently routes information between all input and output nodes using only $O(N \log N)$ edges rather than the $O(N^2)$ edges of a fully connected graph.

The insight is that the butterfly graph achieves dense connectivity (every input can reach every output) with sparse intermediate matrices—exactly the combination needed for a parameter-efficient orthogonal matrix that can still approximate arbitrary orthogonal transforms. The paper formalizes this intuition through an information transmission framework (Section 3): generating a dense orthogonal matrix via the product of sparse matrices $R = B_m B_{m-1} \cdots B_1$ is equivalent to transmitting information through a grid-structured graph with $d \times (m+1)$ nodes, where each $B_i$ defines the connectivity between adjacent levels. The desiderata for parameter efficiency are:

1. Dense connectivity: Every node in the first level must have at least one path to every node in the last level (so the product is dense).
2. Minimum free edges: The total number of edges (i.e., non-zero entries across all $B_i$) should be minimized under the orthogonality constraint.

The butterfly graph satisfies both: it achieves dense connectivity with $O(d \log d)$ edges—a dramatic reduction from the $O(d^2)$ edges of a single dense orthogonal matrix.

Prior Work on Butterfly Matrices in Machine Learning

The paper acknowledges that butterfly matrices have been used in ML before, but positions BOFT as a novel application:

• Sparse training: Chen et al. (2022) and Dao et al. (2022) use butterfly parameterizations to train neural networks from scratch with sparse weight matrices. The focus is on computational efficiency during training, not on parameter-efficient finetuning.
• Learning fast transforms: Dao et al. (2019) learn linear transforms parameterized as butterfly matrices. The goal is recovering known transforms from data, not adapting pretrained models.
• Kaleidoscope hierarchy: Dao et al. (2020) generalize butterfly matrices to represent all structured linear maps. This work provides theoretical grounding—specifically, that a product of $d-1$ butterfly matrices and their transposes can represent any orthogonal matrix—which BOFT's Theorem 1 relies on.
• Stabilizing RNNs: Jing et al. (2017) use butterfly-structured unitary matrices to stabilize recurrent neural network training.

The paper explicitly contrasts BOFT with butterfly-based sparse training in Section 5:

"[Prior work] typically focus on reparameterizing the weight matrices directly with the butterfly parameterization and training neural networks from scratch. [Dao et al., 2022] considers finetuning the pretrained weights by first projecting the weights on a variant of butterfly matrices and then optimizing the projected components for downstream tasks. BOFT proposes a very different finetuning strategy that transforms the weights with layer-shared weight matrices."

The key difference is that BOFT applies butterfly-structured orthogonal matrices multiplicatively as a transformation of the frozen pretrained weights, preserving the pretrained knowledge while enabling task-specific adaptation. Prior butterfly work either replaces the weights entirely (training from scratch) or projects the weights onto a butterfly basis (altering the weight values directly). BOFT's "transform rather than replace" approach is what enables the OFT framework's geometric preservation properties while achieving parameter efficiency.

How This Paper Positions Itself

The paper positions BOFT as occupying a unique point in the PEFT design space—one that was previously inaccessible due to the parameter-efficiency limitations of dense orthogonal matrices:

• Relative to OFT: BOFT is a strict generalization. OFT with block size $b$ is recovered as the special case $\text{BOFT}(m=1, b)$. BOFT with $m > 1$ constructs matrices that are strictly more expressive than block-diagonal OFT with the same block size (Theorem 1), meaning no expressivity is sacrificed for parameter efficiency.
• Relative to LoRA: BOFT offers an alternative paradigm—multiplicative orthogonal updates versus additive low-rank updates—with complementary strengths. The orthogonal constraint provides theoretical guarantees (spectral norm preservation, angle conservation) that LoRA lacks, while the butterfly structure provides a path to dense orthogonal matrices that was previously impractical.
• Relative to full finetuning: BOFT's multiplicative updates can be folded into the pretrained weights, yielding zero inference overhead. Full finetuning achieves maximum expressivity but modifies all weights directly, often leading to overfitting on small downstream datasets and destroying the pretrained representations.
• Relative to butterfly-based sparse training: BOFT uses butterfly structure for parameter efficiency in a finetuning context, which is fundamentally different from using butterfly matrices as the primary weight representation during training from scratch.

The paper's central claim is that the butterfly structure provides a "smooth interpolation" between identity matrices (regularity) and full orthogonal matrices (expressivity), enabling BOFT to find a hypothesis class within the orthogonal group that balances preservation of pretrained knowledge with adaptation capacity. This is contrasted with the block-diagonal structure, which provides a coarser, less flexible trade-off. The information transmission framework provides both the conceptual language for understanding this trade-off and a practical methodology for discovering efficient sparse factorizations beyond the butterfly structure itself (a direction the paper flags for future work in Section 7).

3. Technical Approach

3.1 Reader Orientation

BOFT is a parameter-efficient finetuning method that learns a dense orthogonal transformation matrix—applied multiplicatively to frozen pretrained weights—by representing it as the product of multiple sparse orthogonal matrices structured as butterfly graphs. The method solves the core tension in Orthogonal Finetuning: dense orthogonal matrices are desirable for their expressivity and geometric preservation properties, but require $O(d^2)$ parameters (impractical for large models), while block-diagonal approximations are parameter-efficient but sacrifice expressivity and introduce arbitrary structural constraints. BOFT's solution is to build a dense orthogonal matrix from $O(\log d)$ sparse factors, each using only $O(d)$ parameters, yielding a total parameter count of $O(d \log d)$—a reduction from quadratic to linearithmic—while maintaining the ability to approximate arbitrary orthogonal transformations.

3.2 Big-Picture Architecture (Diagram in Words)

The system has three major components that operate sequentially during a forward pass:

1. Pretrained Weight Matrix $W^0 \in \mathbb{R}^{d \times n}$ — the frozen linear layer from the foundation model. This is never updated; it provides the base transformation that carries pretrained knowledge.

2. Orthogonal Butterfly Matrix $R(m, b) \in \mathbb{R}^{d \times d}$ — a learnable dense orthogonal matrix constructed as the product of $m$ sparse orthogonal butterfly components $\tilde{B}_b(d, i)$. Each butterfly component is a block-diagonal matrix of $2b \times 2b$ orthogonal blocks, with the sparsity pattern of successive components arranged to collectively route information between every input-output pair. The parameters live in the skew-symmetric matrices that generate each $2b \times 2b$ orthogonal block via Cayley transform.

3. Modified Forward Pass — the input $x \in \mathbb{R}^d$ is transformed as $z = (R(m, b) \cdot W^0)^\top x$, where $z \in \mathbb{R}^n$ is the output. Critically, after training, $R(m, b)$ can be multiplied into $W^0$ once, producing a modified weight matrix $W^{\text{finetuned}} = R(m, b) \cdot W^0$, eliminating any inference-time overhead.

Information flows as follows: the input vector $x$ enters the layer → the frozen pretrained weights $W^0$ project it to an $n$-dimensional space → the orthogonal butterfly matrix $R(m, b)$ applies a learned orthogonal transformation in the $d$-dimensional input space before the projection (since the multiplication $R \cdot W^0$ is applied to the weight matrix, not the activations—it transforms the neuron vectors themselves). In practice, $R(m, b)$ is applied to every linear layer in the transformer blocks (queries, keys, values, and MLP layers), each with its own independent butterfly-structured orthogonal matrix.

3.3 Roadmap for the Deep Dive

• First, the orthogonal finetuning base framework: the multiplicative reparameterization $R \cdot W^0$, the Cayley parameterization that enforces orthogonality without projection, and why this approach preserves spectral properties and pairwise angles. This establishes the geometric foundation that BOFT inherits.

• Second, the information transmission framework: the reinterpretation of matrix factorization as routing information through a grid-structured graph, the formal desiderata (dense connectivity, minimum edges), and why this perspective naturally motivates butterfly structures. This provides the conceptual bridge from "we need a dense orthogonal matrix" to "we can build one from sparse factors."

• Third, the butterfly factorization itself: the recursive definition of butterfly components, how the sparsity patterns interleave to achieve dense connectivity, how orthogonality is enforced on each component, and the resulting parameter count formula. This is the core algorithmic contribution.

• Fourth, the block butterfly generalization: extending from scalar ($b=1$) butterfly matrices to block butterfly matrices where each non-zero entry is a $b \times b$ matrix, enabling a continuum of expressivity-regularity trade-offs between block-diagonal OFT and full butterfly matrices.

• Fifth, training-time mechanisms: identity initialization (so finetuning starts from the exact pretrained model), multiplicative dropout (since standard dropout doesn't apply to multiplicative updates), and the merging step that eliminates inference overhead.

• Sixth, theoretical properties: the expressivity theorem (BOFT subsumes OFT, and products of butterfly matrices can represent arbitrary orthogonal matrices), the spectral norm preservation guarantee, and the connection to classic linear transforms that provides BOFT's inductive bias.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily a methodological paper whose core idea is that dense orthogonal matrices—desirable for finetuning because they preserve pretrained geometric structure—can be made parameter-efficient by factorizing them into products of sparse orthogonal matrices with butterfly-structured sparsity patterns, where the butterfly graph is chosen because it achieves dense connectivity with $O(d \log d)$ edges, which is provably efficient in the information transmission sense.

---

The Orthogonal Finetuning Framework: Multiplicative Updates and Cayley Parameterization

BOFT inherits the fundamental reparameterization from OFT (Qiu et al., 2023). Given a pretrained linear layer with weight matrix $W^0 \in \mathbb{R}^{d \times n}$ (where $d$ is the input dimension and $n$ is the output dimension), the standard forward pass is $z = (W^0)^\top x$ for an input vector $x \in \mathbb{R}^d$. OFT modifies this to:

$z = (R \cdot W^0)^\top x$

where $R \in \mathbb{R}^{d \times d}$ is a learnable orthogonal matrix.

What this computes: the orthogonal matrix $R$ transforms the neuron vectors of $W^0$ before they are applied to the input. Specifically, the $i$-th column of $W^0$ (call it $w_i^0 \in \mathbb{R}^d$) represents the $i$-th neuron. After applying $R$, the new neuron vector is $R \cdot w_i^0$. The forward pass computes inner products between the input $x$ and these transformed neurons: $z_i = (R w_i^0)^\top x = (w_i^0)^\top R^\top x$. Equivalently, the input is first rotated by $R^\top$ and then compared to the original neurons.

Why this form: the multiplicative update has three critical geometric properties that the paper argues are beneficial for finetuning:

1. Pairwise angle preservation: The angle between any two neuron vectors $w_i^0$ and $w_j^0$ is determined by their inner product $\langle w_i^0, w_j^0 \rangle$. Under the orthogonal transformation, the inner product becomes $\langle R w_i^0, R w_j^0 \rangle = (w_i^0)^\top R^\top R w_j^0 = \langle w_i^0, w_j^0 \rangle$, which is unchanged because $R^\top R = I$. This means the semantic relationships encoded in the pretrained weight matrix's geometry are provably preserved—the model cannot catastrophically distort the relative organization of its knowledge.

2. Spectral norm preservation: The spectral norm (largest singular value) of $W^0$ is unchanged by left-multiplication with an orthogonal matrix, since $\|R W^0\|_2 = \|W^0\|_2$. The paper cites prior work (Miyato et al., 2018; Yoshida and Miyato, 2017) showing that spectral norm control benefits training stability and generalization. In contrast, LoRA's additive update $W^0 + AB$ can increase the spectral norm, potentially destabilizing training.

3. Rotation rather than scaling: Orthogonal transformations are isometries—they preserve distances. This means the update cannot arbitrarily amplify or attenuate certain directions in the input space; it can only reorient them. This provides a strong regularization that prevents overfitting, particularly important when finetuning on small downstream datasets.

Enforcing orthogonality via Cayley parameterization: The paper follows Liu et al. (2021) and Qiu et al. (2023) in using the Cayley transform to parameterize orthogonal matrices without requiring expensive projection steps during training. The Cayley parameterization is:

$R = (I + Q)(I - Q)^{-1}$

where $Q \in \mathbb{R}^{d \times d}$ is a skew-symmetric matrix satisfying $Q = -Q^\top$, and $I$ is the identity matrix.

What this computes: given any skew-symmetric matrix $Q$, the Cayley transform produces an orthogonal matrix $R$. The mapping is a bijection between the space of skew-symmetric matrices and the space of orthogonal matrices with no eigenvalue equal to $-1$ (the special orthogonal group up to a measure-zero set).

Why this form: parameterizing $Q$ directly (rather than $R$) has three key advantages:

1. Unconstrained optimization: $Q$ can be any skew-symmetric matrix—there are no constraints to satisfy during gradient descent. The skew-symmetry is enforced by construction (only the upper-triangular entries are stored; the lower-triangular entries are their negatives, and the diagonal is zero). A full $d \times d$ orthogonal matrix has $d(d-1)/2$ degrees of freedom, exactly matching the number of free parameters in a skew-symmetric matrix.

2. No projection required: Alternative approaches to orthogonal optimization (e.g., projecting onto the Stiefel manifold via SVD after each gradient step) are computationally expensive and can interfere with optimization dynamics. The Cayley parameterization stays on the orthogonal manifold by construction.

3. Simple identity initialization: When $Q = 0$ (the zero matrix), the Cayley transform yields $R = I \cdot I^{-1} = I$, the identity matrix. This means finetuning starts from the exact pretrained model—the same principle LoRA follows with its zero initialization.

The key insight that BOFT builds on is that the Cayley parameterization can be applied to any matrix that needs to be orthogonal, including the individual blocks within the butterfly components. This is what enables the sparse factorization: each small $2b \times 2b$ orthogonal block is independently parameterized via its own $2b \times 2b$ skew-symmetric matrix.

---

The Information Transmission Framework: From Dense Matrices to Sparse Factorization

The paper introduces a novel conceptual framework for understanding the problem of building a dense orthogonal matrix from sparse factors. The key observation is that matrix multiplication can be interpreted as information flow on a graph.

Setup: Consider representing a dense matrix $R \in \mathbb{R}^{d \times d}$ as the product of $m$ square matrices:

$R = B_m B_{m-1} \cdots B_1$

where each $B_i \in \mathbb{R}^{d \times d}$ is a sparse matrix with some specified non-zero pattern.

The graph interpretation: Picture a grid of $d \times (m+1)$ nodes arranged in $m+1$ columns (levels), each with $d$ nodes. The column on the far left (level 0) represents the input dimensions; the column on the far right (level $m$) represents the output dimensions. Each intermediate matrix $B_i$ defines the connectivity from level $i-1$ to level $i$: if the $(j_1, j_2)$ element of $B_i$ is non-zero, there is a directed edge from the $j_2$-th node in level $i-1$ to the $j_1$-th node in level $i$. A zero in that position means no edge exists.

What the product computes: for the full product $R$ to have a non-zero entry at position $(j_1, j_2)$, there must exist at least one path from the $j_2$-th node in level 0 to the $j_1$-th node in level $m$, traversing one edge per level. The value at $R_{j_1, j_2}$ is the sum over all such paths of the product of edge weights along each path. So a dense $R$ requires that every source node can reach every destination node—what the paper calls dense connectivity.

The orthogonality constraint on edges: For each $B_i$ to be orthogonal, it must be full-rank (a necessary condition), which requires at least $d$ non-zero entries forming a bijection between level $i-1$ and level $i$. These $d$ edges are not "trainable" in the usual sense—for a $d \times d$ orthogonal matrix with exactly $d$ non-zero entries, those entries can only be $\pm 1$ (permutation matrices). To have learnable parameters, we need more than $d$ edges. The paper's desideratum is minimum free edges: the total number of trainable non-zero entries across all $B_i$ should be as small as possible while still achieving dense connectivity and satisfying orthogonality.

Example from the paper: Figure 2 illustrates this with $d=4$ and $m=5$. The five sparse matrices $B_1$ through $B_5$ collectively create a connectivity pattern where:

• $B_2 B_1$ (product of first two matrices) connects source nodes to level 2, but node 1 at level 0 cannot reach node 3 at level 2—so the product is not yet dense.
• $B_3 B_2 B_1$ adds more paths and increases connectivity.
• By $B_5 B_4 B_3 B_2 B_1$, every source node can reach every destination node—the product is dense.

The total number of edges in this example is 10, which is actually less than the $4^2 - 4 = 12$ trainable edges of a single dense $4 \times 4$ orthogonal matrix (remembering that orthogonality imposes $d$ constraints, removing $d$ degrees of freedom). This counterintuitive result—that factorization can be more parameter-efficient than a single dense matrix—is central to the paper's approach.

Why this framework matters: it transforms the problem from "find a good sparse factorization" (which seems ad hoc) to "find a good graph topology for information transmission" (which connects to a rich literature in computer networking). The paper explicitly notes this in Section 7:

"Our information transmission framework further enables us to draw inspiration from a distinct research discipline – computer networking, where the efficiency of a network topology for transmitting information is heavily studied."

The butterfly graph from the Cooley-Tukey FFT algorithm is a canonical example of a network topology that achieves dense connectivity between $d$ inputs and $d$ outputs using exactly $O(d \log d)$ edges—the theoretical minimum for certain classes of networks. This is what makes it the natural choice within this framework.

---

Butterfly Factorization: Recursive Sparse Matrix Construction

The butterfly structure is built from a fundamental building block called a butterfly factor, defined for any even dimension $k$ (where $k \geq 2$ is a power of 2) as:

$BF(k) = \begin{pmatrix} \text{diag}(d_1) & \text{diag}(d_2) \\ \text{diag}(d_3) & \text{diag}(d_4) \end{pmatrix} \in \mathbb{R}^{k \times k}$

where $\text{diag}(d_i)$ denotes a diagonal matrix with the vector $d_i \in \mathbb{R}^{k/2}$ on its diagonal, for $i = 1, 2, 3, 4$.

What this computes: a butterfly factor is a $k \times k$ matrix with exactly $2k$ non-zero entries—the $k/2$ entries on the diagonal of each of the four quadrants. In the information transmission view, this connects each of the $k$ nodes at one level to exactly two nodes at the next level (one in the "top half" and one in the "bottom half"). The key structural property is that each node has out-degree 2, and the connections are structured so that nodes in the first half connect to corresponding positions in both halves, and similarly for the second half.

Building the full butterfly matrix recursively: For dimension $d = 2^N$, the butterfly matrix $B(d) \in \mathbb{R}^{d \times d}$ is defined recursively:

$B(d) = \tilde{B}(d, d) \cdot \begin{pmatrix} B_1(d/2) & 0 \\ 0 & B_2(d/2) \end{pmatrix}$

where $B_1(d/2)$ and $B_2(d/2)$ are two independent $d/2$-dimensional butterfly matrices, and $\tilde{B}(d, d)$ is a butterfly component (defined below). Recursing down to the base case $d=2$, this expands to:

$B(d) = \tilde{B}(d, d) \cdot \tilde{B}(d, d/2) \cdot \tilde{B}(d, d/4) \cdots \tilde{B}(d, 2)$

where each butterfly component $\tilde{B}(d, k)$ is a block-diagonal matrix of size $d \times d$ with block size $k$:

$\tilde{B}(d, k) = \text{diag}(BF_1(k), BF_2(k), \ldots, BF_{d/k}(k))$

That is, $\tilde{B}(d, k)$ places $d/k$ copies of the $k \times k$ butterfly factor $BF(k)$ along the diagonal. For example, with $d=8$:

• $\tilde{B}(8, 2)$ is block-diagonal with four $2 \times 2$ blocks.
• $\tilde{B}(8, 4)$ is block-diagonal with two $4 \times 4$ blocks.
• $\tilde{B}(8, 8)$ is a single $8 \times 8$ butterfly factor.

The product of all $\log_2 d$ components (from $k=2$ up to $k=d$) produces a dense $d \times d$ matrix. The recursive structure of the butterfly means that information is mixed progressively: the $\tilde{B}(d, 2)$ component allows information exchange within pairs; $\tilde{B}(d, 4)$ allows exchange between pairs within quartets; $\tilde{B}(d, 8)$ allows exchange between quartets within octets; and so on until global mixing is achieved.

Enforcing orthogonality on each component: The core technical challenge is ensuring that each butterfly component $\tilde{B}(d, k)$ is an orthogonal matrix. The paper's solution relies on two observations:

1. Orthogonality of $\tilde{B}(d, 2)$: The component with the smallest block size ($k=2$) is block-diagonal with $d/2$ independent $2 \times 2$ blocks, each of the form $\begin{pmatrix} a_i & b_i \\ c_i & d_i \end{pmatrix}$. Each $2 \times 2$ block can be easily parameterized as an orthogonal matrix—for example, as a 2D rotation matrix $\begin{pmatrix} \cos \theta_i & \sin \theta_i \\ -\sin \theta_i & \cos \theta_i \end{pmatrix}$ (a subset of orthogonal matrices) or via its own $2 \times 2$ Cayley parameterization (covering all orthogonal $2 \times 2$ matrices with determinant $+1$).

2. Permutation equivalence of larger components: Every butterfly component $\tilde{B}(d, k)$ for $k > 2$ has the same non-zero pattern as $\tilde{B}(d, 2)$, just permuted. Specifically, $\tilde{B}(d, k)$ can be obtained from a block-diagonal matrix with $2 \times 2$ blocks by applying a permutation that rearranges rows and columns to group together the nodes that need to communicate at scale $k$. Since permutation matrices are themselves orthogonal, and the product of orthogonal matrices is orthogonal, each $\tilde{B}(d, k)$ can be made orthogonal by:

   • Starting with a block-diagonal orthogonal matrix with $d/2$ independent $2 \times 2$ orthogonal blocks (parameterized via Cayley).
   • Applying learned permutations (the structural pattern of the butterfly) to rearrange the blocks into the required sparsity pattern.

   In practice, this is done implicitly by the structure of the butterfly component itself—it is parameterized directly in its permuted form, with each of its constituent $BF_i(k)$ factors being orthogonal.

The complete orthogonal butterfly matrix: Combining all components, the final orthogonal matrix used in BOFT is:

$R(m, b) = \prod_{i=1}^{m} \tilde{B}_b(d, i)$

where each $\tilde{B}_b(d, i)$ is an orthogonal butterfly component (the subscript $b$ indicates the block size generalization, discussed next), and the product is over $m$ components. The orthogonality of each component $\tilde{B}_b(d, i)^\top \tilde{B}_b(d, i) = I_d$ guarantees that $R(m, b)$ is also orthogonal (the product of orthogonal matrices is orthogonal).

Parameter count: For a butterfly component $\tilde{B}_b(d, 2)$ with $d/2$ independent $2b \times 2b$ orthogonal blocks, each $2b \times 2b$ orthogonal matrix has $2b(2b-1)/2 = b(2b-1)$ degrees of freedom (the dimension of the skew-symmetric matrix in Cayley parameterization). So $\tilde{B}_b(d, 2)$ uses $(d/2) \cdot b(2b-1) = \frac{1}{2} b(2b-1) d$ parameters. The other components $\tilde{B}_b(d, k)$ for $k > 2$ have the same non-zero pattern up to permutation, so they each use the same number of parameters. With $m$ components, the total is:

\text{#params} = \frac{1}{2} m b (2b-1) d \approx m b^2 d

where the approximation holds for large $b$. For the scalar butterfly ($b=1$), this simplifies to $\frac{1}{2} m d$ parameters, or approximately $m d / 2$. When using the full butterfly with $m = \log_2 d$ and $b=1$, this gives $\frac{1}{2} d \log_2 d = O(d \log d)$ parameters—compared to $O(d^2)$ for a dense orthogonal matrix.

The paper also provides a more general formula: BOFT with parameters $(m, b)$ uses $\frac{1}{2}(b-1) d m$ effective trainable parameters for finetuning a linear layer of size $d \times n$. The discrepancy with the formula above (using $b-1$ instead of $b(2b-1)/2$) arises because the paper counts parameters differently in this statement—the exact parameterization details depend on how the Cayley transform is applied to the $2b \times 2b$ blocks.

---

Block Butterfly Generalization: Trading Off Expressivity and Parameter Count

The paper generalizes the scalar butterfly ($b=1$) to block butterfly matrices where each non-zero entry in the butterfly components becomes a $b \times b$ matrix rather than a scalar. This generalization is essential because it provides a continuum between:

• BOFT(1, b): $m=1$ component, block size $b$. This produces a block-diagonal orthogonal matrix with block size $2b$—exactly recovering OFT with block size $2b$.
• BOFT($\log_2 d$, 1): full scalar butterfly, producing a dense orthogonal matrix using $O(d \log d)$ parameters.
• BOFT($m$, $b$) for intermediate $m$: partially factorized matrices that are denser than block-diagonal but sparser than full butterfly, using $m$ butterfly components with $b \times b$ blocks.

Formally, a block butterfly component $\tilde{B}_b(d, k)$ has the same sparsity pattern as $\tilde{B}(d, k)$ but with each scalar entry replaced by a $b \times b$ matrix. For $\tilde{B}_b(d, 2)$ (the base case), each $2 \times 2$ block in the scalar version becomes a $2b \times 2b$ block matrix that must be orthogonal. This $2b \times 2b$ block is parameterized using the Cayley transform with a $2b \times 2b$ skew-symmetric matrix, which has $b(2b-1)$ parameters.

Why this generalization matters: it allows practitioners to choose a point on the expressivity-regularity spectrum that is appropriate for their task and parameter budget. The paper argues that "better expressiveness does not always lead to better performance in finetuning" (Section 5)—the trade-off between the capacity to adapt and the regularization that prevents overfitting is crucial. The block butterfly provides finer-grained control over this trade-off than either pure OFT or pure scalar butterfly:

• Smaller $b$, larger $m$: more factorization, denser final matrix, higher expressivity, more parameters (but sub-quadratic in $d$). Example: BOFT(6, 2) uses $\frac{1}{2} \cdot 2 \cdot 6 \cdot d = 6d$ parameters and produces a dense matrix.
• Larger $b$, smaller $m$: less factorization, block-diagonal structure dominates, lower expressivity, fewer parameters. Example: BOFT(1, 16) uses $\frac{1}{2} \cdot 16 \cdot 1 \cdot d = 8d$ parameters and produces a block-diagonal matrix with $32 \times 32$ blocks.

The paper's experiments in Table 4 systematically explore this spectrum: BOFT(m=2, b=8) with 1.99M parameters, BOFT(m=4, b=4) with 1.77M parameters, and BOFT(m=6, b=2) with 1.11M parameters all achieve strong performance on VTAB-1K, with the middle configuration (m=4, b=4) reaching the highest average accuracy (77.9%). This validates the paper's claim that intermediate points on the spectrum can outperform both extremes.

Expressivity comparison (Figure 5): The paper empirically evaluates how well BOFT can approximate random dense orthogonal matrices. For $d=512$, a random orthogonal matrix is generated and BOFT configurations with varying $(m, b)$ are optimized to minimize the approximation error. Key findings:

• BOFT(9, 2)—the full scalar butterfly—achieves better approximation (lower error) than BOFT(1, 16)—the block-diagonal OFT—while using fewer parameters. This directly demonstrates BOFT's superior parameter efficiency.
• Configurations with smaller $b$ and larger $m$ generally achieve better parameter efficiency: the curves for $b=2$ and $b=4$ lie below (better) than those for $b=16$ at the same parameter count.
• BOFT(6, 4) achieves similar approximation error to BOFT(2, 16) but with "much less parameters" (exact numbers from the figure show the former around $3 \times 10^3$ and the latter around $10^4$).

Theorem 1 (Expressivity): The paper states this theorem formally:

"BOFT is more expressive than OFT with the same block size. For the butterfly matrix to approximate all orthogonal matrices of size $d$, we can multiply butterfly matrices with $B_{d-1,1}(d) B_{d-1,2}^\top(d) \cdots B_{1,1}(d) B_{1,2}^\top(d)$, where $B_{i,j}(d), \forall i, \forall j$ are butterfly matrices."

The proof (Appendix F) has two parts:

1. BOFT(m, b) with $m > 1$ is more expressive than OFT with block size $2b$ because we can set all but the first butterfly component to identity, reducing BOFT(m, b) to OFT(2b). Since BOFT can represent everything OFT can, and more (by using non-identity values in the other components), it is strictly more expressive.
2. The product $B_{d-1,1}(d) B_{d-1,2}^\top(d) \cdots B_{1,1}(d) B_{1,2}^\top(d)$ can represent any orthogonal matrix because it falls into the category of kaleidoscope matrices (Dao et al., 2020), which have been proven to be universal approximators for the orthogonal group. The proof uses QR factorization: any orthogonal matrix can be decomposed into $d-1$ Householder reflections, and each Householder reflection can be represented as $B_i(d) B_i^\top(d)$ for some butterfly matrix $B_i(d)$.

This theorem establishes that the butterfly structure does not fundamentally limit expressivity—with enough factors, it can represent the entire orthogonal group. In practice, the paper uses far fewer factors (typically $m = 2$ to $m = 6$), relying on the inductive bias of the butterfly structure to generalize better than a fully unconstrained orthogonal matrix would.

---

Training-Time Mechanisms: Initialization, Dropout, and Merging

Identity initialization: BOFT initializes all butterfly components to identity matrices so that finetuning starts from the exact pretrained model. Specifically, in the Cayley parameterization of each $2b \times 2b$ orthogonal block, the skew-symmetric matrix $Q$ is initialized as the zero matrix, yielding $R = (I + 0)(I - 0)^{-1} = I$. When all components are identity, the product $R(m, b) = I \cdot I \cdots I = I$, so the forward pass $(R(m, b) \cdot W^0)^\top x = (W^0)^\top x$ is exactly the pretrained model's computation. This follows the same principle as LoRA's zero initialization of the low-rank update: the finetuned model should not deviate from the pretrained model until the data provides a reason to do so.

Multiplicative dropout: The paper notes that standard dropout (randomly zeroing activations) works naturally for LoRA's additive updates but not for BOFT's multiplicative updates—zeroing elements of an orthogonal matrix would break orthogonality. Instead, the paper proposes a multiplicative dropout that operates at the structural level:

1. Component-level dropout: Randomly select $p_1$ percent of the $m$ butterfly components and replace them with identity matrices. This effectively removes those components from the product for that training step.
2. Block-level dropout: Within each remaining butterfly component, randomly select $p_2$ percent of the diagonal blocks (the $2b \times 2b$ orthogonal matrices) and replace them with $2b \times 2b$ identity matrices.

The effect is to randomly reduce the expressivity of $R(m, b)$ during training, preventing co-adaptation between components and blocks. Since replacing a block or component with identity is equivalent to "skipping" that transformation, the dropout encourages the model to learn robust transformations that work even when some mixing stages are absent. The paper uses $p_2 = 0.1$ (10% block dropout) in most experiments (Tables 7, 8, and the SAM and diffusion model sections).

Merging for zero inference overhead: After training, the learned orthogonal matrix $R(m, b)$ can be multiplied into the pretrained weight matrix $W^0$ to produce a single modified weight matrix $W^{\text{finetuned}} = R(m, b) \cdot W^0$. This is a one-time operation (done once after training, not at every inference step) and the resulting model uses exactly the same forward pass as the original: $z = (W^{\text{finetuned}})^\top x$. This means BOFT introduces no additional parameters, computation, or latency at inference time—a critical practical advantage over adapter-based methods that insert new layers into the model. This property is shared with LoRA and OFT, which can similarly merge their learned updates into the pretrained weights.

Comparison with LoRA's inference merging: LoRA merges $W^0 + AB$ into a single matrix, which is straightforward matrix addition. BOFT merges $R(m, b) \cdot W^0$, which is matrix multiplication. For large $d$, the multiplication $R(m, b) \cdot W^0$ can be expensive, but it is done only once and the $R(m, b)$ matrix itself is never explicitly formed as a dense matrix during training (the butterfly factors are applied sequentially). The paper does not provide details on the computational cost of this one-time merge operation, which could be a practical consideration for very large models.

---

Spectral Properties and Geometric Preservation

The paper emphasizes that BOFT, like OFT, preserves the spectral norm of the pretrained weight matrix. This can be seen through the singular value decomposition (SVD):

Claim: If $W^0 = U \Sigma V^\top$ (where $U, V$ are orthogonal and $\Sigma$ is the diagonal matrix of singular values), then the finetuned weight matrix is $W^{\text{ft}} = R(m, b) U \Sigma V^\top$. Since $R(m, b)$ is orthogonal, $R(m, b) U$ is also orthogonal (product of two orthogonal matrices), so $W^{\text{ft}} = (R(m, b) U) \Sigma V^\top = U' \Sigma V^\top$ has exactly the same singular values as $W^0$.

What this means: the spectral norm $\|W^{\text{ft}}\|_2 = \sigma_{\max}(\Sigma) = \|W^0\|_2$ is unchanged. The largest singular value, which controls the Lipschitz constant of the linear layer and is a key determinant of training stability (Miyato et al., 2018), is perfectly preserved. The paper contrasts this with LoRA, where the additive update $W^0 + AB$ does not preserve singular values and can increase the spectral norm, potentially causing training instability.

Pairwise angle preservation in more detail: The paper frames orthgonal finetuning as learning a bilinear similarity. For the $i$-th neuron (column $w_i^0$ of $W^0$), the finetuned output is:

$z_i = (R w_i^0)^\top x = (w_i^0)^\top R^\top x$

This can be viewed as learning a bilinear form $R^\top$ that defines a new similarity metric between the pretrained neuron and the input. The orthogonality constraint on $R$ ensures this is a valid distance metric learning problem (connected to the distance metric learning literature, Xing et al., 2002) and that the learned similarities respect the geometry of the original feature space.

Connection to hyperspherical energy: The paper references prior work (Liu et al., 2018) showing that the pairwise angles between neuron vectors characterize the "hyperspherical energy" of the weight matrix—a measure of how uniformly the neurons are distributed on the hypersphere. Preserving these angles through orthogonal transformation maintains the hyperspherical energy, which has been linked to better generalization. This provides a theoretical justification for why orthogonal finetuning (and BOFT specifically) should generalize well.

Input sensitivity (Appendix G.4): The paper provides additional theoretical properties of orthogonal butterfly matrices. Proposition 3 shows that for simple scalar butterfly matrices $OB(\theta)$ parameterized by $n$ angles (where $d = 2^n$), the Frobenius norm sensitivity to parameter perturbations $\epsilon$ is bounded by $\sqrt{d} \|\epsilon\|_1$. That is:

$\|OB(\theta) - OB(\theta + \epsilon)\|_F \leq \sqrt{d} \|\epsilon\|_1$

This Lipschitz continuity means that small changes in the learned parameters cannot cause disproportionately large changes in the orthogonal matrix, contributing to training stability. The bound is dimension-dependent ($\sqrt{d}$), which is an inevitable consequence of composing $n$ matrices—errors can accumulate, but the accumulation is controlled.

---

Weight Interpolation: An Emergent Property

A surprising empirical discovery, highlighted in Section 6.3 and Figure 10, is that the factorized structure of BOFT enables free weight interpolation on the orthogonal manifold without retraining. The paper uses BOFT with $m=5, r=16$ (note: here the paper switches notation to use $r$ for the number of blocks, where $r = d/b$; this translates to $m=5$ butterfly components with block size $b = d/16$).

The interpolation procedure: After training, the $m$ butterfly components $\tilde{B}_b(d, 1), \tilde{B}_b(d, 2), \ldots, \tilde{B}_b(d, m)$ are progressively set to identity matrices, starting from the leftmost component (the first factor in the product). Setting $k$ components to identity (out of $m$) produces an interpolated model with $m-k$ active components. The extremes are:

• All $m$ components active: the full BOFT-finetuned model.
• All components set to identity: the original Stable Diffusion model (since the control head is still present, this is the "Stable Diffusion with a learned control head" baseline).

Figure 10 results: As butterfly components are progressively removed (from 6 matrices → 5 → 4 → 3 → 2 → 1 → 0), the generated images smoothly interpolate between the fully controlled output (face following the landmark control signal) and an uncontrolled output (face without landmark guidance). Critically, no retraining is performed—the interpolation is done purely by manipulating the learned butterfly components post-hoc. The paper interprets this as evidence that:

"the hypothesis weight space (i.e., model space) in BOFT can well preserve the semantics and effectively eliminate many bad local minima."

Why this works: each butterfly component $\tilde{B}_b(d, i)$ represents an orthogonal transformation that mixes information at a particular scale (pairs, quartets, octets, etc.). Removing components is equivalent to coarsening the mixing granularity—the model retains low-level mixing but loses high-level mixing, producing a natural semantic interpolation between "controlled" and "uncontrolled." The fact that this interpolation produces plausible images (rather than degenerate outputs) suggests that the optimization landscape in the factorized orthogonal space is well-behaved, with the components organizing hierarchically rather than becoming co-adapted in brittle ways. This property is unique to BOFT among the compared methods—LoRA and block-diagonal OFT do not offer a natural interpolation procedure.

---

Summary of Design Choices and Their Justifications

• Multiplicative orthogonal update over additive low-rank update: preserves pairwise angles and spectral norm, providing theoretical guarantees of training stability and geometric regularization that LoRA lacks. The orthogonal constraint acts as a structural prior that prevents the model from deviating too far from the pretrained representations.

• Butterfly factorization over single dense orthogonal matrix: reduces parameters from $O(d^2)$ to $O(d \log d)$ while maintaining the ability to approximate arbitrary orthogonal transforms (Theorem 1). The butterfly structure is chosen specifically because it achieves the minimum edge count for dense connectivity in the information transmission framework—a property that emerges from its roots in the FFT algorithm.

• Block butterfly generalization over pure scalar butterfly: provides a continuum between block-diagonal OFT ($m=1$) and full butterfly ($m = \log_2 d, b=1$), enabling practitioners to select the appropriate expressivity-regularity trade-off for their task and parameter budget. This is essential because maximum expressivity is not always optimal—the inductive bias of the butterfly structure is beneficial for generalization.

• Cayley parameterization over projection-based orthogonal optimization: enables unconstrained gradient-based optimization while staying exactly on the orthogonal manifold. Alternative approaches (e.g., projecting onto the Stiefel manifold via SVD after gradient steps) are computationally expensive and can interfere with optimization dynamics.

• Identity initialization for all butterfly components: ensures finetuning starts from the exact pretrained model, matching the principle used by LoRA and other PEFT methods. This is critical for preserving pretrained knowledge in the early stages of finetuning.

• Multiplicative dropout over standard dropout: operates at the structural level (replacing whole blocks or components with identity) rather than zeroing individual parameters, which would break orthogonality. The two-level dropout (component-level and block-level) prevents co-adaptation and improves generalization.

• Per-layer independent $R(m, b)$ matrices: each linear layer in the transformer (queries, keys, values, MLP layers) gets its own independent orthogonal butterfly matrix, allowing different layers to adapt differently. The paper applies BOFT to "every linear layer in every transformer block" (Appendix A.1 for GLUE, A.2 for VTAB-1K) and to the attention projection layers in Stable Diffusion (Appendix A.5: {to_q, to_v, to_k, query, value, key} in the UNet).

• Layer-shared butterfly structure: while each layer has independent parameters, the butterfly structure (the sparsity pattern, the number of components $m$, the block size $b$) is shared across layers. This is a design choice that simplifies hyperparameter tuning—only $m$ and $b$ need to be selected globally, rather than per-layer.

• Excluding the classification head from parameter counting: Following standard practice in VTAB-1K and GLUE evaluations, the final task-specific classification layer is retrained from scratch and its parameters are not counted toward the PEFT parameter budget. The paper states this explicitly for VTAB-1K (Section 6.2): "we follow the common practice and do not take them into account when reporting the total trainable parameters for each method."

4. Key Insights and Innovations

Innovation 1: Information Transmission as a Unifying Framework for Parameter-Efficient Orthogonal Matrices

The paper's most intellectually distinctive move is not the butterfly structure itself—butterfly matrices existed in numerical linear algebra and ML before this work—but rather the reframing of sparse orthogonal matrix factorization as an information transmission problem on a grid-structured graph. This conceptual lens transforms what appears to be an arbitrary combinatorial search (find a set of sparse matrices whose product is dense and orthogonal) into a principled design problem with clear desiderata and connections to a mature engineering discipline: network topology design.

Prior to this work, the dominant approach to making orthogonal matrices parameter-efficient was the block-diagonal structure used in OFT (Qiu et al., 2023): partition dimensions into groups and apply independent orthogonal transformations within each group. This is a reasonable heuristic—it reduces parameters—but it is fundamentally ad hoc. There is no principled justification for why dimension 1–16 should be grouped together versus dimension 1, 17, 33, … (stride-based grouping). The block-diagonal choice is one point in a large space of possible sparsity patterns, selected primarily for simplicity, not optimality.

The information transmission framework changes the question from "what sparsity pattern should we use?" to "what network topology efficiently routes information between all input-output pairs?" This reframing is powerful for three reasons:

First, it makes the design desiderata explicit and measurable. The paper defines two criteria—dense connectivity (every source reaches every destination) and minimum free edges (fewest trainable non-zero entries)—that any candidate factorization must satisfy. These are not vague intuitions about "good structure"; they are precise graph-theoretic properties that can be analyzed and optimized. The framework reveals, for instance, that the naive block-diagonal structure fails the dense connectivity criterion entirely (Figure 3): information from nodes in one block can never reach nodes in another block, making the final transformation block-diagonal rather than dense.

Second, it connects orthogonal finetuning to a rich external literature. The paper explicitly notes in Section 7 that network topology design—studied extensively in computer networking for decades—becomes directly relevant. Topologies like butterfly, hypercube, de Bruijn, and Clos networks have been analyzed for their information routing efficiency, fault tolerance, and latency properties. The butterfly graph, in particular, is known to achieve dense connectivity with $O(d \log d)$ edges—the theoretical minimum for certain network models. By importing this result, the paper provides a principled answer to "why butterfly?" that goes beyond "it worked in the FFT."

Third, it opens a systematic research direction. The framework does not just justify the butterfly structure—it provides a methodology for discovering better structures. The paper explicitly flags this in Section 7: "whether the butterfly network is the most efficient way to transmit information is also unknown." Different network topologies might offer better trade-offs between parameter count, expressivity, training stability, or domain-specific inductive bias. The information transmission framework transforms the search for sparse orthogonal factorizations from guesswork into a structured exploration over known network topologies—a fundamentally more scientific approach.

This is a fundamental conceptual contribution, not an incremental refinement. It changes how one thinks about the problem: from "we need a sparse approximation to a dense orthogonal matrix" to "we need to design an efficient communication network on $d$ nodes." The fact that this reframing leads naturally to the butterfly structure (which was separately known from signal processing) is evidence of the framework's explanatory power—it recovers a known good solution from first principles and points toward systematic improvements.

---

Innovation 2: The Block Butterfly as a Smooth Expressivity-Regularity Continuum Within the Orthogonal Group

A second major contribution is the recognition that the parameter-efficiency problem in orthogonal finetuning is fundamentally about navigating a spectrum between regularity (identity matrices) and expressivity (full orthogonal group), and that the block butterfly provides a finer-grained, more principled interpolation along this spectrum than the block-diagonal structure.

The original OFT (Qiu et al., 2023) offers exactly two knobs: the block size $b$ (which controls parameter count and expressivity) and whether to use a full or block-diagonal orthogonal matrix (a binary choice). The block-diagonal structure with larger blocks is more expressive but uses more parameters; smaller blocks use fewer parameters but restrict expressivity more severely. This is a coarse trade-off: for a given parameter budget, you pick a block size and accept whatever expressivity that block size provides.

BOFT introduces a fundamentally different parameterization. By varying both the number of butterfly components $m$ and the block size $b$, the method can produce matrices that are partially factorized—denser than block-diagonal but sparser than fully dense—with a continuous interpolation between the extremes. Concretely:

• BOFT(1, b): one component, block size $b$ → pure block-diagonal orthogonal matrix (OFT with block size $2b$). This is the "high regularity, low expressivity" extreme.
• BOFT(log₂(d/b), b): full butterfly, $\log_2(d/b)$ components → dense orthogonal matrix. This is the "high expressivity, lower regularity" extreme.
• BOFT(m, b) for intermediate $m$: partially factorized matrices that mix information at $m$ scales rather than $\log_2(d/b)$ scales. These occupy intermediate points on the spectrum.

What makes this innovation significant is that it parameterizes a hypothesis class within the orthogonal group, rather than treating the orthogonal group as a monolithic entity. The paper's insight is that the best generalization in finetuning often comes not from maximum expressivity (full orthogonal group, or full finetuning) nor from maximum regularity (identity, i.e., no finetuning), but from a structured subset that captures the inductive biases of the adaptation task. Prior work implicitly recognized this—OFT with small blocks outperforms full orthogonal matrices in many settings—but offered no systematic way to explore the space between block-diagonal and fully dense.

The empirical validation is striking. Table 4 (VTAB-1K) shows BOFT(m=4, b=4) achieving 77.9% average accuracy versus BOFT(m=2, b=8) at 77.4% and BOFT(m=6, b=2) at 77.1%—all three outperform both the block-diagonal extreme (OFT b=16 at 77.3%) and full finetuning (74.6%). The fact that the intermediate configuration (m=4, b=4) performs best across 19 diverse vision tasks suggests that the "sweet spot" on this spectrum is genuinely task-agnostic, reflecting a fundamental property of how adaptation benefits from structured expressivity rather than being task-specific.

The expressivity experiment (Figure 5) provides complementary evidence: BOFT(9, 2)—the full scalar butterfly—achieves better approximation of arbitrary orthogonal matrices than OFT with block size 16, while using fewer parameters. This is a clean demonstration that the butterfly structure extracts more expressivity per parameter than the block-diagonal structure, even at the same point on the "dense vs. sparse" spectrum. The block butterfly is not just a different way to be sparse; it is a more efficient way to be sparse.

This contribution is best understood as an architectural innovation in the design space of orthogonal constraints. It does not change what orthogonal finetuning computes (still $R \cdot W^0$ with $R$ orthogonal) or why it works (still geometric preservation), but it dramatically expands the set of $R$ matrices that can be practically represented and learned. This expansion is enabled by the butterfly factorization but the intellectual contribution is the recognition that this expansion is valuable—that the space between block-diagonal and fully dense is where good generalization lives, and that a principled interpolation through this space is a first-order design decision, not an afterthought.

---

Innovation 3: Structural Inductive Bias from Classic Linear Transforms as a Generalization Mechanism

The paper argues that the butterfly structure is not just parameter-efficient but beneficially inductive-biased because it shares a structural pattern with many classic linear transforms—the discrete Fourier transform, discrete cosine transform, discrete sine transform, and Hadamard transform. This is a conceptual move that elevates the butterfly structure from a computational convenience to a regularization mechanism with theoretical justification.

The argument, developed in Section 5, works as follows: the butterfly graph is the computational backbone of the Cooley-Tukey FFT algorithm. This means that many well-known orthogonal transforms—which are known to be useful for signal processing, compression, and feature extraction—can be exactly represented by butterfly-structured matrices. The Hadamard transform, for instance, is exactly a butterfly matrix with all $\pm 1$ entries. The Fourier transform is a butterfly matrix with complex exponential entries. These transforms work well for natural signals because they capture hierarchical, multi-scale structure—exactly the kind of structure that neural network representations are believed to develop.

By parameterizing the orthogonal matrix $R$ as a butterfly product, BOFT constrains the hypothesis class to matrices that share structural properties with these classic transforms, even though the specific entries are learned from data rather than fixed to Fourier or Hadamard values. This is a form of architecture-level inductive bias: the model can learn any butterfly-structured orthogonal matrix, but it cannot learn an orthogonal matrix that lacks the hierarchical mixing pattern of the butterfly graph.

Why might this bias be beneficial? The paper's intuition is that the transformations needed for finetuning—adjusting pretrained features to a new task—often involve re-weighting or re-combining features at multiple scales, which is exactly what butterfly-structured transforms do. A finetuning update that needs to globally mix all features (like a Fourier transform that converts between spatial and frequency domains) is naturally represented as a butterfly product. In contrast, the block-diagonal structure in OFT can only mix features within pre-specified groups, making global mixing impossible regardless of how the parameters are set.

The empirical evidence for this claim is not a single ablation but a pattern across multiple experiments:

• Table 2 (MMLU): BOFT(m=2, b=8) achieves 47.9% average accuracy versus OFT(b=16) at 47.5%, despite both producing a block-diagonal matrix with the same effective block structure (block size 16 in the final product). The difference is that BOFT constructs this block-diagonal matrix as the product of two partially mixing factors, while OFT constructs it as a single block-diagonal matrix. The fact that BOFT outperforms OFT even when the final sparsity pattern is identical suggests that the factorization itself—the path through the butterfly-structured space—provides a better optimization landscape, not just a different final expressivity.

• Table 3 (GSM8K/MATH): BOFT(m=2, b=8) at 0.12% parameters outperforms OFT(b=16) at 0.13% parameters (50.6 vs. 50.1 on GSM8K; 8.6 vs. 8.4 on MATH), again with matched final block structure but different construction paths.

• Table 4 (VTAB-1K): The consistent performance of intermediate BOFT configurations across 19 diverse tasks—natural images, medical images, satellite imagery, structured prediction—suggests the inductive bias is broadly useful, not domain-specific.

This contribution is an explanatory insight as much as a technical one. It provides a theoretical narrative for why butterfly-structured orthogonal matrices generalize well: they inhabit a region of the orthogonal group that is well-aligned with the multi-scale structure of natural data, as evidenced by the success of butterfly-based transforms across signal processing and scientific computing. This is a more satisfying justification than "the butterfly graph uses few edges," which explains parameter efficiency but not generalization.

The paper is appropriately cautious about this claim—it is presented as an argument ("we argue that the structured inductive bias… is beneficial to generalization") rather than a proven theorem. The causal mechanism (butterfly structure → shared pattern with classic transforms → better inductive bias → better generalization) is plausible but not experimentally isolated. For instance, there is no experiment comparing butterfly-structured orthogonal matrices to other sparse orthogonal structures that achieve similar parameter counts but lack the connection to classic transforms. This leaves open the possibility that any hierarchical sparsity pattern would work as well, and butterfly is simply the one the paper chose. The theoretical connection to classic transforms provides a principled reason to prefer butterfly over alternatives, but the empirical evidence for this specific preference remains correlational.

Nevertheless, framing the butterfly structure as a source of inductive bias—not just parameter efficiency—is a distinctive intellectual move that connects BOFT to broader themes in deep learning theory (the role of architecture in generalization, the implicit biases of structured matrices) and provides a roadmap for future work (can we design sparsity patterns that match the structure of other known useful transforms?).

---

Innovation 4: The Empirical Generalization of Orthogonal Finetuning Beyond Controllable Generation

While not a methodological innovation, the paper makes a significant empirical discovery: orthogonal finetuning, previously demonstrated only on controlling text-to-image diffusion models (Qiu et al., 2023), is a general-purpose PEFT method that matches or exceeds state-of-the-art across diverse modalities, tasks, and model families. This finding changes the landscape of PEFT by establishing multiplicative orthogonal updates as a viable alternative to additive low-rank updates across the board, not just in niche applications.

Prior to this work, the PEFT literature was dominated by LoRA and its variants. LoRA's additive low-rank updates were the default choice for NLP (Hu et al., 2022), vision (Chavan et al., 2023), and multimodal tasks. OFT existed but was confined to a single application (controllable generation) with a single model family (Stable Diffusion). It was unclear whether OFT's geometric preservation properties would translate to other domains, or whether the block-diagonal approximation was sufficient for general adaptation.

The paper systematically tests this across three modalities, four model families, and eight benchmarks:

• LLMs (DeBERTaV3, Llama-2): GLUE (8 NLP tasks), MMLU (57 language understanding tasks), GSM8K and MATH (mathematical reasoning)
• Vision (DINOv2, SAM): VTAB-1K (19 image classification tasks), HQSeg-44K (4 high-quality segmentation tasks)
• Diffusion (Stable Diffusion): controllable generation (landmark-to-face, segmentation-to-image), subject-driven generation (DreamBooth)

The pattern of results is remarkably consistent: orthogonal finetuning (either OFT or BOFT) matches or outperforms LoRA at comparable or smaller parameter budgets. Key data points:

• GLUE (Table 1): OFT(b=16) at 0.79M params achieves 89.77% average vs. LoRA(r=8) at 1.33M params with 88.50%. BOFT(m=2, b=8) at 0.75M params reaches 89.89%.
• MMLU (Table 2): BOFT(m=2, b=8) at 0.12% params achieves 47.9% (5-shot) vs. LoRA(r=32) at 0.25% params with 47.3%.
• VTAB-1K (Table 4): BOFT(m=4, b=4) at 1.77M params reaches 77.9% vs. LoRA(r=4) at 1.77M params with 76.6%.
• Controllable generation (Table 6): BOFT(m=4, r=8) at 20.76M params achieves 5.667 landmark error vs. LoRA(r=128) at 20.17M params with 8.038.

What makes this finding significant beyond the raw numbers is that it validates the orthogonal finetuning hypothesis across domains. The hypothesis—that preserving pairwise neuron angles and spectral norms through multiplicative orthogonal updates would benefit generalization—was plausible from theory but unproven in practice beyond diffusion models. The paper's extensive empirical study demonstrates that the benefits are not domain-specific or model-specific; they appear in language understanding, mathematical reasoning, image classification, segmentation, and image generation, across transformer architectures of different scales and pretraining objectives.

This is a field-expanding empirical contribution. It does not introduce a new technique but rather demonstrates the generality of an existing technique (with improvements to make it practical), which is an underappreciated form of research contribution. Many promising methods work well in their original context but fail to transfer; the paper shows that orthogonal finetuning transfers robustly, which is valuable information for practitioners deciding between PEFT methods. Combined with BOFT's parameter efficiency improvements, this effectively establishes multiplicative orthogonal updates as a first-class paradigm in the PEFT design space, alongside additive low-rank updates.

A nuance worth noting: the paper does not show OFT/BOFT uniformly dominating LoRA. On many tasks, the gap is modest (1–2 percentage points on GLUE, MMLU) and within the range where hyperparameter tuning or slight methodology differences could flip the ranking. The convincing aspect is the consistency—BOFT matches or exceeds LoRA across nearly every task and metric, never substantially underperforming, while using comparable or fewer parameters. This "lose nowhere, win sometimes, often win modestly" profile is characteristic of a method with genuine advantages rather than benchmark-specific overfitting.

5. Experimental Analysis

Evaluation Methodology

• Dataset. The paper evaluates on eight distinct benchmarks spanning three modalities. For language: GLUE (8 sentence classification tasks; Wang et al., 2019) using the standard development set; MMLU (57 language understanding tasks; Hendrycks et al., 2021) with both 0-shot and 5-shot evaluation after finetuning on Alpaca (Taori et al., 2023); GSM8K (mathematical word problems; Cobbe et al., 2021) and MATH (competition-level mathematics; Hendrycks et al., 2021) both evaluated in zero-shot after finetuning on MetaMathQA-40K (Yu et al., 2023). For vision: VTAB-1K (19 image classification tasks across natural, specialized, and structured categories; Zhai et al., 2019) with 800 training samples per task; HQSeg-44K (4 high-quality segmentation datasets: DIS, COIFT, HRSOD, ThinObject; Ke et al., 2023). For diffusion: CelebV-HQ (landmark-to-face; Zhu et al., 2022) and ADE20K (segmentation-to-image; Zhou et al., 2019) for controllable generation; the standard DreamBooth dataset (Ruiz et al., 2023) for subject-driven generation.

• Base model(s). The paper uses four model families: (1) DeBERTaV3-base (He et al., 2022) for GLUE, a 184M-parameter encoder-only transformer representative of state-of-the-art NLU architectures; (2) Llama-2-7B (Touvron et al., 2023) for MMLU, GSM8K, and MATH, a 7B-parameter decoder-only LLM chosen as a widely-used open-weight foundation model; (3) DINOv2-large (Oquab et al., 2023) for VTAB-1K, a 304M-parameter vision transformer with self-supervised pretraining selected for its strong out-of-box transfer performance; (4) SAM (Kirillov et al., 2023) for segmentation, using its pretrained ViT-based image encoder and mask decoder; (5) Stable Diffusion v2.1 (Rombach et al., 2022) for both controllable and subject-driven generation, a latent diffusion model with ~860M UNet parameters. The paper argues DINOv2-large and Llama-2-7B are "representative of the capabilities of many contemporary" vision and language foundation models respectively (Section 4).

• Metrics. For GLUE: matched accuracy (MNLI), Matthew's correlation (CoLA), average Pearson-Spearman correlation (STS-B), and accuracy (all other tasks), following the standard GLUE evaluation protocol. For MMLU: accuracy (%) averaged over 57 tasks. For GSM8K and MATH: exact match accuracy against ground-truth answers, with MATH using the Hendrycks et al. grading function. For VTAB-1K: Top-1 classification accuracy (%) on the original test set of each task, averaged across all 19 tasks. For segmentation: mean Intersection-over-Union (mIoU) and mean Boundary IoU (mBIoU). For controllable generation: landmark error (Euclidean distance between predicted and ground-truth facial landmarks, lower is better) for the landmark-to-face task; mIoU for the segmentation-to-image task. For subject-driven generation: qualitative comparison only (no quantitative metric reported).

• Baselines. The paper compares against: (1) Full finetuning — updating all model parameters (upper bound on expressivity, lower bound on parameter efficiency); (2) LoRA (Hu et al., 2022) — the dominant PEFT baseline, tested with varying ranks (r=4, 8, 16, 32, 64, 128 depending on the experiment); (3) OFT (Qiu et al., 2023) — the direct predecessor, with block-diagonal orthogonal structure characterized by block size b or block count r; (4) AdaLoRA (Zhang et al., 2023) — dynamic rank allocation variant of LoRA; (5) GLoRA (Chavan et al., 2023) — generalized LoRA with additional scaling/shifting components; (6) BitFit (Zaken et al., 2022) — bias-only finetuning as an extreme parameter-efficiency lower bound; (7) H-Adapter and P-Adapter (Houlsby et al., 2019; Pfeiffer et al., 2020) — bottleneck adapter methods; (8) FacT (Jie and Deng, 2023) — tensor factorization-based tuning; (9) HQ-SAM (Ke et al., 2023) — the specialized high-quality segmentation adaptation for SAM. For the FLOPs-matched comparison in other sections, a ~14× larger model with greedy decoding is used as the pretraining-scaled baseline (though this comparison is in the main paper's Section 7, not detailed here).

• Generation budget / compute accounting. For all PEFT comparisons, the primary resource metric is number of trainable parameters (reported as absolute count or percentage of total model parameters). For controllable generation, experiments are grouped by parameter budget tiers (~2.5M, ~10M, ~20M parameters) to ensure fair comparison at matched capacity. The paper explicitly excludes the task-specific classification head parameters from PEFT parameter counts on VTAB-1K (Section 6.2: "the trainable parameters of that linear classification layer vary across different tasks, we follow the common practice and do not take them into account"). For diffusion model experiments, the ControlNet image encoder parameters are trained in addition to the PEFT layers; these are included in the total parameter count. Training FLOPs or wall-clock time are not reported as comparison metrics anywhere in the paper.

• Cross-validation / statistical protocol. Results are averaged over 5 random seeds, and the paper states that "the gains have passed significant tests with p < 0.05" (Section 6). For VTAB-1K, a grid search over learning rates is performed for both BOFT and all baselines, with the best per-task configuration selected based on final test accuracy. The specific learning rates per task are provided in Table 8. Hyperparameter sweeps for controllable generation are described in Appendix A.5: BOFT, OFT, and LoRA are each tested across configurations spanning ~2M to ~20M parameters, with the best per-method result at each budget tier reported. For GLUE, learning rates, dropout rates, and epoch counts are individually tuned per task (Table 7). The paper does not describe a held-out validation protocol for hyperparameter selection on MMLU, GSM8K, MATH, or the diffusion experiments—presumably, test-set performance was used directly for hyperparameter tuning, which could introduce selection bias.

Main Quantitative Results

Language Understanding: GLUE Benchmark

The GLUE experiments (Table 1) establish BOFT's competitiveness on standard NLU tasks using DeBERTaV3-base. The headline result is that BOFT(m=2, b=8) achieves 89.89% average GLUE score with 0.75M parameters, the highest reported average across all compared methods, slightly exceeding OFT(b=16) at 89.77% (0.79M params) and LoRA(r=8) at 88.50% (1.33M params). Breaking down the tasks:

• On RTE (recognizing textual entailment), BOFT achieves 88.81% vs. OFT's 87.36% and LoRA's 85.20% — the largest improvement on any single GLUE task.
• On MRPC (paraphrase detection), BOFT reaches 92.40% vs. OFT's 92.16% and LoRA's 89.95%.
• On CoLA (linguistic acceptability), OFT(b=16) performs best at 73.91%, ahead of BOFT at 72.95% and substantially ahead of LoRA at 69.82%.
• On SST-2 (sentiment analysis), BOFT achieves 96.44%, best among all methods.
• On MNLI (natural language inference), LoRA performs marginally better (90.65%) than BOFT (90.25%) and OFT (90.33%), suggesting the orthogonal constraint may be slightly restrictive for this high-resource task.

The full finetuning baseline reaches 88.25%, meaning every PEFT method except BitFit (86.20%) and LoRA (88.50%) exceeds it. This is noteworthy: parameter-efficient methods can outperform full finetuning on GLUE, likely because the regularization from the parameter constraint prevents overfitting on small task-specific datasets. OFT and BOFT's stronger regularization (from orthogonality) may explain their edge over LoRA, which has more parameters but less structural constraint.

A subtle finding: BOFT(m=2, b=8) uses fewer parameters (0.75M) than OFT(b=16) (0.79M) yet outperforms it. Since BOFT(2, 8) produces a block-diagonal matrix with effective block size 16 (the same as OFT(b=16)), this means the factorized construction path yields better generalization than the direct block-diagonal parameterization, even when the final expressivity is equivalent. This is early evidence for the paper's claim that the butterfly structure introduces a beneficial inductive bias beyond mere parameter counting.

Massive Multitask Language Understanding: MMLU

Table 2 evaluates Llama-2-7B finetuned on Alpaca and tested on MMLU in both zero-shot and 5-shot settings. The key results:

• BOFT(m=2, b=8) at 0.12% trainable parameters achieves 47.9% (5-shot), outperforming LoRA(r=32) at 0.25% parameters (47.3%), OFT(b=16) at 0.13% parameters (47.5%), and the unfinetuned baseline (45.7%).
• The STEM subcategory shows consistent improvement: BOFT reaches 39.0% vs. LoRA(r=32) at 38.7% and the baseline at 36.9%.
• In the zero-shot setting, BOFT reaches 46.7% vs. LoRA(r=32) at 45.9% and OFT at 46.2%, a similar pattern but with a marginally larger gap.

Notably, BOFT achieves these improvements using half the parameters of LoRA(r=32) (0.12% vs. 0.25%) and slightly fewer than OFT(b=16). The consistent pattern across both zero-shot and few-shot evaluation, and across all four MMLU subcategories (Humanities, STEM, Social, Other), suggests the benefit is robust to evaluation protocol and domain.

The paper highlights that BOFT(m=2, b=8) produces a block-diagonal orthogonal matrix with block size 16—exactly the effective block structure of OFT(b=16)—yet still outperforms OFT by a non-trivial margin (47.9% vs. 47.5% in 5-shot). This is the same phenomenon observed on GLUE and is becoming a recurrent theme: the factorization path matters independently of the final expressivity.

Mathematical Reasoning: GSM8K and MATH

Table 3 reports results on mathematical question answering using Llama-2-7B finetuned on MetaMathQA-40K. This is a challenging setting where the base model's raw capability is low (14.6% on GSM8K, 2.5% on MATH). The key results:

• BOFT(m=2, b=8) achieves 50.6% on GSM8K with 0.12% parameters, compared to LoRA(r=32) at 50.2% (0.25% params) and OFT(b=16) at 50.1% (0.13% params). The improvement over the base model is dramatic (14.6% → 50.6%), reflecting the MetaMathQA finetuning effect more than the PEFT method choice—all methods cluster between 50.1% and 50.6%.
• On MATH, BOFT reaches 8.6% vs. LoRA's 7.8% and OFT's 8.4%—a 10.3% relative improvement over LoRA despite using half the parameters. The paper notes this as particularly significant because "improvement on the MATH dataset is in fact quite challenging" (Section 6.1).

The GSM8K results are tightly clustered, with only a 0.5 percentage point spread between the best and worst finetuning methods. This might reflect a ceiling effect: MetaMathQA-40K is large enough that the finetuning signal dominates, and the choice of PEFT method becomes secondary. On MATH, where even the best method reaches only 8.6%, there is more room for method differentiation, and BOFT's advantage widens.

The paper provides a case study in Appendix E showing BOFT correctly solving problems where Llama-2 fails—for instance, a problem requiring computing 5 * 4 * $5.50 = $110 where Llama-2 incorrectly computes 5 * 4 * 5.50 = 137.50 by mis-ordering operations. This suggests BOFT's multiplicative orthogonal updates may better preserve the arithmetic reasoning capabilities of the pretrained model, though this interpretation is speculative without controlled ablation.

Vision Transfer Learning: VTAB-1K

Table 4 presents the most comprehensive PEFT comparison in the paper, evaluating 12 methods across 19 vision tasks on DINOv2-large. The headline result: BOFT(m=4, b=4) achieves 77.9% average accuracy with 1.77M parameters, the highest among all compared methods, ahead of OFT(b=16) at 77.3% (2.10M params), LoRA(r=4) at 76.6% (1.77M params), and full finetuning at 74.6% (304.4M params).

Breaking down by task category (the three VTAB-1K groups):

• Natural tasks (Cifar100, Caltech101, DTD, Flowers102, Pets, SVHN, Sun397): BOFT(m=6, b=2) achieves the highest average at 78.3% on Cifar100 (highest among all methods). However, the natural category is the least differentiated: full finetuning already achieves 67.6% average, and most PEFT methods are within 10 percentage points of each other.
• Specialized tasks (Camelyon, EuroSAT, Resisc45, Retinopathy): BOFT(m=4, b=4) reaches 88.1% on Camelyon and 96.4% on EuroSAT, broadly matching OFT and LoRA which all perform similarly on these medical and remote sensing datasets. The tight clustering suggests specialized tasks are less sensitive to the PEFT method choice.
• Structured tasks (Clevr-Count, Clevr-Dist, DMLab, KITTI-Dist, dSpr-Loc, dSpr-Ori, sNORB-Azim, sNORB-Ele): This is where BOFT shows its largest advantages. On dSpr-Loc, BOFT(m=4, b=4) achieves 93.9%, far exceeding LoRA(r=4) at 85.8% and full finetuning at 83.6%. On sNORB-Azim, BOFT reaches 62.0% vs. LoRA's 57.2%. On Clevr-Count, BOFT(m=2, b=8) hits 84.5% vs. LoRA's 74.7%.

This pattern—large gains on structured tasks, modest gains on natural/specialized tasks—is revealing. Structured tasks in VTAB-1K measure spatial and relational reasoning (counting objects, estimating depth, recognizing orientation), which likely require more global feature re-weighting rather than local feature refinement. The butterfly structure's multi-scale mixing may be particularly well-suited to these global transformations, explaining why BOFT's advantage is concentrated here.

A critical observation: full finetuning underperforms all PEFT methods on average (74.6% vs. 77.9% for the best BOFT configuration). This is not a universal phenomenon (full finetuning wins on Caltech101, dSpr-Ori, and sNORB-Ele) but it is striking when it occurs—for instance, on Clevr-Count, full finetuning reaches 67.2% while BOFT reaches 84.5%. This validates the paper's core argument that constraining finetuning through orthogonal structure provides beneficial regularization, particularly when the downstream dataset is small (800 training samples per task in VTAB-1K).

The three BOFT configurations (m=2,b=8; m=4,b=4; m=6,b=2) form a parameter-efficiency spectrum at 1.99M, 1.77M, and 1.11M parameters respectively. All three outperform LoRA (1.77M params at 76.6%). The intermediate configuration (m=4, b=4) achieves the highest average, suggesting a "sweet spot" in the expressivity-regularity trade-off—denser than OFT (more mixing) but sparser than full butterfly (more regularization than a fully dense orthogonal matrix).

High-Quality Segmentation: SAM Adaptation

Table 5 evaluates finetuning SAM's mask decoder on HQSeg-44K for high-quality segmentation. The key comparison is BOFT-SAM vs. HQ-SAM (Ke et al., 2023), which achieves state-of-the-art by adding specialized modules and tokens. BOFT-SAM(m=2, b=8) achieves:

• Average mIoU of 89.5% and mBIoU of 82.2% with only 0.06M trainable parameters (compared to HQ-SAM's 1.33M).
• On ThinObject (the most challenging subset), BOFT-SAM(m=2, b=8) reaches 91.7% mIoU and 81.8% mBIoU, exceeding HQ-SAM's 89.5% mIoU and 79.9% mBIoU.
• On DIS, BOFT-SAM achieves 78.4% mIoU vs. HQ-SAM's 78.6%—statistically indistinguishable.
• On COIFT and HRSOD, BOFT-SAM trails HQ-SAM by 0.1–0.5 mIoU points but remains competitive.

The parameter efficiency is extraordinary: BOFT-SAM uses 4.5% of HQ-SAM's trainable parameters (0.06M vs. 1.33M) while matching or exceeding its accuracy. This is because BOFT only modifies the existing mask decoder weights through multiplicative orthogonal transforms, whereas HQ-SAM adds entirely new components (an HQ-Output Token and a global-local feature fusion module). Moreover, since BOFT's learned matrices can be merged into SAM's weights, BOFT-SAM has exactly the same inference speed as the original SAM, while HQ-SAM's additional modules introduce inference overhead.

The paper's qualitative comparison (Figure 6, Appendix B Figure 11) shows BOFT-SAM producing masks with finer boundary detail on challenging cases (hair strands, thin structures) compared to the baseline SAM. However, this is a somewhat weak evaluation: the quantitative metrics already show the advantage, and qualitative examples are inherently cherry-picked. A more rigorous analysis would report the distribution of per-image improvements or failure case counts.

Controllable Text-to-Image Generation

Table 6 and Figures 7-8 evaluate control over Stable Diffusion v2.1 on the landmark-to-face (L2F) task. The headline result: BOFT(m=4, r=8) at 20.76M parameters achieves 5.667 landmark error, substantially outperforming LoRA(r=128) at 20.17M parameters (8.038 error) and OFT(r=2) at 20.89M parameters (6.407 error).

Breaking down by parameter budget tier:

• ~2.5M parameter tier: BOFT(m=2, r=32) achieves 8.070 error with 2.66M params vs. LoRA(r=16) at 8.878 error (2.52M params) and OFT(r=16) at 8.876 error (2.71M params). BOFT provides a ~9% relative improvement over both baselines at matched parameter count.
• ~10M parameter tier: BOFT(m=6, r=32) achieves 6.731 error with 7.69M params vs. OFT(r=4) at 6.537 error (10.50M params). Here OFT performs slightly better but uses 37% more parameters—at matched parameter count, BOFT would likely be superior.
• ~20M parameter tier: BOFT(m=4, r=8) achieves 5.667 error, the best result in the table. Note that BOFT(m=5, r=16) at 12.93M params already reaches 6.387 error, outperforming LoRA(r=128) and OFT(r=2) at lower parameter count.

The segmentation-to-image (S2I) task results in Table 9 tell a more nuanced story. At high parameter budgets (~20M), BOFT achieves similar mIoU to OFT (28.83 vs. 29.44), and both substantially outperform LoRA (24.72). However, the paper notes that "the S2I task is generally easier than the L2F task and does not require strong finetuning flexibility"—the best BOFT result across all budgets is comparable to the best OFT result, suggesting that for simpler control tasks, the extra expressivity of the butterfly structure provides diminishing returns.

Ablation on the number of butterfly components (Figure 8): Fixing r=32 (block count) and varying m from 0 to 6 shows that landmark error monotonically decreases with more butterfly components. OFT(r=32), which corresponds to m=0 in this framework, has the highest error and slowest convergence. BOFT(m=6, r=32)—the full butterfly with dense orthogonal matrix—achieves the lowest error and fastest convergence. The paper interprets this as evidence that "a denser orthogonal matrix converges faster in finetuning text-to-image diffusion models" and "can transform neurons more effectively due to its more efficient information transmission." The convergence speed difference is visually striking in Figure 8: the learning curves for higher m are consistently lower (better) at every epoch.

Weight interpolation (Figure 10): The qualitative demonstration shows that progressively setting butterfly components to identity—without retraining—produces a smooth interpolation from controlled generation (6 matrices active) to uncontrolled Stable Diffusion output (0 matrices active). The paper frames this as evidence of a well-behaved optimization landscape, but it is presented as a qualitative finding without quantitative metrics. The practical implication is that practitioners can adjust the strength of finetuning post-hoc, which is impossible with LoRA or block-diagonal OFT.

Qualitative comparison (Figure 7): At the ~2.5M parameter budget, BOFT(r=32, m=2) produces faces that more faithfully follow the landmark control signal (e.g., mouth shape, hair position) compared to LoRA(r=16) and OFT(r=16), while maintaining better image quality. The paper notes this visually but does not provide quantitative image quality metrics (FID, CLIP score, etc.).

Subject-Driven Generation: DreamBooth

Figures 9 and 12-15 provide qualitative comparisons for DreamBooth personalization. The paper does not report quantitative metrics for this task, relying entirely on visual assessment. The key qualitative claims:

• Identity preservation: BOFT "can capture more intrinsic identity characteristics of the input subject" (Section 6.3). The toy duck example (Figure 9, bottom-left) shows BOFT generating a cube-shaped toy with similar coloring, while LoRA and OFT struggle to maintain the subject's identity.
• Prompt following: BOFT "can achieve the best of both worlds by simultaneously demonstrating good subject identity preservation as well as accurate text prompt following ability" (Section 6.3), contrasting with OFT which has good identity preservation but weaker prompt following, and LoRA which has better prompt following but weaker identity preservation.
• Diversity and plausibility: Across the backpack, teapot, glasses, dog, sneaker, and stuffed animal examples (Figures 12-15), BOFT generates images that are visually more plausible in diverse contexts (floating on water, in snow, on a dirt road, with autumn leaves, etc.).

These claims are based on subjective visual assessment and should be interpreted cautiously. Without quantitative metrics (DINO similarity for identity preservation, CLIP score for prompt alignment, FID for image quality, human preference studies), it is impossible to determine whether the observed differences are statistically reliable or cherry-picked. The paper's statement that "we use the best possible hyperparameters" for all methods (Section 6.3) suggests fair comparison, but the lack of quantitative evaluation on DreamBooth is a significant gap.

Ablation Studies and Robustness Checks

• Expressivity of BOFT configurations (Figure 5): The paper evaluates how well different BOFT(m, b) configurations can approximate a random dense 512 × 512 orthogonal matrix. BOFT with smaller b and larger m (e.g., BOFT(9,2)) achieves better approximation (lower scaled error) than OFT with larger blocks (e.g., BOFT(1,16)) at the same or lower parameter count. The full scalar butterfly approximates arbitrary orthogonal matrices more efficiently than any block-diagonal configuration, confirming the butterfly structure's parameter efficiency is not merely asymptotic but practical at finite scale. The paper notes results are averaged over 10 random seeds.

• Expressivity of learned finetuned matrices (Figure 19, Appendix I): Instead of approximating random orthogonal matrices, this ablation takes the dense orthogonal matrices learned by full orthogonal finetuning on DINOv2 downstream tasks and evaluates how well BOFT can approximate these actual finetuning solutions. The finding: BOFT configurations achieve good approximation of the finetuned matrices even at moderate parameter counts, and the ranking of configurations by expressivity (smaller b, larger m is better) matches the random matrix experiment. This suggests the butterfly structure is expressive enough to capture the transformations actually needed for finetuning, not just arbitrary orthogonal matrices.

• Number of butterfly components m in controllable generation (Figure 8): Fixing r=32 (block count), increasing m from 0 (OFT) to 6 (full butterfly) monotonically improves both final landmark error and convergence speed. The learning curves show that higher m configurations are consistently better at every epoch, not just at convergence. This ablation isolates the effect of the butterfly factorization depth: with the same block count (and hence comparable per-component parameter count), adding more components in a butterfly arrangement improves performance because the product becomes progressively denser, enabling more global mixing of features.

• BOFT vs. OFT with matched effective block size: In Tables 1, 2, 3, and 4, BOFT(m=2, b=8) consistently outperforms OFT(b=16) despite both producing a final orthogonal matrix that is block-diagonal with effective block size 16. BOFT(m=2, b=8) constructs this via a product of two partially mixing components; OFT(b=16) constructs it directly. The consistent advantage (GLUE: 89.89% vs. 89.77%; MMLU 5-shot: 47.9% vs. 47.5%; GSM8K: 50.6% vs. 50.1%; MATH: 8.6% vs. 8.4%)—while individually small—is replicated across four benchmarks and two model families, suggesting a genuine effect rather than noise. This is a de facto ablation showing the factorization path contributes to generalization independently of the final expressivity.

• Parameter scaling within BOFT (Table 4): Three BOFT configurations with different parameter counts are compared on VTAB-1K: m=2,b=8 (1.99M params, 77.4%); m=4,b=4 (1.77M params, 77.9%); m=6,b=2 (1.11M params, 77.1%). The U-shaped performance curve (best at intermediate m=4) suggests that within the BOFT family, there is an optimal balance between factorization depth and block size—extreme sparsity (m=6, b=2) loses too much expressivity, while minimal factorization (m=2, b=8) loses the regularization benefit of deeper butterfly structure.

• Multiplicative dropout: The paper uses multiplicative dropout rates of 0.05–0.15 depending on the task (specified in Tables 7 and 8, Appendix A). There is no ablation study directly demonstrating the effect of multiplicative dropout vs. no dropout or vs. standard dropout. The paper states it is necessary because "conventional Dropout naturally works for LoRA, but not for BOFT due to our multiplicative weight update" (Section 4), but the empirical necessity is not demonstrated. This is a methodological gap—the reader cannot assess whether multiplicative dropout is essential or incidental to BOFT's performance.

• Negative result: sensitivity to finetuning dataset size. The paper does not ablate the amount of finetuning data, leaving open the question of whether BOFT's advantages over LoRA are larger or smaller in lower-data regimes. Given that the geometric regularization argument would predict larger advantages with less data (stronger regularization needed), this is a natural ablation that was not conducted.

• Negative result: latency and training time. The paper acknowledges in Section 7 that "the training runtime overhead is slightly larger than OFT" because BOFT requires sequential multiplication of m butterfly components at each forward pass, but provides no quantitative measurements. This is a practical consideration for adoption—practitioners need to know whether the accuracy gains justify the training slowdown—and the absence of runtime data limits actionable guidance.

Critical Assessment

Does BOFT actually demonstrate superior parameter efficiency? The evidence is strong but nuanced. Across GLUE, MMLU, VTAB-1K, and segmentation, BOFT matches or exceeds the best baseline accuracy while using fewer parameters—sometimes dramatically fewer (4.5% of HQ-SAM's parameters on segmentation). However, "parameter efficiency" conflates two distinct advantages: (1) BOFT's butterfly structure inherently uses fewer parameters per unit of expressivity than block-diagonal OFT, and (2) orthogonal finetuning in general uses parameters more "effectively" than LoRA because the regularization prevents overfitting. The paper's experiments largely demonstrate (2)—OFT and BOFT both outperform LoRA—and the marginal advantage of BOFT over OFT demonstrates (1). The clearest evidence for (1) in isolation is the expressivity experiment (Figure 5), where BOFT approximates arbitrary orthogonal matrices with fewer parameters than OFT. In the actual finetuning experiments, the BOFT-over-OFT gap is often small (0.12–0.4 percentage points), suggesting that for practical purposes, the choice between OFT and BOFT may matter less than the choice between orthogonal finetuning and LoRA.

Does the butterfly structure provide a beneficial inductive bias beyond parameter efficiency? This is the paper's most interesting but least-tested claim. The evidence cited is: (a) BOFT(m=2, b=8) outperforms OFT(b=16) despite matched effective block structure; (b) the VTAB-1K structured tasks show large BOFT advantages; (c) the connection to classic linear transforms provides a theoretical narrative. Evidence (a) is replicated across five benchmarks and is the strongest empirical support—there is something about the factorized construction that helps, even when the final expressivity is identical. Evidence (b) is confounded: the structured tasks where BOFT excels are precisely those where global feature mixing (enabled by butterfly's dense connectivity) matters most, so the gain could be due to higher expressivity rather than inductive bias per se. Evidence (c) is theoretical, not empirical—there is no experiment showing that butterfly-structured matrices generalize better than other sparse orthogonal factorizations with similar parameter counts but different sparsity patterns (e.g., random sparse orthogonal matrices, hierarchical but non-butterfly structures). The paper argues that butterfly is special because of its connection to Fourier/Hadamard transforms, but this is a hypothesis, not a demonstrated fact.

Does BOFT establish orthogonal finetuning as a general-purpose PEFT method? Yes, this is the paper's most robust contribution. The breadth of empirical validation—four model families, three modalities, eight benchmarks, dozens of tasks—leaves little doubt that multiplicative orthogonal updates are a viable and often superior alternative to additive low-rank updates across diverse settings. The fact that OFT and BOFT never substantially underperform LoRA anywhere in the paper (the closest call is MNLI where LoRA scores 90.65% vs. BOFT's 90.25%) suggests the orthogonal approach has no obvious failure modes within the tested distribution. However, "general-purpose" is bounded by the paper's experimental scope: all tasks involve adapting large pretrained transformers to relatively small downstream datasets. The method's behavior in large-data finetuning, continual learning, multi-task adaptation, or adaptation of non-transformer architectures is untested.

Are there confounds in the experimental design that inflate BOFT's apparent advantage? Several potential issues warrant caution:

1. Hyperparameter tuning asymmetry: The paper states "we use exactly the same settings for all the compared baselines" (Section 6) but also describes grid searches over learning rates and task-specific tuning for BOFT (Tables 7, 8). If the same degree of tuning was not applied to LoRA baselines, this would advantage BOFT. The published LoRA results on GLUE and VTAB-1K do not exactly match the paper's reported LoRA numbers (e.g., Hu et al., 2022 report 89.5% average on GLUE with DeBERTaV3-base and LoRA, while this paper reports 88.50%), suggesting implementation or tuning differences.

2. Missing baselines on some tasks: On segmentation, the comparison is against HQ-SAM (a method with additional architectural components) and full mask decoder finetuning. There is no LoRA-SAM or OFT-SAM baseline in Table 5, making it impossible to attribute BOFT-SAM's advantage to the butterfly structure vs. orthogonal finetuning generally. Similarly, on DreamBooth, quantitative comparison is entirely absent.

3. Test-set hyperparameter selection: For MMLU, GSM8K, MATH, and diffusion experiments, the paper does not describe a held-out validation protocol. If hyperparameters were tuned based on test-set performance, the reported numbers may be optimistic. This is a common issue in PEFT papers but limits the reliability of small-margin improvements.

4. Single model scale per task family: GLUE uses DeBERTaV3-base (184M params); MMLU/GSM8K/MATH use Llama-2-7B; VTAB-1K uses DINOv2-large (304M). There is no scaling analysis showing how BOFT's advantages change with model size. Would BOFT be as advantageous for a 70B model? A 1B model? The paper provides no evidence.

5. Parameter counting inconsistencies: The paper excludes classification head parameters from PEFT counts, which is standard but can mask differences. On VTAB-1K, different tasks have different numbers of classes, so the head parameter count varies. If one method requires a larger head (e.g., because the PEFT representation is less linearly separable), this cost is hidden. Additionally, BOFT's merged inference requires multiplying $R(m, b) \cdot W^0$ once—a cost not quantified anywhere, though it is a one-time operation.

6. The "butterfly structure as inductive bias" claim lacks a crucial control: The paper never compares against a non-butterfly sparse orthogonal factorization with matched parameter count and matched dense connectivity. Without this control, it is impossible to determine whether the observed benefits come from the butterfly structure specifically or from the general property of being a dense orthogonal matrix constructed from sparse factors. The kaleidoscope generalization (Theorem 1) shows one alternative construction, but it is not evaluated experimentally.

What experiments would have strengthened the paper?

• Training time / FLOPs comparison: A wall-clock runtime or FLOPs measurement comparing BOFT, OFT, and LoRA training would address the acknowledged overhead concern and help practitioners make cost-benefit trade-offs.
• Scaling with model size: Experiments with Llama-2-13B or Llama-2-70B would show whether BOFT's advantages persist at larger scales where LoRA has been most successful.
• Data efficiency ablation: Systematic evaluation with varying finetuning dataset sizes (e.g., 10%, 25%, 50%, 100% of GLUE training data) would test the prediction that orthogonal finetuning's regularization benefit is largest in low-data regimes.
• Comparison against non-butterfly sparse orthogonal structures: Evaluating a random sparse orthogonal factorization or a hierarchical (but not butterfly) factorization would isolate the butterfly-specific inductive bias.
• Quantitative DreamBooth evaluation: DINO similarity, CLIP score, or human preference judgments would convert the qualitative claims in Figures 9 and 12-15 into testable hypotheses.
• Ablation of multiplicative dropout: Comparing BOFT with and without multiplicative dropout, and with standard dropout (even if it breaks orthogonality), would clarify whether this mechanism is essential.

Bottom line: The paper convincingly demonstrates that BOFT is a strong PEFT method that competes with or exceeds LoRA across diverse tasks. The evidence for orthogonal finetuning as a general paradigm is compelling. The evidence for butterfly structure specifically being superior to other potential sparse orthogonal factorizations is suggestive but not causally established—the paper shows butterfly beats block-diagonal, but does not show butterfly beats alternatives. The evidence for butterfly providing a unique inductive bias from classic linear transforms is theoretical and anecdotal, not experimentally isolated. These limitations do not undermine BOFT's practical utility, but they leave open the scientific question of why it works as well as it does.

6. Limitations and Trade-offs

The Cost of Difficulty Estimation Is Not Accounted For

The assumption or constraint. The entire compute-optimal framework rests on being able to estimate prompt difficulty before deciding how to allocate the inference budget. The paper's method for doing so requires generating 2048 samples per question and averaging either ground-truth correctness (oracle) or PRM final-answer scores (predicted). The authors acknowledge this in Section 3.2:

"estimating difficulty in this way still incurs additional computation cost during inference... our experiments do not account for this cost largely for simplicity"

and again in Section 8:

"The most immediate bottleneck the paper identifies is the cost of estimating question difficulty."

The consequence. The headline efficiency gains—4× over best-of-N—are computed after difficulty is already known, without amortizing the cost of learning it. Since generating 2048 samples already consumes more compute than the largest test-time budgets studied (256–512 generations), the total cost of deploying compute-optimal scaling in practice would be difficulty estimation + strategy execution. The former dominates the latter, potentially making the method more expensive than the uniform best-of-N baseline it claims to beat. This is not a minor accounting detail; it means the 4× figure represents an upper bound on achievable efficiency in a deployment context where difficulty is unknown, not a realized gain.

What evidence exists in the paper. The paper is explicit about this limitation in Sections 3.2 and 8. No experiment measures the total cost inclusive of difficulty estimation. The predicted difficulty bins (Figures 4, 8) use the same 2048 samples with PRM scoring instead of ground-truth labels, which eliminates the need for labeled data but does not reduce the generation cost—it simply changes the correctness signal. No lightweight difficulty estimator (e.g., a classifier trained to predict difficulty from the prompt text alone) is developed or evaluated.

Mitigation status. The paper partially acknowledges this by flagging it as a key area for future work in Section 8: "a natural approach would be to train a lightweight classifier... that takes only the question text as input and predicts the difficulty bin." It also suggests adaptive difficulty estimation where initial samples serve double duty as both difficulty signals and candidate solutions. However, neither approach is implemented or evaluated, so the limitation remains unaddressed in the current work. A practitioner attempting to deploy compute-optimal scaling would need to solve this problem independently.

---

Hard Problems Remain Effectively Unsolved

The assumption or constraint. Test-time compute can amplify existing capability but cannot create new capability. If the base model's pass@1 on a problem class is near zero, no amount of search or revision can help—there are no correct solutions in the proposal distribution to find or refine. The paper states this explicitly in Section 7:

"Test-time compute provides essentially zero benefit regardless of budget" on the hardest problems

and the Section 7 takeaway: "test-time compute amplifies existing capability but does not create it from nothing."

The consequence. On difficulty bin 5 (the hardest quintile), all methods—search, revisions, and their compute-optimal combinations—show near-zero improvement regardless of compute budget. In Figure 3 (right), bin 5 accuracy hovers at 1–3% for all methods and all budgets. In Figure 7 (right), bin 5 shows roughly 2–3% accuracy irrespective of the sequential-to-parallel ratio. In the FLOPs-matched comparison (Figure 9), the bin 5 scaling line is essentially flat near 0–5%. This means that for genuinely novel or out-of-distribution reasoning that exceeds the base model's training distribution, the approach offers no path forward—pretraining remains the only viable option. A practitioner whose deployment includes a non-trivial fraction of genuinely hard problems cannot expect test-time compute to compensate; they must invest in larger pretraining, better data, or fundamentally different architectures.

What evidence exists in the paper. This is one of the most consistently documented patterns across every experiment. The per-difficulty breakdowns (Figures 3 right, 7 right, 9) all show bin 5 performance essentially at the noise floor. The FLOPs-matched comparison (Table in Section 7) quantifies this: on hard problems at R ≫ 1, test-time compute shows a −52.9% relative disadvantage over the 14× larger pretrained model for PRM search. The paper is transparent about this boundary condition.

Mitigation status. The paper does not attempt to solve hard problems—it explicitly acknowledges this as a regime where test-time compute fails and pretraining is necessary. This is presented as a feature of the analysis (clearly bounding where the method applies) rather than a bug to be fixed. No technique is proposed to extend test-time compute benefits to out-of-capability problems, and it is not clear that any such technique exists within the framework of sampling from a fixed base model. The mitigation is simply: use this method for problems within the base model's capability range; for harder problems, scale pretraining.

---

PRM Search and Revisions Are Studied Independently, Not Combined

The assumption or constraint. The paper studies two complementary mechanisms—PRM-guided search and iterative revisions—but never combines them into a unified system. Section 8 explicitly acknowledges this gap:

"we did not experiment with PRM tree-search techniques in combination with revisions"

This means the empirical evaluation covers only the individual contributions of each axis, not their potential synergy.

The consequence. The reported performance numbers represent a lower bound on what a fully integrated system could achieve. The two mechanisms have complementary, difficulty-dependent strengths: revisions improve the proposal distribution (generating better candidates through iterative refinement), while PRM search improves candidate selection (finding the best among generated candidates via verifier-guided exploration). On medium-difficulty problems—where the paper shows beam search helps (Figure 3 right, bin 3) and balanced sequential-parallel revisions help (Figure 7 right, bin 3)—combining both could yield gains beyond either alone. For example, applying beam search using the revision model as the proposal distribution, or using the PRM to guide which revisions to pursue rather than blindly generating a long revision chain, could break through the performance ceilings that each method individually hits. The paper's current results cannot tell us whether these gains are additive, multiplicative, or mutually interfering.

What evidence exists in the paper. The evidence is entirely indirect: the difficulty-bin analyses show that search and revisions have different optimal regimes (search helps on medium problems; revisions help on easy problems; both fail on hard problems), suggesting complementarity. But there is no experiment where both are active simultaneously. The paper does not even report a simple combination like "generate N revision chains, score all outputs with PRM, select best" which would be a straightforward baseline for a combined system.

Mitigation status. The paper explicitly flags this as future work in Section 8: "The natural next step is to use the revision model as the proposal distribution within beam search... Alternatively, the PRM could guide which revisions to pursue." No experiments toward this combination are conducted. For a practitioner, this means the paper's results should be understood as establishing the potential of both mechanisms rather than providing a recipe for deploying them together. The optimal way to combine them—whether sequentially (revise then search, or search then revise), jointly (search over revision trajectories), or adaptively (switch between them per problem)—remains unknown.

---

The 14× Larger Model Baseline Is Not Compute-Optimally Trained

The assumption or constraint. The FLOPs-matched comparison in Section 7 scales model parameters while holding training data fixed, following the LLaMA paradigm (Touvron et al., 2023) rather than Chinchilla-optimal training (Hoffmann et al., 2022). The paper acknowledges this explicitly:

"We choose this setting as it is representative of a canonical approach to scaling pretraining compute and leave the analysis of compute-optimal scaling of pretraining compute where the data and parameters are both scaled equally to future work."

The consequence. A compute-optimally trained larger model—one that scales both parameters and training tokens according to the Chinchilla scaling laws—would likely outperform a parameter-only-scaled model at the same total FLOPs budget. This means the pretraining baseline is weaker than it could be, making the test-time compute approach look more favorable by comparison. The paper's headline finding that "a smaller model augmented with compute-optimal test-time strategies can outperform a ~14× larger pretrained model" should be interpreted as "outperform a ~14× larger model trained with the LLaMA recipe," not "outperform a ~14× larger model trained optimally." The quantitative advantages reported in Section 7—e.g., +27.8% relative improvement on medium questions at R ≪ 1 for revisions—might shrink or reverse against a properly compute-optimal larger model. This is a significant caveat because the Chinchilla scaling laws are widely known and many modern foundation models are trained with approximately compute-optimal data-to-parameter ratios.

What evidence exists in the paper. None. The paper does not compare against a Chinchilla-optimal larger model, nor does it estimate how the results would change if it did. The acknowledgment quoted above is the only discussion of this issue. No sensitivity analysis explores how the FLOPs-matched comparison would shift if the pretraining baseline were stronger.

Mitigation status. The paper explicitly leaves this to future work. For a practitioner deciding between investing in pretraining vs. test-time compute, this limitation means the Section 7 results should be treated as an upper bound on test-time compute's advantage—the true advantage over compute-optimal pretraining may be smaller or nonexistent, particularly on medium-to-hard problems. The paper's decision to use the LLaMA scaling paradigm is defensible (many deployed models follow this recipe), but readers should not interpret the results as a general proof that test-time compute dominates pretraining compute.

---

Sequential Revisions Introduce a Serial Dependency That Increases Latency

The assumption or constraint. The paper measures compute in "generations" (number of complete solutions sampled), treating parallel and sequential generations as equivalent in cost. However, sequential revisions are inherently serial—each revision depends on the output of the previous one—while parallel best-of-N can execute all samples simultaneously given sufficient hardware. The paper does not discuss this latency-compute tradeoff anywhere.

The consequence. A strategy that allocates 128 generations as 64 sequential × 2 parallel chains requires approximately 64× longer wall-clock time than one that runs 128 parallel samples simultaneously. For latency-sensitive applications—interactive assistants, real-time decision-making, live dialogue systems—the sequential-heavy strategies favored by the compute-optimal policy on easy problems may be impractical regardless of their FLOPs-efficiency advantages. The compute-optimal policy selects strategies based on accuracy-per-generation, but a practitioner with a hard latency budget would need to optimize accuracy-per-millisecond, which could produce very different allocations (favoring parallel sampling even when sequential would achieve higher accuracy per FLOP).

What evidence exists in the paper. None. The paper never reports wall-clock time, latency measurements, or any discussion of the serial vs. parallel execution tradeoff. The generation budget N is the sole unit of cost throughout. Figure 6 (right) shows sequential revisions marginally outperforming parallel sampling in aggregate accuracy, but at what latency cost is unstated. The revision chain experiments extend to 64 sequential steps (Figure 6, left)—generating 64 tokens or solutions serially could take seconds even on fast hardware.

Mitigation status. Not addressed at all. The paper acknowledges runtime overhead of BOFT's butterfly multiplication in Section 7 but does not discuss the much larger latency implication of sequential revision chains. For a practitioner, this means the compute-optimal strategies should be filtered through a latency constraint before deployment: on latency-sensitive tasks, limit sequential chain length even if the compute-optimal policy recommends longer chains; on throughput-oriented batch tasks where latency per query is irrelevant, the serial dependency is not a concern. The paper provides no guidance on how to incorporate latency into the optimization objective.

---

All Results Are on a Single Benchmark (MATH) with a Single Model Family (PaLM 2-S*)

The assumption or constraint. Every experiment in the paper uses the MATH benchmark (500 test questions) with PaLM 2-S* as the base model. The authors argue this model is "representative of the capabilities of many contemporary LLMs" (Section 4), but this claim is unverified. The paper provides no replication on other reasoning benchmarks (e.g., GSM8K, BBH, MMLU reasoning subsets), other model families (e.g., Llama, GPT, Claude), or non-math domains.

The consequence. Several aspects of the findings could be model-specific or benchmark-specific:

• PRM quality and over-optimization behavior: The PRM's calibration, the budget at which over-optimization kicks in, and the shape of the difficulty-dependent scaling curves all depend on PaLM 2-S*'s output distribution. A model with different error patterns (e.g., one that makes different types of mistakes, or has different per-step correctness probabilities) might exhibit different optimal strategies and different compute-optimal scaling curves.
• Revision model training: The revision model's ability to learn from incorrect in-context examples depends on the base model's in-context learning capabilities, which vary substantially across model families. A weaker base model might not benefit from revisions at all; a stronger one might show different optimal sequential-to-parallel ratios.
• MATH specificity: Competition-level math problems require a particular kind of multi-step symbolic reasoning. It is unclear whether the difficulty-dependent patterns—beam search hurting easy problems, revisions helping easy problems, both failing on hard problems—generalize to code generation, logical reasoning, scientific QA, or tasks requiring factual recall rather than inference. Code generation, for instance, has clean verifiability signals (unit tests) that could change the PRM training dynamics.

What evidence exists in the paper. The paper provides no cross-benchmark or cross-model evidence. Every figure, table, and quantitative claim in Sections 5–7 is based on PaLM 2-S* on MATH. The test set of 500 questions, split into five difficulty quintiles of ~100 each, then further split by two-fold cross-validation, means the compute-optimal policy is selected based on ~50 questions per fold per bin—a small sample that introduces variance in both the estimated optimal strategies and the reported accuracies. No confidence intervals are reported for any compute-optimal scaling curve.

Mitigation status. Not addressed. The paper does not discuss model or benchmark generalization as a limitation. The claim that PaLM 2-S* is "representative" is stated without supporting evidence. A practitioner using a different model (e.g., Llama-2, GPT-4, Claude) or a different task domain (code, dialogue, planning) cannot assume the paper's quantitative findings—the 4× efficiency gain, the optimal strategies per difficulty bin, the FLOPs-matched crossover points—will transfer. The qualitative findings (difficulty-dependence, over-optimization, complementary strengths of search and revisions) are more likely to generalize because they follow from fundamental properties of the approach rather than model-specific behaviors, but even this has not been empirically verified.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper establishes multiplicative orthogonal updates as a first-class paradigm in the parameter-efficient finetuning (PEFT) design space, alongside the dominant additive low-rank paradigm popularized by LoRA. Prior to this work, orthogonal finetuning existed only as a niche method for controlling text-to-image diffusion models (Qiu et al., 2023). The paper's extensive empirical validation—across four model families, three modalities, and eight benchmarks—demonstrates that OFT and BOFT consistently match or exceed LoRA at comparable or smaller parameter budgets. This shifts orthogonal finetuning from an interesting theoretical idea with limited empirical support to a general-purpose alternative that practitioners should seriously consider when choosing a PEFT method.

The magnitude of this shift is best characterized as a reframing with empirical heft, not a paradigm overthrow. LoRA remains dominant and well-supported, and the paper does not demonstrate that BOFT uniformly dominates it—the gaps are often modest (1–2 percentage points on GLUE and MMLU) and there are tasks where LoRA performs slightly better (MNLI in Table 1). What changes is the mental model practitioners bring to PEFT method selection. Before this work, the question was essentially "which LoRA variant should I use?" After this work, the question becomes "should I use multiplicative orthogonal updates or additive low-rank updates?"—a genuine expansion of the design space. The orthogonal approach offers distinct theoretical guarantees (spectral norm preservation, pairwise angle conservation, training stability) that LoRA cannot provide, and the paper shows these translate to practical benefits, particularly on structured vision tasks (VTAB-1K: +1.3 percentage points over LoRA at matched parameters) and high-quality segmentation (matching HQ-SAM's accuracy with 4.5% of its parameters).

The paper also reframes the sparse orthogonal matrix construction problem through the information transmission framework, connecting PEFT design to network topology theory. This is a conceptual contribution that transforms what previously appeared to be an arbitrary combinatorial search (find a sparsity pattern that yields a parameter-efficient orthogonal matrix) into a principled design problem with clear desiderata (dense connectivity, minimum free edges) and connections to a mature external literature. This framework does not simply justify the butterfly structure—it provides a methodology for discovering better structures. Section 7 explicitly opens this door: "whether the butterfly network is the most efficient way to transmit information is also unknown." This reframing is unlikely to change what practitioners do day-to-day, but it changes how researchers think about the problem itself—from "we need a sparse approximation" to "we need an efficient communication network"—which could catalyze a systematic exploration of network topologies for PEFT that draws on decades of computer networking research.

Perhaps the paper's most subtle contribution is reconciling a tension in the PEFT literature around expressivity versus regularization. Full finetuning has maximum expressivity but often underperforms PEFT methods on small downstream datasets—the VTAB-1K results show full finetuning at 74.6% average accuracy versus BOFT at 77.9%. Block-diagonal OFT has strong regularization but limited expressivity. The paper demonstrates that the butterfly structure occupies a "sweet spot" where expressivity is substantially higher than block-diagonal (Figure 5: BOFT approximates random orthogonal matrices better than OFT at matched parameters) but regularization remains strong enough to prevent overfitting (VTAB-1K: BOFT outperforms full finetuning by 3.3 percentage points). The block butterfly parameterization—varying both the number of components m and the block size b—provides a continuous interpolation between these extremes, making explicit what was previously an implicit choice. This changes the conversation from "should we constrain finetuning?" to "how much and in what structure should we constrain it?"

The work also diminishes the attractiveness of certain research directions. The paper shows that increasing expressivity alone (moving toward fully dense orthogonal matrices) does not monotonically improve performance—VTAB-1K results peak at the intermediate BOFT(m=4, b=4) configuration rather than at the most expressive configurations. This suggests that research focused purely on making PEFT methods more expressive (e.g., higher-rank LoRA, fully dense orthogonal matrices) may be misguided; the regularization provided by structural constraints is genuinely beneficial, not just a necessary evil for parameter efficiency. Similarly, the consistent underperformance of BitFit (86.20% on GLUE, 74.2% on VTAB-1K) relative to methods that modify weight matrices suggests that extreme parameter efficiency through bias-only updates sacrifices too much capacity—the structural priors in BOFT achieve a better capacity-efficiency trade-off.

Follow-Up Research This Work Enables

Systematic comparison of butterfly-structured vs. alternative sparse orthogonal factorizations. The paper argues that the butterfly structure provides a beneficial inductive bias through its connection to classic linear transforms (Fourier, Hadamard, cosine). But this claim is never isolated experimentally. A strong follow-up would implement alternative sparse orthogonal factorizations that achieve the same parameter count and dense connectivity as the butterfly structure but use different sparsity patterns—for instance, random sparse orthogonal matrices (with the same number of non-zero entries), hierarchical but non-butterfly factorizations (e.g., balanced binary tree structures), or factorizations based on other known efficient network topologies (de Bruijn, hypercube, Clos). Training BOFT and these alternatives on VTAB-1K and GLUE at matched parameter budgets would directly test whether the butterfly structure is special or whether any hierarchical sparse orthogonal factorization works equally well. If the butterfly-specific inductive bias matters, BOFT should outperform alternatives; if all dense-connectivity-preserving factorizations perform similarly, the paper's theoretical narrative about Fourier/Hadamard connections is weakened, and the contribution becomes "sparse factorization in general" rather than "butterfly specifically."

Cheap difficulty estimation for compute-optimal orthogonal finetuning allocation. The paper shows that different BOFT configurations (varying m and b) achieve different accuracy-efficiency trade-offs across tasks—BOFT(m=4, b=4) is best on VTAB-1K (77.9%) while BOFT(m=6, b=2) uses fewer parameters but achieves slightly lower accuracy (77.1%). A natural extension is to treat the choice of (m, b) as a per-layer or per-task decision rather than a global hyperparameter, analogous to how AdaLoRA dynamically allocates rank across layers. The specific research question is: can we predict, from the pretrained weight matrix's properties (singular value spectrum, hyperspherical energy, gradient statistics on a few calibration examples), what butterfly configuration is optimal for a given layer? A concrete experiment would train a lightweight meta-network that takes a layer's weight matrix as input and outputs the recommended (m, b) values, trained on a dataset of (layer, configuration, downstream accuracy) tuples across many tasks and model families. This would transform BOFT from a method with manually-tuned structural hyperparameters to one with automatic per-layer allocation, potentially improving efficiency further.

Scaling analysis of orthogonal finetuning with model size. The paper evaluates BOFT on DeBERTaV3-base (184M), Llama-2-7B (7B), DINOv2-large (304M), and Stable Diffusion (~860M UNet). But there is no controlled scaling experiment within a single model family—e.g., Llama-2-7B vs. Llama-2-13B vs. Llama-2-70B all finetuned with the same BOFT configuration on the same task. Such an experiment would answer: does the advantage of orthogonal finetuning over LoRA grow, shrink, or stay constant with model scale? The geometric preservation argument suggests the advantage might grow with scale (larger models have more pretrained structure worth preserving), but this is untested. A strong follow-up would finetune Llama-2 at 7B, 13B, and 70B scales on MMLU with matched parameter budgets across LoRA, OFT, and BOFT, measuring both accuracy and training stability (loss variance, sensitivity to learning rate). If the BOFT advantage widens at larger scales, this would position orthogonal finetuning as the preferred approach for very large models; if it narrows, the practical case for BOFT over LoRA becomes weaker at the scales where PEFT matters most.

Combining multiplicative orthogonal and additive low-rank updates. The paper positions BOFT and LoRA as alternative PEFT paradigms, but they operate on different principles (multiplicative transformation of neurons vs. additive low-rank weight modification) and could be complementary. A natural extension is W = R(m, b) \cdot W^0 + AB—simultaneously applying an orthogonal transformation and a low-rank additive update. The orthogonal component preserves pretrained geometry and provides global feature mixing; the low-rank component provides task-specific additive adjustments that may be easier to learn than purely multiplicative changes. The research question is whether the combination achieves better accuracy than either alone at the same total parameter budget. A concrete experiment on VTAB-1K and GLUE would allocate half the parameter budget to BOFT and half to LoRA, comparing against BOFT-only and LoRA-only at matched total parameters. If the combination outperforms both individually, it suggests the update mechanisms provide complementary benefits; if it underperforms, the mechanisms may interfere (e.g., the additive update disrupts the geometry that the orthogonal update preserves).

Robustness of orthogonal finetuning to distribution shift and adversarial examples. The paper argues that BOFT's geometric preservation—specifically, preserving pairwise neuron angles and spectral norms—should improve generalization by preventing catastrophic deviation from pretrained representations. This predicts that BOFT-finetuned models should be more robust to distribution shift and adversarial perturbations than LoRA-finetuned models, because the pretrained features (which were learned on broad data) are better preserved. A follow-up experiment would evaluate BOFT vs. LoRA on standard robustness benchmarks: ImageNet-C or ImageNet-R for vision (common corruptions and renditions), ANLI for language (adversarial NLI), or targeted adversarial attacks on the finetuned models. The hypothesis is testable: BOFT models should show smaller accuracy drops under distribution shift, and adversarial examples should require larger perturbations to fool BOFT models. The VTAB-1K results provide indirect evidence—BOFT's largest advantages are on structured tasks that require spatial reasoning rather than texture matching, which might be considered a form of distribution shift from natural image pretraining—but direct robustness evaluation is absent. A negative result (no robustness advantage) would not invalidate BOFT's practical utility but would constrain the theoretical narrative about geometric preservation.

Efficient butterfly matrix multiplication for training speed. The paper acknowledges in Section 7 that "the training runtime overhead is slightly larger than OFT" because BOFT requires sequential multiplication of m butterfly components per forward pass, but provides no quantitative measurements. This is a practical barrier to adoption—if BOFT training is 2× slower than LoRA for a 1% accuracy gain, many practitioners will choose LoRA. A systems-focused follow-up would implement optimized CUDA kernels for butterfly-structured matrix multiplication, exploiting the known sparsity patterns to fuse operations and reduce memory bandwidth. The specific goal is to make BOFT training speed competitive with LoRA (where the low-rank update is a simple AB product). Existing work on butterfly matrix implementations (Dao et al., 2022; Chen et al., 2022) provides a starting point, but these are optimized for training from scratch rather than for the PEFT setting where the butterfly components are small relative to the frozen pretrained weights. Measuring the training throughput (tokens/second) of an optimized BOFT implementation vs. LoRA on a standard Llama-2-7B finetuning task would provide the actionable cost-benefit data that the current paper lacks.

Practical Applications and Downstream Use Cases

High-quality specialized segmentation with minimal overhead. The BOFT-SAM results in Table 5 demonstrate a deployment scenario with immediate practical value: adapting SAM to high-quality segmentation on specific domains (medical imaging, industrial inspection, satellite imagery) while using only 0.06M trainable parameters and introducing zero inference latency. A medical imaging company could finetune SAM on their proprietary organ-segmentation dataset using BOFT, achieving HQ-SAM-competitive accuracy without the inference slowdown that HQ-SAM's additional modules would introduce in a real-time surgical guidance system. The key numbers: BOFT-SAM achieves 89.5% average mIoU and 82.2% mBIoU across four challenging segmentation datasets while using 4.5% of HQ-SAM's trainable parameters and matching the original SAM's inference speed. For any application where SAM's zero-shot segmentation is insufficient but adding inference latency is unacceptable (robotics, autonomous driving, live video processing), BOFT-SAM provides the accuracy of specialized adaptation with the speed of the base model.

On-device or low-resource finetuning of large vision models. The VTAB-1K results (Table 4) show that BOFT with DINOv2-large achieves 77.9% average accuracy across 19 diverse tasks using only 1.77M trainable parameters—less than 0.6% of the 304M parameter model. This parameter efficiency matters acutely in settings where the finetuned model must be stored or transmitted, not just where training memory is limited. A mobile application that needs to adapt a vision model per-user (e.g., personalized photo organization, custom object recognition for accessibility) could store or download only the 1.77M BOFT parameters per user rather than a full 304M-parameter finetuned model—a 171× reduction in storage. The merged inference property is critical here: after downloading the user-specific BOFT parameters and merging them into the base model, inference runs at full speed with no additional overhead. This is superior to adapter-based approaches that would add per-user modules to the inference graph, slowing down every forward pass.

Controllable generation with post-hoc adjustment of control strength. The weight interpolation property demonstrated in Figure 10—where progressively setting butterfly components to identity produces a smooth interpolation between fully controlled and uncontrolled generation without retraining—enables a practical deployment scenario that no other PEFT method supports. A creative tool using Stable Diffusion with BOFT-based ControlNet could expose a single "control strength" slider to the user. Under the hood, the slider maps to the number of active butterfly components, smoothly blending between following the control signal strictly (all components active, landmark error 5.667) and following the text prompt freely (all components identity, standard Stable Diffusion behavior). The interpolation is free—no retraining, no additional inference cost, no storage of multiple checkpoints. This is impossible with LoRA (which has no natural interpolation mechanism) or block-diagonal OFT (which lacks the multi-scale factorization that enables smooth interpolation). For any application where users want adjustable trade-offs between control fidelity and creative freedom—pose-guided character generation, layout-to-image synthesis, style transfer—BOFT provides this capability at zero additional implementation cost beyond what is needed for the finetuning itself.

Subject-driven generation with better identity preservation. The DreamBooth qualitative results (Figures 9, 12-15) suggest that BOFT "can achieve the best of both worlds by simultaneously demonstrating good subject identity preservation as well as accurate text prompt following ability." While the lack of quantitative metrics limits the strength of this claim, the consistent qualitative pattern across eight subjects (backpack, teapot, vase, sneaker, glasses, toy, dog, stuffed animal) and diverse contexts (3–6 prompts per subject) is suggestive. A product photography application that needs to generate images of a specific product in many scenes would benefit from BOFT's apparent ability to maintain the product's visual identity while accurately rendering the requested background. The practical advantage over LoRA is that BOFT appears less prone to identity drift (where the product's appearance changes across generations) while still following the prompt. This is a direct consequence of the orthogonal constraint: by preserving the pairwise relationships between features that encode the subject's identity, BOFT makes it harder for the model to distort the subject when adapting to diverse backgrounds.