ON PETITIONS FOR REHEARING
REVISED OPINION
Before EDMONDSON and CARNES, Circuit Judges, and HILL, Senior Circuit Judge. CARNES, Circuit Judge:The panel hereby grants rehearing, withdraws the previous panel opinion dated May 4, 1994, and published at 20 F.3d 1489, and substitutes the following opinion:
This litigation began more than twenty years ago when the United States and private parties filed civil rights complaints against the City of Birmingham, the Personnel Board of Jefferson County, and other local governmental agencies and officials.1 The City and the Board share responsibility for hiring and promoting local government employees. The Board, pursuant to state law, administers written tests and other job selection procedures that produce a pool of qualified, or “certified,” candidates for a particular position. See Act of July 6, 1945, No. 248, §§ 2, 16, 1945 Ala. Acts 376, 377-79, 391-92 (“Act of 1945”). The Board ranks the passing applicants and then forwards a list of the top candidates to the City for final selection. See id., § 18, 1945 Ala. Acts at 392-94 (regulating civil service appointments), amended, Act of May 4, 1989, No. 89-467, § 1, 1989 Ala. Acts 967, 967-70 (“Amendments of 1989”). The original complaints alleged, first, that the Board used discriminatory tests to determine eligibility for hiring and promotion, and second, that the City and other “employing agencies engaged in still further discrimination when selecting individuals from [the Board’s] already tainted lists.” In re Birmingham Reverse Discrimination Employment Litig., 37 Fair Empl.Prac.Cas. (BNA) 1, 2, 1985 WL 1415 (N.D.Ala.1985). Over the past twenty years, the resulting litigation has prompted three decisions of this Court and one of the Supreme Court.
This appeal stems from a recent proceeding to modify two consent decrees negotiated thirteen years ago by the original parties. In the present appeal, none of the original parties contends that the district court’s modifications were inappropriate — as far as those modifications went. Instead, the United States, joined by an intervening class of male, non-black employees of the City (the “Wilks class”), contends that the district court failed to go far enough in modifying the consent decrees to address changed circumstances. Because we agree that the Constitution requires further modifications, we reverse a portion of the district court’s order and remand for further proceedings.
More specifically, we hold that the district court should: determine whether the City and the Board have a strong basis in evidence for their conclusion that race-based affirmative action is necessary in departments other than the police and fire departments, and if not, terminate the race-based goals with respect to those other departments; order the City and Board to implement valid job-selection procedures forthwith; prohibit appointments based on race or gender after valid procedures are in place, unless the district court specifically finds that further affirmative action is necessary to remedy the lingering effects of discrimination; revise the decrees’ annual appointment goals for blacks to make them flexible and reasonably related to the pool of qualified black applicants; and award appropriate attorneys’ fees to the Wilks class.
Part I of this opinion sets forth the factual and procedural background of the present litigation. Part II sets forth our standards of review. Part III concerns the decree *1553modification issues: subpart A discusses the applicable law; subpart B applies that law to the decrees’ race-conscious affirmative action provisions; and subpart C applies the law to the decrees’ gender-conscious affirmative action provisions. Part IV involves an attorneys’ fees issue. Part V concludes.
I. BACKGROUND
The size and complexity of this case require that we consider its history in some detail. Whenever possible, we draw on our prior decisions to summarize what has come before.
A. THE COMPLAINTS, FIRST TRIAL, AND APPEAL
The first six years of litigation began with a series of lawsuits against the City and Board alleging discriminatory employment practices:
On January 4, 1974, the Ensley Branch of the National Association for the Advancement of Colored People, together with certain named individuals, for themselves and on behalf of others similarly situated, filed a complaint in the United States District Court for the Northern District of Alabama, against George Seibels (then Mayor of Birmingham, Alabama), the City of Birmingham, the members of the Personnel Board of Jefferson County, and the Personnel Director of that Board, alleging that the defendants engage in discriminatory hiring practices against blacks in violation of the Fourteenth Amendment, 42 U.S.C. §§ 1981, 1983, and 2000e et seq. (Title VII). A suit raising the same constitutional and statutory allegations was filed on January 7,1974, by John W. Martin and other named plaintiffs [the “Martin class”] against the City of Birmingham, Jefferson County, and the Personnel Board of Jefferson County. On May 27, 1975, the United States brought suit against the Jefferson County Personnel Board and the municipal and other governmental jurisdictions within Jefferson County alleging a pattern or practice of discriminatory employment practices against blacks and women in violation of Title VII, the Omnibus Crime Control and Safe Streets Act of 1968, as amended, 42 U.S.C. § 3766(c), the State and Local Fiscal Assistance Act of 1972, as amended, 31 U.S.C. § 1242, the Fourteenth Amendment and 42 U.S.C. § 1981. On February 20, 1976, Lucy Walker filed suit challenging the employment practices of the Jefferson County nursing home under Title VII and 42 U.S.C. § 1981. All four eases were consolidated for trial.
On December 20-22,1976, trial was held on the merits of the limited issue of whether the two tests used by the Personnel Board to screen and rank applicants for positions as police officers and firefighters [were] discriminatory and violative of the constitutional or statutory rights of blacks. All other issues under the complaints were reserved until a later date.
Ensley Branch, NAACP v. Seibels, 616 F.2d 812, 814-15 (5th Cir.) (footnotes omitted), cert. denied, 449 U.S. 1061, 101 S.Ct. 783, 66 L.Ed.2d 603 (1980).
The police officer and firefighter tests at issue were written examinations consisting of 120 multiple-choice aptitude and knowledge questions. Ensley Branch, NAACP v. Seibels, 13 Empl.Prac.Dec. (CCH) ¶ 11,504, at 6797 & n. 16, 1977 WL 806 (N.D.Ala.1977), aff'd. in part and rev’d in part, 616 F.2d 812 (5th Cir.), cert. denied, 449 U.S. 1061, 101 S.Ct. 783, 66 L.Ed.2d 603 (1980). The score required to pass each test varied with the number of vacancies and other factors. Ensley Branch, 616 F.2d at 816 n. 10. Under procedures still in place today, the Board ranks passing applicants on an eligibility list according to their score. Id. at 816. For promotional positions, an applicant’s score is increased by one point for each year of seniority. See Act of 1945, § 20,1945 AIa.Acts at 394-95; accord In re Birmingham Reverse Discrimination Employment Litig., 37 Fair Empl.Prac.Cas. (BNA) 1, 5, 1985 WL 1415 (N.D.Ala.1985). When a vacancy arises, the Board forwards the top three names from the eligibility list to the City for final selection. See Act of 1945, § 18, 1945 Ala. Acts at 392-94, amended, Amendments of *15541989, § 1, 1989 Ala. Acts at 967-70;2 accord 37 Fair Empl.Prac.Cas. (BNA) at 5 & n. 12. As discussed below, the district court in 1981 approved a pair of consent decrees requiring the City and Board to modify their procedures to take into account race and gender as well.
Ironically, the firefighter and police officer tests challenged in the original trial were themselves adopted, or at least modified, for the specific purpose of hiring more blacks. As the district court explained:
In late 1965, following an independent study as to why no blacks were then employed as police officers in the City of Birmingham, the Personnel Board decided to replace its police and firefighter exams with tests developed by the Public Personnel Association, now known as the International Personnel Management Association. IPMA tests were being widely used in other parts of the country and were considered by the Board as superior to other tests then available. The change was part of a multi-faceted program intended to increase black participation in governmental positions.
Ensley Branch, 13 Empl.Prac.Dec. (CCH) ¶ 11,504, at 6795. On the advice of consultants that some test questions were more predictive than others of blacks’ future job performance, the Board in 1974 began to use a new scoring key that was designed to “increase validity of the [police officer] test for black applicants.”3 Id, The Board also began actively to encourage blacks to apply, to waive examination fees, to experiment with reducing the passing score for the police officer test, and to eliminate priority for applicants residing within the employing agency’s jurisdiction. Id. at 6795-96.
After assessing these efforts to increase black employment, the district court concluded that the Board’s “selection, administration and use” of the two tests had not been motivated by a “design or intent ... to discriminate on the basis of race or color” and therefore did not violate the Equal Protection Clause.4 Id. at 6796. The plaintiffs did not appeal that finding. Ensley Branch, 616 F.2d at 815 n. 5.
The district court also found, however, that the police officer and firefighter tests violated Title VIL The court noted that both tests had a significant adverse impact on black applicants, a phenomenon defined as a passing rate “less than four-fifths ... of the rate for [whites].” Ensley Branch, 13 Empl. Prac.Dec. (CCH) ¶ 11,504, at 6796-97 (internal quotation marks omitted). The court ruled that the tests could be used only if, despite their adverse impact, they were sufficiently “job related” to predict effectively test takers’ future job performance. Id. at 6796 nn. 10-11, 6806. After reviewing testing data, the court concluded that the tests failed to meet this standard. Id. at 6798-6808.
The court found no statistically significant correlation between the applicants’ scores on the firefighter test and their later job performance. Although there was a significant positive correlation between test scores and job performance during the first three years of a firefighter’s service, the court found a significant negative correlation between test scores and job performance after the first three years. Id. at 6803. To the court, these findings “suggested] that over time the lower scoring applicants made the better employees.” Id. Thus, “one is hard pressed to conclude that the higher scoring [firefighter] applicants are in fact the better persons to hire.” Id.
The district court analyzed the police officer test somewhat differently. Operating under the assumption that supervisor bias had not influenced black officers’ perfor-*1555manee ratings, id. at 6802, the district court found a statistically significant correlation between black police officers’ test scores and their later job performance, id. at 6803. Nevertheless, the district court concluded that “the magnitude of the positive prediction is so low that the test is worthless for all practical purposes.” Ensley Branch, 616 F.2d 812, 818 n. 16 (5th Cir.), cert. denied, 449 U.S. 1061, 101 S.Ct. 783, 66 L.Ed.2d 603 (1980). Among its many detailed findings, the district court determined that “use of the test predicts [job performance] with a margin of error that is only 2% smaller than it would be without the test.” Ensley Branch, 13 Empl.Prac.Dec. (CCH) ¶ 11,504, at 6804. The court also found the test could not predict with a reasonable degree of certainty whether any one applicant would actually perform better than any other. Id. at 6805. The district court therefore concluded that the tests were not sufficiently “job-related” to satisfy Title VII, 42 U.S.C. § 2000e-2(h). Id. at 6806-08; see generally Albemarle Paper Co. v. Moody, 422 U.S. 405, 425, 95 S.Ct. 2362, 2375, 45 L.Ed.2d 280 (1975) (“Title VII forbids the use of employment tests that are discriminatory in effect unless the employer meets ‘the burden of showing that any given requirement [has] ... a manifest relationship to the employment in question.’” (quoting Griggs v. Duke Power Co., 401 U.S. 424, 432, 91 S.Ct. 849, 854, 28 L.Ed.2d 158 (1971)).
As a remedy for the Board’s use of illegal tests, the district court ordered race-conscious relief “[p]ending adoption of some selection procedure which either has no adverse effect upon black applicants or is sufficiently job-related.” Ensley Branch, 13 Empl.Prac.Dec. (CCH) ¶ 11,504, at 6808. The district court:
ordered that blacks be referred for openings on the police and firefighter forces at the rate at which they took the tests when most recently administered. To accomplish this, the Court ordered that the names of a sufficient number of blacks be added to the current police and firefighter eligibility lists [which included passing applicants from the most recent test administration] so that the lists shall be representative of the racial composition of the test-takers [at that most recent test administration], i.e., 28 and 14 percent black for police and firefighter ■ lists, respectively; that, one-third of future certifications, i.e., referrals from the [existing eligibility] lists for actual employment, are to be black until, considering all certifications since the relevant 1975 and 1976 dates [when the Title VII violations began], the numbers of certifications become representative of the racial composition of the test-takers [at the most recent test administration]. Thereafter, blacks are to be certified in accordance with their representation on the lists, i.e., 28 and 14 percent of certifications for policemen and firefighters, respectively, will be black. Similarly, referrals from future [eligibility] lists [created by future test administrations] will be a function of the rate at which blacks take the examinations on which the lists are based, until or unless defendants develop valid tests.
Ensley Branch, 616 F.2d at 815 n. 6.
An appeal and cross-appeal ensued. The Board appealed the district court’s decision that the police and firefighter exams violated Title VII. Id. at 815. In doing so, the Board did not contest the district court’s finding that the two tests had an adverse impact, but contended that the tests were in fact job-related. Id. at 816. We upheld the district court’s finding that the Board had faded to validate either exam, and affirmed the district court’s holding that use of the two exams violated Title VII. Id. at 818, 822.
The United States and the Martin class of black plaintiffs jointly cross-appealed the district court’s holding that use of the tests did not begin to violate Title VII until the dates on which the negative results of the test validation studies were reported to the Board. Id. at 815, 823. The district court had reasoned that, until the final results were reported, the Board was justified in using the tests in anticipation of favorable results from the validation studies. Id. at 823. On appeal, we inferred that the district court had relied on an Equal Employment Opportunity Commission guideline that, in “ Very limited circumstances,’ ” authorized a local government to use tests pending the *1556results of a validation study. Id. (quoting Albemarle Paper C.o., 422 U.S. at 436, 95 S.Ct. at 2380). However, because we could not determine from the district court’s findings whether the case presented one of those “very limited circumstances,” we remanded for additional fact finding. Subsequent events obviated the need for those findings, which were therefore never made.
B. THE SECOND TRIAL, CONSENT DECREES, AND APPEAL
While the first appeal was pending, the district court conducted a second trial. That trial involved challenges to other Board practices, including: written tests for eighteen more positions; various rules affecting promotional opportunities; the imposition of height, weight, and educational requirements for certain jobs; and the restriction of some job announcements and certifications to persons of a particular sex. United States v. Jefferson County, 28 Fair Empl.Prac.Cas. (BNA) 1834, 1835, 1981 WL 27018 (N.D.Ala.1981), aff'd, 720 F.2d 1511 (11th Cir.1983). The Board defended on the grounds that these practices either had no adverse impact upon blacks or women, or were sufficiently job-related to be effective predictors of future job performance. Id. As in the first trial, the City did not participate. In fact, the original plaintiffs’ claims against the City never reached trial.
While the first proceeding was on remand and the second was at trial, the parties entered settlement talks that eventually suspended both proceedings. Once again, we resort to our summary of the facts from a prior decision:
After we ruled on the district court’s decision concerning the written [police officer and firefighter] tests, [Ensley Branch, 616 F.2d at 812], the plaintiffs, in all three cases, entered into extensive negotiations with the Board and the City which culminated in two proposed consent decrees, one with the Board and one with the City. The former disposed of all of the plaintiffs’ claims against the Board; the latter disposed of all the plaintiffs’ claims against the City.
United States v. Jefferson County, 720 F.2d 1511, 1514-15 (11th Cir.1983) (footnotes omitted). Thus, before the district court ruled on the remand of the first case or rendered a decision in the second case, the parties submitted proposed consent decrees that settled all claims against the City and the Board, including allegations of gender discrimination raised by the United States. Although these decrees provided retrospective relief such as back pay for some individuals, their keystone was an extensive regime of affirmative action for blacks and women.
At the heart of the Board decree was a requirement, subject to the availability of qualified applicants, that the Board annually certify blacks and women either according to racial and gender quotas set forth in the decree or in proportion to their representation in the applicant pool, whichever was higher. The decree’s minimum certification rates ranged from ten to fifty percent, depending on the position involved and whether the goal applied to blacks or women. The Board agreed to continue to certify according to these annual “goals” until satisfaction of the long-term “goal”; i.e., until the proportion of blacks and women employed by the City in any given job classification “approximate[d] the respective percentages [of blacks and women] in the civilian labor force of Jefferson County.” These provisions did not govern appointment of blacks to entry-level police and firefighter positions, with respect to which the Board decree simply adopted the remedies established by the district court’s 1977 order on that subject. Nor did the decree state that the development of lawful selection procedures would terminate race- and gender-conscious certification requirements, which could potentially have continued forever.5
*1557The Board decree established several other significant obligations. First, the Board committed itself “periodically” to review its hiring and promotion procedures to ensure that the procedures either had no adverse impact or were sufficiently job-related to pass muster under Title VII. Second, so long as the Board’s procedures — whether job related or not — had a disparate impact on blacks or women, the Board agreed to “mak[e] a good faith effort to determine whether there [were] any alternative [testing procedures] ... which [would] reduce any adverse impact.” Third, the decree prohibited the Board’s prior practice of restricting job announcements on the basis of gender. Fourth, the decree mandated continued aggressive recruitment of blacks and women.
In broad outline, the City decree was quite similar to the Board decree. It too established annual “goals” for hiring and promoting blacks and women and a “long term goal” of parity between the proportion of blacks and women in any City job classification and the proportion of blacks and women in the civilian labor force. With a few exceptions,6 the annual goals required the City to hire and promote blacks and women either according to racial and gender quotas set forth in the decree, or at the rate of black and female representation in the applicant pool, whichever was higher. The City also agreed to request the Board “selectively to certify ... qualified blacks and females whenever ... necessary to provide the City with a certification list that contains sufficient numbers of blacks and females to meet the [decree’s] goals.”
As with the Board decree, the City decree’s annual goals were “subject to the availability of qualified ... applicants.” In addition, the parties reserved the right:
to adjust, through agreement and subject to the approval of the Court, any of the goals provided by this Decree where it can be shown that a professional degree, license or certificate is required to perform the duties of any particular job or jobs in the City’s workforce and that blacks and/or women hold such degrees, licenses or certificates in percentage terms which are inconsistent -with the goals provided.
The decree also stated that “[n]othing herein shall be interpreted as requiring the City ... to hire, transfer, or promote a person who is not qualified, or to hire, transfer or promote a less qualified person, in preference to a person who is demonstrably better qualified based upon the results of a job related selection procedure.” Other provisions obligated the City to strengthen its recruitment of blacks and women, prohibited any restriction of jobs by gender, and eliminated time-in-grade requirements for some promotional positions.
Although the consent decrees resolved the issues as between the parties to the original cases, several interested non-parties soon appeared to challenge the decrees, claiming that the decrees would adversely affect their employment opportunities. Chief among the objectors was the Birmingham Firefighters’ Association (“BFA”), a labor association representing a majority of City firefighters, most of whom were white males. We return to our previous narrative for a description of the ensuing conflict:
The [district] court provisionally approved these consent decrees in June 1981, but reserved final approval until it convened a fairness hearing to consider the objections of all interested parties. The court held that hearing in August 1981, at *1558which it considered, among others, the objections filed by the Birmingham Firefighters Association 117 (BFA), as amicus curiae. The day after the hearing, BFA and two of its members (BFA members) moved ... to intervene of right in each of the three cases, contending that the proposed consent decrees would have a substantial adverse impact upon them. The court denied their motions as untimely, and approved, and entered, both consent decrees.
Jefferson County, 720 F.2d at 1515 (footnote omitted).
Before approving the decrees, the district court rejected the merits of the objections raised at the fairness hearing by the would-be intervenors. The district court reasoned that the decrees “[did] not preclude the hiring or promotion of whites or males,” Jefferson County, 28 Fair Empl.Prac.Cas. (BNA) at 1836, and that the City’s hiring goals were “expressly made subject to the caveat that the [City] decree is not to be interpreted as requiring the hiring or promotion of a person who is not qualified or of a person who is demonstrably less qualified according to a job-related selection procedure,” id. at 1837. The court further noted that the “provisions for potentially preferential treatment [were] limited both in time and in effect” because they would expire on their own terms when the work-force parity goals were met and because either decree could “be dissolved after a period of six years” if the purposes of the decree had been substantially achieved. Id.; see also In re Birmingham Reverse Discrimination Employment Litig., 37 Fair Empl.Prac.Cas. (BNA) 1, 3 n. 5, 1985 WL 1415 (N.D.Ala.1985) (describing the circumstances in which the decrees may be dissolved). In addition, the court reviewed the evidence of past discrimination against blacks and women and concluded that “there is more than ample reason for the Personnel Board and the City of Birmingham to be concerned that they would be in time held liable for discrimination” against blacks seeking promotional positions in the police and fire departments and against woman at all levels of hiring and promotion in those departments. Jefferson County, 28 Fair Empl.Prac.Cas. (BNA) at 1838. On appeal, this Court affirmed the district court’s denial of the BFA’s intervention motion. Jefferson County, 720 F.2d at 1516-19.
Shortly after the district court approved the decrees and denied leave to intervene:
Seven individual white male firefighters ... filed a complaint in the district court against the Board and the City to enjoin the enforcement of the consent decrees on the ground that the operation of the decrees would discriminate against them in violation of Title VII of the Civil Rights Act. They applied for a preliminary injunction, which, after a hearing, the district court denied.
Jefferson County, 720 F.2d at 1515 (footnote omitted). In the same opinion in which we affirmed the denial of the BFA’s motion to intervene, we also upheld the district court’s denial of the preliminary injunctive relief sought by the seven individual white male firefighters. Id. at 1520.
C. THE REVERSE DISCRIMINATION LITIGATION
The district court’s approval of the consent decrees, and our refusal to allow the BFA to intervene, brought forth a collection of cases that has come to be known as the “Birmingham Reverse Discrimination Employment Litigation.” In these cases, a number of male, non-black City employees collaterally attacked the decrees and the affirmative action programs adopted under them. See In re Birmingham Reverse Discrimination Employment Litig., 833 F.2d 1492, 1495 (11th Cir.1987), aff'd sub nom. Martin v. Wilks, 490 U.S. 755, 109 S.Ct. 2180, 104 L.Ed.2d 835 (1989). The United States, despite its status as a signatory of the consent decrees, also brought suit against the City, lodging allegations similar to those of the individual plaintiffs. Id., 833 F.2d at 1496; cf. In re Birmingham Reverse Discrimination Employment Litig., 37 Fair Empl.Prac.Cas. (BNA) 1, 8, 1985 WL 1415 (N.D.Ala.1985) (permitting the United States to side with the reverse discrimination plaintiffs on the issue of whether the City was violating the decree). These cases were heard by the same judge who had heard the earlier consent-decree cases.
*1559Prior to trial, the district court rejected the reverse discrimination plaintiffs’ collateral challenge to the legality of the decrees. See In re Birmingham Reverse Discrimination Employment Litig., 37 Fair Empl.Prac.Cas. (BNA) at 3 & n. 6. Instead, the district court restricted the plaintiffs’ action to the questions of whether the City or the Board had violated the decrees or had granted illegal preferences that were not required by the decrees. Id. at 3-4. At the close of the plaintiffs’ ease, the court further limited the action by dismissing for lack of evidence all claims against the Board. See Martin v. Wilks, 490 U.S. 755, 779 n. 16, 109 S.Ct. 2180, 2194 n. 16, 104 L.Ed.2d 835 (1989) (Stevens, J., dissenting). This left the City as the only defendant.
At trial, the plaintiffs had claimed that some blacks were promoted over more-qualified non-blacks despite the fact that the City decree specifically did not require the City to “promote a less qualified person, in preference to a person who is demonstrably better qualified based upon the results of a job related selection procedure.” After trial, the district court found for the City, holding that the City had shown that its employment actions were required by the decrees. Id. at 780-81, 109 S.Ct. at 2194-95. The district court in effect decided that the provision quoted by the plaintiffs applied only if job related selection procedures were in place. In re Birmingham Reverse Discrimination Employment Litig., 833 F.2d at 1497. Although the district court agreed that “[m]ost but not all of those whites who were not selected for [the challenged promotions] had higher test scores” than the blacks who were selected, the court pointed out that the tests on which these scores were based had never been shown to be valid predictors of future job performance. The court further noted that the City “ ‘does not use a job-related selection procedure in evaluating the qualifications of certified candidates [and] has made no effort to develop ... such a procedure.’ ” In re Birmingham Reverse Discrimination Employment Litig., 833 F.2d at 1497 (quoting the district court’s December 26, 1985, order (emphasis and alteration added)). Accordingly, the district court rejected the plaintiffs’ assertion that demonstrably better qualified whites had been passed over.
On appeal, this Court reversed. We observed that “the district judge treated the plaintiffs as if they were bound by the consent decrees,” rendering the plaintiffs unable to challenge the decrees’ validity, and limiting their action to a claim that the City had granted racial preferences beyond those mandated by the City decree. Id. at 1496. This limitation was unfair to the male, non-black plaintiffs, we reasoned, because they had not participated in the negotiation or signing of the consent decrees. Id. at 1498-99. To give the reverse-discrimination plaintiffs their day in court, we ruled that they must be allowed to bring an action challenging the validity of the decrees. Id. at 1499-1500. We therefore directed the district court to re-examine the legality of the decrees under the heightened scrutiny applicable to voluntary government affirmative actions plans. Id. at 1500-01. Finally, we ruled that the United States was estopped from collaterally attacking the decrees by its status as a signatory. Id. at 1501. “[I]f the United States believes that the decrees should be modified based on changed circumstances, its remedy ... is to seek modification in the court which retained jurisdiction over the cases in which the decrees arose.” Id. at 1501.
Our decision' was upheld by the Supreme Court in Martin v. Wilks, 490 U.S. at 769, 109 S.Ct. at 2188. In affirming our reasoning, the Wilks Court implicitly suggested that plaintiffs in future eases could avoid such collateral challenges by insuring that all interested parties were joined from the outset. See id. at 765-67, 109 S.Ct. at 2187.
The district court subsequently held a new trial on the reverse discrimination plaintiffs’ challenge. At the conclusion of that trial, the district court again ruled in favor of the City. Bennett v. Arrington, 806 F.Supp. 926, 931 (N.D.Ala.1992). Applying strict scrutiny, id. at 928, the district court found that the City had “significant evidence” of past discrimination to support its affirmative action program. Id. at 929. The court further found the affirmative action provisions were narrowly tailored because the City had first *1560tried alternative measures, and because these provisions were both flexible and temporary. Id. at 929-30. That ruling was recently reversed by another panel of this Court. See In re Birmingham Reverse Discrimination Employment Litig., 20 F.3d 1525 (11th Cir.1994).
D. THIS DECREE MODIFICATION PROCEEDING
After we suggested that the United States could not collaterally challenge the decrees but could seek modifications, see In re Birmingham Reverse Discrimination Employment Litig., 833 F.2d at 1501, the parties began discussing modification as a possible means of resolving their outstanding differences. With that prospect in mind, the plaintiffs from the reverse-discrimination case moved to intervene in this, the original consent-decree, ease and to consolidate this case with the reverse-discrimination case. On May 25, 1990, the district court denied the reverse-discrimination plaintiffs’ motion to consolidate, but allowed them to intervene in this case “for the limited purpose of participating in any litigation regarding potential modification of the consent decrees.” Subsequently, in an effort to gather all interested parties in a single proceeding, the district court certified both a class of “[a]ll present and future black and female employees ... [and] applicants for employment with the City” (the “Bryant class”), and a class, represented by several of the plaintiffs from the parallel reverse-discrimination case, of “[a]ll present and future male, non-black employees ... [and] applicants for employment with the City of Birmingham” (the “Wilks class”).
On May 3, 1990, the United States moved to modify the consent decrees. The United States urged the district court:
(1) “to replace the existing long-term goals (which [were] ... based on civilian labor force figures) with the long-term goal of developing lawful selection procedures”;
(2) “to replace the current interim goals with interim goals based on applicant flow data” that would terminate upon the implementation of lawful selection procedures;
(3) “to require the Personnel Board to develop nondiscriminatory selection procedures in a timely manner ... ”;
(4) “to require the City of Birmingham to cooperate with the Board in the Board’s efforts to develop nondiscriminatory selection procedures and for the City to demonstrate that any selection procedures it has implemented in addition to those of the Personnel Board, are lawful”; and
(5) “to strengthen the current recruitment mechanisms.”
In an accompanying proposed order, the United States requested the court to give the Board three years to develop lawful tests and to require the Board to stop crediting applicants with seniority points to the extent that use of such points violated Title VII. The United States asserted that “[t]hese modifications are appropriate in light of changed circumstances, emerging case law, and the experience of the parties under the decrees over the past nine years, and to move this matter toward a conclusion where continuing court jurisdiction will no longer be required.”
The Wilks class soon submitted its own modification proposals, which requested the court:
(1) to vacate all long-term and annual goals;
(2) to enjoin the City and Board from making employment decisions based solely on race or gender; and
(3) to terminate both the decrees and all court supervision of City and Board employment practices within four years.
The City, the Bryant class of blacks and women, and the Board filed responses to these modification motions in July 1990. For its part, the City “acknowledge^] that limited modification ... [was] appropriate because of changed circumstances,” including the City’s achievement of some of its long-term goals and the fact that “the selection procedures employed by the Personnel Board continue to have an adverse impact upon blacks and have not been demonstrated to be valid selection procedures.” With these developments in mind, the City proposed the following modifications:
*1561(1) “Where long term goals have been met, but selection devices which create an adverse impact on blacks remain ..., replace the current interim annual goals [based on fixed percentages set out in the City decree] with interim annual goals based on representation in the qualified applicant pool.”
(2) “Modify long term goals which are demonstrated to be inconsistent with the qualified applicant pool to reflect representation of the qualified pool,” rather than representation in the general labor force.
(3) Terminate the Decree, “in whole, or in part by job classification[ ], upon motion of any party, and a finding by the Court that a lawful selection procedure is in place for appointment to that job classification and the long term goal for such classification(s) has been achieved.”
The Bryant class of blacks and women joined in these recommendations and also agreed with the United States that “a reasonable timetable should be established” for the development of lawful selection procedures by the Board.
The Board, too, accepted the need to develop lawful tests, but vehemently opposed the United States’ proposed three-year timetable as both unrealistic and unnecessary. The Board rested its contention that a timetable was unnecessary on its assertion that it had already made significant progress toward eliminating adverse impact from its selection procedures. The Board also opposed the United States’ call for an end to seniority-point enhancements, noting that the federal guidelines on enforcement of Title VII do not disallow the use of seniority points. Cf. 42 U.S.C.A. § 2000e-2(h) (1981 & Supp.1993) (“[I]t shall not be an unlawful employment practice for an employer to apply different standards of compensation, or different terms, conditions, or privileges of employment pursuant to a bona fide seniority or merit system _”).
After holding a hearing on these issues, the district court ordered several modifications to the decrees. The court began by noting that the decrees had:
in conjunction with a city administration whose ... leaders have reflected the majority-black voting population within the city, served to reduce, if not eliminate, discriminatory employment practices against blacks and females and, indeed, to enhance the opportunities of such persons for employment and promotion. Nor can it be denied that, in so doing, the decrees have impaired some employment or promotional opportunities of whites and males
In the police and fire departments, the two departments at the core of the original litigation, black employment had more than doubled, from twenty to forty-one percent in the Police Department and from ten to twenty-six percent in the Fire Department. The percentage of blacks and females in many promotional positions had also increased significantly. Overall, forty-five percent of the City’s full-time employees were black and twenty-three percent were female as of September 1990. Blacks and women held jobs in approximate proportion to their presence in the general labor force for about half of the City’s classified positions.
After reciting these facts, the district court noted that “[a]ll parties agree that some modifications have become appropriate.” Guided by its view of the underlying purposes of the decrees, remedying past and preventing future discrimination, the district court ordered the following modifications to the City decree:
(1) The City must stop using annual goals for any particular job classification once the long-term goal for that classification is met.
(2) The City must stop using annual goals for any promotional position once the long-term goal is met for the position from which the promotional candidates are normally chosen, except that the City should continue to promote blacks and women to high-level police and fire positions in proportion to those groups’ representation in the position from which promotions are normally made until the long-term goal is reached with respect to the high-level positions.
*1562(3) The City must stop using annual goals for any particular job classification once the Board develops lawful screening procedures for that job.
(4) The City should group similar jobs together for the purpose of determining whether a particular goal has been met.
(5) The district court will, in 1996, reconsider the appropriateness of continuing the City decree.
The district court made only one modification to the Board decree. This modification requires that, until the Board develops a lawful test for a particular position, it must, at the City’s request and subject to the availability of qualified applicants, certify black and female candidates for that position in proportion to their representation among applicants — even after the City has met its long-term goal (and thus has stopped following the annual goal) for that position. The district court viewed this modification as necessary to avoid a situation in which the City would be obligated to “appoint or promote only on the basis of certifications made from [the] discriminatory testing devices employed by the Personnel Board.”7
The district court acknowledged that long-term goals tied to black and female representation in the general labor force “do[] not provide an accurate estimate of the pool of persons potentially qualified” for particular City jobs. As a result, the court conceded that these goals “would not pass muster under current legal standards as a valid measure of a discrimination-free job force.” However, noting that the long-term goals were “largely hortatory,” the court said that the consequences of this “potentially inappropriate measure” would be “partly reduced” by other modifications to the City decree. The court therefore declined to rewrite the decrees’ “inherently suspect” long-term goals to reflect the proportion of qualified blacks and women in the relevant labor pool. The court also refused to impose deadlines on the Board for the development of lawful selection procedures that would displace the long-term goals. The court agreed that the “use of such testing procedures would be desirable,” but reasoned that specific development and review requirements “would be unrealistic, unworkable, and unwise” — “particularly if accompanied by a judicially-imposed timetable.” Finally, the district court rejected the United States’ request for an order mandating strengthened recruitment of blacks and women because the parties were already “in general agreement” that recruitment efforts should be increased.
After the district court issued its initial modification order, the Wilks class moved for an interim award of attorneys’ fees for its efforts in both the parallel, reverse-discrimination case and the modification proceeding. The class argued that the court’s modification order meant that the class had, in part, prevailed in both cases. The district court denied the request, but expressly permitted the class to renew its application in the reverse-discrimination case.
Both the United States and the Wilks class now appeal. The United States claims that the district court abused its discretion in rejecting any requirement that the City and Board develop lawful, nondiscriminatory selection procedures to replace the existing numerical goals. The Wilks class takes a bolder position, arguing that there is insufficient evidence of past discrimination to give the City and Board a compelling interest in any affirmative action plan. In addition, both the Wilks class and the United States argue that the decrees’ appointment goals fail the narrowly tailored test, established by City of Richmond v. J.A. Croson Co., 488 U.S. 469, 109 S.Ct. 706, 102 L.Ed.2d 854 (1989), because these goals are tied to general labor force statistics rather than to a more accurate measure of the pool of qualified applicants. Finally, the Wilks class challenges the district court’s denial of fees and its refusal to accept certain deposition testimony in evidence. The City, the Board, and the Bryant class contend on appeal that the district court orders were within the district *1563court’s discretion and should be affirmed in their entirety.
II. STANDARDS OF REVIEW
We review for abuse of discretion a district court’s modification of, or refusal to modify, a consent decree. System Fed’n No. 91 v. Wright, 364 U.S. 642, 648, 81 S.Ct. 368, 371, 5 L.Ed.2d 349 (1961); Jacksonville Branch, NAACP v. Duval County Sch. Bd., 978 F.2d 1574, 1578 (11th Cir.1992). At the very least, a district court abuses its discretion if it refuses to make modifications required by applicable law. See Firefighters Local Union No. 1784 v. Stotts, 467 U.S. 561, 573-83, 104 S.Ct. 2576, 2585-90, 81 L.Ed.2d 483 (1984); cf. Rufo v. Inmates of Suffolk County Jail, — U.S. -, -, 112 S.Ct. 748, 762, 116 L.Ed.2d 867 (1992) (“A consent decree must of course be modified if, as it later turns out, one or more of the obligations placed upon the parties has become impermissible under federal law.”). We also review for abuse of discretion a district court’s exclusion of evidence and denial of attorneys’ fees. U.S. Anchor Mfg., Inc. v. Rule Indus., Inc., 7 F.3d 986, 993 (11th Cir.1993) (eviden-tiary rulings); Church of Scientology Flag Serv., Org. v. City of Clearwater, 2 F.3d 1509, 1513 (11th Cir.1993) (attorneys’ fees).
III. THE CONSENT DECREE MODIFICATION ISSUES
A. CONSENT DECREE MODIFICATION LAW
The Supreme Court has articulated a two-pronged approach to determining when, and to what extent, an institutional-reform consent decree that “arguably relates to the vindication of a constitutional right” should be modified. Rufo v. Inmates of Suffolk County Jail, — U.S. -, - n. 7, 112 S.Ct. 748, 760 n. 7, 116 L.Ed.2d 867 (1992). The first prong requires the party seeking modification to “establish that a significant change in facts or law warrants revision of the decree.” Id. at-, 112 S.Ct. at 765. If the moving party satisfies this requirement, then the second prong requires the court to make modifications that are “suitably tailored” to address the new factual or legal environment. Id. We now elaborate on this dual inquiry.
1. Rufo’s First Prong: Prerequisites for Modification
Rufo normally permits modification of a consent decree only to accommodate new factual or legal circumstances. The sorts of factual changes that may qualify include unanticipated developments that render continuation of the decree “inequitable,” Jacksonville Branch, NAACP v. Duval County Sch. Bd., 978 F.2d 1574, 1582 (11th Cir.1992), or that, “for reasons unrelated to past discrimination or to the fault of the parties,” make it extremely difficult or impossible to satisfy obligations that, while imposed by the decree, are not part of its fundamental purpose, United States v. City of Miami, 2 F.3d 1497, 1509 (11th Cir.1993). However, a district court should not modify “long-standing goals in consent decrees merely because the goals have not been achieved.” Id. at 1509.
Rufo similarly provides for flexibility in the face of changing legal standards, but does not mandate modifications in response to every legal development. For example, a court need not necessarily “rewrite a consent decree so that it conforms to the constitutional floor” just because that floor drops after entry of the decree. Rufo, — U.S. at -, 112 S.Ct. at 764. On the other hand, a rising constitutional floor — or, as in this case, a falling constitutional ceiling — may make modifications necessary. Above all, “[a] consent decree must ... be modified if ... one or more of the obligations placed upon the parties has become impermissible under federal law,” id. at -, 112 S.Ct. at 762, and that is the aspect of Rufo with which we grapple in the present ease.
2. Rufo’s Second Prong: Suitably Tailored Modifications
Once a court has determined that some modification is warranted because of a significant change in law or fact, the second prong of the Rufo analysis comes into play. This prong requires the court to determine the appropriate scope of the changes, accepting *1564only proposals that are “suitably tailored” to address significant factual developments or conflicts between new legal standards and the requirements of the decree. Rufo, — U.S. at -, 112 S.Ct. at 765. This determination requires a flexible “exercise of that court’s equitable power,” City of Miami, 2 F.3d at 1509, but the district court’s discretion is not unlimited. The court may not modify a decree in a way that would “violate the basic purpose of the decree,” and must under no circumstances “create or perpetuate a constitutional violation.” Rufo, — U.S. at - - -, 112 S.Ct. at 762-63.
We now turn to the question of whether the district court properly exercised its equitable discretion when it rejected some of the appellants’ proposed modifications. This inquiry will require us to decide whether the court modified the consent decrees’ race- and gender-based remedies sufficiently to make them permissible under current constitutional standards. Because racial and gender classifications attract different levels of scrutiny under the Equal Protection Clause, we analyze separately the decrees’ race- and gender-conscious provisions.
B. MODIFICATION OF THE RACE-CONSCIOUS AFFIRMATIVE ACTION' PROVISIONS IN THIS CASE
1. Rufo’s First Prong: Prerequisites for Modification
The district court approved the City and Board decrees in 1981, thirteen years ago. The Supreme Court had, at that time, just begun to address the constitutionality of affirmative action. See Fullilove v. Klutznick, 448 U.S. 448, 100 S.Ct. 2758, 65 L.Ed.2d 902 (1980); Regents of Univ. of Cal. v. Bakke, 438 U.S. 265, 98 S.Ct. 2733, 57 L.Ed.2d 750 (1978); Califano v. Webster, 430 U.S. 313, 97 S.Ct. 1192, 51 L.Ed.2d 360 (1977). Since then, the Court has repeatedly revisited this issue, substantially changing affirmative action jurisprudence. Most significantly, City of Richmond v. J.A. Croson Co., 488 U.S. 469, 498-508, 109 S.Ct. 706, 724-30, 102 L.Ed.2d 854 (1989), established that voluntary, race-conscious, local-government affirmative action programs are subject to strict scrutiny. Prior to Croson, “a majority of the Supreme Court had never joined in one opinion on the constitutionality” of such programs. Peightal v. Metropolitan Dade County, 940 F.2d 1394, 1398-99 (11th Cir.1991) (footnote omitted), cert. denied, — U.S. -, 112 S.Ct. 969, 117 L.Ed.2d 134 (1992). Croson sufficiently altered the legal landscape to warrant modifications to the present decrees under Rufo. As we discuss later in this opinion, Croson has rendered parts of the decrees unconstitutional.
2. Rufo’s Second Prong: Suitably Tailored Modifications
Rufo’s second prong requires that consent decrees be modified to avoid any violations of governing constitutional standards. The relevant constitutional standard in this case is Croson’s strict scrutiny test. While it is true that Croson applies only to voluntary affirmative action programs, see Croson, 488 U.S. at 491-93, 109 S.Ct. at 720-21, we have previously held that, because of their peculiar procedural history, the present decrees should be treated as “a voluntary affirmative action plan for purposes of equal protection analysis.” In re Birmingham Reverse Discrimination Employment Litig., 833 F.2d 1492, 1501 n. 23 (11th Cir.1987), aff'd sub nom., Martin v. Wilks, 490 U.S. 755, 109 S.Ct. 2180, 104 L.Ed.2d 835 (1989).
Under strict scrutiny, an affirmative action plan must be based upon a “compelling governmental interest” and must be “narrowly tailored” to achieve that interest. S.J. Groves & Sons Co. v. Fulton County, 920 F.2d 752, 767 (11th Cir.), cert. denied, 500 U.S. 959, 111 S.Ct. 2274, 114 L.Ed.2d 725, and cert. denied, 501 U.S. 1252, 111 S.Ct. 2893, 115 L.Ed.2d 1057 (1991); see also Croson, 488 U.S. at 498-508, 109 S.Ct. at 724-30. We address separately those two requirements as they apply to this decree.
a. Croson’s Compelling Government Interest Requirement
Strict scrutiny’s compelling government interest requirement was designed “to ‘smoke out’ illegitimate uses of race by assuring that the legislative body is pursuing a goal important enough to warrant use of a highly sus*1565pect tool.” Croson, 488 U.S. at 493, 109 S.Ct. at 721 (plurality opinion of O’Connor, J.). In practice, the interest that is alleged in support of racial preferences is almost always the same — remedying past or present discrimination. United States v. City of San Francisco, 696 F.Supp. 1287, 1301 (N.D.Cal.1988), aff'd in part and modified in part on other grounds sub nom. Davis v. City of San Francisco, 890 F.2d 1438 (9th Cir.1989), cert. denied, 498 U.S. 897, 111 S.Ct. 248, 112 L.Ed.2d 206 (1990). That interest is widely accepted as compelling. See, e.g., Wygant v. Jackson Bd. of Educ., 476 U.S. 267, 286, 106 S.Ct. 1842, 1853, 90 L.Ed.2d 260 (1986) (O’Connor, J., concurring); Cone Corp. v. Hillsborough County, 908 F.2d 908, 916 (11th Cir.), cert. denied, 498 U.S. 983, 111 S.Ct. 516, 112 L.Ed.2d 528 (1990); Howard v. McLucas, 871 F.2d 1000, 1006-08 (11th Cir.), cert. denied, 493 U.S. 1002, 110 S.Ct. 560, 107 L.Ed.2d 555 (1989). As a result, the true test of an affirmative action program is usually not the nature of the government’s interest, but rather “the adequacy of the evidence of discrimination” offered to show that interest. City of San Francisco, 696 F.Supp. at 1301. Without an adequate showing of discrimination, the government’s assertion that affirmative action is necessary lacks credibility. See Croson, 488 U.S. at 505, 109 S.Ct. at 728.
Therefore, when a consent decree providing race-conscious relief is challenged as unconstitutional, the district court must make a factual determination that the public employer has “ ‘a strong basis in evidence for its conclusion that’ ” racial discrimination necessitates affirmative action. Howard, 871 F.2d at 1007 (quoting Wygant, 476 U.S. at 277, 106 S.Ct. at 1849). Certain aspects of this inquiry are well established. A local-government employer cannot rest on an “amorphous claim” of societal discrimination, Croson, 488 U.S. at 499, 109 S.Ct. at 724, on “simple legislative assurances of good intention,” id. at 500, 109 S.Ct. at 725, or on congressional findings of discrimination in the national economy, id. at 504, 109 S.Ct. at 727. Public employers may, however, justify affirmative action by demonstrating “gross statistical disparities” between the proportion of minorities hired by the public employer and the proportion of minorities willing and able to do the work. Id. at 501, 109 S.Ct. at 725 (internal quotation marks omitted); see also Cone Corp., 908 F.2d at 916 (finding a prima facie case of discrimination sufficient to justify race-conscious relief where minorities owned 12% of the contracting businesses but received only 1.2% of the local government’s contracting dollars); Howard, 871 F.2d at 1007 (upholding a finding of discrimination based on statistical evidence, including the fact that black employees spent an average of three times longer than white employees in low-grade wage jobs). Anecdotal evidence may also be used to document discrimination, especially if buttressed by relevant statistical evidence. Cone Corp., 908 F.2d at 916.
Although Croson requires that a public employer show strong evidence of discrimination when defending an affirmative action plan, the Supreme Court has never required that, before implementing affirmative action, the employer must have already proved that it has discriminated. On the contrary, formal findings of discrimination need neither precede nor accompany the adoption of affirmative action. Wygant, 476 U.S. at 286, 106 S.Ct. at 1853 (O’Connor, J., concurring) (rejecting any formal findings requirement); id. at 305, 106 S.Ct. at 1863 (Marshall, J., dissenting, joined by Brennan and Blackmun, JJ.) (stating that “[t]he Court is correct to recognize, as it does at least implicitly today, that formal findings of past discrimination are not a necessary predicate to the adoption of affirmative-action policies”); id. at 313, 106 S.Ct. at 1867 (Stevens, J., dissenting) (arguing that a showing of past discrimination is not necessary to finding a compelling interest in racial classifications with purely prospective effect); Howard, 871 F.2d at 1007 (specifically rejecting the intervenor white employees’ argument “that a showing of past discrimination must precede the implementation of the promotional relief and that this showing may be made only through the employer’s own admittance of such discrimination or through a judicial finding of past discrimination”); cf. Contractors Ass’n v. City of Philadelphia, 6 F.3d 990, 1004 (3d Cir.1993) (noting that federal courts have *1566admitted evidence that supports affirmative action, even when that evidence was developed after the affirmative action plan); Harrison & Burrowes Bridge Constructors, Inc. v. Cuomo, 981 F.2d 50, 60 (2d Cir.1992) (“The law is plain that the constitutional sufficiency of a state’s proffered reasons necessitating an affirmative action plan should be assessed on whatever evidence is presented, whether prior to or subsequent to the program’s enactment.”). This is because, as Justice O’Connor has explained
A violation of federal statutory or constitutional requirements does not arise with the making of a finding; it arises when the wrong is committed. Contemporaneous findings serve solely as a means by which it can be made absolutely certain that the governmental actor truly is attempting to remedy its own unlawful conduct when it adopts an affirmative action plan .... Such findings, when voluntarily made by a public employer, obviously are desirable in that they provide evidentiary safeguards .... If contemporaneous findings were required of public employers in every case as a precondition to the constitutional validity of their affirmative action efforts, however, the relative value of these eviden-tiary advantages would diminish, for they could be secured only by the sacrifice of other vitally important values.
The imposition of a requirement that public employers make findings that they have engaged in illegal discrimination before they engage in affirmative action programs would severely undermine public employers’ incentive to meet voluntarily their civil rights obligations....
... [P]ublic employers are trapped between the competing hazards of liability to minorities if affirmative action is not taken to remedy apparent employment discrimination and liability to nonminorities if affirmative action is taken. Where these employers, who are presumably fully aware both of their duty under federal law to respect the rights of all their employees and of their potential liability for failing to do so, act on the basis of information which gives them a sufficient basis for concluding that remedial action is necessary, a contemporaneous findings requirement should not be necessary.
Wygant, 476 U.S. at 289-91, 106 S.Ct. at 1855-56 (O’Connor, J., concurring). For these and related reasons, the Supreme Court has required a public employer defending an affirmative action plan to show only that it has “a ‘strong basis in evidence for its conclusion that remedial action was necessary.’” Croson, 488 U.S. at 500, 109 S.Ct. at 725 (quoting Wygant, 476 U.S. at 277, 106 S.Ct. at 1849 (plurality opinion)).
At the time the City and the Board accepted the present consent decrees, they already had a “strong basis in evidence” for concluding that race-based relief was needed to correct discrimination in the police and fire departments. When it approved the consent decrees, the district court noted that the City and the Board had good reason to believe that they had discriminated in those two departments. United States v. Jefferson County, 28 Fair Empl.Prac.Cas. (BNA) 1834, 1838, 1981 WL 27018 (N.D.Ala.1981), aff'd, 720 F.2d 1511 (11th Cir.1983). The district court evaluated an extensive record that supported this conclusion. Most importantly, the district court stated:
This court at the first trial found — and the Fifth Circuit agreed — that blacks applying for jobs as police officers and firefighters were discriminated against by the tests used by the Personnel Board to screen and rank applicants. The evidence presented at the second trial established, at the .01 level of statistical significance, that blacks were adversely affected by the exam used by the Personnel Board to screen and rank applicants for the position of police sergeant. Since governmental employers such as the City of Birmingham have been limited by state law to selecting candidates from among those certified by the Board, one would hardly be surprised to find that the process as a whole has had an adverse effect upon blacks seeking employment as Birmingham police officers, police sergeants, or firefighters — regardless of whether or not there was any actual bias on the part of selecting officials of the City. A natural consequence of discrimination against blacks at entry-level positions in *1567the police and fire departments would be to limit their opportunities for promotion to higher levels in the departments.
Id. at 1837-38. The district court concluded that:
While the only judicial finding of discrimination thus far entered has been with respect to the effect upon black applicants of the Personnel Board’s tests for police officer and firefighter, it can hardly be doubted that there is more than ample reason for the Personnel Board and the City of Birmingham to be concerned that they would be in time held liable for discrimination against blacks at higher level positions in the police and fire departments and for discrimination against women at all levels in those departments. The proposed consent decrees, by way of settlement for such potential liability, provide appropriate corrective measures reasonably commensurate with the nature and extent of the indicated discrimination.
Id. at 1838 (emphasis added). As the district court’s analysis demonstrates, the City and the Board had strong reason to believe that employment discrimination in the police and fire departments justified race-based relief. The Board’s discrimination against blacks seeking entry-level police and firefighter jobs made it almost inevitable that the effects of discrimination had worked their way up to taint City and Board promotional positions, too. This fact gave the City and the Board an adequate basis for implementing affirmative action in those two departments, which are at the core of this litigation. Further findings with respect to those departments are unnecessary.
However, the parties apparently have not yet fully litigated, nor has the district court decided, whether there is sufficient evidence of past or present discrimination to justify continued use of race-conscious remedies in the other departments covered by these decrees.8 In their briefs, some of the parties attempt to demonstrate either the existence of, or lack of, discrimination in city and county employment. The district court declined to consider these issues as part of the modification proceeding. Instead, the court ruled that a showing of discrimination was relevant only to the original validity of the decrees, and that the decrees’ original validity could not be challenged in this modification proceeding. The district court apparently considered a showing of discrimination irrelevant to the present proceeding.
That ruling was an abuse of the district court’s discretion. As we have already discussed, Rufo requires that these decrees comply with Croson, and Croson requires that the City and the Board show a basis for concluding that public employment discrimination against blacks necessitates affirmative action. Croson, 488 U.S. at 500, 109 S.Ct. at 725. A showing of discrimination is relevant to the decree’s present validity, which is very much at issue here. We must therefore remand the case to the district court for findings on whether the public employers here have a strong basis in evidence for their conclusion that past or present discrimination in departments other than the police and fire departments warrants race-based relief.9
The City and Board may defend their programs by showing enough evidence *1568of discrimination to create a strong basis for the conclusion that past or present discrimination warrants race-based remedies in departments in addition to the police and fire departments. It is not necessary (but would of course be sufficient) for the City and Board to show that, when they approved the decrees, they already had strong evidence of such discrimination. This case concerns only the prospective validity of the decrees, and prospective validity can be established just as well with new evidence as with old. If the City and Board can now show strong evidence of the need for affirmative action in a department, then future affirmative action in that department is justified. Cf. Contractors Ass’n v. City of Philadelphia, 6 F.3d 990, 1004 (3d Cir.1993) (holding that consideration of evidence developed after adoption of an affirmative action plan is “especially appropriate” where the relief sought is “prospective only”); Concrete Works, Inc. v. City of Denver, 823 F.Supp. 821, 837 (D.Colo.1993) (“[I]t would make little sense to strike down the [affirmative action plan] solely because the evidence of discrimination before the City Council was insufficient without the post-enactment evidence only to watch the City Council reconvene immediately, incorporate the new evidence into a new ordinance, and arrive at a constitutionally adequate factual predicate”).
On remand, the district court should give the City and the Board a chance to make the requisite showing. Without intending to foreclose the issue, we note that in the parallel but narrower reverse-discrimination proceeding, the district court upheld race-based relief in the engineering department, although it never discussed the evidence on which it based its decision as to that department. Bennett v. Arrington, 806 F.Supp. 926, 929 (N.D.Ala.1992).10 As recently as 1986, when discussing an engineering department promotion, the district court made the following observation about continuing racial prejudice:
[T]he chief engineer in his deposition testimony indicated candidly that he considered the race of Mr. Thomas, [the] person ultimately chosen, being black, as a negative feature. And that he would have so considered that as a negative feature, but for the fact that the consent decree required him to look otherwise at the candidate.
These indications suggest that the compelling interest prong will likely be satisfied as to at least some of the departments besides the police and fire departments. If, however, the City and Board fail to present strong evidence justifying race-based relief in a department, the district court must forthwith terminate the race-based affirmative action provisions as to that department.
Because we have held that Croson’s first requirement is satisfied with respect to the police and fire departments, and may on remand be satisfied with respect to the other departments, we proceed to discuss Croson’s second requirement. The next section assumes, without deciding, that race-based affirmative action in the other departments is allowable because there has been an adequate showing of evidence of racial discrimination by the City and the Board.
b. Croson’s “Narrow Tailoring” Requirement
Croson’s second requirement is that the affirmative action provided be narrowly tailored to the discrimination to be remedied. This requirement, like the “compelling interest” requirement, applies to the present case through the interaction of Rufo and Croson. Rufo commands district courts to modify consent decrees to avoid “perpetuating] a constitutional violation.” Rufo v. Inmates of Suffolk County Jail, — U.S. -, -, 112 S.Ct. 748, 763, 116 L.Ed.2d 867 (1992). For its part, Croson establishes the controlling constitutional standard that cannot be violated. Taken together, these decisions mandate that the present decrees’ affirmative action *1569provisions be “narrowly tailored” to serve the compelling government interest of ending racial discrimination. City of Richmond v. J.A. Croson Co., 488 U.S. 469, 507, 109 S.Ct. 706, 728 (1989). The district court failed to make the modifications necessary to tailor the decrees narrowly to that interest.
A local government wishing to use racial preferences must strike a difficult balance between an admirable ambition to overcome this nation’s “sorry history of ... private and public discrimination,” Croson, 488 U.S. at 499, 109 S.Ct. at 724, and the sometimes contrary goal of making race irrelevant to public decisionmaking. “These related constitutional duties are not always harmonious; reconciling them requires public employers to act with extraordinary care.” Wygant v. Jackson Bd. of Educ., 476 U.S. 267, 277, 106 S.Ct. 1842, 1848, 90 L.Ed.2d 260 (1986) (plurality opinion).
Carefully tailored affirmative action programs can be a legitimate means of reconciling these aims, and “ ‘innocent persons may be called upon to bear some of the burden of the remedy1 ” for past discrimination. Metro Broadcasting, Inc. v. Federal Communications Comm’n, 497 U.S. 547, 596, 110 S.Ct. 2997, 3025-26, 111 L.Ed.2d 445 (1990) (quoting Wygant, 476 U.S. at 281, 106 S.Ct. at 1850 (opinion of Powell, J.)); accord Peightal v. Metropolitan Dade County, 940 F.2d 1394, 1410 (11th Cir.1991) (opinion of Brown, J.), cert. denied, — U.S. -, 112 S.Ct. 969, 117 L.Ed.2d 134 (1992). Croson itself noted that local governments may in some circumstances use affirmative action to eradicate the effects of public discrimination. Croson, 488 U.S. at 491-93, 109 S.Ct. at 720-21; accord Cone Corp. v. Hillsborough County, 908 F.2d 908, 916-17 (11th Cir.), cert. denied, 498 U.S. 983, 111 S.Ct. 516, 112 L.Ed.2d 528 (1990). To ensure that affirmative action programs do not go too far, however, they must be scrutinized strictly. In making this evaluation, we consider: (1) “the ‘necessity for the relief and the efficacy of alternative remedies’ ”; (2) “the ‘flexibility and duration of the relief, including the availability of waiver provisions’ ”; (3) “the ‘relationship of numerical goals to the relevant labor market’ ”; and (4) “the ‘impact of the relief on the rights of [innocent third parties].’ ” Howard v. McLucas, 871 F.2d 1000, 1008 (11th Cir.) (quoting United States v. Paradise, 480 U.S. 149, 171, 107 S.Ct. 1053, 1066, 94 L.Ed.2d 203 (1987) (plurality opinion)), cert. denied, 493 U.S. 1002, 110 S.Ct. 560, 107 L.Ed.2d 555 (1989). Special vigilance is required against unyielding racial quotas that “rest[ ] upon the completely unrealistic assumption that minorities will choose a particular trade in lockstep proportion to their representation in the local population.” Croson, 488 U.S. at 507, 109 S.Ct. at 729 (internal quote marks omitted).
Since Croson, this Court has twice rejected an equal protection challenge to government-sponsored racial preferences. In Howard v. McLucas, 871 F.2d at 1006, we applied strict scrutiny to a consent decree provision that reserved a certain number of promotions for blacks. The number of promotions reserved matched the number of promotions that had been lost by blacks due to past discrimination. Id. at 1003. The “set aside” was thus narrowly tailored to correct the precisely identified effects of past discrimination.
In Cone Corp., we upheld a minority business enterprise plan that had been carefully crafted to minimize the burden on innocent third parties. 908 F.2d at 910. Under this program, persons who bid for' certain county contracts had to make a good-faith effort to subcontract a stated percentage of the job to minority businesses. Id. at 911. Although the program included a goal of twenty-five percent minority participation, the county would grant a waiver if qualified minority businesses were uninterested, unavailable, or significantly more expensive than non-minority businesses. Id. at 910-11. In the first year of the program’s operation, the county had, after investigation, granted good-faith waivers to each of the bidders who had failed to reach the twenty-five percent target for minority participation. Id. at 911. Despite the plan’s flexibility, the district court entered summary judgment against the county. This Court reversed, holding that the plan was sufficiently likely to pass constitutional muster to warrant a trial. Id. at 917.
The affirmative action provisions at issue in the present case lack both the ex*1570treme specificity of the Howard plan and the generous flexibility of the Cone Corp. plan. They are not narrowly tailored. Thus, the district court must re-write the decrees to make them narrowly tailored to the compelling interest they are intended to serve.
The decrees contain two sets of affirmative action provisions: “long-term goals” and “annual goals.” The long-term goals are intended to reflect the basic purpose of the decree; they are the final destination. As the long-term goals are reached, affirmative action ends. By contrast, the annual appointment goals are the means of getting to the long-term goals; they guide year-to-year personnel decisions. We will discuss the flaws in the long-term goals first, and then turn to the short-term goals.
i. Long-Term Goals
As written, the long-term racial goals are fundamentally flawed. The flaw is that they are designed to create parity between the racial composition of the labor pool and the race of the employees in each job position. The Constitution does not guarantee racial parity in public employment; instead, it forbids racial discrimination. A public employment consent decree’s race-conscious provisions are valid only to the extent that they promote the compelling government interest, anchored in the Constitution, of ending discrimination. We stressed in United States v. City of Miami, 2 F.3d 1497, 1506 (11th Cir.1993), that the intent of consent decrees like those in this case cannot be to maintain employment quotas. Instead, the proper goals of such a decree are to end discrimination and eliminate the effects of past discrimination. Id.; see also Brunet v. City of Columbus, 1 F.3d 390, 412 (6th Cir.1993) (“ ‘Title VII does not require employers to equalize the probabilities of hiring of the average members of two groups. Rather, it requires that actual individuals enjoy opportunities for employment free from discriminatory barriers.’” (quoting Brunet v. City of Columbus, 642 F.Supp. 1214, 1228 (S.D.Ohio 1986)).
By striving for racial parity rather than an end to racial discrimination, these decrees actually promote racial discrimination in contravention of the Constitution. Some might argue that an end to discrimination requires parity between the racial composition of the labor pool and the racial composition in each job position. The Supreme Court, however, has rejected that contention, because it “rests upon the completely unrealistic assumption that minorities will choose a particular profession in lockstep proportion to their representation in the local workforce.” Croson, 488 U.S. at 507, 109 S.Ct. at 729 (internal quotation marks omitted).
Conceding that the decrees’ long-term racial parity goals violate Croson, the district court stated: “There can be little doubt that the civilian labor force data would not pass muster under current legal standards as a valid measure of a discrimination-free job force for all city jobs ....” Nevertheless, the district court believed that this admittedly “inappropriate measure” did not need to be altered because other modifications to the decrees would “partly reduce[]” any “adverse consequences” arising from use of labor force data, and because the long-term goals “have proved in practice to be largely hortatory.” Courts should not be satisfied with partly reducing the effects of unconstitutional aspects of their decrees. Instead, they must modify decrees to prevent them from operating unconstitutionally in whole or in part.
Moreover, the long-term goals play a significant role in the operation of this decree. These goals may not determine the annual level of appointments, but they serve more than a hortative function. As the district court explained, “[t]heir primary effect has been to set a[n] expiration date for the annual goals.” This role is significant because the Constitution demands that race-conscious affirmative action programs end as soon as their purposes are accomplished. Until the long-term goals are met, these goals maintain race-conscious selection procedures. Thus, it is important to ensure that the long-term goals “pass muster under current legal standards as a valid measure of a discrimination-free job force.”
On remand, the district court must rewrite the decrees to reflect that their true long-term purpose is to remedy past and *1571present discrimination, not to achieve workforce parity. The goal of eliminating discrimination may justify some interim use of affirmative action, but affirmative action selection provisions are themselves a form of discrimination that cannot continue forever. An end to racial discrimination demands the development of valid, non-discriminatory selection procedures to replace race-conscious selection procedures. We hesitate to label this essential object “long-term,” because it should be pursued with a sense of urgency.
While “strict scrutiny does not require exhaustion of every possible ... alternative,” it does require “serious, good faith consideration of race-neutral alternatives,” either pri- or to or in conjunction with implementation of an affirmative action plan. Coral Constr. Co. v. King County, 941 F.2d 910, 923 (9th Cir.1991), cert. denied, — U.S. -, 112 S.Ct. 875, 116 L.Ed.2d 780 (1992); see also Cone Corp. v. Hillsborough County, 908 F.2d 908, 917 (11th Cir.) (upholding a minority set-aside program that implemented race-neutral alternatives in conjunction with, rather than prior to, racial preferences), cert. denied, 498 U.S. 983, 111 S.Ct. 516, 112 L.Ed.2d 528 (1990). “[R]ace-neutral means are to be favored.” Peightal v. Metropolitan Dade County, 26 F.3d 1545, 1557 (11th Cir.1994). Unfortunately, race-neutral alternatives have not been pursued diligently enough in this case.
True, the City and the Board have engaged in several race-neutral efforts to cure past and present discrimination. In the 1960s, the Board actively encouraged blacks to apply for jobs, and either waived or eliminated certain application fees. The consent decrees themselves required strengthened recruitment of blacks and women, eliminated certain time-in-grade and size requirements that may have hindered the promotion of blacks or women, and mandated education of supervisors in their responsibility to prevent discrimination against blacks and women. No party has alleged on appeal that these obligations have not been met.
However, the single most important race-neutral alternative contained in the decrees was the requirement that the Board develop and put in place non-discriminatory selection procedures — a requirement that the Board has not satisfied. The Board was quite properly ordered to implement selection procedures that either had no disparate impact on blacks and women or that, despite having disparate impact, were “job related” as that term is used in Title VII. Moreover, if the Board chose the second approach, adopting procedures that were job-related despite having some disparate impact, then the Board was required to search for selection procedures that were equally job-related but with less adverse impact. These decree provisions roughly parallel the requirements of Title VII, which mandates that an employer use either a selection procedure with no adverse impact or a job-related selection procedure that has no more adverse impact than other, equally job-related selection procedures. See Albemarle Paper Co. v. Moody, 422 U.S. 405, 425, 95 S.Ct. 2362, 2375, 45 L.Ed.2d 280 (1975). Although the decree ordered the Board to comply with Title VII by developing valid tests, it provided no deadlines or formal review mechanism to ensure that the Board actually did so. That omission turned out to be a serious flaw.
The development of valid selection procedures, in conjunction with the other race-neutral measures, would in time have ended race-conscious hiring. By minimizing and ultimately ending the need for racial preferences, implementation of race-neutral selection procedures would have gone far toward making sure that these decrees satisfied constitutional requirements. But little or no progress in this direction has been made. In 1991, the Board administered thirty-five different tests, none of which had been validated. Thirteen years after the consent decrees took effect, the Board is still unable or unwilling to demonstrate the legality of a single exam.11 For its part, the City has never *1572tried to validate the selection procedures it uses to choose from among qualified candidates; nor does the City decree presently require that it do so. Thirteen years of experience teach that the decrees as written are simply too weak to make the City and the Board develop non-discriminatory selection procedures. The district court should remedy this defect. The provisions requiring valid selection procedures must be given teeth and extended to cover the City, too.
Under its present decree, the Board may indefinitely administer racially discriminatory tests and then attempt to cure the resulting injury to blacks with race-conscious affirmative action. Federal courts should not tolerate such institutionalized discrimination. See Billish v. City of Chicago, 989 F.2d 890, 894 (7th Cir.1993) (en banc) (“[A] public employer cannot be allowed to justify reverse discrimination by the bootstrap method of an alternating sequence of racial promotions (or hires). That is, the city cannot get points for first using a presumptively biased eligibility list to make a string of white promotions and then turning around and trying to do some rough racial justice by promoting two blacks from the bottom of the list.”). Use of racial hiring quotas to mask the effects of discriminatory selection procedures places grievous burdens on blacks as well as whites. Whatever they measure, tests that are not job-related do not predict future job performance, yet they may nevertheless convince some persons that those who score lower are less qualified. As Justice Brennan once explained, “even in the pursuit of remedial objectives, an explicit policy of assignment by race may serve to stimulate our society’s latent race consciousness, suggesting the utility and propriety of basing decisions on a factor that ideally bears no relationship to an individual’s worth or needs.” United Jewish Orgs. v. Carey, 430 U.S. 144, 173, 97 S.Ct. 996, 1014, 51 L.Ed.2d 229 (1977) (Brennan, J., concurring in part). Blacks who do not make top marks on the flawed exams, but who nevertheless are appointed through affirmative action, may discover that their colleagues mistakenly consider them less able. Croson, 488 U.S. at 493, 109 S.Ct. at 722 (plurality opinion) (“Classifications based on race carry a danger of stigmatic harm. Unless they are strictly reserved for remedial settings, they may in fact promote notions of racial inferiority and lead to a politics of racial hostility.”); Hayes v. North State Law Enforcement Ass’n, 10 F.3d 207, 212 (4th Cir.1993) (“ “While the inequities and indignities visited by past discrimination are undeniable, the use of race as a reparational device risks perpetuating the very race-consciousness such a remedy purports to overcome.’ ” (quoting Maryland Troopers Ass’n v. Evans, 993 F.2d 1072, 1076 (4th Cir.1993))). For these reasons, it is not surprising that the class of black employees argued in the district court that a reasonable timetable for adoption of valid tests should be imposed. The failure of the consent decrees to force the City and the Board to develop race-neutral selection procedures that are fair to blacks and whites has caused both to suffer the effects of discrimination.
By permitting the continued use of discriminatory tests, the decrees compound the very evil they were designed to eliminate. The Constitution will not allow such a discriminatory construct. One color of discrimination has been painted over another in an effort to mask the peeling remnants of prejudice past, leaving a new and equally offensive *1573discoloration rather than a clean canvas. The time has long passed for the Board and the City to strip away the past and adopt fresh, race-neutral selection procedures. And court-approved racial preferences must end as soon as possible.
The district court declined to set deadlines for the development of valid selection procedures. The court agreed that “use of such testing procedures would be desirable,” but nevertheless summarily decided “that specific requirements for development and review [of lawful tests], particularly if accompanied by a judicially-imposed timetable, would be unrealistic, unworkable, and unwise.” That decision was an abuse of discretion.
While it may be difficult to develop valid selection procedures, that task is far from impossible. Other public employment cases prove that it can be done. See, e.g., Hamer v. City of Atlanta, 872 F.2d 1521, 1532 (11th Cir.1989) (upholding the district court’s finding that a written test used to determine promotions from firefighter to fire lieutenant was properly validated); Brunet v. City of Columbus, 1 F.3d 390, 411 (6th Cir.1993) (upholding use of professionally-developed firefighter exam); Bridgeport Guardians, Inc. v. City of Bridgeport, 933 F.2d 1140, 1148 (2d Cir.) (affirming the use of a job-related exam in conjunction with “banding,” a technique designed to reduce the test’s disparate impact), cert. denied, — U.S. -, 112 S.Ct. 337, 116 L.Ed.2d 277 (1991); Police Officers for Equal Rights v. City of Columbus, 916 F.2d 1092, 1101-02 (6th Cir.1990) (affirming a district court’s finding that the challenged portion of a police lieutenant exam was job-related); Bernard v. Gulf Oil Corp., 890 F.2d 735, 746 (5th Cir.1989) (affirming the district court’s determination “that the tests Gulf used to determine which employees were eligible for promotion were job related, based upon the validation studies and expert testimony”), cert. denied, 497 U.S. 1003, 110 S.Ct. 3237, 111 L.Ed.2d 748 (1990); Berkman v. City of New York, 812 F.2d 52, 59-60 (2d Cir.) (approving the district court’s conclusion that physical examinations used by the city to select entry-level firefighters were valid), cert. denied, 484 U.S. 848, 108 S.Ct. 146, 98 L.Ed.2d 102 (1987); Clady v. County of Los Angeles, 770 F.2d 1421, 1430-32 (9th Cir.1985) (affirming the district court’s conclusion that a written examination used by the county to hire firefighters was valid), cert. denied, 475 U.S. 1109, 106 S.Ct. 1516, 89 L.Ed.2d 915 (1986); Rivera v. City of Wichita Falls, 665 F.2d 531, 538 (5th Cir. Unit A 1982) (affirming a district court finding that a police officer exam was job-related); Contreras v. City of Los Angeles, 656 F.2d 1267, 1281, 1284 (9th Cir.1981) (concluding that an auditor exam was job-related), cert. denied, 455 U.S. 1021, 102 S.Ct. 1719, 72 L.Ed.2d 140 (1982); United States v. Las Vegas Metropolitan Police Dep’t, D.Nev. (No. CV-S-84-809-RDF (LRL), June 11, 1991) (report and recommendation of magistrate judge) (finding a professionally-developed police officer exam to be lawful); cf. Guardians Ass’n v. Civil Serv. Comm’n, 630 F.2d 79, 103 (2d Cir.1980) (holding that an employer “faces a substantial task in demonstrating” the job-relatedness of a test, “[b]ut the task is by no means impossible”), cert. denied, 452 U.S. 940, 101 S.Ct. 3083, 69 L.Ed.2d 954 (1981); Craig v. County of Los Angeles, 626 F.2d 659, 664-66 (9th Cir.1980) (upholding the district court’s determination that success on a written exam was predictive of success at the police academy, but remanding for a determination of whether success at the academy correlated to job performance), cert. denied, 450 U.S. 919, 101 S.Ct. 1364, 67 L.Ed.2d 345 (1981); United States v. City of San Francisco, 696 F.Supp. 1287, 1297 (N.D.Cal.1988) (approving a consent decree that set out a schedule of test-development deadlines), affd in part and modified in part on other grounds sub nom. Davis v. City of San Francisco, 890 F.2d 1438 (9th Cir.1989), cert. denied, 498 U.S. 897, 111 S.Ct. 248, 112 L.Ed.2d 206 (1990).
Moreover, the conclusion that job selection procedures cannot be brought into compliance with Title VII necessarily implies that Congress set up a legal requirement that is impossible to meet. We are loath to impute such a gross error to our nation’s elected representatives. Had Congress shared the district court’s belief that validation of selection procedures was “unrealistic, unworkable, and unwise,” then Congress “would not have made a specific exception to Title VII for the *1574proper use of professionally designed tests.” Guardians Ass’n v. Civil Serv. Comm’n, 630 F.2d 79, 89 (2d Cir.1980), cert. denied, 452 U.S. 940, 101 S.Ct. 3083, 69 L.Ed.2d 954 (1981). Valid tests may prove administratively burdensome to design and validate, but minimizing inconvenience is not a constitutional value. It certainly does not outweigh the importance of ending racial discrimination. See, e.g., Hayes v. North State Law Enforcement Ass’n, 10 F.3d 207, 216 (4th Cir.1993). As Judge Frank M. Johnson, Jr., has explained, “[t]he Constitution does not put a price on constitutional rights, in terms either of time or money. The rights guaranteed by the Constitution are to be made effective in the present.” Jack Bass, Taming the Storm 398 (1993) (quoting written statement made by Judge Johnson during confirmation proceedings regarding his appointment to the Court of Appeals). If the process of approving selection procedures places undue strain on the district court’s resources, it may appoint a special master to assist with the task.
Our conclusion that the development of valid job-selection procedures is feasible is buttressed by the fact that, even while complaining about the burdens of test-development, the Board claims that approximately two-thirds of the thirty-five exams it administered in 1991 had no disparate impact on the passing rate of blacks. The Board does not purport to claim that its tests are sufficiently “job-related” to satisfy Title VIL But its alleged success at developing tests with no disparate impact puts us at a loss to understand the Board’s refusal to subject even a single exam to judicial scrutiny and its vigorous opposition to any deadline for doing so. The Board’s self-professed capacity for designing non-discriminatory tests belies its contention that test-development is too tricky for deadlines.12
As Judge Clark recently noted for this Court, “our experience teaches us that on some occasions public employers prefer the supervision of a federal court to confronting directly [their] employees and the public.” United States v. City of Miami, 2 F.3d 1497, 1507 (11th Cir.1993). The Constitution was not designed to ease the lot of public officials, and it is not the role of federal courts to insulate public officials from the people. Instead, woven throughout the Constitution is a commitment to democratic self-rule, making public officials answerable to the people. While one of the most important duties of federal courts is to protect the constitutional and statutory rights of minorities, interference in the processes of another branch of government should be as narrow and short-lived as fulfilling that constitutional duty allows. Remedial decrees should require the responsible officials to end their unconstitutional action posthaste. Remedial decrees *1575should not foster prolonged oversight and management by the least representative branch. Federal court supervision of local government has always been “intended as a temporary measure” and should “ ‘not extend beyond the time required to remedy the effects of past intentional discrimination.’” Board of Educ. v. Dowell, 498 U.S. 237, 248, 111 S.Ct. 630, 637, 112 L.Ed.2d 715 (1991) (school desegregation case) (quoting Spangler v. Pasadena City Bd. of Educ., 611 F.2d 1239, 1245 n. 5 (9th Cir.1979) (Kennedy, J., concurring)).
Valid selection procedures are both possible in practice and constitutionally necessary. Therefore, on remand, the district court should set prompt deadlines for the City and the Board to develop and implement valid job-selection procedures.13
ii. Annual Goals
We now turn to a discussion of the decree’s annual goals, which guide the year-to-year actions of the City and Board. Such annual hiring goals may serve the ultimate purpose of eliminating discrimination in two different ways. First, affirmative action may be needed to remedy present discrimination where less-suspect means are unavailable or inadequate. Second, hiring preferences may be essential to cure the lingering effects of past discrimination. We first consider the extent to which these two purposes justify continued use of the annual goals; we then discuss how the annual goals should be modified to make their interim use narrowly tailored.
Until valid job-selection procedures are in place, some use of racial preferences is necessary to counteract the ongoing effects of racially discriminatory testing. Were such race-conscious decisionmaking not allowed prior to the implementation of race-neutral selection devices, the City and the Board would find themselves in the impossible position of trying to comply with Title VII on the basis of discrimination-tainted procedures. The Wilks class implicitly conceded as much at the modification hearing, and argues on appeal only that “supplemental” affirmative action should be disallowed in the absence of “a firm schedule for adoption of lawful tests.” We have already decided that adoption of such a schedule is necessary. Therefore, pending prompt implementation of valid selection procedures, the Board may continue to make race-conscious certifications to the City and the City may continue to take race into account when hiring and promoting. We will discuss later the character of race-conscious decisionmaking that is permitted.
In addition, even after valid selection procedures are in place, affirmative action may be needed to cure past discrimination by the City and the Board. However, we refuse simply to assume that the effects of past discrimination in public employment have endured or will endure indefinitely. For the past thirteen years, the decrees have mandated that the City and Board affirmatively hire blacks as a remedy for past wrongs. This court-approved remedy has apparently had substantial impact.
On remand, the district court must determine from evidence whether the effects of past City and Board discrimination persist. As long as significant specified effects linger, affirmative action may be justified despite the implementation of valid selection procedures. Public employers cannot escape their constitutional responsibilities merely by adopting facially-neutral policies that institutionalize the effects of prior discrimination and thus perpetuate de facto discrimination. See United States v. Fordice, — U.S. -, - - -, 112 S.Ct. 2727, 2735-36, 120 L.Ed.2d 575 (1992) (school desegregation case). Here, however, it is not at all clear that broad affirmative action is still needed to cure past discrimination by the City and the Board. After thirteen years of racial preferences — and even longer with respect to firefighters and police officers— the district court should consider the retro-*1576speetive, remedial purpose of affirmative action satisfied except where it finds that past discrimination continues to taint a particular position. Absent such findings, and once valid selection procedures have been adopted, affirmative action will no longer be legitimate; the goals of rectifying past and present discrimination will have been achieved.
Having discussed the circumstances in which the City and the Board may continue to use annual affirmative action goals, we now discuss the form that any further affirmative action must take. Affirmative action, when allowed, must be flexible, reasonably related to the pool of qualified minorities, and impose no undue burden on innocents. See Howard v. McLucas, 871 F.2d 1000, 1008 (11th Cir.), cert. denied, 493 U.S. 1002, 110 S.Ct. 560, 107 L.Ed.2d 555 (1989). As presently written, the City and Board decrees’ affirmative action provisions do not satisfy these requirements.
The present annual “goals” for blacks lack flexibility. These goals have been set, apparently arbitrarily, at figures ranging from twenty-five to fifty percent, depending on the position. We might allow such fixed-percentage “goals,” under the theory that they represented an estimate of the speed with which past discrimination could be eradicated, if they were in fact treated as goals rather than absolute commandments. The Cone Corp. Court, for example, upheld a plan that set a goal of twenty-five percent minority participation because the county granted waivers whenever that goal could not be achieved. Cone Corp. v. Hillsborough County, 908 F.2d 908, 916-17 (11th Cir.), cert. denied, 498 U.S. 983, 111 S.Ct. 516, 112 L.Ed.2d 528 (1990). Here, by contrast, the annual appointment “goals” have been applied as rigid quotas. In the early 1980s, the City mechanically appointed equal numbers of blacks and whites to fire department positions without any consideration of relative qualifications in order to meet the stated fifty-percent “goal.” In 1989, the City promoted to fire lieutenant seven blacks previously found by a City review board to be unqualified — despite the competing candidacy of several whites found by the review panel to be more qualified. The City apparently viewed its annual fifty-percent “goal” as mandatory, and believed that if it did not promote blacks and whites in approximately equal numbers, then it could make no appointments at all. As implemented, these goals lack the flexibility that the Constitution requires.
Despite its rigid application of the annual goals, the City contends that two provisions in its decree create sufficient flexibility to satisfy strict scrutiny. The City chiefly relies on paragraph two of its decree, which provides:
Nothing herein shall be interpreted as requiring the City to hire unnecessary personnel, or to hire, transfer, or promote a person who is not qualified, or to hire, transfer or promote a less qualified person, in preference to a person who is demonstrably better qualified based upon the results of a job-related selection procedure.
According to the City, this paragraph allows the City to adjust its “goals” when there is an insufficient pool of qualified black applicants.
We find the City’s interpretation unpersuasive. On its own terms, paragraph two does not permit departure from the “goals” unless and until the Board develops “a job-related selection procedure” — i.e., a test that can accurately determine the relative qualifications of candidates. See In re Birmingham Reverse Discrimination Employment Litig., 833 F.2d 1492, 1497 (11th Cir.1987) (discussing the district court’s understanding that paragraph two does not apply until validated exams are in place), aff'd sub nom., Martin v. Wilks, 490 U.S. 755, 109 S.Ct. 2180, 104 L.Ed.2d 835 (1989). While paragraph two may underscore the need for valid selection procedures, absent such procedures it does not help the City survive strict scrutiny.
The City also suggests that paragraph five of its decree infuses significant flexibility into the City’s hiring and promotion goals. That paragraph provides, in relevant part:
The parties also preserve the right to adjust, through agreement and subject to the approval of the Court, any of the goals provided by this Decree where it can be shown that a professional degree, license *1577or certificate is required to perform the duties of any particular job or jobs in the City’s workforce and that blacks and/or women hold such degrees, licenses or certificates in percentage terms which are inconsistent with the goals provided.
This clause mitigates the rigidity of the City decree’s “goals” in some situations, but it does not go far enough. First, while paragraph five allows the City to take account of the unavailability of sufficient blacks with degrees and licenses, it imposes no duty to do so. The requirement of “narrow tailoring” is obligatory, not permissive. Second, the clause focuses only on “degrees, licenses, and certificates.” Such an unnecessarily limited scope is improper. When determining the proportion of blacks in the qualified labor pool, the City and Board should also take into account other objective prerequisites for employment, such as age or experience requirements, for which data is reasonably available. Where the City always makes promotions to a particular senior position from among individuals holding a particular junior position, the relative proportion of blacks in the junior position will generally be the most significant determinant of the proportion of blacks in the qualified applicant pool. Finally, paragraph five of the City decree applies only to the City, not to the Board.
Thus, in their present form, the annual goals are unconstitutionally unrefined. On remand, the district court must re-write the decrees to make clear that the annual goals cannot last indefinitely. Once a valid selection procedure is in place for a particular position, neither the City nor the Board may continue to certify, hire, or promote according to a race-conscious “goal” absent proof of ongoing racial discrimination, or of the lingering effects of past racial discrimination, with respect to that position. Under no circumstances may the City hire or promote, or the Board certify, candidates who are demonstrably less qualified than other candidates, based upon the results of valid, job-related selection procedures, unless the district court finds that such appointments are necessary to cure employment discrimination by the City or Board.
In addition, the district court must re-write the decrees to relate the annual goals to the proportion of blacks in the relevant, objectively-qualified labor pool, calculated with reasonably available data. The district court may set an annual affirmative action goal that is greater than the proportion of blacks in the qualified labor pool if the district court finds that unlawful employment discrimination by the City or Board has reduced the proportion of blacks either in the qualified pool or in the position itself. In such circumstances, the district court may set a flexible goal that does not unduly burden the interests of innocent third parties and that is reasonably related to the pool of qualified blacks. See, e.g., Cone Corp. v. Hillsborough County, 908 F.2d 908, 916-17 (11th Cir.1990) (approving a flexible affirmative action goal set at approximately twice the proportion of minorities in the qualified pool); Howard v. McLucas, 871 F.2d 1000, 1008 (11th Cir.) (approving a flexible, 50% affirmative action goal in order “expeditious[ly]” to remedy the identified effects of unlawful discrimination), cert. denied, 493 U.S. 1002, 110 S.Ct. 560, 107 L.Ed.2d 555 (1989); cf. In re Birmingham Reverse Discrimination Employment Litig., 20 F.3d 1525, 1542-43 (11th Cir.1994) (suggesting that affirmative action goals must be flexible and “tied in some reasonable manner” to the proportion of blacks in the qualified pool). Appropriately designed, such increased goals may hasten the end to judicial oversight by expeditiously remedying past discrimination.
The Constitution tolerates race-based remedies only when they are necessary either to remedy past discrimination or to correct present discrimination until valid selection procedures are in place. Affirmative action is at most a temporary treatment; a cure for discrimination requires more fundamental and more even-handed reform. We cannot allow stop-gap remedies to turn into permanent palliatives. Therefore, the district court is directed to order the City and the Board to develop race-neutral selection procedures forthwith, not at the casual pace the Board has passed off as progress for thirteen years. The Board’s decree is not a security blanket to be clung to, but a badge of shame, a *1578monument to the Board’s past and present failure to treat all candidates in a fair and non-discriminatory manner. Federal judicial oversight should provide public employers no refuge from their responsibilities. We are confident that, on remand, the district court will modify and enforce the decrees in a way that will bring that truth home.
C. MODIFICATION OF THE GENDER-CONSCIOUS AFFIRMATIVE ACTION PROVISIONS
We now consider what modifications are required to the decrees’ gender-based affirmative action provisions. We first consider the prerequisites for modification, and then discuss the nature of the required modifications.
1. Rufo’s First Prong and Its Adaptation: Prerequisites for Modification
As previously discussed, Rufo normally permits modification only to accommodate “a significant change in facts or law.” Rufo v. Inmates of Suffolk County Jail, — U.S. -, -, 112 S.Ct. 748, 765, 116 L.Ed.2d 867 (1992). However, we must adapt that general rule to the peculiar procedural posture of the present case. Rufo involved, and envisions, a typical consent decree modification proceeding in which all the participants are parties to the original decree. Cf Fed.R.Civ.P. 60(b) (allowing parties to seek decree modifications). Parties to a consent decree are estopped by their status as signatories from challenging the decree’s validity under law existing when they accepted the decree. In re Birmingham Reverse Discrimination Employment Litig., 833 F.2d 1492, 1501 (11th Cir.1987), aff'd sub nom., Martin v. Wilks, 490 U.S. 755, 109 S.Ct. 2180, 104 L.Ed.2d 835 (1989). As a result, where a modification proceeding involves only parties to the original decree, a change in law or fact is a prerequisite to modification or termination of the decree.
That was Rufo, but this case is different. Consistent with the Supreme Court’s decision in Martin v. Wilks, the district court allowed the Wilks class, which was not a party to the original decrees, to intervene in the present modification proceeding. The Wilks intervenors, unlike the original parties, are not estopped from collaterally attacking the validity of the decree as originally adopted. Martin v. Wilks, 490 U.S. at 761-62, 109 S.Ct. at 2184. In fact, they are doing just that in the parallel reverse-discrimination case.
This atypical situation raises the question whether intervenors, like parties, may challenge a consent decree’s validity based on changes in the law alone, or instead may seek modifications even if there has been no change in the law.14 Rufo does not consider or answer this question, which should not recur often.15
Common sense demands that inter-venors be allowed to challenge the constitutional validity of a consent decree under the law that exists at the time of the challenge, irrespective of whether that law has changed since the decree was entered. Because in-tervenors may seek to alter or dissolve a *1579consent decree through a collateral attack, In re Birmingham Reverse Discrimination Employment Litig., 833 F.2d 1492, 1496 & n. 13, 1498-99 (11th Cir.1987), aff'd sub nom., Martin v. Wilks, 490 U.S. 755, 109 S.Ct. 2180, 104 L.Ed.2d 835 (1989), it is pointless to prohibit a similar challenge in a modification proceeding. It is far better to resolve all of the modification questions at one time rather than to split those questions between two or more proceedings.
We hold that, in the unusual circumstances of this case, the intervenors may bring challenges based on current law, regardless of whether that law has changed. Accordingly, modifications are warranted if necessary to prevent the decrees from violating governing constitutional standards — whether or not those standards had already been announced at the time the decrees were entered. Only by so adapting Rufo’s prerequisite to the unusual posture of the present case can we adhere to Rufo’s spirit: a call for “flexible,” prospective reconsideration of aging consent decrees to ensure their continuing validity. Moreover, although our holding may at first appear to make consent decrees more vulnerable, it should have just the opposite effect. A modification proceeding may, to the extent outlined above, be used to make constitutional an otherwise unconstitutional decree — saving it from continuing collateral attack.
We now consider whether existing constitutional standards require modification of these decrees’ gender preferences. When the district court entered the decrees, the Supreme Court had recently decided that gender-based classifications were subject to intermediate scrutiny under the Equal Protection Clause. Craig v. Boren, 429 U.S. 190, 197, 97 S.Ct. 451, 457, 50 L.Ed.2d 397 (1976). In addition, the Supreme Court had specifically employed an intermediate scrutiny standard in upholding a gender-conscious government program designed to “[reduce] the disparity in economic condition between men and women caused by the long history of discrimination against women.” Califano v. Webster, 430 U.S. 313, 317, 97 S.Ct. 1192, 1194, 51 L.Ed.2d 360 (1977). The decision in Mississippi University for Women v. Hogan, 458 U.S. 718, 102 S.Ct. 3331, 73 L.Ed.2d 1090 (1982), clarified that a classification must pass intermediate scrutiny even if the state’s asserted purpose is benign. Id. at 728, 102 S.Ct. at 3338.
It has been suggested that Croson changed the rule established by Craig, Cali-fano, and Hogan, so that gender-based affirmative action is now subject to strict scrutiny just like race-based affirmative action. See John Galotto, Note, Strict Scrutiny for Gender, Via Croson, 93 Colum.L.Rev. 508, 508 (1993) (“Croson compels the application of strict scrutiny to all forms of gender discrimination.”); but see Peter Lurie, Comment, The Law as They Found It: Disentangling Gender-Based Affirmative Action Programs from Croson, 59 U.Chi.L.Rev. 1563, 1564 (1992) (“One standard, intermediate scrutiny, must apply to all gender classifications.”). Indeed, several post-Croson cases have, with little or no discussion, followed this approach. See Brunet v. City of Columbus, 1 F.3d 390, 404 (6th Cir.1993) (“Under the precedent in this Circuit, gender based affirmative action plans are subject to strict scrutiny when challenged under the Equal Protection Clause.”); Long v. City of Saginaw, 911 F.2d 1192, 1196 (6th Cir.1990) (“The strict scrutiny standard was adopted by a majority of the Court in [Croson ] as the standard by which ‘affirmative action’ cases are to be reviewed.”); Conlin v. Blanchard, 890 F.2d 811, 816 (6th Cir.1989) (applying strict scrutiny, without discussion, to a gender-conscious affirmative action program); American Subcontractors Ass’n v. City of Atlanta, 259 Ga. 14, 376 S.E.2d 662, 664 (1989) (striking down a race- and gender-conscious affirmative action program under “a strict scrutiny standard, the appropriateness of which is conceded by the parties”).
We find those cases unpersuasive. Nothing in Croson suggests that the Supreme Court intended sub silentio to strike down its own decisions applying intermediate scrutiny to gender classifications. While it may seem odd that it is now easier to uphold affirmative action programs for women than for racial minorities, Supreme Court precedent compels that result. Compare Croson, 488 U.S. at 498-508, 109 S.Ct. at 724-30 (applying strict scrutiny to race-based affirmative *1580action) with Califano, 430 U.S. at 317, 97 S.Ct. at 457 (applying intermediate scrutiny to gender-based affirmative action). We may not, of course, disobey the Supreme Court.
We also note that each post-Crosow case that has considered in detail whether Croson applies to gender classifications has concluded that it does not. Contractors Ass’n v. City of Philadelphia, 6 F.3d 990, 1000-01 (3d Cir.1993); Coral Constr. Co. v. King County, 941 F.2d 910, 930-31 (9th Cir.1991), cert. denied, — U.S. -, 112 S.Ct. 875, 116 L.Ed.2d 780 (1992); cf. Milwaukee County Pavers Ass’n v. Fiedler, 922 F.2d 419, 422 (7th Cir.) (“Croson is about favoritism toward racial and ethnic groups, not about favoritism toward women. The Supreme Court does not consider discrimination against women to be as invidious ... as discrimination against blacks or other racial minorities; nor ... does it consider discrimination against men to be as invidious as racial discrimination.”), cert. denied, 500 U.S. 954, 111 S.Ct. 2261, 114 L.Ed.2d 714 (1991); see also Lamprecht v. Federal Communications Comm’n, 958 F.2d 382, 391 (D.C.Cir.1992) (majority opinion of Thomas, Circuit Justice). A year after Cro-son, we recognized that intermediate scrutiny still applied in gender discrimination cases: “For a considerable time now, the law has been quite clear that [discrimination] on the basis of sex is unconstitutional, unless that conduct is ... substantially related to the furtherance of an important government interest.” Nicholson v. Georgia Dep’t of Human Resources, 918 F.2d 145, 148 (11th Cir.1990).
Our decision in Cone Corp. v. Hillsborough County, 908 F.2d 908 (11th Cir.), cert. denied, 498 U.S. 983, 111 S.Ct. 516, 112 L.Ed.2d 528 (1990), says nothing to the contrary. There, we held that a race- and gender-conscious “minority business enterprise” program survived strict scrutiny. Id. at 914-17. We did not consider whether a less-exacting standard applied to the gender-conscious provisions of the program. We did not need to do so, given our holding that the plan satisfied even the searching Croson test. Intermediate scrutiny remains the applicable constitutional standard in gender discrimination cases.
Although there has been no significant change in the governing constitutional standard since the gender-conscious provisions of the decrees were adopted, for reasons we have discussed relating to the presence of intervenors, those provisions nevertheless must comply with present constitutional standards. We next explain why the gender-conscious provisions of the decrees are unconstitutional and require further modification.
2. Rufo’s Second Prong: Suitably Tailored Modifications
“A consent decree must of course be modified if ... one or more of the obligations placed upon the parties has become impermissible under federal law.” Rufo v. Inmates of Suffolk County Jail, — U.S. -, -, 112 S.Ct. 748, 762, 116 L.Ed.2d 867 (1992). This rule requires us to evaluate the gender-conscious provisions of the consent decree under the equal protection standard articulated by Craig and Califano and clarified by Hogan. Under this standard, no gender preference can survive unless it is substantially related to an important government interest. Hogan, 458 U.S. at 724, 102 S.Ct. at 3336.
a. Intermediate Scrutiny’s First Requirement: An Important Government Interest in Gender-Based Relief
We are convinced that the City and Board have established a sufficiently important government interest to justify gender-conscious affirmative action. Under the intermediate scrutiny test, a local government must demonstrate some past discrimination against women, but not necessarily discrimination by the government itself. One of the distinguishing features of intermediate scrutiny is that, unlike strict scrutiny, the government interest prong of the inquiry can be satisfied by a showing of societal discrimination in the relevant economic sector. See, e.g., Hogan, 458 U.S. at 728-29, 102 S.Ct. at 3338 (comparing the social security preference upheld in Califano, which “took into account” that women had been hindered from earning as much as men, with the all-female nursing program in Hogan, struck down in part because the state had made “no showing *1581that women lacked opportunities” in the field of nursing); cf. Coral Constr. Co. v. King County, 941 F.2d 910, 932 (9th Cir.1991) (noting that “[s]ome degree of discrimination must have occurred in a particular field before a gender-specific remedy may be instituted in that field,” but that “intermediate scrutiny does not require any showing of governmental involvement ... in the discrimination it seeks to remedy”), cert. denied, — U.S. -, 112 S.Ct. 875, 116 L.Ed.2d 780 (1992). The principal purpose of intermediate scrutiny is not so much to make sure that gender-based classifications are used only as a “last resort,” Hayes v. North State Law Enforcement Ass’n, 10 F.3d 207, 217 (4th Cir.1993) (racial discrimination ease), as it is to ensure that gender classifications are based on reasoned analysis rather than archaic stereotypes, see Contractors Ass’n v. City of Philadelphia, 6 F.3d 990, 1010 (3d Cir.1993) (“The Supreme Court has stated that an affirmative action program survives intermediate scrutiny if the proponent can show it was ‘a product of analysis rather than a stereotyped reaction based on habit.’ ” (quoting Metro Broadcasting, Inc. v. Federal Communications Comm’n, 497 U.S. 547, 582-83, 110 S.Ct. 2997, 3018-19, 111 L.Ed.2d 445 (1990))); Lamprecht v. Federal Communications Comm’n, 958 F.2d 382, 393 n. 3 (D.C.Cir.1992) (majority opinion of Thomas, Circuit Justice) (noting that intermediate scrutiny is intended to ensure reasoned analysis of classifications, and commenting that “analysis” is never “reasoned” when it rests on stereotypes rather than facts); Recent Case, 106 Harv.L.Rev. 804, 808 (1993). In a case such as this, in which there is no allegation that gender-based affirmative action was adopted because of “archaic and overbroad assumptions about the relative needs and capacities of the sexes,” Roberts v. United States Jaycees, 468 U.S. 609, 625, 104 S.Ct. 3244, 3253, 82 L.Ed.2d 462 (1984), the “important government interest” inquiry turns on whether there is evidence of past discrimination in the economic sphere at which the affirmative action program is directed.
The record before us contains substantial anecdotal and statistical evidence of past discrimination against women, including discrimination by both the City and the Board. For example, “[f]or many years announcements for positions as police patrolman and firefighter were restricted to males only.” United States v. Jefferson County, 28 Fair Empl.Prac.Cas. (BNA) 1834, at 1838, 1981 WL 27018 (N.D.Ala.1981), aff'd, 720 F.2d 1511 (11th Cir.1983). Coupled with that, women were grossly underrepresented in a variety of City positions at the time the consent decrees were negotiated. Id. These and related findings by the district court, see id., justify the district court’s finding that “there is more than ample reason for the Personnel Board and the City of Birmingham to be concerned that they would be in time held liable for discrimination.” Id. We are satisfied that the City and Board have demonstrated an important government interest: eradicating gender discrimination against women in public employment.
b. Intermediate Scrutiny’s Second Requirement: A Substantial Relation to the Important Interest
The present decree is not substantially related to the goal of eliminating gender discrimination in public employment. That goal requires, at a minimum, the development of gender-neutral selection procedures — whether or not developed in conjunction with a program of affirmative female appointments designed to remedy discrimination against women. Otherwise, both discriminatory selection procedures and remedial gender-based appointments would likely continue forever. While the present decrees mandate appointment of women, for thirteen years these decrees have done little or nothing to promote the development of selection procedures that are fair to women. In fact, as with race, the Board has yet to demonstrate the gender-neutrality or job-relatedness of a single employment exam. This glaring failure suggests that the decrees have, in a very real sense, perpetuated gender discrimination by allowing the Board and the City to use biased tests coupled with gender preferences.
It was an abuse of discretion for the district court to permit such a potentially indefinite cycle of discrimination to continue. Per*1582petual use of affirmative action may foster the misguided belief that women cannot compete on their own. That notion is just “as pernicious and offensive as its converse, that women ought to be excluded from all enterprises because their place is in the home.” Coral Constr., 941 F.2d at 932 (quoting Associated General Contractors v. City of San Francisco, 813 F.2d 922, 941 (9th Cir.1987)). When affirmative action outlives the pressing necessity that justifies its use, it begins to breed the very “archaic and overbroad assumptions about the relative needs and capacities of the sexes” that it was designed to erase. Roberts v. United States Jaycees, 468 U.S. 609, 625, 104 S.Ct. 3244, 3253, 82 L.Ed.2d 462 (1984). In view of that phenomenon, it is not surprising that the class of female employees in this case urged the district court to impose a timetable for adoption of valid, job-related selection procedures.
On remand, the district court should modify the decree to impose a set of prompt deadlines on the City and the Board for the development of gender-neutral selection procedures. As these procedures are developed and put into place, the City and Board must stop employing any affirmative “goals” or quotas for female appointments unless further affirmative action is needed to eradicate lingering effects of discrimination against women. However, because gender goals need be only “substantially related” (rather than “narrowly tailored”) to their goal, compare, e.g., Kahn v. Shevin, 416 U.S. 351, 356 n. 10, 94 S.Ct. 1734, 1737 n. 10, 40 L.Ed.2d 189 (1974) (rejecting Justice Brennan’s dissenting opinion that a Florida property-tax exemption for widows that was intended to reduce the economic disparity between men and women should have been crafted as narrowly as possible to achieve that goal) with Croson, 488 U.S. at 507, 109 S.Ct. at 729 (requiring narrow tailoring), the decrees need not tie gender goals to the proportion of qualified female applicants.
IV. THE ATTORNEYS’ FEES ISSUE
Following the district court’s modification order, the Wilks class moved for an interim award of attorneys’ fees and expenses against the City pursuant to 42 U.S.C.A. § 1988(b) (Supp.1993) (“In any action or proceeding to enforce ... [§ 1983], the court, in its discretion, may allow the prevailing party ... a reasonable attorney’s fee_”). The Wilks class sought fees against the City in this modification proceeding for work performed by its counsel both in this proceeding and in the parallel, reverse-discrimination case. The district court summarily denied the fee request “without prejudice to refiling at a later date” in the reverse-discrimination ease.
“It is well-settled that a [civil rights] plaintiff is a prevailing party [under 42 U.S.C. § 1988] and thus ordinarily entitled to a fee award of ‘some kind’ if the plaintiff has succeeded on ‘any significant issue in litigation which achieves some of the benefit the parties sought in bringing suit.’ ” Church of Scientology Flag Serv., Org. v. City of Clearwater, 2 F.3d 1509, 1513 (11th Cir.1993) (quoting Hensley v. Eckerhart, 461 U.S. 424, 433, 103 S.Ct. 1933, 1939, 76 L.Ed.2d 40 (1983) (footnote omitted)). However, “no fee award is permissible until the plaintiff has crossed the ‘statutory threshold’ of prevailing party status.” Texas State Teachers Ass’n v. Garland Indep. Sch. Dist., 489 U.S. 782, 789, 109 S.Ct. 1486, 1492, 103 L.Ed.2d 866 (1989) (citing 42 U.S.C. § 1988). “[A]t a minimum,” the party claiming fees “must be able to point to a resolution of the dispute which changes the legal relationship between itself and the defendant.” Id. at 792, 109 S.Ct. at 1493. Moreover, a party cannot win fees on the basis of an interlocutory judgment that will not necessarily result in “some action (or cessation of action)” by the party against whom fees are sought. Hewitt v. Helms, 482 U.S. 755, 761, 107 S.Ct. 2672, 2676, 96 L.Ed.2d 654 (1987).
Under the law of this Circuit, we may decide, rather than remanding the issue the district court, whether the Wilks class now a prevailing party entitled to an interim award of attorneys’ fees and costs. See Jones v. Diamond, 636 F.2d 1364, 1381-83 (5th Cir. Jan. 29, 1981) (en banc). In light of our decision in this appeal, the Wilks class is prevailing party under section 1988 insofar this modification proceeding case is concerned, and it is entitled to an appropriate *1583interim award of attorneys’ fees and costs against the City for that portion of its modification proceeding work on which it has succeeded. The class originally asked the district court to find the goals in the consent decrees to be unconstitutional. On appeal, the class urged this Court to order the goals rewritten so that they would be narrowly tailored and to require that they be adequately founded on a compelling state interest. The class urged both the district court and this Court to modify the decrees to ensure the rapid development of race-neutral selection procedures. See Transcript of Conference, Feb. 19, 1991, at pp. 24-27. We have held that the affirmative action provisions of the consent decrees are not narrowly tailored; we have accordingly remanded the case to the district court with instructions to rewrite those provisions. We have specifically directed the district court to eliminate the City’s present long-term goals, which are based on the proportion of blacks in the civilian labor-force, and to replace those goals with a schedule of reasonably prompt deadlines under which the City must develop race-neutral selection procedures. That ruling will result in “some action” by the City that is beneficial to the Wilks class, see Hewitt, 482 U.S. at 761, 107 S.Ct. at 2676, and effectively means that the Wilks class has succeeded on a “significant issue in [the] litigation which achieves some of the benefit [it] sought in bringing suit.” City of Clearwater, 2 F.3d at 1513 (internal quote marks omitted).
That we have not granted the identical relief originally sought by the class— complete elimination of all goals — is not dis-positive. To have prevailed, a party “need not obtain relief identical to the relief [that it] specifically demanded, as long as the relief obtained is of the same general type.” Ashley v. Atlantic Richfield Co., 794 F.2d 128, 131 (3d Cir.1986) (internal quotation marks omitted); cf. Ruffin v. Great Dane Trailers, 969 F.2d 989, 992-93 (11th Cir.1992) (reversing a denial of attorneys’ fees where the district court granted an injunction different from that sought by the plaintiff), cert. denied, — U.S. -, 113 S.Ct. 1257, 122 L.Ed.2d 655 (1993). The party seeking fees need only have received “actual relief on the merits of [the party’s] claim [that] materially alters the legal relationship between the parties by modifying the defendant’s behavior in a way that directly benefits the [party].” Farrar v. Hobby, — U.S. -, -, 113 S.Ct. 566, 573, 121 L.Ed.2d 494 (1992). The Wilks class had sought the elimination of all race- and gender-conscious affirmative action. Our holdings move toward the elimination of race- and gender-conscious personnel decisions by restricting the scope and duration of the affirmative action provisions of the decrees. The Wilks class has thus obtained relief on the merits of the same general type as it originally sought, even if to a lesser extent than it might have liked. Cf. Texas State Teachers, 489 U.S. at 793, 109 S.Ct. at 1494 (“[T]he degree of the plaintiffs overall success goes to the reasonableness of the award ... not to the availability of a fee award vel non.”). The legal relationship between the Wilks class and the defendants has been materially altered in the direction sought by the class. The Wilks class is therefore a prevailing party insofar as the modification proceedings case is concerned. The district court’s denial of attorneys’ fees for the Wilks class is vacated and remanded with instructions that the class be awarded reasonable attorneys’ fees for work in this modification proceeding case.16
Y. CONCLUSION
The district court’s modification orders are REVERSED in part. On remand, the district court should determine whether the City and the Board have a strong evidentiary basis for their conclusion that race-based remedies are necessary to cure public employment discrimination in departments other than the police and fire departments. If not, the race-based affirmative action provisions that apply to those other departments are unconstitutional and must be terminated. With respect to the police and fire departments, and all other departments for which race-based remedies are found to be justi*1584fied, the district court must re-write the decrees’ affirmative action provisions to make them narrowly tailored. The court is therefore directed to establish a schedule of reasonably prompt deadlines for' the City and the Board to develop and implement race-neutral selection procedures. In addition, the district court should restrict the decrees’ use of race-based preferences to circumstances in which race-based relief is necessary either to remedy the lingering effects of public employment discrimination against blacks, or until the City and the Board have implemented valid selection procedures.
The decrees’ gender-based preferences must be re-written to make them substantially related to the objective of ending discrimination against women. To that end, we direct the district court to establish a schedule of reasonably prompt deadlines for the City and the Board to develop and implement gender-neutral selection procedures. Unless needed to remedy lingering discrimination against women, gender preferences should be phased out as gender-neutral selection procedures are implemented.
In all other respects consistent with this opinion, the district court’s modification orders are AFFIRMED.17
We VACATE the district court’s order denying attorneys’ fees to the Wilks class, and REMAND for determination of an appropriate award in light of this opinion.
As outlined in this conclusion and explained in this opinion, the district court’s orders are AFFIRMED in part, REVERSED in part, VACATED in part, and REMANDED for further proceedings consistent with this opinion.
. The claims against these other government officials and agencies are not involved in this appeal.
. The 1989 amendment specifically allows the Personnel Board to certify, at the City's request, as many as five applicants for any entry-level police officer or firefighter vacancy. See Amendments of 1989, § 1, 1989 Ala.Acts at 970.
. Statistical analysis later showed that the new scoring key had made direct comparison of black and white applicants’ scores even less accurate at predicting black and white applicants’ relative job performance. See Ensley Branch, 13 Empl.Prac.Dec. (CCH) ¶ 11,504, at 6802.
.The Equal Protection Clause provides: ’’[N]or shall any State ... deny to any person within its jurisdiction the equal protection of the laws.” U.S. Const.Amend. 14, § 1.
. There is one possible, partial, exception to this statement. The Board decree allowed the Board to continue to administer the police officer and firefighter tests previously found illegal, "provided that certifications [were] in compliance with” the district court’s January 1977 order from the trial on those illegal tests. The 1977 order required race-conscious hiring "[p]ending adoption of some selection procedure which either has no adverse effect upon black applicants or is sufficiently job-related.” Ensley Branch, NAACP v. Seibels, 13 Empl.Prac.Dec. (CCH) ¶ 11,504, at *15576808, 1985 WL 1415 (N.D.Ala.1977), aff'd in part and rev'd in part, 616 F.2d 812 (5th Cir.), cert. denied, 449 U.S. 1061, 101 S.Ct. 783, 66 L.Ed.2d 603 (1980). However, it is not clear that the Board decree incorporated the 1977 order’s termination clause; none of the parties have suggested that it did so.
. The decree created special provisions for promotion of blacks to the more senior positions in the police and fire departments, and for promotion of women to police positions above the rank of sergeant. After a set number of blacks had been promoted to specified senior police positions, further promotions were to be made "at twice the black percentage representation in the job classifications from which promotional candidates are traditionally selected for those jobs." Women were to be promoted to police positions above the rank of sergeant “in percentages which are approximately equivalent to their percentage representation in the job classification from which promotional candidates are traditionally selected.”
. This is the only modification made that any party contends on appeal went too far. The Wilks class argues that "[t]he district court's imposition of supplemental Personnel Board referral goals without a firm schedule for adoption of lawful tests should be vacated.” We address the Wilks class' argument at page 1575, infra.
. As another circuit court said in a similar context, "[i]t may be that in the voluminous record [from two decades of litigation] this issue was addressed, but we are unable to find it." Brunet v. City of Columbus, 1 F.3d 390, 412 n. 10 (6th Cir.1993). This issue certainly was not addressed during the modification proceedings in the present case.
. The district court excluded certain evidence proffered by the Wilks class regarding the City's negotiation of its consent decree. This evidence is purportedly relevant to the compelling interest inquiry. Because we have held that the City and the Board had a compelling interest in affirma-five action in the police and fire departments, the Wilks class’ appeal on the evidentiary issue is moot with respect to those departments. As regards the other departments, ''[djistrict judges have broad discretion" to admit or exclude evidence, BankAtlantic v. Blythe Eastman Paine Webber, Inc., 955 F.2d 1467, 1476 (11th Cir.1992), cert. denied, - U.S. -, 113 S.Ct. 966, 122 L.Ed.2d 122 (1993), and "[a] district court's evidentiary rulings are not disturbed unless there is a clear showing of abuse of discretion,” U.S. Anchor Mfg., Inc. v. Rule Indus., Inc., 7 F.3d 986, 993 (11th Cir.1993). We are not convinced that the district court abused its broad discretion by excluding the Wilks class' proffered evidence. *1568The district court may, but is not required to, revisit that ruling on remand.
. The district court’s finding in the parallel case of past discrimination is not fully transferable to this proceeding. The Wilks class in this proceeding includes many persons who are not parties to the parallel case, persons who therefore cannot be bound by the result of that case. See Parklane Hosiery Co. v. Shore, 439 U.S. 322, 327 n. 7, 99 S.Ct. 645, 649 n. 7, 58 L.Ed.2d 552 (1979) ("It is a violation of due process for a judgment to be binding on a litigant who was not a party or a privy_").
. In February 1991, the district court engaged in the following colloquy with Ms. Battle, counsel for the Board:
THE COURT: I suppose my assumption ... is that there would be some acknowledgement that whatever the Board has done with respect to redefining or refining tests since 1981, it has not yet gotten to the point where there is a presentation that the tests would be shown and demonstrated as of this time to be job related.
*1572MS. BATTLE: Well, Your Honor, we do not intend at this hearing to put on specific evidence at all of job validity of any particular test. As I understand it, the only involvement that the Board has with respect to this hearing for changes to be augmented is what needs to be done for the City and, likewise, a timetable for winding down the process of the Board.
THE COURT: ... [I]t seems to me one aspect of evaluating the City's consent decree is to take into account that since '81 and to the present date, there really has not been developed and presented for some kind of validation new testing procedures, and that is a part of the backdrop of looking at whether there should be any modifications ....
MS. BATTLE: ... [B]ut the actual request of whether or not a particular test is valid is not something that the Board thinks is relevant.
THE COURT: Well, wouldn’t it be fair to say that the Board has not gotten to the position of wanting to demonstrate the validity at this point of any of the tests?
MS. BATTLE: That may be true.
THE COURT: And that is a factor that the Court has to be aware of in looking at the modification.
. Of course, the Board’s reluctance to validate its exams may reveal that it has not been as successful as it suggests at developing race-neutral selection procedures. The Board claims only that blacks and women pass many of its exams in close proportion to their representation in the applicant pool — not that blacks and women score as well as others. It may be that the Board’s present exams are accurate enough to determine which applicants are qualified, but are not accurate enough to rank fairly those who pass. See Guardians Ass’n, 630 F.2d at 100 ("A test may have enough validity for making gross distinctions between those qualified and unqualified for a job, yet may be totally inadequate to yield passing grades that show positive correlation with job performance.”); Ensley Branch, NAACP v. Seibels, 13 Empl.Prac.Dec. (CCH) ¶ 11,504, at 6804, 1977 WL 806 (N.D.Ala.1977) (noting that many tests may be accurate enough “to determine which individuals will exceed a given minimum standard of performance” but unable "to predict individuals' relative standing"), aff'd in part and rev'd in part on other grounds, 616 F.2d 812 (5th Cir.), cert. denied, 449 U.S. 1061, 101 S.Ct. 783, 66 L.Ed.2d 603 (1980). Even if this hypothesis is correct, it would not justify further race-conscious employment actions. Continued use of an exam to rank applicants, when the exam cannot predict applicants’ relative merits, offers nothing but a false sense of assurance based on a misplaced belief that some criterion — no matter how arbitrary — is better than none. Arbitrary, race-conscious hiring should not be tolerated after the Board has had thirteen years to come up with something better. If the Board cannot rank passing applicants in a valid manner because its tests are inadequate, then the Board could be ordered to use time-of-application, a lottery, or some other race-neutral device to select from among those who are qualified. See Guardians Ass'n, 630 F.2d at 104; cf. Brunet v. City of Columbus, S.D.Ohio (No. C2-84-1973, 1992 WL 540716, March 18, 1992) ("A lottery would be one example of a gender neutral selection device.”). At least then the racially discriminatory hiring would end.
. Under the present appointment system, the City selects its final choice for any given job vacancy from among a very small number of candidates certified to it by the Board. In making its final choice, the City appears to rely not only on the candidate's race, but also in part on interviews, evaluations of candidate experience, and other subjective criteria. By requiring the City to validate its procedures, we do not mean to condemn subjective screening tools. Nevertheless, Title VII applies to both the Ci1y and the Board.
. This question did not arise during our analysis of the consent decrees’ racial preferences because Croson, the controlling precedent, was handed down years after the entry of the consent decrees. Croson sufficiently changed the constitutional standards applicable to race to require modification under Rufo. Therefore, in the context of the racial preferences, we had no need to consider whether the Wilks class could challenge the decrees under constitutional standards in place when the decrees were written. This question is relevant in the context of gender, however, because the equal protection standards applicable to gender classifications have changed little these past thirteen years.
. There are two reasons this atypical situation is unlikely to recur. First, Martin v. Wilks should ensure from the outset that all interested parties participate in, and are thus bound by, consent decree proceedings that occur after that decision. Second, Congress has recently barred collateral, reverse-discrimination challenges to consent decrees by persons who fail to intervene in the original consent decree case despite having had actual notice. See 42 U.S.C.A. § 2000e-2(n) (Supp.1993). No one has argued that this statutory change undoes the Supreme Court's Martin v. Wilks decision as it affects the present litigation. We do not believe that it does, because section 2000e-2(n)(2) specifically provides that “[n]othing in this subsection shall be construed to ... apply to the rights of parties who have successfully intervened ... in the proceeding in which the parties intervened.”
. Whether the Wilks class is entitled to attorneys' fees for work done in the reverse-discrimination case is an issue that should be decided in that case.
. In addition, we note that the district court may revisit the decrees, in 1996 as it had planned, or at any other time, to decide whether these decrees should be terminated. The district court may also make any additional decree modifications appropriate for compliance with this Court’s decision in the parallel, reverse-discrimination case.