pith. sign in

arxiv: 2604.07045 · v1 · submitted 2026-04-08 · 📡 eess.SP

Tree Search Algorithms Applied to the BD-RIS Configuration in MU-MISO Communication Systems

Pedro H. C. de Souza (1) , Luciano Mendes (1) ((1) National Institute of Telecommunications) This is my paper

Pith reviewed 2026-05-10 17:23 UTC · model grok-4.3

classification 📡 eess.SP
keywords BD-RIStree searchMU-MISOreconfigurable intelligent surfacechannel strength maximizationconfiguration optimizationwireless communicationsdepth-first search
0
0 comments X

The pith

A depth-first tree search algorithm configures BD-RIS reflection parameters in MU-MISO systems to maximize channel strength while scaling computation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proposes a depth-first tree search method to choose the many adjustable reflection settings made possible by the beyond-diagonal reconfigurable intelligent surface in multi-user multiple-input single-output wireless links. The goal is to find configurations that strengthen the overall channels without the exponential cost of checking every possible combination. A sympathetic reader would care because the extra circuit connections in BD-RIS create many more useful reflection patterns than ordinary surfaces, yet those patterns are useless unless a fast optimizer can locate them. If the claim holds, system designers gain a concrete tool that turns the added hardware complexity of BD-RIS into measurable signal gains at acceptable runtime.

Core claim

The authors introduce a depth-first tree search algorithm that traverses the configuration space of the BD-RIS to select reflection coefficients for a MU-MISO downlink. The method exploits the tree structure to explore promising branches first, delivering a favorable balance between achieved channel strength and the number of configurations evaluated as the surface size grows.

What carries the argument

A depth-first tree search that builds partial configurations of the BD-RIS elements level by level and prunes or continues branches according to an objective of summed channel strength.

If this is right

  • The algorithm yields higher aggregate channel strength than greedy or random selection methods at comparable runtimes.
  • Computation time grows more slowly than exhaustive search as the number of BD-RIS elements or users increases.
  • The approach remains feasible for surfaces whose total configuration count is too large for brute-force evaluation.
  • It supports real-time or near-real-time reconfiguration when channel coherence time allows a moderate number of node visits.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar tree-search structures could be adapted to other discrete electromagnetic optimization tasks that currently rely on convex relaxation or machine-learning surrogates.
  • Combining the depth-first traversal with early stopping criteria based on channel statistics might further reduce average latency in slowly varying environments.
  • Hardware implementations could embed the search logic directly in the surface controller, removing the need to ship full channel matrices to a central processor.

Load-bearing premise

That the depth-first ordering reliably reaches near-optimal configurations without exhaustive enumeration or getting trapped in weak branches under typical MU-MISO channel conditions.

What would settle it

A small-scale simulation in which the tree search returns channel strengths more than a few percent below an exhaustive-search optimum while its runtime still grows faster than linear in the number of elements.

Figures

Figures reproduced from arXiv: 2604.07045 by Luciano Mendes (1) ((1) National Institute of Telecommunications), Pedro H. C. de Souza (1).

