PaperlayerView exact revision on arXiv

Source-linked AI summary

ToPA: Block-wise Toeplitz Adaptation for Expressive and Efficient Fine-Tuning

Sicong Li, Qianqian Xu, Zhiyong Yang, Zitai Wang, Longtao Huang, Xiaochun Cao, Qingming Huang

arXiv:2610.22883v1cs.AIcs.LG

TL;DR

Low-rank and sparse PEFT methods can constrain update expressiveness and parameter connectivity. ToPA uses block-wise Toeplitz factors with an identity residual to provide compact, dense, high-rank adaptation while shortening the factor chain. The paper reports that ToPA consistently surpasses multiple baselines across diverse models and tasks.

  • Problem

    Low-rank and sparse reparameterizations can constrain update rank, adaptation flexibility, and connectivity relative to the high-rank updates of full fine-tuning.

    Source: §2.1 · p. 3, §2.2 · p. 4

  • Method

    ToPA adapts pretrained weights with compact block-wise Toeplitz factors and an identity residual, increasing factor capacity and shortening the multiplication chain.

    Source: §1 · pp. 2–3

  • Results

    ToPA consistently surpasses multiple baselines across diverse models and tasks, with theoretical results supporting high-rank, dense adaptation and shorter-chain matrix representation.

    Source: §1 · p. 3

  • Takeaways & Limitations

    ToPA offers a parameter-efficient reparameterization with high-rank, dense adaptation and optimization stability from a shortened factor chain and identity residual.

    Source: §3.3 · p. 5, §7 · p. 10

    Low-rank and fixed-sparsity structures remain constrained: low-rank updates limit expressiveness, while sparse patterns restrict cross-dimensional interactions.

    Source: §2.1 · p. 3, §2.2 · p. 4

Abstract

from arXiv · show

Parameter-Efficient Fine-Tuning (PEFT) has emerged as a prevalent strategy for adapting large pre-trained models. Among PEFT techniques, reparameterization-based methods, particularly those that employ low-rank or sparsity structures, have attracted significant attention. However, these approaches often underperform full fine-tuning. Specifically, low-rank methods constrain the update rank, which is misaligned with the inherently high-rank nature of full fine-tuning. In contrast, sparsity-based techniques limit the flexibility of the parameter space and compromise connectivity across weights. To overcome these limitations, we explore the use of Toeplitz matrices, whose entries are constant along each diagonal, therefore providing a compact parameterization without imposing explicit rank or sparsity constraints. A straightforward approach is to update weights via a product of Toeplitz matrices. However, similar to RNNs, long multiplicative chains often lead to gradient instability. To address this issue, we propose \textbf{ToPA}, a more refined version of this idea that replaces standard Toeplitz matrices with block-wise Toeplitz, greatly increasing each factor's capacity and shortening the chain, thereby stabilizing training and improving expressiveness. We theoretically show that products of block-wise Toeplitz matrices can approximate arbitrary matrices under shorter chain length, justifying the structural design of ToPA. Furthermore, we demonstrate that ToPA offers greater expressivity than existing low-rank and sparse parameterizations. Empirical evaluations across 21 NLP and CV datasets, spanning 5 model architectures, consistently validate the effectiveness of ToPA.

1 Introduction

PEFT reduces the cost of adapting pretrained models, but low-rank and sparse reparameterizations can constrain update expressiveness. ToPA uses block-wise Toeplitz factors and an identity residual to target dense, high-rank adaptation with a compact parameter budget.

1 Introduction

  • Low-rank updates can restrict expressiveness because full fine-tuning typically produces high-rank updates, while fixed sparsity can reduce parameter connectivity.These limitations motivate a compact parameterization that can better match full fine-tuning’s expressiveness.Source: §1 · p. 2
  • Toeplitz matrices provide a compact parameterization without explicit rank or sparsity constraints, and any matrix can be represented as a product of Toeplitz matrices.An n × n Toeplitz matrix has 2n − 1 free parameters, and matrix–vector multiplication can be implemented in O(n log n) time via FFT.Source: §1 · p. 2
  • A long chain of standard Toeplitz factors can cause gradient explosion, so ToPA uses higher-capacity block-wise factors to shorten the chain.Under the same parameter budget, the required chain length can be reduced by roughly a factor of p; an identity residual further stabilizes optimization.Source: §1 · pp. 2–3
  • The paper reports theoretical support for high-rank, dense adaptation and shorter-chain matrix representation, alongside experiments where ToPA consistently surpasses multiple baselines.The evaluations span natural-language understanding, subject-driven generation, commonsense reasoning, and math and code generation across multiple models.Source: §1 · p. 3
  • ToPA’s block-wise Toeplitz factors and identity residual support dense, high-rank adaptation while retaining a compact parameter budget.The paper reports that block-wise factors increase capacity and shorten the multiplication chain, while the identity residual stabilizes optimization.Source: Figure 1 · p. 2, §1 · p. 3

2 Preliminaries

This section reviews low-rank and sparsity structures in reparameterization-based PEFT and describes how their constraints may limit adaptation expressiveness and flexibility.

2 Preliminaries

  • The preliminaries focus on low-rank and sparsity constraints as structural limitations of existing reparameterization approaches.The section frames these constraints as potential barriers to expressiveness and adaptation flexibility.Source: §2 · p. 3

2.1 Low-rank Decomposition and its Limitation

  • Low-rank updates can constrain expressiveness because full fine-tuning generally produces high-rank update matrices.For LLaMA-2-7B math reasoning, the reported full fine-tuning rank is about 3758, compared with LoRA ranks such as 16, 32, and 64.Source: §2.1 · p. 3, Figure 2 · p. 3

2.2 Sparsity Structure and its Limitations

  • Sparsity-based methods impose a fixed pattern that restricts adapted columns to predefined subspaces and reduces cross-dimensional interactions.In the LLaMA-2-7B math-reasoning setting, OFT and BOFT adapter nonzero ratios range from approximately 0.5% to 6.5%.Source: §2.2 · p. 4

3 Methodology

ToPA uses compact Toeplitz structure for expressive adaptation, replacing unstable long chains with block-wise factors and a residual connection. Its initialization preserves pretrained behavior at the start of training.

3.1 Toeplitz Matrix

  • A standard n×n Toeplitz matrix uses 2n−1 parameters, supports FFT multiplication in O(n log n), and products of such matrices can represent any matrix with sufficient depth.Every n×n matrix is generically a product of ⌊n/2⌋+1 Toeplitz matrices and always a product of at most 2n+5.Source: §3.1 · p. 4

3.2 A Naive Implementation

  • Long Toeplitz-factor chains can cause gradient explosion; in the matched-parameter LLaMA-3-8B test, gradients and loss fluctuate, and the naive method collapses.The gradient contains products of preceding and following factors, tending to grow exponentially with chain length when intermediate spectral norms exceed one.Source: §3.2 · p. 5, Figure 3 · p. 5

3.3 ToPA: Block-wise Toeplitz Adaptation

  • Block-wise Toeplitz factors provide roughly p times the parameters per factor, reducing chain length by a factor of p at the same budget.The residual term centers adaptation around the identity, stabilizing optimization and keeping adapted weights close to pretrained initialization.Source: §3.3 · pp. 5–6
  • Under the same parameter budget, ToPA shows smoother training dynamics than the naive implementation.The comparison uses LLaMA-3-8B on commonsense reasoning, with the naive method at t=16 and ToPA at t=2, p=8.Source: Figure 3 · p. 5, §3.3 · p. 6

3.4 Initialization Strategy of ToPA

  • To preserve the pretrained model’s initial behavior, ToPA initializes its first block-wise Toeplitz matrix to zero and the others from a normal distribution.This asymmetric initialization makes the learnable modules contribute zero output at the start of training.Source: §3.4 · p. 6

4 Theoretical Analysis

ToPA’s block-wise Toeplitz structure supports high-rank, dense adaptation and stronger expressivity than low-rank or sparse parameterizations. Its products can represent arbitrary matrices with shorter chains, and some adaptations require fewer parameters than with either alternative.