Figure 1
Figure 1. Figure 1: An example of the tree search exploration executed by Algorithm 1. [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Average channel gain achieved by the proposed BD-RIS configuration [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Depiction of the communications scenario investigated. [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 5
Figure 5. Figure 5: For these results, the Algorithm 2 with branch [PITH_FULL_IMAGE:figures/full_fig_p006_5.png] view at source ↗
Figure 4
Figure 4. Figure 4: The average channel gain is computed for a range of different BD-RIS matrix sizes, [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The average channel gain is computed for a range of different BD-RIS matrix sizes, [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Computational complexity of Algorithm 2 based on its average runtime. The settings used for Algorithm 2 are identical to those reported for Figure 4. [PITH_FULL_IMAGE:figures/full_fig_p008_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The impact of the branch pruning parameters, [PITH_FULL_IMAGE:figures/full_fig_p009_7.png] view at source ↗
read the original abstract

The reconfigurable intelligent surface (RIS) has attracted considerable attention of both academia and industry in recent years, given its capacity to dynamically manipulate the reflection of incident electromagnetic waves. Although the research developed for the RIS may have reached its maturity, there are still contentious aspects and limitations regarding its potential benefits for the next generation of wireless communications. In order to improve upon the the RIS technology, the beyond diagonal reconfigurable intelligent surface (BD-RIS) was recently proposed as an promising alternative. The BD-RIS boasts a more sophisticated circuit topology that is capable of providing more combinations of different adjustments or configurations for signal reflection. However, to aptly reap the benefits of the BD-RIS, the added degrees-of-freedom of its configuration must be leveraged accordingly. Therefore, in this work we propose a depth-first tree search algorithm for configuring the BD-RIS in multi-user multiple-input single-output (MU-MISO) communication systems. Taking advantage of the tree search exploration, the proposed algorithm achieves a remarkable trade-off between channel strength maximization performance and computational complexity scalability.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript proposes a depth-first tree search algorithm for optimizing the configuration of a beyond-diagonal reconfigurable intelligent surface (BD-RIS) in multi-user MISO (MU-MISO) systems. The central claim is that the algorithm leverages tree-search exploration to achieve a strong trade-off between maximizing channel strength and maintaining computational scalability.

Significance. If the proposed depth-first search demonstrably delivers near-optimal channel-strength performance with complexity that scales better than exhaustive search for realistic BD-RIS sizes, the work would be useful for practical BD-RIS deployment where the increased degrees of freedom make conventional optimization intractable. The paper does not appear to supply machine-checked proofs, reproducible code, or parameter-free derivations, so its value rests entirely on the empirical and analytical support for the claimed trade-off.

major comments (2)
  1. [Abstract and algorithm description] The central claim that depth-first tree search yields a 'remarkable trade-off' between performance and scalability is load-bearing yet unsupported by any complexity bound, pruning analysis, or worst-case scaling result. Standard depth-first search without explicit bounding or early termination explores an exponential number of leaves when the number of BD-RIS elements or reflection states grows; the manuscript must supply either a proven pruning rule or a rigorous big-O analysis that shows the explored fraction remains sub-exponential under the MU-MISO channel model.
  2. [Abstract] No simulation results, baselines (e.g., exhaustive search, random configuration, or gradient-based methods), error metrics, or channel assumptions (i.i.d. Rayleigh vs. correlated) are referenced in the abstract or visible description. Without these, it is impossible to verify whether the reported performance-complexity points actually support the scalability claim for array sizes beyond the smallest cases.
minor comments (1)
  1. [Abstract] The abstract contains a repeated 'the' ('improve upon the the RIS technology').

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. We agree that the abstract and complexity claims require strengthening and will revise accordingly. Below we respond point-by-point to the major comments.

read point-by-point responses

  1. Referee: [Abstract and algorithm description] The central claim that depth-first tree search yields a 'remarkable trade-off' between performance and scalability is load-bearing yet unsupported by any complexity bound, pruning analysis, or worst-case scaling result. Standard depth-first search without explicit bounding or early termination explores an exponential number of leaves when the number of BD-RIS elements or reflection states grows; the manuscript must supply either a proven pruning rule or a rigorous big-O analysis that shows the explored fraction remains sub-exponential under the MU-MISO channel model.

    Authors: We acknowledge that the current manuscript does not include a formal complexity bound or explicit pruning analysis. The proposed depth-first search does employ early termination when the partial configuration's projected channel strength cannot exceed the incumbent best solution, but this rule is described only at a high level. We agree a rigorous treatment is needed. In the revised manuscript we will add: (i) a precise statement of the pruning criterion, (ii) an average-case complexity discussion under i.i.d. Rayleigh MU-MISO channels showing that the fraction of explored nodes decreases with array size in our tested regimes, and (iii) tabulated scaling results up to 16 BD-RIS elements. We note that a worst-case exponential bound cannot be avoided for any exact tree search; our claim is therefore limited to practical scalability, which we will make explicit. revision: yes

  2. Referee: [Abstract] No simulation results, baselines (e.g., exhaustive search, random configuration, or gradient-based methods), error metrics, or channel assumptions (i.i.d. Rayleigh vs. correlated) are referenced in the abstract or visible description. Without these, it is impossible to verify whether the reported performance-complexity points actually support the scalability claim for array sizes beyond the smallest cases.

    Authors: We agree the abstract is too terse. The revised abstract will explicitly state: (a) the performance metric (normalized channel strength), (b) the main baselines (exhaustive search for small sizes, random configuration, and a gradient-based benchmark), (c) the channel model (i.i.d. Rayleigh fading), and (d) representative complexity numbers (e.g., explored nodes versus BD-RIS size). These details already appear in the simulation section; moving a concise summary into the abstract will address the concern. revision: yes

Circularity Check

0 steps flagged

No circularity detected in algorithmic proposal

full rationale

The manuscript proposes a depth-first tree search algorithm to configure BD-RIS elements in MU-MISO systems, claiming a performance-complexity trade-off from tree exploration. No equations, parameter fits, self-citations of uniqueness results, or ansatzes appear in the abstract or description. The central claim is an empirical algorithmic outcome evaluated on channel strength maximization, not a derivation that reduces to its own inputs by construction. The work is self-contained as a heuristic search method whose validity rests on simulation results rather than self-referential definitions or fitted predictions.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based solely on the abstract, the paper introduces no identifiable free parameters, axioms, or invented entities. It applies an existing search technique to a configuration problem without postulating new physical quantities or unproven assumptions beyond standard wireless models.

pith-pipeline@v0.9.0 · 5496 in / 1198 out tokens · 60324 ms · 2026-05-10T17:23:21.649646+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages · 1 internal anchor

  1. [1]

    Potential standardization work for reconfigurable intelligent surface white paper,

    N. Li, Y . Yuan, Q. Liu, Y . Zhao, S. Jinet al., “Potential standardization work for reconfigurable intelligent surface white paper,” inFuTURE Forum, Nanjing, China, 2025

    work page 2025

  2. [2]

    Electric dipole-magnetic quadrupole resonant coupling for broadband operating metasurfaces,

    J. A. P. Ribeiro, J. J. Hernandez-Sarria, L. A. M. Pereira, A. C. Sodr ´e, O. N. d. Oliveira Junior, L. L. Mendes, and J. R. Mej´ıa-Salazar, “Electric dipole-magnetic quadrupole resonant coupling for broadband operating metasurfaces,”IEEE Transactions on Antennas and Propagation, 2025

    work page 2025

  3. [3]

    Reconfigurable intelligent surfaces in upper mid-band 6g networks: Gain or pain?

    F. Kara, O. T. Demir, and E. Bj ¨ornson, “Reconfigurable intelligent surfaces in upper mid-band 6g networks: Gain or pain?”IEEE Wireless Communications, pp. 1–9, 2025

    work page 2025

  4. [4]

    A tutorial on beyond- diagonal reconfigurable intelligent surfaces: Modeling, architectures, system design and optimization, and applications,

    H. Li, M. Nerini, S. Shen, and B. Clerckx, “A tutorial on beyond- diagonal reconfigurable intelligent surfaces: Modeling, architectures, system design and optimization, and applications,”IEEE Communica- tions Surveys & Tutorials, vol. 28, pp. 4086–4126, 2026

    work page 2026

  5. [5]

    A low-complexity beamforming design for beyond-diagonal RIS aided multi-User networks,

    T. Fang and Y . Mao, “A low-complexity beamforming design for beyond-diagonal RIS aided multi-User networks,”IEEE Communica- tions Letters, vol. 28, no. 1, pp. 203–207, 2024

    work page 2024

  6. [6]

    Riemannian optimization on the manifold of unitary and symmetric matrices with application to BD-RIS-assisted systems,

    I. Santamaria, M. Soleymani, E. Jorswieck, J. Gutierrez, and C. Beltran, “Riemannian optimization on the manifold of unitary and symmetric matrices with application to BD-RIS-assisted systems,” 2026. [Online]. Available: https://arxiv.org/abs/2601.13877

    work page arXiv 2026

  7. [7]

    Exploiting beyond diagonal RIS in beamforming design for MU-MISO communications,

    X. Zhang, Z. Wu, Y . Ren, X. Ma, and H. Zhang, “Exploiting beyond diagonal RIS in beamforming design for MU-MISO communications,” IEEE Transactions on Vehicular Technology, pp. 1–6, 2025

    work page 2025

  8. [8]

    Fractional programming and manifold optimization for reciprocal BD-RIS scattering matrix design,

    M. Fidanovski, I. A. M. Sandoval, K. R. R. Ranasinghe, G. T. F. de Abreu, E. Bj ¨ornson, and B. Clerckx, “Fractional programming and manifold optimization for reciprocal BD-RIS scattering matrix design,”

    work page

  9. [9]

    Available: https://arxiv.org/abs/2511.07683

    [Online]. Available: https://arxiv.org/abs/2511.07683

    work page internal anchor Pith review arXiv

  10. [10]

    Joint beamforming and bs selection for energy-efficient communications via aerial-RIS,

    J. J. L. Quispe, T. F. Maciel, Y . C. B. Silva, and A. Klein, “Joint beamforming and bs selection for energy-efficient communications via aerial-RIS,” in2021 IEEE Globecom Workshops (GC Wkshps), 2021, pp. 1–6

    work page 2021

  11. [11]

    An information- theoretic branch-and-prune algorithm for discrete phase optimization of RIS in massive MIMO,

    I. Z. Ahmed, H. R. Sadjadpour, and S. Yousefi, “An information- theoretic branch-and-prune algorithm for discrete phase optimization of RIS in massive MIMO,”IEEE Transactions on Vehicular Technology, vol. 72, no. 6, pp. 7395–7410, 2023

    work page 2023

  12. [12]

    Optimal discrete beamforming of RIS-aided wireless communications: An inner product maximization approach,

    R. Xiong, X. Dong, T. Mi, K. Wan, and R. C. Qiu, “Optimal discrete beamforming of RIS-aided wireless communications: An inner product maximization approach,” in2024 IEEE Wireless Communications and Networking Conference (WCNC), 2024, pp. 1–6

    work page 2024

  13. [13]

    Joint discrete precoding and RIS optimization for RIS-assisted MU-MIMO communi- cation systems,

    P. Ramezani, Y . Khorsandmanesh, and E. Bj ¨ornson, “Joint discrete precoding and RIS optimization for RIS-assisted MU-MIMO communi- cation systems,”IEEE Transactions on Communications, vol. 73, no. 3, pp. 1531–1546, 2025

    work page 2025

  14. [14]

    A universal lattice code decoder for fading channels,

    E. Viterbo and J. Boutros, “A universal lattice code decoder for fading channels,”IEEE Transactions on Information Theory, vol. 45, no. 5, pp. 1639–1642, 1999

    work page 1999

  15. [15]

    Hybrid deployment optimization algorithm for reconfigurable intelligent surface,

    Y . Lin, X. Lin, Z. Han, and Y . Wang, “Hybrid deployment optimization algorithm for reconfigurable intelligent surface,”Sensors, vol. 25, no. 23, 2025. [Online]. Available: https://www.mdpi.com/1424-8220/ 25/23/7195

    work page 2025

  16. [16]

    G. H. Golub and C. F. V . Loan,Matrix Computations, 4th ed. Johns Hopkins University Press, 2013

    work page 2013

  17. [17]

    R. A. Horn and C. R. Johnson,Matrix Analysis, 2nd ed. Cambridge university Press, 2012. Pedro H. C. de Souzawas born in Santa Rita do Sapuca´ı, Minas Gerais, MG, Brazil in 1992. He received the B.S., M.S. and the Doctor degrees in telecommunications engineering from the National Institute of Telecommunications - INATEL, Santa Rita do Sapuca ´ı, in 2015, 2...

    work page 2012