4.1 Achieving High-Rank and Dense Adaptation

  • ToPA’s updates have the same rank as the pretrained weights almost surely, and its adapters are substantially denser than those from OFT and BOFT.Because pretrained weights typically have high rank, ToPA yields substantially higher-rank updates than LoRA under comparable parameter budgets.Source: §4.1 · p. 6

4.2 Expressive Power of ToPA

  • Every n×n matrix is generically a product of ⌊n/(2p)⌋+1 block-wise Toeplitz matrices and always a product of at most 2n/p+5.This represents arbitrary matrices with a shorter chain than the classical results for standard Toeplitz matrices.Source: §4.2 · p. 6
  • For a class of adapted weight matrices, ToPA uses O(n) trainable parameters, versus at least O(n^2) for LoRA and O(n log n) for OFT or BOFT.The theorem identifies adaptations that ToPA represents compactly but neither low-rank nor sparse approaches capture efficiently.Source: §4.2 · pp. 6–7

5 Experiments

Experiments span commonsense reasoning, math and code generation, subject-driven generation, and GLUE, using multiple model families and task-specific baselines. ToPA generally leads across these settings, while ablations examine parameter scale, block count, chain length, and identity residuals.

5.2 Commonsense Reasoning

  • ToPA leads or performs competitively across commonsense, math and code, subject-driven generation, and GLUE tasks, generally with comparable or fewer parameters.The GLUE results also report a slight LPIPS diversity trade-off in subject-driven generation and a marginal shortfall on MBPP.Source: §5.2 · p. 8, §5.3 · p. 8, §5.4 · p. 8
  • 81.4% on LLaMA-2-7B and 86.3% on LLaMA-3-8B are ToPA’s leading average scores on commonsense reasoning.It has the best average performance across both backbones while maintaining a comparable or smaller parameter count.Source: §5.2 · p. 8

5.3 Math Reasoning & Code Generation

  • 74.7% on GSM8K and 51.8% on HumanEval with LLaMA-3-8B exceed the strongest baseline by 0.9% and 0.6%, respectively.On Qwen3-4B, ToPA reaches 84.3% on GSM8K and 73.2% on HumanEval; it is marginally below the leading method on MBPP.Source: §5.3 · p. 8

5.4 Subject-Driven Generation

  • ToPA surpasses baselines on DINO, CLIP-I, and CLIP-T under comparable or reduced parameter budgets, with a marginal LPIPS diversity trade-off.The prose associates DINO and CLIP-I with subject fidelity and CLIP-T with prompt alignment, and reports qualitative gains over LoRA and OFT in Figure 4.Source: §5.4 · p. 8, Table 4 · p. 8, Figure 4 · p. 8

5.5 Natural Language Understanding

  • 88.75 is ToPA’s best average GLUE score with about 0.44M parameters, including a 0.29% average-score gain and first- or second-place rankings across eight tasks.Table 5 reports Matthew’s correlation for CoLA, Pearson correlation for STS-B, matched accuracy for MNLI, and accuracy for the other datasets.Source: §5.5 · pp. 8–9, Table 5 · p. 9

5.6 Performance Comparison across Parameter Scales

  • ToPA outperforms LoRA at each matched parameter scale on both GSM8K and MATH in the LLaMA-3-8B comparison.The comparison uses LoRA ranks 8, 16, and 32, and ToPA with t = 3 and p values 2, 4, and 8.Source: §5.6 · p. 9, Figure 7 · p. 9

5.7 Influence of p and t

  • Increasing p from 1 to 8 at t = 3 consistently improves accuracy on all three commonsense datasets; increasing t from 1 to 3 at p = 8 also improves performance.At t = 4, accuracy slightly drops on OBQA and PIQA, which the authors attribute possibly to optimization instability in longer chains.Source: §5.7 · p. 9, Figure 5 · p. 9

5.8 Ablation Study of Identity Residual

  • Adding the identity residual consistently improves performance across evaluated commonsense datasets on both LLaMA-2-7B and LLaMA-3-8B.Source: Figure 6 · p. 9, §5.8 · p. 10

6 Related Work

Related work groups PEFT approaches into reparameterization-based and other methods. Reparameterization includes low-rank and sparse structures, while other approaches use prompts, adapters, or selective parameter updates.

6.1 Reparameterization-Based Methods

  • Low-rank reparameterization ranges from LoRA’s two-factor updates to variants that alter magnitude-direction tuning, use SVD, Hadamard products, or series connections with a diagonal ridge.The section also describes sparse orthogonal approaches: OFT uses a sparse orthogonal matrix, BOFT uses multiple sparse butterfly matrices, and PSOFT limits transformations to a low-rank principal subspace.Source: §6.1 · p. 10

6.2 Other PEFT Methods

  • Other PEFT methods learn task prompts or prefixes, insert adapter modules, or selectively tune existing parameters such as biases and activation gates.Examples include Prompt Tuning, Prefix Tuning, Adapter, AdaptFormer, BitFit, and IA3.Source: §6.2 · p. 10

7 Conclusion

The conclusion presents ToPA as a parameter-efficient block-wise Toeplitz framework for dense, high-rank updates, supported by theoretical expressiveness results and experiments. The appendix proof passages outline a gradient derivation and a rank-preservation argument for products of block-wise Toeplitz matrices.

7 Conclusion

  • ToPA is presented as enabling high-rank, dense updates with parameter efficiency and optimization stability, and as more expressive than low-rank and sparse methods.The conclusion cites theoretical compositional expressiveness and experiments across diverse models and tasks as support for the approach.Source: §7 · p. 10

A.1 Proof of Prop. 3.2

  • The gradient proof begins with G := ∇W L and derives the gradient with respect to each factor Ti from the induced differential of W and the loss differential.Source: §A.1 · p. 18

A.2 Proof of Prop. 4.1

  • The rank proof bounds rank(∆W) and uses that the product of block-wise Toeplitz factors is invertible with probability 1 to attain the bound.The proof states that the singular-product set has measure zero, then uses rank preservation under invertible right multiplication.Source: §A.2 · pp. 18–19

A.3 Proof of Thm. 4.2

The appendix establishes factorization expressivity for block-wise Toeplitz products and develops a parameter-efficiency comparison for a constructed adaptation. It also describes the construction, its dense full-rank properties, and OFT/BOFT structures relevant to the lower-bound argument.

A.3 Proof of Thm. 4.2

  • Every matrix A ∈ Cn×n admits a factorization into a product of at most 4r0 + 1 block-wise Toeplitz matrices.Source: §A.3 · p. 19

A.4 Proof of Thm. 4.3

  • For a full-column-rank pretrained weight, the theorem gives a class of adapted weights realizable by ToPA with O(n) trainable parameters, versus at least O(n2) for LoRA and O(n log n) for OFT or BOFT.Source: §A.4 · p. 21

1. Construction of the Adaptation via ToPA.

  • The construction chooses constant t and p and forms the adapter from a product of block-wise Toeplitz matrices parameterized by Toeplitz sub-blocks.The passage states that the total trainable parameter count is calculated for this adaptation, but the supplied text does not show the expression.Source: §1 · p. 22

2. Properties of the Adaptation.

  • Under the stated continuous parameter distribution, the constructed update is dense and full rank almost surely; the adapted weight uniquely determines its adapter when W0 has full column rank.The proof uses invertibility of the product to preserve the rank of W0.Source: §2 · p. 22

3. Parameter Lower Bounds for LoRA and OFT/BOFT.

  • Matching the constructed adaptation requires LoRA to use at least O(n2) parameters and OFT or BOFT at least O(n log n).The argument relies on the dense adapter and, for BOFT, a stated lower bound for representing a dense matrix with butterfly factors.Source: §3 · p. 23

B Detailed Introduction of OFT and BOFT

  • OFT uses one block-diagonal sparse orthogonal matrix, whereas BOFT generalizes it as a product of sparse orthogonal factors built from butterfly factors.The BOFT factors are described as block diagonal, with butterfly factors comprising learnable b × b sub-blocks.Source: B Detailed Introduction of OFT and BOFT · p. 23

C Analysis of Parameter and Computation Cost

ToPA’s block-wise Toeplitz factors provide a parameter-efficient adaptation, with computation costs analyzed through blockwise products and FFT-based Toeplitz multiplication. Experiments report moderate overhead over low-rank methods but greater efficiency than sparsity-structured methods.

C.1 Parameter Cost

  • ToPA uses tp(2n −p) parameters, broadly comparable to LoRA’s r(m + n) when m ≈n and tp ≈r, while enabling richer updates.A block-wise Toeplitz factor with p blocks contributes p(2n −p) parameters; a chain of length t contributes tp(2n −p).Source: §C.1 · p. 24

C.2 Computation Cost

  • A chain of t block-wise Toeplitz multiplications costs O(tpn log q), with each factor applied through p² Toeplitz block–vector products.Each block–vector product costs O(q log q) using FFT-based Toeplitz multiplication.Source: §C.2 · pp. 24–25
  • ToPA has moderate overhead over LoRA, DoRA, and HiRA, but is substantially more efficient than OFT and BOFT.The efficiency comparison measures average wall-clock time per training step and peak GPU memory; BOFT runs out of memory on LLaMA-2-7B under the matched setting without gradient checkpointing.Source: §C.2 · p. 25, Table 6 · p. 25, Table 7 · p. 25

D Fast Matrix–Vector Multiplication for Toeplitz Matrices

  • Embedding a Toeplitz matrix in a larger circulant matrix enables FFT-based multiplication in O(n log n) time.The desired product is recovered by zero-padding the input, multiplying through the circulant embedding, and selecting the first n output coordinates.Source: D Fast Matrix–Vector Multiplication… · p. 26

E.1 Datasets

The evaluation spans language understanding, commonsense reasoning, math and code generation, and subject-driven image generation. Experiments compare ToPA with several adaptation methods using task-specific model configurations.

E.1 Datasets

  • The evaluation covers eight GLUE datasets, eight commonsense benchmarks, four math and code datasets, and DreamBooth subject-driven generation.The tasks span sentence-level and sentence-pair language understanding, commonsense inference, math reasoning, code generation, and personalized image synthesis.Source: §E.1 · pp. 26–28

E.2 Competitors

  • Competitors include low-rank approaches such as LoRA and HiRA, and structured orthogonal approaches such as OFT, BOFT, and HRA.The listed competitors also include DoRA, PiSSA, and RidgeLoRA.Source: §E.2 · p. 29

E.3 Implementation Details

  • Implementation uses DeBERTaV3-Base, Stable Diffusion v1.5, LLaMA-2/3, and Qwen3, with adapters inserted into task-specific model projections.Pretrained weights are frozen in the described NLU and commonsense settings; the math and code experiments use a cosine learning-rate schedule and train for one epoch.Source: §E.3 · pp. 29–30

F.1 Additional Ablation Study of the Identity Residual

Additional experiments report gains from the identity residual, more stable training than the naive long-chain method, and robust performance across seeds. Qualitative subject-generation comparisons also favor ToPA over LoRA and OFT on fidelity and instruction following.

F.1 Additional Ablation Study of the Identity Residual

  • With the identity residual, ToPA gains consistently across all evaluated LLaMA-3-8B math and code datasets.The ablation compares ToPA with and without the identity matrix at t=3 and p=8.Source: §F.1 · p. 30, Table 9 · p. 30

F.2 Additional Results on Training Instability in the Naive Method

  • On LLaMA-2-7B commonsense reasoning, ToPA has smoother, smaller gradient norms and training loss than the naive method, which shows substantial fluctuations.The comparison uses matched parameters and follows the first 300 training steps shown in Fig. 8.Source: §F.2 · p. 30, Figure 8 · p. 30

F.3 Multi-Seed Evaluation on Math Reasoning and Code Generation

  • Across three random seeds, ToPA achieves the best or tied-best average on LLaMA-3-8B math and code tasks under a comparable parameter budget.The reported results are averaged over three random seeds.Source: §F.3 · p. 31, Table 10 · p. 31

F.4 Additional Qualitative Results for Subject-Driven Generation

  • Qualitative subject-generation examples show higher subject fidelity and stronger instruction following for ToPA than for LoRA and OFT.The comparisons are presented in Fig. 9, Fig. 10, and Fig. 11.Source: §F.4 · p. 31, Figure 9 · p. 31

F.5 Qualitative Results for Math Reasoning

Qualitative math-reasoning examples show ToPA producing more accurate and reliable answers than LoRA. The examples include cases where the two methods give different answers to the same problem.

F.5 Qualitative Results for Math Reasoning

  • ToPA consistently produces more accurate and reliable answers than LoRA in the presented math-reasoning examples.The paper presents these examples as qualitative support for ToPA’s math-reasoning capability.Source: §F.5 · p. 31
  • For the drink-mixture question, ToPA answers 15 liters of water in the remaining 24 liters, while LoRA answers 14.67 liters.The ToPA response accounts for the spilled liter by reducing the orange drink before calculating its remaining water.Source: §F.5 · p. 32
  • For the translation question, ToPA gives −5 + 3i, while LoRA’s response proceeds through an incorrect distance-based calculation.The ToPA answer follows the stated translation by adding 1 to the real part and 3 to the imaginary part.Source: §F.5 · p. 34

G Limitations

The authors identify single-modal evaluation and experiments limited to models up to 8B as scope boundaries. They also discuss potential benefits and downstream risks, and affirm that the paper’s claims reflect its contributions and evidence.

G Limitations

  • Evaluation focuses mainly on single-modal backbones; multimodal models, including vision-language models, remain a direction for future work.The authors note that cross-modal interactions may introduce new adaptation requirements.Source: G Limitations · p. 36
  • Experiments cover models up to the 8B scale, leaving larger-scale scalability and practical behavior for future investigation.The authors cite computational resource constraints as the reason for this experimental boundary.Source: G Limitations · p. 37

H Broader Impacts

  • The paper describes potential benefits from reducing adaptation costs, including greater accessibility and possibly lower environmental costs.The environmental benefit is presented as a possibility, not a measured result.Source: H Broader Impacts · p. 37
  • The authors identify task-dependent risks in downstream deployment, including misuse, bias, and unreliable generations.The work is described as methodological and not targeted at a specific high-risk application.Source: H Broader Impacts · p. 37

NeurIPS Paper Checklist

  • The checklist affirms that the abstract and introduction accurately reflect the proposed method, theoretical analysis, and empirical results.Source: NeurIPS Paper Checklist · p. 38

2. Limitations

Checklist responses report that the paper discusses its limitations and broader impacts, while also documenting asset use, study scope, and method choices. The paper reports experiments and provides supporting reproducibility and statistical information.

2. Limitations

  • The checklist says the paper has a dedicated Limitations section covering evaluation scope and future multimodal and larger-scale extensions.Source: §2 · p. 38
  • The checklist reports that the paper specifies key experimental details and that appendix results over multiple random seeds include means and standard deviations.Source: §2 · p. 40

10. Broader impacts

  • The paper’s broader-impacts discussion covers potential benefits of efficient adaptation and general risks associated with adapting large models.Source: §10 · p. 41

11. Safeguards

  • The safeguards item is marked not applicable because the paper releases no new high-risk pretrained models, image generators, or scraped datasets.Source: §11 · p. 42

12. Licenses for existing assets

  • The authors report using publicly available assets, crediting existing datasets, models, and baselines, and following their licenses and terms.Source: §12 · p. 42

13. New assets

  • The new-assets item is marked not applicable because the paper introduces or releases no new standalone datasets, models, or other assets.Source: §13 · p. 43

14. Crowdsourcing and research with human subjects

  • The checklist reports no crowdsourcing, human-subject studies, or user experiments, so IRB approval is not applicable.Source: §14 · pp. 43–44

16. Declaration of LLM usage

  • The core methodology does not use LLMs as an important, original, or non-standard research component.Source: §16 · p. 44

Related papers

Loading 2610.22883v1…